Morph MORPH
SIGN IN SIGN UP
google / or-tools UNCLAIMED

Google's Operations Research tools:

0 0 687 C++
Normal View History Raw
Bump copyright to 2025 note: done using ```sh git grep -l "2010-2024 Google" | xargs sed -i 's/2010-2024 Google/2010-2025 Google/' ```
2025-01-10 11:33:35 +01:00
// Copyright 2010-2025 Google LLC
initial checking
2010-09-15 12:42:33 +00:00
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Various utility functions on bitsets.
util: update include guards
2025-11-05 10:13:48 +01:00
#ifndef ORTOOLS_UTIL_BITSET_H_
#define ORTOOLS_UTIL_BITSET_H_
initial checking
2010-09-15 12:42:33 +00:00
remove using directives, in particular string -> std::string everywhere; speedups in the routing library
2013-12-16 10:24:42 +00:00
#include <string.h>
plenty of minor format issues; fix one numerical issue with glop; improve cut management in CP-SAT; automatic tightening of big-M in CP-SAT
2019-04-08 19:00:46 +02:00
remove using directives, in particular string -> std::string everywhere; speedups in the routing library
2013-12-16 10:24:42 +00:00
#include <algorithm>
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
#include <cstddef>
fix
2024-01-23 14:15:18 +01:00
#include <cstdint>
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
#include <iterator>
stl includes; new library; optional_proto python bazel entry
2022-03-29 17:58:33 +02:00
#include <string>
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
#include <tuple>
initial checking
2010-09-15 12:42:33 +00:00
#include <vector>
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
#include "absl/log/check.h"
initial checking
2010-09-15 12:42:33 +00:00
namespace operations_research {
// Basic bit operations
// Useful constants: word and double word will all bits set.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
static const uint64_t kAllBits64 = uint64_t{0xFFFFFFFFFFFFFFFF};
static const uint64_t kAllBitsButLsb64 = uint64_t{0xFFFFFFFFFFFFFFFE};
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
static const uint32_t kAllBits32 = 0xFFFFFFFFU;
initial checking
2010-09-15 12:42:33 +00:00
// Returns a word with only bit pos set.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline uint64_t OneBit64(int pos) { return uint64_t{1} << pos; }
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t OneBit32(int pos) { return 1U << pos; }
initial checking
2010-09-15 12:42:33 +00:00
// Returns the number of bits set in n.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline uint64_t BitCount64(uint64_t n) {
const uint64_t m1 = uint64_t{0x5555555555555555};
const uint64_t m2 = uint64_t{0x3333333333333333};
const uint64_t m4 = uint64_t{0x0F0F0F0F0F0F0F0F};
const uint64_t h01 = uint64_t{0x0101010101010101};
initial checking
2010-09-15 12:42:33 +00:00
n -= (n >> 1) & m1;
n = (n & m2) + ((n >> 2) & m2);
n = (n + (n >> 4)) & m4;
n = (n * h01) >> 56;
return n;
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t BitCount32(uint32_t n) {
initial checking
2010-09-15 12:42:33 +00:00
n -= (n >> 1) & 0x55555555UL;
n = (n & 0x33333333) + ((n >> 2) & 0x33333333UL);
n = (n + (n >> 4)) & 0x0F0F0F0FUL;
n = n + (n >> 8);
n = n + (n >> 16);
return n & 0x0000003FUL;
}
// Returns a word with only the least significant bit of n set.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline uint64_t LeastSignificantBitWord64(uint64_t n) { return n & ~(n - 1); }
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t LeastSignificantBitWord32(uint32_t n) { return n & ~(n - 1); }
initial checking
2010-09-15 12:42:33 +00:00
// Returns the least significant bit position in n.
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
// Discussion around lsb computation:
// De Bruijn is almost as fast as the bsr/bsf-instruction-based intrinsics.
// Both are always much faster than the Default algorithm.
reapply google format
2020-10-22 23:36:58 +02:00
#define USE_DEBRUIJN true // if true, use de Bruijn bit forward scanner.
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
#if defined(__GNUC__) || defined(__llvm__)
reapply google format
2020-10-22 23:36:58 +02:00
#define USE_FAST_LEAST_SIGNIFICANT_BIT true // if true, use fast lsb.
initial checking
2010-09-15 12:42:33 +00:00
#endif
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline int LeastSignificantBitPosition64Fast(uint64_t n) {
speed up bitset
2022-11-22 17:44:54 +01:00
return __builtin_ctzll(n);
remove concise_iterator, replace by c++11 version; clean up LeastSignificantBitPosition{32|64}
2014-04-16 09:57:29 +00:00
}
#endif
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline int LeastSignificantBitPosition64DeBruijn(uint64_t n) {
static const uint64_t kSeq = uint64_t{0x0218a392dd5fb34f};
initial checking
2010-09-15 12:42:33 +00:00
static const int kTab[64] = {
reapply google format
2020-10-22 23:36:58 +02:00
// initialized by 'kTab[(kSeq << i) >> 58] = i
0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 52, 20, 58,
5, 17, 26, 56, 15, 38, 29, 40, 10, 49, 53, 31, 21, 34, 59, 42,
63, 6, 12, 18, 24, 27, 51, 57, 16, 55, 37, 39, 48, 30, 33, 41,
62, 11, 23, 50, 54, 36, 47, 32, 61, 22, 35, 46, 60, 45, 44, 43,
clang-format
2018-06-08 16:40:43 +02:00
};
Update bitset.h Laurent's suggestion is (as expected) nicer to look at.
2015-10-13 17:03:37 +02:00
return kTab[((n & (~n + 1)) * kSeq) >> 58];
remove concise_iterator, replace by c++11 version; clean up LeastSignificantBitPosition{32|64}
2014-04-16 09:57:29 +00:00
}
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline int LeastSignificantBitPosition64Default(uint64_t n) {
speed up bitset
2022-11-22 17:44:54 +01:00
DCHECK_NE(n, 0);
initial checking
2010-09-15 12:42:33 +00:00
int pos = 63;
if (n & 0x00000000FFFFFFFFLL) {
pos -= 32;
} else {
n >>= 32;
}
if (n & 0x000000000000FFFFLL) {
pos -= 16;
} else {
n >>= 16;
}
if (n & 0x00000000000000FFLL) {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
pos -= 8;
initial checking
2010-09-15 12:42:33 +00:00
} else {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
n >>= 8;
initial checking
2010-09-15 12:42:33 +00:00
}
if (n & 0x000000000000000FLL) {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
pos -= 4;
initial checking
2010-09-15 12:42:33 +00:00
} else {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
n >>= 4;
initial checking
2010-09-15 12:42:33 +00:00
}
if (n & 0x0000000000000003LL) {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
pos -= 2;
initial checking
2010-09-15 12:42:33 +00:00
} else {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
n >>= 2;
initial checking
2010-09-15 12:42:33 +00:00
}
if (n & 0x0000000000000001LL) {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
pos -= 1;
initial checking
2010-09-15 12:42:33 +00:00
}
return pos;
}
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline int LeastSignificantBitPosition64(uint64_t n) {
remove concise_iterator, replace by c++11 version; clean up LeastSignificantBitPosition{32|64}
2014-04-16 09:57:29 +00:00
DCHECK_NE(n, 0);
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
return LeastSignificantBitPosition64Fast(n);
remove concise_iterator, replace by c++11 version; clean up LeastSignificantBitPosition{32|64}
2014-04-16 09:57:29 +00:00
#elif defined(USE_DEBRUIJN)
return LeastSignificantBitPosition64DeBruijn(n);
#else
return LeastSignificantBitPosition64Default(n);
#endif
}
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline int LeastSignificantBitPosition32Fast(uint32_t n) {
speed up bitset
2022-11-22 17:44:54 +01:00
return __builtin_ctzl(n);
remove concise_iterator, replace by c++11 version; clean up LeastSignificantBitPosition{32|64}
2014-04-16 09:57:29 +00:00
}
#endif
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline int LeastSignificantBitPosition32DeBruijn(uint32_t n) {
static const uint32_t kSeq = 0x077CB531U; // de Bruijn sequence
reapply google format
2020-10-22 23:36:58 +02:00
static const int kTab[32] = {// initialized by 'kTab[(kSeq << i) >> 27] = i
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,
15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
Update bitset.h Laurent's suggestion is (as expected) nicer to look at.
2015-10-13 17:03:37 +02:00
return kTab[((n & (~n + 1)) * kSeq) >> 27];
remove concise_iterator, replace by c++11 version; clean up LeastSignificantBitPosition{32|64}
2014-04-16 09:57:29 +00:00
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline int LeastSignificantBitPosition32Default(uint32_t n) {
speed up bitset
2022-11-22 17:44:54 +01:00
DCHECK_NE(n, 0);
initial checking
2010-09-15 12:42:33 +00:00
int pos = 31;
if (n & 0x0000FFFFL) {
pos -= 16;
} else {
n >>= 16;
}
if (n & 0x000000FFL) {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
pos -= 8;
initial checking
2010-09-15 12:42:33 +00:00
} else {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
n >>= 8;
initial checking
2010-09-15 12:42:33 +00:00
}
if (n & 0x0000000FL) {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
pos -= 4;
initial checking
2010-09-15 12:42:33 +00:00
} else {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
n >>= 4;
initial checking
2010-09-15 12:42:33 +00:00
}
if (n & 0x00000003L) {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
pos -= 2;
initial checking
2010-09-15 12:42:33 +00:00
} else {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
n >>= 2;
initial checking
2010-09-15 12:42:33 +00:00
}
if (n & 0x00000001L) {
reformat code using clang-format
2014-01-08 12:01:58 +00:00
pos -= 1;
initial checking
2010-09-15 12:42:33 +00:00
}
return pos;
remove concise_iterator, replace by c++11 version; clean up LeastSignificantBitPosition{32|64}
2014-04-16 09:57:29 +00:00
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline int LeastSignificantBitPosition32(uint32_t n) {
remove concise_iterator, replace by c++11 version; clean up LeastSignificantBitPosition{32|64}
2014-04-16 09:57:29 +00:00
DCHECK_NE(n, 0);
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
return LeastSignificantBitPosition32Fast(n);
remove concise_iterator, replace by c++11 version; clean up LeastSignificantBitPosition{32|64}
2014-04-16 09:57:29 +00:00
#elif defined(USE_DEBRUIJN)
return LeastSignificantBitPosition32DeBruijn(n);
#else
return LeastSignificantBitPosition32Default(n);
initial checking
2010-09-15 12:42:33 +00:00
#endif
}
// Returns the most significant bit position in n.
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
#if USE_FAST_LEAST_SIGNIFICANT_BIT
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline int MostSignificantBitPosition64Fast(uint64_t n) {
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
// __builtin_clzll(1) should always return 63. There is no penalty in
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
// using offset, and the code looks more like its uint32_t counterpart.
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
const int offset = __builtin_clzll(1);
remove std:: from std::min|max in comments; performance improvements on the SAT, bug fixes
2018-01-10 13:21:06 +01:00
return n == 0 ? 0 : (offset - __builtin_clzll(n));
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
}
initial checking
2010-09-15 12:42:33 +00:00
#endif
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline int MostSignificantBitPosition64Default(uint64_t n) {
initial checking
2010-09-15 12:42:33 +00:00
int b = 0;
if (0 != (n & (kAllBits64 << (1 << 5)))) {
b |= (1 << 5);
n >>= (1 << 5);
}
if (0 != (n & (kAllBits64 << (1 << 4)))) {
b |= (1 << 4);
n >>= (1 << 4);
}
if (0 != (n & (kAllBits64 << (1 << 3)))) {
b |= (1 << 3);
n >>= (1 << 3);
}
if (0 != (n & (kAllBits64 << (1 << 2)))) {
b |= (1 << 2);
n >>= (1 << 2);
}
if (0 != (n & (kAllBits64 << (1 << 1)))) {
b |= (1 << 1);
n >>= (1 << 1);
}
if (0 != (n & (kAllBits64 << (1 << 0)))) {
b |= (1 << 0);
}
return b;
}
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline int MostSignificantBitPosition64(uint64_t n) {
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
return MostSignificantBitPosition64Fast(n);
initial checking
2010-09-15 12:42:33 +00:00
#else
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
return MostSignificantBitPosition64Default(n);
#endif
}
#if USE_FAST_LEAST_SIGNIFICANT_BIT
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline int MostSignificantBitPosition32Fast(uint32_t n) {
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
// The constant here depends on whether we are on a 32-bit or 64-bit machine.
// __builtin_clzl(1) returns 63 on a 64-bit machine and 31 on a 32-bit
// machine.
const int offset = __builtin_clzl(1);
remove std:: from std::min|max in comments; performance improvements on the SAT, bug fixes
2018-01-10 13:21:06 +01:00
return n == 0 ? 0 : (offset - __builtin_clzl(n));
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
}
#endif
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline int MostSignificantBitPosition32Default(uint32_t n) {
initial checking
2010-09-15 12:42:33 +00:00
int b = 0;
if (0 != (n & (kAllBits32 << (1 << 4)))) {
b |= (1 << 4);
n >>= (1 << 4);
}
if (0 != (n & (kAllBits32 << (1 << 3)))) {
b |= (1 << 3);
n >>= (1 << 3);
}
if (0 != (n & (kAllBits32 << (1 << 2)))) {
b |= (1 << 2);
n >>= (1 << 2);
}
if (0 != (n & (kAllBits32 << (1 << 1)))) {
b |= (1 << 1);
n >>= (1 << 1);
}
if (0 != (n & (kAllBits32 << (1 << 0)))) {
b |= (1 << 0);
}
return b;
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline int MostSignificantBitPosition32(uint32_t n) {
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
return MostSignificantBitPosition32Fast(n);
#else
return MostSignificantBitPosition32Default(n);
initial checking
2010-09-15 12:42:33 +00:00
#endif
}
#undef USE_DEBRUIJN
Update of LSB/MSB code.
2015-06-15 11:46:24 +02:00
#undef USE_FAST_LEAST_SIGNIFICANT_BIT
initial checking
2010-09-15 12:42:33 +00:00
// Returns a word with bits from s to e set.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline uint64_t OneRange64(uint64_t s, uint64_t e) {
initial checking
2010-09-15 12:42:33 +00:00
DCHECK_LE(s, 63);
DCHECK_LE(e, 63);
DCHECK_LE(s, e);
return (kAllBits64 << s) ^ ((kAllBits64 - 1) << e);
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t OneRange32(uint32_t s, uint32_t e) {
initial checking
2010-09-15 12:42:33 +00:00
DCHECK_LE(s, 31);
DCHECK_LE(e, 31);
DCHECK_LE(s, e);
return (kAllBits32 << s) ^ ((kAllBits32 - 1) << e);
}
// Returns a word with s least significant bits unset.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline uint64_t IntervalUp64(uint64_t s) {
initial checking
2010-09-15 12:42:33 +00:00
DCHECK_LE(s, 63);
return kAllBits64 << s;
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t IntervalUp32(uint32_t s) {
initial checking
2010-09-15 12:42:33 +00:00
DCHECK_LE(s, 31);
return kAllBits32 << s;
}
// Returns a word with the s most significant bits unset.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline uint64_t IntervalDown64(uint64_t s) {
initial checking
2010-09-15 12:42:33 +00:00
DCHECK_LE(s, 63);
return kAllBits64 >> (63 - s);
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t IntervalDown32(uint32_t s) {
initial checking
2010-09-15 12:42:33 +00:00
DCHECK_LE(s, 31);
return kAllBits32 >> (31 - s);
}
// ----- Bitset operators -----
sync from google3
2024-03-15 16:38:25 +01:00
// Bitset: array of uint32_t/uint64_t words
initial checking
2010-09-15 12:42:33 +00:00
// Bit operators used to manipulates bitsets.
// Returns the bit number in the word computed by BitOffsetXX,
// corresponding to the bit at position pos in the bitset.
// Note: '& 63' is faster than '% 64'
// TODO(user): rename BitPos and BitOffset to something more understandable.
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t BitPos64(uint64_t pos) { return (pos & 63); }
inline uint32_t BitPos32(uint32_t pos) { return (pos & 31); }
initial checking
2010-09-15 12:42:33 +00:00
// Returns the word number corresponding to bit number pos.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline uint64_t BitOffset64(uint64_t pos) { return (pos >> 6); }
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t BitOffset32(uint32_t pos) { return (pos >> 5); }
initial checking
2010-09-15 12:42:33 +00:00
// Returns the number of words needed to store size bits.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline uint64_t BitLength64(uint64_t size) { return ((size + 63) >> 6); }
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t BitLength32(uint32_t size) { return ((size + 31) >> 5); }
initial checking
2010-09-15 12:42:33 +00:00
// Returns the bit number in the bitset of the first bit of word number v.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline uint64_t BitShift64(uint64_t v) { return v << 6; }
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline uint32_t BitShift32(uint32_t v) { return v << 5; }
initial checking
2010-09-15 12:42:33 +00:00
// Returns true if the bit pos is set in bitset.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline bool IsBitSet64(const uint64_t* const bitset, uint64_t pos) {
initial checking
2010-09-15 12:42:33 +00:00
return (bitset[BitOffset64(pos)] & OneBit64(BitPos64(pos)));
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline bool IsBitSet32(const uint32_t* const bitset, uint32_t pos) {
initial checking
2010-09-15 12:42:33 +00:00
return (bitset[BitOffset32(pos)] & OneBit32(BitPos32(pos)));
}
// Sets the bit pos to true in bitset.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline void SetBit64(uint64_t* const bitset, uint64_t pos) {
initial checking
2010-09-15 12:42:33 +00:00
bitset[BitOffset64(pos)] |= OneBit64(BitPos64(pos));
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline void SetBit32(uint32_t* const bitset, uint32_t pos) {
initial checking
2010-09-15 12:42:33 +00:00
bitset[BitOffset32(pos)] |= OneBit32(BitPos32(pos));
}
// Sets the bit pos to false in bitset.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
inline void ClearBit64(uint64_t* const bitset, uint64_t pos) {
initial checking
2010-09-15 12:42:33 +00:00
bitset[BitOffset64(pos)] &= ~OneBit64(BitPos64(pos));
}
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
inline void ClearBit32(uint32_t* const bitset, uint32_t pos) {
initial checking
2010-09-15 12:42:33 +00:00
bitset[BitOffset32(pos)] &= ~OneBit32(BitPos32(pos));
}
// Returns the number of bits set in bitset between positions start and end.
export from google3
2023-05-24 15:34:42 +02:00
uint64_t BitCountRange64(const uint64_t* bitset, uint64_t start, uint64_t end);
uint32_t BitCountRange32(const uint32_t* bitset, uint32_t start, uint32_t end);
initial checking
2010-09-15 12:42:33 +00:00
// Returns true if no bits are set in bitset between start and end.
export from google3
2023-05-24 15:34:42 +02:00
bool IsEmptyRange64(const uint64_t* bitset, uint64_t start, uint64_t end);
bool IsEmptyRange32(const uint32_t* bitset, uint32_t start, uint32_t end);
initial checking
2010-09-15 12:42:33 +00:00
// Returns the first bit set in bitset between start and max_bit.
export from google3
2023-05-24 15:34:42 +02:00
int64_t LeastSignificantBitPosition64(const uint64_t* bitset, uint64_t start,
uint64_t end);
int LeastSignificantBitPosition32(const uint32_t* bitset, uint32_t start,
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
uint32_t end);
initial checking
2010-09-15 12:42:33 +00:00
// Returns the last bit set in bitset between min_bit and start.
export from google3
2023-05-24 15:34:42 +02:00
int64_t MostSignificantBitPosition64(const uint64_t* bitset, uint64_t start,
uint64_t end);
int MostSignificantBitPosition32(const uint32_t* bitset, uint32_t start,
util: [u]int32 -> [u]int32_t note: sed -i 's/\b\([u]\?int32\)\b/\1_t/g' *.h *.cc
2021-04-05 13:48:47 +02:00
uint32_t end);
initial checking
2010-09-15 12:42:33 +00:00
// Unsafe versions of the functions above where respectively end and start
// are supposed to be set.
export from google3
2023-05-24 15:34:42 +02:00
int64_t UnsafeLeastSignificantBitPosition64(const uint64_t* bitset,
reindent after int64 -> int64_t change
2021-04-08 18:26:38 +02:00
uint64_t start, uint64_t end);
export from google3
2023-05-24 15:34:42 +02:00
int32_t UnsafeLeastSignificantBitPosition32(const uint32_t* bitset,
reindent after int64 -> int64_t change
2021-04-08 18:26:38 +02:00
uint32_t start, uint32_t end);
initial checking
2010-09-15 12:42:33 +00:00
export from google3
2023-05-24 15:34:42 +02:00
int64_t UnsafeMostSignificantBitPosition64(const uint64_t* bitset,
reindent after int64 -> int64_t change
2021-04-08 18:26:38 +02:00
uint64_t start, uint64_t end);
export from google3
2023-05-24 15:34:42 +02:00
int32_t UnsafeMostSignificantBitPosition32(const uint32_t* bitset,
reindent after int64 -> int64_t change
2021-04-08 18:26:38 +02:00
uint32_t start, uint32_t end);
initial checking
2010-09-15 12:42:33 +00:00
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
// Returns a mask with the bits pos % 64 and (pos ^ 1) % 64 sets.
reindent after int64 -> int64_t change
2021-04-08 18:26:38 +02:00
inline uint64_t TwoBitsFromPos64(uint64_t pos) {
return uint64_t{3} << (pos & 62);
}
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
// This class is like an ITIVector<IndexType, bool> except that it provides a
// more efficient way to iterate over the positions set to true. It achieves
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
// this by caching the current uint64_t bucket in the Iterator and using
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
// LeastSignificantBitPosition64() to iterate over the positions at 1 in this
// bucket.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
template <typename IndexType = int64_t>
reapply google format
2020-10-22 23:36:58 +02:00
class Bitset64 {
public:
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
using value_type = IndexType;
[CP-SAT] better unsat reporting; improve linear propagation
2024-04-17 14:13:41 +02:00
// When speed matter, caching the base pointer helps.
speed up bitset
2022-11-22 17:44:54 +01:00
class ConstView {
public:
explicit ConstView(const Bitset64* bitset) : data_(bitset->data_.data()) {}
bool operator[](IndexType i) const {
return data_[BitOffset64(Value(i))] & OneBit64(BitPos64(Value(i)));
}
const uint64_t* data() const { return data_; }
private:
const uint64_t* const data_;
};
[CP-SAT] better unsat reporting; improve linear propagation
2024-04-17 14:13:41 +02:00
class View {
public:
explicit View(Bitset64* bitset) : data_(bitset->data_.data()) {}
bool operator[](IndexType i) const {
return data_[BitOffset64(Value(i))] & OneBit64(BitPos64(Value(i)));
}
void Clear(IndexType i) {
data_[BitOffset64(Value(i))] &= ~OneBit64(BitPos64(Value(i)));
}
void Set(IndexType i) {
data_[BitOffset64(Value(i))] |= OneBit64(BitPos64(Value(i)));
}
private:
uint64_t* const data_;
};
speed up bitset
2022-11-22 17:44:54 +01:00
Bitset64() : size_(), data_() {}
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
explicit Bitset64(IndexType size)
speedup bitsets
2014-03-21 18:01:18 +00:00
: size_(Value(size) > 0 ? size : IndexType(0)),
speed up bitset
2022-11-22 17:44:54 +01:00
data_(BitLength64(Value(size_))) {}
ConstView const_view() const { return ConstView(this); }
[CP-SAT] better unsat reporting; improve linear propagation
2024-04-17 14:13:41 +02:00
View view() { return View(this); }
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
// Returns how many bits this Bitset64 can hold.
IndexType size() const { return size_; }
huge sync with internal version
2013-06-11 14:53:20 +00:00
// Appends value at the end of the bitset.
void PushBack(bool value) {
++size_;
speedup bitsets
2014-03-21 18:01:18 +00:00
data_.resize(BitLength64(Value(size_)), 0);
huge sync with internal version
2013-06-11 14:53:20 +00:00
Set(size_ - 1, value);
}
speedup bitsets
2014-03-21 18:01:18 +00:00
// Resizes the Bitset64 to the given number of bits. New bits are sets to 0.
fix
2023-02-06 17:19:44 +01:00
void resize(int size) { Resize(IndexType(size)); }
add core computation to sat solver; add vehicle dependent dimensions in routing
2014-01-27 15:05:30 +00:00
void Resize(IndexType size) {
speedup bitsets
2014-03-21 18:01:18 +00:00
DCHECK_GE(Value(size), 0);
fix
2024-01-23 14:15:18 +01:00
IndexType new_size = Value(size) > 0 ? size : IndexType(0);
if (new_size < size_ && Value(new_size) > 0) {
const int64_t new_data_size = BitLength64(Value(new_size));
const uint64_t bitmask = kAllBitsButLsb64
<< BitPos64(Value(new_size) - 1);
data_[new_data_size - 1] &= ~bitmask;
}
size_ = new_size;
speedup bitsets
2014-03-21 18:01:18 +00:00
data_.resize(BitLength64(Value(size_)), 0);
add core computation to sat solver; add vehicle dependent dimensions in routing
2014-01-27 15:05:30 +00:00
}
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
// Changes the number of bits the Bitset64 can hold and set all of them to 0.
void ClearAndResize(IndexType size) {
speedup bitsets
2014-03-21 18:01:18 +00:00
DCHECK_GE(Value(size), 0);
size_ = Value(size) > 0 ? size : IndexType(0);
// Memset is 4x faster than data_.assign() as of 19/03/2014.
// TODO(user): Ideally if a realloc happens, we don't need to copy the old
// data...
const size_t bit_length = static_cast<size_t>(BitLength64(Value(size_)));
const size_t to_clear = std::min(data_.size(), bit_length);
data_.resize(bit_length, 0);
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
memset(data_.data(), 0, to_clear * sizeof(int64_t));
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
// Sets all bits to 0.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
void ClearAll() { memset(data_.data(), 0, data_.size() * sizeof(int64_t)); }
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
// Sets the bit at position i to 0.
void Clear(IndexType i) {
speedup bitsets
2014-03-21 18:01:18 +00:00
DCHECK_GE(Value(i), 0);
cosmetic improvements to the code
2017-04-19 16:20:56 +02:00
DCHECK_LT(Value(i), Value(size_));
minor optim
2025-01-30 14:25:55 +01:00
data_.data()[BitOffset64(Value(i))] &= ~OneBit64(BitPos64(Value(i)));
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
// Sets bucket containing bit i to 0.
void ClearBucket(IndexType i) {
DCHECK_GE(Value(i), 0);
cosmetic improvements to the code
2017-04-19 16:20:56 +02:00
DCHECK_LT(Value(i), Value(size_));
[CP-SAT] more fuzzer bugfixes; tweaking ot the max clique heuristics
2024-11-15 15:27:50 +01:00
data_.data()[BitOffset64(Value(i))] = 0;
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
}
minor changes to statistics module, add one api on bitsets
2014-05-21 12:54:10 +00:00
// Clears the bits at position i and i ^ 1.
void ClearTwoBits(IndexType i) {
speedup bitsets
2014-03-21 18:01:18 +00:00
DCHECK_GE(Value(i), 0);
cosmetic improvements to the code
2017-04-19 16:20:56 +02:00
DCHECK_LT(Value(i), Value(size_));
minor changes to statistics module, add one api on bitsets
2014-05-21 12:54:10 +00:00
data_[BitOffset64(Value(i))] &= ~TwoBitsFromPos64(Value(i));
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
}
// Returns true if the bit at position i or the one at position i ^ 1 is set.
bool AreOneOfTwoBitsSet(IndexType i) const {
speedup bitsets
2014-03-21 18:01:18 +00:00
DCHECK_GE(Value(i), 0);
cosmetic improvements to the code
2017-04-19 16:20:56 +02:00
DCHECK_LT(Value(i), Value(size_));
minor optim
2025-01-30 14:25:55 +01:00
return data_.data()[BitOffset64(Value(i))] & TwoBitsFromPos64(Value(i));
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
}
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
// Returns true if the bit at position i is set.
bool IsSet(IndexType i) const {
speedup bitsets
2014-03-21 18:01:18 +00:00
DCHECK_GE(Value(i), 0);
cosmetic improvements to the code
2017-04-19 16:20:56 +02:00
DCHECK_LT(Value(i), Value(size_));
minor optim
2025-01-30 14:25:55 +01:00
return data_.data()[BitOffset64(Value(i))] & OneBit64(BitPos64(Value(i)));
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
speedup bitsets
2014-03-21 18:01:18 +00:00
// Same as IsSet().
bool operator[](IndexType i) const { return IsSet(i); }
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
// Sets the bit at position i to 1.
void Set(IndexType i) {
speedup bitsets
2014-03-21 18:01:18 +00:00
DCHECK_GE(Value(i), 0);
DCHECK_LT(Value(i), size_);
sat: export from google3
2024-09-27 11:10:42 +02:00
// The c++ hardening is costly here, so we disable it.
minor optim
2025-01-30 14:25:55 +01:00
data_.data()[BitOffset64(Value(i))] |= OneBit64(BitPos64(Value(i)));
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
// If value is true, sets the bit at position i to 1, sets it to 0 otherwise.
void Set(IndexType i, bool value) {
if (value) {
Set(i);
} else {
Clear(i);
}
}
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
// Copies bucket containing bit i from "other" to "this".
format file forcing the left alignment
2020-10-29 14:25:39 +01:00
void CopyBucket(const Bitset64<IndexType>& other, IndexType i) {
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
const uint64_t offset = BitOffset64(Value(i));
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
data_[offset] = other.data_[offset];
}
// Copies "other" to "this". The bitsets do not have to be of the same size.
// If "other" is smaller, high order bits are not changed. If "other" is
// larger, its high order bits are ignored. In any case "this" is not resized.
cosmetic improvements to the code
2017-04-19 16:20:56 +02:00
template <typename OtherIndexType>
format file forcing the left alignment
2020-10-29 14:25:39 +01:00
void SetContentFromBitset(const Bitset64<OtherIndexType>& other) {
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
const int64_t min_size = std::min(data_.size(), other.data_.size());
reapply google format
2020-10-22 23:36:58 +02:00
if (min_size == 0) return;
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
const uint64_t last_common_bucket = data_[min_size - 1];
memcpy(data_.data(), other.data_.data(), min_size * sizeof(uint64_t));
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
if (data_.size() >= other.data_.size()) {
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
const uint64_t bitmask = kAllBitsButLsb64
reindent after int64 -> int64_t change
2021-04-08 18:26:38 +02:00
<< BitPos64(other.Value(other.size() - 1));
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
data_[min_size - 1] &= ~bitmask;
data_[min_size - 1] |= (bitmask & last_common_bucket);
}
}
// Same as SetContentFromBitset where "this" and "other" have the same size.
cosmetic improvements to the code
2017-04-19 16:20:56 +02:00
template <typename OtherIndexType>
format file forcing the left alignment
2020-10-29 14:25:39 +01:00
void SetContentFromBitsetOfSameSize(const Bitset64<OtherIndexType>& other) {
cosmetic improvements to the code
2017-04-19 16:20:56 +02:00
DCHECK_EQ(Value(size()), other.Value(other.size()));
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
memcpy(data_.data(), other.data_.data(), data_.size() * sizeof(uint64_t));
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
}
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
// Sets "this" to be the intersection of "this" and "other". The
// bitsets do not have to be the same size. If other is smaller, all
// the higher order bits are assumed to be 0.
format file forcing the left alignment
2020-10-29 14:25:39 +01:00
void Intersection(const Bitset64<IndexType>& other) {
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
const int min_size = std::min(data_.size(), other.data_.size());
speedup glop; better respect the time limit
2025-02-05 18:11:16 +01:00
uint64_t* const d = data_.data();
const uint64_t* const o = other.data_.data();
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
for (int i = 0; i < min_size; ++i) {
speedup glop; better respect the time limit
2025-02-05 18:11:16 +01:00
d[i] &= o[i];
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
for (int i = min_size; i < data_.size(); ++i) {
speedup glop; better respect the time limit
2025-02-05 18:11:16 +01:00
d[i] = 0;
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
}
sat: export from google3
2024-09-27 11:10:42 +02:00
// This one assume both given bitset to be of the same size.
void SetToIntersectionOf(const Bitset64<IndexType>& a,
const Bitset64<IndexType>& b) {
DCHECK_EQ(a.size(), b.size());
Resize(a.size());
// Copy buckets.
const int num_buckets = a.data_.size();
for (int i = 0; i < num_buckets; ++i) {
data_[i] = a.data_[i] & b.data_[i];
}
}
add objective tabu search in local search; remove hash_map/hash_set in the routing library; implement network_flow and network_flow_cost in sat and sat/flatzinc; implement timetable_edgefinding in sat/cumulative; move code around in the christofides algotithm
2017-02-06 16:11:43 +01:00
// Sets "this" to be the union of "this" and "other". The
// bitsets do not have to be the same size. If other is smaller, all
// the higher order bits are assumed to be 0.
format file forcing the left alignment
2020-10-29 14:25:39 +01:00
void Union(const Bitset64<IndexType>& other) {
add objective tabu search in local search; remove hash_map/hash_set in the routing library; implement network_flow and network_flow_cost in sat and sat/flatzinc; implement timetable_edgefinding in sat/cumulative; move code around in the christofides algotithm
2017-02-06 16:11:43 +01:00
const int min_size = std::min(data_.size(), other.data_.size());
for (int i = 0; i < min_size; ++i) {
data_[i] |= other.data_[i];
}
}
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
// Class to iterate over the bit positions at 1 of a Bitset64.
speedup bitsets
2014-03-21 18:01:18 +00:00
//
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
// IMPORTANT: Because the iterator "caches" the current uint64_t bucket, this
speedup bitsets
2014-03-21 18:01:18 +00:00
// will probably not do what you want if Bitset64 is modified while iterating.
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
class Iterator {
reapply google format
2020-10-22 23:36:58 +02:00
public:
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
// Make this iterator a std::forward_iterator, so it works with std::sample,
// std::max_element, etc.
Iterator() : data_(nullptr), size_(0) {}
Iterator(Iterator&& other) = default;
Iterator(const Iterator& other) = default;
Iterator& operator=(const Iterator& other) = default;
using difference_type = std::ptrdiff_t;
using iterator_category = std::forward_iterator_tag;
using value_type = IndexType;
using size_type = std::size_t;
using reference = value_type&;
using pointer = value_type*;
speed up bitset
2022-11-22 17:44:54 +01:00
explicit Iterator(const Bitset64& bitset)
: data_(bitset.data_.data()), size_(bitset.data_.size()) {
if (!bitset.data_.empty()) {
current_ = data_[0];
this->operator++();
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
}
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
static Iterator EndIterator(const Bitset64& bitset) {
return Iterator(bitset.data_.data());
}
fix
2024-01-31 16:19:50 +01:00
bool operator==(const Iterator& other) const { return !(*this != other); }
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
bool operator!=(const Iterator& other) const {
if (other.size_ == 0) {
return size_ != 0;
}
return std::tie(index_, current_) !=
std::tie(other.index_, other.current_);
}
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
speed up bitset
2022-11-22 17:44:54 +01:00
IndexType operator*() const { return IndexType(index_); }
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
Iterator operator++(int) {
Iterator other = *this;
fix
2024-01-31 16:19:50 +01:00
++(*this);
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
return other;
}
Iterator& operator++() {
speed up bitset
2022-11-22 17:44:54 +01:00
int bucket = BitOffset64(index_);
while (current_ == 0) {
bucket++;
if (bucket == size_) {
size_ = 0;
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
return *this;
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
speed up bitset
2022-11-22 17:44:54 +01:00
current_ = data_[bucket];
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
// Computes the index and clear the least significant bit of current_.
speed up bitset
2022-11-22 17:44:54 +01:00
index_ = BitShift64(bucket) | LeastSignificantBitPosition64(current_);
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
current_ &= current_ - 1;
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
return *this;
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
reapply google format
2020-10-22 23:36:58 +02:00
private:
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
explicit Iterator(const uint64_t* data) : data_(data), size_(0) {}
const uint64_t* data_;
speed up bitset
2022-11-22 17:44:54 +01:00
int size_;
int index_ = 0;
uint64_t current_ = 0;
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
};
huge sync with internal version
2013-06-11 14:53:20 +00:00
// Allows range-based "for" loop on the non-zero positions:
// for (const IndexType index : bitset) {}
Iterator begin() const { return Iterator(*this); }
[CP-SAT] cleanup diffn propagation; remove dead code
2024-01-31 14:44:02 +01:00
Iterator end() const { return Iterator::EndIterator(*this); }
huge sync with internal version
2013-06-11 14:53:20 +00:00
simplify glop branching code
2021-04-14 14:33:47 +02:00
// Cryptic function! This is just an optimized version of a given piece of
// code and has probably little general use.
static uint64_t ConditionalXorOfTwoBits(IndexType i, uint64_t use1,
[CP-SAT] speedup on constraint_violation; cleanup clause invariants; fix explanation of divition
2023-10-15 18:08:33 +02:00
Bitset64<IndexType>::ConstView set1,
simplify glop branching code
2021-04-14 14:33:47 +02:00
uint64_t use2,
[CP-SAT] speedup on constraint_violation; cleanup clause invariants; fix explanation of divition
2023-10-15 18:08:33 +02:00
Bitset64<IndexType>::ConstView set2) {
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
DCHECK(use1 == 0 || use1 == 1);
DCHECK(use2 == 0 || use2 == 1);
speedup bitsets
2014-03-21 18:01:18 +00:00
const int bucket = BitOffset64(Value(i));
const int pos = BitPos64(Value(i));
[CP-SAT] speedup on constraint_violation; cleanup clause invariants; fix explanation of divition
2023-10-15 18:08:33 +02:00
return ((use1 << pos) & set1.data()[bucket]) ^
((use2 << pos) & set2.data()[bucket]);
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
}
bump abseil to the latest version, adapt the code all around
2019-11-20 14:28:11 -08:00
// Returns a 0/1 string representing the bitset.
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
std::string DebugString() const {
std::string output;
for (IndexType i(0); i < size(); ++i) {
output += IsSet(i) ? "1" : "0";
}
return output;
}
speedup glop; better respect the time limit
2025-02-05 18:11:16 +01:00
bool IsAllFalse() const {
return std::all_of(data_.begin(), data_.end(),
[](uint64_t v) { return v == 0; });
}
reapply google format
2020-10-22 23:36:58 +02:00
private:
speedup bitsets
2014-03-21 18:01:18 +00:00
// Returns the value of the index type.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
// This function is specialized below to work with IntType and int64_t.
Use pybind11 instead for swig for sorted_interval_list and cp_sat swig_helper; speed up CP-SAT presolve; add missing std includes
2022-02-22 18:33:45 +01:00
static int Value(IndexType input);
speedup bitsets
2014-03-21 18:01:18 +00:00
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
IndexType size_;
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
std::vector<uint64_t> data_;
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
reapply google format
2020-10-22 23:36:58 +02:00
template <class OtherIndexType>
friend class Bitset64;
sync with internal code, most notable change is the modification to the RoutingModel::AddDimension API that takes an additional boolean parameter
2013-01-10 17:01:34 +00:00
};
large rewrite in the documentation/headers; changed implementation of the ForbiddenInterval constraints, renamed to NotMember; remove unused mode in sat; rewrite of internals of glop; change callbacks to std::function in shortestpath.h; random sync with interval code
2016-06-02 13:19:10 +02:00
// Specialized version of Bitset64 that allows to query the last bit set more
// efficiently.
class BitQueue64 {
reapply google format
2020-10-22 23:36:58 +02:00
public:
large rewrite in the documentation/headers; changed implementation of the ForbiddenInterval constraints, renamed to NotMember; remove unused mode in sat; rewrite of internals of glop; change callbacks to std::function in shortestpath.h; random sync with interval code
2016-06-02 13:19:10 +02:00
BitQueue64() : size_(), top_(-1), data_() {}
explicit BitQueue64(int size)
: size_(size), top_(-1), data_(BitLength64(size), 0) {}
remove obsolete macro
2023-08-30 10:04:47 -04:00
// This type is neither copyable nor movable.
BitQueue64(const BitQueue64&) = delete;
BitQueue64& operator=(const BitQueue64&) = delete;
large rewrite in the documentation/headers; changed implementation of the ForbiddenInterval constraints, renamed to NotMember; remove unused mode in sat; rewrite of internals of glop; change callbacks to std::function in shortestpath.h; random sync with interval code
2016-06-02 13:19:10 +02:00
void IncreaseSize(int size) {
CHECK_GE(size, size_);
size_ = size;
data_.resize(BitLength64(size), 0);
}
void ClearAndResize(int size) {
top_ = -1;
size_ = size;
data_.assign(BitLength64(size), 0);
}
void Set(int i) {
DCHECK_GE(i, 0);
DCHECK_LT(i, size_);
top_ = std::max(top_, i);
data_[BitOffset64(i)] |= OneBit64(BitPos64(i));
}
add missing API to BitQueue64
2017-11-24 11:07:21 +01:00
// Sets all the bits from 0 up to i-1 to 1.
void SetAllBefore(int i) {
DCHECK_GE(i, 0);
DCHECK_LT(i, size_);
top_ = std::max(top_, i - 1);
change BitOffset64 API to return uint32
2018-02-12 11:39:56 +01:00
int bucket_index = static_cast<int>(BitOffset64(i));
add missing API to BitQueue64
2017-11-24 11:07:21 +01:00
data_[bucket_index] |= OneBit64(BitPos64(i)) - 1;
for (--bucket_index; bucket_index >= 0; --bucket_index) {
data_[bucket_index] = kAllBits64;
}
}
large rewrite in the documentation/headers; changed implementation of the ForbiddenInterval constraints, renamed to NotMember; remove unused mode in sat; rewrite of internals of glop; change callbacks to std::function in shortestpath.h; random sync with interval code
2016-06-02 13:19:10 +02:00
// Returns the position of the highest bit set in O(1) or -1 if no bit is set.
int Top() const { return top_; }
// Clears the Top() bit and recomputes the position of the next Top().
void ClearTop() {
DCHECK_NE(top_, -1);
change BitOffset64 API to return uint32
2018-02-12 11:39:56 +01:00
int bucket_index = static_cast<int>(BitOffset64(top_));
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
uint64_t bucket = data_[bucket_index] &= ~OneBit64(BitPos64(top_));
large rewrite in the documentation/headers; changed implementation of the ForbiddenInterval constraints, renamed to NotMember; remove unused mode in sat; rewrite of internals of glop; change callbacks to std::function in shortestpath.h; random sync with interval code
2016-06-02 13:19:10 +02:00
while (!bucket) {
if (bucket_index == 0) {
top_ = -1;
return;
}
bucket = data_[--bucket_index];
}
// Note(user): I experimented with reversing the bit order in a bucket to
// use LeastSignificantBitPosition64() and it is only slightly faster at the
fix: typo spelling grammar
2021-08-15 23:11:16 +07:00
// cost of a lower Set() speed. So I preferred this version.
change BitOffset64 API to return uint32
2018-02-12 11:39:56 +01:00
top_ = static_cast<int>(BitShift64(bucket_index) +
MostSignificantBitPosition64(bucket));
large rewrite in the documentation/headers; changed implementation of the ForbiddenInterval constraints, renamed to NotMember; remove unused mode in sat; rewrite of internals of glop; change callbacks to std::function in shortestpath.h; random sync with interval code
2016-06-02 13:19:10 +02:00
}
reapply google format
2020-10-22 23:36:58 +02:00
private:
large rewrite in the documentation/headers; changed implementation of the ForbiddenInterval constraints, renamed to NotMember; remove unused mode in sat; rewrite of internals of glop; change callbacks to std::function in shortestpath.h; random sync with interval code
2016-06-02 13:19:10 +02:00
int size_;
int top_;
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
std::vector<uint64_t> data_;
large rewrite in the documentation/headers; changed implementation of the ForbiddenInterval constraints, renamed to NotMember; remove unused mode in sat; rewrite of internals of glop; change callbacks to std::function in shortestpath.h; random sync with interval code
2016-06-02 13:19:10 +02:00
};
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
// The specialization of Value() for IntType and int64_t.
speedup bitsets
2014-03-21 18:01:18 +00:00
template <typename IntType>
Use pybind11 instead for swig for sorted_interval_list and cp_sat swig_helper; speed up CP-SAT presolve; add missing std includes
2022-02-22 18:33:45 +01:00
inline int Bitset64<IntType>::Value(IntType input) {
speedup bitsets
2014-03-21 18:01:18 +00:00
DCHECK_GE(input.value(), 0);
return input.value();
}
reapply google format
2020-10-22 23:36:58 +02:00
template <>
Use pybind11 instead for swig for sorted_interval_list and cp_sat swig_helper; speed up CP-SAT presolve; add missing std includes
2022-02-22 18:33:45 +01:00
inline int Bitset64<int>::Value(int input) {
DCHECK_GE(input, 0);
return input;
}
template <>
inline int Bitset64<int64_t>::Value(int64_t input) {
speedup bitsets
2014-03-21 18:01:18 +00:00
DCHECK_GE(input, 0);
return input;
}
add API in ortools/util
2024-09-23 16:04:53 +02:00
template <>
inline int Bitset64<size_t>::Value(size_t input) {
return input;
}
speedup bitsets
2014-03-21 18:01:18 +00:00
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
// A simple utility class to set/unset integer in a range [0, size).
// This is optimized for sparsity.
cpp: Migrate int64 to int64_t
2021-04-01 12:13:35 +02:00
template <typename IntegerType = int64_t>
reapply google format
2020-10-22 23:36:58 +02:00
class SparseBitset {
public:
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
SparseBitset() {}
speedup bitsets
2014-03-21 18:01:18 +00:00
explicit SparseBitset(IntegerType size) : bitset_(size) {}
remove obsolete macro
2023-08-30 10:04:47 -04:00
// This type is neither copyable nor movable.
SparseBitset(const SparseBitset&) = delete;
SparseBitset& operator=(const SparseBitset&) = delete;
speedup bitsets
2014-03-21 18:01:18 +00:00
IntegerType size() const { return bitset_.size(); }
change bitset API
2025-03-05 14:03:49 +01:00
void ResetAllToFalse() { ClearAndResize(size()); }
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
void ClearAndResize(IntegerType size) {
speedup bitsets
2014-03-21 18:01:18 +00:00
// As of 19/03/2014, experiments show that this is a reasonable threshold.
const int kSparseThreshold = 300;
if (to_clear_.size() * kSparseThreshold < size) {
change bitset API
2025-03-05 14:03:49 +01:00
for (const IntegerType i : to_clear_) bitset_.ClearBucket(i);
to_clear_.clear();
speedup bitsets
2014-03-21 18:01:18 +00:00
bitset_.Resize(size);
} else {
bitset_.ClearAndResize(size);
more work on src/util, mainly on the bitset class
2014-04-04 09:13:02 +00:00
to_clear_.clear();
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
}
}
more work on the sat solver
2014-07-29 00:58:38 +00:00
void Resize(IntegerType size) {
if (size < bitset_.size()) {
int new_index = 0;
for (IntegerType index : to_clear_) {
if (index < size) {
to_clear_[new_index] = index;
++new_index;
}
}
to_clear_.resize(new_index);
}
bitset_.Resize(size);
}
speedup bitsets
2014-03-21 18:01:18 +00:00
bool operator[](IntegerType index) const { return bitset_[index]; }
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
void Set(IntegerType index) {
speedup bitsets
2014-03-21 18:01:18 +00:00
if (!bitset_[index]) {
bitset_.Set(index);
more cleaning on swiging of vectors in python; misc improvements
2013-12-10 15:58:07 +00:00
to_clear_.push_back(index);
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
}
}
sat: export from google3
2024-09-27 11:10:42 +02:00
minor API on bitsets; it
2025-10-16 13:29:59 +02:00
void CopyFrom(const SparseBitset& other) {
bitset_.ClearAndResize(other.size());
bitset_.SetContentFromBitsetOfSameSize(other.bitset_);
to_clear_.assign(other.to_clear_.begin(), other.to_clear_.end());
}
sat: export from google3
2024-09-27 11:10:42 +02:00
// A bit hacky for really hot loop.
typename Bitset64<IntegerType>::View BitsetView() { return bitset_.view(); }
[CP-SAT] more work on precedences; and no_overlap_2d
2025-06-17 12:48:24 +02:00
typename Bitset64<IntegerType>::ConstView BitsetConstView() {
return bitset_.const_view();
}
sat: export from google3
2024-09-27 11:10:42 +02:00
void SetUnsafe(typename Bitset64<IntegerType>::View view, IntegerType index) {
view.Set(index);
fix
2023-02-06 19:02:44 +01:00
to_clear_.push_back(index);
}
sat: export from google3
2024-09-27 11:10:42 +02:00
speedup bitsets
2014-03-21 18:01:18 +00:00
void Clear(IntegerType index) { bitset_.Clear(index); }
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
int NumberOfSetCallsWithDifferentArguments() const {
return to_clear_.size();
}
format file forcing the left alignment
2020-10-29 14:25:39 +01:00
const std::vector<IntegerType>& PositionsSetAtLeastOnce() const {
more cleaning on swiging of vectors in python; misc improvements
2013-12-10 15:58:07 +00:00
return to_clear_;
}
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
more work on the sat solver
2014-07-29 00:58:38 +00:00
// Tells the class that all its bits are cleared, so it can reset to_clear_
// to the empty vector. Note that this call is "unsafe" since the fact that
// the class is actually all cleared is only checked in debug mode.
//
// This is useful to iterate on the "set" positions while clearing them for
// instance. This way, after the loop, a client can call this for efficiency.
void NotifyAllClear() {
big includes cleanup
2025-02-24 22:59:21 +01:00
#if !defined(NDEBUG)
for (IntegerType index : to_clear_) CHECK(!bitset_[index]);
#endif
more work on the sat solver
2014-07-29 00:58:38 +00:00
to_clear_.clear();
}
fix
2023-02-06 19:02:44 +01:00
typename Bitset64<IntegerType>::ConstView const_view() const {
return bitset_.const_view();
}
reapply google format
2020-10-22 23:36:58 +02:00
private:
speedup bitsets
2014-03-21 18:01:18 +00:00
Bitset64<IntegerType> bitset_;
more cleaning on swiging of vectors in python; misc improvements
2013-12-10 15:58:07 +00:00
std::vector<IntegerType> to_clear_;
scoped_ptr -> unique_ptr; improve piecewise linear functions
2013-12-05 09:23:39 +00:00
};
reapply google format
2020-10-22 23:36:58 +02:00
} // namespace operations_research
initial checking
2010-09-15 12:42:33 +00:00
util: update include guards
2025-11-05 10:13:48 +01:00
#endif // ORTOOLS_UTIL_BITSET_H_
Reference in New Issue Copy Permalink