eavlmmap.h
00001 //
00002 // eavlmmap.h --- definition for embedded avl multimap class
00003 //
00004 // Copyright (C) 1996 Limit Point Systems, Inc.
00005 //
00006 // Author: Curtis Janssen <cljanss@limitpt.com>
00007 // Maintainer: LPS
00008 //
00009 // This file is part of the SC Toolkit.
00010 //
00011 // The SC Toolkit is free software; you can redistribute it and/or modify
00012 // it under the terms of the GNU Library General Public License as published by
00013 // the Free Software Foundation; either version 2, or (at your option)
00014 // any later version.
00015 //
00016 // The SC Toolkit is distributed in the hope that it will be useful,
00017 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00018 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
00019 // GNU Library General Public License for more details.
00020 //
00021 // You should have received a copy of the GNU Library General Public License
00022 // along with the SC Toolkit; see the file COPYING.LIB. If not, write to
00023 // the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
00024 //
00025 // The U.S. Government is granted a limited license as per AL 91-7.
00026 //
00027
00028 #ifndef _util_container_eavlmmap_h
00029 #define _util_container_eavlmmap_h
00030
00031 #ifdef HAVE_CONFIG_H
00032 # include <scconfig.h>
00033 #endif
00034 #include <iostream>
00035 #include <util/misc/exenv.h>
00036 #include <util/container/compare.h>
00037 #include <unistd.h> // for size_t on solaris
00038 #include <stdlib.h>
00039
00040 #ifdef __GNUC__
00041 // gcc typename seems to be broken in some cases
00042 # define eavl_typename
00043 #else
00044 # define eavl_typename typename
00045 #endif
00046
00047 namespace sc {
00048
00049 template <class K, class T>
00050 class EAVLMMapNode {
00051 public:
00052 K key;
00053 T* lt;
00054 T* rt;
00055 T* up;
00056 int balance;
00057 public:
00058 EAVLMMapNode(const K& k): key(k) {}
00059 };
00060
00061 template <class K, class T>
00062 class EAVLMMap {
00063 private:
00064 size_t length_;
00065 T *root_;
00066 T *start_;
00067 EAVLMMapNode<K,T> T::* node_;
00068 public:
00069 T*& rlink(T* n) const { return (n->*node_).rt; }
00070 T* rlink(const T* n) const { return (n->*node_).rt; }
00071 T*& llink(T* n) const { return (n->*node_).lt; }
00072 T* llink(const T* n) const { return (n->*node_).lt; }
00073 T*& uplink(T* n) const { return (n->*node_).up; }
00074 T* uplink(const T* n) const { return (n->*node_).up; }
00075 int& balance(T* n) const { return (n->*node_).balance; }
00076 int balance(const T* n) const { return (n->*node_).balance; }
00077 K& key(T* n) const { return (n->*node_).key; }
00078 const K& key(const T* n) const { return (n->*node_).key; }
00079 int compare(T*n,T*m) const { return sc::compare(key(n), key(m)); }
00080 int compare(T*n,const K&m) const { return sc::compare(key(n), m); }
00081 private:
00082 void adjust_balance_insert(T* A, T* child);
00083 void adjust_balance_remove(T* A, T* child);
00084 void clear(T*);
00085 public:
00086 class iterator {
00087 private:
00088 EAVLMMap<K,T> *map_;
00089 T *node;
00090 public:
00091 iterator(EAVLMMap<K,T> *m, T *n):map_(m),node(n){}
00092 iterator(const eavl_typename EAVLMMap<K,T>::iterator &i) { map_=i.map_; node=i.node; }
00093 void operator++() { map_->next(node); }
00094 void operator++(int) { operator++(); }
00095 int operator == (const eavl_typename EAVLMMap<K,T>::iterator &i) const
00096 { return map_ == i.map_ && node == i.node; }
00097 int operator != (const eavl_typename EAVLMMap<K,T>::iterator &i) const
00098 { return !operator == (i); }
00099 void operator = (const eavl_typename EAVLMMap<K,T>::iterator &i)
00100 { map_ = i.map_; node = i.node; }
00101 const K &key() const { return map_->key(node); }
00102 T & operator *() { return *node; }
00103 T * operator->() { return node; }
00104 };
00105 public:
00106 EAVLMMap();
00107 EAVLMMap(EAVLMMapNode<K,T> T::* node);
00108 ~EAVLMMap() { clear(root_); }
00109 void initialize(EAVLMMapNode<K,T> T::* node);
00110 void clear_without_delete() { initialize(node_); }
00111 void clear() { clear(root_); initialize(node_); }
00112 void insert(T*);
00113 void remove(T*);
00114 T* find(const K&) const;
00115
00116 int height(T* node);
00117 int height() { return height(root_); }
00118 void check();
00119 void check_node(T*) const;
00120
00121 T* start() const { return start_; }
00122 void next(const T*&) const;
00123 void next(T*&) const;
00124
00125 iterator begin() { return iterator(this,start()); }
00126 iterator end() { return iterator(this,0); }
00127
00128 void print();
00129 int length() const { return length_; }
00130 int depth(T*);
00131 };
00132
00133 template <class K, class T>
00134 T*
00135 EAVLMMap<K,T>::find(const K& key) const
00136 {
00137 T* n = root_;
00138
00139 while (n) {
00140 int cmp = compare(n, key);
00141 if (cmp < 0) n = rlink(n);
00142 else if (cmp > 0) n = llink(n);
00143 else return n;
00144 }
00145
00146 return 0;
00147 }
00148
00149 template <class K, class T>
00150 void
00151 EAVLMMap<K,T>::remove(T* node)
00152 {
00153 if (!node) return;
00154
00155 length_--;
00156
00157 if (node == start_) {
00158 next(start_);
00159 }
00160
00161 T *rebalance_point;
00162 T *q;
00163
00164 if (llink(node) == 0) {
00165 q = rlink(node);
00166 rebalance_point = uplink(node);
00167
00168 if (q) uplink(q) = rebalance_point;
00169
00170 if (rebalance_point) {
00171 if (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
00172 else llink(rebalance_point) = q;
00173 }
00174 else root_ = q;
00175 }
00176 else if (rlink(node) == 0) {
00177 q = llink(node);
00178 rebalance_point = uplink(node);
00179
00180 if (q) uplink(q) = rebalance_point;
00181
00182 if (rebalance_point) {
00183 if (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
00184 else llink(rebalance_point) = q;
00185 }
00186 else root_ = q;
00187 }
00188 else {
00189 T *r = node;
00190 next(r);
00191
00192 if (r == 0 || llink(r) != 0) {
00193 ExEnv::errn() << "EAVLMMap::remove: inconsistency" << std::endl;
00194 abort();
00195 }
00196
00197 if (r == rlink(node)) {
00198 llink(r) = llink(node);
00199 if (llink(r)) uplink(llink(r)) = r;
00200 balance(r) = balance(node);
00201 rebalance_point = r;
00202 q = rlink(r);
00203 }
00204 else {
00205 q = rlink(r);
00206
00207 rebalance_point = uplink(r);
00208
00209 if (llink(rebalance_point) == r) llink(rebalance_point) = q;
00210 else rlink(rebalance_point) = q;
00211
00212 if (q) uplink(q) = rebalance_point;
00213
00214 balance(r) = balance(node);
00215 rlink(r) = rlink(node);
00216 llink(r) = llink(node);
00217 if (rlink(r)) uplink(rlink(r)) = r;
00218 if (llink(r)) uplink(llink(r)) = r;
00219 }
00220 if (r) {
00221 T* up = uplink(node);
00222 uplink(r) = up;
00223 if (up) {
00224 if (rlink(up) == node) rlink(up) = r;
00225 else llink(up) = r;
00226 }
00227 if (up == 0) root_ = r;
00228 }
00229 }
00230
00231 // adjust balance won't work if both children are null,
00232 // so handle this special case here
00233 if (rebalance_point &&
00234 llink(rebalance_point) == 0 && rlink(rebalance_point) == 0) {
00235 balance(rebalance_point) = 0;
00236 q = rebalance_point;
00237 rebalance_point = uplink(rebalance_point);
00238 }
00239 adjust_balance_remove(rebalance_point, q);
00240 }
00241
00242 template <class K, class T>
00243 void
00244 EAVLMMap<K,T>::print()
00245 {
00246 for (T*n=start(); n; next(n)) {
00247 int d = depth(n) + 1;
00248 for (int i=0; i<d; i++) ExEnv::out0() << " ";
00249 if (balance(n) == 1) ExEnv::out0() << " (+)" << std::endl;
00250 else if (balance(n) == -1) ExEnv::out0() << " (-)" << std::endl;
00251 else if (balance(n) == 0) ExEnv::out0() << " (.)" << std::endl;
00252 else ExEnv::out0() << " (" << balance(n) << ")" << std::endl;
00253 }
00254 }
00255
00256 template <class K, class T>
00257 int
00258 EAVLMMap<K,T>::depth(T*node)
00259 {
00260 int d = 0;
00261 while (node) {
00262 node = uplink(node);
00263 d++;
00264 }
00265 return d;
00266 }
00267
00268 template <class K, class T>
00269 void
00270 EAVLMMap<K,T>::check_node(T*n) const
00271 {
00272 if (uplink(n) && uplink(n) == n) abort();
00273 if (llink(n) && llink(n) == n) abort();
00274 if (rlink(n) && rlink(n) == n) abort();
00275 if (rlink(n) && rlink(n) == llink(n)) abort();
00276 if (uplink(n) && uplink(n) == llink(n)) abort();
00277 if (uplink(n) && uplink(n) == rlink(n)) abort();
00278 if (uplink(n) && !(llink(uplink(n)) == n
00279 || rlink(uplink(n)) == n)) abort();
00280 }
00281
00282 template <class K, class T>
00283 void
00284 EAVLMMap<K,T>::clear(T*n)
00285 {
00286 if (!n) return;
00287 clear(llink(n));
00288 clear(rlink(n));
00289 delete n;
00290 }
00291
00292 template <class K, class T>
00293 int
00294 EAVLMMap<K,T>::height(T* node)
00295 {
00296 if (!node) return 0;
00297 int rh = height(rlink(node)) + 1;
00298 int lh = height(llink(node)) + 1;
00299 return rh>lh?rh:lh;
00300 }
00301
00302 template <class K, class T>
00303 void
00304 EAVLMMap<K,T>::check()
00305 {
00306 T* node;
00307 T* prev=0;
00308 size_t computed_length = 0;
00309 for (node = start(); node; next(node)) {
00310 check_node(node);
00311 if (prev && compare(prev,node) > 0) {
00312 ExEnv::errn() << "nodes out of order" << std::endl;
00313 abort();
00314 }
00315 prev = node;
00316 computed_length++;
00317 }
00318 for (node = start(); node; next(node)) {
00319 if (balance(node) != height(rlink(node)) - height(llink(node))) {
00320 ExEnv::errn() << "balance inconsistency" << std::endl;
00321 abort();
00322 }
00323 if (balance(node) < -1 || balance(node) > 1) {
00324 ExEnv::errn() << "balance out of range" << std::endl;
00325 abort();
00326 }
00327 }
00328 if (length_ != computed_length) {
00329 ExEnv::errn() << "length error" << std::endl;
00330 abort();
00331 }
00332 }
00333
00334 template <class K, class T>
00335 void
00336 EAVLMMap<K,T>::next(const T*& node) const
00337 {
00338 const T* r;
00339 if (r = rlink(node)) {
00340 node = r;
00341 while (r = llink(node)) node = r;
00342 return;
00343 }
00344 while (r = uplink(node)) {
00345 if (node == llink(r)) {
00346 node = r;
00347 return;
00348 }
00349 node = r;
00350 }
00351 node = 0;
00352 }
00353
00354 template <class K, class T>
00355 void
00356 EAVLMMap<K,T>::next(T*& node) const
00357 {
00358 T* r;
00359 if (r = rlink(node)) {
00360 node = r;
00361 while (r = llink(node)) node = r;
00362 return;
00363 }
00364 while (r = uplink(node)) {
00365 if (node == llink(r)) {
00366 node = r;
00367 return;
00368 }
00369 node = r;
00370 }
00371 node = 0;
00372 }
00373
00374 template <class K, class T>
00375 void
00376 EAVLMMap<K,T>::insert(T* n)
00377 {
00378 if (!n) {
00379 return;
00380 }
00381
00382 length_++;
00383
00384 rlink(n) = 0;
00385 llink(n) = 0;
00386 balance(n) = 0;
00387
00388 if (!root_) {
00389 uplink(n) = 0;
00390 root_ = n;
00391 start_ = n;
00392 return;
00393 }
00394
00395 // find an insertion point
00396 T* p = root_;
00397 T* prev_p = 0;
00398 int cmp;
00399 int have_start = 1;
00400 while (p) {
00401 if (p == n) {
00402 abort();
00403 }
00404 prev_p = p;
00405 cmp = compare(n,p);
00406 if (cmp < 0) p = llink(p);
00407 else {
00408 p = rlink(p);
00409 have_start = 0;
00410 }
00411 }
00412
00413 // insert the node
00414 uplink(n) = prev_p;
00415 if (prev_p) {
00416 if (cmp < 0) llink(prev_p) = n;
00417 else rlink(prev_p) = n;
00418 }
00419
00420 // maybe update the first node in the map
00421 if (have_start) start_ = n;
00422
00423 // adjust the balance factors
00424 if (prev_p) {
00425 adjust_balance_insert(prev_p, n);
00426 }
00427 }
00428
00429 template <class K, class T>
00430 void
00431 EAVLMMap<K,T>::adjust_balance_insert(T* A, T* child)
00432 {
00433 if (!A) return;
00434 int adjustment;
00435 if (llink(A) == child) adjustment = -1;
00436 else adjustment = 1;
00437 int bal = balance(A) + adjustment;
00438 if (bal == 0) {
00439 balance(A) = 0;
00440 }
00441 else if (bal == -1 || bal == 1) {
00442 balance(A) = bal;
00443 adjust_balance_insert(uplink(A), A);
00444 }
00445 else if (bal == 2) {
00446 T* B = rlink(A);
00447 if (balance(B) == 1) {
00448 balance(B) = 0;
00449 balance(A) = 0;
00450 rlink(A) = llink(B);
00451 llink(B) = A;
00452 uplink(B) = uplink(A);
00453 uplink(A) = B;
00454 if (rlink(A)) uplink(rlink(A)) = A;
00455 if (llink(B)) uplink(llink(B)) = B;
00456 if (uplink(B) == 0) root_ = B;
00457 else {
00458 if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
00459 else llink(uplink(B)) = B;
00460 }
00461 }
00462 else {
00463 T* X = llink(B);
00464 rlink(A) = llink(X);
00465 llink(B) = rlink(X);
00466 llink(X) = A;
00467 rlink(X) = B;
00468 if (balance(X) == 1) {
00469 balance(A) = -1;
00470 balance(B) = 0;
00471 }
00472 else if (balance(X) == -1) {
00473 balance(A) = 0;
00474 balance(B) = 1;
00475 }
00476 else {
00477 balance(A) = 0;
00478 balance(B) = 0;
00479 }
00480 balance(X) = 0;
00481 uplink(X) = uplink(A);
00482 uplink(A) = X;
00483 uplink(B) = X;
00484 if (rlink(A)) uplink(rlink(A)) = A;
00485 if (llink(B)) uplink(llink(B)) = B;
00486 if (uplink(X) == 0) root_ = X;
00487 else {
00488 if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
00489 else llink(uplink(X)) = X;
00490 }
00491 }
00492 }
00493 else if (bal == -2) {
00494 T* B = llink(A);
00495 if (balance(B) == -1) {
00496 balance(B) = 0;
00497 balance(A) = 0;
00498 llink(A) = rlink(B);
00499 rlink(B) = A;
00500 uplink(B) = uplink(A);
00501 uplink(A) = B;
00502 if (llink(A)) uplink(llink(A)) = A;
00503 if (rlink(B)) uplink(rlink(B)) = B;
00504 if (uplink(B) == 0) root_ = B;
00505 else {
00506 if (llink(uplink(B)) == A) llink(uplink(B)) = B;
00507 else rlink(uplink(B)) = B;
00508 }
00509 }
00510 else {
00511 T* X = rlink(B);
00512 llink(A) = rlink(X);
00513 rlink(B) = llink(X);
00514 rlink(X) = A;
00515 llink(X) = B;
00516 if (balance(X) == -1) {
00517 balance(A) = 1;
00518 balance(B) = 0;
00519 }
00520 else if (balance(X) == 1) {
00521 balance(A) = 0;
00522 balance(B) = -1;
00523 }
00524 else {
00525 balance(A) = 0;
00526 balance(B) = 0;
00527 }
00528 balance(X) = 0;
00529 uplink(X) = uplink(A);
00530 uplink(A) = X;
00531 uplink(B) = X;
00532 if (llink(A)) uplink(llink(A)) = A;
00533 if (rlink(B)) uplink(rlink(B)) = B;
00534 if (uplink(X) == 0) root_ = X;
00535 else {
00536 if (llink(uplink(X)) == A) llink(uplink(X)) = X;
00537 else rlink(uplink(X)) = X;
00538 }
00539 }
00540 }
00541 }
00542
00543 template <class K, class T>
00544 void
00545 EAVLMMap<K,T>::adjust_balance_remove(T* A, T* child)
00546 {
00547 if (!A) return;
00548 int adjustment;
00549 if (llink(A) == child) adjustment = 1;
00550 else adjustment = -1;
00551 int bal = balance(A) + adjustment;
00552 if (bal == 0) {
00553 balance(A) = 0;
00554 adjust_balance_remove(uplink(A), A);
00555 }
00556 else if (bal == -1 || bal == 1) {
00557 balance(A) = bal;
00558 }
00559 else if (bal == 2) {
00560 T* B = rlink(A);
00561 if (balance(B) == 0) {
00562 balance(B) = -1;
00563 balance(A) = 1;
00564 rlink(A) = llink(B);
00565 llink(B) = A;
00566 uplink(B) = uplink(A);
00567 uplink(A) = B;
00568 if (rlink(A)) uplink(rlink(A)) = A;
00569 if (llink(B)) uplink(llink(B)) = B;
00570 if (uplink(B) == 0) root_ = B;
00571 else {
00572 if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
00573 else llink(uplink(B)) = B;
00574 }
00575 }
00576 else if (balance(B) == 1) {
00577 balance(B) = 0;
00578 balance(A) = 0;
00579 rlink(A) = llink(B);
00580 llink(B) = A;
00581 uplink(B) = uplink(A);
00582 uplink(A) = B;
00583 if (rlink(A)) uplink(rlink(A)) = A;
00584 if (llink(B)) uplink(llink(B)) = B;
00585 if (uplink(B) == 0) root_ = B;
00586 else {
00587 if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
00588 else llink(uplink(B)) = B;
00589 }
00590 adjust_balance_remove(uplink(B), B);
00591 }
00592 else {
00593 T* X = llink(B);
00594 rlink(A) = llink(X);
00595 llink(B) = rlink(X);
00596 llink(X) = A;
00597 rlink(X) = B;
00598 if (balance(X) == 0) {
00599 balance(A) = 0;
00600 balance(B) = 0;
00601 }
00602 else if (balance(X) == 1) {
00603 balance(A) = -1;
00604 balance(B) = 0;
00605 }
00606 else {
00607 balance(A) = 0;
00608 balance(B) = 1;
00609 }
00610 balance(X) = 0;
00611 uplink(X) = uplink(A);
00612 uplink(A) = X;
00613 uplink(B) = X;
00614 if (rlink(A)) uplink(rlink(A)) = A;
00615 if (llink(B)) uplink(llink(B)) = B;
00616 if (uplink(X) == 0) root_ = X;
00617 else {
00618 if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
00619 else llink(uplink(X)) = X;
00620 }
00621 adjust_balance_remove(uplink(X), X);
00622 }
00623 }
00624 else if (bal == -2) {
00625 T* B = llink(A);
00626 if (balance(B) == 0) {
00627 balance(B) = 1;
00628 balance(A) = -1;
00629 llink(A) = rlink(B);
00630 rlink(B) = A;
00631 uplink(B) = uplink(A);
00632 uplink(A) = B;
00633 if (llink(A)) uplink(llink(A)) = A;
00634 if (rlink(B)) uplink(rlink(B)) = B;
00635 if (uplink(B) == 0) root_ = B;
00636 else {
00637 if (llink(uplink(B)) == A) llink(uplink(B)) = B;
00638 else rlink(uplink(B)) = B;
00639 }
00640 }
00641 else if (balance(B) == -1) {
00642 balance(B) = 0;
00643 balance(A) = 0;
00644 llink(A) = rlink(B);
00645 rlink(B) = A;
00646 uplink(B) = uplink(A);
00647 uplink(A) = B;
00648 if (llink(A)) uplink(llink(A)) = A;
00649 if (rlink(B)) uplink(rlink(B)) = B;
00650 if (uplink(B) == 0) root_ = B;
00651 else {
00652 if (llink(uplink(B)) == A) llink(uplink(B)) = B;
00653 else rlink(uplink(B)) = B;
00654 }
00655 adjust_balance_remove(uplink(B), B);
00656 }
00657 else {
00658 T* X = rlink(B);
00659 llink(A) = rlink(X);
00660 rlink(B) = llink(X);
00661 rlink(X) = A;
00662 llink(X) = B;
00663 if (balance(X) == 0) {
00664 balance(A) = 0;
00665 balance(B) = 0;
00666 }
00667 else if (balance(X) == -1) {
00668 balance(A) = 1;
00669 balance(B) = 0;
00670 }
00671 else {
00672 balance(A) = 0;
00673 balance(B) = -1;
00674 }
00675 balance(X) = 0;
00676 uplink(X) = uplink(A);
00677 uplink(A) = X;
00678 uplink(B) = X;
00679 if (llink(A)) uplink(llink(A)) = A;
00680 if (rlink(B)) uplink(rlink(B)) = B;
00681 if (uplink(X) == 0) root_ = X;
00682 else {
00683 if (llink(uplink(X)) == A) llink(uplink(X)) = X;
00684 else rlink(uplink(X)) = X;
00685 }
00686 adjust_balance_remove(uplink(X), X);
00687 }
00688 }
00689 }
00690
00691 template <class K, class T>
00692 inline
00693 EAVLMMap<K,T>::EAVLMMap()
00694 {
00695 initialize(0);
00696 }
00697
00698 template <class K, class T>
00699 inline
00700 EAVLMMap<K,T>::EAVLMMap(EAVLMMapNode<K,T> T::* node)
00701 {
00702 initialize(node);
00703 }
00704
00705 template <class K, class T>
00706 inline void
00707 EAVLMMap<K,T>::initialize(EAVLMMapNode<K,T> T::* node)
00708 {
00709 node_ = node;
00710 root_ = 0;
00711 start_ = 0;
00712 length_ = 0;
00713 }
00714
00715 }
00716
00717 #endif
00718
00719 // ///////////////////////////////////////////////////////////////////////////
00720
00721 // Local Variables:
00722 // mode: c++
00723 // c-file-style: "CLJ"
00724 // End:
Generated at Fri Jan 10 08:14:08 2003 for MPQC 2.1.3 using the documentation package Doxygen 1.2.14.