overby.me
this repo has no description
1// -*- C++ -*-
2//===---------------------------- bitset ----------------------------------===//
3//
4// The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_BITSET
12#define _LIBCPP_BITSET
13
14/*
15 bitset synopsis
16
17namespace std
18{
19
20namespace std {
21
22template <size_t N>
23class bitset
24{
25public:
26 // bit reference:
27 class reference
28 {
29 friend class bitset;
30 reference() noexcept;
31 public:
32 ~reference() noexcept;
33 reference& operator=(bool x) noexcept; // for b[i] = x;
34 reference& operator=(const reference&) noexcept; // for b[i] = b[j];
35 bool operator~() const noexcept; // flips the bit
36 operator bool() const noexcept; // for x = b[i];
37 reference& flip() noexcept; // for b[i].flip();
38 };
39
40 // 23.3.5.1 constructors:
41 constexpr bitset() noexcept;
42 constexpr bitset(unsigned long long val) noexcept;
43 template <class charT>
44 explicit bitset(const charT* str,
45 typename basic_string<charT>::size_type n = basic_string<charT>::npos,
46 charT zero = charT('0'), charT one = charT('1'));
47 template<class charT, class traits, class Allocator>
48 explicit bitset(const basic_string<charT,traits,Allocator>& str,
49 typename basic_string<charT,traits,Allocator>::size_type pos = 0,
50 typename basic_string<charT,traits,Allocator>::size_type n =
51 basic_string<charT,traits,Allocator>::npos,
52 charT zero = charT('0'), charT one = charT('1'));
53
54 // 23.3.5.2 bitset operations:
55 bitset& operator&=(const bitset& rhs) noexcept;
56 bitset& operator|=(const bitset& rhs) noexcept;
57 bitset& operator^=(const bitset& rhs) noexcept;
58 bitset& operator<<=(size_t pos) noexcept;
59 bitset& operator>>=(size_t pos) noexcept;
60 bitset& set() noexcept;
61 bitset& set(size_t pos, bool val = true);
62 bitset& reset() noexcept;
63 bitset& reset(size_t pos);
64 bitset operator~() const noexcept;
65 bitset& flip() noexcept;
66 bitset& flip(size_t pos);
67
68 // element access:
69 constexpr bool operator[](size_t pos) const; // for b[i];
70 reference operator[](size_t pos); // for b[i];
71 unsigned long to_ulong() const;
72 unsigned long long to_ullong() const;
73 template <class charT, class traits, class Allocator>
74 basic_string<charT, traits, Allocator> to_string(charT zero = charT('0'), charT one = charT('1')) const;
75 template <class charT, class traits>
76 basic_string<charT, traits, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const;
77 template <class charT>
78 basic_string<charT, char_traits<charT>, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const;
79 basic_string<char, char_traits<char>, allocator<char> > to_string(char zero = '0', char one = '1') const;
80 size_t count() const noexcept;
81 constexpr size_t size() const noexcept;
82 bool operator==(const bitset& rhs) const noexcept;
83 bool operator!=(const bitset& rhs) const noexcept;
84 bool test(size_t pos) const;
85 bool all() const noexcept;
86 bool any() const noexcept;
87 bool none() const noexcept;
88 bitset operator<<(size_t pos) const noexcept;
89 bitset operator>>(size_t pos) const noexcept;
90};
91
92// 23.3.5.3 bitset operators:
93template <size_t N>
94bitset<N> operator&(const bitset<N>&, const bitset<N>&) noexcept;
95
96template <size_t N>
97bitset<N> operator|(const bitset<N>&, const bitset<N>&) noexcept;
98
99template <size_t N>
100bitset<N> operator^(const bitset<N>&, const bitset<N>&) noexcept;
101
102template <class charT, class traits, size_t N>
103basic_istream<charT, traits>&
104operator>>(basic_istream<charT, traits>& is, bitset<N>& x);
105
106template <class charT, class traits, size_t N>
107basic_ostream<charT, traits>&
108operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x);
109
110template <size_t N> struct hash<std::bitset<N>>;
111
112} // std
113
114*/
115
116#include <__config>
117#include <__bit_reference>
118#include <cstddef>
119#include <climits>
120#include <string>
121#include <stdexcept>
122#include <iosfwd>
123#include <__functional_base>
124
125#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
126#pragma GCC system_header
127#endif
128
129_LIBCPP_PUSH_MACROS
130#include <__undef_macros>
131
132
133_LIBCPP_BEGIN_NAMESPACE_STD
134
135template <size_t _N_words, size_t _Size>
136class __bitset;
137
138template <size_t _N_words, size_t _Size>
139struct __has_storage_type<__bitset<_N_words, _Size> >
140{
141 static const bool value = true;
142};
143
144template <size_t _N_words, size_t _Size>
145class __bitset
146{
147public:
148 typedef ptrdiff_t difference_type;
149 typedef size_t size_type;
150 typedef size_type __storage_type;
151protected:
152 typedef __bitset __self;
153 typedef __storage_type* __storage_pointer;
154 typedef const __storage_type* __const_storage_pointer;
155 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
156
157 friend class __bit_reference<__bitset>;
158 friend class __bit_const_reference<__bitset>;
159 friend class __bit_iterator<__bitset, false>;
160 friend class __bit_iterator<__bitset, true>;
161 friend struct __bit_array<__bitset>;
162
163 __storage_type __first_[_N_words];
164
165 typedef __bit_reference<__bitset> reference;
166 typedef __bit_const_reference<__bitset> const_reference;
167 typedef __bit_iterator<__bitset, false> iterator;
168 typedef __bit_iterator<__bitset, true> const_iterator;
169
170 _LIBCPP_INLINE_VISIBILITY
171 _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
172 _LIBCPP_INLINE_VISIBILITY
173 explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long __v) _NOEXCEPT;
174
175 _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t __pos) _NOEXCEPT
176 {return reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
177 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t __pos) const _NOEXCEPT
178 {return const_reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
179 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) _NOEXCEPT
180 {return iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
181 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const _NOEXCEPT
182 {return const_iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
183
184 _LIBCPP_INLINE_VISIBILITY
185 void operator&=(const __bitset& __v) _NOEXCEPT;
186 _LIBCPP_INLINE_VISIBILITY
187 void operator|=(const __bitset& __v) _NOEXCEPT;
188 _LIBCPP_INLINE_VISIBILITY
189 void operator^=(const __bitset& __v) _NOEXCEPT;
190
191 void flip() _NOEXCEPT;
192 _LIBCPP_INLINE_VISIBILITY unsigned long to_ulong() const
193 {return to_ulong(integral_constant<bool, _Size < sizeof(unsigned long) * CHAR_BIT>());}
194 _LIBCPP_INLINE_VISIBILITY unsigned long long to_ullong() const
195 {return to_ullong(integral_constant<bool, _Size < sizeof(unsigned long long) * CHAR_BIT>());}
196
197 bool all() const _NOEXCEPT;
198 bool any() const _NOEXCEPT;
199 _LIBCPP_INLINE_VISIBILITY
200 size_t __hash_code() const _NOEXCEPT;
201private:
202#ifdef _LIBCPP_CXX03_LANG
203 void __init(unsigned long long __v, false_type) _NOEXCEPT;
204 _LIBCPP_INLINE_VISIBILITY
205 void __init(unsigned long long __v, true_type) _NOEXCEPT;
206#endif // _LIBCPP_CXX03_LANG
207 unsigned long to_ulong(false_type) const;
208 _LIBCPP_INLINE_VISIBILITY
209 unsigned long to_ulong(true_type) const;
210 unsigned long long to_ullong(false_type) const;
211 _LIBCPP_INLINE_VISIBILITY
212 unsigned long long to_ullong(true_type) const;
213 _LIBCPP_INLINE_VISIBILITY
214 unsigned long long to_ullong(true_type, false_type) const;
215 unsigned long long to_ullong(true_type, true_type) const;
216};
217
218template <size_t _N_words, size_t _Size>
219inline
220_LIBCPP_CONSTEXPR
221__bitset<_N_words, _Size>::__bitset() _NOEXCEPT
222#ifndef _LIBCPP_CXX03_LANG
223 : __first_{0}
224#endif
225{
226#ifdef _LIBCPP_CXX03_LANG
227 _VSTD::fill_n(__first_, _N_words, __storage_type(0));
228#endif
229}
230
231#ifdef _LIBCPP_CXX03_LANG
232
233template <size_t _N_words, size_t _Size>
234void
235__bitset<_N_words, _Size>::__init(unsigned long long __v, false_type) _NOEXCEPT
236{
237 __storage_type __t[sizeof(unsigned long long) / sizeof(__storage_type)];
238 for (size_t __i = 0; __i < sizeof(__t)/sizeof(__t[0]); ++__i, __v >>= __bits_per_word)
239 __t[__i] = static_cast<__storage_type>(__v);
240 _VSTD::copy(__t, __t + sizeof(__t)/sizeof(__t[0]), __first_);
241 _VSTD::fill(__first_ + sizeof(__t)/sizeof(__t[0]), __first_ + sizeof(__first_)/sizeof(__first_[0]),
242 __storage_type(0));
243}
244
245template <size_t _N_words, size_t _Size>
246inline _LIBCPP_INLINE_VISIBILITY
247void
248__bitset<_N_words, _Size>::__init(unsigned long long __v, true_type) _NOEXCEPT
249{
250 __first_[0] = __v;
251 _VSTD::fill(__first_ + 1, __first_ + sizeof(__first_)/sizeof(__first_[0]), __storage_type(0));
252}
253
254#endif // _LIBCPP_CXX03_LANG
255
256template <size_t _N_words, size_t _Size>
257inline
258_LIBCPP_CONSTEXPR
259__bitset<_N_words, _Size>::__bitset(unsigned long long __v) _NOEXCEPT
260#ifndef _LIBCPP_CXX03_LANG
261#if __SIZEOF_SIZE_T__ == 8
262 : __first_{__v}
263#elif __SIZEOF_SIZE_T__ == 4
264 : __first_{static_cast<__storage_type>(__v), static_cast<__storage_type>(__v >> __bits_per_word)}
265#else
266#error This constructor has not been ported to this platform
267#endif
268#endif
269{
270#ifdef _LIBCPP_CXX03_LANG
271 __init(__v, integral_constant<bool, sizeof(unsigned long long) == sizeof(__storage_type)>());
272#endif
273}
274
275template <size_t _N_words, size_t _Size>
276inline
277void
278__bitset<_N_words, _Size>::operator&=(const __bitset& __v) _NOEXCEPT
279{
280 for (size_type __i = 0; __i < _N_words; ++__i)
281 __first_[__i] &= __v.__first_[__i];
282}
283
284template <size_t _N_words, size_t _Size>
285inline
286void
287__bitset<_N_words, _Size>::operator|=(const __bitset& __v) _NOEXCEPT
288{
289 for (size_type __i = 0; __i < _N_words; ++__i)
290 __first_[__i] |= __v.__first_[__i];
291}
292
293template <size_t _N_words, size_t _Size>
294inline
295void
296__bitset<_N_words, _Size>::operator^=(const __bitset& __v) _NOEXCEPT
297{
298 for (size_type __i = 0; __i < _N_words; ++__i)
299 __first_[__i] ^= __v.__first_[__i];
300}
301
302template <size_t _N_words, size_t _Size>
303void
304__bitset<_N_words, _Size>::flip() _NOEXCEPT
305{
306 // do middle whole words
307 size_type __n = _Size;
308 __storage_pointer __p = __first_;
309 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
310 *__p = ~*__p;
311 // do last partial word
312 if (__n > 0)
313 {
314 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
315 __storage_type __b = *__p & __m;
316 *__p &= ~__m;
317 *__p |= ~__b & __m;
318 }
319}
320
321template <size_t _N_words, size_t _Size>
322unsigned long
323__bitset<_N_words, _Size>::to_ulong(false_type) const
324{
325 const_iterator __e = __make_iter(_Size);
326 const_iterator __i = _VSTD::find(__make_iter(sizeof(unsigned long) * CHAR_BIT), __e, true);
327 if (__i != __e)
328 __throw_overflow_error("bitset to_ulong overflow error");
329
330 return __first_[0];
331}
332
333template <size_t _N_words, size_t _Size>
334inline
335unsigned long
336__bitset<_N_words, _Size>::to_ulong(true_type) const
337{
338 return __first_[0];
339}
340
341template <size_t _N_words, size_t _Size>
342unsigned long long
343__bitset<_N_words, _Size>::to_ullong(false_type) const
344{
345 const_iterator __e = __make_iter(_Size);
346 const_iterator __i = _VSTD::find(__make_iter(sizeof(unsigned long long) * CHAR_BIT), __e, true);
347 if (__i != __e)
348 __throw_overflow_error("bitset to_ullong overflow error");
349
350 return to_ullong(true_type());
351}
352
353template <size_t _N_words, size_t _Size>
354inline
355unsigned long long
356__bitset<_N_words, _Size>::to_ullong(true_type) const
357{
358 return to_ullong(true_type(), integral_constant<bool, sizeof(__storage_type) < sizeof(unsigned long long)>());
359}
360
361template <size_t _N_words, size_t _Size>
362inline
363unsigned long long
364__bitset<_N_words, _Size>::to_ullong(true_type, false_type) const
365{
366 return __first_[0];
367}
368
369template <size_t _N_words, size_t _Size>
370unsigned long long
371__bitset<_N_words, _Size>::to_ullong(true_type, true_type) const
372{
373 unsigned long long __r = __first_[0];
374 for (std::size_t __i = 1; __i < sizeof(unsigned long long) / sizeof(__storage_type); ++__i)
375 __r |= static_cast<unsigned long long>(__first_[__i]) << (sizeof(__storage_type) * CHAR_BIT);
376 return __r;
377}
378
379template <size_t _N_words, size_t _Size>
380bool
381__bitset<_N_words, _Size>::all() const _NOEXCEPT
382{
383 // do middle whole words
384 size_type __n = _Size;
385 __const_storage_pointer __p = __first_;
386 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
387 if (~*__p)
388 return false;
389 // do last partial word
390 if (__n > 0)
391 {
392 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
393 if (~*__p & __m)
394 return false;
395 }
396 return true;
397}
398
399template <size_t _N_words, size_t _Size>
400bool
401__bitset<_N_words, _Size>::any() const _NOEXCEPT
402{
403 // do middle whole words
404 size_type __n = _Size;
405 __const_storage_pointer __p = __first_;
406 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
407 if (*__p)
408 return true;
409 // do last partial word
410 if (__n > 0)
411 {
412 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
413 if (*__p & __m)
414 return true;
415 }
416 return false;
417}
418
419template <size_t _N_words, size_t _Size>
420inline
421size_t
422__bitset<_N_words, _Size>::__hash_code() const _NOEXCEPT
423{
424 size_t __h = 0;
425 for (size_type __i = 0; __i < _N_words; ++__i)
426 __h ^= __first_[__i];
427 return __h;
428}
429
430template <size_t _Size>
431class __bitset<1, _Size>
432{
433public:
434 typedef ptrdiff_t difference_type;
435 typedef size_t size_type;
436 typedef size_type __storage_type;
437protected:
438 typedef __bitset __self;
439 typedef __storage_type* __storage_pointer;
440 typedef const __storage_type* __const_storage_pointer;
441 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
442
443 friend class __bit_reference<__bitset>;
444 friend class __bit_const_reference<__bitset>;
445 friend class __bit_iterator<__bitset, false>;
446 friend class __bit_iterator<__bitset, true>;
447 friend struct __bit_array<__bitset>;
448
449 __storage_type __first_;
450
451 typedef __bit_reference<__bitset> reference;
452 typedef __bit_const_reference<__bitset> const_reference;
453 typedef __bit_iterator<__bitset, false> iterator;
454 typedef __bit_iterator<__bitset, true> const_iterator;
455
456 _LIBCPP_INLINE_VISIBILITY
457 _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
458 _LIBCPP_INLINE_VISIBILITY
459 explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long __v) _NOEXCEPT;
460
461 _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t __pos) _NOEXCEPT
462 {return reference(&__first_, __storage_type(1) << __pos);}
463 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t __pos) const _NOEXCEPT
464 {return const_reference(&__first_, __storage_type(1) << __pos);}
465 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) _NOEXCEPT
466 {return iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
467 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const _NOEXCEPT
468 {return const_iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
469
470 _LIBCPP_INLINE_VISIBILITY
471 void operator&=(const __bitset& __v) _NOEXCEPT;
472 _LIBCPP_INLINE_VISIBILITY
473 void operator|=(const __bitset& __v) _NOEXCEPT;
474 _LIBCPP_INLINE_VISIBILITY
475 void operator^=(const __bitset& __v) _NOEXCEPT;
476
477 _LIBCPP_INLINE_VISIBILITY
478 void flip() _NOEXCEPT;
479
480 _LIBCPP_INLINE_VISIBILITY
481 unsigned long to_ulong() const;
482 _LIBCPP_INLINE_VISIBILITY
483 unsigned long long to_ullong() const;
484
485 _LIBCPP_INLINE_VISIBILITY
486 bool all() const _NOEXCEPT;
487 _LIBCPP_INLINE_VISIBILITY
488 bool any() const _NOEXCEPT;
489
490 _LIBCPP_INLINE_VISIBILITY
491 size_t __hash_code() const _NOEXCEPT;
492};
493
494template <size_t _Size>
495inline
496_LIBCPP_CONSTEXPR
497__bitset<1, _Size>::__bitset() _NOEXCEPT
498 : __first_(0)
499{
500}
501
502template <size_t _Size>
503inline
504_LIBCPP_CONSTEXPR
505__bitset<1, _Size>::__bitset(unsigned long long __v) _NOEXCEPT
506 : __first_(static_cast<__storage_type>(__v))
507{
508}
509
510template <size_t _Size>
511inline
512void
513__bitset<1, _Size>::operator&=(const __bitset& __v) _NOEXCEPT
514{
515 __first_ &= __v.__first_;
516}
517
518template <size_t _Size>
519inline
520void
521__bitset<1, _Size>::operator|=(const __bitset& __v) _NOEXCEPT
522{
523 __first_ |= __v.__first_;
524}
525
526template <size_t _Size>
527inline
528void
529__bitset<1, _Size>::operator^=(const __bitset& __v) _NOEXCEPT
530{
531 __first_ ^= __v.__first_;
532}
533
534template <size_t _Size>
535inline
536void
537__bitset<1, _Size>::flip() _NOEXCEPT
538{
539 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
540 __first_ = ~__first_;
541 __first_ &= __m;
542}
543
544template <size_t _Size>
545inline
546unsigned long
547__bitset<1, _Size>::to_ulong() const
548{
549 return __first_;
550}
551
552template <size_t _Size>
553inline
554unsigned long long
555__bitset<1, _Size>::to_ullong() const
556{
557 return __first_;
558}
559
560template <size_t _Size>
561inline
562bool
563__bitset<1, _Size>::all() const _NOEXCEPT
564{
565 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
566 return !(~__first_ & __m);
567}
568
569template <size_t _Size>
570inline
571bool
572__bitset<1, _Size>::any() const _NOEXCEPT
573{
574 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
575 return __first_ & __m;
576}
577
578template <size_t _Size>
579inline
580size_t
581__bitset<1, _Size>::__hash_code() const _NOEXCEPT
582{
583 return __first_;
584}
585
586template <>
587class __bitset<0, 0>
588{
589public:
590 typedef ptrdiff_t difference_type;
591 typedef size_t size_type;
592 typedef size_type __storage_type;
593protected:
594 typedef __bitset __self;
595 typedef __storage_type* __storage_pointer;
596 typedef const __storage_type* __const_storage_pointer;
597 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
598
599 friend class __bit_reference<__bitset>;
600 friend class __bit_const_reference<__bitset>;
601 friend class __bit_iterator<__bitset, false>;
602 friend class __bit_iterator<__bitset, true>;
603 friend struct __bit_array<__bitset>;
604
605 typedef __bit_reference<__bitset> reference;
606 typedef __bit_const_reference<__bitset> const_reference;
607 typedef __bit_iterator<__bitset, false> iterator;
608 typedef __bit_iterator<__bitset, true> const_iterator;
609
610 _LIBCPP_INLINE_VISIBILITY
611 _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
612 _LIBCPP_INLINE_VISIBILITY
613 explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long) _NOEXCEPT;
614
615 _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t) _NOEXCEPT
616 {return reference(0, 1);}
617 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t) const _NOEXCEPT
618 {return const_reference(0, 1);}
619 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t) _NOEXCEPT
620 {return iterator(0, 0);}
621 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t) const _NOEXCEPT
622 {return const_iterator(0, 0);}
623
624 _LIBCPP_INLINE_VISIBILITY void operator&=(const __bitset&) _NOEXCEPT {}
625 _LIBCPP_INLINE_VISIBILITY void operator|=(const __bitset&) _NOEXCEPT {}
626 _LIBCPP_INLINE_VISIBILITY void operator^=(const __bitset&) _NOEXCEPT {}
627
628 _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {}
629
630 _LIBCPP_INLINE_VISIBILITY unsigned long to_ulong() const {return 0;}
631 _LIBCPP_INLINE_VISIBILITY unsigned long long to_ullong() const {return 0;}
632
633 _LIBCPP_INLINE_VISIBILITY bool all() const _NOEXCEPT {return true;}
634 _LIBCPP_INLINE_VISIBILITY bool any() const _NOEXCEPT {return false;}
635
636 _LIBCPP_INLINE_VISIBILITY size_t __hash_code() const _NOEXCEPT {return 0;}
637};
638
639inline
640_LIBCPP_CONSTEXPR
641__bitset<0, 0>::__bitset() _NOEXCEPT
642{
643}
644
645inline
646_LIBCPP_CONSTEXPR
647__bitset<0, 0>::__bitset(unsigned long long) _NOEXCEPT
648{
649}
650
651template <size_t _Size> class _LIBCPP_TEMPLATE_VIS bitset;
652template <size_t _Size> struct hash<bitset<_Size> >;
653
654template <size_t _Size>
655class _LIBCPP_TEMPLATE_VIS bitset
656 : private __bitset<_Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1, _Size>
657{
658public:
659 static const unsigned __n_words = _Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1;
660 typedef __bitset<__n_words, _Size> base;
661
662public:
663 typedef typename base::reference reference;
664 typedef typename base::const_reference const_reference;
665
666 // 23.3.5.1 constructors:
667 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR bitset() _NOEXCEPT {}
668 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
669 bitset(unsigned long long __v) _NOEXCEPT : base(__v) {}
670 template<class _CharT>
671 explicit bitset(const _CharT* __str,
672 typename basic_string<_CharT>::size_type __n = basic_string<_CharT>::npos,
673 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'));
674 template<class _CharT, class _Traits, class _Allocator>
675 explicit bitset(const basic_string<_CharT,_Traits,_Allocator>& __str,
676 typename basic_string<_CharT,_Traits,_Allocator>::size_type __pos = 0,
677 typename basic_string<_CharT,_Traits,_Allocator>::size_type __n =
678 (basic_string<_CharT,_Traits,_Allocator>::npos),
679 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'));
680
681 // 23.3.5.2 bitset operations:
682 _LIBCPP_INLINE_VISIBILITY
683 bitset& operator&=(const bitset& __rhs) _NOEXCEPT;
684 _LIBCPP_INLINE_VISIBILITY
685 bitset& operator|=(const bitset& __rhs) _NOEXCEPT;
686 _LIBCPP_INLINE_VISIBILITY
687 bitset& operator^=(const bitset& __rhs) _NOEXCEPT;
688 bitset& operator<<=(size_t __pos) _NOEXCEPT;
689 bitset& operator>>=(size_t __pos) _NOEXCEPT;
690 _LIBCPP_INLINE_VISIBILITY
691 bitset& set() _NOEXCEPT;
692 bitset& set(size_t __pos, bool __val = true);
693 _LIBCPP_INLINE_VISIBILITY
694 bitset& reset() _NOEXCEPT;
695 bitset& reset(size_t __pos);
696 _LIBCPP_INLINE_VISIBILITY
697 bitset operator~() const _NOEXCEPT;
698 _LIBCPP_INLINE_VISIBILITY
699 bitset& flip() _NOEXCEPT;
700 bitset& flip(size_t __pos);
701
702 // element access:
703 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
704 const_reference operator[](size_t __p) const {return base::__make_ref(__p);}
705 _LIBCPP_INLINE_VISIBILITY reference operator[](size_t __p) {return base::__make_ref(__p);}
706 _LIBCPP_INLINE_VISIBILITY
707 unsigned long to_ulong() const;
708 _LIBCPP_INLINE_VISIBILITY
709 unsigned long long to_ullong() const;
710 template <class _CharT, class _Traits, class _Allocator>
711 basic_string<_CharT, _Traits, _Allocator> to_string(_CharT __zero = _CharT('0'),
712 _CharT __one = _CharT('1')) const;
713 template <class _CharT, class _Traits>
714 _LIBCPP_INLINE_VISIBILITY
715 basic_string<_CharT, _Traits, allocator<_CharT> > to_string(_CharT __zero = _CharT('0'),
716 _CharT __one = _CharT('1')) const;
717 template <class _CharT>
718 _LIBCPP_INLINE_VISIBILITY
719 basic_string<_CharT, char_traits<_CharT>, allocator<_CharT> > to_string(_CharT __zero = _CharT('0'),
720 _CharT __one = _CharT('1')) const;
721 _LIBCPP_INLINE_VISIBILITY
722 basic_string<char, char_traits<char>, allocator<char> > to_string(char __zero = '0',
723 char __one = '1') const;
724 _LIBCPP_INLINE_VISIBILITY
725 size_t count() const _NOEXCEPT;
726 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR size_t size() const _NOEXCEPT {return _Size;}
727 _LIBCPP_INLINE_VISIBILITY
728 bool operator==(const bitset& __rhs) const _NOEXCEPT;
729 _LIBCPP_INLINE_VISIBILITY
730 bool operator!=(const bitset& __rhs) const _NOEXCEPT;
731 bool test(size_t __pos) const;
732 _LIBCPP_INLINE_VISIBILITY
733 bool all() const _NOEXCEPT;
734 _LIBCPP_INLINE_VISIBILITY
735 bool any() const _NOEXCEPT;
736 _LIBCPP_INLINE_VISIBILITY bool none() const _NOEXCEPT {return !any();}
737 _LIBCPP_INLINE_VISIBILITY
738 bitset operator<<(size_t __pos) const _NOEXCEPT;
739 _LIBCPP_INLINE_VISIBILITY
740 bitset operator>>(size_t __pos) const _NOEXCEPT;
741
742private:
743
744 _LIBCPP_INLINE_VISIBILITY
745 size_t __hash_code() const _NOEXCEPT {return base::__hash_code();}
746
747 friend struct hash<bitset>;
748};
749
750template <size_t _Size>
751template<class _CharT>
752bitset<_Size>::bitset(const _CharT* __str,
753 typename basic_string<_CharT>::size_type __n,
754 _CharT __zero, _CharT __one)
755{
756 size_t __rlen = _VSTD::min(__n, char_traits<_CharT>::length(__str));
757 for (size_t __i = 0; __i < __rlen; ++__i)
758 if (__str[__i] != __zero && __str[__i] != __one)
759 __throw_invalid_argument("bitset string ctor has invalid argument");
760
761 size_t _Mp = _VSTD::min(__rlen, _Size);
762 size_t __i = 0;
763 for (; __i < _Mp; ++__i)
764 {
765 _CharT __c = __str[_Mp - 1 - __i];
766 if (__c == __zero)
767 (*this)[__i] = false;
768 else
769 (*this)[__i] = true;
770 }
771 _VSTD::fill(base::__make_iter(__i), base::__make_iter(_Size), false);
772}
773
774template <size_t _Size>
775template<class _CharT, class _Traits, class _Allocator>
776bitset<_Size>::bitset(const basic_string<_CharT,_Traits,_Allocator>& __str,
777 typename basic_string<_CharT,_Traits,_Allocator>::size_type __pos,
778 typename basic_string<_CharT,_Traits,_Allocator>::size_type __n,
779 _CharT __zero, _CharT __one)
780{
781 if (__pos > __str.size())
782 __throw_out_of_range("bitset string pos out of range");
783
784 size_t __rlen = _VSTD::min(__n, __str.size() - __pos);
785 for (size_t __i = __pos; __i < __pos + __rlen; ++__i)
786 if (!_Traits::eq(__str[__i], __zero) && !_Traits::eq(__str[__i], __one))
787 __throw_invalid_argument("bitset string ctor has invalid argument");
788
789 size_t _Mp = _VSTD::min(__rlen, _Size);
790 size_t __i = 0;
791 for (; __i < _Mp; ++__i)
792 {
793 _CharT __c = __str[__pos + _Mp - 1 - __i];
794 if (_Traits::eq(__c, __zero))
795 (*this)[__i] = false;
796 else
797 (*this)[__i] = true;
798 }
799 _VSTD::fill(base::__make_iter(__i), base::__make_iter(_Size), false);
800}
801
802template <size_t _Size>
803inline
804bitset<_Size>&
805bitset<_Size>::operator&=(const bitset& __rhs) _NOEXCEPT
806{
807 base::operator&=(__rhs);
808 return *this;
809}
810
811template <size_t _Size>
812inline
813bitset<_Size>&
814bitset<_Size>::operator|=(const bitset& __rhs) _NOEXCEPT
815{
816 base::operator|=(__rhs);
817 return *this;
818}
819
820template <size_t _Size>
821inline
822bitset<_Size>&
823bitset<_Size>::operator^=(const bitset& __rhs) _NOEXCEPT
824{
825 base::operator^=(__rhs);
826 return *this;
827}
828
829template <size_t _Size>
830bitset<_Size>&
831bitset<_Size>::operator<<=(size_t __pos) _NOEXCEPT
832{
833 __pos = _VSTD::min(__pos, _Size);
834 _VSTD::copy_backward(base::__make_iter(0), base::__make_iter(_Size - __pos), base::__make_iter(_Size));
835 _VSTD::fill_n(base::__make_iter(0), __pos, false);
836 return *this;
837}
838
839template <size_t _Size>
840bitset<_Size>&
841bitset<_Size>::operator>>=(size_t __pos) _NOEXCEPT
842{
843 __pos = _VSTD::min(__pos, _Size);
844 _VSTD::copy(base::__make_iter(__pos), base::__make_iter(_Size), base::__make_iter(0));
845 _VSTD::fill_n(base::__make_iter(_Size - __pos), __pos, false);
846 return *this;
847}
848
849template <size_t _Size>
850inline
851bitset<_Size>&
852bitset<_Size>::set() _NOEXCEPT
853{
854 _VSTD::fill_n(base::__make_iter(0), _Size, true);
855 return *this;
856}
857
858template <size_t _Size>
859bitset<_Size>&
860bitset<_Size>::set(size_t __pos, bool __val)
861{
862 if (__pos >= _Size)
863 __throw_out_of_range("bitset set argument out of range");
864
865 (*this)[__pos] = __val;
866 return *this;
867}
868
869template <size_t _Size>
870inline
871bitset<_Size>&
872bitset<_Size>::reset() _NOEXCEPT
873{
874 _VSTD::fill_n(base::__make_iter(0), _Size, false);
875 return *this;
876}
877
878template <size_t _Size>
879bitset<_Size>&
880bitset<_Size>::reset(size_t __pos)
881{
882 if (__pos >= _Size)
883 __throw_out_of_range("bitset reset argument out of range");
884
885 (*this)[__pos] = false;
886 return *this;
887}
888
889template <size_t _Size>
890inline
891bitset<_Size>
892bitset<_Size>::operator~() const _NOEXCEPT
893{
894 bitset __x(*this);
895 __x.flip();
896 return __x;
897}
898
899template <size_t _Size>
900inline
901bitset<_Size>&
902bitset<_Size>::flip() _NOEXCEPT
903{
904 base::flip();
905 return *this;
906}
907
908template <size_t _Size>
909bitset<_Size>&
910bitset<_Size>::flip(size_t __pos)
911{
912 if (__pos >= _Size)
913 __throw_out_of_range("bitset flip argument out of range");
914
915 reference r = base::__make_ref(__pos);
916 r = ~r;
917 return *this;
918}
919
920template <size_t _Size>
921inline
922unsigned long
923bitset<_Size>::to_ulong() const
924{
925 return base::to_ulong();
926}
927
928template <size_t _Size>
929inline
930unsigned long long
931bitset<_Size>::to_ullong() const
932{
933 return base::to_ullong();
934}
935
936template <size_t _Size>
937template <class _CharT, class _Traits, class _Allocator>
938basic_string<_CharT, _Traits, _Allocator>
939bitset<_Size>::to_string(_CharT __zero, _CharT __one) const
940{
941 basic_string<_CharT, _Traits, _Allocator> __r(_Size, __zero);
942 for (size_t __i = 0; __i < _Size; ++__i)
943 {
944 if ((*this)[__i])
945 __r[_Size - 1 - __i] = __one;
946 }
947 return __r;
948}
949
950template <size_t _Size>
951template <class _CharT, class _Traits>
952inline
953basic_string<_CharT, _Traits, allocator<_CharT> >
954bitset<_Size>::to_string(_CharT __zero, _CharT __one) const
955{
956 return to_string<_CharT, _Traits, allocator<_CharT> >(__zero, __one);
957}
958
959template <size_t _Size>
960template <class _CharT>
961inline
962basic_string<_CharT, char_traits<_CharT>, allocator<_CharT> >
963bitset<_Size>::to_string(_CharT __zero, _CharT __one) const
964{
965 return to_string<_CharT, char_traits<_CharT>, allocator<_CharT> >(__zero, __one);
966}
967
968template <size_t _Size>
969inline
970basic_string<char, char_traits<char>, allocator<char> >
971bitset<_Size>::to_string(char __zero, char __one) const
972{
973 return to_string<char, char_traits<char>, allocator<char> >(__zero, __one);
974}
975
976template <size_t _Size>
977inline
978size_t
979bitset<_Size>::count() const _NOEXCEPT
980{
981 return static_cast<size_t>(_VSTD::count(base::__make_iter(0), base::__make_iter(_Size), true));
982}
983
984template <size_t _Size>
985inline
986bool
987bitset<_Size>::operator==(const bitset& __rhs) const _NOEXCEPT
988{
989 return _VSTD::equal(base::__make_iter(0), base::__make_iter(_Size), __rhs.__make_iter(0));
990}
991
992template <size_t _Size>
993inline
994bool
995bitset<_Size>::operator!=(const bitset& __rhs) const _NOEXCEPT
996{
997 return !(*this == __rhs);
998}
999
1000template <size_t _Size>
1001bool
1002bitset<_Size>::test(size_t __pos) const
1003{
1004 if (__pos >= _Size)
1005 __throw_out_of_range("bitset test argument out of range");
1006
1007 return (*this)[__pos];
1008}
1009
1010template <size_t _Size>
1011inline
1012bool
1013bitset<_Size>::all() const _NOEXCEPT
1014{
1015 return base::all();
1016}
1017
1018template <size_t _Size>
1019inline
1020bool
1021bitset<_Size>::any() const _NOEXCEPT
1022{
1023 return base::any();
1024}
1025
1026template <size_t _Size>
1027inline
1028bitset<_Size>
1029bitset<_Size>::operator<<(size_t __pos) const _NOEXCEPT
1030{
1031 bitset __r = *this;
1032 __r <<= __pos;
1033 return __r;
1034}
1035
1036template <size_t _Size>
1037inline
1038bitset<_Size>
1039bitset<_Size>::operator>>(size_t __pos) const _NOEXCEPT
1040{
1041 bitset __r = *this;
1042 __r >>= __pos;
1043 return __r;
1044}
1045
1046template <size_t _Size>
1047inline _LIBCPP_INLINE_VISIBILITY
1048bitset<_Size>
1049operator&(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT
1050{
1051 bitset<_Size> __r = __x;
1052 __r &= __y;
1053 return __r;
1054}
1055
1056template <size_t _Size>
1057inline _LIBCPP_INLINE_VISIBILITY
1058bitset<_Size>
1059operator|(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT
1060{
1061 bitset<_Size> __r = __x;
1062 __r |= __y;
1063 return __r;
1064}
1065
1066template <size_t _Size>
1067inline _LIBCPP_INLINE_VISIBILITY
1068bitset<_Size>
1069operator^(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT
1070{
1071 bitset<_Size> __r = __x;
1072 __r ^= __y;
1073 return __r;
1074}
1075
1076template <size_t _Size>
1077struct _LIBCPP_TEMPLATE_VIS hash<bitset<_Size> >
1078 : public unary_function<bitset<_Size>, size_t>
1079{
1080 _LIBCPP_INLINE_VISIBILITY
1081 size_t operator()(const bitset<_Size>& __bs) const _NOEXCEPT
1082 {return __bs.__hash_code();}
1083};
1084
1085template <class _CharT, class _Traits, size_t _Size>
1086basic_istream<_CharT, _Traits>&
1087operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Size>& __x);
1088
1089template <class _CharT, class _Traits, size_t _Size>
1090basic_ostream<_CharT, _Traits>&
1091operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Size>& __x);
1092
1093_LIBCPP_END_NAMESPACE_STD
1094
1095_LIBCPP_POP_MACROS
1096
1097#endif // _LIBCPP_BITSET