OR-Tools  8.2
bitset.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 // Various utility functions on bitsets.
15 
16 #ifndef OR_TOOLS_UTIL_BITSET_H_
17 #define OR_TOOLS_UTIL_BITSET_H_
18 
19 #include <string.h>
20 
21 #include <algorithm>
22 #include <vector>
23 
25 #include "ortools/base/logging.h"
26 #include "ortools/base/macros.h"
27 
28 namespace operations_research {
29 
30 // Basic bit operations
31 
32 // Useful constants: word and double word will all bits set.
33 static const uint64 kAllBits64 = uint64_t{0xFFFFFFFFFFFFFFFF};
34 static const uint64 kAllBitsButLsb64 = uint64_t{0xFFFFFFFFFFFFFFFE};
35 static const uint32 kAllBits32 = 0xFFFFFFFFU;
36 
37 // Returns a word with only bit pos set.
38 inline uint64 OneBit64(int pos) { return uint64_t{1} << pos; }
39 inline uint32 OneBit32(int pos) { return 1U << pos; }
40 
41 // Returns the number of bits set in n.
43  const uint64 m1 = uint64_t{0x5555555555555555};
44  const uint64 m2 = uint64_t{0x3333333333333333};
45  const uint64 m4 = uint64_t{0x0F0F0F0F0F0F0F0F};
46  const uint64 h01 = uint64_t{0x0101010101010101};
47  n -= (n >> 1) & m1;
48  n = (n & m2) + ((n >> 2) & m2);
49  n = (n + (n >> 4)) & m4;
50  n = (n * h01) >> 56;
51  return n;
52 }
54  n -= (n >> 1) & 0x55555555UL;
55  n = (n & 0x33333333) + ((n >> 2) & 0x33333333UL);
56  n = (n + (n >> 4)) & 0x0F0F0F0FUL;
57  n = n + (n >> 8);
58  n = n + (n >> 16);
59  return n & 0x0000003FUL;
60 }
61 
62 // Returns a word with only the least significant bit of n set.
63 inline uint64 LeastSignificantBitWord64(uint64 n) { return n & ~(n - 1); }
64 inline uint32 LeastSignificantBitWord32(uint32 n) { return n & ~(n - 1); }
65 
66 // Returns the least significant bit position in n.
67 // Discussion around lsb computation:
68 // De Bruijn is almost as fast as the bsr/bsf-instruction-based intrinsics.
69 // Both are always much faster than the Default algorithm.
70 #define USE_DEBRUIJN true // if true, use de Bruijn bit forward scanner.
71 #if defined(__GNUC__) || defined(__llvm__)
72 #define USE_FAST_LEAST_SIGNIFICANT_BIT true // if true, use fast lsb.
73 #endif
74 
75 #if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
76 inline int LeastSignificantBitPosition64Fast(uint64 n) {
77  return n == 0 ? 0 : __builtin_ctzll(n);
78 }
79 #endif
80 
82  static const uint64 kSeq = uint64_t{0x0218a392dd5fb34f};
83  static const int kTab[64] = {
84  // initialized by 'kTab[(kSeq << i) >> 58] = i
85  0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 52, 20, 58,
86  5, 17, 26, 56, 15, 38, 29, 40, 10, 49, 53, 31, 21, 34, 59, 42,
87  63, 6, 12, 18, 24, 27, 51, 57, 16, 55, 37, 39, 48, 30, 33, 41,
88  62, 11, 23, 50, 54, 36, 47, 32, 61, 22, 35, 46, 60, 45, 44, 43,
89  };
90  return kTab[((n & (~n + 1)) * kSeq) >> 58];
91 }
92 
94  if (n == 0) return 0;
95  int pos = 63;
96  if (n & 0x00000000FFFFFFFFLL) {
97  pos -= 32;
98  } else {
99  n >>= 32;
100  }
101  if (n & 0x000000000000FFFFLL) {
102  pos -= 16;
103  } else {
104  n >>= 16;
105  }
106  if (n & 0x00000000000000FFLL) {
107  pos -= 8;
108  } else {
109  n >>= 8;
110  }
111  if (n & 0x000000000000000FLL) {
112  pos -= 4;
113  } else {
114  n >>= 4;
115  }
116  if (n & 0x0000000000000003LL) {
117  pos -= 2;
118  } else {
119  n >>= 2;
120  }
121  if (n & 0x0000000000000001LL) {
122  pos -= 1;
123  }
124  return pos;
125 }
126 
128  DCHECK_NE(n, 0);
129 #ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
130  return LeastSignificantBitPosition64Fast(n);
131 #elif defined(USE_DEBRUIJN)
133 #else
135 #endif
136 }
137 
138 #if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
139 inline int LeastSignificantBitPosition32Fast(uint32 n) {
140  return n == 0 ? 0 : __builtin_ctzl(n);
141 }
142 #endif
143 
145  static const uint32 kSeq = 0x077CB531U; // de Bruijn sequence
146  static const int kTab[32] = {// initialized by 'kTab[(kSeq << i) >> 27] = i
147  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,
148  15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
149  16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
150  return kTab[((n & (~n + 1)) * kSeq) >> 27];
151 }
152 
154  if (n == 0) return 0;
155  int pos = 31;
156  if (n & 0x0000FFFFL) {
157  pos -= 16;
158  } else {
159  n >>= 16;
160  }
161  if (n & 0x000000FFL) {
162  pos -= 8;
163  } else {
164  n >>= 8;
165  }
166  if (n & 0x0000000FL) {
167  pos -= 4;
168  } else {
169  n >>= 4;
170  }
171  if (n & 0x00000003L) {
172  pos -= 2;
173  } else {
174  n >>= 2;
175  }
176  if (n & 0x00000001L) {
177  pos -= 1;
178  }
179  return pos;
180 }
181 
183  DCHECK_NE(n, 0);
184 #ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
185  return LeastSignificantBitPosition32Fast(n);
186 #elif defined(USE_DEBRUIJN)
188 #else
190 #endif
191 }
192 
193 // Returns the most significant bit position in n.
194 #if USE_FAST_LEAST_SIGNIFICANT_BIT
195 inline int MostSignificantBitPosition64Fast(uint64 n) {
196  // __builtin_clzll(1) should always return 63. There is no penalty in
197  // using offset, and the code looks more like its uint32 counterpart.
198  const int offset = __builtin_clzll(1);
199  return n == 0 ? 0 : (offset - __builtin_clzll(n));
200 }
201 #endif
202 
204  int b = 0;
205  if (0 != (n & (kAllBits64 << (1 << 5)))) {
206  b |= (1 << 5);
207  n >>= (1 << 5);
208  }
209  if (0 != (n & (kAllBits64 << (1 << 4)))) {
210  b |= (1 << 4);
211  n >>= (1 << 4);
212  }
213  if (0 != (n & (kAllBits64 << (1 << 3)))) {
214  b |= (1 << 3);
215  n >>= (1 << 3);
216  }
217  if (0 != (n & (kAllBits64 << (1 << 2)))) {
218  b |= (1 << 2);
219  n >>= (1 << 2);
220  }
221  if (0 != (n & (kAllBits64 << (1 << 1)))) {
222  b |= (1 << 1);
223  n >>= (1 << 1);
224  }
225  if (0 != (n & (kAllBits64 << (1 << 0)))) {
226  b |= (1 << 0);
227  }
228  return b;
229 }
230 
232 #ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
233  return MostSignificantBitPosition64Fast(n);
234 #else
236 #endif
237 }
238 
239 #if USE_FAST_LEAST_SIGNIFICANT_BIT
240 inline int MostSignificantBitPosition32Fast(uint32 n) {
241  // The constant here depends on whether we are on a 32-bit or 64-bit machine.
242  // __builtin_clzl(1) returns 63 on a 64-bit machine and 31 on a 32-bit
243  // machine.
244  const int offset = __builtin_clzl(1);
245  return n == 0 ? 0 : (offset - __builtin_clzl(n));
246 }
247 #endif
248 
250  int b = 0;
251  if (0 != (n & (kAllBits32 << (1 << 4)))) {
252  b |= (1 << 4);
253  n >>= (1 << 4);
254  }
255  if (0 != (n & (kAllBits32 << (1 << 3)))) {
256  b |= (1 << 3);
257  n >>= (1 << 3);
258  }
259  if (0 != (n & (kAllBits32 << (1 << 2)))) {
260  b |= (1 << 2);
261  n >>= (1 << 2);
262  }
263  if (0 != (n & (kAllBits32 << (1 << 1)))) {
264  b |= (1 << 1);
265  n >>= (1 << 1);
266  }
267  if (0 != (n & (kAllBits32 << (1 << 0)))) {
268  b |= (1 << 0);
269  }
270  return b;
271 }
272 
274 #ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
275  return MostSignificantBitPosition32Fast(n);
276 #else
278 #endif
279 }
280 
281 #undef USE_DEBRUIJN
282 #undef USE_FAST_LEAST_SIGNIFICANT_BIT
283 
284 // Returns a word with bits from s to e set.
286  DCHECK_LE(s, 63);
287  DCHECK_LE(e, 63);
288  DCHECK_LE(s, e);
289  return (kAllBits64 << s) ^ ((kAllBits64 - 1) << e);
290 }
291 
293  DCHECK_LE(s, 31);
294  DCHECK_LE(e, 31);
295  DCHECK_LE(s, e);
296  return (kAllBits32 << s) ^ ((kAllBits32 - 1) << e);
297 }
298 
299 // Returns a word with s least significant bits unset.
301  DCHECK_LE(s, 63);
302  return kAllBits64 << s;
303 }
304 
306  DCHECK_LE(s, 31);
307  return kAllBits32 << s;
308 }
309 
310 // Returns a word with the s most significant bits unset.
312  DCHECK_LE(s, 63);
313  return kAllBits64 >> (63 - s);
314 }
315 
317  DCHECK_LE(s, 31);
318  return kAllBits32 >> (31 - s);
319 }
320 
321 // ----- Bitset operators -----
322 // Bitset: array of uint32/uint64 words
323 
324 // Bit operators used to manipulates bitsets.
325 
326 // Returns the bit number in the word computed by BitOffsetXX,
327 // corresponding to the bit at position pos in the bitset.
328 // Note: '& 63' is faster than '% 64'
329 // TODO(user): rename BitPos and BitOffset to something more understandable.
330 inline uint32 BitPos64(uint64 pos) { return (pos & 63); }
331 inline uint32 BitPos32(uint32 pos) { return (pos & 31); }
332 
333 // Returns the word number corresponding to bit number pos.
334 inline uint64 BitOffset64(uint64 pos) { return (pos >> 6); }
335 inline uint32 BitOffset32(uint32 pos) { return (pos >> 5); }
336 
337 // Returns the number of words needed to store size bits.
338 inline uint64 BitLength64(uint64 size) { return ((size + 63) >> 6); }
339 inline uint32 BitLength32(uint32 size) { return ((size + 31) >> 5); }
340 
341 // Returns the bit number in the bitset of the first bit of word number v.
342 inline uint64 BitShift64(uint64 v) { return v << 6; }
343 inline uint32 BitShift32(uint32 v) { return v << 5; }
344 
345 // Returns true if the bit pos is set in bitset.
346 inline bool IsBitSet64(const uint64* const bitset, uint64 pos) {
347  return (bitset[BitOffset64(pos)] & OneBit64(BitPos64(pos)));
348 }
349 inline bool IsBitSet32(const uint32* const bitset, uint32 pos) {
350  return (bitset[BitOffset32(pos)] & OneBit32(BitPos32(pos)));
351 }
352 
353 // Sets the bit pos to true in bitset.
354 inline void SetBit64(uint64* const bitset, uint64 pos) {
355  bitset[BitOffset64(pos)] |= OneBit64(BitPos64(pos));
356 }
357 inline void SetBit32(uint32* const bitset, uint32 pos) {
358  bitset[BitOffset32(pos)] |= OneBit32(BitPos32(pos));
359 }
360 
361 // Sets the bit pos to false in bitset.
362 inline void ClearBit64(uint64* const bitset, uint64 pos) {
363  bitset[BitOffset64(pos)] &= ~OneBit64(BitPos64(pos));
364 }
365 inline void ClearBit32(uint32* const bitset, uint32 pos) {
366  bitset[BitOffset32(pos)] &= ~OneBit32(BitPos32(pos));
367 }
368 
369 // Returns the number of bits set in bitset between positions start and end.
370 uint64 BitCountRange64(const uint64* const bitset, uint64 start, uint64 end);
371 uint32 BitCountRange32(const uint32* const bitset, uint32 start, uint32 end);
372 
373 // Returns true if no bits are set in bitset between start and end.
374 bool IsEmptyRange64(const uint64* const bitset, uint64 start, uint64 end);
375 bool IsEmptyRange32(const uint32* const bitset, uint32 start, uint32 end);
376 
377 // Returns the first bit set in bitset between start and max_bit.
379  uint64 end);
380 int LeastSignificantBitPosition32(const uint32* const bitset, uint32 start,
381  uint32 end);
382 
383 // Returns the last bit set in bitset between min_bit and start.
384 int64 MostSignificantBitPosition64(const uint64* const bitset, uint64 start,
385  uint64 end);
386 int MostSignificantBitPosition32(const uint32* const bitset, uint32 start,
387  uint32 end);
388 
389 // Unsafe versions of the functions above where respectively end and start
390 // are supposed to be set.
392  uint64 start, uint64 end);
394  uint32 start, uint32 end);
395 
397  uint64 start, uint64 end);
399  uint32 start, uint32 end);
400 
401 // Returns a mask with the bits pos % 64 and (pos ^ 1) % 64 sets.
402 inline uint64 TwoBitsFromPos64(uint64 pos) { return uint64_t{3} << (pos & 62); }
403 
404 // This class is like an ITIVector<IndexType, bool> except that it provides a
405 // more efficient way to iterate over the positions set to true. It achieves
406 // this by caching the current uint64 bucket in the Iterator and using
407 // LeastSignificantBitPosition64() to iterate over the positions at 1 in this
408 // bucket.
409 template <typename IndexType = int64>
410 class Bitset64 {
411  public:
412  Bitset64() : size_(), data_(), end_(*this, /*at_end=*/true) {}
413  explicit Bitset64(IndexType size)
414  : size_(Value(size) > 0 ? size : IndexType(0)),
415  data_(BitLength64(Value(size_))),
416  end_(*this, /*at_end=*/true) {}
417 
418  // Returns how many bits this Bitset64 can hold.
419  IndexType size() const { return size_; }
420 
421  // Appends value at the end of the bitset.
422  void PushBack(bool value) {
423  ++size_;
424  data_.resize(BitLength64(Value(size_)), 0);
425  Set(size_ - 1, value);
426  }
427 
428  // Resizes the Bitset64 to the given number of bits. New bits are sets to 0.
429  void Resize(IndexType size) {
430  DCHECK_GE(Value(size), 0);
431  size_ = Value(size) > 0 ? size : IndexType(0);
432  data_.resize(BitLength64(Value(size_)), 0);
433  }
434 
435  // Changes the number of bits the Bitset64 can hold and set all of them to 0.
436  void ClearAndResize(IndexType size) {
437  DCHECK_GE(Value(size), 0);
438  size_ = Value(size) > 0 ? size : IndexType(0);
439 
440  // Memset is 4x faster than data_.assign() as of 19/03/2014.
441  // TODO(user): Ideally if a realloc happens, we don't need to copy the old
442  // data...
443  const size_t bit_length = static_cast<size_t>(BitLength64(Value(size_)));
444  const size_t to_clear = std::min(data_.size(), bit_length);
445  data_.resize(bit_length, 0);
446  memset(data_.data(), 0, to_clear * sizeof(int64));
447  }
448 
449  // Sets all bits to 0.
450  void ClearAll() { memset(data_.data(), 0, data_.size() * sizeof(int64)); }
451 
452  // Sets the bit at position i to 0.
453  void Clear(IndexType i) {
454  DCHECK_GE(Value(i), 0);
455  DCHECK_LT(Value(i), Value(size_));
456  data_[BitOffset64(Value(i))] &= ~OneBit64(BitPos64(Value(i)));
457  }
458 
459  // Sets bucket containing bit i to 0.
460  void ClearBucket(IndexType i) {
461  DCHECK_GE(Value(i), 0);
462  DCHECK_LT(Value(i), Value(size_));
463  data_[BitOffset64(Value(i))] = 0;
464  }
465 
466  // Clears the bits at position i and i ^ 1.
467  void ClearTwoBits(IndexType i) {
468  DCHECK_GE(Value(i), 0);
469  DCHECK_LT(Value(i), Value(size_));
470  data_[BitOffset64(Value(i))] &= ~TwoBitsFromPos64(Value(i));
471  }
472 
473  // Returns true if the bit at position i or the one at position i ^ 1 is set.
474  bool AreOneOfTwoBitsSet(IndexType i) const {
475  DCHECK_GE(Value(i), 0);
476  DCHECK_LT(Value(i), Value(size_));
477  return data_[BitOffset64(Value(i))] & TwoBitsFromPos64(Value(i));
478  }
479 
480  // Returns true if the bit at position i is set.
481  bool IsSet(IndexType i) const {
482  DCHECK_GE(Value(i), 0);
483  DCHECK_LT(Value(i), Value(size_));
484  return data_[BitOffset64(Value(i))] & OneBit64(BitPos64(Value(i)));
485  }
486 
487  // Same as IsSet().
488  bool operator[](IndexType i) const { return IsSet(i); }
489 
490  // Sets the bit at position i to 1.
491  void Set(IndexType i) {
492  DCHECK_GE(Value(i), 0);
493  DCHECK_LT(Value(i), size_);
494  data_[BitOffset64(Value(i))] |= OneBit64(BitPos64(Value(i)));
495  }
496 
497  // If value is true, sets the bit at position i to 1, sets it to 0 otherwise.
498  void Set(IndexType i, bool value) {
499  if (value) {
500  Set(i);
501  } else {
502  Clear(i);
503  }
504  }
505 
506  // Copies bucket containing bit i from "other" to "this".
507  void CopyBucket(const Bitset64<IndexType>& other, IndexType i) {
508  const uint64 offset = BitOffset64(Value(i));
509  data_[offset] = other.data_[offset];
510  }
511 
512  // Copies "other" to "this". The bitsets do not have to be of the same size.
513  // If "other" is smaller, high order bits are not changed. If "other" is
514  // larger, its high order bits are ignored. In any case "this" is not resized.
515  template <typename OtherIndexType>
517  const int64 min_size = std::min(data_.size(), other.data_.size());
518  if (min_size == 0) return;
519  const uint64 last_common_bucket = data_[min_size - 1];
520  memcpy(data_.data(), other.data_.data(), min_size * sizeof(uint64));
521  if (data_.size() >= other.data_.size()) {
522  const uint64 bitmask = kAllBitsButLsb64
523  << BitPos64(other.Value(other.size() - 1));
524  data_[min_size - 1] &= ~bitmask;
525  data_[min_size - 1] |= (bitmask & last_common_bucket);
526  }
527  }
528 
529  // Same as SetContentFromBitset where "this" and "other" have the same size.
530  template <typename OtherIndexType>
532  DCHECK_EQ(Value(size()), other.Value(other.size()));
533  memcpy(data_.data(), other.data_.data(), data_.size() * sizeof(uint64));
534  }
535 
536  // Sets "this" to be the intersection of "this" and "other". The
537  // bitsets do not have to be the same size. If other is smaller, all
538  // the higher order bits are assumed to be 0.
539  void Intersection(const Bitset64<IndexType>& other) {
540  const int min_size = std::min(data_.size(), other.data_.size());
541  for (int i = 0; i < min_size; ++i) {
542  data_[i] &= other.data_[i];
543  }
544  for (int i = min_size; i < data_.size(); ++i) {
545  data_[i] = 0;
546  }
547  }
548 
549  // Sets "this" to be the union of "this" and "other". The
550  // bitsets do not have to be the same size. If other is smaller, all
551  // the higher order bits are assumed to be 0.
552  void Union(const Bitset64<IndexType>& other) {
553  const int min_size = std::min(data_.size(), other.data_.size());
554  for (int i = 0; i < min_size; ++i) {
555  data_[i] |= other.data_[i];
556  }
557  }
558 
559  // Class to iterate over the bit positions at 1 of a Bitset64.
560  //
561  // IMPORTANT: Because the iterator "caches" the current uint64 bucket, this
562  // will probably not do what you want if Bitset64 is modified while iterating.
563  class Iterator {
564  public:
565  explicit Iterator(const Bitset64& data_)
566  : bitset_(data_), index_(0), base_index_(0), current_(0) {
567  if (bitset_.data_.empty()) {
568  index_ = -1;
569  } else {
570  current_ = bitset_.data_[0];
571  Next();
572  }
573  }
574 
575  // Returns true if the Iterator is at a valid position.
576  bool Ok() const { return index_ != -1; }
577 
578  // Returns the current position of the iterator.
579  IndexType Index() const {
580  DCHECK(Ok());
581  return IndexType(index_);
582  }
583 
584  // Moves the iterator the the next position at 1 of the Bitset64.
585  void Next() {
586  DCHECK(Ok());
587  if (current_ == 0) {
588  int bucket = BitOffset64(base_index_);
589  const int size = bitset_.data_.size();
590  do {
591  bucket++;
592  } while (bucket < size && bitset_.data_[bucket] == 0);
593  if (bucket == size) {
594  index_ = -1;
595  return;
596  }
597  current_ = bitset_.data_[bucket];
598  base_index_ = BitShift64(bucket);
599  }
600 
601  // Computes the index and clear the least significant bit of current_.
602  index_ = base_index_ + LeastSignificantBitPosition64(current_);
603  current_ &= current_ - 1;
604  }
605 
606  // STL version of the functions above to support range-based "for" loop.
607  Iterator(const Bitset64& data_, bool at_end)
608  : bitset_(data_), index_(0), base_index_(0), current_(0) {
609  if (at_end || bitset_.data_.empty()) {
610  index_ = -1;
611  } else {
612  current_ = bitset_.data_[0];
613  Next();
614  }
615  }
616  bool operator!=(const Iterator& other) const {
617  return index_ != other.index_;
618  }
619  IndexType operator*() const { return IndexType(index_); }
620  void operator++() { Next(); }
621 
622  private:
623  const Bitset64& bitset_;
624  int index_;
625  int base_index_;
626  uint64 current_;
627  };
628 
629  // Allows range-based "for" loop on the non-zero positions:
630  // for (const IndexType index : bitset) {}
631  // instead of:
632  // for (Bitset64<IndexType>::Iterator it(bitset); it.Ok(); it.Next()) {
633  // const IndexType index = it.Index();
634  Iterator begin() const { return Iterator(*this); }
635  Iterator end() const { return end_; }
636 
637  // Cryptic function!
638  // This is just an optimized version of a given piece of code and has probably
639  // little general use. Sets the bit at position i to the result of
640  // (other1[i] && use1) XOR (other2[i] && use2).
641  void SetBitFromOtherBitSets(IndexType i, const Bitset64<IndexType>& other1,
642  uint64 use1, const Bitset64<IndexType>& other2,
643  uint64 use2) {
644  DCHECK_EQ(data_.size(), other1.data_.size());
645  DCHECK_EQ(data_.size(), other2.data_.size());
646  DCHECK(use1 == 0 || use1 == 1);
647  DCHECK(use2 == 0 || use2 == 1);
648  const int bucket = BitOffset64(Value(i));
649  const int pos = BitPos64(Value(i));
650  data_[bucket] ^= ((1ull << pos) & data_[bucket]) ^
651  ((use1 << pos) & other1.data_[bucket]) ^
652  ((use2 << pos) & other2.data_[bucket]);
653  }
654 
655  // Returns a 0/1 string representing the bitset.
656  std::string DebugString() const {
657  std::string output;
658  for (IndexType i(0); i < size(); ++i) {
659  output += IsSet(i) ? "1" : "0";
660  }
661  return output;
662  }
663 
664  private:
665  // Returns the value of the index type.
666  // This function is specialized below to work with IntType and int64.
667  int64 Value(IndexType input) const;
668 
669  IndexType size_;
670  std::vector<uint64> data_;
671 
672  // It is faster to store the end() Iterator than to recompute it every time.
673  // Note that we cannot do the same for begin().
674  const Iterator end_;
675 
676  template <class OtherIndexType>
677  friend class Bitset64;
679 };
680 
681 // Specialized version of Bitset64 that allows to query the last bit set more
682 // efficiently.
683 class BitQueue64 {
684  public:
685  BitQueue64() : size_(), top_(-1), data_() {}
686  explicit BitQueue64(int size)
687  : size_(size), top_(-1), data_(BitLength64(size), 0) {}
688 
689  void IncreaseSize(int size) {
690  CHECK_GE(size, size_);
691  size_ = size;
692  data_.resize(BitLength64(size), 0);
693  }
694 
695  void ClearAndResize(int size) {
696  top_ = -1;
697  size_ = size;
698  data_.assign(BitLength64(size), 0);
699  }
700 
701  void Set(int i) {
702  DCHECK_GE(i, 0);
703  DCHECK_LT(i, size_);
704  top_ = std::max(top_, i);
705  data_[BitOffset64(i)] |= OneBit64(BitPos64(i));
706  }
707 
708  // Sets all the bits from 0 up to i-1 to 1.
709  void SetAllBefore(int i) {
710  DCHECK_GE(i, 0);
711  DCHECK_LT(i, size_);
712  top_ = std::max(top_, i - 1);
713  int bucket_index = static_cast<int>(BitOffset64(i));
714  data_[bucket_index] |= OneBit64(BitPos64(i)) - 1;
715  for (--bucket_index; bucket_index >= 0; --bucket_index) {
716  data_[bucket_index] = kAllBits64;
717  }
718  }
719 
720  // Returns the position of the highest bit set in O(1) or -1 if no bit is set.
721  int Top() const { return top_; }
722 
723  // Clears the Top() bit and recomputes the position of the next Top().
724  void ClearTop() {
725  DCHECK_NE(top_, -1);
726  int bucket_index = static_cast<int>(BitOffset64(top_));
727  uint64 bucket = data_[bucket_index] &= ~OneBit64(BitPos64(top_));
728  while (!bucket) {
729  if (bucket_index == 0) {
730  top_ = -1;
731  return;
732  }
733  bucket = data_[--bucket_index];
734  }
735 
736  // Note(user): I experimented with reversing the bit order in a bucket to
737  // use LeastSignificantBitPosition64() and it is only slightly faster at the
738  // cost of a lower Set() speed. So I prefered this version.
739  top_ = static_cast<int>(BitShift64(bucket_index) +
741  }
742 
743  private:
744  int size_;
745  int top_;
746  std::vector<uint64> data_;
747  DISALLOW_COPY_AND_ASSIGN(BitQueue64);
748 };
749 
750 // The specialization of Value() for IntType and int64.
751 template <typename IntType>
752 inline int64 Bitset64<IntType>::Value(IntType input) const {
753  DCHECK_GE(input.value(), 0);
754  return input.value();
755 }
756 template <>
757 inline int64 Bitset64<int64>::Value(int64 input) const {
758  DCHECK_GE(input, 0);
759  return input;
760 }
761 
762 // A simple utility class to set/unset integer in a range [0, size).
763 // This is optimized for sparsity.
764 template <typename IntegerType = int64>
766  public:
768  explicit SparseBitset(IntegerType size) : bitset_(size) {}
769  IntegerType size() const { return bitset_.size(); }
770  void SparseClearAll() {
771  for (const IntegerType i : to_clear_) bitset_.ClearBucket(i);
772  to_clear_.clear();
773  }
774  void ClearAll() {
775  bitset_.ClearAll();
776  to_clear_.clear();
777  }
778  void ClearAndResize(IntegerType size) {
779  // As of 19/03/2014, experiments show that this is a reasonable threshold.
780  const int kSparseThreshold = 300;
781  if (to_clear_.size() * kSparseThreshold < size) {
782  SparseClearAll();
783  bitset_.Resize(size);
784  } else {
785  bitset_.ClearAndResize(size);
786  to_clear_.clear();
787  }
788  }
789  void Resize(IntegerType size) {
790  if (size < bitset_.size()) {
791  int new_index = 0;
792  for (IntegerType index : to_clear_) {
793  if (index < size) {
794  to_clear_[new_index] = index;
795  ++new_index;
796  }
797  }
798  to_clear_.resize(new_index);
799  }
800  bitset_.Resize(size);
801  }
802  bool operator[](IntegerType index) const { return bitset_[index]; }
803  void Set(IntegerType index) {
804  if (!bitset_[index]) {
805  bitset_.Set(index);
806  to_clear_.push_back(index);
807  }
808  }
809  void Clear(IntegerType index) { bitset_.Clear(index); }
811  return to_clear_.size();
812  }
813  const std::vector<IntegerType>& PositionsSetAtLeastOnce() const {
814  return to_clear_;
815  }
816 
817  // Tells the class that all its bits are cleared, so it can reset to_clear_
818  // to the empty vector. Note that this call is "unsafe" since the fact that
819  // the class is actually all cleared is only checked in debug mode.
820  //
821  // This is useful to iterate on the "set" positions while clearing them for
822  // instance. This way, after the loop, a client can call this for efficiency.
823  void NotifyAllClear() {
824  if (DEBUG_MODE) {
825  for (IntegerType index : to_clear_) CHECK(!bitset_[index]);
826  }
827  to_clear_.clear();
828  }
829 
830  private:
831  Bitset64<IntegerType> bitset_;
832  std::vector<IntegerType> to_clear_;
834 };
835 
836 } // namespace operations_research
837 
838 #endif // OR_TOOLS_UTIL_BITSET_H_
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
void IncreaseSize(int size)
Definition: bitset.h:689
void ClearAndResize(int size)
Definition: bitset.h:695
Iterator(const Bitset64 &data_)
Definition: bitset.h:565
Iterator(const Bitset64 &data_, bool at_end)
Definition: bitset.h:607
bool operator!=(const Iterator &other) const
Definition: bitset.h:616
void ClearAndResize(IndexType size)
Definition: bitset.h:436
Iterator begin() const
Definition: bitset.h:634
void ClearBucket(IndexType i)
Definition: bitset.h:460
void Set(IndexType i, bool value)
Definition: bitset.h:498
IndexType size() const
Definition: bitset.h:419
void SetContentFromBitsetOfSameSize(const Bitset64< OtherIndexType > &other)
Definition: bitset.h:531
Bitset64(IndexType size)
Definition: bitset.h:413
void SetBitFromOtherBitSets(IndexType i, const Bitset64< IndexType > &other1, uint64 use1, const Bitset64< IndexType > &other2, uint64 use2)
Definition: bitset.h:641
void Clear(IndexType i)
Definition: bitset.h:453
Iterator end() const
Definition: bitset.h:635
void Union(const Bitset64< IndexType > &other)
Definition: bitset.h:552
std::string DebugString() const
Definition: bitset.h:656
void Set(IndexType i)
Definition: bitset.h:491
void SetContentFromBitset(const Bitset64< OtherIndexType > &other)
Definition: bitset.h:516
void Intersection(const Bitset64< IndexType > &other)
Definition: bitset.h:539
void Resize(IndexType size)
Definition: bitset.h:429
bool IsSet(IndexType i) const
Definition: bitset.h:481
void ClearTwoBits(IndexType i)
Definition: bitset.h:467
void CopyBucket(const Bitset64< IndexType > &other, IndexType i)
Definition: bitset.h:507
bool operator[](IndexType i) const
Definition: bitset.h:488
bool AreOneOfTwoBitsSet(IndexType i) const
Definition: bitset.h:474
void PushBack(bool value)
Definition: bitset.h:422
SparseBitset(IntegerType size)
Definition: bitset.h:768
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition: bitset.h:813
IntegerType size() const
Definition: bitset.h:769
void Set(IntegerType index)
Definition: bitset.h:803
int NumberOfSetCallsWithDifferentArguments() const
Definition: bitset.h:810
void Clear(IntegerType index)
Definition: bitset.h:809
void Resize(IntegerType size)
Definition: bitset.h:789
bool operator[](IntegerType index) const
Definition: bitset.h:802
void ClearAndResize(IntegerType size)
Definition: bitset.h:778
int64 value
unsigned int uint32
int int32
int64_t int64
uint64_t uint64
const bool DEBUG_MODE
Definition: macros.h:24
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
uint64 BitShift64(uint64 v)
Definition: bitset.h:342
int LeastSignificantBitPosition64(uint64 n)
Definition: bitset.h:127
uint32 BitCount32(uint32 n)
Definition: bitset.h:53
uint32 BitPos64(uint64 pos)
Definition: bitset.h:330
void SetBit32(uint32 *const bitset, uint32 pos)
Definition: bitset.h:357
int LeastSignificantBitPosition64Default(uint64 n)
Definition: bitset.h:93
uint32 LeastSignificantBitWord32(uint32 n)
Definition: bitset.h:64
uint64 IntervalUp64(uint64 s)
Definition: bitset.h:300
int MostSignificantBitPosition64(uint64 n)
Definition: bitset.h:231
uint32 BitShift32(uint32 v)
Definition: bitset.h:343
uint64 BitCount64(uint64 n)
Definition: bitset.h:42
uint32 BitPos32(uint32 pos)
Definition: bitset.h:331
uint32 IntervalDown32(uint32 s)
Definition: bitset.h:316
int64 UnsafeLeastSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 TwoBitsFromPos64(uint64 pos)
Definition: bitset.h:402
uint64 BitOffset64(uint64 pos)
Definition: bitset.h:334
static const uint64 kAllBitsButLsb64
Definition: bitset.h:34
void SetBit64(uint64 *const bitset, uint64 pos)
Definition: bitset.h:354
uint32 BitLength32(uint32 size)
Definition: bitset.h:339
bool IsBitSet32(const uint32 *const bitset, uint32 pos)
Definition: bitset.h:349
int32 UnsafeMostSignificantBitPosition32(const uint32 *const bitset, uint32 start, uint32 end)
bool IsBitSet64(const uint64 *const bitset, uint64 pos)
Definition: bitset.h:346
int LeastSignificantBitPosition32Default(uint32 n)
Definition: bitset.h:153
int32 UnsafeLeastSignificantBitPosition32(const uint32 *const bitset, uint32 start, uint32 end)
static const uint32 kAllBits32
Definition: bitset.h:35
bool IsEmptyRange64(const uint64 *const bitset, uint64 start, uint64 end)
int LeastSignificantBitPosition32(uint32 n)
Definition: bitset.h:182
int LeastSignificantBitPosition64DeBruijn(uint64 n)
Definition: bitset.h:81
static const uint64 kAllBits64
Definition: bitset.h:33
uint32 BitCountRange32(const uint32 *const bitset, uint32 start, uint32 end)
uint32 IntervalUp32(uint32 s)
Definition: bitset.h:305
void ClearBit64(uint64 *const bitset, uint64 pos)
Definition: bitset.h:362
uint64 LeastSignificantBitWord64(uint64 n)
Definition: bitset.h:63
void ClearBit32(uint32 *const bitset, uint32 pos)
Definition: bitset.h:365
uint64 OneRange64(uint64 s, uint64 e)
Definition: bitset.h:285
uint32 BitOffset32(uint32 pos)
Definition: bitset.h:335
int LeastSignificantBitPosition32DeBruijn(uint32 n)
Definition: bitset.h:144
uint64 BitCountRange64(const uint64 *const bitset, uint64 start, uint64 end)
int MostSignificantBitPosition64Default(uint64 n)
Definition: bitset.h:203
uint32 OneBit32(int pos)
Definition: bitset.h:39
int64 UnsafeMostSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 IntervalDown64(uint64 s)
Definition: bitset.h:311
uint32 OneRange32(uint32 s, uint32 e)
Definition: bitset.h:292
int MostSignificantBitPosition32Default(uint32 n)
Definition: bitset.h:249
uint64 OneBit64(int pos)
Definition: bitset.h:38
bool IsEmptyRange32(const uint32 *const bitset, uint32 start, uint32 end)
uint64 BitLength64(uint64 size)
Definition: bitset.h:338
int MostSignificantBitPosition32(uint32 n)
Definition: bitset.h:273
int index
Definition: pack.cc:508
static int input(yyscan_t yyscanner)