version2/src/C/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         /** Override: new operator */
  34         void *operator new(size_t size) {
  35                 return ourmalloc(size);
  36         }
  37
  38         /** Override: delete operator */
  39         void operator delete(void *p, size_t size) {
  40                 ourfree(p);
  41         }
  42
  43         /** Override: new[] operator */
  44         void *operator new[](size_t size) {
  45                 return ourmalloc(size);
  46         }
  47
  48         /** Override: delete[] operator */
  49         void operator delete[](void *p, size_t size) {
  50                 ourfree(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, hash_function, equals> *set;
  77 };
  78
  79 template<typename _Key, typename _KeyInt = uintptr_t, int _Shift = 0, unsigned int (*hash_function) (_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals) (_Key, _Key) = defaultEquals<_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, 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                         ourfree(tmp);
  95                         tmp = tmpnext;
  96                 }
  97                 delete table;
  98         }
  99
 100         Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy() {
 101                 Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy = new Hashset<_Key, _KeyInt, _Shift, hash_function, equals>(table->getCapacity(), table->getLoadFactor());
 102                 SetIterator<_Key, _KeyInt, _Shift, 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                         ourfree(tmp);
 114                         tmp = tmpnext;
 115                 }
 116                 list = tail = NULL;
 117                 table->reset();
 118         }
 119
 120         void resetAndDelete() {
 121                 Linknode<_Key> *tmp = list;
 122                 while (tmp != NULL) {
 123                         Linknode<_Key> *tmpnext = tmp->next;
 124                         ourfree(tmp);
 125                         tmp = tmpnext;
 126                 }
 127                 list = tail = NULL;
 128                 table->resetAndDeleteKeys();
 129         }
 130
 131         /** @brief Adds a new key to the hashset.  Returns false if the key
 132          *  is already present. */
 133
 134         void addAll(Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *table) {
 135                 SetIterator<_Key, _KeyInt, _Shift, hash_function, equals> *it = iterator();
 136                 while (it->hasNext())
 137                         add(it->next());
 138                 delete it;
 139         }
 140
 141         /** @brief Adds a new key to the hashset.  Returns false if the key
 142          *  is already present. */
 143
 144         bool add(_Key key) {
 145                 Linknode<_Key> *val = table->get(key);
 146                 if (val == NULL) {
 147                         Linknode<_Key> *newnode = (Linknode<_Key> *)ourmalloc(sizeof(struct Linknode<_Key>));
 148                         newnode->prev = tail;
 149                         newnode->next = NULL;
 150                         newnode->key = key;
 151                         if (tail != NULL)
 152                                 tail->next = newnode;
 153                         else
 154                                 list = newnode;
 155                         tail = newnode;
 156                         table->put(key, newnode);
 157                         return true;
 158                 } else
 159                         return false;
 160         }
 161
 162         /** @brief Return random key from set. */
 163
 164         _Key getRandomElement() {
 165                 if (getSize() == 0)
 166                         return NULL;
 167                 else if (getSize() < 6) {
 168                         uint count = random() % getSize();
 169                         Linknode<_Key> *ptr = list;
 170                         while (count > 0) {
 171                                 ptr = ptr->next;
 172                                 count--;
 173                         }
 174                         return ptr->key;
 175                 } else
 176                         return table->getRandomValue()->key;
 177         }
 178
 179         /** @brief Gets the original key corresponding to this one from the
 180          *  hashset.  Returns NULL if not present. */
 181
 182         _Key get(_Key key) {
 183                 Linknode<_Key> *val = table->get(key);
 184                 if (val != NULL)
 185                         return val->key;
 186                 else
 187                         return NULL;
 188         }
 189
 190         _Key getFirstKey() {
 191                 return list->key;
 192         }
 193
 194         bool contains(_Key key) {
 195                 return table->get(key) != NULL;
 196         }
 197
 198         bool remove(_Key key) {
 199                 Linknode<_Key> *oldlinknode;
 200                 oldlinknode = table->get(key);
 201                 if (oldlinknode == NULL) {
 202                         return false;
 203                 }
 204                 table->remove(key);
 205
 206                 //remove link node from the list
 207                 if (oldlinknode->prev == NULL)
 208                         list = oldlinknode->next;
 209                 else
 210                         oldlinknode->prev->next = oldlinknode->next;
 211                 if (oldlinknode->next != NULL)
 212                         oldlinknode->next->prev = oldlinknode->prev;
 213                 else
 214                         tail = oldlinknode->prev;
 215                 ourfree(oldlinknode);
 216                 return true;
 217         }
 218
 219         unsigned int getSize() const {
 220                 return table->getSize();
 221         }
 222
 223         bool isEmpty() const {
 224                 return getSize() == 0;
 225         }
 226
 227         SetIterator<_Key, _KeyInt, _Shift, hash_function, equals> *iterator() {
 228                 return new SetIterator<_Key, _KeyInt, _Shift, hash_function, equals>(list, this);
 229         }
 230
 231         /** Override: new operator */
 232         void *operator new(size_t size) {
 233                 return ourmalloc(size);
 234         }
 235
 236         /** Override: delete operator */
 237         void operator delete(void *p, size_t size) {
 238                 ourfree(p);
 239         }
 240
 241         /** Override: new[] operator */
 242         void *operator new[](size_t size) {
 243                 return ourmalloc(size);
 244         }
 245
 246         /** Override: delete[] operator */
 247         void operator delete[](void *p, size_t size) {
 248                 ourfree(p);
 249         }
 250 private:
 251         Hashtable<_Key, Linknode<_Key> *, _KeyInt, _Shift, hash_function, equals> *table;
 252         Linknode<_Key> *list;
 253         Linknode<_Key> *tail;
 254 };
 255 #endif