When repositioning a subtree, move nodes in random order

diff --git a/quadtree.c b/quadtree.c
index a914f66324a8e0a6ba09d5ccfc50bd6d0c3c1128..804bab00521053d02216260500506b351142902e 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -148,30 +148,57 @@ _quadtree_reposition_reqursively(struct quadtree *root,
                                 struct quadtree *node,
                                 struct quadtree_ops *ops)
 {
-       int i;
+       struct quadtree *n, *tmp;
+       int i, j, idx = 0;
 
-       validate_tree(root);
+       n = node;
 
-       /* First remove all children, if any */
+       while (1) {
+               idx++;
 
-       for (i = 0; i < 4; i++) {
-               if (!node->child[i])
-                       continue;
+               for (i = 0; i < 4; i++)
+                       if (n->child[(i + idx) & 3])
+                               break;
 
-               if (node->child[i] == node ||
-                   node->child[i] == node->parent)
-                       trap();
+               if (i < 4) {
+                       /* There are children left for n */
 
-               _quadtree_reposition_reqursively(root, node->child[i], ops);
-               node->child[i] = 0;
-       }
+                       tmp = n->child[(i + idx) & 3];
+                       for (j = 0; j < 4; j++)
+                               if (tmp->child[j])
+                                       break;
 
-       /* There are no children left, reset stats */
-       node->depth = 0;
-       node->children = 0;
+                       /* tmp has got children as well */
+                       if (j < 4) {
+                               n = tmp;
+                               continue;
+                       }
 
-       /* Then remove this node under the new root. */
-       quadtree_add(root, node, ops);
+                       /* tmp has no more children, move it */
+                       validate_tree(root);
+
+                       n->child[(i + idx) & 3] = NULL;
+
+                       tmp->depth = 0;
+                       tmp->children = 0;
+                       tmp->parent = NULL;
+                       quadtree_add(root, tmp, ops);
+
+                       continue;
+               }
+
+               /* n has no more children left */
+               if (n == node) {
+                       n->depth = 0;
+                       n->children = 0;
+                       n->parent = NULL;
+                       quadtree_add(root, n, ops);
+
+                       break;
+               }
+
+               n = node;
+       }
 }
 
 /*