Class: Decode::Trie

Inherits:
Object
  • Object
show all
Defined in:
lib/decode/trie.rb

Overview

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

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Trie

Initialize an empty trie.



71
72
73
 
# File 'lib/decode/trie.rb', line 71

def initialize
	@root = Node.new
end

Instance Attribute Details

#root ⇒ Object (readonly)

The root of the trie.



77
78
79
 
# File 'lib/decode/trie.rb', line 77

def root
  @root
end

Instance Method Details

#each(path = [], &block) ⇒ Object

Enumerate all lexical scopes under the specified path.



111
112
113
114
115
116
117
118
119
 
# File 'lib/decode/trie.rb', line 111

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

#insert(path, value) ⇒ Object

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



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/decode/trie.rb', line 82

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

#lookup(path) ⇒ Object

Lookup the values at the specified path.



101
102
103
 
# File 'lib/decode/trie.rb', line 101

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

#The root node of the trie structure.=(rootnodeofthetriestructure. = (value)) ⇒ Object

The root of the trie.



77
 
# File 'lib/decode/trie.rb', line 77

attr :root

#traverse(path = [], &block) ⇒ Object

Traverse the trie starting from the specified path. See Decode::Trie::Node#traverse for details.



126
127
128
129
130
 
# File 'lib/decode/trie.rb', line 126

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