LargeIntArray (networkanalysis 1.3.0 API)

java.lang.Object
- nl.cwts.util.LargeIntArray

All Implemented Interfaces:

java.lang.Cloneable, java.lang.Iterable<java.lang.Integer>
```
public final class LargeIntArray
extends java.lang.Object
implements java.lang.Cloneable, java.lang.Iterable<java.lang.Integer>
```
This class enables arrays of ints 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(int) and pop() operations.

This class also contains a number of convenience functions to easily add(long, int), subtract(long, int), multiply(long, int) and divide(long, int) 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 (int x : array) and for (int x : array.fromto(10, 50)

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`class`	`LargeIntArray.FromIterable` Iterable starting from a certain element.
`class`	`LargeIntArray.FromToIterable` Iterable starting from a certain element to a certain element.
`class`	`LargeIntArray.Iterator` Iterator capable of iterating over a specified range.

Field Summary

Fields
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 Summary

Constructors
Constructor and Description
`LargeIntArray(int[] values)` Constructs a new array copying the values of the supplied array.
`LargeIntArray(long size)` Constructs a new empty array of specified size.
`LargeIntArray(long size, int constant)` Constructs a new array of indicated size with all elements set to a constant value.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`add(long index, int addition)` Adds addition to existing element.
`void`	`append(int value)` Appends a specified value to the end of the array.
`long`	`binarySearch(int value)` Searches for the specified value using binary search.
`long`	`binarySearch(long from, long to, int value)` Searches for the specified value using binary search in the indicated range.
`double`	`calcAverage()` Calculates the average of all elements.
`int`	`calcMaximum()` Calculates the maximum of all elements.
`int`	`calcMinimum()` Calculates the minimum of all elements.
`int`	`calcSum()` Calculates the sum of all elements.
`int`	`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.
`LargeIntArray`	`clone()` Clones the array.
`LargeIntArray`	`copyOfRange(long from, long to)` Copies the specified range to a new array.
`void`	`divide(long index, int 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(int constant)` Fills entire array with constant.
`void`	`fill(long from, long to, int constant)` Fills indicated range with constant.
`LargeIntArray.FromIterable`	`from(long from)` Iterates over all elements, starting from the indicated element.
`LargeIntArray.FromToIterable`	`fromTo(long from, long to)` Iterates over elements in indicated range.
`int`	`get(int segment, int offset)` Gets value element based on segment and offset.
`int`	`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.
`LargeIntArray.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, int multiplier)` Multiplies existing element by multiplier.
`int`	`nSegments()` Gets the number of segments.
`int`	`pop()` Pops last value off the end of the array.
`void`	`push(int 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, int value)` Sets element to value for indicated segment and offset.
`void`	`set(long index, int 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, int subtraction)` Subtracts subtraction from existing element.
`void`	`swap(long indexA, long indexB)` Swaps two elements.
`int[]`	`toArray()` Copies the values to an ordinary array.
`int[]`	`toArray(long from, long to)` Copies indicated range to an ordinary array.
`void`	`updateFrom(LargeIntArray array)` Updates this array from the provided array.
`void`	`updateFrom(LargeIntArray array, long from, long to, long insertionPoint)` Updates this array from the provided array.

Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.lang.Iterable
forEach, spliterator

- Field Detail
  - ARRAY_BIT_SIZE
```
public static final byte ARRAY_BIT_SIZE
```
    The number of bits to use for each individual array.
    
    See Also:
    
    Constant Field Values
  - MAX_SIZE_ARRAY
```
public static final int MAX_SIZE_ARRAY
```
    The maximum size of each individual array.
    
    See Also:
    
    Constant Field Values
  - MINIMUM_INITIAL_CAPACITY
```
public static final long MINIMUM_INITIAL_CAPACITY
```
    Minimum initial capacity of the array.
    
    See Also:
    
    Constant Field Values
  - RELATIVE_CAPACITY_INCREASE
```
public static final double RELATIVE_CAPACITY_INCREASE
```
    The relative increase in the capacity when increasing the capacity.
    
    See Also:
    
    Constant Field Values
  - MAX_SIZE
```
public static final long MAX_SIZE
```
    The maximum size of the array in total.
    
    See Also:
    
    Constant Field Values
- Constructor Detail
  - LargeIntArray
```
public LargeIntArray(long size)
```
    Constructs a new empty array of specified 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).
    
    Parameters:
    
    size - Size of the array
  - LargeIntArray
```
public LargeIntArray(long size,
                     int constant)
```
    Constructs a new array of indicated size with all elements set to a constant value.
    
    Parameters:
    
    size - Size of the array
    
    constant - Constant value to set
  - LargeIntArray
```
public LargeIntArray(int[] values)
```
    Constructs a new array copying the values of the supplied array.
    
    Parameters:
    
    values - Array to copy from
- Method Detail
  - getSegment
```
public static int getSegment(long index)
```
    Gets the segment of the index.
    
    Parameters:
    
    index - Index
    
    Returns:
    
    Segment
  - getOffset
```
public static int getOffset(long index)
```
    Gets the offset within a particular segment of the index.
    
    Parameters:
    
    index - Index
    
    Returns:
    
    Offset within particular segment
  - nSegments
```
public int nSegments()
```
    Gets the number of segments.
    
    Returns:
    
    Number of segments
  - length
```
public int length(int segment)
```
    Gets the length of the indicated segment.
    
    Parameters:
    
    segment - Segment
    
    Returns:
    
    Length of segment
  - get
```
public int get(long index)
```
    Gets value element based on long index.
    
    Parameters:
    
    index - Index of element
    
    Returns:
    
    Value of element
  - get
```
public int get(int segment,
               int offset)
```
    Gets value element based on segment and offset.
    
    Parameters:
    
    segment - Segment of element
    
    offset - Offset of element
    
    Returns:
    
    Value of element
  - set
```
public void set(long index,
                int value)
```
    Sets element to value for indicated index.
    
    Parameters:
    
    index - Index of element
    
    value - Value
  - set
```
public void set(int segment,
                int offset,
                int value)
```
    Sets element to value for indicated segment and offset.
    
    Parameters:
    
    segment - Segment of element
    
    offset - Offset of element
    
    value - Value
  - fill
```
public void fill(int constant)
```
    Fills entire array with constant.
    
    Parameters:
    
    constant - Constant
  - fill
```
public void fill(long from,
                 long to,
                 int constant)
```
    Fills indicated range with constant.
    
    Parameters:
    
    from - From index, inclusive
    
    to - To index, exclusive
    
    constant - Constant
  - append
```
public void append(int value)
```
    Appends a specified value to the end of the array.
    
    Parameters:
    
    value - Value
    
    See Also:
    
    push(int), pop()
  - push
```
public void push(int value)
```
    Appends a specified value to the end of the array.
    
    Parameters:
    
    value - Value
    
    See Also:
    
    append(int), pop()
  - pop
```
public int pop()
```
    Pops last value off the end of the array.
    
    Returns:
    
    Last value
  - clear
```
public void clear()
```
    Removes all elements from the array.
  - ensureCapacity
```
public void ensureCapacity(long minCapacity)
```
    Increases the capacity to ensure that the array has at least the minimum capacity.
    The capacity is increased with a percentage indicated by RELATIVE_CAPACITY_INCREASE, unless the indicated minimum capacity exceeds this.
    
    Parameters:
    
    minCapacity - Minimum capacity
  - resize
```
public void resize(long size)
```
    Resizes array.
    
    Parameters:
    
    size - New size
  - shrink
```
public void shrink()
```
    Shrinks capacity to fit actual size.
  - size
```
public long size()
```
    Gets size of array.
    This is always less than or equal to the capacity.
    
    Returns:
    
    Size
  - capacity
```
public long capacity()
```
    Gets capacity of array.
    This is always greater than or equal to the size.
    
    Returns:
    
    Capacity
  - add
```
public void add(long index,
                int addition)
```
    Adds addition to existing element.
    
    Parameters:
    
    index - Index of element
    
    addition - Value to add
  - subtract
```
public void subtract(long index,
                     int subtraction)
```
    Subtracts subtraction from existing element.
    
    Parameters:
    
    index - Index of element
    
    subtraction - Value to subtract
  - multiply
```
public void multiply(long index,
                     int multiplier)
```
    Multiplies existing element by multiplier.
    
    Parameters:
    
    index - Index of element
    
    multiplier - Multiplier
  - divide
```
public void divide(long index,
                   int divisor)
```
    Divides existing element by divisor.
    
    Parameters:
    
    index - Index of element
    
    divisor - Divisor
  - calcSum
```
public int calcSum()
```
    Calculates the sum of all elements.
    
    Returns:
    
    Sum
  - calcSum
```
public int calcSum(long from,
                   long to)
```
    Calculates the sum of all elements in the indicated range.
    
    Parameters:
    
    from - From index, inclusive
    
    to - To index, exclusive
    
    Returns:
    
    Sum
  - calcAverage
```
public double calcAverage()
```
    Calculates the average of all elements.
    
    Returns:
    
    Average
  - calcMaximum
```
public int calcMaximum()
```
    Calculates the maximum of all elements.
    
    Returns:
    
    Maximum
  - calcMinimum
```
public int calcMinimum()
```
    Calculates the minimum of all elements.
    
    Returns:
    
    Minimum
  - swap
```
public void swap(long indexA,
                 long indexB)
```
    Swaps two elements.
    
    Parameters:
    
    indexA - First element to swap
    
    indexB - Second element to swap
  - mergeSort
```
public void mergeSort()
```
    Sorts elements in ascending order using merge sort.
  - quickSort
```
public void quickSort()
```
    Sorts elements in ascending order using quick sort.
  - sort
```
public void sort()
```
    Sorts elements in ascending order using merge sort.
  - sort
```
public void sort(it.unimi.dsi.fastutil.longs.LongComparator comparator)
```
    Sorts elements in a specified order using merge sort.
    
    Parameters:
    
    comparator - Comparator indicating the desired ordering
  - binarySearch
```
public long binarySearch(int value)
```
    Searches for the specified value using binary search.
    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.
    
    Parameters:
    
    value - The value to search for
    
    Returns:
    
    Index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or the total size if all elements in the array are less than the specified key. Note that this guarantees that the return value will be non-negative if and only if the key is found.
  - binarySearch
```
public long binarySearch(long from,
                         long to,
                         int value)
```
    Searches for the specified value using binary search in the indicated range.
    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.
    
    Parameters:
    
    from - From index, inclusive
    
    to - To index, exclusive
    
    value - The value to search for
    
    Returns:
    
    Index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or the total size if all elements in the array are less than the specified key. Note that this guarantees that the return value will be non-negative if and only if the key is found.
  - iterator
```
public LargeIntArray.Iterator iterator()
```
    Iterates over all elements
    
    Specified by:
    
    iterator in interface java.lang.Iterable<java.lang.Integer>
    
    Returns:
    
    Iterator
  - from
```
public LargeIntArray.FromIterable from(long from)
```
    Iterates over all elements, starting from the indicated element.
    
    Parameters:
    
    from - From index, inclusive
    
    Returns:
    
    Iterable
  - fromTo
```
public LargeIntArray.FromToIterable fromTo(long from,
                                           long to)
```
    Iterates over elements in indicated range.
    
    Parameters:
    
    from - From index, inclusive
    
    to - To index, exclusive
    
    Returns:
    
    Iterable
  - updateFrom
```
public void updateFrom(LargeIntArray array)
```
    Updates this array from the provided array.
    
    Parameters:
    
    array - Array to update from
  - updateFrom
```
public void updateFrom(LargeIntArray array,
                       long from,
                       long to,
                       long insertionPoint)
```
    Updates this array from the provided array.
    Values from other array starting at from until to (exclusive) will be copied to this array, starting from the insertionPoint onwards.
    
    Parameters:
    
    array - Array to update from
    
    from - Index in array from where to update, inclusive
    
    to - Index in array until where to update, exclusive
    
    insertionPoint - Starting index in this array to update
  - copyOfRange
```
public LargeIntArray copyOfRange(long from,
                                 long to)
```
    Copies the specified range to a new array.
    
    Parameters:
    
    from - From index, inclusive
    
    to - To index, exclusive
    
    Returns:
    
    New array
  - toArray
```
public int[] toArray()
```
    Copies the values to an ordinary array.
    Not all elements of this array may fit in an ordinary array.
    
    Returns:
    
    Array
  - toArray
```
public int[] toArray(long from,
                     long to)
```
    Copies indicated range to an ordinary array.
    
    Parameters:
    
    from - From index, inclusive
    
    to - To index, exclusive
    
    Returns:
    
    Array
  - clone
```
public LargeIntArray clone()
```
    Clones the array.
    
    Overrides:
    
    clone in class java.lang.Object
    
    Returns:
    
    Cloned array

Class LargeIntArray

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.lang.Iterable

Field Detail

ARRAY_BIT_SIZE

MAX_SIZE_ARRAY

MINIMUM_INITIAL_CAPACITY

RELATIVE_CAPACITY_INCREASE

MAX_SIZE

Constructor Detail

LargeIntArray

LargeIntArray

LargeIntArray

Method Detail

getSegment

getOffset

nSegments

length

get

get

set

set

fill

fill

append

push

pop

clear

ensureCapacity

resize

shrink

size

capacity

add

subtract

multiply

divide

calcSum

calcSum

calcAverage

calcMaximum

calcMinimum

swap

mergeSort

quickSort

sort

sort

binarySearch

binarySearch

iterator

from

fromTo

updateFrom

updateFrom

copyOfRange

toArray

toArray

clone