import java.util.LinkedList;
import java.util.HashMap;
import java.awt.Point;
import javax.swing.JOptionPane;
import java.io.*;

public class Board
{
    private int width, height;
    private Island islands[][];
    private Island solvedIslands[][];

    public Board(int width, int height)
    {
        this.width  = width;
        this.height = height;
        this.solvedIslands = new Island[width][height];
        this.randomiseIslands();
    }

    public boolean isSolved()
    {
        for(int i = 0; i < this.width; i++)
        {
            for(int j = 0; j < this.height; j++)
            {
                if(this.islands[i][j] != null)
                {
                    if(this.islands[i][j].numNorthBridges != this.solvedIslands[i][j].numNorthBridges ||
                       this.islands[i][j].numSouthBridges != this.solvedIslands[i][j].numSouthBridges ||
                       this.islands[i][j].numEastBridges  != this.solvedIslands[i][j].numEastBridges  ||
                       this.islands[i][j].numWestBridges  != this.solvedIslands[i][j].numWestBridges)
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public boolean islandExistsAtSquare(int x, int y)
    {
        try
        {
            return this.islands[x][y] != null;
        }
        catch(ArrayIndexOutOfBoundsException e)
        {
            return false;
        }
    }

    public boolean noIslandsAdjacentToSquare(int x, int y)
    {
        if((x > 0 && this.solvedIslands[x - 1][y] != null) ||
           (x < this.width - 1 && this.solvedIslands[x + 1][y] != null) ||
           (y > 0 && this.solvedIslands[x][y - 1] != null) ||
           (y < this.height - 1 && this.solvedIslands[x][y + 1] != null))
        {
            return false;
        }
        else
        {
            return true;
        }
    }

    public void randomiseIslands()
    {try{
        // Keep a record of which squares are still empty (i.e. do not contain
        // either a bridge or an island)
        boolean squareUsed[][] = new boolean[this.width][this.height];
        
        // Create an island at a random point
        Point newIslandCoords = new Point((int)(Math.random() * this.width), (int)(Math.random() * this.height));
        Island newIsland = new Island(0);
        this.solvedIslands[newIslandCoords.x][newIslandCoords.y] = newIsland;
        squareUsed[newIslandCoords.x][newIslandCoords.y] = true;

        // Maintain a list of all islands created so far for which there are
        // still directions in which no attempt has been made to create a bridge
        LinkedList<Island> untriedIslands = new LinkedList<Island>();
        untriedIslands.add(newIsland);

        // Creates maps of all islands and their co-ordinates and untried directions
        HashMap<Island, Point> islandCoordsMap = new HashMap<Island, Point>();
        islandCoordsMap.put(newIsland, newIslandCoords);
        
        HashMap<Island, DirectionsTested> untriedDirectionsMap = new HashMap<Island, DirectionsTested>();
        untriedDirectionsMap.put(newIsland, new DirectionsTested());

        // While there are still islands for which not every direction has been
        // tried pick one of these islands and try to add a bridge in one of its
        // untried directions
        while(!untriedIslands.isEmpty())
        {
            // Pick an island a random
            int randomIslandIndex = (int)(Math.random() * untriedIslands.size());
            Island currentIsland  = untriedIslands.get(randomIslandIndex);

            // Pick a direction to try to add a bridge in
            int direction = untriedDirectionsMap.get(currentIsland).randomUntriedDirection();
            int dx, dy;
            switch(direction)
            {
                case DirectionsTested.LEFT:  dx = -1; dy = 0;  break;
                case DirectionsTested.RIGHT: dx = 1;  dy = 0;  break;
                case DirectionsTested.UP:    dx = 0;  dy = -1; break;
                case DirectionsTested.DOWN:  dx = 0;  dy = 1;  break;
                default:
                    untriedIslands.remove(randomIslandIndex);
                    continue;
            }

            // Check it is possible to travel at least two squares in this direction
            Point currentIslandCoords = islandCoordsMap.get(currentIsland);
            int x = currentIslandCoords.x + dx + dx,
                y = currentIslandCoords.y + dy + dy;

            if(x < 0 ||
               y < 0 ||
               x >= this.width ||
               y >= this.height ||
               squareUsed[currentIslandCoords.x + dx][currentIslandCoords.y + dy] ||
               squareUsed[x][y] ||
               !this.noIslandsAdjacentToSquare(x, y))
            {
                continue;
            }

            // Mark the square two squares left of the current island as a suitable
            // location for a new island
            newIslandCoords = new Point(x, y);

            // If it is possible to travel another square in this direction then
            // randomly decide whether to do so
            x += dx;
            y += dy;
            while(x >= 0 && y >= 0 && x < this.width && y < this.height && !squareUsed[x][y] && Math.random() > 0.2)
            {
                // If there are no islands adjacent to this square then mark is
                // as a more suitable location for the new island
                if(this.noIslandsAdjacentToSquare(x, y))
                {
                    newIslandCoords.x = x;
                    newIslandCoords.y = y;
                }
                
                x += dx;
                y += dy;
            }

            // Randomly decide how many bridges to have between the current
            // island and the new one
            int numNewBridges = (int)(Math.random() * 2) + 1;

            // Create a new island at the suitable location found
            newIsland = new Island(numNewBridges);
            this.solvedIslands[newIslandCoords.x][newIslandCoords.y] = newIsland;
            currentIsland.numBridgesRequired += numNewBridges;

            // Mark all squares between the two islands as used
            for(int i = currentIslandCoords.x, j = currentIslandCoords.y; i != newIslandCoords.x + dx || j != newIslandCoords.y + dy; i += dx, j += dy)
            {
                squareUsed[i][j] = true;
            }

            // Add the bridges
            if(direction == DirectionsTested.LEFT)
            {
                currentIsland.numWestBridges = numNewBridges;
                newIsland.numEastBridges     = numNewBridges;
            }
            else if(direction == DirectionsTested.RIGHT)
            {
                currentIsland.numEastBridges = numNewBridges;
                newIsland.numWestBridges     = numNewBridges;
            }
            else if(direction == DirectionsTested.UP)
            {
                currentIsland.numNorthBridges = numNewBridges;
                newIsland.numSouthBridges     = numNewBridges;
            }
            else if(direction == DirectionsTested.DOWN)
            {
                currentIsland.numSouthBridges = numNewBridges;
                newIsland.numNorthBridges     = numNewBridges;
            }

            // Add the newly created island to the list of islands in which
            // not all directions have been tried
            untriedIslands.add(newIsland);
            islandCoordsMap.put(newIsland, newIslandCoords);
            untriedDirectionsMap.put(newIsland, new DirectionsTested());
        }

        // Keep a "solved" copy of all this islands with the required number
        // of bridges. Create an "unsolved" copy with all of the bridges removed.
        this.islands = new Island[this.width][this.height];
        for(int i = 0; i < this.width; i++)
        {
            for(int j = 0; j < this.height; j++)
            {
                if(this.solvedIslands[i][j] != null)
                {
                    this.islands[i][j] = new Island(this.solvedIslands[i][j].numBridgesRequired);
                    this.islands[i][j].numWestBridges = 0;
                    this.islands[i][j].numEastBridges = 0;
                    this.islands[i][j].numNorthBridges = 0;
                    this.islands[i][j].numSouthBridges = 0;
                }
            }
        }


    }catch(Exception e){
        StringWriter stringWritter = new StringWriter();
        PrintWriter printWritter = new PrintWriter(stringWritter, true);
        e.printStackTrace(printWritter);
        printWritter.flush();
        stringWritter.flush(); 
        stringWritter.toString();
        JOptionPane.showMessageDialog(null, stringWritter.toString());
    }
    }

    public boolean removeBridge(int x1, int y1, int x2, int y2)
    {
        Island island1 = null, island2 = null;

        // Check islands exist at both locations.
        // Store pointers to both islands.
        try
        {
            island1 = this.islands[x1][y1];
            island2 = this.islands[x2][y2];
        }
        catch(IndexOutOfBoundsException e)
        {
            return false;
        }

        if(island1 == null || island2 == null)
        {
            return false;
        }

        if(x1 == x2)
        {
            if(y1 == y2)
            {
                return false;
            }
            else if(y1 < y2)
            {
                if(island1.numSouthBridges > 0 && island2.numNorthBridges > 0 && y2 == this.getDueSouthIsland(x1, y1))
                {
                    island1.numSouthBridges--;
                    island2.numNorthBridges--;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                if(island2.numSouthBridges > 0 && island1.numNorthBridges > 0 && y1 == this.getDueSouthIsland(x1, y2))
                {
                    island2.numSouthBridges--;
                    island1.numNorthBridges--;
                }
                else
                {
                    return false;
                }
            }
        }
        else if(y1 == y2)
        {
            if(x1 > x2)
            {
                if(island1.numWestBridges > 0 && island2.numEastBridges > 0 && x1 == this.getDueEastIsland(x2, y2))
                {
                    island1.numWestBridges--;
                    island2.numEastBridges--;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                if(island1.numEastBridges > 0 && island2.numWestBridges > 0 && x2 == this.getDueEastIsland(x1, y1))
                {
                    island1.numEastBridges--;
                    island2.numWestBridges--;
                }
                else
                {
                    return false;
                }
            }
        }

        return true;
    }

    public boolean addBridge(int x1, int y1, int x2, int y2)
    {
        Island island1 = null, island2 = null;

        // Check islands exist at both locations.
        // Store pointers to both islands.
        try
        {
            island1 = this.islands[x1][y1];
            island2 = this.islands[x2][y2];
        }
        catch(IndexOutOfBoundsException e)
        {
            return false;
        }

        if(island1 == null || island2 == null)
        {
            return false;
        }

        // Do not let the user adfd more brides than requried
        if(island1.numBridgesRequired == (island1.numSouthBridges + island1.numNorthBridges + island1.numEastBridges + island1.numWestBridges) ||
            island2.numBridgesRequired == (island2.numSouthBridges + island2.numNorthBridges + island2.numEastBridges + island2.numWestBridges))
        {
            return false;
        }
        
        //
        if(x1 == x2)
        {
            if(y1 == y2)
            {
                return false;
            }
            else if(y1 < y2)
            {
                for(int i = y1 + 1; i < y2; i++)
                {
                    if(islands[x1][i] != null)
                    {
                        return false;
                    }
                }

                if(island1.numSouthBridges >= 2 || island2.numNorthBridges >= 2)
                {
                    return false;
                }

                island1.numSouthBridges++;
                island2.numNorthBridges++;
            }
            else
            {
                for(int i = y2 + 1; i < y1; i++)
                {
                    if(islands[x1][i] != null)
                    {
                        return false;
                    }
                }

                if(island2.numSouthBridges >= 2 || island1.numNorthBridges >= 2)
                {
                    return false;
                }

                island2.numSouthBridges++;
                island1.numNorthBridges++;
            }
        }
        else if(y1 == y2)
        {
            if(x1 < x2)
            {
                for(int i = x1 + 1; i < x2; i++)
                {
                    if(islands[i][y1] != null)
                    {
                        return false;
                    }
                }

                if(island1.numEastBridges >= 2 || island2.numWestBridges >= 2)
                {
                    return false;
                }

                island1.numEastBridges++;
                island2.numWestBridges++;
            }
            else
            {
                for(int i = x2 + 1; i < x1; i++)
                {
                    if(islands[i][y1] != null)
                    {
                        return false;
                    }
                }

                if(island2.numEastBridges >= 2 || island1.numWestBridges >= 2)
                {
                    return false;
                }

                island2.numEastBridges++;
                island1.numWestBridges++;
            }
        }
        return true;
    }

    /*public int getNumNorthBridges(int x, int y, boolean solved)
    {
        try
        {
            return solved ? solvedIslands[x][y].numNorthBridges : islands[x][y].numNorthBridges;
        }
        catch(Exception e)
        {
            return 0;
        }
    }*/

    public int getNumSouthBridges(int x, int y, boolean solved)
    {
        try
        {
            return solved ? solvedIslands[x][y].numSouthBridges : islands[x][y].numSouthBridges;
        }
        catch(Exception e)
        {
            return 0;
        }
    }

    public int getNumEastBridges(int x, int y, boolean solved)
    {
        try
        {
            return solved ? solvedIslands[x][y].numEastBridges : islands[x][y].numEastBridges;
        }
        catch(Exception e)
        {
            return 0;
        }
    }

    public int getCurrentNumBridges(int x, int y)
    {
        try
        {
            Island i = this.islands[x][y];
            return i.numNorthBridges + i.numSouthBridges + i.numEastBridges + i.numWestBridges;
        }
        catch(Exception e)
        {
            return 0;
        }
    }

    /*public int getNumWestBridges(int x, int y, boolean solved)
    {
        try
        {
            return solved ? solvedIslands[x][y].numWestBridges : islands[x][y].numWestBridges;
        }
        catch(Exception e)
        {
            return 0;
        }
    }*/

    public int getDueSouthIsland(int x, int y)
    {
        for(int i = y + 1; i < this.height; i++)
        {
            if(islands[x][i] != null)
            {
                return i;
            }
        }

        return -1;
    }

    public int getDueEastIsland(int x, int y)
    {
        for(int i = x + 1; i < this.width; i++)
        {
            if(islands[i][y] != null)
            {
                return i;
            }
        }

        return -1;
    }

    public int getHeight()
    {
        return this.height;
    }

    public int getWidth()
    {
        return this.width;
    }

    public int getNumRequiredBridges(int x, int y)
    {
        try
        {
            return islands[x][y].numBridgesRequired;
        }
        catch(Exception e)
        {
            return 0;
        }
    }
}