From 595d2b060b1ba50bc8fbbcdd1cd22bc86403bcce Mon Sep 17 00:00:00 2001 From: dan Date: Fri, 15 Sep 2000 04:57:31 +0000 Subject: [PATCH] Removed array bag, and restructured the tree bag to be WMBag --- WINGs/ChangeLog | 4 + WINGs/Makefile.am | 2 - WINGs/Tests/testtext.c | 8 +- WINGs/WUtil.h | 104 +-- WINGs/array.c | 152 ++++ WINGs/bagarray.c | 418 ----------- WINGs/bagtree.c | 1841 ++++++++++++++++++++++++------------------------ WINGs/wtext.c | 4 +- 8 files changed, 1117 insertions(+), 1416 deletions(-) create mode 100644 WINGs/array.c delete mode 100644 WINGs/bagarray.c rewrite WINGs/bagtree.c (64%) diff --git a/WINGs/ChangeLog b/WINGs/ChangeLog index 2dbc1f2f..e91972e7 100644 --- a/WINGs/ChangeLog +++ b/WINGs/ChangeLog @@ -11,6 +11,10 @@ changes since wmaker 0.62.1: - added WMCreateTabViewItem() - added W_CreateUnmanagedTopView() - added wtokenize() +- restructured the directory tree. Added Documentation, Examples and Tests + subdirectories +- removed WMArrayBag and reorganized WMTreeBag to be WMBag. + changes since wmaker 0.62.0: ............................ diff --git a/WINGs/Makefile.am b/WINGs/Makefile.am index 8150b3c7..1c580ae8 100644 --- a/WINGs/Makefile.am +++ b/WINGs/Makefile.am @@ -68,7 +68,6 @@ libWINGs_a_SOURCES = \ wview.c \ error.c \ findfile.c \ - bagarray.c \ bagtree.c \ connection.c \ data.c \ @@ -82,7 +81,6 @@ libWINGs_a_SOURCES = \ libWUtil_a_SOURCES = \ WINGs.h \ WINGsP.h \ - bagarray.c \ bagtree.c \ connection.c \ data.c \ diff --git a/WINGs/Tests/testtext.c b/WINGs/Tests/testtext.c index 76b0acee..e6ec8013 100644 --- a/WINGs/Tests/testtext.c +++ b/WINGs/Tests/testtext.c @@ -1,8 +1,12 @@ -#include "WINGs.h" + #include +#include + +#include "WINGs.h" + +WMScreen *scr; -WMScreen *scr; void wAbort() diff --git a/WINGs/WUtil.h b/WINGs/WUtil.h index a3bccb00..8317cc92 100644 --- a/WINGs/WUtil.h +++ b/WINGs/WUtil.h @@ -158,35 +158,11 @@ typedef struct { void (*releaseKey)(const void *); } WMHashTableCallbacks; - + typedef void *WMBagIterator; -typedef struct W_BagFunctions { - int (*getItemCount)(WMBag *self); - int (*appendBag)(WMBag *self, WMBag *bag); - int (*putInBag)(WMBag *self, void *item); - int (*insertInBag)(WMBag *self, int index, void *item); - int (*removeFromBag)(WMBag *bag, void *item); - int (*eraseFromBag)(WMBag *bag, int index); - int (*deleteFromBag)(WMBag *bag, int index); - void *(*getFromBag)(WMBag *bag, int index); - int (*firstInBag)(WMBag *bag, void *item); - int (*countInBag)(WMBag *bag, void *item); - void *(*replaceInBag)(WMBag *bag, int index, void *item); - int (*sortBag)(WMBag *bag, int (*comparer)(const void*, const void*)); - void (*emptyBag)(WMBag *bag); - void (*freeBag)(WMBag *bag); - void (*mapBag)(WMBag *bag, void (*function)(void*, void*), void *data); - int (*findInBag)(WMBag *bag, int (*match)(void*, void*), void *cdata); - void *(*first)(WMBag *bag, WMBagIterator *ptr); - void *(*last)(WMBag *bag, WMBagIterator *ptr); - void *(*next)(WMBag *bag, WMBagIterator *ptr); - void *(*previous)(WMBag *bag, WMBagIterator *ptr); - void *(*iteratorAtIndex)(WMBag *bag, int index, WMBagIterator *ptr); - int (*indexForIterator)(WMBag *bag, WMBagIterator ptr); -} W_BagFunctions; - +#if 0 struct W_Bag { void *data; @@ -194,6 +170,7 @@ struct W_Bag { W_BagFunctions func; }; +#endif @@ -373,77 +350,74 @@ WMBag* WMCreateArrayBagWithDestructor(int initialSize, * O(lg n) insertion/deletion/search * Slow for storing small numbers of elements */ -WMBag *WMCreateTreeBag(void); -WMBag *WMCreateTreeBagWithDestructor(void (*destructor)(void*)); - -#define WMCreateArrayBag(a) WMCreateTreeBag() -#define WMCreateArrayBagWithDestructor(a,d) WMCreateTreeBagWithDestructor(d) - #define WMCreateBag(size) WMCreateTreeBag() #define WMCreateBagWithDestructor(size, d) WMCreateTreeBagWithDestructor(d) -#define WMGetBagItemCount(bag) bag->func.getItemCount(bag) +WMBag* WMCreateTreeBag(void); -#define WMAppendBag(bag, other) bag->func.appendBag(bag, other) +WMBag* WMCreateTreeBagWithDestructor(void (*destructor)(void*)); -#define WMPutInBag(bag, item) bag->func.putInBag(bag, item) +int WMGetBagItemCount(WMBag *self); + +int WMAppendBag(WMBag *self, WMBag *bag); + +int WMPutInBag(WMBag *self, void *item); /* insert will increment the index of elements after it by 1 */ -#define WMInsertInBag(bag, index, item) bag->func.insertInBag(bag, index, item) +int WMInsertInBag(WMBag *self, int index, void *item); /* this is slow */ /* erase will remove the element from the bag, * but will keep the index of the other elements unchanged */ -#define WMEraseFromBag(bag, index) bag->func.eraseFromBag(bag, index) +int WMEraseFromBag(WMBag *self, int index); /* delete and remove will remove the elements and cause the elements * after them to decrement their indexes by 1 */ -#define WMRemoveFromBag(bag, item) bag->func.removeFromBag(bag, item) +int WMRemoveFromBag(WMBag *self, void *item); -#define WMDeleteFromBag(bag, index) bag->func.deleteFromBag(bag, index) +int WMDeleteFromBag(WMBag *self, int index); -#define WMGetFromBag(bag, index) bag->func.getFromBag(bag, index) +void* WMGetFromBag(WMBag *self, int index); -#define WMCountInBag(bag, item) bag->func.countInBag(bag, item) +void* WMReplaceInBag(WMBag *self, int index, void *item); -#define WMReplaceInBag(bag, index, item) bag->func.replaceInBag(bag, index, item) -#define WMSetInBag(bag, index, item) bag->func.replaceInBag(bag, index, item) +#define WMSetInBag(bag, index, item) WMReplaceInBag(bag, index, item) /* comparer must return: * < 0 if a < b * > 0 if a > b * = 0 if a = b */ -#define WMSortBag(bag, comparer) bag->func.sortBag(bag, comparer) +int WMSortBag(WMBag *self, int (*comparer)(const void*, const void*)); -#define WMEmptyBag(bag) bag->func.emptyBag(bag) - -#define WMFreeBag(bag) bag->func.freeBag(bag) +void WMEmptyBag(WMBag *self); -#define WMMapBag(bag, function, cdata) bag->func.mapBag(bag, function, cdata) +void WMFreeBag(WMBag *self); -#define WMGetFirstInBag(bag, item) bag->func.firstInBag(bag, item) - -#define WMCountInBag(bag, item) bag->func.countInBag(bag, item) +void WMMapBag(WMBag *self, void (*function)(void*, void*), void *data); -#define WMFindInBag(bag, match, cdata) bag->func.findInBag(bag, match, cdata) - -#define WMBagFirst(bag, ptr) bag->func.first(bag, ptr) +int WMGetFirstInBag(WMBag *self, void *item); -#define WMBagLast(bag, ptr) bag->func.last(bag, ptr) - -#define WMBagNext(bag, ptr) bag->func.next(bag, ptr) - -#define WMBagPrevious(bag, ptr) bag->func.previous(bag, ptr) +int WMCountInBag(WMBag *self, void *item); + +int WMFindInBag(WMBag *self, int (*match)(void*,void*), void *cdata); + +void* WMBagFirst(WMBag *self, WMBagIterator *ptr); + +void* WMBagLast(WMBag *self, WMBagIterator *ptr); + +void* WMBagNext(WMBag *self, WMBagIterator *ptr); + +void* WMBagPrevious(WMBag *self, WMBagIterator *ptr); + +void* WMBagIteratorAtIndex(WMBag *self, int index, WMBagIterator *ptr); + +int WMBagIndexForIterator(WMBag *bag, WMBagIterator ptr); -#define WMBagIteratorAtIndex(bag, index, ptr) bag->func.iteratorAtIndex(bag, index, ptr) -#define WMBagIndexForIterator(bag, ptr) bag->func.indexForIterator(bag, ptr) - - #define WM_ITERATE_BAG(bag, var, i) \ for (var = WMBagFirst(bag, &(i)); (i) != NULL; \ var = WMBagNext(bag, &(i))) @@ -452,8 +426,8 @@ WMBag *WMCreateTreeBagWithDestructor(void (*destructor)(void*)); for (var = WMBagLast(bag, &(i)); (i) != NULL; \ var = WMBagPrevious(bag, &(i))) - - + + /*-------------------------------------------------------------------------*/ /* WMData handling */ diff --git a/WINGs/array.c b/WINGs/array.c new file mode 100644 index 00000000..f7249218 --- /dev/null +++ b/WINGs/array.c @@ -0,0 +1,152 @@ +/* + * Dynamically Resized Array + * + * Authors: Alfredo K. Kojima + * Dan Pascu + * + * This code is released to the Public Domain, but + * proper credit is always appreciated :) + */ + + +#include +#include + +#include "WUtil.h" + + +#define INITIAL_SIZE 8 +#define RESIZE_INCREMENT 8 + + +typedef struct { + void **items; /* the array data */ + unsigned length; /* # of items in array */ + unsigned allocSize; /* allocated size of array */ +} W_Array; + + +WMArray* +WMCreateArray(unsigned initialSize) +{ + Array *a; + + a = malloc(sizeof(Array)); + sassertrv(a!=NULL, NULL); + + if (initialSize == 0) { + initialSize = INITIAL_SIZE; + } + + a->items = malloc(sizeof(void*)*initialSize); + sassertdo(a->items!=NULL, + free(a); + return NULL; + ); + a->length = 0; + a->allocSize = initialSize; + + return a; +} + + +void ArrayFree(Array *array) +{ + free(array->items); + free(array); +} + + +void ArrayClear(Array *array) +{ + memset(array->items, 0, array->length*sizeof(void*)); + array->length = 0; +} + + +int ArraySet(Array *array, unsigned index, void *data) +{ + sassertrv(index > array->length, 0); + + if (index == array->length) + return ArrayAppend(array, data); + + array->items[index] = data; + + return 1; +} + + +#if 0 +void *ArrayGet(Array *array, unsigned index) +{ + return array->items[index]; +} +#endif + + +int ArrayAppend(Array *array, void *data) +{ + if (array->length >= array->allocSize) { + array->allocSize += RESIZE_INCREMENT; + array->items = realloc(array->items, sizeof(void*)*array->allocSize); + sassertrv(array->items != NULL, 0); + } + array->items[array->length++] = data; + + return 1; +} + + +int ArrayInsert(Array *array, unsigned index, void *data) +{ + sassertrv(index < array->length, 0); + + if (array->length >= array->allocSize) { + array->allocSize += RESIZE_INCREMENT; + array->items = realloc(array->items, sizeof(void*)*array->allocSize); + sassertrv(array->items != NULL, 0); + } + if (index < array->length-1) + memmove(array->items+index+1, array->items+index, + sizeof(void*)*(array->length-index)); + array->items[index] = data; + + array->length++; + + return 1; +} + + +void ArrayDelete(Array *array, unsigned index) +{ + sassertr(index < array->length); + + memmove(array->items+index, array->items+index+1, + sizeof(void*)*(array->length-index-1)); + + array->length--; +} + + + +void *ArrayPop(Array *array) +{ + void *d = ArrayGet(array, array->length-1); + + ArrayDelete(array, array->length-1); + + return d; +} + + +int ArrayIndex(Array *array, void *data) +{ + unsigned i; + + for (i = 0; i < array->length; i++) + if (array->items[i] == data) + return i; + + return -1; +} diff --git a/WINGs/bagarray.c b/WINGs/bagarray.c deleted file mode 100644 index bb42c778..00000000 --- a/WINGs/bagarray.c +++ /dev/null @@ -1,418 +0,0 @@ - - - - -#include -#include - -#include "WUtil.h" - -#if 0 - -typedef struct W_ArrayBag { - void **items; - int size; - int count; - - int base; - int first; - int last; -} W_ArrayBag; - - -static int getItemCount(WMBag *bag); -static int appendBag(WMBag *bag, WMBag *appendedBag); -static int putInBag(WMBag *bag, void *item); -static int insertInBag(WMBag *bag, int index, void *item); -static int removeFromBag(WMBag *bag, void *item); -static int deleteFromBag(WMBag *bag, int index); -static void* getFromBag(WMBag *bag, int index); -static int firstInBag(WMBag *bag, void *item); -static int countInBag(WMBag *bag, void *item); -static void* replaceInBag(WMBag *bag, int index, void *item); -static int sortBag(WMBag *bag, int (*comparer)(const void*, const void*)); -static void emptyBag(WMBag *bag); -static void freeBag(WMBag *bag); -static void mapBag(WMBag *bag, void (*function)(void*, void*), void *data); -static int findInBag(WMBag *bag, int (*match)(void*)); -static void* first(WMBag *bag, void **ptr); -static void* last(WMBag *bag, void **ptr); -static void* next(WMBag *bag, void **ptr); -static void* previous(WMBag *bag, void **ptr); -static void* iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr); -static int indexForIterator(WMBag *bag, WMBagIterator ptr); - - -static W_BagFunctions arrayFunctions = { - getItemCount, - appendBag, - putInBag, - insertInBag, - removeFromBag, - deleteFromBag, - deleteFromBag, - getFromBag, - firstInBag, - countInBag, - replaceInBag, - sortBag, - emptyBag, - freeBag, - mapBag, - findInBag, - first, - last, - next, - previous, - iteratorAtIndex, - indexForIterator -}; - - -#define ARRAY ((W_ArrayBag*)(bag->data)) - - -#define I2O(a, i) ((a)->base + i) - - -WMBag* -WMCreateArrayBagWithDestructor(int initialSize, void (*destructor)(void*)) -{ - WMBag *bag; - W_ArrayBag *array; - int size; - - assert(0&&"array bag is not working"); - bag = wmalloc(sizeof(WMBag)); - - array = wmalloc(sizeof(W_ArrayBag)); - - bag->data = array; - - array->items = wmalloc(sizeof(void*) * size); - array->size = size; - array->count = 0; - array->first = 0; - array->last = 0; - array->base = 0; - - bag->func = arrayFunctions; - - bag->destructor = destructor; - - return bag; -} - - -WMBag* -WMCreateArrayBag(int initialSize) -{ - return WMCreateArrayBagWithDestructor(initialSize, NULL); -} - - -static int -getItemCount(WMBag *bag) -{ - return ARRAY->count; -} - - -static int -appendBag(WMBag *bag, WMBag *appendedBag) -{ - W_ArrayBag *array = (W_ArrayBag*)appendedBag->data; - int ok; - int i; - - for (i = array->first; i <= array->last; i++) { - if (array->items[array->base+i]) { - ok = putInBag(bag, array->items[array->base+i]); - if (!ok) - return 0; - } - } - - return 1; -} - - - -static int -putInBag(WMBag *bag, void *item) -{ - return insertInBag(bag, ARRAY->last+1, item); -} - - - -static int -insertInBag(WMBag *bag, int index, void *item) -{ - W_ArrayBag *array = ARRAY; - - if (I2O(array, index) >= array->size) { - array->size = WMAX(array->size + 16, I2O(array, index)); - array->items = wrealloc(array->items, sizeof(void*) * array->size); - memset(array->items + I2O(array, array->last), 0, - sizeof(void*) * (array->size - I2O(array, array->last))); - } - - if (index > array->last) { - array->last = index; - } else if (index >= array->first) { - memmove(array->items + I2O(array, index), - array->items + (I2O(array, index) + 1), sizeof(void*)); - array->last++; - } else { - memmove(array->items, - array->items + (abs(index) - array->base), - sizeof(void*) * (abs(index) - array->base)); - memset(array->items, 0, sizeof(void*) * (abs(index) - array->base)); - array->first = index; - array->base = abs(index); - } - - array->items[array->base + index] = item; - array->count++; - - return 1; -} - - -static int -removeFromBag(WMBag *bag, void *item) -{ - int i; - W_ArrayBag *array = ARRAY; - - for (i = 0; i < array->count; i++) { - if (array->items[i] == item) { - if (bag->destructor) - bag->destructor(array->items[i]); - - memmove(&array->items[i], &array->items[i + 1], - (array->count - i - 1) * sizeof(void*)); - array->count--; - - return 1; - } - } - - return 0; -} - - - -static int -deleteFromBag(WMBag *bag, int index) -{ - W_ArrayBag *array = ARRAY; - - if (index < 0 || index >= array->count) - return 0; - - if (index < array->count-1) { - if (bag->destructor) - bag->destructor(array->items[index]); - - memmove(&array->items[index], &array->items[index + 1], - (array->count - index - 1) * sizeof(void*)); - } - array->count--; - - return 1; -} - - -static void* -getFromBag(WMBag *bag, int index) -{ - if (index < 0 || index >= ARRAY->count) - return NULL; - - return ARRAY->items[index]; -} - - -static int -firstInBag(WMBag *bag, void *item) -{ - int j; - int count = ARRAY->count; - W_ArrayBag *array = ARRAY; - - for (j = 0; j < count; j++) { - if (array->items[j] == item) - return j; - } - return -1; -} - - - - -static int -countInBag(WMBag *bag, void *item) -{ - int i, j; - int count = ARRAY->count; - W_ArrayBag *array = ARRAY; - - for (j = 0, i = 0; j < count; j++) { - if (array->items[j] == item) - i++; - } - return i; -} - - -static void* -replaceInBag(WMBag *bag, int index, void *item) -{ - void *old; - - if (index < 0 || index >= ARRAY->count) - return NULL; - - old = ARRAY->items[index]; - - ARRAY->items[index] = item; - - return old; -} - - -static int -sortBag(WMBag *bag, int (*comparer)(const void*, const void*)) -{ - qsort(ARRAY->items, ARRAY->count, sizeof(void*), comparer); - return 1; -} - - - -static void -emptyBag(WMBag *bag) -{ - W_ArrayBag *array = ARRAY; - - if (bag->destructor) { - while (--array->count) { - bag->destructor(array->items[array->count]); - } - } - ARRAY->count=0; -} - - -static void -freeBag(WMBag *bag) -{ - emptyBag(bag); - - wfree(ARRAY->items); - wfree(ARRAY); - wfree(bag); -} - - -static void -mapBag(WMBag *bag, void (*function)(void *, void *), void *clientData) -{ - int i; - - for (i = 0; i < ARRAY->last; i++) { - if (ARRAY->items[i]) - (*function)(ARRAY->items[i], clientData); - } -} - - -static int -findInBag(WMBag *bag, int (*match)(void*)) -{ - int i; - - for (i = 0; i < ARRAY->last; i++) { - if ((*match)(ARRAY->items[i])) - return i; - } - - return -1; -} - - -static void* -first(WMBag *bag, void **ptr) -{ - *ptr = NULL; - - if (ARRAY->count == 0) - return NULL; - - *(int**)ptr = 0; - return ARRAY->items[0]; -} - - -static void* -last(WMBag *bag, void **ptr) -{ - *ptr = NULL; - - if (ARRAY->count == 0) - return NULL; - - *(int*)ptr = ARRAY->count-1; - - return ARRAY->items[ARRAY->count-1]; -} - - -static void* -next(WMBag *bag, void **ptr) -{ - if (!*ptr) - return NULL; - - (*(int*)ptr)++; - if (*(int*)ptr >= ARRAY->count) { - *ptr = NULL; - return NULL; - } - - return ARRAY->items[*(int*)ptr]; -} - - -static void* -previous(WMBag *bag, void **ptr) -{ - if (!*ptr) - return NULL; - - (*(int*)ptr)--; - if (*(int*)ptr < 0) { - *ptr = NULL; - return NULL; - } - - return ARRAY->items[*(int*)ptr]; -} - - - -static void* -iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr) -{ -} - - -static int -indexForIterator(WMBag *bag, WMBagIterator ptr) -{ - -} - -#endif diff --git a/WINGs/bagtree.c b/WINGs/bagtree.c dissimilarity index 64% index 65507124..9787ad1c 100644 --- a/WINGs/bagtree.c +++ b/WINGs/bagtree.c @@ -1,927 +1,914 @@ - - - - -#include -#include - -#include "WUtil.h" - - -typedef struct W_Node { - struct W_Node *parent; - struct W_Node *left; - struct W_Node *right; - int color; - - void *data; - int index; -} W_Node; - - -typedef struct W_TreeBag { - W_Node *root; - - W_Node *nil; /* sentinel */ - - int count; -} W_TreeBag; - - - -static int getItemCount(WMBag *self); -static int appendBag(WMBag *self, WMBag *bag); -static int putInBag(WMBag *self, void *item); -static int insertInBag(WMBag *self, int index, void *item); -static int removeFromBag(WMBag *bag, void *item); -static int eraseFromBag(WMBag *bag, int index); -static int deleteFromBag(WMBag *bag, int index); -static void *getFromBag(WMBag *bag, int index); -static int countInBag(WMBag *bag, void *item); -static int firstInBag(WMBag *bag, void *item); -static void *replaceInBag(WMBag *bag, int index, void *item); -static int sortBag(WMBag *bag, int (*comparer)(const void*, const void*)); -static void emptyBag(WMBag *bag); -static void freeBag(WMBag *bag); -static void mapBag(WMBag *bag, void (*function)(void*, void*), void *data); -static int findInBag(WMBag *bag, int (*match)(void*,void*), void *data); -static void *first(WMBag *bag, WMBagIterator *ptr); -static void *last(WMBag *bag, WMBagIterator *ptr); -static void *next(WMBag *bag, WMBagIterator *ptr); -static void *previous(WMBag *bag, WMBagIterator *ptr); -static void *iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr); -static int indexForIterator(WMBag *bag, WMBagIterator ptr); - - -static W_BagFunctions bagFunctions = { - getItemCount, - appendBag, - putInBag, - insertInBag, - removeFromBag, - eraseFromBag, - deleteFromBag, - getFromBag, - firstInBag, - countInBag, - replaceInBag, - sortBag, - emptyBag, - freeBag, - mapBag, - findInBag, - first, - last, - next, - previous, - iteratorAtIndex, - indexForIterator -}; - - - - -#define IS_LEFT(node) (node == node->parent->left) -#define IS_RIGHT(node) (node == node->parent->right) - - - -static void leftRotate(W_TreeBag *tree, W_Node *node) -{ - W_Node *node2; - - node2 = node->right; - node->right = node2->left; - - node2->left->parent = node; - - node2->parent = node->parent; - - if (node->parent == tree->nil) { - tree->root = node2; - } else { - if (IS_LEFT(node)) { - node->parent->left = node2; - } else { - node->parent->right = node2; - } - } - node2->left = node; - node->parent = node2; -} - - - -static void rightRotate(W_TreeBag *tree, W_Node *node) -{ - W_Node *node2; - - node2 = node->left; - node->left = node2->right; - - node2->right->parent = node; - - node2->parent = node->parent; - - if (node->parent == tree->nil) { - tree->root = node2; - } else { - if (IS_LEFT(node)) { - node->parent->left = node2; - } else { - node->parent->right = node2; - } - } - node2->right = node; - node->parent = node2; -} - - - -static void treeInsert(W_TreeBag *tree, W_Node *node) -{ - W_Node *y = tree->nil; - W_Node *x = tree->root; - - while (x != tree->nil) { - y = x; - if (node->index <= x->index) - x = x->left; - else - x = x->right; - } - node->parent = y; - if (y == tree->nil) - tree->root = node; - else if (node->index <= y->index) - y->left = node; - else - y->right = node; -} - - -static void rbTreeInsert(W_TreeBag *tree, W_Node *node) -{ - W_Node *y; - - treeInsert(tree, node); - - node->color = 'R'; - - while (node != tree->root && node->parent->color == 'R') { - if (IS_LEFT(node->parent)) { - y = node->parent->parent->right; - - if (y->color == 'R') { - - node->parent->color = 'B'; - y->color = 'B'; - node->parent->parent->color = 'R'; - node = node->parent->parent; - - } else { - if (IS_RIGHT(node)) { - node = node->parent; - leftRotate(tree, node); - } - node->parent->color = 'B'; - node->parent->parent->color = 'R'; - rightRotate(tree, node->parent->parent); - } - } else { - y = node->parent->parent->left; - - if (y->color == 'R') { - - node->parent->color = 'B'; - y->color = 'B'; - node->parent->parent->color = 'R'; - node = node->parent->parent; - - } else { - if (IS_LEFT(node)) { - node = node->parent; - rightRotate(tree, node); - } - node->parent->color = 'B'; - node->parent->parent->color = 'R'; - leftRotate(tree, node->parent->parent); - } - } - } - tree->root->color = 'B'; -} - - - -static void rbDeleteFixup(W_TreeBag *tree, W_Node *node) -{ - W_Node *w; - - while (node != tree->root && node->color == 'B') { - if (IS_LEFT(node)) { - w = node->parent->right; - if (w->color == 'R') { - w->color = 'B'; - node->parent->color = 'R'; - leftRotate(tree, node->parent); - w = node->parent->right; - } - if (w->left->color == 'B' && w->right->color == 'B') { - w->color = 'R'; - node = node->parent; - } else { - if (w->right->color == 'B') { - w->left->color = 'B'; - w->color = 'R'; - rightRotate(tree, w); - w = node->parent->right; - } - w->color = node->parent->color; - node->parent->color = 'B'; - w->right->color = 'B'; - leftRotate(tree, node->parent); - node = tree->root; - } - } else { - w = node->parent->left; - if (w->color == 'R') { - w->color = 'B'; - node->parent->color = 'R'; - rightRotate(tree, node->parent); - w = node->parent->left; - } - if (w->left->color == 'B' && w->right->color == 'B') { - w->color = 'R'; - node = node->parent; - } else { - if (w->left->color == 'B') { - w->right->color = 'B'; - w->color = 'R'; - leftRotate(tree, w); - w = node->parent->left; - } - w->color = node->parent->color; - node->parent->color = 'B'; - w->left->color = 'B'; - rightRotate(tree, node->parent); - node = tree->root; - } - } - } - node->color = 'B'; - -} - - -static W_Node *treeMinimum(W_Node *node, W_Node *nil) -{ - while (node->left != nil) - node = node->left; - return node; -} - - -static W_Node *treeMaximum(W_Node *node, W_Node *nil) -{ - while (node->right != nil) - node = node->right; - return node; -} - - -static W_Node *treeSuccessor(W_Node *node, W_Node *nil) -{ - W_Node *y; - - if (node->right != nil) { - return treeMinimum(node->right, nil); - } - y = node->parent; - while (y != nil && node == y->right) { - node = y; - y = y->parent; - } - return y; -} - - -static W_Node *treePredecessor(W_Node *node, W_Node *nil) -{ - W_Node *y; - - if (node->left != nil) { - return treeMaximum(node->left, nil); - } - y = node->parent; - while (y != nil && node == y->left) { - node = y; - y = y->parent; - } - return y; -} - - -static W_Node *rbTreeDelete(W_TreeBag *tree, W_Node *node) -{ - W_Node *nil = tree->nil; - W_Node *x, *y; - - if (node->left == nil || node->right == nil) { - y = node; - } else { - y = treeSuccessor(node, nil); - } - - if (y->left != nil) { - x = y->left; - } else { - x = y->right; - } - - x->parent = y->parent; - - if (y->parent == nil) { - tree->root = x; - } else { - if (IS_LEFT(y)) { - y->parent->left = x; - } else { - y->parent->right = x; - } - } - if (y != node) { - node->index = y->index; - node->data = y->data; - } - if (y->color == 'B') { - rbDeleteFixup(tree, x); - } - - return y; -} - - - -static W_Node *treeSearch(W_Node *root, W_Node *nil, int index) -{ - if (root == nil || root->index == index) { - return root; - } - - if (index < root->index) { - return treeSearch(root->left, nil, index); - } else { - return treeSearch(root->right, nil, index); - } -} - - -static W_Node *treeFind(W_Node *root, W_Node *nil, void *data) -{ - W_Node *tmp; - - if (root == nil || root->data == data) - return root; - - tmp = treeFind(root->left, nil, data); - if (tmp != nil) - return tmp; - - tmp = treeFind(root->right, nil, data); - - return tmp; -} - - - - - -#if 0 -static char buf[512]; - -static void printNodes(W_Node *node, W_Node *nil, int depth) -{ - if (node == nil) { - return; - } - - printNodes(node->left, nil, depth+1); - - memset(buf, ' ', depth*2); - buf[depth*2] = 0; - if (IS_LEFT(node)) - printf("%s/(%2i\n", buf, node->index); - else - printf("%s\\(%2i\n", buf, node->index); - - printNodes(node->right, nil, depth+1); -} - - -void PrintTree(WMBag *bag) -{ - W_TreeBag *tree = (W_TreeBag*)bag->data; - - printNodes(tree->root, tree->nil, 0); -} -#endif - - - - -#define SELF ((W_TreeBag*)self->data) - -WMBag *WMCreateTreeBag(void) -{ - return WMCreateTreeBagWithDestructor(NULL); -} - - -WMBag *WMCreateTreeBagWithDestructor(void (*destructor)(void*)) -{ - WMBag *bag; - W_TreeBag *tree; - - bag = wmalloc(sizeof(WMBag)); - - bag->data = tree = wmalloc(sizeof(W_TreeBag)); - memset(tree, 0, sizeof(W_TreeBag)); - - tree->nil = wmalloc(sizeof(W_Node)); - memset(tree->nil, 0, sizeof(W_Node)); - tree->nil->left = tree->nil->right = tree->nil->parent = tree->nil; - tree->nil->index = WBNotFound; - - tree->root = tree->nil; - - bag->destructor = destructor; - - bag->func = bagFunctions; - - return bag; -} - - -static int getItemCount(WMBag *self) -{ - return SELF->count; -} - - -static int appendBag(WMBag *self, WMBag *bag) -{ - WMBagIterator ptr; - void *data; - - for (data = first(bag, &ptr); data != NULL; data = next(bag, &ptr)) { - if (!putInBag(self, data)) - return 0; - } - - return 1; -} - -extern WMBag *bla; - -static int putInBag(WMBag *self, void *item) -{ - W_Node *ptr; - - - ptr = wmalloc(sizeof(W_Node)); - - ptr->data = item; - ptr->index = SELF->count; - ptr->left = SELF->nil; - ptr->right = SELF->nil; - ptr->parent = SELF->nil; - - rbTreeInsert(SELF, ptr); - - SELF->count++; - - return 1; -} - - -static int insertInBag(WMBag *self, int index, void *item) -{ - W_Node *ptr; - - ptr = wmalloc(sizeof(W_Node)); - - ptr->data = item; - ptr->index = index; - ptr->left = SELF->nil; - ptr->right = SELF->nil; - ptr->parent = SELF->nil; - - rbTreeInsert(SELF, ptr); - - while ((ptr = treeSuccessor(ptr, SELF->nil)) != SELF->nil) { - ptr->index++; - } - - - SELF->count++; - - return 1; -} - - - -static int removeFromBag(WMBag *self, void *item) -{ - W_Node *ptr = treeFind(SELF->root, SELF->nil, item); - - if (ptr != SELF->nil) { - W_Node *tmp; - - SELF->count--; - - tmp = treeSuccessor(ptr, SELF->nil); - while (tmp != SELF->nil) { - tmp->index--; - tmp = treeSuccessor(tmp, SELF->nil); - } - - ptr = rbTreeDelete(SELF, ptr); - if (self->destructor) - self->destructor(ptr->data); - free(ptr); - - return 1; - } else { - return 0; - } -} - - - -static int eraseFromBag(WMBag *self, int index) -{ - W_Node *ptr = treeSearch(SELF->root, SELF->nil, index); - - if (ptr != SELF->nil) { - - SELF->count--; - - ptr = rbTreeDelete(SELF, ptr); - if (self->destructor) - self->destructor(ptr->data); - free(ptr); - - wassertrv(SELF->count == 0||SELF->root->index >= 0, 1); - - return 1; - } else { - return 0; - } -} - - -static int deleteFromBag(WMBag *self, int index) -{ - W_Node *ptr = treeSearch(SELF->root, SELF->nil, index); - - if (ptr != SELF->nil) { - W_Node *tmp; - - SELF->count--; - - tmp = treeSuccessor(ptr, SELF->nil); - while (tmp != SELF->nil) { - tmp->index--; - tmp = treeSuccessor(tmp, SELF->nil); - } - - ptr = rbTreeDelete(SELF, ptr); - if (self->destructor) - self->destructor(ptr->data); - free(ptr); - - wassertrv(SELF->count == 0||SELF->root->index >= 0, 1); - - return 1; - } else { - return 0; - } -} - - -static void *getFromBag(WMBag *self, int index) -{ - W_Node *node; - - node = treeSearch(SELF->root, SELF->nil, index); - if (node != SELF->nil) - return node->data; - else - return NULL; -} - - - -static int firstInBag(WMBag *self, void *item) -{ - W_Node *node; - - node = treeFind(SELF->root, SELF->nil, item); - if (node != SELF->nil) - return node->index; - else - return WBNotFound; -} - - - -static int treeCount(W_Node *root, W_Node *nil, void *item) -{ - int count = 0; - - if (root == nil) - return 0; - - if (root->data == item) - count++; - - if (root->left != nil) - count += treeCount(root->left, nil, item); - - if (root->right != nil) - count += treeCount(root->right, nil, item); - - return count; -} - - - -static int countInBag(WMBag *self, void *item) -{ - return treeCount(SELF->root, SELF->nil, item); -} - - -static void *replaceInBag(WMBag *self, int index, void *item) -{ - W_Node *ptr = treeSearch(SELF->root, SELF->nil, index); - void *old = NULL; - - if (item == NULL) { - SELF->count--; - ptr = rbTreeDelete(SELF, ptr); - if (self->destructor) - self->destructor(ptr->data); - free(ptr); - } else if (ptr != SELF->nil) { - old = ptr->data; - ptr->data = item; - } else { - W_Node *ptr; - - ptr = wmalloc(sizeof(W_Node)); - - ptr->data = item; - ptr->index = index; - ptr->left = SELF->nil; - ptr->right = SELF->nil; - ptr->parent = SELF->nil; - - rbTreeInsert(SELF, ptr); - - SELF->count++; - } - - return old; -} - - - - -static int sortBag(WMBag *self, int (*comparer)(const void*, const void*)) -{ - void **items; - W_Node *tmp; - int i; - - if (SELF->count == 0) - return 1; - - items = wmalloc(sizeof(void*)*SELF->count); - i = 0; - - tmp = treeMinimum(SELF->root, SELF->nil); - while (tmp != SELF->nil) { - items[i++] = tmp->data; - tmp = treeSuccessor(tmp, SELF->nil); - } - - qsort(&items[0], SELF->count, sizeof(void*), comparer); - - i = 0; - tmp = treeMinimum(SELF->root, SELF->nil); - while (tmp != SELF->nil) { - tmp->index = i; - tmp->data = items[i++]; - tmp = treeSuccessor(tmp, SELF->nil); - } - - wfree(items); - - return 1; -} - - - - -static void deleteTree(WMBag *self, W_Node *node) -{ - if (node == SELF->nil) - return; - - deleteTree(self, node->left); - - if (self->destructor) - self->destructor(node->data); - - deleteTree(self, node->right); - - free(node); -} - - -static void emptyBag(WMBag *self) -{ - deleteTree(self, SELF->root); - SELF->root = SELF->nil; - SELF->count = 0; -} - - -static void freeBag(WMBag *self) -{ - emptyBag(self); - - free(SELF->nil); - free(self->data); - - free(self); -} - - - -static void mapTree(W_TreeBag *tree, W_Node *node, - void (*function)(void*, void*), void *data) -{ - if (node == tree->nil) - return; - - mapTree(tree, node->left, function, data); - - (*function)(node->data, data); - - mapTree(tree, node->right, function, data); -} - - -static void mapBag(WMBag *self, void (*function)(void*, void*), void *data) -{ - mapTree(SELF, SELF->root, function, data); -} - - - -static int findInTree(W_TreeBag *tree, W_Node *node, - int (*function)(void*,void*), void *cdata) -{ - int index; - - if (node == tree->nil) - return WBNotFound; - - index = findInTree(tree, node->left, function, cdata); - if (index != WBNotFound) - return index; - - if ((*function)(node->data, cdata)) { - return node->index; - } - - return findInTree(tree, node->right, function, cdata); -} - - -static int findInBag(WMBag *self, int (*match)(void*,void*), void *cdata) -{ - return findInTree(SELF, SELF->root, match, cdata); -} - - - - -static void *first(WMBag *self, WMBagIterator *ptr) -{ - W_Node *node; - - node = treeMinimum(SELF->root, SELF->nil); - - if (node == SELF->nil) { - *ptr = NULL; - - return NULL; - } else { - *ptr = node; - - return node->data; - } -} - - - -static void *last(WMBag *self, WMBagIterator *ptr) -{ - - W_Node *node; - - node = treeMaximum(SELF->root, SELF->nil); - - if (node == SELF->nil) { - *ptr = NULL; - - return NULL; - } else { - *ptr = node; - - return node->data; - } -} - - - -static void *next(WMBag *self, WMBagIterator *ptr) -{ - W_Node *node; - - if (*ptr == NULL) - return NULL; - - node = treeSuccessor(*ptr, SELF->nil); - - if (node == SELF->nil) { - *ptr = NULL; - - return NULL; - } else { - *ptr = node; - - return node->data; - } -} - - - -static void *previous(WMBag *self, WMBagIterator *ptr) -{ - W_Node *node; - - if (*ptr == NULL) - return NULL; - - node = treePredecessor(*ptr, SELF->nil); - - - if (node == SELF->nil) { - *ptr = NULL; - - return NULL; - } else { - *ptr = node; - - return node->data; - } -} - - - -static void *iteratorAtIndex(WMBag *self, int index, WMBagIterator *ptr) -{ - W_Node *node; - - node = treeSearch(SELF->root, SELF->nil, index); - - if (node == SELF->nil) { - *ptr = NULL; - return NULL; - } else { - *ptr = node; - return node->data; - } -} - - -static int indexForIterator(WMBag *bag, WMBagIterator ptr) -{ - return ((W_Node*)ptr)->index; -} - + + + + +#include +#include + +#include "WUtil.h" + + +typedef struct W_Node { + struct W_Node *parent; + struct W_Node *left; + struct W_Node *right; + int color; + + void *data; + int index; +} W_Node; + + +typedef struct W_Bag { + W_Node *root; + + W_Node *nil; /* sentinel */ + + int count; + + void (*destructor)(void *item); +} W_Bag; + + +#if 0 +static int getItemCount(WMBag *self); +static int appendBag(WMBag *self, WMBag *bag); +static int putInBag(WMBag *self, void *item); +static int insertInBag(WMBag *self, int index, void *item); +static int removeFromBag(WMBag *bag, void *item); +static int eraseFromBag(WMBag *bag, int index); +static int deleteFromBag(WMBag *bag, int index); +static void *getFromBag(WMBag *bag, int index); +static int countInBag(WMBag *bag, void *item); +static int firstInBag(WMBag *bag, void *item); +static void *replaceInBag(WMBag *bag, int index, void *item); +static int sortBag(WMBag *bag, int (*comparer)(const void*, const void*)); +static void emptyBag(WMBag *bag); +static void freeBag(WMBag *bag); +static void mapBag(WMBag *bag, void (*function)(void*, void*), void *data); +static int findInBag(WMBag *bag, int (*match)(void*,void*), void *data); +static void *first(WMBag *bag, WMBagIterator *ptr); +static void *last(WMBag *bag, WMBagIterator *ptr); +static void *next(WMBag *bag, WMBagIterator *ptr); +static void *previous(WMBag *bag, WMBagIterator *ptr); +static void *iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr); +static int indexForIterator(WMBag *bag, WMBagIterator ptr); +#endif + + +#define IS_LEFT(node) (node == node->parent->left) +#define IS_RIGHT(node) (node == node->parent->right) + + + +static void +leftRotate(W_Bag *tree, W_Node *node) +{ + W_Node *node2; + + node2 = node->right; + node->right = node2->left; + + node2->left->parent = node; + + node2->parent = node->parent; + + if (node->parent == tree->nil) { + tree->root = node2; + } else { + if (IS_LEFT(node)) { + node->parent->left = node2; + } else { + node->parent->right = node2; + } + } + node2->left = node; + node->parent = node2; +} + + + +static void +rightRotate(W_Bag *tree, W_Node *node) +{ + W_Node *node2; + + node2 = node->left; + node->left = node2->right; + + node2->right->parent = node; + + node2->parent = node->parent; + + if (node->parent == tree->nil) { + tree->root = node2; + } else { + if (IS_LEFT(node)) { + node->parent->left = node2; + } else { + node->parent->right = node2; + } + } + node2->right = node; + node->parent = node2; +} + + +static void +treeInsert(W_Bag *tree, W_Node *node) +{ + W_Node *y = tree->nil; + W_Node *x = tree->root; + + while (x != tree->nil) { + y = x; + if (node->index <= x->index) + x = x->left; + else + x = x->right; + } + node->parent = y; + if (y == tree->nil) + tree->root = node; + else if (node->index <= y->index) + y->left = node; + else + y->right = node; +} + + +static void +rbTreeInsert(W_Bag *tree, W_Node *node) +{ + W_Node *y; + + treeInsert(tree, node); + + node->color = 'R'; + + while (node != tree->root && node->parent->color == 'R') { + if (IS_LEFT(node->parent)) { + y = node->parent->parent->right; + + if (y->color == 'R') { + + node->parent->color = 'B'; + y->color = 'B'; + node->parent->parent->color = 'R'; + node = node->parent->parent; + + } else { + if (IS_RIGHT(node)) { + node = node->parent; + leftRotate(tree, node); + } + node->parent->color = 'B'; + node->parent->parent->color = 'R'; + rightRotate(tree, node->parent->parent); + } + } else { + y = node->parent->parent->left; + + if (y->color == 'R') { + + node->parent->color = 'B'; + y->color = 'B'; + node->parent->parent->color = 'R'; + node = node->parent->parent; + + } else { + if (IS_LEFT(node)) { + node = node->parent; + rightRotate(tree, node); + } + node->parent->color = 'B'; + node->parent->parent->color = 'R'; + leftRotate(tree, node->parent->parent); + } + } + } + tree->root->color = 'B'; +} + + +static void +rbDeleteFixup(W_Bag *tree, W_Node *node) +{ + W_Node *w; + + while (node != tree->root && node->color == 'B') { + if (IS_LEFT(node)) { + w = node->parent->right; + if (w->color == 'R') { + w->color = 'B'; + node->parent->color = 'R'; + leftRotate(tree, node->parent); + w = node->parent->right; + } + if (w->left->color == 'B' && w->right->color == 'B') { + w->color = 'R'; + node = node->parent; + } else { + if (w->right->color == 'B') { + w->left->color = 'B'; + w->color = 'R'; + rightRotate(tree, w); + w = node->parent->right; + } + w->color = node->parent->color; + node->parent->color = 'B'; + w->right->color = 'B'; + leftRotate(tree, node->parent); + node = tree->root; + } + } else { + w = node->parent->left; + if (w->color == 'R') { + w->color = 'B'; + node->parent->color = 'R'; + rightRotate(tree, node->parent); + w = node->parent->left; + } + if (w->left->color == 'B' && w->right->color == 'B') { + w->color = 'R'; + node = node->parent; + } else { + if (w->left->color == 'B') { + w->right->color = 'B'; + w->color = 'R'; + leftRotate(tree, w); + w = node->parent->left; + } + w->color = node->parent->color; + node->parent->color = 'B'; + w->left->color = 'B'; + rightRotate(tree, node->parent); + node = tree->root; + } + } + } + node->color = 'B'; + +} + + +static W_Node* +treeMinimum(W_Node *node, W_Node *nil) +{ + while (node->left != nil) + node = node->left; + return node; +} + + +static W_Node* +treeMaximum(W_Node *node, W_Node *nil) +{ + while (node->right != nil) + node = node->right; + return node; +} + + +static W_Node* +treeSuccessor(W_Node *node, W_Node *nil) +{ + W_Node *y; + + if (node->right != nil) { + return treeMinimum(node->right, nil); + } + y = node->parent; + while (y != nil && node == y->right) { + node = y; + y = y->parent; + } + return y; +} + + +static W_Node* +treePredecessor(W_Node *node, W_Node *nil) +{ + W_Node *y; + + if (node->left != nil) { + return treeMaximum(node->left, nil); + } + y = node->parent; + while (y != nil && node == y->left) { + node = y; + y = y->parent; + } + return y; +} + + +static W_Node* +rbTreeDelete(W_Bag *tree, W_Node *node) +{ + W_Node *nil = tree->nil; + W_Node *x, *y; + + if (node->left == nil || node->right == nil) { + y = node; + } else { + y = treeSuccessor(node, nil); + } + + if (y->left != nil) { + x = y->left; + } else { + x = y->right; + } + + x->parent = y->parent; + + if (y->parent == nil) { + tree->root = x; + } else { + if (IS_LEFT(y)) { + y->parent->left = x; + } else { + y->parent->right = x; + } + } + if (y != node) { + node->index = y->index; + node->data = y->data; + } + if (y->color == 'B') { + rbDeleteFixup(tree, x); + } + + return y; +} + + +static W_Node* +treeSearch(W_Node *root, W_Node *nil, int index) +{ + if (root == nil || root->index == index) { + return root; + } + + if (index < root->index) { + return treeSearch(root->left, nil, index); + } else { + return treeSearch(root->right, nil, index); + } +} + + +static W_Node* +treeFind(W_Node *root, W_Node *nil, void *data) +{ + W_Node *tmp; + + if (root == nil || root->data == data) + return root; + + tmp = treeFind(root->left, nil, data); + if (tmp != nil) + return tmp; + + tmp = treeFind(root->right, nil, data); + + return tmp; +} + + + +#if 0 +static char buf[512]; + +static void printNodes(W_Node *node, W_Node *nil, int depth) +{ + if (node == nil) { + return; + } + + printNodes(node->left, nil, depth+1); + + memset(buf, ' ', depth*2); + buf[depth*2] = 0; + if (IS_LEFT(node)) + printf("%s/(%2i\n", buf, node->index); + else + printf("%s\\(%2i\n", buf, node->index); + + printNodes(node->right, nil, depth+1); +} + + +void PrintTree(WMBag *bag) +{ + W_TreeBag *tree = (W_TreeBag*)bag->data; + + printNodes(tree->root, tree->nil, 0); +} +#endif + + +//#define SELF ((W_TreeBag*)self->data) + +WMBag* +WMCreateTreeBag(void) +{ + return WMCreateTreeBagWithDestructor(NULL); +} + + +WMBag* +WMCreateTreeBagWithDestructor(void (*destructor)(void*)) +{ + WMBag *bag; + + bag = wmalloc(sizeof(WMBag)); + + memset(bag, 0, sizeof(WMBag)); + + bag->nil = wmalloc(sizeof(W_Node)); + memset(bag->nil, 0, sizeof(W_Node)); + bag->nil->left = bag->nil->right = bag->nil->parent = bag->nil; + bag->nil->index = WBNotFound; + + bag->root = bag->nil; + + bag->destructor = destructor; + + return bag; +} + + +int +WMGetBagItemCount(WMBag *self) +{ + return self->count; +} + + +int +WMAppendBag(WMBag *self, WMBag *bag) +{ + WMBagIterator ptr; + void *data; + + for (data = WMBagFirst(bag, &ptr); data != NULL; data = WMBagNext(bag, &ptr)) { + if (!WMPutInBag(self, data)) + return 0; + } + + return 1; +} + +//extern WMBag *bla; + +int +WMPutInBag(WMBag *self, void *item) +{ + W_Node *ptr; + + + ptr = wmalloc(sizeof(W_Node)); + + ptr->data = item; + ptr->index = self->count; + ptr->left = self->nil; + ptr->right = self->nil; + ptr->parent = self->nil; + + rbTreeInsert(self, ptr); + + self->count++; + + return 1; +} + + +int +WMInsertInBag(WMBag *self, int index, void *item) +{ + W_Node *ptr; + + ptr = wmalloc(sizeof(W_Node)); + + ptr->data = item; + ptr->index = index; + ptr->left = self->nil; + ptr->right = self->nil; + ptr->parent = self->nil; + + rbTreeInsert(self, ptr); + + while ((ptr = treeSuccessor(ptr, self->nil)) != self->nil) { + ptr->index++; + } + + + self->count++; + + return 1; +} + + +int +WMRemoveFromBag(WMBag *self, void *item) +{ + W_Node *ptr = treeFind(self->root, self->nil, item); + + if (ptr != self->nil) { + W_Node *tmp; + + self->count--; + + tmp = treeSuccessor(ptr, self->nil); + while (tmp != self->nil) { + tmp->index--; + tmp = treeSuccessor(tmp, self->nil); + } + + ptr = rbTreeDelete(self, ptr); + if (self->destructor) + self->destructor(ptr->data); + free(ptr); + + return 1; + } else { + return 0; + } +} + + +int +WMEraseFromBag(WMBag *self, int index) +{ + W_Node *ptr = treeSearch(self->root, self->nil, index); + + if (ptr != self->nil) { + + self->count--; + + ptr = rbTreeDelete(self, ptr); + if (self->destructor) + self->destructor(ptr->data); + free(ptr); + + wassertrv(self->count == 0||self->root->index >= 0, 1); + + return 1; + } else { + return 0; + } +} + + +int +WMDeleteFromBag(WMBag *self, int index) +{ + W_Node *ptr = treeSearch(self->root, self->nil, index); + + if (ptr != self->nil) { + W_Node *tmp; + + self->count--; + + tmp = treeSuccessor(ptr, self->nil); + while (tmp != self->nil) { + tmp->index--; + tmp = treeSuccessor(tmp, self->nil); + } + + ptr = rbTreeDelete(self, ptr); + if (self->destructor) + self->destructor(ptr->data); + free(ptr); + + wassertrv(self->count == 0||self->root->index >= 0, 1); + + return 1; + } else { + return 0; + } +} + + +void* +WMGetFromBag(WMBag *self, int index) +{ + W_Node *node; + + node = treeSearch(self->root, self->nil, index); + if (node != self->nil) + return node->data; + else + return NULL; +} + + +int +WMGetFirstInBag(WMBag *self, void *item) +{ + W_Node *node; + + node = treeFind(self->root, self->nil, item); + if (node != self->nil) + return node->index; + else + return WBNotFound; +} + + + +static int +treeCount(W_Node *root, W_Node *nil, void *item) +{ + int count = 0; + + if (root == nil) + return 0; + + if (root->data == item) + count++; + + if (root->left != nil) + count += treeCount(root->left, nil, item); + + if (root->right != nil) + count += treeCount(root->right, nil, item); + + return count; +} + + + +int +WMCountInBag(WMBag *self, void *item) +{ + return treeCount(self->root, self->nil, item); +} + + +void* +WMReplaceInBag(WMBag *self, int index, void *item) +{ + W_Node *ptr = treeSearch(self->root, self->nil, index); + void *old = NULL; + + if (item == NULL) { + self->count--; + ptr = rbTreeDelete(self, ptr); + if (self->destructor) + self->destructor(ptr->data); + free(ptr); + } else if (ptr != self->nil) { + old = ptr->data; + ptr->data = item; + } else { + W_Node *ptr; + + ptr = wmalloc(sizeof(W_Node)); + + ptr->data = item; + ptr->index = index; + ptr->left = self->nil; + ptr->right = self->nil; + ptr->parent = self->nil; + + rbTreeInsert(self, ptr); + + self->count++; + } + + return old; +} + + +int +WMSortBag(WMBag *self, int (*comparer)(const void*, const void*)) +{ + void **items; + W_Node *tmp; + int i; + + if (self->count == 0) + return 1; + + items = wmalloc(sizeof(void*)*self->count); + i = 0; + + tmp = treeMinimum(self->root, self->nil); + while (tmp != self->nil) { + items[i++] = tmp->data; + tmp = treeSuccessor(tmp, self->nil); + } + + qsort(&items[0], self->count, sizeof(void*), comparer); + + i = 0; + tmp = treeMinimum(self->root, self->nil); + while (tmp != self->nil) { + tmp->index = i; + tmp->data = items[i++]; + tmp = treeSuccessor(tmp, self->nil); + } + + wfree(items); + + return 1; +} + + +static void +deleteTree(WMBag *self, W_Node *node) +{ + if (node == self->nil) + return; + + deleteTree(self, node->left); + + if (self->destructor) + self->destructor(node->data); + + deleteTree(self, node->right); + + free(node); +} + + +void +WMEmptyBag(WMBag *self) +{ + deleteTree(self, self->root); + self->root = self->nil; + self->count = 0; +} + + +void +WMFreeBag(WMBag *self) +{ + WMEmptyBag(self); + + free(self->nil); + + free(self); +} + + +static void +mapTree(W_Bag *tree, W_Node *node, void (*function)(void*, void*), void *data) +{ + if (node == tree->nil) + return; + + mapTree(tree, node->left, function, data); + + (*function)(node->data, data); + + mapTree(tree, node->right, function, data); +} + + +void +WMMapBag(WMBag *self, void (*function)(void*, void*), void *data) +{ + mapTree(self, self->root, function, data); +} + + + +static int +findInTree(W_Bag *tree, W_Node *node, int (*function)(void*,void*), void *cdata) +{ + int index; + + if (node == tree->nil) + return WBNotFound; + + index = findInTree(tree, node->left, function, cdata); + if (index != WBNotFound) + return index; + + if ((*function)(node->data, cdata)) { + return node->index; + } + + return findInTree(tree, node->right, function, cdata); +} + + +int +WMFindInBag(WMBag *self, int (*match)(void*,void*), void *cdata) +{ + return findInTree(self, self->root, match, cdata); +} + + +void* +WMBagFirst(WMBag *self, WMBagIterator *ptr) +{ + W_Node *node; + + node = treeMinimum(self->root, self->nil); + + if (node == self->nil) { + *ptr = NULL; + + return NULL; + } else { + *ptr = node; + + return node->data; + } +} + + +void* +WMBagLast(WMBag *self, WMBagIterator *ptr) +{ + + W_Node *node; + + node = treeMaximum(self->root, self->nil); + + if (node == self->nil) { + *ptr = NULL; + + return NULL; + } else { + *ptr = node; + + return node->data; + } +} + + +void* +WMBagNext(WMBag *self, WMBagIterator *ptr) +{ + W_Node *node; + + if (*ptr == NULL) + return NULL; + + node = treeSuccessor(*ptr, self->nil); + + if (node == self->nil) { + *ptr = NULL; + + return NULL; + } else { + *ptr = node; + + return node->data; + } +} + + +void* +WMBagPrevious(WMBag *self, WMBagIterator *ptr) +{ + W_Node *node; + + if (*ptr == NULL) + return NULL; + + node = treePredecessor(*ptr, self->nil); + + if (node == self->nil) { + *ptr = NULL; + + return NULL; + } else { + *ptr = node; + + return node->data; + } +} + + +void* +WMBagIteratorAtIndex(WMBag *self, int index, WMBagIterator *ptr) +{ + W_Node *node; + + node = treeSearch(self->root, self->nil, index); + + if (node == self->nil) { + *ptr = NULL; + return NULL; + } else { + *ptr = node; + return node->data; + } +} + + +int +WMBagIndexForIterator(WMBag *bag, WMBagIterator ptr) +{ + return ((W_Node*)ptr)->index; +} + + diff --git a/WINGs/wtext.c b/WINGs/wtext.c index c48e9f0a..d0675d43 100644 --- a/WINGs/wtext.c +++ b/WINGs/wtext.c @@ -2158,7 +2158,7 @@ getStreamIntoBag(WMText *tPtr, int sel) if(!stream) return NULL; - bag = WMCreateArrayBagWithDestructor(4, releaseBagData); + bag = WMCreateBagWithDestructor(4, releaseBagData); start = stream; while (start) { @@ -2265,7 +2265,7 @@ WMCreateText(WMWidget *parent) tPtr->currentTextBlock = NULL; tPtr->tpos = 0; - tPtr->gfxItems = WMCreateArrayBag(4); + tPtr->gfxItems = WMCreateBag(4); tPtr->parser = NULL; tPtr->writer = NULL; -- 2.11.4.GIT