libyui-ncurses  2.44.1
/usr/src/RPM/BUILD/libyui-ncurses-2.44.1/src/tnode.h
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
 All Classes Functions Variables