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