ARB
TreeNode.h
Go to the documentation of this file.
1 // ================================================================ //
2 // //
3 // File : TreeNode.h //
4 // Purpose : //
5 // //
6 // Coded by Ralf Westram (coder@reallysoft.de) in December 2013 //
7 // Institute of Microbiology (Technical University Munich) //
8 // http://www.arb-home.de/ //
9 // //
10 // ================================================================ //
11 
12 #ifndef TREENODE_H
13 #define TREENODE_H
14 
15 #ifndef ARBDBT_H
16 #include "arbdbt.h"
17 #endif
18 #ifndef _GLIBCXX_ALGORITHM
19 #include <algorithm>
20 #endif
21 
22 #define rt_assert(cond) arb_assert(cond)
23 
24 #if defined(DEBUG) || defined(UNIT_TESTS) // UT_DIFF
25 # define PROVIDE_TREE_STRUCTURE_TESTS
26 #endif
27 #if defined(DEVEL_RALF) && defined(PROVIDE_TREE_STRUCTURE_TESTS)
28 # define AUTO_CHECK_TREE_STRUCTURE // Note: dramatically slows down most tree operations
29 #endif
30 
31 class TreeRoot;
32 class TreeNode;
33 class ARB_edge;
34 
35 enum TreeOrder { // contains bit values!
36  ORDER_BIG_DOWN = 1, // bit 0 set -> big branches down
37  ORDER_BIG_TO_EDGE = 2, // bit 1 set -> big branches to edge
38  ORDER_BIG_TO_CENTER = 4, // bit 2 set -> big branches to center
39  ORDER_ALTERNATING = 8, // bit 3 set -> alternate bit 0
40 
41  // user visible orders:
47 };
48 
49 #define DEFINE_READ_ACCESSORS(TYPE, ACCESS, MEMBER) \
50  TYPE ACCESS() { return MEMBER; } \
51  const TYPE ACCESS() const { return MEMBER; }
52 
53 class TreeRoot : virtual Noncopyable {
54  TreeNode *rootNode; // root node of the tree
55  bool deleteWithNodes;
56  bool seenBootstrapDuringLoad;
57 
58 protected:
59  void predelete() {
60  // should be called from dtor of derived class defining makeNode/destroyNode
61  if (rootNode) {
62  destroyNode(rootNode);
63  rt_assert(!rootNode);
64  }
65  }
66 public:
67  explicit TreeRoot(bool deleteWithNodes_) :
68  rootNode(NULp),
69  deleteWithNodes(deleteWithNodes_),
70  seenBootstrapDuringLoad(false)
71  {
90  }
91  virtual ~TreeRoot();
92  virtual void change_root(TreeNode *old, TreeNode *newroot);
93 
94  void delete_by_node() {
95  if (deleteWithNodes) {
96  rt_assert(!rootNode);
97  delete this;
98  }
99  }
100 
101  bool has_bootstrap() const {
102  return seenBootstrapDuringLoad;
103  }
104  void set_bootstrap_seen(bool seen) {
105  seenBootstrapDuringLoad = seen;
106  }
107 
108  virtual TreeNode *makeNode() const = 0;
109  virtual void destroyNode(TreeNode *node) const = 0;
110 
111  DEFINE_READ_ACCESSORS(TreeNode*, get_root_node, rootNode);
112 
114 };
116 
117 inline GBT_RemarkType parse_remark(const char *remark, double& bootstrap) {
121  if (!remark) return REMARK_NONE;
122 
123  const char *end = NULp;
124  bootstrap = strtod(remark, (char**)&end);
125 
126  bool is_bootstrap = end[0] == '%' && end[1] == 0;
127  return is_bootstrap ? REMARK_BOOTSTRAP : REMARK_OTHER;
128 }
129 
130 struct TreeNode : virtual Noncopyable {
134  char *name;
135 
136 private:
137  bool leaf;
138  bool keeledOver; // node has group info and tree-root was moved "inside" that group -> group changed meaning (see #735)
139  bool inverseLeft; // (only if keeledOver) true -> left son contains "inverse" of original group; false -> right son dito
140 
141  SmartCharPtr remark_branch; // remark_branch normally contains some bootstrap value in format 'xx%'
142  // if you store other info there, please make sure that this info does not start with digits!!
143  // Otherwise the tree export routines will not work correctly!
144 
145  GBT_LEN& length_ref() { return is_leftson() ? father->leftlen : father->rightlen; }
146  const GBT_LEN& length_ref() const { return const_cast<TreeNode*>(this)->length_ref(); }
147 
148  void keelOver(TreeNode *prev, TreeNode *next, double len);
149 
150 protected:
152  return is_leftson() ? father->leftson : father->rightson;
153  }
155  if (father) {
156  self_ref() = NULp;
157  father = NULp;
158  }
159  }
160 
161  inline void swap_node_info(TreeNode *other, bool ofKeeledGroups);
163  if (father->keeledOver) {
164  father->inverseLeft = is_leftson();
166  }
167  }
168 
169 public:
170 
171  bool is_leaf() const { return leaf; }
172  void markAsLeaf() {
173  rt_assert(!is_leaf());
174  rt_assert(!leftson && !rightson); // only allowed during setup!
175  leaf = true;
176  }
177 
179  DEFINE_READ_ACCESSORS(TreeNode*, get_leftson, leftson);
180  DEFINE_READ_ACCESSORS(TreeNode*, get_rightson, rightson);
181 
182  // Note: unittests for these attributes are in ../NTREE/ad_trees.cxx@TEST_TreeNode_attributes
183 
184  bool is_son_of(const TreeNode *Father) const {
185  return father == Father &&
186  (father->leftson == this || father->rightson == this);
187  }
188  bool is_leftson() const {
189  // left when root is at bottom; see also ../SL/ARB_TREE/ARB_Tree.hxx@is_upper_son
190  gb_assert(is_son_of(get_father())); // do only call with sons!
191  return father->leftson == this;
192  }
193  bool is_rightson() const {
194  gb_assert(is_son_of(get_father())); // do only call with sons!
195  return father->rightson == this;
196  }
197 
198  bool is_inside(const TreeNode *subtree) const {
199  return this == subtree || (father && get_father()->is_inside(subtree));
200  }
201  bool is_ancestor_of(const TreeNode *descendant) const {
202  return !is_leaf() && descendant != this && descendant->is_inside(this);
203  }
204  bool in_same_branch_as(const TreeNode *other) const {
205  // returns true if 'this' and 'other' are in ONE branch
206  return this == other || is_ancestor_of(other) || other->is_ancestor_of(this);
207  }
208  bool in_other_branch_than(const TreeNode *other) const {
209  // returns true if 'this' and 'other' are NOT in one branch
210  return !in_same_branch_as(other);
211  }
212  const TreeNode *ancestor_common_with(const TreeNode *other) const;
213  TreeNode *ancestor_common_with(TreeNode *other) { return const_cast<TreeNode*>(ancestor_common_with(const_cast<const TreeNode*>(other))); }
214 
215  bool is_son_of_root() const {
216  return father && !father->father && father->is_root_node();
217  }
218 
219  GBT_LEN get_branchlength() const { return length_ref(); }
220  void set_branchlength(GBT_LEN newlen) {
221  gb_assert(!is_nan_or_inf(newlen));
222  length_ref() = newlen;
223  }
224 
227  if (father->is_root_node()) {
228  return father->leftlen+father->rightlen;
229  }
230  return get_branchlength();
231  }
234  if (father->is_root_node()) {
235  father->leftlen = newlen/2;
236  father->rightlen = newlen-father->leftlen; // make sure sum equals newlen
237  }
238  else {
239  set_branchlength(newlen);
240  }
241  }
242 
243  GBT_LEN sum_child_lengths() const;
246  return father ? get_branchlength()+father->root_distance() : 0.0;
247  }
248  GBT_LEN intree_distance_to(const TreeNode *other) const {
249  const TreeNode *ancestor = ancestor_common_with(other);
250  return root_distance() + other->root_distance() - 2*ancestor->root_distance();
251  }
252 
253  void remove_bootstrap(); // remove bootstrap values from subtree
254 
255  void reset_branchlengths(); // reset branchlengths of subtree to tree_defaults::LENGTH
256  void scale_branchlengths(double factor);
257 
258  void bootstrap2branchlen(); // copy bootstraps to branchlengths
259  void branchlen2bootstrap(); // copy branchlengths to bootstraps
260 
261  GBT_RemarkType parse_bootstrap(double& bootstrap) const {
262  rt_assert(!is_leaf()); // only inner nodes may have bootstraps
263  return parse_remark(remark_branch.content(), bootstrap);
264  }
265 
266  const char *get_remark() const {
267  rt_assert(!is_leaf()); // only inner nodes may have bootstraps
268  return remark_branch.content();
269  }
270  const SmartCharPtr& get_remark_ptr() const {
271  rt_assert(!is_leaf()); // only inner nodes may have bootstraps
272  return remark_branch;
273  }
274  bool is_inner_node_with_remark() const { return !is_leaf() && get_remark_ptr().isSet(); }
275  void use_as_remark(const SmartCharPtr& newRemark) {
276  rt_assert(!is_leaf()); // only inner nodes may have bootstraps
277  remark_branch = newRemark;
278  }
279  void set_remark(const char *newRemark) {
280  use_as_remark(strdup(newRemark));
281  }
282  void set_bootstrap(double bootstrap) {
283  use_as_remark(GBS_global_string_copy("%i%%", int(bootstrap+0.5)));
284  }
285  void remove_remark() {
286  SmartCharPtr norem;
287  use_as_remark(norem);
288  }
289 #if defined(ASSERTION_USED) || defined(PROVIDE_TREE_STRUCTURE_TESTS)
290  bool has_no_remark() const { return remark_branch.isNull(); }
291  bool has_valid_root_remarks() const;
292 #endif
293 
294 private:
295 
296  friend void TreeRoot::change_root(TreeNode *old, TreeNode *newroot);
297 
298  TreeRoot *tree_root;
299 
300  // ------------------
301  // functions
302 
303  void reorder_subtree(TreeOrder mode);
304 
305 protected:
306  void set_tree_root(TreeRoot *new_root);
307 
308  bool at_root() const {
310  return !father || !father->father;
311  }
312  virtual ~TreeNode() {
313  if (tree_root) {
314  rt_assert(tree_root->get_root_node() == this); // you may only free the root-node or unlinked nodes (i.e. nodes where tree_root is NULp)
315 
316  TreeRoot *root = tree_root;
317  root->TreeRoot::change_root(this, NULp);
318  root->delete_by_node();
319  }
320  delete leftson; gb_assert(!leftson); // cannot use destroy here
321  delete rightson; gb_assert(!rightson);
322 
324 
325  free(name);
326  }
327  void destroy() {
328  rt_assert(knownNonNull(this));
329  TreeRoot *myRoot = get_tree_root();
330  rt_assert(myRoot); // if this fails, you need to use destroy(TreeRoot*), i.e. destroy(TreeNode*, TreeRoot*)
331  myRoot->destroyNode(this);
332  }
333  void destroy(TreeRoot *viaRoot) {
334  rt_assert(knownNonNull(this));
335 #if defined(ASSERTION_USED)
336  TreeRoot *myRoot = get_tree_root();
337  rt_assert(!myRoot || myRoot == viaRoot);
338 #endif
339  viaRoot->destroyNode(this);
340  }
341 
342 public:
344  father(NULp), leftson(NULp), rightson(NULp),
345  leftlen(0.0), rightlen(0.0),
346  gb_node(NULp),
347  name(NULp),
348  leaf(false),
349  keeledOver(false),
350  inverseLeft(false),
351  tree_root(root)
352  {}
353  static void destroy(TreeNode *that) { // replacement for destructor
354  if (that) that->destroy();
355  }
356  static void destroy(TreeNode *that, TreeRoot *root) {
357  if (that) that->destroy(root);
358  }
359 
360  TreeNode *fixDeletedSon(); // @@@ review (design)
361 
362  void unlink_from_DB();
363 
364  void announce_tree_constructed() { // @@@ use this function or just call change_root instead?
365  // (has to be) called after tree has been constructed
366  gb_assert(!father); // has to be called with root-node!
367  get_tree_root()->change_root(NULp, this);
368  }
369 
370  virtual unsigned get_leaf_count() const = 0;
371  virtual void compute_tree() = 0;
372 
375  leftson = NULp;
376  rightson = NULp;
377  father = NULp;
378  }
379 
380  TreeRoot *get_tree_root() const { return tree_root; }
381 
382  const TreeNode *get_root_node() const {
383  if (!tree_root) return NULp; // nodes removed from tree have no root-node
384 
385  const TreeNode *root = tree_root->get_root_node();
386  rt_assert(is_inside(root)); // this is not in tree - behavior of get_root_node() changed!
387  return root;
388  }
389  TreeNode *get_root_node() { return const_cast<TreeNode*>(const_cast<const TreeNode*>(this)->get_root_node()); }
390 
391  bool is_root_node() const { return !father && get_root_node() == this; }
392  virtual void set_root();
393 
395  rt_assert(!is_root_node()); // root node has no brother
396  rt_assert(father); // this is a removed node (not root, but no father)
397  return is_leftson() ? get_father()->get_rightson() : get_father()->get_leftson();
398  }
399  const TreeNode *get_brother() const {
400  return const_cast<const TreeNode*>(const_cast<TreeNode*>(this)->get_brother());
401  }
402 
403  bool has_group_info() const {
404  rt_assert(!is_leaf()); // a leaf never has group info (useless call)
405  return gb_node && name;
406  }
408  return (has_group_info() && keeledOver) ? (inverseLeft ? get_leftson() : get_rightson()) : NULp;
409  }
410  const TreeNode *keelTarget() const {
411  return const_cast<TreeNode*>(this)->keelTarget();
412  }
413  bool keelsDownGroup(const TreeNode *toSon) const {
414  // returns true if node has a group keeled down 'toSon'
415  return keelTarget() == toSon;
416  }
417  void unkeelGroup() {
419  keeledOver = false;
420  }
421  int keeledStateInfo() const { // keeled-state as stored in database
422  return keeledOver ? (inverseLeft ? 1 : 2) : 0;
423  }
424  void setKeeledState(int keeledState) {
425  keeledOver = keeledState;
426  inverseLeft = keeledState == 1;
427  }
428 
429  bool is_normal_group() const {
430  // returns true when node shall show a "normal" group
431  rt_assert(!is_leaf()); // useless call (a normal group never may occur at leaf)
432  return has_group_info() && !keeledOver;
433  }
434  bool is_keeled_group() const {
435  // returns true when node shall show a "keeled" group.
436  // (i.e. when father has a keeled group oriented towards 'this')
437  return father && father->keelsDownGroup(this);
438  }
439  bool is_clade() const {
440  // return true, if a clickable group shall be displayed in tree
441  // (Note: keeled groups may appear at leafs)
442  return (!is_leaf() && is_normal_group()) || is_keeled_group();
443  }
444 
445  const char *get_group_name() const {
446  return
447  !is_leaf() && is_normal_group()
448  ? name
449  : (is_keeled_group() ? father->name : NULp);
450  }
451 
452  const TreeNode *find_parent_with_groupInfo(bool skipKeeledBrothers = false) const {
453  const TreeNode *child = this;
454  const TreeNode *parent = get_father();
455 
456  while (parent) {
457  if (parent->has_group_info()) {
458  if (!skipKeeledBrothers) break; // report any group
459 
460  const TreeNode *keeled = parent->keelTarget();
461  if (!keeled || keeled == child) break;
462 
463  // continue with next parent if keeled to other branch
464  }
465  child = parent;
466  parent = child->get_father();
467  }
468  return parent;
469  }
470  TreeNode *find_parent_with_groupInfo(bool skipKeeledBrothers = false) {
471  return const_cast<TreeNode*>(const_cast<const TreeNode*>(this)->find_parent_with_groupInfo(skipKeeledBrothers));
472  }
473 
474  const TreeNode *find_parent_clade() const {
475  // opposed to find_parent_with_groupInfo this reports only nodes where a group is DISPLAYED
476  // (i.e. in case of keeled groups at son node)
477 
478  const TreeNode *parent = find_parent_with_groupInfo();
479  const TreeNode *myBranch = this; // me or any ancestor
480  while (parent) {
481  const TreeNode *keeled = parent->keelTarget();
482  if (!keeled) break; // use parent
483 
484  if (parent != father && keeled->in_same_branch_as(myBranch)) {
485  parent = keeled; // use keeled
486  break;
487  }
488 
489  // either keeled to self, to brother or to brother of some of my ancestors -> step up
490  rt_assert(keeled == this || keeled == get_brother() || keeled->get_brother()->is_ancestor_of(this));
491 
492  myBranch = parent;
493  parent = parent->find_parent_with_groupInfo();
494  }
495 
496  rt_assert(implicated(parent, parent->is_clade()));
497 
498  return parent;
499  }
501  return const_cast<TreeNode*>(const_cast<const TreeNode*>(this)->find_parent_clade());
502  }
503  int calc_clade_level() const {
504  int taxLev = is_clade();
505  const TreeNode *parent = find_parent_clade();
506  if (parent) taxLev += parent->calc_clade_level();
507  return taxLev;
508  }
509 
510  int count_clades() const;
511 
512  virtual void swap_sons() {
513  rt_assert(!is_leaf()); // only possible for inner nodes!
514 
515  std::swap(leftson, rightson);
516  std::swap(leftlen, rightlen);
517  inverseLeft = !inverseLeft;
518  }
519  void rotate_subtree(); // flip whole subtree ( = recursive swap_sons())
520  void reorder_tree(TreeOrder mode);
521 
522  TreeNode *findLeafNamed(const char *wantedName);
523 
526  if (!is_leaf()) remove_remark();
529  return len;
530  }
531 
533  double bootstrap;
534  double branchlength;
536  multifurc_limits(double bootstrap_, double branchlength_, bool applyAtLeafs_)
537  : bootstrap(bootstrap_),
538  branchlength(branchlength_),
539  applyAtLeafs(applyAtLeafs_)
540  {}
541  };
542  class LengthCollector;
543 
544  void multifurcate();
545  void set_branchlength_preserving(GBT_LEN new_len);
546 
547  void multifurcate_whole_tree(const multifurc_limits& below);
548 private:
549  void eliminate_and_collect(const multifurc_limits& below, LengthCollector& collect);
550 public:
551 
552 #if defined(PROVIDE_TREE_STRUCTURE_TESTS)
553  Validity is_valid() const;
554 #endif // PROVIDE_TREE_STRUCTURE_TESTS
555 };
556 MARK_NONFINAL_METHOD(TreeNode,swap_sons,());
557 MARK_NONFINAL_METHOD(TreeNode,set_root,());
558 
559 inline void destroy(TreeNode *that) {
560  TreeNode::destroy(that);
561 }
562 inline void destroy(TreeNode *that, TreeRoot *root) {
563  TreeNode::destroy(that, root);
564 }
565 
566 // ---------------------------------------------------------------------------------------
567 // macros to overwrite accessors in classes derived from TreeRoot or TreeNode:
568 
569 #define DEFINE_TREE_ROOT_ACCESSORS(RootType, TreeType) \
570  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_root_node, TreeRoot::get_root_node())
571 
572 #define DEFINE_TREE_RELATIVES_ACCESSORS(TreeType) \
573  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_father, father); \
574  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_leftson, leftson); \
575  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_rightson, rightson); \
576  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_brother, TreeNode::get_brother()); \
577  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_root_node, TreeNode::get_root_node()); \
578  TreeType *findLeafNamed(const char *wantedName) { return DOWNCAST(TreeType*, TreeNode::findLeafNamed(wantedName)); }
579 
580 #define DEFINE_TREE_ACCESSORS(RootType, TreeType) \
581  DEFINE_DOWNCAST_ACCESSORS(RootType, get_tree_root, TreeNode::get_tree_root()); \
582  DEFINE_TREE_RELATIVES_ACCESSORS(TreeType)
583 
584 
585 // -------------------------
586 // structure tests
587 
588 #if defined(PROVIDE_TREE_STRUCTURE_TESTS)
589 template <typename TREE>
590 inline Validity tree_is_valid(const TREE *tree, bool acceptNULL) {
591  if (tree) return tree->is_valid();
592  return Validity(acceptNULL, "NULp tree");
593 }
594 template <typename TREE>
595 inline bool tree_is_valid_or_dump(const TREE *tree, bool acceptNULL) {
596  Validity valid = tree_is_valid(tree, acceptNULL);
597  if (!valid) fprintf(stderr, "\ntree is NOT valid (Reason: %s)\n", valid.why_not());
598  return valid;
599 }
600 #endif
601 
602 #if defined(AUTO_CHECK_TREE_STRUCTURE)
603 #define ASSERT_VALID_TREE(tree) rt_assert(tree_is_valid_or_dump(tree, false))
604 #define ASSERT_VALID_TREE_OR_NULL(tree) rt_assert(tree_is_valid_or_dump(tree, true))
605 #else
606 #define ASSERT_VALID_TREE(tree)
607 #define ASSERT_VALID_TREE_OR_NULL(tree)
608 #endif // AUTO_CHECK_TREE_STRUCTURE
609 
610 #if defined(PROVIDE_TREE_STRUCTURE_TESTS) && defined(UNIT_TESTS)
611 
612 #define TEST_EXPECT_VALID_TREE(tree) TEST_VALIDITY(tree_is_valid(tree, false))
613 #define TEST_EXPECT_VALID_TREE_OR_NULL(tree) TEST_VALIDITY(tree_is_valid(tree, true))
614 #define TEST_EXPECT_VALID_TREE__BROKEN(tree,why) TEST_VALIDITY__BROKEN(tree_is_valid(tree, false), why)
615 #define TEST_EXPECT_VALID_TREE_OR_NULL__BROKEN(tree,why) TEST_VALIDITY__BROKEN(tree_is_valid(tree, true), why)
616 
617 #else
618 
619 #define TEST_EXPECT_VALID_TREE(tree)
620 #define TEST_EXPECT_VALID_TREE_OR_NULL(tree)
621 #define TEST_EXPECT_VALID_TREE__BROKEN(tree)
622 #define TEST_EXPECT_VALID_TREE_OR_NULL__BROKEN(tree)
623 
624 #endif
625 
626 // --------------------
627 // SimpleTree
628 
629 struct SimpleRoot : public TreeRoot {
630  inline SimpleRoot();
631  inline TreeNode *makeNode() const OVERRIDE;
632  inline void destroyNode(TreeNode *node) const OVERRIDE;
633 };
634 
635 class SimpleTree FINAL_TYPE : public TreeNode {
636 protected:
638  friend class SimpleRoot;
639 public:
640  SimpleTree(SimpleRoot *sroot) : TreeNode(sroot) {}
641 
642  // TreeNode interface
643  unsigned get_leaf_count() const OVERRIDE {
644  rt_assert(0); // @@@ impl?
645  return 0;
646  }
648 };
649 
651 inline TreeNode *SimpleRoot::makeNode() const { return new SimpleTree(const_cast<SimpleRoot*>(this)); }
652 inline void SimpleRoot::destroyNode(TreeNode *node) const { delete DOWNCAST(SimpleTree*,node); }
653 
654 // ----------------------
655 // ARB_edge_type
656 
658  EDGE_TO_ROOT, // edge points towards the root node
659  EDGE_TO_LEAF, // edge points away from the root node
660  ROOT_EDGE, // edge between sons of root node
661 };
662 
663 class ARB_edge {
664  // ARB_edge is a directional edge between two non-root-nodes of the same tree
665  // (can act as iterator for TreeNode)
666 
667  TreeNode *from, *to;
668  ARB_edge_type type;
669 
670  ARB_edge_type detectType() const {
671  rt_assert(to != from);
672  rt_assert(!from->is_root_node()); // edges cannot be at root - use edge between sons of root!
673  rt_assert(!to->is_root_node());
674 
675  if (from->father == to) return EDGE_TO_ROOT;
676  if (to->father == from) return EDGE_TO_LEAF;
677 
678  rt_assert(from->get_brother() == to); // no edge exists between 'from' and 'to'
679  rt_assert(to->get_father()->is_root_node());
680  return ROOT_EDGE;
681  }
682 
683  GBT_LEN adjacent_distance() const;
684  GBT_LEN length_or_adjacent_distance() const {
685  {
686  GBT_LEN len = length();
687  if (len>0.0) return len;
688  }
689  return adjacent_distance();
690  }
691 
692  void virtually_add_or_distribute_length_forward(GBT_LEN len, TreeNode::LengthCollector& collect) const;
693  void virtually_distribute_length_forward(GBT_LEN len, TreeNode::LengthCollector& collect) const;
694 public:
695  void virtually_distribute_length(GBT_LEN len, TreeNode::LengthCollector& collect) const; // @@@ hm public :(
696 private:
697 
698 #if defined(UNIT_TESTS) // UT_DIFF
699  friend void TEST_edges();
700 #endif
701 
702 public:
703  ARB_edge(TreeNode *From, TreeNode *To) :
704  from(From),
705  to(To),
706  type(detectType())
707  {}
709  from(From),
710  to(To),
711  type(Type)
712  {
713  rt_assert(type == detectType());
714  }
715  ARB_edge(const ARB_edge& otherEdge) :
716  from(otherEdge.from),
717  to(otherEdge.to),
718  type(otherEdge.type)
719  {
720  rt_assert(type == detectType());
721  }
722 
724 
725  ARB_edge_type get_type() const { return type; }
726  TreeNode *source() const { return from; }
727  TreeNode *dest() const { return to; }
728 
729  TreeNode *son() const { return type == EDGE_TO_ROOT ? from : to; }
730  TreeNode *other() const { return type == EDGE_TO_ROOT ? to : from; }
731 
732  GBT_LEN length() const {
733  if (type == ROOT_EDGE) return from->get_branchlength() + to->get_branchlength();
734  return son()->get_branchlength();
735  }
736  void set_length(GBT_LEN len) {
737  if (type == ROOT_EDGE) {
738  from->set_branchlength(len/2);
739  to->set_branchlength(len/2);
740  }
741  else {
742  son()->set_branchlength(len);
743  }
744  }
747  if (type == ROOT_EDGE) {
749  }
750  return son()->reset_length_and_bootstrap();
751  }
752 
753  ARB_edge inverse() const {
754  return ARB_edge(to, from, ARB_edge_type(type == ROOT_EDGE ? ROOT_EDGE : (EDGE_TO_LEAF+EDGE_TO_ROOT)-type));
755  }
756 
757  // iterator functions: endlessly iterate over all edges of tree
758  // - next: forward (=towards dest())
759  // - previous: backward (=back before source())
760  // - counter: forward descends left (=upper) son first
761  // - non-counter: forward descends right (=lower) son first
762 
763  ARB_edge next() const { // descends rightson first (traverses leaf-edges from bottom to top)
764  if (type == EDGE_TO_ROOT) {
765  rt_assert(from->is_son_of(to));
766  if (from->is_rightson()) return ARB_edge(to, to->get_leftson(), EDGE_TO_LEAF);
767  TreeNode *father = to->get_father();
768  if (father->is_root_node()) return ARB_edge(to, to->get_brother(), ROOT_EDGE);
769  return ARB_edge(to, father, EDGE_TO_ROOT);
770  }
771  if (is_edge_to_leaf()) return inverse();
772  return ARB_edge(to, to->get_rightson(), EDGE_TO_LEAF);
773  }
774  ARB_edge previous() const { // inverse of next(). (traverses leaf-edges from top to bottom)
775  if (type == EDGE_TO_LEAF) {
776  rt_assert(to->is_son_of(from));
777  if (to->is_leftson()) return ARB_edge(from->get_rightson(), from, EDGE_TO_ROOT);
778  TreeNode *father = from->get_father();
779  if (father->is_root_node()) return ARB_edge(from->get_brother(), from, ROOT_EDGE);
780  return ARB_edge(father, from, EDGE_TO_LEAF);
781  }
782  if (is_edge_from_leaf()) return inverse();
783  return ARB_edge(from->get_leftson(), from, EDGE_TO_ROOT);
784  }
785 
786  ARB_edge counter_next() const { // descends leftson first (traverses leaf-edges from top to bottom)
787  if (type == EDGE_TO_ROOT) {
788  rt_assert(from->is_son_of(to));
789  if (from->is_leftson()) return ARB_edge(to, to->get_rightson(), EDGE_TO_LEAF);
790  TreeNode *father = to->get_father();
791  if (father->is_root_node()) return ARB_edge(to, to->get_brother(), ROOT_EDGE);
792  return ARB_edge(to, father, EDGE_TO_ROOT);
793  }
794  if (is_edge_to_leaf()) return inverse();
795  return ARB_edge(to, to->get_leftson(), EDGE_TO_LEAF);
796  }
797  ARB_edge counter_previous() const { // inverse of counter_next(). (traverses leaf-edges from bottom to top)
798  if (type == EDGE_TO_LEAF) {
799  rt_assert(to->is_son_of(from));
800  if (to->is_rightson()) return ARB_edge(from->get_leftson(), from, EDGE_TO_ROOT);
801  TreeNode *father = from->get_father();
802  if (father->is_root_node()) return ARB_edge(from->get_brother(), from, ROOT_EDGE);
803  return ARB_edge(father, from, EDGE_TO_LEAF);
804  }
805  if (is_edge_from_leaf()) return inverse();
806  return ARB_edge(from->get_rightson(), from, EDGE_TO_ROOT);
807  }
808 
809  static int iteration_count(int leafs_in_tree) {
813  return leafs_2_edges(leafs_in_tree, UNROOTED) * 2;
814  }
815 
816  bool operator == (const ARB_edge& otherEdge) const {
817  return from == otherEdge.from && to == otherEdge.to;
818  }
819  bool operator != (const ARB_edge& otherEdge) const {
820  return !operator == (otherEdge);
821  }
822 
823  bool is_edge_to_leaf() const {
825  return dest()->is_leaf();
826  }
827  bool is_edge_from_leaf() const {
829  return source()->is_leaf();
830  }
831  bool is_inner_edge() const {
833  return !is_edge_to_leaf() && !is_edge_from_leaf();
834  }
835 
836  void set_root() { son()->set_root(); }
837 
838  void multifurcate();
839 
840 };
841 
846  TreeNode *father = son->get_father();
847  rt_assert(father);
848 
849  if (father->is_root_node()) return ARB_edge(son, son->get_brother(), ROOT_EDGE);
850  return ARB_edge(son, father, EDGE_TO_ROOT);
851 }
852 inline ARB_edge leafEdge(TreeNode *leaf) {
853  rt_assert(leaf->is_leaf());
854  return parentEdge(leaf).inverse();
855 }
856 
857 inline ARB_edge rootEdge(TreeRoot *root) {
858  TreeNode *root_node = root->get_root_node();
859  return ARB_edge(root_node->get_leftson(), root_node->get_rightson(), ROOT_EDGE);
860 }
861 
862 #else
863 #error TreeNode.h included twice
864 #endif // TREENODE_H
ARB_edge(const ARB_edge &otherEdge)
Definition: TreeNode.h:715
void set_bootstrap(double bootstrap)
Definition: TreeNode.h:282
void set_branchlength_unrooted(GBT_LEN newlen)
Definition: TreeNode.h:232
void compute_tree() OVERRIDE
Definition: TreeNode.h:647
bool is_rightson() const
Definition: TreeNode.h:193
DECLARE_ASSIGNMENT_OPERATOR(ARB_edge)
void unlink_from_DB()
Definition: adtree.cxx:930
ARB_edge(TreeNode *From, TreeNode *To)
Definition: TreeNode.h:703
virtual ~TreeRoot()
Definition: TreeNode.cxx:22
void destroyNode(TreeNode *node) const OVERRIDE
Definition: TreeNode.h:652
void virtually_distribute_length(GBT_LEN len, TreeNode::LengthCollector &collect) const
Definition: TreeNode.cxx:520
void bootstrap2branchlen()
Definition: TreeNode.cxx:679
bool operator==(const ARB_edge &otherEdge) const
Definition: TreeNode.h:816
virtual void swap_sons()
Definition: TreeNode.h:512
TreeNode * makeNode() const OVERRIDE
Definition: TreeNode.h:651
GBT_RemarkType parse_bootstrap(double &bootstrap) const
Definition: TreeNode.h:261
void destroy()
Definition: TreeNode.h:327
#define implicated(hypothesis, conclusion)
Definition: arb_assert.h:289
TreeNode * findLeafNamed(const char *wantedName)
Definition: TreeNode.cxx:274
MARK_NONFINAL_METHOD(TreeRoot, change_root,(TreeNode *, TreeNode *))
int calc_clade_level() const
Definition: TreeNode.h:503
const TreeNode * get_root_node() const
Definition: TreeNode.h:382
TreeNode * find_parent_clade()
Definition: TreeNode.h:500
bool has_group_info() const
Definition: TreeNode.h:403
virtual void set_root()
Definition: TreeNode.cxx:206
void unlink_from_father()
Definition: TreeNode.h:154
const char * why_not() const
Definition: arb_error.h:169
GBT_LEN get_branchlength_unrooted() const
Definition: TreeNode.h:225
virtual void compute_tree()=0
bool is_clade() const
Definition: TreeNode.h:439
void forget_origin()
Definition: TreeNode.h:373
bool is_edge_from_leaf() const
Definition: TreeNode.h:827
ARB_edge_type get_type() const
Definition: TreeNode.h:725
void setKeeledState(int keeledState)
Definition: TreeNode.h:424
TreeRoot * get_tree_root() const
Definition: TreeNode.h:380
ARB_edge inverse() const
Definition: TreeNode.h:753
TreeNode *& self_ref()
Definition: TreeNode.h:151
GBT_LEN reset_length_and_bootstrap()
Definition: TreeNode.h:524
TreeNode * ancestor_common_with(TreeNode *other)
Definition: TreeNode.h:213
ARB_edge previous() const
Definition: TreeNode.h:774
TreeNode * other() const
Definition: TreeNode.h:730
GBT_LEN length() const
Definition: TreeNode.h:732
bool operator!=(const ARB_edge &otherEdge) const
Definition: TreeNode.h:819
TreeNode * son() const
Definition: TreeNode.h:729
const TreeNode * find_parent_with_groupInfo(bool skipKeeledBrothers=false) const
Definition: TreeNode.h:452
ARB_edge rootEdge(TreeRoot *root)
Definition: TreeNode.h:857
void use_as_remark(const SmartCharPtr &newRemark)
Definition: TreeNode.h:275
multifurc_limits(double bootstrap_, double branchlength_, bool applyAtLeafs_)
Definition: TreeNode.h:536
void destroy(TreeRoot *viaRoot)
Definition: TreeNode.h:333
bool keelsDownGroup(const TreeNode *toSon) const
Definition: TreeNode.h:413
void reset_branchlengths()
Definition: TreeNode.cxx:651
GBT_LEN leftlen
Definition: TreeNode.h:132
TreeNode * rightson
Definition: TreeNode.h:131
#define DOWNCAST(totype, expr)
Definition: downcast.h:141
SimpleTree(SimpleRoot *sroot)
Definition: TreeNode.h:640
bool has_valid_root_remarks() const
Definition: TreeNode.cxx:778
ARB_edge next() const
Definition: TreeNode.h:763
ARB_edge parentEdge(TreeNode *son)
Definition: TreeNode.h:842
GBT_RemarkType parse_remark(const char *remark, double &bootstrap)
Definition: TreeNode.h:117
CONSTEXPR_INLINE bool is_nan_or_inf(const T &n)
Definition: arbtools.h:175
const TreeNode * get_brother() const
Definition: TreeNode.h:399
void set_root()
Definition: TreeNode.h:836
POS_TREE1 * get_father() const
Definition: probe_tree.h:49
void branchlen2bootstrap()
Definition: TreeNode.cxx:702
ARB_edge(TreeNode *From, TreeNode *To, ARB_edge_type Type)
Definition: TreeNode.h:708
static void destroy(TreeNode *that, TreeRoot *root)
Definition: TreeNode.h:356
const TreeNode * keelTarget() const
Definition: TreeNode.h:410
bool in_other_branch_than(const TreeNode *other) const
Definition: TreeNode.h:208
virtual ~TreeNode()
Definition: TreeNode.h:312
bool is_son_of_root() const
Definition: TreeNode.h:215
const TreeNode * ancestor_common_with(const TreeNode *other) const
Definition: TreeNode.cxx:765
virtual TreeNode * makeNode() const =0
void swap_node_info(TreeNode *other, bool ofKeeledGroups)
Definition: AP_Tree.cxx:575
int keeledStateInfo() const
Definition: TreeNode.h:421
bool is_leftson() const
Definition: TreeNode.h:188
#define true
Definition: ureadseq.h:14
CONSTEXPR_INLINE int leafs_2_edges(int leafs, TreeModel model)
Definition: arbdbt.h:61
ARB_edge leafEdge(TreeNode *leaf)
Definition: TreeNode.h:852
DEFINE_READ_ACCESSORS(TreeNode *, get_father, father)
#define false
Definition: ureadseq.h:13
void multifurcate()
Definition: TreeNode.cxx:578
TreeNode * father
Definition: TreeNode.h:131
bool is_root_node() const
Definition: TreeNode.h:391
CONSTEXPR_INLINE_Cxx14 void swap(unsigned char &c1, unsigned char &c2)
Definition: ad_io_inline.h:19
bool is_keeled_group() const
Definition: TreeNode.h:434
#define that(thing)
Definition: test_unit.h:1032
bool in_same_branch_as(const TreeNode *other) const
Definition: TreeNode.h:204
void unkeelGroup()
Definition: TreeNode.h:417
TreeNode * get_root_node()
Definition: TreeNode.h:389
TreeNode * get_brother()
Definition: TreeNode.h:394
ARB_edge counter_previous() const
Definition: TreeNode.h:797
static void destroy(TreeNode *that)
Definition: TreeNode.h:353
void multifurcate_whole_tree(const multifurc_limits &below)
Definition: TreeNode.cxx:623
virtual unsigned get_leaf_count() const =0
void rotate_subtree()
Definition: TreeNode.cxx:164
bool at_root() const
Definition: TreeNode.h:308
bool is_son_of(const TreeNode *Father) const
Definition: TreeNode.h:184
CONSTEXPR_INLINE bool valid(SpeciesCreationMode m)
Definition: ed4_class.hxx:2246
TreeRoot(bool deleteWithNodes_)
Definition: TreeNode.h:67
TreeNode * leftson
Definition: TreeNode.h:131
GBT_RemarkType
Definition: arbdbt.h:29
~SimpleTree() OVERRIDE
Definition: TreeNode.h:637
GBT_LEN rightlen
Definition: TreeNode.h:132
TreeNode * find_parent_with_groupInfo(bool skipKeeledBrothers=false)
Definition: TreeNode.h:470
bool is_ancestor_of(const TreeNode *descendant) const
Definition: TreeNode.h:201
int count_clades() const
Definition: TreeNode.cxx:772
void reorder_tree(TreeOrder mode)
Definition: TreeNode.cxx:157
bool knownNonNull(const void *nonnull)
Definition: arb_assert.h:368
GBT_LEN root_distance() const
Definition: TreeNode.h:244
void remove_remark()
Definition: TreeNode.h:285
ARB_edge_type
Definition: TreeNode.h:657
void predelete()
Definition: TreeNode.h:59
bool has_no_remark() const
Definition: TreeNode.h:290
bool has_bootstrap() const
Definition: TreeNode.h:101
TreeNode * dest() const
Definition: TreeNode.h:727
#define rt_assert(cond)
Definition: TreeNode.h:22
bool is_edge_to_leaf() const
Definition: TreeNode.h:823
bool is_leaf() const
Definition: TreeNode.h:171
void set_branchlength_preserving(GBT_LEN new_len)
Definition: TreeNode.cxx:596
TreeNode * fixDeletedSon()
Definition: TreeNode.cxx:719
#define gb_assert(cond)
Definition: arbdbt.h:11
void multifurcate()
Definition: TreeNode.cxx:588
xml element
GBT_LEN intree_distance_to(const TreeNode *other) const
Definition: TreeNode.h:248
bool is_inner_node_with_remark() const
Definition: TreeNode.h:274
bool is_inside(const TreeNode *subtree) const
Definition: TreeNode.h:198
TreeNode(TreeRoot *root)
Definition: TreeNode.h:343
DEFINE_READ_ACCESSORS(TreeNode *, get_root_node, rootNode)
#define OVERRIDE
Definition: cxxforward.h:93
char * name
Definition: TreeNode.h:134
void announce_tree_constructed()
Definition: TreeNode.h:364
SimpleRoot()
Definition: TreeNode.h:650
void fixKeeledOrientation()
Definition: TreeNode.h:162
void scale_branchlengths(double factor)
Definition: TreeNode.cxx:660
void set_branchlength(GBT_LEN newlen)
Definition: TreeNode.h:220
TreeOrder
Definition: TreeNode.h:35
void set_tree_root(TreeRoot *new_root)
Definition: TreeNode.cxx:84
void set_remark(const char *newRemark)
Definition: TreeNode.h:279
GBT_LEN sum_child_lengths() const
Definition: TreeNode.cxx:670
void remove_bootstrap()
Definition: TreeNode.cxx:644
ARB_edge counter_next() const
Definition: TreeNode.h:786
float GBT_LEN
Definition: arbdb_base.h:34
bool is_inner_edge() const
Definition: TreeNode.h:831
#define NULp
Definition: cxxforward.h:97
ARB_edge find_innermost_edge()
Definition: TreeNode.cxx:395
void markAsLeaf()
Definition: TreeNode.h:172
TreeNode * keelTarget()
Definition: TreeNode.h:407
GBT_LEN get_branchlength() const
Definition: TreeNode.h:219
virtual void destroyNode(TreeNode *node) const =0
void destroy(TreeNode *that)
Definition: TreeNode.h:559
GBDATA * gb_node
Definition: TreeNode.h:133
GBT_LEN eliminate()
Definition: TreeNode.h:745
virtual void change_root(TreeNode *old, TreeNode *newroot)
Definition: TreeNode.cxx:28
void set_length(GBT_LEN len)
Definition: TreeNode.h:736
const char * get_remark() const
Definition: TreeNode.h:266
const TreeNode * find_parent_clade() const
Definition: TreeNode.h:474
const SmartCharPtr & get_remark_ptr() const
Definition: TreeNode.h:270
void set_bootstrap_seen(bool seen)
Definition: TreeNode.h:104
void delete_by_node()
Definition: TreeNode.h:94
void forget_relatives()
Definition: TreeNode.h:374
const char * get_group_name() const
Definition: TreeNode.h:445
unsigned get_leaf_count() const OVERRIDE
Definition: TreeNode.h:643
bool is_normal_group() const
Definition: TreeNode.h:429
char * GBS_global_string_copy(const char *templat,...)
Definition: arb_msg.cxx:195
TreeNode * source() const
Definition: TreeNode.h:726
static int iteration_count(int leafs_in_tree)
Definition: TreeNode.h:809