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>

diff --git a/quadtree.c b/quadtree.c
index 7d9273c363d5626dc95b7bcf6245506281efd2c0..e827595309fe549425c6594a51a7a7a56ef0178c 100644 (file)
--- 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 23b79cebd7595d51875618fadedc42129fd0d5b8..3d8f51835ddad4a2c6c549b856ab12b1fad2a3c2 100644 (file)
--- 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