Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Patricia and Huffman, Sitting in a Trie

, 27 Dec 2004
Article demonstrates a text-based Patricia trie and adds new text-compression features.
article_demo.zip
MyPat.exe
article_src.zip
docs
pat.sdr
src
<!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" lang="en" xml:lang="en">
<head>
<title>PatriciaTrieC</title>
<link type="text/css" rel="stylesheet" href="style.css" />
<title></title>
</head>
<body>
<div class="box title">
<h2 class="right">PatriciaTrieC</h2>
</div>

<div class="box information"><b>Purpose</b><br />
<br />
<p>
The PatriciaTrieC stores text in a Patricia Trie and associates the ASSOCIATED_CLASS (default PayloadC) class with each text element
stored. It converts text to integers using a hard-coded Huffman code.
</p>
</div>

<div class="box information"><b>Data</b><br />
<br />
<table>
<tr>
<th>Visibility</th>
<th>Name</th>
<th>Type</th>
<th>Purpose</th>
</tr>
<tr>
<td>private</td>
<td>head</td>
<td>PatriciaNodeC*</td>
<td>a pointer to the first internal node of the patricia trie</td>
</tr>
<tr>
<td>private static</td>
<td>huffman_code</td>
<td>char [] (array)</td>
<td>stores conversion codes for text to key (or integer)</td>
</tr>
</table>
</div>

<!--------------------------------------------------->
<div class="box function"><b>Constructor</b><br />
<br />
<p>
sets the trie to empty. Note: the huffman_code is a class variable (static) so it is declared outside of any method when the program
using this class is run. See the pat.cpp file at the top where the huffman_code is initialized.
</p>
<b class="return">Parameters</b>
<ol>
<li>void</li>
</ol>
<b class="return">Returns</b>::: void
</div>

<!--------------------------------------------------->
<div class="box function"><b>Deconstructor</b><br />
<br />
<p>
deletes all internal trie nodes. it will not delete any PayloadC objects associated with the trie.
</p>
<b class="return">Parameters</b>
<ol>
<li>void</li>
</ol>
<b class="return">Returns</b>::: void
</div>

<!--------------------------------------------------->
<div class="box function"><b>Insert</b><br />
<br />
<p>
adds a key (text converted to a key or a raw key) to the trie. a ASSOCIATED_CLASS class is linked to the key. passing NULL in for the associated class is acceptable.
</p>
<b class="return">Parameters</b>
<ol>
<li>_key (char* OR keyType) ~ the key to store in the trie</li>
<li>_payload (ASSOCIATED_CLASS*) ~ the class to associate with the new key (default EMPTY_NODE)</li>
</ol>
<b class="return">Returns</b>::: bool
<ol>
<li>true ~ insert succeeded</li>
<li>false ~ ran out of memory or key already exists</li>
</ol>
</div>

<!--------------------------------------------------->
<div class="box function"><b>Search</b><br />
<br />
<p>
searches through the trie for a key.
</p>
<b class="return">Parameters</b>
<ol>
<li>_key (char* OR keyType) ~ the key to search for in the trie</li>
</ol>
<b class="return">Returns</b>::: ASSOCIATED_CLASS*
<ol>
<li>EMPTY_NODE ~ no match</li>
<li><u>NOT</u> EMPTY_NODE ~ a pointer to the class associated with the key searched for</li>
</ol>
</div>

<!--------------------------------------------------->
<div class="box function"><b>Remove</b><br />
<br />
<p>
removes one key from the trie.
</p>
<b class="return">Parameters</b>
<ol>
<li>_key (char* OR keyType) ~ the key to remove from the trie</li>
</ol>
<b class="return">Returns</b>::: ASSOCIATED_CLASS*
<ol>
<li>EMPTY_NODE ~ no match, nothing removed</li>
<li><u>NOT</u> EMPTY_NODE ~ a pointer to the class associated with the key just removed from the trie</li>
</ol>
</div>

<!--------------------------------------------------->
<div class="box function"><b>Clear</b><br />
<br />
<p>
wipes entire data structure clean. warning, the associated classes will not be removed. the head is set to EMPTY_NODE.
</p>
<b class="return">Parameters</b>
<ol>
<li>void</li>
</ol>
<b class="return">Returns</b>::: void
</div>

<!--------------------------------------------------->
<div class="box function"><b>Print</b><br />
<br />
<p>
prints the trie pre-order (root,left,right). prints addresses of internal nodes and key values of leaf nodes. only part
of the class if DEBUG is defined.
</p>
<b class="return">Parameters</b>
<ol>
<li>void</li>
</ol>
<b class="return">Returns</b>::: void
</div>

<!--------------------------------------------------->
<div class="box function"><b>IsBitOn</b><br />
<br />
<p>
checks if one bit in a key is true or 1. used in branching decisions.
</p>
<b class="return">Parameters</b>
<ol>
<li>_key (keyType) ~ the key to check one bit on</li>
<li>_bp (bitPositionType) ~ the position of the bit to check</li>
</ol>
<b class="return">Returns</b>::: bool
<ol>
<li>true ~ </li>
<li>false ~ </li>
</ol>
</div>

<!--------------------------------------------------->
<div class="box function"><b>BuildKey</b><br />
<br />
<p>
produces a key from a string of text, based on a general huffman code.
</p>
<b class="return">Parameters</b>
<ol>
<li>_txt (char*) ~ the text string to build the key from</li>
</ol>
<b class="return">Returns</b>::: keyType
<ol>
<li>0 ~ the string was empty</li>
<li>ALL (except zero) ~ the keyType representation of the text string</li>
</ol>
</div>

</body>
</html>

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Michael Jaworski
Software Developer
United Kingdom United Kingdom
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141223.1 | Last Updated 28 Dec 2004
Article Copyright 2004 by Michael Jaworski
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid