org.openimaj.util.array

Class SparseBinSearchShortArray

java.lang.Object

org.openimaj.util.array.SparseShortArray

org.openimaj.util.array.SparseBinSearchShortArray

All Implemented Interfaces:

Readable, ReadableASCII, ReadableBinary, ReadWriteable, Writeable, WriteableASCII, WriteableBinary, Concatenatable<SparseShortArray,SparseShortArray>

public class SparseBinSearchShortArray
extends SparseShortArray

A Sparse array of short values implemented using a pair of sorted parallel arrays. The first array holds the indexes of the non-zero elements in ascending order; the second holds the corresponding values.

Element access has worst-case O(log n) performance. Appends (where the index being added is greater than the existing indices) has O(1) complexity. Random puts have worst case O(n + log n) complexity. Complexity for getting values by increasing index for iteration through the non-zero values is O(1).

In summary, this implementation has good access performance, and is fast for appending values, but slow for putting at random indices. It is is optimal for a scenario where you first create the sparse array and put values in order of increasing indices, and later use the array mostly for reading.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk)

See Also:

"http://stackoverflow.com/questions/1880804/java-time-efficient-sparse-1d-array-double"

Nested Class Summary

Nested classes/interfaces inherited from class org.openimaj.util.array.SparseShortArray

SparseShortArray.DualEntry, SparseShortArray.Entry

Field Summary

Fields

Modifier and Type	Field and Description
protected int[]	keys
protected int	used
protected short[]	values

Fields inherited from class org.openimaj.util.array.SparseShortArray

DEFAULT_CAPACITY, length

Constructor Summary

Constructors

Constructor and Description
SparseBinSearchShortArray(int length) Construct the array with the given length
SparseBinSearchShortArray(int length, float density) Construct the array with the given length and expected density
SparseBinSearchShortArray(int length, int capacity) Construct the array with the given length and capacity for non-zero elements
SparseBinSearchShortArray(int length, int used, int[] keys, short[] values) Generate a new SparseBinSearchShortArray wrapper which works around an existing array of keys and values
SparseBinSearchShortArray(short[] values) Construct from an existing array of values

Method Summary

Modifier and Type	Method and Description
void	compact() Compact the space being used by the array if possible.
SparseShortArray	copy() Deep copy the array.
Iterable<SparseShortArray.Entry>	entries() Provide an iterator over the non-zero values.
boolean	equals(Object obj)
short	get(int key) Get the value at the given index.
int	hashCode()
short	increment(int key, short value) Increment the value at the given index.
int[]	indices()
boolean	isUsed(int key) Check whether the given index is used (i.e.
SparseShortArray	reverse() Reverse the elements, returning this.
short	set(int key, short value) Set the value at the given index.
Iterable<SparseShortArray.DualEntry>	unionEntries(SparseBinSearchShortArray otherArray) Provide an iterator over the union of values present in both this array and another array.
Iterable<SparseShortArray.DualEntry>	unionEntries(SparseShortArray otherArray) Provide an iterator over the union of values present in both this array and another array.
int	used()
short[]	values()

Methods inherited from class org.openimaj.util.array.SparseShortArray

add, addInplace, asciiHeader, binaryHeader, concatenate, concatenate, concatenateArrays, density, dotProduct, intersectEntries, length, maxIndex, maxValue, minIndex, minValue, multiply, multiplyInplace, readASCII, readBinary, setLength, size, subtract, subtractInplace, sumValues, sumValuesSquared, toArray, toArray, writeASCII, writeBinary

Methods inherited from class java.lang.Object

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

Field Detail

keys

protected int[] keys

values

protected short[] values

used

protected int used

Constructor Detail

SparseBinSearchShortArray

public SparseBinSearchShortArray(short[] values)

Construct from an existing array of values

Parameters:

values - the values

SparseBinSearchShortArray

public SparseBinSearchShortArray(int length,
                                 int used,
                                 int[] keys,
                                 short[] values)

Generate a new SparseBinSearchShortArray wrapper which works around an existing array of keys and values

Parameters:

length -

used -

keys -

values -

SparseBinSearchShortArray

public SparseBinSearchShortArray(int length)

Construct the array with the given length

Parameters:

length - the length

SparseBinSearchShortArray

public SparseBinSearchShortArray(int length,
                                 int capacity)

Construct the array with the given length and capacity for non-zero elements

Parameters:

length - the length

capacity - the capacity

SparseBinSearchShortArray

public SparseBinSearchShortArray(int length,
                                 float density)

Construct the array with the given length and expected density

Parameters:

length - the length

density - the density

Method Detail

indices

public int[] indices()

Specified by:

indices in class SparseShortArray

Returns:

the indices of the non-zero valued entries of the array.

values

public short[] values()

Specified by:

values in class SparseShortArray

Returns:

the packed non-zero valued entries of the array.

unionEntries

public Iterable<SparseShortArray.DualEntry> unionEntries(SparseShortArray otherArray)

Description copied from class: SparseShortArray

Provide an iterator over the union of values present in both this array and another array. Values where both arrays are zero are skipped.

Note: the SparseShortArray.DualEntry returned by the iterator is always the same object. In addition, the iterator cannot affect the value of anything in the array (i.e. changing anything in the SparseShortArray.DualEntry has no effect on the actual array).

Overrides:

unionEntries in class SparseShortArray

Parameters:

otherArray - the second array

Returns:

an iterator over the non-zero values.

unionEntries

public Iterable<SparseShortArray.DualEntry> unionEntries(SparseBinSearchShortArray otherArray)

Provide an iterator over the union of values present in both this array and another array. Values where both arrays are zero are skipped.

Note: the SparseShortArray.DualEntry returned by the iterator is always the same object. In addition, the iterator cannot affect the value of anything in the array (i.e. changing anything in the SparseShortArray.DualEntry has no effect on the actual array).

Parameters:

otherArray - the second array

Returns:

an iterator over the non-zero values.

entries

public Iterable<SparseShortArray.Entry> entries()

Description copied from class: SparseShortArray

Provide an iterator over the non-zero values.

Note: the SparseShortArray.Entry returned by the iterator is always the same object. In addition, the iterator cannot affect the value of anything in the array (i.e. changing anything in the SparseShortArray.Entry has no effect on the actual array).

Specified by:

entries in class SparseShortArray

Returns:

an iterator over the non-zero values.

equals

public boolean equals(Object obj)

Overrides:

equals in class Object

get

public short get(int key)

Description copied from class: SparseShortArray

Get the value at the given index.

Specified by:

get in class SparseShortArray

Parameters:

key - the index

Returns:

the value at the index.

hashCode

public int hashCode()

Overrides:

hashCode in class Object

isUsed

public boolean isUsed(int key)

Description copied from class: SparseShortArray

Check whether the given index is used (i.e. has a non-zero value)

Specified by:

isUsed in class SparseShortArray

Parameters:

key - the index

Returns:

true if not used; false otherwise.

set

public short set(int key,
                 short value)

Description copied from class: SparseShortArray

Set the value at the given index.

Specified by:

set in class SparseShortArray

Parameters:

key - the index.

value - the value to set.

Returns:

the value

increment

public short increment(int key,
                       short value)

Description copied from class: SparseShortArray

Increment the value at the given index.

Specified by:

increment in class SparseShortArray

Parameters:

key - the index

value - the amount to increment by.

Returns:

the new value

used

public int used()

Specified by:

used in class SparseShortArray

Returns:

the number of non-zero entries in the array

compact

public void compact()

Description copied from class: SparseShortArray

Compact the space being used by the array if possible.

Specified by:

compact in class SparseShortArray

copy

public SparseShortArray copy()

Description copied from class: SparseShortArray

Deep copy the array.

Specified by:

copy in class SparseShortArray

Returns:

a deep copy of the array

reverse

public SparseShortArray reverse()

Description copied from class: SparseShortArray

Reverse the elements, returning this.

Specified by:

reverse in class SparseShortArray

Returns:

this array