/* Provides an interval type.  Defines the type interval with fields
lo and hi.  The user should #define the following:

    interval
    make_interval                            
    singleton_interval
    copy_interval                            
    is_empty
    include_in_interval
    INCLUDE_INTERVAL_DIVISION (optional)
    divide_interval*
    divide_rounding_to_minus_inf*
    divide_rounding_to_plus_inf*
    multiply_interval
    shift_interval                            
    containing_interval                            
    intersect_intervals
    interval_contains (optional)
    ALLOC

    Those marked * are needed only if INCLUDE_INTERVAL_DIVISION is true.
*/

#include "alloc.h"
#include "bool.h"

typedef struct {
  T lo, hi;
} interval;

TI_INLINE(make_interval) interval *make_interval(T lo, T hi)
{
  interval *r = ALLOC(interval, 1);
  r->lo = lo;
  r->hi = hi;
  assert(lo <= hi);
  return r;
}

TI_INLINE(singleton_interval) interval *singleton_interval(T p)
{
  return make_interval(p, p);
}

TI_INLINE(copy_interval) interval *copy_interval(interval *i)
{
  return make_interval(i->lo, i->hi);
}

TI_INLINE(is_empty) bool is_empty(interval *i)
{
  return (i == NULL || i->lo > i->hi);
}

/* Modify i to contain a. */
TI_INLINE(include_in_interval) void include_in_interval(interval *i, T a)
{
  if (is_empty(i))
    i->lo = i->hi = a;
  else {
    if (i->lo > a)
      i->lo = a;
    if (i->hi < a)
      i->hi = a;
  }
}

#ifdef interval_contains
TI_INLINE(interval_contains) bool interval_contains(interval *i, T a)
{
  return (i->lo <= a && a <= i->hi);
}
#endif

#if INCLUDE_INTERVAL_DIVISION
/* Return r, the smallest interval such that i is a subset of d times r. */
TI_INLINE(divide_interval) interval *divide_interval(interval *i, T d)
{
  if (!is_empty(i)) {
    if (d != 1) {
      i->lo = divide_rounding_to_minus_inf(i->lo, d);
      i->hi = divide_rounding_to_plus_inf(i->hi, d);
    }
    if (d < 0) {
      T x = i->lo;
      i->lo = i->hi;
      i->hi = x;
    } 
  }
  return i;
}
#endif

TI_INLINE(multiply_interval) interval *multiply_interval(interval *i, T d)
{
  if (d != 1) {
    i->lo *= d;
    i->hi *= d;
  }
  if (d < 0) {
    T x = i->lo;
    i->lo = i->hi;
    i->hi = x;
  } 
  return i;
}

TI_INLINE(shift_interval) interval *shift_interval(interval *i, T d)
{
  i->lo += d;
  i->hi += d;
  return i;
}

/* Return a new interval that is the smallest interval that covers i and j. */
TI_INLINE(containing_interval) interval *containing_interval(interval *i, interval *j)
{
  if (is_empty(i))
    return make_interval(j->lo, j->hi);
  else if (is_empty(j))
    return make_interval(i->lo, i->hi);
  else {
    interval *r = ALLOC(interval, 1);
    r->lo = ((i->lo < j->lo) ? i->lo : j->lo);
    r->hi = ((i->hi > j->hi) ? i->hi : j->hi);
    return r;
  }
}

/* Return a new interval that is intersection of i and j. */
TI_INLINE(intersect_intervals) interval *intersect_intervals(interval *i, interval *j)
{
  if (is_empty(i))
    return make_interval(i->lo, i->hi);
  else if (is_empty(j))
    return make_interval(j->lo, j->hi);
  else {
    interval *r = ALLOC(interval, 1);
    r->lo = ((i->lo > j->lo) ? i->lo : j->lo);
    r->hi = ((i->hi < j->hi) ? i->hi : j->hi);
    return r;
  }
}