class Decode::Trie
A prefix-trie data structure for fast lexical lookups.
Attributes
The root of the trie. @attribute [Node]
Public Class Methods
Initialize an empty trie.
# File lib/decode/trie.rb, line 74 def initialize @root = Node.new end
Public Instance Methods
Enumerate all lexical scopes under the specified path.
@block {|path, values| …} @yield path [Array(String)] The lexical path. @yield values [Array(Object)] The values that exist at the given path.
# File lib/decode/trie.rb, line 108 def each(path = [], &block) if node = @root.lookup(path) node.traverse do |path, node, descend| yield path, node.values descend.call end end end
Insert the specified value at the given path into the trie. @parameter path [Array(String)] The lexical path where the value will be inserted. @parameter value [Object] The value to insert.
# File lib/decode/trie.rb, line 85 def insert(path, value) node = @root path.each do |key| node = (node.children[key] ||= Node.new) end (node.values ||= []) << value end
Lookup the values at the specified path.
@parameter path [Array(String)] The lexical path which contains the values. @returns [Array(Object) | Nil] The values that existed (or not) at the specified path.
# File lib/decode/trie.rb, line 99 def lookup(path) @root.lookup(path) end
Traverse the trie. See {Node#traverse} for details.
# File lib/decode/trie.rb, line 120 def traverse(path = [], &block) if node = @root.lookup(path) node.traverse(&block) end end