package Others;

// Java Program to implement Auto-Complete 
// Feature using Trie
class Trieac {
    
    // Alphabet size (# of symbols) 
    public static final int ALPHABET_SIZE = 26;

    // Trie node 
    static class TrieNode 
    { 
        TrieNode children[] = new TrieNode[ALPHABET_SIZE];
    
        // isWordEnd is true if the node represents 
        // end of a word 
        boolean isWordEnd;
    };
    
    // Returns new trie node (initialized to NULLs) 
    static TrieNode getNode() {
        TrieNode pNode = new TrieNode(); 
        pNode.isWordEnd = false; 
        
        for(int i = 0; i < ALPHABET_SIZE; i++) 
            pNode.children[i] = null; 
        
        return pNode; 
    }
    
    // If not present, inserts key into trie. If the 
    // key is prefix of trie node, just marks leaf node 
    static void insert(TrieNode root, final String key) 
    { 
        TrieNode pCrawl = root; 
        
        for(int level = 0; level < key.length(); level++) 
        { 
            int index = (key.charAt(level) - 'a');
            if (pCrawl.children[index] == null) 
            pCrawl.children[index] = getNode(); 
            pCrawl = pCrawl.children[index]; 
        } 

        // mark last node as leaf 
        pCrawl.isWordEnd = true; 
    } 

    // Returns true if key presents in trie, else false 
    boolean search(TrieNode root, final String key) 
    { 
        int length = key.length(); 
        TrieNode pCrawl = root; 
        
        for (int level = 0; level < length; level++) 
        { 
            int index = (key.charAt(level) - 'a');
            
            if (pCrawl.children[index] == null) 
                pCrawl = pCrawl.children[index]; 
        } 

        return (pCrawl != null && pCrawl.isWordEnd); 
    } 

    // Returns 0 if current node has a child 
    // If all children are NULL, return 1. 
    static boolean isLastNode(TrieNode root) 
    { 
        for (int i = 0; i < ALPHABET_SIZE; i++) 
            if (root.children[i] != null) 
                return false; 
        return true; 
    }
    
    // Recursive function to print auto-suggestions 
    // for given node. 
    static void suggestionsRec(TrieNode root, String currPrefix) 
    { 
        // found a string in Trie with the given prefix 
        if (root.isWordEnd) 
        { 
            System.out.println(currPrefix);
        } 

        // All children struct node pointers are NULL 
        if (isLastNode(root)) 
            return; 

        for (int i = 0; i < ALPHABET_SIZE; i++) 
        { 
            if (root.children[i] != null) 
            { 
                // append current character to currPrefix string 
                currPrefix += (char)(97 + i); 

                // recur over the rest 
                suggestionsRec(root.children[i], currPrefix); 
            } 
        } 
    }
    
    // Fucntion  to print suggestions for
    // given query prefix.
    static int printAutoSuggestions(TrieNode root, 
                                final String query) 
    { 
        TrieNode pCrawl = root; 

        // Check if prefix is present and find the 
        // the node (of last level) with last character 
        // of given string. 
        int level; 
        int n = query.length(); 
        
        for (level = 0; level < n; level++) 
        { 
            int index = (query.charAt(level) - 'a');

            // no string in the Trie has this prefix 
            if (pCrawl.children[index] == null) 
                return 0; 

            pCrawl = pCrawl.children[index]; 
        } 

        // If prefix is present as a word. 
        boolean isWord = (pCrawl.isWordEnd == true); 

        // If prefix is last node of tree (has no 
        // children) 
        boolean isLast = isLastNode(pCrawl); 

        // If prefix is present as a word, but 
        // there is no subtree below the last 
        // matching node. 
        if (isWord && isLast) 
        { 
            System.out.println(query);
            return -1; 
        } 

        // If there are are nodes below last 
        // matching character. 
        if (!isLast) 
        { 
            String prefix = query; 
            suggestionsRec(pCrawl, prefix); 
            return 1; 
        }
        
        return 0;
    }
    
    // Driver code
    public static void main(String[] args)
    {   
        TrieNode root = getNode(); 
        insert(root, "hello"); 
        insert(root, "dog"); 
        insert(root, "hell"); 
        insert(root, "cat"); 
        insert(root, "a"); 
        insert(root, "hel"); 
        insert(root, "help"); 
        insert(root, "helps"); 
        insert(root, "helping"); 
        int comp = printAutoSuggestions(root, "hel"); 

        if (comp == -1)
            System.out.println("No other strings found "+
                                    "with this prefix\n");
        else if (comp == 0) 
            System.out.println("No string found with"+ 
                                        " this prefix\n");
    }
}