Class: LexerKit::Trie

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

Overview

Builds and encodes trie data structures for literal matching.

## Value Constraints

  • order: 0..MAX_ORDER (ORDER_UNSET is reserved for unset values)

  • action_ip: 0..0xFFFFFFFF (ACTION_UNSET used for non-terminal nodes)

## Label Resolution

labels hash must have Symbol keys only (Integer keys are ambiguous with direct offsets). Resolution order:

  1. If action_ref is in labels hash, use mapped value

  2. If action_ref is Symbol not in labels, raise ArgumentError

  3. If action_ref is Integer, use directly as offset

Defined Under Namespace

Classes: Node, NodeEntry, TrieData

Constant Summary collapse

ORDER_UNSET = 
0xFFFF
MAX_ORDER = 
0xFFFE
ACTION_UNSET = 
0xFFFFFFFF
MAX_EDGE_COUNT = 
0xFFFF

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(entries) ⇒ Trie

Returns a new instance of Trie.



25
26
27
 
# File 'lib/lexer_kit/trie.rb', line 25

def initialize(entries)
  @trie = build_trie(entries)
end

Class Method Details

.build(entries) ⇒ Object 



33
34
35
36
37
38
 
# File 'lib/lexer_kit/trie.rb', line 33

def self.build(entries)
  trie_entries = entries.map.with_index do |(literal, action_ip), index|
    [literal, index, action_ip]
  end
  new(trie_entries).encode
end

Instance Method Details

#encode(labels: nil) ⇒ Object 



29
30
31
 
# File 'lib/lexer_kit/trie.rb', line 29

def encode(labels: nil)
  encode_trie(@trie, labels || {})
end