/**
 * This is the code used at the end of my Chapel Tutorial.  This file header is written using JavaDoc because I don't know any better.  Edited lines have been commented out in case this is helpful to people having trouble with any step of the tutorial.
 * @author Kyle Burke (paithanq@gmail.com)
 */

 
use Time;
use Random;

//var maximum: real = 0.0;
var maximum = 0.0;
writeln("maximum: ", maximum);

/*
var n: int = 10;
var realArray: [0..(n-1)] real;
realArray[0] = 1.0;
realArray[1] = 2.0;
realArray[2] = 3.0;
realArray[3] = 4.0;
realArray[4] = 5.0;
realArray[5] = 4.0;
realArray[6] = 3.0;
realArray[7] = 2.0;
realArray[8] = 1.0;
realArray[9] = 0.0;
writeln("realArray: ", realArray);
*/

//var n = 10;
//var n = 500;
config const n = 5000000;
var realArray : [0..n-1] real;
var randomStream = new RandomStream(SeedGenerator.currentTime);
randomStream.fillRandom(realArray);
writeln("Array initialized.");




//writeln("realArray: ", realArray);

/*
for realNumber in realArray {
    if (realNumber > maximum) {
        maximum = realNumber;
    }
}
writeln("Max: ", maximum);
*/

/*
proc findMax(array) {
    var arrayMax = array[0];
    for number in array {
        if (number > arrayMax) {
            arrayMax = number;
        }
    }
    return arrayMax;
}*/

//writeln("Max of realArray is: ", findMax(realArray));

/*
var timer: Timer;
timer.start();
writeln("Max of realArray is: ", findMax(realArray));
timer.stop();
writeln("That took ", timer.elapsed(), " seconds.");
*/


var timer: Timer;
timer.start();
maximum = findMax(realArray);
timer.stop();
writeln("Max of realArray is: ", maximum);
writeln("That took ", timer.elapsed(), " seconds.");


//proc findMaxInRange(array, lower, upper) {
/*proc findMaxInRange(array, in lower, upper) {
    var arrayMax = array[lower];
    while (lower <= upper) {
        if (array[lower] > arrayMax) {
            arrayMax = array[lower];
        }
        lower += 1;
    }
    return arrayMax;
}*/

/*
proc findMaxInRange(array, lower, upper) {
    var i = lower;
    var arrayMax = array[i];
    while (i <= upper) {
        if (array[i] > arrayMax) {
            arrayMax = array[i];
        }
        i += 1;
    }
    return arrayMax;
}
*/

/*
proc findMax(array) {
    var middle = array.numElements/2;
    var lowerMax, upperMax: real;
    lowerMax = findMaxInRange(array, 0, middle);
    upperMax = findMaxInRange(array, middle+1, array.numElements - 1);
    //if (lowerMax > upperMax) { return lowerMax; }
    //return upperMax;
    return max(lowerMax, upperMax);
}
*/

proc findMaxInRange(array, lower, upper) {
    var i = lower;
    var arrayMax = array[i];
    while (i <= upper) {
        if (array[i] > arrayMax) {
            arrayMax = array[i];
        }
        i += 1;
    }
    return arrayMax;
}

proc findMax(array) {
    var middle = array.numElements/2;
    var lowerMax, upperMax: real;
    cobegin ref(lowerMax, upperMax) {
        lowerMax = findMaxInRange(array, 0, middle);
        upperMax = findMaxInRange(array, middle+1, array.numElements - 1);
    }
    return max(lowerMax, upperMax);
}

proc fastFindMaxInRange(array, lower, upper) : real {
    if (lower == upper) { return array[lower]; }
    var lowerMax, upperMax: real;
    var middle = ((upper - lower) / 2) + lower;
    cobegin ref(lowerMax, upperMax) {
        lowerMax = fastFindMaxInRange(array, lower, middle);
        upperMax = fastFindMaxInRange(array, middle + 1, upper);
    }
    return max(lowerMax, upperMax);
}

proc serialFindMax(array) {
    var max: real;
    max = findMaxInRange(array, 0, array.numElements - 1);
    return max;
}

proc parallelFindMax(array) {
    return fastFindMaxInRange(array, 0, array.numElements - 1);
}

var serialMax: real;
var serialSeconds: real;

timer.clear();
timer.start();
serialMax = serialFindMax(realArray);
timer.stop();
serialSeconds = timer.elapsed();
writeln("SERIAL test: found the max to be ", serialMax, " in ", serialSeconds, " seconds.");
timer.clear();

var speedup : real;

/*
timer.start();
var parallelMax = parallelFindMax(realArray);
timer.stop();
var parallelSeconds = timer.elapsed();
timer.clear();
writeln("PARALLEL test: found the max to be ", parallelMax, " in ", parallelSeconds, " seconds.");
speedup = serialSeconds / parallelSeconds;
if (speedup > 1) {
    writeln("    The parallel trial achieved a ", speedup, "x speedup over the serial!");
} else {
    writeln("    No speedup attained!");
}
*/

proc hybridFindMaxInRange(array, lower, upper, numTasks) : real {
    if (lower == upper) { return array[lower]; }
    if (numTasks == 1) {
        return findMaxInRange(array, lower, upper);
    }
    var lowerMax, upperMax: real;
    var middle = ((upper - lower) / 2) + lower;
    var lowerTasks : int = numTasks / 2;
    var upperTasks = numTasks - lowerTasks;
    cobegin ref(lowerMax, upperMax) {
        lowerMax = hybridFindMaxInRange(array, lower, middle, lowerTasks);
        upperMax = hybridFindMaxInRange(array, middle+1, upper, upperTasks);
    }
    return max(lowerMax, upperMax);
}

proc hybridFindMax(array, numTasks) {
    return hybridFindMaxInRange(array, 0, array.numElements-1, numTasks);
}

config const threads = 8;

timer.clear();
timer.start();
var hybridMax = hybridFindMax(realArray, threads);
timer.stop();
var hybridSeconds = timer.elapsed();
timer.clear();
writeln("HYBRID test: found the max to be ", hybridMax, " in ", hybridSeconds, " seconds.");
speedup = serialSeconds / hybridSeconds;
if (speedup > 1) {
    writeln("    The hybrid achieved a ", speedup, "x speedup over the serial trial!");
} else {
    writeln("    No speedup attained.");
}

timer.clear();
timer.start();
var reduceMax = max reduce realArray;
timer.stop();
var reduceSeconds = timer.elapsed();
writeln("REDUCE test: found the max to be ", reduceMax, " in ", reduceSeconds, " seconds.");
speedup = serialSeconds / reduceSeconds;
if (speedup > 1) {
    writeln("    The reduce call achieved a ", speedup, "x speedup over the serial trial!");
} else {
    writeln("    No speedup attained.");
}