// Exercise 3.1.16 3.1.17 3.1.30 (Solution published at http://algs4.cs.princeton.edu/)
package algs31;
import stdlib.*;
import algs13.Queue;
/* ***********************************************************************
 *  Compilation:  javac BinarySearchST.java
 *  Execution:    java BinarySearchST
 *  Dependencies: StdIn.java StdOut.java
 *  Data files:   http://algs4.cs.princeton.edu/31elementary/tinyST.txt
 *
 *  Symbol table implementation with binary search in an ordered array.
 *
 *  % more tinyST.txt
 *  S E A R C H E X A M P L E
 *
 *  % java BinarySearchST < tinyST.txt
 *  A 8
 *  C 4
 *  E 12
 *  H 5
 *  L 11
 *  M 9
 *  P 10
 *  R 3
 *  S 0
 *  X 7
 *
 *************************************************************************/

public class BinarySearchST<K extends Comparable<? super K>, V> {
  private static final int INIT_CAPACITY = 2;
  private K[] keys;
  private V[] vals;
  private int N = 0;

  // create an empty symbol table with default initial capacity
  public BinarySearchST() { this(INIT_CAPACITY); }

  // create an empty symbol table with given initial capacity
  @SuppressWarnings("unchecked")
  public BinarySearchST(int capacity) {
    keys = (K[]) new Comparable[capacity];
    vals = (V[]) new Object[capacity];
  }

  // resize the underlying arrays
  @SuppressWarnings("unchecked")
  private void resize(int capacity) {
    if (capacity <= N) throw new IllegalArgumentException ();
    K[] tempk = (K[]) new Comparable[capacity];
    V[] tempv = (V[]) new Object[capacity];
    for (int i = 0; i < N; i++) {
      tempk[i] = keys[i];
      tempv[i] = vals[i];
    }
    vals = tempv;
    keys = tempk;
  }


  // is the key in the table?
  public boolean contains(K key) { return get(key) != null; }

  // number of key-value pairs in the table
  public int size() { return N; }

  // is the symbol table empty?
  public boolean isEmpty() { return size() == 0; }

  // return the value associated with the given key, or null if no such key
  public V get(K key) {
    if (isEmpty()) return null;
    int i = rank(key);
    if (i < N && keys[i].compareTo(key) == 0) return vals[i];
    return null;
  }

  // return the number of keys in the table that are smaller than given key
  public int rank(K key) {
    int lo = 0, hi = N-1;
    while (lo <= hi) {
      int m = lo + (hi - lo) / 2;
      int cmp = key.compareTo(keys[m]);
      if      (cmp < 0) hi = m - 1;
      else if (cmp > 0) lo = m + 1;
      else return m;
    }
    return lo;
  }


  // Search for key. Update value if found; grow table if new.
  public void put(K key, V val)  {
    if (val == null) { delete(key); return; }

    int i = rank(key);

    // key is already in table
    if (i < N && keys[i].compareTo(key) == 0) {
      vals[i] = val;
      return;
    }

    // insert new key-value pair
    if (N == keys.length) resize(2*keys.length);

    for (int j = N; j > i; j--)  {
      keys[j] = keys[j-1];
      vals[j] = vals[j-1];
    }
    keys[i] = key;
    vals[i] = val;
    N++;

    //assert check();
  }


  // Remove the key-value pair if present
  public void delete(K key)  {
    if (isEmpty()) return;

    // compute rank
    int i = rank(key);

    // key not in table
    if (i == N || keys[i].compareTo(key) != 0) {
      return;
    }

    for (int j = i; j < N-1; j++)  {
      keys[j] = keys[j+1];
      vals[j] = vals[j+1];
    }

    N--;
    keys[N] = null;  // to avoid loitering
    vals[N] = null;

    // resize if 1/4 full
    if (N > 0 && N == keys.length/4) resize(keys.length/2);

    //assert check();
  }

  // delete the minimum key and its associated value
  public void deleteMin() {
    if (isEmpty()) throw new Error("Symbol table underflow error");
    delete(min());
  }

  // delete the maximum key and its associated value
  public void deleteMax() {
    if (isEmpty()) throw new Error("Symbol table underflow error");
    delete(max());
  }


  /* ***************************************************************************
   *  Ordered symbol table methods
   *****************************************************************************/
  public K min() {

    if (isEmpty()) return null;
    return keys[0];
  }

  public K max() {
    if (isEmpty()) return null;
    return keys[N-1];
  }

  public K select(int k) {
    if (k < 0 || k >= N) return null;
    return keys[k];
  }

  public K floor(K key) {
    int i = rank(key);
    if (i < N && key.compareTo(keys[i]) == 0) return keys[i];
    if (i == 0) return null;
    else return keys[i-1];
  }

  public K ceiling(K key) {
    int i = rank(key);
    if (i == N) return null;
    else return keys[i];
  }

  public int size(K lo, K hi) {
    if (lo.compareTo(hi) > 0) return 0;
    if (contains(hi)) return rank(hi) - rank(lo) + 1;
    else              return rank(hi) - rank(lo);
  }

  public Iterable<K> keys() {
    return keys(min(), max());
  }

  public Iterable<K> keys(K lo, K hi) {
    Queue<K> queue = new Queue<>();
    if (lo == null && hi == null) return queue;
    if (lo == null) throw new Error("lo is null in keys()");
    if (hi == null) throw new Error("hi is null in keys()");
    if (lo.compareTo(hi) > 0) return queue;
    for (int i = rank(lo); i < rank(hi); i++)
      queue.enqueue(keys[i]);
    if (contains(hi)) queue.enqueue(keys[rank(hi)]);
    return queue;
  }


  /* ***************************************************************************
   *  Check internal invariants
   *****************************************************************************/

  private boolean check() {
    return isSorted() && rankCheck();
  }

  // are the items in the array in ascending order?
  private boolean isSorted() {
    for (int i = 1; i < size(); i++)
      if (keys[i].compareTo(keys[i-1]) < 0) return false;
    return true;
  }

  // check that rank(select(i)) = i
  private boolean rankCheck() {
    for (int i = 0; i < size(); i++)
      if (i != rank(select(i))) return false;
    for (int i = 0; i < size(); i++)
      if (keys[i].compareTo(select(rank(keys[i]))) != 0) return false;
    return true;
  }


  /* ***************************************************************************
   *  Test client
   *****************************************************************************/
  public static void main(String[] args) {
    StdIn.fromFile("data/tiny.txt");

    BinarySearchST<String, Integer> st = new BinarySearchST<>();
    for (int i = 0; !StdIn.isEmpty(); i++) {
      String key = StdIn.readString();
      st.put(key, i);
    }
    for (String s : st.keys())
      StdOut.println(s + " " + st.get(s));
  }
}