// -*- C++ -*-
//===---------------------------- bitset ----------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_BITSET
#define _LIBCPP_BITSET

/*
    bitset synopsis

namespace std
{

namespace std {

template <size_t N>
class bitset
{
public:
    // bit reference:
    class reference
    {
        friend class bitset;
        reference() noexcept;
    public:
        ~reference() noexcept;
        reference& operator=(bool x) noexcept;           // for b[i] = x;
        reference& operator=(const reference&) noexcept; // for b[i] = b[j];
        bool operator~() const noexcept;                 // flips the bit
        operator bool() const noexcept;                  // for x = b[i];
        reference& flip() noexcept;                      // for b[i].flip();
    };

    // 23.3.5.1 constructors:
    constexpr bitset() noexcept;
    constexpr bitset(unsigned long long val) noexcept;
    template <class charT>
        explicit bitset(const charT* str,
                        typename basic_string<charT>::size_type n = basic_string<charT>::npos,
                        charT zero = charT('0'), charT one = charT('1'));
    template<class charT, class traits, class Allocator>
        explicit bitset(const basic_string<charT,traits,Allocator>& str,
                        typename basic_string<charT,traits,Allocator>::size_type pos = 0,
                        typename basic_string<charT,traits,Allocator>::size_type n =
                                 basic_string<charT,traits,Allocator>::npos,
                        charT zero = charT('0'), charT one = charT('1'));

    // 23.3.5.2 bitset operations:
    bitset& operator&=(const bitset& rhs) noexcept;
    bitset& operator|=(const bitset& rhs) noexcept;
    bitset& operator^=(const bitset& rhs) noexcept;
    bitset& operator<<=(size_t pos) noexcept;
    bitset& operator>>=(size_t pos) noexcept;
    bitset& set() noexcept;
    bitset& set(size_t pos, bool val = true);
    bitset& reset() noexcept;
    bitset& reset(size_t pos);
    bitset operator~() const noexcept;
    bitset& flip() noexcept;
    bitset& flip(size_t pos);

    // element access:
    constexpr bool operator[](size_t pos) const; // for b[i];
    reference operator[](size_t pos);            // for b[i];
    unsigned long to_ulong() const;
    unsigned long long to_ullong() const;
    template <class charT, class traits, class Allocator>
        basic_string<charT, traits, Allocator> to_string(charT zero = charT('0'), charT one = charT('1')) const;
    template <class charT, class traits>
        basic_string<charT, traits, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const;
    template <class charT>
        basic_string<charT, char_traits<charT>, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const;
    basic_string<char, char_traits<char>, allocator<char> > to_string(char zero = '0', char one = '1') const;
    size_t count() const noexcept;
    constexpr size_t size() const noexcept;
    bool operator==(const bitset& rhs) const noexcept;
    bool operator!=(const bitset& rhs) const noexcept;
    bool test(size_t pos) const;
    bool all() const noexcept;
    bool any() const noexcept;
    bool none() const noexcept;
    bitset operator<<(size_t pos) const noexcept;
    bitset operator>>(size_t pos) const noexcept;
};

// 23.3.5.3 bitset operators:
template <size_t N>
bitset<N> operator&(const bitset<N>&, const bitset<N>&) noexcept;

template <size_t N>
bitset<N> operator|(const bitset<N>&, const bitset<N>&) noexcept;

template <size_t N>
bitset<N> operator^(const bitset<N>&, const bitset<N>&) noexcept;

template <class charT, class traits, size_t N>
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is, bitset<N>& x);

template <class charT, class traits, size_t N>
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x);

template <size_t N> struct hash<std::bitset<N>>;

}  // std

*/

#include <__config>
#include <__bit_reference>
#include <__functional_base>
#include <climits>
#include <cstddef>
#include <iosfwd>
#include <stdexcept>
#include <string>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header
#endif

_LIBCPP_PUSH_MACROS
#include <__undef_macros>


_LIBCPP_BEGIN_NAMESPACE_STD

template <size_t _N_words, size_t _Size>
class __bitset;

template <size_t _N_words, size_t _Size>
struct __has_storage_type<__bitset<_N_words, _Size> >
{
    static const bool value = true;
};

template <size_t _N_words, size_t _Size>
class __bitset
{
public:
    typedef ptrdiff_t              difference_type;
    typedef size_t                 size_type;
    typedef size_type              __storage_type;
protected:
    typedef __bitset __self;
    typedef       __storage_type*  __storage_pointer;
    typedef const __storage_type*  __const_storage_pointer;
    static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);

    friend class __bit_reference<__bitset>;
    friend class __bit_const_reference<__bitset>;
    friend class __bit_iterator<__bitset, false>;
    friend class __bit_iterator<__bitset, true>;
    friend struct __bit_array<__bitset>;

    __storage_type __first_[_N_words];

    typedef __bit_reference<__bitset>                  reference;
    typedef __bit_const_reference<__bitset>            const_reference;
    typedef __bit_iterator<__bitset, false>            iterator;
    typedef __bit_iterator<__bitset, true>             const_iterator;

    _LIBCPP_INLINE_VISIBILITY
    _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
    _LIBCPP_INLINE_VISIBILITY
    explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long __v) _NOEXCEPT;

    _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t __pos) _NOEXCEPT
        {return reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t __pos) const _NOEXCEPT
        {return const_reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
    _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) _NOEXCEPT
        {return iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
    _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const _NOEXCEPT
        {return const_iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}

    _LIBCPP_INLINE_VISIBILITY
    void operator&=(const __bitset& __v) _NOEXCEPT;
    _LIBCPP_INLINE_VISIBILITY
    void operator|=(const __bitset& __v) _NOEXCEPT;
    _LIBCPP_INLINE_VISIBILITY
    void operator^=(const __bitset& __v) _NOEXCEPT;

    void flip() _NOEXCEPT;
    _LIBCPP_INLINE_VISIBILITY unsigned long to_ulong() const
        {return to_ulong(integral_constant<bool, _Size < sizeof(unsigned long) * CHAR_BIT>());}
    _LIBCPP_INLINE_VISIBILITY unsigned long long to_ullong() const
        {return to_ullong(integral_constant<bool, _Size < sizeof(unsigned long long) * CHAR_BIT>());}

    bool all() const _NOEXCEPT;
    bool any() const _NOEXCEPT;
    _LIBCPP_INLINE_VISIBILITY
    size_t __hash_code() const _NOEXCEPT;
private:
#ifdef _LIBCPP_CXX03_LANG
    void __init(unsigned long long __v, false_type) _NOEXCEPT;
    _LIBCPP_INLINE_VISIBILITY
    void __init(unsigned long long __v, true_type) _NOEXCEPT;
#endif // _LIBCPP_CXX03_LANG
    unsigned long to_ulong(false_type) const;
    _LIBCPP_INLINE_VISIBILITY
    unsigned long to_ulong(true_type) const;
    unsigned long long to_ullong(false_type) const;
    _LIBCPP_INLINE_VISIBILITY
    unsigned long long to_ullong(true_type) const;
    _LIBCPP_INLINE_VISIBILITY
    unsigned long long to_ullong(true_type, false_type) const;
    unsigned long long to_ullong(true_type, true_type) const;
};

template <size_t _N_words, size_t _Size>
inline
_LIBCPP_CONSTEXPR
__bitset<_N_words, _Size>::__bitset() _NOEXCEPT
#ifndef _LIBCPP_CXX03_LANG
    : __first_{0}
#endif
{
#ifdef _LIBCPP_CXX03_LANG
    _VSTD::fill_n(__first_, _N_words, __storage_type(0));
#endif
}

#ifdef _LIBCPP_CXX03_LANG

template <size_t _N_words, size_t _Size>
void
__bitset<_N_words, _Size>::__init(unsigned long long __v, false_type) _NOEXCEPT
{
    __storage_type __t[sizeof(unsigned long long) / sizeof(__storage_type)];
    size_t __sz = _Size;
    for (size_t __i = 0; __i < sizeof(__t)/sizeof(__t[0]); ++__i, __v >>= __bits_per_word, __sz -= __bits_per_word )
        if ( __sz < __bits_per_word)
            __t[__i] = static_cast<__storage_type>(__v) & ( 1ULL << __sz ) - 1;
        else
            __t[__i] = static_cast<__storage_type>(__v);

    _VSTD::copy(__t, __t + sizeof(__t)/sizeof(__t[0]), __first_);
    _VSTD::fill(__first_ + sizeof(__t)/sizeof(__t[0]), __first_ + sizeof(__first_)/sizeof(__first_[0]),
               __storage_type(0));
}

template <size_t _N_words, size_t _Size>
inline _LIBCPP_INLINE_VISIBILITY
void
__bitset<_N_words, _Size>::__init(unsigned long long __v, true_type) _NOEXCEPT
{
    __first_[0] = __v;
    if (_Size < __bits_per_word)
        __first_[0] &= ( 1ULL << _Size ) - 1;

    _VSTD::fill(__first_ + 1, __first_ + sizeof(__first_)/sizeof(__first_[0]), __storage_type(0));
}

#endif // _LIBCPP_CXX03_LANG

template <size_t _N_words, size_t _Size>
inline
_LIBCPP_CONSTEXPR
__bitset<_N_words, _Size>::__bitset(unsigned long long __v) _NOEXCEPT
#ifndef _LIBCPP_CXX03_LANG
#if _                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               