@Test public void testRangeCardinality() { RoaringBitmap r = new RoaringBitmap(); long Min = 0L; long Max = 1000000L; r.add(Min, Max); for (long s = Min; s <= Max; s += 100) { for (long e = s; e <= Max; e += 100) { assertEquals(e - s, r.rangeCardinality(s, e)); } } }
@Override public long rangeCardinality(long start, long end) { if(Long.compareUnsigned(start, end) >= 0) { return 0; } long size = 0; int startIndex = this.highLowContainer.getIndex(Util.highbits(start)); if(startIndex < 0) { startIndex = -startIndex - 1; } else { int inContainerStart = (Util.lowbits(start)); if(inContainerStart != 0) { size -= this.highLowContainer .getContainerAtIndex(startIndex) .rank((char)(inContainerStart - 1)); } } char xhigh = Util.highbits(end - 1); for (int i = startIndex; i < this.highLowContainer.size(); i++) { char key = this.highLowContainer.getKeyAtIndex(i); if (key < xhigh) { size += this.highLowContainer.getContainerAtIndex(i).getCardinality(); } else if (key == xhigh) { return size + this.highLowContainer .getContainerAtIndex(i).rank(Util.lowbits((int)(end - 1))); } } return size; }
RoaringBitmap implements Cloneable, Serializable, Iterable<Integer>, Externalizable,
    ImmutableBitmapDataProvider, BitmapDataProvider, AppendableStorage<Container> { @Override public long rangeCardinality(long start, long end) { if(Long.compareUnsigned(start, end) >= 0) { return 0; } long size = 0; int startIndex = this.highLowContainer.getIndex(Util.highbits(start)); if(startIndex < 0) { startIndex = -startIndex - 1; } else { int inContainerStart = (Util.lowbits(start)); if(inContainerStart != 0) { size -= this.highLowContainer .getContainerAtIndex(startIndex) .rank((char)(inContainerStart - 1)); } } char xhigh = Util.highbits(end - 1); for (int i = startIndex; i < this.highLowContainer.size(); i++) { char key = this.highLowContainer.getKeyAtIndex(i); if (key < xhigh) { size += this.highLowContainer.getContainerAtIndex(i).getCardinality(); } else if (key == xhigh) { return size + this.highLowContainer .getContainerAtIndex(i).rank(Util.lowbits((int)(end - 1))); } } return size; } }
RoaringBitmap implements Cloneable, Serializable, Iterable<Integer>, Externalizable,
    ImmutableBitmapDataProvider, BitmapDataProvider, AppendableStorage<Container> { @Override public long rangeCardinality(long start, long end) { if(Long.compareUnsigned(start, end) >= 0) { return 0; } long size = 0; int startIndex = this.highLowContainer.getIndex(Util.highbits(start)); if(startIndex < 0) { startIndex = -startIndex - 1; } else { int inContainerStart = (Util.lowbits(start)); if(inContainerStart != 0) { size -= this.highLowContainer .getContainerAtIndex(startIndex) .rank((char)(inContainerStart - 1)); } } char xhigh = Util.highbits(end - 1); for (int i = startIndex; i < this.highLowContainer.size(); i++) { char key = this.highLowContainer.getKeyAtIndex(i); if (key < xhigh) { size += this.highLowContainer.getContainerAtIndex(i).getCardinality(); } else if (key == xhigh) { return size + this.highLowContainer .getContainerAtIndex(i).rank(Util.lowbits((int)(end - 1))); } } return size; } RoaringBitmap();   RoaringBitmap(RoaringArray highLowContainer);  RoaringBitmap(ImmutableRoaringBitmap rb); }
RoaringBitmap implements Cloneable, Serializable, Iterable<Integer>, Externalizable,
    ImmutableBitmapDataProvider, BitmapDataProvider, AppendableStorage<Container> { @Override public long rangeCardinality(long start, long end) { if(Long.compareUnsigned(start, end) >= 0) { return 0; } long size = 0; int startIndex = this.highLowContainer.getIndex(Util.highbits(start)); if(startIndex < 0) { startIndex = -startIndex - 1; } else { int inContainerStart = (Util.lowbits(start)); if(inContainerStart != 0) { size -= this.highLowContainer .getContainerAtIndex(startIndex) .rank((char)(inContainerStart - 1)); } } char xhigh = Util.highbits(end - 1); for (int i = startIndex; i < this.highLowContainer.size(); i++) { char key = this.highLowContainer.getKeyAtIndex(i); if (key < xhigh) { size += this.highLowContainer.getContainerAtIndex(i).getCardinality(); } else if (key == xhigh) { return size + this.highLowContainer .getContainerAtIndex(i).rank(Util.lowbits((int)(end - 1))); } } return size; } 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 long rangeCardinality(long start, long end) { if(Long.compareUnsigned(start, end) >= 0) { return 0; } long size = 0; int startIndex = this.highLowContainer.getIndex(Util.highbits(start)); if(startIndex < 0) { startIndex = -startIndex - 1; } else { int inContainerStart = (Util.lowbits(start)); if(inContainerStart != 0) { size -= this.highLowContainer .getContainerAtIndex(startIndex) .rank((char)(inContainerStart - 1)); } } char xhigh = Util.highbits(end - 1); for (int i = startIndex; i < this.highLowContainer.size(); i++) { char key = this.highLowContainer.getKeyAtIndex(i); if (key < xhigh) { size += this.highLowContainer.getContainerAtIndex(i).getCardinality(); } else if (key == xhigh) { return size + this.highLowContainer .getContainerAtIndex(i).rank(Util.lowbits((int)(end - 1))); } } return size; } 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);  }