source: trunk/src/emx/include/Attic/cpp/gen/RAVLMap.ccP@ 18

Last change on this file since 18 was 18, checked in by bird, 23 years ago

Initial revision
  • Property cvs2svn:cvs-rev set to 1.1
  • Property svn:eol-style set to native
  • Property svn:executable set to *
File size: 14.1 KB
Line 
1// This may look like C code, but it is really -*- C++ -*-
2/*
3Copyright (C) 1988 Free Software Foundation
4 written by Doug Lea ([email protected])
5
6This file is part of the GNU C++ Library. This library is free
7software; you can redistribute it and/or modify it under the terms of
8the GNU Library General Public License as published by the Free
9Software Foundation; either version 2 of the License, or (at your
10option) any later version. This library is distributed in the hope
11that it will be useful, but WITHOUT ANY WARRANTY; without even the
12implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
13PURPOSE. See the GNU Library General Public License for more details.
14You should have received a copy of the GNU Library General Public
15License along with this library; if not, write to the Free Software
16Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17*/
18
19#ifdef __GNUG__
20#pragma implementation
21#endif
22#include <stream.h>
23#include "<T>.<C>.RAVLMap.h"
24
25
26/*
27 constants & inlines for maintaining balance & thread status in tree nodes
28*/
29
30#define AVLBALANCEMASK 3
31#define AVLBALANCED 0
32#define AVLLEFTHEAVY 1
33#define AVLRIGHTHEAVY 2
34
35#define LTHREADBIT 4
36#define RTHREADBIT 8
37
38
39static inline int bf(<T><C>RAVLNode* t)
40{
41 return t->stat & AVLBALANCEMASK;
42}
43
44static inline void set_bf(<T><C>RAVLNode* t, int b)
45{
46 t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
47}
48
49
50static inline int rthread(<T><C>RAVLNode* t)
51{
52 return t->stat & RTHREADBIT;
53}
54
55static inline void set_rthread(<T><C>RAVLNode* t, int b)
56{
57 if (b)
58 t->stat |= RTHREADBIT;
59 else
60 t->stat &= ~RTHREADBIT;
61}
62
63static inline int lthread(<T><C>RAVLNode* t)
64{
65 return t->stat & LTHREADBIT;
66}
67
68static inline void set_lthread(<T><C>RAVLNode* t, int b)
69{
70 if (b)
71 t->stat |= LTHREADBIT;
72 else
73 t->stat &= ~LTHREADBIT;
74}
75
76/*
77 traversal primitives
78*/
79
80
81<T><C>RAVLNode* <T><C>RAVLMap::leftmost()
82{
83 <T><C>RAVLNode* t = root;
84 if (t != 0) while (t->lt != 0) t = t->lt;
85 return t;
86}
87
88<T><C>RAVLNode* <T><C>RAVLMap::rightmost()
89{
90 <T><C>RAVLNode* t = root;
91 if (t != 0) while (t->rt != 0) t = t->rt;
92 return t;
93}
94
95<T><C>RAVLNode* <T><C>RAVLMap::succ(<T><C>RAVLNode* t)
96{
97 <T><C>RAVLNode* r = t->rt;
98 if (!rthread(t)) while (!lthread(r)) r = r->lt;
99 return r;
100}
101
102<T><C>RAVLNode* <T><C>RAVLMap::pred(<T><C>RAVLNode* t)
103{
104 <T><C>RAVLNode* l = t->lt;
105 if (!lthread(t)) while (!rthread(l)) l = l->rt;
106 return l;
107}
108
109
110Pix <T><C>RAVLMap::seek(<T&> key)
111{
112 <T><C>RAVLNode* t = root;
113 if (t == 0)
114 return 0;
115 for (;;)
116 {
117 int cmp = <T>CMP(key, t->item);
118 if (cmp == 0)
119 return Pix(t);
120 else if (cmp < 0)
121 {
122 if (lthread(t))
123 return 0;
124 else
125 t = t->lt;
126 }
127 else if (rthread(t))
128 return 0;
129 else
130 t = t->rt;
131 }
132}
133
134
135int <T><C>RAVLMap::rankof(<T&> key)
136{
137 int r;
138 <T><C>RAVLNode* t = root;
139 if (t == 0)
140 return 0;
141 for (r=t->rank; t != 0; r+=t->rank)
142 {
143 int cmp = <T>CMP(key, t->item);
144 if (cmp == 0)
145 return r;
146 else if (cmp < 0)
147 {
148 if (lthread(t))
149 return 0;
150 else
151 {
152 r -= t->rank;
153 t = t->lt;
154 }
155 }
156 else if (rthread(t))
157 return 0;
158 else
159 {
160 t = t->rt;
161 }
162 }
163 return 0;
164}
165
166Pix <T><C>RAVLMap::ranktoPix(int i)
167{
168 int r;
169 <T><C>RAVLNode* t = root;
170
171 if ((i<1)||(i>count))
172 return 0;
173 for (r=t->rank; r!=i; r+=t->rank)
174 {
175 if (r>i)
176 {
177 r -= t->rank;
178 t = t->lt;
179 }
180 else
181 t = t->rt;
182 }
183 return Pix(t);
184}
185
186/*
187 The combination of threads and AVL bits make adding & deleting
188 interesting, but very awkward.
189
190 We use the following statics to avoid passing them around recursively
191*/
192
193static int _need_rebalancing; // to send back balance info from rec. calls
194static <T>* _target_item; // add/del_item target
195static <T><C>RAVLNode* _found_node; // returned added/deleted node
196static int _already_found; // for deletion subcases
197static int _rank_changed; // for rank computation
198
199
200void <T><C>RAVLMap:: _add(<T><C>RAVLNode*& t)
201{
202 int cmp = <T>CMP(*_target_item, t->item);
203 if (cmp == 0)
204 {
205 _found_node = t;
206 return;
207 }
208 else if (cmp < 0)
209 {
210 if (lthread(t))
211 {
212 ++count;
213 _found_node = new <T><C>RAVLNode(*_target_item, def);
214 set_lthread(_found_node, 1);
215 set_rthread(_found_node, 1);
216 _found_node->lt = t->lt;
217 _found_node->rt = t;
218 t->lt = _found_node;
219 set_lthread(t, 0);
220 _need_rebalancing = 1;
221 _rank_changed = 1;
222 }
223 else
224 _add(t->lt);
225 if (_rank_changed) ++t->rank;
226 if (_need_rebalancing)
227 {
228 switch(bf(t))
229 {
230 case AVLRIGHTHEAVY:
231 set_bf(t, AVLBALANCED);
232 _need_rebalancing = 0;
233 return;
234 case AVLBALANCED:
235 set_bf(t, AVLLEFTHEAVY);
236 return;
237 case AVLLEFTHEAVY:
238 {
239 <T><C>RAVLNode* l = t->lt;
240 if (bf(l) == AVLLEFTHEAVY)
241 {
242 t->rank -= l->rank;
243 if (rthread(l))
244 t->lt = l;
245 else
246 t->lt = l->rt;
247 set_lthread(t, rthread(l));
248 l->rt = t;
249 set_rthread(l, 0);
250 set_bf(t, AVLBALANCED);
251 set_bf(l, AVLBALANCED);
252 t = l;
253 _need_rebalancing = 0;
254 }
255 else
256 {
257 <T><C>RAVLNode* r = l->rt;
258 r->rank += l->rank;
259 t->rank -= r->rank;
260 set_rthread(l, lthread(r));
261 if (lthread(r))
262 l->rt = r;
263 else
264 l->rt = r->lt;
265 r->lt = l;
266 set_lthread(r, 0);
267 set_lthread(t, rthread(r));
268 if (rthread(r))
269 t->lt = r;
270 else
271 t->lt = r->rt;
272 r->rt = t;
273 set_rthread(r, 0);
274 if (bf(r) == AVLLEFTHEAVY)
275 set_bf(t, AVLRIGHTHEAVY);
276 else
277 set_bf(t, AVLBALANCED);
278 if (bf(r) == AVLRIGHTHEAVY)
279 set_bf(l, AVLLEFTHEAVY);
280 else
281 set_bf(l, AVLBALANCED);
282 set_bf(r, AVLBALANCED);
283 t = r;
284 _need_rebalancing = 0;
285 return;
286 }
287 }
288 }
289 }
290 }
291 else
292 {
293 if (rthread(t))
294 {
295 ++count;
296 _found_node = new <T><C>RAVLNode(*_target_item, def);
297 set_rthread(t, 0);
298 set_lthread(_found_node, 1);
299 set_rthread(_found_node, 1);
300 _found_node->lt = t;
301 _found_node->rt = t->rt;
302 t->rt = _found_node;
303 _need_rebalancing = 1;
304 _rank_changed = 1;
305 }
306 else
307 _add(t->rt);
308 if (_need_rebalancing)
309 {
310 switch(bf(t))
311 {
312 case AVLLEFTHEAVY:
313 set_bf(t, AVLBALANCED);
314 _need_rebalancing = 0;
315 return;
316 case AVLBALANCED:
317 set_bf(t, AVLRIGHTHEAVY);
318 return;
319 case AVLRIGHTHEAVY:
320 {
321 <T><C>RAVLNode* r = t->rt;
322 if (bf(r) == AVLRIGHTHEAVY)
323 {
324 r->rank += t->rank;
325 if (lthread(r))
326 t->rt = r;
327 else
328 t->rt = r->lt;
329 set_rthread(t, lthread(r));
330 r->lt = t;
331 set_lthread(r, 0);
332 set_bf(t, AVLBALANCED);
333 set_bf(r, AVLBALANCED);
334 t = r;
335 _need_rebalancing = 0;
336 }
337 else
338 {
339 <T><C>RAVLNode* l = r->lt;
340 r->rank -= l->rank;
341 l->rank += t->rank;
342 set_lthread(r, rthread(l));
343 if (rthread(l))
344 r->lt = l;
345 else
346 r->lt = l->rt;
347 l->rt = r;
348 set_rthread(l, 0);
349 set_rthread(t, lthread(l));
350 if (lthread(l))
351 t->rt = l;
352 else
353 t->rt = l->lt;
354 l->lt = t;
355 set_lthread(l, 0);
356 if (bf(l) == AVLRIGHTHEAVY)
357 set_bf(t, AVLLEFTHEAVY);
358 else
359 set_bf(t, AVLBALANCED);
360 if (bf(l) == AVLLEFTHEAVY)
361 set_bf(r, AVLRIGHTHEAVY);
362 else
363 set_bf(r, AVLBALANCED);
364 set_bf(l, AVLBALANCED);
365 t = l;
366 _need_rebalancing = 0;
367 return;
368 }
369 }
370 }
371 }
372 }
373}
374
375
376<C>& <T><C>RAVLMap::operator [] (<T&> item)
377{
378 if (root == 0)
379 {
380 ++count;
381 root = new <T><C>RAVLNode(item, def);
382 set_rthread(root, 1);
383 set_lthread(root, 1);
384 return root->cont;
385 }
386 else
387 {
388 _target_item = &item;
389 _need_rebalancing = 0;
390 _rank_changed = 0;
391 _add(root);
392 return _found_node->cont;
393 }
394}
395
396
397void <T><C>RAVLMap::_del(<T><C>RAVLNode* par, <T><C>RAVLNode*& t)
398{
399 int comp;
400 if (_already_found)
401 {
402 if (rthread(t))
403 comp = 0;
404 else
405 comp = 1;
406 }
407 else
408 comp = <T>CMP(*_target_item, t->item);
409 if (comp == 0)
410 {
411 if (lthread(t) && rthread(t))
412 {
413 _found_node = t;
414 if (t == par->lt)
415 {
416 set_lthread(par, 1);
417 par->lt = t->lt;
418 }
419 else
420 {
421 set_rthread(par, 1);
422 par->rt = t->rt;
423 }
424 _need_rebalancing = 1;
425 _rank_changed = 1;
426 return;
427 }
428 else if (lthread(t))
429 {
430 _found_node = t;
431 <T><C>RAVLNode* s = succ(t);
432 if (s != 0 && lthread(s))
433 s->lt = t->lt;
434 t = t->rt;
435 _need_rebalancing = 1;
436 _rank_changed = 1;
437 return;
438 }
439 else if (rthread(t))
440 {
441 _found_node = t;
442 <T><C>RAVLNode* p = pred(t);
443 if (p != 0 && rthread(p))
444 p->rt = t->rt;
445 t = t->lt;
446 _need_rebalancing = 1;
447 _rank_changed = 1;
448 return;
449 }
450 else // replace item & find someone deletable
451 {
452 <T><C>RAVLNode* p = pred(t);
453 t->item = p->item;
454 t->cont = p->cont;
455 _already_found = 1;
456 comp = -1; // fall through below to left
457 }
458 }
459
460 if (comp < 0)
461 {
462 if (lthread(t))
463 return;
464 _del(t, t->lt);
465 if (_rank_changed) --t->rank;
466 if (!_need_rebalancing)
467 return;
468 switch (bf(t))
469 {
470 case AVLLEFTHEAVY:
471 set_bf(t, AVLBALANCED);
472 return;
473 case AVLBALANCED:
474 set_bf(t, AVLRIGHTHEAVY);
475 _need_rebalancing = 0;
476 return;
477 case AVLRIGHTHEAVY:
478 {
479 <T><C>RAVLNode* r = t->rt;
480 switch (bf(r))
481 {
482 case AVLBALANCED:
483 r->rank += t->rank;
484 if (lthread(r))
485 t->rt = r;
486 else
487 t->rt = r->lt;
488 set_rthread(t, lthread(r));
489 r->lt = t;
490 set_lthread(r, 0);
491 set_bf(t, AVLRIGHTHEAVY);
492 set_bf(r, AVLLEFTHEAVY);
493 _need_rebalancing = 0;
494 t = r;
495 return;
496 case AVLRIGHTHEAVY:
497 r->rank += t->rank;
498 if (lthread(r))
499 t->rt = r;
500 else
501 t->rt = r->lt;
502 set_rthread(t, lthread(r));
503 r->lt = t;
504 set_lthread(r, 0);
505 set_bf(t, AVLBALANCED);
506 set_bf(r, AVLBALANCED);
507 t = r;
508 return;
509 case AVLLEFTHEAVY:
510 {
511 <T><C>RAVLNode* l = r->lt;
512 r->rank -= l->rank;
513 l->rank += t->rank;
514 set_lthread(r, rthread(l));
515 if (rthread(l))
516 r->lt = l;
517 else
518 r->lt = l->rt;
519 l->rt = r;
520 set_rthread(l, 0);
521 set_rthread(t, lthread(l));
522 if (lthread(l))
523 t->rt = l;
524 else
525 t->rt = l->lt;
526 l->lt = t;
527 set_lthread(l, 0);
528 if (bf(l) == AVLRIGHTHEAVY)
529 set_bf(t, AVLLEFTHEAVY);
530 else
531 set_bf(t, AVLBALANCED);
532 if (bf(l) == AVLLEFTHEAVY)
533 set_bf(r, AVLRIGHTHEAVY);
534 else
535 set_bf(r, AVLBALANCED);
536 set_bf(l, AVLBALANCED);
537 t = l;
538 return;
539 }
540 }
541 }
542 }
543 }
544 else
545 {
546 if (rthread(t))
547 return;
548 _del(t, t->rt);
549 if (!_need_rebalancing)
550 return;
551 switch (bf(t))
552 {
553 case AVLRIGHTHEAVY:
554 set_bf(t, AVLBALANCED);
555 return;
556 case AVLBALANCED:
557 set_bf(t, AVLLEFTHEAVY);
558 _need_rebalancing = 0;
559 return;
560 case AVLLEFTHEAVY:
561 {
562 <T><C>RAVLNode* l = t->lt;
563 switch (bf(l))
564 {
565 case AVLBALANCED:
566 t->rank -= l->rank;
567 if (rthread(l))
568 t->lt = l;
569 else
570 t->lt = l->rt;
571 set_lthread(t, rthread(l));
572 l->rt = t;
573 set_rthread(l, 0);
574 set_bf(t, AVLLEFTHEAVY);
575 set_bf(l, AVLRIGHTHEAVY);
576 _need_rebalancing = 0;
577 t = l;
578 return;
579 case AVLLEFTHEAVY:
580 t->rank -= l->rank;
581 if (rthread(l))
582 t->lt = l;
583 else
584 t->lt = l->rt;
585 set_lthread(t, rthread(l));
586 l->rt = t;
587 set_rthread(l, 0);
588 set_bf(t, AVLBALANCED);
589 set_bf(l, AVLBALANCED);
590 t = l;
591 return;
592 case AVLRIGHTHEAVY:
593 {
594 <T><C>RAVLNode* r = l->rt;
595 r->rank += l->rank;
596 t->rank -= r->rank;
597 set_rthread(l, lthread(r));
598 if (lthread(r))
599 l->rt = r;
600 else
601 l->rt = r->lt;
602 r->lt = l;
603 set_lthread(r, 0);
604 set_lthread(t, rthread(r));
605 if (rthread(r))
606 t->lt = r;
607 else
608 t->lt = r->rt;
609 r->rt = t;
610 set_rthread(r, 0);
611 if (bf(r) == AVLLEFTHEAVY)
612 set_bf(t, AVLRIGHTHEAVY);
613 else
614 set_bf(t, AVLBALANCED);
615 if (bf(r) == AVLRIGHTHEAVY)
616 set_bf(l, AVLLEFTHEAVY);
617 else
618 set_bf(l, AVLBALANCED);
619 set_bf(r, AVLBALANCED);
620 t = r;
621 return;
622 }
623 }
624 }
625 }
626 }
627}
628
629
630void <T><C>RAVLMap::del(<T&> item)
631{
632 if (root == 0) return;
633 _need_rebalancing = 0;
634 _already_found = 0;
635 _found_node = 0;
636 _rank_changed = 0;
637 _target_item = &item;
638 _del(root, root);
639 if (_found_node)
640 {
641 delete(_found_node);
642 if (--count == 0)
643 root = 0;
644 }
645}
646
647void <T><C>RAVLMap::_kill(<T><C>RAVLNode* t)
648{
649 if (t != 0)
650 {
651 if (!lthread(t)) _kill(t->lt);
652 if (!rthread(t)) _kill(t->rt);
653 delete t;
654 }
655}
656
657
658<T><C>RAVLMap::<T><C>RAVLMap(<T><C>RAVLMap& b) :<T><C>Map(b.def)
659{
660 root = 0;
661 count = 0;
662 for (Pix i = b.first(); i != 0; b.next(i))
663 (*this)[b.key(i)] = b.contents(i);
664}
665
666
667int <T><C>RAVLMap::OK()
668{
669 int v = 1;
670 if (root == 0)
671 v = count == 0;
672 else
673 {
674 int n = 1;
675 <T><C>RAVLNode* trail = leftmost();
676 v &= rankof(trail->item) == n;
677 <T><C>RAVLNode* t = succ(trail);
678 while (t != 0)
679 {
680 ++n;
681 v &= <T>CMP(trail->item, t->item) < 0;
682 v &= rankof(t->item) == n;
683 trail = t;
684 t = succ(t);
685 }
686 v &= n == count;
687 }
688 if (!v) error("invariant failure");
689 return v;
690}
Note: See TracBrowser for help on using the repository browser.