/* sum2(X, x) */

#include <alloca.h>

static int fd_sum2_filter(fd_constraint this)
{
  int sum = this->nvariables - 1;
  int min, max;
  int *mins, *maxs;
  int i;

  mins = alloca(this->nvariables * sizeof(int));
  maxs = alloca(this->nvariables * sizeof(int));

  /* do bounds filtering */

  mins[sum] = _fd_var_min(VAR(this, sum));
  maxs[sum] = _fd_var_max(VAR(this, sum));

  // sum the minima of the summands domains
  min = 0;

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

      if (min > maxs[sum])
	return FD_NOSOLUTION;
    }

  // sum the maxima of the summands domains
  max = 0;

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

  if (max < mins[sum])
    return FD_NOSOLUTION;

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

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

	  changed = 1;
	}

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

	  changed = 1;
	}

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

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

  if (min > mins[sum])
    {
      _fd_var_del_lt(min, VAR(this, sum));

      if (fd_domain_empty(VAR(this, sum)))
	return FD_NOSOLUTION;

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

  if (max < maxs[sum])
    {
      _fd_var_del_gt(max, VAR(this, sum));

      if (fd_domain_empty(VAR(this, sum)))
	return FD_NOSOLUTION;

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

  return FD_OK;
}

static int fd_sum2_propagate2(fd_constraint this, fd_int culprit)
{
  return fd_sum2_filter(this);
}

fd_constraint fd_sum2(fd_int *variables, int nvariables, fd_int x)
{
  fd_constraint c = _fd_constraint_new(nvariables + 1, 0);
  int i;

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

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

      _fd_add_constraint(c);
    }

  return c;
}