pdutil/h/list.h

   1 /*
   2  *  Copyright 1993 Jeff Hollingsworth.  All rights reserved.
   3  *
   4  */
   5
   6 /*
   7  * list.h - list ADT
   8  *
   9  * $Log: list.h,v $
  10  * Revision 1.3  1993/08/02 22:46:37  hollings
  11  * added remove which was missing.
  12  *
  13  * Revision 1.2  1993/07/01  17:02:36  hollings
  14  * ansi endif comments
  15  *
  16  * Revision 1.1  1993/05/07  20:21:15  hollings
  17  * Initial revision
  18  *
  19  * Revision 1.1  1993/03/19  22:51:05  hollings
  20  * Initial revision
  21  *
  22  *
  23  */
  24 #ifndef LIST_H
  25 #define LIST_H
  26 #include <stdio.h>
  27
  28 typedef char Boolean;
  29
  30 #define FALSE 0
  31 #define TRUE  1
  32
  33 inline static int ListHash(void *ptr, int size)
  34 {
  35     return(((int)(ptr) % (int)(size)));
  36 }
  37
  38 template <class Type> class List;
  39
  40 template <class Type> class ListItem {
  41     friend class List<Type>;
  42     private:
  43         Type            data;
  44         void            *key;
  45         ListItem<Type>  *next;
  46 };
  47
  48 template <class Type> class List {
  49     public:
  50         List() { head = NULL; }
  51         void add(Type data, void *key);
  52         void add(Type data) { add(data, (void *) data); }
  53         Boolean addUnique(Type data) { return(addUnique(data, (void *) data)); }
  54         Boolean addUnique(Type data, void *key) {
  55             Type temp;
  56
  57             temp = find(key);
  58             if (!temp) {
  59                 add(data, key);
  60                 return(TRUE);
  61             } else {
  62                 return(FALSE);
  63             }
  64         }
  65         Type find(void *key);
  66         void remove(Type data);
  67         int count()     {
  68             int c;
  69             ListItem<Type> *curr;
  70
  71             for (curr=head,c=0; curr; curr=curr->next) c++;
  72             return(c);
  73         }
  74         Type operator *() {
  75             if (head)
  76                 return(head->data);
  77             else
  78                 return((Type) NULL);
  79         }
  80         void operator +=(List<Type> mergee) {
  81             ListItem<Type> *curr;
  82
  83             for (curr=mergee.head; curr; curr=curr->next) {
  84                 add(curr->data, curr->key);
  85             }
  86         }
  87         Type operator ++() {
  88             Type ret = (Type) NULL;
  89             if (head) {
  90                 ret = head->data;
  91                 head = head->next;
  92             }
  93             return(ret);
  94         }
  95     private:
  96         ListItem<Type>  *head;
  97 };
  98
  99
 100 template <class Type> void List<Type>::add(Type data, void *key)
 101 {
 102     ListItem<Type> *ni;
 103
 104     ni = new(ListItem<Type>);
 105     ni->data = data;
 106     ni->key = key;
 107
 108     ni->next = head;
 109     head = ni;
 110 }
 111
 112 template <class Type> void List<Type>::remove(Type data)
 113 {
 114     ListItem<Type> *lag;
 115     ListItem<Type> *curr;
 116
 117     for (curr=head, lag = NULL; curr; curr=curr->next) {
 118         if (curr->data == data) {
 119             break;
 120         }
 121         lag = curr;
 122     }
 123
 124     if (curr) {
 125         if (lag) {
 126             lag->next = curr->next;
 127         } else {
 128             head = curr->next;
 129         }
 130         delete(curr);
 131     } else {
 132         abort();
 133     }
 134 }
 135
 136 template <class Type> Type List<Type>::find(void *data)
 137 {
 138     ListItem<Type> *curr;
 139
 140     for (curr=head; curr; curr=curr->next) {
 141         if (curr->key == data) {
 142             return(curr->data);
 143         }
 144     }
 145     return((Type) 0);
 146 }
 147
 148 template <class Type> class HTable {
 149
 150     public:
 151         HTable(Type data) { HTable(); add(data, (void *) data); }
 152         HTable();
 153         void add(Type data, void *key);
 154         Boolean addUnique(Type data, void *key) {
 155             Type temp;
 156
 157             temp = find(key);
 158             if (temp ) {
 159                 return(0);
 160             } else {
 161                 add(data, key);
 162                 return(1);
 163             }
 164         }
 165         Type find(void *key);
 166         void remove(Type data);
 167         Type operator *() {
 168             Type curr;
 169
 170             curr = *currList;
 171             if (curr) return(curr);
 172             for (currHid++; currHid < tableSize; currHid++) {
 173                 if (table[currHid]) {
 174                     currList = *table[currHid];
 175                     curr = *currList;
 176                     if (curr) return(curr);
 177                 }
 178             }
 179             return(NULL);
 180         }
 181         Type operator ++() {
 182             Type curr;
 183
 184             curr = *currList;
 185             currList++;
 186             return(curr);
 187         }
 188         int count()     {
 189             int i, total;
 190
 191             total = 0;
 192             for (i=0; i < tableSize; i++) {
 193                 if (table[i]) {
 194                     total += table[i]->count();
 195                 }
 196             }
 197             return(total);
 198         }
 199     private:
 200         List<Type> **table;
 201         List<Type> currList;
 202         int currHid;
 203         int tableSize;
 204 };
 205
 206 template <class Type> HTable<Type>::HTable()
 207 {
 208     table = NULL;
 209     currHid = 0;
 210     tableSize = 0;
 211 }
 212
 213 template <class Type> Type HTable<Type>::find(void *key)
 214 {
 215     int hid;
 216
 217     if (!tableSize) return(NULL);
 218     hid = ListHash(key, tableSize);
 219     if (!table[hid]) {
 220         return(NULL);
 221     } else {
 222         return(table[hid]->find(key));
 223     }
 224 }
 225
 226 template <class Type> void HTable<Type>::add(Type data, void *key)
 227 {
 228     int hid;
 229
 230     if (!tableSize) {
 231         tableSize = 97;
 232         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
 233     }
 234     hid = ListHash(key, tableSize);
 235     if (!table[hid]) {
 236         table[hid] = new(List<Type>);
 237     }
 238     table[hid]->add(data, key);
 239 }
 240
 241
 242 template <class Type> void HTable<Type>::remove(Type data)
 243 {
 244     int hid;
 245
 246     for (hid = 0; hid < tableSize; hid++) {
 247         if (table[hid]) {
 248             table[hid]->remove(data);
 249         }
 250     }
 251 }
 252
 253 #endif /* LIST_H */