6 * quadtree_add - add a node to a quadtree
8 * @new: the new node to be added
9 * @compare: pointer to a comparison function
11 * Add a node to a quadtree. The tree is kept in order, the new node
12 * is placed in the end of appropriate branch. The compare function is
13 * used to compare the new node against a branch in the tree. The
14 * comparison function must have following return value depending on
15 * the position of node a compared to the position of node b:
22 * The case of nodes sharing identical coordinates is not taken into
26 struct quadtree *quadtree_add(struct quadtree *parent,
28 int (*compare)(struct quadtree *a,
33 ret = compare(parent, new);
35 if (ret < 0 || ret >= 4) {
36 printf("Invalid comparison result of %d\n", ret);
40 if (parent->child[ret])
41 return quadtree_add(parent->child[ret], new, compare);
43 parent->child[ret] = new;
49 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
51 int direction, count = 0;
53 direction = it->direction(head, it->ptr);
55 if ((direction & QUADTREE_UPLEFT) && head->child[0])
56 count += _walk_tree(head->child[0], it);
58 if ((direction & QUADTREE_UPRIGHT) && head->child[1])
59 count += _walk_tree(head->child[1], it);
61 if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
62 count += _walk_tree(head->child[2], it);
64 if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
65 count += _walk_tree(head->child[3], it);
67 if ((direction & QUADTREE_SELF) && it->callback) {
68 it->callback(head, it->ptr);
76 int walk_tree(const struct quadtree_iterator *it)
78 return _walk_tree(it->head, it);