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