#ifndef _INTVECTOR_H_
#define _INTVECTOR_H_

/* Vectors of ints, represented as a pointer to an array of ints,
   the first of which is the vector length.  After being constructed,
   the length is not mutable.  Bounds checks are always performed.
*/

#include <iostream>
#include <cassert>
#include <cstring>
#include <string>
#include "llist.h"
#include "int2string.h"
#include <cmath>
#include "gputil.h"
#include <algorithm>
#include "using-std.h"

class intvector {
 public:
  /* Constructors & Destructor */
  intvector(int n, int *vals = NULL) {
    data = new int [n + 1];
    assert(data != NULL);
    data[0] = n;
    if (vals)
      memcpy((void *) (data + 1), (void *) vals, n * sizeof(int));
  }

  /* Make an intvector out of the data in l. */
  intvector(const llist<int> *l) {
    int n = l->size();
    data = new int [n + 1];
    data[0] = n;
    for (int i = 0; i < n; i++) {
      data[i + 1] = l->front();
      l = l->tail();
    }
  }

  ~intvector() {
    delete[] data;
  }

  /* Utils */
  inline size_t size() const { return data[0]; }

  inline int dot(intvector const *v) const {
    int n = size();
    assert(v->size() == (size_t) n);
    int sum = 0;
    while (n-- > 0)
      sum += (*this)[n] * (*v)[n];
    return sum;
  }

  inline double dot_double(intvector const *v) const {
    int n = size();
    assert(v->size() == (size_t) n);
    double sum = 0;
    while (n-- > 0)
      sum += (*this)[n] * (*v)[n];
    return sum;
  }

  intvector *copy() const {
    int n = size();
    intvector *result = new intvector(n, NULL);
    while (n-- > 0)
      (*result)[n] = (*this)[n];
    return result;
  }

  bool equals(intvector const *v) const {
    int n = size();
    assert(v->size() == (size_t) n);
    while (n-- > 0)
      if ((*this)[n] != (*v)[n])
	return false;
    return true;
  }

  /* Non-destructive. */
  intvector *plus(intvector const *v) const {
    return copy()->destructive_sum(v);
  }
  intvector *minus(intvector const *v) const {
    intvector *r, *tmp;
    r = plus(tmp = v->times(-1));
    delete tmp;
    return r;
  }
  intvector *times(intvector const *v) const {
    return copy()->destructive_product(v);
  }
  intvector *times(int k) const {
    return copy()->destructive_product(k);
  }

  llist<int> *to_list() const {
    int n = size();
    llist<int> *result = NULL;
    while (n-- >= 0)
      push(result, (*this)[n]);
    return result;
  }

  int first() const { return (*this)[0]; }
  int last() const { return (*this)[size() - 1]; }

  /* An intvector same as this but without last component.
     E.g., [3, 4] -> [3]. */
  intvector *chop_last() const {
    return new intvector(size() - 1, data + 1);
  }

  /* An intvector same as this but without first component.
     E.g., [3, 4] -> [4]. */
  intvector *chop_first() const {
    return new intvector(size() - 1, data + 2);
  }

  intvector *destructive_sum(intvector const *v) {
    int n = size();
    assert(v->size() == (size_t) n);
    while (n-- > 0)
      (*this)[n] += (*v)[n];
    return this;
  }

  intvector *destructive_product(int k) {
    int n = size();
    while (n-- > 0)
      (*this)[n] *= k;
    return this;
  }

  intvector *destructive_product(intvector const *v) {
    int n = size();
    assert(v->size() == (size_t) n);
    while (n-- > 0)
      (*this)[n] *= (*v)[n];
    return this;
  }

  /* Return index of first value that is not x.
     If all are x, return -1. */
  inline int find_not(int x) const {
    int n = size();
    for (int i = 0; i < n; i++)
      if ((*this)[i] != x)
	return i;
    return -1;
  }

  /* Return index of first value that is x.
     If all are not x, return -1. */
  inline int find(int x) const {
    int n = size();
    for (int i = 0; i < n; i++)
      if ((*this)[i] == x)
	return i;
    return -1;
  }

  inline int find_non_zero() const { return find_not(0); }
  inline bool contains(int x) const { return (find(x) >= 0); }


  int gcd() const;
  bool has_unit_gcd() const { return gcd() == 1; }
  intvector *approximate_with_unit_vector() const;
  bool lexicographically_precedes(intvector const *) const;
  double norm() const { return sqrt(dot_double(this)); }
  bool is_parallel(const intvector *v) const {
    assert(!is_zero() && !v->is_zero());
    return square(v->dot(this)) == abs(v->dot(v) * this->dot(this));
  }
  /* True iff this contains exactly one non-zero element. */
  bool is_axis_aligned() const {
    int n = size(), non_zeros = 0;
    while (n-- > 0)
      if ((*this)[n] != 0)
	if (++non_zeros > 1)
	  return false;
    return (non_zeros == 1);
  }
  bool is_zero() const {
    int n = size();
    while (n-- > 0)
      if ((*this)[n] != 0)
	return false;
    return true;
  }
  intvector *dreverse() {
   #ifdef __INTEL_COMPILER
    /* reverse requires swap, which may not be defined for int *  */
    int *front = data + 1;
    int *back = data + size();
    while (front < back) {
      int tmp = *front;
      *front = *back;
      *back = tmp;
      front++;
      back--;
    }
   #else
    std::reverse(data + 1, data + 1 + size());
   #endif
    return this;
  }
  intvector *reverse() const { return copy()->dreverse(); }

  /* Printing Utils */
  string to_string() const {
    string result("[");
    int n = size();
    for (int i = 0; i < n; i++) {
      if (i > 0)
	result += ", ";
      result += i2s(data[i + 1]);
    }
    return result + "]";
  }
  void print(ostream &o) {
    o << to_string();
  }
  void print() { print(cout); }

  /* Accessors */
  inline int & operator[](size_t i) {
    assert(i < size() && "Bounds checking error");
    return data[i + 1];
  }

  inline const int & operator[](size_t i) const {
    assert(i < size() && "Bounds checking error");
    return data[i + 1];
  }

 private:
  int *data;
};

intvector *multiple_with_min_length(intvector const *v, double l);
intvector *sum_intvectors(llist<intvector *> *l, int n = -1);
intvector *zero_vector(int n);
intvector *unit_vector(int i, int n);

int lexicographically_first(llist<intvector *> *l, llist<int> *c);
int lexicographically_last(llist<intvector *> *l, llist<int> *c);
int lexicographically_first(llist<intvector *> *l);
int lexicographically_last(llist<intvector *> *l);
intvector * excise_lexicographically_first(llist<intvector *> *&l);
intvector * excise_lexicographically_last(llist<intvector *> *&l);

void qsort_intvectors(intvector **a, int n);

string llist_intvector_to_string(llist<intvector *> *l);
string intvectors_to_string(intvector **a, size_t n);

#endif