Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members

TreeItem.h

Go to the documentation of this file.
00001 /*---------------------------------------------------------------------\
00002 |                                                                      |
00003 |                      __   __    ____ _____ ____                      |
00004 |                      \ \ / /_ _/ ___|_   _|___ \                     |
00005 |                       \ V / _` \___ \ | |   __) |                    |
00006 |                        | | (_| |___) || |  / __/                     |
00007 |                        |_|\__,_|____/ |_| |_____|                    |
00008 |                                                                      |
00009 |                            General Utilities                         |
00010 |                                                        (C) SuSE GmbH |
00011 \----------------------------------------------------------------------/
00012 
00013   File:         TreeItem.h
00014 
00015   Purpose:      Generic tree handling
00016 
00017   Author:       Stefan Hundhammer <sh@suse.de>
00018 
00019 /-*/
00020 
00021 #ifndef TreeItem_h
00022 #define TreeItem_h
00023 
00024 #include <string>
00025 
00026 
00027 
00028 
00036 template<class PAYLOAD> class TreeItem
00037 {
00038 public:
00039 
00045     TreeItem<PAYLOAD> ( const PAYLOAD &         val,
00046                         TreeItem<PAYLOAD> *     parent = 0 )
00047         : _value( val )
00048         , _parent( parent )
00049         , _next( 0 )
00050         , _firstChild( 0 )
00051     {
00052         if ( _parent )
00053             _parent->addChild( this );
00054     }
00055 
00056 
00057 protected:
00058 
00065     TreeItem<PAYLOAD> ( PAYLOAD                 val,
00066                         bool                    autoAddChild,
00067                         TreeItem<PAYLOAD> *     parent = 0 )
00068         : _value( val )
00069         , _parent( parent )
00070         , _next( 0 )
00071         , _firstChild( 0 )
00072     {
00073         if ( _parent && autoAddChild )
00074             _parent->addChild( this );
00075     }
00076 
00077     
00078 private:
00083     TreeItem<PAYLOAD>             ( const TreeItem<PAYLOAD> & ) {}
00084     TreeItem<PAYLOAD> & operator= ( const TreeItem<PAYLOAD> & ) {}
00085 
00086 
00087 public:
00088 
00093     virtual ~TreeItem<PAYLOAD> ()
00094     {
00095         TreeItem<PAYLOAD> * child = firstChild();
00096 
00097         while ( child )
00098         {
00099             TreeItem<PAYLOAD> * lastChild = child;
00100             child = child->next();
00101             delete lastChild;
00102         }
00103     }
00104 
00105 
00109     const PAYLOAD & value() const { return _value; }
00110 
00118     void setValue( PAYLOAD newValue ) { _value = newValue; }
00119 
00123     TreeItem<PAYLOAD> *         parent()        const { return _parent;         }
00124 
00128     TreeItem<PAYLOAD> *         next()          const { return _next;           }
00129 
00133     TreeItem<PAYLOAD> *         firstChild()    const { return _firstChild;     }
00134 
00138     void setParent( TreeItem<PAYLOAD> * newParent )     { _parent = newParent;  }
00139 
00143     void setNext( TreeItem<PAYLOAD> * newNext )         { _next = newNext;      }
00144 
00148     void setFirstChild( TreeItem<PAYLOAD> * newFirstChild )
00149         { _firstChild = newFirstChild; }
00150 
00151     
00161     void addChild( TreeItem<PAYLOAD> * newChild )
00162     {
00163         if ( newChild )
00164         {
00165             newChild->setNext( firstChild() );
00166             setFirstChild( newChild );
00167         }
00168     }
00169 
00170 
00175     bool isChildOf( const TreeItem<PAYLOAD> * maybeParent ) const
00176     {
00177         const TreeItem<PAYLOAD> * child = this;
00178         
00179         while ( child )
00180         {
00181             if ( child == maybeParent )
00182                 return true;
00183             child = child->parent();
00184         }
00185         return false;
00186     }
00187     
00188 
00189 protected:
00190 
00191     PAYLOAD             _value;
00192     TreeItem<PAYLOAD> * _parent;
00193     TreeItem<PAYLOAD> * _next;
00194     TreeItem<PAYLOAD> * _firstChild;
00195 };
00196 
00197 
00198 
00205 template<class PAYLOAD> class SortedTreeItem: public TreeItem<PAYLOAD>
00206 {
00207 public:
00208 
00213     SortedTreeItem<PAYLOAD>( PAYLOAD                    val,
00214                              SortedTreeItem<PAYLOAD> *  parentItem = 0 )
00215         : TreeItem<PAYLOAD> ( val, false, parentItem )
00216     {
00217         if ( parentItem )
00218         {
00219             // Hopefully we have a SortedTreeItem parent
00220             SortedTreeItem<PAYLOAD> * sortParent =
00221                 dynamic_cast<SortedTreeItem<PAYLOAD> *> ( parentItem );
00222 
00223             if ( sortParent )
00224                 sortParent->insertChildSorted( this );
00225             else // no SortedTreeItem parent - add unsorted
00226                 parentItem->addChild( this );
00227         }
00228     }
00229 
00230 
00234     virtual ~SortedTreeItem<PAYLOAD> () {}
00235 
00236     
00241     void insertChildSorted( SortedTreeItem<PAYLOAD> * newChild )
00242     {
00243         if ( ! newChild )
00244             return;
00245 
00246         if ( ! firstChild() ||
00247              newChild->value() < firstChild()->value() )
00248         {
00249             // Insert as first child
00250 
00251             newChild->setNext( firstChild() );
00252             setFirstChild( newChild );
00253         }
00254         else
00255         {
00256             // Search correct place to insert
00257 
00258             TreeItem<PAYLOAD> * child = firstChild();
00259 
00260             while ( child->next() &&
00261                     child->next()->value() < newChild->value() )
00262             {
00263                 child = child->next();
00264             }
00265 
00266 
00267             // Insert after 'child'
00268 
00269             newChild->setNext( child->next() );
00270             child->setNext( newChild );
00271         }
00272     }
00273 
00274 
00278     SortedTreeItem<PAYLOAD> *   parent()        const
00279         { return (SortedTreeItem<PAYLOAD> *) _parent;   }
00280 
00284     SortedTreeItem<PAYLOAD> *   next()          const
00285         { return (SortedTreeItem<PAYLOAD> *) _next;     }
00286 
00290     SortedTreeItem<PAYLOAD> *   firstChild()    const
00291         { return (SortedTreeItem<PAYLOAD> *) _firstChild; }
00292     
00293     
00294 private:
00295     
00300     SortedTreeItem<PAYLOAD>             ( const SortedTreeItem<PAYLOAD> & ) {}
00301     SortedTreeItem<PAYLOAD> & operator= ( const SortedTreeItem<PAYLOAD> & ) {}
00302 };
00303 
00304 
00305 
00310 template<class ITEM, class PAYLOAD> inline
00311 ITEM *
00312 findDirectChild( ITEM * item, PAYLOAD searchVal )
00313 {
00314     TreeItem<PAYLOAD> * child = item->firstChild();
00315 
00316     while ( child )
00317     {
00318         if ( child->value() == searchVal )
00319             return dynamic_cast<ITEM *> (child);
00320 
00321         child = child->next();
00322     }
00323 
00324     return 0;
00325 }
00326 
00327 
00328 
00329 #endif // TreeItem_h

Generated on Thu Feb 23 23:56:10 2006 for liby2util by doxygen 1.3.6