TreeItem.h

/*
  Copyright (C) 2000-2012 Novell, Inc
  This library is free software; you can redistribute it and/or modify
  it under the terms of the GNU Lesser General Public License as
  published by the Free Software Foundation; either version 2.1 of the
  License, or (at your option) version 3.0 of the License. This library
  is distributed in the hope that it will be useful, but WITHOUT ANY
  WARRANTY; without even the implied warranty of MERCHANTABILITY or
  FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
  License for more details. You should have received a copy of the GNU
  Lesser General Public License along with this library; if not, write
  to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  Floor, Boston, MA 02110-1301 USA
*/


/*-/

  File:     TreeItem.h

  Author:   Stefan Hundhammer <shundhammer@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 );
    }
    }


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() );
        this->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> * ) TreeItem<PAYLOAD>::_parent; }

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

    SortedTreeItem<PAYLOAD> *   firstChild()    const
    { return ( SortedTreeItem<PAYLOAD> * ) TreeItem<PAYLOAD>::_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