#include  "defns.i"
#include  "extern.i"



int	FoundSize = 20000;		/* size of current Found table  */


	/*  Given tuples T with index TIX, find the tuples that satisfy
	    the column and same-value constraints on case C.  Leave the
	    tuples in Found with their number in NFound  */

	/*  NB: Foil spends a large proportion of its execution time in
	    this single routine.  For that reason, the code has been
	    written for speed (on a DECstation 3100), even though this has
	    reduced its clarity.  If using different hardware, it would
	    probably be worth rewriting this  */


Boolean Join(T, TIX, A, C, N, YesOrNo)
/*      ----  */
    Tuples T;
    Index TIX;
    Vars A;
    Tuple C;
    int N;
    Boolean YesOrNo;
{
    int Pair[2*MAXARITY],		/* Pair[i], Pair[i+1] are paired variables */
	*MaxPair = Pair,		/* highest pair of same variables */
	*PairPtr,
	MaxCol = 0,			/* highest column constraint */
    	MaxNo = 0, 			/* index numbers in relation */
	*Next[MAXARITY],		/* Next[i] = next tuple obeying ith constraint */
	**NextPtr,
	**LastNext,
	V, Val, i, j;
    Boolean NoCols, Checked[MAXARITY];
    Tuple Candidate;

    NFound = 0;

    /*  Set the column constraints and find pairs of free variables that
	must be the same  */

    memset(Checked+1, 0, N);

    ForEach(i, 1, N)
    {
	if ( ! (V = A[i]) ) continue;

	/*  If this variable is bound, record a constraint; otherwise see if
	    it is the same as another unbound variable  */

	if ( V <= MaxVar && (Val = C[V]) )
	{
	    if ( ! (Next[MaxCol++] = TIX[i][Val]) ) return false;
	}
	else
	if ( ! Checked[i] )
	{
	    ForEach(j, i+1, N)
	    {
		if ( A[j] == V )
		{
		    *MaxPair++ = i;
		    *MaxPair++ = j;
		    Checked[j] = true;
		}
	    }
	}
    }
    NoCols = MaxCol-- <= 0;
    LastNext = Next + MaxCol;

    while ( true )
    {
	/*  Advance all columns to MaxNo  */

	for ( NextPtr = Next ; NextPtr <= LastNext ; )
	{
	    while ( **NextPtr < MaxNo ) (*NextPtr)++;

	    MaxNo = **NextPtr++;
	}

	if ( MaxNo == FINISH || NoCols && ! T[MaxNo] )
	{
	    Found[NFound] = Nil;
	    return (NFound > 0);
	}
	else
	if ( NoCols || MaxNo == *Next[0] )
	{
	    /*  Found one possibility  -- check same variable constraints  */

	    Candidate = T[MaxNo];

	    for ( PairPtr = Pair ;
		  PairPtr < MaxPair && Candidate[*PairPtr] == Candidate[*(PairPtr+1)] ;
		  PairPtr += 2 )
		;

	    if ( PairPtr >= MaxPair )
	    {
		if ( YesOrNo ) return true;

		if ( NFound >= FoundSize )
		{
		    FoundSize += 20000;
		    Found = (Tuple *) Resize(Found, (FoundSize+1) * sizeof(Tuple));
		}

		Found[NFound++] = Candidate;
	    }

	    MaxNo++;
	}
    }
}