Listing 3. Trie
/*
* Trie
*/
using System;
using com.db4o;
namespace PersistentTrees
{
///
/// Description of Trie.
///
/// trie class
public class Trie
{
private TriePnode root; // Root of Trie
// Constructor
public Trie()
{
root = null;
}
// insert
// Insert a key/data pair into the tree.
// Allows duplicates
public void insert(string key, // Key to insert
Object data) // Data assoc.
with key
{
TriePnode t = root;
TriePnode parent = null;
int index=0;
int slen = key.Length;
for(int i=0; i< slen; i++)
{
char c = key[i];
// If a node doesn't exist -- create it
if(t == null) t = new TriePnode();
// If this is the first node of the tree,
// it is the
// root. Otherwise, it is stored in the
// pnodes array
// of the parent
if(i==0)
root = t;
else
parent.setPnodePointer(index, t);
// If the character is not on the node,
// add it
if((index=t.isCharOnNode(c))==-1)
index = t.addKeyChar(c);
if(i == slen-1) break;
parent = t;
t = t.getPnodePointer(index);
}
// Finally, add the data item
t.addData(index, data);
}
// search
// Searches for a string in the trie.
// If found, returns the Object[] data array associated.
// Else, returns null
// db is the ObjectContainer holding the trie
public Object[] search(string _key,
ObjectContainer db)
{
TriePnode t;
char c;
int index=0;
// Empty trie?
if((t=root)==null) return(null);
int slen = _key.Length;
for(int i=0; i