choco-solver
choco-solver copied to clipboard
SparseBitSet for a backtrackable bitset with mostly 0s.
This implementation for IStateBitSet targets backtrackable bitsets that mostly contains 0. For non-dense bitsets, this implementation is more efficient in terms of memory usage as bitsets are allocated per region instead of relying on a single, possibly bit array. In this context, the iteration is also faster.
This patch does not force any integration inside choco Environment given the criticality of that part. For the moment, this is just something I will have in btrplace and that may be useful for everyone.
The following code throws an error:
IEnvironment env = new EnvironmentTrailing();
IStateBitSet bs = env.makeSparseBitset(64);
bs.set(100);
bs.set(200);
bs.clear(101, 199);
Indeed, in SparseBitSet#clear(int,int)
, line 286:
final int st;
if (bIdx == blockIndex(from)) {
st = from;
} else {
st = 0;
}
st = from
should be replaced by st = localIndex(from);
right?