/* ADTAssignment.java, written for java2
   Author:  Zach Tomaszewski
   Date: 23 Sept 2001
 */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.NoSuchElementException;

/**
 * A digital clock ADT.  
 *
 * @author Zach Tomaszewski
 */

class TimeOfDay implements Comparable {

   private int hours;
   private int minutes;
                
 public static void main(String args[]){
    runTests();
 }
 
 /**
  * Creates a new instance intantiated to midnight (0:00).
  */
 protected TimeOfDay() {
   hours = 0;
   minutes = 0;
 }

 /**
  * Creates a new instance set to the specified time.  The time should
  * be given in a valid 24-hour format.
  * 
  * @param hours  The hour to set this TimeOfDay to
  * @param hours  The minutes to set this TimeOfDay object to
  * @throws InvalidInputException When it is not true that
  *                    0 <= hours < 24 or 0 <= minutes < 60
  */
 protected TimeOfDay(int hours, int minutes) throws InvalidInputException {
    this.setTime(hours, minutes);
 }


 /**
  * Sets this instance to the specified time.  The time should
  * be given in 24-hour format.  For example, use
  * <code>new TimeOfDay(0,0)</code> to set the time to midnight.
  * <code>new TimeOfDay(15,3)</code> would set the time to 15:03 (or 3:03pm).
  *
  * @param hours  The hour to set this TimeOfDay to
  * @param hours  The minutes to set this TimeOfDay object to
  */
 protected void setTime(int hours, int minutes) throws InvalidInputException{ 
   if (hours > 23 || hours < 0) {
     throw new InvalidInputException("Hours given are not between 0 and 23.");
   }else if (minutes >59 || minutes < 0) {
     throw new InvalidInputException("Minutes given are not between 0 and 59.");
   }else {
     this.hours = hours;
     this.minutes = minutes;
   }
 }


 /**
  * Increase this instance's time a positive number of minutes.
  * If more than 60 minutes are given,
  * the hours increase.  If the time would exceed 23:59, it rolls over to
  * 0:00 and the remainder of the minutes are added.
  * (In short, behavior models a real clock.)
  * This method does not decrease the time if a negative number of minutes
  * is given; instead, it simply does not increase the time (does nothing).
  *
  * @param minutes Number of minutes to increase the time.
  */
 protected void increaseTime(int minutes) {
    if (minutes < 0) { return; } //don't handle negative input
    int minutesToAdd = 0;          //initially...
    int hoursToAdd = minutes / 60;  //integer math; more than one hour here?
    if (hoursToAdd > 0) {             //avoid divide-by-zero
      minutesToAdd = minutes - (60 * hoursToAdd);
    }else {
      minutesToAdd = minutes;
    }

    this.minutes += minutesToAdd;
    if (this.minutes > 59) {
      /* minutesToAdd may exceed 59, but should never reach 120 */
      this.minutes -= 60;
      hoursToAdd++;
    }
    this.hours += hoursToAdd;
    if (this.hours > 23) {
      this.hours %= 24;
    }
 }


 /**
  * Returns the this time in 24 hour format, as in "16:19".
  *
  * @returns The time
  */
 protected String get24Time() {
    String time = "";
    if (hours < 10) {
      time = time + "0";
    }
    time = time + hours + ":";
    if (minutes < 10) {
      time = time + "0";
    }
    time = time + minutes;
    return time;
 }


 /**
  * Returns the this time in 12-hour format, as in "4:19PM".
  *
  * @returns The time
  */
 protected String get12Time() {
    String time = "";
    String meridian = "";
    if (hours < 10 && hours == 0) {
      time = time + "0";
    }
    if (hours > 12) {
       time = time + (hours - 12) + ":";
       meridian = "PM";
    }else{
       if (hours == 0) {
         time= time + "12:";  //0:00 == 12:00am
       }else {
         time = time + hours + ":";
       }
       meridian = "AM";
    }   
    if (minutes < 10) {
      time = time + "0";
    }
    time = time + minutes;
    time = time + meridian;
    return time;
 }


 /**
  *  Returns this instance's hours
  */
 protected int getHours() {
   return this.hours;
 }


 /**
  * Returns this instances's minutes
  */
 protected int getMinutes() {
   return this.minutes;
 }



 /**
  * Determines whether these two TimeOfDay objects are equal
  * (whether they have the same time).
  */
 public boolean equals(TimeOfDay tod){
   if (this.getHours() == tod.getHours() &&
       this.getMinutes() == tod.getMinutes()){
          return true;
   }else {
      return false;
   }
 }


 /**
  * Returns -1 if this object has an earlier time than the given object,
  * 1 if this time is later, or 0 if they are equal.
  */
 public int compareTo(Object obj){
     TimeOfDay tod = (TimeOfDay) obj;
     if (this.getHours() < tod.getHours()) {
       return -1;
     }else if (this.getHours() > tod.getHours()){
       return 1;
     }else {  //the hours are equal
       if (this.getMinutes() < tod.getMinutes()) {
          return -1;
       }else if (this.getMinutes() > tod.getMinutes()) {
          return 1;
       }else { //minutes are also equal
          return 0;
       }
     }
 }


 /**
  * A method used to test the other methods of this class.
  */
 private static void runTests() {
  try {
    TimeOfDay clock = null;
    StringTokenizer menuChoice;
    char firstChar = ' ';
    int hours, minutes;
    BufferedReader stdin = new BufferedReader(
                              new InputStreamReader(System.in));

    while (firstChar != 'e' && firstChar != 'E'){
      if (clock == null) {
        System.out.println("\nc \t --Create a new TimeOfDay instance "
                            + "with default time.");
        System.out.println("c TIME \t --Create a new TimeOfDay instance "
                            + "set to this 24-hour time");
        System.out.println("e \t --Exit.");
        System.out.println("Current time: [No instance created]");
        System.out.print("Enter a command: ");
      }else {
        System.out.println("\nc \t --Create a new TimeOfDay instance "
                            + "with default time.");
        System.out.println("c TIME \t --Create a new TimeOfDay instance "
                            + "set to this 24-hour time.");
        System.out.println("s TIME \t --Set the current instance to this "
                            + "24-hour time.");
        System.out.println("i MINUTES --Increment the current instance "
                            + "this many minutes.");
        System.out.println("e \t --Exit.");
        System.out.println("Current time: [" + clock.get24Time() + "] ||"
                            + " [" + clock.get12Time() + "]");
        System.out.print("Enter a command: ");
      }
      menuChoice = new StringTokenizer(stdin.readLine(), " ,:");

      if (menuChoice.countTokens() > 0) {
        firstChar = menuChoice.nextToken().charAt(0);
      }

      if (firstChar == 'c' || firstChar == 'C'){
        if (menuChoice.hasMoreTokens()){
          clock = new TimeOfDay(Integer.parseInt(menuChoice.nextToken()),
                                  Integer.parseInt(menuChoice.nextToken()));
        }else {
          clock = new TimeOfDay();
        }
      }else if (firstChar == 's' || firstChar == 'S'){
          clock.setTime(Integer.parseInt(menuChoice.nextToken()),
                         Integer.parseInt(menuChoice.nextToken()));
      }else if (firstChar == 'i' || firstChar == 'I'){
          clock.increaseTime(Integer.parseInt(menuChoice.nextToken()));
      }else if (firstChar == 'e' || firstChar == 'E'){
          //do nothing and drop through to the while loop
      }else {
          throw new InvalidInputException("That is not a valid menu option.");
      }
    }//end while
  }catch (IOException ioe){
  }catch (NumberFormatException nfe){
     System.out.println("\nYour menu selection did not contain an "
                         + "appropriate time. Please try again.");
     runTests();
  }catch (NoSuchElementException nsee){
     System.out.println("\nYour menu selection did not contain an "
                         + "appropriate time. Please try again.");
     runTests();
  }catch (InvalidInputException iie){
     System.out.println("\n" + iie.getMessage() + "  Please try again.");
     runTests();
  }

 }

}//end class




/**
 * Defines a sorted list of Objects.  Objects must implement 
 * java.lang.Comparable for sorting purposes.
 *
 * @author Zach Tomaszewski
 */
interface SortedList{

 /**
  * Determines whether a sorted list is empty.
  */
 public boolean sortedIsEmpty();

 /**
  * Returns the number of items that are in a sorted list
  */
 public int sortedSize();

 /**
  * Inserts item into its proper sorted position
  * in a sorted list. Throws an exception if the item
  * cannot be place in the list (list full)
  */
 public void sortedAdd(Comparable item);

 /**
  * Deletes item from a sorted list. 
  * Throws an exception if the item is not found.
  */
 public void sortedRemove(Comparable item) throws ListItemNotFoundException;

 /**
  * Returns the item at postion index of a sorted list,
  * if 1 <= index <= sortedSite(). The list is left unchanged 
  * by this operation. Throws an exception if the index is out of range
  */ 
 public Comparable sortedGet(int index) throws IndexOutOfBoundsException;

 /**
  * Returns the position where item belongs or exists in a sorted list; 
  * item and the list are unchanged. Items in the list must implement
  * java.lang.Comparable.
  */
 public int locateIndex(Comparable item);

}//end interface



/**
 * A sorted list of Comparable objects; max array size is 50 objects.
 * Objects placed in the
 * array must implement java.lang.Comparable for sorting purposes.
 *
 * @author Zach Tomaszewski
 */
class SortedListArrayBased implements SortedList{
  static final int MAX_SIZE = 50;
  private Comparable[] array;
  private int size;
           
 /**
  * Creates an empty sorted list
  */
 public SortedListArrayBased(){
   array = new Comparable[MAX_SIZE];
   size = 0;
 }


 /**
  * Determines whether a sorted list is empty.
  *
  * @returns True if the list contains no items
  */
 public boolean sortedIsEmpty(){
   return (size == 0) ? true : false;
 }


 /**
  * Returns the number of items that are in a sorted list
  */
 public int sortedSize() {
   return size;
 }


 /**
  * Inserts item into its proper sorted position
  * in a sorted list. Throws an exception if the item
  * cannot be place in the list (list full)
  *
  * @param item The Object to add to the list
  * @throws IndexOutOfBoundsException if the list is full
  */
 public void sortedAdd(Comparable item) throws IndexOutOfBoundsException{
   if (this.sortedSize() >= MAX_SIZE) {
      throw new IndexOutOfBoundsException("This sorted list has already "
                          + "reached max size; item cannnot be added.");
   }else {
      int insertIndex = this.locateIndex(item);
      for (int i = this.sortedSize() - 1; i >= insertIndex; i--) {
         this.array[i+1] = this.array[i];
      }
      this.array[insertIndex] = item;
      size++;
   }
 }


 /**
  * Deletes the specified item from a sorted list. 
  * 
  * @param item The specified item to remove
  * @throws ListItemNotFoundExcption if item does not exist in the list
  */
 public void sortedRemove(Comparable item) throws ListItemNotFoundException {
    //get the index (not the position)
    int removeIndex = this.locateIndex(item) - 1;
    if (this.sortedGet(removeIndex + 1).compareTo(item) != 0) { //position again
       /* this is not really the item we want; must not be in the list */
       throw new ListItemNotFoundException("Cannot delete");
    }else {   
      /* shuffle everything down, covering the unwanted item */
      for (int i = removeIndex; i <= this.sortedSize()-1; i++) {
        this.array[i] = this.array[i + 1];
      }
      size--;
    }
 }


 /**
  * Returns the item at the specified list postion,
  * if 1 <= position <= sortedSize(). The list is left unchanged 
  * by this operation. Throws an exception if the index is out of range
  *
  * @param position The position in the list from which to grab an object
  * @returns The object so found
  */
 public Comparable sortedGet(int position) throws IndexOutOfBoundsException {
   if (position < 1 || position > this.sortedSize()){
      throw new IndexOutOfBoundsException("Specified position is out of range");
   }else {
      return this.array[position - 1];
   }
 }


 /**
  * Returns the index where item belongs or exists in a sorted list; 
  * item and the list are unchanged. Items in the list must implement
  * java.lang.Comparable.
  *
  * @param item  The object to find in the array
  * @returns int  The index at which the object can be found
  */
 public int locateIndex(Comparable item) {
    return this.locateIndex(item, 0, size-1);
 }


 /**
  * Returns the index where item belongs or exists in a sorted list;
  * item and the list are unchanged. Items in the list must implement
  * java.lang.Comparable.
  *
  * @param item  The object to find in the array
  * @param first  Index at which to start searching
  * @param last   Index at which to stop searching
  * @returns   the index at which the object can be found
  */
 private int locateIndex(Comparable item, int first, int last) {
     int midpoint = (last + first)/2;
     
     if (first >= last) {     //one item array
       if (array[midpoint] != null && array[midpoint].compareTo(item) < 0) {
          return midpoint + 1;
       }else {
          return midpoint;
       }
     }else if (first == last - 1) {  //two item array
       if (array[midpoint].compareTo(item) > 0) {
          return midpoint;
       }else if (array[midpoint].compareTo(item) < 0 &&
           array[midpoint + 1].compareTo(item) > 0   ) {
              return midpoint + 1;
       }else {
          return midpoint + 2;
       }
       
     }else {
       if (array[midpoint].compareTo(item) == 0) {
          return midpoint; 
       }else if (array[midpoint].compareTo(item) > 0) { 
          last = midpoint;    /* take lower half of array */ 
          return this.locateIndex(item, first, last); 
       }else if (array[midpoint].compareTo(item) < 0) { 
           first = midpoint;  /* take upper half of array */
           return this.locateIndex(item, first, last);
       }else { //should never be needed, but needed to compile
          return -1;
       }
     }
 }

}//end class




/**
 * An application for testing SortedListArrayBased by using TimeOfDay
 * objects.  It queries the user for a number of times and adds them
 * to their proper places in a sorted list.
 *
 * @author Zach Tomaszewski
 */

class SortedListTester {

 public static void main(String[] args) {

   SortedListArrayBased slab = new SortedListArrayBased();
   String nextTime = "not an empty string";
   StringTokenizer stringT;
   int hours, minutes;

  try{
    BufferedReader stdin = new BufferedReader(
                             new InputStreamReader(System.in));

    while (!nextTime.equals("")) {
      System.out.println("Ordered list currently contains: ");
      printList(slab);
      System.out.print("Add a time to the list or hit Enter to quit: ");
      nextTime = stdin.readLine();
     try{
      if (!nextTime.equals("")){
        stringT = new StringTokenizer(nextTime, " ,:");
        hours = Integer.parseInt(stringT.nextToken());
        minutes = Integer.parseInt(stringT.nextToken());
        slab.sortedAdd(new TimeOfDay(hours, minutes));
      }
     }catch (Exception e) {
       System.out.println(e.getClass().getName());

       System.out.println("Time format unrecognized.  Please try again.");
     }
    }//end while
  }catch (IOException ioe) {
    System.err.println("Problem with IO!");
  }
 }

 protected static void printList(SortedListArrayBased slab) {
   int index = 1;
   while (index <= slab.sortedSize()){
     System.out.print("[" +
                    ((TimeOfDay)slab.sortedGet(index)).get24Time() +
                    "] ");
     index++;
   }
   System.out.println();
 }

}//end class




/**
 * An exception convenient for when a method recieved parameters it can't
 * handle, especially when those parameters are documented in the method's
 * description.
 */
class InvalidInputException extends Exception {

   public InvalidInputException() {
     super();
   }

   public InvalidInputException(String s) {
     super(s);
   }
}//end class


/**
 * For when a specified item is not in a list.
 */
class ListItemNotFoundException extends Exception {

   public ListItemNotFoundException() {
     super();
   }

   public ListItemNotFoundException(String s) {
     super(s);
   }
}//end class