import java.util.Iterator;
import java.util.Vector;

/**
   The ArrayDictionary class implements the Dictionary interface by means of
   an array.
  
   @author      Franck van Breugel
   @version     1.6    June 10, 2002
*/
public class ArrayDictionary implements Dictionary 
{
    public static final int CAPACITY = 1000; // default maximal capacity of this dictionary
    
    private Item[] dictionary;               // array containing items of this dictionary ordered by key
    private int size = 0;                    // size of this dictionary
    private int capacity;                    // maximal capacity of this dictionary
    private Comparator comparator;           // contains methods isEqualTo and isLessThanOrEqualTo to compare keys

    /** 
       Constructs a dictionary of default capacity with specified comparator.
       
       @param comparator Comparator containing method isEqualTo and isLessThan
       to compare keys.
    */
    public ArrayDictionary(Comparator comparator) 
    {
        this(CAPACITY, comparator);
    }

    /** 
       Constructs a dictionary of specified capacity with specified comparator.  
       If the specified capacity is negative, the default capacity is used 
       instead.
      
       @param capacity the capacity of the dictionary. 
       @param comparator Comparator containing method isEqualTo and isLessThan
       to compare keys.
    */
    public ArrayDictionary(int capacity, Comparator comparator) 
    {
        if (capacity < 0) 
        {
            capacity = CAPACITY;
        }
        this.dictionary = new Item[capacity];
        this.capacity = capacity;
        this.comparator = comparator;
    }

    public int size() 
    {
        return size;
    }

    public boolean isEmpty() 
    {
        return (size == 0);
    }

    public Iterator elements()
    {
        Vector collection = new Vector();
        for (int i = 0; i < size; i++)
	{
            /* vector contains the elements of dictionary[0], ..., dictionary[i-1] */
            collection.addElement(dictionary[i].element());
        }
        return collection.iterator();
    }

    public Iterator keys()
    {
        Vector collection = new Vector();
        for (int i = 0; i < size; i++)
	{
            /* vector contains the keys of dictionary[0], ..., dictionary[i-1] */
            collection.addElement(dictionary[i].key());
        }
        return collection.iterator();
    }

    /**
       Returns the index of an item in this dictionary with the specified
       key and its index greater than or equal to low and smaller than or
       equal to high, and returns -1 if no such item exists.
      
       @param key The key to be searched for.
       @param low The smallest index of the items to be searched.
       @param high The biggest index of the items to be searched.
       @return The index of an item in this dictionary with the specified
       key and its index greater than or equal to low and smaller than or
       equal to high, and returns -1 if no such item exists.
    */
    private int binarySearch(Object key, int low, int high) 
    {
        int result = -1;
        if (low <= high) 
        {
            int middle = (low + high) / 2;
            if (comparator.isEqualTo(key, dictionary[middle].key())) 
            {
                result = middle;
            } 
            else if (comparator.isLessThan(key, dictionary[middle].key())) 
            {
                result = binarySearch(key, low, middle - 1);
	    } 
            else 
            {
                result = binarySearch(key, middle + 1, high);
            }
        }
	return result;
    }

    public Object findElement(Object key) 
    {
        int i = binarySearch(key, 0, size - 1);
        if (i == -1) 
        {
            return NO_SUCH_KEY;
        } 
        else 
        {
            return dictionary[i].element();
        }
    }

    public Iterator findAllElements(Object key) 
    {
        Vector vector = new Vector();
        int index = binarySearch(key, 0, size - 1);
        if (index == -1) 
        {
            return vector.iterator();
        } 
        else 
        {
            int temp = index;
            while (temp >= 0 && comparator.isEqualTo(key, dictionary[temp].key())) 
            {
		/* for all i : temp < i <= index : key of dictionary[i] is equal to key */
                temp--;
            }
            int min = temp + 1;
            temp = index;
            while (temp < size && comparator.isEqualTo(key, dictionary[temp].key())) 
            {
		/* for all i : index <= i < temp : key of dictionary[i] is equal to key */
                temp++;
            }
            int max = temp - 1;
            for (int i = min; i <= max; i++) 
            {
		/* elements of dictionary[min], ..., dictionary[i - 1] have been added to vector. */
                vector.addElement(dictionary[i].element());
            }
            return vector.iterator();
        }
    }

    public void insertItem(Object key, Object element) 
    {
        if (size >= capacity) 
        {
            throw new DictionaryFullException("Dictionary is full.");
        }
        int i = size - 1;
        while (i >= 0 && comparator.isLessThan(key, dictionary[i].key())) 
        {
        /* the items with index greater than i have keys greater than key
           and these items have been moved one position to the right in the
           array */
            dictionary[i + 1] = dictionary[i];
            i--;
        }
        dictionary[i + 1] = new Item(key, element);
        size++;
    }

    public Object removeElement(Object key) 
    {
        int i = binarySearch(key, 0, size - 1);
        if (i == -1) 
        {
            return NO_SUCH_KEY;
        } 
        else 
        {
            Object temp = dictionary[i].element();
            for (int j = i + 1; j < size; j++) 
            {
            /* dictionary[i + 1], ..., dictionary[j - 1] have been moved one position to the left. */
                dictionary[j - 1] = dictionary[j];
            }
            size--;
            return temp;
        }
    }

    public Iterator removeAllElements(Object key) 
    {
        Vector vector = new Vector();
        int index = binarySearch(key, 0, size - 1);
        if (index == -1) 
        {
            return vector.iterator();
        } 
        else 
        {
            int temp = index;
            while (temp >= 0 && comparator.isEqualTo(key, dictionary[temp].key())) 
            {
            /* keys of dictionary[temp + 1], ... dictionary[index] are equal to key. */
                temp--;
            }
            int min = temp + 1;
            temp = index;
            while (temp < size && comparator.isEqualTo(key, dictionary[temp].key())) 
            {
            /* keys of dictionary[index], ... dictionary[temp - 1] are equal to key. */
                temp++;
            }
            int max = temp - 1;
            for (int i = min; i <= max; i++) 
            {
            /* elements of dictionary[min], ..., dictionary[i - 1] have been added to vector. */
                vector.addElement(dictionary[i].element());
            }
            int num = max - min + 1;
            for (int i = max + 1; i < size; i++) 
            {
            /* dictionary[max + 1], ..., dictionary[i - 1] have been moved num positions to the left.
             */
                dictionary[i - num] = dictionary[i];
            }
            size -= num;
            return vector.iterator();
        }
    }

    /**
       Returns a string representation of this dictionary.
      
       @return A string representation of this dictionary.
    */
    public String toString() 
    {
        String rep = "";
        for (int i = 0; i < size; i++) 
        {
        /* rep = dictionary[0].toString() + "\n" + ... + dictionary[i-1].toString() + "\n"
 */
            rep += dictionary[i].toString();
            rep += "\n";
        }
        return rep;
    }
}