From 6a3b06e609dec210bd9159503ff8c1671a59b9d2 Mon Sep 17 00:00:00 2001 From: dan Date: Thu, 18 Jan 2001 16:59:15 +0000 Subject: [PATCH] Finished the generic tree node data type --- WINGs/WUtil.h | 32 ++-- WINGs/tree.c | 482 +++++++++++++++++++++++++++++++++------------------------- 2 files changed, 302 insertions(+), 212 deletions(-) rewrite WINGs/tree.c (75%) diff --git a/WINGs/WUtil.h b/WINGs/WUtil.h index a1778d74..ea5bb4c9 100644 --- a/WINGs/WUtil.h +++ b/WINGs/WUtil.h @@ -582,23 +582,37 @@ WMTreeNode* WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc *destructo WMTreeNode* WMInsertItemInTree(WMTreeNode *parent, int index, void *item); -WMTreeNode* WMAddItemToTree(WMTreeNode *parent, void *item); +#define WMAddItemToTree(parent, item) WMInsertItemInTree(parent, -1, item) -WMTreeNode* WMInsertNodeInTree(WMTreeNode *parent, int index, WMTreeNode *node); +WMTreeNode* WMInsertNodeInTree(WMTreeNode *parent, int index, WMTreeNode *aNode); -WMTreeNode* WMAddNodeToTree(WMTreeNode *parent, WMTreeNode *node); +#define WMAddNodeToTree(parent, aNode) WMInsertNodeInTree(parent, -1, aNode) -int WMGetTreeNodeDepth(WMTreeNode *node); +void WMDestroyTreeNode(WMTreeNode *aNode); -void WMDestroyTreeNode(WMTreeNode *node); +void WMDeleteLeafForTreeNode(WMTreeNode *aNode, int index); -void* WMGetDataForTreeNode(WMTreeNode *node); +void WMRemoveLeafForTreeNode(WMTreeNode *aNode, void *leaf); -WMTreeNode* WMGetParentForTreeNode(WMTreeNode *node); +void* WMReplaceDataForTreeNode(WMTreeNode *aNode, void *newData); -void WMSortLeavesForTreeNode(WMTreeNode *node, WMCompareDataProc *comparer); +void* WMGetDataForTreeNode(WMTreeNode *aNode); -void WMSortTree(WMTreeNode *root, WMCompareDataProc *comparer); +int WMGetTreeNodeDepth(WMTreeNode *aNode); + +WMTreeNode* WMGetParentForTreeNode(WMTreeNode *aNode); + +/* Sort only the leaves of the passed node */ +void WMSortLeavesForTreeNode(WMTreeNode *aNode, WMCompareDataProc *comparer); + +/* Sort all tree recursively starting from the passed node */ +void WMSortTree(WMTreeNode *aNode, WMCompareDataProc *comparer); + +/* Returns the first node which matches node's data with cdata by 'match' */ +WMTreeNode* WMFindInTree(WMTreeNode *aTree, WMMatchDataProc *match, void *cdata); + +/* Returns first tree node that has data == cdata */ +#define WMGetFirstInTree(aTree, cdata) WMFindInTree(atree, NULL, cdata) /*--------------------------------------------------------------------------*/ diff --git a/WINGs/tree.c b/WINGs/tree.c dissimilarity index 75% index dd2a9d01..e5c56ea3 100644 --- a/WINGs/tree.c +++ b/WINGs/tree.c @@ -1,203 +1,279 @@ - - - -#include - -#include "WUtil.h" - - -typedef struct W_TreeNode { - void *data; - - /*unsigned int uflags:16;*/ - - WMArray *leaves; - - int depth; - - struct W_TreeNode *parent; - - WMFreeDataProc *destructor; -} W_TreeNode; - - - -void -destroyNode(void *data) -{ - WMTreeNode *node = (WMTreeNode*) data; - - if (node->destructor) { - (*node->destructor)(node->data); - } - if (node->leaves) { - WMFreeArray(node->leaves); - } - wfree(node); -} - - -WMTreeNode* -WMCreateTreeNode(void *data) -{ - return WMCreateTreeNodeWithDestructor(data, NULL); -} - - -WMTreeNode* -WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc *destructor) -{ - WMTreeNode *node; - - node = (WMTreeNode*) wmalloc(sizeof(W_TreeNode)); - memset(node, 0, sizeof(W_TreeNode)); - - node->destructor = destructor; - - node->data = data; - node->parent = NULL; - node->depth = 0; - node->leaves = WMCreateArrayWithDestructor(1, destroyNode); - - return node; -} - - -WMTreeNode* -WMInsertItemInTree(WMTreeNode *parent, int index, void *item) -{ - WMTreeNode *node; - - wassertrv(parent!=NULL, NULL); - - node = WMCreateTreeNodeWithDestructor(item, parent->destructor); - node->parent = parent; - node->depth = parent->depth+1; - if (index < 0 || index > WMGetArrayItemCount(parent->leaves)) { - WMAddToArray(parent->leaves, node); - } else { - WMInsertInArray(parent->leaves, index, node); - } - - return node; -} - - -WMTreeNode* -WMAddItemToTree(WMTreeNode *parent, void *item) -{ - WMTreeNode *node; - - wassertrv(parent!=NULL, NULL); - - node = WMCreateTreeNodeWithDestructor(item, parent->destructor); - node->parent = parent; - node->depth = parent->depth+1; - WMAddToArray(parent->leaves, node); - - return node; -} - - -static void -updateNodeDepth(WMTreeNode *node, int depth) -{ - int i; - - node->depth = depth; - for (i=0; ileaves); i++) { - updateNodeDepth(WMGetFromArray(node->leaves, i), depth+1); - } -} - - -WMTreeNode* -WMInsertNodeInTree(WMTreeNode *parent, int index, WMTreeNode *node) -{ - wassertrv(parent!=NULL, NULL); - wassertrv(node!=NULL, NULL); - - node->parent = parent; - updateNodeDepth(node, parent->depth+1); - if (index < 0 || index > WMGetArrayItemCount(parent->leaves)) { - WMAddToArray(parent->leaves, node); - } else { - WMInsertInArray(parent->leaves, index, node); - } - - return node; -} - - -WMTreeNode* -WMAddNodeToTree(WMTreeNode *parent, WMTreeNode *node) -{ - wassertrv(parent!=NULL, NULL); - wassertrv(node!=NULL, NULL); - - node->parent = parent; - updateNodeDepth(node, parent->depth+1); - WMAddToArray(parent->leaves, node); - - return node; -} - - -int -WMGetTreeNodeDepth(WMTreeNode *node) -{ - return node->depth; -} - - -void -WMDestroyTreeNode(WMTreeNode *node) -{ - destroyNode(node); -} - - -void* -WMGetDataForTreeNode(WMTreeNode *node) -{ - return node->data; -} - - -WMTreeNode* -WMGetParentForTreeNode(WMTreeNode *node) -{ - return node->parent; -} - - -void -WMSortLeavesForTreeNode(WMTreeNode *node, WMCompareDataProc *comparer) -{ - wassertr(node!=NULL); - - WMSortArray(node->leaves, comparer); -} - - -static void -sortLeavesForNode(WMTreeNode *node, WMCompareDataProc *comparer) -{ - int i; - - WMSortArray(node->leaves, comparer); - for (i=0; ileaves); i++) { - sortLeavesForNode(WMGetFromArray(node->leaves, i), comparer); - } -} - - -void -WMSortTree(WMTreeNode *root, WMCompareDataProc *comparer) -{ - wassertr(root!=NULL); - - sortLeavesForNode(root, comparer); -} - - + + + +#include + +#include "WUtil.h" + + +typedef struct W_TreeNode { + void *data; + + /*unsigned int uflags:16;*/ + + WMArray *leaves; + + int depth; + + struct W_TreeNode *parent; + + WMFreeDataProc *destructor; +} W_TreeNode; + + + + +void +destroyNode(void *data) +{ + WMTreeNode *aNode = (WMTreeNode*) data; + + if (aNode->destructor) { + (*aNode->destructor)(aNode->data); + } + if (aNode->leaves) { + WMFreeArray(aNode->leaves); + } + wfree(aNode); +} + + +WMTreeNode* +WMCreateTreeNode(void *data) +{ + return WMCreateTreeNodeWithDestructor(data, NULL); +} + + +WMTreeNode* +WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc *destructor) +{ + WMTreeNode *aNode; + + aNode = (WMTreeNode*) wmalloc(sizeof(W_TreeNode)); + memset(aNode, 0, sizeof(W_TreeNode)); + + aNode->destructor = destructor; + + aNode->data = data; + aNode->parent = NULL; + aNode->depth = 0; + aNode->leaves = NULL; + /*aNode->leaves = WMCreateArrayWithDestructor(1, destroyNode);*/ + + return aNode; +} + + +WMTreeNode* +WMInsertItemInTree(WMTreeNode *parent, int index, void *item) +{ + WMTreeNode *aNode; + + wassertrv(parent!=NULL, NULL); + + aNode = WMCreateTreeNodeWithDestructor(item, parent->destructor); + aNode->parent = parent; + aNode->depth = parent->depth+1; + if (!parent->leaves) { + parent->leaves = WMCreateArrayWithDestructor(1, destroyNode); + } + if (index < 0) { + WMAddToArray(parent->leaves, aNode); + } else { + WMInsertInArray(parent->leaves, index, aNode); + } + + return aNode; +} + + +static void +updateNodeDepth(WMTreeNode *aNode, int depth) +{ + int i; + + aNode->depth = depth; + + if (aNode->leaves) { + for (i=0; ileaves); i++) { + updateNodeDepth(WMGetFromArray(aNode->leaves, i), depth+1); + } + } +} + + +WMTreeNode* +WMInsertNodeInTree(WMTreeNode *parent, int index, WMTreeNode *aNode) +{ + wassertrv(parent!=NULL, NULL); + wassertrv(aNode!=NULL, NULL); + + aNode->parent = parent; + updateNodeDepth(aNode, parent->depth+1); + if (!parent->leaves) { + parent->leaves = WMCreateArrayWithDestructor(1, destroyNode); + } + if (index < 0) { + WMAddToArray(parent->leaves, aNode); + } else { + WMInsertInArray(parent->leaves, index, aNode); + } + + return aNode; +} + + +void +WMDestroyTreeNode(WMTreeNode *aNode) +{ + wassertr(aNode!=NULL); + + if (aNode->parent && aNode->parent->leaves) { + WMRemoveFromArray(aNode->parent->leaves, aNode); + } else { + destroyNode(aNode); + } +} + + +void +WMDeleteLeafForTreeNode(WMTreeNode *aNode, int index) +{ + wassertr(aNode!=NULL); + wassertr(aNode->leaves!=NULL); + + WMDeleteFromArray(aNode->leaves, index); +} + + +static int +sameData(void *item, void *data) +{ + return (((WMTreeNode*)item)->data == data); +} + + +void +WMRemoveLeafForTreeNode(WMTreeNode *aNode, void *leaf) +{ + int index; + + wassertr(aNode!=NULL); + wassertr(aNode->leaves!=NULL); + + index = WMFindInArray(aNode->leaves, sameData, leaf); + if (index != WANotFound) { + WMDeleteFromArray(aNode->leaves, index); + } +} + + +void* +WMReplaceDataForTreeNode(WMTreeNode *aNode, void *newData) +{ + void *old; + + wassertrv(aNode!=NULL, NULL); + + old = aNode->data; + aNode->data = newData; + + return old; +} + + +void* +WMGetDataForTreeNode(WMTreeNode *aNode) +{ + return aNode->data; +} + + +int +WMGetTreeNodeDepth(WMTreeNode *aNode) +{ + return aNode->depth; +} + + +WMTreeNode* +WMGetParentForTreeNode(WMTreeNode *aNode) +{ + return aNode->parent; +} + + +void +WMSortLeavesForTreeNode(WMTreeNode *aNode, WMCompareDataProc *comparer) +{ + wassertr(aNode!=NULL); + + if (aNode->leaves) { + WMSortArray(aNode->leaves, comparer); + } +} + + +static void +sortLeavesForNode(WMTreeNode *aNode, WMCompareDataProc *comparer) +{ + int i; + + if (!aNode->leaves) + return; + + WMSortArray(aNode->leaves, comparer); + for (i=0; ileaves); i++) { + sortLeavesForNode(WMGetFromArray(aNode->leaves, i), comparer); + } +} + + +void +WMSortTree(WMTreeNode *aNode, WMCompareDataProc *comparer) +{ + wassertr(aNode!=NULL); + + sortLeavesForNode(aNode, comparer); +} + + +static WMTreeNode* +findNodeInTree(WMTreeNode *aNode, WMMatchDataProc *match, void *cdata) +{ + if (match==NULL) { + if (aNode->data == cdata) { + return aNode; + } + } else { + if ((*match)(aNode->data, cdata)) { + return aNode; + } + } + + if (aNode->leaves) { + WMTreeNode *leaf; + int i; + + for (i=0; ileaves); i++) { + leaf = findNodeInTree(WMGetFromArray(aNode->leaves, i), match, cdata); + if (leaf) { + return leaf; + } + } + } + + return NULL; +} + + +WMTreeNode* +WMFindInTree(WMTreeNode *aTree, WMMatchDataProc *match, void *cdata) +{ + wassertrv(aTree!=NULL, NULL); + + return findNodeInTree(aTree, match, cdata); +} + + -- 2.11.4.GIT