Tree.h

Go to the documentation of this file.

#ifndef _H_TREE
#define _H_TREE
#include <vector>

//#define _INDEX

template< typename stored_type, typename tree_type >
class Tree {
  protected:

        vector< stored_type > elements;

        vector< tree_type* > children;

#ifdef _INDEX
//TODO find a way to traverse the tree without using this int and the changed bool!
        int _id;
#endif

        tree_type *parent;

#ifdef _INDEX

        bool changed;

        tree_type *getNext( const int id_at );
        
        int index( int id_at );
#endif

public:

        virtual ~Tree() {}

        Tree();

        Tree( tree_type *par );

#ifdef _INDEX

        void index();
#endif

        tree_type *getRoot();
        
        int getDepth() const;
        
        int getHeight() const;

        bool isRoot() const { return ( parent == 0); }

        bool isEmpty() { return ( elements.size() == 0 && children.size() == 0 ); }
        
        bool isLeaf() const { return ( children.size() == 0 ); }
        
        tree_type getChild( int index );

        stored_type getElement( unsigned int index );
        
        //virtual:
        
        virtual tree_type *insert(stored_type newElement) = 0;
        
        template < class InputIterator >
        void insertElements( InputIterator begin,  InputIterator end ) { for ( ; begin!=end; ++begin ) insert( *begin ); }

        virtual tree_type *remove(stored_type element) = 0;
        
        virtual tree_type *search(stored_type toSearch) = 0;

#ifdef _INDEX

        class Iterator : public std::iterator<std::forward_iterator_tag, stored_type> {
        protected:
        
                Tree* _current;
                
                int id_at;

        public:

                Iterator( Tree< stored_type, tree_type > *current );
        
        //operators:
        
                Iterator& operator=( const Iterator& other ) {
                        _current = other._current;
                        id_at = other.id_at;
                        return (*this);
                }
                
                bool operator==( const Iterator& other ) {
                        return ( _current == other._current && id_at = other.id_at);
                }

                bool operator!=( const Iterator& other ) {
                        return ( _current != other._current || id_at != other.id_at );
                }

                Iterator& operator++() {
                        _current = _current->getNext( id_at );
                        while ( ! _current->isEmpty() )
                                _current = _current->getNext( id_at );
                        if ( _current != 0)
                                id_at = _current->_id;
                        else
                                id_at = 0;
                        return (*this);
                }

                stored_type operator*() {
                        return ( _current->getElement( id_at ) );
                }
                
                //the below doesnt work..
                //const stored_type* operator->() const {
                //      return _current->getElement( id_at ).operator ->();
        };
        
        Iterator begin() { index(); return Iterator( this ); }
        
        Iterator end() { return Iterator( 0 ); }
#endif

        //debug funcs
        void printTreeToStdOut( const int x, const void* par ) const;

};


//debug funcs:
template< typename stored_type, typename tree_type >
void Tree< stored_type, tree_type >::printTreeToStdOut( const int x, const void* par ) const {
        for( int i=0; i<x; i++ )
                cout << " ";
        cout << "|";
        if ( parent != par )
                cout << "*";
        else
                cout << "-";
        cout << endl;
        if ( isLeaf() )
                return;
        for( unsigned int i=0; i<children.size(); i++ ) {
                children[i]->printTreeToStdOut( x+1, this );
        }
}


#ifdef _INDEX
/*****************************************************
 *           ITERATOR SUBCLASS -- PUBLIC             *
 *****************************************************/

template< typename stored_type, typename tree_type >
Tree< stored_type, tree_type >::Iterator::Iterator( Tree< stored_type, tree_type > *current ) {
        _current = current;
        if ( _current != 0 )
                id_at = current->_id;
        else
                id_at = 0;
}
#endif


/*****************************************************
 *                       PUBLIC                      *
 *****************************************************/
 
        
template< typename stored_type, typename tree_type >
Tree< stored_type, tree_type >::Tree() {
#ifdef _INDEX
        _id = 0;
#endif
        parent = 0;
#ifdef _INDEX
        changed = true;
        index();
#endif
}

template< typename stored_type, typename tree_type >
Tree< stored_type, tree_type >::Tree( tree_type *par ) {
#ifdef _INDEX
        _id = 0;
#endif
        parent = par;
#ifdef _INDEX
        changed = true;
        index();
#endif
}

#ifdef _INDEX
template< typename stored_type, typename tree_type >
void Tree< stored_type, tree_type >::index() {
        index(1);
        changed = false;
}
#endif

template< typename stored_type, typename tree_type >
tree_type* Tree< stored_type, tree_type >::getRoot() {
        if ( !isRoot() )
                return parent->getRoot();
        else
                return this;
}

template< typename stored_type, typename tree_type >
int Tree< stored_type, tree_type >::getDepth() const {
        if ( isRoot() )
                return 0;
        else
                return ( 1 + parent->getDepth() );
}

template< typename stored_type, typename tree_type >
int Tree< stored_type, tree_type >::getHeight() const {
        if ( isLeaf() )
                return getDepth();
        else {
                int ret = children[0]->getHeight();
                for ( unsigned int i = 1; i<children.size(); i++ ) {
                        int curHeight = children[i]->getHeight();
                        if ( curHeight > ret )
                                ret = curHeight;
                        }
                return ret;
        }
}

template< typename stored_type, typename tree_type >
tree_type Tree< stored_type, tree_type >::getChild( int index ) {
        if ( index >= children.size() ) {
                cerr << "Error: index too large in Tree::getChild()!" << endl;
                exit(1);
        }
        
        return children[index];
}

template< typename stored_type, typename tree_type >
stored_type Tree< stored_type, tree_type >::getElement( unsigned int index ) {
        if ( index >= elements.size() ) {
                cerr << "Error: index too large in Tree::getChild()!" << endl;
                exit(1);
        }
        
        return elements[index];
}



/*****************************************************
 *                      PROTECTED                    *
 *****************************************************/

#ifdef _INDEX
template< typename stored_type, typename tree_type >
tree_type* Tree< stored_type, tree_type >::getNext( const int id_at ) {
        for ( unsigned int i=0; i<children.size(); i++ ) {
                if ( children[i]->_id > id_at )
                        return children[_id];
        }
        if ( isRoot() )
                return 0; //end element
        else
                return parent->getNext( id_at );
}

template< typename stored_type, typename tree_type >
int Tree< stored_type, tree_type >::index( int id_at ) {
        _id = id_at;
        int max = _id;
        for ( unsigned int i=0; i<children.size(); i++ ) {
                max = children[i]->index( max + 1 );
        }
        return max;
}
#endif

#endif

---