gist_sstree.cc

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

// gist_sstree.cc						-*- c++ -*-
// Copyright (c) 1998, Regents of the University of California
// $Id: gist_sstree.cc,v 1.6 1999/06/16 03:07:42 marcel Exp $

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

#include "gist_compat.h"		// for MAXDOUBLE
#include "gist_defs.h"			// for assert()
#include "gist_rtpred_rect.h"		// for rt_rect
#include "gist_rtpred_ss.h"
#include "gist_sstree.h"
#include "gist_ball.h"			// for EnclosingBall()
#include "gist_rtreecext.h"
#include "gist_support.h" // for print<>, parse<>, etc.

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

static double
ss_pt_dist(const void *item, int itemLen, const rt_pred& query)
{
    rt_centroid_sphere s(rt_centroid_sphere::size2dim(itemLen),
	(double *) item);
    return(s.dist((rt_point&) query));
}

static bool
ss_equal_ss(const void *c1, int l, const rt_pred& s2)
{
    rt_centroid_sphere s1(rt_centroid_sphere::size2dim(l), (const double *) c1);
    return (s1.isEqual((const rt_centroid_sphere&) s2));
}

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

static bool
ss_contains_rect(const void *c1, int l, const rt_pred& r2)
{
    rt_centroid_sphere s1(rt_centroid_sphere::size2dim(l), (const double *) c1);
    return (s1.contains((const rt_rect&) r2));
}

static bool
ss_contains_ss(const void *c1, int l, const rt_pred& s2)
{
    rt_centroid_sphere s1(rt_centroid_sphere::size2dim(l), (const double *) c1);
    return (s1.contains((const rt_centroid_sphere&) s2));
}

static bool
ss_overlaps_rect(const void *c1, int l, const rt_pred& r2)
{
    rt_centroid_sphere s1(rt_centroid_sphere::size2dim(l), (const double *) c1);
    return (s1.overlaps((const rt_rect&) r2));
}

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

static double
ss_span(const rt_pred& pred)
{
    return(((const rt_centroid_sphere&) pred).span());
}

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

static rt_pred*
pt_center(rt_pred* pred, const void* item, int itemLen)
{
    int d = rt_point::size2dim(itemLen);
    assert(pred == NULL || pred->dim() == d);
    double *c = (double*) item;					// XXX center
    if (pred == NULL) {
	return(new rt_point(d, c));
    }
    pred->set(c);
    return(pred);
}

static rt_pred*
ss_center(rt_pred* pred, const void* item, int itemLen)
{
    int d = rt_centroid_sphere::size2dim(itemLen);
    assert(pred == NULL || pred->dim() == d);
    double *c = (double*) item;					// XXX center
    if (pred == NULL) {
	return(new rt_point(d, c));
    }
    pred->set(c);
    return(pred);
}

static rt_pred*
ss_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_centroid_sphere*) pred)->expand(p, preserve)
	: new rt_centroid_sphere(p));
}

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

///////////////////////////////////////////////////////////////////////////////
// ss_ext_t function tables
///////////////////////////////////////////////////////////////////////////////

rtbase_ext_t::CmpFctTbl ssPointCmpTbl = {
    // 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,	// sphere key, point query
	  &ss_contains_pt,
	  &ss_contains_pt,
	  &ss_contains_pt,
	  &ss_contains_pt,
	  &rt_pred::alwaysTrue,
	  &ss_contains_pt,
	  &ss_contains_pt,
	  &ss_contains_pt,
	},
	{ &rt_pred::alwaysTrue,	// sphere key, rect query
	  &ss_contains_rect,
	  &ss_overlaps_rect,
	  &ss_contains_rect,
	  &ss_overlaps_rect,
	  &rt_pred::alwaysTrue,
	  &ss_overlaps_rect,
	  &ss_overlaps_rect,
	  &ss_overlaps_rect,
	}
    }
};
rtbase_ext_t::ExpandFctTbl ssPointExpandTbl = {
    &ss_pt_expand,						// leaf
    &ss_ss_expand						// internal
};
rtbase_ext_t::PropFctTbl ssPointPropTbl = {
    { &pt_span, NULL },						// leaf
    { &ss_span, NULL }						// internal
};
rtbase_ext_t::BpCmpFctTbl ssPointBpCmpTbl = {
    &ss_equal_ss,
    &ss_contains_pt,						// leaf
    &ss_contains_ss						// internal
};
rtbase_ext_t::ConvFctTbl ssPointConvTbl = {
    { &rt_point::size2dim, &rt_point::dim2size },		// leaf
    { &rt_centroid_sphere::size2dim, &rt_centroid_sphere::dim2size } // internal
};
ss_ext_t::CenterFctTbl ssPointCenterTbl = {
    &pt_center,
    &ss_center
};
rtbase_ext_t::OpTbl ssPointOpTbl = {
    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_ss_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
};

ss_ext_t sspoint_ext(ssPointCmpTbl, ssPointExpandTbl,
    ssPointPropTbl, ssPointConvTbl, ssPointBpCmpTbl,
    ssPointOpTbl, ssPointCenterTbl);
gist_unorderedn_ext_t ss_point_ext(gist_ext_t::ss_point_ext_id,
    "ss_point_ext", gist_support::printSsPred, gist_support::printInt,
    &gist_support::parsePoint, &gist_support::parseInt, gist_support::parseGeoQuery,
    sspoint_ext);

rtbase_nn_cursorext_t::RtPrioFctTbl ssPointNnPrioTbl = {
    { &rt_point::dist_point, NULL },				// leaf
    { &ss_pt_dist, NULL }					// internal
};

rtbase_nn_cursorext_t ss_point_nn_cext(
    gist_cursorext_t::cext_ss_point_nn_id, ssPointNnPrioTbl);

///////////////////////////////////////////////////////////////////////////////
// ss_ext_t methods
///////////////////////////////////////////////////////////////////////////////

ss_ext_t::ss_ext_t(
    CmpFctTbl tbl,
    ExpandFctTbl exp,
    PropFctTbl pf,
    ConvFctTbl cf,
    BpCmpFctTbl bcf,
    OpTbl op,
    CenterFctTbl cenf)
    : rtbase_ext_t(tbl, exp, pf, cf, bcf, op)
{
    for (int i = 0; i < numLvl; ++i) {
	centerFcts[i] = cenf ? cenf[i] : NULL;
    }
}

void
ss_ext_t::penalty(
    const void *subtreePred,
    int predLen,
    int level,
    const void *newKey,
    int keyLen,
    gist_penalty_t &p) const
{
    int d = rt_point::size2dim(keyLen);
    rt_centroid_sphere s(d, (double*) subtreePred);
    rt_point pt(d, (double*) newKey);
    p.p = s.center.dist(pt);
}