/*

  * 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.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.TreeSet;

 import java.util.logging.Level;

 import java.util.logging.Logger;

 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 {

     /** winner, if any */

     private final Player winner;

     /** 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;

         this.winner = null;

     }

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

             BitSet bs = new BitSet(17 * 17);

             if (!accessibleFinalLine (p, p.endDirection, occupied, bs)) {

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

             }

         }

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

         this.winner = null;

     }

     /** Copy constructor for resigning the game */

     private Board(Board previous, int winner) {

         this.players = previous.players;

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

         this.fences = previous.fences;

         this.occupied = previous.occupied;

         this.winner = players.get(this.turn);

     }

     /** 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, null if the game is over

      */

     public Player getCurrentPlayer() {

         if (getWinner() != null) {

             return null;

         }

         return players.get(turn);

     }

     /** The play who wins on current board.

      *

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

      */

     public Player getWinner() {

         if (winner != null) {

             return winner;

         }

         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

         }

         return apply(move, getCurrentPlayer());

     }

     private Board apply(Move move, Player p) throws IllegalPositionException {

         if (move.direction != null) {

             return move(p, move.direction);

         } else {

             if (move.fence != null) {

                 return fence(p, move.fence);

             } else {

                 return new Board(this, turn + 1);

             }

         }

     }

     /** Is there a move that would take the player onto given position while

      * respecting situation on board?

      * 

      * @param p the player to try to move

      * @param column desired x-coordinate. Between 0-8. See {@link Player#getColumn()}.

      * @param row desired y-coordinate. Between 0-8. See {@link Player#getRow()}.

      * @return the move that can be {@link #apply applied} to the position and

      *   that would move the player p into desired position or null, if such 

      *   move does not exist

      * @since 1.4

      */

     public Move findMove(Player p, int column, int row) {

         int idx = getPlayers().indexOf(p);

         if (idx < 0) {

             return null;

         }

         for (Move m : Move.allMovements()) {

             Board b;

             try {

                 b = apply(m, p);

             } catch (IllegalPositionException ex) {

                 continue;

             }

             if (

                 b.getPlayers().get(idx).getColumn() == column &&

                 b.getPlayers().get(idx).getRow() == row

             ) {

                 return m;

             }

         }

         return null;

     }

     /** 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]);

                 if (arr[index].equals(player)) {

                     throw new IllegalPositionException("You cannot jump forth and back"); // NOI18N

                 }

                 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);

         if (!fen.add (fence)) {

             throw new IllegalPositionException ("Fence already prsent: " + fence); // NOI18N

         }

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

     }

     //

     // Serialization

     //

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

     /** Reads the board from a reader. Opposite operation to {@link #write(java.io.Writer)}.

      *

      * @param r the reader

      * @return the read board

      * @throws IOException if I/O error occurs

      * @throws IllegalPositionException if the reader does not contain description

      *   of the board

      */

     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);

             }

         }

     }

     /** Translates the string into board, if possible. String created by

      * use of {@link #toString()} is accepted, more information about the

      * format is avaliable in the description of {@link #write(java.io.Writer)}

      * method.

      *

      * @param board string to analyze

      * @return board object, if the string can be read

      * @throws IllegalPositionException if the string does not represent the board

      */

     public static Board valueOf(String board) {

         return new Board(board);

     }

     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;

     }

     /** Converts the board into string representation. For more information

      * about the format see {@link #write(java.io.Writer)}. To read the

      * string back use {@link #valueOf(java.lang.String)}.

      *

      * @return string representing the board

      */

     @Override

     public String toString() {

         return getCode();

     }

     //

     // 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;

         }

         if (endDir.reached(position)) {

             return true;

         }

         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 (17 * 17);

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

         assert x >= 0 && x < 17;

         assert y >= 0 && y < 17;

         return 17 * y + x;

     }

     Board(String hashCode) throws IllegalStateException{

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

         if((hashCode != null) && (hashCode.length() > 6)){

             char[]c = hashCode.toCharArray();

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

                 new Player ((c[0]-'A')*2, (c[1]-'0')*2, c[2]-'a', Player.Direction.NORTH),

                 new Player ((c[3]-'A')*2, (c[4]-'0')*2, c[5]-'a', Player.Direction.SOUTH),

             }));

             if(c[6]=='w'){

                 this.turn = 0;

                 this.winner = null;

             }else if(c[6]=='b'){

                 this.turn = 1;

                 this.winner = null;

             }else if(c[6]=='W'){

                 this.turn = 0;

                 this.winner = this.players.get(0);

             }else if(c[6]=='B'){

                 this.turn = 1;

                 this.winner = this.players.get(1);

             }else{

                 this.turn = 0;

                 this.winner = null;

             }

             for(int i=7; i<c.length;i+=2){

                 int f = Integer.parseInt(hashCode.substring(i, i+2),16);

                 Fence.Orientation o = Fence.Orientation.HORIZONTAL;

                 if(f >= 64){

                     o = Fence.Orientation.VERTICAL;

                     f -= 64;

                 }

                 fences.add(new Fence((f/8)*2+1, (f%8)*2+1,o));

             }

         }else{

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

                 new Player (8,0,10,Player.Direction.NORTH),

                 new Player (8,16,10,Player.Direction.SOUTH),

             }));

             this.winner = null;

             this.turn = 0;

         }

         try {

             this.occupied = computeOccupied (players, fences);

         } catch (IllegalPositionException ex) {

             throw new IllegalStateException (ex.getMessage ());

         }

     }

     public final String getCode() {

         Board b = this;

         StringBuilder sb = new StringBuilder();

         for(Player p: b.getPlayers()){

             sb.append((char)(p.getColumn() + 'A'));

             sb.append((char)(p.getRow() + '0'));

             sb.append((char)(p.getFences() + 'a'));

         }

         Player winner = b.getWinner();

         if(winner == null){

             if(b.players.indexOf(b.getCurrentPlayer())==0)

                 sb.append('w');

             else if(b.players.indexOf(b.getCurrentPlayer())==1)

                 sb.append('b');

             else

                 sb.append('n');

         }else{

             if(b.players.indexOf(winner)==0)

                 sb.append('W');

             else if(b.players.indexOf(winner)==1)

                 sb.append('B');

             else

                 sb.append('N');

         }

         TreeSet<Integer> fences = new TreeSet<Integer>();

         for(Fence f: b.getFences()){

             int a = (f.getColumn() - 'A')*8 + (f.getRow()-1);

             if(f.getOrientation().equals(Fence.Orientation.VERTICAL))

                 a+=64;

             fences.add(a);

         }

         for(int f: fences){

             if(f<16)

                 sb.append('0');

             sb.append(Integer.toHexString(f));

         }

         return sb.toString();

     }

 }