import java.util.concurrent.RecursiveTask;


public class Histogram extends RecursiveTask<int[]> {

	private int[] input;
	private int low;
	private int high;
	static final int SEQUENTIAL_CUTOFF=1000;
	
	/**
	 * @param input
	 * @param low
	 * @param high
	 */
	public Histogram(int[] input, int low, int high) {
		this.input = input;
		this.low = low;
		this.high = high;
	}

	@Override
	protected int[] compute() {
		int[] results = new int[10];
		if(high - low <= SEQUENTIAL_CUTOFF) {
			for(int i = low; i < high; i++ ) 
				results[input[i] / 10] += 1; // increment count of correct bin
		} else {
			int mid = (low+high)/2;
			Histogram left = new Histogram(input,low, mid); // count up the left side of the input array
			Histogram right = new Histogram(input, mid, high); // count up right side of input array
			left.fork();
			int[] rightResults = right.compute();
			int[] leftResults = left.join();
			// leftResults and rightResults are both 10 long, we need to add up their counts
			for(int i = 0; i < 10; i++) {
				results[i] = rightResults[i] + leftResults[i];
			}
			
		}
		return results;
	}

}