[1526] | 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
|
---|