com.almworks.integers

Class LongArray

java.lang.Object

com.almworks.integers.AbstractLongList

com.almworks.integers.AbstractWritableLongList

com.almworks.integers.LongArray

All Implemented Interfaces:

LongCollector, LongIterable, LongList, LongSizedIterable, WritableLongList, java.lang.Iterable<LongIterator>

public final class LongArray
extends AbstractWritableLongList

Nested Class Summary

Nested classes/interfaces inherited from class com.almworks.integers.AbstractWritableLongList

AbstractWritableLongList.WritableIndexIterator

Nested classes/interfaces inherited from class com.almworks.integers.AbstractLongList

AbstractLongList.IndexIterator, AbstractLongList.SubList

Nested classes/interfaces inherited from interface com.almworks.integers.LongList

LongList.Single

Nested classes/interfaces inherited from interface com.almworks.integers.LongCollector

LongCollector.Dummy

Field Summary

Fields inherited from interface com.almworks.integers.LongList

EMPTY

Fields inherited from interface com.almworks.integers.LongCollector

DUMMY

Constructor Summary

Constructors

Constructor and Description
LongArray()
LongArray(int capacity) Constructs an empty array with the specified initial capacity.
LongArray(long[] hostArray) Constructs a LongArray that is backed by hostArray See copy(long[]) }, create(long...).
LongArray(long[] hostArray, int length) Constructs a LongArray with the specified size length that is backed by hostArray See copy(long[]), create(long...).
LongArray(LongIterator iterator) Constructs a LongArray and add all elements from iterator
LongArray(LongList copyFrom) Constructs a LongArray and adds all elements from copyFrom

Method Summary

Methods

Modifier and Type	Method and Description
void	add(long value)
void	addAll(long... ints)
void	addAll(LongList list)
void	addAll(LongSet set)
int	addAllNotMore(LongIterable iterable, int maxCount) Adds elements from iterable until maxCount elements are added or iterable reaches its end.
int	addAllNotMore(LongList collection, int maxCount) Adds first maxCount elements from collection or the whole collection if it size is less than maxCount.
void	clear()
static LongArray	copy(long[] array)
static LongArray	copy(long[] array, int length)
static LongArray	copy(LongIterable iterable)
static LongArray	create(java.util.Collection<java.lang.Long> values) May be used to convert the collection of Long to native long[] array: LongArray.create(values).extractHostArray().
static LongArray	create(long... values)
void	ensureCapacity(int expectedCapacity) Increases the capacity of this LongArray instance, if necessary, to ensure that it can hold at least the number of elements specified by expectedCapacity argument.
boolean	equalOrder(long[] array)
void	expand(int index, int count) Increases the list size and shifts all values to the right of index.
long[]	extractHostArray() Extracts from this array inner buffer with long[] values and clears this array.
long	get(int index)
int	getCapacity()
int	getInsertionPoints(LongSizedIterable src, int[][] points) Finds positions for inserting elements of sorted src into this sorted unique array and writes them to points[0].
int	indexOf(long value) Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
void	insert(int index, long value)
void	insertAll(int index, LongList collection, int sourceIndex, int count)
void	insertMultiple(int index, long value, int count) Insert value count times between indices index, index + 1
protected boolean	isSorted(boolean checkUnique)
void	merge(LongList src) Merges the specified sorted unique list and this sorted unique array.
void	mergeWithSameLength(LongList src) Merges the specified sorted unique list into this sorted unique array.
void	mergeWithSmall(LongList src) Merges the specified sorted list and this sorted array into this sorted unique array.
void	mergeWithSmall(LongList src, int[][] insertionPoints)
void	removeAllAtSorted(IntIterator indices) Removes from this list all elements whose index is contained in the specified IntList indices
void	removeRange(int from, int to)
boolean	removeSorted(long value) Removes 1 times value from this sorted list, if this list contains value.
void	retain(LongList values) removes from this array all of its elements that are not contained in values
void	retainSorted(LongList values) removes from this array all of its elements that are not contained in values
void	set(int index, long value)
void	setAll(int index, LongList values, int sourceIndex, int count) Replaces the elements in this list from index to index + count with the elements from values beginning from index sourceIndex and ending with sourceIndex + count
void	setRange(int from, int to, long value)
void	shuffle(java.util.Random random) Shuffles this array using random as number generator.
void	sort(WritableLongList... sortAlso) Sorts this list using quicksort copied from Arrays.sort(int[]) then corrected
void	sortUnique() Sorts this array using Arrays.sort(int[]), removes duplicates and updates size.
void	swap(int index1, int index2)
long[]	toNativeArray(int sourceOffset, long[] dest, int destOffset, int length) Writes values to dest.

Methods inherited from class com.almworks.integers.AbstractWritableLongList

addAll, addSorted, apply, insertAll, insertAll, iterator, iterator, iterator, modCount, modified, remove, removeAll, removeAll, removeAll, removeAllSorted, removeAt, removeDuplicates, removeLast, reverse, setAll, size, update, updateSize, write

Methods inherited from class com.almworks.integers.AbstractLongList

binarySearch, binarySearch, contains, equals, equalSortedUniqueValues, get, getLast, getNextDifferentValueIndex, hashCode, isEmpty, isSorted, isSortedUnique, subList, toList, toNativeArray, toString, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface com.almworks.integers.LongList

binarySearch, binarySearch, contains, get, getNextDifferentValueIndex, isEmpty, isSorted, isSortedUnique, subList, toList, toNativeArray

Constructor Detail

LongArray

public LongArray()

LongArray

public LongArray(int capacity)

Constructs an empty array with the specified initial capacity.

LongArray

public LongArray(LongList copyFrom)

Constructs a LongArray and adds all elements from copyFrom

LongArray

public LongArray(LongIterator iterator)

Constructs a LongArray and add all elements from iterator

LongArray

public LongArray(long[] hostArray)

Constructs a LongArray that is backed by hostArray See copy(long[]) }, create(long...).

LongArray

public LongArray(long[] hostArray,
         int length)

Constructs a LongArray with the specified size length that is backed by hostArray See copy(long[]), create(long...).

Parameters:

length - size of the new array. If length >= hostArray.length new size is equal to hostArray.length otherwise equal to length.

Throws:

java.lang.IllegalArgumentException - if length < 0

Method Detail

copy

public static LongArray copy(long[] array)

Returns:

LongArray containing elements from the specified long[] array

copy

public static LongArray copy(long[] array,
             int length)

Returns:

LongArray with the specified size containing elements from the specified long[] array

copy

public static LongArray copy(@Nullable
             LongIterable iterable)

Returns:

LongArray containing elements from iterable

create

public static LongArray create(long... values)

Returns:

LongArray containing the specified elements. See LongArray(long[]), LongArray(long[], int).

create

public static LongArray create(@Nullable
               java.util.Collection<java.lang.Long> values)

May be used to convert the collection of Long to native long[] array: LongArray.create(values).extractHostArray().

Returns:

LongArray containing elements from collection values

indexOf

public int indexOf(long value)

Description copied from class: AbstractLongList

Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

Specified by:

indexOf in interface LongList

Overrides:

indexOf in class AbstractLongList

Returns:

index of first occurence of value. If not found returns negative value

get

public final long get(int index)

Returns:

the item at index. Valid value of an index is in range [0, size()). Note: May not be efficient (up to O(N)). Efficient algorithm should use iterator to iterate collection.

toNativeArray

public long[] toNativeArray(int sourceOffset,
                   long[] dest,
                   int destOffset,
                   int length)

Description copied from interface: LongList

Writes values to dest.

Specified by:

toNativeArray in interface LongList

Overrides:

toNativeArray in class AbstractLongList

Returns:

dest

ensureCapacity

public void ensureCapacity(int expectedCapacity)

Increases the capacity of this LongArray instance, if necessary, to ensure that it can hold at least the number of elements specified by expectedCapacity argument.

Parameters:

expectedCapacity - the desired minimum capacity

getCapacity

public int getCapacity()

Returns:

the capacity of this array

set

public void set(int index,
       long value)

Specified by:

set in interface WritableLongList

Overrides:

set in class AbstractWritableLongList

setRange

public void setRange(int from,
            int to,
            long value)

removeRange

public void removeRange(int from,
               int to)

clear

public void clear()

Specified by:

clear in interface WritableLongList

Overrides:

clear in class AbstractWritableLongList

insertMultiple

public void insertMultiple(int index,
                  long value,
                  int count)

Description copied from interface: WritableLongList

Insert value count times between indices index, index + 1

Specified by:

insertMultiple in interface WritableLongList

Overrides:

insertMultiple in class AbstractWritableLongList

expand

public void expand(int index,
          int count)

Description copied from interface: WritableLongList

Increases the list size and shifts all values to the right of index. The resulting "hole" in the range [index; index + count) contains undefined values.

Parameters:

index - where to insert the "hole"

count - how much size increase is needed, must be >= 0

insert

public void insert(int index,
          long value)

Specified by:

insert in interface WritableLongList

Overrides:

insert in class AbstractWritableLongList

add

public void add(long value)

Specified by:

add in interface LongCollector

Overrides:

add in class AbstractWritableLongList

insertAll

public void insertAll(int index,
             LongList collection,
             int sourceIndex,
             int count)

Specified by:

insertAll in interface WritableLongList

Overrides:

insertAll in class AbstractWritableLongList

setAll

public void setAll(int index,
          LongList values,
          int sourceIndex,
          int count)

Description copied from interface: WritableLongList

Replaces the elements in this list from index to index + count with the elements from values beginning from index sourceIndex and ending with sourceIndex + count

Specified by:

setAll in interface WritableLongList

Overrides:

setAll in class AbstractWritableLongList

swap

public void swap(int index1,
        int index2)

Specified by:

swap in interface WritableLongList

Overrides:

swap in class AbstractWritableLongList

addAll

public void addAll(long... ints)

Specified by:

addAll in interface LongCollector

Overrides:

addAll in class AbstractWritableLongList

sort

public void sort(WritableLongList... sortAlso)

Description copied from class: AbstractWritableLongList

Sorts this list using quicksort copied from Arrays.sort(int[]) then corrected

Specified by:

sort in interface WritableLongList

Overrides:

sort in class AbstractWritableLongList

Parameters:

sortAlso - lists in which the order is changed as well as this list

addAll

public void addAll(LongList list)

Specified by:

addAll in interface LongCollector

Overrides:

addAll in class AbstractWritableLongList

addAll

public void addAll(LongSet set)

isSorted

protected boolean isSorted(boolean checkUnique)

Overrides:

isSorted in class AbstractLongList

equalOrder

public boolean equalOrder(long[] array)

Returns:

true if size of this array equals to array.length and all elements in the specified array equal to corresponding elements

sortUnique

public void sortUnique()

Sorts this array using Arrays.sort(int[]), removes duplicates and updates size.

Specified by:

sortUnique in interface WritableLongList

Overrides:

sortUnique in class AbstractWritableLongList

retain

public void retain(LongList values)

removes from this array all of its elements that are not contained in values

Complexity: O((M + N) * log(M)), where N - size(), M - values.size()

retainSorted

public void retainSorted(LongList values)

removes from this array all of its elements that are not contained in values

Complexity: O(N * log(M), where N - size(), M - values.size()

Parameters:

values - sorted LongList

addAllNotMore

public int addAllNotMore(LongList collection,
                int maxCount)

Adds first maxCount elements from collection or the whole collection if it size is less than maxCount.

Returns:

number of added elements

addAllNotMore

public int addAllNotMore(LongIterable iterable,
                int maxCount)

Adds elements from iterable until maxCount elements are added or iterable reaches its end.

Returns:

number of added elements

removeSorted

public boolean removeSorted(long value)

Removes 1 times value from this sorted list, if this list contains value.
Example: ar = [0, 1, 1, 2]; ar.removeSorted(1) -> [0, 1, 2]

Returns:

true if this set contained value. Otherwise false.

See Also:

AbstractWritableLongList.removeAllSorted(long)

removeAllAtSorted

public void removeAllAtSorted(IntIterator indices)

Removes from this list all elements whose index is contained in the specified IntList indices

Unlike LongCollections.removeAllAtSorted(WritableLongList, IntList), which in case of LongArray takes O(N*M) time, this method requires just O(N + M), where N - size(), M - indices.size().

Parameters:

indices - sorted IntIterable

See Also:

LongCollections.removeAllAtSorted(WritableLongList, IntList)

extractHostArray

public long[] extractHostArray()

Extracts from this array inner buffer with long[] values and clears this array.

Returns:

long[] array with values from this array.

getInsertionPoints

public int getInsertionPoints(LongSizedIterable src,
                     int[][] points)

Finds positions for inserting elements of sorted src into this sorted unique array and writes them to points[0]. points[0][idx] will be equal to -1 if src.get(idx) is contained in this array, otherwise equal to index in this array where inserting src.get(idx) keeps this array sorted unique.
Examples:

this	src	return	points[0]
[0, 2, 4, 7, 9, 10]	[0, 4, 8, 8, 9]	1	[-1, -1, 4, -1, -1]
[0, 2, 4, 7, 9, 10]	[1, 4, 6, 6, 7, 11, 12]	4	[1, -1, 3, -1, -1, 6, 6]

Parameters:

src - sorted iterable

points - container for insertion points array, not null. If points[0] == null or points[0].length < src.size(), a new array will be allocated in points[0]. If points[0].length > src.size(), elements in points[0] beyond src.size() will be ignored.

Returns:

number of unique elements from src that are not contained in this array.

merge

public void merge(LongList src)

Merges the specified sorted unique list and this sorted unique array. Depending on size() and src.size() uses mergeWithSmall(LongList) or mergeWithSameLength(LongList).

If this array is smaller than the specified list, it will copy the specified list and merge it with existing contents using mergeWithSmall(LongList).

mergeWithSmall

public void mergeWithSmall(LongList src)

Merges the specified sorted list and this sorted array into this sorted unique array. If src is not sorted or this array is not sorted unique, result is undefined. src can contain duplicates.

If getCapacity() < src.size() + size(), will do reallocation.

Complexity: O(eps(N/T, this, src) * N + T * log(N)), where N = size() and T = src.size(). eps grows as N/T grows. eps also depends on how evenly src values are distributed in this array: it is higher when they are uniformly distributed. In the general case, if N/T > 4, then on average eps < 0.5.

Prefer to use this method over mergeWithSameLength(LongList) If src.size() is much smaller than size(). If they are close use mergeWithSameLength(LongList)

Parameters:

src - sorted list.

See Also:

merge(LongList)

mergeWithSmall

public void mergeWithSmall(LongList src,
                  int[][] insertionPoints)

Parameters:

insertionPoints - contains temporary array in the first element. If it isn't there, it will be written there

See Also:

mergeWithSmall(LongList)

mergeWithSameLength

public void mergeWithSameLength(LongList src)

Merges the specified sorted unique list into this sorted unique array. If getCapacity() < src.size() + size(), will do reallocation.
If src or this array are not sorted unique, result is undefined. Complexity: O(N + T), where N = size() and T = src.size().
Prefer to use if size() and src.size() are comparable. If src.size() is much smaller than size(), it's better to use mergeWithSmall(LongList)

Parameters:

src - sorted list of numbers (set)

shuffle

public void shuffle(java.util.Random random)

Shuffles this array using random as number generator.