1 static char const rcsid[] = "$Id: urktree.c,v 6.6 2003/05/30 17:25:38 coulouri Exp $";
2
3 /*
4 * ===========================================================================
5 *
6 * PUBLIC DOMAIN NOTICE
7 * National Center for Biotechnology Information
8 *
9 * This software/database is a "United States Government Work" under the
10 * terms of the United States Copyright Act. It was written as part of
11 * the author's official duties as a United States Government employee and
12 * thus cannot be copyrighted. This software/database is freely available
13 * to the public for use. The National Library of Medicine and the U.S.
14 * Government have not placed any restriction on its use or reproduction.
15 *
16 * Although all reasonable efforts have been taken to ensure the accuracy
17 * and reliability of the software and data, the NLM and the U.S.
18 * Government do not and cannot warrant the performance or results that
19 * may be obtained by using this software or data. The NLM and the U.S.
20 * Government disclaim all warranties, express or implied, including
21 * warranties of performance, merchantability or fitness for any particular
22 * purpose.
23 *
24 * Please cite the author in any work or product based on this material.
25 *
26 * ===========================================================================
27 *
28 * File Name: urktree.c
29 *
30 * Author(s): John Kuzio
31 *
32 * Version Creation Date: 98-01-01
33 *
34 * $Revision: 6.6 $
35 *
36 * File Description: trees
37 *
38 * Modifications:
39 * --------------------------------------------------------------------------
40 * Date Name Description of modification
41 * --------------------------------------------------------------------------
42 * $Log: urktree.c,v $
43 * Revision 6.6 2003/05/30 17:25:38 coulouri
44 * add rcsid
45 *
46 * Revision 6.5 1998/09/16 18:03:37 kuzio
47 * cvs logging
48 *
49 *
50 * ==========================================================================
51 */
52
53 #include <urktree.h>
54
TreeCenterNode(TreeNodePtr ptrNode)55 extern TreeNodePtr TreeCenterNode (TreeNodePtr ptrNode)
56 {
57 if (ptrNode == NULL)
58 return ptrNode;
59
60 if (ptrNode->ptrUp == NULL)
61 return ptrNode->ptrUp;
62
63 if (ptrNode->ptrUp->ptrUp == ptrNode)
64 return ptrNode;
65
66 return TreeCenterNode (ptrNode->ptrUp);
67 }
68
ExploreUnrootedTreeNumber(TreeNodePtr ptrNode,Int4 nodenumber)69 extern TreeNodePtr ExploreUnrootedTreeNumber (TreeNodePtr ptrNode,
70 Int4 nodenumber)
71 {
72 ptrNode = TreeCenterNode (ptrNode);
73 return ExploreUnrootedTree (ptrNode, ptrNode, nodenumber);
74 }
75
ExploreUnrootedTree(TreeNodePtr ptrNode,TreeNodePtr ptrSkip,Int4 nodenumber)76 extern TreeNodePtr ExploreUnrootedTree (TreeNodePtr ptrNode,
77 TreeNodePtr ptrSkip,
78 Int4 nodenumber)
79 {
80 TreeNodePtr ptrTemp;
81
82 if (ptrNode == NULL)
83 return ptrNode;
84
85 if (ptrNode->nodenumber == nodenumber)
86 return ptrNode;
87
88 if ((ptrTemp = ExploreUnrootedTree (ptrNode->ptrChildLeft, ptrSkip,
89 nodenumber)) != NULL)
90 return ptrTemp;
91
92 if ((ptrTemp = ExploreUnrootedTree (ptrNode->ptrChildRight, ptrSkip,
93 nodenumber)) != NULL)
94 return ptrTemp;
95
96 if (ptrNode != ptrSkip)
97 return ptrTemp;
98
99 return ExploreUnrootedTree (ptrNode->ptrUp, ptrSkip, nodenumber);
100 }
101
ExploreTreeNumber(TreeNodePtr ptrNode,Int4 nodenumber)102 extern TreeNodePtr ExploreTreeNumber (TreeNodePtr ptrNode,
103 Int4 nodenumber)
104 {
105 TreeNodePtr ptrTemp;
106
107 if (ptrNode == NULL)
108 return ptrNode;
109
110 if (nodenumber == 0)
111 return HeadNode (ptrNode);
112
113 if (nodenumber == -1)
114 return LastNode (HeadNode (ptrNode));
115
116 if (ptrNode->nodenumber == nodenumber)
117 return ptrNode;
118
119 if ((ptrTemp = ExploreTreeNumber (ptrNode->ptrChildLeft,
120 nodenumber)) != NULL)
121 return ptrTemp;
122
123 return ExploreTreeNumber (ptrNode->ptrChildRight, nodenumber);
124 }
125
ExploreTreeLevel(TreeNodePtr ptrNode,TreeNodePtr ptrSkip,Int4 level,Boolean PNTR flagTakeNext)126 extern TreeNodePtr ExploreTreeLevel (TreeNodePtr ptrNode, TreeNodePtr ptrSkip,
127 Int4 level, Boolean PNTR flagTakeNext)
128 {
129 TreeNodePtr ptrTemp;
130
131 if (ptrNode == NULL)
132 return ptrNode;
133
134 if (ptrNode->level == level)
135 {
136 if (ptrSkip == NULL)
137 return ptrNode;
138 if (*flagTakeNext)
139 return ptrNode;
140 if (ptrNode == ptrSkip)
141 *flagTakeNext = TRUE;
142 }
143
144 if ((ptrTemp = ExploreTreeLevel (ptrNode->ptrChildLeft, ptrSkip, level,
145 flagTakeNext)) != NULL)
146 return ptrTemp;
147
148 return ExploreTreeLevel (ptrNode->ptrChildRight, ptrSkip, level,
149 flagTakeNext);
150 }
151
ExploreTree(TreeNodePtr ptrNode,TreeNodePtr ptrSkip,Boolean PNTR flagTakeNext)152 extern TreeNodePtr ExploreTree (TreeNodePtr ptrNode, TreeNodePtr ptrSkip,
153 Boolean PNTR flagTakeNext)
154 {
155 TreeNodePtr ptrTemp;
156
157 if (ptrNode == NULL)
158 return ptrNode;
159
160 if (ptrSkip == NULL)
161 return ptrNode;
162 if (*flagTakeNext)
163 return ptrNode;
164 if (ptrNode == ptrSkip)
165 *flagTakeNext = TRUE;
166
167 if ((ptrTemp = ExploreTree (ptrNode->ptrChildLeft, ptrSkip,
168 flagTakeNext)) != NULL)
169 return ptrTemp;
170
171 return ExploreTree (ptrNode->ptrChildRight, ptrSkip, flagTakeNext);
172 }
173
GetDeepestLevelBranch(TreeNodePtr ptrNode,Int4 level)174 extern Int4 GetDeepestLevelBranch (TreeNodePtr ptrNode, Int4 level)
175 {
176 if (ptrNode == NULL)
177 return level;
178
179 if (ptrNode->ptrChildLeft != NULL || ptrNode->ptrChildRight != NULL)
180 if (ptrNode->level > level)
181 level = ptrNode->level;
182
183 level = GetDeepestLevelBranch (ptrNode->ptrChildLeft, level);
184 level = GetDeepestLevelBranch (ptrNode->ptrChildRight, level);
185
186 return level;
187 }
188
GetDeepestLevel(TreeNodePtr ptrNode)189 extern Int4 GetDeepestLevel (TreeNodePtr ptrNode)
190 {
191 Int4 level;
192
193 if (ptrNode == NULL)
194 return -1;
195 if (ptrNode->ptrChildLeft == NULL && ptrNode->ptrChildRight == NULL)
196 return 0;
197 level = GetDeepestLevelBranch (ptrNode, 0);
198 level++;
199 return level;
200 }
201
GetWidestLevelLeftNode(TreeNodePtr ptrNode,Int4 startlevel)202 extern TreeNodePtr GetWidestLevelLeftNode (TreeNodePtr ptrNode,
203 Int4 startlevel)
204 {
205 Boolean flagTakeNext;
206 TreeNodePtr ptrNodeFind, ptrNodeLeft;
207 Int4 nodecount, nodemax;
208
209 if (ptrNode == NULL)
210 return NULL;
211
212 ptrNodeLeft = NULL;
213 nodemax = 0;
214 ptrNodeFind = NULL;
215 flagTakeNext = FALSE;
216 while ((ptrNodeFind = ExploreTree (ptrNode, ptrNodeFind,
217 &flagTakeNext)) != NULL)
218 {
219 if (ptrNodeFind->ptrLevelLeft == NULL)
220 {
221 if (ptrNodeFind->level > startlevel)
222 {
223 nodecount = CountNodesOnLevel (ptrNodeFind, ptrNodeFind->level);
224 if (nodecount > nodemax)
225 {
226 nodemax = nodecount;
227 ptrNodeLeft = ptrNodeFind;;
228 }
229 }
230 }
231 flagTakeNext = FALSE;
232 }
233 return ptrNodeLeft;
234 }
235
GetLevelLeftNode(TreeNodePtr ptrNode,Int4 level)236 extern TreeNodePtr GetLevelLeftNode (TreeNodePtr ptrNode, Int4 level)
237 {
238 Boolean flagTakeNext;
239 TreeNodePtr ptrNodeFind;
240
241 if (ptrNode == NULL)
242 return NULL;
243
244 ptrNodeFind = NULL;
245 flagTakeNext = FALSE;
246 while ((ptrNodeFind = ExploreTree (ptrNode, ptrNodeFind,
247 &flagTakeNext)) != NULL)
248 {
249 if (ptrNodeFind->level == level)
250 return ptrNodeFind;
251 flagTakeNext = FALSE;
252 }
253 return NULL;
254 }
255
SetLevelNode(TreeNodePtr ptrNode,Int4 level)256 extern void SetLevelNode (TreeNodePtr ptrNode, Int4 level)
257 {
258 if (ptrNode == NULL)
259 return;
260
261 ptrNode->level = level;
262 level++;
263 SetLevelNode (ptrNode->ptrChildLeft, level);
264 SetLevelNode (ptrNode->ptrChildRight, level);
265
266 return;
267 }
268
SetAllLevelNodes(TreeNodePtr ptrNode)269 extern void SetAllLevelNodes (TreeNodePtr ptrNode)
270 {
271 Int4 level;
272
273 if ((ptrNode = HeadNode (ptrNode)) == NULL)
274 return;
275
276 level = 0;
277 ptrNode->level = level;
278 level++;
279 SetLevelNode (ptrNode->ptrChildLeft, level);
280 SetLevelNode (ptrNode->ptrChildRight, level);
281
282 return;
283 }
284
SetNumberNode(TreeNodePtr ptrNode,Int4 nodenumber)285 extern Int4 SetNumberNode (TreeNodePtr ptrNode, Int4 nodenumber)
286 {
287 if (ptrNode == NULL)
288 return nodenumber;
289
290 ptrNode->nodenumber = nodenumber++;
291 nodenumber = SetNumberNode (ptrNode->ptrChildLeft, nodenumber);
292 nodenumber = SetNumberNode (ptrNode->ptrChildRight, nodenumber);
293
294 return nodenumber;
295 }
296
SetAllNumberNodes(TreeNodePtr ptrNode)297 extern Int4 SetAllNumberNodes (TreeNodePtr ptrNode)
298 {
299 Int4 nodenumber;
300
301 if ((ptrNode = HeadNode (ptrNode)) == NULL)
302 return -1;
303
304 nodenumber = 0;
305 ptrNode->nodenumber = nodenumber++;
306 nodenumber = SetNumberNode (ptrNode->ptrChildLeft, nodenumber);
307 nodenumber = SetNumberNode (ptrNode->ptrChildRight, nodenumber);
308
309 return nodenumber;
310 }
311
ZeroNodes(TreeNodePtr ptrNode)312 extern void ZeroNodes (TreeNodePtr ptrNode)
313 {
314 if (ptrNode == NULL)
315 return;
316
317 ptrNode->nodenumber = 0;
318 ZeroNodes (ptrNode->ptrChildLeft);
319 ZeroNodes (ptrNode->ptrChildRight);
320
321 return;
322 }
323
CountNodes(TreeNodePtr ptrNode,Int4 nodenumber)324 extern Int4 CountNodes (TreeNodePtr ptrNode, Int4 nodenumber)
325 {
326 if (ptrNode == NULL)
327 return nodenumber;
328
329 nodenumber++;
330 nodenumber = CountNodes (ptrNode->ptrChildLeft, nodenumber);
331 nodenumber = CountNodes (ptrNode->ptrChildRight, nodenumber);
332
333 return nodenumber;
334 }
335
CountNodesOnLevel(TreeNodePtr ptrNode,Int4 level)336 extern Int4 CountNodesOnLevel (TreeNodePtr ptrNode, Int4 level)
337 {
338 Int4 nodenumber;
339 TreeNodePtr ptrNodeFind;
340 Boolean flagTakeNext;
341
342 if (ptrNode == NULL)
343 return 0;
344
345 nodenumber = 0;
346
347 flagTakeNext = FALSE;
348 if ((ptrNodeFind = ExploreTreeLevel (ptrNode, NULL, level,
349 &flagTakeNext)) != NULL)
350 {
351 while (ptrNodeFind != NULL)
352 {
353 nodenumber++;
354 ptrNodeFind = ptrNodeFind->ptrLevelRight;
355 }
356 }
357 return nodenumber;
358 }
359
HeadNode(TreeNodePtr ptrNode)360 extern TreeNodePtr HeadNode (TreeNodePtr ptrNode)
361 {
362 if (ptrNode == NULL)
363 return ptrNode;
364
365 while (ptrNode->ptrUp != NULL)
366 ptrNode = ptrNode->ptrUp;
367
368 return ptrNode;
369 }
370
LastNode(TreeNodePtr ptrNode)371 extern TreeNodePtr LastNode (TreeNodePtr ptrNode)
372 {
373 TreeNodePtr ptrNodeFind, ptrNodeCurrent;
374 Boolean flagTakeNext;
375
376 if ((ptrNode = HeadNode (ptrNode)) == NULL)
377 return ptrNode;
378
379 flagTakeNext = FALSE;
380 ptrNodeCurrent = ptrNode;
381 while ((ptrNodeFind = ExploreTree (ptrNode, ptrNodeCurrent,
382 &flagTakeNext)) != NULL)
383 {
384 ptrNodeCurrent = ptrNodeFind;
385 flagTakeNext = FALSE;
386 }
387 return ptrNodeCurrent;
388 }
389
FindPivotNode(TreeNodePtr ptrNode,TreeNodePtr ptrSkip)390 extern TreeNodePtr FindPivotNode (TreeNodePtr ptrNode,
391 TreeNodePtr ptrSkip)
392 {
393 if (ptrNode == NULL)
394 return ptrNode;
395
396 if (ptrNode != ptrSkip)
397 {
398 if (ptrNode->flagPivot)
399 return ptrNode;
400 }
401
402 if ((ptrNode = FindPivotNode (ptrNode->ptrChildLeft, ptrSkip)) != NULL)
403 return ptrNode;
404
405 return FindPivotNode (ptrNode->ptrChildRight, ptrSkip);
406 }
407
SetPivotNode(TreeNodePtr ptrNode,Int4 level)408 extern TreeNodePtr SetPivotNode (TreeNodePtr ptrNode, Int4 level)
409 {
410 TreeNodePtr ptrOne, ptrTwo;
411 Boolean flagTakeNext;
412
413 if (ptrNode == NULL)
414 return ptrNode;
415
416 flagTakeNext = FALSE;
417 ptrOne = ExploreTreeLevel (ptrNode, NULL, level, &flagTakeNext);
418 ptrTwo = ExploreTreeLevel (ptrNode, ptrOne, level, &flagTakeNext);
419
420 if (ptrOne != NULL && ptrTwo == NULL)
421 {
422 ptrOne->flagPivot = TRUE;
423 return ptrOne;
424 }
425 else
426 {
427 return NULL;
428 }
429 }
430
SetAllPivotNodes(TreeNodePtr ptrNode)431 extern TreeNodePtr SetAllPivotNodes (TreeNodePtr ptrNode)
432 {
433 Int4 i, level;
434 TreeNodePtr ptrPivot;
435
436 if ((ptrNode = HeadNode (ptrNode)) == NULL)
437 return ptrNode;
438
439 UnSetPivotNodes (ptrNode);
440 level = GetDeepestLevelBranch (ptrNode, -1);
441
442 for (i = 0; i < level; i++)
443 {
444 ptrPivot = SetPivotNode (ptrNode, i);
445 if (ptrPivot != NULL)
446 ptrNode = ptrPivot;
447 }
448 return HeadNode (ptrNode);
449 }
450
UnSetPivotNodes(TreeNodePtr ptrNode)451 extern void UnSetPivotNodes (TreeNodePtr ptrNode)
452 {
453 if (ptrNode == NULL)
454 return;
455
456 ptrNode->flagPivot = FALSE;;
457 UnSetPivotNodes (ptrNode->ptrChildLeft);
458 UnSetPivotNodes (ptrNode->ptrChildRight);
459
460 return;
461 }
462
SetLeftRightRootedTreeNeighbors(TreeNodePtr ptrNode,Int4 level)463 extern void SetLeftRightRootedTreeNeighbors (TreeNodePtr ptrNode, Int4 level)
464 {
465 TreeNodePtr ptrNodeFind, ptrNodeCurrent;
466 Boolean flagTakeNext;
467
468 if (ptrNode == NULL)
469 return;
470
471 ptrNodeFind = ptrNodeCurrent = NULL;
472 flagTakeNext = FALSE;
473 while ((ptrNodeFind = ExploreTreeLevel (ptrNode, ptrNodeFind, level,
474 &flagTakeNext)) != NULL)
475 {
476 ptrNodeFind->ptrLevelLeft = NULL;
477 ptrNodeFind->ptrLevelRight = NULL;
478 if (ptrNodeCurrent != NULL)
479 {
480 ptrNodeCurrent->ptrLevelRight = ptrNodeFind;
481 ptrNodeFind->ptrLevelLeft = ptrNodeCurrent;
482 }
483 ptrNodeCurrent = ptrNodeFind;
484 flagTakeNext = FALSE;
485 }
486
487 return;
488 }
489
SetAllLeftRightRootedTreeNeighbors(TreeNodePtr ptrNode)490 extern void SetAllLeftRightRootedTreeNeighbors (TreeNodePtr ptrNode)
491 {
492 Int4 i, depth;
493
494 if (TestTree (ptrNode) != TREE_ROOTED)
495 return;
496 ptrNode = HeadNode (ptrNode);
497 SetLevelNode (ptrNode, 0);
498 depth = GetDeepestLevel (ptrNode);
499 for (i = 0; i <= depth; i++)
500 SetLeftRightRootedTreeNeighbors (ptrNode, i);
501
502 return;
503 }
504
GetMaximumTreeXcoord(TreeNodePtr ptrNode)505 extern Int4 GetMaximumTreeXcoord (TreeNodePtr ptrNode)
506 {
507 Int4 max;
508 TreeNodePtr ptrNodeCurrent;
509 Boolean flagTakeNext;
510
511 if (ptrNode == NULL)
512 return 0;
513
514 max = ptrNode->xcoord;
515 flagTakeNext = FALSE;
516 ptrNodeCurrent = NULL;
517 while ((ptrNodeCurrent = ExploreTree (ptrNode, ptrNodeCurrent,
518 &flagTakeNext)) != NULL)
519 {
520 if (ptrNodeCurrent->xcoord > max)
521 max = ptrNodeCurrent->xcoord;
522 flagTakeNext = FALSE;
523 }
524 return max;
525 }
526
GetMinimumTreeXcoord(TreeNodePtr ptrNode)527 extern Int4 GetMinimumTreeXcoord (TreeNodePtr ptrNode)
528 {
529 Int4 min;
530 TreeNodePtr ptrNodeCurrent;
531 Boolean flagTakeNext;
532
533 if (ptrNode == NULL)
534 return 0;
535
536 min = ptrNode->xcoord;
537 flagTakeNext = FALSE;
538 ptrNodeCurrent = NULL;
539 while ((ptrNodeCurrent = ExploreTree (ptrNode, ptrNodeCurrent,
540 &flagTakeNext)) != NULL)
541 {
542 if (ptrNodeCurrent->xcoord < min)
543 min = ptrNodeCurrent->xcoord;
544 flagTakeNext = FALSE;
545 }
546 return min;
547 }
548
GetMaximumTreeYcoord(TreeNodePtr ptrNode)549 extern Int4 GetMaximumTreeYcoord (TreeNodePtr ptrNode)
550 {
551 Int4 max;
552 TreeNodePtr ptrNodeCurrent;
553 Boolean flagTakeNext;
554
555 if (ptrNode == NULL)
556 return 0;
557
558 max = ptrNode->ycoord;
559 flagTakeNext = FALSE;
560 ptrNodeCurrent = NULL;
561 while ((ptrNodeCurrent = ExploreTree (ptrNode, ptrNodeCurrent,
562 &flagTakeNext)) != NULL)
563 {
564 if (ptrNodeCurrent->ycoord > max)
565 max = ptrNodeCurrent->ycoord;
566 flagTakeNext = FALSE;
567 }
568 return max;
569 }
570
GetMinimumTreeYcoord(TreeNodePtr ptrNode)571 extern Int4 GetMinimumTreeYcoord (TreeNodePtr ptrNode)
572 {
573 Int4 min;
574 TreeNodePtr ptrNodeCurrent;
575 Boolean flagTakeNext;
576
577 if (ptrNode == NULL)
578 return 0;
579
580 min = ptrNode->ycoord;
581 flagTakeNext = FALSE;
582 ptrNodeCurrent = NULL;
583 while ((ptrNodeCurrent = ExploreTree (ptrNode, ptrNodeCurrent,
584 &flagTakeNext)) != NULL)
585 {
586 if (ptrNodeCurrent->ycoord < min)
587 min = ptrNodeCurrent->ycoord;
588 flagTakeNext = FALSE;
589 }
590 return min;
591 }
592
SetAllCoordinates(TreeNodePtr ptrNode,Int4 Xcoord,Int4 Ycoord,Int4 Xdelta,Int4 Ydelta)593 extern void SetAllCoordinates (TreeNodePtr ptrNode, Int4 Xcoord, Int4 Ycoord,
594 Int4 Xdelta, Int4 Ydelta)
595 {
596 Int4 level, levelold, tlevel, decomp;
597 Int4 depth, width, widthold;
598 Int4 midpoint, xleft, xright, xleftold, xrightold, xthis;
599 Int4 xmin, xdiff;
600 Int4 index, indexshift;
601 TreeNodePtr ptrNodeCurr, ptrNodeThis, ptrNodeLeft, ptrNodeCheck, ptrNodeS;
602 Boolean flagTakeNext;
603
604 if (TestTree (ptrNode) != TREE_ROOTED)
605 return;
606 ptrNode = HeadNode (ptrNode);
607 ptrNode->xcoord = Xcoord;
608 ptrNode->ycoord = Ycoord;
609
610 SetAllLevelNodes (ptrNode);
611 depth = GetDeepestLevel (ptrNode);
612
613 levelold = level = 0;
614 widthold = 1;
615 xleftold = Xcoord;
616 xrightold = Xcoord;
617 while (level <= depth)
618 {
619 ptrNodeLeft = GetWidestLevelLeftNode (ptrNode, level);
620 if (ptrNodeLeft == NULL)
621 break;
622 level = ptrNodeLeft->level;
623 width = CountNodesOnLevel (ptrNode, level);
624 if (widthold < width)
625 {
626 decomp = 1;
627 midpoint = (xrightold + xleftold) / 2;
628 }
629 else
630 {
631 decomp = widthold / width;
632 ptrNodeCheck = ptrNodeLeft;
633 while (ptrNodeCheck->level != levelold)
634 ptrNodeCheck = ptrNodeCheck->ptrUp;
635 midpoint = ptrNodeCheck->xcoord;
636 }
637 if (level > levelold+1)
638 {
639 xthis = midpoint -
640 (((width*Xdelta*decomp)+((width/2-1)*Xdelta*decomp))/2);
641 }
642 else
643 {
644 xthis = ptrNodeLeft->ptrUp->xcoord - (Xdelta*decomp);
645 }
646 ptrNodeThis = ptrNodeLeft;
647 while (ptrNodeThis != NULL)
648 {
649 if (ptrNodeThis->ptrLevelLeft != NULL)
650 {
651 if (((ptrNodeThis->ptrChildLeft == NULL) &&
652 (ptrNodeThis->ptrChildRight == NULL)) &&
653 ((ptrNodeThis->ptrLevelLeft->ptrChildLeft == NULL) &&
654 (ptrNodeThis->ptrLevelLeft->ptrChildRight == NULL)))
655 xthis += (Xdelta*decomp);
656 }
657 ptrNodeThis->xcoord = xthis;
658 ptrNodeThis->ycoord = Ycoord + (level*Ydelta);
659 xthis += (Xdelta*2*decomp);
660 ptrNodeThis->ptrLevelRight->xcoord = xthis;
661 ptrNodeThis->ptrLevelRight->ycoord = Ycoord + (level*Ydelta);
662 xthis += (Xdelta*decomp);
663 ptrNodeThis = ptrNodeThis->ptrLevelRight->ptrLevelRight;
664 }
665 ptrNodeCurr = ptrNodeLeft;
666 for (tlevel = level; tlevel != levelold; tlevel--)
667 {
668 ptrNodeThis = ptrNodeCurr;
669 while (ptrNodeThis != NULL)
670 {
671 if (ptrNodeThis->xcoord == 0 && ptrNodeThis->ycoord == 0)
672 {
673 ptrNodeThis->xcoord = ptrNodeThis->ptrLevelLeft->xcoord + Xdelta;
674 if (((ptrNodeThis->ptrChildLeft == NULL) &&
675 (ptrNodeThis->ptrChildRight == NULL)) &&
676 ((ptrNodeThis->ptrLevelLeft->ptrChildLeft == NULL) &&
677 (ptrNodeThis->ptrLevelLeft->ptrChildRight == NULL)))
678 ptrNodeThis->xcoord += Xdelta;
679 ptrNodeThis->ycoord = Ycoord + (tlevel * Ydelta);
680 if ((ptrNodeThis->xcoord >= ptrNodeThis->ptrLevelRight->xcoord) &&
681 ptrNodeThis->ptrLevelRight->xcoord != 0 &&
682 ptrNodeThis->ptrLevelRight->ycoord != 0)
683 {
684 xdiff = ptrNodeThis->xcoord -
685 ptrNodeThis->ptrLevelRight->xcoord + Xdelta;
686 ptrNodeCheck = ptrNodeThis->ptrLevelRight;
687 while (ptrNodeCheck != NULL)
688 {
689 if (ptrNodeCheck->xcoord != 0 &&
690 ptrNodeCheck->ycoord != 0)
691 {
692 ptrNodeCheck->xcoord += xdiff;
693 flagTakeNext = FALSE;
694 ptrNodeS = ptrNodeCheck;
695 while ((ptrNodeS = ExploreTree (ptrNodeCheck, ptrNodeS,
696 &flagTakeNext)) != NULL)
697 {
698 if (ptrNodeS->level <= level)
699 ptrNodeS->xcoord += xdiff;
700 flagTakeNext = FALSE;
701 }
702 }
703 ptrNodeCheck = ptrNodeCheck->ptrLevelRight;
704 }
705 }
706 }
707 ptrNodeThis = ptrNodeThis->ptrLevelRight;
708 }
709 if (tlevel == levelold+1)
710 break;
711 ptrNodeThis = ptrNodeCurr;
712 while (ptrNodeThis != NULL)
713 {
714 xthis = (ptrNodeThis->xcoord + ptrNodeThis->ptrLevelRight->xcoord) / 2;
715 ptrNodeThis->ptrUp->xcoord = xthis;
716 ptrNodeThis->ptrUp->ycoord = Ycoord + ((tlevel-1)*Ydelta);
717 if (ptrNodeThis->ptrLevelRight->ptrLevelRight == NULL)
718 {
719 ptrNodeCheck = ptrNodeThis->ptrUp->ptrLevelRight;
720 while (ptrNodeCheck != NULL)
721 {
722 xthis += (Xdelta*2*decomp);
723 ptrNodeCheck->xcoord = xthis;
724 ptrNodeCheck->ycoord = Ycoord + ((tlevel-1)*Ydelta);
725 ptrNodeCheck = ptrNodeCheck->ptrLevelRight;
726 }
727 }
728 ptrNodeThis = ptrNodeThis->ptrLevelRight->ptrLevelRight;
729 }
730 ptrNodeCurr = ptrNodeCheck = ptrNodeCurr->ptrUp;
731 xthis = ptrNodeCheck->xcoord;
732 ptrNodeCheck = ptrNodeCheck->ptrLevelLeft;
733 while (ptrNodeCheck != NULL)
734 {
735 xthis -= (Xdelta*2*decomp);
736 ptrNodeCheck->xcoord = xthis;
737 ptrNodeCheck->ycoord = Ycoord + ((tlevel-1)*Ydelta);
738 ptrNodeCheck = ptrNodeCheck->ptrLevelLeft;
739 }
740 while (ptrNodeCurr->ptrLevelLeft != NULL)
741 ptrNodeCurr = ptrNodeCurr->ptrLevelLeft;
742 }
743 if (levelold == 0)
744 {
745 ptrNodeThis = ptrNodeCurr;
746 if (ptrNodeThis != NULL)
747 {
748 xthis = (ptrNodeThis->xcoord + ptrNodeThis->ptrLevelRight->xcoord) / 2;
749 ptrNodeThis->ptrUp->xcoord = xthis;
750 }
751 }
752 levelold = level;
753 widthold = width;
754
755 ptrNodeLeft = GetLevelLeftNode (ptrNode, level);
756 xleft = ptrNodeLeft->xcoord;
757 while (ptrNodeLeft->ptrLevelRight != NULL)
758 ptrNodeLeft = ptrNodeLeft->ptrLevelRight;
759 xright = ptrNodeLeft->xcoord;
760
761 xleftold = xleft;
762 xrightold = xright;
763 }
764 for (level = 0; level <= depth; level++)
765 {
766 ptrNodeCheck = ptrNodeLeft = GetLevelLeftNode (ptrNode, level);
767 if (ptrNodeLeft != NULL && ptrNodeLeft->ptrUp != NULL)
768 {
769 index = indexshift = 0;
770 while (ptrNodeCheck->ptrLevelRight != NULL)
771 {
772 index++;
773 if (ptrNodeCheck->ptrLevelRight->xcoord >=
774 ptrNodeCheck->ptrLevelRight->ptrUp->xcoord)
775 {
776 indexshift = -1;
777 }
778 else
779 {
780 if (indexshift == -1)
781 indexshift = index;
782 }
783 ptrNodeCheck = ptrNodeCheck->ptrLevelRight;
784 }
785 if (indexshift > -1)
786 {
787 ptrNodeCheck = ptrNodeLeft;
788 index = 0;
789 while (index < indexshift)
790 {
791 ptrNodeCheck = ptrNodeCheck->ptrLevelRight;
792 index++;
793 }
794 xdiff = ptrNodeCheck->ptrUp->xcoord - ptrNodeCheck->xcoord - Xdelta;
795 while (ptrNodeCheck != NULL)
796 {
797 ptrNodeCheck->xcoord += xdiff;
798 ptrNodeCheck = ptrNodeCheck->ptrLevelRight;
799 }
800 level--;
801 }
802 }
803 }
804 xmin = GetMinimumTreeXcoord (ptrNode);
805 if (xmin < 0)
806 {
807 xmin *= -1;
808 xmin += 25;
809 ShiftTree (ptrNode, xmin, 0);
810 }
811 return;
812 }
813
SetTheoreticalCoordinates(TreeNodePtr ptrNode,Int4 xcoord,Int4 ycoord,Int4 xdelta,Int4 ydelta,Int4 xroot,Int4 xparent,Int4 xoffset,Int4 xoffmax)814 extern void SetTheoreticalCoordinates (TreeNodePtr ptrNode,
815 Int4 xcoord, Int4 ycoord,
816 Int4 xdelta, Int4 ydelta,
817 Int4 xroot, Int4 xparent,
818 Int4 xoffset, Int4 xoffmax)
819 {
820 Int4 xLcoord, xRcoord, xLoffset, xRoffset;
821
822 if (ptrNode == NULL)
823 return;
824
825 ptrNode->xcoord = xcoord;
826 ptrNode->ycoord = ycoord;
827
828 if (xcoord >= xroot)
829 {
830 xRoffset = (xoffset * xdelta * 3) + xparent;
831 xLcoord = xRoffset - xdelta;
832 if (xLcoord < xcoord)
833 xLcoord = xcoord;
834 xRcoord = xRoffset + xdelta;
835 if (xoffset > xoffmax)
836 {
837 xoffset = (Int4) pow (2, 20);
838 }
839 SetTheoreticalCoordinates (ptrNode->ptrChildLeft,
840 xLcoord, ycoord+ydelta,
841 xdelta, ydelta, xroot,
842 xparent, 2*xoffset, xoffmax);
843 SetTheoreticalCoordinates (ptrNode->ptrChildRight,
844 xRcoord, ycoord+ydelta,
845 xdelta, ydelta, xroot,
846 xparent, 2*xoffset+1, xoffmax);
847 }
848 else
849 {
850 xLoffset = xparent - (xoffset * xdelta * 3);
851 xLcoord = xLoffset - xdelta;
852 xRcoord = xLoffset + xdelta;
853 if (xRcoord > xcoord)
854 xRcoord = xcoord;
855 SetTheoreticalCoordinates (ptrNode->ptrChildLeft,
856 xLcoord, ycoord+ydelta,
857 xdelta, ydelta, xroot,
858 xparent, 2*xoffset+1, xoffmax);
859 SetTheoreticalCoordinates (ptrNode->ptrChildRight,
860 xRcoord, ycoord+ydelta,
861 xdelta, ydelta, xroot,
862 xparent, 2*xoffset, xoffmax);
863 }
864 return;
865 }
866
SetAllTheoreticalCoordinates(TreeNodePtr ptrNode,Int4 xcoord,Int4 ycoord)867 extern void SetAllTheoreticalCoordinates (TreeNodePtr ptrNode,
868 Int4 xcoord, Int4 ycoord)
869 {
870 Int4 xdelta, ydelta, xoffmax;
871
872 if (TestTree (ptrNode) != TREE_ROOTED)
873 return;
874 ptrNode = HeadNode (ptrNode);
875
876 ptrNode->xcoord = xcoord;
877 ptrNode->ycoord = ycoord;
878 xdelta = 1;
879 ydelta = 1;
880
881 xoffmax = (Int4) pow (2, 29);
882
883 SetTheoreticalCoordinates (ptrNode->ptrChildLeft,
884 xcoord-xdelta, ycoord+ydelta, xdelta, ydelta,
885 xcoord, xcoord-xdelta, 0, xoffmax);
886 SetTheoreticalCoordinates (ptrNode->ptrChildRight,
887 xcoord+xdelta, ycoord+ydelta, xdelta, ydelta,
888 xcoord, xcoord+xdelta, 0, xoffmax);
889 return;
890 }
891
AdjustTheoreticalCoordinates(TreeNodePtr ptrNode,Int4 Xcoord,Int4 Xdelta,Int4 level)892 extern void AdjustTheoreticalCoordinates (TreeNodePtr ptrNode,
893 Int4 Xcoord, Int4 Xdelta,
894 Int4 level)
895 {
896 Int4 xpleft, xpright, xpdelta, xleft, xright, xdelta;
897 Boolean flagTakeNext, flagOnEntry;
898 TreeNodePtr ptrNodeLeftEnd, ptrNodeStart, ptrNodeCurrent, ptrNodeLoop;
899
900 flagOnEntry = TRUE;
901 flagTakeNext = FALSE;
902 if ((ptrNodeLeftEnd = ExploreTreeLevel (ptrNode, NULL, level,
903 &flagTakeNext)) == NULL)
904 return;
905
906 if (ptrNodeLeftEnd->ptrUp == NULL)
907 return;
908
909 ptrNodeCurrent = ptrNodeStart = ptrNodeLeftEnd;
910 while (ptrNodeCurrent->ptrLevelRight != NULL)
911 {
912 if (flagOnEntry && ptrNodeCurrent->xcoord >= Xcoord)
913 {
914 flagOnEntry = FALSE;
915 xleft = ptrNodeCurrent->xcoord;
916 xpleft = ptrNodeCurrent->ptrUp->xcoord;
917 xdelta = xleft - xpleft + Xdelta;
918 for (ptrNodeLoop = ptrNodeCurrent;
919 ptrNodeLoop != NULL;
920 ptrNodeLoop = ptrNodeLoop->ptrLevelRight)
921 {
922 ptrNodeLoop->xcoord -= xdelta;
923 }
924 continue;
925 }
926 flagOnEntry = FALSE;
927 if (ptrNodeCurrent->ptrLevelRight->ptrLevelRight == NULL &&
928 ptrNodeCurrent == ptrNodeStart)
929 {
930 if (ptrNodeCurrent->ptrLevelLeft != NULL)
931 {
932 xdelta = ptrNodeCurrent->xcoord -
933 ptrNodeCurrent->ptrLevelRight->xcoord;
934 }
935 else
936 {
937 xdelta = ptrNodeCurrent->xcoord + Xdelta -
938 ptrNodeCurrent->ptrUp->xcoord;
939 }
940 if (xdelta < 0)
941 xdelta *= -1;
942 if (xdelta > 2*Xdelta)
943 {
944 if (ptrNodeCurrent->xcoord >= Xcoord)
945 {
946 while (ptrNodeCurrent != NULL)
947 {
948 ptrNodeCurrent->xcoord -= xdelta;
949 ptrNodeCurrent = ptrNodeCurrent->ptrLevelRight;
950 }
951 }
952 else
953 {
954 while (ptrNodeCurrent->ptrLevelRight != NULL)
955 {
956 ptrNodeCurrent = ptrNodeCurrent->ptrLevelRight;
957 }
958 while (ptrNodeCurrent != ptrNodeStart)
959 {
960 ptrNodeCurrent->xcoord += xdelta;
961 ptrNodeCurrent = ptrNodeCurrent->ptrLevelLeft;
962 }
963 ptrNodeCurrent->xcoord += xdelta;
964 }
965 }
966 ptrNodeCurrent = ptrNodeStart->ptrLevelRight;
967 continue;
968 }
969
970 xleft = ptrNodeCurrent->xcoord;
971 xright = ptrNodeCurrent->ptrLevelRight->xcoord;
972 xdelta = xright - xleft;
973 xpleft = ptrNodeCurrent->ptrUp->xcoord;
974 xpright = ptrNodeCurrent->ptrLevelRight->ptrUp->xcoord;
975 xpdelta = xpright - xpleft;
976
977 if (xdelta > 2*Xdelta)
978 {
979 if (xleft >= Xcoord && xright >= Xcoord)
980 {
981 if (xright == xpright)
982 xright -= Xdelta;
983 ptrNodeCurrent->ptrLevelRight->xcoord = xright;
984 xdelta = xright - xleft - Xdelta;
985 if (((ptrNodeCurrent->ptrChildLeft == NULL) &&
986 (ptrNodeCurrent->ptrChildRight == NULL)) &&
987 ((ptrNodeCurrent->ptrLevelRight->ptrChildLeft == NULL) &&
988 (ptrNodeCurrent->ptrLevelRight->ptrChildRight == NULL)))
989 xdelta -= Xdelta;
990 if (xdelta > xright - xpright + Xdelta)
991 xdelta = xright - xpright + Xdelta;
992 for (ptrNodeLoop = ptrNodeCurrent->ptrLevelRight;
993 ptrNodeLoop != NULL;
994 ptrNodeLoop = ptrNodeLoop->ptrLevelRight)
995 {
996 ptrNodeLoop->xcoord -= xdelta;
997 }
998 }
999 else if (xleft < Xcoord && xright < Xcoord)
1000 {
1001 if (xleft == xpleft)
1002 xleft += Xdelta;
1003 ptrNodeCurrent->xcoord = xleft;
1004 xdelta = xpright - xleft - Xdelta - Xdelta;
1005 if (((ptrNodeCurrent->ptrChildLeft == NULL) &&
1006 (ptrNodeCurrent->ptrChildRight == NULL)) &&
1007 ((ptrNodeCurrent->ptrLevelLeft->ptrChildLeft == NULL) &&
1008 (ptrNodeCurrent->ptrLevelLeft->ptrChildRight == NULL)))
1009 xdelta -= Xdelta;
1010 if (xdelta > xpleft - xleft + Xdelta)
1011 xdelta = xpleft - xleft + Xdelta;
1012 for (ptrNodeLoop = ptrNodeCurrent;
1013 ptrNodeLoop != ptrNodeStart;
1014 ptrNodeLoop = ptrNodeLoop->ptrLevelLeft)
1015 {
1016 ptrNodeLoop->xcoord += xdelta;
1017 }
1018 ptrNodeLoop->xcoord += xdelta;
1019 }
1020 else
1021 {
1022 if (xpdelta > 2*Xdelta)
1023 {
1024 if (xright == xpright)
1025 xright -= Xdelta;
1026 if (xleft == xpleft)
1027 xleft += Xdelta;
1028 }
1029 ptrNodeCurrent->ptrLevelRight->xcoord = xright;
1030 xdelta = xright - xpright + Xdelta;
1031 for (ptrNodeLoop = ptrNodeCurrent->ptrLevelRight;
1032 ptrNodeLoop != NULL;
1033 ptrNodeLoop = ptrNodeLoop->ptrLevelRight)
1034 {
1035 ptrNodeLoop->xcoord -= xdelta;
1036 }
1037 ptrNodeCurrent->xcoord = xleft;
1038 xdelta = xpleft - xleft + Xdelta;
1039 for (ptrNodeLoop = ptrNodeCurrent;
1040 ptrNodeLoop != ptrNodeStart;
1041 ptrNodeLoop = ptrNodeLoop->ptrLevelLeft)
1042 {
1043 ptrNodeLoop->xcoord += xdelta;
1044 }
1045 ptrNodeLoop->xcoord += xdelta;
1046 if (xpdelta <= 2*Xdelta)
1047 {
1048 xright = xpright;
1049 xleft = xpleft;
1050 ptrNodeCurrent->ptrLevelRight->xcoord = xright;
1051 ptrNodeCurrent->xcoord = xleft;
1052 }
1053 }
1054 ptrNodeStart = ptrNodeCurrent->ptrLevelRight;
1055 }
1056 ptrNodeCurrent = ptrNodeCurrent->ptrLevelRight;
1057 }
1058
1059 return;
1060 }
1061
AdjustAllTheoreticalCoordinates(TreeNodePtr ptrNode,Int4 Xcoord)1062 extern void AdjustAllTheoreticalCoordinates (TreeNodePtr ptrNode, Int4 Xcoord)
1063 {
1064 Int4 i, depth, xmin;
1065 Int4 Xdelta;
1066
1067 if (TestTree (ptrNode) != TREE_ROOTED)
1068 return;
1069 ptrNode = HeadNode (ptrNode);
1070 depth = GetDeepestLevel (ptrNode);
1071 Xdelta = 1;
1072
1073 for (i = 0; i <= depth; i++)
1074 AdjustTheoreticalCoordinates (ptrNode, Xcoord, Xdelta, i);
1075
1076 xmin = GetMinimumTreeXcoord (ptrNode);
1077 if (xmin < 0)
1078 {
1079 xmin *= -1;
1080 xmin += 25;
1081 ShiftTree (ptrNode, xmin, 0);
1082 }
1083 return;
1084 }
1085
ChangeTreeScale(TreeNodePtr ptrNode,Int4 Xcoord,Int4 Ycoord,FloatHi sx,FloatHi sy)1086 extern void ChangeTreeScale (TreeNodePtr ptrNode, Int4 Xcoord, Int4 Ycoord,
1087 FloatHi sx, FloatHi sy)
1088 {
1089 Boolean flagTakeNext;
1090 TreeNodePtr ptrNodeCurrent;
1091 FloatHi tx, ty;
1092
1093 if (TestTree (ptrNode) != TREE_ROOTED)
1094 return;
1095 ptrNode = HeadNode (ptrNode);
1096
1097 flagTakeNext = FALSE;
1098 ptrNodeCurrent = NULL;
1099 while ((ptrNodeCurrent = ExploreTree (ptrNode, ptrNodeCurrent,
1100 &flagTakeNext)) != NULL)
1101 {
1102 tx = (FloatHi) (ptrNodeCurrent->xcoord - Xcoord);
1103 ty = (FloatHi) (ptrNodeCurrent->ycoord - Ycoord);
1104 tx *= sx;
1105 ty *= sy;
1106 if (tx >= 0.0)
1107 {
1108 if (tx - (FloatHi) ((Int4) tx) >= 0.5)
1109 tx += 1.0;
1110 }
1111 else
1112 {
1113 if (tx + (FloatHi) ((Int4) tx) <= 0.5)
1114 tx -= 1.0;
1115 }
1116 if (ty >= 0.0)
1117 {
1118 if (ty - (FloatHi) ((Int4) ty) >= 0.5)
1119 ty += 1.0;
1120 }
1121 else
1122 {
1123 if (ty - (FloatHi) ((Int4) ty) <= 0.5)
1124 ty -= 1.0;
1125 }
1126 ptrNodeCurrent->xcoord = Xcoord + (Int4) tx;
1127 ptrNodeCurrent->ycoord = Ycoord + (Int4) ty;
1128 flagTakeNext = FALSE;
1129 }
1130 return;
1131 }
1132
ShiftTree(TreeNodePtr ptrNode,Int4 sx,Int4 sy)1133 extern void ShiftTree (TreeNodePtr ptrNode, Int4 sx, Int4 sy)
1134 {
1135 Boolean flagTakeNext;
1136 TreeNodePtr ptrNodeCurrent;
1137
1138 if (TestTree (ptrNode) != TREE_ROOTED)
1139 return;
1140 ptrNode = HeadNode (ptrNode);
1141
1142 flagTakeNext = FALSE;
1143 ptrNodeCurrent = NULL;
1144 while ((ptrNodeCurrent = ExploreTree (ptrNode, ptrNodeCurrent,
1145 &flagTakeNext)) != NULL)
1146 {
1147 ptrNodeCurrent->xcoord += sx;
1148 ptrNodeCurrent->ycoord += sy;
1149 flagTakeNext = FALSE;
1150 }
1151 return;
1152 }
1153
TestTree(TreeNodePtr ptrNode)1154 extern Int4 TestTree (TreeNodePtr ptrNode)
1155 {
1156 if (ptrNode == NULL)
1157 return TREE_NULL;
1158
1159 while (ptrNode != NULL && ptrNode->ptrUp != NULL)
1160 {
1161 if (ptrNode->ptrUp->ptrUp == ptrNode)
1162 return TREE_UNROOTED;
1163 ptrNode = ptrNode->ptrUp;
1164 }
1165 return TREE_ROOTED;
1166 }
1167
RootTree(TreeNodePtr ptrNode,Int4 left,Int4 right)1168 extern TreeNodePtr RootTree (TreeNodePtr ptrNode, Int4 left, Int4 right)
1169 {
1170 TreeNodePtr ptrTemp;
1171
1172 if (TestTree (ptrNode) == TREE_ROOTED)
1173 return NULL;
1174
1175 ptrNode = ExploreUnrootedTreeNumber (ptrNode, left);
1176 if (ptrNode != NULL)
1177 {
1178 ptrTemp = TreeNodeNew ();
1179
1180 if (ptrNode->ptrUp->ptrUp == ptrNode)
1181 {
1182 ptrTemp->ptrChildRight = ptrNode->ptrUp;
1183 ptrTemp->ptrChildLeft = ptrNode;
1184 ptrTemp->ptrChildRight->ptrUp = ptrTemp;
1185 ptrTemp->ptrChildLeft->ptrUp = ptrTemp;
1186 return ptrTemp;
1187 }
1188
1189 while (ptrNode->ptrUp->ptrUp != ptrNode)
1190 {
1191 /* if right then want to mirror and force left */
1192 if ((ptrNode->ptrChildRight != NULL) &&
1193 (ptrNode->ptrChildRight->nodenumber == right))
1194 {
1195 ptrTemp->ptrChildLeft = ptrNode->ptrChildRight;
1196 ptrNode->ptrChildRight = ptrNode->ptrChildLeft;
1197 ptrNode->ptrChildLeft = ptrTemp->ptrChildLeft;
1198 ptrTemp->ptrChildLeft = NULL;
1199 }
1200
1201 if ((ptrNode->ptrChildLeft != NULL) &&
1202 (ptrNode->ptrChildLeft->nodenumber == right))
1203 {
1204 ptrTemp->ptrChildLeft = ptrNode->ptrChildLeft;
1205 ptrNode->ptrChildLeft->ptrUp = ptrTemp;
1206 }
1207 else /* will root the tree -- default is up */
1208 {
1209 if (ptrNode->ptrUp->ptrChildRight == ptrNode)
1210 {
1211 /* if right then want to mirror and force left */
1212 ptrTemp->ptrChildRight = ptrNode->ptrUp->ptrChildRight;
1213 ptrNode->ptrUp->ptrChildRight = ptrNode->ptrUp->ptrChildLeft;
1214 ptrNode->ptrUp->ptrChildLeft = ptrTemp->ptrChildRight;
1215 ptrTemp->ptrChildRight = NULL;
1216 }
1217 if (ptrNode->ptrUp->ptrChildLeft == ptrNode) /* must be */
1218 {
1219 ptrTemp->ptrChildLeft = ptrNode;
1220 ptrNode = ptrNode->ptrUp;
1221 }
1222 }
1223 ptrTemp->ptrChildRight = ptrNode;
1224 ptrNode->ptrChildLeft = ptrNode->ptrUp;
1225 ptrNode->ptrUp = ptrTemp;
1226 ptrNode = ptrTemp;
1227 }
1228 ptrNode->ptrChildLeft = ptrNode->ptrUp;
1229 while (ptrNode->ptrUp != NULL)
1230 ptrNode = ptrNode->ptrUp;
1231 }
1232 return ptrNode;
1233 }
1234
UnrootTree(TreeNodePtr ptrNode)1235 extern TreeNodePtr UnrootTree (TreeNodePtr ptrNode)
1236 {
1237 TreeNodePtr ptrTemp;
1238
1239 if (TestTree (ptrNode) == TREE_UNROOTED)
1240 return NULL;
1241
1242 ptrNode = HeadNode (ptrNode);
1243 if (ptrNode != NULL)
1244 {
1245 ptrNode->ptrChildLeft->ptrUp = ptrNode->ptrChildRight;
1246 ptrNode->ptrChildRight->ptrUp = ptrNode->ptrChildLeft;
1247 ptrTemp = ptrNode->ptrChildLeft;
1248 ptrNode->ptrChildLeft = NULL;
1249 ptrNode->ptrChildRight = NULL;
1250 TreeNodeFree (ptrNode);
1251 ptrNode = ptrTemp;
1252 }
1253 return ptrNode;
1254 }
1255
TreeNodeNew(void)1256 extern TreeNodePtr TreeNodeNew (void)
1257 {
1258 TreeNodePtr ptrNode;
1259
1260 if ((ptrNode = (TreeNodePtr) MemNew (sizeof (TreeNode))) != NULL)
1261 {
1262 ptrNode->score = 0.0;
1263 ptrNode->flagPivot = FALSE;
1264 ptrNode->level = 0;
1265 ptrNode->nodenumber = 0;
1266 ptrNode->ptrUp = NULL;
1267 ptrNode->ptrChildLeft = NULL;
1268 ptrNode->ptrChildRight = NULL;
1269 ptrNode->ptrLevelLeft = NULL;
1270 ptrNode->ptrLevelRight = NULL;
1271 }
1272 return ptrNode;
1273 }
1274
TreeNodeFree(TreeNodePtr ptrNode)1275 extern TreeNodePtr TreeNodeFree (TreeNodePtr ptrNode)
1276 {
1277 MemFree (ptrNode->name);
1278 return (TreeNodePtr) MemFree (ptrNode);
1279 }
1280
TreeNodeFreeBranch(TreeNodePtr ptrNode)1281 extern TreeNodePtr TreeNodeFreeBranch (TreeNodePtr ptrNode)
1282 {
1283 if (ptrNode == NULL)
1284 return ptrNode;
1285
1286 TreeNodeFreeBranch (ptrNode->ptrChildLeft);
1287 TreeNodeFreeBranch (ptrNode->ptrChildRight);
1288
1289 return TreeNodeFree (ptrNode);
1290 }
1291
TreeNodeFreeTree(TreeNodePtr ptrNode)1292 extern TreeNodePtr TreeNodeFreeTree (TreeNodePtr ptrNode)
1293 {
1294 if (ptrNode == NULL)
1295 return ptrNode;
1296
1297 return TreeNodeFreeBranch (HeadNode (ptrNode));
1298 }
1299