00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
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
00202 SortedTreeItem<PAYLOAD> * sortParent =
00203 dynamic_cast<SortedTreeItem<PAYLOAD> *> ( parentItem );
00204
00205 if ( sortParent )
00206 sortParent->insertChildSorted( this );
00207 else
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
00232
00233 newChild->setNext( firstChild() );
00234 setFirstChild( newChild );
00235 }
00236 else
00237 {
00238
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
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