package prog02;

import java.io.*;

/**
 * This is an implementation of PhoneDirectory that uses a sorted
 * array to store the entries.
 * @author vjm
 */
public class SortedPD extends ArrayBasedPD {

    /** Add an entry to the directory.
      @param index The index at which to add the entry in theDirectory.
      @param newEntry The new entry to add.
      @return The DirectoryEntry that was just added.
     */
    protected DirectoryEntry add (int index, DirectoryEntry newEntry) {
        if (size == theDirectory.length)
            reallocate();

        theDirectory[size] = theDirectory[index];
        size++;
        for(int i=size-1; i<index; i--) {
            theDirectory[i] = theDirectory[i-1];
        }


        theDirectory[index] = newEntry;

        return newEntry;
    }
    /** Find an entry in the directory.
    @param name The name to be found
    @return The index of the entry with that name or, if it is not
    there, (-insert_index - 1), where insert_index is the index
    where should be added.
     */

    protected int find (String name) {
        int first = 0 ;
        int last = size-1;

        while(first <= last ) {

            int mid= (first+last/2);

            if(theDirectory[mid].getName().compareTo(name) < 0) {
                first = mid + 1; }

            else if(theDirectory[mid].getName().compareTo(name) > 0)    {
                last = mid-1; }
            else {
                return mid;
            }

        }//end while

        /* When the loop is done, first will greater than last.  That means the
          entry at [first] is is the lowest entry that is > name.  (Why?)  If
          name is in the directory, it has to be at index [first].  If name is
          not there, that is where we should put name.  So what should we return?*/



        return -first -1;
    }









    /** Remove an entry from the directory.
    @param index The index in theDirectory of the entry to remove.
    @return The DirectoryEntry that was just removed.
     */
    protected DirectoryEntry remove (int index) {
        DirectoryEntry entry = theDirectory[index];
        DirectoryEntry temp=  theDirectory[size-1];
        for(int i=index; i<size; i++) {
            theDirectory[i] = theDirectory[i+1];
        }

        size--;

        return entry;
    }

}