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