1 /* 2 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * All rights reserved. Distributed under the terms of the MIT license. 4 */ 5 #ifndef _VECTOR_H 6 #define _VECTOR_H 7 8 #include <new> 9 #include <stdlib.h> 10 #include <string.h> 11 12 #include <SupportDefs.h> 13 14 template<typename Value> class VectorIterator; 15 16 // for convenience 17 #define _VECTOR_TEMPLATE_LIST template<typename Value> 18 #define _VECTOR_CLASS_NAME Vector<Value> 19 20 /*! 21 \class Vector 22 \brief A generic vector implementation. 23 */ 24 template<typename Value> 25 class Vector { 26 public: 27 typedef VectorIterator<Value> Iterator; 28 typedef VectorIterator<const Value> ConstIterator; 29 30 private: 31 static const size_t kDefaultChunkSize = 10; 32 static const size_t kMaximalChunkSize = 1024 * 1024; 33 34 public: 35 Vector(size_t chunkSize = kDefaultChunkSize); 36 ~Vector(); 37 38 status_t PushFront(const Value &value); 39 status_t PushBack(const Value &value); 40 41 void PopFront(); 42 void PopBack(); 43 44 status_t Insert(const Value &value, int32 index); 45 status_t Insert(const Value &value, const Iterator &iterator); 46 47 int32 Remove(const Value &value); 48 Iterator Erase(int32 index); 49 Iterator Erase(const Iterator &iterator); 50 51 inline int32 Count() const; 52 inline bool IsEmpty() const; 53 void MakeEmpty(); 54 55 inline Iterator Begin(); 56 inline ConstIterator Begin() const; 57 inline Iterator End(); 58 inline ConstIterator End() const; 59 inline Iterator Null(); 60 inline ConstIterator Null() const; 61 inline Iterator IteratorForIndex(int32 index); 62 inline ConstIterator IteratorForIndex(int32 index) const; 63 64 inline const Value &ElementAt(int32 index) const; 65 inline Value &ElementAt(int32 index); 66 67 int32 IndexOf(const Value &value, int32 start = 0) const; 68 Iterator Find(const Value &value); 69 Iterator Find(const Value &value, const Iterator &start); 70 ConstIterator Find(const Value &value) const; 71 ConstIterator Find(const Value &value, const ConstIterator &start) const; 72 73 inline Value &operator[](int32 index); 74 inline const Value &operator[](int32 index) const; 75 76 // debugging 77 int32 GetCapacity() const { return fCapacity; } 78 79 private: 80 inline static void _MoveItems(Value *values, int32 offset, int32 count); 81 bool _Resize(size_t count); 82 inline int32 _IteratorIndex(const Iterator &iterator) const; 83 inline int32 _IteratorIndex(const ConstIterator &iterator) const; 84 85 private: 86 size_t fCapacity; 87 size_t fChunkSize; 88 int32 fItemCount; 89 Value *fItems; 90 }; 91 92 93 // VectorIterator 94 template<typename Value> 95 class VectorIterator { 96 private: 97 typedef VectorIterator<Value> Iterator; 98 99 public: 100 inline VectorIterator<Value>() 101 : fElement(NULL) 102 { 103 } 104 105 inline VectorIterator<Value>(const Iterator &other) 106 : fElement(other.fElement) 107 { 108 } 109 110 inline Iterator &operator++() 111 { 112 if (fElement) 113 ++fElement; 114 return *this; 115 } 116 117 inline Iterator operator++(int) 118 { 119 Iterator it(*this); 120 ++*this; 121 return it; 122 } 123 124 inline Iterator &operator--() 125 { 126 if (fElement) 127 --fElement; 128 return *this; 129 } 130 131 inline Iterator operator--(int) 132 { 133 Iterator it(*this); 134 --*this; 135 return it; 136 } 137 138 inline Iterator &operator=(const Iterator &other) 139 { 140 fElement = other.fElement; 141 return *this; 142 } 143 144 145 inline bool operator==(const Iterator &other) const 146 { 147 return (fElement == other.fElement); 148 } 149 150 inline bool operator!=(const Iterator &other) const 151 { 152 return !(*this == other); 153 } 154 155 inline Value &operator*() const 156 { 157 return *fElement; 158 } 159 160 inline Value *operator->() const 161 { 162 return fElement; 163 } 164 165 inline operator bool() const 166 { 167 return fElement; 168 } 169 170 // private 171 public: 172 inline VectorIterator<Value>(Value *element) 173 : fElement(element) 174 { 175 } 176 177 inline Value *Element() const 178 { 179 return fElement; 180 } 181 182 protected: 183 Value *fElement; 184 }; 185 186 187 // Vector 188 189 // constructor 190 /*! \brief Creates an empty vector. 191 \param chunkSize The granularity for the vector's capacity, i.e. the 192 minimal number of elements the capacity grows or shrinks when 193 necessary. 194 */ 195 _VECTOR_TEMPLATE_LIST 196 _VECTOR_CLASS_NAME::Vector(size_t chunkSize) 197 : fCapacity(0), 198 fChunkSize(chunkSize), 199 fItemCount(0), 200 fItems(NULL) 201 { 202 if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize) 203 fChunkSize = kDefaultChunkSize; 204 _Resize(0); 205 } 206 207 // destructor 208 /*! \brief Frees all resources associated with the object. 209 210 The contained elements are destroyed. Note, that, if the element 211 type is a pointer type, only the pointer is destroyed, not the object 212 it points to. 213 */ 214 _VECTOR_TEMPLATE_LIST 215 _VECTOR_CLASS_NAME::~Vector() 216 { 217 MakeEmpty(); 218 free(fItems); 219 } 220 221 // PushFront 222 /*! \brief Inserts a copy of the supplied value at the beginning of the 223 vector. 224 \param value The element to be inserted. 225 \return 226 - \c B_OK: Everything went fine. 227 - \c B_NO_MEMORY: Insufficient memory for this operation. 228 */ 229 _VECTOR_TEMPLATE_LIST 230 status_t 231 _VECTOR_CLASS_NAME::PushFront(const Value &value) 232 { 233 return Insert(value, 0); 234 } 235 236 // PushBack 237 /*! \brief Inserts a copy of the supplied value at the end of the vector. 238 \param value The element to be inserted. 239 \return 240 - \c B_OK: Everything went fine. 241 - \c B_NO_MEMORY: Insufficient memory for this operation. 242 */ 243 _VECTOR_TEMPLATE_LIST 244 status_t 245 _VECTOR_CLASS_NAME::PushBack(const Value &value) 246 { 247 return Insert(value, fItemCount); 248 } 249 250 // PopFront 251 /*! \brief Removes the first element of the vector. 252 253 Invocation on an empty vector is harmless. 254 */ 255 _VECTOR_TEMPLATE_LIST 256 void 257 _VECTOR_CLASS_NAME::PopFront() 258 { 259 if (fItemCount > 0) 260 Erase(0); 261 } 262 263 // PopBack 264 /*! \brief Removes the last element of the vector. 265 266 Invocation on an empty vector is harmless. 267 */ 268 _VECTOR_TEMPLATE_LIST 269 void 270 _VECTOR_CLASS_NAME::PopBack() 271 { 272 if (fItemCount > 0) 273 Erase(fItemCount - 1); 274 } 275 276 // _MoveItems 277 /*! \brief Moves elements within an array. 278 \param items The elements to be moved. 279 \param offset The index to which the elements shall be moved. May be 280 negative. 281 \param count The number of elements to be moved. 282 */ 283 _VECTOR_TEMPLATE_LIST 284 inline 285 void 286 _VECTOR_CLASS_NAME::_MoveItems(Value* items, int32 offset, int32 count) 287 { 288 if (count > 0 && offset != 0) 289 memmove(items + offset, items, count * sizeof(Value)); 290 } 291 292 // Insert 293 /*! \brief Inserts a copy of the the supplied value at the given index. 294 \param value The value to be inserted. 295 \param index The index at which to insert the new element. It must 296 hold: 0 <= \a index <= Count(). 297 \return 298 - \c B_OK: Everything went fine. 299 - \c B_BAD_VALUE: \a index is out of range. 300 - \c B_NO_MEMORY: Insufficient memory for this operation. 301 */ 302 _VECTOR_TEMPLATE_LIST 303 status_t 304 _VECTOR_CLASS_NAME::Insert(const Value &value, int32 index) 305 { 306 if (index < 0 || index > fItemCount) 307 return B_BAD_VALUE; 308 if (!_Resize(fItemCount + 1)) 309 return B_NO_MEMORY; 310 _MoveItems(fItems + index, 1, fItemCount - index - 1); 311 new(fItems + index) Value(value); 312 return B_OK; 313 } 314 315 // Insert 316 /*! \brief Inserts a copy of the the supplied value at the given position. 317 \param value The value to be inserted. 318 \param iterator An iterator specifying the position at which to insert 319 the new element. 320 \return 321 - \c B_OK: Everything went fine. 322 - \c B_BAD_VALUE: \a iterator is is invalid. 323 - \c B_NO_MEMORY: Insufficient memory for this operation. 324 */ 325 _VECTOR_TEMPLATE_LIST 326 status_t 327 _VECTOR_CLASS_NAME::Insert(const Value &value, const Iterator &iterator) 328 { 329 int32 index = _IteratorIndex(iterator); 330 if (index >= 0) 331 return Insert(value, index); 332 return B_BAD_VALUE; 333 } 334 335 // Remove 336 /*! \brief Removes all elements of the supplied value. 337 \param value The value of the elements to be removed. 338 \return The number of removed occurrences. 339 */ 340 _VECTOR_TEMPLATE_LIST 341 int32 342 _VECTOR_CLASS_NAME::Remove(const Value &value) 343 { 344 int32 count = 0; 345 for (int32 i = fItemCount - 1; i >= 0; i--) { 346 if (ElementAt(i) == value) { 347 Erase(i); 348 count++; 349 } 350 } 351 return count; 352 } 353 354 // Erase 355 /*! \brief Removes the element at the given index. 356 \param index The position of the element to be removed. 357 \return An iterator referring to the element now being located at index 358 \a index (End(), if it was the last element that has been 359 removed), or Null(), if \a index was out of range. 360 */ 361 _VECTOR_TEMPLATE_LIST 362 typename _VECTOR_CLASS_NAME::Iterator 363 _VECTOR_CLASS_NAME::Erase(int32 index) 364 { 365 if (index >= 0 && index < fItemCount) { 366 fItems[index].~Value(); 367 _MoveItems(fItems + index + 1, -1, fItemCount - index - 1); 368 _Resize(fItemCount - 1); 369 return Iterator(fItems + index); 370 } 371 return Null(); 372 } 373 374 // Erase 375 /*! \brief Removes the element at the given position. 376 \param iterator An iterator referring to the element to be removed. 377 \return An iterator referring to the element succeeding the removed 378 one (End(), if it was the last element that has been 379 removed), or Null(), if \a iterator was an invalid iterator 380 (in this case including End()). 381 */ 382 _VECTOR_TEMPLATE_LIST 383 typename _VECTOR_CLASS_NAME::Iterator 384 _VECTOR_CLASS_NAME::Erase(const Iterator &iterator) 385 { 386 int32 index = _IteratorIndex(iterator); 387 if (index >= 0 && index < fItemCount) 388 return Erase(index); 389 return Null(); 390 } 391 392 // Count 393 /*! \brief Returns the number of elements the vector contains. 394 \return The number of elements the vector contains. 395 */ 396 _VECTOR_TEMPLATE_LIST 397 inline 398 int32 399 _VECTOR_CLASS_NAME::Count() const 400 { 401 return fItemCount; 402 } 403 404 // IsEmpty 405 /*! \brief Returns whether the vector is empty. 406 \return \c true, if the vector is empty, \c false otherwise. 407 */ 408 _VECTOR_TEMPLATE_LIST 409 inline 410 bool 411 _VECTOR_CLASS_NAME::IsEmpty() const 412 { 413 return (fItemCount == 0); 414 } 415 416 // MakeEmpty 417 /*! \brief Removes all elements from the vector. 418 */ 419 _VECTOR_TEMPLATE_LIST 420 void 421 _VECTOR_CLASS_NAME::MakeEmpty() 422 { 423 for (int32 i = 0; i < fItemCount; i++) 424 fItems[i].~Value(); 425 _Resize(0); 426 } 427 428 // Begin 429 /*! \brief Returns an iterator referring to the beginning of the vector. 430 431 If the vector is not empty, Begin() refers to its first element, 432 otherwise it is equal to End() and must not be dereferenced! 433 434 \return An iterator referring to the beginning of the vector. 435 */ 436 _VECTOR_TEMPLATE_LIST 437 inline 438 typename _VECTOR_CLASS_NAME::Iterator 439 _VECTOR_CLASS_NAME::Begin() 440 { 441 return Iterator(fItems); 442 } 443 444 // Begin 445 /*! \brief Returns an iterator referring to the beginning of the vector. 446 447 If the vector is not empty, Begin() refers to its first element, 448 otherwise it is equal to End() and must not be dereferenced! 449 450 \return An iterator referring to the beginning of the vector. 451 */ 452 _VECTOR_TEMPLATE_LIST 453 inline 454 typename _VECTOR_CLASS_NAME::ConstIterator 455 _VECTOR_CLASS_NAME::Begin() const 456 { 457 return ConstIterator(fItems); 458 } 459 460 // End 461 /*! \brief Returns an iterator referring to the end of the vector. 462 463 The position identified by End() is the one succeeding the last 464 element, i.e. it must not be dereferenced! 465 466 \return An iterator referring to the end of the vector. 467 */ 468 _VECTOR_TEMPLATE_LIST 469 inline 470 typename _VECTOR_CLASS_NAME::Iterator 471 _VECTOR_CLASS_NAME::End() 472 { 473 return Iterator(fItems + fItemCount); 474 } 475 476 // End 477 /*! \brief Returns an iterator referring to the end of the vector. 478 479 The position identified by End() is the one succeeding the last 480 element, i.e. it must not be dereferenced! 481 482 \return An iterator referring to the end of the vector. 483 */ 484 _VECTOR_TEMPLATE_LIST 485 inline 486 typename _VECTOR_CLASS_NAME::ConstIterator 487 _VECTOR_CLASS_NAME::End() const 488 { 489 return ConstIterator(fItems + fItemCount); 490 } 491 492 // Null 493 /*! \brief Returns an invalid iterator. 494 495 Null() is used as a return value, if something went wrong. It must 496 neither be incremented or decremented nor dereferenced! 497 498 \return An invalid iterator. 499 */ 500 _VECTOR_TEMPLATE_LIST 501 inline 502 typename _VECTOR_CLASS_NAME::Iterator 503 _VECTOR_CLASS_NAME::Null() 504 { 505 return Iterator(NULL); 506 } 507 508 // Null 509 /*! \brief Returns an invalid iterator. 510 511 Null() is used as a return value, if something went wrong. It must 512 neither be incremented or decremented nor dereferenced! 513 514 \return An invalid iterator. 515 */ 516 _VECTOR_TEMPLATE_LIST 517 inline 518 typename _VECTOR_CLASS_NAME::ConstIterator 519 _VECTOR_CLASS_NAME::Null() const 520 { 521 return ConstIterator(NULL); 522 } 523 524 // IteratorForIndex 525 /*! \brief Returns an iterator for a given index. 526 \return An iterator referring to the same element as \a index, or 527 End(), if \a index is out of range. 528 */ 529 _VECTOR_TEMPLATE_LIST 530 inline 531 typename _VECTOR_CLASS_NAME::Iterator 532 _VECTOR_CLASS_NAME::IteratorForIndex(int32 index) 533 { 534 if (index >= 0 && index <= fItemCount) 535 return Iterator(fItems + index); 536 return End(); 537 } 538 539 // IteratorForIndex 540 /*! \brief Returns an iterator for a given index. 541 \return An iterator referring to the same element as \a index, or 542 End(), if \a index is out of range. 543 */ 544 _VECTOR_TEMPLATE_LIST 545 inline 546 typename _VECTOR_CLASS_NAME::ConstIterator 547 _VECTOR_CLASS_NAME::IteratorForIndex(int32 index) const 548 { 549 if (index >= 0 && index <= fItemCount) 550 return ConstIterator(fItems + index); 551 return End(); 552 } 553 554 // ElementAt 555 /*! \brief Returns the element at a given index. 556 \param index The index identifying the element to be returned. 557 \return The element identified by the given index. 558 */ 559 _VECTOR_TEMPLATE_LIST 560 inline 561 const Value & 562 _VECTOR_CLASS_NAME::ElementAt(int32 index) const 563 { 564 if (index >= 0 && index < fItemCount) 565 return fItems[index]; 566 // Return the 0th element by default. Unless the allocation failed, there 567 // is always a 0th element -- uninitialized perhaps. 568 return fItems[0]; 569 } 570 571 // ElementAt 572 /*! \brief Returns the element at a given index. 573 \param index The index identifying the element to be returned. 574 \return The element identified by the given index. 575 */ 576 _VECTOR_TEMPLATE_LIST 577 inline 578 Value & 579 _VECTOR_CLASS_NAME::ElementAt(int32 index) 580 { 581 if (index >= 0 && index < fItemCount) 582 return fItems[index]; 583 // Return the 0th element by default. Unless the allocation failed, there 584 // is always a 0th element -- uninitialized perhaps. 585 return fItems[0]; 586 } 587 588 // IndexOf 589 /*! \brief Returns the index of the next element with the specified value. 590 \param value The value of the element to be found. 591 \param start The index at which to be started to search for the element. 592 \return The index of the found element, or \c -1, if no further element 593 with the given value could be found or \a index is out of range. 594 */ 595 _VECTOR_TEMPLATE_LIST 596 int32 597 _VECTOR_CLASS_NAME::IndexOf(const Value &value, int32 start) const 598 { 599 if (start >= 0) { 600 for (int32 i = start; i < fItemCount; i++) { 601 if (fItems[i] == value) 602 return i; 603 } 604 } 605 return -1; 606 } 607 608 // Find 609 /*! \brief Returns an iterator referring to the next element with the 610 specified value. 611 \param value The value of the element to be found. 612 \return An iterator referring to the found element, or End(), if no 613 further with the given value could be found. 614 */ 615 _VECTOR_TEMPLATE_LIST 616 inline 617 typename _VECTOR_CLASS_NAME::Iterator 618 _VECTOR_CLASS_NAME::Find(const Value &value) 619 { 620 return Find(value, Begin()); 621 } 622 623 // Find 624 /*! \brief Returns an iterator referring to the next element with the 625 specified value. 626 \param value The value of the element to be found. 627 \param start And iterator specifying where to start searching for the 628 element. 629 \return An iterator referring to the found element, or End(), if no 630 further with the given value could be found or \a start was 631 invalid. 632 */ 633 _VECTOR_TEMPLATE_LIST 634 typename _VECTOR_CLASS_NAME::Iterator 635 _VECTOR_CLASS_NAME::Find(const Value &value, const Iterator &start) 636 { 637 int32 index = IndexOf(value, _IteratorIndex(start)); 638 if (index >= 0) 639 return Iterator(fItems + index); 640 return End(); 641 } 642 643 // Find 644 /*! \brief Returns an iterator referring to the of the next element with the 645 specified value. 646 \param value The value of the element to be found. 647 \return An iterator referring to the found element, or End(), if no 648 further with the given value could be found. 649 */ 650 _VECTOR_TEMPLATE_LIST 651 inline 652 typename _VECTOR_CLASS_NAME::ConstIterator 653 _VECTOR_CLASS_NAME::Find(const Value &value) const 654 { 655 return Find(value, Begin()); 656 } 657 658 // Find 659 /*! \brief Returns an iterator referring to the of the next element with the 660 specified value. 661 \param value The value of the element to be found. 662 \param start And iterator specifying where to start searching for the 663 element. 664 \return An iterator referring to the found element, or End(), if no 665 further with the given value could be found or \a start was 666 invalid. 667 */ 668 _VECTOR_TEMPLATE_LIST 669 typename _VECTOR_CLASS_NAME::ConstIterator 670 _VECTOR_CLASS_NAME::Find(const Value &value, const ConstIterator &start) const 671 { 672 int32 index = IndexOf(value, _IteratorIndex(start)); 673 if (index >= 0) 674 return ConstIterator(fItems + index); 675 return End(); 676 } 677 678 // [] 679 /*! \brief Semantically equivalent to ElementAt(). 680 */ 681 _VECTOR_TEMPLATE_LIST 682 inline 683 Value & 684 _VECTOR_CLASS_NAME::operator[](int32 index) 685 { 686 return ElementAt(index); 687 } 688 689 // [] 690 /*! \brief Semantically equivalent to ElementAt(). 691 */ 692 _VECTOR_TEMPLATE_LIST 693 inline 694 const Value & 695 _VECTOR_CLASS_NAME::operator[](int32 index) const 696 { 697 return ElementAt(index); 698 } 699 700 // _Resize 701 /*! \brief Resizes the vector. 702 703 The internal element array will be grown or shrunk to the next multiple 704 of \a fChunkSize >= \a count, but no less than \a fChunkSize. 705 706 Also adjusts \a fItemCount according to the supplied \a count, but does 707 not invoke a destructor or constructor on any element. 708 709 \param count The number of element. 710 \return \c true, if everything went fine, \c false, if the memory 711 allocation failed. 712 */ 713 _VECTOR_TEMPLATE_LIST 714 bool 715 _VECTOR_CLASS_NAME::_Resize(size_t count) 716 { 717 bool result = true; 718 // calculate the new capacity 719 int32 newSize = count; 720 if (newSize <= 0) 721 newSize = 1; 722 newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize; 723 // resize if necessary 724 if ((size_t)newSize != fCapacity) { 725 Value* newItems = (Value*)realloc(fItems, newSize * sizeof(Value)); 726 if (newItems) { 727 fItems = newItems; 728 fCapacity = newSize; 729 } else 730 result = false; 731 } 732 if (result) 733 fItemCount = count; 734 return result; 735 } 736 737 // _IteratorIndex 738 /*! \brief Returns index of the element the supplied iterator refers to. 739 \return The index of the element the supplied iterator refers to, or 740 \c -1, if the iterator is invalid (End() is considered valid 741 here, and Count() is returned). 742 */ 743 _VECTOR_TEMPLATE_LIST 744 inline 745 int32 746 _VECTOR_CLASS_NAME::_IteratorIndex(const Iterator &iterator) const 747 { 748 if (iterator.Element()) { 749 int32 index = iterator.Element() - fItems; 750 if (index >= 0 && index <= fItemCount) 751 return index; 752 } 753 return -1; 754 } 755 756 // _IteratorIndex 757 /*! \brief Returns index of the element the supplied iterator refers to. 758 \return The index of the element the supplied iterator refers to, or 759 \c -1, if the iterator is invalid (End() is considered valid 760 here, and Count() is returned). 761 */ 762 _VECTOR_TEMPLATE_LIST 763 inline 764 int32 765 _VECTOR_CLASS_NAME::_IteratorIndex(const ConstIterator &iterator) const 766 { 767 if (iterator.Element()) { 768 int32 index = iterator.Element() - fItems; 769 if (index >= 0 && index <= fItemCount) 770 return index; 771 } 772 return -1; 773 } 774 775 #endif // _VECTOR_H 776