Class: RubyIndexer::PrefixTree

Inherits:
Object
  • Object
show all
Extended by:
T::Generic, T::Sig
Defined in:
lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb

Overview

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 “‘ruby tree = PrefixTree.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

Defined Under Namespace

Classes: Node

Constant Summary collapse

Value = 
type_member

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PrefixTree

Returns a new instance of PrefixTree.



42
43
44
 
# File 'lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb', line 42

def initialize
  @root = T.let(Node.new("", ""), Node[Value])
end

Instance Method Details

#delete(key) ⇒ Object 



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# 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) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
72
 
# 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) ⇒ Object 



51
52
53
54
55
56
 
# 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