edu.ucla.sspace.vector

Class AmortizedSparseVector

java.lang.Object

edu.ucla.sspace.vector.AmortizedSparseVector

All Implemented Interfaces:

DoubleVector, SparseDoubleVector, SparseVector<Double>, Vector<Double>, Serializable

public class AmortizedSparseVector
extends Object
implements SparseDoubleVector, Serializable

An implementation of a sparse vector based on the Yale Sparse matrix format. This class offers better access for modification efficiency over SparseVector at the expense of increased memory usage, for certain usage patterns. Only non-zero values in the vector are stored in an ArrayList, which tracks both the index of the value, and the value itself. Lookups for all indices are O(log n). Writes to already existing indices are O(log n). Writes to non-existing indices are dependent on the insertion time of a ArrayList, but are at a minimum O(log n).

Author:

Keith Stevens

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
AmortizedSparseVector() An AmortizedSparseVector with Integer.MAX_VALUE dimensions.
AmortizedSparseVector(int length) Create AmortizedSparseVector of size @{code length}, which initially has all dimensions set to 0.

Method Summary

Methods

Modifier and Type	Method and Description
double	add(int index, double delta) Changes the value in this vector by a specified amount (optional operation).
double	get(int index) Returns the value of this vector at the given index.
int[]	getNonZeroIndices() Returns all the indices whose values are non-zero
Double	getValue(int index) Return the value of the vector at the given index as a Number.
int	length() Return the size of the Vector.
double	magnitude() Returns the magnitude of this vector
void	set(double[] value) Note that any values which are 0 are left out of the vector.
void	set(int index, double value) Sets the length in this vector (optional operation).
void	set(int index, Number value) Set the value in the vector (optional operation).
double[]	toArray() Returns a double array representing this vector.

Methods inherited from class java.lang.Object

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

Methods inherited from interface edu.ucla.sspace.vector.Vector

equals, hashCode

Constructor Detail

AmortizedSparseVector

public AmortizedSparseVector()

An AmortizedSparseVector with Integer.MAX_VALUE dimensions.

AmortizedSparseVector

public AmortizedSparseVector(int length)

Create AmortizedSparseVector of size @{code length}, which initially has all dimensions set to 0.

Parameters:

length - The maximum length of the Vector.

Method Detail

add

public double add(int index,
         double delta)

Changes the value in this vector by a specified amount (optional operation). If there is not a value set at index, delta should be set to the actual value.

Specified by:

add in interface DoubleVector

Parameters:

index - index to change.

delta - the amount to change by.

Returns:

the resulting value at the index

get

public double get(int index)

Returns the value of this vector at the given index.

Specified by:

get in interface DoubleVector

Parameters:

index - index to retrieve.

Returns:

value at index.

getValue

public Double getValue(int index)

Return the value of the vector at the given index as a Number.

Specified by:

getValue in interface DoubleVector

Specified by:

getValue in interface Vector<Double>

Parameters:

index - index to retrieve.

Returns:

value at index.

magnitude

public double magnitude()

Returns the magnitude of this vector

Specified by:

magnitude in interface Vector<Double>

set

public void set(int index,
       double value)

Sets the length in this vector (optional operation). All read operations, and writes to indices which already exist are of time O(log n). Writers to new indices are of time O(log n).

Specified by:

set in interface DoubleVector

Parameters:

index - index to set.

value - value to set in the vector.

set

public void set(int index,
       Number value)

Set the value in the vector (optional operation).

Specified by:

set in interface Vector<Double>

Parameters:

index - index to set.

value - value to set in the vector.

set

public void set(double[] value)

Note that any values which are 0 are left out of the vector.

toArray

public double[] toArray()

Returns a double array representing this vector. The returned array will be "safe" in that no changes to the array will be reflected in the vector, and likewise for changes to to the vector. The caller is thus free to modify the returned array.

Specified by:

toArray in interface DoubleVector

Returns:

a double array of this vector.

getNonZeroIndices

public int[] getNonZeroIndices()

Returns all the indices whose values are non-zero

Specified by:

getNonZeroIndices in interface SparseVector<Double>

length

public int length()

Return the size of the Vector.

Specified by:

length in interface Vector<Double>

Returns:

size of the vector.