/* T02n03 - All three of our minmax algorithms from class in one program. The
 * purpose of this program is to demonstrate code profiling.  The following
 * information applies to Java 1.5.  Profiling was broken in 1.4, but worked
 * pretty well in 1.3.  I think this gives an indication of the priority
 * Sun assigns to this feature of their version of Java.
 *
 * The Sun JDK comes with a couple of forms of code profiling, neither of
 * which work particularly well.  THe profilers work by 'sampling' the
 * execution of the program.  That is, they wake up every so often, see
 * where within the code execution is happening, and make a note to that
 * effect.  At the end of execution, a report is generated with a total
 * of the notes.  If this sampling occurs frequently enough, we get a
 * good view of where the program is spending its time.  Otherwise, the
 * results are hard to interpret.  The sampling rate on the supplied
 * profilers is quite coarse, meaning that these profilers are of any
 * use only on long executions.  Long executions can often be forced by
 * increasing problem sizes, but that often means remembering to 
 * increase the amount of memory available to java.
 *
 * Still game to try?  OK.  Here are your two choices:
 *
 * (1)  -Xprof is a flag you supply on the command line to activate the
 *      Xprof profiler.  At the end of execution, a report is displayed.
 *
 *      Example:  $ java -Xprof -Xmx1024m T02n03 40000000 
 *
 *      The -Xmx1024m increasing the available heap space for this
 *      execution to 1 gigabyte, which is sufficient to permit the
 *      execution to complete on this much data.
 *
 * (2)  -agentlib:hprof=cpu=samples,interval=1,depth=1
 *
 *      hprof is more configurable (obviously) that Xprof, but this
 *      doesn't solve the granularity problem.
 *
 *      Example:  Same as above, just put the -agentlib stuff in place
 *                of -Xprof.
 *
 *      After execution, a file named java.hprof.txt is be created.  The
 *      profiling results are at the end.
 *
 * There are many commercial profilers available, though most of them
 * focus on memory profiling instead of CPU profiling.  I don't know of
 * a free CPU profiler that works outside of a particular IDE.
 */

import java.io.*;

public class T02n03
{

    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 void main (String[] args)
    {
        double mean;
        double [] list;
        int    listSize = 0;
        MinMax minMax = new MinMax();

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

        list = new double [listSize];

        createList(list,listSize);

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

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

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

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

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;
    }
}