home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / BC_502 / INC.PAK / BITSET.H < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-06  |  17.7 KB  |  629 lines
  1. #ifndef __STD_BITS
  2. #define __STD_BITS
  3. /* $Revision:   8.1  $ */
  4.  
  5. /***************************************************************************
  6.  *
  7.  * bitset - class bitset declaration
  8.  *
  9.  * $Id: bitset,v 1.55 1995/09/29 23:52:59 smithey Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  14.  * ALL RIGHTS RESERVED
  15.  *
  16.  * The software and information contained herein are proprietary to, and
  17.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  18.  * intends to preserve as trade secrets such software and information.
  19.  * This software is furnished pursuant to a written license agreement and
  20.  * may be used, copied, transmitted, and stored only in accordance with
  21.  * the terms of such license and with the inclusion of the above copyright
  22.  * notice.  This software and information or any other copies thereof may
  23.  * not be provided or otherwise made available to any other person.
  24.  *
  25.  * Notwithstanding any other lease or license that may pertain to, or
  26.  * accompany the delivery of, this computer software and information, the
  27.  * rights of the Government regarding its use, reproduction and disclosure
  28.  * are as set forth in Section 52.227-19 of the FARS Computer
  29.  * Software-Restricted Rights clause.
  30.  *
  31.  * Use, duplication, or disclosure by the Government is subject to
  32.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  33.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  34.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  35.  * P.O. Box 2328, Corvallis, Oregon 97339.
  36.  *
  37.  * This computer software and information is distributed with "restricted
  38.  * rights."  Use, duplication or disclosure is subject to restrictions as
  39.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  40.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  41.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  42.  * then the "Alternate III" clause applies.
  43.  *
  44.  **************************************************************************/
  45.  
  46. #include <stdcomp.h>
  47. #include <stddefs.h>
  48.  
  49. #ifndef RWSTD_NO_NEW_HEADER
  50. #include <climits>
  51. #include <cstddef>
  52. #else
  53. #include <limits.h>
  54. #include <stddef.h>
  55. #endif
  56.  
  57. #ifdef RW_STD_IOSTREAM
  58. #include <iosfwd>
  59. #else
  60. class  ostream;
  61. class  istream;
  62. #endif
  63.  
  64. #ifndef RWSTD_NO_EXCEPTIONS
  65. #ifdef RW_STD_EXCEPT
  66. #include <stdexcept>
  67. #endif
  68. #endif
  69.  
  70. #include <string>
  71.  
  72. #ifndef RWSTD_NO_NAMESPACE
  73. namespace std {
  74. #endif
  75.  
  76. //
  77. // Exception error messages.
  78. //
  79. extern char RWSTDExport  __rw_bitset_InvalidPosition[];
  80. extern char RWSTDExport  __rw_bitset_InvalidCtorArgument[];
  81. extern char RWSTDExport  __rw_bitset_ConversionOverflow[];
  82.  
  83. template <size_t N>
  84. class  bitset
  85. {
  86.   private:
  87.     //
  88.     // The type of array in which we store the bits.
  89.     //
  90.     typedef unsigned int VectorType;
  91.     //
  92.     // Number of bits in an array element.
  93.     //
  94.     enum { BitsPerChunk = CHAR_BIT*sizeof(unsigned int) };
  95.     //
  96.     // Number of array elements.
  97.     //
  98. #ifndef RWSTD_BC5_ENUM_BUG
  99.     enum { NumOfElems = N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk) };
  100.     #define NELEMENTS NumOfElems
  101. #else
  102.     int NumOfElems () const
  103.     {
  104.         return N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk);
  105.     }
  106.     #define NELEMENTS NumOfElems()
  107. #endif /*RWSTD_BC5_ENUM_BUG*/
  108.     //
  109.     // Number of bits in an unsigned long.
  110.     //
  111.     enum { BitsInUnsignedLong = CHAR_BIT*sizeof(unsigned long) };
  112.     //
  113.     // The array of bits.
  114.     //
  115. #ifndef RWSTD_BC5_ENUM_BUG
  116.     VectorType bits[NELEMENTS];
  117. #else
  118.     VectorType* bits;
  119. #endif /*RWSTD_BC5_ENUM_BUG*/
  120.  
  121.   protected:
  122.     //
  123.     // Is pos a valid bitset position?
  124.     //
  125.     bool valid_position (size_t pos) const RWSTD_THROW_SPEC_NULL
  126.     {
  127.         return N > pos ? true : false;
  128.     }
  129.     //
  130.     // Given a bit position `pos', returns the index into the appropriate
  131.     // chunk in bits[] such that 0 <= index < BitsPerChunk.
  132.     //
  133.     size_t index (size_t pos) const RWSTD_THROW_SPEC_NULL
  134.     {
  135. #if UINT_MAX == 256
  136.         return 7 & pos;
  137. #elif UINT_MAX == 65535
  138.         return 15 & pos;
  139. #elif UINT_MAX == 4294967295
  140.         return 31 & pos;
  141. #elif UINT_MAX == 18446744073709551616
  142.         return 63 & pos;
  143. #else
  144.         return pos % BitsPerChunk;
  145. #endif
  146.     }
  147.  
  148.   public:
  149.     //
  150.     // bit reference
  151.     //
  152.     class reference
  153.     {
  154.         friend class bitset<N>;
  155.       private:
  156.         bitset<N>& ref;
  157.         size_t     pos;
  158.         reference (bitset<N>& r, size_t p) RWSTD_THROW_SPEC_NULL
  159.             : ref(r), pos(p) {}
  160.       public:
  161.         ~reference() RWSTD_THROW_SPEC_NULL {}
  162.         //
  163.         // for b[i] = x;
  164.         //
  165.         reference& operator= (bool val) RWSTD_THROW_SPEC_NULL
  166.         {
  167.             ref.set(pos, val); return *this;
  168.         }
  169.         //
  170.         // for b[i] = b[j];
  171.         //
  172.         reference& operator= (const reference& rhs) RWSTD_THROW_SPEC_NULL
  173.         {
  174.             ref.set(pos, rhs.ref.test(rhs.pos)); return *this;
  175.         }
  176.         //
  177.         // for x = ~b[i];
  178.         //
  179.         bool operator~ () const RWSTD_THROW_SPEC_NULL { return !ref.test(pos);}
  180.         //
  181.         // for x = b[i];
  182.         //
  183.         operator bool () const RWSTD_THROW_SPEC_NULL { return ref.test(pos); }
  184.         //
  185.         // flips the bit
  186.         //
  187.         reference& flip() RWSTD_THROW_SPEC_NULL { ref.flip(pos); return *this;}
  188.     };
  189.     //
  190.     // constructors
  191.     //
  192.     bitset () RWSTD_THROW_SPEC_NULL
  193.     {
  194. #ifndef RWSTD_BC5_ENUM_BUG
  195.         memset(bits, 0, sizeof(bits));
  196. #else
  197.         bits = new VectorType[NELEMENTS];
  198.         //
  199.         // TODO -- check for bits == 0 here?
  200.         //
  201.         memset(bits, 0, NELEMENTS*sizeof(VectorType));
  202. #endif /*RWSTD_BC5_ENUM_BUG*/
  203.     }
  204.     bitset (unsigned long val) RWSTD_THROW_SPEC_NULL
  205.     {
  206.         //
  207.         // Initialize first M bit positions to the corresponding
  208.         // bit values in val. M is the smaller of N and the value
  209.         // CHAR_BIT * sizeof(unsigned long).
  210.         //
  211. #ifndef RWSTD_BC5_ENUM_BUG
  212.         memset(bits, 0, sizeof(bits));
  213. #else
  214.         bits = new VectorType[NELEMENTS];
  215.         //
  216.         // TODO -- check for bits == 0 here?
  217.         //
  218.         memset(bits, 0, NELEMENTS*sizeof(VectorType));
  219. #endif /*RWSTD_BC5_ENUM_BUG*/
  220.         size_t M = N < BitsInUnsignedLong ? N : BitsInUnsignedLong;
  221.         for (size_t i = 0; i < M; i++)
  222.             if (val & (1 << i))
  223.                 set(i);
  224.     }
  225.     explicit bitset (const string& str,
  226.                      size_t pos = 0,
  227.                      size_t n = (size_t) -1)
  228.                      RWSTD_THROW_SPEC((out_of_range, invalid_argument));
  229.     //
  230.     // We explicitly defined the copy constructor, though
  231.     // WP 17.2.2.2 allows us to use the default generated one.
  232.     //
  233.     bitset (const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  234.     {
  235. #ifndef RWSTD_BC5_ENUM_BUG
  236.         memcpy(bits, rhs.bits, sizeof(bits));
  237. #else
  238.         bits = new VectorType[NELEMENTS];
  239.         //
  240.         // TODO -- check for bits == 0 here?
  241.         //
  242.         memcpy(bits, rhs.bits, NELEMENTS*sizeof(VectorType));
  243. #endif /*RWSTD_BC5_ENUM_BUG*/
  244.     }
  245.     //
  246.     // We explicitly defined the assignment, though
  247.     // WP 17.2.2.2 allows us to use the default generated one.
  248.     //
  249.     bitset<N>& operator= (const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  250.     {
  251.         if (!(this == &rhs))
  252. #ifndef RWSTD_BC5_ENUM_BUG
  253.             memcpy(bits, rhs.bits, sizeof(bits));
  254. #else
  255.             memcpy(bits, rhs.bits, NELEMENTS*sizeof(VectorType));
  256. #endif /*RWSTD_BC5_ENUM_BUG*/
  257.         return *this;
  258.     }
  259. #ifdef RWSTD_BC5_ENUM_BUG
  260.     ~bitset () RWSTD_THROW_SPEC_NULL { delete [] bits; }
  261. #endif
  262.     //
  263.     // bitset operations
  264.     //
  265.     bitset<N>& operator&= (const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  266.     {
  267.         for (size_t i = 0; i < NELEMENTS; i++)
  268.             bits[i] &= rhs.bits[i];
  269.         return *this;
  270.     }
  271.     bitset<N>& operator|= (const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  272.     {
  273.         for (size_t i = 0; i < NELEMENTS; i++)
  274.             bits[i] |= rhs.bits[i];
  275.         return *this;
  276.     }
  277.     bitset<N>& operator^= (const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  278.     {
  279.         for (size_t i = 0; i < NELEMENTS; i++)
  280.             bits[i] ^= rhs.bits[i];
  281.         return *this;
  282.     }
  283.     //
  284.     // Replaces bit at position I with a value determined as follows:
  285.     //
  286.     //   If (I <  pos) the new value is 0
  287.     //   If (I >= pos) the new value is the previous value at position I - pos
  288.     //
  289.     bitset<N>& operator<<= (size_t pos) RWSTD_THROW_SPEC_NULL
  290.     {
  291.         if (pos)
  292.             for (long i = N - 1; i >= 0 ; --i)
  293.                 set(i, i < pos || test(i - pos) == 0 ? 0 : 1);
  294.         return *this;
  295.     }
  296.     //
  297.     // Replaces bit at position I with a value determined as follows:
  298.     //
  299.     //   If (pos >= N-i) the new value is zero
  300.     //   If (pos <  N-i) the new value is the previous value at position I + pos
  301.     //
  302.     bitset<N>& operator>>= (size_t pos) RWSTD_THROW_SPEC_NULL
  303.     {
  304.         if (pos)
  305.             for (size_t i = 0; i < N; i++)
  306.                 set(i, pos >= N - i || test(i + pos) == 0 ? 0 : 1);
  307.         return *this;
  308.     }
  309.     bitset<N>& set () RWSTD_THROW_SPEC_NULL
  310.     {
  311.         for (size_t i = 0; i < NELEMENTS; i++)
  312.             bits[i] = ~0;
  313.         return *this;
  314.     }
  315.     bitset<N>& set (size_t pos, int val = 1) RWSTD_THROW_SPEC((out_of_range))
  316.     {
  317.         RWSTD_THROW(!valid_position(pos),
  318.                     out_of_range,
  319.                     __rw_bitset_InvalidPosition);
  320.         if (val)
  321.             bits[pos / BitsPerChunk] |=  (1 << index(pos));
  322.         else
  323.             bits[pos / BitsPerChunk] &= ~(1 << index(pos));
  324.         return *this;
  325.     }
  326.     bitset<N>& reset () RWSTD_THROW_SPEC_NULL
  327.     {
  328.         memset(bits, 0, sizeof(bits)); return *this;
  329.     }
  330.     bitset<N>& reset (size_t pos) RWSTD_THROW_SPEC((out_of_range))
  331.     {
  332.         return set(pos, 0);
  333.     }
  334.     bitset<N> operator~ () RWSTD_THROW_SPEC_NULL
  335.     {
  336.         bitset<N> tmp(*this); return tmp.flip();
  337.     }
  338.     bitset<N>& flip () RWSTD_THROW_SPEC_NULL
  339.     {
  340.         for (size_t i = 0; i < NELEMENTS; i++)
  341.             bits[i] = ~bits[i];
  342.         return *this;
  343.     }
  344.     bitset<N>& flip (size_t pos) RWSTD_THROW_SPEC((out_of_range))
  345.     {
  346.         RWSTD_THROW(!valid_position(pos),
  347.                     out_of_range,
  348.                     __rw_bitset_InvalidPosition);
  349.         bits[pos / BitsPerChunk] ^= (1 << index(pos));
  350.         return *this;
  351.     }
  352.     //
  353.     // element access
  354.     //
  355.     reference operator[] (size_t pos) RWSTD_THROW_SPEC((out_of_range))
  356.     {
  357.         //
  358.         // We check that pos is valid here so that NONE of the reference
  359.         // member functions need check.  This way ALL the reference member
  360.         // functions can have empty throw specifications.
  361.         //
  362.         RWSTD_THROW(!valid_position(pos),
  363.                     out_of_range,
  364.                     __rw_bitset_InvalidPosition);
  365.         reference r(*this, pos); return r;
  366.     }
  367.     //
  368.     // conversion functions
  369.     //
  370.     unsigned long  to_ulong  () const RWSTD_THROW_SPEC((overflow_error));
  371.     string         to_string () const;
  372.     //
  373.     // miscellaneous member functions
  374.     //
  375.     size_t count () const RWSTD_THROW_SPEC_NULL;
  376.     size_t size  () const RWSTD_THROW_SPEC_NULL { return N; }
  377.     bool operator== (const bitset<N>& rhs) const RWSTD_THROW_SPEC_NULL
  378.     {
  379.         bool flag = true;
  380.         for (size_t i = 0; i < NELEMENTS && flag; i++)
  381.             if (!(bits[i] == rhs.bits[i]))
  382.                 flag = false;
  383.         return flag;
  384.     }
  385.     bool operator!= (const bitset<N>& rhs) const RWSTD_THROW_SPEC_NULL
  386.     {
  387.         return !(*this == rhs);
  388.     }
  389.     bool test (size_t pos) const RWSTD_THROW_SPEC((out_of_range))
  390.     {
  391.         RWSTD_THROW(!valid_position(pos),
  392.                     out_of_range,
  393.                     __rw_bitset_InvalidPosition);
  394.         return (bits[pos / BitsPerChunk] & (1 << index(pos))) != 0;
  395.     }
  396.     bool any () const RWSTD_THROW_SPEC_NULL
  397.     {
  398.         bool flag = false;
  399.         for (size_t i = 0; i < NELEMENTS && !flag; i++)
  400.             if (bits[i])
  401.                 flag = true;
  402.         return flag;
  403.     }
  404.     bool none () const RWSTD_THROW_SPEC_NULL
  405.     {
  406.         bool flag = true;
  407.         for (size_t i = 0; i < NELEMENTS && flag; i++)
  408.             if (bits[i])
  409.                 flag = false;
  410.         return flag;
  411.     }
  412.     bitset<N> operator<< (size_t pos) const RWSTD_THROW_SPEC_NULL
  413.     {
  414.         bitset<N> tmp(*this); tmp <<= pos; return tmp;
  415.     }
  416.     bitset<N> operator>> (size_t pos) const RWSTD_THROW_SPEC_NULL
  417.     {
  418.         bitset<N> tmp(*this); tmp >>= pos; return tmp;
  419.     }
  420. };
  421.  
  422. template <size_t N>
  423. bitset<N>::bitset (const string& str,
  424.                    size_t pos,
  425.                    size_t n) RWSTD_THROW_SPEC((out_of_range, invalid_argument))
  426. {
  427.     size_t slen = str.size();
  428.  
  429.     RWSTD_THROW(pos > slen,
  430.                 out_of_range,
  431.                 __rw_bitset_InvalidPosition);
  432.  
  433.     size_t rlen = n < (slen - pos) ? n : slen - pos;
  434.     size_t M = N >= rlen ? rlen : N;
  435. #ifndef RWSTD_BC5_ENUM_BUG
  436.     memset(bits, 0, sizeof(bits));
  437. #else
  438.     bits = new VectorType[NELEMENTS];
  439.     //
  440.     // TODO -- check for bits == 0 here?
  441.     //
  442.     memset(bits, 0, NELEMENTS*sizeof(VectorType));
  443. #endif /*RWSTD_BC5_ENUM_BUG*/
  444.     for (size_t i = pos; i < M + pos; i++)
  445.     {
  446.         char c = str[slen - i - 1];
  447.  
  448.         RWSTD_THROW(!(c == '0' || c == '1'),
  449.                     invalid_argument,
  450.                     __rw_bitset_InvalidCtorArgument);
  451.  
  452.         if (c == '1') set(i - pos);
  453.     }
  454. }
  455.  
  456. //
  457. // Constructs an object of type string and initializes it
  458. // to a string of length N characters. Each character is
  459. // determined by the value of its corresponding bit position
  460. // in *this. Character position N-1 corresponds to bit
  461. // position zero. Subsequent decreasing character positions
  462. // correspond to increasing bit positions. Bit value zero becomes
  463. // the character 0, bit value one becomes the character 1.
  464. //
  465.  
  466. template <size_t N>
  467. string
  468. bitset<N>::to_string () const
  469. {
  470.     string s;
  471.     if (N)
  472.         for (long i = N - 1; i >= 0; --i)
  473.             s.append(1, test(i) ? '1' : '0');
  474.     return s;
  475. }
  476.  
  477. //
  478. // If the integral value x corresponding to the bitset in *this
  479. // cannot be represented as type unsigned long, throws overflow_error.
  480. //
  481.  
  482. template <size_t N>
  483. unsigned long
  484. bitset<N>::to_ulong () const RWSTD_THROW_SPEC((overflow_error))
  485. {
  486.     const size_t size_long = sizeof(unsigned long);
  487.  
  488.     for (size_t i = NELEMENTS-1; size_long/sizeof(VectorType) <= i; --i)
  489.         RWSTD_THROW(bits[i],
  490.                     overflow_error,
  491.                     __rw_bitset_ConversionOverflow);
  492.  
  493.     unsigned long result = 0;
  494.  
  495.     for (size_t pos = 0; pos < N; pos++)
  496.         if (test(pos))
  497.             result |= 1 << pos;
  498.  
  499.     return result;
  500. }
  501.  
  502. //
  503. // Returns the count of the number of set bits.
  504. //
  505.  
  506. template <size_t N>
  507. size_t
  508. bitset<N>::count () const RWSTD_THROW_SPEC_NULL
  509. {
  510.     size_t sum = 0;
  511.  
  512. #if UINT_MAX <= 4294967295
  513.     //
  514.     // A sophisticated implementaton that works if BitsPerChunk < 63
  515.     //
  516.     for (size_t i = 0; i < NELEMENTS; i++)
  517.     {
  518.         unsigned long n = bits[i];
  519.         unsigned long t = n - ((n>>1) & 033333333333) - ((n>>2) & 011111111111);
  520.         t = ((t + (t >> 3)) & 030707070707);
  521.  
  522.         unsigned long x = t & 07700770077;
  523.         unsigned long y = (t >> 6) & 07700770077;
  524.  
  525.         t = x + y;
  526.         t = ((t >> 12) + (t >> 24) + t) & 0777;
  527.         t = (t >> 6) + (t & 077);
  528.         t = t + 1;
  529.  
  530.         sum += (t >> 6) + (t & 077) - 1;
  531.     }
  532. #else
  533.     //
  534.     // The more naive implementation that always works.
  535.     //
  536.     for (size_t i = 0; i < NELEMENTS; i++)
  537.     {
  538.         unsigned long n = bits[i];
  539.         while (n)
  540.         {
  541.             n &= n-1;
  542.             sum++;
  543.         }
  544.     }
  545. #endif
  546.     return sum;
  547. }
  548.  
  549. #ifndef RWSTD_NO_NONTYPE_ARGS
  550. template<size_t N>
  551. bitset<N>  operator& (const bitset<N>& lhs,
  552.                      const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  553. {
  554.     bitset<N> tmp(lhs); tmp &= rhs; return tmp;
  555. }
  556.  
  557. template<size_t N>
  558. bitset<N>  operator| (const bitset<N>& lhs,
  559.                      const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  560. {
  561.     bitset<N> tmp(lhs); tmp |= rhs; return tmp;
  562. }
  563.  
  564. template<size_t N>
  565. bitset<N>  operator^ (const bitset<N>& lhs,
  566.                      const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  567. {
  568.     bitset<N> tmp(lhs); tmp ^= rhs; return tmp;
  569. }
  570.  
  571. template<size_t N> ostream&  operator<< (ostream& os, const bitset<N>& x)
  572. {
  573.     return os << x.to_string();
  574. }
  575.  
  576. template <size_t N>
  577. istream&
  578.  operator>> (istream& is, bitset<N>& x)
  579. {
  580.     string str(N, '0');
  581.  
  582.     for (size_t count = 0; count < N && !is.eof(); )
  583.     {
  584.         char c = 0;
  585.         is >> c;
  586.         if (c == '1' || c == '0')
  587.         {
  588.             str.append(1, c);
  589.             count++;
  590.         }
  591.         else
  592.         {
  593.             is.putback(c);
  594.             break;
  595.         }
  596.     }
  597.  
  598.     if (str.size() == 0)
  599. #ifdef RW_STD_IOSTREAM
  600.         is.setstate(ios::failbit);
  601. #else
  602.         is.clear(ios::failbit);
  603. #endif
  604.  
  605.     x = bitset<N>(str);
  606.  
  607.     return is;
  608. }
  609. #endif /*RWSTD_NO_NONTYPE_ARGS*/
  610.  
  611. #if defined(RWSTD_NO_DESTROY_BUILTIN) || defined(RWSTD_NO_DESTROY_NONBUILTIN)
  612. #ifndef RWSTD_NO_NONTYPE_ARGS
  613. //
  614. // Specializations of STL destroy for bitset.
  615. //
  616. template <size_t N> inline void destroy (bitset<N>**)   {;}
  617. template <size_t N> inline void destroy (bitset<N>***)  {;}
  618. template <size_t N> inline void destroy (bitset<N>****) {;}
  619. #endif
  620. #endif
  621.  
  622. #undef NELEMENTS
  623.  
  624. #ifndef RWSTD_NO_NAMESPACE
  625. }
  626. #endif
  627.  
  628. #endif /*__STD_BITS*/
  629.