/*
 * Statistics Utility Class
 * Will take a collection of numbers (that extends Number)
 *  and perform a variety of statistical functions.
 *
 * These functions include:
 *  mean
 *  median
 *  variance
 *  std deviation
 *
 * @author Doug Swain
 */

package simplestatscalculator;
import java.util.*;

/**
 *
 */
public class Statistics {
    /**
     * Calculate the mean of a set of values.
     * Collection must contain only Number values.
     *
     * @param Collection<T extends Number> values The values to base it upon.
     * @return Double The value calculated.
     */
    public static<T extends Number> Double mean(AbstractList<T> values) {
        if (values == null || values.isEmpty())
            return new Double(0.0);
        
        double sum = 0.0;

        for (T value : values) {
            sum += value.doubleValue();
        }

        return new Double(sum / values.size());
    }

    /**
     * Calculate the variance of a set of numbers.
     * Uses the mean() method to determine the difference
     *  from the mean.
     *
     * variance = (sum((x_i - mean)^2)) / value_count
     *
     * @param <T extends Number> Some form of a number to sum
     * @param Collection<T> values The values to determine the variance from.
     * @return Double The variance of the collection of values
     */
    public static<T extends Number> Double variance(AbstractList<T> values) {
        Double mean = Statistics.mean(values);

        if (mean.doubleValue() > 0.0) {
            double sum = 0.0;

            for (T value : values) {
                double difference = (value.doubleValue() - mean.doubleValue());
                sum += Math.pow(difference, 2.0);
            }

            return new Double(sum / values.size());
        } else {
            return mean;
        }
    }

    /**
     * Calculate the standard deviation of a collection of numbers.
     * Uses the variance() method defined above.
     * 
     * @param <T extends Number> Some form of a number to sum
     * @param Collection<T> values The values to determine the variance from.
     * @return Double The variance of the collection of values
     */
    public static<T extends Number> Double standardDeviation(AbstractList<T> values) {
        Double variance = Statistics.variance(values);

        if (variance.doubleValue() > 0.0) {
            return new Double(Math.sqrt(variance.doubleValue()));
        } else {
            return variance;
        }
    }

    /**
     * Determine the median of a set of numbers.
     * If the size of the collection is == 0 or collection is null,
     *  return new Double(-1.0);
     * If the size of the collection is odd,
     *  return middle-most value
     * If the size of the collection is even,
     *  return sum of middle-most values / 2.
     *
     * @param <T extends Number> Some form of a number to sum
     * @param Collection<T> values The values to determine the variance from.
     * @return Double The median of the collection of values
     */
    public static<T extends Number> T median(AbstractList<T> values) {
        if (values.size() % 2 ==0)
            return selection(values, values.size() / 2);
        else
            return selection(values, ((values.size() / 2) + 1));
    }

    /**
     * Selection algorithm. Used as a way to select a value from a certain area
     *  of a collection.
     *
     * For example, to select the median, provide the size of the collection/2
     *  as the selectionIndex.
     * To select the smallest number, provide 1.
     * To select the largest number, provide the size of the collection.
     *
     * @param <T extends Number> Some form of a number to sum
     * @param Collection<T> values The values to determine the variance from.
     * @param int selectionIndex The index from which to select from.
     * @return Double The median of the collection of values
     */
    private static<T extends Number> T selection(AbstractList<T> values,
                                                      int selectionIndex) {
        Random randomGenerator = new Random();
        int randomSelection = randomGenerator.nextInt(values.size());
        T pivotPoint = values.get(randomSelection);

        ArrayList<ArrayList<T>> split = splitValues(values, pivotPoint);

        if (selectionIndex <= split.get(0).size())
            return selection(split.get(0), selectionIndex);
        else if (split.get(0).size() < selectionIndex &&
                 selectionIndex <= (split.get(0).size() + split.get(1).size()))
            return split.get(1).get(split.get(1).size() - 1);
        else
            return selection(split.get(2), selectionIndex - split.get(0).size() -
                                            split.get(1).size());
    }

    /**
     * Divide a list into three parts depending upon the pivot value:
     *  a) Values < pivotValue
     *  b) Values == pivotValue
     *  c) Values > pivotValue
     * 
     * @param <T extends Number> Some form of a number to sum
     * @param Collection<T> values The values to split into multiple collections
     * @param int pivotValue The value which should be split upon.
     * @return AbstractList<AbstractList<T>> Collection of the split lists
     */
    private static<T extends Number> ArrayList<ArrayList<T>>
                                           splitValues(AbstractList<T> values,
                                                       T pivotValue) {
        ArrayList<ArrayList<T>> splitValues = new ArrayList<ArrayList<T>>();
        splitValues.add(new ArrayList<T>());
        splitValues.add(new ArrayList<T>());
        splitValues.add(new ArrayList<T>());
        
        double pivot = pivotValue.doubleValue();

        for (T value : values) {
            double currentValue = value.doubleValue();

            if (currentValue < pivot)
                splitValues.get(0).add(value);
            else if (currentValue == pivot)
                splitValues.get(1).add(value);
            else
                splitValues.get(2).add(value);
        }

        return splitValues;
    }
}