lib/3rdparty/stlport/stlport/stl/_bvector.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Copyright (c) 1996,1997
   7  * Silicon Graphics Computer Systems, Inc.
   8  *
   9  * Copyright (c) 1997
  10  * Moscow Center for SPARC Technology
  11  *
  12  * Copyright (c) 1999
  13  * Boris Fomitchev
  14  *
  15  * This material is provided "as is", with absolutely no warranty expressed
  16  * or implied. Any use is at your own risk.
  17  *
  18  * Permission to use or copy this software for any purpose is hereby granted
  19  * without fee, provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  */
  25
  26 /* NOTE: This is an internal header file, included by other STL headers.
  27  *   You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _STLP_INTERNAL_BVECTOR_H
  31 #define _STLP_INTERNAL_BVECTOR_H
  32
  33 #ifndef _STLP_INTERNAL_VECTOR_H
  34 #  include <stl/_vector.h>
  35 #endif
  36
  37 #define _STLP_WORD_BIT (int(CHAR_BIT * sizeof(unsigned int)))
  38
  39 _STLP_BEGIN_NAMESPACE
  40 _STLP_MOVE_TO_PRIV_NAMESPACE
  41
  42 struct _Bit_reference {
  43   unsigned int* _M_p;
  44   unsigned int _M_mask;
  45   _Bit_reference(unsigned int* __x, unsigned int __y)
  46     : _M_p(__x), _M_mask(__y) {}
  47
  48 public:
  49   _Bit_reference() : _M_p(0), _M_mask(0) {}
  50
  51   operator bool() const {
  52     return !(!(*_M_p & _M_mask));
  53   }
  54   _Bit_reference& operator = (bool __x) {
  55     if (__x)  *_M_p |= _M_mask;
  56     else      *_M_p &= ~_M_mask;
  57     return *this;
  58   }
  59   _Bit_reference& operator = (const _Bit_reference& __x) {
  60     return *this = bool(__x);
  61   }
  62   bool operator == (const _Bit_reference& __x) const {
  63     return bool(*this) == bool(__x);
  64   }
  65   bool operator < (const _Bit_reference& __x) const {
  66     return !bool(*this) && bool(__x);
  67   }
  68
  69   _Bit_reference& operator |= (bool __x) {
  70     if (__x)
  71       *_M_p |= _M_mask;
  72     return *this;
  73   }
  74   _Bit_reference& operator &= (bool __x) {
  75     if (!__x)
  76       *_M_p &= ~_M_mask;
  77     return *this;
  78   }
  79   void flip() { *_M_p ^= _M_mask; }
  80 };
  81
  82
  83 _STLP_MOVE_TO_STD_NAMESPACE
  84
  85 inline void swap(_STLP_PRIV _Bit_reference& __x, _STLP_PRIV _Bit_reference& __y) {
  86   bool __tmp = (bool)__x;
  87   __x = __y;
  88   __y = __tmp;
  89 }
  90
  91 // Might not be very useful but costs nothing!
  92 _STLP_TEMPLATE_NULL
  93 struct __type_traits<_STLP_PRIV _Bit_reference> {
  94   typedef __false_type    has_trivial_default_constructor;
  95   typedef __true_type     has_trivial_copy_constructor;
  96   typedef __false_type    has_trivial_assignment_operator;
  97   typedef __true_type     has_trivial_destructor;
  98   typedef __false_type    is_POD_type;
  99 };
 100
 101 _STLP_MOVE_TO_PRIV_NAMESPACE
 102
 103 struct _Bit_iterator_base {
 104   typedef ptrdiff_t difference_type;
 105
 106   unsigned int* _M_p;
 107   unsigned int  _M_offset;
 108
 109   void _M_bump_up() {
 110     if (_M_offset++ == _STLP_WORD_BIT - 1) {
 111       _M_offset = 0;
 112       ++_M_p;
 113     }
 114   }
 115
 116   void _M_bump_down() {
 117     if (_M_offset-- == 0) {
 118       _M_offset = _STLP_WORD_BIT - 1;
 119       --_M_p;
 120     }
 121   }
 122
 123   _Bit_iterator_base() : _M_p(0), _M_offset(0) {}
 124   _Bit_iterator_base(unsigned int* __x, unsigned int __y) : _M_p(__x), _M_offset(__y) {}
 125 // see comment in doc/README.evc4 and doc/README.evc8
 126 #if defined(_MSC_VER) && _MSC_VER<=1401 && defined(MIPS) && defined(NDEBUG)
 127   _Bit_iterator_base( const _Bit_iterator_base& __x) : _M_p(__x._M_p), _M_offset(__x._M_offset) {}
 128 #endif
 129   //  _Bit_iterator_base& operator = ( const _Bit_iterator_base& __x) { _M_p = __x._M_p ; _M_offset = __x._M_offset ; return *this; }
 130
 131   void _M_advance (difference_type __i) {
 132     difference_type __n = __i + _M_offset;
 133     _M_p += __n / _STLP_WORD_BIT;
 134     __n = __n % _STLP_WORD_BIT;
 135     if (__n < 0) {
 136       _M_offset = (unsigned int) __n + _STLP_WORD_BIT;
 137       --_M_p;
 138     } else
 139       _M_offset = (unsigned int) __n;
 140   }
 141
 142   difference_type _M_subtract(const _Bit_iterator_base& __x) const {
 143     return _STLP_WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset;
 144   }
 145 };
 146
 147 inline bool  _STLP_CALL operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
 148   return __y._M_p == __x._M_p && __y._M_offset == __x._M_offset;
 149 }
 150 inline bool  _STLP_CALL operator!=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
 151   return __y._M_p != __x._M_p || __y._M_offset != __x._M_offset;
 152 }
 153
 154 inline bool _STLP_CALL operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
 155   return __x._M_p < __y._M_p || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset);
 156 }
 157
 158 inline bool _STLP_CALL operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)  {
 159   return operator <(__y , __x);
 160 }
 161 inline bool _STLP_CALL operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
 162   return !(__y < __x);
 163 }
 164 inline bool _STLP_CALL operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
 165   return !(__x < __y);
 166 }
 167
 168 template <class _Ref, class _Ptr>
 169 struct _Bit_iter : public _Bit_iterator_base {
 170   typedef _Ref  reference;
 171   typedef _Ptr  pointer;
 172   typedef _Bit_iter<_Ref, _Ptr> _Self;
 173   typedef random_access_iterator_tag iterator_category;
 174   typedef bool value_type;
 175   typedef ptrdiff_t difference_type;
 176   typedef size_t size_type;
 177
 178   _Bit_iter(unsigned int* __x, unsigned int __y) : _Bit_iterator_base(__x, __y) {}
 179   _Bit_iter() {}
 180
 181   _Bit_iter(const _Bit_iter<_Bit_reference, _Bit_reference*>& __x):
 182     _Bit_iterator_base((const _Bit_iterator_base&)__x) {}
 183
 184   //  _Self& operator = (const _Bit_iter<_Bit_reference, _Bit_reference*>& __x)
 185   //   { (_Bit_iterator_base&)*this = (const _Bit_iterator_base&)__x; return *this; }
 186
 187   reference operator*() const {
 188     return _Bit_reference(_M_p, 1UL << _M_offset);
 189   }
 190   _Self& operator++() {
 191     _M_bump_up();
 192     return *this;
 193   }
 194   _Self operator++(int) {
 195     _Self __tmp = *this;
 196     _M_bump_up();
 197     return __tmp;
 198   }
 199   _Self& operator--() {
 200     _M_bump_down();
 201     return *this;
 202   }
 203   _Self operator--(int) {
 204     _Self __tmp = *this;
 205     _M_bump_down();
 206     return __tmp;
 207   }
 208   _Self& operator+=(difference_type __i) {
 209     _M_advance(__i);
 210     return *this;
 211   }
 212   _Self& operator-=(difference_type __i) {
 213     *this += -__i;
 214     return *this;
 215   }
 216   _Self operator+(difference_type __i) const {
 217     _Self __tmp = *this;
 218     return __tmp += __i;
 219   }
 220   _Self operator-(difference_type __i) const {
 221     _Self __tmp = *this;
 222     return __tmp -= __i;
 223   }
 224   difference_type operator-(const _Self& __x) const {
 225     return _M_subtract(__x);
 226   }
 227   reference operator[](difference_type __i) { return *(*this + __i); }
 228 };
 229
 230 template <class _Ref, class _Ptr>
 231 inline _Bit_iter<_Ref,_Ptr>  _STLP_CALL
 232 operator+(ptrdiff_t __n, const _Bit_iter<_Ref, _Ptr>& __x) {
 233    return __x + __n;
 234 }
 235
 236 _STLP_MOVE_TO_STD_NAMESPACE
 237
 238 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 239 template <class _Ref, class _Ptr>
 240 struct __type_traits< _STLP_PRIV _Bit_iter<_Ref, _Ptr> > {
 241   typedef __false_type   has_trivial_default_constructor;
 242   typedef __true_type    has_trivial_copy_constructor;
 243   typedef __true_type    has_trivial_assignment_operator;
 244   typedef __true_type    has_trivial_destructor;
 245   typedef __false_type   is_POD_type;
 246 };
 247 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 248
 249 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
 250 inline random_access_iterator_tag iterator_category(const _STLP_PRIV _Bit_iterator_base&)
 251 { return random_access_iterator_tag(); }
 252 inline ptrdiff_t* distance_type(const _STLP_PRIV _Bit_iterator_base&)
 253 { return (ptrdiff_t*)0; }
 254 inline bool* value_type(const _STLP_PRIV _Bit_iter<_STLP_PRIV _Bit_reference, _STLP_PRIV _Bit_reference*>&)
 255 { return (bool*)0; }
 256 inline bool* value_type(const _STLP_PRIV _Bit_iter<bool, const bool*>&)
 257 { return (bool*)0; }
 258 #endif
 259
 260 _STLP_MOVE_TO_PRIV_NAMESPACE
 261
 262 typedef _Bit_iter<bool, const bool*> _Bit_const_iterator;
 263 typedef _Bit_iter<_Bit_reference, _Bit_reference*> _Bit_iterator;
 264
 265 // Bit-vector base class, which encapsulates the difference between
 266 //  old SGI-style allocators and standard-conforming allocators.
 267 template <class _Alloc>
 268 class _Bvector_base {
 269   typedef _Bvector_base<_Alloc> _Self;
 270 public:
 271   _STLP_FORCE_ALLOCATORS(bool, _Alloc)
 272   typedef _Alloc allocator_type;
 273   typedef unsigned int __chunk_type;
 274   typedef typename _Alloc_traits<__chunk_type, _Alloc>::allocator_type __chunk_allocator_type;
 275   allocator_type get_allocator() const
 276   { return _STLP_CONVERT_ALLOCATOR(__STATIC_CAST(const __chunk_allocator_type&, _M_end_of_storage), bool); }
 277
 278   _Bvector_base(const allocator_type& __a)
 279     : _M_start(), _M_finish(), _M_end_of_storage(_STLP_CONVERT_ALLOCATOR(__a, __chunk_type),
 280                                                  (__chunk_type*)0)
 281   {}
 282 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 283   _Bvector_base(__move_source<_Self> src)
 284     : _M_start(src.get()._M_start), _M_finish(src.get()._M_finish),
 285       _M_end_of_storage(src.get()._M_end_of_storage) {
 286     //Make the source destroyable
 287     src.get()._M_start._M_p = 0;
 288   }
 289 #endif
 290
 291   ~_Bvector_base() {
 292     _M_deallocate();
 293   }
 294
 295 protected:
 296
 297   static size_t _M_bits_to_chunks(size_t __n_bits)
 298   { return (__n_bits + _STLP_WORD_BIT - 1) / _STLP_WORD_BIT; }
 299
 300   __chunk_type* _M_bit_alloc(size_t __n)
 301   { return _M_end_of_storage.allocate(_M_bits_to_chunks(__n)); }
 302
 303   void _M_deallocate() {
 304     if (_M_start._M_p)
 305       _M_end_of_storage.deallocate(_M_start._M_p,
 306                                    _M_end_of_storage._M_data - _M_start._M_p);
 307   }
 308
 309   _Bit_iterator _M_start;
 310   _Bit_iterator _M_finish;
 311   _STLP_alloc_proxy<__chunk_type*, __chunk_type, __chunk_allocator_type> _M_end_of_storage;
 312 };
 313
 314
 315 // The next few lines are confusing.  What we're doing is declaring a
 316 //  partial specialization of vector<T, Alloc> if we have the necessary
 317 //  compiler support.  Otherwise, we define a class bit_vector which uses
 318 //  the default allocator.
 319
 320 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_BOOL) && !defined (__SUNPRO_CC)
 321 #  define _STLP_VECBOOL_TEMPLATE
 322 #  define __BVEC_TMPL_HEADER template <class _Alloc>
 323 #else
 324 #  undef _STLP_VECBOOL_TEMPLATE
 325 #  ifdef _STLP_NO_BOOL
 326 #    define __BVEC_TMPL_HEADER
 327 #  else
 328 #    define __BVEC_TMPL_HEADER _STLP_TEMPLATE_NULL
 329 #  endif
 330 #  define _Alloc allocator<bool>
 331 #endif
 332
 333 #if defined (_STLP_DEBUG)
 334 #  define vector _STLP_NON_DBG_NAME(vector)
 335 #endif
 336
 337 #ifdef _STLP_NO_BOOL
 338 #  define __BVECTOR_QUALIFIED bit_vector
 339 #  define __BVECTOR           bit_vector
 340 #else
 341 #  ifdef _STLP_VECBOOL_TEMPLATE
 342 #    define __BVECTOR_QUALIFIED vector<bool, _Alloc>
 343 #  else
 344 #    define __BVECTOR_QUALIFIED vector<bool, allocator<bool> >
 345 #  endif
 346 #  if defined (_STLP_PARTIAL_SPEC_NEEDS_TEMPLATE_ARGS)
 347 #    define __BVECTOR __BVECTOR_QUALIFIED
 348 #  else
 349 #    define __BVECTOR vector
 350 #  endif
 351 #endif
 352
 353 #if !defined (_STLP_DEBUG) || defined (_STLP_NO_BOOL)
 354 _STLP_MOVE_TO_STD_NAMESPACE
 355 #endif
 356
 357 __BVEC_TMPL_HEADER
 358 class __BVECTOR_QUALIFIED : public _STLP_PRIV _Bvector_base<_Alloc >
 359 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_DEBUG)
 360                           , public __stlport_class< __BVECTOR_QUALIFIED >
 361 #endif
 362 {
 363   typedef _STLP_PRIV _Bvector_base<_Alloc > _Base;
 364   typedef __BVECTOR_QUALIFIED _Self;
 365 public:
 366   typedef bool value_type;
 367   typedef size_t size_type;
 368   typedef ptrdiff_t difference_type;
 369   typedef _STLP_PRIV _Bit_reference reference;
 370   typedef bool const_reference;
 371   typedef _STLP_PRIV _Bit_reference* pointer;
 372   typedef const bool* const_pointer;
 373   typedef random_access_iterator_tag _Iterator_category;
 374
 375   typedef _STLP_PRIV _Bit_iterator          iterator;
 376   typedef _STLP_PRIV _Bit_const_iterator    const_iterator;
 377
 378   _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
 379
 380 #ifdef _STLP_VECBOOL_TEMPLATE
 381   typedef _STLP_TYPENAME _STLP_PRIV _Bvector_base<_Alloc >::allocator_type allocator_type;
 382   typedef _STLP_TYPENAME _STLP_PRIV _Bvector_base<_Alloc >::__chunk_type __chunk_type;
 383 #else
 384   typedef _STLP_PRIV _Bvector_base<_Alloc >::allocator_type allocator_type;
 385   typedef _STLP_PRIV _Bvector_base<_Alloc >::__chunk_type __chunk_type;
 386 #endif
 387
 388 protected:
 389
 390   void _M_initialize(size_type __n) {
 391     __chunk_type* __q = this->_M_bit_alloc(__n);
 392     this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__n);
 393     this->_M_start = iterator(__q, 0);
 394     this->_M_finish = this->_M_start + difference_type(__n);
 395   }
 396   void _M_insert_aux(iterator __position, bool __x) {
 397     if (this->_M_finish._M_p != this->_M_end_of_storage._M_data) {
 398       _STLP_PRIV __copy_backward(__position, this->_M_finish, this->_M_finish + 1,
 399                                  random_access_iterator_tag(), (difference_type*)0 );
 400       *__position = __x;
 401       ++this->_M_finish;
 402     }
 403     else {
 404       size_type __len = size() ? 2 * size() : _STLP_WORD_BIT;
 405       __chunk_type* __q = this->_M_bit_alloc(__len);
 406       iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
 407       *__i++ = __x;
 408       this->_M_finish = _STLP_STD::copy(__position, end(), __i);
 409       this->_M_deallocate();
 410       this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
 411       this->_M_start = iterator(__q, 0);
 412     }
 413   }
 414
 415 #if defined (_STLP_MEMBER_TEMPLATES)
 416   template <class _InputIterator>
 417   void _M_initialize_range(_InputIterator __first, _InputIterator __last,
 418                            const input_iterator_tag &) {
 419     this->_M_start = iterator();
 420     this->_M_finish = iterator();
 421     this->_M_end_of_storage._M_data = 0;
 422     for ( ; __first != __last; ++__first)
 423       push_back(*__first);
 424   }
 425
 426   template <class _ForwardIterator>
 427   void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
 428                            const forward_iterator_tag &) {
 429     size_type __n = _STLP_STD::distance(__first, __last);
 430     _M_initialize(__n);
 431     _STLP_STD::copy(__first, __last, this->_M_start);
 432   }
 433
 434   template <class _InputIterator>
 435   void _M_insert_range(iterator __pos,
 436                        _InputIterator __first, _InputIterator __last,
 437                        const input_iterator_tag &) {
 438     for ( ; __first != __last; ++__first) {
 439       __pos = insert(__pos, *__first);
 440       ++__pos;
 441     }
 442   }
 443
 444   template <class _ForwardIterator>
 445   void _M_insert_range(iterator __position,
 446                        _ForwardIterator __first, _ForwardIterator __last,
 447                        const forward_iterator_tag &) {
 448     if (__first != __last) {
 449       size_type __n = _STLP_STD::distance(__first, __last);
 450       if (capacity() - size() >= __n) {
 451         _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + difference_type(__n),
 452                                    random_access_iterator_tag(), (difference_type*)0 );
 453         _STLP_STD::copy(__first, __last, __position);
 454         this->_M_finish += difference_type(__n);
 455       }
 456       else {
 457         size_type __len = size() + (max)(size(), __n);
 458         __chunk_type* __q = this->_M_bit_alloc(__len);
 459         iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
 460         __i = _STLP_STD::copy(__first, __last, __i);
 461         this->_M_finish = _STLP_STD::copy(__position, end(), __i);
 462         this->_M_deallocate();
 463         this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
 464         this->_M_start = iterator(__q, 0);
 465       }
 466     }
 467   }
 468
 469 #endif /* _STLP_MEMBER_TEMPLATES */
 470
 471 public:
 472   iterator begin() { return this->_M_start; }
 473   const_iterator begin() const { return this->_M_start; }
 474   iterator end() { return this->_M_finish; }
 475   const_iterator end() const { return this->_M_finish; }
 476
 477   reverse_iterator rbegin() { return reverse_iterator(end()); }
 478   const_reverse_iterator rbegin() const {
 479     return const_reverse_iterator(end());
 480   }
 481   reverse_iterator rend() { return reverse_iterator(begin()); }
 482   const_reverse_iterator rend() const {
 483     return const_reverse_iterator(begin());
 484   }
 485
 486   size_type size() const { return size_type(end() - begin()); }
 487   size_type max_size() const { return size_type(-1); }
 488   size_type capacity() const {
 489     return size_type(const_iterator(this->_M_end_of_storage._M_data, 0) - begin());
 490   }
 491   bool empty() const { return begin() == end(); }
 492   reference operator[](size_type __n)
 493   { return *(begin() + difference_type(__n)); }
 494   const_reference operator[](size_type __n) const
 495   { return *(begin() + difference_type(__n)); }
 496
 497   void _M_range_check(size_type __n) const {
 498     if (__n >= this->size())
 499       __stl_throw_range_error("vector<bool>");
 500   }
 501
 502   reference at(size_type __n)
 503     { _M_range_check(__n); return (*this)[__n]; }
 504   const_reference at(size_type __n) const
 505     { _M_range_check(__n); return (*this)[__n]; }
 506
 507   explicit __BVECTOR(const allocator_type& __a = allocator_type())
 508     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {}
 509
 510   __BVECTOR(size_type __n, bool __val,
 511             const allocator_type& __a = allocator_type())
 512     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
 513     _M_initialize(__n);
 514     fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __val ? ~0 : 0);
 515   }
 516
 517   explicit __BVECTOR(size_type __n)
 518     : _STLP_PRIV _Bvector_base<_Alloc >(allocator_type()) {
 519     _M_initialize(__n);
 520     fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), 0);
 521   }
 522
 523   __BVECTOR(const _Self& __x)
 524     : _STLP_PRIV _Bvector_base<_Alloc >(__x.get_allocator()) {
 525     _M_initialize(__x.size());
 526     _STLP_STD::copy(__x.begin(), __x.end(), this->_M_start);
 527   }
 528
 529 #if defined (_STLP_MEMBER_TEMPLATES)
 530   template <class _Integer>
 531   void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
 532     _M_initialize(__n);
 533     fill(this->_M_start._M_p, this->_M_end_of_storage._M_data, __x ? ~0 : 0);
 534   }
 535
 536   template <class _InputIterator>
 537   void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
 538                               const __false_type&) {
 539     _M_initialize_range(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
 540   }
 541 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
 542   // Check whether it's an integral type.  If so, it's not an iterator.
 543   template <class _InputIterator>
 544   __BVECTOR(_InputIterator __first, _InputIterator __last)
 545     : _STLP_PRIV _Bvector_base<_Alloc >(allocator_type()) {
 546     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 547     _M_initialize_dispatch(__first, __last, _Integral());
 548   }
 549 #  endif
 550   template <class _InputIterator>
 551   __BVECTOR(_InputIterator __first, _InputIterator __last,
 552             const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 553     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
 554     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 555     _M_initialize_dispatch(__first, __last, _Integral());
 556   }
 557 #else /* _STLP_MEMBER_TEMPLATES */
 558   __BVECTOR(const_iterator __first, const_iterator __last,
 559             const allocator_type& __a = allocator_type())
 560     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
 561     size_type __n = _STLP_STD::distance(__first, __last);
 562     _M_initialize(__n);
 563     _STLP_STD::copy(__first, __last, this->_M_start);
 564   }
 565   __BVECTOR(const bool* __first, const bool* __last,
 566             const allocator_type& __a = allocator_type())
 567     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
 568     size_type __n = _STLP_STD::distance(__first, __last);
 569     _M_initialize(__n);
 570     _STLP_STD::copy(__first, __last, this->_M_start);
 571   }
 572 #endif /* _STLP_MEMBER_TEMPLATES */
 573
 574 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 575   __BVECTOR(__move_source<_Self> src)
 576     : _STLP_PRIV _Bvector_base<_Alloc >(__move_source<_Base>(src.get())) {}
 577 #endif
 578
 579   ~__BVECTOR() {}
 580
 581   __BVECTOR_QUALIFIED& operator=(const __BVECTOR_QUALIFIED& __x) {
 582     if (&__x == this) return *this;
 583     if (__x.size() > capacity()) {
 584       this->_M_deallocate();
 585       _M_initialize(__x.size());
 586     }
 587     _STLP_STD::copy(__x.begin(), __x.end(), begin());
 588     this->_M_finish = begin() + difference_type(__x.size());
 589     return *this;
 590   }
 591
 592   // assign(), a generalized assignment member function.  Two
 593   // versions: one that takes a count, and one that takes a range.
 594   // The range version is a member template, so we dispatch on whether
 595   // or not the type is an integer.
 596
 597   void _M_fill_assign(size_t __n, bool __x) {
 598     if (__n > size()) {
 599       fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __x ? ~0 : 0);
 600       insert(end(), __n - size(), __x);
 601     }
 602     else {
 603       erase(begin() + __n, end());
 604       fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __x ? ~0 : 0);
 605     }
 606   }
 607   void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); }
 608
 609 #if defined (_STLP_MEMBER_TEMPLATES)
 610   template <class _InputIterator>
 611   void assign(_InputIterator __first, _InputIterator __last) {
 612     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 613     _M_assign_dispatch(__first, __last, _Integral());
 614   }
 615
 616   template <class _Integer>
 617   void _M_assign_dispatch(_Integer __n, _Integer __val, const __true_type&)
 618     { _M_fill_assign((size_t) __n, (bool) __val); }
 619
 620   template <class _InputIter>
 621   void _M_assign_dispatch(_InputIter __first, _InputIter __last, const __false_type&)
 622     { _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); }
 623
 624   template <class _InputIterator>
 625   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
 626                      const input_iterator_tag &) {
 627     iterator __cur = begin();
 628     for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
 629       *__cur = *__first;
 630     if (__first == __last)
 631       erase(__cur, end());
 632     else
 633       insert(end(), __first, __last);
 634   }
 635
 636   template <class _ForwardIterator>
 637   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 638                      const forward_iterator_tag &) {
 639     size_type __len = _STLP_STD::distance(__first, __last);
 640     if (__len < size())
 641       erase(_STLP_STD::copy(__first, __last, begin()), end());
 642     else {
 643       _ForwardIterator __mid = __first;
 644       _STLP_STD::advance(__mid, size());
 645       _STLP_STD::copy(__first, __mid, begin());
 646       insert(end(), __mid, __last);
 647     }
 648   }
 649 #endif /* _STLP_MEMBER_TEMPLATES */
 650
 651   void reserve(size_type __n) {
 652     if (capacity() < __n) {
 653       if (max_size() < __n)
 654         __stl_throw_length_error("vector<bool>");
 655       __chunk_type* __q = this->_M_bit_alloc(__n);
 656       _STLP_PRIV _Bit_iterator __z(__q, 0);
 657       this->_M_finish = _STLP_STD::copy(begin(), end(), __z);
 658       this->_M_deallocate();
 659       this->_M_start = iterator(__q, 0);
 660       this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__n);
 661     }
 662   }
 663
 664   reference front() { return *begin(); }
 665   const_reference front() const { return *begin(); }
 666   reference back() { return *(end() - 1); }
 667   const_reference back() const { return *(end() - 1); }
 668   void push_back(bool __x) {
 669     if (this->_M_finish._M_p != this->_M_end_of_storage._M_data) {
 670       *(this->_M_finish) = __x;
 671       ++this->_M_finish;
 672     }
 673     else
 674       _M_insert_aux(end(), __x);
 675   }
 676   void swap(__BVECTOR_QUALIFIED& __x) {
 677     _STLP_STD::swap(this->_M_start, __x._M_start);
 678     _STLP_STD::swap(this->_M_finish, __x._M_finish);
 679     this->_M_end_of_storage.swap(__x._M_end_of_storage);
 680   }
 681 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
 682   void _M_swap_workaround(__BVECTOR_QUALIFIED& __x) { swap(__x); }
 683 #endif
 684
 685   iterator insert(iterator __position, bool __x = bool()) {
 686     difference_type __n = __position - begin();
 687     if (this->_M_finish._M_p != this->_M_end_of_storage._M_data && __position == end()) {
 688       *(this->_M_finish) = __x;
 689       ++this->_M_finish;
 690     }
 691     else
 692       _M_insert_aux(__position, __x);
 693     return begin() + __n;
 694   }
 695
 696 #if defined (_STLP_MEMBER_TEMPLATES)
 697
 698   template <class _Integer>
 699   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
 700                           const __true_type&) {
 701     _M_fill_insert(__pos, (size_type) __n, (bool) __x);
 702   }
 703
 704   template <class _InputIterator>
 705   void _M_insert_dispatch(iterator __pos,
 706                           _InputIterator __first, _InputIterator __last,
 707                           const __false_type&) {
 708     _M_insert_range(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
 709   }
 710
 711   // Check whether it's an integral type.  If so, it's not an iterator.
 712   template <class _InputIterator>
 713   void insert(iterator __position,
 714               _InputIterator __first, _InputIterator __last) {
 715     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 716     _M_insert_dispatch(__position, __first, __last, _Integral());
 717   }
 718 #else /* _STLP_MEMBER_TEMPLATES */
 719   void insert(iterator __position,
 720               const_iterator __first, const_iterator __last) {
 721     if (__first == __last) return;
 722     size_type __n = _STLP_STD::distance(__first, __last);
 723     if (capacity() - size() >= __n) {
 724       _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n,
 725                                  random_access_iterator_tag(), (difference_type*)0 );
 726       _STLP_STD::copy(__first, __last, __position);
 727       this->_M_finish += __n;
 728     }
 729     else {
 730       size_type __len = size() + (max)(size(), __n);
 731       __chunk_type* __q = this->_M_bit_alloc(__len);
 732       iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
 733       __i = _STLP_STD::copy(__first, __last, __i);
 734       this->_M_finish = _STLP_STD::copy(__position, end(), __i);
 735       this->_M_deallocate();
 736       this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
 737       this->_M_start = iterator(__q, 0);
 738     }
 739   }
 740
 741   void insert(iterator __position, const bool* __first, const bool* __last) {
 742     if (__first == __last) return;
 743     size_type __n = _STLP_STD::distance(__first, __last);
 744     if (capacity() - size() >= __n) {
 745       _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n,
 746                                  random_access_iterator_tag(), (difference_type*)0 );
 747       _STLP_STD::copy(__first, __last, __position);
 748       this->_M_finish += __n;
 749     }
 750     else {
 751       size_type __len = size() + (max)(size(), __n);
 752       __chunk_type* __q = this->_M_bit_alloc(__len);
 753       iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
 754       __i = _STLP_STD::copy(__first, __last, __i);
 755       this->_M_finish = _STLP_STD::copy(__position, end(), __i);
 756       this->_M_deallocate();
 757       this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
 758       this->_M_start = iterator(__q, 0);
 759     }
 760   }
 761 #endif /* _STLP_MEMBER_TEMPLATES */
 762
 763   void _M_fill_insert(iterator __position, size_type __n, bool __x) {
 764     if (__n == 0) return;
 765     if (capacity() - size() >= __n) {
 766       _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + difference_type(__n),
 767                                  random_access_iterator_tag(), (difference_type*)0 );
 768       fill(__position, __position + difference_type(__n), __x);
 769       this->_M_finish += difference_type(__n);
 770     }
 771     else {
 772       size_type __len = size() + (max)(size(), __n);
 773       __chunk_type* __q = this->_M_bit_alloc(__len);
 774       iterator __i = _STLP_STD::copy(begin(), __position, iterator(__q, 0));
 775       fill_n(__i, __n, __x);
 776       this->_M_finish = _STLP_STD::copy(__position, end(), __i + difference_type(__n));
 777       this->_M_deallocate();
 778       this->_M_end_of_storage._M_data = __q + _Base::_M_bits_to_chunks(__len);
 779       this->_M_start = iterator(__q, 0);
 780     }
 781   }
 782
 783   void insert(iterator __position, size_type __n, bool __x) {
 784     _M_fill_insert(__position, __n, __x);
 785   }
 786
 787   void pop_back() {
 788     --this->_M_finish;
 789   }
 790   iterator erase(iterator __position) {
 791     if (__position + 1 != end())
 792       _STLP_STD::copy(__position + 1, end(), __position);
 793       --this->_M_finish;
 794     return __position;
 795   }
 796   iterator erase(iterator __first, iterator __last) {
 797     this->_M_finish = _STLP_STD::copy(__last, end(), __first);
 798     return __first;
 799   }
 800   void resize(size_type __new_size, bool __x = bool()) {
 801     if (__new_size < size())
 802       erase(begin() + difference_type(__new_size), end());
 803     else
 804       insert(end(), __new_size - size(), __x);
 805   }
 806   void flip() {
 807     for (__chunk_type* __p = this->_M_start._M_p; __p != this->_M_end_of_storage._M_data; ++__p)
 808       *__p = ~*__p;
 809   }
 810
 811   void clear() { erase(begin(), end()); }
 812 };
 813
 814 #if defined  (_STLP_NO_BOOL) || defined (__HP_aCC) // fixed soon (03/17/2000)
 815 #  define _STLP_TEMPLATE_HEADER __BVEC_TMPL_HEADER
 816 #  define _STLP_TEMPLATE_CONTAINER __BVECTOR_QUALIFIED
 817 #  include <stl/_relops_cont.h>
 818 #  undef _STLP_TEMPLATE_CONTAINER
 819 #  undef _STLP_TEMPLATE_HEADER
 820 #endif /* NO_BOOL */
 821
 822 #if defined (_STLP_DEBUG) && !defined (_STLP_NO_BOOL)
 823 _STLP_MOVE_TO_STD_NAMESPACE
 824 #endif
 825
 826 _STLP_END_NAMESPACE
 827
 828 #undef vector
 829 #undef _Alloc
 830 #undef _STLP_VECBOOL_TEMPLATE
 831 #undef __BVECTOR
 832 #undef __BVECTOR_QUALIFIED
 833 #undef __BVEC_TMPL_HEADER
 834
 835 #undef _STLP_WORD_BIT
 836
 837 #endif /* _STLP_INTERNAL_BVECTOR_H */
 838
 839 // Local Variables:
 840 // mode:C++
 841 // End: