1 // Common/MyVector.h 2 3 #ifndef ZIP7_INC_COMMON_MY_VECTOR_H 4 #define ZIP7_INC_COMMON_MY_VECTOR_H 5 6 #include <string.h> 7 8 #include "Common.h" 9 10 const unsigned k_VectorSizeMax = ((unsigned)1 << 31) - 1; 11 12 template <class T> 13 class CRecordVector 14 { 15 T *_items; 16 unsigned _size; 17 unsigned _capacity; 18 MoveItems(unsigned destIndex,unsigned srcIndex)19 void MoveItems(unsigned destIndex, unsigned srcIndex) 20 { 21 memmove(_items + destIndex, _items + srcIndex, (size_t)(_size - srcIndex) * sizeof(T)); 22 } 23 ReAllocForNewCapacity(const unsigned newCapacity)24 void ReAllocForNewCapacity(const unsigned newCapacity) 25 { 26 T *p; 27 Z7_ARRAY_NEW(p, T, newCapacity) 28 // p = new T[newCapacity]; 29 if (_size != 0) 30 memcpy(p, _items, (size_t)_size * sizeof(T)); 31 delete []_items; 32 _items = p; 33 _capacity = newCapacity; 34 } 35 36 public: 37 ReserveOnePosition()38 void ReserveOnePosition() 39 { 40 if (_size != _capacity) 41 return; 42 if (_capacity >= k_VectorSizeMax) 43 throw 2021; 44 const unsigned rem = k_VectorSizeMax - _capacity; 45 unsigned add = (_capacity >> 2) + 1; 46 if (add > rem) 47 add = rem; 48 ReAllocForNewCapacity(_capacity + add); 49 } 50 CRecordVector()51 CRecordVector(): _items(NULL), _size(0), _capacity(0) {} 52 CRecordVector(const CRecordVector & v)53 CRecordVector(const CRecordVector &v): _items(NULL), _size(0), _capacity(0) 54 { 55 const unsigned size = v.Size(); 56 if (size != 0) 57 { 58 // Z7_ARRAY_NEW(_items, T, size) 59 _items = new T[size]; 60 _size = size; 61 _capacity = size; 62 memcpy(_items, v._items, (size_t)size * sizeof(T)); 63 } 64 } 65 Size()66 unsigned Size() const { return _size; } IsEmpty()67 bool IsEmpty() const { return _size == 0; } 68 ConstructReserve(unsigned size)69 void ConstructReserve(unsigned size) 70 { 71 if (size != 0) 72 { 73 Z7_ARRAY_NEW(_items, T, size) 74 // _items = new T[size]; 75 _capacity = size; 76 } 77 } 78 Reserve(unsigned newCapacity)79 void Reserve(unsigned newCapacity) 80 { 81 if (newCapacity > _capacity) 82 { 83 if (newCapacity > k_VectorSizeMax) 84 throw 2021; 85 ReAllocForNewCapacity(newCapacity); 86 } 87 } 88 ChangeSize_KeepData(unsigned newSize)89 void ChangeSize_KeepData(unsigned newSize) 90 { 91 Reserve(newSize); 92 _size = newSize; 93 } 94 ClearAndReserve(unsigned newCapacity)95 void ClearAndReserve(unsigned newCapacity) 96 { 97 Clear(); 98 if (newCapacity > _capacity) 99 { 100 if (newCapacity > k_VectorSizeMax) 101 throw 2021; 102 delete []_items; 103 _items = NULL; 104 _capacity = 0; 105 Z7_ARRAY_NEW(_items, T, newCapacity) 106 // _items = new T[newCapacity]; 107 _capacity = newCapacity; 108 } 109 } 110 ClearAndSetSize(unsigned newSize)111 void ClearAndSetSize(unsigned newSize) 112 { 113 ClearAndReserve(newSize); 114 _size = newSize; 115 } 116 ReserveDown()117 void ReserveDown() 118 { 119 if (_size == _capacity) 120 return; 121 T *p = NULL; 122 if (_size != 0) 123 { 124 // Z7_ARRAY_NEW(p, T, _size) 125 p = new T[_size]; 126 memcpy(p, _items, (size_t)_size * sizeof(T)); 127 } 128 delete []_items; 129 _items = p; 130 _capacity = _size; 131 } 132 ~CRecordVector()133 ~CRecordVector() { delete []_items; } 134 ClearAndFree()135 void ClearAndFree() 136 { 137 delete []_items; 138 _items = NULL; 139 _size = 0; 140 _capacity = 0; 141 } 142 Clear()143 void Clear() { _size = 0; } 144 DeleteBack()145 void DeleteBack() { _size--; } 146 DeleteFrom(unsigned index)147 void DeleteFrom(unsigned index) 148 { 149 // if (index <= _size) 150 _size = index; 151 } 152 DeleteFrontal(unsigned num)153 void DeleteFrontal(unsigned num) 154 { 155 if (num != 0) 156 { 157 MoveItems(0, num); 158 _size -= num; 159 } 160 } 161 Delete(unsigned index)162 void Delete(unsigned index) 163 { 164 MoveItems(index, index + 1); 165 _size -= 1; 166 } 167 168 /* 169 void Delete(unsigned index, unsigned num) 170 { 171 if (num > 0) 172 { 173 MoveItems(index, index + num); 174 _size -= num; 175 } 176 } 177 */ 178 179 CRecordVector& operator=(const CRecordVector &v) 180 { 181 if (&v == this) 182 return *this; 183 const unsigned size = v.Size(); 184 if (size > _capacity) 185 { 186 delete []_items; 187 _capacity = 0; 188 _size = 0; 189 _items = NULL; 190 _items = new T[size]; 191 _capacity = size; 192 } 193 _size = size; 194 if (size != 0) 195 memcpy(_items, v._items, (size_t)size * sizeof(T)); 196 return *this; 197 } 198 199 CRecordVector& operator+=(const CRecordVector &v) 200 { 201 const unsigned size = v.Size(); 202 if (size != 0) 203 { 204 if (_size >= k_VectorSizeMax || size > k_VectorSizeMax - _size) 205 throw 2021; 206 const unsigned newSize = _size + size; 207 Reserve(newSize); 208 memcpy(_items + _size, v._items, (size_t)size * sizeof(T)); 209 _size = newSize; 210 } 211 return *this; 212 } 213 Add(const T item)214 unsigned Add(const T item) 215 { 216 ReserveOnePosition(); 217 const unsigned size = _size; 218 _size = size + 1; 219 _items[size] = item; 220 return size; 221 } 222 223 /* 224 unsigned Add2(const T &item) 225 { 226 ReserveOnePosition(); 227 const unsigned size = _size; 228 _size = size + 1; 229 _items[size] = item; 230 return size; 231 } 232 */ 233 AddInReserved(const T item)234 unsigned AddInReserved(const T item) 235 { 236 const unsigned size = _size; 237 _size = size + 1; 238 _items[size] = item; 239 return size; 240 } 241 Insert(unsigned index,const T item)242 void Insert(unsigned index, const T item) 243 { 244 ReserveOnePosition(); 245 MoveItems(index + 1, index); 246 _items[index] = item; 247 _size++; 248 } 249 InsertInReserved(unsigned index,const T item)250 void InsertInReserved(unsigned index, const T item) 251 { 252 MoveItems(index + 1, index); 253 _items[index] = item; 254 _size++; 255 } 256 MoveToFront(unsigned index)257 void MoveToFront(unsigned index) 258 { 259 if (index != 0) 260 { 261 T temp = _items[index]; 262 memmove(_items + 1, _items, (size_t)index * sizeof(T)); 263 _items[0] = temp; 264 } 265 } 266 267 const T& operator[](unsigned index) const { return _items[index]; } 268 T& operator[](unsigned index) { return _items[index]; } 269 const T& operator[](int index) const { return _items[(unsigned)index]; } 270 T& operator[](int index) { return _items[(unsigned)index]; } Front()271 const T& Front() const { return _items[0]; } Front()272 T& Front() { return _items[0]; } Back()273 const T& Back() const { return _items[(size_t)_size - 1]; } Back()274 T& Back() { return _items[(size_t)_size - 1]; } 275 276 /* 277 void Swap(unsigned i, unsigned j) 278 { 279 T temp = _items[i]; 280 _items[i] = _items[j]; 281 _items[j] = temp; 282 } 283 */ 284 FindInSorted(const T item,unsigned left,unsigned right)285 int FindInSorted(const T item, unsigned left, unsigned right) const 286 { 287 while (left != right) 288 { 289 // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); 290 const unsigned mid = (left + right) / 2; 291 const T midVal = (*this)[mid]; 292 if (item == midVal) 293 return (int)mid; 294 if (item < midVal) 295 right = mid; 296 else 297 left = mid + 1; 298 } 299 return -1; 300 } 301 FindInSorted2(const T & item,unsigned left,unsigned right)302 int FindInSorted2(const T &item, unsigned left, unsigned right) const 303 { 304 while (left != right) 305 { 306 // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); 307 const unsigned mid = (left + right) / 2; 308 const T& midVal = (*this)[mid]; 309 const int comp = item.Compare(midVal); 310 if (comp == 0) 311 return (int)mid; 312 if (comp < 0) 313 right = mid; 314 else 315 left = mid + 1; 316 } 317 return -1; 318 } 319 FindInSorted(const T item)320 int FindInSorted(const T item) const 321 { 322 return FindInSorted(item, 0, _size); 323 } 324 FindInSorted2(const T & item)325 int FindInSorted2(const T &item) const 326 { 327 return FindInSorted2(item, 0, _size); 328 } 329 AddToUniqueSorted(const T item)330 unsigned AddToUniqueSorted(const T item) 331 { 332 unsigned left = 0, right = _size; 333 while (left != right) 334 { 335 // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); 336 const unsigned mid = (left + right) / 2; 337 const T midVal = (*this)[mid]; 338 if (item == midVal) 339 return mid; 340 if (item < midVal) 341 right = mid; 342 else 343 left = mid + 1; 344 } 345 Insert(right, item); 346 return right; 347 } 348 AddToUniqueSorted2(const T & item)349 unsigned AddToUniqueSorted2(const T &item) 350 { 351 unsigned left = 0, right = _size; 352 while (left != right) 353 { 354 // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); 355 const unsigned mid = (left + right) / 2; 356 const T& midVal = (*this)[mid]; 357 const int comp = item.Compare(midVal); 358 if (comp == 0) 359 return mid; 360 if (comp < 0) 361 right = mid; 362 else 363 left = mid + 1; 364 } 365 Insert(right, item); 366 return right; 367 } 368 SortRefDown(T * p,unsigned k,unsigned size,int (* compare)(const T *,const T *,void *),void * param)369 static void SortRefDown(T* p, unsigned k, unsigned size, int (*compare)(const T*, const T*, void *), void *param) 370 { 371 T temp = p[k]; 372 for (;;) 373 { 374 unsigned s = (k << 1); 375 if (s > size) 376 break; 377 if (s < size && compare(p + s + 1, p + s, param) > 0) 378 s++; 379 if (compare(&temp, p + s, param) >= 0) 380 break; 381 p[k] = p[s]; 382 k = s; 383 } 384 p[k] = temp; 385 } 386 Sort(int (* compare)(const T *,const T *,void *),void * param)387 void Sort(int (*compare)(const T*, const T*, void *), void *param) 388 { 389 unsigned size = _size; 390 if (size <= 1) 391 return; 392 T* p = (&Front()) - 1; 393 { 394 unsigned i = size >> 1; 395 do 396 SortRefDown(p, i, size, compare, param); 397 while (--i != 0); 398 } 399 do 400 { 401 T temp = p[size]; 402 p[size--] = p[1]; 403 p[1] = temp; 404 SortRefDown(p, 1, size, compare, param); 405 } 406 while (size > 1); 407 } 408 SortRefDown2(T * p,unsigned k,unsigned size)409 static void SortRefDown2(T* p, unsigned k, unsigned size) 410 { 411 T temp = p[k]; 412 for (;;) 413 { 414 unsigned s = (k << 1); 415 if (s > size) 416 break; 417 if (s < size && p[(size_t)s + 1].Compare(p[s]) > 0) 418 s++; 419 if (temp.Compare(p[s]) >= 0) 420 break; 421 p[k] = p[s]; 422 k = s; 423 } 424 p[k] = temp; 425 } 426 Sort2()427 void Sort2() 428 { 429 unsigned size = _size; 430 if (size <= 1) 431 return; 432 T* p = (&Front()) - 1; 433 { 434 unsigned i = size >> 1; 435 do 436 SortRefDown2(p, i, size); 437 while (--i != 0); 438 } 439 do 440 { 441 T temp = p[size]; 442 p[size--] = p[1]; 443 p[1] = temp; 444 SortRefDown2(p, 1, size); 445 } 446 while (size > 1); 447 } 448 }; 449 450 typedef CRecordVector<int> CIntVector; 451 typedef CRecordVector<unsigned int> CUIntVector; 452 typedef CRecordVector<bool> CBoolVector; 453 typedef CRecordVector<unsigned char> CByteVector; 454 typedef CRecordVector<void *> CPointerVector; 455 456 template <class T> 457 class CObjectVector 458 { 459 CPointerVector _v; 460 public: Size()461 unsigned Size() const { return _v.Size(); } IsEmpty()462 bool IsEmpty() const { return _v.IsEmpty(); } ReserveDown()463 void ReserveDown() { _v.ReserveDown(); } 464 // void Reserve(unsigned newCapacity) { _v.Reserve(newCapacity); } ClearAndReserve(unsigned newCapacity)465 void ClearAndReserve(unsigned newCapacity) { Clear(); _v.ClearAndReserve(newCapacity); } 466 CObjectVector()467 CObjectVector() {} CObjectVector(const CObjectVector & v)468 CObjectVector(const CObjectVector &v) 469 { 470 const unsigned size = v.Size(); 471 _v.ConstructReserve(size); 472 for (unsigned i = 0; i < size; i++) 473 AddInReserved(v[i]); 474 } 475 CObjectVector& operator=(const CObjectVector &v) 476 { 477 if (&v == this) 478 return *this; 479 Clear(); 480 const unsigned size = v.Size(); 481 _v.Reserve(size); 482 for (unsigned i = 0; i < size; i++) 483 AddInReserved(v[i]); 484 return *this; 485 } 486 487 CObjectVector& operator+=(const CObjectVector &v) 488 { 489 const unsigned addSize = v.Size(); 490 if (addSize != 0) 491 { 492 const unsigned size = Size(); 493 if (size >= k_VectorSizeMax || addSize > k_VectorSizeMax - size) 494 throw 2021; 495 _v.Reserve(size + addSize); 496 for (unsigned i = 0; i < addSize; i++) 497 AddInReserved(v[i]); 498 } 499 return *this; 500 } 501 502 const T& operator[](unsigned index) const { return *((T *)_v[index]); } 503 T& operator[](unsigned index) { return *((T *)_v[index]); } 504 const T& operator[](int index) const { return *((T *)_v[(unsigned)index]); } 505 T& operator[](int index) { return *((T *)_v[(unsigned)index]); } Front()506 const T& Front() const { return operator[](0); } Front()507 T& Front() { return operator[](0); } Back()508 const T& Back() const { return *(T *)_v.Back(); } Back()509 T& Back() { return *(T *)_v.Back(); } 510 MoveToFront(unsigned index)511 void MoveToFront(unsigned index) { _v.MoveToFront(index); } 512 Add(const T & item)513 unsigned Add(const T& item) 514 { 515 _v.ReserveOnePosition(); 516 return AddInReserved(item); 517 } 518 AddInReserved(const T & item)519 unsigned AddInReserved(const T& item) 520 { 521 return _v.AddInReserved(new T(item)); 522 } 523 ReserveOnePosition()524 void ReserveOnePosition() 525 { 526 _v.ReserveOnePosition(); 527 } 528 AddInReserved_Ptr_of_new(T * ptr)529 unsigned AddInReserved_Ptr_of_new(T *ptr) 530 { 531 return _v.AddInReserved(ptr); 532 } 533 534 #define VECTOR_ADD_NEW_OBJECT(v, a) \ 535 (v).ReserveOnePosition(); \ 536 (v).AddInReserved_Ptr_of_new(new a); 537 538 AddNew()539 T& AddNew() 540 { 541 _v.ReserveOnePosition(); 542 T *p = new T; 543 _v.AddInReserved(p); 544 return *p; 545 } 546 AddNewInReserved()547 T& AddNewInReserved() 548 { 549 T *p = new T; 550 _v.AddInReserved(p); 551 return *p; 552 } 553 Insert(unsigned index,const T & item)554 void Insert(unsigned index, const T& item) 555 { 556 _v.ReserveOnePosition(); 557 _v.InsertInReserved(index, new T(item)); 558 } 559 InsertNew(unsigned index)560 T& InsertNew(unsigned index) 561 { 562 _v.ReserveOnePosition(); 563 T *p = new T; 564 _v.InsertInReserved(index, p); 565 return *p; 566 } 567 ~CObjectVector()568 ~CObjectVector() 569 { 570 for (unsigned i = _v.Size(); i != 0;) 571 delete (T *)_v[--i]; 572 } 573 ClearAndFree()574 void ClearAndFree() 575 { 576 Clear(); 577 _v.ClearAndFree(); 578 } 579 Clear()580 void Clear() 581 { 582 for (unsigned i = _v.Size(); i != 0;) 583 delete (T *)_v[--i]; 584 _v.Clear(); 585 } 586 DeleteFrom(unsigned index)587 void DeleteFrom(unsigned index) 588 { 589 const unsigned size = _v.Size(); 590 for (unsigned i = index; i < size; i++) 591 delete (T *)_v[i]; 592 _v.DeleteFrom(index); 593 } 594 DeleteFrontal(unsigned num)595 void DeleteFrontal(unsigned num) 596 { 597 for (unsigned i = 0; i < num; i++) 598 delete (T *)_v[i]; 599 _v.DeleteFrontal(num); 600 } 601 DeleteBack()602 void DeleteBack() 603 { 604 delete (T *)_v.Back(); 605 _v.DeleteBack(); 606 } 607 Delete(unsigned index)608 void Delete(unsigned index) 609 { 610 delete (T *)_v[index]; 611 _v.Delete(index); 612 } 613 // void Delete(int index) { Delete((unsigned)index); } 614 615 /* 616 void Delete(unsigned index, unsigned num) 617 { 618 for (unsigned i = 0; i < num; i++) 619 delete (T *)_v[index + i]; 620 _v.Delete(index, num); 621 } 622 */ 623 624 /* 625 int Find(const T& item) const 626 { 627 unsigned size = Size(); 628 for (unsigned i = 0; i < size; i++) 629 if (item == (*this)[i]) 630 return i; 631 return -1; 632 } 633 */ 634 FindInSorted(const T & item)635 int FindInSorted(const T& item) const 636 { 637 unsigned left = 0, right = Size(); 638 while (left != right) 639 { 640 // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); 641 const unsigned mid = (left + right) / 2; 642 const T& midVal = (*this)[mid]; 643 const int comp = item.Compare(midVal); 644 if (comp == 0) 645 return (int)mid; 646 if (comp < 0) 647 right = mid; 648 else 649 left = mid + 1; 650 } 651 return -1; 652 } 653 AddToUniqueSorted(const T & item)654 unsigned AddToUniqueSorted(const T& item) 655 { 656 unsigned left = 0, right = Size(); 657 while (left != right) 658 { 659 // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); 660 const unsigned mid = (left + right) / 2; 661 const T& midVal = (*this)[mid]; 662 const int comp = item.Compare(midVal); 663 if (comp == 0) 664 return mid; 665 if (comp < 0) 666 right = mid; 667 else 668 left = mid + 1; 669 } 670 Insert(right, item); 671 return right; 672 } 673 674 /* 675 unsigned AddToSorted(const T& item) 676 { 677 unsigned left = 0, right = Size(); 678 while (left != right) 679 { 680 // const unsigned mid = (unsigned)(((size_t)left + (size_t)right) / 2); 681 const unsigned mid = (left + right) / 2; 682 const T& midVal = (*this)[mid]; 683 const int comp = item.Compare(midVal); 684 if (comp == 0) 685 { 686 right = mid + 1; 687 break; 688 } 689 if (comp < 0) 690 right = mid; 691 else 692 left = mid + 1; 693 } 694 Insert(right, item); 695 return right; 696 } 697 */ 698 Sort(int (* compare)(void * const *,void * const *,void *),void * param)699 void Sort(int (*compare)(void *const *, void *const *, void *), void *param) 700 { _v.Sort(compare, param); } 701 CompareObjectItems(void * const * a1,void * const * a2,void *)702 static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */) 703 { return (*(*((const T *const *)a1))).Compare(*(*((const T *const *)a2))); } 704 Sort()705 void Sort() { _v.Sort(CompareObjectItems, NULL); } 706 }; 707 708 #define FOR_VECTOR(_i_, _v_) for (unsigned _i_ = 0; _i_ < (_v_).Size(); _i_++) 709 710 #endif 711