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