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

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.

Parameters:

  • path (Array(String)) —

    The lexical path where the value will be inserted.

  • value (Object) —

    The value to insert.



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) ⇒ Array(Object) | Nil

Lookup the values at the specified path.

Parameters:

  • path (Array(String)) —

    The lexical path which contains the values.

Returns:

  • (Array(Object) | Nil) —

    The values that existed (or not) 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