quadtree: Add support to walk through the tree

An iterator structure can be used to walk only desired parts of the
tree, while the rest of the tree is left untouched.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index ba8cf9f1999372ce135459e23fce46aa2e63051e..ee1bc88a9fd086858f6577e9041c93a799645833 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -46,3 +46,34 @@ struct quadtree *quadtree_add(struct quadtree *parent,
        return new;
 }
 
+static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
+{
+       int direction, count = 0;
+
+       direction = it->direction(head, it->ptr);
+
+       if ((direction & QUADTREE_UPLEFT) && head->child[0])
+               count += _walk_tree(head->child[0], it);
+
+       if ((direction & QUADTREE_UPRIGHT) && head->child[1])
+               count += _walk_tree(head->child[1], it);
+
+       if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
+               count += _walk_tree(head->child[2], it);
+
+       if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
+               count += _walk_tree(head->child[3], it);
+
+       if ((direction & QUADTREE_SELF) && it->callback) {
+               it->callback(head, it->ptr);
+               count++;
+       }
+
+       return count;
+}
+
+
+int walk_tree(const struct quadtree_iterator *it)
+{
+       return _walk_tree(it->head, it);
+}

diff --git a/quadtree.h b/quadtree.h
index dee62d6b90f5d1d4af1072f58863321fd9c179f6..4e478159a56855d3205d1ec4cf21142fd835992e 100644 (file)
--- a/quadtree.h
+++ b/quadtree.h
@@ -15,4 +15,20 @@ static inline void init_quadtree(struct quadtree *t)
        t->parent = 0;
 }
 
+#define QUADTREE_UPLEFT                0x1
+#define QUADTREE_UPRIGHT       0x2
+#define QUADTREE_DOWNLEFT      0x4
+#define QUADTREE_DOWNRIGHT     0x8
+#define QUADTREE_SELF          0x10
+
+struct quadtree_iterator {
+       struct quadtree *head;
+       void *ptr;
+
+       int (*direction)(struct quadtree *head, void *ptr);
+       void (*callback)(struct quadtree *head, void *ptr);
+};
+
+int walk_tree(const struct quadtree_iterator *iterator);
+
 #endif