import java.util.*;
/** 
 * String Bag Collection Class
 * Collection of Strings is sorted only when needed for binary search
 * CSE 142 lecture, 2/03.  HP
 * Modified by TV for CSE 142 Homework 5
 */
public class SortedStringBag {
  // instance variables
  private String[] strings;           // Strings in this StringList are stored in
  private int      numStrings;        //   strings[0..numStrings-1]
  private boolean  stringsAreSorted;  // If true, the strings are sorted in ascending order
  
  
  /** Construct a new empty StringList with the given capacity */
  public SortedStringBag(int capacity) {
    strings = new String[capacity];
    numStrings = 0;
    stringsAreSorted = true;
  }
  
  
  /**
   *  Add str to this StringList if room available and return true; 
   *  otherwise return false
   */
  public boolean add(String str) {
    if (numStrings >= strings.length) {
      return false;
    } else {
      // Room for str.  Add it at the end and set list to unsorted
      strings[numStrings] = str;
      numStrings++;
      stringsAreSorted = false;
      return true;
    }
  }
  
  
  /** Return the current size of this StringList */
  public int size() {
    return numStrings;
  }
  
  
  /** Remove all strings from this StringList */
  public void clear() {
    // null out string references so the space can be recycled if not otherwise in use
    for (int k = 0; k < numStrings; k++) {
      strings[k] = null;
    }
    // record that the list is now empty
    numStrings = 0;
  }
  
  
  /** Return the string at position pos, or null if pos is out of bounds */
  public String get(int pos) {
    if (pos < 0 || pos >= numStrings) {
      return null;
    } else {
      return strings[pos];
    }
  }
  
  
  /** Return whether this StringList contains str */
  public boolean contains(String str) {
    // ensure sorted for binary search
    if (!stringsAreSorted) {
      sortStrings();
    }
    
    // binary search
    // invariant: strings[0..L] <= str, strings[R..numStrings-1] > str, and
    //            strings[L+1..R-1] have not been examined yet
    int L = -1;
    int R = numStrings;
    while (L+1 != R) {
      int mid = (L + R) / 2;
      if (strings[mid].compareTo(str) <= 0) {
        L = mid;
      } else {
        R = mid;
      }
    }
    
    // Found if L >= 0 and strings[L] matches str
    return (L >= 0 && strings[L].equals(str));
  }
  
  
  // Sort the list of strings
  private void sortStrings() {
    System.out.println("Sorting!");
    // selection sort
    for (int k = 0; k < numStrings-1; k++) {
      int pos = smallestStringIn(k,numStrings-1);
      // swap strings[pos] ans strings[k]
      String temp = strings[k];
      strings[k] = strings[pos];
      strings[pos] = temp;
    }
    stringsAreSorted = true;
  }
  
  // Return location of smallest string in strings[start]..strings[end]
  // precondition: start <= end (i.e., at least one string in the interval)
  private int smallestStringIn(int start, int end) {
    int locationOfSmallest = start;
    for (int k = start+1; k <= end; k++) {
      if (strings[k].compareTo(strings[locationOfSmallest]) < 0) {
        locationOfSmallest = k;
      }
    }
    return locationOfSmallest;
  }
  
  /** Returns a randomly generated string with length between
   * 1 and 10 */
  public String generateRandomString() {
    Random rgenerator = new Random();
    int randomNum;
    String randomString = "";
    // length of string is between 1 and 10
    int lengthOfString = rgenerator.nextInt(10) + 1;
    for(int k = 0; k < lengthOfString; k++) {
      randomNum = (rgenerator.nextInt(52)); //52 characters (lower-case
                                            // and upper-case)
      if(randomNum < 26) {   // create upper-case letter
        randomString = randomString + (char)(randomNum + (int)'A');
      } else {        // create lower-case letter
        randomString = randomString + (char)(randomNum - 26 + (int)'a');
      } 
    }
    return randomString;
  }
    
  /** Generates a random set of strings and stores them in strings[0] to 
   * strings[num-1]. Note: previously stored strings in positions 0 to num-1 
   * will be cleared */
  public boolean setRandomSequence(int num) {             
    if (num <= strings.length) {
      
      Random rgenerator = new Random();
      int lengthOfString = 0;
      int randomNum;
      String randomString;
      
      for (int k = 0; k < num; k++ ){
        randomString = "";
        lengthOfString = rgenerator.nextInt(10) + 1;  
        
        //each string will be at least
        // one character and at most 10 characters

        for (int j = 0; j < lengthOfString; j++) {
          randomNum = (rgenerator.nextInt(52)); //52 characters (lower-case
                                                // and upper-case)
          if(randomNum < 26) {   // create upper-case letter
            randomString = randomString + (char)(randomNum + (int)'A');
          } else {        // create lower-case letter
            randomString = randomString + (char)(randomNum - 26 + (int)'a');
          } 
        }
        add(randomString);
      }
      return true;
    }
    else { return false; }
  }
  
  /** Return a string representation of this StringList */
  public String toString() {
    String result = "[";
    if (numStrings > 0) {
      result = result + strings[0];
      for (int k = 1; k < numStrings; k++) {
        result = result + ", " + strings[k];
      }
    }
    result = result + "]";
    return result;
  }
}