OSDN Git Service

* include/std/std_bitset.h (_M_do_find_next): Fix -Wall nit.
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / std / std_bitset.h
1 // <bitset> -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING.  If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
19 // USA.
20
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction.  Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License.  This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
29
30 /*
31  * Copyright (c) 1998
32  * Silicon Graphics Computer Systems, Inc.
33  *
34  * Permission to use, copy, modify, distribute and sell this software
35  * and its documentation for any purpose is hereby granted without fee,
36  * provided that the above copyright notice appear in all copies and
37  * that both that copyright notice and this permission notice appear
38  * in supporting documentation.  Silicon Graphics makes no
39  * representations about the suitability of this software for any
40  * purpose.  It is provided "as is" without express or implied warranty.
41  */
42
43 /** @file bitset
44  *  This is a Standard C++ Library header.  You should @c #include this header
45  *  in your programs, rather than any of the "st[dl]_*.h" implementation files.
46  */
47
48 #ifndef _GLIBCPP_BITSET_H
49 #define _GLIBCPP_BITSET_H
50
51 #pragma GCC system_header
52
53 #include <cstddef>     // for size_t
54 #include <cstring>     // for memset
55 #include <limits>      // for numeric_limits
56 #include <string>
57 #include <bits/functexcept.h>   // for invalid_argument, out_of_range,
58                                 // overflow_error
59 #include <ostream>     // for ostream (operator<<)
60 #include <istream>     // for istream (operator>>)
61
62
63 #define _GLIBCPP_BITSET_BITS_PER_WORD  numeric_limits<unsigned long>::digits
64 #define _GLIBCPP_BITSET_WORDS(__n) \
65  ((__n) < 1 ? 0 : ((__n) + _GLIBCPP_BITSET_BITS_PER_WORD - 1)/_GLIBCPP_BITSET_BITS_PER_WORD)
66
67 namespace std
68 {
69   /**
70    *  @if maint
71    *  Base class, general case.  It is a class inveriant that _Nw will be
72    *  nonnegative.
73    *
74    *  See documentation for bitset.
75    *  @endif
76   */
77   template<size_t _Nw>
78     struct _Base_bitset
79     {
80       typedef unsigned long _WordT;
81
82       /// 0 is the least significant word.
83       _WordT            _M_w[_Nw];
84
85       _Base_bitset() { _M_do_reset(); }
86       _Base_bitset(unsigned long __val)
87       {
88         _M_do_reset();
89         _M_w[0] = __val;
90       }
91
92       static size_t
93       _S_whichword(size_t __pos )
94       { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
95
96       static size_t
97       _S_whichbyte(size_t __pos )
98       { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
99
100       static size_t
101       _S_whichbit(size_t __pos )
102       { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
103
104       static _WordT
105       _S_maskbit(size_t __pos )
106       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
107
108       _WordT&
109       _M_getword(size_t __pos)
110       { return _M_w[_S_whichword(__pos)]; }
111
112       _WordT
113       _M_getword(size_t __pos) const
114       { return _M_w[_S_whichword(__pos)]; }
115
116       _WordT&
117       _M_hiword() { return _M_w[_Nw - 1]; }
118
119       _WordT
120       _M_hiword() const { return _M_w[_Nw - 1]; }
121
122       void
123       _M_do_and(const _Base_bitset<_Nw>& __x)
124       {
125         for (size_t __i = 0; __i < _Nw; __i++)
126           _M_w[__i] &= __x._M_w[__i];
127       }
128
129       void
130       _M_do_or(const _Base_bitset<_Nw>& __x)
131       {
132         for (size_t __i = 0; __i < _Nw; __i++)
133           _M_w[__i] |= __x._M_w[__i];
134       }
135
136       void
137       _M_do_xor(const _Base_bitset<_Nw>& __x)
138       {
139         for (size_t __i = 0; __i < _Nw; __i++)
140           _M_w[__i] ^= __x._M_w[__i];
141       }
142
143       void
144       _M_do_left_shift(size_t __shift);
145
146       void
147       _M_do_right_shift(size_t __shift);
148
149       void
150       _M_do_flip()
151       {
152         for (size_t __i = 0; __i < _Nw; __i++)
153           _M_w[__i] = ~_M_w[__i];
154       }
155
156       void
157       _M_do_set()
158       {
159         for (size_t __i = 0; __i < _Nw; __i++)
160           _M_w[__i] = ~static_cast<_WordT>(0);
161       }
162
163       void
164       _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); }
165
166       bool
167       _M_is_equal(const _Base_bitset<_Nw>& __x) const
168       {
169         for (size_t __i = 0; __i < _Nw; ++__i)
170           {
171             if (_M_w[__i] != __x._M_w[__i])
172               return false;
173           }
174         return true;
175       }
176
177       bool
178       _M_is_any() const
179       {
180         for (size_t __i = 0; __i < _Nw; __i++)
181           {
182             if (_M_w[__i] != static_cast<_WordT>(0))
183               return true;
184           }
185         return false;
186       }
187
188       size_t
189       _M_do_count() const
190       {
191         size_t __result = 0;
192         for (size_t __i = 0; __i < _Nw; __i++)
193           __result += __builtin_popcountl(_M_w[__i]);
194         return __result;
195       }
196
197       unsigned long
198       _M_do_to_ulong() const;
199
200       // find first "on" bit
201       size_t
202       _M_do_find_first(size_t __not_found) const;
203
204       // find the next "on" bit that follows "prev"
205       size_t
206       _M_do_find_next(size_t __prev, size_t __not_found) const;
207     };
208
209   // Definitions of non-inline functions from _Base_bitset.
210   template<size_t _Nw>
211     void
212     _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
213     {
214       if (__builtin_expect(__shift != 0, 1))
215         {
216           const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD;
217           const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD;
218
219           if (__offset == 0)
220             for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
221               _M_w[__n] = _M_w[__n - __wshift];
222           else
223             {
224               const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset;
225               for (size_t __n = _Nw - 1; __n > __wshift; --__n)
226                 _M_w[__n] = (_M_w[__n - __wshift] << __offset) |
227                   (_M_w[__n - __wshift - 1] >> __sub_offset);
228               _M_w[__wshift] = _M_w[0] << __offset;
229             }
230
231           fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
232         }
233     }
234
235   template<size_t _Nw>
236     void
237     _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
238     {
239       if (__builtin_expect(__shift != 0, 1))
240         {
241           const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD;
242           const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD;
243           const size_t __limit = _Nw - __wshift - 1;
244
245           if (__offset == 0)
246             for (size_t __n = 0; __n <= __limit; ++__n)
247               _M_w[__n] = _M_w[__n + __wshift];
248           else
249             {
250               const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset;
251               for (size_t __n = 0; __n < __limit; ++__n)
252                 _M_w[__n] = (_M_w[__n + __wshift] >> __offset) |
253                   (_M_w[__n + __wshift + 1] << __sub_offset);
254               _M_w[__limit] = _M_w[_Nw-1] >> __offset;
255             }
256
257           fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
258         }
259     }
260
261   template<size_t _Nw>
262     unsigned long
263     _Base_bitset<_Nw>::_M_do_to_ulong() const
264     {
265       for (size_t __i = 1; __i < _Nw; ++__i)
266         if (_M_w[__i])
267           __throw_overflow_error("bitset -- too large to fit in unsigned long");
268       return _M_w[0];
269     }
270
271   template<size_t _Nw>
272     size_t
273     _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const
274     {
275       for (size_t __i = 0; __i < _Nw; __i++)
276         {
277           _WordT __thisword = _M_w[__i];
278           if (__thisword != static_cast<_WordT>(0))
279             return __i * _GLIBCPP_BITSET_BITS_PER_WORD
280               + __builtin_ctzl(__thisword);
281         }
282       // not found, so return an indication of failure.
283       return __not_found;
284     }
285
286   template<size_t _Nw>
287     size_t
288     _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
289     {
290       // make bound inclusive
291       ++__prev;
292
293       // check out of bounds
294       if ( __prev >= _Nw * _GLIBCPP_BITSET_BITS_PER_WORD )
295         return __not_found;
296
297       // search first word
298       size_t __i = _S_whichword(__prev);
299       _WordT __thisword = _M_w[__i];
300
301       // mask off bits below bound
302       __thisword >>= __prev + 1;
303
304       if (__thisword != static_cast<_WordT>(0))
305         return __i * _GLIBCPP_BITSET_BITS_PER_WORD
306           + __builtin_ctzl(__thisword);
307
308       // check subsequent words
309       __i++;
310       for ( ; __i < _Nw; __i++ )
311         {
312           __thisword = _M_w[__i];
313           if (__thisword != static_cast<_WordT>(0))
314             return __i * _GLIBCPP_BITSET_BITS_PER_WORD
315               + __builtin_ctzl(__thisword);
316         }
317       // not found, so return an indication of failure.
318       return __not_found;
319     } // end _M_do_find_next
320
321
322   /**
323    *  @if maint
324    *  Base class, specialization for a single word.
325    *
326    *  See documentation for bitset.
327    *  @endif
328   */
329   template<>
330     struct _Base_bitset<1>
331     {
332       typedef unsigned long _WordT;
333       _WordT _M_w;
334
335       _Base_bitset( void ) : _M_w(0) {}
336       _Base_bitset(unsigned long __val) : _M_w(__val) {}
337
338       static size_t
339       _S_whichword(size_t __pos )
340       { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
341
342       static size_t
343       _S_whichbyte(size_t __pos )
344       { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
345
346       static size_t
347       _S_whichbit(size_t __pos )
348       {  return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
349
350       static _WordT
351       _S_maskbit(size_t __pos )
352       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
353
354       _WordT&
355       _M_getword(size_t) { return _M_w; }
356
357       _WordT
358       _M_getword(size_t) const { return _M_w; }
359
360       _WordT&
361       _M_hiword() { return _M_w; }
362
363       _WordT
364       _M_hiword() const { return _M_w; }
365
366       void
367       _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; }
368
369       void
370       _M_do_or(const _Base_bitset<1>& __x)  { _M_w |= __x._M_w; }
371
372       void
373       _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; }
374
375       void
376       _M_do_left_shift(size_t __shift) { _M_w <<= __shift; }
377
378       void
379       _M_do_right_shift(size_t __shift) { _M_w >>= __shift; }
380
381       void
382       _M_do_flip() { _M_w = ~_M_w; }
383
384       void
385       _M_do_set() { _M_w = ~static_cast<_WordT>(0); }
386
387       void
388       _M_do_reset() { _M_w = 0; }
389
390       bool
391       _M_is_equal(const _Base_bitset<1>& __x) const
392       { return _M_w == __x._M_w; }
393
394       bool
395       _M_is_any() const { return _M_w != 0; }
396
397       size_t
398       _M_do_count() const { return __builtin_popcountl(_M_w); }
399
400       unsigned long
401       _M_do_to_ulong() const { return _M_w; }
402
403       size_t
404       _M_do_find_first(size_t __not_found) const
405       {
406         if (_M_w != 0)
407           return __builtin_ctzl(_M_w);
408         else
409           return __not_found;
410       }
411
412       // find the next "on" bit that follows "prev"
413       size_t
414       _M_do_find_next(size_t __prev, size_t __not_found) const
415       {
416         ++__prev;
417         if (__prev >= ((size_t) _GLIBCPP_BITSET_BITS_PER_WORD))
418           return __not_found;
419
420         _WordT __x = _M_w >> __prev;
421         if (__x != 0)
422           return __builtin_ctzl(__x) + __prev;
423         else
424           return __not_found;
425       }
426     };
427
428
429   /**
430    *  @if maint
431    *  Base class, specialization for no storage (zero-length %bitset).
432    *
433    *  See documentation for bitset.
434    *  @endif
435   */
436   template<>
437     struct _Base_bitset<0>
438     {
439       typedef unsigned long _WordT;
440
441       _Base_bitset() {}
442       _Base_bitset(unsigned long) {}
443
444       static size_t
445       _S_whichword(size_t __pos )
446       { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
447
448       static size_t
449       _S_whichbyte(size_t __pos )
450       { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
451
452       static size_t
453       _S_whichbit(size_t __pos )
454       {  return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
455
456       static _WordT
457       _S_maskbit(size_t __pos )
458       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
459
460       // This would normally give access to the data.  The bounds-checking
461       // in the bitset class will prevent the user from getting this far,
462       // but (1) it must still return an lvalue to compile, and (2) the
463       // user might call _Unchecked_set directly, in which case this /needs/
464       // to fail.  Let's not penalize zero-length users unless they actually
465       // make an unchecked call; all the memory ugliness is therefore
466       // localized to this single should-never-get-this-far function.
467       _WordT&
468       _M_getword(size_t) const
469       { __throw_out_of_range("bitset -- zero-length"); return *new _WordT; }
470
471       _WordT
472       _M_hiword() const { return 0; }
473
474       void
475       _M_do_and(const _Base_bitset<0>&) { }
476
477       void
478       _M_do_or(const _Base_bitset<0>&)  { }
479
480       void
481       _M_do_xor(const _Base_bitset<0>&) { }
482
483       void
484       _M_do_left_shift(size_t) { }
485
486       void
487       _M_do_right_shift(size_t) { }
488
489       void
490       _M_do_flip() { }
491
492       void
493       _M_do_set() { }
494
495       void
496       _M_do_reset() { }
497
498       // Are all empty bitsets equal to each other?  Are they equal to
499       // themselves?  How to compare a thing which has no state?  What is
500       // the sound of one zero-length bitset clapping?
501       bool
502       _M_is_equal(const _Base_bitset<0>&) const { return true; }
503
504       bool
505       _M_is_any() const { return false; }
506
507       size_t
508       _M_do_count() const { return 0; }
509
510       unsigned long
511       _M_do_to_ulong() const { return 0; }
512
513       // Normally "not found" is the size, but that could also be
514       // misinterpreted as an index in this corner case.  Oh well.
515       size_t
516       _M_do_find_first(size_t) const { return 0; }
517
518       size_t
519       _M_do_find_next(size_t, size_t) const { return 0; }
520     };
521
522
523   // Helper class to zero out the unused high-order bits in the highest word.
524   template<size_t _Extrabits>
525     struct _Sanitize
526     {
527       static void _S_do_sanitize(unsigned long& __val)
528       { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
529     };
530
531   template<>
532     struct _Sanitize<0>
533     { static void _S_do_sanitize(unsigned long) { } };
534
535
536   /**
537    *  @brief  The %bitset class represents a @e fixed-size sequence of bits.
538    *
539    *  @ingroup Containers
540    *
541    *  (Note that %bitset does @e not meet the formal requirements of a
542    *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
543    *
544    *  The template argument, @a Nb, may be any non-negative number,
545    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
546    *
547    *  In the general unoptimized case, storage is allocated in word-sized
548    *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
549    *  words will be used for storage.  B - Nb%B bits are unused.  (They are
550    *  the high-order bits in the highest word.)  It is a class invariant
551    *  that those unused bits are always zero.
552    *
553    *  If you think of %bitset as "a simple array of bits," be aware that
554    *  your mental picture is reversed:  a %bitset behaves the same way as
555    *  bits in integers do, with the bit at index 0 in the "least significant
556    *  / right-hand" position, and the bit at index Nb-1 in the "most
557    *  significant / left-hand" position.  Thus, unlike other containers, a
558    *  %bitset's index "counts from right to left," to put it very loosely.
559    *
560    *  This behavior is preserved when translating to and from strings.  For
561    *  example, the first line of the following program probably prints
562    *  "b('a') is 0001100001" on a modern ASCII system.
563    *
564    *  @code
565    *     #include <bitset>
566    *     #include <iostream>
567    *     #include <sstream>
568    *
569    *     using namespace std;
570    *
571    *     int main()
572    *     {
573    *         long         a = 'a';
574    *         bitset<10>   b(a);
575    *
576    *         cout << "b('a') is " << b << endl;
577    *
578    *         ostringstream s;
579    *         s << b;
580    *         string  str = s.str();
581    *         cout << "index 3 in the string is " << str[3] << " but\n"
582    *              << "index 3 in the bitset is " << b[3] << endl;
583    *     }
584    *  @endcode
585    *
586    *  Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23
587    *  for a description of extensions.
588    *
589    *  @if maint
590    *  Most of the actual code isn't contained in %bitset<> itself, but in the
591    *  base class _Base_bitset.  The base class works with whole words, not with
592    *  individual bits.  This allows us to specialize _Base_bitset for the
593    *  important special case where the %bitset is only a single word.
594    *
595    *  Extra confusion can result due to the fact that the storage for
596    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
597    *  carefully encapsulated.
598    *  @endif
599   */
600   template<size_t _Nb>
601     class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)>
602   {
603   private:
604     typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base;
605     typedef unsigned long _WordT;
606
607     void
608     _M_do_sanitize()
609     {
610       _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>::
611           _S_do_sanitize(this->_M_hiword());
612     }
613
614   public:
615     /**
616      *  This encapsulates the concept of a single bit.  An instance of this
617      *  class is a proxy for an actual bit; this way the individual bit
618      *  operations are done as faster word-size bitwise instructions.
619      *
620      *  Most users will never need to use this class directly; conversions
621      *  to and from bool are automatic and should be transparent.  Overloaded
622      *  operators help to preserve the illusion.
623      *
624      *  (On a typical system, this "bit %reference" is 64 times the size of
625      *  an actual bit.  Ha.)
626     */
627     class reference
628     {
629       friend class bitset;
630
631       _WordT *_M_wp;
632       size_t _M_bpos;
633
634       // left undefined
635       reference();
636
637     public:
638       reference(bitset& __b, size_t __pos)
639       {
640         _M_wp = &__b._M_getword(__pos);
641         _M_bpos = _Base::_S_whichbit(__pos);
642       }
643
644       ~reference() { }
645
646       // for b[i] = __x;
647       reference&
648       operator=(bool __x)
649       {
650         if ( __x )
651           *_M_wp |= _Base::_S_maskbit(_M_bpos);
652         else
653           *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
654         return *this;
655       }
656
657       // for b[i] = b[__j];
658       reference&
659       operator=(const reference& __j)
660       {
661         if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) )
662           *_M_wp |= _Base::_S_maskbit(_M_bpos);
663         else
664           *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
665         return *this;
666       }
667
668       // flips the bit
669       bool
670       operator~() const
671       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
672
673       // for __x = b[i];
674       operator bool() const
675       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
676
677       // for b[i].flip();
678       reference&
679       flip()
680       {
681         *_M_wp ^= _Base::_S_maskbit(_M_bpos);
682         return *this;
683       }
684     };
685     friend class reference;
686
687     // 23.3.5.1 constructors:
688     /// All bits set to zero.
689     bitset() { }
690
691     /// Initial bits bitwise-copied from a single word (others set to zero).
692     bitset(unsigned long __val) : _Base(__val)
693     { _M_do_sanitize(); }
694
695     /**
696      *  @brief  Use a subset of a string.
697      *  @param  s  A string of '0' and '1' characters.
698      *  @param  pos  Index of the first character in @a s to use; defaults
699      *               to zero.
700      *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
701      *  @throw  std::invalid_argument  If a character appears in the string
702      *                                 which is neither '0' nor '1'.
703     */
704     template<class _CharT, class _Traits, class _Alloc>
705       explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
706                       size_t __pos = 0) : _Base()
707       {
708         if (__pos > __s.size())
709           __throw_out_of_range("bitset -- initial position is larger than "
710                                "the string itself");
711         _M_copy_from_string(__s, __pos,
712                             basic_string<_CharT, _Traits, _Alloc>::npos);
713       }
714
715     /**
716      *  @brief  Use a subset of a string.
717      *  @param  s  A string of '0' and '1' characters.
718      *  @param  pos  Index of the first character in @a s to use.
719      *  @param  n    The number of characters to copy.
720      *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
721      *  @throw  std::invalid_argument  If a character appears in the string
722      *                                 which is neither '0' nor '1'.
723     */
724     template<class _CharT, class _Traits, class _Alloc>
725       bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
726              size_t __pos, size_t __n) : _Base()
727       {
728         if (__pos > __s.size())
729           __throw_out_of_range("bitset -- initial position is larger than "
730                                "the string itself");
731         _M_copy_from_string(__s, __pos, __n);
732       }
733
734     // 23.3.5.2 bitset operations:
735     //@{
736     /**
737      *  @brief  Operations on bitsets.
738      *  @param  rhs  A same-sized bitset.
739      *
740      *  These should be self-explanatory.
741     */
742     bitset<_Nb>&
743     operator&=(const bitset<_Nb>& __rhs)
744     {
745       this->_M_do_and(__rhs);
746       return *this;
747     }
748
749     bitset<_Nb>&
750     operator|=(const bitset<_Nb>& __rhs)
751     {
752       this->_M_do_or(__rhs);
753       return *this;
754     }
755
756     bitset<_Nb>&
757     operator^=(const bitset<_Nb>& __rhs)
758     {
759       this->_M_do_xor(__rhs);
760       return *this;
761     }
762     //@}
763
764     //@{
765     /**
766      *  @brief  Operations on bitsets.
767      *  @param  pos  The number of places to shift.
768      *
769      *  These should be self-explanatory.
770     */
771     bitset<_Nb>&
772     operator<<=(size_t __pos)
773     {
774       if (__builtin_expect(__pos < _Nb, 1))
775         {
776           this->_M_do_left_shift(__pos);
777           this->_M_do_sanitize();
778         }
779       else
780         this->_M_do_reset();
781       return *this;
782     }
783
784     bitset<_Nb>&
785     operator>>=(size_t __pos)
786     {
787       if (__builtin_expect(__pos < _Nb, 1))
788         {
789           this->_M_do_right_shift(__pos);
790           this->_M_do_sanitize();
791         }
792       else
793         this->_M_do_reset();
794       return *this;
795     }
796     //@}
797
798     //@{
799     /**
800      *  These versions of single-bit set, reset, flip, and test are
801      *  extensions from the SGI version.  They do no range checking.
802      *  @ingroup SGIextensions
803     */
804     bitset<_Nb>&
805     _Unchecked_set(size_t __pos)
806     {
807       this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
808       return *this;
809     }
810
811     bitset<_Nb>&
812     _Unchecked_set(size_t __pos, int __val)
813     {
814       if (__val)
815         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
816       else
817         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
818       return *this;
819     }
820
821     bitset<_Nb>&
822     _Unchecked_reset(size_t __pos)
823     {
824       this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
825       return *this;
826     }
827
828     bitset<_Nb>&
829     _Unchecked_flip(size_t __pos)
830     {
831       this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
832       return *this;
833     }
834
835     bool
836     _Unchecked_test(size_t __pos) const
837     {
838       return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
839         != static_cast<_WordT>(0);
840     }
841     //@}
842
843     // Set, reset, and flip.
844     /**
845      *  @brief Sets every bit to true.
846     */
847     bitset<_Nb>&
848     set()
849     {
850       this->_M_do_set();
851       this->_M_do_sanitize();
852       return *this;
853     }
854
855     /**
856      *  @brief Sets a given bit to a particular value.
857      *  @param  pos  The index of the bit.
858      *  @param  val  Either true or false, defaults to true.
859      *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
860     */
861     bitset<_Nb>&
862     set(size_t __pos, bool __val = true)
863     {
864       if (__pos >= _Nb)
865         __throw_out_of_range("bitset -- set() argument too large");
866       return _Unchecked_set(__pos, __val);
867     }
868
869     /**
870      *  @brief Sets every bit to false.
871     */
872     bitset<_Nb>&
873     reset()
874     {
875       this->_M_do_reset();
876       return *this;
877     }
878
879     /**
880      *  @brief Sets a given bit to false.
881      *  @param  pos  The index of the bit.
882      *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
883      *
884      *  Same as writing @c set(pos,false).
885     */
886     bitset<_Nb>&
887     reset(size_t __pos)
888     {
889       if (__pos >= _Nb)
890         __throw_out_of_range("bitset -- reset() argument too large");
891       return _Unchecked_reset(__pos);
892     }
893
894     /**
895      *  @brief Toggles every bit to its opposite value.
896     */
897     bitset<_Nb>&
898     flip()
899     {
900       this->_M_do_flip();
901       this->_M_do_sanitize();
902       return *this;
903     }
904
905     /**
906      *  @brief Toggles a given bit to its opposite value.
907      *  @param  pos  The index of the bit.
908      *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
909     */
910     bitset<_Nb>&
911     flip(size_t __pos)
912     {
913       if (__pos >= _Nb)
914         __throw_out_of_range("bitset -- flip() argument too large");
915       return _Unchecked_flip(__pos);
916     }
917
918     /// See the no-argument flip().
919     bitset<_Nb>
920     operator~() const { return bitset<_Nb>(*this).flip(); }
921
922     //@{
923     /**
924      *  @brief  Array-indexing support.
925      *  @param  pos  Index into the %bitset.
926      *  @return  A bool for a 'const %bitset'.  For non-const bitsets, an
927      *           instance of the reference proxy class.
928      *  @note  These operators do no range checking and throw no exceptions,
929      *         as required by DR 11 to the standard.
930      *
931      *  @if maint
932      *  _GLIBCPP_RESOLVE_LIB_DEFECTS Note that this implementation already
933      *  resolves DR 11 (items 1 and 2), but does not do the range-checking
934      *  required by that DR's resolution.  -pme
935      *  The DR has since been changed:  range-checking is a precondition
936      *  (users' responsibility), and these functions must not throw.  -pme
937      *  @endif
938     */
939     reference
940     operator[](size_t __pos) { return reference(*this,__pos); }
941
942     bool
943     operator[](size_t __pos) const { return _Unchecked_test(__pos); }
944     //@}
945
946     /**
947      *  @brief Retuns a numerical interpretation of the %bitset.
948      *  @return  The integral equivalent of the bits.
949      *  @throw  std::overflow_error  If there are too many bits to be
950      *                               represented in an @c unsigned @c long.
951     */
952     unsigned long
953     to_ulong() const { return this->_M_do_to_ulong(); }
954
955     /**
956      *  @brief Retuns a character interpretation of the %bitset.
957      *  @return  The string equivalent of the bits.
958      *
959      *  Note the ordering of the bits:  decreasing character positions
960      *  correspond to increasing bit positions (see the main class notes for
961      *  an example).
962      *
963      *  Also note that you must specify the string's template parameters
964      *  explicitly.  Given a bitset @c bs and a string @s:
965      *  @code
966      *     s = bs.to_string<char,char_traits<char>,allocator<char> >();
967      *  @endcode
968     */
969     template<class _CharT, class _Traits, class _Alloc>
970       basic_string<_CharT, _Traits, _Alloc>
971       to_string() const
972       {
973         basic_string<_CharT, _Traits, _Alloc> __result;
974         _M_copy_to_string(__result);
975         return __result;
976       }
977
978     // Helper functions for string operations.
979     template<class _CharT, class _Traits, class _Alloc>
980       void
981       _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s,
982                           size_t, size_t);
983
984     template<class _CharT, class _Traits, class _Alloc>
985       void
986       _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const;
987
988     /// Returns the number of bits which are set.
989     size_t
990     count() const { return this->_M_do_count(); }
991
992     /// Returns the total number of bits.
993     size_t
994     size() const { return _Nb; }
995
996     //@{
997     /// These comparisons for equality/inequality are, well, @e bitwise.
998     bool
999     operator==(const bitset<_Nb>& __rhs) const
1000     { return this->_M_is_equal(__rhs); }
1001
1002     bool
1003     operator!=(const bitset<_Nb>& __rhs) const
1004     { return !this->_M_is_equal(__rhs); }
1005     //@}
1006
1007     /**
1008      *  @brief Tests the value of a bit.
1009      *  @param  pos  The index of a bit.
1010      *  @return  The value at @a pos.
1011      *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1012     */
1013     bool
1014     test(size_t __pos) const
1015     {
1016       if (__pos >= _Nb)
1017         __throw_out_of_range("bitset -- test() argument too large");
1018       return _Unchecked_test(__pos);
1019     }
1020
1021     /**
1022      *  @brief Tests whether any of the bits are on.
1023      *  @return  True if at least one bit is set.
1024     */
1025     bool
1026     any() const { return this->_M_is_any(); }
1027
1028     /**
1029      *  @brief Tests whether any of the bits are on.
1030      *  @return  True if none of the bits are set.
1031     */
1032     bool
1033     none() const { return !this->_M_is_any(); }
1034
1035     //@{
1036     /// Self-explanatory.
1037     bitset<_Nb>
1038     operator<<(size_t __pos) const
1039     { return bitset<_Nb>(*this) <<= __pos; }
1040
1041     bitset<_Nb>
1042     operator>>(size_t __pos) const
1043     { return bitset<_Nb>(*this) >>= __pos; }
1044     //@}
1045
1046     /**
1047      *  @brief  Finds the index of the first "on" bit.
1048      *  @return  The index of the first bit set, or size() if not found.
1049      *  @ingroup SGIextensions
1050      *  @sa  _Find_next
1051     */
1052     size_t
1053     _Find_first() const
1054     { return this->_M_do_find_first(_Nb); }
1055
1056     /**
1057      *  @brief  Finds the index of the next "on" bit after prev.
1058      *  @return  The index of the next bit set, or size() if not found.
1059      *  @param  prev  Where to start searching.
1060      *  @ingroup SGIextensions
1061      *  @sa  _Find_first
1062     */
1063     size_t
1064     _Find_next(size_t __prev ) const
1065     { return this->_M_do_find_next(__prev, _Nb); }
1066   };
1067
1068   // Definitions of non-inline member functions.
1069   template<size_t _Nb>
1070     template<class _CharT, class _Traits, class _Alloc>
1071     void
1072     bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n)
1073     {
1074       reset();
1075       const size_t __nbits = std::min(_Nb, std::min(__n, __s.size() - __pos));
1076       for (size_t __i = 0; __i < __nbits; ++__i)
1077         {
1078           switch(__s[__pos + __nbits - __i - 1])
1079             {
1080             case '0':
1081               break;
1082             case '1':
1083               set(__i);
1084               break;
1085             default:
1086               __throw_invalid_argument("bitset -- string contains characters "
1087                                        "which are neither 0 nor 1");
1088             }
1089         }
1090     }
1091
1092   template<size_t _Nb>
1093     template<class _CharT, class _Traits, class _Alloc>
1094     void
1095     bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const
1096     {
1097       __s.assign(_Nb, '0');
1098       for (size_t __i = 0; __i < _Nb; ++__i)
1099         if (_Unchecked_test(__i))
1100           __s[_Nb - 1 - __i] = '1';
1101     }
1102
1103   // 23.3.5.3 bitset operations:
1104   //@{
1105   /**
1106    *  @brief  Global bitwise operations on bitsets.
1107    *  @param  x  A bitset.
1108    *  @param  y  A bitset of the same size as @a x.
1109    *  @return  A new bitset.
1110    *
1111    *  These should be self-explanatory.
1112   */
1113   template<size_t _Nb>
1114     inline bitset<_Nb>
1115     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1116     {
1117       bitset<_Nb> __result(__x);
1118       __result &= __y;
1119       return __result;
1120     }
1121
1122   template<size_t _Nb>
1123     inline bitset<_Nb>
1124     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1125     {
1126       bitset<_Nb> __result(__x);
1127       __result |= __y;
1128       return __result;
1129     }
1130
1131   template <size_t _Nb>
1132     inline bitset<_Nb>
1133     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1134     {
1135       bitset<_Nb> __result(__x);
1136       __result ^= __y;
1137       return __result;
1138     }
1139   //@}
1140
1141   //@{
1142   /**
1143    *  @brief Global I/O operators for bitsets.
1144    *
1145    *  Direct I/O between streams and bitsets is supported.  Output is
1146    *  straightforward.  Input will skip whitespace, only accept '0' and '1'
1147    *  characters, and will only extract as many digits as the %bitset will
1148    *  hold.
1149   */
1150   template<class _CharT, class _Traits, size_t _Nb>
1151     basic_istream<_CharT, _Traits>&
1152     operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
1153     {
1154       typedef typename _Traits::char_type char_type;
1155       basic_string<_CharT, _Traits> __tmp;
1156       __tmp.reserve(_Nb);
1157
1158       // Skip whitespace
1159       typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
1160       if (__sentry)
1161         {
1162           ios_base::iostate  __state = ios_base::goodbit;
1163           basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
1164           for (size_t __i = 0; __i < _Nb; ++__i)
1165             {
1166               static typename _Traits::int_type __eof = _Traits::eof();
1167
1168               typename _Traits::int_type __c1 = __buf->sbumpc();
1169               if (_Traits::eq_int_type(__c1, __eof))
1170                 {
1171                   __state |= ios_base::eofbit;
1172                   break;
1173                 }
1174               else
1175                 {
1176                   char_type __c2 = _Traits::to_char_type(__c1);
1177                   char_type __c  = __is.narrow(__c2, '*');
1178
1179                   if (__c == '0' || __c == '1')
1180                     __tmp.push_back(__c);
1181                   else if (_Traits::eq_int_type(__buf->sputbackc(__c2), __eof))
1182                     {
1183                       __state |= ios_base::failbit;
1184                       break;
1185                     }
1186                 }
1187             }
1188
1189           if (__tmp.empty() && !_Nb)
1190             __state |= ios_base::failbit;
1191           else
1192             __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
1193
1194           if (__state != ios_base::goodbit)
1195             __is.setstate(__state);    // may throw an exception
1196         }
1197
1198       return __is;
1199     }
1200
1201   template <class _CharT, class _Traits, size_t _Nb>
1202     basic_ostream<_CharT, _Traits>&
1203     operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x)
1204     {
1205       basic_string<_CharT, _Traits> __tmp;
1206       __x._M_copy_to_string(__tmp);
1207       return __os << __tmp;
1208     }
1209   //@}
1210 } // namespace std
1211
1212 #undef _GLIBCPP_BITSET_WORDS
1213 #undef _GLIBCPP_BITSET_BITS_PER_WORD
1214
1215 #endif /* _GLIBCPP_BITSET_H */