libyui-ncurses
2.44.1
|
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: tnode.h 00020 00021 Author: Michael Andres <ma@suse.de> 00022 00023 /-*/ 00024 00025 #ifndef tnode_h 00026 #define tnode_h 00027 00028 #include <iosfwd> 00029 00030 00031 template <class n_value> class tnode 00032 { 00033 00034 tnode & operator=( const tnode & ); 00035 tnode( const tnode & ); 00036 00037 protected: 00038 00039 typedef tnode<n_value> self; 00040 00041 mutable n_value val; 00042 00043 private: 00044 00045 self * parent; 00046 self * psibling; 00047 self * nsibling; 00048 self * fchild; 00049 self * lchild; 00050 00051 00052 bool DoReparentTo( self & p, self * s, const bool behind ) 00053 { 00054 00055 if ( &p == this || p.IsDescendantOf( this ) ) 00056 return false; 00057 00058 Disconnect(); 00059 00060 parent = &p; 00061 00062 PreReparent(); 00063 00064 if ( !s || s->parent != parent ) // using default sibling 00065 s = behind ? parent->lchild : parent->fchild; 00066 00067 if ( !s ) 00068 { 00069 // no sibling, so we'll be the only child 00070 parent->fchild = parent->lchild = this; 00071 } 00072 else 00073 { 00074 if ( behind ) 00075 { 00076 psibling = s; 00077 nsibling = s->nsibling; 00078 s->nsibling = this; 00079 00080 if ( nsibling ) 00081 nsibling->psibling = this; 00082 else 00083 parent->lchild = this; 00084 } 00085 else 00086 { 00087 psibling = s->psibling; 00088 nsibling = s; 00089 s->psibling = this; 00090 00091 if ( psibling ) 00092 psibling->nsibling = this; 00093 else 00094 parent->fchild = this; 00095 } 00096 } 00097 00098 PostReparent(); 00099 00100 return true; 00101 } 00102 00103 protected: 00104 00105 virtual void PreDisconnect() {} 00106 00107 virtual void PostDisconnect() {} 00108 00109 virtual void PreReparent() {} 00110 00111 virtual void PostReparent() {} 00112 00113 public: 00114 00115 tnode( n_value v, self * p = 0, const bool behind = true ) 00116 : val( v ) 00117 , parent( 0 ) 00118 , psibling( 0 ) 00119 , nsibling( 0 ) 00120 , fchild( 0 ) 00121 , lchild( 0 ) 00122 { 00123 if ( p ) 00124 DoReparentTo( *p, 0, behind ); 00125 } 00126 00127 tnode( n_value v, self & p, const bool behind = true ) 00128 : val( v ) 00129 , parent( 0 ) 00130 , psibling( 0 ) 00131 , nsibling( 0 ) 00132 , fchild( 0 ) 00133 , lchild( 0 ) 00134 { 00135 DoReparentTo( p, 0, behind ); 00136 } 00137 00138 tnode( n_value v, self & p, self & s, const bool behind = true ) 00139 : val( v ) 00140 , parent( 0 ) 00141 , psibling( 0 ) 00142 , nsibling( 0 ) 00143 , fchild( 0 ) 00144 , lchild( 0 ) 00145 { 00146 DoReparentTo( p, &s, behind ); 00147 } 00148 00149 00150 virtual ~tnode() 00151 { 00152 while ( fchild ) 00153 fchild->Disconnect(); 00154 00155 Disconnect(); 00156 } 00157 00158 00159 void Disconnect() 00160 { 00161 if ( !parent ) 00162 return; 00163 00164 PreDisconnect(); 00165 00166 if ( psibling ) 00167 psibling->nsibling = nsibling; 00168 else 00169 parent->fchild = nsibling; 00170 00171 if ( nsibling ) 00172 nsibling->psibling = psibling; 00173 else 00174 parent->lchild = psibling; 00175 00176 parent = psibling = nsibling = 0; 00177 00178 PostDisconnect(); 00179 } 00180 00181 bool ReparentTo( self & p, const bool behind = true ) 00182 { 00183 return DoReparentTo( p, 0, behind ); 00184 } 00185 00186 bool ReparentTo( self & p, self & s, const bool behind = true ) 00187 { 00188 return DoReparentTo( p, &s, behind ); 00189 } 00190 00191 00192 n_value & Value() const { return val; } 00193 00194 n_value & operator()() const { return Value(); } 00195 00196 self * Parent() { return parent; } 00197 00198 const self * Parent() const { return parent; } 00199 00200 self * Psibling() { return psibling; } 00201 00202 const self * Psibling() const { return psibling; } 00203 00204 self * Nsibling() { return nsibling; } 00205 00206 const self * Nsibling() const { return nsibling; } 00207 00208 self * Fchild() { return fchild; } 00209 00210 const self * Fchild() const { return fchild; } 00211 00212 self * Lchild() { return lchild; } 00213 00214 const self * Lchild() const { return lchild; } 00215 00216 bool HasParent() const { return parent; } 00217 00218 bool HasSiblings() const { return psibling || nsibling; } 00219 00220 bool HasChildren() const { return fchild; } 00221 00222 bool IsParentOf( const self & c ) const { return c.parent == this; } 00223 00224 bool IsSiblingOf( const self & s ) const { return parent && s.parent == parent; } 00225 00226 bool IsChildOf( const self & p ) const { return parent == &p; } 00227 00228 unsigned Depth() const 00229 { 00230 self * l = const_cast<self *>( this ); 00231 unsigned level = 0; 00232 00233 while ( l->parent ) 00234 { 00235 l = l->parent; 00236 ++level; 00237 } 00238 00239 return level; 00240 } 00241 00242 // tree walk 00243 00244 bool IsDescendantOf( const self & n ) const 00245 { 00246 for ( const self * l = parent; l; l = l->parent ) 00247 { 00248 if ( l == &n ) 00249 return true; 00250 } 00251 00252 return false; 00253 } 00254 00255 bool IsDescendantOf( const self * n ) const 00256 { 00257 return( n && IsDescendantOf( *n ) ); 00258 } 00259 00260 self & Top() 00261 { 00262 self * l = this; 00263 00264 while ( l->parent ) 00265 l = l->parent; 00266 00267 return *l; 00268 } 00269 00270 self * Next( const bool restart = false ) 00271 { 00272 if ( fchild ) // down first 00273 return fchild; 00274 00275 self * l = this; // then next 00276 00277 while ( !l->nsibling ) 00278 { 00279 if ( l->parent ) 00280 l = l->parent; 00281 else 00282 return restart ? l : 0; // at Top() 00283 } 00284 00285 return l->nsibling; 00286 } 00287 00288 self * Prev( const bool restart = false ) 00289 { 00290 if ( !psibling && parent ) 00291 return parent; 00292 00293 if ( !psibling && !restart ) 00294 return 0; 00295 00296 // have psibling or at Top() and restart: 00297 self * l = psibling ? psibling : this; 00298 00299 while ( l->lchild ) 00300 l = l->lchild; 00301 00302 return l; 00303 } 00304 00305 self * Next( self *& c, const bool restart = false ) 00306 { 00307 return c = Next( restart ); 00308 } 00309 00310 self * Prev( self *& c, const bool restart = false ) 00311 { 00312 return c = Prev( restart ); 00313 } 00314 00315 // const versions 00316 00317 const self & Top() const 00318 { 00319 return const_cast<self *>( this )->Top(); 00320 } 00321 00322 const self * Next( const bool restart = false ) const 00323 { 00324 return const_cast<self *>( this )->Next( restart ); 00325 } 00326 00327 const self * Prev( const bool restart = false ) const 00328 { 00329 return const_cast<self *>( this )->Prev( restart ); 00330 } 00331 00332 const self * Next( const self *& c, const bool restart = false ) const 00333 { 00334 return c = const_cast<self *>( this )->Next( restart ); 00335 } 00336 00337 const self * Prev( const self *& c, const bool restart = false ) const 00338 { 00339 return c = const_cast<self *>( this )->Prev( restart ); 00340 } 00341 00342 }; 00343 00344 00345 #endif // tnode_h