<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title>Class: TernaryTrie</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<link rel="stylesheet" href=".././rdoc-style.css" type="text/css" media="screen" />
<script type="text/javascript">
// <![CDATA[
function popupCode( url ) {
window.open(url, "Code", "resizable=yes,scrollbars=yes,toolbar=no,status=no,height=150,width=400")
}
function toggleCode( id ) {
if ( document.getElementById )
elem = document.getElementById( id );
else if ( document.all )
elem = eval( "document.all." + id );
else
return false;
elemStyle = elem.style;
if ( elemStyle.display != "block" ) {
elemStyle.display = "block"
} else {
elemStyle.display = "none"
}
return true;
}
// Make codeblocks hidden by default
document.writeln( "<style type=\"text/css\">div.method-source-code { display: none }</style>" )
// ]]>
</script>
</head>
<body>
<div id="classHeader">
<table class="header-table">
<tr class="top-aligned-row">
<td><strong>Class</strong></td>
<td class="class-name-in-header">TernaryTrie</td>
</tr>
<tr class="top-aligned-row">
<td><strong>In:</strong></td>
<td>
<a href="../files/lib/utility/ternarytrie_rb.html">
lib/utility/ternarytrie.rb
</a>
<br />
</td>
</tr>
<tr class="top-aligned-row">
<td><strong>Parent:</strong></td>
<td>
Object
</td>
</tr>
</table>
</div>
<!-- banner header -->
<div id="bodyContent">
<div id="contextContent">
<div id="diagram">
<map id="map" name="map">
<area shape="rect" coords="5,5,96,53" href="TernaryTrie.html" alt="TernaryTrie
" />
</map>
<img src="../dot/f_58.png" usemap="#map" border="0" alt="dot/f_58.png">
</div>
<div id="description">
<p>
class <a href="TernaryTrie.html">TernaryTrie</a> 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
</p>
</div>
</div>
<div id="method-list">
<h3 class="section-bar">Methods</h3>
<div class="name-list">
<a href="#M000017">find</a>
<a href="#M000016">find_exact</a>
<a href="#M000015">insert</a>
<a href="#M000014">new</a>
<a href="#M000018">to_hash</a>
</div>
</div>
</div>
<!-- if includes -->
<div id="section">
<div id="class-list">
<h3 class="section-bar">Classes and Modules</h3>
Class <a href="TernaryTrie/TNode.html" class="link">TernaryTrie::TNode</a><br />
</div>
<!-- if method_list -->
<div id="methods">
<h3 class="section-bar">Public Class methods</h3>
<div id="method-M000014" class="method-detail">
<a name="M000014"></a>
<div class="method-heading">
<a href="#M000014" class="method-signature">
<span class="method-name">new</span><span class="method-args">()</span>
</a>
</div>
<div class="method-description">
<p>
constructor simply ensures we have a root
</p>
<p><a class="source-toggle" href="#"
onclick="toggleCode('M000014-source');return false;">[Source]</a></p>
<div class="method-source-code" id="M000014-source">
<pre>
<span class="ruby-comment cmt"># File lib/utility/ternarytrie.rb, line 22</span>
<span class="ruby-keyword kw">def</span> <span class="ruby-identifier">initialize</span>
<span class="ruby-ivar">@root</span> = <span class="ruby-keyword kw">nil</span>
<span class="ruby-keyword kw">end</span>
</pre>
</div>
</div>
</div>
<h3 class="section-bar">Public Instance methods</h3>
<div id="method-M000017" class="method-detail">
<a name="M000017"></a>
<div class="method-heading">
<a href="#M000017" class="method-signature">
<span class="method-name">find</span><span class="method-args">(key)</span>
</a>
</div>
<div class="method-description">
<p>
Returns array of values that are the shortest possible match of the key.
</p>
<dl>
<dt><tt>key</tt></dt><dd>A string
</dd>
<dt><tt>return</tt></dt><dd>An array of values or nil if nothing found
</dd>
</dl>
<p><a class="source-toggle" href="#"
onclick="toggleCode('M000017-source');return false;">[Source]</a></p>
<div class="method-source-code" id="M000017-source">
<pre>
<span class="ruby-comment cmt"># File lib/utility/ternarytrie.rb, line 46</span>
<span class="ruby-keyword kw">def</span> <span class="ruby-identifier">find</span>(<span class="ruby-identifier">key</span>)
<span class="ruby-keyword kw">return</span> [] <span class="ruby-keyword kw">if</span> <span class="ruby-operator">!</span><span class="ruby-identifier">key</span>.<span class="ruby-identifier">respond_to?</span> <span class="ruby-identifier">:to_str</span>
<span class="ruby-identifier">key</span> = <span class="ruby-identifier">key</span>.<span class="ruby-identifier">to_str</span>
<span class="ruby-identifier">match</span> = []
<span class="ruby-identifier">find_r</span>(<span class="ruby-ivar">@root</span>, <span class="ruby-identifier">key</span>, <span class="ruby-identifier">match</span>, <span class="ruby-value">0</span>)
<span class="ruby-identifier">match</span>
<span class="ruby-keyword kw">end</span>
</pre>
</div>
</div>
</div>
<div id="method-M000016" class="method-detail">
<a name="M000016"></a>
<div class="method-heading">
<a href="#M000016" class="method-signature">
<span class="method-name">find_exact</span><span class="method-args">(key)</span>
</a>
</div>
<div class="method-description">
<p>
Returns an exact match only of the key or nil if not found
</p>
<dl>
<dt><tt>key</tt></dt><dd>A string
</dd>
<dt><tt>return</tt></dt><dd>A values or nil if nothing found
</dd>
</dl>
<p><a class="source-toggle" href="#"
onclick="toggleCode('M000016-source');return false;">[Source]</a></p>
<div class="method-source-code" id="M000016-source">
<pre>
<span class="ruby-comment cmt"># File lib/utility/ternarytrie.rb, line 36</span>
<span class="ruby-keyword kw">def</span> <span class="ruby-identifier">find_exact</span>(<span class="ruby-identifier">key</span>)
<span class="ruby-keyword kw">return</span> <span class="ruby-keyword kw">nil</span> <span class="ruby-keyword kw">if</span> <span class="ruby-operator">!</span><span class="ruby-identifier">key</span>.<span class="ruby-identifier">respond_to?</span> <span class="ruby-identifier">:to_str</span>
<span class="ruby-identifier">key</span> = <span class="ruby-identifier">key</span>.<span class="ruby-identifier">to_str</span>
<span class="ruby-keyword kw">return</span> <span class="ruby-identifier">find_exact_r</span>(<span class="ruby-ivar">@root</span>, <span class="ruby-identifier">key</span>, <span class="ruby-value">0</span>)
<span class="ruby-keyword kw">end</span>
</pre>
</div>
</div>
</div>
<div id="method-M000015" class="method-detail">
<a name="M000015"></a>
<div class="method-heading">
<a href="#M000015" class="method-signature">
<span class="method-name">insert</span><span class="method-args">(key, val)</span>
</a>
</div>
<div class="method-description">
<p>
Inserts a key/val pair - no duplicate keys (will replace key if found).
</p>
<dl>
<dt><tt>key</tt></dt><dd>A string
</dd>
<dt><tt>value</tt></dt><dd>A value which ay be any object.
</dd>
</dl>
<p><a class="source-toggle" href="#"
onclick="toggleCode('M000015-source');return false;">[Source]</a></p>
<div class="method-source-code" id="M000015-source">
<pre>
<span class="ruby-comment cmt"># File lib/utility/ternarytrie.rb, line 29</span>
<span class="ruby-keyword kw">def</span> <span class="ruby-identifier">insert</span>(<span class="ruby-identifier">key</span>, <span class="ruby-identifier">val</span>)
<span class="ruby-ivar">@root</span> = <span class="ruby-identifier">insert_r</span>(<span class="ruby-ivar">@root</span>, <span class="ruby-identifier">key</span>, <span class="ruby-identifier">val</span>, <span class="ruby-value">0</span>)
<span class="ruby-keyword kw">end</span>
</pre>
</div>
</div>
</div>
<div id="method-M000018" class="method-detail">
<a name="M000018"></a>
<div class="method-heading">
<a href="#M000018" class="method-signature">
<span class="method-name">to_hash</span><span class="method-args">()</span>
</a>
</div>
<div class="method-description">
<p>
Routine which converts the trie into a hash table
</p>
<dl>
<dt><tt>return</tt></dt><dd>hash table of key/value pairs
</dd>
</dl>
<p><a class="source-toggle" href="#"
onclick="toggleCode('M000018-source');return false;">[Source]</a></p>
<div class="method-source-code" id="M000018-source">
<pre>
<span class="ruby-comment cmt"># File lib/utility/ternarytrie.rb, line 56</span>
<span class="ruby-keyword kw">def</span> <span class="ruby-identifier">to_hash</span>
<span class="ruby-identifier">key</span> = <span class="ruby-value str">" "</span> <span class="ruby-operator">*</span> <span class="ruby-value">64</span> <span class="ruby-comment cmt"># max key length - raise if keys are enormeous</span>
<span class="ruby-identifier">hash</span> = {}
<span class="ruby-identifier">to_hash_r</span>(<span class="ruby-ivar">@root</span>, <span class="ruby-identifier">key</span>, <span class="ruby-identifier">hash</span>, <span class="ruby-value">0</span>)
<span class="ruby-identifier">hash</span>
<span class="ruby-keyword kw">end</span>
</pre>
</div>
</div>
</div>
</div>
</div>
<div id="validator-badges">
<p><small><a href="http://validator.w3.org/check/referer">[Validate]</a></small></p>
</div>
</body>
</html>
