/************************************************************************/
/*                                                                      */
/* Copyright (c) 1988 -                                                 */
/*     The Rector and Visitors of the University of Virginia            */
/*                                                                      */
/* This code may not be distributed further without permission          */
/*      from the University of Virginia.                                */
/* This code is distributed WITHOUT ANY WARRANTY.  No claims are        */
/*      made as to whether it serves any particular purpose or even     */
/*      works at all.                                                   */
/*                                                                      */
/************************************************************************/

/*
 * Sets are implemented as a structure consisting of the minimum element,
 * the maximum element, and a fixed size array of words.  This array is
 * a bit map representation of the set elements.  If the minimum element
 * is greater than the maximum, or if the bit map is all zeros, the set
 * is null.  The bit map is always shifted in such a way that the bit
 * representing the minimum element "min" is the nth bit in the first
 * word of the bit map.  If L is the number of bits in a word, then
 * for min > 0, n = min mod L.  For min < 0, n = L - (-min mod L).
 *
 * Any set can be represented so long as max div L - min div L < N, where
 * N is the number of words in the bit map.  The bit map should be long
 * enough to represent "set of char", which has the elements 0..255 on
 * most ascii machines.
 */

#include <stdio.h>
#include "size.h"
#include "scan.h"
#include "runtime.h"

#define SHBASE(i) (((i) / WBITS - ((i) < 0)))
#define BASE(i) (SHBASE(i) * WBITS)
#define BITOP(op,bits,n) ((bits)[(n)/WBITS] op (1 << ((n)%WBITS)))
#define NULLSET(s) ((s)->st_min > (s)->st_max)

/*
 * shift(s,n) shifts the set bitmap by n words.  Positive n moves words
 * from the front of the array towards the back, negative n from the
 * back to the front.
 */

static 
shift(s, n)
	SET *s;
	int n;
{
	register int i;
	if (n > 0) {
		for (i = MAPLENG-1; i >= 0; i--)
			s->st_bits[i] = (i-n >= 0) ? s->st_bits[i-n] : 0;
	}
	else if (n < 0) {
		for (i = 0; i < MAPLENG; i++)
			s->st_bits[i] = (i-n < MAPLENG) ? s->st_bits[i-n] : 0;
	}
}


/*
 * normalize(s) finds the min and max element of a set "s" and shifts its
 * bit map as far toward the front as possible.  Returns "s".
 */

static SET *
normalize(s)
	SET *s;
{
	register int i, b;

	/* find smallest element */

	for (i = 0; i < MAPLENG; i++) {
		if (s->st_bits[i])
			break;
	}
	if (i >= MAPLENG) {		/* a null set */
		s->st_min = 0;
		s->st_max = -1;
		return(s);
	}

	for (b = 0; b < WBITS; b++) {
		if (s->st_bits[i] & (1 << b))
			break;
	}
	s->st_min = BASE(s->st_min) + i * WBITS + b;
	shift(s, -i);

	/* find largest element */

	for (i = MAPLENG-1; i >= 0; i--) {
		if (s->st_bits[i])
			break;
	}
	for (b = WBITS-1; b >= 0; b--) {
		if (s->st_bits[i] & (1 << b))
			break;
	}
	s->st_max = BASE(s->st_min) + i * WBITS + b;
	return(s);
}

/*
 * RT_set_init(s) assigns the null set to "s" and returns "s".
 */

SET *
RT_set_init(s)
	register SET *s;
{
	register int i;
	s->st_min = 0;
	s->st_max = -1;
	for (i = 0; i < MAPLENG; i++)
		s->st_bits[i] = 0;
	return(s);
}

/*
 * RT_set_in(i, s) returns 1 if "i" is an element of set "s", else 0.
 */

int
RT_set_in(i, s)
	int i;
	SET *s;
{
	if (s->st_min <= i && i <= s->st_max) {
		i -= BASE(s->st_min);
		return(BITOP(&, s->st_bits, i) ? 1 : 0);
	}
	return(0);
}

/*
 * RT_set_member adds element "i" to set "s" and returns "s".
 */

SET *
RT_set_member(i, s)
	int i;
	SET *s;
{
	int base, newbase, errflag=0;
	if (NULLSET(s))
		s->st_min = s->st_max = i;
	base = BASE(s->st_min);
	if (i < base) {		/* must shift before adding element */
		newbase = BASE(i);
		if (s->st_max - newbase < MAXELM) {
			shift(s, SHBASE(s->st_min) - SHBASE(i));
			s->st_min = i;
			BITOP(|=, s->st_bits, i - newbase);
		}
		else
			errflag++;
	}
	else if (i - base < MAXELM) {
		BITOP(|=, s->st_bits, i - base);
		if (i > s->st_max)
			s->st_max = i;
		else if (i < s->st_min)
			s->st_min = i;
	}
	else
		errflag++;
	if (errflag)
		 RT_abort("set was too large to construct");
	return(s);
}

/*
 * RT_set_range(low, high, s) adds the range of elements "low..high" to
 * set "s" and returns "s".
 */

SET *
RT_set_range(low, high, s)
	register int low, high;
	SET *s;
{
	while (low <= high)
		(void) RT_set_member(low++, s);
	return(s);
}

/*
 * RT_set_cmp(op, s1, s2) returns 1 if the comparison "s1 op s2" is true
 * for sets "s1" and "s2", else 0.  The pascal operators are ">=", "<=",
 * "=", and "<>".
 */

int
RT_set_cmp(op, s1, s2)
	int op;
	SET *s1, *s2;
{
	register int i;
	int equal;
	SET tmp, *p;

	switch(op) {

	case SY_EQUAL:
	case SY_NE:
		if (NULLSET(s1) && NULLSET(s2))
			equal = 1;
		else if (s1->st_min != s2->st_min || s1->st_max != s2->st_max)
			equal = 0;
		else {
			equal = 1;
			for (i = 0; i < MAPLENG; i++) {
				if (s1->st_bits[i] != s2->st_bits[i]) {
					equal = 0;
					break;
				}
			}
		}
		return(op == SY_EQUAL ? equal : !equal);

	case SY_LE:		/* (s1 <= s2) == (s2 >= s1) */
		p  = s1;
		s1 = s2;
		s2 = p;
		/* fall through */	

	case SY_GE:
		if (NULLSET(s2))
			return(1);
		if (s1->st_min > s2->st_min || s1->st_max < s2->st_max)
			return(0);
		tmp = *s2;
		shift(&tmp, SHBASE(tmp.st_min) - SHBASE(s1->st_min));
		for (i = 0; i < MAPLENG; i++) {
			if (s1->st_bits[i] != (s1->st_bits[i] | tmp.st_bits[i]))
				return(0);
		}
		return(1);
	}
	/* NOTREACHED */
}

/*
 * RT_set_binop(op, s1, s2, ret) performs the set arithmetic operation
 * "s1 op s2", storing the result in "ret" and returning "ret".  The
 * operators are "+" (set union), "*" (set intersection), and "-" (set
 * difference).
 */

SET *
RT_set_binop(op, s1, s2, ret)
	int op;
	SET *s1, *s2, *ret;
{
	SET tmp;
	register int i;

	switch (op) {

	case SY_PLUS:
		if (NULLSET(s1)) {
			*ret = *s2;
			return(ret);
		}
		if (NULLSET(s2)) {
			*ret = *s1;
			return(ret);
		}

		/* copy set with larger minimum to tmp */

		if (s1->st_min > s2->st_min) {
			tmp  = *s1;
			*ret = *s2;
		}
		else {
			tmp  = *s2;
			*ret = *s1;
		}

		/* check for overflow */

		if (tmp.st_max - BASE(ret->st_min) >= MAXELM)
			RT_abort("result from set union was too large");

		/* shift and OR together */

		shift(&tmp, SHBASE(tmp.st_min) - SHBASE(ret->st_min));
		for(i = 0; i < MAPLENG; i++)
			ret->st_bits[i] |= tmp.st_bits[i];
		return(normalize(ret));

	case SY_STAR:
		
		if (NULLSET(s2)) {
			*ret = *s2;
			return(ret);
		}
		/* fall through */

	case SY_MINUS:
		*ret = *s1;
		if (NULLSET(ret)) {
			return(ret);
		}
		tmp = *s2;
		shift(&tmp, SHBASE(tmp.st_min) - SHBASE(ret->st_min));
		for (i = 0; i < MAPLENG; i++) {
			ret->st_bits[i] &= 
				op == SY_STAR ? tmp.st_bits[i] : ~tmp.st_bits[i];
		}
		return(normalize(ret));
	}
	/* NOTREACHED */
}

/*
 * RT_set_check sees if a set has members that are outside a permissible
 * range.
 */

SET *
RT_set_check(s, lower, upper)
	SET *s;
	int lower, upper;
{
	if (!NULLSET(s) && (s->st_min < lower || s->st_max > upper))
		RT_abort("set expression out of bounds");
	return(s);
}

/*
 * RT_set_dump writes out the integral values of the memebers of
 * a set.  This function is provided for users to print out a set with
 * the debugger \fIsdb\fR.
 */

RT_set_dump(s)
	register SET *s;
{
	register int base, i, j, count;
	if (NULLSET(s)) {
		printf ("null set\n");
		return;
	}
	putc('[', stdout);
	count = 1;
	base = BASE(s->st_min);
	for (i = 0; i < MAPLENG; i++) {
		for (j = 0; j < WBITS; j++) {
			if (s->st_bits[i] & (1 << j)) {
				if (count > 70) {
					count = 0;
					putc('\n', stdout);
				}
				count += printf(" %d", base + i * WBITS + j);
			}
		}
	}
	printf (" ]\n");
}
