package com.srbenoit.modeling.grid;

import java.util.logging.Level;
import com.srbenoit.sparsearray.SparseArray;

/**
 * A two-dimensional grid that may contain objects . Contained objects must be derived from <code>
 * GridMember</code>. This class provides a fast way to iterate over the set of potential neighbors
 * of an object.
 *
 * <p>The grid manages a sparse array data structure that assigns each added object an array index
 * that does not change while the object is part of the grid. Removing objects may open gaps in the
 * array, which newly added objects will fill first before expanding the array. There are three
 * parallel arrays, all the same length, and each with the same indices populated with data:
 *
 * <dl>
 * <dt><strong>objects</strong></dt>
 * <dd>the sparse array of <code>GridMember</code> objects</dd>
 *
 * <dt><strong>xAddresses</strong></dt>
 * <dd>the X address (from 0 to gridWidth - 1) of each object</dd>
 *
 * <dt><strong>yAddresses</strong></dt>
 * <dd>the Y address (from 0 to gridHeight - 1) of each object</dd>
 * </dl>
 *
 * <p>The <strong>sortedIndices</strong> array supports fast access to neighbors lists for a member
 * as follows. Each element in this array is an array of integers containing the indices of all
 * objects with a particular X address. Within these inner arrays, indices are organized in blocks
 * by Y address (all indices with Y address 0 first, all indices with Y address 1 next, and so
 * forth). The starting index of each block is stored in the two-dimensional array <strong>
 * sortedIndexStarts</strong>, which is gridWidth x gridHeight in size, and the index after the
 * ending index of each block is stored in <strong>sortedIndexEnds</strong> (meaning that if the
 * values in <strong>sortedIndexStarts</strong> and <strong>sortedIndexEnds</strong> are equal,
 * there are no items in the list for that Y address).
 */
public final class Grid2D extends AbstractGrid2D {

    /** the X coordinate of the left edge of the grid */
    private final double minX;

    /** the Y coordinate of the bottom edge of the grid */
    private final double minY;

    /** the X coordinate of the right edge of the grid */
    private final double maxX;

    /** the Y coordinate of the top edge of the grid */
    private final double maxY;

    /** the width of the grid as a number of grid cells */
    private final int gridWidth;

    /** the height of the grid as a number of grid cells */
    private final int gridHeight;

    /** the X address of each object in the grid (size = objects.length) */
    private int[] xAddresses;

    /** the Y address of each object in the grid (size = objects.length) */
    private int[] yAddresses;

    /**
     * an array of lists of object indices, where [0] holds the list of indices of all objects with
     * X address 0, [1] holds the list of indices of all objects with X address [1], and so forth
     * (the length of this array is gridWidth). Within each list, indices of all objects with Y
     * address 0 appear first, then all with Y address 1, and so forth.
     */
    private int[][] sortedIndices;

    /**
     * the starting index of each block in sortedIndices (this array is gridWidth x gridHeight, and
     * the element at [i][j] is the index into the sortedIndices[i] array of the first object whose
     * Y address is j)
     */
    private final int[][] sortedIndexStarts;

    /**
     * the ending index of each block in sortedIndices (this array is gridWidth x gridHeightm, and
     * the element at [i][j] is the index into the sortedIndices[i] array after the last object
     * whose Y address is j - may be equal to array length)
     */
    private final int[][] sortedIndexEnds;

    /**
     * Constructs a new <code>AbstractGrid</code>.
     *
     * @param  minXCoord  the X coordinate of the left edge of the grid
     * @param  minYCoord  the Y coordinate of the bottom edge of the grid
     * @param  cellSize   width and height of the grid cells
     * @param  width      the width of the grid in cells
     * @param  height     the height of the grid in cells
     */
    public Grid2D(final double minXCoord, final double minYCoord, final double cellSize,
        final int width, final int height) {

        super(cellSize);

        this.minX = minXCoord;
        this.minY = minYCoord;
        this.maxX = minXCoord + (width * cellSize);
        this.maxY = minYCoord + (height * cellSize);

        this.gridWidth = width;
        this.gridHeight = height;

        this.xAddresses = new int[BLOCK_SIZE];
        this.yAddresses = new int[BLOCK_SIZE];

        this.sortedIndices = new int[width][BLOCK_SIZE / 4];
        this.sortedIndexStarts = new int[width][height];
        this.sortedIndexEnds = new int[width][height];
    }

    /**
     * Gets the X coordinate of the left edge of the grid.
     *
     * @return  the minimum X coordinate
     */
    public double getMinX() {

        return this.minX;
    }

    /**
     * Gets the X coordinate of the left edge of the grid.
     *
     * @return  the minimum X coordinate
     */
    public double getMaxX() {

        return this.maxX;
    }

    /**
     * Gets the Y coordinate of the bottom edge of the grid.
     *
     * @return  the minimum Y coordinate
     */
    public double getMinY() {

        return this.minY;
    }

    /**
     * Gets the Y coordinate of the bottom edge of the grid.
     *
     * @return  the minimum Y coordinate
     */
    public double getMaxY() {

        return this.maxY;
    }

    /**
     * Gets the width of the grid as a number of cells.
     *
     * @return  the width of the grid
     */
    public int getGridWidth() {

        return this.gridWidth;
    }

    /**
     * Gets the height of the grid as a number of cells.
     *
     * @return  the height of the grid
     */
    public int getGridHeight() {

        return this.gridHeight;
    }

    /**
     * Called when a member has been added - subclasses should compute grid cells for the object
     * and add the object to sorted index arrays
     *
     * @param  index  the index of the member that has just been added
     */
    protected void memberAdded(final int index) {

        GridMember2Int member;
        int xAddr;
        int yAddr;

        member = get(index);

        xAddr = coordinateToAddress(member.getPosX(), this.minX, this.gridWidth);
        yAddr = coordinateToAddress(member.getPosY(), this.minY, this.gridHeight);
        this.xAddresses[index] = xAddr;
        this.yAddresses[index] = yAddr;

        // Update the sortedIndices arrays to include the new object
        addSortedIndex(index);
    }

    /**
     * Gets the X address of the element at a particular index.
     *
     * @param   index  the index of the element
     * @return  the X address of that element
     */
    public int getXAddress(final int index) {

        return this.xAddresses[index];
    }

    /**
     * Gets the Y address of the element at a particular index.
     *
     * @param   index  the index of the element
     * @return  the Y address of that element
     */
    public int getYAddress(final int index) {

        return this.yAddresses[index];
    }

    /**
     * Called when a member is about to be removed - subclasses should clean up actions performed
     * in <code>memberAdded</code>. The object still exists in the grid's object array when this
     * method is called.
     *
     * @param  index  the index of the member that is being removed
     */
    protected void memberRemoved(final int index) {

        removeSortedIndex(index);
    }

    /**
     * Updates the grid address for a grid member that has moved.
     *
     * @param  index  the index of the grid member that moved
     * @param  newX   the grid member's new X coordinate
     * @param  newY   the grid member's new Y coordinate
     */
    public void move(final int index, final double newX, final double newY) {

        int xAddr;
        int yAddr;

        xAddr = coordinateToAddress(newX, this.minX, this.gridWidth);
        yAddr = coordinateToAddress(newY, this.minY, this.gridHeight);

        // Only take action if addresses have changed
        if ((xAddr != this.xAddresses[index]) || (yAddr != this.yAddresses[index])) {
            removeSortedIndex(index);
            this.xAddresses[index] = xAddr;
            this.yAddresses[index] = yAddr;
            addSortedIndex(index);
        }
    }

    /**
     * Identifies the neighboring objects to a specified object, and sets the bits corresponding to
     * those potential neighbors in the <code>temp</code> bit set.
     *
     * @param  member  the grid member whose neighbors are requested
     * @param  range   the range within which we consider points to be neighbors (must be no more
     *                 than one grid cell size)
     */
    public void getNeighborsOf(final GridMember2Int member, final double range) {

        int index;
        double targetX;
        double targetY;
        double targetMinX;
        double targetMaxX;
        double targetMinY;
        double targetMaxY;
        int xAddr;
        int yAddr;
        GridMember2Int test;
        int testIndex;
        int[] starts;
        int[] ends;
        int[] array;
        int end;
        int xPos;
        int yPos;
        int which;

        member.clearNeighbors();

        index = member.getGridIndex();
        targetX = member.getPosX();
        targetY = member.getPosY();

        targetMinX = targetX - range;
        targetMaxX = targetX + range;
        targetMinY = targetY - range;
        targetMaxY = targetY + range;

        xAddr = this.xAddresses[index];
        yAddr = this.yAddresses[index];

        // Test the column to the left of the object's cell
        xPos = xAddr - 1;

        if (xPos >= 0) {
            array = this.sortedIndices[xPos];
            starts = this.sortedIndexStarts[xPos];
            ends = this.sortedIndexEnds[xPos];

            // Test the cell below and left of the object's cell
            yPos = yAddr - 1;

            if (yPos >= 0) {
                end = ends[yPos];

                for (which = starts[yPos]; which < end; which++) {
                    testIndex = array[which];
                    test = get(testIndex);

                    if ((test.getPosX() > targetMinX) && (test.getPosY() > targetMinY)) { // NOPMD SRB
                        member.addNeighbor(test);
                    }
                }
            }

            // Test the cell to the left of the object's cell
            end = ends[yAddr];

            for (which = starts[yAddr]; which < end; which++) {
                testIndex = array[which];
                test = get(testIndex);

                if (test.getPosX() > targetMinX) {
                    member.addNeighbor(test);
                }
            }

            // Test the cell above and to the left of the object's cell
            yPos = yAddr + 1;

            if (yPos < this.gridHeight) {
                end = ends[yPos];

                for (which = starts[yPos]; which < end; which++) {
                    testIndex = array[which];
                    test = get(testIndex);

                    if ((test.getPosX() > targetMinX) && (test.getPosY() < targetMaxY)) { // NOPMD SRB
                        member.addNeighbor(test);
                    }
                }
            }
        }

        // Test the column containing the object's cell
        array = this.sortedIndices[xAddr];
        starts = this.sortedIndexStarts[xAddr];
        ends = this.sortedIndexEnds[xAddr];

        // Test the cell below the object's cell
        yPos = yAddr - 1;

        if (yPos >= 0) {
            end = ends[yPos];

            for (which = starts[yPos]; which < end; which++) {
                testIndex = array[which];
                test = get(testIndex);

                if (test.getPosY() > targetMinY) {
                    member.addNeighbor(test);
                }
            }
        }

        // Test the object's cell
        end = ends[yAddr];

        for (which = starts[yAddr]; which < end; which++) {
            testIndex = array[which];

            if (testIndex != index) {
                test = get(testIndex);
                member.addNeighbor(test);
            }
        }

        // Test the cell above the object's cell
        yPos = yAddr + 1;

        if (yPos < this.gridHeight) {
            end = ends[yPos];

            for (which = starts[yPos]; which < end; which++) {
                testIndex = array[which];
                test = get(testIndex);

                if (test.getPosY() < targetMaxY) {
                    member.addNeighbor(test);
                }
            }
        }

        // Test the column to the right of the object's cell
        xPos = xAddr + 1;

        if (xPos < this.gridWidth) {
            array = this.sortedIndices[xPos];
            starts = this.sortedIndexStarts[xPos];
            ends = this.sortedIndexEnds[xPos];

            // Test the cell below and right of the object's cell
            yPos = yAddr - 1;

            if (yPos >= 0) {
                end = ends[yPos];

                for (which = starts[yPos]; which < end; which++) {
                    testIndex = array[which];
                    test = get(testIndex);

                    if ((test.getPosX() < targetMaxX) && (test.getPosY() > targetMinY)) { // NOPMD SRB
                        member.addNeighbor(test);
                    }
                }
            }

            // Test the cell to the right of the object's cell
            end = ends[yAddr];

            for (which = starts[yAddr]; which < end; which++) {
                testIndex = array[which];
                test = get(testIndex);

                if (test.getPosX() < targetMaxX) {
                    member.addNeighbor(test);
                }
            }

            // Test the cell above and to the right of the object's cell
            yPos = yAddr + 1;

            if (yPos < this.gridHeight) {
                end = ends[yPos];

                for (which = starts[yPos]; which < end; which++) {
                    testIndex = array[which];
                    test = get(testIndex);

                    if ((test.getPosX() < targetMaxX) && (test.getPosY() < targetMaxY)) { // NOPMD SRB
                        member.addNeighbor(test);
                    }
                }
            }
        }
    }

    /**
     * Identifies the neighboring objects to a specified object, and sets the bits corresponding to
     * those potential neighbors in the <code>temp</code> bit set.
     *
     * @param  member  the grid member whose neighbors are requested
     */
    public void getNeighborsOf(final GridMember2Int member) {

        int index;
        int xAddr;
        int yAddr;
        int testIndex;
        int[] starts;
        int[] ends;
        int[] array;
        int end;
        int xPos;
        int yPos;
        int which;
        GridMember2Int test;

        member.clearNeighbors();

        index = member.getGridIndex();

        xAddr = this.xAddresses[index];
        yAddr = this.yAddresses[index];

        // Test the column to the left of the object's cell
        xPos = xAddr - 1;

        if (xPos >= 0) {
            array = this.sortedIndices[xPos];
            starts = this.sortedIndexStarts[xPos];
            ends = this.sortedIndexEnds[xPos];

            // Test the cell below and left of the object's cell
            yPos = yAddr - 1;

            if (yPos >= 0) {
                end = ends[yPos];

                for (which = starts[yPos]; which < end; which++) {
                    testIndex = array[which];
                    test = get(testIndex);
                    member.addNeighbor(test);
                }
            }

            // Test the cell to the left of the object's cell
            end = ends[yAddr];

            for (which = starts[yAddr]; which < end; which++) {
                testIndex = array[which];
                test = get(testIndex);
                member.addNeighbor(test);
            }

            // Test the cell above and to the left of the object's cell
            yPos = yAddr + 1;

            if (yPos < this.gridHeight) {
                end = ends[yPos];

                for (which = starts[yPos]; which < end; which++) {
                    testIndex = array[which];
                    test = get(testIndex);
                    member.addNeighbor(test);
                }
            }
        }

        // Test the column containing the object's cell
        array = this.sortedIndices[xAddr];
        starts = this.sortedIndexStarts[xAddr];
        ends = this.sortedIndexEnds[xAddr];

        // Test the cell below the object's cell
        yPos = yAddr - 1;

        if (yPos >= 0) {
            end = ends[yPos];

            for (which = starts[yPos]; which < end; which++) {
                testIndex = array[which];
                test = get(testIndex);
                member.addNeighbor(test);
            }
        }

        // Test the object's cell
        end = ends[yAddr];

        for (which = starts[yAddr]; which < end; which++) {
            testIndex = array[which];

            if (testIndex != index) {
                test = get(testIndex);
                member.addNeighbor(test);
            }
        }

        // Test the cell above the object's cell
        yPos = yAddr + 1;

        if (yPos < this.gridHeight) {
            end = ends[yPos];

            for (which = starts[yPos]; which < end; which++) {
                testIndex = array[which];
                test = get(testIndex);
                member.addNeighbor(test);
            }
        }

        // Test the column to the right of the object's cell
        xPos = xAddr + 1;

        if (xPos < this.gridWidth) {
            array = this.sortedIndices[xPos];
            starts = this.sortedIndexStarts[xPos];
            ends = this.sortedIndexEnds[xPos];

            // Test the cell below and right of the object's cell
            yPos = yAddr - 1;

            if (yPos >= 0) {
                end = ends[yPos];

                for (which = starts[yPos]; which < end; which++) {
                    testIndex = array[which];
                    test = get(testIndex);
                    member.addNeighbor(test);
                }
            }

            // Test the cell to the right of the object's cell
            end = ends[yAddr];

            for (which = starts[yAddr]; which < end; which++) {
                testIndex = array[which];
                test = get(testIndex);
                member.addNeighbor(test);
            }

            // Test the cell above and to the right of the object's cell
            yPos = yAddr + 1;

            if (yPos < this.gridHeight) {
                end = ends[yPos];

                for (which = starts[yPos]; which < end; which++) {
                    testIndex = array[which];
                    test = get(testIndex);
                    member.addNeighbor(test);
                }
            }
        }
    }

    /**
     * Called when the capacity of the sparse array is changed, to allow other programs that need
     * to keep arrays of the same size to adjust their arrays.
     *
     * @param  array        the array whose capacity is changing
     * @param  newCapacity  the new capacity of the sparse array
     */
    public void capacityChanged(final SparseArray<?> array, final int newCapacity) {

        int len;
        int[] newXAddr;
        int[] newYAddr;

        len = this.xAddresses.length;

        newXAddr = new int[newCapacity];
        newYAddr = new int[newCapacity];

        System.arraycopy(this.xAddresses, 0, newXAddr, 0, len);
        System.arraycopy(this.yAddresses, 0, newYAddr, 0, len);

        this.xAddresses = newXAddr;
        this.yAddresses = newYAddr;
    }

    /**
     * Adds a member index to the set of sorted indices. The object, X address, and Y address
     * should be populated before calling this method.
     *
     * @param  index  the index to add
     */
    private void addSortedIndex(final int index) {

        int xAddr;
        int yAddr;
        int start;
        int end;
        int[] array;
        int nextStart;
        int priorEnd;
        int[] newArray;
        int size;
        int pos;

        xAddr = this.xAddresses[index];
        yAddr = this.yAddresses[index];

        // Get array and current start and end of the block within the array
        array = this.sortedIndices[xAddr];
        start = this.sortedIndexStarts[xAddr][yAddr];
        end = this.sortedIndexEnds[xAddr][yAddr];

        for (int test = start; test < end; test++) {

            if (array[test] == index) {
                LOG.log(Level.WARNING, "Request to add object to sorted list it is already in",
                    new Exception());

                return;
            }
        }

        // Find the start of the next block
        if (yAddr < (this.gridHeight - 1)) {
            nextStart = this.sortedIndexStarts[xAddr][yAddr + 1];
        } else {
            nextStart = array.length;
        }

        // Find the end of the prior block
        if (yAddr > 0) {
            priorEnd = this.sortedIndexEnds[xAddr][yAddr - 1];
        } else {
            priorEnd = 0;
        }

        // If there is room after the current block, insert the element at the end of the current
        // block and advance its end position.  Otherwise, if there is room before the block,
        // insert the element before the block and move its start position back one.  If neither
        // can be done, expand storage to make room at the end of the block then add the element.

        if (nextStart > end) {
            array[end] = index;
            this.sortedIndexEnds[xAddr][yAddr] = end + 1;
        } else if (priorEnd < start) {
            array[start - 1] = index;
            this.sortedIndexStarts[xAddr][yAddr] = start - 1;
        } else {

            // If we're going to reallocate, size the array so there are four empty slots at the
            // end of each block (this keeps arrays from growing too large while ensuring we only
            // do this at most every fourth add)
            size = 0;

            for (int y = 0; y < this.gridHeight; y++) {
                size += this.sortedIndexEnds[xAddr][y] - this.sortedIndexStarts[xAddr][y] + 4;
            }

            newArray = new int[size];

            // Copy the array data into the new array
            pos = 0;

            for (int y = 0; y < this.gridHeight; y++) {
                size = this.sortedIndexEnds[xAddr][y] - this.sortedIndexStarts[xAddr][y];

                if (size > 0) {
                    System.arraycopy(array, this.sortedIndexStarts[xAddr][y], newArray, pos, size);
                }

                this.sortedIndexStarts[xAddr][y] = pos;
                this.sortedIndexEnds[xAddr][y] = pos + size;
                pos += size + 4;
            }

            this.sortedIndices[xAddr] = newArray;

            // Now there's room to add the new element
            end = this.sortedIndexEnds[xAddr][yAddr];
            newArray[end] = index;
            this.sortedIndexEnds[xAddr][yAddr] = end + 1;
        }
    }

    /**
     * Removes a member index from the set of sorted indices.
     *
     * @param  index  the index to remove
     */
    private void removeSortedIndex(final int index) {

        int xAddr;
        int yAddr;
        int start;
        int end;
        int[] array;
        int pos;

        xAddr = this.xAddresses[index];
        yAddr = this.yAddresses[index];

        array = this.sortedIndices[xAddr];
        start = this.sortedIndexStarts[xAddr][yAddr];
        end = this.sortedIndexEnds[xAddr][yAddr];

        for (pos = start; pos < end; pos++) {

            if (array[pos] == index) {
                array[pos] = -1;

                break;
            }
        }

        if (pos == start) {

            // If it was the first item, just shift the start ahead one
            this.sortedIndexStarts[xAddr][yAddr] = start + 1;
        } else if (pos == (end - 1)) {

            // If it was the last item, just shift the end back by one
            this.sortedIndexEnds[xAddr][yAddr] = end - 1;
        } else if (pos < (end - 1)) {

            // If it was in the middle, shift the end to the position we found,
            // then shift the end back by one
            array[pos] = array[end - 1];
            this.sortedIndexEnds[xAddr][yAddr] = end - 1;
        } else {
            LOG.warning("index not found while removing from sorted arrays");
        }
    }
}