Simbody  3.5
Array.h
Go to the documentation of this file.
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_
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines