public class SparseBinSearchByteArray extends SparseByteArray
Element access has worst-case O(log n) performance. Appends (where the index being added is greater than the existing indices) has O(1) complexity. Random puts have worst case O(n + log n) complexity. Complexity for getting values by increasing index for iteration through the non-zero values is O(1).
In summary, this implementation has good access performance, and is fast for appending values, but slow for putting at random indices. It is is optimal for a scenario where you first create the sparse array and put values in order of increasing indices, and later use the array mostly for reading.
SparseByteArray.DualEntry, SparseByteArray.Entry| Modifier and Type | Field and Description |
|---|---|
protected int[] |
keys |
protected int |
used |
protected byte[] |
values |
DEFAULT_CAPACITY, length| Constructor and Description |
|---|
SparseBinSearchByteArray(byte[] values)
Construct from an existing array of values
|
SparseBinSearchByteArray(int length)
Construct the array with the given length
|
SparseBinSearchByteArray(int length,
float density)
Construct the array with the given length and expected density
|
SparseBinSearchByteArray(int length,
int capacity)
Construct the array with the given length and capacity for non-zero elements
|
SparseBinSearchByteArray(int length,
int used,
int[] keys,
byte[] values)
Generate a new
SparseBinSearchByteArray wrapper which works around
an existing array of keys and values |
| Modifier and Type | Method and Description |
|---|---|
void |
compact()
Compact the space being used by the array if possible.
|
SparseByteArray |
copy()
Deep copy the array.
|
Iterable<SparseByteArray.Entry> |
entries()
Provide an iterator over the non-zero values.
|
boolean |
equals(Object obj) |
byte |
get(int key)
Get the value at the given index.
|
int |
hashCode() |
byte |
increment(int key,
byte value)
Increment the value at the given index.
|
int[] |
indices() |
boolean |
isUsed(int key)
Check whether the given index is used (i.e.
|
SparseByteArray |
reverse()
Reverse the elements, returning this.
|
byte |
set(int key,
byte value)
Set the value at the given index.
|
Iterable<SparseByteArray.DualEntry> |
unionEntries(SparseBinSearchByteArray otherArray)
Provide an iterator over the union of values present in
both this array and another array.
|
Iterable<SparseByteArray.DualEntry> |
unionEntries(SparseByteArray otherArray)
Provide an iterator over the union of values present in
both this array and another array.
|
int |
used() |
byte[] |
values() |
add, addInplace, asciiHeader, binaryHeader, concatenate, concatenate, concatenateArrays, density, dotProduct, intersectEntries, length, maxIndex, maxValue, minIndex, minValue, multiply, multiplyInplace, readASCII, readBinary, setLength, size, subtract, subtractInplace, sumValues, sumValuesSquared, toArray, toArray, writeASCII, writeBinarypublic SparseBinSearchByteArray(byte[] values)
values - the valuespublic SparseBinSearchByteArray(int length, int used, int[] keys, byte[] values)
SparseBinSearchByteArray wrapper which works around
an existing array of keys and valueslength - used - keys - values - public SparseBinSearchByteArray(int length)
length - the lengthpublic SparseBinSearchByteArray(int length, int capacity)
length - the lengthcapacity - the capacitypublic SparseBinSearchByteArray(int length, float density)
length - the lengthdensity - the densitypublic int[] indices()
indices in class SparseByteArraypublic byte[] values()
values in class SparseByteArraypublic Iterable<SparseByteArray.DualEntry> unionEntries(SparseByteArray otherArray)
SparseByteArray
Note: the SparseByteArray.DualEntry returned by the iterator
is always the same object. In addition, the iterator
cannot affect the value of anything in the array (i.e.
changing anything in the SparseByteArray.DualEntry has no effect
on the actual array).
unionEntries in class SparseByteArrayotherArray - the second arraypublic Iterable<SparseByteArray.DualEntry> unionEntries(SparseBinSearchByteArray otherArray)
Note: the SparseByteArray.DualEntry returned by the iterator
is always the same object. In addition, the iterator
cannot affect the value of anything in the array (i.e.
changing anything in the SparseByteArray.DualEntry has no effect
on the actual array).
otherArray - the second arraypublic Iterable<SparseByteArray.Entry> entries()
SparseByteArray
Note: the SparseByteArray.Entry returned by the iterator
is always the same object. In addition, the iterator
cannot affect the value of anything in the array (i.e.
changing anything in the SparseByteArray.Entry has no effect
on the actual array).
entries in class SparseByteArraypublic byte get(int key)
SparseByteArrayget in class SparseByteArraykey - the indexpublic boolean isUsed(int key)
SparseByteArrayisUsed in class SparseByteArraykey - the indexpublic byte set(int key, byte value)
SparseByteArrayset in class SparseByteArraykey - the index.value - the value to set.public byte increment(int key, byte value)
SparseByteArrayincrement in class SparseByteArraykey - the indexvalue - the amount to increment by.public int used()
used in class SparseByteArraypublic void compact()
SparseByteArraycompact in class SparseByteArraypublic SparseByteArray copy()
SparseByteArraycopy in class SparseByteArraypublic SparseByteArray reverse()
SparseByteArrayreverse in class SparseByteArray