Context Navigation

source: tags/ms_ra2q1/ARBDB/adtree.cxx

Visit:

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

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

Download in other formats: