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