# avlmap.h

    00001 //
    00002 // avlmap.h --- definition for avl map class
    00003 //
    00004 // Copyright (C) 1998 Limit Point Systems, Inc.
    00005 //
    00006 // Author: Curtis Janssen <cljanss@limitpt.com>
    00007 // Maintainer: LPS
    00008 //
    00009 // This file is part of the SC Toolkit.
    00010 //
    00011 // The SC Toolkit is free software; you can redistribute it and/or modify
    00012 // it under the terms of the GNU Library General Public License as published by
    00013 // the Free Software Foundation; either version 2, or (at your option)
    00014 // any later version.
    00015 //
    00016 // The SC Toolkit is distributed in the hope that it will be useful,
    00017 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00018 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00019 // GNU Library General Public License for more details.
    00020 //
    00021 // You should have received a copy of the GNU Library General Public License
    00022 // along with the SC Toolkit; see the file COPYING.LIB.  If not, write to
    00023 // the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
    00024 //
    00025 // The U.S. Government is granted a limited license as per AL 91-7.
    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 // Local Variables:
    00135 // mode: c++
    00136 // c-file-style: "CLJ"
    00137 // End: