/* Sets of vectors of integers, represented using hashing on the first
   n - 1 vector coordinates.  The last coordinate uses an
   interval-based set representation.

*/

#include "iseti.h"
#include "ivhash.h"
#include "stringlist.h"

typedef struct ivseti {
  iseti s;
  ivhash *h;
} ivseti;

#define ivseti_emptyset() NULL

TI_INLINE(ivseti_is_empty) bool ivseti_is_empty(ivseti *s)
{
  return (s == NULL || iseti_is_empty(s->s));
}

TI_INLINE(ivseti_dim) int ivseti_dim(ivseti *s)
{
  int count = 1;
  if (s == NULL)
    return 0;
  while (s != NULL && s->h != NULL && !iseti_is_empty(s->s)) {
    count++;
    s = ivget(iseti_min(s->s), s->h);
  }
  return count;
}

TI_INLINE(ivseti_flat) ivseti *ivseti_flat(iseti f) {
  ivseti *s = ALLOC(ivseti, 1);
  s->s = f;
  s->h = NULL;
  return s;
}

TI_INLINE(ivseti_singleton) ivseti *ivseti_singleton(int i)
{
  return ivseti_flat(iseti_singleton(i));
}

TI_INLINE(ivseti_single_interval) ivseti *ivseti_single_interval(iinterval *i)
{
  return ivseti_flat(iseti_single_interval(i));
}

TI_INLINE(ivseti_intervals) seti *ivseti_intervals(ivseti *s)
{
  return (ivseti_is_empty(s) ? NULL : s->s);
}

TI_INLINE(ivseti_to_iseti) iseti ivseti_to_iseti(ivseti *s)
{
  switch (ivseti_dim(s)) {
  case 0: return iseti_emptyset();
  case 1: return s->s;
  default: assert(("Can't convert multidimensional ivseti to an iseti", 0));
    abort();
    return iseti_emptyset();
  }
}    

TI_INLINE(ivseti_cons) ivseti *ivseti_cons(int x, ivseti *s)
{
  ivseti *r = ivseti_singleton(x);
  if (!ivseti_is_empty(s)) {
    r->h = ivhashtable();
    ivinsert(x, s, r->h);
  }
  return r;
}

/* Return a list whose head is the set s with each element prefixed by p.
   The rest of the list is random junk we allocated followed by z.
   Caller should deallocate the list and all the strings in it. */
#define ivseti_to_string_with_prefix_body				\
{									\
  int d = ivseti_dim(s);						\
  if (d == 1) {								\
    bool empty = iseti_is_empty(s->s);					\
    char *last = empty ? NULL : iseti_to_string(s->s);			\
    int len = empty ? 1 : (strlen(p) + 20 + strlen(last));		\
    char *result = ALLOC(char, len);					\
    if (empty)								\
      result[0] = '\0';							\
    else {								\
      /* don't use '{' and '}' that start and end last */		\
      last[strlen(last) - 1] = '\0';					\
      sprintf(result, "<%s%s>", p, last + 1);				\
    }									\
    return cons_stringlist(result, cons_stringlist(last, NULL));	\
  } else if (d > 1) {							\
    seti *i;								\
    char *result = NULL;						\
    for (i = s->s; i != NULL; i = tail_interval(i)) {			\
      int j;								\
      for (j = head_interval(i)->lo; j <= head_interval(i)->hi; j++) {	\
	int x;								\
	char *q, *subresult, *pp = ALLOC(char, strlen(p) + 20);		\
	sprintf(pp, "%s%d; ", p, j);					\
	z = ivseti_to_string_with_prefix(ivget(j, s->h), pp, z);	\
	FREE(pp);							\
	subresult = (z == NULL) ? "NULL" : head_stringlist(z);		\
	x = 10 + strlen(subresult);					\
	if (result != NULL)						\
	  x += strlen(result);						\
	q = ALLOC(char, x);						\
	if (result != NULL)						\
	  sprintf(q, "%s, %s", result, subresult);			\
	else								\
	  sprintf(q, "%s", subresult);					\
	if (z != NULL) {						\
	  FREE(subresult);						\
	  z = freecell_stringlist(z);					\
	}								\
	z = cons_stringlist(q, z);					\
	result = q;							\
      }									\
    }									\
  }									\
  return z;								\
}

TI_INLINE(ivseti_to_string_with_prefix) stringlist *ivseti_to_string_with_prefix(ivseti *s,
								const char *p,
								stringlist *z)
ivseti_to_string_with_prefix_body
#undef ivseti_to_string_with_prefix_body

/* Caller should free the result. */
#define ivseti_to_string_body					\
{								\
  stringlist *r = ivseti_to_string_with_prefix(s, "", NULL);	\
  char *o = ((r == NULL) ? "" : head_stringlist(r)),		\
    *q = ALLOC(char, strlen(o) + 10);				\
  sprintf(q, "{ %s }", o);					\
  while (r != NULL) {						\
    FREE(head_stringlist(r));					\
    r = freecell_stringlist(r);					\
  }								\
  return q;							\
}

TI_INLINE(ivseti_to_string) char *ivseti_to_string(ivseti *s)
ivseti_to_string_body
#undef ivseti_to_string_body

TI_INLINE(ivseti_print) void ivseti_print(ivseti *s)
{
  char *o = ivseti_to_string(s);
  fputs(o, stdout);
  FREE(o);
}

/* Compute the union of a and b, possibly destructively modifying a. 
   Also, a may end up sharing parts of b's data structure.
*/
#define ivseti_union_body						 \
{									 \
  if (ivseti_is_empty(b))						 \
    return a;								 \
  else if (ivseti_is_empty(a))						 \
    return b;								 \
  else {								 \
    if (b->h != NULL) {							 \
      seti *i;								 \
      for (i = b->s; i != NULL; i = tail_interval(i)) {		 \
	int j;								 \
	for (j = head_interval(i)->lo; j <= head_interval(i)->hi; j++) { \
	  ivseti *a_of_j, *b_of_j = ivget(j, b->h);			 \
	  if (a->h == NULL) {						 \
	    a->h = ivhashtable();					 \
	    a_of_j = NULL;						 \
	  } else							 \
	    a_of_j = ivget(j, a->h);					 \
	  if (a_of_j == NULL)						 \
	    ivinsert(j, b_of_j, a->h);					 \
	  else								 \
	    ivinsert(j, ivseti_union(a_of_j, b_of_j), a->h);		 \
	}								 \
      }									 \
    }									 \
    a->s = iseti_union(a->s, b->s);					 \
    return a;								 \
  }									 \
}

TI_INLINE(ivseti_union) ivseti *ivseti_union(ivseti *a, ivseti *b)
ivseti_union_body
#undef ivseti_union_body

/* Compute the intersection of a and b, possibly destructively modifying a. 
   Also, a may end up sharing parts of b's data structure.
*/
TI_INLINE(ivseti_intersection) ivseti *ivseti_intersection(ivseti *a, ivseti *b)
{
  if (ivseti_is_empty(b))
    return ivseti_emptyset();
  else if (!ivseti_is_empty(a)) {
    /* Iterate through each part of a, removing parts as needed */
    if (a->h != NULL) {
      seti *i;
      iseti dead = iseti_emptyset();
      for (i = a->s; i != NULL; i = tail_interval(i)) {
	int j;
	for (j = head_interval(i)->lo; j <= head_interval(i)->hi; j++) {
	  ivseti *a_of_j;
	  if (iseti_contains(b->s, j))
	    a_of_j = ivseti_intersection(ivget(j, a->h), ivget(j, b->h));
	  else
	    a_of_j = NULL;
	  ivdelete(j, a->h);
	  if (ivseti_is_empty(a_of_j))
	    dead = iseti_destructive_adjoin(j, dead);
	  else
	    ivinsert(j, a_of_j, a->h);
	}
      }
      a->s = iseti_difference(a->s, dead);
    }
    else
      a->s = iseti_intersection(a->s, b->s);
  }
  if (ivseti_is_empty(a))
    return ivseti_emptyset();
  return a;
}


TI_INLINE(interval_cross_ivseti) ivseti *interval_cross_ivseti(iinterval *i, ivseti *s)
{
  int a;
  ivseti *result = ivseti_single_interval(i);
  result->h = ivhashtable();
  for (a = i->lo; a <= i->hi; a++)
    ivinsert(a, s, result->h);
  return result;
}

TI_INLINE(iseti_cross_ivseti) ivseti *iseti_cross_ivseti(iseti r, ivseti *s)
{
  ivseti *result = ivseti_emptyset();
  if (!iseti_is_empty(r) && !ivseti_is_empty(s)) {
    seti *l = r;
    while (l != NULL) {
      result = ivseti_union(result,
			    interval_cross_ivseti(head_interval(l), s));
      l = tail_interval(l);
    }
  }
  return result;
}

/* Find the minimum of s in dimension dim (counting from 0).
   Extremely inefficient! */
TI_INLINE(ivseti_min) int ivseti_min(ivseti *s, int dim)
{
  assert(!ivseti_is_empty(s));
  if (dim == 0)
    return iseti_min(s->s);
  else {
    int result = 0;
    bool inited = false;
    seti *i;
    for (i = s->s; i != NULL; i = tail_interval(i)) {
      int j;
      for (j = head_interval(i)->lo; j <= head_interval(i)->hi; j++) {
	int submin = ivseti_min(ivget(j, s->h), dim - 1);
	if (!inited) {
	  result = submin;
	  inited = true;
	} else if (submin < result)
	  result = submin;
      }
    }
    assert(inited);
    return result;
  }
}

/* Find the maximum of s in dimension dim (counting from 0).
   Extremely inefficient! */
TI_INLINE(ivseti_max) int ivseti_max(ivseti *s, int dim)
{
  assert(!ivseti_is_empty(s));
  if (dim == 0)
    return iseti_max(s->s);
  else {
    int result = 0;
    bool inited = false;
    seti *i;
    for (i = s->s; i != NULL; i = tail_interval(i)) {
      int j;
      for (j = head_interval(i)->lo; j <= head_interval(i)->hi; j++) {
	int submax = ivseti_max(ivget(j, s->h), dim - 1);
	if (!inited) {
	  result = submax;
	  inited = true;
	} else if (submax > result)
	  result = submax;
      }
    }
    assert(inited);
    return result;
  }
}

TI_INLINE(ivseti_range) void ivseti_range(ivseti *s, int dim, int *lo, int *hi)
{
  *lo = ivseti_min(s, dim);
  *hi = ivseti_max(s, dim);
}

TI_INLINE(ivseti_contains) bool ivseti_contains(ivseti *s, int *v)
{
  return (!ivseti_is_empty(s) && iseti_contains(s->s, v[0]) &&
	  (s->h == NULL || ivseti_contains(ivget(v[0], s->h), v + 1)));
}

TI_INLINE(ivseti_contains1) bool ivseti_contains1(ivseti *s, int v0)
{
  return (!ivseti_is_empty(s) && iseti_contains(s->s, v0));
}

TI_INLINE(ivseti_contains2) bool ivseti_contains2(ivseti *s, int v0, int v1)
{
  return (!ivseti_is_empty(s) && iseti_contains(s->s, v0) &&
	  (s->h != NULL && ivseti_contains1(ivget(v0, s->h), v1)));
}

TI_INLINE(ivseti_contains3) bool ivseti_contains3(ivseti *s, int v0, int v1, int v2)
{
  return (!ivseti_is_empty(s) && iseti_contains(s->s, v0) &&
	  (s->h != NULL && ivseti_contains2(ivget(v0, s->h), v1, v2)));
}

TI_INLINE(ivseti_contains_interval) bool ivseti_contains_interval(ivseti *s, int lo, int hi)
{
  assert(ivseti_dim(s) == 1);
  {
    bool result = iseti_contains_interval(s->s, lo, hi);
    /*
      printf("ivseti_contains_interval(%s, %d, %d): %d\n",
      ivseti_to_string(s), lo, hi, (int)result);
    */
    return result;
  }
}

/* is s shifted by shift a subset of t? */
TI_INLINE(ivseti_is_shifted_subset) bool ivseti_is_shifted_subset(ivseti *s, ivseti *t, int *shift)
{
  if (!ivseti_is_empty(s)) {
    seti *i;
    int dim = ivseti_dim(s);
    if (dim == 1) {
      for (i = s->s; i != NULL; i = tail_interval(i))
	if (!ivseti_contains_interval(t, head_interval(i)->lo + *shift,
				      head_interval(i)->hi + *shift))
	  return false;
    } else {
      for (i = s->s; i != NULL; i = tail_interval(i)) {
	int j;
	for (j = head_interval(i)->lo; j <= head_interval(i)->hi; j++) {
	  if (!iseti_contains(t->s, j + *shift) ||
	      !ivseti_is_shifted_subset(ivget(j, s->h), ivget(j + *shift, t->h),
					shift + 1))
	    return false;
	}
      }
    }
  }
  return true;
}

TI_INLINE(ivseti_is_shifted_subset1) bool ivseti_is_shifted_subset1(ivseti *s, ivseti *t, int shift)
{
  return ivseti_is_shifted_subset(s, t, &shift);
}

TI_INLINE(ivseti_is_shifted_subset2) bool ivseti_is_shifted_subset2(ivseti *s, ivseti *t, int shift0, int shift1)
{
  bool result;
  int a[2];
  a[0] = shift0;
  a[1] = shift1;
  result = ivseti_is_shifted_subset(s, t, a);
  /*
  if (!result) {
    printf("not shifted subset: ");
    ivseti_print(s);
    printf(", ");
    ivseti_print(t);
    printf(", [%d %d]\n", shift0, shift1);
  }
  */
  return result;
}

TI_INLINE(ivseti_is_shifted_subset3) bool ivseti_is_shifted_subset3(ivseti *s, ivseti *t, int shift0, int shift1, int shift2)
{
  bool result;
  int a[3];
  a[0] = shift0;
  a[1] = shift1;
  a[2] = shift2;
  result = ivseti_is_shifted_subset(s, t, a);
  /*
  if (!result) {
    printf("not shifted subset: ");
    ivseti_print(s);
    printf(", ");
    ivseti_print(t);
    printf(", [%d %d %d]\n", shift0, shift1, shift2);
  }
  */
  return result;
}


TI_INLINE(ivseti_copy) ivseti *ivseti_copy(ivseti *s)
{
  if (ivseti_is_empty(s))
    return ivseti_emptyset();
  else {
    seti *i;
    ivseti *r = ivseti_flat(iseti_copy(s->s));
    /* fputs("r = ", stdout); ivseti_print(r); puts(""); */
    if (s->h != NULL) {
      r->h = ivhashtable();
      for (i = s->s; i != NULL; i = tail_interval(i)) {
	int j;
	for (j = head_interval(i)->lo; j <= head_interval(i)->hi; j++)
	  ivinsert(j, ivseti_copy(ivget(j, s->h)), r->h);
      }
    }
    /*
    ivseti_print(s); fputs(" copied to ", stdout); ivseti_print(r); puts("");
    */
    return r;
  }
}