Algorithms-II : 4-Boggle: implementationalgs-II

1 files changed, 177 insertions, 0 deletions

diff --git a/Algorithms/Part-II/4-Boggle/BoggleHybridTST.java b/Algorithms/Part-II/4-Boggle/BoggleHybridTST.java
new file mode 100644
index 0000000..ee442bb
--- /dev/null
+++ b/Algorithms/Part-II/4-Boggle/BoggleHybridTST.java
@@ -0,0 +1,177 @@
+
+public class BoggleHybridTST
+{
+    private static final int R = 26;
+    private static final int OFFSET = 'A';
+
+    private static Node emptyNode = null;
+
+    private Node[] roots = new Node[R * R];
+
+    public class Node
+    {
+        private boolean isWord;
+        private char c;
+        private Node left, mid, right;
+
+        public boolean isWord() { return isWord; }
+        public String toString() { return "'"+c+"' "+isWord; }
+    }
+
+    public Node emptyNode() {
+        if (emptyNode == null) {
+            emptyNode = new Node();
+        }
+        return emptyNode;
+    }
+
+    public void put(String word)
+    {
+        int l = word.length();
+        if (l < 3) return;
+        int idx = ((word.charAt(0) - OFFSET) * R) + (word.charAt(1) - OFFSET);
+        roots[idx] = put(roots[idx], word, 2);
+    }
+
+    private Node put(Node n, String word, int d)
+    {
+        char c = word.charAt(d);
+
+        Node x = n;
+        if (n == null) {
+            x = new Node();
+            x.c = c;
+        }
+
+        char ref = x.c;
+        if (c < ref) {
+            x.left = put(x.left, word, d);
+        } else if (c == ref) {
+            if (word.length() == (d + 1)) {
+                x.isWord = true;
+            } else {
+                x.mid = put(x.mid, word, (d + 1));
+            }
+        } else {
+            x.right = put(x.right, word, d);
+        }
+
+        return x;
+    }
+
+    public boolean contains(String word)
+    {
+        return (get(word) != null);
+    }
+
+    private Node get(String word)
+    {
+        if (word.length() < 3) return null;
+        int idx = ((word.charAt(0) - OFFSET) * R) + (word.charAt(1) - OFFSET);
+        return get(roots[idx], word, 2);
+    }
+
+    private Node get(Node n, String word, int d)
+    {
+        if (n == null) return null;
+
+        char c = word.charAt(d);
+        char ref = n.c;
+
+        if (c < ref) {
+            return get(n.left, word, d);
+        } else if (c == ref) {
+            if (word.length() == (d + 1)) {
+                if (n.isWord) return n;
+                else return null;
+            }
+            return get(n.mid, word, (d + 1));
+        } else {
+            return get(n.right, word, d);
+        }
+    }
+
+    private Node get(Node n, char c)
+    {
+        if (n == null) return null;
+
+        char ref = n.c;
+
+        if (c < ref) {
+            return get(n.left, c);
+        } else if (c == ref) {
+            return n;
+        } else {
+            return get(n.right, c);
+        }
+    }
+
+    public Node filter(char c, Node n, StringBuilder s, int l)
+    {
+        if (n == null) return null;
+
+        if (l > 2) {
+            return get(n.mid, c);
+        } else if (l == 2) {
+            int idx = ((s.charAt(0) - OFFSET) * R) + (s.charAt(1) - OFFSET);
+            Node root = roots[idx];
+            if (root == null) return null;
+            return get(root, c);
+        } else {
+            return n;
+        }
+    }
+
+    public Node filter(char c, Node n, String s, int l)
+    {
+        if (n == null) return null;
+
+        if (l > 2) {
+            return get(n.mid, c);
+        } else if (l == 2) {
+            int idx = ((s.charAt(0) - OFFSET) * R) + (s.charAt(1) - OFFSET);
+            Node root = roots[idx];
+            if (root == null) return null;
+            return get(root, c);
+        } else {
+            return n;
+        }
+    }
+
+    public static void check(BoggleHybridTST tst, String word, boolean expected)
+    {
+        String status = "ok";
+        if (tst.contains(word) != expected)
+            status = "ERROR";
+        System.out.println("check "+word+" : "+status);
+    }
+
+    // test client
+    public static void main(String[] args)
+    {
+
+        BoggleHybridTST tst = new BoggleHybridTST();
+
+        In in = new In(args[0]);
+        String[] dictionary = in.readAllStrings();
+
+        for (String word : dictionary)
+            tst.put(word);
+
+        check(tst, "ABC", true);
+        check(tst, "BITE", false);
+        check(tst, "BITEX", false);
+        String word = "QUESTIONACCIA";
+        check(tst, word, true);
+
+        word += "X";
+        StringBuilder s = new StringBuilder();
+        Node n = tst.emptyNode();
+        for (int i = 0; i < word.length(); i++) {
+            char c = word.charAt(i);
+            n = tst.filter(c, n, s, i);
+            s.append(c);
+            System.out.println(s+" "+n);
+        }
+    }
+}