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