MPQC  3.0.0-alpha
avlmmap.h
1 //
2 // avlmmap.h --- definition for avl multimap class
3 //
4 // Copyright (C) 1996 Limit Point Systems, Inc.
5 //
6 // Author: Curtis Janssen <cljanss@ca.sandia.gov>
7 // Maintainer: SNL
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_avlmmap_h
29 #define _util_container_avlmmap_h
30 
31 #include <iostream>
32 #include <functional>
33 #include <vector>
34 #include <stdexcept>
35 
36 #include <unistd.h> // for size_t on solaris
37 #include <stdlib.h>
38 
39 namespace sc {
40 
41 template <class K, class T>
42 class AVLMMapNode {
43  public:
44  std::pair<K,T> keyval;
45  AVLMMapNode<K,T>* lt;
46  AVLMMapNode<K,T>* rt;
47  AVLMMapNode<K,T>* up;
48  int balance;
49  public:
50  AVLMMapNode(const std::pair<K,T> &kv): keyval(kv) {}
51  AVLMMapNode(const K& k, const T&v): keyval(std::make_pair(k,v)) {}
52  K& key() { return keyval.first; }
53  const K& key() const { return keyval.first; }
54  T& val() { return keyval.second; }
55  const T& val() const { return keyval.second; }
56 };
57 
58 template <class T>
59 class chunk_allocator {
60  enum {default_chunksize = 4096};
61  struct chunk {
62  void *data;
63  chunk *next;
64  int current;
65  int chunksize;
66  chunk(int _chunksize, int datasize) {
67  data = new char[_chunksize*datasize];
68  next = 0;
69  current = 0;
70  chunksize = _chunksize;
71  }
72  ~chunk() {
73  delete[] (char*)data;
74  }
75  };
76  chunk *head;
77  long total;
78  public:
79  chunk_allocator() {
80  total = 0;
81  head = new chunk(default_chunksize, sizeof(T));
82  }
83  ~chunk_allocator() {
84  if (total != 0) {
85  std::cout << "chunks remain: " << total << std::endl;
86  abort();
87  }
88  for (chunk *i = head; i;) {
89  chunk *next = i->next;
90  delete i;
91  i = next;
92  }
93  }
94  void reinit() {
95  if (total != 0) {
96  std::cout << "reinit: chunks remain: " << total << std::endl;
97  abort();
98  }
99  for (chunk *i = head; i;) {
100  chunk *next = i->next;
101  delete i;
102  i = next;
103  }
104  head = new chunk(default_chunksize, sizeof(T));
105  }
106  void destroy(T*d) {
107  d->~T();
108  }
109  void deallocate(T*d,int n) {
110  // deallocated memory is not reclaimed until the chunk_allocator dtor
111  // is called
112  total -= n;
113  }
114  T *allocate(int n) {
115  if (n==1) {
116  if (head->current == head->chunksize) {
117  chunk *newhead = new chunk(default_chunksize, sizeof(T));
118  newhead->next = head;
119  head = newhead;
120  }
121  T *r = &((T*)head->data)[head->current];
122  head->current++;
123  total += n;
124  return r;
125  }
126  else if (n>0) {
127  chunk *newchunk = new chunk(n, sizeof(T));
128  newchunk->next = head->next;
129  head->next = newchunk;
130  total += n;
131  return (T*)newchunk->data;
132  }
133  else {
134  return 0;
135  }
136  }
137 };
138 
139 template <class T>
140 class tristate_less {
141  public:
142  bool operator()(const T&a, const T&b) const {
143  return a < b;
144  }
145  int compare(const T&a, const T&b) const {
146  if (a < b) return -1;
147  else if (a > b) return 1;
148  return 0;
149  }
150 };
151 
152 template <class K, class T, class C = tristate_less<K>,
153  class A = chunk_allocator<AVLMMapNode<K,T> > >
154 // class A = std::allocator<AVLMMapNode<K,T> > >
155 class AVLMMap {
156  private:
157  typedef AVLMMapNode<K,T> * link_type;
158  C key_comp_;
159  A alloc_;
160  size_t length_;
161  AVLMMapNode<K,T> *root_;
162  AVLMMapNode<K,T> *start_;
163  public:
164  static AVLMMapNode<K,T>*& rlink(AVLMMapNode<K,T>* n) { return n->rt; }
165  static AVLMMapNode<K,T>* rlink(const AVLMMapNode<K,T>* n) { return n->rt; }
166  static AVLMMapNode<K,T>*& llink(AVLMMapNode<K,T>* n) { return n->lt; }
167  static AVLMMapNode<K,T>* llink(const AVLMMapNode<K,T>* n) { return n->lt; }
168  static AVLMMapNode<K,T>*& uplink(AVLMMapNode<K,T>* n) { return n->up; }
169  static AVLMMapNode<K,T>* uplink(const AVLMMapNode<K,T>* n) { return n->up; }
170  static int& balance(AVLMMapNode<K,T>* n) { return n->balance; }
171  static int balance(const AVLMMapNode<K,T>* n) { return n->balance; }
172  static const K& key(const AVLMMapNode<K,T>* n) { return n->key(); }
173  int compare(const K&n,const K&m) const {
174  return key_comp_.compare(n,m);
175 // This is for a standard boolean comparision operation
176 // if (key_comp_(n, m)) return -1;
177 // else if (key_comp_(m, n)) return 1;
178 // return 0;
179  }
180  private:
181  void adjust_balance_insert(AVLMMapNode<K,T>* _A, AVLMMapNode<K,T>* child);
182  void adjust_balance_remove(AVLMMapNode<K,T>* _A, AVLMMapNode<K,T>* child);
183  void clear(AVLMMapNode<K,T>*);
184  public:
185  typedef C key_compare;
186  typedef std::pair<K,T> value_type;
187  class iterator {
188  friend class AVLMMap<K,T,C,A>;
189  public:
190  AVLMMapNode<K,T> *node;
191  public:
192  iterator(AVLMMapNode<K,T> *n = 0):node(n){}
193  iterator(const typename AVLMMap<K,T,C>::iterator &i) { node=i.node; }
194  void operator++() { AVLMMap<K,T,C>::next(node); }
195  void operator++(int) { operator++(); }
196  int operator == (const typename AVLMMap<K,T,C>::iterator &i) const
197  { return node == i.node; }
198  int operator != (const typename AVLMMap<K,T,C>::iterator &i) const
199  { return node != i.node; }
200  void operator = (const typename AVLMMap<K,T,C>::iterator &i)
201  { node = i.node; }
202  const K &key() const { return node->key(); }
203  std::pair<K,T> & operator *() { return node->keyval; }
204  std::pair<K,T> * operator->() { return &node->keyval; }
205  };
206  class const_iterator {
207  friend class AVLMMap<K,T,C,A>;
208  private:
209  const AVLMMapNode<K,T> *node;
210  public:
211  const_iterator(const AVLMMapNode<K,T> *n = 0):node(n){}
212  const_iterator(const typename AVLMMap<K,T,C>::const_iterator &i) { node=i.node; }
213  const_iterator(const typename AVLMMap<K,T,C>::iterator &i) { node=i.node; }
214  void operator++() { AVLMMap<K,T,C>::next(node); }
215  void operator++(int) { operator++(); }
216  int operator == (const typename AVLMMap<K,T,C>::const_iterator &i) const
217  { return node == i.node; }
218  int operator != (const typename AVLMMap<K,T,C>::const_iterator &i) const
219  { return node != i.node; }
220  void operator = (const typename AVLMMap<K,T,C>::const_iterator &i)
221  { node = i.node; }
222  const K &key() const { return node->key(); }
223  const std::pair<K,T> & operator *() { return node->keyval; }
224  const std::pair<K,T> * operator->() { return &node->keyval; }
225  };
226  private:
227  iterator subtree_insert_new_(AVLMMapNode<K,T> *root, AVLMMapNode<K,T> *node);
228  iterator subtree_insert_equal_(AVLMMapNode<K,T> *root, AVLMMapNode<K,T> *node);
229  iterator subtree_insert_unique_(AVLMMapNode<K,T> *root,
230  const std::pair<K,T> &ipair);
231  iterator subtree_find_(AVLMMapNode<K,T> *root, const K&);
232  const_iterator subtree_find_(const AVLMMapNode<K,T> *root, const K&) const;
233  public:
234  AVLMMap();
235  AVLMMap(const C& c);
236  AVLMMap(const AVLMMap<K,T,C,A>&m);
237  ~AVLMMap() { clear(); }
238  key_compare key_comp() const { return key_comp_; }
239  void initialize();
240  void clear() {
241  clear(root_);
242  length_ = 0;
243  root_ = 0;
244  start_ = 0;
245  // destroy the allocator
246  // this is needed to force deletion of all data if the chunk_allocator is used
247  alloc_.~A();
248  // reconstruct the allocator
249  new((void*)&alloc_)A;
250 // alloc_.reinit();
251  }
252  // Insert an element. The element must not already exist.
253  iterator insert_new(const iterator &hint, const std::pair<K,T> &ipair);
254 // // Insert an element. If an element with the same key already exists
255 // // then a duplicate element will be added.
256 // iterator insert_equal(const iterator &hint, const std::pair<K,T> &ipair);
257 // // Insert an element. If an entry with the key already exists then
258 // // this will do nothing and return the iterator for the pre-existing
259 // // element.
260 // iterator insert_unique(const iterator &hint, const std::pair<K,T> &ipair);
261  // slow; do not use:
262  iterator insert_equal(const iterator &hint, const std::pair<K,T> &ipair);
263  // Insert an element. The element must not already exist.
264  iterator insert_new(const std::pair<K,T> &ipair);
265  // Insert an element. If an element with the same key already exists
266  // then a duplicate element will be added.
267  iterator insert_equal(const std::pair<K,T> &ipair);
268  // Insert an element. If an entry with the key already exists then
269  // this will do nothing and return the iterator for the pre-existing
270  // element.
271  iterator insert_unique(const std::pair<K,T> &ipair);
272  // This is equivalent to insert_equal.
273  iterator insert(const std::pair<K,T> &ipair) { return insert_equal(ipair); }
274  // This is equivalent to insert_equal with a hint.
275  iterator insert(const iterator &hint, const std::pair<K,T> &ipair) { return insert_equal(hint, ipair); }
276 
277  // Insert elements in the given range.
278  void insert(const const_iterator &b, const const_iterator &e) {
279  for (const_iterator i = b; i != e; i++) insert(*i);
280  }
281 
282  void remove(AVLMMapNode<K,T>*);
283  iterator find(const K&);
284  const_iterator find(const K&) const;
285  iterator find(const iterator &hint, const K&);
286  const_iterator find(const const_iterator &hint, const K&) const;
287 
288  void erase(const iterator &i) { remove(i.node); }
289 
290  int height(AVLMMapNode<K,T>* node);
291  int height() { return height(root_); }
292  void check();
293  void check_node(AVLMMapNode<K,T>*) const;
294 
295  AVLMMapNode<K,T>* start() const { return start_; }
296  static void next(const AVLMMapNode<K,T>*&);
297  static void next(AVLMMapNode<K,T>*&);
298 
299  iterator begin() { return iterator(start()); }
300  const_iterator begin() const { return const_iterator(start()); }
301 
302  iterator end() { return iterator(0); }
303  const_iterator end() const { return const_iterator(0); }
304 
305  const_iterator lower_bound(const K& k) const;
306  const_iterator upper_bound(const K& k) const;
307  std::pair<const_iterator,const_iterator> equal_range(const K& k) const;
308 
309  void print(std::ostream &o = std::cout) const;
310  size_t size() const { return length_; }
311  int depth(AVLMMapNode<K,T>*) const;
312 };
313 
314 template <class K, class T, class C, class A>
315 std::pair<typename AVLMMap<K,T,C,A>::const_iterator,
316  typename AVLMMap<K,T,C,A>::const_iterator>
317 AVLMMap<K,T,C,A>::equal_range(const K& __k) const
318 {
319  link_type __lb = 0; /* Last node which is not less than __k. */
320  link_type __ub = 0; /* Last node which is greater than __k. */
321  link_type __x = root_; /* Current node. */
322 
323  while (__x != 0) {
324  int cmp = compare(key(__x), __k);
325  if (cmp == 1) {
326  __lb = __x;
327  __ub = __x;
328  __x = llink(__x);
329  }
330  else if (cmp == -1) {
331  __x = rlink(__x);
332  }
333  else {
334  // behaviours of lower_bound and upper_bound diverge here
335  link_type __saved_x = __x;
336  // find the lowerbound
337  __lb = __x, __x = llink(__x);
338  while (__x != 0)
339  if (!key_comp_(key(__x), __k))
340  __lb = __x, __x = llink(__x);
341  else
342  __x = rlink(__x);
343  // find the upperbound
344  __x = __saved_x;
345  __x = rlink(__x);
346  while (__x != 0)
347  if (key_comp_(__k, key(__x)))
348  __ub = __x, __x = llink(__x);
349  else
350  __x = rlink(__x);
351  }
352  }
353 
354  typedef typename AVLMMap<K,T,C,A>::const_iterator iterator;
355  return std::pair<iterator,iterator>(__lb, __ub);
356 }
357 
358 template <class K, class T, class C, class A>
359 typename AVLMMap<K,T,C,A>::const_iterator
360 AVLMMap<K,T,C,A>::lower_bound(const K& __k) const
361 {
362  // this is the GNU STL RB tree algorithm
363  link_type __y = 0; /* Last node which is not less than __k. */
364  link_type __x = root_; /* Current node. */
365 
366  while (__x != 0)
367  if (!key_comp_(key(__x), __k))
368  __y = __x, __x = llink(__x);
369  else
370  __x = rlink(__x);
371 
372  return const_iterator(__y);
373 }
374 
375 template <class K, class T, class C, class A>
376 typename AVLMMap<K,T,C,A>::const_iterator
377 AVLMMap<K,T,C,A>::upper_bound(const K& __k) const
378 {
379  // this the GNU STL RB tree algorithm
380  link_type __y = 0; /* Last node which is greater than __k. */
381  link_type __x = root_; /* Current node. */
382 
383  while (__x != 0)
384  if (key_comp_(__k, key(__x)))
385  __y = __x, __x = llink(__x);
386  else
387  __x = rlink(__x);
388 
389  return const_iterator(__y);
390 }
391 
392 template <class K, class T, class C, class A>
393 inline typename AVLMMap<K,T,C,A>::iterator
394 AVLMMap<K,T,C,A>::find(const K& k)
395 {
396  return subtree_find_(root_,k);
397 }
398 
399 template <class K, class T, class C, class A>
400 inline typename AVLMMap<K,T,C,A>::const_iterator
401 AVLMMap<K,T,C,A>::find(const K& k) const
402 {
403  return subtree_find_(root_,k);
404 }
405 
406 template <class K, class T, class C, class A>
407 inline typename AVLMMap<K,T,C,A>::iterator
408 AVLMMap<K,T,C,A>::find(const iterator &hint, const K& k)
409 {
410  AVLMMapNode<K,T> *x = hint.node;
411  if (x == 0) return subtree_find_(root_,k);
412  AVLMMapNode<K,T> *y = uplink(x);
413  while (y != 0) {
414  int cmp = compare(k, key(x));
415  if (cmp == 0) return x;
416  int cmp2 = compare(k, key(y));
417  if (cmp2 == 0) return y;
418  if (cmp == -1 && cmp2 == 1) {
419  return subtree_find_(llink(x), k);
420  }
421  else if (cmp == 1 && cmp2 == -1) {
422  return subtree_find_(rlink(x), k);
423  }
424  x = y;
425  cmp = cmp2;
426  y = uplink(x);
427  }
428  return subtree_find_(x,k);
429 }
430 
431 template <class K, class T, class C, class A>
432 inline typename AVLMMap<K,T,C,A>::const_iterator
433 AVLMMap<K,T,C,A>::find(const const_iterator &hint, const K& k) const
434 {
435  const AVLMMapNode<K,T> *x = hint.node;
436  if (x == 0) return subtree_find_(root_,k);
437  const AVLMMapNode<K,T> *y = uplink(x);
438  while (y != 0) {
439  int cmp = compare(k, key(x));
440  if (cmp == 0) return x;
441  int cmp2 = compare(k, key(y));
442  if (cmp2 == 0) return y;
443  if (cmp == -1 && cmp2 == 1) {
444  return subtree_find_(llink(x), k);
445  }
446  else if (cmp == 1 && cmp2 == -1) {
447  return subtree_find_(rlink(x), k);
448  }
449  x = y;
450  cmp = cmp2;
451  y = uplink(x);
452  }
453  return subtree_find_(x,k);
454 }
455 
456 template <class K, class T, class C, class A>
457 typename AVLMMap<K,T,C,A>::iterator
458 AVLMMap<K,T,C,A>::subtree_find_(AVLMMapNode<K,T> *root, const K& k)
459 {
460  AVLMMapNode<K,T>* n = root;
461 
462  while (n) {
463  int cmp = compare(key(n), k);
464  if (cmp < 0) n = rlink(n);
465  else if (cmp > 0) n = llink(n);
466  else return iterator(n);
467  }
468 
469  return iterator(0);
470 }
471 
472 template <class K, class T, class C, class A>
473 typename AVLMMap<K,T,C,A>::const_iterator
474 AVLMMap<K,T,C,A>::subtree_find_(const AVLMMapNode<K,T> *root, const K& k) const
475 {
476  const AVLMMapNode<K,T>* n = root;
477 
478  while (n) {
479  int cmp = compare(key(n), k);
480  if (cmp < 0) n = rlink(n);
481  else if (cmp > 0) n = llink(n);
482  else return const_iterator(n);
483  }
484 
485  return const_iterator(0);
486 }
487 
488 template <class K, class T, class C, class A>
489 void
490 AVLMMap<K,T,C,A>::remove(AVLMMapNode<K,T>* node)
491 {
492  if (!node) return;
493 
494  length_--;
495 
496  if (node == start_) {
497  next(start_);
498  }
499 
500  AVLMMapNode<K,T> *rebalance_point;
501  AVLMMapNode<K,T> *q;
502 
503  if (llink(node) == 0) {
504  q = rlink(node);
505  rebalance_point = uplink(node);
506 
507  if (q) uplink(q) = rebalance_point;
508 
509  if (rebalance_point) {
510  if (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
511  else llink(rebalance_point) = q;
512  }
513  else root_ = q;
514  }
515  else if (rlink(node) == 0) {
516  q = llink(node);
517  rebalance_point = uplink(node);
518 
519  if (q) uplink(q) = rebalance_point;
520 
521  if (rebalance_point) {
522  if (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
523  else llink(rebalance_point) = q;
524  }
525  else root_ = q;
526  }
527  else {
528  AVLMMapNode<K,T> *r = node;
529  next(r);
530 
531  if (r == 0 || llink(r) != 0) {
532  throw std::runtime_error("AVLMMap::remove: inconsistency");
533  }
534 
535  if (r == rlink(node)) {
536  llink(r) = llink(node);
537  if (llink(r)) uplink(llink(r)) = r;
538  balance(r) = balance(node);
539  rebalance_point = r;
540  q = rlink(r);
541  }
542  else {
543  q = rlink(r);
544 
545  rebalance_point = uplink(r);
546 
547  if (llink(rebalance_point) == r) llink(rebalance_point) = q;
548  else rlink(rebalance_point) = q;
549 
550  if (q) uplink(q) = rebalance_point;
551 
552  balance(r) = balance(node);
553  rlink(r) = rlink(node);
554  llink(r) = llink(node);
555  if (rlink(r)) uplink(rlink(r)) = r;
556  if (llink(r)) uplink(llink(r)) = r;
557  }
558  if (r) {
559  AVLMMapNode<K,T>* up = uplink(node);
560  uplink(r) = up;
561  if (up) {
562  if (rlink(up) == node) rlink(up) = r;
563  else llink(up) = r;
564  }
565  if (up == 0) root_ = r;
566  }
567  }
568 
569  // adjust balance won't work if both children are null,
570  // so handle this special case here
571  if (rebalance_point &&
572  llink(rebalance_point) == 0 && rlink(rebalance_point) == 0) {
573  balance(rebalance_point) = 0;
574  q = rebalance_point;
575  rebalance_point = uplink(rebalance_point);
576  }
577  adjust_balance_remove(rebalance_point, q);
578 
579  alloc_.destroy(node);
580  alloc_.deallocate(node,1);
581 }
582 
583 template <class K, class T, class C, class A>
584 void
585 AVLMMap<K,T,C,A>::print(std::ostream &o) const
586 {
587  std::cout << "--------------------------" << std::endl;
588  for (AVLMMapNode<K,T>*n=start(); n; next(n)) {
589  int d = depth(n) + 1;
590  for (int i=0; i<d; i++) o << " ";
591  if (balance(n) == 1) o << " (+) " << key(n) << std::endl;
592  else if (balance(n) == -1) o << " (-) " << key(n) << std::endl;
593  else if (balance(n) == 0) o << " (.) " << key(n) << std::endl;
594  else o << " (" << balance(n) << ") " << key(n) << std::endl;
595  }
596 }
597 
598 template <class K, class T, class C, class A>
599 int
600 AVLMMap<K,T,C,A>::depth(AVLMMapNode<K,T>*node) const
601 {
602  int d = 0;
603  while (node) {
604  node = uplink(node);
605  d++;
606  }
607  return d;
608 }
609 
610 template <class K, class T, class C, class A>
611 void
612 AVLMMap<K,T,C,A>::check_node(AVLMMapNode<K,T>*n) const
613 {
614  if (uplink(n) && uplink(n) == n) abort();
615  if (llink(n) && llink(n) == n) abort();
616  if (rlink(n) && rlink(n) == n) abort();
617  if (rlink(n) && rlink(n) == llink(n)) abort();
618  if (uplink(n) && uplink(n) == llink(n)) abort();
619  if (uplink(n) && uplink(n) == rlink(n)) abort();
620  if (uplink(n) && !(llink(uplink(n)) == n
621  || rlink(uplink(n)) == n)) abort();
622 }
623 
624 template <class K, class T, class C, class A>
625 void
626 AVLMMap<K,T,C,A>::clear(AVLMMapNode<K,T>*n)
627 {
628  if (!n) return;
629  clear(llink(n));
630  clear(rlink(n));
631  alloc_.destroy(n);
632  alloc_.deallocate(n,1);
633 }
634 
635 template <class K, class T, class C, class A>
636 int
637 AVLMMap<K,T,C,A>::height(AVLMMapNode<K,T>* node)
638 {
639  if (!node) return 0;
640  int rh = height(rlink(node)) + 1;
641  int lh = height(llink(node)) + 1;
642  return rh>lh?rh:lh;
643 }
644 
645 template <class K, class T, class C, class A>
646 void
647 AVLMMap<K,T,C,A>::check()
648 {
649  AVLMMapNode<K,T>* node;
650  AVLMMapNode<K,T>* prev=0;
651  size_t computed_length = 0;
652  for (node = start(); node; next(node)) {
653  check_node(node);
654  if (prev && compare(key(prev),key(node)) > 0) {
655  throw std::runtime_error("nodes out of order");
656  }
657  prev = node;
658  computed_length++;
659  }
660  for (node = start(); node; next(node)) {
661  if (balance(node) != height(rlink(node)) - height(llink(node))) {
662  throw std::runtime_error("balance inconsistency");
663  }
664  if (balance(node) < -1 || balance(node) > 1) {
665  throw std::runtime_error("balance out of range");
666  }
667  }
668  if (length_ != computed_length) {
669  throw std::runtime_error("length error");
670  }
671 }
672 
673 template <class K, class T, class C, class A>
674 void
675 AVLMMap<K,T,C,A>::next(const AVLMMapNode<K,T>*& node)
676 {
677  const AVLMMapNode<K,T>* r;
678  if ((r = rlink(node))) {
679  node = r;
680  while ((r = llink(node))) node = r;
681  return;
682  }
683  while ((r = uplink(node))) {
684  if (node == llink(r)) {
685  node = r;
686  return;
687  }
688  node = r;
689  }
690  node = 0;
691 }
692 
693 template <class K, class T, class C, class A>
694 void
695 AVLMMap<K,T,C,A>::next(AVLMMapNode<K,T>*& node)
696 {
697  AVLMMapNode<K,T>* r;
698  if ((r = rlink(node))) {
699  node = r;
700  while ((r = llink(node))) node = r;
701  return;
702  }
703  while ((r = uplink(node))) {
704  if (node == llink(r)) {
705  node = r;
706  return;
707  }
708  node = r;
709  }
710  node = 0;
711 }
712 
713 template <class K, class T, class C, class A>
714 typename AVLMMap<K,T,C,A>::iterator
715 AVLMMap<K,T,C,A>::insert_equal(const iterator &hint, const std::pair<K,T> &ipair)
716 {
717  AVLMMapNode<K,T>* n = alloc_.allocate(1);
718  new((void*)n)AVLMMapNode<K,T>(ipair);
719 
720  llink(n) = 0;
721  rlink(n) = 0;
722  balance(n) = 0;
723 
724  AVLMMapNode<K,T> *x = hint.node;
725  if (x == 0) return subtree_insert_equal_(root_,n);
726  AVLMMapNode<K,T> *y = uplink(x);
727  while (y != 0) {
728  int cmp = compare(key(n), key(x));
729  if (cmp == 0) return subtree_insert_equal_(x, n);
730  int cmp2 = compare(key(n), key(y));
731  if (cmp2 == 0) return subtree_insert_equal_(y, n);
732  if (cmp == -1 && cmp2 == 1) {
733  y = llink(x);
734  if (y != 0) return subtree_insert_equal_(y, n);
735  else {
736  uplink(n) = x;
737  llink(x) = n;
738  adjust_balance_insert(x,n);
739  return iterator(n);
740  }
741  }
742  else if (cmp == 1 && cmp2 == -1) {
743  y = rlink(x);
744  if (y != 0) return subtree_insert_equal_(y, n);
745  else {
746  uplink(n) = x;
747  rlink(x) = n;
748  adjust_balance_insert(x,n);
749  return iterator(n);
750  }
751  }
752  x = y;
753  cmp = cmp2;
754  y = uplink(x);
755  }
756  return subtree_insert_equal_(x, n);
757 }
758 
759 template <class K, class T, class C, class A>
760 typename AVLMMap<K,T,C,A>::iterator
761 AVLMMap<K,T,C,A>::insert_new(const iterator &hint, const std::pair<K,T> &ipair)
762 {
763  AVLMMapNode<K,T>* n = alloc_.allocate(1);
764  new((void*)n)AVLMMapNode<K,T>(ipair);
765 
766  llink(n) = 0;
767  rlink(n) = 0;
768  balance(n) = 0;
769 
770  AVLMMapNode<K,T> *x = hint.node;
771  if (x == 0) return subtree_insert_new_(root_,n);
772  AVLMMapNode<K,T> *y = uplink(x);
773  while (y != 0) {
774  bool cmp = key_comp_(key(n), key(x));
775  bool cmp2 = key_comp_(key(n), key(y));
776  if (cmp && !cmp2) {
777  y = llink(x);
778  if (y != 0) return subtree_insert_new_(y, n);
779  else {
780  uplink(n) = x;
781  llink(x) = n;
782  adjust_balance_insert(x,n);
783  return iterator(n);
784  }
785  }
786  else if (!cmp && cmp2) {
787  y = rlink(x);
788  if (y != 0) return subtree_insert_new_(y, n);
789  else {
790  uplink(n) = x;
791  rlink(x) = n;
792  adjust_balance_insert(x,n);
793  return iterator(n);
794  }
795  }
796  x = y;
797  cmp = cmp2;
798  y = uplink(x);
799  }
800  return subtree_insert_new_(x, n);
801 }
802 
803 template <class K, class T, class C, class A>
804 inline typename AVLMMap<K,T,C,A>::iterator
805 AVLMMap<K,T,C,A>::insert_equal(const std::pair<K,T> &ipair)
806 {
807  AVLMMapNode<K,T>* n = alloc_.allocate(1);
808  new((void*)n)AVLMMapNode<K,T>(ipair);
809 
810  return subtree_insert_equal_(root_, n);
811 }
812 
813 template <class K, class T, class C, class A>
814 inline typename AVLMMap<K,T,C,A>::iterator
815 AVLMMap<K,T,C,A>::insert_unique(const std::pair<K,T> &ipair)
816 {
817  return subtree_insert_unique_(root_, ipair);
818 }
819 
820 template <class K, class T, class C, class A>
821 inline typename AVLMMap<K,T,C,A>::iterator
822 AVLMMap<K,T,C,A>::insert_new(const std::pair<K,T> &ipair)
823 {
824  AVLMMapNode<K,T>* n = alloc_.allocate(1);
825  new((void*)n)AVLMMapNode<K,T>(ipair);
826 
827  length_++;
828 
829  rlink(n) = 0;
830  llink(n) = 0;
831  balance(n) = 0;
832 
833  return subtree_insert_new_(root_, n);
834 }
835 
836 template <class K, class T, class C, class A>
837 typename AVLMMap<K,T,C,A>::iterator
838 AVLMMap<K,T,C,A>::subtree_insert_equal_(AVLMMapNode<K,T> *root,
839  AVLMMapNode<K,T> *n)
840 {
841  length_++;
842 
843  rlink(n) = 0;
844  llink(n) = 0;
845  balance(n) = 0;
846 
847  // root is only null if the actual root is null
848  if (!root) {
849  uplink(n) = 0;
850  root_ = n;
851  start_ = n;
852  return iterator(n);
853  }
854 
855  // find an insertion point
856  AVLMMapNode<K,T>* p = root;
857  AVLMMapNode<K,T>* prev_p = 0;
858  int cmp;
859  while (p) {
860  if (p == n) {
861  abort();
862  }
863  prev_p = p;
864  cmp = compare(key(n),key(p));
865  if (cmp < 0) p = llink(p);
866  else {
867  p = rlink(p);
868  }
869  }
870 
871  // insert the node
872  uplink(n) = prev_p;
873  if (prev_p) {
874  if (cmp < 0) {
875  llink(prev_p) = n;
876  if (prev_p == start_) start_ = n;
877  }
878  else rlink(prev_p) = n;
879  }
880 
881  // adjust the balance factors
882  if (prev_p) {
883  adjust_balance_insert(prev_p, n);
884  }
885 
886  return iterator(n);
887 }
888 
889 template <class K, class T, class C, class A>
890 typename AVLMMap<K,T,C,A>::iterator
891 AVLMMap<K,T,C,A>::subtree_insert_unique_(AVLMMapNode<K,T> *root,
892  const std::pair<K,T> &ipair)
893 {
894  // root is only null if the actual root is null
895  if (!root) {
896  AVLMMapNode<K,T>* n = alloc_.allocate(1);
897  new((void*)n)AVLMMapNode<K,T>(ipair);
898 
899  length_++;
900 
901  rlink(n) = 0;
902  llink(n) = 0;
903  balance(n) = 0;
904  uplink(n) = 0;
905  root_ = n;
906  start_ = n;
907  return iterator(n);
908  }
909 
910  // find an insertion point
911  AVLMMapNode<K,T>* p = root;
912  AVLMMapNode<K,T>* prev_p = 0;
913  int cmp;
914  while (p) {
915  prev_p = p;
916  cmp = compare(ipair.first,key(p));
917  if (cmp < 0) p = llink(p);
918  else if (cmp == 0) {
919  return iterator(p);
920  }
921  else {
922  p = rlink(p);
923  }
924  }
925 
926  // no match was found; create the node
927  AVLMMapNode<K,T>* n = alloc_.allocate(1);
928  new((void*)n)AVLMMapNode<K,T>(ipair);
929 
930  length_++;
931 
932  rlink(n) = 0;
933  llink(n) = 0;
934  balance(n) = 0;
935 
936  // insert the node
937  uplink(n) = prev_p;
938  if (prev_p) {
939  if (cmp < 0) {
940  llink(prev_p) = n;
941  if (prev_p == start_) start_ = n;
942  }
943  else rlink(prev_p) = n;
944  }
945 
946  // adjust the balance factors
947  if (prev_p) {
948  adjust_balance_insert(prev_p, n);
949  }
950 
951  return iterator(n);
952 }
953 
954 template <class K, class T, class C, class A>
955 typename AVLMMap<K,T,C,A>::iterator
956 AVLMMap<K,T,C,A>::subtree_insert_new_(AVLMMapNode<K,T> *root,
957  AVLMMapNode<K,T> *n)
958 {
959  // root is only null if the actual root is null
960  if (!root) {
961  uplink(n) = 0;
962  root_ = n;
963  start_ = n;
964  return iterator(n);
965  }
966 
967  // find an insertion point
968  AVLMMapNode<K,T>* p = root;
969  AVLMMapNode<K,T>* prev_p = 0;
970  bool cmp;
971  while (p) {
972  prev_p = p;
973  cmp = key_comp_(key(n),key(p));
974  if (cmp) p = llink(p);
975  else {
976  p = rlink(p);
977  }
978  }
979 
980  // insert the node
981  uplink(n) = prev_p;
982  if (prev_p) {
983  if (cmp) {
984  llink(prev_p) = n;
985  if (prev_p == start_) start_ = n;
986  }
987  else rlink(prev_p) = n;
988  }
989 
990  // adjust the balance factors
991  if (prev_p) {
992  adjust_balance_insert(prev_p, n);
993  }
994 
995  return iterator(n);
996 }
997 
998 template <class K, class T, class C, class Alloc>
999 void
1000 AVLMMap<K,T,C,Alloc>::adjust_balance_insert(AVLMMapNode<K,T>* A, AVLMMapNode<K,T>* child)
1001 {
1002  if (!A) return;
1003  int adjustment;
1004  if (llink(A) == child) adjustment = -1;
1005  else adjustment = 1;
1006  int bal = balance(A) + adjustment;
1007  if (bal == 0) {
1008  balance(A) = 0;
1009  }
1010  else if (bal == -1 || bal == 1) {
1011  balance(A) = bal;
1012  adjust_balance_insert(uplink(A), A);
1013  }
1014  else if (bal == 2) {
1015  AVLMMapNode<K,T>* B = rlink(A);
1016  if (balance(B) == 1) {
1017  balance(B) = 0;
1018  balance(A) = 0;
1019  rlink(A) = llink(B);
1020  llink(B) = A;
1021  uplink(B) = uplink(A);
1022  uplink(A) = B;
1023  if (rlink(A)) uplink(rlink(A)) = A;
1024  if (llink(B)) uplink(llink(B)) = B;
1025  if (uplink(B) == 0) root_ = B;
1026  else {
1027  if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
1028  else llink(uplink(B)) = B;
1029  }
1030  }
1031  else {
1032  AVLMMapNode<K,T>* X = llink(B);
1033  rlink(A) = llink(X);
1034  llink(B) = rlink(X);
1035  llink(X) = A;
1036  rlink(X) = B;
1037  if (balance(X) == 1) {
1038  balance(A) = -1;
1039  balance(B) = 0;
1040  }
1041  else if (balance(X) == -1) {
1042  balance(A) = 0;
1043  balance(B) = 1;
1044  }
1045  else {
1046  balance(A) = 0;
1047  balance(B) = 0;
1048  }
1049  balance(X) = 0;
1050  uplink(X) = uplink(A);
1051  uplink(A) = X;
1052  uplink(B) = X;
1053  if (rlink(A)) uplink(rlink(A)) = A;
1054  if (llink(B)) uplink(llink(B)) = B;
1055  if (uplink(X) == 0) root_ = X;
1056  else {
1057  if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
1058  else llink(uplink(X)) = X;
1059  }
1060  }
1061  }
1062  else if (bal == -2) {
1063  AVLMMapNode<K,T>* B = llink(A);
1064  if (balance(B) == -1) {
1065  balance(B) = 0;
1066  balance(A) = 0;
1067  llink(A) = rlink(B);
1068  rlink(B) = A;
1069  uplink(B) = uplink(A);
1070  uplink(A) = B;
1071  if (llink(A)) uplink(llink(A)) = A;
1072  if (rlink(B)) uplink(rlink(B)) = B;
1073  if (uplink(B) == 0) root_ = B;
1074  else {
1075  if (llink(uplink(B)) == A) llink(uplink(B)) = B;
1076  else rlink(uplink(B)) = B;
1077  }
1078  }
1079  else {
1080  AVLMMapNode<K,T>* X = rlink(B);
1081  llink(A) = rlink(X);
1082  rlink(B) = llink(X);
1083  rlink(X) = A;
1084  llink(X) = B;
1085  if (balance(X) == -1) {
1086  balance(A) = 1;
1087  balance(B) = 0;
1088  }
1089  else if (balance(X) == 1) {
1090  balance(A) = 0;
1091  balance(B) = -1;
1092  }
1093  else {
1094  balance(A) = 0;
1095  balance(B) = 0;
1096  }
1097  balance(X) = 0;
1098  uplink(X) = uplink(A);
1099  uplink(A) = X;
1100  uplink(B) = X;
1101  if (llink(A)) uplink(llink(A)) = A;
1102  if (rlink(B)) uplink(rlink(B)) = B;
1103  if (uplink(X) == 0) root_ = X;
1104  else {
1105  if (llink(uplink(X)) == A) llink(uplink(X)) = X;
1106  else rlink(uplink(X)) = X;
1107  }
1108  }
1109  }
1110 }
1111 
1112 template <class K, class T, class C, class Alloc>
1113 void
1114 AVLMMap<K,T,C,Alloc>::adjust_balance_remove(AVLMMapNode<K,T>* A, AVLMMapNode<K,T>* child)
1115 {
1116  if (!A) return;
1117  int adjustment;
1118  if (llink(A) == child) adjustment = 1;
1119  else adjustment = -1;
1120  int bal = balance(A) + adjustment;
1121  if (bal == 0) {
1122  balance(A) = 0;
1123  adjust_balance_remove(uplink(A), A);
1124  }
1125  else if (bal == -1 || bal == 1) {
1126  balance(A) = bal;
1127  }
1128  else if (bal == 2) {
1129  AVLMMapNode<K,T>* B = rlink(A);
1130  if (balance(B) == 0) {
1131  balance(B) = -1;
1132  balance(A) = 1;
1133  rlink(A) = llink(B);
1134  llink(B) = A;
1135  uplink(B) = uplink(A);
1136  uplink(A) = B;
1137  if (rlink(A)) uplink(rlink(A)) = A;
1138  if (llink(B)) uplink(llink(B)) = B;
1139  if (uplink(B) == 0) root_ = B;
1140  else {
1141  if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
1142  else llink(uplink(B)) = B;
1143  }
1144  }
1145  else if (balance(B) == 1) {
1146  balance(B) = 0;
1147  balance(A) = 0;
1148  rlink(A) = llink(B);
1149  llink(B) = A;
1150  uplink(B) = uplink(A);
1151  uplink(A) = B;
1152  if (rlink(A)) uplink(rlink(A)) = A;
1153  if (llink(B)) uplink(llink(B)) = B;
1154  if (uplink(B) == 0) root_ = B;
1155  else {
1156  if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
1157  else llink(uplink(B)) = B;
1158  }
1159  adjust_balance_remove(uplink(B), B);
1160  }
1161  else {
1162  AVLMMapNode<K,T>* X = llink(B);
1163  rlink(A) = llink(X);
1164  llink(B) = rlink(X);
1165  llink(X) = A;
1166  rlink(X) = B;
1167  if (balance(X) == 0) {
1168  balance(A) = 0;
1169  balance(B) = 0;
1170  }
1171  else if (balance(X) == 1) {
1172  balance(A) = -1;
1173  balance(B) = 0;
1174  }
1175  else {
1176  balance(A) = 0;
1177  balance(B) = 1;
1178  }
1179  balance(X) = 0;
1180  uplink(X) = uplink(A);
1181  uplink(A) = X;
1182  uplink(B) = X;
1183  if (rlink(A)) uplink(rlink(A)) = A;
1184  if (llink(B)) uplink(llink(B)) = B;
1185  if (uplink(X) == 0) root_ = X;
1186  else {
1187  if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
1188  else llink(uplink(X)) = X;
1189  }
1190  adjust_balance_remove(uplink(X), X);
1191  }
1192  }
1193  else if (bal == -2) {
1194  AVLMMapNode<K,T>* B = llink(A);
1195  if (balance(B) == 0) {
1196  balance(B) = 1;
1197  balance(A) = -1;
1198  llink(A) = rlink(B);
1199  rlink(B) = A;
1200  uplink(B) = uplink(A);
1201  uplink(A) = B;
1202  if (llink(A)) uplink(llink(A)) = A;
1203  if (rlink(B)) uplink(rlink(B)) = B;
1204  if (uplink(B) == 0) root_ = B;
1205  else {
1206  if (llink(uplink(B)) == A) llink(uplink(B)) = B;
1207  else rlink(uplink(B)) = B;
1208  }
1209  }
1210  else if (balance(B) == -1) {
1211  balance(B) = 0;
1212  balance(A) = 0;
1213  llink(A) = rlink(B);
1214  rlink(B) = A;
1215  uplink(B) = uplink(A);
1216  uplink(A) = B;
1217  if (llink(A)) uplink(llink(A)) = A;
1218  if (rlink(B)) uplink(rlink(B)) = B;
1219  if (uplink(B) == 0) root_ = B;
1220  else {
1221  if (llink(uplink(B)) == A) llink(uplink(B)) = B;
1222  else rlink(uplink(B)) = B;
1223  }
1224  adjust_balance_remove(uplink(B), B);
1225  }
1226  else {
1227  AVLMMapNode<K,T>* X = rlink(B);
1228  llink(A) = rlink(X);
1229  rlink(B) = llink(X);
1230  rlink(X) = A;
1231  llink(X) = B;
1232  if (balance(X) == 0) {
1233  balance(A) = 0;
1234  balance(B) = 0;
1235  }
1236  else if (balance(X) == -1) {
1237  balance(A) = 1;
1238  balance(B) = 0;
1239  }
1240  else {
1241  balance(A) = 0;
1242  balance(B) = -1;
1243  }
1244  balance(X) = 0;
1245  uplink(X) = uplink(A);
1246  uplink(A) = X;
1247  uplink(B) = X;
1248  if (llink(A)) uplink(llink(A)) = A;
1249  if (rlink(B)) uplink(rlink(B)) = B;
1250  if (uplink(X) == 0) root_ = X;
1251  else {
1252  if (llink(uplink(X)) == A) llink(uplink(X)) = X;
1253  else rlink(uplink(X)) = X;
1254  }
1255  adjust_balance_remove(uplink(X), X);
1256  }
1257  }
1258 }
1259 
1260 template <class K, class T, class C, class A>
1261 inline
1262 AVLMMap<K,T,C,A>::AVLMMap()
1263 {
1264  initialize();
1265 }
1266 
1267 template <class K, class T, class C, class A>
1268 inline
1269 AVLMMap<K,T,C,A>::AVLMMap(const C &c):
1270  key_comp_(c)
1271 {
1272  initialize();
1273 }
1274 
1275 template <class K, class T, class C, class A>
1276 inline
1277 AVLMMap<K,T,C,A>::AVLMMap(const AVLMMap<K,T,C,A>&m)
1278 {
1279  initialize();
1280  insert(m.begin(), m.end());
1281 }
1282 
1283 template <class K, class T, class C, class A>
1284 inline void
1285 AVLMMap<K,T,C,A>::initialize()
1286 {
1287  root_ = 0;
1288  start_ = 0;
1289  length_ = 0;
1290 }
1291 
1292 }
1293 
1294 #endif
1295 
1296 // ///////////////////////////////////////////////////////////////////////////
1297 
1298 // Local Variables:
1299 // mode: c++
1300 // c-file-style: "CLJ"
1301 // End:
sc::AVLMMap::iterator
Definition: avlmmap.h:187
sc::tristate_less
Definition: avlmmap.h:140
sc::operator!=
bool operator!=(const Atom &a, const Atom &b)
Definition: atom.h:170
sc::AVLMMap::const_iterator
Definition: avlmmap.h:206
sc::AVLMMapNode
Definition: avlmmap.h:42
sc::AVLMMap
Definition: avlmmap.h:155
sc::operator==
bool operator==(const Atom &a, const Atom &b)
sc
Contains all MPQC code up to version 3.
Definition: mpqcin.h:14
sc::chunk_allocator
Definition: avlmmap.h:59
Generated at Sun Jan 26 2020 23:23:58 for MPQC 3.0.0-alpha using the documentation package Doxygen 1.8.16.