MPQC  3.0.0-alpha
avlmap.h
1 //
2 // avlmap.h --- definition for avl map class
3 //
4 // Copyright (C) 1998 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_avlmap_h
29 #define _util_container_avlmap_h
30 
31 #include <util/container/eavlmmap.h>
32 
33 namespace sc {
34 
35 template <class K, class T>
36 class AVLMapNode {
37  public:
38  T data;
40  public:
41  AVLMapNode(const K& k, const T& d): data(d), node(k) {};
42 };
43 
44 template <class K, class T>
45 class AVLMap {
46  public:
48  public:
49  class iterator {
50  private:
51  const EAVLMMap<K, AVLMapNode<K,T> > *map_;
52  AVLMapNode<K, T> *node;
53  public:
54  iterator(): map_(0), node(0) {}
55  iterator(const EAVLMMap<K,AVLMapNode<K,T> > *m,
56  AVLMapNode<K,T> *n)
57  :map_(m), node(n) {}
58  iterator(const eavl_typename AVLMap<K,T>::iterator &i) { map_=i.map_; node=i.node; }
59  void operator++() { map_->next(node); }
60  void operator++(int) { operator++(); }
61  int operator == (const eavl_typename AVLMap<K,T>::iterator &i) const
62  { return map_ == i.map_ && node == i.node; }
63  int operator != (const eavl_typename AVLMap<K,T>::iterator &i) const
64  { return !operator == (i); }
65  void operator = (const eavl_typename AVLMap<K,T>::iterator &i)
66  { map_ = i.map_; node = i.node; }
67  const K &key() const { return node->node.key; }
68  T &data() { return node->data; }
69  };
70  public:
71  AVLMap(): map_(&AVLMapNode<K,T>::node) {};
72  void clear() { map_.clear(); }
73  void insert(const K& key, const T& data);
74  void remove(const K& key);
75  int contains(const K& k) const { return map_.find(k) != 0; }
76  iterator find(const K&) const;
77  T &operator[](const K &k);
78 
79  int height() { return map_.height(); }
80  void check() { map_.check(); }
81 
82  int length() const { return map_.length(); }
83 
84  iterator begin() const { return iterator(&map_,map_.start()); }
85  iterator end() const { return iterator(&map_,0); }
86 
87  void print() { map_.print(); }
88 };
89 
90 template <class K, class T>
91 inline void
92 AVLMap<K,T>::insert(const K& key, const T& data)
93 {
94  AVLMapNode<K,T> *node = map_.find(key);
95  if (node) node->data = data;
96  else map_.insert(new AVLMapNode<K, T>(key,data));
97 }
98 
99 template <class K, class T>
100 inline void
101 AVLMap<K,T>::remove(const K& key)
102 {
103  AVLMapNode<K, T> *node = map_.find(key);
104  if (node) {
105  map_.remove(node);
106  delete node;
107  }
108 }
109 
110 template <class K, class T>
111 inline typename AVLMap<K,T>::iterator
112 AVLMap<K,T>::find(const K& k) const
113 {
114  return iterator(&map_,map_.find(k));
115 }
116 
117 template <class K, class T>
118 inline T&
119 AVLMap<K,T>::operator [](const K& k)
120 {
121  AVLMapNode<K, T> *node = map_.find(k);
122  if (node) return node->data;
123  insert(k,T());
124  node = map_.find(k);
125  return node->data;
126 }
127 
128 }
129 
130 #endif
131 
132 // /////////////////////////////////////////////////////////////////////////
133 
134 // Local Variables:
135 // mode: c++
136 // c-file-style: "CLJ"
137 // End:
sc::EAVLMMap
Definition: eavlmmap.h:62
sc::EAVLMMapNode
Definition: eavlmmap.h:50
sc::AVLMap
Definition: avlmap.h:45
sc::AVLMap::iterator
Definition: avlmap.h:49
sc::AVLMapNode
Definition: avlmap.h:36
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.