/* File: ClickWinner.java - April 2017 */
package l14;
import java.util.Random;

/**
* Determine the winner from an array of integer where each indexes chance
* of winning should be proportional to the value of the array at that index.
*
* Includes a main method for doing some testing. In this case we want to find
* a winner multiple times so the method we use is to store the cumulative 
* sums of the entries array and search for the first index larger than some
* appropriately chosen random number.
*
* @author Michael Albert
*
*/

public class ClickWinner{

  public static final Random R = new Random();
  
  
  public static int[] cumulativeSums(int[] entries) {
    int[] sums = new int[entries.length];
    int total = 0;
    for(int i = 0; i < sums.length; i++) {
      total += entries[i];
      sums[i] = total;
    }
    return sums;
  }
  
  public static int findWinner(int[] sums) {
    int r = R.nextInt(sums[sums.length-1]);
    return findFirstIndexLarger(r, sums);
  }
  
  public static int findFirstIndexLarger(int value, int[] sums) {
    if (sums[0] > value) return 0; // Special case
    return findFirstIndexLarger(value, sums, 0, sums.length);
  }

  // Use a simple modification of binary search to find the first
  // index in an (increasing) array where the entry is larger than
  // a target value (no exception handling included).
  public static int findFirstIndexLarger(int value, int[] sums, 
                                            int low, int high) {
    if (high - low <= 1) { // Recursive base case
      return high;
    }
    int mid = (high + low)/2;
    if (sums[mid] <= value) {
      return findFirstIndexLarger(value, sums, mid, high);
    } else {
      return findFirstIndexLarger(value, sums, low, mid);
    }
  }
  
  public static void main(String[] args) {
  
    int[] entries = new int[10];
    for(int i = 0; i < entries.length; i++) {
      entries[i] = R.nextInt(100);
    }
    int[] sums = cumulativeSums(entries);
    int total = sums[sums.length-1];
    int[] winners = new int[entries.length];
    // Run the competition the same number of times as the total number
    // of entries. If things are correct the number of times each index
    // wins should be roughly equal to the value of the entry at that
    // index.
    for(int run = 0; run < total; run++) {
      winners[findWinner(sums)]++;
    }
    for(int i = 0; i < entries.length; i++) {
      System.out.println((entries[i] + "     ").substring(0,4) + winners[i]);
    }
  
    // Now do it 1000 times as often as the total number of entries
    System.out.println();
    for(int run = 0; run < 1000*total; run++) {
      winners[findWinner(sums)]++;
    }
    for(int i = 0; i < entries.length; i++) {
      System.out.println((entries[i] + "     ").substring(0,4) +     
                                                    (winners[i]/1000.0));
    }
  }

}