quadtree: Implement node removing

Removing a node from a quadtree is a tricky process. The node might
have multiple children which all need to be repositioned in the
remainig tree, which propably requires a recursive recreation of the
entire (sub)tree. If the given node happens to be the root node of the
tree, a new root needs to be selected for the remaining tree.

This kind of tree manipulation might have significant impact on the
balance of the tree. On the contrary, as massive tree reorganization
might be required, this is a good opportunity to rebalance the
(sub)tree. The introduced implementation does not address any
balancing issues at all.

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

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;

diff --git a/quadtree.h b/quadtree.h
index 5631013047f6e0e47f51e2fb80ad946ae655689b..2e4a76b90b3b51376e86d3937b654a971bedf545 100644 (file)
--- a/quadtree.h
+++ b/quadtree.h
@@ -34,6 +34,10 @@ struct quadtree *quadtree_add(struct quadtree *parent,
                              int (*compare)(struct quadtree *a,
                                             struct quadtree *b));
 
+struct quadtree *quadtree_del(struct quadtree *node,
+                             int (*compare)(struct quadtree *a,
+                                            struct quadtree *b));
+
 int walk_tree(const struct quadtree_iterator *iterator);