class TernaryTrie

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

Public Class Methods

new() click to toggle source

constructor simply ensures we have a root

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

Public Instance Methods

find(key) click to toggle source

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

# 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) click to toggle source

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

key: A string
return: A values or nil if nothing found

# 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) click to toggle source

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

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

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

to_hash() click to toggle source

Routine which converts the trie into a hash table

return: hash table of key/value pairs

# 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