Context Navigation

← Previous Revision
Next Revision →
Blame
Revision Log

adtree.cxx

Visit:

Last change on this file was 19518, checked in by westram, 3 months ago
full update from 'trunk' into 'help' adds: log:branches/ali@19183:19205,19357:19424 log:branches/gde@19228:19233,19460:19479 log:branches/macros@19482:19488 log:branches/nds@18843:18882 log:branches/progress@18885:18958 log:branches/refactor@19286:19345 log:branches/sina@18984:19244 log:branches/split@19077:19099,19102:19166,19169:19221 log:branches/stable@18903:18906,18908 log:trunk@18813:19517
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 75.4 KB

Line
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
27	GBDATA GBT_get_tree_data(GBDATA gb_main) {
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()
35	/*! Remove leafs from given 'tree'.
36	* @param tree tree from which species will be removed
37	* @param mode defines what to remove
38	* @param species_hash hash translation from leaf-name to species-dbnode (not needed if tree is linked; see GBT_link_tree)
39	* @param removed will be incremented for each removed leaf (if !NULp)
40	* @param groups_removed will be incremented for each removed group (if !NULp)
41	* @return new root node
42	*
43	* if 'species_hash' is not provided and tree is not linked,
44	* the function will silently act strange:
45	* - GBT_REMOVE_MARKED and GBT_REMOVE_UNMARKED will remove any leaf
46	* - GBT_REMOVE_ZOMBIES and GBT_KEEP_MARKED will remove all leafs
47	*/
48
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) {
61	if (mode & (GBT_REMOVE_MARKED\|GBT_REMOVE_UNMARKED)) {
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) {
442	/*! writes a tree to the database.
443	*
444	* If tree is loaded by function GBT_read_tree(..) then 'tree_name' should be NULp
445	* else 'gb_tree' should be set to NULp
446	*
447	* To copy a tree call GBT_copy_tree() or copy_tree_container()
448	* or set recursively all tree->gb_node variables to zero (that unlinks the tree),
449	*/
450
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	}
526	GB_ERROR GBT_overwrite_tree(GBDATA gb_tree, TreeNode tree) {
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) {
538	/*! append 'log_entry' to tree comment
539	* @param gb_tree the tree
540	* @param log_entry text to append
541	* @param stamp true -> prefix date before 'log_entry'
542	* @return error in case of failure
543	*/
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) {
557	/*! append 'log_entry' to tree comment
558	* @param gb_main database
559	* @param tree_name name of tree
560	* @param log_entry text to append
561	* @param stamp true -> prefix date before 'log_entry'
562	* @return error in case of failure
563	*/
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) {
771	/*! Loads a tree from DB into any user defined structure.
772	*
773	* @param gb_main DB root node
774	* @param tree_name is the name of the tree in the db
775	* @param troot constructs the tree-node instances
776	* @param tree_size if specified -> will be set to "size of tree" (aka number of leafs minus 1)
777	*
778	* @return
779	* - NULp if any error occurs (which is exported then)
780	* - root of loaded tree (dynamic type depends on 'nodeFactory')
781	*/
782
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)
816	tree->announce_tree_constructed();
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) {
838	//! @see GBT_read_tree_and_size()
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
880	GB_ERROR GBT_is_invalid(const TreeNode *tree) {
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
889	struct link_tree_data {
890	GB_HASH *species_hash;
891	GB_HASH *seen_species; // used to count duplicates
892	arb_progress *progress;
893	int zombies; // counts zombies
894	int duplicates; // counts duplicates
895	};
896
897	static GB_ERROR gbt_link_tree_to_hash_rek(TreeNode tree, link_tree_data ltd) {
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);
943	if (ltd.seen_species) GBS_free_hash(ltd.seen_species);
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
954	/*! Link a given tree to the database. That means that for all tips the member
955	* 'gb_node' is set to the database container holding the species data.
956	*
957	* @param tree which will be linked to DB
958	* @param gb_main DB root node
959	* @param show_status show a progress indicator?
960	* @param zombies if specified -> set to number of zombies (aka non-existing species) in tree
961	* @param duplicates if specified -> set to number of duplicated species in tree
962	*
963	* @return error on failure
964	*
965	* @see GBT_unlink_tree()
966	*/
967
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
976	void TreeNode::unlink_from_DB() {
977	/*! Unlink tree from the database.
978	* @see GBT_link_tree()
979	*/
980	gb_node = NULp;
981	if (!is_leaf()) {
982	get_leftson()->unlink_from_DB();
983	get_rightson()->unlink_from_DB();
984	}
985	}
986	void GBT_unlink_tree(TreeNode *tree) {
987	tree->unlink_from_DB();
988	}
989
990	// ----------------------
991	// search trees
992
993	GBDATA GBT_find_tree(GBDATA gb_main, const char *tree_name) {
994	/*! @return
995	* - DB tree container associated with tree_name
996	* - NULp if no such tree exists
997	*/
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
1007	inline GBDATA get_first_tree(GBDATA gb_main) {
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
1017	static GBDATA find_largest_tree(GBDATA gb_main) {
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
1031	GBDATA GBT_tree_infrontof(GBDATA gb_tree) {
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	}
1036	GBDATA GBT_tree_behind(GBDATA gb_tree) {
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
1042	GBDATA GBT_find_top_tree(GBDATA gb_main) {
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	}
1050	GBDATA GBT_find_bottom_tree(GBDATA gb_main) {
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
1063	GBDATA GBT_find_next_tree(GBDATA gb_tree) {
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
1103	const char GBT_name_of_largest_tree(GBDATA gb_main) {
1104	return GBT_get_tree_name(find_largest_tree(gb_main));
1105	}
1106
1107	const char GBT_name_of_bottom_tree(GBDATA gb_main) {
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 long nodes = GB_read_int(gb_nnodes)+1;
1130	const char *sizeInfo = GBS_global_string("(%li:%i)", nodes, GB_read_security_write(gb_tree));
1131	GBDATA *gb_rem = GB_entry(gb_tree, "remark");
1132	int len;
1133
1134	if (maxTreeNameLen == -1) {
1135	result = GBS_global_string("%s %11s", tree_name, sizeInfo);
1136	len = strlen(tree_name);
1137	}
1138	else {
1139	result = GBS_global_string("%-*s %11s", maxTreeNameLen, tree_name, sizeInfo);
1140	len = maxTreeNameLen;
1141	}
1142	if (gb_rem) {
1143	const char *remark = GB_read_char_pntr(gb_rem);
1144	const int remarkLen = 800;
1145	char *res2 = GB_give_other_buffer(remark, len+1+11+2+remarkLen+1);
1146
1147	strcpy(res2, result);
1148	strcat(res2, " ");
1149	strncat(res2, remark, remarkLen);
1150
1151	result = res2;
1152	}
1153
1154	if (nodes<2) {
1155	GB_warningf("Warning: tree '%s' has less than 2 nodes (is invalid + can be deleted).", tree_name);
1156	}
1157	}
1158	}
1159	return result;
1160	}
1161
1162	long GBT_size_of_tree(GBDATA gb_main, const char tree_name) {
1163	// return the number of inner nodes in binary tree (or -1 if unknown)
1164	// Note:
1165	// leafs = size + 1
1166	// inner nodes in unrooted tree = size - 1
1167
1168	long nnodes = -1;
1169	GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
1170	if (gb_tree) {
1171	GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
1172	if (gb_nnodes) {
1173	nnodes = GB_read_int(gb_nnodes);
1174	}
1175	}
1176	return nnodes;
1177	}
1178
1179
1180	struct indexed_name {
1181	int idx;
1182	const char *name;
1183
1184	bool operator<(const indexed_name& other) const { return idx < other.idx; }
1185	};
1186
1187	void GBT_get_tree_names(ConstStrArray& names, GBDATA *gb_main, bool sorted) {
1188	// stores tree names in 'names'
1189
1190	GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
1191	ensure_trees_have_order(gb_treedata);
1192
1193	long tree_count = GB_number_of_subentries(gb_treedata);
1194
1195	names.reserve(tree_count);
1196	typedef std::set<indexed_name> ordered_trees;
1197	ordered_trees trees;
1198
1199	{
1200	int t = 0;
1201	int count = 0;
1202	for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree), ++t) {
1203	indexed_name iname;
1204	iname.name = GB_read_key_pntr(gb_tree);
1205	iname.idx = sorted ? get_tree_idx(gb_tree) : ++count;
1206
1207	trees.insert(iname);
1208	}
1209	}
1210
1211	if (tree_count != (long)trees.size()) { // there are duplicated "order" entries
1212	gb_assert(sorted); // should not happen in unsorted mode
1213
1214	typedef std::set<int> ints;
1215
1216	ints used_indices;
1217	GBDATA *gb_first_tree = GB_child(gb_treedata);
1218	GBDATA *gb_tree = gb_first_tree;
1219
1220	while (gb_tree) {
1221	int idx = get_tree_idx(gb_tree);
1222	if (used_indices.find(idx) != used_indices.end()) { // duplicate order
1223	GB_ERROR error = reserve_tree_idx(gb_treedata, idx+1);
1224	if (!error) error = set_tree_idx(gb_tree, idx+1);
1225	if (error) GBK_terminatef("failed to fix tree-order (Reason: %s)", error);
1226
1227	// now restart
1228	used_indices.clear();
1229	gb_tree = gb_first_tree;
1230	}
1231	else {
1232	used_indices.insert(idx);
1233	gb_tree = GB_nextChild(gb_tree);
1234	}
1235	}
1236	GBT_get_tree_names(names, gb_main, sorted);
1237	return;
1238	}
1239
1240	for (ordered_trees::const_iterator t = trees.begin(); t != trees.end(); ++t) {
1241	names.put(t->name);
1242	}
1243	}
1244
1245	NOT4PERL GB_ERROR GBT_move_tree(GBDATA gb_moved_tree, GBT_ORDER_MODE mode, GBDATA gb_target_tree) {
1246	// moves 'gb_moved_tree' next to 'gb_target_tree' (only changes tree-order)
1247	gb_assert(gb_moved_tree && gb_target_tree);
1248
1249	GBDATA *gb_treedata = GB_get_father(gb_moved_tree);
1250	ensure_trees_have_order(gb_treedata);
1251
1252	int target_idx = get_tree_idx(gb_target_tree);
1253	gb_assert(target_idx);
1254
1255	if (mode == GBT_BEHIND) target_idx++;
1256
1257	GB_ERROR error = reserve_tree_idx(gb_treedata, target_idx);
1258	if (!error) error = set_tree_idx(gb_moved_tree, target_idx);
1259
1260	return error;
1261	}
1262
1263	static GBDATA get_source_and_check_target_tree(GBDATA gb_main, const char source_tree, const char dest_tree, GB_ERROR& error) {
1264	GBDATA *gb_source_tree = NULp;
1265
1266	error = GBT_check_tree_name(source_tree);
1267	if (!error) error = GBT_check_tree_name(dest_tree);
1268
1269	if (error && strcmp(source_tree, NO_TREE_SELECTED) == 0) {
1270	error = "No tree selected";
1271	}
1272
1273	if (!error && strcmp(source_tree, dest_tree) == 0) error = "source- and dest-tree are the same";
1274
1275	if (!error) {
1276	gb_source_tree = GBT_find_tree(gb_main, source_tree);
1277	if (!gb_source_tree) error = GBS_global_string("tree '%s' not found", source_tree);
1278	else {
1279	GBDATA *gb_dest_tree = GBT_find_tree(gb_main, dest_tree);
1280	if (gb_dest_tree) {
1281	error = GBS_global_string("tree '%s' already exists", dest_tree);
1282	gb_source_tree = NULp;
1283	}
1284	}
1285	}
1286
1287	gb_assert(contradicted(error, gb_source_tree));
1288	return gb_source_tree;
1289	}
1290
1291	static GBDATA copy_tree_container(GBDATA gb_source_tree, const char *newName, GB_ERROR& error) {
1292	GBDATA *gb_treedata = GB_get_father(gb_source_tree);
1293	GBDATA *gb_dest_tree = GB_create_container(gb_treedata, newName);
1294
1295	if (!gb_dest_tree) error = GB_await_error();
1296	else error = GB_copy_dropProtectMarksAndTempstate(gb_dest_tree, gb_source_tree);
1297
1298	gb_assert(contradicted(error, gb_dest_tree));
1299	return gb_dest_tree;
1300	}
1301
1302	GB_ERROR GBT_copy_tree(GBDATA gb_main, const char source_name, const char *dest_name) {
1303	GB_ERROR error;
1304	GBDATA *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error);
1305
1306	if (gb_source_tree) {
1307	GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error);
1308	if (gb_dest_tree) {
1309	int source_idx = get_tree_idx(gb_source_tree);
1310	int dest_idx = source_idx+1;
1311
1312	error = reserve_tree_idx(GB_get_father(gb_dest_tree), dest_idx);
1313	if (!error) error = set_tree_idx(gb_dest_tree, dest_idx);
1314	}
1315	}
1316
1317	return error;
1318	}
1319
1320	GB_ERROR GBT_rename_tree(GBDATA gb_main, const char source_name, const char *dest_name) {
1321	GB_ERROR error;
1322	GBDATA *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error);
1323
1324	if (gb_source_tree) {
1325	error = GB_test_delete_possible(gb_source_tree);
1326	if (!error) {
1327	GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error);
1328	if (gb_dest_tree) error = GB_delete(gb_source_tree);
1329	}
1330	}
1331
1332	if (error) {
1333	error = GBS_global_string("While renaming tree '%s' to '%s':\n%s",
1334	source_name, dest_name, error);
1335	}
1336
1337	return error;
1338	}
1339
1340	static GB_CSTR fill_species_name_array(GB_CSTR current, const TreeNode *tree) {
1341	if (tree->is_leaf()) {
1342	current[0] = tree->name;
1343	return current+1;
1344	}
1345	current = fill_species_name_array(current, tree->get_leftson());
1346	current = fill_species_name_array(current, tree->get_rightson());
1347	return current;
1348	}
1349
1350	GB_CSTR GBT_get_names_of_species_in_tree(const TreeNode tree, size_t *count) {
1351	/* creates an array of all species names in a tree,
1352	* The names are not allocated (so they may change as side effect of renaming species) */
1353
1354	size_t size = GBT_count_leafs(tree);
1355	GB_CSTR *result = ARB_calloc<GB_CSTR>(size + 1);
1356
1357	IF_ASSERTION_USED(GB_CSTR *check =) fill_species_name_array(result, tree);
1358	gb_assert(check - size == result);
1359
1360	if (count) *count = size;
1361
1362	return result;
1363	}
1364
1365	static void tree2newick(const TreeNode *tree, GBS_strstruct& out, NewickFormat format, int indent) {
1366	gb_assert(tree);
1367	if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); }
1368	if (tree->is_leaf()) {
1369	out.cat(tree->name);
1370	}
1371	else {
1372	out.put('(');
1373	tree2newick(tree->get_leftson(), out, format, indent+1);
1374	out.put(',');
1375	tree2newick(tree->get_rightson(), out, format, indent+1);
1376	if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); }
1377	out.put(')');
1378
1379	if (format & (nGROUP\|nREMARK)) {
1380	const char *remark = format&nREMARK ? tree->get_remark() : NULp;
1381	const char *group = NULp;
1382	const char *kgroup = NULp;
1383
1384	if (format&nGROUP) {
1385	if (tree->is_normal_group()) group = tree->name;
1386	if (tree->is_keeled_group()) kgroup = tree->get_father()->name;
1387	}
1388
1389	if (remark \|\| group \|\| kgroup) {
1390	out.put('\'');
1391	if (remark) {
1392	out.cat(remark);
1393	if (group) out.put(':');
1394	}
1395	if (group) out.cat(group);
1396	if (kgroup) {
1397	if (group) out.cat(" = ");
1398	out.put(KEELED_INDICATOR);
1399	out.cat(kgroup);
1400	}
1401	out.put('\'');
1402	}
1403	}
1404	}
1405
1406	if (format&nLENGTH && !tree->is_root_node()) {
1407	out.put(':');
1408	out.nprintf(10, "%5.3f", tree->get_branchlength());
1409	}
1410	}
1411
1412	char GBT_tree_2_newick(const TreeNode tree, NewickFormat format, bool compact) {
1413	// testcode-only newick exporter
1414	// see also ../SL/TREE_WRITE/TreeWrite.cxx@NEWICK_EXPORTER
1415	gb_assert(RUNNING_TEST());
1416
1417	GBS_strstruct out(1000);
1418	if (tree) tree2newick(tree, out, format, 0);
1419	out.put(';');
1420
1421	char *result = out.release();
1422	if (compact && (format&nWRAP)) {
1423	GB_ERROR error = NULp;
1424
1425	char compact1 = GBS_regreplace(result, "/[\n ][)]/)/", &error);
1426	if (compact1) {
1427	char compact2 = GBS_regreplace(compact1, "/[(][\n ]/(/", &error);
1428	if (compact2) freeset(result, compact2);
1429	free(compact1);
1430	}
1431	if (error) {
1432	fprintf(stderr, "Error in GBT_tree_2_newick: %s\n", error);
1433	gb_assert(!error); // should be impossible; falls back to 'result' if happens
1434	}
1435	}
1436	return result;
1437	}
1438
1439
1440	// --------------------------------------------------------------------------------
1441
1442	#ifdef UNIT_TESTS
1443	#include <test_unit.h>
1444
1445	static const char getTreeOrder(GBDATA gb_main) {
1446	ConstStrArray names;
1447	GBT_get_tree_names(names, gb_main, true);
1448
1449	char *joined = GBT_join_strings(names, '\|');
1450	char *size_and_names = GBS_global_string_copy("%zu:%s", names.size(), joined);
1451	free(joined);
1452
1453	RETURN_LOCAL_ALLOC(size_and_names);
1454	}
1455
1456	void TEST_tree_names() {
1457	TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name(""), "not a valid treename");
1458	TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("not_a_treename"), "not a valid treename");
1459	TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("tree_bad.dot"), "not a valid treename");
1460
1461	TEST_EXPECT_NO_ERROR(GBT_check_tree_name("tree_")); // ugly but ok
1462	TEST_EXPECT_NO_ERROR(GBT_check_tree_name("tree_ok"));
1463	}
1464
1465	void TEST_tree_contraints() {
1466	// test minima
1467	const int MIN_LEAFS = 2;
1468
1469	TEST_EXPECT_EQUAL(leafs_2_nodes (MIN_LEAFS, ROOTED), 3);
1470	TEST_EXPECT_EQUAL(leafs_2_nodes (MIN_LEAFS, UNROOTED), 2);
1471	TEST_EXPECT_EQUAL(leafs_2_edges (MIN_LEAFS, ROOTED), 2);
1472	TEST_EXPECT_EQUAL(leafs_2_edges (MIN_LEAFS, UNROOTED), 1);
1473	TEST_EXPECT_EQUAL(leafs_2_innerNodes(MIN_LEAFS, ROOTED), 1);
1474	TEST_EXPECT_EQUAL(leafs_2_innerNodes(MIN_LEAFS, UNROOTED), 0);
1475
1476	TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(3, ROOTED)); // test minimum (3 nodes rooted)
1477	TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(2, UNROOTED)); // test minimum (2 nodes unrooted)
1478
1479	TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(2, ROOTED)); // test minimum (2 edges rooted)
1480	TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(1, UNROOTED)); // test minimum (1 edge unrooted)
1481
1482	// test inverse functions:
1483	for (int i = 3; i<=7; ++i) {
1484	// test "leaf->XXX" and back conversions (any number of leafs is possible)
1485	TEST_EXPECT_EQUAL(i, nodes_2_leafs(leafs_2_nodes(i, ROOTED), ROOTED));
1486	TEST_EXPECT_EQUAL(i, nodes_2_leafs(leafs_2_nodes(i, UNROOTED), UNROOTED));
1487
1488	TEST_EXPECT_EQUAL(i, edges_2_leafs(leafs_2_edges(i, ROOTED), ROOTED));
1489	TEST_EXPECT_EQUAL(i, edges_2_leafs(leafs_2_edges(i, UNROOTED), UNROOTED));
1490
1491	bool odd = i%2;
1492	if (odd) {
1493	TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, ROOTED), ROOTED)); // rooted trees only contain odd numbers of nodes
1494	TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain odd numbers of edges
1495	}
1496	else { // even
1497	TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain even numbers of nodes
1498	TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, ROOTED), ROOTED)); // rooted trees only contain even numbers of edges
1499	}
1500
1501	TEST_EXPECT_EQUAL(i + leafs_2_innerNodes(i, ROOTED), leafs_2_nodes(i, ROOTED));
1502	TEST_EXPECT_EQUAL(i + leafs_2_innerNodes(i, UNROOTED), leafs_2_nodes(i, UNROOTED));
1503
1504	TEST_EXPECT_EQUAL(i + nodes_2_innerNodes(leafs_2_nodes(i, ROOTED), ROOTED), leafs_2_nodes(i, ROOTED));
1505	TEST_EXPECT_EQUAL(i + nodes_2_innerNodes(leafs_2_nodes(i, UNROOTED), UNROOTED), leafs_2_nodes(i, UNROOTED));
1506
1507	// test adding a leaf adds two nodes:
1508	int added = i+1;
1509	TEST_EXPECT_EQUAL(leafs_2_nodes(added, ROOTED)-leafs_2_nodes(i, ROOTED), 2);
1510	TEST_EXPECT_EQUAL(leafs_2_nodes(added, UNROOTED)-leafs_2_nodes(i, UNROOTED), 2);
1511	}
1512	}
1513
1514	void TEST_copy_rename_delete_tree_order() {
1515	GB_shell shell;
1516	GBDATA *gb_main = GB_open("TEST_trees.arb", "r");
1517
1518	{
1519	GB_transaction ta(gb_main);
1520
1521	{
1522	TEST_EXPECT_NULL(GBT_get_tree_name(NULp));
1523
1524	TEST_EXPECT_EQUAL(GBT_name_of_largest_tree(gb_main), "tree_removal");
1525
1526	TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_test");
1527	TEST_EXPECT_EQUAL(GBT_name_of_bottom_tree(gb_main), "tree_removal");
1528
1529	long inner_nodes = GBT_size_of_tree(gb_main, "tree_nj_bs");
1530	TEST_EXPECT_EQUAL(inner_nodes, 5);
1531	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");
1532	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");
1533
1534	{
1535	TreeNode *tree = GBT_read_tree(gb_main, "tree_nj_bs", new SimpleRoot);
1536
1537	TEST_REJECT_NULL(tree);
1538
1539	size_t leaf_count = GBT_count_leafs(tree);
1540
1541	size_t species_count;
1542	GB_CSTR *species = GBT_get_names_of_species_in_tree(tree, &species_count);
1543
1544	StrArray species2;
1545	for (int i = 0; species[i]; ++i) species2.put(ARB_strdup(species[i]));
1546
1547	TEST_EXPECT_EQUAL(species_count, leaf_count);
1548	TEST_EXPECT_EQUAL(long(species_count), inner_nodes+1);
1549	TEST_EXPECT_STRARRAY_CONTAINS(species2, '', "CloButyrCloButy2CorGlutaCorAquatCurCitreCytAquat");
1550
1551	free(species);
1552
1553	TEST_EXPECT_NEWICK(nSIMPLE, tree, "(CloButyr,(CloButy2,((CorGluta,(CorAquat,CurCitre)),CytAquat)));");
1554	TEST_EXPECT_NEWICK(nSIMPLE, NULp, ";");
1555
1556	destroy(tree);
1557	}
1558
1559	TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nj_bs"), "tree_nj_bs");
1560	TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nosuch"), "tree_test");
1561	}
1562
1563	// changing tree order
1564	{
1565	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");
1566
1567	GBDATA *gb_test = GBT_find_tree(gb_main, "tree_test");
1568	GBDATA *gb_tree2 = GBT_find_tree(gb_main, "tree_tree2");
1569	GBDATA *gb_groups = GBT_find_tree(gb_main, "tree_groups");
1570	GBDATA *gb_keeled = GBT_find_tree(gb_main, "tree_keeled");
1571	GBDATA *gb_keeled2 = GBT_find_tree(gb_main, "tree_keeled_2");
1572	GBDATA *gb_nj = GBT_find_tree(gb_main, "tree_nj");
1573	GBDATA *gb_nj_bs = GBT_find_tree(gb_main, "tree_nj_bs");
1574	GBDATA *gb_removal = GBT_find_tree(gb_main, "tree_removal");
1575
1576	TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_removal)); // move to bottom
1577	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");
1578
1579	TEST_EXPECT_EQUAL(GBT_tree_behind(gb_tree2), gb_groups);
1580	TEST_EXPECT_EQUAL(GBT_tree_behind(gb_keeled), gb_keeled2);
1581	TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj), gb_nj_bs);
1582	TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj_bs), gb_removal);
1583	TEST_EXPECT_EQUAL(GBT_tree_behind(gb_removal), gb_test);
1584	TEST_EXPECT_NULL(GBT_tree_behind(gb_test));
1585
1586	TEST_EXPECT_NULL(GBT_tree_infrontof(gb_tree2));
1587	TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_groups), gb_tree2);
1588	TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj), gb_keeled2);
1589	TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_nj);
1590	TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_removal), gb_nj_bs);
1591	TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_test), gb_removal);
1592
1593	TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_tree2)); // move back to top
1594	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");
1595
1596	TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_tree2)); // move from top
1597	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");
1598
1599	TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_removal, GBT_INFRONTOF, gb_nj)); // move from end
1600	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");
1601
1602	TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_nj_bs, GBT_INFRONTOF, gb_nj_bs)); // noop
1603	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");
1604
1605	TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_tree2");
1606
1607	TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_removal)), "tree_nj");
1608	TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_nj_bs)), "tree_tree2"); // last -> first
1609	}
1610
1611	// check tree order is maintained by copy, rename and delete
1612
1613	{
1614	// copy
1615	TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_nosuch", "tree_whatever"), "tree 'tree_nosuch' not found");
1616	TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_test", "tree_test"), "source- and dest-tree are the same");
1617	TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_tree2", "tree_test"), "tree 'tree_test' already exists");
1618
1619	TEST_EXPECT_NO_ERROR(GBT_copy_tree(gb_main, "tree_test", "tree_test_copy"));
1620	TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_test_copy"));
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_nj\|tree_nj_bs");
1622
1623	// rename
1624	TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_nj", "tree_renamed_nj"));
1625	TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_renamed_nj"));
1626	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");
1627
1628	TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_tree2", "tree_renamed_tree2"));
1629	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");
1630
1631	TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_test_copy", "tree_renamed_test_copy"));
1632	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");
1633
1634	// delete
1635
1636	GBDATA *gb_nj_bs = GBT_find_tree(gb_main, "tree_nj_bs");
1637	GBDATA *gb_renamed_nj = GBT_find_tree(gb_main, "tree_renamed_nj");
1638	GBDATA *gb_renamed_test_copy = GBT_find_tree(gb_main, "tree_renamed_test_copy");
1639	GBDATA *gb_renamed_tree2 = GBT_find_tree(gb_main, "tree_renamed_tree2");
1640	GBDATA *gb_test = GBT_find_tree(gb_main, "tree_test");
1641	GBDATA *gb_removal = GBT_find_tree(gb_main, "tree_removal");
1642	GBDATA *gb_groups = GBT_find_tree(gb_main, "tree_groups");
1643	GBDATA *gb_keeled = GBT_find_tree(gb_main, "tree_keeled");
1644	GBDATA *gb_keeled2 = GBT_find_tree(gb_main, "tree_keeled_2");
1645
1646	TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_tree2));
1647	TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_test_copy));
1648	TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_nj));
1649	TEST_EXPECT_NO_ERROR(GB_delete(gb_removal));
1650	TEST_EXPECT_NO_ERROR(GB_delete(gb_groups));
1651	TEST_EXPECT_NO_ERROR(GB_delete(gb_keeled));
1652	TEST_EXPECT_NO_ERROR(GB_delete(gb_keeled2));
1653
1654	// .. two trees left
1655
1656	TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test\|tree_nj_bs");
1657
1658	TEST_EXPECT_EQUAL(find_largest_tree(gb_main), gb_test);
1659	TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test);
1660	TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_nj_bs);
1661
1662	TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs);
1663	TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs);
1664	TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_nj_bs), gb_test);
1665
1666	TEST_EXPECT_NULL (GBT_tree_infrontof(gb_test));
1667	TEST_EXPECT_EQUAL(GBT_tree_behind (gb_test), gb_nj_bs);
1668
1669	TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_test);
1670	TEST_EXPECT_NULL (GBT_tree_behind (gb_nj_bs));
1671
1672	TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_nj_bs)); // move to bottom
1673	TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_nj_bs\|tree_test");
1674	TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_nj_bs)); // move to top
1675	TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test\|tree_nj_bs");
1676
1677	TEST_EXPECT_NO_ERROR(GB_delete(gb_nj_bs));
1678
1679	// .. one tree left
1680
1681	TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "1:tree_test");
1682
1683	TEST_EXPECT_EQUAL(find_largest_tree(gb_main), gb_test);
1684	TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test);
1685	TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_test);
1686
1687	TEST_EXPECT_NULL(GBT_find_next_tree(gb_test)); // no other tree left
1688	TEST_EXPECT_NULL(GBT_tree_behind(gb_test));
1689	TEST_EXPECT_NULL(GBT_tree_infrontof(gb_test));
1690
1691	TEST_EXPECT_NO_ERROR(GB_delete(gb_test));
1692
1693	// .. no tree left
1694
1695	TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "0:");
1696
1697	TEST_EXPECT_NULL(GBT_find_tree(gb_main, "tree_test"));
1698	TEST_EXPECT_NULL(GBT_existing_tree(gb_main, "tree_whatever"));
1699	TEST_EXPECT_NULL(find_largest_tree(gb_main));
1700	}
1701	}
1702
1703	GB_close(gb_main);
1704	}
1705	TEST_PUBLISH(TEST_copy_rename_delete_tree_order);
1706
1707
1708	void TEST_group_keeling() {
1709	GB_shell shell;
1710	GBDATA *gb_main = GB_open("TEST_trees.arb", "r");
1711
1712	{
1713	GB_transaction ta(gb_main);
1714
1715	const char *topo_tree2 = "(((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc),(((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste)),((CloTyrob,CloTyro2),CloTyro4)'g2')'outer');";
1716	const char *topo_groups = "(((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc)'upper',(((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste))'low1',((CloTyrob,CloTyro2)'twoleafs',CloTyro4)'low2')'lower');";
1717	const char *topo_keeled = "(CloTyrob,(((((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste))'low1',((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc)'upper = !lower')'!low2',CloTyro4)'!twoleafs',CloTyro2));";
1718	// Note: shows fixed semantics (#735)
1719	// e.g.
1720	// - compare members of group 'twoleafs' in
1721	// * topo_groups (2 members) and
1722	// * topo_keeled (all but former 2 members in inverse group)
1723	// - compares locations of groups 'upper' and 'lower'
1724	// * topo_groups: located at sons of root
1725	// * topo_keeled: located at same node!
1726
1727	{
1728	TreeNode *tree = GBT_read_tree(gb_main, "tree_tree2", new SimpleRoot);
1729	TEST_EXPECT_NEWICK(nGROUP, tree, topo_tree2);
1730	destroy(tree);
1731	}
1732	{
1733	TreeNode *tree = GBT_read_tree(gb_main, "tree_groups", new SimpleRoot);
1734	TEST_EXPECT_NEWICK(nGROUP, tree, topo_groups);
1735
1736	TreeNode *CloTyrob = tree->findLeafNamed("CloTyrob");
1737	TEST_REJECT_NULL(CloTyrob);
1738	CloTyrob->set_root();
1739
1740	tree = tree->get_root_node();
1741	TEST_EXPECT(tree->is_root_node());
1742
1743	TEST_EXPECT_NEWICK(nGROUP, tree, topo_keeled);
1744
1745	destroy(tree);
1746	}
1747	{
1748	TreeNode *tree = GBT_read_tree(gb_main, "tree_keeled", new SimpleRoot);
1749	TEST_EXPECT_NEWICK(nGROUP, tree, topo_keeled);
1750	destroy(tree);
1751	}
1752	{
1753	// Note: there is a HIDDEN_KEELED_GROUP at CytAquat (not shown here in topo, but displayed in dendro-tree-display)!
1754	// Group is found by group-search; see ../SL/GROUP_SEARCH/group_search.cxx@HIDDEN_KEELED_GROUP
1755	const char *topo_keeled2 = "(CloTyro4,((((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste))'low1',((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc)'upper = !lower')'!low2',(CloTyrob,CloTyro2)'twoleafs'));";
1756	TreeNode *tree = GBT_read_tree(gb_main, "tree_keeled_2", new SimpleRoot);
1757	TEST_EXPECT_NEWICK(nGROUP, tree, topo_keeled2);
1758	destroy(tree);
1759	}
1760	}
1761
1762	GB_close(gb_main);
1763	}
1764
1765	void TEST_tree_remove_leafs() {
1766	GB_shell shell;
1767	GBDATA *gb_main = GB_open("TEST_trees.arb", "r");
1768
1769	{
1770	GBT_TreeRemoveType tested_modes[] = {
1771	GBT_REMOVE_MARKED,
1772	GBT_REMOVE_UNMARKED,
1773	GBT_REMOVE_ZOMBIES,
1774	GBT_KEEP_MARKED,
1775	};
1776
1777	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);";
1778	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);";
1779	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);";
1780	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);";
1781	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);";
1782
1783	const char *kept_zombies_topo = "(Zombie1:0.131,Zombie2:0.162);";
1784	const char *kept_zombies_broken_topo = "Zombie2;";
1785
1786	const char *empty_topo = ";";
1787
1788	GB_transaction ta(gb_main);
1789	for (unsigned mode = 0; mode<ARRAY_ELEMS(tested_modes); ++mode) {
1790	GBT_TreeRemoveType what = tested_modes[mode];
1791
1792	for (int linked = 0; linked<=1; ++linked) {
1793	TEST_ANNOTATE(GBS_global_string("mode=%u linked=%i", mode, linked));
1794
1795	TreeNode *tree = GBT_read_tree(gb_main, "tree_removal", new SimpleRoot);
1796	gb_assert(tree);
1797	bool once = mode == 0 && linked == 0;
1798
1799	if (linked) {
1800	int zombies = 0;
1801	int duplicates = 0;
1802
1803	TEST_EXPECT_NO_ERROR(GBT_link_tree(tree, gb_main, false, &zombies, &duplicates));
1804
1805	TEST_EXPECT_EQUAL(zombies, 2);
1806	TEST_EXPECT_EQUAL(duplicates, 0);
1807	}
1808
1809	if (once) TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo);
1810
1811	int removedCount = 0;
1812	int groupsRemovedCount = 0;
1813
1814	tree = GBT_remove_leafs(tree, what, NULp, &removedCount, &groupsRemovedCount);
1815
1816	if (linked) {
1817	GBT_TreeRemoveType what_next = what;
1818
1819	switch (what) {
1820	case GBT_REMOVE_MARKED:
1821	TEST_EXPECT_EQUAL(removedCount, 6);
1822	TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1823	TEST_EXPECT_NEWICK(nLENGTH, tree, rem_marked_topo);
1824	what_next = GBT_REMOVE_UNMARKED;
1825	break;
1826	case GBT_REMOVE_UNMARKED:
1827	TEST_EXPECT_EQUAL(removedCount, 9);
1828	TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1829	TEST_EXPECT_NEWICK(nLENGTH, tree, rem_unmarked_topo);
1830	what_next = GBT_REMOVE_MARKED;
1831	break;
1832	case GBT_REMOVE_ZOMBIES:
1833	TEST_EXPECT_EQUAL(removedCount, 2);
1834	TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1835	TEST_EXPECT_NEWICK(nLENGTH, tree, rem_zombies_topo);
1836	break;
1837	case GBT_KEEP_MARKED:
1838	TEST_EXPECT_EQUAL(removedCount, 11);
1839	TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1840	TEST_EXPECT_NEWICK(nLENGTH, tree, kept_marked_topo);
1841	{
1842	// just a test for nWRAP NewickFormat (may be removed later)
1843	const char *kept_marked_topo_wrapped =
1844	"(\n"
1845	" CurCitre:1.000,\n"
1846	" (\n"
1847	" (\n"
1848	" CloButy2:0.009,\n"
1849	" CloButyr:0.000\n"
1850	" ):0.131,\n"
1851	" (\n"
1852	" CytAquat:0.711,\n"
1853	" (\n"
1854	" CorGluta:0.522,\n"
1855	" CorAquat:0.103\n"
1856	" ):0.207\n"
1857	" ):0.162\n"
1858	" ):0.124);";
1859	TEST_EXPECT_NEWICK(NewickFormat(nLENGTH\|nWRAP), tree, kept_marked_topo_wrapped);
1860
1861	const char *expected_compacted =
1862	"(CurCitre:1.000,\n"
1863	" ((CloButy2:0.009,\n"
1864	" CloButyr:0.000):0.131,\n"
1865	" (CytAquat:0.711,\n"
1866	" (CorGluta:0.522,\n"
1867	" CorAquat:0.103):0.207):0.162):0.124);";
1868	char *compacted = GBT_tree_2_newick(tree, NewickFormat(nLENGTH\|nWRAP), true);
1869	TEST_EXPECT_EQUAL(compacted, expected_compacted);
1870	free(compacted);
1871	}
1872	what_next = GBT_REMOVE_MARKED;
1873	break;
1874	}
1875
1876	if (what_next != what) {
1877	gb_assert(tree);
1878	tree = GBT_remove_leafs(tree, what_next, NULp, &removedCount, &groupsRemovedCount);
1879
1880	switch (what) {
1881	case GBT_REMOVE_MARKED: // + GBT_REMOVE_UNMARKED
1882	TEST_EXPECT_EQUAL(removedCount, 16);
1883	TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1884	TEST_EXPECT_NEWICK__BROKEN(nLENGTH, tree, kept_zombies_topo);
1885	TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_broken_topo); // @@@ invalid topology (single leaf)
1886	break;
1887	case GBT_REMOVE_UNMARKED: // + GBT_REMOVE_MARKED
1888	TEST_EXPECT_EQUAL(removedCount, 15);
1889	TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1890	TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_topo);
1891	break;
1892	case GBT_KEEP_MARKED: // + GBT_REMOVE_MARKED
1893	TEST_EXPECT_EQUAL(removedCount, 17);
1894	TEST_EXPECT_EQUAL__BROKEN(groupsRemovedCount, 2, 1); // @@@ expect that all groups have been removed!
1895	TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1896	TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo);
1897	break;
1898	default:
1899	TEST_REJECT(true);
1900	break;
1901	}
1902	}
1903	}
1904	else {
1905	switch (what) {
1906	case GBT_REMOVE_MARKED:
1907	case GBT_REMOVE_UNMARKED:
1908	TEST_EXPECT_EQUAL(removedCount, 0);
1909	TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1910	TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo);
1911	break;
1912	case GBT_REMOVE_ZOMBIES:
1913	case GBT_KEEP_MARKED:
1914	TEST_EXPECT_EQUAL(removedCount, 17);
1915	TEST_EXPECT_EQUAL(groupsRemovedCount, 2);
1916	TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo);
1917	break;
1918	}
1919	}
1920
1921	if (tree) {
1922	gb_assert(tree->is_root_node());
1923	destroy(tree);
1924	}
1925	}
1926	}
1927	}
1928
1929	GB_close(gb_main);
1930	}
1931	TEST_PUBLISH(TEST_tree_remove_leafs);
1932
1933
1934	#endif // UNIT_TESTS

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: branches/help/ARBDB/adtree.cxx

Download in other formats: