// <bitset> -*- C++ -*-

// Copyright (C) 2001-2026 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/*
 * Copyright (c) 1998
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file include/bitset
 *  This is a Standard C++ Library header.
 */

#ifndef _GLIBCXX_BITSET
#define _GLIBCXX_BITSET 1

#ifdef _GLIBCXX_SYSHDR
#pragma GCC system_header
#endif

#include <bits/stdexcept_throw.h> // For invalid_argument, out_of_range,
				  // overflow_error
#include <bits/stl_algobase.h>  // For std::fill

#if _GLIBCXX_HOSTED
# include <string>
# include <iosfwd>
# include <bits/cxxabi_forced.h>
#endif

#if __cplusplus >= 201103L
# include <bits/functional_hash.h>
#endif

#define __glibcxx_want_constexpr_bitset
#define __glibcxx_want_bitset  // ...construct from string_view
#include <bits/version.h>

#ifdef __cpp_lib_bitset // ...construct from string_view
# include <string_view>
#endif

#define _GLIBCXX_BITSET_BITS_PER_WORD  (__CHAR_BIT__ * __SIZEOF_LONG__)
#define _GLIBCXX_BITSET_WORDS(__n) \
  ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \
   ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1))

#define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__)

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

  /**
   *  Base class, general case.  It is a class invariant that _Nw will be
   *  nonnegative.
   *
   *  See documentation for bitset.
  */
  template<size_t _Nw>
    struct _Base_bitset
    {
      typedef unsigned long _WordT;

      /// 0 is the least significant word.
      _WordT 		_M_w[_Nw];

      _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
      : _M_w() { }

#if __cplusplus >= 201103L
      constexpr _Base_bitset(unsigned long long __val) noexcept
      : _M_w{ _WordT(__val)
#if __SIZEOF_LONG_LONG__ > __SIZEOF_LONG__
	       , _WordT(__val >> _GLIBCXX_BITSET_BITS_PER_WORD)
#endif
       } { }
#else
      _Base_bitset(unsigned long __val)
      : _M_w()
      { _M_w[0] = __val; }
#endif

      static _GLIBCXX_CONSTEXPR size_t
      _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
      { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }

      static _GLIBCXX_CONSTEXPR size_t
      _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
      { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }

      static _GLIBCXX_CONSTEXPR size_t
      _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
      { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }

      static _GLIBCXX_CONSTEXPR _WordT
      _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
      { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }

      _GLIBCXX14_CONSTEXPR _WordT&
      _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT
      { return _M_w[_S_whichword(__pos)]; }

      _GLIBCXX_CONSTEXPR _WordT
      _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT
      { return _M_w[_S_whichword(__pos)]; }

#if __cplusplus >= 201103L
      constexpr const _WordT*
      _M_getdata() const noexcept
      { return _M_w; }
#endif

      _GLIBCXX23_CONSTEXPR _WordT&
      _M_hiword() _GLIBCXX_NOEXCEPT
      { return _M_w[_Nw - 1]; }

      _GLIBCXX_CONSTEXPR _WordT
      _M_hiword() const _GLIBCXX_NOEXCEPT
      { return _M_w[_Nw - 1]; }

      _GLIBCXX23_CONSTEXPR void
      _M_do_and(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] &= __x._M_w[__i];
      }

      _GLIBCXX14_CONSTEXPR void
      _M_do_or(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] |= __x._M_w[__i];
      }

      _GLIBCXX14_CONSTEXPR void
      _M_do_xor(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] ^= __x._M_w[__i];
      }

      _GLIBCXX14_CONSTEXPR void
      _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT;

      _GLIBCXX14_CONSTEXPR void
      _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT;

      _GLIBCXX14_CONSTEXPR void
      _M_do_flip() _GLIBCXX_NOEXCEPT
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] = ~_M_w[__i];
      }

      _GLIBCXX14_CONSTEXPR void
      _M_do_set() _GLIBCXX_NOEXCEPT
      {
#if __cplusplus >= 201402L
	if (__builtin_is_constant_evaluated())
	  {
	    for (_WordT& __w : _M_w)
	      __w = ~static_cast<_WordT>(0);;
	    return;
	  }
#endif
	__builtin_memset(_M_w, 0xFF, _Nw * sizeof(_WordT));
      }

      _GLIBCXX14_CONSTEXPR void
      _M_do_reset() _GLIBCXX_NOEXCEPT
      {
#if __cplusplus >= 201402L
	if (__builtin_is_constant_evaluated())
	  {
	    for (_WordT& __w : _M_w)
	      __w = 0;
	    return;
	  }
#endif
	__builtin_memset(_M_w, 0, _Nw * sizeof(_WordT));
      }

      _GLIBCXX14_CONSTEXPR bool
      _M_is_equal(const _Base_bitset<_Nw>& __x) const _GLIBCXX_NOEXCEPT
      {
#if __cplusplus >= 201402L
	if (__builtin_is_constant_evaluated())
	  {
	    for (size_t __i = 0; __i < _Nw; ++__i)
	      if (_M_w[__i] != __x._M_w[__i])
		return false;
	    return true;
	  }
#endif
	return !__builtin_memcmp(_M_w, __x._M_w, _Nw * sizeof(_WordT));
      }

      template<size_t _Nb>
        _GLIBCXX14_CONSTEXPR bool
        _M_are_all() const _GLIBCXX_NOEXCEPT
        {
	  for (size_t __i = 0; __i < _Nw - 1; __i++)
	    if (_M_w[__i] != ~static_cast<_WordT>(0))
	      return false;
	  return _M_hiword() == (~static_cast<_WordT>(0)
				 >> (_Nw * _GLIBCXX_BITSET_BITS_PER_WORD
				     - _Nb));
	}

      _GLIBCXX14_CONSTEXPR bool
      _M_is_any() const _GLIBCXX_NOEXCEPT
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  if (_M_w[__i] != static_cast<_WordT>(0))
	    return true;
	return false;
      }

      _GLIBCXX14_CONSTEXPR size_t
      _M_do_count() const _GLIBCXX_NOEXCEPT
      {
	size_t __result = 0;
	for (size_t __i = 0; __i < _Nw; __i++)
	  __result += __builtin_popcountl(_M_w[__i]);
	return __result;
      }

      _GLIBCXX14_CONSTEXPR unsigned long
      _M_do_to_ulong() const;

#if __cplusplus >= 201103L
      _GLIBCXX14_CONSTEXPR unsigned long long
      _M_do_to_ullong() const;
#endif

      // find first "on" bit
      _GLIBCXX14_CONSTEXPR size_t
      _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT;

      // find the next "on" bit that follows "prev"
      _GLIBCXX14_CONSTEXPR size_t
      _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT;
    };

  // Definitions of non-inline functions from _Base_bitset.
  template<size_t _Nw>
    _GLIBCXX14_CONSTEXPR void
    _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT
    {
      if (__builtin_expect(__shift != 0, 1))
	{
	  const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
	  const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;

	  if (__offset == 0)
	    for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
	      _M_w[                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            