1 | ////////////////////////////////////////////////////////////////////////////////
|
---|
2 | // NTL Nonstandard Template Library for C++
|
---|
3 | // Copyright (c) 2003 by Miroslav Fidler, Tomas Rylek
|
---|
4 | //
|
---|
5 | // Created by Miroslav Fidler, Tomas Rylek, cxl@volny.cz
|
---|
6 | //
|
---|
7 | // Permission to use, copy, modify, distribute and sell this software for any
|
---|
8 | // purpose is hereby granted without fee, provided that the above copyright
|
---|
9 | // notice appear in all copies and that both that copyright notice and this
|
---|
10 | // permission notice appear in supporting documentation.
|
---|
11 | // The author makes no representations about the suitability of this software
|
---|
12 | // for any purpose. It is provided "as is"
|
---|
13 | // without express or implied warranty.
|
---|
14 | ////////////////////////////////////////////////////////////////////////////////
|
---|
15 |
|
---|
16 | template <int size>
|
---|
17 | void RawVector<size>::Realloc(int newalloc)
|
---|
18 | {
|
---|
19 | ASSERT(newalloc >= items);
|
---|
20 | Chk();
|
---|
21 | if(newalloc == alloc) return;
|
---|
22 | Data *newvector = newalloc ? Alloc(newalloc) : NULL;
|
---|
23 | if(vector) {
|
---|
24 | memcpy(newvector, vector, items * sizeof(Data));
|
---|
25 | RawFree();
|
---|
26 | }
|
---|
27 | vector = newvector;
|
---|
28 | alloc = newalloc;
|
---|
29 | }
|
---|
30 |
|
---|
31 | template <int size>
|
---|
32 | void RawVector<size>::Expand()
|
---|
33 | {
|
---|
34 | #ifdef _DEBUG
|
---|
35 | Realloc(ntl_max(2 * alloc, 1));
|
---|
36 | #else
|
---|
37 | Realloc(ntl_max(2 * alloc, size == 4 ? 8 : 1));
|
---|
38 | #endif
|
---|
39 | }
|
---|
40 |
|
---|
41 | template <int size>
|
---|
42 | void RawVector<size>::RawFree()
|
---|
43 | {
|
---|
44 | NTL_RAW_FREE(vector, size, sizeof(T));
|
---|
45 | }
|
---|
46 |
|
---|
47 | template <int size>
|
---|
48 | void RawVector<size>::Pick(pick_ RawVector& v)
|
---|
49 | {
|
---|
50 | vector = v.vector;
|
---|
51 | items = v.items;
|
---|
52 | alloc = v.alloc;
|
---|
53 | SetPicked(v);
|
---|
54 | }
|
---|
55 |
|
---|
56 | template <int size>
|
---|
57 | int RawVector<size>::RawGetIndex(const void *item) const
|
---|
58 | {
|
---|
59 | Chk();
|
---|
60 | if(vector == NULL) return -1;
|
---|
61 | int n = (const Data *)item - vector;
|
---|
62 | return n >= 0 && n < items ? n : -1;
|
---|
63 | }
|
---|
64 |
|
---|
65 | template <int size>
|
---|
66 | void RawVector<size>::RawSwap(RawVector<size>& b)
|
---|
67 | {
|
---|
68 | ::Swap(items, b.items);
|
---|
69 | ::Swap(alloc, b.alloc);
|
---|
70 | ::Swap(vector, b.vector);
|
---|
71 | }
|
---|
72 |
|
---|
73 | template <int size>
|
---|
74 | void RawVector<size>::RawReserve(int n)
|
---|
75 | {
|
---|
76 | if(n > alloc)
|
---|
77 | Realloc(n);
|
---|
78 | }
|
---|
79 |
|
---|
80 | template <int size>
|
---|
81 | void RawVector<size>::RawInsert(int q, int count)
|
---|
82 | {
|
---|
83 | Chk();
|
---|
84 | ASSERT(q >= 0 && q <= items);
|
---|
85 | if(!count) return;
|
---|
86 | if(items + count > alloc) {
|
---|
87 | Data *newvector = Alloc(alloc = alloc + ntl_max(alloc, count));
|
---|
88 | if(vector) {
|
---|
89 | memcpy(newvector, vector, q * sizeof(Data));
|
---|
90 | memcpy(newvector + q + count, vector + q, (items - q) * sizeof(Data));
|
---|
91 | RawFree();
|
---|
92 | }
|
---|
93 | vector = newvector;
|
---|
94 | }
|
---|
95 | else
|
---|
96 | memmove(vector + q + count, vector + q, (items - q) * sizeof(Data));
|
---|
97 | items += count;
|
---|
98 | }
|
---|
99 |
|
---|
100 | template <int size>
|
---|
101 | void RawVector<size>::RawInsertPick(int i, pick_ RawVector<size>& v) {
|
---|
102 | Chk();
|
---|
103 | v.Chk();
|
---|
104 | if(v.items) {
|
---|
105 | RawInsert(i, v.items);
|
---|
106 | memcpy(vector + i, v.vector, size * v.items);
|
---|
107 | }
|
---|
108 | const_cast< RawVector<size>& >(v).RawFree();
|
---|
109 | SetPicked(v);
|
---|
110 | }
|
---|
111 |
|
---|
112 | // ------------------
|
---|
113 |
|
---|
114 | template <class T>
|
---|
115 | void Vector<T>::Free() {
|
---|
116 | if(B::vector && B::items >= 0)
|
---|
117 | DestroyArray((T *)B::vector, (T *)B::vector + B::items);
|
---|
118 | B::RawFree();
|
---|
119 | }
|
---|
120 |
|
---|
121 | template <class T>
|
---|
122 | void Vector<T>::Clear() {
|
---|
123 | if(B::vector && B::items >= 0)
|
---|
124 | SetCount(0);
|
---|
125 | else {
|
---|
126 | B::alloc = B::items = 0;
|
---|
127 | B::vector = NULL;
|
---|
128 | }
|
---|
129 | }
|
---|
130 |
|
---|
131 | template <class T>
|
---|
132 | void Vector<T>::__DeepCopy(const Vector& src) {
|
---|
133 | src.Chk();
|
---|
134 | B::items = B::alloc = src.B::items;
|
---|
135 | if(src.vector) {
|
---|
136 | B::vector = B::Alloc(B::alloc);
|
---|
137 | DeepCopyConstructArray((T *)B::vector, (T *)src.B::vector,
|
---|
138 | (T *)src.B::vector + B::items);
|
---|
139 | }
|
---|
140 | else
|
---|
141 | B::vector = NULL;
|
---|
142 | }
|
---|
143 |
|
---|
144 | template <class T> inline
|
---|
145 | T& Vector<T>::Add()
|
---|
146 | {
|
---|
147 | if(B::items >= B::alloc) Expand();
|
---|
148 | T *p = ::new(B::vector + B::items) T;
|
---|
149 | B::items++;
|
---|
150 | return *p;
|
---|
151 | }
|
---|
152 |
|
---|
153 | template <class T> inline
|
---|
154 | void Vector<T>::AddN(int n)
|
---|
155 | {
|
---|
156 | ASSERT(n >= 0);
|
---|
157 | if(B::items + n <= B::alloc) {
|
---|
158 | const TYPENAME Vector<T>::Data *w = B::vector + B::items;
|
---|
159 | B::items += n;
|
---|
160 | while(n--)
|
---|
161 | ::new((void *)w++) T;
|
---|
162 | }
|
---|
163 | else
|
---|
164 | SetCountR(B::items + n);
|
---|
165 | }
|
---|
166 |
|
---|
167 | template <class T>
|
---|
168 | void Vector<T>::Trim(int n)
|
---|
169 | {
|
---|
170 | ASSERT(n >= 0 && n <= B::items);
|
---|
171 | DestroyArray((T*)B::vector + n, (T*)B::vector + B::items);
|
---|
172 | B::items = n;
|
---|
173 | }
|
---|
174 |
|
---|
175 | template <class T>
|
---|
176 | void Vector<T>::SetCount(int n) {
|
---|
177 | Chk();
|
---|
178 | ASSERT(n >= 0);
|
---|
179 | if(n == B::items) return;
|
---|
180 | if(n < B::items)
|
---|
181 | Trim(n);
|
---|
182 | else {
|
---|
183 | if(n > B::alloc) B::Realloc(n);
|
---|
184 | ConstructArray((T*)B::vector + B::items, (T*)B::vector + n);
|
---|
185 | B::items = n;
|
---|
186 | }
|
---|
187 | }
|
---|
188 |
|
---|
189 | template <class T>
|
---|
190 | void Vector<T>::SetCount(int n, const T& init) {
|
---|
191 | Chk();
|
---|
192 | ASSERT(n >= 0);
|
---|
193 | if(n == B::items) return;
|
---|
194 | if(n < B::items)
|
---|
195 | DestroyArray((T*)B::vector + n, (T*)B::vector + B::items);
|
---|
196 | else {
|
---|
197 | if(n > B::alloc) B::Realloc(n);
|
---|
198 | DeepCopyConstructFill((T*)B::vector + B::items, (T*)B::vector + n, init);
|
---|
199 | }
|
---|
200 | B::items = n;
|
---|
201 | }
|
---|
202 |
|
---|
203 | template <class T>
|
---|
204 | void Vector<T>::SetCountR(int n) {
|
---|
205 | Chk();
|
---|
206 | if(n + B::items > B::alloc)
|
---|
207 | B::Realloc(B::alloc + ntl_max(B::alloc, n));
|
---|
208 | SetCount(n);
|
---|
209 | }
|
---|
210 |
|
---|
211 | template <class T>
|
---|
212 | void Vector<T>::SetCountR(int n, const T& init) {
|
---|
213 | Chk();
|
---|
214 | if(n + B::items > B::alloc)
|
---|
215 | B::Realloc(B::alloc + ntl_max(B::alloc, n));
|
---|
216 | SetCount(n, init);
|
---|
217 | }
|
---|
218 |
|
---|
219 | template <class T>
|
---|
220 | void Vector<T>::Remove(int q, int count) {
|
---|
221 | Chk();
|
---|
222 | ASSERT(q >= 0 && q <= B::items - count && count >= 0);
|
---|
223 | if(count == 0) return;
|
---|
224 | DestroyArray((T*)B::vector + q, (T*)B::vector + q + count);
|
---|
225 | //G++
|
---|
226 | memmove((T*)B::vector + q, (T*)B::vector + q + count, (B::items - q - count) * sizeof(T));
|
---|
227 | // memmove((T*)vector + q, (T*)vector + q + count, (items - q - count) * sizeof(Data));
|
---|
228 | B::items -= count;
|
---|
229 | }
|
---|
230 |
|
---|
231 | template <int size>
|
---|
232 | class Data_S_ {
|
---|
233 | byte filler[size];
|
---|
234 | };
|
---|
235 |
|
---|
236 | template <class T>
|
---|
237 | void Vector<T>::Remove(const int *sorted_list, int n)
|
---|
238 | {
|
---|
239 | Chk();
|
---|
240 | if(!n) return;
|
---|
241 | int pos = *sorted_list;
|
---|
242 | int npos = pos;
|
---|
243 | for(;;) {
|
---|
244 | ASSERT(pos < B::items);
|
---|
245 | if(pos == *sorted_list) {
|
---|
246 | ((T*)B::vector + pos)->T::~T();
|
---|
247 | pos++;
|
---|
248 | sorted_list++;
|
---|
249 | if(--n == 0) break;
|
---|
250 | ASSERT(*sorted_list >= pos);
|
---|
251 | }
|
---|
252 | else
|
---|
253 | *((Data_S_<sizeof(T)>*)B::vector + npos++)
|
---|
254 | = *((Data_S_<sizeof(T)>*)B::vector + pos++);
|
---|
255 | }
|
---|
256 | while(pos < B::items)
|
---|
257 | *((Data_S_<sizeof(T)>*)B::vector + npos++) = *((Data_S_<sizeof(T)>*)B::vector + pos++);
|
---|
258 | B::items = npos;
|
---|
259 | }
|
---|
260 |
|
---|
261 | template <class T>
|
---|
262 | void Vector<T>::Remove(const Vector<int>& v)
|
---|
263 | {
|
---|
264 | Remove(v, v.GetCount());
|
---|
265 | }
|
---|
266 |
|
---|
267 | template <class T>
|
---|
268 | void Vector<T>::InsertN(int q, int count) {
|
---|
269 | ASSERT(count >= 0);
|
---|
270 | B::RawInsert(q, count);
|
---|
271 | ConstructArray((T*) B::vector + q, (T*)B::vector + q + count);
|
---|
272 | }
|
---|
273 |
|
---|
274 | template <class T>
|
---|
275 | void Vector<T>::Insert(int q, const T& x, int count) {
|
---|
276 | if(!count) return;
|
---|
277 | B::RawInsert(q, count);
|
---|
278 | DeepCopyConstructFill((T*)B::vector + q, (T*)B::vector + q + count, x);
|
---|
279 | }
|
---|
280 |
|
---|
281 | template <class T>
|
---|
282 | void Vector<T>::Insert(int q, const Vector& x, int offset, int count) {
|
---|
283 | if(!count) return;
|
---|
284 | ASSERT(offset >= 0 && count >= 0 && offset + count <= x.GetCount());
|
---|
285 | B::RawInsert(q, count);
|
---|
286 | DeepCopyConstructArray((T*)B::vector + q, (T*)x.B::vector + offset,
|
---|
287 | (T*)x.B::vector + offset + count);
|
---|
288 | }
|
---|
289 |
|
---|
290 | template <class T>
|
---|
291 | void Vector<T>::Insert(int q, const Vector& x) {
|
---|
292 | if(!x.GetCount()) return;
|
---|
293 | Insert(q, x, 0, x.GetCount());
|
---|
294 | }
|
---|
295 |
|
---|
296 | template <class T>
|
---|
297 | void Vector<T>::Set(int i, const T& x, int count) {
|
---|
298 | Chk();
|
---|
299 | ASSERT(i >= 0 && count >= 0);
|
---|
300 | if(count == 0) return;
|
---|
301 | DoIndex(i + count - 1);
|
---|
302 | Fill((T*)B::vector + i, (T*)B::vector + i + count, x);
|
---|
303 | }
|
---|
304 |
|
---|
305 | // ------------------
|
---|
306 |
|
---|
307 | template <class T>
|
---|
308 | void Array<T>::Free() {
|
---|
309 | if(IsPicked()) return;
|
---|
310 | for(int i = 0; i < vector.GetCount(); i++)
|
---|
311 | delete (T *) vector[i];
|
---|
312 | }
|
---|
313 |
|
---|
314 | template <class T>
|
---|
315 | void Array<T>::__DeepCopy(const Array<T>& v) {
|
---|
316 | int n = v.GetCount();
|
---|
317 | vector.SetCount(n);
|
---|
318 | for(int i = 0; i < n; i++)
|
---|
319 | vector[i] = DeepCopyNew(v[i]);
|
---|
320 | }
|
---|
321 |
|
---|
322 | template <class T>
|
---|
323 | void Array<T>::Trim(int n)
|
---|
324 | {
|
---|
325 | ASSERT(n >= 0 && n <= GetCount());
|
---|
326 | Del(vector.Begin() + n, vector.End());
|
---|
327 | vector.Trim(n);
|
---|
328 | }
|
---|
329 |
|
---|
330 | template <class T>
|
---|
331 | void Array<T>::SetCount(int n) {
|
---|
332 | ASSERT(n >= 0);
|
---|
333 | int lc = vector.GetCount();
|
---|
334 | Del(vector.Begin() + n, vector.End());
|
---|
335 | vector.SetCount(n);
|
---|
336 | Init(vector.Begin() + lc, vector.Begin() + n);
|
---|
337 | }
|
---|
338 |
|
---|
339 | template <class T>
|
---|
340 | void Array<T>::SetCount(int n, const T& init) {
|
---|
341 | ASSERT(n >= 0);
|
---|
342 | int lc = vector.GetCount();
|
---|
343 | Del(vector.Begin() + n, vector.End());
|
---|
344 | vector.SetCount(n);
|
---|
345 | Init(vector.Begin() + lc, vector.Begin() + n, init);
|
---|
346 | }
|
---|
347 |
|
---|
348 | template <class T>
|
---|
349 | void Array<T>::SetCountR(int n) {
|
---|
350 | ASSERT(n >= 0);
|
---|
351 | int lc = vector.GetCount();
|
---|
352 | Del(vector.Begin() + n, vector.End());
|
---|
353 | vector.SetCountR(n);
|
---|
354 | Init(vector.Begin() + lc, vector.Begin() + n);
|
---|
355 | }
|
---|
356 |
|
---|
357 | template <class T>
|
---|
358 | void Array<T>::SetCountR(int n, const T& init) {
|
---|
359 | ASSERT(n >= 0);
|
---|
360 | int lc = vector.GetCount();
|
---|
361 | Del(vector.Begin() + n, vector.End());
|
---|
362 | vector.SetCountR(n);
|
---|
363 | Init(vector.Begin() + lc, vector.Begin() + n, init);
|
---|
364 | }
|
---|
365 |
|
---|
366 | template <class T>
|
---|
367 | int Array<T>::GetIndex(const T& item) const {
|
---|
368 | for(void * const *ptr = vector.Begin(); ptr < vector.End(); ptr++)
|
---|
369 | if(*ptr == (void *)&item) return ptr - vector.Begin();
|
---|
370 | return -1;
|
---|
371 | }
|
---|
372 |
|
---|
373 | template <class T>
|
---|
374 | void Array<T>::Move(int i1, int i2) {
|
---|
375 | void *q = vector[i1];
|
---|
376 | vector.Remove(i1);
|
---|
377 | vector.Insert(i2) = q;
|
---|
378 | }
|
---|
379 |
|
---|
380 | template <class T>
|
---|
381 | void Array<T>::Remove(int i, int count) {
|
---|
382 | ASSERT(i + count <= GetCount() && count >= 0 && i >= 0);
|
---|
383 | Del(vector.Begin() + i, vector.Begin() + i + count);
|
---|
384 | vector.Remove(i, count);
|
---|
385 | }
|
---|
386 |
|
---|
387 | template <class T>
|
---|
388 | void Array<T>::Remove(const int *sorted_list, int n)
|
---|
389 | {
|
---|
390 | const int *q = sorted_list;
|
---|
391 | const int *e = sorted_list + n;
|
---|
392 | while(q < e) {
|
---|
393 | ASSERT(*q >= 0 && *q < GetCount());
|
---|
394 | delete (T *)vector[*q++];
|
---|
395 | }
|
---|
396 | vector.Remove(sorted_list, n);
|
---|
397 | }
|
---|
398 |
|
---|
399 | template <class T>
|
---|
400 | void Array<T>::Remove(const Vector<int>& sorted_list)
|
---|
401 | {
|
---|
402 | Remove(sorted_list, sorted_list.GetCount());
|
---|
403 | }
|
---|
404 |
|
---|
405 | template <class T>
|
---|
406 | void Array<T>::Set(int i, const T& x, int count) {
|
---|
407 | ASSERT(i >= 0 && count >= 0);
|
---|
408 | if(i + count >= GetCount())
|
---|
409 | SetCountR(i + count);
|
---|
410 | for(void **ptr = vector.Begin() + i; ptr < vector.Begin() + i + count; ptr++) {
|
---|
411 | delete (T *) *ptr;
|
---|
412 | *ptr = new T(x);
|
---|
413 | }
|
---|
414 | }
|
---|
415 |
|
---|
416 | template <class T>
|
---|
417 | void Array<T>::InsertN(int i, int count) {
|
---|
418 | ASSERT(i >= 0 && count >= 0);
|
---|
419 | vector.InsertN(i, count);
|
---|
420 | Init(vector.Begin() + i, vector.Begin() + i + count);
|
---|
421 | }
|
---|
422 |
|
---|
423 | template <class T>
|
---|
424 | void Array<T>::Insert(int i, const T& x, int count) {
|
---|
425 | vector.InsertN(i, count);
|
---|
426 | Init(vector.Begin() + i, vector.Begin() + i + count, x);
|
---|
427 | }
|
---|
428 |
|
---|
429 | template <class T>
|
---|
430 | void Array<T>::Insert(int i, T *newt) {
|
---|
431 | vector.InsertN(i, 1);
|
---|
432 | vector[i] = newt;
|
---|
433 | }
|
---|
434 |
|
---|
435 | template <class T>
|
---|
436 | void Array<T>::Insert(int i, const Array& x) {
|
---|
437 | Insert(i, x, 0, x.GetCount());
|
---|
438 | }
|
---|
439 |
|
---|
440 | template <class T>
|
---|
441 | void Array<T>::Insert(int i, const Array& x, int offset, int count) {
|
---|
442 | vector.InsertN(i, count);
|
---|
443 | for(int q = 0; q < count; q++)
|
---|
444 | vector[q + i] = DeepCopyNew(x[q + offset]);
|
---|
445 | }
|
---|
446 |
|
---|
447 | template <class T>
|
---|
448 | void Array<T>::InsertPick(int i, pick_ Array& x) {
|
---|
449 | Array xx = x;
|
---|
450 | int cx = xx.GetCount();
|
---|
451 | vector.InsertN(i, cx);
|
---|
452 | for(int q = 0; q < cx; q++)
|
---|
453 | vector[q + i] = x.vector[q];
|
---|
454 | }
|
---|
455 |
|
---|
456 | // ------------------
|
---|
457 |
|
---|
458 | template <class T, int NBLK>
|
---|
459 | Segtor<T, NBLK>::Segtor(const Segtor& s, int) {
|
---|
460 | items = s.items;
|
---|
461 | block.SetCount((items + NBLK - 1) / NBLK);
|
---|
462 | int q = items / NBLK;
|
---|
463 | int r = items % NBLK;
|
---|
464 | int i;
|
---|
465 | for(i = 0; i < q; i++) {
|
---|
466 | T *a = (T *) s.block[i].item;
|
---|
467 | DeepCopyConstructArray((T *) block[i].item, a, a + NBLK);
|
---|
468 | }
|
---|
469 | if(r) {
|
---|
470 | T *a = (T *) s.block[q].item;
|
---|
471 | DeepCopyConstructArray((T *) block[i].item, a, a + r);
|
---|
472 | }
|
---|
473 | }
|
---|
474 |
|
---|
475 | template <class T, int NBLK>
|
---|
476 | void Segtor<T, NBLK>::Free() {
|
---|
477 | int q = items / NBLK;
|
---|
478 | int r = items % NBLK;
|
---|
479 | int i;
|
---|
480 | for(i = 0; i < q; i++) {
|
---|
481 | T *a = (T *) block[i].item;
|
---|
482 | DestroyArray(a, a + NBLK);
|
---|
483 | }
|
---|
484 | if(r) {
|
---|
485 | T *a = (T *) block[i].item;
|
---|
486 | DestroyArray(a, a + r);
|
---|
487 | }
|
---|
488 | }
|
---|
489 |
|
---|
490 | template <class T, int NBLK>
|
---|
491 | Segtor<T, NBLK>::~Segtor() {
|
---|
492 | if(IsPicked()) return;
|
---|
493 | Free();
|
---|
494 | }
|
---|
495 |
|
---|
496 | template <class T, int NBLK>
|
---|
497 | void Segtor<T, NBLK>::DoRange(unsigned beg, unsigned end, void (*fn)(T*, const T*)) {
|
---|
498 | ASSERT(beg <= end);
|
---|
499 | int bblk = beg / NBLK, bidx = beg % NBLK;
|
---|
500 | int eblk = end / NBLK, eidx = end % NBLK;
|
---|
501 | if(eblk == block.GetCount()) {
|
---|
502 | ASSERT(eidx == 0);
|
---|
503 | eblk--;
|
---|
504 | eidx = NBLK;
|
---|
505 | }
|
---|
506 | ASSERT(eblk < block.GetCount());
|
---|
507 | T *tp = (T *)block[bblk].item;
|
---|
508 | if(bblk != eblk) {
|
---|
509 | (*fn)(tp + bidx, tp + NBLK);
|
---|
510 | while(++bblk < eblk) {
|
---|
511 | tp = (T *)block[bblk].item;
|
---|
512 | (*fn)(tp, tp + NBLK);
|
---|
513 | }
|
---|
514 | tp = (T *)block[bblk].item;
|
---|
515 | (*fn)(tp, tp + eidx);
|
---|
516 | }
|
---|
517 | else
|
---|
518 | (*fn)(tp + bidx, tp + eidx);
|
---|
519 | }
|
---|
520 |
|
---|
521 | template <class T, int NBLK>
|
---|
522 | void Segtor<T, NBLK>::Fill(unsigned beg, unsigned end, const T& x) {
|
---|
523 | ASSERT(beg <= end);
|
---|
524 | int bblk = beg / NBLK, bidx = beg % NBLK;
|
---|
525 | int eblk = end / NBLK, eidx = end % NBLK;
|
---|
526 | if(eblk == block.GetCount()) {
|
---|
527 | ASSERT(eidx == 0);
|
---|
528 | eblk--;
|
---|
529 | eidx = NBLK;
|
---|
530 | }
|
---|
531 | ASSERT(eblk < block.GetCount());
|
---|
532 | T *tp = (T *)block[bblk].item;
|
---|
533 | if(bblk != eblk) {
|
---|
534 | DeepCopyConstructFill(tp + bidx, tp + NBLK, x);
|
---|
535 | while(++bblk < eblk) {
|
---|
536 | tp = (T *)block[bblk].item;
|
---|
537 | DeepCopyConstructFill(tp, tp + NBLK, x);
|
---|
538 | }
|
---|
539 | tp = (T *)block[bblk].item;
|
---|
540 | DeepCopyConstructFill(tp, tp + eidx, x);
|
---|
541 | }
|
---|
542 | else
|
---|
543 | DeepCopyConstructFill(tp + bidx, tp + eidx, x);
|
---|
544 | }
|
---|
545 |
|
---|
546 | template <class T, int NBLK>
|
---|
547 | void Segtor<T, NBLK>::SetCount(int n) {
|
---|
548 | Del(n);
|
---|
549 | block.SetCount((n + NBLK - 1) / NBLK);
|
---|
550 | Init(n);
|
---|
551 | }
|
---|
552 |
|
---|
553 | template <class T, int NBLK>
|
---|
554 | void Segtor<T, NBLK>::SetCount(int n, const T& init) {
|
---|
555 | Del(n);
|
---|
556 | block.SetCount((n + NBLK - 1) / NBLK);
|
---|
557 | Init(n, init);
|
---|
558 | }
|
---|
559 |
|
---|
560 | template <class T, int NBLK>
|
---|
561 | void Segtor<T, NBLK>::Clear() {
|
---|
562 | if(!IsPicked())
|
---|
563 | Free();
|
---|
564 | items = 0;
|
---|
565 | block.Clear();
|
---|
566 | }
|
---|
567 |
|
---|
568 | template <class T, int NBLK>
|
---|
569 | void Segtor<T, NBLK>::Set(int i, const T& x, int count) {
|
---|
570 | ASSERT(i >= 0 && count >= 0);
|
---|
571 | DoIndex(i + count - 1);
|
---|
572 | Iterator q(*this, i);
|
---|
573 | while(count--)
|
---|
574 | *q++ = x;
|
---|
575 | }
|
---|
576 |
|
---|
577 | template <class T, int NBLK>
|
---|
578 | int Segtor<T, NBLK>::GetIndex(const T& item) const {
|
---|
579 | for(int i = 0; i < block.GetCount(); i++) {
|
---|
580 | T *q = (T *) block[i].item;
|
---|
581 | if(&item >= q && &item < q + NBLK)
|
---|
582 | return &item - q + NBLK * i;
|
---|
583 | }
|
---|
584 | return -1;
|
---|
585 | }
|
---|
586 |
|
---|
587 | // ------------------
|
---|
588 |
|
---|
589 | template <class T>
|
---|
590 | void BiVector<T>::ReAlloc(int newalloc) {
|
---|
591 | ASSERT(items <= newalloc && items >= 0);
|
---|
592 | T *newvector = newalloc ? (T *) NTL_RAW_ALLOC(newalloc * sizeof(T)) : NULL;
|
---|
593 | if(items) {
|
---|
594 | int end = start + items;
|
---|
595 | if(end <= alloc)
|
---|
596 | memcpy(newvector, vector + start, (end - start) * sizeof(T));
|
---|
597 | else {
|
---|
598 | memcpy(newvector, vector + start, (alloc - start) * sizeof(T));
|
---|
599 | memcpy(newvector + alloc - start, vector, (end - alloc) * sizeof(T));
|
---|
600 | }
|
---|
601 | NTL_RAW_FREE(vector, items, sizeof(T));
|
---|
602 | }
|
---|
603 | vector = newvector;
|
---|
604 | alloc = newalloc;
|
---|
605 | start = 0;
|
---|
606 | }
|
---|
607 |
|
---|
608 | template <class T>
|
---|
609 | void BiVector<T>::DeepCopy0(const BiVector& src) {
|
---|
610 | alloc = items = src.items;
|
---|
611 | vector = alloc ? (T *) NTL_RAW_ALLOC((alloc * sizeof(T))) : NULL;
|
---|
612 | if(items) {
|
---|
613 | int end = src.start + src.items;
|
---|
614 | if(end <= src.alloc)
|
---|
615 | DeepCopyConstructArray(vector, src.vector + src.start, src.vector + end);
|
---|
616 | else {
|
---|
617 | DeepCopyConstructArray(vector, src.vector + src.start, src.vector + src.alloc);
|
---|
618 | DeepCopyConstructArray(vector + src.alloc - src.start, src.vector,
|
---|
619 | src.vector + end - src.alloc);
|
---|
620 | }
|
---|
621 | }
|
---|
622 | start = 0;
|
---|
623 | }
|
---|
624 |
|
---|
625 | template <class T>
|
---|
626 | void BiVector<T>::Clear() {
|
---|
627 | Free();
|
---|
628 | start = items = alloc = 0;
|
---|
629 |
|
---|
630 | vector = NULL;
|
---|
631 | }
|
---|
632 |
|
---|
633 | template <class T>
|
---|
634 | void BiVector<T>::Add0() {
|
---|
635 | ASSERT(items >= 0);
|
---|
636 | if(items >= alloc)
|
---|
637 | ReAlloc(ntl_max(2 * items, 4));
|
---|
638 | items++;
|
---|
639 | }
|
---|
640 |
|
---|
641 | template <class T>
|
---|
642 | void BiVector<T>::Shrink() {
|
---|
643 | ASSERT(items >= 0);
|
---|
644 | if(items < alloc)
|
---|
645 | ReAlloc(items);
|
---|
646 | }
|
---|
647 |
|
---|
648 | template <class T>
|
---|
649 | void BiVector<T>::Reserve(int n) {
|
---|
650 | ASSERT(items >= 0);
|
---|
651 | n += items;
|
---|
652 | if(n > alloc)
|
---|
653 | ReAlloc(n);
|
---|
654 | }
|
---|
655 |
|
---|
656 | template <class T>
|
---|
657 | void BiVector<T>::Free() {
|
---|
658 | if(vector && items >= 0) {
|
---|
659 | int end = start + items;
|
---|
660 | if(end <= alloc)
|
---|
661 | DestroyArray(vector + start, vector + end);
|
---|
662 | else {
|
---|
663 | DestroyArray(vector + start, vector + alloc);
|
---|
664 | DestroyArray(vector, vector + end - alloc);
|
---|
665 | }
|
---|
666 | NTL_RAW_FREE(vector, items, sizeof(T));
|
---|
667 | }
|
---|
668 | }
|
---|
669 |
|
---|
670 | #ifdef UPP
|
---|
671 | template <class T>
|
---|
672 | void BiVector<T>::Serialize(Stream& s) {
|
---|
673 | int n = items;
|
---|
674 | s / n;
|
---|
675 | if(s.IsLoading()) {
|
---|
676 | Clear();
|
---|
677 | while(n--)
|
---|
678 | s % AddTail();
|
---|
679 | }
|
---|
680 | else
|
---|
681 | for(int i = 0; i < items; i++)
|
---|
682 | s % operator[](i);
|
---|
683 | }
|
---|
684 | #endif
|
---|
685 |
|
---|
686 | // ------------------
|
---|
687 |
|
---|
688 | template <class T>
|
---|
689 | void BiArray<T>::Free() {
|
---|
690 | if(!bv.IsPicked())
|
---|
691 | for(int i = 0; i < GetCount(); i++)
|
---|
692 | delete (T *) bv[i];
|
---|
693 | }
|
---|
694 |
|
---|
695 | template <class T>
|
---|
696 | void BiArray<T>::DeepCopy0(const BiArray<T>& v) {
|
---|
697 | int n = v.GetCount();
|
---|
698 | bv.Clear();
|
---|
699 | bv.Reserve(v.GetCount());
|
---|
700 | for(int i = 0; i < n; i++)
|
---|
701 | bv.AddTail() = DeepCopyNew(v[i]);
|
---|
702 | }
|
---|
703 |
|
---|
704 | #ifdef UPP
|
---|
705 | template <class T>
|
---|
706 | void BiArray<T>::Serialize(Stream& s) {
|
---|
707 | int n = bv.GetCount();
|
---|
708 | s / n;
|
---|
709 | if(s.IsLoading()) {
|
---|
710 | Clear();
|
---|
711 | while(n--)
|
---|
712 | s % AddTail();
|
---|
713 | }
|
---|
714 | else
|
---|
715 | for(int i = 0; i < bv.GetCount(); i++)
|
---|
716 | s % operator[](i);
|
---|
717 | }
|
---|
718 | #endif
|
---|