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-1999
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_base : public random_access_iterator<bool, ptrdiff_t> 
00076 {
00077   unsigned int* _M_p;
00078   unsigned int _M_offset;
00079 
00080   _Bit_iterator_base(unsigned int* __x, unsigned int __y)
00081     : _M_p(__x), _M_offset(__y) {}
00082 
00083   void _M_bump_up() {
00084     if (_M_offset++ == __WORD_BIT - 1) {
00085       _M_offset = 0;
00086       ++_M_p;
00087     }
00088   }
00089   void _M_bump_down() {
00090     if (_M_offset-- == 0) {
00091       _M_offset = __WORD_BIT - 1;
00092       --_M_p;
00093     }
00094   }
00095 
00096   void _M_incr(ptrdiff_t __i) {
00097     difference_type __n = __i + _M_offset;
00098     _M_p += __n / __WORD_BIT;
00099     __n = __n % __WORD_BIT;
00100     if (__n < 0) {
00101       _M_offset = (unsigned int) __n + __WORD_BIT;
00102       --_M_p;
00103     } else
00104       _M_offset = (unsigned int) __n;
00105   }
00106 
00107   bool operator==(const _Bit_iterator_base& __i) const {
00108     return _M_p == __i._M_p && _M_offset == __i._M_offset;
00109   }
00110   bool operator<(const _Bit_iterator_base& __i) const {
00111     return _M_p < __i._M_p || (_M_p == __i._M_p && _M_offset < __i._M_offset);
00112   }
00113   bool operator!=(const _Bit_iterator_base& __i) const {
00114     return !(*this == __i);
00115   }
00116   bool operator>(const _Bit_iterator_base& __i) const {
00117     return __i < *this;
00118   }
00119   bool operator<=(const _Bit_iterator_base& __i) const {
00120     return !(__i < *this); 
00121   }
00122   bool operator>=(const _Bit_iterator_base& __i) const {
00123     return !(*this < __i);
00124   }
00125 };
00126 
00127 inline ptrdiff_t
00128 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
00129   return __WORD_BIT * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset;
00130 }
00131 
00132 
00133 struct _Bit_iterator : public _Bit_iterator_base
00134 {
00135   typedef _Bit_reference  reference;
00136   typedef _Bit_reference* pointer;
00137   typedef _Bit_iterator   iterator;
00138 
00139   _Bit_iterator() : _Bit_iterator_base(0, 0) {}
00140   _Bit_iterator(unsigned int* __x, unsigned int __y) 
00141     : _Bit_iterator_base(__x, __y) {}
00142 
00143   reference operator*() const { return reference(_M_p, 1U << _M_offset); }
00144   iterator& operator++() {
00145     _M_bump_up();
00146     return *this;
00147   }
00148   iterator operator++(int) {
00149     iterator __tmp = *this;
00150     _M_bump_up();
00151     return __tmp;
00152   }
00153   iterator& operator--() {
00154     _M_bump_down();
00155     return *this;
00156   }
00157   iterator operator--(int) {
00158     iterator __tmp = *this;
00159     _M_bump_down();
00160     return __tmp;
00161   }
00162   iterator& operator+=(difference_type __i) {
00163     _M_incr(__i);
00164     return *this;
00165   }
00166   iterator& operator-=(difference_type __i) {
00167     *this += -__i;
00168     return *this;
00169   }
00170   iterator operator+(difference_type __i) const {
00171     iterator __tmp = *this;
00172     return __tmp += __i;
00173   }
00174   iterator operator-(difference_type __i) const {
00175     iterator __tmp = *this;
00176     return __tmp -= __i;
00177   }
00178 
00179   reference operator[](difference_type __i) { return *(*this + __i); }
00180 };
00181 
00182 inline _Bit_iterator 
00183 operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; }
00184 
00185 
00186 struct _Bit_const_iterator : public _Bit_iterator_base
00187 {
00188   typedef bool                 reference;
00189   typedef bool                 const_reference;
00190   typedef const bool*          pointer;
00191   typedef _Bit_const_iterator  const_iterator;
00192 
00193   _Bit_const_iterator() : _Bit_iterator_base(0, 0) {}
00194   _Bit_const_iterator(unsigned int* __x, unsigned int __y) 
00195     : _Bit_iterator_base(__x, __y) {}
00196   _Bit_const_iterator(const _Bit_iterator& __x) 
00197     : _Bit_iterator_base(__x._M_p, __x._M_offset) {}
00198 
00199   const_reference operator*() const {
00200     return _Bit_reference(_M_p, 1U << _M_offset);
00201   }
00202   const_iterator& operator++() {
00203     _M_bump_up();
00204     return *this;
00205   }
00206   const_iterator operator++(int) {
00207     const_iterator __tmp = *this;
00208     _M_bump_up();
00209     return __tmp;
00210   }
00211   const_iterator& operator--() {
00212     _M_bump_down();
00213     return *this;
00214   }
00215   const_iterator operator--(int) {
00216     const_iterator __tmp = *this;
00217     _M_bump_down();
00218     return __tmp;
00219   }
00220   const_iterator& operator+=(difference_type __i) {
00221     _M_incr(__i);
00222     return *this;
00223   }
00224   const_iterator& operator-=(difference_type __i) {
00225     *this += -__i;
00226     return *this;
00227   }
00228   const_iterator operator+(difference_type __i) const {
00229     const_iterator __tmp = *this;
00230     return __tmp += __i;
00231   }
00232   const_iterator operator-(difference_type __i) const {
00233     const_iterator __tmp = *this;
00234     return __tmp -= __i;
00235   }
00236   const_reference operator[](difference_type __i) { 
00237     return *(*this + __i); 
00238   }
00239 };
00240 
00241 inline _Bit_const_iterator 
00242 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) { return __x + __n; }
00243 
00244 
00245 // Bit-vector base class, which encapsulates the difference between
00246 // old SGI-style allocators and standard-conforming allocators.
00247 
00248 #ifdef __STL_USE_STD_ALLOCATORS
00249 
00250 // Base class for ordinary allocators.
00251 template <class _Allocator, bool __is_static>
00252 class _Bvector_alloc_base {
00253 public:
00254   typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
00255           allocator_type;
00256   allocator_type get_allocator() const { return _M_data_allocator; }
00257 
00258   _Bvector_alloc_base(const allocator_type& __a)
00259     : _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {}
00260 
00261 protected:
00262   unsigned int* _M_bit_alloc(size_t __n) 
00263     { return _M_data_allocator.allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
00264   void _M_deallocate() {
00265     if (_M_start._M_p)
00266       _M_data_allocator.deallocate(_M_start._M_p, 
00267                                    _M_end_of_storage - _M_start._M_p);
00268   }  
00269 
00270   typename _Alloc_traits<unsigned int, _Allocator>::allocator_type 
00271           _M_data_allocator;
00272   _Bit_iterator _M_start;
00273   _Bit_iterator _M_finish;
00274   unsigned int* _M_end_of_storage;
00275 };
00276 
00277 // Specialization for instanceless allocators.
00278 template <class _Allocator>
00279 class _Bvector_alloc_base<_Allocator, true> {
00280 public:
00281   typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
00282           allocator_type;
00283   allocator_type get_allocator() const { return allocator_type(); }
00284 
00285   _Bvector_alloc_base(const allocator_type&)
00286     : _M_start(), _M_finish(), _M_end_of_storage(0) {}
00287 
00288 protected:
00289   typedef typename _Alloc_traits<unsigned int, _Allocator>::_Alloc_type
00290           _Alloc_type;
00291           
00292   unsigned int* _M_bit_alloc(size_t __n) 
00293     { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
00294   void _M_deallocate() {
00295     if (_M_start._M_p)
00296       _Alloc_type::deallocate(_M_start._M_p,
00297                               _M_end_of_storage - _M_start._M_p);
00298   }  
00299 
00300   _Bit_iterator _M_start;
00301   _Bit_iterator _M_finish;
00302   unsigned int* _M_end_of_storage;
00303 };  
00304 
00305 template <class _Alloc>
00306 class _Bvector_base
00307   : public _Bvector_alloc_base<_Alloc,
00308                                _Alloc_traits<bool, _Alloc>::_S_instanceless>
00309 {
00310   typedef _Bvector_alloc_base<_Alloc,
00311                               _Alloc_traits<bool, _Alloc>::_S_instanceless>
00312           _Base;
00313 public:
00314   typedef typename _Base::allocator_type allocator_type;
00315 
00316   _Bvector_base(const allocator_type& __a) : _Base(__a) {}
00317   ~_Bvector_base() { _Base::_M_deallocate(); }
00318 };
00319 
00320 #else /* __STL_USE_STD_ALLOCATORS */
00321 
00322 template <class _Alloc>
00323 class _Bvector_base
00324 {
00325 public:
00326   typedef _Alloc allocator_type;
00327   allocator_type get_allocator() const { return allocator_type(); }
00328 
00329   _Bvector_base(const allocator_type&)
00330     : _M_start(), _M_finish(), _M_end_of_storage(0) {}
00331   ~_Bvector_base() { _M_deallocate(); }
00332 
00333 protected:
00334   typedef simple_alloc<unsigned int, _Alloc> _Alloc_type;
00335   
00336   unsigned int* _M_bit_alloc(size_t __n) 
00337     { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
00338   void _M_deallocate() {
00339     if (_M_start._M_p)
00340       _Alloc_type::deallocate(_M_start._M_p,
00341                               _M_end_of_storage - _M_start._M_p);
00342   }
00343 
00344   _Bit_iterator _M_start;
00345   _Bit_iterator _M_finish;
00346   unsigned int* _M_end_of_storage;  
00347 };
00348 
00349 #endif /* __STL_USE_STD_ALLOCATORS */
00350 
00351 // The next few lines are confusing.  What we're doing is declaring a
00352 //  partial specialization of vector<T, Alloc> if we have the necessary
00353 //  compiler support.  Otherwise, we define a class bit_vector which uses
00354 //  the default allocator. 
00355 
00356 #if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NO_BOOL)
00357 #  define __SGI_STL_VECBOOL_TEMPLATE
00358 #  define __BVECTOR           vector<bool, _Alloc>
00359 #  define __VECTOR            vector
00360 #  define __BVECTOR_BASE      _Bvector_base<_Alloc>
00361 #  define __BVECTOR_TMPL_LIST template <class _Alloc>
00362    __STL_END_NAMESPACE
00363 #  include <stl_vector.h>
00364    __STL_BEGIN_NAMESPACE
00365 #else  /* __STL_CLASS_PARTIAL_SPECIALIZATION && !__STL_NO_BOOL */
00366 #  undef  __SGI_STL_VECBOOL_TEMPLATE
00367 #  define __BVECTOR           bit_vector
00368 #  define __VECTOR            bit_vector
00369 #  define __BVECTOR_BASE      _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) >
00370 #  define __BVECTOR_TMPL_LIST
00371 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION && !__STL_NO_BOOL */
00372 
00373 
00374 __BVECTOR_TMPL_LIST 
00375 class __BVECTOR : public __BVECTOR_BASE 
00376 {
00377 public:
00378   typedef bool value_type;
00379   typedef size_t size_type;
00380   typedef ptrdiff_t difference_type; 
00381   typedef _Bit_reference reference;
00382   typedef bool const_reference;
00383   typedef _Bit_reference* pointer;
00384   typedef const bool* const_pointer;
00385 
00386   typedef _Bit_iterator                iterator;
00387   typedef _Bit_const_iterator          const_iterator;
00388 
00389 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
00390   typedef reverse_iterator<const_iterator> const_reverse_iterator;
00391   typedef reverse_iterator<iterator> reverse_iterator;
00392 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
00393   typedef reverse_iterator<const_iterator, value_type, const_reference, 
00394                            difference_type> const_reverse_iterator;
00395   typedef reverse_iterator<iterator, value_type, reference, difference_type>
00396           reverse_iterator;
00397 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
00398 
00399   typedef typename __BVECTOR_BASE::allocator_type allocator_type;
00400   allocator_type get_allocator() const {
00401     return __BVECTOR_BASE::get_allocator();
00402   }
00403 
00404 protected:
00405 #ifdef __STL_USE_NAMESPACES  
00406   using __BVECTOR_BASE::_M_bit_alloc;
00407   using __BVECTOR_BASE::_M_deallocate;
00408   using __BVECTOR_BASE::_M_start;
00409   using __BVECTOR_BASE::_M_finish;
00410   using __BVECTOR_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 
00517   reference operator[](size_type __n)
00518     { return *(begin() + difference_type(__n)); }
00519   const_reference operator[](size_type __n) const
00520     { return *(begin() + difference_type(__n)); }
00521 
00522 #ifdef __STL_THROW_RANGE_ERRORS
00523   void _M_range_check(size_type __n) const {
00524     if (__n >= this->size())
00525       __stl_throw_range_error("vector<bool>");
00526   }
00527 
00528   reference at(size_type __n)
00529     { _M_range_check(__n); return (*this)[__n]; }
00530   const_reference at(size_type __n) const
00531     { _M_range_check(__n); return (*this)[__n]; }
00532 #endif /* __STL_THROW_RANGE_ERRORS */
00533 
00534   explicit __VECTOR(const allocator_type& __a = allocator_type())
00535     : __BVECTOR_BASE(__a) {}
00536 
00537   __VECTOR(size_type __n, bool __value,
00538             const allocator_type& __a = allocator_type())
00539     : __BVECTOR_BASE(__a)
00540   {
00541     _M_initialize(__n);
00542     fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0);
00543   }
00544 
00545   explicit __VECTOR(size_type __n)
00546     : __BVECTOR_BASE(allocator_type())
00547   {
00548     _M_initialize(__n);
00549     fill(_M_start._M_p, _M_end_of_storage, 0);
00550   }
00551 
00552   __VECTOR(const __VECTOR& __x) : __BVECTOR_BASE(__x.get_allocator()) {
00553     _M_initialize(__x.size());
00554     copy(__x.begin(), __x.end(), _M_start);
00555   }
00556 
00557 #ifdef __STL_MEMBER_TEMPLATES
00558 
00559   // Check whether it's an integral type.  If so, it's not an iterator.
00560 
00561   template <class _Integer>
00562   void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
00563     _M_initialize(__n);
00564     fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
00565   }
00566 
00567   template <class _InputIterator>
00568   void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00569                               __false_type) {
00570     _M_initialize_range(__first, __last, __ITERATOR_CATEGORY(__first));
00571   }
00572 
00573   template <class _InputIterator>
00574   __VECTOR(_InputIterator __first, _InputIterator __last,
00575            const allocator_type& __a = allocator_type())
00576     : __BVECTOR_BASE(__a)
00577   {
00578     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00579     _M_initialize_dispatch(__first, __last, _Integral());
00580   }
00581     
00582 #else /* __STL_MEMBER_TEMPLATES */
00583 
00584   __VECTOR(const_iterator __first, const_iterator __last,
00585            const allocator_type& __a = allocator_type())
00586     : __BVECTOR_BASE(__a)
00587   {
00588     size_type __n = 0;
00589     distance(__first, __last, __n);
00590     _M_initialize(__n);
00591     copy(__first, __last, _M_start);
00592   }
00593   __VECTOR(const bool* __first, const bool* __last,
00594            const allocator_type& __a = allocator_type())
00595     : __BVECTOR_BASE(__a)
00596   {
00597     size_type __n = 0;
00598     distance(__first, __last, __n);
00599     _M_initialize(__n);
00600     copy(__first, __last, _M_start);
00601   }
00602 
00603 #endif /* __STL_MEMBER_TEMPLATES */
00604 
00605   ~__VECTOR() { }
00606 
00607   __VECTOR& operator=(const __VECTOR& __x) {
00608     if (&__x == this) return *this;
00609     if (__x.size() > capacity()) {
00610       _M_deallocate();
00611       _M_initialize(__x.size());
00612     }
00613     copy(__x.begin(), __x.end(), begin());
00614     _M_finish = begin() + difference_type(__x.size());
00615     return *this;
00616   }
00617 
00618   // assign(), a generalized assignment member function.  Two
00619   // versions: one that takes a count, and one that takes a range.
00620   // The range version is a member template, so we dispatch on whether
00621   // or not the type is an integer.
00622 
00623   void _M_fill_assign(size_t __n, bool __x) {
00624     if (__n > size()) {
00625       fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
00626       insert(end(), __n - size(), __x);
00627     }
00628     else {
00629       erase(begin() + __n, end());
00630       fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
00631     }
00632   }
00633 
00634   void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); }
00635 
00636 #ifdef __STL_MEMBER_TEMPLATES
00637 
00638   template <class _InputIterator>
00639   void assign(_InputIterator __first, _InputIterator __last) {
00640     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00641     _M_assign_dispatch(__first, __last, _Integral());
00642   }
00643 
00644   template <class _Integer>
00645   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00646     { _M_fill_assign((size_t) __n, (bool) __val); }
00647 
00648   template <class _InputIter>
00649   void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
00650     { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }
00651 
00652   template <class _InputIterator>
00653   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
00654                      input_iterator_tag) {
00655     iterator __cur = begin();
00656     for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
00657       *__cur = *__first;
00658     if (__first == __last)
00659       erase(__cur, end());
00660     else
00661       insert(end(), __first, __last);
00662   }
00663 
00664   template <class _ForwardIterator>
00665   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00666                      forward_iterator_tag) {
00667     size_type __len = 0;
00668     distance(__first, __last, __len);
00669     if (__len < size())
00670       erase(copy(__first, __last, begin()), end());
00671     else {
00672       _ForwardIterator __mid = __first;
00673       advance(__mid, size());
00674       copy(__first, __mid, begin());
00675       insert(end(), __mid, __last);
00676     }
00677   }    
00678 
00679 #endif /* __STL_MEMBER_TEMPLATES */
00680 
00681   void reserve(size_type __n) {
00682     if (capacity() < __n) {
00683       unsigned int* __q = _M_bit_alloc(__n);
00684       _M_finish = copy(begin(), end(), iterator(__q, 0));
00685       _M_deallocate();
00686       _M_start = iterator(__q, 0);
00687       _M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT;
00688     }
00689   }
00690 
00691   reference front() { return *begin(); }
00692   const_reference front() const { return *begin(); }
00693   reference back() { return *(end() - 1); }
00694   const_reference back() const { return *(end() - 1); }
00695   void push_back(bool __x) {
00696     if (_M_finish._M_p != _M_end_of_storage)
00697       *_M_finish++ = __x;
00698     else
00699       _M_insert_aux(end(), __x);
00700   }
00701   void swap(__BVECTOR& __x) {
00702     __STD::swap(_M_start, __x._M_start);
00703     __STD::swap(_M_finish, __x._M_finish);
00704     __STD::swap(_M_end_of_storage, __x._M_end_of_storage);
00705   }
00706   iterator insert(iterator __position, bool __x = bool()) {
00707     difference_type __n = __position - begin();
00708     if (_M_finish._M_p != _M_end_of_storage && __position == end())
00709       *_M_finish++ = __x;
00710     else
00711       _M_insert_aux(__position, __x);
00712     return begin() + __n;
00713   }
00714 
00715 #ifdef __STL_MEMBER_TEMPLATES
00716   // Check whether it's an integral type.  If so, it's not an iterator.
00717 
00718   template <class _Integer>
00719   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
00720                           __true_type) {
00721     _M_fill_insert(__pos, __n, __x);
00722   }
00723 
00724   template <class _InputIterator>
00725   void _M_insert_dispatch(iterator __pos,
00726                           _InputIterator __first, _InputIterator __last,
00727                           __false_type) {
00728     _M_insert_range(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
00729   }
00730 
00731   template <class _InputIterator>
00732   void insert(iterator __position,
00733               _InputIterator __first, _InputIterator __last) {
00734     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00735     _M_insert_dispatch(__position, __first, __last, _Integral());
00736   }
00737 
00738 #else /* __STL_MEMBER_TEMPLATES */
00739   void insert(iterator __position,
00740               const_iterator __first, const_iterator __last) {
00741     if (__first == __last) return;
00742     size_type __n = 0;
00743     distance(__first, __last, __n);
00744     if (capacity() - size() >= __n) {
00745       copy_backward(__position, end(), _M_finish + __n);
00746       copy(__first, __last, __position);
00747       _M_finish += __n;
00748     }
00749     else {
00750       size_type __len = size() + max(size(), __n);
00751       unsigned int* __q = _M_bit_alloc(__len);
00752       iterator __i = copy(begin(), __position, iterator(__q, 0));
00753       __i = copy(__first, __last, __i);
00754       _M_finish = copy(__position, end(), __i);
00755       _M_deallocate();
00756       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
00757       _M_start = iterator(__q, 0);
00758     }
00759   }
00760 
00761   void insert(iterator __position, const bool* __first, const bool* __last) {
00762     if (__first == __last) return;
00763     size_type __n = 0;
00764     distance(__first, __last, __n);
00765     if (capacity() - size() >= __n) {
00766       copy_backward(__position, end(), _M_finish + __n);
00767       copy(__first, __last, __position);
00768       _M_finish += __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       __i = copy(__first, __last, __i);
00775       _M_finish = copy(__position, end(), __i);
00776       _M_deallocate();
00777       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
00778       _M_start = iterator(__q, 0);
00779     }
00780   }
00781 #endif /* __STL_MEMBER_TEMPLATES */
00782 
00783   void _M_fill_insert(iterator __position, size_type __n, bool __x) {
00784     if (__n == 0) return;
00785     if (capacity() - size() >= __n) {
00786       copy_backward(__position, end(), _M_finish + difference_type(__n));
00787       fill(__position, __position + difference_type(__n), __x);
00788       _M_finish += difference_type(__n);
00789     }
00790     else {
00791       size_type __len = size() + max(size(), __n);
00792       unsigned int* __q = _M_bit_alloc(__len);
00793       iterator __i = copy(begin(), __position, iterator(__q, 0));
00794       fill_n(__i, __n, __x);
00795       _M_finish = copy(__position, end(), __i + difference_type(__n));
00796       _M_deallocate();
00797       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
00798       _M_start = iterator(__q, 0);
00799     }
00800   }
00801 
00802   void insert(iterator __position, size_type __n, bool __x) {
00803     _M_fill_insert(__position, __n, __x);
00804   }
00805 
00806   void pop_back() { --_M_finish; }
00807   iterator erase(iterator __position) {
00808     if (__position + 1 != end())
00809       copy(__position + 1, end(), __position);
00810       --_M_finish;
00811     return __position;
00812   }
00813   iterator erase(iterator __first, iterator __last) {
00814     _M_finish = copy(__last, end(), __first);
00815     return __first;
00816   }
00817   void resize(size_type __new_size, bool __x = bool()) {
00818     if (__new_size < size()) 
00819       erase(begin() + difference_type(__new_size), end());
00820     else
00821       insert(end(), __new_size - size(), __x);
00822   }
00823   void flip() {
00824     for (unsigned int* __p = _M_start._M_p; __p != _M_end_of_storage; ++__p)
00825       *__p = ~*__p;
00826   }
00827 
00828   void clear() { erase(begin(), end()); }
00829 };
00830 
00831 #ifdef __SGI_STL_VECBOOL_TEMPLATE
00832 
00833 // This typedef is non-standard.  It is provided for backward compatibility.
00834 typedef vector<bool, alloc> bit_vector;
00835 
00836 #else /* __SGI_STL_VECBOOL_TEMPLATE */
00837 
00838 inline void swap(bit_vector& __x, bit_vector& __y) {
00839   __x.swap(__y);
00840 }
00841 
00842 inline bool 
00843 operator==(const bit_vector& __x, const bit_vector& __y)
00844 {
00845   return (__x.size() == __y.size() && 
00846           equal(__x.begin(), __x.end(), __y.begin()));
00847 }
00848 
00849 inline bool 
00850 operator!=(const bit_vector& __x, const bit_vector& __y)
00851 {
00852   return !(__x == __y);
00853 }
00854 
00855 inline bool 
00856 operator<(const bit_vector& __x, const bit_vector& __y)
00857 {
00858   return lexicographical_compare(__x.begin(), __x.end(), 
00859                                  __y.begin(), __y.end());
00860 }
00861 
00862 inline bool operator>(const bit_vector& __x, const bit_vector& __y)
00863 {
00864   return __y < __x;
00865 }
00866 
00867 inline bool operator<=(const bit_vector& __x, const bit_vector& __y)
00868 {
00869   return !(__y < __x);
00870 }
00871 
00872 inline bool operator>=(const bit_vector& __x, const bit_vector& __y)
00873 {
00874   return !(__x < __y);
00875 }
00876 
00877 #endif /* __SGI_STL_VECBOOL_TEMPLATE */
00878 
00879 #undef __SGI_STL_VECBOOL_TEMPLATE
00880 #undef __BVECTOR
00881 #undef __VECTOR
00882 #undef __BVECTOR_BASE
00883 #undef __BVECTOR_TMPL_LIST 
00884 
00885 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
00886 #pragma reset woff 1174
00887 #pragma reset woff 1375
00888 #endif
00889 
00890 __STL_END_NAMESPACE 
00891 
00892 #endif /* __SGI_STL_INTERNAL_BVECTOR_H */
00893 
00894 // Local Variables:
00895 // mode:C++
00896 // End:

Generated on Mon Jun 5 10:20:44 2006 for Intelligence.kdevelop by  doxygen 1.4.6