1 // vec.h: declaration of integer vector classes
2 //////////////////////////////////////////////////////////////////////////
3 //
4 // Copyright 1990-2012 John Cremona
5 //
6 // This file is part of the eclib package.
7 //
8 // eclib is free software; you can redistribute it and/or modify it
9 // under the terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 2 of the License, or (at your
11 // option) any later version.
12 //
13 // eclib is distributed in the hope that it will be useful, but WITHOUT
14 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 // for more details.
17 //
18 // You should have received a copy of the GNU General Public License
19 // along with eclib; if not, write to the Free Software Foundation,
20 // Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
21 //
22 //////////////////////////////////////////////////////////////////////////
23
24 // Not to be included directly by user: use vector.h which defines
25 // _ECLIB_VECTOR_H and includes this twice
26 //
27
28 class svec;
29 class subspace;
30
31 class vec;
32 vec iota(scalar n); // (1,2,...,n)
33 mat restrict_mat(const mat& m, const subspace& s, int cr=0);
34 mat prestrict(const mat& m, const subspace& s, scalar pr, int cr=0);
35
36 class vec {
37 friend class svec;
38 friend class smat;
39 friend class smat_elim;
40 friend class vec_m;
41 friend class mat;
42 friend class subspace;
43 public:
44 // constructors
45 vec(long n=0);
46 vec(long n, scalar* arr);
47 vec(const vec&); // copy constructor
48 ~vec(); // destructor
49 // member functions & operators
50 void init(long n=0); // (re)-initializes
51 vec& operator=(const vec&); // assignment
52 scalar& operator[](long i) const; // the i'th component
53 vec& operator+=(const vec&);
54 void add_row(const mat&m, int i);
55 void addmodp(const vec&, scalar);
56 vec& operator-=(const vec&);
57 void sub_row(const mat&m, int i);
58 vec& operator*=(scalar);
59 vec& operator/=(scalar);
60 vec slice(long,long=-1) const; // returns subvec
61 vec operator[](const vec&) const; // subscript composition
62 void set(long i, scalar x); // sets v[i]=x
63 void add(long i, scalar x); // v[i]+=x
64 void add_modp(long i, scalar x, scalar p); // v[i]+=x mod p
65 scalar sub(long i) const; // same as v[i] (no ref)
get_entries()66 const scalar* get_entries()const {return entries;}
67 // non-member (friend) functions and operators
68 friend long dim(const vec&); // the dimension
69 friend scalar operator*(const vec&, const vec&); // dot product
70 friend scalar operator*(const svec&, const vec&);
71 friend vec operator*(const mat& m, const vec& v);
72 friend int operator==(const vec&, const vec&);
73 friend int operator!=(const vec&, const vec&);
74 friend int trivial(const vec&); // v==zerovec?
75 // add/sub row i of mat to v (implemented in mat.cc)
76 friend void add_row_to_vec(vec& v, const mat& m, long i);
77 friend void sub_row_to_vec(vec& v, const mat& m, long i);
78 friend ostream& operator<< (ostream&s, const vec&);
79 friend istream& operator>> (istream&s, vec&);
80 friend vec iota(scalar n); // (1,2,...,n)
81 friend scalar vecgcd(const vec&);
82 friend void swapvec(vec& v, vec& w);
83 friend int member(scalar a, const vec& v);//tests if a=v[i] for some i
84 friend mat restrict_mat(const mat& m, const subspace& s, int cr);
85 friend mat_m restrict_mat(const mat_m& m, const msubspace& s);
86 friend mat prestrict(const mat& m, const subspace& s, scalar pr, int cr);
87 friend mat_m prestrict(const mat_m& m, const msubspace& s, const bigint& pr);
88 friend scalar dotmodp(const vec& v1, const vec& v2, scalar pr);
89
90 // Implementation
91 private:
92 long d;
93 scalar * entries;
94 };
95
96 // Declaration of non-member, non-friend functions
97
98 vec operator+(const vec&); // unary
99 vec operator-(const vec&); // unary
100 vec operator+(const vec&, const vec&);
101 vec addmodp(const vec&, const vec&, scalar);
102 vec operator-(const vec&, const vec&);
103 inline vec operator*(scalar, const vec&); // componentwise
104 vec operator/(const vec&, scalar); // componentwise
105 void makeprimitive(vec& v);
106 void elim(const vec& a, vec& b, long pos);
107 void elim1(const vec& a, vec& b, long pos);
108 void elim2(const vec& a, vec& b, long pos, scalar lastpivot);
109 vec reverse(vec& order);
110 vec express(const vec& v, const vec& v1, const vec& v2);
111 int lift(const vec& v, scalar pr, vec& ans); //lifts a mod-p vector to a rational
112 //and scales to a primitive vec in Z. Returns success flag
113
114 // inline function definitions
115
dim(const vec & v)116 inline long dim(const vec& v) {return v.d;}
117
118 inline int operator!=(const vec& v, const vec& w) { return !(v==w);}
119
120 inline vec operator+(const vec& v) { return v;}
121
122 inline vec operator-(const vec& v) { return (-1)*v;}
123
124 inline vec operator+(const vec& v1, const vec& v2)
125 { vec ans(v1); ans+=v2; return ans;}
126
addmodp(const vec & v1,const vec & v2,scalar pr)127 inline vec addmodp(const vec& v1, const vec& v2, scalar pr)
128 { vec ans(v1); ans.addmodp(v2,pr); return ans;}
129
130 inline vec operator-(const vec& v1, const vec& v2)
131 { vec ans(v1); ans-=v2; return ans;}
132
133 inline vec operator*(scalar scal, const vec& v)
134 { vec ans(v); ans*=scal; return ans;}
135
136 inline vec operator/(const vec& v, scalar scal)
137 { vec ans(v); ans/=scal; return ans;}
138
makeprimitive(vec & v)139 inline void makeprimitive(vec& v)
140 { scalar g=vecgcd(v); if (g>1) v/=g;}
141
elim(const vec & a,vec & b,long pos)142 inline void elim(const vec& a, vec& b, long pos)
143 { (b*=a[pos])-=(b[pos]*a);}
144
elim1(const vec & a,vec & b,long pos)145 inline void elim1(const vec& a, vec& b, long pos)
146 { (b*=a[pos])-=(b[pos]*a); makeprimitive(b);}
147
elim2(const vec & a,vec & b,long pos,scalar lastpivot)148 inline void elim2(const vec& a, vec& b, long pos, scalar lastpivot)
149 { ((b*=a[pos])-=(b[pos]*a))/=lastpivot;}
150
151