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;
148 size_t capacity()
const
150 return 8 * block_count_ *
sizeof(block_t);
155 bool get(
size_t pos)
const
157 SPOT_ASSERT(pos < size_);
158 const size_t bpb = 8 *
sizeof(block_t);
159 return storage_[pos / bpb] & (1UL << (pos % bpb));
164 for (
size_t i = 0; i < block_count_; ++i)
168 bool is_fully_clear()
const
171 const size_t bpb = 8 *
sizeof(bitvect::block_t);
172 size_t rest = size() % bpb;
173 for (i = 0; i < block_count_ - !!rest; ++i)
174 if (storage_[i] != 0)
180 block_t mask = (1UL << rest) - 1;
181 return (storage_[i] & mask) == 0;
184 bool is_fully_set()
const
187 const size_t bpb = 8 *
sizeof(bitvect::block_t);
188 size_t rest = size() % bpb;
189 for (i = 0; i < block_count_ - !!rest; ++i)
190 if (storage_[i] != -1UL)
196 block_t mask = (1UL << rest) - 1;
197 return ((~storage_[i]) & mask) == 0;
202 for (
size_t i = 0; i < block_count_; ++i)
208 for (
size_t i = 0; i < block_count_; ++i)
209 storage_[i] = ~storage_[i];
214 SPOT_ASSERT(pos < size_);
215 const size_t bpb = 8 *
sizeof(block_t);
216 storage_[pos / bpb] |= 1UL << (pos % bpb);
219 void clear(
size_t pos)
221 SPOT_ASSERT(pos < size_);
222 const size_t bpb = 8 *
sizeof(block_t);
223 storage_[pos / bpb] &= ~(1UL << (pos % bpb));
226 void flip(
size_t pos)
228 SPOT_ASSERT(pos < size_);
229 const size_t bpb = 8 *
sizeof(block_t);
230 storage_[pos / bpb] ^= (1UL << (pos % bpb));
234 bitvect& operator|=(
const bitvect& other)
236 SPOT_ASSERT(other.size_ <= size_);
237 unsigned m = std::min(other.block_count_, block_count_);
238 for (
size_t i = 0; i < m; ++i)
239 storage_[i] |= other.storage_[i];
243 bitvect& operator&=(
const bitvect& other)
245 SPOT_ASSERT(other.size_ <= size_);
246 unsigned m = std::min(other.block_count_, block_count_);
247 for (
size_t i = 0; i < m; ++i)
248 storage_[i] &= other.storage_[i];
252 bitvect& operator^=(
const bitvect& other)
254 SPOT_ASSERT(other.size_ <= size_);
255 unsigned m = std::min(other.block_count_, block_count_);
256 for (
size_t i = 0; i < m; ++i)
257 storage_[i] ^= other.storage_[i];
261 bitvect& operator-=(
const bitvect& other)
263 SPOT_ASSERT(other.block_count_ <= block_count_);
264 for (
size_t i = 0; i < other.block_count_; ++i)
265 storage_[i] &= ~other.storage_[i];
269 bool is_subset_of(
const bitvect& other)
const
271 SPOT_ASSERT(other.block_count_ >= block_count_);
274 const size_t bpb = 8 *
sizeof(bitvect::block_t);
275 size_t rest = size() % bpb;
276 for (i = 0; i < block_count_ - !!rest; ++i)
277 if ((storage_[i] & other.storage_[i]) != storage_[i])
284 block_t mask = (1UL << rest) - 1;
285 return ((storage_[i] & mask & other.storage_[i])
286 == (storage_[i] & mask));
289 bool operator==(
const bitvect& other)
const
291 if (other.size_ != size_)
296 size_t m = other.used_blocks();
297 const size_t bpb = 8 *
sizeof(bitvect::block_t);
298 size_t rest = size() % bpb;
299 for (i = 0; i < m - !!rest; ++i)
300 if (storage_[i] != other.storage_[i])
306 block_t mask = (1UL << rest) - 1;
307 return (storage_[i] & mask) == (other.storage_[i] & mask);
310 bool operator!=(
const bitvect& other)
const
312 return !(*
this == other);
315 bool operator<(
const bitvect& other)
const
317 if (size_ != other.size_)
318 return size_ < other.size_;
322 size_t m = other.used_blocks();
323 const size_t bpb = 8 *
sizeof(bitvect::block_t);
324 size_t rest = size() % bpb;
325 for (i = 0; i < m - !!rest; ++i)
326 if (storage_[i] > other.storage_[i])
332 block_t mask = (1UL << rest) - 1;
333 return (storage_[i] & mask) < (other.storage_[i] & mask);
336 bool operator>=(
const bitvect& other)
const
338 return !(*
this < other);
341 bool operator>(
const bitvect& other)
const
343 return other < *
this;
346 bool operator<=(
const bitvect& other)
const
348 return !(other < *
this);
351 friend SPOT_API bitvect* make_bitvect(
size_t bitcount);
354 friend SPOT_API std::ostream& operator<<(std::ostream&,
358 friend SPOT_API bitvect_array* make_bitvect_array(
size_t bitcount,
367 block_t local_storage_;
386 return reinterpret_cast<char*
>(
this) +
sizeof(*
this);
389 const char* storage()
const
391 return reinterpret_cast<const char*
>(
this) +
sizeof(*
this);
397 for (
size_t i = 0; i < size_; ++i)
410 SPOT_ASSERT(index < size_);
411 return *
reinterpret_cast<bitvect*
>(storage() + index * bvsize_);
418 for (
unsigned s = 0; s < size_; s++)
425 SPOT_ASSERT(index < size_);
426 return *
reinterpret_cast<const bitvect*
>(storage() + index * bvsize_);
429 friend SPOT_API
bitvect_array* make_bitvect_array(
size_t bitcount,
434 friend SPOT_API std::ostream& operator<<(std::ostream&,
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:402
const bitvect & at(const size_t index) const
Return the bit-vector at index.
Definition: bitvect.hh:423
Definition: bitvect.hh:370
bitvect & at(const size_t index)
Return the bit-vector at index.
Definition: bitvect.hh:408
void reserve_blocks(size_t new_block_count)
Definition: bitvect.hh:102
A bit vector.
Definition: bitvect.hh:51