/*
 * Copyright 2006-2007 Sun Microsystems, Inc.  All Rights Reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Sun designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Sun in the LICENSE file that accompanied this code.
 *
 * This code 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
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 */

package java.awt;

import java.awt.MultipleGradientPaint.CycleMethod;
import java.awt.MultipleGradientPaint.ColorSpaceType;
import java.awt.color.ColorSpace;
import java.awt.geom.AffineTransform;
import java.awt.geom.NoninvertibleTransformException;
import java.awt.geom.Rectangle2D;
import java.awt.image.ColorModel;
import java.awt.image.DataBuffer;
import java.awt.image.DataBufferInt;
import java.awt.image.DirectColorModel;
import java.awt.image.Raster;
import java.awt.image.SinglePixelPackedSampleModel;
import java.awt.image.WritableRaster;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;
import java.util.Arrays;

/**
 * This is the superclass for all PaintContexts which use a multiple color
 * gradient to fill in their raster.  It provides the actual color
 * interpolation functionality.  Subclasses only have to deal with using
 * the gradient to fill pixels in a raster.
 *
 * @author Nicholas Talian, Vincent Hardy, Jim Graham, Jerry Evans
 */
abstract class MultipleGradientPaintContext implements PaintContext {

    /**
     * The PaintContext's ColorModel.  This is ARGB if colors are not all
     * opaque, otherwise it is RGB.
     */
    protected ColorModel model;

    /** Color model used if gradient colors are all opaque. */
    private static ColorModel xrgbmodel =
        new DirectColorModel(24, 0x00ff0000, 0x0000ff00, 0x000000ff);

    /** The cached ColorModel. */
    protected static ColorModel cachedModel;

    /** The cached raster, which is reusable among instances. */
    protected static WeakReference<Raster> cached;

    /** Raster is reused whenever possible. */
    protected Raster saved;

    /** The method to use when painting out of the gradient bounds. */
    protected CycleMethod cycleMethod;

    /** The ColorSpace in which to perform the interpolation */
    protected ColorSpaceType colorSpace;

    /** Elements of the inverse transform matrix. */
    protected float a00, a01, a10, a11, a02, a12;

    /**
     * This boolean specifies wether we are in simple lookup mode, where an
     * input value between 0 and 1 may be used to directly index into a single
     * array of gradient colors.  If this boolean value is false, then we have
     * to use a 2-step process where we have to determine which gradient array
     * we fall into, then determine the index into that array.
     */
    protected boolean isSimpleLookup;

    /**
     * Size of gradients array for scaling the 0-1 index when looking up
     * colors the fast way.
     */
    protected int fastGradientArraySize;

    /**
     * Array which contains the interpolated color values for each interval,
     * used by calculateSingleArrayGradient().  It is protected for possible
     * direct access by subclasses.
     */
    protected int[] gradient;

    /**
     * Array of gradient arrays, one array for each interval.  Used by
     * calculateMultipleArrayGradient().
     */
    private int[][] gradients;

    /** Normalized intervals array. */
    private float[] normalizedIntervals;

    /** Fractions array. */
    private float[] fractions;

    /** Used to determine if gradient colors are all opaque. */
    private int transparencyTest;

    /** Color space conversion lookup tables. */
    private static final int SRGBtoLinearRGB[] = new int[256];
    private static final int LinearRGBtoSRGB[] = new int[256];

    static {
        // build the tables
        for (int k = 0; k < 256; k++) {
            SRGBtoLinearRGB[k] = convertSRGBtoLinearRGB(k);
            LinearRGBtoSRGB[k] = convertLinearRGBtoSRGB(k);
        }
    }

    /**
     * Constant number of max colors between any 2 arbitrary colors.
     * Used for creating and indexing gradients arrays.
     */
    protected static final int GRADIENT_SIZE = 256;
    protected static final int GRADIENT_SIZE_INDEX = GRADIENT_SIZE -1;

    /**
     * Maximum length of the fast single-array.  If the estimated array size
     * is greater than this, switch over to the slow lookup method.
     * No particular reason for choosing this number, but it seems to provide
     * satisfactory performance for the common case (fast lookup).
     */
    private static final int MAX_GRADIENT_ARRAY_SIZE = 5000;

    /**
     * Constructor for MultipleGradientPaintContext superclass.
     */
    protected MultipleGradientPaintContext(MultipleGradientPaint mgp,
                                           ColorModel cm,
                                           Rectangle deviceBounds,
                                           Rectangle2D userBounds,
                                           AffineTransform t,
                                           RenderingHints hints,
                                           float[] fractions,
                                           Color[] colors,
                                           CycleMethod cycleMethod,
                                           ColorSpaceType colorSpace)
    {
        if (deviceBounds == null) {
            throw new NullPointerException("Device bounds cannot be null");
        }

        if (userBounds == null) {
            throw new NullPointerException("User bounds cannot be null");
        }

        if (t == null) {
            throw new NullPointerException("Transform cannot be null");
        }

        if (hints == null) {
            throw new NullPointerException("RenderingHints cannot be null");
        }

        // The inverse transform is needed to go from device to user space.
        // Get all the components of the inverse transform matrix.
        AffineTransform tInv;
        try {
            // the following assumes that the caller has copied the incoming
            // transform and is not concerned about it being modified
            t.invert();
            tInv = t;
        } catch (NoninvertibleTransformException e) {
            // just use identity transform in this case; better to show
            // (incorrect) results than to throw an exception and/or no-op
            tInv = new AffineTransform();
        }
        double m[] = new double[6];
        tInv.getMatrix(m);
        a00 = (float)m[0];
        a10 = (float)m[1];
        a01 = (float)m[2];
        a11 = (float)m[3];
        a02 = (float)m[4];
        a12 = (float)m[5];

        // copy some flags
        this.cycleMethod = cycleMethod;
        this.colorSpace = colorSpace;

        // we can avoid copying this array since we do not modify its values
        this.fractions = fractions;

        // note that only one of these values can ever be non-null (we either
        // store the fast gradient array or the slow one, but never both
        // at the same time)
        int[] gradient =
            (mgp.gradient != null) ? mgp.gradient.get() : null;
        int[][] gradients =
            (mgp.gradients != null) ? mgp.gradients.get() : null;

        if (gradient == null && gradients == null) {
            // we need to (re)create the appropriate values
            calculateLookupData(colors);

            // now cache the calculated values in the
            // MultipleGradientPaint instance for future use
            mgp.model               = this.model;
            mgp.normalizedIntervals = this.normalizedIntervals;
            mgp.isSimpleLookup      = this.isSimpleLookup;
            if (isSimpleLookup) {
                // only cache the fast array
                mgp.fastGradientArraySize = this.fastGradientArraySize;
                mgp.gradient = new SoftReference<int[]>(this.gradient);
            } else {
                // only cache the slow array
                mgp.gradients = new SoftReference<int[][]>(this.gradients);
            }
        } else {
            // use the values cached in the MultipleGradientPaint instance
            this.model                 = mgp.model;
            this.normalizedIntervals   = mgp.normalizedIntervals;
            this.isSimpleLookup        = mgp.isSimpleLookup;
            this.gradient              = gradient;
            this.fastGradientArraySize = mgp.fastGradientArraySize;
            this.gradients             = gradients;
        }
    }

    /**
     * This function is the meat of this class.  It calculates an array of
     * gradient colors based on an array of fractions and color values at
     * those fractions.
     */
    private void calculateLookupData(Color[] colors) {
        Color[] normalizedColors;
        if (colorSpace == ColorSpaceType.LINEAR_RGB) {
            // create a new colors array
            normalizedColors = new Color[colors.length];
            // convert the colors using the lookup table
            for (int i = 0; i < colors.length; i++) {
                int argb = colors[i].getRGB();
                int a = argb >>> 24;
                int r = SRGBtoLinearRGB[(argb >> 16) & 0xff];
                int g = SRGBtoLinearRGB[(argb >>  8) & 0xff];
                int b = SRGBtoLinearRGB[(argb      ) & 0xff];
                normalizedColors[i] = new Color(r, g, b, a);
            }
        } else {
            // we can just use this array by reference since we do not
            // modify its values in the case of SRGB
            normalizedColors = colors;
        }

        // this will store the intervals (distances) between gradient stops
        normalizedIntervals = new float[fractions.length-1];

        // convert from fractions into intervals
        for (int i = 0; i < normalizedIntervals.length; i++) {
            // interval distance is equal to the difference in positions
            normalizedIntervals[i] = this.fractions[i+1] - this.fractions[i];
        }

        // initialize to be fully opaque for ANDing with colors
        transparencyTest = 0xff000000;

        // array of interpolation arrays
        gradients = new int[normalizedIntervals.length][];

        // find smallest interval
        float Imin = 1;
        for (int i = 0; i < normalizedIntervals.length; i++) {
            Imin = (Imin > normalizedIntervals[i]) ?
                normalizedIntervals[i] : Imin;
        }

        // Estimate the size of the entire gradients array.
        // This is to prevent a tiny interval from causing the size of array
        // to explode.  If the estimated size is too large, break to using
        // separate arrays for each interval, and using an indexing scheme at
        // look-up time.
        int estimatedSize = 0;
        for (int i = 0; i < normalizedIntervals.length; i++) {
            estimatedSize += (normalizedIntervals[i]/Imin) * GRADIENT_SIZE;
        }

        if (estimatedSize > MAX_GRADIENT_ARRAY_SIZE) {
            // slow method
            calculateMultipleArrayGradient(normalizedColors);
        } else {
            // fast method
            calculateSingleArrayGradient(normalizedColors, Imin);
        }

        // use the most "economical" model
        if ((transparencyTest >>> 24) == 0xff) {
            model = xrgbmodel;
        } else {
            model = ColorModel.getRGBdefault();
        }
    }

    /**
     * FAST LOOKUP METHOD
     *
     * This method calculates the gradient color values and places them in a
     * single int array, gradient[].  It does this by allocating space for
     * each interval based on its size relative to the smallest interval in
     * the array.  The smallest interval is allocated 255 interpolated values
     * (the maximum number of unique in-between colors in a 24 bit color
     * system), and all other intervals are allocated
     * size = (255 * the ratio of their size to the smallest interval).
     *
     * This scheme expedites a speedy retrieval because the colors are
     * distributed along the array according to their user-specified
     * distribution.  All that is needed is a relative index from 0 to 1.
     *
     * The only problem with this method is that the possibility exists for
     * the array size to balloon in the case where there is a
     * disproportionately small gradient interval.  In this case the other
     * intervals will be allocated huge space, but much of that data is
     * redundant.  We thus need to use the space conserving scheme below.
     *
     * @param Imin the size of the smallest interval
     */
    private void calculateSingleArrayGradient(Color[] colors, float Imin) {
        // set the flag so we know later it is a simple (fast) lookup
        isSimpleLookup = true;

        // 2 colors to interpolate
        int rgb1, rgb2;

        //the eventual size of the single array
        int gradientsTot = 1;

        // for every interval (transition between 2 colors)
        for (int i = 0; i < gradients.length; i++) {
            // create an array whose size is based on the ratio to the
            // smallest interval
            int nGradients = (int)((normalizedIntervals[i]/Imin)*255f);
            gradientsTot += nGradients;
            gradients[i] = new int[nGradients];

            // the 2 colors (keyframes) to interpolate between
            rgb1 = colors[i].getRGB();
            rgb2 = colors[i+1].getRGB();

            // fill this array with the colors in between rgb1 and rgb2
            interpolate(rgb1, rgb2, gradients[i]);

            // if the colors are opaque, transparency should still
            // be 0xff000000
            transparencyTest &= rgb1;
            transparencyTest &= rgb2;
        }

        // put all gradients in a single array
        gradient = new int[gradientsTot];
        int curOffset = 0;
        for (int i = 0; i < gradients.length; i++){
            System.arraycopy(gradients[i], 0, gradient,
                             curOffset, gradients[i].length);
            curOffset += gradients[i].length;
        }
        gradient[gradient.length-1] = colors[colors.length-1].getRGB();

        // if interpolation occurred in Linear RGB space, convert the
        // gradients back to sRGB using the lookup table
        if (colorSpace == ColorSpaceType.LINEAR_RGB) {
            for (int i = 0; i < gradient.length; i++) {
                gradient[i] = convertEntireColorLinearRGBtoSRGB(gradient[i]);
            }
        }

        fastGradientArraySize = gradient.length - 1;
    }

    /**
     * SLOW LOOKUP METHOD
     *
     * This method calculates the gradient color values for each interval and
     * places each into its own 255 size array.  The arrays are stored in
     * gradients[][].  (255 is used because this is the maximum number of
     * unique colors between 2 arbitrary colors in a 24 bit color system.)
     *
     * This method uses the minimum amount of space (only 255 * number of
     * intervals), but it aggravates the lookup procedure, because now we
     * have to find out which interval to select, then calculate the index
     * within that interval.  This causes a significant performance hit,
     * because it requires this calculation be done for every point in
     * the rendering loop.
     *
     * For those of you who are interested, this is a classic example of the
     * time-space tradeoff.
     */
    private void calculateMultipleArrayGradient(Color[] colors) {
        // set the flag so we know later it is a non-simple lookup
        isSimpleLookup = false;

        // 2 colors to interpolate
        int rgb1, rgb2;

        // for every interval (transition between 2 colors)
        for (int i = 0; i < gradients.length; i++){
            // create an array of the maximum theoretical size for
            // each interval
            gradients[i] = new int[GRADIENT_SIZE];

            // get the the 2 colors
            rgb1 = colors[i].getRGB();
            rgb2 = colors[i+1].getRGB();

            // fill this array with the colors in between rgb1 and rgb2
            interpolate(rgb1, rgb2, gradients[i]);

            // if the colors are opaque, transparency should still
            // be 0xff000000
            transparencyTest &= rgb1;
            transparencyTest &= rgb2;
        }

        // if interpolation occurred in Linear RGB space, convert the
        // gradients back to SRGB using the lookup table
        if (colorSpace == ColorSpaceType.LINEAR_RGB) {
            for (int j = 0; j < gradients.length; j++) {
                for (int i = 0; i < gradients[j].length; i++) {
                    gradients[j][i] =
                        convertEntireColorLinearRGBtoSRGB(gradients[j][i]);
                }
            }
        }
    }

    /**
     * Yet another helper function.  This one linearly interpolates between
     * 2 colors, filling up the output array.
     *
     * @param rgb1 the start color
     * @param rgb2 the end color
     * @param output the output array of colors; must not be null
     */
    private void interpolate(int rgb1, int rgb2, int[] output) {
        // color components
        int a1, r1, g1, b1, da, dr, dg, db;

        // step between interpolated values
        float stepSize = 1.0f / output.length;

        // extract color components from packed integer
        a1 = (rgb1 >> 24) & 0xff;
        r1 = (rgb1 >> 16) & 0xff;
        g1 = (rgb1 >>  8) & 0xff;
        b1 = (rgb1      ) & 0xff;

        // calculate the total change in alpha, red, green, blue
        da = ((rgb2 >> 24) & 0xff) - a1;
        dr = ((rgb2 >> 16) & 0xff) - r1;
        dg = ((rgb2 >>  8) & 0xff) - g1;
        db = ((rgb2      ) & 0xff) - b1;

        // for each step in the interval calculate the in-between color by
        // multiplying the normalized current position by the total color
        // change (0.5 is added to prevent truncation round-off error)
        for (int i = 0; i < output.length; i++) {
            output[i] =
                (((int) ((a1 + i * da * stepSize) + 0.5) << 24)) |
                (((int) ((r1 + i * dr * stepSize) + 0.5) << 16)) |
                (((int) ((g1 + i * dg * stepSize) + 0.5) <<  8)) |
                (((int) ((b1 + i * db * stepSize) + 0.5)      ));
        }
    }

    /**
     * Yet another helper function.  This one extracts the color components
     * of an integer RGB triple, converts them from LinearRGB to SRGB, then
     * recompacts them into an int.
     */
    private int convertEntireColorLinearRGBtoSRGB(int rgb) {
        // color components
        int a1, r1, g1, b1;

        // extract red, green, blue components
        a1 = (rgb >> 24) & 0xff;
        r1 = (rgb >> 16) & 0xff;
        g1 = (rgb >>  8) & 0xff;
        b1 = (rgb      ) & 0xff;

        // use the lookup table
        r1 = LinearRGBtoSRGB[r1];
        g1 = LinearRGBtoSRGB[g1];
        b1 = LinearRGBtoSRGB[b1];

        // re-compact the components
        return ((a1 << 24) |
                (r1 << 16) |
                (g1 <<  8) |
                (b1      ));
    }

    /**
     * Helper function to index into the gradients array.  This is necessary
     * because each interval has an array of colors with uniform size 255.
     * However, the color intervals are not necessarily of uniform length, so
     * a conversion is required.
     *
     * @param position the unmanipulated position, which will be mapped
     *                 into the range 0 to 1
     * @returns integer color to display
     */
    protected final int indexIntoGradientsArrays(float position) {
        // first, manipulate position value depending on the cycle method
        if (cycleMethod == CycleMethod.NO_CYCLE) {
            if (position > 1) {
                // upper bound is 1
                position = 1;
            } else if (position < 0) {
                // lower bound is 0
                position = 0;
            }
        } else if (cycleMethod == CycleMethod.REPEAT) {
            // get the fractional part
            // (modulo behavior discards integer component)
            position = position - (int)position;

            //position should now be between -1 and 1
            if (position < 0) {
                // force it to be in the range 0-1
                position = position + 1;
            }
        } else { // cycleMethod == CycleMethod.REFLECT
            if (position < 0) {
                // take absolute value
                position = -position;
            }

            // get the integer part
            int part = (int)position;

            // get the fractional part
            position = position - part;

            if ((part & 1) == 1) {
                // integer part is odd, get reflected color instead
                position = 1 - position;
            }
        }

        // now, get the color based on this 0-1 position...

        if (isSimpleLookup) {
            // easy to compute: just scale index by array size
            return gradient[(int)(position * fastGradientArraySize)];
        } else {
            // more complicated computation, to save space

            // for all the gradient interval arrays
            for (int i = 0; i < gradients.length; i++) {
                if (position < fractions[i+1]) {
                    // this is the array we want
                    float delta = position - fractions[i];

                    // this is the interval we want
                    int index = (int)((delta / normalizedIntervals[i])
                                      * (GRADIENT_SIZE_INDEX));

                    return gradients[i][index];
                }
            }
        }

        return gradients[gradients.length - 1][GRADIENT_SIZE_INDEX];
    }

    /**
     * Helper function to convert a color component in sRGB space to linear
     * RGB space.  Used to build a static lookup table.
     */
    private static int convertSRGBtoLinearRGB(int color) {
        float input, output;

        input = color / 255.0f;
        if (input <= 0.04045f) {
            output = input / 12.92f;
        } else {
            output = (float)Math.pow((input + 0.055) / 1.055, 2.4);
        }

        return Math.round(output * 255.0f);
    }

    /**
     * Helper function to convert a color component in linear RGB space to
     * SRGB space.  Used to build a static lookup table.
     */
    private static int convertLinearRGBtoSRGB(int color) {
        float input, output;

        input = color/255.0f;
        if (input <= 0.0031308) {
            output = input * 12.92f;
        } else {
            output = (1.055f *
                ((float) Math.pow(input, (1.0 / 2.4)))) - 0.055f;
        }

        return Math.round(output * 255.0f);
    }

    /**
     * {@inheritDoc}
     */
    public final Raster getRaster(int x, int y, int w, int h) {
        // If working raster is big enough, reuse it. Otherwise,
        // build a large enough new one.
        Raster raster = saved;
        if (raster == null ||
            raster.getWidth() < w || raster.getHeight() < h)
        {
            raster = getCachedRaster(model, w, h);
            saved = raster;
        }

        // Access raster internal int array. Because we use a DirectColorModel,
        // we know the DataBuffer is of type DataBufferInt and the SampleModel
        // is SinglePixelPackedSampleModel.
        // Adjust for initial offset in DataBuffer and also for the scanline
        // stride.
        // These calls make the DataBuffer non-acceleratable, but the
        // Raster is never Stable long enough to accelerate anyway...
        DataBufferInt rasterDB = (DataBufferInt)raster.getDataBuffer();
        int[] pixels = rasterDB.getData(0);
        int off = rasterDB.getOffset();
        int scanlineStride = ((SinglePixelPackedSampleModel)
                              raster.getSampleModel()).getScanlineStride();
        int adjust = scanlineStride - w;

        fillRaster(pixels, off, adjust, x, y, w, h); // delegate to subclass

        return raster;
    }

    protected abstract void fillRaster(int pixels[], int off, int adjust,
                                       int x, int y, int w, int h);


    /**
     * Took this cacheRaster code from GradientPaint. It appears to recycle
     * rasters for use by any other instance, as long as they are sufficiently
     * large.
     */
    private static synchronized Raster getCachedRaster(ColorModel cm,
                                                       int w, int h)
    {
        if (cm == cachedModel) {
            if (cached != null) {
                Raster ras = (Raster) cached.get();
                if (ras != null &&
                    ras.getWidth() >= w &&
                    ras.getHeight() >= h)
                {
                    cached = null;
                    return ras;
                }
            }
        }
        return cm.createCompatibleWritableRaster(w, h);
    }

    /**
     * Took this cacheRaster code from GradientPaint. It appears to recycle
     * rasters for use by any other instance, as long as they are sufficiently
     * large.
     */
    private static synchronized void putCachedRaster(ColorModel cm,
                                                     Raster ras)
    {
        if (cached != null) {
            Raster cras = (Raster) cached.get();
            if (cras != null) {
                int cw = cras.getWidth();
                int ch = cras.getHeight();
                int iw = ras.getWidth();
                int ih = ras.getHeight();
                if (cw >= iw && ch >= ih) {
                    return;
                }
                if (cw * ch >= iw * ih) {
                    return;
                }
            }
        }
        cachedModel = cm;
        cached = new WeakReference<Raster>(ras);
    }

    /**
     * {@inheritDoc}
     */
    public final void dispose() {
        if (saved != null) {
            putCachedRaster(model, saved);
            saved = null;
        }
    }

    /**
     * {@inheritDoc}
     */
    public final ColorModel getColorModel() {
        return model;
    }
}