@Test public void testSelect() { long w = ~0l; for (int k = 0; k < 64; ++k) { assertEquals(k, Util.select(w, k)); } for (int k = 0; k < 64; ++k) { assertEquals(k, Util.select(1l << k, 0)); } for (int k = 1; k < 64; ++k) { assertEquals(k, Util.select((1l << k) + 1, 1)); } assertEquals(0, Util.select(1, 0)); assertEquals(0, Util.select(5, 0)); assertEquals(2, Util.select(5, 1)); for (int gap = 1; gap <= 1024; gap *= 2) { RoaringBitmap rb = new RoaringBitmap(); for (int k = 0; k < 100000; k += gap) { rb.add(k); } for (int k = 0; k < 100000 / gap; ++k) { assertEquals(k * gap, rb.select(k)); } } }
@Override public int select(int j) { long leftover = Util.toUnsignedLong(j); for (int i = 0; i < this.highLowContainer.size(); i++) { Container c = this.highLowContainer.getContainerAtIndex(i); int thiscard = c.getCardinality(); if (thiscard > leftover) { int keycontrib = this.highLowContainer.getKeyAtIndex(i) << 16; int lowcontrib = (c.select((int)leftover)); return lowcontrib + keycontrib; } leftover -= thiscard; } throw new IllegalArgumentException("You are trying to select the " + j + "th value when the cardinality is " + this.getCardinality() + "."); }
RoaringBitmap implements Cloneable, Serializable, Iterable<Integer>, Externalizable,
    ImmutableBitmapDataProvider, BitmapDataProvider, AppendableStorage<Container> { @Override public int select(int j) { long leftover = Util.toUnsignedLong(j); for (int i = 0; i < this.highLowContainer.size(); i++) { Container c = this.highLowContainer.getContainerAtIndex(i); int thiscard = c.getCardinality(); if (thiscard > leftover) { int keycontrib = this.highLowContainer.getKeyAtIndex(i) << 16; int lowcontrib = (c.select((int)leftover)); return lowcontrib + keycontrib; } leftover -= thiscard; } throw new IllegalArgumentException("You are trying to select the " + j + "th value when the cardinality is " + this.getCardinality() + "."); } }
RoaringBitmap implements Cloneable, Serializable, Iterable<Integer>, Externalizable,
    ImmutableBitmapDataProvider, BitmapDataProvider, AppendableStorage<Container> { @Override public int select(int j) { long leftover = Util.toUnsignedLong(j); for (int i = 0; i < this.highLowContainer.size(); i++) { Container c = this.highLowContainer.getContainerAtIndex(i); int thiscard = c.getCardinality(); if (thiscard > leftover) { int keycontrib = this.highLowContainer.getKeyAtIndex(i) << 16; int lowcontrib = (c.select((int)leftover)); return lowcontrib + keycontrib; } leftover -= thiscard; } throw new IllegalArgumentException("You are trying to select the " + j + "th value when the cardinality is " + this.getCardinality() + "."); } RoaringBitmap();   RoaringBitmap(RoaringArray highLowContainer);  RoaringBitmap(ImmutableRoaringBitmap rb); }
RoaringBitmap implements Cloneable, Serializable, Iterable<Integer>, Externalizable,
    ImmutableBitmapDataProvider, BitmapDataProvider, AppendableStorage<Container> { @Override public int select(int j) { long leftover = Util.toUnsignedLong(j); for (int i = 0; i < this.highLowContainer.size(); i++) { Container c = this.highLowContainer.getContainerAtIndex(i); int thiscard = c.getCardinality(); if (thiscard > leftover) { int keycontrib = this.highLowContainer.getKeyAtIndex(i) << 16; int lowcontrib = (c.select((int)leftover)); return lowcontrib + keycontrib; } leftover -= thiscard; } throw new IllegalArgumentException("You are trying to select the " + j + "th value when the cardinality is " + this.getCardinality() + "."); } RoaringBitmap();   RoaringBitmap(RoaringArray highLowContainer);  RoaringBitmap(ImmutableRoaringBitmap rb); static RoaringBitmap addOffset(final RoaringBitmap x, long offset); static RoaringBitmap add(RoaringBitmap rb, final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap add(RoaringBitmap rb, final int rangeStart, final int rangeEnd); static RoaringBitmap and(final RoaringBitmap x1, final RoaringBitmap x2); static int andCardinality(final RoaringBitmap x1, final RoaringBitmap x2); static RoaringBitmap andNot(final RoaringBitmap x1, final RoaringBitmap x2); void add(final int... dat); void addN(final int[] dat, final int offset, final int n); static RoaringBitmap bitmapOf(final int... dat); static RoaringBitmap bitmapOfUnordered(final int... data); static RoaringBitmap flip(RoaringBitmap bm, final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap flip(RoaringBitmap rb, final int rangeStart, final int rangeEnd); static boolean intersects(final RoaringBitmap x1, final RoaringBitmap x2); static RoaringBitmap or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap or(RoaringBitmap... bitmaps); static RoaringBitmap or(final RoaringBitmap x1, final RoaringBitmap x2); static int orCardinality(final RoaringBitmap x1, final RoaringBitmap x2); static int xorCardinality(final RoaringBitmap x1, final RoaringBitmap x2); static int andNotCardinality(final RoaringBitmap x1, final RoaringBitmap x2); static RoaringBitmap remove(RoaringBitmap rb, final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap remove(RoaringBitmap rb, final int rangeStart, final int rangeEnd); static RoaringBitmap xor(final RoaringBitmap x1, final RoaringBitmap x2); @Override void add(final int x); void add(final long rangeStart, final long rangeEnd); @Deprecated void add(final int rangeStart, final int rangeEnd); boolean intersects(long minimum, long supremum); void and(final RoaringBitmap x2); static RoaringBitmap and(final Iterator<? extends RoaringBitmap> bitmaps,
      final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap and(final Iterator<? extends RoaringBitmap> bitmaps,
      final int rangeStart, final int rangeEnd); void andNot(final RoaringBitmap x2); static RoaringBitmap andNot(final RoaringBitmap x1, final RoaringBitmap x2,
      long rangeStart, long rangeEnd); @Deprecated static RoaringBitmap andNot(final RoaringBitmap x1, final RoaringBitmap x2,
          final int rangeStart, final int rangeEnd); void orNot(final RoaringBitmap other, long rangeEnd); static RoaringBitmap orNot(
          final RoaringBitmap x1, final RoaringBitmap x2, long rangeEnd); boolean checkedAdd(final int x); boolean checkedRemove(final int x); void clear(); @Override RoaringBitmap clone(); @Override boolean contains(final int x); boolean contains(long minimum, long supremum); void deserialize(DataInput in, byte[] buffer); void deserialize(DataInput in); void deserialize(ByteBuffer bbf); @Override boolean equals(Object o); boolean isHammingSimilar(RoaringBitmap other, int tolerance); void flip(final int x); void flip(final long rangeStart, final long rangeEnd); @Deprecated void flip(final int rangeStart, final int rangeEnd); @Override long getLongCardinality(); @Override int getCardinality(); @Override void forEach(IntConsumer ic); ContainerPointer getContainerPointer(); @Override PeekableIntIterator getIntIterator(); @Override IntIterator getReverseIntIterator(); @Override RoaringBatchIterator getBatchIterator(); @Override long getLongSizeInBytes(); @Override int getSizeInBytes(); @Override int hashCode(); boolean hasRunCompression(); @Override boolean isEmpty(); @Override Iterator<Integer> iterator(); @Override RoaringBitmap limit(int maxcardinality); void or(final RoaringBitmap x2); static RoaringBitmap or(final Iterator<? extends RoaringBitmap> bitmaps,
      final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap or(final Iterator<? extends RoaringBitmap> bitmaps,
          final int rangeStart, final int rangeEnd); @Override long rankLong(int x); @Override long rangeCardinality(long start, long end); @Override int rank(int x); @Override void readExternal(ObjectInput in); @Override void remove(final int x); void remove(final long rangeStart, final long rangeEnd); @Deprecated void remove(final int rangeStart, final int rangeEnd); boolean removeRunCompression(); boolean runOptimize(); boolean contains(RoaringBitmap subset); @Override int select(int j); @Override long nextValue(int fromValue); @Override long previousValue(int fromValue); @Override long nextAbsentValue(int fromValue); @Override long previousAbsentValue(int fromValue); @Override int first(); @Override int last(); @Override void serialize(DataOutput out); @Override void serialize(ByteBuffer buffer); static long maximumSerializedSize(long cardinality, long universe_size); @Override int serializedSizeInBytes(); @Override int[] toArray(); @Override void append(char key, Container container); MutableRoaringBitmap toMutableRoaringBitmap(); @Override String toString(); @Override void trim(); @Override void writeExternal(ObjectOutput out); void xor(final RoaringBitmap x2); static RoaringBitmap xor(final Iterator<? extends RoaringBitmap> bitmaps,
      final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap xor(final Iterator<? extends RoaringBitmap> bitmaps,
          final int rangeStart, final int rangeEnd); }
RoaringBitmap implements Cloneable, Serializable, Iterable<Integer>, Externalizable,
    ImmutableBitmapDataProvider, BitmapDataProvider, AppendableStorage<Container> { @Override public int select(int j) { long leftover = Util.toUnsignedLong(j); for (int i = 0; i < this.highLowContainer.size(); i++) { Container c = this.highLowContainer.getContainerAtIndex(i); int thiscard = c.getCardinality(); if (thiscard > leftover) { int keycontrib = this.highLowContainer.getKeyAtIndex(i) << 16; int lowcontrib = (c.select((int)leftover)); return lowcontrib + keycontrib; } leftover -= thiscard; } throw new IllegalArgumentException("You are trying to select the " + j + "th value when the cardinality is " + this.getCardinality() + "."); } RoaringBitmap();   RoaringBitmap(RoaringArray highLowContainer);  RoaringBitmap(ImmutableRoaringBitmap rb); static RoaringBitmap addOffset(final RoaringBitmap x, long offset); static RoaringBitmap add(RoaringBitmap rb, final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap add(RoaringBitmap rb, final int rangeStart, final int rangeEnd); static RoaringBitmap and(final RoaringBitmap x1, final RoaringBitmap x2); static int andCardinality(final RoaringBitmap x1, final RoaringBitmap x2); static RoaringBitmap andNot(final RoaringBitmap x1, final RoaringBitmap x2); void add(final int... dat); void addN(final int[] dat, final int offset, final int n); static RoaringBitmap bitmapOf(final int... dat); static RoaringBitmap bitmapOfUnordered(final int... data); static RoaringBitmap flip(RoaringBitmap bm, final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap flip(RoaringBitmap rb, final int rangeStart, final int rangeEnd); static boolean intersects(final RoaringBitmap x1, final RoaringBitmap x2); static RoaringBitmap or(Iterator<? extends RoaringBitmap> bitmaps); static RoaringBitmap or(RoaringBitmap... bitmaps); static RoaringBitmap or(final RoaringBitmap x1, final RoaringBitmap x2); static int orCardinality(final RoaringBitmap x1, final RoaringBitmap x2); static int xorCardinality(final RoaringBitmap x1, final RoaringBitmap x2); static int andNotCardinality(final RoaringBitmap x1, final RoaringBitmap x2); static RoaringBitmap remove(RoaringBitmap rb, final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap remove(RoaringBitmap rb, final int rangeStart, final int rangeEnd); static RoaringBitmap xor(final RoaringBitmap x1, final RoaringBitmap x2); @Override void add(final int x); void add(final long rangeStart, final long rangeEnd); @Deprecated void add(final int rangeStart, final int rangeEnd); boolean intersects(long minimum, long supremum); void and(final RoaringBitmap x2); static RoaringBitmap and(final Iterator<? extends RoaringBitmap> bitmaps,
      final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap and(final Iterator<? extends RoaringBitmap> bitmaps,
      final int rangeStart, final int rangeEnd); void andNot(final RoaringBitmap x2); static RoaringBitmap andNot(final RoaringBitmap x1, final RoaringBitmap x2,
      long rangeStart, long rangeEnd); @Deprecated static RoaringBitmap andNot(final RoaringBitmap x1, final RoaringBitmap x2,
          final int rangeStart, final int rangeEnd); void orNot(final RoaringBitmap other, long rangeEnd); static RoaringBitmap orNot(
          final RoaringBitmap x1, final RoaringBitmap x2, long rangeEnd); boolean checkedAdd(final int x); boolean checkedRemove(final int x); void clear(); @Override RoaringBitmap clone(); @Override boolean contains(final int x); boolean contains(long minimum, long supremum); void deserialize(DataInput in, byte[] buffer); void deserialize(DataInput in); void deserialize(ByteBuffer bbf); @Override boolean equals(Object o); boolean isHammingSimilar(RoaringBitmap other, int tolerance); void flip(final int x); void flip(final long rangeStart, final long rangeEnd); @Deprecated void flip(final int rangeStart, final int rangeEnd); @Override long getLongCardinality(); @Override int getCardinality(); @Override void forEach(IntConsumer ic); ContainerPointer getContainerPointer(); @Override PeekableIntIterator getIntIterator(); @Override IntIterator getReverseIntIterator(); @Override RoaringBatchIterator getBatchIterator(); @Override long getLongSizeInBytes(); @Override int getSizeInBytes(); @Override int hashCode(); boolean hasRunCompression(); @Override boolean isEmpty(); @Override Iterator<Integer> iterator(); @Override RoaringBitmap limit(int maxcardinality); void or(final RoaringBitmap x2); static RoaringBitmap or(final Iterator<? extends RoaringBitmap> bitmaps,
      final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap or(final Iterator<? extends RoaringBitmap> bitmaps,
          final int rangeStart, final int rangeEnd); @Override long rankLong(int x); @Override long rangeCardinality(long start, long end); @Override int rank(int x); @Override void readExternal(ObjectInput in); @Override void remove(final int x); void remove(final long rangeStart, final long rangeEnd); @Deprecated void remove(final int rangeStart, final int rangeEnd); boolean removeRunCompression(); boolean runOptimize(); boolean contains(RoaringBitmap subset); @Override int select(int j); @Override long nextValue(int fromValue); @Override long previousValue(int fromValue); @Override long nextAbsentValue(int fromValue); @Override long previousAbsentValue(int fromValue); @Override int first(); @Override int last(); @Override void serialize(DataOutput out); @Override void serialize(ByteBuffer buffer); static long maximumSerializedSize(long cardinality, long universe_size); @Override int serializedSizeInBytes(); @Override int[] toArray(); @Override void append(char key, Container container); MutableRoaringBitmap toMutableRoaringBitmap(); @Override String toString(); @Override void trim(); @Override void writeExternal(ObjectOutput out); void xor(final RoaringBitmap x2); static RoaringBitmap xor(final Iterator<? extends RoaringBitmap> bitmaps,
      final long rangeStart, final long rangeEnd); @Deprecated static RoaringBitmap xor(final Iterator<? extends RoaringBitmap> bitmaps,
          final int rangeStart, final int rangeEnd);  }