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

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 
00171 protected:
00172 
00173     PAYLOAD             _value;
00174     TreeItem<PAYLOAD> * _parent;
00175     TreeItem<PAYLOAD> * _next;
00176     TreeItem<PAYLOAD> * _firstChild;
00177 };
00178 
00179 
00180 
00187 template<class PAYLOAD> class SortedTreeItem: public TreeItem<PAYLOAD>
00188 {
00189 public:
00190 
00195     SortedTreeItem<PAYLOAD>( PAYLOAD                    val,
00196                              SortedTreeItem<PAYLOAD> *  parentItem = 0 )
00197         : TreeItem<PAYLOAD> ( val, false, parentItem )
00198     {
00199         if ( parentItem )
00200         {
00201             // Hopefully we have a SortedTreeItem parent
00202             SortedTreeItem<PAYLOAD> * sortParent =
00203                 dynamic_cast<SortedTreeItem<PAYLOAD> *> ( parentItem );
00204 
00205             if ( sortParent )
00206                 sortParent->insertChildSorted( this );
00207             else // no SortedTreeItem parent - add unsorted
00208                 parentItem->addChild( this );
00209         }
00210     }
00211 
00212 
00216     virtual ~SortedTreeItem<PAYLOAD> () {}
00217 
00218     
00223     void insertChildSorted( SortedTreeItem<PAYLOAD> * newChild )
00224     {
00225         if ( ! newChild )
00226             return;
00227 
00228         if ( ! firstChild() ||
00229              newChild->value() < firstChild()->value() )
00230         {
00231             // Insert as first child
00232 
00233             newChild->setNext( firstChild() );
00234             setFirstChild( newChild );
00235         }
00236         else
00237         {
00238             // Search correct place to insert
00239 
00240             TreeItem<PAYLOAD> * child = firstChild();
00241 
00242             while ( child->next() &&
00243                     child->next()->value() < newChild->value() )
00244             {
00245                 child = child->next();
00246             }
00247 
00248 
00249             // Insert after 'child'
00250 
00251             newChild->setNext( child->next() );
00252             child->setNext( newChild );
00253         }
00254     }
00255 
00256 
00260     SortedTreeItem<PAYLOAD> *   parent()        const
00261         { return ( SortedTreeItem<PAYLOAD> * ) _parent;         }
00262 
00266     SortedTreeItem<PAYLOAD> *   next()          const
00267         { return ( SortedTreeItem<PAYLOAD> * ) _next;   }
00268 
00272     SortedTreeItem<PAYLOAD> *   firstChild()    const
00273         { return ( SortedTreeItem<PAYLOAD> * ) _firstChild; }
00274     
00275     
00276 private:
00277     
00282     SortedTreeItem<PAYLOAD>             ( const SortedTreeItem<PAYLOAD> & ) {}
00283     SortedTreeItem<PAYLOAD> & operator= ( const SortedTreeItem<PAYLOAD> & ) {}
00284 };
00285 
00286 
00287 
00292 template<class ITEM, class PAYLOAD> inline
00293 ITEM *
00294 findDirectChild( ITEM * item, PAYLOAD searchVal )
00295 {
00296     TreeItem<PAYLOAD> * child = item->firstChild();
00297 
00298     while ( child )
00299     {
00300         if ( child->value() == searchVal )
00301             return dynamic_cast<ITEM *> ( child );
00302 
00303         child = child->next();
00304     }
00305 
00306     return 0;
00307 }
00308 
00309 
00310 
00311 #endif // TreeItem_h

Generated on Fri Nov 9 18:15:22 2007 for yast2-core by doxygen 1.3.6