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.



74
75
76
 
# File 'lib/decode/trie.rb', line 74

def initialize
	@root = Node.new
end

Instance Attribute Details

#root ⇒ Object

The root of the trie.



80
81
82
 
# File 'lib/decode/trie.rb', line 80

def root
  @root
end

Instance Method Details

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

Enumerate all lexical scopes under the specified path.



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

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.



85
86
87
88
89
90
91
92
93
 
# File 'lib/decode/trie.rb', line 85

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.



99
100
101
 
# File 'lib/decode/trie.rb', line 99

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

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

Traverse the trie. See Node:traverse for details.



120
121
122
123
124
 
# File 'lib/decode/trie.rb', line 120

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