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