› Decode › Source › Decode › Trie

class Trie

A prefix-trie data structure for fast lexical lookups.

Nested

Definitions

def initialize

Initialize an empty trie.

Implementation

 
def initialize
	@root = Node.new
end

attr :root

The root of the trie.

Signature
attribute　Node

def insert(path, value)

Insert the specified value at the given path into the trie.

Signature
parameter　path　Array(String)

The lexical path where the value will be inserted.

parameter　value　Object

The value to insert.

Implementation

 
def insert(path, value)
	node = @root
	
	path.each do |key|
		node = (node.children[key] ||= Node.new)
	end
	
	(node.values ||= []) << value
end

def lookup(path)

Lookup the values at the specified path.

Signature
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.

Implementation

 
def lookup(path)
	@root.lookup(path)
end

def each(path = [], &block)

Enumerate all lexical scopes under the specified path.

Implementation

 
def each(path = [], &block)
	if node = @root.lookup(path)
		node.traverse do |path, node, descend|
			yield path, node.values
			
			descend.call
		end
	end
end

def traverse(path = [], &block)

Traverse the trie. See Decode::Trie::Node#traverse for details.

Implementation

 
def traverse(path = [], &block)
	if node = @root.lookup(path)
		node.traverse(&block)
	end
end