22 #include <spot/misc/common.hh>
41 SPOT_API bitvect* make_bitvect(
size_t bitcount);
46 SPOT_API bitvect_array* make_bitvect_array(
size_t bitcount,
54 bitvect(
size_t size,
size_t block_count);
55 bitvect(
size_t size,
size_t block_count,
bool);
58 typedef unsigned long block_t;
63 storage_(&local_storage_),
71 storage_(&local_storage_)
85 reserve_blocks(other.block_count_);
87 for (
size_t i = 0; i < block_count_; ++i)
88 storage_[i] = other.storage_[i];
94 if (storage_ != &local_storage_)
103 if (new_block_count < block_count_)
105 if (storage_ == &local_storage_)
107 block_t* new_storage_ =
static_cast<block_t*
>
108 (malloc(new_block_count *
sizeof(block_t)));
109 for (
size_t i = 0; i < block_count_; ++i)
110 new_storage_[i] = storage_[i];
111 storage_ = new_storage_;
115 storage_ =
static_cast<block_t*
>
116 (realloc(storage_, new_block_count *
sizeof(block_t)));
118 block_count_ = new_block_count;
124 size_t new_block_count_ = (block_count_ + 1) * 7 / 5;
125 reserve_blocks(new_block_count_);
130 size_t used_blocks()
const
132 const size_t bpb = 8 *
sizeof(block_t);
133 return (size_ + bpb - 1) / bpb;
139 if (size() == capacity())
141 size_t pos = size_++;
151 if (size() + count > capacity())
153 const size_t bpb = 8 *
sizeof(block_t);
157 data &= (1UL << count) - 1;
159 size_t n = size() % bpb;
160 size_t i = size_ / bpb;
169 block_t mask = (1UL << (bpb - n)) - 1;
170 block_t data1 = (data & mask) << n;
173 storage_[i] = (storage_[i] & ~mask) | data1;
176 storage_[i + 1] = data >> (bpb - n);
185 size_t capacity()
const
187 return 8 * block_count_ *
sizeof(block_t);
192 bool get(
size_t pos)
const
194 SPOT_ASSERT(pos < size_);
195 const size_t bpb = 8 *
sizeof(block_t);
196 return storage_[pos / bpb] & (1UL << (pos % bpb));
201 for (
size_t i = 0; i < block_count_; ++i)
205 bool is_fully_clear()
const
208 const size_t bpb = 8 *
sizeof(bitvect::block_t);
209 size_t rest = size() % bpb;
210 for (i = 0; i < block_count_ - !!rest; ++i)
211 if (storage_[i] != 0)
217 block_t mask = (1UL << rest) - 1;
218 return (storage_[i] & mask) == 0;
221 bool is_fully_set()
const
224 const size_t bpb = 8 *
sizeof(bitvect::block_t);
225 size_t rest = size() % bpb;
226 for (i = 0; i < block_count_ - !!rest; ++i)
227 if (storage_[i] != -1UL)
233 block_t mask = (1UL << rest) - 1;
234 return ((~storage_[i]) & mask) == 0;
239 for (
size_t i = 0; i < block_count_; ++i)
245 for (
size_t i = 0; i < block_count_; ++i)
246 storage_[i] = ~storage_[i];
251 SPOT_ASSERT(pos < size_);
252 const size_t bpb = 8 *
sizeof(block_t);
253 storage_[pos / bpb] |= 1UL << (pos % bpb);
256 void clear(
size_t pos)
258 SPOT_ASSERT(pos < size_);
259 const size_t bpb = 8 *
sizeof(block_t);
260 storage_[pos / bpb] &= ~(1UL << (pos % bpb));
263 void flip(
size_t pos)
265 SPOT_ASSERT(pos < size_);
266 const size_t bpb = 8 *
sizeof(block_t);
267 storage_[pos / bpb] ^= (1UL << (pos % bpb));
271 bitvect& operator|=(
const bitvect& other)
273 SPOT_ASSERT(other.size_ <= size_);
274 unsigned m = std::min(other.block_count_, block_count_);
275 for (
size_t i = 0; i < m; ++i)
276 storage_[i] |= other.storage_[i];
280 bitvect& operator&=(
const bitvect& other)
282 SPOT_ASSERT(other.size_ <= size_);
283 unsigned m = std::min(other.block_count_, block_count_);
284 for (
size_t i = 0; i < m; ++i)
285 storage_[i] &= other.storage_[i];
289 bitvect& operator^=(
const bitvect& other)
291 SPOT_ASSERT(other.size_ <= size_);
292 unsigned m = std::min(other.block_count_, block_count_);
293 for (
size_t i = 0; i < m; ++i)
294 storage_[i] ^= other.storage_[i];
298 bitvect& operator-=(
const bitvect& other)
300 SPOT_ASSERT(other.block_count_ <= block_count_);
301 for (
size_t i = 0; i < other.block_count_; ++i)
302 storage_[i] &= ~other.storage_[i];
306 bool is_subset_of(
const bitvect& other)
const
308 SPOT_ASSERT(other.block_count_ >= block_count_);
311 const size_t bpb = 8 *
sizeof(bitvect::block_t);
312 size_t rest = size() % bpb;
313 for (i = 0; i < block_count_ - !!rest; ++i)
314 if ((storage_[i] & other.storage_[i]) != other.storage_[i])
321 block_t mask = (1UL << rest) - 1;
322 return ((storage_[i] & mask & other.storage_[i])
323 == (other.storage_[i] & mask));
326 bool operator==(
const bitvect& other)
const
328 if (other.size_ != size_)
333 size_t m = other.used_blocks();
334 const size_t bpb = 8 *
sizeof(bitvect::block_t);
335 size_t rest = size() % bpb;
336 for (i = 0; i < m - !!rest; ++i)
337 if (storage_[i] != other.storage_[i])
343 block_t mask = (1UL << rest) - 1;
344 return (storage_[i] & mask) == (other.storage_[i] & mask);
347 bool operator!=(
const bitvect& other)
const
349 return !(*
this == other);
352 bool operator<(
const bitvect& other)
const
354 if (size_ != other.size_)
355 return size_ < other.size_;
359 size_t m = other.used_blocks();
360 const size_t bpb = 8 *
sizeof(bitvect::block_t);
361 size_t rest = size() % bpb;
362 for (i = 0; i < m - !!rest; ++i)
363 if (storage_[i] > other.storage_[i])
369 block_t mask = (1UL << rest) - 1;
370 return (storage_[i] & mask) < (other.storage_[i] & mask);
373 bool operator>=(
const bitvect& other)
const
375 return !(*
this < other);
378 bool operator>(
const bitvect& other)
const
380 return other < *
this;
383 bool operator<=(
const bitvect& other)
const
385 return !(other < *
this);
392 bitvect* extract_range(
size_t begin,
size_t end)
394 SPOT_ASSERT(begin <= end);
395 SPOT_ASSERT(end <= size());
396 size_t count = end - begin;
397 bitvect* res = make_bitvect(count);
403 const size_t bpb = 8 *
sizeof(bitvect::block_t);
405 size_t indexb = begin / bpb;
406 unsigned bitb = begin % bpb;
407 size_t indexe = (end - 1) / bpb;
409 if (indexb == indexe)
411 block_t data = storage_[indexb];
413 res->push_back(data, count);
417 block_t data = storage_[indexb];
419 res->push_back(data, bpb - bitb);
424 res->push_back(storage_[indexb], bpb);
426 SPOT_ASSERT(indexb != indexe || count == 0);
431 SPOT_ASSERT(indexb == indexe);
432 SPOT_ASSERT(count == end % bpb);
433 res->push_back(storage_[indexb], count);
439 friend SPOT_API bitvect* make_bitvect(
size_t bitcount);
442 friend SPOT_API std::ostream& operator<<(std::ostream&,
446 friend SPOT_API bitvect_array* make_bitvect_array(
size_t bitcount,
455 block_t local_storage_;
474 return reinterpret_cast<char*
>(
this) +
sizeof(*
this);
477 const char* storage()
const
479 return reinterpret_cast<const char*
>(
this) +
sizeof(*
this);
485 for (
size_t i = 0; i < size_; ++i)
498 SPOT_ASSERT(index < size_);
499 return *
reinterpret_cast<bitvect*
>(storage() + index * bvsize_);
506 for (
unsigned s = 0; s < size_; s++)
513 SPOT_ASSERT(index < size_);
514 return *
reinterpret_cast<const bitvect*
>(storage() + index * bvsize_);
517 friend SPOT_API
bitvect_array* make_bitvect_array(
size_t bitcount,
522 friend SPOT_API std::ostream& operator<<(std::ostream&,
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:490
const bitvect & at(const size_t index) const
Return the bit-vector at index.
Definition: bitvect.hh:511
void push_back(bool val)
Append one bit.
Definition: bitvect.hh:137
Definition: bitvect.hh:458
void push_back(block_t data, unsigned count)
Append the lowest count bits of data.
Definition: bitvect.hh:149
bitvect & at(const size_t index)
Return the bit-vector at index.
Definition: bitvect.hh:496
void reserve_blocks(size_t new_block_count)
Definition: bitvect.hh:101
A bit vector.
Definition: bitvect.hh:50