procope.tools
Class SparseMatrixInt

java.lang.Object
  extended by procope.tools.SparseMatrixInt

public class SparseMatrixInt
extends Object

Implementation of a matrix (2-dimensional array) of integers. Optimized for sparse matrices, i.e. only relatively few values in the matrix actually have a value.

This implementation reduces the space complexity of a matrix with n*n elements from O(n2) to O(l), where l is the number of nonzero items in the matrix.

Author:
Jan Krumsiek

Constructor Summary
SparseMatrixInt(boolean symmetrical)
          Creates an empty matrix
 
Method Summary
 void add(int x, int y, int value)
          Increase the value of a given cell.
 int get(int x, int y)
          Retrieves a value from the matrix.
 int getElementCount()
          Returns the number of elements set in this matrix
 List<Integer> getFirstIndices()
          Get the list of indices which are set as a first index
 int[] getNeighbors(int first)
          Return array of items which have a value associated with the given index
 int[] getValues(int first)
          Return array of values associated with a given index.
 int set(int x, int y, int value)
          Set a cell in the matrix to a given value.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

SparseMatrixInt

public SparseMatrixInt(boolean symmetrical)
Creates an empty matrix

Parameters:
symmetrical - if true, the values (a,b) and (b,a) will always be equal and only consume memory once
Method Detail

set

public int set(int x,
               int y,
               int value)
Set a cell in the matrix to a given value. If the cell is already set the old value will be overwritten and returned

Parameters:
x - first index
y - second index
value - value
Returns:
the old value of that cell or Integer.MIN_VALUE if the cell was not set before

get

public int get(int x,
               int y)
Retrieves a value from the matrix.

Parameters:
x - first index
y - second index
Returns:
value of that cell or Integer.MIN_VALUE if the cell is not set

add

public void add(int x,
                int y,
                int value)
Increase the value of a given cell. If the cell is not set yet, the value 0 is assumed

Parameters:
x - first index
y - second index
value - value by which the cell will be increased, can be negative

getElementCount

public int getElementCount()
Returns the number of elements set in this matrix

Returns:
number of elements in the matrix

getFirstIndices

public List<Integer> getFirstIndices()
Get the list of indices which are set as a first index

Returns:
list of indices which are used a first index

getNeighbors

public int[] getNeighbors(int first)
Return array of items which have a value associated with the given index

Parameters:
first - index for which to retrieve neighbors
Returns:
array of neighbors for the given index

getValues

public int[] getValues(int first)
Return array of values associated with a given index. Only makes sense in combination with getNeighbors(int).

Parameters:
first - index for which to retrieve values
Returns:
array of values for the given index