import java.io.BufferedReader; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.ArrayList; /** * Counts the words in a text with a map: each word is a key, and its value is * how many times the word appears. The map is a BSTMap or a HashMap, chosen * when the WordCounter is made. * * To time one map on one text, 5 times in a row: * * java WordCounter BST CLEANED_shakespeare.txt * java WordCounter HashMap CLEANED_shakespeare.txt * * Each run times three things: building the map, looking up every word, * and removing every key. You write the last two (Project 07, Task 2). */ public class WordCounter { private MapSet wordCounts; // word -> how many times it appears private int totalWords; // every word counted, repeats included /** dataStructure is "BST" or "HashMap" (capital letters don't matter). */ public WordCounter(String dataStructure) { if (dataStructure.equalsIgnoreCase("BST")) { wordCounts = new BSTMap(); } else if (dataStructure.equalsIgnoreCase("HashMap")) { wordCounts = new HashMap(); } else { throw new IllegalArgumentException("the data structure must be \"BST\" or \"HashMap\", not \"" + dataStructure + "\""); } totalWords = 0; } /** Reads a text file and returns its words in order. Words are separated by spaces or line breaks. */ public 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.split(" ")) { if (!word.isEmpty()) { words.add(word); } } line = reader.readLine(); } reader.close(); } catch (IOException e) { System.out.println("Could not read " + filename + ": " + e.getMessage()); } return words; } /** * Counts every word in the list, adding to the counts already in the map. * Returns the time it took, in milliseconds, measured with System.nanoTime(). */ public double buildMap(ArrayList words) { long start = System.nanoTime(); for (String word : words) { Integer count = wordCounts.get(word); if (count == null) { wordCounts.put(word, 1); } else { wordCounts.put(word, count + 1); } totalWords++; } return (System.nanoTime() - start) / 1e6; } /** * Looks up every word in the list with the map's get, without changing the map. * Returns the time it took, in milliseconds, measured with System.nanoTime(). */ public double timeLookups(ArrayList words) { // TODO 1: record the start time, as buildMap does // TODO 2: for each word in the list, call get on the map with that word // (only get: no put, so the map doesn't change) // TODO 3: return the time since the start, in milliseconds, as buildMap does throw new UnsupportedOperationException("timeLookups is not written yet (Task 2)"); } /** * Removes every key from the map, one at a time, in the order of keySet, and sets * the total word count back to 0. Returns the time the removes took, in milliseconds. */ public double timeRemoveAll() { // TODO 1: get the list of keys with keySet (before starting the timer: // we are timing remove, not keySet) // TODO 2: record the start time // TODO 3: for each key in that list, call remove on the map with that key // TODO 4: compute the time since the start, in milliseconds // TODO 5: set totalWords to 0: the map is empty now // TODO 6: return the time throw new UnsupportedOperationException("timeRemoveAll is not written yet (Task 2)"); } /** Empties the map and sets the total word count back to 0. */ public void clearMap() { wordCounts.clear(); totalWords = 0; } /** The number of words counted, repeats included. */ public int totalWordCount() { return totalWords; } /** The number of different words: the number of keys in the map. */ public int uniqueWordCount() { return wordCounts.size(); } /** How many times word appears; 0 if it never does. */ public int getCount(String word) { Integer count = wordCounts.get(word); if (count == null) { return 0; } return count; } /** The fraction of all the words counted that are this word; 0 if it never appears. */ public double getFrequency(String word) { if (totalWords == 0) { return 0; } return (double) getCount(word) / totalWords; } /** The map's maxDepth: levels for a BSTMap, the biggest bin for a HashMap. */ public int maxDepth() { return wordCounts.maxDepth(); } /** Writes the total word count, then one line per word, "word count", in the order of keySet. */ public boolean writeWordCount(String filename) { try { FileWriter writer = new FileWriter(filename); writer.write(totalWords + "\n"); ArrayList keys = wordCounts.keySet(); ArrayList values = wordCounts.values(); for (int i = 0; i < keys.size(); i++) { writer.write(keys.get(i) + " " + values.get(i) + "\n"); } writer.close(); return true; } catch (IOException e) { System.out.println("Could not write " + filename + ": " + e.getMessage()); return false; } } /** * Times one map on one text, 5 times in a row. Each run builds the map, looks up every * word, and removes every key, and prints the three times. Then it prints the number of * different words and the maxDepth after building. */ public static void main(String[] args) { if (args.length != 2) { System.out.println("Give a data structure and a text file, for example:"); System.out.println(" java WordCounter BST CLEANED_shakespeare.txt"); System.out.println(" java WordCounter HashMap CLEANED_shakespeare.txt"); return; } WordCounter counter = new WordCounter(args[0]); ArrayList words = counter.readWords(args[1]); System.out.printf("Timing a %s on the %,d words of %s, 5 times (all times in ms):%n", args[0].equalsIgnoreCase("BST") ? "BSTMap" : "HashMap", words.size(), args[1]); System.out.printf(" %-6s %12s %12s %12s%n", "", "build", "lookups", "remove all"); int different = 0; int depth = 0; String stopped = null; // the "not written yet" message, if a timing method is missing try { for (int run = 1; run <= 5; run++) { counter.clearMap(); double build = counter.buildMap(words); different = counter.uniqueWordCount(); // record these before removing every key depth = counter.maxDepth(); String lookups = "-"; String removes = "-"; try { lookups = String.format("%.1f", counter.timeLookups(words)); removes = String.format("%.1f", counter.timeRemoveAll()); } catch (UnsupportedOperationException e) { stopped = e.getMessage(); } System.out.printf(" run %d: %12.1f %12s %12s%n", run, build, lookups, removes); } System.out.printf("%,d different words. maxDepth after building: %,d%n", different, depth); if (stopped != null) { System.out.println("(- means not timed: " + stopped + ".)"); } } catch (UnsupportedOperationException e) { System.out.println("Stopped: " + e.getMessage() + ". Finish Lab 07 first."); } } }