edu.ucla.sspace.util

Class SparseHashArray<T>

java.lang.Object

edu.ucla.sspace.util.SparseHashArray<T>

All Implemented Interfaces:

SparseArray<T>, Serializable, Iterable<ObjectEntry<T>>

public class SparseHashArray<T>
extends Object
implements SparseArray<T>, Iterable<ObjectEntry<T>>, Serializable

A sparse array backed by a HashMap. 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 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 IntegerMap, but will use significantly more space as the cardinality increases. In addition, this class will marshall primitive types into their reified object forms.

See Also:

SparseArray, IntegerMap, Serialized Form

Constructor Summary

Constructors

Constructor and Description
SparseHashArray() Creates a sparse array that grows to the maximum size set by Integer.MAX_VALUE.
SparseHashArray(int length) Creates a sparse array with a fixed length
SparseHashArray(T[] 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
T	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.
Iterator<ObjectEntry<T>>	iterator() Returns an iterator over the non-null values in this array.
int	length() Returns the maximum length of this array.
void	set(int index, T 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

SparseHashArray

public SparseHashArray()

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

SparseHashArray

public SparseHashArray(int length)

Creates a sparse array with a fixed length

SparseHashArray

public SparseHashArray(T[] 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<T>

get

public T get(int index)

Returns the value of this array at the index.

Specified by:

get in interface SparseArray<T>

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

Returns:

the indices that contain values

iterator

public Iterator<ObjectEntry<T>> iterator()

Returns an iterator over the non-null values in this array. This method makes no guarantee about the order in which the indices are returned.

Specified by:

iterator in interface Iterable<ObjectEntry<T>>

length

public int length()

Returns the maximum length of this array.

Specified by:

length in interface SparseArray<T>

set

public void set(int index,
       T value)

Sets the object as the value at the index.

Specified by:

set in interface SparseArray<T>

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