Back to index

texmacs  1.0.7.15
hashset.hpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : hashset.hpp
00004 * DESCRIPTION: hashsets with reference counting
00005 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #ifndef HASHSET_H
00013 #define HASHSET_H
00014 #include "list.hpp"
00015 
00016 template<class T> class hashset;
00017 template<class T> class hashset_iterator_rep;
00018 template<class T> int N (hashset<T> h);
00019 template<class T> tm_ostream& operator << (tm_ostream& out, hashset<T> h);
00020 template<class T> bool operator <= (hashset<T> h1, hashset<T> h2);
00021 
00022 template<class T> class hashset_rep: concrete_struct {
00023   int size;    // size of hashset (nr of entries)
00024   int n;       // nr of keys (a power of two)
00025   int max;     // mean number of entries per key
00026   list<T>* a;  // the array of entries
00027 
00028 public:
00029   inline hashset_rep ():
00030     size(0), n(1), max(1), a (tm_new_array<list<T> > (1)) {}
00031   inline hashset_rep(int n2, int max2=1):
00032     size(0), n(n2), max(max2), a (tm_new_array<list<T> > (n)) {}
00033   inline ~hashset_rep () { tm_delete_array (a); }
00034 
00035   bool contains (T x);
00036   void resize (int n);
00037   void insert (T x);
00038   void remove (T x);
00039 
00040   friend class hashset<T>;
00041   friend int N LESSGTR (hashset<T> h);
00042   friend tm_ostream& operator << LESSGTR (tm_ostream& out, hashset<T> h);
00043   friend bool operator <= LESSGTR (hashset<T> h1, hashset<T> h2);
00044   friend class hashset_iterator_rep<T>;
00045 };
00046 
00047 template<class T> class hashset {
00048 CONCRETE_TEMPLATE(hashset,T);
00049   inline hashset (int n=1, int max=1):
00050     rep (tm_new<hashset_rep<T> > (n, max)) {}
00051   operator tree ();
00052 };
00053 CONCRETE_TEMPLATE_CODE(hashset,class,T);
00054 
00055 template<class T> inline int N (hashset<T> h) { return h->size; }
00056 template<class T> bool operator == (hashset<T> h1, hashset<T> h2);
00057 template<class T> bool operator <= (hashset<T> h1, hashset<T> h2);
00058 template<class T> bool operator <  (hashset<T> h1, hashset<T> h2);
00059 
00060 #include "hashset.cpp"
00061 
00062 #endif // defined HASHSET_H