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