#include "linalg.h"
#include "intvector.h"
#include <cstdlib>

int intvector::gcd() const
{
  int n = size();
  int d0 = (*this)[0];
  if (n == 1)
    return (d0 >= 0) ? d0 : -d0;
  int g = d0;
  while (n > 1 && g != 1)
    g = ::positive_gcd(g, (*this)[--n]);
  return g;
}

/* Of all vectors that have length 1, return the one with maximal dot
   product with this. */
intvector *intvector::approximate_with_unit_vector() const
{
  int n = size();
  int m, p, i;
  for (i = 1, m = abs((*this)[p = 0]); i < n; i++)
    if (abs((*this)[i]) > m)
      m = abs((*this)[p = i]);
  /* m is the absolute value of the largest magnitude element of this.
     p is its position. */
  intvector *result = new intvector(n);
  for (i = 0; i < n; i++)
    result[i] = 0;
  result[p] = ((*this)[p] >= 0) ? 1 : -1;
  return result;
}

intvector *multiple_with_min_length(intvector const *v, double l)
{
  double n = v->norm();
  assert(n > 0);
  int q = std::max(1, (int) (l / n));
  do {
    intvector *result = v->times(q);
    if (result->norm() >= l)
      return result;
    delete result;
    q++;
  } while (true);
}

/* Unit vector of length n in the i direction.  i counts from 0. */
intvector *unit_vector(int i, int n)
{
  intvector *u = zero_vector(n);
  (*u)[i] = 1;
  return u;
}

intvector *zero_vector(int n)
{
  return (new intvector(n))->destructive_product(0);
}

intvector *sum_intvectors(llist<intvector *> *l, int n)
{
  assert(l != NULL || n > 0);
  if (l == NULL)
    return zero_vector(n);
  intvector *result = l->front()->copy();
  l = l->tail();
  while (l != NULL) {
    result->destructive_sum(l->front());
    l = l->tail();
  }
  return result;
}

bool intvector::lexicographically_precedes(intvector const *x) const
{
  size_t n = size();
  assert(x->size() == n);
  for (int i = 0; i < (int) n; i++)
    if ((*this)[i] < (*x)[i])
      return true;
    else if ((*this)[i] > (*x)[i])
      return false;
  return false;
}

/* Return the index of the lexicographically first intvector among the set
   { v | exists x in c such that v = (*l)[x] } */
int lexicographically_first(llist<intvector *> *l, llist<int> *c)
{
  assert(c != NULL);
  int result = c->front();
  c = c->tail();
  while (c != NULL) {
    if ((*l)[c->front()]->lexicographically_precedes((*l)[result]))
      result = c->front();
    c = c->tail();
  }
  return result;
}

/* Return the index of the lexicographically last intvector among the set
   { v | exists x in c such that v = (*l)[x] } */
int lexicographically_last(llist<intvector *> *l, llist<int> *c)
{
  assert(c != NULL);
  int result = c->front();
  c = c->tail();
  while (c != NULL) {
    if ((*l)[result]->lexicographically_precedes((*l)[c->front()]))
      result = c->front();
    c = c->tail();
  }
  return result;
}

/* Return the index of the lexicographically last intvector in l. */
int lexicographically_last(llist<intvector *> *l)
{
  int result = 0, i = l->size();
  assert(i > 0);
  while (--i >= 1)
    if ((*l)[result]->lexicographically_precedes((*l)[i]))
      result = i;
  return result;
}

/* Return the index of the lexicographically first intvector in l. */
int lexicographically_first(llist<intvector *> *l)
{
  int result = 0, i = l->size();
  assert(i > 0);
  while (--i >= 1)
    if ((*l)[i]->lexicographically_precedes((*l)[result]))
      result = i;
  return result;
}

/* Return the lexicographically first intvector in l, and remove it from l. */
intvector * excise_lexicographically_first(llist<intvector *> *&l)
{
  assert(l != NULL);
  int i = lexicographically_first(l);
  intvector *result = (*l)[i];
  l = l->excise(i);
  return result;
}

/* Return the lexicographically last intvector in l, and remove it from l. */
intvector * excise_lexicographically_last(llist<intvector *> *&l)
{
  assert(l != NULL);
  int i = lexicographically_last(l);
  intvector *result = (*l)[i];
  l = l->excise(i);
  return result;
}

static int intvector_compare(const void *a, const void *b)
{
  const intvector *x = * (intvector **) a;
  const intvector *y = * (intvector **) b;
  return (x->lexicographically_precedes(y) ? -1 :
	  (y->lexicographically_precedes(x) ? 1 : 0));
}

/* Quicksort an array of n pointers to intvectors.  Sort on lexicographic order of vectors. */
void qsort_intvectors(intvector **a, int n)
{
  qsort((void *) a, n, sizeof(intvector *), intvector_compare);
}

string llist_intvector_to_string(llist<intvector *> *l)
{
  string result("{");
  for (ListIterator<intvector *> i(l); !i.isDone(); i.next())
    result = result + ' ' + (*i)->to_string();
  return result + " }";
}

string intvectors_to_string(intvector **a, size_t n)
{
  string result("{");
  for (int i = 0; ((size_t) i) < n; i++)
    result = result + ' ' + a[i]->to_string();
  return result + " }";
}