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

details vigra/array_vector.hxx VIGRA

00001 /************************************************************************/
00002 /*                                                                      */
00003 /*               Copyright 2002-2003 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.2.0, Aug 07 2003 )                                    */
00008 /*    You may use, modify, and distribute this software according       */
00009 /*    to the terms stated in the LICENSE file included in               */
00010 /*    the VIGRA distribution.                                           */
00011 /*                                                                      */
00012 /*    The VIGRA Website is                                              */
00013 /*        http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/      */
00014 /*    Please direct questions, bug reports, and contributions to        */
00015 /*        koethe@informatik.uni-hamburg.de                              */
00016 /*                                                                      */
00017 /*  THIS SOFTWARE IS PROVIDED AS IS AND WITHOUT ANY EXPRESS OR          */
00018 /*  IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED      */
00019 /*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. */
00020 /*                                                                      */
00021 /************************************************************************/
00022 
00023 #ifndef VIGRA_ARRAY_VECTOR_HXX
00024 #define VIGRA_ARRAY_VECTOR_HXX
00025 
00026 #include <memory>
00027 #include <algorithm>
00028 #include <vigra/memory.hxx>
00029 
00030 namespace vigra
00031 {
00032 
00033 template <class T>
00034 class ArrayVector
00035 {
00036     typedef ArrayVector<T> this_type;
00037 
00038 public:
00039     typedef T value_type;
00040     typedef value_type & reference;
00041     typedef value_type const & const_reference;
00042     typedef value_type * pointer;
00043     typedef value_type const * const_pointer;
00044     typedef value_type * iterator;
00045     typedef value_type const * const_iterator;
00046     typedef unsigned int size_type;
00047     typedef int          difference_type;
00048 
00049 public:
00050     ArrayVector();
00051 
00052     ArrayVector( size_type size);
00053 
00054     ArrayVector( size_type size, value_type const & initial);
00055 
00056     ArrayVector( this_type const & rhs );
00057 
00058     template <class InputIterator>
00059     ArrayVector(InputIterator i, InputIterator end);
00060 
00061     this_type & operator=( this_type const & rhs );
00062 
00063     ~ArrayVector();
00064 
00065     inline const_pointer data() const
00066     {
00067         return data_;
00068     }
00069 
00070     inline pointer data()
00071     {
00072         return data_;
00073     }
00074 
00075     inline const_iterator begin() const
00076     {
00077         return data();
00078     }
00079 
00080     inline iterator begin()
00081     {
00082         return data();
00083     }
00084 
00085     inline const_iterator end() const
00086     {
00087         return data() + size();
00088     }
00089 
00090     inline iterator end()
00091     {
00092         return data() + size();
00093     }
00094 
00095     reference front()
00096     {
00097         return *data_;
00098     }
00099 
00100     const_reference front() const
00101     {
00102         return *data_;
00103     }
00104 
00105     reference back()
00106     {
00107         return data_[size_-1];
00108     }
00109 
00110     const_reference back() const
00111     {
00112         return data_[size_-1];
00113     }
00114 
00115     reference operator[]( size_type i )
00116     {
00117         return data()[i];
00118     }
00119 
00120     const_reference operator[]( size_type i ) const
00121     {
00122         return data()[i];
00123     }
00124 
00125     void pop_back();
00126 
00127     void push_back( value_type const & t );
00128 
00129     iterator insert(iterator p, value_type const & v);
00130 
00131     iterator insert(iterator p, size_type n, value_type const & v);
00132 
00133     template <class InputIterator>
00134     iterator insert(iterator p, InputIterator i, InputIterator iend);
00135 
00136     iterator erase(iterator p);
00137 
00138     iterator erase(iterator p, iterator q);
00139 
00140     void clear();
00141 
00142     void reserve( size_type new_capacity );
00143 
00144     void reserve();
00145 
00146     void resize( size_type new_size, value_type const & initial );
00147 
00148     void resize( size_type new_size )
00149     {
00150         resize(new_size, value_type());
00151     }
00152 
00153     bool empty() const
00154     {
00155         return size_ == 0;
00156     }
00157 
00158     size_type size() const
00159     {
00160         return size_;
00161     }
00162 
00163     size_type capacity() const
00164     {
00165         return capacity_;
00166     }
00167 
00168     void swap(this_type & rhs);
00169 
00170   private:
00171 
00172     static void deallocate(pointer data, size_type size);
00173 
00174     static pointer reserve_raw(size_type capacity);
00175 
00176     size_type size_, capacity_;
00177     pointer data_;
00178 };
00179 
00180 template <class T>
00181 ArrayVector<T>::ArrayVector()
00182 : size_(0),
00183   capacity_(5),
00184   data_(reserve_raw(5))
00185 {}
00186 
00187 template <class T>
00188 ArrayVector<T>::ArrayVector( size_type size)
00189 : size_(size),
00190   capacity_(size),
00191   data_(reserve_raw(size))
00192 {
00193     if(size_ > 0)
00194         std::uninitialized_fill(data_, data_+size_, value_type());
00195 }
00196 
00197 template <class T>
00198 ArrayVector<T>::ArrayVector( size_type size, value_type const & initial)
00199 : size_(size),
00200   capacity_(size),
00201   data_(reserve_raw(size))
00202 {
00203     if(size_ > 0)
00204         std::uninitialized_fill(data_, data_+size_, initial);
00205 }
00206 
00207 template <class T>
00208 ArrayVector<T>::ArrayVector( this_type const & rhs )
00209 : size_(rhs.size_),
00210   capacity_(rhs.capacity_),
00211   data_(reserve_raw(rhs.capacity_))
00212 {
00213     if(size_ > 0)
00214         std::uninitialized_copy(rhs.data_, rhs.data_+size_, data_);
00215 }
00216 
00217 template <class T>
00218 template <class InputIterator>
00219 ArrayVector<T>::ArrayVector(InputIterator i, InputIterator end)
00220 : size_(std::distance(i, end)),
00221   capacity_(size_),
00222   data_(reserve_raw(size_))
00223 {
00224     std::uninitialized_copy(i, end, data_);
00225 }
00226 
00227 
00228 template <class T>
00229 ArrayVector<T> & ArrayVector<T>::operator=( this_type const & rhs )
00230 {
00231     if(this == &rhs)
00232         return *this;
00233     ArrayVector new_vector(rhs);
00234     swap(new_vector);
00235     return *this;
00236 }
00237 
00238 template <class T>
00239 ArrayVector<T>::~ArrayVector()
00240 {
00241     deallocate(data_, size_);
00242 }
00243 
00244 template <class T>
00245 void ArrayVector<T>::pop_back()
00246 {
00247     --size_;
00248     detail::destroy(data_ + size_);
00249 }
00250 
00251 template <class T>
00252 void ArrayVector<T>::push_back( value_type const & t )
00253 {
00254     reserve();
00255     new (static_cast<void*>(data_ + size_)) T(t);
00256     ++size_;
00257 }
00258 
00259 template <class T>
00260 void ArrayVector<T>::clear()
00261 {
00262     detail::destroy_n(data_, size_);
00263     size_ = 0;
00264 }
00265 
00266 template <class T>
00267 typename ArrayVector<T>::iterator
00268 ArrayVector<T>::insert(iterator p, value_type const & v)
00269 {
00270     difference_type pos = p - begin();
00271     if(p == end())
00272     {
00273         push_back(v);
00274         p = begin() + pos;
00275     }
00276     else
00277     {
00278         push_back(back());
00279         p = begin() + pos;
00280         std::copy_backward(p, end() - 2, end() - 1);
00281         *p = v;
00282     }
00283     return p;
00284 }
00285 
00286 template <class T>
00287 typename ArrayVector<T>::iterator
00288 ArrayVector<T>::insert(iterator p, size_type n, value_type const & v)
00289 {
00290     difference_type pos = p - begin();
00291     size_type new_size = size() + n;
00292     if(new_size >= capacity_)
00293     {
00294         pointer new_data = reserve_raw(new_size);
00295         std::uninitialized_copy(begin(), p, new_data);
00296         std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
00297         std::uninitialized_copy(p, end(), new_data + pos + n);
00298         deallocate(data_, size_);
00299         capacity_ = new_size;
00300         data_ = new_data;
00301     }
00302     else if(pos + n >= size_)
00303     {
00304         size_type diff = pos + n - size_;
00305         std::uninitialized_copy(p, end(), end() + diff);
00306         std::uninitialized_fill(end(), end() + diff, v);
00307         std::fill(p, end(), v);
00308     }
00309     else
00310     {
00311         size_type diff = size_ - (pos + n);
00312         std::uninitialized_copy(end() - n, end(), end());
00313         std::copy_backward(p, p + diff, end());
00314         std::fill(p, p + n, v);
00315     }
00316     size_ = new_size;
00317     return begin() + pos;
00318 }
00319 
00320 template <class T>
00321 template <class InputIterator>
00322 typename ArrayVector<T>::iterator
00323 ArrayVector<T>::insert(iterator p, InputIterator i, InputIterator iend)
00324 {
00325     difference_type n = iend - i;
00326     difference_type pos = p - begin();
00327     size_type new_size = size() + n;
00328     if(new_size >= capacity_)
00329     {
00330         pointer new_data = reserve_raw(new_size);
00331         std::uninitialized_copy(begin(), p, new_data);
00332         std::uninitialized_copy(i, iend, new_data + pos);
00333         std::uninitialized_copy(p, end(), new_data + pos + n);
00334         std::deallocate(data_, size_);
00335         capacity_ = new_size;
00336         data_ = new_data;
00337     }
00338     else if(pos + n >= size_)
00339     {
00340         size_type diff = pos + n - size_;
00341         std::uninitialized_copy(p, end(), end() + diff);
00342         std::uninitialized_copy(iend - diff, iend, end());
00343         std::copy(i, iend - diff, p);
00344     }
00345     else
00346     {
00347         size_type diff = size_ - (pos + n);
00348         std::uninitialized_copy(end() - n, end(), end());
00349         std::copy_backward(p, p + diff, end());
00350         std::copy(i, iend, p);
00351     }
00352     size_ = new_size;
00353     return begin() + pos;
00354 }
00355 
00356 template <class T>
00357 typename ArrayVector<T>::iterator
00358 ArrayVector<T>::erase(iterator p)
00359 {
00360     std::copy(p+1, end(), p);
00361     pop_back();
00362     return p;
00363 }
00364 
00365 template <class T>
00366 typename ArrayVector<T>::iterator
00367 ArrayVector<T>::erase(iterator p, iterator q)
00368 {
00369     std::copy(q, end(), p);
00370     size_type eraseCount = q - p;
00371     detail::destroy_n(end() - eraseCount, eraseCount);
00372     size_ -= eraseCount;
00373     return p;
00374 }
00375 
00376 template <class T>
00377 void ArrayVector<T>::reserve( size_type new_capacity )
00378 {
00379     if(new_capacity <= capacity_)
00380         return;
00381     pointer new_data = reserve_raw(new_capacity);
00382     if(size_ > 0)
00383         std::uninitialized_copy(data_, data_+size_, new_data);
00384     deallocate(data_, size_);
00385     data_ = new_data;
00386     capacity_ = new_capacity;
00387 }
00388 
00389 template <class T>
00390 void ArrayVector<T>::reserve()
00391 {
00392     if(size_ == capacity_)
00393         reserve(2*capacity_);
00394 }
00395 
00396 template <class T>
00397 void ArrayVector<T>::resize( size_type new_size, value_type const & initial)
00398 {
00399     if(new_size < size_)
00400         erase(begin() + new_size, end());
00401     else if(size_ < new_size)
00402     {
00403         insert(end(), new_size - size(), initial);
00404     }
00405 }
00406 
00407 template <class T>
00408 void ArrayVector<T>::swap(this_type & rhs)
00409 {
00410     std::swap(size_, rhs.size_);
00411     std::swap(capacity_, rhs.capacity_);
00412     std::swap(data_, rhs.data_);
00413 }
00414 
00415 template <class T>
00416 void ArrayVector<T>::deallocate(pointer data, size_type size)
00417 {
00418     if(data)
00419     {
00420         detail::destroy_n(data, size);
00421         ::operator delete(data);
00422     }
00423 }
00424 
00425 template <class T>
00426 typename ArrayVector<T>::pointer
00427 ArrayVector<T>::reserve_raw(size_type capacity)
00428 {
00429     pointer data = 0;
00430     if(capacity)
00431         data = static_cast<pointer>(::operator new(capacity*sizeof(value_type)));
00432     return data;
00433 }
00434 
00435 } // namespace vigra
00436 
00437 
00438 #endif /* VIGRA_ARRAY_VECTOR_HXX */

© Ullrich Köthe (koethe@informatik.uni-hamburg.de)
Cognitive Systems Group, University of Hamburg, Germany

html generated using doxygen and Python
VIGRA 1.2.0 (7 Aug 2003)