From b3f2325feea76de6f355651c9f95b290cca6a0dc Mon Sep 17 00:00:00 2001
From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Mon, 5 Apr 2010 12:19:26 +0300
Subject: [PATCH] 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>
---
 quadtree.c | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 quadtree.h |  4 +++
 2 files changed, 86 insertions(+)

diff --git a/quadtree.c b/quadtree.c
index ee1bc88..5e1eea7 100644
--- 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 5631013..2e4a76b 100644
--- 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);
 
 
-- 
2.44.0