`class Trie`

Represents a prefix-trie data structure for fast lexical lookups.

Nested

Node

Definitions

`def initialize`

Initialize an empty trie.

Implementation

def initialize
	@root = Node.new
end

`attr :root`

The root of the trie.

Signature

attribute　Node: The root node of the trie structure.

`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 at the specified path.

Implementation

def insert(path, value)
	node = @root
	
	# Navigate to the target node, creating nodes as needed:
	path.each do |key|
		node = (node.children[key] ||= Node.new)
	end
	
	# Add the value to the target node:
	(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　Node | Nil: The node at the specified path, or nil if not found.

Implementation

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

`def each(path = [], &block)`

Enumerate all lexical scopes under the specified path.

Signature

parameter　path　Array(String)

The starting path to enumerate from.

yields　{|path, values| ...}

Called for each path with values.

parameter　path　Array(String): The lexical path.
parameter　values　Array(Object) | Nil: The values that exist at the given 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 starting from the specified path. See Decode::Trie::Node#traverse for details.

Signature

parameter　path　Array(String): The starting path to traverse from.
yields　{|path, node, descend| ...}: Called for each node during traversal.

Implementation

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