/* Code for COMP 103 Assignment 5 T3 2006
 * Name:
 * Usercode:
 * ID:
 */

import java.util.*;

/**
  * SortedArraySet - an implementation of Set
  * 
  * The implementation uses an array to store the items.
  * It keeps the items in order, determined by a comparator
  *  provided to the constructor
  *  
  * It does not allow null as an element of a set.
  * It is efficient for accessing items; it is slower to insert.
  * When full it will create a new array of double the current size, and
  *  copy all the items over to the new array
  */

public class SortedArraySet < E > extends AbstractSet < E >  {

  // data fields
  private static int INITIALCAPACITY = 10;
  private int count = 0;
  private E[] data;

  private Comparator < E > comp;                  // the comparator

  /** Constructs an empty SortedArraySet that will use the given comparator */
  public SortedArraySet(Comparator < E > comp) {
    data = (E[])new Object[INITIALCAPACITY];
    this.comp = comp;
  }

  /** Constructs an SortedArraySet that will use the given comparator
    *  and initially contains all the items in the given collection (with
    *  duplicates removed) 
    */
  public SortedArraySet(Collection < E > col, Comparator < E > comp) {
    // YOUR CODE HERE


    
    removeDuplicates();         // the collection may have had duplicate values.
  }

  /** Returns true iff the collection is empty */
  public boolean isEmpty() {
    return count == 0;
  }

  /** Returns the number of elements in collection */
  public int size() {
    return count;
  }


  /** Returns true iff the set contains an item */
  public boolean contains(Object item) {
    int index = findIndex(item);
    if (index >= 0 && data[index] != null)
      return true;
    return false;
    // YOUR CODE HERE
  }

  /** Adds the specified element to this set if it is not already present 
    * Returns true if the collection changes, and false if it did not change. 
    */
  public boolean add(E item) {
    int index = findIndex(item);                  // where item should be.
    System.out.println("We got index: " + index);    
    if (index < 0 || index > count)
      throw new IndexOutOfBoundsException();
    if (item == null){
        System.out.println("NULL!! not adding this piece of crud");
      throw new NullPointerException();
    }
    // YOUR CODE HERE
    //add - ensureCapacity. Then move all items along whilst adding the new item
    // in first.
    ensureCapacity();

    if (data[index] == null) {//at the end of the array so just append to end and increment count     
         data[count] = item;
         count++;
         return true;
    } else if (data[index].equals(item)){
        return false;
    } else {
         for (int i=count; i> index; i--){
         data[i]=data[i-1];
         }
         System.out.println("adding: " + item + " over " + data[index] + " count at: " + count);
         data[index]=item;//insert value
         count++;
         return true;
    }
    
/*    
    if (data[index] != null && data[index].equals(item)) {
      System.out.println("Already exists");
      return false;
    }
    else {
      ensureCapacity();
      for (int i = count-1; i == index; i--) {  //move items along
        System.out.println("Moving: " + data[i] + " over " + data[i+1]);
        if (data[i+1] != null)
            data[i + 1] = data[i];
      }
      System.out.println("adding: " + item + " over " + data[index] + " count at: " + count);
      data[index] = item;
      count++;   
                                          //increment count by 1
      return true;
    }
    */
  }


  /** Remove the element matching a given item
    * Returns true if the collection changes, and false if it did not change. 
    */
  public boolean remove(Object item) {
    if (item == null)
      return false;
    int index = findIndex(item);
    // YOUR CODE HERE
    System.out.println("Deleting " + data[index]);
    for (int i = index; i < count-1; i++) {
      data[i] = data[i+1];
    }
    count--;                                      //decrement count by 1
    return true;
  }

  /** Returns an iterator over the elements in this set. **/
  public Iterator < E > iterator() {
    return new SortedArraySetIterator < E > (this);
  }


  // SortedArraySet utility methods

  /** Find the index of where an element is in the dataarray,
    *  (or where it ought to be, if it's not there).
    *  Assumes that the item is not null.
    *  Uses binary search and requires that the items are kept in order. 
    */
  private int findIndex(Object itm) {
    //Comparable < E > temp = (Comparable < E > )itm;
    E item = (E)itm;
    Comparable < E > temp = (Comparable < E > )item;
    int low = 0;
    int high = count;
    int mid = 0;

    if (isEmpty()) return 0; //if the array is empty just return 0
    if (low >=high) return low;
    while (low < high){
        mid=((low+high)/2);
        if (temp.compareTo(data[mid]) == 0)
            return mid;//this is it
        else if (temp.compareTo(data[mid]) > 0)
            low = mid+1;
        else
            high = mid;
    }
    //if we reach here we have not found the element we are looking for but this
    // is where we want it so..
    return low;
  }
  /** Ensure data array has sufficient number of elements
    * to add a new element 
    */
  private void ensureCapacity() {
    if (count < data.length)
      return;
    E[] newArray = (E[])new Object[data.length * 2];
    for (int i = 0; i < count; i++)
      newArray[i] = data[i];
    data = newArray;
  }

  /** Removes any duplicate items in a single pass,
    *  Assumes that the data is sorted so that duplicates are adjacent 
    */
  private void removeDuplicates() {
    int i = 0;
    int j = 1;                                    // j is always > i
    while (j < count) {
      if (data[i].equals(data[j]))                // duplicate at j
        j++;                 // so don't copy item at j, advance j, but leave i 
      else                                        // not a duplicate, 
        data[++i] = data[j++];
            // so shift item at j down and advance both i andj
    }
    count = i + 1;
  }


  private class SortedArraySetIterator < E > implements Iterator < E >  {
    private SortedArraySet < E > set;
    private int nextIndex = 0;
    private boolean canRemove = false;

    private SortedArraySetIterator(SortedArraySet < E > s) {
      set = s;
    }

    /** Return true if iterator has at least one more element */
    public boolean hasNext() {
      return (nextIndex < set.count);
    }

    /** return next element in the set */
    public E next() {
      if (nextIndex >= set.count)
        throw new NoSuchElementException();
      canRemove = true;
      return set.data[nextIndex++];
    }

    /** Remove from the set the last element returned by the iterator.
      *  Can only be called once per call to next.
      */
    public void remove() {
      if (!canRemove)
        throw new IllegalStateException();
      canRemove = false;
      
      nextIndex--;
      set.count--;

      for (int i = nextIndex + 1; i < set.count; i++)
        data[i - 1] = data[i];
      data[count] = null;
      canRemove = false;
    }
  }





  public static void main(String[] args) {
    test();
  }

  // two comparators for the test method.

  private static class StringComparator implements Comparator < String >  {
    public int compare(String str1, String str2) {
      return (str1).compareTo(str2);
    }
  }

  private static class ReverseStringComparator implements Comparator < String >
      {
    public int compare(String str1, String str2) {
      return ( - str1.compareTo(str2));
    }
  }

  public static void test() {
    SortedArraySet < String > set = new SortedArraySet < String >
        (new StringComparator());
    System.out.format("\nCreating new, empty set:\n");
    System.out.format(" Size: %d, isEmpty: %b, Set: %s\n", set.size(),
                      set.isEmpty(), set);

    System.out.format("\nChecking add:\n");
    String[] array1 =  {
      "A", "P", "F", "R", "E", "W", "Q", "T", "Z", "X", "C", "V", "B", "G",
          "I", "H", "M", "S", "K", "U", "N"
        }
    ;
    for (String s: array1){
      System.out.println("Set size: " +set.size());  
      set.add(s);
    }
    System.out.format(" Size: %d, isEmpty: %b, Set: %s\n", set.size(),
                      set.isEmpty(), set);

    System.out.format("\nChecking contains:\n");
    for (String st: array1)
      System.out.print(set.contains(st)? " OK": " FAIL");

    System.out.format("\n Contains(D)=%s\n", set.contains("D"));

    System.out.format("\nAdding A, Z, and P again\n");

    set.add("A");
    set.add("Z");
    set.add("P");
    System.out.format(" Size: %d, isEmpty: %b, Set: %s\n", set.size(),
                      set.isEmpty(), set);

    System.out.format("\nRemoving A, Z, and P\n");
    set.remove("A");
    System.out.println(" now contains(A)=" + set.contains("A"));
    set.remove("Z");
    System.out.println(" now contains(Z)=" + set.contains("Z"));
    set.remove("P");
    System.out.println(" now contains(P)=" + set.contains("P"));
    System.out.format(" Size: %d, isEmpty: %b, Set: %s\n", set.size(),
                      set.isEmpty(), set);


    System.out.format("\nChecking alternative constructors\n");
    List < String > list = new ArrayList < String > ();
    String[] array2 =  {
      "a", "p", "f", "r", "e", "w", "q", "q", "t", "z", "x", "c", "v", "b",
          "a", "z"
        }
    ;
    for (String s: array2)
      list.add(s);

    SortedArraySet < String > set2 = new SortedArraySet < String >
        (list, new StringComparator());
    System.out.format(" Set(list): %s\n", set2);
    for (String s: list)
      if (!set2.contains(s))
        System.out.format(" Fail contains: %s\n", s);

    //check with a reversed String comparator.

    SortedArraySet < String > set3 = new SortedArraySet < String >
        (new ReverseStringComparator());
    for (String s: list)
      set3.add(s);
    System.out.format(" Set(reverse): %s\n", set3);
    for (String s: list)
      if (!set3.contains(s))
        System.out.format(" Fail contains: %s\n", s);

    SortedArraySet < String > set4 = new SortedArraySet < String >
        (list, new ReverseStringComparator());
    System.out.format(" Set(list,reverse): %s\n", set4);
    for (String s: list)
      if (!set4.contains(s))
        System.out.format(" Fail contains: %s\n", s);

  }

}