/* rqueue of vectors of integers */

/* Main function of interest is taxi_upfrom(int dist, int arity),
   which returns an rqueue of all vectors with taxicab distance at least
   dist, sorted by dist.

   taxi(int arity) is equivalent to taxi_upfrom(0, arity).
*/

#include "rqueue.h"
#include "intvector.h"

static inline llist<int> * zeroes(int arity)
{
  llist<int> *result = NULL;
  while (arity-- > 0)
    result = cons(0, result);
  return result;
}

static inline llist< llist<int> * > * all_with_taxi_dist(int dist, int arity)
{
  if (dist == 0)
    return cons(zeroes(arity));
  assert(dist > 0);
  if (arity == 1)
    return cons(cons(dist), cons(cons(-dist)));
  assert(arity > 0);
  llist< llist<int> * > *result = NULL;
  for (int i = 0; i <= dist; i++) {
    llist< llist<int> * > *r =
      dreverse(all_with_taxi_dist(dist - i, arity - 1));
    while (r != NULL) {
      if (i != 0)
	result = cons(cons(-i, r->front()), result);
      result = cons(cons(i, r->front()), result);
      r = r->tail();
    }
  }
  return result;
}

/* Add to q all vectors of the given arity that have the given taxicab
   distance from the origin. */
static inline void add_taxi(int dist, int arity, queue<intvector *> *q)
{
  llist< llist<int> * > *l = all_with_taxi_dist(dist, arity);
  while (l != NULL) {
    q->push(new intvector(l->front()));
    l = l->tail();
  }
}

static inline bool taxi_upfrom_(void *&v, queue<intvector *> *q)
{
  pair< int, int > *p = (pair< int, int > *) v;
  add_taxi(p->first++, p->second, q);
  return true;
}

static inline rqueue<intvector *> * taxi_upfrom(int n, int arity)
{
  return new rqueue<intvector *>(&taxi_upfrom_,
				 (void *) new pair< int, int >(n, arity));
}

static inline rqueue<intvector *> * taxi(int arity)
{
  return taxi_upfrom(0, arity);
}