#ifdef USE_VALUE
#error "does not work with USE_VALUE (yet)"
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>	// for sysconf()
#include <pthread.h>

#include <assert.h>

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

#include "util.h"

#if STEAL_WORK > 0
#include <time.h>
#endif

static int _fd_dsearch_(fd_int[]);  // XXX

#ifdef STORE_LIST
#error "STORE_LIST deprecated"
#endif

static __thread int agent;

static int nagents;	// how many agents there are

// says whether we are counting or looking for solutions
int _fd_counting_solutions;

#ifdef NEW_ENTRANCE
#  if STEAL_WORK < 1
#    error "NEW_ENTRANCE only makes sense with STEAL_WORK"
#  else
static pthread_spinlock_t entrance_lock;
static volatile int agents_searching = 0, agents_failed = 0;
#  endif
#endif

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

#include "pool.c"

void _fd_epoch_forward()
{
}

void _fd_epoch_rewind()
{
  fd__constraint_data_reset();
}

int _fd_dsearch(fd_int variables[], int agent_no)
{
#if STEAL_WORK > 0
  struct timespec tsettle = { 0, 1000000 }; // 1ms
#ifdef NEW_ENTRANCE
  bool failed_initially = false;
#endif
#endif

  agent = agent_no;

#if defined(NEW_ENTRANCE) && defined(DEBUG_SPLITGO)
  fd__debug("[%d.%d] agents_searching = %d, agents_failed = %d\n", tid, agent, agents_searching, agents_failed);
#endif

  _fd_init_local_depository();

#if DEBUG_SPLITGO > 1
  fd__output("[%d.%d] ", tid, agent); _fd_cprint2(variables);
#endif

  if (_fd_filter_domains() == FD_NOSOLUTION)
    {
      fd_int variable = NULL;

      fd__trace("[%d.%d] failed before beginning\n", tid, agent);

#if STEAL_WORK > 0
#ifdef NEW_ENTRANCE
      failed_initially = true;

      pthread_spin_lock(&entrance_lock);
      ++agents_failed;
      pthread_spin_unlock(&entrance_lock);

      while (agents_searching == 0 && agents_failed < nagents)
	;

      if (agents_searching == 0)
	return FD_NOSOLUTION;
#endif /* NEW_ENTRANCE */

#if RANDOM_VICTIM >= 2	// XXX: to check if this is needed/useful
      // give the other agents time to start searching
      nanosleep(&tsettle, NULL);
#endif

      do
	{
	  if (!_fd_steal_store(store, &variable, agent_no, 7))
	    {
	      fd__trace("[%d.%d] giving up\n", tid, agent);

	      return FD_NOSOLUTION;
	    }

	  fd__constraint_data_reset();	// XXX: this doesn't belong here!
	}
      while (_fd_revise_wrt_variable(variable) == FD_NOSOLUTION);
#else  /* STEAL_WORK > 0 */
      return FD_NOSOLUTION;
#endif /* STEAL_WORK > 0 */
    }

#if DEBUG_SPLITGO > 1
  fd__output("[%d.%d] ", tid, agent); _fd_cprint2(variables);
#endif

#ifdef NEW_ENTRANCE
  pthread_spin_lock(&entrance_lock);
  if (failed_initially)
    --agents_failed;
  ++agents_searching;
  pthread_spin_unlock(&entrance_lock);
#endif

  fd__trace("[%d.%d] about to start searching\n", tid, agent);

  return _fd_dsearch_(variables);
}

static int _fd_dsearch_(fd_int _fd_variables[])
{
#ifndef STORE_IN_POOL
  _fd_store alt_store;
#endif
  fd_int variable;
  int instantiations = 0, backtrack = 0;

#ifdef DEBUG_SEARCH
  printf("* before search\n"); _fd_cprint2(_fd_variables);
#endif

  // start by selecting a variable
  while (variable = _fd_var_select2(fd__label_vars))
    {
      // clone store
      _fd_start_saving_store(&alt_store);

      // split domain
      _fd_val_split(DOMAIN_REF(variable),
		    (DOMAIN_REF_T()) (alt_store + variable->index)); // XXX

      _fd_epoch_forward();
      instantiations++;
#ifdef DEBUG_PROGRESS
      if (instantiations % 100000 == 0)
	fd__debug("[%d.%d] still alive (%d stores)\n", tid, agent,
		  next_split_index - base_split_index);
#endif

#ifndef INLINE_DOMAINS
      assert(!_fd_val_empty((DOMAIN_REF_T()) (alt_store + variable->index)));
#else
      assert(!_fd_val_empty(alt_store[variable->index]));
#endif

      _fd_end_saving_store(variable);

      while (_fd_revise_wrt_variable(variable) == FD_NOSOLUTION)
	{
#ifdef DEBUG_SEARCH
	  printf("* fail\n"); _fd_cprint2(_fd_variables);
#endif

	  // check whether this thread has been cancelled
	  // XXX: is there a better place to put this?
	  if (!_fd_counting_solutions)
	    pthread_testcancel();

	  _fd_epoch_rewind();

	  do
	    {
	      // try to ``restore'' the store
	      if (!_fd_restore_store(&variable))
		{
		  if (!_fd_counting_solutions)
		    {
		      fd__trace("[%d.%d] performed %d instantiations and %d backtracks\n",
				tid, agent, instantiations, backtrack);

		      _fd_statistics_pool();
		    }

		  return FD_NOSOLUTION;
		}

	      backtrack++;
	    }
	  while (_fd_optimising && fd__bound_and_revise() == FD_NOSOLUTION);

	  if (_fd_optimising && variable == _fd_bound_variable())
	    break;

	  if (variable && !fd_var_single(variable, NULL))
	    break;
	}
    }

#ifdef DEBUG_SEARCH
  printf("* succeed\n"); _fd_cprint2(_fd_variables);
#endif

  if (!_fd_counting_solutions)
    {
      fd__trace("[%d.%d] performed %d instantiations and %d backtracks\n", tid,
		agent, instantiations, backtrack);

      fd__trace("[%d.%d] %d stores in store\n", tid, agent, next_split_index - base_split_index);

      _fd_statistics_pool();
    }

#ifdef STORE_IN_POOL
  memcpy(main_store, store, STORE_SIZE);
#endif

  return FD_OK;	// found a solution: all domains are singletons
}

int _fd_dsearch_again(fd_int _fd_variables[])
{
  fd_int variable;

  do
    {
      // try to restore the state to the previous store
      _fd_epoch_rewind();

      if (!_fd_restore_store(&variable))
	return FD_NOSOLUTION;
    }
  while (// force the propagation of the new bound when optimising
	 _fd_optimising && fd__bound_and_revise() == FD_NOSOLUTION ||
	 (!_fd_optimising || variable != _fd_bound_variable()) &&
	 (!variable || fd_var_single(variable, NULL)) &&
	 _fd_revise_wrt_variable(variable) == FD_NOSOLUTION);

  return _fd_dsearch_(_fd_variables);
}

unsigned long long _fd_count_solutions(fd_int variables[], int agent_no)
{
  unsigned long long solutions = 0;

  if (_fd_dsearch(variables, agent_no) == FD_OK)
    {
      solutions = 1;

      while (_fd_dsearch_again(variables) == FD_OK)
	solutions++;
    }

  _fd_statistics_pool();

  return solutions;
}