#include "linalg.h" #include "intvector.h" #include 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 *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 *l, llist *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 *l, llist *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 *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 *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 *&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 *&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 *l) { string result("{"); for (ListIterator 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 + " }"; }