home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / include / bitset < prev    next >
Text File  |  1998-06-16  |  7KB  |  264 lines
  1. // bitset standard header
  2.  
  3. #if     _MSC_VER > 1000
  4. #pragma once
  5. #endif
  6.  
  7. #ifndef _BITSET_
  8. #define _BITSET_
  9. #include <istream>
  10.  
  11. #ifdef  _MSC_VER
  12. #pragma pack(push,8)
  13. #endif  /* _MSC_VER */
  14.         // TEMPLATE CLASS bitset
  15. _STD_BEGIN
  16. template<size_t _N> class bitset {
  17.     typedef unsigned long _Ty;
  18. public:
  19.     typedef bool element_type;
  20.     class reference {
  21.     friend class bitset<_N>;
  22.     public:
  23.         reference& operator=(bool _X)
  24.             {_Pbs->set(_Off, _X);
  25.             return (*this); }
  26.         reference& operator=(const reference& _Bs)
  27.             {_Pbs->set(_Off, bool(_Bs));
  28.             return (*this); }
  29.         reference& flip()
  30.             {_Pbs->flip(_Off);
  31.             return (*this); }
  32.         bool operator~() const
  33.             {return (!_Pbs->test(_Off)); }
  34.         operator bool() const
  35.             {return (_Pbs->test(_Off)); }
  36.     private:
  37.         reference(bitset<_N>& _X, size_t _P)
  38.             : _Pbs(&_X), _Off(_P) {}
  39.         bitset<_N> *_Pbs;
  40.         size_t _Off;
  41.         };
  42.     _STCONS(size_t, bitset_size, _N);
  43.     bool at(size_t _P) const
  44.         {if (_N <= _P)
  45.             _Xran();
  46.         return (test(_P)); }
  47.     reference at(size_t _P)
  48.         {if (_N <= _P)
  49.             _Xran();
  50.         return (reference(*this, _P)); }
  51.     bool operator[](size_t _P) const
  52.         {return (test(_P)); }
  53.     reference operator[](size_t _P)
  54.         {return (reference(*this, _P)); }
  55.     bitset()
  56.         {_Tidy(); }
  57.     bitset(unsigned long _X)
  58.         {_Tidy();
  59.         for (size_t _P = 0; _X != 0 && _P < _N; _X >>= 1, ++_P)
  60.             if (_X & 1)
  61.                 set(_P); }
  62.     explicit bitset(const string& _S, size_t _P = 0,
  63.         size_t _L = (size_t)(-1))
  64.         {size_t _I;
  65.         if (_S.size() < _P)
  66.             _Xran();
  67.         if (_S.size() - _P < _L)
  68.             _L = _S.size() - _P;
  69.         if (_N < _L)
  70.             _L = _N;
  71.         _Tidy(), _P += _L;
  72.         for (_I = 0; _I < _L; ++_I)
  73.             if (_S[--_P] == '1')
  74.                 set(_I);
  75.             else if (_S[_P] != '0')
  76.                 _Xinv(); }
  77.     bitset<_N>& operator&=(const bitset<_N>& _R)
  78.         {for (int _I = _Nw; 0 <= _I; --_I)
  79.             _A[_I] &= _R._W(_I);
  80.         return (*this); }
  81.     bitset<_N>& operator|=(const bitset<_N>& _R)
  82.         {for (int _I = _Nw; 0 <= _I; --_I)
  83.             _A[_I] |= _R._W(_I);
  84.         return (*this); }
  85.     bitset<_N>& operator^=(const bitset<_N>& _R)
  86.         {for (int _I = _Nw; 0 <= _I; --_I)
  87.             _A[_I] ^= _R._W(_I);
  88.         return (*this); }
  89.     bitset<_N>& operator<<=(size_t _P)
  90.         {if (_P < 0)
  91.             return (*this >>= -_P);
  92.         const int _D = _P / _Nb;
  93.         if (_D != 0)
  94.             for (int _I = _Nw; 0 <= _I; --_I)
  95.                 _A[_I] = _D <= _I ? _A[_I - _D] : 0;
  96.         if ((_P %= _Nb) != 0)
  97.             {for (int _I = _Nw; 0 < _I; --_I)
  98.                 _A[_I] = (_A[_I] << _P)
  99.                     | (_A[_I - 1] >> (_Nb - _P));
  100.             _A[0] <<= _P, _Trim(); }
  101.         return (*this); }
  102.     bitset<_N>& operator>>=(size_t _P)
  103.         {if (_P < 0)
  104.             return (*this <<= -_P);
  105.         const int _D = _P / _Nb;
  106.         if (_D != 0)
  107.             for (int _I = 0; _I <= _Nw; ++_I)
  108.                 _A[_I] = _D <= _Nw - _I ? _A[_I + _D] : 0;
  109.         if ((_P %= _Nb) != 0)
  110.             {for (int _I = 0; _I < _Nw; ++_I)
  111.                 _A[_I] = (_A[_I] >> _P)
  112.                     | (_A[_I + 1] << (_Nb - _P));
  113.             _A[_Nw] >>= _P; }
  114.         return (*this); }
  115.     bitset<_N>& set()
  116.         {_Tidy(~(_Ty)0);
  117.         return (*this); }
  118.     bitset<_N>& set(size_t _P, bool _X = true)
  119.         {if (_N <= _P)
  120.             _Xran();
  121.         if (_X)
  122.             _A[_P / _Nb] |= (_Ty)1 << _P % _Nb;
  123.         else
  124.             _A[_P / _Nb] &= ~((_Ty)1 << _P % _Nb);
  125.         return (*this); }
  126.     bitset<_N>& reset()
  127.         {_Tidy();
  128.         return (*this); }
  129.     bitset<_N>& reset(size_t _P)
  130.         {return (set(_P, 0)); }
  131.     bitset<_N> operator~() const
  132.         {return (bitset<_N>(*this).flip()); }
  133.     bitset<_N>& flip()
  134.         {for (int _I = _Nw; 0 <= _I; --_I)
  135.             _A[_I] = ~_A[_I];
  136.         _Trim();
  137.         return (*this); }
  138.     bitset<_N>& flip(size_t _P)
  139.         {if (_N <= _P)
  140.             _Xran();
  141.         _A[_P / _Nb] ^= (_Ty)1 << _P % _Nb;
  142.         return (*this); }
  143.     unsigned long to_ulong() const
  144.         {enum {_Assertion = 1 /
  145.             (sizeof (unsigned long) % sizeof (_Ty) == 0)};
  146.         int _I = _Nw;
  147.         for (; sizeof (unsigned long) / sizeof (_Ty) <= _I; --_I)
  148.             if (_A[_I] != 0)
  149.                 _Xoflo();
  150.         unsigned long _V = _A[_I];
  151.         for (; 0 <= --_I; )
  152.             _V = _V << _Nb | _A[_I];
  153.         return (_V); }
  154.     string to_string() const
  155.         {string _S;
  156.         _S.reserve(_N);
  157.         for (size_t _P = _N; 0 < _P; )
  158.             _S += test(--_P) ? '1' : '0';
  159.         return (_S); }
  160.     size_t count() const
  161.         {size_t _V = 0;
  162.         for (int _I = _Nw; 0 <= _I; --_I)
  163.             for (_Ty _X = _A[_I]; _X != 0; _X >>= 4)
  164.                 _V += "\0\1\1\2\1\2\2\3"
  165.                     "\1\2\2\3\2\3\3\4"[_X & 0xF];
  166.         return (_V); }
  167.     size_t size() const
  168.         {return (_N); }
  169.     bool operator==(const bitset<_N>& _R) const
  170.         {for (int _I = _Nw; 0 <= _I; --_I)
  171.             if (_A[_I] != _R._W(_I))
  172.                 return (false);
  173.         return (true); }
  174.     bool operator!=(const bitset<_N>& _R) const
  175.         {return (!(*this == _R)); }
  176.     bool test(size_t _P) const
  177.         {if (_N <= _P)
  178.             _Xran();
  179.         return ((_A[_P / _Nb] & ((_Ty)1 << _P % _Nb)) != 0); }
  180.     bool any() const
  181.         {for (int _I = _Nw; 0 <= _I; --_I)
  182.             if (_A[_I] != 0)
  183.                 return (true);
  184.         return (false); }
  185.     bool none() const
  186.         {return (!any()); }
  187.     bitset<_N> operator<<(size_t _R) const
  188.         {return (bitset<_N>(*this) <<= _R); }
  189.     bitset<_N> operator>>(size_t _R) const
  190.         {return (bitset<_N>(*this) >>= _R); }
  191.     friend bitset<_N> operator&(const bitset<_N>& _L,
  192.         const bitset<_N>& _R)
  193.         {return (bitset<_N>(_L) &= _R); }
  194.     friend bitset<_N> operator|(const bitset<_N>& _L,
  195.         const bitset<_N>& _R)
  196.         {return (bitset<_N>(_L) |= _R); }
  197.     friend bitset<_N> operator^(const bitset<_N>& _L,
  198.         const bitset<_N>& _R)
  199.         {return (bitset<_N>(_L) ^= _R); }
  200.     friend ostream& operator<<(ostream& _O, const bitset<_N>& _R)
  201.     {for (size_t _P = _N; 0 < _P; )
  202.         _O << (_R.test(--_P) ? '1' : '0');
  203.     return (_O); }
  204.         // TEMPLATE operator>>
  205.     friend istream& operator>>(istream& _I, bitset<_N>& _R)
  206.     {ios_base::iostate _St = ios_base::goodbit;
  207.     bool _Chg = false;
  208.     string _X;
  209.     const istream::sentry _Ok(_I);
  210.     if (_Ok)
  211.         {_TRY_IO_BEGIN
  212.         int _C = _I.rdbuf()->sgetc();
  213.         for (size_t _M = _R.size(); 0 < _M;
  214.             _C = _I.rdbuf()->snextc(), --_M)
  215.             {if (_C == EOF)
  216.                 {_St |= ios_base::eofbit;
  217.                 break; }
  218.             else if (_C != '0' && _C != '1')
  219.                 break;
  220.             else if (_X.max_size() <= _X.size())
  221.                 {_St |= ios_base::failbit;
  222.                 break; }
  223.             else
  224.                 _X.append(1, (char)_C), _Chg = true; }
  225.         _CATCH_IO_(_I); }
  226.     if (!_Chg)
  227.         _St |= ios_base::failbit;
  228.     _I.setstate(_St);
  229.     _R = bitset<_N>(_X);
  230.     return (_I); }
  231.     _Ty _W(size_t _I) const
  232.         {return (_A[_I]); }
  233. private:
  234.     enum {_Nb = CHAR_BIT * sizeof (_Ty),
  235.         _Nw = _N == 0 ? 0 : (_N - 1) / _Nb};
  236.     void _Tidy(_Ty _X = 0)
  237.         {for (int _I = _Nw; 0 <= _I; --_I)
  238.             _A[_I] = _X;
  239.         if (_X != 0)
  240.             _Trim(); }
  241.     void _Trim()
  242.         {if (_N % _Nb != 0)
  243.             _A[_Nw] &= ((_Ty)1 << _N % _Nb) - 1; }
  244.     void _Xinv() const
  245.         {_THROW(invalid_argument, "invalid bitset<N> char"); }
  246.     void _Xoflo() const
  247.         {_THROW(overflow_error,
  248.             "bitset<N> conversion overflow"); }
  249.     void _Xran() const
  250.         {_THROW(out_of_range, "invalid bitset<N> position"); }
  251.     _Ty _A[_Nw + 1];
  252.     };
  253. _STD_END
  254. #ifdef  _MSC_VER
  255. #pragma pack(pop)
  256. #endif  /* _MSC_VER */
  257.  
  258. #endif /* _BITSET */
  259.  
  260. /*
  261.  * Copyright (c) 1994 by P.J. Plauger.  ALL RIGHTS RESERVED. 
  262.  * Consult your license regarding permissions and restrictions.
  263.  */
  264.