public final class LargeDoubleArray
extends java.lang.Object
implements java.lang.Cloneable, java.lang.Iterable<java.lang.Double>
This class enables arrays of doubles 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(double)
and pop()
operations.
This class also contains a number of convenience functions to easily add(long, double)
, subtract(long, double)
, multiply(long, double)
and divide(long, double)
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 (double x : array)
and
for (double x : array.fromto(10, 50)
Modifier and Type | Class and Description |
---|---|
class |
LargeDoubleArray.FromIterable
Iterable starting from a certain element.
|
class |
LargeDoubleArray.FromToIterable
Iterable starting from a certain element to a certain element.
|
class |
LargeDoubleArray.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 |
---|
LargeDoubleArray(double[] values)
Constructs a new array copying the values of the supplied array.
|
LargeDoubleArray(long size)
Constructs a new empty array of specified size.
|
LargeDoubleArray(long size,
double 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,
double addition)
Adds addition to existing element.
|
void |
append(double value)
Appends a specified value to the end of the array.
|
long |
binarySearch(double value)
Searches for the specified value using binary search.
|
long |
binarySearch(long from,
long to,
double value)
Searches for the specified value using binary search in the indicated
range.
|
double |
calcAverage()
Calculates the average of all elements.
|
double |
calcMaximum()
Calculates the maximum of all elements.
|
double |
calcMinimum()
Calculates the minimum of all elements.
|
double |
calcSum()
Calculates the sum of all elements.
|
double |
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.
|
LargeDoubleArray |
clone()
Clones the array.
|
LargeDoubleArray |
copyOfRange(long from,
long to)
Copies the specified range to a new array.
|
void |
divide(long index,
double 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(double constant)
Fills entire array with constant.
|
void |
fill(long from,
long to,
double constant)
Fills indicated range with constant.
|
LargeDoubleArray.FromIterable |
from(long from)
Iterates over all elements, starting from the indicated element.
|
LargeDoubleArray.FromToIterable |
fromTo(long from,
long to)
Iterates over elements in indicated range.
|
double |
get(int segment,
int offset)
Gets value element based on segment and offset.
|
double |
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.
|
LargeDoubleArray.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,
double multiplier)
Multiplies existing element by multiplier.
|
int |
nSegments()
Gets the number of segments.
|
double |
pop()
Pops last value off the end of the array.
|
void |
push(double 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,
double value)
Sets element to value for indicated segment and offset.
|
void |
set(long index,
double 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,
double subtraction)
Subtracts subtraction from existing element.
|
void |
swap(long indexA,
long indexB)
Swaps two elements.
|
double[] |
toArray()
Copies the values to an ordinary array.
|
double[] |
toArray(long from,
long to)
Copies indicated range to an ordinary array.
|
void |
updateFrom(LargeDoubleArray array)
Updates this array from the provided array.
|
void |
updateFrom(LargeDoubleArray 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 LargeDoubleArray(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 LargeDoubleArray(long size, double constant)
size
- Size of the arrayconstant
- Constant value to setpublic LargeDoubleArray(double[] 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 double get(long index)
index
- Index of elementpublic double get(int segment, int offset)
segment
- Segment of elementoffset
- Offset of elementpublic void set(long index, double value)
index
- Index of elementvalue
- Valuepublic void set(int segment, int offset, double value)
segment
- Segment of elementoffset
- Offset of elementvalue
- Valuepublic void fill(double constant)
constant
- Constantpublic void fill(long from, long to, double constant)
from
- From index, inclusiveto
- To index, exclusiveconstant
- Constantpublic void append(double value)
value
- Valuepush(double)
,
pop()
public void push(double value)
value
- Valueappend(double)
,
pop()
public double 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, double addition)
index
- Index of elementaddition
- Value to addpublic void subtract(long index, double subtraction)
index
- Index of elementsubtraction
- Value to subtractpublic void multiply(long index, double multiplier)
index
- Index of elementmultiplier
- Multiplierpublic void divide(long index, double divisor)
index
- Index of elementdivisor
- Divisorpublic double calcSum()
public double calcSum(long from, long to)
from
- From index, inclusiveto
- To index, exclusivepublic double calcAverage()
public double calcMaximum()
public double 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(double 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, double 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 LargeDoubleArray.Iterator iterator()
iterator
in interface java.lang.Iterable<java.lang.Double>
public LargeDoubleArray.FromIterable from(long from)
from
- From index, inclusivepublic LargeDoubleArray.FromToIterable fromTo(long from, long to)
from
- From index, inclusiveto
- To index, exclusivepublic void updateFrom(LargeDoubleArray array)
array
- Array to update frompublic void updateFrom(LargeDoubleArray 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 LargeDoubleArray copyOfRange(long from, long to)
from
- From index, inclusiveto
- To index, exclusivepublic double[] toArray()
Not all elements of this array may fit in an ordinary array.
public double[] toArray(long from, long to)
from
- From index, inclusiveto
- To index, exclusivepublic LargeDoubleArray clone()
clone
in class java.lang.Object