mxtree.h

#ifndef __MX__TREE_H_
#define __MX__TREE_H_

/*
        MX library.

        http://lostsidedead.com/svn


        libmx written by jared bruni, it is wrappers around SDL
        and other api's to provide a set of classes and functions
        to produce multi media applications, using object oriented
        techniques.

        (C) 2008 LostSideDead


        This source file includes, the code for a tree.
        with right and left leaves, to sort the items
        The Key type must support a overloaded operator >
        and operator =

        also contains a few overloaded hashing functions
        if you create a mxList with a key of type integer
        you can use the tree as a hash table, using each
        index as a tree or bucket for duplicate hashes.

        (C) 2008 LostSideDead

*/

#include<iostream>
#include<cstdlib>

namespace mx
{

        template<typename Key, typename Value>
        class mxNode {
        public:
                mxNode() { left = right = 0; }
                mxNode( Key k, Value v )
                {
                        key = k;
                        value = v;
                        left = right = 0;
                }

                ~mxNode()
                {
                        if(left) delete left;
                        if(right) delete right;
                        left = 0;
                        right = 0;
                }

                Value value;
                Key   key;
                mxNode *left, *right;
        };


        template<typename Key, typename Value>
        class mxList {

        public:

                mxList() : head(0) { } // default constructor


                mxList( mxList<Key, Value> &lst ); // copy constructor

                ~mxList();

                mxNode<Key,Value> *addItem( Key k, Value val ); // addItem to list
                Value &operator[]( Key k ); // overloaded [] operator for random access if not found then insert
                Value *operator()( Key k ); // overloaded () operator for random access if not found return 0

                mxList<Key,Value> &operator=( mxList<Key,Value> &lst );
                mxList<Key,Value> &operator+=( mxList<Key,Value> &lst ) { concatList(lst); return *this; } // operator += concat list
                void concatList( mxList<Key,Value> &lst ); // concat List of Same Type
                void clear(); // clear Items
                void removeItem( Key k );

                void printNode( mxNode<Key,Value> *n); // print nodes to stdout from any point
                void printNode();


                mxNode<Key,Value> *root() const { return head; } // root node
                mxNode<Key,Value> *find( Key k ); // find by key


        protected:
                mxNode<Key,Value> *head;
                void catNode( mxNode<Key,Value> *n );
                void nocatNode( mxNode<Key,Value> *n, Key k );

        };


        template<typename Key, typename Value>
        mxList<Key,Value>::mxList( mxList<Key, Value> &lst ) : head(0)
        {
                clear();
                concatList( lst );

        }

        template<typename Key, typename Value>
        mxNode<Key,Value> *mxList<Key,Value>::addItem( Key k, Value value )
        {
                if(head == 0)
                {
                        head = new mxNode<Key,Value>(k,value);
                        return head;

                }

                mxNode<Key,Value> **ptr = &head, *p;

                while ( ( p = *ptr ) != 0 )
                {
                        if(p->key == k) return p;
                        if( (p->key > k) == 0 ) ptr = &p->left; else ptr = &p->right;
                }

                p = new mxNode<Key,Value>(k,value);
                *ptr = p;

                return p;
        }

        template<typename Key, typename Value>
        mxNode<Key,Value> *mxList<Key,Value>::find( Key k )
        {

                if(head == 0) return 0;

                mxNode<Key,Value> **ptr = &head, *p;

                while( ( p = *ptr ) != 0 )
                {

                        if(p->key == k) return p;
                        if((p->key > k) == 0) ptr = &p->left; else ptr = &p->right;
                }
                return 0;
        }

        template<typename Key, typename Value>
        mxList<Key, Value>::~mxList()
        {

                clear();

        }

        template<typename Key, typename Value>
        void mxList<Key,Value>::clear()
        {

                if(head)
                delete head;
                head = 0;

        }

        template<typename Key, typename Value>
        void mxList<Key,Value>::printNode( mxNode<Key,Value> *n)
        {


                if(n->left) printNode(n->left);
                if(n->right) printNode(n->right);

                std::cout << "Node: " << n->key << " : "  << n->value << "\n";
        }

        template<typename Key, typename Value>
        void mxList<Key,Value>::printNode()
        {

                if(root())
                printNode(root());

        }

        template<typename Key, typename Value>
        Value  &mxList<Key,Value>::operator[]( Key k )
        {

                mxNode<Key,Value> *node_ptr;

                node_ptr = this->find(k);

                Value v;
                if(node_ptr == 0) return addItem(k, v)->value;

                return node_ptr->value;
        }

        template<typename Key, typename Value>
        Value *mxList<Key,Value>::operator()( Key k )
        {
                mxNode<Key,Value> *node_ptr;
                node_ptr = this->find(k);
                if(node_ptr == 0) return 0;
                return &node_ptr->value;
        }

        template<typename Key, typename Value>
        void mxList<Key,Value>::concatList( mxList<Key,Value> &lst )
        {
                if(lst.root())
                catNode( lst.root() );
        }

        template<typename Key, typename Value>
        void mxList<Key,Value>::catNode( mxNode<Key,Value> *n )
        {

                if(n->left)  catNode(n->left);
                if(n->right) catNode(n->right);

                addItem(n->key, n->value);

        }

        template<typename Key, typename Value>
        void mxList<Key,Value>::nocatNode( mxNode<Key,Value> *n, Key k )
        {

                if(n->left) nocatNode(n->left, k);
                if(n->right) nocatNode(n->right, k);

                if(n->key != k)
                addItem(n->key, n->value);
        }

        template<typename Key, typename Value>
        void mxList<Key,Value>::removeItem ( Key k )
        {
                mxList<Key,Value> lst(*this);
                clear();

                if(lst.root())
                nocatNode( lst.root(), k);
        }


        template<typename Key, typename Value>
        mxList<Key,Value> &mxList<Key,Value>::operator=( mxList<Key,Value> &lst )
        {
                clear();
                concatList( lst );
                return *this;
        }


        // hashing function for Trees indexed by integers
        // tree[HashKey<std::string,unsigned int, 100>(str)] = value;
        template<typename Type, typename Accum, size_t HASH_SIZE>
        Accum  HashKey(Type t)
        {
                size_t i = 0;
                Accum h = Accum(), g = Accum();

                for(i = 0; t[i] != 0; i++)
                {
                        h = ( h << 4 ) + ( t[i] );
                        if( (g = h&0xF0000000) )
                        {
                                h = h ^ (g >> 24);
                                h = h ^ g;
                        }
                }

                return (h%HASH_SIZE);
        }

        // Another implementation of a hashing function ( taken from "Compilers Principals Techniques and Tools" aka the Dragon Book )
        template<size_t HASH_SIZE, typename InputIterator, typename Return>
        Return HashKey(InputIterator begin, InputIterator end)
        {
                Return h = Return(), g = Return();
                InputIterator i;
                for(i = begin; i != end; i++)
                {
                        h = ( h << 4 ) + ( *i );
                        if( (g = h&0xF0000000) )
                        {
                                h = h ^ (g >> 24);
                                h = h ^ g;
                        }
                }
                return (h%HASH_SIZE);
        }

        // overloaded non-template implementation of HashKey
        template<typename String>
        unsigned int HashKey(String key, unsigned int size)
        {

                unsigned int i = 0, h = 0, g = 0;
                for(i = 0;  key[i] != 0; i++)
                {
                        h = ( h << 4 ) + ( key[i] );
                        if( (g = h&0xF0000000) )
                        {
                                h = h ^ (g >> 24);
                                h = h ^ g;
                        }
                }
                return (h%size);
        }



}




#endif

---