import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Scanner; /** * Watch your BSTMap grow in a window. * * java BSTDemo lecture's tree one put at a time, then the same words sorted * java BSTDemo tiny.txt count the words in a file, then print the counts * * Press Enter in the Terminal to take each step. */ public class BSTDemo { private static Scanner keyboard = new Scanner(System.in); public static void main(String[] args) { try { if (args.length == 0) { lectureKeys(); } else { countWords(args[0]); } } catch (UnsupportedOperationException e) { System.out.println(); System.out.println("Stopped: " + e.getMessage() + "."); System.exit(0); // also closes the window } } /** Waits for Enter, so you can make a prediction before each step. */ private static void pause(String prompt) { System.out.print(prompt + " [Enter] "); keyboard.nextLine(); } /** Lecture's tree, one put at a time, and then the same words in alphabetical order. */ private static void lectureKeys() { // These words have the same order as lecture's keys 15 8 17 3 10 16 20, // so they build lecture's tree. Each word's value is its lecture number. String[] words = {"dog", "bee", "fox", "ant", "cat", "eel", "gnu"}; int[] numbers = {15, 8, 17, 3, 10, 16, 20}; BSTMap map = new BSTMap<>(); BSTDisplay display = new BSTDisplay(map, "Lecture's tree: dog bee fox ant cat eel gnu"); System.out.println("Predict where each word goes before you press Enter."); for (int i = 0; i < words.length; i++) { pause("Next: put(\"" + words[i] + "\", " + numbers[i] + ")."); map.put(words[i], numbers[i]); display.show(words[i], "put " + words[i]); System.out.println(" the path from the root to " + words[i] + " is outlined in the window"); } System.out.println(); System.out.print(map); System.out.println(); pause("Now the same words in alphabetical order: ant bee cat dog eel fox gnu. Predict the shape."); String[] sorted = {"ant", "bee", "cat", "dog", "eel", "fox", "gnu"}; BSTMap chain = new BSTMap<>(); BSTDisplay display2 = new BSTDisplay(chain, "The same words in alphabetical order"); for (int i = 0; i < sorted.length; i++) { chain.put(sorted[i], i + 1); display2.show(sorted[i], "put " + sorted[i]); sleep(400); } System.out.println(); System.out.print(chain); System.out.println(); System.out.println("Close the windows to finish."); } /** Counts every word in a file with put and get, then prints the counts. */ private static void countWords(String filename) { ArrayList words = readWords(filename); if (words == null) { return; } BSTMap counts = new BSTMap<>(); BSTDisplay display = new BSTDisplay(counts, filename); int delay = words.size() <= 100 ? 150 : 0; System.out.println("Read " + words.size() + " words from " + filename + "."); pause("Build the tree?"); try { for (String word : words) { Integer count = counts.get(word); if (count == null) { counts.put(word, 1); } else { counts.put(word, count + 1); } if (delay > 0) { display.show(word, "put " + word); sleep(delay); } } } catch (UnsupportedOperationException e) { System.out.println("Stopped: " + e.getMessage() + ". Counting words needs put and get."); return; } display.show(null, "done"); try { System.out.println(counts.size() + " different words, " + counts.maxDepth() + " levels"); } catch (UnsupportedOperationException e) { System.out.println("(size and maxDepth are not written yet)"); } try { ArrayList keys = counts.keySet(); ArrayList values = counts.values(); for (int i = 0; i < keys.size(); i++) { System.out.println(" " + keys.get(i) + " " + values.get(i)); } } catch (UnsupportedOperationException e) { System.out.println("(keySet and values are not written yet, so the counts can't be listed)"); } System.out.println("Close the window to finish."); } /** Reads a text file and returns its words in lowercase, without punctuation. */ private static ArrayList readWords(String filename) { ArrayList words = new ArrayList<>(); try (BufferedReader reader = new BufferedReader(new FileReader(filename))) { String line = reader.readLine(); while (line != null) { for (String word : line.toLowerCase().split("[^a-z']+")) { if (!word.isEmpty()) { words.add(word); } } line = reader.readLine(); } } catch (IOException e) { System.out.println("Could not read " + filename + ": " + e.getMessage()); return null; } return words; } private static void sleep(int milliseconds) { try { Thread.sleep(milliseconds); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } }