import java.util.concurrent.*;
import java.util.*;

/*
This program takes an array of elements in the range of 0-99 (inclusive).
It outputs how many occurrences were in 0-9, 10-19, 20-29, etc.
*/

public class Histogram extends RecursiveTask<int[]>
{
	static final ForkJoinPool fjPool=new ForkJoinPool();
	
	int[] array; //the input data; NOT the output data - that gets returned each time
	int lo,hi;
	static final int SEQUENTIAL_CUTOFF=1000;
	
	public Histogram(int[] arr,int l,int h)
	{ array=arr; lo=l; hi=h; }
	
	public int[] compute()
	{
		if(hi-lo<=SEQUENTIAL_CUTOFF)
		{
			int[] output=new int[10];
			for(int i=lo;i<hi;i++) output[array[i]/10]++; //increment the corresponding bucket
			return output;
		}
		else
		{
			int mid=(lo+hi)/2;
			Histogram left=new Histogram(array,lo,mid);
			Histogram right=new Histogram(array,mid,hi);
			left.fork();
			int[] rightOutput=right.compute();
			int[] leftOutput=left.join();
			for(int i=0;i<leftOutput.length;i++) leftOutput[i]+=rightOutput[i];
			return leftOutput;
		}
	}
	
	public static void main(String[] args)
	{
		Random r=new Random();
		int arrSize=100000000;
		int[] arr=new int[arrSize];
		for(int i=0;i<arrSize;i++) arr[i]=r.nextInt(100);
		
		int[] output=fjPool.invoke(new Histogram(arr,0,arrSize));
		System.out.println("Results:");
		for(int i=0;i<output.length;i++) System.out.println("Index "+i+": "+output[i]);
	}
}