Quadtree: Initial commit

Add an initial and very basic form of the quadtree implementation. At
this point there is code only for the actual quadtree structure and a
function for adding nodes into the tree.

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

diff --git a/quadtree.h b/quadtree.h
new file mode 100644 (file)
index 0000000..fe31e04
--- /dev/null
+++ b/quadtree.h
@@ -0,0 +1,62 @@
+#ifndef _QUADTREE_H_
+#define _QUADTREE_H_
+
+struct quadtree {
+       struct quadtree *child[4];
+       struct quadtree *parent;
+};
+
+static inline void init_quadtree(struct quadtree *t)
+{
+       int i;
+
+       for (i = 0; i < 4; i++)
+               t->child[i] = 0;
+       t->parent = 0;
+}
+
+/**
+ * quadtree_add - add a node to a quadtree
+ * @parent: parent node
+ * @new: the new node to be added
+ * @compare: pointer to a comparison function
+ *
+ * Add a node to a quadtree. The tree is kept in order, the new node
+ * is placed in the end of appropriate branch. The compare function is
+ * used to compare the new node against a branch in the tree. The
+ * comparison function must have following return value depending on
+ * the position of node a compared to the position of node b:
+ *
+ * 0: upper left
+ * 1: upper right
+ * 2: lower left
+ * 3: lower right
+ *
+ * The case of nodes sharing identical coordinates is not taken into
+ * account at all.
+ */
+
+static inline struct quadtree *quadtree_add(struct quadtree *parent,
+                                           struct quadtree *new,
+                                           int (*compare)(struct quadtree *a,
+                                                          struct quadtree *b))
+{
+       int ret;
+
+       ret = compare(parent, new);
+
+       if (ret < 0 || ret >= 4) {
+               printf("Invalid comparison result of %d\n", ret);
+               return 0;
+       }
+
+       if (parent->child[ret])
+               return quadtree_add(parent->child[ret], new, compare);
+
+       parent->child[ret] = new;
+       new->parent = parent;
+
+       return new;
+}
+
+#endif