001package algs33;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac TestRedBlackBST.java
005 *  Execution:    java -ea XTestRedBlackBST 10
006 *  Dependencies: RedBlackBST.java
007 *
008 *  Test client for RedBlackBST.java.
009 *
010 *************************************************************************/
011
012public class XTestRedBlackBST {
013
014        public static void main(String[] args) {
015                args = new String[] { "1000" };
016
017                String test = "S E A R C H E X A M P L E";
018                String[] keys = test.split(" ");
019                RedBlackBST<String, Integer> st = new RedBlackBST<>();
020                for (int i = 0; i < keys.length; i++)
021                        st.put(keys[i], i);
022
023                StdOut.println("size = " + st.size());
024                StdOut.println("min  = " + st.min());
025                StdOut.println("max  = " + st.max());
026                StdOut.println();
027
028
029                // print keys in order using allKeys()
030                StdOut.println("Testing keys()");
031                StdOut.println("--------------------------------");
032                for (String s : st.keys())
033                        StdOut.println(s + " " + st.get(s));
034                StdOut.println();
035
036                // print keys in order using select
037                StdOut.println("Testing select");
038                StdOut.println("--------------------------------");
039                for (int i = 0; i <= st.size(); i++)
040                        StdOut.println(i + " " + st.select(i));
041                StdOut.println();
042
043                // test rank, floor, ceiling
044                StdOut.println("key rank floor ceil");
045                StdOut.println("-------------------");
046                for (char i = 'A'; i <= 'Z'; i++) {
047                        String s = i + "";
048                        StdOut.format("%2s %4d %4s %4s\n", s, st.rank(s), st.floor(s), st.ceiling(s));
049                }
050                StdOut.println();
051
052                // test range search and range count
053                String[] from = { "A", "Z", "X", "0", "B", "C" };
054                String[] to   = { "Z", "A", "X", "Z", "G", "L" };
055                StdOut.println("range search");
056                StdOut.println("-------------------");
057                for (int i = 0; i < from.length; i++) {
058                        StdOut.format("%s-%s (%2d) : ", from[i], to[i], st.size(from[i], to[i]));
059                        for (String s : st.keys(from[i], to[i]))
060                                StdOut.print(s + " ");
061                        StdOut.println();
062                }
063                StdOut.println();
064
065                // delete the smallest keys
066                for (int i = 0; i < st.size() / 2; i++) {
067                        st.deleteMin();
068                }
069                StdOut.println("After deleting the smallest " + st.size() / 2 + " keys");
070                StdOut.println("--------------------------------");
071                for (String s : st.keys())
072                        StdOut.println(s + " " + st.get(s));
073                StdOut.println();
074
075                // delete all the remaining keys
076                while (!st.isEmpty()) {
077                        st.delete(st.select(st.size() / 2));
078                }
079                StdOut.println("After deleting the remaining keys");
080                StdOut.println("--------------------------------");
081                for (String s : st.keys())
082                        StdOut.println(s + " " + st.get(s));
083                StdOut.println();
084
085                StdOut.println("After adding back N keys");
086                StdOut.println("--------------------------------");
087                for (int i = 0; i < keys.length; i++)
088                        st.put(keys[i], i);
089                for (String s : st.keys())
090                        StdOut.println(s + " " + st.get(s));
091                StdOut.println();
092
093                StdOut.println();
094
095
096
097
098                // insert N elements in order if one command-line argument supplied
099                if (args.length == 0) return;
100                int N = Integer.parseInt(args[0]);
101                RedBlackBST<Integer, Integer> st2 = new RedBlackBST<>();
102                for (int i = 0; i < N; i++) {
103                        st2.put(i, i);
104                        int h = st2.height();
105                        //StdOut.println("i = " + i + ", height = " + h + ", size = " + st2.size());
106                }
107
108                // delete keys in random order
109                StdOut.println("Deleting keys in random order");
110                while (st2.size() > 0) {
111                        int i = StdRandom.uniform(N);
112                        if (st2.contains(i)) {
113                                st2.delete(i);
114                                int h = st2.height();
115                                //StdOut.println("i = " + i + ", height = " + h + ", size = " + st2.size());
116                        }
117                }
118
119                StdOut.println("size = " + st2.size());
120        }
121}