From 23092e17ca23f5bc4a214062c6583c911e24f1e9 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Mon, 9 May 2011 11:46:30 -0600
Subject: Make dmnsn_new_prtree() more scalable.

---
 libdimension/prtree.c | 595 +++++++++++++++++++-------------------------------
 1 file changed, 223 insertions(+), 372 deletions(-)

(limited to 'libdimension/prtree.c')

diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index 9a329ce..2738d40 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -30,8 +30,8 @@
 
 /** Number of children per PR-node. */
 #define DMNSN_PRTREE_B 8
-/** Number of children per pseudo-PR-node (must be 2*ndimensions). */
-#define DMNSN_PSEUDO_PRTREE_B 6
+/** Number of priority leaves per pseudo-PR-node (must be 2*ndimensions). */
+#define DMNSN_PSEUDO_B 6
 
 /** A flat node for storing in an array for fast pre-order traversal. */
 typedef struct dmnsn_flat_prnode {
@@ -40,45 +40,55 @@ typedef struct dmnsn_flat_prnode {
   size_t skip;
 } dmnsn_flat_prnode;
 
+/** The side of the split that a node ended up on. */
+typedef enum dmnsn_prnode_location {
+  DMNSN_PRTREE_LEAF, /**< Priority leaf. */
+  DMNSN_PRTREE_LEFT, /**< Left child. */
+  DMNSN_PRTREE_RIGHT /**< Right child. */
+} dmnsn_prnode_location;
+
 /** Pseudo PR-tree node. */
-typedef struct dmnsn_prtree_node {
+typedef struct dmnsn_prnode {
   dmnsn_bounding_box bounding_box;
 
-  /* Children (objects or subtrees) */
-  bool is_leaf;
-  void *children[DMNSN_PRTREE_B];
-} dmnsn_prtree_node;
+  dmnsn_object *object;
+  struct dmnsn_prnode *children[DMNSN_PRTREE_B];
 
-/** Pseudo PR-tree leaf node. */
-typedef struct dmnsn_pseudo_prleaf {
-  void *children[DMNSN_PRTREE_B];
-  bool is_leaf;
-  dmnsn_bounding_box bounding_box;
-} dmnsn_pseudo_prleaf;
-
-typedef struct dmnsn_pseudo_prtree dmnsn_pseudo_prtree;
-
-/** Pseudo PR-tree internal node. */
-typedef struct dmnsn_pseudo_prnode {
-  dmnsn_pseudo_prtree *left, *right;
-  dmnsn_pseudo_prleaf children[DMNSN_PSEUDO_PRTREE_B];
-} dmnsn_pseudo_prnode;
-
-/** Pseudo PR-tree. */
-struct dmnsn_pseudo_prtree {
-  bool is_leaf;
-  union {
-    dmnsn_pseudo_prleaf leaf;
-    dmnsn_pseudo_prnode node;
-  } pseudo;
-};
+  dmnsn_prnode_location location;
+} dmnsn_prnode;
+
+/** Construct an empty PR-node. */
+static inline dmnsn_prnode *
+dmnsn_new_prnode()
+{
+  dmnsn_prnode *node = dmnsn_malloc(sizeof(dmnsn_prnode));
+  node->bounding_box = dmnsn_zero_bounding_box();
+  node->object       = NULL;
+  node->location     = DMNSN_PRTREE_LEFT; /* Mustn't be _LEAF */
+  for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
+    node->children[i] = NULL;
+  }
+  return node;
+}
+
+/** Free a non-flat PR-tree. */
+static void
+dmnsn_delete_prnode(dmnsn_prnode *node)
+{
+  if (node) {
+    for (size_t i = 0; i < DMNSN_PRTREE_B && node->children[i]; ++i) {
+      dmnsn_delete_prnode(node->children[i]);
+    }
+    dmnsn_free(node);
+  }
+}
 
 /** Expand a node to contain the bounding box \p box. */
 static void
-dmnsn_pseudo_prleaf_swallow(dmnsn_pseudo_prleaf *leaf, dmnsn_bounding_box box)
+dmnsn_prnode_swallow(dmnsn_prnode *node, dmnsn_bounding_box box)
 {
-  leaf->bounding_box.min = dmnsn_vector_min(leaf->bounding_box.min, box.min);
-  leaf->bounding_box.max = dmnsn_vector_max(leaf->bounding_box.max, box.max);
+  node->bounding_box.min = dmnsn_vector_min(node->bounding_box.min, box.min);
+  node->bounding_box.max = dmnsn_vector_max(node->bounding_box.max, box.max);
 }
 
 /** Comparator types. */
@@ -93,379 +103,259 @@ enum {
 
 /** Get a coordinate of the bounding box of a node. */
 static inline double
-dmnsn_priority_get(const dmnsn_list_iterator *i, bool is_object, int comparator)
+dmnsn_get_coordinate(const dmnsn_list_iterator *i, int comparator)
 {
-  dmnsn_bounding_box box;
-
-  if (is_object) {
-    dmnsn_object **object = dmnsn_list_at(i);
-    box = (*object)->bounding_box;
-  } else {
-    dmnsn_prtree_node **prnode = dmnsn_list_at(i);
-    box = (*prnode)->bounding_box;
-  }
+  dmnsn_prnode **node = dmnsn_list_at(i);
 
   switch (comparator) {
   case DMNSN_XMIN:
-    return box.min.x;
+    return (*node)->bounding_box.min.x;
   case DMNSN_YMIN:
-    return box.min.y;
+    return (*node)->bounding_box.min.y;
   case DMNSN_ZMIN:
-    return box.min.z;
+    return (*node)->bounding_box.min.z;
 
   case DMNSN_XMAX:
-    return -box.max.x;
+    return -(*node)->bounding_box.max.x;
   case DMNSN_YMAX:
-    return -box.max.y;
+    return -(*node)->bounding_box.max.y;
   case DMNSN_ZMAX:
-    return -box.max.z;
+    return -(*node)->bounding_box.max.z;
 
   default:
     dmnsn_assert(false, "Invalid comparator.");
-    return 0.0;
+    return 0.0; /* Shut up compiler */
   }
 }
 
 /* List sorting comparators */
 
 static bool
-dmnsn_xmin_object_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
-{
-  double lval = dmnsn_priority_get(l, true, DMNSN_XMIN);
-  double rval = dmnsn_priority_get(r, true, DMNSN_XMIN);
-  return lval < rval;
-}
-
-static bool
-dmnsn_xmin_prnode_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
-{
-  double lval = dmnsn_priority_get(l, false, DMNSN_XMIN);
-  double rval = dmnsn_priority_get(r, false, DMNSN_XMIN);
-  return lval < rval;
-}
-
-static bool
-dmnsn_ymin_object_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
+dmnsn_xmin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
 {
-  double lval = dmnsn_priority_get(l, true, DMNSN_YMIN);
-  double rval = dmnsn_priority_get(r, true, DMNSN_YMIN);
+  double lval = dmnsn_get_coordinate(l, DMNSN_XMIN);
+  double rval = dmnsn_get_coordinate(r, DMNSN_XMIN);
   return lval < rval;
 }
 
 static bool
-dmnsn_ymin_prnode_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
+dmnsn_ymin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
 {
-  double lval = dmnsn_priority_get(l, false, DMNSN_YMIN);
-  double rval = dmnsn_priority_get(r, false, DMNSN_YMIN);
+  double lval = dmnsn_get_coordinate(l, DMNSN_YMIN);
+  double rval = dmnsn_get_coordinate(r, DMNSN_YMIN);
   return lval < rval;
 }
 
 static bool
-dmnsn_zmin_object_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
+dmnsn_zmin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
 {
-  double lval = dmnsn_priority_get(l, true, DMNSN_ZMIN);
-  double rval = dmnsn_priority_get(r, true, DMNSN_ZMIN);
+  double lval = dmnsn_get_coordinate(l, DMNSN_ZMIN);
+  double rval = dmnsn_get_coordinate(r, DMNSN_ZMIN);
   return lval < rval;
 }
 
 static bool
-dmnsn_zmin_prnode_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
+dmnsn_xmax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
 {
-  double lval = dmnsn_priority_get(l, false, DMNSN_ZMIN);
-  double rval = dmnsn_priority_get(r, false, DMNSN_ZMIN);
+  double lval = dmnsn_get_coordinate(l, DMNSN_XMAX);
+  double rval = dmnsn_get_coordinate(r, DMNSN_XMAX);
   return lval < rval;
 }
 
 static bool
-dmnsn_xmax_object_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
+dmnsn_ymax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
 {
-  double lval = dmnsn_priority_get(l, true, DMNSN_XMAX);
-  double rval = dmnsn_priority_get(r, true, DMNSN_XMAX);
+  double lval = dmnsn_get_coordinate(l, DMNSN_YMAX);
+  double rval = dmnsn_get_coordinate(r, DMNSN_YMAX);
   return lval < rval;
 }
 
 static bool
-dmnsn_xmax_prnode_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
+dmnsn_zmax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
 {
-  double lval = dmnsn_priority_get(l, false, DMNSN_XMAX);
-  double rval = dmnsn_priority_get(r, false, DMNSN_XMAX);
+  double lval = dmnsn_get_coordinate(l, DMNSN_ZMAX);
+  double rval = dmnsn_get_coordinate(r, DMNSN_ZMAX);
   return lval < rval;
 }
 
-static bool
-dmnsn_ymax_object_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
-{
-  double lval = dmnsn_priority_get(l, true, DMNSN_YMAX);
-  double rval = dmnsn_priority_get(r, true, DMNSN_YMAX);
-  return lval < rval;
-}
-
-static bool
-dmnsn_ymax_prnode_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
-{
-  double lval = dmnsn_priority_get(l, false, DMNSN_YMAX);
-  double rval = dmnsn_priority_get(r, false, DMNSN_YMAX);
-  return lval < rval;
-}
-
-static bool
-dmnsn_zmax_object_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
-{
-  double lval = dmnsn_priority_get(l, true, DMNSN_ZMAX);
-  double rval = dmnsn_priority_get(r, true, DMNSN_ZMAX);
-  return lval < rval;
-}
-
-static bool
-dmnsn_zmax_prnode_comp(const dmnsn_list_iterator *l,
-                       const dmnsn_list_iterator *r)
-{
-  double lval = dmnsn_priority_get(l, false, DMNSN_ZMAX);
-  double rval = dmnsn_priority_get(r, false, DMNSN_ZMAX);
-  return lval < rval;
-}
-
-/** Leaf node comparators. */
-static dmnsn_list_comparator_fn *dmnsn_object_comparators[6] = {
-  [DMNSN_XMIN] = dmnsn_xmin_object_comp,
-  [DMNSN_YMIN] = dmnsn_ymin_object_comp,
-  [DMNSN_ZMIN] = dmnsn_zmin_object_comp,
-  [DMNSN_XMAX] = dmnsn_xmax_object_comp,
-  [DMNSN_YMAX] = dmnsn_ymax_object_comp,
-  [DMNSN_ZMAX] = dmnsn_zmax_object_comp
-};
-
-/** Internal node comparators. */
-static dmnsn_list_comparator_fn *dmnsn_prnode_comparators[6] = {
-  [DMNSN_XMIN] = dmnsn_xmin_prnode_comp,
-  [DMNSN_YMIN] = dmnsn_ymin_prnode_comp,
-  [DMNSN_ZMIN] = dmnsn_zmin_prnode_comp,
-  [DMNSN_XMAX] = dmnsn_xmax_prnode_comp,
-  [DMNSN_YMAX] = dmnsn_ymax_prnode_comp,
-  [DMNSN_ZMAX] = dmnsn_zmax_prnode_comp
+/** All comparators. */
+static dmnsn_list_comparator_fn *const dmnsn_comparators[DMNSN_PSEUDO_B] = {
+  [DMNSN_XMIN] = dmnsn_xmin_comp,
+  [DMNSN_YMIN] = dmnsn_ymin_comp,
+  [DMNSN_ZMIN] = dmnsn_zmin_comp,
+  [DMNSN_XMAX] = dmnsn_xmax_comp,
+  [DMNSN_YMAX] = dmnsn_ymax_comp,
+  [DMNSN_ZMAX] = dmnsn_zmax_comp
 };
 
-/** Select an extreme node based on a comparator. */
-static dmnsn_list_iterator *
-dmnsn_priority_search(dmnsn_list *leaves, bool are_objects, int comparator)
-{
-  dmnsn_list_iterator *i = dmnsn_list_first(leaves);
-  if (i) {
-    double candidate = dmnsn_priority_get(i, are_objects, comparator);
-
-    for (dmnsn_list_iterator *j = dmnsn_list_next(i);
-         j != NULL;
-         j = dmnsn_list_next(j))
-    {
-      double new_candidate = dmnsn_priority_get(j, are_objects, comparator);
-      if (new_candidate < candidate) {
-        candidate = new_candidate;
-        i = j;
+/** Add the priority leaves for this level. */
+static void
+dmnsn_add_priority_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
+                          dmnsn_list *new_leaves, int comparator)
+{
+  for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
+    dmnsn_prnode *leaf = dmnsn_new_prnode();
+    size_t count = 0;
+    dmnsn_list_iterator *j = dmnsn_list_first(sorted_leaves[i]);
+    while (count < DMNSN_PRTREE_B && j) {
+      /* Skip all the previously found extreme nodes */
+      dmnsn_prnode **node;
+      do {
+        node = dmnsn_list_at(j);
+        j = dmnsn_list_next(j);
+      } while ((*node)->location == DMNSN_PRTREE_LEAF && j);
+
+      if ((*node)->location != DMNSN_PRTREE_LEAF) {
+        (*node)->location = DMNSN_PRTREE_LEAF;
+        leaf->children[count++] = *node;
+        dmnsn_prnode_swallow(leaf, (*node)->bounding_box);
       }
     }
-  }
 
-  return i;
-}
-
-/** Build a pseudo PR-tree. */
-static dmnsn_pseudo_prtree *
-dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator)
-{
-  dmnsn_pseudo_prtree *pseudo = dmnsn_malloc(sizeof(dmnsn_pseudo_prtree));
-
-  if (dmnsn_list_size(leaves) <= DMNSN_PRTREE_B) {
-    /* Make a leaf */
-    pseudo->is_leaf = true;
-    pseudo->pseudo.leaf.bounding_box = dmnsn_zero_bounding_box();
-
-    size_t i;
-    dmnsn_list_iterator *ii;
-    if (are_objects) {
-      pseudo->pseudo.leaf.is_leaf = true;
-      for (i = 0, ii = dmnsn_list_first(leaves);
-           ii != NULL;
-           ++i, ii = dmnsn_list_next(ii))
-      {
-        dmnsn_object *object;
-        dmnsn_list_get(ii, &object);
-
-        pseudo->pseudo.leaf.children[i] = object;
-        dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.leaf, object->bounding_box);
-      }
+    if (count > 0) {
+      dmnsn_list_push(new_leaves, &leaf);
     } else {
-      pseudo->pseudo.leaf.is_leaf = false;
-      for (i = 0, ii = dmnsn_list_first(leaves);
-           ii != NULL;
-           ++i, ii = dmnsn_list_next(ii))
-      {
-        dmnsn_prtree_node *prnode;
-        dmnsn_list_get(ii, &prnode);
-
-        pseudo->pseudo.leaf.children[i] = prnode;
-        dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.leaf, prnode->bounding_box);
-      }
+      dmnsn_delete_prnode(leaf);
+      return;
     }
+  }
+}
 
-    for (; i < DMNSN_PRTREE_B; ++i) {
-      pseudo->pseudo.leaf.children[i] = NULL;
-    }
-  } else {
-    /* Make an internal node */
-    pseudo->is_leaf = false;
-    for (size_t i = 0; i < DMNSN_PSEUDO_PRTREE_B; ++i) {
-      pseudo->pseudo.node.children[i].is_leaf = are_objects;
-      pseudo->pseudo.node.children[i].bounding_box = dmnsn_zero_bounding_box();
+/** Split the sorted lists into the left and right subtrees. */
+static bool
+dmnsn_split_sorted_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
+                          dmnsn_list *right_sorted_leaves[DMNSN_PSEUDO_B],
+                          size_t i)
+{
+  /* Get rid of the extreme nodes */
+  dmnsn_list_iterator *j = dmnsn_list_first(sorted_leaves[i]);
+  while (j) {
+    dmnsn_list_iterator *next = dmnsn_list_next(j);
+    dmnsn_prnode **node = dmnsn_list_at(j);
+    if ((*node)->location == DMNSN_PRTREE_LEAF) {
+      dmnsn_list_remove(sorted_leaves[i], j);
     }
+    j = next;
+  }
 
-    /* Fill the priority leaves */
-    size_t i, j;
-    for (i = 0; i < DMNSN_PSEUDO_PRTREE_B; ++i) {
-      for (j = 0; j < DMNSN_PRTREE_B; ++j) {
-        dmnsn_list_iterator *k = dmnsn_priority_search(leaves, are_objects, i);
-        if (!k)
-          break;
-
-        if (are_objects) {
-          dmnsn_object *object;
-          dmnsn_list_get(k, &object);
-          pseudo->pseudo.node.children[i].children[j] = object;
-          dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.node.children[i],
-                                      object->bounding_box);
-        } else {
-          dmnsn_prtree_node *prnode;
-          dmnsn_list_get(k, &prnode);
-          pseudo->pseudo.node.children[i].children[j] = prnode;
-          dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.node.children[i],
-                                      prnode->bounding_box);
-        }
-
-        dmnsn_list_remove(leaves, k);
-      }
+  if (dmnsn_list_size(sorted_leaves[i]) == 0) {
+    return false;
+  }
 
-      if (dmnsn_list_size(leaves) == 0)
-        break;
-    }
+  /* Split the appropriate list and mark the left and right child nodes */
+  right_sorted_leaves[i] = dmnsn_list_split(sorted_leaves[i]);
+  for (dmnsn_list_iterator *j = dmnsn_list_first(sorted_leaves[i]);
+       j != NULL;
+       j = dmnsn_list_next(j))
+  {
+    dmnsn_prnode **node = dmnsn_list_at(j);
+    (*node)->location = DMNSN_PRTREE_LEFT;
+  }
+  for (dmnsn_list_iterator *j = dmnsn_list_first(right_sorted_leaves[i]);
+       j != NULL;
+       j = dmnsn_list_next(j))
+  {
+    dmnsn_prnode **node = dmnsn_list_at(j);
+    (*node)->location = DMNSN_PRTREE_RIGHT;
+  }
 
-    /* Set remaining space in the priority leaves to NULL */
-    for (; i < DMNSN_PSEUDO_PRTREE_B; ++i) {
-      for (; j < DMNSN_PRTREE_B; ++j) {
-        pseudo->pseudo.node.children[i].children[j] = NULL;
+  /* Split the rest of the lists */
+  for (size_t j = 0; j < DMNSN_PSEUDO_B; ++j) {
+    if (j != i) {
+      right_sorted_leaves[j] = dmnsn_new_list(sizeof(dmnsn_prnode *));
+
+      dmnsn_list_iterator *k = dmnsn_list_first(sorted_leaves[j]);
+      while (k) {
+        dmnsn_list_iterator *next = dmnsn_list_next(k);
+        dmnsn_prnode **node = dmnsn_list_at(k);
+        if ((*node)->location == DMNSN_PRTREE_LEAF) {
+          dmnsn_list_remove(sorted_leaves[j], k);
+        } else if ((*node)->location == DMNSN_PRTREE_RIGHT) {
+          dmnsn_list_iterator_remove(sorted_leaves[j], k);
+          dmnsn_list_iterator_insert(right_sorted_leaves[j], NULL, k);
+        }
+        k = next;
       }
-      j = 0;
     }
-
-    /* Recursively build the subtrees */
-    if (are_objects)
-      dmnsn_list_sort(leaves, dmnsn_object_comparators[comparator]);
-    else
-      dmnsn_list_sort(leaves, dmnsn_prnode_comparators[comparator]);
-
-    dmnsn_list *half = dmnsn_list_split(leaves);
-    pseudo->pseudo.node.left
-      = dmnsn_new_pseudo_prtree(leaves, are_objects, (comparator + 1)%6);
-    pseudo->pseudo.node.right
-      = dmnsn_new_pseudo_prtree(half, are_objects, (comparator + 1)%6);
-    dmnsn_delete_list(half);
   }
 
-  return pseudo;
+  return true;
 }
 
-/** Delete a pseudo-PR-tree. */
+/** Recursively constructs an implicit pseudo-PR-tree and collects the priority
+    leaves. */
 static void
-dmnsn_delete_pseudo_prtree(dmnsn_pseudo_prtree *pseudo)
+dmnsn_priority_leaves_recursive(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
+                                dmnsn_list *new_leaves,
+                                int comparator)
 {
-  if (pseudo) {
-    if (!pseudo->is_leaf) {
-      dmnsn_delete_pseudo_prtree(pseudo->pseudo.node.left);
-      dmnsn_delete_pseudo_prtree(pseudo->pseudo.node.right);
+  dmnsn_add_priority_leaves(sorted_leaves, new_leaves, comparator);
+
+  dmnsn_list *right_sorted_leaves[DMNSN_PSEUDO_B];
+  if (dmnsn_split_sorted_leaves(sorted_leaves, right_sorted_leaves, comparator))
+  {
+    dmnsn_priority_leaves_recursive(right_sorted_leaves, new_leaves,
+                                    (comparator + 1)%DMNSN_PSEUDO_B);
+    for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
+      dmnsn_delete_list(right_sorted_leaves[i]);
     }
-    dmnsn_free(pseudo);
+
+    dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves,
+                                    (comparator + 1)%DMNSN_PSEUDO_B);
   }
 }
 
-/** Construct a node from a pseudo leaf. */
-static dmnsn_prtree_node *
-dmnsn_new_prtree_node(const dmnsn_pseudo_prleaf *leaf)
+/** Constructs an implicit pseudo-PR-tree and returns the priority leaves. */
+static dmnsn_list *
+dmnsn_priority_leaves(const dmnsn_list *leaves)
 {
-  dmnsn_prtree_node *node = dmnsn_malloc(sizeof(dmnsn_prtree_node));
-  node->is_leaf      = leaf->is_leaf;
-  node->bounding_box = leaf->bounding_box;
-
-  for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
-    node->children[i] = leaf->children[i];
+  dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B];
+  for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
+    sorted_leaves[i] = dmnsn_copy_list(leaves);
+    dmnsn_list_sort(sorted_leaves[i], dmnsn_comparators[i]);
   }
 
-  return node;
-}
+  dmnsn_list *new_leaves = dmnsn_new_list(sizeof(dmnsn_prnode *));
+  dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves, 0);
 
-/** Free a PR-tree node. */
-static void
-dmnsn_delete_prtree_node(dmnsn_prtree_node *node)
-{
-  if (node) {
-    if (!node->is_leaf) {
-      for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
-        dmnsn_delete_prtree_node(node->children[i]);
-      }
-    }
-    dmnsn_free(node);
+  for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
+    dmnsn_delete_list(sorted_leaves[i]);
   }
-}
 
-/** Add a pseudo leaf to a list of leaves. */
-static void
-dmnsn_pseudo_prtree_add_leaf(const dmnsn_pseudo_prleaf *leaf,
-                             dmnsn_list *leaves)
-{
-  /* Don't add empty leaves */
-  if (leaf->children[0]) {
-    dmnsn_prtree_node *prnode = dmnsn_new_prtree_node(leaf);
-    dmnsn_list_push(leaves, &prnode);
-  }
+  return new_leaves;
 }
 
-/** Recursively extract the leaves of a pseudo-PR-tree. */
-static void
-dmnsn_pseudo_prtree_leaves_recursive(const dmnsn_pseudo_prtree *node,
-                                     dmnsn_list *leaves)
+/** Construct a non-flat PR-tree. */
+static dmnsn_prnode *
+dmnsn_make_prtree(const dmnsn_list *objects)
 {
-  if (node->is_leaf) {
-    dmnsn_pseudo_prtree_add_leaf(&node->pseudo.leaf, leaves);
-  } else {
-    for (size_t i = 0; i < DMNSN_PSEUDO_PRTREE_B; ++i) {
-      dmnsn_pseudo_prtree_add_leaf(&node->pseudo.node.children[i], leaves);
-    }
-    dmnsn_pseudo_prtree_leaves_recursive(node->pseudo.node.left, leaves);
-    dmnsn_pseudo_prtree_leaves_recursive(node->pseudo.node.right, leaves);
+  if (dmnsn_list_size(objects) == 0) {
+    return NULL;
   }
-}
 
-/** Extract the leaves of a pseudo PR-tree. */
-static dmnsn_list *
-dmnsn_pseudo_prtree_leaves(const dmnsn_pseudo_prtree *pseudo)
-{
-  dmnsn_list *leaves = dmnsn_new_list(sizeof(dmnsn_prtree_node *));
-  dmnsn_pseudo_prtree_leaves_recursive(pseudo, leaves);
+  /* Make the initial list of leaves */
+  dmnsn_list *leaves = dmnsn_new_list(sizeof(dmnsn_prnode *));
+  for (dmnsn_list_iterator *i = dmnsn_list_first(objects);
+       i != NULL;
+       i = dmnsn_list_next(i))
+  {
+    dmnsn_object **object = dmnsn_list_at(i);
+    dmnsn_prnode *node = dmnsn_new_prnode();
+    node->bounding_box = (*object)->bounding_box;
+    node->object       = *object;
+    dmnsn_list_push(leaves, &node);
+  }
 
-  if (dmnsn_list_size(leaves) == 0) {
-    dmnsn_prtree_node *prnode = dmnsn_new_prtree_node(&pseudo->pseudo.leaf);
-    dmnsn_list_push(leaves, &prnode);
+  while (dmnsn_list_size(leaves) > 1) {
+    dmnsn_list *new_leaves = dmnsn_priority_leaves(leaves);
+    dmnsn_delete_list(leaves);
+    leaves = new_leaves;
   }
 
-  return leaves;
+  dmnsn_prnode **leaf = dmnsn_list_at(dmnsn_list_first(leaves));
+  dmnsn_prnode *root = *leaf;
+  dmnsn_delete_list(leaves);
+  return root;
 }
 
 /** Add an object or its children, if any, to a list. */
@@ -500,10 +390,9 @@ dmnsn_split_unbounded(dmnsn_list *objects)
 
   dmnsn_list_iterator *i = dmnsn_list_first(objects);
   while (i) {
-    dmnsn_object *object;
-    dmnsn_list_get(i, &object);
+    dmnsn_object **object = dmnsn_list_at(i);
 
-    if (dmnsn_bounding_box_is_infinite(object->bounding_box)) {
+    if (dmnsn_bounding_box_is_infinite((*object)->bounding_box)) {
       dmnsn_list_iterator *next = dmnsn_list_next(i);
       dmnsn_list_iterator_remove(objects, i);
       dmnsn_list_iterator_insert(unbounded, NULL, i);
@@ -516,59 +405,19 @@ dmnsn_split_unbounded(dmnsn_list *objects)
   return unbounded;
 }
 
-/* Construct a non-flat PR-tree */
-static dmnsn_prtree_node *
-dmnsn_make_prtree(dmnsn_list *leaves)
-{
-  dmnsn_prtree_node *root = NULL;
-
-  if (dmnsn_list_size(leaves) > 0) {
-    dmnsn_pseudo_prtree *pseudo = dmnsn_new_pseudo_prtree(leaves, true, 0);
-    dmnsn_delete_list(leaves);
-    leaves = dmnsn_pseudo_prtree_leaves(pseudo);
-    dmnsn_delete_pseudo_prtree(pseudo);
-
-    while (dmnsn_list_size(leaves) > 1) {
-      pseudo = dmnsn_new_pseudo_prtree(leaves, false, 0);
-      dmnsn_delete_list(leaves);
-      leaves = dmnsn_pseudo_prtree_leaves(pseudo);
-      dmnsn_delete_pseudo_prtree(pseudo);
-    }
-
-    dmnsn_list_get(dmnsn_list_first(leaves), &root);
-  }
-
-  dmnsn_delete_list(leaves);
-  return root;
-}
-
 /** Recursively flatten a PR-tree into an array of flat nodes. */
 static void
-dmnsn_flatten_prtree_recursive(dmnsn_prtree_node *node, dmnsn_array *flat)
+dmnsn_flatten_prtree_recursive(dmnsn_prnode *node, dmnsn_array *flat)
 {
   size_t currenti = dmnsn_array_size(flat);
   dmnsn_array_resize(flat, currenti + 1);
   dmnsn_flat_prnode *flatnode = dmnsn_array_at(flat, currenti);
 
   flatnode->bounding_box = node->bounding_box;
-  flatnode->object       = NULL;
-
-  for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
-    if (!node->children[i])
-      break;
-
-    if (node->is_leaf) {
-      dmnsn_object *object = node->children[i];
+  flatnode->object       = node->object;
 
-      dmnsn_array_resize(flat, dmnsn_array_size(flat) + 1);
-      dmnsn_flat_prnode *objnode = dmnsn_array_last(flat);
-
-      objnode->bounding_box = object->bounding_box;
-      objnode->object       = object;
-      objnode->skip         = 1;
-    } else {
-      dmnsn_flatten_prtree_recursive(node->children[i], flat);
-    }
+  for (size_t i = 0; i < DMNSN_PRTREE_B && node->children[i]; ++i) {
+    dmnsn_flatten_prtree_recursive(node->children[i], flat);
   }
 
   /* Array could have been realloc()'d somewhere else above */
@@ -578,7 +427,7 @@ dmnsn_flatten_prtree_recursive(dmnsn_prtree_node *node, dmnsn_array *flat)
 
 /** Flatten a PR-tree into an array of flat nodes. */
 static dmnsn_array *
-dmnsn_flatten_prtree(dmnsn_prtree_node *root)
+dmnsn_flatten_prtree(dmnsn_prnode *root)
 {
   dmnsn_array *flat = dmnsn_new_array(sizeof(dmnsn_flat_prnode));
   if (root) {
@@ -596,15 +445,17 @@ dmnsn_new_prtree(const dmnsn_array *objects)
 {
   dmnsn_prtree *prtree = dmnsn_malloc(sizeof(dmnsn_prtree));
 
-  dmnsn_list *leaves = dmnsn_object_list(objects);
-  dmnsn_list *unbounded = dmnsn_split_unbounded(leaves);
+  dmnsn_list *object_list = dmnsn_object_list(objects);
 
+  dmnsn_list *unbounded = dmnsn_split_unbounded(object_list);
   prtree->unbounded = dmnsn_array_from_list(unbounded);
-  dmnsn_prtree_node *root = dmnsn_make_prtree(leaves);
+
+  dmnsn_prnode *root = dmnsn_make_prtree(object_list);
   prtree->bounded = dmnsn_flatten_prtree(root);
 
-  dmnsn_delete_prtree_node(root);
+  dmnsn_delete_prnode(root);
   dmnsn_delete_list(unbounded);
+  dmnsn_delete_list(object_list);
 
   if (dmnsn_array_size(prtree->unbounded) > 0) {
     prtree->bounding_box = dmnsn_infinite_bounding_box();
-- 
cgit v1.2.3