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