From 354913a46f51a570f4c4f1d51fe736777723e847 Mon Sep 17 00:00:00 2001
From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Sat, 10 Apr 2010 17:39:07 +0300
Subject: [PATCH] quadtree: Collect tree statistics

Tree depth and child count is collected and kept up to date.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
---
 quadtree.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 quadtree.h | 39 ++++++++++++++++++++++++++++++++++-----
 2 files changed, 86 insertions(+), 5 deletions(-)

diff --git a/quadtree.c b/quadtree.c
index 7d9273c..e827595 100644
--- a/quadtree.c
+++ b/quadtree.c
@@ -18,6 +18,8 @@ static void trap(void )
 static void validate_subtree(const struct quadtree *node)
 {
 	int i;
+	long int children;
+	children = 0;
 
 	for (i = 0; i < 4; i++) {
 		if (!node->child[i])
@@ -29,6 +31,7 @@ static void validate_subtree(const struct quadtree *node)
 			       __func__, __LINE__, i, node);
 			trap();
 		}
+
 		if (node->parent) {
 			if (node->child[i] == node->parent) {
 				printf("%s:%d Fatal! Tree loop detected "
@@ -38,8 +41,45 @@ static void validate_subtree(const struct quadtree *node)
 			}
 		}
 
+		children += node->child[i]->children + 1;
+
 		validate_subtree(node->child[i]);
 	}
+
+	if (node->depth < 0) {
+		printf("%s:%d Tree statistics inconsistency detected! "
+		       "Negative depth: %ld\n",
+		       __func__, __LINE__, node->depth);
+	}
+
+	if (node->children != children) {
+		printf("%s:%d Tree statistics inconsistency detected! "
+		       "child count mismatch. Expected %ld, got %ld\n",
+		       __func__, __LINE__, children, node->children);
+		trap();
+	}
+
+	for (i = 0; i < 4 && node->children; i++) {
+		if (!node->child[i])
+			continue;
+
+		if (node->depth == node->child[i]->depth + 1)
+			break;
+
+		if (node->child[i]->depth > node->depth) {
+			printf("%s:%d Tree statistics inconsistency detected! "
+			       "child depth mismatch %ld > %ld\n",
+			       __func__, __LINE__, node->child[i]->depth,
+			       node->depth);
+		}
+	}
+
+	if (i == 4) {
+		printf("%s:%d Tree statistics inconsistency detected! "
+		       "child depth mismatch.",
+		       __func__, __LINE__);
+		trap();
+	}
 }
 
 static void validate_tree(const struct quadtree *node)
@@ -93,6 +133,8 @@ struct quadtree *quadtree_add(struct quadtree *parent,
 	parent->child[ret] = new;
 	new->parent = parent;
 
+	quadtree_recalculate_parent_stats(parent);
+
 	validate_tree(new);
 
 	return new;
@@ -127,6 +169,10 @@ _quadtree_reposition_reqursively(struct quadtree *root,
 		node->child[i] = 0;
 	}
 
+	/* There are no children left, reset stats */
+	node->depth = 0;
+	node->children = 0;
+
 	/* Then remove this node under the new root. */
 	quadtree_add(root, node, compare);
 }
@@ -186,6 +232,9 @@ struct quadtree *quadtree_del(struct quadtree *node,
 		trap();
 	}
 
+	/* Fix parent stats */
+	quadtree_recalculate_parent_stats(node->parent);
+
 	/*
 	 * The sub branch is now detached from the main tree. Continue
 	 * relocating the detached branch.
@@ -203,6 +252,9 @@ struct quadtree *quadtree_del(struct quadtree *node,
 	parent = quadtree_find_parent(node);
 	node->parent = 0;
 
+	node->children = 0;
+	node->depth = 0;
+
 	validate_tree(parent);
 	return parent;
 }
diff --git a/quadtree.h b/quadtree.h
index 23b79ce..3d8f518 100644
--- a/quadtree.h
+++ b/quadtree.h
@@ -1,18 +1,22 @@
 #ifndef _QUADTREE_H_
 #define _QUADTREE_H_
 
+#include <string.h>
+
+#include "utils.h"
+
 struct quadtree {
 	struct quadtree *child[4];
 	struct quadtree *parent;
+
+	/* statistics */
+	long int children;	/* The total number of children */
+	long int depth;		/* The deepest subtree branch */
 };
 
 static inline void init_quadtree(struct quadtree *t)
 {
-	int i;
-
-	for (i = 0; i < 4; i++)
-		t->child[i] = 0;
-	t->parent = 0;
+	memset(t, 0, sizeof(*t));
 }
 
 #define QUADTREE_UPLEFT		0x1
@@ -51,4 +55,29 @@ static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
 	return t;
 }
 
+/*
+ * Recursively walk through the tree and propagate changes made to the
+ * given node up until the highest parent.
+ */
+static inline void quadtree_recalculate_parent_stats(struct quadtree *node)
+{
+	int i;
+
+	while (node) {
+		node->depth = 0;
+		node->children = 0;
+
+		for (i = 0; i < 4; i++) {
+			if (!node->child[i])
+				continue;
+
+			node->depth = MAX(node->depth,
+					  node->child[i]->depth + 1);
+			node->children += node->child[i]->children + 1;
+		}
+
+		node = node->parent;
+	}
+}
+
 #endif
-- 
2.45.0