org/guru/boggle/DictionaryTrie.java

   1 package org.guru.boggle;
   2
   3 import java.io.BufferedReader;
   4 import java.io.FileReader;
   5 import java.io.IOException;
   6 import java.util.Set;
   7
   8 import com.google.common.base.Objects;
   9 import com.google.common.base.Preconditions;
  10 import com.google.common.collect.ImmutableSet;
  11 import com.google.common.collect.Sets;
  12
  13 public class DictionaryTrie {
  14
  15     private static class Node {
  16         private boolean wordEndsHere;
  17         private final Node[] children = new Node[26];
  18
  19         public Node(boolean wordEndsHere) {
  20             this.wordEndsHere = wordEndsHere;
  21         }
  22
  23         private int letterToIndex(char letter) {
  24             Preconditions.checkArgument(letter >= 'A' && letter <= 'Z', "Expect uppercase letter");
  25             return letter - 'A';
  26         }
  27
  28         // nullable
  29         public Node childForLetter(char letter) {
  30             return children[letterToIndex(letter)];
  31         }
  32
  33         public void addChildAtLetter(Node child, char letter) {
  34             Preconditions.checkState(!hasChildAtLetter(letter), "I already have a child");
  35             children[letterToIndex(letter)] = child;
  36         }
  37
  38         public boolean hasChildAtLetter(char letter) {
  39             return children[letterToIndex(letter)] != null;
  40         }
  41
  42         public Set<Character> childrenList() {
  43             Set<Character> result = Sets.newHashSetWithExpectedSize(8);
  44             for (int i = 0; i < 26; ++i) {
  45                 if (children[i] != null) {
  46                     result.add((char) (i + 'A'));
  47                 }
  48             }
  49             return result;
  50         }
  51
  52         public boolean doesWordEndHere() {
  53             return wordEndsHere;
  54         }
  55
  56         public void markWordEndsHere() {
  57             wordEndsHere = true;
  58         }
  59
  60         @Override
  61         public String toString() {
  62             return Objects.toStringHelper(this)
  63             .add("wordEndsHere", wordEndsHere)
  64             .add("children", children)
  65             .toString();
  66         }
  67     }
  68
  69     private final Node root = new Node(false);
  70
  71     public DictionaryTrie(String inputFilePath) throws IOException {
  72         FileReader fr = new FileReader(inputFilePath);
  73         BufferedReader br = new BufferedReader(fr);
  74         try {
  75             String line;
  76             while ((line = br.readLine()) != null) {
  77                 line = line.toUpperCase();
  78                 Node node = root;
  79                 for (int i = 0; i < line.length(); ++i) {
  80                     char letter = line.charAt(i);
  81                     if (!Character.isUpperCase(letter)) {
  82                         break;
  83                     }
  84                     boolean lastCharacter = (i == line.length() - 1);
  85                     if (node.hasChildAtLetter(letter)) {
  86                         node = node.childForLetter(letter);
  87                         if (lastCharacter) {
  88                             node.markWordEndsHere();
  89                         }
  90                     } else {
  91                         Node child = new Node(lastCharacter);
  92                         node.addChildAtLetter(child, letter);
  93                     }
  94                 }
  95                 System.out.printf("Added %s\n", line);
  96             }
  97         } catch (IOException e) {
  98             System.err.println("Error: " + e);
  99         } finally {
 100             br.close();
 101             fr.close();
 102         }
 103     }
 104
 105     // nullable
 106     private Node traverse(String word) {
 107         Node node = root;
 108         for (int i = 0; i < word.length(); ++i) {
 109             char letter = word.charAt(i);
 110             if (!Character.isUpperCase(letter)) {
 111                 return null;
 112             }
 113             if (node.hasChildAtLetter(letter)) {
 114                 node = node.childForLetter(letter);
 115             } else {
 116                 return null;
 117             }
 118         }
 119         return node;
 120     }
 121
 122     public boolean containsWord(String word) {
 123         Node node = traverse(word);
 124         return node != null && node.doesWordEndHere();
 125     }
 126
 127     public Set<Character> possibleSuccessorLetters(String prefix) {
 128         Node node = traverse(prefix);
 129         if (node == null) {
 130             return ImmutableSet.of();
 131         }
 132         return node.childrenList();
 133     }
 134 }