Use arrays for PR-tree construction instead of lists.

6 files changed, 169 insertions, 660 deletions

diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am
index 3622f08..4d4f58e 100644
--- a/libdimension/Makefile.am
+++ b/libdimension/Makefile.am
@@ -37,7 +37,6 @@ nobase_include_HEADERS = dimension.h                                           \
                          dimension/interior.h                                  \
                          dimension/light.h                                     \
                          dimension/lights.h                                    \
-                         dimension/list.h                                      \
                          dimension/malloc.h                                    \
                          dimension/map.h                                       \
                          dimension/object.h                                    \
@@ -80,7 +79,6 @@ libdimension_la_SOURCES = $(nobase_include_HEADERS)                            \
                           inline.c                                             \
                           interior.c                                           \
                           light.c                                              \
-                          list.c                                               \
                           malloc.c                                             \
                           map.c                                                \
                           object.c                                             \
diff --git a/libdimension/dimension.h b/libdimension/dimension.h
index bd055fc..3f0ea57 100644
--- a/libdimension/dimension.h
+++ b/libdimension/dimension.h
@@ -78,7 +78,6 @@ typedef void dmnsn_free_fn(void *ptr);
 #include <dimension/error.h>
 #include <dimension/malloc.h>
 #include <dimension/array.h>
-#include <dimension/list.h>
 #include <dimension/dictionary.h>
 #include <dimension/progress.h>
 #include <dimension/timer.h>
diff --git a/libdimension/dimension/array.h b/libdimension/dimension/array.h
index 51830e7..18affd7 100644
--- a/libdimension/dimension/array.h
+++ b/libdimension/dimension/array.h
@@ -27,7 +27,8 @@
 #define DIMENSION_ARRAY_H
 
 #include <stddef.h> /* For size_t */
-#include <string.h> /* For memcpy */
+#include <stdlib.h> /* For qsort() */
+#include <string.h> /* For memcpy() */
 
 /** Dynamic array type. */
 typedef struct dmnsn_array {
@@ -98,6 +99,38 @@ dmnsn_array_resize(dmnsn_array *array, size_t length)
 }
 
 /**
+ * Copy an array.
+ * @param[in] array  The array to copy.
+ * @return A copy of the array.
+ */
+DMNSN_INLINE dmnsn_array *
+dmnsn_array_copy(const dmnsn_array *array)
+{
+  dmnsn_array *copy = dmnsn_new_array(array->obj_size);
+  dmnsn_array_resize(copy, dmnsn_array_size(array));
+  memcpy(copy->ptr, array->ptr, dmnsn_array_size(array)*array->obj_size);
+  return copy;
+}
+
+/**
+ * Split an array in half.
+ * @param[in,out] array  The array to split.
+ * @return The second half of the array.
+ */
+DMNSN_INLINE dmnsn_array *
+dmnsn_array_split(dmnsn_array *array)
+{
+  dmnsn_array *half = dmnsn_new_array(array->obj_size);
+  size_t new_size = dmnsn_array_size(array)/2;
+  size_t old_size = dmnsn_array_size(array) - new_size;
+  dmnsn_array_resize(half, new_size);
+  memcpy(half->ptr, (char *)array->ptr + old_size*array->obj_size,
+         new_size*array->obj_size);
+  dmnsn_array_resize(array, old_size);
+  return half;
+}
+
+/**
  * Get the i'th element.
  * @param[in]  array  The array to access.
  * @param[in]  i      The index of the element to extract.
@@ -240,6 +273,26 @@ dmnsn_array_apply(dmnsn_array *array, dmnsn_callback_fn *callback)
   }
 }
 
+/**
+ * Callback type for array sorting.
+ * @param[in] a  The first element.
+ * @param[in] b  The second element.
+ * @return A negative value iff a < b, zero iff a == b, and a positive value iff
+ *         a > b.
+ */
+typedef int dmnsn_array_comparator_fn(const void *a, const void *b);
+
+/**
+ * Sort an array.
+ * @param[in,out] array       The array to sort.
+ * @param[in]     comparator  The sorting comparator to use.
+ */
+DMNSN_INLINE void
+dmnsn_array_sort(dmnsn_array *array, dmnsn_array_comparator_fn *comparator)
+{
+  qsort(array->ptr, dmnsn_array_size(array), array->obj_size, comparator);
+}
+
 /* Macros to shorten array iteration */
 
 /**
diff --git a/libdimension/dimension/list.h b/libdimension/dimension/list.h
deleted file mode 100644
index 70c944c..0000000
--- a/libdimension/dimension/list.h
+++ /dev/null
@@ -1,357 +0,0 @@
-/*************************************************************************
- * Copyright (C) 2010 Tavian Barnes <tavianator@tavianator.com>          *
- *                                                                       *
- * This file is part of The Dimension Library.                           *
- *                                                                       *
- * The Dimension Library is free software; you can redistribute it and/  *
- * or modify it under the terms of the GNU Lesser General Public License *
- * as published by the Free Software Foundation; either version 3 of the *
- * License, or (at your option) any later version.                       *
- *                                                                       *
- * The Dimension Library is distributed in the hope that it will be      *
- * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
- * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
- * Lesser General Public License for more details.                       *
- *                                                                       *
- * You should have received a copy of the GNU Lesser General Public      *
- * License along with this program.  If not, see                         *
- * <http://www.gnu.org/licenses/>.                                       *
- *************************************************************************/
-
-/**
- * @file
- * Simple doubly-linked lists.
- */
-
-#ifndef DIMENSION_LIST_H
-#define DIMENSION_LIST_H
-
-#include <stdbool.h>
-#include <stdlib.h>
-#include <string.h>
-
-/**
- * A list iterator.
- */
-typedef struct dmnsn_list_iterator {
-  void *ptr;                        /**< @internal The stored object. */
-  size_t obj_size;                  /**< @internal The object size. */
-  struct dmnsn_list_iterator *prev; /**< @internal The previous iterator. */
-  struct dmnsn_list_iterator *next; /**< @internal The next iterator. */
-} dmnsn_list_iterator;
-
-/**
- * @internal
- * Iterator allocation.
- * @param[in] obj       The location of the object to store in the iterator.
- * @param[in] obj_size  The size of the object to store in the iterator.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_new_list_iterator(const void *obj, size_t obj_size)
-{
-  dmnsn_list_iterator *i
-    = (dmnsn_list_iterator *)dmnsn_malloc(sizeof(dmnsn_list_iterator));
-  i->obj_size = obj_size;
-  i->prev = NULL;
-  i->next = NULL;
-  i->ptr  = dmnsn_malloc(obj_size);
-  memcpy(i->ptr, obj, obj_size);
-  return i;
-}
-
-/**
- * @internal
- * Iterator release.
- * @param[in,out] i  The iterator to free.
- */
-DMNSN_INLINE void
-dmnsn_delete_list_iterator(dmnsn_list_iterator *i)
-{
-  if (i) {
-    dmnsn_free(i->ptr);
-    dmnsn_free(i);
-  }
-}
-
-/** A doubly-linked list. */
-typedef struct dmnsn_list {
-  dmnsn_list_iterator *first; /**< @internal The first iterator in the list. */
-  dmnsn_list_iterator *last;  /**< @internal The last iterator in the list. */
-  size_t length;              /**< @internal The size of the list. */
-  size_t obj_size;            /**< @internal The size of list objects. */
-} dmnsn_list;
-
-/**
- * Allocate a list.
- * @param[in] obj_size  The size of the objects to be stored.
- * @return An empty list.
- */
-DMNSN_INLINE dmnsn_list *
-dmnsn_new_list(size_t obj_size)
-{
-  dmnsn_list *list = (dmnsn_list *)dmnsn_malloc(sizeof(dmnsn_list));
-  list->first    = NULL;
-  list->last     = NULL;
-  list->obj_size = obj_size;
-  list->length   = 0;
-  return list;
-}
-
-/**
- * Delete a list.
- * @param[in,out] list  The list to delete.
- */
-void dmnsn_delete_list(dmnsn_list *list);
-
-/**
- * Copy a list.
- * @param[in] list  The list to copy.
- * @return A list containing the same elements as \p list.
- */
-dmnsn_list *dmnsn_copy_list(const dmnsn_list *list);
-
-/**
- * Construct a list from an array.
- * @param[in] array  The array to copy.
- * @return A list with the same contents as \p array.
- */
-dmnsn_list *dmnsn_list_from_array(const dmnsn_array *array);
-
-/**
- * Construct an array from a list.
- * @param[in] list  The list to copy.
- * @return An array with the same contents as \p list.
- */
-dmnsn_array *dmnsn_array_from_list(const dmnsn_list *list);
-
-/**
- * First element.
- * @param[in] list  The list to index.
- * @return An iterator to the first list element, or NULL if the list is empty.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_list_first(const dmnsn_list *list)
-{
-  return list->first;
-}
-
-/**
- * Last element.
- * @param[in] list  The list to index.
- * @return An iterator to the last list element, or NULL if the list is empty.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_list_last(const dmnsn_list *list)
-{
-  return list->last;
-}
-
-/**
- * Previous element.
- * @param[in] i  The iterator to follow.
- * @return The iterator preceding \c i.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_list_prev(const dmnsn_list_iterator *i)
-{
-  dmnsn_assert(i, "NULL list iterator.");
-  return i->prev;
-}
-
-/**
- * Next element.
- * @param[in] i  The iterator to follow.
- * @return The iterator following \c i.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_list_next(const dmnsn_list_iterator *i)
-{
-  dmnsn_assert(i, "NULL list iterator.");
-  return i->next;
-}
-
-/**
- * Get the size of the list.
- * @param[in] list  The list in question.
- * @return The number of elements in the list.
- */
-DMNSN_INLINE size_t
-dmnsn_list_size(const dmnsn_list *list)
-{
-  return list->length;
-}
-
-/**
- * Get the i'th object.
- * @param[in]  i   The iterator to dereference.
- * @param[out] obj The location to store the object.
- */
-DMNSN_INLINE void
-dmnsn_list_get(const dmnsn_list_iterator *i, void *obj)
-{
-  dmnsn_assert(i, "NULL list iterator.");
-  memcpy(obj, i->ptr, i->obj_size);
-}
-
-/**
- * Get a pointer to the i'th object.
- * @param[in] i  The iterator to dereference.
- * @return A pointer to the object stored at \c i.
- */
-DMNSN_INLINE void *
-dmnsn_list_at(const dmnsn_list_iterator *i)
-{
-  dmnsn_assert(i, "NULL list iterator.");
-  return i->ptr;
-}
-
-/**
- * Set the i'th object.
- * @param[in,out] i    The iterator to dereference.
- * @param[in]     obj  The object to store at \c i.
- */
-DMNSN_INLINE void
-dmnsn_list_set(dmnsn_list_iterator *i, const void *obj)
-{
-  dmnsn_assert(i, "NULL list iterator.");
-  memcpy(i->ptr, obj, i->obj_size);
-}
-
-/**
- * Swap the objects in two iterators.
- * @param[in,out] a  The first iterator.
- * @param[in,out] b  The second iterator.
- */
-DMNSN_INLINE void
-dmnsn_list_swap(dmnsn_list_iterator *a, dmnsn_list_iterator *b)
-{
-  void *temp = a->ptr;
-  a->ptr = b->ptr;
-  b->ptr = temp;
-}
-
-/**
- * Insert a detached iterator into a list.
- * @param[in,out] list  The list to insert into.
- * @param[in,out] i     The iterator before which to insert, or NULL for the end
- *                      of the list.
- * @param[in,out] j     The detached iterator to insert.
- */
-DMNSN_INLINE void
-dmnsn_list_iterator_insert(dmnsn_list *list,
-                           dmnsn_list_iterator *i, dmnsn_list_iterator *j)
-{
-  if (list->first == i)
-    list->first = j;
-
-  if (i) {
-    j->prev = i->prev;
-    i->prev = j;
-  } else {
-    j->prev = list->last;
-    list->last = j;
-  }
-
-  if (j->prev)
-    j->prev->next = j;
-  j->next = i;
-  ++list->length;
-}
-
-/**
- * Insert an object.
- * @param[in,out] list  The list to insert into.
- * @param[in,out] i     The iterator before which to insert, or NULL for the end
- *                      of the list.
- * @param[in]     obj   The location of the object to insert.
- */
-DMNSN_INLINE void
-dmnsn_list_insert(dmnsn_list *list, dmnsn_list_iterator *i, const void *obj)
-{
-  dmnsn_list_iterator *j = dmnsn_new_list_iterator(obj, list->obj_size);
-  dmnsn_list_iterator_insert(list, i, j);
-}
-
-/**
- * Detach an iterator from a list.
- * @param[in,out] list  The list to remove from.
- * @param[in,out] i     The iterator to detach.
- */
-DMNSN_INLINE void
-dmnsn_list_iterator_remove(dmnsn_list *list, dmnsn_list_iterator *i)
-{
-  dmnsn_assert(i, "NULL list iterator.");
-  dmnsn_assert(list->first, "List is empty.");
-  if (list->first == i)
-    list->first = i->next;
-  if (list->last == i)
-    list->last = i->prev;
-  if (i->prev)
-    i->prev->next = i->next;
-  if (i->next)
-    i->next->prev = i->prev;
-  i->prev = NULL;
-  i->next = NULL;
-  --list->length;
-}
-
-/**
- * Remove the specified item from a list.
- * @param[in,out] list  The list to remove from.
- * @param[in,out] i     The iterator to delete.
- */
-DMNSN_INLINE void
-dmnsn_list_remove(dmnsn_list *list, dmnsn_list_iterator *i)
-{
-  dmnsn_list_iterator_remove(list, i);
-  dmnsn_delete_list_iterator(i);
-}
-
-/**
- * Push an object to the end of the list.
- * @param[in,out] list  The list to append to.
- * @param[in]     obj   The location of the object to push.
- */
-DMNSN_INLINE void
-dmnsn_list_push(dmnsn_list *list, const void *obj)
-{
-  dmnsn_list_insert(list, NULL, obj);
-}
-
-/**
- * Pop an object from the end of the list.
- * @param[in,out] list  The list to extract from.
- * @param[out]    obj   The location to store the extracted object.
- */
-DMNSN_INLINE void
-dmnsn_list_pop(dmnsn_list *list, void *obj)
-{
-  dmnsn_assert(list->last, "List is empty.");
-  dmnsn_list_get(list->last, obj);
-  dmnsn_list_remove(list, list->last);
-}
-
-/**
- * Split a list in half, and return the second half.
- * @param[in,out] list  The list to split.
- * @return A the second half of the list.
- */
-dmnsn_list *dmnsn_list_split(dmnsn_list *list);
-
-/**
- * List object comparator function type.
- * @param[in] l  The first iterator.
- * @param[in] r  The second iterator.
- * @return Whether \p l < \p r.
- */
-typedef bool dmnsn_list_comparator_fn(const dmnsn_list_iterator *l,
-                                      const dmnsn_list_iterator *r);
-
-/**
- * Sort a list, with O(n*log(n)) comparisons.
- * @param[in,out] list       The list to sort.
- * @param[in]     comparator The comparator to use for comparisons.
- */
-void dmnsn_list_sort(dmnsn_list *list, dmnsn_list_comparator_fn *comparator);
-
-#endif /* DIMENSION_LIST_H */
diff --git a/libdimension/list.c b/libdimension/list.c
deleted file mode 100644
index a44e8f0..0000000
--- a/libdimension/list.c
+++ /dev/null
@@ -1,166 +0,0 @@
-/*************************************************************************
- * Copyright (C) 2010-2011 Tavian Barnes <tavianator@tavianator.com>     *
- *                                                                       *
- * This file is part of The Dimension Library.                           *
- *                                                                       *
- * The Dimension Library is free software; you can redistribute it and/  *
- * or modify it under the terms of the GNU Lesser General Public License *
- * as published by the Free Software Foundation; either version 3 of the *
- * License, or (at your option) any later version.                       *
- *                                                                       *
- * The Dimension Library is distributed in the hope that it will be      *
- * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
- * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
- * Lesser General Public License for more details.                       *
- *                                                                       *
- * You should have received a copy of the GNU Lesser General Public      *
- * License along with this program.  If not, see                         *
- * <http://www.gnu.org/licenses/>.                                       *
- *************************************************************************/
-
-/**
- * @file
- * Doubly-linked lists.
- */
-
-#include "dimension.h"
-
-dmnsn_list *
-dmnsn_copy_list(const dmnsn_list *list)
-{
-  dmnsn_list *copy = dmnsn_new_list(list->obj_size);
-
-  for (dmnsn_list_iterator *i = dmnsn_list_first(list);
-       i != NULL;
-       i = dmnsn_list_next(i))
-  {
-    dmnsn_list_push(copy, dmnsn_list_at(i));
-  }
-
-  return copy;
-}
-
-dmnsn_list *
-dmnsn_list_from_array(const dmnsn_array *array)
-{
-  dmnsn_list *list = dmnsn_new_list(array->obj_size);
-
-  for (size_t i = 0; i < dmnsn_array_size(array); ++i) {
-    dmnsn_list_push(list, dmnsn_array_at(array, i));
-  }
-
-  return list;
-}
-
-dmnsn_array *
-dmnsn_array_from_list(const dmnsn_list *list)
-{
-  dmnsn_array *array = dmnsn_new_array(list->obj_size);
-
-  for (dmnsn_list_iterator *i = dmnsn_list_first(list);
-       i != NULL;
-       i = dmnsn_list_next(i))
-  {
-    dmnsn_array_push(array, dmnsn_list_at(i));
-  }
-
-  return array;
-}
-
-void
-dmnsn_delete_list(dmnsn_list *list)
-{
-  if (list) {
-    while (dmnsn_list_first(list)) {
-      dmnsn_list_remove(list, dmnsn_list_first(list));
-    }
-    dmnsn_free(list);
-  }
-}
-
-/** Split the second half of a list into a new list. */
-static void
-dmnsn_list_split_impl(dmnsn_list *list, dmnsn_list *half)
-{
-  /* Find the halfway point */
-  size_t i, max = dmnsn_list_size(list)/2;
-  dmnsn_list_iterator *ii;
-  for (i = 0, ii = dmnsn_list_last(list);
-       i < max && ii;
-       ++i, ii = dmnsn_list_prev(ii));
-
-  if (ii && ii->next) {
-    half->first = ii->next;
-    half->last = list->last;
-    list->last = ii;
-    half->first->prev = NULL;
-    list->last->next  = NULL;
-  }
-
-  list->length -= max;
-  half->length = max;
-}
-
-dmnsn_list *
-dmnsn_list_split(dmnsn_list *list)
-{
-  dmnsn_list *half = dmnsn_new_list(list->obj_size);
-  dmnsn_list_split_impl(list, half);
-  return half;
-}
-
-void
-dmnsn_list_sort(dmnsn_list *list, dmnsn_list_comparator_fn *comparator)
-{
-  if (dmnsn_list_size(list) < 2) {
-    return;
-  } else if (dmnsn_list_size(list) <= 16) {
-    /* Use insertion sort on small lists */
-    dmnsn_list_iterator *current = dmnsn_list_next(dmnsn_list_first(list));
-    do {
-      dmnsn_list_iterator *next = dmnsn_list_next(current);
-      dmnsn_list_iterator_remove(list, current);
-
-      dmnsn_list_iterator *i = next;
-      do {
-        dmnsn_list_iterator *prev = i ? dmnsn_list_prev(i)
-                                      : dmnsn_list_last(list);
-        if (!comparator(current, prev))
-          break;
-        i = prev;
-      } while (i != dmnsn_list_first(list));
-      dmnsn_list_iterator_insert(list, i, current);
-
-      current = next;
-    } while (current);
-  } else {
-    /* Recursive merge sort */
-    dmnsn_list half;
-    dmnsn_list_split_impl(list, &half);
-    dmnsn_list_sort(list, comparator);
-    dmnsn_list_sort(&half, comparator);
-
-    dmnsn_list_iterator *i = dmnsn_list_first(list);
-    dmnsn_list_iterator *j = dmnsn_list_first(&half);
-    while (i || j) {
-      if (!i) {
-        j->prev = dmnsn_list_last(list);
-        list->last->next = j;
-        list->last = half.last;
-        list->length += half.length;
-        half.first = half.last = NULL;
-        half.length = 0;
-        break;
-      } else if (!j) {
-        break;
-      } else if (comparator(j, i)) {
-        dmnsn_list_iterator *temp = dmnsn_list_next(j);
-        dmnsn_list_iterator_remove(&half, j);
-        dmnsn_list_iterator_insert(list, i, j);
-        j = temp;
-      } else {
-        i = dmnsn_list_next(i);
-      }
-    }
-  }
-}
diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index fc15860..7551fc8 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -103,10 +103,8 @@ enum {
 
 /** Get a coordinate of the bounding box of a node. */
 static inline double
-dmnsn_get_coordinate(const dmnsn_list_iterator *i, int comparator)
+dmnsn_get_coordinate(const dmnsn_prnode * const *node, int comparator)
 {
-  dmnsn_prnode **node = dmnsn_list_at(i);
-
   switch (comparator) {
   case DMNSN_XMIN:
     return (*node)->bounding_box.min.x;
@@ -130,56 +128,56 @@ dmnsn_get_coordinate(const dmnsn_list_iterator *i, int comparator)
 
 /* List sorting comparators */
 
-static bool
-dmnsn_xmin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_xmin_comp(const void *l, const void *r)
 {
   double lval = dmnsn_get_coordinate(l, DMNSN_XMIN);
   double rval = dmnsn_get_coordinate(r, DMNSN_XMIN);
-  return lval < rval;
+  return lval < rval ? -1 : 1;
 }
 
-static bool
-dmnsn_ymin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_ymin_comp(const void *l, const void *r)
 {
   double lval = dmnsn_get_coordinate(l, DMNSN_YMIN);
   double rval = dmnsn_get_coordinate(r, DMNSN_YMIN);
-  return lval < rval;
+  return lval < rval ? -1 : 1;
 }
 
-static bool
-dmnsn_zmin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_zmin_comp(const void *l, const void *r)
 {
   double lval = dmnsn_get_coordinate(l, DMNSN_ZMIN);
   double rval = dmnsn_get_coordinate(r, DMNSN_ZMIN);
-  return lval < rval;
+  return lval < rval ? -1 : 1;
 }
 
-static bool
-dmnsn_xmax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_xmax_comp(const void *l, const void *r)
 {
   double lval = dmnsn_get_coordinate(l, DMNSN_XMAX);
   double rval = dmnsn_get_coordinate(r, DMNSN_XMAX);
-  return lval < rval;
+  return lval < rval ? -1 : 1;
 }
 
-static bool
-dmnsn_ymax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_ymax_comp(const void *l, const void *r)
 {
   double lval = dmnsn_get_coordinate(l, DMNSN_YMAX);
   double rval = dmnsn_get_coordinate(r, DMNSN_YMAX);
-  return lval < rval;
+  return lval < rval ? -1 : 1;
 }
 
-static bool
-dmnsn_zmax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_zmax_comp(const void *l, const void *r)
 {
   double lval = dmnsn_get_coordinate(l, DMNSN_ZMAX);
   double rval = dmnsn_get_coordinate(r, DMNSN_ZMAX);
-  return lval < rval;
+  return lval < rval ? -1 : 1;
 }
 
 /** All comparators. */
-static dmnsn_list_comparator_fn *const dmnsn_comparators[DMNSN_PSEUDO_B] = {
+static dmnsn_array_comparator_fn *const dmnsn_comparators[DMNSN_PSEUDO_B] = {
   [DMNSN_XMIN] = dmnsn_xmin_comp,
   [DMNSN_YMIN] = dmnsn_ymin_comp,
   [DMNSN_ZMIN] = dmnsn_zmin_comp,
@@ -190,32 +188,32 @@ static dmnsn_list_comparator_fn *const dmnsn_comparators[DMNSN_PSEUDO_B] = {
 
 /** 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)
+dmnsn_add_priority_leaves(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
+                          dmnsn_array *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) {
+    dmnsn_prnode *leaf = NULL;
+    dmnsn_prnode **leaves = dmnsn_array_first(sorted_leaves[i]);
+    for (size_t j = 0, count = 0, size = dmnsn_array_size(sorted_leaves[i]);
+         j < size && 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);
+      if (leaves[j]->location == DMNSN_PRTREE_LEAF) {
+        continue;
       }
+
+      if (!leaf) {
+        leaf = dmnsn_new_prnode();
+      }
+      leaves[j]->location = DMNSN_PRTREE_LEAF;
+      leaf->children[count++] = leaves[j];
+      dmnsn_prnode_swallow(leaf, leaves[j]->bounding_box);
     }
 
-    if (count > 0) {
-      dmnsn_list_push(new_leaves, &leaf);
+    if (leaf) {
+      dmnsn_array_push(new_leaves, &leaf);
     } else {
-      dmnsn_delete_prnode(leaf);
       return;
     }
   }
@@ -223,59 +221,53 @@ dmnsn_add_priority_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
 
 /** 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],
+dmnsn_split_sorted_leaves(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
+                          dmnsn_array *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);
+  dmnsn_prnode **leaves = dmnsn_array_first(sorted_leaves[i]);
+  size_t j, skip;
+  for (j = 0, skip = 0; j < dmnsn_array_size(sorted_leaves[i]); ++j) {
+    if (leaves[j]->location == DMNSN_PRTREE_LEAF) {
+      ++skip;
+    } else {
+      leaves[j - skip] = leaves[j];
     }
-    j = next;
   }
+  dmnsn_array_resize(sorted_leaves[i], j - skip);
 
-  if (dmnsn_list_size(sorted_leaves[i]) == 0) {
+  if (dmnsn_array_size(sorted_leaves[i]) == 0) {
     return false;
   }
 
   /* 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);
+  right_sorted_leaves[i] = dmnsn_array_split(sorted_leaves[i]);
+  DMNSN_ARRAY_FOREACH (dmnsn_prnode **, node, sorted_leaves[i]) {
     (*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);
+  DMNSN_ARRAY_FOREACH (dmnsn_prnode **, node, right_sorted_leaves[i]) {
     (*node)->location = DMNSN_PRTREE_RIGHT;
   }
 
   /* 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);
+      right_sorted_leaves[j] = dmnsn_new_array(sizeof(dmnsn_prnode *));
+
+      dmnsn_prnode **leaves = dmnsn_array_first(sorted_leaves[j]);
+      size_t k, skip;
+      for (k = 0, skip = 0; k < dmnsn_array_size(sorted_leaves[j]); ++k) {
+        if (leaves[k]->location == DMNSN_PRTREE_LEAF) {
+          ++skip;
+        } else if (leaves[k]->location == DMNSN_PRTREE_RIGHT) {
+          dmnsn_array_push(right_sorted_leaves[j], &leaves[k]);
+          ++skip;
+        } else {
+          leaves[k - skip] = leaves[k];
         }
-        k = next;
       }
+      dmnsn_array_resize(sorted_leaves[j], k - skip);
     }
   }
 
@@ -285,19 +277,19 @@ dmnsn_split_sorted_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
 /** Recursively constructs an implicit pseudo-PR-tree and collects the priority
     leaves. */
 static void
-dmnsn_priority_leaves_recursive(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
-                                dmnsn_list *new_leaves,
+dmnsn_priority_leaves_recursive(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
+                                dmnsn_array *new_leaves,
                                 int comparator)
 {
   dmnsn_add_priority_leaves(sorted_leaves, new_leaves, comparator);
 
-  dmnsn_list *right_sorted_leaves[DMNSN_PSEUDO_B];
+  dmnsn_array *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_delete_array(right_sorted_leaves[i]);
     }
 
     dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves,
@@ -306,20 +298,20 @@ dmnsn_priority_leaves_recursive(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
 }
 
 /** Constructs an implicit pseudo-PR-tree and returns the priority leaves. */
-static dmnsn_list *
-dmnsn_priority_leaves(const dmnsn_list *leaves)
+static dmnsn_array *
+dmnsn_priority_leaves(const dmnsn_array *leaves)
 {
-  dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B];
+  dmnsn_array *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]);
+    sorted_leaves[i] = dmnsn_array_copy(leaves);
+    dmnsn_array_sort(sorted_leaves[i], dmnsn_comparators[i]);
   }
 
-  dmnsn_list *new_leaves = dmnsn_new_list(sizeof(dmnsn_prnode *));
+  dmnsn_array *new_leaves = dmnsn_new_array(sizeof(dmnsn_prnode *));
   dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves, 0);
 
   for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
-    dmnsn_delete_list(sorted_leaves[i]);
+    dmnsn_delete_array(sorted_leaves[i]);
   }
 
   return new_leaves;
@@ -327,80 +319,73 @@ dmnsn_priority_leaves(const dmnsn_list *leaves)
 
 /** Construct a non-flat PR-tree. */
 static dmnsn_prnode *
-dmnsn_make_prtree(const dmnsn_list *objects)
+dmnsn_make_prtree(const dmnsn_array *objects)
 {
-  if (dmnsn_list_size(objects) == 0) {
+  if (dmnsn_array_size(objects) == 0) {
     return NULL;
   }
 
-  /* 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);
+  /* Make the initial array of leaves */
+  dmnsn_array *leaves = dmnsn_new_array(sizeof(dmnsn_prnode *));
+  DMNSN_ARRAY_FOREACH (dmnsn_object **, object, objects) {
     dmnsn_prnode *node = dmnsn_new_prnode();
     node->bounding_box = (*object)->bounding_box;
     node->object       = *object;
-    dmnsn_list_push(leaves, &node);
+    dmnsn_array_push(leaves, &node);
   }
 
-  while (dmnsn_list_size(leaves) > 1) {
-    dmnsn_list *new_leaves = dmnsn_priority_leaves(leaves);
-    dmnsn_delete_list(leaves);
+  while (dmnsn_array_size(leaves) > 1) {
+    dmnsn_array *new_leaves = dmnsn_priority_leaves(leaves);
+    dmnsn_delete_array(leaves);
     leaves = new_leaves;
   }
 
-  dmnsn_prnode **leaf = dmnsn_list_at(dmnsn_list_first(leaves));
-  dmnsn_prnode *root = *leaf;
-  dmnsn_delete_list(leaves);
+  dmnsn_prnode *root = *(dmnsn_prnode **)dmnsn_array_first(leaves);
+  dmnsn_delete_array(leaves);
   return root;
 }
 
-/** Add an object or its children, if any, to a list. */
+/** Add an object or its children, if any, to an array. */
 static void
-dmnsn_list_add_object(dmnsn_list *objects, const dmnsn_object *object)
+dmnsn_split_add_object(dmnsn_array *objects, const dmnsn_object *object)
 {
   if (dmnsn_array_size(object->children) == 0) {
-    dmnsn_list_push(objects, &object);
+    dmnsn_array_push(objects, &object);
   } else {
     DMNSN_ARRAY_FOREACH (const dmnsn_object **, child, object->children) {
-      dmnsn_list_add_object(objects, *child);
+      dmnsn_split_add_object(objects, *child);
     }
   }
 }
 
-/** Add objects from an array to a list, splitting unions etc. */
-static dmnsn_list *
-dmnsn_object_list(const dmnsn_array *objects)
+/** Split unions to create the input for the PR-tree. */
+static dmnsn_array *
+dmnsn_split_objects(const dmnsn_array *objects)
 {
-  dmnsn_list *list = dmnsn_new_list(sizeof(dmnsn_object *));
+  dmnsn_array *split = dmnsn_new_array(sizeof(dmnsn_object *));
   DMNSN_ARRAY_FOREACH (const dmnsn_object **, object, objects) {
-    dmnsn_list_add_object(list, *object);
+    dmnsn_split_add_object(split, *object);
   }
-  return list;
+  return split;
 }
 
-/** Split unbounded objects into a new list. */
-static dmnsn_list *
-dmnsn_split_unbounded(dmnsn_list *objects)
+/** Split unbounded objects into a new array. */
+static dmnsn_array *
+dmnsn_split_unbounded(dmnsn_array *objects)
 {
-  dmnsn_list *unbounded = dmnsn_new_list(sizeof(dmnsn_object *));
-
-  dmnsn_list_iterator *i = dmnsn_list_first(objects);
-  while (i) {
-    dmnsn_object **object = dmnsn_list_at(i);
-
-    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);
-      i = next;
+  dmnsn_array *unbounded = dmnsn_new_array(sizeof(dmnsn_object *));
+
+  dmnsn_object **array = dmnsn_array_first(objects);
+  size_t i, skip;
+  for (i = 0, skip = 0; i < dmnsn_array_size(objects); ++i) {
+    if (dmnsn_bounding_box_is_infinite(array[i]->bounding_box)) {
+      dmnsn_array_push(unbounded, &array[i]);
+      ++skip;
     } else {
-      i = dmnsn_list_next(i);
+      array[i - skip] = array[i];
     }
   }
+  dmnsn_array_resize(objects, i - skip);
 
   return unbounded;
 }
@@ -445,17 +430,14 @@ dmnsn_new_prtree(const dmnsn_array *objects)
 {
   dmnsn_prtree *prtree = dmnsn_malloc(sizeof(dmnsn_prtree));
 
-  dmnsn_list *object_list = dmnsn_object_list(objects);
-
-  dmnsn_list *unbounded = dmnsn_split_unbounded(object_list);
-  prtree->unbounded = dmnsn_array_from_list(unbounded);
+  dmnsn_array *bounded = dmnsn_split_objects(objects);
+  prtree->unbounded = dmnsn_split_unbounded(bounded);
 
-  dmnsn_prnode *root = dmnsn_make_prtree(object_list);
+  dmnsn_prnode *root = dmnsn_make_prtree(bounded);
   prtree->bounded = dmnsn_flatten_prtree(root);
 
   dmnsn_delete_prnode(root);
-  dmnsn_delete_list(unbounded);
-  dmnsn_delete_list(object_list);
+  dmnsn_delete_array(bounded);
 
   if (dmnsn_array_size(prtree->unbounded) > 0) {
     prtree->bounding_box = dmnsn_infinite_bounding_box();