6 typedef struct W_TreeNode
{
9 /*unsigned int uflags:16; */
15 struct W_TreeNode
*parent
;
17 WMFreeDataProc
*destructor
;
20 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 memset(aNode
, 0, sizeof(W_TreeNode
));
45 aNode
->destructor
= destructor
;
51 /*aNode->leaves = WMCreateArrayWithDestructor(1, destroyNode); */
56 WMTreeNode
*WMInsertItemInTree(WMTreeNode
* parent
, int index
, void *item
)
60 wassertrv(parent
!= NULL
, NULL
);
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
);
69 WMAddToArray(parent
->leaves
, aNode
);
71 WMInsertInArray(parent
->leaves
, index
, aNode
);
77 static void updateNodeDepth(WMTreeNode
* aNode
, int depth
)
84 for (i
= 0; i
< WMGetArrayItemCount(aNode
->leaves
); i
++) {
85 updateNodeDepth(WMGetFromArray(aNode
->leaves
, i
), depth
+ 1);
90 WMTreeNode
*WMInsertNodeInTree(WMTreeNode
* parent
, int index
, WMTreeNode
* aNode
)
92 wassertrv(parent
!= NULL
, NULL
);
93 wassertrv(aNode
!= NULL
, NULL
);
95 aNode
->parent
= parent
;
96 updateNodeDepth(aNode
, parent
->depth
+ 1);
97 if (!parent
->leaves
) {
98 parent
->leaves
= WMCreateArrayWithDestructor(1, destroyNode
);
101 WMAddToArray(parent
->leaves
, aNode
);
103 WMInsertInArray(parent
->leaves
, index
, aNode
);
109 void WMDestroyTreeNode(WMTreeNode
* aNode
)
111 wassertr(aNode
!= NULL
);
113 if (aNode
->parent
&& aNode
->parent
->leaves
) {
114 WMRemoveFromArray(aNode
->parent
->leaves
, aNode
);
120 void WMDeleteLeafForTreeNode(WMTreeNode
* aNode
, int index
)
122 wassertr(aNode
!= NULL
);
123 wassertr(aNode
->leaves
!= NULL
);
125 WMDeleteFromArray(aNode
->leaves
, index
);
128 static int sameData(void *item
, void *data
)
130 return (((WMTreeNode
*) item
)->data
== data
);
133 void WMRemoveLeafForTreeNode(WMTreeNode
* aNode
, void *leaf
)
137 wassertr(aNode
!= NULL
);
138 wassertr(aNode
->leaves
!= NULL
);
140 index
= WMFindInArray(aNode
->leaves
, sameData
, leaf
);
141 if (index
!= WANotFound
) {
142 WMDeleteFromArray(aNode
->leaves
, index
);
146 void *WMReplaceDataForTreeNode(WMTreeNode
* aNode
, void *newData
)
150 wassertrv(aNode
!= NULL
, NULL
);
153 aNode
->data
= newData
;
158 void *WMGetDataForTreeNode(WMTreeNode
* aNode
)
163 int WMGetTreeNodeDepth(WMTreeNode
* aNode
)
168 WMTreeNode
*WMGetParentForTreeNode(WMTreeNode
* aNode
)
170 return aNode
->parent
;
173 void WMSortLeavesForTreeNode(WMTreeNode
* aNode
, WMCompareDataProc
* comparer
)
175 wassertr(aNode
!= NULL
);
178 WMSortArray(aNode
->leaves
, comparer
);
182 static void sortLeavesForNode(WMTreeNode
* aNode
, WMCompareDataProc
* comparer
)
189 WMSortArray(aNode
->leaves
, comparer
);
190 for (i
= 0; i
< WMGetArrayItemCount(aNode
->leaves
); i
++) {
191 sortLeavesForNode(WMGetFromArray(aNode
->leaves
, i
), comparer
);
195 void WMSortTree(WMTreeNode
* aNode
, WMCompareDataProc
* comparer
)
197 wassertr(aNode
!= NULL
);
199 sortLeavesForNode(aNode
, comparer
);
202 static WMTreeNode
*findNodeInTree(WMTreeNode
* aNode
, WMMatchDataProc
* match
, void *cdata
)
205 if (aNode
->data
== cdata
) {
209 if ((*match
) (aNode
->data
, cdata
)) {
218 for (i
= 0; i
< WMGetArrayItemCount(aNode
->leaves
); i
++) {
219 leaf
= findNodeInTree(WMGetFromArray(aNode
->leaves
, i
), match
, cdata
);
229 WMTreeNode
*WMFindInTree(WMTreeNode
* aTree
, WMMatchDataProc
* match
, void *cdata
)
231 wassertrv(aTree
!= NULL
, NULL
);
233 return findNodeInTree(aTree
, match
, cdata
);