#include <assert.h>

/* Sets represented as an ordered list of intervals.
   All functions (except as noted) are non-destructive.

   Assumes interval type as already been defined by including interval.h.

   User should #define: 
    type
    print (optional)
    to_string (optional)
    PRINTF_FORMAT** ( e.g., #define PRINTF_FORMAT "%d" )
    FORMATTED**     ( e.g., #define FORMATTED(x) (x) )
    emptyset
    universe
    is_empty
    is_universe
    singleton
    single_interval
    union
    intersection
    intersect_lists
    equal
    contains
    MAKE_CANONICAL (optional)
    contains_interval*
    abutting_or_overlapping*
    canonicalize*

   * if MAKE_CANONICAL is true
   ** if print is defined
  
   Also, if the type is a signed integral type, one may optionally #define
   all of the following:

    make_bottomopen_interval
    make_topopen_interval
    diff_lists
    difference
*/

#ifndef PRINTF_FORMAT
#define PRINTF_FORMAT "%d"
#endif

#ifndef FORMATTED
#define FORMATTED(x) ((int) (x))
#endif

#include "bool.h"

#define T interval *
#define list seti
#define cons cons_interval
#define head  head_interval
#define tail  tail_interval
#define length  length_interval
#define freecell  freecell_interval
#define set_head  set_head_interval
#define set_tail  set_tail_interval
#define dreverse  dreverse_interval
#define dreverse_and_extend  dreverse_and_extend_interval

#include "list.h"

typedef seti * set;

TI_INLINE(emptyset) set emptyset()
{ set r = NULL; return r; }
TI_INLINE(universe) set universe()
{ set r = (seti *) -1; return r; }
TI_INLINE(is_empty) bool is_empty(set r)
{ return (r == NULL); }
TI_INLINE(is_universe) bool is_universe(set r)
{ return (r == (seti *) -1); }

#if MAKE_CANONICAL
TI_INLINE(abutting_or_overlapping) bool abutting_or_overlapping(interval *x, interval *y)
{
  return ((x->lo <= y->lo && x->hi + 1 >= y->lo) ||
	  (y->lo <= x->lo && y->hi + 1 >= x->lo));
}

TI_INLINE(canonicalize) set canonicalize(set s)
{
  seti *l = s;
  if (!is_universe(s))
    while (l != NULL && tail(l) != NULL) {
      if (abutting_or_overlapping(head(l), head(tail(l)))) {
	set_head(l, containing_interval(head(l), head(tail(l))));
	set_tail(l, tail(tail(l)));
      } else {
	l = tail(l);
      }
    }

  return s;
}

/* s is not the universe and s has at least one element;
   only look at s's first two elements. 
   Otherwise the same as canonicalize(), above. */
TI_INLINE(canonicalize1) set canonicalize1(set s)
{
  seti *l = s;
  if (tail(l) != NULL &&
      abutting_or_overlapping(head(l), head(tail(l)))) {
    set_head(l, containing_interval(head(l), head(tail(l))));
    set_tail(l, tail(tail(l)));
  }
  return s;
}
#else
#define canonicalize
#endif

#ifdef print
TI_INLINE(print) void print(set s) {
  seti *l = s;
  putchar('{');
  while (l != NULL) {
    if (l != s)
      fputs(", ", stdout);
    printf(PRINTF_FORMAT, head(l)->lo);
    if (head(l)->lo != head(l)->hi)
      printf(" - " PRINTF_FORMAT, head(l)->hi);
    l = tail(l);
  }
  putchar('}');
}
#endif

#ifdef to_string
#define ADD_TO_STRING(x)			\
    do {					\
      char *f = (x);				\
      int olen = strlen(o), flen = strlen(f);	\
      if (olen + flen + 2 >= size) {		\
	do 					\
	  size *= 2;				\
	while (olen + flen + 2 >= size);	\
	tmp = ALLOC(char, size);		\
	strcpy(tmp, o);				\
	FREE(o);				\
	o = tmp;				\
      }						\
      strcpy(o + olen, f);			\
    } while (0)

#define ADD_TO_STRING2(x, y)			\
    do {					\
      char *f = (x);				\
      int olen = strlen(o), flen = strlen(f);	\
      if (olen + flen + 2 >= size) {		\
	do					\
	  size *= 2;				\
	while (olen + flen + 2 >= size);	\
	tmp = ALLOC(char, size);		\
	strcpy(tmp, o);				\
	FREE(o);				\
	o = tmp;				\
      }						\
      sprintf(o + olen, f, (y));		\
    } while (0)

#define TO_STRING_BODY					\
{							\
  seti *l = s;						\
  int size = 40;					\
  char *o = ALLOC(char, size), *tmp;			\
  o[0] = '\0'; 						\
  ADD_TO_STRING("{");					\
  while (l != NULL) {					\
    if (l != s)						\
      ADD_TO_STRING(", ");				\
    ADD_TO_STRING2(PRINTF_FORMAT, head(l)->lo);		\
    if (head(l)->lo != head(l)->hi)			\
      ADD_TO_STRING2(" - " PRINTF_FORMAT, head(l)->hi);	\
    l = tail(l);					\
  }							\
  ADD_TO_STRING("}");					\
  return o;						\
}

/* Returns a string representation of s.  Caller should FREE the result. */
TI_INLINE(to_string) char * to_string(set s) 
TO_STRING_BODY

#undef ADD_TO_STRING
#undef ADD_TO_STRING2
#endif /* to_string */

TI_INLINE(minseti) type minseti(seti *l) {
  assert(l != NULL);
  return head(l)->lo;
}

TI_INLINE(maxseti) type maxseti(seti *l) {
  assert(l != NULL);
  while (tail(l) != NULL)
    l = tail(l);
  return head(l)->hi;
}

TI_INLINE(minset) type minset(set s) {
  assert(!is_universe(s));
  return minseti(s);
}

TI_INLINE(maxset) type maxset(set s) {
  assert(!is_universe(s));
  return maxseti(s);
}

TI_INLINE(singleton) set singleton(type x) {
  set r;
  r = cons(singleton_interval(x), NULL);
  return r;
}

TI_INLINE(single_interval) set single_interval(interval *i)
{
  set r;
  r = cons(copy_interval(i), NULL);
  return r;
}

#define copy_body					\
{							\
  set x;						\
  seti *l, *result = NULL;				\
  for (l = s; l != NULL; l = tail(l))			\
    result = cons(copy_interval(head(l)), result);	\
  x = dreverse(result);					\
  if (0) {						\
    char *ss, *xs;					\
    ss = to_string(s);					\
    xs = to_string(x);					\
    printf("copy set %s to %s\n", ss, xs);		\
    FREE(ss);						\
    FREE(xs);						\
  }							\
  return x;						\
}

TI_INLINE(copy) set copy(set s)
copy_body
#undef copy_body

#if MAKE_CANONICAL
#define JUST_UNDER				\
  if (l != NULL && v == head(l)->lo - 1) {	\
    head(l)->lo = v;				\
    return s;					\
  }
#define JUST_OVER				\
  if (l != NULL && v == head(l)->hi + 1) {	\
    head(l)->hi = v;				\
    return canonicalize1(s);			\
  }
#else
#define JUST_UNDER
#define JUST_OVER
#endif

#if MAKE_CANONICAL
TI_INLINE(contains_interval) bool contains_interval(set s, type lo, type hi)
{
  seti *l;
  if (is_empty(s))
    return false;
  if (is_universe(s))
    return true;
  for (l = s; l != NULL; l = tail(l))
    if (head(l)->lo <= lo && head(l)->hi >= hi)
      return true;
    else if (head(l)->lo >= lo)
      break;
  return false;
}
#endif


/* Add v to s. */
TI_INLINE(destructive_adjoin) set destructive_adjoin(type v, set s)
{
  seti *l = s;
  JUST_UNDER;
  JUST_OVER;
  if (l == NULL || v < head(l)->lo) {
    s = cons(singleton_interval(v), l);
    goto canon;
  } else if (v > head(l)->hi)
    while (1)
      if (tail(l) == NULL || v < head(tail(l))->lo) {
	set_tail(l, cons(singleton_interval(v), tail(l)));
	goto canon;
      } else if (v <= head(tail(l))->hi)
	goto done;
      else
	l = tail(l);
  else
    goto done;

 canon:
  s = canonicalize(s);
 done:
  return s;
}

#undef JUST_UNDER
#undef JUST_OVER

/* Return {v} union s (without modifying s).  Result may share part of s. */
TI_INLINE(share_adjoin) set share_adjoin(type v, set s)
{
  if (is_universe(s))
    return s;
  else {
    seti *l = s;
    while (l != NULL) 
      if (v < head(l)->lo) {
	/* everything after l can be shared */
	/* This could be improved by specializing on cases where
	   v isn't in s but some w in s is adjacent to v. */
	seti *h = s;
	set x;
	seti *reversed_result = NULL;
	for (;;) {
	  if (h == l) {
	    seti *result = cons(singleton_interval(v), cons(head(l), tail(l)));
	    x = dreverse_and_extend(reversed_result, result);
	    return canonicalize(x);
	  }
	  reversed_result = cons(head(h), reversed_result);
	  h = tail(h);
	}
      } else if (v <= head(l)->hi)
	/* v >= head(l)->lo && v <= head(l)->hi */
	return s;
      else
	l = tail(l);
    {
      /* v is greater than all elements of s */
      set x;
      seti *result = cons(singleton_interval(v), NULL);
      for (l = s; l != NULL; l = tail(l))
	result = cons(head(l), result);
      x = dreverse(result);
      return x;
    }
  }
}

/* Non-destructive; result may not share structure. */
TI_INLINE(adjoin) set adjoin(type v, set s)
{
  return destructive_adjoin(v, copy(s));
}

#ifdef to_string
#ifdef seti_to_string
TI_INLINE(seti_to_string) char * seti_to_string(seti *l)
{
  set s;
  s = l;
  return to_string(s);
}
#endif
#endif

TI_INLINE(seti_contains) bool seti_contains(seti *l, type v)
{
  for ( ; l != NULL; l = tail(l))
    if (interval_contains(head(l), v))
      return true;
  return false;
}

TI_INLINE(contains) bool contains(set s, type v)
{
  seti *l;
  if (is_empty(s))
    return false;
  if (is_universe(s))
    return true;
  for (l = s; l != NULL; l = tail(l))
    if (interval_contains(head(l), v))
      return true;
  return false;
}

#define equal_body							\
{									\
  seti *xi, *yi;							\
  if (is_universe(x))							\
    return is_universe(y);						\
  if (is_universe(y))							\
    return false;							\
  xi = x;								\
  yi = y;								\
  while (xi != NULL && yi != NULL)					\
    if (head(xi)->lo != head(yi)->lo || head(xi)->hi != head(yi)->hi)	\
      return false;							\
    else {								\
      xi = tail(xi);							\
      yi = tail(yi);							\
    }									\
									\
  return (yi == NULL && xi == NULL);					\
}

TI_INLINE(equal) bool equal(set x, set y)
equal_body
#undef equal_body

#define union_body							\
{									\
  seti *xi, *yi;							\
  seti *r = NULL; /* result */						\
  set s;								\
  if (is_empty(x))							\
    return y;								\
  if (is_empty(y))							\
    return x;								\
  if (is_universe(x) || is_universe(y))					\
    return universe();							\
  xi = x;								\
  yi = y;								\
  while (xi != NULL || yi != NULL)					\
    if (xi == NULL || (yi != NULL && head(yi)->hi < head(xi)->lo)) {	\
      r = cons(head(yi), r);						\
      yi = tail(yi);							\
    } else if (yi == NULL || head(xi)->hi < head(yi)->lo) {		\
      r = cons(head(xi), r);						\
      xi = tail(xi);							\
    } else {								\
      r = cons(containing_interval(head(xi), head(yi)), r);		\
      xi = tail(xi);							\
      yi = tail(yi);							\
    }									\
  s = dreverse(r);							\
  return canonicalize(s);						\
}

TI_INLINE(union) set union(set x, set y)
union_body
#undef union_body

/* May modify one or both args */
#define destructive_union_body_helper				\
{								\
  if (xi == NULL)						\
    return yi;							\
  else if (yi == NULL)						\
    return xi;							\
  else if (head(yi)->hi < head(xi)->lo) {			\
    set_tail(yi, destructive_union_helper(xi, tail(yi)));	\
    return yi;							\
  } else if (head(xi)->hi < head(yi)->lo) {			\
    set_tail(xi, destructive_union_helper(tail(xi), yi));	\
    return xi;							\
  } else {							\
    set_head(xi, containing_interval(head(xi), head(yi)));	\
    yi = destructive_union_helper(tail(xi), tail(yi));		\
    set_tail(xi, NULL);						\
    return destructive_union_helper(xi, yi);			\
  }								\
}

TI_INLINE(destructive_union_helper) seti *destructive_union_helper(seti *xi, seti *yi)
destructive_union_body_helper
#undef destructive_union_body_helper

#define destructive_union_body			\
{						\
  if (is_empty(x))				\
    return y;					\
  if (is_empty(y))				\
    return x;					\
  if (is_universe(x) || is_universe(y))		\
    return universe();				\
  x = destructive_union_helper(x, y);		\
  return x;					\
}

TI_INLINE(destructive_union) set destructive_union(set x, set y)
destructive_union_body
#undef destructive_union_body


TI_INLINE(intersect_lists) seti *intersect_lists(seti *a, seti *b)
{
  if (a == NULL || b == NULL)
    return NULL;
  if (head(a)->hi < head(b)->lo)
    return intersect_lists(tail(a), b);
  if (head(b)->hi < head(a)->lo)
    return intersect_lists(a, tail(b));
  {
    interval *f = intersect_intervals(head(a), head(b));
    if (head(a)->hi > head(b)->hi)
      b = tail(b);
    else
      a = tail(a);
    return cons(f, intersect_lists(a, b));
  }
}

#define intersection_body			\
{						\
  set s;					\
  if (is_empty(x) || is_universe(y))		\
    return x;					\
  if (is_empty(y) || is_universe(x))		\
    return y;					\
  						\
  s = intersect_lists(x, y);		\
  return canonicalize(s);			\
}

TI_INLINE(intersection) set intersection(set x, set y)
intersection_body
#undef intersection_body

#ifdef make_bottomopen_interval
TI_INLINE(make_bottomopen_interval) interval *make_bottomopen_interval(type y, type z)
{
  return make_interval(y + 1, z);
}

TI_INLINE(make_topopen_interval) interval *make_topopen_interval(type y, type z)
{
  return make_interval(y, z - 1);
}

#define DIFF_LISTS_BODY							   \
{									   \
  if (a == NULL || b == NULL)						   \
    return a;								   \
  if (head(a)->hi < head(b)->lo)					   \
    return cons(head(a), diff_lists(tail(a), b));			   \
  if (head(b)->hi < head(a)->lo)					   \
    return diff_lists(a, tail(b));					   \
  {									   \
    type alo = head(a)->lo, blo = head(b)->lo, 				   \
      ahi = head(a)->hi, bhi = head(b)->hi; 				   \
    if (blo <= alo) {							   \
      if (bhi >= ahi)							   \
	return diff_lists(tail(a), b);					   \
      else								   \
	return diff_lists(cons(make_bottomopen_interval(bhi, ahi), a), b); \
    } else {								   \
      /* alo < blo */							   \
      assert(blo <= ahi);						   \
      a = cons(make_interval(blo, ahi), tail(a));			   \
      return cons(make_topopen_interval(alo, blo),			   \
		  diff_lists(a, b));					   \
    }									   \
  }									   \
}

TI_INLINE(diff_lists) seti *diff_lists(seti *a, seti *b)
DIFF_LISTS_BODY
#undef DIFF_LISTS_BODY

#define difference_body				\
{						\
  set s;					\
  if (is_empty(x) || is_empty(y))		\
    return x;					\
  if (is_universe(y))				\
    return emptyset();				\
  assert(!is_universe(x));			\
  						\
  s = diff_lists(x, y);				\
  return canonicalize(s);			\
}

TI_INLINE(difference) set difference(set x, set y)
difference_body
#endif
#undef difference_body


#undef T
#undef list
#undef cons
#undef head
#undef tail
#undef length
#undef freecell
#undef set_head
#undef set_tail
#undef dreverse
#undef dreverse_and_extend