ARB
adtree.cxx
Go to the documentation of this file.
1 // =============================================================== //
2 // //
3 // File : adtree.cxx //
4 // Purpose : tree functions //
5 // //
6 // Institute of Microbiology (Technical University Munich) //
7 // http://www.arb-home.de/ //
8 // //
9 // =============================================================== //
10 
11 #include <arb_progress.h>
12 #include "gb_local.h"
13 #include <arb_strarray.h>
14 #include <set>
15 #include <limits.h>
16 #include <arb_global_defs.h>
17 #include <arb_strbuf.h>
18 #include <arb_diff.h>
19 #include <arb_defs.h>
20 #include <arb_match.h>
21 #include "TreeNode.h"
22 
23 #define GBT_PUT_DATA 1
24 #define GBT_GET_SIZE 0
25 
27  return GBT_find_or_create(gb_main, "tree_data", 7);
28 }
29 
30 // ----------------------
31 // remove leafs
32 
33 TreeNode *GBT_remove_leafs(TreeNode *tree, GBT_TreeRemoveType mode, const GB_HASH *species_hash, int *removed, int *groups_removed) { // @@@ add tests for GBT_remove_leafs()
48  if (tree->is_leaf()) {
49  if (tree->name) {
50  bool deleteSelf = false;
51  GBDATA *gb_node;
52 
53  if (species_hash) {
54  gb_node = (GBDATA*)GBS_read_hash(species_hash, tree->name);
55  gb_assert(!tree->gb_node); // don't call linked tree with 'species_hash'!
56  }
57  else gb_node = tree->gb_node;
58 
59  if (gb_node) {
61  long flag = GB_read_flag(gb_node);
62  deleteSelf = (flag && (mode&GBT_REMOVE_MARKED)) || (!flag && (mode&GBT_REMOVE_UNMARKED));
63  }
64  }
65  else { // zombie
66  if (mode & GBT_REMOVE_ZOMBIES) deleteSelf = true;
67  }
68 
69  if (deleteSelf) {
70  gb_assert(!tree->is_root_node());
71 
72  TreeRoot *troot = tree->get_tree_root();
73  tree->forget_origin();
74  destroy(tree, troot);
75 
76  tree = NULp;
77  if (removed) (*removed)++;
78  }
79  }
80  }
81  else {
82  tree->leftson = GBT_remove_leafs(tree->get_leftson(), mode, species_hash, removed, groups_removed);
83  tree->rightson = GBT_remove_leafs(tree->get_rightson(), mode, species_hash, removed, groups_removed);
84 
85  if (tree->leftson) {
86  if (!tree->rightson) { // right son deleted
87  tree = tree->fixDeletedSon();
88  }
89  // otherwise no son deleted
90  }
91  else if (tree->rightson) { // left son deleted
92  tree = tree->fixDeletedSon();
93  }
94  else { // everything deleted -> delete self
95  if (tree->name && groups_removed) (*groups_removed)++;
96 
97  TreeRoot *troot = tree->get_tree_root();
98  if (!tree->is_root_node()) tree->forget_origin();
99  tree->forget_relatives();
100  destroy(tree, troot);
101 
102  tree = NULp;
103  }
104  }
105 
106  return tree;
107 }
108 
109 // ---------------------
110 // trees order
111 
112 inline int get_tree_idx(GBDATA *gb_tree) {
113  GBDATA *gb_order = GB_entry(gb_tree, "order");
114  int idx = 0;
115  if (gb_order) {
116  idx = GB_read_int(gb_order);
117  gb_assert(idx>0); // invalid index
118  }
119  return idx;
120 }
121 
122 inline int get_max_tree_idx(GBDATA *gb_treedata) {
123  int max_idx = 0;
124  for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree)) {
125  int idx = get_tree_idx(gb_tree);
126  if (idx>max_idx) max_idx = idx;
127  }
128  return max_idx;
129 }
130 
131 inline GBDATA *get_tree_with_idx(GBDATA *gb_treedata, int at_idx) {
132  GBDATA *gb_found = NULp;
133  for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree && !gb_found; gb_tree = GB_nextChild(gb_tree)) {
134  int idx = get_tree_idx(gb_tree);
135  if (idx == at_idx) {
136  gb_found = gb_tree;
137  }
138  }
139  return gb_found;
140 }
141 
142 inline GBDATA *get_tree_infrontof_idx(GBDATA *gb_treedata, int infrontof_idx) {
143  GBDATA *gb_infrontof = NULp;
144  if (infrontof_idx) {
145  int best_idx = 0;
146  for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree)) {
147  int idx = get_tree_idx(gb_tree);
148  gb_assert(idx);
149  if (idx>best_idx && idx<infrontof_idx) {
150  best_idx = idx;
151  gb_infrontof = gb_tree;
152  }
153  }
154  }
155  return gb_infrontof;
156 }
157 
158 inline GBDATA *get_tree_behind_idx(GBDATA *gb_treedata, int behind_idx) {
159  GBDATA *gb_behind = NULp;
160  if (behind_idx) {
161  int best_idx = INT_MAX;
162  for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree)) {
163  int idx = get_tree_idx(gb_tree);
164  gb_assert(idx);
165  if (idx>behind_idx && idx<best_idx) {
166  best_idx = idx;
167  gb_behind = gb_tree;
168  }
169  }
170  }
171  return gb_behind;
172 }
173 
174 inline GB_ERROR set_tree_idx(GBDATA *gb_tree, int idx) {
175  GB_ERROR error = NULp;
176  GBDATA *gb_order = GB_entry(gb_tree, "order");
177  if (!gb_order) {
178  gb_order = GB_create(gb_tree, "order", GB_INT);
179  if (!gb_order) error = GB_await_error();
180  }
181  if (!error) error = GB_write_int(gb_order, idx);
182  return error;
183 }
184 
185 static GB_ERROR reserve_tree_idx(GBDATA *gb_treedata, int idx) {
186  GB_ERROR error = NULp;
187  GBDATA *gb_tree = get_tree_with_idx(gb_treedata, idx);
188  if (gb_tree) {
189  error = reserve_tree_idx(gb_treedata, idx+1);
190  if (!error) error = set_tree_idx(gb_tree, idx+1);
191  }
192  return error;
193 }
194 
195 static void ensure_trees_have_order(GBDATA *gb_treedata) {
196  GBDATA *gb_main = GB_get_father(gb_treedata);
197 
198  gb_assert(GB_get_root(gb_main) == gb_main);
199  gb_assert(GBT_get_tree_data(gb_main) == gb_treedata);
200 
201  GB_ERROR error = NULp;
202  GBDATA *gb_tree_order_flag = GB_search(gb_main, "/tmp/trees_have_order", GB_INT);
203 
204  if (!gb_tree_order_flag) error = GB_await_error();
205  else {
206  if (GB_read_int(gb_tree_order_flag) == 0) { // not checked yet
207  int max_idx = get_max_tree_idx(gb_treedata);
208  for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree && !error; gb_tree = GB_nextChild(gb_tree)) {
209  if (!get_tree_idx(gb_tree)) {
210  error = set_tree_idx(gb_tree, ++max_idx);
211  }
212  }
213  if (!error) error = GB_write_int(gb_tree_order_flag, 1);
214  }
215  }
216  if (error) GBK_terminatef("failed to order trees (Reason: %s)", error);
217 }
218 
219 static void tree_set_default_order(GBDATA *gb_tree) {
220  // if 'gb_tree' has no order yet, move it to the bottom (as done previously)
221  if (!get_tree_idx(gb_tree)) {
222  set_tree_idx(gb_tree, get_max_tree_idx(GB_get_father(gb_tree))+1);
223  }
224 }
225 
226 // -----------------------------
227 // tree write functions
228 
229 GB_ERROR GBT_write_group_name(GBDATA *gb_group_name, const char *new_group_name, bool pedantic) {
230  GB_ERROR error = NULp;
231 
232  gb_assert(strcmp(GB_read_key_pntr(gb_group_name), "group_name") == 0);
233 
234  if (!error) {
235  // deny several uses of '!' (at start and in the middle after '=' or ' ')
236  for (const char *em = strchr(new_group_name, '!'); em && !error; em = strchr(em+1, '!')) {
237  if (em == new_group_name || em[-1] == ' ' || em[-1] == '=') {
238  error = GBS_global_string("Invalid placement of '!' in group name '%s'\n(reserved for keeled groups)", new_group_name);
239  }
240  }
241  }
242 
243  if (!error) {
244  size_t len = strlen(new_group_name);
245  if (len >= GB_GROUP_NAME_MAX) {
246  error = GBS_global_string("Group name '%s' too long (max %i characters)", new_group_name, GB_GROUP_NAME_MAX);
247  }
248  else if (len<1) {
249  error = "Invalid empty group name";
250  }
251  }
252 
253  // warn about unwanted groupnames:
254  if (!error && pedantic) {
255  // group names which may be misinterpreted as bootstrap-values (see also #767):
256  const char *num = "0123456789.";
257  size_t numAtStart = strspn(new_group_name, num);
258 
259  if (numAtStart && !new_group_name[numAtStart]) {
260  GB_warningf("Warning: group name '%s' may be misinterpreted as bootstrap value\n"
261  "(consider prefixing a non-numeric character)",
262  new_group_name);
263  }
264 
265  // warn about '/' in group name:
266  if (strchr(new_group_name, '/')) {
267  GB_warningf("Warning: group name '%s' contains a '/'\n"
268  "(this will interfere with taxonomy!)",
269  new_group_name);
270  }
271  }
272 
273 
274  if (!error) {
275  error = GB_write_string(gb_group_name, new_group_name);
276  }
277  return error;
278 }
279 GB_ERROR GBT_write_name_to_groupData(GBDATA *gb_group, bool createNameEntry, const char *new_group_name, bool pedantic) {
280  GBDATA *gb_group_name = GB_search(gb_group, "group_name", createNameEntry ? GB_STRING : GB_FIND);
281  return gb_group_name
282  ? GBT_write_group_name(gb_group_name, new_group_name, pedantic)
283  : GB_await_error();
284 }
285 
286 static GB_ERROR gbt_write_tree_nodes(GBDATA *gb_tree, TreeNode *node, long *startid) {
287  // increments '*startid' for each inner node (not for leafs)
288 
289  GB_ERROR error = NULp;
290 
291  if (!node->is_leaf()) {
292  bool node_is_used = false;
293 
294  if (node->name && node->name[0]) {
295  if (!node->gb_node) {
296  node->gb_node = GB_create_container(gb_tree, "node");
297  if (!node->gb_node) error = GB_await_error();
298  }
299  if (!error) {
300  GBDATA *gb_name = GB_search(node->gb_node, "group_name", GB_STRING);
301  if (!gb_name) error = GB_await_error();
302  else error = GBT_write_group_name(gb_name, node->name, false);
303 
304  node_is_used = true; // wrote groupname -> node is used
305  }
306  if (!error) {
307  int keeledState = node->keeledStateInfo();
308  GBDATA *gb_keeled = GB_search(node->gb_node, "keeled", keeledState ? GB_INT : GB_FIND); // only force creation if keeledState != 0
309  if (!gb_keeled) error = keeledState || GB_have_error() ? GB_await_error() : NULp;
310  else error = GB_write_int(gb_keeled, keeledState);
311  }
312  }
313 
314  if (node->gb_node && !error) {
315  if (!node_is_used) {
316  GBDATA *gb_nonid = GB_child(node->gb_node);
317  while (gb_nonid && strcmp("id", GB_read_key_pntr(gb_nonid)) == 0) {
318  gb_nonid = GB_nextChild(gb_nonid);
319  }
320  if (gb_nonid) node_is_used = true; // found child that is not "id" -> node is used
321  }
322 
323  if (node_is_used) { // set id for used nodes
324  error = GBT_write_int(node->gb_node, "id", *startid);
325  if (!error) GB_clear_user_flag(node->gb_node, GB_USERFLAG_GHOSTNODE); // mark node as "used"
326  }
327  else { // delete unused nodes
328  error = GB_delete(node->gb_node);
329  if (!error) node->gb_node = NULp;
330  }
331  }
332 
333  (*startid)++;
334  if (!error) error = gbt_write_tree_nodes(gb_tree, node->get_leftson(), startid);
335  if (!error) error = gbt_write_tree_nodes(gb_tree, node->get_rightson(), startid);
336  }
337  return error;
338 }
339 
340 static char *gbt_write_tree_rek_new(const TreeNode *node, char *dest, long mode) {
341  if (node->is_leaf()) {
342  gb_assert(node->has_no_remark());
343  if (mode == GBT_PUT_DATA) {
344  *(dest++) = 'L';
345  if (node->name) strcpy(dest, node->name);
346 
347  char *c1;
348  while ((c1 = (char *)strchr(dest, 1))) {
349  *c1 = 2;
350  }
351  dest += strlen(dest);
352  *(dest++) = 1;
353 
354  return dest;
355  }
356  else {
357  if (node->name) return dest+1+strlen(node->name)+1; // N name term
358  return dest+1+1;
359  }
360  }
361  else {
362  { // write remark
363  const char *c1 = node->get_remark();
364  if (c1) {
365  if (mode == GBT_PUT_DATA) {
366  int c;
367  *(dest++) = 'R';
368  while ((c = *(c1++))) {
369  if (c == 1) continue;
370  *(dest++) = c;
371  }
372  *(dest++) = 1;
373  }
374  else {
375  dest += strlen(c1) + 2;
376  }
377  }
378  }
379  char buffer[40];
380  sprintf(buffer, "%g,%g;", node->leftlen, node->rightlen);
381  if (mode == GBT_PUT_DATA) {
382  *(dest++) = 'N';
383  strcpy(dest, buffer);
384  dest += strlen(buffer);
385  }
386  else {
387  dest += strlen(buffer)+1;
388  }
389  dest = gbt_write_tree_rek_new(node->get_leftson(), dest, mode);
390  dest = gbt_write_tree_rek_new(node->get_rightson(), dest, mode);
391  return dest;
392  }
393 }
394 
395 static GB_ERROR gbt_write_tree(GBDATA *gb_main, GBDATA *gb_tree, const char *tree_name, TreeNode *tree) {
405  GB_ERROR error = NULp;
406 
407  if (tree) {
408  if (tree_name) {
409  if (gb_tree) error = GBS_global_string("can't change name of existing tree (to '%s')", tree_name);
410  else {
411  error = GBT_check_tree_name(tree_name);
412  if (!error) {
413  GBDATA *gb_tree_data = GBT_get_tree_data(gb_main);
414  gb_tree = GB_search(gb_tree_data, tree_name, GB_CREATE_CONTAINER);
415 
416  if (!gb_tree) error = GB_await_error();
417  }
418  }
419  }
420  else {
421  if (!gb_tree) error = "No tree name given";
422  }
423 
424  gb_assert(gb_tree || error);
425 
426  if (!error) {
427  // mark all old style tree data for deletion
428  GBDATA *gb_node;
429  for (gb_node = GB_entry(gb_tree, "node"); gb_node; gb_node = GB_nextEntry(gb_node)) {
430  GB_raise_user_flag(gb_node, GB_USERFLAG_GHOSTNODE); // mark as "possibly unused"
431  }
432 
433  // build tree-string and save to DB
434  {
435  char *t_size = gbt_write_tree_rek_new(tree, NULp, GBT_GET_SIZE); // calc size of tree-string
436  char *ctree = ARB_calloc<char>(size_t(t_size+1)); // allocate buffer for tree-string
437 
438  t_size = gbt_write_tree_rek_new(tree, ctree, GBT_PUT_DATA); // write into buffer
439  *(t_size) = 0;
440 
441  bool was_allowed = GB_allow_compression(gb_main, false);
442  error = GBT_write_string(gb_tree, "tree", ctree);
443  GB_allow_compression(gb_main, was_allowed);
444  free(ctree);
445  }
446  }
447 
448  if (!error) {
449  // save nodes to DB
450  long size = 0;
451  error = gbt_write_tree_nodes(gb_tree, tree, &size); // reports number of nodes in 'size'
452  if (!error) error = GBT_write_int(gb_tree, "nnodes", size);
453 
454  if (!error) {
455  if (!GB_entry(gb_tree, "keep_ghostnodes")) { // see ../PARSIMONY/PARS_main.cxx@keep_ghostnodes
456  GBDATA *gb_node;
457  GBDATA *gb_node_next;
458 
459  for (gb_node = GB_entry(gb_tree, "node"); // delete all ghost nodes
460  gb_node && !error;
461  gb_node = gb_node_next)
462  {
463  GBDATA *gbd = GB_entry(gb_node, "id");
464  gb_node_next = GB_nextEntry(gb_node);
465  if (!gbd || GB_user_flag(gb_node, GB_USERFLAG_GHOSTNODE)) error = GB_delete(gb_node);
466  }
467  }
468  }
469  }
470 
471  if (!error) tree_set_default_order(gb_tree);
472  }
473 
474  return error;
475 }
476 
477 GB_ERROR GBT_write_tree(GBDATA *gb_main, const char *tree_name, TreeNode *tree) {
478  return gbt_write_tree(gb_main, NULp, tree_name, tree);
479 }
481  return gbt_write_tree(GB_get_root(gb_tree), gb_tree, NULp, tree);
482 }
483 
484 static GB_ERROR write_tree_remark(GBDATA *gb_tree, const char *remark) {
485  return GBT_write_string(gb_tree, "remark", remark);
486 }
487 GB_ERROR GBT_write_tree_remark(GBDATA *gb_main, const char *tree_name, const char *remark) {
488  return write_tree_remark(GBT_find_tree(gb_main, tree_name), remark);
489 }
490 
491 GB_ERROR GBT_log_to_tree_remark(GBDATA *gb_tree, const char *log_entry, bool stamp) {
498  GB_ERROR error = NULp;
499  const char *old_remark = GBT_read_char_pntr(gb_tree, "remark");
500  if (!old_remark && GB_have_error()) {
501  error = GB_await_error();
502  }
503  else {
504  char *new_remark = GBS_log_action_to(old_remark, log_entry, stamp);
505  error = write_tree_remark(gb_tree, new_remark);
506  free(new_remark);
507  }
508  return error;
509 }
510 GB_ERROR GBT_log_to_tree_remark(GBDATA *gb_main, const char *tree_name, const char *log_entry, bool stamp) {
518  GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
519  return gb_tree
520  ? GBT_log_to_tree_remark(gb_tree, log_entry, stamp)
521  : GBS_global_string("No such tree (%s)", tree_name);
522 }
523 
524 GB_ERROR GBT_write_tree_with_remark(GBDATA *gb_main, const char *tree_name, TreeNode *tree, const char *remark) {
525  GB_ERROR error = GBT_write_tree(gb_main, tree_name, tree);
526  if (!error && remark) error = GBT_write_tree_remark(gb_main, tree_name, remark);
527  return error;
528 }
529 
530 // ----------------------------
531 // tree read functions
532 
533 static TreeNode *gbt_read_tree_rek(char **data, long *startid, GBDATA **gb_tree_nodes, TreeRoot *troot, int size_of_tree, GB_ERROR& error) {
534  TreeNode *node = NULp;
535  if (!error) {
536  node = troot->makeNode();
537 
538  char c = *((*data)++);
539  char *p1;
540 
541  if (c=='R') {
542  p1 = strchr(*data, 1);
543  *(p1++) = 0;
544 
545  node->set_remark(*data);
546  if (node->is_inner_node_with_remark()) {
547  double bootval;
548  if (node->parse_bootstrap(bootval) == REMARK_BOOTSTRAP) {
549  if (bootval == 100.0) node->remove_remark(); // auto-remove 100% comments
550  else troot->set_bootstrap_seen(true); // activate auto-100% only if bootstrap value != 100% was seen
551  }
552  }
553 
554  c = *(p1++);
555  *data = p1;
556  }
557 
558 
559  if (c=='N') {
560  p1 = (char *)strchr(*data, ',');
561  *(p1++) = 0;
562  node->leftlen = GB_atof(*data);
563  *data = p1;
564  p1 = (char *)strchr(*data, ';');
565  *(p1++) = 0;
566  node->rightlen = GB_atof(*data);
567  *data = p1;
568  if ((*startid < size_of_tree) && (node->gb_node = gb_tree_nodes[*startid])) {
569  GBDATA *gb_group_name = GB_entry(node->gb_node, "group_name");
570  if (gb_group_name) {
571  node->name = GB_read_string(gb_group_name);
572  if (!node->name || !node->name[0]) {
573  char *auto_rename = ARB_strdup("<missing groupname>");
574  GBDATA *gb_main = GB_get_root(gb_group_name);
575 
576  const char *warn;
577  if (!node->name) {
578  warn = GBS_global_string("Unreadable 'group_name' detected (Reason: %s)", GB_await_error());
579  }
580  else {
581  warn = "Empty groupname detected";
582  }
583  warn = GBS_global_string("%s\nGroup has been named '%s'", warn, auto_rename);
584  GBT_message(gb_main, warn);
585 
586  GB_ERROR rename_error = GBT_write_group_name(gb_group_name, auto_rename, false);
587  if (rename_error) {
588  GBT_message(gb_main,
589  GBS_global_string("Failed to name group (Reason: %s)\n"
590  "Please check tree for corrupted groups, e.g. by using group search",
591  rename_error));
592  }
593  node->name = auto_rename;
594  }
595 
596  // init node according to saved "keeled" state:
597  GBDATA *gb_keeled = GB_entry(node->gb_node, "keeled");
598  if (gb_keeled) { // missing = default = not keeled
599  int keeledState = GB_read_int(gb_keeled);
600  node->setKeeledState(keeledState);
601  }
602  }
603  }
604  (*startid)++;
605  node->leftson = gbt_read_tree_rek(data, startid, gb_tree_nodes, troot, size_of_tree, error);
606  if (!node->leftson) freenull(node);
607  else {
608  node->rightson = gbt_read_tree_rek(data, startid, gb_tree_nodes, troot, size_of_tree, error);
609  if (!node->rightson) {
610  freenull(node->leftson);
611  freenull(node);
612  }
613  else {
614  node->leftson->father = node;
615  node->rightson->father = node;
616  }
617  }
618  }
619  else if (c=='L') {
620  node->markAsLeaf();
621  p1 = (char *)strchr(*data, 1);
622 
623  gb_assert(p1);
624  gb_assert(p1[0] == 1);
625 
626  *p1 = 0;
627  node->name = ARB_strdup(*data);
628  *data = p1+1;
629  }
630  else {
631  if (!c) {
632  error = "Unexpected end of tree definition.";
633  }
634  else {
635  error = GBS_global_string("Can't interpret tree definition (expected 'N' or 'L' - not '%c')", c);
636  }
637  freenull(node);
638  }
639  }
640  gb_assert(contradicted(node, error));
641  return node;
642 }
643 
644 
645 static TreeNode *read_tree_and_size_internal(GBDATA *gb_tree, GBDATA *gb_ctree, TreeRoot *troot, int node_count, GB_ERROR& error) {
646  GBDATA **gb_tree_nodes;
647  TreeNode *node = NULp; // root node
648 
649  ARB_calloc(gb_tree_nodes, node_count);
650  if (gb_tree) {
651  GBDATA *gb_node;
652 
653  for (gb_node = GB_entry(gb_tree, "node"); gb_node && !error; gb_node = GB_nextEntry(gb_node)) {
654  long i;
655  GBDATA *gbd = GB_entry(gb_node, "id");
656  if (!gbd) continue;
657 
658  i = GB_read_int(gbd);
659  if (i<0 || i >= node_count) {
660  error = "An inner node of the tree is corrupt";
661  }
662  else {
663  gb_tree_nodes[i] = gb_node;
664  }
665  }
666  }
667  if (!error) {
668  char * const treeString = GB_read_string(gb_ctree);
669  if (!treeString) {
670  error = GB_await_error();
671  }
672  else {
673  char *ts = treeString;
674  long id = 0;
675 
676  troot->set_bootstrap_seen(false); // will be update by gbt_read_tree_rek
677  node = gbt_read_tree_rek(&ts, &id, gb_tree_nodes, troot, node_count, error);
678  }
679  free(treeString);
680  }
681 
682  free(gb_tree_nodes);
683 
684  if (node) {
685  gb_assert(!node->father); // @@@ if never fails -> if condition is ok!
686 
687  if (node->has_group_info()) {
688  if (node->is_normal_group()) {
689  // workaround for #753:
690  GBDATA *gb_group = node->gb_node;
691  GBDATA *gb_main = GB_get_root(gb_group);
692  GBDATA *gb_group_name = GB_entry(gb_group, "group_name");
693 
694  gb_assert(gb_group_name);
695  if (gb_group_name) {
696  char *groupAtRoot_name = GB_read_string(gb_group_name);
697 
698  GBT_message(gb_main, GBS_global_string("Warning: invalid group '%s' at root of '%s' removed", groupAtRoot_name, GB_read_key_pntr(gb_tree)));
699  error = GB_delete(gb_group_name);
700  if (error) {
701  GBT_message(gb_main, GBS_global_string("Failed to delete 'group_name' of root-node (Reason: %s)", error));
702  error = NULp; // dont fail loading the tree
703  }
704  free(groupAtRoot_name);
705  }
706  freenull(node->name); // erase name from tree-structure
707  gb_assert(!node->is_normal_group());
708  }
709  else {
710  gb_assert(!node->keelTarget()); // root shall not host keeled group
711  // Assumed to be impossible; otherwise could be resolved by moving unkeeled group to other son(-of-root)
712  }
713  }
714  }
715  else {
716  gb_assert(error);
717  }
718 
719  gb_assert(contradicted(node, error));
720  gb_assert(implicated(node, !node->is_normal_group()));
721  return node;
722 }
723 
724 TreeNode *GBT_read_tree_and_size(GBDATA *gb_main, const char *tree_name, TreeRoot *troot, int *tree_size) {
737  GB_ERROR error = NULp;
738 
739  if (!tree_name) {
740  error = "no treename given";
741  }
742  else {
743  error = GBT_check_tree_name(tree_name);
744  if (!error) {
745  GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
746 
747  if (!gb_tree) {
748  error = "tree not found";
749  }
750  else {
751  GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
752  if (!gb_nnodes) {
753  error = "tree is empty";
754  }
755  else {
756  long size = GB_read_int(gb_nnodes);
757  if (!size) {
758  error = "has no nodes";
759  }
760  else {
761  GBDATA *gb_ctree = GB_search(gb_tree, "tree", GB_FIND);
762  if (!gb_ctree) {
763  error = "old unsupported tree format";
764  }
765  else { // "new" style tree
766  TreeNode *tree = read_tree_and_size_internal(gb_tree, gb_ctree, troot, size, error);
767  if (!error) {
768  gb_assert(tree);
769  if (tree_size) *tree_size = size; // return size of tree (=leafs-1)
771 
772  gb_assert(!tree->is_normal_group()); // root shall not be a group (see #753)
773 
774  return tree;
775  }
776 
777  gb_assert(!tree);
778  }
779  }
780  }
781  }
782  }
783  }
784 
785  gb_assert(error);
786  GB_export_errorf("Failed to read tree '%s' (Reason: %s)", tree_name, error);
787  troot->delete_by_node();
788  return NULp;
789 }
790 
791 TreeNode *GBT_read_tree(GBDATA *gb_main, const char *tree_name, TreeRoot *troot) {
793  return GBT_read_tree_and_size(gb_main, tree_name, troot, NULp);
794 }
795 
796 size_t GBT_count_leafs(const TreeNode *tree) {
797  if (tree->is_leaf()) {
798  return 1;
799  }
800  return GBT_count_leafs(tree->get_leftson()) + GBT_count_leafs(tree->get_rightson());
801 }
802 
803 static GB_ERROR gbt_invalid_because(const TreeNode *tree, const char *reason) {
804  return GBS_global_string("((TreeNode*)0x%p) %s", tree, reason);
805 }
806 
807 inline bool has_son(const TreeNode *father, const TreeNode *son) {
808  return !father->is_leaf() && (father->leftson == son || father->rightson == son);
809 }
810 
811 static GB_ERROR gbt_is_invalid(bool is_root, const TreeNode *tree) {
812  if (tree->father) {
813  if (!has_son(tree->get_father(), tree)) return gbt_invalid_because(tree, "is not son of its father");
814  }
815  else {
816  if (!is_root) return gbt_invalid_because(tree, "has no father (but isn't root)");
817  }
818 
819  GB_ERROR error = NULp;
820  if (tree->is_leaf()) {
821  if (tree->leftson) return gbt_invalid_because(tree, "is leaf, but has leftson");
822  if (tree->rightson) return gbt_invalid_because(tree, "is leaf, but has rightson");
823  }
824  else {
825  if (!tree->leftson) return gbt_invalid_because(tree, "is inner node, but has no leftson");
826  if (!tree->rightson) return gbt_invalid_because(tree, "is inner node, but has no rightson");
827 
828  error = gbt_is_invalid(false, tree->get_leftson());
829  if (!error) error = gbt_is_invalid(false, tree->get_rightson());
830  }
831  return error;
832 }
833 
835  if (tree->father) return gbt_invalid_because(tree, "is expected to be the root-node, but has father");
836  if (tree->is_leaf()) return gbt_invalid_because(tree, "is expected to be the root-node, but is a leaf (tree too small)");
837  return gbt_is_invalid(true, tree);
838 }
839 
840 // -------------------------------------------
841 // link the tree tips to the database
842 
845  GB_HASH *seen_species; // used to count duplicates
847  int zombies; // counts zombies
848  int duplicates; // counts duplicates
849 };
850 
852  GB_ERROR error = NULp;
853  if (tree->is_leaf()) {
854  tree->gb_node = NULp;
855  if (tree->name) {
856  GBDATA *gbd = (GBDATA*)GBS_read_hash(ltd->species_hash, tree->name);
857  if (gbd) tree->gb_node = gbd;
858  else ltd->zombies++;
859 
860  if (ltd->seen_species) {
861  if (GBS_read_hash(ltd->seen_species, tree->name)) ltd->duplicates++;
862  else GBS_write_hash(ltd->seen_species, tree->name, 1);
863  }
864  }
865 
866  if (ltd->progress) ++(*ltd->progress);
867  }
868  else {
869  error = gbt_link_tree_to_hash_rek(tree->get_leftson(), ltd);
870  if (!error) error = gbt_link_tree_to_hash_rek(tree->get_rightson(), ltd);
871  }
872  return error;
873 }
874 
875 static GB_ERROR GBT_link_tree_using_species_hash(TreeNode *tree, bool show_status, GB_HASH *species_hash, int *zombies, int *duplicates) {
876  GB_ERROR error;
877  link_tree_data ltd;
878  long leafs = 0;
879 
880  if (duplicates || show_status) {
881  leafs = GBT_count_leafs(tree);
882  }
883 
884  ltd.species_hash = species_hash;
885  ltd.seen_species = leafs ? GBS_create_hash(leafs, GB_IGNORE_CASE) : NULp;
886  ltd.zombies = 0;
887  ltd.duplicates = 0;
888 
889  if (show_status) {
890  ltd.progress = new arb_progress("Relinking tree to database", leafs);
891  }
892  else {
893  ltd.progress = NULp;
894  }
895 
896  error = gbt_link_tree_to_hash_rek(tree, &ltd);
898 
899  if (zombies) *zombies = ltd.zombies;
900  if (duplicates) *duplicates = ltd.duplicates;
901 
902  delete ltd.progress;
903 
904  return error;
905 }
906 
907 GB_ERROR GBT_link_tree(TreeNode *tree, GBDATA *gb_main, bool show_status, int *zombies, int *duplicates) { // @@@ most callers use NULp for last 2 args -> split like GBT_read_tree vs GBT_read_tree_and_size
922  GB_HASH *species_hash = GBT_create_species_hash(gb_main);
923  GB_ERROR error = GBT_link_tree_using_species_hash(tree, show_status, species_hash, zombies, duplicates);
924 
925  GBS_free_hash(species_hash);
926 
927  return error;
928 }
929 
934  gb_node = NULp;
935  if (!is_leaf()) {
936  get_leftson()->unlink_from_DB();
937  get_rightson()->unlink_from_DB();
938  }
939 }
941  tree->unlink_from_DB();
942 }
943 
944 // ----------------------
945 // search trees
946 
947 GBDATA *GBT_find_tree(GBDATA *gb_main, const char *tree_name) {
952  return GB_entry(GBT_get_tree_data(gb_main), tree_name);
953 }
954 
955 inline bool is_tree(GBDATA *gb_tree) {
956  if (!gb_tree) return false;
957  GBDATA *gb_tree_data = GB_get_father(gb_tree);
958  return gb_tree_data && GB_has_key(gb_tree_data, "tree_data");
959 }
960 
962  return GB_child(GBT_get_tree_data(gb_main));
963 }
964 
965 inline GBDATA *get_next_tree(GBDATA *gb_tree) {
966  if (!gb_tree) return NULp;
967  gb_assert(is_tree(gb_tree));
968  return GB_nextChild(gb_tree);
969 }
970 
972  long maxnodes = 0;
973  GBDATA *gb_largest = NULp;
974 
975  for (GBDATA *gb_tree = get_first_tree(gb_main); gb_tree; gb_tree = get_next_tree(gb_tree)) {
976  long *nnodes = GBT_read_int(gb_tree, "nnodes");
977  if (nnodes && *nnodes>maxnodes) {
978  gb_largest = gb_tree;
979  maxnodes = *nnodes;
980  }
981  }
982  return gb_largest;
983 }
984 
986  GBDATA *gb_treedata = GB_get_father(gb_tree);
987  ensure_trees_have_order(gb_treedata);
988  return get_tree_infrontof_idx(gb_treedata, get_tree_idx(gb_tree));
989 }
991  GBDATA *gb_treedata = GB_get_father(gb_tree);
992  ensure_trees_have_order(gb_treedata);
993  return get_tree_behind_idx(gb_treedata, get_tree_idx(gb_tree));
994 }
995 
997  GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
998  ensure_trees_have_order(gb_treedata);
999 
1000  GBDATA *gb_top = get_tree_with_idx(gb_treedata, 1);
1001  if (!gb_top) gb_top = get_tree_behind_idx(gb_treedata, 1);
1002  return gb_top;
1003 }
1005  GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
1006  ensure_trees_have_order(gb_treedata);
1007  return get_tree_infrontof_idx(gb_treedata, INT_MAX);
1008 }
1009 
1010 const char *GBT_existing_tree(GBDATA *gb_main, const char *tree_name) {
1011  // search for a specify existing tree (and fallback to any existing)
1012  GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
1013  if (!gb_tree) gb_tree = get_first_tree(gb_main);
1014  return GBT_get_tree_name(gb_tree);
1015 }
1016 
1018  GBDATA *gb_other = NULp;
1019  if (gb_tree) {
1020  gb_other = GBT_tree_behind(gb_tree);
1021  if (!gb_other) {
1022  gb_other = GBT_find_top_tree(GB_get_root(gb_tree));
1023  if (gb_other == gb_tree) gb_other = NULp;
1024  }
1025  }
1026  gb_assert(gb_other != gb_tree);
1027  return gb_other;
1028 }
1029 
1030 // --------------------
1031 // tree names
1032 
1033 const char *GBT_get_tree_name(GBDATA *gb_tree) {
1034  if (!gb_tree) return NULp;
1035  gb_assert(is_tree(gb_tree));
1036  return GB_read_key_pntr(gb_tree);
1037 }
1038 
1039 GB_ERROR GBT_check_tree_name(const char *tree_name) {
1040  GB_ERROR error = GB_check_key(tree_name);
1041  if (!error) {
1042  if (strncmp(tree_name, "tree_", 5) != 0) {
1043  error = "has to start with 'tree_'";
1044  }
1045  }
1046  if (error) {
1047  if (strcmp(tree_name, NO_TREE_SELECTED) == 0) {
1048  error = "no tree selected"; // overwrites existing error
1049  }
1050  else {
1051  error = GBS_global_string("not a valid treename '%s' (Reason: %s)", tree_name, error);
1052  }
1053  }
1054  return error;
1055 }
1056 
1058  return GBT_get_tree_name(find_largest_tree(gb_main));
1059 }
1060 
1062  return GBT_get_tree_name(GBT_find_bottom_tree(gb_main));
1063 }
1064 
1065 // -------------------
1066 // tree info
1067 
1068 const char *GBT_tree_info_string(GBDATA *gb_main, const char *tree_name, int maxTreeNameLen) {
1069  // maxTreeNameLen shall be the max len of the longest tree name (or -1 -> do not format)
1070 
1071  const char *result = NULp;
1072  GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
1073 
1074  if (!gb_tree) {
1075  GB_export_errorf("tree '%s' not found", tree_name);
1076  }
1077  else {
1078  GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
1079  if (!gb_nnodes) {
1080  GB_export_errorf("nnodes not found in tree '%s'", tree_name);
1081  }
1082  else {
1083  const char *sizeInfo = GBS_global_string("(%li:%i)", GB_read_int(gb_nnodes)+1, GB_read_security_write(gb_tree));
1084  GBDATA *gb_rem = GB_entry(gb_tree, "remark");
1085  int len;
1086 
1087  if (maxTreeNameLen == -1) {
1088  result = GBS_global_string("%s %11s", tree_name, sizeInfo);
1089  len = strlen(tree_name);
1090  }
1091  else {
1092  result = GBS_global_string("%-*s %11s", maxTreeNameLen, tree_name, sizeInfo);
1093  len = maxTreeNameLen;
1094  }
1095  if (gb_rem) {
1096  const char *remark = GB_read_char_pntr(gb_rem);
1097  const int remarkLen = 800;
1098  char *res2 = GB_give_other_buffer(remark, len+1+11+2+remarkLen+1);
1099 
1100  strcpy(res2, result);
1101  strcat(res2, " ");
1102  strncat(res2, remark, remarkLen);
1103 
1104  result = res2;
1105  }
1106  }
1107  }
1108  return result;
1109 }
1110 
1111 long GBT_size_of_tree(GBDATA *gb_main, const char *tree_name) {
1112  // return the number of inner nodes in binary tree (or -1 if unknown)
1113  // Note:
1114  // leafs = size + 1
1115  // inner nodes in unrooted tree = size - 1
1116 
1117  long nnodes = -1;
1118  GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
1119  if (gb_tree) {
1120  GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
1121  if (gb_nnodes) {
1122  nnodes = GB_read_int(gb_nnodes);
1123  }
1124  }
1125  return nnodes;
1126 }
1127 
1128 
1130  int idx;
1131  const char *name;
1132 
1133  bool operator<(const indexed_name& other) const { return idx < other.idx; }
1134 };
1135 
1137  // stores tree names in 'names'
1138 
1139  GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
1140  ensure_trees_have_order(gb_treedata);
1141 
1142  long tree_count = GB_number_of_subentries(gb_treedata);
1143 
1144  names.reserve(tree_count);
1145  typedef std::set<indexed_name> ordered_trees;
1146  ordered_trees trees;
1147 
1148  {
1149  int t = 0;
1150  int count = 0;
1151  for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree), ++t) {
1152  indexed_name iname;
1153  iname.name = GB_read_key_pntr(gb_tree);
1154  iname.idx = sorted ? get_tree_idx(gb_tree) : ++count;
1155 
1156  trees.insert(iname);
1157  }
1158  }
1159 
1160  if (tree_count != (long)trees.size()) { // there are duplicated "order" entries
1161  gb_assert(sorted); // should not happen in unsorted mode
1162 
1163  typedef std::set<int> ints;
1164 
1165  ints used_indices;
1166  GBDATA *gb_first_tree = GB_child(gb_treedata);
1167  GBDATA *gb_tree = gb_first_tree;
1168 
1169  while (gb_tree) {
1170  int idx = get_tree_idx(gb_tree);
1171  if (used_indices.find(idx) != used_indices.end()) { // duplicate order
1172  GB_ERROR error = reserve_tree_idx(gb_treedata, idx+1);
1173  if (!error) error = set_tree_idx(gb_tree, idx+1);
1174  if (error) GBK_terminatef("failed to fix tree-order (Reason: %s)", error);
1175 
1176  // now restart
1177  used_indices.clear();
1178  gb_tree = gb_first_tree;
1179  }
1180  else {
1181  used_indices.insert(idx);
1182  gb_tree = GB_nextChild(gb_tree);
1183  }
1184  }
1185  GBT_get_tree_names(names, gb_main, sorted);
1186  return;
1187  }
1188 
1189  for (ordered_trees::const_iterator t = trees.begin(); t != trees.end(); ++t) {
1190  names.put(t->name);
1191  }
1192 }
1193 
1194 NOT4PERL GB_ERROR GBT_move_tree(GBDATA *gb_moved_tree, GBT_ORDER_MODE mode, GBDATA *gb_target_tree) {
1195  // moves 'gb_moved_tree' next to 'gb_target_tree' (only changes tree-order)
1196  gb_assert(gb_moved_tree && gb_target_tree);
1197 
1198  GBDATA *gb_treedata = GB_get_father(gb_moved_tree);
1199  ensure_trees_have_order(gb_treedata);
1200 
1201  int target_idx = get_tree_idx(gb_target_tree);
1202  gb_assert(target_idx);
1203 
1204  if (mode == GBT_BEHIND) target_idx++;
1205 
1206  GB_ERROR error = reserve_tree_idx(gb_treedata, target_idx);
1207  if (!error) error = set_tree_idx(gb_moved_tree, target_idx);
1208 
1209  return error;
1210 }
1211 
1212 static GBDATA *get_source_and_check_target_tree(GBDATA *gb_main, const char *source_tree, const char *dest_tree, GB_ERROR& error) {
1213  GBDATA *gb_source_tree = NULp;
1214 
1215  error = GBT_check_tree_name(source_tree);
1216  if (!error) error = GBT_check_tree_name(dest_tree);
1217 
1218  if (error && strcmp(source_tree, NO_TREE_SELECTED) == 0) {
1219  error = "No tree selected";
1220  }
1221 
1222  if (!error && strcmp(source_tree, dest_tree) == 0) error = "source- and dest-tree are the same";
1223 
1224  if (!error) {
1225  gb_source_tree = GBT_find_tree(gb_main, source_tree);
1226  if (!gb_source_tree) error = GBS_global_string("tree '%s' not found", source_tree);
1227  else {
1228  GBDATA *gb_dest_tree = GBT_find_tree(gb_main, dest_tree);
1229  if (gb_dest_tree) {
1230  error = GBS_global_string("tree '%s' already exists", dest_tree);
1231  gb_source_tree = NULp;
1232  }
1233  }
1234  }
1235 
1236  gb_assert(contradicted(error, gb_source_tree));
1237  return gb_source_tree;
1238 }
1239 
1240 static GBDATA *copy_tree_container(GBDATA *gb_source_tree, const char *newName, GB_ERROR& error) {
1241  GBDATA *gb_treedata = GB_get_father(gb_source_tree);
1242  GBDATA *gb_dest_tree = GB_create_container(gb_treedata, newName);
1243 
1244  if (!gb_dest_tree) error = GB_await_error();
1245  else error = GB_copy_dropProtectMarksAndTempstate(gb_dest_tree, gb_source_tree);
1246 
1247  gb_assert(contradicted(error, gb_dest_tree));
1248  return gb_dest_tree;
1249 }
1250 
1251 GB_ERROR GBT_copy_tree(GBDATA *gb_main, const char *source_name, const char *dest_name) {
1252  GB_ERROR error;
1253  GBDATA *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error);
1254 
1255  if (gb_source_tree) {
1256  GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error);
1257  if (gb_dest_tree) {
1258  int source_idx = get_tree_idx(gb_source_tree);
1259  int dest_idx = source_idx+1;
1260 
1261  error = reserve_tree_idx(GB_get_father(gb_dest_tree), dest_idx);
1262  if (!error) error = set_tree_idx(gb_dest_tree, dest_idx);
1263  }
1264  }
1265 
1266  return error;
1267 }
1268 
1269 GB_ERROR GBT_rename_tree(GBDATA *gb_main, const char *source_name, const char *dest_name) {
1270  GB_ERROR error;
1271  GBDATA *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error);
1272 
1273  if (gb_source_tree) {
1274  GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error);
1275  if (gb_dest_tree) error = GB_delete(gb_source_tree);
1276  }
1277 
1278  return error;
1279 }
1280 
1282  if (tree->is_leaf()) {
1283  current[0] = tree->name;
1284  return current+1;
1285  }
1286  current = fill_species_name_array(current, tree->get_leftson());
1287  current = fill_species_name_array(current, tree->get_rightson());
1288  return current;
1289 }
1290 
1292  /* creates an array of all species names in a tree,
1293  * The names are not allocated (so they may change as side effect of renaming species) */
1294 
1295  size_t size = GBT_count_leafs(tree);
1296  GB_CSTR *result = ARB_calloc<GB_CSTR>(size + 1);
1297 
1298  IF_ASSERTION_USED(GB_CSTR *check =) fill_species_name_array(result, tree);
1299  gb_assert(check - size == result);
1300 
1301  if (count) *count = size;
1302 
1303  return result;
1304 }
1305 
1307  gb_assert(tree);
1308  if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); }
1309  if (tree->is_leaf()) {
1310  out.cat(tree->name);
1311  }
1312  else {
1313  out.put('(');
1314  tree2newick(tree->get_leftson(), out, format, indent+1);
1315  out.put(',');
1316  tree2newick(tree->get_rightson(), out, format, indent+1);
1317  if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); }
1318  out.put(')');
1319 
1320  if (format & (nGROUP|nREMARK)) {
1321  const char *remark = format&nREMARK ? tree->get_remark() : NULp;
1322  const char *group = NULp;
1323  const char *kgroup = NULp;
1324 
1325  if (format&nGROUP) {
1326  if (tree->is_normal_group()) group = tree->name;
1327  if (tree->is_keeled_group()) kgroup = tree->get_father()->name;
1328  }
1329 
1330  if (remark || group || kgroup) {
1331  out.put('\'');
1332  if (remark) {
1333  out.cat(remark);
1334  if (group) out.put(':');
1335  }
1336  if (group) out.cat(group);
1337  if (kgroup) {
1338  if (group) out.cat(" = ");
1339  out.put('!');
1340  out.cat(kgroup);
1341  }
1342  out.put('\'');
1343  }
1344  }
1345  }
1346 
1347  if (format&nLENGTH && !tree->is_root_node()) {
1348  out.put(':');
1349  out.nprintf(10, "%5.3f", tree->get_branchlength());
1350  }
1351 }
1352 
1353 char *GBT_tree_2_newick(const TreeNode *tree, NewickFormat format, bool compact) {
1354  // testcode-only newick exporter
1355  // see also ../SL/TREE_WRITE/TreeWrite.cxx@NEWICK_EXPORTER
1357 
1358  GBS_strstruct out(1000);
1359  if (tree) tree2newick(tree, out, format, 0);
1360  out.put(';');
1361 
1362  char *result = out.release();
1363  if (compact && (format&nWRAP)) {
1364  GB_ERROR error = NULp;
1365 
1366  char *compact1 = GBS_regreplace(result, "/[\n ]*[)]/)/", &error);
1367  if (compact1) {
1368  char *compact2 = GBS_regreplace(compact1, "/[(][\n ]*/(/", &error);
1369  if (compact2) freeset(result, compact2);
1370  free(compact1);
1371  }
1372  if (error) {
1373  fprintf(stderr, "Error in GBT_tree_2_newick: %s\n", error);
1374  gb_assert(!error); // should be impossible; falls back to 'result' if happens
1375  }
1376  }
1377  return result;
1378 }
1379 
1380 
1381 // --------------------------------------------------------------------------------
1382 
1383 #ifdef UNIT_TESTS
1384 #include <test_unit.h>
1385 
1386 static const char *getTreeOrder(GBDATA *gb_main) {
1388  GBT_get_tree_names(names, gb_main, true);
1389 
1390  char *joined = GBT_join_strings(names, '|');
1391  char *size_and_names = GBS_global_string_copy("%zu:%s", names.size(), joined);
1392  free(joined);
1393 
1394  RETURN_LOCAL_ALLOC(size_and_names);
1395 }
1396 
1397 void TEST_tree_names() {
1398  TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name(""), "not a valid treename");
1399  TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("not_a_treename"), "not a valid treename");
1400  TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("tree_bad.dot"), "not a valid treename");
1401 
1402  TEST_EXPECT_NO_ERROR(GBT_check_tree_name("tree_")); // ugly but ok
1404 }
1405 
1406 void TEST_tree_contraints() {
1407  // test minima
1408  const int MIN_LEAFS = 2;
1409 
1410  TEST_EXPECT_EQUAL(leafs_2_nodes (MIN_LEAFS, ROOTED), 3);
1411  TEST_EXPECT_EQUAL(leafs_2_nodes (MIN_LEAFS, UNROOTED), 2);
1412  TEST_EXPECT_EQUAL(leafs_2_edges (MIN_LEAFS, ROOTED), 2);
1413  TEST_EXPECT_EQUAL(leafs_2_edges (MIN_LEAFS, UNROOTED), 1);
1416 
1417  TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(3, ROOTED)); // test minimum (3 nodes rooted)
1418  TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(2, UNROOTED)); // test minimum (2 nodes unrooted)
1419 
1420  TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(2, ROOTED)); // test minimum (2 edges rooted)
1421  TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(1, UNROOTED)); // test minimum (1 edge unrooted)
1422 
1423  // test inverse functions:
1424  for (int i = 3; i<=7; ++i) {
1425  // test "leaf->XXX" and back conversions (any number of leafs is possible)
1428 
1431 
1432  bool odd = i%2;
1433  if (odd) {
1434  TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, ROOTED), ROOTED)); // rooted trees only contain odd numbers of nodes
1435  TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain odd numbers of edges
1436  }
1437  else { // even
1438  TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain even numbers of nodes
1439  TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, ROOTED), ROOTED)); // rooted trees only contain even numbers of edges
1440  }
1441 
1444 
1447 
1448  // test adding a leaf adds two nodes:
1449  int added = i+1;
1452  }
1453 }
1454 
1455 void TEST_copy_rename_delete_tree_order() {
1456  GB_shell shell;
1457  GBDATA *gb_main = GB_open("TEST_trees.arb", "r");
1458 
1459  {
1460  GB_transaction ta(gb_main);
1461 
1462  {
1464 
1465  TEST_EXPECT_EQUAL(GBT_name_of_largest_tree(gb_main), "tree_removal");
1466 
1467  TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_test");
1468  TEST_EXPECT_EQUAL(GBT_name_of_bottom_tree(gb_main), "tree_removal");
1469 
1470  long inner_nodes = GBT_size_of_tree(gb_main, "tree_nj_bs");
1471  TEST_EXPECT_EQUAL(inner_nodes, 5);
1472  TEST_EXPECT_EQUAL(GBT_tree_info_string(gb_main, "tree_nj_bs", -1), "tree_nj_bs (6:0) PRG=dnadist CORR=none FILTER=none PKG=ARB");
1473  TEST_EXPECT_EQUAL(GBT_tree_info_string(gb_main, "tree_nj_bs", 20), "tree_nj_bs (6:0) PRG=dnadist CORR=none FILTER=none PKG=ARB");
1474 
1475  {
1476  TreeNode *tree = GBT_read_tree(gb_main, "tree_nj_bs", new SimpleRoot);
1477 
1478  TEST_REJECT_NULL(tree);
1479 
1480  size_t leaf_count = GBT_count_leafs(tree);
1481 
1482  size_t species_count;
1483  GB_CSTR *species = GBT_get_names_of_species_in_tree(tree, &species_count);
1484 
1485  StrArray species2;
1486  for (int i = 0; species[i]; ++i) species2.put(ARB_strdup(species[i]));
1487 
1488  TEST_EXPECT_EQUAL(species_count, leaf_count);
1489  TEST_EXPECT_EQUAL(long(species_count), inner_nodes+1);
1490 
1491  {
1492  char *joined = GBT_join_strings(species2, '*');
1493  TEST_EXPECT_EQUAL(joined, "CloButyr*CloButy2*CorGluta*CorAquat*CurCitre*CytAquat");
1494  free(joined);
1495  }
1496 
1497  free(species);
1498 
1499  TEST_EXPECT_NEWICK(nSIMPLE, tree, "(CloButyr,(CloButy2,((CorGluta,(CorAquat,CurCitre)),CytAquat)));");
1501 
1502  destroy(tree);
1503  }
1504 
1505  TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nj_bs"), "tree_nj_bs");
1506  TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nosuch"), "tree_test");
1507  }
1508 
1509  // changing tree order
1510  {
1511  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_test|tree_tree2|tree_groups|tree_keeled|tree_keeled_2|tree_nj|tree_nj_bs|tree_removal");
1512 
1513  GBDATA *gb_test = GBT_find_tree(gb_main, "tree_test");
1514  GBDATA *gb_tree2 = GBT_find_tree(gb_main, "tree_tree2");
1515  GBDATA *gb_groups = GBT_find_tree(gb_main, "tree_groups");
1516  GBDATA *gb_keeled = GBT_find_tree(gb_main, "tree_keeled");
1517  GBDATA *gb_keeled2 = GBT_find_tree(gb_main, "tree_keeled_2");
1518  GBDATA *gb_nj = GBT_find_tree(gb_main, "tree_nj");
1519  GBDATA *gb_nj_bs = GBT_find_tree(gb_main, "tree_nj_bs");
1520  GBDATA *gb_removal = GBT_find_tree(gb_main, "tree_removal");
1521 
1522  TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_removal)); // move to bottom
1523  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_tree2|tree_groups|tree_keeled|tree_keeled_2|tree_nj|tree_nj_bs|tree_removal|tree_test");
1524 
1525  TEST_EXPECT_EQUAL(GBT_tree_behind(gb_tree2), gb_groups);
1526  TEST_EXPECT_EQUAL(GBT_tree_behind(gb_keeled), gb_keeled2);
1527  TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj), gb_nj_bs);
1528  TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj_bs), gb_removal);
1529  TEST_EXPECT_EQUAL(GBT_tree_behind(gb_removal), gb_test);
1531 
1533  TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_groups), gb_tree2);
1534  TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj), gb_keeled2);
1535  TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_nj);
1536  TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_removal), gb_nj_bs);
1537  TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_test), gb_removal);
1538 
1539  TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_tree2)); // move back to top
1540  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_test|tree_tree2|tree_groups|tree_keeled|tree_keeled_2|tree_nj|tree_nj_bs|tree_removal");
1541 
1542  TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_tree2)); // move from top
1543  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_tree2|tree_test|tree_groups|tree_keeled|tree_keeled_2|tree_nj|tree_nj_bs|tree_removal");
1544 
1545  TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_removal, GBT_INFRONTOF, gb_nj)); // move from end
1546  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_tree2|tree_test|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_nj|tree_nj_bs");
1547 
1548  TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_nj_bs, GBT_INFRONTOF, gb_nj_bs)); // noop
1549  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_tree2|tree_test|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_nj|tree_nj_bs");
1550 
1551  TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_tree2");
1552 
1553  TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_removal)), "tree_nj");
1554  TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_nj_bs)), "tree_tree2"); // last -> first
1555  }
1556 
1557  // check tree order is maintained by copy, rename and delete
1558 
1559  {
1560  // copy
1561  TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_nosuch", "tree_whatever"), "tree 'tree_nosuch' not found");
1562  TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_test", "tree_test"), "source- and dest-tree are the same");
1563  TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_tree2", "tree_test"), "tree 'tree_test' already exists");
1564 
1565  TEST_EXPECT_NO_ERROR(GBT_copy_tree(gb_main, "tree_test", "tree_test_copy"));
1566  TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_test_copy"));
1567  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "9:tree_tree2|tree_test|tree_test_copy|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_nj|tree_nj_bs");
1568 
1569  // rename
1570  TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_nj", "tree_renamed_nj"));
1571  TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_renamed_nj"));
1572  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "9:tree_tree2|tree_test|tree_test_copy|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_renamed_nj|tree_nj_bs");
1573 
1574  TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_tree2", "tree_renamed_tree2"));
1575  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "9:tree_renamed_tree2|tree_test|tree_test_copy|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_renamed_nj|tree_nj_bs");
1576 
1577  TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_test_copy", "tree_renamed_test_copy"));
1578  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "9:tree_renamed_tree2|tree_test|tree_renamed_test_copy|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_renamed_nj|tree_nj_bs");
1579 
1580  // delete
1581 
1582  GBDATA *gb_nj_bs = GBT_find_tree(gb_main, "tree_nj_bs");
1583  GBDATA *gb_renamed_nj = GBT_find_tree(gb_main, "tree_renamed_nj");
1584  GBDATA *gb_renamed_test_copy = GBT_find_tree(gb_main, "tree_renamed_test_copy");
1585  GBDATA *gb_renamed_tree2 = GBT_find_tree(gb_main, "tree_renamed_tree2");
1586  GBDATA *gb_test = GBT_find_tree(gb_main, "tree_test");
1587  GBDATA *gb_removal = GBT_find_tree(gb_main, "tree_removal");
1588  GBDATA *gb_groups = GBT_find_tree(gb_main, "tree_groups");
1589  GBDATA *gb_keeled = GBT_find_tree(gb_main, "tree_keeled");
1590  GBDATA *gb_keeled2 = GBT_find_tree(gb_main, "tree_keeled_2");
1591 
1592  TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_tree2));
1593  TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_test_copy));
1594  TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_nj));
1595  TEST_EXPECT_NO_ERROR(GB_delete(gb_removal));
1596  TEST_EXPECT_NO_ERROR(GB_delete(gb_groups));
1597  TEST_EXPECT_NO_ERROR(GB_delete(gb_keeled));
1598  TEST_EXPECT_NO_ERROR(GB_delete(gb_keeled2));
1599 
1600  // .. two trees left
1601 
1602  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test|tree_nj_bs");
1603 
1604  TEST_EXPECT_EQUAL(find_largest_tree(gb_main), gb_test);
1605  TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test);
1606  TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_nj_bs);
1607 
1608  TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs);
1609  TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs);
1610  TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_nj_bs), gb_test);
1611 
1613  TEST_EXPECT_EQUAL(GBT_tree_behind (gb_test), gb_nj_bs);
1614 
1615  TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_test);
1616  TEST_EXPECT_NULL (GBT_tree_behind (gb_nj_bs));
1617 
1618  TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_nj_bs)); // move to bottom
1619  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_nj_bs|tree_test");
1620  TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_nj_bs)); // move to top
1621  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test|tree_nj_bs");
1622 
1623  TEST_EXPECT_NO_ERROR(GB_delete(gb_nj_bs));
1624 
1625  // .. one tree left
1626 
1627  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "1:tree_test");
1628 
1629  TEST_EXPECT_EQUAL(find_largest_tree(gb_main), gb_test);
1630  TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test);
1631  TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_test);
1632 
1633  TEST_EXPECT_NULL(GBT_find_next_tree(gb_test)); // no other tree left
1636 
1637  TEST_EXPECT_NO_ERROR(GB_delete(gb_test));
1638 
1639  // .. no tree left
1640 
1641  TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "0:");
1642 
1643  TEST_EXPECT_NULL(GBT_find_tree(gb_main, "tree_test"));
1644  TEST_EXPECT_NULL(GBT_existing_tree(gb_main, "tree_whatever"));
1646  }
1647  }
1648 
1649  GB_close(gb_main);
1650 }
1651 TEST_PUBLISH(TEST_copy_rename_delete_tree_order);
1652 
1653 
1654 void TEST_group_keeling() {
1655  GB_shell shell;
1656  GBDATA *gb_main = GB_open("TEST_trees.arb", "r");
1657 
1658  {
1659  GB_transaction ta(gb_main);
1660 
1661  const char *topo_tree2 = "(((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc),(((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste)),((CloTyrob,CloTyro2),CloTyro4)'g2')'outer');";
1662  const char *topo_groups = "(((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc)'upper',(((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste))'low1',((CloTyrob,CloTyro2)'twoleafs',CloTyro4)'low2')'lower');";
1663  const char *topo_keeled = "(CloTyrob,(((((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste))'low1',((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc)'upper = !lower')'!low2',CloTyro4)'!twoleafs',CloTyro2));";
1664  // Note: shows fixed semantics (#735)
1665  // e.g.
1666  // - compare members of group 'twoleafs' in
1667  // * topo_groups (2 members) and
1668  // * topo_keeled (all but former 2 members in inverse group)
1669  // - compares locations of groups 'upper' and 'lower'
1670  // * topo_groups: located at sons of root
1671  // * topo_keeled: located at same node!
1672 
1673  {
1674  TreeNode *tree = GBT_read_tree(gb_main, "tree_tree2", new SimpleRoot);
1675  TEST_EXPECT_NEWICK(nGROUP, tree, topo_tree2);
1676  destroy(tree);
1677  }
1678  {
1679  TreeNode *tree = GBT_read_tree(gb_main, "tree_groups", new SimpleRoot);
1680  TEST_EXPECT_NEWICK(nGROUP, tree, topo_groups);
1681 
1682  TreeNode *CloTyrob = tree->findLeafNamed("CloTyrob");
1683  TEST_REJECT_NULL(CloTyrob);
1684  CloTyrob->set_root();
1685 
1686  tree = tree->get_root_node();
1687  TEST_EXPECT(tree->is_root_node());
1688 
1689  TEST_EXPECT_NEWICK(nGROUP, tree, topo_keeled);
1690 
1691  destroy(tree);
1692  }
1693  {
1694  TreeNode *tree = GBT_read_tree(gb_main, "tree_keeled", new SimpleRoot);
1695  TEST_EXPECT_NEWICK(nGROUP, tree, topo_keeled);
1696  destroy(tree);
1697  }
1698  {
1699  // Note: there is a HIDDEN_KEELED_GROUP at CytAquat (not shown here in topo, but displayed in dendro-tree-display)!
1700  // Group is found by group-search; see ../SL/GROUP_SEARCH/group_search.cxx@HIDDEN_KEELED_GROUP
1701  const char *topo_keeled2 = "(CloTyro4,((((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste))'low1',((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc)'upper = !lower')'!low2',(CloTyrob,CloTyro2)'twoleafs'));";
1702  TreeNode *tree = GBT_read_tree(gb_main, "tree_keeled_2", new SimpleRoot);
1703  TEST_EXPECT_NEWICK(nGROUP, tree, topo_keeled2);
1704  destroy(tree);
1705  }
1706  }
1707 
1708  GB_close(gb_main);
1709 }
1710 
1711 void TEST_tree_remove_leafs() {
1712  GB_shell shell;
1713  GBDATA *gb_main = GB_open("TEST_trees.arb", "r");
1714 
1715  {
1716  GBT_TreeRemoveType tested_modes[] = {
1721  };
1722 
1723  const char *org_topo = "((CloInnoc:0.371,(CloTyrob:0.009,(CloTyro2:0.017,(CloTyro3:1.046,CloTyro4:0.061):0.026):0.017):0.274):0.029,(CloBifer:0.388,((CloCarni:0.120,CurCitre:0.058):1.000,((CloPaste:0.179,(Zombie1:0.120,(CloButy2:0.009,CloButyr:0.000):0.564):0.010):0.131,(CytAquat:0.711,(CelBiazo:0.059,(CorGluta:0.522,(CorAquat:0.084,Zombie2:0.058):0.103):0.054):0.207):0.162):0.124):0.124):0.029);";
1724  const char *rem_marked_topo = "((CloInnoc:0.371,(CloTyrob:0.009,(CloTyro2:0.017,(CloTyro3:1.046,CloTyro4:0.061):0.026):0.017):0.274):0.029,(CloBifer:0.388,(CloCarni:1.000,((CloPaste:0.179,Zombie1:0.010):0.131,(CelBiazo:0.059,Zombie2:0.054):0.162):0.124):0.124):0.029);";
1725  const char *rem_unmarked_topo = "(CurCitre:1.000,((Zombie1:0.120,(CloButy2:0.009,CloButyr:0.000):0.564):0.131,(CytAquat:0.711,(CorGluta:0.522,(CorAquat:0.084,Zombie2:0.058):0.103):0.207):0.162):0.124);";
1726  const char *rem_zombies_topo = "((CloInnoc:0.371,(CloTyrob:0.009,(CloTyro2:0.017,(CloTyro3:1.046,CloTyro4:0.061):0.026):0.017):0.274):0.029,(CloBifer:0.388,((CloCarni:0.120,CurCitre:0.058):1.000,((CloPaste:0.179,(CloButy2:0.009,CloButyr:0.000):0.010):0.131,(CytAquat:0.711,(CelBiazo:0.059,(CorGluta:0.522,CorAquat:0.103):0.054):0.207):0.162):0.124):0.124):0.029);";
1727  const char *kept_marked_topo = "(CurCitre:1.000,((CloButy2:0.009,CloButyr:0.000):0.131,(CytAquat:0.711,(CorGluta:0.522,CorAquat:0.103):0.207):0.162):0.124);";
1728 
1729  const char *kept_zombies_topo = "(Zombie1:0.131,Zombie2:0.162);";
1730  const char *kept_zombies_broken_topo = "Zombie2;";
1731 
1732  const char *empty_topo = ";";
1733 
1734  GB_transaction ta(gb_main);
1735  for (unsigned mode = 0; mode<ARRAY_ELEMS(tested_modes); ++mode) {
1736  GBT_TreeRemoveType what = tested_modes[mode];
1737 
1738  for (int linked = 0; linked<=1; ++linked) {
1739  TEST_ANNOTATE(GBS_global_string("mode=%u linked=%i", mode, linked));
1740 
1741  TreeNode *tree = GBT_read_tree(gb_main, "tree_removal", new SimpleRoot);
1742  gb_assert(tree);
1743  bool once = mode == 0 && linked == 0;
1744 
1745  if (linked) {
1746  int zombies = 0;
1747  int duplicates = 0;
1748 
1749  TEST_EXPECT_NO_ERROR(GBT_link_tree(tree, gb_main, false, &zombies, &duplicates));
1750 
1751  TEST_EXPECT_EQUAL(zombies, 2);
1752  TEST_EXPECT_EQUAL(duplicates, 0);
1753  }
1754 
1755  if (once) TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo);
1756 
1757  int removedCount = 0;
1758  int groupsRemovedCount = 0;
1759 
1760  tree = GBT_remove_leafs(tree, what, NULp, &removedCount, &groupsRemovedCount);
1761 
1762  if (linked) {
1763  GBT_TreeRemoveType what_next = what;
1764 
1765  switch (what) {
1766  case GBT_REMOVE_MARKED:
1767  TEST_EXPECT_EQUAL(removedCount, 6);
1768  TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1769  TEST_EXPECT_NEWICK(nLENGTH, tree, rem_marked_topo);
1770  what_next = GBT_REMOVE_UNMARKED;
1771  break;
1772  case GBT_REMOVE_UNMARKED:
1773  TEST_EXPECT_EQUAL(removedCount, 9);
1774  TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1775  TEST_EXPECT_NEWICK(nLENGTH, tree, rem_unmarked_topo);
1776  what_next = GBT_REMOVE_MARKED;
1777  break;
1778  case GBT_REMOVE_ZOMBIES:
1779  TEST_EXPECT_EQUAL(removedCount, 2);
1780  TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1781  TEST_EXPECT_NEWICK(nLENGTH, tree, rem_zombies_topo);
1782  break;
1783  case GBT_KEEP_MARKED:
1784  TEST_EXPECT_EQUAL(removedCount, 11);
1785  TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1786  TEST_EXPECT_NEWICK(nLENGTH, tree, kept_marked_topo);
1787  {
1788  // just a test for nWRAP NewickFormat (may be removed later)
1789  const char *kept_marked_topo_wrapped =
1790  "(\n"
1791  " CurCitre:1.000,\n"
1792  " (\n"
1793  " (\n"
1794  " CloButy2:0.009,\n"
1795  " CloButyr:0.000\n"
1796  " ):0.131,\n"
1797  " (\n"
1798  " CytAquat:0.711,\n"
1799  " (\n"
1800  " CorGluta:0.522,\n"
1801  " CorAquat:0.103\n"
1802  " ):0.207\n"
1803  " ):0.162\n"
1804  " ):0.124);";
1805  TEST_EXPECT_NEWICK(NewickFormat(nLENGTH|nWRAP), tree, kept_marked_topo_wrapped);
1806 
1807  const char *expected_compacted =
1808  "(CurCitre:1.000,\n"
1809  " ((CloButy2:0.009,\n"
1810  " CloButyr:0.000):0.131,\n"
1811  " (CytAquat:0.711,\n"
1812  " (CorGluta:0.522,\n"
1813  " CorAquat:0.103):0.207):0.162):0.124);";
1814  char *compacted = GBT_tree_2_newick(tree, NewickFormat(nLENGTH|nWRAP), true);
1815  TEST_EXPECT_EQUAL(compacted, expected_compacted);
1816  free(compacted);
1817  }
1818  what_next = GBT_REMOVE_MARKED;
1819  break;
1820  }
1821 
1822  if (what_next != what) {
1823  gb_assert(tree);
1824  tree = GBT_remove_leafs(tree, what_next, NULp, &removedCount, &groupsRemovedCount);
1825 
1826  switch (what) {
1827  case GBT_REMOVE_MARKED: // + GBT_REMOVE_UNMARKED
1828  TEST_EXPECT_EQUAL(removedCount, 16);
1829  TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1830  TEST_EXPECT_NEWICK__BROKEN(nLENGTH, tree, kept_zombies_topo);
1831  TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_broken_topo); // @@@ invalid topology (single leaf)
1832  break;
1833  case GBT_REMOVE_UNMARKED: // + GBT_REMOVE_MARKED
1834  TEST_EXPECT_EQUAL(removedCount, 15);
1835  TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1836  TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_topo);
1837  break;
1838  case GBT_KEEP_MARKED: // + GBT_REMOVE_MARKED
1839  TEST_EXPECT_EQUAL(removedCount, 17);
1840  TEST_EXPECT_EQUAL__BROKEN(groupsRemovedCount, 2, 1); // @@@ expect that all groups have been removed!
1841  TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1842  TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo);
1843  break;
1844  default:
1845  TEST_REJECT(true);
1846  break;
1847  }
1848  }
1849  }
1850  else {
1851  switch (what) {
1852  case GBT_REMOVE_MARKED:
1853  case GBT_REMOVE_UNMARKED:
1854  TEST_EXPECT_EQUAL(removedCount, 0);
1855  TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1856  TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo);
1857  break;
1858  case GBT_REMOVE_ZOMBIES:
1859  case GBT_KEEP_MARKED:
1860  TEST_EXPECT_EQUAL(removedCount, 17);
1861  TEST_EXPECT_EQUAL(groupsRemovedCount, 2);
1862  TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo);
1863  break;
1864  }
1865  }
1866 
1867  if (tree) {
1868  gb_assert(tree->is_root_node());
1869  destroy(tree);
1870  }
1871  }
1872  }
1873  }
1874 
1875  GB_close(gb_main);
1876 }
1877 TEST_PUBLISH(TEST_tree_remove_leafs);
1878 
1879 
1880 #endif // UNIT_TESTS
GB_ERROR GB_check_key(const char *key) __ATTR__USERESULT
Definition: adstring.cxx:85
GB_ERROR GB_copy_dropProtectMarksAndTempstate(GBDATA *dest, GBDATA *source)
Definition: arbdb.cxx:2144
Definition: arbdbt.h:48
const char * GB_ERROR
Definition: arb_core.h:25
void unlink_from_DB()
Definition: adtree.cxx:930
string result
GBDATA * GB_open(const char *path, const char *opent)
Definition: ad_load.cxx:1363
GBT_TreeRemoveType
Definition: arbdbt.h:31
void put(const char *elem)
Definition: arb_strarray.h:199
size_t size() const
Definition: arb_strarray.h:85
AliDataPtr format(AliDataPtr data, const size_t wanted_len, GB_ERROR &error)
Definition: insdel.cxx:615
TreeNode * GBT_remove_leafs(TreeNode *tree, GBT_TreeRemoveType mode, const GB_HASH *species_hash, int *removed, int *groups_removed)
Definition: adtree.cxx:33
GBT_RemarkType parse_bootstrap(double &bootstrap) const
Definition: TreeNode.h:261
long GB_read_int(GBDATA *gbd)
Definition: arbdb.cxx:723
GBDATA * GB_child(GBDATA *father)
Definition: adquery.cxx:322
#define implicated(hypothesis, conclusion)
Definition: arb_assert.h:289
TreeNode * findLeafNamed(const char *wantedName)
Definition: TreeNode.cxx:274
long GBS_write_hash(GB_HASH *hs, const char *key, long val)
Definition: adhash.cxx:457
GBDATA * GBT_get_tree_data(GBDATA *gb_main)
Definition: adtree.cxx:26
bool operator<(const indexed_name &other) const
Definition: adtree.cxx:1133
static GB_CSTR * fill_species_name_array(GB_CSTR *current, const TreeNode *tree)
Definition: adtree.cxx:1281
const TreeNode * get_root_node() const
Definition: TreeNode.h:382
GB_ERROR GB_write_string(GBDATA *gbd, const char *s)
Definition: arbdb.cxx:1385
bool has_group_info() const
Definition: TreeNode.h:403
GBDATA * GBT_find_next_tree(GBDATA *gb_tree)
Definition: adtree.cxx:1017
static GB_ERROR reserve_tree_idx(GBDATA *gb_treedata, int idx)
Definition: adtree.cxx:185
char * GBT_tree_2_newick(const TreeNode *tree, NewickFormat format, bool compact)
Definition: adtree.cxx:1353
virtual void set_root()
Definition: TreeNode.cxx:206
GB_ERROR GBT_rename_tree(GBDATA *gb_main, const char *source_name, const char *dest_name)
Definition: adtree.cxx:1269
GBDATA * get_next_tree(GBDATA *gb_tree)
Definition: adtree.cxx:965
GBDATA * GB_nextEntry(GBDATA *entry)
Definition: adquery.cxx:339
void forget_origin()
Definition: TreeNode.h:373
static GBDATA * get_source_and_check_target_tree(GBDATA *gb_main, const char *source_tree, const char *dest_tree, GB_ERROR &error)
Definition: adtree.cxx:1212
#define NO_TREE_SELECTED
int get_max_tree_idx(GBDATA *gb_treedata)
Definition: adtree.cxx:122
TreeNode * GBT_read_tree(GBDATA *gb_main, const char *tree_name, TreeRoot *troot)
Definition: adtree.cxx:791
char * ARB_strdup(const char *str)
Definition: arb_string.h:27
void setKeeledState(int keeledState)
Definition: TreeNode.h:424
CONSTEXPR_INLINE int nodes_2_innerNodes(int nodes, TreeModel model)
Definition: arbdbt.h:74
TreeRoot * get_tree_root() const
Definition: TreeNode.h:380
GB_ERROR GBT_copy_tree(GBDATA *gb_main, const char *source_name, const char *dest_name)
Definition: adtree.cxx:1251
static GB_ERROR gbt_is_invalid(bool is_root, const TreeNode *tree)
Definition: adtree.cxx:811
#define TEST_EXPECT_NEWICK__BROKEN(format, tree, expected_newick)
Definition: test_unit.h:1450
const char * GBS_global_string(const char *templat,...)
Definition: arb_msg.cxx:204
GBDATA * GBT_find_tree(GBDATA *gb_main, const char *tree_name)
Definition: adtree.cxx:947
bool GB_have_error()
Definition: arb_msg.cxx:349
CONSTEXPR_INLINE int leafs_2_innerNodes(int leafs, TreeModel model)
Definition: arbdbt.h:70
void GBK_terminatef(const char *templat,...)
Definition: arb_msg.cxx:477
char * release()
Definition: arb_strbuf.h:80
const char * GBT_tree_info_string(GBDATA *gb_main, const char *tree_name, int maxTreeNameLen)
Definition: adtree.cxx:1068
void nput(char c, size_t count)
Definition: arb_strbuf.h:143
void GBS_free_hash(GB_HASH *hs)
Definition: adhash.cxx:541
GB_HASH * GBT_create_species_hash(GBDATA *gb_main)
Definition: adhashtools.cxx:36
char * GBS_regreplace(const char *str, const char *regReplExpr, GB_ERROR *error)
Definition: arb_match.cxx:175
void cat(const char *from)
Definition: arb_strbuf.h:158
bool GB_allow_compression(GBDATA *gb_main, bool allow_compression)
Definition: arbdb.cxx:1895
const char * GBT_existing_tree(GBDATA *gb_main, const char *tree_name)
Definition: adtree.cxx:1010
static char * gbt_write_tree_rek_new(const TreeNode *node, char *dest, long mode)
Definition: adtree.cxx:340
static TreeNode * gbt_read_tree_rek(char **data, long *startid, GBDATA **gb_tree_nodes, TreeRoot *troot, int size_of_tree, GB_ERROR &error)
Definition: adtree.cxx:533
const char * GBT_name_of_largest_tree(GBDATA *gb_main)
Definition: adtree.cxx:1057
#define ARRAY_ELEMS(array)
Definition: arb_defs.h:19
char buffer[MESSAGE_BUFFERSIZE]
Definition: seq_search.cxx:34
GBDATA * GB_get_father(GBDATA *gbd)
Definition: arbdb.cxx:1720
static TreeNode * read_tree_and_size_internal(GBDATA *gb_tree, GBDATA *gb_ctree, TreeRoot *troot, int node_count, GB_ERROR &error)
Definition: adtree.cxx:645
GBT_LEN leftlen
Definition: TreeNode.h:132
TreeNode * rightson
Definition: TreeNode.h:131
#define NOT4PERL
Definition: arbdb_base.h:23
GB_ERROR GB_delete(GBDATA *&source)
Definition: arbdb.cxx:1904
static GB_ERROR gbt_link_tree_to_hash_rek(TreeNode *tree, link_tree_data *ltd)
Definition: adtree.cxx:851
GB_BUFFER GB_give_other_buffer(GB_CBUFFER buffer, long size)
Definition: arbdb.cxx:357
static GB_ERROR gbt_write_tree(GBDATA *gb_main, GBDATA *gb_tree, const char *tree_name, TreeNode *tree)
Definition: adtree.cxx:395
TreeNode * GBT_read_tree_and_size(GBDATA *gb_main, const char *tree_name, TreeRoot *troot, int *tree_size)
Definition: adtree.cxx:724
GBDATA * GBT_find_bottom_tree(GBDATA *gb_main)
Definition: adtree.cxx:1004
POS_TREE1 * father
Definition: probe_tree.h:39
static FullNameMap names
void GB_raise_user_flag(GBDATA *gbd, unsigned char user_bit)
Definition: arbdb.cxx:2743
#define TEST_PUBLISH(testfunction)
Definition: test_unit.h:1485
bool GB_user_flag(GBDATA *gbd, unsigned char user_bit)
Definition: arbdb.cxx:2738
static GBDATA * find_largest_tree(GBDATA *gb_main)
Definition: adtree.cxx:971
CONSTEXPR_INLINE int leafs_2_nodes(int leafs, TreeModel model)
Definition: arbdbt.h:53
static void ensure_trees_have_order(GBDATA *gb_treedata)
Definition: adtree.cxx:195
GB_ERROR GB_await_error()
Definition: arb_msg.cxx:353
NOT4PERL long * GBT_read_int(GBDATA *gb_container, const char *fieldpath)
Definition: adtools.cxx:327
GBDATA * GBT_find_top_tree(GBDATA *gb_main)
Definition: adtree.cxx:996
GB_ERROR GBT_overwrite_tree(GBDATA *gb_tree, TreeNode *tree)
Definition: adtree.cxx:480
GBDATA * GB_create_container(GBDATA *father, const char *key)
Definition: arbdb.cxx:1827
#define TEST_EXPECT(cond)
Definition: test_unit.h:1313
GBT_ORDER_MODE
Definition: arbdbt.h:43
void GB_warningf(const char *templat,...)
Definition: arb_msg.cxx:490
#define TEST_EXPECT_NEWICK(format, tree, expected_newick)
Definition: test_unit.h:1449
GB_CSTR GB_read_key_pntr(GBDATA *gbd)
Definition: arbdb.cxx:1654
#define GBT_GET_SIZE
Definition: adtree.cxx:24
virtual TreeNode * makeNode() const =0
GBDATA * GB_create(GBDATA *father, const char *key, GB_TYPES type)
Definition: arbdb.cxx:1779
GB_ERROR GBT_write_tree_with_remark(GBDATA *gb_main, const char *tree_name, TreeNode *tree, const char *remark)
Definition: adtree.cxx:524
GB_ERROR GBT_is_invalid(const TreeNode *tree)
Definition: adtree.cxx:834
static void tree_set_default_order(GBDATA *gb_tree)
Definition: adtree.cxx:219
long GB_number_of_subentries(GBDATA *gbd)
Definition: arbdb.cxx:2880
int keeledStateInfo() const
Definition: TreeNode.h:421
int GB_read_security_write(GBDATA *gbd)
Definition: arbdb.cxx:1570
CONSTEXPR_INLINE int leafs_2_edges(int leafs, TreeModel model)
Definition: arbdbt.h:61
#define TEST_EXPECT_EQUAL__BROKEN(expr, want, got)
Definition: test_unit.h:1284
static int group[MAXN+1]
Definition: ClustalV.cxx:65
#define GBT_PUT_DATA
Definition: adtree.cxx:23
GB_ERROR GBT_write_tree(GBDATA *gb_main, const char *tree_name, TreeNode *tree)
Definition: adtree.cxx:477
#define TEST_REJECT(cond)
Definition: test_unit.h:1315
#define TEST_REJECT_NULL(n)
Definition: test_unit.h:1310
GB_ERROR set_tree_idx(GBDATA *gb_tree, int idx)
Definition: adtree.cxx:174
TreeNode * father
Definition: TreeNode.h:131
static void error(const char *msg)
Definition: mkptypes.cxx:96
GBDATA * GB_get_root(GBDATA *gbd)
Definition: arbdb.cxx:1738
bool is_root_node() const
Definition: TreeNode.h:391
GB_CSTR * GBT_get_names_of_species_in_tree(const TreeNode *tree, size_t *count)
Definition: adtree.cxx:1291
bool is_keeled_group() const
Definition: TreeNode.h:434
#define RETURN_LOCAL_ALLOC(mallocation)
Definition: smartptr.h:310
void GBT_get_tree_names(ConstStrArray &names, GBDATA *gb_main, bool sorted)
Definition: adtree.cxx:1136
GB_write_int const char GB_write_autoconv_string WRITE_SKELETON(write_pointer, GBDATA *,"%p", GB_write_pointer) char *AW_awa if)(!gb_var) return strdup("")
Definition: AW_awar.cxx:166
NOT4PERL GB_ERROR GBT_move_tree(GBDATA *gb_moved_tree, GBT_ORDER_MODE mode, GBDATA *gb_target_tree)
Definition: adtree.cxx:1194
size_t GBT_count_leafs(const TreeNode *tree)
Definition: adtree.cxx:796
static SearchTree * tree[SEARCH_PATTERNS]
Definition: ED4_search.cxx:629
GBDATA * get_tree_with_idx(GBDATA *gb_treedata, int at_idx)
Definition: adtree.cxx:131
int GB_read_flag(GBDATA *gbd)
Definition: arbdb.cxx:2784
bool is_tree(GBDATA *gb_tree)
Definition: adtree.cxx:955
static GB_ERROR write_tree_remark(GBDATA *gb_tree, const char *remark)
Definition: adtree.cxx:484
GB_ERROR GBT_log_to_tree_remark(GBDATA *gb_tree, const char *log_entry, bool stamp)
Definition: adtree.cxx:491
NewickFormat
Definition: arbdb_base.h:68
TreeNode * leftson
Definition: TreeNode.h:131
char * GBS_log_action_to(const char *comment, const char *action, bool stamp)
Definition: adstring.cxx:990
GB_ERROR GBT_link_tree(TreeNode *tree, GBDATA *gb_main, bool show_status, int *zombies, int *duplicates)
Definition: adtree.cxx:907
#define RUNNING_TEST()
Definition: arb_assert.h:278
bool GB_has_key(GBDATA *gbd, const char *key)
Definition: arbdb.cxx:1705
Definition: arbdb.h:86
GBT_LEN rightlen
Definition: TreeNode.h:132
GB_ERROR GB_write_int(GBDATA *gbd, long i)
Definition: arbdb.cxx:1244
static GB_ERROR gbt_write_tree_nodes(GBDATA *gb_tree, TreeNode *node, long *startid)
Definition: adtree.cxx:286
long int flag
Definition: f2c.h:39
void remove_remark()
Definition: TreeNode.h:285
const char * GBT_get_tree_name(GBDATA *gb_tree)
Definition: adtree.cxx:1033
bool has_no_remark() const
Definition: TreeNode.h:290
static GB_ERROR GBT_link_tree_using_species_hash(TreeNode *tree, bool show_status, GB_HASH *species_hash, int *zombies, int *duplicates)
Definition: adtree.cxx:875
CONSTEXPR_INLINE int edges_2_leafs(int edges, TreeModel model)
Definition: arbdbt.h:65
char * GBT_join_strings(const CharPtrArray &strings, char separator)
GB_ERROR GB_export_errorf(const char *templat,...)
Definition: arb_msg.cxx:264
long GBT_size_of_tree(GBDATA *gb_main, const char *tree_name)
Definition: adtree.cxx:1111
bool is_leaf() const
Definition: TreeNode.h:171
TYPE * ARB_calloc(size_t nelem)
Definition: arb_mem.h:81
#define IF_ASSERTION_USED(x)
Definition: arb_assert.h:308
TreeNode * fixDeletedSon()
Definition: TreeNode.cxx:719
#define TEST_EXPECT_NULL(n)
Definition: test_unit.h:1307
#define gb_assert(cond)
Definition: arbdbt.h:11
#define GB_GROUP_NAME_MAX
Definition: arbdbt.h:16
static GBDATA * copy_tree_container(GBDATA *gb_source_tree, const char *newName, GB_ERROR &error)
Definition: adtree.cxx:1240
GBDATA * get_tree_infrontof_idx(GBDATA *gb_treedata, int infrontof_idx)
Definition: adtree.cxx:142
bool is_inner_node_with_remark() const
Definition: TreeNode.h:274
GB_ERROR GBT_write_string(GBDATA *gb_container, const char *fieldpath, const char *content)
Definition: adtools.cxx:451
Definition: output.h:122
const char * name
Definition: adtree.cxx:1131
char * name
Definition: TreeNode.h:134
void nprintf(size_t maxlen, const char *templat,...) __ATTR__FORMAT_MEMBER(2)
Definition: arb_strbuf.cxx:29
void announce_tree_constructed()
Definition: TreeNode.h:364
GBDATA * GBT_tree_behind(GBDATA *gb_tree)
Definition: adtree.cxx:990
char * GB_read_string(GBDATA *gbd)
Definition: arbdb.cxx:903
GBDATA * get_first_tree(GBDATA *gb_main)
Definition: adtree.cxx:961
GBDATA * GBT_find_or_create(GBDATA *father, const char *key, long delete_level)
Definition: adtools.cxx:42
CONSTEXPR_INLINE int nodes_2_leafs(int nodes, TreeModel model)
Definition: arbdbt.h:57
void GBT_message(GBDATA *gb_main, const char *msg)
Definition: adtools.cxx:238
bool has_son(const TreeNode *father, const TreeNode *son)
Definition: adtree.cxx:807
GB_ERROR GBT_check_tree_name(const char *tree_name)
Definition: adtree.cxx:1039
GB_ERROR GBT_write_group_name(GBDATA *gb_group_name, const char *new_group_name, bool pedantic)
Definition: adtree.cxx:229
void set_remark(const char *newRemark)
Definition: TreeNode.h:279
float GB_atof(const char *str)
Definition: arbdb.cxx:184
#define TEST_EXPECT_NO_ERROR(call)
Definition: test_unit.h:1107
void GB_clear_user_flag(GBDATA *gbd, unsigned char user_bit)
Definition: arbdb.cxx:2748
void GBT_unlink_tree(TreeNode *tree)
Definition: adtree.cxx:940
#define NULp
Definition: cxxforward.h:97
#define TEST_EXPECT_ERROR_CONTAINS(call, part)
Definition: test_unit.h:1103
void reserve(size_t forElems)
Definition: arb_strarray.h:82
void markAsLeaf()
Definition: TreeNode.h:172
GB_ERROR GBT_write_tree_remark(GBDATA *gb_main, const char *tree_name, const char *remark)
Definition: adtree.cxx:487
GBDATA * get_tree_behind_idx(GBDATA *gb_treedata, int behind_idx)
Definition: adtree.cxx:158
GBDATA * GB_nextChild(GBDATA *child)
Definition: adquery.cxx:326
TreeNode * keelTarget()
Definition: TreeNode.h:407
GBT_LEN get_branchlength() const
Definition: TreeNode.h:219
GB_transaction ta(gb_var)
GB_ERROR GBT_write_int(GBDATA *gb_container, const char *fieldpath, long content)
Definition: adtools.cxx:471
int get_tree_idx(GBDATA *gb_tree)
Definition: adtree.cxx:112
void destroy(TreeNode *that)
Definition: TreeNode.h:559
GB_CSTR GB_read_char_pntr(GBDATA *gbd)
Definition: arbdb.cxx:898
GBDATA * gb_node
Definition: TreeNode.h:133
GBDATA * gb_main
Definition: adname.cxx:33
static void tree2newick(const TreeNode *tree, GBS_strstruct &out, NewickFormat format, int indent)
Definition: adtree.cxx:1306
GB_ERROR GBT_write_name_to_groupData(GBDATA *gb_group, bool createNameEntry, const char *new_group_name, bool pedantic)
Definition: adtree.cxx:279
GBDATA * GB_search(GBDATA *gbd, const char *fieldpath, GB_TYPES create)
Definition: adquery.cxx:531
const char * get_remark() const
Definition: TreeNode.h:266
void set_bootstrap_seen(bool seen)
Definition: TreeNode.h:104
void delete_by_node()
Definition: TreeNode.h:94
void forget_relatives()
Definition: TreeNode.h:374
const char * GBT_read_char_pntr(GBDATA *gb_container, const char *fieldpath)
Definition: adtools.cxx:307
GBDATA * GBT_tree_infrontof(GBDATA *gb_tree)
Definition: adtree.cxx:985
const char * GB_CSTR
Definition: arbdb_base.h:25
#define TEST_EXPECT_EQUAL(expr, want)
Definition: test_unit.h:1283
bool is_normal_group() const
Definition: TreeNode.h:429
long GBS_read_hash(const GB_HASH *hs, const char *key)
Definition: adhash.cxx:395
GBDATA * GB_entry(GBDATA *father, const char *key)
Definition: adquery.cxx:334
const char * GBT_name_of_bottom_tree(GBDATA *gb_main)
Definition: adtree.cxx:1061
#define GB_USERFLAG_GHOSTNODE
Definition: arbdb.h:57
char * GBS_global_string_copy(const char *templat,...)
Definition: arb_msg.cxx:195
void GB_close(GBDATA *gbd)
Definition: arbdb.cxx:649
GB_HASH * GBS_create_hash(long estimated_elements, GB_CASE case_sens)
Definition: adhash.cxx:253
void put(char c)
Definition: arb_strbuf.h:138
Definition: arbdb.h:66
static GB_ERROR gbt_invalid_because(const TreeNode *tree, const char *reason)
Definition: adtree.cxx:803