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();
    }
}