/* knapsack */
/* knapsack(X, Y) == min(Y) <= sum(X) <= max(Y) */

// XXX: assumes all values are non-negative

static int fd_knapsack_propagate2(fd_constraint this, fd_int culprit)
{
  int ub, lb;
  int min, max;
  int terms = this->nvariables - 1;
  int i;

  // XXX: ignoring culprit

  lb = _fd_var_min(VAR(this, this->nvariables - 1));	// lower bound
  ub = _fd_var_max(VAR(this, this->nvariables - 1));	// upper bound

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

  for (i = 0; i < terms; ++i)
    {
      min += _fd_var_min(VAR(this, i));

      if (min > ub)
	return FD_NOSOLUTION;
    }

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

  for (i = 0; i < terms; ++i)
    max += _fd_var_max(VAR(this, i));

  if (max < lb)
    return FD_NOSOLUTION;

  // XXX: poor man's propagation
  if (min == ub)
    for (i = 0; i < terms; ++i)
      {
	int min_x = _fd_var_min(VAR(this, i));
	int min_y = _fd_var_min(VAR(this, terms + i));
	int changed_x = 0, changed_y = 0;

	if (min_x != 0 || min_y != 0)
	  if (min_x == 0)
	    {
	      if (_fd_var_del_gt(0, VAR(this, i)))
		_fd_revise_connected(this, VAR(this, i));
	    }
	  else if (min_y == 0)
	    {
	      if (_fd_var_del_gt(0, VAR(this, terms + i)))
		_fd_revise_connected(this, VAR(this, terms + i));
	    }
	  else // min_x != 0 && min_y != 0
	    {
	      if (_fd_var_del_gt(min_x, VAR(this, i)))
		_fd_revise_connected(this, VAR(this, i));

	      if (_fd_var_del_gt(min_y, VAR(this, terms + i)))
		_fd_revise_connected(this, VAR(this, terms + i));
	    }
      }
  else if (max == lb)
    for (i = 0; i < terms; ++i)
      {
	int max_x = _fd_var_max(VAR(this, i));
	int max_y = _fd_var_max(VAR(this, terms + i));
	int changed_x = 0, changed_y = 0;

	if (max_x != 0 || max_y != 0)
	  if (max_x == 0)
	    {
	      if (_fd_var_del_lt(0, VAR(this, i)))	   // XXX: delete < 0???
		_fd_revise_connected(this, VAR(this, i));
	    }
	  else if (max_y == 0)
	    {
	      if (_fd_var_del_lt(0, VAR(this, terms + i))) // XXX: delete < 0???
		_fd_revise_connected(this, VAR(this, terms + i));
	    }
	  else // max_x != 0 && max_y != 0
	    {
	      if (_fd_var_del_lt(max_x, VAR(this, i)))
		_fd_revise_connected(this, VAR(this, i));

	      if (_fd_var_del_lt(max_y, VAR(this, terms + i)))
		_fd_revise_connected(this, VAR(this, terms + i));
	    }
      }

  if (_fd_var_del_lt(min, VAR(this, this->nvariables - 1)) |
      _fd_var_del_gt(max, VAR(this, this->nvariables - 1)))
    {
      if (fd_domain_empty(VAR(this, this->nvariables - 1)))
	return FD_NOSOLUTION;

      _fd_revise_connected(this, VAR(this, this->nvariables - 1));
    }

  return FD_OK;
}

fd_constraint fd_knapsack(fd_int variables[], int nvariables, fd_int limits)
{
  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(limits);
#ifdef CONSTRAINT_CLASS
      c->kind = FD_CONSTR_KNAPSACK;
#else /* CONSTRAINT_CLASS */
      c->propagator2 = fd_knapsack_propagate2;
#endif /* CONSTRAINT_CLASS */

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

      _fd_add_constraint(c);
    }

  return c;
}