/**
 * <p>Title: Complexity Demo</p>
 * <p>Description: A demonstration of how complexity of algorithms affects how well they run and 
 * scale. Try to identify what kinds of algorithms are what.</p>
 * @author Arijit Sengupta
 * @version 1.0
 */
public class ComplexityDemo {
  
  Input myinput = new Input(); // The Input class - takes care of input from user
  
  // The different array sizes - the second line is for the bad algorithm :)
  int [] sizes = {10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000};
//    int [] sizes = {5, 10, 15, 20, 25, 30, 35, 40, 45};
  
  // Space for creating all the arrays - basically an array of arrays!
  int [][] arrays = new int[sizes.length][];
  
  // Some of the algorithms will be repeated to show a realistic sense of numbers
  int repeats = 1000;
  
  // The main method - this is what drives the application
  public static void main(String[] args) {
    // As we discussed, we will always create an instance and call a method.
    ComplexityDemo complexitydemo = new ComplexityDemo();
    complexitydemo.run();
  }

  // Here is the method that does the bulk of the task
  public void run() {
    int option;
    // Present with a menu
    do {
      option = menu();
      // Basically, 0 through 6 are all valid options, 7 quits, everything else is invalid.
      switch(option) {
        case 0:
        case 1: 
        case 2: 
        case 3: 
        case 4: 
        case 5: 
        case 6: doTask(option); break;
        case 7: break;
        default: System.out.println("Invalid option!");
      }
    }
    while (option != 7);
  }

  // The method that generates the "menu", asks the user for a response and returns the selected option
  public int menu() {
    System.out.println("You have the following options:\n\n");
    System.out.println("\t0. Generate arrays of random numbers");
    System.out.println("\t1. Access a random element of an array");
    System.out.println("\t2. Find the average, min and max of array elements");
    System.out.println("\t3. Sort the arrays - quick method");
    System.out.println("\t4. Sort the arrays - intelligent method");
    System.out.println("\t5. Generate all possible pairs of numbers");
    System.out.println("\t6. Generate all possible subsets of numbers");
    System.out.println("\t7. Quit");
    System.out.print("Your option: ");
    return myinput.readInt();
  }
  
  // This really is the method that breaks up the task based on the option. Probably could be
  // included with the run method, but just keeping it somewhat cleaner with the timing options
  public void doTask(int option) {
    for (int i=0; i < sizes.length; i++) {
      long startT = System.currentTimeMillis();
      switch(option) {
        case 0: generateArrays(i); break;
        case 1: randomElement(i); break;
        case 2: getStats(i); break;
        case 3: sortQuick(i); break;
        case 4: sortFast(i); break;
        case 5: genPairs(i); break;
        case 6: genSubsets(i); break;
      }
      long endT = System.currentTimeMillis();
      System.out.println(" " + (endT-startT) + " ms.");
    }
  }
  
  // Generate the arrays - could probably be done without asking, but this way
  // the user can repeat the process.
  public void generateArrays(int i) {
    System.out.print("Generating an array of size " + sizes[i] + ": ");
    System.out.flush();
    arrays[i] = new int[sizes[i]];
    for (int j = 0; j < sizes[i]; j++) {
      arrays[i][j] = (int)(Math.random()*1000);
    }
  }
  
  // First task - get a random element. To show decent times, we actually repeat this 100,000 times!
  public void randomElement(int i) {
    int result = 0;
    System.out.print("Getting a random element of size " + sizes[i] + " array: ");
    System.out.flush();
    for (int r = 0; r < repeats*100; r++) {
      int rnd = (int)(Math.random()*sizes[i]);
      result = arrays[i][rnd];
    }
    System.out.print(" (result: " + result + "): ");
  }
  
  // Generate the min, max and average. We repeat this one 2000 times!
  public void getStats(int i) {
    System.out.print("Finding min/max/avg of an array of size " + sizes[i] + ": ");
    System.out.flush();
    int min=0, max=0, sum=0;
    for (int r = 0; r < repeats*2; r++) {
      min = 1001; max = -1; sum =0;
      for (int j = 0; j < sizes[i]; j++) {
        if (arrays[i][j] < min) min = arrays[i][j];
        if (arrays[i][j] > max) max = arrays[i][j];
        sum += arrays[i][j];
      }
    }
    System.out.println("min: " + min + ", max: " + max + ", avg: " + (((float)sum)/sizes[i]));
  }
  
  // The quick and dirty bubble sort - may not even be exactly right. No repeats here.
  public void sortQuick(int i) {
    System.out.print("Sorting an array of size " + sizes[i] + " using bubblesort: ");
    System.out.flush();
    for (int j = 0; j < sizes[i]-1; j++) {
      for (int k = 0; k < sizes[i]; k++) {
        if (arrays[i][j] > arrays[i][k]) {
          int temp = arrays[i][k];
          arrays[i][k] = arrays[i][j];
          arrays[i][j] = temp;
        }
      }
    }
  }
  
  // Mergesort - this one we repeat 20 times to show some decent times in ms.
  public void sortFast(int i) {
    System.out.print("Sorting an array of size " + sizes[i] + " using mergesort: ");
    System.out.flush();
    for (int r=0; r < repeats/50; r++) {
      mergesort(i, 0, sizes[i]-1); 
    }
  }
  
  // Generate all the pairs. No repeats here.
  public void genPairs(int i) {
    System.out.print("Generating all possible pairs from an array of size " + sizes[i] + " : ");
    System.out.flush();
    long count=0;
    for (int r=0; r < repeats/500; r++) {
      count = 0;
      for (int j=0; j < sizes[i]; j++) {
        for (int k=0; k < sizes[i]; k++) {
          count++;
        }
      }
    }
    System.out.print(" " + count + " pairs.");
  }
  
  // Generate all possible subsets. Calls the recursive genSubs method.
  public void genSubsets(int i) {
    System.out.print("Generating all possible subsets from an array of size " + sizes[i] + ": ");
    System.out.flush();
    long count = genSubs(i, 0);
    System.out.print(" " + count + " subsets.");
  }
  
  // The recursive genSubs method
  public long genSubs(int i, int start) {
    if (start == sizes[i]-1) return 2;
    long count = 0;
    // First generate all subsets from start + 1
    long tempcount = genSubs(i, start+1);
    for (long j=0; j <tempcount; j++) {
      count++; // Add the current value to each of the generated subsets
    }
    // Then just add all the subsets already generated to this 
    count += tempcount;
    return count;
  }
  
  // The recursive mergesort method. 
  public void mergesort(int i, int lbound, int ubound) {
    if (lbound >=ubound) return;
    mergesort(i, lbound, (ubound+lbound)/2);
    mergesort(i, (ubound+lbound)/2+1, ubound);
    
    // merge the two sorted arrays
    int s1 = lbound, s2 = (ubound+lbound)/2+1, s3 = 0;
    int [] temparray = new int[ubound-lbound+1];
    while (s1 <=(ubound+lbound)/2 && s2 <=ubound) {
      if (arrays[i][s1] > arrays[i][s2]) {
        temparray[s3] = arrays[i][s2];
        s2++;
      }
      else {
        temparray[s3] = arrays[i][s1];
        s1++;
      }
      s3++;
    }
    for (s1=lbound; s1 <=ubound; s1++) {
      arrays[i][s1] = temparray[s1-lbound];
    }
  }
}