libyui
3.0.10
|
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