/* T02n05 - The same content as T02n03.java, but with 'wall-clock'
 * timing code added.
 *
 * Java was designed to be system independent.  For that reason, we
 * can't use standard Java and still access system-dependent features,
 * such as CPU timing information.  CPU timing information would tell
 * us how much time the CPU spent working on our program.
 *
 * Instead, we must live with 'wall-clock' time, which is the amount of
 * time that elapsed on the clock while the code was executing.  This
 * can vary quite a bit based on the system's load.  Thus, to get
 * reasonable comparisons, the code being compared should be executed
 * repeatedly, and at a time when the system is as lightly-loaded as possible.
 *
 * This program uses Java's System.currentTimeMillis() method to record
 * the current time before and after the calls to each of the versions of
 * the algorithm.  Java 1.5 added System.nanoTime() for programmers needing
 * finer timing granularity.
 *
 * Compare the timing results from this program's execution with the
 * profiling results from T02n03.  Are they similar?
 */

import java.io.*;

public class T02n05
{

    private static void createList(double [] list, int size)
    {
        for (int i=0; i<size; i++) {
            list[i] = Math.random() * size;
            if (size <= 5) System.out.println(" ["+i+"]="+list[i]);
        }
        if (size <= 5) System.out.println();
    }
    
    public static void minMaxV1 (double [] list, int n, MinMax minMax)
    {
        double min, max;

        min = max = list[0];

        for (int i=1; i<n; i++) {
            if (list[i] < min)
                min = list[i];
            if (list[i] > max)
                max = list[i];
        }

        minMax.setMinValue(min);
        minMax.setMaxValue(max);
    }


    public static void minMaxV2 (double [] list, int n, MinMax minMax)
    {
        double [] candidates = new double [n+1];
        int    i, 
               low = 0,
               high = n;
        double min,
               max;

        for (i=0; i<n-1; i+=2) {
            if (list[i] < list[i+1]) {
                candidates[low++] = list[i];
                candidates[high--] = list[i+1];
            } else {
                candidates[low++] = list[i+1];
                candidates[high--] = list[i];
            }
        }

                /* If there are an odd # of list items, the last item needs
                 * to be considered as both a min and a max candidate.
                 */

        if (i==n-1) {
            candidates[low++] = list[i];
            candidates[high--] = list[i];
        }

                /* Now just do the normal min search on the lower half
                 * and the max search on the upper half.
                 */

        min = candidates[0];

        for (int j=1; j<low; j++)
            if (candidates[j] < min)
                min = candidates[j];

        max = candidates[high+1];

        for (int k=high+1; k<n+1; k++)
            if (candidates[k] > max)
                max = candidates[k];

        minMax.setMinValue(min);
        minMax.setMaxValue(max);
    }


    public static void minMaxV3 (double [] list, int n, MinMax minMax)
    {
        int i;
        double min,
               max;

        min = max = list[0];

        for (i=1; i<n-1; i+=2) {
            if (list[i] < list[i+1]) {
                if (list[i] < min)
                    min = list[i];
                if (list[i+1] > max)
                    max = list[i+1];
            } else {
                if (list[i+1] < min)
                    min = list[i+1];
                if (list[i] > max)
                    max = list[i];
            }
        }

            /* If there's an extra, un-paired item left, it might
             * be the new min or the new max.
             */

        if (i==n-1) {
            if (list[i] < min)
                min = list[i];
            if (list[i] > max)
                max = list[i];
        }

        minMax.setMinValue(min);
        minMax.setMaxValue(max);
    }


    public static long startTiming ()
    {
        System.gc();
        return (System.currentTimeMillis());
    }

    public static double stopTiming (long startingTime)
    {
        long elapsedTime = System.currentTimeMillis() - startingTime;
        return (elapsedTime / 1000.0);    // return seconds
    }


    public static void main (String[] args)
    {
        double mean;
        double [] list;
        int    listSize = 0;
        long startTime;
        double seconds;
        MinMax minMax = new MinMax();


        if (args.length == 0) {
            System.out.println("Usage: java T02n05 <list size>");
            System.exit(1);
        } else {
            listSize = Integer.parseInt(args[0]);
        }

        list = new double [listSize];

        createList(list,listSize);

        System.out.println("n = " + list.length);

        startTime = startTiming();
        minMaxV1(list, list.length, minMax);
        seconds = stopTiming(startTime);
        System.out.println("minMaxV1: min = " + minMax.getMinValue() 
                         + ", max = " + minMax.getMaxValue()
                         + " in " + seconds + " seconds."); 

        startTime = startTiming();
        minMaxV2(list, list.length, minMax);
        seconds = stopTiming(startTime);
        System.out.println("minMaxV2: min = " + minMax.getMinValue() 
                         + ", max = " + minMax.getMaxValue()
                         + " in " + seconds + " seconds."); 

        startTime = startTiming();
        minMaxV3(list, list.length, minMax);
        seconds = stopTiming(startTime);
        System.out.println("minMaxV3: min = " + minMax.getMinValue() 
                         + ", max = " + minMax.getMaxValue()
                         + " in " + seconds + " seconds."); 
    }
}

class MinMax
{
    private double minimum, maximum;

    public MinMax ()
    {
        minimum = Double.POSITIVE_INFINITY;
        maximum = Double.NEGATIVE_INFINITY;
    }

    public MinMax (double minValue, double maxValue)
    {
        minimum = minValue;
        maximum = maxValue;
    }

    public double getMinValue ()
    {
        return minimum;
    }

    public double getMaxValue ()
    {
        return maximum;
    }

    public void setMinValue (double newMinValue)
    {
        minimum = newMinValue;
    }

    public void setMaxValue (double newMaxValue)
    {
        maximum = newMaxValue;
    }
}