Class: RubyIndexer::PrefixTree

Inherits:
Object
  • Object
show all
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 : [Value]

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PrefixTree

: -> void



38
39
40
41
42
43
 
# File 'lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb', line 38

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

Instance Method Details

#delete(key) ⇒ Object

Deletes the entry identified by ‘key` from the tree. Notice that a partial match will still delete all entries that match it. For example, if the tree contains `foo` and we ask to delete `fo`, then `foo` will be deleted : (String key) -> void



76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb', line 76

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

#insert(key, value) ⇒ Object

Inserts a ‘value` using the given `key` : (String key, Value value) -> void



59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb', line 59

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

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



50
51
52
53
54
55
 
# File 'lib/ruby_indexer/lib/ruby_indexer/prefix_tree.rb', line 50

def search(prefix)
  node = find_node(prefix)
  return [] unless node

  node.collect
end