#ifndef __STD_BITS
#define __STD_BITS
//
//
//  Copyright Digital Equipment Corporation 1996. All rights reserved.
//
//  Restricted Rights: Use, duplication, or disclosure by the U.S.
//  Government is subject to restrictions as set forth in subparagraph
//  (c) (1) (ii) of DFARS 252.227-7013, or in FAR 52.227-19, or in FAR
//  52.227-14 Alt. III, as applicable.
//
//  This software is proprietary to and embodies the confidential
//  technology of Digital Equipment Corporation. Possession, use, or
//  copying of this software and media is authorized only pursuant to a
//  valid written license from Digital or an authorized sublicensor.
//
//

/***************************************************************************
 *
 * bitset - class bitset declaration
 *
 * $Id: bitset,v 1.68 1996/08/28 18:41:14 smithey Exp $
 *
 ***************************************************************************
 *
 * (c) Copyright 1994-1996 Rogue Wave Software, Inc.
 * ALL RIGHTS RESERVED
 *
 * The software and information contained herein are proprietary to, and
 * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
 * intends to preserve as trade secrets such software and information.
 * This software is furnished pursuant to a written license agreement and
 * may be used, copied, transmitted, and stored only in accordance with
 * the terms of such license and with the inclusion of the above copyright
 * notice.  This software and information or any other copies thereof may
 * not be provided or otherwise made available to any other person.
 *
 * Notwithstanding any other lease or license that may pertain to, or
 * accompany the delivery of, this computer software and information, the
 * rights of the Government regarding its use, reproduction and disclosure
 * are as set forth in Section 52.227-19 of the FARS Computer
 * Software-Restricted Rights clause.
 * 
 * Use, duplication, or disclosure by the Government is subject to
 * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
 * Technical Data and Computer Software clause at DFARS 252.227-7013.
 * Contractor/Manufacturer is Rogue Wave Software, Inc.,
 * P.O. Box 2328, Corvallis, Oregon 97339.
 *
 * This computer software and information is distributed with "restricted
 * rights."  Use, duplication or disclosure is subject to restrictions as
 * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
 * Computer Software-Restricted Rights (April 1985)."  If the Clause at
 * 18-52.227-74 "Rights in Data General" is specified in the contract,
 * then the "Alternate III" clause applies.
 *
 **************************************************************************/

#include <stdcomp>
#include <stddefs>

#ifndef _RWSTD_NO_NEW_HEADER
#include <climits>
#include <cstddef>
#else
#include <limits.h>
#include <stddef.h>
#endif

#ifdef __USE_STD_IOSTREAM
#include <iosfwd>
#else
class  ostream;
class  istream;
#endif

#ifndef _RWSTD_NO_EXCEPTIONS
#ifdef _RW_STD_EXCEPT
#include <stdexcept>
#endif
#endif

#ifndef _RWSTD_HEADER_REQUIRES_HPP
#include <string>
#else
#include <string.hpp>
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __save
#      pragma __environment __header_defaults
#   endif
#endif

#ifndef _RWSTD_NO_NAMESPACE 
namespace std {
#endif

#ifndef _RWSTD_BC5_ENUM_BUG
    #define NELEMENTS NumOfElems
#else
    #define NELEMENTS NumOfElems()
#endif /*_RWSTD_BC5_ENUM_BUG*/

//
// Exception error messages.
//
extern const char _RWSTDExportFunc(*) __rw_bitset_InvalidPosition;
extern const char _RWSTDExportFunc(*) __rw_bitset_InvalidCtorArgument;
extern const char _RWSTDExportFunc(*) __rw_bitset_ConversionOverflow;

template <size_t N>
class  bitset
{
  private:
    //
    // The type of array in which we store the bits.
    //
    typedef unsigned int VectorType;
    //
    // Number of bits in an array element.
    //
    enum { BitsPerChunk = CHAR_BIT*sizeof(unsigned int) };
    //
    // Number of array elements.
    //
#ifndef _RWSTD_BC5_ENUM_BUG
    enum { NumOfElems = N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk) };
#else
    int NumOfElems () const
    {
        return N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk);
    }
#endif /*_RWSTD_BC5_ENUM_BUG*/
    //
    // Number of bits in an unsigned long.
    //
    enum { BitsInUnsignedLong = CHAR_BIT*sizeof(unsigned long) };
    //
    // The array of bits.
    //
#ifndef _RWSTD_BC5_ENUM_BUG
    VectorType bits[NELEMENTS];
#else
    VectorType* bits;
#endif /*_RWSTD_BC5_ENUM_BUG*/

  protected:
    //
    // Is pos a valid bitset position?
    //
    bool valid_position (size_t pos) const _RWSTD_THROW_SPEC_NULL
    {
        return N > pos ? true : false;
    }
    //
    // Given a bit position `pos', returns the index into the appropriate
    // chunk in bits[] such that 0 <= index < BitsPerChunk.
    //
    unsigned long index (size_t pos) const _RWSTD_THROW_SPEC_NULL
    {
#if UINT_MAX == 256
        return 7 & pos;
#elif UINT_MAX == 65535
        return 15 & pos;
#elif UINT_MAX == 4294967295
        return 31 & pos;
#elif UINT_MAX == 18446744073709551616
        return 63 & pos;
#else
        return pos % BitsPerChunk;
#endif
    }

  public:

    typedef bool element_type;
#ifdef _RWSTD_MSC22_STATIC_INIT_BUG
    const size_t bitset_size;
#else
#ifndef _RWSTD_NO_STI_TEMPLATE
    static const size_t bitset_size = N;
#else
    static const size_t bitset_size;
#endif
#endif

    //
    // bit reference
    //
    class reference
    {
        friend class bitset<N>;
      private:
        bitset<N>& ref;
        size_t     pos;
        reference (bitset<N>& r, size_t p) _RWSTD_THROW_SPEC_NULL
            : ref(r), pos(p) {}
      public:
        ~reference() _RWSTD_THROW_SPEC_NULL {}
        //
        // for b[i] = x;
        //
        reference& operator= (bool val) _RWSTD_THROW_SPEC_NULL
        {
            ref.set(pos, val); return *this;
        }
        //
        // for b[i] = b[j];
        //
        reference& operator= (const reference& rhs) _RWSTD_THROW_SPEC_NULL
        {
            ref.set(pos, rhs.ref.test(rhs.pos)); return *this;
        }
        //
        // for x = ~b[i];
        //
        bool operator~ () const _RWSTD_THROW_SPEC_NULL { return !ref.test(pos);}
        //
        // for x = b[i];
        //
        operator bool () const _RWSTD_THROW_SPEC_NULL { return ref.test(pos); }
        //
        // flips the bit
        //
        reference& flip() _RWSTD_THROW_SPEC_NULL { ref.flip(pos); return *this;}
    };
    //
    // constructors
    //
    bitset () _RWSTD_THROW_SPEC((out_of_range, invalid_argument))
#ifdef _RWSTD_MSC22_STATIC_INIT_BUG
      : bitset_size(N)
#endif
    {
#ifndef _RWSTD_BC5_ENUM_BUG
        memset(bits, 0, sizeof(bits));
#else
        bits = new VectorType[NELEMENTS];
        //
        // TODO -- check for bits == 0 here?
        //
        memset(bits, 0, NELEMENTS*sizeof(VectorType));
#endif /*_RWSTD_BC5_ENUM_BUG*/
    }
    bitset (unsigned long val) _RWSTD_THROW_SPEC((out_of_range, invalid_argument))
#ifdef _RWSTD_MSC22_STATIC_INIT_BUG
      : bitset_size(N)
#endif
    {
        //
        // Initialize first M bit positions to the corresponding
        // bit values in val. M is the smaller of N and the value
        // CHAR_BIT * sizeof(unsigned long).
        //
#ifndef _RWSTD_BC5_ENUM_BUG
        memset(bits, 0, sizeof(bits));
#else
        bits = new VectorType[NELEMENTS];
        //
        // TODO -- check for bits == 0 here?
        //
        memset(bits, 0, NELEMENTS*sizeof(VectorType));
#endif /*_RWSTD_BC5_ENUM_BUG*/
        size_t M = N < BitsInUnsignedLong ? N : BitsInUnsignedLong;
        for (size_t i = 0; i < M; i++)
            if (val & (1UL << i))
                set(i);
    }
    _EXPLICIT bitset (const string& str,
                     size_t pos = 0,
                     size_t n = (size_t) -1)
                     _RWSTD_THROW_SPEC((out_of_range, invalid_argument));
    
    // We _EXPLICITly defined the copy constructor, though
    // WP 17.2.2.2 allows us to use the default generated one.
    //
    bitset (const bitset<N>& rhs) _RWSTD_THROW_SPEC((out_of_range, invalid_argument))
#ifdef _RWSTD_MSC22_STATIC_INIT_BUG
      : bitset_size(N)
#endif
    {
#ifndef _RWSTD_BC5_ENUM_BUG
        memcpy(bits, rhs.bits, sizeof(bits));
#else
        bits = new VectorType[NELEMENTS];
        //
        // TODO -- check for bits == 0 here?
        //
        memcpy(bits, rhs.bits, NELEMENTS*sizeof(VectorType));
#endif /*_RWSTD_BC5_ENUM_BUG*/
    }
    //
    // We _EXPLICITly defined the assignment, though
    // WP 17.2.2.2 allows us to use the default generated one.
    //
    bitset<N>& operator= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
    {
        if (!(this == &rhs))
#ifndef _RWSTD_BC5_ENUM_BUG
            memcpy(bits, rhs.bits, sizeof(bits));
#else
            memcpy(bits, rhs.bits, NELEMENTS*sizeof(VectorType));
#endif /*_RWSTD_BC5_ENUM_BUG*/
        return *this;
    }
#ifdef _RWSTD_BC5_ENUM_BUG
    ~bitset () _RWSTD_THROW_SPEC_NULL { delete [] bits; }
#endif
    //
    // bitset operations
    //
    bitset<N>& operator&= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
    {
        for (size_t i = 0; i < NELEMENTS; i++)
            bits[i] &= rhs.bits[i];
        return *this;
    }
    bitset<N>& operator|= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
    {
        for (size_t i = 0; i < NELEMENTS; i++)
            bits[i] |= rhs.bits[i];
        return *this;
    }
    bitset<N>& operator^= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
    {
        for (size_t i = 0; i < NELEMENTS; i++)
            bits[i] ^= rhs.bits[i];
        return *this;
    }
    //
    // Replaces bit at position I with a value determined as follows:
    //
    //   If (I <  pos) the new value is 0
    //   If (I >= pos) the new value is the previous value at position I - pos
    //
    bitset<N>& operator<<= (size_t pos) _RWSTD_THROW_SPEC_NULL
    {
        if (pos)
            for (long i = N - 1; i >= 0 ; --i)
                set(i, i < pos || test(i - pos) == 0 ? 0 : 1);
        return *this;
    }
    //
    // Replaces bit at position I with a value determined as follows:
    //
    //   If (pos >= N-i) the new value is zero
    //   If (pos <  N-i) the new value is the previous value at position I + pos
    //
    bitset<N>& operator>>= (size_t pos) _RWSTD_THROW_SPEC_NULL
    {
        if (pos)
            for (size_t i = 0; i < N; i++)
                set(i, pos >= N - i || test(i + pos) == 0 ? 0 : 1);
        return *this;
    }
    bitset<N>& set () _RWSTD_THROW_SPEC_NULL
    {
        for (size_t i = 0; i < NELEMENTS; i++)
            bits[i] = ~0;
        return *this;
    }
    bitset<N>& set (size_t pos, int val = 1) _RWSTD_THROW_SPEC((out_of_range))
    {
        _RWSTD_THROW(!valid_position(pos),
                    out_of_range,
                    __rw_bitset_InvalidPosition);
        if (val)
            bits[pos / BitsPerChunk] |=  (1UL << index(pos));
        else
            bits[pos / BitsPerChunk] &= ~(1UL << index(pos));
        return *this;
    }
    bitset<N>& reset () _RWSTD_THROW_SPEC_NULL
    {
        memset(bits, 0, sizeof(bits)); return *this;
    }
    bitset<N>& reset (size_t pos) _RWSTD_THROW_SPEC((out_of_range))
    {
        return set(pos, 0);
    }
    bitset<N> operator~ () const _RWSTD_THROW_SPEC_NULL
    {
        bitset<N> tmp(*this); return tmp.flip();
    }
    bitset<N>& flip () _RWSTD_THROW_SPEC_NULL
    {
        for (size_t i = 0; i < NELEMENTS; i++) 
            bits[i] = ~bits[i];
        return *this;
    }
    bitset<N>& flip (size_t pos) _RWSTD_THROW_SPEC((out_of_range))
    {
        _RWSTD_THROW(!valid_position(pos),
                    out_of_range,
                    __rw_bitset_InvalidPosition);
        bits[pos / BitsPerChunk] ^= (1UL << index(pos));
        return *this;
    }
    //
    // element access
    //
    reference operator[] (size_t pos) _RWSTD_THROW_SPEC((out_of_range))
    {
        //
        // We check that pos is valid here so that NONE of the reference
        // member functions need check.  This way ALL the reference member
        // functions can have empty throw specifications.
        //
        _RWSTD_THROW(!valid_position(pos),
                    out_of_range,
                    __rw_bitset_InvalidPosition);
        reference r(*this, pos); return r;
    }
    //
    // conversion functions
    //
    unsigned long  to_ulong  () const _RWSTD_THROW_SPEC((overflow_error));
    string         to_string () const;
    //
    // miscellaneous member functions
    //
    size_t count () const _RWSTD_THROW_SPEC_NULL;
    size_t size  () const _RWSTD_THROW_SPEC_NULL { return N; }
    bool operator== (const bitset<N>& rhs) const _RWSTD_THROW_SPEC_NULL
    {
        for (size_t i = 0; i+1 < NELEMENTS; i++)
            if (!(bits[i] == rhs.bits[i]))
                return false;
        for (size_t j = (NELEMENTS-1)*BitsPerChunk; j < N; j++)
            if (!(test(j) == rhs.test(j)))
                return false;
        return true;
    }
    bool operator!= (const bitset<N>& rhs) const _RWSTD_THROW_SPEC_NULL
    {
        return !(*this == rhs);
    }
    bool test (size_t pos) const _RWSTD_THROW_SPEC((out_of_range))
    {
        _RWSTD_THROW(!valid_position(pos),
                    out_of_range,
                    __rw_bitset_InvalidPosition);
        return (bits[pos / BitsPerChunk] & (1UL << index(pos))) != 0;
    }
    bool any () const _RWSTD_THROW_SPEC_NULL
    {
        bool flag = false;
        for (size_t i = 0; i+1 <= NELEMENTS && !flag; i++)
            if (bits[i])
                flag = true;
        return flag;
    }
    bool none () const _RWSTD_THROW_SPEC_NULL
    {
        bool flag = true;
        for (size_t i = 0; i+1 <= NELEMENTS && flag; i++)
            if (bits[i])
                flag = false;
        return flag;
    }
    bitset<N> operator<< (size_t pos) const _RWSTD_THROW_SPEC_NULL
    {
        bitset<N> tmp(*this); tmp <<= pos; return tmp;
    }
    bitset<N> operator>> (size_t pos) const _RWSTD_THROW_SPEC_NULL
    {
        bitset<N> tmp(*this); tmp >>= pos; return tmp;
    }
};


#ifndef _RWSTD_NO_NONTYPE_ARGS
template<size_t N>
inline bitset<N>  operator& (const bitset<N>& lhs,
                     const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
{
    bitset<N> tmp(lhs); tmp &= rhs; return tmp;
}

template<size_t N>
inline bitset<N>  operator| (const bitset<N>& lhs,
                     const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
{
    bitset<N> tmp(lhs); tmp |= rhs; return tmp;
}

template<size_t N>
inline bitset<N>  operator^ (const bitset<N>& lhs,
                     const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
{
    bitset<N> tmp(lhs); tmp ^= rhs; return tmp;
}

template<size_t N> inline ostream&  operator<< (ostream& os, const bitset<N>& x)
{
    return os << x.to_string();
}

template <size_t N>
istream&  operator>> (istream& is, bitset<N>& x);

#endif  /* _RWSTD_NO_NONTYPE_ARGS */

#undef NELEMENTS

#ifndef _RWSTD_NO_NAMESPACE
} 
#endif

#if defined(_RWSTD_NO_DESTROY_BUILTIN) || defined(_RWSTD_NO_DESTROY_NONBUILTIN)
#ifndef _RWSTD_NO_NONTYPE_ARGS

#ifndef _RWSTD_NO_NAMESPACE
namespace __rogue_wave_std {
#endif
//
// Specializations of STL destroy for bitset.
//
template <size_t N> inline void __destroy (bitset<N>**)   {;}
template <size_t N> inline void __destroy (bitset<N>***)  {;}
template <size_t N> inline void __destroy (bitset<N>****) {;}

#ifndef _RWSTD_NO_NAMESPACE
} 
#endif
#endif
#endif

#ifdef _RWSTD_COMPILE_INSTANTIATE
#include <bitset.cc>
#endif
      
#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __restore
#   endif
#endif

#endif /*__STD_BITS*/