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,1997
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
36static 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
43struct _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
49public:
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
68inline void swap(_Bit_reference __x, _Bit_reference __y)
69{
70  bool __tmp = __x;
71  __x = __y;
72  __y = __tmp;
73}
74
75struct _Bit_iterator : public random_access_iterator<bool, ptrdiff_t> {
76  typedef _Bit_reference  reference;
77  typedef _Bit_reference* pointer;
78  typedef _Bit_iterator   iterator;
79
80  unsigned int* _M_p;
81  unsigned int _M_offset;
82  void bump_up() {
83    if (_M_offset++ == __WORD_BIT - 1) {
84      _M_offset = 0;
85      ++_M_p;
86    }
87  }
88  void bump_down() {
89    if (_M_offset-- == 0) {
90      _M_offset = __WORD_BIT - 1;
91      --_M_p;
92    }
93  }
94
95  _Bit_iterator() : _M_p(0), _M_offset(0) {}
96  _Bit_iterator(unsigned int* __x, unsigned int __y)
97    : _M_p(__x), _M_offset(__y) {}
98  reference operator*() const { return reference(_M_p, 1U << _M_offset); }
99  iterator& operator++() {
100    bump_up();
101    return *this;
102  }
103  iterator operator++(int) {
104    iterator __tmp = *this;
105    bump_up();
106    return __tmp;
107  }
108  iterator& operator--() {
109    bump_down();
110    return *this;
111  }
112  iterator operator--(int) {
113    iterator __tmp = *this;
114    bump_down();
115    return __tmp;
116  }
117  iterator& operator+=(difference_type __i) {
118    difference_type __n = __i + _M_offset;
119    _M_p += __n / __WORD_BIT;
120    __n = __n % __WORD_BIT;
121    if (__n < 0) {
122      _M_offset = (unsigned int) __n + __WORD_BIT;
123      --_M_p;
124    } else
125      _M_offset = (unsigned int) __n;
126    return *this;
127  }
128  iterator& operator-=(difference_type __i) {
129    *this += -__i;
130    return *this;
131  }
132  iterator operator+(difference_type __i) const {
133    iterator __tmp = *this;
134    return __tmp += __i;
135  }
136  iterator operator-(difference_type __i) const {
137    iterator __tmp = *this;
138    return __tmp -= __i;
139  }
140  difference_type operator-(iterator __x) const {
141    return __WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset;
142  }
143  reference operator[](difference_type __i) { return *(*this + __i); }
144  bool operator==(const iterator& __x) const {
145    return _M_p == __x._M_p && _M_offset == __x._M_offset;
146  }
147  bool operator!=(const iterator& __x) const {
148    return _M_p != __x._M_p || _M_offset != __x._M_offset;
149  }
150  bool operator<(iterator __x) const {
151    return _M_p < __x._M_p || (_M_p == __x._M_p && _M_offset < __x._M_offset);
152  }
153};
154
155struct _Bit_const_iterator
156  : public random_access_iterator<bool, ptrdiff_t>
157{
158  typedef bool                 reference;
159  typedef bool                 const_reference;
160  typedef const bool*          pointer;
161  typedef _Bit_const_iterator  const_iterator;
162
163  unsigned int* _M_p;
164  unsigned int _M_offset;
165  void bump_up() {
166    if (_M_offset++ == __WORD_BIT - 1) {
167      _M_offset = 0;
168      ++_M_p;
169    }
170  }
171  void bump_down() {
172    if (_M_offset-- == 0) {
173      _M_offset = __WORD_BIT - 1;
174      --_M_p;
175    }
176  }
177
178  _Bit_const_iterator() : _M_p(0), _M_offset(0) {}
179  _Bit_const_iterator(unsigned int* __x, unsigned int __y)
180    : _M_p(__x), _M_offset(__y) {}
181  _Bit_const_iterator(const _Bit_iterator& __x)
182    : _M_p(__x._M_p), _M_offset(__x._M_offset) {}
183  const_reference operator*() const {
184    return _Bit_reference(_M_p, 1U << _M_offset);
185  }
186  const_iterator& operator++() {
187    bump_up();
188    return *this;
189  }
190  const_iterator operator++(int) {
191    const_iterator __tmp = *this;
192    bump_up();
193    return __tmp;
194  }
195  const_iterator& operator--() {
196    bump_down();
197    return *this;
198  }
199  const_iterator operator--(int) {
200    const_iterator __tmp = *this;
201    bump_down();
202    return __tmp;
203  }
204  const_iterator& operator+=(difference_type __i) {
205    difference_type __n = __i + _M_offset;
206    _M_p += __n / __WORD_BIT;
207    __n = __n % __WORD_BIT;
208    if (__n < 0) {
209      _M_offset = (unsigned int) __n + __WORD_BIT;
210      --_M_p;
211    } else
212      _M_offset = (unsigned int) __n;
213    return *this;
214  }
215  const_iterator& operator-=(difference_type __i) {
216    *this += -__i;
217    return *this;
218  }
219  const_iterator operator+(difference_type __i) const {
220    const_iterator __tmp = *this;
221    return __tmp += __i;
222  }
223  const_iterator operator-(difference_type __i) const {
224    const_iterator __tmp = *this;
225    return __tmp -= __i;
226  }
227  difference_type operator-(const_iterator __x) const {
228    return __WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset;
229  }
230  const_reference operator[](difference_type __i) {
231    return *(*this + __i);
232  }
233  bool operator==(const const_iterator& __x) const {
234    return _M_p == __x._M_p && _M_offset == __x._M_offset;
235  }
236  bool operator!=(const const_iterator& __x) const {
237    return _M_p != __x._M_p || _M_offset != __x._M_offset;
238  }
239  bool operator<(const_iterator __x) const {
240    return _M_p < __x._M_p || (_M_p == __x._M_p && _M_offset < __x._M_offset);
241  }
242};
243
244// Bit-vector base class, which encapsulates the difference between
245//  old SGI-style allocators and standard-conforming allocators.
246
247#ifdef __STL_USE_STD_ALLOCATORS
248
249// Base class for ordinary allocators.
250template <class _Allocator, bool __is_static>
251class _Bvector_alloc_base {
252public:
253  typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
254          allocator_type;
255  allocator_type get_allocator() const { return _M_data_allocator; }
256
257  _Bvector_alloc_base(const allocator_type& __a)
258    : _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {}
259
260protected:
261  unsigned int* _M_bit_alloc(size_t __n)
262    { return _M_data_allocator.allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
263  void _M_deallocate() {
264    if (_M_start._M_p)
265      _M_data_allocator.deallocate(_M_start._M_p,
266                                   _M_end_of_storage - _M_start._M_p);
267  }
268
269  typename _Alloc_traits<unsigned int, _Allocator>::allocator_type
270          _M_data_allocator;
271  _Bit_iterator _M_start;
272  _Bit_iterator _M_finish;
273  unsigned int* _M_end_of_storage;
274};
275
276// Specialization for instanceless allocators.
277template <class _Allocator>
278class _Bvector_alloc_base<_Allocator, true> {
279public:
280  typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
281          allocator_type;
282  allocator_type get_allocator() const { return allocator_type(); }
283
284  _Bvector_alloc_base(const allocator_type&)
285    : _M_start(), _M_finish(), _M_end_of_storage(0) {}
286
287protected:
288  typedef typename _Alloc_traits<unsigned int, _Allocator>::_Alloc_type
289          _Alloc_type;
290
291  unsigned int* _M_bit_alloc(size_t __n)
292    { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
293  void _M_deallocate() {
294    if (_M_start._M_p)
295      _Alloc_type::deallocate(_M_start._M_p,
296                              _M_end_of_storage - _M_start._M_p);
297  }
298
299  _Bit_iterator _M_start;
300  _Bit_iterator _M_finish;
301  unsigned int* _M_end_of_storage;
302};
303
304template <class _Alloc>
305class _Bvector_base
306  : public _Bvector_alloc_base<_Alloc,
307                               _Alloc_traits<bool, _Alloc>::_S_instanceless>
308{
309  typedef _Bvector_alloc_base<_Alloc,
310                              _Alloc_traits<bool, _Alloc>::_S_instanceless>
311          _Base;
312public:
313  typedef typename _Base::allocator_type allocator_type;
314
315  _Bvector_base(const allocator_type& __a) : _Base(__a) {}
316  ~_Bvector_base() { _Base::_M_deallocate(); }
317};
318
319#else /* __STL_USE_STD_ALLOCATORS */
320
321template <class _Alloc>
322class _Bvector_base
323{
324public:
325  typedef _Alloc allocator_type;
326  allocator_type get_allocator() const { return allocator_type(); }
327
328  _Bvector_base(const allocator_type&)
329    : _M_start(), _M_finish(), _M_end_of_storage(0) {}
330  ~_Bvector_base() { _M_deallocate(); }
331
332protected:
333  typedef simple_alloc<unsigned int, _Alloc> _Alloc_type;
334
335  unsigned int* _M_bit_alloc(size_t __n)
336    { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
337  void _M_deallocate() {
338    if (_M_start._M_p)
339      _Alloc_type::deallocate(_M_start._M_p,
340                              _M_end_of_storage - _M_start._M_p);
341  }
342
343  _Bit_iterator _M_start;
344  _Bit_iterator _M_finish;
345  unsigned int* _M_end_of_storage;
346};
347
348#endif /* __STL_USE_STD_ALLOCATORS */
349
350// The next few lines are confusing.  What we're doing is declaring a
351//  partial specialization of vector<T, Alloc> if we have the necessary
352//  compiler support.  Otherwise, we define a class bit_vector which uses
353//  the default allocator.
354
355#if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NO_BOOL)
356#define __SGI_STL_VECBOOL_TEMPLATE
357#define __BVECTOR vector
358#else
359#undef __SGI_STL_VECBOOL_TEMPLATE
360#define __BVECTOR bit_vector
361#endif
362
363#      ifdef __SGI_STL_VECBOOL_TEMPLATE
364       __STL_END_NAMESPACE
365#      include <stl_vector.h>
366       __STL_BEGIN_NAMESPACE
367template<class _Alloc> class vector<bool,_Alloc>
368  : public _Bvector_base<_Alloc>
369#      else /* __SGI_STL_VECBOOL_TEMPLATE */
370class bit_vector
371  : public _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) >
372#      endif /* __SGI_STL_VECBOOL_TEMPLATE */
373{
374#      ifdef __SGI_STL_VECBOOL_TEMPLATE
375  typedef _Bvector_base<_Alloc> _Base;
376#      else /* __SGI_STL_VECBOOL_TEMPLATE */
377  typedef _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) > _Base;
378#      endif /* __SGI_STL_VECBOOL_TEMPLATE */
379public:
380  typedef bool value_type;
381  typedef size_t size_type;
382  typedef ptrdiff_t difference_type;
383  typedef _Bit_reference reference;
384  typedef bool const_reference;
385  typedef _Bit_reference* pointer;
386  typedef const bool* const_pointer;
387
388  typedef _Bit_iterator                iterator;
389  typedef _Bit_const_iterator          const_iterator;
390
391#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
392  typedef reverse_iterator<const_iterator> const_reverse_iterator;
393  typedef reverse_iterator<iterator> reverse_iterator;
394#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
395  typedef reverse_iterator<const_iterator, value_type, const_reference,
396                           difference_type> const_reverse_iterator;
397  typedef reverse_iterator<iterator, value_type, reference, difference_type>
398          reverse_iterator;
399#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
400
401  typedef typename _Base::allocator_type allocator_type;
402  allocator_type get_allocator() const { return _Base::get_allocator(); }
403
404protected:
405#ifdef __STL_USE_NAMESPACES
406  using _Base::_M_bit_alloc;
407  using _Base::_M_deallocate;
408  using _Base::_M_start;
409  using _Base::_M_finish;
410  using _Base::_M_end_of_storage;
411#endif /* __STL_USE_NAMESPACES */
412
413protected:
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
495public:
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  reference operator[](size_type __n) {
517    return *(begin() + difference_type(__n));
518  }
519  const_reference operator[](size_type __n) const {
520    return *(begin() + difference_type(__n));
521  }
522
523  explicit __BVECTOR(const allocator_type& __a = allocator_type())
524    : _Base(__a) {}
525
526  __BVECTOR(size_type __n, bool __value,
527            const allocator_type& __a = allocator_type())
528    : _Base(__a)
529  {
530    _M_initialize(__n);
531    fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0);
532  }
533
534  explicit __BVECTOR(size_type __n)
535    : _Base(allocator_type())
536  {
537    _M_initialize(__n);
538    fill(_M_start._M_p, _M_end_of_storage, 0);
539  }
540
541  __BVECTOR(const __BVECTOR& __x) : _Base(__x.get_allocator()) {
542    _M_initialize(__x.size());
543    copy(__x.begin(), __x.end(), _M_start);
544  }
545
546#ifdef __STL_MEMBER_TEMPLATES
547  // Check whether it's an integral type.  If so, it's not an iterator.
548  template <class _InputIterator>
549  __BVECTOR(_InputIterator __first, _InputIterator __last,
550            const allocator_type& __a = allocator_type())
551    : _Base(__a)
552  {
553    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
554    _M_initialize_dispatch(__first, __last, _Integral());
555  }
556
557  template <class _Integer>
558  void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
559    _M_initialize(__n);
560    fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
561  }
562
563  template <class _InputIterator>
564  void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
565                              __false_type) {
566    _M_initialize_range(__first, __last, __ITERATOR_CATEGORY(__first));
567  }
568#else /* __STL_MEMBER_TEMPLATES */
569  __BVECTOR(const_iterator __first, const_iterator __last,
570            const allocator_type& __a = allocator_type())
571    : _Base(__a)
572  {
573    size_type __n = 0;
574    distance(__first, __last, __n);
575    _M_initialize(__n);
576    copy(__first, __last, _M_start);
577  }
578  __BVECTOR(const bool* __first, const bool* __last,
579            const allocator_type& __a = allocator_type())
580    : _Base(__a)
581  {
582    size_type __n = 0;
583    distance(__first, __last, __n);
584    _M_initialize(__n);
585    copy(__first, __last, _M_start);
586  }
587#endif /* __STL_MEMBER_TEMPLATES */
588
589  ~__BVECTOR() { }
590
591  __BVECTOR& operator=(const __BVECTOR& __x) {
592    if (&__x == this) return *this;
593    if (__x.size() > capacity()) {
594      _M_deallocate();
595      _M_initialize(__x.size());
596    }
597    copy(__x.begin(), __x.end(), begin());
598    _M_finish = begin() + difference_type(__x.size());
599    return *this;
600  }
601
602  // assign(), a generalized assignment member function.  Two
603  // versions: one that takes a count, and one that takes a range.
604  // The range version is a member template, so we dispatch on whether
605  // or not the type is an integer.
606
607  void assign(size_t __n, bool __x) {
608    if (__n > size()) {
609      fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
610      insert(end(), __n - size(), __x);
611    }
612    else {
613      erase(begin() + __n, end());
614      fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
615    }
616  }
617
618#ifdef __STL_MEMBER_TEMPLATES
619
620  template <class _InputIterator>
621  void assign(_InputIterator __first, _InputIterator __last) {
622    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
623    _M_assign_dispatch(__first, __last, _Integral());
624  }
625
626  template <class _Integer>
627  void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
628    { assign((size_t) __n, (bool) __val); }
629
630  template <class _InputIter>
631  void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
632    { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }
633
634  template <class _InputIterator>
635  void _M_assign_aux(_InputIterator __first, _InputIterator __last,
636                     input_iterator_tag) {
637    iterator __cur = begin();
638    for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
639      *__cur = *__first;
640    if (__first == __last)
641      erase(__cur, end());
642    else
643      insert(end(), __first, __last);
644  }
645
646  template <class _ForwardIterator>
647  void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
648                     forward_iterator_tag) {
649    size_type __len = 0;
650    distance(__first, __last, __len);
651    if (__len < size())
652      erase(copy(__first, __last, begin()), end());
653    else {
654      _ForwardIterator __mid = __first;
655      advance(__mid, size());
656      copy(__first, __mid, begin());
657      insert(end(), __mid, __last);
658    }
659  }
660
661#endif /* __STL_MEMBER_TEMPLATES */
662
663  void reserve(size_type __n) {
664    if (capacity() < __n) {
665      unsigned int* __q = _M_bit_alloc(__n);
666      _M_finish = copy(begin(), end(), iterator(__q, 0));
667      _M_deallocate();
668      _M_start = iterator(__q, 0);
669      _M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT;
670    }
671  }
672
673  reference front() { return *begin(); }
674  const_reference front() const { return *begin(); }
675  reference back() { return *(end() - 1); }
676  const_reference back() const { return *(end() - 1); }
677  void push_back(bool __x) {
678    if (_M_finish._M_p != _M_end_of_storage)
679      *_M_finish++ = __x;
680    else
681      _M_insert_aux(end(), __x);
682  }
683  void swap(__BVECTOR& __x) {
684    __STD::swap(_M_start, __x._M_start);
685    __STD::swap(_M_finish, __x._M_finish);
686    __STD::swap(_M_end_of_storage, __x._M_end_of_storage);
687  }
688  iterator insert(iterator __position, bool __x = bool()) {
689    difference_type __n = __position - begin();
690    if (_M_finish._M_p != _M_end_of_storage && __position == end())
691      *_M_finish++ = __x;
692    else
693      _M_insert_aux(__position, __x);
694    return begin() + __n;
695  }
696
697#ifdef __STL_MEMBER_TEMPLATES
698  // Check whether it's an integral type.  If so, it's not an iterator.
699  template <class _InputIterator>
700  void insert(iterator __position,
701              _InputIterator __first, _InputIterator __last) {
702    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
703    _M_insert_dispatch(__position, __first, __last, _Integral());
704  }
705
706  template <class _Integer>
707  void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
708                          __true_type) {
709    insert(__pos, (size_type) __n, (bool) __x);
710  }
711
712  template <class _InputIterator>
713  void _M_insert_dispatch(iterator __pos,
714                          _InputIterator __first, _InputIterator __last,
715                          __false_type) {
716    _M_insert_range(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
717  }
718#else /* __STL_MEMBER_TEMPLATES */
719  void insert(iterator __position,
720              const_iterator __first, const_iterator __last) {
721    if (__first == __last) return;
722    size_type __n = 0;
723    distance(__first, __last, __n);
724    if (capacity() - size() >= __n) {
725      copy_backward(__position, end(), _M_finish + __n);
726      copy(__first, __last, __position);
727      _M_finish += __n;
728    }
729    else {
730      size_type __len = size() + max(size(), __n);
731      unsigned int* __q = _M_bit_alloc(__len);
732      iterator __i = copy(begin(), __position, iterator(__q, 0));
733      __i = copy(__first, __last, __i);
734      _M_finish = copy(__position, end(), __i);
735      _M_deallocate();
736      _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
737      _M_start = iterator(__q, 0);
738    }
739  }
740
741  void insert(iterator __position, const bool* __first, const bool* __last) {
742    if (__first == __last) return;
743    size_type __n = 0;
744    distance(__first, __last, __n);
745    if (capacity() - size() >= __n) {
746      copy_backward(__position, end(), _M_finish + __n);
747      copy(__first, __last, __position);
748      _M_finish += __n;
749    }
750    else {
751      size_type __len = size() + max(size(), __n);
752      unsigned int* __q = _M_bit_alloc(__len);
753      iterator __i = copy(begin(), __position, iterator(__q, 0));
754      __i = copy(__first, __last, __i);
755      _M_finish = copy(__position, end(), __i);
756      _M_deallocate();
757      _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
758      _M_start = iterator(__q, 0);
759    }
760  }
761#endif /* __STL_MEMBER_TEMPLATES */
762
763  void insert(iterator __position, size_type __n, bool __x) {
764    if (__n == 0) return;
765    if (capacity() - size() >= __n) {
766      copy_backward(__position, end(), _M_finish + difference_type(__n));
767      fill(__position, __position + difference_type(__n), __x);
768      _M_finish += difference_type(__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      fill_n(__i, __n, __x);
775      _M_finish = copy(__position, end(), __i + difference_type(__n));
776      _M_deallocate();
777      _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
778      _M_start = iterator(__q, 0);
779    }
780  }
781
782  void pop_back() { --_M_finish; }
783  iterator erase(iterator __position) {
784    if (__position + 1 != end())
785      copy(__position + 1, end(), __position);
786      --_M_finish;
787    return __position;
788  }
789  iterator erase(iterator __first, iterator __last) {
790    _M_finish = copy(__last, end(), __first);
791    return __first;
792  }
793  void resize(size_type __new_size, bool __x = bool()) {
794    if (__new_size < size())
795      erase(begin() + difference_type(__new_size), end());
796    else
797      insert(end(), __new_size - size(), __x);
798  }
799  void clear() { erase(begin(), end()); }
800};
801
802#ifdef __SGI_STL_VECBOOL_TEMPLATE
803
804typedef vector<bool, alloc> bit_vector;
805
806#else /* __SGI_STL_VECBOOL_TEMPLATE */
807
808inline bool
809operator==(const bit_vector& __x, const bit_vector& __y)
810{
811  return (__x.size() == __y.size() &&
812          equal(__x.begin(), __x.end(), __y.begin()));
813}
814
815inline bool
816operator<(const bit_vector& __x, const bit_vector& __y)
817{
818  return lexicographical_compare(__x.begin(), __x.end(),
819                                 __y.begin(), __y.end());
820}
821
822#endif /* __SGI_STL_VECBOOL_TEMPLATE */
823
824#undef __SGI_STL_VECBOOL_TEMPLATE
825#undef __BVECTOR
826
827#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
828#pragma reset woff 1174
829#pragma reset woff 1375
830#endif
831
832__STL_END_NAMESPACE
833
834#endif /* __SGI_STL_INTERNAL_BVECTOR_H */
835
836// Local Variables:
837// mode:C++
838// End:
839