/*
  Domains represented by sequences of intervals.
*/

#ifdef COMPACT_DOMAINS
#  error "COMPACT_DOMAINS defined: shouldn't be reading this file"
#endif

struct fd_iterator {
  fd_value domain;
  int last;
  bool started;
};

fd_value fd_new_value(int min, int max)
{
  fd_value v = malloc(sizeof(struct fd_value));

  if (v)
    {
      if (min < max)
	{
	  v->kind = FD_MULTIPLE;
	  v->value.interval.lower = min;
	  v->value.interval.upper = max;
	}
      else if (min == max)
	{
	  v->kind = FD_SINGLETON;
	  v->value.value = min;
	}
      else
	v->kind = FD_EMPTY;

      v->next = 0;
    }
  else
    perror("fd_new_value(?): malloc");

  return v;
}

bool _fd_val_empty(fd_value domain)
{
  return domain->kind == FD_EMPTY;
}

int _fd_val_single(fd_value domain, int *value)
{
  if (domain->kind != FD_SINGLETON || domain->next != 0)
    return 0;

  if (value != NULL)
    *value = domain->value.value;

  return 1;
}

static void _fd_free_value_segment(fd_value value)
{
  free(value);
}


void _fd_free_value(fd_value value)
{
  fd_value next;

  while (value)
    {
      next = value->next;
      free(value);
      value = next;
    }
}


/* return maximum value from DOMAIN */
int _fd_val_max(fd_value domain)
{
  fd_value v = domain;

  while (v->next)
    v = v->next;

  switch (v->kind)
    {
      case FD_SINGLETON:
	return v->value.value;
      case FD_MULTIPLE:
	return v->value.interval.upper;
      case FD_EMPTY:
	_fd_fatal("empty domain in _fd_val_max");
	/* NOTREACHED */
      default:
	_fd_fatal("corrupt domain in _fd_val_max?");
	/* NOTREACHED */
    }
}

/* return minimum value from DOMAIN */
int _fd_val_min(fd_value domain)
{
  switch (domain->kind)
    {
      case FD_SINGLETON:
	return domain->value.value;
      case FD_MULTIPLE:
	return domain->value.interval.lower;
      case FD_EMPTY:
	_fd_fatal("empty domain in _fd_val_min");
	/* NOTREACHED */
      default:
	_fd_fatal("corrupt domain in _fd_val_min?");
	/* NOTREACHED */
    }
}

/* return and remove minimum value from DOMAIN */
int _fd_val_del_min(fd_value domain)
{
  int min;

  switch (domain->kind)
    {
      case FD_SINGLETON:
	min = domain->value.value;

	if (domain->next == 0)
	  domain->kind = FD_EMPTY;
	else
	  {
	    fd_value next = domain->next;

	    *domain = *domain->next;

	    _fd_free_value_segment(next);
	  }

	break;
      case FD_MULTIPLE:
	min = domain->value.interval.lower;

	if (min + 1 == domain->value.interval.upper)
	  {
	    domain->kind = FD_SINGLETON;
	    domain->value.value = min + 1;
	  }
	else
	  domain->value.interval.lower++;

	break;
      case FD_EMPTY:
	_fd_fatal("empty domain in _fd_val_del_min");
	/* NOTREACHED */
      default:
	_fd_fatal("corrupt domain in _fd_val_del_min?");
	/* NOTREACHED */
    }

  return min;
}

/* return and remove maximum value from DOMAIN */
int _fd_val_del_max(fd_value domain)
{
  fd_value v = domain, *p = &domain;
  int max;

  while (v->next)
    {
      p = &v->next;
      v = v->next;
    }

  switch (v->kind)
    {
      case FD_SINGLETON:
	max = v->value.value;

	if (v == domain)
	    v->kind = FD_EMPTY;
	else
	  {
	    *p = v->next;
	    _fd_free_value_segment(v);
	  }

	break;
      case FD_MULTIPLE:
	max = v->value.interval.upper;

	if (v->value.interval.lower == --v->value.interval.upper)
	  {
	    v->kind = FD_SINGLETON;
	    v->value.value = v->value.interval.lower;
	  }

	break;
      case FD_EMPTY:
	_fd_fatal("empty domain in _fd_val_del_max");
	/* NOTREACHED */
      default:
	_fd_fatal("corrupt domain in _fd_val_del_max?");
	/* NOTREACHED */
    }

  return max;
}

int _fd_val_contains_val(fd_value domain, int value)
{
  fd_value d = domain;

  while (d)
    {
      switch (d->kind)
	{
	  case FD_SINGLETON:
	    if (value < d->value.value)
	      return 0;

	    if (value == d->value.value)
	      return 1;

	    break;
	  case FD_MULTIPLE:
	    if (value <= d->value.interval.upper)
	      return  d->value.interval.lower <= value;

	    break;
	  case FD_EMPTY:
	    _fd_fatal("empty domain in _fd_val_contains_val");
	    /* NOTREACHED */
	  default:
	    _fd_fatal("corrupt domain in _fd_val_contains_val?");
	    /* NOTREACHED */
	}

      d = d->next;
    }

  return 0;
}


void _fd_val_set_value(fd_value domain, int value)
{
  switch (domain->kind)
    {
      case FD_EMPTY:
	_fd_fatal("_fd_val_set_val called on a variable with empty domain");
	/* NOTREACHED */
      case FD_MULTIPLE:
	domain->kind = FD_SINGLETON;
      case FD_SINGLETON:
	domain->value.value = value;
	if (domain->next)
	  {
	    _fd_free_value(domain->next);
	    domain->next = 0;
	  }
	break;
      default:
	_fd_fatal("corrupt domain in _fd_val_set_value?");
	/* NOTREACHED */
    }
}

/* remove all values greater than or equal to VALUE from DOMAIN */
int _fd_val_del_ge(int value, fd_value domain)
{
  fd_value prev, cur;

#ifdef DEBUG_VALUE
  printf("remove {%d..} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

  if (domain->kind == FD_EMPTY)
    return 0;

  prev = cur = domain;

  while (cur)
    if (cur->kind == FD_SINGLETON && cur->value.value < value)
      {
	prev = cur;
	cur = cur->next;
      }
    else if (cur->kind == FD_MULTIPLE && cur->value.interval.upper < value)
      {
	prev = cur;
	cur = cur->next;
      }
    else
      break;

  if (cur == 0)
    return 0;

  if (cur->kind == FD_SINGLETON || cur->value.interval.lower >= value)
    {
      if (cur == domain)
	{
	  domain->kind = FD_EMPTY;
	  _fd_free_value(domain->next);
	  domain->next = 0;
	}
      else
	{
	  _fd_free_value(cur);
	  prev->next = 0;
	}
    }
  else // cur->value.interval.lower < value <= cur->value.interval.upper
    {
      cur->value.interval.upper = value - 1;
      if (cur->value.interval.lower == cur->value.interval.upper)
	{
	  cur->kind = FD_SINGLETON;
	  cur->value.value = cur->value.interval.lower;
	}
      _fd_free_value(cur->next);
      cur->next = 0;
    }

  return 1;
}

/* remove all values greater than VALUE from DOMAIN */
int _fd_val_del_gt(int value, fd_value domain)
{
  fd_value prev, cur;

#ifdef DEBUG_VALUE
  printf("remove {%d..} from ", value + 1);
  _fd_val_print(domain);
  putchar('\n');
#endif

  if (domain->kind == FD_EMPTY)
    return 0;

  prev = cur = domain;

  while (cur)
    if (cur->kind == FD_SINGLETON && cur->value.value <= value)
      {
	prev = cur;
	cur = cur->next;
      }
    else if (cur->kind == FD_MULTIPLE && cur->value.interval.upper <= value)
      {
	prev = cur;
	cur = cur->next;
      }
    else
      break;

  if (cur == 0)
    return 0;

  if (cur->kind == FD_SINGLETON || cur->value.interval.lower > value)
    {
      if (cur == domain)
	{
	  domain->kind = FD_EMPTY;
	  _fd_free_value(domain->next);
	  domain->next = 0;
	}
      else
	{
	  _fd_free_value(cur);
	  prev->next = 0;
	}
    }
  else // cur->value.interval.lower <= value < cur->value.interval.upper
    {
      cur->value.interval.upper = value;
      if (cur->value.interval.lower == cur->value.interval.upper)
	{
	  cur->kind = FD_SINGLETON;
	  cur->value.value = cur->value.interval.lower;
	}
      _fd_free_value(cur->next);
      cur->next = 0;
    }

  return 1;
}

/* remove all values less than or equal to VALUE from DOMAIN */
int _fd_val_del_le(int value, fd_value domain)
{
  fd_value cur;

#ifdef DEBUG_VALUE
  printf("remove {..%d} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

  if (domain->kind == FD_EMPTY)
    return 0;

  // see if there is anything to remove
  if (_fd_val_min(domain) > value)
    return 0;

  // if the first segment of the domain is an interval whose upper
  // bound is greater than value, adjust it
  if (domain->kind == FD_MULTIPLE && domain->value.interval.upper > value)
    {
      domain->value.interval.lower = value + 1;
      if (domain->value.interval.lower == domain->value.interval.upper)
	{
	  domain->kind = FD_SINGLETON;
	  domain->value.value = domain->value.interval.lower;
	}

      return 1;
    }

  // otherwise, the values in the first segment are all less than or
  // equal to value, so don't bother with it
  cur = domain->next;

  // delete all segments with values less than or equal to value
  while (cur &&
	 (cur->kind == FD_SINGLETON && cur->value.value <= value ||
	  cur->kind == FD_MULTIPLE && cur->value.interval.upper <= value))
    {
      fd_value v = cur;

      cur = cur->next;
      _fd_free_value_segment(v);
    }

  if (cur && cur->kind == FD_MULTIPLE && cur->value.interval.lower <= value)
    {
      cur->value.interval.lower = value + 1;
      if (cur->value.interval.lower == cur->value.interval.upper)
	{
	  cur->kind = FD_SINGLETON;
	  cur->value.value = cur->value.interval.lower;
	}
    }

  if (cur == 0)
    {
      domain->kind = FD_EMPTY;
      domain->next = 0;
    }
  else
    {
      memcpy(domain, cur, sizeof(struct fd_value));
      _fd_free_value_segment(cur);
    }

  return 1;
}

/* remove all values less than VALUE from DOMAIN */
int _fd_val_del_lt(int value, fd_value domain)
{
  fd_value cur;

#ifdef DEBUG_VALUE
  printf("remove {..%d} from ", value - 1);
  _fd_val_print(domain);
  putchar('\n');
#endif

  if (domain->kind == FD_EMPTY)
    return 0;

  // see if there is anything to remove
  if (_fd_val_min(domain) >= value)
    return 0;

  // if the first segment of the domain is an interval whose upper
  // bound is greater than or equal to value, adjust it
  if (domain->kind == FD_MULTIPLE && domain->value.interval.upper >= value)
    {
      domain->value.interval.lower = value;
      if (domain->value.interval.lower == domain->value.interval.upper)
	{
	  domain->kind = FD_SINGLETON;
	  domain->value.value = domain->value.interval.lower;
	}

      return 1;
    }

  // otherwise, the values in the first segment are all less than or
  // equal to value, so don't bother with it
  cur = domain->next;

  // delete all segments with values less than value
  while (cur &&
	 (cur->kind == FD_SINGLETON && cur->value.value < value ||
	  cur->kind == FD_MULTIPLE && cur->value.interval.upper < value))
    {
      fd_value v = cur;

      cur = cur->next;
      _fd_free_value_segment(v);
    }

  if (cur && cur->kind == FD_MULTIPLE && cur->value.interval.lower < value)
    {
      cur->value.interval.lower = value;
      if (cur->value.interval.lower == cur->value.interval.upper)
	{
	  cur->kind = FD_SINGLETON;
	  cur->value.value = cur->value.interval.lower;
	}
    }

  if (cur == 0)
    {
      domain->kind = FD_EMPTY;
      domain->next = 0;
    }
  else
    {
      memcpy(domain, cur, sizeof(struct fd_value));
      _fd_free_value_segment(cur);
    }

  return 1;
}

/* remove VALUE from DOMAIN */
int _fd_val_del_val(int value, fd_value domain)
{
  fd_value cur, prev;
  int found = 0;

#ifdef DEBUG_VALUE
  printf("remove {%d} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

  if (domain->kind == FD_EMPTY)
    return 0;

  cur = domain;

  while (!found && cur)
    {
      if (cur->kind == FD_SINGLETON)
	{
	  if (cur->value.value < value)
	    {
	      prev = cur;
	      cur = cur->next;
	    }
	  else if (cur->value.value == value)
	    found = 1;
	  else // value doesn't belong to domain
	    break;
	}
      else // FD_MULTIPLE
	{
	  if (cur->value.interval.upper < value)
	    {
	      prev = cur;
	      cur = cur->next;
	    }
	  else if (cur->value.interval.lower <= value)
	    found = 1;
	  else // value doesn't belong to domain
	    break;
	}
    }

  if (!found)
    return 0;

  if (cur->kind == FD_SINGLETON)
    {
      if (cur == domain)
	{
	  if (domain->next == 0)
	    domain->kind = FD_EMPTY;
	  else
	    {
	      fd_value next = domain->next;
	      memcpy(domain, next, sizeof(struct fd_value));
	      _fd_free_value_segment(next);
	    }
	}
      else
	{
	  prev->next = cur->next;
	  _fd_free_value_segment(cur);
	}
    }
  else // FD_MULTIPLE
    {
      if (value == cur->value.interval.lower)
	cur->value.interval.lower = value + 1;
      else if (value == cur->value.interval.upper)
	cur->value.interval.upper = value - 1;
      else // cur->value.interval.lower < value < cur->value.interval.upper)
	{
	  // split interval
	  fd_value next = cur->next;

	  cur->next = fd_new_value(value + 1, cur->value.interval.upper);

	  cur->value.interval.upper = value - 1;

	  cur->next->next = next;
	}

      // check if the resulting interval is a singleton
      if (cur->value.interval.lower == cur->value.interval.upper)
	{
	  cur->kind = FD_SINGLETON;
	  cur->value.value = cur->value.interval.lower;
	}
    }

  return 1;
}

/* remove every value other than VALUE from DOMAIN */
int _fd_val_del_other(fd_value domain, int value)
{
  // XXX: keeping it simple
  return _fd_val_del_lt(value, domain) | _fd_val_del_gt(value, domain);
}

/* remove from DOMAIN1 all values not in DOMAIN2 */
// XXX
int _fd_val_intersect(fd_value domain1, fd_value domain2)
{
  fd_value copy2;
  int v, min1, max1;
  int changed = 0;

  if (domain1->kind == FD_EMPTY)
    return 0;

  if (domain2->kind == FD_EMPTY)
    {
      _fd_free_value(domain1->next);
      domain1->next = 0;
      domain1->kind = FD_EMPTY;

      return 1;
    }

  copy2 = _fd_val_clone(domain2);

  min1 = _fd_val_min(domain1);
  max1 = _fd_val_max(domain1);

  for (v = min1; v <= max1; ++v)
    {
      if (! _fd_val_del_val(v, copy2))
	changed |= _fd_val_del_val(v, domain1);

      if (copy2->kind == FD_EMPTY)
	{
	  _fd_free_value(copy2);

	  return _fd_val_del_gt(v, domain1) || changed;
	}
    }

  _fd_free_value(copy2);

  return changed;
}

/* create a clone of VALUE */
fd_value _fd_val_clone(fd_value value)
{
  fd_value new, *next;

  new = 0;
  next = &new;

  while (value != 0)
    {
      switch (value->kind)
	{
	  case FD_SINGLETON:
	    *next = fd_new_value(value->value.value, value->value.value);
	    break;
	  case FD_MULTIPLE:
	    *next = fd_new_value(value->value.interval.lower,
				 value->value.interval.upper);
	    break;
	  case FD_EMPTY:
	    *next = fd_new_value(1, 0);
	    break;
	  default:
	    _fd_fatal("corrupt domain in _fd_val_clone?");
	    /* NOTREACHED */
	}

      next = &(*next)->next;

      value = value->next;
    }

  return new;
}

#if 01 // XXX: only used with compact domains?
/* copy FROM's value to TO */
void _fd_val_copy(fd_value to, fd_value from)
{
  // free to's segments other than the first
  if (to->next)
    _fd_free_value(to->next);

  // copy from's first segment
  memcpy(to, from, sizeof(*from));

  while (from->next != 0)
    {
      from = from->next;

      switch (from->kind)
	{
	  case FD_SINGLETON:
	    to->next = fd_new_value(from->value.value, from->value.value);
	    break;
	  case FD_MULTIPLE:
	    to->next = fd_new_value(from->value.interval.lower,
				    from->value.interval.upper);
	    break;
#if 0 // XXX: shouldn't happen
	  case FD_EMPTY:
	    to->next = fd_new_value(1, 0);
	    break;
#endif
	  default:
	    _fd_fatal("corrupt domain in _fd_val_copy?");
	    /* NOTREACHED */
	}

      to = to->next;
    }
}
#endif

int _fd_val_size(fd_value domain)
{
  fd_value v = domain;
  int s = 0;

  while (v && v->kind != FD_EMPTY)
    {
      switch (v->kind)
	{
	  case FD_SINGLETON:
	    s++;
	    break;
	  case FD_MULTIPLE:
	    s += v->value.interval.upper - v->value.interval.lower + 1;
	    break;
	  default:
	    _fd_fatal("corrupt domain in _fd_val_size?");
	    /* NOTREACHED */
	}

      v = v->next;
    }

  return s;
}

void _fd_val_print(fd_value value)
{
  putchar('{');

  while (value)
    {
      switch (value->kind)
	{
	  case FD_SINGLETON:
	    printf("%d", value->value.value);
	    break;
	  case FD_MULTIPLE:
	    printf("%d..%d", value->value.interval.lower,
		             value->value.interval.upper);
	    break;
	}

      value = value->next;

      if (value)
	printf(",");
    }

  putchar('}');
}

/* Iterate over a domain */

fd_iterator _fd_val_iterator(fd_value domain)
{
  struct fd_iterator *iterator = malloc(sizeof(*iterator)); // XXX: NULL

  iterator->domain = domain;
  iterator->started = false;

  return iterator;
}

int _fd_val_has_next(fd_iterator iterator)
{
  return !iterator->started || iterator->domain != NULL;
}

int _fd_val_next_element(fd_iterator iterator)
{
  int v;

  if (!iterator->started)
    {
      iterator->started = true;

      if (iterator->domain->kind == FD_SINGLETON)
	{
	  v = iterator->last = iterator->domain->value.value;

	  iterator->domain = iterator->domain->next;
	}
      else // FD_MULTIPLE
	v = iterator->last = iterator->domain->value.interval.lower;
    }
  else
    {
      if (iterator->domain->kind == FD_SINGLETON)
	{
	  v = iterator->last = iterator->domain->value.value;

	  iterator->domain = iterator->domain->next;
	}
      else // FD_MULTIPLE
	{
	  if (iterator->last < iterator->domain->value.interval.lower)
	    v = iterator->last = iterator->domain->value.interval.lower;
	  else
	    {
	      v = ++iterator->last;

	      if (v == iterator->domain->value.interval.upper)
		iterator->domain = iterator->domain->next;
	    }
	}
    }

  return v;
}

void _fd_val_iterator_dispose(fd_iterator iterator)
{
  free(iterator);
}