DCCL v3
bitset.h
1 // Copyright 2009-2017 Toby Schneider (http://gobysoft.org/index.wt/people/toby)
2 // GobySoft, LLC (for 2013-)
3 // Massachusetts Institute of Technology (for 2007-2014)
4 // Community contributors (see AUTHORS file)
5 //
6 //
7 // This file is part of the Dynamic Compact Control Language Library
8 // ("DCCL").
9 //
10 // DCCL is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU Lesser General Public License as published by
12 // the Free Software Foundation, either version 2.1 of the License, or
13 // (at your option) any later version.
14 //
15 // DCCL is distributed in the hope that it will be useful,
16 // but WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 // GNU Lesser General Public License for more details.
19 //
20 // You should have received a copy of the GNU Lesser General Public License
21 // along with DCCL. If not, see <http://www.gnu.org/licenses/>.
22 #ifndef DCCLBITSET20120424H
23 #define DCCLBITSET20120424H
24 
25 #include <deque>
26 #include <algorithm>
27 #include <limits>
28 #include <string>
29 #include <cstring>
30 
31 #include "exception.h"
32 
33 namespace dccl
34 {
38  class Bitset : public std::deque<bool>
39  {
40  public:
44  explicit Bitset(Bitset* parent = 0)
45  : parent_(parent)
46  { }
47 
53  explicit Bitset(size_type num_bits, unsigned long value = 0, Bitset* parent = 0)
54  : std::deque<bool>(num_bits, false),
55  parent_(parent)
56  { from(value, num_bits); }
57 
58  ~Bitset() { }
59 
66  void get_more_bits(size_type num_bits);
67 
74  Bitset& operator&=(const Bitset& rhs)
75  {
76  if(rhs.size() != size())
77  throw(dccl::Exception("Bitset operator&= requires this->size() == rhs.size()"));
78 
79  for (size_type i = 0; i != this->size(); ++i)
80  (*this)[i] = (*this)[i] & rhs[i];
81  return *this;
82  }
83 
90  Bitset& operator|=(const Bitset& rhs)
91  {
92  if(rhs.size() != size())
93  throw(dccl::Exception("Bitset operator|= requires this->size() == rhs.size()"));
94 
95  for (size_type i = 0; i != this->size(); ++i)
96  (*this)[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)
112  (*this)[i] = (*this)[i] ^ rhs[i];
113  return *this;
114  }
115 
116 // Bitset& operator-=(const Bitset& rhs);
117 
118 
125  Bitset& operator<<=(size_type n)
126  {
127  for(size_type i = 0; i < n; ++i)
128  {
129  push_front(false);
130  pop_back();
131  }
132  return *this;
133  }
134 
141  Bitset& operator>>=(size_type n)
142  {
143  for(size_type i = 0; i < n; ++i)
144  {
145  push_back(false);
146  pop_front();
147  }
148  return *this;
149  }
150 
154  Bitset operator<<(size_type n) const
155  {
156  Bitset copy(*this);
157  copy <<= n;
158  return copy;
159  }
160 
164  Bitset operator>>(size_type n) const
165  {
166  Bitset copy(*this);
167  copy >>= n;
168  return copy;
169  }
170 
176  Bitset& set(size_type n, bool val = true)
177  {
178  (*this)[n] = val;
179  return *this;
180  }
181 
185  Bitset& set()
186  {
187  for(iterator it = begin(), n = end(); it != n; ++it)
188  *it = true;
189  return *this;
190  }
191 
196  Bitset& reset(size_type n)
197  { return set(n, false);}
198 
203  {
204  for(iterator it = begin(), n = end(); it != n; ++it)
205  *it = false;
206  return *this;
207  }
208 
213  Bitset& flip(size_type n)
214  { return set(n, !(*this)[n]); }
215 
220  {
221  for(size_type i = 0, n = size(); i < n; ++i)
222  flip(i);
223  return *this;
224  }
225 
230  bool test(size_type n) const
231  { return (*this)[n]; }
232 
233  /* bool any() const; */
234  /* bool none() const; */
235  /* Bitset operator~() const; */
236  /* size_type count() const; */
237 
238 
239 
244  template<typename IntType>
245  void from(IntType value, size_type num_bits = std::numeric_limits<IntType>::digits)
246  {
247  this->resize(num_bits);
248  for(int i = 0, n = std::min<size_type>(std::numeric_limits<IntType>::digits, size());
249  i < n; ++i)
250  {
251  if(value & (static_cast<IntType>(1) << i))
252  (*this)[i] = true;
253  }
254  }
255 
257  void from_ulong(unsigned long value, size_type num_bits = std::numeric_limits<unsigned long>::digits)
258  {
259  from<unsigned long>(value, num_bits);
260  }
261 
266  template<typename IntType>
267  IntType to() const
268  {
269  if(size() > static_cast<size_type>(std::numeric_limits<IntType>::digits))
270  throw(Exception("Type IntType cannot represent current bitset (this->size() > std::numeric_limits<IntType>::digits)"));
271 
272  IntType out = 0;
273  for(int i = 0, n = size(); i < n; ++i)
274  {
275  if((*this)[i])
276  out |= (static_cast<IntType>(1) << i);
277  }
278 
279  return out;
280  }
281 
282 
284  unsigned long to_ulong() const
285  {
286  return to<unsigned long>();
287  }
288 
290  std::string to_string() const
291  {
292  std::string s(size(), 0);
293  int i = 0;
294  for(Bitset::const_reverse_iterator it = rbegin(),
295  n = rend(); it != n; ++it)
296  {
297  s[i] = (*it) ? '1' : '0';
298  ++i;
299  }
300  return s;
301  }
302 
303  // little-endian
304  // LSB = string[0]
305  // MSB = string[N]
306 
310  std::string to_byte_string()
311  {
312  // number of bytes needed is ceil(size() / 8)
313  std::string s(this->size()/8 + (this->size()%8 ? 1 : 0), 0);
314 
315  for(size_type i = 0, n = this->size(); i < n; ++i)
316  s[i/8] |= static_cast<char>((*this)[i] << (i%8));
317 
318  return s;
319  }
320 
326  size_t to_byte_string(char* buf, size_t max_len)
327  {
328  // number of bytes needed is ceil(size() / 8)
329  size_t len = this->size()/8 + (this->size()%8 ? 1 : 0);
330 
331  if (max_len < len)
332  {
333  throw std::length_error("max_len must be >= len");
334  }
335 
336  // initialize buffer to all zeroes
337  std::fill_n(buf, len, 0);
338 
339  for(size_type i = 0, n = this->size(); i < n; ++i)
340  buf[i/8] |= static_cast<char>((*this)[i] << (i%8));
341 
342  return len;
343  }
344 
348  void from_byte_string(const std::string& s)
349  {
350  from_byte_stream(s.begin(), s.end());
351  }
352 
357  template<typename CharIterator>
358  void from_byte_stream(CharIterator begin, CharIterator end)
359  {
360  this->resize(std::distance(begin, end) * 8);
361  int i = 0;
362  for(CharIterator it = begin; it != end; ++it)
363  {
364  for(size_type j = 0; j < 8; ++j)
365  (*this)[i*8+j] = (*it) & (1 << j);
366  ++i;
367  }
368  }
369 
371  Bitset& prepend(const Bitset& bits)
372  {
373  for(const_reverse_iterator it = bits.rbegin(),
374  n = bits.rend(); it != n; ++it)
375  push_front(*it);
376 
377  return *this;
378  }
379 
381  Bitset& append(const Bitset& bits)
382  {
383  for(const_iterator it = bits.begin(),
384  n = bits.end(); it != n; ++it)
385  push_back(*it);
386 
387  return *this;
388  }
389 
390 
391  private:
392  Bitset relinquish_bits(size_type num_bits, bool final_child);
393 
394  private:
395  Bitset* parent_;
396 
397 
398  };
399 
400  inline bool operator==(const Bitset& a, const Bitset& b)
401  {
402  return (a.size() == b.size()) && std::equal(a.begin(), a.end(), b.begin());
403  }
404 
405  inline bool operator<(const Bitset& a, const Bitset& b)
406  {
407  for(int i = (std::max(a.size(), b.size()) - 1); i >= 0; --i)
408  {
409  bool a_bit = (i < static_cast<int>(a.size())) ? a[i] : 0;
410  bool b_bit = (i < static_cast<int>(b.size())) ? b[i] : 0;
411 
412  if(a_bit > b_bit) return false;
413  else if(a_bit < b_bit) return true;
414  }
415  return false;
416  }
417 
418  inline Bitset operator&(const Bitset& b1, const Bitset& b2)
419  {
420  Bitset out(b1);
421  out &= b2;
422  return out;
423  }
424 
425  inline Bitset operator|(const Bitset& b1, const Bitset& b2)
426  {
427  Bitset out(b1);
428  out |= b2;
429  return out;
430  }
431 
432  inline Bitset operator^(const Bitset& b1, const Bitset& b2)
433  {
434  Bitset out(b1);
435  out ^= b2;
436  return out;
437  }
438 
439 
440  inline std::ostream& operator<<(std::ostream& os, const Bitset& b)
441  {
442  return (os << b.to_string());
443  }
444 
445 }
446 
447 inline void dccl::Bitset::get_more_bits(size_type num_bits)
448 {
449  relinquish_bits(num_bits, true);
450 }
451 
452 
453 #endif
Bitset & flip(size_type n)
Flip (toggle) a bit.
Definition: bitset.h:213
Bitset & append(const Bitset &bits)
Adds the bitset to the big end.
Definition: bitset.h:381
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:245
bool test(size_type n) const
Test a bit (return its value)
Definition: bitset.h:230
unsigned long to_ulong() const
Returns the value of the Bitset as an unsigned long integer. Equivalent to to<unsigned long>()...
Definition: bitset.h:284
Bitset operator<<(size_type n) const
Left shift.
Definition: bitset.h:154
std::string to_string() const
Returns the value of the Bitset as a printable string, where each bit is represented by &#39;1&#39; or &#39;0&#39;...
Definition: bitset.h:290
Bitset & operator&=(const Bitset &rhs)
Logical AND in place.
Definition: bitset.h:74
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:257
STL namespace.
Bitset & operator|=(const Bitset &rhs)
Logical OR in place.
Definition: bitset.h:90
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:358
Bitset & reset(size_type n)
Reset a bit (i.e. set it to false)
Definition: bitset.h:196
Bitset & operator^=(const Bitset &rhs)
Logical XOR in place.
Definition: bitset.h:106
Bitset & operator>>=(size_type n)
Right shift in place.
Definition: bitset.h:141
Bitset(Bitset *parent=0)
Construct an empty Bitset.
Definition: bitset.h:44
Bitset operator>>(size_type n) const
Right shift.
Definition: bitset.h:164
void get_more_bits(size_type num_bits)
Retrieve more bits from the parent Bitset.
Definition: bitset.h:447
Bitset & prepend(const Bitset &bits)
Adds the bitset to the little end.
Definition: bitset.h:371
Dynamic Compact Control Language namespace.
Bitset & operator<<=(size_type n)
Left shift in place.
Definition: bitset.h:125
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:326
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:348
Bitset & flip()
Flip (toggle) all bits.
Definition: bitset.h:219
Exception class for DCCL.
Definition: exception.h:31
IntType to() const
Returns the value of the Bitset as a integer.
Definition: bitset.h:267
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:310
Bitset(size_type num_bits, unsigned long value=0, Bitset *parent=0)
Construct a Bitset of a certain initial size and value.
Definition: bitset.h:53
A variable size container of bits (subclassed from std::deque<bool>) with an optional hierarchy...
Definition: bitset.h:38
Bitset & reset()
Set all bits false.
Definition: bitset.h:202