- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_bvector.h

    00001 /*
    00002  *
    00003  * Copyright (c) 1994
    00004  * Hewlett-Packard Company
    00005  *
    00006  * Permission to use, copy, modify, distribute and sell this software
    00007  * and its documentation for any purpose is hereby granted without fee,
    00008  * provided that the above copyright notice appear in all copies and
    00009  * that both that copyright notice and this permission notice appear
    00010  * in supporting documentation.  Hewlett-Packard Company makes no
    00011  * representations about the suitability of this software for any
    00012  * purpose.  It is provided "as is" without express or implied warranty.
    00013  *
    00014  *
    00015  * Copyright (c) 1996,1997
    00016  * Silicon Graphics Computer Systems, Inc.
    00017  *
    00018  * Permission to use, copy, modify, distribute and sell this software
    00019  * and its documentation for any purpose is hereby granted without fee,
    00020  * provided that the above copyright notice appear in all copies and
    00021  * that both that copyright notice and this permission notice appear
    00022  * in supporting documentation.  Silicon Graphics makes no
    00023  * representations about the suitability of this software for any
    00024  * purpose.  It is provided "as is" without express or implied warranty.
    00025  */
    00026
    00027 /* NOTE: This is an internal header file, included by other STL headers.
    00028  *   You should not attempt to use it directly.
    00029  */
    00030
    00031 #ifndef __SGI_STL_INTERNAL_BVECTOR_H
    00032 #define __SGI_STL_INTERNAL_BVECTOR_H
    00033
    00034 __STL_BEGIN_NAMESPACE
    00035
    00036 static const int __WORD_BIT = int(CHAR_BIT*sizeof(unsigned int));
    00037
    00038 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00039 #pragma set woff 1174
    00040 #pragma set woff 1375
    00041 #endif
    00042
    00043 struct _Bit_reference {
    00044   unsigned int* _M_p;
    00045   unsigned int _M_mask;
    00046   _Bit_reference(unsigned int* __x, unsigned int __y)
    00047     : _M_p(__x), _M_mask(__y) {}
    00048
    00049 public:
    00050   _Bit_reference() : _M_p(0), _M_mask(0) {}
    00051   operator bool() const { return !(!(*_M_p & _M_mask)); }
    00052   _Bit_reference& operator=(bool __x)
    00053   {
    00054     if (__x)  *_M_p |= _M_mask;
    00055     else      *_M_p &= ~_M_mask;
    00056     return *this;
    00057   }
    00058   _Bit_reference& operator=(const _Bit_reference& __x)
    00059     { return *this = bool(__x); }
    00060   bool operator==(const _Bit_reference& __x) const
    00061     { return bool(*this) == bool(__x); }
    00062   bool operator<(const _Bit_reference& __x) const {
    00063     return !bool(*this) && bool(__x);
    00064   }
    00065   void flip() { *_M_p ^= _M_mask; }
    00066 };
    00067
    00068 inline void swap(_Bit_reference __x, _Bit_reference __y)
    00069 {
    00070   bool __tmp = __x;
    00071   __x = __y;
    00072   __y = __tmp;
    00073 }
    00074
    00075 struct _Bit_iterator : public random_access_iterator<bool, ptrdiff_t> {
    00076   typedef _Bit_reference  reference;
    00077   typedef _Bit_reference* pointer;
    00078   typedef _Bit_iterator   iterator;
    00079
    00080   unsigned int* _M_p;
    00081   unsigned int _M_offset;
    00082   void bump_up() {
    00083     if (_M_offset++ == __WORD_BIT - 1) {
    00084       _M_offset = 0;
    00085       ++_M_p;
    00086     }
    00087   }
    00088   void bump_down() {
    00089     if (_M_offset-- == 0) {
    00090       _M_offset = __WORD_BIT - 1;
    00091       --_M_p;
    00092     }
    00093   }
    00094
    00095   _Bit_iterator() : _M_p(0), _M_offset(0) {}
    00096   _Bit_iterator(unsigned int* __x, unsigned int __y)
    00097     : _M_p(__x), _M_offset(__y) {}
    00098   reference operator*() const { return reference(_M_p, 1U << _M_offset); }
    00099   iterator& operator++() {
    00100     bump_up();
    00101     return *this;
    00102   }
    00103   iterator operator++(int) {
    00104     iterator __tmp = *this;
    00105     bump_up();
    00106     return __tmp;
    00107   }
    00108   iterator& operator--() {
    00109     bump_down();
    00110     return *this;
    00111   }
    00112   iterator operator--(int) {
    00113     iterator __tmp = *this;
    00114     bump_down();
    00115     return __tmp;
    00116   }
    00117   iterator& operator+=(difference_type __i) {
    00118     difference_type __n = __i + _M_offset;
    00119     _M_p += __n / __WORD_BIT;
    00120     __n = __n % __WORD_BIT;
    00121     if (__n < 0) {
    00122       _M_offset = (unsigned int) __n + __WORD_BIT;
    00123       --_M_p;
    00124     } else
    00125       _M_offset = (unsigned int) __n;
    00126     return *this;
    00127   }
    00128   iterator& operator-=(difference_type __i) {
    00129     *this += -__i;
    00130     return *this;
    00131   }
    00132   iterator operator+(difference_type __i) const {
    00133     iterator __tmp = *this;
    00134     return __tmp += __i;
    00135   }
    00136   iterator operator-(difference_type __i) const {
    00137     iterator __tmp = *this;
    00138     return __tmp -= __i;
    00139   }
    00140   difference_type operator-(iterator __x) const {
    00141     return __WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset;
    00142   }
    00143   reference operator[](difference_type __i) { return *(*this + __i); }
    00144   bool operator==(const iterator& __x) const {
    00145     return _M_p == __x._M_p && _M_offset == __x._M_offset;
    00146   }
    00147   bool operator!=(const iterator& __x) const {
    00148     return _M_p != __x._M_p || _M_offset != __x._M_offset;
    00149   }
    00150   bool operator<(iterator __x) const {
    00151     return _M_p < __x._M_p || (_M_p == __x._M_p && _M_offset < __x._M_offset);
    00152   }
    00153 };
    00154
    00155 struct _Bit_const_iterator
    00156   : public random_access_iterator<bool, ptrdiff_t>
    00157 {
    00158   typedef bool                 reference;
    00159   typedef bool                 const_reference;
    00160   typedef const bool*          pointer;
    00161   typedef _Bit_const_iterator  const_iterator;
    00162
    00163   unsigned int* _M_p;
    00164   unsigned int _M_offset;
    00165   void bump_up() {
    00166     if (_M_offset++ == __WORD_BIT - 1) {
    00167       _M_offset = 0;
    00168       ++_M_p;
    00169     }
    00170   }
    00171   void bump_down() {
    00172     if (_M_offset-- == 0) {
    00173       _M_offset = __WORD_BIT - 1;
    00174       --_M_p;
    00175     }
    00176   }
    00177
    00178   _Bit_const_iterator() : _M_p(0), _M_offset(0) {}
    00179   _Bit_const_iterator(unsigned int* __x, unsigned int __y)
    00180     : _M_p(__x), _M_offset(__y) {}
    00181   _Bit_const_iterator(const _Bit_iterator& __x)
    00182     : _M_p(__x._M_p), _M_offset(__x._M_offset) {}
    00183   const_reference operator*() const {
    00184     return _Bit_reference(_M_p, 1U << _M_offset);
    00185   }
    00186   const_iterator& operator++() {
    00187     bump_up();
    00188     return *this;
    00189   }
    00190   const_iterator operator++(int) {
    00191     const_iterator __tmp = *this;
    00192     bump_up();
    00193     return __tmp;
    00194   }
    00195   const_iterator& operator--() {
    00196     bump_down();
    00197     return *this;
    00198   }
    00199   const_iterator operator--(int) {
    00200     const_iterator __tmp = *this;
    00201     bump_down();
    00202     return __tmp;
    00203   }
    00204   const_iterator& operator+=(difference_type __i) {
    00205     difference_type __n = __i + _M_offset;
    00206     _M_p += __n / __WORD_BIT;
    00207     __n = __n % __WORD_BIT;
    00208     if (__n < 0) {
    00209       _M_offset = (unsigned int) __n + __WORD_BIT;
    00210       --_M_p;
    00211     } else
    00212       _M_offset = (unsigned int) __n;
    00213     return *this;
    00214   }
    00215   const_iterator& operator-=(difference_type __i) {
    00216     *this += -__i;
    00217     return *this;
    00218   }
    00219   const_iterator operator+(difference_type __i) const {
    00220     const_iterator __tmp = *this;
    00221     return __tmp += __i;
    00222   }
    00223   const_iterator operator-(difference_type __i) const {
    00224     const_iterator __tmp = *this;
    00225     return __tmp -= __i;
    00226   }
    00227   difference_type operator-(const_iterator __x) const {
    00228     return __WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset;
    00229   }
    00230   const_reference operator[](difference_type __i) {
    00231     return *(*this + __i);
    00232   }
    00233   bool operator==(const const_iterator& __x) const {
    00234     return _M_p == __x._M_p && _M_offset == __x._M_offset;
    00235   }
    00236   bool operator!=(const const_iterator& __x) const {
    00237     return _M_p != __x._M_p || _M_offset != __x._M_offset;
    00238   }
    00239   bool operator<(const_iterator __x) const {
    00240     return _M_p < __x._M_p || (_M_p == __x._M_p && _M_offset < __x._M_offset);
    00241   }
    00242 };
    00243
    00244 // Bit-vector base class, which encapsulates the difference between
    00245 //  old SGI-style allocators and standard-conforming allocators.
    00246
    00247 #ifdef __STL_USE_STD_ALLOCATORS
    00248
    00249 // Base class for ordinary allocators.
    00250 template <class _Allocator, bool __is_static>
    00251 class _Bvector_alloc_base {
    00252 public:
    00253   typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
    00254           allocator_type;
    00255   allocator_type get_allocator() const { return _M_data_allocator; }
    00256
    00257   _Bvector_alloc_base(const allocator_type& __a)
    00258     : _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {}
    00259
    00260 protected:
    00261   unsigned int* _M_bit_alloc(size_t __n)
    00262     { return _M_data_allocator.allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
    00263   void _M_deallocate() {
    00264     if (_M_start._M_p)
    00265       _M_data_allocator.deallocate(_M_start._M_p,
    00266                                    _M_end_of_storage - _M_start._M_p);
    00267   }
    00268
    00269   typename _Alloc_traits<unsigned int, _Allocator>::allocator_type
    00270           _M_data_allocator;
    00271   _Bit_iterator _M_start;
    00272   _Bit_iterator _M_finish;
    00273   unsigned int* _M_end_of_storage;
    00274 };
    00275
    00276 // Specialization for instanceless allocators.
    00277 template <class _Allocator>
    00278 class _Bvector_alloc_base<_Allocator, true> {
    00279 public:
    00280   typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
    00281           allocator_type;
    00282   allocator_type get_allocator() const { return allocator_type(); }
    00283
    00284   _Bvector_alloc_base(const allocator_type&)
    00285     : _M_start(), _M_finish(), _M_end_of_storage(0) {}
    00286
    00287 protected:
    00288   typedef typename _Alloc_traits<unsigned int, _Allocator>::_Alloc_type
    00289           _Alloc_type;
    00290
    00291   unsigned int* _M_bit_alloc(size_t __n)
    00292     { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
    00293   void _M_deallocate() {
    00294     if (_M_start._M_p)
    00295       _Alloc_type::deallocate(_M_start._M_p,
    00296                               _M_end_of_storage - _M_start._M_p);
    00297   }
    00298
    00299   _Bit_iterator _M_start;
    00300   _Bit_iterator _M_finish;
    00301   unsigned int* _M_end_of_storage;
    00302 };
    00303
    00304 template <class _Alloc>
    00305 class _Bvector_base
    00306   : public _Bvector_alloc_base<_Alloc,
    00307                                _Alloc_traits<bool, _Alloc>::_S_instanceless>
    00308 {
    00309   typedef _Bvector_alloc_base<_Alloc,
    00310                               _Alloc_traits<bool, _Alloc>::_S_instanceless>
    00311           _Base;
    00312 public:
    00313   typedef typename _Base::allocator_type allocator_type;
    00314
    00315   _Bvector_base(const allocator_type& __a) : _Base(__a) {}
    00316   ~_Bvector_base() { _Base::_M_deallocate(); }
    00317 };
    00318
    00319 #else /* __STL_USE_STD_ALLOCATORS */
    00320
    00321 template <class _Alloc>
    00322 class _Bvector_base
    00323 {
    00324 public:
    00325   typedef _Alloc allocator_type;
    00326   allocator_type get_allocator() const { return allocator_type(); }
    00327
    00328   _Bvector_base(const allocator_type&)
    00329     : _M_start(), _M_finish(), _M_end_of_storage(0) {}
    00330   ~_Bvector_base() { _M_deallocate(); }
    00331
    00332 protected:
    00333   typedef simple_alloc<unsigned int, _Alloc> _Alloc_type;
    00334
    00335   unsigned int* _M_bit_alloc(size_t __n)
    00336     { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
    00337   void _M_deallocate() {
    00338     if (_M_start._M_p)
    00339       _Alloc_type::deallocate(_M_start._M_p,
    00340                               _M_end_of_storage - _M_start._M_p);
    00341   }
    00342
    00343   _Bit_iterator _M_start;
    00344   _Bit_iterator _M_finish;
    00345   unsigned int* _M_end_of_storage;
    00346 };
    00347
    00348 #endif /* __STL_USE_STD_ALLOCATORS */
    00349
    00350 // The next few lines are confusing.  What we're doing is declaring a
    00351 //  partial specialization of vector<T, Alloc> if we have the necessary
    00352 //  compiler support.  Otherwise, we define a class bit_vector which uses
    00353 //  the default allocator.
    00354
    00355 #if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NO_BOOL)
    00356 #define __SGI_STL_VECBOOL_TEMPLATE
    00357 #define __BVECTOR vector
    00358 #else
    00359 #undef __SGI_STL_VECBOOL_TEMPLATE
    00360 #define __BVECTOR bit_vector
    00361 #endif
    00362
    00363 #      ifdef __SGI_STL_VECBOOL_TEMPLATE
    00364        __STL_END_NAMESPACE
    00365 #      include <stl_vector.h>
    00366        __STL_BEGIN_NAMESPACE
    00367 template<class _Alloc> class vector<bool,_Alloc>
    00368   : public _Bvector_base<_Alloc>
    00369 #      else /* __SGI_STL_VECBOOL_TEMPLATE */
    00370 class bit_vector
    00371   : public _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) >
    00372 #      endif /* __SGI_STL_VECBOOL_TEMPLATE */
    00373 {
    00374 #      ifdef __SGI_STL_VECBOOL_TEMPLATE
    00375   typedef _Bvector_base<_Alloc> _Base;
    00376 #      else /* __SGI_STL_VECBOOL_TEMPLATE */
    00377   typedef _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) > _Base;
    00378 #      endif /* __SGI_STL_VECBOOL_TEMPLATE */
    00379 public:
    00380   typedef bool value_type;
    00381   typedef size_t size_type;
    00382   typedef ptrdiff_t difference_type;
    00383   typedef _Bit_reference reference;
    00384   typedef bool const_reference;
    00385   typedef _Bit_reference* pointer;
    00386   typedef const bool* const_pointer;
    00387
    00388   typedef _Bit_iterator                iterator;
    00389   typedef _Bit_const_iterator          const_iterator;
    00390
    00391 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    00392   typedef reverse_iterator<const_iterator> const_reverse_iterator;
    00393   typedef reverse_iterator<iterator> reverse_iterator;
    00394 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00395   typedef reverse_iterator<const_iterator, value_type, const_reference,
    00396                            difference_type> const_reverse_iterator;
    00397   typedef reverse_iterator<iterator, value_type, reference, difference_type>
    00398           reverse_iterator;
    00399 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00400
    00401   typedef typename _Base::allocator_type allocator_type;
    00402   allocator_type get_allocator() const { return _Base::get_allocator(); }
    00403
    00404 protected:
    00405 #ifdef __STL_USE_NAMESPACES
    00406   using _Base::_M_bit_alloc;
    00407   using _Base::_M_deallocate;
    00408   using _Base::_M_start;
    00409   using _Base::_M_finish;
    00410   using _Base::_M_end_of_storage;
    00411 #endif /* __STL_USE_NAMESPACES */
    00412
    00413 protected:
    00414   void _M_initialize(size_type __n) {
    00415     unsigned int* __q = _M_bit_alloc(__n);
    00416     _M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT;
    00417     _M_start = iterator(__q, 0);
    00418     _M_finish = _M_start + difference_type(__n);
    00419   }
    00420   void _M_insert_aux(iterator __position, bool __x) {
    00421     if (_M_finish._M_p != _M_end_of_storage) {
    00422       copy_backward(__position, _M_finish, _M_finish + 1);
    00423       *__position = __x;
    00424       ++_M_finish;
    00425     }
    00426     else {
    00427       size_type __len = size() ? 2 * size() : __WORD_BIT;
    00428       unsigned int* __q = _M_bit_alloc(__len);
    00429       iterator __i = copy(begin(), __position, iterator(__q, 0));
    00430       *__i++ = __x;
    00431       _M_finish = copy(__position, end(), __i);
    00432       _M_deallocate();
    00433       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
    00434       _M_start = iterator(__q, 0);
    00435     }
    00436   }
    00437
    00438 #ifdef __STL_MEMBER_TEMPLATES
    00439   template <class _InputIterator>
    00440   void _M_initialize_range(_InputIterator __first, _InputIterator __last,
    00441                            input_iterator_tag) {
    00442     _M_start = iterator();
    00443     _M_finish = iterator();
    00444     _M_end_of_storage = 0;
    00445     for ( ; __first != __last; ++__first)
    00446       push_back(*__first);
    00447   }
    00448
    00449   template <class _ForwardIterator>
    00450   void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
    00451                            forward_iterator_tag) {
    00452     size_type __n = 0;
    00453     distance(__first, __last, __n);
    00454     _M_initialize(__n);
    00455     copy(__first, __last, _M_start);
    00456   }
    00457
    00458   template <class _InputIterator>
    00459   void _M_insert_range(iterator __pos,
    00460                        _InputIterator __first, _InputIterator __last,
    00461                        input_iterator_tag) {
    00462     for ( ; __first != __last; ++__first) {
    00463       __pos = insert(__pos, *__first);
    00464       ++__pos;
    00465     }
    00466   }
    00467
    00468   template <class _ForwardIterator>
    00469   void _M_insert_range(iterator __position,
    00470                        _ForwardIterator __first, _ForwardIterator __last,
    00471                        forward_iterator_tag) {
    00472     if (__first != __last) {
    00473       size_type __n = 0;
    00474       distance(__first, __last, __n);
    00475       if (capacity() - size() >= __n) {
    00476         copy_backward(__position, end(), _M_finish + difference_type(__n));
    00477         copy(__first, __last, __position);
    00478         _M_finish += difference_type(__n);
    00479       }
    00480       else {
    00481         size_type __len = size() + max(size(), __n);
    00482         unsigned int* __q = _M_bit_alloc(__len);
    00483         iterator __i = copy(begin(), __position, iterator(__q, 0));
    00484         __i = copy(__first, __last, __i);
    00485         _M_finish = copy(__position, end(), __i);
    00486         _M_deallocate();
    00487         _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
    00488         _M_start = iterator(__q, 0);
    00489       }
    00490     }
    00491   }
    00492
    00493 #endif /* __STL_MEMBER_TEMPLATES */
    00494
    00495 public:
    00496   iterator begin() { return _M_start; }
    00497   const_iterator begin() const { return _M_start; }
    00498   iterator end() { return _M_finish; }
    00499   const_iterator end() const { return _M_finish; }
    00500
    00501   reverse_iterator rbegin() { return reverse_iterator(end()); }
    00502   const_reverse_iterator rbegin() const {
    00503     return const_reverse_iterator(end());
    00504   }
    00505   reverse_iterator rend() { return reverse_iterator(begin()); }
    00506   const_reverse_iterator rend() const {
    00507     return const_reverse_iterator(begin());
    00508   }
    00509
    00510   size_type size() const { return size_type(end() - begin()); }
    00511   size_type max_size() const { return size_type(-1); }
    00512   size_type capacity() const {
    00513     return size_type(const_iterator(_M_end_of_storage, 0) - begin());
    00514   }
    00515   bool empty() const { return begin() == end(); }
    00516   reference operator[](size_type __n) {
    00517     return *(begin() + difference_type(__n));
    00518   }
    00519   const_reference operator[](size_type __n) const {
    00520     return *(begin() + difference_type(__n));
    00521   }
    00522
    00523   explicit __BVECTOR(const allocator_type& __a = allocator_type())
    00524     : _Base(__a) {}
    00525
    00526   __BVECTOR(size_type __n, bool __value,
    00527             const allocator_type& __a = allocator_type())
    00528     : _Base(__a)
    00529   {
    00530     _M_initialize(__n);
    00531     fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0);
    00532   }
    00533
    00534   explicit __BVECTOR(size_type __n)
    00535     : _Base(allocator_type())
    00536   {
    00537     _M_initialize(__n);
    00538     fill(_M_start._M_p, _M_end_of_storage, 0);
    00539   }
    00540
    00541   __BVECTOR(const __BVECTOR& __x) : _Base(__x.get_allocator()) {
    00542     _M_initialize(__x.size());
    00543     copy(__x.begin(), __x.end(), _M_start);
    00544   }
    00545
    00546 #ifdef __STL_MEMBER_TEMPLATES
    00547   // Check whether it's an integral type.  If so, it's not an iterator.
    00548   template <class _InputIterator>
    00549   __BVECTOR(_InputIterator __first, _InputIterator __last,
    00550             const allocator_type& __a = allocator_type())
    00551     : _Base(__a)
    00552   {
    00553     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00554     _M_initialize_dispatch(__first, __last, _Integral());
    00555   }
    00556
    00557   template <class _Integer>
    00558   void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
    00559     _M_initialize(__n);
    00560     fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
    00561   }
    00562
    00563   template <class _InputIterator>
    00564   void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
    00565                               __false_type) {
    00566     _M_initialize_range(__first, __last, __ITERATOR_CATEGORY(__first));
    00567   }
    00568 #else /* __STL_MEMBER_TEMPLATES */
    00569   __BVECTOR(const_iterator __first, const_iterator __last,
    00570             const allocator_type& __a = allocator_type())
    00571     : _Base(__a)
    00572   {
    00573     size_type __n = 0;
    00574     distance(__first, __last, __n);
    00575     _M_initialize(__n);
    00576     copy(__first, __last, _M_start);
    00577   }
    00578   __BVECTOR(const bool* __first, const bool* __last,
    00579             const allocator_type& __a = allocator_type())
    00580     : _Base(__a)
    00581   {
    00582     size_type __n = 0;
    00583     distance(__first, __last, __n);
    00584     _M_initialize(__n);
    00585     copy(__first, __last, _M_start);
    00586   }
    00587 #endif /* __STL_MEMBER_TEMPLATES */
    00588
    00589   ~__BVECTOR() { }
    00590
    00591   __BVECTOR& operator=(const __BVECTOR& __x) {
    00592     if (&__x == this) return *this;
    00593     if (__x.size() > capacity()) {
    00594       _M_deallocate();
    00595       _M_initialize(__x.size());
    00596     }
    00597     copy(__x.begin(), __x.end(), begin());
    00598     _M_finish = begin() + difference_type(__x.size());
    00599     return *this;
    00600   }
    00601
    00602   // assign(), a generalized assignment member function.  Two
    00603   // versions: one that takes a count, and one that takes a range.
    00604   // The range version is a member template, so we dispatch on whether
    00605   // or not the type is an integer.
    00606
    00607   void assign(size_t __n, bool __x) {
    00608     if (__n > size()) {
    00609       fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
    00610       insert(end(), __n - size(), __x);
    00611     }
    00612     else {
    00613       erase(begin() + __n, end());
    00614       fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
    00615     }
    00616   }
    00617
    00618 #ifdef __STL_MEMBER_TEMPLATES
    00619
    00620   template <class _InputIterator>
    00621   void assign(_InputIterator __first, _InputIterator __last) {
    00622     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00623     _M_assign_dispatch(__first, __last, _Integral());
    00624   }
    00625
    00626   template <class _Integer>
    00627   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    00628     { assign((size_t) __n, (bool) __val); }
    00629
    00630   template <class _InputIter>
    00631   void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
    00632     { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }
    00633
    00634   template <class _InputIterator>
    00635   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
    00636                      input_iterator_tag) {
    00637     iterator __cur = begin();
    00638     for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
    00639       *__cur = *__first;
    00640     if (__first == __last)
    00641       erase(__cur, end());
    00642     else
    00643       insert(end(), __first, __last);
    00644   }
    00645
    00646   template <class _ForwardIterator>
    00647   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
    00648                      forward_iterator_tag) {
    00649     size_type __len = 0;
    00650     distance(__first, __last, __len);
    00651     if (__len < size())
    00652       erase(copy(__first, __last, begin()), end());
    00653     else {
    00654       _ForwardIterator __mid = __first;
    00655       advance(__mid, size());
    00656       copy(__first, __mid, begin());
    00657       insert(end(), __mid, __last);
    00658     }
    00659   }
    00660
    00661 #endif /* __STL_MEMBER_TEMPLATES */
    00662
    00663   void reserve(size_type __n) {
    00664     if (capacity() < __n) {
    00665       unsigned int* __q = _M_bit_alloc(__n);
    00666       _M_finish = copy(begin(), end(), iterator(__q, 0));
    00667       _M_deallocate();
    00668       _M_start = iterator(__q, 0);
    00669       _M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT;
    00670     }
    00671   }
    00672
    00673   reference front() { return *begin(); }
    00674   const_reference front() const { return *begin(); }
    00675   reference back() { return *(end() - 1); }
    00676   const_reference back() const { return *(end() - 1); }
    00677   void push_back(bool __x) {
    00678     if (_M_finish._M_p != _M_end_of_storage)
    00679       *_M_finish++ = __x;
    00680     else
    00681       _M_insert_aux(end(), __x);
    00682   }
    00683   void swap(__BVECTOR& __x) {
    00684     __STD::swap(_M_start, __x._M_start);
    00685     __STD::swap(_M_finish, __x._M_finish);
    00686     __STD::swap(_M_end_of_storage, __x._M_end_of_storage);
    00687   }
    00688   iterator insert(iterator __position, bool __x = bool()) {
    00689     difference_type __n = __position - begin();
    00690     if (_M_finish._M_p != _M_end_of_storage && __position == end())
    00691       *_M_finish++ = __x;
    00692     else
    00693       _M_insert_aux(__position, __x);
    00694     return begin() + __n;
    00695   }
    00696
    00697 #ifdef __STL_MEMBER_TEMPLATES
    00698   // Check whether it's an integral type.  If so, it's not an iterator.
    00699   template <class _InputIterator>
    00700   void insert(iterator __position,
    00701               _InputIterator __first, _InputIterator __last) {
    00702     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00703     _M_insert_dispatch(__position, __first, __last, _Integral());
    00704   }
    00705
    00706   template <class _Integer>
    00707   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
    00708                           __true_type) {
    00709     insert(__pos, (size_type) __n, (bool) __x);
    00710   }
    00711
    00712   template <class _InputIterator>
    00713   void _M_insert_dispatch(iterator __pos,
    00714                           _InputIterator __first, _InputIterator __last,
    00715                           __false_type) {
    00716     _M_insert_range(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
    00717   }
    00718 #else /* __STL_MEMBER_TEMPLATES */
    00719   void insert(iterator __position,
    00720               const_iterator __first, const_iterator __last) {
    00721     if (__first == __last) return;
    00722     size_type __n = 0;
    00723     distance(__first, __last, __n);
    00724     if (capacity() - size() >= __n) {
    00725       copy_backward(__position, end(), _M_finish + __n);
    00726       copy(__first, __last, __position);
    00727       _M_finish += __n;
    00728     }
    00729     else {
    00730       size_type __len = size() + max(size(), __n);
    00731       unsigned int* __q = _M_bit_alloc(__len);
    00732       iterator __i = copy(begin(), __position, iterator(__q, 0));
    00733       __i = copy(__first, __last, __i);
    00734       _M_finish = copy(__position, end(), __i);
    00735       _M_deallocate();
    00736       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
    00737       _M_start = iterator(__q, 0);
    00738     }
    00739   }
    00740
    00741   void insert(iterator __position, const bool* __first, const bool* __last) {
    00742     if (__first == __last) return;
    00743     size_type __n = 0;
    00744     distance(__first, __last, __n);
    00745     if (capacity() - size() >= __n) {
    00746       copy_backward(__position, end(), _M_finish + __n);
    00747       copy(__first, __last, __position);
    00748       _M_finish += __n;
    00749     }
    00750     else {
    00751       size_type __len = size() + max(size(), __n);
    00752       unsigned int* __q = _M_bit_alloc(__len);
    00753       iterator __i = copy(begin(), __position, iterator(__q, 0));
    00754       __i = copy(__first, __last, __i);
    00755       _M_finish = copy(__position, end(), __i);
    00756       _M_deallocate();
    00757       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
    00758       _M_start = iterator(__q, 0);
    00759     }
    00760   }
    00761 #endif /* __STL_MEMBER_TEMPLATES */
    00762
    00763   void insert(iterator __position, size_type __n, bool __x) {
    00764     if (__n == 0) return;
    00765     if (capacity() - size() >= __n) {
    00766       copy_backward(__position, end(), _M_finish + difference_type(__n));
    00767       fill(__position, __position + difference_type(__n), __x);
    00768       _M_finish += difference_type(__n);
    00769     }
    00770     else {
    00771       size_type __len = size() + max(size(), __n);
    00772       unsigned int* __q = _M_bit_alloc(__len);
    00773       iterator __i = copy(begin(), __position, iterator(__q, 0));
    00774       fill_n(__i, __n, __x);
    00775       _M_finish = copy(__position, end(), __i + difference_type(__n));
    00776       _M_deallocate();
    00777       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
    00778       _M_start = iterator(__q, 0);
    00779     }
    00780   }
    00781
    00782   void pop_back() { --_M_finish; }
    00783   iterator erase(iterator __position) {
    00784     if (__position + 1 != end())
    00785       copy(__position + 1, end(), __position);
    00786       --_M_finish;
    00787     return __position;
    00788   }
    00789   iterator erase(iterator __first, iterator __last) {
    00790     _M_finish = copy(__last, end(), __first);
    00791     return __first;
    00792   }
    00793   void resize(size_type __new_size, bool __x = bool()) {
    00794     if (__new_size < size())
    00795       erase(begin() + difference_type(__new_size), end());
    00796     else
    00797       insert(end(), __new_size - size(), __x);
    00798   }
    00799   void clear() { erase(begin(), end()); }
    00800 };
    00801
    00802 #ifdef __SGI_STL_VECBOOL_TEMPLATE
    00803
    00804 typedef vector<bool, alloc> bit_vector;
    00805
    00806 #else /* __SGI_STL_VECBOOL_TEMPLATE */
    00807
    00808 inline bool
    00809 operator==(const bit_vector& __x, const bit_vector& __y)
    00810 {
    00811   return (__x.size() == __y.size() &&
    00812           equal(__x.begin(), __x.end(), __y.begin()));
    00813 }
    00814
    00815 inline bool
    00816 operator<(const bit_vector& __x, const bit_vector& __y)
    00817 {
    00818   return lexicographical_compare(__x.begin(), __x.end(),
    00819                                  __y.begin(), __y.end());
    00820 }
    00821
    00822 #endif /* __SGI_STL_VECBOOL_TEMPLATE */
    00823
    00824 #undef __SGI_STL_VECBOOL_TEMPLATE
    00825 #undef __BVECTOR
    00826
    00827 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00828 #pragma reset woff 1174
    00829 #pragma reset woff 1375
    00830 #endif
    00831
    00832 __STL_END_NAMESPACE
    00833
    00834 #endif /* __SGI_STL_INTERNAL_BVECTOR_H */
    00835
    00836 // Local Variables:
    00837 // mode:C++
    00838 // End: