edu.ucla.sspace.util

Class SparseLongArray

java.lang.Object

edu.ucla.sspace.util.SparseLongArray

All Implemented Interfaces:

SparseArray<Long>, SparseNumericArray<Long>, Serializable

public class SparseLongArray
extends Object
implements SparseNumericArray<Long>, Serializable

A sparse long array. This class trades increased space efficiency at the cost of decreased performance.

This class also provides additional primitive accessor methods. This allows users to invoke get and set without marshalling primitive types to their Long equivalents unnecessarily.

The get operation runs in logarithmic time. The set operation runs in consant time if setting an existing non-zero value to a non-zero value. However, if the set invocation sets a zero value to non-zero, the operation is linear with the size of the array.

Instance offer a space savings of retaining only the non-zero indices and values. For large array with only a few values set, this offers a huge savings. However, as the cardinality of the array grows in relation to its size, a dense long[] array will offer better performance in both space and time. This is especially true if the sparse array instance approaches a cardinality to size ratio of .5.

See Also:

SparseArray, Serialized Form

Constructor Summary

Constructors

Constructor and Description
SparseLongArray() Creates a sparse long array that grows to the maximum size set by Long.MAX_VALUE.
SparseLongArray(int length) Creates a sparse long array with a fixed length
SparseLongArray(long[] array) Creates a sparse array copy of the provided array, retaining only the non-zero values.

Method Summary

Methods

Modifier and Type	Method and Description
Long	add(int index, Long delta) Adds the specified value to the value at the index and stores the result (just as array[index] += delta).
long	addPrimitive(int index, long delta) Adds the specified value to the index.
int	cardinality() Returns the number of non-zero values in this sparse array
Long	divide(int index, Long value) Divides the specified value to the index by the provided value and stores the result at the index (just as array[index] /= value)
long	dividePrimitive(int index, long value) Divides the specified value to the index by the provided value and stores the result at the index (just as array[index] /= value)
Long	get(int index) Returns the value of this array at the index.
int[]	getElementIndices() Returns the indices of the array that contain non-0 values.
long	getPrimitive(int index) Retrieve the value at specified index or 0 if no value had been specified.
int	length() Returns the maximum length of this array.
Long	multiply(int index, Long value) Multiplies the value to the index by the provided value and saves the result at the index (just as array[index] *= value)
long	multiplyPrimitive(int index, long value) Multiplies the value to the index by the provided value and saves the result at the index (just as array[index] *= value)
void	set(int index, Long value) Sets the object as the value at the index.
void	setPrimitive(int index, long value) Sets the value of the index to the value using the Java primitives without auto-boxing.
<E> E[]	toArray(E[] array) Fills the provided array with the values contained in this array that fit within the length of the provided array.
long[]	toPrimitiveArray(long[] array) Sets the values of the provided array using the contents of this array.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SparseLongArray

public SparseLongArray()

Creates a sparse long array that grows to the maximum size set by Long.MAX_VALUE.

SparseLongArray

public SparseLongArray(int length)

Creates a sparse long array with a fixed length

SparseLongArray

public SparseLongArray(long[] array)

Creates a sparse array copy of the provided array, retaining only the non-zero values. The length of the provided array is used to set the maximum size of this sparse array.

Method Detail

addPrimitive

public long addPrimitive(int index,
                long delta)

Adds the specified value to the index. This call is more effecient than calling get and set.

Parameters:

index - the position in the array

delta - the change in value at the index

add

public Long add(int index,
       Long delta)

Adds the specified value to the value at the index and stores the result (just as array[index] += delta). Note that this can be used with negative delta values to achieve equivalent -= functionality.

Specified by:

add in interface SparseNumericArray<Long>

Parameters:

index - the position in the array

delta - the change in value at the index

Returns:

the new value stored at the index

cardinality

public int cardinality()

Returns the number of non-zero values in this sparse array

Specified by:

cardinality in interface SparseArray<Long>

dividePrimitive

public long dividePrimitive(int index,
                   long value)

Divides the specified value to the index by the provided value and stores the result at the index (just as array[index] /= value)

Parameters:

index - the position in the array

value - the value by which the value at the index will be divided

Returns:

the new value stored at the index

divide

public Long divide(int index,
          Long value)

Divides the specified value to the index by the provided value and stores the result at the index (just as array[index] /= value)

Specified by:

divide in interface SparseNumericArray<Long>

Parameters:

index - the position in the array

Returns:

the new value stored at the index

get

public Long get(int index)

Returns the value of this array at the index.

Specified by:

get in interface SparseArray<Long>

Parameters:

index - the position in the array

Returns:

the object at the position

getElementIndices

public int[] getElementIndices()

Returns the indices of the array that contain non-0 values.

Specified by:

getElementIndices in interface SparseArray<Long>

Returns:

the indices that contain values

getPrimitive

public long getPrimitive(int index)

Retrieve the value at specified index or 0 if no value had been specified.

Parameters:

index - the position in the array

Returns:

the primitive value at that position

Throws:

ArrayIndexOutOfBoundException - if the index is greater than the maximum length of the array.

length

public int length()

Returns the maximum length of this array.

Specified by:

length in interface SparseArray<Long>

multiplyPrimitive

public long multiplyPrimitive(int index,
                     long value)

Multiplies the value to the index by the provided value and saves the result at the index (just as array[index] *= value)

Parameters:

index - the position in the array

value - the value that will be multiplied in value at the index

Returns:

the new value stored at the index

multiply

public Long multiply(int index,
            Long value)

Multiplies the value to the index by the provided value and saves the result at the index (just as array[index] *= value)

Specified by:

multiply in interface SparseNumericArray<Long>

Parameters:

index - the position in the array

Returns:

the new value stored at the index

set

public void set(int index,
       Long value)

Sets the object as the value at the index.

Specified by:

set in interface SparseArray<Long>

Parameters:

index - an index in the array

value - the value

setPrimitive

public void setPrimitive(int index,
                long value)

Sets the value of the index to the value using the Java primitives without auto-boxing.

toArray

public <E> E[] toArray(E[] array)

Fills the provided array with the values contained in this array that fit within the length of the provided array.

Specified by:

toArray in interface SparseArray<Long>

toPrimitiveArray

public long[] toPrimitiveArray(long[] array)

Sets the values of the provided array using the contents of this array. If the provided array is longer than this array, the additional values are left unchanged.