package algs33;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac TestRedBlackBST.java
 *  Execution:    java -ea XTestRedBlackBST 10
 *  Dependencies: RedBlackBST.java
 *
 *  Test client for RedBlackBST.java.
 *
 *************************************************************************/

public class XTestRedBlackBST {

  public static void main(String[] args) {
    args = new String[] { "1000" };

    String test = "S E A R C H E X A M P L E";
    String[] keys = test.split(" ");
    RedBlackBST<String, Integer> st = new RedBlackBST<>();
    for (int i = 0; i < keys.length; i++)
      st.put(keys[i], i);

    StdOut.println("size = " + st.size());
    StdOut.println("min  = " + st.min());
    StdOut.println("max  = " + st.max());
    StdOut.println();


    // print keys in order using allKeys()
    StdOut.println("Testing keys()");
    StdOut.println("--------------------------------");
    for (String s : st.keys())
      StdOut.println(s + " " + st.get(s));
    StdOut.println();

    // print keys in order using select
    StdOut.println("Testing select");
    StdOut.println("--------------------------------");
    for (int i = 0; i <= st.size(); i++)
      StdOut.println(i + " " + st.select(i));
    StdOut.println();

    // test rank, floor, ceiling
    StdOut.println("key rank floor ceil");
    StdOut.println("-------------------");
    for (char i = 'A'; i <= 'Z'; i++) {
      String s = i + "";
      StdOut.format("%2s %4d %4s %4s\n", s, st.rank(s), st.floor(s), st.ceiling(s));
    }
    StdOut.println();

    // test range search and range count
    String[] from = { "A", "Z", "X", "0", "B", "C" };
    String[] to   = { "Z", "A", "X", "Z", "G", "L" };
    StdOut.println("range search");
    StdOut.println("-------------------");
    for (int i = 0; i < from.length; i++) {
      StdOut.format("%s-%s (%2d) : ", from[i], to[i], st.size(from[i], to[i]));
      for (String s : st.keys(from[i], to[i]))
        StdOut.print(s + " ");
      StdOut.println();
    }
    StdOut.println();

    // delete the smallest keys
    for (int i = 0; i < st.size() / 2; i++) {
      st.deleteMin();
    }
    StdOut.println("After deleting the smallest " + st.size() / 2 + " keys");
    StdOut.println("--------------------------------");
    for (String s : st.keys())
      StdOut.println(s + " " + st.get(s));
    StdOut.println();

    // delete all the remaining keys
    while (!st.isEmpty()) {
      st.delete(st.select(st.size() / 2));
    }
    StdOut.println("After deleting the remaining keys");
    StdOut.println("--------------------------------");
    for (String s : st.keys())
      StdOut.println(s + " " + st.get(s));
    StdOut.println();

    StdOut.println("After adding back N keys");
    StdOut.println("--------------------------------");
    for (int i = 0; i < keys.length; i++)
      st.put(keys[i], i);
    for (String s : st.keys())
      StdOut.println(s + " " + st.get(s));
    StdOut.println();

    StdOut.println();




    // insert N elements in order if one command-line argument supplied
    if (args.length == 0) return;
    int N = Integer.parseInt(args[0]);
    RedBlackBST<Integer, Integer> st2 = new RedBlackBST<>();
    for (int i = 0; i < N; i++) {
      st2.put(i, i);
      int h = st2.height();
      //StdOut.println("i = " + i + ", height = " + h + ", size = " + st2.size());
    }

    // delete keys in random order
    StdOut.println("Deleting keys in random order");
    while (st2.size() > 0) {
      int i = StdRandom.uniform(N);
      if (st2.contains(i)) {
        st2.delete(i);
        int h = st2.height();
        //StdOut.println("i = " + i + ", height = " + h + ", size = " + st2.size());
      }
    }

    StdOut.println("size = " + st2.size());
  }
}