class RubyIndexer::PrefixTree

: [Value]
See en.wikipedia.org/wiki/Trie for more information
`Value` type.
finished typing yet. This PrefixTree implementation allows for string keys and any arbitrary value using the generic
A PrefixTree is useful for autocomplete, since we always want to find all alternatives while the developer hasn’t
“‘
tree.search(“bar”) # => [“bar”]
tree.search(“ba”) # => [“bar”, “baz”]
tree.search(“b”) # => [“bar”, “baz”]
tree.search(“”) # => [“bar”, “baz”]
# When we search it, it finds all possible values based on partial (or complete matches):
# }
# }
# }
# “z” => “baz”
# “r” => “bar”,
# “a” => {
# “b” => {
# {
# Internally, the structure is analogous to this, but using nodes:
tree.insert(“baz”, “baz”)
tree.insert(“bar”, “bar”)
# Insert entries using the same key and value
tree = PrefixTree.new
“`ruby
## Example
hash structure, where the keys are the characters of the inserted strings.
A PrefixTree is a data structure that allows searching for partial strings fast. The tree is similar to a nested

def delete(key)

: (String key) -> void
that match it. For example, if the tree contains `foo` and we ask to delete `fo`, then `foo` will be deleted
Deletes the entry identified by `key` from the tree. Notice that a partial match will still delete all entries 
def delete(key)
  node = find_node(key)
  return unless node
  # Remove the node from the tree and then go up the parents to remove any of them with empty children
  parent = node.parent #: Node[Value]?
  while parent
    parent.children.delete(node.key)
    return if parent.children.any? || parent.leaf
    node = parent
    parent = parent.parent
  end
end

def find_node(key)

: (String key) -> Node[Value]?
Find a node that matches the given `key` 
def find_node(key)
  node = @root
  key.each_char do |char|
    snode = node.children[char]
    return nil unless snode
    node = snode
  end
  node
end

def initialize

: -> void 
def initialize
  @root = Node.new(
    "",
    "", #: as untyped
  ) #: Node[Value]
end

def insert(key, value)

: (String key, Value value) -> void
Inserts a `value` using the given `key` 
def insert(key, value)
  node = @root
  key.each_char do |char|
    node = node.children[char] ||= Node.new(char, value, node)
  end
  # This line is to allow a value to be overridden. When we are indexing files, we want to be able to update entries
  # for a given fully qualified name if we find more occurrences of it. Without being able to override, that would
  # not be possible
  node.value = value
  node.leaf = true
end

def search(prefix)

: (String prefix) -> Array[Value]
of values for a given match
Notice that if the `Value` is an array, this method will return an array of arrays, where each entry is the array
return it as a result. The result is always an array of the type of value attribute to the generic `Value` type.
Search the PrefixTree based on a given `prefix`. If `foo` is an entry in the tree, then searching for `fo` will 
def search(prefix)
  node = find_node(prefix)
  return [] unless node
  node.collect
end