MPQC 2.3.1

- Main Page
- Related Pages
- Classes
- Files

- File List

eavlmmap.h
1 //
2 // eavlmmap.h --- definition for embedded avl multimap class
3 //
4 // Copyright (C) 1996 Limit Point Systems, Inc.
5 //
6 // Author: Curtis Janssen <cljanss@limitpt.com>
7 // Maintainer: LPS
8 //
9 // This file is part of the SC Toolkit.
10 //
11 // The SC Toolkit is free software; you can redistribute it and/or modify
12 // it under the terms of the GNU Library General Public License as published by
13 // the Free Software Foundation; either version 2, or (at your option)
14 // any later version.
15 //
16 // The SC Toolkit is distributed in the hope that it will be useful,
17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 // GNU Library General Public License for more details.
20 //
21 // You should have received a copy of the GNU Library General Public License
22 // along with the SC Toolkit; see the file COPYING.LIB. If not, write to
23 // the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
24 //
25 // The U.S. Government is granted a limited license as per AL 91-7.
26 //
27
28 #ifndef _util_container_eavlmmap_h
29 #define _util_container_eavlmmap_h
30
31 #ifdef HAVE_CONFIG_H
32 # include <scconfig.h>
33 #endif
34 #include <iostream>
35 #include <util/misc/exenv.h>
36 #include <util/container/compare.h>
37 #include <unistd.h> // for size_t on solaris
38 #include <stdlib.h>
39
40 #ifdef __GNUC__
41 // gcc typename seems to be broken in some cases
42 # define eavl_typename
43 #else
44 # define eavl_typename typename
45 #endif
46
47 namespace sc {
48
49 template <class K, class T>
50 class EAVLMMapNode {
51 public:
52 K key;
53 T* lt;
54 T* rt;
55 T* up;
56 int balance;
57 public:
58 EAVLMMapNode(const K& k): key(k) {}
59 };
60
61 template <class K, class T>
62 class EAVLMMap {
63 private:
64 size_t length_;
65 T *root_;
66 T *start_;
67 EAVLMMapNode<K,T> T::* node_;
68 public:
69 T*& rlink(T* n) const { return (n->*node_).rt; }
70 T* rlink(const T* n) const { return (n->*node_).rt; }
71 T*& llink(T* n) const { return (n->*node_).lt; }
72 T* llink(const T* n) const { return (n->*node_).lt; }
73 T*& uplink(T* n) const { return (n->*node_).up; }
74 T* uplink(const T* n) const { return (n->*node_).up; }
75 int& balance(T* n) const { return (n->*node_).balance; }
76 int balance(const T* n) const { return (n->*node_).balance; }
77 K& key(T* n) const { return (n->*node_).key; }
78 const K& key(const T* n) const { return (n->*node_).key; }
79 int compare(T*n,T*m) const { return sc::compare(key(n), key(m)); }
80 int compare(T*n,const K&m) const { return sc::compare(key(n), m); }
81 private:
82 void adjust_balance_insert(T* A, T* child);
83 void adjust_balance_remove(T* A, T* child);
84 void clear(T*);
85 public:
86 class iterator {
87 private:
88 EAVLMMap<K,T> *map_;
89 T *node;
90 public:
91 iterator(EAVLMMap<K,T> *m, T *n):map_(m),node(n){}
92 iterator(const eavl_typename EAVLMMap<K,T>::iterator &i) { map_=i.map_; node=i.node; }
93 void operator++() { map_->next(node); }
94 void operator++(int) { operator++(); }
95 int operator == (const eavl_typename EAVLMMap<K,T>::iterator &i) const
96 { return map_ == i.map_ && node == i.node; }
97 int operator != (const eavl_typename EAVLMMap<K,T>::iterator &i) const
98 { return !operator == (i); }
99 void operator = (const eavl_typename EAVLMMap<K,T>::iterator &i)
100 { map_ = i.map_; node = i.node; }
101 const K &key() const { return map_->key(node); }
102 T & operator *() { return *node; }
103 T * operator->() { return node; }
104 };
105 public:
106 EAVLMMap();
107 EAVLMMap(EAVLMMapNode<K,T> T::* node);
108 ~EAVLMMap() { clear(root_); }
109 void initialize(EAVLMMapNode<K,T> T::* node);
110 void clear_without_delete() { initialize(node_); }
111 void clear() { clear(root_); initialize(node_); }
112 void insert(T*);
113 void remove(T*);
114 T* find(const K&) const;
115
116 int height(T* node);
117 int height() { return height(root_); }
118 void check();
119 void check_node(T*) const;
120
121 T* start() const { return start_; }
122 void next(const T*&) const;
123 void next(T*&) const;
124
125 iterator begin() { return iterator(this,start()); }
126 iterator end() { return iterator(this,0); }
127
128 void print();
129 int length() const { return length_; }
130 int depth(T*);
131 };
132
133 template <class K, class T>
134 T*
135 EAVLMMap<K,T>::find(const K& key) const
136 {
137 T* n = root_;
138
139 while (n) {
140 int cmp = compare(n, key);
141 if (cmp < 0) n = rlink(n);
142 else if (cmp > 0) n = llink(n);
143 else return n;
144 }
145
146 return 0;
147 }
148
149 template <class K, class T>
150 void
151 EAVLMMap<K,T>::remove(T* node)
152 {
153 if (!node) return;
154
155 length_--;
156
157 if (node == start_) {
158 next(start_);
159 }
160
161 T *rebalance_point;
162 T *q;
163
164 if (llink(node) == 0) {
165 q = rlink(node);
166 rebalance_point = uplink(node);
167
168 if (q) uplink(q) = rebalance_point;
169
170 if (rebalance_point) {
171 if (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
172 else llink(rebalance_point) = q;
173 }
174 else root_ = q;
175 }
176 else if (rlink(node) == 0) {
177 q = llink(node);
178 rebalance_point = uplink(node);
179
180 if (q) uplink(q) = rebalance_point;
181
182 if (rebalance_point) {
183 if (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
184 else llink(rebalance_point) = q;
185 }
186 else root_ = q;
187 }
188 else {
189 T *r = node;
190 next(r);
191
192 if (r == 0 || llink(r) != 0) {
193 ExEnv::errn() << "EAVLMMap::remove: inconsistency" << std::endl;
194 abort();
195 }
196
197 if (r == rlink(node)) {
198 llink(r) = llink(node);
199 if (llink(r)) uplink(llink(r)) = r;
200 balance(r) = balance(node);
201 rebalance_point = r;
202 q = rlink(r);
203 }
204 else {
205 q = rlink(r);
206
207 rebalance_point = uplink(r);
208
209 if (llink(rebalance_point) == r) llink(rebalance_point) = q;
210 else rlink(rebalance_point) = q;
211
212 if (q) uplink(q) = rebalance_point;
213
214 balance(r) = balance(node);
215 rlink(r) = rlink(node);
216 llink(r) = llink(node);
217 if (rlink(r)) uplink(rlink(r)) = r;
218 if (llink(r)) uplink(llink(r)) = r;
219 }
220 if (r) {
221 T* up = uplink(node);
222 uplink(r) = up;
223 if (up) {
224 if (rlink(up) == node) rlink(up) = r;
225 else llink(up) = r;
226 }
227 if (up == 0) root_ = r;
228 }
229 }
230
231 // adjust balance won't work if both children are null,
232 // so handle this special case here
233 if (rebalance_point &&
234 llink(rebalance_point) == 0 && rlink(rebalance_point) == 0) {
235 balance(rebalance_point) = 0;
236 q = rebalance_point;
237 rebalance_point = uplink(rebalance_point);
238 }
239 adjust_balance_remove(rebalance_point, q);
240 }
241
242 template <class K, class T>
243 void
244 EAVLMMap<K,T>::print()
245 {
246 for (T*n=start(); n; next(n)) {
247 int d = depth(n) + 1;
248 for (int i=0; i<d; i++) ExEnv::out0() << " ";
249 if (balance(n) == 1) ExEnv::out0() << " (+)" << std::endl;
250 else if (balance(n) == -1) ExEnv::out0() << " (-)" << std::endl;
251 else if (balance(n) == 0) ExEnv::out0() << " (.)" << std::endl;
252 else ExEnv::out0() << " (" << balance(n) << ")" << std::endl;
253 }
254 }
255
256 template <class K, class T>
257 int
258 EAVLMMap<K,T>::depth(T*node)
259 {
260 int d = 0;
261 while (node) {
262 node = uplink(node);
263 d++;
264 }
265 return d;
266 }
267
268 template <class K, class T>
269 void
270 EAVLMMap<K,T>::check_node(T*n) const
271 {
272 if (uplink(n) && uplink(n) == n) abort();
273 if (llink(n) && llink(n) == n) abort();
274 if (rlink(n) && rlink(n) == n) abort();
275 if (rlink(n) && rlink(n) == llink(n)) abort();
276 if (uplink(n) && uplink(n) == llink(n)) abort();
277 if (uplink(n) && uplink(n) == rlink(n)) abort();
278 if (uplink(n) && !(llink(uplink(n)) == n
279 || rlink(uplink(n)) == n)) abort();
280 }
281
282 template <class K, class T>
283 void
284 EAVLMMap<K,T>::clear(T*n)
285 {
286 if (!n) return;
287 clear(llink(n));
288 clear(rlink(n));
289 delete n;
290 }
291
292 template <class K, class T>
293 int
294 EAVLMMap<K,T>::height(T* node)
295 {
296 if (!node) return 0;
297 int rh = height(rlink(node)) + 1;
298 int lh = height(llink(node)) + 1;
299 return rh>lh?rh:lh;
300 }
301
302 template <class K, class T>
303 void
304 EAVLMMap<K,T>::check()
305 {
306 T* node;
307 T* prev=0;
308 size_t computed_length = 0;
309 for (node = start(); node; next(node)) {
310 check_node(node);
311 if (prev && compare(prev,node) > 0) {
312 ExEnv::errn() << "nodes out of order" << std::endl;
313 abort();
314 }
315 prev = node;
316 computed_length++;
317 }
318 for (node = start(); node; next(node)) {
319 if (balance(node) != height(rlink(node)) - height(llink(node))) {
320 ExEnv::errn() << "balance inconsistency" << std::endl;
321 abort();
322 }
323 if (balance(node) < -1 || balance(node) > 1) {
324 ExEnv::errn() << "balance out of range" << std::endl;
325 abort();
326 }
327 }
328 if (length_ != computed_length) {
329 ExEnv::errn() << "length error" << std::endl;
330 abort();
331 }
332 }
333
334 template <class K, class T>
335 void
336 EAVLMMap<K,T>::next(const T*& node) const
337 {
338 const T* r;
339 if (r = rlink(node)) {
340 node = r;
341 while (r = llink(node)) node = r;
342 return;
343 }
344 while (r = uplink(node)) {
345 if (node == llink(r)) {
346 node = r;
347 return;
348 }
349 node = r;
350 }
351 node = 0;
352 }
353
354 template <class K, class T>
355 void
356 EAVLMMap<K,T>::next(T*& node) const
357 {
358 T* r;
359 if (r = rlink(node)) {
360 node = r;
361 while (r = llink(node)) node = r;
362 return;
363 }
364 while (r = uplink(node)) {
365 if (node == llink(r)) {
366 node = r;
367 return;
368 }
369 node = r;
370 }
371 node = 0;
372 }
373
374 template <class K, class T>
375 void
376 EAVLMMap<K,T>::insert(T* n)
377 {
378 if (!n) {
379 return;
380 }
381
382 length_++;
383
384 rlink(n) = 0;
385 llink(n) = 0;
386 balance(n) = 0;
387
388 if (!root_) {
389 uplink(n) = 0;
390 root_ = n;
391 start_ = n;
392 return;
393 }
394
395 // find an insertion point
396 T* p = root_;
397 T* prev_p = 0;
398 int cmp;
399 int have_start = 1;
400 while (p) {
401 if (p == n) {
402 abort();
403 }
404 prev_p = p;
405 cmp = compare(n,p);
406 if (cmp < 0) p = llink(p);
407 else {
408 p = rlink(p);
409 have_start = 0;
410 }
411 }
412
413 // insert the node
414 uplink(n) = prev_p;
415 if (prev_p) {
416 if (cmp < 0) llink(prev_p) = n;
417 else rlink(prev_p) = n;
418 }
419
420 // maybe update the first node in the map
421 if (have_start) start_ = n;
422
423 // adjust the balance factors
424 if (prev_p) {
425 adjust_balance_insert(prev_p, n);
426 }
427 }
428
429 template <class K, class T>
430 void
431 EAVLMMap<K,T>::adjust_balance_insert(T* A, T* child)
432 {
433 if (!A) return;
434 int adjustment;
435 if (llink(A) == child) adjustment = -1;
436 else adjustment = 1;
437 int bal = balance(A) + adjustment;
438 if (bal == 0) {
439 balance(A) = 0;
440 }
441 else if (bal == -1 || bal == 1) {
442 balance(A) = bal;
443 adjust_balance_insert(uplink(A), A);
444 }
445 else if (bal == 2) {
446 T* B = rlink(A);
447 if (balance(B) == 1) {
448 balance(B) = 0;
449 balance(A) = 0;
450 rlink(A) = llink(B);
451 llink(B) = A;
452 uplink(B) = uplink(A);
453 uplink(A) = B;
454 if (rlink(A)) uplink(rlink(A)) = A;
455 if (llink(B)) uplink(llink(B)) = B;
456 if (uplink(B) == 0) root_ = B;
457 else {
458 if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
459 else llink(uplink(B)) = B;
460 }
461 }
462 else {
463 T* X = llink(B);
464 rlink(A) = llink(X);
465 llink(B) = rlink(X);
466 llink(X) = A;
467 rlink(X) = B;
468 if (balance(X) == 1) {
469 balance(A) = -1;
470 balance(B) = 0;
471 }
472 else if (balance(X) == -1) {
473 balance(A) = 0;
474 balance(B) = 1;
475 }
476 else {
477 balance(A) = 0;
478 balance(B) = 0;
479 }
480 balance(X) = 0;
481 uplink(X) = uplink(A);
482 uplink(A) = X;
483 uplink(B) = X;
484 if (rlink(A)) uplink(rlink(A)) = A;
485 if (llink(B)) uplink(llink(B)) = B;
486 if (uplink(X) == 0) root_ = X;
487 else {
488 if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
489 else llink(uplink(X)) = X;
490 }
491 }
492 }
493 else if (bal == -2) {
494 T* B = llink(A);
495 if (balance(B) == -1) {
496 balance(B) = 0;
497 balance(A) = 0;
498 llink(A) = rlink(B);
499 rlink(B) = A;
500 uplink(B) = uplink(A);
501 uplink(A) = B;
502 if (llink(A)) uplink(llink(A)) = A;
503 if (rlink(B)) uplink(rlink(B)) = B;
504 if (uplink(B) == 0) root_ = B;
505 else {
506 if (llink(uplink(B)) == A) llink(uplink(B)) = B;
507 else rlink(uplink(B)) = B;
508 }
509 }
510 else {
511 T* X = rlink(B);
512 llink(A) = rlink(X);
513 rlink(B) = llink(X);
514 rlink(X) = A;
515 llink(X) = B;
516 if (balance(X) == -1) {
517 balance(A) = 1;
518 balance(B) = 0;
519 }
520 else if (balance(X) == 1) {
521 balance(A) = 0;
522 balance(B) = -1;
523 }
524 else {
525 balance(A) = 0;
526 balance(B) = 0;
527 }
528 balance(X) = 0;
529 uplink(X) = uplink(A);
530 uplink(A) = X;
531 uplink(B) = X;
532 if (llink(A)) uplink(llink(A)) = A;
533 if (rlink(B)) uplink(rlink(B)) = B;
534 if (uplink(X) == 0) root_ = X;
535 else {
536 if (llink(uplink(X)) == A) llink(uplink(X)) = X;
537 else rlink(uplink(X)) = X;
538 }
539 }
540 }
541 }
542
543 template <class K, class T>
544 void
545 EAVLMMap<K,T>::adjust_balance_remove(T* A, T* child)
546 {
547 if (!A) return;
548 int adjustment;
549 if (llink(A) == child) adjustment = 1;
550 else adjustment = -1;
551 int bal = balance(A) + adjustment;
552 if (bal == 0) {
553 balance(A) = 0;
554 adjust_balance_remove(uplink(A), A);
555 }
556 else if (bal == -1 || bal == 1) {
557 balance(A) = bal;
558 }
559 else if (bal == 2) {
560 T* B = rlink(A);
561 if (balance(B) == 0) {
562 balance(B) = -1;
563 balance(A) = 1;
564 rlink(A) = llink(B);
565 llink(B) = A;
566 uplink(B) = uplink(A);
567 uplink(A) = B;
568 if (rlink(A)) uplink(rlink(A)) = A;
569 if (llink(B)) uplink(llink(B)) = B;
570 if (uplink(B) == 0) root_ = B;
571 else {
572 if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
573 else llink(uplink(B)) = B;
574 }
575 }
576 else if (balance(B) == 1) {
577 balance(B) = 0;
578 balance(A) = 0;
579 rlink(A) = llink(B);
580 llink(B) = A;
581 uplink(B) = uplink(A);
582 uplink(A) = B;
583 if (rlink(A)) uplink(rlink(A)) = A;
584 if (llink(B)) uplink(llink(B)) = B;
585 if (uplink(B) == 0) root_ = B;
586 else {
587 if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
588 else llink(uplink(B)) = B;
589 }
590 adjust_balance_remove(uplink(B), B);
591 }
592 else {
593 T* X = llink(B);
594 rlink(A) = llink(X);
595 llink(B) = rlink(X);
596 llink(X) = A;
597 rlink(X) = B;
598 if (balance(X) == 0) {
599 balance(A) = 0;
600 balance(B) = 0;
601 }
602 else if (balance(X) == 1) {
603 balance(A) = -1;
604 balance(B) = 0;
605 }
606 else {
607 balance(A) = 0;
608 balance(B) = 1;
609 }
610 balance(X) = 0;
611 uplink(X) = uplink(A);
612 uplink(A) = X;
613 uplink(B) = X;
614 if (rlink(A)) uplink(rlink(A)) = A;
615 if (llink(B)) uplink(llink(B)) = B;
616 if (uplink(X) == 0) root_ = X;
617 else {
618 if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
619 else llink(uplink(X)) = X;
620 }
621 adjust_balance_remove(uplink(X), X);
622 }
623 }
624 else if (bal == -2) {
625 T* B = llink(A);
626 if (balance(B) == 0) {
627 balance(B) = 1;
628 balance(A) = -1;
629 llink(A) = rlink(B);
630 rlink(B) = A;
631 uplink(B) = uplink(A);
632 uplink(A) = B;
633 if (llink(A)) uplink(llink(A)) = A;
634 if (rlink(B)) uplink(rlink(B)) = B;
635 if (uplink(B) == 0) root_ = B;
636 else {
637 if (llink(uplink(B)) == A) llink(uplink(B)) = B;
638 else rlink(uplink(B)) = B;
639 }
640 }
641 else if (balance(B) == -1) {
642 balance(B) = 0;
643 balance(A) = 0;
644 llink(A) = rlink(B);
645 rlink(B) = A;
646 uplink(B) = uplink(A);
647 uplink(A) = B;
648 if (llink(A)) uplink(llink(A)) = A;
649 if (rlink(B)) uplink(rlink(B)) = B;
650 if (uplink(B) == 0) root_ = B;
651 else {
652 if (llink(uplink(B)) == A) llink(uplink(B)) = B;
653 else rlink(uplink(B)) = B;
654 }
655 adjust_balance_remove(uplink(B), B);
656 }
657 else {
658 T* X = rlink(B);
659 llink(A) = rlink(X);
660 rlink(B) = llink(X);
661 rlink(X) = A;
662 llink(X) = B;
663 if (balance(X) == 0) {
664 balance(A) = 0;
665 balance(B) = 0;
666 }
667 else if (balance(X) == -1) {
668 balance(A) = 1;
669 balance(B) = 0;
670 }
671 else {
672 balance(A) = 0;
673 balance(B) = -1;
674 }
675 balance(X) = 0;
676 uplink(X) = uplink(A);
677 uplink(A) = X;
678 uplink(B) = X;
679 if (llink(A)) uplink(llink(A)) = A;
680 if (rlink(B)) uplink(rlink(B)) = B;
681 if (uplink(X) == 0) root_ = X;
682 else {
683 if (llink(uplink(X)) == A) llink(uplink(X)) = X;
684 else rlink(uplink(X)) = X;
685 }
686 adjust_balance_remove(uplink(X), X);
687 }
688 }
689 }
690
691 template <class K, class T>
692 inline
693 EAVLMMap<K,T>::EAVLMMap()
694 {
695 initialize(0);
696 }
697
698 template <class K, class T>
699 inline
700 EAVLMMap<K,T>::EAVLMMap(EAVLMMapNode<K,T> T::* node)
701 {
702 initialize(node);
703 }
704
705 template <class K, class T>
706 inline void
707 EAVLMMap<K,T>::initialize(EAVLMMapNode<K,T> T::* node)
708 {
709 node_ = node;
710 root_ = 0;
711 start_ = 0;
712 length_ = 0;
713 }
714
715 }
716
717 #endif
718
719 // ///////////////////////////////////////////////////////////////////////////
720
721 // Local Variables:
722 // mode: c++
723 // c-file-style: "CLJ"
724 // End: