public class SparseIntArray extends Object implements SparseNumericArray<Integer>, Serializable, Iterable<IntegerEntry>
int 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 Integer 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 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 supports iterating over the non-zero indices and values in the
array via the iterator() method. The indices will be returned in
sorted order. In cases where both the values and indices are needed,
iteration will be faster, O(k), than using getElementIndices() and getPrimitive(int) together, O(k *
log(k)), where k is the number of non-zero indices. The iterator
returned by this class is not thread-safe and will not throw an
exception if the array is concurrently modified during iteration.
SparseArray,
Serialized Form| Constructor and Description |
|---|
SparseIntArray()
Creates a sparse
int array that grows to the maximum size set by
Integer.MAX_VALUE. |
SparseIntArray(int length)
Creates a sparse
int array with a fixed length |
SparseIntArray(int[] array)
Creates a sparse array copy of the provided array, retaining only the
non-zero values.
|
SparseIntArray(int[] indices,
int[] values,
int length)
Creates a sparse array using the specified indices and their
corresponding values.
|
| Modifier and Type | Method and Description |
|---|---|
Integer |
add(int index,
Integer delta)
Adds the specified value to the value at the index and stores the result
(just as
array[index] += delta). |
int |
addPrimitive(int index,
int delta)
Adds the specified value to the index.
|
int |
cardinality()
Returns the number of non-zero values in this sparse array
|
Integer |
divide(int index,
Integer value)
Divides the specified value to the index by the provided value and stores
the result at the index (just as
array[index] /= value) |
int |
dividePrimitive(int index,
int value)
Divides the specified value to the index by the provided value and stores
the result at the index (just as
array[index] /= value) |
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 |
getPrimitive(int index)
Retrieve the value at specified index or 0 if no value had been
specified.
|
Iterator<IntegerEntry> |
iterator()
Returns an iterator over the non-zero values in this array.
|
int |
length()
Returns the maximum length of this array.
|
Integer |
multiply(int index,
Integer value)
Multiplies the value to the index by the provided value and saves the
result at the index (just as
array[index] *= value) |
int |
multiplyPrimitive(int index,
int 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,
Integer value)
Sets the object as the value at the index.
|
void |
setPrimitive(int index,
int 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.
|
int[] |
toPrimitiveArray(int[] array)
Sets the values of the provided array using the contents of this array.
|
String |
toString() |
public SparseIntArray()
int array that grows to the maximum size set by
Integer.MAX_VALUE.public SparseIntArray(int length)
int array with a fixed lengthpublic SparseIntArray(int[] array)
public SparseIntArray(int[] indices,
int[] values,
int length)
indices - an sorted array of positive values representing the
non-zero indices of the arrayvalues - an array of values that correspond their respective indiceslength - the total length of the arraypublic int addPrimitive(int index,
int delta)
get and set.index - the position in the arraydelta - the change in value at the indexpublic Integer add(int index, Integer delta)
array[index] += delta). Note that this can be used with
negative delta values to achieve equivalent -=
functionality.add in interface SparseNumericArray<Integer>index - the position in the arraydelta - the change in value at the indexpublic int cardinality()
cardinality in interface SparseArray<Integer>public int dividePrimitive(int index,
int value)
array[index] /= value)index - the position in the arrayvalue - the value by which the value at the index will be dividedpublic Integer divide(int index, Integer value)
array[index] /= value)divide in interface SparseNumericArray<Integer>index - the position in the arraypublic Integer get(int index)
get in interface SparseArray<Integer>index - the position in the arraypublic int[] getElementIndices()
0 values.getElementIndices in interface SparseArray<Integer>public int getPrimitive(int index)
index - the position in the arrayArrayIndexOutOfBoundException - if the index is greater than
the maximum length of the array.public Iterator<IntegerEntry> iterator()
iterator in interface Iterable<IntegerEntry>public int length()
length in interface SparseArray<Integer>public int multiplyPrimitive(int index,
int value)
array[index] *= value)index - the position in the arrayvalue - the value that will be multiplied in value at the indexpublic Integer multiply(int index, Integer value)
array[index] *= value)multiply in interface SparseNumericArray<Integer>index - the position in the arraypublic void set(int index,
Integer value)
set in interface SparseArray<Integer>index - an index in the arrayvalue - the valuepublic void setPrimitive(int index,
int value)
value is 0, and the value at index is already zero, this will be a no-op.public <E> E[] toArray(E[] array)
toArray in interface SparseArray<Integer>public int[] toPrimitiveArray(int[] array)
Copyright © 2012. All Rights Reserved.