//Compressed Row Storage format for a sparse square matrix

public class CRS{

	//the values of the nonzero elements of the matrix
	float[] val;

	//the column indices of the elements in the val vector
	int[] col_idx;

	//locations in the val vector that start a row
	//the size is decided by the size of the matrix
	int[] row_ptr;

	//the number of rows of the matrix
	int mSize=0;


	//constructor that takes a sparse matrix and convert it to a CRS object
	CRS( float[][] matrix){

		int i;//row index
		int j;//column index

		int totalNonZeros;//the total number of nonzero in the matrix
		int index;

        //get the number of rows and columns
		mSize = matrix.length;
		System.out.println("the size of the matrix is:"+mSize+"X"+mSize+"\n");

		//find the number of nonzero entries in the matrix
		totalNonZeros = 0;
		for(i=0; i<mSize; i++){//each row
			for(j=0; j<mSize; j++){//each column
				if(matrix[i][j] != 0)
					totalNonZeros++;
			}
		}

		//allocate memory for val and col_idx
		val = new float[totalNonZeros];
		col_idx = new int[totalNonZeros];

		//allocate memory for row_ptr
		row_ptr = new int[mSize+1];
		row_ptr[0] = 0;
		
		//store the matrix in CRS format
		index = 0;// point to the next position in val to store the value
		for(i=0; i<mSize; i++){

			for(j=0; j<mSize; j++){
				if(matrix[i][j] != 0){
					//add the value to val
					val[index] = matrix[i][j];
					//record the column index in col_idx
					col_idx[index] = j;
					index++;
				}
			}
			//update row_ptr
			row_ptr[i+1] = index;
		}
	}

	//print the matrix in CRS format
	public void printCRS(){
		int i;

		System.out.println("print vectors used in CRS");

		System.out.println("The vector val");
		for(i=0; i<val.length; i++){
			System.out.print( val[i] + ", ");
		}
		System.out.println();

		System.out.println("The vector col_idx");
		for(i=0; i<col_idx.length; i++){
			System.out.print( col_idx[i] + ", ");
		}
		System.out.println();

		System.out.println("The vector row_ptr");
		for(i=0; i<row_ptr.length; i++){
			System.out.print(row_ptr[i]+ ", ");
		}
		System.out.println();
	}


	//print the matrix stored in CRS in a two dimensional array format
	public void printMatrix(){
		int i, j, k, zeroIndex;

		System.out.println("print the matrix in CRS format as a "+mSize+"x"+mSize+" matrix");

		//Scan the row_ptr array to find the beginning and end of row i
		for(i = 0; i < mSize; i++){

			//the column index of the element to print
			zeroIndex = 0;
			
			// Print row i: index k goes from the beginning to the end of row i	
			for(k = row_ptr[i]; k < row_ptr[i+1]; k++){
				j = col_idx[k];

				//print entries of zero values that exist between consecutive
				// non-zeroes
				while(zeroIndex < j){
					System.out.print(0.0+", ");
					zeroIndex++;
				} // end of while-loop

				//print the nonzero value
				System.out.print(val[k]+", ");

				// Prepare zeroIndex for the next sequence of zeroes
				zeroIndex++;
			} // end of for-k loop

			//print the trailing zeroes in this row
			while(zeroIndex < mSize){
				System.out.print(0.0+", ");
				zeroIndex++;
			}
	
			// Start the next line
			System.out.println();
		} // end of for-i loop

		System.out.println();

	} // end of printMatrix



	//test the program
	public static void main(String[] args){

		float[][] matrix = {{10, 0, 0, 0, -2, 0},
							{3, 9, 0, 0, 0, 3},
							{0, 7, 8, 7, 0, 0},
							{3, 0, 8, 7, 5, 0},
							{0, 8, 0, 9, 9, 13},
							{0, 4, 0, 0, 2, -1}};
		System.out.println("the original sparse matrix");
		for(int i=0; i<6; i++){
			for(int j=0; j<6; j++){
				System.out.print(matrix[i][j]+", ");
			}
			System.out.println();
		}
		System.out.println();

		CRS crs = new CRS(matrix);

		crs.printMatrix();
		crs.printCRS();

	}

}