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