Class Roaring64NavigableMap

java.lang.Object
org.roaringbitmap.longlong.Roaring64NavigableMap
All Implemented Interfaces:
Externalizable, Serializable, ImmutableLongBitmapDataProvider, LongBitmapDataProvider

public class Roaring64NavigableMap extends Object implements Externalizable, LongBitmapDataProvider
Roaring64NavigableMap extends RoaringBitmap to the whole range of longs (or unsigned longs). It enables a greater cardinality, up to 2*Long.MAX_VALUE-1 Longs are added by default in unsigned sorted order (i.e. -1L is the greatest long to be added while 0 has no previous value). It can be configured to signed sorted order (in which case, 0 is preceded by -1). That is, they are treated as unsigned integers (see Java 8's Integer.toUnsignedLong function). Up to 4294967296 integers can be stored.
See Also:
  • Field Details

    • SERIALIZATION_MODE_LEGACY

      public static final int SERIALIZATION_MODE_LEGACY
      See Also:
    • SERIALIZATION_MODE_PORTABLE

      public static final int SERIALIZATION_MODE_PORTABLE
      See Also:
    • SERIALIZATION_MODE

      public static int SERIALIZATION_MODE
    • highToBitmap

      private NavigableMap<Integer,BitmapDataProvider> highToBitmap
    • signedLongs

      private boolean signedLongs
    • supplier

      private transient BitmapDataProviderSupplier supplier
    • doCacheCardinalities

      private transient boolean doCacheCardinalities
    • firstHighNotValid

      private transient int firstHighNotValid
    • allValid

      private transient boolean allValid
    • sortedCumulatedCardinality

      private transient long[] sortedCumulatedCardinality
    • sortedHighs

      private transient int[] sortedHighs
    • latestAddedHigh

      private transient Map.Entry<Integer,BitmapDataProvider> latestAddedHigh
    • DEFAULT_ORDER_IS_SIGNED

      private static final boolean DEFAULT_ORDER_IS_SIGNED
      See Also:
    • DEFAULT_CARDINALITIES_ARE_CACHED

      private static final boolean DEFAULT_CARDINALITIES_ARE_CACHED
      See Also:
  • Constructor Details

    • Roaring64NavigableMap

      public Roaring64NavigableMap()
      By default, we consider longs are unsigned longs: normal longs: 0 is the lowest possible long. Long.MAX_VALUE is followed by Long.MIN_VALUE. -1L is the highest possible value
    • Roaring64NavigableMap

      public Roaring64NavigableMap(boolean signedLongs)
      By default, use RoaringBitmap as underlyings BitmapDataProvider
      Parameters:
      signedLongs - true if longs has to be ordered as plain java longs. False to handle them as unsigned 64bits long (as RoaringBitmap with unsigned integers)
    • Roaring64NavigableMap

      public Roaring64NavigableMap(boolean signedLongs, boolean cacheCardinalities)
      By default, use RoaringBitmap as underlyings BitmapDataProvider
      Parameters:
      signedLongs - true if longs has to be ordered as plain java longs. False to handle them as unsigned 64bits long (as RoaringBitmap with unsigned integers)
      cacheCardinalities - true if cardinalities have to be cached. It will prevent many iteration along the NavigableMap
    • Roaring64NavigableMap

      public Roaring64NavigableMap(BitmapDataProviderSupplier supplier)
      By default, longs are managed as unsigned longs and cardinalities are cached.
      Parameters:
      supplier - provide the logic to instantiate new BitmapDataProvider, typically instantiated once per high.
    • Roaring64NavigableMap

      public Roaring64NavigableMap(boolean signedLongs, BitmapDataProviderSupplier supplier)
      By default, we activating cardinalities caching.
      Parameters:
      signedLongs - true if longs has to be ordered as plain java longs. False to handle them as unsigned 64bits long (as RoaringBitmap with unsigned integers)
      supplier - provide the logic to instantiate new BitmapDataProvider, typically instantiated once per high.
    • Roaring64NavigableMap

      public Roaring64NavigableMap(boolean signedLongs, boolean cacheCardinalities, BitmapDataProviderSupplier supplier)
      Parameters:
      signedLongs - true if longs has to be ordered as plain java longs. False to handle them as unsigned 64bits long (as RoaringBitmap with unsigned integers)
      cacheCardinalities - true if cardinalities have to be cached. It will prevent many iteration along the NavigableMap
      supplier - provide the logic to instantiate new BitmapDataProvider, typically instantiated once per high.
  • Method Details

    • resetPerfHelpers

      private void resetPerfHelpers()
    • getHighToBitmap

    • getLowestInvalidHigh

      int getLowestInvalidHigh()
    • getSortedCumulatedCardinality

      long[] getSortedCumulatedCardinality()
    • getClassName

      private static String getClassName(BitmapDataProvider bitmap)
    • addLong

      public void addLong(long x)
      Add the value to the container (set the value to "true"), whether it already appears or not. Java lacks native unsigned longs but the x argument is considered to be unsigned. Within bitmaps, numbers are ordered according toLong.compareUnsigned(long, long). We order the numbers like 0, 1, ..., 9223372036854775807, -9223372036854775808, -9223372036854775807,..., -1.
      Specified by:
      addLong in interface LongBitmapDataProvider
      Parameters:
      x - long value
    • addInt

      public void addInt(int x)
      Add the integer value to the container (set the value to "true"), whether it already appears or not. Javac lacks native unsigned integers but the x argument is considered to be unsigned. Within bitmaps, numbers are ordered according toInteger.compareUnsigned(int, int). We order the numbers like 0, 1, ..., 2147483647, -2147483648, -2147483647,..., -1.
      Parameters:
      x - integer value
    • newRoaringBitmap

      private BitmapDataProvider newRoaringBitmap()
    • invalidateAboveHigh

      private void invalidateAboveHigh(int high)
    • compare

      private int compare(int x, int y)
    • pushBitmapForHigh

      private void pushBitmapForHigh(int high, BitmapDataProvider bitmap)
    • low

      private int low(long id)
    • high

      private int high(long id)
    • getLongCardinality

      public long getLongCardinality()
      Returns the number of distinct integers added to the bitmap (e.g., number of bits set).
      Specified by:
      getLongCardinality in interface ImmutableLongBitmapDataProvider
      Returns:
      the cardinality
    • getIntCardinality

      public int getIntCardinality() throws UnsupportedOperationException
      Returns:
      the cardinality as an int
      Throws:
      UnsupportedOperationException - if the cardinality does not fit in an int
    • select

      public long select(long j) throws IllegalArgumentException
      Return the jth value stored in this bitmap.
      Specified by:
      select in interface ImmutableLongBitmapDataProvider
      Parameters:
      j - index of the value
      Returns:
      the value
      Throws:
      IllegalArgumentException - if j is out of the bounds of the bitmap cardinality
    • selectNoCache

      private long selectNoCache(long j)
    • throwSelectInvalidIndex

      private long throwSelectInvalidIndex(long j)
    • iterator

      public Iterator<Long> iterator()
      For better performance, consider the Use the forEach method.
      Returns:
      a custom iterator over set bits, the bits are traversed in ascending sorted order
    • forEach

      public void forEach(LongConsumer lc)
      Description copied from interface: ImmutableLongBitmapDataProvider
      Visit all values in the bitmap and pass them to the consumer. * Usage:
       
        bitmap.forEach(new LongConsumer() {
      
          {@literal @}Override
          public void accept(long value) {
            // do something here
            
          }});
         
       }
       
      Specified by:
      forEach in interface ImmutableLongBitmapDataProvider
      Parameters:
      lc - the consumer
    • rankLong

      public long rankLong(long id)
      Description copied from interface: ImmutableLongBitmapDataProvider
      Rank returns the number of integers that are smaller or equal to x (Rank(infinity) would be GetCardinality()). The value is a full 64-bit value.
      Specified by:
      rankLong in interface ImmutableLongBitmapDataProvider
      Parameters:
      id - upper limit
      Returns:
      the rank
    • rankLongNoCache

      private long rankLongNoCache(int high, int low)
    • ensureCumulatives

      protected int ensureCumulatives(int high)
      Parameters:
      high - for which high bucket should we compute the cardinality
      Returns:
      the highest validatedIndex
    • binarySearch

      private int binarySearch(int[] array, int key)
    • binarySearch

      private int binarySearch(int[] array, int from, int to, int key)
    • unsignedBinarySearch

      private static int unsignedBinarySearch(int[] a, int fromIndex, int toIndex, int key, Comparator<? super Integer> c)
    • ensureOne

      private void ensureOne(Map.Entry<Integer,BitmapDataProvider> e, int currentHigh, int indexOk)
    • highestHigh

      private int highestHigh()
    • naivelazyor

      public void naivelazyor(Roaring64NavigableMap x2)
      In-place bitwise OR (union) operation without maintaining cardinality. Don't forget to call repairAfterLazy() afterward. The current bitmap is modified.
      Parameters:
      x2 - other bitmap
    • or

      public void or(Roaring64NavigableMap x2)
      In-place bitwise OR (union) operation. The current bitmap is modified.
      Parameters:
      x2 - other bitmap
    • xor

      public void xor(Roaring64NavigableMap x2)
      In-place bitwise XOR (symmetric difference) operation. The current bitmap is modified.
      Parameters:
      x2 - other bitmap
    • and

      public void and(Roaring64NavigableMap x2)
      In-place bitwise AND (intersection) operation. The current bitmap is modified.
      Parameters:
      x2 - other bitmap
    • andNot

      public void andNot(Roaring64NavigableMap x2)
      In-place bitwise ANDNOT (difference) operation. The current bitmap is modified.
      Parameters:
      x2 - other bitmap
    • writeExternal

      public void writeExternal(ObjectOutput out) throws IOException
      Roaring64NavigableMap are serializable. However, contrary to RoaringBitmap, the serialization format is not well-defined: for now, it is strongly coupled with Java standard serialization. Just like the serialization may be incompatible between various Java versions, Roaring64NavigableMap are subject to incompatibilities. Moreover, even on a given Java versions, the serialization format may change from one RoaringBitmap version to another
      Specified by:
      writeExternal in interface Externalizable
      Throws:
      IOException
    • readExternal

      public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
      Specified by:
      readExternal in interface Externalizable
      Throws:
      IOException
      ClassNotFoundException
    • toString

      public String toString()
      A string describing the bitmap.
      Overrides:
      toString in class Object
      Returns:
      the string
    • getLongIterator

      public LongIterator getLongIterator()
      For better performance, consider the Use the forEach method.
      Specified by:
      getLongIterator in interface ImmutableLongBitmapDataProvider
      Returns:
      a custom iterator over set bits, the bits are traversed in ascending sorted order
    • toIterator

      protected LongIterator toIterator(Iterator<Map.Entry<Integer,BitmapDataProvider>> it, boolean reversed)
    • contains

      public boolean contains(long x)
      Description copied from interface: ImmutableLongBitmapDataProvider
      Checks whether the value in included, which is equivalent to checking if the corresponding bit is set (get in BitSet class).
      Specified by:
      contains in interface ImmutableLongBitmapDataProvider
      Parameters:
      x - long value
      Returns:
      whether the long value is included.
    • getSizeInBytes

      public int getSizeInBytes()
      Description copied from interface: ImmutableLongBitmapDataProvider
      Estimate of the memory usage of this data structure. Internally, this is computed as a 64-bit counter.
      Specified by:
      getSizeInBytes in interface ImmutableLongBitmapDataProvider
      Returns:
      estimated memory usage.
    • getLongSizeInBytes

      public long getLongSizeInBytes()
      Description copied from interface: ImmutableLongBitmapDataProvider
      Estimate of the memory usage of this data structure. Provides full 64-bit number.
      Specified by:
      getLongSizeInBytes in interface ImmutableLongBitmapDataProvider
      Returns:
      estimated memory usage.
    • isEmpty

      public boolean isEmpty()
      Description copied from interface: ImmutableLongBitmapDataProvider
      Checks whether the bitmap is empty.
      Specified by:
      isEmpty in interface ImmutableLongBitmapDataProvider
      Returns:
      true if this bitmap contains no set bit
    • limit

      public ImmutableLongBitmapDataProvider limit(long x)
      Description copied from interface: ImmutableLongBitmapDataProvider
      Create a new bitmap of the same class, containing at most maxcardinality integers.
      Specified by:
      limit in interface ImmutableLongBitmapDataProvider
      Parameters:
      x - maximal cardinality
      Returns:
      a new bitmap with cardinality no more than maxcardinality
    • repairAfterLazy

      public void repairAfterLazy()
      to be used with naivelazyor
    • runOptimize

      public boolean runOptimize()
      Use a run-length encoding where it is estimated as more space efficient
      Returns:
      whether a change was applied
    • serialize

      public void serialize(DataOutput out) throws IOException
      Serialize this bitmap. If SERIALIZATION_MODE is set to SERIALIZATION_MODE_PORTABLE, this will rely on the specification at https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations. As of 0.x, this is **not** the default behavior. Consider calling runOptimize() before serialization to improve compression. The current bitmap is not modified.
      Specified by:
      serialize in interface ImmutableLongBitmapDataProvider
      Parameters:
      out - the DataOutput stream
      Throws:
      IOException - Signals that an I/O exception has occurred.
    • serializeLegacy

      @Deprecated public void serializeLegacy(DataOutput out) throws IOException
      Deprecated.
      Serialize this bitmap. This format was introduced before converting with CRoaring portable format. It remains useful when considering signed longs. It is the default in 0.x Consider calling runOptimize() before serialization to improve compression. The current bitmap is not modified.
      Parameters:
      out - the DataOutput stream
      Throws:
      IOException - Signals that an I/O exception has occurred.
    • serializePortable

      public void serializePortable(DataOutput out) throws IOException
      Serialize this bitmap. The format is specified at https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations. It is the compatible with CRoaring (and GoRoaring). Consider calling runOptimize() before serialization to improve compression. The current bitmap is not modified.
      Parameters:
      out - the DataOutput stream
      Throws:
      IOException - Signals that an I/O exception has occurred.
    • deserialize

      public void deserialize(DataInput in) throws IOException
      Deserialize (retrieve) this bitmap. If SERIALIZATION_MODE is set to SERIALIZATION_MODE_PORTABLE, this will rely on the specification at https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations. As of 0.x, this is **not** the default behavior. The current bitmap is overwritten.
      Parameters:
      in - the DataInput stream
      Throws:
      IOException - Signals that an I/O exception has occurred.
    • deserializeLegacy

      public void deserializeLegacy(DataInput in) throws IOException
      Deserialize (retrieve) this bitmap. This format was introduced before converting with CRoaring portable format. It remains useful when considering signed longs. It is the default in 0.x The current bitmap is overwritten.
      Parameters:
      in - the DataInput stream
      Throws:
      IOException - Signals that an I/O exception has occurred.
    • deserializePortable

      public void deserializePortable(DataInput in) throws IOException
      Deserialize (retrieve) this bitmap. The format is specified at https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations. It is the compatible with CRoaring (and GoRoaring). The current bitmap is overwritten.
      Parameters:
      in - the DataInput stream
      Throws:
      IOException - Signals that an I/O exception has occurred.
    • serializedSizeInBytes

      public long serializedSizeInBytes()
      Description copied from interface: ImmutableLongBitmapDataProvider
      Report the number of bytes required to serialize this bitmap. This is the number of bytes written out when using the serialize method. When using the writeExternal method, the count will be higher due to the overhead of Java serialization.
      Specified by:
      serializedSizeInBytes in interface ImmutableLongBitmapDataProvider
      Returns:
      the size in bytes
    • clear

      public void clear()
      reset to an empty bitmap; result occupies as much space a newly created bitmap.
    • toArray

      public long[] toArray()
      Return the set values as an array, if the cardinality is smaller than 2147483648. The long values are in sorted order.
      Specified by:
      toArray in interface ImmutableLongBitmapDataProvider
      Returns:
      array representing the set values.
    • bitmapOf

      public static Roaring64NavigableMap bitmapOf(long... dat)
      Generate a bitmap with the specified values set to true. The provided longs values don't have to be in sorted order, but it may be preferable to sort them from a performance point of view.
      Parameters:
      dat - set values
      Returns:
      a new bitmap
    • add

      public void add(long... dat)
      Set all the specified values to true. This can be expected to be slightly faster than calling "add" repeatedly. The provided integers values don't have to be in sorted order, but it may be preferable to sort them from a performance point of view.
      Parameters:
      dat - set values
    • add

      @Deprecated public void add(long rangeStart, long rangeEnd)
      Deprecated.
      as this may be confused with adding individual longs
      Add to the current bitmap all longs in [rangeStart,rangeEnd).
      Parameters:
      rangeStart - inclusive beginning of range
      rangeEnd - exclusive ending of range
    • addRange

      public void addRange(long rangeStart, long rangeEnd)
      Add to the current bitmap all longs in [rangeStart,rangeEnd).
      Parameters:
      rangeStart - inclusive beginning of range
      rangeEnd - exclusive ending of range
    • getReverseLongIterator

      public LongIterator getReverseLongIterator()
      Specified by:
      getReverseLongIterator in interface ImmutableLongBitmapDataProvider
      Returns:
      a custom iterator over set bits, the bits are traversed in descending sorted order
    • removeLong

      public void removeLong(long x)
      Description copied from interface: LongBitmapDataProvider
      If present remove the specified integers (effectively, sets its bit value to false)
      Specified by:
      removeLong in interface LongBitmapDataProvider
      Parameters:
      x - long value representing the index in a bitmap
    • trim

      public void trim()
      Description copied from interface: LongBitmapDataProvider
      Recover allocated but unused memory.
      Specified by:
      trim in interface LongBitmapDataProvider
    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object
    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object
    • flip

      public void flip(long x)
      Add the value if it is not already present, otherwise remove it.
      Parameters:
      x - long value
    • assertNonEmpty

      private void assertNonEmpty()
    • first

      public long first()
      Description copied from interface: ImmutableLongBitmapDataProvider
      Get the first (smallest) integer in this RoaringBitmap, that is, return the minimum of the set.
      Specified by:
      first in interface ImmutableLongBitmapDataProvider
      Returns:
      the first (smallest) integer
    • last

      public long last()
      Description copied from interface: ImmutableLongBitmapDataProvider
      Get the last (largest) integer in this RoaringBitmap, that is, return the maximum of the set.
      Specified by:
      last in interface ImmutableLongBitmapDataProvider
      Returns:
      the last (largest) integer