WINGs/tree.c

   1
   2
   3
   4 //#include <stdlib.h>
   5 #include <string.h>
   6
   7 #include "WUtil.h"
   8
   9
  10 typedef struct W_TreeNode {
  11     void *data;
  12
  13     //unsigned int uflags:16;
  14
  15     WMArray *leaves;
  16
  17     int depth;
  18
  19     struct W_TreeNode *parent;
  20
  21     WMFreeDataProc *destructor;
  22 } W_TreeNode;
  23
  24
  25
  26 void
  27 destroyNode(void *data)
  28 {
  29     WMTreeNode *node = (WMTreeNode*) data;
  30
  31     if (node->destructor) {
  32         (*node->destructor)(node->data);
  33     }
  34     if (node->leaves) {
  35         WMFreeArray(node->leaves);
  36     }
  37     wfree(node);
  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 *node;
  52
  53     node = (WMTreeNode*) wmalloc(sizeof(W_TreeNode));
  54     memset(node, 0, sizeof(W_TreeNode));
  55
  56     node->destructor = destructor;
  57
  58     node->data = data;
  59     node->parent = NULL;
  60     node->depth = 0;
  61     node->leaves = WMCreateArrayWithDestructor(1, destroyNode);
  62
  63     return node;
  64 }
  65
  66
  67 WMTreeNode*
  68 WMInsertItemInTree(WMTreeNode *parent, int index, void *item)
  69 {
  70     WMTreeNode *node;
  71
  72     wassertrv(parent!=NULL, NULL);
  73
  74     node = WMCreateTreeNodeWithDestructor(item, parent->destructor);
  75     node->parent = parent;
  76     node->depth = parent->depth+1;
  77     if (index < 0 || index > WMGetArrayItemCount(parent->leaves)) {
  78         WMAddToArray(parent->leaves, node);
  79     } else {
  80         WMInsertInArray(parent->leaves, index, node);
  81     }
  82
  83     return node;
  84 }
  85
  86
  87 WMTreeNode*
  88 WMAddItemToTree(WMTreeNode *parent, void *item)
  89 {
  90     WMTreeNode *node;
  91
  92     wassertrv(parent!=NULL, NULL);
  93
  94     node = WMCreateTreeNodeWithDestructor(item, parent->destructor);
  95     node->parent = parent;
  96     node->depth = parent->depth+1;
  97     WMAddToArray(parent->leaves, node);
  98
  99     return node;
 100 }
 101
 102
 103 static void
 104 updateNodeDepth(WMTreeNode *node, int depth)
 105 {
 106     int i;
 107
 108     node->depth = depth;
 109     for (i=0; i<WMGetArrayItemCount(node->leaves); i++) {
 110         updateNodeDepth(WMGetFromArray(node->leaves, i), depth+1);
 111     }
 112 }
 113
 114
 115 WMTreeNode*
 116 WMInsertNodeInTree(WMTreeNode *parent, int index, WMTreeNode *node)
 117 {
 118     wassertrv(parent!=NULL, NULL);
 119     wassertrv(node!=NULL, NULL);
 120
 121     node->parent = parent;
 122     updateNodeDepth(node, parent->depth+1);
 123     if (index < 0 || index > WMGetArrayItemCount(parent->leaves)) {
 124         WMAddToArray(parent->leaves, node);
 125     } else {
 126         WMInsertInArray(parent->leaves, index, node);
 127     }
 128
 129     return node;
 130 }
 131
 132
 133 WMTreeNode*
 134 WMAddNodeToTree(WMTreeNode *parent, WMTreeNode *node)
 135 {
 136     wassertrv(parent!=NULL, NULL);
 137     wassertrv(node!=NULL, NULL);
 138
 139     node->parent = parent;
 140     updateNodeDepth(node, parent->depth+1);
 141     WMAddToArray(parent->leaves, node);
 142
 143     return node;
 144 }
 145
 146
 147 int
 148 WMGetTreeNodeDepth(WMTreeNode *node)
 149 {
 150     return node->depth;
 151 }
 152
 153
 154 void
 155 WMDestroyTreeNode(WMTreeNode *node)
 156 {
 157     destroyNode(node);
 158 }
 159
 160