WINGs/tree.c

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