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 void
  26 destroyNode(void *data)
  27 {
  28     WMTreeNode *node = (WMTreeNode*) data;
  29
  30     if (node->destructor) {
  31         (*node->destructor)(node->data);
  32     }
  33     if (node->leaves) {
  34         WMFreeArray(node->leaves);
  35     }
  36     wfree(node);
  37 }
  38
  39
  40 WMTreeNode*
  41 WMCreateTreeNode(void *data)
  42 {
  43     return WMCreateTreeNodeWithDestructor(data, NULL);
  44 }
  45
  46
  47 WMTreeNode*
  48 WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc *destructor)
  49 {
  50     WMTreeNode *node;
  51
  52     node = (WMTreeNode*) wmalloc(sizeof(W_TreeNode));
  53     memset(node, 0, sizeof(W_TreeNode));
  54
  55     node->destructor = destructor;
  56
  57     node->data = data;
  58     node->parent = NULL;
  59     node->depth = 0;
  60     node->leaves = WMCreateArrayWithDestructor(1, destroyNode);
  61
  62     return node;
  63 }
  64
  65
  66 WMTreeNode*
  67 WMInsertItemInTree(WMTreeNode *parent, int index, void *item)
  68 {
  69     WMTreeNode *node;
  70
  71     wassertrv(parent!=NULL, NULL);
  72
  73     node = WMCreateTreeNodeWithDestructor(item, parent->destructor);
  74     node->parent = parent;
  75     node->depth = parent->depth+1;
  76     if (index < 0 || index > WMGetArrayItemCount(parent->leaves)) {
  77         WMAddToArray(parent->leaves, node);
  78     } else {
  79         WMInsertInArray(parent->leaves, index, node);
  80     }
  81
  82     return node;
  83 }
  84
  85
  86 WMTreeNode*
  87 WMAddItemToTree(WMTreeNode *parent, void *item)
  88 {
  89     WMTreeNode *node;
  90
  91     wassertrv(parent!=NULL, NULL);
  92
  93     node = WMCreateTreeNodeWithDestructor(item, parent->destructor);
  94     node->parent = parent;
  95     node->depth = parent->depth+1;
  96     WMAddToArray(parent->leaves, node);
  97
  98     return node;
  99 }
 100
 101
 102 static void
 103 updateNodeDepth(WMTreeNode *node, int depth)
 104 {
 105     int i;
 106
 107     node->depth = depth;
 108     for (i=0; i<WMGetArrayItemCount(node->leaves); i++) {
 109         updateNodeDepth(WMGetFromArray(node->leaves, i), depth+1);
 110     }
 111 }
 112
 113
 114 WMTreeNode*
 115 WMInsertNodeInTree(WMTreeNode *parent, int index, WMTreeNode *node)
 116 {
 117     wassertrv(parent!=NULL, NULL);
 118     wassertrv(node!=NULL, NULL);
 119
 120     node->parent = parent;
 121     updateNodeDepth(node, parent->depth+1);
 122     if (index < 0 || index > WMGetArrayItemCount(parent->leaves)) {
 123         WMAddToArray(parent->leaves, node);
 124     } else {
 125         WMInsertInArray(parent->leaves, index, node);
 126     }
 127
 128     return node;
 129 }
 130
 131
 132 WMTreeNode*
 133 WMAddNodeToTree(WMTreeNode *parent, WMTreeNode *node)
 134 {
 135     wassertrv(parent!=NULL, NULL);
 136     wassertrv(node!=NULL, NULL);
 137
 138     node->parent = parent;
 139     updateNodeDepth(node, parent->depth+1);
 140     WMAddToArray(parent->leaves, node);
 141
 142     return node;
 143 }
 144
 145
 146 int
 147 WMGetTreeNodeDepth(WMTreeNode *node)
 148 {
 149     return node->depth;
 150 }
 151
 152
 153 void
 154 WMDestroyTreeNode(WMTreeNode *node)
 155 {
 156     destroyNode(node);
 157 }
 158
 159
 160 void*
 161 WMGetDataForTreeNode(WMTreeNode *node)
 162 {
 163     return node->data;
 164 }
 165
 166
 167 WMTreeNode*
 168 WMGetParentForTreeNode(WMTreeNode *node)
 169 {
 170     return node->parent;
 171 }
 172
 173
 174 void
 175 WMSortLeavesForTreeNode(WMTreeNode *node, WMCompareDataProc *comparer)
 176 {
 177     wassertr(node!=NULL);
 178
 179     WMSortArray(node->leaves, comparer);
 180 }
 181
 182
 183 static void
 184 sortLeavesForNode(WMTreeNode *node, WMCompareDataProc *comparer)
 185 {
 186     int i;
 187
 188     WMSortArray(node->leaves, comparer);
 189     for (i=0; i<WMGetArrayItemCount(node->leaves); i++) {
 190         sortLeavesForNode(WMGetFromArray(node->leaves, i), comparer);
 191     }
 192 }
 193
 194
 195 void
 196 WMSortTree(WMTreeNode *root, WMCompareDataProc *comparer)
 197 {
 198     wassertr(root!=NULL);
 199
 200     sortLeavesForNode(root, comparer);
 201 }
 202
 203