view release on metacpan or  search on metacpan

rtree/salad/rtree.h  view on Meta::CPAN

 *    copyright notice, this list of conditions and the following
 *    disclaimer in the documentation and/or other materials
 *    provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
 * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
 * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
#include <stddef.h>
#include <stdbool.h>
#include "small/matras.h"

#define RB_COMPACT 1
#include "small/rb.h"

/**
 * In-memory Guttman's R-tree
 */

/* Type of payload data */
typedef void *record_t;
/* Type of coordinate */
typedef double coord_t;
/* Type of square coordinate */
typedef double sq_coord_t;
/* Type of area (volume) of rectangle (box) */
typedef double area_t;

#if defined(__cplusplus)
extern "C" {
#endif /* defined(__cplusplus) */

struct rtree_neighbor {
	rb_node(struct rtree_neighbor) link;
	struct rtree_neighbor *next;
	void *child;
	int level;
	sq_coord_t distance;
};

typedef rb_tree(struct rtree_neighbor) rtnt_t;

enum {
	/** Maximal possible R-tree height */
	RTREE_MAX_HEIGHT = 16,
	/** Maximal possible R-tree height */
	RTREE_MAX_DIMENSION = 20
};

/**
 * Rtree search operations. Used for searching and iterations.
 * All operations except SOP_ALL reqires a rectangle to be set,
 * and treat it in different ways
 */
enum spatial_search_op
{
	/* Find and itearate all records */
	SOP_ALL,
	/* Find and itearate records with the same rectangle */
	SOP_EQUALS,
	/* Find and itearate records that contain given rectangle */
	SOP_CONTAINS,
	/* Find and itearate records that strictly contain given rectangle */
	SOP_STRICT_CONTAINS,
	/* Find and itearate records that overlaps with given rectangle */
	SOP_OVERLAPS,
	/* Find and itearate records that belongs to given rectangle */
	SOP_BELONGS,
	/* Find and itearate records that strictly belongs to given rectangle */
	SOP_STRICT_BELONGS,
	/* Find and itearate nearest records from a given point (the point is
	 * acluattly lowest_point of given rectangle). Records are iterated in
	 * order of distance to given point. Yes, it is KNN iterator */
	SOP_NEIGHBOR
};

/* pointers to page allocation and deallocations functions */
typedef void *(*rtree_extent_alloc_t)(void *ctx);
typedef void (*rtree_extent_free_t)(void *ctx, void *extent);

/* A box in RTREE_DIMENSION space */
struct rtree_rect
{
	/* coords: { low X, upper X, low Y, upper Y, etc } */
	coord_t coords[RTREE_MAX_DIMENSION * 2];
};

/* Type of function, comparing two rectangles */
typedef bool (*rtree_comparator_t)(const struct rtree_rect *rt1,
				   const struct rtree_rect *rt2,
				   unsigned dimension);

/* Type distance comparison */
enum rtree_distance_type {
	RTREE_EUCLID = 0, /* Euclid distance, sqrt(dx*dx + dy*dy) */
	RTREE_MANHATTAN = 1 /* Manhattan distance, fabs(dx) + fabs(dy) */
};

/* Main rtree struct */
struct rtree
{
	/* Root node (page) */
	struct rtree_page *root;
	/* R-tree dimension */
	unsigned dimension;
	/* Minimal number of branches in tree page */
	unsigned page_min_fill;
	/* Maximal number of branches in tree page */
	unsigned page_max_fill;
	/* Page size in bytes */
	unsigned page_size;