#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <assert.h>

#include "fdc_int.h"
#include "constraints.h"

#ifdef REVISION_IS_VAR
typedef fd_int revision;
#else /* REVISION_IS_VAR */
typedef struct revision {
  fd_int        variable;
  fd_constraint constraint;
} revision;
#endif /* REVISION_IS_VAR */

#if defined(REVISION_IS_VAR) || !defined(ORDER_REVISIONS)
// there can't be more scheduled revisions than there are variables
static __thread revision _fd_revisions[MAX_VARIABLES];
static __thread int first_revision = 0;
static __thread int n_revisions = 0;
#else
// XXX: adapt it to using an array (or better)
static __thread fd_list _fd_revisions;
#endif

#ifndef ORDER_REVISIONS
static __thread int revision_location[MAX_VARIABLES];
#endif


/* returns < 0, 0, or > 0 if R1 is less than, equal to, or greater than R2 */
#ifdef REVISION_IS_VAR
int _fd_cmp_revisions(revision r1, revision r2)
{
  if (r1 < r2)
    return -1;

  if (r1 > r2)
    return 1;

  return 0;
}
#else /* REVISION_IS_VAR */
int _fd_cmp_revisions(revision *r1, revision *r2)
{
  if (r1->variable < r2->variable)
    return -1;

  if (r1->variable > r2->variable)
    return 1;

  return 0;
}
#endif /* REVISION_IS_VAR */

/* discard all scheduled revisions */
void _fd_reset_revisions()
{
#if defined(REVISION_IS_VAR) || !defined(ORDER_REVISIONS)
#ifndef ORDER_REVISIONS
  if (n_revisions > MAX_VARIABLES / (1 << 30)) // XXX
    memset(revision_location, -1,
	   fd_variables_count * sizeof(*revision_location));
  else if (n_revisions)
    {
      int i;

      for (i = first_revision; i < first_revision + n_revisions; ++i)
#ifdef REVISION_IS_VAR
	revision_location[_fd_revisions[i % MAX_VARIABLES]->index] = -1;
#else
	revision_location[_fd_revisions[i % MAX_VARIABLES].variable->index] = -1;
#endif
    }
#endif /* ORDER_REVISIONS */

  n_revisions = 0;
  first_revision = 0;
#else /* REVISION_IS_VAR || !ORDER_REVISIONS */
  fd_list_empty_list_deep(_fd_revisions, free);
#endif /* REVISION_IS_VAR || !ORDER_REVISIONS */
}

/* schedule a revision request for every variable from VARIABLES (wrt
   every constraint, where applicable) */
void _fd_init_revisions2(fd_int variables[])
{
#if defined(REVISION_IS_VAR) || !defined(ORDER_REVISIONS)
  int i;

  for (i = 0; i < fd_variables_count; ++i)
    {
#ifdef REVISION_IS_VAR
      _fd_revisions[i] = _fd_variables[i];
#else
      _fd_revisions[i].variable = _fd_variables[i];
      _fd_revisions[i].constraint = NULL;
#endif
#ifndef ORDER_REVISIONS
      revision_location[i] = i; // XXX: assuming order coincides with index
#endif
    }

  first_revision = 0;
  n_revisions = fd_variables_count;
#else /* ORDER_REVISIONS */
  int i;

  _fd_revisions = fd_list_new();

  for (i = 0; i < fd_variables_count; ++i)
    {
      revision *r = malloc(sizeof(struct revision));

      r->variable = variables[i];
      r->constraint = NULL;

      fd_list_sorted_insert(_fd_revisions, r, _fd_cmp_revisions);
    }
#endif /* ORDER_REVISIONS */
}

/* schedule a revision request for every variable (wrt every
   constraint, where applicable) */
void _fd_init_revisions()
{
  _fd_init_revisions2(_fd_variables);
}

void _fd_cleanup_revisions()
{
#if !defined(REVISION_IS_VAR) && defined(ORDER_REVISIONS)
  if (_fd_revisions)
    fd_list_dispose(_fd_revisions);
#endif
}

int _fd_perform_revisions()
{
#ifdef REVISION_IS_VAR
  revision r;
#else
  revision *r;
#endif
  fd_int v;
  int i;
#ifdef COUNT_REVISIONS
  int nr = 0;
#endif

#if defined(REVISION_IS_VAR) || !defined(ORDER_REVISIONS)
  while (n_revisions)
    {
#ifdef REVISION_IS_VAR
      v = _fd_revisions[first_revision];
#else
      r = &_fd_revisions[first_revision];
      v = r->variable;
#endif
#ifndef ORDER_REVISIONS
      revision_location[v->index] = -1;
#endif
      first_revision = (first_revision + 1) % MAX_VARIABLES;
      n_revisions--;

      for (i = 0; i < v->nconstraints; ++i)
	{
	  fd_constraint c = CONSTRAINT(v, i);

#ifndef REVISION_IS_VAR
	  if (c == r->constraint)
	    continue;
#endif

	  if (fd__constraint_entailed(c))
	    continue;

	  if (_fd_propagate(c, v) == FD_NOSOLUTION)
	    {
#ifdef COUNT_REVISIONS
	      _fd_debug("failed after %d revisions\n", nr + 1);
#endif

	      return FD_NOSOLUTION;
	    }

#ifdef COUNT_REVISIONS
	  ++nr;
#endif
	}
    }
#else /* ORDER_REVISIONS */
  while (r = fd_list_remove(_fd_revisions))
    {
      v = r->variable;

      for (i = 0; i < v->nconstraints; ++i)
	{
	  fd_constraint c = CONSTRAINT(v, i);

	  if (c == r->constraint)
	    continue;

	  if (fd__constraint_entailed(c))
	    continue;

	  if (_fd_propagate(c, v) == FD_NOSOLUTION)
	    {
	      free(r);

#ifdef COUNT_REVISIONS
	      _fd_debug("failed after %d revisions\n", nr + 1);
#endif

	      return FD_NOSOLUTION;
	    }

#ifdef COUNT_REVISIONS
	  ++nr;
#endif
	}

      free(r);
    }
#endif /* ORDER_REVISIONS */

#ifdef COUNT_REVISIONS
  _fd_debug("performed %d revisions\n", nr);
#endif

  return FD_OK;
}

static int filter_domains()
{
  int i;
#ifdef COUNT_REVISIONS
  int nr = 0;
#endif

  n_revisions = MAX_VARIABLES;		// XXX: tmp hack, to force resetting
  _fd_reset_revisions();

  for (i = 0; i < _fd_constraint_count; ++i)
    {
      fd_constraint c = _fd_constraints[i];

      if (_fd_filter(c) == FD_NOSOLUTION)
	{
#ifdef COUNT_REVISIONS
	  _fd_debug("failed after %d filtering steps\n", nr + 1);
#endif

	  return FD_NOSOLUTION;
	}

#ifdef COUNT_REVISIONS
      ++nr;
#endif
    }

#ifdef COUNT_REVISIONS
  _fd_debug("performed %d filtering steps\n", nr);
#endif

  // revise domains wrt the variables whose domains changed
  return _fd_perform_revisions();
}

int _fd_filter_domains()
{
#ifdef CONSTRAINT_TEMPS
  fd__constraint_data_reset();
#endif

  return filter_domains();
}

int _fd_revise_wrt_variable(fd_int variable)
{
  if (variable)
    {
      _fd_reset_revisions();

      _fd_revise_connected(NULL, variable);

      return _fd_perform_revisions();
    }

  return filter_domains();
}

#ifdef REVISION_IS_VAR
void _fd_add_revision(fd_int variable)
{
  revision r = variable;

#ifndef ORDER_REVISIONS
#ifdef DEBUG_REVISION
  printf("add revision (%p)\n", variable);
#endif

  assert(n_revisions < fd_variables_count);

  // doesn't check whether it is already scheduled
  // XXX: is there a risk of overflowing the array?
  // XXXXXX: not really used
  _fd_revisions[(first_revision + n_revisions) % MAX_VARIABLES] = r;
  revision_location[r->index] = (first_revision + n_revisions) % MAX_VARIABLES;
  n_revisions++;
#else /* ORDER_REVISIONS */
  int l, u, m;

  // XXX: could (should?) index directly by variable->index

  l = first_revision;
  u = l + n_revisions;

  while (l < u)
    {
      m = (l + u) / 2;
      switch (_fd_cmp_revisions(r, _fd_revisions[m % MAX_VARIABLES]))
	{
	  case -1:
	    u = m;
	    break;
	  case 0:
#ifdef DEBUG_REVISION
	    printf("revision (%p) already scheduled\n", variable);
#endif
	    return;
	  case 1:
	    l = m + 1;
	    break;
	}
    }

#ifdef DEBUG_REVISION
    printf("add revision (%p)\n", variable);
#endif

    assert(n_revisions < fd_variables_count);

    // insert revision at l % MAX_VARIABLES
    for (u = first_revision + n_revisions; u > l; --u)
      _fd_revisions[u % MAX_VARIABLES] = _fd_revisions[(u - 1) % MAX_VARIABLES];
    _fd_revisions[l % MAX_VARIABLES] = r;
    n_revisions++;
#endif /* ORDER_REVISIONS */
}
#else /* REVISION_IS_VAR */
void _fd_add_revision(fd_int variable, fd_constraint constraint)
{
#ifndef ORDER_REVISIONS
  int p;

#ifdef DEBUG_REVISION
  printf("add revision (%p, %p)\n", variable, constraint);
#endif

  assert(n_revisions < fd_variables_count);

  // doesn't check whether it is already scheduled
  // XXX: is there a risk of overflowing the array?
  // XXXXXX: not really used
  p = (first_revision + n_revisions) % MAX_VARIABLES;
  _fd_revisions[p].variable = variable;
  _fd_revisions[p].constraint = constraint;
  revision_location[variable->index] = p;
  n_revisions++;
#else /* ORDER_REVISIONS */
  revision *r = malloc(sizeof(struct revision));  // XXX: check for null

  r->variable = variable;
  r->constraint = constraint;

  if (!fd_list_sorted_insert(_fd_revisions, r, _fd_cmp_revisions))
    // already scheduled
#ifdef DEBUG_REVISION
    {
      printf("revision (%p, %p) already scheduled\n", variable, constraint);
#endif
      free(r);
#ifdef DEBUG_REVISION
    }
  else
    printf("add revision (%p, %p)\n", variable, constraint);
#endif
#endif /* ORDER_REVISIONS */
}
#endif /* REVISION_IS_VAR */

/* only add a revision if it is not already scheduled */
#ifdef REVISION_IS_VAR
void _fd_add_new_revision(fd_int variable)
{
#ifndef ORDER_REVISIONS
  int i, n = n_revisions;

  if (revision_location[variable->index] != -1)
    // already scheduled
    {
#ifdef DEBUG_REVISION
      printf("revision (%p) already scheduled\n", variable);
#endif

      return;
    }

#ifdef DEBUG_REVISION
  printf("added revision (%p)\n", variable);
#endif

  assert(n_revisions < fd_variables_count);

  _fd_revisions[(first_revision + n_revisions) % MAX_VARIABLES] = variable;
  revision_location[variable->index] =
    (first_revision + n_revisions) % MAX_VARIABLES;
  n_revisions++;
#else /* ORDER_REVISIONS */
  _fd_add_revision(variable);
#endif /* ORDER_REVISIONS */
}
#else /* REVISION_IS_VAR */
void _fd_add_new_revision(fd_int variable, fd_constraint constraint)
{
#ifndef ORDER_REVISIONS
  int i, n = n_revisions;

  if (revision_location[variable->index] != -1)
    // already scheduled
    {
#ifdef DEBUG_REVISION
      printf("revision (%p) already scheduled\n", variable);
#endif

      i = revision_location[variable->index];

      if (_fd_revisions[i].constraint == NULL)
	_fd_revisions[i].constraint = constraint;
      else if (_fd_revisions[i].constraint != constraint)
	_fd_revisions[i].constraint = NULL;

#ifdef DEBUG_REVISION
      printf("revision (%p) constraint changed to %p\n", variable, _fd_revisions[i].constraint);
#endif

      return;
    }

#ifdef DEBUG_REVISION
  printf("added revision (%p, %p)\n", variable, constraint);
#endif

  assert(n_revisions < fd_variables_count);

  i = (first_revision + n_revisions) % MAX_VARIABLES;
  _fd_revisions[i].variable = variable;
  _fd_revisions[i].constraint = constraint;
  revision_location[variable->index] = i;
  n_revisions++;
#else /* ORDER_REVISIONS */
#warning "this is wrong (it doesn't update the constraint field)"
  _fd_add_revision(variable, constraint);
#endif /* ORDER_REVISIONS */
}
#endif /* REVISION_IS_VAR */