Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members

tnode.h

Go to the documentation of this file.
00001 /*---------------------------------------------------------------------\
00002 |                                                                      |
00003 |                      __   __    ____ _____ ____                      |
00004 |                      \ \ / /_ _/ ___|_   _|___ \                     |
00005 |                       \ V / _` \___ \ | |   __) |                    |
00006 |                        | | (_| |___) || |  / __/                     |
00007 |                        |_|\__,_|____/ |_| |_____|                    |
00008 |                                                                      |
00009 |                               core system                            |
00010 |                                                        (C) SuSE GmbH |
00011 \----------------------------------------------------------------------/
00012 
00013    File:       tnode.h
00014 
00015    Author:     Michael Andres <ma@suse.de>
00016    Maintainer: Michael Andres <ma@suse.de>
00017 
00018 /-*/
00019 #ifndef tnode_h
00020 #define tnode_h
00021 
00022 #include <iosfwd>
00023 
00025 //
00026 //      CLASS NAME : tnode
00027 //
00028 //      DESCRIPTION :
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 ) // using default sibling
00063         s = behind ? parent->lchild : parent->fchild;
00064 
00065       if ( !s ) {
00066         // no sibling, so we'll be the only child
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     // tree walk
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 ) // down first
00232         return fchild;
00233       self * l = this; // then next
00234       while ( !l->nsibling ) {
00235         if ( l->parent )
00236           l = l->parent;
00237         else
00238           return restart ? l : 0; // at Top()
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       // have psibling or at Top() and restart:
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     // const versions
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

Generated on Wed Sep 5 17:18:55 2007 for yast2-ncurses by doxygen 1.3.6