/**
 * BinomialCoef -- A class that represents a set of binomial coefficients of a specified
 * size.
 * 
 * Copyright (C) 2011-2015, by Joseph A. Huwaldt. All rights reserved.
 * 
 * This library is free software; you can redistribute it and/or modify it under the terms
 * of the GNU Lesser General Public License as published by the Free Software Foundation;
 * either version 2 of the License, or (at your option) any later version.
 * 
 * This library 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 Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser 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. Or visit: http://www.gnu.org/licenses/lgpl.html
 */
package jahuwaldt.js.math;

import jahuwaldt.js.util.SizedObject;
import jahuwaldt.js.util.SizedObjectFactory;
import javolution.lang.ValueType;
import javolution.text.Text;
import javolution.text.TextBuilder;

/**
 * <p>
 * This class represents an immutable matrix of binomial coefficients (n/k) defined up to
 * a specified maximum index.
 * </p>
 * <pre>
 *     ( n )      n!
 *     (   ) = --------   0 <= k <= n
 *     ( k )   k!(n-k)!
 * </pre>
 * 
 * <p> Reference: http://en.wikipedia.org/wiki/Binomial_coefficient</p>
 *
 * <p> Modified by: Joseph A. Huwaldt </p>
 * 
 * @author Joseph A. Huwaldt, Date: May 11, 2011
 * @version October 16, 2015
 */
public final class BinomialCoef implements ValueType, SizedObject {

    /**
     * The coefficients are stored in the this matrix.
     */
    private final double[][] _coefs;

    /**
     * Returns a {@link BinomialCoef} instance holding the coefficients (at least) up to
     * the specified size. The returned instance may be recycled and may contain more
     * coefficients than the requested size.
     *
     * @param size the desired size to compute coefficients for:
     *             <code>N = size - 1 ==> (N/N)</code> or <code>size = N + 1</code>.
     * @return The binomial coefficient matrix having at least specified size.
     */
    public static BinomialCoef newInstance(int size) {
        BinomialCoef M = FACTORY.object(size);
        return M;
    }

    /**
     * Return the size of the binomial coefficient matrix (the maximum binomial index
     * value: (N/N)).
     */
    @Override
    public int size() {
        return _coefs.length;
    }

    /**
     * Return the specified binomial coefficient (n / k)
     *
     * @param n The 1st index into the binomial coefficient matrix (n / k). Must be &lt;
     *          size().
     * @param k The 2nd index into the binomial coefficient matrix (n / k). Must be &lt;
     *          size().
     * @return The specified binomial coefficient as a double.
     */
    public double get(int n, int k) {
        return _coefs[n][k];
    }

    /**
     * Returns a copy of this binomial coefficient matrix
     * {@link javolution.context.AllocatorContext allocated} by the calling thread
     * (possibly on the stack).
     *
     * @return an identical and independent copy of this binomial coefficient matrix.
     */
    @Override
    public BinomialCoef copy() {
        return copyOf(this);
    }

    /**
     * Recycles a <code>BinomialCoef</code> instance immediately (on the stack when
     * executing in a StackContext).
     */
    public static void recycle(BinomialCoef instance) {
        FACTORY.recycle(instance);
    }

    /**
     * Returns the text representation of this binomial coefficient matrix.
     *
     * @return the text representation of this binomial coefficient matrix.
     */
    public Text toText() {
        TextBuilder tmp = TextBuilder.newInstance();

        tmp.append('{');
        int size = size() + 1;
        for (int i = 0; i < size; i++) {
            tmp.append('{');
            for (int j = 0; j < size; ++j) {
                tmp.append(get(i, j));
                if (j != size - 1)
                    tmp.append(", ");
            }
            tmp.append('}');
        }
        tmp.append('}');

        Text txt = tmp.toText();
        TextBuilder.recycle(tmp);
        return txt;
    }

    /**
     * Method that actually allocates a new array and fills it with binomial coefficients.
     */
    private static double[][] binomial(int size) {
        double[][] bin = new double[size][size];

        // Setup the first line
        @SuppressWarnings("MismatchedReadAndWriteOfArray")
        double[] row0 = bin[0];
        row0[0] = 1.0;
        for (int k = 1; k < size; ++k)
            row0[k] = 0.;

        // Setup the other lines
        for (int n = 0; n < size - 1; n++) {
            @SuppressWarnings("MismatchedReadAndWriteOfArray")
            double[] binnp1 = bin[n + 1];
            binnp1[0] = 1.0;
            double[] binn = bin[n];
            for (int k = 1; k < size; k++) {
                if (n + 1 < k)
                    binn[k] = 0.0;
                else
                    binnp1[k] = binn[k] + binn[k - 1];
            }
        }
        return bin;
    }

    ///////////////////////
    // Factory creation. //
    ///////////////////////
    @SuppressWarnings("unchecked")
    private static SizedObjectFactory<BinomialCoef> FACTORY = new SizedObjectFactory<BinomialCoef>() {
        @Override
        protected BinomialCoef create(int size) {
            BinomialCoef M = new BinomialCoef(size);
            return M;
        }
    };

    @SuppressWarnings("unchecked")
    private static BinomialCoef copyOf(BinomialCoef original) {
        int size = original.size();
        BinomialCoef M = BinomialCoef.newInstance(size);
        return M;
    }

    private BinomialCoef() {
        _coefs = null;
    }

    private BinomialCoef(int size) {
        _coefs = binomial(size);
    }

}