/* exactly(X, c, k) == #{ x \in X | x = k } = c */

static int fd_exactly_filter(fd_constraint this)
{
  int k, c;
  int set, possible;
  int value;
  int i;

  k = this->constants[0];
  c = this->constants[1];

  set = possible = 0;

  // count the variables that are set to k and those which contain k
  // in their domain
  for (i = 0; i < this->nvariables; ++i)
    if (fd_var_single(VAR(this, i), &value))
      {
	if (value == k)
	  // if there are more than c variables set to k, fail
	  if (++set > c)
	    return FD_NOSOLUTION;
      }
    else if (_fd_var_contains_val(VAR(this, i), k))
      possible++;

  // see if it still possible to satisfy the constraint
  if (set + possible < c)
    return FD_NOSOLUTION;

  if (set + possible == c)
    {
      for (i = 0; possible > 0; ++i)
	if (!fd_var_single(VAR(this, i), NULL) &&
	    _fd_var_contains_val(VAR(this, i), k))
	  {
	    _fd_var_set_value(VAR(this, i), k);

	    possible--;

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

      fd__constraint_set_entailed(this);

      return FD_OK;
    }

  if (set == c)
    {
      for (i = 0;  possible > 0; ++i)
	if (!fd_var_single(VAR(this, i), NULL) &&
	    _fd_var_del_val(k, VAR(this, i)))
	  {
	    possible--;

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

      fd__constraint_set_entailed(this);

      return FD_OK;
    }

  // the constraint can still be satisfied: set < c && set + possible > c
  return FD_OK;
}

static int fd_exactly_propagate2(fd_constraint this, fd_int culprit)
{
  return fd_exactly_filter(this);
}

fd_constraint fd_exactly(fd_int *variables, int nvariables, int cardinal, int k)
{
  fd_constraint c = _fd_constraint_new(nvariables, 2);
  int i;

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

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

      _fd_add_constraint(c);
    }

  return c;
}