/**
 * Copyright (c) 2011, The University of Southampton and the individual contributors.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 *   *  Redistributions of source code must retain the above copyright notice,
 *      this list of conditions and the following disclaimer.
 *
 *   *  Redistributions in binary form must reproduce the above copyright notice,
 *      this list of conditions and the following disclaimer in the documentation
 *      and/or other materials provided with the distribution.
 *
 *   *  Neither the name of the University of Southampton nor the names of its
 *      contributors may be used to endorse or promote products derived from this
 *      software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.openimaj.ml.clustering.rac;

import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import org.apache.commons.math.FunctionEvaluationException;
import org.apache.commons.math.MaxIterationsExceededException;
import org.apache.commons.math.analysis.UnivariateRealFunction;
import org.apache.commons.math.analysis.solvers.BisectionSolver;
import org.openimaj.citation.annotation.Reference;
import org.openimaj.citation.annotation.ReferenceType;
import org.openimaj.data.DataSource;
import org.openimaj.data.RandomData;
import org.openimaj.ml.clustering.CentroidsProvider;
import org.openimaj.ml.clustering.IndexClusters;
import org.openimaj.ml.clustering.SpatialClusterer;
import org.openimaj.ml.clustering.SpatialClusters;
import org.openimaj.ml.clustering.assignment.HardAssigner;
import org.openimaj.util.pair.IntFloatPair;

/**
 * An implementation of the RAC algorithm proposed by <a
 * href="http://eprints.ecs.soton.ac.uk/21401/">Ramanan and Niranjan</a>.
 * <p>
 * During training, data points are selected at random. The first data point is
 * chosen as a centroid. Every following data point is set as a new centroid if
 * it is outside the threshold of all current centroids. In this way it is
 * difficult to guarantee number of clusters so a minimisation function is
 * provided to allow a close estimate of the required threshold for a given K.
 * <p>
 * This implementation supports int[] cluster centroids.
 * <p>
 * In terms of implementation, this class is a both a clusterer, assigner and
 * the result of the clustering. This is because the RAC algorithm never ends;
 * that is to say that if a new point is being assigned through the
 * {@link HardAssigner} interface, and that point is more than the threshold
 * distance from any other centroid, then a new centroid will be created for the
 * point. If this behaviour is undesirable, the results of clustering can be
 * "frozen" by manually constructing an assigner that takes a
 * {@link CentroidsProvider} (or the centroids provided by calling
 * {@link #getCentroids()}) as an argument.
 * 
 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
 */
@Reference(
                type = ReferenceType.Inproceedings,
                author = { "Amirthalingam Ramanan", "Mahesan Niranjan" },
                title = "Resource-Allocating Codebook for Patch-based Face Recognition",
                year = "2009",
                booktitle = "IIS",
                url = "http://eprints.ecs.soton.ac.uk/21401/")
public class IntRAC
                implements
                SpatialClusters<int[]>,
                SpatialClusterer<IntRAC, int[]>,
                CentroidsProvider<int[]>,
                HardAssigner<int[], float[], IntFloatPair>
{
        private static class ClusterMinimisationFunction implements UnivariateRealFunction {
                private int[][] distances;
                private int[][] samples;
                private int nClusters;

                public ClusterMinimisationFunction(int[][] samples, int[][] distances, int nClusters) {
                        this.distances = distances;
                        this.samples = samples;
                        this.nClusters = nClusters;
                }

                @Override
                public double value(double radius) throws FunctionEvaluationException {
                        final IntRAC r = new IntRAC(radius);
                        r.train(samples, distances);
                        final int diff = this.nClusters - r.numClusters();
                        return diff;
                }
        }

        private static final String HEADER = SpatialClusters.CLUSTER_HEADER + "RAIC";

        protected ArrayList<int[]> codebook;
        protected double threshold;
        protected int nDims;
        protected static int[][] distances;
        protected long totalSamples;

        /**
         * Sets the threshold to 128
         */
        public IntRAC() {
                codebook = new ArrayList<int[]>();
                this.threshold = 128;
                this.nDims = -1;
                this.totalSamples = 0;
        }

        /**
         * Define the threshold at which point a new cluster will be made.
         * 
         * @param radiusSquared
         */
        public IntRAC(double radiusSquared) {
                this();
                this.threshold = radiusSquared;
        }

        /**
         * Iteratively select subSamples from bKeys and try to choose a threshold
         * which results in nClusters. This is provided to estimate threshold as
         * this is a very data dependant value. The threshold is found using a
         * BisectionSolver with a complete distance matrix (so make sure subSamples
         * is reasonable)
         * 
         * @param bKeys
         *            All keys to be trained against
         * @param subSamples
         *            number of subsamples to select from bKeys each iteration
         * @param nClusters
         *            number of clusters to aim for
         */
        public IntRAC(int[][] bKeys, int subSamples, int nClusters) {
                this();

                distances = new int[subSamples][subSamples];
                int j = 0;
                this.threshold = 0;
                final int thresholdIteration = 5;
                while (j++ < thresholdIteration) {
                        final int[][] randomList = new int[subSamples][];
                        final int[] randomListIndex = RandomData.getUniqueRandomInts(subSamples, 0, bKeys.length);
                        int ri = 0;
                        for (int k = 0; k < randomListIndex.length; k++)
                                randomList[ri++] = bKeys[randomListIndex[k]];
                        try {
                                this.threshold += calculateThreshold(randomList, nClusters);
                        } catch (final Exception e) {
                                this.threshold += 200000;
                        }
                        System.out.println("Current threshold: " + this.threshold / j);
                }
                this.threshold /= thresholdIteration;
        }

        @SuppressWarnings("deprecation")
        protected static double calculateThreshold(int[][] samples, int nClusters) throws MaxIterationsExceededException,
                        FunctionEvaluationException
        {
                int maxDistance = 0;
                for (int i = 0; i < samples.length; i++) {
                        for (int j = i + 1; j < samples.length; j++) {
                                distances[i][j] = distanceEuclidianSquared(samples[i], samples[j]);
                                distances[j][i] = distances[i][j];
                                if (distances[i][j] > maxDistance)
                                        maxDistance = distances[i][j];
                        }
                }
                System.out.println("Distance matrix calculated");
                final BisectionSolver b = new BisectionSolver();
                b.setAbsoluteAccuracy(100.0);
                return b.solve(100, new ClusterMinimisationFunction(samples, distances, nClusters), 0, maxDistance);
        }

        int train(int[][] samples, int[][] distances) {
                int foundLength = -1;
                final List<Integer> codebookIndex = new ArrayList<Integer>();
                for (int i = 0; i < samples.length; i++) {
                        final int[] entry = samples[i];
                        if (foundLength == -1)
                                foundLength = entry.length;

                        // all the data entries must be the same length otherwise this
                        // doesn't make sense
                        if (foundLength != entry.length) {
                                this.codebook = new ArrayList<int[]>();
                                return -1;
                        }
                        boolean found = false;
                        for (final int j : codebookIndex) {
                                if (distances[i][j] < threshold) {
                                        found = true;
                                        break;
                                }
                        }
                        if (!found) {
                                this.codebook.add(entry);
                                codebookIndex.add(i);
                        }
                }
                this.nDims = foundLength;
                return 0;
        }

        @Override
        public IntRAC cluster(int[][] data) {
                int foundLength = -1;

                for (final int[] entry : data) {
                        if (foundLength == -1)
                                foundLength = entry.length;

                        // all the data entries must be the same length otherwise this
                        // doesn't make sense
                        if (foundLength != entry.length) {
                                this.codebook = new ArrayList<int[]>();
                                throw new RuntimeException();
                        }
                        boolean found = false;
                        for (final int[] existing : this.codebook) {
                                if (distanceEuclidianSquared(entry, existing) < threshold) {
                                        found = true;
                                        break;
                                }
                        }
                        if (!found) {
                                this.codebook.add(entry);
                                if (this.codebook.size() % 1000 == 0) {
                                        System.out.println("Codebook increased to size " + this.codebook.size());
                                }
                        }
                }

                return this;
        }

        @Override
        public IntRAC cluster(DataSource<int[]> data) {
                final int[][] dataArr = new int[data.size()][data.numDimensions()];

                return cluster(dataArr);
        }

        static int distanceEuclidianSquared(int[] a, int[] b) {
                int sum = 0;
                for (int i = 0; i < a.length; i++) {
                        final int diff = a[i] - b[i];
                        sum += diff * diff;
                }
                return sum;
        }

        static int distanceEuclidianSquared(int[] a, int[] b, int threshold2) {
                int sum = 0;

                for (int i = 0; i < a.length; i++) {
                        final int diff = a[i] - b[i];
                        sum += diff * diff;
                        if (sum > threshold2)
                                return threshold2;
                }
                return sum;
        }

        @Override
        public int numClusters() {
                return this.codebook.size();
        }

        @Override
        public int numDimensions() {
                return this.nDims;
        }

        @Override
        public int[] assign(int[][] data) {
                final int[] centroids = new int[data.length];
                for (int i = 0; i < data.length; i++) {
                        final int[] entry = data[i];
                        centroids[i] = this.assign(entry);
                }
                return centroids;
        }

        @Override
        public int assign(int[] data) {
                int mindiff = -1;
                int centroid = -1;

                for (int i = 0; i < this.numClusters(); i++) {
                        final int[] centroids = this.codebook.get(i);
                        int sum = 0;
                        boolean set = true;

                        for (int j = 0; j < centroids.length; j++) {
                                final int diff = centroids[j] - data[j];
                                sum += diff * diff;
                                if (mindiff != -1 && mindiff < sum) {
                                        set = false;
                                        break; // Stop checking the distance if you
                                }
                        }

                        if (set) {
                                mindiff = sum;
                                centroid = i;
                                // if(mindiff < this.threshold){
                                // return centroid;
                                // }
                        }
                }
                return centroid;
        }

        @Override
        public String asciiHeader() {
                return "ASCII" + HEADER;
        }

        @Override
        public byte[] binaryHeader() {
                return HEADER.getBytes();
        }

        @Override
        public void readASCII(Scanner in) throws IOException {
                throw new UnsupportedOperationException("Not done!");
        }

        @Override
        public void readBinary(DataInput dis) throws IOException {
                threshold = dis.readDouble();
                nDims = dis.readInt();
                final int nClusters = dis.readInt();
                assert (threshold > 0);
                codebook = new ArrayList<int[]>();
                for (int i = 0; i < nClusters; i++) {
                        final byte[] wang = new byte[nDims];
                        dis.readFully(wang, 0, nDims);
                        final int[] cluster = new int[nDims];
                        for (int j = 0; j < nDims; j++)
                                cluster[j] = wang[j] & 0xFF;
                        codebook.add(cluster);
                }
        }

        @Override
        public void writeASCII(PrintWriter writer) throws IOException {
                writer.format("%d\n", this.threshold);
                writer.format("%d\n", this.nDims);
                writer.format("%d\n", this.numClusters());
                for (final int[] a : this.codebook) {
                        writer.format("%d,", a);
                }
        }

        @Override
        public void writeBinary(DataOutput dos) throws IOException {
                dos.writeDouble(this.threshold);
                dos.writeInt(this.nDims);
                dos.writeInt(this.numClusters());
                for (final int[] arr : this.codebook) {
                        for (final int a : arr) {
                                dos.write(a);
                        }
                }
        }

        @Override
        public int[][] getCentroids() {
                return this.codebook.toArray(new int[0][]);
        }

        @Override
        public void assignDistance(int[][] data, int[] indices, float[] distances) {
                throw new UnsupportedOperationException("Not implemented");
        }

        @Override
        public IntFloatPair assignDistance(int[] data) {
                throw new UnsupportedOperationException("Not implemented");
        }

        @Override
        public HardAssigner<int[], ?, ?> defaultHardAssigner() {
                return this;
        }

        /**
         * The number of centroids; this potentially grows as assignments are made.
         * 
         * @see org.openimaj.ml.clustering.assignment.HardAssigner#size()
         */
        @Override
        public int size() {
                return this.nDims;
        }

        @Override
        public int[][] performClustering(int[][] data) {
                return new IndexClusters(this.cluster(data).defaultHardAssigner().assign(data)).clusters();
        }
}