WINGs/bag.c

   1
   2
   3 #include <stdlib.h>
   4 #include <string.h>
   5
   6 #include "WUtil.h"
   7
   8
   9
  10 struct W_Bag {
  11     int size;
  12     int count;
  13
  14     void **items;
  15 };
  16
  17
  18
  19
  20 WMBag*
  21 WMCreateBag(int size)
  22 {
  23     WMBag *bag;
  24
  25     wassertrv(size > 0, NULL);
  26
  27     bag = wmalloc(sizeof(WMBag));
  28
  29     bag->items = wmalloc(sizeof(void*) * size);
  30     bag->size = size;
  31     bag->count = 0;
  32
  33     return bag;
  34 }
  35
  36
  37
  38 int
  39 WMGetBagItemCount(WMBag *bag)
  40 {
  41     return bag->count;
  42 }
  43
  44
  45
  46 void
  47 WMAppendBag(WMBag *bag, WMBag *appendedBag)
  48 {
  49     bag->items = wrealloc(bag->items,
  50                           sizeof(void*) * (bag->size+appendedBag->count));
  51
  52     memcpy(bag->items + bag->count, appendedBag->items,
  53           sizeof(void*) * appendedBag->count);
  54
  55     bag->count += appendedBag->count;
  56     bag->size += appendedBag->count;
  57 }
  58
  59
  60
  61 void
  62 WMPutInBag(WMBag *bag, void *item)
  63 {
  64     WMInsertInBag(bag, bag->count, item);
  65 }
  66
  67
  68
  69 void
  70 WMInsertInBag(WMBag *bag, int index, void *item)
  71 {
  72     if (bag->count == bag->size) {
  73         bag->size += 16;
  74         bag->items = wrealloc(bag->items, sizeof(void*) * bag->size);
  75     }
  76
  77     if (index >= 0 && index < bag->count) {
  78         memmove(&bag->items[index+1], &bag->items[index],
  79                 (bag->count - index) * sizeof(void*));
  80     } else {
  81         /* If index is invalid, place it at end */
  82         index = bag->count;
  83     }
  84     bag->items[index] = item;
  85     bag->count++;
  86 }
  87
  88
  89 int
  90 WMGetFirstInBag(WMBag *bag, void *item)
  91 {
  92     int i;
  93
  94     for (i = 0; i < bag->count; i++) {
  95         if (bag->items[i] == item) {
  96             return i;
  97         }
  98     }
  99     return -1;
 100 }
 101
 102
 103 int
 104 WMGetLastInBag(WMBag *bag, void *item)
 105 {
 106     int i;
 107
 108     for (i = bag->count-1; i>= 0; i--) {
 109         if (bag->items[i] == item) {
 110             return i;
 111         }
 112     }
 113     return -1;
 114 }
 115
 116
 117 void
 118 WMRemoveFromBag(WMBag *bag, void *item)
 119 {
 120     int i;
 121
 122     i = WMGetFirstInBag(bag, item);
 123     if (i >= 0) {
 124         WMDeleteFromBag(bag, i);
 125     }
 126 }
 127
 128
 129
 130 void
 131 WMDeleteFromBag(WMBag *bag, int index)
 132 {
 133     wassertr(index >= 0 && index < bag->count);
 134
 135     if (index < bag->count-1) {
 136         memmove(&bag->items[index], &bag->items[index + 1],
 137                 (bag->count - index - 1) * sizeof(void*));
 138     }
 139     bag->count--;
 140 }
 141
 142
 143 void*
 144 WMGetFromBag(WMBag *bag, int index)
 145 {
 146     wassertrv(index >= 0 && index < bag->count, NULL);
 147
 148     return bag->items[index];
 149 }
 150
 151
 152 int
 153 WMCountInBag(WMBag *bag, void *item)
 154 {
 155     int i, j;
 156
 157     for (j = 0, i = 0; j < bag->count; j++) {
 158         if (bag->items[j] == item)
 159             i++;
 160     }
 161     return i;
 162 }
 163
 164
 165
 166 void
 167 WMSortBag(WMBag *bag, int (*comparer)(const void*, const void*))
 168 {
 169     qsort(bag->items, bag->count, sizeof(void*), comparer);
 170 }
 171
 172
 173
 174 void
 175 WMFreeBag(WMBag *bag)
 176 {
 177     wfree(bag->items);
 178     wfree(bag);
 179 }
 180
 181
 182 void
 183 WMEmptyBag(WMBag *bag)
 184 {
 185     bag->count = 0;
 186 }
 187
 188
 189
 190 WMBag*
 191 WMMapBag(WMBag *bag, void *(*function)(void *))
 192 {
 193     int i;
 194     WMBag *new = WMCreateBag(bag->size);
 195
 196     for (i = 0; i < bag->count; i++) {
 197         WMPutInBag(new, (*function)(bag->items[i]));
 198     }
 199
 200     return new;
 201 }
 202
 203
 204 void*
 205 WMReplaceInBag(WMBag *bag, int index, void *item)
 206 {
 207     void *old;
 208
 209     wassertrv(index >= 0 && index < bag->count, NULL);
 210
 211     old = bag->items[index];
 212
 213     bag->items[index] = item;
 214
 215     return old;
 216 }