home *** CD-ROM | disk | FTP | other *** search
/ PC Plus SuperCD (UK) 2000 May / PCP163A.iso / Runimage / Cbuilder4 / Include / BITSET.H < prev    next >
Encoding:
C/C++ Source or Header  |  1999-01-26  |  16.7 KB  |  552 lines
  1. #ifndef __BITSET_H
  2. #define __BITSET_H
  3. #pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig
  4. // -*- C++ -*-
  5. #ifndef __STD_BITS
  6. #define __STD_BITS
  7.  
  8. /***************************************************************************
  9.  *
  10.  * bitset - class bitset declaration
  11.  *
  12.  ***************************************************************************
  13.  *
  14.  * (c) Copyright 1994, 1998 Rogue Wave Software, Inc.
  15.  * ALL RIGHTS RESERVED
  16.  *
  17.  * The software and information contained herein are proprietary to, and
  18.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  19.  * intends to preserve as trade secrets such software and information.
  20.  * This software is furnished pursuant to a written license agreement and
  21.  * may be used, copied, transmitted, and stored only in accordance with
  22.  * the terms of such license and with the inclusion of the above copyright
  23.  * notice.  This software and information or any other copies thereof may
  24.  * not be provided or otherwise made available to any other person.
  25.  *
  26.  * Notwithstanding any other lease or license that may pertain to, or
  27.  * accompany the delivery of, this computer software and information, the
  28.  * rights of the Government regarding its use, reproduction and disclosure
  29.  * are as set forth in Section 52.227-19 of the FARS Computer
  30.  * Software-Restricted Rights clause.
  31.  * 
  32.  * Use, duplication, or disclosure by the Government is subject to
  33.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  34.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  35.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  36.  * P.O. Box 2328, Corvallis, Oregon 97339.
  37.  *
  38.  * This computer software and information is distributed with "restricted
  39.  * rights."  Use, duplication or disclosure is subject to restrictions as
  40.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  41.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  42.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  43.  * then the "Alternate III" clause applies.
  44.  *
  45.  **************************************************************************/
  46.  
  47. #include <stdcomp.h>
  48. #include <rw/stddefs.h>
  49. #include <rw/rwstderr.h>
  50.  
  51. #ifndef _RWSTD_NO_NEW_HEADER
  52. #include <climits>
  53. #include <cstddef>
  54. #else
  55. #include <limits.h>
  56. #include <stddef.h>
  57. #endif
  58.  
  59. #ifdef _RW_STD_IOSTREAM
  60. #include <iosfwd>
  61. #else
  62. class  ostream;
  63. class  istream;
  64. #endif
  65.  
  66. #ifndef _RWSTD_NO_EXCEPTIONS
  67. #ifdef _RW_STD_EXCEPT
  68. #include <stdexcept>
  69. #endif
  70. #endif
  71.  
  72. #include <string>
  73. #ifndef _RWSTD_BC5_ENUM_BUG
  74. #define _NELEMENTS NumOfElems
  75. #else
  76. #define _NELEMENTS NumOfElems()
  77. #endif /*_RWSTD_BC5_ENUM_BUG*/
  78.  
  79. #ifndef _RWSTD_NO_NAMESPACE
  80. namespace __rwstd {
  81. #endif
  82. //
  83. // Exception error messages.
  84. //
  85. #ifdef _RWSTD_LOCALIZED_ERRORS
  86.   extern const unsigned int _RWSTDExport __rw_bitset_InvalidPosition;
  87.   extern const unsigned int _RWSTDExport __rw_bitset_InvalidCtorArgument;
  88.   extern const unsigned int _RWSTDExport __rw_bitset_ConversionOverflow;
  89. #else
  90.   extern const char _RWSTDExportFunc(*) __rw_bitset_InvalidPosition;
  91.   extern const char _RWSTDExportFunc(*) __rw_bitset_InvalidCtorArgument;
  92.   extern const char _RWSTDExportFunc(*) __rw_bitset_ConversionOverflow;
  93. #endif//_RWSTD_LOCALIZED_ERRORS
  94.  
  95. #ifndef _RWSTD_NO_NAMESPACE
  96. } namespace std {
  97. #endif
  98.  
  99.   template <size_t N>
  100.   class _RWSTDExportTemplate bitset // RW_BUG: fix for bts-42913
  101.   {
  102.   private:
  103.     //
  104.     // The type of array in which we store the bits.
  105.     //
  106.     typedef unsigned int VectorType;
  107.     //
  108.     // Number of bits in an array element.
  109.     //
  110.     enum { BitsPerChunk = CHAR_BIT*sizeof(unsigned int) };
  111.     //
  112.     // Number of array elements.
  113.     //
  114. #ifndef _RWSTD_BC5_ENUM_BUG
  115.     enum { NumOfElems = N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk) };
  116. #else
  117.     size_t NumOfElems () const
  118.     {
  119.       return N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk);
  120.     }
  121. #endif /*_RWSTD_BC5_ENUM_BUG*/
  122.     //
  123.     // Number of bits in an unsigned long.
  124.     //
  125.     enum { BitsInUnsignedLong = CHAR_BIT*sizeof(unsigned long) };
  126.     //
  127.     // The array of bits.
  128.     //
  129. #ifndef _RWSTD_BC5_ENUM_BUG
  130.     VectorType bits[_NELEMENTS];
  131. #else
  132.     VectorType* bits;
  133. #endif /*_RWSTD_BC5_ENUM_BUG*/
  134.  
  135.   protected:
  136.     //
  137.     // Is pos a valid bitset position?
  138.     //
  139.     bool valid_position (size_t pos) const _RWSTD_THROW_SPEC_NULL
  140.     {
  141.       return N > pos ? true : false;
  142.     }
  143.     //
  144.     // Given a bit position `pos', returns the index into the appropriate
  145.     // chunk in bits[] such that 0 <= index < BitsPerChunk.
  146.     //
  147.     unsigned long index (size_t pos) const _RWSTD_THROW_SPEC_NULL
  148.     {
  149. #if UINT_MAX == 256
  150.       return 7 & pos;
  151. #elif UINT_MAX == 65535
  152.       return 15 & pos;
  153. #elif UINT_MAX == 4294967295
  154.       return 31 & pos;
  155. #elif UINT_MAX == 18446744073709551615
  156.       return 63 & pos;
  157. #else
  158.       return pos % BitsPerChunk;
  159. #endif
  160.     }
  161.  
  162.   public:
  163.  
  164.     typedef bool element_type;
  165. #ifdef _RWSTD_MSC22_STATIC_INIT_BUG
  166.     const size_t bitset_size;
  167. #else
  168. #ifndef _RWSTD_NO_STI_TEMPLATE
  169.     static const size_t bitset_size = N;
  170. #else
  171.     static const size_t bitset_size;
  172. #endif
  173. #endif
  174.  
  175.     //
  176.     // bit reference
  177.     //
  178.     class reference
  179.     {
  180.       friend class bitset<N>;
  181.     private:
  182.       bitset<N>& ref;
  183.       size_t     pos;
  184.       reference (bitset<N>& r, size_t p) _RWSTD_THROW_SPEC_NULL
  185.       : ref(r), pos(p) {}
  186.     public:
  187.       ~reference() _RWSTD_THROW_SPEC_NULL {}
  188.       //
  189.       // for b[i] = x;
  190.       //
  191.       reference& operator= (bool val) _RWSTD_THROW_SPEC_NULL
  192.       {
  193.         ref.set(pos, val); return *this;
  194.       }
  195.       //
  196.       // for b[i] = b[j];
  197.       //
  198.       reference& operator= (const reference& rhs) _RWSTD_THROW_SPEC_NULL
  199.       {
  200.         ref.set(pos, rhs.ref.test(rhs.pos)); return *this;
  201.       }
  202.       //
  203.       // for x = ~b[i];
  204.       //
  205.       bool operator~ () const _RWSTD_THROW_SPEC_NULL { return !ref.test(pos);}
  206.       //
  207.       // for x = b[i];
  208.       //
  209.       operator bool () const _RWSTD_THROW_SPEC_NULL { return ref.test(pos); }
  210.       reference& flip() _RWSTD_THROW_SPEC_NULL { ref.flip(pos); return *this;}
  211.     };
  212.     //
  213.     // constructors
  214.     //
  215.     bitset () _RWSTD_THROW_SPEC_NULL
  216. #ifdef _RWSTD_MSC22_STATIC_INIT_BUG
  217.       : bitset_size(N)
  218. #endif
  219.     {
  220. #ifndef _RWSTD_BC5_ENUM_BUG
  221.       memset(bits, 0, sizeof(bits));
  222. #else
  223.       bits = new VectorType[_NELEMENTS];
  224.       memset(bits, 0, _NELEMENTS*sizeof(VectorType));
  225. #endif /*_RWSTD_BC5_ENUM_BUG*/
  226.     }
  227.     bitset (unsigned long val) _RWSTD_THROW_SPEC_NULL
  228. #ifdef _RWSTD_MSC22_STATIC_INIT_BUG
  229.       : bitset_size(N)
  230. #endif
  231.     {
  232.       //
  233.       // Initialize first M bit positions to the corresponding
  234.       // bit values in val. M is the smaller of N and the value
  235.       // CHAR_BIT * sizeof(unsigned long).
  236.       //
  237. #ifndef _RWSTD_BC5_ENUM_BUG
  238.       memset(bits, 0, sizeof(bits));
  239. #else
  240.       bits = new VectorType[_NELEMENTS];
  241.       memset(bits, 0, _NELEMENTS*sizeof(VectorType));
  242. #endif /*_RWSTD_BC5_ENUM_BUG*/
  243.       size_t M = N < BitsInUnsignedLong ? N : BitsInUnsignedLong;
  244.       for (size_t i = 0; i < M; i++)
  245.         if (val & (1UL << i))
  246.           set(i);
  247.     }
  248.  
  249. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  250.     template <class charT, class traits, class Allocator>
  251.     _EXPLICIT bitset (const basic_string<charT,traits,Allocator>,
  252.                       _TYPENAME basic_string<charT,traits,Allocator>::size_type=0,
  253.                       _TYPENAME basic_string<charT,traits,Allocator>::size_type=
  254.                       std::template basic_string<charT,traits,Allocator>::npos)
  255. #else
  256.       _EXPLICIT bitset (const string& str,
  257.                         size_t pos = 0,
  258.                         size_t n = (size_t) -1)
  259. #endif // _RWSTD_NO_MEMBER_TEMPLATES
  260.       _RWSTD_THROW_SPEC((out_of_range, invalid_argument));
  261.  
  262.       // We _EXPLICITly defined the copy constructor, though
  263.       // WP 23.3.5 allows us to use the default generated one.
  264.       //
  265.       bitset (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  266. #ifdef _RWSTD_MSC22_STATIC_INIT_BUG
  267.         : bitset_size(N)
  268. #endif
  269.     {
  270. #ifndef _RWSTD_BC5_ENUM_BUG
  271.       memcpy(bits, rhs.bits, sizeof(bits));
  272. #else
  273.       bits = new VectorType[_NELEMENTS];
  274.       memcpy(bits, rhs.bits, _NELEMENTS*sizeof(VectorType));
  275. #endif /*_RWSTD_BC5_ENUM_BUG*/
  276.     }
  277.     //
  278.     // We _EXPLICITly defined the assignment, though
  279.     // WP 23.3.5 allows us to use the default generated one.
  280.     //
  281.     bitset<N>& operator= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  282.     {
  283.       if (!(this == &rhs))
  284. #ifndef _RWSTD_BC5_ENUM_BUG
  285.         memcpy(bits, rhs.bits, sizeof(bits));
  286. #else
  287.       memcpy(bits, rhs.bits, _NELEMENTS*sizeof(VectorType));
  288. #endif /*_RWSTD_BC5_ENUM_BUG*/
  289.       return *this;
  290.     }
  291. #ifdef _RWSTD_BC5_ENUM_BUG
  292.     ~bitset () _RWSTD_THROW_SPEC_NULL { delete [] bits; }
  293. #endif
  294.     //
  295.     // bitset operations
  296.     //
  297.     bitset<N>& operator&= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  298.     {
  299.       for (size_t i = 0; i < _NELEMENTS; i++)
  300.         bits[i] &= rhs.bits[i];
  301.       return *this;
  302.     }
  303.     bitset<N>& operator|= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  304.     {
  305.       for (size_t i = 0; i < _NELEMENTS; i++)
  306.         bits[i] |= rhs.bits[i];
  307.       return *this;
  308.     }
  309.     bitset<N>& operator^= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  310.     {
  311.       for (size_t i = 0; i < _NELEMENTS; i++)
  312.         bits[i] ^= rhs.bits[i];
  313.       return *this;
  314.     }
  315.     //
  316.     // Replaces bit at position I with a value determined as follows:
  317.     //
  318.     //   If (I <  pos) the new value is 0
  319.     //   If (I >= pos) the new value is the previous value at position I - pos
  320.     //
  321.     bitset<N>& operator<<= (size_t pos) _RWSTD_THROW_SPEC_NULL
  322.     {
  323.       if (pos)
  324.         for (long i = N - 1; i >= 0 ; --i)
  325.           set(i, i < pos || test(i - pos) == 0 ? 0 : 1);
  326.       return *this;
  327.     }
  328.     //
  329.     // Replaces bit at position I with a value determined as follows:
  330.     //
  331.     //   If (pos >= N-i) the new value is zero
  332.     //   If (pos <  N-i) the new value is the previous value at position I + pos
  333.     //
  334.     bitset<N>& operator>>= (size_t pos) _RWSTD_THROW_SPEC_NULL
  335.     {
  336.       if (pos)
  337.         for (size_t i = 0; i < N; i++)
  338.           set(i, pos >= N - i || test(i + pos) == 0 ? 0 : 1);
  339.       return *this;
  340.     }
  341.     bitset<N>& set () _RWSTD_THROW_SPEC_NULL
  342.     {
  343.       for (size_t i = 0; i < _NELEMENTS; i++)
  344.         bits[i] = ~0;
  345.       return *this;
  346.     }
  347.     bitset<N>& set (size_t pos, int val = 1) _RWSTD_THROW_SPEC((out_of_range))
  348.     {
  349.       _RWSTD_THROW(!valid_position(pos),out_of_range,
  350.                    __RWSTD::except_msg_string(__RWSTD::__rw_bitset_InvalidPosition,
  351.                                               "bitset::set(size_t,int )",pos).msgstr());
  352.  
  353.       if (val)
  354.         bits[pos / BitsPerChunk] |=  (1UL << index(pos));
  355.       else
  356.         bits[pos / BitsPerChunk] &= ~(1UL << index(pos));
  357.       return *this;
  358.     }
  359.     bitset<N>& reset () _RWSTD_THROW_SPEC_NULL
  360.     {
  361.       memset(bits, 0, sizeof(bits)); return *this;
  362.     }
  363.     bitset<N>& reset (size_t pos) _RWSTD_THROW_SPEC((out_of_range))
  364.     {
  365.       return set(pos, 0);
  366.     }
  367.     bitset<N> operator~ () const _RWSTD_THROW_SPEC_NULL
  368.     {
  369.       bitset<N> tmp(*this); return tmp.flip();
  370.     }
  371.     bitset<N>& flip () _RWSTD_THROW_SPEC_NULL
  372.     {
  373.       for (size_t i = 0; i < _NELEMENTS; i++) 
  374.         bits[i] = ~bits[i];
  375.       return *this;
  376.     }
  377.     bitset<N>& flip (size_t pos) _RWSTD_THROW_SPEC((out_of_range))
  378.     {
  379.       _RWSTD_THROW(!valid_position(pos),out_of_range,
  380.                    __RWSTD::except_msg_string(__RWSTD::__rw_bitset_InvalidPosition,
  381.                                               "bitset::flip(size_t)",pos).msgstr());
  382.  
  383.       bits[pos / BitsPerChunk] ^= (1UL << index(pos));
  384.       return *this;
  385.     }
  386.     //
  387.     // element access
  388.     //
  389.     reference operator[] (size_t pos) _RWSTD_THROW_SPEC((out_of_range))
  390.     {
  391.       //
  392.       // We check that pos is valid here so that NONE of the reference
  393.       // member functions need check.  This way ALL the reference member
  394.       // functions can have empty throw specifications.
  395.       //
  396.       _RWSTD_THROW(!valid_position(pos),out_of_range,
  397.                    __RWSTD::except_msg_string(__RWSTD::__rw_bitset_InvalidPosition,
  398.                                               "bitset::operator[](size_t)",pos).msgstr());
  399.  
  400.       reference r(*this, pos); return r;
  401.     }
  402.     //
  403.     // conversion functions
  404.     //
  405.     unsigned long  to_ulong  () const _RWSTD_THROW_SPEC((overflow_error));
  406. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  407.     template <class charT, class traits, class Allocator>
  408.     basic_string<charT,traits,Allocator>   to_string () const;
  409. #else
  410.     string         to_string () const;
  411. #endif
  412.     //
  413.     // miscellaneous member functions
  414.     //
  415.     size_t count () const _RWSTD_THROW_SPEC_NULL;
  416.     size_t size  () const _RWSTD_THROW_SPEC_NULL { return N; }
  417.     bool operator== (const bitset<N>& rhs) const _RWSTD_THROW_SPEC_NULL
  418.     {
  419.       for (size_t i = 0; i+1 < _NELEMENTS; i++)
  420.         if (!(bits[i] == rhs.bits[i]))
  421.           return false;
  422.       for (size_t j = (_NELEMENTS-1)*BitsPerChunk; j < N; j++)
  423.         if (!(test(j) == rhs.test(j)))
  424.           return false;
  425.       return true;
  426.     }
  427.     bool operator!= (const bitset<N>& rhs) const _RWSTD_THROW_SPEC_NULL
  428.     {
  429.       return !(*this == rhs);
  430.     }
  431.     bool test (size_t pos) const _RWSTD_THROW_SPEC((out_of_range))
  432.     {
  433.       _RWSTD_THROW(!valid_position(pos),out_of_range,
  434.                    __RWSTD::except_msg_string(__RWSTD::__rw_bitset_InvalidPosition,
  435.                                               "bitset::test(size_t) const",pos).msgstr());
  436.  
  437.       return (bits[pos / BitsPerChunk] & (1UL << index(pos))) != 0;
  438.     }
  439.     bool any () const _RWSTD_THROW_SPEC_NULL
  440.     {
  441.       bool flag = false;
  442.       for (size_t i = 0; i+1 <= _NELEMENTS && !flag; i++)
  443.         if (bits[i])
  444.           flag = true;
  445.       return flag;
  446.     }
  447.     bool none () const _RWSTD_THROW_SPEC_NULL
  448.     {
  449.       bool flag = true;
  450.       for (size_t i = 0; i+1 <= _NELEMENTS && flag; i++)
  451.         if (bits[i])
  452.           flag = false;
  453.       return flag;
  454.     }
  455.     bitset<N> operator<< (size_t pos) const _RWSTD_THROW_SPEC_NULL
  456.     {
  457.       bitset<N> tmp(*this); tmp <<= pos; return tmp;
  458.     }
  459.     bitset<N> operator>> (size_t pos) const _RWSTD_THROW_SPEC_NULL
  460.     {
  461.       bitset<N> tmp(*this); tmp >>= pos; return tmp;
  462.     }
  463.   };
  464. #ifndef _RWSTD_NO_NONTYPE_ARGS
  465.   template<size_t N>
  466.   inline bitset<N>  operator& (const bitset<N>& lhs,
  467.                                const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  468.   {
  469.     bitset<N> tmp(lhs); tmp &= rhs; return tmp;
  470.   }
  471.  
  472.   template<size_t N>
  473.   inline bitset<N>  operator| (const bitset<N>& lhs,
  474.                                const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  475.   {
  476.     bitset<N> tmp(lhs); tmp |= rhs; return tmp;
  477.   }
  478.  
  479.   template<size_t N>
  480.   inline bitset<N>  operator^ (const bitset<N>& lhs,
  481.                                const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  482.   {
  483.     bitset<N> tmp(lhs); tmp ^= rhs; return tmp;
  484.   }
  485.  
  486. #ifdef _RW_STD_IOSTREAM
  487.   template<class charT, class traits, size_t N> 
  488.   inline basic_ostream<charT,traits>&  
  489.   operator<< (basic_ostream<charT,traits>& os, const bitset<N>& x)
  490.   {
  491. #if !defined ( _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE) && !defined (_HPACC_)
  492.     return os << x.to_string<charT,traits,allocator<charT> >();
  493. #else
  494.     return os << x.to_string();
  495. #endif
  496.   }
  497.  
  498.   template<class charT, class traits, size_t N> 
  499.   basic_istream<charT,traits>&  
  500.   operator>> (basic_istream<charT,traits>& is, bitset<N>& x);
  501. #else
  502.   template<size_t N> 
  503.   inline ostream&  
  504.   operator<< (ostream& os, const bitset<N>& x)
  505.   {
  506. #ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  507.     return os << x.to_string<char,char_traits<char>,allocator<char> >();
  508. #else
  509.     return os << x.to_string();
  510. #endif
  511.   }
  512.  
  513.   template<size_t N> 
  514.   istream&  
  515.   operator>> (istream& is, bitset<N>& x);
  516. #endif //  _RW_STD_IOSTREAM
  517. #endif  /* _RWSTD_NO_NONTYPE_ARGS */
  518.  
  519. #undef _NELEMENTS
  520.  
  521. #ifndef _RWSTD_NO_NAMESPACE
  522. } 
  523. #endif
  524.  
  525. #if defined(_RWSTD_NO_DESTROY_BUILTIN) || defined(_RWSTD_NO_DESTROY_NONBUILTIN)
  526. #ifndef _RWSTD_NO_NONTYPE_ARGS
  527.  
  528. #ifndef _RWSTD_NO_NAMESPACE
  529. namespace __rwstd {
  530. #endif
  531. //
  532. // Specializations of STL destroy for bitset.
  533. //
  534.   template <size_t N> inline void __destroy (bitset<N>**)   {;}
  535.   template <size_t N> inline void __destroy (bitset<N>***)  {;}
  536.   template <size_t N> inline void __destroy (bitset<N>****) {;}
  537.  
  538. #ifndef _RWSTD_NO_NAMESPACE
  539. } 
  540. #endif
  541. #endif
  542. #endif
  543. #ifdef _RWSTD_NO_TEMPLATE_REPOSITORY
  544. #include <bitset.cc>
  545. #endif
  546. #endif /*__STD_BITS*/
  547. #ifndef __USING_STD_NAMES__
  548.   using namespace std;
  549. #endif
  550. #pragma option pop
  551. #endif /* __BITSET_H */
  552.