[ 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> <<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     : alloc_(alloc)
00522     {
00523         initImpl(size, value_type(), VigraTrueType());
00524     }
00525 
00526     ArrayVector( size_type size, value_type const & initial, Alloc const & alloc = Alloc())
00527     : alloc_(alloc)
00528     {
00529         initImpl(size, initial, VigraTrueType());
00530     }
00531 
00532 
00533     ArrayVector( this_type const & rhs )
00534     : view_type(rhs), alloc_(rhs.alloc_)
00535     {
00536         initImpl(rhs.begin(), rhs.end(), VigraFalseType());
00537     }
00538 
00539     template <class U>
00540     explicit ArrayVector( ArrayVectorView<U> const & rhs, Alloc const & alloc = Alloc() )
00541     : alloc_(alloc)
00542     {
00543         initImpl(rhs.begin(), rhs.end(), VigraFalseType());
00544     }
00545 
00546     template <class InputIterator>
00547     ArrayVector(InputIterator i, InputIterator end)
00548     {
00549         initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral());
00550     }
00551 
00552     template <class InputIterator>
00553     ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc)
00554     : alloc_(alloc)
00555     {
00556         initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral());
00557     }
00558 
00559     this_type & operator=( this_type const & rhs )
00560     {
00561         if(this == &rhs)
00562             return *this;
00563         if(this->size_ == rhs.size_)
00564             this->copyImpl(rhs);
00565         else
00566         {
00567             ArrayVector t(rhs);
00568             this->swap(t);
00569         }
00570         return *this;
00571     }
00572 
00573     template <class U>
00574     this_type & operator=( ArrayVectorView<U> const & rhs);
00575 
00576     ~ArrayVector()
00577     {
00578         deallocate(this->data_, this->size_);
00579     }
00580 
00581     void pop_back();
00582 
00583     void push_back( value_type const & t );
00584 
00585     iterator insert(iterator p, value_type const & v);
00586 
00587     iterator insert(iterator p, size_type n, value_type const & v);
00588 
00589     template <class InputIterator>
00590     iterator insert(iterator p, InputIterator i, InputIterator iend);
00591 
00592     iterator erase(iterator p);
00593 
00594     iterator erase(iterator p, iterator q);
00595 
00596     void clear();
00597 
00598     void reserve( size_type new_capacity );
00599 
00600     void reserve();
00601 
00602     void resize( size_type new_size, value_type const & initial );
00603 
00604     void resize( size_type new_size )
00605     {
00606         resize(new_size, value_type());
00607     }
00608 
00609     size_type capacity() const
00610     {
00611         return capacity_;
00612     }
00613 
00614     void swap(this_type & rhs);
00615 
00616   private:
00617 
00618     void deallocate(pointer data, size_type size);
00619 
00620     pointer reserve_raw(size_type capacity);
00621     
00622     void initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/);
00623 
00624     template <class Iter>
00625     void initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/);
00626     
00627     template <class Iter>
00628     void initImpl( Iter i, Iter end, Error_NumericTraits_not_specialized_for_this_case)
00629     {
00630         initImpl(i, end, VigraFalseType());
00631     }
00632 
00633     size_type capacity_;
00634     Alloc alloc_;
00635 };
00636 
00637 template <class T, class Alloc>
00638 template <class U>
00639 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( ArrayVectorView<U> const & rhs )
00640 {
00641     if(this->size_ == rhs.size())
00642         this->copyImpl(rhs);
00643     else
00644     {
00645         ArrayVector t(rhs);
00646         this->swap(t);
00647     }
00648     return *this;
00649 }
00650 
00651 template <class T, class Alloc>
00652 inline void ArrayVector<T, Alloc>::pop_back()
00653 {
00654     --this->size_;
00655     alloc_.destroy(this->data_ + this->size_);
00656 }
00657 
00658 template <class T, class Alloc>
00659 inline void ArrayVector<T, Alloc>::push_back( value_type const & t )
00660 {
00661     reserve();
00662     alloc_.construct(this->data_ + this->size_, t);
00663     ++this->size_;
00664 }
00665 
00666 template <class T, class Alloc>
00667 inline void ArrayVector<T, Alloc>::clear()
00668 {
00669     detail::destroy_n(this->data_, (int)this->size_);
00670     this->size_ = 0;
00671 }
00672 
00673 template <class T, class Alloc>
00674 typename ArrayVector<T, Alloc>::iterator
00675 ArrayVector<T, Alloc>::insert(iterator p, value_type const & v)
00676 {
00677     difference_type pos = p - this->begin();
00678     if(p == this->end())
00679     {
00680         push_back(v);
00681         p = this->begin() + pos;
00682     }
00683     else
00684     {
00685         push_back(this->back());
00686         p = this->begin() + pos;
00687         std::copy_backward(p, this->end() - 2, this->end() - 1);
00688         *p = v;
00689     }
00690     return p;
00691 }
00692 
00693 template <class T, class Alloc>
00694 typename ArrayVector<T, Alloc>::iterator
00695 ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type const & v)
00696 {
00697     difference_type pos = p - this->begin();
00698     size_type new_size = this->size() + n;
00699     if(new_size >= capacity_)
00700     {
00701         size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
00702         pointer new_data = reserve_raw(new_capacity);
00703         std::uninitialized_copy(this->begin(), p, new_data);
00704         std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
00705         std::uninitialized_copy(p, this->end(), new_data + pos + n);
00706         deallocate(this->data_, this->size_);
00707         capacity_ = new_capacity;
00708         this->data_ = new_data;
00709     }
00710     else if(pos + n >= this->size_)
00711     {
00712         size_type diff = pos + n - this->size_;
00713         std::uninitialized_copy(p, this->end(), this->end() + diff);
00714         std::uninitialized_fill(this->end(), this->end() + diff, v);
00715         std::fill(p, this->end(), v);
00716     }
00717     else
00718     {
00719         size_type diff = this->size_ - (pos + n);
00720         std::uninitialized_copy(this->end() - n, this->end(), this->end());
00721         std::copy_backward(p, p + diff, this->end());
00722         std::fill(p, p + n, v);
00723     }
00724     this->size_ = new_size;
00725     return this->begin() + pos;
00726 }
00727 
00728 template <class T, class Alloc>
00729 template <class InputIterator>
00730 typename ArrayVector<T, Alloc>::iterator
00731 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
00732 {
00733     size_type n = iend - i;
00734     size_type pos = p - this->begin();
00735     size_type new_size = this->size() + n;
00736     if(new_size >= capacity_)
00737     {
00738         size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
00739         pointer new_data = reserve_raw(new_capacity);
00740         std::uninitialized_copy(this->begin(), p, new_data);
00741         std::uninitialized_copy(i, iend, new_data + pos);
00742         std::uninitialized_copy(p, this->end(), new_data + pos + n);
00743         deallocate(this->data_, this->size_);
00744         capacity_ = new_capacity;
00745         this->data_ = new_data;
00746     }
00747     else if(pos + n >= this->size_)
00748     {
00749         size_type diff = pos + n - this->size_;
00750         std::uninitialized_copy(p, this->end(), this->end() + diff);
00751         std::uninitialized_copy(iend - diff, iend, this->end());
00752         std::copy(i, iend - diff, p);
00753     }
00754     else
00755     {
00756         size_type diff = this->size_ - (pos + n);
00757         std::uninitialized_copy(this->end() - n, this->end(), this->end());
00758         std::copy_backward(p, p + diff, this->end());
00759         std::copy(i, iend, p);
00760     }
00761     this->size_ = new_size;
00762     return this->begin() + pos;
00763 }
00764 
00765 template <class T, class Alloc>
00766 typename ArrayVector<T, Alloc>::iterator
00767 ArrayVector<T, Alloc>::erase(iterator p)
00768 {
00769     std::copy(p+1, this->end(), p);
00770     pop_back();
00771     return p;
00772 }
00773 
00774 template <class T, class Alloc>
00775 typename ArrayVector<T, Alloc>::iterator
00776 ArrayVector<T, Alloc>::erase(iterator p, iterator q)
00777 {
00778     std::copy(q, this->end(), p);
00779     difference_type eraseCount = q - p;
00780     detail::destroy_n(this->end() - eraseCount, eraseCount);
00781     this->size_ -= eraseCount;
00782     return p;
00783 }
00784 
00785 template <class T, class Alloc>
00786 inline void
00787 ArrayVector<T, Alloc>::reserve( size_type new_capacity )
00788 {
00789     if(new_capacity <= capacity_)
00790         return;
00791     pointer new_data = reserve_raw(new_capacity);
00792     if(this->size_ > 0)
00793         std::uninitialized_copy(this->data_, this->data_+this->size_, new_data);
00794     deallocate(this->data_, this->size_);
00795     this->data_ = new_data;
00796     capacity_ = new_capacity;
00797 }
00798 
00799 template <class T, class Alloc>
00800 inline void
00801 ArrayVector<T, Alloc>::reserve()
00802 {
00803     if(capacity_ == 0)
00804         reserve(minimumCapacity);
00805     else if(this->size_ == capacity_)
00806         reserve(resizeFactor*capacity_);
00807 }
00808 
00809 template <class T, class Alloc>
00810 inline void
00811 ArrayVector<T, Alloc>::resize( size_type new_size, value_type const & initial)
00812 {
00813     if(new_size < this->size_)
00814         erase(this->begin() + new_size, this->end());
00815     else if(this->size_ < new_size)
00816     {
00817         insert(this->end(), new_size - this->size(), initial);
00818     }
00819 }
00820 
00821 template <class T, class Alloc>
00822 inline void
00823 ArrayVector<T, Alloc>::initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/)
00824 {
00825     this->size_ = size;
00826     capacity_ = size;
00827     this->data_ = reserve_raw(capacity_);
00828     if(this->size_ > 0)
00829         std::uninitialized_fill(this->data_, this->data_+this->size_, initial);
00830 }
00831 
00832 template <class T, class Alloc>
00833 template <class Iter>
00834 inline void
00835 ArrayVector<T, Alloc>::initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/)
00836 {
00837     this->size_ = std::distance(i, end);
00838     capacity_ = this->size_;
00839     this->data_ = reserve_raw(capacity_);
00840     if(this->size_ > 0)
00841         std::uninitialized_copy(i, end, this->data_);
00842 }
00843 
00844 template <class T, class Alloc>
00845 inline void
00846 ArrayVector<T, Alloc>::swap(this_type & rhs)
00847 {
00848     std::swap(this->size_, rhs.size_);
00849     std::swap(capacity_, rhs.capacity_);
00850     std::swap(this->data_, rhs.data_);
00851 }
00852 
00853 template <class T, class Alloc>
00854 inline void
00855 ArrayVector<T, Alloc>::deallocate(pointer data, size_type size)
00856 {
00857     if(data)
00858     {
00859         detail::destroy_n(data, (int)size);
00860         alloc_.deallocate(data, size);
00861     }
00862 }
00863 
00864 template <class T, class Alloc>
00865 inline typename ArrayVector<T, Alloc>::pointer
00866 ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
00867 {
00868     pointer data = 0;
00869     if(capacity)
00870     {
00871         data = alloc_.allocate(capacity);
00872     }
00873     return data;
00874 }
00875 
00876 } // namespace vigra
00877 
00878 namespace std {
00879 
00880 template <class T>
00881 ostream & operator<<(ostream & s, vigra::ArrayVectorView<T> const & a)
00882 {
00883     for(int k=0; k<(int)a.size()-1; ++k)
00884         s << a[k] << ", ";
00885     if(a.size())
00886             s << a.back();
00887     return s;
00888 }
00889 
00890 } // namespace std
00891 
00892 #undef VIGRA_ASSERT_INSIDE
00893 #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.0 (15 Apr 2010)