DCCL v4
bitset.h
1 // Copyright 2012-2023:
2 // GobySoft, LLC (2013-)
3 // Massachusetts Institute of Technology (2007-2014)
4 // Community contributors (see AUTHORS file)
5 // File authors:
6 // Toby Schneider <toby@gobysoft.org>
7 // Nathan Knotts <nknotts@gmail.com>
8 // philboske <philboske@gmail.com>
9 //
10 //
11 // This file is part of the Dynamic Compact Control Language Library
12 // ("DCCL").
13 //
14 // DCCL is free software: you can redistribute it and/or modify
15 // it under the terms of the GNU Lesser General Public License as published by
16 // the Free Software Foundation, either version 2.1 of the License, or
17 // (at your option) any later version.
18 //
19 // DCCL is distributed in the hope that it will be useful,
20 // but WITHOUT ANY WARRANTY; without even the implied warranty of
21 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 // GNU Lesser General Public License for more details.
23 //
24 // You should have received a copy of the GNU Lesser General Public License
25 // along with DCCL. If not, see <http://www.gnu.org/licenses/>.
26 #ifndef DCCLBITSET20120424H
27 #define DCCLBITSET20120424H
28 
29 #include <algorithm>
30 #include <cstring>
31 #include <deque>
32 #include <limits>
33 #include <string>
34 
35 #include "exception.h"
36 
37 namespace dccl
38 {
42 class Bitset : public std::deque<bool>
43 {
44  public:
48  explicit Bitset(Bitset* parent = nullptr) : parent_(parent) {}
49 
55  explicit Bitset(size_type num_bits, unsigned long value = 0, Bitset* parent = nullptr)
56  : std::deque<bool>(num_bits, false), parent_(parent)
57  {
58  from(value, num_bits);
59  }
60 
61  ~Bitset() = default;
62 
69  void get_more_bits(size_type num_bits);
70 
77  Bitset& operator&=(const Bitset& rhs)
78  {
79  if (rhs.size() != size())
80  throw(dccl::Exception("Bitset operator&= requires this->size() == rhs.size()"));
81 
82  for (size_type i = 0; i != this->size(); ++i) (*this)[i] &= rhs[i];
83  return *this;
84  }
85 
92  Bitset& operator|=(const Bitset& rhs)
93  {
94  if (rhs.size() != size())
95  throw(dccl::Exception("Bitset operator|= requires this->size() == rhs.size()"));
96 
97  for (size_type i = 0; i != this->size(); ++i) (*this)[i] |= rhs[i];
98  return *this;
99  }
100 
107  Bitset& operator^=(const Bitset& rhs)
108  {
109  if (rhs.size() != size())
110  throw(dccl::Exception("Bitset operator^= requires this->size() == rhs.size()"));
111 
112  for (size_type i = 0; i != this->size(); ++i) (*this)[i] ^= rhs[i];
113  return *this;
114  }
115 
116  // Bitset& operator-=(const Bitset& rhs);
117 
124  Bitset& operator<<=(size_type n)
125  {
126  for (size_type i = 0; i < n; ++i)
127  {
128  push_front(false);
129  pop_back();
130  }
131  return *this;
132  }
133 
140  Bitset& operator>>=(size_type n)
141  {
142  for (size_type i = 0; i < n; ++i)
143  {
144  push_back(false);
145  pop_front();
146  }
147  return *this;
148  }
149 
153  Bitset operator<<(size_type n) const
154  {
155  Bitset copy(*this);
156  copy <<= n;
157  return copy;
158  }
159 
163  Bitset operator>>(size_type n) const
164  {
165  Bitset copy(*this);
166  copy >>= n;
167  return copy;
168  }
169 
175  Bitset& set(size_type n, bool val = true)
176  {
177  (*this)[n] = val;
178  return *this;
179  }
180 
185  {
186  for (bool& it : *this) it = true;
187  return *this;
188  }
189 
194  Bitset& reset(size_type n) { return set(n, false); }
195 
200  {
201  for (bool& it : *this) it = false;
202  return *this;
203  }
204 
209  Bitset& flip(size_type n) { return set(n, !(*this)[n]); }
210 
215  {
216  for (size_type i = 0, n = size(); i < n; ++i) flip(i);
217  return *this;
218  }
219 
224  bool test(size_type n) const { return (*this)[n]; }
225 
226  /* bool any() const; */
227  /* bool none() const; */
228  /* Bitset operator~() const; */
229  /* size_type count() const; */
230 
235  template <typename IntType>
236  void from(IntType value, size_type num_bits = std::numeric_limits<IntType>::digits)
237  {
238  this->resize(num_bits);
239  for (int i = 0, n = std::min<size_type>(std::numeric_limits<IntType>::digits, size());
240  i < n; ++i)
241  {
242  if (value & (static_cast<IntType>(1) << i))
243  (*this)[i] = true;
244  }
245  }
246 
248  void from_ulong(unsigned long value,
249  size_type num_bits = std::numeric_limits<unsigned long>::digits)
250  {
251  from<unsigned long>(value, num_bits);
252  }
253 
258  template <typename IntType> IntType to() const
259  {
260  if (size() > static_cast<size_type>(std::numeric_limits<IntType>::digits))
261  throw(Exception("Type IntType cannot represent current bitset (this->size() > "
262  "std::numeric_limits<IntType>::digits)"));
263 
264  IntType out = 0;
265  for (int i = 0, n = size(); i < n; ++i)
266  {
267  if ((*this)[i])
268  out |= (static_cast<IntType>(1) << i);
269  }
270 
271  return out;
272  }
273 
275  unsigned long to_ulong() const { return to<unsigned long>(); }
276 
278  std::string to_string() const
279  {
280  std::string s(size(), 0);
281  int i = 0;
282  for (auto it = rbegin(), n = rend(); it != n; ++it)
283  {
284  s[i] = (*it) ? '1' : '0';
285  ++i;
286  }
287  return s;
288  }
289 
290  // little-endian
291  // LSB = string[0]
292  // MSB = string[N]
293 
297  std::string to_byte_string()
298  {
299  // number of bytes needed is ceil(size() / 8)
300  std::string s(this->size() / 8 + (this->size() % 8 ? 1 : 0), 0);
301 
302  for (size_type i = 0, n = this->size(); i < n; ++i)
303  s[i / 8] |= static_cast<char>((*this)[i] << (i % 8));
304 
305  return s;
306  }
307 
313  size_t to_byte_string(char* buf, size_t max_len)
314  {
315  // number of bytes needed is ceil(size() / 8)
316  size_t len = this->size() / 8 + (this->size() % 8 ? 1 : 0);
317 
318  if (max_len < len)
319  {
320  throw std::length_error("max_len must be >= len");
321  }
322 
323  // initialize buffer to all zeroes
324  std::fill_n(buf, len, 0);
325 
326  for (size_type i = 0, n = this->size(); i < n; ++i)
327  buf[i / 8] |= static_cast<char>((*this)[i] << (i % 8));
328 
329  return len;
330  }
331 
335  void from_byte_string(const std::string& s) { from_byte_stream(s.begin(), s.end()); }
336 
341  template <typename CharIterator> void from_byte_stream(CharIterator begin, CharIterator end)
342  {
343  this->resize(std::distance(begin, end) * 8);
344  int i = 0;
345  for (CharIterator it = begin; it != end; ++it)
346  {
347  for (size_type j = 0; j < 8; ++j) (*this)[i * 8 + j] = (*it) & (1 << j);
348  ++i;
349  }
350  }
351 
353  Bitset& prepend(const Bitset& bits)
354  {
355  for (auto it = bits.rbegin(), n = bits.rend(); it != n; ++it) push_front(*it);
356 
357  return *this;
358  }
359 
361  Bitset& append(const Bitset& bits)
362  {
363  for (bool bit : bits) push_back(bit);
364 
365  return *this;
366  }
367 
368  private:
369  Bitset relinquish_bits(size_type num_bits, bool final_child);
370 
371  private:
372  Bitset* parent_;
373 };
374 
375 inline bool operator==(const Bitset& a, const Bitset& b)
376 {
377  return (a.size() == b.size()) && std::equal(a.begin(), a.end(), b.begin());
378 }
379 
380 inline bool operator<(const Bitset& a, const Bitset& b)
381 {
382  for (int i = (std::max(a.size(), b.size()) - 1); i >= 0; --i)
383  {
384  bool a_bit = (i < static_cast<int>(a.size())) ? a[i] : 0;
385  bool b_bit = (i < static_cast<int>(b.size())) ? b[i] : 0;
386 
387  if (a_bit > b_bit)
388  return false;
389  else if (a_bit < b_bit)
390  return true;
391  }
392  return false;
393 }
394 
395 inline Bitset operator&(const Bitset& b1, const Bitset& b2)
396 {
397  Bitset out(b1);
398  out &= b2;
399  return out;
400 }
401 
402 inline Bitset operator|(const Bitset& b1, const Bitset& b2)
403 {
404  Bitset out(b1);
405  out |= b2;
406  return out;
407 }
408 
409 inline Bitset operator^(const Bitset& b1, const Bitset& b2)
410 {
411  Bitset out(b1);
412  out ^= b2;
413  return out;
414 }
415 
416 inline std::ostream& operator<<(std::ostream& os, const Bitset& b) { return (os << b.to_string()); }
417 
418 } // namespace dccl
419 
420 inline void dccl::Bitset::get_more_bits(size_type num_bits) { relinquish_bits(num_bits, true); }
421 
422 #endif
dccl::Bitset::reset
Bitset & reset()
Set all bits false.
Definition: bitset.h:199
dccl::Bitset::to
IntType to() const
Returns the value of the Bitset as a integer.
Definition: bitset.h:258
dccl::Bitset::operator&=
Bitset & operator&=(const Bitset &rhs)
Logical AND in place.
Definition: bitset.h:77
dccl::Bitset::Bitset
Bitset(size_type num_bits, unsigned long value=0, Bitset *parent=nullptr)
Construct a Bitset of a certain initial size and value.
Definition: bitset.h:55
dccl::Bitset::flip
Bitset & flip()
Flip (toggle) all bits.
Definition: bitset.h:214
dccl::Bitset::to_ulong
unsigned long to_ulong() const
Returns the value of the Bitset as an unsigned long integer. Equivalent to to<unsigned long>().
Definition: bitset.h:275
dccl::Bitset::get_more_bits
void get_more_bits(size_type num_bits)
Retrieve more bits from the parent Bitset.
Definition: bitset.h:420
dccl
Dynamic Compact Control Language namespace.
Definition: any.h:46
dccl::Exception
Exception class for DCCL.
Definition: exception.h:46
dccl::Bitset::flip
Bitset & flip(size_type n)
Flip (toggle) a bit.
Definition: bitset.h:209
dccl::Bitset::from_byte_string
void from_byte_string(const std::string &s)
Sets the value of the Bitset to the contents of a byte string, where each character represents 8 bits...
Definition: bitset.h:335
dccl::Bitset::operator>>
Bitset operator>>(size_type n) const
Right shift.
Definition: bitset.h:163
dccl::Bitset::from
void from(IntType value, size_type num_bits=std::numeric_limits< IntType >::digits)
Sets value of the Bitset to the contents of an integer.
Definition: bitset.h:236
bool
dccl::Bitset::operator|=
Bitset & operator|=(const Bitset &rhs)
Logical OR in place.
Definition: bitset.h:92
dccl::Bitset::append
Bitset & append(const Bitset &bits)
Adds the bitset to the big end.
Definition: bitset.h:361
dccl::Bitset::test
bool test(size_type n) const
Test a bit (return its value)
Definition: bitset.h:224
dccl::Bitset::from_byte_stream
void from_byte_stream(CharIterator begin, CharIterator end)
Sets the value of the Bitset to the contents of a byte string, where each character represents 8 bits...
Definition: bitset.h:341
dccl::Bitset
A variable size container of bits (subclassed from std::deque<bool>) with an optional hierarchy....
Definition: bitset.h:42
dccl::Bitset::operator<<=
Bitset & operator<<=(size_type n)
Left shift in place.
Definition: bitset.h:124
dccl::Bitset::reset
Bitset & reset(size_type n)
Reset a bit (i.e. set it to false)
Definition: bitset.h:194
dccl::Bitset::operator>>=
Bitset & operator>>=(size_type n)
Right shift in place.
Definition: bitset.h:140
dccl::Bitset::operator<<
Bitset operator<<(size_type n) const
Left shift.
Definition: bitset.h:153
dccl::Bitset::to_string
std::string to_string() const
Returns the value of the Bitset as a printable string, where each bit is represented by '1' or '0'....
Definition: bitset.h:278
dccl::Bitset::from_ulong
void from_ulong(unsigned long value, size_type num_bits=std::numeric_limits< unsigned long >::digits)
Sets value of the Bitset to the contents of an unsigned long integer. Equivalent to from<unsigned lon...
Definition: bitset.h:248
dccl::Bitset::set
Bitset & set()
Set all bits true.
Definition: bitset.h:184
dccl::Bitset::prepend
Bitset & prepend(const Bitset &bits)
Adds the bitset to the little end.
Definition: bitset.h:353
dccl::Bitset::Bitset
Bitset(Bitset *parent=nullptr)
Construct an empty Bitset.
Definition: bitset.h:48
dccl::Bitset::operator^=
Bitset & operator^=(const Bitset &rhs)
Logical XOR in place.
Definition: bitset.h:107
dccl::Bitset::set
Bitset & set(size_type n, bool val=true)
Set a bit to a given value.
Definition: bitset.h:175
dccl::Bitset::to_byte_string
size_t to_byte_string(char *buf, size_t max_len)
Generate a byte string representation of the Bitset, where each character represents 8 bits of the Bi...
Definition: bitset.h:313
dccl::Bitset::to_byte_string
std::string to_byte_string()
Returns the value of the Bitset to a byte string, where each character represents 8 bits of the Bitse...
Definition: bitset.h:297