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