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