/*
  Copyright (c) 2003, 2008 Nesterovsky bros.  All rights reserved.
  
  PGN parser component.
  We use http://www.very-best.de/pgn-spec.htm as PGN specification.

  You must not remove this notice, or any other, from this software.
*/

/*
  PGN document.
*/
function PgnDocument()
{
  this.games = new Array;
  this._ids = new Array;
}

/*
  Occurs when pgn document is changed
*/
PgnDocument.prototype.onchanged = null;

PgnDocument.prototype.games; // array of PgnGame

PgnDocument.prototype._ids = null; // map (id, document elements)

PgnDocument.prototype._chessBaseFormat = true;

// 0 - uninitialized
// 1 - loading
// 2 - ready
PgnDocument.prototype._state = 0;

PgnDocument.prototype._change = function() 
{ 
  if (this.onchanged)
  {
    this.onchanged(this); 
  }
}

/*
  Returns current state of the pgn document.
*/
PgnDocument.prototype.getState = function()
{
  return this._state;
}

PgnDocument.prototype.getElementById = function(id) 
{ 
  return this._ids[id]; 
}

PgnDocument.prototype.load = function(source, asyncCallback)
{
  this.state = 1;

  var document = this;
  var scanner = new PgnScanner(source);
  var games = new Array;
  var game = null;
  
  this.games = games;
  
  function readMoves(parent, whiteTurn)
  {
    // load move text section
    var moves = new Array;
    var prev = null;
    
  MovesCycle:  
    while(true)
    {
      var moveNumber = 0;
      var whiteMove = whiteTurn;

      whiteTurn = !whiteTurn;
      scanner.skipSpace();
      
      switch(scanner.getCurrentToken())
      {
        case PgnScanner.Integer:
        {
          moveNumber = scanner.getValue();
          
          scanner.next();
          scanner.skipSpace();

          var periods = 0;          
          
          while(scanner.getCurrentToken() == PgnScanner.Period)
          {
            periods++;
            scanner.next();
          }
          
          if (periods >= 2)
          {
            if (periods <= 3)
            {
              whiteMove = false;
              whiteTurn = true;
            }
            else
            {
              throw new Error("Invalid format");
            }

            scanner.skipSpace();
          }
          else 
          {
            scanner.skipSpace();
  
            if (scanner.getCurrentToken() == PgnScanner.Minus)
            {
              scanner.next();
              
              if (scanner.getCurrentToken() != PgnScanner.Minus)
              {
                throw new Error("Invalid format");
              }

              scanner.next();
              scanner.skipSpace();
              whiteMove = false;
              whiteTurn = true;
            }
          }
          // Pass through
        }
        case PgnScanner.Symbol:
        {
          var move = scanner.getValue();
          var annotation = null;
          var variations = null;
          var gameMove = new PgnMove;
          var token;
          var comment = null;
          
          scanner.next();
          scanner.skipSpace();

ReadMove:
          while(true)
          {
            var s = scanner.getComment(true);
            
            if (s)
            {
              if (comment)
              {
                comment += s;
              }
              else
              {
                comment = s;
              }
            }
            
            switch(scanner.getCurrentToken())
            {
              case PgnScanner.NAG:
              {
                var annotationValue = scanner.getValue();
                
                if (annotation == null)
                {
                  annotation = annotationValue;
                }
                else
                {
                  if (!(annotation instanceof Array))
                  {
                    var annotationList = new Array;
                    
                    annotationList.push(annotation);
                    annotation = annotationList;
                  }

                  annotation.push(annotationValue);
                }

                scanner.next();
                scanner.skipSpace();
            
                break;
              }
              case PgnScanner.LeftParenthesis:
              {
                scanner.next();
                
                if (variations == null)
                {
                  variations = new Array;
                }
               
                variations.push(readMoves(gameMove, whiteMove));
                
                if (scanner.getCurrentToken() != PgnScanner.RightParenthesis)
                {
                  throw new Error("Invalid format");
                }
                
                scanner.next();
                scanner.skipSpace();
                break;
              }
              default:
              {
                break ReadMove;
              }
            }
          }
          
          gameMove.id = document._ids.length;
          document._ids.push(gameMove);
          gameMove.moveNumber = moveNumber;
          gameMove.move = move;
          gameMove.whiteMove = whiteMove;
          gameMove.annotation = annotation;
          gameMove.comment = comment;
          gameMove.variations = variations;
          gameMove.parentMove = parent;
          gameMove.prevMove = prev;
          
          if (prev)
          {
            prev.nextMove = gameMove;
          }
          
          gameMove.game = game;
          moves.push(gameMove);
          prev = gameMove;
          
          break;
        }
        case PgnScanner.Termination:
        {
          if (parent) 
          {
            throw new Error("Invalid format");
          }
            
          var value = scanner.getValue();
          
          game.result = value;
          scanner.skipSpace();
          
          break MovesCycle;
        }
        case PgnScanner.RightParenthesis:
        {
          if (!parent) 
          {
            throw new Error("Invalid format");
          }
          
          break MovesCycle;
        }
        default:
        {
          throw new Error("Invalid format");
        }
      }
    }
    
    return moves;
  }
  
  function readGame()
  {
    if (!scanner.next())
    {
      return null;
    }
    
    scanner.skipSpace();
    
    if (scanner.getCurrentToken() == PgnScanner.End)
    {
      return null;
    }
    
    // Load game
    var tags = new Array;

    game = new PgnGame;
    game.document = document;
    game.id = document._ids.length;
    document._ids.push(game);
    games.push(game);
    game.tags = tags;
    
    // load tag section
    while(scanner.getCurrentToken() == PgnScanner.LeftBracket)
    {
      scanner.readToken(PgnScanner.Symbol, true);
      
      var name = scanner.getValue();
      
      scanner.readToken(PgnScanner.Space);
      scanner.readToken(PgnScanner.String);

      var value = scanner.getValue();

      scanner.readToken(PgnScanner.RightBracket, true);
      scanner.next();
      scanner.skipSpace();
      tags[name] = value;
    }
    
    game.comment = scanner.getComment(true);
    game.moves = readMoves(null, true);
    
    return game;
  }

  // Go through all games
  if (asyncCallback)
  {
    function cycle()
    {
      var game = readGame();
      
      if (game != null)
      {
        if (asyncCallback(document, game))
        {
          Util.run(cycle, games.length % 10 ? 0 : 500);
        }
      }
      else
      {
        document._state = 2; 
      }
      
      document._change();
    }
  
    Util.run(cycle, 0);
  }
  else
  {
    while(readGame() != null)
    {
      // do nothing
    }
    
    document._state = 2;
    
    Util.run(change, 0);
  }
}

function PgnGame() {}

PgnGame.prototype.id = null; // game unique id
PgnGame.prototype.tags = null; // (name, value) map
PgnGame.prototype.moves = null; // array of PgnMove
PgnGame.prototype.result = "*"; // game result string
PgnGame.prototype.comment = null; // comment to the game
PgnGame.prototype._state = null; // cached initial game state
PgnGame.prototype.document = null; // pgn document

PgnGame.prototype.getState = function() { return _PgnGameState.getGameState(this); }

function PgnMove() {}

PgnMove.prototype.id = null; // move unique id
PgnMove.prototype.moveNumber = 0;
PgnMove.prototype.move = null; // move itself
PgnMove.prototype.annotation = null; // numeric annotation glyph
PgnMove.prototype.comment = null; // comment to a move
PgnMove.prototype.variations = null; // optional move variations, array of array of PgnMove
PgnMove.prototype.whiteMove = true; // true - white's move, false - black's move
PgnMove.prototype.prevMove = null; // reference to previous move
PgnMove.prototype.nextMove = null; // reference to next move
PgnMove.prototype.parentMove = null; // reference to next move
PgnMove.prototype.game = null; // reference to game

// State of the move is specified by map with set of items that corespond to pieces
// and other items. Each item contains array of board elements of the specified type.
// There are following pieces: K, Q, R, B, N, P, k, q, r, b, n, p. Each piece has it's
// position. There are also a, A - arrows board element that has start and end point.
PgnMove.prototype._state = null; // cached game state

PgnMove.prototype.getState = function() 
{ 
  return _PgnGameState.getMoveState(this); 
}

PgnState = function() {}

PgnState.prototype.board = null;

// Pgn scanner
// This class scans Pgn data and returns tokens.
function PgnScanner(source)
{
  this._source = source;
  this._pos = new PgnScannerPosition;
  this._nextPos = new PgnScannerPosition;
}

PgnScanner.prototype._source = null;
PgnScanner.prototype._index = 0;
PgnScanner.prototype._pos = null;
PgnScanner.prototype._nextPos = null;
PgnScanner.prototype._currentToken = PgnScanner.Start;
PgnScanner.prototype._value = null;
PgnScanner.prototype._comment = null;

PgnScanner.prototype.getSource = function()
{ 
  return this._source;
}

PgnScanner.prototype.getSourceIndex = function() 
{ 
  return this._index; 
}

PgnScanner.prototype.getCurrentPosition = function()
{
  return PgnScannerPosition.Copy(this._pos);
}

PgnScanner.prototype.getCurrentToken = function() 
{ 
  return this._currentToken; 
}

PgnScanner.prototype.getValue = function() 
{ 
  return this._value; 
}

PgnScanner.prototype.getComment = function(reset)
{ 
  var value = this._comment;
  
  if (reset)
    this._comment = null;
    
  return value; 
}

PgnScanner.prototype.next = function()
{
  var source = this._source;
  var length = source.length;
  var pos = this._nextPos;
  var i = this._index;
  var c;
  
  if (this._index >= length)
  {
    this._currentToken = PgnScanner.End;
    this._value = null;
    
    return false;
  }
  
  this._pos.assign(pos);
  c = source.charAt(this._index);
  
  switch(c)
  {
    case " ": case "\t": case "\v":
    {
SkipSpace:
      while(true)
      {
        i++;
        pos.column++;
        
        if (i > length)
        {
          break;
        }
        
        switch(source.charAt(i))
        {
          case " ": case "\t": case "\v":
          {
            break;
          }
          default:
          {
            break SkipSpace;
          }
        }
      }
      
      this._value = source.substring(this._index, i);
      this._currentToken = PgnScanner.Space;
      this._index = i;
    
      break;
    }
    case "\r":
    {
      i++;
      
      if ((i < length) && (source.charAt(i) == "\n"))
      {
        i++;
      }
      
      pos.column = 0;
      pos.line++;
      this._value = source.substring(this._index, i);
      this._currentToken = PgnScanner.NewLine;
      this._index = i;
    
      break;
    }
    case "\n":
    {
      i++;
      
      if ((i < length) && (source.charAt(i) == "\r"))
      {
        i++;
      }
      
      pos.column = 0;
      pos.line++;
      this._value = source.substring(this._index, i);
      this._currentToken = PgnScanner.NewLine;
      this._index = i;
     
      break;
    }
    case "\"":
    {
      var value = "";
      
      i++;
      
ScanString:
      { 
StringError:
        while(i < length)
        {
          c = source.charAt(i++);
          pos.column++;
          
          switch(c)
          {
            case "\"":
            {
              break ScanString;  
            }
            case "\r": case "\n":
            {
              break StringError;
            }
            case "\\":
            {
              i++;
          
              if (i >= length)
              {
                break;
              }
              
              pos.column++;
              c = source.charAt(i);
              
              switch(c)
              {
                case "r":
                {
                  value += "\r";
                 
                  break;
                }
                case "t":
                {
                  value += "\t";
                
                  break;
                }
                case "v":
                {
                  value += "\v";
                
                  break;
                }
                default:
                {
                  value += c;
                
                  break;
                }
              }
              
              break;
            }
            default:
            {
              value += c;
              
              break;
            }
          }
        }
        
        throw new Error("Invalid string format.");
      }
      
      this._value = value;
      this._currentToken = PgnScanner.String;
      this._index = i;
      
      break;
    }
    case "0": case "1": case "2": case "3": case "4":
    case "5": case "6": case "7": case "8": case "9":
    {
SkipInteger:    
      while(true)
      {
        i++;
        pos.column++;
        
        if (i > length)
        {
          break;
        }
        
        c = source.charAt(i);
        
        switch(c)
        {
          case "0": case "1": case "2": case "3": case "4":
          case "5": case "6": case "7": case "8": case "9":
          {
            break;
          }
          default:
          {
            break SkipInteger;
          }
        }
      }
      
      // Check for "0-1", "1-0", "1/2-1/2" termination tokens
      if (this._index + 1 == i && ((c == "-") || (c == "/")))
      {
        if (source.substr(this._index, 3) == "0-1")
        {
          this._value = "0-1";
          this._currentToken = PgnScanner.Termination;
          this._index += 3;
      
          break;
        }
        else if (source.substr(this._index, 3) == "1-0")
        {
          this._value = "1-0";
          this._currentToken = PgnScanner.Termination;
          this._index += 3;
      
          break;
        }
        else if (source.substr(this._index, 7) == "1/2-1/2")
        {
          this._value = "1/2-1/2";
          this._currentToken = PgnScanner.Termination;
          this._index += 7;
      
          break;
        }
      }
      
      this._value = parseInt(source.substring(this._index, i));
      this._currentToken = PgnScanner.Integer;
      this._index = i;
      
      break;
    }
    case ".":
    {
      pos.column++;
      this._value = ".";
      this._currentToken = PgnScanner.Period;
      this._index = i + 1;
      
      break;
    }
    case "*":
    {
      pos.column++;
      this._value = "*";
      this._currentToken = PgnScanner.Termination;
      this._index = i + 1;
      
      break;
    }
    case "[":
    {
      pos.column++;
      this._value = "[";
      this._currentToken = PgnScanner.LeftBracket;
      this._index = i + 1;
      
      break;
    }
    case "]":
    {
      pos.column++;
      this._value = "]";
      this._currentToken = PgnScanner.RightBracket;
      this._index = i + 1;
      
      break;
    }
    case "(":
    {
      pos.column++;
      this._value = "(";
      this._currentToken = PgnScanner.LeftParenthesis;
      this._index = i + 1;
      
      break;
    }
    case ")":
    {
      pos.column++;
      this._value = ")";
      this._currentToken = PgnScanner.RightParenthesis;
      this._index = i + 1;
      
      break;
    }
    case "<":
    {
      pos.column++;
      this._value = "<";
      this._currentToken = PgnScanner.LeftAngle;
      this._index = i + 1;
      
      break;
    }
    case ">":
    {
      pos.column++;
      this._value = ">";
      this._currentToken = PgnScanner.RightAngle;
      this._index = i + 1;
      
      break;
    }
    case "$":
    {
      i++;
      pos.column++;
      
      if (i >= length)
      {
        throw new Error("Invalid NAG.");
      }

      var first = true;
      
SkipNag:
      while(true)
      {
        if (i > length)
        {
          break;
        }
        
        c = source.charAt(i);
        
        switch(c)
        {
          case "0": case "1": case "2": case "3": case "4":
          case "5": case "6": case "7": case "8": case "9":
          {
            first = false;
        
            break;
          }
          default:
          {
            if (first)
            {
              throw new Error("Invalid NAG.");
            }
            else
            {
              break SkipNag;
            }
          }
        }
        
        i++;
        pos.column++;
      }
      
      this._value = parseInt(source.substring(this._index + 1, i));
      this._currentToken = PgnScanner.NAG;
      this._index = i;
     
      break;
    }
    case ";":
    case "%":
    {
      var isComment = c == ";";
      
      this._currentToken = isComment ?  PgnComment : PgnExtension;
      
SkipLineComment:      
      while(++i < length)
      {
        c = source.charAt(i);
        switch(c)
        {
          case "\r": case "n":
          {
            break SkipLineComment;
          }
        }
      }
      
      this._value = source.substring(this._index + 1, i);
      
      if (isComment)
      {
        if (this._comment)
        {
          this._comment += "\r" + this._value;
        }
        else
        {
          this._comment = this._value;
        }
      }
      if (i < length)
      {
        i++;
        
        switch(c)
        {
          case "\r":
          {
            if ((i < length) && (source.charAt(i) == "\n"))
            {
              i++;
            }
          
            break;
          }
          case "\n":
          {
            if ((i < length) && (source.charAt(i) == "\r"))
            {
              i++;
            }
          
            break;
          }
        }
      }
      
      this._index = i;
      pos.column = 0;
      pos.line++;
      
      break;
    }
    case "{":
    {
SkipComment:
      {    
CommentError:      
        while(++i < length)
        {
          c = source.charAt(i);
      
          switch(c)
          {
            case "}":
            {
              break SkipComment;
            }
            case "\r":
            {
              if ((i < length) && (source.charAt(i) == "\n"))
              {
                i++;
              }
              
              pos.column = 0;
              pos.line++;
            
              break;
            }
            case "\n":
            {
              if ((i < length) && (source.charAt(i) == "\r"))
              {
                i++;
              }
              
              pos.column = 0;
              pos.line++;
            
              break;
            }
            default:
            {
              pos.column++;
             
              break;
            }
          }
        }
        
        throw new Error("Invalid comment");
      }
      
      this._value = source.substring(this._index + 1, i);
      
      if (this._comment)
      {
        this._comment += "\r" + this._value;
      }
      else
      {
        this._comment = this._value;
      }
      
      this._currentToken = PgnScanner.Comment;
      this._index = i + 1;
      
      break;
    }
    default:
    {
      if ((c >= "A") && (c <= "Z") || (c >= "a") && (c <= "z"))
      {
        while(++i < length)
        {
          pos.column++;
          c = source.charAt(i);
      
          if (!((c >= "A") && (c <= "Z") || (c >= "a") && (c <= "z") || 
            (c >= "0") && (c <= "9") || (c == "_") || (c == "+") || 
            (c == "-") || (c == ":") || (c == "#") || (c == "=")))
          {
            break;
          }
        }
        
        this._value = source.substring(this._index, i);
        this._currentToken = PgnScanner.Symbol;
        this._index = i;
      }
      else if (c == "-")
      {
        // Minus.
        this._value = c;
        this._currentToken = PgnScanner.Minus;
        this._index = ++i;
      }
      else
      {
        // Unknown token.
        this._value = c;
        this._currentToken = PgnScanner.Unknown;
        this._index = ++i;
      }
      
      break;
    }
  }
  
  return true;
}

PgnScanner.prototype.skipSpace = function()
{
  while(true)
  {
    switch(this.getCurrentToken())
    {
      case PgnScanner.Start: 
      case PgnScanner.Space: 
      case PgnScanner.NewLine: 
      case PgnScanner.Comment:
      case PgnScanner.Unknown:
      {
        if (!this.next())
        {
          return;
        }
        
        break;
      }
      default:
      {
        return;
      }
    }
  }
}

PgnScanner.prototype.readToken = function(value, skipSpace)
{
  if (this.next())
  {
    if (skipSpace)
    {
      this.skipSpace();
    }
    
    if (this.getCurrentToken() == value)
    {
      return;
    }
  }
  else
  {
    if (value == PgnScanner.End)
    {
      return;
    }
  }
  
  throw new Error("Invalid token");
}

// Tokens
PgnScanner.Unknown = -1;
PgnScanner.Start = 0;
PgnScanner.End = 1;
PgnScanner.Space = 2;
PgnScanner.NewLine = 3;
PgnScanner.String = 4;
PgnScanner.Integer = 5;
PgnScanner.Period = 6;
PgnScanner.Termination = 7;
PgnScanner.LeftBracket = 8;
PgnScanner.RightBracket = 9;
PgnScanner.LeftParenthesis = 10;
PgnScanner.RightParenthesis = 11;
PgnScanner.LeftAngle = 12;
PgnScanner.RightAngle = 13;
PgnScanner.NAG = 14;
PgnScanner.Symbol = 15;
PgnScanner.Comment = 16;
PgnScanner.Extension = 17;
PgnScanner.Minus = 18;

function PgnScannerPosition(value)
{
  if (value)
  {
    this.assign(value);
  }
}

PgnScannerPosition.prototype.isNewLine = true;
PgnScannerPosition.prototype.line = 0;
PgnScannerPosition.prototype.column = 0;

PgnScannerPosition.prototype.assign = function(value)
{
  this.isNewLine = value.isNewLine;
  this.line = value.line;
  this.column = value.column;
}

function _PgnGameState() {}

_PgnGameState.getGameState = function(game)
{
  if (game._state == null)
  {
    _PgnGameState.calculateGameState(game);
  }
  
  var result = new PgnState;
  
  Util.deepCopy(game._state, result);
  
  return result;
}

_PgnGameState.getMoveState = function(move)
{
  if (move._state == null)
  {
    // Get list of moves to check.
    var list = new Array;
    var item = move;
    
    while(true)
    {
      list.push(item);
      item = item.prevMove ? item.prevMove : 
        item.parentMove ? item.parentMove.prevMove : null;
   
      if ((item == null) || (item._state != null))
      {
        break;
      }
    }
    
    while((item = list.pop()) != null)
    {
      _PgnGameState.calculateState(item);
    }
  }
  
  var result = new PgnState;
  
  Util.deepCopy(move._state, result);
  
  return result;
}

_PgnGameState.calculateGameState = function(game)
{
  // Initialize root state. Look for FEN tag or setup default position
  var state = new PgnState;
  var fen = game.tags["FEN"];
  
  state.board = new Array(64);
  
  if (fen)
  {
    // Read FEN
    var coord = new Coord;
    var length = fen.length;
    var c;
    
    // Chessbase format enumerates fields from last line to first!
    // I believe this is Chessbase bug.
    // They use letters in opposite manner to describe pieces.
    if (game.document._chessBaseFormat)
    {
      coord.y = 7;
    }
    
ReadFen:      
    for(var pos = 0; pos < length; pos++)
    {
      c = fen.charAt(pos);
     
      switch(c)
      {
        case "1": case "2": case "3": case "4": case "5": case "6": case "7": case "8":
        {
          coord.x += parseInt(c);
        
          break;
        }
        case "/":
        {
          // Compensation of chessbase bug
          if (game.document._chessBaseFormat)
          {
            coord.y--;
          }
          else
          {
            coord.y++;
          }
          
          coord.x = 0;
        
          break;
        }
        case "k": case "q": case "r": case "b": case "n": case "p":
        case "K": case "Q": case "R": case "B": case "N": case "P":
        {
          if ((coord.x >= 8) || (coord.y >= 8))
          {
            throw new Error("Invalid FEN format");
          }
          
          // Compensation of chessbase bug
          if (game.document._chessBaseFormat)
          {
            if (c >= "a")
            {
              c = c.toUpperCase();
            }
            else
            {
              c = c.toLowerCase();
            }
          }

          var item = state[c];
          
          if (!item)
          {
            state[c] = item = new Array;
          }
          
          item.push(String(coord));
          state.board[coord.x + coord.y * 8] = c;
          coord.x++;
          
          break;
        }
        case " ":
        {
          break ReadFen;
        }
        default:
        {
          throw new Error("Invalid FEN format");
        }
      }
    }
  }
  else
  {
    // default position
    state["k"]=new Array("e1");
    state["q"]=new Array("d1");
    state["r"]=new Array("a1", "h1");
    state["b"]=new Array("c1", "f1");
    state["n"]=new Array("b1", "g1");
    state["p"]=new Array("a2", "b2", "c2", "d2", "e2", "f2", "g2", "h2");
    state["K"]=new Array("e8");
    state["Q"]=new Array("d8");
    state["R"]=new Array("a8", "h8");
    state["B"]=new Array("c8", "f8");
    state["N"]=new Array("b8", "g8");
    state["P"]=new Array("a7", "b7", "c7", "d7", "e7", "f7", "g7", "h7");
    state.board[0] = "r";
    state.board[1] = "n";
    state.board[2] = "b";
    state.board[3] = "q";
    state.board[4] = "k";
    state.board[5] = "b";
    state.board[6] = "n";
    state.board[7] = "r";
    state.board[8] = "p";
    state.board[9] = "p";
    state.board[10] = "p";
    state.board[11] = "p";
    state.board[12] = "p";
    state.board[13] = "p";
    state.board[14] = "p";
    state.board[15] = "p";
    state.board[48] = "P";
    state.board[49] = "P";
    state.board[50] = "P";
    state.board[51] = "P";
    state.board[52] = "P";
    state.board[53] = "P";
    state.board[54] = "P";
    state.board[55] = "P";
    state.board[56] = "R";
    state.board[57] = "N";
    state.board[58] = "B";
    state.board[59] = "Q";
    state.board[60] = "K";
    state.board[61] = "B";
    state.board[62] = "N";
    state.board[63] = "R";
  }
  
  game._state = state;
}

_PgnGameState.moveRe = new RegExp(
  "(O-O-O)|(O-O)|" +
  "([KQRBNP]?)" +
  "(?:([a-h][1-8]|[a-h]|[1-8])([-x]?)([a-h][1-8])|" +
  "(x?)([a-h][1-8]))=?([QRBN]?)");

_PgnGameState.calculateState = function(move)
{
  var prev = move.prevMove ? move.prevMove : 
    move.parentMove ? move.parentMove.prevMove : null;
  var state = prev ? _PgnGameState.getMoveState(prev) : 
    _PgnGameState.getGameState(move.game);
  var board = state.board;
  
ParseMove:  
  {
    // Perform move
    var moveDesc = move.move.match(_PgnGameState.moveRe);

MoveError:    
    if (moveDesc != null)
    {
      var from;
      var to;
      
      if (moveDesc[1])
      {
        var kPiece = move.whiteMove ? "k" : "K";
        var rPiece = move.whiteMove ? "r" : "R";
        
        if (move.whiteMove)
        {
          from = "e1";
          to = "c1";
        }
        else
        {
          from = "e8";
          to = "c8";
        }
        
        var items = state[kPiece];
        
        if (!items || (items.length != 1) || (items[0] != from))
        {
          break MoveError;
        }
        
        items[0] = to;
        items = state[rPiece];
        
        if (!items)
        {
          break MoveError;
        }

CastleQS:
        {        
          for(var j = 0, c = items.length; j < c; j++)
          {
            if (items[j] == (move.whiteMove ? "a1" : "a8"))
            {
              items.splice(j, 1);
         
              break CastleQS;
            }
          }
         
          break MoveError;
        }
        
        items.push(move.whiteMove ? "d1" : "d8");

        if (move.whiteMove)
        {
          board[0] = null;
          board[2] = kPiece;
          board[3] = rPiece;
          board[4] = null;
        }
        else
        {
          board[56] = null;
          board[58] = kPiece;
          board[59] = rPiece;
          board[60] = null;
        }
      }
      else if (moveDesc[2])
      {
        var kPiece = move.whiteMove ? "k" : "K";
        var rPiece = move.whiteMove ? "r" : "R";
        
        if (move.whiteMove)
        {
          from = "e1";
          to = "g1";
        }
        else
        {
          from = "e8";
          to = "g8";
        }
        
        var items = state[kPiece];
        
        if (!items || (items.length != 1) || (items[0] != from))
        {
          break MoveError;
        }
        
        items[0] = to;
        items = state[rPiece];
        
        if (!items)
        {
          break MoveError;
        }

CastleKS:
        {        
          for(var j = 0, c = items.length; j < c; j++)
          {
            if (items[j] == (move.whiteMove ? "h1" : "h8"))
            {
              items.splice(j, 1);
              
              break CastleKS;
            }
          }
          
          break MoveError;
        }
        
        items.push(move.whiteMove ? "f1" : "f8");

        if (move.whiteMove)
        {
          board[4] = null;
          board[5] = rPiece;
          board[6] = kPiece;
          board[7] = null;
        }
        else
        {
          board[60] = null;
          board[61] = rPiece;
          board[62] = kPiece;
          board[63] = null;
        }
      }
      else
      {
        var p = moveDesc[3];
        
        if (!p)
          p = "P";

        from = moveDesc[4];
        to = moveDesc[6];
        if (!to)
        {
          from = null;
          to = moveDesc[8];
        }
        
        var piece = move.whiteMove ? p.toLowerCase() : p;
        var items = state[piece];
        var length;

        if (!items || ((length = items.length) == 0))
        {
          break MoveError;
        }

        var take = moveDesc[from ? 5 : 7] == "x";
        var itemIndex = 0;
        var toCoord = new Coord(to);
        var fromCoord;

DeletePiece:    
        if (length == 1)
        {
          from = items[0];
          fromCoord = new Coord(from);
        }
        else
        {
           var fromPos = from;
           
CheckItems:
          for(; itemIndex < length; itemIndex++)
          {
            from = items[itemIndex];
            fromCoord = new Coord(from);
            if (fromPos && (from.indexOf(fromPos) == -1))
              continue;
            
            var d = Coord.minus(toCoord, fromCoord);
                
            switch(p)
            {
              case "K":
              {
                if ((d.x == 0) && (Math.abs(d.y) == 1) || 
                  (Math.abs(d.x) == 1) && (Math.abs(d.y) <= 1))
                {
                  break DeletePiece;
                }
                
                break;
              }
              case "Q":
              {
                if ((d.x != 0) && (d.y != 0) && (Math.abs(d.x) != Math.abs(d.y)))
                {
                  break;
                }

                var dx = d.x > 0 ? 1 : d.x < 0 ? -1 : 0;
                var dy = d.y > 0 ? 1 : d.y < 0 ? -1 : 0;
                var x = fromCoord.x + dx;
                var y = fromCoord.y + dy;
                
                while((x != toCoord.x) || (y != toCoord.y))
                {
                  if (board[x + y * 8])
                  {
                    continue CheckItems;
                  }
                  
                  x += dx;
                  y += dy;
                }
                
                break DeletePiece;
              }
              case "R":
              {
                if ((d.x != 0) && (d.y != 0))
                {
                  break;
                }

                var dx = d.x > 0 ? 1 : d.x < 0 ? -1 : 0;
                var dy = d.y > 0 ? 1 : d.y < 0 ? -1 : 0;
                var x = fromCoord.x + dx;
                var y = fromCoord.y + dy;
                
                while((x != toCoord.x) || (y != toCoord.y))
                {
                  if (board[x + y * 8])
                    continue CheckItems;
                  x += dx;
                  y += dy;
                }
                
                break DeletePiece;
              }
              case "B":
              {
                if (Math.abs(d.x) != Math.abs(d.y))
                {
                  break;
                }

                var dx = d.x > 0 ? 1 : -1;
                var dy = d.y > 0 ? 1 : -1;
                var x = fromCoord.x + dx;
                var y = fromCoord.y + dy;
                
                while(x != toCoord.x)
                {
                  if (board[x + y * 8])
                  {
                    continue CheckItems;
                  }
                  
                  x += dx;
                  y += dy;
                }
                
                break DeletePiece;
              }
              case "N":
              {
                if ((Math.abs(d.x) == 1) && (Math.abs(d.y) == 2) || 
                  (Math.abs(d.x) == 2) && (Math.abs(d.y) == 1))
                {
                  break DeletePiece;
                }
                
                break;
              }
              case "P":
              {
                if (take)
                {
                  if ((Math.abs(d.x) == 1) && 
                    (d.y == (move.whiteMove ? 1 : -1)))
                  {
                    break DeletePiece;
                  }
                }
                else if (d.x == 0)
                {
                  if (move.whiteMove)
                  {
                    if ((d.y == 1) || (d.y == 2) && 
                      (!board[fromCoord.x + (fromCoord.y + 1) * 8]))
                    {
                      break DeletePiece;
                    }
                  }
                  else
                  {
                    if ((d.y == -1) || (d.y == -2) && 
                      (!board[fromCoord.x + (fromCoord.y - 1) * 8]))
                    {
                      break DeletePiece;
                    }
                  }
                }
                
                break;
              }
            }
          }
          
          break MoveError;
        }
        
        items.splice(itemIndex, 1);

DeleteEnemy:
        if (take)
        {
          var target = new Coord;
          
          target.x = toCoord.x;
          target.y = toCoord.y;
          
          var enemy = board[target.x + target.y * 8];
          
FindEnemy:  
          if (!enemy)
          {
            // Check passant target
            if (p == "P")
            {
              target.x = toCoord.x;
              target.y = fromCoord.y;
              enemy = board[target.x + target.y * 8];
              
              if (enemy)
              {
                board[target.x + target.y * 8] = null;
                
                break FindEnemy;
              }
            }
            
            break MoveError;
          }
          
          var enemyItems = state[enemy];
          
          if (!enemyItems)
          {
            break MoveError;
          }
            
          var targetPos = String(target);
          
          for(var i = 0, c = enemyItems.length; i < c; i++)
          {
            if (enemyItems[i] == targetPos)
            {
              enemyItems.splice(i, 1);
              
              break DeleteEnemy;
            }
          }
          
          break MoveError;
        }
        
        // Promotion
        if ((p == "P") && (move.whiteMove ? toCoord.y == 7 : toCoord.y == 0))
        {
          if (items.length == 0)
          {
            delete state[piece];
          } 
          
          piece = moveDesc[9];
          
          if (move.whiteMove)
          {
            piece = piece.toLowerCase();
          }
          
          if (!state[piece])
          {
            state[piece] = new Array;
          }
        }
        
        state[piece].push(to);
        board[fromCoord.x + fromCoord.y * 8] = null;
        board[toCoord.x + toCoord.y * 8] = piece;
      }
      
      break ParseMove;
    }
    
    throw new Error("Invalid move format");
  }
  
  var arrow = new Object;
  
  arrow.from = from;
  arrow.to = to;
  state["a"] = new Array(arrow);
  move._state = state;
}

/*
  Board coordinate.
*/
function Coord(value)
{
  if (value)
  {
    this.x = value.charCodeAt(0) - "a".charCodeAt(0);
    this.y = value.charCodeAt(1) - "1".charCodeAt(0);
  }
}

Coord.prototype.x = 0;
Coord.prototype.y = 0;

/*
  Subtracts two board coordinates scalarly.
*/
Coord.minus = function(a, b)
{
  var result = new Coord;
  
  result.x = a.x - b.x;
  result.y = a.y - b.y;

  return result;
}

Coord.prototype.toString = function()
{
  return String.fromCharCode("a".charCodeAt(0) + this.x, "1".charCodeAt(0) + this.y);
}