[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

vigra/array_vector.hxx |

    00001 /************************************************************************/
    00002 /*                                                                      */
    00003 /*               Copyright 2002-2004 by Ullrich Koethe                  */
    00004 /*                                                                      */
    00005 /*    This file is part of the VIGRA computer vision library.           */
    00006 /*    The VIGRA Website is                                              */
    00007 /*        http://hci.iwr.uni-heidelberg.de/vigra/                       */
    00008 /*    Please direct questions, bug reports, and contributions to        */
    00009 /*        ullrich.koethe@iwr.uni-heidelberg.de    or                    */
    00010 /*        vigra@informatik.uni-hamburg.de                               */
    00011 /*                                                                      */
    00012 /*    Permission is hereby granted, free of charge, to any person       */
    00013 /*    obtaining a copy of this software and associated documentation    */
    00014 /*    files (the "Software"), to deal in the Software without           */
    00015 /*    restriction, including without limitation the rights to use,      */
    00016 /*    copy, modify, merge, publish, distribute, sublicense, and/or      */
    00017 /*    sell copies of the Software, and to permit persons to whom the    */
    00018 /*    Software is furnished to do so, subject to the following          */
    00019 /*    conditions:                                                       */
    00020 /*                                                                      */
    00021 /*    The above copyright notice and this permission notice shall be    */
    00022 /*    included in all copies or substantial portions of the             */
    00023 /*    Software.                                                         */
    00024 /*                                                                      */
    00025 /*    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND    */
    00026 /*    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES   */
    00027 /*    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND          */
    00028 /*    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT       */
    00029 /*    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,      */
    00030 /*    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      */
    00031 /*    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR     */
    00032 /*    OTHER DEALINGS IN THE SOFTWARE.                                   */
    00033 /*                                                                      */
    00034 /************************************************************************/
    00035
    00036 #ifndef VIGRA_ARRAY_VECTOR_HXX
    00037 #define VIGRA_ARRAY_VECTOR_HXX
    00038
    00039 #include "error.hxx"
    00040 #include "memory.hxx"
    00041 #include "numerictraits.hxx"
    00042 #include <memory>
    00043 #include <algorithm>
    00044 #include <iosfwd>
    00045
    00046 #ifdef VIGRA_CHECK_BOUNDS
    00047 #define VIGRA_ASSERT_INSIDE(diff) \
    00048   vigra_precondition(diff >= 0, "Index out of bounds");\
    00049   vigra_precondition((unsigned int)diff < size_, "Index out of bounds");
    00050 #else
    00051 #define VIGRA_ASSERT_INSIDE(diff)
    00052 #endif
    00053
    00054 namespace vigra
    00055 {
    00056
    00057 template <class T, class Alloc = std::allocator<T> >
    00058 class ArrayVector;
    00059
    00060 /** Provide STL conforming interface for C-arrays.
    00061
    00062     This template implements much of the functionality of <tt><a href="http://www.sgi.com/tech/stl/Vector.html">std::vector</a></tt>
    00063     on top of a C-array. <tt>ArrayVectorView</tt> does not manage the memory
    00064     it refers to (i.e. it does not allocate or deallocate any memory).
    00065     Thus, if the underlying memory changes, all dependent <tt>ArrayVectorView</tt>
    00066     objects are invalidated. This is especially important when <tt>ArrayVectorView</tt>
    00067     is used as a base class for <tt>ArrayVector</tt>, where several functions
    00068     (e.g. resize(), insert()) can allocate new memory and thus invalidate the
    00069     dependent views. The rules what operations invalidate view objects are the
    00070     same as the rules concerning standard iterators.
    00071
    00072     <b>\#include</b> <<a href="array__vector_8hxx-source.html">vigra/array_vector.hxx</a>><br>
    00073     Namespace: vigra
    00074 */
    00075 template <class T>
    00076 class ArrayVectorView
    00077 {
    00078     typedef ArrayVectorView<T> this_type;
    00079
    00080 public:
    00081         /** default constructor
    00082         */
    00083     typedef T value_type;
    00084     typedef value_type & reference;
    00085     typedef value_type const & const_reference;
    00086     typedef value_type * pointer;
    00087     typedef value_type const * const_pointer;
    00088     typedef value_type * iterator;
    00089     typedef value_type const * const_iterator;
    00090     typedef std::size_t size_type;
    00091     typedef std::ptrdiff_t difference_type;
    00092     typedef std::reverse_iterator<iterator> reverse_iterator;
    00093     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    00094
    00095 public:
    00096         /** default constructor.
    00097             View contains NULL pointer.
    00098         */
    00099     ArrayVectorView()
    00100     : size_(0),
    00101       data_(0)
    00102     {}
    00103
    00104         /** Construct for given array \a data of length \a size.
    00105             <tt>data, data+size</tt> must form a valid range.
    00106         */
    00107     ArrayVectorView( size_type size, pointer const & data)
    00108     : size_(size),
    00109       data_(data)
    00110     {}
    00111
    00112         /** Copy constructor.
    00113         */
    00114     ArrayVectorView( this_type const & rhs )
    00115     : size_(rhs.size_),
    00116       data_(rhs.data_)
    00117     {}
    00118
    00119         /** Copy assignment. There are 3 cases:
    00120
    00121             <ul>
    00122             <li> When this <tt>ArrayVectorView</tt> does not point to valid data
    00123                  (e.g. after default construction), it becomes a copy of \a rhs.
    00124             <li> When the shapes of the two arrays match, the array contents
    00125                  (not the pointers) are copied.
    00126             <li> Otherwise, a <tt>PreconditionViolation</tt> exception is thrown.
    00127             </ul>
    00128         */
    00129     ArrayVectorView & operator=( ArrayVectorView const & rhs );
    00130
    00131         /** Copy assignment.
    00132             When the shapes of the two arrays match, the array contents
    00133             (not the pointers) are copied. Otherwise, a <tt>PreconditionViolation</tt>
    00134             exception is thrown.
    00135         */
    00136     template <class U>
    00137     this_type & operator=( ArrayVectorView<U> const & rhs )
    00138     {
    00139         copyImpl(rhs);
    00140         return *this;
    00141     }
    00142
    00143         /** Overwrite all array elements with the value \a initial.
    00144         */
    00145     template <class U>
    00146     void init(U const & initial)
    00147     {
    00148         std::fill(begin(), end(), initial);
    00149     }
    00150
    00151         /** Copy array elements.
    00152             When the shapes of the two arrays match, the array contents
    00153             (not the pointers) are copied. Otherwise, a <tt>PreconditionViolation</tt>
    00154             exception is thrown.
    00155         */
    00156     void copy( this_type const & rhs )
    00157     {
    00158         if(data_ != rhs.data_)
    00159             copyImpl(rhs);
    00160     }
    00161
    00162         /** Copy array elements.
    00163             When the shapes of the two arrays match, the array contents
    00164             (not the pointers) are copied. Otherwise, a <tt>PreconditionViolation</tt>
    00165             exception is thrown.
    00166         */
    00167     template <class U>
    00168     void copy( ArrayVectorView<U> const & rhs )
    00169     {
    00170         copyImpl(rhs);
    00171     }
    00172
    00173         /** Swap array elements.
    00174             When the shapes of the two arrays match, the array contents
    00175             (not the pointers) are swapped. Otherwise, a <tt>PreconditionViolation</tt>
    00176             exception is thrown.
    00177         */
    00178     void swapData(this_type rhs)
    00179     {
    00180         if(data_ != rhs.data_)
    00181             swapDataImpl(rhs);
    00182     }
    00183
    00184         /** Swap array elements.
    00185             When the shapes of the two arrays match, the array contents
    00186             (not the pointers) are swapped. Otherwise, a <tt>PreconditionViolation</tt>
    00187             exception is thrown.
    00188         */
    00189     template <class U>
    00190     void swapData(ArrayVectorView<U> rhs)
    00191     {
    00192         swapDataImpl(rhs);
    00193     }
    00194
    00195         /** Construct <tt>ArrayVectorView</tt> refering to a subarray.
    00196             \a begin and \a end must be a valid sub-range of the current array.
    00197             Otherwise, a <tt>PreconditionViolation</tt>
    00198             exception is thrown.
    00199         */
    00200     this_type subarray (size_type begin, size_type end) const
    00201     {
    00202         vigra_precondition(begin <= end && end <= size_,
    00203                 "ArrayVectorView::subarray(): Limits out of range.");
    00204         return this_type(end-begin, data_ + begin);
    00205     }
    00206
    00207         /** Get contained const pointer to the data.
    00208         */
    00209     inline const_pointer data() const
    00210     {
    00211         return data_;
    00212     }
    00213
    00214         /** Get contained pointer to the data.
    00215         */
    00216     inline pointer data()
    00217     {
    00218         return data_;
    00219     }
    00220
    00221         /** Get const iterator refering to the first array element.
    00222         */
    00223     inline const_iterator begin() const
    00224     {
    00225         return data();
    00226     }
    00227
    00228         /** Get iterator refering to the first array element.
    00229         */
    00230     inline iterator begin()
    00231     {
    00232         return data();
    00233     }
    00234
    00235         /** Get const iterator pointing beyond the last array element.
    00236         */
    00237     inline const_iterator end() const
    00238     {
    00239         return data() + size();
    00240     }
    00241
    00242         /** Get iterator pointing beyond the last array element.
    00243         */
    00244     inline iterator end()
    00245     {
    00246         return data() + size();
    00247     }
    00248
    00249         /** Get reverse iterator referring to the last array element.
    00250         */
    00251     inline reverse_iterator rbegin()
    00252     {
    00253         return (reverse_iterator(end()));
    00254     }
    00255
    00256         /** Get const reverse iterator referring to the last array element.
    00257         */
    00258     inline const_reverse_iterator rbegin() const
    00259     {
    00260         return (const_reverse_iterator(end()));
    00261     }
    00262
    00263         /** Get reverse iterator pointing before the first array element.
    00264         */
    00265     inline reverse_iterator rend()
    00266     {
    00267         return (reverse_iterator(begin()));
    00268     }
    00269
    00270         /** Get const reverse iterator pointing before the first array element.
    00271         */
    00272     inline const_reverse_iterator rend() const
    00273     {
    00274         return (const_reverse_iterator(begin()));
    00275     }
    00276
    00277         /** Access first array element.
    00278         */
    00279     reference front()
    00280     {
    00281         return *data_;
    00282     }
    00283
    00284         /** Read first array element.
    00285         */
    00286     const_reference front() const
    00287     {
    00288         return *data_;
    00289     }
    00290
    00291         /** Access last array element.
    00292         */
    00293     reference back()
    00294     {
    00295         return data_[size_-1];
    00296     }
    00297
    00298         /** Read last array element.
    00299         */
    00300     const_reference back() const
    00301     {
    00302         return data_[size_-1];
    00303     }
    00304
    00305         /** Access array element \a i.
    00306         */
    00307     reference operator[]( difference_type i )
    00308     {
    00309         VIGRA_ASSERT_INSIDE(i);
    00310         return data()[i];
    00311     }
    00312
    00313         /** Read array element \a i.
    00314         */
    00315     const_reference operator[]( difference_type i ) const
    00316     {
    00317         VIGRA_ASSERT_INSIDE(i);
    00318         return data()[i];
    00319     }
    00320
    00321         /** Equivalent to <tt>size() == 0</tt>.
    00322         */
    00323     bool empty() const
    00324     {
    00325         return size_ == 0;
    00326     }
    00327
    00328         /** Number of elements in the array.
    00329         */
    00330     size_type size() const
    00331     {
    00332         return size_;
    00333     }
    00334
    00335         /** Check for element-wise equality of two array.
    00336             Also returns <tt>false</tt> if the two arrays have different sizes.
    00337         */
    00338     template <class U>
    00339     bool operator==(ArrayVectorView<U> const & rhs) const;
    00340
    00341         /** check whether two arrays are not elementwise equal.
    00342             Also returns <tt>true</tt> if the two arrays have different sizes.
    00343          */
    00344     template <class U>
    00345     bool operator!=(ArrayVectorView<U> const & rhs) const
    00346     {
    00347         return !operator==(rhs);
    00348     }
    00349
    00350         /** check whether the given point is in the array range.
    00351          */
    00352     bool isInside (difference_type const & p) const
    00353     {
    00354         return p >= 0 && p < size_;
    00355     }
    00356
    00357   protected:
    00358
    00359     template <class U>
    00360     void copyImpl(const ArrayVectorView <U>& rhs);
    00361
    00362     void copyImpl(const ArrayVectorView & rhs);
    00363
    00364     template <class U>
    00365     void swapDataImpl(const ArrayVectorView <U>& rhs);
    00366
    00367     size_type size_;
    00368     pointer data_;
    00369 };
    00370
    00371 template <class T>
    00372 ArrayVectorView<T> & ArrayVectorView<T>::operator=( ArrayVectorView<T> const & rhs )
    00373 {
    00374     if(data_ == 0)
    00375     {
    00376         size_ = rhs.size_;
    00377         data_ = rhs.data_;
    00378     }
    00379     else if(data_ != rhs.data_)
    00380         copyImpl(rhs);
    00381     return *this;
    00382 }
    00383
    00384 template <class T>
    00385 template <class U>
    00386 bool ArrayVectorView<T>::operator==(ArrayVectorView<U> const & rhs) const
    00387 {
    00388     if(size() != rhs.size())
    00389         return false;
    00390     for(unsigned int k=0; k<size(); ++k)
    00391         if(data_[k] != rhs[k])
    00392             return false;
    00393     return true;
    00394 }
    00395
    00396 template <class T>
    00397 void
    00398 ArrayVectorView <T>::copyImpl(const ArrayVectorView & rhs)
    00399 {
    00400     vigra_precondition (size() == rhs.size(),
    00401         "ArrayVectorView::copy(): shape mismatch.");
    00402     // use copy() or copy_backward() according to possible overlap of this and rhs
    00403     if(data_ <= rhs.data())
    00404     {
    00405         std::copy(rhs.begin(), rhs.end(), begin());
    00406     }
    00407     else
    00408     {
    00409         std::copy_backward(rhs.begin(), rhs.end(), end());
    00410     }
    00411 }
    00412
    00413 template <class T>
    00414 template <class U>
    00415 void
    00416 ArrayVectorView <T>::copyImpl(const ArrayVectorView <U>& rhs)
    00417 {
    00418     vigra_precondition (size() == rhs.size(),
    00419         "ArrayVectorView::copy(): shape mismatch.");
    00420     std::copy(rhs.begin(), rhs.end(), begin());
    00421 }
    00422
    00423 template <class T>
    00424 template <class U>
    00425 void
    00426 ArrayVectorView <T>::swapDataImpl(const ArrayVectorView <U>& rhs)
    00427 {
    00428     vigra_precondition (size () == rhs.size() (),
    00429         "ArrayVectorView::swapData(): size mismatch.");
    00430
    00431     // check for overlap
    00432     if(data_ + size_ <= rhs.data_ || rhs.data_ + size_ <= data_)
    00433     {
    00434         for(unsigned int k=0; k<size_; ++k)
    00435             std::swap(data_[k], rhs.data_[k]);
    00436     }
    00437     else
    00438     {
    00439         ArrayVector<T> t(*this);
    00440         copyImpl(rhs);
    00441         rhs.copyImpl(*this);
    00442     }
    00443 }
    00444
    00445
    00446 /** Replacement for <tt>std::vector</tt>.
    00447
    00448     This template implements the same functionality as <tt>a href="http://www.sgi.com/tech/stl/Vector.html">std::vector</a></tt> (see there for detailed documentation).
    00449     However, it gives two useful guarantees, that <tt>std::vector</tt> fails
    00450     to provide:
    00451
    00452     <ul>
    00453     <li>The memory is always allocated as one contiguous piece.</li>
    00454     <li>The iterator is always a <TT>T *</TT> </li>
    00455     </ul>
    00456
    00457     This means that memory managed by <tt>ArrayVector</tt> can be passed
    00458     to algorithms that expect raw memory. This is especially important
    00459     when lagacy or C code has to be called, but it is also useful for certain
    00460     optimizations.
    00461
    00462     Moreover, <tt>ArrayVector</tt> is derived from <tt>ArrayVectorView</tt> so that one
    00463     can create views of the array (in particular, subarrays). This implies another
    00464     important difference to <tt>std::vector</tt>: the indexing operator
    00465     (<tt>ArrayVector::operator[]</tt>) takes <tt>signed</tt> indices. In this way,
    00466     an <tt>ArrayVectorView</tt> can be used with negative indices:
    00467
    00468     \code
    00469     ArrayVector<int> data(100);
    00470     ArrayVectorView<int> view = data.subarray(50, 100);
    00471
    00472     view[-50] = 1; // valid access
    00473     \endcode
    00474
    00475     Refer to the documentation of <tt>std::vector</tt> for a detailed
    00476     description of <tt>ArrayVector</tt> functionality.
    00477
    00478     <b>\#include</b> <<a href="array__vector_8hxx-source.html">vigra/array_vector.hxx</a>><br>
    00479     Namespace: vigra
    00480 */
    00481 template <class T, class Alloc /* = std::allocator<T> */ >
    00482 class ArrayVector
    00483 : public ArrayVectorView<T>
    00484 {
    00485     typedef ArrayVector<T, Alloc> this_type;
    00486     enum { minimumCapacity = 2, resizeFactor = 2 };
    00487
    00488 public:
    00489     typedef ArrayVectorView<T> view_type;
    00490     typedef typename view_type::value_type value_type;
    00491     typedef typename view_type::reference reference;
    00492     typedef typename view_type::const_reference const_reference;
    00493     typedef typename view_type::pointer pointer;
    00494     typedef typename view_type::const_pointer const_pointer;
    00495     typedef typename view_type::iterator iterator;
    00496     typedef typename view_type::const_iterator const_iterator;
    00497     typedef typename view_type::size_type size_type;
    00498     typedef typename view_type::difference_type difference_type;
    00499     typedef typename view_type::reverse_iterator reverse_iterator;
    00500     typedef typename view_type::const_reverse_iterator const_reverse_iterator;
    00501     typedef Alloc        allocator_type;
    00502
    00503 public:
    00504     ArrayVector()
    00505     : view_type(),
    00506       capacity_(minimumCapacity),
    00507       alloc_(Alloc())
    00508     {
    00509         this->data_ = reserve_raw(capacity_);
    00510     }
    00511
    00512     explicit ArrayVector(Alloc const & alloc)
    00513     : view_type(),
    00514       capacity_(minimumCapacity),
    00515       alloc_(alloc)
    00516     {
    00517         this->data_ = reserve_raw(capacity_);
    00518     }
    00519
    00520     explicit ArrayVector( size_type size, Alloc const & alloc = Alloc())
    00521     : view_type(),
    00522       alloc_(alloc)
    00523     {
    00524         initImpl(size, value_type(), VigraTrueType());
    00525     }
    00526
    00527     ArrayVector( size_type size, value_type const & initial, Alloc const & alloc = Alloc())
    00528     : view_type(),
    00529       alloc_(alloc)
    00530     {
    00531         initImpl(size, initial, VigraTrueType());
    00532     }
    00533
    00534
    00535     ArrayVector( this_type const & rhs )
    00536     : view_type(),
    00537       alloc_(rhs.alloc_)
    00538     {
    00539         initImpl(rhs.begin(), rhs.end(), VigraFalseType());
    00540     }
    00541
    00542     template <class U>
    00543     explicit ArrayVector( ArrayVectorView<U> const & rhs, Alloc const & alloc = Alloc() )
    00544     : view_type(),
    00545       alloc_(alloc)
    00546     {
    00547         initImpl(rhs.begin(), rhs.end(), VigraFalseType());
    00548     }
    00549
    00550     template <class InputIterator>
    00551     ArrayVector(InputIterator i, InputIterator end)
    00552     {
    00553         initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral());
    00554     }
    00555
    00556     template <class InputIterator>
    00557     ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc)
    00558     : alloc_(alloc)
    00559     {
    00560         initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral());
    00561     }
    00562
    00563     this_type & operator=( this_type const & rhs )
    00564     {
    00565         if(this == &rhs)
    00566             return *this;
    00567         if(this->size_ == rhs.size_)
    00568             this->copyImpl(rhs);
    00569         else
    00570         {
    00571             ArrayVector t(rhs);
    00572             this->swap(t);
    00573         }
    00574         return *this;
    00575     }
    00576
    00577     template <class U>
    00578     this_type & operator=( ArrayVectorView<U> const & rhs);
    00579
    00580     ~ArrayVector()
    00581     {
    00582         deallocate(this->data_, this->size_);
    00583     }
    00584
    00585     void pop_back();
    00586
    00587     void push_back( value_type const & t );
    00588
    00589     iterator insert(iterator p, value_type const & v);
    00590
    00591     iterator insert(iterator p, size_type n, value_type const & v);
    00592
    00593     template <class InputIterator>
    00594     iterator insert(iterator p, InputIterator i, InputIterator iend);
    00595
    00596     iterator erase(iterator p);
    00597
    00598     iterator erase(iterator p, iterator q);
    00599
    00600     void clear();
    00601
    00602     void reserve( size_type new_capacity );
    00603
    00604     void reserve();
    00605
    00606     void resize( size_type new_size, value_type const & initial );
    00607
    00608     void resize( size_type new_size )
    00609     {
    00610         resize(new_size, value_type());
    00611     }
    00612
    00613     size_type capacity() const
    00614     {
    00615         return capacity_;
    00616     }
    00617
    00618     void swap(this_type & rhs);
    00619
    00620   private:
    00621
    00622     void deallocate(pointer data, size_type size);
    00623
    00624     pointer reserve_raw(size_type capacity);
    00625
    00626     void initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/);
    00627
    00628     template <class Iter>
    00629     void initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/);
    00630
    00631     template <class Iter>
    00632     void initImpl( Iter i, Iter end, Error_NumericTraits_not_specialized_for_this_case)
    00633     {
    00634         initImpl(i, end, VigraFalseType());
    00635     }
    00636
    00637     size_type capacity_;
    00638     Alloc alloc_;
    00639 };
    00640
    00641 template <class T, class Alloc>
    00642 template <class U>
    00643 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( ArrayVectorView<U> const & rhs )
    00644 {
    00645     if(this->size_ == rhs.size())
    00646         this->copyImpl(rhs);
    00647     else
    00648     {
    00649         ArrayVector t(rhs);
    00650         this->swap(t);
    00651     }
    00652     return *this;
    00653 }
    00654
    00655 template <class T, class Alloc>
    00656 inline void ArrayVector<T, Alloc>::pop_back()
    00657 {
    00658     --this->size_;
    00659     alloc_.destroy(this->data_ + this->size_);
    00660 }
    00661
    00662 template <class T, class Alloc>
    00663 inline void ArrayVector<T, Alloc>::push_back( value_type const & t )
    00664 {
    00665     reserve();
    00666     alloc_.construct(this->data_ + this->size_, t);
    00667     ++this->size_;
    00668 }
    00669
    00670 template <class T, class Alloc>
    00671 inline void ArrayVector<T, Alloc>::clear()
    00672 {
    00673     detail::destroy_n(this->data_, (int)this->size_);
    00674     this->size_ = 0;
    00675 }
    00676
    00677 template <class T, class Alloc>
    00678 typename ArrayVector<T, Alloc>::iterator
    00679 ArrayVector<T, Alloc>::insert(iterator p, value_type const & v)
    00680 {
    00681     difference_type pos = p - this->begin();
    00682     if(p == this->end())
    00683     {
    00684         push_back(v);
    00685         p = this->begin() + pos;
    00686     }
    00687     else
    00688     {
    00689         push_back(this->back());
    00690         p = this->begin() + pos;
    00691         std::copy_backward(p, this->end() - 2, this->end() - 1);
    00692         *p = v;
    00693     }
    00694     return p;
    00695 }
    00696
    00697 template <class T, class Alloc>
    00698 typename ArrayVector<T, Alloc>::iterator
    00699 ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type const & v)
    00700 {
    00701     difference_type pos = p - this->begin();
    00702     size_type new_size = this->size() + n;
    00703     if(new_size >= capacity_)
    00704     {
    00705         size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
    00706         pointer new_data = reserve_raw(new_capacity);
    00707         std::uninitialized_copy(this->begin(), p, new_data);
    00708         std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
    00709         std::uninitialized_copy(p, this->end(), new_data + pos + n);
    00710         deallocate(this->data_, this->size_);
    00711         capacity_ = new_capacity;
    00712         this->data_ = new_data;
    00713     }
    00714     else if(pos + n >= this->size_)
    00715     {
    00716         size_type diff = pos + n - this->size_;
    00717         std::uninitialized_copy(p, this->end(), this->end() + diff);
    00718         std::uninitialized_fill(this->end(), this->end() + diff, v);
    00719         std::fill(p, this->end(), v);
    00720     }
    00721     else
    00722     {
    00723         size_type diff = this->size_ - (pos + n);
    00724         std::uninitialized_copy(this->end() - n, this->end(), this->end());
    00725         std::copy_backward(p, p + diff, this->end());
    00726         std::fill(p, p + n, v);
    00727     }
    00728     this->size_ = new_size;
    00729     return this->begin() + pos;
    00730 }
    00731
    00732 template <class T, class Alloc>
    00733 template <class InputIterator>
    00734 typename ArrayVector<T, Alloc>::iterator
    00735 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
    00736 {
    00737     size_type n = iend - i;
    00738     size_type pos = p - this->begin();
    00739     size_type new_size = this->size() + n;
    00740     if(new_size >= capacity_)
    00741     {
    00742         size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
    00743         pointer new_data = reserve_raw(new_capacity);
    00744         std::uninitialized_copy(this->begin(), p, new_data);
    00745         std::uninitialized_copy(i, iend, new_data + pos);
    00746         std::uninitialized_copy(p, this->end(), new_data + pos + n);
    00747         deallocate(this->data_, this->size_);
    00748         capacity_ = new_capacity;
    00749         this->data_ = new_data;
    00750     }
    00751     else if(pos + n >= this->size_)
    00752     {
    00753         size_type diff = pos + n - this->size_;
    00754         std::uninitialized_copy(p, this->end(), this->end() + diff);
    00755         std::uninitialized_copy(iend - diff, iend, this->end());
    00756         std::copy(i, iend - diff, p);
    00757     }
    00758     else
    00759     {
    00760         size_type diff = this->size_ - (pos + n);
    00761         std::uninitialized_copy(this->end() - n, this->end(), this->end());
    00762         std::copy_backward(p, p + diff, this->end());
    00763         std::copy(i, iend, p);
    00764     }
    00765     this->size_ = new_size;
    00766     return this->begin() + pos;
    00767 }
    00768
    00769 template <class T, class Alloc>
    00770 typename ArrayVector<T, Alloc>::iterator
    00771 ArrayVector<T, Alloc>::erase(iterator p)
    00772 {
    00773     std::copy(p+1, this->end(), p);
    00774     pop_back();
    00775     return p;
    00776 }
    00777
    00778 template <class T, class Alloc>
    00779 typename ArrayVector<T, Alloc>::iterator
    00780 ArrayVector<T, Alloc>::erase(iterator p, iterator q)
    00781 {
    00782     std::copy(q, this->end(), p);
    00783     difference_type eraseCount = q - p;
    00784     detail::destroy_n(this->end() - eraseCount, eraseCount);
    00785     this->size_ -= eraseCount;
    00786     return p;
    00787 }
    00788
    00789 template <class T, class Alloc>
    00790 inline void
    00791 ArrayVector<T, Alloc>::reserve( size_type new_capacity )
    00792 {
    00793     if(new_capacity <= capacity_)
    00794         return;
    00795     pointer new_data = reserve_raw(new_capacity);
    00796     if(this->size_ > 0)
    00797         std::uninitialized_copy(this->data_, this->data_+this->size_, new_data);
    00798     deallocate(this->data_, this->size_);
    00799     this->data_ = new_data;
    00800     capacity_ = new_capacity;
    00801 }
    00802
    00803 template <class T, class Alloc>
    00804 inline void
    00805 ArrayVector<T, Alloc>::reserve()
    00806 {
    00807     if(capacity_ == 0)
    00808         reserve(minimumCapacity);
    00809     else if(this->size_ == capacity_)
    00810         reserve(resizeFactor*capacity_);
    00811 }
    00812
    00813 template <class T, class Alloc>
    00814 inline void
    00815 ArrayVector<T, Alloc>::resize( size_type new_size, value_type const & initial)
    00816 {
    00817     if(new_size < this->size_)
    00818         erase(this->begin() + new_size, this->end());
    00819     else if(this->size_ < new_size)
    00820     {
    00821         insert(this->end(), new_size - this->size(), initial);
    00822     }
    00823 }
    00824
    00825 template <class T, class Alloc>
    00826 inline void
    00827 ArrayVector<T, Alloc>::initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/)
    00828 {
    00829     this->size_ = size;
    00830     capacity_ = size;
    00831     this->data_ = reserve_raw(capacity_);
    00832     if(this->size_ > 0)
    00833         std::uninitialized_fill(this->data_, this->data_+this->size_, initial);
    00834 }
    00835
    00836 template <class T, class Alloc>
    00837 template <class Iter>
    00838 inline void
    00839 ArrayVector<T, Alloc>::initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/)
    00840 {
    00841     this->size_ = std::distance(i, end);
    00842     capacity_ = this->size_;
    00843     this->data_ = reserve_raw(capacity_);
    00844     if(this->size_ > 0)
    00845         std::uninitialized_copy(i, end, this->data_);
    00846 }
    00847
    00848 template <class T, class Alloc>
    00849 inline void
    00850 ArrayVector<T, Alloc>::swap(this_type & rhs)
    00851 {
    00852     std::swap(this->size_, rhs.size_);
    00853     std::swap(capacity_, rhs.capacity_);
    00854     std::swap(this->data_, rhs.data_);
    00855 }
    00856
    00857 template <class T, class Alloc>
    00858 inline void
    00859 ArrayVector<T, Alloc>::deallocate(pointer data, size_type size)
    00860 {
    00861     if(data)
    00862     {
    00863         detail::destroy_n(data, (int)size);
    00864         alloc_.deallocate(data, size);
    00865     }
    00866 }
    00867
    00868 template <class T, class Alloc>
    00869 inline typename ArrayVector<T, Alloc>::pointer
    00870 ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
    00871 {
    00872     pointer data = 0;
    00873     if(capacity)
    00874     {
    00875         data = alloc_.allocate(capacity);
    00876     }
    00877     return data;
    00878 }
    00879
    00880 } // namespace vigra
    00881
    00882 namespace std {
    00883
    00884 template <class T>
    00885 ostream & operator<<(ostream & s, vigra::ArrayVectorView<T> const & a)
    00886 {
    00887     for(int k=0; k<(int)a.size()-1; ++k)
    00888         s << a[k] << ", ";
    00889     if(a.size())
    00890             s << a.back();
    00891     return s;
    00892 }
    00893
    00894 } // namespace std
    00895
    00896 #undef VIGRA_ASSERT_INSIDE
    00897 #endif /* VIGRA_ARRAY_VECTOR_HXX */

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.7.1 (3 Dec 2010)