DCCL v4
Loading...
Searching...
No Matches
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
37namespace dccl
38{
42class 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
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
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
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
375inline 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
380inline 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
395inline Bitset operator&(const Bitset& b1, const Bitset& b2)
396{
397 Bitset out(b1);
398 out &= b2;
399 return out;
400}
401
402inline Bitset operator|(const Bitset& b1, const Bitset& b2)
403{
404 Bitset out(b1);
405 out |= b2;
406 return out;
407}
408
409inline Bitset operator^(const Bitset& b1, const Bitset& b2)
410{
411 Bitset out(b1);
412 out ^= b2;
413 return out;
414}
415
416inline std::ostream& operator<<(std::ostream& os, const Bitset& b) { return (os << b.to_string()); }
417
418} // namespace dccl
419
420inline void dccl::Bitset::get_more_bits(size_type num_bits) { relinquish_bits(num_bits, true); }
421
422#endif
A variable size container of bits (subclassed from std::deque<bool>) with an optional hierarchy....
Definition bitset.h:43
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
Bitset & reset()
Set all bits false.
Definition bitset.h:199
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
void get_more_bits(size_type num_bits)
Retrieve more bits from the parent Bitset.
Definition bitset.h:420
Bitset operator>>(size_type n) const
Right shift.
Definition bitset.h:163
Bitset & operator>>=(size_type n)
Right shift in place.
Definition bitset.h:140
Bitset operator<<(size_type n) const
Left shift.
Definition bitset.h:153
Bitset & operator^=(const Bitset &rhs)
Logical XOR in place.
Definition bitset.h:107
Bitset & append(const Bitset &bits)
Adds the bitset to the big end.
Definition bitset.h:361
bool test(size_type n) const
Test a bit (return its value)
Definition bitset.h:224
Bitset & flip(size_type n)
Flip (toggle) a bit.
Definition bitset.h:209
Bitset & operator<<=(size_type n)
Left shift in place.
Definition bitset.h:124
IntType to() const
Returns the value of the Bitset as a integer.
Definition bitset.h:258
Bitset & operator|=(const Bitset &rhs)
Logical OR in place.
Definition bitset.h:92
Bitset & flip()
Flip (toggle) all bits.
Definition bitset.h:214
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
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
Bitset(Bitset *parent=nullptr)
Construct an empty Bitset.
Definition bitset.h:48
Bitset & set()
Set all bits true.
Definition bitset.h:184
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
Bitset & operator&=(const Bitset &rhs)
Logical AND in place.
Definition bitset.h:77
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
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
Bitset & reset(size_type n)
Reset a bit (i.e. set it to false)
Definition bitset.h:194
Bitset & set(size_type n, bool val=true)
Set a bit to a given value.
Definition bitset.h:175
Bitset & prepend(const Bitset &bits)
Adds the bitset to the little end.
Definition bitset.h:353
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
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
Exception class for DCCL.
Definition exception.h:47
Dynamic Compact Control Language namespace.
Definition any.h:47