class RubyIndexer::PrefixTree

A PrefixTree is a data structure that allows searching for partial strings fast. The tree is similar to a nested hash structure, where the keys are the characters of the inserted strings.

Example¶ ↑

tree = PrefixTree[String].new
# Insert entries using the same key and value
tree.insert("bar", "bar")
tree.insert("baz", "baz")
# Internally, the structure is analogous to this, but using nodes:
# {
#   "b" => {
#     "a" => {
#       "r" => "bar",
#       "z" => "baz"
#     }
#   }
# }
# When we search it, it finds all possible values based on partial (or complete matches):
tree.search("") # => ["bar", "baz"]
tree.search("b") # => ["bar", "baz"]
tree.search("ba") # => ["bar", "baz"]
tree.search("bar") # => ["bar"]

A PrefixTree is useful for autocomplete, since we always want to find all alternatives while the developer hasn’t finished typing yet. This PrefixTree implementation allows for string keys and any arbitrary value using the generic Value type.

See en.wikipedia.org/wiki/Trie for more information

Constants

>Value

Public Class Methods

new()

# File lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb, line 42
def initialize
  @root = T.let(Node.new("", ""), Node[Value])
end

Public Instance Methods

delete(key)

# File lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb, line 77
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 = T.let(T.must(node.parent), T.nilable(Node[Value]))

  while parent
    parent.children.delete(node.key)
    return if parent.children.any? || parent.leaf

    node = parent
    parent = parent.parent
  end
end

insert(key, value)

# File lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb, line 60
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

search(prefix)

# File lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb, line 51
def search(prefix)
  node = find_node(prefix)
  return [] unless node

  node.collect
end

class RubyIndexer::PrefixTree

Example¶ ↑

Constants

Public Class Methods

new() Show source

Public Instance Methods

delete(key) Show source

insert(key, value) Show source

search(prefix) Show source

new()

delete(key)

insert(key, value)

search(prefix)