nux-1.14.0
|
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 }