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