Simbody
3.5
|
00001 #ifndef SimTK_SimTKCOMMON_ARRAY_H_ 00002 #define SimTK_SimTKCOMMON_ARRAY_H_ 00003 00004 /* -------------------------------------------------------------------------- * 00005 * Simbody(tm): SimTKcommon * 00006 * -------------------------------------------------------------------------- * 00007 * This is part of the SimTK biosimulation toolkit originating from * 00008 * Simbios, the NIH National Center for Physics-Based Simulation of * 00009 * Biological Structures at Stanford, funded under the NIH Roadmap for * 00010 * Medical Research, grant U54 GM072970. See https://simtk.org/home/simbody. * 00011 * * 00012 * Portions copyright (c) 2010-13 Stanford University and the Authors. * 00013 * Authors: Michael Sherman * 00014 * Contributors: * 00015 * * 00016 * Licensed under the Apache License, Version 2.0 (the "License"); you may * 00017 * not use this file except in compliance with the License. You may obtain a * 00018 * copy of the License at http://www.apache.org/licenses/LICENSE-2.0. * 00019 * * 00020 * Unless required by applicable law or agreed to in writing, software * 00021 * distributed under the License is distributed on an "AS IS" BASIS, * 00022 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 00023 * See the License for the specific language governing permissions and * 00024 * limitations under the License. * 00025 * -------------------------------------------------------------------------- */ 00026 00033 #include "SimTKcommon/internal/common.h" 00034 #include "SimTKcommon/internal/ExceptionMacros.h" 00035 #include "SimTKcommon/internal/Serialize.h" 00036 00037 #include <algorithm> 00038 #include <iterator> 00039 #include <vector> 00040 #include <ostream> 00041 #include <climits> 00042 #include <typeinfo> 00043 00044 namespace SimTK { 00045 00046 // These are the classes defined in this header. 00047 template <class X> struct ArrayIndexTraits; 00048 template <class T, class X=unsigned> class ArrayViewConst_; 00049 template <class T, class X=unsigned> class ArrayView_; 00050 template <class T, class X=unsigned> class Array_; 00051 00052 // NOTE: I have attempted to force the compilers to inline certain trivial 00053 // methods here because I observed Visual C++ 2013 fail to inline operator[] 00054 // in a performance-critical method (getCacheEntry() to be specific). It is 00055 // essential that there be no overhead introduced by the Array_ classes, which 00056 // Simbody uses extensively specifically because std::vector was too slow. 00057 // (sherm 20140404). 00058 00059 //============================================================================== 00060 // CLASS ArrayIndexTraits 00061 //============================================================================== 00062 00105 template <class X> struct ArrayIndexTraits { 00108 typedef typename X::size_type size_type; 00111 typedef typename X::difference_type difference_type; 00114 static size_type max_size() {return X::max_size();} 00115 }; 00116 00119 template <> struct ArrayIndexTraits<unsigned> { 00120 typedef unsigned size_type; 00121 typedef int difference_type; 00122 static size_type max_size() {return (unsigned)INT_MAX;} 00123 }; 00124 00126 template <> struct ArrayIndexTraits<int> { 00127 typedef int size_type; 00128 typedef int difference_type; 00129 static size_type max_size() {return INT_MAX;} 00130 }; 00131 00139 template <> struct ArrayIndexTraits<unsigned long> { 00140 typedef unsigned long size_type; 00141 typedef long difference_type; 00142 static size_type max_size() {return (unsigned long)LONG_MAX;} 00143 }; 00144 00152 template <> struct ArrayIndexTraits<long> { 00153 typedef long size_type; 00154 typedef long difference_type; 00155 static size_type max_size() {return LONG_MAX;} 00156 }; 00157 00163 template <> struct ArrayIndexTraits<unsigned short> { 00164 typedef unsigned short size_type; 00165 typedef int difference_type; 00166 static size_type max_size() {return USHRT_MAX;} 00167 }; 00168 00173 template <> struct ArrayIndexTraits<short> { 00174 typedef short size_type; 00175 typedef short difference_type; 00176 static size_type max_size() {return SHRT_MAX;} 00177 }; 00178 00179 00184 template <> struct ArrayIndexTraits<unsigned char> { 00185 typedef unsigned char size_type; 00186 typedef short difference_type; 00187 static size_type max_size() {return UCHAR_MAX;} // not CHAR_MAX 00188 }; 00189 00195 template <> struct ArrayIndexTraits<signed char> { 00196 typedef signed char size_type; 00197 typedef signed char difference_type; 00198 static size_type max_size() {return SCHAR_MAX;} 00199 }; 00200 00207 template <> struct ArrayIndexTraits<char> { 00208 typedef char size_type; 00209 typedef signed char difference_type; 00210 static size_type max_size() {return (char)SCHAR_MAX;} 00211 }; 00212 00218 template <> struct ArrayIndexTraits<bool> { 00219 typedef unsigned char size_type; 00220 typedef signed char difference_type; 00221 static size_type max_size() {return 2;} 00222 }; 00223 00226 template <> struct ArrayIndexTraits<unsigned long long> { 00227 typedef unsigned long long size_type; 00228 typedef long long difference_type; 00229 static size_type max_size() 00230 {return (unsigned long long)LLONG_MAX;} 00231 }; 00232 00235 template <> struct ArrayIndexTraits<long long> { 00236 typedef long long size_type; 00237 typedef long long difference_type; 00238 static size_type max_size() {return LLONG_MAX;} 00239 }; 00240 00241 // Don't show this in Doxygen. 00243 // This helper class decides what integral type we should use to best pack 00244 // the index type's size_type representation. The idea is to pack the whole 00245 // Array_ structure into 8 bytes on a 32 bit machine, 16 bytes on a 64 bit 00246 // machine, using the largest integral type that will work, giving a layout 00247 // like this: | data pointer | 00248 // | nUsed | nAllocated | 00249 00250 // The default implementation just uses the integral type itself. 00251 template <class Integral, class is64Bit> struct ArrayIndexPackTypeHelper 00252 { typedef Integral packed_size_type;}; 00253 00254 // On 32 bit machine, pack anything smaller than a short into a short. 00255 template<> struct ArrayIndexPackTypeHelper<bool,FalseType> 00256 { typedef unsigned short packed_size_type;}; 00257 template<> struct ArrayIndexPackTypeHelper<char,FalseType> 00258 { typedef unsigned short packed_size_type;}; 00259 template<> struct ArrayIndexPackTypeHelper<unsigned char,FalseType> 00260 { typedef unsigned short packed_size_type;}; 00261 template<> struct ArrayIndexPackTypeHelper<signed char,FalseType> 00262 { typedef short packed_size_type;}; 00263 00264 // On 64 bit machine, pack anything smaller than an int into an int. 00265 template<> struct ArrayIndexPackTypeHelper<bool,TrueType> 00266 { typedef unsigned int packed_size_type;}; 00267 template<> struct ArrayIndexPackTypeHelper<char,TrueType> 00268 { typedef unsigned int packed_size_type;}; 00269 template<> struct ArrayIndexPackTypeHelper<unsigned char,TrueType> 00270 { typedef unsigned int packed_size_type;}; 00271 template<> struct ArrayIndexPackTypeHelper<signed char,TrueType> 00272 { typedef int packed_size_type;}; 00273 template<> struct ArrayIndexPackTypeHelper<unsigned short,TrueType> 00274 { typedef unsigned int packed_size_type;}; 00275 template<> struct ArrayIndexPackTypeHelper<short,TrueType> 00276 { typedef int packed_size_type;}; 00277 00278 template <class Integral> struct ArrayIndexPackType 00279 { typedef typename ArrayIndexPackTypeHelper<Integral,Is64BitPlatformType> 00280 ::packed_size_type packed_size_type;}; 00288 //============================================================================== 00289 // CLASS ArrayViewConst_ 00290 //============================================================================== 00317 template <class T, class X> class ArrayViewConst_ { 00318 public: 00319 00320 00321 //------------------------------------------------------------------------------ 00328 typedef T value_type; 00330 typedef X index_type; 00332 typedef T* pointer; 00334 typedef const T* const_pointer; 00336 typedef T& reference; 00338 typedef const T& const_reference; 00340 typedef T* iterator; 00342 typedef const T* const_iterator; 00344 typedef std::reverse_iterator<iterator> reverse_iterator; 00346 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00348 typedef typename ArrayIndexTraits<X>::size_type size_type; 00351 typedef typename ArrayIndexTraits<X>::difference_type difference_type; 00353 typedef typename ArrayIndexPackType<size_type>::packed_size_type 00354 packed_size_type; 00358 //------------------------------------------------------------------------------ 00364 00366 ArrayViewConst_() : pData(0), nUsed(0), nAllocated(0) {} 00367 00377 ArrayViewConst_(const ArrayViewConst_& src) 00378 : pData(0), nUsed(src.nUsed), nAllocated(0) { 00379 if (nUsed) pData = const_cast<T*>(src.pData); 00380 } 00381 00382 // Copy assignment is suppressed. 00383 00406 ArrayViewConst_(const T* first, const T* last1) 00407 : pData(0),nUsed(0),nAllocated(0) { 00408 if (last1==first) return; // empty 00409 00410 SimTK_ERRCHK((first&&last1)||(first==last1), 00411 "ArrayViewConst_<T>(first,last1)", 00412 "One of the source pointers was null (0); either both must be" 00413 " non-null or both must be null."); 00414 00415 SimTK_ERRCHK3(this->isSizeOK(last1-first), 00416 "ArrayViewConst_<T>(first,last1)", 00417 "The source data's size %llu is too big for this array which" 00418 " is limited to %llu elements by its index type %s.", 00419 this->ull(last1-first), ullMaxSize(), indexName()); 00420 00421 pData = const_cast<T*>(first); 00422 nUsed = packed_size_type(last1-first); 00423 // nAllocated is already zero 00424 } 00425 00453 template <class A> 00454 ArrayViewConst_(const std::vector<T,A>& src) 00455 : pData(0),nUsed(0),nAllocated(0) { 00456 if (src.empty()) return; 00457 00458 SimTK_ERRCHK3(this->isSizeOK(src.size()), 00459 "ArrayViewConst_<T>::ctor(std::vector<T>)", 00460 "The source std::vector's size %llu is too big for this array which" 00461 " is limited to %llu elements by its index type %s.", 00462 this->ull(src.size()), ullMaxSize(), indexName()); 00463 00464 pData = const_cast<T*>(&src.front()); 00465 nUsed = packed_size_type(src.size()); 00466 // nAllocated is already zero 00467 } 00470 operator const ArrayView_<T,X>&() const 00471 { return *reinterpret_cast<const ArrayView_<T,X>*>(this); } 00474 operator const Array_<T,X>&() const 00475 { return *reinterpret_cast<const Array_<T,X>*>(this); } 00476 00482 void disconnect() { 00483 SimTK_ASSERT(nAllocated==0, 00484 "ArrayViewConst_::deallocate(): called on an owner Array_"); 00485 nUsed = 0; 00486 pData = 0; 00487 } 00488 00491 ~ArrayViewConst_() { 00492 disconnect(); 00493 } 00497 //------------------------------------------------------------------------------ 00504 00506 size_type size() const {return size_type(nUsed);} 00508 size_type max_size() const 00509 { return ArrayIndexTraits<X>::max_size(); } 00512 bool empty() const {return nUsed==0;} 00517 size_type capacity() const 00518 { return size_type(nAllocated?nAllocated:nUsed); } 00522 size_type allocated() const {return size_type(nAllocated);} 00528 bool isOwner() const {return nAllocated || pData==0;} 00529 /*}*/ 00530 00531 00532 //------------------------------------------------------------------------------ 00539 00547 SimTK_FORCE_INLINE const T& operator[](index_type i) const { 00548 SimTK_INDEXCHECK(size_type(i),size(),"ArrayViewConst_<T>::operator[]()"); 00549 return pData[i]; 00550 } 00555 const T& at(index_type i) const { 00556 SimTK_INDEXCHECK_ALWAYS(size_type(i),size(),"ArrayViewConst_<T>::at()"); 00557 return pData[i]; 00558 } 00561 SimTK_FORCE_INLINE const T& getElt(index_type i) const { 00562 SimTK_INDEXCHECK(size_type(i),size(),"ArrayViewConst_<T>::getElt()"); 00563 return pData[i]; 00564 } 00570 SimTK_FORCE_INLINE const T& front() const 00571 { SimTK_ERRCHK(!empty(), "ArrayViewConst_<T>::front()", "Array was empty."); 00572 return pData[0]; } 00578 SimTK_FORCE_INLINE const T& back() const 00579 { SimTK_ERRCHK(!empty(), "ArrayViewConst_<T>::back()", "Array was empty."); 00580 return pData[nUsed-1]; } 00581 00600 ArrayViewConst_ operator()(index_type index, size_type length) const { 00601 const size_type ix(index); 00602 SimTK_ERRCHK2(isSizeInRange(ix, size()), "ArrayViewConst_<T>(index,length)", 00603 "For this operator, we must have 0 <= index <= size(), but" 00604 " index==%llu and size==%llu.", this->ull(ix), ullSize()); 00605 SimTK_ERRCHK2(isSizeInRange(length, size_type(size()-ix)), 00606 "ArrayViewConst_<T>(index,length)", 00607 "This operator requires 0 <= length <= size()-index, but" 00608 " length==%llu and size()-index==%llu.",this->ull(length),this->ull(size()-ix)); 00609 00610 return ArrayViewConst_(pData+ix, pData+ix+length); 00611 } 00614 ArrayViewConst_ getSubArray(index_type index, size_type length) const 00615 { return (*this)(index,length); } 00616 00620 //------------------------------------------------------------------------------ 00629 00634 const T* cbegin() const {return pData;} 00639 const T* cend() const {return pData + nUsed;} 00641 const T* begin() const {return pData;} 00643 const T* end() const {return pData + nUsed;} 00644 00647 const_reverse_iterator crbegin() const 00648 { return const_reverse_iterator(cend()); } 00652 const_reverse_iterator crend() const 00653 { return const_reverse_iterator(cbegin()); } 00655 const_reverse_iterator rbegin() const {return crbegin();} 00657 const_reverse_iterator rend() const {return crend();} 00658 00665 const T* cdata() const {return pData;} 00667 const T* data() const {return pData;} 00671 //------------------------------------------------------------------------------ 00672 protected: 00673 //------------------------------------------------------------------------------ 00674 // The remainder of this class is for the use of the ArrayView_<T,X> and 00675 // Array_<T,X> derived classes only and should not be documented for users to 00676 // see. 00677 00678 // Don't let doxygen see any of this. 00680 packed_size_type psize() const {return nUsed;} 00681 packed_size_type pallocated() const {return nAllocated;} 00682 00683 // These provide direct access to the data members for our trusted friends. 00684 void setData(const T* p) {pData = const_cast<T*>(p);} 00685 void setSize(size_type n) {nUsed = packed_size_type(n);} 00686 void incrSize() {++nUsed;} 00687 void decrSize() {--nUsed;} 00688 void setAllocated(size_type n) {nAllocated = packed_size_type(n);} 00689 00690 // Check whether a given size is the same as the current size of this array, 00691 // avoiding any compiler warnings due to mismatched integral types. 00692 template <class S> 00693 bool isSameSize(S sz) const 00694 { return ull(sz) == ullSize(); } 00695 00696 // Check that a source object's size will fit in the array being careful to 00697 // avoid overflow and warnings in the comparison. 00698 template <class S> 00699 bool isSizeOK(S srcSz) const 00700 { return ull(srcSz) <= ullMaxSize(); } 00701 00702 // This is identical in function to std::distance() (reports how many 00703 // elements lie between two iterators) but avoids any slow 00704 // Release-build bugcatchers that Microsoft may have felt compelled to add. 00705 // The implementation is specialized for random access iterators because 00706 // they can measure distance very fast. 00707 template<class Iter> static 00708 typename std::iterator_traits<Iter>::difference_type 00709 iterDistance(const Iter& first, const Iter& last1) { 00710 return iterDistanceImpl(first,last1, 00711 typename std::iterator_traits<Iter>::iterator_category()); 00712 } 00713 00714 // Generic slow implementation for non-random access iterators. This is fine 00715 // for forward and bidirectional iterators, but it will *consume* input 00716 // iterators so is useless for them. 00717 template<class Iter> static 00718 typename std::iterator_traits<Iter>::difference_type 00719 iterDistanceImpl(const Iter& first, const Iter& last1, std::input_iterator_tag) { 00720 typename std::iterator_traits<Iter>::difference_type d = 0; 00721 for (Iter src=first; src != last1; ++src, ++d) 00722 ; 00723 return d; 00724 } 00725 00726 // Fast specialization for random access iterators (including ordinary 00727 // pointers) -- just subtract. 00728 template<class Iter> static 00729 typename std::iterator_traits<Iter>::difference_type 00730 iterDistanceImpl(const Iter& first, const Iter& last1, 00731 std::random_access_iterator_tag) { 00732 return last1 - first; 00733 } 00734 00735 // This method attempts to determine whether any elements in the iterator range 00736 // [first,last1) overlap with the elements stored in this array. This is used 00737 // for error checks for operations where source is not permitted to overlap the 00738 // destination. For random access iterators (including ordinary pointers), we 00739 // can answer this question definitively because we expect the data to be 00740 // consecutive in memory. For other kinds of iterators, we will just assume 00741 // there is no overlap. Note that null ranges do not overlap even if the 00742 // pair of equal iterators points within the other range -- what matters is 00743 // the number of overlapping elements. 00744 template<class Iter> bool 00745 overlapsWithData(const Iter& first, const Iter& last1) { 00746 return overlapsWithDataImpl(first,last1, 00747 typename std::iterator_traits<Iter>::iterator_category()); 00748 } 00749 00750 // This is a partial specialization of the above where the data is given 00751 // with ordinary pointers. 00752 template <class T2> bool 00753 overlapsWithData(const T2* first, const T2* last1) { 00754 // Find the start and end+1 of the alleged overlap region. There is 00755 // overlap iff end+1 > start. Note that this works if either range 00756 // is [0,0) or [p,p), or if last1 is illegally less than first (we just 00757 // want to report no overlap in that case -- it is someone else's business 00758 // to complain). 00759 const T* obegin = std::max(cbegin(), (const T*)first); 00760 const T* oend1 = std::min(cend(), (const T*)last1); 00761 00762 return obegin < oend1; 00763 } 00764 00765 // This is the generic implementation for any type of input iterator other than 00766 // random access (i.e., bidirectional, forward, or input) -- assume no overlap. 00767 template<class Iter> bool 00768 overlapsWithDataImpl(const Iter&, const Iter&, std::input_iterator_tag) 00769 { return false; } 00770 00771 // Here we can actually test for overlap since we have random access iterators. 00772 // We convert them to pointers and then look for memory overlap. 00773 template<class Iter> bool 00774 overlapsWithDataImpl(const Iter& first, const Iter& last1, 00775 std::random_access_iterator_tag) { 00776 // We must check that the input iterators span a non-zero range before 00777 // assuming we can dereference them. 00778 if (last1 <= first) 00779 return false; // zero or malformed source range: no overlap 00780 00781 // We now know we can dereference first and last1-1 (can't safely 00782 // dereference last1 but we can use pointer arithmetic to point past 00783 // the (last-1)th element in memory). We then take the dereferenced 00784 // object's address to get ordinary pointers that we can use to 00785 // watch for illegal overlap. 00786 return overlapsWithData(&*first, &*(last1-1)); // use pointer overload 00787 } 00788 00789 // Cast an integral type to maximal-width unsigned long long to avoid accidental 00790 // overflows that might otherwise occur due to wraparound that can happen 00791 // with small index types. 00792 template <class S> 00793 static unsigned long long ull(S sz) 00794 { return (unsigned long long)sz; } 00795 00796 // Return size(), capacity(), and max_size() cast to unsigned long long. 00797 unsigned long long ullSize() const {return ull(size());} 00798 unsigned long long ullCapacity() const {return ull(capacity());} 00799 unsigned long long ullMaxSize() const {return ull(max_size());} 00800 00801 // Useful in error messages for explaining why something was too big. 00802 const char* indexName() const {return NiceTypeName<X>::name();} 00803 00806 private: 00807 //------------------------------------------------------------------------------ 00808 // DATA MEMBERS 00809 // These are the only data members and this layout is guaranteed not to change 00810 // from release to release. If data is null, then nUsed==nAllocated==0. 00811 00812 T* pData; // ptr to data referenced here, or 0 if none 00813 packed_size_type nUsed; // number of elements currently present (size) 00814 packed_size_type nAllocated; // heap allocation; 0 if pData is not owned 00815 00816 ArrayViewConst_& operator=(const ArrayViewConst_& src); // suppressed 00817 }; 00818 00819 00820 00821 00822 00823 00824 //============================================================================== 00825 // CLASS ArrayView_ 00826 //============================================================================== 00838 template <class T, class X> class ArrayView_ : public ArrayViewConst_<T,X> { 00839 typedef ArrayViewConst_<T,X> CBase; 00840 public: 00841 //------------------------------------------------------------------------------ 00846 /*{*/ 00847 typedef T value_type; 00848 typedef X index_type; 00849 typedef T* pointer; 00850 typedef const T* const_pointer; 00851 typedef T& reference; 00852 typedef const T& const_reference; 00853 typedef T* iterator; 00854 typedef const T* const_iterator; 00855 typedef std::reverse_iterator<iterator> reverse_iterator; 00856 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00857 typedef typename ArrayIndexTraits<X>::size_type size_type; 00858 typedef typename ArrayIndexTraits<X>::difference_type difference_type; 00859 typedef typename ArrayIndexPackType<size_type>::packed_size_type 00860 packed_size_type; 00861 /*}*/ 00862 00863 00864 //------------------------------------------------------------------------------ 00870 00872 ArrayView_() : CBase() {} 00873 00875 ArrayView_(const ArrayView_& src) : CBase(src) {} 00876 00878 ArrayView_(T* first, const T* last1) : CBase(first,last1) {} 00879 00881 template <class A> 00882 ArrayView_(std::vector<T,A>& v) : CBase(v) {} 00883 00885 operator const Array_<T,X>&() const 00886 { return *reinterpret_cast<const Array_<T,X>*>(this); } 00887 00889 operator Array_<T,X>&() 00890 { return *reinterpret_cast<Array_<T,X>*>(this); } 00891 00894 void disconnect() {this->CBase::disconnect();} 00895 00898 ~ArrayView_() {this->CBase::disconnect();} 00902 //------------------------------------------------------------------------------ 00914 00916 ArrayView_& operator=(const ArrayView_& src) { 00917 if (&src != this) 00918 avAssignIteratorDispatch(src.cbegin(), src.cend(), 00919 std::random_access_iterator_tag(), 00920 "ArrayView_<T>::operator=(ArrayView_<T>)"); 00921 return *this; 00922 } 00923 00924 00927 template <class T2, class X2> 00928 ArrayView_& operator=(const ArrayViewConst_<T2,X2>& src) { 00929 if ((const void*)&src != (void*)this) 00930 avAssignIteratorDispatch(src.cbegin(), src.cend(), 00931 std::random_access_iterator_tag(), 00932 "ArrayView_<T>::operator=(Array_<T2>)"); 00933 return *this; 00934 } 00935 00936 // Help out dumb compilers struggling to match the template arguments and 00937 // promote the Array_ or ArrayView_ to ArrayConstView_ at the same time. 00938 00941 template <class T2, class X2> 00942 ArrayView_& operator=(const ArrayView_<T2,X2>& src) 00943 { return *this = static_cast<const ArrayViewConst_<T2,X2>&>(src); } 00946 template <class T2, class X2> 00947 ArrayView_& operator=(const Array_<T2,X2>& src) 00948 { return *this = static_cast<const ArrayViewConst_<T2,X2>&>(src); } 00949 00952 template <class T2, class A2> 00953 ArrayView_& operator=(const std::vector<T2,A2>& src) { 00954 avAssignIteratorDispatch(src.begin(), src.end(), 00955 std::random_access_iterator_tag(), 00956 "ArrayView_<T>::operator=(std::vector<T2>)"); 00957 return *this; 00958 } 00959 00961 ArrayView_& operator=(const T& fillValue) 00962 { fill(fillValue); return *this; } 00963 00969 ArrayView_& fill(const T& fillValue) { 00970 for (T* d = begin(); d != end(); ++d) 00971 *d = fillValue; // using T::operator=(T) 00972 return *this; 00973 } 00974 00978 void assign(size_type n, const T& fillValue) { 00979 SimTK_ERRCHK2(n == size(), "ArrayView_<T>::assign(n,value)", 00980 "Assignment to an ArrayView is permitted only if the source" 00981 " is the same size. Here n==%llu element(s) but the" 00982 " ArrayView has a fixed size of %llu.", 00983 this->ull(n), this->ull(size())); 00984 00985 fill(fillValue); 00986 } 00987 01005 template <class T2> 01006 void assign(const T2* first, const T2* last1) { 01007 const char* methodName = "ArrayView_<T>::assign(T2* first, T2* last1)"; 01008 SimTK_ERRCHK((first&&last1)||(first==last1), methodName, 01009 "One of the source pointers was null (0); either both must be" 01010 " non-null or both must be null."); 01011 // Valid pointers are random access iterators. 01012 avAssignIteratorDispatch(first, last1, std::random_access_iterator_tag(), 01013 methodName); 01014 } 01015 01045 // Watch out for integral types matching this signature -- they must be 01046 // forwarded to the assign(n, fillValue) signature instead. 01047 template <class Iter> 01048 void assign(const Iter& first, const Iter& last1) 01049 { avAssignDispatch(first,last1,typename IsIntegralType<Iter>::Result(), 01050 "ArrayView_<T>::assign(Iter first, Iter last1)"); } 01054 //------------------------------------------------------------------------------ 01061 01068 SimTK_FORCE_INLINE const T& operator[](index_type i) const 01069 { return this->CBase::operator[](i); } 01070 01078 SimTK_FORCE_INLINE T& operator[](index_type i) 01079 { return const_cast<T&>(this->CBase::operator[](i)); } 01080 01085 const T& at(index_type i) const {return this->CBase::at(i);} 01086 01091 T& at(index_type i) {return const_cast<T&>(this->CBase::at(i));} 01092 01095 SimTK_FORCE_INLINE const T& getElt(index_type i) const 01096 { return this->CBase::getElt(i); } 01099 SimTK_FORCE_INLINE T& updElt(index_type i) 01100 { return const_cast<T&>(this->CBase::getElt(i)); } 01101 01107 SimTK_FORCE_INLINE const T& front() const {return this->CBase::front();} 01108 01114 SimTK_FORCE_INLINE T& front() {return const_cast<T&>(this->CBase::front());} 01115 01121 SimTK_FORCE_INLINE const T& back() const {return this->CBase::back();} 01122 01128 SimTK_FORCE_INLINE T& back() {return const_cast<T&>(this->CBase::back());} 01129 01148 ArrayView_ operator()(index_type index, size_type length) { 01149 const size_type ix(index); 01150 SimTK_ERRCHK2(isSizeInRange(ix, size()), "ArrayView_<T>(index,length)", 01151 "For this operator, we must have 0 <= index <= size(), but" 01152 " index==%llu and size==%llu.", this->ull(ix), ullSize()); 01153 SimTK_ERRCHK2(isSizeInRange(length, size_type(size()-ix)), 01154 "ArrayView_<T>(index,length)", 01155 "This operator requires 0 <= length <= size()-index, but" 01156 " length==%llu and size()-index==%llu.",this->ull(length),this->ull(size()-ix)); 01157 01158 return ArrayView_(data()+ix, data()+ix+length); 01159 } 01162 ArrayView_ updSubArray(index_type index, size_type length) 01163 { return (*this)(index,length); } 01167 //------------------------------------------------------------------------------ 01176 01181 SimTK_FORCE_INLINE const T* cbegin() const {return this->CBase::cbegin();} 01183 SimTK_FORCE_INLINE const T* begin() const {return this->CBase::cbegin();} 01188 SimTK_FORCE_INLINE T* begin() {return const_cast<T*>(this->CBase::cbegin());} 01189 01194 SimTK_FORCE_INLINE const T* cend() const {return this->CBase::cend();} 01196 SimTK_FORCE_INLINE const T* end() const {return this->CBase::cend();} 01201 SimTK_FORCE_INLINE T* end() {return const_cast<T*>(this->CBase::cend());} 01202 01205 const_reverse_iterator crbegin() const 01206 { return this->CBase::crbegin(); } 01208 const_reverse_iterator rbegin() const 01209 { return this->CBase::crbegin(); } 01212 reverse_iterator rbegin() {return reverse_iterator(end());} 01213 01217 const_reverse_iterator crend() const 01218 { return this->CBase::crend(); } 01220 const_reverse_iterator rend() const 01221 { return this->CBase::crend(); } 01225 reverse_iterator rend() {return reverse_iterator(begin());} 01226 01233 SimTK_FORCE_INLINE const T* cdata() const {return this->CBase::cdata();} 01236 SimTK_FORCE_INLINE const T* data() const {return this->CBase::cdata();} 01240 SimTK_FORCE_INLINE T* data() {return const_cast<T*>(this->CBase::cdata());} 01244 //------------------------------------------------------------------------------ 01250 01251 // Note: these have to be explicitly forwarded to the base class methods 01252 // in order to keep gcc from complaining. Note that the "this->" is 01253 // apparently necessary in order to permit delayed definition of templatized 01254 // methods. Doxygen picks up the comments from the base class. 01255 01256 SimTK_FORCE_INLINE size_type size() const {return this->CBase::size();} 01257 size_type max_size() const {return this->CBase::max_size();} 01258 bool empty() const {return this->CBase::empty();} 01259 size_type capacity() const {return this->CBase::capacity();} 01260 size_type allocated() const {return this->CBase::allocated();} 01261 bool isOwner() const {return this->CBase::isOwner();} 01265 //------------------------------------------------------------------------------ 01266 private: 01267 //------------------------------------------------------------------------------ 01268 // no data members are allowed 01269 01270 //------------------------------------------------------------------------------ 01271 // ARRAY VIEW ASSIGN DISPATCH 01272 // This is the assign() implementation for ArrayView_ when the class that 01273 // matched the alleged InputIterator template argument turned out to be one of 01274 // the integral types in which case this should match the assign(n, fillValue) 01275 // signature. 01276 template <class IntegralType> 01277 void avAssignDispatch(IntegralType n, IntegralType v, TrueType isIntegralType, 01278 const char*) 01279 { assign(size_type(n), value_type(v)); } 01280 01281 // This is the assign() implementation for ArrayView_ when the class that 01282 // matched the alleged InputIterator template argument is NOT an integral type 01283 // and may very well be an iterator. 01284 template <class InputIterator> 01285 void avAssignDispatch(const InputIterator& first, const InputIterator& last1, 01286 FalseType isIntegralType, const char* methodName) 01287 { avAssignIteratorDispatch(first, last1, 01288 typename std::iterator_traits<InputIterator>::iterator_category(), 01289 methodName); } 01290 01291 // This is the assign() implementation for a plain input_iterator 01292 // (i.e., not a forward, bidirectional, or random access iterator). These 01293 // have the unfortunate property that we can't count the elements in advance. 01294 // Here we're going to complain if there aren't enough; but will simply stop 01295 // when we get size() elements and not insist that the input stream reached 01296 // the supplied last1 iterator. Semantics is elementwise assignment. 01297 template <class InputIterator> 01298 void avAssignIteratorDispatch(const InputIterator& first, 01299 const InputIterator& last1, 01300 std::input_iterator_tag, 01301 const char* methodName) 01302 { 01303 T* p = begin(); 01304 InputIterator src = first; 01305 while (src != last1 && p != end()) 01306 *p++ = *src++; // call T's assignment operator 01307 01308 // p now points just after the last element that was copied. 01309 const size_type nCopied = size_type(p - begin()); 01310 SimTK_ERRCHK2_ALWAYS(nCopied == size(), methodName, 01311 "The supplied input_iterator provided only %llu elements but this" 01312 " ArrayView has a fixed size of %llu elements.", 01313 this->ull(nCopied), ullSize()); 01314 01315 // We don't care if there are still more input elements available. 01316 } 01317 01318 // This is the assign() implementation that works for forward and bidirectional 01319 // iterators, but is not used for random_access_iterators. Here we'll count 01320 // the elements as we copy them and complain at the end if there were too 01321 // few or too many. 01322 template <class ForwardIterator> 01323 void avAssignIteratorDispatch(const ForwardIterator& first, 01324 const ForwardIterator& last1, 01325 std::forward_iterator_tag, 01326 const char* methodName) 01327 { 01328 T* p = begin(); 01329 ForwardIterator src = first; 01330 while (src != last1 && p != end()) 01331 *p++ = *src++; // call T's assignment operator 01332 01333 // p now points just after the last element that was copied. 01334 const size_type nCopied = size_type(p - begin()); 01335 SimTK_ERRCHK2_ALWAYS(nCopied == size(), methodName, 01336 "The supplied forward_ or bidirectional_iterator source range provided" 01337 " only %llu elements but this ArrayView has a fixed size of" 01338 " %llu elements.", this->ull(nCopied), ullSize()); 01339 01340 // Make sure we ran out of source elements. 01341 SimTK_ERRCHK1_ALWAYS(src == last1, methodName, 01342 "The supplied forward_ or bidirectional_iterator source range" 01343 " contained too many elements; this ArrayView has a fixed size of" 01344 " %llu elements.", ullSize()); 01345 } 01346 01347 // This is the assign() implementation that works for random_access_iterators 01348 // including ordinary pointers. Here we check the number of elements in advance 01349 // and complain if the source and destination aren't the same size. The 01350 // copying loop can be done faster in this case. 01351 template <class RandomAccessIterator> 01352 void avAssignIteratorDispatch(const RandomAccessIterator& first, 01353 const RandomAccessIterator& last1, 01354 std::random_access_iterator_tag, 01355 const char* methodName) 01356 { 01357 SimTK_ERRCHK2_ALWAYS(this->isSameSize(last1-first), methodName, 01358 "Assignment to an ArrayView is permitted only if the source" 01359 " is the same size. Here the source had %llu element(s) but the" 01360 " ArrayView has a fixed size of %llu.", 01361 this->ull(last1-first), this->ull(size())); 01362 01363 SimTK_ERRCHK_ALWAYS(!this->overlapsWithData(first,last1), methodName, 01364 "Source range can't overlap with the destination data."); 01365 01366 T* p = begin(); 01367 RandomAccessIterator src = first; 01368 while (p != end()) 01369 *p++ = *src++; // call T's assignment operator 01370 } 01371 01372 01373 //------------------------------------------------------------------------------ 01374 // The following private methods are protected methods in the ArrayViewConst_ 01375 // base class, so they should not need repeating here. However, we explicitly 01376 // forward to the base methods to avoid gcc errors. The gcc complaint 01377 // is due to their not depending on any template parameters; the "this->" 01378 // apparently fixes that problem. 01379 01380 packed_size_type psize() const 01381 { return this->CBase::psize(); } 01382 packed_size_type pallocated() const 01383 { return this->CBase::pallocated(); } 01384 01385 // This just cast sizes to unsigned long long so that we can do comparisons 01386 // without getting warnings. 01387 unsigned long long ullSize() const 01388 { return this->CBase::ullSize(); } 01389 unsigned long long ullCapacity() const 01390 { return this->CBase::ullCapacity(); } 01391 unsigned long long ullMaxSize() const 01392 { return this->CBase::ullMaxSize(); } 01393 // This is the index type name and is handy for error messages to explain 01394 // why some size was too big. 01395 const char* indexName() const {return this->CBase::indexName();} 01396 }; 01397 01398 01399 01400 01401 01402 //============================================================================== 01403 // CLASS Array_ 01404 //============================================================================== 01507 template <class T, class X> class Array_ : public ArrayView_<T,X> { 01508 typedef ArrayView_<T,X> Base; 01509 typedef ArrayViewConst_<T,X> CBase; 01510 public: 01511 01512 01513 //------------------------------------------------------------------------------ 01519 // Doxygen picks up individual descriptions from the base class. 01520 /*{*/ 01521 typedef T value_type; 01522 typedef X index_type; 01523 typedef T* pointer; 01524 typedef const T* const_pointer; 01525 typedef T& reference; 01526 typedef const T& const_reference; 01527 typedef T* iterator; 01528 typedef const T* const_iterator; 01529 typedef std::reverse_iterator<iterator> reverse_iterator; 01530 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 01531 typedef typename ArrayIndexTraits<X>::size_type size_type; 01532 typedef typename ArrayIndexTraits<X>::difference_type difference_type; 01533 typedef typename ArrayIndexPackType<size_type>::packed_size_type 01534 packed_size_type; 01535 /*}*/ 01536 01537 //------------------------------------------------------------------------------ 01544 /*{*/ 01545 01547 Array_() : Base() {} 01548 01553 explicit Array_(size_type n) : Base() { 01554 SimTK_SIZECHECK(n, max_size(), "Array_<T>::ctor(n)"); 01555 allocateNoConstruct(n); 01556 defaultConstruct(data(), data()+n); 01557 setSize(n); 01558 } 01559 01563 Array_(size_type n, const T& initVal) : Base() { 01564 SimTK_SIZECHECK(n, max_size(), "Array_<T>::ctor(n,T)"); 01565 setSize(n); 01566 allocateNoConstruct(size()); 01567 fillConstruct(begin(), cend(), initVal); 01568 } 01584 template <class InputIter> 01585 Array_(const InputIter& first, const InputIter& last1) : Base() { 01586 ctorDispatch(first,last1,typename IsIntegralType<InputIter>::Result()); 01587 } 01588 01594 template <class T2> 01595 Array_(const T2* first, const T2* last1) : Base() { 01596 SimTK_ERRCHK((first&&last1)||(first==last1), "Array_<T>(first,last1)", 01597 "Pointers must be non-null unless they are both null."); 01598 SimTK_ERRCHK3(this->isSizeOK(last1-first), "Array_<T>(first,last1)", 01599 "Source has %llu elements but this array is limited to %llu" 01600 " elements by its index type %s.", 01601 this->ull(last1-first), ullMaxSize(), indexName()); 01602 01603 setSize(size_type(last1-first)); 01604 allocateNoConstruct(size()); 01605 copyConstruct(begin(), cend(), first); 01606 } 01607 01612 template <class T2> 01613 explicit Array_(const std::vector<T2>& v) : Base() { 01614 if (v.empty()) return; 01615 01616 SimTK_ERRCHK3(this->isSizeOK(v.size()), "Array_<T>::ctor(std::vector<T2>)", 01617 "The source std::vector's size %llu is too big for this array which" 01618 " is limited to %llu elements by its index type %s.", 01619 this->ull(v.size()), ullMaxSize(), indexName()); 01620 01621 // Call the above constructor, making sure to use pointers into the 01622 // vector's data rather than the iterators begin() and end() in case 01623 // they are different types. 01624 new (this) Array_(&v.front(), (&v.back())+1); 01625 } 01626 01631 Array_(const Array_& src) : Base() { 01632 setSize(src.size()); 01633 allocateNoConstruct(size()); 01634 copyConstruct(begin(), cend(), src.data()); 01635 } 01636 01643 template <class T2, class X2> 01644 Array_(const Array_<T2,X2>& src) : Base() { 01645 new (this) Array_(src.begin(), src.cend()); // see above 01646 } 01647 01677 Array_(T* first, const T* last1, const DontCopy&) : Base(first,last1) {} 01678 01706 template <class A> 01707 Array_(std::vector<T,A>& v, const DontCopy&) : Base(v) {} 01708 01712 ~Array_() { 01713 deallocate(); 01714 } 01715 01724 Array_& deallocate() { 01725 if (allocated()) { // owner with non-zero allocation 01726 clear(); // each element is destructed; size()=0; allocated() unchanged 01727 deallocateNoDestruct(); // free data(); allocated()=0 01728 } 01729 this->Base::disconnect(); // clear the handle 01730 return *this; 01731 } 01732 01736 //------------------------------------------------------------------------------ 01771 01789 void assign(size_type n, const T& fillValue) { 01790 SimTK_ERRCHK3(this->isSizeOK(n), "Array_<T>::assign(n,value)", 01791 "Requested size %llu is too big for this array which is limited" 01792 " to %llu elements by its index type %s.", 01793 this->ull(n), ullMaxSize(), indexName()); 01794 01795 SimTK_ERRCHK2(isOwner() || n==size(), "Array_<T>::assign(n,value)", 01796 "Requested size %llu is not allowed because this is a non-owner" 01797 " array of fixed size %llu.", this->ull(n), this->ull(size())); 01798 01799 if (!isOwner()) 01800 this->Base::fill(fillValue); 01801 else { 01802 clear(); // all elements destructed; allocation unchanged 01803 reallocateIfAdvisable(n); // change size if too small or too big 01804 fillConstruct(data(), cdata()+n, fillValue); 01805 setSize(n); 01806 } 01807 } 01808 01823 void fill(const T& fillValue) {this->Base::fill(fillValue);} 01824 01825 01847 template <class T2> 01848 void assign(const T2* first, const T2* last1) { 01849 const char* methodName = "Array_<T>::assign(T2* first, T2* last1)"; 01850 SimTK_ERRCHK((first&&last1)||(first==last1), methodName, 01851 "Pointers must be non-null unless they are both null."); 01852 SimTK_ERRCHK(!this->overlapsWithData(first,last1), methodName, 01853 "Source range can't overlap the current array contents."); 01854 // Pointers are random access iterators. 01855 assignIteratorDispatch(first,last1,std::random_access_iterator_tag(), 01856 methodName); 01857 } 01858 01859 01895 template <class Iter> 01896 void assign(const Iter& first, const Iter& last1) { 01897 assignDispatch(first,last1,typename IsIntegralType<Iter>::Result(), 01898 "Array_<T>::assign(Iter first, Iter last1)"); 01899 } 01900 01906 Array_& operator=(const Array_& src) { 01907 if (this != &src) 01908 assignIteratorDispatch(src.begin(), src.end(), 01909 std::random_access_iterator_tag(), 01910 "Array_<T>::operator=(Array_<T>)"); 01911 return *this; 01912 } 01913 01919 template <class T2, class X2> 01920 Array_& operator=(const Array_<T2,X2>& src) { 01921 assignIteratorDispatch(src.begin(), src.end(), 01922 std::random_access_iterator_tag(), 01923 "Array_<T>::operator=(Array_<T2,X2>)"); 01924 return *this; 01925 } 01926 01927 01932 template <class T2, class A> 01933 Array_& operator=(const std::vector<T2,A>& src) { 01934 assignIteratorDispatch(src.begin(), src.end(), 01935 std::random_access_iterator_tag(), 01936 "Array_<T>::operator=(std::vector)"); 01937 return *this; 01938 } 01939 01946 void swap(Array_& other) { 01947 T* const pTmp=data(); setData(other.data()); other.setData(pTmp); 01948 size_type nTmp=size(); setSize(other.size()); other.setSize(nTmp); 01949 nTmp=allocated(); setAllocated(other.allocated()); other.setAllocated(nTmp); 01950 } 01951 01957 Array_& adoptData(T* newData, size_type dataSize, 01958 size_type dataCapacity) 01959 { 01960 SimTK_SIZECHECK(dataCapacity, max_size(), "Array_<T>::adoptData()"); 01961 SimTK_ERRCHK2(dataSize <= dataCapacity, "Array_<T>::adoptData()", 01962 "Specified data size %llu was greater than the specified data" 01963 " capacity of %llu.", this->ull(dataSize), this->ull(dataCapacity)); 01964 SimTK_ERRCHK(newData || dataCapacity==0, "Array_<T>::adoptData()", 01965 "A null data pointer is allowed only if the size and capacity are" 01966 " specified as zero."); 01967 SimTK_ERRCHK(!this->overlapsWithData(newData, newData+dataSize), 01968 "Array_<T>::adoptData()", 01969 "The new data can't overlap with the old data."); 01970 01971 deallocate(); 01972 setData(newData); 01973 setSize(dataSize); 01974 setAllocated(dataCapacity); 01975 return *this; 01976 } 01979 Array_& adoptData(T* newData, size_type dataSize) 01980 { return adoptData(newData, dataSize, dataSize); } 01981 01982 01996 Array_& shareData(T* newData, size_type dataSize) { 01997 SimTK_SIZECHECK(dataSize, max_size(), "Array_<T>::shareData()"); 01998 SimTK_ERRCHK(newData || dataSize==0, "Array_<T>::shareData()", 01999 "A null data pointer is allowed only if the size is zero."); 02000 SimTK_ERRCHK(!this->overlapsWithData(newData, newData+dataSize), 02001 "Array_<T>::shareData()", 02002 "The new data can't overlap with the old data."); 02003 02004 deallocate(); 02005 setData(newData); 02006 setSize(dataSize); 02007 setAllocated(0); // indicates shared data 02008 return *this; 02009 } 02010 02013 Array_& shareData(T* first, const T* last1) { 02014 SimTK_ERRCHK3(this->isSizeOK(last1-first), "Array_<T>::shareData(first,last1)", 02015 "Requested size %llu is too big for this array which is limited" 02016 " to %llu elements by its index type %s.", 02017 this->ull(last1-first), ullMaxSize(), indexName()); 02018 return shareData(first, size_type(last1-first)); 02019 } 02020 02024 //------------------------------------------------------------------------------ 02030 02031 // Note: these have to be explicitly forwarded to the base class methods 02032 // in order to keep gcc from complaining. Note that the "this->" is 02033 // apparently necessary in order to permit delayed definition of templatized 02034 // methods. 02035 02037 SimTK_FORCE_INLINE size_type size() const {return this->CBase::size();} 02039 size_type max_size() const {return this->CBase::max_size();} 02042 bool empty() const {return this->CBase::empty();} 02047 size_type capacity() const {return this->CBase::capacity();} 02048 02053 void resize(size_type n) { 02054 if (n == size()) return; 02055 02056 SimTK_ERRCHK2(isOwner(), "Array_<T>::resize(n)", 02057 "Requested size change to %llu is not allowed because this is a" 02058 " non-owner array of fixed size %llu.", this->ull(n), this->ull(size())); 02059 02060 if (n < size()) { 02061 erase(data()+n, cend()); 02062 return; 02063 } 02064 // n > size() 02065 reserve(n); 02066 defaultConstruct(data()+size(), cdata()+n); // data() has changed 02067 setSize(n); 02068 } 02069 02074 void resize(size_type n, const T& initVal) { 02075 if (n == size()) return; 02076 02077 SimTK_ERRCHK2(isOwner(), "Array_<T>::resize(n,value)", 02078 "Requested size change to %llu is not allowed because this is a" 02079 " non-owner array of fixed size %llu.", this->ull(n), this->ull(size())); 02080 02081 if (n < size()) { 02082 erase(data()+n, cend()); 02083 return; 02084 } 02085 // n > size() 02086 reserve(n); 02087 fillConstruct(data()+size(), cdata()+n, initVal); 02088 setSize(n); 02089 } 02090 02097 void reserve(size_type n) { 02098 if (capacity() >= n) 02099 return; 02100 02101 SimTK_ERRCHK2(isOwner(), "Array_<T>::reserve()", 02102 "Requested capacity change to %llu is not allowed because this is a" 02103 " non-owner array of fixed size %llu.", this->ull(n), this->ull(size())); 02104 02105 T* newData = allocN(n); // no construction yet 02106 copyConstructThenDestructSource(newData, newData+size(), data()); 02107 freeN(data()); 02108 setData(newData); 02109 setAllocated(n); 02110 } 02111 02132 void shrink_to_fit() { 02133 // Allow 25% slop, but note that if size()==0 this will always reallocate 02134 // unless capacity is already zero. 02135 if (capacity() - size()/4 <= size()) // avoid overflow if size() near max 02136 return; 02137 T* newData = allocN(size()); 02138 copyConstructThenDestructSource(newData, newData+size(), data()); 02139 deallocateNoDestruct(); // data()=0, allocated()=0, size() unchanged 02140 setData(newData); 02141 setAllocated(size()); 02142 } 02143 02147 size_type allocated() const 02148 { return this->CBase::allocated(); } 02154 bool isOwner() const {return this->CBase::isOwner();} 02158 //------------------------------------------------------------------------------ 02167 02172 SimTK_FORCE_INLINE const T* cbegin() const {return this->CBase::cbegin();} 02174 SimTK_FORCE_INLINE const T* begin() const {return this->CBase::cbegin();} 02179 SimTK_FORCE_INLINE T* begin() {return this->Base::begin();} 02180 02185 SimTK_FORCE_INLINE const T* cend() const {return this->CBase::cend();} 02187 SimTK_FORCE_INLINE const T* end() const {return this->CBase::cend();} 02192 SimTK_FORCE_INLINE T* end() {return this->Base::end();} 02193 02196 const_reverse_iterator crbegin() const 02197 { return this->CBase::crbegin(); } 02199 const_reverse_iterator rbegin() const 02200 { return this->CBase::crbegin(); } 02203 reverse_iterator rbegin() {return this->Base::rbegin();} 02204 02208 const_reverse_iterator crend() const 02209 { return this->CBase::crend(); } 02211 const_reverse_iterator rend() const 02212 { return this->CBase::crend(); } 02216 reverse_iterator rend() {return this->Base::rend();} 02217 02224 SimTK_FORCE_INLINE const T* cdata() const {return this->CBase::cdata();} 02227 SimTK_FORCE_INLINE const T* data() const {return this->CBase::cdata();} 02231 SimTK_FORCE_INLINE T* data() {return this->Base::data();} 02239 02246 SimTK_FORCE_INLINE const T& operator[](index_type i) const 02247 { return this->CBase::operator[](i); } 02248 02256 SimTK_FORCE_INLINE T& operator[](index_type i) {return this->Base::operator[](i);} 02257 02262 const T& at(index_type i) const {return this->CBase::at(i);} 02263 02268 T& at(index_type i) {return const_cast<T&>(this->Base::at(i));} 02269 02272 SimTK_FORCE_INLINE const T& getElt(index_type i) const 02273 { return this->CBase::getElt(i); } 02276 SimTK_FORCE_INLINE T& updElt(index_type i) {return this->Base::updElt(i);} 02277 02283 SimTK_FORCE_INLINE const T& front() const {return this->CBase::front();} 02284 02290 SimTK_FORCE_INLINE T& front() {return const_cast<T&>(this->Base::front());} 02291 02297 SimTK_FORCE_INLINE const T& back() const {return this->CBase::back();} 02298 02304 SimTK_FORCE_INLINE T& back() {return const_cast<T&>(this->Base::back());} 02305 02308 ArrayViewConst_<T,X> operator()(index_type index, size_type length) const 02309 { return CBase::operator()(index,length); } 02312 ArrayViewConst_<T,X> getSubArray(index_type index, size_type length) const 02313 { return CBase::getSubArray(index,length); } 02314 02317 ArrayView_<T,X> operator()(index_type index, size_type length) 02318 { return Base::operator()(index,length); } 02321 ArrayView_<T,X> updSubArray(index_type index, size_type length) 02322 { return Base::updSubArray(index,length); } 02326 //------------------------------------------------------------------------------ 02332 02359 void push_back(const T& value) { 02360 if (pallocated() == psize()) 02361 growAtEnd(1,"Array_<T>::push_back(value)"); 02362 copyConstruct(end(), value); 02363 incrSize(); 02364 } 02365 02379 void push_back() { 02380 if (pallocated() == psize()) 02381 growAtEnd(1,"Array_<T>::push_back()"); 02382 defaultConstruct(end()); 02383 incrSize(); 02384 } 02385 02401 T* raw_push_back() { 02402 if (pallocated() == psize()) 02403 growAtEnd(1,"Array_<T>::raw_push_back()"); 02404 T* const p = end(); 02405 incrSize(); 02406 return p; 02407 } 02408 02411 void pop_back() { 02412 SimTK_ERRCHK(!empty(), "Array_<T>::pop_back()", "Array was empty."); 02413 destruct(&back()); 02414 decrSize(); 02415 } 02416 02434 T* erase(T* first, const T* last1) { 02435 SimTK_ERRCHK(begin() <= first && first <= last1 && last1 <= end(), 02436 "Array<T>::erase(first,last1)", "Pointers out of range or out of order."); 02437 02438 const size_type nErased = size_type(last1-first); 02439 SimTK_ERRCHK(isOwner() || nErased==0, "Array<T>::erase(first,last1)", 02440 "No elements can be erased from a non-owner array."); 02441 02442 if (nErased) { 02443 destruct(first, last1); // Destruct the elements we're erasing. 02444 moveElementsDown(first+nErased, nErased); // Compress followers into the gap. 02445 setSize(size()-nErased); 02446 } 02447 return first; 02448 } 02449 02469 T* erase(T* p) { 02470 SimTK_ERRCHK(begin() <= p && p < end(), 02471 "Array<T>::erase(p)", "Pointer must point to a valid element."); 02472 SimTK_ERRCHK(isOwner(), "Array<T>::erase(p)", 02473 "No elements can be erased from a non-owner array."); 02474 02475 destruct(p); // Destruct the element we're erasing. 02476 moveElementsDown(p+1, 1); // Compress followers into the gap. 02477 decrSize(); 02478 return p; 02479 } 02480 02481 02502 T* eraseFast(T* p) { 02503 SimTK_ERRCHK(begin() <= p && p < end(), 02504 "Array<T>::eraseFast(p)", "Pointer must point to a valid element."); 02505 SimTK_ERRCHK(isOwner(), "Array<T>::eraseFast(p)", 02506 "No elements can be erased from a non-owner array."); 02507 02508 destruct(p); 02509 if (p+1 != end()) 02510 moveOneElement(p, &back()); 02511 decrSize(); 02512 return p; 02513 } 02514 02522 void clear() { 02523 SimTK_ERRCHK(isOwner() || empty(), "Array_<T>::clear()", 02524 "clear() is not allowed for a non-owner array."); 02525 destruct(begin(), end()); 02526 setSize(0); 02527 } 02528 02529 02556 T* insert(T* p, size_type n, const T& value) { 02557 T* const gap = insertGapAt(p, n, "Array<T>::insert(p,n,value)"); 02558 // Copy construct into the inserted elements and note the size change. 02559 fillConstruct(gap, gap+n, value); 02560 setSize(size()+n); 02561 return gap; 02562 } 02563 02568 T* insert(T* p, const T& value) { 02569 T* const gap = insertGapAt(p, 1, "Array<T>::insert(p,value)"); 02570 // Copy construct into the inserted element and note the size change. 02571 copyConstruct(gap, value); 02572 incrSize(); 02573 return gap; 02574 } 02575 02605 template <class T2> 02606 T* insert(T* p, const T2* first, const T2* last1) { 02607 const char* methodName = "Array_<T>::insert(T* p, T2* first, T2* last1)"; 02608 SimTK_ERRCHK((first&&last1) || (first==last1), methodName, 02609 "One of first or last1 was null; either both or neither must be null."); 02610 SimTK_ERRCHK(!this->overlapsWithData(first,last1), methodName, 02611 "Source range can't overlap with the current array contents."); 02612 // Pointers are random access iterators. 02613 return insertIteratorDispatch(p, first, last1, 02614 std::random_access_iterator_tag(), 02615 methodName); 02616 } 02617 02620 template <class Iter> 02621 T* insert(T* p, const Iter& first, const Iter& last1) { 02622 return insertDispatch(p, first, last1, 02623 typename IsIntegralType<Iter>::Result(), 02624 "Array_<T>::insert(T* p, Iter first, Iter last1)"); 02625 } 02630 //------------------------------------------------------------------------------ 02631 private: 02632 //------------------------------------------------------------------------------ 02633 02634 02635 // This method is used when we have already decided we need to make room for 02636 // some new elements by reallocation, by creating a gap somewhere within the 02637 // existing data. We'll issue an error message if this would violate the 02638 // max_size restriction (we can afford to do that even in a Release build since 02639 // we don't expect to grow very often). Otherwise we'll allocate some more space 02640 // and copy construct the existing elements into the new space, leaving a gap 02641 // where indicated. Note that this method does not change the current size but 02642 // does change the capacity. 02643 // 02644 // The gapPos must point within the existing data with null OK if the array 02645 // itself is null, and end() being OK any time although you should use the 02646 // more specialized growAtEnd() method if you know that's what's happening. 02647 // 02648 // Don't call this with a gapSz of zero. 02649 T* growWithGap(T* gapPos, size_type gapSz, const char* methodName) { 02650 assert(gapSz > 0); // <= 0 is a bug, not a user error 02651 02652 // Note that gapPos may be null if begin() and end() are also. 02653 SimTK_ERRCHK(begin() <= gapPos && gapPos <= end(), methodName, 02654 "Given insertion point is not valid for this array."); 02655 02656 // Get some new space of a reasonable size. 02657 setAllocated(calcNewCapacityForGrowthBy(gapSz, methodName)); 02658 T* newData = allocN(allocated()); 02659 02660 // How many elements will be before the gap? 02661 const size_type nBefore = (size_type)(gapPos-begin()); 02662 02663 // Locate the gap in the new space allocation. 02664 T* newGap = newData + nBefore; 02665 T* newGapEnd = newGap + gapSz; // one past the last element in the gap 02666 02667 // Copy elements before insertion point; destruct source as we go. 02668 copyConstructThenDestructSource(newData, newGap, data()); 02669 // Copy/destruct elements at and after insertion pt; leave gapSz gap. 02670 copyConstructThenDestructSource(newGapEnd, newData+size(), gapPos); 02671 02672 // Throw away the old data and switch to the new. 02673 freeN(data()); setData(newData); 02674 return newGap; 02675 } 02676 02677 // Same as growWithGap(end(), n, methodName); see above. 02678 void growAtEnd(size_type n, const char* methodName) { 02679 assert(n > 0); // <= 0 is a bug, not a user error 02680 // Get some new space of a reasonable size. 02681 setAllocated(calcNewCapacityForGrowthBy(n, methodName)); 02682 T* newData = allocN(allocated()); 02683 // Copy all the elements; destruct source as we go. 02684 copyConstructThenDestructSource(newData, newData+size(), data()); 02685 // Throw away the old data and switch to the new. 02686 freeN(data()); setData(newData); 02687 } 02688 02689 // This method determines how much we should increase the array's capacity 02690 // when asked to insert n elements, due to an insertion or push_back. We will 02691 // generally allocate more new space than requested, in anticipation of 02692 // further insertions. This has to be based on the current size so that only 02693 // log(n) reallocations are performed to insert n elements one at a time. Our 02694 // policy here is to at least double the capacity unless that would exceed 02695 // max_size(). There is also a minimum amount of allocation we'll do if the 02696 // current size is zero or very small. 02697 size_type calcNewCapacityForGrowthBy(size_type n, const char* methodName) const { 02698 SimTK_ERRCHK3_ALWAYS(isGrowthOK(n), methodName, 02699 "Can't grow this Array by %llu element(s) because it would" 02700 " then exceed the max_size of %llu set by its index type %s.", 02701 (unsigned long long)n, ullMaxSize(), indexName()); 02702 02703 // At this point we know that capacity()+n <= max_size(). 02704 const size_type mustHave = capacity() + n; 02705 02706 // Be careful not to overflow size_type as you could if you 02707 // double capacity() rather than halving max_size(). 02708 const size_type wantToHave = capacity() <= max_size()/2 02709 ? 2*capacity() 02710 : max_size(); 02711 02712 const size_type newCapacity = std::max(std::max(mustHave,wantToHave), 02713 minAlloc()); 02714 return newCapacity; 02715 } 02716 02717 // Insert an unconstructed gap of size n beginning at position p. The return 02718 // value is a pointer to the first element in the gap. It will be p if no 02719 // reallocation occurred, otherwise it will be pointing into the new data. 02720 // On return size() will be unchanged although allocated() may be bigger. 02721 T* insertGapAt(T* p, size_type n, const char* methodName) { 02722 // Note that p may be null if begin() and end() are also. 02723 SimTK_ERRCHK(begin() <= p && p <= end(), methodName, 02724 "Given insertion point is not valid for this Array."); 02725 02726 if (n==0) return p; // nothing to do 02727 02728 SimTK_ERRCHK_ALWAYS(isOwner(), methodName, 02729 "No elements can be inserted into a non-owner array."); 02730 02731 // Determine the number of elements before the insertion point and 02732 // the number at or afterwards (those must be moved up by one slot). 02733 const size_type before = (size_type)(p-begin()), after = (size_type)(end()-p); 02734 02735 // Grow the container if necessary. Note that if we have to grow we 02736 // can create the gap at the same time we copy the old elements over 02737 // to the new space. 02738 if (capacity() >= size()+n) { 02739 moveElementsUp(p, n); // leave a gap at p 02740 } else { // need to grow 02741 setAllocated(calcNewCapacityForGrowthBy(n, methodName)); 02742 T* newdata = allocN(allocated()); 02743 // Copy the elements before the insertion point, and destroy source. 02744 copyConstructThenDestructSource(newdata, newdata+before, data()); 02745 // Copy the elements at and after the insertion point, leaving a gap 02746 // of n elements. 02747 copyConstructThenDestructSource(newdata+before+n, 02748 newdata+before+n+after, 02749 p); // i.e., pData+before 02750 p = newdata + before; // points into newdata now 02751 freeN(data()); 02752 setData(newdata); 02753 } 02754 02755 return p; 02756 } 02757 02758 //------------------------------------------------------------------------------ 02759 // CTOR DISPATCH 02760 // This is the constructor implementation for when the class that matches 02761 // the alleged InputIterator type turns out to be one of the integral types 02762 // in which case this should be the ctor(n, initValue) constructor. 02763 template <class IntegralType> void 02764 ctorDispatch(IntegralType n, IntegralType v, TrueType isIntegralType) { 02765 new(this) Array_(size_type(n), value_type(v)); 02766 } 02767 02768 // This is the constructor implementation for when the class that matches 02769 // the alleged InputIterator type is NOT an integral type and may very well 02770 // be an iterator. In that case we split into iterators for which we can 02771 // determine the number of elements in advance (forward, bidirectional, 02772 // random access) and input iterators, for which we can't. Note: iterator 02773 // types are arranged hierarchically random->bi->forward->input with each 02774 // deriving from the one on its right, so the forward iterator tag also 02775 // matches bi and random. 02776 template <class InputIterator> void 02777 ctorDispatch(const InputIterator& first, const InputIterator& last1, 02778 FalseType isIntegralType) 02779 { ctorIteratorDispatch(first, last1, 02780 typename std::iterator_traits<InputIterator>::iterator_category()); } 02781 02782 // This is the slow generic ctor implementation for any iterator that can't 02783 // make it up to forward_iterator capability (that is, an input_iterator). 02784 // The issue here is that we can't advance the iterator to count the number 02785 // of elements before allocating because input_iterators are consumed when 02786 // reference so we can't go back to look. That means we may have to reallocate 02787 // memory log n times as we "push back" these elements onto the array. 02788 template <class InputIterator> void 02789 ctorIteratorDispatch(const InputIterator& first, const InputIterator& last1, 02790 std::input_iterator_tag) 02791 { 02792 InputIterator src = first; 02793 while (src != last1) { 02794 // We can afford to check this always since we are probably doing I/O. 02795 // Throwing an exception in a constructor is tricky, though -- this 02796 // won't go through the Array_ destructor although it will call the 02797 // Base (ArrayView_) destructor. Since we have already allocated 02798 // some space, we must call deallocate() manually. 02799 if (size() == max_size()) { 02800 deallocate(); 02801 SimTK_ERRCHK2_ALWAYS(!"too many elements", 02802 "Array_::ctor(InputIterator first, InputIterator last1)", 02803 "There were still source elements available when the array" 02804 " reached its maximum size of %llu as determined by its index" 02805 " type %s.", ullMaxSize(), indexName()); 02806 } 02807 push_back(*src++); 02808 } 02809 } 02810 02811 // This is the faster constructor implementation for iterator types for which 02812 // we can calculate the number of elements in advance. This will be optimal 02813 // for a random access iterator since we can count in constant time, but for 02814 // forward or bidirectional we'll have to advance n times to count and then 02815 // go back again to do the copy constructions. 02816 template <class ForwardIterator> void 02817 ctorIteratorDispatch(const ForwardIterator& first, const ForwardIterator& last1, 02818 std::forward_iterator_tag) 02819 { 02820 typedef typename std::iterator_traits<ForwardIterator>::difference_type 02821 difference_type; 02822 // iterDistance() is constant time for random access iterators, but 02823 // O(last1-first) for forward and bidirectional since it has to increment 02824 // to count how far apart they are. 02825 const difference_type nInput = this->iterDistance(first,last1); 02826 02827 SimTK_ERRCHK(nInput >= 0, 02828 "Array_(ForwardIterator first, ForwardIterator last1)", 02829 "Iterators were out of order."); 02830 02831 SimTK_ERRCHK3(this->isSizeOK(nInput), 02832 "Array_(ForwardIterator first, ForwardIterator last1)", 02833 "Source has %llu elements but this array is limited to %llu" 02834 " elements by its index type %s.", 02835 this->ull(nInput), ullMaxSize(), indexName()); 02836 02837 const size_type n = size_type(nInput); 02838 setSize(n); 02839 allocateNoConstruct(n); 02840 copyConstruct(data(), data()+n, first); 02841 } 02842 02843 //------------------------------------------------------------------------------ 02844 // INSERT DISPATCH 02845 // This is the insert() implementation for when the class that matches 02846 // the alleged InputIterator type turns out to be one of the integral types 02847 // in which case this should be the insert(p, n, initValue) constructor. 02848 template <class IntegralType> 02849 T* insertDispatch(T* p, IntegralType n, IntegralType v, 02850 TrueType isIntegralType, const char*) 02851 { return insert(p, size_type(n), value_type(v)); } 02852 02853 // This is the insert() implementation for when the class that matches 02854 // the alleged InputIterator type is NOT an integral type and may very well 02855 // be an iterator. See ctorDispatch() above for more information. 02856 template <class InputIterator> 02857 T* insertDispatch(T* p, const InputIterator& first, const InputIterator& last1, 02858 FalseType isIntegralType, const char* methodName) 02859 { return insertIteratorDispatch(p, first, last1, 02860 typename std::iterator_traits<InputIterator>::iterator_category(), 02861 methodName); } 02862 02863 // This is the slow generic insert implementation for any iterator that can't 02864 // make it up to forward_iterator capability (that is, an input_iterator). 02865 // See ctorIteratorDispatch() above for more information. 02866 template <class InputIterator> 02867 T* insertIteratorDispatch(T* p, InputIterator first, InputIterator last1, 02868 std::input_iterator_tag, const char* methodName) 02869 { 02870 size_type nInserted = 0; 02871 while (first != last1) { 02872 // We can afford to check this always since we are probably doing I/O. 02873 SimTK_ERRCHK2_ALWAYS(size() < max_size(), methodName, 02874 "There were still source elements available when the array" 02875 " reached its maximum size of %llu as determined by its index" 02876 " type %s.", ullMaxSize(), indexName()); 02877 p = insert(p, *first++); // p may now point to reallocated memory 02878 ++p; ++nInserted; 02879 } 02880 // p now points just after the last inserted element; subtract the 02881 // number inserted to get a pointer to the first inserted element. 02882 return p-nInserted; 02883 } 02884 02885 // This is the faster constructor implementation for iterator types for which 02886 // we can calculate the number of elements in advance. This will be optimal 02887 // for a random access iterator since we can count in constant time, but for 02888 // forward or bidirectional we'll have to advance n times to count and then 02889 // go back again to do the copy constructions. 02890 template <class ForwardIterator> 02891 T* insertIteratorDispatch(T* p, const ForwardIterator& first, 02892 const ForwardIterator& last1, 02893 std::forward_iterator_tag, 02894 const char* methodName) 02895 { 02896 typedef typename std::iterator_traits<ForwardIterator>::difference_type 02897 difference_type; 02898 // iterDistance() is constant time for random access iterators, but 02899 // O(last1-first) for forward and bidirectional since it has to increment 02900 // to count how far apart they are. 02901 const difference_type nInput = this->iterDistance(first,last1); 02902 02903 SimTK_ERRCHK(nInput >= 0, methodName, "Iterators were out of order."); 02904 02905 SimTK_ERRCHK3(isGrowthOK(nInput), methodName, 02906 "Source has %llu elements which would make this array exceed the %llu" 02907 " elements allowed by its index type %s.", 02908 this->ull(nInput), ullMaxSize(), indexName()); 02909 02910 const size_type n = size_type(nInput); 02911 p = insertGapAt(p, n, methodName); 02912 copyConstruct(p, p+n, first); 02913 setSize(size()+n); 02914 return p; 02915 } 02916 02917 //------------------------------------------------------------------------------ 02918 // ASSIGN DISPATCH 02919 // This is the assign() implementation for when the class that matches 02920 // the alleged InputIterator type turns out to be one of the integral types 02921 // in which case this should be the assign(n, initValue) constructor. 02922 template <class IntegralType> 02923 void assignDispatch(IntegralType n, IntegralType v, TrueType isIntegralType, 02924 const char* methodName) 02925 { assign(size_type(n), value_type(v)); } 02926 02927 // This is the assign() implementation for when the class that matches 02928 // the alleged InputIterator type is NOT an integral type and may very well 02929 // be an iterator. See ctorDispatch() above for more information. 02930 template <class InputIterator> 02931 void assignDispatch(const InputIterator& first, const InputIterator& last1, 02932 FalseType isIntegralType, const char* methodName) 02933 { assignIteratorDispatch(first, last1, 02934 typename std::iterator_traits<InputIterator>::iterator_category(), 02935 methodName); } 02936 02937 // This is the slow generic implementation for a plain input_iterator 02938 // (i.e., not a forward, bidirectional, or random access iterator). These 02939 // have the unfortunate property that we can't count the elements in advance. 02940 template <class InputIterator> 02941 void assignIteratorDispatch(const InputIterator& first, 02942 const InputIterator& last1, 02943 std::input_iterator_tag, 02944 const char* methodName) 02945 { 02946 // TODO: should probably allow this and just blow up when the size()+1st 02947 // element is seen. 02948 SimTK_ERRCHK_ALWAYS(isOwner(), methodName, 02949 "Assignment to a non-owner array can only be done from a source" 02950 " designated with forward iterators or pointers because we" 02951 " must be able to verify that the source and destination sizes" 02952 " are the same."); 02953 02954 clear(); // TODO: change space allocation here? 02955 InputIterator src = first; 02956 while (src != last1) { 02957 // We can afford to check this always since we are probably doing I/O. 02958 SimTK_ERRCHK2_ALWAYS(size() < max_size(), methodName, 02959 "There were still source elements available when the array" 02960 " reached its maximum size of %llu as determined by its index" 02961 " type %s.", ullMaxSize(), indexName()); 02962 02963 push_back(*src++); 02964 } 02965 } 02966 02967 // This is the faster implementation that works for forward, bidirectional, 02968 // and random access iterators including ordinary pointers. We can check here that the 02969 // iterators are in the right order, and that the source is not too big to 02970 // fit in this array. Null pointer checks should be done prior to calling, 02971 // however, since iterators in general aren't pointers. 02972 template <class ForwardIterator> 02973 void assignIteratorDispatch(const ForwardIterator& first, 02974 const ForwardIterator& last1, 02975 std::forward_iterator_tag, 02976 const char* methodName) 02977 { 02978 typedef typename std::iterator_traits<ForwardIterator>::difference_type 02979 IterDiffType; 02980 // iterDistance() is constant time for random access iterators, but 02981 // O(last1-first) for forward and bidirectional since it has to increment 02982 // to count how far apart they are. 02983 const IterDiffType nInput = this->iterDistance(first,last1); 02984 02985 SimTK_ERRCHK(nInput >= 0, methodName, "Iterators were out of order."); 02986 02987 SimTK_ERRCHK3(this->isSizeOK(nInput), methodName, 02988 "Source has %llu elements but this Array is limited to %llu" 02989 " elements by its index type %s.", 02990 this->ull(nInput), ullMaxSize(), indexName()); 02991 02992 const size_type n = size_type(nInput); 02993 if (isOwner()) { 02994 // This is an owner Array; assignment is considered deallocation 02995 // followed by copy construction. 02996 02997 clear(); // all elements destructed; allocation unchanged 02998 reallocateIfAdvisable(n); // change allocation if too small or too big 02999 copyConstruct(data(), cdata()+n, first); 03000 setSize(n); 03001 } else { 03002 // This is a non-owner Array. Assignment can occur only if the 03003 // source is the same size as the array, and the semantics are of 03004 // repeated assignment using T::operator=() not destruction followed 03005 // by copy construction. 03006 SimTK_ERRCHK2(n == size(), methodName, 03007 "Source has %llu elements which does not match the size %llu" 03008 " of the non-owner array it is being assigned into.", 03009 this->ull(n), ullSize()); 03010 03011 T* p = begin(); 03012 ForwardIterator src = first; 03013 while (src != last1) 03014 *p++ = *src++; // call T's assignment operator 03015 } 03016 } 03017 03018 // We are going to put a total of n elements into the Array (probably 03019 // because of an assignment or resize) and we want the space allocation 03020 // to be reasonable. That means of course that the allocation must be 03021 // *at least* n, but we also don't want it to be too big. Our policy 03022 // here is that if it is currently less than twice what we need we 03023 // won't reallocate, otherwise we'll shrink the space. When changing 03024 // the size to zero or something very small we'll treat the Array as 03025 // though its current size is minAlloc, meaning we won't reallocate 03026 // if the existing space is less than twice minAlloc. 03027 // nAllocated will be set appropriately; size() is not touched here. 03028 // No constructors or destructors are called. 03029 void reallocateIfAdvisable(size_type n) { 03030 if (allocated() < n || allocated()/2 > std::max(minAlloc(), n)) 03031 reallocateNoDestructOrConstruct(n); 03032 } 03033 03034 03035 void allocateNoConstruct(size_type n) 03036 { setData(allocN(n)); setAllocated(n); } // size() left unchanged 03037 void deallocateNoDestruct() 03038 { freeN(data()); setData(0); setAllocated(0); } // size() left unchanged 03039 void reallocateNoDestructOrConstruct(size_type n) 03040 { deallocateNoDestruct(); allocateNoConstruct(n); } 03041 03042 // This sets the smallest allocation we'll do when growing. 03043 size_type minAlloc() const 03044 { return std::min(max_size(), size_type(4)); } 03045 03046 // Allocate without construction. Returns a null pointer if asked 03047 // to allocate 0 elements. In Debug mode we'll fill memory with 03048 // all 1's as a bug catcher. 03049 static T* allocN(size_type n) { 03050 if (n==0) return 0; 03051 unsigned char* newdata = new unsigned char[n * sizeof(T)]; 03052 #ifndef NDEBUG 03053 unsigned char* b=newdata; 03054 const unsigned char* e=newdata+(n*sizeof(T)); 03055 while (b != e) *b++ = 0xff; 03056 #endif 03057 return reinterpret_cast<T*>(newdata); 03058 } 03059 03060 // Free memory without calling T's destructor. Nothing happens if passed 03061 // a null pointer. 03062 static void freeN(T* p) { 03063 delete[] reinterpret_cast<char*>(p); 03064 } 03065 03066 // default construct one element 03067 static void defaultConstruct(T* p) {new(p) T();} 03068 // default construct range [b,e) 03069 static void defaultConstruct(T* b, const T* e) 03070 { while (b!=e) new(b++) T(); } 03071 03072 // copy construct range [b,e) with repeats of a given value 03073 static void fillConstruct(T* b, const T* e, const T& v) 03074 { while(b!=e) new(b++) T(v); } 03075 03076 // copy construct one element from a given value 03077 static void copyConstruct(T* p, const T& v) {new(p) T(v);} 03078 // copy construct range [b,e) from sequence of source values 03079 static void copyConstruct(T* b, const T* e, T* src) 03080 { while(b!=e) new(b++) T(*src++); } 03081 // Templatized copy construct will work if the source elements are 03082 // assignment compatible with the destination elements. 03083 template <class InputIterator> 03084 static void copyConstruct(T* b, const T* e, InputIterator src) 03085 { while(b!=e) new(b++) T(*src++); } 03086 03087 // Copy construct range [b,e] from sequence of source values and 03088 // destruct the source after it is copied. It's better to alternate 03089 // copying and destructing than to do this in two passes since we 03090 // will already have touched the memory. 03091 static void copyConstructThenDestructSource(T* b, const T* e, T* src) 03092 { while(b!=e) {new(b++) T(*src); src++->~T();} } 03093 03094 // We have an element at from that we would like to move into the currently- 03095 // unconstructed slot at to. Both from and to are expected to be pointing to 03096 // elements within the currently allocated space. From's slot will be left 03097 // unconstructed. 03098 void moveOneElement(T* to, T* from) { 03099 assert(data() <= to && to < data()+allocated()); 03100 assert(data() <= from && from < data()+allocated()); 03101 copyConstruct(to, *from); 03102 destruct(from); 03103 } 03104 03105 03106 // Move elements from p to end() down by n>0 places to fill an unconstructed 03107 // gap beginning at p-n. Any leftover space at the end will be unconstructed. 03108 void moveElementsDown(T* p, size_type n) { 03109 assert(n > 0); 03110 for (; p != end(); ++p) 03111 moveOneElement(p-n,p); 03112 } 03113 03114 // Move elements from p to end() up by n>0 places to make an unconstructed gap 03115 // at [p,p+n). Note that this has to be done backwards so that we don't 03116 // write on any elements until after they've been copied. 03117 void moveElementsUp(T* p, size_type n) { 03118 assert(n > 0); 03119 T* src = end(); // points one past source element (begin()-1 not allowed) 03120 while (src != p) { 03121 --src; // now points to source 03122 moveOneElement(src+n, src);; 03123 } 03124 } 03125 03126 // destruct one element 03127 static void destruct(T* p) {p->~T();} 03128 // destruct range [b,e) 03129 static void destruct(T* b, const T* e) 03130 { while(b!=e) b++->~T(); } 03131 03132 // Check that growing this array by n elements wouldn't cause it to exceed 03133 // its allowable maximum size. 03134 template <class S> 03135 bool isGrowthOK(S n) const 03136 { return this->isSizeOK(ullCapacity() + this->ull(n)); } 03137 03138 // The following private methods are protected methods in the ArrayView base 03139 // class, so they should not need repeating here. Howevr, we explicitly 03140 // forward to the Base methods to avoid gcc errors. The gcc complaint 03141 // is due to their not depending on any template parameters; the "this->" 03142 // apparently fixes that problem. 03143 03144 // These provide direct access to the data members. 03145 packed_size_type psize() const {return this->CBase::psize();} 03146 packed_size_type pallocated() const {return this->CBase::pallocated();} 03147 03148 void setData(const T* p) {this->CBase::setData(p);} 03149 void setSize(size_type n) {this->CBase::setSize(n);} 03150 void incrSize() {this->CBase::incrSize();} 03151 void decrSize() {this->CBase::decrSize();} 03152 void setAllocated(size_type n) {this->CBase::setAllocated(n);} 03153 // This just cast sizes to unsigned long long so that we can do comparisons 03154 // without getting warnings. 03155 unsigned long long ullSize() const 03156 { return this->CBase::ullSize(); } 03157 unsigned long long ullCapacity() const 03158 { return this->CBase::ullCapacity(); } 03159 unsigned long long ullMaxSize() const 03160 { return this->CBase::ullMaxSize(); } 03161 // This is the index type name and is handy for error messages to explain 03162 // why some size was too big. 03163 const char* indexName() const {return this->CBase::indexName();} 03164 }; 03165 03166 03167 // This "private" static method is used to implement ArrayView's 03168 // fillArrayViewFromStream() and Array's readArrayFromStream() namespace-scope 03169 // static methods, which are in turn used to implement ArrayView's and 03170 // Array's stream extraction operators ">>". This method has to be in the 03171 // header file so that we don't need to pass streams through the API, but it 03172 // is not intended for use by users and has no Doxygen presence, unlike 03173 // fillArrayFromStream() and readArrayFromStream() and (more commonly) 03174 // the extraction operators. 03175 template <class T, class X> static inline 03176 std::istream& readArrayFromStreamHelper 03177 (std::istream& in, bool isFixedSize, Array_<T,X>& out) 03178 { 03179 // If already failed, bad, or eof, set failed bit and return without 03180 // touching the Array. 03181 if (!in.good()) {in.setstate(std::ios::failbit); return in;} 03182 03183 // If the passed-in Array isn't an owner, then we have to treat it as 03184 // a fixed size ArrayView regardless of the setting of the isFixedSize 03185 // argument. 03186 if (!out.isOwner()) 03187 isFixedSize = true; // might be overriding the argument here 03188 03189 // numRequired will be ignored unless isFixedSize==true. 03190 const typename Array_<T,X>::size_type 03191 numRequired = isFixedSize ? out.size() : 0; 03192 03193 if (!isFixedSize) 03194 out.clear(); // We're going to replace the entire contents of the Array. 03195 03196 // Skip initial whitespace. If that results in eof this may be a successful 03197 // read of a 0-length, unbracketed Array. That is OK for either a 03198 // variable-length Array or a fixed-length ArrayView of length zero. 03199 std::ws(in); if (in.fail()) return in; 03200 if (in.eof()) { 03201 if (isFixedSize && numRequired != 0) 03202 in.setstate(std::ios_base::failbit); // zero elements not OK 03203 return in; 03204 } 03205 03206 // Here the stream is good and the next character is non-white. 03207 assert(in.good()); 03208 03209 // Use this for raw i/o (peeks and gets). 03210 typename std::iostream::int_type ch; 03211 03212 #ifndef NDEBUG // avoid unused variable warnings in Release 03213 const typename std::iostream::int_type EOFch = 03214 std::iostream::traits_type::eof(); 03215 #endif 03216 03217 // Now see if the sequence is bare or surrounded by (), [], or {}. 03218 bool lookForCloser = true; 03219 char openBracket, closeBracket; 03220 ch = in.peek(); if (in.fail()) return in; 03221 assert(ch != EOFch); // we already checked above 03222 03223 openBracket = (char)ch; 03224 if (openBracket=='(') {in.get(); closeBracket = ')';} 03225 else if (openBracket=='[') {in.get(); closeBracket = ']';} 03226 else if (openBracket=='{') {in.get(); closeBracket = '}';} 03227 else lookForCloser = false; 03228 03229 // If lookForCloser is true, then closeBracket contains the terminating 03230 // delimiter, otherwise we're not going to quit until eof. 03231 03232 // Eat whitespace after the opening bracket to see what's next. 03233 if (in.good()) std::ws(in); 03234 03235 // If we're at eof now it must be because the open bracket was the 03236 // last non-white character in the stream, which is an error. 03237 if (!in.good()) { 03238 if (in.eof()) { 03239 assert(lookForCloser); // or we haven't read anything that could eof 03240 in.setstate(std::ios::failbit); 03241 } 03242 return in; 03243 } 03244 03245 // istream is good and next character is non-white; ready to read first 03246 // value or terminator. 03247 03248 // We need to figure out whether the elements are space- or comma- 03249 // separated and then insist on consistency. 03250 bool commaOK = true, commaRequired = false; 03251 bool terminatorSeen = false; 03252 X nextIndex(0); 03253 while (true) { 03254 char c; 03255 03256 // Here at the top of this loop, we have already successfully read 03257 // n=nextIndex values of type T. For fixed-size reads, it might be 03258 // the case that n==numRequired already, but we still may need to 03259 // look for a closing bracket before we can declare victory. 03260 // The stream is good() (not at eof) but it might be the case that 03261 // there is nothing but white space left; we don't know yet because 03262 // if we have satisfied the fixed-size count and are not expecting 03263 // a terminator then we should quit without absorbing the trailing 03264 // white space. 03265 assert(in.good()); 03266 03267 // Look for closing bracket before trying to read value. 03268 if (lookForCloser) { 03269 // Eat white space to find the closing bracket. 03270 std::ws(in); if (!in.good()) break; // eof? 03271 ch = in.peek(); assert(ch != EOFch); 03272 if (!in.good()) break; 03273 c = (char)ch; 03274 if (c == closeBracket) { 03275 in.get(); // absorb the closing bracket 03276 terminatorSeen = true; 03277 break; 03278 } 03279 // next char not a closing bracket; fall through 03280 } 03281 03282 // We didn't look or didn't find a closing bracket. The istream is good 03283 // but we might be looking at white space. 03284 03285 // If we already got all the elements we want, break for final checks. 03286 if (isFixedSize && (nextIndex == numRequired)) 03287 break; // that's a full count. 03288 03289 // Look for comma before value, except the first time. 03290 if (commaOK && nextIndex != 0) { 03291 // Eat white space to find the comma. 03292 std::ws(in); if (!in.good()) break; // eof? 03293 ch = in.peek(); assert(ch != EOFch); 03294 if (!in.good()) break; 03295 c = (char)ch; 03296 if (c == ',') { 03297 in.get(); // absorb comma 03298 commaRequired = true; // all commas from now on 03299 } else { // next char not a comma 03300 if (commaRequired) // bad, e.g.: v1, v2, v3 v4 03301 { in.setstate(std::ios::failbit); break; } 03302 else commaOK = false; // saw: v1 v2 (no commas now) 03303 } 03304 if (!in.good()) break; // might be eof 03305 } 03306 03307 // No closing bracket yet; don't have enough elements; skipped comma 03308 // if any; istream is good; might be looking at white space. 03309 assert(in.good()); 03310 03311 // Now read in an element of type T. 03312 // The extractor T::operator>>() will ignore leading white space. 03313 if (!isFixedSize) 03314 out.push_back(); // grow by one (default consructed) 03315 in >> out[nextIndex]; if (in.fail()) break; 03316 ++nextIndex; 03317 03318 if (!in.good()) break; // might be eof 03319 } 03320 03321 // We will get here under a number of circumstances: 03322 // - the fail bit is set in the istream, or 03323 // - we reached eof 03324 // - we saw a closing brace 03325 // - we got all the elements we wanted (for a fixed-size read) 03326 // Note that it is possible that we consumed everything except some 03327 // trailing white space (meaning we're not technically at eof), but 03328 // for consistency with built-in operator>>()'s we won't try to absorb 03329 // that trailing white space. 03330 03331 if (!in.fail()) { 03332 if (lookForCloser && !terminatorSeen) 03333 in.setstate(std::ios::failbit); // missing terminator 03334 03335 if (isFixedSize && nextIndex != numRequired) 03336 in.setstate(std::ios::failbit); // wrong number of values 03337 } 03338 03339 return in; 03340 } 03341 03342 03343 03344 //------------------------------------------------------------------------------ 03345 // RELATED GLOBAL OPERATORS 03346 //------------------------------------------------------------------------------ 03347 // These are logically part of the Array_<T,X> class but are not actually 03348 // class members; that is, they are in the SimTK namespace. 03349 03350 // Some of the serialization methods could have been member functions but 03351 // then an attempt to explicitly instantiate the whole Array_<T> class for 03352 // some type T would fail if T did not support the requisite I/O operations 03353 // even if those operations were never used. This came up when Chris Bruns was 03354 // trying to wrap Array objects for Python, which requires explicit 03355 // instantiation. 03356 03364 03368 template <class T, class X> inline void 03369 writeUnformatted(std::ostream& o, const Array_<T,X>& v) { 03370 for (X i(0); i < v.size(); ++i) { 03371 if (i != 0) o << " "; 03372 writeUnformatted(o, v[i]); 03373 } 03374 } 03375 03376 03380 template <class T, class X> inline void 03381 writeFormatted(std::ostream& o, const Array_<T,X>& v) { 03382 o << '('; 03383 for (X i(0); i < v.size(); ++i) { 03384 if (i != 0) o << ','; 03385 writeFormatted(o, v[i]); 03386 } 03387 o << ')'; 03388 } 03389 03396 template <class T, class X> inline 03397 std::ostream& 03398 operator<<(std::ostream& o, 03399 const ArrayViewConst_<T,X>& a) 03400 { 03401 o << '('; 03402 if (!a.empty()) { 03403 o << a.front(); 03404 for (const T* p = a.begin()+1; p != a.end(); ++p) 03405 o << ',' << *p; 03406 } 03407 return o << ')'; 03408 } 03409 03410 03414 template <class T, class X> inline bool 03415 readUnformatted(std::istream& in, Array_<T,X>& v) { 03416 v.clear(); 03417 T element; 03418 std::ws(in); // Make sure we're at eof if stream is all whitespace. 03419 while (!in.eof() && readUnformatted(in, element)) 03420 v.push_back(element); 03421 return !in.fail(); // eof is expected and ok 03422 } 03423 03428 template <class T, class X> inline bool 03429 readUnformatted(std::istream& in, ArrayView_<T,X>& v) { 03430 for (X i(0); i < v.size(); ++i) 03431 if (!readUnformatted(in, v[i])) return false; 03432 return true; 03433 } 03434 03435 03441 template <class T, class X> inline bool 03442 readFormatted(std::istream& in, Array_<T,X>& v) { 03443 return !readArrayFromStream(in,v).fail(); 03444 } 03445 03451 template <class T, class X> inline bool 03452 readFormatted(std::istream& in, ArrayView_<T,X>& v) { 03453 return !fillArrayViewFromStream(in,v).fail(); 03454 } 03455 03485 template <class T, class X> static inline 03486 std::istream& readArrayFromStream(std::istream& in, Array_<T,X>& out) 03487 { return readArrayFromStreamHelper<T,X>(in, false /*variable sizez*/, out); } 03488 03489 03490 03515 template <class T, class X> static inline 03516 std::istream& fillArrayFromStream(std::istream& in, Array_<T,X>& out) 03517 { return readArrayFromStreamHelper<T,X>(in, true /*fixed size*/, out); } 03518 03523 template <class T, class X> static inline 03524 std::istream& fillArrayViewFromStream(std::istream& in, ArrayView_<T,X>& out) 03525 { return readArrayFromStreamHelper<T,X>(in, true /*fixed size*/, out); } 03526 03527 03528 03529 03539 template <class T, class X> inline 03540 std::istream& operator>>(std::istream& in, Array_<T,X>& out) 03541 { return readArrayFromStream<T,X>(in, out); } 03542 03550 template <class T, class X> inline 03551 std::istream& operator>>(std::istream& in, ArrayView_<T,X>& out) 03552 { return fillArrayViewFromStream<T,X>(in, out); } 03553 03563 03566 template <class T1, class X1, class T2, class X2> inline bool 03567 operator==(const ArrayViewConst_<T1,X1>& a1, const ArrayViewConst_<T2,X2>& a2) { 03568 // Avoid warnings in size comparison by using common type. 03569 const ptrdiff_t sz1 = a1.end()-a1.begin(); 03570 const ptrdiff_t sz2 = a2.end()-a2.begin(); 03571 if (sz1 != sz2) return false; 03572 const T1* p1 = a1.begin(); 03573 const T2* p2 = a2.begin(); 03574 while (p1 != a1.end()) 03575 if (!(*p1++ == *p2++)) return false; 03576 return true; 03577 } 03580 template <class T1, class X1, class T2, class X2> inline bool 03581 operator!=(const ArrayViewConst_<T1,X1>& a1, const ArrayViewConst_<T2,X2>& a2) 03582 { return !(a1 == a2); } 03583 03588 template <class T1, class X1, class T2, class X2> inline bool 03589 operator<(const ArrayViewConst_<T1,X1>& a1, const ArrayViewConst_<T2,X2>& a2) { 03590 const T1* p1 = a1.begin(); 03591 const T2* p2 = a2.begin(); 03592 while (p1 != a1.end() && p2 != a2.end()) { 03593 if (!(*p1 == *p2)) 03594 return *p1 < *p2; // otherwise p1 > p2 03595 ++p1; ++p2; 03596 } 03597 // All elements were equal until one or both arrays ran out of elements. 03598 // a1 is less than a2 only if a1 ran out and a2 didn't. 03599 return p1 == a1.end() && p2 != a2.end(); 03600 } 03603 template <class T1, class X1, class T2, class X2> inline bool 03604 operator>=(const ArrayViewConst_<T1,X1>& a1, const ArrayViewConst_<T2,X2>& a2) 03605 { return !(a1 < a2); } 03609 template <class T1, class X1, class T2, class X2> inline bool 03610 operator>(const ArrayViewConst_<T1,X1>& a1, const ArrayViewConst_<T2,X2>& a2) 03611 { return a2 < a1; } 03614 template <class T1, class X1, class T2, class X2> inline bool 03615 operator<=(const ArrayViewConst_<T1,X1>& a1, const ArrayViewConst_<T2,X2>& a2) 03616 { return !(a1 > a2); } 03617 03621 template <class T1, class X1, class T2, class A2> inline bool 03622 operator==(const ArrayViewConst_<T1,X1>& a1, const std::vector<T2,A2>& v2) 03623 { return a1 == ArrayViewConst_<T2,size_t>(v2); } 03624 03628 template <class T1, class A1, class T2, class X2> inline bool 03629 operator==(const std::vector<T1,A1>& v1, const ArrayViewConst_<T2,X2>& a2) 03630 { return a2 == v1; } 03631 03634 template <class T1, class X1, class T2, class A2> inline bool 03635 operator!=(const ArrayViewConst_<T1,X1>& a1, const std::vector<T2,A2>& v2) 03636 { return !(a1 == v2); } 03639 template <class T1, class A1, class T2, class X2> inline bool 03640 operator!=(const std::vector<T1,A1>& v1, const ArrayViewConst_<T2,X2>& a2) 03641 { return !(a2 == v1); } 03642 03648 template <class T1, class X1, class T2, class A2> inline bool 03649 operator<(const ArrayViewConst_<T1,X1>& a1, const std::vector<T2,A2>& v2) 03650 { return a1 < ArrayViewConst_<T2,size_t>(v2); } 03651 03657 template <class T1, class A1, class T2, class X2> inline bool 03658 operator<(const std::vector<T1,A1>& v1, const ArrayViewConst_<T2,X2>& a2) 03659 { return ArrayViewConst_<T1,size_t>(v1) < a2; } 03660 03663 template <class T1, class X1, class T2, class A2> inline bool 03664 operator>=(const ArrayViewConst_<T1,X1>& a1, const std::vector<T2,A2>& v2) 03665 { return !(a1 < v2); } 03668 template <class T1, class A1, class T2, class X2> inline bool 03669 operator>=(const std::vector<T1,A1>& v1, const ArrayViewConst_<T2,X2>& a2) 03670 { return !(v1 < a2); } 03671 03675 template <class T1, class X1, class T2, class A2> inline bool 03676 operator>(const ArrayViewConst_<T1,X1>& a1, const std::vector<T2,A2>& v2) 03677 { return v2 < a1; } 03681 template <class T1, class A1, class T2, class X2> inline bool 03682 operator>(const std::vector<T1,A1>& v1, const ArrayViewConst_<T2,X2>& a2) 03683 { return a2 < v1; } 03684 03687 template <class T1, class X1, class T2, class A2> inline bool 03688 operator<=(const ArrayViewConst_<T1,X1>& a1, const std::vector<T2,A2>& v2) 03689 { return !(a1 > v2); } 03692 template <class T1, class A1, class T2, class X2> inline bool 03693 operator<=(const std::vector<T1,A1>& v1, const ArrayViewConst_<T2,X2>& a2) 03694 { return !(v1 > a2); } 03695 03698 } // namespace SimTK 03699 03700 namespace std { 03704 template <class T, class X> inline void 03705 swap(SimTK::Array_<T,X>& a1, SimTK::Array_<T,X>& a2) { 03706 a1.swap(a2); 03707 } 03708 03709 } // namespace std 03710 03711 #endif // SimTK_SimTKCOMMON_ARRAY_H_