22 #include <spot/misc/common.hh>
42 SPOT_API bitvect* make_bitvect(
size_t bitcount);
47 SPOT_API bitvect_array* make_bitvect_array(
size_t bitcount,
55 bitvect(
size_t size,
size_t block_count);
56 bitvect(
size_t size,
size_t block_count,
bool);
59 typedef unsigned long block_t;
64 storage_(&local_storage_),
72 storage_(&local_storage_)
86 reserve_blocks(other.block_count_);
88 for (
size_t i = 0; i < block_count_; ++i)
89 storage_[i] = other.storage_[i];
95 if (storage_ != &local_storage_)
104 if (new_block_count < block_count_)
106 if (storage_ == &local_storage_)
108 block_t* new_storage_ =
static_cast<block_t*
>
109 (malloc(new_block_count *
sizeof(block_t)));
110 for (
size_t i = 0; i < block_count_; ++i)
111 new_storage_[i] = storage_[i];
112 storage_ = new_storage_;
117 storage_ =
static_cast<block_t*
>
118 (realloc(old, new_block_count *
sizeof(block_t)));
122 throw std::bad_alloc();
125 block_count_ = new_block_count;
131 size_t new_block_count_ = (block_count_ + 1) * 7 / 5;
132 reserve_blocks(new_block_count_);
137 size_t used_blocks()
const
139 const size_t bpb = 8 *
sizeof(block_t);
140 return (size_ + bpb - 1) / bpb;
146 if (size() == capacity())
148 size_t pos = size_++;
158 if (size() + count > capacity())
160 const size_t bpb = 8 *
sizeof(block_t);
164 data &= (1UL << count) - 1;
166 size_t n = size() % bpb;
167 size_t i = size_ / bpb;
176 block_t mask = (1UL << (bpb - n)) - 1;
177 block_t data1 = (data & mask) << n;
180 storage_[i] = (storage_[i] & ~mask) | data1;
183 storage_[i + 1] = data >> (bpb - n);
192 size_t capacity()
const
194 return 8 * block_count_ *
sizeof(block_t);
199 bool get(
size_t pos)
const
201 SPOT_ASSERT(pos < size_);
202 const size_t bpb = 8 *
sizeof(block_t);
203 return storage_[pos / bpb] & (1UL << (pos % bpb));
208 for (
size_t i = 0; i < block_count_; ++i)
212 bool is_fully_clear()
const
215 const size_t bpb = 8 *
sizeof(bitvect::block_t);
216 size_t rest = size() % bpb;
217 for (i = 0; i < block_count_ - !!rest; ++i)
218 if (storage_[i] != 0)
224 block_t mask = (1UL << rest) - 1;
225 return (storage_[i] & mask) == 0;
228 bool is_fully_set()
const
231 const size_t bpb = 8 *
sizeof(bitvect::block_t);
232 size_t rest = size() % bpb;
233 for (i = 0; i < block_count_ - !!rest; ++i)
234 if (storage_[i] != -1UL)
240 block_t mask = (1UL << rest) - 1;
241 return ((~storage_[i]) & mask) == 0;
246 for (
size_t i = 0; i < block_count_; ++i)
252 for (
size_t i = 0; i < block_count_; ++i)
253 storage_[i] = ~storage_[i];
258 SPOT_ASSERT(pos < size_);
259 const size_t bpb = 8 *
sizeof(block_t);
260 storage_[pos / bpb] |= 1UL << (pos % bpb);
263 void clear(
size_t pos)
265 SPOT_ASSERT(pos < size_);
266 const size_t bpb = 8 *
sizeof(block_t);
267 storage_[pos / bpb] &= ~(1UL << (pos % bpb));
270 void flip(
size_t pos)
272 SPOT_ASSERT(pos < size_);
273 const size_t bpb = 8 *
sizeof(block_t);
274 storage_[pos / bpb] ^= (1UL << (pos % bpb));
278 bitvect& operator|=(
const bitvect& other)
280 SPOT_ASSERT(other.size_ <= size_);
281 unsigned m = std::min(other.block_count_, block_count_);
282 for (
size_t i = 0; i < m; ++i)
283 storage_[i] |= other.storage_[i];
287 bitvect& operator&=(
const bitvect& other)
289 SPOT_ASSERT(other.size_ <= size_);
290 unsigned m = std::min(other.block_count_, block_count_);
291 for (
size_t i = 0; i < m; ++i)
292 storage_[i] &= other.storage_[i];
296 bitvect& operator^=(
const bitvect& other)
298 SPOT_ASSERT(other.size_ <= size_);
299 unsigned m = std::min(other.block_count_, block_count_);
300 for (
size_t i = 0; i < m; ++i)
301 storage_[i] ^= other.storage_[i];
305 bitvect& operator-=(
const bitvect& other)
307 SPOT_ASSERT(other.block_count_ <= block_count_);
308 for (
size_t i = 0; i < other.block_count_; ++i)
309 storage_[i] &= ~other.storage_[i];
313 bool is_subset_of(
const bitvect& other)
const
315 SPOT_ASSERT(other.block_count_ >= block_count_);
318 const size_t bpb = 8 *
sizeof(bitvect::block_t);
319 size_t rest = size() % bpb;
320 for (i = 0; i < block_count_ - !!rest; ++i)
321 if ((storage_[i] & other.storage_[i]) != storage_[i])
328 block_t mask = (1UL << rest) - 1;
329 return ((storage_[i] & mask & other.storage_[i])
330 == (storage_[i] & mask));
333 bool operator==(
const bitvect& other)
const
335 if (other.size_ != size_)
340 size_t m = other.used_blocks();
341 const size_t bpb = 8 *
sizeof(bitvect::block_t);
342 size_t rest = size() % bpb;
343 for (i = 0; i < m - !!rest; ++i)
344 if (storage_[i] != other.storage_[i])
350 block_t mask = (1UL << rest) - 1;
351 return (storage_[i] & mask) == (other.storage_[i] & mask);
354 bool operator!=(
const bitvect& other)
const
356 return !(*
this == other);
359 bool operator<(
const bitvect& other)
const
361 if (size_ != other.size_)
362 return size_ < other.size_;
366 size_t m = other.used_blocks();
367 const size_t bpb = 8 *
sizeof(bitvect::block_t);
368 size_t rest = size() % bpb;
369 for (i = 0; i < m - !!rest; ++i)
370 if (storage_[i] > other.storage_[i])
376 block_t mask = (1UL << rest) - 1;
377 return (storage_[i] & mask) < (other.storage_[i] & mask);
380 bool operator>=(
const bitvect& other)
const
382 return !(*
this < other);
385 bool operator>(
const bitvect& other)
const
387 return other < *
this;
390 bool operator<=(
const bitvect& other)
const
392 return !(other < *
this);
399 bitvect* extract_range(
size_t begin,
size_t end)
401 SPOT_ASSERT(begin <= end);
402 SPOT_ASSERT(end <= size());
403 size_t count = end - begin;
404 bitvect* res = make_bitvect(count);
410 const size_t bpb = 8 *
sizeof(bitvect::block_t);
412 size_t indexb = begin / bpb;
413 unsigned bitb = begin % bpb;
414 size_t indexe = (end - 1) / bpb;
416 if (indexb == indexe)
418 block_t data = storage_[indexb];
420 res->push_back(data, count);
424 block_t data = storage_[indexb];
426 res->push_back(data, bpb - bitb);
431 res->push_back(storage_[indexb], bpb);
433 SPOT_ASSERT(indexb != indexe || count == 0);
438 SPOT_ASSERT(indexb == indexe);
439 SPOT_ASSERT(count == end % bpb);
440 res->push_back(storage_[indexb], count);
446 friend SPOT_API bitvect* make_bitvect(
size_t bitcount);
449 friend SPOT_API std::ostream& operator<<(std::ostream&,
453 friend SPOT_API bitvect_array* make_bitvect_array(
size_t bitcount,
462 block_t local_storage_;
481 return reinterpret_cast<char*
>(
this) +
sizeof(*
this);
484 const char* storage()
const
486 return reinterpret_cast<const char*
>(
this) +
sizeof(*
this);
492 for (
size_t i = 0; i < size_; ++i)
505 SPOT_ASSERT(index < size_);
506 return *
reinterpret_cast<bitvect*
>(storage() + index * bvsize_);
513 for (
unsigned s = 0; s < size_; s++)
520 SPOT_ASSERT(index < size_);
521 return *
reinterpret_cast<const bitvect*
>(storage() + index * bvsize_);
524 friend SPOT_API
bitvect_array* make_bitvect_array(
size_t bitcount,
529 friend SPOT_API std::ostream& operator<<(std::ostream&,
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:497
const bitvect & at(const size_t index) const
Return the bit-vector at index.
Definition: bitvect.hh:518
void push_back(bool val)
Append one bit.
Definition: bitvect.hh:144
Definition: bitvect.hh:465
void push_back(block_t data, unsigned count)
Append the lowest count bits of data.
Definition: bitvect.hh:156
bitvect & at(const size_t index)
Return the bit-vector at index.
Definition: bitvect.hh:503
void reserve_blocks(size_t new_block_count)
Definition: bitvect.hh:102
A bit vector.
Definition: bitvect.hh:51