[ VIGRA Homepage | Class Index | Function Index | File Index | Main Page ]
![]() |
vigra/array_vector.hxx | ![]() |
---|
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) |
html generated using doxygen and Python
|