Initial boggle code checkin.HEADmaster

1 files changed, 134 insertions, 0 deletions

diff --git a/org/guru/boggle/DictionaryTrie.java b/org/guru/boggle/DictionaryTrie.java
new file mode 100644
index 0000000..421d670
--- /dev/null
+++ b/org/guru/boggle/DictionaryTrie.java
@@ -0,0 +1,134 @@
+package org.guru.boggle;
+
+import java.io.BufferedReader;
+import java.io.FileReader;
+import java.io.IOException;
+import java.util.Set;
+
+import com.google.common.base.Objects;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+
+public class DictionaryTrie {
+
+    private static class Node {
+        private boolean wordEndsHere;
+        private final Node[] children = new Node[26];
+
+        public Node(boolean wordEndsHere) {
+            this.wordEndsHere = wordEndsHere;
+        }
+
+        private int letterToIndex(char letter) {
+            Preconditions.checkArgument(letter >= 'A' && letter <= 'Z', "Expect uppercase letter");
+            return letter - 'A';
+        }
+
+        // nullable
+        public Node childForLetter(char letter) {
+            return children[letterToIndex(letter)];
+        }
+
+        public void addChildAtLetter(Node child, char letter) {
+            Preconditions.checkState(!hasChildAtLetter(letter), "I already have a child");
+            children[letterToIndex(letter)] = child;
+        }
+
+        public boolean hasChildAtLetter(char letter) {
+            return children[letterToIndex(letter)] != null;
+        }
+
+        public Set<Character> childrenList() {
+            Set<Character> result = Sets.newHashSetWithExpectedSize(8);
+            for (int i = 0; i < 26; ++i) {
+                if (children[i] != null) {
+                    result.add((char) (i + 'A'));
+                }
+            }
+            return result;
+        }
+
+        public boolean doesWordEndHere() {
+            return wordEndsHere;
+        }
+
+        public void markWordEndsHere() {
+            wordEndsHere = true;
+        }
+
+        @Override
+        public String toString() {
+            return Objects.toStringHelper(this)
+            .add("wordEndsHere", wordEndsHere)
+            .add("children", children)
+            .toString();
+        }
+    }
+
+    private final Node root = new Node(false);
+
+    public DictionaryTrie(String inputFilePath) throws IOException {
+        FileReader fr = new FileReader(inputFilePath);
+        BufferedReader br = new BufferedReader(fr);
+        try {
+            String line;
+            while ((line = br.readLine()) != null) {
+                line = line.toUpperCase();
+                Node node = root;
+                for (int i = 0; i < line.length(); ++i) {
+                    char letter = line.charAt(i);
+                    if (!Character.isUpperCase(letter)) {
+                        break;
+                    }
+                    boolean lastCharacter = (i == line.length() - 1);
+                    if (node.hasChildAtLetter(letter)) {
+                        node = node.childForLetter(letter);
+                        if (lastCharacter) {
+                            node.markWordEndsHere();
+                        }
+                    } else {
+                        Node child = new Node(lastCharacter);
+                        node.addChildAtLetter(child, letter);
+                    }
+                }
+                System.out.printf("Added %s\n", line);
+            }
+        } catch (IOException e) {
+            System.err.println("Error: " + e);
+        } finally {
+            br.close();
+            fr.close();
+        }
+    }
+
+    // nullable
+    private Node traverse(String word) {
+        Node node = root;
+        for (int i = 0; i < word.length(); ++i) {
+            char letter = word.charAt(i);
+            if (!Character.isUpperCase(letter)) {
+                return null;
+            }
+            if (node.hasChildAtLetter(letter)) {
+                node = node.childForLetter(letter);
+            } else {
+                return null;
+            }
+        }
+        return node;
+    }
+
+    public boolean containsWord(String word) {
+        Node node = traverse(word);
+        return node != null && node.doesWordEndHere();
+    }
+
+    public Set<Character> possibleSuccessorLetters(String prefix) {
+        Node node = traverse(prefix);
+        if (node == null) {
+            return ImmutableSet.of();
+        }
+        return node.childrenList();
+    }
+}