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;
50 * _quadtree_reposition_reqursively - Move everything under and
51 * including a given node under the new root node
55 _quadtree_reposition_reqursively(struct quadtree *root,
56 struct quadtree *node,
57 int (*compare)(struct quadtree *a,
62 /* First remove all children, if any */
63 for (i = 0; i < 4; i++) {
67 _quadtree_reposition_reqursively(root, node->child[i], compare);
71 /* Then remove this node under the new root. */
72 quadtree_add(root, node, compare);
76 * quadtree_del - Detach a node from the tree
78 * Return value: The new root node of the tree. If we are detaching
79 * anything but the root node of the entire tree, the returned root
80 * value will be the original root of the tree.
82 struct quadtree *quadtree_del(struct quadtree *node,
83 int (*compare)(struct quadtree *a,
86 struct quadtree *parent = 0;
90 * We are deleting the root node. This means we have to select
91 * a new root node and reconstruct the entire tree under it
95 for (i = 0; i < 4; i++) {
100 parent = node->child[i];
103 _quadtree_reposition_reqursively(parent,
113 * We are not deleting the parent. Just relocate the children
114 * and detach the node from the tree.
116 for (i = 0; i < 4; i++) {
120 _quadtree_reposition_reqursively(node->parent, node->child[i],
124 parent = quadtree_find_parent(node);
131 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
133 int direction, count = 0;
135 direction = it->direction(head, it->ptr);
137 if ((direction & QUADTREE_UPLEFT) && head->child[0])
138 count += _walk_tree(head->child[0], it);
140 if ((direction & QUADTREE_UPRIGHT) && head->child[1])
141 count += _walk_tree(head->child[1], it);
143 if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
144 count += _walk_tree(head->child[2], it);
146 if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
147 count += _walk_tree(head->child[3], it);
149 if ((direction & QUADTREE_SELF) && it->callback) {
150 it->callback(head, it->ptr);
158 int walk_tree(const struct quadtree_iterator *it)
160 return _walk_tree(it->head, it);