Change to the linux kernel coding style
[wmaker-crm.git] / WINGs / tree.c
Commit [+]AuthorDateLineData
a7ec9dab dan2001-01-11 02:35:21 +00001
a7ec9dab dan2001-01-11 02:35:21 +00002#include <string.h>
3
4#include "WUtil.h"
5
a7ec9dab dan2001-01-11 02:35:21 +00006typedef struct W_TreeNode {
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +02007 void *data;
a7ec9dab dan2001-01-11 02:35:21 +00008
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +02009 /*unsigned int uflags:16; */
a7ec9dab dan2001-01-11 02:35:21 +000010
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020011 WMArray *leaves;
a7ec9dab dan2001-01-11 02:35:21 +000012
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020013 int depth;
a7ec9dab dan2001-01-11 02:35:21 +000014
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020015 struct W_TreeNode *parent;
a7ec9dab dan2001-01-11 02:35:21 +000016
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020017 WMFreeDataProc *destructor;
a7ec9dab dan2001-01-11 02:35:21 +000018} W_TreeNode;
19
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020020void destroyNode(void *data)
a7ec9dab dan2001-01-11 02:35:21 +000021{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020022 WMTreeNode *aNode = (WMTreeNode *) data;
a7ec9dab dan2001-01-11 02:35:21 +000023
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020024 if (aNode->destructor) {
25 (*aNode->destructor) (aNode->data);
26 }
27 if (aNode->leaves) {
28 WMFreeArray(aNode->leaves);
29 }
30 wfree(aNode);
31}
a7ec9dab dan2001-01-11 02:35:21 +000032
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020033WMTreeNode *WMCreateTreeNode(void *data)
a7ec9dab dan2001-01-11 02:35:21 +000034{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020035 return WMCreateTreeNodeWithDestructor(data, NULL);
a7ec9dab dan2001-01-11 02:35:21 +000036}
37
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020038WMTreeNode *WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc * destructor)
a7ec9dab dan2001-01-11 02:35:21 +000039{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020040 WMTreeNode *aNode;
a7ec9dab dan2001-01-11 02:35:21 +000041
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020042 aNode = (WMTreeNode *) wmalloc(sizeof(W_TreeNode));
43 memset(aNode, 0, sizeof(W_TreeNode));
a7ec9dab dan2001-01-11 02:35:21 +000044
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020045 aNode->destructor = destructor;
a7ec9dab dan2001-01-11 02:35:21 +000046
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020047 aNode->data = data;
48 aNode->parent = NULL;
49 aNode->depth = 0;
50 aNode->leaves = NULL;
51 /*aNode->leaves = WMCreateArrayWithDestructor(1, destroyNode); */
a7ec9dab dan2001-01-11 02:35:21 +000052
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020053 return aNode;
a7ec9dab dan2001-01-11 02:35:21 +000054}
55
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020056WMTreeNode *WMInsertItemInTree(WMTreeNode * parent, int index, void *item)
a7ec9dab dan2001-01-11 02:35:21 +000057{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020058 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 }
a7ec9dab dan2001-01-11 02:35:21 +000073
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020074 return aNode;
75}
a7ec9dab dan2001-01-11 02:35:21 +000076
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020077static void updateNodeDepth(WMTreeNode * aNode, int depth)
a7ec9dab dan2001-01-11 02:35:21 +000078{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020079 int i;
a7ec9dab dan2001-01-11 02:35:21 +000080
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020081 aNode->depth = depth;
6a3b06e6 dan2001-01-18 16:59:15 +000082
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020083 if (aNode->leaves) {
84 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
85 updateNodeDepth(WMGetFromArray(aNode->leaves, i), depth + 1);
86 }
87 }
a7ec9dab dan2001-01-11 02:35:21 +000088}
89
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020090WMTreeNode *WMInsertNodeInTree(WMTreeNode * parent, int index, WMTreeNode * aNode)
a7ec9dab dan2001-01-11 02:35:21 +000091{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020092 wassertrv(parent != NULL, NULL);
93 wassertrv(aNode != NULL, NULL);
a7ec9dab dan2001-01-11 02:35:21 +000094
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020095 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 }
a7ec9dab dan2001-01-11 02:35:21 +0000105
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200106 return aNode;
107}
108
109void WMDestroyTreeNode(WMTreeNode * aNode)
a7ec9dab dan2001-01-11 02:35:21 +0000110{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200111 wassertr(aNode != NULL);
a7ec9dab dan2001-01-11 02:35:21 +0000112
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200113 if (aNode->parent && aNode->parent->leaves) {
114 WMRemoveFromArray(aNode->parent->leaves, aNode);
115 } else {
116 destroyNode(aNode);
117 }
6a3b06e6 dan2001-01-18 16:59:15 +0000118}
119
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200120void WMDeleteLeafForTreeNode(WMTreeNode * aNode, int index)
6a3b06e6 dan2001-01-18 16:59:15 +0000121{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200122 wassertr(aNode != NULL);
123 wassertr(aNode->leaves != NULL);
a7ec9dab dan2001-01-11 02:35:21 +0000124
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200125 WMDeleteFromArray(aNode->leaves, index);
a7ec9dab dan2001-01-11 02:35:21 +0000126}
127
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200128static int sameData(void *item, void *data)
a7ec9dab dan2001-01-11 02:35:21 +0000129{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200130 return (((WMTreeNode *) item)->data == data);
a7ec9dab dan2001-01-11 02:35:21 +0000131}
132
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200133void WMRemoveLeafForTreeNode(WMTreeNode * aNode, void *leaf)
6a3b06e6 dan2001-01-18 16:59:15 +0000134{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200135 int index;
6a3b06e6 dan2001-01-18 16:59:15 +0000136
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200137 wassertr(aNode != NULL);
138 wassertr(aNode->leaves != NULL);
6a3b06e6 dan2001-01-18 16:59:15 +0000139
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200140 index = WMFindInArray(aNode->leaves, sameData, leaf);
141 if (index != WANotFound) {
142 WMDeleteFromArray(aNode->leaves, index);
143 }
6a3b06e6 dan2001-01-18 16:59:15 +0000144}
145
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200146void *WMReplaceDataForTreeNode(WMTreeNode * aNode, void *newData)
a7ec9dab dan2001-01-11 02:35:21 +0000147{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200148 void *old;
6a3b06e6 dan2001-01-18 16:59:15 +0000149
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200150 wassertrv(aNode != NULL, NULL);
6a3b06e6 dan2001-01-18 16:59:15 +0000151
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200152 old = aNode->data;
153 aNode->data = newData;
6a3b06e6 dan2001-01-18 16:59:15 +0000154
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200155 return old;
a7ec9dab dan2001-01-11 02:35:21 +0000156}
157
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200158void *WMGetDataForTreeNode(WMTreeNode * aNode)
7d88519c dan2001-01-11 02:59:32 +0000159{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200160 return aNode->data;
6a3b06e6 dan2001-01-18 16:59:15 +0000161}
162
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200163int WMGetTreeNodeDepth(WMTreeNode * aNode)
6a3b06e6 dan2001-01-18 16:59:15 +0000164{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200165 return aNode->depth;
7d88519c dan2001-01-11 02:59:32 +0000166}
167
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200168WMTreeNode *WMGetParentForTreeNode(WMTreeNode * aNode)
7d88519c dan2001-01-11 02:59:32 +0000169{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200170 return aNode->parent;
7d88519c dan2001-01-11 02:59:32 +0000171}
172
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200173void WMSortLeavesForTreeNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
7d88519c dan2001-01-11 02:59:32 +0000174{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200175 wassertr(aNode != NULL);
7d88519c dan2001-01-11 02:59:32 +0000176
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200177 if (aNode->leaves) {
178 WMSortArray(aNode->leaves, comparer);
179 }
7d88519c dan2001-01-11 02:59:32 +0000180}
181
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200182static void sortLeavesForNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
7d88519c dan2001-01-11 02:59:32 +0000183{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200184 int i;
7d88519c dan2001-01-11 02:59:32 +0000185
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200186 if (!aNode->leaves)
187 return;
6a3b06e6 dan2001-01-18 16:59:15 +0000188
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200189 WMSortArray(aNode->leaves, comparer);
190 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
191 sortLeavesForNode(WMGetFromArray(aNode->leaves, i), comparer);
192 }
7d88519c dan2001-01-11 02:59:32 +0000193}
194
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200195void WMSortTree(WMTreeNode * aNode, WMCompareDataProc * comparer)
6a3b06e6 dan2001-01-18 16:59:15 +0000196{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200197 wassertr(aNode != NULL);
6a3b06e6 dan2001-01-18 16:59:15 +0000198
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200199 sortLeavesForNode(aNode, comparer);
6a3b06e6 dan2001-01-18 16:59:15 +0000200}
201
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200202static WMTreeNode *findNodeInTree(WMTreeNode * aNode, WMMatchDataProc * match, void *cdata)
6a3b06e6 dan2001-01-18 16:59:15 +0000203{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200204 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 }
6a3b06e6 dan2001-01-18 16:59:15 +0000213
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200214 if (aNode->leaves) {
215 WMTreeNode *leaf;
216 int i;
6a3b06e6 dan2001-01-18 16:59:15 +0000217
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200218 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 }
7d88519c dan2001-01-11 02:59:32 +0000225
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200226 return NULL;
7d88519c dan2001-01-11 02:59:32 +0000227}
228
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200229WMTreeNode *WMFindInTree(WMTreeNode * aTree, WMMatchDataProc * match, void *cdata)
230{
231 wassertrv(aTree != NULL, NULL);
7d88519c dan2001-01-11 02:59:32 +0000232
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200233 return findNodeInTree(aTree, match, cdata);
234}