Back to index

texmacs  1.0.7.15
hashset.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : hashset.cpp
00004 * DESCRIPTION: fixed size 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_CC
00013 #define HASHSET_CC
00014 #include "hashset.hpp"
00015 
00016 template<class T> void
00017 hashset_rep<T>::resize (int n2) {
00018   int i;
00019   int oldn= n;
00020   list<T>* olda= a;
00021   n= n2;
00022   a= tm_new_array<list<T> > (n);
00023   for (i=0; i<oldn; i++) {
00024     list<T> l(olda[i]);
00025     while (!is_nil(l)) {
00026       list<T>& newl= a[hash(l->item)&(n-1)];
00027       newl= list<T> (l->item, newl);
00028       l=l->next;
00029     }
00030   }
00031   tm_delete_array (olda);
00032 }
00033 
00034 template<class T> static T*
00035 search (list<T> l, T x) {
00036   while (!is_nil (l)) {
00037     if (l->item==x) return &(l->item);
00038     l= l->next;
00039   }
00040   return NULL;
00041 }
00042 
00043 template<class T> bool
00044 hashset_rep<T>::contains (T x) {
00045   return (search (a[hash(x)&(n-1)], x)==NULL? false: true);
00046 }
00047 
00048 template<class T> void
00049 hashset_rep<T>::insert (T x) {
00050   if (size==n*max) resize (n << 1);
00051   list<T>& l= a[hash(x)&(n-1)];
00052   if (search (l, x) != NULL) return;
00053   l= list<T> (x, l);
00054   size ++;
00055 }
00056 
00057 template<class T> void
00058 hashset_rep<T>::remove (T x) {
00059   list<T>* lptr= &a[hash(x)&(n-1)];
00060   while (!is_nil (*lptr)) {
00061     if ((*lptr)->item==x) {
00062       *lptr=(*lptr)->next;
00063       size --;
00064       return;
00065     }
00066     lptr=&((*lptr)->next);
00067   }
00068 }
00069 
00070 template<class T> bool
00071 operator <= (hashset<T> h1, hashset<T> h2) {
00072   int i=0, j=0, n=h1->n;
00073   if (N(h1)>N(h2)) return false;
00074   for (; i<n; i++) {
00075     list<T> l=h1->a[i];
00076     for (; !is_nil (l); l=l->next, j++)
00077       if (!h2->contains (l->item)) return false;
00078   }
00079   return true;
00080 }
00081 
00082 template<class T> bool
00083 operator < (hashset<T> h1, hashset<T> h2) {
00084   return (N(h1)<N(h2)) && (h1<=h2);
00085 }
00086 
00087 template<class T> bool
00088 operator == (hashset<T> h1, hashset<T> h2) {
00089   return (N(h1)==N(h2)) && (h1<=h2);
00090 }
00091 
00092 template<class T> tm_ostream&
00093 operator << (tm_ostream& out, hashset<T> h) {
00094   int i=0, j=0, n=h->n, size=h->size;
00095   out << "{ ";
00096   for (; i<n; i++) {
00097     list<T> l=h->a[i];
00098     for (; !is_nil (l); l=l->next, j++) {
00099       out << l->item;
00100       if (j!=size-1) out << ", ";
00101     }
00102   }
00103   out << " }";
00104   return out;
00105 }
00106 
00107 template<class T>
00108 hashset<T>::operator tree () {
00109   int i=0, j=0, n=this->rep->n, size=this->rep->size;
00110   tree t (COLLECTION, size);
00111   for (; i<n; i++) {
00112     list<T> l=this->rep->a[i];
00113     for (; !is_nil (l); l=l->next, j++)
00114       t[j]= as_tree(l->item);
00115   }
00116   return t;
00117 }
00118 
00119 #endif // defined HASHSET_CC