TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
MySet.hpp
1 /*
2  * TdZdd: a Top-down/Breadth-first Decision Diagram Manipulation Framework
3  * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
4  * Copyright (c) 2014 ERATO MINATO Project
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the "Software"),
8  * to deal in the Software without restriction, including without limitation
9  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  * and/or sell copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  * DEALINGS IN THE SOFTWARE.
23  */
24 
25 #pragma once
26 
27 #include <algorithm>
28 #include <cassert>
29 #include <cstring>
30 #include <stdint.h>
31 
32 #include "MemoryPool.hpp"
33 #include "MyHashTable.hpp"
34 
35 namespace tdzdd {
36 
37 template<size_t N>
38 class MyBitSet {
39  static size_t const offset = (N == 0) ? 1 : 0;
40 
41  uint64_t array_[(N == 0) ? 1 : N];
42 
43  uint64_t& word(size_t i) {
44  assert(i < numWords());
45  return array_[i + offset];
46  }
47 
48  uint64_t word(size_t i) const {
49  assert(i < numWords());
50  return array_[i + offset];
51  }
52 
53  uint64_t mask(size_t i) const {
54  return uint64_t(1) << i;
55  }
56 
57 public:
58  MyBitSet(uint64_t n = 0) {
59  array_[0] = n;
60  for (size_t i = (N == 0) ? 0 : 1; i < numWords(); ++i) {
61  word(i) = 0;
62  }
63  }
64 
69  size_t numWords() const {
70  return (N == 0) ? array_[0] : N;
71  }
72 
77  void clear() {
78  for (size_t i = 0; i < numWords(); ++i) {
79  word(i) = 0;
80  }
81  }
82 
87  bool empty() const {
88  for (size_t i = 0; i < numWords(); ++i) {
89  if (word(i) != 0) return false;
90  }
91  return true;
92  }
93 
98  void add(size_t i) {
99  uint64_t& w = word(i / 64);
100  uint64_t m = mask(i % 64);
101  w |= m;
102  }
103 
108  void remove(size_t i) {
109  uint64_t& w = word(i / 64);
110  uint64_t m = mask(i % 64);
111  w &= ~m;
112  }
113 
119  void pullout(size_t i) {
120  size_t k = i / 64;
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);
125  while (++p < q) {
126  *(p - 1) |= *p >> 63;
127  *p <<= 1;
128  }
129  }
130 
136  bool includes(size_t i) const {
137  uint64_t w = word(i / 64);
138  uint64_t m = mask(i % 64);
139  return w & m;
140  }
141 
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;
151  }
152  return false;
153  }
154 
155  class const_iterator {
156  MyBitSet const& bitSet;
157  size_t wordPos;
158  int bitPos;
159  uint64_t word;
160 
161  public:
162  const_iterator(MyBitSet const& bitSet) :
163  bitSet(bitSet), wordPos(bitSet.numWords()), bitPos(-1), word(0) {
164  }
165 
166  const_iterator(MyBitSet const& bitSet, size_t i) :
167  bitSet(bitSet), wordPos(i), bitPos(-1), word(bitSet.word(i)) {
168  ++(*this);
169  }
170 
171  size_t operator*() const {
172  return wordPos * 64 + bitPos;
173  }
174 
175  const_iterator& operator++() {
176  while (word == 0) {
177  bitPos = -1;
178  if (++wordPos >= bitSet.numWords()) {
179  wordPos = bitSet.numWords();
180  return *this;
181  }
182  word = bitSet.word(wordPos);
183  }
184 
185  if (word == uint64_t(1) << 63) {
186  bitPos = 63;
187  word = 0;
188  }
189  else {
190  int k = __builtin_ffsll(word);
191  bitPos += k;
192  word >>= k;
193  }
194 
195 // int k = __builtin_ffsll(word);
196 // bitPos += k;
197 // word = (k < 64) ? word >> k : 0;
198 
199 // while ((word & 1) == 0) {
200 // word >>= 1;
201 // ++bitPos;
202 // }
203 // word >>= 1;
204 // ++bitPos;
205 
206  return *this;
207  }
208 
209  bool operator==(const_iterator const& o) const {
210  return wordPos == o.wordPos && bitPos == o.bitPos;
211  }
212 
213  bool operator!=(const_iterator const& o) const {
214  return !(*this == o);
215  }
216  };
217 
222  const_iterator begin() const {
223  return (numWords() == 0) ? end() : const_iterator(*this, 0);
224  }
225 
230  const_iterator end() const {
231  return const_iterator(*this);
232  }
233 
238  size_t hash() const {
239  size_t n = numWords();
240  size_t h = 0;
241  for (size_t i = 0; i < n; ++i) {
242  h = (h + word(i)) * 314159257;
243  }
244  return h;
245  }
246 
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;
257  }
258  return true;
259  }
260 
267  friend std::ostream& operator<<(std::ostream& os, MyBitSet const& o) {
268  bool comma = false;
269  os << '{';
270  for (const_iterator t = o.begin(); t != o.end(); ++t) {
271  if (comma) os << ',';
272  os << *t;
273  comma = true;
274  }
275  return os << '}';
276  }
277 };
278 
279 class MyBitSetOnPool: public MyBitSet<0> {
280  MyBitSetOnPool(size_t n) :
281  MyBitSet<0>(n) {
282  }
283 
284 public:
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);
288  }
289 };
290 
291 template<typename T, size_t N>
292 class MySmallSet {
293  size_t size_;
294  T array_[N == 0 ? 1 : N];
295 
296 public:
297  MySmallSet() :
298  size_(0) {
299  }
300 
305  size_t size() const {
306  return size_;
307  }
308 
312  void clear() {
313  size_ = 0;
314  }
315 
320  bool empty() const {
321  return size_ == 0;
322  }
323 
328 // void add(T const& e) {
329 // T* p = std::lower_bound(array_, array_ + size_, e);
330 // if (p != array_ + size_ && *p == e) return;
331 // if (N > 0 && size_ >= N - 1) throw std::out_of_range("MySmallSet::add");
332 // for (T* q = array_ + size_; q != p; --q) {
333 // *q = *(q - 1);
334 // }
335 // *p = e;
336 // ++size_;
337 // }
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_;
341  T* p = pz - 1;
342  while (array_ <= p && e <= *p) {
343  if (e == *p) {
344  while (++p < pz) {
345  *p = *(p + 1);
346  }
347  return;
348  }
349  *(p + 1) = *p;
350  --p;
351  }
352  *(p + 1) = e;
353  ++size_;
354  }
355 
360  void remove(T const& e) {
361  T* p = std::lower_bound(array_, array_ + size_, e);
362  if (p == array_ + size_ || *p != e) return;
363  --size_;
364  for (T* q = p; q != array_ + size_; ++q) {
365  *q = *(q + 1);
366  }
367  }
368 
374  bool includes(T const& e) const {
375  return std::binary_search(array_, array_ + size_, e);
376  }
377 
384  template<typename C>
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;
392  ++p, ++q;
393  }
394  return p == pz && q == qz;
395  }
396 
403  template<typename C>
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;
411  if (*p < *q) ++p;
412  else ++q;
413  }
414  return false;
415  }
416 
423  template<typename C>
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;
431  if (*p < *q) ++p;
432  else ++p, ++q;
433  }
434  return q == qz;
435  }
436 
437  typedef T const* const_iterator;
438 
443  const_iterator begin() const {
444  return array_;
445  }
446 
451  const_iterator end() const {
452  return array_ + size_;
453  }
454 
455  class const_reverse_iterator {
456  T const* ptr;
457 
458  public:
459  const_reverse_iterator(T const* ptr) :
460  ptr(ptr) {
461  }
462 
463  T const& operator*() const {
464  return *ptr;
465  }
466 
467  T const* operator->() const {
468  return ptr;
469  }
470 
471  const_reverse_iterator& operator++() {
472  --ptr;
473  return *this;
474  }
475 
476  bool operator==(const_reverse_iterator const& o) const {
477  return ptr == o.ptr;
478  }
479 
480  bool operator!=(const_reverse_iterator const& o) const {
481  return ptr != o.ptr;
482  }
483  };
484 
489  const_reverse_iterator rbegin() const {
490  return const_reverse_iterator(array_ + size_ - 1);
491  }
492 
497  const_reverse_iterator rend() const {
498  return const_reverse_iterator(array_ - 1);
499  }
500 
506  T const& get(size_t i) const {
507  assert(N == 0 || i < N);
508  return array_[i];
509  }
510 
515  size_t hash() const {
516  size_t h = 0;
517  for (size_t k = 0; k < size_; ++k) {
518  h = h * 271828171 + MyHashDefault<T>()(array_[k]);
519  }
520  return h;
521  }
522 
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;
532  }
533  return true;
534  }
535 
542  friend std::ostream& operator<<(std::ostream& os, MySmallSet const& o) {
543  bool comma = false;
544  os << '{';
545  for (size_t k = 0; k < o.size_; ++k) {
546  if (comma) os << ',';
547  os << o.array_[k];
548  comma = true;
549  }
550  return os << '}';
551  }
552 };
553 
554 template<typename T>
555 class MySmallSetOnPool: public MySmallSet<T,0> {
556 public:
557  static MySmallSetOnPool* newInstance(MemoryPool& pool, size_t n) {
558  size_t m = (sizeof(MySmallSet<T,0> ) - sizeof(T)
559  + sizeof(T) * n
560  + sizeof(size_t)
561  - 1)
562  / sizeof(size_t);
563  return new (pool.template allocate<size_t>(m)) MySmallSetOnPool();
564  }
565 
566  static MySmallSetOnPool* newInstance(MemoryPool& pool, int n) {
567  return newInstance(pool, size_t(n));
568  }
569 
570  template<typename C>
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();
574  ++t) {
575  obj->add(*t);
576  }
577  return obj;
578  }
579 };
580 
581 } // namespace tdzdd