bitset 33 KB

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