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