/** COMP2009-ACE WEEK 3+4 - LAB - FORMATIVE EXERRCISE
    Title:  Analysis of Algorithms
	Author: Andrew Parkes

	This exercise is formative, so feel free to work together, but recommend to try it yourself first.
*/
import java.util.Random;
import java.lang.Math;

public class Main {

	/// used for counting primitive operations
	static int c;
	static Random rnd;

	/* Main method:  runs the experiments and prints results.

		You can (and should) change this as needed.

		E.g. You should change the maxN and maxRuns to values of your choice.
		You may well also want to do more than just report the n,c from each run.
		e.g. to collect and print more 'statistics' such as worst, best, average at each value of n.
	*/
	public static void main(String[] a){

		int maxN = 10;   // CHANGE AS NEEDED
		int numRuns = 5;  // CHANGE AS NEEDED

		rnd = new Random();

		for (int n = 1 ; n <= maxN ; n+=1 ) {
			int[] A = new int[n];
			double worst_case=0.0,best_case=Integer.MAX_VALUE,sum=0.0;
			for (int run = 0 ; run < numRuns ; run++ ) {
				// initialise A with randomised values
				randInit(A);
				// reset the counter, c, run f, and report the count
				c=0;
				int out = p(A);
				//System.out.println(n + " " + c);
				// KEEP EXTRA STATISTICS AS NEEDED
				if (c>worst_case) worst_case=c;
				if (c<best_case) best_case=c;
				sum+=c;

			}
			System.out.println(n+" "+worst_case+" "+best_case+" "+sum/numRuns);
		}
		// PROCESS/PRINT EXTRA STATISTICS AS NEEDED
	}

	/* 	This is the function 'p' that needs to be analysed.
		It works on an integer array, 'A' with n elements.
		You can think of it as a piece of 'legacy code' you are given and it is suspected to
		be causing trouble, such as making the application program to be going slow.
		You need to analyse its scaling behaviour and make other comments.
		The "c += " fragments have been added to help, but are not intnded as part of the "p()" methof itself.  However, they are part of the annotated code and do run.

		Note in particular if the increment is in the body of the loop then it will run each time the body runs, and so you should not then directly include terms to account for the "Number of passes". Hence, it is a bit differnt from the lectures.

		NOTE: Do _NOT_ take this as an example of how to write good code!
		Parts of it may be deliberately poor to illustrate useful points.

		DO NOT CHANGE THIS FUNCTION EXCEPT THE increments to the counter on the r.h.s. !!!


	// My own counting solution
		*/
	// static int p(int[] A) {
	// 	int n = A.length;                   	c += 3; // 1. obtain A from address space, 2. obtain length of A, 3. assigning length of A to n
	//     int[] B = new int[n];               	c += 3; // 1. get value of n, instantiate a new integer array with the size equal to the value of n, 3. assign it to integer array B

	// 	int sum = 0;                        	c += 1; // 1. assignment of value
	// 	int max = 0;                      		c += 1; // 1. assignment of value
	//     for (int p=0; p < n; p++) {     		c += 2*n; // 1. for loop 2. check for condition 3. run n times
	// 		int k = A[p];                   	c += 3*n; // 1. get value for p, 2. index array A with p, 3. assign to int k, n = run n times
	// 		sum += k;                     		c += 3*n; // 1. get value of k, 2. + value of k to value of sum, 3. assign total value to var sum, n = run n times
	// 		B[p] = sum;                       	c += 4*n; // 1. get value of sum, 2. get value of p, 3. index array B[] with value of p, 4. assign to B[p], n = run n times
	// 		int m = 0;                      	c += 1*n; // 1. initialize and assign m to 0
	// 		int s;            	              	c += 1*n; // 1. initialize var s
	// 		s = ( n%2 == 0 ? sum : k );         c += 0 ;
	// 		while ( s >= 2 ) {            		c += 0 ;
	// 			s /= 2;                     	c += 0 ;
	// 			m++;                        	c += 0 ;
	// 		}

	// 		if ( m > max ) {	            	c += 0 ;
	// 				max = m;               		c += 0 ;
	// 			}
	// 		}
	// 										c += 0; // for 'anything else'
	// 	A = B;                              c += 0;
	// 										c += 0; // for the 'return'
	// 	return max;
	// }

	// TSN's primitive counting solution
	// static int p(int[] A) {
	// 	int n = A.length;                   	c += 2;
	//     int[] B = new int[n];               	c += (100+2)*n;
	// 	// new is expensive (lots of operations)

	// 	int sum = 0;                        	c += 1;
	// 	int max = 0;                      		c += 1;
	//     for (int p=0; p < n; p++) {     		c += (n+1);
	// 		int k = A[p];                   	c += 3*n;
	// 		sum += k;                     		c += 2*n;
	// 		B[p] = sum;                       	c += 3*n;
	// 		int m = 0;                      	c += n;
	// 		int s;            	              	c += n;
	// 		s = ( n%2 == 0 ? sum : k );         c += 4*n ;
	// 		while ( s >= 2 ) {            		c += 2*n ;
	// 			s /= 2;                     	c += 2*n*(Math.log((double) s) / Math.log((double) 2)) ;
	// 			m++;                        	c += 2*n*(Math.log((double) s) / Math.log((double) 2)) ;
	// 		}

	// 		if ( m > max ) {	            	c += 2*n ;
	// 				max = m;               		c += n ;
	// 			}
	// 		}
	// 										c += 2*n; // for 'anything else'
	// 	A = B;                              c += 1;
	// 										c += 1; // for the 'return'
	// 	return max;
	// }

		// log and n not needed as the code already loops this function for you,
		// you dont have to account for the loops in calculating the operations
		static int p(int[] A) {
			int n = A.length;                   	c += 2;
			int[] B = new int[n];               	c += (100+2)*n;
			// new is expensive (lots of operations)

			int sum = 0;                        	c += 1;
			int max = 0;                      		c += 1;
			for (int p=0; p < n; p++) {     		c += (n+1);
				int k = A[p];                   	c += 3;
				sum += k;                     		c += 2;
				B[p] = sum;                       	c += 3;
				int m = 0;                      	c += 1;
				int s;            	              	c += 1;
				s = ( n%2 == 0 ? sum : k );         c += 4 ;
				while ( s >= 2 ) {            		c += 2 ;
					s /= 2;                     	c += 2;
					m++;                        	c += 2;
				}

				if ( m > max ) {	            	c += 2 ;
						max = m;               		c += n ;
					}
				}
												c += 2; // for 'anything else'
			A = B;                              c += 1;
												c += 1; // for the 'return'
			return max;
		}


	/* Used to initialise the array A.
	   You are expected to first do experiments using version exactly as below.
	*/
	static void randInit(int[] A) {
			int n = A.length;
			for (int i = 0 ; i < n ; i++ ) {
				A[i] = 10*n + rnd.nextInt( n );
			}
		}


	/* OPTIONAL: use these other versions in order to initialise the array, and get graphs that are more interesting.

	   Used to initialise the array A.
	   You are expected to first do experiments using version exactly as below.
	*/
	static void randInit_v2(int[] A) {
			int n = A.length;
			if (n%3 == 0) {
				for (int i = 0 ; i < n ; i++ ) {
					A[i] = 10*n + rnd.nextInt( n );
				}
			}
		}


	/* Used to initialise the array A.
	   You are expected to report results using version exactly as below.
	   DO NOT CHANGE THIS FUNCTION!!!
	   (Unless you know what you are doing, e.g. for some "side experiments"
	    used to help you understand.)
	*/
	static void randInit_v3(int[] A) {
			int n = A.length;

			if (n%3 == 0) {
				for (int i = 0 ; i < n ; i++ ) {
					A[i] = 10*n + rnd.nextInt( n );
				}
			}
			else {
				for (int i = 0 ; i < n ; i++ ) {
					A[i] = 10 + rnd.nextInt(  Math.min( n, 100)   );
				}
			}
		}

}