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
26#include "ortools/base/macros.h"
27
28namespace operations_research {
29
30// Basic bit operations
31
32// Useful constants: word and double word will all bits set.
33static const uint64 kAllBits64 = uint64_t{0xFFFFFFFFFFFFFFFF};
34static const uint64 kAllBitsButLsb64 = uint64_t{0xFFFFFFFFFFFFFFFE};
35static const uint32 kAllBits32 = 0xFFFFFFFFU;
36
37// Returns a word with only bit pos set.
38inline uint64 OneBit64(int pos) { return uint64_t{1} << pos; }
39inline 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.
63inline uint64 LeastSignificantBitWord64(uint64 n) { return n & ~(n - 1); }
64inline 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)
76inline 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)
139inline 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
195inline 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
240inline 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.
330inline uint32 BitPos64(uint64 pos) { return (pos & 63); }
331inline uint32 BitPos32(uint32 pos) { return (pos & 31); }
332
333// Returns the word number corresponding to bit number pos.
334inline uint64 BitOffset64(uint64 pos) { return (pos >> 6); }
335inline uint32 BitOffset32(uint32 pos) { return (pos >> 5); }
336
337// Returns the number of words needed to store size bits.
338inline uint64 BitLength64(uint64 size) { return ((size + 63) >> 6); }
339inline 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.
342inline uint64 BitShift64(uint64 v) { return v << 6; }
343inline uint32 BitShift32(uint32 v) { return v << 5; }
344
345// Returns true if the bit pos is set in bitset.
346inline bool IsBitSet64(const uint64* const bitset, uint64 pos) {
347 return (bitset[BitOffset64(pos)] & OneBit64(BitPos64(pos)));
348}
349inline 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.
354inline void SetBit64(uint64* const bitset, uint64 pos) {
355 bitset[BitOffset64(pos)] |= OneBit64(BitPos64(pos));
356}
357inline 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.
362inline void ClearBit64(uint64* const bitset, uint64 pos) {
363 bitset[BitOffset64(pos)] &= ~OneBit64(BitPos64(pos));
364}
365inline 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.
370uint64 BitCountRange64(const uint64* const bitset, uint64 start, uint64 end);
371uint32 BitCountRange32(const uint32* const bitset, uint32 start, uint32 end);
372
373// Returns true if no bits are set in bitset between start and end.
374bool IsEmptyRange64(const uint64* const bitset, uint64 start, uint64 end);
375bool 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);
380int LeastSignificantBitPosition32(const uint32* const bitset, uint32 start,
381 uint32 end);
382
383// Returns the last bit set in bitset between min_bit and start.
385 uint64 end);
386int 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.
402inline 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.
409template <typename IndexType = int64>
410class 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.
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.
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.
751template <typename IntType>
752inline int64 Bitset64<IntType>::Value(IntType input) const {
753 DCHECK_GE(input.value(), 0);
754 return input.value();
755}
756template <>
757inline 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.
764template <typename IntegerType = int64>
766 public:
768 explicit SparseBitset(IntegerType size) : bitset_(size) {}
769 IntegerType size() const { return bitset_.size(); }
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.
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
IntegerType size() const
Definition: bitset.h:769
void Set(IntegerType index)
Definition: bitset.h:803
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition: bitset.h:813
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...
int LeastSignificantBitPosition32DeBruijn(uint32 n)
Definition: bitset.h:144
int LeastSignificantBitPosition32(uint32 n)
Definition: bitset.h:182
int64 UnsafeLeastSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 BitShift64(uint64 v)
Definition: bitset.h:342
int MostSignificantBitPosition64Default(uint64 n)
Definition: bitset.h:203
bool IsBitSet32(const uint32 *const bitset, uint32 pos)
Definition: bitset.h:349
uint64 LeastSignificantBitWord64(uint64 n)
Definition: bitset.h:63
uint32 OneRange32(uint32 s, uint32 e)
Definition: bitset.h:292
uint64 BitLength64(uint64 size)
Definition: bitset.h:338
void SetBit64(uint64 *const bitset, uint64 pos)
Definition: bitset.h:354
uint64 IntervalUp64(uint64 s)
Definition: bitset.h:300
uint32 BitOffset32(uint32 pos)
Definition: bitset.h:335
bool IsBitSet64(const uint64 *const bitset, uint64 pos)
Definition: bitset.h:346
uint32 BitCount32(uint32 n)
Definition: bitset.h:53
int32 UnsafeLeastSignificantBitPosition32(const uint32 *const bitset, uint32 start, uint32 end)
int MostSignificantBitPosition64(uint64 n)
Definition: bitset.h:231
int LeastSignificantBitPosition64DeBruijn(uint64 n)
Definition: bitset.h:81
uint32 BitShift32(uint32 v)
Definition: bitset.h:343
static const uint64 kAllBitsButLsb64
Definition: bitset.h:34
void ClearBit64(uint64 *const bitset, uint64 pos)
Definition: bitset.h:362
int MostSignificantBitPosition32Default(uint32 n)
Definition: bitset.h:249
uint32 BitPos64(uint64 pos)
Definition: bitset.h:330
uint32 OneBit32(int pos)
Definition: bitset.h:39
uint64 OneRange64(uint64 s, uint64 e)
Definition: bitset.h:285
uint32 BitCountRange32(const uint32 *const bitset, uint32 start, uint32 end)
static const uint32 kAllBits32
Definition: bitset.h:35
static const uint64 kAllBits64
Definition: bitset.h:33
int32 UnsafeMostSignificantBitPosition32(const uint32 *const bitset, uint32 start, uint32 end)
uint64 OneBit64(int pos)
Definition: bitset.h:38
void ClearBit32(uint32 *const bitset, uint32 pos)
Definition: bitset.h:365
int MostSignificantBitPosition32(uint32 n)
Definition: bitset.h:273
uint32 BitPos32(uint32 pos)
Definition: bitset.h:331
uint64 BitOffset64(uint64 pos)
Definition: bitset.h:334
uint32 BitLength32(uint32 size)
Definition: bitset.h:339
int LeastSignificantBitPosition64(uint64 n)
Definition: bitset.h:127
uint64 TwoBitsFromPos64(uint64 pos)
Definition: bitset.h:402
uint32 IntervalDown32(uint32 s)
Definition: bitset.h:316
uint32 LeastSignificantBitWord32(uint32 n)
Definition: bitset.h:64
int LeastSignificantBitPosition64Default(uint64 n)
Definition: bitset.h:93
uint64 IntervalDown64(uint64 s)
Definition: bitset.h:311
uint64 BitCountRange64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 BitCount64(uint64 n)
Definition: bitset.h:42
bool IsEmptyRange32(const uint32 *const bitset, uint32 start, uint32 end)
int LeastSignificantBitPosition32Default(uint32 n)
Definition: bitset.h:153
int64 UnsafeMostSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
void SetBit32(uint32 *const bitset, uint32 pos)
Definition: bitset.h:357
bool IsEmptyRange64(const uint64 *const bitset, uint64 start, uint64 end)
uint32 IntervalUp32(uint32 s)
Definition: bitset.h:305
int index
Definition: pack.cc:508
static int input(yyscan_t yyscanner)