ARB
CT_dtree.cxx
Go to the documentation of this file.
1 // ============================================================= //
2 // //
3 // File : CT_dtree.cxx //
4 // Purpose : //
5 // //
6 // Institute of Microbiology (Technical University Munich) //
7 // http://www.arb-home.de/ //
8 // //
9 // ============================================================= //
10 
11 #include "CT_hash.hxx"
12 #include "CT_ctree.hxx"
13 
14 inline void inc_insert_progress(arb_progress *insertProgress) { if (insertProgress) ++(*insertProgress); }
15 
16 PART *DeconstructedTree::deconstruct_full_subtree(const TreeNode *tree, const GBT_LEN& len, const double& weight, arb_progress *insertProgress) {
22  arb_assert(tree->father);
23 
24  PART *ptree = NULp;
25  if (tree->is_leaf()) {
26  ptree = specSpace.create_tree_PART(tree, weight);
27  }
28  else {
29  if (!(insertProgress && insertProgress->aborted())) {
30  PART *pl = deconstruct_full_subtree(tree->get_leftson(), tree->leftlen, weight, insertProgress);
31  if (pl) {
32  PART *pr = deconstruct_full_subtree(tree->get_rightson(), tree->rightlen, weight, insertProgress);
33  if (!pr) {
34  arb_assert(insertProgress && insertProgress->aborted());
35  delete pl;
36  }
37  else {
38  arb_assert(pl->disjunct_from(pr));
39 
40  ptree = pl->clone();
41  ptree->add_members_from(pr);
42 
43  registry->put_part_from_complete_tree(pl, tree->get_leftson());
44  registry->put_part_from_complete_tree(pr, tree->get_rightson());
45  }
46  }
47  }
48  }
49  if (ptree) ptree->set_len(len);
50  inc_insert_progress(insertProgress);
51 
52  return ptree;
53 }
54 
55 void DeconstructedTree::deconstruct_full_rootnode(const TreeNode *tree, const double& weight, arb_progress *insertProgress) {
60  arb_assert(!tree->father);
61  arb_assert(!tree->is_leaf());
62 
63  double root_length = (tree->leftlen + tree->rightlen);
64 
65  PART *pl = deconstruct_full_subtree(tree->get_leftson(), root_length, weight, insertProgress);
66  if (!pl) {
67  arb_assert(insertProgress && insertProgress->aborted());
68  }
69  else {
70  PART *pr = deconstruct_full_subtree(tree->get_rightson(), root_length, weight, insertProgress);
71  if (!pr) {
72  arb_assert(insertProgress && insertProgress->aborted());
73  delete pl;
74  }
75  else {
76  arb_assert(pl->disjunct_from(pr));
77 
78  // add only one of the partition pl and pr (they both represent the root-edge)
79  registry->put_part_from_complete_tree(pl, tree->get_leftson());
80  delete pr;
81 
82  inc_insert_progress(insertProgress);
83  }
84  }
85 }
86 
87 PART *DeconstructedTree::deconstruct_partial_subtree(const TreeNode *tree, const GBT_LEN& len, const double& weight, const PART *partialTree, arb_progress *insertProgress) {
94  arb_assert(tree->father);
95 
96  PART *ptree = NULp;
97  if (tree->is_leaf()) {
98  ptree = specSpace.create_tree_PART(tree, weight);
99  }
100  else {
101  if (!(insertProgress && insertProgress->aborted())) {
102  PART *pl = deconstruct_partial_subtree(tree->get_leftson(), tree->leftlen, weight, partialTree, insertProgress);
103  if (pl) {
104  PART *pr = deconstruct_partial_subtree(tree->get_rightson(), tree->rightlen, weight, partialTree, insertProgress);
105  if (!pr) {
106  arb_assert(insertProgress && insertProgress->aborted());
107  delete pl;
108  }
109  else {
110  arb_assert(pl->disjunct_from(pr));
111 
112  ptree = pl->clone();
113  ptree->add_members_from(pr);
114 
115  registry->put_part_from_partial_tree(pl, partialTree, tree->get_leftson());
116  registry->put_part_from_partial_tree(pr, partialTree, tree->get_rightson());
117  }
118  }
119  }
120  }
121  if (ptree) ptree->set_len(len);
122  inc_insert_progress(insertProgress);
123 
124  return ptree;
125 }
126 
127 void DeconstructedTree::deconstruct_partial_rootnode(const TreeNode *tree, const double& weight, const PART *partialTree, arb_progress *insertProgress) {
134  arb_assert(!tree->father);
135  arb_assert(!tree->is_leaf());
136 
137  double root_length = (tree->leftlen + tree->rightlen);
138 
139  PART *pl = deconstruct_partial_subtree(tree->get_leftson(), root_length, weight, partialTree, insertProgress);
140  if (!pl) {
141  arb_assert(insertProgress && insertProgress->aborted());
142  }
143  else {
144  PART *pr = deconstruct_partial_subtree(tree->get_rightson(), root_length, weight, partialTree, insertProgress);
145  if (!pr) {
146  arb_assert(insertProgress && insertProgress->aborted());
147  delete pl;
148  }
149  else {
150  arb_assert(pl->disjunct_from(pr));
151 
152  pr->add_members_from(pl); // in 'pr' we collect the whole partialTree
153  registry->put_part_from_partial_tree(pl, partialTree, tree->get_leftson()); // because we are at root edge, we only insert one partition ('pl')
154 
155  arb_assert(pr->equals(partialTree));
156 
157  arb_assert(is_similar(pr->get_weight(), weight, 0.01));
158  registry->put_artificial_part(pr);
159  inc_insert_progress(insertProgress);
160  }
161  }
162 }
163 
164 void SpeciesSpace::add_tree_to_PART(const TreeNode *tree, PART& part) const {
165  if (tree->is_leaf()) {
166  part.setbit(get_species_index(tree->name));
167  }
168  else {
169  add_tree_to_PART(tree->get_leftson(), part);
170  add_tree_to_PART(tree->get_rightson(), part);
171  }
172 }
173 
174 PART *SpeciesSpace::create_tree_PART(const TreeNode *tree, const double& weight) const {
175  PART *part = new PART(get_PartitionSize(), weight);
176  if (part) add_tree_to_PART(tree, *part);
177  return part;
178 }
179 
void inc_insert_progress(arb_progress *insertProgress)
Definition: CT_dtree.cxx:14
#define arb_assert(cond)
Definition: arb_assert.h:245
int get_species_index(const char *name) const
Definition: CT_common.hxx:179
void put_part_from_partial_tree(PART *&part, const PART *partialTree, const TreeNode *node)
Definition: CT_hash.cxx:80
CONSTEXPR_INLINE bool is_similar(double d1, double d2, double eps)
Definition: CT_part.hxx:38
PART * clone() const
Definition: CT_part.hxx:118
GBT_LEN leftlen
Definition: TreeNode.h:132
static int weight[maxsites+1]
double get_weight() const
Definition: CT_part.hxx:179
bool aborted()
Definition: arb_progress.h:335
TreeNode * father
Definition: TreeNode.h:131
bool disjunct_from(const PART *other) const
Definition: CT_part.hxx:217
bool equals(const PART *other) const
Definition: CT_part.cxx:208
void add_members_from(const PART *source)
Definition: CT_part.cxx:185
GBT_LEN rightlen
Definition: TreeNode.h:132
Definition: CT_part.hxx:62
void put_artificial_part(PART *&part)
Definition: CT_hash.cxx:65
bool is_leaf() const
Definition: TreeNode.h:171
char * name
Definition: TreeNode.h:134
float GBT_LEN
Definition: arbdb_base.h:34
void put_part_from_complete_tree(PART *&part, const TreeNode *node)
Definition: CT_hash.cxx:46
#define NULp
Definition: cxxforward.h:114
PART * create_tree_PART(const TreeNode *tree, const double &weight) const
Definition: CT_dtree.cxx:174
void setbit(int pos)
Definition: CT_part.hxx:141
const PartitionSize * get_PartitionSize() const
Definition: CT_common.hxx:186