00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #ifndef _util_container_avlmap_h
00029 #define _util_container_avlmap_h
00030
00031 #include <util/container/eavlmmap.h>
00032
00033 namespace sc {
00034
00035 template <class K, class T>
00036 class AVLMapNode {
00037 public:
00038 T data;
00039 EAVLMMapNode<K,AVLMapNode<K, T> > node;
00040 public:
00041 AVLMapNode(const K& k, const T& d): data(d), node(k) {};
00042 };
00043
00044 template <class K, class T>
00045 class AVLMap {
00046 public:
00047 EAVLMMap<K, AVLMapNode<K,T> > map_;
00048 public:
00049 class iterator {
00050 private:
00051 const EAVLMMap<K, AVLMapNode<K,T> > *map_;
00052 AVLMapNode<K, T> *node;
00053 public:
00054 iterator(): map_(0), node(0) {}
00055 iterator(const EAVLMMap<K,AVLMapNode<K,T> > *m,
00056 AVLMapNode<K,T> *n)
00057 :map_(m), node(n) {}
00058 iterator(const eavl_typename AVLMap<K,T>::iterator &i) { map_=i.map_; node=i.node; }
00059 void operator++() { map_->next(node); }
00060 void operator++(int) { operator++(); }
00061 int operator == (const eavl_typename AVLMap<K,T>::iterator &i) const
00062 { return map_ == i.map_ && node == i.node; }
00063 int operator != (const eavl_typename AVLMap<K,T>::iterator &i) const
00064 { return !operator == (i); }
00065 void operator = (const eavl_typename AVLMap<K,T>::iterator &i)
00066 { map_ = i.map_; node = i.node; }
00067 const K &key() const { return node->node.key; }
00068 T &data() { return node->data; }
00069 };
00070 public:
00071 AVLMap(): map_(&AVLMapNode<K,T>::node) {};
00072 void clear() { map_.clear(); }
00073 void insert(const K& key, const T& data);
00074 void remove(const K& key);
00075 int contains(const K& k) const { return map_.find(k) != 0; }
00076 iterator find(const K&) const;
00077 T &operator[](const K &k);
00078
00079 int height() { return map_.height(); }
00080 void check() { map_.check(); }
00081
00082 int length() const { return map_.length(); }
00083
00084 iterator begin() const { return iterator(&map_,map_.start()); }
00085 iterator end() const { return iterator(&map_,0); }
00086
00087 void print() { map_.print(); }
00088 };
00089
00090 template <class K, class T>
00091 inline void
00092 AVLMap<K,T>::insert(const K& key, const T& data)
00093 {
00094 AVLMapNode<K,T> *node = map_.find(key);
00095 if (node) node->data = data;
00096 else map_.insert(new AVLMapNode<K, T>(key,data));
00097 }
00098
00099 template <class K, class T>
00100 inline void
00101 AVLMap<K,T>::remove(const K& key)
00102 {
00103 AVLMapNode<K, T> *node = map_.find(key);
00104 if (node) {
00105 map_.remove(node);
00106 delete node;
00107 }
00108 }
00109
00110 template <class K, class T>
00111 inline typename AVLMap<K,T>::iterator
00112 AVLMap<K,T>::find(const K& k) const
00113 {
00114 return iterator(&map_,map_.find(k));
00115 }
00116
00117 template <class K, class T>
00118 inline T&
00119 AVLMap<K,T>::operator [](const K& k)
00120 {
00121 AVLMapNode<K, T> *node = map_.find(k);
00122 if (node) return node->data;
00123 insert(k,T());
00124 node = map_.find(k);
00125 return node->data;
00126 }
00127
00128 }
00129
00130 #endif
00131
00132
00133
00134
00135
00136
00137