///////////////////////////////////////////////////////////////////////////////
// For information as to what this class does, see the Javadoc, below.       //
// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,       //
// 2007, 2008, 2009, 2010, 2014, 2015 by Peter Spirtes, Richard Scheines, Joseph   //
// Ramsey, and Clark Glymour.                                                //
//                                                                           //
// This program is free software; you can redistribute it and/or modify      //
// it under the terms of the GNU General Public License as published by      //
// the Free Software Foundation; either version 2 of the License, or         //
// (at your option) any later version.                                       //
//                                                                           //
// This program is distributed in the hope that it will be useful,           //
// but WITHOUT ANY WARRANTY; without even the implied warranty of            //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             //
// GNU General Public License for more details.                              //
//                                                                           //
// You should have received a copy of the GNU General Public License         //
// along with this program; if not, write to the Free Software               //
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA //
///////////////////////////////////////////////////////////////////////////////

package edu.cmu.tetrad.util;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Calculates a ROC curve and AUC (area under curve) for a list of scored cases
 * whose inclusion in category C is known.
 *
 * @author Joseph Ramsey and Frank Wimberly
 */
public class RocCalculator {
    public static final int ASCENDING = 0;
    private static final int DESCENDING = 1;

    private int direction = ASCENDING;

    private int[][] points;
    private ScoreCategoryPair[] scoreCatPairs;

    /**
     * Constructs a calculator using the parameter information below.
     *
     * @param scores     The scores to be plotted.
     * @param inCategory Whether each score is in the category in question or
     *                   not. Must be an array of the same length as scores.
     * @param direction  Either RocCalculator.ASCENDING or RocCalculator.DESCENDING.
     */
    public RocCalculator(double[] scores, boolean[] inCategory, int direction) {
        if (scores == null) {
            throw new NullPointerException();
        }

        if (inCategory == null) {
            throw new NullPointerException();
        }

        if (scores.length != inCategory.length) {
            throw new IllegalArgumentException("Scores array must have same " +
                    "number of items as inCategory array.");
        }

        if (direction != ASCENDING && direction != DESCENDING) {
            throw new IllegalArgumentException(
                    "Direction must be ASCENDING or " + "DESCENDING.");
        }

        this.direction = direction;

        //Create an array of scores and inCategory pairs for sorting.
        this.scoreCatPairs = new ScoreCategoryPair[scores.length];

        for (int i = 0; i < scores.length; i++) {
            scoreCatPairs[i] = new ScoreCategoryPair(scores[i], inCategory[i]);
        }
    }

    /**
     * Calculates the area under the ROC curve using a very clever Ramsey idea.
     *
     * @return the area under the ROC curve (AUC).
     */
    public double getAuc() {

        if (points == null) {
            getUnscaledRocPlot();
        }

        int lastPoint = points.length - 1;

        int height = 0;
        int area = 0;

        for (int i = 1; i < points.length; i++) {

            if (points[i][1] > points[i - 1][1]) {
                height += 1;
            } else if (points[i][0] > points[i - 1][0]) {
                area += height;
            }
        }

        return ((double) area) / (points[lastPoint][0] * points[lastPoint][1]);
    }

    /**
     * Produces a doubly subscripted array of ints representing the points in
     * the unscaled ROC Curve plot.  The first subscript of the array is the
     * index of the point and the second subscript is 0 for x values and 1 for y
     * values.
     */
    private void getUnscaledRocPlot() {
        sortCases();

        OrderedPairInt p0 = new OrderedPairInt(0, 0);
        OrderedPairInt pPrime;
        List<OrderedPairInt> plot = new LinkedList<>();
        plot.add(p0);
        int numPairs = scoreCatPairs.length;

        for (int i = numPairs - 1; i >= 0; i--) {
            ScoreCategoryPair tPrime = scoreCatPairs[i];

            if (tPrime.getHasProperty()) {
                pPrime = new OrderedPairInt(p0.getFirst(), p0.getSecond() + 1);
                plot.add(pPrime);
                p0 = pPrime;
            } else {
                pPrime = new OrderedPairInt(p0.getFirst() + 1, p0.getSecond());
                plot.add(pPrime);
                p0 = pPrime;
            }
        }

        this.points = new int[plot.size()][2];

        for (int i = 0; i < plot.size(); i++) {
            OrderedPairInt point = plot.get(i);
            points[i][0] = point.getFirst();
            points[i][1] = point.getSecond();
        }
    }

    public double[][] getScaledRocPlot() {
        if (points == null) {
            getUnscaledRocPlot();
        }

        int numPoints = points.length;
        double[][] pointsDouble = new double[numPoints][2];

        for (int i = 0; i < numPoints; i++) {
            //System.out.println(plot[i][0] + " " + plot[i][1]);
            pointsDouble[i][0] = ((double) points[i][0]) /
                    ((double) points[numPoints - 1][0]);
            pointsDouble[i][1] = ((double) points[i][1]) /
                    ((double) points[numPoints - 1][1]);
        }

        return pointsDouble;
    }

    private void sortCases() {
        //Sort the score-category pairs.  They will be in increasing order by score.
        Arrays.sort(scoreCatPairs);

        //If a higher score implies a lower probability that the case has property P
        //reverse the order.
        if (direction == DESCENDING) {
            int numPairs = scoreCatPairs.length;
            ScoreCategoryPair[] scpRev = new ScoreCategoryPair[numPairs];

            for (int i = 0; i < numPairs; i++) {
                scpRev[i] = scoreCatPairs[numPairs - i - 1];
            }

            System.arraycopy(scpRev, 0, scoreCatPairs, 0, numPairs);
        }
    }

    private static class OrderedPairInt {
        private int first;
        private int second;

        public OrderedPairInt(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public int getFirst() {
            return first;
        }

        public void setFirst(int first) {
            this.first = first;
        }

        public int getSecond() {
            return second;
        }

        public void setSecond(int second) {
            this.second = second;
        }
    }

    private static class ScoreCategoryPair implements Comparable {
        private final double score;
        private final boolean hasProperty;

        public ScoreCategoryPair(double score, boolean hasProperty) {

            this.score = score;
            this.hasProperty = hasProperty;

        }

        public double getScore() {
            return score;
        }

        public boolean getHasProperty() {
            return hasProperty;
        }

        public int compareTo(Object other) {
            if (getScore() < ((ScoreCategoryPair) other).getScore()) {
                return -1;
            } else if (getScore() == ((ScoreCategoryPair) other).getScore()) {
                return 0;
            } else {
                return 1;
            }
        }
    }
}





