00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef tnode_h
00020 #define tnode_h
00021
00022 #include <iosfwd>
00023
00025
00026
00027
00028
00029
00030 template <class n_value>
00031 class tnode {
00032
00033 tnode & operator=( const tnode & );
00034 tnode ( const tnode & );
00035
00036 protected:
00037
00038 typedef tnode<n_value> self;
00039
00040 mutable n_value val;
00041
00042 private:
00043
00044 self * parent;
00045 self * psibling;
00046 self * nsibling;
00047 self * fchild;
00048 self * lchild;
00049
00050 private:
00051
00052 bool DoReparentTo( self & p, self * s, const bool behind ) {
00053
00054 if ( &p == this || p.IsDescendantOf( this ) )
00055 return false;
00056
00057 Disconnect();
00058
00059 parent = &p;
00060 PreReparent();
00061
00062 if ( !s || s->parent != parent )
00063 s = behind ? parent->lchild : parent->fchild;
00064
00065 if ( !s ) {
00066
00067 parent->fchild = parent->lchild = this;
00068 }
00069 else {
00070 if ( behind ) {
00071 psibling = s;
00072 nsibling = s->nsibling;
00073 s->nsibling = this;
00074 if ( nsibling )
00075 nsibling->psibling = this;
00076 else
00077 parent->lchild = this;
00078 }
00079 else {
00080 psibling = s->psibling;
00081 nsibling = s;
00082 s->psibling = this;
00083 if ( psibling )
00084 psibling->nsibling = this;
00085 else
00086 parent->fchild = this;
00087 }
00088 }
00089
00090 PostReparent();
00091 return true;
00092 }
00093
00094 protected:
00095
00096 virtual void PreDisconnect() {}
00097 virtual void PostDisconnect() {}
00098 virtual void PreReparent() {}
00099 virtual void PostReparent() {}
00100
00101 public:
00102
00103 tnode( n_value v, self * p = 0, const bool behind = true )
00104 : val( v )
00105 , parent( 0 )
00106 , psibling( 0 )
00107 , nsibling( 0 )
00108 , fchild( 0 )
00109 , lchild( 0 )
00110 {
00111 if ( p )
00112 DoReparentTo( *p, 0, behind );
00113 }
00114
00115 tnode( n_value v, self & p, const bool behind = true )
00116 : val( v )
00117 , parent( 0 )
00118 , psibling( 0 )
00119 , nsibling( 0 )
00120 , fchild( 0 )
00121 , lchild( 0 )
00122 {
00123 DoReparentTo( p, 0, behind );
00124 }
00125
00126 tnode( n_value v, self & p, self & s, const bool behind = true )
00127 : val( v )
00128 , parent( 0 )
00129 , psibling( 0 )
00130 , nsibling( 0 )
00131 , fchild( 0 )
00132 , lchild( 0 )
00133 {
00134 DoReparentTo( p, &s, behind );
00135 }
00136
00137
00138 virtual ~tnode() {
00139 while ( fchild )
00140 fchild->Disconnect();
00141 Disconnect();
00142 }
00143
00144 public:
00145
00146 void Disconnect() {
00147 if ( !parent )
00148 return;
00149
00150 PreDisconnect();
00151
00152 if ( psibling )
00153 psibling->nsibling = nsibling;
00154 else
00155 parent->fchild = nsibling;
00156
00157 if ( nsibling )
00158 nsibling->psibling = psibling;
00159 else
00160 parent->lchild = psibling;
00161
00162 parent = psibling = nsibling = 0;
00163
00164 PostDisconnect();
00165 }
00166
00167 bool ReparentTo( self & p, const bool behind = true ) {
00168 return DoReparentTo( p, 0, behind );
00169 }
00170
00171 bool ReparentTo( self & p, self & s, const bool behind = true ) {
00172 return DoReparentTo( p, &s, behind );
00173 }
00174
00175
00176 public:
00177
00178 n_value & Value() const { return val; }
00179 n_value & operator()() const { return Value(); }
00180
00181 self * Parent() { return parent; }
00182 const self * Parent() const { return parent; }
00183 self * Psibling() { return psibling; }
00184 const self * Psibling() const { return psibling; }
00185 self * Nsibling() { return nsibling; }
00186 const self * Nsibling() const { return nsibling; }
00187 self * Fchild() { return fchild; }
00188 const self * Fchild() const { return fchild; }
00189 self * Lchild() { return lchild; }
00190 const self * Lchild() const { return lchild; }
00191
00192 bool HasParent() const { return parent; }
00193 bool HasSiblings() const { return psibling || nsibling; }
00194 bool HasChildren() const { return fchild; }
00195
00196 bool IsParentOf ( const self & c ) const { return c.parent == this; }
00197 bool IsSiblingOf( const self & s ) const { return parent && s.parent == parent; }
00198 bool IsChildOf ( const self & p ) const { return parent == &p; }
00199
00200 unsigned Depth() const {
00201 self * l = const_cast<self *>(this);
00202 unsigned level = 0;
00203 while( l->parent ) {
00204 l = l->parent;
00205 ++level;
00206 }
00207 return level;
00208 }
00209
00210
00211
00212 bool IsDescendantOf( const self & n ) const {
00213 for ( const self * l = parent; l; l = l->parent ) {
00214 if ( l == &n )
00215 return true;
00216 }
00217 return false;
00218 }
00219 bool IsDescendantOf( const self * n ) const {
00220 return( n && IsDescendantOf( *n ) );
00221 }
00222
00223 self & Top() {
00224 self * l = this;
00225 while( l->parent )
00226 l = l->parent;
00227 return *l;
00228 }
00229
00230 self * Next( const bool restart = false ) {
00231 if ( fchild )
00232 return fchild;
00233 self * l = this;
00234 while ( !l->nsibling ) {
00235 if ( l->parent )
00236 l = l->parent;
00237 else
00238 return restart ? l : 0;
00239 }
00240 return l->nsibling;
00241 }
00242
00243 self * Prev( const bool restart = false ) {
00244 if ( !psibling && parent )
00245 return parent;
00246 if ( !psibling && !restart )
00247 return 0;
00248
00249 self * l = psibling ? psibling : this;
00250 while ( l->lchild )
00251 l = l->lchild;
00252 return l;
00253 }
00254
00255 self * Next( self *& c, const bool restart = false ) {
00256 return c = Next( restart );
00257 }
00258 self * Prev( self *& c, const bool restart = false ) {
00259 return c = Prev( restart );
00260 }
00261
00262
00263
00264 const self & Top() const {
00265 return const_cast<self *>(this)->Top();
00266 }
00267 const self * Next( const bool restart = false ) const {
00268 return const_cast<self *>(this)->Next( restart );
00269 }
00270 const self * Prev( const bool restart = false ) const {
00271 return const_cast<self *>(this)->Prev( restart );
00272 }
00273 const self * Next( const self *& c, const bool restart = false ) const {
00274 return c = const_cast<self *>(this)->Next( restart );
00275 }
00276 const self * Prev( const self *& c, const bool restart = false ) const {
00277 return c = const_cast<self *>(this)->Prev( restart );
00278 }
00279
00280 };
00281
00283
00284 #endif // tnode_h