<reponame>minemile/wildhack
class TrieNode:
    """A node in the trie structure"""

    def __init__(self, char):
        # the character stored in this node
        self.char = char

        # whether this can be the end of a word
        self.is_end = False

        # a counter indicating how many times a word is inserted
        # (if this node's is_end is True)
        self.counter = 0

        self.popularity = None

        # a dictionary of child nodes
        # keys are characters, values are nodes
        self.children = {}


class Trie(object):
    """The trie object"""

    def __init__(self):
        """
        The trie has at least the root node.
        The root node does not store any character
        """
        self.root = TrieNode("")

    def insert(self, word, popularity=None):
        """Insert a word into the trie"""
        node = self.root

        # Loop through each character in the word
        # Check if there is no child containing the character, create a new child for the current node
        for char in word:
            if char in node.children:
                node = node.children[char]
            else:
                # If a character is not found,
                # create a new node in the trie
                new_node = TrieNode(char)
                new_node.popularity = popularity

                node.children[char] = new_node
                node = new_node

        # Mark the end of a word
        node.is_end = True

        # Increment the counter to indicate that we see this word once more
        node.counter += 1

    def dfs(self, node, prefix):
        """Depth-first traversal of the trie
        
        Args:
            - node: the node to start with
            - prefix: the current prefix, for tracing a
                word while traversing the trie
        """
        if node.is_end:
            self.output.append((prefix + node.char, node.counter, node.popularity))

        for child in node.children.values():
            self.dfs(child, prefix + node.char)

    def query(self, x):
        """Given an input (a prefix), retrieve all words stored in
        the trie with that prefix, sort the words by the number of 
        times they have been inserted
        """
        # Use a variable within the class to keep all possible outputs
        # As there can be more than one word with such prefix
        self.output = []
        node = self.root

        # Check if the prefix is in the trie
        for char in x:
            if char in node.children:
                node = node.children[char]
            else:
                # cannot found the prefix, return empty list
                return []

        # Traverse the trie to get all candidates
        self.dfs(node, x[:-1])

        # Sort the results in reverse order and return
        # return sorted(self.output, key=lambda x: x[1], reverse=True)
        return self.output


def make_trie(query_database):
    trie = Trie()
    print(f"Making database for queries... It length: {len(query_database)}")
    for row in query_database:
        words = row.split()
        for word in words:
            trie.insert(word, 0)
    return trie

class TrieNode:
    """A node in the trie structure"""

    def __init__(self, char):
        # the character stored in this node
        self.char = char

        # whether this can be the end of a word
        self.is_end = False

        # a counter indicating how many times a word is inserted
        # (if this node's is_end is True)
        self.counter = 0

        self.popularity = None

        # a dictionary of child nodes
        # keys are characters, values are nodes
        self.children = {}


class Trie(object):
    """The trie object"""

    def __init__(self):
        """
        The trie has at least the root node.
        The root node does not store any character
        """
        self.root = TrieNode("")

    def insert(self, word, popularity=None):
        """Insert a word into the trie"""
        node = self.root

        # Loop through each character in the word
        # Check if there is no child containing the character, create a new child for the current node
        for char in word:
            if char in node.children:
                node = node.children[char]
            else:
                # If a character is not found,
                # create a new node in the trie
                new_node = TrieNode(char)
                new_node.popularity = popularity

                node.children[char] = new_node
                node = new_node

        # Mark the end of a word
        node.is_end = True

        # Increment the counter to indicate that we see this word once more
        node.counter += 1

    def dfs(self, node, prefix):
        """Depth-first traversal of the trie
        
        Args:
            - node: the node to start with
            - prefix: the current prefix, for tracing a
                word while traversing the trie
        """
        if node.is_end:
            self.output.append((prefix + node.char, node.counter, node.popularity))

        for child in node.children.values():
            self.dfs(child, prefix + node.char)

    def query(self, x):
        """Given an input (a prefix), retrieve all words stored in
        the trie with that prefix, sort the words by the number of 
        times they have been inserted
        """
        # Use a variable within the class to keep all possible outputs
        # As there can be more than one word with such prefix
        self.output = []
        node = self.root

        # Check if the prefix is in the trie
        for char in x:
            if char in node.children:
                node = node.children[char]
            else:
                # cannot found the prefix, return empty list
                return []

        # Traverse the trie to get all candidates
        self.dfs(node, x[:-1])

        # Sort the results in reverse order and return
        # return sorted(self.output, key=lambda x: x[1], reverse=True)
        return self.output


def make_trie(query_database):
    trie = Trie()
    print(f"Making database for queries... It length: {len(query_database)}")
    for row in query_database:
        words = row.split()
        for word in words:
            trie.insert(word, 0)
    return trie
A node in the trie structure # the character stored in this node # whether this can be the end of a word # a counter indicating how many times a word is inserted # (if this node's is_end is True) # a dictionary of child nodes # keys are characters, values are nodes The trie object The trie has at least the root node.         The root node does not store any character Insert a word into the trie # Loop through each character in the word # Check if there is no child containing the character, create a new child for the current node # If a character is not found, # create a new node in the trie # Mark the end of a word # Increment the counter to indicate that we see this word once more Depth-first traversal of the trie                  Args:             - node: the node to start with             - prefix: the current prefix, for tracing a                 word while traversing the trie Given an input (a prefix), retrieve all words stored in         the trie with that prefix, sort the words by the number of          times they have been inserted # Use a variable within the class to keep all possible outputs # As there can be more than one word with such prefix # Check if the prefix is in the trie # cannot found the prefix, return empty list # Traverse the trie to get all candidates # Sort the results in reverse order and return # return sorted(self.output, key=lambda x: x[1], reverse=True)