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}