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