include/c++/stl/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 typename _Alloc_traits<bool, _Alloc>::allocator_type allocator_type;
 273   typedef unsigned int __chunk_type;
 274   typedef typename _Alloc_traits<__chunk_type,
 275           _Alloc>::allocator_type __chunk_allocator_type;
 276   allocator_type get_allocator() const {
 277     return _STLP_CONVERT_ALLOCATOR((const __chunk_allocator_type&)_M_end_of_storage, bool);
 278   }
 279   static allocator_type __get_dfl_allocator() { return allocator_type(); }
 280
 281   _Bvector_base(const allocator_type& __a)
 282     : _M_start(), _M_finish(), _M_end_of_storage(_STLP_CONVERT_ALLOCATOR(__a, __chunk_type),
 283                                                  (__chunk_type*)0)
 284   {}
 285   _Bvector_base(__move_source<_Self> src)
 286     : _M_start(src.get()._M_start), _M_finish(src.get()._M_finish),
 287       _M_end_of_storage(src.get()._M_end_of_storage) {
 288     //Make the source destroyable
 289     src.get()._M_start._M_p = 0;
 290   }
 291
 292   ~_Bvector_base() {
 293     _M_deallocate();
 294   }
 295
 296 protected:
 297
 298   unsigned int* _M_bit_alloc(size_t __n) {
 299     return _M_end_of_storage.allocate((__n + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT);
 300   }
 301   void _M_deallocate() {
 302     if (_M_start._M_p)
 303       _M_end_of_storage.deallocate(_M_start._M_p,
 304                                    _M_end_of_storage._M_data - _M_start._M_p);
 305   }
 306
 307   _Bit_iterator _M_start;
 308   _Bit_iterator _M_finish;
 309   _STLP_alloc_proxy<__chunk_type*, __chunk_type, __chunk_allocator_type> _M_end_of_storage;
 310 };
 311
 312
 313 // The next few lines are confusing.  What we're doing is declaring a
 314 //  partial specialization of vector<T, Alloc> if we have the necessary
 315 //  compiler support.  Otherwise, we define a class bit_vector which uses
 316 //  the default allocator.
 317
 318 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_BOOL) && !defined (__SUNPRO_CC)
 319 #  define _STLP_VECBOOL_TEMPLATE
 320 #  define __BVEC_TMPL_HEADER template <class _Alloc>
 321 #else
 322 #  undef _STLP_VECBOOL_TEMPLATE
 323 #  ifdef _STLP_NO_BOOL
 324 #    define __BVEC_TMPL_HEADER
 325 #  else
 326 #    define __BVEC_TMPL_HEADER _STLP_TEMPLATE_NULL
 327 #  endif
 328 #  if !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__)))      //*TY 12/17/2000 -
 329 #    define _Alloc _STLP_DEFAULT_ALLOCATOR(bool)
 330 #  else
 331 #    define _Alloc allocator<bool>
 332 #  endif
 333 #endif
 334
 335 #if defined (_STLP_DEBUG)
 336 #  define vector _STLP_NON_DBG_NAME(vector)
 337 #endif
 338
 339 #ifdef _STLP_NO_BOOL
 340 #  define __BVECTOR_QUALIFIED bit_vector
 341 #  define __BVECTOR           bit_vector
 342 #else
 343 #  ifdef _STLP_VECBOOL_TEMPLATE
 344 #    define __BVECTOR_QUALIFIED vector<bool, _Alloc>
 345 #  else
 346 #    define __BVECTOR_QUALIFIED vector<bool, allocator<bool> >
 347 #  endif
 348 #  if defined (_STLP_PARTIAL_SPEC_NEEDS_TEMPLATE_ARGS)
 349 #    define __BVECTOR __BVECTOR_QUALIFIED
 350 #  else
 351 #    define __BVECTOR vector
 352 #  endif
 353 #endif
 354
 355 #if !defined (_STLP_DEBUG) || defined (_STLP_NO_BOOL)
 356 _STLP_MOVE_TO_STD_NAMESPACE
 357 #endif
 358
 359 __BVEC_TMPL_HEADER
 360 class __BVECTOR_QUALIFIED : public _STLP_PRIV _Bvector_base<_Alloc >
 361 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_DEBUG)
 362                           , public __stlport_class< __BVECTOR_QUALIFIED >
 363 #endif
 364 {
 365   typedef _STLP_PRIV _Bvector_base<_Alloc > _Base;
 366   typedef __BVECTOR_QUALIFIED _Self;
 367 public:
 368   typedef bool value_type;
 369   typedef size_t size_type;
 370   typedef ptrdiff_t difference_type;
 371   typedef _STLP_PRIV _Bit_reference reference;
 372   typedef bool const_reference;
 373   typedef _STLP_PRIV _Bit_reference* pointer;
 374   typedef const bool* const_pointer;
 375   typedef random_access_iterator_tag _Iterator_category;
 376
 377   typedef _STLP_PRIV _Bit_iterator          iterator;
 378   typedef _STLP_PRIV _Bit_const_iterator    const_iterator;
 379
 380   _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
 381
 382 #ifdef _STLP_VECBOOL_TEMPLATE
 383   typedef typename _STLP_PRIV _Bvector_base<_Alloc >::allocator_type allocator_type;
 384   typedef typename _STLP_PRIV _Bvector_base<_Alloc >::__chunk_type __chunk_type;
 385 #else
 386   typedef _STLP_PRIV _Bvector_base<_Alloc >::allocator_type allocator_type;
 387   typedef _STLP_PRIV _Bvector_base<_Alloc >::__chunk_type __chunk_type;
 388 #endif
 389
 390 protected:
 391
 392   void _M_initialize(size_type __n) {
 393     unsigned int* __q = this->_M_bit_alloc(__n);
 394     this->_M_end_of_storage._M_data = __q + (__n + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
 395     this->_M_start = iterator(__q, 0);
 396     this->_M_finish = this->_M_start + difference_type(__n);
 397   }
 398   void _M_insert_aux(iterator __position, bool __x) {
 399     if (this->_M_finish._M_p != this->_M_end_of_storage._M_data) {
 400       _STLP_PRIV __copy_backward(__position, this->_M_finish, this->_M_finish + 1,
 401                                  random_access_iterator_tag(), (difference_type*)0 );
 402       *__position = __x;
 403       ++this->_M_finish;
 404     }
 405     else {
 406       size_type __len = size() ? 2 * size() : _STLP_WORD_BIT;
 407       unsigned int* __q = this->_M_bit_alloc(__len);
 408       iterator __i = copy(begin(), __position, iterator(__q, 0));
 409       *__i++ = __x;
 410       this->_M_finish = copy(__position, end(), __i);
 411       this->_M_deallocate();
 412       this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
 413       this->_M_start = iterator(__q, 0);
 414     }
 415   }
 416
 417 #if defined (_STLP_MEMBER_TEMPLATES)
 418   template <class _InputIterator>
 419   void _M_initialize_range(_InputIterator __first, _InputIterator __last,
 420                            const input_iterator_tag &) {
 421     this->_M_start = iterator();
 422     this->_M_finish = iterator();
 423     this->_M_end_of_storage._M_data = 0;
 424     for ( ; __first != __last; ++__first)
 425       push_back(*__first);
 426   }
 427
 428   template <class _ForwardIterator>
 429   void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
 430                            const forward_iterator_tag &) {
 431     size_type __n = distance(__first, __last);
 432     _M_initialize(__n);
 433     copy(__first, __last, this->_M_start);
 434   }
 435
 436   template <class _InputIterator>
 437   void _M_insert_range(iterator __pos,
 438                        _InputIterator __first, _InputIterator __last,
 439                        const input_iterator_tag &) {
 440     for ( ; __first != __last; ++__first) {
 441       __pos = insert(__pos, *__first);
 442       ++__pos;
 443     }
 444   }
 445
 446   template <class _ForwardIterator>
 447   void _M_insert_range(iterator __position,
 448                        _ForwardIterator __first, _ForwardIterator __last,
 449                        const forward_iterator_tag &) {
 450     if (__first != __last) {
 451       size_type __n = distance(__first, __last);
 452       if (capacity() - size() >= __n) {
 453         _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + difference_type(__n),
 454                                    random_access_iterator_tag(), (difference_type*)0 );
 455         copy(__first, __last, __position);
 456         this->_M_finish += difference_type(__n);
 457       }
 458       else {
 459         size_type __len = size() + (max)(size(), __n);
 460         unsigned int* __q = this->_M_bit_alloc(__len);
 461         iterator __i = copy(begin(), __position, iterator(__q, 0));
 462         __i = copy(__first, __last, __i);
 463         this->_M_finish = copy(__position, end(), __i);
 464         this->_M_deallocate();
 465         this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
 466         this->_M_start = iterator(__q, 0);
 467       }
 468     }
 469   }
 470
 471 #endif /* _STLP_MEMBER_TEMPLATES */
 472
 473 public:
 474   iterator begin() { return this->_M_start; }
 475   const_iterator begin() const { return this->_M_start; }
 476   iterator end() { return this->_M_finish; }
 477   const_iterator end() const { return this->_M_finish; }
 478
 479   reverse_iterator rbegin() { return reverse_iterator(end()); }
 480   const_reverse_iterator rbegin() const {
 481     return const_reverse_iterator(end());
 482   }
 483   reverse_iterator rend() { return reverse_iterator(begin()); }
 484   const_reverse_iterator rend() const {
 485     return const_reverse_iterator(begin());
 486   }
 487
 488   size_type size() const { return size_type(end() - begin()); }
 489   size_type max_size() const { return size_type(-1); }
 490   size_type capacity() const {
 491     return size_type(const_iterator(this->_M_end_of_storage._M_data, 0) - begin());
 492   }
 493   bool empty() const { return begin() == end(); }
 494   reference operator[](size_type __n)
 495   { return *(begin() + difference_type(__n)); }
 496   const_reference operator[](size_type __n) const
 497   { return *(begin() + difference_type(__n)); }
 498
 499   void _M_range_check(size_type __n) const {
 500     if (__n >= this->size())
 501       __stl_throw_range_error("vector<bool>");
 502   }
 503
 504   reference at(size_type __n)
 505     { _M_range_check(__n); return (*this)[__n]; }
 506   const_reference at(size_type __n) const
 507     { _M_range_check(__n); return (*this)[__n]; }
 508
 509   explicit __BVECTOR(const allocator_type& __a = allocator_type())
 510     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {}
 511
 512   __BVECTOR(size_type __n, bool __val,
 513             const allocator_type& __a = allocator_type())
 514     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
 515     _M_initialize(__n);
 516     fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), __val ? ~0 : 0);
 517   }
 518
 519   explicit __BVECTOR(size_type __n)
 520     : _STLP_PRIV _Bvector_base<_Alloc >(allocator_type()) {
 521     _M_initialize(__n);
 522     fill(this->_M_start._M_p, (__chunk_type*)(this->_M_end_of_storage._M_data), 0);
 523   }
 524
 525   __BVECTOR(const _Self& __x)
 526     : _STLP_PRIV _Bvector_base<_Alloc >(__x.get_allocator()) {
 527     _M_initialize(__x.size());
 528     copy(__x.begin(), __x.end(), this->_M_start);
 529   }
 530
 531 #if defined (_STLP_MEMBER_TEMPLATES)
 532   template <class _Integer>
 533   void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
 534     _M_initialize(__n);
 535     fill(this->_M_start._M_p, this->_M_end_of_storage._M_data, __x ? ~0 : 0);
 536   }
 537
 538   template <class _InputIterator>
 539   void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
 540                               const __false_type&) {
 541     _M_initialize_range(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
 542   }
 543 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
 544   // Check whether it's an integral type.  If so, it's not an iterator.
 545   template <class _InputIterator>
 546   __BVECTOR(_InputIterator __first, _InputIterator __last)
 547     : _STLP_PRIV _Bvector_base<_Alloc >(allocator_type()) {
 548     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 549     _M_initialize_dispatch(__first, __last, _Integral());
 550   }
 551 #  endif
 552   template <class _InputIterator>
 553   __BVECTOR(_InputIterator __first, _InputIterator __last,
 554             const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 555     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
 556     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 557     _M_initialize_dispatch(__first, __last, _Integral());
 558   }
 559 #else /* _STLP_MEMBER_TEMPLATES */
 560   __BVECTOR(const_iterator __first, const_iterator __last,
 561             const allocator_type& __a = allocator_type())
 562     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
 563     size_type __n = distance(__first, __last);
 564     _M_initialize(__n);
 565     copy(__first, __last, this->_M_start);
 566   }
 567   __BVECTOR(const bool* __first, const bool* __last,
 568             const allocator_type& __a = allocator_type())
 569     : _STLP_PRIV _Bvector_base<_Alloc >(__a) {
 570     size_type __n = distance(__first, __last);
 571     _M_initialize(__n);
 572     copy(__first, __last, this->_M_start);
 573   }
 574 #endif /* _STLP_MEMBER_TEMPLATES */
 575
 576   __BVECTOR(__move_source<_Self> src)
 577     : _STLP_PRIV _Bvector_base<_Alloc >(__move_source<_Base>(src.get())) {}
 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     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 = distance(__first, __last);
 640     if (__len < size())
 641       erase(copy(__first, __last, begin()), end());
 642     else {
 643       _ForwardIterator __mid = __first;
 644       advance(__mid, size());
 645       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       unsigned int* __q = this->_M_bit_alloc(__n);
 656       _STLP_PRIV _Bit_iterator __z(__q, 0);
 657       this->_M_finish = copy(begin(), end(), __z);
 658       this->_M_deallocate();
 659       this->_M_start = iterator(__q, 0);
 660       this->_M_end_of_storage._M_data = __q + (__n + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
 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   iterator insert(iterator __position, bool __x = bool()) {
 682     difference_type __n = __position - begin();
 683     if (this->_M_finish._M_p != this->_M_end_of_storage._M_data && __position == end()) {
 684       *(this->_M_finish) = __x;
 685       ++this->_M_finish;
 686     }
 687     else
 688       _M_insert_aux(__position, __x);
 689     return begin() + __n;
 690   }
 691
 692 #if defined (_STLP_MEMBER_TEMPLATES)
 693
 694   template <class _Integer>
 695   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
 696                           const __true_type&) {
 697     _M_fill_insert(__pos, (size_type) __n, (bool) __x);
 698   }
 699
 700   template <class _InputIterator>
 701   void _M_insert_dispatch(iterator __pos,
 702                           _InputIterator __first, _InputIterator __last,
 703                           const __false_type&) {
 704     _M_insert_range(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
 705   }
 706
 707   // Check whether it's an integral type.  If so, it's not an iterator.
 708   template <class _InputIterator>
 709   void insert(iterator __position,
 710               _InputIterator __first, _InputIterator __last) {
 711     typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
 712     _M_insert_dispatch(__position, __first, __last, _Integral());
 713   }
 714 #else /* _STLP_MEMBER_TEMPLATES */
 715   void insert(iterator __position,
 716               const_iterator __first, const_iterator __last) {
 717     if (__first == __last) return;
 718     size_type __n = distance(__first, __last);
 719     if (capacity() - size() >= __n) {
 720       _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n,
 721                                  random_access_iterator_tag(), (difference_type*)0 );
 722       copy(__first, __last, __position);
 723       this->_M_finish += __n;
 724     }
 725     else {
 726       size_type __len = size() + (max)(size(), __n);
 727       unsigned int* __q = this->_M_bit_alloc(__len);
 728       iterator __i = copy(begin(), __position, iterator(__q, 0));
 729       __i = copy(__first, __last, __i);
 730       this->_M_finish = copy(__position, end(), __i);
 731       this->_M_deallocate();
 732       this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
 733       this->_M_start = iterator(__q, 0);
 734     }
 735   }
 736
 737   void insert(iterator __position, const bool* __first, const bool* __last) {
 738     if (__first == __last) return;
 739     size_type __n = distance(__first, __last);
 740     if (capacity() - size() >= __n) {
 741       _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + __n,
 742                                  random_access_iterator_tag(), (difference_type*)0 );
 743       copy(__first, __last, __position);
 744       this->_M_finish += __n;
 745     }
 746     else {
 747       size_type __len = size() + (max)(size(), __n);
 748       unsigned int* __q = this->_M_bit_alloc(__len);
 749       iterator __i = copy(begin(), __position, iterator(__q, 0));
 750       __i = copy(__first, __last, __i);
 751       this->_M_finish = copy(__position, end(), __i);
 752       this->_M_deallocate();
 753       this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
 754       this->_M_start = iterator(__q, 0);
 755     }
 756   }
 757 #endif /* _STLP_MEMBER_TEMPLATES */
 758
 759   void _M_fill_insert(iterator __position, size_type __n, bool __x) {
 760     if (__n == 0) return;
 761     if (capacity() - size() >= __n) {
 762       _STLP_PRIV __copy_backward(__position, end(), this->_M_finish + difference_type(__n),
 763                                  random_access_iterator_tag(), (difference_type*)0 );
 764       fill(__position, __position + difference_type(__n), __x);
 765       this->_M_finish += difference_type(__n);
 766     }
 767     else {
 768       size_type __len = size() + (max)(size(), __n);
 769       unsigned int* __q = this->_M_bit_alloc(__len);
 770       iterator __i = copy(begin(), __position, iterator(__q, 0));
 771       fill_n(__i, __n, __x);
 772       this->_M_finish = copy(__position, end(), __i + difference_type(__n));
 773       this->_M_deallocate();
 774       this->_M_end_of_storage._M_data = __q + (__len + _STLP_WORD_BIT - 1)/_STLP_WORD_BIT;
 775       this->_M_start = iterator(__q, 0);
 776     }
 777   }
 778
 779   void insert(iterator __position, size_type __n, bool __x) {
 780     _M_fill_insert(__position, __n, __x);
 781   }
 782
 783   void pop_back() {
 784     --this->_M_finish;
 785   }
 786   iterator erase(iterator __position) {
 787     if (__position + 1 != end())
 788       copy(__position + 1, end(), __position);
 789       --this->_M_finish;
 790     return __position;
 791   }
 792   iterator erase(iterator __first, iterator __last) {
 793     this->_M_finish = copy(__last, end(), __first);
 794     return __first;
 795   }
 796   void resize(size_type __new_size, bool __x = bool()) {
 797     if (__new_size < size())
 798       erase(begin() + difference_type(__new_size), end());
 799     else
 800       insert(end(), __new_size - size(), __x);
 801   }
 802   void flip() {
 803     for (unsigned int* __p = this->_M_start._M_p; __p != this->_M_end_of_storage._M_data; ++__p)
 804       *__p = ~*__p;
 805   }
 806
 807   void clear() { erase(begin(), end()); }
 808 };
 809
 810 #if defined  (_STLP_NO_BOOL) || defined (__HP_aCC) // fixed soon (03/17/2000)
 811 #  define _STLP_TEMPLATE_HEADER __BVEC_TMPL_HEADER
 812 #  define _STLP_TEMPLATE_CONTAINER __BVECTOR_QUALIFIED
 813 #  include <stl/_relops_cont.h>
 814 #  undef _STLP_TEMPLATE_CONTAINER
 815 #  undef _STLP_TEMPLATE_HEADER
 816 #endif /* NO_BOOL */
 817
 818 #if defined (_STLP_DEBUG) && !defined (_STLP_NO_BOOL)
 819 _STLP_MOVE_TO_STD_NAMESPACE
 820 #endif
 821
 822 _STLP_END_NAMESPACE
 823
 824 #undef vector
 825 #undef _Alloc
 826 #undef _STLP_VECBOOL_TEMPLATE
 827 #undef __BVECTOR
 828 #undef __BVECTOR_QUALIFIED
 829 #undef __BVEC_TMPL_HEADER
 830
 831 #undef _STLP_WORD_BIT
 832
 833 #endif /* _STLP_INTERNAL_BVECTOR_H */
 834
 835 // Local Variables:
 836 // mode:C++
 837 // End: