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.vector.sparse;

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

import la4j.factory.SparseFactory;
import la4j.vector.AbstractVector;
import la4j.vector.Vector;

public class SparseVector extends AbstractVector implements Vector {

	private static final int MINIMUM_SIZE = 32;
	
	private double values[];
	private int indices[];
	
	private int nonzero;
	
	public SparseVector() {
		this(0);
	}
	
	public SparseVector(int length) {
		this(length, 0);
	}
	
	public SparseVector(int length, int nonzero) {
		super(new SparseFactory());
		
		int alignedSize = Math.min(length, ((nonzero % MINIMUM_SIZE) + 1) * MINIMUM_SIZE);
		this.values = new double[alignedSize];
		this.indices = new int[alignedSize];
		this.length = length;
		this.nonzero = nonzero;
	}
	
	public SparseVector(double array[]) {
		super(new SparseFactory());

		this.length = array.length;
		this.nonzero = 0;
		
		int alignedSize = Math.min(length, ((nonzero % MINIMUM_SIZE) + 1) * MINIMUM_SIZE);
		this.values = new double[alignedSize];
		this.indices = new int[alignedSize];
		
		for (int i = 0; i < array.length; i++) {
			if (Math.abs(array[i]) > EPS) {
				
				if (values.length <= nonzero) {
					growup();
				}
				
				values[nonzero] = array[i];
				indices[nonzero] = i;
				nonzero++;
			}
		}
	}
	
	@Override
	public double get(int i) {
		
		if (i >= length || i < 0) throw new IndexOutOfBoundsException();
		
		for (int k = 0; k < nonzero; k++) {
			if (indices[k] == i) {
				return values[k];
			}
		}
		
		return 0.0;
	}

	@Override
	public void set(int i, double value) {
		
		if (i >= length || i < 0) throw new IndexOutOfBoundsException();

		for (int k = 0; k < nonzero; k++) {
			if (indices[k] == i) {
				if (Math.abs(value) > EPS) {
					values[k] = value;
					return;
				} else {
					nonzero--;
					for (int kk=k; kk < nonzero; kk++) {
						values[kk] = values[kk + 1];
						indices[kk] = indices[kk + 1];
					}
				}
			}
		}
		
		if (Math.abs(value) < EPS) return;
		
		if (values.length <= nonzero + 1) {
			growup();
		} 
		
		values[nonzero] = value;
		indices[nonzero] = i;
		nonzero++;
	}
	
	@Override
	public int nonzero() {
		return nonzero;
	}

	@Override
	public double[] toArray() {
		
		double result[] = new double[length];
		for (int i = 0; i < nonzero; i++) {
			result[indices[i]] = values[i]; 
		}
		
		return result;
	}

	@Override
	public double[] toArrayCopy() {
		return toArray();
	}
	
	@Override
	public void resize(int length) {
		
		if (length < 0) throw new IllegalArgumentException();
		
		if (length == this.length) return;
		
		if (length < this.length) {

			for (int i = 0; i < nonzero; i++) {
				if (indices[i] > length) {
					nonzero--;
				}
			}
		} 
		
		this.length = length;
	}

	@Override
	public void swap(int i, int j) {
		
		if (i >= length || i < 0 || j >= length || j < 0) throw new IndexOutOfBoundsException();
		
		if (i == j) return;
		
		int ii = -1, jj = -1;
		
		for (int k = 0; (ii == -1 || jj == -1) && k < nonzero; k++) {
			if (ii == -1 && indices[k] == i) ii = k;
			if (jj == -1 && indices[k] == j) jj = k;
		}
		
		if (ii == -1 && jj == -1) return;
		
		if (ii == -1) { 
			indices[jj] = i;
			return;
		}
		
		if (jj == -1) {
			indices[ii] = j;
			return;
		}
		
		int s = indices[jj];
		indices[jj] = indices[ii];
		indices[ii] = s;
	}
	
	@Override
	public void writeExternal(ObjectOutput out) throws IOException {
	
		out.writeInt(length);
		out.writeInt(nonzero);
		out.writeByte(META_MARKER);

		for (int i = 0; i < nonzero; i++) {
			out.writeInt(indices[i]);
			out.writeDouble(values[i]);
			out.writeByte(ELEMENT_MARKER);
		}
	}

	@Override
	public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
		
		length = in.readInt();
		nonzero = in.readInt();
		in.readByte();

		int alignedSize = Math.min(length, ((nonzero % MINIMUM_SIZE) + 1) * MINIMUM_SIZE);
		
		values = new double[alignedSize];
		indices = new int[alignedSize];
		
		for (int i = 0; i < nonzero; i++) {
			indices[i] = in.readInt();
			values[i] = in.readDouble();
			in.readByte();
		}
	}
	
	@Override
	public Vector clone() {
		
		SparseVector dolly = (SparseVector) super.clone();
		
		dolly.indices = indices.clone();
		dolly.values = values.clone();
		
		return dolly;
	}
	
	private void growup() {
		
		int newSize = Math.min(length, (nonzero * 3) / 2 + 1);
		
		double newValues[] = new double[newSize];
		int newIndices[] = new int[newSize];
		
		System.arraycopy(values, 0, newValues, 0, nonzero);
		System.arraycopy(indices, 0, newIndices, 0, nonzero);
		
		this.values = newValues;
		this.indices = newIndices;
	}
}