import java.util.Random;
import java.util.concurrent.CyclicBarrier;

/**
 * b.1, b.2, b.3 og b.4 er implementert, kommenter ut den oppgaven du
 * vil teste i metoden FindMaxWorkerThread.run()
 *
 * Vi skal n? parallellisere problemet med ? finne det st?rste
 * elementet i en heltallsarray a[] av lengde n - og skrive: 'int
 * finnMax(int a[]) {..};
 *
 * Arrayen vi skal f?rst lage en slik array med tilfeldig innhold med
 * klassen Random i pakken:
 *    java.util
 * hvor man nytter metoden nextInt(n) for ? trekke elementene i a[].
 *
 * Vi skal nedenfor teste denne for n = 100, 1000, ..., 10 millioner.
 */
public class Uke1_Oppg2 {
    public static final int TEN_MILLIONS = 10000000;
    private final int numThreads;
    private int[] randomNumbers;
    private int globalMax;

    public static void main(String[] args) {
        // Number of threads default to available processors
        int localNumThreads = Runtime.getRuntime().availableProcessors();

        if (args.length == 1) {
            // Optional argument to specify number of threads
            localNumThreads = Integer.parseInt(args[0]);
        }

        Uke1_Oppg2 o = new Uke1_Oppg2(TEN_MILLIONS, localNumThreads);

        for (int i = 100; i <= TEN_MILLIONS; i *= 10) {
            o.sequentialFindMax(i);
            o.globalMax = 0;
            o.parallelFindMax(i);
            System.out.println();
        }
    }

    Uke1_Oppg2(int numElements, int numThreads) {
        this.numThreads = numThreads;

        randomNumbers = new int[numElements];
        Random r = new Random();

        // Populate the array with random numbers
        for (int i = 0; i < numElements; i++) {
            randomNumbers[i] = r.nextInt(Integer.MAX_VALUE);
        }
    }


    public void printAnswerAndTime(String type, int elements, double time, int number) {
        System.out.printf("%10s (%8d numbers checked) in time %5.2f, max number %4d\n",
                          type, elements, time, number);
    }

    /**
     * Sekvensiell l?sning for ? finne st?rste nummer in en array.
     */
    public void sequentialFindMax(int numElements) {
        long start = System.nanoTime();

        int localMax = randomNumbers[0];
        for (int i = 1; i < numElements; i++) {
            if (randomNumbers[i] > localMax) {
                localMax = randomNumbers[i];
            }
        }

        long end = System.nanoTime();
        printAnswerAndTime("sequential", numElements, (end-start)/1000000.0, localMax);
    }

    /**
     * Fordel elementene til tr?dene og starte dem opp.
     */
    public void parallelFindMax(int numElements) {
        long start = System.nanoTime();
        final int elementsPerThread = numElements / numThreads;
        final int remainderForLastThread = numElements % numThreads;

        CyclicBarrier barrier = new CyclicBarrier(numThreads + 1); // +1 for main

        for (int i = 0; i < numThreads; i++) {
            int startRange = i * elementsPerThread;
            int endRange = (i+1) * elementsPerThread;

            // Last element takes the remainder
            if (i == numThreads - 1)
                endRange += remainderForLastThread;

            new Thread(new FindMaxWorkerThread(i, numElements, startRange, endRange, barrier)).start();
        }

        try { // Wait for all threads to finish
            barrier.await();
        } catch (Exception e) {
            return;
        }

        long end = System.nanoTime();
        printAnswerAndTime("parallel", numElements, (end-start)/1000000.0, globalMax);
    }

    /**
     * Oppdaterer globalMax om det er funnet ny st?rste. Denne er
     * synkronisert, s? om flere tr?der kaller p? denne tr?den vil de
     * bli plassert i en k? f?r de f?r l?sen.
     *
     * @param possibleMax
     */
    public synchronized void synchronizedGlobalMax(int possibleMax) {
        if (possibleMax > globalMax) {
            globalMax = possibleMax;
        }
    }


    class FindMaxWorkerThread implements Runnable {
        private final int fromIndex, toIndex;
        private final int threadId;
        private final int numElements;
        private int localMax;
        private CyclicBarrier barrier;

        FindMaxWorkerThread(int threadId, int numElements, int fromIndex,
                            int toIndex, CyclicBarrier barrier) {
            this.fromIndex = fromIndex;
            this.numElements = numElements;
            this.toIndex = toIndex;
            this.barrier = barrier;
            this.threadId = threadId;
        }

        /**
         * Avkommenter den metoden du ?nsker ? teste
         *
         * b_1_3(): Oppgave b.1 og b.3
         * b_2_3(): Oppgave b.2 og b.3
         * b_1_4(): Oppgave b.1 og b.4
         * b_2_4(): Oppgave b.2 og b.4
         */
        public void run() {
            // Using synchronizedGlobalMax() for every element:
            //b_1_3(); // Threads pick numbers from a range
            //b_2_3(); // Threads pick numbers spread

            // Using synchronizedGlobalMax() for localMax only:
            b_1_4(); // Threads pick numbers from a range
            //b_2_4(); // Threads pick numbers spread

            try { // Wait for all threads to finish
                barrier.await();
            } catch (Exception e) {
                return;
            }
        }

        /**
         * Bruker en synchronized metode som alle tr?dene kaller for
         * hvert element de har, og som oppdaterer globalMax hvis det
         * nye elementet er st?rre enn gammel verdi av globalMax
         *
         * Elementene plukkes ut i en sammehengende f?lge,
         * f.eks. tr?d 0 har elementene "0,1,2" og tr?d 1 har
         * elementene "3,4,5"
         */
        public void b_1_3() {
            for (int i = fromIndex; i < toIndex; i++) {
                synchronizedGlobalMax(randomNumbers[i]);
            }
        }

        /**
         * Samme som b_1_3, men elementene plukkes p? f?lgende m?te:
         *
         * Deretter deler vi arrayen a[] slik at tr?d 0 tester
         * element: 0, k, 2k, 3k,..osv. Tr?d 1 tester element
         * nr. 1, k+1, 2k+1, .... Tr?d 2 tester element 2, k+2, 2k+2,..
         *
         * OBS: Denne originale oppgaven hadde en skrivefeil, dette er
         * den oppdaterte og korrekte versjonen.
         *
         * numThreads = k
         */
        public void b_2_3() {
            int elementIndex = threadId;
            int threadCounter = 1;

            // Only go as long as the index is lower than number of
            // elements to inspect
            while (elementIndex < numElements) {
                synchronizedGlobalMax(randomNumbers[elementIndex]);

                elementIndex = (threadCounter * numThreads) + threadId;
                threadCounter++;
            }
        }

        /**
         * 4 La alle tr?dene ha hver sin variabel localMax som de
         * bruker til ? finne max i sin del av arrayen. Tilslutt
         * kaller hver tr?d da bare en gang p? en synchronized metode
         * (samme for ? sette golbalMax i b.3) som da finner ut
         * hvilken av tr?denes lokale max som var st?rst.
         *
         * Elementene plukkes ut i en sammehengende f?lge,
         * f.eks. tr?d 0 har elementene "0,1,2" og tr?d 1 har
         * elementene "3,4,5"
         */
        public void b_1_4() {
            for (int i = fromIndex; i < toIndex; i++) {
                if (randomNumbers[i] > localMax) {
                    localMax = randomNumbers[i];
                }
            }

            synchronizedGlobalMax(localMax);
        }

        /**
         * Samme som b_1_4, men elementene plukkes p? f?lgende m?te:
         *
         * Deretter deler vi arrayen a[] slik at tr?d 0 tester
         * element: 0, k, 2k, 3k,..osv. Tr?d 1 tester element
         * nr. 1, k+1, 2k+1, .... Tr?d 2 tester element 2, k+2, 2k+2,..
         *
         * OBS: Denne originale oppgaven hadde en skrivefeil, dette er
         * den oppdaterte og korrekte versjonen.
         *
         * numThreads = k
         */
        public void b_2_4() {
            int elementIndex = threadId;
            int threadCounter = 1;

            while (elementIndex < numElements) {
                if (randomNumbers[elementIndex] > localMax) {
                    localMax = randomNumbers[elementIndex];
                }

                elementIndex = (threadCounter * numThreads) + threadId;
                threadCounter++;
            }

            synchronizedGlobalMax(localMax);
        }
    }
}