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

vigra/array_vector.hxx VIGRA

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> <vigra/array_vector.hxx><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> referring 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 referring to the first array element.
00222         */
00223     inline const_iterator begin() const
00224     {
00225         return data();
00226     }
00227 
00228         /** Get iterator referring 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 legacy 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> <vigra/array_vector.hxx><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         try
00708         {
00709             std::uninitialized_copy(this->begin(), p, new_data);
00710             std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
00711             std::uninitialized_copy(p, this->end(), new_data + pos + n);
00712         }
00713         catch(...)
00714         {
00715             alloc_.deallocate(new_data, new_capacity);
00716             throw;
00717         }
00718         deallocate(this->data_, this->size_);
00719         capacity_ = new_capacity;
00720         this->data_ = new_data;
00721     }
00722     else if(pos + n > this->size_)
00723     {
00724         size_type diff = pos + n - this->size_;
00725         std::uninitialized_copy(p, this->end(), this->end() + diff);
00726         std::uninitialized_fill(this->end(), this->end() + diff, v);
00727         std::fill(p, this->end(), v);
00728     }
00729     else
00730     {
00731         size_type diff = this->size_ - (pos + n);
00732         std::uninitialized_copy(this->end() - n, this->end(), this->end());
00733         std::copy_backward(p, p + diff, this->end());
00734         std::fill(p, p + n, v);
00735     }
00736     this->size_ = new_size;
00737     return this->begin() + pos;
00738 }
00739 
00740 template <class T, class Alloc>
00741 template <class InputIterator>
00742 typename ArrayVector<T, Alloc>::iterator
00743 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
00744 {
00745     size_type n = std::distance(i, iend);
00746     size_type pos = p - this->begin();
00747     size_type new_size = this->size() + n;
00748     if(new_size > capacity_)
00749     {
00750         size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
00751         pointer new_data = reserve_raw(new_capacity);
00752         try
00753         {
00754             std::uninitialized_copy(this->begin(), p, new_data);
00755             std::uninitialized_copy(i, iend, new_data + pos);
00756             std::uninitialized_copy(p, this->end(), new_data + pos + n);
00757         }
00758         catch(...)
00759         {
00760             alloc_.deallocate(new_data, new_capacity);
00761             throw;
00762         }
00763         deallocate(this->data_, this->size_);
00764         capacity_ = new_capacity;
00765         this->data_ = new_data;
00766     }
00767     else if(pos + n > this->size_)
00768     {
00769         size_type diff = pos + n - this->size_;
00770         std::uninitialized_copy(p, this->end(), this->end() + diff);
00771         InputIterator split = i;
00772         std::advance(split, n - diff);
00773         std::uninitialized_copy(split, iend, this->end());
00774         std::copy(i, split, p);
00775     }
00776     else
00777     {
00778         size_type diff = this->size_ - (pos + n);
00779         std::uninitialized_copy(this->end() - n, this->end(), this->end());
00780         std::copy_backward(p, p + diff, this->end());
00781         std::copy(i, iend, p);
00782     }
00783     this->size_ = new_size;
00784     return this->begin() + pos;
00785 }
00786 
00787 template <class T, class Alloc>
00788 typename ArrayVector<T, Alloc>::iterator
00789 ArrayVector<T, Alloc>::erase(iterator p)
00790 {
00791     std::copy(p+1, this->end(), p);
00792     pop_back();
00793     return p;
00794 }
00795 
00796 template <class T, class Alloc>
00797 typename ArrayVector<T, Alloc>::iterator
00798 ArrayVector<T, Alloc>::erase(iterator p, iterator q)
00799 {
00800     std::copy(q, this->end(), p);
00801     difference_type eraseCount = q - p;
00802     detail::destroy_n(this->end() - eraseCount, eraseCount);
00803     this->size_ -= eraseCount;
00804     return p;
00805 }
00806 
00807 template <class T, class Alloc>
00808 inline void
00809 ArrayVector<T, Alloc>::reserve( size_type new_capacity )
00810 {
00811     if(new_capacity <= capacity_)
00812         return;
00813     pointer new_data = reserve_raw(new_capacity);
00814     if(this->size_ > 0)
00815         std::uninitialized_copy(this->data_, this->data_+this->size_, new_data);
00816     deallocate(this->data_, this->size_);
00817     this->data_ = new_data;
00818     capacity_ = new_capacity;
00819 }
00820 
00821 template <class T, class Alloc>
00822 inline void
00823 ArrayVector<T, Alloc>::reserve()
00824 {
00825     if(capacity_ == 0)
00826         reserve(minimumCapacity);
00827     else if(this->size_ == capacity_)
00828         reserve(resizeFactor*capacity_);
00829 }
00830 
00831 template <class T, class Alloc>
00832 inline void
00833 ArrayVector<T, Alloc>::resize( size_type new_size, value_type const & initial)
00834 {
00835     if(new_size < this->size_)
00836         erase(this->begin() + new_size, this->end());
00837     else if(this->size_ < new_size)
00838     {
00839         insert(this->end(), new_size - this->size(), initial);
00840     }
00841 }
00842 
00843 template <class T, class Alloc>
00844 inline void
00845 ArrayVector<T, Alloc>::initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/)
00846 {
00847     this->size_ = size;
00848     capacity_ = size;
00849     this->data_ = reserve_raw(capacity_);
00850     if(this->size_ > 0)
00851         std::uninitialized_fill(this->data_, this->data_+this->size_, initial);
00852 }
00853 
00854 template <class T, class Alloc>
00855 template <class Iter>
00856 inline void
00857 ArrayVector<T, Alloc>::initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/)
00858 {
00859     this->size_ = std::distance(i, end);
00860     capacity_ = this->size_;
00861     this->data_ = reserve_raw(capacity_);
00862     if(this->size_ > 0)
00863         std::uninitialized_copy(i, end, this->data_);
00864 }
00865 
00866 template <class T, class Alloc>
00867 inline void
00868 ArrayVector<T, Alloc>::swap(this_type & rhs)
00869 {
00870     std::swap(this->size_, rhs.size_);
00871     std::swap(capacity_, rhs.capacity_);
00872     std::swap(this->data_, rhs.data_);
00873 }
00874 
00875 template <class T, class Alloc>
00876 inline void
00877 ArrayVector<T, Alloc>::deallocate(pointer data, size_type size)
00878 {
00879     if(data)
00880     {
00881         detail::destroy_n(data, (int)size);
00882         alloc_.deallocate(data, size);
00883     }
00884 }
00885 
00886 template <class T, class Alloc>
00887 inline typename ArrayVector<T, Alloc>::pointer
00888 ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
00889 {
00890     pointer data = 0;
00891     if(capacity)
00892     {
00893         data = alloc_.allocate(capacity);
00894     }
00895     return data;
00896 }
00897 
00898 } // namespace vigra
00899 
00900 namespace std {
00901 
00902 template <class T>
00903 ostream & operator<<(ostream & s, vigra::ArrayVectorView<T> const & a)
00904 {
00905     for(int k=0; k<(int)a.size()-1; ++k)
00906         s << a[k] << ", ";
00907     if(a.size())
00908             s << a.back();
00909     return s;
00910 }
00911 
00912 } // namespace std
00913 
00914 #undef VIGRA_ASSERT_INSIDE
00915 #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.8.0 (20 Sep 2011)