TeensyMud - 'A ruby mud server.'

Browse repository
back

ternarytrie.rb

#
# file:: ternarytrie.rb
# author:: Jon A. Lambert
# version:: 2.8.0
# date:: 01/19/2006
#
# This source code copyright (C) 2005, 2006 by Jon A. Lambert
# All rights reserved.
#
# Released under the terms of the TeensyMUD Public License
# See LICENSE file for additional information.
#


# 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
class TernaryTrie

public
# constructor simply ensures we have a root
def initialize
@root = nil
end

# Inserts a key/val pair - no duplicate keys (will replace key if found).
# [+key+] A string
# [+value+] A value which ay be any object.
def insert(key, val)
@root = insert_r(@root, key, val, 0)
end

# Returns an exact match only of the key or nil if not found
# [+key+] A string
# [+return+] A values or nil if nothing found
def find_exact(key)
return nil if !key.respond_to? :to_str
key = key.to_str
return find_exact_r(@root, key, 0)
end

# 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
def find(key)
return [] if !key.respond_to? :to_str
key = key.to_str
match = []
find_r(@root, key, match, 0)
match
end

# Routine which converts the trie into a hash table
# [+return+] hash table of key/value pairs
def to_hash
key = " " * 64 # max key length - raise if keys are enormeous
hash = {}
to_hash_r(@root, key, hash, 0)
hash
end

private
# The trie node - not for public consumption
class TNode
attr_accessor :val, :keyc, :l, :m, :r
def initialize(kc)
@keyc = kc
end
end

# recursive trie traversal routines follow
def insert_r(node, key, val, idx)
node = TNode.new(key[idx]) if node == nil
if idx == key.size - 1 && key[idx] == node.keyc
node.val = val
return node
end
node.l = insert_r(node.l, key, val, idx) if key[idx] && key[idx] < node.keyc
node.m = insert_r(node.m, key, val, idx+1) if key[idx] && key[idx] == node.keyc
node.r = insert_r(node.r, key, val, idx) if key[idx] && key[idx] > node.keyc
return node
end

def find_exact_r(node, key, idx)
return nil if node == nil
if idx == key.size - 1 && key[idx] == node.keyc
return node.val if node.val
return nil
end
return find_exact_r(node.l, key, idx) if key[idx] < node.keyc
return find_exact_r(node.m, key, idx+1) if key[idx] == node.keyc
return find_exact_r(node.r, key, idx) if key[idx] > node.keyc
end

def find_rest_r(node, match)
return if node == nil
if node.val
match << node.val
end
find_rest_r(node.l, match)
find_rest_r(node.m, match)
find_rest_r(node.r, match)
end

def find_r(node, key, match, idx)
return if node == nil
if idx == key.size - 1 && key[idx] == node.keyc
if node.val
match << node.val
end
find_rest_r(node.m, match)
return
end
return find_r(node.l, key, match, idx) if key[idx] && key[idx] < node.keyc
return find_r(node.m, key, match, idx+1) if key[idx] && key[idx] == node.keyc
return find_r(node.r, key, match, idx) if key[idx] && key[idx] > node.keyc
end

def to_hash_r(node, key, hash, idx)
return if node == nil
key[idx] = node.keyc
hash[key.strip] = node.val if node.val
to_hash_r(node.m, key, hash, idx+1)
to_hash_r(node.l, key, hash, idx)
to_hash_r(node.r, key, hash, idx)
end
end