#include "TilingPlane.h"
#include "pick_planes.h"
#include "rqueue.h"
#include "vecrqueue.h"
#include <map>
#include <set>
#include <utility>
#include "linalg.h"
#include "OrderingConstraint.h"

static int perserverance;
static int const default_perserverance = 500;

static map < Foreach *,
  map < llist<OrderingConstraint *> *, rqueue<TilingPlane *> * > > qplanes;

typedef pair< Foreach *, llist<OrderingConstraint *> * > constraints;
typedef pair< constraints *, int > constraints_giveup;
typedef pair< constraints_giveup *, int > constraints_giveup_count;

typedef map< int, llist< intvector * > * > map_int_to_intvectors;
typedef map< int, map_int_to_intvectors > map_int_int_to_intvectors;

static bool is_legal(constraints *a, intvector *n)
{
  Foreach *f = a->first;
  llist<OrderingConstraint *> *oc = a->second;
  return is_legal(f, oc, n);
}

bool is_legal(Foreach *f, llist<OrderingConstraint *> *oc, intvector *n)
{
  bool result = true;

  llist<TilingPlane *> *planes = f->planes;
  if (!n->has_unit_gcd() ||
      !is_linearly_indep(cons(new TilingPlane(n), planes)) ||
      some_oc_violated_by_generic_plane(f, oc, n))
    result = false;
  DBG(cout << "is_legal(..., " << n->to_string() << "): " << result << endl);
  return result;
}

/* Go through the list of all legal planes (according to a), sorted by
taxicab norm of the normal vector, and add up to n to q.
For each plane we look at, decrease giveup.  When giveup is 0 or
less, fail, by returning false.  If we don't fail, add the first n legal
planes to q and return true. */
static bool get_n_legal_planes(constraints *a, int n, int &giveup,
			       queue<TilingPlane *> *q)
{
  // Map from M to prefix of the list of all possible M dimensional vectors.
  static map_int_to_intvectors memo;

  Foreach *f = a->first;
  int arity = f->highest_arity_iteration_space();

  DPRINTLN("get_n_legal_planes() n = " + i2s(n) + ", arity = " + i2s(arity));

  /* Make sure we have an appropriate number of vectors to pick from */
  if (memo[arity] == NULL || ((int) memo[arity]->size()) < giveup) {
    if (memo[arity] != NULL) memo[arity]->free();
    rqueue<intvector *> *q = taxi(arity);
    memo[arity] = q->as_llist(giveup);
    delete q;
  }
  llist<intvector *> *l = memo[arity];
  while (giveup > 0) {
    if (is_legal(a, l->front())) {
      q->push(new TilingPlane(l->front()));
      if (--n == 0)
	return true;
    }
    giveup--;
    l = l->tail();
  }
  return false;
}

/* u is userdata.  q is the queue to which we add, if we want to.
   Return false if this function should not be called again (because
   we've run out of things to add). */
static bool pick_planes_(void *& u, queue<TilingPlane *> *q)
{
  constraints_giveup_count *c = (constraints_giveup_count *) u;
  int count = c->second;
  constraints_giveup *b = c->first;
  int &giveup = b->second;
  constraints *a = b->first;
  return get_n_legal_planes(a, count, giveup, q);
}

static void prepare_to_pick_planes(Foreach *f, llist<OrderingConstraint *> *oc,
				   int count)
{
  constraints *a = new constraints(f, oc);
  constraints_giveup *b = new constraints_giveup(a, perserverance);
  void *u = (void *) new constraints_giveup_count(b, count);
  qplanes[f][oc] = new rqueue<TilingPlane *>(pick_planes_, u);
}

/* Attempt to grab the nth item of the list l, counting from the back.
   (I.e., n=0 means the last item in l).  If l doesn't have enough
   items, add items to its front by popping them off q.  If we run dry
   then return false.  Otherwise, put result in p and return true. */
bool grab_plane(rqueue<TilingPlane *> * q, int n, TilingPlane *&p)
{
  llist<TilingPlane *> *l = NULL;
  int k = 0;
  while (n >= k) {
    if (q->empty()) return false;
    l = cons(q->pop(), l);
    k++;
  }
  /* k is the length of l */
  int skip = k - n - 1;
  llist<TilingPlane *> *w = l;
  while (skip-- > 0) {
    DBG(cout << "Skipping " << w->front()->n()->to_string() << endl);
    w = w->tail();
  }
  p = w->front();
  return true; 
}

/* Consider all planes sorted by taxicab distance of their normal
   vector from the 0 vector.  Remove those that are not legal or that
   have a normal that is a linear combination of elts of f->planes or that
   have a normal with non-unit GCD.  Select the nth of those that
   remain and put it in p.  Return true if successful, false if not
   successful.  We consider ourselves not successful if we have to
   look at greater than some user-specified number of planes.  */
bool pick_plane(Foreach *f, llist<OrderingConstraint *> *oc,
		int n, TilingPlane *&p)
{
  perserverance =
    get_parameter("Perserverance in selecting planes",
		  "Maximum number of planes to examine in searching for a tiling", NONNEG, default_perserverance);
  if (qplanes[f][oc] != NULL)
    delete qplanes[f][oc];
  prepare_to_pick_planes(f, oc, n + 1);
  return grab_plane(qplanes[f][oc], n, p);
}