Class: Trees::Trie

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

Defined Under Namespace

Classes: Result

Constant Summary collapse

PARAM_DELIMITERS = 
[' ', ':'].freeze
ARG_DELIMITERS = 
[' '].freeze

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Trie

Returns a new instance of Trie.



17
18
19
 
# File 'lib/trie.rb', line 17

def initialize
  @root_node = TrieNode.new
end

Instance Attribute Details

#root_node ⇒ Object (readonly)

Returns the value of attribute root_node.



13
14
15
 
# File 'lib/trie.rb', line 13

def root_node
  @root_node
end

Instance Method Details

#match(path:, current_node: @root_node, current_index: 0, params: {}) ⇒ Object 



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/trie.rb', line 39

def match(path:, current_node: @root_node, current_index: 0, params: {})
  return [] if (key = path[current_index]).nil?

  results = []

  # Static path segment.
  if (child_node = current_node.child(key:))
    results << Result.new(line: child_node.line, params:) if child_node.line
    results = [*results, *match(path:, current_node: child_node, current_index: current_index + 1, params:)]
  end

  # Dynamic path segment.
  current_node.params.each do |param|
    child_node = current_node.child(key: param)

    arg, next_index = capture_arg(start_index: current_index, path:)
    params[param.delete_prefix(':').to_sym] = arg

    results << Result.new(line: child_node.line, params:) if child_node.line
    results = [*results, *match(path:, current_node: child_node, current_index: next_index, params:)]
  end

  results
end

#merge(line:, current_node: @root_node) ⇒ Object 



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/trie.rb', line 21

def merge(line:, current_node: @root_node)
  @current_index = 0
  path = line.path

  while @current_index < path.length
    key = path[@current_index]

    @current_index += 1

    # Sometimes the key is an entire variable name.
    key = capture_param(path:) if key == ':'

    current_node = current_node.upsert_child(key:)
  end

  current_node.line = line
end