Class: Decode::Trie

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

Overview

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.



65
66
67
 
# File 'lib/decode/trie.rb', line 65

def initialize
	@root = Node.new
end

Instance Attribute Details

#root ⇒ Object

The root of the trie.



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

def root
  @root
end

Instance Method Details

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

Enumerate all lexical scopes under the specified path.



99
100
101
102
103
104
105
106
107
 
# File 'lib/decode/trie.rb', line 99

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) ⇒ Object

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



76
77
78
79
80
81
82
83
84
 
# File 'lib/decode/trie.rb', line 76

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

#lookup(path) ⇒ Object

Lookup the values at the specified path.



90
91
92
 
# File 'lib/decode/trie.rb', line 90

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

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

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



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

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