Package org.roaringbitmap
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 Summary
FieldsModifier and TypeFieldDescription(package private) static final int
(package private) char[]
private static final int
private static final char
private static final char
private static final long
(package private) int
(package private) Container[]
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
(package private)
RoaringArray
(char[] keys, Container[] values, int size) (package private)
RoaringArray
(int initialCapacity) -
Method Summary
Modifier and TypeMethodDescriptionprotected int
advanceUntil
(char x, int pos) Find the smallest integer index larger than pos such that array[index].key>=x.void
Appends the key and container to the storage, throws if the key is less than the current mark.(package private) void
append
(RoaringArray roaringArray) protected void
append
(RoaringArray sa, int startingIndex, int end) Append the values from another array, no copy is made (use with care)(package private) void
appendCopiesAfter
(RoaringArray sa, char beforeStart) Append copies of the values AFTER a specified key (may or may not be present) to end.(package private) void
appendCopiesUntil
(RoaringArray sourceArray, char stoppingKey) Append copies of the values from another array, from the start(package private) void
appendCopy
(RoaringArray sa, int index) Append copy of the one value from another array(package private) void
appendCopy
(RoaringArray sa, int startingIndex, int end) Append copies of the values from another arrayprivate void
private int
binarySearch
(int begin, int end, char key) protected void
clear()
clone()
(package private) void
copyRange
(int begin, int end, int newBegin) void
deserialize
(DataInput in) Deserialize.void
deserialize
(DataInput in, byte[] buffer) Deserialize.void
deserialize
(ByteBuffer bbf) Deserialize (retrieve) this bitmap.boolean
(package private) void
extendArray
(int k) int
first()
Gets the first value in the arrayprotected Container
getContainer
(char x) protected Container
getContainerAtIndex
(int i) protected int
getContainerIndex
(char x) Create a ContainerPointer for this RoaringArraygetContainerPointer
(int startIndex) Create a ContainerPointer for this RoaringArray(package private) int
getIndex
(char x) protected char
getKeyAtIndex
(int i) int
hashCode()
private boolean
private int
(package private) void
insertNewKeyValueAt
(int i, char key, Container value) int
last()
Gets the last value in the arrayvoid
(package private) void
removeAtIndex
(int i) (package private) void
removeIndexRange
(int begin, int end) (package private) void
replaceKeyAndContainerAtIndex
(int i, char key, Container c) (package private) void
resize
(int newLength) void
serialize
(DataOutput out) Serialize.void
serialize
(ByteBuffer buffer) Serialize.int
Report the number of bytes required for serialization.(package private) void
setContainerAtIndex
(int i, Container c) protected int
size()
void
trim()
If possible, recover wasted memory.void
-
Field Details
-
SERIAL_COOKIE_NO_RUNCONTAINER
private static final char SERIAL_COOKIE_NO_RUNCONTAINER- See Also:
-
SERIAL_COOKIE
private static final char SERIAL_COOKIE- See Also:
-
NO_OFFSET_THRESHOLD
private static final int NO_OFFSET_THRESHOLD- See Also:
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
INITIAL_CAPACITY
static final int INITIAL_CAPACITY- See Also:
-
keys
char[] keys -
values
Container[] values -
size
int size
-
-
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 valuepos
- 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
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 interfaceAppendableStorage<Container>
- Parameters:
key
- the key to appendvalue
- the data to append
-
append
-
appendCopiesAfter
Append copies of the values AFTER a specified key (may or may not be present) to end.- Parameters:
sa
- other arraybeforeStart
- given key is the largest key that we won't copy
-
appendCopiesUntil
Append copies of the values from another array, from the start- Parameters:
sourceArray
- The array to copy fromstoppingKey
- any equal or larger key in other array will terminate copying
-
appendCopy
Append copy of the one value from another array- Parameters:
sa
- other arrayindex
- index in the other array
-
appendCopy
Append copies of the values from another array- Parameters:
sa
- other arraystartingIndex
- starting index in the other arrayend
- endingIndex (exclusive) in the other array
-
append
Append the values from another array, no copy is made (use with care)- Parameters:
sa
- other arraystartingIndex
- starting index in the other arrayend
- 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 classObject
- Throws:
CloneNotSupportedException
-
copyRange
void copyRange(int begin, int end, int newBegin) -
deserialize
Deserialize. If the DataInput is available as a byte[] or a ByteBuffer, you could prefer relying ondeserialize(ByteBuffer)
. If the InputStream is >= 8kB, you could prefer relying ondeserialize(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
Deserialize.- Parameters:
in
- the DataInput streambuffer
- 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
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
-
extendArray
void extendArray(int k) -
getContainer
-
getContainerIndex
protected int getContainerIndex(char x) -
getContainerAtIndex
-
getContainerPointer
Create a ContainerPointer for this RoaringArray- Returns:
- a ContainerPointer
-
getContainerPointer
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() -
hasRunContainer
private boolean hasRunContainer() -
headerSize
private int headerSize() -
insertNewKeyValueAt
-
readExternal
- Specified by:
readExternal
in interfaceExternalizable
- Throws:
IOException
-
removeAtIndex
void removeAtIndex(int i) -
removeIndexRange
void removeIndexRange(int begin, int end) -
replaceKeyAndContainerAtIndex
-
resize
void resize(int newLength) -
serialize
Serialize. The current bitmap is not modified.- Parameters:
out
- the DataOutput stream- Throws:
IOException
- Signals that an I/O exception has occurred.
-
serialize
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
-
size
protected int size() -
writeExternal
- Specified by:
writeExternal
in interfaceExternalizable
- 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()
-