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 static 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         aNode->destructor = destructor;
  44         aNode->data = data;
  45         aNode->parent = NULL;
  46         aNode->depth = 0;
  47         aNode->leaves = NULL;
  48         /*aNode->leaves = WMCreateArrayWithDestructor(1, destroyNode); */
  49
  50         return aNode;
  51 }
  52
  53 WMTreeNode *WMInsertItemInTree(WMTreeNode * parent, int index, void *item)
  54 {
  55         WMTreeNode *aNode;
  56
  57         wassertrv(parent != NULL, NULL);
  58
  59         aNode = WMCreateTreeNodeWithDestructor(item, parent->destructor);
  60         aNode->parent = parent;
  61         aNode->depth = parent->depth + 1;
  62         if (!parent->leaves) {
  63                 parent->leaves = WMCreateArrayWithDestructor(1, destroyNode);
  64         }
  65         if (index < 0) {
  66                 WMAddToArray(parent->leaves, aNode);
  67         } else {
  68                 WMInsertInArray(parent->leaves, index, aNode);
  69         }
  70
  71         return aNode;
  72 }
  73
  74 static void updateNodeDepth(WMTreeNode * aNode, int depth)
  75 {
  76         int i;
  77
  78         aNode->depth = depth;
  79
  80         if (aNode->leaves) {
  81                 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
  82                         updateNodeDepth(WMGetFromArray(aNode->leaves, i), depth + 1);
  83                 }
  84         }
  85 }
  86
  87 WMTreeNode *WMInsertNodeInTree(WMTreeNode * parent, int index, WMTreeNode * aNode)
  88 {
  89         wassertrv(parent != NULL, NULL);
  90         wassertrv(aNode != NULL, NULL);
  91
  92         aNode->parent = parent;
  93         updateNodeDepth(aNode, parent->depth + 1);
  94         if (!parent->leaves) {
  95                 parent->leaves = WMCreateArrayWithDestructor(1, destroyNode);
  96         }
  97         if (index < 0) {
  98                 WMAddToArray(parent->leaves, aNode);
  99         } else {
 100                 WMInsertInArray(parent->leaves, index, aNode);
 101         }
 102
 103         return aNode;
 104 }
 105
 106 void WMDestroyTreeNode(WMTreeNode * aNode)
 107 {
 108         wassertr(aNode != NULL);
 109
 110         if (aNode->parent && aNode->parent->leaves) {
 111                 WMRemoveFromArray(aNode->parent->leaves, aNode);
 112         } else {
 113                 destroyNode(aNode);
 114         }
 115 }
 116
 117 void WMDeleteLeafForTreeNode(WMTreeNode * aNode, int index)
 118 {
 119         wassertr(aNode != NULL);
 120         wassertr(aNode->leaves != NULL);
 121
 122         WMDeleteFromArray(aNode->leaves, index);
 123 }
 124
 125 static int sameData(const void *item, const void *data)
 126 {
 127         return (((WMTreeNode *) item)->data == data);
 128 }
 129
 130 void WMRemoveLeafForTreeNode(WMTreeNode * aNode, void *leaf)
 131 {
 132         int index;
 133
 134         wassertr(aNode != NULL);
 135         wassertr(aNode->leaves != NULL);
 136
 137         index = WMFindInArray(aNode->leaves, sameData, leaf);
 138         if (index != WANotFound) {
 139                 WMDeleteFromArray(aNode->leaves, index);
 140         }
 141 }
 142
 143 void *WMReplaceDataForTreeNode(WMTreeNode * aNode, void *newData)
 144 {
 145         void *old;
 146
 147         wassertrv(aNode != NULL, NULL);
 148
 149         old = aNode->data;
 150         aNode->data = newData;
 151
 152         return old;
 153 }
 154
 155 void *WMGetDataForTreeNode(WMTreeNode * aNode)
 156 {
 157         return aNode->data;
 158 }
 159
 160 int WMGetTreeNodeDepth(WMTreeNode * aNode)
 161 {
 162         return aNode->depth;
 163 }
 164
 165 WMTreeNode *WMGetParentForTreeNode(WMTreeNode * aNode)
 166 {
 167         return aNode->parent;
 168 }
 169
 170 void WMSortLeavesForTreeNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
 171 {
 172         wassertr(aNode != NULL);
 173
 174         if (aNode->leaves) {
 175                 WMSortArray(aNode->leaves, comparer);
 176         }
 177 }
 178
 179 static void sortLeavesForNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
 180 {
 181         int i;
 182
 183         if (!aNode->leaves)
 184                 return;
 185
 186         WMSortArray(aNode->leaves, comparer);
 187         for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
 188                 sortLeavesForNode(WMGetFromArray(aNode->leaves, i), comparer);
 189         }
 190 }
 191
 192 void WMSortTree(WMTreeNode * aNode, WMCompareDataProc * comparer)
 193 {
 194         wassertr(aNode != NULL);
 195
 196         sortLeavesForNode(aNode, comparer);
 197 }
 198
 199 static WMTreeNode *findNodeInTree(WMTreeNode * aNode, WMMatchDataProc * match, void *cdata, int limit)
 200 {
 201         if (match == NULL && aNode->data == cdata)
 202                 return aNode;
 203         else if (match && (*match) (aNode->data, cdata))
 204                 return aNode;
 205
 206         if (aNode->leaves && limit != 0) {
 207                 WMTreeNode *leaf;
 208                 int i;
 209
 210                 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
 211                         leaf = findNodeInTree(WMGetFromArray(aNode->leaves, i),
 212                                               match, cdata, limit > 0 ? limit - 1 : limit);
 213                         if (leaf)
 214                                 return leaf;
 215                 }
 216         }
 217
 218         return NULL;
 219 }
 220
 221 WMTreeNode *WMFindInTree(WMTreeNode * aTree, WMMatchDataProc * match, void *cdata)
 222 {
 223         wassertrv(aTree != NULL, NULL);
 224
 225         return findNodeInTree(aTree, match, cdata, -1);
 226 }
 227
 228 WMTreeNode *WMFindInTreeWithDepthLimit(WMTreeNode * aTree, WMMatchDataProc * match, void *cdata, int limit)
 229 {
 230         wassertrv(aTree != NULL, NULL);
 231         wassertrv(limit >= 0, NULL);
 232
 233         return findNodeInTree(aTree, match, cdata, limit);
 234 }
 235
 236 void WMTreeWalk(WMTreeNode * aNode, WMTreeWalkProc * walk, void *data, Bool DepthFirst)
 237 {
 238         int i;
 239         WMTreeNode *leaf;
 240
 241         wassertr(aNode != NULL);
 242
 243         if (DepthFirst)
 244                 (*walk)(aNode, data);
 245
 246         if (aNode->leaves) {
 247                 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
 248                         leaf = (WMTreeNode *)WMGetFromArray(aNode->leaves, i);
 249                         WMTreeWalk(leaf, walk, data, DepthFirst);
 250                 }
 251         }
 252
 253         if (!DepthFirst)
 254                 (*walk)(aNode, data);
 255 }