/* element */
/* element(X, Y, k) == X[Y] = k */

static int fd_element_filter(fd_constraint this)
{
  fd_int index;
  int k;
  int value;
  int i;

  // do some filtering...

  index = VAR(this, this->nvariables - 1);
  k = this->constants[0];

  // see if the index is already fixed
  if (fd_var_single(index, &value))
    {
      if (_fd_var_del_other(VAR(this, value), k))
	{
	  if (fd_domain_empty(VAR(this, value)))
	    return FD_NOSOLUTION;

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

      fd__constraint_set_entailed(this);

      return FD_OK;
    }

  // check which variables have k in their domain
  for (i = 0; i < this->nvariables - 1; ++i)
    if (!_fd_var_contains_val(VAR(this, i), k) && _fd_var_del_val(i, index))
      {
	if (fd_domain_empty(index))
	  return FD_NOSOLUTION;

	_fd_revise_connected(NULL, index);
      }

  // the index may have become fixed
  if (fd_var_single(index, &value))
    {
      if (_fd_var_del_other(VAR(this, value), k))
	_fd_revise_connected(this, VAR(this, value));

      fd__constraint_set_entailed(this);
    }

  return FD_OK;
}

static int fd_element_propagate2(fd_constraint this, fd_int culprit)
{
  fd_int index;
  int k;
  int value;
  int i;

  // do some filtering...
  // XXX: assuming that, in time, the last (index) variable's domain's
  //      values will all correspond to variables which have k in their
  //      domain

  index = VAR(this, this->nvariables - 1);
  k = this->constants[0];

  // see if the culprit is the index variable
  if (culprit == index)
    {
      if (fd_var_single(index, &value))
	{
	  if (_fd_var_del_other(VAR(this, value), k))
	    {
	      if (fd_domain_empty(VAR(this, value)))
		return FD_NOSOLUTION;

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

	  fd__constraint_set_entailed(this);
	}

      return FD_OK; // XXX: there's more to be done...
    }

  // find which non-index variable caused the propagation
  for (i = 0; culprit != VAR(this, i); ++i)
    ;

  if (!_fd_var_contains_val(culprit, k) && _fd_var_del_val(i, index))
    {
      if (fd_domain_empty(index))
	return FD_NOSOLUTION;

      _fd_revise_connected(NULL, index);
    }

  return FD_OK;
}

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

  // XXX: add a constraint 0 <= INDEX < nvariables

  if (c)
    {
      for (i = 0; i < nvariables; ++i)
	c->variables[i] = FD_INT2C_VAR(variables[i]);
      c->variables[nvariables] = FD_INT2C_VAR(index);
      c->constants[0] = k;
#ifdef CONSTRAINT_CLASS
      c->kind = FD_CONSTR_ELEMENT;
#else /* CONSTRAINT_CLASS */
      c->propagator2 = fd_element_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;
}