/* sum(X, k) */

#include <alloca.h>

static int fd_sum_filter(fd_constraint this)
{
  int k;
  int min, max;
  int *mins, *maxs;
  int i;
#ifdef CONSTRAINT_TEMPS
  int *base;

  assert(!fd__constraint_data_valid(this));

  if (constraint_memory[this->index] == NULL)
    constraint_memory[this->index] =
      malloc((2 + 2 * this->nvariables) * sizeof(*base));	// XXX: NULL

  base = constraint_memory[this->index];

  mins = base + 2;
  maxs = mins + this->nvariables;
#else
  mins = alloca(this->nvariables * sizeof(int));
  maxs = alloca(this->nvariables * sizeof(int));
#endif

  // do bounds filtering

  k = this->constants[0];

  // sum the minima of the variables' domains
  min = 0;

  for (i = 0; i < this->nvariables; ++i)
    {
      min += mins[i] = _fd_var_min(VAR(this, i));

      if (min > k)
	return FD_NOSOLUTION;
    }

  // sum the maxima of the variables' domains
  max = 0;

  for (i = 0; i < this->nvariables; ++i)
    max += maxs[i] = _fd_var_max(VAR(this, i));

  if (max < k)
    return FD_NOSOLUTION;

  for (i = 0; i < this->nvariables; ++i)
    {
      int changed = 0;

      if (mins[i] + k - min < maxs[i])
	{
	  _fd_var_del_gt(mins[i] + k - min, VAR(this, i));

	  changed = 1;
	}

      if (maxs[i] - (max - k) > mins[i])
	{
	  _fd_var_del_lt(maxs[i] - (max - k), VAR(this, i));

	  changed = 1;
	}

      if (changed)
	{
	  if (fd_domain_empty(VAR(this, i)))
	    return FD_NOSOLUTION;

	  _fd_revise_connected(this, VAR(this, i));
	}
    }

#ifdef CONSTRAINT_TEMPS
  // save values
  *base = min;
  *(base + 1) = max;

  fd__constraint_remember(this);
#endif /* CONSTRAINT_TEMPS */

  return FD_OK;
}

static int fd_sum_propagate2(fd_constraint this, fd_int culprit)
{
#ifdef CONSTRAINT_TEMPS
  int k;
  int min, max;
  int *mins, *maxs;
  int *base;
  int nmin, nmax, nmin_v, nmax_v;
  int v;
  int i;

  // do bounds filtering

  if (!fd__constraint_data_valid(this))
    return fd_sum_filter(this);		// ignores culprit

  base = constraint_memory[this->index];

  min = *base;
  max = *(base + 1);
  mins = base + 2;
  maxs = mins + this->nvariables;

  k = this->constants[0];

  nmin_v = _fd_var_min(culprit);
  nmax_v = _fd_var_max(culprit);

  // find out where is the culprit
  for (v = 0; culprit != VAR(this, v); ++v)
    ;

  if (nmin_v == mins[v] && nmax_v == maxs[v])
    return FD_OK;	// nothing has (meaningfully) changed

  do
    {
      nmin = min - mins[v] + nmin_v;
      nmax = max - maxs[v] + nmax_v;

      mins[v] = nmin_v;
      maxs[v] = nmax_v;

      while (++v < this->nvariables && VAR(this, v) != culprit)
	;
    }
  while (v < this->nvariables);

  if (nmin > k || nmax < k)
    return FD_NOSOLUTION;

  if (nmin != min)
    {
      for (i = 0; i < this->nvariables; ++i)
	if (mins[i] + k - nmin < maxs[i] &&
	    _fd_var_del_gt(mins[i] + k - nmin, VAR(this, i)))
	  {
	    if (fd_domain_empty(VAR(this, i)))
	      return FD_NOSOLUTION;

	    _fd_revise_connected(NULL, VAR(this, i));
	  }

      *base = nmin;
    }

  if (nmax != max)
    {
      for (i = 0; i < this->nvariables; ++i)
	if (maxs[i] - (nmax - k) > mins[i] &&
	    _fd_var_del_lt(maxs[i] - (nmax - k), VAR(this, i)))
	  {
	    if (fd_domain_empty(VAR(this, i)))
	      return FD_NOSOLUTION;

	    _fd_revise_connected(NULL, VAR(this, i));
	  }

      *(base + 1) = nmax;
    }

  return FD_OK;
#else /* CONSTRAINT_TEMPS */
  return fd_sum_filter(this);	// ignores culprit
#endif /* CONSTRAINT_TEMPS */
}

fd_constraint fd_sum(fd_int *variables, int nvariables, int k)
{
  fd_constraint c = _fd_constraint_new(nvariables, 1);
  int i;

  if (c)
    {
      for (i = 0; i < nvariables; ++i)
	c->variables[i] = FD_INT2C_VAR(variables[i]);
      c->constants[0] = k;
#ifdef CONSTRAINT_CLASS
      c->kind = FD_CONSTR_SUM;
#else /* CONSTRAINT_CLASS */
      c->propagator2 = fd_sum_propagate2;
#endif /* CONSTRAINT_CLASS */

      for (i = 0; i < nvariables; ++i)
	_fd_var_add_constraint(VAR(c, i), c);

      _fd_add_constraint(c);
    }

  return c;
}