1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/_bvector.h Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,839 @@
1.4 +/*
1.5 + *
1.6 + * Copyright (c) 1994
1.7 + * Hewlett-Packard Company
1.8 + *
1.9 + * Copyright (c) 1996,1997
1.10 + * Silicon Graphics Computer Systems, Inc.
1.11 + *
1.12 + * Copyright (c) 1997
1.13 + * Moscow Center for SPARC Technology
1.14 + *
1.15 + * Copyright (c) 1999
1.16 + * Boris Fomitchev
1.17 + *
1.18 + * This material is provided "as is", with absolutely no warranty expressed
1.19 + * or implied. Any use is at your own risk.
1.20 + *
1.21 + * Permission to use or copy this software for any purpose is hereby granted
1.22 + * without fee, provided the above notices are retained on all copies.
1.23 + * Permission to modify the code and to distribute modified code is granted,
1.24 + * provided the above notices are retained, and a notice that the code was
1.25 + * modified is included with the above copyright notice.
1.26 + *
1.27 + */
1.28 +
1.29 +/* NOTE: This is an internal header file, included by other STL headers.
1.30 + * You should not attempt to use it directly.
1.31 + */
1.32 +
1.33 +#ifndef _STLP_INTERNAL_BVECTOR_H
1.34 +#define _STLP_INTERNAL_BVECTOR_H
1.35 +
1.36 +#ifndef _STLP_INTERNAL_VECTOR_H
1.37 +# include <stl/_vector.h>
1.38 +#endif
1.39 +
1.40 +#define _STLP_WORD_BIT (int(CHAR_BIT*sizeof(unsigned int)))
1.41 +
1.42 +_STLP_BEGIN_NAMESPACE
1.43 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.44 +
1.45 +struct _Bit_reference {
1.46 + unsigned int* _M_p;
1.47 + unsigned int _M_mask;
1.48 + _Bit_reference(unsigned int* __x, unsigned int __y)
1.49 + : _M_p(__x), _M_mask(__y) {}
1.50 +
1.51 +public:
1.52 + _Bit_reference() : _M_p(0), _M_mask(0) {}
1.53 +
1.54 + operator bool() const {
1.55 + return !(!(*_M_p & _M_mask));
1.56 + }
1.57 + _Bit_reference& operator = (bool __x) {
1.58 + if (__x) *_M_p |= _M_mask;
1.59 + else *_M_p &= ~_M_mask;
1.60 + return *this;
1.61 + }
1.62 + _Bit_reference& operator = (const _Bit_reference& __x) {
1.63 + return *this = bool(__x);
1.64 + }
1.65 + bool operator == (const _Bit_reference& __x) const {
1.66 + return bool(*this) == bool(__x);
1.67 + }
1.68 + bool operator < (const _Bit_reference& __x) const {
1.69 + return !bool(*this) && bool(__x);
1.70 + }
1.71 +
1.72 + _Bit_reference& operator |= (bool __x) {
1.73 + if (__x)
1.74 + *_M_p |= _M_mask;
1.75 + return *this;
1.76 + }
1.77 + _Bit_reference& operator &= (bool __x) {
1.78 + if (!__x)
1.79 + *_M_p &= ~_M_mask;
1.80 + return *this;
1.81 + }
1.82 + void flip() { *_M_p ^= _M_mask; }
1.83 +};
1.84 +
1.85 +
1.86 +_STLP_MOVE_TO_STD_NAMESPACE
1.87 +
1.88 +inline void swap(_STLP_PRIV _Bit_reference& __x, _STLP_PRIV _Bit_reference& __y) {
1.89 + bool __tmp = (bool)__x;
1.90 + __x = __y;
1.91 + __y = __tmp;
1.92 +}
1.93 +
1.94 +// Might not be very useful but costs nothing!
1.95 +_STLP_TEMPLATE_NULL
1.96 +struct __type_traits<_STLP_PRIV _Bit_reference> {
1.97 + typedef __false_type has_trivial_default_constructor;
1.98 + typedef __true_type has_trivial_copy_constructor;
1.99 + typedef __false_type has_trivial_assignment_operator;
1.100 + typedef __true_type has_trivial_destructor;
1.101 + typedef __false_type is_POD_type;
1.102 +};
1.103 +
1.104 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.105 +
1.106 +struct _Bit_iterator_base {
1.107 + typedef ptrdiff_t difference_type;
1.108 +
1.109 + unsigned int* _M_p;
1.110 + unsigned int _M_offset;
1.111 +
1.112 + void _M_bump_up() {
1.113 + if (_M_offset++ == _STLP_WORD_BIT - 1) {
1.114 + _M_offset = 0;
1.115 + ++_M_p;
1.116 + }
1.117 + }
1.118 +
1.119 + void _M_bump_down() {
1.120 + if (_M_offset-- == 0) {
1.121 + _M_offset = _STLP_WORD_BIT - 1;
1.122 + --_M_p;
1.123 + }
1.124 + }
1.125 +
1.126 + _Bit_iterator_base() : _M_p(0), _M_offset(0) {}
1.127 + _Bit_iterator_base(unsigned int* __x, unsigned int __y) : _M_p(__x), _M_offset(__y) {}
1.128 +// see comment in doc/README.evc4
1.129 +// TODO: since this still applies to the MIPS compiler delivered with VC8,
1.130 +// but isn't mentioned in its (yet nonexistant) README.evc8.
1.131 +#if defined(_MSC_VER) && _MSC_VER<=1400 && defined(MIPS) && defined(NDEBUG)
1.132 + _Bit_iterator_base( const _Bit_iterator_base& __x) : _M_p(__x._M_p), _M_offset(__x._M_offset) {}
1.133 +#endif
1.134 + // _Bit_iterator_base& operator = ( const _Bit_iterator_base& __x) { _M_p = __x._M_p ; _M_offset = __x._M_offset ; return *this; }
1.135 +
1.136 + void _M_advance (difference_type __i) {
1.137 + difference_type __n = __i + _M_offset;
1.138 + _M_p += __n / _STLP_WORD_BIT;
1.139 + __n = __n % _STLP_WORD_BIT;
1.140 + if (__n < 0) {
1.141 + _M_offset = (unsigned int) __n + _STLP_WORD_BIT;
1.142 + --_M_p;
1.143 + } else
1.144 + _M_offset = (unsigned int) __n;
1.145 + }
1.146 +
1.147 + difference_type _M_subtract(const _Bit_iterator_base& __x) const {
1.148 + return _STLP_WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset;
1.149 + }
1.150 +};
1.151 +
1.152 +inline bool _STLP_CALL operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
1.153 + return __y._M_p == __x._M_p && __y._M_offset == __x._M_offset;
1.154 +}
1.155 +inline bool _STLP_CALL operator!=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
1.156 + return __y._M_p != __x._M_p || __y._M_offset != __x._M_offset;
1.157 +}
1.158 +
1.159 +inline bool _STLP_CALL operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
1.160 + return __x._M_p < __y._M_p || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset);
1.161 +}
1.162 +
1.163 +inline bool _STLP_CALL operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
1.164 + return operator <(__y , __x);
1.165 +}
1.166 +inline bool _STLP_CALL operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
1.167 + return !(__y < __x);
1.168 +}
1.169 +inline bool _STLP_CALL operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
1.170 + return !(__x < __y);
1.171 +}
1.172 +
1.173 +template <class _Ref, class _Ptr>
1.174 +struct _Bit_iter : public _Bit_iterator_base {
1.175 + typedef _Ref reference;
1.176 + typedef _Ptr pointer;
1.177 + typedef _Bit_iter<_Ref, _Ptr> _Self;
1.178 + typedef random_access_iterator_tag iterator_category;
1.179 + typedef bool value_type;
1.180 + typedef ptrdiff_t difference_type;
1.181 + typedef size_t size_type;
1.182 +
1.183 + _Bit_iter(unsigned int* __x, unsigned int __y) : _Bit_iterator_base(__x, __y) {}
1.184 + _Bit_iter() {}
1.185 +
1.186 + _Bit_iter(const _Bit_iter<_Bit_reference, _Bit_reference*>& __x):
1.187 + _Bit_iterator_base((const _Bit_iterator_base&)__x) {}
1.188 +
1.189 + // _Self& operator = (const _Bit_iter<_Bit_reference, _Bit_reference*>& __x)
1.190 + // { (_Bit_iterator_base&)*this = (const _Bit_iterator_base&)__x; return *this; }
1.191 +
1.192 + reference operator*() const {
1.193 + return _Bit_reference(_M_p, 1UL << _M_offset);
1.194 + }
1.195 + _Self& operator++() {
1.196 + _M_bump_up();
1.197 + return *this;
1.198 + }
1.199 + _Self operator++(int) {
1.200 + _Self __tmp = *this;
1.201 + _M_bump_up();
1.202 + return __tmp;
1.203 + }
1.204 + _Self& operator--() {
1.205 + _M_bump_down();
1.206 + return *this;
1.207 + }
1.208 + _Self operator--(int) {
1.209 + _Self __tmp = *this;
1.210 + _M_bump_down();
1.211 + return __tmp;
1.212 + }
1.213 + _Self& operator+=(difference_type __i) {
1.214 + _M_advance(__i);
1.215 + return *this;
1.216 + }
1.217 + _Self& operator-=(difference_type __i) {
1.218 + *this += -__i;
1.219 + return *this;
1.220 + }
1.221 + _Self operator+(difference_type __i) const {
1.222 + _Self __tmp = *this;
1.223 + return __tmp += __i;
1.224 + }
1.225 + _Self operator-(difference_type __i) const {
1.226 + _Self __tmp = *this;
1.227 + return __tmp -= __i;
1.228 + }
1.229 + difference_type operator-(const _Self& __x) const {
1.230 + return _M_subtract(__x);
1.231 + }
1.232 + reference operator[](difference_type __i) { return *(*this + __i); }
1.233 +};
1.234 +
1.235 +template <class _Ref, class _Ptr>
1.236 +inline _Bit_iter<_Ref,_Ptr> _STLP_CALL
1.237 +operator+(ptrdiff_t __n, const _Bit_iter<_Ref, _Ptr>& __x) {
1.238 + return __x + __n;
1.239 +}
1.240 +
1.241 +_STLP_MOVE_TO_STD_NAMESPACE
1.242 +
1.243 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.244 +template <class _Ref, class _Ptr>
1.245 +struct __type_traits< _STLP_PRIV _Bit_iter<_Ref, _Ptr> > {
1.246 + typedef __false_type has_trivial_default_constructor;
1.247 + typedef __true_type has_trivial_copy_constructor;
1.248 + typedef __true_type has_trivial_assignment_operator;
1.249 + typedef __true_type has_trivial_destructor;
1.250 + typedef __false_type is_POD_type;
1.251 +};
1.252 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.253 +
1.254 +#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
1.255 +inline random_access_iterator_tag iterator_category(const _STLP_PRIV _Bit_iterator_base&)
1.256 +{ return random_access_iterator_tag(); }
1.257 +inline ptrdiff_t* distance_type(const _STLP_PRIV _Bit_iterator_base&)
1.258 +{ return (ptrdiff_t*)0; }
1.259 +inline bool* value_type(const _STLP_PRIV _Bit_iter<_STLP_PRIV _Bit_reference, _STLP_PRIV _Bit_reference*>&)
1.260 +{ return (bool*)0; }
1.261 +inline bool* value_type(const _STLP_PRIV _Bit_iter<bool, const bool*>&)
1.262 +{ return (bool*)0; }
1.263 +#endif
1.264 +
1.265 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.266 +
1.267 +typedef _Bit_iter<bool, const bool*> _Bit_const_iterator;
1.268 +typedef _Bit_iter<_Bit_reference, _Bit_reference*> _Bit_iterator;
1.269 +
1.270 +// Bit-vector base class, which encapsulates the difference between
1.271 +// old SGI-style allocators and standard-conforming allocators.
1.272 +template <class _Alloc>
1.273 +class _Bvector_base {
1.274 + typedef _Bvector_base<_Alloc> _Self;
1.275 +public:
1.276 + _STLP_FORCE_ALLOCATORS(bool, _Alloc)
1.277 + typedef typename _Alloc_traits<bool, _Alloc>::allocator_type allocator_type;
1.278 + typedef unsigned int __chunk_type;
1.279 + typedef typename _Alloc_traits<__chunk_type,
1.280 + _Alloc>::allocator_type __chunk_allocator_type;
1.281 + allocator_type get_allocator() const {
1.282 + return _STLP_CONVERT_ALLOCATOR((const __chunk_allocator_type&)_M_end_of_storage, bool);
1.283 + }
1.284 + static allocator_type __get_dfl_allocator() { return allocator_type(); }
1.285 +
1.286 + _Bvector_base(const allocator_type& __a)
1.287 + : _M_start(), _M_finish(), _M_end_of_storage(_STLP_CONVERT_ALLOCATOR(__a, __chunk_type),
1.288 + (__chunk_type*)0)
1.289 + {}
1.290 + _Bvector_base(__move_source<_Self> src)
1.291 + : _M_start(src.get()._M_start), _M_finish(src.get()._M_finish),
1.292 + _M_end_of_storage(src.get()._M_end_of_storage) {
1.293 + //Make the source destroyable
1.294 + src.get()._M_start._M_p = 0;
1.295 + }
1.296 +
1.297 + ~_Bvector_base() {
1.298 + _M_deallocate();
1.299 + }
1.300 +
1.301 +protected:
1.302 +
1.303 + unsigned int* _M_bit_alloc(size_t __n) {
1.304 + return _M_end_of_storage.allocate((__n + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT);
1.305 + }
1.306 + void _M_deallocate() {
1.307 + if (_M_start._M_p)
1.308 + _M_end_of_storage.deallocate(_M_start._M_p,
1.309 + _M_end_of_storage._M_data - _M_start._M_p);
1.310 + }
1.311 +
1.312 + _Bit_iterator _M_start;
1.313 + _Bit_iterator _M_finish;
1.314 + _STLP_alloc_proxy<__chunk_type*, __chunk_type, __chunk_allocator_type> _M_end_of_storage;
1.315 +};
1.316 +
1.317 +
1.318 +// The next few lines are confusing. What we're doing is declaring a
1.319 +// partial specialization of vector<T, Alloc> if we have the necessary
1.320 +// compiler support. Otherwise, we define a class bit_vector which uses
1.321 +// the default allocator.
1.322 +
1.323 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_BOOL) && !defined (__SUNPRO_CC)
1.324 +# define _STLP_VECBOOL_TEMPLATE
1.325 +# define __BVEC_TMPL_HEADER template <class _Alloc>
1.326 +#else
1.327 +# undef _STLP_VECBOOL_TEMPLATE
1.328 +# ifdef _STLP_NO_BOOL
1.329 +# define __BVEC_TMPL_HEADER
1.330 +# else
1.331 +# define __BVEC_TMPL_HEADER _STLP_TEMPLATE_NULL
1.332 +# endif
1.333 +# if !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__))) //*TY 12/17/2000 -
1.334 +# define _Alloc _STLP_DEFAULT_ALLOCATOR(bool)
1.335 +# else
1.336 +# define _Alloc allocator<bool>
1.337 +# endif
1.338 +#endif
1.339 +
1.340 +#if defined (_STLP_DEBUG)
1.341 +# define vector _STLP_NON_DBG_NAME(vector)
1.342 +#endif
1.343 +
1.344 +#ifdef _STLP_NO_BOOL
1.345 +# define __BVECTOR_QUALIFIED bit_vector
1.346 +# define __BVECTOR bit_vector
1.347 +#else
1.348 +# ifdef _STLP_VECBOOL_TEMPLATE
1.349 +# define __BVECTOR_QUALIFIED vector<bool, _Alloc>
1.350 +# else
1.351 +# define __BVECTOR_QUALIFIED vector<bool, allocator<bool> >
1.352 +# endif
1.353 +# if defined (_STLP_PARTIAL_SPEC_NEEDS_TEMPLATE_ARGS)
1.354 +# define __BVECTOR __BVECTOR_QUALIFIED
1.355 +# else
1.356 +# define __BVECTOR vector
1.357 +# endif
1.358 +#endif
1.359 +
1.360 +#if !defined (_STLP_DEBUG) || defined (_STLP_NO_BOOL)
1.361 +_STLP_MOVE_TO_STD_NAMESPACE
1.362 +#endif
1.363 +
1.364 +__BVEC_TMPL_HEADER
1.365 +class __BVECTOR_QUALIFIED : public _STLP_PRIV _Bvector_base<_Alloc >
1.366 +#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_DEBUG)
1.367 + , public __stlport_class< __BVECTOR_QUALIFIED >
1.368 +#endif
1.369 +{
1.370 + typedef _STLP_PRIV _Bvector_base<_Alloc > _Base;
1.371 + typedef __BVECTOR_QUALIFIED _Self;
1.372 +public:
1.373 + typedef bool value_type;
1.374 + typedef size_t size_type;
1.375 + typedef ptrdiff_t difference_type;
1.376 + typedef _STLP_PRIV _Bit_reference reference;
1.377 + typedef bool const_reference;
1.378 + typedef _STLP_PRIV _Bit_reference* pointer;
1.379 + typedef const bool* const_pointer;
1.380 + typedef random_access_iterator_tag _Iterator_category;
1.381 +
1.382 + typedef _STLP_PRIV _Bit_iterator iterator;
1.383 + typedef _STLP_PRIV _Bit_const_iterator const_iterator;
1.384 +
1.385 + _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
1.386 +
1.387 +#ifdef _STLP_VECBOOL_TEMPLATE
1.388 + typedef typename _STLP_PRIV _Bvector_base<_Alloc >::allocator_type allocator_type;
1.389 + typedef typename _STLP_PRIV _Bvector_base<_Alloc >::__chunk_type __chunk_type;
1.390 +#else
1.391 + typedef _STLP_PRIV _Bvector_base<_Alloc >::allocator_type allocator_type;
1.392 + typedef _STLP_PRIV _Bvector_base<_Alloc >::__chunk_type __chunk_type;
1.393 +#endif
1.394 +
1.395 +protected:
1.396 +
1.397 + void _M_initialize(size_type __n) {
1.398 + unsigned int* __q = this->_M_bit_alloc(__n);
1.399 + this->_M_end_of_storage._M_data = __q + (__n + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
1.400 + this->_M_start = iterator(__q, 0);
1.401 + this->_M_finish = this->_M_start + difference_type(__n);
1.402 + }
1.403 + void _M_insert_aux(iterator __position, bool __x) {
1.404 + if (this->_M_finish._M_p != this->_M_end_of_storage._M_data) {
1.405 + _STLP_PRIV __copy_backward(__position, this->_M_finish, this->_M_finish + 1,
1.406 + random_access_iterator_tag(), (difference_type*)0 );
1.407 + *__position = __x;
1.408 + ++this->_M_finish;
1.409 + }
1.410 + else {
1.411 + size_type __len = size() ? 2 * size() : _STLP_WORD_BIT;
1.412 + unsigned int* __q = this->_M_bit_alloc(__len);
1.413 + iterator __i = copy(begin(), __position, iterator(__q, 0));
1.414 + *__i++ = __x;
1.415 + this->_M_finish = copy(__position, end(), __i);
1.416 + this->_M_deallocate();
1.417 + this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
1.418 + this->_M_start = iterator(__q, 0);
1.419 + }
1.420 + }
1.421 +
1.422 +#if defined (_STLP_MEMBER_TEMPLATES)
1.423 + template <class _InputIterator>
1.424 + void _M_initialize_range(_InputIterator __first, _InputIterator __last,
1.425 + const input_iterator_tag &) {
1.426 + this->_M_start = iterator();
1.427 + this->_M_finish = iterator();
1.428 + this->_M_end_of_storage._M_data = 0;
1.429 + for ( ; __first != __last; ++__first)
1.430 + push_back(*__first);
1.431 + }
1.432 +
1.433 + template <class _ForwardIterator>
1.434 + void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1.435 + const forward_iterator_tag &) {
1.436 + size_type __n = distance(__first, __last);
1.437 + _M_initialize(__n);
1.438 + copy(__first, __last, this->_M_start);
1.439 + }
1.440 +
1.441 + template <class _InputIterator>
1.442 + void _M_insert_range(iterator __pos,
1.443 + _InputIterator __first, _InputIterator __last,
1.444 + const input_iterator_tag &) {
1.445 + for ( ; __first != __last; ++__first) {
1.446 + __pos = insert(__pos, *__first);
1.447 + ++__pos;
1.448 + }
1.449 + }
1.450 +
1.451 + template <class _ForwardIterator>
1.452 + void _M_insert_range(iterator __position,
1.453 + _ForwardIterator __first, _ForwardIterator __last,
1.454 + const forward_iterator_tag &) {
1.455 + if (__first != __last) {
1.456 + size_type __n = distance(__first, __last);
1.457 + if (capacity() - size() >= __n) {
1.458 + _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + difference_type(__n),
1.459 + random_access_iterator_tag(), (difference_type*)0 );
1.460 + copy(__first, __last, __position);
1.461 + this->_M_finish += difference_type(__n);
1.462 + }
1.463 + else {
1.464 + size_type __len = size() + (max)(size(), __n);
1.465 + unsigned int* __q = this->_M_bit_alloc(__len);
1.466 + iterator __i = copy(begin(), __position, iterator(__q, 0));
1.467 + __i = copy(__first, __last, __i);
1.468 + this->_M_finish = copy(__position, end(), __i);
1.469 + this->_M_deallocate();
1.470 + this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
1.471 + this->_M_start = iterator(__q, 0);
1.472 + }
1.473 + }
1.474 + }
1.475 +
1.476 +#endif /* _STLP_MEMBER_TEMPLATES */
1.477 +
1.478 +public:
1.479 + iterator begin() { return this->_M_start; }
1.480 + const_iterator begin() const { return this->_M_start; }
1.481 + iterator end() { return this->_M_finish; }
1.482 + const_iterator end() const { return this->_M_finish; }
1.483 +
1.484 + reverse_iterator rbegin() { return reverse_iterator(end()); }
1.485 + const_reverse_iterator rbegin() const {
1.486 + return const_reverse_iterator(end());
1.487 + }
1.488 + reverse_iterator rend() { return reverse_iterator(begin()); }
1.489 + const_reverse_iterator rend() const {
1.490 + return const_reverse_iterator(begin());
1.491 + }
1.492 +
1.493 + size_type size() const { return size_type(end() - begin()); }
1.494 + size_type max_size() const { return size_type(-1); }
1.495 + size_type capacity() const {
1.496 + return size_type(const_iterator(this->_M_end_of_storage._M_data, 0) - begin());
1.497 + }
1.498 + bool empty() const { return begin() == end(); }
1.499 + reference operator[](size_type __n)
1.500 + { return *(begin() + difference_type(__n)); }
1.501 + const_reference operator[](size_type __n) const
1.502 + { return *(begin() + difference_type(__n)); }
1.503 +
1.504 + void _M_range_check(size_type __n) const {
1.505 + if (__n >= this->size())
1.506 + __stl_throw_range_error("vector<bool>");
1.507 + }
1.508 +
1.509 + reference at(size_type __n)
1.510 + { _M_range_check(__n); return (*this)[__n]; }
1.511 + const_reference at(size_type __n) const
1.512 + { _M_range_check(__n); return (*this)[__n]; }
1.513 +
1.514 + explicit __BVECTOR(const allocator_type& __a = allocator_type())
1.515 + : _STLP_PRIV _Bvector_base<_Alloc >(__a) {}
1.516 +
1.517 + __BVECTOR(size_type __n, bool __val,
1.518 + const allocator_type& __a = allocator_type())
1.519 + : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
1.520 + _M_initialize(__n);
1.521 + fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __val ? ~0 : 0);
1.522 + }
1.523 +
1.524 + explicit __BVECTOR(size_type __n)
1.525 + : _STLP_PRIV _Bvector_base<_Alloc >(allocator_type()) {
1.526 + _M_initialize(__n);
1.527 + fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), 0);
1.528 + }
1.529 +
1.530 + __BVECTOR(const _Self& __x)
1.531 + : _STLP_PRIV _Bvector_base<_Alloc >(__x.get_allocator()) {
1.532 + _M_initialize(__x.size());
1.533 + copy(__x.begin(), __x.end(), this->_M_start);
1.534 + }
1.535 +
1.536 +#if defined (_STLP_MEMBER_TEMPLATES)
1.537 + template <class _Integer>
1.538 + void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
1.539 + _M_initialize(__n);
1.540 + fill(this->_M_start._M_p, this->_M_end_of_storage._M_data, __x ? ~0 : 0);
1.541 + }
1.542 +
1.543 + template <class _InputIterator>
1.544 + void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1.545 + const __false_type&) {
1.546 + _M_initialize_range(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
1.547 + }
1.548 +# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
1.549 + // Check whether it's an integral type. If so, it's not an iterator.
1.550 + template <class _InputIterator>
1.551 + __BVECTOR(_InputIterator __first, _InputIterator __last)
1.552 + : _STLP_PRIV _Bvector_base<_Alloc >(allocator_type()) {
1.553 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.554 + _M_initialize_dispatch(__first, __last, _Integral());
1.555 + }
1.556 +# endif
1.557 + template <class _InputIterator>
1.558 + __BVECTOR(_InputIterator __first, _InputIterator __last,
1.559 + const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
1.560 + : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
1.561 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.562 + _M_initialize_dispatch(__first, __last, _Integral());
1.563 + }
1.564 +#else /* _STLP_MEMBER_TEMPLATES */
1.565 + __BVECTOR(const_iterator __first, const_iterator __last,
1.566 + const allocator_type& __a = allocator_type())
1.567 + : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
1.568 + size_type __n = distance(__first, __last);
1.569 + _M_initialize(__n);
1.570 + copy(__first, __last, this->_M_start);
1.571 + }
1.572 + __BVECTOR(const bool* __first, const bool* __last,
1.573 + const allocator_type& __a = allocator_type())
1.574 + : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
1.575 + size_type __n = distance(__first, __last);
1.576 + _M_initialize(__n);
1.577 + copy(__first, __last, this->_M_start);
1.578 + }
1.579 +#endif /* _STLP_MEMBER_TEMPLATES */
1.580 +
1.581 + __BVECTOR(__move_source<_Self> src)
1.582 + : _STLP_PRIV _Bvector_base<_Alloc >(__move_source<_Base>(src.get())) {}
1.583 +
1.584 + ~__BVECTOR() {}
1.585 +
1.586 + __BVECTOR_QUALIFIED& operator=(const __BVECTOR_QUALIFIED& __x) {
1.587 + if (&__x == this) return *this;
1.588 + if (__x.size() > capacity()) {
1.589 + this->_M_deallocate();
1.590 + _M_initialize(__x.size());
1.591 + }
1.592 + copy(__x.begin(), __x.end(), begin());
1.593 + this->_M_finish = begin() + difference_type(__x.size());
1.594 + return *this;
1.595 + }
1.596 +
1.597 + // assign(), a generalized assignment member function. Two
1.598 + // versions: one that takes a count, and one that takes a range.
1.599 + // The range version is a member template, so we dispatch on whether
1.600 + // or not the type is an integer.
1.601 +
1.602 + void _M_fill_assign(size_t __n, bool __x) {
1.603 + if (__n > size()) {
1.604 + fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __x ? ~0 : 0);
1.605 + insert(end(), __n - size(), __x);
1.606 + }
1.607 + else {
1.608 + erase(begin() + __n, end());
1.609 + fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __x ? ~0 : 0);
1.610 + }
1.611 + }
1.612 + void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); }
1.613 +
1.614 +#if defined (_STLP_MEMBER_TEMPLATES)
1.615 + template <class _InputIterator>
1.616 + void assign(_InputIterator __first, _InputIterator __last) {
1.617 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.618 + _M_assign_dispatch(__first, __last, _Integral());
1.619 + }
1.620 +
1.621 + template <class _Integer>
1.622 + void _M_assign_dispatch(_Integer __n, _Integer __val, const __true_type&)
1.623 + { _M_fill_assign((size_t) __n, (bool) __val); }
1.624 +
1.625 + template <class _InputIter>
1.626 + void _M_assign_dispatch(_InputIter __first, _InputIter __last, const __false_type&)
1.627 + { _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); }
1.628 +
1.629 + template <class _InputIterator>
1.630 + void _M_assign_aux(_InputIterator __first, _InputIterator __last,
1.631 + const input_iterator_tag &) {
1.632 + iterator __cur = begin();
1.633 + for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
1.634 + *__cur = *__first;
1.635 + if (__first == __last)
1.636 + erase(__cur, end());
1.637 + else
1.638 + insert(end(), __first, __last);
1.639 + }
1.640 +
1.641 + template <class _ForwardIterator>
1.642 + void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1.643 + const forward_iterator_tag &) {
1.644 + size_type __len = distance(__first, __last);
1.645 + if (__len < size())
1.646 + erase(copy(__first, __last, begin()), end());
1.647 + else {
1.648 + _ForwardIterator __mid = __first;
1.649 + advance(__mid, size());
1.650 + copy(__first, __mid, begin());
1.651 + insert(end(), __mid, __last);
1.652 + }
1.653 + }
1.654 +#endif /* _STLP_MEMBER_TEMPLATES */
1.655 +
1.656 + void reserve(size_type __n) {
1.657 + if (capacity() < __n) {
1.658 + if (max_size() < __n)
1.659 + __stl_throw_length_error("vector<bool>");
1.660 + unsigned int* __q = this->_M_bit_alloc(__n);
1.661 + _STLP_PRIV _Bit_iterator __z(__q, 0);
1.662 + this->_M_finish = copy(begin(), end(), __z);
1.663 + this->_M_deallocate();
1.664 + this->_M_start = iterator(__q, 0);
1.665 + this->_M_end_of_storage._M_data = __q + (__n + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
1.666 + }
1.667 + }
1.668 +
1.669 + reference front() { return *begin(); }
1.670 + const_reference front() const { return *begin(); }
1.671 + reference back() { return *(end() - 1); }
1.672 + const_reference back() const { return *(end() - 1); }
1.673 + void push_back(bool __x) {
1.674 + if (this->_M_finish._M_p != this->_M_end_of_storage._M_data) {
1.675 + *(this->_M_finish) = __x;
1.676 + ++this->_M_finish;
1.677 + }
1.678 + else
1.679 + _M_insert_aux(end(), __x);
1.680 + }
1.681 + void swap(__BVECTOR_QUALIFIED& __x) {
1.682 + _STLP_STD::swap(this->_M_start, __x._M_start);
1.683 + _STLP_STD::swap(this->_M_finish, __x._M_finish);
1.684 + this->_M_end_of_storage.swap(__x._M_end_of_storage);
1.685 + }
1.686 + iterator insert(iterator __position, bool __x = bool()) {
1.687 + difference_type __n = __position - begin();
1.688 + if (this->_M_finish._M_p != this->_M_end_of_storage._M_data && __position == end()) {
1.689 + *(this->_M_finish) = __x;
1.690 + ++this->_M_finish;
1.691 + }
1.692 + else
1.693 + _M_insert_aux(__position, __x);
1.694 + return begin() + __n;
1.695 + }
1.696 +
1.697 +#if defined (_STLP_MEMBER_TEMPLATES)
1.698 +
1.699 + template <class _Integer>
1.700 + void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1.701 + const __true_type&) {
1.702 + _M_fill_insert(__pos, (size_type) __n, (bool) __x);
1.703 + }
1.704 +
1.705 + template <class _InputIterator>
1.706 + void _M_insert_dispatch(iterator __pos,
1.707 + _InputIterator __first, _InputIterator __last,
1.708 + const __false_type&) {
1.709 + _M_insert_range(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
1.710 + }
1.711 +
1.712 + // Check whether it's an integral type. If so, it's not an iterator.
1.713 + template <class _InputIterator>
1.714 + void insert(iterator __position,
1.715 + _InputIterator __first, _InputIterator __last) {
1.716 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.717 + _M_insert_dispatch(__position, __first, __last, _Integral());
1.718 + }
1.719 +#else /* _STLP_MEMBER_TEMPLATES */
1.720 + void insert(iterator __position,
1.721 + const_iterator __first, const_iterator __last) {
1.722 + if (__first == __last) return;
1.723 + size_type __n = distance(__first, __last);
1.724 + if (capacity() - size() >= __n) {
1.725 + _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n,
1.726 + random_access_iterator_tag(), (difference_type*)0 );
1.727 + copy(__first, __last, __position);
1.728 + this->_M_finish += __n;
1.729 + }
1.730 + else {
1.731 + size_type __len = size() + (max)(size(), __n);
1.732 + unsigned int* __q = this->_M_bit_alloc(__len);
1.733 + iterator __i = copy(begin(), __position, iterator(__q, 0));
1.734 + __i = copy(__first, __last, __i);
1.735 + this->_M_finish = copy(__position, end(), __i);
1.736 + this->_M_deallocate();
1.737 + this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
1.738 + this->_M_start = iterator(__q, 0);
1.739 + }
1.740 + }
1.741 +
1.742 + void insert(iterator __position, const bool* __first, const bool* __last) {
1.743 + if (__first == __last) return;
1.744 + size_type __n = distance(__first, __last);
1.745 + if (capacity() - size() >= __n) {
1.746 + _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n,
1.747 + random_access_iterator_tag(), (difference_type*)0 );
1.748 + copy(__first, __last, __position);
1.749 + this->_M_finish += __n;
1.750 + }
1.751 + else {
1.752 + size_type __len = size() + (max)(size(), __n);
1.753 + unsigned int* __q = this->_M_bit_alloc(__len);
1.754 + iterator __i = copy(begin(), __position, iterator(__q, 0));
1.755 + __i = copy(__first, __last, __i);
1.756 + this->_M_finish = copy(__position, end(), __i);
1.757 + this->_M_deallocate();
1.758 + this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
1.759 + this->_M_start = iterator(__q, 0);
1.760 + }
1.761 + }
1.762 +#endif /* _STLP_MEMBER_TEMPLATES */
1.763 +
1.764 + void _M_fill_insert(iterator __position, size_type __n, bool __x) {
1.765 + if (__n == 0) return;
1.766 + if (capacity() - size() >= __n) {
1.767 + _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + difference_type(__n),
1.768 + random_access_iterator_tag(), (difference_type*)0 );
1.769 + fill(__position, __position + difference_type(__n), __x);
1.770 + this->_M_finish += difference_type(__n);
1.771 + }
1.772 + else {
1.773 + size_type __len = size() + (max)(size(), __n);
1.774 + unsigned int* __q = this->_M_bit_alloc(__len);
1.775 + iterator __i = copy(begin(), __position, iterator(__q, 0));
1.776 + fill_n(__i, __n, __x);
1.777 + this->_M_finish = copy(__position, end(), __i + difference_type(__n));
1.778 + this->_M_deallocate();
1.779 + this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
1.780 + this->_M_start = iterator(__q, 0);
1.781 + }
1.782 + }
1.783 +
1.784 + void insert(iterator __position, size_type __n, bool __x) {
1.785 + _M_fill_insert(__position, __n, __x);
1.786 + }
1.787 +
1.788 + void pop_back() {
1.789 + --this->_M_finish;
1.790 + }
1.791 + iterator erase(iterator __position) {
1.792 + if (__position + 1 != end())
1.793 + copy(__position + 1, end(), __position);
1.794 + --this->_M_finish;
1.795 + return __position;
1.796 + }
1.797 + iterator erase(iterator __first, iterator __last) {
1.798 + this->_M_finish = copy(__last, end(), __first);
1.799 + return __first;
1.800 + }
1.801 + void resize(size_type __new_size, bool __x = bool()) {
1.802 + if (__new_size < size())
1.803 + erase(begin() + difference_type(__new_size), end());
1.804 + else
1.805 + insert(end(), __new_size - size(), __x);
1.806 + }
1.807 + void flip() {
1.808 + for (unsigned int* __p = this->_M_start._M_p; __p != this->_M_end_of_storage._M_data; ++__p)
1.809 + *__p = ~*__p;
1.810 + }
1.811 +
1.812 + void clear() { erase(begin(), end()); }
1.813 +};
1.814 +
1.815 +#if defined (_STLP_NO_BOOL) || defined (__HP_aCC) // fixed soon (03/17/2000)
1.816 +# define _STLP_TEMPLATE_HEADER __BVEC_TMPL_HEADER
1.817 +# define _STLP_TEMPLATE_CONTAINER __BVECTOR_QUALIFIED
1.818 +# include <stl/_relops_cont.h>
1.819 +# undef _STLP_TEMPLATE_CONTAINER
1.820 +# undef _STLP_TEMPLATE_HEADER
1.821 +#endif /* NO_BOOL */
1.822 +
1.823 +#if defined (_STLP_DEBUG) && !defined (_STLP_NO_BOOL)
1.824 +_STLP_MOVE_TO_STD_NAMESPACE
1.825 +#endif
1.826 +
1.827 +_STLP_END_NAMESPACE
1.828 +
1.829 +#undef vector
1.830 +#undef _Alloc
1.831 +#undef _STLP_VECBOOL_TEMPLATE
1.832 +#undef __BVECTOR
1.833 +#undef __BVECTOR_QUALIFIED
1.834 +#undef __BVEC_TMPL_HEADER
1.835 +
1.836 +#undef _STLP_WORD_BIT
1.837 +
1.838 +#endif /* _STLP_INTERNAL_BVECTOR_H */
1.839 +
1.840 +// Local Variables:
1.841 +// mode:C++
1.842 +// End: