src/Collections/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 #define HashSetDef(Name, _Key)                                          \
  15         struct LinkNode ## Name {                                             \
  16                 _Key key;                                                           \
  17                 struct LinkNode ## Name *prev;                                      \
  18                 struct LinkNode ## Name *next;                                      \
  19         };                                                                    \
  20         typedef struct LinkNode ## Name LinkNode ## Name;                     \
  21         struct HashSet ## Name;                                               \
  22         typedef struct HashSet ## Name HashSet ## Name;                       \
  23         struct HSIterator ## Name {                                           \
  24                 LinkNode ## Name * curr;                                             \
  25                 LinkNode ## Name * last;                                             \
  26                 HashSet ## Name * set;                                              \
  27         };                                                                    \
  28         typedef struct HSIterator ## Name HSIterator ## Name;                 \
  29         HashTableDef(Name ## Set, _Key, LinkNode ## Name *);                  \
  30         HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name * _curr, HashSet ## Name * _set); \
  31         void deleteIter ## Name(HSIterator ## Name * hsit);                      \
  32         bool hasNext ## Name(HSIterator ## Name * hsit);                       \
  33         _Key next ## Name(HSIterator ## Name * hsit);                          \
  34         _Key currKey ## Name(HSIterator ## Name * hsit);                       \
  35         void removeIter ## Name(HSIterator ## Name * hsit);                        \
  36         struct HashSet ## Name {                                              \
  37                 HashTable ## Name ## Set * table;                                   \
  38                 LinkNode ## Name * list;                                             \
  39                 LinkNode ## Name * tail;                                             \
  40         };                                                                    \
  41         typedef struct HashSet ## Name HashSet ## Name;                       \
  42                                                                         \
  43         HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor); \
  44         void deleteHashSet ## Name(struct HashSet ## Name *set);               \
  45         HashSet ## Name * copyHashSet ## Name(HashSet ## Name * set);                \
  46         void resetHashSet ## Name(HashSet ## Name * set);                         \
  47         bool addHashSet ## Name(HashSet ## Name * set,_Key key);                     \
  48         void addAllHashSet ## Name(HashSet ## Name * set,HashSet ## Name * other);  \
  49         _Key getHashSet ## Name(HashSet ## Name * set,_Key key);                  \
  50         _Key getHashSetFirstKey ## Name(HashSet ## Name * set);                      \
  51         bool containsHashSet ## Name(HashSet ## Name * set,_Key key);             \
  52         bool removeHashSet ## Name(HashSet ## Name * set,_Key key);               \
  53         unsigned int getSizeHashSet ## Name(HashSet ## Name * set);               \
  54         bool isEmptyHashSet ## Name(HashSet ## Name * set);                          \
  55         HSIterator ## Name * iterator ## Name(HashSet ## Name * set);
  56
  57
  58 #define HashSetImpl(Name, _Key, hash_function, equals)                  \
  59         HashTableImpl(Name ## Set, _Key, LinkNode ## Name *, hash_function, equals, ourfree); \
  60         HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name * _curr, HashSet ## Name * _set) { \
  61                 HSIterator ## Name * hsit = (HSIterator ## Name *)ourmalloc(sizeof(HSIterator ## Name)); \
  62                 hsit->curr = _curr;                                                   \
  63                 hsit->set = _set;                                                     \
  64                 return hsit;                                                        \
  65         }                                                                     \
  66                                                                         \
  67         void deleteIter ## Name(HSIterator ## Name * hsit) {                   \
  68                 ourfree(hsit);                                                      \
  69         }                                                                     \
  70                                                                         \
  71         bool hasNext ## Name(HSIterator ## Name * hsit) {                      \
  72                 return hsit->curr != NULL;                                            \
  73         }                                                                     \
  74                                                                         \
  75         _Key next ## Name(HSIterator ## Name * hsit) {                         \
  76                 _Key k = hsit->curr->key;                                             \
  77                 hsit->last = hsit->curr;                                              \
  78                 hsit->curr = hsit->curr->next;                                        \
  79                 return k;                                                           \
  80         }                                                                     \
  81                                                                         \
  82         _Key currKey ## Name(HSIterator ## Name * hsit) {                      \
  83                 return hsit->last->key;                                             \
  84         }                                                                     \
  85                                                                         \
  86         void removeIter ## Name(HSIterator ## Name * hsit) {                   \
  87                 _Key k = hsit->last->key;                                             \
  88                 removeHashSet ## Name(hsit->set, k);                                    \
  89         }                                                                     \
  90                                                                         \
  91         HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor) { \
  92                 HashSet ## Name * set = (HashSet ## Name *)ourmalloc(sizeof(struct HashSet ## Name));  \
  93                 set->table = allocHashTable ## Name ## Set(initialcapacity, factor);          \
  94                 set->list = NULL;                                                     \
  95                 set->tail = NULL;                                                     \
  96                 return set;                                                         \
  97         }                                                                       \
  98                                                                         \
  99         void deleteHashSet ## Name(struct HashSet ## Name *set) {            \
 100                 LinkNode ## Name *tmp = set->list;                                    \
 101                 while (tmp != NULL) {                                                  \
 102                         LinkNode ## Name * tmpnext = tmp->next;                              \
 103                         ourfree(tmp);                                                     \
 104                         tmp = tmpnext;                                                      \
 105                 }                                                                   \
 106                 deleteHashTable ## Name ## Set(set->table);                         \
 107                 ourfree(set);                                                       \
 108         }                                                                     \
 109                                                                         \
 110         HashSet ## Name * copyHashSet ## Name(HashSet ## Name * set) {               \
 111                 HashSet ## Name * copy = allocHashSet ## Name(getCapacity ## Name ## Set(set->table), getLoadFactor ## Name ## Set(set->table)); \
 112                 HSIterator ## Name * it = iterator ## Name(set);                      \
 113                 while (hasNext ## Name(it))                                          \
 114                         addHashSet ## Name(copy, next ## Name(it));                              \
 115                 deleteIter ## Name(it);                                             \
 116                 return copy;                                                        \
 117         }                                                                     \
 118                                                                         \
 119         void resetHashSet ## Name(HashSet ## Name * set) {                        \
 120                 LinkNode ## Name * tmp = set->list;                                    \
 121                 while (tmp != NULL) {                                                  \
 122                         LinkNode ## Name * tmpnext = tmp->next;                              \
 123                         ourfree(tmp);                                                     \
 124                         tmp = tmpnext;                                                      \
 125                 }                                                                   \
 126                 set->list = set->tail = NULL;                                           \
 127                 reset ## Name ## Set(set->table);                                   \
 128         }                                                                     \
 129                                                                         \
 130         void addAllHashSet ## Name(HashSet ## Name * set, HashSet ## Name * other) { \
 131                 HSIterator ## Name * it = iterator ## Name(other);                  \
 132                 while (hasNext ## Name(it))                                         \
 133                         addHashSet ## Name(set, next ## Name(it));                        \
 134                 deleteIter ## Name(it);                                             \
 135         }                                                                     \
 136                                                                         \
 137         bool addHashSet ## Name(HashSet ## Name * set,_Key key) {                    \
 138                 LinkNode ## Name * val = get ## Name ## Set(set->table, key);         \
 139                 if (val == NULL) {                                                    \
 140                         LinkNode ## Name * newnode = (LinkNode ## Name *)ourmalloc(sizeof(struct LinkNode ## Name)); \
 141                         newnode->prev = set->tail;                                          \
 142                         newnode->next = NULL;                                               \
 143                         newnode->key = key;                                                 \
 144                         if (set->tail != NULL)                                              \
 145                                 set->tail->next = newnode;                                        \
 146                         else                                                              \
 147                                 set->list = newnode;                                              \
 148                         set->tail = newnode;                                                \
 149                         put ## Name ## Set(set->table, key, newnode);                     \
 150                         return true;                                                      \
 151                 } else                                                              \
 152                         return false;                                                     \
 153         }                                                                     \
 154                                                                         \
 155         _Key getHashSet ## Name(HashSet ## Name * set,_Key key) {                 \
 156                 LinkNode ## Name * val = get ## Name ## Set(set->table, key);         \
 157                 if (val != NULL)                                                      \
 158                         return val->key;                                                  \
 159                 else                                                                \
 160                         return NULL;                                                      \
 161         }                                                                     \
 162                                                                         \
 163         _Key getHashSetFirstKey ## Name(HashSet ## Name * set) {                     \
 164                 return set->list->key;                                              \
 165         }                                                                     \
 166                                                                         \
 167         bool containsHashSet ## Name(HashSet ## Name * set,_Key key) {            \
 168                 return get ## Name ## Set(set->table, key) != NULL;                   \
 169         }                                                                     \
 170                                                                         \
 171         bool removeHashSet ## Name(HashSet ## Name * set,_Key key) {              \
 172                 LinkNode ## Name * oldlinknode;                                     \
 173                 oldlinknode = get ## Name ## Set(set->table, key);                    \
 174                 if (oldlinknode == NULL) {                                            \
 175                         return false;                                                     \
 176                 }                                                                   \
 177                 remove ## Name ## Set(set->table, key);                             \
 178                                                                         \
 179                 if (oldlinknode->prev == NULL)                                        \
 180                         set->list = oldlinknode->next;                                      \
 181                 else                                                                \
 182                         oldlinknode->prev->next = oldlinknode->next;                        \
 183                 if (oldlinknode->next != NULL)                                        \
 184                         oldlinknode->next->prev = oldlinknode->prev;                        \
 185                 else                                                                \
 186                         set->tail = oldlinknode->prev;                                      \
 187                 ourfree(oldlinknode);                                               \
 188                 return true;                                                        \
 189         }                                                                     \
 190                                                                         \
 191         unsigned int getSizeHashSet ## Name(HashSet ## Name * set) {              \
 192                 return getSizeTable ## Name ## Set(set->table);                     \
 193         }                                                                     \
 194                                                                         \
 195         bool isEmptyHashSet ## Name(HashSet ## Name * set) {                         \
 196                 return getSizeHashSet ## Name(set) == 0;                                  \
 197         }                                                                     \
 198                                                                         \
 199         HSIterator ## Name * iterator ## Name(HashSet ## Name * set) {        \
 200                 return allocHSIterator ## Name(set->list, set);                     \
 201         }
 202 #endif