/*

 * 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) {