Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

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