org.opentripplanner.common.geometry

Class SparseMatrix<T>

java.lang.Object

org.opentripplanner.common.geometry.SparseMatrix<T>

All Implemented Interfaces:

Iterable<T>

public class SparseMatrix<T>
extends Object
implements Iterable<T>

A fast sparse 2D matrix holding elements of type T. The x and y indexes into the sparse matrix are _signed_ 32-bit integers (negative indexes are allowed). Square sub-chunks of size chunkSize x chunkSize are stored in a hashmap, keyed on a combination of the x and y coordinates. Does not implement the collection interface for simplicity and speed. Not thread-safe!

Author:

laurent

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	SparseMatrix.SparseMatrixChunk A public representation of the internal structure of the sparse matrix, i.e.

Field Summary

Fields

Modifier and Type	Field and Description
int	xMax
int	xMin
int	yMax
int	yMin

Constructor Summary

Constructors

Constructor and Description
SparseMatrix(int chunkSize, int totalSize)

Method Summary

Modifier and Type	Method and Description
T	get(int x, int y)
Iterable<SparseMatrix.SparseMatrixChunk>	getChunks()
Iterator<T>	iterator()
T	put(int x, int y, T t)
int	size()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

xMin

public int xMin

xMax

public int xMax

yMin

public int yMin

yMax

public int yMax

Constructor Detail

SparseMatrix

public SparseMatrix(int chunkSize,
                    int totalSize)

Parameters:

chunkSize - Must be a power of two so chunk indexes can be determined by shifting off low order bits. Keep it small (8, 16, 32...). Chunks are square, with this many elements in each of two dimensions, so the number of elements in each chunk will be the square of this value.

totalSize - Estimated total number of elements to be stored in the matrix (actual use, not capacity).

Method Detail

get

public final T get(int x,
                   int y)

put

public final T put(int x,
                   int y,
                   T t)

size

public int size()

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Iterable<T>

getChunks

public Iterable<SparseMatrix.SparseMatrixChunk> getChunks()