hashset.h

   1 /*      Copyright (c) 2015 Regents of the University of California
   2  *
   3  *      Author: Brian Demsky <bdemsky@uci.edu>
   4  *
   5  *      This program is free software; you can redistribute it and/or
   6  *      modify it under the terms of the GNU General Public License
   7  *      version 2 as published by the Free Software Foundation.
   8  */
   9
  10 #ifndef HASH_SET_H
  11 #define HASH_SET_H
  12 #include "hashtable.h"
  13
  14 template<typename _Key>
  15 struct LinkNode {
  16         _Key key;
  17         LinkNode<_Key> *prev;
  18         LinkNode<_Key> *next;
  19 };
  20
  21 template<typename _Key, typename _KeyInt, int _Shift, void * (* _malloc)(size_t), void * (* _calloc)(size_t, size_t), void (*_free)(void *), unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
  22 class HashSet;
  23
  24 template<typename _Key, typename _KeyInt, int _Shift, void * (* _malloc)(size_t) = snapshot_malloc, void * (* _calloc)(size_t, size_t) = snapshot_calloc, void (*_free)(void *) = snapshot_free, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
  25 class HSIterator {
  26 public:
  27         HSIterator(LinkNode<_Key> *_curr, HashSet <_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * _set) :
  28                 curr(_curr),
  29                 set(_set)
  30         {
  31         }
  32
  33         /** Override: new operator */
  34         void * operator new(size_t size) {
  35                 return _malloc(size);
  36         }
  37
  38         /** Override: delete operator */
  39         void operator delete(void *p, size_t size) {
  40                 _free(p);
  41         }
  42
  43         /** Override: new[] operator */
  44         void * operator new[](size_t size) {
  45                 return _malloc(size);
  46         }
  47
  48         /** Override: delete[] operator */
  49         void operator delete[](void *p, size_t size) {
  50                 _free(p);
  51         }
  52
  53         bool hasNext() {
  54                 return curr!=NULL;
  55         }
  56
  57         _Key next() {
  58                 _Key k=curr->key;
  59                 last=curr;
  60                 curr=curr->next;
  61                 return k;
  62         }
  63
  64         _Key currKey() {
  65                 return last->key;
  66         }
  67
  68         void remove() {
  69                 _Key k=last->key;
  70                 set->remove(k);
  71         }
  72
  73 private:
  74         LinkNode<_Key> *curr;
  75         LinkNode<_Key> *last;
  76         HashSet <_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * set;
  77 };
  78
  79 template<typename _Key, typename _KeyInt, int _Shift = 0, void * (*_malloc)(size_t) = snapshot_malloc, void * (*_calloc)(size_t, size_t) = snapshot_calloc, void (*_free)(void *) = snapshot_free, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
  80 class HashSet {
  81 public:
  82         HashSet(unsigned int initialcapacity = 16, double factor = 0.5) :
  83                 table(new HashTable<_Key, LinkNode<_Key> *, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(initialcapacity, factor)),
  84                 list(NULL),
  85                 tail(NULL)
  86         {
  87         }
  88
  89         /** @brief Hashset destructor */
  90         ~HashSet() {
  91                 LinkNode<_Key> *tmp=list;
  92                 while(tmp!=NULL) {
  93                         LinkNode<_Key> *tmpnext=tmp->next;
  94                         _free(tmp);
  95                         tmp=tmpnext;
  96                 }
  97                 delete table;
  98         }
  99
 100         HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * copy() {
 101                 HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> *copy=new HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(table->getCapacity(), table->getLoadFactor());
 102                 HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * it=iterator();
 103                 while(it->hasNext())
 104                         copy->add(it->next());
 105                 delete it;
 106                 return copy;
 107         }
 108
 109         void reset() {
 110                 LinkNode<_Key> *tmp=list;
 111                 while(tmp!=NULL) {
 112                         LinkNode<_Key> *tmpnext=tmp->next;
 113                         _free(tmp);
 114                         tmp=tmpnext;
 115                 }
 116                 list=tail=NULL;
 117                 table->reset();
 118         }
 119
 120         /** @brief Adds a new key to the hashset.  Returns false if the key
 121          *  is already present. */
 122
 123         bool add(_Key key) {
 124                 LinkNode<_Key> * val=table->get(key);
 125                 if (val==NULL) {
 126                         LinkNode<_Key> * newnode=(LinkNode<_Key> *)_malloc(sizeof(struct LinkNode<_Key>));
 127                         newnode->prev=tail;
 128                         newnode->next=NULL;
 129                         newnode->key=key;
 130                         if (tail!=NULL)
 131                                 tail->next=newnode;
 132                         else
 133                                 list=newnode;
 134                         tail=newnode;
 135                         table->put(key, newnode);
 136                         return true;
 137                 } else
 138                         return false;
 139         }
 140
 141         /** @brief Gets the original key corresponding to this one from the
 142          *  hashset.  Returns NULL if not present. */
 143
 144         _Key get(_Key key) {
 145                 LinkNode<_Key> * val=table->get(key);
 146                 if (val!=NULL)
 147                         return val->key;
 148                 else
 149                         return NULL;
 150         }
 151
 152         _Key getFirstKey() {
 153                 return list->key;
 154         }
 155
 156         bool contains(_Key key) {
 157                 return table->get(key)!=NULL;
 158         }
 159
 160         bool remove(_Key key) {
 161                 LinkNode<_Key> * oldlinknode;
 162                 oldlinknode=table->get(key);
 163                 if (oldlinknode==NULL) {
 164                         return false;
 165                 }
 166                 table->remove(key);
 167
 168                 //remove link node from the list
 169                 if (oldlinknode->prev==NULL)
 170                         list=oldlinknode->next;
 171                 else
 172                         oldlinknode->prev->next=oldlinknode->next;
 173                 if (oldlinknode->next!=NULL)
 174                         oldlinknode->next->prev=oldlinknode->prev;
 175                 else
 176                         tail=oldlinknode->prev;
 177                 _free(oldlinknode);
 178                 return true;
 179         }
 180
 181         unsigned int getSize() {
 182                 return table->getSize();
 183         }
 184
 185         bool isEmpty() {
 186                 return getSize()==0;
 187         }
 188
 189
 190
 191         HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * iterator() {
 192                 return new HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(list, this);
 193         }
 194
 195         /** Override: new operator */
 196         void * operator new(size_t size) {
 197                 return _malloc(size);
 198         }
 199
 200         /** Override: delete operator */
 201         void operator delete(void *p, size_t size) {
 202                 _free(p);
 203         }
 204
 205         /** Override: new[] operator */
 206         void * operator new[](size_t size) {
 207                 return _malloc(size);
 208         }
 209
 210         /** Override: delete[] operator */
 211         void operator delete[](void *p, size_t size) {
 212                 _free(p);
 213         }
 214 private:
 215         HashTable<_Key, LinkNode<_Key>*, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * table;
 216         LinkNode<_Key> *list;
 217         LinkNode<_Key> *tail;
 218 };
 219 #endif