6 typedef struct W_TreeNode
{
9 /*unsigned int uflags:16; */
15 struct W_TreeNode
*parent
;
17 WMFreeDataProc
*destructor
;
20 static void destroyNode(void *data
)
22 WMTreeNode
*aNode
= (WMTreeNode
*) data
;
24 if (aNode
->destructor
) {
25 (*aNode
->destructor
) (aNode
->data
);
28 WMFreeArray(aNode
->leaves
);
33 WMTreeNode
*WMCreateTreeNode(void *data
)
35 return WMCreateTreeNodeWithDestructor(data
, NULL
);
38 WMTreeNode
*WMCreateTreeNodeWithDestructor(void *data
, WMFreeDataProc
* destructor
)
42 aNode
= (WMTreeNode
*) wmalloc(sizeof(W_TreeNode
));
43 aNode
->destructor
= destructor
;
48 /*aNode->leaves = WMCreateArrayWithDestructor(1, destroyNode); */
53 WMTreeNode
*WMInsertItemInTree(WMTreeNode
* parent
, int index
, void *item
)
57 wassertrv(parent
!= NULL
, NULL
);
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
);
66 WMAddToArray(parent
->leaves
, aNode
);
68 WMInsertInArray(parent
->leaves
, index
, aNode
);
74 static void updateNodeDepth(WMTreeNode
* aNode
, int depth
)
81 for (i
= 0; i
< WMGetArrayItemCount(aNode
->leaves
); i
++) {
82 updateNodeDepth(WMGetFromArray(aNode
->leaves
, i
), depth
+ 1);
87 WMTreeNode
*WMInsertNodeInTree(WMTreeNode
* parent
, int index
, WMTreeNode
* aNode
)
89 wassertrv(parent
!= NULL
, NULL
);
90 wassertrv(aNode
!= NULL
, NULL
);
92 aNode
->parent
= parent
;
93 updateNodeDepth(aNode
, parent
->depth
+ 1);
94 if (!parent
->leaves
) {
95 parent
->leaves
= WMCreateArrayWithDestructor(1, destroyNode
);
98 WMAddToArray(parent
->leaves
, aNode
);
100 WMInsertInArray(parent
->leaves
, index
, aNode
);
106 void WMDestroyTreeNode(WMTreeNode
* aNode
)
108 wassertr(aNode
!= NULL
);
110 if (aNode
->parent
&& aNode
->parent
->leaves
) {
111 WMRemoveFromArray(aNode
->parent
->leaves
, aNode
);
117 void WMDeleteLeafForTreeNode(WMTreeNode
* aNode
, int index
)
119 wassertr(aNode
!= NULL
);
120 wassertr(aNode
->leaves
!= NULL
);
122 WMDeleteFromArray(aNode
->leaves
, index
);
125 static int sameData(const void *item
, const void *data
)
127 return (((WMTreeNode
*) item
)->data
== data
);
130 void WMRemoveLeafForTreeNode(WMTreeNode
* aNode
, void *leaf
)
134 wassertr(aNode
!= NULL
);
135 wassertr(aNode
->leaves
!= NULL
);
137 index
= WMFindInArray(aNode
->leaves
, sameData
, leaf
);
138 if (index
!= WANotFound
) {
139 WMDeleteFromArray(aNode
->leaves
, index
);
143 void *WMReplaceDataForTreeNode(WMTreeNode
* aNode
, void *newData
)
147 wassertrv(aNode
!= NULL
, NULL
);
150 aNode
->data
= newData
;
155 void *WMGetDataForTreeNode(WMTreeNode
* aNode
)
160 int WMGetTreeNodeDepth(WMTreeNode
* aNode
)
165 WMTreeNode
*WMGetParentForTreeNode(WMTreeNode
* aNode
)
167 return aNode
->parent
;
170 void WMSortLeavesForTreeNode(WMTreeNode
* aNode
, WMCompareDataProc
* comparer
)
172 wassertr(aNode
!= NULL
);
175 WMSortArray(aNode
->leaves
, comparer
);
179 static void sortLeavesForNode(WMTreeNode
* aNode
, WMCompareDataProc
* comparer
)
186 WMSortArray(aNode
->leaves
, comparer
);
187 for (i
= 0; i
< WMGetArrayItemCount(aNode
->leaves
); i
++) {
188 sortLeavesForNode(WMGetFromArray(aNode
->leaves
, i
), comparer
);
192 void WMSortTree(WMTreeNode
* aNode
, WMCompareDataProc
* comparer
)
194 wassertr(aNode
!= NULL
);
196 sortLeavesForNode(aNode
, comparer
);
199 static WMTreeNode
*findNodeInTree(WMTreeNode
* aNode
, WMMatchDataProc
* match
, void *cdata
, int limit
)
201 if (match
== NULL
&& aNode
->data
== cdata
)
203 else if (match
&& (*match
) (aNode
->data
, cdata
))
206 if (aNode
->leaves
&& limit
!= 0) {
210 for (i
= 0; i
< WMGetArrayItemCount(aNode
->leaves
); i
++) {
211 leaf
= findNodeInTree(WMGetFromArray(aNode
->leaves
, i
),
212 match
, cdata
, limit
> 0 ? limit
- 1 : limit
);
221 WMTreeNode
*WMFindInTree(WMTreeNode
* aTree
, WMMatchDataProc
* match
, void *cdata
)
223 wassertrv(aTree
!= NULL
, NULL
);
225 return findNodeInTree(aTree
, match
, cdata
, -1);
228 WMTreeNode
*WMFindInTreeWithDepthLimit(WMTreeNode
* aTree
, WMMatchDataProc
* match
, void *cdata
, int limit
)
230 wassertrv(aTree
!= NULL
, NULL
);
231 wassertrv(limit
>= 0, NULL
);
233 return findNodeInTree(aTree
, match
, cdata
, limit
);
236 void WMTreeWalk(WMTreeNode
* aNode
, WMTreeWalkProc
* walk
, void *data
, Bool DepthFirst
)
241 wassertr(aNode
!= NULL
);
244 (*walk
)(aNode
, data
);
247 for (i
= 0; i
< WMGetArrayItemCount(aNode
->leaves
); i
++) {
248 leaf
= (WMTreeNode
*)WMGetFromArray(aNode
->leaves
, i
);
249 WMTreeWalk(leaf
, walk
, data
, DepthFirst
);
254 (*walk
)(aNode
, data
);