williamr@2
|
1 |
// --------------------------------------------------
|
williamr@2
|
2 |
//
|
williamr@2
|
3 |
// (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002.
|
williamr@2
|
4 |
// (C) Copyright Gennaro Prota 2003 - 2004.
|
williamr@2
|
5 |
//
|
williamr@2
|
6 |
// Distributed under the Boost Software License, Version 1.0.
|
williamr@2
|
7 |
// (See accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
8 |
// http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
9 |
//
|
williamr@2
|
10 |
// -----------------------------------------------------------
|
williamr@2
|
11 |
|
williamr@2
|
12 |
// See http://www.boost.org/libs/dynamic_bitset for documentation.
|
williamr@2
|
13 |
|
williamr@2
|
14 |
|
williamr@2
|
15 |
|
williamr@2
|
16 |
#ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
|
williamr@2
|
17 |
#define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
|
williamr@2
|
18 |
|
williamr@2
|
19 |
#include <cassert>
|
williamr@2
|
20 |
#include <string>
|
williamr@2
|
21 |
#include <stdexcept> // for std::overflow_error
|
williamr@2
|
22 |
#include <algorithm> // for std::swap, std::min, std::copy, std::fill
|
williamr@2
|
23 |
#include <vector>
|
williamr@2
|
24 |
#include <climits> // for CHAR_BIT
|
williamr@2
|
25 |
|
williamr@2
|
26 |
#include "boost/dynamic_bitset/config.hpp"
|
williamr@2
|
27 |
|
williamr@2
|
28 |
#ifndef BOOST_NO_STD_LOCALE
|
williamr@2
|
29 |
# include <locale> // G.P.S
|
williamr@2
|
30 |
#endif
|
williamr@2
|
31 |
|
williamr@2
|
32 |
#if defined(BOOST_OLD_IOSTREAMS)
|
williamr@2
|
33 |
# include <iostream.h>
|
williamr@2
|
34 |
# include <ctype.h> // for isspace
|
williamr@2
|
35 |
#else
|
williamr@2
|
36 |
# include <istream>
|
williamr@2
|
37 |
# include <ostream>
|
williamr@2
|
38 |
#endif
|
williamr@2
|
39 |
|
williamr@2
|
40 |
#include "boost/dynamic_bitset_fwd.hpp"
|
williamr@2
|
41 |
#include "boost/detail/dynamic_bitset.hpp"
|
williamr@2
|
42 |
#include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)
|
williamr@2
|
43 |
#include "boost/static_assert.hpp"
|
williamr@2
|
44 |
#include "boost/limits.hpp"
|
williamr@2
|
45 |
#include "boost/pending/lowest_bit.hpp" // used by find_first/next
|
williamr@2
|
46 |
|
williamr@2
|
47 |
|
williamr@2
|
48 |
namespace boost {
|
williamr@2
|
49 |
|
williamr@2
|
50 |
template
|
williamr@2
|
51 |
|
williamr@2
|
52 |
#if defined(BOOST_MSVC) && BOOST_WORKAROUND(BOOST_MSVC, <= 1300) // 1300 == VC++ 7.0
|
williamr@2
|
53 |
// VC++ (up to 7.0) wants the default arguments again
|
williamr@2
|
54 |
<typename Block = unsigned long, typename Allocator = std::allocator<Block> >
|
williamr@2
|
55 |
# else
|
williamr@2
|
56 |
<typename Block, typename Allocator>
|
williamr@2
|
57 |
# endif
|
williamr@2
|
58 |
|
williamr@2
|
59 |
class dynamic_bitset
|
williamr@2
|
60 |
{
|
williamr@2
|
61 |
// Portability note: member function templates are defined inside
|
williamr@2
|
62 |
// this class definition to avoid problems with VC++. Similarly,
|
williamr@2
|
63 |
// with the member functions of nested classes.
|
williamr@2
|
64 |
|
williamr@2
|
65 |
BOOST_STATIC_ASSERT(detail::dynamic_bitset_allowed_block_type<Block>::value);
|
williamr@2
|
66 |
|
williamr@2
|
67 |
public:
|
williamr@2
|
68 |
typedef Block block_type;
|
williamr@2
|
69 |
typedef Allocator allocator_type;
|
williamr@2
|
70 |
typedef std::size_t size_type;
|
williamr@2
|
71 |
typedef int block_width_type; // gps
|
williamr@2
|
72 |
|
williamr@2
|
73 |
BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));
|
williamr@2
|
74 |
BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
|
williamr@2
|
75 |
|
williamr@2
|
76 |
|
williamr@2
|
77 |
public:
|
williamr@2
|
78 |
|
williamr@2
|
79 |
// A proxy class to simulate lvalues of bit type.
|
williamr@2
|
80 |
// Shouldn't it be private? [gps]
|
williamr@2
|
81 |
//
|
williamr@2
|
82 |
class reference
|
williamr@2
|
83 |
{
|
williamr@2
|
84 |
friend class dynamic_bitset<Block, Allocator>;
|
williamr@2
|
85 |
|
williamr@2
|
86 |
|
williamr@2
|
87 |
// the one and only non-copy ctor
|
williamr@2
|
88 |
reference(block_type & b, int pos)
|
williamr@2
|
89 |
:m_block(b), m_mask(block_type(1) << pos)
|
williamr@2
|
90 |
{}
|
williamr@2
|
91 |
|
williamr@2
|
92 |
void operator&(); // left undefined
|
williamr@2
|
93 |
|
williamr@2
|
94 |
public:
|
williamr@2
|
95 |
|
williamr@2
|
96 |
// copy constructor: compiler generated
|
williamr@2
|
97 |
|
williamr@2
|
98 |
operator bool() const { return (m_block & m_mask) != 0; }
|
williamr@2
|
99 |
bool operator~() const { return (m_block & m_mask) == 0; }
|
williamr@2
|
100 |
|
williamr@2
|
101 |
reference& flip() { do_flip(); return *this; }
|
williamr@2
|
102 |
|
williamr@2
|
103 |
reference& operator=(bool x) { do_assign(x); return *this; } // for b[i] = x
|
williamr@2
|
104 |
reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]
|
williamr@2
|
105 |
|
williamr@2
|
106 |
reference& operator|=(bool x) { if (x) do_set(); return *this; }
|
williamr@2
|
107 |
reference& operator&=(bool x) { if (!x) do_reset(); return *this; }
|
williamr@2
|
108 |
reference& operator^=(bool x) { if (x) do_flip(); return *this; }
|
williamr@2
|
109 |
reference& operator-=(bool x) { if (x) do_reset(); return *this; }
|
williamr@2
|
110 |
|
williamr@2
|
111 |
private:
|
williamr@2
|
112 |
block_type & m_block;
|
williamr@2
|
113 |
const block_type m_mask;
|
williamr@2
|
114 |
|
williamr@2
|
115 |
void do_set() { m_block |= m_mask; }
|
williamr@2
|
116 |
void do_reset() { m_block &= ~m_mask; }
|
williamr@2
|
117 |
void do_flip() { m_block ^= m_mask; }
|
williamr@2
|
118 |
void do_assign(bool x) { x? do_set() : do_reset(); }
|
williamr@2
|
119 |
};
|
williamr@2
|
120 |
|
williamr@2
|
121 |
typedef bool const_reference;
|
williamr@2
|
122 |
|
williamr@2
|
123 |
// constructors, etc.
|
williamr@2
|
124 |
explicit
|
williamr@2
|
125 |
dynamic_bitset(const Allocator& alloc = Allocator());
|
williamr@2
|
126 |
|
williamr@2
|
127 |
explicit
|
williamr@2
|
128 |
dynamic_bitset(size_type num_bits, unsigned long value = 0,
|
williamr@2
|
129 |
const Allocator& alloc = Allocator());
|
williamr@2
|
130 |
|
williamr@2
|
131 |
|
williamr@2
|
132 |
// The presence of this constructor is a concession to ease of
|
williamr@2
|
133 |
// use, especially for the novice user. A conversion from string
|
williamr@2
|
134 |
// is, in most cases, formatting, and should be done by the standard
|
williamr@2
|
135 |
// formatting convention: operator>>.
|
williamr@2
|
136 |
//
|
williamr@2
|
137 |
// NOTE:
|
williamr@2
|
138 |
// Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.
|
williamr@2
|
139 |
// g++ 3.2 requires them and probably the standard will - see core issue 325
|
williamr@2
|
140 |
// NOTE 2:
|
williamr@2
|
141 |
// split into two constructors because of bugs in MSVC 6.0sp5 with STLport
|
williamr@2
|
142 |
|
williamr@2
|
143 |
template <typename CharT, typename Traits, typename Alloc>
|
williamr@2
|
144 |
dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
|
williamr@2
|
145 |
typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
|
williamr@2
|
146 |
typename std::basic_string<CharT, Traits, Alloc>::size_type n,
|
williamr@2
|
147 |
size_type num_bits = npos,
|
williamr@2
|
148 |
const Allocator& alloc = Allocator())
|
williamr@2
|
149 |
|
williamr@2
|
150 |
:m_bits(alloc),
|
williamr@2
|
151 |
m_num_bits(0)
|
williamr@2
|
152 |
{
|
williamr@2
|
153 |
init_from_string(s, pos, n, num_bits, alloc);
|
williamr@2
|
154 |
}
|
williamr@2
|
155 |
|
williamr@2
|
156 |
template <typename CharT, typename Traits, typename Alloc>
|
williamr@2
|
157 |
explicit
|
williamr@2
|
158 |
dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
|
williamr@2
|
159 |
typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0)
|
williamr@2
|
160 |
|
williamr@2
|
161 |
:m_bits(Allocator()),
|
williamr@2
|
162 |
m_num_bits(0)
|
williamr@2
|
163 |
{
|
williamr@2
|
164 |
init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),
|
williamr@2
|
165 |
npos, Allocator());
|
williamr@2
|
166 |
}
|
williamr@2
|
167 |
|
williamr@2
|
168 |
// The first bit in *first is the least significant bit, and the
|
williamr@2
|
169 |
// last bit in the block just before *last is the most significant bit.
|
williamr@2
|
170 |
template <typename BlockInputIterator>
|
williamr@2
|
171 |
dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
|
williamr@2
|
172 |
const Allocator& alloc = Allocator())
|
williamr@2
|
173 |
|
williamr@2
|
174 |
:m_bits(first, last, alloc),
|
williamr@2
|
175 |
m_num_bits(m_bits.size() * bits_per_block)
|
williamr@2
|
176 |
{}
|
williamr@2
|
177 |
|
williamr@2
|
178 |
|
williamr@2
|
179 |
// copy constructor
|
williamr@2
|
180 |
dynamic_bitset(const dynamic_bitset& b);
|
williamr@2
|
181 |
|
williamr@2
|
182 |
~dynamic_bitset();
|
williamr@2
|
183 |
|
williamr@2
|
184 |
void swap(dynamic_bitset& b);
|
williamr@2
|
185 |
dynamic_bitset& operator=(const dynamic_bitset& b);
|
williamr@2
|
186 |
|
williamr@2
|
187 |
allocator_type get_allocator() const;
|
williamr@2
|
188 |
|
williamr@2
|
189 |
// size changing operations
|
williamr@2
|
190 |
void resize(size_type num_bits, bool value = false);
|
williamr@2
|
191 |
void clear();
|
williamr@2
|
192 |
void push_back(bool bit);
|
williamr@2
|
193 |
void append(Block block);
|
williamr@2
|
194 |
|
williamr@2
|
195 |
template <typename BlockInputIterator>
|
williamr@2
|
196 |
void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)
|
williamr@2
|
197 |
{
|
williamr@2
|
198 |
std::vector<Block, Allocator> v(first, last);
|
williamr@2
|
199 |
m_append(v.begin(), v.end(), std::random_access_iterator_tag());
|
williamr@2
|
200 |
}
|
williamr@2
|
201 |
template <typename BlockInputIterator>
|
williamr@2
|
202 |
void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)
|
williamr@2
|
203 |
{
|
williamr@2
|
204 |
assert(first != last);
|
williamr@2
|
205 |
block_width_type r = count_extra_bits();
|
williamr@2
|
206 |
std::size_t d = boost::detail::distance(first, last);
|
williamr@2
|
207 |
m_bits.reserve(num_blocks() + d);
|
williamr@2
|
208 |
if (r == 0) {
|
williamr@2
|
209 |
for( ; first != last; ++first)
|
williamr@2
|
210 |
m_bits.push_back(*first); // could use vector<>::insert()
|
williamr@2
|
211 |
}
|
williamr@2
|
212 |
else {
|
williamr@2
|
213 |
m_highest_block() |= (*first << r);
|
williamr@2
|
214 |
do {
|
williamr@2
|
215 |
Block b = *first >> (bits_per_block - r);
|
williamr@2
|
216 |
++first;
|
williamr@2
|
217 |
m_bits.push_back(b | (first==last? 0 : *first << r));
|
williamr@2
|
218 |
} while (first != last);
|
williamr@2
|
219 |
}
|
williamr@2
|
220 |
m_num_bits += bits_per_block * d;
|
williamr@2
|
221 |
}
|
williamr@2
|
222 |
template <typename BlockInputIterator>
|
williamr@2
|
223 |
void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee
|
williamr@2
|
224 |
{
|
williamr@2
|
225 |
if (first != last) {
|
williamr@2
|
226 |
typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;
|
williamr@2
|
227 |
m_append(first, last, cat);
|
williamr@2
|
228 |
}
|
williamr@2
|
229 |
}
|
williamr@2
|
230 |
|
williamr@2
|
231 |
|
williamr@2
|
232 |
// bitset operations
|
williamr@2
|
233 |
dynamic_bitset& operator&=(const dynamic_bitset& b);
|
williamr@2
|
234 |
dynamic_bitset& operator|=(const dynamic_bitset& b);
|
williamr@2
|
235 |
dynamic_bitset& operator^=(const dynamic_bitset& b);
|
williamr@2
|
236 |
dynamic_bitset& operator-=(const dynamic_bitset& b);
|
williamr@2
|
237 |
dynamic_bitset& operator<<=(size_type n);
|
williamr@2
|
238 |
dynamic_bitset& operator>>=(size_type n);
|
williamr@2
|
239 |
dynamic_bitset operator<<(size_type n) const;
|
williamr@2
|
240 |
dynamic_bitset operator>>(size_type n) const;
|
williamr@2
|
241 |
|
williamr@2
|
242 |
// basic bit operations
|
williamr@2
|
243 |
dynamic_bitset& set(size_type n, bool val = true);
|
williamr@2
|
244 |
dynamic_bitset& set();
|
williamr@2
|
245 |
dynamic_bitset& reset(size_type n);
|
williamr@2
|
246 |
dynamic_bitset& reset();
|
williamr@2
|
247 |
dynamic_bitset& flip(size_type n);
|
williamr@2
|
248 |
dynamic_bitset& flip();
|
williamr@2
|
249 |
bool test(size_type n) const;
|
williamr@2
|
250 |
bool any() const;
|
williamr@2
|
251 |
bool none() const;
|
williamr@2
|
252 |
dynamic_bitset operator~() const;
|
williamr@2
|
253 |
size_type count() const;
|
williamr@2
|
254 |
|
williamr@2
|
255 |
// subscript
|
williamr@2
|
256 |
reference operator[](size_type pos) {
|
williamr@2
|
257 |
return reference(m_bits[block_index(pos)], bit_index(pos));
|
williamr@2
|
258 |
}
|
williamr@2
|
259 |
bool operator[](size_type pos) const { return test(pos); }
|
williamr@2
|
260 |
|
williamr@2
|
261 |
unsigned long to_ulong() const;
|
williamr@2
|
262 |
|
williamr@2
|
263 |
size_type size() const;
|
williamr@2
|
264 |
size_type num_blocks() const;
|
williamr@2
|
265 |
size_type max_size() const;
|
williamr@2
|
266 |
bool empty() const;
|
williamr@2
|
267 |
#if 0 // gps
|
williamr@2
|
268 |
void reserve(size_type n);
|
williamr@2
|
269 |
size_type capacity() const;
|
williamr@2
|
270 |
#endif
|
williamr@2
|
271 |
|
williamr@2
|
272 |
bool is_subset_of(const dynamic_bitset& a) const;
|
williamr@2
|
273 |
bool is_proper_subset_of(const dynamic_bitset& a) const;
|
williamr@2
|
274 |
bool intersects(const dynamic_bitset & a) const;
|
williamr@2
|
275 |
|
williamr@2
|
276 |
// lookup
|
williamr@2
|
277 |
size_type find_first() const;
|
williamr@2
|
278 |
size_type find_next(size_type pos) const;
|
williamr@2
|
279 |
|
williamr@2
|
280 |
|
williamr@2
|
281 |
#if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS
|
williamr@2
|
282 |
// lexicographical comparison
|
williamr@2
|
283 |
template <typename B, typename A>
|
williamr@2
|
284 |
friend bool operator==(const dynamic_bitset<B, A>& a,
|
williamr@2
|
285 |
const dynamic_bitset<B, A>& b);
|
williamr@2
|
286 |
|
williamr@2
|
287 |
template <typename B, typename A>
|
williamr@2
|
288 |
friend bool operator<(const dynamic_bitset<B, A>& a,
|
williamr@2
|
289 |
const dynamic_bitset<B, A>& b);
|
williamr@2
|
290 |
|
williamr@2
|
291 |
|
williamr@2
|
292 |
template <typename B, typename A, typename BlockOutputIterator>
|
williamr@2
|
293 |
friend void to_block_range(const dynamic_bitset<B, A>& b,
|
williamr@2
|
294 |
BlockOutputIterator result);
|
williamr@2
|
295 |
|
williamr@2
|
296 |
template <typename BlockIterator, typename B, typename A>
|
williamr@2
|
297 |
friend void from_block_range(BlockIterator first, BlockIterator last,
|
williamr@2
|
298 |
dynamic_bitset<B, A>& result);
|
williamr@2
|
299 |
|
williamr@2
|
300 |
|
williamr@2
|
301 |
template <typename CharT, typename Traits, typename B, typename A>
|
williamr@2
|
302 |
friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,
|
williamr@2
|
303 |
dynamic_bitset<B, A>& b);
|
williamr@2
|
304 |
|
williamr@2
|
305 |
template <typename B, typename A, typename stringT>
|
williamr@2
|
306 |
friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);
|
williamr@2
|
307 |
|
williamr@2
|
308 |
|
williamr@2
|
309 |
#endif
|
williamr@2
|
310 |
|
williamr@2
|
311 |
|
williamr@2
|
312 |
private:
|
williamr@2
|
313 |
BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
|
williamr@2
|
314 |
typedef std::vector<block_type, allocator_type> buffer_type;
|
williamr@2
|
315 |
|
williamr@2
|
316 |
void m_zero_unused_bits();
|
williamr@2
|
317 |
bool m_check_invariants() const;
|
williamr@2
|
318 |
|
williamr@2
|
319 |
size_type m_do_find_from(size_type first_block) const;
|
williamr@2
|
320 |
|
williamr@2
|
321 |
block_width_type count_extra_bits() const { return bit_index(size()); }
|
williamr@2
|
322 |
static size_type block_index(size_type pos) { return pos / bits_per_block; }
|
williamr@2
|
323 |
static block_width_type bit_index(size_type pos) { return static_cast<int>(pos % bits_per_block); }
|
williamr@2
|
324 |
static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }
|
williamr@2
|
325 |
|
williamr@2
|
326 |
template <typename CharT, typename Traits, typename Alloc>
|
williamr@2
|
327 |
void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
|
williamr@2
|
328 |
typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
|
williamr@2
|
329 |
typename std::basic_string<CharT, Traits, Alloc>::size_type n,
|
williamr@2
|
330 |
size_type num_bits,
|
williamr@2
|
331 |
const Allocator& alloc)
|
williamr@2
|
332 |
{
|
williamr@2
|
333 |
assert(pos <= s.size());
|
williamr@2
|
334 |
|
williamr@2
|
335 |
typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
|
williamr@2
|
336 |
typedef typename StrT::traits_type Tr;
|
williamr@2
|
337 |
|
williamr@2
|
338 |
const typename StrT::size_type rlen = (std::min)(n, s.size() - pos); // gps
|
williamr@2
|
339 |
const size_type sz = ( num_bits != npos? num_bits : rlen);
|
williamr@2
|
340 |
m_bits.resize(calc_num_blocks(sz));
|
williamr@2
|
341 |
m_num_bits = sz;
|
williamr@2
|
342 |
|
williamr@2
|
343 |
|
williamr@2
|
344 |
BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());
|
williamr@2
|
345 |
const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
|
williamr@2
|
346 |
|
williamr@2
|
347 |
const size_type m = num_bits < rlen ? num_bits : rlen; // [gps]
|
williamr@2
|
348 |
typename StrT::size_type i = 0;
|
williamr@2
|
349 |
for( ; i < m; ++i) {
|
williamr@2
|
350 |
|
williamr@2
|
351 |
const CharT c = s[(pos + m - 1) - i];
|
williamr@2
|
352 |
|
williamr@2
|
353 |
assert( Tr::eq(c, one)
|
williamr@2
|
354 |
|| Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );
|
williamr@2
|
355 |
|
williamr@2
|
356 |
if (Tr::eq(c, one))
|
williamr@2
|
357 |
set(i);
|
williamr@2
|
358 |
|
williamr@2
|
359 |
}
|
williamr@2
|
360 |
|
williamr@2
|
361 |
}
|
williamr@2
|
362 |
|
williamr@2
|
363 |
BOOST_DYNAMIC_BITSET_PRIVATE:
|
williamr@2
|
364 |
|
williamr@2
|
365 |
bool m_unchecked_test(size_type pos) const;
|
williamr@2
|
366 |
static size_type calc_num_blocks(size_type num_bits);
|
williamr@2
|
367 |
|
williamr@2
|
368 |
Block& m_highest_block();
|
williamr@2
|
369 |
const Block& m_highest_block() const;
|
williamr@2
|
370 |
|
williamr@2
|
371 |
buffer_type m_bits; // [gps] to be renamed
|
williamr@2
|
372 |
size_type m_num_bits;
|
williamr@2
|
373 |
|
williamr@2
|
374 |
|
williamr@2
|
375 |
class bit_appender;
|
williamr@2
|
376 |
friend class bit_appender;
|
williamr@2
|
377 |
class bit_appender {
|
williamr@2
|
378 |
// helper for stream >>
|
williamr@2
|
379 |
// Supplies to the lack of an efficient append at the less
|
williamr@2
|
380 |
// significant end: bits are actually appended "at left" but
|
williamr@2
|
381 |
// rearranged in the destructor. Everything works just as if
|
williamr@2
|
382 |
// dynamic_bitset<> had an append_at_right() function (which
|
williamr@2
|
383 |
// threw, in case, the same exceptions as push_back) except
|
williamr@2
|
384 |
// that the function is actually called bit_appender::do_append().
|
williamr@2
|
385 |
//
|
williamr@2
|
386 |
dynamic_bitset & bs;
|
williamr@2
|
387 |
size_type n;
|
williamr@2
|
388 |
Block mask;
|
williamr@2
|
389 |
Block * current;
|
williamr@2
|
390 |
public:
|
williamr@2
|
391 |
bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
|
williamr@2
|
392 |
~bit_appender() {
|
williamr@2
|
393 |
// reverse the order of blocks, shift
|
williamr@2
|
394 |
// if needed, and then resize
|
williamr@2
|
395 |
//
|
williamr@2
|
396 |
std::reverse(bs.m_bits.begin(), bs.m_bits.end());
|
williamr@2
|
397 |
const block_width_type offs = bit_index(n);
|
williamr@2
|
398 |
if (offs)
|
williamr@2
|
399 |
bs >>= (bits_per_block - offs);
|
williamr@2
|
400 |
bs.resize(n); // doesn't enlarge, so can't throw
|
williamr@2
|
401 |
assert(bs.m_check_invariants());
|
williamr@2
|
402 |
}
|
williamr@2
|
403 |
inline void do_append(bool value) {
|
williamr@2
|
404 |
|
williamr@2
|
405 |
if (mask == 0) {
|
williamr@2
|
406 |
bs.append(Block(0));
|
williamr@2
|
407 |
current = &bs.m_highest_block();
|
williamr@2
|
408 |
mask = Block(1) << (bits_per_block - 1);
|
williamr@2
|
409 |
}
|
williamr@2
|
410 |
|
williamr@2
|
411 |
if(value)
|
williamr@2
|
412 |
*current |= mask;
|
williamr@2
|
413 |
|
williamr@2
|
414 |
mask /= 2;
|
williamr@2
|
415 |
++n;
|
williamr@2
|
416 |
}
|
williamr@2
|
417 |
size_type get_count() const { return n; }
|
williamr@2
|
418 |
};
|
williamr@2
|
419 |
|
williamr@2
|
420 |
};
|
williamr@2
|
421 |
|
williamr@2
|
422 |
#if BOOST_WORKAROUND( __IBMCPP__, <=600 )
|
williamr@2
|
423 |
|
williamr@2
|
424 |
// Workaround for IBM's AIX platform.
|
williamr@2
|
425 |
// See http://comments.gmane.org/gmane.comp.lib.boost.user/15331
|
williamr@2
|
426 |
|
williamr@2
|
427 |
template<typename Block, typename Allocator>
|
williamr@2
|
428 |
dynamic_bitset<Block, Allocator>::block_width_type const
|
williamr@2
|
429 |
dynamic_bitset<Block, Allocator>::bits_per_block;
|
williamr@2
|
430 |
|
williamr@2
|
431 |
template<typename Block, typename Allocator>
|
williamr@2
|
432 |
dynamic_bitset<Block, Allocator>::block_width_type const
|
williamr@2
|
433 |
dynamic_bitset<Block, Allocator>::ulong_width;
|
williamr@2
|
434 |
|
williamr@2
|
435 |
#endif
|
williamr@2
|
436 |
|
williamr@2
|
437 |
// Global Functions:
|
williamr@2
|
438 |
|
williamr@2
|
439 |
// comparison
|
williamr@2
|
440 |
template <typename Block, typename Allocator>
|
williamr@2
|
441 |
bool operator!=(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
442 |
const dynamic_bitset<Block, Allocator>& b);
|
williamr@2
|
443 |
|
williamr@2
|
444 |
template <typename Block, typename Allocator>
|
williamr@2
|
445 |
bool operator<=(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
446 |
const dynamic_bitset<Block, Allocator>& b);
|
williamr@2
|
447 |
|
williamr@2
|
448 |
template <typename Block, typename Allocator>
|
williamr@2
|
449 |
bool operator>(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
450 |
const dynamic_bitset<Block, Allocator>& b);
|
williamr@2
|
451 |
|
williamr@2
|
452 |
template <typename Block, typename Allocator>
|
williamr@2
|
453 |
bool operator>=(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
454 |
const dynamic_bitset<Block, Allocator>& b);
|
williamr@2
|
455 |
|
williamr@2
|
456 |
// stream operators
|
williamr@2
|
457 |
#ifdef BOOST_OLD_IOSTREAMS
|
williamr@2
|
458 |
template <typename Block, typename Allocator>
|
williamr@2
|
459 |
std::ostream& operator<<(std::ostream& os,
|
williamr@2
|
460 |
const dynamic_bitset<Block, Allocator>& b);
|
williamr@2
|
461 |
|
williamr@2
|
462 |
template <typename Block, typename Allocator>
|
williamr@2
|
463 |
std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
|
williamr@2
|
464 |
#else
|
williamr@2
|
465 |
// NOTE: Digital Mars wants the same template parameter names
|
williamr@2
|
466 |
// here and in the definition! [last tested: 8.48.10]
|
williamr@2
|
467 |
//
|
williamr@2
|
468 |
template <typename Ch, typename Tr, typename Block, typename Alloc>
|
williamr@2
|
469 |
std::basic_ostream<Ch, Tr>&
|
williamr@2
|
470 |
operator<<(std::basic_ostream<Ch, Tr>& os,
|
williamr@2
|
471 |
const dynamic_bitset<Block, Alloc>& b);
|
williamr@2
|
472 |
|
williamr@2
|
473 |
template <typename Ch, typename Tr, typename Block, typename Alloc>
|
williamr@2
|
474 |
std::basic_istream<Ch, Tr>&
|
williamr@2
|
475 |
operator>>(std::basic_istream<Ch, Tr>& is,
|
williamr@2
|
476 |
dynamic_bitset<Block, Alloc>& b);
|
williamr@2
|
477 |
#endif
|
williamr@2
|
478 |
|
williamr@2
|
479 |
// bitset operations
|
williamr@2
|
480 |
template <typename Block, typename Allocator>
|
williamr@2
|
481 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
482 |
operator&(const dynamic_bitset<Block, Allocator>& b1,
|
williamr@2
|
483 |
const dynamic_bitset<Block, Allocator>& b2);
|
williamr@2
|
484 |
|
williamr@2
|
485 |
template <typename Block, typename Allocator>
|
williamr@2
|
486 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
487 |
operator|(const dynamic_bitset<Block, Allocator>& b1,
|
williamr@2
|
488 |
const dynamic_bitset<Block, Allocator>& b2);
|
williamr@2
|
489 |
|
williamr@2
|
490 |
template <typename Block, typename Allocator>
|
williamr@2
|
491 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
492 |
operator^(const dynamic_bitset<Block, Allocator>& b1,
|
williamr@2
|
493 |
const dynamic_bitset<Block, Allocator>& b2);
|
williamr@2
|
494 |
|
williamr@2
|
495 |
template <typename Block, typename Allocator>
|
williamr@2
|
496 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
497 |
operator-(const dynamic_bitset<Block, Allocator>& b1,
|
williamr@2
|
498 |
const dynamic_bitset<Block, Allocator>& b2);
|
williamr@2
|
499 |
|
williamr@2
|
500 |
// namespace scope swap
|
williamr@2
|
501 |
template<typename Block, typename Allocator>
|
williamr@2
|
502 |
void swap(dynamic_bitset<Block, Allocator>& b1,
|
williamr@2
|
503 |
dynamic_bitset<Block, Allocator>& b2);
|
williamr@2
|
504 |
|
williamr@2
|
505 |
|
williamr@2
|
506 |
template <typename Block, typename Allocator, typename stringT>
|
williamr@2
|
507 |
void
|
williamr@2
|
508 |
to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s); // gps
|
williamr@2
|
509 |
|
williamr@2
|
510 |
template <typename Block, typename Allocator, typename BlockOutputIterator>
|
williamr@2
|
511 |
void
|
williamr@2
|
512 |
to_block_range(const dynamic_bitset<Block, Allocator>& b,
|
williamr@2
|
513 |
BlockOutputIterator result);
|
williamr@2
|
514 |
|
williamr@2
|
515 |
|
williamr@2
|
516 |
// gps - check docs with Jeremy
|
williamr@2
|
517 |
//
|
williamr@2
|
518 |
template <typename BlockIterator, typename B, typename A>
|
williamr@2
|
519 |
inline void
|
williamr@2
|
520 |
from_block_range(BlockIterator first, BlockIterator last,
|
williamr@2
|
521 |
dynamic_bitset<B, A>& result)
|
williamr@2
|
522 |
{
|
williamr@2
|
523 |
// PRE: distance(first, last) <= numblocks()
|
williamr@2
|
524 |
std::copy (first, last, result.m_bits.begin()); //[gps]
|
williamr@2
|
525 |
}
|
williamr@2
|
526 |
|
williamr@2
|
527 |
//=============================================================================
|
williamr@2
|
528 |
// dynamic_bitset implementation
|
williamr@2
|
529 |
|
williamr@2
|
530 |
|
williamr@2
|
531 |
//-----------------------------------------------------------------------------
|
williamr@2
|
532 |
// constructors, etc.
|
williamr@2
|
533 |
|
williamr@2
|
534 |
template <typename Block, typename Allocator>
|
williamr@2
|
535 |
dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
|
williamr@2
|
536 |
: m_bits(alloc), m_num_bits(0)
|
williamr@2
|
537 |
{
|
williamr@2
|
538 |
|
williamr@2
|
539 |
}
|
williamr@2
|
540 |
|
williamr@2
|
541 |
template <typename Block, typename Allocator>
|
williamr@2
|
542 |
dynamic_bitset<Block, Allocator>::
|
williamr@2
|
543 |
dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
|
williamr@2
|
544 |
: m_bits(calc_num_blocks(num_bits), Block(0), alloc),
|
williamr@2
|
545 |
m_num_bits(num_bits)
|
williamr@2
|
546 |
{
|
williamr@2
|
547 |
|
williamr@2
|
548 |
if (num_bits == 0)
|
williamr@2
|
549 |
return;
|
williamr@2
|
550 |
|
williamr@2
|
551 |
typedef unsigned long num_type;
|
williamr@2
|
552 |
|
williamr@2
|
553 |
// cut off all bits in value that have pos >= num_bits, if any
|
williamr@2
|
554 |
if (num_bits < static_cast<size_type>(ulong_width)) {
|
williamr@2
|
555 |
const num_type mask = (num_type(1) << num_bits) - 1;
|
williamr@2
|
556 |
value &= mask;
|
williamr@2
|
557 |
}
|
williamr@2
|
558 |
|
williamr@2
|
559 |
if (bits_per_block >= ulong_width) {
|
williamr@2
|
560 |
m_bits[0] = static_cast<block_type>(value);
|
williamr@2
|
561 |
}
|
williamr@2
|
562 |
else {
|
williamr@2
|
563 |
for(size_type i = 0; value != 0; ++i) {
|
williamr@2
|
564 |
|
williamr@2
|
565 |
m_bits[i] = static_cast<block_type>(value);
|
williamr@2
|
566 |
value >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(bits_per_block);
|
williamr@2
|
567 |
}
|
williamr@2
|
568 |
}
|
williamr@2
|
569 |
|
williamr@2
|
570 |
}
|
williamr@2
|
571 |
|
williamr@2
|
572 |
// copy constructor
|
williamr@2
|
573 |
template <typename Block, typename Allocator>
|
williamr@2
|
574 |
inline dynamic_bitset<Block, Allocator>::
|
williamr@2
|
575 |
dynamic_bitset(const dynamic_bitset& b)
|
williamr@2
|
576 |
: m_bits(b.m_bits), m_num_bits(b.m_num_bits) // [gps]
|
williamr@2
|
577 |
{
|
williamr@2
|
578 |
|
williamr@2
|
579 |
}
|
williamr@2
|
580 |
|
williamr@2
|
581 |
template <typename Block, typename Allocator>
|
williamr@2
|
582 |
inline dynamic_bitset<Block, Allocator>::
|
williamr@2
|
583 |
~dynamic_bitset()
|
williamr@2
|
584 |
{
|
williamr@2
|
585 |
assert(m_check_invariants());
|
williamr@2
|
586 |
}
|
williamr@2
|
587 |
|
williamr@2
|
588 |
template <typename Block, typename Allocator>
|
williamr@2
|
589 |
inline void dynamic_bitset<Block, Allocator>::
|
williamr@2
|
590 |
swap(dynamic_bitset<Block, Allocator>& b) // no throw
|
williamr@2
|
591 |
{
|
williamr@2
|
592 |
std::swap(m_bits, b.m_bits);
|
williamr@2
|
593 |
std::swap(m_num_bits, b.m_num_bits);
|
williamr@2
|
594 |
}
|
williamr@2
|
595 |
|
williamr@2
|
596 |
template <typename Block, typename Allocator>
|
williamr@2
|
597 |
dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
|
williamr@2
|
598 |
operator=(const dynamic_bitset<Block, Allocator>& b)
|
williamr@2
|
599 |
{
|
williamr@2
|
600 |
#if 0 // gps
|
williamr@2
|
601 |
dynamic_bitset<Block, Allocator> tmp(b);
|
williamr@2
|
602 |
this->swap(tmp);
|
williamr@2
|
603 |
return *this;
|
williamr@2
|
604 |
#else
|
williamr@2
|
605 |
m_bits = b.m_bits;
|
williamr@2
|
606 |
m_num_bits = b.m_num_bits;
|
williamr@2
|
607 |
return *this;
|
williamr@2
|
608 |
#endif
|
williamr@2
|
609 |
}
|
williamr@2
|
610 |
|
williamr@2
|
611 |
template <typename Block, typename Allocator>
|
williamr@2
|
612 |
inline typename dynamic_bitset<Block, Allocator>::allocator_type
|
williamr@2
|
613 |
dynamic_bitset<Block, Allocator>::get_allocator() const
|
williamr@2
|
614 |
{
|
williamr@2
|
615 |
return m_bits.get_allocator();
|
williamr@2
|
616 |
}
|
williamr@2
|
617 |
|
williamr@2
|
618 |
//-----------------------------------------------------------------------------
|
williamr@2
|
619 |
// size changing operations
|
williamr@2
|
620 |
|
williamr@2
|
621 |
template <typename Block, typename Allocator>
|
williamr@2
|
622 |
void dynamic_bitset<Block, Allocator>::
|
williamr@2
|
623 |
resize(size_type num_bits, bool value) // strong guarantee
|
williamr@2
|
624 |
{
|
williamr@2
|
625 |
|
williamr@2
|
626 |
const size_type old_num_blocks = num_blocks();
|
williamr@2
|
627 |
const size_type required_blocks = calc_num_blocks(num_bits);
|
williamr@2
|
628 |
|
williamr@2
|
629 |
const block_type v = value? ~Block(0) : Block(0);
|
williamr@2
|
630 |
|
williamr@2
|
631 |
if (required_blocks != old_num_blocks) {
|
williamr@2
|
632 |
m_bits.resize(required_blocks, v); // s.g. (copy) [gps]
|
williamr@2
|
633 |
}
|
williamr@2
|
634 |
|
williamr@2
|
635 |
|
williamr@2
|
636 |
// At this point:
|
williamr@2
|
637 |
//
|
williamr@2
|
638 |
// - if the buffer was shrunk, there's nothing to do, except
|
williamr@2
|
639 |
// a call to m_zero_unused_bits()
|
williamr@2
|
640 |
//
|
williamr@2
|
641 |
// - if it it is enlarged, all the (used) bits in the new blocks have
|
williamr@2
|
642 |
// the correct value, but we should also take care of the bits,
|
williamr@2
|
643 |
// if any, that were 'unused bits' before enlarging: if value == true,
|
williamr@2
|
644 |
// they must be set.
|
williamr@2
|
645 |
|
williamr@2
|
646 |
if (value && (num_bits > m_num_bits)) {
|
williamr@2
|
647 |
|
williamr@2
|
648 |
const size_type extra_bits = count_extra_bits(); // gps
|
williamr@2
|
649 |
if (extra_bits) {
|
williamr@2
|
650 |
assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
|
williamr@2
|
651 |
|
williamr@2
|
652 |
// Set them.
|
williamr@2
|
653 |
m_bits[old_num_blocks - 1] |= (v << extra_bits); // gps
|
williamr@2
|
654 |
}
|
williamr@2
|
655 |
|
williamr@2
|
656 |
}
|
williamr@2
|
657 |
|
williamr@2
|
658 |
|
williamr@2
|
659 |
|
williamr@2
|
660 |
m_num_bits = num_bits;
|
williamr@2
|
661 |
m_zero_unused_bits();
|
williamr@2
|
662 |
|
williamr@2
|
663 |
}
|
williamr@2
|
664 |
|
williamr@2
|
665 |
template <typename Block, typename Allocator>
|
williamr@2
|
666 |
void dynamic_bitset<Block, Allocator>::
|
williamr@2
|
667 |
clear() // no throw
|
williamr@2
|
668 |
{
|
williamr@2
|
669 |
m_bits.clear();
|
williamr@2
|
670 |
m_num_bits = 0;
|
williamr@2
|
671 |
}
|
williamr@2
|
672 |
|
williamr@2
|
673 |
|
williamr@2
|
674 |
template <typename Block, typename Allocator>
|
williamr@2
|
675 |
void dynamic_bitset<Block, Allocator>::
|
williamr@2
|
676 |
push_back(bool bit)
|
williamr@2
|
677 |
{
|
williamr@2
|
678 |
resize(size() + 1);
|
williamr@2
|
679 |
set(size() - 1, bit);
|
williamr@2
|
680 |
}
|
williamr@2
|
681 |
|
williamr@2
|
682 |
template <typename Block, typename Allocator>
|
williamr@2
|
683 |
void dynamic_bitset<Block, Allocator>::
|
williamr@2
|
684 |
append(Block value) // strong guarantee
|
williamr@2
|
685 |
{
|
williamr@2
|
686 |
// G.P.S. to be reviewed...
|
williamr@2
|
687 |
|
williamr@2
|
688 |
const block_width_type r = count_extra_bits();
|
williamr@2
|
689 |
|
williamr@2
|
690 |
if (r == 0) {
|
williamr@2
|
691 |
// the buffer is empty, or all blocks are filled
|
williamr@2
|
692 |
m_bits.push_back(value);
|
williamr@2
|
693 |
}
|
williamr@2
|
694 |
else {
|
williamr@2
|
695 |
m_bits.push_back(value >> (bits_per_block - r));
|
williamr@2
|
696 |
m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
|
williamr@2
|
697 |
}
|
williamr@2
|
698 |
|
williamr@2
|
699 |
m_num_bits += bits_per_block;
|
williamr@2
|
700 |
assert(m_check_invariants());
|
williamr@2
|
701 |
|
williamr@2
|
702 |
}
|
williamr@2
|
703 |
|
williamr@2
|
704 |
|
williamr@2
|
705 |
//-----------------------------------------------------------------------------
|
williamr@2
|
706 |
// bitset operations
|
williamr@2
|
707 |
template <typename Block, typename Allocator>
|
williamr@2
|
708 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
709 |
dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
|
williamr@2
|
710 |
{
|
williamr@2
|
711 |
assert(size() == rhs.size());
|
williamr@2
|
712 |
for (size_type i = 0; i < num_blocks(); ++i)
|
williamr@2
|
713 |
m_bits[i] &= rhs.m_bits[i];
|
williamr@2
|
714 |
return *this;
|
williamr@2
|
715 |
}
|
williamr@2
|
716 |
|
williamr@2
|
717 |
template <typename Block, typename Allocator>
|
williamr@2
|
718 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
719 |
dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
|
williamr@2
|
720 |
{
|
williamr@2
|
721 |
assert(size() == rhs.size());
|
williamr@2
|
722 |
for (size_type i = 0; i < num_blocks(); ++i)
|
williamr@2
|
723 |
m_bits[i] |= rhs.m_bits[i];
|
williamr@2
|
724 |
//m_zero_unused_bits();
|
williamr@2
|
725 |
return *this;
|
williamr@2
|
726 |
}
|
williamr@2
|
727 |
|
williamr@2
|
728 |
template <typename Block, typename Allocator>
|
williamr@2
|
729 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
730 |
dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
|
williamr@2
|
731 |
{
|
williamr@2
|
732 |
assert(size() == rhs.size());
|
williamr@2
|
733 |
for (size_type i = 0; i < this->num_blocks(); ++i)
|
williamr@2
|
734 |
m_bits[i] ^= rhs.m_bits[i];
|
williamr@2
|
735 |
//m_zero_unused_bits();
|
williamr@2
|
736 |
return *this;
|
williamr@2
|
737 |
}
|
williamr@2
|
738 |
|
williamr@2
|
739 |
template <typename Block, typename Allocator>
|
williamr@2
|
740 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
741 |
dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
|
williamr@2
|
742 |
{
|
williamr@2
|
743 |
assert(size() == rhs.size());
|
williamr@2
|
744 |
for (size_type i = 0; i < num_blocks(); ++i)
|
williamr@2
|
745 |
m_bits[i] &= ~rhs.m_bits[i];
|
williamr@2
|
746 |
//m_zero_unused_bits();
|
williamr@2
|
747 |
return *this;
|
williamr@2
|
748 |
}
|
williamr@2
|
749 |
|
williamr@2
|
750 |
//
|
williamr@2
|
751 |
// NOTE:
|
williamr@2
|
752 |
// Note that the 'if (r != 0)' is crucial to avoid undefined
|
williamr@2
|
753 |
// behavior when the left hand operand of >> isn't promoted to a
|
williamr@2
|
754 |
// wider type (because rs would be too large).
|
williamr@2
|
755 |
//
|
williamr@2
|
756 |
template <typename Block, typename Allocator>
|
williamr@2
|
757 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
758 |
dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
|
williamr@2
|
759 |
{
|
williamr@2
|
760 |
if (n >= m_num_bits)
|
williamr@2
|
761 |
return reset();
|
williamr@2
|
762 |
//else
|
williamr@2
|
763 |
if (n > 0) {
|
williamr@2
|
764 |
|
williamr@2
|
765 |
size_type const last = num_blocks() - 1; // num_blocks() is >= 1
|
williamr@2
|
766 |
size_type const div = n / bits_per_block; // div is <= last
|
williamr@2
|
767 |
block_width_type const r = bit_index(n);
|
williamr@2
|
768 |
block_type * const b = &m_bits[0];
|
williamr@2
|
769 |
|
williamr@2
|
770 |
if (r != 0) {
|
williamr@2
|
771 |
|
williamr@2
|
772 |
block_width_type const rs = bits_per_block - r;
|
williamr@2
|
773 |
|
williamr@2
|
774 |
for (size_type i = last-div; i>0; --i) {
|
williamr@2
|
775 |
b[i+div] = (b[i] << r) | (b[i-1] >> rs);
|
williamr@2
|
776 |
}
|
williamr@2
|
777 |
b[div] = b[0] << r;
|
williamr@2
|
778 |
|
williamr@2
|
779 |
}
|
williamr@2
|
780 |
else {
|
williamr@2
|
781 |
for (size_type i = last-div; i>0; --i) {
|
williamr@2
|
782 |
b[i+div] = b[i];
|
williamr@2
|
783 |
}
|
williamr@2
|
784 |
b[div] = b[0];
|
williamr@2
|
785 |
}
|
williamr@2
|
786 |
|
williamr@2
|
787 |
|
williamr@2
|
788 |
// zero out div blocks at the less significant end
|
williamr@2
|
789 |
std::fill_n(b, div, static_cast<block_type>(0));
|
williamr@2
|
790 |
|
williamr@2
|
791 |
// zero out any 1 bit that flowed into the unused part
|
williamr@2
|
792 |
m_zero_unused_bits(); // thanks to Lester Gong
|
williamr@2
|
793 |
|
williamr@2
|
794 |
|
williamr@2
|
795 |
}
|
williamr@2
|
796 |
|
williamr@2
|
797 |
return *this;
|
williamr@2
|
798 |
|
williamr@2
|
799 |
|
williamr@2
|
800 |
}
|
williamr@2
|
801 |
|
williamr@2
|
802 |
|
williamr@2
|
803 |
//
|
williamr@2
|
804 |
// NOTE:
|
williamr@2
|
805 |
// see the comments to operator <<=
|
williamr@2
|
806 |
//
|
williamr@2
|
807 |
template <typename B, typename A>
|
williamr@2
|
808 |
dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
|
williamr@2
|
809 |
if (n >= m_num_bits) {
|
williamr@2
|
810 |
return reset();
|
williamr@2
|
811 |
}
|
williamr@2
|
812 |
//else
|
williamr@2
|
813 |
if (n>0) {
|
williamr@2
|
814 |
|
williamr@2
|
815 |
size_type const last = num_blocks() - 1; // num_blocks() is >= 1
|
williamr@2
|
816 |
size_type const div = n / bits_per_block; // div is <= last
|
williamr@2
|
817 |
block_width_type const r = bit_index(n);
|
williamr@2
|
818 |
block_type * const b = &m_bits[0];
|
williamr@2
|
819 |
|
williamr@2
|
820 |
|
williamr@2
|
821 |
if (r != 0) {
|
williamr@2
|
822 |
|
williamr@2
|
823 |
block_width_type const ls = bits_per_block - r;
|
williamr@2
|
824 |
|
williamr@2
|
825 |
for (size_type i = div; i < last; ++i) {
|
williamr@2
|
826 |
b[i-div] = (b[i] >> r) | (b[i+1] << ls);
|
williamr@2
|
827 |
}
|
williamr@2
|
828 |
// r bits go to zero
|
williamr@2
|
829 |
b[last-div] = b[last] >> r;
|
williamr@2
|
830 |
}
|
williamr@2
|
831 |
|
williamr@2
|
832 |
else {
|
williamr@2
|
833 |
for (size_type i = div; i <= last; ++i) {
|
williamr@2
|
834 |
b[i-div] = b[i];
|
williamr@2
|
835 |
}
|
williamr@2
|
836 |
// note the '<=': the last iteration 'absorbs'
|
williamr@2
|
837 |
// b[last-div] = b[last] >> 0;
|
williamr@2
|
838 |
}
|
williamr@2
|
839 |
|
williamr@2
|
840 |
|
williamr@2
|
841 |
|
williamr@2
|
842 |
// div blocks are zero filled at the most significant end
|
williamr@2
|
843 |
std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0));
|
williamr@2
|
844 |
}
|
williamr@2
|
845 |
|
williamr@2
|
846 |
return *this;
|
williamr@2
|
847 |
}
|
williamr@2
|
848 |
|
williamr@2
|
849 |
|
williamr@2
|
850 |
template <typename Block, typename Allocator>
|
williamr@2
|
851 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
852 |
dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
|
williamr@2
|
853 |
{
|
williamr@2
|
854 |
dynamic_bitset r(*this);
|
williamr@2
|
855 |
return r <<= n;
|
williamr@2
|
856 |
}
|
williamr@2
|
857 |
|
williamr@2
|
858 |
template <typename Block, typename Allocator>
|
williamr@2
|
859 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
860 |
dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
|
williamr@2
|
861 |
{
|
williamr@2
|
862 |
dynamic_bitset r(*this);
|
williamr@2
|
863 |
return r >>= n;
|
williamr@2
|
864 |
}
|
williamr@2
|
865 |
|
williamr@2
|
866 |
|
williamr@2
|
867 |
//-----------------------------------------------------------------------------
|
williamr@2
|
868 |
// basic bit operations
|
williamr@2
|
869 |
|
williamr@2
|
870 |
template <typename Block, typename Allocator>
|
williamr@2
|
871 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
872 |
dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
|
williamr@2
|
873 |
{
|
williamr@2
|
874 |
// [gps]
|
williamr@2
|
875 |
//
|
williamr@2
|
876 |
// Below we have no set(size_type) function to call when
|
williamr@2
|
877 |
// value == true; instead of using a helper, I think
|
williamr@2
|
878 |
// overloading set (rather than giving it a default bool
|
williamr@2
|
879 |
// argument) would be more elegant.
|
williamr@2
|
880 |
|
williamr@2
|
881 |
assert(pos < m_num_bits);
|
williamr@2
|
882 |
|
williamr@2
|
883 |
if (val)
|
williamr@2
|
884 |
m_bits[block_index(pos)] |= bit_mask(pos);
|
williamr@2
|
885 |
else
|
williamr@2
|
886 |
reset(pos);
|
williamr@2
|
887 |
|
williamr@2
|
888 |
return *this;
|
williamr@2
|
889 |
}
|
williamr@2
|
890 |
|
williamr@2
|
891 |
template <typename Block, typename Allocator>
|
williamr@2
|
892 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
893 |
dynamic_bitset<Block, Allocator>::set()
|
williamr@2
|
894 |
{
|
williamr@2
|
895 |
std::fill(m_bits.begin(), m_bits.end(), ~Block(0));
|
williamr@2
|
896 |
m_zero_unused_bits();
|
williamr@2
|
897 |
return *this;
|
williamr@2
|
898 |
}
|
williamr@2
|
899 |
|
williamr@2
|
900 |
template <typename Block, typename Allocator>
|
williamr@2
|
901 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
902 |
dynamic_bitset<Block, Allocator>::reset(size_type pos)
|
williamr@2
|
903 |
{
|
williamr@2
|
904 |
assert(pos < m_num_bits);
|
williamr@2
|
905 |
#if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
|
williamr@2
|
906 |
// CodeWarrior 8 generates incorrect code when the &=~ is compiled,
|
williamr@2
|
907 |
// use the |^ variation instead.. <grafik>
|
williamr@2
|
908 |
m_bits[block_index(pos)] |= bit_mask(pos);
|
williamr@2
|
909 |
m_bits[block_index(pos)] ^= bit_mask(pos);
|
williamr@2
|
910 |
#else
|
williamr@2
|
911 |
m_bits[block_index(pos)] &= ~bit_mask(pos);
|
williamr@2
|
912 |
#endif
|
williamr@2
|
913 |
return *this;
|
williamr@2
|
914 |
}
|
williamr@2
|
915 |
|
williamr@2
|
916 |
template <typename Block, typename Allocator>
|
williamr@2
|
917 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
918 |
dynamic_bitset<Block, Allocator>::reset()
|
williamr@2
|
919 |
{
|
williamr@2
|
920 |
std::fill(m_bits.begin(), m_bits.end(), Block(0));
|
williamr@2
|
921 |
return *this;
|
williamr@2
|
922 |
}
|
williamr@2
|
923 |
|
williamr@2
|
924 |
template <typename Block, typename Allocator>
|
williamr@2
|
925 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
926 |
dynamic_bitset<Block, Allocator>::flip(size_type pos)
|
williamr@2
|
927 |
{
|
williamr@2
|
928 |
assert(pos < m_num_bits);
|
williamr@2
|
929 |
m_bits[block_index(pos)] ^= bit_mask(pos);
|
williamr@2
|
930 |
return *this;
|
williamr@2
|
931 |
}
|
williamr@2
|
932 |
|
williamr@2
|
933 |
template <typename Block, typename Allocator>
|
williamr@2
|
934 |
dynamic_bitset<Block, Allocator>&
|
williamr@2
|
935 |
dynamic_bitset<Block, Allocator>::flip()
|
williamr@2
|
936 |
{
|
williamr@2
|
937 |
for (size_type i = 0; i < num_blocks(); ++i)
|
williamr@2
|
938 |
m_bits[i] = ~m_bits[i];
|
williamr@2
|
939 |
m_zero_unused_bits();
|
williamr@2
|
940 |
return *this;
|
williamr@2
|
941 |
}
|
williamr@2
|
942 |
|
williamr@2
|
943 |
template <typename Block, typename Allocator>
|
williamr@2
|
944 |
bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
|
williamr@2
|
945 |
{
|
williamr@2
|
946 |
return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
|
williamr@2
|
947 |
}
|
williamr@2
|
948 |
|
williamr@2
|
949 |
template <typename Block, typename Allocator>
|
williamr@2
|
950 |
bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
|
williamr@2
|
951 |
{
|
williamr@2
|
952 |
assert(pos < m_num_bits);
|
williamr@2
|
953 |
return m_unchecked_test(pos);
|
williamr@2
|
954 |
}
|
williamr@2
|
955 |
|
williamr@2
|
956 |
template <typename Block, typename Allocator>
|
williamr@2
|
957 |
bool dynamic_bitset<Block, Allocator>::any() const
|
williamr@2
|
958 |
{
|
williamr@2
|
959 |
for (size_type i = 0; i < num_blocks(); ++i)
|
williamr@2
|
960 |
if (m_bits[i])
|
williamr@2
|
961 |
return true;
|
williamr@2
|
962 |
return false;
|
williamr@2
|
963 |
}
|
williamr@2
|
964 |
|
williamr@2
|
965 |
template <typename Block, typename Allocator>
|
williamr@2
|
966 |
inline bool dynamic_bitset<Block, Allocator>::none() const
|
williamr@2
|
967 |
{
|
williamr@2
|
968 |
return !any();
|
williamr@2
|
969 |
}
|
williamr@2
|
970 |
|
williamr@2
|
971 |
template <typename Block, typename Allocator>
|
williamr@2
|
972 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
973 |
dynamic_bitset<Block, Allocator>::operator~() const
|
williamr@2
|
974 |
{
|
williamr@2
|
975 |
dynamic_bitset b(*this);
|
williamr@2
|
976 |
b.flip();
|
williamr@2
|
977 |
return b;
|
williamr@2
|
978 |
}
|
williamr@2
|
979 |
|
williamr@2
|
980 |
|
williamr@2
|
981 |
/*
|
williamr@2
|
982 |
|
williamr@2
|
983 |
The following is the straightforward implementation of count(), which
|
williamr@2
|
984 |
we leave here in a comment for documentation purposes.
|
williamr@2
|
985 |
|
williamr@2
|
986 |
template <typename Block, typename Allocator>
|
williamr@2
|
987 |
typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
988 |
dynamic_bitset<Block, Allocator>::count() const
|
williamr@2
|
989 |
{
|
williamr@2
|
990 |
size_type sum = 0;
|
williamr@2
|
991 |
for (size_type i = 0; i != this->m_num_bits; ++i)
|
williamr@2
|
992 |
if (test(i))
|
williamr@2
|
993 |
++sum;
|
williamr@2
|
994 |
return sum;
|
williamr@2
|
995 |
}
|
williamr@2
|
996 |
|
williamr@2
|
997 |
The actual algorithm uses a lookup table.
|
williamr@2
|
998 |
|
williamr@2
|
999 |
|
williamr@2
|
1000 |
The basic idea of the method is to pick up X bits at a time
|
williamr@2
|
1001 |
from the internal array of blocks and consider those bits as
|
williamr@2
|
1002 |
the binary representation of a number N. Then, to use a table
|
williamr@2
|
1003 |
of 1<<X elements where table[N] is the number of '1' digits
|
williamr@2
|
1004 |
in the binary representation of N (i.e. in our X bits).
|
williamr@2
|
1005 |
|
williamr@2
|
1006 |
|
williamr@2
|
1007 |
In this implementation X is 8 (but can be easily changed: you
|
williamr@2
|
1008 |
just have to modify the definition of table_width and shrink/enlarge
|
williamr@2
|
1009 |
the table accordingly - it could be useful, for instance, to expand
|
williamr@2
|
1010 |
the table to 512 elements on an implementation with 9-bit bytes) and
|
williamr@2
|
1011 |
the internal array of blocks is seen, if possible, as an array of bytes.
|
williamr@2
|
1012 |
In practice the "reinterpretation" as array of bytes is possible if and
|
williamr@2
|
1013 |
only if X >= CHAR_BIT and Block has no padding bits (that would be counted
|
williamr@2
|
1014 |
together with the "real ones" if we saw the array as array of bytes).
|
williamr@2
|
1015 |
Otherwise we simply 'extract' X bits at a time from each Block.
|
williamr@2
|
1016 |
|
williamr@2
|
1017 |
*/
|
williamr@2
|
1018 |
|
williamr@2
|
1019 |
|
williamr@2
|
1020 |
template <typename Block, typename Allocator>
|
williamr@2
|
1021 |
typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
1022 |
dynamic_bitset<Block, Allocator>::count() const
|
williamr@2
|
1023 |
{
|
williamr@2
|
1024 |
using namespace detail::dynamic_bitset_count_impl;
|
williamr@2
|
1025 |
|
williamr@2
|
1026 |
const bool no_padding = bits_per_block == CHAR_BIT * sizeof(Block);
|
williamr@2
|
1027 |
const bool enough_table_width = table_width >= CHAR_BIT;
|
williamr@2
|
1028 |
|
williamr@2
|
1029 |
typedef mode_to_type< (no_padding && enough_table_width ?
|
williamr@2
|
1030 |
access_by_bytes : access_by_blocks) > m;
|
williamr@2
|
1031 |
|
williamr@2
|
1032 |
return do_count(m_bits.begin(), num_blocks(), Block(0), static_cast<m*>(0));
|
williamr@2
|
1033 |
|
williamr@2
|
1034 |
}
|
williamr@2
|
1035 |
|
williamr@2
|
1036 |
|
williamr@2
|
1037 |
//-----------------------------------------------------------------------------
|
williamr@2
|
1038 |
// conversions
|
williamr@2
|
1039 |
|
williamr@2
|
1040 |
|
williamr@2
|
1041 |
template <typename B, typename A, typename stringT>
|
williamr@2
|
1042 |
void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
|
williamr@2
|
1043 |
bool dump_all)
|
williamr@2
|
1044 |
{
|
williamr@2
|
1045 |
typedef typename stringT::traits_type Tr;
|
williamr@2
|
1046 |
typedef typename stringT::value_type Ch;
|
williamr@2
|
1047 |
|
williamr@2
|
1048 |
BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
|
williamr@2
|
1049 |
const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
|
williamr@2
|
1050 |
const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
|
williamr@2
|
1051 |
|
williamr@2
|
1052 |
// Note that this function may access (when
|
williamr@2
|
1053 |
// dump_all == true) bits beyond position size() - 1
|
williamr@2
|
1054 |
|
williamr@2
|
1055 |
typedef typename dynamic_bitset<B, A>::size_type size_type;
|
williamr@2
|
1056 |
|
williamr@2
|
1057 |
const size_type len = dump_all?
|
williamr@2
|
1058 |
dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
|
williamr@2
|
1059 |
b.size();
|
williamr@2
|
1060 |
s.assign (len, zero);
|
williamr@2
|
1061 |
|
williamr@2
|
1062 |
for (size_type i = 0; i < len; ++i) {
|
williamr@2
|
1063 |
if (b.m_unchecked_test(i))
|
williamr@2
|
1064 |
Tr::assign(s[len - 1 - i], one);
|
williamr@2
|
1065 |
|
williamr@2
|
1066 |
}
|
williamr@2
|
1067 |
|
williamr@2
|
1068 |
}
|
williamr@2
|
1069 |
|
williamr@2
|
1070 |
|
williamr@2
|
1071 |
// A comment similar to the one about the constructor from
|
williamr@2
|
1072 |
// basic_string can be done here. Thanks to James Kanze for
|
williamr@2
|
1073 |
// making me (Gennaro) realize this important separation of
|
williamr@2
|
1074 |
// concerns issue, as well as many things about i18n.
|
williamr@2
|
1075 |
//
|
williamr@2
|
1076 |
template <typename Block, typename Allocator, typename stringT> // G.P.S.
|
williamr@2
|
1077 |
inline void
|
williamr@2
|
1078 |
to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
|
williamr@2
|
1079 |
{
|
williamr@2
|
1080 |
to_string_helper(b, s, false);
|
williamr@2
|
1081 |
}
|
williamr@2
|
1082 |
|
williamr@2
|
1083 |
|
williamr@2
|
1084 |
// Differently from to_string this function dumps out
|
williamr@2
|
1085 |
// every bit of the internal representation (may be
|
williamr@2
|
1086 |
// useful for debugging purposes)
|
williamr@2
|
1087 |
//
|
williamr@2
|
1088 |
template <typename B, typename A, typename stringT>
|
williamr@2
|
1089 |
inline void
|
williamr@2
|
1090 |
dump_to_string(const dynamic_bitset<B, A>& b, stringT& s) // G.P.S.
|
williamr@2
|
1091 |
{
|
williamr@2
|
1092 |
to_string_helper(b, s, true /* =dump_all*/);
|
williamr@2
|
1093 |
}
|
williamr@2
|
1094 |
|
williamr@2
|
1095 |
template <typename Block, typename Allocator, typename BlockOutputIterator>
|
williamr@2
|
1096 |
inline void
|
williamr@2
|
1097 |
to_block_range(const dynamic_bitset<Block, Allocator>& b,
|
williamr@2
|
1098 |
BlockOutputIterator result)
|
williamr@2
|
1099 |
{
|
williamr@2
|
1100 |
// note how this copies *all* bits, including the
|
williamr@2
|
1101 |
// unused ones in the last block (which are zero)
|
williamr@2
|
1102 |
std::copy(b.m_bits.begin(), b.m_bits.end(), result); // [gps]
|
williamr@2
|
1103 |
}
|
williamr@2
|
1104 |
|
williamr@2
|
1105 |
template <typename Block, typename Allocator>
|
williamr@2
|
1106 |
unsigned long dynamic_bitset<Block, Allocator>::
|
williamr@2
|
1107 |
to_ulong() const
|
williamr@2
|
1108 |
{
|
williamr@2
|
1109 |
|
williamr@2
|
1110 |
if (m_num_bits == 0)
|
williamr@2
|
1111 |
return 0; // convention
|
williamr@2
|
1112 |
|
williamr@2
|
1113 |
// Check for overflows. This may be a performance burden on very
|
williamr@2
|
1114 |
// large bitsets but is required by the specification, sorry
|
williamr@2
|
1115 |
if (find_next(ulong_width - 1) != npos)
|
williamr@2
|
1116 |
throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");
|
williamr@2
|
1117 |
|
williamr@2
|
1118 |
|
williamr@2
|
1119 |
// Ok, from now on we can be sure there's no "on" bit beyond
|
williamr@2
|
1120 |
// the allowed positions
|
williamr@2
|
1121 |
|
williamr@2
|
1122 |
if (bits_per_block >= ulong_width)
|
williamr@2
|
1123 |
return m_bits[0];
|
williamr@2
|
1124 |
|
williamr@2
|
1125 |
|
williamr@2
|
1126 |
size_type last_block = block_index((std::min)(m_num_bits-1, // gps
|
williamr@2
|
1127 |
(size_type)(ulong_width-1)));
|
williamr@2
|
1128 |
unsigned long result = 0;
|
williamr@2
|
1129 |
for (size_type i = 0; i <= last_block; ++i) {
|
williamr@2
|
1130 |
|
williamr@2
|
1131 |
assert((size_type)bits_per_block * i < (size_type)ulong_width); // gps
|
williamr@2
|
1132 |
|
williamr@2
|
1133 |
unsigned long piece = m_bits[i];
|
williamr@2
|
1134 |
result |= (piece << (bits_per_block * i));
|
williamr@2
|
1135 |
}
|
williamr@2
|
1136 |
|
williamr@2
|
1137 |
return result;
|
williamr@2
|
1138 |
|
williamr@2
|
1139 |
}
|
williamr@2
|
1140 |
|
williamr@2
|
1141 |
|
williamr@2
|
1142 |
template <typename Block, typename Allocator>
|
williamr@2
|
1143 |
inline typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
1144 |
dynamic_bitset<Block, Allocator>::size() const
|
williamr@2
|
1145 |
{
|
williamr@2
|
1146 |
return m_num_bits;
|
williamr@2
|
1147 |
}
|
williamr@2
|
1148 |
|
williamr@2
|
1149 |
template <typename Block, typename Allocator>
|
williamr@2
|
1150 |
inline typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
1151 |
dynamic_bitset<Block, Allocator>::num_blocks() const
|
williamr@2
|
1152 |
{
|
williamr@2
|
1153 |
return m_bits.size();
|
williamr@2
|
1154 |
}
|
williamr@2
|
1155 |
|
williamr@2
|
1156 |
template <typename Block, typename Allocator>
|
williamr@2
|
1157 |
inline typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
1158 |
dynamic_bitset<Block, Allocator>::max_size() const
|
williamr@2
|
1159 |
{
|
williamr@2
|
1160 |
// Semantics of vector<>::max_size() aren't very clear
|
williamr@2
|
1161 |
// (see lib issue 197) and many library implementations
|
williamr@2
|
1162 |
// simply return dummy values, _unrelated_ to the underlying
|
williamr@2
|
1163 |
// allocator.
|
williamr@2
|
1164 |
//
|
williamr@2
|
1165 |
// Given these problems, I was tempted to not provide this
|
williamr@2
|
1166 |
// function at all but the user could need it if he provides
|
williamr@2
|
1167 |
// his own allocator.
|
williamr@2
|
1168 |
//
|
williamr@2
|
1169 |
|
williamr@2
|
1170 |
const size_type m = detail::vector_max_size_workaround(m_bits);
|
williamr@2
|
1171 |
|
williamr@2
|
1172 |
return m <= (size_type(-1)/bits_per_block) ?
|
williamr@2
|
1173 |
m * bits_per_block :
|
williamr@2
|
1174 |
size_type(-1);
|
williamr@2
|
1175 |
}
|
williamr@2
|
1176 |
|
williamr@2
|
1177 |
template <typename Block, typename Allocator>
|
williamr@2
|
1178 |
inline bool dynamic_bitset<Block, Allocator>::empty() const
|
williamr@2
|
1179 |
{
|
williamr@2
|
1180 |
return size() == 0;
|
williamr@2
|
1181 |
}
|
williamr@2
|
1182 |
|
williamr@2
|
1183 |
#if 0 // gps
|
williamr@2
|
1184 |
template <typename Block, typename Allocator>
|
williamr@2
|
1185 |
inline void dynamic_bitset<Block, Allocator>::reserve(size_type n)
|
williamr@2
|
1186 |
{
|
williamr@2
|
1187 |
assert(n <= max_size()); // PRE - G.P.S.
|
williamr@2
|
1188 |
m_bits.reserve(calc_num_blocks(n));
|
williamr@2
|
1189 |
}
|
williamr@2
|
1190 |
|
williamr@2
|
1191 |
template <typename Block, typename Allocator>
|
williamr@2
|
1192 |
typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
1193 |
dynamic_bitset<Block, Allocator>::capacity() const
|
williamr@2
|
1194 |
{
|
williamr@2
|
1195 |
// capacity is m_bits.capacity() * bits_per_block
|
williamr@2
|
1196 |
// unless that one overflows
|
williamr@2
|
1197 |
const size_type m = static_cast<size_type>(-1);
|
williamr@2
|
1198 |
const size_type q = m / bits_per_block;
|
williamr@2
|
1199 |
|
williamr@2
|
1200 |
const size_type c = m_bits.capacity();
|
williamr@2
|
1201 |
|
williamr@2
|
1202 |
return c <= q ?
|
williamr@2
|
1203 |
c * bits_per_block :
|
williamr@2
|
1204 |
m;
|
williamr@2
|
1205 |
}
|
williamr@2
|
1206 |
#endif
|
williamr@2
|
1207 |
|
williamr@2
|
1208 |
template <typename Block, typename Allocator>
|
williamr@2
|
1209 |
bool dynamic_bitset<Block, Allocator>::
|
williamr@2
|
1210 |
is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
|
williamr@2
|
1211 |
{
|
williamr@2
|
1212 |
assert(size() == a.size());
|
williamr@2
|
1213 |
for (size_type i = 0; i < num_blocks(); ++i)
|
williamr@2
|
1214 |
if (m_bits[i] & ~a.m_bits[i])
|
williamr@2
|
1215 |
return false;
|
williamr@2
|
1216 |
return true;
|
williamr@2
|
1217 |
}
|
williamr@2
|
1218 |
|
williamr@2
|
1219 |
template <typename Block, typename Allocator>
|
williamr@2
|
1220 |
bool dynamic_bitset<Block, Allocator>::
|
williamr@2
|
1221 |
is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
|
williamr@2
|
1222 |
{
|
williamr@2
|
1223 |
assert(size() == a.size());
|
williamr@2
|
1224 |
bool proper = false;
|
williamr@2
|
1225 |
for (size_type i = 0; i < num_blocks(); ++i) {
|
williamr@2
|
1226 |
Block bt = m_bits[i], ba = a.m_bits[i];
|
williamr@2
|
1227 |
if (ba & ~bt)
|
williamr@2
|
1228 |
proper = true;
|
williamr@2
|
1229 |
if (bt & ~ba)
|
williamr@2
|
1230 |
return false;
|
williamr@2
|
1231 |
}
|
williamr@2
|
1232 |
return proper;
|
williamr@2
|
1233 |
}
|
williamr@2
|
1234 |
|
williamr@2
|
1235 |
template <typename Block, typename Allocator>
|
williamr@2
|
1236 |
bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
|
williamr@2
|
1237 |
{
|
williamr@2
|
1238 |
size_type common_blocks = num_blocks() < b.num_blocks()
|
williamr@2
|
1239 |
? num_blocks() : b.num_blocks();
|
williamr@2
|
1240 |
|
williamr@2
|
1241 |
for(size_type i = 0; i < common_blocks; ++i) {
|
williamr@2
|
1242 |
if(m_bits[i] & b.m_bits[i])
|
williamr@2
|
1243 |
return true;
|
williamr@2
|
1244 |
}
|
williamr@2
|
1245 |
return false;
|
williamr@2
|
1246 |
}
|
williamr@2
|
1247 |
|
williamr@2
|
1248 |
// --------------------------------
|
williamr@2
|
1249 |
// lookup
|
williamr@2
|
1250 |
|
williamr@2
|
1251 |
|
williamr@2
|
1252 |
// look for the first bit "on", starting
|
williamr@2
|
1253 |
// from the block with index first_block
|
williamr@2
|
1254 |
//
|
williamr@2
|
1255 |
template <typename Block, typename Allocator>
|
williamr@2
|
1256 |
typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
1257 |
dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
|
williamr@2
|
1258 |
{
|
williamr@2
|
1259 |
size_type i = first_block;
|
williamr@2
|
1260 |
|
williamr@2
|
1261 |
// skip null blocks
|
williamr@2
|
1262 |
while (i < num_blocks() && m_bits[i] == 0)
|
williamr@2
|
1263 |
++i;
|
williamr@2
|
1264 |
|
williamr@2
|
1265 |
if (i >= num_blocks())
|
williamr@2
|
1266 |
return npos; // not found
|
williamr@2
|
1267 |
|
williamr@2
|
1268 |
return i * bits_per_block + boost::lowest_bit(m_bits[i]);
|
williamr@2
|
1269 |
|
williamr@2
|
1270 |
}
|
williamr@2
|
1271 |
|
williamr@2
|
1272 |
|
williamr@2
|
1273 |
template <typename Block, typename Allocator>
|
williamr@2
|
1274 |
typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
1275 |
dynamic_bitset<Block, Allocator>::find_first() const
|
williamr@2
|
1276 |
{
|
williamr@2
|
1277 |
return m_do_find_from(0);
|
williamr@2
|
1278 |
}
|
williamr@2
|
1279 |
|
williamr@2
|
1280 |
|
williamr@2
|
1281 |
template <typename Block, typename Allocator>
|
williamr@2
|
1282 |
typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
1283 |
dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
|
williamr@2
|
1284 |
{
|
williamr@2
|
1285 |
|
williamr@2
|
1286 |
const size_type sz = size();
|
williamr@2
|
1287 |
if (pos >= (sz-1) || sz == 0)
|
williamr@2
|
1288 |
return npos;
|
williamr@2
|
1289 |
|
williamr@2
|
1290 |
++pos;
|
williamr@2
|
1291 |
|
williamr@2
|
1292 |
const size_type blk = block_index(pos);
|
williamr@2
|
1293 |
const block_width_type ind = bit_index(pos);
|
williamr@2
|
1294 |
|
williamr@2
|
1295 |
// mask out bits before pos
|
williamr@2
|
1296 |
const Block fore = m_bits[blk] & ( ~Block(0) << ind );
|
williamr@2
|
1297 |
|
williamr@2
|
1298 |
return fore?
|
williamr@2
|
1299 |
blk * bits_per_block + lowest_bit(fore)
|
williamr@2
|
1300 |
:
|
williamr@2
|
1301 |
m_do_find_from(blk + 1);
|
williamr@2
|
1302 |
|
williamr@2
|
1303 |
}
|
williamr@2
|
1304 |
|
williamr@2
|
1305 |
|
williamr@2
|
1306 |
|
williamr@2
|
1307 |
//-----------------------------------------------------------------------------
|
williamr@2
|
1308 |
// comparison
|
williamr@2
|
1309 |
|
williamr@2
|
1310 |
template <typename Block, typename Allocator>
|
williamr@2
|
1311 |
bool operator==(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
1312 |
const dynamic_bitset<Block, Allocator>& b)
|
williamr@2
|
1313 |
{
|
williamr@2
|
1314 |
return (a.m_num_bits == b.m_num_bits)
|
williamr@2
|
1315 |
&& (a.m_bits == b.m_bits); // [gps]
|
williamr@2
|
1316 |
}
|
williamr@2
|
1317 |
|
williamr@2
|
1318 |
template <typename Block, typename Allocator>
|
williamr@2
|
1319 |
inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
1320 |
const dynamic_bitset<Block, Allocator>& b)
|
williamr@2
|
1321 |
{
|
williamr@2
|
1322 |
return !(a == b);
|
williamr@2
|
1323 |
}
|
williamr@2
|
1324 |
|
williamr@2
|
1325 |
template <typename Block, typename Allocator>
|
williamr@2
|
1326 |
bool operator<(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
1327 |
const dynamic_bitset<Block, Allocator>& b)
|
williamr@2
|
1328 |
{
|
williamr@2
|
1329 |
assert(a.size() == b.size());
|
williamr@2
|
1330 |
typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;
|
williamr@2
|
1331 |
|
williamr@2
|
1332 |
if (a.size() == 0)
|
williamr@2
|
1333 |
return false;
|
williamr@2
|
1334 |
|
williamr@2
|
1335 |
// Since we are storing the most significant bit
|
williamr@2
|
1336 |
// at pos == size() - 1, we need to do the comparisons in reverse.
|
williamr@2
|
1337 |
|
williamr@2
|
1338 |
// Compare a block at a time
|
williamr@2
|
1339 |
for (size_type i = a.num_blocks() - 1; i > 0; --i)
|
williamr@2
|
1340 |
if (a.m_bits[i] < b.m_bits[i])
|
williamr@2
|
1341 |
return true;
|
williamr@2
|
1342 |
else if (a.m_bits[i] > b.m_bits[i])
|
williamr@2
|
1343 |
return false;
|
williamr@2
|
1344 |
|
williamr@2
|
1345 |
if (a.m_bits[0] < b.m_bits[0])
|
williamr@2
|
1346 |
return true;
|
williamr@2
|
1347 |
else
|
williamr@2
|
1348 |
return false;
|
williamr@2
|
1349 |
}
|
williamr@2
|
1350 |
|
williamr@2
|
1351 |
template <typename Block, typename Allocator>
|
williamr@2
|
1352 |
inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
1353 |
const dynamic_bitset<Block, Allocator>& b)
|
williamr@2
|
1354 |
{
|
williamr@2
|
1355 |
return !(a > b);
|
williamr@2
|
1356 |
}
|
williamr@2
|
1357 |
|
williamr@2
|
1358 |
template <typename Block, typename Allocator>
|
williamr@2
|
1359 |
inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
1360 |
const dynamic_bitset<Block, Allocator>& b)
|
williamr@2
|
1361 |
{
|
williamr@2
|
1362 |
return b < a;
|
williamr@2
|
1363 |
}
|
williamr@2
|
1364 |
|
williamr@2
|
1365 |
template <typename Block, typename Allocator>
|
williamr@2
|
1366 |
inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
|
williamr@2
|
1367 |
const dynamic_bitset<Block, Allocator>& b)
|
williamr@2
|
1368 |
{
|
williamr@2
|
1369 |
return !(a < b);
|
williamr@2
|
1370 |
}
|
williamr@2
|
1371 |
|
williamr@2
|
1372 |
//-----------------------------------------------------------------------------
|
williamr@2
|
1373 |
// stream operations
|
williamr@2
|
1374 |
|
williamr@2
|
1375 |
#ifdef BOOST_OLD_IOSTREAMS
|
williamr@2
|
1376 |
template < typename Block, typename Alloc>
|
williamr@2
|
1377 |
std::ostream&
|
williamr@2
|
1378 |
operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
|
williamr@2
|
1379 |
{
|
williamr@2
|
1380 |
// NOTE: since this is aimed at "classic" iostreams, exception
|
williamr@2
|
1381 |
// masks on the stream are not supported. The library that
|
williamr@2
|
1382 |
// ships with gcc 2.95 has an exceptions() member function but
|
williamr@2
|
1383 |
// nothing is actually implemented; not even the class ios::failure.
|
williamr@2
|
1384 |
|
williamr@2
|
1385 |
using namespace std;
|
williamr@2
|
1386 |
|
williamr@2
|
1387 |
const ios::iostate ok = ios::goodbit;
|
williamr@2
|
1388 |
ios::iostate err = ok;
|
williamr@2
|
1389 |
|
williamr@2
|
1390 |
if (os.opfx()) { // gps
|
williamr@2
|
1391 |
|
williamr@2
|
1392 |
//try
|
williamr@2
|
1393 |
typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
|
williamr@2
|
1394 |
|
williamr@2
|
1395 |
const bitsetsize_type sz = b.size();
|
williamr@2
|
1396 |
std::streambuf * buf = os.rdbuf();
|
williamr@2
|
1397 |
size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0)
|
williamr@2
|
1398 |
|| (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz; //- gps
|
williamr@2
|
1399 |
|
williamr@2
|
1400 |
const char fill_char = os.fill();
|
williamr@2
|
1401 |
const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
|
williamr@2
|
1402 |
|
williamr@2
|
1403 |
// if needed fill at left; pad is decresed along the way
|
williamr@2
|
1404 |
if (adjustfield != ios::left) {
|
williamr@2
|
1405 |
for (; 0 < npad; --npad)
|
williamr@2
|
1406 |
if (fill_char != buf->sputc(fill_char)) {
|
williamr@2
|
1407 |
err |= ios::failbit; // gps
|
williamr@2
|
1408 |
break;
|
williamr@2
|
1409 |
}
|
williamr@2
|
1410 |
}
|
williamr@2
|
1411 |
|
williamr@2
|
1412 |
if (err == ok) {
|
williamr@2
|
1413 |
// output the bitset
|
williamr@2
|
1414 |
for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
|
williamr@2
|
1415 |
const char dig = b.test(i-1)? '1' : '0';
|
williamr@2
|
1416 |
if (EOF == buf->sputc(dig)) { // ok?? gps
|
williamr@2
|
1417 |
err |= ios::failbit;
|
williamr@2
|
1418 |
break;
|
williamr@2
|
1419 |
}
|
williamr@2
|
1420 |
}
|
williamr@2
|
1421 |
}
|
williamr@2
|
1422 |
|
williamr@2
|
1423 |
if (err == ok) {
|
williamr@2
|
1424 |
// if needed fill at right
|
williamr@2
|
1425 |
for (; 0 < npad; --npad) {
|
williamr@2
|
1426 |
if (fill_char != buf->sputc(fill_char)) {
|
williamr@2
|
1427 |
err |= ios::failbit;
|
williamr@2
|
1428 |
break;
|
williamr@2
|
1429 |
}
|
williamr@2
|
1430 |
}
|
williamr@2
|
1431 |
}
|
williamr@2
|
1432 |
|
williamr@2
|
1433 |
os.osfx();
|
williamr@2
|
1434 |
os.width(0);
|
williamr@2
|
1435 |
|
williamr@2
|
1436 |
} // if opfx
|
williamr@2
|
1437 |
|
williamr@2
|
1438 |
if(err != ok)
|
williamr@2
|
1439 |
os.setstate(err); // assume this does NOT throw - gps
|
williamr@2
|
1440 |
return os;
|
williamr@2
|
1441 |
|
williamr@2
|
1442 |
}
|
williamr@2
|
1443 |
#else
|
williamr@2
|
1444 |
|
williamr@2
|
1445 |
template <typename Ch, typename Tr, typename Block, typename Alloc>
|
williamr@2
|
1446 |
std::basic_ostream<Ch, Tr>&
|
williamr@2
|
1447 |
operator<<(std::basic_ostream<Ch, Tr>& os,
|
williamr@2
|
1448 |
const dynamic_bitset<Block, Alloc>& b)
|
williamr@2
|
1449 |
{
|
williamr@2
|
1450 |
|
williamr@2
|
1451 |
using namespace std;
|
williamr@2
|
1452 |
|
williamr@2
|
1453 |
const ios_base::iostate ok = ios_base::goodbit;
|
williamr@2
|
1454 |
ios_base::iostate err = ok;
|
williamr@2
|
1455 |
|
williamr@2
|
1456 |
typename basic_ostream<Ch, Tr>::sentry cerberos(os);
|
williamr@2
|
1457 |
if (cerberos) {
|
williamr@2
|
1458 |
|
williamr@2
|
1459 |
BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
|
williamr@2
|
1460 |
const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
|
williamr@2
|
1461 |
const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
|
williamr@2
|
1462 |
|
williamr@2
|
1463 |
try {
|
williamr@2
|
1464 |
|
williamr@2
|
1465 |
typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
|
williamr@2
|
1466 |
typedef basic_streambuf<Ch, Tr> buffer_type; // G.P.S.
|
williamr@2
|
1467 |
|
williamr@2
|
1468 |
buffer_type * buf = os.rdbuf();
|
williamr@2
|
1469 |
size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0)
|
williamr@2
|
1470 |
|| (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size(); //- G.P.S.
|
williamr@2
|
1471 |
|
williamr@2
|
1472 |
const Ch fill_char = os.fill();
|
williamr@2
|
1473 |
const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
|
williamr@2
|
1474 |
|
williamr@2
|
1475 |
// if needed fill at left; pad is decresed along the way
|
williamr@2
|
1476 |
if (adjustfield != ios_base::left) {
|
williamr@2
|
1477 |
for (; 0 < npad; --npad)
|
williamr@2
|
1478 |
if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
|
williamr@2
|
1479 |
err |= ios_base::failbit; // G.P.S.
|
williamr@2
|
1480 |
break;
|
williamr@2
|
1481 |
}
|
williamr@2
|
1482 |
}
|
williamr@2
|
1483 |
|
williamr@2
|
1484 |
if (err == ok) {
|
williamr@2
|
1485 |
// output the bitset
|
williamr@2
|
1486 |
for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
|
williamr@2
|
1487 |
typename buffer_type::int_type
|
williamr@2
|
1488 |
ret = buf->sputc(b.test(i-1)? one : zero);
|
williamr@2
|
1489 |
if (Tr::eq_int_type(Tr::eof(), ret)) {
|
williamr@2
|
1490 |
err |= ios_base::failbit;
|
williamr@2
|
1491 |
break;
|
williamr@2
|
1492 |
}
|
williamr@2
|
1493 |
}
|
williamr@2
|
1494 |
}
|
williamr@2
|
1495 |
|
williamr@2
|
1496 |
if (err == ok) {
|
williamr@2
|
1497 |
// if needed fill at right
|
williamr@2
|
1498 |
for (; 0 < npad; --npad) {
|
williamr@2
|
1499 |
if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
|
williamr@2
|
1500 |
err |= ios_base::failbit;
|
williamr@2
|
1501 |
break;
|
williamr@2
|
1502 |
}
|
williamr@2
|
1503 |
}
|
williamr@2
|
1504 |
}
|
williamr@2
|
1505 |
|
williamr@2
|
1506 |
|
williamr@2
|
1507 |
os.width(0);
|
williamr@2
|
1508 |
|
williamr@2
|
1509 |
} catch (...) { // see std 27.6.1.1/4
|
williamr@2
|
1510 |
bool rethrow = false;
|
williamr@2
|
1511 |
try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }
|
williamr@2
|
1512 |
|
williamr@2
|
1513 |
if (rethrow)
|
williamr@2
|
1514 |
throw;
|
williamr@2
|
1515 |
}
|
williamr@2
|
1516 |
}
|
williamr@2
|
1517 |
|
williamr@2
|
1518 |
if(err != ok)
|
williamr@2
|
1519 |
os.setstate(err); // may throw exception
|
williamr@2
|
1520 |
return os;
|
williamr@2
|
1521 |
|
williamr@2
|
1522 |
}
|
williamr@2
|
1523 |
#endif
|
williamr@2
|
1524 |
|
williamr@2
|
1525 |
|
williamr@2
|
1526 |
#ifdef BOOST_OLD_IOSTREAMS
|
williamr@2
|
1527 |
|
williamr@2
|
1528 |
// gps - A sentry-like class that calls isfx in its
|
williamr@2
|
1529 |
// destructor. Necessary because bit_appender::do_append may throw.
|
williamr@2
|
1530 |
class pseudo_sentry {
|
williamr@2
|
1531 |
std::istream & m_r;
|
williamr@2
|
1532 |
const bool m_ok;
|
williamr@2
|
1533 |
public:
|
williamr@2
|
1534 |
explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
|
williamr@2
|
1535 |
~pseudo_sentry() { m_r.isfx(); }
|
williamr@2
|
1536 |
operator bool() const { return m_ok; }
|
williamr@2
|
1537 |
};
|
williamr@2
|
1538 |
|
williamr@2
|
1539 |
template <typename Block, typename Alloc>
|
williamr@2
|
1540 |
std::istream&
|
williamr@2
|
1541 |
operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
|
williamr@2
|
1542 |
{
|
williamr@2
|
1543 |
|
williamr@2
|
1544 |
// Extractor for classic IO streams (libstdc++ < 3.0)
|
williamr@2
|
1545 |
// ----------------------------------------------------//
|
williamr@2
|
1546 |
// It's assumed that the stream buffer functions, and
|
williamr@2
|
1547 |
// the stream's setstate() _cannot_ throw.
|
williamr@2
|
1548 |
|
williamr@2
|
1549 |
|
williamr@2
|
1550 |
typedef dynamic_bitset<Block, Alloc> bitset_type;
|
williamr@2
|
1551 |
typedef typename bitset_type::size_type size_type;
|
williamr@2
|
1552 |
|
williamr@2
|
1553 |
std::ios::iostate err = std::ios::goodbit; // gps
|
williamr@2
|
1554 |
pseudo_sentry cerberos(is); // skips whitespaces
|
williamr@2
|
1555 |
if(cerberos) {
|
williamr@2
|
1556 |
|
williamr@2
|
1557 |
b.clear();
|
williamr@2
|
1558 |
|
williamr@2
|
1559 |
const std::streamsize w = is.width();
|
williamr@2
|
1560 |
const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()// gps
|
williamr@2
|
1561 |
? w : b.max_size();
|
williamr@2
|
1562 |
typename bitset_type::bit_appender appender(b);
|
williamr@2
|
1563 |
std::streambuf * buf = is.rdbuf();
|
williamr@2
|
1564 |
for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
|
williamr@2
|
1565 |
|
williamr@2
|
1566 |
if (c == EOF) {
|
williamr@2
|
1567 |
err |= std::ios::eofbit; // G.P.S.
|
williamr@2
|
1568 |
break;
|
williamr@2
|
1569 |
}
|
williamr@2
|
1570 |
else if (char(c) != '0' && char(c) != '1')
|
williamr@2
|
1571 |
break; // non digit character
|
williamr@2
|
1572 |
|
williamr@2
|
1573 |
else {
|
williamr@2
|
1574 |
try {
|
williamr@2
|
1575 |
//throw std::bad_alloc(); // gps
|
williamr@2
|
1576 |
appender.do_append(char(c) == '1');
|
williamr@2
|
1577 |
}
|
williamr@2
|
1578 |
catch(...) {
|
williamr@2
|
1579 |
is.setstate(std::ios::failbit); // assume this can't throw
|
williamr@2
|
1580 |
throw;
|
williamr@2
|
1581 |
}
|
williamr@2
|
1582 |
}
|
williamr@2
|
1583 |
|
williamr@2
|
1584 |
} // for
|
williamr@2
|
1585 |
}
|
williamr@2
|
1586 |
|
williamr@2
|
1587 |
is.width(0); // gps
|
williamr@2
|
1588 |
if (b.size() == 0)
|
williamr@2
|
1589 |
err |= std::ios::failbit;
|
williamr@2
|
1590 |
if (err != std::ios::goodbit) // gps
|
williamr@2
|
1591 |
is.setstate (err); // may throw
|
williamr@2
|
1592 |
|
williamr@2
|
1593 |
return is;
|
williamr@2
|
1594 |
}
|
williamr@2
|
1595 |
|
williamr@2
|
1596 |
#else // BOOST_OLD_IOSTREAMS
|
williamr@2
|
1597 |
|
williamr@2
|
1598 |
template <typename Ch, typename Tr, typename Block, typename Alloc>
|
williamr@2
|
1599 |
std::basic_istream<Ch, Tr>&
|
williamr@2
|
1600 |
operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
|
williamr@2
|
1601 |
{
|
williamr@2
|
1602 |
|
williamr@2
|
1603 |
using namespace std;
|
williamr@2
|
1604 |
|
williamr@2
|
1605 |
typedef dynamic_bitset<Block, Alloc> bitset_type;
|
williamr@2
|
1606 |
typedef typename bitset_type::size_type size_type;
|
williamr@2
|
1607 |
|
williamr@2
|
1608 |
const streamsize w = is.width();
|
williamr@2
|
1609 |
const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()? // gps
|
williamr@2
|
1610 |
w : b.max_size();
|
williamr@2
|
1611 |
|
williamr@2
|
1612 |
ios_base::iostate err = ios_base::goodbit; // gps
|
williamr@2
|
1613 |
typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
|
williamr@2
|
1614 |
if(cerberos) {
|
williamr@2
|
1615 |
|
williamr@2
|
1616 |
// in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
|
williamr@2
|
1617 |
BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
|
williamr@2
|
1618 |
const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
|
williamr@2
|
1619 |
const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
|
williamr@2
|
1620 |
|
williamr@2
|
1621 |
b.clear();
|
williamr@2
|
1622 |
try {
|
williamr@2
|
1623 |
typename bitset_type::bit_appender appender(b);
|
williamr@2
|
1624 |
basic_streambuf <Ch, Tr> * buf = is.rdbuf();
|
williamr@2
|
1625 |
typename Tr::int_type c = buf->sgetc(); // G.P.S.
|
williamr@2
|
1626 |
for( ; appender.get_count() < limit; c = buf->snextc() ) {
|
williamr@2
|
1627 |
|
williamr@2
|
1628 |
if (Tr::eq_int_type(Tr::eof(), c)) {
|
williamr@2
|
1629 |
err |= ios_base::eofbit; // G.P.S.
|
williamr@2
|
1630 |
break;
|
williamr@2
|
1631 |
}
|
williamr@2
|
1632 |
else {
|
williamr@2
|
1633 |
const Ch to_c = Tr::to_char_type(c);
|
williamr@2
|
1634 |
const bool is_one = Tr::eq(to_c, one);
|
williamr@2
|
1635 |
|
williamr@2
|
1636 |
if (!is_one && !Tr::eq(to_c, zero))
|
williamr@2
|
1637 |
break; // non digit character
|
williamr@2
|
1638 |
|
williamr@2
|
1639 |
appender.do_append(is_one);
|
williamr@2
|
1640 |
|
williamr@2
|
1641 |
}
|
williamr@2
|
1642 |
|
williamr@2
|
1643 |
} // for
|
williamr@2
|
1644 |
}
|
williamr@2
|
1645 |
catch (...) {
|
williamr@2
|
1646 |
// catches from stream buf, or from vector:
|
williamr@2
|
1647 |
//
|
williamr@2
|
1648 |
// bits_stored bits have been extracted and stored, and
|
williamr@2
|
1649 |
// either no further character is extractable or we can't
|
williamr@2
|
1650 |
// append to the underlying vector (out of memory) gps
|
williamr@2
|
1651 |
|
williamr@2
|
1652 |
bool rethrow = false; // see std 27.6.1.1/4
|
williamr@2
|
1653 |
try { is.setstate(ios_base::badbit); }
|
williamr@2
|
1654 |
catch(...) { rethrow = true; }
|
williamr@2
|
1655 |
|
williamr@2
|
1656 |
if (rethrow)
|
williamr@2
|
1657 |
throw;
|
williamr@2
|
1658 |
|
williamr@2
|
1659 |
}
|
williamr@2
|
1660 |
}
|
williamr@2
|
1661 |
|
williamr@2
|
1662 |
is.width(0); // gps
|
williamr@2
|
1663 |
if (b.size() == 0 /*|| !cerberos*/)
|
williamr@2
|
1664 |
err |= ios_base::failbit;
|
williamr@2
|
1665 |
if (err != ios_base::goodbit) // gps
|
williamr@2
|
1666 |
is.setstate (err); // may throw
|
williamr@2
|
1667 |
|
williamr@2
|
1668 |
return is;
|
williamr@2
|
1669 |
|
williamr@2
|
1670 |
}
|
williamr@2
|
1671 |
|
williamr@2
|
1672 |
|
williamr@2
|
1673 |
#endif
|
williamr@2
|
1674 |
|
williamr@2
|
1675 |
|
williamr@2
|
1676 |
//-----------------------------------------------------------------------------
|
williamr@2
|
1677 |
// bitset operations
|
williamr@2
|
1678 |
|
williamr@2
|
1679 |
template <typename Block, typename Allocator>
|
williamr@2
|
1680 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
1681 |
operator&(const dynamic_bitset<Block, Allocator>& x,
|
williamr@2
|
1682 |
const dynamic_bitset<Block, Allocator>& y)
|
williamr@2
|
1683 |
{
|
williamr@2
|
1684 |
dynamic_bitset<Block, Allocator> b(x);
|
williamr@2
|
1685 |
return b &= y;
|
williamr@2
|
1686 |
}
|
williamr@2
|
1687 |
|
williamr@2
|
1688 |
template <typename Block, typename Allocator>
|
williamr@2
|
1689 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
1690 |
operator|(const dynamic_bitset<Block, Allocator>& x,
|
williamr@2
|
1691 |
const dynamic_bitset<Block, Allocator>& y)
|
williamr@2
|
1692 |
{
|
williamr@2
|
1693 |
dynamic_bitset<Block, Allocator> b(x);
|
williamr@2
|
1694 |
return b |= y;
|
williamr@2
|
1695 |
}
|
williamr@2
|
1696 |
|
williamr@2
|
1697 |
template <typename Block, typename Allocator>
|
williamr@2
|
1698 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
1699 |
operator^(const dynamic_bitset<Block, Allocator>& x,
|
williamr@2
|
1700 |
const dynamic_bitset<Block, Allocator>& y)
|
williamr@2
|
1701 |
{
|
williamr@2
|
1702 |
dynamic_bitset<Block, Allocator> b(x);
|
williamr@2
|
1703 |
return b ^= y;
|
williamr@2
|
1704 |
}
|
williamr@2
|
1705 |
|
williamr@2
|
1706 |
template <typename Block, typename Allocator>
|
williamr@2
|
1707 |
dynamic_bitset<Block, Allocator>
|
williamr@2
|
1708 |
operator-(const dynamic_bitset<Block, Allocator>& x,
|
williamr@2
|
1709 |
const dynamic_bitset<Block, Allocator>& y)
|
williamr@2
|
1710 |
{
|
williamr@2
|
1711 |
dynamic_bitset<Block, Allocator> b(x);
|
williamr@2
|
1712 |
return b -= y;
|
williamr@2
|
1713 |
}
|
williamr@2
|
1714 |
|
williamr@2
|
1715 |
//-----------------------------------------------------------------------------
|
williamr@2
|
1716 |
// namespace scope swap
|
williamr@2
|
1717 |
|
williamr@2
|
1718 |
template<typename Block, typename Allocator>
|
williamr@2
|
1719 |
inline void
|
williamr@2
|
1720 |
swap(dynamic_bitset<Block, Allocator>& left,
|
williamr@2
|
1721 |
dynamic_bitset<Block, Allocator>& right) // no throw
|
williamr@2
|
1722 |
{
|
williamr@2
|
1723 |
left.swap(right); // gps
|
williamr@2
|
1724 |
}
|
williamr@2
|
1725 |
|
williamr@2
|
1726 |
|
williamr@2
|
1727 |
//-----------------------------------------------------------------------------
|
williamr@2
|
1728 |
// private (on conforming compilers) member functions
|
williamr@2
|
1729 |
|
williamr@2
|
1730 |
|
williamr@2
|
1731 |
template <typename Block, typename Allocator>
|
williamr@2
|
1732 |
inline typename dynamic_bitset<Block, Allocator>::size_type
|
williamr@2
|
1733 |
dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
|
williamr@2
|
1734 |
{
|
williamr@2
|
1735 |
return num_bits / bits_per_block
|
williamr@2
|
1736 |
+ static_cast<int>( num_bits % bits_per_block != 0 );
|
williamr@2
|
1737 |
}
|
williamr@2
|
1738 |
|
williamr@2
|
1739 |
// gives a reference to the highest block
|
williamr@2
|
1740 |
//
|
williamr@2
|
1741 |
template <typename Block, typename Allocator>
|
williamr@2
|
1742 |
inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
|
williamr@2
|
1743 |
{
|
williamr@2
|
1744 |
return const_cast<Block &>
|
williamr@2
|
1745 |
(static_cast<const dynamic_bitset *>(this)->m_highest_block());
|
williamr@2
|
1746 |
}
|
williamr@2
|
1747 |
|
williamr@2
|
1748 |
// gives a const-reference to the highest block
|
williamr@2
|
1749 |
//
|
williamr@2
|
1750 |
template <typename Block, typename Allocator>
|
williamr@2
|
1751 |
inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
|
williamr@2
|
1752 |
{
|
williamr@2
|
1753 |
assert(size() > 0 && num_blocks() > 0);
|
williamr@2
|
1754 |
return m_bits.back();
|
williamr@2
|
1755 |
}
|
williamr@2
|
1756 |
|
williamr@2
|
1757 |
|
williamr@2
|
1758 |
// If size() is not a multiple of bits_per_block
|
williamr@2
|
1759 |
// then not all the bits in the last block are used.
|
williamr@2
|
1760 |
// This function resets the unused bits (convenient
|
williamr@2
|
1761 |
// for the implementation of many member functions)
|
williamr@2
|
1762 |
//
|
williamr@2
|
1763 |
template <typename Block, typename Allocator>
|
williamr@2
|
1764 |
inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
|
williamr@2
|
1765 |
{
|
williamr@2
|
1766 |
assert (num_blocks() == calc_num_blocks(m_num_bits));
|
williamr@2
|
1767 |
|
williamr@2
|
1768 |
// if != 0 this is the number of bits used in the last block
|
williamr@2
|
1769 |
const block_width_type extra_bits = count_extra_bits();
|
williamr@2
|
1770 |
|
williamr@2
|
1771 |
if (extra_bits != 0)
|
williamr@2
|
1772 |
m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
|
williamr@2
|
1773 |
|
williamr@2
|
1774 |
}
|
williamr@2
|
1775 |
|
williamr@2
|
1776 |
// check class invariants
|
williamr@2
|
1777 |
template <typename Block, typename Allocator>
|
williamr@2
|
1778 |
bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
|
williamr@2
|
1779 |
{
|
williamr@2
|
1780 |
const block_width_type extra_bits = count_extra_bits();
|
williamr@2
|
1781 |
if (extra_bits > 0) {
|
williamr@2
|
1782 |
block_type const mask = (~static_cast<Block>(0) << extra_bits);
|
williamr@2
|
1783 |
if ((m_highest_block() & mask) != 0)
|
williamr@2
|
1784 |
return false;
|
williamr@2
|
1785 |
}
|
williamr@2
|
1786 |
if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
|
williamr@2
|
1787 |
return false;
|
williamr@2
|
1788 |
|
williamr@2
|
1789 |
return true;
|
williamr@2
|
1790 |
|
williamr@2
|
1791 |
}
|
williamr@2
|
1792 |
|
williamr@2
|
1793 |
|
williamr@2
|
1794 |
} // namespace boost
|
williamr@2
|
1795 |
|
williamr@2
|
1796 |
|
williamr@2
|
1797 |
#undef BOOST_BITSET_CHAR
|
williamr@2
|
1798 |
|
williamr@2
|
1799 |
#endif // include guard
|
williamr@2
|
1800 |
|