libyui  3.0.10
/usr/src/RPM/BUILD/libyui-3.0.10/src/TreeItem.h
00001 /*
00002   Copyright (C) 2000-2012 Novell, Inc
00003   This library is free software; you can redistribute it and/or modify
00004   it under the terms of the GNU Lesser General Public License as
00005   published by the Free Software Foundation; either version 2.1 of the
00006   License, or (at your option) version 3.0 of the License. This library
00007   is distributed in the hope that it will be useful, but WITHOUT ANY
00008   WARRANTY; without even the implied warranty of MERCHANTABILITY or 
00009   FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
00010   License for more details. You should have received a copy of the GNU
00011   Lesser General Public License along with this library; if not, write
00012   to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
00013   Floor, Boston, MA 02110-1301 USA
00014 */
00015 
00016 
00017 /*-/
00018 
00019   File:         TreeItem.h
00020 
00021   Author:       Stefan Hundhammer <sh@suse.de>
00022 
00023 /-*/
00024 
00025 #ifndef TreeItem_h
00026 #define TreeItem_h
00027 
00028 #include <string>
00029 
00030 
00031 
00032 
00033 /**
00034  * Template class for tree items that can handle tree children in a
00035  * generic way - firstChild(), next() and parent(). Each item stores one value
00036  * of type 'PAYLOAD'.
00037  *
00038  * Class 'PAYLOAD' needs to provide operator=().
00039  **/
00040 template<class PAYLOAD> class TreeItem
00041 {
00042 public:
00043 
00044     /**
00045      * Constructor. Creates a new tree item with value "val" and inserts it
00046      * ( without maintaining any meaningful sort order! ) into the children list
00047      * of "parent".
00048      **/
00049     TreeItem<PAYLOAD> ( const PAYLOAD &         val,
00050                         TreeItem<PAYLOAD> *     parent = 0 )
00051         : _value( val )
00052         , _parent( parent )
00053         , _next(0)
00054         , _firstChild(0)
00055     {
00056         if ( _parent )
00057             _parent->addChild( this );
00058     }
00059 
00060 
00061 protected:
00062 
00063     /**
00064      * Constructor to be called for derived classes: Decide whether or not to
00065      * automatically insert this item into the parent's children list. Useful
00066      * for derived classes that want to maintain a specific sort order among
00067      * children.
00068      **/
00069     TreeItem<PAYLOAD> ( PAYLOAD                 val,
00070                         bool                    autoAddChild,
00071                         TreeItem<PAYLOAD> *     parent = 0 )
00072         : _value( val )
00073         , _parent( parent )
00074         , _next(0)
00075         , _firstChild(0)
00076     {
00077         if ( _parent && autoAddChild )
00078             _parent->addChild( this );
00079     }
00080 
00081 
00082 private:
00083     /**
00084      * Private ( i.e. disabled ) copy constructor and operator=()
00085      * - neither makes any sense with this class.
00086      **/
00087     TreeItem<PAYLOAD>             ( const TreeItem<PAYLOAD> & ) {}
00088     TreeItem<PAYLOAD> & operator= ( const TreeItem<PAYLOAD> & ) {}
00089 
00090 
00091 public:
00092 
00093     /**
00094      * Destructor. Takes care of children - they will be deleted along with
00095      * this item.
00096      **/
00097     virtual ~TreeItem<PAYLOAD> ()
00098     {
00099         TreeItem<PAYLOAD> * child = firstChild();
00100 
00101         while ( child )
00102         {
00103             TreeItem<PAYLOAD> * lastChild = child;
00104             child = child->next();
00105             delete lastChild;
00106         }
00107     }
00108 
00109 
00110     /**
00111      * Returns this item's value, the "payload".
00112      **/
00113     const PAYLOAD & value() const { return _value; }
00114 
00115     /**
00116      * Set this item's value, the "payload".
00117      *
00118      * If the sort order among children of one level is important, overwrite
00119      * this method and change the sort order according to the new value.
00120      * The template class itself never calls this.
00121      **/
00122     void setValue( PAYLOAD newValue ) { _value = newValue; }
00123 
00124     /**
00125      * Returns this item's parent or 0 if there is none.
00126      **/
00127     TreeItem<PAYLOAD> *         parent()        const { return _parent;         }
00128 
00129     /**
00130      * Returns this item's next sibling or 0 if there is none.
00131      **/
00132     TreeItem<PAYLOAD> *         next()          const { return _next;           }
00133 
00134     /**
00135      * Returns this item's first child or 0 if there is none.
00136      **/
00137     TreeItem<PAYLOAD> *         firstChild()    const { return _firstChild;     }
00138 
00139     /**
00140      * Sets this item's parent.
00141      **/
00142     void setParent( TreeItem<PAYLOAD> * newParent )     { _parent = newParent;  }
00143 
00144     /**
00145      * Sets this item's next sibling.
00146      **/
00147     void setNext( TreeItem<PAYLOAD> * newNext )         { _next = newNext;      }
00148 
00149     /**
00150      * Sets this item's first child.
00151      **/
00152     void setFirstChild( TreeItem<PAYLOAD> * newFirstChild )
00153         { _firstChild = newFirstChild; }
00154 
00155 
00156     /**
00157      * Add a child to the internal children list - usually called from within
00158      * the child's default constructor.
00159      *
00160      * This default method does not maintain any meaningful sorting order -
00161      * derived classes that require this might want to use the other
00162      * constructor ( with 'autoAddChild' set to 'false' ) take care of child
00163      * insertion themselves.
00164      **/
00165     void addChild( TreeItem<PAYLOAD> * newChild )
00166     {
00167         if ( newChild )
00168         {
00169             newChild->setNext( firstChild() );
00170             setFirstChild( newChild );
00171         }
00172     }
00173 
00174 
00175 protected:
00176 
00177     PAYLOAD             _value;
00178     TreeItem<PAYLOAD> * _parent;
00179     TreeItem<PAYLOAD> * _next;
00180     TreeItem<PAYLOAD> * _firstChild;
00181 };
00182 
00183 
00184 
00185 /**
00186  * Template class for tree items that maintain sort order.
00187  *
00188  * Class 'PAYLOAD' to provide operator<() in addition to what template
00189  *'TreeItem' requires.
00190  **/
00191 template<class PAYLOAD> class SortedTreeItem: public TreeItem<PAYLOAD>
00192 {
00193 public:
00194 
00195     /**
00196      * Constructor. Creates a new tree item with value "val" and inserts it in
00197      * ascending sort order into the children list of "parent".
00198      **/
00199     SortedTreeItem<PAYLOAD>( PAYLOAD                    val,
00200                              SortedTreeItem<PAYLOAD> *  parentItem = 0 )
00201         : TreeItem<PAYLOAD> ( val, false, parentItem )
00202     {
00203         if ( parentItem )
00204         {
00205             // Hopefully we have a SortedTreeItem parent
00206             SortedTreeItem<PAYLOAD> * sortParent =
00207                 dynamic_cast<SortedTreeItem<PAYLOAD> *> ( parentItem );
00208 
00209             if ( sortParent )
00210                 sortParent->insertChildSorted( this );
00211             else // no SortedTreeItem parent - add unsorted
00212                 parentItem->addChild( this );
00213         }
00214     }
00215 
00216 
00217     /**
00218      * Destructor.
00219      **/
00220     virtual ~SortedTreeItem<PAYLOAD> () {}
00221 
00222 
00223     /**
00224      * Insert a child into the internal children list in ascending sort order.
00225      * Called from the new child's constructor, thus 'public'.
00226      **/
00227     void insertChildSorted( SortedTreeItem<PAYLOAD> * newChild )
00228     {
00229         if ( ! newChild )
00230             return;
00231 
00232         if ( ! firstChild() ||
00233              newChild->value() < firstChild()->value() )
00234         {
00235             // Insert as first child
00236 
00237             newChild->setNext( firstChild() );
00238             this->setFirstChild( newChild );
00239         }
00240         else
00241         {
00242             // Search correct place to insert
00243 
00244             TreeItem<PAYLOAD> * child = firstChild();
00245 
00246             while ( child->next() &&
00247                     child->next()->value() < newChild->value() )
00248             {
00249                 child = child->next();
00250             }
00251 
00252 
00253             // Insert after 'child'
00254 
00255             newChild->setNext( child->next() );
00256             child->setNext( newChild );
00257         }
00258     }
00259 
00260 
00261     /**
00262      * Returns this item's parent or 0 if there is none.
00263      **/
00264     SortedTreeItem<PAYLOAD> *   parent()        const
00265         { return ( SortedTreeItem<PAYLOAD> * ) TreeItem<PAYLOAD>::_parent; }
00266 
00267     /**
00268      * Returns this item's next sibling or 0 if there is none.
00269      **/
00270     SortedTreeItem<PAYLOAD> *   next()          const
00271         { return ( SortedTreeItem<PAYLOAD> * ) TreeItem<PAYLOAD>::_next; }
00272 
00273     /**
00274      * Returns this item's first child or 0 if there is none.
00275      **/
00276     SortedTreeItem<PAYLOAD> *   firstChild()    const
00277         { return ( SortedTreeItem<PAYLOAD> * ) TreeItem<PAYLOAD>::_firstChild; }
00278 
00279 
00280 private:
00281 
00282     /**
00283      * Private ( i.e. disabled ) copy constructor and operator=()
00284      * - neither makes any sense with this class.
00285      **/
00286     SortedTreeItem<PAYLOAD>             ( const SortedTreeItem<PAYLOAD> & ) {}
00287     SortedTreeItem<PAYLOAD> & operator= ( const SortedTreeItem<PAYLOAD> & ) {}
00288 };
00289 
00290 
00291 
00292 /**
00293  * Find a direct child ( i.e., non-recursive ) with value "searchVal".
00294  * Returns 0 if there is no such child.
00295  **/
00296 template<class ITEM, class PAYLOAD> inline
00297 ITEM *
00298 findDirectChild( ITEM * item, PAYLOAD searchVal )
00299 {
00300     TreeItem<PAYLOAD> * child = item->firstChild();
00301 
00302     while ( child )
00303     {
00304         if ( child->value() == searchVal )
00305             return dynamic_cast<ITEM *> ( child );
00306 
00307         child = child->next();
00308     }
00309 
00310     return 0;
00311 }
00312 
00313 
00314 
00315 #endif // TreeItem_h
 All Classes Functions Variables Enumerations Friends