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
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
00220 SortedTreeItem<PAYLOAD> * sortParent =
00221 dynamic_cast<SortedTreeItem<PAYLOAD> *> ( parentItem );
00222
00223 if ( sortParent )
00224 sortParent->insertChildSorted( this );
00225 else
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
00250
00251 newChild->setNext( firstChild() );
00252 setFirstChild( newChild );
00253 }
00254 else
00255 {
00256
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
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