/*
 * Copyright (c) 2007, Oracle and/or its affiliates. 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.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package sun.java2d.pisces;

import java.util.Arrays;

public class Renderer implements LineSink {

///////////////////////////////////////////////////////////////////////////////
// Scan line iterator and edge crossing data.
//////////////////////////////////////////////////////////////////////////////

    private int[] crossings;

    // This is an array of indices into the edge array. It is initialized to
    // [i * SIZEOF_STRUCT_EDGE for i in range(0, edgesSize/SIZEOF_STRUCT_EDGE)]
    // (where range(i, j) is i,i+1,...,j-1 -- just like in python).
    // The reason for keeping this is because we need the edges array sorted
    // by y0, but we don't want to move all that data around, so instead we
    // sort the indices into the edge array, and use edgeIndices to access
    // the edges array. This is meant to simulate a pointer array (hence the name)
    private int[] edgePtrs;

    // crossing bounds. The bounds are not necessarily tight (the scan line
    // at minY, for example, might have no crossings). The x bounds will
    // be accumulated as crossings are computed.
    private int minY, maxY;
    private int minX, maxX;
    private int nextY;

    // indices into the edge pointer list. They indicate the "active" sublist in
    // the edge list (the portion of the list that contains all the edges that
    // cross the next scan line).
    private int lo, hi;

    private static final int INIT_CROSSINGS_SIZE = 50;
    private void ScanLineItInitialize() {
        crossings = new int[INIT_CROSSINGS_SIZE];
        edgePtrs = new int[edgesSize / SIZEOF_STRUCT_EDGE];
        for (int i = 0; i < edgePtrs.length; i++) {
            edgePtrs[i] = i * SIZEOF_STRUCT_EDGE;
        }

        qsort(0, edgePtrs.length - 1);

        // We don't care if we clip some of the line off with ceil, since
        // no scan line crossings will be eliminated (in fact, the ceil is
        // the y of the first scan line crossing).
        nextY = minY = Math.max(boundsMinY, (int)Math.ceil(edgeMinY));
        maxY = Math.min(boundsMaxY, (int)Math.ceil(edgeMaxY));

        for (lo = 0; lo < edgePtrs.length && edges[edgePtrs[lo]+Y1] <= nextY; lo++)
            ;
        for (hi = lo; hi < edgePtrs.length && edges[edgePtrs[hi]+CURY] <= nextY; hi++)
            ; // the active list is *edgePtrs[lo] (inclusive) *edgePtrs[hi] (exclusive)
        for (int i = lo; i < hi; i++) {
            setCurY(edgePtrs[i], nextY);
        }

        // We accumulate X in the iterator because accumulating it in addEdge
        // like we do with Y does not do much good: if there's an edge
        // (0,0)->(1000,10000), and if y gets clipped to 1000, then the x
        // bound should be 100, but the accumulator from addEdge would say 1000,
        // so we'd still have to accumulate the X bounds as we add crossings.
        minX = boundsMinX;
        maxX = boundsMaxX;
    }

    private int ScanLineItCurrentY() {
        return nextY - 1;
    }

    private int ScanLineItGoToNextYAndComputeCrossings() {
        // we go through the active list and remove the ones that don't cross
        // the nextY scanline.
        int crossingIdx = 0;
        for (int i = lo; i < hi; i++) {
            if (edges[edgePtrs[i]+Y1] <= nextY) {
                edgePtrs[i] = edgePtrs[lo++];
            }
        }
        if (hi - lo > crossings.length) {
            int newSize = Math.max(hi - lo, crossings.length * 2);
            crossings = Arrays.copyOf(crossings, newSize);
        }
        // Now every edge between lo and hi crosses nextY. Compute it's
        // crossing and put it in the crossings array.
        for (int i = lo; i < hi; i++) {
            addCrossing(nextY, getCurCrossing(edgePtrs[i]), (int)edges[edgePtrs[i]+OR], crossingIdx);
            gotoNextY(edgePtrs[i]);
            crossingIdx++;
        }

        nextY++;
        // Expand active list to include new edges.
        for (; hi < edgePtrs.length && edges[edgePtrs[hi]+CURY] <= nextY; hi++) {
            setCurY(edgePtrs[hi], nextY);
        }

        Arrays.sort(crossings, 0, crossingIdx);
        return crossingIdx;
    }

    private boolean ScanLineItHasNext() {
        return nextY < maxY;
    }

    private void addCrossing(int y, int x, int or, int idx) {
        if (x < minX) {
            minX = x;
        }
        if (x > maxX) {
            maxX = x;
        }
        x <<= 1;
        crossings[idx] = ((or == 1) ? (x | 0x1) : x);
    }


    // quicksort implementation for sorting the edge indices ("pointers")
    // by increasing y0. first, last are indices into the "pointer" array
    // It sorts the pointer array from first (inclusive) to last (inclusive)
    private void qsort(int first, int last) {
        if (last > first) {
            int p = partition(first, last);
            if (first < p - 1) {
                qsort(first, p - 1);
            }
            if (p < last) {
                qsort(p, last);
            }
        }
    }

    // i, j are indices into edgePtrs.
    private int partition(int i, int j) {
        int pivotVal = edgePtrs[i];
        while (i <= j) {
            // edges[edgePtrs[i]+1] is equivalent to (*(edgePtrs[i])).y0 in C
            while (edges[edgePtrs[i]+CURY] < edges[pivotVal+CURY]) { i++; }
            while (edges[edgePtrs[j]+CURY] > edges[pivotVal+CURY]) { j--; }
            if (i <= j) {
                int tmp = edgePtrs[i];
                edgePtrs[i] = edgePtrs[j];
                edgePtrs[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

//============================================================================


//////////////////////////////////////////////////////////////////////////////
//  EDGE LIST
//////////////////////////////////////////////////////////////////////////////

    private static final int INIT_NUM_EDGES = 1000;
    private static final int SIZEOF_STRUCT_EDGE = 5;

    // The following array is a poor man's struct array:
    // it simulates a struct array by having
    // edges[SIZEOF_STRUCT_EDGE * i + j] be the jth field in the ith element
    // of an array of edge structs.
    private float[] edges;
    private int edgesSize; // size of the edge list.
    private static final int Y1    = 0;
    private static final int SLOPE = 1;
    private static final int OR    = 2; // the orientation. This can be -1 or 1.
                                     // -1 means up, 1 means down.
    private static final int CURY  = 3; // j = 5 corresponds to the "current Y".
                             // Each edge keeps track of the last scanline
                             // crossing it computed, and this is the y coord of
                             // that scanline.
    private static final int CURX = 4; //the x coord of the current crossing.

    // Note that while the array is declared as a float[] not all of it's
    // elements should be floats. currentY and Orientation should be ints (or int and
    // byte respectively), but they all need to be the same type. This isn't
    // really a problem because floats can represent exactly all 23 bit integers,
    // which should be more than enough.
    // Note, also, that we only need x1 for slope computation, so we don't need
    // to store it. x0, y0 don't need to be stored either. They can be put into
    // curx, cury, and it's ok if they're lost when curx and cury are changed.
    // We take this undeniably ugly and error prone approach (instead of simply
    // making an Edge class) for performance reasons. Also, it would probably be nicer
    // to have one array for each field, but that would defeat the purpose because
    // it would make poor use of the processor cache, since we tend to access
    // all the fields for one edge at a time.

    private float edgeMinY;
    private float edgeMaxY;


    private void addEdge(float x0, float y0, float x1, float y1) {
        float or = (y0 < y1) ? 1f : -1f; // orientation: 1 = UP; -1 = DOWN
        if (or == -1) {
            float tmp = y0;
            y0 = y1;
            y1 = tmp;
            tmp = x0;
            x0 = x1;
            x1 = tmp;
        }
        // skip edges that don't cross a scanline
        if (Math.ceil(y0) >= Math.ceil(y1)) {
            return;
        }

        int newSize = edgesSize + SIZEOF_STRUCT_EDGE;
        if (edges.length < newSize) {
            edges = Arrays.copyOf(edges, newSize * 2);
        }
        edges[edgesSize+CURX] = x0;
        edges[edgesSize+CURY] = y0;
        edges[edgesSize+Y1] = y1;
        edges[edgesSize+SLOPE] = (x1 - x0) / (y1 - y0);
        edges[edgesSize+OR] = or;
        // the crossing values can't be initialized meaningfully yet. This
        // will have to wait until setCurY is called
        edgesSize += SIZEOF_STRUCT_EDGE;

        // Accumulate edgeMinY and edgeMaxY
        if (y0 < edgeMinY) { edgeMinY = y0; }
        if (y1 > edgeMaxY) { edgeMaxY = y1; }
    }

    // As far as the following methods care, this edges extends to infinity.
    // They can compute the x intersect of any horizontal line.
    // precondition: idx is the index to the start of the desired edge.
    // So, if the ith edge is wanted, idx should be SIZEOF_STRUCT_EDGE * i
    private void setCurY(int idx, int y) {
        // compute the x crossing of edge at idx and horizontal line y
        // currentXCrossing = (y - y0)*slope + x0
        edges[idx + CURX] = (y - edges[idx + CURY]) * edges[idx + SLOPE] + edges[idx+CURX];
        edges[idx + CURY] = (float)y;
    }

    private void gotoNextY(int idx) {
        edges[idx + CURY] += 1f; // i.e. curY += 1
        edges[idx + CURX] += edges[idx + SLOPE]; // i.e. curXCrossing += slope
    }

    private int getCurCrossing(int idx) {
        return (int)edges[idx + CURX];
    }
//====================================================================================

    public static final int WIND_EVEN_ODD = 0;
    public static final int WIND_NON_ZERO = 1;

    // Antialiasing
    final private int SUBPIXEL_LG_POSITIONS_X;
    final private int SUBPIXEL_LG_POSITIONS_Y;
    final private int SUBPIXEL_POSITIONS_X;
    final private int SUBPIXEL_POSITIONS_Y;
    final private int SUBPIXEL_MASK_X;
    final private int SUBPIXEL_MASK_Y;
    final int MAX_AA_ALPHA;

    // Cache to store RLE-encoded coverage mask of the current primitive
    final PiscesCache cache;

    // Bounds of the drawing region, at subpixel precision.
    final private int boundsMinX, boundsMinY, boundsMaxX, boundsMaxY;

    // Pixel bounding box for current primitive
    private int pix_bboxX0, pix_bboxY0, pix_bboxX1, pix_bboxY1;

    // Current winding rule
    final private int windingRule;

    // Current drawing position, i.e., final point of last segment
    private float x0, y0;

    // Position of most recent 'moveTo' command
    private float pix_sx0, pix_sy0;

    public Renderer(int subpixelLgPositionsX, int subpixelLgPositionsY,
                    int pix_boundsX, int pix_boundsY,
                    int pix_boundsWidth, int pix_boundsHeight,
                    int windingRule,
                    PiscesCache cache) {
        this.SUBPIXEL_LG_POSITIONS_X = subpixelLgPositionsX;
        this.SUBPIXEL_LG_POSITIONS_Y = subpixelLgPositionsY;
        this.SUBPIXEL_MASK_X = (1 << (SUBPIXEL_LG_POSITIONS_X)) - 1;
        this.SUBPIXEL_MASK_Y = (1 << (SUBPIXEL_LG_POSITIONS_Y)) - 1;
        this.SUBPIXEL_POSITIONS_X = 1 << (SUBPIXEL_LG_POSITIONS_X);
        this.SUBPIXEL_POSITIONS_Y = 1 << (SUBPIXEL_LG_POSITIONS_Y);
        this.MAX_AA_ALPHA = (SUBPIXEL_POSITIONS_X * SUBPIXEL_POSITIONS_Y);

        this.edges = new float[SIZEOF_STRUCT_EDGE * INIT_NUM_EDGES];
        edgeMinY = Float.POSITIVE_INFINITY;
        edgeMaxY = Float.NEGATIVE_INFINITY;
        edgesSize = 0;

        this.windingRule = windingRule;
        this.cache = cache;

        this.boundsMinX = pix_boundsX * SUBPIXEL_POSITIONS_X;
        this.boundsMinY = pix_boundsY * SUBPIXEL_POSITIONS_Y;
        this.boundsMaxX = (pix_boundsX + pix_boundsWidth) * SUBPIXEL_POSITIONS_X;
        this.boundsMaxY = (pix_boundsY + pix_boundsHeight) * SUBPIXEL_POSITIONS_Y;

        this.pix_bboxX0 = pix_boundsX;
        this.pix_bboxY0 = pix_boundsY;
        this.pix_bboxX1 = pix_boundsX + pix_boundsWidth;
        this.pix_bboxY1 = pix_boundsY + pix_boundsHeight;
    }

    private float tosubpixx(float pix_x) {
        return pix_x * SUBPIXEL_POSITIONS_X;
    }
    private float tosubpixy(float pix_y) {
        return pix_y * SUBPIXEL_POSITIONS_Y;
    }

    public void moveTo(float pix_x0, float pix_y0) {
        close();
        this.pix_sx0 = pix_x0;
        this.pix_sy0 = pix_y0;
        this.y0 = tosubpixy(pix_y0);
        this.x0 = tosubpixx(pix_x0);
    }

    public void lineJoin() { /* do nothing */ }

    public void lineTo(float pix_x1, float pix_y1) {
        float x1 = tosubpixx(pix_x1);
        float y1 = tosubpixy(pix_y1);

        // Ignore horizontal lines
        if (y0 == y1) {
            this.x0 = x1;
            return;
        }

        addEdge(x0, y0, x1, y1);

        this.x0 = x1;
        this.y0 = y1;
    }

    public void close() {
        // lineTo expects its input in pixel coordinates.
        lineTo(pix_sx0, pix_sy0);
    }

    public void end() {
        close();
    }

    private void _endRendering() {
        // Mask to determine the relevant bit of the crossing sum
        // 0x1 if EVEN_ODD, all bits if NON_ZERO
        int mask = (windingRule == WIND_EVEN_ODD) ? 0x1 : ~0x0;

        // add 1 to better deal with the last pixel in a pixel row.
        int width = ((boundsMaxX - boundsMinX) >> SUBPIXEL_LG_POSITIONS_X) + 1;
        byte[] alpha = new byte[width+1];

        // Now we iterate through the scanlines. We must tell emitRow the coord
        // of the first non-transparent pixel, so we must keep accumulators for
        // the first and last pixels of the section of the current pixel row
        // that we will emit.
        // We also need to accumulate pix_bbox*, but the iterator does it
        // for us. We will just get the values from it once this loop is done
        int pix_maxX = Integer.MIN_VALUE;
        int pix_minX = Integer.MAX_VALUE;

        int y = boundsMinY; // needs to be declared here so we emit the last row properly.
        ScanLineItInitialize();
        for ( ; ScanLineItHasNext(); ) {
            int numCrossings = ScanLineItGoToNextYAndComputeCrossings();
            y = ScanLineItCurrentY();

            if (numCrossings > 0) {
                int lowx = crossings[0] >> 1;
                int highx = crossings[numCrossings - 1] >> 1;
                int x0 = Math.max(lowx, boundsMinX);
                int x1 = Math.min(highx, boundsMaxX);

                pix_minX = Math.min(pix_minX, x0 >> SUBPIXEL_LG_POSITIONS_X);
                pix_maxX = Math.max(pix_maxX, x1 >> SUBPIXEL_LG_POSITIONS_X);
            }

            int sum = 0;
            int prev = boundsMinX;
            for (int i = 0; i < numCrossings; i++) {
                int curxo = crossings[i];
                int curx = curxo >> 1;
                int crorientation = ((curxo & 0x1) == 0x1) ? 1 : -1;
                if ((sum & mask) != 0) {
                    int x0 = Math.max(prev, boundsMinX);
                    int x1 = Math.min(curx, boundsMaxX);
                    if (x0 < x1) {
                        x0 -= boundsMinX; // turn x0, x1 from coords to indeces
                        x1 -= boundsMinX; // in the alpha array.

                        int pix_x = x0 >> SUBPIXEL_LG_POSITIONS_X;
                        int pix_xmaxm1 = (x1 - 1) >> SUBPIXEL_LG_POSITIONS_X;

                        if (pix_x == pix_xmaxm1) {
                            // Start and end in same pixel
                            alpha[pix_x] += (x1 - x0);
                            alpha[pix_x+1] -= (x1 - x0);
                        } else {
                            int pix_xmax = x1 >> SUBPIXEL_LG_POSITIONS_X;
                            alpha[pix_x] += SUBPIXEL_POSITIONS_X - (x0 & SUBPIXEL_MASK_X);
                            alpha[pix_x+1] += (x0 & SUBPIXEL_MASK_X);
                            alpha[pix_xmax] -= SUBPIXEL_POSITIONS_X - (x1 & SUBPIXEL_MASK_X);
                            alpha[pix_xmax+1] -= (x1 & SUBPIXEL_MASK_X);
                        }
                    }
                }
                sum += crorientation;
                prev = curx;
            }

            if ((y & SUBPIXEL_MASK_Y) == SUBPIXEL_MASK_Y) {
                emitRow(alpha, y >> SUBPIXEL_LG_POSITIONS_Y, pix_minX, pix_maxX);
                pix_minX = Integer.MAX_VALUE;
                pix_maxX = Integer.MIN_VALUE;
            }
        }

        // Emit final row
        if (pix_maxX >= pix_minX) {
            emitRow(alpha, y >> SUBPIXEL_LG_POSITIONS_Y, pix_minX, pix_maxX);
        }
        pix_bboxX0 = minX >> SUBPIXEL_LG_POSITIONS_X;
        pix_bboxX1 = maxX >> SUBPIXEL_LG_POSITIONS_X;
        pix_bboxY0 = minY >> SUBPIXEL_LG_POSITIONS_Y;
        pix_bboxY1 = maxY >> SUBPIXEL_LG_POSITIONS_Y;
    }


    public void endRendering() {
        // Set up the cache to accumulate the bounding box
        if (cache != null) {
            cache.bboxX0 = Integer.MAX_VALUE;
            cache.bboxY0 = Integer.MAX_VALUE;
            cache.bboxX1 = Integer.MIN_VALUE;
            cache.bboxY1 = Integer.MIN_VALUE;
        }

        _endRendering();
    }

    public void getBoundingBox(int[] pix_bbox) {
        pix_bbox[0] = pix_bboxX0;
        pix_bbox[1] = pix_bboxY0;
        pix_bbox[2] = pix_bboxX1 - pix_bboxX0;
        pix_bbox[3] = pix_bboxY1 - pix_bboxY0;
    }

    private void emitRow(byte[] alphaRow, int pix_y, int pix_from, int pix_to) {
        // Copy rowAA data into the cache if one is present
        if (cache != null) {
            if (pix_to >= pix_from) {
                cache.startRow(pix_y, pix_from, pix_to);

                // Perform run-length encoding and store results in the cache
                int from = pix_from - (boundsMinX >> SUBPIXEL_LG_POSITIONS_X);
                int to = pix_to - (boundsMinX >> SUBPIXEL_LG_POSITIONS_X);

                int runLen = 1;
                byte startVal = alphaRow[from];
                for (int i = from + 1; i <= to; i++) {
                    byte nextVal = (byte)(startVal + alphaRow[i]);
                    if (nextVal == startVal && runLen < 255) {
                        runLen++;
                    } else {
                        cache.addRLERun(startVal, runLen);
                        runLen = 1;
                        startVal = nextVal;
                    }
                }
                cache.addRLERun(startVal, runLen);
                cache.addRLERun((byte)0, 0);
            }
        }
        java.util.Arrays.fill(alphaRow, (byte)0);
    }
}