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

#include <assert.h>

#include "fdc_int.h"
#include "values.h"
#include "store.h"
#include "constraints.h"

#include "util.h"

int fd_variables_count = 0;
__thread fd_int _fd_variables[MAX_VARIABLES];

// variables with singleton domains (ie, constants)
static fd_int fd__constants[MAX_VALUE + 1];

fd_int *fd__label_vars = 0;	// variables subject to labelling
int fd__label_vars_count = 0;
bool *fd__var_labelled;		// identifies the variables subject to labelling


/*
  Create and return a new variable with domain { MIN, ..., MAX }.
  Also store it in the global variable table.
*/
static fd_int create_variable(int min, int max)
{
  fd_int v;

  if (fd_variables_count == MAX_VARIABLES)
    fd__fatal("too many variables, increase MAX_VARIABLES");

  v = malloc(sizeof(struct fd_int));

  if (v)
    {
      v->index = fd_variables_count++;
      _fd_init_domain(DOMAIN(v), min, max);
      v->constraints = NULL;
      v->nconstraints = 0;
      v->nconnections = 0;
      v->epoch = 0;
      v->assigned = false;
      v->flags = 0;

      _fd_variables[v->index] = v;
    }

  return v;
}

/* Return a variable with singleton domain { VALUE }. */
fd_int fd_const(int value)
{
  if (value < MIN_VALUE)
    fd__fatal("value less than MIN_VALUE");

  if (value > MAX_VALUE)
    fd__fatal("value greater than MAX_VALUE");

  // only create the variable if it has not yet been created
  if (fd__constants[value] == NULL)
    fd__constants[value] = create_variable(value, value);

  return fd__constants[value];
}

/* Return a variable with domain { MIN, ..., MAX }. */
fd_int fd_new(int min, int max)
{
  if (min == max)
    return fd_const(min);
  else
    return create_variable(min, max);
}

#ifdef SPLITGO
/* create a skeletal copy of VARIABLE */ // XXX: description
fd_int _fd_var_copy(fd_int variable)
{
  fd_int v = malloc(sizeof(struct fd_int));

  if (v)
    {
      v->index = variable->index;
#ifdef USE_STORE
//      v->domain = variable->domain;
#else
      v->domain = 0;
#endif
      v->constraints = variable->constraints;
      v->nconstraints = variable->nconstraints;
      v->nconnections = variable->nconnections;
      v->epoch = 0;
      v->assigned = false;
      v->flags = 0;
    }

  return v;
}
#endif /* SPLITGO */

#ifndef USE_STORE
void _fd_var_copy_domain(fd_int to, fd_int from)
{
  if (DOMAIN(to))
    _fd_free_value(DOMAIN(to));

  DOMAIN(to) = _fd_val_clone(DOMAIN(from));
}

void _fd_var_copy_domains(fd_int to[], fd_int from[])
{
  int i;

  for (i = 0; i < fd_variables_count; ++i)
    _fd_val_copy(DOMAIN_REF(to[i]), DOMAIN(from[i]));
}
#endif /* USE_STORE */

/* Add the CONSTRAINT to the VARIABLE's constraints. */
void _fd_var_add_constraint(fd_int variable, fd_constraint constraint)
{
  // first make sure there is room for one more constraint
  /* initially make room for 4 constraints; everytime the number of
     constraints reaches a power of 2 (not less than 4), double the
     size of the array */
  if (variable->nconstraints == 0)
    variable->constraints = malloc(4 * sizeof(*variable->constraints)); // XXX
  else
    {
      // a variable may appear more than once in some constraints
      // check if this is the case
      if (variable->constraints[variable->nconstraints - 1] ==
	    _fd_constraint_count - 1)
	{
	  variable->nconnections--;

	  return;
	}

      if (variable->nconstraints >= 4 &&
	  variable->nconstraints ==
	    (variable->nconstraints & -variable->nconstraints))
	variable->constraints =
	  realloc(variable->constraints,
		  2 * variable->nconstraints * sizeof(*variable->constraints));
    }

  // then add the constraint
  variable->constraints[variable->nconstraints] = _fd_constraint_count - 1; // XXX
  variable->nconstraints++;

  // update the number of connections of the variable
  variable->nconnections += constraint->nvariables - 1;
}

#ifndef fd_domain_empty // XXX: ???
/* Check if VARIABLE's domain is empty. */
int fd_domain_empty(fd_int variable)
{
  return _fd_val_empty(DOMAIN(variable));
}
#endif

/* Check if VARIABLE's domain is a singleton. If it is, store the
   value in the address pointed to by VALUE (if any). */
int fd_var_single(fd_int variable, int *value)
{
  return _fd_val_single(DOMAIN(variable), value);
}

/* Return the value assigned to VARIABLE. */
int fd_var_value(fd_int variable)
{
#ifndef USE_VALUE
  int value;

#ifndef NDEBUG
  assert( _fd_val_single(DOMAIN(variable), &value) );
#else
  _fd_val_single(DOMAIN(variable), &value);
#endif

  return value;
#else /* USE_VALUE */
#ifndef COMPACT_DOMAINS
  assert(DOMAIN(variable)->kind == FD_SINGLETON && DOMAIN(variable)->next == 0
	 && DOMAIN(variable)->value.value == variable->value);
#elif defined(INLINE_DOMAINS)
  assert(DOMAIN(variable) == ((unsigned) 0x80000000 >> variable->value));
#else
  assert(*DOMAIN(variable) == ((unsigned) 0x80000000 >> variable->value));
#endif

  return variable->value;
#endif /* USE_VALUE */
}

void _fd_revise_connected(fd_constraint constraint, fd_int variable)
{
#ifdef REVISION_IS_VAR
  _fd_add_new_revision(variable);
#else
  _fd_add_new_revision(variable, constraint);
#endif
}

/* print variable domain */
void fd_print(fd_int variable)
{
  _fd_val_print(DOMAIN(variable));
}

/* print variable domain + \n */
void fd_println(fd_int variable)
{
  fd_print(variable);
  putchar('\n');
}

// print all variables domains (and their epoch)
void _fd_print()
{
  int i;

  for (i = 0; i < fd_variables_count; ++i)
    {
      fd_print(_fd_variables[i]);
      printf("\t(%d)\n", _fd_variables[i]->epoch);
    }
}

// print all variables domains (and their epoch) on a single line
void _fd_cprint()
{
  int i;

  for (i = 0; i < fd_variables_count; ++i)
    {
      fd_print(_fd_variables[i]);
      putchar(' '); //printf("/%d ", _fd_variables[i]->epoch);
    }

  putchar('\n');
}

void _fd_gprint()
{
  int i, value;

  for (i = 0; i < fd_variables_count; ++i)
    {
      i % 9 == 0 ? putchar('\n') : 0;
      _fd_val_single(DOMAIN(_fd_variables[i]), &value);
      printf("%d ", value);
    }

  putchar('\n');
}

/* wrappers for functions dealing directly with the domains */

int _fd_var_max(fd_int variable)
{
  return _fd_val_max(DOMAIN(variable));
}

int _fd_var_min(fd_int variable)
{
  return _fd_val_min(DOMAIN(variable));
}

int _fd_var_del_ge(int value, fd_int variable)
{
//  _fd_var_save(variable);

  return _fd_val_del_ge(value, DOMAIN_REF(variable));
}

int _fd_var_del_gt(int value, fd_int variable)
{
//  _fd_var_save(variable);

  return _fd_val_del_gt(value, DOMAIN_REF(variable));
}

int _fd_var_del_le(int value, fd_int variable)
{
//  _fd_var_save(variable);

  return _fd_val_del_le(value, DOMAIN_REF(variable));
}

int _fd_var_del_lt(int value, fd_int variable)
{
//  _fd_var_save(variable);

  return _fd_val_del_lt(value, DOMAIN_REF(variable));
}

int _fd_var_del_val(int value, fd_int variable)
{
//  _fd_var_save(variable);

  return _fd_val_del_val(value, DOMAIN_REF(variable));
}

int _fd_var_del_other(fd_int variable, int value)
{
//  _fd_var_save(variable);

  return _fd_val_del_other(DOMAIN_REF(variable), value);
}

int _fd_var_intersect(fd_int variable1, fd_int variable2)
{
//  _fd_var_save(variable1);

  return _fd_val_intersect(DOMAIN_REF(variable1), DOMAIN(variable2));
}

int _fd_var_contains_val(fd_int variable, int value)
{
  return _fd_val_contains_val(DOMAIN(variable), value);
}

// XXX: only used by exactly-*?
void _fd_var_set_value(fd_int variable, int value)
{
  _fd_val_set_value(DOMAIN_REF(variable), value);
}

// SEARCH

/* select the variables which are candidate to be assigned */
void fd_label(fd_int variables[], int n)
{
  if (fd__label_vars)
    fd__fatal("fd_label() can only be called once");

  fd__label_vars = malloc(n * sizeof(*fd__label_vars));	// XXX: NULL
  fd__label_vars_count = n;

  memcpy(fd__label_vars, variables, n * sizeof(*fd__label_vars));
}

// XXX: variables addresses change when packing; reflect that on the
//	labelled variables
static void relocate_label_vars()
{
  int i;

  for (i = 0; i < fd__label_vars_count; ++i)
    fd__label_vars[i] = _fd_variables[fd__label_vars[i]->index];
}

#ifndef ASSIGNED_AFTER
// assigned variables should come before non-assigned ones, and
// relative order between assigned variables doesn't matter
#define cmp_var_assigned(a, b)    			\
  do    						\
    {    						\
      if (fd_var_single(a, NULL))    			\
	return -1;    					\
    							\
      if (fd_var_single(b, NULL))    			\
	return 1;    					\
    }    						\
  while (0);
#else
// assigned variables should come after non-assigned ones, and
// relative order between assigned variables doesn't matter
#define cmp_var_assigned(a, b)    			\
  do    						\
    {    						\
      if (fd_var_single(a, NULL))    			\
	return fd_var_single(b, NULL) ? -1 : 1;		\
    							\
      if (fd_var_single(b, NULL))    			\
	return -1;    					\
    }    						\
  while (0);
#endif

// variables with smaller domains come before variables with greater
int fd__cmp_var_size(fd_int a, fd_int b)
{
  cmp_var_assigned(a, b);

  return _fd_val_size(DOMAIN(a)) - _fd_val_size(DOMAIN(b));
}

// variables involved in more constraints come before variables
// involved in less
int fd__cmp_var_constraints(fd_int a, fd_int b)
{
  cmp_var_assigned(a, b);

  return b->nconstraints - a->nconstraints;
}

// variables involved in more constraints come before variables
// involved in less; in case of a tie, variables with smaller domains
// come before variables with greater
int fd__cmp_var_size_degree(fd_int a, fd_int b)
{
  cmp_var_assigned(a, b);

  if (a->nconstraints != b ->nconstraints)
    return b->nconstraints - a->nconstraints;

  return _fd_val_size(DOMAIN(a)) - _fd_val_size(DOMAIN(b));
}

// variables connected to more variables come before variables
// connected to less
int fd__cmp_var_connections(fd_int a, fd_int b)
{
  int ac, bc;

  cmp_var_assigned(a, b);

  return b->nconnections - a->nconnections;
}

// variables with smaller minimum value come before variables with
// greater
int fd__cmp_var_min(fd_int a, fd_int b)
{
  cmp_var_assigned(a, b);

  return _fd_var_min(a) - _fd_var_min(b);
}

// variables with greater maximum value come before variables with
// smaller
int fd__cmp_var_max(fd_int a, fd_int b)
{
  cmp_var_assigned(a, b);

  return _fd_var_max(b) - _fd_var_max(a);
}

int (*fd__cmp_variables)(fd_int, fd_int) = NULL;

// ascending stable merge
static void merge_vars(fd_int vs[], fd_int vt[], int f, int l,
		       int (*cmp)(fd_int, fd_int))
{
  int f0 = f, l0 = (f + l) / 2;
  int f1 = l0 + 1, l1 = l;

  while (f <= l && f0 <= l0 && f1 <= l1)
    vs[f++] = cmp(vt[f0], vt[f1]) < 1 ? vt[f0++] : vt[f1++];

  while (f0 <= l0)
    vs[f++] = vt[f0++];

  while (f1 <= l1)
    vs[f++] = vt[f1++];
}

static void merge_sort_vars(fd_int vs[], fd_int vt[], int f, int l,
			    int (*cmp)(fd_int, fd_int))
{
  if (f == l)
    return;

  merge_sort_vars(vt, vs, f, (f + l) / 2, cmp);
  merge_sort_vars(vt, vs, (f + l) / 2 + 1, l, cmp);
  merge_vars(vs, vt, f, l, cmp);
}

void fd__sort_variables(fd_int vars[], int nvars, int (*cmp)(fd_int, fd_int))
{
  fd_int *aux;

  aux = alloca(nvars * sizeof(*aux));
  memcpy(aux, vars, nvars * sizeof(*aux));

  merge_sort_vars(vars, aux, 0, nvars - 1, cmp);
}

void fd__sort_label_vars()
{
  fd_int *aux;

  if (!fd__cmp_variables)
    return;

  fd__sort_variables(fd__label_vars, fd__label_vars_count, fd__cmp_variables);
}

void fd__setup_label_vars()
{
  int i;

  assert(PACK_PROBLEM);		// XXX: variables addresses are shared

  if (!fd__label_vars)
    {
      fd__label_vars = malloc(fd_variables_count * sizeof(*fd__label_vars));
      memcpy(fd__label_vars, _fd_variables,
	     fd_variables_count * sizeof(*fd__label_vars));
      fd__label_vars_count = fd_variables_count;
    }
  else
    relocate_label_vars();

  fd__sort_label_vars();

  fd__var_labelled = calloc(fd_variables_count, sizeof(*fd__var_labelled)); // XXX: NULL

  for (i = 0; i < fd__label_vars_count; ++i)
    fd__var_labelled[fd__label_vars[i]->index] = true;
}

/* select the next variable to be instantiated (search) */
fd_int (*_fd_var_select2)(fd_int[]);

fd_int _fd_select_first_var(fd_int _fd_variables[])
{
  int i;

  for (i = 0; i < fd__label_vars_count; ++i)
    if (!fd_var_single(_fd_variables[i], NULL))
      {
	return _fd_variables[i];
      }

  return NULL;
}

fd_int _fd_select_first_fail(fd_int _fd_variables[])
{
  // select the first variable with the smallest domain
  fd_int variable = NULL;
  int i, domain_size, s;

  i = 0;
  while (i < fd__label_vars_count && fd_var_single(_fd_variables[i], NULL))
    ++i;

  if (i == fd__label_vars_count)
    return NULL;		// all variables' domains are singletons

  variable = _fd_variables[i++];
  domain_size = _fd_val_size(DOMAIN(variable));

  for (; i < fd__label_vars_count; ++i)
    if ((s = _fd_val_size(DOMAIN(_fd_variables[i]))) > 1 && s < domain_size)
      {
	variable = _fd_variables[i];
	domain_size = s;
      }

  return variable;
}

fd_int _fd_select_most_constrained(fd_int _fd_variables[])
{
  // select the first variable with the most constraints
  // XXX: should global constraints count as more than one?
  fd_int variable = NULL;
  int i, nconstraints;

  i = 0;
  while (i < fd__label_vars_count && fd_var_single(_fd_variables[i], NULL))
    ++i;

  if (i == fd__label_vars_count)
    return NULL;		// all variables' domains are singletons

  variable = _fd_variables[i++];
  nconstraints = variable->nconstraints;

  for (; i < fd__label_vars_count; ++i)
    if (_fd_variables[i]->nconstraints > nconstraints &&
	!fd_var_single(_fd_variables[i], NULL))
      {
	variable = _fd_variables[i];
	nconstraints = variable->nconstraints;
      }

  return variable;
}

fd_int _fd_select_size_degree(fd_int _fd_variables[])
{
  // select the first variable with the smallest domain size / constraints
  // (seen in Gecode)
  fd_int variable = NULL;
  double ratio;
  int i, s;

  i = 0;
  while (i < fd__label_vars_count && fd_var_single(_fd_variables[i], NULL))
    ++i;

  if (i == fd__label_vars_count)
    return NULL;		// all variables' domains are singletons

  variable = _fd_variables[i++];
  ratio = (double) _fd_val_size(DOMAIN(variable)) /
          (double) variable->nconstraints;

  for (; i < fd__label_vars_count; ++i)
    if ((s = _fd_val_size(DOMAIN(_fd_variables[i]))) > 1)
      {
	double r = (double) s / (double) _fd_variables[i]->nconstraints;

	if (r < ratio)
	  {
	    variable = _fd_variables[i];
	    ratio = r;
	  }
      }

  return variable;
}

fd_int _fd_select_most_connected(fd_int _fd_variables[])
{
  // select the first variable with the most connections
  fd_int variable = NULL;
  int i, j, connections;

  i = 0;
  while (i < fd__label_vars_count && fd_var_single(_fd_variables[i], NULL))
    ++i;

  if (i == fd__label_vars_count)
    return NULL;		// all variables' domains are singletons

  variable = _fd_variables[i++];
  connections = variable->nconnections;

  for (; i < fd__label_vars_count; ++i)
    if (!fd_var_single(_fd_variables[i], NULL))
      if (_fd_variables[i]->nconnections > connections)
	{
	  variable = _fd_variables[i];
	  connections = _fd_variables[i]->nconnections;
	}

  return variable;
}

fd_int _fd_select_random_var(fd_int _fd_variables[])
{
  fd_int *vs;
  int i, n;

  vs = alloca(fd__label_vars_count * sizeof(*vs)); // XXX: may be too big?

  for (i = n = 0; i < fd__label_vars_count; ++i)
    if (!fd_var_single(_fd_variables[i], NULL))
      vs[n++] = _fd_variables[i];

  return n ? vs[random() % n] : 0;
}

/* select the first variable with the smallest value in its domain */
fd_int _fd_select_min_value(fd_int _fd_variables[])
{
  fd_int variable = NULL;
  int i, k, min;

  i = 0;
  while (i < fd__label_vars_count && fd_var_single(_fd_variables[i], NULL))
    ++i;

  if (i == fd__label_vars_count)
    return NULL;		// all variables' domains are singletons

  variable = _fd_variables[i++];
  min = _fd_val_min(DOMAIN(variable));

  for (; i < fd__label_vars_count; ++i)
    if (!fd_var_single(_fd_variables[i], NULL) &&
	(k = _fd_val_min(DOMAIN(_fd_variables[i]))) < min)
      {
	variable = _fd_variables[i];
	min = k;
      }

  return variable;
}

/* select the first variable with the greatest value in its domain */
fd_int _fd_select_max_value(fd_int _fd_variables[])
{
  fd_int variable = NULL;
  int i, k, max;

  i = 0;
  while (i < fd__label_vars_count && fd_var_single(_fd_variables[i], NULL))
    ++i;

  if (i == fd__label_vars_count)
    return NULL;		// all variables' domains are singletons

  variable = _fd_variables[i++];
  max = _fd_val_max(DOMAIN(variable));

  for (; i < fd__label_vars_count; ++i)
    if (!fd_var_single(_fd_variables[i], NULL) &&
	(k = _fd_val_max(DOMAIN(_fd_variables[i]))) > max)
      {
	variable = _fd_variables[i];
	max = k;
      }

  return variable;
}

/* select the next variable to be instantiated (search) */
fd_int _fd_var_select()
{
  return _fd_var_select2(_fd_variables);
}