Repository: jtablesaw/tablesaw
Pull request #1099 (2022-04-04 21:02:27)

implemented a BitSetBackedSelection. Made it the default selection pr…
…oduced by BooleanColumn ops

Thanks for contributing.

- [x] Tick to sign-off your agreement to the [Developer Certificate of Origin (DCO) 1.1](https://developercertificate.org)

## Description

implemented a BitSetBackedSelection. Made it the default selection produced by BooleanColumn operations. 

The performance of RoaringBitmap is not great when there are few if any runs in the selection. This should provide more consistent, fast performance where few Selections are needed (as in where clauses). The RoaringBitmap backed selection will continue to be useful for group-by operations, where the number of selections could be very large. 

## Testing

Did you add a unit test? Yes. a whole bunch



Patch:
diff --git a/core/src/main/java/tech/tablesaw/columns/booleans/BitSetBooleanData.java b/core/src/main/java/tech/tablesaw/columns/booleans/BitSetBooleanData.java
index 836a6e0c..16bd3d21 100644
--- a/core/src/main/java/tech/tablesaw/columns/booleans/BitSetBooleanData.java
+++ b/core/src/main/java/tech/tablesaw/columns/booleans/BitSetBooleanData.java
@@ -5,7 +5,7 @@ import static tech.tablesaw.columns.booleans.BooleanColumnType.*;
 import it.unimi.dsi.fastutil.bytes.ByteArrayList;
 import it.unimi.dsi.fastutil.bytes.ByteIterator;
 import java.util.BitSet;
-import tech.tablesaw.selection.BitmapBackedSelection;
+import tech.tablesaw.selection.BitSetBackedSelection;
 import tech.tablesaw.selection.Selection;
 
 /**
@@ -211,43 +211,19 @@ public class BitSetBooleanData implements BooleanData {
   /** {@inheritDoc} */
   @Override
   public Selection isFalse() {
-    Selection results = new BitmapBackedSelection();
-    int i = 0;
-    for (byte next : this) {
-      if (next == BYTE_FALSE) {
-        results.add(i);
-      }
-      i++;
-    }
-    return results;
+    return new BitSetBackedSelection((BitSet) falseValues.clone());
   }
 
   /** {@inheritDoc} */
   @Override
   public Selection isTrue() {
-    Selection results = new BitmapBackedSelection();
-    int i = 0;
-    for (byte next : this) {
-      if (next == BYTE_TRUE) {
-        results.add(i);
-      }
-      i++;
-    }
-    return results;
+    return new BitSetBackedSelection((BitSet) trueValues.clone());
   }
 
   /** {@inheritDoc} */
   @Override
   public Selection isMissing() {
-    Selection results = new BitmapBackedSelection();
-    int i = 0;
-    for (byte next : this) {
-      if (next == BYTE_FALSE) {
-        results.add(i);
-      }
-      i++;
-    }
-    return results;
+    return new BitSetBackedSelection((BitSet) missingValues.clone());
   }
 
   @Override
diff --git a/core/src/main/java/tech/tablesaw/selection/BitSetBackedSelection.java b/core/src/main/java/tech/tablesaw/selection/BitSetBackedSelection.java
new file mode 100644
index 00000000..fd28393f
--- /dev/null
+++ b/core/src/main/java/tech/tablesaw/selection/BitSetBackedSelection.java
@@ -0,0 +1,291 @@
+/*
+ * 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.
+ */
+
+package tech.tablesaw.selection;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import it.unimi.dsi.fastutil.ints.IntIterator;
+import java.util.BitSet;
+import java.util.PrimitiveIterator;
+import java.util.Random;
+
+/** A Selection implemented using java.util.BitSet */
+public class BitSetBackedSelection implements Selection {
+
+  private static final Random random = new Random();
+  private final BitSet bitmap;
+
+  /**
+   * Returns a selection initialized from 0 to the given size, which cane be used for queries that
+   * exclude certain items, by first selecting the items to exclude, then flipping the bits.
+   *
+   * @param size The size The end point, exclusive
+   */
+  public BitSetBackedSelection(int size) {
+    this.bitmap = new BitSet(size);
+  }
+
+  /** Constructs a selection containing the elements in the given array */
+  public BitSetBackedSelection(int[] arr) {
+    this.bitmap = new BitSet(arr.length);
+    add(arr);
+  }
+
+  /** Constructs a selection containing the elements in the given bitmap */
+  public BitSetBackedSelection(BitSet bitmap) {
+    this.bitmap = bitmap;
+  }
+
+  /** Constructs an empty Selection */
+  public BitSetBackedSelection() {
+    this.bitmap = new BitSet();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public BitSetBackedSelection removeRange(long start, long end) {
+    this.bitmap.clear((int) start, (int) end);
+    return this;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public BitSetBackedSelection flip(int rangeStart, int rangeEnd) {
+    this.bitmap.flip(rangeStart, rangeEnd);
+    return this;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public BitSetBackedSelection add(int... ints) {
+    for (int i : ints) {
+      bitmap.set(i);
+    }
+    return this;
+  }
+
+  @Override
+  public String toString() {
+    return "Selection of size: " + bitmap.cardinality();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public int size() {
+    return bitmap.cardinality();
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public int[] toArray() {
+    return bitmap.stream().toArray();
+  }
+
+  private BitSet toBitmap(Selection otherSelection) {
+    if (otherSelection instanceof BitSetBackedSelection) {
+      return (BitSet) ((BitSetBackedSelection) otherSelection).bitmap.clone();
+    }
+    BitSet bits = new BitSet();
+    for (int i : otherSelection) {
+      bits.set(i);
+    }
+    return bits;
+  }
+
+  /** Intersects the receiver and {@code otherSelection}, updating the receiver */
+  @Override
+  public Selection and(Selection otherSelection) {
+    bitmap.and(toBitmap(otherSelection));
+    return this;
+  }
+
+  /** Implements the union of the receiver and {@code otherSelection}, updating the receiver */
+  @Override
+  public Selection or(Selection otherSelection) {
+    bitmap.or(toBitmap(otherSelection));
+    return this;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public Selection andNot(Selection otherSelection) {
+    bitmap.andNot(toBitmap(otherSelection));
+    return this;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public boolean isEmpty() {
+    return size() == 0;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public Selection clear() {
+    bitmap.clear();
+    return this;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public boolean contains(int i) {
+    return bitmap.get(i);
+  }
+
+  /**
+   * Adds to the current bitmap all integers in [rangeStart,rangeEnd)
+   *
+   * @param start inclusive beginning of range
+   * @param end exclusive ending of range
+   */
+  @Override
+  public Selection addRange(int start, int end) {
+    bitmap.set(start, end);
+    return this;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public int get(int indexToFind) {
+    if (indexToFind >= size())
+      throw new IndexOutOfBoundsException("The requested index is larger than the selection");
+    int currentStep = 0;
+    int currentIndex = 0;
+    while (true) {
+      int value = bitmap.nextSetBit(currentIndex);
+      if (indexToFind == currentStep) {
+        return value;
+      }
+      currentStep++;
+      currentIndex = value + 1;
+    }
+    // TODO: Check for consistency
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) return true;
+    if (o == null || getClass() != o.getClass()) return false;
+
+    BitSetBackedSelection integers = (BitSetBackedSelection) o;
+
+    return bitmap.equals(integers.bitmap);
+  }
+
+  @Override
+  public int hashCode() {
+    return bitmap.hashCode();
+  }
+
+  /** Returns a fastUtil intIterator that wraps a bitmap intIterator */
+  @Override
+  public IntIterator iterator() {
+
+    return new IntIterator() {
+
+      private final PrimitiveIterator.OfInt iterator = bitmap.stream().iterator();
+
+      @Override
+      public int nextInt() {
+        return iterator.next();
+      }
+
+      @Override
+      public int skip(int k) {
+        throw new UnsupportedOperationException("Views do not support skipping in the iterator");
+      }
+
+      @Override
+      public boolean hasNext() {
+        return iterator.hasNext();
+      }
+    };
+  }
+
+  /** Returns a Selection containing all indexes in the array */
+  public static BitSetBackedSelection with(int... rows) {
+    BitSetBackedSelection selection = new BitSetBackedSelection();
+    for (int i : rows) {
+      selection.add(i);
+    }
+    return selection;
+  }
+
+  /**
+   * Returns a Selection containing all indexes in the range start (inclusive) to end (exclusive),
+   */
+  public static BitSetBackedSelection withRange(int start, int end) {
+    BitSetBackedSelection selection = new BitSetBackedSelection();
+    selection.addRange(start, end);
+    return selection;
+  }
+
+  /**
+   * Returns a Selection containing all values from totalRangeStart to totalRangeEnd, except for
+   * those in the range from excludedRangeStart to excludedRangeEnd. Start values are inclusive, end
+   * values exclusive.
+   */
+  protected static Selection withoutRange(
+      int totalRangeStart, int totalRangeEnd, int excludedRangeStart, int excludedRangeEnd) {
+    Preconditions.checkArgument(excludedRangeStart >= totalRangeStart);
+    Preconditions.checkArgument(excludedRangeEnd <= totalRangeEnd);
+    Preconditions.checkArgument(totalRangeEnd >= totalRangeStart);
+    Preconditions.checkArgument(excludedRangeEnd >= excludedRangeStart);
+    Selection selection = BitSetBackedSelection.withRange(totalRangeStart, totalRangeEnd);
+    Selection exclusion = BitSetBackedSelection.withRange(excludedRangeStart, excludedRangeEnd);
+    selection.andNot(exclusion);
+    return selection;
+  }
+
+  /** Returns an randomly generated selection of size N where Max is the largest possible value */
+  protected static BitSetBackedSelection selectNRowsAtRandom(int n, int max) {
+    BitSetBackedSelection selection = new BitSetBackedSelection();
+    if (n > max) {
+      throw new IllegalArgumentException(
+          "Illegal arguments: N (" + n + ") greater than Max (" + max + ")");
+    }
+
+    int[] rows = new int[n];
+    if (n == max) {
+      for (int k = 0; k < n; ++k) {
+        selection.add(k);
+      }
+      return selection;
+    }
+
+    BitSet bs = new BitSet(max);
+    int cardinality = 0;
+    while (cardinality < n) {
+      int v = random.nextInt(max);
+      if (!bs.get(v)) {
+        bs.set(v);
+        cardinality++;
+      }
+    }
+    int pos = 0;
+    for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
+      rows[pos++] = i;
+    }
+    for (int row : rows) {
+      selection.add(row);
+    }
+    return selection;
+  }
+
+  @VisibleForTesting
+  BitSet bitSet() {
+    return bitmap;
+  }
+}


Test patch:
diff --git a/core/src/test/java/tech/tablesaw/selection/BitSetSelectionTest.java b/core/src/test/java/tech/tablesaw/selection/BitSetSelectionTest.java
new file mode 100644
index 00000000..48df809f
--- /dev/null
+++ b/core/src/test/java/tech/tablesaw/selection/BitSetSelectionTest.java
@@ -0,0 +1,217 @@
+package tech.tablesaw.selection;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import it.unimi.dsi.fastutil.ints.IntIterator;
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.List;
+import org.junit.jupiter.api.Test;
+
+class BitSetSelectionTest {
+
+  @Test
+  void with() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    assertTrue(selection.contains(42));
+    assertTrue(selection.contains(53));
+    assertTrue(selection.contains(111));
+    assertFalse(selection.contains(43));
+    assertFalse(selection.contains(0));
+    assertFalse(selection.contains(122));
+  }
+
+  @Test
+  void withoutRange() {
+    Selection selection = BitSetBackedSelection.withoutRange(0, 130, 42, 53);
+    assertFalse(selection.contains(42));
+    assertFalse(selection.contains(43));
+    assertFalse(selection.contains(52));
+    assertTrue(selection.contains(53));
+    assertTrue(selection.contains(111));
+    assertTrue(selection.contains(0));
+    assertTrue(selection.contains(122));
+  }
+
+  @Test
+  void withRange() {
+    Selection selection = BitSetBackedSelection.withRange(42, 53);
+    assertTrue(selection.contains(42));
+    assertTrue(selection.contains(43));
+    assertTrue(selection.contains(52));
+    assertFalse(selection.contains(53));
+    assertFalse(selection.contains(111));
+    assertFalse(selection.contains(0));
+    assertFalse(selection.contains(122));
+  }
+
+  @Test
+  void toArray() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    int[] expected = {42, 53, 111};
+    assertArrayEquals(expected, selection.toArray());
+  }
+
+  @Test
+  void add() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    assertTrue(selection.contains(42));
+    assertFalse(selection.contains(43));
+    assertTrue(selection.add(43).contains(43));
+  }
+
+  @Test
+  void addRange() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    assertTrue(selection.contains(42));
+    assertFalse(selection.contains(43));
+    assertTrue(selection.addRange(70, 80).contains(73));
+    assertTrue(selection.addRange(70, 80).contains(70));
+    assertTrue(selection.addRange(70, 80).contains(79));
+    assertFalse(selection.addRange(70, 80).contains(80));
+  }
+
+  @Test
+  void size() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    assertEquals(3, selection.size());
+  }
+
+  @Test
+  void and() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    Selection selection2 = BitSetBackedSelection.with(11, 133, 53, 112);
+    Selection selection3 = selection.and(selection2);
+    assertEquals(1, selection3.size());
+    assertEquals(53, selection3.get(0));
+  }
+
+  @Test
+  void or() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    Selection selection2 = BitSetBackedSelection.with(11, 133, 53, 112);
+    Selection selection3 = selection.or(selection2);
+    assertEquals(6, selection3.size());
+    assertEquals(11, selection3.get(0));
+    assertEquals(42, selection3.get(1));
+    assertTrue(selection3.contains(53));
+  }
+
+  @Test
+  void andNot() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    Selection selection2 = BitSetBackedSelection.with(11, 133, 53, 112);
+    Selection selection3 = selection.andNot(selection2);
+    assertEquals(2, selection3.size());
+    assertEquals(111, selection3.get(1));
+    assertEquals(42, selection3.get(0));
+    assertFalse(selection3.contains(53));
+  }
+
+  @Test
+  void isEmpty() {
+    Selection selection = BitSetBackedSelection.with();
+    assertTrue(selection.isEmpty());
+
+    Selection selection1 = BitSetBackedSelection.with(42, 53, 111);
+    assertFalse(selection1.isEmpty());
+  }
+
+  @Test
+  void clear() {
+    Selection selection1 = BitSetBackedSelection.with(42, 53, 111);
+    assertFalse(selection1.isEmpty());
+
+    selection1.clear();
+    assertTrue(selection1.isEmpty());
+  }
+
+  @Test
+  void get() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    assertEquals(42, selection.get(0));
+    assertEquals(53, selection.get(1));
+  }
+
+  @Test
+  void remove() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    assertTrue(selection.contains(53));
+
+    selection = selection.removeRange(50, 69);
+    assertFalse(selection.contains(53));
+    assertTrue(selection.contains(111));
+  }
+
+  @Test
+  void flip() {
+    Selection selection = BitSetBackedSelection.with(42, 53, 111);
+    assertTrue(selection.contains(53));
+    assertTrue(selection.contains(42));
+    assertTrue(selection.contains(111));
+
+    selection = selection.flip(0, 124);
+    assertFalse(selection.contains(53));
+    assertFalse(selection.contains(42));
+    assertFalse(selection.contains(111));
+    assertTrue(selection.contains(0));
+    assertTrue(selection.contains(110));
+    assertTrue(selection.contains(112));
+  }
+
+  @Test
+  void testConstructor1() {
+    BitSetBackedSelection selection = new BitSetBackedSelection(10);
+    assertEquals(-1, selection.bitSet().nextSetBit(0));
+  }
+
+  @Test
+  void testConstructor2() {
+    int[] values = {4, 11, 19};
+    BitSetBackedSelection selection = new BitSetBackedSelection(values);
+    assertEquals(4, selection.bitSet().nextSetBit(0));
+    assertEquals(11, selection.bitSet().nextSetBit(5));
+    assertEquals(19, selection.bitSet().nextSetBit(12));
+  }
+
+  @Test
+  void testConstructor3() {
+    BitSet bitSet = new BitSet(3);
+    bitSet.set(2);
+    BitSetBackedSelection selection = new BitSetBackedSelection(bitSet);
+    assertEquals(2, selection.bitSet().nextSetBit(0));
+  }
+
+  @Test
+  void testToString() {
+    int[] values = {4, 11, 19};
+    BitSetBackedSelection selection = new BitSetBackedSelection(values);
+    assertEquals("Selection of size: 3", selection.toString());
+  }
+
+  @Test
+  void testEquals() {
+    int[] values = {4, 11, 19};
+    BitSetBackedSelection selection1 = new BitSetBackedSelection(values);
+    BitSetBackedSelection selection2 = new BitSetBackedSelection(values.clone());
+    assertEquals(selection1, selection2);
+    assertEquals(selection1.hashCode(), selection2.hashCode());
+  }
+
+  @Test
+  void selectNRandomRows() {
+    BitSetBackedSelection random = BitSetBackedSelection.selectNRowsAtRandom(4, 40);
+    assertEquals(4, random.size());
+  }
+
+  @Test
+  void iterator() {
+    BitSetBackedSelection random = BitSetBackedSelection.selectNRowsAtRandom(4, 40);
+    List<Integer> elements = new ArrayList<>();
+    IntIterator it = random.iterator();
+    while (it.hasNext()) {
+      elements.add(it.nextInt());
+    }
+    assertEquals(4, elements.size());
+  }
+}