MPQC 2.3.1

- Main Page
- Related Pages
- Classes
- Files

- File List

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;
39 EAVLMMapNode<K,AVLMapNode<K, T> > node;
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:
47 EAVLMMap<K, AVLMapNode<K,T> > map_;
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: