Main Page Class Hierarchy Compound List File List Compound Members Related Pages

# avlset.h

    00001 //
    00002 // avlset.h --- definition for avl set 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_avlset_h
    00029 #define _util_container_avlset_h
    00030
    00031 #include <util/container/avlmap.h>
    00032
    00033 namespace sc {
    00034
    00035 template <class K>
    00036 class AVLSet {
    00037   private:
    00038     AVLMap<K,int> map_;
    00039   public:
    00040     class iterator {
    00041       private:
    00042         const EAVLMMap<K, AVLMapNode<K,int> > *map_;
    00043         const AVLMapNode<K, int> *node;
    00044       public:
    00045         iterator(): map_(0), node(0) {}
    00046         iterator(const EAVLMMap<K,AVLMapNode<K,int> > *m,
    00047                  const AVLMapNode<K,int> *n)
    00048           :map_(m), node(n) {}
    00049         iterator(const eavl_typename AVLSet<K>::iterator &i):map_(i.map_),node(i.node) {}
    00050         void operator++() { map_->next(node); }
    00051         void operator++(int) { operator++(); }
    00052         int operator == (const eavl_typename AVLSet<K>::iterator &i) const
    00053             { return map_ == i.map_ && node == i.node; }
    00054         int operator != (const eavl_typename AVLSet<K>::iterator &i) const
    00055             { return !(map_ == i.map_ && node == i.node); }
    00056         void operator = (const eavl_typename AVLSet<K>::iterator &i)
    00057             { map_ = i.map_; node = i.node; }
    00058         const K &key() const { return node->node.key; }
    00059         const K &operator *() const { return node->node.key; }
    00060         //const K *operator ->() const { return &node->node.key; }
    00061     };
    00062   public:
    00063     AVLSet() {};
    00064     void clear() { map_.clear(); }
    00065     void insert(const K& key) { map_.insert(key,0); }
    00066     void remove(const K& key) { map_.remove(key); }
    00067     int contains(const K& key) const { return map_.contains(key); }
    00068     iterator find(const K& k) const;
    00069
    00070     int height() { return map_.height(); }
    00071     void check() { map_.check(); }
    00072
    00073     int length() const { return map_.length(); }
    00074
    00075     iterator begin() const { return iterator(&map_.map_,map_.map_.start()); }
    00076     iterator end() const { return iterator(&map_.map_,0); }
    00077
    00078     void operator -= (const AVLSet<K> &s);
    00079     void operator |= (const AVLSet<K> &s);
    00080
    00081     void print() { map_.print(); }
    00082 };
    00083
    00084 template <class K>
    00085 void
    00086 AVLSet<K>::operator -= (const AVLSet<K> &s)
    00087 {
    00088   for (typename AVLSet<K>::iterator i=s.begin(); i!=s.end(); i++) {
    00089       remove(*i);
    00090     }
    00091 }
    00092
    00093 template <class K>
    00094 void
    00095 AVLSet<K>::operator |= (const AVLSet<K> &s)
    00096 {
    00097   for (typename AVLSet<K>::iterator i=s.begin(); i!=s.end(); i++) {
    00098       insert(*i);
    00099     }
    00100 }
    00101
    00102 template <class K>
    00103 inline typename AVLSet<K>::iterator
    00104 AVLSet<K>::find(const K& k) const
    00105 {
    00106   return iterator(&map_.map_,map_.map_.find(k));
    00107 }
    00108
    00109 }
    00110
    00111 #endif
    00112
    00113 // ///////////////////////////////////////////////////////////////////////////
    00114
    00115 // Local Variables:
    00116 // mode: c++
    00117 // c-file-style: "CLJ"
    00118 // End: