package com.wrox.algorithms.tstrees;

import com.wrox.algorithms.lists.List;

public class TernarySearchTree {
    /* znak blankietowy, zastępujący dowolny "konkretny" znak */
    public static final char WILDCARD = '?';

    /** Korzeń drzewa lub wartość pusta dla pustego drzewa */
    private Node _root;

    public void add(CharSequence word) {
        assert word != null : "nie określono słowa";
        assert word.length() > 0 : "nie można używać pustych słów";

        Node node = insert(_root, word, 0);
        if (_root == null) {
            _root = node;
        }
    }

    public boolean contains(CharSequence word) {
        assert word != null : "nie określono słowa";
        assert word.length() > 0 : "nie można używać pustych słów";

        Node node = search(_root, word, 0);
        return node != null && node.isEndOfWord();
    }

    public void patternMatch(CharSequence pattern, List results) {
        assert pattern != null : "nie określono wzorca";
        assert pattern.length() > 0 : "wzorzec nie może być pusty";
        assert results != null : "nie określono listy wynikowej";

        patternMatch(_root, pattern, 0, results);
    }

    public void prefixSearch(CharSequence prefix, List results) {
        assert prefix != null : "nie określono prefiksu";
        assert prefix.length() > 0 : "prefiks nie może być pusty";

        inOrderTraversal(search(_root, prefix, 0), results);
    }

    private Node search(Node node, CharSequence word, int index) {
        assert word != null : "nie określono poszukiwanego słowa";

        Node result = node;

        if (node == null) {
            return null;
        }

        char c = word.charAt(index);

        if (c == node.getChar()) {
            if (index + 1 < word.length()) {
                result = search(node.getChild(), word, index + 1);
            }
        } else if (c < node.getChar()) {
            result = search(node.getSmaller(), word, index);
        } else {
            result = search(node.getLarger(), word, index);
        }

        return result;
    }

    private Node insert(Node node, CharSequence word, int index) {
        assert word != null : "nie określono wstawianego słowa";

        char c = word.charAt(index);

        if (node == null) {
            return insert(new Node(c), word, index);
        }

        if (c == node.getChar()) {
            if (index + 1 < word.length()) {
                node.setChild(insert(node.getChild(), word, index + 1));
            } else {
                node.setWord(word.toString());
            }
        } else if (c < node.getChar()) {
            node.setSmaller(insert(node.getSmaller(), word, index));
        } else {
            node.setLarger(insert(node.getLarger(), word, index));
        }

        return node;
    }

    private void patternMatch
       (Node node, CharSequence pattern, int index, List results)  {
        assert pattern != null : "nie określono wzorca";
        assert results != null : "nie określono listy wynikowej";

        if (node == null) {
            return;
        }

        char c = pattern.charAt(index);

        if (c == WILDCARD || c < node.getChar()) {
            patternMatch(node.getSmaller(), pattern, index, results);
        }

        if (c == WILDCARD || c == node.getChar()) {
            if (index + 1 < pattern.length()) {
                patternMatch(node.getChild(), pattern, index + 1, results);
            } else if (node.isEndOfWord()) {
                results.add(node.getWord());
            }
        }

        if (c == WILDCARD || c > node.getChar()) {
            patternMatch(node.getLarger(), pattern, index, results);
        }
    }

    private void inOrderTraversal(Node node, List results) {
        assert results != null : "nie określono listy wynikowej";

        if (node == null) {
            return;
        }

        inOrderTraversal(node.getSmaller(), results);
        if (node.isEndOfWord()) {
            results.add(node.getWord());
        }
        inOrderTraversal(node.getChild(), results);
        inOrderTraversal(node.getLarger(), results);
    }

    private static final class Node {
        /** znak przechowywany w węźle */
        private final char _c;

        /** lewy brat (jeśli istnieje) */
        private Node _smaller;

        /** prawy brat (jeśli istnieje) */
        private Node _larger;

        /** korzeń poddrzewa kontynuacyjnego (jeśli istnieje) */
        private Node _child;

        /** kompletne słowo przechowywane w węźle zawierającym jego ostatni znak */
        private String _word;

        public Node(char c) {
            _c = c;
        }

        public char getChar() {
            return _c;
        }

        public Node getSmaller() {
            return _smaller;
        }

        public void setSmaller(Node smaller) {
            _smaller = smaller;
        }

        public Node getLarger() {
            return _larger;
        }

        public void setLarger(Node larger) {
            _larger = larger;
        }

        public Node getChild() {
            return _child;
        }

        public void setChild(Node child) {
            _child = child;
        }

        public String getWord() {
            return _word;
        }

        public void setWord(String word) {
            _word = word;
        }

        public boolean isEndOfWord() {
            return getWord() != null;
        }
    }
}
