/*
 *  rtstrat.c -- strategy map data for rtrees.
 */
#include "tmp/c.h"

#include "utils/rel.h"

#include "storage/bufmgr.h"
#include "storage/bufpage.h"
#include "storage/page.h"

#include "access/isop.h"
#include "access/istrat.h"
#include "access/rtree.h"

RcsId("$Header: /usr/local/dev/postgres/mastertree/newconf/RCS/rtstrat.c,v 1.3 1991/02/27 19:32:47 mao Exp $");

/*
 *  Note:  negate, commute, and negatecommute all assume that operators are
 *	   ordered as follows in the strategy map:
 *
 *	left, left-or-overlap, overlap, right-or-overlap, right, same,
 *	contains, contained-by
 *
 *  The negate, commute, and negatecommute arrays are used by the planner
 *  to plan indexed scans over data that appears in the qualificiation in
 *  a boolean negation, or whose operands appear in the wrong order.  For
 *  example, if the operator "<%" means "contains", and the user says
 *
 *	where not rel.box <% "(10,10,20,20)"::box
 *
 *  the planner can plan an index scan by noting that rtree indices have
 *  an operator in their operator class for negating <%.
 *
 *  Similarly, if the user says something like
 *
 *	where "(10,10,20,20)"::box <% rel.box
 *
 *  the planner can see that the rtree index on rel.box has an operator in
 *  its opclass for commuting <%, and plan the scan using that operator.
 *  This added complexity in the access methods makes the planner a lot easier
 *  to write.
 */

/* if a op b, what operator tells us if (not a op b)? */
static StrategyNumber	RTNegate[RTNStrategies] = {
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy
};

/* if a op_1 b, what is the operator op_2 such that b op_2 a? */
static StrategyNumber	RTCommute[RTNStrategies] = {
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy
};

/* if a op_1 b, what is the operator op_2 such that (b !op_2 a)? */
static StrategyNumber	RTNegateCommute[RTNStrategies] = {
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy,
	InvalidStrategy
};

/*
 *  Now do the TermData arrays.  These exist in case the user doesn't give
 *  us a full set of operators for a particular operator class.  The idea
 *  is that by making multiple comparisons using any one of the supplied
 *  operators, we can decide whether two n-dimensional polygons are equal.
 *  For example, if a contains b and b contains a, we may conclude that
 *  a and b are equal.
 *
 *  The presence of the TermData arrays in all this is a historical accident.
 *  Early in the development of the POSTGRES access methods, it was believed
 *  that writing functions was harder than writing arrays.  This is wrong;
 *  TermData is hard to understand and hard to get right.  In general, when
 *  someone populates a new operator class, the populate it completely.  If
 *  Mike Hirohama had forced Cimarron Taylor to populate the strategy map
 *  for btree int2_ops completely in 1988, you wouldn't have to deal with
 *  all this now.  Too bad for you.
 *
 *  Since you can't necessarily do this in all cases (for example, you can't
 *  do it given only "intersects" or "disjoint"), TermData arrays for some
 *  operators don't appear below.
 *
 *  Note that if you DO supply all the operators required in a given opclass
 *  by inserting them into the pg_opclass system catalog, you can get away
 *  without doing all this TermData stuff.  Since the rtree code is intended
 *  to be a reference for access method implementors, I'm doing TermData
 *  correctly here.
 *
 *  Note on style:  these are all actually of type StrategyTermData, but
 *  since those have variable-length data at the end of the struct we can't
 *  properly initialize them if we declare them to be what they are.
 */

/* if you only have "contained-by", how do you determine equality? */
static uint16 RTContainedByTermData[] = {
	2,					/* make two comparisons */
	RTContainedByStrategyNumber,		/* use "a contained-by b" */
	0x0,					/* without any magic */
	RTContainedByStrategyNumber,		/* then use contained-by, */
	CommuteArguments			/* swapping a and b */
};

/* if you only have "contains", how do you determine equality? */
static uint16 RTContainsTermData[] = {
	2,					/* make two comparisons */
	RTContainsStrategyNumber,		/* use "a contains b" */
	0x0,					/* without any magic */
	RTContainsStrategyNumber,		/* then use contains again, */
	CommuteArguments			/* swapping a and b */
};

/* now put all that together in one place for the planner */
static StrategyTerm RTEqualExpressionData[] = {
	(StrategyTerm) RTContainedByTermData,
	(StrategyTerm) RTContainsTermData,
	NULL
};

/*
 *  If you were sufficiently attentive to detail, you would go through
 *  the ExpressionData pain above for every one of the seven strategies
 *  we defined.  I am not.  Now we declare the StrategyEvaluationData
 *  structure that gets shipped around to help the planner and the access
 *  method decide what sort of scan it should do, based on (a) what the
 *  user asked for, (b) what operators are defined for a particular opclass,
 *  and (c) the reams of information we supplied above.
 *
 *  The idea of all of this initialized data is to make life easier on the
 *  user when he defines a new operator class to use this access method.
 *  By filling in all the data, we let him get away with leaving holes in his
 *  operator class, and still let him use the index.  The added complexity
 *  in the access methods just isn't worth the trouble, though.
 */

static StrategyEvaluationData RTEvaluationData = {
	RTNStrategies,				/* # of strategies */
	(StrategyTransformMap) RTNegate,	/* how to do (not qual) */
	(StrategyTransformMap) RTCommute,	/* how to swap operands */
	(StrategyTransformMap) RTNegateCommute,	/* how to do both */
	NULL,					/* express left */
	NULL,					/* express overleft */
	NULL,					/* express over */
	NULL,					/* express overright */
	NULL,					/* express right */
	(StrategyExpression) RTEqualExpressionData,	/* express same */
	NULL,					/* express contains */
	NULL					/* express contained-by */
};

/*
 *  Okay, now something peculiar to rtrees that doesn't apply to most other
 *  indexing structures:  When we're searching a tree for a given value, we
 *  can't do the same sorts of comparisons on internal node entries as we
 *  do at leaves.  The reason is that if we're looking for (say) all boxes
 *  that are the same as (0,0,10,10), then we need to find all leaf pages
 *  that overlap that region.  So internally we search for overlap, and at
 *  the leaf we search for equality.
 *
 *  This array maps leaf search operators to the internal search operators.
 *  We assume the normal ordering on operators.
 */
static StrategyNumber RTOperMap[RTNStrategies] = {
	RTOverLeftStrategyNumber,
	RTOverLeftStrategyNumber,
	RTOverlapStrategyNumber,
	RTOverRightStrategyNumber,
	RTOverRightStrategyNumber,
	RTOverlapStrategyNumber,
	RTContainsStrategyNumber,
	RTContainedByStrategyNumber
};

StrategyNumber
RelationGetRTStrategy(r, attnum, proc)
	Relation r;
	AttributeNumber attnum;
	RegProcedure proc;
{
	return (RelationGetStrategy(r, attnum, &RTEvaluationData, proc));
}

bool
RelationInvokeRTStrategy(r, attnum, s, left, right)
	Relation r;
	AttributeNumber attnum;
	StrategyNumber s;
	Datum left;
	Datum right;
{
	return (RelationInvokeStrategy(r, &RTEvaluationData, attnum, s,
				       left, right));
}

RegProcedure
RTMapOperator(r, attnum, proc)
	Relation r;
	AttributeNumber attnum;
	RegProcedure proc;
{
	StrategyNumber procstrat;
	RegProcedure newproc;
	StrategyMap strategyMap;

	procstrat = RelationGetRTStrategy(r, attnum, proc);
	strategyMap = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(r),
						  RTNStrategies,
						  attnum);

	return (strategyMap->entry[RTOperMap[procstrat - 1] - 1].procedure);
}