1 | |
---|
2 | |
---|
3 | /**************************************************************************\ |
---|
4 | |
---|
5 | MODULE: vector |
---|
6 | |
---|
7 | SUMMARY: |
---|
8 | |
---|
9 | Macros are defined providing template-like classes for dynamic-sized |
---|
10 | arrays. |
---|
11 | |
---|
12 | The macro NTL_vector_decl(T,vec_T) declares a class vec_T, whose |
---|
13 | implementation can be instantiated with NTL_vector_impl(T,vec_T). It is |
---|
14 | presumed that the underlying type have a public default constructor, copy |
---|
15 | constructor, assignment operator, and a destructor (this is |
---|
16 | normally the case for most types). |
---|
17 | |
---|
18 | Note that the type T must be a type name (you'll need to make |
---|
19 | a typedef for the type if this is not the case). |
---|
20 | |
---|
21 | If the type T supports I/O operator << and >>, then vec_T can be |
---|
22 | made to support these operators as well using NTL_io_vector_decl(T,vec_T) and |
---|
23 | NTL_io_vector_impl(T,vec_T). |
---|
24 | |
---|
25 | The same goes for equality operators == and != using |
---|
26 | NTL_eq_vector_decl(T,vec_T) and NTL_eq_vector_impl(T,vec_T). |
---|
27 | |
---|
28 | The declaration |
---|
29 | |
---|
30 | vec_T v; |
---|
31 | |
---|
32 | creates a zero-length vector. To grow this vector to length n, |
---|
33 | execute |
---|
34 | |
---|
35 | v.SetLength(n) |
---|
36 | |
---|
37 | This causes space to be allocated for (at least) n elements, and also |
---|
38 | causes the delault constructor for T to be called to initialize these |
---|
39 | elements. |
---|
40 | |
---|
41 | The current length of a vector is available as v.length(). |
---|
42 | |
---|
43 | The i-th vector element (counting from 0) is accessed as v[i]. If the |
---|
44 | macro NTL_RANGE_CHECK is defined, code is emitted to test if 0 <= i < |
---|
45 | v.length(). This check is not performed by default. |
---|
46 | |
---|
47 | For old-time FORTRAN programmers, the i-th vector element (counting |
---|
48 | from 1) is accessed as v(i). |
---|
49 | |
---|
50 | Let n = v.length(). Calling v.SetLength(m) with m <= n sets the |
---|
51 | current length of v to m (but does not call any destructors or free |
---|
52 | any space). Calling v.SetLength(m) with m > n will allocate space and |
---|
53 | initialize as necessary, but will leave the values of the already |
---|
54 | allocated elements unchanged (although their addresses may change). |
---|
55 | Initializations are performed using T's default constructor. |
---|
56 | |
---|
57 | v.MaxLength() is the largest value of n for which v.SetLength(n) was invoked, |
---|
58 | and is equal to the number of entries that have been initialized. |
---|
59 | v.SetMaxLength(n) will allocate space for and |
---|
60 | initialize up to n elements, without changing v.length(). |
---|
61 | |
---|
62 | When v's destructor is called, all constructed elements will be |
---|
63 | destructed, and all space will be relinquished. |
---|
64 | |
---|
65 | Space is managed using malloc, realloc, and free. When a vector is |
---|
66 | grown, a bit more space may be allocated than was requested for |
---|
67 | efficiency reasons. |
---|
68 | |
---|
69 | Note that when a vector is grown, the space is reallocated using |
---|
70 | realloc, and thus the addresses of vector elements may change, |
---|
71 | possibly creating dangling references to vector elements. One has to |
---|
72 | be especially careful of this when using vectors passed as reference |
---|
73 | parameters that may alias one another. |
---|
74 | |
---|
75 | Because realloc is used to grow a vector, the objects stored |
---|
76 | in a vector should be "relocatable"---that is, they shouldn't care |
---|
77 | what their actual address is, which may change over time. |
---|
78 | Most reasonable objects satisfy this constraint. |
---|
79 | |
---|
80 | v.allocated() is the number of elements which have been allocated, |
---|
81 | which may be more than the number elements initialized. |
---|
82 | Note that if n <= v.allocated(), then v.SetLength(n) is guaranteed |
---|
83 | not to cause any memory allocation, or movement of objects. |
---|
84 | |
---|
85 | \**************************************************************************/ |
---|
86 | |
---|
87 | class vec_T { |
---|
88 | public: |
---|
89 | |
---|
90 | vec_T(); // initially length 0 |
---|
91 | |
---|
92 | vec_T(const vec_T& a); |
---|
93 | // copy constructor; currently, this is implemented by |
---|
94 | // initializing elements using T's defaults constructor and |
---|
95 | // copying elements from a using T's assigment operator. |
---|
96 | |
---|
97 | vec_T& operator=(const vec_T& a); |
---|
98 | // assignment...performs an element-wise assignment |
---|
99 | // using T's assignment operator. |
---|
100 | |
---|
101 | ~vec_T(); |
---|
102 | |
---|
103 | void SetLength(long n); |
---|
104 | // set current length to n, growing vector if necessary |
---|
105 | |
---|
106 | long length() const; |
---|
107 | // current length |
---|
108 | // SIZE INVARIANT: length()*sizeof(T) < 2^(NTL_BITS_PER_LONG-4) |
---|
109 | |
---|
110 | T& operator[](long i); |
---|
111 | const T& operator[](long i) const; |
---|
112 | // indexing operation, starting from 0. |
---|
113 | // The first version is applied to non-const vec_T, |
---|
114 | // and returns a non-const reference to a T, while the second version |
---|
115 | // is applied to a const vec_T and returns a const reference to a T. |
---|
116 | |
---|
117 | T& operator()(long i); |
---|
118 | const T& operator()(long i) const; |
---|
119 | // indexing operation, starting from 1 |
---|
120 | // The first version is applied to non-const vec_T, |
---|
121 | // and returns a non-const reference to a T, while the second version |
---|
122 | // is applied to a const vec_T and returns a const reference to a T. |
---|
123 | |
---|
124 | T* elts(); |
---|
125 | const T* elts() const; |
---|
126 | // returns address of first vector element (or 0 if no space has |
---|
127 | // been allocated for this vector). If a vector potentially has |
---|
128 | // length 0, it is safer to write v.elts() instead of &v[0]. |
---|
129 | // The first version is applied to non-const vec_T, |
---|
130 | // and returns a non-const pointer to a T, while the second version |
---|
131 | // is applied to a const vec_T and returns a const reference to a T. |
---|
132 | |
---|
133 | |
---|
134 | // the remaining member functions are a bit esoteric (skip on first |
---|
135 | // reading): |
---|
136 | |
---|
137 | vec_T(INIT_SIZE_TYPE, long n); |
---|
138 | // vec_T(INIT_SIZE, n) initializes with an intial length of n. |
---|
139 | |
---|
140 | void kill(); |
---|
141 | // release space and set to length 0 |
---|
142 | |
---|
143 | void SetMaxLength(long n); |
---|
144 | // allocates space and initializes up to n elements. Does not change |
---|
145 | // current length |
---|
146 | |
---|
147 | void FixLength(long n); |
---|
148 | // sets length to n and prohibits all future length changes. |
---|
149 | // FixLength may only be invoked immediately after the default |
---|
150 | // construction or kill. |
---|
151 | |
---|
152 | // The kill operation is also subsequently prohibited, and swap is |
---|
153 | // allowed on fixed length vectors of the same length. |
---|
154 | |
---|
155 | // FixLength is provided mainly to implement mat_T, to enforce |
---|
156 | // the restriction that all rows have the same length. |
---|
157 | |
---|
158 | long fixed() const; |
---|
159 | // test if length has been fixed by FixLength(). |
---|
160 | |
---|
161 | long MaxLength() const; |
---|
162 | // maximum length, i.e., number of allocated and initialized elements |
---|
163 | |
---|
164 | long allocated() const; |
---|
165 | // the number of objects for which space has been allocated, but not |
---|
166 | // necessarily initialized; this may be larger than MaxLength(). |
---|
167 | |
---|
168 | T& RawGet(long i); |
---|
169 | const T& RawGet(long i) const; |
---|
170 | // indexing with no range checking |
---|
171 | |
---|
172 | long position(const T& a) const; |
---|
173 | // returns position of a in the vector, or -1 if it is not there. |
---|
174 | // The search is conducted from position 0 to MaxAlloc()-1 of the vector, |
---|
175 | // and an error is raised if the object is found at position MaxLength() |
---|
176 | // or higher (in which case a references an uninitialized object). |
---|
177 | // Note that if NTL_CLEAN_PTR flag is set, this routine takes |
---|
178 | // linear time, and otherwise, it takes constant time. |
---|
179 | |
---|
180 | long position1(const T& a) const; |
---|
181 | // returns position of a in the vector, or -1 if it is not there. |
---|
182 | // The search is conducted from position 0 to length()-1 of the vector. |
---|
183 | // Note that if NTL_CLEAN_PTR flag is set, this routine takes |
---|
184 | // linear time, and otherwise, it takes constant time. |
---|
185 | |
---|
186 | }; |
---|
187 | |
---|
188 | |
---|
189 | /**************************************************************************\ |
---|
190 | |
---|
191 | Some utility routines |
---|
192 | |
---|
193 | \**************************************************************************/ |
---|
194 | |
---|
195 | |
---|
196 | void swap(vec_T& x, vec_T& y); |
---|
197 | // swaps x & y by swapping pointers |
---|
198 | |
---|
199 | void append(vec_T& v, const T& a); |
---|
200 | // appends a to the end of v |
---|
201 | |
---|
202 | void append(vec_T& v, const vec_T& w); |
---|
203 | // appends w to the end of v |
---|
204 | |
---|
205 | |
---|
206 | |
---|
207 | |
---|
208 | /**************************************************************************\ |
---|
209 | |
---|
210 | Input/Output |
---|
211 | |
---|
212 | The I/O operators can be declared with NTL_io_vector_decl(T,vec_T), and |
---|
213 | implemented using NTL_io_vector_impl(T,vec_T). Elements are read and written |
---|
214 | using the underlying I/O operators << and >> for T. |
---|
215 | |
---|
216 | The I/O format for a vector v with n elements is: |
---|
217 | |
---|
218 | [v[0] v[1] ... v[n-1]] |
---|
219 | |
---|
220 | \**************************************************************************/ |
---|
221 | |
---|
222 | istream& operator>>(istream&, vec_T&); |
---|
223 | ostream& operator<<(ostream&, const vec_T&); |
---|
224 | |
---|
225 | |
---|
226 | |
---|
227 | /**************************************************************************\ |
---|
228 | |
---|
229 | Equality Testing |
---|
230 | |
---|
231 | The equality testing operators == and != can be declared |
---|
232 | with NTL_eq_vector_decl(T,vec_T) and implemented with |
---|
233 | NTL_eq_vector_impl(T,vec_T). |
---|
234 | The tests are performed using the underlying operator == for T. |
---|
235 | |
---|
236 | \**************************************************************************/ |
---|
237 | |
---|
238 | |
---|
239 | long operator==(const vec_T& a, const vec_T& b); |
---|
240 | long operator!=(const vec_T& a, const vec_T& b); |
---|
241 | |
---|
242 | |
---|
243 | /**************************************************************************\ |
---|
244 | |
---|
245 | Customized Constructors and Destructors |
---|
246 | |
---|
247 | Esoteric: skip on first reading |
---|
248 | |
---|
249 | When new elements in a vector need to be constructed, the routine |
---|
250 | |
---|
251 | void BlockConstruct(T* p, long n); |
---|
252 | |
---|
253 | is called, whose default implementation invokes the default |
---|
254 | constructor for T n times. Likewise, when a vector is destroyed, the |
---|
255 | routine |
---|
256 | |
---|
257 | void BlockDestroy(T* p, long n); |
---|
258 | |
---|
259 | is called, whose default implementation invokes the default destructor |
---|
260 | for T n times. |
---|
261 | |
---|
262 | Both of these default implementations can be overridden as follows. |
---|
263 | Instead of implementing vec_T with NTL_vector_impl(T,vec_T), implement it |
---|
264 | with NTL_vector_impl_plain(T,vec_T), and then write your own BlockConstruct and |
---|
265 | BlockDestroy. |
---|
266 | |
---|
267 | For an example of this, see vec_ZZ_p.c. |
---|
268 | |
---|
269 | \**************************************************************************/ |
---|
270 | |
---|