/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

 *

 * The contents of this file are subject to the terms of either the GNU

 * General Public License Version 2 only ("GPL") or the Common

 * Development and Distribution License("CDDL") (collectively, the

 * "License"). You may not use this file except in compliance with the

 * License. You can obtain a copy of the License at

 * http://www.netbeans.org/cddl-gplv2.html

 * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the

 * specific language governing permissions and limitations under the

 * License.  When distributing the software, include this License Header

 * Notice in each file and include the License file at

 * nbbuild/licenses/CDDL-GPL-2-CP.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun in the GPL Version 2 section of the License file that

 * accompanied this code. If applicable, add the following below the

 * License Header, with the fields enclosed by brackets [] replaced by

 * your own identifying information:

 * "Portions Copyrighted [year] [name of copyright owner]"

 *

 * Contributor(s):

 *

 * Portions Copyrighted 2009 Jaroslav Tulach

 */

package cz.xelfi.quoridor;

import cz.xelfi.quoridor.Player.Direction;

import java.io.BufferedReader;

import java.io.EOFException;

import java.io.IOException;

import java.io.Reader;

import java.io.StringWriter;

import java.io.Writer;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.BitSet;

import java.util.Collection;

import java.util.Collections;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

/**

 * Represents a snapshot of the game position,

 * including all the placed and not-yet placed fences and player positions.

 * It it can print itself to stream in

 * <a href="http://www.gamerz.net/pbmserv/quoridor.html">ascii art format<a/>

 * and can it read back. The class is immutable

 * but it contains {@link #apply(cz.xelfi.quoridor.Move)}

 * that produce new {@link Board} with position created after

 * applying some {@link Move}. Use:

 * <pre>

 * Board whiteOnTurn = Board.empty();

 * Board blackOnTurn = whiteOnTurn.apply(Move.NORTH);

 * Board whiteAgain = blackOnTurn.apply(Move.SOUTH);

 * Board withOneFence = whiteAgain.apply(Move.fence('D', 7));

 * </pre>

 * 

 * @author Jaroslav Tulach

 */

public final class Board {

    /** players */

    private final List<Player> players;

    /** fences placed on board */

    private final Set<Fence> fences;

    /** occurpied bits (coordinates encoded by toIndex methods) 

                         [N]

        +-----------------------------------+

     6  |                                   |          

     5  |   +   +   +   +   +   +   +   +   |  

     4  |                                   |          

     3  |   +   +   +   +   +   +   +   +   |  

     2  |                                   |          

     1  |   +   +   +   +   +   +   +   +   |  

     0  |                                   |

     9  |   +   +   +   +   +   +   +   +   |

[W]  8  |                                   |     [E]

     7  |   +   +   +   +   +   +   +   +   |

     6  |                                   |

     5  |   +   +   +   +   +   +   +   +   |

     4  |                                   |

     3  |   +   +   +   +   +   +   +   +   |

     2  |                                   |

     1  |   +   +   +   +   +   +   +   +   |

     0  |                                   |

        +-----------------------------------+

          0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6

                         [S]

     * even indexes == position of the pawns

     * odd indexes  == centers of fences

     * even x odd   == side of a fence

     * odd x even   == side of a fence

     */

    private final BitSet occupied;

    /** which player's turn is next? */

    private final int turn;

    /**

     * Creates a new instance of Board 

     */

    private Board (int x1, int y1, int f1, int x2, int y2, int f2) {

        this.players = Collections.unmodifiableList (Arrays.asList (new Player[] {

            new Player (x1, y1, f1, Player.Direction.NORTH),

            new Player (x2, y2, f2, Player.Direction.SOUTH),

        }));

        this.fences = Collections.emptySet ();

        try {

            this.occupied = computeOccupied (players, fences);

        } catch (IllegalPositionException ex) {

            throw new IllegalStateException (ex.getMessage ());

        }

        this.turn = 0;

    }

    /** Copy constructor that provides players and fences.

     */

    private Board (int turn, List<Player> players, Set<Fence> fences)

    throws IllegalPositionException {

        this.players = Collections.unmodifiableList (players);

        this.fences = Collections.unmodifiableSet (fences);

        this.occupied = computeOccupied (players, fences);

        for (Player p : players) {

            if (!accessibleFinalLine (p, p.endDirection, occupied, new BitSet ())) {

                throw new IllegalPositionException ("Player " + p + " cannot reach " + p.endDirection + " side"); // NOI18N

            }

        }

        this.turn = turn % players.size();

    }

    /** Returns empty board with default starting position.

     * @return board with two pawns.

     */

    public static Board empty () {

        return new Board (8, 0, 10, 8, 16, 10);

    }

    /** Returns players in the game.

     * @return player object

     */

    public List<Player> getPlayers () {

        return players;

    }

    /** The fences currently on board. 

     * 

     * @return immutable set of Fences

     */

    public Set<Fence> getFences () {

        return fences;

    }

    /** The player that is supposed to play now.

     * @return the player to do next move

     */

    public Player getCurrentPlayer() {

        return players.get(turn);

    }

    /** The play who wins on current board.

     *

     * @return the winning player or <code>null</code>

     */

    public Player getWinner() {

        for (Player p : players) {

            if (p.endDirection.reached(p)) {

                return p;

            }

        }

        return null;

    }

    /** Applies given move to current board.

     *

     * @param move move creates by one of the factory methods or fields of the {@link Move} class

     * @return new board derived from this one

     *

     * @throws cz.xelfi.quoridor.IllegalPositionException throws exception if the move is illegal

     */

    public Board apply(Move move) throws IllegalPositionException {

        if (getWinner() != null) {

            throw new IllegalPositionException("Game finished!"); // NOI18N

        }

        if (move.direction != null) {

            return move(getCurrentPlayer(), move.direction);

        } else {

            return fence(getCurrentPlayer(), move.fence);

        }

    }

    /** Can the move be applied to current board position?

     * 

     * @param move the move to apply

     * @return true if one can call {@link #apply} method without getting 

     *   an exception

     */

    public boolean isApplicable(Move move) {

        try {

            // trivial implementation is enough for now

            apply(move);

            return true;

        } catch (IllegalPositionException ex) {

            return false;

        }

    }

    /** Moves the player in given direction. The direction usually

     * is one of Player.Direction constants, but in case the move

     * is a jump over another players pawn it can be followed by

     * another (usually, if there is no fence the same) direction.

     *

     * @param player the player to move

     * @param where one or two directions saying where

     * @return the new board

     * @exception IllegalPositionException if the move is not possible

     */

    final Board move (Player player, Player.Direction... where) throws IllegalPositionException {

        if (where.length != 1 && where.length != 2) {

            throw new IllegalPositionException ("Move over one or two Directions"); // NOI18N

        }

        int index = players.indexOf (player);

        Player[] arr = players.toArray (new Player[0]);

        Player oneStep = newPosition (player, where[0]);

        if (where.length == 1) {

            arr[index] = oneStep;

            return new Board(turn + 1, Arrays.asList (arr), fences);

        }

        // straight jump over

        for (Player p : players) {

            if (p.getXInternal () == oneStep.getXInternal () && p.getYInternal() == oneStep.getYInternal ()) {

                // ok, we are jumping over this one

                GO_ON: if (where[0] != where[1]) {

                    // first of all ensure that we cannot go straight

                    try {

                        newPosition (oneStep, where[0]);

                    } catch (IllegalPositionException ex) {

                        // ok

                        break GO_ON;

                    }

                    throw new IllegalPositionException ("You have to jump straight if there is no wall"); // NOI18N

                }

                arr[index] = newPosition (oneStep, where[1]);

                return new Board (turn + 1, Arrays.asList (arr), fences);

            }

        }

        throw new IllegalPositionException ("Cannot use multi direction when there is not oponent pawn"); // NOI18N

    }

    final Board fence (Player player, char x, int y, Fence.Orientation orientation) throws IllegalPositionException {

        return fence(player, new Fence ((x - 'A') * 2 + 1, y * 2 - 1, orientation));

    }

    private void columnLine(int width, int spaceX, Writer w) throws IOException {

        char ch = 'A';

        for (int x = 0; x < width - 1; x++) {

            if (x % (spaceX + 1) == 0 && x > 0) {

                w.write(ch);

                ch = (char) (ch + 1);

            } else {

                w.write(' ');

            }

        }

    }

    private Board fence(Player player, Fence fence) throws IllegalPositionException {

        if (player.getFences () == 0) {

            throw new IllegalPositionException ("Not enough fences: " + player); // NOI18N

        }

        int index = players.indexOf (player);

        Player[] arr = players.toArray (new Player[0]);

        arr[index] = new Player (arr[index].getXInternal(), arr[index].getYInternal(), arr[index].getFences() - 1, arr[index].endDirection);

        HashSet<Fence> fen = new HashSet<Fence> (this.fences);

        fen.add (fence);

        return new Board (turn + 1, Arrays.asList (arr), fen);

    }

    //

    // Serialization

    //

    private static final Pattern northSouthPattern = Pattern.compile("(\\+(\\|*)(\\*)?-+\\+)");

    public static Board read(Reader r) throws IOException, IllegalPositionException {

        BufferedReader b = new BufferedReader(r);

        for (;;) {

            String s = b.readLine();

            if (s == null) {

                throw new IOException("No board found!");

            }

            Matcher m = northSouthPattern.matcher(s);

            if (m.find()) {

                return readFromBetween(b, m);

            }

        }

    }

    private static int assertChar(String s, int pos, char... ch) throws IOException {

        if (s.length() >= pos) {

            for (int i = 0; i < ch.length; i++) {

                if (ch[i] == s.charAt(pos)) {

                    return i;

                }

            }

        }

        throw new IOException("Not found " + ch[0] + " at " + pos + " in" + s);

    }

    private static Player findPlayer(

        Player previous, String line, int y, int spaceX, Player.Direction dir, int fences

    ) {

        int index = line.indexOf(dir.player);

        if (index == -1) {

            return previous;

        }

        int x = (index - 1) / (spaceX + 1) * 2;

        return new Player(x, y - 1, fences, dir);

    }

    private static Board readFromBetween(BufferedReader b, Matcher firstMatcher)

    throws IOException, IllegalPositionException {

        final int from = firstMatcher.start(1);

        final int to = firstMatcher.end(1);

        final int northFences = firstMatcher.end(2) - firstMatcher.start(2);

        final int spaceX = (to - from - 1) / 9 - 1;

        final int spaceY = 1;

        Player p = null;

        Player q = null;

        Set<Fence> fences = new HashSet<Fence>();

        StringBuffer sb = new StringBuffer();

        int row = 7;

        for (int y = (spaceY + 1) * 9 - 1; y > 0; y--) {

            String s = b.readLine();

            if (s == null) {

                throw new EOFException();

            }

            sb.append(s);

            sb.append('\n');

            if (s.length() < to) {

                throw new IOException("Too short line: " + s); // NOI18N

            }

            assertChar(s, from, '|');

            assertChar(s, to - 1, '|');

            if (y % (spaceY + 1) == 0) {

                for (int x = 1; x < 9; x++) {

                    switch (assertChar(s, from + (spaceX + 1) * x, '+', '-', '|')) {

                        case 1:

                            fences.add(new Fence(x * 2 - 1, row * 2 + 1, Fence.Orientation.HORIZONTAL));

                            break;

                        case 2:

                            fences.add(new Fence(x * 2 - 1, row * 2 + 1, Fence.Orientation.VERTICAL));

                            break;

                        case 0:

                            break;

                        default:

                            assert false;

                    }

                }

                row--;

            } else {

                String line = s.substring(from, to);

                p = findPlayer(p, line, y, spaceX, Player.Direction.NORTH, -1);

                q = findPlayer(q, line, y, spaceX, Player.Direction.SOUTH, northFences);

            }

        }

        String last = b.readLine();

        if (last == null) {

            throw new EOFException();

        }

        Matcher lastMatcher = northSouthPattern.matcher(last);

        if (!lastMatcher.find()) {

            throw new IOException("Unrecognized last line: " + last);

        }

        List<Player> arr = new ArrayList<Player>(2);

        assert p != null;

        int southFences = lastMatcher.end(2) - lastMatcher.start(2);

        arr.add(new Player(p.getXInternal(), p.getYInternal(), southFences, p.endDirection));

        arr.add(q);

        int turn = "*".equals(lastMatcher.group(3)) ? 0 : 1; // NOI18N

        return new Board(turn, arr, fences);

    }

    /** Writes the board to the provided writer. <b>P</b> denotes position

     * of the first player and <b>Q</b> of the second. Number of remaining

     * fences of each player are shown in left bottom and left top corner

     * as appropriate number of <b>|||</b> - one <b>|</b> per fence. The

     * player that is supposed to move in this turn has <b>*</b> right after

     * the set of its fences.

     *

     * <pre>

                         [N]

            A   B   C   D   E   F   G   H

            |   |   |   |   |   |   |   |

        +|||||------------------------------+

        |                 Q                 |

     8--|   +   +   +   +   +   +   +   +   |--8

        |       |                           |           

     7--|   +   |   +   +-------+-------+   |--7

        |       |       |                   |           

     6--|-------+-------|-------+-------+   |--6

        |               |                   |          

     5--|   +   +   +   +   +   +   +   +   |--5

[W]     |               |                   |     [E]

     4--|   +   +   +   |   +   +   +-------|--4

        |               |                   |

     3--|   +   +   +   +-------+   +   +   |--3

        |                                   |

     2--|   +   +   +   +   +   +   +   +   |--2

        |                       |           |

     1--|   +   +   +   +   +   |   +   +   |--1

        |                 P     |           |

        +|||*-------------------------------+

            |   |   |   |   |   |   |   |

            A   B   C   D   E   F   G   H

                         [S]

     </pre>

     * @param w writer to write the board to

     * @exception IOException if communiction with writer fails

     */

    public void write (Writer w) throws IOException {

        write(w, 3, 1);

    }

    private void northSouthSign(int width, char sign, Writer w) throws IOException {

        int middle = width / 2;

        for (int x = 0; x < width; x++) {

            char ch = ' ';

            if (x == middle - 1) {

                ch = '[';

            }

            if (x == middle) {

                ch = sign;

            }

            if (x == middle + 1) {

                ch = ']';

            }

            w.write(ch);

        }

        w.write(System.getProperty("line.separator")); // NOI18N

    }

    private void subColumnLine(int width, int spaceX, Writer w) throws IOException {

        for (int x = 0; x < width - 1; x++) {

            if (x % (spaceX + 1) == 0 && x > 0) {

                w.write('|');

            } else {

                w.write(' ');

            }

        }

    }

    /** This will print the board with provided spacing.

     * This is example of 3:1 spacing: 

     * <pre>

     *  +---+

     *  |sss|

     *  +---+

     * </pre>

     * and this 4:2 spacing:

     * <pre>

     *  +----+

     *  |ssss|

     *  |ssss|

     *  +----+

     * </pre>

     */

    private void write (Writer w, int spaceX, int spaceY) throws IOException {

        int width = spaceX * 9 + 10;

        int height = spaceY * 9 + 10;

        char[][] desk = new char[height][];

        for (int i = 0; i < height; i++) {

            desk[i] = new char[width];

            for (int j = 0; j < width; j++) {

                if (i % (spaceY + 1) == 0 && j % (spaceX + 1) == 0) {

                    desk[i][j] = '+';

                } else {

                    desk[i][j] = ' ';

                }

            }

            desk[i][0] = '|';

            desk[i][width - 1] = '|';

        }

        for (int i = 1; i < width - 1; i++) {

            desk[0][i] = '-';

            desk[height -1][i] = '-';

        }

        desk[0][0] = '+';

        desk[0][width - 1] = '+';

        desk[height - 1][0] = '+';

        desk[height - 1][width - 1] = '+';

        {

            for (Player p : players) {

                int px = p.getXInternal() / 2;

                int py = p.getYInternal() / 2;

                desk

                    [1 + py * (spaceY + 1) + spaceY / 2]

                    [1 + px * (spaceX + 1) + spaceX / 2] = p.endDirection.player;

                paintLeftFences(desk, p.endDirection, p.getFences(), p.equals(getCurrentPlayer()));

            }

        }

        for (Fence f : fences) {

            int fx = (f.getX() / 2 + 1) * (spaceX + 1);

            int fy = (f.getY() / 2 + 1) * (spaceY + 1);

            switch (f.getOrientation()) {

                case HORIZONTAL:

                    for (int i = -spaceX; i <= spaceX; i++) {

                        desk[fy][fx + i] = '-';

                    }

                    break;

                case VERTICAL:

                    for (int i = -spaceY; i <= spaceY; i++) {

                        desk[fy + i][fx] = '|';

                    }

                    break;

                default: 

                    throw new IllegalStateException ("Unknown orientation: " + f.getOrientation ()); // NOI18N

            }

        }

        w.write("        ");

        northSouthSign(width, 'N', w);

        w.write(System.getProperty("line.separator")); // NOI18N

        w.write("        ");

        columnLine(width, spaceX, w);

        w.write(System.getProperty("line.separator")); // NOI18N

        w.write("        ");

        subColumnLine(width, spaceX, w);

        w.write(System.getProperty("line.separator")); // NOI18N

        int cnt = 9;

        for (int y = height - 1; y >= 0; y--) {

            if (y == height / 2) {

                w.write("[W]  ");

            } else {

                w.write("     ");

            }

            boolean number = y % (spaceY + 1) == 0 && y > 0 && y < height - 1;

            if (number) {

                cnt--;

                w.write(Integer.toString(cnt));

                w.write("--");

            } else {

                w.write("   ");

            }

            for (int x = 0; x < width; x++) {

                w.write(desk[y][x]);

            }

            if (number) {

                w.write("--");

                w.write(Integer.toString(cnt));

            } else {

                w.write("   ");

            }

            if (y == height / 2) {

                w.write("  [E]");

            }

            w.write(System.getProperty("line.separator")); // NOI18N

        }

        w.write("        ");

        subColumnLine(width, spaceX, w);

        w.write(System.getProperty("line.separator")); // NOI18N

        w.write("        ");

        columnLine(width, spaceX, w);

        w.write(System.getProperty("line.separator")); // NOI18N

        w.write(System.getProperty("line.separator")); // NOI18N

        w.write("        ");

        northSouthSign(width, 'S', w);

    }

    private void paintLeftFences(char[][] desk, Direction endDirection, int fences, boolean currentTurn) {

        assert fences >= 0 && fences <= 10 : "Players: " + players;

        switch (endDirection) {

            case SOUTH: {

                for (int i = 0; i < fences; i++) {

                    desk[desk.length - 1][i + 1] = '|';

                }

                if (currentTurn) {

                    desk[desk.length - 1][fences + 1] = '*';

                }

                break;

            }

            case NORTH: {

                for (int i = 0; i < fences; i++) {

                    desk[0][i + 1] = '|';

                }

                if (currentTurn) {

                    desk[0][fences + 1] = '*';

                }

                break;

            }

            default:

                assert false;

        }

    }

    //

    // Standard Methods

    // 

    @Override

    public int hashCode () {

        return occupied.hashCode ();

    }

    @Override

    public boolean equals (Object o) {

        if (o instanceof Board) {

            Board b = (Board)o;

            return occupied.equals (b.occupied) && players.equals (b.players);

        }

        return false;

    }

    @Override

    public String toString() {

        StringWriter w = new StringWriter();

        try {

            write(w);

        } catch (IOException ex) {

            return ex.toString();

        }

        return w.toString();

    }

    //

    // Validation methods

    //

    /** Computes new position of a player and checks whether there is no

     * fence between the old and new.

     */

    private Player newPosition (Player old, Player.Direction direction) throws IllegalPositionException {

        return newPosition (old, direction, occupied);

    }

    private static Player newPosition (Player old, Player.Direction direction, BitSet occupied) throws IllegalPositionException {

        int nx = old.x;

        int ny = old.y;

        int fx = old.x;

        int fy = old.y;

        switch (direction) {

            case NORTH: 

                ny = old.y + 2;

                fy = old.y + 1;

                break;

            case SOUTH: 

                ny = old.y - 2; 

                fy = old.y - 1;

                break;

            case EAST: 

                nx = old.x + 2; 

                fx = old.x + 1;

                break;

            case WEST: 

                nx = old.x - 2; 

                fx = old.x - 1;

                break;

            default: throw new IllegalStateException ("Unknown direction: " + direction); // NOI18N

        }

        if (nx < 0 || nx > 16) throw new IllegalPositionException ("Wrong player position: " + nx + ":" + ny); // NOI18N

        if (ny < 0 || ny > 16) throw new IllegalPositionException ("Wrong player position: " + nx + ":" + ny); // NOI18N

        int fenceIndex = toIndex (fx, fy);

        if (occupied.get (fenceIndex)) {

            throw new IllegalPositionException ("You cannot go over fences"); // NOI18N

        }

        return new Player (nx, ny, old.getFences (), old.endDirection);

    }

    /** @param position the current position of the player

     * @param endDir the side the player wants to reach

     * @param fences bits set to 1 when fences are placed

     * @param reached bits on squares that were already reached (modified during run)

     * @return true if the end line can be reached

     */

    private static boolean accessibleFinalLine (Player position, Player.Direction endDir, BitSet fences, BitSet reached) {

        int index = toIndex (position);

        if (reached.get (index)) {

            // already visited without success

            return false;

        }

        switch (endDir) {

            case NORTH: 

                if (position.getYInternal() == 8) return true;

                break;

            case SOUTH:

                if (position.getYInternal() == 0) return true;

                break;

            case EAST:

                if (position.getXInternal() == 0) return true;

                break;

            case WEST:

                if (position.getXInternal() == 8) return true;

                break;

            default:

                throw new IllegalStateException ("Wrong direction: " + endDir); // NOI18N

        }

        reached.set (index);

        for (Player.Direction oneDirection : Player.Direction.values ()) {

            try {

                if (accessibleFinalLine (newPosition (position, oneDirection, fences), endDir, fences, reached)) {

                    return true;

                }

            } catch (IllegalPositionException ex) {

                // ok, try once more

            }

        }

        return false;

    }

    /** Computes mask of the occupried bits.

     */

    private static BitSet computeOccupied (

        Collection<Player> players, Collection<Fence> fences

    ) throws IllegalPositionException {

        BitSet occupied = new BitSet (20 * 30); // TBD this is just an upper guess

        for (Player p : players) {

            if (p.getXInternal() % 2 == 1) throw new IllegalPositionException ("Wrong player position: " + p); // NOI18N

            if (p.getYInternal() % 2 == 1) throw new IllegalPositionException ("Wrong player position: " + p); // NOI18N

            int index = toIndex (p);

            if (occupied.get (index)) {

                throw new IllegalPositionException ("There cannot be two players at " + p); // NOI18N

            }

            occupied.set (index);

        }

        for (Fence f : fences) {

            for (int i = -1; i <= 1; i++) {

                int index = toIndex (f, i);

                if (index < 0 || index > occupied.size ()) {

                    throw new IllegalPositionException ("Wrong fence position: " + f); // NOI18N

                }

                if (occupied.get (index)) {

                    throw new IllegalPositionException ("Fence collition: " + f); // NOI18N

                }

                occupied.set (index);

            }

        }

        return occupied;

    }

    /** Converts twodimensional coordinates of player to one dimensional index.

     */

    private static int toIndex (Player p) {

        return toIndex (p.getXInternal(), p.getYInternal());

    }

    /** Converts twodimensional coordinates of fence to one dimensional index.

     * @param f the fence

     * @param whichPart (-1, 0, 1) 

     */

    private static int toIndex (Fence f, int whichPart) {

        int x = f.getX ();

        int y = f.getY ();

        switch (f.getOrientation ()) {

            case HORIZONTAL: x += whichPart; break;

            case VERTICAL: y += whichPart; break;

            default: throw new IllegalStateException ("Wrong orientation: " + f.getOrientation ()); // NOI18N

        }

        return toIndex (x, y);

    }

    /** Diagonal conversion of two positive integers to one integer.

     * <pre>

     * y3 9

     * y2 5  8

     * y1 2  4  7

     * y0 0  1  3  6

     *   x0 x1 x2 x3

     * </pre>

     */

    private static int toIndex (int x, int y) {

        int max = x + y;

        int baseOnY0 = max * (max + 1) / 2;

        return baseOnY0 + y;

    }

}