class OrderedContainer {


  private Comparable[] items;
  private int count;
  
  private static final int DEFAULT_SIZE = 2;
  private static final int GROW_AMOUNT = 2;
  private static final String NL = System.getProperty ("line.separator");
  
  
  public OrderedContainer () {
    count = 0;
    items = new Comparable[DEFAULT_SIZE];
  }
  
  
  public OrderedContainer (int size) {
    count = 0;
    items = new Comparable[size];
  }
  
  
  
  
  public String toString() {
    
    String retString = "Count: " + count + ", Length: " + items.length + NL;
  
    for (int index=0; index < count; index++) {
      retString += items[index] + NL;
   }
  
    return retString;
  }
  
  
  public int size() {
    return count;
  }
  
  
  /*
   * PROBLEM #1
   * MODIFY THIS METHOD
   *...so that it always returns true by growing
   */
  public boolean add(Comparable item) { 
  
    if (count >= items.length)
      grow();

      
   
    int hole = count;
    for ( ; hole > 0; hole--) {
      if (items[hole-1].compareTo(item) > 0)
        items[hole] = items[hole-1];
      else
        break;
    }
    
    items[hole] = item;
    count++;
    
    return true;
  }



  /*
   * PROBLEM #3
   * Complete this method so that it returns the _n_ items
   * beginning with the one provided (_start_), or nothing 
   * if start is not there.
   *
   * HINT: You may want a getIndex helper method...
   */
   
  private int getIndex(Comparable item) {
    int left = 0;
    int right = count-1;
    int pivot = left + (right-left)/2;
  
    while (right >= left) {
    
      int difference = items[pivot].compareTo(item);
    
      if (difference == 0) return pivot;
    
      if (difference > 0) 
        left = pivot-1;
      else
        right = pivot+1;
      
      pivot = left + (right-left)/2;
    }
    
    return -1;
    /* 
    int startingIndex = 0;
    for ( ; startingIndex < count; startingIndex++) {
      if (items[startingIndex].compareTo(start) == 0)
        break;
    }
    
    if (startingIndex == count) return -1;
    return startingIndex;
    */
  }
  public OrderedContainer getNFrom (Comparable start, int n) {

    OrderedContainer newContainer= new OrderedContainer(n);
    
    // Find the starting place
           
    int startingIndex = getIndex(start);
    
    if (startingIndex == -1) return newContainer; // Found nothing
    
    // Copy the items
    for (int index=0; index < n; index++) {
      if ((startingIndex+index) == items.length) break;
      
      newContainer.add(items[startingIndex+index]);
    }
    
    return newContainer; // Found items
  }


 
  /*
   * PROBLEM #2
   * MODIFY THIS METHOD...
   * so that the container is grown by EXACTLY TWO elements
   */
  public void grow() {
  
    Comparable[] biggerItems = new Comparable[items.length+GROW_AMOUNT];
    
    for (int index=0; index < count; index++) {
    
      biggerItems[index] = items[index];
    }
    
    items = biggerItems;
  }


  public static void main (String[] args) {
    OrderedContainer oc = new OrderedContainer();

    System.out.println ("****************************");
    System.out.println ("***** THIS OUTPUT WILL NOT BE CONSISTENT UNTIL YOUR METHODS ARE CORRECT!");
    System.out.println ("****************************");
    System.out.println ("");
    System.out.println ("");

    System.out.println ("***** Testing grow by two...notice the growth by exactly 2.");
    System.out.println ("");
    
    System.out.println ("This container holds nothing (empty).");
    System.out.println ("Should be Count: 0, Length: 2");
    System.out.println (oc);
  
    System.out.println ("This container holds Apple, Banana, & Orange.");
    System.out.println ("Should be Count: 3, Length: 4");
    oc.add("Orange");
    oc.add("Apple");
    oc.add("Banana");
    System.out.println (oc);
  
    System.out.println ("This container holds Apple, Banana, Grapefruit, Orange, Pear, and Watermelon.");
    System.out.println ("Should be Count: 6, Length: 6");
    oc.add("Watermelon");
    oc.add("Pear");
    oc.add("Grapefruit");
    System.out.println (oc);

    
    System.out.println ("");
    System.out.println ("");

    System.out.println ("***** Testing getNFrom(...)...");
    System.out.println ("");

    System.out.println ("1 from Apple is just Apple...");
    System.out.println (oc.getNFrom("Apple", 1));
    System.out.println ("");

    System.out.println ("2 from Apple is Apple, Banana...");
    System.out.println (oc.getNFrom("Apple", 2));
    System.out.println ("");

    System.out.println ("3 from Grapefruit is Grapefruit, Orange, Pear...");
    System.out.println (oc.getNFrom("Grapefruit", 3));
    System.out.println ("");

    System.out.println ("3 from Pear (2nd to last) is Pear, Watermellon...");
    System.out.println (oc.getNFrom("Pear", 3));
    System.out.println ("");

    System.out.println ("2 from NonExistant is nothing...");
    System.out.println (oc.getNFrom("NonExistant", 2));
    System.out.println ("");

    

  }
}