JavaSparseArray

package com.example;

import java.util.Arrays;
import java.util.Iterator;

public class JavaSparseArray implements Iterable<SparseArrayTuple>, Iterator<SparseArrayTuple> {
	private int[][] Avalue;
	private int[][] Aindex;
	private int columnCount;
	
	private int currentRow;
	private int currentColumnPtrIndex;
	
	public JavaSparseArray() {
	}

	public JavaSparseArray(int[][] value, int[][] index, int columnCount) {
		this.Avalue = value;
		this.Aindex = index;
		this.columnCount = columnCount;
	}
	
	public JavaSparseArray(int rowCount) {
		this.Avalue = new int[rowCount][];
		this.Aindex = new int[rowCount][];
		this.columnCount = 0;
	}
	
	public JavaSparseArray add(JavaSparseArray B) {
		// Iterate over the array with more rows ...
		
		JavaSparseArray C = B.copy();
		
		int rowCount = this.getRowCount();

		int[][] newValue = new int[rowCount][];
		int[][] newIndex = new int[rowCount][];
		
		for (int row=0; row<rowCount; row++) {
			int filledColCount = this.Aindex[row].length;
			for (int colIndex=0; colIndex<filledColCount; colIndex++) {
				int col = this.Aindex[row][colIndex];
				int data = this.Avalue[row][colIndex];
				data += B.get(col, row);
				C.set(data, col, row);
			}
		}
		
		return C;
	}
	
	public int get(int x, int y) {
		if (y < this.Aindex.length && this.Aindex[y] != null) {
			int index = Arrays.binarySearch(this.Aindex[y], x);
			if (index >= 0) {
				return this.Avalue[y][index];
			}
		}
		return 0;
	}
	
	public void set(int val, int x, int y) {
		if (this.Aindex == null || y >= this.Aindex.length) {
			this.setSize(y+1);
		}
		if (this.Aindex[y] != null) {
			int index = Arrays.binarySearch(this.Aindex[y], x);
			if (index >= 0) {
				// the value is already there, just overwrite it
				this.Avalue[y][index] = val;
			} else {
				// the value is not yet defined in the sparse array so we need to de-define some arrays
				this.Aindex[y] = insert(this.Aindex[y], x, -index-1);
				this.Avalue[y] = insert(this.Avalue[y], val, -index-1);
			}
		} else {
			this.Aindex[y] = new int[1];
			this.Aindex[y][0] = x;

			this.Avalue[y] = new int[1];
			this.Avalue[y][0] = val;
		}
		
		if (x > this.columnCount) {
			this.columnCount = x;
		}
	}
	
	public void setSize(int rows) {
		int[][] value = new int[rows][];
		int[][] index = new int[rows][];
		for (int row=0; row<this.Aindex.length; row++) {
			if (this.Avalue[row] != null) {
				value[row] = new int[this.Avalue[row].length];
				System.arraycopy(this.Avalue[row], 0, value[row], 0, this.Avalue[row].length);
			}
			if (this.Aindex[row] != null) {
				index[row] = new int[this.Aindex[row].length];
				System.arraycopy(this.Aindex[row], 0, index[row], 0, this.Aindex[row].length);
			}
		}
	    this.Aindex = index;
	    this.Avalue = value;
	}
	
	public int getRowCount() {
		return ( this.Avalue != null ? this.Avalue.length : 0 );
	}
	
	public int getColumnCount() {
		return this.columnCount;
	}

	public String toString() {
		String s = "";
		if (this.Aindex != null) {
			for (int row=0; row<this.Aindex.length; row++) {
				int col = 0;
				s += "{ ";
				if (this.Aindex[row] != null) {
					for (int colIndex=0; colIndex<this.Aindex[row].length; colIndex++) {
						int nextCol = this.Aindex[row][colIndex];
						for (int i=col; i<nextCol; i++) {
							s += "0, ";
						}
						s += this.Avalue[row][colIndex] + ", ";
						col = nextCol+1;
					}
				}
				s += " }\n";
			}
		} else {
			s = "{ }";
		}
		return s;
	}
	
	static int[] insert(int[] a, int val, int insertIndex) {
	    // Insert the new item into sortedArray. The example here creates
	    // a new larger array to hold the new item.
	    int[] newArray = new int[a.length + 1];
	    System.arraycopy(a, 0, newArray, 0, insertIndex);
	    System.arraycopy(a, insertIndex, newArray, insertIndex+1, a.length-insertIndex);
	    newArray[insertIndex] = val;
	    return newArray;
	}
	
	public JavaSparseArray copy() {
	    // Insert the new item into sortedArray. The example here creates
	    // a new larger array to hold the new item.
		int rows = this.Avalue.length;
		int[][] value = new int[rows][];
		int[][] index = new int[rows][];
		int columnCount = this.columnCount;
		for (int row=0; row<rows; row++) {
			if (this.Avalue[row] != null) {
				value[row] = new int[this.Avalue[row].length];
				System.arraycopy(this.Avalue[row], 0, value[row], 0, this.Avalue[row].length);
			}
			if (this.Aindex[row] != null) {
				index[row] = new int[this.Aindex[row].length];
				System.arraycopy(this.Aindex[row], 0, index[row], 0, this.Aindex[row].length);
				columnCount = Math.max(index[row][index[row].length-1], columnCount);
			}
		}
	    return new JavaSparseArray(value, index, columnCount);
	}

	public int getMaxValue() {
		// TODO Auto-generated method stub
		return 5;
	}

	@Override
	public Iterator<SparseArrayTuple> iterator() {
		// find the first item to start with...
		for (int i=0; i<this.Aindex.length; i++) {
			if (this.Aindex[i] != null && this.Aindex[i].length > 0) {
				currentRow = i;
				break;
			}
		}
		currentColumnPtrIndex = 0;
		return this;
	}

	@Override
	public boolean hasNext() {
		if (this.Aindex != null) {
			// set the currentRow to the next valid row, it may be that currentRow is already valid
			int row = nextValidRow(currentRow);
			if (row == -1) {
				return false;
			} else {
				// now check that there is a valid value in that row
				if (currentColumnPtrIndex+1 < this.Aindex[row].length) { // In this case we have another value on the same row
					return true;
				} else { // In this case we need to get the next valid row that has a value in it
					row = nextValidRow(row+1);
					while (row != -1) {
						if (this.Aindex[row] != null && this.Aindex[row].length > 0) {
							return true;
						}
						row = nextValidRow(row+1);
					}
					return false;
				}
			}
		} else {
			// We have no values in the matrix
			return false;
		}
	}

	@Override
	public SparseArrayTuple next() {
		// First try to get the next item on this row...
		currentColumnPtrIndex++;
		if (currentColumnPtrIndex >= this.Aindex[currentRow].length) {
			// Since hasNext() has been called before next() while iterating, 
			// we know there is a valid row after current row
			currentRow = nextValidRow(currentRow+1);
			currentColumnPtrIndex = 0;
		}

		return new SparseArrayTuple(this.Avalue[currentRow][currentColumnPtrIndex], this.Aindex[currentRow][currentColumnPtrIndex], currentRow);
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub
		
	}
	
	public int getCurrentRow() {
		return this.currentRow;
	}
	
	public int getCurrentColumnPtrIndex() {
		return this.currentColumnPtrIndex;
	}
	
	public int nextValidRow(int row) {
		while (row < this.Aindex.length && (this.Aindex[row] == null || this.Aindex[row].length == 0)) {
			row++;
		}
		return ( row == this.Aindex.length ? -1 : row );
	}
	
	public int nextValidColumnPtrIndex(int row, int columnPtrIndex) {
		return 0;
	}
}