import java.util.ArrayList;

import java.util.TreeMap;

import util.FileOperation;

public class Trie {

    private class Node{

        public boolean isWord;

        public TreeMap<Character,Node> next;

        public Node(boolean isWord) {

            this.isWord=isWord;

            next=new TreeMap<>();

        }

        public Node() {

            this(false);

        }

    }

    private Node root;

    private int size;

    public Trie() {

        root=new Node();

        size=0;

    }

    public int getSize() {

        return size;

    }

    public void add(String word) {

        Node cur=root;

        for(char c:word.toCharArray()) {

            if(cur.next.get(c)==null)

                  cur.next.put(c, new Node());

            cur=cur.next.get(c);

        }

        if(!cur.isWord) {

            cur.isWord=true;

            size++;

        }

    }

    public boolean find(String word) {

        Node cur=root;

        for(char c:word.toCharArray()) {

            if(cur.next.get(c)==null)

                  return false;

            cur=cur.next.get(c);

        }

        return cur.isWord;

    }

    public boolean isPrefix(String word) {

        Node cur=root;

        for(char c:word.toCharArray()) {

            if(cur.next.get(c)==null)

                  return false;

            cur=cur.next.get(c);

        }

        return true;

    }

    public boolean searchRegex(String word) {

        return match(root,word,0);

    }

    private boolean match(Node node,String word,int index) {

        if(index==word.length()) return node.isWord;

        else {

            char c=word.charAt(index);

            if(c!='.') {

                if(node.next.get(c)==null) return false;

                return match(node.next.get(c), word, index+1);

            }else {

                for(char w:node.next.keySet()) {

                    if(match(node.next.get(w), word, index+1)) {

                        return true;

                    }

                }

                return false;

            }

        }

    }

    public static void main(String[] args) {

        System.out.println("Pride and Prejudice");

        ArrayList<String> words = new ArrayList<>();

        if(FileOperation.readFile("pride-and-prejudice.txt", words)){

            long startTime = System.nanoTime();

            long endTime = System.nanoTime();

            // ---

            startTime = System.nanoTime();

            Trie trie = new Trie();

            for(String word: words)

                trie.add(word);

            for(String word: words)

                trie.find(word);

            endTime = System.nanoTime();

            double time = (endTime - startTime) / 1000000000.0;

            System.out.println("Total different words: " + trie.getSize());

            System.out.println("Trie: " + time + " s");

        }

    }

}