Class: Heist::Trie

Inherits:
Object
  • Object
show all
Defined in:
lib/trie.rb

Overview

A Trie is a special type of key-value store, one in which the keys are all sequences of some kind: they could be strings, or arrays, or lists. We use tries to store symbol tables in Heist because it makes autocompletion easier to implement, and one aim of Heist is to be a pleasant interactive Scheme.

In our particular implementation, keys (strings representing variable names) are split into arrays and stored in a series of nested hashtables whose keys are single characters. Strings sharing a common prefix share part of the tree structure. The Trie#inspect method provides a good representation of this (values omitted for the sake of brevity):

tree = Trie.new
tree['foo'] = 1

tree #=> {"f"=>{"o"=>{"o"=>{}}}}

tree['bar'] = 2
tree['baz'] = 3

tree #=> {"b"=>{"a"=>{"z"=>{}, "r"=>{}}}, "f"=>{"o"=>{"o"=>{}}}}

A trie is a recursive structure; each key in a trie points to another trie. Every trie contains a list of its children (a hash mapping characters to subtries) and may contain a value if it appears at the end of a sequence making up a full key of the root trie.

For more information, see en.wikipedia.org/wiki/Trie

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(value = nil) ⇒ Trie

A Trie is initialized with an optional value. The value may be omitted if the trie does not represent the end of a key sequence.



36
37
38
39
 
# File 'lib/trie.rb', line 36

def initialize(value = nil)
  @value = value
  @children = {}
end

Instance Attribute Details

#value ⇒ Object

Returns the value of attribute value.



32
33
34
 
# File 'lib/trie.rb', line 32

def value
  @value
end

Instance Method Details

#[](key) ⇒ Object

Returns the value corresponding to key, or nil if none is found.



50
51
52
53
 
# File 'lib/trie.rb', line 50

def [](key)
  trie = traverse(key)
  trie ? trie.value : nil
end

#[]=(key, value) ⇒ Object

Assigns value to the given key.



56
57
58
 
# File 'lib/trie.rb', line 56

def []=(key, value)
  traverse(key, true).value = value
end

#has_key?(key) ⇒ Boolean

Returns true iff the given key is present in the Trie. They key must match a complete key sequence that maps to a value, not a partial prefix with no value attached.

Returns:

  • (Boolean) 


44
45
46
47
 
# File 'lib/trie.rb', line 44

def has_key?(key)
  trie = traverse(key)
  trie and not trie.value.nil?
end

#inspect ⇒ Object

Returns a string representation of the trie’s internal structure. Values are not printed; the main purpose of this method is to inspect the internal tree structure.



122
123
124
 
# File 'lib/trie.rb', line 122

def inspect
  @children.inspect
end

#longest_prefix(key) ⇒ Object

Returns the longest unique key prefix that starts with key. This is used for autocompletion in the REPL. Given a string, this method returns another string such that the start of the output is the same as the input, and the output may contain zero or more additional characters such that all the keys that begin with the input also begin with the output.

tree = Trie.new
tree['foo'] = 1
tree['bar'] = 2
tree['baz'] = 3

tree.longest_prefix 'f'
#=> "foo"
tree.longest_prefix 'b'
#=> "ba"



103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/trie.rb', line 103

def longest_prefix(key)
  prefix = convert_key(key).dup
  trie = traverse(key)
  return nil if trie.nil?
  while trie.singular?
    next_key = trie.prefixes.first
    prefix << next_key
    trie = trie.traverse(next_key)
  end
  case key
    when String then prefix.join('')
    when Symbol then prefix.join('').to_sym
    else prefix
  end
end

#prefixes ⇒ Object

Returns an array of all the characters used as keys in this Trie. That is, this method returns the initial letters of all the keys stored in the Trie.



75
76
77
 
# File 'lib/trie.rb', line 75

def prefixes
  @children.keys
end

#singular? ⇒ Boolean

Returns true if the Trie has no value and only one child. Used in longest_prefix to find the longest unique prefix from some starting point.

Returns:

  • (Boolean) 


82
83
84
 
# File 'lib/trie.rb', line 82

def singular?
  @value.nil? and @children.size == 1
end

#traverse(key, create_if_absent = false) ⇒ Object

Walks the Trie structure using the given key, returning the resulting subtrie or nil if the key is absent. Pass true as the second argument to create a subtrie for the key if none exists.



63
64
65
66
67
68
69
70
 
# File 'lib/trie.rb', line 63

def traverse(key, create_if_absent = false)
  key = convert_key(key)
  return self if key.empty?
  trie = @children[key.first]
  return nil if trie.nil? and not create_if_absent
  trie = @children[key.first] = Trie.new if trie.nil?
  trie.traverse(key[1..-1], create_if_absent)
end