summaryrefslogtreecommitdiffstats
path: root/libdimension/prtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'libdimension/prtree.c')
-rw-r--r--libdimension/prtree.c248
1 files changed, 115 insertions, 133 deletions
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();