› Decode › Source › Decode › Trie

class Trie

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

Signature
rbs

generic T

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

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(Symbol)

The lexical path where the value will be inserted.

parameter　value　T

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:
	if node.values
		node.values << value
	else
		node.values = [value]
	end
end

def lookup(path)

Lookup the values at the specified path.

Signature
parameter　path　Array(Symbol)

The lexical path which contains the values.

returns　Node?

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(Symbol)

The starting path to enumerate from.

yields　{|path, values| ...}

Called for each path with values.

parameter　path　Array(Symbol)

The lexical path.

parameter　values　Array[T]?

The values that exist at the given path.

rbs

(?Array[Symbol]) (Array[Symbol], (Array[T] | nil)) -> void -> void

Implementation

 
def each(path = [], &block)
	if node = @root.lookup(path, 0)
		node.traverse(path) 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(Symbol)

The starting path to traverse from.

yields　{|path, node, descend| ...}

Called for each node during traversal.

rbs

(?Array[Symbol]) (Array[Symbol], Node, Proc) -> void -> void

Implementation

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