/**
 * Lab6 Solution.
 * 
 * @author M.Imtiaz ur rahaman.
 * @version 15-Sep-02.
 */
public class StringArray
{

    private String[] wordlist = null;

    // The following variables are used to restrict the search in the array.
    private int head;
    private int tail;
    private int mid;

    /**
     * Constructors for objects of class StringArray
     */
    
    // Create an empty wordlist.
    public StringArray()
    {
        wordlist = null;
        head = tail = mid = 0;
    }

    // Initialize the wordlist with the given array.
    public StringArray(String[] ss)
    {
        wordlist = new String[ss.length];
        for(int i = 0; i < ss.length; i++)
        {
            wordlist[i] = ss[i];
        }
        head = 0;
        tail = wordlist.length-1;
        mid = (head + tail)/2;
    }

    // Print the entire wordlist.
    public void showWordList()
    {
        if(wordlist == null)
        {
            System.out.println("<null>");
            return;
        }
    
        for(int i=0; i<wordlist.length; i++)
        {
            System.out.println("wordlist[" + i + "] = " + wordlist[i]);
        }
    }

    /*
    *   Add an additional word to the list.
    *   Note that the word being added should still keep the wordlist in
    *   sorted order.
    */    
    public void add(String s)
    {
        if(wordlist == null)
        {
            wordlist = new String[1];
            wordlist[0] = s;
        }    
        else
        {
            String[] temp = new String[wordlist.length + 1];
            int i;
    
            for(i=0; i<wordlist.length; i++)
            {
                temp[i] = wordlist[i];
            }
            temp[i] = s;
            wordlist = temp;
        }
    
        head = 0;
        tail = wordlist.length-1;
        mid = (head + tail)/2;

    }
    
    /*
    *   Append the given array to the end of existing wordlist.
    *   Note that after the array is appended, the wordlist should
    *   still be sorted.
    */
    public void addAll(String[] ss)
    {
        if(wordlist == null)
        {
            wordlist = new String[ss.length];
            for(int i=0; i<ss.length; i++)
            {
                wordlist[i] = ss[i];
            }
        }    
        else
        {
            String[] temp = new String[wordlist.length + ss.length];

            for(int i=0; i<wordlist.length; i++)
            {
                temp[i] = wordlist[i];
            }

            for(int i=0; i<ss.length; i++)
            {
                temp[wordlist.length+i] = ss[i];
            }

            wordlist = temp;
        }

        head = 0;
        tail = wordlist.length-1;
        mid = (head + tail)/2;
    }
    
    /*
    *   Search for the string "str" in the wordlist.
    *   This is a case sensitive search.
    */
    public int binarySearch(String str)
    {
        if(wordlist == null)
            return -1;
      
        if(head > tail)
        {
            head = 0;
            tail = wordlist.length-1;
            mid = (head+tail)/2;
            return -1;
        }

        int value = str.compareTo(wordlist[mid]);
        
        if(value == 0)
        {
            int retvalue = mid;

            head = 0;
            tail = wordlist.length-1;
            mid = (head+tail)/2;

            return retvalue;   
        }
        else
        {
            if(value < 0)
            {
                tail = mid-1;
                mid = (head+tail)/2;
                return binarySearch(str);
            }
            else
            {
                head = mid+1;
                mid = (head+tail)/2;
                return binarySearch(str);
            }
        }
    }

    /* 
    * Search for the string "str" in the wordlist.
    * If caseIgnore == false then it becomes a case sensitive search
    * and just calls the above binarysearch(str) else do a case
    * insensitive search.
    */

    public int binarySearch(String str, boolean caseIgnore)
    {
        if(caseIgnore == false)
            return binarySearch(str);
        
        if(wordlist == null)
            return -1;
      
        if(head > tail)
        {
            head = 0;
            tail = wordlist.length-1;
            mid = (head+tail)/2;
            return -1;
        }

        int value = str.compareToIgnoreCase(wordlist[mid]);
        
        if(value == 0)
        {
            int retvalue = mid;

            head = 0;
            tail = wordlist.length-1;
            mid = (head+tail)/2;

            return retvalue;   
        }
        else
        {
            if(value < 0)
            {
                tail = mid-1;
                mid = (head+tail)/2;
                return binarySearch(str,true);
            }
            else
            {
                head = mid+1;
                mid = (head+tail)/2;
                return binarySearch(str,true);
            }
        }
    }
    
}