package algs31;
import stdlib.*;
import algs32.BST;
import algs33.RedBlackBST;
import algs34.LinearProbingHashST;
import algs34.SeparateChainingHashST;
import algs35.ST;
/* ***********************************************************************
 *  Compilation:  javac FrequencyCounter.java
 *  Execution:    java FrequencyCounter L < input.txt
 *  Dependencies: ST.java StdIn.java StdOut.java
 *  Data files:   http://algs4.cs.princeton.edu/41elementary/tnyTale.txt
 *                http://algs4.cs.princeton.edu/41elementary/tale.txt
 *                http://algs4.cs.princeton.edu/41elementary/tale.txt
 *                http://algs4.cs.princeton.edu/41elementary/leipzig100K.txt
 *                http://algs4.cs.princeton.edu/41elementary/leipzig300K.txt
 *                http://algs4.cs.princeton.edu/41elementary/leipzig1M.txt
 *
 *  Read in a list of words from standard input and print out
 *  the most frequently occurring word.
 *
 *  % java FrequencyCounter 1 < tinyTale.txt
 *  it 10
 *
 *  % java FrequencyCounter 8 < tale.txt
 *  business 122
 *
 *  % java FrequencyCounter 10 < leipzig1M.txt
 *  government 24763
 *
 *
 *************************************************************************/
/*
-------------------------------------------------
Results Leipzig, 15
-------------------------------------------------
Java TreeMap (ST)
  put time: 17.078
  get time: 0.023
  most frequent word = over-the-counter (1067 times)
  distinct = 22172
  words    = 64647
LinearProbingHashST
  put time: 17.11
  get time: 0.024
SeparateChainingHashST
  put time: 19.439
  get time: 0.03
BST
  put time: 24.604
  get time: 0.045
RedBlackBST
  put time: 25.651
  get time: 0.045
Ordered Array (BinarySearchST)
  put time: 25.862
  get time: 0.035
Unordered Array (ArrayST)
  put time: 54.04
  get time: 7.073
Unordered Linked List (SequentialSearchST)
  put time: 71.719
  get time: 11.849

-------------------------------------------------
Results Leipzig, 10
-------------------------------------------------
Java TreeMap (ST)
  put time: 30.91
  get time: 0.154
  most frequent word = government (24763 times)
  distinct =  165555
  words    = 1610829
LinearProbingHashST
  put time: 25.752
  get time: 0.075
SeparateChainingHashST
  put time: 27.603
  get time: 0.123
BST
  put time: 31.053
  get time: 0.248
RedBlackBST
  put time: 32.014
  get time: 0.237
Ordered Array (BinarySearchST)
  put time: 153.086
  get time: 0.252
Unordered Array (ArrayST)
  ...
 */
public class FrequencyCounter {

  public static void main(String[] args) {
    //int minlen = 2; String file = "data/tinyTale.txt";
    int minlen = 6; String file = "data/tale.txt";
    //int minlen = 12; String file = "data/leipzig1M.txt";
    StdOut.println ("Java TreeMap (ST)"); testST(minlen, file);
    //StdOut.println ("LinearProbingHashST"); testLinearProbingHashST(minlen, file);
    //StdOut.println ("SeparateChainingHashST"); testSeparateChainingHashST(minlen, file);
    //StdOut.println ("BST"); testBST(minlen, file);
    //StdOut.println ("RedBlackBST"); testRedBlackBST(minlen, file);
    //StdOut.println ("Ordered Array (BinarySearchST)"); testBinarySearchST(minlen, file);
    //StdOut.println ("Unordered Array (ArrayST)"); testArrayST(minlen, file);
    //StdOut.println ("Unordered Linked List (SequentialSearchST)"); testSequentialSearchST(minlen, file);
  }

  private static void testLinearProbingHashST (int minlen, String file) {
    LinearProbingHashST<String, Integer> st = new LinearProbingHashST<>();

    In in = new In (file);
    Stopwatch sw = new Stopwatch();
    while (!in.isEmpty()) {
      String key = in.readString();
      if (key.length() < minlen) continue;
      if (st.contains(key)) { st.put(key, st.get(key) + 1); }
      else                  { st.put(key, 1); }
    }
    StdOut.println("  put time: " + sw.elapsedTime ());

    sw = new Stopwatch();
    String max = "";
    st.put(max, 0);
    for (String word : st.keys()) {
      if (st.get(word) > st.get(max))
        max = word;
    }
    StdOut.println("  get time: " + sw.elapsedTime ());
    StdOut.println("  most frequent word = " + max + " (" + st.get(max) + " times)");
  }
  private static void testSeparateChainingHashST (int minlen, String file) {
    SeparateChainingHashST<String, Integer> st = new SeparateChainingHashST<>();

    In in = new In (file);
    Stopwatch sw = new Stopwatch();
    while (!in.isEmpty()) {
      String key = in.readString();
      if (key.length() < minlen) continue;
      if (st.contains(key)) { st.put(key, st.get(key) + 1); }
      else                  { st.put(key, 1); }
    }
    StdOut.println("  put time: " + sw.elapsedTime ());

    sw = new Stopwatch();
    String max = "";
    st.put(max, 0);
    for (String word : st.keys()) {
      if (st.get(word) > st.get(max))
        max = word;
    }
    StdOut.println("  get time: " + sw.elapsedTime ());
    StdOut.println("  most frequent word = " + max + " (" + st.get(max) + " times)");
  }
  private static void testArrayST (int minlen, String file) {
    ArrayST<String, Integer> st = new ArrayST<>();

    In in = new In (file);
    Stopwatch sw = new Stopwatch();
    while (!in.isEmpty()) {
      String key = in.readString();
      if (key.length() < minlen) continue;
      if (st.contains(key)) { st.put(key, st.get(key) + 1); }
      else                  { st.put(key, 1); }
    }
    StdOut.println("  put time: " + sw.elapsedTime ());

    sw = new Stopwatch();
    String max = "";
    st.put(max, 0);
    for (String word : st.keys()) {
      if (st.get(word) > st.get(max))
        max = word;
    }
    StdOut.println("  get time: " + sw.elapsedTime ());
    StdOut.println("  most frequent word = " + max + " (" + st.get(max) + " times)");
  }
  private static void testRedBlackBST (int minlen, String file) {
    RedBlackBST<String, Integer> st = new RedBlackBST<>();

    In in = new In (file);
    Stopwatch sw = new Stopwatch();
    while (!in.isEmpty()) {
      String key = in.readString();
      if (key.length() < minlen) continue;
      if (st.contains(key)) { st.put(key, st.get(key) + 1); }
      else                  { st.put(key, 1); }
    }
    StdOut.println("  put time: " + sw.elapsedTime ());

    sw = new Stopwatch();
    String max = "";
    st.put(max, 0);
    for (String word : st.keys()) {
      if (st.get(word) > st.get(max))
        max = word;
    }
    StdOut.println("  get time: " + sw.elapsedTime ());
    StdOut.println("  most frequent word = " + max + " (" + st.get(max) + " times)");
  }
  private static void testSequentialSearchST (int minlen, String file) {
    SequentialSearchST<String, Integer> st = new SequentialSearchST<>();

    In in = new In (file);
    Stopwatch sw = new Stopwatch();
    while (!in.isEmpty()) {
      String key = in.readString();
      if (key.length() < minlen) continue;
      if (st.contains(key)) { st.put(key, st.get(key) + 1); }
      else                  { st.put(key, 1); }
    }
    StdOut.println("  put time: " + sw.elapsedTime ());

    sw = new Stopwatch();
    String max = "";
    st.put(max, 0);
    for (String word : st.keys()) {
      if (st.get(word) > st.get(max))
        max = word;
    }
    StdOut.println("  get time: " + sw.elapsedTime ());
    StdOut.println("  most frequent word = " + max + " (" + st.get(max) + " times)");
  }
  private static void testBST (int minlen, String file) {
    BST<String, Integer> st = new BST<>();

    In in = new In (file);
    Stopwatch sw = new Stopwatch();
    while (!in.isEmpty()) {
      String key = in.readString();
      if (key.length() < minlen) continue;
      if (st.contains(key)) { st.put(key, st.get(key) + 1); }
      else                  { st.put(key, 1); }
    }
    StdOut.println("  put time: " + sw.elapsedTime ());

    sw = new Stopwatch();
    String max = "";
    st.put(max, 0);
    for (String word : st.keys()) {
      if (st.get(word) > st.get(max))
        max = word;
    }
    StdOut.println("  get time: " + sw.elapsedTime ());
    StdOut.println("  most frequent word = " + max + " (" + st.get(max) + " times)");
  }
  private static void testBinarySearchST (int minlen, String file) {
    BinarySearchST<String, Integer> st = new BinarySearchST<>();

    In in = new In (file);
    Stopwatch sw = new Stopwatch();
    while (!in.isEmpty()) {
      String key = in.readString();
      if (key.length() < minlen) continue;
      if (st.contains(key)) { st.put(key, st.get(key) + 1); }
      else                  { st.put(key, 1); }
    }
    StdOut.println("  put time: " + sw.elapsedTime ());

    sw = new Stopwatch();
    String max = "";
    st.put(max, 0);
    for (String word : st.keys()) {
      if (st.get(word) > st.get(max))
        max = word;
    }
    StdOut.println("  get time: " + sw.elapsedTime ());
    StdOut.println("  most frequent word = " + max + " (" + st.get(max) + " times)");
  }
  private static void testST (int minlen, String file) {
    int words = 0;
    In in = new In (file);
    ST<String, Integer> st = new ST<>();

    // compute frequency counts
    Stopwatch sw = new Stopwatch();
    while (!in.isEmpty()) {
      String key = in.readString();
      if (key.length() < minlen) continue;
      words++;
      if (st.contains(key)) { st.put(key, st.get(key) + 1); }
      else                  { st.put(key, 1); }
    }
    StdOut.println("  put time: " + sw.elapsedTime ());

    // find a key with the highest frequency count
    sw = new Stopwatch();
    String max = "";
    st.put(max, 0);
    for (String word : st.keys()) {
      if (st.get(word) > st.get(max))
        max = word;
    }
    StdOut.println("  get time: " + sw.elapsedTime ());

    StdOut.println("  most frequent word = " + max + " (" + st.get(max) + " times)");
    StdOut.println("  distinct = " + (st.size ()-1));
    StdOut.println("  words  = " + words);
  }


}