public class Trie{

    private int SIZE = 26;

    private TrieNode root;

    Trie(){

        root = new TrieNode();

    }

    private class TrieNode{

        private int num;//the times  that words passing this node

        private TrieNode[] son;//son point

        private boolean isEnd;//record weather there are points ending in this point

        private char val;//char value

        public TrieNode(){

            num = 1;

            son = new TrieNode[SIZE];

            isEnd = false;

        }

    }

    //create the trie tree

    public void insert(String str){//insert a word to the trie tree

        if(str == null||str.length() == 0){

            return;

        }

        TrieNode node = root;

        char[] letters = str.toCharArray();

        for(int i =0,len = str.length();i<len;i++){

            int pos = letters[i]-'a';

            if(node.son[pos]==null){

                node.son[pos] = new TrieNode();

                node.son[pos].val = letters[i];

            }else{

                node.son[pos].num++;

            }

            node = node.son[pos];

        }

        node.isEnd= true;//

    }

    //calculate the count of words'prefix

    public int countPrefix(String prefix){

        if(prefix == null||prefix.length()==0){

            return -1;

        }

        TrieNode node = root;

        char[] letters = prefix.toCharArray();

        int pos;

        int num = 0;

        for(int i=0,len = prefix.length();i<len;i++){

            pos = letters[i]-'a';

            node = node.son[pos];

            if(node==null){

                return 0;

            }else{

                num = node.num;

            }

        }

        return num;

    }

    //print the word having the assigned prefix

    public String hasprefix(String prefix){

        if(prefix ==null||prefix.length()==0){

            return null;

        }

        TrieNode node = root;

        char[] letters = prefix.toCharArray();

        int pos;

        for(int i=0,len = prefix.length();i<len; i++){

            pos = letters[i]-'a';

            if(node.son[pos]==null){

                return null;

            }else{

                node = node.son[pos];

            }

        }

        preTraverse(node,prefix);

        return null;

    }

    //walk the node's words

    public void preTraverse(TrieNode node,String prefix){

        if(!node.isEnd){

            for(TrieNode child:node.son){

                if(child!=null){

                    preTraverse(child,prefix+child.val);

                }

            }

            return;

        }

        System.out.println(prefix);

    }

    //find the completely matching word

    public boolean has(String str){

        if(str == null||str.length() == 0){

            return false;

        }

        TrieNode node = root;

        char[] letters = str.toCharArray();

        int pos;

        for(int i=0,len = str.length();i<len;i++){

            pos = letters[i]-'a';

            if(node.son[pos]==null){

                return false;

            }else{

                node = node.son[pos];

            }

        }

        return node.isEnd;

    }

    //pre-order of the trie tree

    public void preTraverse(TrieNode node){

        if(node!=null){

            System.out.print(node.val+" ");

            for(TrieNode child:node.son){

                preTraverse(child);

            }

        }

    }

    public TrieNode getRoot(){

        return this.root;

    }

    public static void main(String[] args){

        Trie tree = new Trie();

        String[] strs = {"dsfahjk","fjdkafhdask","fdhjfk","dafjdk","qepoi","fda"};

        String[] prefix={"ds","f","qepo","abd"};

        for(String str:strs){

            tree.insert(str);

        }

        for(String pre:prefix){

            int num = tree.countPrefix(pre);

            System.out.println(pre+" "+num);

        }

        tree.preTraverse(tree.getRoot());

        System.out.println("\ntree.has(\"f\"):"+tree.has("f"));

        System.out.println("tree.has(\"fda\"):"+tree.has("fda"));

        tree.hasprefix("f");

        System.out.println("countprefix(\"f\"):"+tree.countPrefix("f"));

    }

}