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