/data/gitorious.org/libyui/libyui-master/src/TreeItem.h

/**************************************************************************
Copyright (C) 2000 - 2010 Novell, Inc.
All Rights Reserved.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program 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 General Public License for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

**************************************************************************/



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

  File:         TreeItem.h

  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 );
        }
    }


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> * ) 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