home *** CD-ROM | disk | FTP | other *** search
/ PC Format (South-Africa) 2001 May / PCFMay2001.iso / Xenon / C++ / FreeCommandLineTools.exe / Include / bitset.cc < prev    next >
Encoding:
C/C++ Source or Header  |  2000-01-31  |  6.5 KB  |  209 lines
  1. #ifndef __BITSET_CC
  2. #define __BITSET_CC
  3. #pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig
  4. /***************************************************************************
  5.  *
  6.  * bitset - class bitset declaration
  7.  *
  8.  ***************************************************************************
  9.  *
  10.  * Copyright (c) 1994-1999 Rogue Wave Software, Inc.  All Rights Reserved.
  11.  *
  12.  * This computer software is owned by Rogue Wave Software, Inc. and is
  13.  * protected by U.S. copyright laws and other laws and by international
  14.  * treaties.  This computer software is furnished by Rogue Wave Software,
  15.  * Inc. pursuant to a written license agreement and may be used, copied,
  16.  * transmitted, and stored only in accordance with the terms of such
  17.  * license and with the inclusion of the above copyright notice.  This
  18.  * computer software or any other copies thereof may not be provided or
  19.  * otherwise made available to any other person.
  20.  *
  21.  * U.S. Government Restricted Rights.  This computer software is provided
  22.  * with Restricted Rights.  Use, duplication, or disclosure by the
  23.  * Government is subject to restrictions as set forth in subparagraph (c)
  24.  * (1) (ii) of The Rights in Technical Data and Computer Software clause
  25.  * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
  26.  * Commercial Computer Software รป Restricted Rights at 48 CFR 52.227-19,
  27.  * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
  28.  * Flatiron Parkway, Boulder, Colorado 80301 USA.
  29.  *
  30.  **************************************************************************/
  31.  
  32. #include <stdcomp.h>
  33.  
  34. #ifdef _HPACC_
  35. #ifdef _RW_STD_IOSTREAM
  36. #include <iostream>
  37. #else
  38. #include <iostream.h>
  39. #endif
  40. #endif //_HPACC_
  41.  
  42. #ifndef _RWSTD_NO_NAMESPACE
  43. namespace std {
  44. #endif
  45.  
  46. #ifndef _NELEMENTS
  47. #  ifndef _RWSTD_BC5_ENUM_BUG
  48. #define _NELEMENTS NumOfElems
  49. #  else
  50. #define _NELEMENTS NumOfElems()
  51. #  endif /*_RWSTD_BC5_ENUM_BUG*/
  52. #endif /* _NELEMENTS */
  53.  
  54. #ifndef _RWSTD_MSC22_STATIC_INIT_BUG
  55.   template <size_t N>
  56.   const size_t bitset<N>::bitset_size 
  57. #ifdef _RWSTD_NO_STI_TEMPLATE
  58.   = N
  59. #endif
  60.   ;
  61. #endif /* _RWSTD_MSC22_STATIC_INIT_BUG */
  62.   template <size_t N>
  63. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  64.   template <class charT, class traits, class Allocator>
  65.   bitset<N>::bitset (const basic_string<charT,traits,Allocator> &str,
  66.                      _TYPENAME basic_string<charT,traits,Allocator>::size_type pos,
  67.                      _TYPENAME basic_string<charT,traits,Allocator>::size_type n)
  68. #else
  69.   bitset<N>::bitset (const string& str,
  70.                      size_t pos,
  71.                      size_t n) 
  72. #endif // _RWSTD_NO_MEMBER_TEMPLATES
  73.   _RWSTD_THROW_SPEC((out_of_range, invalid_argument))
  74. #ifdef _RWSTD_MSC22_STATIC_INIT_BUG
  75.   : bitset_size(N)
  76. #endif
  77.   {
  78.     size_t slen = str.size();
  79.  
  80.     _RWSTD_THROW(pos > slen,out_of_range,
  81.                  __RWSTD::except_msg_string(__RWSTD::__rw_bitset_InvalidPosition,
  82.                                             "bitset::bitset(const string&,size_t,size_t)",pos,slen).msgstr());
  83.  
  84.     size_t rlen = n < (slen - pos) ? n : slen - pos;
  85.     size_t M = N >= rlen ? rlen : N;
  86. #ifndef _RWSTD_BC5_ENUM_BUG
  87.     memset(bits, 0, sizeof(bits));
  88. #else
  89.     bits = new VectorType[_NELEMENTS];
  90.     memset(bits, 0, _NELEMENTS*sizeof(VectorType));
  91. #endif /*_RWSTD_BC5_ENUM_BUG*/
  92.     for (size_t i = pos; i < M + pos; i++)
  93.     {
  94.       char c = str[slen - i - 1];
  95.  
  96.       _RWSTD_THROW(!(c == '0' || c == '1'), invalid_argument,
  97.                    __RWSTD::except_msg_string(__RWSTD:: __rw_bitset_InvalidCtorArgument,
  98.                                               "bitset::bitset(const string&,size_t,size_t)").msgstr());
  99.  
  100.       if (c == '1') set(i - pos);
  101.     }
  102.   }
  103.  
  104. //
  105. // Constructs an object of type string and initializes it
  106. // to a string of length N characters. Each character is
  107. // determined by the value of its corresponding bit position
  108. // in *this. Character position N-1 corresponds to bit
  109. // position zero. Subsequent decreasing character positions
  110. // correspond to increasing bit positions. Bit value zero becomes
  111. // the character 0, bit value one becomes the character 1.
  112. //
  113.  
  114.   template <size_t N>
  115. #if !defined ( _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE) && !defined (_HPACC_)  && !defined(_RWSTD_NO_EXPLICIT_ARGS) 
  116.   template <class charT, class traits, class Allocator>
  117.   basic_string<charT,traits,Allocator>
  118. #else
  119.   string 
  120. #endif
  121.   bitset<N>::to_string () const 
  122.   {
  123. #if !defined ( _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE) && !defined (_HPACC_)  && !defined(_RWSTD_NO_EXPLICIT_ARGS) 
  124.     basic_string<charT,traits,Allocator>   s;
  125. #else
  126.     string s;
  127. #endif
  128.     for (long i = N - 1; i >= 0; --i)
  129.       s.append(1, test(i) ? '1' : '0');
  130.     return s;
  131.   }
  132.  
  133. //
  134. // If the integral value x corresponding to the bitset in *this
  135. // cannot be represented as type unsigned long, throws overflow_error.
  136. //
  137.  
  138.   template <size_t N>
  139.   unsigned long
  140.   bitset<N>::to_ulong () const _RWSTD_THROW_SPEC((overflow_error))
  141.   {
  142.     const size_t size_long = sizeof(unsigned long);
  143.  
  144.     for (size_t i = _NELEMENTS-1; size_long/sizeof(VectorType) <= i; --i)
  145.  
  146.       _RWSTD_THROW(bits[i], overflow_error,
  147.                    __RWSTD::except_msg_string(__RWSTD::__rw_bitset_ConversionOverflow,
  148.                                               "bitset::to_ulong() const").msgstr());
  149.     unsigned long result = 0;
  150.  
  151.     for (size_t pos = 0; pos < N; pos++)
  152.       if (test(pos))
  153.         result |= 1UL << pos;
  154.  
  155.     return result;
  156.   } 
  157.  
  158. //
  159. // Returns the count of the number of set bits.
  160. //
  161.  
  162.   template <size_t N>
  163.   size_t
  164.   bitset<N>::count () const _RWSTD_THROW_SPEC_NULL
  165.   {
  166.     size_t sum = 0;
  167.  
  168. #if UINT_MAX <= 4294967295
  169.     //
  170.     // A sophisticated implementaton that works if BitsPerChunk < 63
  171.     //
  172.     for (size_t i = 0; i < _NELEMENTS; i++)
  173.     {
  174.       unsigned long n = bits[i];
  175.       unsigned long t = n - ((n>>1) & 033333333333) - ((n>>2) & 011111111111);
  176.       t = ((t + (t >> 3)) & 030707070707);
  177.  
  178.       unsigned long x = t & 07700770077;
  179.       unsigned long y = (t >> 6) & 07700770077;
  180.  
  181.       t = x + y;
  182.       t = ((t >> 12) + (t >> 24) + t) & 0777;
  183.       t = (t >> 6) + (t & 077);
  184.       t = t + 1;
  185.  
  186.       sum += (t >> 6) + (t & 077) - 1;
  187.     }
  188. #else
  189.     //
  190.     // The more naive implementation that always works.
  191.     //
  192.     for (size_t i = 0; i < _NELEMENTS; i++)
  193.     {
  194.       unsigned long n = bits[i];
  195.       while (n)
  196.       {
  197.         n &= n-1;
  198.         sum++;
  199.       }
  200.     }
  201. #endif
  202.     return sum;
  203.   }
  204. #ifndef _RWSTD_NO_NAMESPACE
  205. }
  206. #endif
  207. #pragma option pop
  208. #endif /* __BITSET_CC */
  209.