choco-solver icon indicating copy to clipboard operation
choco-solver copied to clipboard

SparseBitSet for a backtrackable bitset with mostly 0s.

Open fhermeni opened this issue 2 years ago • 1 comments

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.

fhermeni avatar Sep 12 '22 10:09 fhermeni

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.

fhermeni avatar Sep 12 '22 13:09 fhermeni

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?

cprudhom avatar Oct 05 '23 09:10 cprudhom