Class RoaringArray

java.lang.Object
org.roaringbitmap.RoaringArray
All Implemented Interfaces:
Externalizable, Serializable, Cloneable, AppendableStorage<Container>

public final class RoaringArray extends Object implements Cloneable, Externalizable, AppendableStorage<Container>
Specialized array to store the containers used by a RoaringBitmap. This is not meant to be used by end users.
See Also:
  • Field Details

  • Constructor Details

    • RoaringArray

      protected RoaringArray()
    • RoaringArray

      RoaringArray(int initialCapacity)
    • RoaringArray

      RoaringArray(char[] keys, Container[] values, int size)
  • Method Details

    • advanceUntil

      protected int advanceUntil(char x, int pos)
      Find the smallest integer index larger than pos such that array[index].key>=x. If none can be found, return size. Based on code by O. Kaser.
      Parameters:
      x - minimal value
      pos - index to exceed
      Returns:
      the smallest index greater than pos such that array[index].key is at least as large as min, or size if it is not possible.
    • append

      public void append(char key, Container value)
      Description copied from interface: AppendableStorage
      Appends the key and container to the storage, throws if the key is less than the current mark.
      Specified by:
      append in interface AppendableStorage<Container>
      Parameters:
      key - the key to append
      value - the data to append
    • append

      void append(RoaringArray roaringArray)
    • appendCopiesAfter

      void appendCopiesAfter(RoaringArray sa, char beforeStart)
      Append copies of the values AFTER a specified key (may or may not be present) to end.
      Parameters:
      sa - other array
      beforeStart - given key is the largest key that we won't copy
    • appendCopiesUntil

      void appendCopiesUntil(RoaringArray sourceArray, char stoppingKey)
      Append copies of the values from another array, from the start
      Parameters:
      sourceArray - The array to copy from
      stoppingKey - any equal or larger key in other array will terminate copying
    • appendCopy

      void appendCopy(RoaringArray sa, int index)
      Append copy of the one value from another array
      Parameters:
      sa - other array
      index - index in the other array
    • appendCopy

      void appendCopy(RoaringArray sa, int startingIndex, int end)
      Append copies of the values from another array
      Parameters:
      sa - other array
      startingIndex - starting index in the other array
      end - endingIndex (exclusive) in the other array
    • append

      protected void append(RoaringArray sa, int startingIndex, int end)
      Append the values from another array, no copy is made (use with care)
      Parameters:
      sa - other array
      startingIndex - starting index in the other array
      end - endingIndex (exclusive) in the other array
    • binarySearch

      private int binarySearch(int begin, int end, char key)
    • clear

      protected void clear()
    • trim

      public void trim()
      If possible, recover wasted memory.
    • clone

      Overrides:
      clone in class Object
      Throws:
      CloneNotSupportedException
    • copyRange

      void copyRange(int begin, int end, int newBegin)
    • deserialize

      public void deserialize(DataInput in) throws IOException
      Deserialize. If the DataInput is available as a byte[] or a ByteBuffer, you could prefer relying on deserialize(ByteBuffer). If the InputStream is >= 8kB, you could prefer relying on deserialize(DataInput, byte[]);
      Parameters:
      in - the DataInput stream
      Throws:
      IOException - Signals that an I/O exception has occurred.
      InvalidRoaringFormat - if a Roaring Bitmap cookie is missing.
    • deserialize

      public void deserialize(DataInput in, byte[] buffer) throws IOException
      Deserialize.
      Parameters:
      in - the DataInput stream
      buffer - The buffer gets overwritten with data during deserialization. You can pass a NULL reference as a buffer. A buffer containing at least 8192 bytes might be ideal for performance. It is recommended to reuse the buffer between calls to deserialize (in a single-threaded context) for best performance.
      Throws:
      IOException - Signals that an I/O exception has occurred.
      InvalidRoaringFormat - if a Roaring Bitmap cookie is missing.
    • deserialize

      public void deserialize(ByteBuffer bbf)
      Deserialize (retrieve) this bitmap. See format specification at https://github.com/RoaringBitmap/RoaringFormatSpec The current bitmap is overwritten. It is not necessary that limit() on the input ByteBuffer indicates the end of the serialized data. After loading this RoaringBitmap, you can advance to the rest of the data (if there is more) by setting bbf.position(bbf.position() + bitmap.serializedSizeInBytes()); Note that the input ByteBuffer is effectively copied (with the slice operation) so you should expect the provided ByteBuffer position/mark/limit/order to remain unchanged.
      Parameters:
      bbf - the byte buffer (can be mapped, direct, array backed etc.
    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object
    • extendArray

      void extendArray(int k)
    • getContainer

      protected Container getContainer(char x)
    • getContainerIndex

      protected int getContainerIndex(char x)
    • getContainerAtIndex

      protected Container getContainerAtIndex(int i)
    • getContainerPointer

      public ContainerPointer getContainerPointer()
      Create a ContainerPointer for this RoaringArray
      Returns:
      a ContainerPointer
    • getContainerPointer

      public ContainerPointer getContainerPointer(int startIndex)
      Create a ContainerPointer for this RoaringArray
      Parameters:
      startIndex - starting index in the container list
      Returns:
      a ContainerPointer
    • getIndex

      int getIndex(char x)
    • getKeyAtIndex

      protected char getKeyAtIndex(int i)
    • hashCode

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

      private boolean hasRunContainer()
    • headerSize

      private int headerSize()
    • insertNewKeyValueAt

      void insertNewKeyValueAt(int i, char key, Container value)
    • readExternal

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

      void removeAtIndex(int i)
    • removeIndexRange

      void removeIndexRange(int begin, int end)
    • replaceKeyAndContainerAtIndex

      void replaceKeyAndContainerAtIndex(int i, char key, Container c)
    • resize

      void resize(int newLength)
    • serialize

      public void serialize(DataOutput out) throws IOException
      Serialize. The current bitmap is not modified.
      Parameters:
      out - the DataOutput stream
      Throws:
      IOException - Signals that an I/O exception has occurred.
    • serialize

      public void serialize(ByteBuffer buffer)
      Serialize. The current bitmap is not modified.
      Parameters:
      buffer - the ByteBuffer to write to
    • serializedSizeInBytes

      public int serializedSizeInBytes()
      Report the number of bytes required for serialization.
      Returns:
      the size in bytes
    • setContainerAtIndex

      void setContainerAtIndex(int i, Container c)
    • size

      protected int size()
    • writeExternal

      public void writeExternal(ObjectOutput out) throws IOException
      Specified by:
      writeExternal in interface Externalizable
      Throws:
      IOException
    • first

      public int first()
      Gets the first value in the array
      Returns:
      the first value in the array
      Throws:
      NoSuchElementException - if empty
    • last

      public int last()
      Gets the last value in the array
      Returns:
      the last value in the array
      Throws:
      NoSuchElementException - if empty
    • assertNonEmpty

      private void assertNonEmpty()