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, typename _KeyInt, int _Shift, unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
  15 class Hashset;
  16
  17 template<typename _Key, typename _Val, typename _KeyInt = uintptr_t, int _Shift = 0, unsigned int (*hash_function)(_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = defaultEquals<_Key> >
  18 class SetIterator {
  19 public:
  20         SetIterator(Hashtable <_Key, _Val, _KeyInt, _Shift, hash_function, equals> *_table) :
  21     currptr(1),
  22     nextptr(0),
  23                 table(_table)
  24         {
  25         }
  26
  27         /** Override: new operator */
  28         void *operator new(size_t size) {
  29                 return ourmalloc(size);
  30         }
  31
  32         /** Override: delete operator */
  33         void operator delete(void *p, size_t size) {
  34                 ourfree(p);
  35         }
  36
  37         /** Override: new[] operator */
  38         void *operator new[](size_t size) {
  39                 return ourmalloc(size);
  40         }
  41
  42         /** Override: delete[] operator */
  43         void operator delete[](void *p, size_t size) {
  44                 ourfree(p);
  45         }
  46
  47         bool hasNext() {
  48                 if (currptr > nextptr) {
  49                         currptr = 0;
  50                 } else {
  51                         nextptr++;
  52                 }
  53                 if (nextptr == 0) {
  54                         if (table->zero && table->zero->val)
  55                                 return true;
  56                         else
  57                                 nextptr++;
  58                 }
  59                 for(;nextptr < (table->capacity + 1);nextptr++) {
  60                         struct Hashlistnode<_Key, _Val> *ptr = & table->table[nextptr-1];
  61                         if (ptr->key && ptr->val) {
  62                                 return true;
  63                         }
  64                 }
  65                 return false;
  66         }
  67
  68   _Val currVal() {
  69     if (currptr == 0)
  70                         return table->zero->val;
  71                 else
  72                         return table->table[currptr-1].val;
  73   }
  74
  75   _Key currKey() {
  76                 if (currptr == 0)
  77                         return table->zero->key;
  78                 else
  79                         return table->table[currptr-1].key;
  80         }
  81
  82   _Key next() {
  83                 currptr = nextptr;
  84                 return currKey();
  85         }
  86
  87         void remove() {
  88                 table->remove(currKey());
  89         }
  90
  91 private:
  92   unsigned int currptr;
  93   unsigned int nextptr;
  94         Hashtable <_Key, _Val, _KeyInt, _Shift, hash_function, equals> *table;
  95 };
  96
  97 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> >
  98 class Hashset {
  99 public:
 100         Hashset(unsigned int initialcapacity = 16, double factor = 0.5) :
 101                 table(new Hashtable<_Key, _Key, _KeyInt, _Shift, hash_function, equals>(initialcapacity, factor))
 102         {
 103         }
 104
 105         /** @brief Hashset destructor */
 106         ~Hashset() {
 107                 delete table;
 108         }
 109
 110         Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy() {
 111                 Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy = new Hashset<_Key, _KeyInt, _Shift, hash_function, equals>(table->getCapacity(), table->getLoadFactor());
 112                 SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals> *it = iterator();
 113                 while (it->hasNext())
 114                         copy->add(it->next());
 115                 delete it;
 116                 return copy;
 117         }
 118
 119         void clear() {
 120                 table->clear();
 121         }
 122
 123         /** @brief Adds a new key to the hashset.  Returns false if the key
 124          *  is already present. */
 125
 126         void addAll(Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *table) {
 127                 SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals> *it = iterator();
 128                 while (it->hasNext())
 129                         add(it->next());
 130                 delete it;
 131         }
 132
 133         /** @brief Adds a new key to the hashset.  Returns false if the key
 134          *  is already present. */
 135
 136         bool add(_Key key) {
 137                 if (!table->contains(key)) {
 138                         table->put(key, key);
 139                         return true;
 140                 } else
 141                         return false;
 142         }
 143
 144         /** @brief Gets the original key corresponding to this one from the
 145          *  hashset.  Returns NULL if not present. */
 146
 147         _Key get(_Key key) {
 148                 return table->get(key);
 149         }
 150
 151         _Key getFirstKey() {
 152                 return table->list->key;
 153         }
 154
 155         bool contains(_Key key) {
 156                 return table->contains(key);
 157         }
 158
 159         bool remove(_Key key) {
 160                 if (!table->contains(key))
 161                         return false;
 162                 table->remove(key);
 163                 return true;
 164         }
 165
 166         unsigned int size() const {
 167                 return table->size();
 168         }
 169
 170         bool isEmpty() const {
 171                 return size() == 0;
 172         }
 173
 174         SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals> *iterator() {
 175                 return new SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals>(table);
 176         }
 177
 178         /** Override: new operator */
 179         void *operator new(size_t size) {
 180                 return ourmalloc(size);
 181         }
 182
 183         /** Override: delete operator */
 184         void operator delete(void *p, size_t size) {
 185                 ourfree(p);
 186         }
 187
 188         /** Override: new[] operator */
 189         void *operator new[](size_t size) {
 190                 return ourmalloc(size);
 191         }
 192
 193         /** Override: delete[] operator */
 194         void operator delete[](void *p, size_t size) {
 195                 ourfree(p);
 196         }
 197 private:
 198         Hashtable<_Key, _Key, _KeyInt, _Shift, hash_function, equals> *table;
 199 };
 200
 201 template<typename _Key, typename _Val, typename _KeyInt, int _Shift, unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
 202 SetIterator<_Key, _Val,_KeyInt, _Shift, hash_function, equals> *getKeyIterator(Hashtable<_Key,_Val,_KeyInt,_Shift,hash_function,equals> *table) {
 203         return new SetIterator<_Key, _Val, _KeyInt, _Shift, hash_function, equals>(table);
 204 }
 205 #endif