la4j - Linear Algebra for Java

/*
 * Copyright 2011, Vladimir Kostyukov
 * 
 * This file is part of la4j project (http://la4j.googlecode.com)
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * You may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 *      
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package la4j.matrix.sparse;

import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;

import la4j.factory.Factory;
import la4j.factory.SparseFactory;
import la4j.matrix.AbstractMatrix;
import la4j.matrix.Matrix;
import la4j.vector.Vector;

public class SparseMatrix extends AbstractMatrix implements Matrix {

	private static final int MINIMUM_SIZE = 32;
	
	private static final long serialVersionUID = 1L;
	
	private double values[];
	private int columnIndices[];
	private int rowPointers[];
	
	private int nonzero;

	public SparseMatrix() {
		this(0, 0);
	}

	public SparseMatrix(int rows, int columns) {
		this(rows, columns, 0);
	}
	
	public SparseMatrix(double array[][]) {
		this(array.length, array[0].length, 0);
		
		for (int i = 0; i < rows; i++) {
			rowPointers[i] = nonzero;
			for (int j = 0; j < columns; j++) {
				if (Math.abs(array[i][j]) > EPS) {
					
					if (values.length < nonzero + 1) {
						growup();
					}
					
					values[nonzero] = array[i][j];
					columnIndices[nonzero] = j;
					nonzero++;
				}
			}
		}
		
		rowPointers[rows] = nonzero;
	}
	
	public SparseMatrix(int rows, int columns, int nonzero) {
		super(new SparseFactory());

		this.rows = rows;
		this.columns = columns;
		this.nonzero = 0;
		
		int alignedSize = Math.min(rows * columns, ((nonzero % MINIMUM_SIZE) + 1) * MINIMUM_SIZE);

		this.values = new double[alignedSize];
		this.columnIndices = new int[alignedSize];
		this.rowPointers = new int[rows + 1];
	}
	

	@Override
	public double get(int i, int j) {
		
		if (i >= rows || i < 0 || j >= columns || j < 0) throw new IndexOutOfBoundsException();

		for(int ii = rowPointers[i]; ii < rowPointers[i + 1]; ii++) {
			if (columnIndices[ii] == j) {
				return values[ii];
			}
		}
		
		return 0.0;
	}

	@Override
	public void set(int i, int j, double value) {

		if (i >= rows || i < 0 || j >= columns || j < 0) throw new IndexOutOfBoundsException();

		for(int ii = rowPointers[i]; ii < rowPointers[i + 1]; ii++) {
			if (columnIndices[ii] == j) {
				values[ii] = value;
				return;
			}
		}
		
		if (Math.abs(value) < EPS) return;
		
		if (values.length < nonzero + 1) {
			growup();
		}
		
		int position = rowPointers[i];
		while (position < rowPointers[i + 1] && j >= columnIndices[position]) position++;
		
				
		for (int k = nonzero; k > position; k--) {
			values[k] = values[k - 1];
			columnIndices[k] = columnIndices[k - 1];
		}

		values[position] = value;
		columnIndices[position] = j;
		
		for (int k = i + 1; k < rows + 1; k++) {
			rowPointers[k]++; 
		}
		
		nonzero++;
	}
	
	@Override
	public void resize(int rows, int columns) {
		
		if (rows < 0 || columns < 0) throw new IllegalArgumentException();
		
		if (this.rows == rows && this.columns == columns) return;
		
		if (this.rows >= rows && this.columns >= columns) {
			
			int position = 0;
			for (int k = 0; k < rowPointers[rows]; k++) {
				if (columns > columnIndices[k]) {
					values[position++] = values[k];				
				}
			}

			nonzero = rowPointers[rows];
			
		} else if (this.rows < rows) {
			
			int newRowPointers[] = new int[rows + 1];
			System.arraycopy(rowPointers, 0, newRowPointers, 0, rowPointers.length);
			
			for (int i = this.rows; i < rows; i++) {
				newRowPointers[i] = nonzero;
			}
			
			this.rowPointers = newRowPointers;
		}
		
		this.rows = rows;
		this.columns = columns;
	}

	@Override
	public double[][] toArray() {

		double result[][] = new double[rows][columns];

		int k = 0, i = 0;
		while (k < nonzero) {
			for (int j = rowPointers[i]; j < rowPointers[i + 1]; j++, k++) {
				result[i][columnIndices[j]] = values[j];
			}
			i++;
		}

		return result;
	}

	@Override
	public double[][] toArrayCopy() {
		return toArray();
	}

	@Override
	public void swapRows(int i, int j) {
		
		// TODO: optimize it
		
		if (i >= rows || i < 0 || j >= rows || j < 0) throw new IndexOutOfBoundsException();
		
		if (i == j) return;

		Vector ii = getRow(i);
		Vector jj = getRow(j);
		
		setRow(i, jj);
		setRow(j, ii);
	}
	
	@Override
	public void swapColumns(int i, int j) {
		
		// TODO: optimize it
		
		if (i >= columns || i < 0 || j >= columns || j < 0) throw new IndexOutOfBoundsException();
		
		if (i == j) return;
		
		Vector ii = getColumn(i);
		Vector jj = getColumn(j);
		
		setColumn(i, jj);
		setColumn(j, ii);
	}		
	
	@Override
	public int nonzero() {
		return nonzero;
	}

	@Override
	public Matrix transpose(Factory factory) {
		
		if (factory == null) throw new NullPointerException();

		Matrix result = factory.createMatrix(columns, rows);
		
		int k = 0, i = 0;
		while (k < nonzero) {
			for (int j = rowPointers[i]; j < rowPointers[i + 1]; j++, k++) {
				result.set(columnIndices[j], i, values[j]);
			}
			i++;
		}
		
		return result;
	}

	@Override
	public Vector getRow(int i) {
		
		if (i >= rows || i < 0) throw new IndexOutOfBoundsException();
		
		Vector result = factory.createVector(columns);
		
		for(int ii = rowPointers[i]; ii < rowPointers[i + 1]; ii++) {
			result.set(columnIndices[ii], values[ii]);
		}
		
		return result;
	}

	@Override
	public Vector getColumn(int i) {
		
		if (i >= columns || i < 0) throw new IndexOutOfBoundsException();
		
		Vector result = factory.createVector(rows);
		
		int k = 0, ii = 0;
		while (k < nonzero) {
			for (int jj = rowPointers[ii]; jj < rowPointers[ii + 1]; jj++, k++) {
				if (columnIndices[jj] == i) {
					result.set(ii, values[jj]);
				}
			}
			ii++;
		}
		
		return result;
	}

	@Override
	public void setColumn(int i, Vector column) {

		if (i >= columns || i < 0) throw new IndexOutOfBoundsException();

		for (int ii = 0; ii < column.length(); ii++) {
			
			int position = rowPointers[ii], limit = rowPointers[ii + 1];
			while (position < limit && columnIndices[position] < i) position++;
			
			if (Math.abs(column.get(ii)) > EPS) {

				if (columnIndices[position] != i) {

					if (values.length < nonzero + 1) {
						growup();
					}
		
					for (int k = nonzero; k > position; k--) {
						values[k] = values[k - 1];
						columnIndices[k] = columnIndices[k - 1];
					}
				} 
				
				for (int k = ii + 1; k < rows + 1; k++) {
					rowPointers[k]++; 
				}
				
				values[position] = column.get(ii);
				columnIndices[position] = i;
				nonzero++;
				
			} else if (columnIndices[position] == i && position < limit) {

				for (int k = position; k < nonzero - 1; k++) {
					values[k] = values[k + 1];
					columnIndices[k] = columnIndices[k + 1];
				}
				
				for (int k = ii + 1; k < rows + 1; k++) {
					rowPointers[k]--; 
				}
				
				nonzero--;
			}
		}
	}

	@Override
	public void setRow(int i, Vector row) {
		
		// TODO: optimize it
		
		if (i >= rows || i < 0) throw new IndexOutOfBoundsException();
		
		int position = rowPointers[i], limit = rowPointers[i + 1];
		
		rowPointers[i] = limit;
		
		for (int ii = 0; ii < row.length(); ii++) {
			
			if (Math.abs(row.get(ii)) > EPS) {
				
				if (position >= limit) {

					if (values.length < nonzero + 1) {
						growup();
					}
		
					for (int k = nonzero; k > position; k--) {
						values[k] = values[k - 1];
						columnIndices[k] = columnIndices[k - 1];
					}
					
					nonzero++;

				} else {
					
					rowPointers[i]--;

				}
				
				values[position] = row.get(ii);
				columnIndices[position] = ii;
				position++;
			}
		}
		
		if (limit > position) {
			
			nonzero -= (limit - position);

			for (int k = position; k < nonzero; k++) {
				values[k] = values[k + (limit - position)];
				columnIndices[k] = columnIndices[k + (limit - position)];
			}
			
			rowPointers[i] -= (limit - position);
		}
		
		for (int k = i + 1; k < rows + 1; k++) {
			rowPointers[k] +=  (position - limit); 
		}
	}
	
	@Override
	public void writeExternal(ObjectOutput out) throws IOException {

		out.writeInt(rows);
		out.writeInt(columns);
		out.writeInt(nonzero);
		out.writeByte(META_MARKER);
		
		int k = 0, i = 0;
		while (k < nonzero) {
			for (int j = rowPointers[i]; j < rowPointers[i + 1]; j++, k++) {
				out.writeInt(i);
				out.writeInt(columnIndices[j]);
				out.writeDouble(values[j]);
				out.writeByte(ELEMENT_MARKER);
			}
			i++;
		}
	}

	@Override
	public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
		
		// TODO: make it works with non-sorted input
		
		rows = in.readInt();
		columns = in.readInt();
		nonzero = in.readInt();
		in.readByte();

		int alignedSize = Math.min(rows * columns, ((nonzero % MINIMUM_SIZE) + 1) * MINIMUM_SIZE);
		
		values = new double[alignedSize];
		columnIndices = new int[alignedSize];
		rowPointers = new int[rows + 1];
		
		for (int k = 0; k < nonzero; k++) {
			
			int i = in.readInt();
			
			columnIndices[k] = in.readInt();
			values[k] = in.readDouble();

			in.readByte();

			rowPointers[i + 1] = k + 1;
		}
	}
	
	@Override
	public Matrix clone() {

		SparseMatrix dolly = (SparseMatrix) super.clone();
		
		dolly.values = values.clone();
		dolly.columnIndices = columnIndices.clone();
		dolly.rowPointers = rowPointers.clone();

		return dolly;
	}
	
	private void growup() {

		int newSize = Math.min(rows * columns, (nonzero * 3) / 2 + 1);
		
		double newValues[] = new double[newSize];
		int newColumnIndices[] = new int[newSize];
		
		System.arraycopy(values, 0, newValues, 0, nonzero);
		System.arraycopy(columnIndices, 0, newColumnIndices, 0, nonzero);
		
		this.values = newValues;
		this.columnIndices = newColumnIndices;
	}
}