From 599ac8f467bde1e71e8a2b034d9988c6b1cb3807 Mon Sep 17 00:00:00 2001
From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Sat, 24 Apr 2010 14:00:49 +0300
Subject: [PATCH] quadtree: Try to keep the tree in better balance.

When a tree node is removed, we now attempt to add the detached
subtree in more optimized order to the new tree. This is done so that
we walk down the detached tree and add a new node to the main tree
always when the tree is one quarter'th smaller than the previous node
that was added.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
---
 quadtree.c | 118 ++++++++++++++++++++++++++++++++---------------------
 1 file changed, 72 insertions(+), 46 deletions(-)

diff --git a/quadtree.c b/quadtree.c
index a331539..61a2699 100644
--- a/quadtree.c
+++ b/quadtree.c
@@ -157,39 +157,72 @@ struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
 }
 
 /*
- * _quadtree_reposition_reqursively - Move everything under and
- * including a given node under the new root node
+ * _qt_optimal_del - Delete nodes from a detached subtree in optimal order
+ *
+ * All nodes are moved under the new parent node
  */
-
-static void
-_quadtree_reposition_reqursively(struct quadtree *root,
-				 struct quadtree *node,
-				 struct quadtree_ops *ops)
+static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
+		       struct quadtree_ops *ops, int parents)
 {
-	int i;
-
-	validate_tree(root);
-
-	/* First remove all children, if any */
+	struct quadtree *child[4] = {0};
+	int i, children = 0, max_c, max_i;
 
 	for (i = 0; i < 4; i++) {
-		if (!node->child[i])
+		if (!node->child[i]) {
+			child[i] = 0;
 			continue;
+		}
 
-		if (node->child[i] == node ||
-		    node->child[i] == node->parent)
-			trap();
+		child[children] = node->child[i];
+		node->child[i] = NULL;
+		children++;
+	}
+
+	/*
+	 * Try to remove the nodes in such order that the node which
+	 * has child number one quarter of the parent's child numer
+	 * gets deleted first.
+	 */
 
-		_quadtree_reposition_reqursively(root, node->child[i], ops);
-		node->child[i] = 0;
+	if (node->children <= parents / 4) {
+		if (debug) {
+			printf("%d: Moving node %p away from parent %p\n",
+			       __LINE__, node, parent);
+			fflush(stdout);
+		}
+		validate_tree(parent);
+		quadtree_add(parent, node, ops);
+		node = NULL;
+		parents /= 4;
 	}
 
-	/* There are no children left, reset stats */
-	node->depth = 0;
-	node->children = 0;
+	while(children) {
+		max_c = -1;
+		max_i = -1;
+		for (i = 0; i < 4; i++) {
+			if (!child[i])
+				continue;
+
+			if (max_c < child[i]->children) {
+				max_c = child[i]->children;
+				max_i = i;
+			}
+		}
 
-	/* Then remove this node under the new root. */
-	quadtree_add(root, node, ops);
+		_qt_optimal_del(parent, child[max_i], ops, parents / 4);
+		child[max_i] = 0;
+		children--;
+	}
+
+	if (node) {
+		validate_tree(parent);
+		if (debug) {
+			printf("%d: Moving node %p away from parent %p\n",
+			       __LINE__, node, parent);
+			fflush(stdout);
+		}
+		quadtree_add(parent, node, ops);
+	}
 }
 
 /*
@@ -225,9 +258,8 @@ struct quadtree *quadtree_del(struct quadtree *node,
 				parent->parent = 0;
 				continue;
 			}
-			_quadtree_reposition_reqursively(parent,
-							 node->child[i],
-							 ops);
+			_qt_optimal_del(parent, node->child[i], ops,
+					node->children);
 			node->child[i] = 0;
 		}
 
@@ -246,34 +278,28 @@ struct quadtree *quadtree_del(struct quadtree *node,
 			break;
 		}
 	}
-	if (i == 4) {
-		printf("%s:%d Fatal! Tree inconsistency detected\n",
-		       __func__, __LINE__);
+	if (i == 4)
 		trap();
-	}
 
-	/* Fix parent stats */
-	quadtree_recalculate_parent_stats(node->parent, ops);
+	parent = node->parent;
 
 	/*
-	 * The sub branch is now detached from the main tree. Continue
-	 * relocating the detached branch.
+	 * The sub branch is now detached from the main tree. Fix the
+	 * stats.
 	 */
+	quadtree_recalculate_parent_stats(node->parent, ops);
 
-	for (i = 0; i < 4; i++) {
-		if (!node->child[i])
-			continue;
-
-		_quadtree_reposition_reqursively(node->parent, node->child[i],
-						 ops);
-		node->child[i] = 0;
-	}
+	parent = quadtree_find_parent(parent);
 
-	parent = quadtree_find_parent(node);
-	node->parent = 0;
+	if (node->children) {
+		for (i = 0; i < 4; i++) {
+			if (!node->child[i])
+				continue;
 
-	node->children = 0;
-	node->depth = 0;
+			_qt_optimal_del(parent, node->child[i], ops,
+					node->children);
+		}
+	}
 
 	validate_tree(parent);
 	return parent;
-- 
2.45.0