class Decode::Trie

A prefix-trie data structure for fast lexical lookups.

Attributes

root[R]

The root of the trie. @attribute [Node]

Public Class Methods

new() click to toggle source

Initialize an empty trie.

# File lib/decode/trie.rb, line 74
def initialize
        @root = Node.new
end

Public Instance Methods

each(path = []) { |path, values| ... } click to toggle source

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(path, value) click to toggle source

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(path) click to toggle source

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(path = [], &block) click to toggle source

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