common/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.9  1994/02/03 23:30:43  hollings
  11  * changed listHash to a macro to work with g++ 2.5.2.
  12  *
  13  * Revision 1.8  1994/01/25  20:49:40  hollings
  14  * First real version of utility library.
  15  *
  16  * Revision 1.7  1994/01/19  20:46:17  hollings
  17  * guardef defn of true/false.
  18  *
  19  * Revision 1.6  1993/12/15  21:06:54  hollings
  20  * removed destructors.  Our current list semantics don't support auto
  21  * destruction of list comonents since list elements can be shared between
  22  * lists.
  23  *
  24  * Revision 1.5  1993/12/13  20:11:14  hollings
  25  * added destructor for List class.
  26  *
  27  * Revision 1.4  1993/10/19  15:31:52  hollings
  28  * assorted small fixes.
  29  *
  30  * Revision 1.3  1993/08/02  22:46:37  hollings
  31  * added remove which was missing.
  32  *
  33  * Revision 1.2  1993/07/01  17:02:36  hollings
  34  * ansi endif comments
  35  *
  36  * Revision 1.1  1993/05/07  20:21:15  hollings
  37  * Initial revision
  38  *
  39  * Revision 1.1  1993/03/19  22:51:05  hollings
  40  * Initial revision
  41  *
  42  *
  43  */
  44 #ifndef LIST_H
  45 #define LIST_H
  46 #include <stdio.h>
  47 #include <stdlib.h>
  48
  49 typedef int Boolean;
  50
  51 #ifndef FALSE
  52 #define FALSE 0
  53 #define TRUE  1
  54 #endif
  55
  56 #define ListHash(ptr, size) (((int)(ptr) % (int)(size)))
  57
  58 template <class Type> class List;
  59
  60 template <class Type> class ListItem {
  61     friend class List<Type>;
  62     friend class StringList<Type>;
  63     private:
  64         Type            data;
  65         void            *key;
  66         ListItem<Type>  *next;
  67 };
  68
  69 template <class Type> class List {
  70     public:
  71         List() { head = NULL; }
  72         void add(Type data, void *key);
  73         void add(Type data) { add(data, (void *) data); }
  74         Boolean addUnique(Type data) { return(addUnique(data, (void *) data)); }
  75         Boolean addUnique(Type data, void *key) {
  76             Type temp;
  77
  78             temp = find(key);
  79             if (!temp) {
  80                 add(data, key);
  81                 return(TRUE);
  82             } else {
  83                 return(FALSE);
  84             }
  85         }
  86         Type find(void *key);
  87         Boolean remove(void *key);
  88         int count()     {
  89             int c;
  90             ListItem<Type> *curr;
  91
  92             for (curr=head,c=0; curr; curr=curr->next) c++;
  93             return(c);
  94         }
  95         Type operator *() {
  96             if (head)
  97                 return(head->data);
  98             else
  99                 return((Type) NULL);
 100         }
 101         void operator +=(List<Type> mergee) {
 102             ListItem<Type> *curr;
 103
 104             for (curr=mergee.head; curr; curr=curr->next) {
 105                 add(curr->data, curr->key);
 106             }
 107         }
 108         Type operator ++() {
 109             Type ret = (Type) NULL;
 110             if (head) {
 111                 ret = head->data;
 112                 head = head->next;
 113             }
 114             return(ret);
 115         }
 116     protected:
 117         ListItem<Type>  *head;
 118 };
 119
 120 template <class Type> void List<Type>::add(Type data, void *key)
 121 {
 122     ListItem<Type> *ni;
 123
 124     ni = new(ListItem<Type>);
 125     ni->data = data;
 126     ni->key = key;
 127
 128     ni->next = head;
 129     head = ni;
 130 }
 131
 132 template <class Type> Boolean List<Type>::remove(void *key)
 133 {
 134     ListItem<Type> *lag;
 135     ListItem<Type> *curr;
 136
 137     for (curr=head, lag = NULL; curr; curr=curr->next) {
 138         if (curr->key == key) {
 139             break;
 140         }
 141         lag = curr;
 142     }
 143
 144     if (curr) {
 145         if (lag) {
 146             lag->next = curr->next;
 147         } else {
 148             head = curr->next;
 149         }
 150         delete(curr);
 151         return(TRUE);
 152     } else {
 153         return(FALSE);
 154     }
 155 }
 156
 157 template <class Type> Type List<Type>::find(void *data)
 158 {
 159     ListItem<Type> *curr;
 160
 161     for (curr=head; curr; curr=curr->next) {
 162         if (curr->key == data) {
 163             return(curr->data);
 164         }
 165     }
 166     return((Type) 0);
 167 }
 168
 169 template <class Type> class HTable {
 170
 171     public:
 172         HTable(Type data) { HTable(); add(data, (void *) data); }
 173         HTable();
 174         void add(Type data, void *key);
 175         Boolean addUnique(Type data, void *key) {
 176             Type temp;
 177
 178             temp = find(key);
 179             if (temp ) {
 180                 return(0);
 181             } else {
 182                 add(data, key);
 183                 return(1);
 184             }
 185         }
 186         Type find(void *key);
 187         Boolean remove(void *key);
 188         Type operator *() {
 189             Type curr;
 190
 191             curr = *currList;
 192             if (curr) return(curr);
 193             for (currHid++; currHid < tableSize; currHid++) {
 194                 if (table[currHid]) {
 195                     currList = *table[currHid];
 196                     curr = *currList;
 197                     if (curr) return(curr);
 198                 }
 199             }
 200             return(NULL);
 201         }
 202         Type operator ++() {
 203             Type curr;
 204
 205             curr = *currList;
 206             currList++;
 207             return(curr);
 208         }
 209         int count()     {
 210             int i, total;
 211
 212             total = 0;
 213             for (i=0; i < tableSize; i++) {
 214                 if (table[i]) {
 215                     total += table[i]->count();
 216                 }
 217             }
 218             return(total);
 219         }
 220     private:
 221         List<Type> **table;
 222         List<Type> currList;
 223         int currHid;
 224         int tableSize;
 225 };
 226
 227 template <class Type> HTable<Type>::HTable()
 228 {
 229     table = NULL;
 230     currHid = 0;
 231     tableSize = 0;
 232 }
 233
 234 template <class Type> Type HTable<Type>::find(void *key)
 235 {
 236     int hid;
 237
 238     if (!tableSize) return(NULL);
 239     hid = ListHash(key, tableSize);
 240     if (!table[hid]) {
 241         return(NULL);
 242     } else {
 243         return(table[hid]->find(key));
 244     }
 245 }
 246
 247 template <class Type> void HTable<Type>::add(Type data, void *key)
 248 {
 249     int hid;
 250
 251     if (!tableSize) {
 252         tableSize = 97;
 253         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
 254     }
 255     hid = ListHash(key, tableSize);
 256     if (!table[hid]) {
 257         table[hid] = new(List<Type>);
 258     }
 259     table[hid]->add(data, key);
 260 }
 261
 262
 263 template <class Type> Boolean HTable<Type>::remove(void *key)
 264 {
 265     int hid;
 266
 267     hid = ListHash(key, tableSize);
 268     if (table[hid]) {
 269         return(table[hid]->remove(key));
 270     }
 271     return(FALSE);
 272 }
 273
 274 template <class Type> class StringList: public List<Type> {
 275     public:
 276         Type find(void *key);
 277 };
 278
 279 template <class Type> Type StringList<Type>::find(void *data)
 280 {
 281     ListItem<Type> *curr;
 282
 283     for (curr=head; curr; curr=curr->next) {
 284         if (!strcmp((char *) curr->key, (char *) data)) {
 285             return(curr->data);
 286         }
 287     }
 288     return((Type) 0);
 289 }
 290
 291 #endif /* LIST_H */