/**
 * Dictionary implementation using a sorted array.
 *
 * Limitations:  the constructor takes an argument that specifies
 *               the maximum number of entries that can be stored in the 
 *               dictionary.  Inserting additional entries into the dictionary
 *               results in a runtime exception.
 *
 * David Liben-Nowell (CS127, Carleton College)
 * Winter 2006
 *
 */
public class DictionarySortedArray implements Dictionary {

    private DictionaryEntry[] dict; // dict[i] will store the ith entry
                                    // sorted alphabetically by word.

    private int dictSize;           // current number of stored word/def pairs 

    private int maxDictSize;        // maximum number of pairs that
				    // can be stored.

    /**
     * Constructor -- the maxSize parameter sets the maximum number of
     * entries that can be stored in the dictionary.
     */
    public DictionarySortedArray(int maxDictSize) {
	this.maxDictSize = maxDictSize;
	dictSize = 0;
	dict = new DictionaryEntry[maxDictSize];
    }
    

    /**
     * Insert a word and its definition into the dictionary.
     */
    public void insert(String word, String definition) {
	
	/* If there's no room left in dict[], we die. */
	if (dictSize >= maxDictSize) {
	    throw new RuntimeException("Cannot insert into full dictionary");
	}

	/* Walk from the right end of the dict[] array until we find
	 * the slot where the new entry should go.  As we pass each
	 * entry, we move it one slot to the right. */
	int i = dictSize;  

	// loop invariant:  dict[i] is empty; every dict[j].getWord() with 
	//                  dictSize > j > i  is later alphabetically than word
	while (i > 0 && (dict[i-1].getWord().compareTo(word) > 0)) {
	    dict[i] = dict[i-1];
	    i--;
	}

	/* Place the new entry in the newly vacated ith slot. */
	dict[i] = new DictionaryEntry(word,definition);
	dictSize++;
    }


    /**
     * Finds the index i such that dict[i] contains the word using
     * binary search.  Returns -1 if the word isn't in dict[].  
     */
    private int findWordIndex(String word) {
	int l=0;
	int r=dictSize-1;
	int m;

	// loop invariant:  for all 0 <= j < l, dict[j] <= word and
	//                  for all dictSize-1 >= j > r, dict[j] >= word.
	while (l <= r) {
	    m = (l + r)/2;
	    int comparison = dict[m].getWord().compareTo(word);

	    if (comparison == 0) {
		return m;
	    } else if (comparison > 0) {
		r = m-1;
	    } else {
		l = m+1;
	    }
	}
	return -1;
    }


    /**
     * Return a definition for a word that is in the dictionary.
     * Throws an exception if the word is not in fact in the dictionary.
     */
    public String define(String word) throws NotInDictionaryException {
	int i = findWordIndex(word);
	if (i == -1) {
	    throw new NotInDictionaryException(word + "is not in dictionary");
	}
	return dict[i].getDefinition();
    }

}