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  GB_ERROR apply_aci_to_remarks(const char *aci, const GBL_call_env& callEnv);
255 
256  void reset_branchlengths(); // reset branchlengths of subtree to tree_defaults::LENGTH
257  void scale_branchlengths(double factor);
258 
259  void bootstrap2branchlen(); // copy bootstraps to branchlengths
260  void branchlen2bootstrap(); // copy branchlengths to bootstraps
261 
262  GBT_RemarkType parse_bootstrap(double& bootstrap) const {
263  rt_assert(!is_leaf()); // only inner nodes may have bootstraps
264  return parse_remark(remark_branch.content(), bootstrap);
265  }
266 
267  const char *get_remark() const {
268  rt_assert(!is_leaf()); // only inner nodes may have bootstraps
269  return remark_branch.content();
270  }
271  const SmartCharPtr& get_remark_ptr() const {
272  rt_assert(!is_leaf()); // only inner nodes may have bootstraps
273  return remark_branch;
274  }
275  bool is_inner_node_with_remark() const { return !is_leaf() && get_remark_ptr().isSet(); }
276  void use_as_remark(const SmartCharPtr& newRemark) {
277  rt_assert(!is_leaf()); // only inner nodes may have bootstraps
278  remark_branch = newRemark;
279  }
280  void set_remark(const char *newRemark) {
281  use_as_remark(strdup(newRemark));
282  }
283  void set_bootstrap(double bootstrap) {
284  use_as_remark(GBS_global_string_copy("%i%%", int(bootstrap+0.5)));
285  }
286  void remove_remark() {
287  SmartCharPtr norem;
288  use_as_remark(norem);
289  }
290 #if defined(ASSERTION_USED) || defined(PROVIDE_TREE_STRUCTURE_TESTS)
291  bool has_no_remark() const { return remark_branch.isNull(); }
292  bool has_valid_root_remarks() const;
293 #endif
294 
295 private:
296 
297  friend void TreeRoot::change_root(TreeNode *old, TreeNode *newroot);
298 
299  TreeRoot *tree_root;
300 
301  // ------------------
302  // functions
303 
304  void reorder_subtree(TreeOrder mode);
305 
306 protected:
307  void set_tree_root(TreeRoot *new_root);
308 
309  bool at_root() const {
311  return !father || !father->father;
312  }
313  virtual ~TreeNode() {
314  if (tree_root) {
315  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)
316 
317  TreeRoot *root = tree_root;
318  root->TreeRoot::change_root(this, NULp);
319  root->delete_by_node();
320  }
321  delete leftson; gb_assert(!leftson); // cannot use destroy here
322  delete rightson; gb_assert(!rightson);
323 
325 
326  free(name);
327  }
328  void destroy() {
329  rt_assert(knownNonNull(this));
330  TreeRoot *myRoot = get_tree_root();
331  rt_assert(myRoot); // if this fails, you need to use destroy(TreeRoot*), i.e. destroy(TreeNode*, TreeRoot*)
332  myRoot->destroyNode(this);
333  }
334  void destroy(TreeRoot *viaRoot) {
335  rt_assert(knownNonNull(this));
336 #if defined(ASSERTION_USED)
337  TreeRoot *myRoot = get_tree_root();
338  rt_assert(!myRoot || myRoot == viaRoot);
339 #endif
340  viaRoot->destroyNode(this);
341  }
342 
343 public:
345  father(NULp), leftson(NULp), rightson(NULp),
346  leftlen(0.0), rightlen(0.0),
347  gb_node(NULp),
348  name(NULp),
349  leaf(false),
350  keeledOver(false),
351  inverseLeft(false),
352  tree_root(root)
353  {}
354  static void destroy(TreeNode *that) { // replacement for destructor
355  if (that) that->destroy();
356  }
357  static void destroy(TreeNode *that, TreeRoot *root) {
358  if (that) that->destroy(root);
359  }
360 
361  TreeNode *fixDeletedSon(); // @@@ review (design)
362 
363  void unlink_from_DB();
364 
365  void announce_tree_constructed() { // @@@ use this function or just call change_root instead?
366  // (has to be) called after tree has been constructed
367  gb_assert(!father); // has to be called with root-node!
368  get_tree_root()->change_root(NULp, this);
369  }
370 
371  virtual unsigned get_leaf_count() const = 0;
372  virtual void compute_tree() = 0;
373 
376  leftson = NULp;
377  rightson = NULp;
378  father = NULp;
379  }
380 
381  TreeRoot *get_tree_root() const { return tree_root; }
382 
383  const TreeNode *get_root_node() const {
384  if (!tree_root) return NULp; // nodes removed from tree have no root-node
385 
386  const TreeNode *root = tree_root->get_root_node();
387  rt_assert(is_inside(root)); // this is not in tree - behavior of get_root_node() changed!
388  return root;
389  }
390  TreeNode *get_root_node() { return const_cast<TreeNode*>(const_cast<const TreeNode*>(this)->get_root_node()); }
391 
392  bool is_root_node() const { return !father && get_root_node() == this; }
393  virtual void set_root();
394 
396  rt_assert(!is_root_node()); // root node has no brother
397  rt_assert(father); // this is a removed node (not root, but no father)
398  return is_leftson() ? get_father()->get_rightson() : get_father()->get_leftson();
399  }
400  const TreeNode *get_brother() const {
401  return const_cast<const TreeNode*>(const_cast<TreeNode*>(this)->get_brother());
402  }
403 
404  bool has_group_info() const {
405  rt_assert(!is_leaf()); // a leaf never has group info (useless call)
406  return gb_node && name;
407  }
409  return (has_group_info() && keeledOver) ? (inverseLeft ? get_leftson() : get_rightson()) : NULp;
410  }
411  const TreeNode *keelTarget() const {
412  return const_cast<TreeNode*>(this)->keelTarget();
413  }
414  bool keelsDownGroup(const TreeNode *toSon) const {
415  // returns true if node has a group keeled down 'toSon'
416  return keelTarget() == toSon;
417  }
418  void unkeelGroup() {
420  keeledOver = false;
421  }
422  int keeledStateInfo() const { // keeled-state as stored in database
423  return keeledOver ? (inverseLeft ? 1 : 2) : 0;
424  }
425  void setKeeledState(int keeledState) {
426  keeledOver = keeledState;
427  inverseLeft = keeledState == 1;
428  }
429 
430  bool is_normal_group() const {
431  // returns true when node shall show a "normal" group
432  rt_assert(!is_leaf()); // useless call (a normal group never may occur at leaf)
433  return has_group_info() && !keeledOver;
434  }
435  bool is_keeled_group() const {
436  // returns true when node shall show a "keeled" group.
437  // (i.e. when father has a keeled group oriented towards 'this')
438  return father && father->keelsDownGroup(this);
439  }
440  bool is_clade() const {
441  // return true, if a clickable group shall be displayed in tree
442  // (Note: keeled groups may appear at leafs)
443  return (!is_leaf() && is_normal_group()) || is_keeled_group();
444  }
445 
446  const char *get_group_name() const {
447  return
448  !is_leaf() && is_normal_group()
449  ? name
450  : (is_keeled_group() ? father->name : NULp);
451  }
452 
453  const TreeNode *find_parent_with_groupInfo(bool skipKeeledBrothers = false) const {
454  const TreeNode *child = this;
455  const TreeNode *parent = get_father();
456 
457  while (parent) {
458  if (parent->has_group_info()) {
459  if (!skipKeeledBrothers) break; // report any group
460 
461  const TreeNode *keeled = parent->keelTarget();
462  if (!keeled || keeled == child) break;
463 
464  // continue with next parent if keeled to other branch
465  }
466  child = parent;
467  parent = child->get_father();
468  }
469  return parent;
470  }
471  TreeNode *find_parent_with_groupInfo(bool skipKeeledBrothers = false) {
472  return const_cast<TreeNode*>(const_cast<const TreeNode*>(this)->find_parent_with_groupInfo(skipKeeledBrothers));
473  }
474 
475  const TreeNode *find_parent_clade() const {
476  // opposed to find_parent_with_groupInfo this reports only nodes where a group is DISPLAYED
477  // (i.e. in case of keeled groups at son node)
478 
479  const TreeNode *parent = find_parent_with_groupInfo();
480  const TreeNode *myBranch = this; // me or any ancestor
481  while (parent) {
482  const TreeNode *keeled = parent->keelTarget();
483  if (!keeled) break; // use parent
484 
485  if (parent != father && keeled->in_same_branch_as(myBranch)) {
486  parent = keeled; // use keeled
487  break;
488  }
489 
490  // either keeled to self, to brother or to brother of some of my ancestors -> step up
491  rt_assert(keeled == this || keeled == get_brother() || keeled->get_brother()->is_ancestor_of(this));
492 
493  myBranch = parent;
494  parent = parent->find_parent_with_groupInfo();
495  }
496 
497  rt_assert(implicated(parent, parent->is_clade()));
498 
499  return parent;
500  }
502  return const_cast<TreeNode*>(const_cast<const TreeNode*>(this)->find_parent_clade());
503  }
504  int calc_clade_level() const {
505  int taxLev = is_clade();
506  const TreeNode *parent = find_parent_clade();
507  if (parent) taxLev += parent->calc_clade_level();
508  return taxLev;
509  }
510 
511  int count_clades() const;
512 
513  virtual void swap_sons() {
514  rt_assert(!is_leaf()); // only possible for inner nodes!
515 
516  std::swap(leftson, rightson);
517  std::swap(leftlen, rightlen);
518  inverseLeft = !inverseLeft;
519  }
520  void rotate_subtree(); // flip whole subtree ( = recursive swap_sons())
521  void reorder_tree(TreeOrder mode);
522 
523  TreeNode *findLeafNamed(const char *wantedName);
524 
527  if (!is_leaf()) remove_remark();
530  return len;
531  }
532 
534  double bootstrap;
535  double branchlength;
537  multifurc_limits(double bootstrap_, double branchlength_, bool applyAtLeafs_)
538  : bootstrap(bootstrap_),
539  branchlength(branchlength_),
540  applyAtLeafs(applyAtLeafs_)
541  {}
542  };
543  class LengthCollector;
544 
545  void multifurcate();
546  void set_branchlength_preserving(GBT_LEN new_len);
547 
548  void multifurcate_whole_tree(const multifurc_limits& below);
549 private:
550  void eliminate_and_collect(const multifurc_limits& below, LengthCollector& collect);
551 public:
552 
553 #if defined(PROVIDE_TREE_STRUCTURE_TESTS)
554  Validity is_valid() const;
555 #endif // PROVIDE_TREE_STRUCTURE_TESTS
556 };
557 MARK_NONFINAL_METHOD(TreeNode,swap_sons,());
558 MARK_NONFINAL_METHOD(TreeNode,set_root,());
559 
560 inline void destroy(TreeNode *that) {
561  TreeNode::destroy(that);
562 }
563 inline void destroy(TreeNode *that, TreeRoot *root) {
564  TreeNode::destroy(that, root);
565 }
566 
567 // ---------------------------------------------------------------------------------------
568 // macros to overwrite accessors in classes derived from TreeRoot or TreeNode:
569 
570 #define DEFINE_TREE_ROOT_ACCESSORS(RootType, TreeType) \
571  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_root_node, TreeRoot::get_root_node())
572 
573 #define DEFINE_TREE_RELATIVES_ACCESSORS(TreeType) \
574  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_father, father); \
575  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_leftson, leftson); \
576  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_rightson, rightson); \
577  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_brother, TreeNode::get_brother()); \
578  DEFINE_DOWNCAST_ACCESSORS(TreeType, get_root_node, TreeNode::get_root_node()); \
579  TreeType *findLeafNamed(const char *wantedName) { return DOWNCAST(TreeType*, TreeNode::findLeafNamed(wantedName)); }
580 
581 #define DEFINE_TREE_ACCESSORS(RootType, TreeType) \
582  DEFINE_DOWNCAST_ACCESSORS(RootType, get_tree_root, TreeNode::get_tree_root()); \
583  DEFINE_TREE_RELATIVES_ACCESSORS(TreeType)
584 
585 
586 // -------------------------
587 // structure tests
588 
589 #if defined(PROVIDE_TREE_STRUCTURE_TESTS)
590 template <typename TREE>
591 inline Validity tree_is_valid(const TREE *tree, bool acceptNULL) {
592  if (tree) return tree->is_valid();
593  return Validity(acceptNULL, "NULp tree");
594 }
595 template <typename TREE>
596 inline bool tree_is_valid_or_dump(const TREE *tree, bool acceptNULL) {
597  Validity valid = tree_is_valid(tree, acceptNULL);
598  if (!valid) fprintf(stderr, "\ntree is NOT valid (Reason: %s)\n", valid.why_not());
599  return valid;
600 }
601 #endif
602 
603 #if defined(AUTO_CHECK_TREE_STRUCTURE)
604 #define ASSERT_VALID_TREE(tree) rt_assert(tree_is_valid_or_dump(tree, false))
605 #define ASSERT_VALID_TREE_OR_NULL(tree) rt_assert(tree_is_valid_or_dump(tree, true))
606 #else
607 #define ASSERT_VALID_TREE(tree)
608 #define ASSERT_VALID_TREE_OR_NULL(tree)
609 #endif // AUTO_CHECK_TREE_STRUCTURE
610 
611 #if defined(PROVIDE_TREE_STRUCTURE_TESTS) && defined(UNIT_TESTS)
612 
613 #define TEST_EXPECT_VALID_TREE(tree) TEST_VALIDITY(tree_is_valid(tree, false))
614 #define TEST_EXPECT_VALID_TREE_OR_NULL(tree) TEST_VALIDITY(tree_is_valid(tree, true))
615 #define TEST_EXPECT_VALID_TREE__BROKEN(tree,why) TEST_VALIDITY__BROKEN(tree_is_valid(tree, false), why)
616 #define TEST_EXPECT_VALID_TREE_OR_NULL__BROKEN(tree,why) TEST_VALIDITY__BROKEN(tree_is_valid(tree, true), why)
617 
618 #else
619 
620 #define TEST_EXPECT_VALID_TREE(tree)
621 #define TEST_EXPECT_VALID_TREE_OR_NULL(tree)
622 #define TEST_EXPECT_VALID_TREE__BROKEN(tree)
623 #define TEST_EXPECT_VALID_TREE_OR_NULL__BROKEN(tree)
624 
625 #endif
626 
627 // --------------------
628 // SimpleTree
629 
630 struct SimpleRoot : public TreeRoot {
631  inline SimpleRoot();
632  inline TreeNode *makeNode() const OVERRIDE;
633  inline void destroyNode(TreeNode *node) const OVERRIDE;
634 };
635 
636 class SimpleTree FINAL_TYPE : public TreeNode {
637 protected:
639  friend class SimpleRoot;
640 public:
641  SimpleTree(SimpleRoot *sroot) : TreeNode(sroot) {}
642 
643  // TreeNode interface
644  unsigned get_leaf_count() const OVERRIDE {
645  rt_assert(0); // @@@ impl?
646  return 0;
647  }
649 };
650 
652 inline TreeNode *SimpleRoot::makeNode() const { return new SimpleTree(const_cast<SimpleRoot*>(this)); }
653 inline void SimpleRoot::destroyNode(TreeNode *node) const { delete DOWNCAST(SimpleTree*,node); }
654 
655 // ----------------------
656 // ARB_edge_type
657 
659  EDGE_TO_ROOT, // edge points towards the root node
660  EDGE_TO_LEAF, // edge points away from the root node
661  ROOT_EDGE, // edge between sons of root node
662 };
663 
664 class ARB_edge {
665  // ARB_edge is a directional edge between two non-root-nodes of the same tree
666  // (can act as iterator for TreeNode)
667 
668  TreeNode *from, *to;
669  ARB_edge_type type;
670 
671  ARB_edge_type detectType() const {
672  rt_assert(to != from);
673  rt_assert(!from->is_root_node()); // edges cannot be at root - use edge between sons of root!
674  rt_assert(!to->is_root_node());
675 
676  if (from->father == to) return EDGE_TO_ROOT;
677  if (to->father == from) return EDGE_TO_LEAF;
678 
679  rt_assert(from->get_brother() == to); // no edge exists between 'from' and 'to'
680  rt_assert(to->get_father()->is_root_node());
681  return ROOT_EDGE;
682  }
683 
684  GBT_LEN adjacent_distance() const;
685  GBT_LEN length_or_adjacent_distance() const {
686  {
687  GBT_LEN len = length();
688  if (len>0.0) return len;
689  }
690  return adjacent_distance();
691  }
692 
693  void virtually_add_or_distribute_length_forward(GBT_LEN len, TreeNode::LengthCollector& collect) const;
694  void virtually_distribute_length_forward(GBT_LEN len, TreeNode::LengthCollector& collect) const;
695 public:
696  void virtually_distribute_length(GBT_LEN len, TreeNode::LengthCollector& collect) const; // @@@ hm public :(
697 private:
698 
699 #if defined(UNIT_TESTS) // UT_DIFF
700  friend void TEST_edges();
701 #endif
702 
703 public:
704  ARB_edge(TreeNode *From, TreeNode *To) :
705  from(From),
706  to(To),
707  type(detectType())
708  {}
710  from(From),
711  to(To),
712  type(Type)
713  {
714  rt_assert(type == detectType());
715  }
716  ARB_edge(const ARB_edge& otherEdge) :
717  from(otherEdge.from),
718  to(otherEdge.to),
719  type(otherEdge.type)
720  {
721  rt_assert(type == detectType());
722  }
723 
725 
726  ARB_edge_type get_type() const { return type; }
727  TreeNode *source() const { return from; }
728  TreeNode *dest() const { return to; }
729 
730  TreeNode *son() const { return type == EDGE_TO_ROOT ? from : to; }
731  TreeNode *other() const { return type == EDGE_TO_ROOT ? to : from; }
732 
733  GBT_LEN length() const {
734  if (type == ROOT_EDGE) return from->get_branchlength() + to->get_branchlength();
735  return son()->get_branchlength();
736  }
737  void set_length(GBT_LEN len) {
738  if (type == ROOT_EDGE) {
739  from->set_branchlength(len/2);
740  to->set_branchlength(len/2);
741  }
742  else {
743  son()->set_branchlength(len);
744  }
745  }
748  if (type == ROOT_EDGE) {
750  }
751  return son()->reset_length_and_bootstrap();
752  }
753 
754  ARB_edge inverse() const {
755  return ARB_edge(to, from, ARB_edge_type(type == ROOT_EDGE ? ROOT_EDGE : (EDGE_TO_LEAF+EDGE_TO_ROOT)-type));
756  }
757 
758  // iterator functions: endlessly iterate over all edges of tree
759  // - next: forward (=towards dest())
760  // - previous: backward (=back before source())
761  // - counter: forward descends left (=upper) son first
762  // - non-counter: forward descends right (=lower) son first
763 
764  ARB_edge next() const { // descends rightson first (traverses leaf-edges from bottom to top)
765  if (type == EDGE_TO_ROOT) {
766  rt_assert(from->is_son_of(to));
767  if (from->is_rightson()) return ARB_edge(to, to->get_leftson(), EDGE_TO_LEAF);
768  TreeNode *father = to->get_father();
769  if (father->is_root_node()) return ARB_edge(to, to->get_brother(), ROOT_EDGE);
770  return ARB_edge(to, father, EDGE_TO_ROOT);
771  }
772  if (is_edge_to_leaf()) return inverse();
773  return ARB_edge(to, to->get_rightson(), EDGE_TO_LEAF);
774  }
775  ARB_edge previous() const { // inverse of next(). (traverses leaf-edges from top to bottom)
776  if (type == EDGE_TO_LEAF) {
777  rt_assert(to->is_son_of(from));
778  if (to->is_leftson()) return ARB_edge(from->get_rightson(), from, EDGE_TO_ROOT);
779  TreeNode *father = from->get_father();
780  if (father->is_root_node()) return ARB_edge(from->get_brother(), from, ROOT_EDGE);
781  return ARB_edge(father, from, EDGE_TO_LEAF);
782  }
783  if (is_edge_from_leaf()) return inverse();
784  return ARB_edge(from->get_leftson(), from, EDGE_TO_ROOT);
785  }
786 
787  ARB_edge counter_next() const { // descends leftson first (traverses leaf-edges from top to bottom)
788  if (type == EDGE_TO_ROOT) {
789  rt_assert(from->is_son_of(to));
790  if (from->is_leftson()) return ARB_edge(to, to->get_rightson(), EDGE_TO_LEAF);
791  TreeNode *father = to->get_father();
792  if (father->is_root_node()) return ARB_edge(to, to->get_brother(), ROOT_EDGE);
793  return ARB_edge(to, father, EDGE_TO_ROOT);
794  }
795  if (is_edge_to_leaf()) return inverse();
796  return ARB_edge(to, to->get_leftson(), EDGE_TO_LEAF);
797  }
798  ARB_edge counter_previous() const { // inverse of counter_next(). (traverses leaf-edges from bottom to top)
799  if (type == EDGE_TO_LEAF) {
800  rt_assert(to->is_son_of(from));
801  if (to->is_rightson()) return ARB_edge(from->get_leftson(), from, EDGE_TO_ROOT);
802  TreeNode *father = from->get_father();
803  if (father->is_root_node()) return ARB_edge(from->get_brother(), from, ROOT_EDGE);
804  return ARB_edge(father, from, EDGE_TO_LEAF);
805  }
806  if (is_edge_from_leaf()) return inverse();
807  return ARB_edge(from->get_rightson(), from, EDGE_TO_ROOT);
808  }
809 
810  static int iteration_count(int leafs_in_tree) {
814  return leafs_2_edges(leafs_in_tree, UNROOTED) * 2;
815  }
816 
817  bool operator == (const ARB_edge& otherEdge) const {
818  return from == otherEdge.from && to == otherEdge.to;
819  }
820  bool operator != (const ARB_edge& otherEdge) const {
821  return !operator == (otherEdge);
822  }
823 
824  bool is_edge_to_leaf() const {
826  return dest()->is_leaf();
827  }
828  bool is_edge_from_leaf() const {
830  return source()->is_leaf();
831  }
832  bool is_inner_edge() const {
834  return !is_edge_to_leaf() && !is_edge_from_leaf();
835  }
836 
837  void set_root() { son()->set_root(); }
838 
839  void multifurcate();
840 
841 };
842 
847  TreeNode *father = son->get_father();
848  rt_assert(father);
849 
850  if (father->is_root_node()) return ARB_edge(son, son->get_brother(), ROOT_EDGE);
851  return ARB_edge(son, father, EDGE_TO_ROOT);
852 }
853 inline ARB_edge leafEdge(TreeNode *leaf) {
854  rt_assert(leaf->is_leaf());
855  return parentEdge(leaf).inverse();
856 }
857 
858 inline ARB_edge rootEdge(TreeRoot *root) {
859  TreeNode *root_node = root->get_root_node();
860  return ARB_edge(root_node->get_leftson(), root_node->get_rightson(), ROOT_EDGE);
861 }
862 
863 #else
864 #error TreeNode.h included twice
865 #endif // TREENODE_H
ARB_edge(const ARB_edge &otherEdge)
Definition: TreeNode.h:716
void set_bootstrap(double bootstrap)
Definition: TreeNode.h:283
void set_branchlength_unrooted(GBT_LEN newlen)
Definition: TreeNode.h:232
void compute_tree() OVERRIDE
Definition: TreeNode.h:648
const char * GB_ERROR
Definition: arb_core.h:25
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:704
virtual ~TreeRoot()
Definition: TreeNode.cxx:22
void destroyNode(TreeNode *node) const OVERRIDE
Definition: TreeNode.h:653
void virtually_distribute_length(GBT_LEN len, TreeNode::LengthCollector &collect) const
Definition: TreeNode.cxx:520
void bootstrap2branchlen()
Definition: TreeNode.cxx:706
bool operator==(const ARB_edge &otherEdge) const
Definition: TreeNode.h:817
virtual void swap_sons()
Definition: TreeNode.h:513
TreeNode * makeNode() const OVERRIDE
Definition: TreeNode.h:652
GBT_RemarkType parse_bootstrap(double &bootstrap) const
Definition: TreeNode.h:262
void destroy()
Definition: TreeNode.h:328
#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:504
const TreeNode * get_root_node() const
Definition: TreeNode.h:383
TreeNode * find_parent_clade()
Definition: TreeNode.h:501
bool has_group_info() const
Definition: TreeNode.h:404
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:171
GBT_LEN get_branchlength_unrooted() const
Definition: TreeNode.h:225
virtual void compute_tree()=0
bool is_clade() const
Definition: TreeNode.h:440
void forget_origin()
Definition: TreeNode.h:374
bool is_edge_from_leaf() const
Definition: TreeNode.h:828
ARB_edge_type get_type() const
Definition: TreeNode.h:726
void setKeeledState(int keeledState)
Definition: TreeNode.h:425
TreeRoot * get_tree_root() const
Definition: TreeNode.h:381
ARB_edge inverse() const
Definition: TreeNode.h:754
TreeNode *& self_ref()
Definition: TreeNode.h:151
GBT_LEN reset_length_and_bootstrap()
Definition: TreeNode.h:525
TreeNode * ancestor_common_with(TreeNode *other)
Definition: TreeNode.h:213
ARB_edge previous() const
Definition: TreeNode.h:775
TreeNode * other() const
Definition: TreeNode.h:731
GBT_LEN length() const
Definition: TreeNode.h:733
bool operator!=(const ARB_edge &otherEdge) const
Definition: TreeNode.h:820
TreeNode * son() const
Definition: TreeNode.h:730
const TreeNode * find_parent_with_groupInfo(bool skipKeeledBrothers=false) const
Definition: TreeNode.h:453
ARB_edge rootEdge(TreeRoot *root)
Definition: TreeNode.h:858
void use_as_remark(const SmartCharPtr &newRemark)
Definition: TreeNode.h:276
multifurc_limits(double bootstrap_, double branchlength_, bool applyAtLeafs_)
Definition: TreeNode.h:537
void destroy(TreeRoot *viaRoot)
Definition: TreeNode.h:334
bool keelsDownGroup(const TreeNode *toSon) const
Definition: TreeNode.h:414
void reset_branchlengths()
Definition: TreeNode.cxx:678
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:641
bool has_valid_root_remarks() const
Definition: TreeNode.cxx:805
ARB_edge next() const
Definition: TreeNode.h:764
ARB_edge parentEdge(TreeNode *son)
Definition: TreeNode.h:843
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:178
const TreeNode * get_brother() const
Definition: TreeNode.h:400
void set_root()
Definition: TreeNode.h:837
POS_TREE1 * get_father() const
Definition: probe_tree.h:49
void branchlen2bootstrap()
Definition: TreeNode.cxx:729
ARB_edge(TreeNode *From, TreeNode *To, ARB_edge_type Type)
Definition: TreeNode.h:709
static void destroy(TreeNode *that, TreeRoot *root)
Definition: TreeNode.h:357
const TreeNode * keelTarget() const
Definition: TreeNode.h:411
bool in_other_branch_than(const TreeNode *other) const
Definition: TreeNode.h:208
virtual ~TreeNode()
Definition: TreeNode.h:313
bool is_son_of_root() const
Definition: TreeNode.h:215
const TreeNode * ancestor_common_with(const TreeNode *other) const
Definition: TreeNode.cxx:792
virtual TreeNode * makeNode() const =0
void swap_node_info(TreeNode *other, bool ofKeeledGroups)
Definition: AP_Tree.cxx:575
int keeledStateInfo() const
Definition: TreeNode.h:422
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:853
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:392
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:435
#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:418
TreeNode * get_root_node()
Definition: TreeNode.h:390
TreeNode * get_brother()
Definition: TreeNode.h:395
ARB_edge counter_previous() const
Definition: TreeNode.h:798
static void destroy(TreeNode *that)
Definition: TreeNode.h:354
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:309
bool is_son_of(const TreeNode *Father) const
Definition: TreeNode.h:184
CONSTEXPR_INLINE bool valid(SpeciesCreationMode m)
Definition: ed4_class.hxx:2247
TreeRoot(bool deleteWithNodes_)
Definition: TreeNode.h:67
TreeNode * leftson
Definition: TreeNode.h:131
GBT_RemarkType
Definition: arbdbt.h:29
~SimpleTree() OVERRIDE
Definition: TreeNode.h:638
GBT_LEN rightlen
Definition: TreeNode.h:132
TreeNode * find_parent_with_groupInfo(bool skipKeeledBrothers=false)
Definition: TreeNode.h:471
bool is_ancestor_of(const TreeNode *descendant) const
Definition: TreeNode.h:201
int count_clades() const
Definition: TreeNode.cxx:799
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:286
ARB_edge_type
Definition: TreeNode.h:658
void predelete()
Definition: TreeNode.h:59
bool has_no_remark() const
Definition: TreeNode.h:291
bool has_bootstrap() const
Definition: TreeNode.h:101
TreeNode * dest() const
Definition: TreeNode.h:728
#define rt_assert(cond)
Definition: TreeNode.h:22
bool is_edge_to_leaf() const
Definition: TreeNode.h:824
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:746
#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:275
bool is_inside(const TreeNode *subtree) const
Definition: TreeNode.h:198
TreeNode(TreeRoot *root)
Definition: TreeNode.h:344
DEFINE_READ_ACCESSORS(TreeNode *, get_root_node, rootNode)
#define OVERRIDE
Definition: cxxforward.h:110
char * name
Definition: TreeNode.h:134
void announce_tree_constructed()
Definition: TreeNode.h:365
SimpleRoot()
Definition: TreeNode.h:651
void fixKeeledOrientation()
Definition: TreeNode.h:162
void scale_branchlengths(double factor)
Definition: TreeNode.cxx:687
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:280
GBT_LEN sum_child_lengths() const
Definition: TreeNode.cxx:697
void remove_bootstrap()
Definition: TreeNode.cxx:644
ARB_edge counter_next() const
Definition: TreeNode.h:787
float GBT_LEN
Definition: arbdb_base.h:34
bool is_inner_edge() const
Definition: TreeNode.h:832
#define NULp
Definition: cxxforward.h:114
GB_ERROR apply_aci_to_remarks(const char *aci, const GBL_call_env &callEnv)
Definition: TreeNode.cxx:652
ARB_edge find_innermost_edge()
Definition: TreeNode.cxx:395
void markAsLeaf()
Definition: TreeNode.h:172
TreeNode * keelTarget()
Definition: TreeNode.h:408
GBT_LEN get_branchlength() const
Definition: TreeNode.h:219
virtual void destroyNode(TreeNode *node) const =0
void destroy(TreeNode *that)
Definition: TreeNode.h:560
GBDATA * gb_node
Definition: TreeNode.h:133
GBT_LEN eliminate()
Definition: TreeNode.h:746
virtual void change_root(TreeNode *old, TreeNode *newroot)
Definition: TreeNode.cxx:28
void set_length(GBT_LEN len)
Definition: TreeNode.h:737
const char * get_remark() const
Definition: TreeNode.h:267
const TreeNode * find_parent_clade() const
Definition: TreeNode.h:475
const SmartCharPtr & get_remark_ptr() const
Definition: TreeNode.h:271
void set_bootstrap_seen(bool seen)
Definition: TreeNode.h:104
void delete_by_node()
Definition: TreeNode.h:94
void forget_relatives()
Definition: TreeNode.h:375
const char * get_group_name() const
Definition: TreeNode.h:446
unsigned get_leaf_count() const OVERRIDE
Definition: TreeNode.h:644
bool is_normal_group() const
Definition: TreeNode.h:430
char * GBS_global_string_copy(const char *templat,...)
Definition: arb_msg.cxx:193
TreeNode * source() const
Definition: TreeNode.h:727
static int iteration_count(int leafs_in_tree)
Definition: TreeNode.h:810