import java.util.*;

public class CRSTester {

	/*takes an n by n matrix A, stored in the standard 2-dimensional float array,
	  and a size-n vector x and returns the product A*x.*/
	public static float[] uncompressedProduct(float[][] A, float[] x){
		//get the matrix size
		int mSize = A.length;

		float[] product = new float[mSize];

		for( int i = 0; i < mSize; i++){
			for (int j = 0; j < mSize; j++){
				product[i] += A[i][j] * x[j];
			}
		}

		return product;
	}

	/*takes a probability p and a positive integer n and returns an n by n matrix.
	Each entry in the array is non-zero with probability p.*/
	public static float[][] generateMatrix(float p, int n){

		//allocate the matrix.
		float[][] matrix =  new float[n][n];

		Random random = new Random();

		//generate the entries of the matrix
		for( int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(random.nextFloat() <= p)
					matrix[i][j] = 1 + random.nextFloat(); //in the range 1 through 2
				else
					matrix[i][j] = 0;
			}
		}

		return matrix;

	}//end of generateMatrix

	/*takes a positive integer n and returns a size-n vector.
	 The entries of the vector are at random in the range 0 through 1.*/
	public static float[] generateVector(int n){
		//allocate the vector
		float[] vector = new float[n];

		Random myRandom = new Random();

		//generate the vector
		for(int i = 0; i < n; i++){
			vector[i] = myRandom.nextFloat();
		}

		return vector;

	} //end of generateVector


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

		CRS crs;

		float[] vec, prod;
		float[][] mat;
		int n;

		long startTime, endTime, totalTime;

		float p = (float)(0.01); //set p = 1/100

		n = 500;
		while( n<=4000){

			mat = CRSTester.generateMatrix(p, n);
			vec = CRSTester.generateVector(n);
			crs = new CRS(mat);

			System.out.println("The matrix size=" + n);

			//repeat the experiment 10 times and take the average.
			totalTime = 0;
			for(int j= 0; j<10; j++){
				startTime = System.currentTimeMillis();

				prod = CRSTester.uncompressedProduct(mat, vec);

				endTime  = System.currentTimeMillis();

				//System.out.println("uncompressedProduct time = " + (endTime - startTime) );
				totalTime += (endTime - startTime);
			}
			System.out.println(" the average running time of uncompressedProduct = " + (totalTime)/10);

			//repeat the experiment 10 times and take the average.
			totalTime = 0;
			for(int j=0; j<10; j++){
				startTime = System.currentTimeMillis();

				prod = crs.product(vec);

				endTime  = System.currentTimeMillis();

				//System.out.println(", product time = " + (endTime - startTime) );
				totalTime += (endTime - startTime);
			}
			System.out.println("the average running time of product = " + (totalTime)/10 );

			
			if(n<1000){
				n += 100;
			}
			else
				n+= 1000;

		} //end of while loop

	} //end of main

}//end of class