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 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 20/*! 21 \class Vector 22 \brief A generic vector implementation. 23*/ 24template<typename Value> 25class Vector { 26public: 27 typedef VectorIterator<Value> Iterator; 28 typedef VectorIterator<const Value> ConstIterator; 29 30private: 31 static const size_t kDefaultChunkSize = 10; 32 static const size_t kMaximalChunkSize = 1024 * 1024; 33 34public: 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 79private: 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 85private: 86 size_t fCapacity; 87 size_t fChunkSize; 88 int32 fItemCount; 89 Value *fItems; 90}; 91 92 93// VectorIterator 94template<typename Value> 95class VectorIterator { 96private: 97 typedef VectorIterator<Value> Iterator; 98 99public: 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 171public: 172 inline VectorIterator<Value>(Value *element) 173 : fElement(element) 174 { 175 } 176 177 inline Value *Element() const 178 { 179 return fElement; 180 } 181 182protected: 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 230status_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 244status_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 256void 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 269void 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 284inline 285void 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 303status_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 326status_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 341int32 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 362typename _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 383typename _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 397inline 398int32 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 409inline 410bool 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 420void 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 437inline 438typename _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 453inline 454typename _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 469inline 470typename _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 485inline 486typename _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 501inline 502typename _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 517inline 518typename _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 530inline 531typename _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 545inline 546typename _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 560inline 561const 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 577inline 578Value & 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 596int32 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 616inline 617typename _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 634typename _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 651inline 652typename _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 669typename _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 682inline 683Value & 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 693inline 694const 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 714bool 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 744inline 745int32 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 763inline 764int32 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