source: liacs/da/opdr2a/trie.cc@ 83

/* Author    : Rick van der Zwet
 * S-number  : 0433373
 * Version   : $Id: trie.cc 322 2007-11-22 14:09:00Z rick $
 * Copyright : FreeBSD Licence
 */

#include "trie.h"

#ifndef TRIE_CC
#define TRIE_CC

template <class InfoTp>
TrieNode<InfoTp>::TrieNode()
{
    Value = '\0';
    One = NULL;
    Zero = NULL;
    Parent = NULL;
}



template <class InfoTp>
TrieNode<InfoTp>::~TrieNode()
{
    delete One;
    delete Zero;
}



template <class InfoTp>
Trie<InfoTp>::Trie ()
{
    Root = new TrieNode<InfoTp> ();
    //Set window to root
    GoRoot ();
}



template <class InfoTp>
Trie<InfoTp>::~Trie ()
{
    delete Root;
}



template <class InfoTp>
bool Trie<InfoTp>::AtLeaf ()
{
    if (Window->One == NULL and Window->Zero == NULL)
    {
        return(true);
    }

    // Got some extra nodes down below
    return(false);
}



template <class InfoTp>
void Trie<InfoTp>::GoChild (char K)
{
    // Call ExistsChild to check if node exists and deliver an pointer
    // to the node in NodeFound
    if ( ExistsChild(K) )
    {
        Window = NodeFound;
    }
}



template <class InfoTp>
void Trie<InfoTp>::GoRoot ()
{
    //set the current window on the Root pointer
    Window = Root;
}



template <class InfoTp>
bool Trie<InfoTp>::ExistsChild (char K)
{
    // worker with different knob, to make it able to get back
    TrieNode<InfoTp> * Worker = Window;

    int i;
    for (i = 7; i >= 0; i--)
    {
        // bit i is 1 or not?
        if (K & 1<<i)
        {
            // If node not exists, bail out
            if (Worker->One == NULL)
            {
                return false;
            }
            else
            {
                Worker = Worker->One;
            }
        }
        else
        {
            // If node not exists, bail out
            if (Worker->Zero == NULL)
            {
                return false;
            }
            else
            {
                Worker = Worker->Zero;
            }
        }
    }

    // Store found window in NodeFound
    NodeFound = Worker;
    return true;
}



template <class InfoTp>
char Trie<InfoTp>::FirstChild ()
{
    // worker with different knob, to make it able to get back
    TrieNode<InfoTp> * Worker = Window;
    // walk 8 bits, i indication of the bit currently are
    int i;
    // return value
    char retval = 0;
    for (i = 7; i >= 0; i--)
    {
        // go as many Zero if possible else go right if possible else return \0
        if (Worker->Zero != NULL)
        {
            Worker = Worker->Zero;
        }
        else if (Worker->One != NULL)
        {
            //set bit i to 1
            retval |= 1<<i;
            Worker = Worker->One;
        }
        else
        {
            retval = '\0';
            break;
        }
    }
    return(retval);
}



/* This does not seems be very logical in the first place, but try to
 * draw a picture and then follow the paths, just remind 2 things
 * -no One 'turns' are allowed, cause those are higher order childs
 * -the story ends if you hit the startnode from the right
 * XXX: Only works well with one level depth, not multilevel depth
 */
template <class InfoTp>
char Trie<InfoTp>::NextChild (char K)
{
    // store startnode
    TrieNode<InfoTp> * Worker;
    // tmp (loop) counter
    int i;
    // return value, not changed if not found
    int retval = '\0';

    // goto child node if it exists at least
    if (ExistsChild(K)) {
        Worker = NodeFound;

        // depth counter
        i = 0;
        while ( true )
        {
            // ends if in startnode and came from right or
            // in startnode en no left turn possible
            if (Worker->Parent == Window)
            {
                if (Worker->Parent->One == Worker or
                       Worker->Parent->One == NULL)
                {
                    return(retval);
                }
            }

            //if from left and right available, go for it
            if (Worker->Parent->Zero == Worker and
                Worker->Parent->One != NULL)
            {
                Worker = Worker->Parent->One;

                //walk to child leaf
                while (i > 0)
                {
                    //decrement counter, cause we are going inward again
                    i--;
                    // if left available take it, else right
                    if (Worker->Zero != NULL)
                    {
                        Worker = Worker->Zero;
                    }
                    else
                    {
                        Worker = Worker->One;
                    }
                }

                //calculate value NextChild
                retval = 0;
                for (i = 0; i <= 7; i++)
                {
                    if (Worker->Parent->One == Worker)
                    {
                        retval |= 1<<i;
                    }
                    Worker = Worker->Parent;
                }

                //should never happen
                if (Worker != Window)
                {
                    perror("BUG: NextChild find value error");
                    exit(1);
                }
                return(retval);
            }

            //set new value Worker
            Worker = Worker->Parent;
            //raise counter
            i++;
        }
        // end none found
        return(retval);
    }
    // no valid leaf
    return(retval);
}



template <class InfoTp>
void Trie<InfoTp>::AddChild (char K)
{
    //get worker pointer
    TrieNode<InfoTp> * Worker = Window;

    int i;
    for (i = 7; i >= 0; i--)
    {
        //bit i is 1 or not?
        if (K & 1<<i)
        {
            // check is node exists, else create new one
            if (Worker->One == NULL)
            {
                Worker->One = new TrieNode<InfoTp>();
            }
            Worker->One->Parent = Worker;
            Worker = Worker->One;
        }
        else {
            // check is node exists, else create new one
            if (Worker->Zero == NULL)
            {
                Worker->Zero = new TrieNode<InfoTp>();
            }
            Worker->Zero->Parent = Worker;
            Worker = Worker->Zero;
        }
    }
}



template <class InfoTp>
void Trie<InfoTp>::RemoveChild (char K)
{
    TrieNode<InfoTp> * Worker;
    int i; //loop counter
    //check whether this knob exists
    if ( ExistsChild(K) )
    {
        Worker = NodeFound;
        //and is leaf
        if (Worker->One == NULL and Worker->Zero == NULL)
        {
            //delete obsolete knob and null refering pointer
            // walk 7 steps up and delete node if both pointers are zero
            // first step is special cause the other could be a leaf as
            // well


            //goto parent
            Worker = Worker->Parent;
            //deleted leaf specified at NodeFound
            if (Worker->One == NodeFound)
            {
                delete Worker->One;
                Worker->One = NULL;
            }
            else
            {
                delete Worker->Zero;
                Worker->Zero = NULL;
            }

            for (i = 0; i <= 6; i++)
            {
                // go one up
                Worker = Worker->Parent;

                //XXX: Only need to check the node we came from, instead
                //of both

                // Check wether we could delete arch 1
                if (Worker->One != NULL)
                {
                    //delete subnode if both pointers are NULL
                    if (Worker->One->One == NULL and
                        Worker->One->Zero == NULL)
                    {
                        delete Worker->One;
                        Worker->One = NULL;
                    }
                }

                // Check wether we could delete arch 0
                if (Worker->Zero != NULL)
                {
                    //delete subnode if both pointers are NULL
                    if (Worker->Zero->One == NULL and
                        Worker->Zero->Zero == NULL)
                    {
                        delete Worker->Zero;
                        Worker->Zero = NULL;
                    }
                }
            }

            //Should never happen
            if (Window != Worker)
            {
                perror("BUG: Pointer delete error");
                exit(1);
            }
        }
    }
}



template <class InfoTp>
void Trie<InfoTp>::PutInfo (InfoTp I)
{
    Window->Value = I;
}



template <class InfoTp>
InfoTp Trie<InfoTp>::GetInfo ()
{
    return(Window->Value);
}



template <class InfoTp>
void Trie<InfoTp>::GotoNode(TrieNode<InfoTp> *Nd)
{
    Window = Nd;
}



template <class InfoTp>
TrieNode<InfoTp> *Trie<InfoTp>::GetNode()
{
    return(Window);
}

#endif