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 (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 (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:
Generated at Fri Jan 10 08:14:08 2003 for MPQC 2.1.3 using the documentation package Doxygen 1.2.14.