00001
00002
00003
00004
00005
00006 template <class T> inline void BCP_vec<T>::destroy(iterator pos)
00007 {
00008 pos->~T();
00009 }
00010
00011 template <class T> inline void BCP_vec<T>::destroy_range(iterator first, iterator last)
00012 {
00013 while (first != last) {
00014 (--last)->~T();
00015 }
00016 }
00017
00018 template <class T> inline void BCP_vec<T>::construct(iterator pos)
00019 {
00020 ::new(static_cast<void*>(pos)) T();
00021 }
00022
00023 template <class T> inline void BCP_vec<T>::construct(iterator pos, const_reference x)
00024 {
00025 ::new(static_cast<void*>(pos)) T(x);
00026 }
00027
00028
00029 template <class T> inline typename BCP_vec<T>::iterator
00030 BCP_vec<T>::allocate(size_t len)
00031 {
00032 return static_cast<iterator>(::operator new(len * sizeof(T)));
00033 }
00034
00035 template <class T> inline void BCP_vec<T>::deallocate()
00036 {
00037 if (start) {
00038 destroy_range(start, finish);
00039 ::operator delete(start);
00040 }
00041 }
00042
00043 template <class T> void BCP_vec<T>::insert_aux(iterator position, const_reference x)
00044 {
00045 if (finish != end_of_storage) {
00046 construct(finish);
00047 std::copy_backward(position, finish - 1, finish);
00048 *position = x;
00049 ++finish;
00050 } else {
00051 const size_t len = (2*size() + 0x100);
00052 iterator tmp = allocate(len);
00053 iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
00054 construct(tmp_finish++, x);
00055 tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
00056 deallocate();
00057 start = tmp;
00058 finish = tmp_finish;
00059 end_of_storage = tmp + len;
00060 }
00061 }
00062
00063
00064
00065 template <class T> BCP_vec<T>::BCP_vec() :
00066 start(0), finish(0), end_of_storage(0) {}
00067
00068 template <class T> BCP_vec<T>::BCP_vec(const BCP_vec<T>& x) :
00069 start(0), finish(0), end_of_storage(0)
00070 {
00071 *this = x;
00072 }
00073
00074 template <class T>
00075 BCP_vec<T>::BCP_vec(const size_t n, const_reference value) :
00076 start(0), finish(0), end_of_storage(0)
00077 {
00078 if (n > 0) {
00079 start = allocate(n);
00080 end_of_storage = finish = start + n;
00081 std::uninitialized_fill_n(start, n, value);
00082 }
00083 }
00084
00085 template <class T>
00086 BCP_vec<T>::BCP_vec(const_iterator first, const_iterator last) :
00087 start(0), finish(0), end_of_storage(0)
00088 {
00089 const size_t len = last - first;
00090 if (len > 0) {
00091 start = allocate(len);
00092 end_of_storage = finish = std::uninitialized_copy(first, last, start);
00093 }
00094 }
00095
00096 template <class T>
00097 BCP_vec<T>::BCP_vec(const T* x, const size_t num) :
00098 start(0), finish(0), end_of_storage(0)
00099 {
00100 if (num > 0) {
00101 finish = start = allocate(num);
00102 const T* const lastx = x + num;
00103 while (x != lastx) {
00104 construct(finish++, *x++);
00105 }
00106 end_of_storage = finish;
00107 }
00108 }
00109
00110
00111
00112 template <class T> void BCP_vec<T>::reserve(const size_t n)
00113 {
00114 if (capacity() < n) {
00115 iterator tmp = allocate(n);
00116 iterator tmp_finish = std::uninitialized_copy(start, finish, tmp);
00117 deallocate();
00118 start = tmp;
00119 finish = tmp_finish;
00120 end_of_storage = start + n;
00121 }
00122 }
00123
00124 template <class T> inline void BCP_vec<T>::swap(BCP_vec<T>& x)
00125 {
00126 std::swap(start, x.start);
00127 std::swap(finish, x.finish);
00128 std::swap(end_of_storage, x.end_of_storage);
00129 }
00130
00131 template <class T> BCP_vec<T>& BCP_vec<T>::operator=(const BCP_vec<T>& x)
00132 {
00133 if (&x != this) {
00134 const size_t x_size = x.size();
00135 if (x_size > capacity()) {
00136 deallocate();
00137 start = allocate(x_size);
00138 end_of_storage = start + x_size;
00139 finish = std::uninitialized_copy(x.begin(), x.end(), start);
00140 } else {
00141 if (x_size < size()) {
00142 iterator oldfinish = finish;
00143 finish = std::copy(x.begin(), x.end(), start);
00144 destroy_range(finish, oldfinish);
00145 } else {
00146 std::copy(x.begin(), x.entry(size()), start);
00147 finish = std::uninitialized_copy(x.entry(size()), x.end(), finish);
00148 }
00149 }
00150 }
00151 return *this;
00152 }
00153
00154
00155
00156
00157 template <class T> void BCP_vec<T>::assign(const void* x, const size_t num)
00158 {
00159 if (num > capacity()){
00160 deallocate();
00161 start = allocate(num);
00162 end_of_storage = start + num;
00163 } else {
00164 destroy_range(start, finish);
00165 }
00166 T entry;
00167 finish = start;
00168 const char* charx = static_cast<const char*>(x);
00169 for (int i = num; i > 0; --i) {
00170 memcpy(&entry, charx, sizeof(T));
00171 construct(finish++, entry);
00172 charx += sizeof(T);
00173 }
00174 }
00175
00176 template <class T> void BCP_vec<T>::insert(iterator position,
00177 const void* first, const size_t n)
00178 {
00179 if (n == 0) return;
00180 T entry;
00181 const char* charx = static_cast<const char*>(first);
00182 if ((size_t) (end_of_storage - finish) >= n) {
00183 const size_t to_move = finish - position;
00184 if (to_move <= n) {
00185 std::uninitialized_copy(position, finish, position + n);
00186 finish += n;
00187 size_t i = n;
00188 for ( ; i > to_move; --i) {
00189 memcpy(&entry, charx, sizeof(T));
00190 construct(position++, entry);
00191 charx += sizeof(T);
00192 }
00193 for ( ; i > 0; --i) {
00194 memcpy(&entry, charx, sizeof(T));
00195 *position++ = entry;
00196 charx += sizeof(T);
00197 }
00198 } else {
00199 std::uninitialized_copy(finish - n, finish, finish);
00200 std::copy_backward(position, finish - n, finish);
00201 finish += n;
00202 for (int i = n; i > 0; --i) {
00203 memcpy(&entry, charx, sizeof(T));
00204 *position++ = entry;
00205 charx += sizeof(T);
00206 }
00207 }
00208 } else {
00209 const size_t new_size = (2*size() + n);
00210 iterator tmp = allocate(new_size);
00211 iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
00212 for (int i = n; i > 0; --i) {
00213 memcpy(&entry, charx, sizeof(T));
00214 construct(tmp_finish++, entry);
00215 charx += sizeof(T);
00216 }
00217 tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
00218 deallocate();
00219 start = tmp;
00220 finish = tmp_finish;
00221 end_of_storage = tmp + new_size;
00222 }
00223 }
00224
00225 template <class T> void BCP_vec<T>::insert(iterator position,
00226 const_iterator first,
00227 const_iterator last)
00228 {
00229 if (first == last) return;
00230 const size_t n = last - first;
00231 if ((size_t) (end_of_storage - finish) >= n) {
00232 const size_t to_move = finish - position;
00233 if (to_move <= n) {
00234 std::uninitialized_copy(position, finish, position + n);
00235 std::copy(first, first + to_move, position);
00236 std::uninitialized_copy(first + to_move, last, finish);
00237 } else {
00238 std::uninitialized_copy(finish - n, finish, finish);
00239 std::copy_backward(position, finish - n, finish);
00240 std::copy(first, last, position);
00241 }
00242 finish += n;
00243 } else {
00244 const size_t new_size = (2*size() + n);
00245 iterator tmp = allocate(new_size);
00246 iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
00247 tmp_finish = std::uninitialized_copy(first, last, tmp_finish);
00248 tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
00249 deallocate();
00250 start = tmp;
00251 finish = tmp_finish;
00252 end_of_storage = tmp + new_size;
00253 }
00254 }
00255
00256 template <class T> void BCP_vec<T>::insert(iterator position, const size_t n,
00257 const_reference x)
00258 {
00259 if (n == 0) return;
00260 if ((size_t) (end_of_storage - finish) >= n) {
00261 const size_t to_move = finish - position;
00262 if (to_move <= n) {
00263 std::uninitialized_copy(position, finish, position + n);
00264 std::fill_n(position, to_move, x);
00265 std::uninitialized_fill_n(finish, n - to_move, x);
00266 } else {
00267 std::uninitialized_copy(finish - n, finish, finish);
00268 std::copy_backward(position, finish - n, finish);
00269 std::fill_n(position, n, x);
00270 }
00271 finish += n;
00272 } else {
00273 const size_t new_size = (2*size() + n);
00274 iterator tmp = allocate(new_size);
00275 iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
00276 std::uninitialized_fill_n(tmp_finish, n, x);
00277 tmp_finish += n;
00278 tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
00279 deallocate();
00280 start = tmp;
00281 finish = tmp_finish;
00282 end_of_storage = tmp + new_size;
00283 }
00284 }
00285
00286 template <class T> inline typename BCP_vec<T>::iterator
00287 BCP_vec<T>::insert(iterator position, const_reference x)
00288 {
00289 const size_t n = position - start;
00290 if (finish != end_of_storage && position == finish) {
00291 construct(finish++, x);
00292 } else {
00293 insert_aux(position, x);
00294 }
00295 return start + n;
00296 }
00297
00298
00299
00300 template <class T> inline void BCP_vec<T>::push_back(const_reference x)
00301 {
00302 if (finish != end_of_storage) {
00303 construct(finish++, x);
00304 } else
00305 insert_aux(finish, x);
00306 }
00307
00308 template <class T> inline void BCP_vec<T>::unchecked_push_back(const_reference x)
00309 {
00310 construct(finish++, x);
00311 }
00312
00313 template <class T> inline void BCP_vec<T>::pop_back()
00314 {
00315 destroy(--finish);
00316 }
00317
00318 template <class T> inline void BCP_vec<T>::clear()
00319 {
00320 if (start) erase(start, finish);
00321 }
00322
00323 template <class T> void
00324 BCP_vec<T>::unchecked_update(const BCP_vec<int>& positions,
00325 const BCP_vec<T>& values)
00326 {
00327 if (positions.size() == 0)
00328 return;
00329 const_iterator val = values.begin();
00330 BCP_vec<int>::const_iterator pos = positions.begin();
00331 const BCP_vec<int>::const_iterator lastpos = positions.end();
00332 while (pos != lastpos)
00333 operator[](*pos++) = *val++;
00334 }
00335
00336 template <class T> inline void BCP_vec<T>::update(const BCP_vec<int>& positions,
00337 const BCP_vec<T>& values)
00338 {
00339 if (positions.size() != values.size())
00340 throw BCP_fatal_error("BCP_vec::update() called with unequal sizes.\n");
00341 BCP_vec_sanity_check(positions.begin(), positions.end(), size());
00342 unchecked_update(positions, values);
00343 }
00344
00345
00346
00347 template <class T> inline void BCP_vec<T>::keep(iterator pos)
00348 {
00349 iterator oldfinish = finish;
00350 finish = std::copy(pos, pos + 1, start);
00351 destroy_range(finish, oldfinish);
00352 }
00353
00354 template <class T> inline void BCP_vec<T>::keep(iterator first, iterator last)
00355 {
00356 iterator oldfinish = finish;
00357 finish = std::copy(first, last, start);
00358 destroy_range(finish, oldfinish);
00359 }
00360
00361 template <class T> inline void
00362 BCP_vec<T>::keep_by_index(const BCP_vec<int>& positions)
00363 {
00364 BCP_vec_sanity_check(positions.begin(), positions.end(), size());
00365 unchecked_keep_by_index(positions.begin(), positions.end());
00366 }
00367
00368 template <class T> inline void
00369 BCP_vec<T>::unchecked_keep_by_index(const BCP_vec<int>& positions)
00370 {
00371 unchecked_keep_by_index(positions.begin(), positions.end());
00372 }
00373
00374 template <class T> inline void
00375 BCP_vec<T>::keep_by_index(BCP_vec<int>::const_iterator firstpos,
00376 BCP_vec<int>::const_iterator lastpos)
00377 {
00378 BCP_vec_sanity_check(firstpos, lastpos, size());
00379 unchecked_keep_by_index(firstpos, lastpos);
00380 }
00381
00382 template <class T> void
00383 BCP_vec<T>::unchecked_keep_by_index(BCP_vec<int>::const_iterator firstpos,
00384 BCP_vec<int>::const_iterator lastpos)
00385 {
00386 if (firstpos == lastpos) {
00387 clear();
00388 } else {
00389 iterator target = start;
00390 while ( firstpos != lastpos )
00391 *target++ = operator[](*firstpos++);
00392 destroy_range(target, finish);
00393 finish = target;
00394 }
00395 }
00396
00397
00398
00399 template <class T> inline void BCP_vec<T>::erase(iterator position)
00400 {
00401 if (position + 1 != finish)
00402 std::copy(position + 1, finish, position);
00403 destroy(--finish);
00404 }
00405
00406 template <class T> inline void BCP_vec<T>::erase(iterator first, iterator last)
00407 {
00408 iterator oldfinish = finish;
00409 finish = std::copy(last, finish, first);
00410 destroy_range(finish, oldfinish);
00411 }
00412
00413 template <class T> inline void
00414 BCP_vec<T>::erase_by_index(const BCP_vec<int>& positions)
00415 {
00416 BCP_vec_sanity_check(positions.begin(), positions.end(), size());
00417 unchecked_erase_by_index(positions.begin(), positions.end());
00418 }
00419
00420 template <class T> inline void
00421 BCP_vec<T>::unchecked_erase_by_index(const BCP_vec<int>& positions)
00422 {
00423 unchecked_erase_by_index(positions.begin(), positions.end());
00424 }
00425
00426 template <class T> inline void
00427 BCP_vec<T>::erase_by_index(BCP_vec<int>::const_iterator firstpos,
00428 BCP_vec<int>::const_iterator lastpos)
00429 {
00430 BCP_vec_sanity_check(firstpos, lastpos, size());
00431 unchecked_erase_by_index(firstpos, lastpos);
00432 }
00433
00434 template <class T> void
00435 BCP_vec<T>::unchecked_erase_by_index(BCP_vec<int>::const_iterator firstpos,
00436 BCP_vec<int>::const_iterator lastpos)
00437 {
00438 if (firstpos == lastpos)
00439 return;
00440 --lastpos;
00441 int source;
00442 iterator target = entry(*firstpos);
00443 while (firstpos != lastpos){
00444 source = *firstpos + 1;
00445 ++firstpos;
00446 if (*firstpos > source)
00447 target = std::copy( entry(source), entry(*firstpos), target );
00448 }
00449 iterator oldfinish = finish;
00450 finish = std::copy( entry(*firstpos + 1), end(), target );
00451 destroy_range(finish, oldfinish);
00452 }
00453
00454