#include <string.h>

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

#ifndef COMPACT_DOMAINS
#error "only works with COMPACT_DOMAINS"
#endif

#ifndef USE_STORE
#error "must USE_STORE"
#endif

//#define MAX_AGENTS 256

//static fd_int *_fd_copies[MAX_AGENTS];

extern int tid; // XXX: team ID, just for debugging

/*
  Problem partitioning functions use the domains from `store' and save
  the N subproblems created in the STORES given in their 2nd argument.
*/
int (*fd__split_problem_f)(int n, _fd_store stores[]);
#ifdef SPLITGO_MPI
int (*fd__split_team_problem_f)(int n, _fd_store stores[]);
#endif

static int fd__split_eager(int n, _fd_store stores[])
{
  int np, minv, maxv;
  int v;

  np = 1;

  for (v = 0; v < fd__label_vars_count && np < n; v++)
    {
      int cp = np;
      int vi = fd__label_vars[v]->index;
      int p;

      for (p = 0; p < cp && np < n; ++p)
	{
	  fd_iterator iterator = _fd_val_iterator(DOMAIN(fd__label_vars[v]));
	  minv = _fd_val_next_element(iterator);

	  _fd_init_domain(SVALUE(stores[p][vi]), minv, minv);

	  while (_fd_val_has_next(iterator) && np < n)
	    {
	      int i = _fd_val_next_element(iterator);
	      int j;

	      for (j = 0; j < v; ++j)
		_fd_copy_value(SVALUE(stores[np][fd__label_vars[j]->index]),
			       SVALUE(stores[p][fd__label_vars[j]->index]));

	      _fd_init_domain(SVALUE(stores[np][vi]), i, i);

	      np++;
	    }

	  _fd_val_iterator_dispose(iterator);

	  // XXX: this reassigns a domain to the last variable assigned,
	  //      which is a waste (although it only does that once?)
	  if (np == n)
	    {
	      int value;

	      _fd_val_single(SVALUE(stores[np - 1][vi]), &value);
	      _fd_copy_value(SVALUE(stores[np - 1][vi]), DOMAIN(fd__label_vars[v]));
	      _fd_val_del_lt(value, &stores[np - 1][vi]); // XXX
	    }
	}

      for (; p < cp; ++p)
	_fd_copy_value(SVALUE(stores[p][vi]), DOMAIN(fd__label_vars[v]));
    }

  for (; v < fd__label_vars_count; ++v)
    {
      int vi = fd__label_vars[v]->index;
      int p;

      for (p = 0; p < n; ++p)
	_fd_copy_value(SVALUE(stores[p][vi]), DOMAIN(fd__label_vars[v]));
    }

  return np;
}

static int split_even(int n, _fd_store stores[], int first_var)
{
  int v, vi, p;
  int ds;
  int g;
  fd_iterator iterator;

  v = first_var;

  while (v < fd__label_vars_count &&
	 (ds = _fd_val_size(DOMAIN(fd__label_vars[v]))) == 1)
    {
      vi = fd__label_vars[v]->index;

      for (p = 0; p < n; ++p)
	_fd_copy_value(SVALUE(stores[p][vi]), DOMAIN(fd__label_vars[v]));

      ++v;
    }

  if (v == fd__label_vars_count)
    return 1;		// all domains are singletons

  if (ds >= n)
    {
      // divide the v-th variable domain between the n stores
      iterator = _fd_val_iterator(DOMAIN(fd__label_vars[v]));

      vi = fd__label_vars[v]->index;

      for (p = 0; p < n; ++p)
	{
	  // this is all maybe a little wasteful
	  int minv, maxv;
	  int i;

	  _fd_copy_value(SVALUE(stores[p][vi]), DOMAIN(fd__label_vars[v]));

	  minv = maxv = _fd_val_next_element(iterator);

	  // find the last element of the new domain
	  for (i = ds / n + (p >= n - ds % n); i > 1; --i)
	    maxv = _fd_val_next_element(iterator);

	  (void) _fd_val_del_lt(minv, (DOMAIN_REF_T()) &stores[p][vi]); // XXX
	  (void) _fd_val_del_gt(maxv, (DOMAIN_REF_T()) &stores[p][vi]); // XXX
	}

      // copy the domains of the remaining variables to all the stores
      for (v++; v < fd__label_vars_count; v++)
	{
	  vi = fd__label_vars[v]->index;

	  for (p = 0; p < n; ++p)
	    _fd_copy_value(SVALUE(stores[p][vi]), DOMAIN(fd__label_vars[v]));
	}

      return n;
    }

  /*
    the domain of the variable has less than n elements, some stores
    will have to share a value:

      - the first n % ds elements will be shared by n / ds + 1 stores
      - the remaining ds - n % ds elements will be shared by n / ds
        stores
  */

  iterator = _fd_val_iterator(DOMAIN(fd__label_vars[v]));
  vi = fd__label_vars[v]->index;

  p = 0;
  for (g = 0; g < ds; ++g)
    {
      int e = _fd_val_next_element(iterator);
      int gs = n / ds + (g < n % ds);
      int j;

      for (j = 0; j < gs; ++j)
	_fd_init_domain(SVALUE(stores[p + j][vi]), e, e);

      // count the stores really created
      p += split_even(gs, stores + p, v + 1);
    }

  return p;
}

static int fd__split_even(int n, _fd_store stores[])
{
  return split_even(n, stores, 0);
}

/*
  Split the store evenly on the first variable whose domain has at
  least N elements. If no such variable exists, use split-even.
*/
static int fd__split_even_one(int n, _fd_store stores[])
{
  int v, vi, p;
  int ds;
  fd_iterator iterator;

  for (v = 0; v < fd__label_vars_count; ++v)
    {
      // see if the v-th variable domain can be split n-ways
      if ((ds = _fd_val_size(DOMAIN(fd__label_vars[v]))) >= n)
	break;

      // as it can't, copy it to all the stores
      vi = fd__label_vars[v]->index;
      for (p = 0; p < n; ++p)
	_fd_copy_value(SVALUE(stores[p][vi]), DOMAIN(fd__label_vars[v]));
    }

  if (v == fd__label_vars_count)
    {
      _fd_debug("[%d] cannot split %d-ways evenly, resorting to even "
		"splitting\n", tid, n);

      return fd__split_even(n, stores);
    }

  // divide the v-th variable domain between the n stores
  iterator = _fd_val_iterator(DOMAIN(fd__label_vars[v]));

  for (p = 0; p < n; ++p)
    {
      // this is all maybe a little wasteful
      int minv, maxv;
      int i;

      vi = fd__label_vars[v]->index;

      _fd_copy_value(SVALUE(stores[p][vi]), DOMAIN(fd__label_vars[v]));

      minv = maxv = _fd_val_next_element(iterator);

      // find the last element of the new domain
      for (i = ds / n + (p >= n - ds % n); i > 1; --i)
	maxv = _fd_val_next_element(iterator);

      (void) _fd_val_del_lt(minv, (DOMAIN_REF_T()) &stores[p][vi]); // XXX
      (void) _fd_val_del_gt(maxv, (DOMAIN_REF_T()) &stores[p][vi]); // XXX
    }

  // copy the domains of the remaining variables to all the stores
  for (v++; v < fd__label_vars_count; v++)
    {
      vi = fd__label_vars[v]->index;

      for (p = 0; p < n; ++p)
	_fd_copy_value(SVALUE(stores[p][vi]), DOMAIN(fd__label_vars[v]));
    }

  return n;
}

int fd__split_problem(int n, _fd_store stores[],
		      int (*splitter)(int, _fd_store[]))
{
  int parts;
  int v, p;

#ifdef DEBUG_SPLITTING
  _fd_output("before splitting: "); _fd_cprint3(store);
#endif

  parts = splitter(n, stores);

  // copy the domains of the non-labelled variables to the sub-search
  // spaces
  if (fd__label_vars_count != fd_variables_count)
    for (v = 0; v < fd_variables_count; ++v)
      if (!fd__var_labelled[v])
	for (p = 0; p < parts; ++p)
	  _fd_copy_value(SVALUE(stores[p][v]), DOMAIN(_fd_variables[v]));

#ifdef DEBUG_SPLITTING
  _fd_output("split into %d out of %d stores\n", np, n);
  for (p = 0; p < n; ++p)
    _fd_output("store %d: ", p), _fd_cprint3(stores[p]);
#endif

  return parts;
}

void fd__init_splitgo(int *argc, char *argv[])
{
  int args = *argc;
  int i, j;

  fd__split_problem_f = fd__split_eager;
#ifdef SPLITGO_MPI
  fd__split_team_problem_f = 0;
#endif

  for (i = j = 1; i < args; i++)
    if (!strcmp(argv[i], "--split-even"))
      fd__split_problem_f = fd__split_even;
    else if (!strcmp(argv[i], "--split-even1"))
      fd__split_problem_f = fd__split_even_one;
    else if (!strcmp(argv[i], "--split-eager"))
      fd__split_problem_f = fd__split_eager;
#ifdef SPLITGO_MPI
    else if (!strcmp(argv[i], "--team-split-even"))
      fd__split_team_problem_f = fd__split_even;
    else if (!strcmp(argv[i], "--team-split-even1"))
      fd__split_team_problem_f = fd__split_even_one;
    else if (!strcmp(argv[i], "--team-split-eager"))
      fd__split_team_problem_f = fd__split_eager;
#endif
    else
      argv[j++] = argv[i];

  *argc = j;

#ifdef SPLITGO_MPI
  if (!fd__split_team_problem_f)
    fd__split_team_problem_f = fd__split_problem_f;
#endif
}