28 #ifndef _util_container_eavlmmap_h
29 #define _util_container_eavlmmap_h
32 # include <scconfig.h>
35 #include <util/misc/exenv.h>
36 #include <util/container/compare.h>
42 # define eavl_typename
44 # define eavl_typename typename
49 template <
class K,
class T>
61 template <
class K,
class T>
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); }
82 void adjust_balance_insert(T* A, T* child);
83 void adjust_balance_remove(T* A, T* child);
93 void operator++() { map_->next(node); }
94 void operator++(
int) { operator++(); }
96 {
return map_ == i.map_ && node == i.node; }
98 {
return !operator == (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; }
110 void clear_without_delete() { initialize(node_); }
111 void clear() { clear(root_); initialize(node_); }
114 T* find(
const K&)
const;
117 int height() {
return height(root_); }
119 void check_node(T*)
const;
121 T* start()
const {
return start_; }
122 void next(
const T*&)
const;
123 void next(T*&)
const;
125 iterator begin() {
return iterator(
this,start()); }
126 iterator end() {
return iterator(
this,0); }
129 int length()
const {
return length_; }
133 template <
class K,
class T>
135 EAVLMMap<K,T>::find(
const K& key)
const
140 int cmp = compare(n, key);
141 if (cmp < 0) n = rlink(n);
142 else if (cmp > 0) n = llink(n);
149 template <
class K,
class T>
151 EAVLMMap<K,T>::remove(T* node)
157 if (node == start_) {
164 if (llink(node) == 0) {
166 rebalance_point = uplink(node);
168 if (q) uplink(q) = rebalance_point;
170 if (rebalance_point) {
171 if (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
172 else llink(rebalance_point) = q;
176 else if (rlink(node) == 0) {
178 rebalance_point = uplink(node);
180 if (q) uplink(q) = rebalance_point;
182 if (rebalance_point) {
183 if (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
184 else llink(rebalance_point) = q;
192 if (r == 0 || llink(r) != 0) {
193 ExEnv::errn() <<
"EAVLMMap::remove: inconsistency" << std::endl;
197 if (r == rlink(node)) {
198 llink(r) = llink(node);
199 if (llink(r)) uplink(llink(r)) = r;
200 balance(r) = balance(node);
207 rebalance_point = uplink(r);
209 if (llink(rebalance_point) == r) llink(rebalance_point) = q;
210 else rlink(rebalance_point) = q;
212 if (q) uplink(q) = rebalance_point;
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;
221 T* up = uplink(node);
224 if (rlink(up) == node) rlink(up) = r;
227 if (up == 0) root_ = r;
233 if (rebalance_point &&
234 llink(rebalance_point) == 0 && rlink(rebalance_point) == 0) {
235 balance(rebalance_point) = 0;
237 rebalance_point = uplink(rebalance_point);
239 adjust_balance_remove(rebalance_point, q);
242 template <
class K,
class T>
244 EAVLMMap<K,T>::print()
246 for (T*n=start(); n; next(n)) {
247 int d = depth(n) + 1;
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;
256 template <
class K,
class T>
258 EAVLMMap<K,T>::depth(T*node)
268 template <
class K,
class T>
270 EAVLMMap<K,T>::check_node(T*n)
const
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();
282 template <
class K,
class T>
284 EAVLMMap<K,T>::clear(T*n)
292 template <
class K,
class T>
294 EAVLMMap<K,T>::height(T* node)
297 int rh = height(rlink(node)) + 1;
298 int lh = height(llink(node)) + 1;
302 template <
class K,
class T>
304 EAVLMMap<K,T>::check()
308 size_t computed_length = 0;
309 for (node = start(); node; next(node)) {
311 if (prev && compare(prev,node) > 0) {
312 ExEnv::errn() <<
"nodes out of order" << std::endl;
318 for (node = start(); node; next(node)) {
319 if (balance(node) != height(rlink(node)) - height(llink(node))) {
320 ExEnv::errn() <<
"balance inconsistency" << std::endl;
323 if (balance(node) < -1 || balance(node) > 1) {
324 ExEnv::errn() <<
"balance out of range" << std::endl;
328 if (length_ != computed_length) {
334 template <
class K,
class T>
336 EAVLMMap<K,T>::next(
const T*& node)
const
339 if (r = rlink(node)) {
341 while (r = llink(node)) node = r;
344 while (r = uplink(node)) {
345 if (node == llink(r)) {
354 template <
class K,
class T>
356 EAVLMMap<K,T>::next(T*& node)
const
359 if (r = rlink(node)) {
361 while (r = llink(node)) node = r;
364 while (r = uplink(node)) {
365 if (node == llink(r)) {
374 template <
class K,
class T>
376 EAVLMMap<K,T>::insert(T* n)
406 if (cmp < 0) p = llink(p);
416 if (cmp < 0) llink(prev_p) = n;
417 else rlink(prev_p) = n;
421 if (have_start) start_ = n;
425 adjust_balance_insert(prev_p, n);
429 template <
class K,
class T>
431 EAVLMMap<K,T>::adjust_balance_insert(T* A, T* child)
435 if (llink(A) == child) adjustment = -1;
437 int bal = balance(A) + adjustment;
441 else if (bal == -1 || bal == 1) {
443 adjust_balance_insert(uplink(A), A);
447 if (balance(B) == 1) {
452 uplink(B) = uplink(A);
454 if (rlink(A)) uplink(rlink(A)) = A;
455 if (llink(B)) uplink(llink(B)) = B;
456 if (uplink(B) == 0) root_ = B;
458 if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
459 else llink(uplink(B)) = B;
468 if (balance(X) == 1) {
472 else if (balance(X) == -1) {
481 uplink(X) = uplink(A);
484 if (rlink(A)) uplink(rlink(A)) = A;
485 if (llink(B)) uplink(llink(B)) = B;
486 if (uplink(X) == 0) root_ = X;
488 if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
489 else llink(uplink(X)) = X;
493 else if (bal == -2) {
495 if (balance(B) == -1) {
500 uplink(B) = uplink(A);
502 if (llink(A)) uplink(llink(A)) = A;
503 if (rlink(B)) uplink(rlink(B)) = B;
504 if (uplink(B) == 0) root_ = B;
506 if (llink(uplink(B)) == A) llink(uplink(B)) = B;
507 else rlink(uplink(B)) = B;
516 if (balance(X) == -1) {
520 else if (balance(X) == 1) {
529 uplink(X) = uplink(A);
532 if (llink(A)) uplink(llink(A)) = A;
533 if (rlink(B)) uplink(rlink(B)) = B;
534 if (uplink(X) == 0) root_ = X;
536 if (llink(uplink(X)) == A) llink(uplink(X)) = X;
537 else rlink(uplink(X)) = X;
543 template <
class K,
class T>
545 EAVLMMap<K,T>::adjust_balance_remove(T* A, T* child)
549 if (llink(A) == child) adjustment = 1;
550 else adjustment = -1;
551 int bal = balance(A) + adjustment;
554 adjust_balance_remove(uplink(A), A);
556 else if (bal == -1 || bal == 1) {
561 if (balance(B) == 0) {
566 uplink(B) = uplink(A);
568 if (rlink(A)) uplink(rlink(A)) = A;
569 if (llink(B)) uplink(llink(B)) = B;
570 if (uplink(B) == 0) root_ = B;
572 if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
573 else llink(uplink(B)) = B;
576 else if (balance(B) == 1) {
581 uplink(B) = uplink(A);
583 if (rlink(A)) uplink(rlink(A)) = A;
584 if (llink(B)) uplink(llink(B)) = B;
585 if (uplink(B) == 0) root_ = B;
587 if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
588 else llink(uplink(B)) = B;
590 adjust_balance_remove(uplink(B), B);
598 if (balance(X) == 0) {
602 else if (balance(X) == 1) {
611 uplink(X) = uplink(A);
614 if (rlink(A)) uplink(rlink(A)) = A;
615 if (llink(B)) uplink(llink(B)) = B;
616 if (uplink(X) == 0) root_ = X;
618 if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
619 else llink(uplink(X)) = X;
621 adjust_balance_remove(uplink(X), X);
624 else if (bal == -2) {
626 if (balance(B) == 0) {
631 uplink(B) = uplink(A);
633 if (llink(A)) uplink(llink(A)) = A;
634 if (rlink(B)) uplink(rlink(B)) = B;
635 if (uplink(B) == 0) root_ = B;
637 if (llink(uplink(B)) == A) llink(uplink(B)) = B;
638 else rlink(uplink(B)) = B;
641 else if (balance(B) == -1) {
646 uplink(B) = uplink(A);
648 if (llink(A)) uplink(llink(A)) = A;
649 if (rlink(B)) uplink(rlink(B)) = B;
650 if (uplink(B) == 0) root_ = B;
652 if (llink(uplink(B)) == A) llink(uplink(B)) = B;
653 else rlink(uplink(B)) = B;
655 adjust_balance_remove(uplink(B), B);
663 if (balance(X) == 0) {
667 else if (balance(X) == -1) {
676 uplink(X) = uplink(A);
679 if (llink(A)) uplink(llink(A)) = A;
680 if (rlink(B)) uplink(rlink(B)) = B;
681 if (uplink(X) == 0) root_ = X;
683 if (llink(uplink(X)) == A) llink(uplink(X)) = X;
684 else rlink(uplink(X)) = X;
686 adjust_balance_remove(uplink(X), X);
691 template <
class K,
class T>
693 EAVLMMap<K,T>::EAVLMMap()
698 template <
class K,
class T>
700 EAVLMMap<K,T>::EAVLMMap(EAVLMMapNode<K,T> T::* node)
705 template <
class K,
class T>
707 EAVLMMap<K,T>::initialize(EAVLMMapNode<K,T> T::* node)