/* all-different */

#ifdef USE_MATCHING

#include "matching.h"

static int fd_all_different_filter(fd_constraint this)
{
#ifdef CONSTRAINT_TEMPS
  int **memory;
  int ok;

  assert(!fd__constraint_data_valid(this));

  // memory is allocated in _fd_find_matching()
  memory = (int **) &constraint_memory[this->index];

  ok = _fd_find_matching(this, memory);

  if (ok)
    fd__constraint_remember(this);

  return ok ? FD_OK : FD_NOSOLUTION;
#else
  return _fd_find_matching(this) ? FD_OK : FD_NOSOLUTION;
#endif /* CONSTRAINT_TEMPS */
}

static int fd_all_different_propagate2(fd_constraint this, fd_int culprit)
{
#ifdef CONSTRAINT_TEMPS
  int *memory;

  if (!fd__constraint_data_valid(this))
    return fd_all_different_filter(this);

  // memory is allocated in _fd_find_matching()
  memory = constraint_memory[this->index];

  return _fd_update_matching(this, culprit, memory) ? FD_OK : FD_NOSOLUTION;
#else
  return fd_all_different_filter(this);
#endif /* CONSTRAINT_TEMPS */
}

#else /* USE_MATCHING */

static int fd_all_different_filter(fd_constraint this)
{
  int value;
  int i, j;

  // only filter wrt variables whose domain is a singleton
  for (i = 0; i < this->nvariables; ++i)
    if (fd_var_single(VAR(this, i), &value))
      for (j = 0; j < this->nvariables; ++j)
	if (j != i)
	  {
	    fd_int revise = VAR(this, j);

	    if (_fd_var_del_val(value, revise))
	      {
		if (fd_domain_empty(revise))
		  return FD_NOSOLUTION;

		if (i < j)
		  _fd_revise_connected(this, revise);
		else
		  _fd_revise_connected(NULL, revise);
	      }
	  }

  return FD_OK;
}

static int fd_all_different_propagate2(fd_constraint this, fd_int culprit)
{
  int value;
  int i;

  // only revise if culprit's domain is a singleton
  if (!fd_var_single(culprit, &value))
    return FD_OK;

  for (i = 0; i < this->nvariables; ++i)
    if (VAR(this, i) != culprit)
      {
	fd_int revise = VAR(this, i);

	if (_fd_var_del_val(value, revise))
	  {
	    if (fd_domain_empty(revise))
	      return FD_NOSOLUTION;

	    _fd_revise_connected(NULL, revise);
	  }
      }

  return FD_OK;
}

#endif /* USE_MATCHING */

static int fd_all_different_propagate(fd_constraint this, fd_int revise)
{
  int value;
  int changed = 0;
#ifdef USE_ENTAILED
  int set = 0;
#endif
  int i;

  // only revise wrt variables whose domain is a singleton
  for (i = 0; i < this->nvariables; ++i)
    if (VAR(this, i) != revise &&
	fd_var_single(VAR(this, i), &value))
      {
	changed |= _fd_var_del_val(value, revise);
#if defined(USE_ENTAILED) && 0
	set++;
#endif
      }

  if (changed && fd_domain_empty(revise))
    return FD_NOSOLUTION;


#if defined(USE_ENTAILED) && 0
  // XXX: hampers performance when not optimised
  if (set == this->nvariables - 1)
    _fd_constraint_set_entailed(this);
#endif

  if (changed)
    if (fd_var_single(revise, NULL))
      _fd_revise_connected(NULL, revise); // XXX?
    else
      _fd_revise_connected(this, revise);

  return FD_OK;
}

fd_constraint fd_all_different(fd_int *variables, int nvariables)
{
  fd_constraint c;
  int i;

  if (nvariables == 2)
    return fd_ne(variables[0], variables[1]);

  c = _fd_constraint_new(nvariables, 0);

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

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

      _fd_add_constraint(c);
    }

  return c;
}