nux-1.16.0
NodeItem.cpp
00001 /*
00002  * Copyright 2010 Inalogic® Inc.
00003  *
00004  * This program is free software: you can redistribute it and/or modify it
00005  * under the terms of the GNU Lesser General Public License, as
00006  * published by the  Free Software Foundation; either version 2.1 or 3.0
00007  * of the License.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranties of
00011  * MERCHANTABILITY, SATISFACTORY QUALITY or FITNESS FOR A PARTICULAR
00012  * PURPOSE.  See the applicable version of the GNU Lesser General Public
00013  * License for more details.
00014  *
00015  * You should have received a copy of both the GNU Lesser General Public
00016  * License along with this program. If not, see <http://www.gnu.org/licenses/>
00017  *
00018  * Authored by: Jay Taoko <jaytaoko@inalogic.com>
00019  *
00020  */
00021 
00022 
00023 #ifndef NUX_STANDALONE
00024 #include "Nux.h"
00025 #endif
00026 
00027 #include "NodeItem.h"
00028 
00029 namespace nux
00030 {
00031 
00032 //                            Node0
00033 //                              |
00034 //                   Head0->  Node <-> Node <-> Node <-> Node <-> Node <-> Node <-> Node  <- Tail0
00035 //                                                         |
00036 //                                                       Node <-> Node <-> Node <-> Node
00037 //
00038 //  <-> : siblings
00039 //  |   : parent child relationship
00040 //
00041 //
00042 
00043 #ifndef NUX_STANDALONE
00044   NUX_IMPLEMENT_ROOT_OBJECT_TYPE (NodeItem);
00045 #endif
00046 
00047 
00048 
00049   NodeItem::NodeItem()
00050   {
00051     parent_node = child_head = child_tail = next_sibling = prev_sibling = 0;
00052   };
00053 
00054   NodeItem::~NodeItem()
00055   {
00056     parent_node = child_head = child_tail = next_sibling = prev_sibling = 0;
00057   };
00058 
00059   /********************************************* NodeItem::first() *******/
00060   /* Returns first sibling in 'this' node's sibling list                  */
00061 
00062   NodeItem   *NodeItem::FirstSibling ( void )
00063   {
00064     if ( parent_node == 0 )
00065       return this;           /* root node has no siblings */
00066     else
00067       return parent_node->child_head;
00068   }
00069 
00070   /********************************************* NodeItem::last() *******/
00071   /* Returns last sibling in 'this' node's sibling list                  */
00072 
00073   NodeItem   *NodeItem::LastSibling ( void )
00074   {
00075     if ( parent_node == 0 )
00076       return this;            /* root node has no siblings */
00077     else
00078       return parent_node->child_tail;
00079   }
00080 
00081   /******************************************** NodeItem::next() ********/
00082   /* Returns next sibling in 'this' node's sibling list                  */
00083 
00084   const NodeItem    *NodeItem::Next ( void ) const
00085   {
00086     return next_sibling;
00087   }
00088 
00089 
00090   /******************************************** NodeItem::prev() ********/
00091   /* Returns prev sibling in 'this' node's sibling list                  */
00092 
00093   const NodeItem    *NodeItem::Prev ( void ) const
00094   {
00095     return prev_sibling;
00096   }
00097 
00098   void NodeItem::PushChildFront ( NodeItem *child )
00099   {
00100     if (child)
00101       child->Unlink();
00102     else
00103       return;
00104 
00105     NodeItem *first = FirstChildNode();
00106     NodeItem *last = LastChildNode();
00107 
00108     if ( (last == 0) && (first == 0) )
00109     {
00110       child_head = child;
00111       child_tail = child;
00112       child->next_sibling = 0;
00113       child->prev_sibling = 0;
00114       child->parent_node = this;
00115     }
00116     else if ( (last != 0) && (first != 0) )
00117     {
00118       first->prev_sibling = child;
00119       child->next_sibling = first;
00120       child->prev_sibling = 0;
00121       child_head = child;
00122       child->parent_node = this;
00123     }
00124     else
00125     {
00126 #ifndef NUX_STANDALONE
00127       nuxAssertMsg (0, TEXT ("NodeItem::add_child_first: This should not happen") );
00128 #endif
00129     }
00130   }
00131 
00132   void NodeItem::PushChildBack ( NodeItem *child ) // Push_Child_Back
00133   {
00134     if (child)
00135       child->Unlink();
00136     else
00137       return;
00138 
00139     NodeItem *first = FirstChildNode();
00140     NodeItem *last = LastChildNode();
00141 
00142     if ( (last == 0) && (first == 0) )
00143     {
00144       child_head = child;
00145       child_tail = child;
00146       child->next_sibling = 0;
00147       child->prev_sibling = 0;
00148       child->parent_node = this;
00149     }
00150     else if ( (last != 0) && (first != 0) )
00151     {
00152       last->next_sibling = child;
00153       child->prev_sibling = last;
00154       child->next_sibling = 0;
00155       child_tail = child;
00156       child->parent_node = this;
00157     }
00158     else
00159     {
00160 #ifndef NUX_STANDALONE
00161       nuxAssertMsg (0, TEXT ("NodeItem::add_child_last: This should not happen") );
00162 #endif
00163     }
00164   }
00165 
00166   void NodeItem::AddNextSibling ( NodeItem *sibling )
00167   {
00168     if (sibling)
00169       sibling->Unlink();
00170 
00171     sibling->next_sibling = this->next_sibling;
00172 
00173     if (this->next_sibling)
00174       this->next_sibling->prev_sibling = sibling;
00175 
00176     sibling->prev_sibling = this;
00177     this->next_sibling = sibling;
00178     sibling->parent_node = this->Parent();
00179   }
00180 
00181   void NodeItem::AddPrevSibling ( NodeItem *sibling )
00182   {
00183     if (sibling)
00184       sibling->Unlink();
00185 
00186     sibling->prev_sibling = this->prev_sibling;
00187 
00188     if (this->prev_sibling)
00189       this->prev_sibling->next_sibling = sibling;
00190 
00191     sibling->next_sibling = this;
00192     this->prev_sibling = sibling;
00193     sibling->parent_node = this->Parent();
00194   }
00195 
00196   /*************************** NodeItem::link_this_to_parent_last() *******/
00197   /* Links as last child of parent                                         */
00198 
00199   void   NodeItem::link_this_to_parent_last ( NodeItem *new_parent )
00200   {
00201     if (new_parent)
00202     {
00203       // First Unlink this
00204       Unlink();
00205     }
00206     else
00207       return;
00208 
00209     if ( new_parent->child_tail == 0 )
00210     {
00211       /* parent has no children */
00212       new_parent->child_head              = this;
00213       new_parent->child_tail              = this;
00214       this->parent_node                   = new_parent;
00215       this->prev_sibling                  = 0;
00216       this->next_sibling                  = 0;
00217     }
00218     else
00219     {
00220       /* parent has children */
00221       new_parent->child_tail->next_sibling = this;
00222       this->prev_sibling                   = new_parent->child_tail;
00223       new_parent->child_tail               = this;
00224       this->parent_node                    = new_parent;
00225       this->next_sibling                   = 0;
00226     }
00227   }
00228 
00229 
00230   /*************************** NodeItem::link_this_to_parent_first() *******/
00231   /* Links as first child of parent                                         */
00232 
00233   void   NodeItem::link_this_to_parent_first ( NodeItem *new_parent )
00234   {
00235     if (new_parent)
00236     {
00237       // First Unlink this
00238       Unlink();
00239     }
00240     else
00241       return;
00242 
00243     if ( new_parent->child_head == 0 )
00244     {
00245       /* parent has no children */
00246       new_parent->child_head               = this;
00247       new_parent->child_tail               = this;
00248       this->parent_node                    = new_parent;
00249       this->prev_sibling                   = 0;
00250       this->next_sibling                   = 0;
00251     }
00252     else
00253     {
00254       /* parent has children */
00255       new_parent->child_head->prev_sibling = this;
00256       this->next_sibling                   = new_parent->child_head;
00257       new_parent->child_head               = this;
00258       this->parent_node                    = new_parent;
00259       this->prev_sibling                   = 0;
00260     }
00261   }
00262 
00263   /**************************** NodeItem::link_this_to_sibling_next() *****/
00264 
00265   void   NodeItem::link_this_to_sibling_next ( NodeItem *sibling )
00266   {
00267     if (sibling)
00268     {
00269       // First Unlink
00270       Unlink();
00271     }
00272     else
00273       return;
00274 
00275     if ( sibling->next_sibling == 0 )
00276     {
00277       /* node has no next sibling */
00278       sibling->next_sibling   = this;
00279       this->prev_sibling      = sibling;
00280       this->next_sibling      = 0;
00281 
00282       /* This was the parent's last child, so update that as well */
00283       if ( sibling->parent_node  != 0 )
00284       {
00285         sibling->parent_node->child_tail = this;
00286       }
00287     }
00288     else
00289     {
00290       /* node already has a next sibling */
00291       sibling->next_sibling->prev_sibling = this;
00292       this->next_sibling                  = sibling->next_sibling;
00293       sibling->next_sibling               = this;
00294       this->prev_sibling                  = sibling;
00295     }
00296 
00297     this->parent_node = sibling->parent_node;
00298   }
00299 
00300 
00301   /**************************** NodeItem::link_this_to_sibling_prev() *****/
00302 
00303   void   NodeItem::link_this_to_sibling_prev ( NodeItem *sibling )
00304   {
00305     if (sibling)
00306     {
00307       // First Unlink
00308       Unlink();
00309     }
00310     else
00311       return;
00312 
00313     if ( sibling->prev_sibling == 0 )
00314     {
00315       /* node has no prev sibling */
00316       sibling->prev_sibling   = this;
00317       this->next_sibling      = sibling;
00318       this->prev_sibling      = 0;
00319 
00320       /* This was the parent's first child, so update that as well */
00321       if ( sibling->parent_node  != 0 )
00322       {
00323         sibling->parent_node->child_head = this;
00324       }
00325     }
00326     else
00327     {
00328       /* node already has a prev sibling */
00329       sibling->prev_sibling->next_sibling = this;
00330       this->prev_sibling                  = sibling->prev_sibling;
00331       sibling->prev_sibling               = this;
00332       this->next_sibling                  = sibling;
00333     }
00334 
00335     this->parent_node = sibling->parent_node;
00336   }
00337 
00338 
00340   void   NodeItem::Unlink ( void )
00341   {
00342     /* Unlink from prev sibling */
00343     if ( this->prev_sibling != 0 )
00344     {
00345       this->prev_sibling->next_sibling = this->next_sibling;
00346     }
00347     else
00348     {
00349       /* No prev sibling: this was parent's first child */
00350       if (this->parent_node)
00351         this->parent_node->child_head = this->next_sibling;
00352     }
00353 
00354     /* Unlink from next sibling */
00355     if ( this->next_sibling != 0 )
00356     {
00357       this->next_sibling->prev_sibling = this->prev_sibling;
00358     }
00359     else
00360     {
00361       /* No next sibling: this was parent's last child */
00362       if (this->parent_node)
00363         this->parent_node->child_tail = this->prev_sibling;
00364     }
00365 
00366     this->parent_node  = 0;
00367     this->next_sibling = 0;
00368     this->prev_sibling = 0;
00369     //this->child_head   = 0;
00370     //this->child_tail   = 0;
00371   }
00372 
00374   void   NodeItem::Unlink ( NodeItem *child )
00375   {
00376     if (!FindNode (child) )
00377       return;
00378 
00379     NodeItem *prev = child->Prev();
00380     NodeItem *next = child->Next();
00381 
00382     if (prev)
00383     {
00384       prev->next_sibling = next;
00385     }
00386     else
00387     {
00388       // child is the first child
00389       NodeItem *parent = child->Parent();
00390 
00391       if (parent)
00392         parent->child_head = next;
00393     }
00394 
00395     if (next)
00396     {
00397       next->prev_sibling = prev;
00398     }
00399     else
00400     {
00401       // child is the last child
00402       NodeItem *parent = child->Parent();
00403 
00404       if (parent)
00405         parent->child_tail = prev;
00406     }
00407 
00408     if ( (next == 0) && (prev == 0) )
00409     {
00410       NodeItem *parent = child->Parent();
00411 
00412       if (parent)
00413       {
00414         parent->child_head = 0;
00415         parent->child_tail = 0;
00416       }
00417     }
00418 
00419     child->parent_node = 0;
00420     child->prev_sibling = 0;
00421     child->next_sibling = 0;
00422   }
00423 
00424   bool NodeItem::FindNode (NodeItem *node)
00425   {
00426     if (node == 0)
00427       return false;
00428 
00429     if (this != node)
00430     {
00431       if (FirstChildNode() )
00432       {
00433         // we have a child node; recurse through it
00434         if (FirstChildNode()->FindNode (node) )
00435           return true;
00436       }
00437     }
00438     else
00439     {
00440       return true;
00441     }
00442 
00443     // Not found in child node; check the siblings
00444     if (Next() )
00445     {
00446       if (Next()->FindNode (node) )
00447         return true;
00448     }
00449 
00450     return false;
00451   }
00452 
00453 
00454 // NodeItem* NodeItem::RootNode()
00455 // {
00456 //     NodeItem* root = this;
00457 //     while(root->Parent())
00458 //     {
00459 //         root = root->Parent();
00460 //     }
00461 //     return root;
00462 // }
00463 
00464   const NodeItem *NodeItem::RootNode() const
00465   {
00466     const NodeItem *root = this;
00467 
00468     while (root->Parent() )
00469     {
00470       root = root->Parent();
00471     }
00472 
00473     return root;
00474   }
00475 
00476   int NodeItem::NumChild() const
00477   {
00478     const NodeItem *child = FirstChildNode();
00479     int Num = 0;
00480 
00481     while (child)
00482     {
00483       ++Num;
00484       child = child->Next();
00485     }
00486 
00487     return Num;
00488   }
00489 
00490   int NodeItem::Depth() const
00491   {
00492     const NodeItem *parent = Parent();
00493     int Num = 0;
00494 
00495     while (parent)
00496     {
00497       ++Num;
00498       parent = parent->Parent();
00499     }
00500 
00501     return Num;
00502   }
00503 
00504   void NodeItem::DeleteTree()
00505   {
00506     NodeItem *child = FirstChildNode();
00507 
00508     while (child && (!SkipChild()))
00509     {
00510       child->DeleteTree();
00511       child->Unlink();
00512       delete child;
00513       child = FirstChildNode();
00514     }
00515   }
00516 
00517 
00518 }
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends