quadtree: Implement node removing

[sdl-planets] / quadtree.c

diff --git a/quadtree.c b/quadtree.c
index ee1bc88a9fd086858f6577e9041c93a799645833..5e1eea746c5616e142933953be37730de3473e8d 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -46,6 +46,88 @@ struct quadtree *quadtree_add(struct quadtree *parent,
        return new;
 }
 
+/*
+ * _quadtree_reposition_reqursively - Move everything under and
+ * including a given node under the new root node
+ */
+
+static void
+_quadtree_reposition_reqursively(struct quadtree *root,
+                                struct quadtree *node,
+                                int (*compare)(struct quadtree *a,
+                                               struct quadtree *b))
+{
+       int i;
+
+       /* First remove all children, if any */
+       for (i = 0; i < 4; i++) {
+               if (!node->child[i])
+                       continue;
+
+               _quadtree_reposition_reqursively(root, node->child[i], compare);
+               node->child[i] = 0;
+       }
+
+       /* Then remove this node under the new root. */
+       quadtree_add(root, node, compare);
+}
+
+/*
+ * quadtree_del - Detach a node from the tree
+ *
+ * Return value: The new root node of the tree. If we are detaching
+ * anything but the root node of the entire tree, the returned root
+ * value will be the original root of the tree.
+ */
+struct quadtree *quadtree_del(struct quadtree *node,
+                             int (*compare)(struct quadtree *a,
+                                            struct quadtree *b))
+{
+       struct quadtree *parent = 0;
+       int i;
+
+       /*
+        * We are deleting the root node. This means we have to select
+        * a new root node and reconstruct the entire tree under it
+        * again.
+        */
+       if (!node->parent) {
+               for (i = 0; i < 4; i++) {
+                       if (!node->child[i])
+                               continue;
+
+                       if (!parent) {
+                               parent = node->child[i];
+                               continue;
+                       }
+                       _quadtree_reposition_reqursively(parent,
+                                                        node->child[i],
+                                                        compare);
+                       node->child[i] = 0;
+               }
+
+               return parent;
+       }
+
+       /*
+        * We are not deleting the parent. Just relocate the children
+        * and detach the node from the tree.
+        */
+       for (i = 0; i < 4; i++) {
+               if (!node->child[i])
+                       continue;
+
+               _quadtree_reposition_reqursively(node->parent, node->child[i],
+                                                compare);
+       }
+
+       parent = quadtree_find_parent(node);
+       node->parent = 0;
+
+       return parent;
+}
+
+
 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
 {
        int direction, count = 0;