gist_rtree.cc

Libgist is an implementation of the Generalized Search Tree, a template index structure that makes i

// gist_rtree.cc						-*- c++ -*-
// Copyright (c) 1997, 1998 Regents of the University of California
// $Id: gist_rtree.cc,v 1.30 2000/03/15 00:24:51 mashah Exp $

#ifdef __GNUG__
#pragma implementation "gist_rtree.h"
#endif

#include <math.h>			// for fabs()

#include "gist_rtpred_point.h"
#include "gist_rtpred_rect.h"
#include "gist_rtree.h"
#include "gist_rtreecext.h"
#include "gist_support.h" // for print<>, parse<>, etc.

///////////////////////////////////////////////////////////////////////////////
// rt_query_t methods
///////////////////////////////////////////////////////////////////////////////

rt_query_t::~rt_query_t() 
{
    if (value != NULL) {
	if (argType == rt_pointarg) {
	    rt_point *pt =  (rt_point *) value;
	    delete pt;
	} else {
	    rt_rect *rect =  (rt_rect *) value;
	    delete rect;
	}
    }
}

///////////////////////////////////////////////////////////////////////////////
// static helper methods
///////////////////////////////////////////////////////////////////////////////

static bool
rect_equal_pt(const void *c1, int l, const rt_pred& p2)
{
    rt_rect r1(rt_rect::size2dim(l), (const double *) c1);
    return (((const rt_point&) p2).contains(r1));
}

static bool
rect_equal_rect(const void *c1, int l, const rt_pred& r2)
{
    rt_rect r1(rt_rect::size2dim(l), (const double *) c1);
    return (r1.isEqual((const rt_rect&) r2));
}

static double
pt_span(const rt_pred& pred)
{
    return(((const rt_point&) pred).span());
}

static double
rect_span(const rt_pred& pred)
{
    return(((const rt_rect&) pred).span());
}

static double
pt_margin(const rt_pred& pred)
{
    return(((const rt_point&) pred).margin());
}

static double
rect_margin(const rt_pred& pred)
{
    return(((const rt_rect&) pred).margin());
}

static rt_pred*
rect_pt_expand(rt_pred* pred, const void* item, int itemLen, bool preserve)
{
    assert(pred == NULL || pred->dim() == rt_point::size2dim(itemLen));
    rt_point p(rt_point::size2dim(itemLen), (const double *) item);
    return(pred ? ((rt_rect*) pred)->expand(p, preserve) : new rt_rect(p));
}

static rt_pred*
rect_rect_expand(rt_pred* pred, const void* item, int itemLen, bool preserve)
{
    assert(pred == NULL || pred->dim() == rt_rect::size2dim(itemLen));
    rt_rect r(rt_rect::size2dim(itemLen), (const double *) item);
    return(pred ? ((rt_rect*) pred)->expand(r, preserve) : new rt_rect(r));
}


// VCPORT_B
const float rtbase_ext_t::MINSPLITUTIL = 0.5;
// VCPORT_E

///////////////////////////////////////////////////////////////////////////////
// rt_ext_t function tables
///////////////////////////////////////////////////////////////////////////////

rtbase_ext_t::CmpFctTbl pointCmpTbl = {
    // nooper, equal, overlap, contains, contained, nearest, count_overlap
    {								// leaf
	{ &rt_pred::alwaysTrue,	// point key, point query
	  &rt_point::contains_point,
	  &rt_point::contains_point,
	  &rt_point::contains_point,
	  &rt_point::contains_point,
	  &rt_pred::alwaysTrue,
	  &rt_point::contains_point,
	  &rt_point::contains_point,
	  &rt_point::contains_point,
	},
	{ &rt_pred::alwaysTrue,	// point key, rect query
	  &rt_point::contains_rect,
	  &rt_point::contained_rect,
	  &rt_point::contains_rect,
	  &rt_point::contained_rect,
	  &rt_pred::alwaysTrue,
	  &rt_point::contained_rect,
	  &rt_point::contained_rect,
	  &rt_point::contained_rect,
	}
    },
    {								// internal
	{ &rt_pred::alwaysTrue, // rect key, point query
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rt_pred::alwaysTrue,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	},
	{ &rt_pred::alwaysTrue,	// rect key, rect query
	  &rt_rect::contains_rect,
	  &rt_rect::overlaps_rect,
	  &rt_rect::contains_rect,
	  &rt_rect::overlaps_rect,
	  &rt_pred::alwaysTrue,
	  &rt_rect::overlaps_rect,
	  &rt_rect::overlaps_rect,
	  &rt_rect::overlaps_rect,
	}
    }
};
rtbase_ext_t::ExpandFctTbl pointExpandTbl = {
    &rect_pt_expand,						// leaf
    &rect_rect_expand						// internal
};
rtbase_ext_t::PropFctTbl pointPropTbl = {
    { &pt_span, &pt_margin },					// leaf
    { &rect_span, &rect_margin }				// internal
};
rtbase_ext_t::BpCmpFctTbl pointBpCmpTbl = {
    &rect_equal_rect,
    &rt_rect::contains_point,					// leaf
    &rt_rect::contains_rect					// internal
};
rtbase_ext_t::ConvFctTbl pointConvTbl = {
    { &rt_point::size2dim, &rt_point::dim2size },		// leaf
    { &rt_rect::size2dim, &rt_rect::dim2size }			// internal
};
rtbase_ext_t::OpTbl pointOpTbl = {
    gist_cursorext_t::cext_stack_id,		// nooper
    gist_cursorext_t::cext_stack_id,		// equal
    gist_cursorext_t::cext_stack_id,		// overlap
    gist_cursorext_t::cext_stack_id,		// contains
    gist_cursorext_t::cext_stack_id,		// contained
    gist_cursorext_t::cext_rt_point_nn_id,	// nearest
    gist_cursorext_t::cext_stack_id,		// count_overlap
    gist_cursorext_t::cext_stack_id,		// count_sample
    gist_cursorext_t::cext_stack_id,		// count_combo
};

rt_ext_t point_ext(pointCmpTbl, pointExpandTbl,
    pointPropTbl, pointConvTbl, pointBpCmpTbl, pointOpTbl);
gist_unorderedn_ext_t rt_point_ext(gist_ext_t::rt_point_ext_id,
    "rt_point_ext", gist_support::printPtRtPred, gist_support::printInt,
    &gist_support::parsePoint, &gist_support::parseInt, gist_support::parseGeoQuery,
    point_ext);

rtbase_ext_t::CmpFctTbl rectCmpTbl = {
    // nooper, equal, overlap, contains, contained, nearest, count_overlap
    {								// leaf
	{ &rt_pred::alwaysTrue,	// rect key, point query
	  &rect_equal_pt,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rect_equal_pt,
	  &rt_pred::alwaysTrue,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	},
	{ &rt_pred::alwaysTrue,	// rect key, rect query
	  &rect_equal_rect,
	  &rt_rect::overlaps_rect,
	  &rt_rect::contains_rect,
	  &rt_rect::contained_rect,
	  &rt_pred::alwaysTrue,
	  &rt_rect::overlaps_rect,
	  &rt_rect::overlaps_rect,
	  &rt_rect::overlaps_rect,
	}
    },
    {								// internal
	{ &rt_pred::alwaysTrue,	// rect key, point query
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rt_pred::alwaysTrue,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	  &rt_rect::contains_point,
	},
	{ &rt_pred::alwaysTrue,	// rect key, rect query
	  &rt_rect::contains_rect,
	  &rt_rect::overlaps_rect,
	  &rt_rect::contains_rect,
	  &rt_rect::overlaps_rect,
	  &rt_pred::alwaysTrue,
	  &rt_rect::overlaps_rect,
	  &rt_rect::overlaps_rect,
	  &rt_rect::overlaps_rect,
	}
    }
};
rtbase_ext_t::ExpandFctTbl rectExpandTbl = {
    &rect_rect_expand,						// leaf
    &rect_rect_expand						// internal
};
rtbase_ext_t::PropFctTbl rectPropTbl = {
    { &rect_span, &rect_margin },				// leaf
    { &rect_span, &rect_margin }				// internal
};
rtbase_ext_t::ConvFctTbl rectConvTbl = {
    { &rt_rect::size2dim, &rt_rect::dim2size },			// leaf
    { &rt_rect::size2dim, &rt_rect::dim2size }			// internal
};
rtbase_ext_t::BpCmpFctTbl rectBpCmpTbl = {
    &rect_equal_rect,
    &rt_rect::contains_rect,					// leaf
    &rt_rect::contains_rect					// internal
};
rtbase_ext_t::OpTbl rectOpTbl = {
    gist_cursorext_t::cext_stack_id,		// nooper
    gist_cursorext_t::cext_stack_id,		// equal
    gist_cursorext_t::cext_stack_id,		// overlap
    gist_cursorext_t::cext_stack_id,		// contains
    gist_cursorext_t::cext_stack_id,		// contained
    gist_cursorext_t::cext_rt_rect_nn_id,	// nearest
    gist_cursorext_t::cext_stack_id,		// count_overlap
    gist_cursorext_t::cext_stack_id,		// count_sample
    gist_cursorext_t::cext_stack_id,		// count_combo
};

rt_ext_t rect_ext(rectCmpTbl, rectExpandTbl, 
    rectPropTbl, rectConvTbl, rectBpCmpTbl, rectOpTbl);
gist_unorderedn_ext_t rt_rect_ext(gist_ext_t::rt_rect_ext_id,
    "rt_rect_ext", gist_support::printRectRtPred, gist_support::printInt,
    &gist_support::parseRect, &gist_support::parseInt, gist_support::parseGeoQuery,
    rect_ext);

rtbase_nn_cursorext_t::RtPrioFctTbl rtPointNnPrioTbl = {
    { &rt_point::dist_point, NULL },				// leaf
    { &rt_rect::dist_point, NULL }				// internal
};
rtbase_nn_cursorext_t::RtPrioFctTbl rtRectNnPrioTbl = {
    { &rt_rect::dist_point, NULL },				// leaf
    { &rt_rect::dist_point, NULL }				// internal
};

rtbase_nn_cursorext_t rt_point_nn_cext(
    gist_cursorext_t::cext_rt_point_nn_id, rtPointNnPrioTbl);
rtbase_nn_cursorext_t rt_rect_nn_cext(
    gist_cursorext_t::cext_rt_rect_nn_id, rtRectNnPrioTbl);

///////////////////////////////////////////////////////////////////////////////
// rtbase_ext_t methods
///////////////////////////////////////////////////////////////////////////////

rtbase_ext_t::rtbase_ext_t(
    CmpFctTbl tbl,
    ExpandFctTbl exp,
    PropFctTbl pf,
    ConvFctTbl cf,
    BpCmpFctTbl bcf,
    OpTbl op)
{
    int i, j, k;

    // copy function tables
    for (i = 0; i < numLvl; i++) {
        for (j = 0; j < rt_query_t::rt_numarg; j++) {
	    for (k = 0; k < rt_query_t::rt_numoper; k++) {
	        cmpFcts[i][j][k] = tbl ? tbl[i][j][k] : NULL;
	    }
	}
	for (j = 0; j < rt_numprop; ++j) {
	    propFcts[i][j] = pf ? pf[i][j] : NULL;
	}
	for (j = 0; j < rt_numconv; ++j) {
	    convFcts[i][j] = cf ? cf[i][j] : NULL;
	}
	expandFcts[i] = exp ? exp[i] : NULL;
    }
    for (i = 0; i < rt_bpnumcmp; ++i) {
	bpCmpFcts[i] = bcf? bcf[i] : NULL;
    }
    for (i = 0; i < rt_query_t::rt_numoper; ++i) {
	opTbl[i] = op ? op[i] : gist_cursorext_t::cext_stack_id;
    }
}

bool
rtbase_ext_t::consistent(
    const gist_query_t* query,
    const void *pred,
    int predLen,
    int level) const
{
    rt_query_t *q = (rt_query_t *) query;
    rt_pred* sarg = (rt_pred*) q->value;