Optimization, work in proggress..

diff --git a/quadtree.c b/quadtree.c
index 804bab00521053d02216260500506b351142902e..930a8f6ae5435ee00115ab9be7211ebcbf39860d 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -201,6 +201,37 @@ _quadtree_reposition_reqursively(struct quadtree *root,
        }
 }
 
+static _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
+                      struct quadtree_ops *ops, int parents)
+{
+       struct quadtree *child[4];
+       int i, nodes_left = 0, children = 0;
+
+       for (i = 0; i < 4; i++) {
+               if (!node->child[i])
+                       continue;
+
+               child[children] = node->child[i];
+               nodes_left += child[children]->children + 1;
+               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.
+        */
+
+       if (node->children <= parents / 4) {
+               quadtree_add(parent, node, ops);
+               node = NULL;
+       }
+
+       while(children) {
+
+}
+
 /*
  * quadtree_del - Detach a node from the tree
  *
@@ -212,6 +243,7 @@ struct quadtree *quadtree_del(struct quadtree *node,
                              struct quadtree_ops *ops)
 {
        struct quadtree *parent = 0;
+       struct quadtree *n;
        int i;
 
        /*
@@ -250,35 +282,24 @@ struct quadtree *quadtree_del(struct quadtree *node,
                        break;
                }
        }
-       if (i == 4) {
-               printf("%s:%d Fatal! Tree inconsistency detected\n",
-                      __func__, __LINE__);
-               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;
-       }
+       if (node->children)
+               _qt_del_optimal(parent, node, ops, node->children);
 
-       parent = quadtree_find_parent(node);
        node->parent = 0;
 
        node->children = 0;
        node->depth = 0;
 
+       parent = quadtree_find_parent(parent);
        validate_tree(parent);
        return parent;
 }