src/Collections/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 HASHSET_H
  11 #define HASHSET_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, unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
  22 class Hashset;
  23
  24 template<typename _Key, typename _KeyInt, int _Shift, unsigned int (*hash_function)(_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = defaultEquals<_Key> >
  25 class SetIterator {
  26 public:
  27         SetIterator(Linknode<_Key> *_curr, Hashset <_Key, _KeyInt, _Shift, hash_function, equals> *_set) :
  28                 curr(_curr),
  29                 set(_set)
  30         {
  31         }
  32
  33         SetIterator(SetIterator *s) : curr(s->curr),
  34                 last(s->last),
  35                 set(s->set) {
  36         }
  37
  38         /** Override: new operator */
  39         void *operator new(size_t size) {
  40                 return ourmalloc(size);
  41         }
  42
  43         /** Override: delete operator */
  44         void operator delete(void *p, size_t size) {
  45                 ourfree(p);
  46         }
  47
  48         /** Override: new[] operator */
  49         void *operator new[](size_t size) {
  50                 return ourmalloc(size);
  51         }
  52
  53         /** Override: delete[] operator */
  54         void operator delete[](void *p, size_t size) {
  55                 ourfree(p);
  56         }
  57
  58         bool hasNext() {
  59                 return curr != NULL;
  60         }
  61
  62         _Key next() {
  63                 _Key k = curr->key;
  64                 last = curr;
  65                 curr = curr->next;
  66                 return k;
  67         }
  68
  69         _Key currKey() {
  70                 return last->key;
  71         }
  72
  73         void remove() {
  74                 _Key k = last->key;
  75                 set->remove(k);
  76         }
  77
  78 private:
  79         Linknode<_Key> *curr;
  80         Linknode<_Key> *last;
  81         Hashset <_Key, _KeyInt, _Shift, hash_function, equals> *set;
  82 };
  83
  84 template<typename _Key, typename _KeyInt, int _Shift = 0, unsigned int (*hash_function)(_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = defaultEquals<_Key> >
  85 class Hashset {
  86 public:
  87         Hashset(unsigned int initialcapacity = 16, double factor = 0.5) :
  88                 table(new Hashtable<_Key, Linknode<_Key> *, _KeyInt, _Shift, hash_function, equals>(initialcapacity, factor)),
  89                 list(NULL),
  90                 tail(NULL)
  91         {
  92         }
  93
  94         /** @brief Hashset destructor */
  95         ~Hashset() {
  96                 Linknode<_Key> *tmp = list;
  97                 while (tmp != NULL) {
  98                         Linknode<_Key> *tmpnext = tmp->next;
  99                         ourfree(tmp);
 100                         tmp = tmpnext;
 101                 }
 102                 delete table;
 103         }
 104
 105         Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy() {
 106                 Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy = new Hashset<_Key, _KeyInt, _Shift, hash_function, equals>(table->getCapacity(), table->getLoadFactor());
 107                 SetIterator<_Key, _KeyInt, _Shift, hash_function, equals> *it = iterator();
 108                 while (it->hasNext())
 109                         copy->add(it->next());
 110                 delete it;
 111                 return copy;
 112         }
 113
 114         void reset() {
 115                 Linknode<_Key> *tmp = list;
 116                 while (tmp != NULL) {
 117                         Linknode<_Key> *tmpnext = tmp->next;
 118                         ourfree(tmp);
 119                         tmp = tmpnext;
 120                 }
 121                 list = tail = NULL;
 122                 table->reset();
 123         }
 124
 125         void resetAndDelete() {
 126                 Linknode<_Key> *tmp = list;
 127                 while (tmp != NULL) {
 128                         Linknode<_Key> *tmpnext = tmp->next;
 129                         ourfree(tmp);
 130                         tmp = tmpnext;
 131                 }
 132                 list = tail = NULL;
 133                 table->resetAndDeleteKeys();
 134         }
 135
 136         /** @brief Adds a new key to the hashset.  Returns false if the key
 137          *  is already present. */
 138
 139         void addAll(Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *table) {
 140                 SetIterator<_Key, _KeyInt, _Shift, hash_function, equals> *it = iterator();
 141                 while (it->hasNext())
 142                         add(it->next());
 143                 delete it;
 144         }
 145
 146         /** @brief Adds a new key to the hashset.  Returns false if the key
 147          *  is already present. */
 148
 149         bool add(_Key key) {
 150                 Linknode<_Key> *val = table->get(key);
 151                 if (val == NULL) {
 152                         Linknode<_Key> *newnode = (Linknode<_Key> *)ourmalloc(sizeof(struct Linknode<_Key>));
 153                         newnode->prev = tail;
 154                         newnode->next = NULL;
 155                         newnode->key = key;
 156                         if (tail != NULL)
 157                                 tail->next = newnode;
 158                         else
 159                                 list = newnode;
 160                         tail = newnode;
 161                         table->put(key, newnode);
 162                         return true;
 163                 } else
 164                         return false;
 165         }
 166
 167         /** @brief Return random key from set. */
 168
 169         _Key getRandomElement() {
 170                 if (getSize() == 0)
 171                         return NULL;
 172                 else if (getSize() < 6) {
 173                         uint count = random() % getSize();
 174                         Linknode<_Key> *ptr = list;
 175                         while (count > 0) {
 176                                 ptr = ptr->next;
 177                                 count--;
 178                         }
 179                         return ptr->key;
 180                 } else
 181                         return table->getRandomValue()->key;
 182         }
 183
 184         /** @brief Gets the original key corresponding to this one from the
 185          *  hashset.  Returns NULL if not present. */
 186
 187         _Key get(_Key key) {
 188                 Linknode<_Key> *val = table->get(key);
 189                 if (val != NULL)
 190                         return val->key;
 191                 else
 192                         return NULL;
 193         }
 194
 195         _Key getFirstKey() {
 196                 return list->key;
 197         }
 198
 199         bool contains(_Key key) {
 200                 return table->get(key) != NULL;
 201         }
 202
 203         bool remove(_Key key) {
 204                 Linknode<_Key> *oldlinknode;
 205                 oldlinknode = table->get(key);
 206                 if (oldlinknode == NULL) {
 207                         return false;
 208                 }
 209                 table->remove(key);
 210
 211                 //remove link node from the list
 212                 if (oldlinknode->prev == NULL)
 213                         list = oldlinknode->next;
 214                 else
 215                         oldlinknode->prev->next = oldlinknode->next;
 216                 if (oldlinknode->next != NULL)
 217                         oldlinknode->next->prev = oldlinknode->prev;
 218                 else
 219                         tail = oldlinknode->prev;
 220                 ourfree(oldlinknode);
 221                 return true;
 222         }
 223
 224         unsigned int getSize() const {
 225                 return table->getSize();
 226         }
 227
 228         bool isEmpty() const {
 229                 return getSize() == 0;
 230         }
 231
 232         SetIterator<_Key, _KeyInt, _Shift, hash_function, equals> *iterator() {
 233                 return new SetIterator<_Key, _KeyInt, _Shift, hash_function, equals>(list, this);
 234         }
 235
 236         /** Override: new operator */
 237         void *operator new(size_t size) {
 238                 return ourmalloc(size);
 239         }
 240
 241         /** Override: delete operator */
 242         void operator delete(void *p, size_t size) {
 243                 ourfree(p);
 244         }
 245
 246         /** Override: new[] operator */
 247         void *operator new[](size_t size) {
 248                 return ourmalloc(size);
 249         }
 250
 251         /** Override: delete[] operator */
 252         void operator delete[](void *p, size_t size) {
 253                 ourfree(p);
 254         }
 255 private:
 256         Hashtable<_Key, Linknode<_Key> *, _KeyInt, _Shift, hash_function, equals> *table;
 257         Linknode<_Key> *list;
 258         Linknode<_Key> *tail;
 259 };
 260 #endif