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