/**
 * StringList - Example of implementing a collection with an array
 * Version 2 - strings are stored in ascending order.
 * 
 * @author Hal Perkins 
 * @version CSE142 Su01, August 15, 2001
 */
public class StringList {

    // constant - default capacity of a new StringList if none specified
    private static final int DEFAULT_CAPACITY = 50;

    // instance variables
    private String[] strings;       // Items in this StringList are stored
    private int      size;          //   in strings[0..size-1].  Strings are
                                    //   sorted in ascending order, i.e.,
                                    //   strings[0] <= strings[1] <= ...
   
    /** Construct new StringList with the default capacity */
    public StringList() {
        this.init(DEFAULT_CAPACITY);
    }

    /** Construct new StringList with the specificed capacity */
    public StringList(int capacity) {
        this.init(capacity);
    }

    // Initialize this StringList with the specificed capacity
    private void init(int capacity) {
        this.strings = new String[capacity];
        this.size = 0;
    }

    /** = "this StringList is empty" */
    public boolean isEmpty() {
        return this.size == 0;
    }

    /** = "this StringList is full" */
    public boolean isFull() {
        return this.strings.length == this.size;
    }

    /** = number of elements in this StringList */
    public int size() {
        return this.size;
    }

    /** 
     * Add new String to this StringList if there is room.
     * @param str String to be added
     * @return True if str was added successfully, otherwise false
     */
    public boolean add(String str) {
        if (this.isFull()) {
            return false;
        } else {
            // shift all strings > str one position to the right
            int pos = size;
            while (pos > 0 && strings[pos-1].compareTo(str) > 0) {
                strings[pos] = strings[pos-1];
                pos--;
            }

            // pos is position where new string should be inserted
            // insert new string there and increase size
            strings[pos] = str;
            size++;
            return true;
        }
    }

    /** Return position of str in this StringList if present,
      * otherwise return -1 */
    public int contains(String str) {
        // Binary search
        // strings[0]..strings[L] are <= str
        // strings[R]..strings[size-1] are > str
        // strings[L+1]..strings[R-1] have not been examined yet
        int L = -1;
        int R = size;
        while (L+1 != R) {
            int mid = (L+R) / 2;
            if (strings[mid].compareTo(str) <= 0) {
                L = mid;
            } else {
                R = mid;
            }
        }

        if (L >= 0 && strings[L].equals(str)) {
            return L;
        } else {
            return -1;
        }
    }

    // = "pos is in bounds (0<=pos<size)"
    private boolean inBounds(int pos) {
        return (pos >= 0 && pos < this.size);
    }

    /** 
     * Return the string stored at at position pos in this StringList.
     * @return String at position pos, provided 0<=pos<size(), 
     *         otherwise return null.
     */
    public String get(int pos) {
        if (inBounds(pos)) {
            return strings[pos];
        } else {
            return null;
        }
    }

    /** 
     * Remove the string stored at position pos in this StringList.
     * @return String that was at position pos, provided 0<=pos<size(),
     *         otherwise return null.
     */
    public String remove(int pos) {
        if (!inBounds(pos)) {
            return null;
        } else {
            String result = strings[pos];

            // shift array elements from strings[pos+1] to
            // strings[size-1] left one position
            for (int k = pos; k < size-1; k++) {
                strings[k] = strings[k+1];
            }

            size--;
            return result;
        }
    } 
    

    

}