ubitset.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 // ubitset.h
   7 //
   8 #ifndef UBITSET_H_7B6450EC1400CBA45DCE0127739F82EE
   9 #define UBITSET_H_7B6450EC1400CBA45DCE0127739F82EE
  10
  11 #include "ustring.h"
  12 #include "ufunction.h"
  13
  14 namespace ustl {
  15
  16 typedef uint32_t        bitset_value_type;
  17
  18 void convert_to_bitstring (const bitset_value_type* v, size_t n, string& buf);
  19 void convert_from_bitstring (const string& buf, bitset_value_type* v, size_t n);
  20
  21 /// \class bitset ubitset.h ustl.h
  22 /// \ingroup Sequences
  23 ///
  24 /// \brief bitset is a fixed-size block of memory with addressable bits.
  25 ///
  26 /// Normally used for state flags; allows setting and unsetting of individual
  27 /// bits as well as bitwise operations on the entire set. The interface is
  28 /// most like that of unsigned integers, and is intended to be used as such.
  29 /// If you were using begin() and end() functions in STL's bitset, you would
  30 /// not be able to do the same thing here, because those functions return
  31 /// host type iterators, not bits.
  32 ///
  33 template <size_t Size>
  34 class bitset {
  35 public:
  36     typedef bitset_value_type   value_type;
  37     typedef value_type*         pointer;
  38     typedef const value_type*   const_pointer;
  39     typedef pointer             iterator;
  40     typedef const_pointer       const_iterator;
  41     typedef size_t              difference_type;
  42     typedef size_t              size_type;
  43 private:
  44     static const size_t s_WordBits      = BitsInType (value_type);
  45     static const size_t s_nWords        = Size / s_WordBits + ((Size % s_WordBits) != 0);
  46     static const size_t s_nBits         = s_nWords * s_WordBits;
  47 private:
  48     inline value_type&          BitRef (uoff_t n)       { assert (n < Size); return (m_Bits [n / s_WordBits]); }
  49     inline value_type           BitRef (uoff_t n) const { assert (n < Size); return (m_Bits [n / s_WordBits]); }
  50     inline value_type           Mask (uoff_t n) const   { assert (n < Size); return (1 << (n % s_WordBits)); }
  51 public:
  52     inline              bitset (value_type v = 0)       { fill_n (m_Bits, s_nWords, 0); m_Bits[0] = v; }
  53     inline              bitset (const string& buf)      { convert_from_bitstring (buf, m_Bits, s_nWords); }
  54     inline void         flip (uoff_t n)                 { BitRef(n) ^= Mask(n); }
  55     inline void         reset (void)                    { fill_n (m_Bits, s_nWords, 0); }
  56     inline void         clear (void)                    { fill_n (m_Bits, s_nWords, 0); }
  57     inline void         set (void)                      { fill_n (m_Bits, s_nWords, -1); }
  58     inline bitset       operator~ (void) const          { bitset rv (*this); rv.flip(); return (rv); }
  59     inline size_type    size (void) const               { return (Size); }
  60     inline size_type    capacity (void) const           { return (s_nBits); }
  61     inline bool         test (uoff_t n) const           { return (BitRef(n) & Mask(n)); }
  62     inline bool         operator[] (uoff_t n) const     { return (test(n)); }
  63   inline const_iterator begin (void) const              { return (m_Bits); }
  64     inline iterator     begin (void)                    { return (m_Bits); }
  65   inline const_iterator end (void) const                { return (m_Bits + s_nWords); }
  66     inline iterator     end (void)                      { return (m_Bits + s_nWords); }
  67                         /// Returns the value_type with the equivalent bits. If size() > 1, you'll get only the first BitsInType(value_type) bits.
  68     inline value_type   to_value (void) const           { return (m_Bits[0]); }
  69                         /// Flips all the bits in the set.
  70     inline void         flip (void) { transform (begin(), end(), begin(), bitwise_not<value_type>()); }
  71                         /// Sets or clears bit \p n.
  72     inline void         set (uoff_t n, bool val = true)
  73                         {
  74                             value_type& br (BitRef (n));
  75                             const value_type mask (Mask (n));
  76                             const value_type bOn (br | mask), bOff (br & ~mask);
  77                             br = val ? bOn : bOff;
  78                         }
  79                         // Sets the value of the bitrange \p first through \p last to the equivalent number of bits from \p v.
  80     inline void         set (uoff_t first, uoff_t DebugArg(last), value_type v)
  81                         {
  82                             assert (size_t (distance (first, last)) <= s_WordBits && "Bit ranges must be 32 bits or smaller");
  83                             assert (first / s_WordBits == last / s_WordBits && "Bit ranges can not cross dword (4 byte) boundary");
  84                             assert ((v & BitMask(value_type,distance(first,last))) == v && "The value is too large to fit in the given bit range");
  85                             BitRef(first) |= v << (first % s_WordBits);
  86                         }
  87                         /// Clears the bit \p n.
  88     inline void         reset (uoff_t n)                { set (n, false); }
  89                         /// Returns a string with bits MSB "001101001..." LSB.
  90     inline string       to_string (void) const
  91                         {
  92                             string rv (Size, '0');
  93                             convert_to_bitstring (m_Bits, s_nWords, rv);
  94                             return (rv);
  95                         }
  96     inline value_type   at (uoff_t n) const             { return (test(n)); }
  97                         /// Returns the value in bits \p first through \p last.
  98     inline value_type   at (uoff_t first, uoff_t last) const
  99                         {
 100                             assert (size_t (distance (first, last)) <= s_WordBits && "Bit ranges must be 32 bits or smaller");
 101                             assert (first / s_WordBits == last / s_WordBits && "Bit ranges can not cross dword (4 byte) boundary");
 102                             return ((BitRef(first) >> (first % s_WordBits)) & BitMask(value_type,distance(first, last)));
 103                         }
 104     inline bool         any (void) const        { value_type sum = 0; foreach (const_iterator, i, *this) sum |= *i; return (sum); }
 105     inline bool         none (void) const       { return (!any()); }
 106     inline size_t       count (void) const      { size_t sum = 0; foreach (const_iterator, i, *this) sum += popcount(*i); return (sum); }
 107     inline bool         operator== (const bitset<Size>& v) const
 108                             { return (s_nWords == 1 ? (m_Bits[0] == v.m_Bits[0]) : equal (begin(), end(), v.begin())); }
 109     inline const bitset operator& (const bitset<Size>& v)
 110                             { bitset<Size> result; transform (begin(), end(), v.begin(), result.begin(), bitwise_and<value_type>()); return (result); }
 111     inline const bitset operator| (const bitset<Size>& v)
 112                             { bitset<Size> result; transform (begin(), end(), v.begin(), result.begin(), bitwise_or<value_type>()); return (result); }
 113     inline const bitset operator^ (const bitset<Size>& v)
 114                             { bitset<Size> result; transform (begin(), end(), v.begin(), result.begin(), bitwise_xor<value_type>()); return (result); }
 115    inline const bitset& operator&= (const bitset<Size>& v)
 116                             { transform (begin(), end(), v.begin(), begin(), bitwise_and<value_type>()); return (*this); }
 117    inline const bitset& operator|= (const bitset<Size>& v)
 118                             { transform (begin(), end(), v.begin(), begin(), bitwise_or<value_type>()); return (*this); }
 119    inline const bitset& operator^= (const bitset<Size>& v)
 120                             { transform (begin(), end(), v.begin(), begin(), bitwise_xor<value_type>()); return (*this); }
 121     inline void         read (istream& is)                      { nr_container_read (is, *this); }
 122     inline void         write (ostream& os) const               { nr_container_write (os, *this); }
 123     inline void         text_write (ostringstream& os) const    { os << to_string(); }
 124     inline size_t       stream_size (void) const                { return (sizeof(m_Bits)); }
 125 private:
 126     value_type          m_Bits [s_nWords];
 127 };
 128
 129 } // namespace ustl
 130
 131 #endif
 132