class Trie {
    private TrieNode root;

    Trie() {
        this.root = new TrieNode();
    }

    public TrieNode getRoot() {
        return this.root;
    }

    public boolean search(String s) {
        s += "*";
        TrieNode temp = this.root; // set a temp node to the root for searching
        int j = 0; // loops through string index
        while(!temp.getChildren().IsEmpty()) { // runs till it reaches a node with no children
            int nextCounter = 0;
            temp.getChildren().First(); // moves to the first element
            for(int i = 0; i < temp.getChildren().GetSize(); i++) { // loops through the children of the list
                if (s.charAt(j) == temp.getChildren().GetValue().getLetter()) { // checks if the string at index j is equal to the children
                    temp = temp.getChildren().GetValue(); // moves temp down to its child at the right value
                    j++;
                    if(j == s.length()) { // if finished going through the list
                        return true;
                    }
                }
                else {
                    temp.getChildren().Next(); // moves to the next element in the list
                    nextCounter++;
                    if(nextCounter > temp.getChildren().GetSize()-1) { // if moves next to the end of the word without finding
                        return false; // anything return false
                    }
                }
            }
        }

        return false;
    }

    /**
     * This function inserts strings into the trie
     *
     * @param value a string to be inserted
     * @param node  a node to move through the tree
     */
    public void insert(String value, TrieNode node) {
        value += "*"; // this is going to be the null character
        if(!search(value)) {
            if (this.root.getChildren().IsEmpty()) {
                node = this.root; // set node to the root
                for (int i = 0; i < value.length(); i++) { // loops through the word to insert it into the list
                    List<TrieNode> temp = node.getChildren(); // create a temp List to store the node
                    temp.InsertAfter(new TrieNode(value.charAt(i))); // inserts the character at the start of the string into the list

                    node.setChildren(temp); // sets the temp list as the children of the
                    node.getChildren().First(); // moves to the first node since its the first insert we know it will be at the right child

                    node = node.getChildren().GetValue(); // move the node to the first element in its children
                }
            }
            else {
                node = this.root; // set the node to the root
                int j = 0; // iterates through loop index
                while(j < value.length()) { // goes through the length of the value
                    node.getChildren().First();
                    boolean letterFound = false;
                    for(int i = 0; i < node.getChildren().GetSize(); i++) { // loops through the children of the node
                        if(value.charAt(j) == node.getChildren().GetValue().getLetter()) { // checks if string index is equal to trie node char
                            node = node.getChildren().GetValue(); // if so set node to that value
                            j++; // increment j
                            letterFound = true;
                        }
                        else { // if they are not equal
                            node.getChildren().Next(); // move to the next element in the linked list
                            letterFound = false;
                        }
                    }
                    if(!letterFound) { // if the letter is not found
                        node.getChildren().First();
                        node.getChildren().InsertAfter(new TrieNode(value.charAt(j))); // insert it
                    }
                }

            }
        }
    }

    public TrieNode getParentNode(TrieNode node, String s) {
        TrieNode temp = this.root; // start at the root
        int j = 0; // starts at the first index
        while(temp.getChildren().contains(node) == null) { // while the node hasnt been found
            int nextCounter = 0; // counts how many times the .Next function is called
            temp.getChildren().First();
            for(int i = 0; i < temp.getChildren().GetSize(); i++) { // goes through the children of temp
                if(s.charAt(j) == temp.getChildren().GetValue().getLetter()) {
                    temp = temp.getChildren().GetValue(); // move temp
                    j++; // move char index
                    break; // leave the loop
                }
                else {
                    temp.getChildren().Next(); // go to the next child
                    nextCounter++;
                    if(nextCounter > temp.getChildren().GetSize()-1)
                        return null;
                }
            }
        }
        return temp;
    }

    /**
     * This method deletes a string from the trie
     * @param s string to be deleted
     */
    public void delete(String s) {
        if(search(s)) { // if the string is in the list
            // This section of code will move to the last node of the string
            TrieNode temp  = this.root; // start at the root
            int j = 0; // s index
            boolean lastNodeFound = false;
            while(!temp.getChildren().IsEmpty() && !lastNodeFound) { // while the children  is not empty
                int nextCounter = 0;
                temp.getChildren().First(); // go to the first child
                for(int i = 0; i < temp.getChildren().GetSize(); i++) { // loops through the children
                    if(s.charAt(j) == temp.getChildren().GetValue().getLetter()) { // until string index is found
                        temp = temp.getChildren().GetValue(); // set temp to child
                        j++;
                        if(j == s.length()) { // if j gets to the end the last node is found
                            lastNodeFound = true;
                            break;
                        }
                    }
                    else {
                        temp.getChildren().Next(); // move to the next child
                        nextCounter++;
                        if(nextCounter > temp.getChildren().GetSize() -1) {
                            break;
                        }
                    }
                }
            }
            // The rest of the code deletes the word
            boolean deleted = false; // to check if its deleted
            while(!deleted) { // while the word hasnt been deleted
                TrieNode parent = getParentNode(temp, s); // stores parent
                if(parent.getChildren().GetSize() <= 1) { // if parent has less than two children move up
                    temp = getParentNode(temp,s);
                }
                else {
                    temp.setLetter('\0'); // set letter to null
                    temp = null; // set the node to null
                    deleted = true; // set deleted to true
                }
            }

        }
    }

    /*
     * Devon showed me his code for this and I applied a similar strategy to my code
     */
    public void print(String prefix, int length) {
        TrieNode temp = this.root;
        char[] primChars = prefix.toCharArray();

        for(int i = 0; i < primChars.length; i++) {
            if(!temp.getChildren().IsEmpty())
                temp.getChildren().First();
            for(int j = 0; j < temp.getChildren().GetSize(); j++) {
                if(primChars[i] == temp.getChildren().GetValue().getLetter()) {
                    temp = temp.getChildren().GetValue();
                    break;
                }
                temp.getChildren().Next();
            }
        }
        int lengthLeft = length - primChars.length;
        Stack<Character> suffix = new Stack<>();
        printPossibleWords(prefix, lengthLeft,0,  suffix, temp);
    }

    /*
     * Devon showed me his code and I used a similar strategy to his.
     */
    private void printPossibleWords(String prefix, int lengthLeft, int suffixLength, Stack<Character> suffix, TrieNode temp) {
        if (suffixLength == lengthLeft) {
            String word = prefix;
            Character[] suffixCopy = new Character[lengthLeft];

            for (int i = lengthLeft - 1; i >= 0; i--) {
                suffixCopy[i] = suffix.pop();
            }
            for (Character c : suffixCopy) {
                suffix.push(c);
            }

            for (int i = 0; i < temp.getChildren().GetSize(); i++) {
                temp.getChildren().SetPos(i);
                if (temp.getChildren().GetValue().getLetter() == '*') {
                    for (int j = 0; j < lengthLeft; j++) {
                        word += suffixCopy[j];
                    }
                    System.out.println(word);
                }

            }
            suffix.pop();
            return;
        }
            int n = 0;
            while(suffixLength < lengthLeft) {
                temp.getChildren().SetPos(n);
                if(n != temp.getChildren().GetSize() && temp.getChildren().GetValue().getLetter() != '*')
                {
                    suffix.push(temp.getChildren().GetValue().getLetter());
                    suffixLength++;
                    printPossibleWords(prefix, lengthLeft, suffixLength, suffix, temp.getChildren().GetValue());
                }
                else {
                    suffix.pop();
                    return;
                }
                suffixLength--;
                n++;
            }
        }
    }