WINGs/tree.c

   1
   2 #include <string.h>
   3
   4 #include "WUtil.h"
   5
   6 typedef struct W_TreeNode {
   7         void *data;
   8
   9         /*unsigned int uflags:16; */
  10
  11         WMArray *leaves;
  12
  13         int depth;
  14
  15         struct W_TreeNode *parent;
  16
  17         WMFreeDataProc *destructor;
  18 } W_TreeNode;
  19
  20 void destroyNode(void *data)
  21 {
  22         WMTreeNode *aNode = (WMTreeNode *) data;
  23
  24         if (aNode->destructor) {
  25                 (*aNode->destructor) (aNode->data);
  26         }
  27         if (aNode->leaves) {
  28                 WMFreeArray(aNode->leaves);
  29         }
  30         wfree(aNode);
  31 }
  32
  33 WMTreeNode *WMCreateTreeNode(void *data)
  34 {
  35         return WMCreateTreeNodeWithDestructor(data, NULL);
  36 }
  37
  38 WMTreeNode *WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc * destructor)
  39 {
  40         WMTreeNode *aNode;
  41
  42         aNode = (WMTreeNode *) wmalloc(sizeof(W_TreeNode));
  43         memset(aNode, 0, sizeof(W_TreeNode));
  44
  45         aNode->destructor = destructor;
  46
  47         aNode->data = data;
  48         aNode->parent = NULL;
  49         aNode->depth = 0;
  50         aNode->leaves = NULL;
  51         /*aNode->leaves = WMCreateArrayWithDestructor(1, destroyNode); */
  52
  53         return aNode;
  54 }
  55
  56 WMTreeNode *WMInsertItemInTree(WMTreeNode * parent, int index, void *item)
  57 {
  58         WMTreeNode *aNode;
  59
  60         wassertrv(parent != NULL, NULL);
  61
  62         aNode = WMCreateTreeNodeWithDestructor(item, parent->destructor);
  63         aNode->parent = parent;
  64         aNode->depth = parent->depth + 1;
  65         if (!parent->leaves) {
  66                 parent->leaves = WMCreateArrayWithDestructor(1, destroyNode);
  67         }
  68         if (index < 0) {
  69                 WMAddToArray(parent->leaves, aNode);
  70         } else {
  71                 WMInsertInArray(parent->leaves, index, aNode);
  72         }
  73
  74         return aNode;
  75 }
  76
  77 static void updateNodeDepth(WMTreeNode * aNode, int depth)
  78 {
  79         int i;
  80
  81         aNode->depth = depth;
  82
  83         if (aNode->leaves) {
  84                 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
  85                         updateNodeDepth(WMGetFromArray(aNode->leaves, i), depth + 1);
  86                 }
  87         }
  88 }
  89
  90 WMTreeNode *WMInsertNodeInTree(WMTreeNode * parent, int index, WMTreeNode * aNode)
  91 {
  92         wassertrv(parent != NULL, NULL);
  93         wassertrv(aNode != NULL, NULL);
  94
  95         aNode->parent = parent;
  96         updateNodeDepth(aNode, parent->depth + 1);
  97         if (!parent->leaves) {
  98                 parent->leaves = WMCreateArrayWithDestructor(1, destroyNode);
  99         }
 100         if (index < 0) {
 101                 WMAddToArray(parent->leaves, aNode);
 102         } else {
 103                 WMInsertInArray(parent->leaves, index, aNode);
 104         }
 105
 106         return aNode;
 107 }
 108
 109 void WMDestroyTreeNode(WMTreeNode * aNode)
 110 {
 111         wassertr(aNode != NULL);
 112
 113         if (aNode->parent && aNode->parent->leaves) {
 114                 WMRemoveFromArray(aNode->parent->leaves, aNode);
 115         } else {
 116                 destroyNode(aNode);
 117         }
 118 }
 119
 120 void WMDeleteLeafForTreeNode(WMTreeNode * aNode, int index)
 121 {
 122         wassertr(aNode != NULL);
 123         wassertr(aNode->leaves != NULL);
 124
 125         WMDeleteFromArray(aNode->leaves, index);
 126 }
 127
 128 static int sameData(void *item, void *data)
 129 {
 130         return (((WMTreeNode *) item)->data == data);
 131 }
 132
 133 void WMRemoveLeafForTreeNode(WMTreeNode * aNode, void *leaf)
 134 {
 135         int index;
 136
 137         wassertr(aNode != NULL);
 138         wassertr(aNode->leaves != NULL);
 139
 140         index = WMFindInArray(aNode->leaves, sameData, leaf);
 141         if (index != WANotFound) {
 142                 WMDeleteFromArray(aNode->leaves, index);
 143         }
 144 }
 145
 146 void *WMReplaceDataForTreeNode(WMTreeNode * aNode, void *newData)
 147 {
 148         void *old;
 149
 150         wassertrv(aNode != NULL, NULL);
 151
 152         old = aNode->data;
 153         aNode->data = newData;
 154
 155         return old;
 156 }
 157
 158 void *WMGetDataForTreeNode(WMTreeNode * aNode)
 159 {
 160         return aNode->data;
 161 }
 162
 163 int WMGetTreeNodeDepth(WMTreeNode * aNode)
 164 {
 165         return aNode->depth;
 166 }
 167
 168 WMTreeNode *WMGetParentForTreeNode(WMTreeNode * aNode)
 169 {
 170         return aNode->parent;
 171 }
 172
 173 void WMSortLeavesForTreeNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
 174 {
 175         wassertr(aNode != NULL);
 176
 177         if (aNode->leaves) {
 178                 WMSortArray(aNode->leaves, comparer);
 179         }
 180 }
 181
 182 static void sortLeavesForNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
 183 {
 184         int i;
 185
 186         if (!aNode->leaves)
 187                 return;
 188
 189         WMSortArray(aNode->leaves, comparer);
 190         for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
 191                 sortLeavesForNode(WMGetFromArray(aNode->leaves, i), comparer);
 192         }
 193 }
 194
 195 void WMSortTree(WMTreeNode * aNode, WMCompareDataProc * comparer)
 196 {
 197         wassertr(aNode != NULL);
 198
 199         sortLeavesForNode(aNode, comparer);
 200 }
 201
 202 static WMTreeNode *findNodeInTree(WMTreeNode * aNode, WMMatchDataProc * match, void *cdata)
 203 {
 204         if (match == NULL) {
 205                 if (aNode->data == cdata) {
 206                         return aNode;
 207                 }
 208         } else {
 209                 if ((*match) (aNode->data, cdata)) {
 210                         return aNode;
 211                 }
 212         }
 213
 214         if (aNode->leaves) {
 215                 WMTreeNode *leaf;
 216                 int i;
 217
 218                 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
 219                         leaf = findNodeInTree(WMGetFromArray(aNode->leaves, i), match, cdata);
 220                         if (leaf) {
 221                                 return leaf;
 222                         }
 223                 }
 224         }
 225
 226         return NULL;
 227 }
 228
 229 WMTreeNode *WMFindInTree(WMTreeNode * aTree, WMMatchDataProc * match, void *cdata)
 230 {
 231         wassertrv(aTree != NULL, NULL);
 232
 233         return findNodeInTree(aTree, match, cdata);
 234 }