Class TernaryTrie
In: lib/utility/ternarytrie.rb
Parent: Object
TernaryTrie dot/f_58.png

class TernaryTrie implements a ternary search trie. The keys are are assumed to be strings, but the values can be any object. This is a very lightweight and useful object

Methods

find   find_exact   insert   new   to_hash  

Classes and Modules

Class TernaryTrie::TNode

Public Class methods

new()

constructor simply ensures we have a root

[Source]

# File lib/utility/ternarytrie.rb, line 22
  def initialize
    @root = nil
  end

Public Instance methods

find(key)

Returns array of values that are the shortest possible match of the key.

key
A string
return
An array of values or nil if nothing found

[Source]

# File lib/utility/ternarytrie.rb, line 46
  def find(key)
    return [] if !key.respond_to? :to_str
    key = key.to_str
    match = []
    find_r(@root, key, match, 0)
    match
  end
find_exact(key)

Returns an exact match only of the key or nil if not found

key
A string
return
A values or nil if nothing found

[Source]

# File lib/utility/ternarytrie.rb, line 36
  def find_exact(key)
    return nil if !key.respond_to? :to_str
    key = key.to_str
    return find_exact_r(@root, key, 0)
  end
insert(key, val)

Inserts a key/val pair - no duplicate keys (will replace key if found).

key
A string
value
A value which ay be any object.

[Source]

# File lib/utility/ternarytrie.rb, line 29
  def insert(key, val)
    @root = insert_r(@root, key, val, 0)
  end
to_hash()

Routine which converts the trie into a hash table

return
hash table of key/value pairs

[Source]

# File lib/utility/ternarytrie.rb, line 56
  def to_hash
    key = " " * 64  # max key length - raise if keys are enormeous
    hash = {}
    to_hash_r(@root, key, hash, 0)
    hash
  end

[Validate]