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

/**
 * The ArrayDictionary class implements the Dictionary interface by means of
 * an array.
 *
 * @version     1.6    June 10, 2002
 * @author      Franck van Breugel
 * @see Dictionary
 */
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;
    }

    /** 
     * Returns the size of this dictionary.
     *
     * @return The size of this dictionary.
     */
    public int size() 
    {
        return size;
    }

    /** 
     * Tests if this dictionary is empty. 
     *
     * @return true if this dictionary is empty, false otherwise.
     */
    public boolean isEmpty() 
    {
        return (size == 0);
    }

    /**
     * Returns the collection of elements of this dictionary.
     *
     * @return The collection of elements of this dictionary.
     */
    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();
    }

    /**
     * Returns the collection of elements of this dictionary.
     *
     * @return The collection of elements of this dictionary.
     */
    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;
    }

    /**
     * Returns the element of an item in this dictionary with the
     * specified key; returns NO_SUCH_KEY if this dictionary does not
     * contain an item with the specified key.
     *
     * @param key The key to be searched for.
     * @return The element of an item in this dictionary with the
     * specified key; returns NO_SUCH_KEY if this dictionary does not
     * contain an item with the specified key.
     */
    public Object findElement(Object key) 
    {
        int i = binarySearch(key, 0, size - 1);
        if (i == -1) 
        {
            return NO_SUCH_KEY;
        } 
        else 
        {
            return dictionary[i].element();
        }
    }

    /**
     * Returns the collection of elements of item in this dictionary with the
     * specified key.
     *
     * @param key The key to be searched for.
     * @return The collection of elements of item in this dictionary with the
     * specified key.
     */
    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();
        }
    }

    /**
     * Add item with the specified key and element to this dictionary.
     *
     * @param key The key of the item to be inserted.
     * @param element The element of the item to be inserted.
     */
    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++;
    }

    /**
     * Removes an item from this dictionary with the specified key and
     * returns its element; returns NO_SUCH_KEY if this dictionary does not
     * contain an item with the specified key.
     *
     * @param key The key to be searched for.
     * @return The element of the removed item if there exists an item
     * with the specified key; NO_SUCH_KEY otherwise.
     */
    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;
        }
    }

    /**
     * Removes all items from this dictionary with the specified key and
     * returns the collection of corresponding elements.
     *
     * @param key The key to be searched for.
     * @return The collection of elements with the specified key in this
     * directory.
     */
    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;
    }
}