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