public final class LargeLongArray
extends java.lang.Object
implements java.lang.Cloneable, java.lang.Iterable<java.lang.Long>
This class enables arrays of longs up to 64-bits in size (for the exact
maximum size, please see MAX_SIZE
). As a single array is limited to
32-bits in Java, this is done by having an array of arrays. We use a
long
to index this array of arrays, and use bitwise operators
to extract the two indices for the array of arrays. The largest index is
extracted using getSegment(long)
while the smallest index is extracted
using getOffset(long)
, where the actual value is located in
values[segment][offset]
.
In addition, this class enables a dynamic array, and can be dynamically
enlarged or shrunken. The total capacity is indicated by capacity()
,
while the actual number of elements is indicated by size()
. When
constructing new arrays, typically the size is set equal to the capacity,
with the restriction that we always at least reserve a minimum capacity
(indicated by MINIMUM_INITIAL_CAPACITY
). This dynamic array then
also supports push(long)
and pop()
operations.
This class also contains a number of convenience functions to easily add(long, long)
, subtract(long, long)
, multiply(long, long)
and divide(long, long)
elements.
This is more efficient than calling both set
and
get
because this requires to retrieve indices twice.
To facilitate easy iteration over this array, a few convenience iterables are
provided, enabling you to use construct such as
for (long x : array)
and
for (long x : array.fromto(10, 50)
Modifier and Type | Class and Description |
---|---|
class |
LargeLongArray.FromIterable
Iterable starting from a certain element.
|
class |
LargeLongArray.FromToIterable
Iterable starting from a certain element to a certain element.
|
class |
LargeLongArray.Iterator
Iterator capable of iterating over a specified range.
|
Modifier and Type | Field and Description |
---|---|
static byte |
ARRAY_BIT_SIZE
The number of bits to use for each individual array.
|
static long |
MAX_SIZE
The maximum size of the array in total.
|
static int |
MAX_SIZE_ARRAY
The maximum size of each individual array.
|
static long |
MINIMUM_INITIAL_CAPACITY
Minimum initial capacity of the array.
|
static double |
RELATIVE_CAPACITY_INCREASE
The relative increase in the capacity when increasing the capacity.
|
Constructor and Description |
---|
LargeLongArray(long size)
Constructs a new empty array of specified size.
|
LargeLongArray(long[] values)
Constructs a new array copying the values of the supplied array.
|
LargeLongArray(long size,
long constant)
Constructs a new array of indicated size with all elements set to a
constant value.
|
Modifier and Type | Method and Description |
---|---|
void |
add(long index,
long addition)
Adds addition to existing element.
|
void |
append(long value)
Appends a specified value to the end of the array.
|
long |
binarySearch(long value)
Searches for the specified value using binary search.
|
long |
binarySearch(long from,
long to,
long value)
Searches for the specified value using binary search in the indicated
range.
|
double |
calcAverage()
Calculates the average of all elements.
|
long |
calcMaximum()
Calculates the maximum of all elements.
|
long |
calcMinimum()
Calculates the minimum of all elements.
|
long |
calcSum()
Calculates the sum of all elements.
|
long |
calcSum(long from,
long to)
Calculates the sum of all elements in the indicated range.
|
long |
capacity()
Gets capacity of array.
|
void |
clear()
Removes all elements from the array.
|
LargeLongArray |
clone()
Clones the array.
|
LargeLongArray |
copyOfRange(long from,
long to)
Copies the specified range to a new array.
|
void |
divide(long index,
long divisor)
Divides existing element by divisor.
|
void |
ensureCapacity(long minCapacity)
Increases the capacity to ensure that the array has at least the minimum
capacity.
|
void |
fill(long constant)
Fills entire array with constant.
|
void |
fill(long from,
long to,
long constant)
Fills indicated range with constant.
|
LargeLongArray.FromIterable |
from(long from)
Iterates over all elements, starting from the indicated element.
|
LargeLongArray.FromToIterable |
fromTo(long from,
long to)
Iterates over elements in indicated range.
|
long |
get(int segment,
int offset)
Gets value element based on segment and offset.
|
long |
get(long index)
Gets value element based on long index.
|
static int |
getOffset(long index)
Gets the offset within a particular segment of the index.
|
static int |
getSegment(long index)
Gets the segment of the index.
|
LargeLongArray.Iterator |
iterator()
Iterates over all elements
|
int |
length(int segment)
Gets the length of the indicated segment.
|
void |
mergeSort()
Sorts elements in ascending order using merge sort.
|
void |
multiply(long index,
long multiplier)
Multiplies existing element by multiplier.
|
int |
nSegments()
Gets the number of segments.
|
long |
pop()
Pops last value off the end of the array.
|
void |
push(long value)
Appends a specified value to the end of the array.
|
void |
quickSort()
Sorts elements in ascending order using quick sort.
|
void |
resize(long size)
Resizes array.
|
void |
set(int segment,
int offset,
long value)
Sets element to value for indicated segment and offset.
|
void |
set(long index,
long value)
Sets element to value for indicated index.
|
void |
shrink()
Shrinks capacity to fit actual size.
|
long |
size()
Gets size of array.
|
void |
sort()
Sorts elements in ascending order using merge sort.
|
void |
sort(it.unimi.dsi.fastutil.longs.LongComparator comparator)
Sorts elements in a specified order using merge sort.
|
void |
subtract(long index,
long subtraction)
Subtracts subtraction from existing element.
|
void |
swap(long indexA,
long indexB)
Swaps two elements.
|
long[] |
toArray()
Copies the values to an ordinary array.
|
long[] |
toArray(long from,
long to)
Copies indicated range to an ordinary array.
|
void |
updateFrom(LargeLongArray array)
Updates this array from the provided array.
|
void |
updateFrom(LargeLongArray array,
long from,
long to,
long insertionPoint)
Updates this array from the provided array.
|
public static final byte ARRAY_BIT_SIZE
public static final int MAX_SIZE_ARRAY
public static final long MINIMUM_INITIAL_CAPACITY
public static final double RELATIVE_CAPACITY_INCREASE
public static final long MAX_SIZE
public LargeLongArray(long size)
Both the capacity and the size is being set to size
, with
all elements initialised to their default value. If instead, you prefer
an empty array, but reserve capacity, pass 0
size
here and use ensureCapacity(long)
.
size
- Size of the arraypublic LargeLongArray(long size, long constant)
size
- Size of the arrayconstant
- Constant value to setpublic LargeLongArray(long[] values)
values
- Array to copy frompublic static int getSegment(long index)
index
- Indexpublic static int getOffset(long index)
index
- Indexpublic int nSegments()
public int length(int segment)
segment
- Segmentpublic long get(long index)
index
- Index of elementpublic long get(int segment, int offset)
segment
- Segment of elementoffset
- Offset of elementpublic void set(long index, long value)
index
- Index of elementvalue
- Valuepublic void set(int segment, int offset, long value)
segment
- Segment of elementoffset
- Offset of elementvalue
- Valuepublic void fill(long constant)
constant
- Constantpublic void fill(long from, long to, long constant)
from
- From index, inclusiveto
- To index, exclusiveconstant
- Constantpublic void append(long value)
value
- Valuepush(long)
,
pop()
public void push(long value)
value
- Valueappend(long)
,
pop()
public long pop()
public void clear()
public void ensureCapacity(long minCapacity)
The capacity is increased with a percentage indicated by RELATIVE_CAPACITY_INCREASE
, unless the indicated minimum capacity
exceeds this.
minCapacity
- Minimum capacitypublic void resize(long size)
size
- New sizepublic void shrink()
public long size()
This is always less than or equal to the capacity.
public long capacity()
This is always greater than or equal to the size.
public void add(long index, long addition)
index
- Index of elementaddition
- Value to addpublic void subtract(long index, long subtraction)
index
- Index of elementsubtraction
- Value to subtractpublic void multiply(long index, long multiplier)
index
- Index of elementmultiplier
- Multiplierpublic void divide(long index, long divisor)
index
- Index of elementdivisor
- Divisorpublic long calcSum()
public long calcSum(long from, long to)
from
- From index, inclusiveto
- To index, exclusivepublic double calcAverage()
public long calcMaximum()
public long calcMinimum()
public void swap(long indexA, long indexB)
indexA
- First element to swapindexB
- Second element to swappublic void mergeSort()
public void quickSort()
public void sort()
public void sort(it.unimi.dsi.fastutil.longs.LongComparator comparator)
comparator
- Comparator indicating the desired orderingpublic long binarySearch(long value)
The array must be sorted in ascending order prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.
value
- The value to search forpublic long binarySearch(long from, long to, long value)
The (range of the) array must be sorted in ascending order prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.
from
- From index, inclusiveto
- To index, exclusivevalue
- The value to search forpublic LargeLongArray.Iterator iterator()
iterator
in interface java.lang.Iterable<java.lang.Long>
public LargeLongArray.FromIterable from(long from)
from
- From index, inclusivepublic LargeLongArray.FromToIterable fromTo(long from, long to)
from
- From index, inclusiveto
- To index, exclusivepublic void updateFrom(LargeLongArray array)
array
- Array to update frompublic void updateFrom(LargeLongArray array, long from, long to, long insertionPoint)
Values from other array starting at from
until
to
(exclusive) will be copied to this array, starting
from the insertionPoint
onwards.
array
- Array to update fromfrom
- Index in array
from where to update,
inclusiveto
- Index in array
until where to update,
exclusiveinsertionPoint
- Starting index in this array to updatepublic LargeLongArray copyOfRange(long from, long to)
from
- From index, inclusiveto
- To index, exclusivepublic long[] toArray()
Not all elements of this array may fit in an ordinary array.
public long[] toArray(long from, long to)
from
- From index, inclusiveto
- To index, exclusivepublic LargeLongArray clone()
clone
in class java.lang.Object