2 ** License Applicability. Except to the extent portions of this file are
3 ** made subject to an alternative license as permitted in the SGI Free
4 ** Software License B, Version 1.1 (the "License"), the contents of this
5 ** file are subject only to the provisions of the License. You may not use
6 ** this file except in compliance with the License. You may obtain a copy
7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10 ** http://oss.sgi.com/projects/FreeB
12 ** Note that, as provided in the License, the Software is distributed on an
13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21 ** Copyright in any portions created by third parties is as indicated
22 ** elsewhere herein. All Rights Reserved.
24 ** Additional Notice Provisions: The application programming interfaces
25 ** established by SGI in conjunction with the Original Code are The
26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31 ** published by SGI, but has not been independently verified as being
32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
34 ** $Date$ $Revision: 1.1 $
37 ** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libnurbs/nurbtess/partitionY.cc,v 1.1 2004/02/02 16:39:13 navaraf Exp $
45 #include "partitionY.h"
46 #include "searchTree.h"
47 #include "quicksort.h"
51 #define max(a,b) ((a>b)? a:b)
52 #define min(a,b) ((a>b)? b:a)
56 *-1: if A < B (Ya<Yb) || (Ya==Yb)
60 static Int
compVertInY(Real A
[2], Real B
[2])
62 if( (A
[1] < B
[1]) || (A
[1]==B
[1] && A
[0]<B
[0]))
65 ( A
[1] == B
[1] && A
[0] == B
[0]) return 0;
70 /*v is a vertex: the head of en edge,
72 *return 1 if e is below v: assume v1 and v2 are the two endpoints of e:
75 Int
isBelow(directedLine
*v
, directedLine
*e
)
77 Real
* vert
= v
->head();
78 if( compVertInY(e
->head(), vert
) != 1
79 && compVertInY(e
->tail(), vert
) != 1
86 /*v is a vertex: the head of en edge,
88 *return 1 if e is below v: assume v1 and v2 are the two endpoints of e:
91 Int
isAbove(directedLine
*v
, directedLine
*e
)
93 Real
* vert
= v
->head();
94 if( compVertInY(e
->head(), vert
) != -1
95 && compVertInY(e
->tail(), vert
) != -1
102 Int
isCusp(directedLine
*v
)
104 Real
*A
=v
->getPrev()->head();
107 if(A
[1] < B
[1] && B
[1] < C
[1])
109 else if(A
[1] > B
[1] && B
[1] > C
[1])
111 else if(A
[1] < B
[1] && C
[1] < B
[1])
113 else if(A
[1] > B
[1] && C
[1] > B
[1])
116 if(isAbove(v
, v
) && isAbove(v
, v
->getPrev()) ||
117 isBelow(v
, v
) && isBelow(v
, v
->getPrev()))
123 /*crossproduct is strictly less than 0*/
124 Int
isReflex(directedLine
*v
)
126 Real
* A
= v
->getPrev()->head();
135 if(Bx
*Cy
- Cx
*By
< 0) return 1;
144 Int
cuspType(directedLine
*v
)
146 if(! isCusp(v
)) return 0;
147 else if(isReflex(v
)) return 1;
152 sweepRange
* sweepRangeMake(directedLine
* left
, Int leftType
,
153 directedLine
* right
, Int rightType
)
155 sweepRange
* ret
= (sweepRange
*)malloc(sizeof(sweepRange
));
158 ret
->leftType
= leftType
;
160 ret
->rightType
= rightType
;
164 void sweepRangeDelete(sweepRange
* range
)
169 Int
sweepRangeEqual(sweepRange
* src1
, sweepRange
* src2
)
175 /*The case when both are vertices should not happen*/
176 assert(! (src1
->leftType
== 0 && src2
->leftType
== 0));
177 if(src1
->leftType
== 0 && src2
->leftType
== 1){
178 if(src1
->left
== src2
->left
||
179 src1
->left
->getPrev() == src2
->left
185 else if(src1
->leftType
== 1 && src2
->leftType
== 1){
186 if(src1
->left
== src2
->left
)
191 else /*src1->leftType == 1 && src2->leftType == 0*/{
192 if(src1
->left
== src2
->left
||
193 src1
->left
== src2
->left
->getPrev()
200 /*the same thing for right*/
201 /*The case when both are vertices should not happen*/
202 assert(! (src1
->rightType
== 0 && src2
->rightType
== 0));
203 if(src1
->rightType
== 0 && src2
->rightType
== 1){
204 if(src1
->right
== src2
->right
||
205 src1
->right
->getPrev() == src2
->right
211 else if(src1
->rightType
== 1 && src2
->rightType
== 1){
212 if(src1
->right
== src2
->right
)
217 else /*src1->rightType == 1 && src2->rightType == 0*/{
218 if(src1
->right
== src2
->right
||
219 src1
->right
== src2
->right
->getPrev()
226 return (leftEqual
== 1 || rightEqual
== 1);
229 /*given (x_1, y_1) and (x_2, y_2), and y
230 *return x such that (x,y) is on the line
232 inline/*static*/ Real
intersectHoriz(Real x1
, Real y1
, Real x2
, Real y2
, Real y
)
234 return ((y2
==y1
)? (x1
+x2
)*Real(0.5) : x1
+ ((y
-y1
)/(y2
-y1
)) * (x2
-x1
));
236 if(y2 == y1) return (x1+x2)*0.5;
237 else return x1 + ((y-y1)/(y2-y1)) * (x2-x1);
241 /*compare two edges of a polygon.
242 *edge A < edge B if there is a horizontal line so that the intersection
243 *with A is to the left of the intersection with B.
244 *This function is used in sweepY for the dynamic search tree insertion to
246 * Implementation: (x_1,y_1) and (x_2, y_2)
248 static Int
compEdges(directedLine
*e1
, directedLine
*e2
)
250 Real
* head1
= e1
->head();
251 Real
* tail1
= e1
->tail();
252 Real
* head2
= e2
->head();
253 Real
* tail2
= e2
->tail();
264 Real e1_Ymax
, e1_Ymin
, e2_Ymax
, e2_Ymin
;
285 if(head1
[1]>tail1
[1]) {
294 if(head2
[1]>tail2
[1]) {
304 /*Real e1_Ymax = max(head1[1], tail1[1]);*/ /*max(e1->head()[1], e1->tail()[1]);*/
305 /*Real e1_Ymin = min(head1[1], tail1[1]);*/ /*min(e1->head()[1], e1->tail()[1]);*/
306 /*Real e2_Ymax = max(head2[1], tail2[1]);*/ /*max(e2->head()[1], e2->tail()[1]);*/
307 /*Real e2_Ymin = min(head2[1], tail2[1]);*/ /*min(e2->head()[1], e2->tail()[1]);*/
309 Real Ymax
= min(e1_Ymax
, e2_Ymax
);
310 Real Ymin
= max(e1_Ymin
, e2_Ymin
);
312 Real y
= Real(0.5)*(Ymax
+ Ymin
);
314 /* Real x1 = intersectHoriz(e1->head()[0], e1->head()[1], e1->tail()[0], e1->tail()[1], y);
315 Real x2 = intersectHoriz(e2->head()[0], e2->head()[1], e2->tail()[0], e2->tail()[1], y);
318 Real x1 = intersectHoriz(h10, h11, t10, t11, y);
319 Real x2 = intersectHoriz(h20, h21, t20, t21, y);
321 Real x1
= intersectHoriz(head1
[0], head1
[1], tail1
[0], tail1
[1], y
);
322 Real x2
= intersectHoriz(head2
[0], head2
[1], tail2
[0], tail2
[1], y
);
324 if(x1
<= x2
) return -1;
328 /*used by sort precedures
330 static Int
compInY(directedLine
* v1
, directedLine
* v2
)
332 return v1
->compInY(v2
);
335 void findDiagonals(Int total_num_edges
, directedLine
** sortedVertices
, sweepRange
** ranges
, Int
& num_diagonals
, directedLine
** diagonal_vertices
)
341 for(i
=0; i
<total_num_edges
; i
++)
343 directedLine
* vert
=sortedVertices
[i
];
344 directedLine
* thisEdge
= vert
;
345 directedLine
* prevEdge
= vert
->getPrev();
347 printf("find i=%i\n", i);
348 printf("the vertex is\n");
351 if(isBelow(vert
, thisEdge
) && isBelow(vert
, prevEdge
) && compEdges(prevEdge
, thisEdge
)<0)
353 /*this is an upward interior cusp*/
354 diagonal_vertices
[k
++] = vert
;
356 for(j
=i
+1; j
<total_num_edges
; j
++)
357 if(sweepRangeEqual(ranges
[i
], ranges
[j
]))
359 diagonal_vertices
[k
++] = sortedVertices
[j
];
362 assert(j
<total_num_edges
);
366 else if(isAbove(vert
, thisEdge
) && isAbove(vert
, prevEdge
) && compEdges(prevEdge
, thisEdge
)>0)
368 /*this is an downward interior cusp*/
369 diagonal_vertices
[k
++] = vert
;
370 for(j
=i
-1; j
>=0; j
--)
371 if(sweepRangeEqual(ranges
[i
], ranges
[j
]))
373 diagonal_vertices
[k
++] = sortedVertices
[j
];
376 /* printf("j=%i\n", j);*/
386 /*get rid of repeated diagonlas so that each diagonal appears only once in the array
388 Int
deleteRepeatDiagonals(Int num_diagonals
, directedLine
** diagonal_vertices
, directedLine
** new_vertices
)
394 for(i
=0,k
=0; i
<num_diagonals
; i
++, k
+=2)
397 /*check the diagonla (diagonal_vertice[k], diagonal_vertices[k+1])
400 for(j
=0,l
=0; j
<index
; j
++, l
+=2)
403 (diagonal_vertices
[k
] == new_vertices
[l
] &&
404 diagonal_vertices
[k
+1] == new_vertices
[l
+1]
408 diagonal_vertices
[k
] == new_vertices
[l
+1] &&
409 diagonal_vertices
[k
+1] == new_vertices
[l
]
419 new_vertices
[index
+index
] = diagonal_vertices
[k
];
420 new_vertices
[index
+index
+1] = diagonal_vertices
[k
+1];
428 directedLine
** DBGfindDiagonals(directedLine
*polygons
, Int
& num_diagonals
)
430 Int total_num_edges
= 0;
431 directedLine
** array
= polygons
->toArrayAllPolygons(total_num_edges
);
432 quicksort( (void**)array
, 0, total_num_edges
-1, (Int (*)(void*, void*)) compInY
);
433 sweepRange
** ranges
= (sweepRange
**) malloc(sizeof(sweepRange
*) * total_num_edges
);
436 sweepY(total_num_edges
, array
, ranges
);
438 directedLine
** diagonal_vertices
= (directedLine
**) malloc(sizeof(directedLine
*) * total_num_edges
);
439 assert(diagonal_vertices
);
440 findDiagonals(total_num_edges
, array
, ranges
, num_diagonals
, diagonal_vertices
);
442 num_diagonals
=deleteRepeatDiagonals(num_diagonals
, diagonal_vertices
, diagonal_vertices
);
443 return diagonal_vertices
;
448 /*partition into Y-monotone polygons*/
449 directedLine
* partitionY(directedLine
*polygons
, sampledLine
**retSampledLines
)
451 Int total_num_edges
= 0;
452 directedLine
** array
= polygons
->toArrayAllPolygons(total_num_edges
);
454 quicksort( (void**)array
, 0, total_num_edges
-1, (Int (*)(void*, void*)) compInY
);
456 sweepRange
** ranges
= (sweepRange
**) malloc(sizeof(sweepRange
*) * (total_num_edges
));
461 sweepY(total_num_edges
, array
, ranges
);
465 /*the diagonal vertices are stored as:
474 /*number diagonals is < total_num_edges*total_num_edges*/
475 directedLine
** diagonal_vertices
= (directedLine
**) malloc(sizeof(directedLine
*) * total_num_edges
*2/*total_num_edges*/);
476 assert(diagonal_vertices
);
480 findDiagonals(total_num_edges
, array
, ranges
, num_diagonals
, diagonal_vertices
);
484 directedLine
* ret_polygons
= polygons
;
485 sampledLine
* newSampledLines
= NULL
;
488 num_diagonals
=deleteRepeatDiagonals(num_diagonals
, diagonal_vertices
, diagonal_vertices
);
492 Int
*removedDiagonals
=(Int
*)malloc(sizeof(Int
) * num_diagonals
);
493 for(i
=0; i
<num_diagonals
; i
++)
494 removedDiagonals
[i
] = 0;
500 for(i
=0,k
=0; i
<num_diagonals
; i
++,k
+=2)
504 directedLine
* v1
=diagonal_vertices
[k
];
505 directedLine
* v2
=diagonal_vertices
[k
+1];
506 directedLine
* ret_p1
;
507 directedLine
* ret_p2
;
509 /*we ahve to determine whether v1 and v2 belong to the same polygon before
510 *their structure are modified by connectDiagonal().
513 directedLine *root1 = v1->findRoot();
514 directedLine *root2 = v2->findRoot();
519 directedLine
* root1
= v1
->rootLinkFindRoot();
520 directedLine
* root2
= v2
->rootLinkFindRoot();
525 removedDiagonals
[i
] = 1;
526 sampledLine
* generatedLine
;
530 v1
->connectDiagonal(v1
,v2
, &ret_p1
, &ret_p2
, &generatedLine
, ret_polygons
);
534 newSampledLines
= generatedLine
->insert(newSampledLines
);
536 ret_polygons = ret_polygons->cutoffPolygon(root1);
538 ret_polygons = ret_polygons->cutoffPolygon(root2);
539 ret_polygons = ret_p1->insertPolygon(ret_polygons);
540 root1->rootLinkSet(ret_p1);
541 root2->rootLinkSet(ret_p1);
542 ret_p1->rootLinkSet(NULL);
543 ret_p2->rootLinkSet(ret_p1);
545 ret_polygons
= ret_polygons
->cutoffPolygon(root2
);
549 root2
->rootLinkSet(root1
);
550 ret_p1
->rootLinkSet(root1
);
551 ret_p2
->rootLinkSet(root1
);
553 /*now that we have connected the diagonal v1 and v2,
554 *we have to check those unprocessed diagonals which
555 *have v1 or v2 as an end point. Notice that the head of v1
556 *has the same coodinates as the head of v2->prev, and the head of
557 *v2 has the same coordinate as the head of v1->prev.
558 *Suppose these is a diagonal (v1, x). If (v1,x) is still a valid
559 *diagonal, then x should be on the left hand side of the directed line: *v1->prev->head -- v1->head -- v1->tail. Otherwise, (v1,x) should be
560 *replaced by (v2->prev, x), that is, x is on the left of
561 * v2->prev->prev->head, v2->prev->head, v2->prev->tail.
564 for(ii
=0, kk
=0; ii
<num_diagonals
; ii
++, kk
+=2)
565 if( removedDiagonals
[ii
]==0)
567 directedLine
* d1
=diagonal_vertices
[kk
];
568 directedLine
* d2
=diagonal_vertices
[kk
+1];
569 /*check d1, and replace diagonal_vertices[kk] if necessary*/
571 /*check if d2 is to left of v1->prev->head:v1->head:v1->tail*/
572 if(! pointLeft2Lines(v1
->getPrev()->head(),
573 v1
->head(), v1
->tail(), d2
->head()))
576 assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
577 v2->getPrev()->head(),
578 v2->getPrev()->tail(), d2->head()));
580 diagonal_vertices
[kk
] = v2
->getPrev();
584 /*check if d2 is to left of v2->prev->head:v2->head:v2->tail*/
585 if(! pointLeft2Lines(v2
->getPrev()->head(),
586 v2
->head(), v2
->tail(), d2
->head()))
589 assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
590 v1->getPrev()->head(),
591 v1->getPrev()->tail(), d2->head()));
593 diagonal_vertices
[kk
] = v1
->getPrev();
596 /*check d2 and replace diagonal_vertices[k+1] if necessary*/
598 /*check if d1 is to left of v1->prev->head:v1->head:v1->tail*/
599 if(! pointLeft2Lines(v1
->getPrev()->head(),
600 v1
->head(), v1
->tail(), d1
->head()))
602 /* assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
603 v2->getPrev()->head(),
604 v2->getPrev()->tail(), d1->head()));
606 diagonal_vertices
[kk
+1] = v2
->getPrev();
610 /*check if d1 is to left of v2->prev->head:v2->head:v2->tail*/
611 if(! pointLeft2Lines(v2
->getPrev()->head(),
612 v2
->head(), v2
->tail(), d1
->head()))
614 /* assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
615 v1->getPrev()->head(),
616 v1->getPrev()->tail(), d1->head()));
618 diagonal_vertices
[kk
+1] = v1
->getPrev();
622 }/*end if (root1 not equal to root 2)*/
625 /*second pass, now all diagoals should belong to the same polygon*/
629 for(i
=0,k
=0; i
<num_diagonals
; i
++, k
+= 2)
630 if(removedDiagonals
[i
] == 0)
634 directedLine
* v1
=diagonal_vertices
[k
];
635 directedLine
* v2
=diagonal_vertices
[k
+1];
639 directedLine
* ret_p1
;
640 directedLine
* ret_p2
;
642 /*we ahve to determine whether v1 and v2 belong to the same polygon before
643 *their structure are modified by connectDiagonal().
645 directedLine
*root1
= v1
->findRoot();
647 directedLine *root2 = v2->findRoot();
653 assert(root1 == root2);
655 sampledLine
* generatedLine
;
659 v1
->connectDiagonal(v1
,v2
, &ret_p1
, &ret_p2
, &generatedLine
, ret_polygons
);
660 newSampledLines
= generatedLine
->insert(newSampledLines
);
662 ret_polygons
= ret_polygons
->cutoffPolygon(root1
);
664 ret_polygons
= ret_p1
->insertPolygon(ret_polygons
);
666 ret_polygons
= ret_p2
->insertPolygon(ret_polygons
);
670 for(Int j
=i
+1; j
<num_diagonals
; j
++)
672 if(removedDiagonals
[j
] ==0)
675 directedLine
* temp1
=diagonal_vertices
[2*j
];
676 directedLine
* temp2
=diagonal_vertices
[2*j
+1];
677 if(temp1
==v1
|| temp1
==v2
|| temp2
==v1
|| temp2
==v2
)
678 if(! temp1
->samePolygon(temp1
, temp2
))
680 /*if temp1 and temp2 are in different polygons,
681 *then one of them must be v1 or v2.
686 assert(temp1
==v1
|| temp1
== v2
|| temp2
==v1
|| temp2
==v2
);
689 diagonal_vertices
[2*j
] = v2
->getPrev();
693 diagonal_vertices
[2*j
+1] = v2
->getPrev();
697 diagonal_vertices
[2*j
] = v1
->getPrev();
701 diagonal_vertices
[2*j
+1] = v1
->getPrev();
712 free(diagonal_vertices
);
713 free(removedDiagonals
);
715 *retSampledLines
= newSampledLines
;
719 /*given a set of simple polygons where the interior
720 *is decided by left-hand principle,
721 *return a range (sight) for each vertex. This is called
724 void sweepY(Int nVertices
, directedLine
** sortedVertices
, sweepRange
** ret_ranges
)
727 /*for each vertex in the sorted list, update the binary search tree.
728 *and store the range information for each vertex.
730 treeNode
* searchTree
= NULL
;
731 for(i
=0; i
<nVertices
;i
++)
734 directedLine
* vert
= sortedVertices
[i
];
736 directedLine
* thisEdge
= vert
;
737 directedLine
* prevEdge
= vert
->getPrev();
739 if(isBelow(vert
, thisEdge
) && isAbove(vert
, prevEdge
))
742 /*case 1: this < v < prev
743 *the polygon is going down at v, the interior is to
744 *the right hand side.
745 * find the edge to the right of thisEdge for right range.
749 treeNode
* thisNode
= TreeNodeFind(searchTree
, thisEdge
, ( Int (*) (void *, void *))compEdges
);
752 treeNode
* succ
= TreeNodeSuccessor(thisNode
);
754 searchTree
= TreeNodeDeleteSingleNode(searchTree
, thisNode
);
755 searchTree
= TreeNodeInsert(searchTree
, TreeNodeMake(prevEdge
), ( Int (*) (void *, void *))compEdges
);
758 ret_ranges
[i
] = sweepRangeMake(vert
, 0, (directedLine
*) (succ
->key
), 1);
761 else if(isAbove(vert
, thisEdge
) && isBelow(vert
, prevEdge
))
764 /*case 2: this > v > prev
765 *the polygon is going up at v, the interior is to
767 * find the edge to the left of thisEdge for left range.
771 treeNode
* prevNode
= TreeNodeFind(searchTree
, prevEdge
, ( Int (*) (void *, void *))compEdges
);
773 treeNode
* pred
= TreeNodePredecessor(prevNode
);
774 searchTree
= TreeNodeDeleteSingleNode(searchTree
, prevNode
);
775 searchTree
= TreeNodeInsert(searchTree
, TreeNodeMake(thisEdge
), ( Int (*) (void *, void *))compEdges
);
776 ret_ranges
[i
] = sweepRangeMake((directedLine
*)(pred
->key
), 1, vert
, 0);
778 else if(isAbove(vert
, thisEdge
) && isAbove(vert
, prevEdge
))
781 /*case 3: insert both edges*/
782 treeNode
* thisNode
= TreeNodeMake(thisEdge
);
783 treeNode
* prevNode
= TreeNodeMake(prevEdge
);
784 searchTree
= TreeNodeInsert(searchTree
, thisNode
, ( Int (*) (void *, void *))compEdges
);
785 searchTree
= TreeNodeInsert(searchTree
, prevNode
, ( Int (*) (void *, void *))compEdges
);
786 if(compEdges(thisEdge
, prevEdge
)<0) /*interior cusp*/
789 treeNode
* leftEdge
= TreeNodePredecessor(thisNode
);
790 treeNode
* rightEdge
= TreeNodeSuccessor(prevNode
);
791 ret_ranges
[i
] = sweepRangeMake( (directedLine
*) leftEdge
->key
, 1,
792 (directedLine
*) rightEdge
->key
, 1
795 else /*exterior cusp*/
798 ret_ranges
[i
] = sweepRangeMake( prevEdge
, 1, thisEdge
, 1);
801 else if(isBelow(vert
, thisEdge
) && isBelow(vert
, prevEdge
))
804 /*case 4: delete both edges*/
805 treeNode
* thisNode
= TreeNodeFind(searchTree
, thisEdge
, ( Int (*) (void *, void *))compEdges
);
806 treeNode
* prevNode
= TreeNodeFind(searchTree
, prevEdge
, ( Int (*) (void *, void *))compEdges
);
807 if(compEdges(thisEdge
, prevEdge
)>0) /*interior cusp*/
809 treeNode
* leftEdge
= TreeNodePredecessor(prevNode
);
810 treeNode
* rightEdge
= TreeNodeSuccessor(thisNode
);
811 ret_ranges
[i
] = sweepRangeMake( (directedLine
*) leftEdge
->key
, 1,
812 (directedLine
*) rightEdge
->key
, 1
815 else /*exterior cusp*/
817 ret_ranges
[i
] = sweepRangeMake( thisEdge
, 1, prevEdge
, 1);
819 searchTree
= TreeNodeDeleteSingleNode(searchTree
, thisNode
);
820 searchTree
= TreeNodeDeleteSingleNode(searchTree
, prevNode
);
824 fprintf(stderr
,"error in partitionY.C, invalid case\n");
827 printf("thisEdge is\n");
828 thisEdge
->printSingle();
829 printf("prevEdge is\n");
830 prevEdge
->printSingle();
836 /*finaly clean up space: delete the search tree*/
837 TreeNodeDeleteWholeTree(searchTree
);