/*
This file implements a bit-vector integer set.
Copyright (C) 2004 The University of Texas at Austin

Based upon Daniel Huson's implementation.

This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your option)
any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 59
Temple Place - Suite 330, Boston, MA 02111-1307, USA.

Email: usman@cs.njit.edu
Mail: Usman Roshan, Department of Computer Sciences, NJIT-CCS, Computer
Science Department, GITC 4400, University Heights, Newark, NJ 07102
*/

#include<int_set.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>

static short    static_inited = 0;
static IS_WORD  mask[IS_WORDBITS];
static short    k2word[IS_MAXBITS];
static short    k2bit[IS_MAXBITS];

static int
IS_MIN(int a, int b)
{
	if (a <= b)
		return a;
	else
		return b;
}
static int
IS_MAX(int a, int b)
{
	if (a >= b)
		return a;
	else
		return b;
}
static void     init_static();
static void     resize_int_set(int_set s, const int n);
static void     compute_nelements_int_set(int_set s);
static void     init_int_set(int_set s, const int maxsize);
static void     find_min_max(const int_set A, const int_set B, int_set * min_set, int_set * max_set);

/***** PUBLIC *****/
int_set
new_int_set(const int size)
{
	int_set         s;
	init_static();
	s = (int_set) malloc(sizeof(struct int_set_struct));
	if (size > IS_MAXBITS)
		printf("size=%d\n", size);
	if (size == 0)
		init_int_set(s, IS_WORDBITS);
	else
		init_int_set(s, size);
	return s;
}

void
del_int_set(int_set s)
{
	assert(s);
	assert(s->data);
	free(s->data);
	free(s);
}

void
get_entries_int_set(int_set s, int *entries)
{
	int             k, i;

	assert(s);
	i = 0;
	for (k = s->min; k <= s->max; k++)
		if (member_int_set(s, k))
			entries[i++] = k;
}

int
words_int_set(int_set s)
{
	return k2word[s->max] - k2word[s->min] + 1;
}

int
size_int_set(int_set s)
{
	assert(s);
	return s->nelements;
}

/* is A a subset of B? */
short
subseteq_int_set(int_set A, int_set B)
{
	int             k;
	int             nw;

	assert(A);
	assert(B);
	if (B->nelements == 0)
		return 0;
	if (A->nelements > B->nelements)
		return 0;
	if (A->nelements == 0)
		return 1;
	nw = A->words;
	/* for(k = 0; k < nw; k++){ */
	for (k = k2word[A->min]; k <= k2word[A->max]; k++) {
		if (k >= B->words) {
			if (A->data[k])
				return 0;
		} else if ((A->data[k] | B->data[k]) != B->data[k])
			return 0;
	}
	return 1;
}

short
equal_int_set(int_set A, int_set B)
{

	int             k;

	if (A->nelements != B->nelements)
		return 0;
	if (A->min != B->min || A->max != B->max)
		return 0;
	for (k = k2word[A->min]; k <= k2word[A->max]; k++)
		if (A->data[k] != B->data[k])
			return 0;

	return 1;
}

/* set A = A union B */
int_set
unionequal_int_set(int_set A, int_set B)
{
	int             k;

	assert(A);
	assert(B);

	/* return A if B is empty */
	if (B->nelements == 0)
		return A;

	if (B->bits > A->bits)
		resize_int_set(A, B->bits);

	for (k = k2word[B->min]; k <= k2word[B->max]; k++)
		A->data[k] |= B->data[k];

	/* note that A could be the empty set */
	if (B->min < A->min || A->nelements == 0)
		A->min = B->min;
	if (B->max > A->max || A->nelements == 0)
		A->max = B->max;

	compute_nelements_int_set(A);

	return A;
}

/* return A union B */
int_set
union_int_set(int_set A, int_set B)
{
	int             k;
	int_set         result, min_set, max_set;

	assert(A);
	assert(B);

	/* handle empty set cases */
	result = new_int_set(IS_MAX(A->bits, B->bits));
	if (A->nelements == 0) {
		assign_int_set(result, B);
		return result;
	} else if (B->nelements == 0) {
		assign_int_set(result, A);
		return result;
	}
	find_min_max(A, B, &min_set, &max_set);
	/* nw = IS_MAX(A->words, B->words); */

	for (k = k2word[min_set->min]; k <= k2word[max_set->max]; k++) {
		if (k < A->words)
			result->data[k] |= A->data[k];
		if (k < B->words)
			result->data[k] |= B->data[k];
	}

	result->min = min_set->min;
	result->max = max_set->max;
	compute_nelements_int_set(result);
	return result;
}

/* return A intersection B */
int_set
intersect_int_set(int_set A, int_set B)
{
	int             i, k, nw, min, max, first_defined_k, last_defined_k;
	int_set         result, min_set_, min_set, max_set;

	assert(A);
	assert(B);

	result = new_int_set(IS_MIN(A->bits, B->bits));

	/* handle empty set cases */
	if (A->nelements == 0 || B->nelements == 0) {
		return result;
	}
	find_min_max(A, B, &min_set, &max_set);
	nw = IS_MIN(A->words, B->words);

	if (A->words < B->words)
		min_set_ = A;
	else if (A->words > B->words)
		min_set_ = B;
	else {
		if (A->bits < B->bits)
			min_set_ = A;
		else
			min_set_ = B;
	}

	min = -1;
	max = -1;
	last_defined_k = -1;
	first_defined_k = -1;

	for (k = k2word[min_set->min]; k <= k2word[min_set_->max]; k++) {
		result->data[k] = A->data[k] & B->data[k];
		if (result->data[k] && first_defined_k == -1)
			first_defined_k = k;
		if (result->data[k])
			last_defined_k = k;
	}
	if (first_defined_k != -1) {
		/* find min */
		for (i = 0; i < IS_WORDBITS; i++)
			if (result->data[first_defined_k] & mask[i]) {
				min = first_defined_k * IS_WORDBITS + i;
				break;
			}
		/* find max */
		for (i = IS_WORDBITS - 1; i > -1; i--)
			if (result->data[last_defined_k] & mask[i]) {
				max = last_defined_k * IS_WORDBITS + i;
				break;
			}
	} else {
		/* this means result is empty */
		assert(result->nelements == 0);
		return result;
	}

	result->min = min;
	result->max = max;

	compute_nelements_int_set(result);
	return result;
}

void
insert_int_set(int_set s, const int k)
{
	int             p, r;

	assert(s);
	assert(k >= 0);
	if (k >= s->bits)
		resize_int_set(s, 2 * k);

	p = k2word[k];
	r = k2bit[k];

	if (!(s->data[p] & mask[r])) {
		s->data[p] |= mask[r];
		s->nelements++;
	}
	/* set max and min of set respectively */
	if (s->nelements == 1) {
		s->max = k;
		s->min = k;
	} else {
		if (k > s->max)
			s->max = k;
		if (k < s->min)
			s->min = k;
	}
}

void
remove_int_set(int_set s, const int k)
{
	int             p, r;

	assert(s);
	assert(k >= 0);
	if (k < s->bits) {
		p = k2word[k];
		r = k2bit[k];

		if (s->data[p] & mask[r]) {
			s->data[p] &= ~mask[r];
			s->nelements--;
		}
		if (s->nelements) {
			if (k == s->min) {
				/* find new min */
				for (p = k + 1; p < s->bits; p++) {
					if (member_int_set(s, p)) {
						s->min = p;
						break;
					}
				}
			} else if (k == s->max) {
				/* find new max */
				for (p = k - 1; p > 0; p--) {
					if (member_int_set(s, p)) {
						s->max = p;
						break;
					}
				}
			}
		}
	}
}

short
member_int_set(int_set s, const int k)
{
	int             p, r;

	assert(s);
	assert(k >= 0);
	if (k >= s->bits)
		return 0;
	p = k2word[k];
	r = k2bit[k];
	return (s->data[p] & mask[r]) != 0;
}

void
set2string(int_set s, char *str)
{
	int             k;
	char            buffer[10];

	assert(s);
	for (k = s->min; k <= s->max; k++)
		if (member_int_set(s, k)) {
			sprintf(buffer, "%d ", k);
			strcat(str, buffer);	/* str+=strlen(buffer); */
		}
}

void
print_int_set(int_set s)
{
	int             k;
	int             first = 1;

	assert(s);
	if (s->nelements == 0)
		return;
	for (k = s->min; k <= s->max; k++)
		if (member_int_set(s, k)) {
			if (first) {
				printf("%d", k);
				first = 0;
			} else {
				printf(" %d", k);
			}
		}
}

void
print_int_set2(int_set s, char **num_to_name)
{
	int             k;
	int             first = 1;

	assert(s);
	if (s->nelements == 0)
		return;
	for (k = s->min; k <= s->max; k++)
		if (member_int_set(s, k)) {
			assert(num_to_name[k]);
			if (first) {
				printf("%s", num_to_name[k]);
				first = 0;
			} else {
				printf(" %s", num_to_name[k]);
			}
		}
}

int
choose_int_set(int_set s)
{
	assert(s);
	return s->min;
}

int_set
diffequal_int_set(int_set A, int_set B)
{
	int             i, k, min, max, first_defined_k, last_defined_k;

	assert(A);
	assert(B);

	/* empty sets */
	if (A->nelements == 0 || B->nelements == 0)
		return A;

	/* nw = IS_MIN(A->words, B->words); */
	min = -1;
	max = -1;
	last_defined_k = -1;
	first_defined_k = -1;

	for (k = k2word[A->min]; k <= k2word[A->max]; k++) {
		A->data[k] -= (B->data[k] & A->data[k]);
		if (A->data[k] && first_defined_k == -1)
			first_defined_k = k;
		if (A->data[k])
			last_defined_k = k;
	}
	if (first_defined_k != -1) {
		/* find min */
		for (i = 0; i < IS_WORDBITS; i++)
			if (A->data[first_defined_k] & mask[i]) {
				min = first_defined_k * IS_WORDBITS + i;
				break;
			}
		/* find max */
		for (i = IS_WORDBITS - 1; i > -1; i--)
			if (A->data[last_defined_k] & mask[i]) {
				max = last_defined_k * IS_WORDBITS + i;
				break;
			}
	} else {
		/* this means A is now empty */
		for (k = k2word[A->min]; k <= k2word[A->max]; k++)
			assert(!A->data[k]);
		A->nelements = 0;
		A->min = -1;
		A->max = -1;
		return A;
	}

	A->min = min;
	A->max = max;
	compute_nelements_int_set(A);
	return A;
}

int_set
diff_int_set(int_set A, int_set B)
{

	int_set         result;
	int             i, k, min, max, first_defined_k, last_defined_k;

	assert(A);
	assert(B);

	result = new_int_set(A->bits);
	if (B->nelements == 0) {
		assign_int_set(result, A);
		return result;
	}
	if (A->nelements == 0)
		return result;

	/* nA = A->words; */
	min = -1;
	max = -1;
	last_defined_k = -1;
	first_defined_k = -1;

	for (k = k2word[A->min]; k <= k2word[A->max]; k++) {
		if (k < B->words)
			result->data[k] = A->data[k] - (A->data[k] & B->data[k]);
		else
			result->data[k] = A->data[k];

		if (result->data[k] && first_defined_k == -1)
			first_defined_k = k;
		if (result->data[k])
			last_defined_k = k;
	}
	if (first_defined_k != -1) {
		/* find min */
		for (i = 0; i < IS_WORDBITS; i++)
			if (result->data[first_defined_k] & mask[i]) {
				min = first_defined_k * IS_WORDBITS + i;
				break;
			}
		/* find max */
		for (i = IS_WORDBITS - 1; i > -1; i--)
			if (result->data[last_defined_k] & mask[i]) {
				max = last_defined_k * IS_WORDBITS + i;
				break;
			}
	} else {
		/* this means result is empty */
		assert(result->nelements == 0);
		assert(result->min == -1 && result->max == -1);
		return result;
	}

	result->min = min;
	result->max = max;
	compute_nelements_int_set(result);
	return result;
}

/* copy B into A, with B untouched */
int_set
assign_int_set(int_set A, int_set B)
{
	size_t          bytes;

	assert(A);
	assert(B);
	A->min = B->min;
	A->max = B->max;
	A->bits = B->bits;
	A->words = B->words;
	A->nelements = B->nelements;
	bytes = IS_WORDBYTES * A->words;
	assert(A->data);
	A->data = (IS_WORD *) realloc(A->data, bytes);
	memcpy(A->data, B->data, bytes);
	return A;
}

/***** PRIVATE *****/
static void
resize_int_set(int_set s, const int n)
{

	int             old_nelements, old_words;
	size_t          bytes;

	assert(s);
	assert(n >= 0 && n < IS_MAXBITS);

	old_nelements = s->nelements;
	old_words = s->words;

	s->bits = n;
	s->words = s->bits / IS_WORDBITS + 1;

	bytes = IS_WORDBYTES * s->words;
	s->data = realloc(s->data, bytes);
	assert(s->data != 0);

	if (s->words > old_words)
		memset(&(s->data[old_words]), '\0', (s->words - old_words) * IS_WORDBYTES);

	if (old_nelements)
		compute_nelements_int_set(s);
	assert(old_nelements == s->nelements);
}

static void
compute_nelements_int_set(int_set s)
{
	int             k, i;

	assert(s);
	assert(s->min >= 0 && s->max >= 0);
	s->nelements = 0;
	for (k = k2word[s->min]; k <= k2word[s->max]; k++)
		for (i = 0; i < IS_WORDBITS; i++)
			if (s->data[k] & mask[i])
				s->nelements++;
}

static void
init_static()
{
	int             i;
	if (!static_inited) {
		for (i = 0; i < IS_WORDBITS; i++)
			mask[i] = (1 << i);
		for (i = 0; i < IS_MAXBITS; i++) {
			k2word[i] = i / IS_WORDBITS;
			k2bit[i] = i % IS_WORDBITS;
		}
		static_inited = 1;
	}
}

static void
init_int_set(int_set s, const int maxsize)
{
	size_t          bytes;

	assert(s);
	assert(1 <= maxsize && maxsize <= IS_MAXBITS);
	s->min = -1;
	s->max = -1;
	s->bits = maxsize;
	s->words = s->bits / IS_WORDBITS + 1;
	s->nelements = 0;
	bytes = IS_WORDBYTES * s->words;
	s->data = (IS_WORD *) malloc(bytes);
	assert(s->data != 0);
	memset(s->data, '\0', bytes);
}

static void
find_min_max(const int_set A, const int_set B,
	     int_set * min_set, int_set * max_set)
{

	assert(A->nelements > 0 && B->nelements > 0);

	if (A->min < B->min) {
		*min_set = A;
	} else {
		*min_set = B;
	}

	if (A->max > B->max) {
		*max_set = A;
	} else {
		*max_set = B;
	}
}