1/* 2 3 HyPhy - Hypothesis Testing Using Phylogenies. 4 5 Copyright (C) 1997-2006 6 Primary Development: 7 Sergei L Kosakovsky Pond (sergeilkp@mac.com) 8 Significant contributions from: 9 Spencer V Muse (muse@stat.ncsu.edu) 10 Simon DW Frost (sdfrost@ucsd.edu) 11 Art FY Poon (apoon@biomail.ucsd.edu) 12 13 Some of the Original Code by William A Casey. 14 15 Permission is hereby granted, free of charge, to any person obtaining a 16 copy of this software and associated documentation files (the 17 "Software"), to deal in the Software without restriction, including 18 without limitation the rights to use, copy, modify, merge, publish, 19 distribute, sublicense, and/or sell copies of the Software, and to 20 permit persons to whom the Software is furnished to do so, subject to 21 the following conditions: 22 23 The above copyright notice and this permission notice shall be included 24 in all copies or substantial portions of the Software. 25 26 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 27 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 28 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 29 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 30 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 31 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 32 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 33 34 */ 35 36 // iterator implementation 37 38template <class node_data> node_iterator<node_data>::node_iterator( 39 node<node_data>* root, int traverser_kind){ 40 41 42 this->travseral_kind = traverser_kind; 43 this->traversal_level = -1L; // not initialized yet 44 this->iterator_state = root; 45} 46 47 48template <class node_data> long node_iterator<node_data>::Level(void) const { 49 return this->iterator_state ? this->traversal_level : -1L; 50} 51 52template <class node_data> void node_iterator<node_data>::Reset(node<node_data>* root) { 53 this->traversal_level = -1L; // not initialized yet 54 this->iterator_state = root; 55} 56 57template <class node_data> node<node_data>* node_iterator<node_data>::Current(void) const { 58 if (this->traversal_level >= 0L) { 59 return this->iterator_state; 60 } 61 return NULL; 62} 63 64template <class node_data> void node_iterator<node_data>::pop_history_item (_SimpleList* history) { 65 if (history) 66 history->Pop(); 67} 68 69template <class node_data> void node_iterator<node_data>::push_history_item (_SimpleList* history) { 70 if (history) 71 (*history)<< (long)this->iterator_state; 72} 73 74template <class node_data> node<node_data>* node_iterator<node_data>::Next(_SimpleList* history) { 75 76 node<node_data>* test_node; 77 78 if (this->iterator_state) { 79 switch (this->travseral_kind) { 80 case _HY_TREE_TRAVERSAL_POSTORDER: 81 case _HY_TREE_TRAVERSAL_POSTORDER_RIGHT_FIRST: { 82 83 if (this->traversal_level < 0L) { 84 this->traversal_level = 0L; 85 this->push_history_item (history); 86 while ((test_node = this->iterator_state->go_down(this->travseral_kind == _HY_TREE_TRAVERSAL_POSTORDER ? 1 : iterator_state->get_num_nodes()))) { 87 this->iterator_state = test_node; 88 this->push_history_item (history); 89 this->traversal_level++; 90 } 91 //printf ("[node_iterator init]%ld\n", this->traversal_level); 92 return this->iterator_state; 93 } 94 95 if (this->traversal_level == 0L) { 96 // need this if traversal is initiated at an interior node which is not root 97 this->iterator_state = nil; 98 } else { 99 test_node = this->iterator_state; 100 test_node = this->travseral_kind == _HY_TREE_TRAVERSAL_POSTORDER ? test_node->go_next() : test_node->go_previous(); 101 102 if (test_node) { 103 this->pop_history_item (history); 104 this->iterator_state=test_node; 105 this->push_history_item (history); 106 while ((test_node = this->iterator_state->go_down(this->travseral_kind == _HY_TREE_TRAVERSAL_POSTORDER ? 1 : iterator_state->get_num_nodes()))) { 107 this->iterator_state = test_node; 108 this->push_history_item (history); 109 this->traversal_level++; 110 } 111 return this->iterator_state; 112 } 113 this->iterator_state=this->iterator_state->go_up(); 114 this->pop_history_item (history); 115 //printf ("[node_iterator up]%ld\n", this->traversal_level); 116 if (this->traversal_level == 0L) { 117 // need this if traversal is initiated at an interior node which is not root 118 this->iterator_state = nil; 119 } else { 120 this->traversal_level--; 121 } 122 } 123 } 124 break; 125 126 case _HY_TREE_TRAVERSAL_PREORDER: { 127 128 if (this->traversal_level < 0L) { 129 this->traversal_level = 0L; 130 } else { 131 132 test_node = this->iterator_state->go_down (1); 133 // iterator_state has already been visited; 134 // try to descend down the tree first 135 // failing that, move to the sibling 136 // failing that, move up the tree 137 138 if (test_node) { 139 this->iterator_state = test_node; 140 this->traversal_level ++; 141 142 } else { 143 test_node = this->iterator_state->go_next(); 144 if (test_node) { 145 this->pop_history_item (history); 146 this->iterator_state = test_node; 147 } else { 148 test_node = this->iterator_state->go_up(); 149 this->pop_history_item (history); 150 while (test_node && test_node->go_down (test_node->get_num_nodes()) == this->iterator_state) { 151 this->iterator_state = test_node; 152 this->pop_history_item (history); 153 this->traversal_level --; 154 test_node = this->iterator_state->go_up(); 155 } 156 if (test_node) { 157 this->iterator_state = this->iterator_state->go_next(); 158 } else { 159 this->iterator_state = nil; 160 break; 161 } 162 } 163 } 164 } 165 this->push_history_item (history); 166 } 167 break; 168 } 169 } 170 171 return this->iterator_state; 172} 173 174 //------------------------------------------------------------- 175template <class node_data> void node<node_data>::delete_tree(bool delSelf){ 176 177 long nc = get_num_nodes(); 178 for (int i=1; i<=nc; i++) { 179 go_down(i)->delete_tree(); 180 delete (go_down(i)); 181 } 182 if (delSelf) { 183 delete (this); 184 } 185} 186 187 //------------------------------------------------------------- 188template <class node_data> node<node_data>* node<node_data>::duplicate_tree(void (callback) (node<node_data>*, node<node_data>*)) { 189 190 node<node_data>* result = new node<node_data>; 191 192 for (int i=1; i<=get_num_nodes(); i++) { 193 result->add_node(*(go_down(i)->duplicate_tree(callback))); 194 } 195 196 197 if (callback) { 198 callback (this, result); 199 } else { 200 result->in_object = in_object; 201 } 202 203 return result; 204} 205 206 //------------------------------------------------------------- 207 208template <class node_data> void node_count_descendants (node<node_data>* source, node<node_data>* n) { 209 if (n->get_num_nodes() == 0) { 210 n->in_object = 1L; 211 } else { 212 n->in_object = 0L; 213 for (int i=1; i<=n->get_num_nodes(); i++) { 214 n->in_object += n->go_down(i)->in_object; 215 } 216 } 217} 218 219 220 //------------------------------------------------------------- 221template <class node_data> bool node<node_data>::compare_subtree(node<node_data>* compareTo) 222{ 223 int nNodes = get_num_nodes(); 224 if (nNodes==compareTo->get_num_nodes()) { 225 for (int i=1; i<=nNodes; i++) 226 if (!go_down(i)->compare_subtree (compareTo->go_down(i))) 227 return false; 228 return true; 229 } 230 return false; 231} 232 233 234 //------------------------------------------------------------- 235 236/* template <class node_data> long NodePathTraverser (_SimpleList& history, node<node_data>* root) 237{ 238 static long going_up, branchCount, tipCount; 239 static node<node_data>* laststep; 240 node<node_data>* curstep, *crashdummy; 241 242 if (root) 243 { 244 laststep = root; 245 branchCount=-1; 246 tipCount=-1; 247 history.Clear(); 248 while ((crashdummy = laststep->go_down(1))) 249 { 250 laststep = crashdummy; 251 if (branchCount>-1) 252 history<<branchCount; 253 branchCount++; 254 } 255 tipCount=0; 256 branchCount--; 257 return 0; 258 } 259 260 curstep = laststep; 261 crashdummy = curstep->go_next(); 262 if (crashdummy) 263 { 264 curstep=crashdummy; 265 while ((crashdummy = curstep->go_down(1))) 266 { 267 branchCount++; 268 history<<branchCount; 269 curstep = crashdummy; 270 } 271 laststep = curstep; 272 going_up = false; 273 laststep = curstep; 274 return ++tipCount; 275 } 276 277 curstep = curstep->parent; 278 history.Delete(history.countitems()-1); 279 if (!curstep) return -1; 280 crashdummy = curstep->go_next(); 281 while (!crashdummy) 282 { 283 curstep=curstep->parent; 284 if (!curstep) 285 { 286 if (!crashdummy) return -1; 287 } 288 crashdummy = curstep->go_next(); 289 history.Delete(history.countitems()-1); 290 } 291 going_up = true; 292 laststep = curstep; 293 return NodePathTraverser (history,(node<node_data>*)nil); 294 295 return -1; 296} */ 297 298 299 300 //------------------------------------------------------------- 301template <class node_data> int node<node_data>::tree_depth(void) 302{ 303 int res = 0; 304 for (int i=nodes.get_length(); i>0;i--) 305 { 306 int t = go_down(i)->tree_depth(); 307 if (t>res) 308 res = t; 309 } 310 return res+1; 311} 312 313 //------------------------------------------------------------- 314template <class node_data> 315node<node_data>* NodeTraverser (node<node_data>* root) 316{ 317 static int going_up; 318 static node<node_data>* laststep; 319 node<node_data>* curstep, *crashdummy; 320 321 if (root) 322 { 323 laststep = root; 324 while ((crashdummy = laststep->go_down(1))) laststep = crashdummy; 325 going_up = false; 326 return laststep; 327 } 328 329 curstep = laststep; 330 crashdummy = curstep->go_next(); 331 if (crashdummy) 332 { 333 curstep=crashdummy; 334 while ((crashdummy = curstep->go_down(1))) curstep = crashdummy; 335 going_up = false; 336 return laststep = curstep; 337 } 338 curstep=curstep->get_parent(); 339 going_up = true; 340 laststep = curstep; 341 return curstep; 342} 343 //-----------------------------------Set Number 1---------------- 344 345 346template <class node_data> void node<node_data>::replace_node(node<node_data>* existing, node<node_data>* newNode){ 347 if (one == existing) { 348 one = newNode; 349 return; 350 } else { 351 if (two == existing) { 352 two = newNode; 353 return; 354 } 355 } 356 for (long j = 0; nodes.length; j++) { 357 if (nodes.data[j] == existing) { 358 nodes.data[j] = newNode; 359 break; 360 } 361 } 362} 363 364 //-----------------------------------Set Number 1---------------- 365template <class node_data> int node<node_data>::get_child_num() { 366 int num_siblings; 367 if (parent) { 368 if (this == parent->one) return 1; 369 if (this == parent->two) return 2; 370 for (int i=0; i<parent->nodes.length; i++) { 371 if (parent->nodes.data[i] == this) return (i+3); 372 } 373 } 374 return -1; 375} 376 //----------------------------------end no 1-------------------- 377 //---------Public set no 2------------------------------------- 378 379 //--Bool (T/F) responses to potential tree moves 380/*template <class node_data> int node<node_data>::down(int index) 381{ 382 if ((index > 0) && (index <= get_num_nodes())){ 383 return 1; 384 } 385 else return 0; 386} //Truth of decent*/ 387 388 //------------------------------------------------------------- 389 390/*template <class node_data> int node<node_data>::next(){ 391 392 if (get_parent() == NULL) return 0; 393 if (get_child_num() < (get_parent())->get_num_nodes()) return 1; 394 return 0; 395} 396 397 //------------------------------------------------------------- 398template <class node_data> int node<node_data>::up(){ 399 if (get_child_num() > 0) return 1; 400 else return 0; 401}*/ 402 403 //--------MOVERS MOVERS through the tree 404template <class node_data> node<node_data>* node<node_data>::go_up(){ 405 return get_parent(); 406} 407 408 //------------------------------------------------------------- 409template <class node_data> node<node_data>* node<node_data>::go_next(){ 410 411 int my_index = get_child_num(); 412 if (my_index > 0) { 413 if (my_index < parent->get_num_nodes()) { 414 return parent->get_node (my_index + 1); 415 } 416 } 417 return NULL; 418} 419 420 //------------------------------------------------------------- 421template <class node_data> node<node_data>* node<node_data>::go_previous(){ 422 int my_index = get_child_num(); 423 if (my_index > 1) { 424 return parent->get_node (my_index - 1); 425 } 426 return NULL; 427} 428 429 430 //------------------------------------------------------------- 431template <class node_data> node<node_data>* node<node_data>::go_down(int index){ 432 if (index > 0L && index <= get_num_nodes()) 433 return (get_node(index)); 434 435 return NULL; //false=can go no further 436} 437 //-------------end public set no 2----------------------------- 438