ARB
CT_ntree.cxx
Go to the documentation of this file.
1 // ============================================================= //
2 // //
3 // File : CT_ntree.cxx //
4 // Purpose : //
5 // //
6 // Institute of Microbiology (Technical University Munich) //
7 // http://www.arb-home.de/ //
8 // //
9 // ============================================================= //
10 
11 #include "CT_ntree.hxx"
12 #include <arbdbt.h>
13 
14 // Einen Binaerbaum erzeugen ueber einen Multitree
15 
16 static NT_NODE *ntree = NULp;
17 
18 
19 const NT_NODE *ntree_get() {
20  // returns the current ntree
21  return ntree;
22 }
23 
24 
25 static NT_NODE *new_ntnode(PART*& p) {
26  // build a new node and store the partition p in it
27  NT_NODE *n = ARB_calloc<NT_NODE>(1);
28  n->part = p;
29  n->son_list = NULp;
30 
31  p = NULp;
32  return n;
33 }
34 
35 
36 static void del_tree(NT_NODE *tree) {
37  // delete the tree
38  if (tree) {
39  for (NSONS *nsonp = tree->son_list; nsonp;) {
40  NSONS *nson_next = nsonp->next;
41  del_tree(nsonp->node);
42  free(nsonp);
43  nsonp = nson_next;
44  }
45  tree->son_list = NULp;
46 
47  // now is leaf
48  delete tree->part;
49  tree->part = NULp;
50  freenull(tree);
51  }
52 }
53 
54 
55 void ntree_init(const PartitionSize *registry) {
56  // Initialization of the tree
57  arb_assert(!ntree); // forgot to call ntree_cleanup ?
58  PART *root = registry->create_root();
59  ntree = new_ntnode(root); // Set root to completely filled partition
60 }
61 
62 void ntree_cleanup() {
63  // Destruct old tree
64  del_tree(ntree);
65  ntree = NULp;
66 }
67 
68 #if 0
69 // test if the tree is already complete (all necessary partitions are inserted)
70 static int ntree_cont(int len) {
71  return ntree_count<len;
72 }
73 #endif
74 
76  int sons = 0;
77  if (tree->son_list) {
78  for (NSONS *node = tree->son_list; node; node = node->next) {
79  sons++;
80  }
81  }
82  return sons;
83 }
84 
85 static void move_son(NT_NODE *f_node, NT_NODE *s_node, NSONS *nson) {
86  // Move son from parent-sonlist to new sonlist
87  // nson is pointer on element in parent-sonlist
88  // sonlist is new sonlist where to move in
89 
90  // Move out of parent-sonlist
91 
92  if (nson == f_node->son_list) f_node->son_list = f_node->son_list->next;
93  if (nson->prev) nson->prev->next = nson->next;
94  if (nson->next) nson->next->prev = nson->prev;
95 
96  // Move in node-sonlist
97  nson->next = s_node->son_list;
98  nson->prev = NULp;
99 
100  if (s_node->son_list) s_node->son_list->prev = nson;
101  s_node->son_list = nson;
102 }
103 
104 
105 
106 static int ins_ntree(NT_NODE *tree, PART*& newpart) {
107  /* Construct a multitree under the constraint,
108  * that the final tree may result in a binary tree.
109  *
110  * To ensure this, it is important to follow two ideas:
111  *
112  * 1. a son only fits below a father
113  * - if the father has all son-bits set AND
114  * - the father is different from the son (so it is possible to add a brother)
115  *
116  * 2. brothers are distinct (i.e. they do not share any bits)
117  */
118 
119  // Tree is leaf
120  if (!tree->son_list) {
121 #if defined(DUMP_PART_INSERTION)
122  fputs("ins_ntree part=", stdout); newpart->print();
123 #endif
124 
125  ARB_calloc(tree->son_list, 1);
126  tree->son_list->node = new_ntnode(newpart);
127 
128  return 1;
129  }
130 
131  arb_assert(newpart->is_subset_of(tree->part)); // @@@ should be invariant for entering this function (really ensured by caller?)
132 
133  // test if part fits under one son of tree. if so, recurse.
134  for (NSONS *nsonp = tree->son_list; nsonp; nsonp=nsonp->next) {
135  const PART *sonpart = nsonp->node->part;
136  if (newpart->is_subset_of(sonpart)) {
137  if (newpart->equals(sonpart)) return 0; // already inserted -> drop
138 
139  arb_assert(newpart->is_real_son_of(sonpart));
140  int res = ins_ntree(nsonp->node, newpart);
141  arb_assert(contradicted(newpart, res));
142  return res;
143  }
144  }
145 
146  // Now we are sure 'newpart' is not a son (of any of my sons)!
147  // -> Test whether it is a brother of a son
148  // If it is neither brother nor son -> don't fit here
149  for (NSONS *nsonp = tree->son_list; nsonp; nsonp=nsonp->next) {
150  const PART *sonpart = nsonp->node->part;
151  if (sonpart->overlaps_with(newpart)) {
152  if (!sonpart->is_subset_of(newpart)) {
153  arb_assert(newpart);
154  return 0;
155  }
156  arb_assert(sonpart->is_real_son_of(newpart));
157  // accept if nsonp is son of newpart (will be pulled down below)
158  }
159  }
160 
161 #if defined(DUMP_PART_INSERTION)
162  fputs("ins_ntree part=", stdout); newpart->print();
163 #endif
164 
165  // Okay, insert part here ...
166  NT_NODE *newntnode = new_ntnode(newpart);
167 
168  // Move sons from parent-sonlist into the new sons sonlist
169  {
170  NSONS *nsonp = tree->son_list;
171  while (nsonp) {
172  NSONS *nsonp_next = nsonp->next;
173  const PART *sonpart = nsonp->node->part;
174  if (sonpart->is_subset_of(newntnode->part)) {
175  arb_assert(sonpart->is_real_son_of(newntnode->part));
176  move_son(tree, newntnode, nsonp);
177  }
178  nsonp = nsonp_next;
179  }
180  }
181 
182  // insert nsons-elem in son-list of father
183  {
184  NSONS *new_son = ARB_calloc<NSONS>(1);
185 
186  new_son->node = newntnode;
187  new_son->prev = NULp;
188  new_son->next = tree->son_list;
189 
190  if (tree->son_list) tree->son_list->prev = new_son;
191  tree->son_list = new_son;
192  }
193 
194  arb_assert(!newpart);
195 
196  return 1;
197 }
198 
199 
200 
201 void insert_ntree(PART*& part) {
202  /* Insert a partition in the NTree.
203  *
204  * Tries both representations, normal and inverse partition, which
205  * represent the two subtrees at both sides of one edge.
206  *
207  * If neither can be inserted, the partition gets dropped.
208  */
209 
210  arb_assert(part->is_valid());
211 
212  bool firstCall = !ntree->son_list;
213  if (firstCall) {
214  part->set_len(part->get_len()/2); // insert as root-edge -> distribute length
215 
216  PART *inverse = part->clone();
217  inverse->invert();
218 
219  ASSERT_RESULT(bool, true, ins_ntree(ntree, part));
220  ASSERT_RESULT(bool, true, ins_ntree(ntree, inverse));
221 
222  arb_assert(!inverse);
223  }
224  else {
225  if (!ins_ntree(ntree, part)) {
226  part->invert();
227  if (!ins_ntree(ntree, part)) {
228 #if defined(DUMP_PART_INSERTION)
229  fputs("insert_ntree drops part=", stdout); part->print();
230 #endif
231  delete part; // drop non-fitting partition
232  part = NULp;
233  }
234  }
235  }
236  arb_assert(!part);
237 }
238 
239 // --------------------------------------------------------------------------------
240 
241 #if defined(NTREE_DEBUG_FUNCTIONS)
242 
243 inline void do_indent(int indent) {
244  for (int i = 0; i<indent; ++i) fputc(' ', stdout);
245 }
246 
247 void print_ntree(NT_NODE *tree, int indent) {
248  // testfunction to print a NTree
249 
250  NSONS *nsonp;
251  if (!tree) {
252  do_indent(indent);
253  fputs("tree is empty\n", stdout);
254  return;
255  }
256 
257  // print father
258  do_indent(indent);
259  fputs("(\n", stdout);
260 
261  indent++;
262 
263  do_indent(indent);
264  tree->part->print();
265 
266  // and sons
267  for (nsonp=tree->son_list; nsonp; nsonp = nsonp->next) {
268  print_ntree(nsonp->node, indent);
269  }
270 
271  indent--;
272 
273  do_indent(indent);
274  fputs(")\n", stdout);
275 }
276 
277 #define FAIL_IF_NOT_WELLFORMED
278 
279 #if defined(FAIL_IF_NOT_WELLFORMED)
280 #define SHOW_FAILURE() arb_assert(0)
281 #else
282 #define SHOW_FAILURE()
283 #endif
284 
285 bool is_well_formed(const NT_NODE *tree) {
286  // checks whether
287  // - tree has sons
288  // - all sons are part of father
289  // - all sons are distinct
290  // - father is sum of sons
291 
292  int sons = ntree_count_sons(tree);
293  bool well_formed = true;
294 
295  if (!sons) {
296  if (tree->part->get_members() != 1) { // leafs should contain single species
297  well_formed = false;
298  SHOW_FAILURE();
299  }
300  }
301  else {
302  arb_assert(tree->son_list);
303 
304  PART *pmerge = NULp;
305  for (NSONS *nson = tree->son_list; nson; nson = nson->next) {
306  PART *pson = nson->node->part;
307 
308  if (!pson->is_subset_of(tree->part)) {
309  well_formed = false;
310  SHOW_FAILURE(); // son is not a subset of father
311  }
312  if (pmerge) {
313  if (pson->overlaps_with(pmerge)) {
314  well_formed = false;
315  SHOW_FAILURE(); // sons are not distinct
316  }
317  pmerge->add_members_from(pson);
318  }
319  else {
320  pmerge = pson->clone();
321  }
322  if (!is_well_formed(nson->node)) {
323  well_formed = false;
324  SHOW_FAILURE(); // son is not well formed
325  }
326  }
327  arb_assert(pmerge);
328  if (tree->part->differs(pmerge)) {
329  well_formed = false;
330 
331 #if defined(FAIL_IF_NOT_WELLFORMED)
332  printf("tree with %i sons {\n", sons);
333  for (NSONS *nson = tree->son_list; nson; nson = nson->next) {
334  PART *pson = nson->node->part;
335  fputs(" pson =", stdout); pson->print();
336  }
337  printf("} end of tree with %i sons\n", sons);
338 
339  fputs("tree part=", stdout); tree->part->print();
340  fputs("pmerge =", stdout); pmerge->print();
341 #endif
342  SHOW_FAILURE(); // means: father is not same as sum of sons
343  }
344  delete pmerge;
345  }
346  return well_formed;
347 }
348 
349 #endif
350 
static NT_NODE * ntree
Definition: CT_ntree.cxx:16
#define arb_assert(cond)
Definition: arb_assert.h:245
void set_len(GBT_LEN length)
Definition: CT_part.hxx:167
void ntree_cleanup()
Definition: CT_ntree.cxx:62
bool differs(const PART *other) const
Definition: CT_part.hxx:220
void do_indent(ostream &out, int indent)
Definition: SEC_io.cxx:44
NSONS * prev
Definition: CT_ntree.hxx:28
int get_members() const
Definition: CT_part.hxx:225
const NT_NODE * ntree_get()
Definition: CT_ntree.cxx:19
int ntree_count_sons(const NT_NODE *tree)
Definition: CT_ntree.cxx:75
#define ASSERT_RESULT(Type, Expected, Expr)
Definition: arb_assert.h:336
bool is_valid() const
Definition: CT_part.hxx:131
PART * clone() const
Definition: CT_part.hxx:118
static void move_son(NT_NODE *f_node, NT_NODE *s_node, NSONS *nson)
Definition: CT_ntree.cxx:85
NT_NODE * node
Definition: CT_ntree.hxx:27
PART * part
Definition: CT_ntree.hxx:21
static NT_NODE * new_ntnode(PART *&p)
Definition: CT_ntree.cxx:25
void ntree_init(const PartitionSize *registry)
Definition: CT_ntree.cxx:55
fputc('\n', stderr)
PART * create_root() const
Definition: CT_part.cxx:124
NSONS * son_list
Definition: CT_ntree.hxx:22
bool equals(const PART *other) const
Definition: CT_part.cxx:208
void add_members_from(const PART *source)
Definition: CT_part.cxx:185
void invert()
Definition: CT_part.cxx:149
Definition: CT_part.hxx:62
static int ins_ntree(NT_NODE *tree, PART *&newpart)
Definition: CT_ntree.cxx:106
fputs(TRACE_PREFIX, stderr)
TYPE * ARB_calloc(size_t nelem)
Definition: arb_mem.h:81
Definition: output.h:122
bool is_real_son_of(const PART *father) const
Definition: CT_part.hxx:214
nodeptr next
static void del_tree(NT_NODE *tree)
Definition: CT_ntree.cxx:36
void insert_ntree(PART *&part)
Definition: CT_ntree.cxx:201
#define NULp
Definition: cxxforward.h:116
bool is_subset_of(const PART *other) const
Definition: CT_part.hxx:205
bool overlaps_with(const PART *other) const
Definition: CT_part.cxx:135
NSONS * next
Definition: CT_ntree.hxx:28
GBT_LEN get_len() const
Definition: CT_part.hxx:171