comparison: docs/Writerside/topics/tree.h.md
docs/Writerside/topics/tree.h.md
- changeset 1273
- c35be6dc1667
- parent 1272
- d016fe8a647c
- child 1275
- 0f21abc52241
equal
deleted
inserted
replaced
| 1272:d016fe8a647c | 1273:c35be6dc1667 |
|---|---|
| 241 ```C | 241 ```C |
| 242 #include <cx/tree.h> | 242 #include <cx/tree.h> |
| 243 | 243 |
| 244 #define CX_TREE_SEARCH_INFINITE_DEPTH | 244 #define CX_TREE_SEARCH_INFINITE_DEPTH |
| 245 | 245 |
| 246 int cx_tree_search_data(const void *root, size_t depth, | 246 int cx_tree_search_data(const void *root, size_t max_depth, |
| 247 const void *data, cx_tree_search_data_func sfunc, | 247 const void *data, cx_tree_search_data_func sfunc, |
| 248 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next); | 248 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next); |
| 249 | 249 |
| 250 int cx_tree_search(const void *root, size_t depth, | 250 int cx_tree_search(const void *root, size_t max_depth, |
| 251 const void *node, cx_tree_search_func sfunc, | 251 const void *node, cx_tree_search_func sfunc, |
| 252 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next); | 252 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next); |
| 253 | 253 |
| 254 void *cxTreeFind(CxTree *tree, const void *data); | 254 void *cxTreeFind(CxTree *tree, const void *data); |
| 255 | 255 |
| 256 void *cxTreeFindInSubtree(CxTree *tree, const void *data, | 256 void *cxTreeFindInSubtree(CxTree *tree, const void *data, |
| 257 void *subtree_root, size_t max_depth); | 257 void *subtree_root, size_t max_depth); |
| 258 ``` | 258 ``` |
| 259 | 259 |
| 260 <warning> | 260 The functions `cx_tree_search_data()` and `cx_tree_search()` are equivalent, |
| 261 TODO: document low level functions | 261 except that `cx_tree_search_data()` compares a currently investigated node against the `data` with the specified `cx_tree_search_data_func`, |
| 262 </warning> | 262 and `cx_tree_search()` compares against a `node` with the specified `cx_tree_search_func`. |
| 263 | |
| 264 Usually you the latter is rarely needed. | |
| 265 It is used, for example, by `cx_tree_add()` to find the correct position where to add a freshly created node. | |
| 266 | |
| 267 The search proceeds as follows, starting with the `root` node: | |
| 268 | |
| 269 1. The current node is compared with `data` / `node` using the `sfunc`. | |
| 270 2. If `sfunc` returns zero, a matching node has been found and the pointer to that node is stored at the location given by `result`. | |
| 271 3. If `sfunc` returns a negative number, the entire subtree is skipped. | |
| 272 4. If `sfunc` returns a positive number, the subtree is searched, unless the number is larger than the number of an already searched subtree. The best match will be stored at the location given by `result`. | |
| 273 5. The return value will be the return value of the `sfunc` for node that was stored in the `result`, or a negative number when no match was found | |
| 274 | |
| 275 > If the `sfunc` implements some kind of metric, the search functions will return the best match in the tree with respect to that metric. | |
| 276 > When a positive number is returned, it means, that a new node with the searched data could be added as a child of the found node. | |
| 277 > This is exactly how `cx_tree_add()` finds the best position to add a node to the tree. | |
| 263 | 278 |
| 264 The function `cxTreeFind()` uses the `search_data_func` of the `CxTree` | 279 The function `cxTreeFind()` uses the `search_data_func` of the `CxTree` |
| 265 to find the `data` in the tree, and returns a pointer to the node when the data was found (or `NULL`, otherwise). | 280 to find the `data` in the tree, and returns a pointer to the node when the data was found (or `NULL`, otherwise). |
| 266 | 281 |
| 267 The function `cxTreeFindInSubtree()` is equivalent, except that it restricts the search to nodes | 282 The function `cxTreeFindInSubtree()` is equivalent, except that it restricts the search to nodes |
