1 /*
2 * treesort.c
3 *
4 *
5 * Part of TREE-PUZZLE 5.2 (July 2004)
6 *
7 * (c) 2003-2004 by Heiko A. Schmidt, Korbinian Strimmer, and Arndt von Haeseler
8 * (c) 1999-2003 by Heiko A. Schmidt, Korbinian Strimmer,
9 * M. Vingron, and Arndt von Haeseler
10 * (c) 1995-1999 by Korbinian Strimmer and Arndt von Haeseler
11 *
12 * All parts of the source except where indicated are distributed under
13 * the GNU public licence. See http://www.opensource.org for details.
14 *
15 * ($Id$)
16 *
17 */
18
19
20 #define EXTERN extern
21 #include "treesort.h"
22
23 int YYY=0;
24 /* fprintf(stderr, "YYY: %d (%s:%d)\n", YYY++, __FILE__, __LINE__); */
25
26
27 /*******************************************/
28 /* tree sorting */
29 /*******************************************/
30
31 /* compute address of the 4 int (sort key) in the 4 int node */
ct_sortkeyaddr(int addr)32 int ct_sortkeyaddr(int addr)
33 {
34 int a, res;
35 a = addr % 4;
36 res = addr - a + 3;
37 return res;
38 } /* ct_sortkeyaddr */
39
40
41 /**********/
42
43 /* compute address of the next edge pointer in a 4 int node (0->1->2->0) */
ct_nextedgeaddr(int addr)44 int ct_nextedgeaddr(int addr)
45 {
46 int a, res;
47 a = addr % 4;
48 if ( a == 2 ) { res = addr - 2; }
49 else { res = addr + 1; }
50 return res;
51 } /* ct_nextedgeaddr */
52
53
54 /**********/
55
56 /* compute address of 1st edge of a 4 int node from node number */
ct_1stedge(int node)57 int ct_1stedge(int node)
58 {
59 int res;
60 res = 4 * node;
61 return res;
62 } /* ct_1stedge */
63
64
65 /**********/
66
67 /* compute address of 2nd edge of a 4 int node from node number */
ct_2ndedge(int node)68 int ct_2ndedge(int node)
69 {
70 int res;
71 res = 4 * node +1;
72 return res;
73 } /* ct_2ndedge */
74
75
76 /**********/
77
78 /* compute address of 3rd edge of a 4 int node from node number */
ct_3rdedge(int node)79 int ct_3rdedge(int node)
80 {
81 int res;
82 res = 4 * node +2;
83 return res;
84 } /* ct_3rdedge */
85
86
87 /**********/
88
89 /* check whether node 'node' is a leaf (2nd/3rd edge pointer = -1) */
ct_isleaf(int node,int * ctree)90 int ct_isleaf(int node, int *ctree)
91 {
92 return (ctree[ct_3rdedge(node)] < 0);
93 } /* ct_isleaf */
94
95
96 /**********/
97
98 /* compute node number of 4 int node from an edge addr. */
ct_addr2node(int addr)99 int ct_addr2node(int addr)
100 {
101 int a, res;
102 a = addr % 4;
103 res = (int) ((addr - a) / 4);
104 return res;
105 } /* ct_addr2node */
106
107
108 /**********/
109
110 /* print graph pointers for checking */
printctree(int * ctree)111 void printctree(int *ctree)
112 {
113 int n;
114 for (n=0; n < 2*Maxspc; n++) {
115 printf("n[%3d] = (%3d.%2d, %3d.%2d, %3d.%2d | %3d)\n", n,
116 (int) ctree[ct_1stedge(n)]/4,
117 (int) ctree[ct_1stedge(n)]%4,
118 (int) ctree[ct_2ndedge(n)]/4,
119 (int) ctree[ct_2ndedge(n)]%4,
120 (int) ctree[ct_3rdedge(n)]/4,
121 (int) ctree[ct_3rdedge(n)]%4,
122 ctree[ct_3rdedge(n)+1]);
123 }
124 printf("\n");
125 } /* printctree */
126
127
128 /**********/
129
130 /* allocate memory for ctree 3 ints pointer plus 1 check byte */
initctree(void)131 int *initctree(void)
132 {
133 int *snodes;
134 int n;
135
136 snodes = (int *) calloc((size_t) (4 * 2 * Maxspc), sizeof(int));
137 if (snodes == NULL) maerror("snodes in copytree");
138
139 for (n=0; n<(4 * 2 * Maxspc); n++) {
140 snodes[n]=-1;
141 }
142 return snodes;
143 } /* initctree */
144
145
146 /**********/
147
148 /* free memory of a tree for sorting */
freectree(int ** snodes)149 void freectree(int **snodes)
150 {
151 free(*snodes);
152 *snodes = NULL;
153 } /* freectree */
154
155
156 #if 0
157 /**********/
158
159 /* trueID (HAS) */
160 /* copy subtree recursively */
161 void copyOTU_trueID(int *ctree, /* in/out: tree array struct */
162 int *ct_nextnode,/* in/out: next free node */
163 int ct_curredge,/* in: currend edge to add subtree */
164 int *ct_nextleaf,/* in/out: next free leaf (0-maxspc) */
165 int ed, /* in: current edge in puzzling tree */
166 ONEEDGE *edge, /* in: tree topology */
167 int *edgeofleaf, /* in: external edge list */
168 int numleaves, /* in: number of leaves */
169 int *trueID) /* in: permutation vector */
170 {
171 int i, nextcurredge;
172
173 /* test whether we are on a leaf */
174 if (edge[ed].downright == NULL && edge[ed].downleft == NULL) {
175 for (i = 1; i < numleaves; i++) {
176 if (edgeofleaf[i] == ed) { /* i is the leaf of ed */
177 nextcurredge = ct_1stedge(*ct_nextleaf);
178 ctree[ct_curredge] = nextcurredge;
179 ctree[nextcurredge] = ct_curredge;
180 /* trueID (HAS) */
181 ctree[ct_sortkeyaddr(nextcurredge)] = trueID[i];
182 (*ct_nextleaf)++;
183 return;
184 }
185 }
186 }
187
188 /* we are NOT on a leaf */
189 nextcurredge = ct_1stedge(*ct_nextnode);
190 ctree[ct_curredge] = nextcurredge;
191 ctree[nextcurredge] = ct_curredge;
192 (*ct_nextnode)++;
193 nextcurredge = ct_nextedgeaddr(nextcurredge);
194 copyOTU_trueID(ctree, ct_nextnode, nextcurredge,
195 ct_nextleaf, edge[ed].downleft->numedge,
196 edge, edgeofleaf, numleaves, trueID);
197
198 nextcurredge = ct_nextedgeaddr(nextcurredge);
199 copyOTU_trueID(ctree, ct_nextnode, nextcurredge,
200 ct_nextleaf, edge[ed].downright->numedge,
201 edge, edgeofleaf, numleaves, trueID);
202 } /* copyOTU_trueID */
203
204 /********/
205
206
207 /* trueID (HAS) */
208 /* copy treestructure to sorting structure */
209 void copytree_trueID(int *ctree, /* out: copy for effective sorting */
210 int *trueID, /* in: permutation vector */
211 ONEEDGE *edgeset, /* in: intermediate tree topology */
212 int *edgeofleaf, /* dito. */
213 int numleaves) /* in: number of leaves */
214 {
215 int ct_curredge;
216 int ct_nextleaf;
217 int ct_nextnode;
218
219 ct_nextnode = Maxspc;
220 ct_curredge = ct_1stedge(ct_nextnode);
221 ct_nextleaf = 1;
222
223 ctree[ct_1stedge(0)] = ct_curredge;
224 ctree[ct_curredge] = ct_1stedge(0);
225 /* trueID (HAS) */
226 ctree[ct_sortkeyaddr(0)] = trueID[0];
227
228 ct_nextnode++;
229
230 ct_curredge = ct_nextedgeaddr(ct_curredge);
231
232 copyOTU_trueID(ctree, &ct_nextnode, ct_curredge,
233 &ct_nextleaf, edgeset[edgeofleaf[0]].downleft->numedge,
234 edgeset, edgeofleaf, numleaves, trueID);
235
236 ct_curredge = ct_nextedgeaddr(ct_curredge);
237 copyOTU_trueID(ctree, &ct_nextnode, ct_curredge,
238 &ct_nextleaf, edgeset[edgeofleaf[0]].downright->numedge,
239 edgeset, edgeofleaf, numleaves, trueID);
240 } /* copytree_trueID */
241 #endif
242
243
244 /**********/
245
246 /* copy subtree recursively */
copyOTU(int * ctree,int * ct_nextnode,int ct_curredge,int * ct_nextleaf,int ed,ONEEDGE * edge,int * edgeofleaf,int numleaves)247 void copyOTU(int *ctree, /* in/out: tree array struct */
248 int *ct_nextnode,/* in/out: next free node */
249 int ct_curredge,/* in: currend edge to add subtree */
250 int *ct_nextleaf,/* in/out: next free leaf (0-maxspc) */
251 int ed, /* in: current edge in puzzling tree */
252 ONEEDGE *edge, /* in: tree topology */
253 int *edgeofleaf, /* in: external edge list */
254 int numleaves) /* in: number of leaves */
255 {
256 int nextcurredge;
257
258 /* test whether we are on a leaf */
259 if (edge[ed].downright == NULL && edge[ed].downleft == NULL) {
260 nextcurredge = ct_1stedge(*ct_nextleaf);
261 ctree[ct_curredge] = nextcurredge;
262 ctree[nextcurredge] = ct_curredge;
263 ctree[ct_sortkeyaddr(nextcurredge)] = edge[ed].taxon;
264 (*ct_nextleaf)++;
265 return;
266 }
267
268 /* we are NOT on a leaf */
269 nextcurredge = ct_1stedge(*ct_nextnode);
270 ctree[ct_curredge] = nextcurredge;
271 ctree[nextcurredge] = ct_curredge;
272 (*ct_nextnode)++;
273 nextcurredge = ct_nextedgeaddr(nextcurredge);
274 copyOTU(ctree, ct_nextnode, nextcurredge,
275 ct_nextleaf, edge[ed].downleft->numedge,
276 edge, edgeofleaf, numleaves);
277
278 nextcurredge = ct_nextedgeaddr(nextcurredge);
279 copyOTU(ctree, ct_nextnode, nextcurredge,
280 ct_nextleaf, edge[ed].downright->numedge,
281 edge, edgeofleaf, numleaves);
282 } /* copyOTU */
283
284
285 /**********/
286
287 /* copy treestructure to sorting structure */
copytree(int * ctree,ONEEDGE * edgeset,int * edgeofleaf,int rootleaf,int numleaves)288 void copytree(int *ctree, /* out: copy for effective sorting */
289 ONEEDGE *edgeset, /* in: intermediate tree topology */
290 int *edgeofleaf, /* dito. */
291 int rootleaf,
292 int numleaves) /* in: number of leaves */
293 {
294 int ct_curredge;
295 int ct_nextleaf;
296 int ct_nextnode;
297
298 ct_nextnode = Maxspc;
299 ct_curredge = ct_1stedge(ct_nextnode);
300 ct_nextleaf = 1;
301
302 ctree[ct_1stedge(0)] = ct_curredge;
303 ctree[ct_curredge] = ct_1stedge(0);
304 ctree[ct_sortkeyaddr(0)] = rootleaf;
305
306 ct_nextnode++;
307
308 ct_curredge = ct_nextedgeaddr(ct_curredge);
309
310 copyOTU(ctree, &ct_nextnode, ct_curredge,
311 &ct_nextleaf, edgeset[edgeofleaf[rootleaf]].downleft->numedge,
312 edgeset, edgeofleaf, numleaves);
313
314 ct_curredge = ct_nextedgeaddr(ct_curredge);
315 copyOTU(ctree, &ct_nextnode, ct_curredge,
316 &ct_nextleaf, edgeset[edgeofleaf[rootleaf]].downright->numedge,
317 edgeset, edgeofleaf, numleaves);
318 } /* copytree */
319
320
321 /**********/
322
323 /* sort subtree from edge recursively by indices */
sortOTU(int edge,int * ctree)324 int sortOTU(int edge, int *ctree)
325 {
326 int key1, key2;
327 int edge1, edge2;
328 int tempedge;
329
330 /* if leaf, return taxonID */
331 if (ctree[ct_2ndedge((int) (edge / 4))] < 0)
332 return ctree[ct_sortkeyaddr(edge)];
333
334 edge1 = ctree[ct_nextedgeaddr(edge)];
335 edge2 = ctree[ct_nextedgeaddr(ct_nextedgeaddr(edge))];
336
337 /* printf ("visiting [%5d] -> [%5d], [%5d]\n", edge, edge1, edge2); */
338 /* printf ("visiting [%2d.%2d] -> [%2d.%2d], [%2d.%2d]\n",
339 (int)(edge/4), edge%4, (int)(edge1/4), edge1%4,
340 (int)(edge2/4), edge2%4); */
341
342 key1 = sortOTU(edge1, ctree);
343 key2 = sortOTU(edge2, ctree);
344
345 if (key2 < key1) {
346 tempedge = ctree[ctree[edge1]];
347 ctree[ctree[edge1]] = ctree[ctree[edge2]];
348 ctree[ctree[edge2]] = tempedge;
349 tempedge = ctree[edge1];
350 ctree[edge1] = ctree[edge2];
351 ctree[edge2] = tempedge;
352 ctree[ct_sortkeyaddr(edge)] = key2;
353
354 } else {
355 ctree[ct_sortkeyaddr(edge)] = key1;
356 }
357 return ctree[ct_sortkeyaddr(edge)];
358 } /* sortOTU */
359
360
361 /**********/
362
363 /* sort ctree recursively by indices */
sortctree(int * ctree)364 int sortctree(int *ctree)
365 {
366 int n, startnode=-1;
367
368 /* find virtual root node (ID=0) */
369 for(n=0; n<Maxspc; n++) {
370 if (ctree[ct_sortkeyaddr(n*4)] == 0)
371 startnode = n;
372 }
373
374 /* sort it starting at virtual root node */
375 sortOTU(ctree[startnode * 4], ctree);
376 return startnode;
377 } /* sortctree */
378
379
380 /**********/
381
382 /* print recursively subtree of edge of sorted tree ctree */
fprintfsortOTU(FILE * ofp,int edge,int * ctree)383 void fprintfsortOTU(FILE *ofp, int edge, int *ctree)
384 {
385 int edge1, edge2;
386
387 if (ctree[ct_2ndedge((int) (edge / 4))] < 0) {
388 fprintf(ofp, "%d", ctree[ct_sortkeyaddr(edge)]);
389 return;
390 }
391
392 edge1 = ctree[ct_nextedgeaddr(edge)];
393 edge2 = ctree[ct_nextedgeaddr(ct_nextedgeaddr(edge))];
394
395 fprintf(ofp, "(");
396 fprintfsortOTU(ofp, edge1, ctree);
397 fprintf(ofp, ",");
398 fprintfsortOTU(ofp, edge2, ctree);
399 fprintf(ofp, ")");
400
401 } /* fprintfsortOTU */
402
403
404 /**********/
405
406 /* print recursively sorted tree ctree */
fprintfsortctree(FILE * ofp,int * ctree)407 int fprintfsortctree(FILE *ofp, int *ctree)
408 {
409 int n, startnode=-1;
410 for(n=0; n<Maxspc; n++) {
411 if (ctree[ct_sortkeyaddr(n*4)] == 0)
412 startnode = n;
413 }
414 fprintf (ofp, "(%d,", ctree[ct_sortkeyaddr(startnode*4)]);
415 fprintfsortOTU(ofp, ctree[startnode * 4], ctree);
416 fprintf (ofp, ");\n");
417 return startnode;
418 } /* fprintfsortctree */
419
420
421 /**********/
422
423 /* print recursively subtree of edge of sorted tree ctree to string */
sprintfOTU(char * str,int * len,int edge,int * ctree)424 void sprintfOTU(char *str, int *len, int edge, int *ctree)
425 {
426 int edge1, edge2;
427
428 if (ctree[ct_2ndedge((int) (edge / 4))] < 0) {
429 *len+=sprintf(&(str[*len]), "%d", ctree[ct_sortkeyaddr(edge)]);
430 return;
431 }
432
433 edge1 = ctree[ct_nextedgeaddr(edge)];
434 edge2 = ctree[ct_nextedgeaddr(ct_nextedgeaddr(edge))];
435
436 sprintf(&(str[*len]), "(");
437 (*len)++;
438 sprintfOTU(str, len, edge1, ctree);
439 sprintf(&(str[*len]), ",");
440 (*len)++;
441 sprintfOTU(str, len, edge2, ctree);
442 sprintf(&(str[*len]), ")");
443 (*len)++;
444 } /* sprintfOTU */
445
446 /**********/
447
448
449 /* print recursively sorted tree ctree to string */
sprintfctree(int * ctree,int strglen)450 char *sprintfctree(int *ctree, int strglen)
451 {
452 char *treestr,
453 *tmpptr;
454 int n,
455 len=0,
456 startnode=-1;
457 treestr = (char *) calloc((size_t) strglen, sizeof(char));
458 tmpptr = treestr;
459 for(n=0; n<Maxspc; n++) {
460 if (ctree[ct_sortkeyaddr(n*4)] == 0)
461 startnode = n;
462 }
463 len+=sprintf (&(tmpptr[len]), "(%d,", ctree[ct_sortkeyaddr(startnode*4)]);
464 sprintfOTU(tmpptr, &len, ctree[startnode * 4], ctree);
465 len+=sprintf (&(tmpptr[len]), ");");
466 return treestr;
467 } /* sprintfctree */
468
469
470 /**********/
471
472
473 /***********************************************/
474 /* establish and handle a list of sorted trees */
475 /***********************************************/
476
477 int itemcount;
478
479 /* initialize structure */
inittreelist(int * treenum)480 treelistitemtype *inittreelist(int *treenum)
481 {
482 *treenum = 0;
483 return NULL;
484 } /* itemcount */
485
486
487 /**********/
488
489 /* malloc new tree list item */
gettreelistitem()490 treelistitemtype *gettreelistitem()
491 {
492 treelistitemtype *tmpptr;
493 tmpptr = (treelistitemtype *)calloc((size_t) 1, sizeof(treelistitemtype));
494 if (tmpptr == NULL) maerror("item of intermediate tree stuctures");
495 (*tmpptr).pred = NULL;
496 (*tmpptr).succ = NULL;
497 (*tmpptr).tree = NULL;
498 (*tmpptr).count = 0;
499 (*tmpptr).idx = itemcount++;
500 return tmpptr;
501 } /* gettreelistitem */
502
503 /**********/
504
505 /* free whole tree list */
freetreelist(treelistitemtype ** list,int * numitems,int * numsum)506 void freetreelist(treelistitemtype **list,
507 int *numitems,
508 int *numsum)
509 {
510 treelistitemtype *current;
511 treelistitemtype *next;
512 current = *list;
513 while (current != NULL) {
514 next = (*current).succ;
515 if ((*current).tree != NULL) {
516 free ((*current).tree);
517 (*current).tree = NULL;
518 }
519 free(current);
520 current = next;
521 }
522 *list = NULL;
523 *numitems = 0;
524 *numsum = 0;
525 } /* freetreelist */
526
527
528 /**********/
529
530 /* add tree to the tree list */
addtree2list(char ** tree,int numtrees,treelistitemtype ** list,int * numitems,int * numsum)531 treelistitemtype *addtree2list(char **tree, /* sorted tree string */
532 int numtrees, /* how many occurred, e.g. in parallel */
533 treelistitemtype **list, /* addr. of tree list */
534 int *numitems,
535 int *numsum)
536 {
537 treelistitemtype *tmpptr = NULL;
538 treelistitemtype *newptr = NULL;
539 int result;
540 int done = 0;
541
542 if ((*list == NULL) || (numitems == 0)) {
543 newptr = gettreelistitem();
544 (*newptr).tree = *tree;
545 *tree = NULL;
546 (*newptr).id = *numitems;
547 (*newptr).count = numtrees;
548 *numitems = 1;
549 *numsum = numtrees;
550 *list = newptr;
551 } else {
552 tmpptr = *list;
553 while(done == 0) {
554 result = strcmp( (*tmpptr).tree, *tree);
555 if (result==0) {
556 free(*tree); *tree = NULL;
557 (*tmpptr).count += numtrees;
558 *numsum += numtrees;
559 done = 1;
560 newptr = tmpptr;
561 } else { if (result < 0) {
562 if ((*tmpptr).succ != NULL)
563 tmpptr = (*tmpptr).succ;
564 else {
565 newptr = gettreelistitem();
566 (*newptr).tree = *tree;
567 *tree = NULL;
568 (*newptr).id = *numitems;
569 (*newptr).count = numtrees;
570 (*newptr).pred = tmpptr;
571 (*tmpptr).succ = newptr;
572 (*numitems)++;
573 *numsum += numtrees;
574 done = 1;
575 }
576 } else { /* result < 0 */
577 newptr = gettreelistitem();
578 (*newptr).tree = *tree;
579 *tree = NULL;
580 (*newptr).id = *numitems;
581 (*newptr).count = numtrees;
582 (*newptr).succ = tmpptr;
583 (*newptr).pred = (*tmpptr).pred;
584 (*tmpptr).pred = newptr;
585 *numsum += numtrees;
586
587 if ((*newptr).pred != NULL) {
588 (*(*newptr).pred).succ = newptr;
589 } else {
590 *list = newptr;
591 }
592 (*numitems)++;
593 done = 1;
594 } /* end if result < 0 */
595 } /* end if result != 0 */
596 } /* while searching in list */
597 } /* if list empty, else */
598 return (newptr);
599 } /* addtree2list */
600
601
602 /**********/
603
604 /* resort list of trees by number of occurences for output */
sortbynum(treelistitemtype * list,treelistitemtype ** sortlist)605 void sortbynum(treelistitemtype *list, treelistitemtype **sortlist)
606 {
607 treelistitemtype *tmpptr = NULL;
608 treelistitemtype *curr = NULL;
609 treelistitemtype *next = NULL;
610 int xchange = 1;
611
612 if (list == NULL) fprintf(stderr, "Grrrrrrrrr>>>>\n");
613 tmpptr = list;
614 *sortlist = list;
615 while (tmpptr != NULL) {
616 (*tmpptr).sortnext = (*tmpptr).succ;
617 (*tmpptr).sortlast = (*tmpptr).pred;
618 tmpptr = (*tmpptr).succ;
619 }
620
621 while (xchange > 0) {
622 curr = *sortlist;
623 xchange = 0;
624 if (curr == NULL) fprintf(stderr, "Grrrrrrrrr>>>>\n");
625 while((*curr).sortnext != NULL) {
626 next = (*curr).sortnext;
627 if ((*curr).count >= (*next).count)
628 curr = (*curr).sortnext;
629 else {
630 if ((*curr).sortlast != NULL)
631 (*((*curr).sortlast)).sortnext = next;
632 if (*sortlist == curr)
633 *sortlist = next;
634 (*next).sortlast = (*curr).sortlast;
635
636 if ((*next).sortnext != NULL)
637 (*((*next).sortnext)).sortlast = curr;
638 (*curr).sortnext = (*next).sortnext;
639
640 (*curr).sortlast = next;
641 (*next).sortnext = curr;
642
643 xchange++;
644 }
645 }
646 }
647 } /* sortbynum */
648
649
650 /**********/
651
652 /* print puzzling step tree stuctures for checking */
printfpstrees(treelistitemtype * list)653 void printfpstrees(treelistitemtype *list)
654 {
655 char ch;
656 treelistitemtype *tmpptr = NULL;
657 tmpptr = list;
658 ch = '-';
659 while (tmpptr != NULL) {
660 printf ("%c[%2d] %5d %s\n", ch, (*tmpptr).idx, (*tmpptr).count, (*tmpptr).tree);
661 tmpptr = (*tmpptr).succ;
662 ch = ' ';
663 }
664 } /* printfpstrees */
665
666 /**********/
667
668 /* print sorted puzzling step tree stucture with names */
fprintffullpstree(FILE * outf,char * treestr)669 void fprintffullpstree(FILE *outf, char *treestr)
670 {
671 int count = 0;
672 int idnum = 0;
673 int n;
674 for(n=0; treestr[n] != '\0'; n++){
675 while(isdigit((int)treestr[n])){
676 idnum = (10 * idnum) + ((int)treestr[n]-48);
677 n++;
678 count++;
679 }
680 if (count > 0){
681 # ifdef USEQUOTES
682 fprintf(outf, "'");
683 # endif
684 (void)fputid(outf, idnum);
685 # ifdef USEQUOTES
686 fprintf(outf, "'");
687 # endif
688 count = 0;
689 idnum = 0;
690 }
691 fprintf(outf, "%c", treestr[n]);
692 }
693 } /* fprintffullpstree */
694
695
696 /**********/
697
698 /* print sorted puzzling step tree stuctures with names */
fprintfsortedpstrees(FILE * output,treelistitemtype * list,int itemnum,int itemsum,int comment,float cutoff)699 void fprintfsortedpstrees(FILE *output,
700 treelistitemtype *list, /* tree list */
701 int itemnum, /* order number */
702 int itemsum, /* number of trees */
703 int comment, /* with statistics, or puzzle report ? */
704 float cutoff) /* cutoff percentage */
705 {
706 treelistitemtype *tmpptr = NULL;
707 treelistitemtype *slist = NULL;
708 int num = 1;
709 float percent;
710
711 if (list == NULL) fprintf(stderr, "Grrrrrrrrr>>>>\n");
712 sortbynum(list, &slist);
713
714 tmpptr = slist;
715 while (tmpptr != NULL) {
716 percent = (float)(100.0 * (*tmpptr).count / itemsum);
717 if ((cutoff == 0.0) || (cutoff <= percent)) {
718 if (comment)
719 fprintf (output, "[ %d. %d %.2f %d %d %d ]", num++, (*tmpptr).count, percent, (*tmpptr).id, itemnum, itemsum);
720 else {
721 if (num == 1){
722 fprintf (output, "\n");
723 fprintf (output, "The following tree(s) occured in more than %.2f%% of the %d puzzling steps.\n", cutoff, itemsum);
724 fprintf (output, "The trees are orderd descending by the number of occurences.\n");
725 fprintf (output, "\n");
726 fprintf (output, "\n occurences ID Phylip tree\n");
727 }
728 fprintf (output, "%2d. %5d %6.2f%% %5d ", num++, (*tmpptr).count, percent, (*tmpptr).id);
729 }
730 fprintffullpstree(output, (*tmpptr).tree);
731 fprintf (output, "\n");
732 }
733 tmpptr = (*tmpptr).sortnext;
734 }
735
736 if (!comment) {
737 fprintf (output, "\n");
738 switch(num) {
739 case 1: fprintf (output, "There were no tree topologies (out of %d) occuring with a percentage \n>= %.2f%% of the %d puzzling steps.\n", itemnum, cutoff, itemsum); break;
740 case 2: fprintf (output, "There was one tree topology (out of %d) occuring with a percentage \n>= %.2f%%.\n", itemnum, cutoff); break;
741 default: fprintf (output, "There were %d tree topologies (out of %d) occuring with a percentage \n>= %.2f%%.\n", num-1, itemnum, cutoff); break;
742 }
743 fprintf (output, "\n");
744 fprintf (output, "\n");
745 }
746
747 } /* fprintfsortedpstrees */
748
749 /**********/
750
751
752 /* print sorted tree topologies for checking */
printfsortedpstrees(treelistitemtype * list)753 void printfsortedpstrees(treelistitemtype *list)
754 {
755 treelistitemtype *tmpptr = NULL;
756 treelistitemtype *slist = NULL;
757
758 sortbynum(list, &slist);
759
760 tmpptr = slist;
761 while (tmpptr != NULL) {
762 printf ("[%2d] %5d %s\n", (*tmpptr).idx, (*tmpptr).count, (*tmpptr).tree);
763 tmpptr = (*tmpptr).sortnext;
764 }
765 } /* printfsortedpstrees */
766
767
768 /*******************************************/
769 /* end of tree sorting */
770 /*******************************************/
771
772
773
774