Listing 3. Trie


/*
 * Trie
 */

using System;
using com.db4o;

namespace PersistentTrees
{
        /// <summary>
        /// Description of Trie.
        /// </summary>
        /// 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<slen; i++)
                        {
                                c = _key[i];
                                if((index=t.isCharOnNode(c))==-1)
return(null);
                                if(i==slen-1) break;
                                db.activate(t,2);
                                t = t.getPnodePointer(index);
                        }
                        // Get the data
                        db.activate(t,3);
                        return(t.getDnodePointers(index).getData());
                }

        }
}