edu.ucla.sspace.util

Class SparseIntHashArray

java.lang.Object

edu.ucla.sspace.util.SparseIntHashArray

All Implemented Interfaces:

SparseArray<Integer>, Serializable

public class SparseIntHashArray
extends Object
implements SparseArray<Integer>, Serializable

A sparse int array. This class offers amortized constant time access to array indices at the expense of space.

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 int[] 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.

This class offers much better performance than SparseIntArray, but will use significantly more space as the cardinality increases. In addition, this class will marshall int primitives into Integer objects.

See Also:

SparseArray, SparseIntArray, Serialized Form

Constructor Summary

Constructors

Constructor and Description
SparseIntHashArray() Creates a sparse int array that grows to the maximum size set by Integer.MAX_VALUE.
SparseIntHashArray(int length) Creates a sparse int array with a fixed length
SparseIntHashArray(int[] 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
int	cardinality() Returns the number of non-zero values in this sparse array
Integer	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.
int	length() Returns the maximum length of this array.
void	set(int index, Integer value) Sets the object as the value at the index.
<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.

Methods inherited from class java.lang.Object

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

Constructor Detail

SparseIntHashArray

public SparseIntHashArray()

Creates a sparse int array that grows to the maximum size set by Integer.MAX_VALUE.

SparseIntHashArray

public SparseIntHashArray(int length)

Creates a sparse int array with a fixed length

SparseIntHashArray

public SparseIntHashArray(int[] 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

cardinality

public int cardinality()

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

Specified by:

cardinality in interface SparseArray<Integer>

get

public Integer get(int index)

Returns the value of this array at the index.

Specified by:

get in interface SparseArray<Integer>

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<Integer>

Returns:

the indices that contain values

length

public int length()

Returns the maximum length of this array.

Specified by:

length in interface SparseArray<Integer>

set

public void set(int index,
       Integer value)

Sets the object as the value at the index.

Specified by:

set in interface SparseArray<Integer>

Parameters:

index - an index in the array

value - the value

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<Integer>