TreeItem.h

Go to the documentation of this file.

/*---------------------------------------------------------------------\
|                                                                      |
|                      __   __    ____ _____ ____                      |
|                      \ \ / /_ _/ ___|_   _|___ \                     |
|                       \ V / _` \___ \ | |   __) |                    |
|                        | | (_| |___) || |  / __/                     |
|                        |_|\__,_|____/ |_| |_____|                    |
|                                                                      |
|                            General Utilities                         |
|                                                        (C) SuSE GmbH |
\----------------------------------------------------------------------/

  File:         TreeItem.h

  Purpose:      Generic tree handling

  Author:       Stefan Hundhammer <sh@suse.de>

/-*/

#ifndef TreeItem_h
#define TreeItem_h

#include <string>




template<class PAYLOAD> class TreeItem
{
public:

    TreeItem<PAYLOAD> ( const PAYLOAD &         val,
                        TreeItem<PAYLOAD> *     parent = 0 )
        : _value( val )
        , _parent( parent )
        , _next( 0 )
        , _firstChild( 0 )
    {
        if ( _parent )
            _parent->addChild( this );
    }


protected:

    TreeItem<PAYLOAD> ( PAYLOAD                 val,
                        bool                    autoAddChild,
                        TreeItem<PAYLOAD> *     parent = 0 )
        : _value( val )
        , _parent( parent )
        , _next( 0 )
        , _firstChild( 0 )
    {
        if ( _parent && autoAddChild )
            _parent->addChild( this );
    }

    
private:
    TreeItem<PAYLOAD>             ( const TreeItem<PAYLOAD> & ) {}
    TreeItem<PAYLOAD> & operator= ( const TreeItem<PAYLOAD> & ) {}


public:

    virtual ~TreeItem<PAYLOAD> ()
    {
        TreeItem<PAYLOAD> * child = firstChild();

        while ( child )
        {
            TreeItem<PAYLOAD> * lastChild = child;
            child = child->next();
            delete lastChild;
        }
    }


    const PAYLOAD & value() const { return _value; }

    void setValue( PAYLOAD newValue ) { _value = newValue; }

    TreeItem<PAYLOAD> *         parent()        const { return _parent;         }

    TreeItem<PAYLOAD> *         next()          const { return _next;           }

    TreeItem<PAYLOAD> *         firstChild()    const { return _firstChild;     }

    void setParent( TreeItem<PAYLOAD> * newParent )     { _parent = newParent;  }

    void setNext( TreeItem<PAYLOAD> * newNext )         { _next = newNext;      }

    void setFirstChild( TreeItem<PAYLOAD> * newFirstChild )
        { _firstChild = newFirstChild; }

    
    void addChild( TreeItem<PAYLOAD> * newChild )
    {
        if ( newChild )
        {
            newChild->setNext( firstChild() );
            setFirstChild( newChild );
        }
    }


    bool isChildOf( const TreeItem<PAYLOAD> * maybeParent ) const
    {
        const TreeItem<PAYLOAD> * child = this;
        
        while ( child )
        {
            if ( child == maybeParent )
                return true;
            child = child->parent();
        }
        return false;
    }
    

protected:

    PAYLOAD             _value;
    TreeItem<PAYLOAD> * _parent;
    TreeItem<PAYLOAD> * _next;
    TreeItem<PAYLOAD> * _firstChild;
};



template<class PAYLOAD> class SortedTreeItem: public TreeItem<PAYLOAD>
{
public:

    SortedTreeItem<PAYLOAD>( PAYLOAD                    val,
                             SortedTreeItem<PAYLOAD> *  parentItem = 0 )
        : TreeItem<PAYLOAD> ( val, false, parentItem )
    {
        if ( parentItem )
        {
            // Hopefully we have a SortedTreeItem parent
            SortedTreeItem<PAYLOAD> * sortParent =
                dynamic_cast<SortedTreeItem<PAYLOAD> *> ( parentItem );

            if ( sortParent )
                sortParent->insertChildSorted( this );
            else // no SortedTreeItem parent - add unsorted
                parentItem->addChild( this );
        }
    }


    virtual ~SortedTreeItem<PAYLOAD> () {}

    
    void insertChildSorted( SortedTreeItem<PAYLOAD> * newChild )
    {
        if ( ! newChild )
            return;

        if ( ! firstChild() ||
             newChild->value() < firstChild()->value() )
        {
            // Insert as first child

            newChild->setNext( firstChild() );
            setFirstChild( newChild );
        }
        else
        {
            // Search correct place to insert

            TreeItem<PAYLOAD> * child = firstChild();

            while ( child->next() &&
                    child->next()->value() < newChild->value() )
            {
                child = child->next();
            }


            // Insert after 'child'

            newChild->setNext( child->next() );
            child->setNext( newChild );
        }
    }


    SortedTreeItem<PAYLOAD> *   parent()        const
        { return (SortedTreeItem<PAYLOAD> *) this->_parent;     }

    SortedTreeItem<PAYLOAD> *   next()          const
        { return (SortedTreeItem<PAYLOAD> *) this->_next;       }

    SortedTreeItem<PAYLOAD> *   firstChild()    const
        { return (SortedTreeItem<PAYLOAD> *) this->_firstChild; }
    
    
private:
    
    SortedTreeItem<PAYLOAD>             ( const SortedTreeItem<PAYLOAD> & ) {}
    SortedTreeItem<PAYLOAD> & operator= ( const SortedTreeItem<PAYLOAD> & ) {}
};



template<class ITEM, class PAYLOAD> inline
ITEM *
findDirectChild( ITEM * item, PAYLOAD searchVal )
{
    TreeItem<PAYLOAD> * child = item->firstChild();

    while ( child )
    {
        if ( child->value() == searchVal )
            return dynamic_cast<ITEM *> (child);

        child = child->next();
    }

    return 0;
}



#endif // TreeItem_h