1 /*
2
3 HyPhy - Hypothesis Testing Using Phylogenies.
4
5 Copyright (C) 1997-now
6 Core Developers:
7 Sergei L Kosakovsky Pond (sergeilkp@icloud.com)
8 Art FY Poon (apoon42@uwo.ca)
9 Steven Weaver (sweaver@temple.edu)
10
11 Module Developers:
12 Lance Hepler (nlhepler@gmail.com)
13 Martin Smith (martin.audacis@gmail.com)
14
15 Significant contributions from:
16 Spencer V Muse (muse@stat.ncsu.edu)
17 Simon DW Frost (sdf22@cam.ac.uk)
18
19 Permission is hereby granted, free of charge, to any person obtaining a
20 copy of this software and associated documentation files (the
21 "Software"), to deal in the Software without restriction, including
22 without limitation the rights to use, copy, modify, merge, publish,
23 distribute, sublicense, and/or sell copies of the Software, and to
24 permit persons to whom the Software is furnished to do so, subject to
25 the following conditions:
26
27 The above copyright notice and this permission notice shall be included
28 in all copies or substantial portions of the Software.
29
30 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
31 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
33 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
34 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
35 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
36 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37
38 */
39
40
41 #include <string.h>
42 #include <stdio.h>
43 #include <ctype.h>
44 #include <math.h>
45 #include <limits.h>
46
47 #include "avllist.h"
48 #include "hy_strings.h"
49 #include "hy_string_buffer.h"
50 #include "parser.h"
51
52 #include "global_things.h"
53
54 using namespace hy_global;
55
56
57 //______________________________________________________________
58 // AVL Lists
59 //______________________________________________________________
60
_AVLList(_SimpleList * d)61 _AVLList::_AVLList (_SimpleList* d) {
62 dataList = d;
63 root = -1;
64 }
65
_AVLList(_AVLList const &)66 _AVLList::_AVLList (_AVLList const &) {
67 HandleApplicationError("Called _AVLList:: copy constructor method stub that is not implemented");
68 }
69
70 //______________________________________________________________
71
makeDynamic(void) const72 BaseRef _AVLList::makeDynamic (void) const {
73 HandleApplicationError("Called _AVLList::makeDynamic: method stub that is not implemented");
74 return nil;
75 }
76
77 //______________________________________________________________
78
Duplicate(BaseRefConst)79 void _AVLList::Duplicate (BaseRefConst) {
80 HandleApplicationError("Called _AVLList::Duplicate: method stub that is not implemented");
81 }
82
83 //______________________________________________________________
84
operator =(_AVLList const & rhs)85 void _AVLList::operator = (_AVLList const & rhs) {
86 HandleApplicationError("Called _AVLList::operator = : method stub that is not implemented");
87 }
88
89 //______________________________________________________________
90
Find(BaseRefConst obj) const91 long _AVLList::Find (BaseRefConst obj) const {
92 long curNode = root;
93
94 while (curNode>=0) {
95 long comp = dataList->Compare (obj,curNode);
96
97 if (comp<0) {
98 curNode = leftChild.list_data[curNode];
99 } else if (comp>0) {
100 curNode = rightChild.list_data[curNode];
101 } else {
102 return curNode;
103 }
104 }
105
106 return kNotFound;
107 }
108
109 //______________________________________________________________
110
FindLong(long obj) const111 long _AVLList::FindLong (long obj) const {
112 long curNode = root;
113
114 while (curNode>=0) {
115 long comp = dataList->list_data[curNode];
116
117 if (obj<comp) {
118 curNode = leftChild.list_data[curNode];
119 } else if (obj>comp) {
120 curNode = rightChild.list_data[curNode];
121 } else {
122 return curNode;
123 }
124 }
125
126 return kNotFound;
127 }
128
129 //______________________________________________________________
130
FindBest(BaseRefConst obj,long & lastNode) const131 char _AVLList::FindBest (BaseRefConst obj, long& lastNode) const {
132 long curNode = root,
133 comp = 1;
134
135 while (curNode>=0 && comp) {
136 comp = dataList->Compare (obj,curNode);
137 lastNode = curNode;
138
139 if (comp<0) {
140 curNode = leftChild.list_data[curNode];
141 } else if (comp>0) {
142 curNode = rightChild.list_data[curNode];
143 } else {
144 return 0;
145 }
146 }
147
148 return comp;
149 }
150
151 //______________________________________________________________
152
Find(BaseRefConst obj,_SimpleList & hist) const153 long _AVLList::Find (BaseRefConst obj, _SimpleList& hist) const {
154 long curNode = root;
155
156 while (curNode>=0) {
157 long comp = dataList->Compare (obj,curNode);
158
159 if (comp<0) {
160 hist << curNode;
161 curNode = leftChild.list_data[curNode];
162 } else if (comp>0) {
163 hist << curNode;
164 curNode = rightChild.list_data[curNode];
165 } else {
166 return curNode;
167 }
168 }
169
170 return -1;
171 }
172
173 //______________________________________________________________
174
Next(long d,_SimpleList & hist) const175 long _AVLList::Next (long d, _SimpleList& hist) const {
176 if (d >= 0) {
177 if (rightChild.list_data [d] >= 0) {
178 hist << d;
179 d = rightChild.list_data [d];
180 while (leftChild.list_data[d] >= 0) {
181 hist << d;
182 d = leftChild.list_data[d];
183 }
184 return d;
185 } else {
186 while (hist.countitems()) {
187 long x = hist.Pop();
188
189 if (rightChild.list_data[x] != d) {
190 return x;
191 }
192 //TODO:???
193 d = x;
194 }
195
196 return -1;
197 }
198 }
199
200 d = root;
201 while (d >= 0 && leftChild.list_data[d] >=0) {
202 hist << d;
203 d = leftChild.list_data[d];
204 }
205
206 return d;
207 }
208
209 //______________________________________________________________
210
First(void) const211 long _AVLList::First (void) const {
212 long d = root;
213 while (d >= 0 && leftChild.list_data[d] >=0) {
214 d = leftChild.list_data[d];
215 }
216
217 return d;
218 }
219
220 //______________________________________________________________
221
Last(void) const222 long _AVLList::Last (void) const {
223 long d = root;
224 while (d >= 0 && rightChild.list_data[d] >=0) {
225 d = rightChild.list_data[d];
226 }
227
228 return d;
229 }
230
231 //______________________________________________________________
232
Prev(long d,_SimpleList & hist) const233 long _AVLList::Prev (long d, _SimpleList& hist) const {
234 if (d >= 0) {
235 if (leftChild.list_data [d] >= 0) {
236 hist << d;
237 d = leftChild.list_data [d];
238 while (rightChild.list_data[d] >= 0) {
239 hist << d;
240 d = rightChild.list_data[d];
241 }
242 return d;
243 } else {
244 while (hist.countitems()) {
245 long x = hist.list_data[hist.lLength-1];
246
247 hist.Delete (hist.lLength-1);
248
249 if (leftChild.list_data[x] != d) {
250 return x;
251 }
252 //TODO:???
253 d = x;
254 }
255
256 return -1;
257 }
258 }
259
260 d = root;
261 while (d >= 0 && rightChild.list_data[d] >=0) {
262 hist << d;
263 d = rightChild.list_data[d];
264 }
265
266 return d;
267
268 }
269
270
271 //______________________________________________________________
272
IsValidIndex(long index) const273 bool _AVLList::IsValidIndex(long index) const {
274 if (index >= 0 && index < dataList->lLength) {
275 return Retrieve(index);
276 }
277 return false;
278 }
279
280 //______________________________________________________________
281
GetByIndex(const long theIndex)282 long _AVLList::GetByIndex (const long theIndex) {
283 if (theIndex == 0) {
284 return First();
285 }
286
287 long elementCount = countitems();
288
289 if (theIndex == elementCount - 1) {
290 return Last();
291 }
292
293 if (theIndex > 0 && theIndex < elementCount) {
294 _SimpleList hist;
295 long ls,
296 cn = Traverser (hist,ls,GetRoot()),
297 counter = 0;
298
299 while (counter < theIndex) {
300 counter ++;
301 cn = Traverser (hist,ls);
302 }
303
304 return cn;
305
306 }
307
308 return -1;
309 }
310
311 //______________________________________________________________
312
ReorderList(_SimpleList * s)313 void _AVLList::ReorderList (_SimpleList *s) {
314
315 unsigned long item_count = (dataList->lLength-emptySlots.lLength+1);
316
317 _SimpleList reorderMe (item_count),
318 nodeStack (64UL, (long*)alloca (64*sizeof (unsigned long)));
319
320 long curNode = root;
321
322 while (1) {
323 while (curNode >= 0) {
324 nodeStack << curNode;
325 curNode = leftChild.list_data[curNode];
326 }
327 if (long h = nodeStack.lLength) {
328 h--;
329 curNode = nodeStack.list_data[h];
330 if (s) {
331 (*s) << curNode;
332 }
333
334 reorderMe.InsertElement (((BaseRef*)dataList->list_data)[curNode],-1,false,false);
335 curNode = rightChild.list_data[curNode];
336 nodeStack.Delete (h, false);
337
338 } else {
339 break;
340 }
341 }
342
343 reorderMe.TrimMemory ();
344 *dataList = reorderMe;
345 }
346
347 //______________________________________________________________
348
ConsistencyCheck(void)349 void _AVLList::ConsistencyCheck (void)
350 {
351 _SimpleList nodeStack ((unsigned long)32);
352
353 long curNode = root,
354 lastNode = -1,
355 checkCount = 0;
356
357 while (1) {
358 while (curNode >= 0) {
359 nodeStack << curNode;
360 curNode = leftChild.list_data[curNode];
361 if (curNode >= (long)dataList->lLength) {
362 hy_global::HandleApplicationError ("Failed Constistency Check in _AVLList");
363 return;
364 }
365
366 }
367 if (long h = nodeStack.lLength) {
368 if (h>3*log (1.+countitems())) {
369 hy_global::HandleApplicationError ("Failed Constistency Check in _AVLList");
370 return;
371 }
372 h--;
373 curNode = nodeStack.list_data[h];
374 if (lastNode >= 0 && curNode >= 0) {
375 if (dataList->Compare (Retrieve (lastNode), curNode) >= 0) {
376 hy_global::HandleApplicationError ("Failed Constistency Check in _AVLList");
377 return;
378 }
379 checkCount++;
380 }
381 if ((balanceFactor.list_data[curNode] < -1)||(balanceFactor.list_data[curNode] > 1)) {
382 hy_global::HandleApplicationError ("Failed Constistency Check in _AVLList");
383 return;
384 }
385 lastNode = curNode;
386 curNode = rightChild.list_data[curNode];
387 if (curNode >= (long)dataList->lLength) {
388 hy_global::HandleApplicationError ("Failed Constistency Check in _AVLList");
389 return;
390 }
391 nodeStack.Delete (h, false);
392 } else {
393 break;
394 }
395 }
396
397 if (dataList->lLength && (dataList->lLength > checkCount + 1 + emptySlots.lLength)) {
398 hy_global::HandleApplicationError ("Failed Constistency Check in _AVLList");
399 return;
400 }
401
402 }
403
404 //______________________________________________________________
405
Traverser(_SimpleList & nodeStack,long & t,long r) const406 long _AVLList::Traverser (_SimpleList &nodeStack, long& t, long r) const {
407 if (r >= 0) {
408 t = r;
409 nodeStack.Clear(false);
410 }
411
412 while (t >= 0) {
413 nodeStack << t;
414 t = leftChild.list_data[t];
415 }
416
417 if (long h = nodeStack.lLength) {
418 h--;
419 t = nodeStack.list_data[h];
420 r = t;
421 t = rightChild.list_data[t];
422 nodeStack.Delete (h, false);
423 return r;
424 }
425 return -1;
426 }
427
428 //______________________________________________________________
429
toStr(unsigned long)430 BaseRef _AVLList::toStr (unsigned long) {
431 _StringBuffer * str = new _StringBuffer (128L);
432
433 if (countitems() == 0) {
434 (*str) << "()";
435 } else {
436 _SimpleList hist;
437 long ls, cn;
438
439 cn = Traverser (hist,ls,root);
440
441 bool first = true;
442
443 (*str) << '(';
444
445 while (cn>=0) {
446 if (first) {
447 first = false;
448 } else {
449 (*str) << ", ";
450 }
451 (*str) << _String((long)Retrieve (cn));
452 cn = Traverser (hist,ls);
453 }
454
455 (*str) << ')';
456 }
457
458 return str;
459 }
460
461 //______________________________________________________________
462
Keys(void) const463 const _List _AVLList::Keys (void) const {
464 _List keys;
465 if (countitems() > 0UL) {
466 _SimpleList hist;
467 long ls = -1L, cn;
468
469 cn = Traverser (hist,ls,root);
470
471 while (cn>=0) {
472 keys << Retrieve (cn);
473 cn = Traverser (hist,ls);
474 }
475 }
476 return keys;
477 }
478
479
480 //______________________________________________________________
481
Retrieve(long idx) const482 BaseRef _AVLList::Retrieve (long idx) const {
483 return ((BaseRef*)dataList->list_data)[idx];
484 }
485
486 //______________________________________________________________
487
RetrieveLong(long idx) const488 long _AVLList::RetrieveLong(long idx) const {
489 return ((long*)dataList->list_data)[idx];
490 }
491
492 //______________________________________________________________
493
Clear(bool cL)494 void _AVLList::Clear (bool cL)
495 {
496 if (cL) {
497 ((_List*)dataList)->Clear();
498 } else {
499 dataList->Clear();
500 }
501
502 emptySlots.Clear();
503 root = -1;
504 leftChild.Clear();
505 rightChild.Clear();
506 balanceFactor.Clear();
507 }
508
509 //______________________________________________________________
510
InsertData(BaseRef b,long,bool)511 long _AVLList::InsertData (BaseRef b, long, bool)
512 {
513 long w = (long)emptySlots.lLength - 1,
514 n;
515
516 if (w>=0) {
517 n = emptySlots.list_data[w];
518 emptySlots.Delete (w);
519 leftChild.list_data[n] = -1;
520 rightChild.list_data[n] = -1;
521 balanceFactor.list_data[n] = 0;
522 ((BaseRef*)dataList->list_data)[n] = b;
523 } else {
524 n = dataList->lLength;
525 dataList->InsertElement (b,-1,false,false);
526 leftChild << -1;
527 rightChild << -1;
528 balanceFactor << 0;
529 }
530 return n;
531 }
532
533 //______________________________________________________________
534
countitems(void) const535 unsigned long _AVLList::countitems (void) const {
536 return dataList->lLength - emptySlots.lLength;
537 }
538
539 //______________________________________________________________
540
Insert(BaseRef b,long xtra,bool cp,bool clear)541 long _AVLList::Insert (BaseRef b, long xtra,bool cp,bool clear) {
542 /**
543 Insert a key (and possibly a value) into this _AVLList
544
545 @param b the key to insert; this operation will NOT increase reference counts for b
546 @param xtra the payload
547 @param cp if true, the insertion operation will add a reference count to payload
548 @param clear if insertion fails (key already exists), then the _key_ will be deleted
549
550 */
551 if (dataList->lLength-emptySlots.lLength) {
552 long y = root,
553 z = -1,
554 p,
555 q,
556 n,
557 w;
558
559 bool go_right = false;
560
561 //_SimpleList da ((unsigned long)32);
562
563 long traversal_stack [32] = {0L};
564 unsigned long stack_pointer = 0UL;
565
566 // try to find the node or where to insert it
567
568 for (q=z, p=y; p>=0; q=p, p=go_right?rightChild.list_data[p]:leftChild.list_data[p]) {
569 long comp = dataList->Compare (b, p);
570 if (comp == 0) {
571 if (cp == false && clear) {
572 DeleteObject (b);
573 }
574 // already exists, return the node it mapped to
575 return -p-1;
576 }
577 if (balanceFactor.list_data[p] != 0) {
578 z = q;
579 y = p;
580 //da.Clear();
581 stack_pointer = 0UL;
582 }
583 go_right = comp > 0;
584 //da << go_right;
585 traversal_stack[stack_pointer++] = go_right;
586 if (stack_pointer >= 32UL) {
587 HandleApplicationError("Internal error: AVLList is too big");
588 }
589 }
590
591 /*if (da.lLength > 3*log (dataList->lLength+2))
592 {
593 WarnError ("AVLList internal error!");
594 return -1;
595 }*/
596
597 // insert new node
598
599 n = InsertData (b, xtra,cp);
600
601 if (go_right) {
602 rightChild.list_data[q] = n;
603 } else {
604 leftChild.list_data[q] = n;
605 }
606
607
608 // update balance factors
609
610 p = y;
611
612 for (long k=0L; p!=n; p=traversal_stack[k]?rightChild.list_data[p]:leftChild.list_data[p],k++)
613 //if (da.list_data[k] == 0) {
614 if (traversal_stack[k] == 0) {
615 balanceFactor.list_data[p]--;
616 } else {
617 balanceFactor.list_data[p]++;
618 }
619
620
621 //if (z < 0)
622 //{
623 //ConsistencyCheck();
624 //return n;
625 //}
626
627 if (balanceFactor.list_data[y] == -2) {
628 //152
629
630 long x = leftChild.list_data[y];
631 if (balanceFactor.list_data[x] == -1) { //155
632 w = x;
633 leftChild.list_data [y] = rightChild.list_data[x];
634 rightChild.list_data[x] = y;
635 balanceFactor.list_data[x] = balanceFactor.list_data[y] = 0;
636 } else { //156
637 w = rightChild.list_data[x];
638 rightChild.list_data[x] = leftChild.list_data[w];
639 leftChild.list_data[w] = x;
640 leftChild.list_data[y] = rightChild.list_data[w];
641 rightChild.list_data[w] = y;
642 if (balanceFactor.list_data[w] == -1) {
643 balanceFactor.list_data[x] = 0;
644 balanceFactor.list_data[y] = 1;
645 } else if (balanceFactor.list_data[w] == 0) {
646 balanceFactor.list_data[x] = 0;
647 balanceFactor.list_data[y] = 0;
648 } else {
649 balanceFactor.list_data[x] = -1;
650 balanceFactor.list_data[y] = 0;
651 }
652
653 balanceFactor.list_data[w] = 0;
654 }
655 } else if (balanceFactor.list_data[y] == 2) {
656 long x = rightChild.list_data[y];
657 if (balanceFactor.list_data[x] == 1) {
658 w = x;
659 rightChild.list_data [y] = leftChild.list_data[x];
660 leftChild.list_data[x] = y;
661 balanceFactor.list_data[x] = balanceFactor.list_data[y] = 0;
662 } else {
663 w = leftChild.list_data[x];
664 leftChild.list_data[x] = rightChild.list_data[w];
665 rightChild.list_data[w] = x;
666 rightChild.list_data[y] = leftChild.list_data[w];
667 leftChild.list_data[w] = y;
668 if (balanceFactor.list_data[w] == 1) {
669 balanceFactor.list_data[x] = 0;
670 balanceFactor.list_data[y] = -1;
671 } else if (balanceFactor.list_data[w] == 0) {
672 balanceFactor.list_data[x] = 0;
673 balanceFactor.list_data[y] = 0;
674 } else {
675 balanceFactor.list_data[x] = 1;
676 balanceFactor.list_data[y] = 0;
677 }
678
679 balanceFactor.list_data[w] = 0;
680 }
681 } else {
682 //ConsistencyCheck ();
683 return n;
684 }
685
686 if (z >= 0) {
687 if (y == leftChild.list_data[z]) {
688 leftChild.list_data[z] = w;
689 } else {
690 rightChild.list_data[z] = w;
691 }
692 }
693
694 if (y==root) {
695 root = w;
696 }
697
698 //ConsistencyCheck ();
699
700 return p;
701 }
702
703 root =InsertData (b, xtra,cp);
704
705 return 0;
706
707 }
708
709 //______________________________________________________________
710
HasData(long idx)711 bool _AVLList::HasData (long idx) {
712 return leftChild.list_data[idx] != 2;
713 }
714
715 //______________________________________________________________
716
Delete(BaseRefConst b,bool delMe)717 void _AVLList::Delete (BaseRefConst b, bool delMe) {
718
719 if (root == -1) {
720 return;
721 }
722
723 _SimpleList pa ((unsigned long)64),
724 da ((unsigned long)64);
725
726 long p = root,
727 cmp = dataList->Compare (b,p),
728 k = 0;
729
730 pa.list_data[k] = -1;
731 da.list_data[k++] = 1;
732
733 for (; cmp !=0; cmp = dataList->Compare (b,p)) {
734 bool go_right = cmp > 0;
735
736 pa.list_data[k] = p;
737 da.list_data[k++] = go_right;
738
739 if (go_right) {
740 p = rightChild.list_data[p];
741 } else {
742 p = leftChild.list_data[p];
743 }
744
745 if (p<0) {
746 return;
747 }
748 }
749
750 if (k==1) {
751 pa.list_data[k] = -1;
752 }
753
754 emptySlots << p;
755 if (delMe) {
756 DeleteObject (Retrieve(p));
757 }
758 //((BaseRef*)dataList->list_data)[p] = nil;
759 dataList->list_data[p] = 0;
760 DeleteXtra (p);
761
762 long r = rightChild.list_data[p];
763
764 if (r < 0) {
765 if (k>1) {
766 if (da.list_data[k-1] == 1) {
767 rightChild.list_data[pa.list_data[k-1]] = leftChild.list_data[p];
768 } else {
769 leftChild.list_data[pa.list_data[k-1]] = leftChild.list_data[p];
770 }
771 }
772
773 if (p==root) {
774 //root = pa.list_data[k-1];
775 root = leftChild.list_data[root];
776 }
777 } else {
778 if (leftChild.list_data[r] < 0) {
779 leftChild.list_data[r] = leftChild.list_data[p];
780 balanceFactor.list_data[r] = balanceFactor.list_data[p];
781 if (k>1) {
782 if (da.list_data[k-1] == 1) {
783 rightChild.list_data[pa.list_data[k-1]] = r;
784 } else {
785 leftChild.list_data[pa.list_data[k-1]] = r;
786 }
787 } else {
788 root = r;
789 }
790
791 da.list_data[k] = 1;
792 pa.list_data[k++] = r;
793 //if (p==root)
794 //root = r;
795 } else {
796 long s;
797 int j = k++;
798 for (;;) {
799 da.list_data[k] = 0;
800 pa.list_data[k++] = r;
801 s = leftChild.list_data[r];
802 if (leftChild.list_data[s] < 0) {
803 break;
804 }
805 r = s;
806 }
807
808
809 leftChild.list_data[s] = leftChild.list_data[p];
810 leftChild.list_data[r] = rightChild.list_data[s];
811 rightChild.list_data[s] = rightChild.list_data[p];
812 balanceFactor.list_data[s] = balanceFactor.list_data[p];
813
814 if (j>1) {
815 if (da.list_data[j-1] == 1) {
816 rightChild.list_data[pa.list_data[j-1]] = s;
817 } else {
818 leftChild.list_data[pa.list_data[j-1]] = s;
819 }
820 }
821
822 da.list_data[j] = 1;
823 pa.list_data[j] = s;
824 if (p==root) {
825 root = s;
826 }
827 }
828 }
829
830 //if (k>63)
831 //{
832 //WarnError ("Internal List error");
833 //}
834
835 while (--k > 0) {
836 long y = pa.list_data[k];
837 if (da.list_data[k] == 0) {
838 balanceFactor.list_data[y] ++;
839 if (balanceFactor.list_data[y] == 1) {
840 break;
841 } else if (balanceFactor.list_data[y] == 2) {
842 long x = rightChild.list_data[y];
843 if (balanceFactor.list_data[x] == -1) {
844 long w = leftChild.list_data[x];
845 leftChild.list_data[x] = rightChild.list_data[w];
846 rightChild.list_data[w] = x;
847 rightChild.list_data[y] = leftChild.list_data[w];
848 leftChild.list_data[w] = y;
849 if (balanceFactor.list_data[w] == 1) {
850 balanceFactor.list_data[x] = 0;
851 balanceFactor.list_data[y] = -1;
852 } else if (balanceFactor.list_data[w] == 0) {
853 balanceFactor.list_data[x] = 0;
854 balanceFactor.list_data[y] = 0;
855 } else {
856 balanceFactor.list_data[x] = 1;
857 balanceFactor.list_data[y] = 0;
858 }
859
860 balanceFactor.list_data[w] = 0;
861 if (k>1) {
862 if (da.list_data[k-1] == 1) {
863 rightChild.list_data[pa.list_data[k-1]] = w;
864 } else {
865 leftChild.list_data[pa.list_data[k-1]] = w;
866 }
867 } else {
868 root = w;
869 }
870
871 //if (y==root)
872 // root = w;
873 } else {
874 rightChild.list_data[y] = leftChild.list_data[x];
875 leftChild.list_data[x] = y;
876
877 if (k>1) {
878 if (da.list_data[k-1] == 1) {
879 rightChild.list_data[pa.list_data[k-1]] = x;
880 } else {
881 leftChild.list_data[pa.list_data[k-1]] = x;
882 }
883 } else {
884 root = x;
885 }
886
887 if (balanceFactor.list_data[x] == 0) {
888 balanceFactor.list_data[x] = -1;
889 balanceFactor.list_data[y] = 1;
890 break;
891 } else {
892 balanceFactor.list_data[x] = 0;
893 balanceFactor.list_data[y] = 0;
894 }
895 }
896 }
897 } else {
898 balanceFactor.list_data[y] --;
899 if (balanceFactor.list_data[y] == -1) {
900 break;
901 } else if ( balanceFactor.list_data[y] == -2) {
902 long x = leftChild.list_data[y];
903 if (balanceFactor.list_data[x] == 1) {
904 long w = rightChild.list_data[x];
905 rightChild.list_data[x] = leftChild.list_data[w];
906 leftChild.list_data[w] = x;
907 leftChild.list_data[y] = rightChild.list_data[w];
908 rightChild.list_data[w] = y;
909 if (balanceFactor.list_data[w] == -1) {
910 balanceFactor.list_data[x] = 0;
911 balanceFactor.list_data[y] = 1;
912 } else if (balanceFactor.list_data[w] == 0) {
913 balanceFactor.list_data[x] = 0;
914 balanceFactor.list_data[y] = 0;
915 } else {
916 balanceFactor.list_data[x] = -1;
917 balanceFactor.list_data[y] = 0;
918 }
919
920 balanceFactor.list_data[w] = 0;
921 if (k>1) {
922 if (da.list_data[k-1] == 1) {
923 rightChild.list_data[pa.list_data[k-1]] = w;
924 } else {
925 leftChild.list_data[pa.list_data[k-1]] = w;
926 }
927 } else {
928 root = w;
929 }
930
931 //if (y==root)
932 //root = w;
933 } else {
934 leftChild.list_data[y] = rightChild.list_data[x];
935 rightChild.list_data[x] = y;
936 if (k>1) {
937 if (da.list_data[k-1] == 1) {
938 rightChild.list_data[pa.list_data[k-1]] = x;
939 } else {
940 leftChild.list_data[pa.list_data[k-1]] = x;
941 }
942 } else {
943 root = x;
944 }
945
946 if (balanceFactor.list_data[x] == 0) {
947 balanceFactor.list_data[x] = 1;
948 balanceFactor.list_data[y] = -1;
949 break;
950 } else {
951 balanceFactor.list_data[x] = 0;
952 balanceFactor.list_data[y] = 0;
953 }
954 }
955 }
956 }
957 }
958 //ConsistencyCheck ();
959
960 }
961