MPQC 2.3.1
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
33namespace sc {
34
35template <class K, class T>
37 public:
38 T data;
40 public:
41 AVLMapNode(const K& k, const T& d): data(d), node(k) {};
42};
43
44template <class K, class T>
45class 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) {}
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
90template <class K, class T>
91inline void
92AVLMap<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
99template <class K, class T>
100inline void
101AVLMap<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
110template <class K, class T>
111inline typename AVLMap<K,T>::iterator
112AVLMap<K,T>::find(const K& k) const
113{
114 return iterator(&map_,map_.find(k));
115}
116
117template <class K, class T>
118inline T&
119AVLMap<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:
Definition: avlmap.h:36
Definition: avlmap.h:49
Definition: avlmap.h:45
Definition: eavlmmap.h:50
Definition: eavlmmap.h:62

Generated at Thu Jan 19 2023 00:00:00 for MPQC 2.3.1 using the documentation package Doxygen 1.9.5.