32 #include "MemoryPool.hpp" 33 #include "MyHashTable.hpp" 39 static size_t const offset = (N == 0) ? 1 : 0;
41 uint64_t array_[(N == 0) ? 1 : N];
43 uint64_t& word(
size_t i) {
44 assert(i < numWords());
45 return array_[i + offset];
48 uint64_t word(
size_t i)
const {
49 assert(i < numWords());
50 return array_[i + offset];
53 uint64_t mask(
size_t i)
const {
54 return uint64_t(1) << i;
58 MyBitSet(uint64_t n = 0) {
60 for (
size_t i = (N == 0) ? 0 : 1; i < numWords(); ++i) {
69 size_t numWords()
const {
70 return (N == 0) ? array_[0] : N;
78 for (
size_t i = 0; i < numWords(); ++i) {
88 for (
size_t i = 0; i < numWords(); ++i) {
89 if (word(i) != 0)
return false;
99 uint64_t& w = word(i / 64);
100 uint64_t m = mask(i % 64);
108 void remove(
size_t i) {
109 uint64_t& w = word(i / 64);
110 uint64_t m = mask(i % 64);
119 void pullout(
size_t i) {
121 uint64_t* p = &word(k);
122 uint64_t* q = p + numWords();
123 uint64_t m = mask(i % 64 + 1) - 1;
124 *p = (*p & ~m) | ((*p << 1) & m);
126 *(p - 1) |= *p >> 63;
136 bool includes(
size_t i)
const {
137 uint64_t w = word(i / 64);
138 uint64_t m = mask(i % 64);
147 bool intersects(MyBitSet
const& o)
const {
148 size_t n = std::min(numWords(), o.numWords());
149 for (
size_t i = 0; i < n; ++i) {
150 if (word(i) & o.word(i))
return true;
155 class const_iterator {
156 MyBitSet
const& bitSet;
162 const_iterator(MyBitSet
const& bitSet) :
163 bitSet(bitSet), wordPos(bitSet.numWords()), bitPos(-1), word(0) {
166 const_iterator(MyBitSet
const& bitSet,
size_t i) :
167 bitSet(bitSet), wordPos(i), bitPos(-1), word(bitSet.word(i)) {
171 size_t operator*()
const {
172 return wordPos * 64 + bitPos;
175 const_iterator& operator++() {
178 if (++wordPos >= bitSet.numWords()) {
179 wordPos = bitSet.numWords();
182 word = bitSet.word(wordPos);
185 if (word == uint64_t(1) << 63) {
190 int k = __builtin_ffsll(word);
209 bool operator==(const_iterator
const& o)
const {
210 return wordPos == o.wordPos && bitPos == o.bitPos;
213 bool operator!=(const_iterator
const& o)
const {
214 return !(*
this == o);
222 const_iterator begin()
const {
223 return (numWords() == 0) ? end() : const_iterator(*this, 0);
230 const_iterator end()
const {
231 return const_iterator(*
this);
238 size_t hash()
const {
239 size_t n = numWords();
241 for (
size_t i = 0; i < n; ++i) {
242 h = (h + word(i)) * 314159257;
252 bool operator==(MyBitSet
const& o)
const {
253 size_t n = numWords();
254 if (o.numWords() != n)
return false;
255 for (
size_t i = 0; i < n; ++i) {
256 if (word(i) != o.word(i))
return false;
267 friend std::ostream& operator<<(std::ostream& os, MyBitSet
const& o) {
270 for (const_iterator t = o.begin(); t != o.end(); ++t) {
271 if (comma) os <<
',';
279 class MyBitSetOnPool:
public MyBitSet<0> {
280 MyBitSetOnPool(
size_t n) :
285 static MyBitSetOnPool* newInstance(MemoryPool& pool,
size_t bits) {
286 size_t n = (bits + 63) / 64;
287 return new (pool.template allocate<uint64_t>(1 + n)) MyBitSetOnPool(n);
291 template<
typename T,
size_t N>
294 T array_[N == 0 ? 1 : N];
305 size_t size()
const {
338 void add(T
const& e) {
339 if (N > 0 && size_ >= N - 1)
throw std::out_of_range(
"MySmallSet::add");
340 T* pz = array_ + size_;
342 while (array_ <= p && e <= *p) {
360 void remove(T
const& e) {
361 T* p = std::lower_bound(array_, array_ + size_, e);
362 if (p == array_ + size_ || *p != e)
return;
364 for (T* q = p; q != array_ + size_; ++q) {
374 bool includes(T
const& e)
const {
375 return std::binary_search(array_, array_ + size_, e);
385 bool equals(C
const& c)
const {
386 const_iterator p = begin();
387 typename C::const_iterator q = c.begin();
388 const_iterator pz = end();
389 typename C::const_iterator qz = c.end();
390 while (p != pz && q != qz) {
391 if (*p != *q)
return false;
394 return p == pz && q == qz;
404 bool intersects(C
const& c)
const {
405 const_iterator p = begin();
406 typename C::const_iterator q = c.begin();
407 const_iterator pz = end();
408 typename C::const_iterator qz = c.end();
409 while (p != pz && q != qz) {
410 if (*p == *q)
return true;
424 bool containsAll(C
const& c)
const {
425 const_iterator p = begin();
426 typename C::const_iterator q = c.begin();
427 const_iterator pz = end();
428 typename C::const_iterator qz = c.end();
429 while (p != pz && q != qz) {
430 if (*p > *q)
return false;
437 typedef T
const* const_iterator;
443 const_iterator begin()
const {
451 const_iterator end()
const {
452 return array_ + size_;
455 class const_reverse_iterator {
459 const_reverse_iterator(T
const* ptr) :
463 T
const& operator*()
const {
467 T
const* operator->()
const {
471 const_reverse_iterator& operator++() {
476 bool operator==(const_reverse_iterator
const& o)
const {
480 bool operator!=(const_reverse_iterator
const& o)
const {
489 const_reverse_iterator rbegin()
const {
490 return const_reverse_iterator(array_ + size_ - 1);
497 const_reverse_iterator rend()
const {
498 return const_reverse_iterator(array_ - 1);
506 T
const&
get(
size_t i)
const {
507 assert(N == 0 || i < N);
515 size_t hash()
const {
517 for (
size_t k = 0; k < size_; ++k) {
518 h = h * 271828171 + MyHashDefault<T>()(array_[k]);
528 bool operator==(MySmallSet
const& o)
const {
529 if (size_ != o.size_)
return false;
530 for (
size_t k = 0; k < size_; ++k) {
531 if (array_[k] != o.array_[k])
return false;
542 friend std::ostream& operator<<(std::ostream& os, MySmallSet
const& o) {
545 for (
size_t k = 0; k < o.size_; ++k) {
546 if (comma) os <<
',';
555 class MySmallSetOnPool:
public MySmallSet<T,0> {
557 static MySmallSetOnPool* newInstance(MemoryPool& pool,
size_t n) {
558 size_t m = (
sizeof(MySmallSet<T,0> ) -
sizeof(T)
563 return new (pool.template allocate<size_t>(m)) MySmallSetOnPool();
566 static MySmallSetOnPool* newInstance(MemoryPool& pool,
int n) {
567 return newInstance(pool,
size_t(n));
571 static MySmallSetOnPool* newInstance(MemoryPool& pool, C
const& copy) {
572 MySmallSetOnPool* obj = newInstance(pool, copy.size());
573 for (
typename C::const_iterator t = copy.begin(); t != copy.end();