//------------------------------------------------------------------------
// © 2001 - François Marques - Francois.Marques@freesbee.fr
//------------------------------------------------------------------------

//========================================================================
// Déclaration des variables contenant les images
//========================================================================
var helpon = new Image();
helpon.src = "blank.gif";
var helpoff = new Image();
helpoff.src = "blank.gif";

var eyeon = new Image();
eyeon.src = "blank.gif";
var eyeoff = new Image();
eyeoff.src = "blank.gif";

var blank = new Image();
blank.src = "images/blank.gif";

var emailon = new Image();
emailon.src = "blank.gif";
var emailoff = new Image();
emailoff.src = "blank.gif";

var lroton = new Image();
lroton.src = "blank.gif";
var lrotoff = new Image();
lrotoff.src = "blank.gif";

var rroton = new Image();
rroton.src = "blank.gif";
var rrotoff = new Image();
rrotoff.src = "blank.gif";

var hsymon = new Image();
hsymon.src = "blank.gif";
var hsymoff = new Image();
hsymoff.src = "blank.gif";

var vsymon = new Image();
vsymon.src = "blank.gif";
var vsymoff = new Image();
vsymoff.src = "blank.gif";

//========================================================================
// Déclaration de fonctions pour le prototype Array destiné à contenir
// un niveau du jeu Sokoban.
//========================================================================
// Les éléments constituants le niveau sont stockés de la façon suivante :
// (abscysse, ordonnée, item {,item...})
// Le premier item est destiné à représenter le niveau dans son état initial,
// les suivants permettent de stocker le même niveau dans des états différents.
// Le codage des items est 0 pour vide, 1 pour Sokoban et 2 pour une caisse.
// Il n'y a pas d'item pour un mur car les emplacements des murs ne sont pas
// stockés : on sait qu'il y a un mur en (x,y) s'il n'y a aucun éléments ayant
// ces coordonnées dans le tableau.
//========================================================================

// Retourne l'abscisse maximale du tableau.
function array_xmax( )
{ var i, xmax=this.items[0][0];
  for (i=1 ; i<this.items.length ; i++) { if (xmax<this.items[i][0]) xmax=this.items[i][0]; }
  return xmax;
}

// Retourne l'abscisse minimale du tableau.
function array_xmin( )
{ var i, xmin=this.items[0][0];
  for (i=1 ; i<this.items.length ; i++) { if (xmin>this.items[i][0]) xmin=this.items[i][0]; }
  return xmin;
}

// Retourne l'ordonnée maximale du tableau.
function array_ymax( )
{ var i, ymax=this.items[0][1];
  for (i=1 ; i<this.items.length ; i++) { if (ymax<this.items[i][1]) ymax=this.items[i][1]; }
  return ymax;
}

// Retourne l'ordonnée minimale du tableau.
function array_ymin( )
{ var i, ymin=this.items[0][1];
  for (i=1 ; i<this.items.length ; i++) { if (ymin>this.items[i][1]) ymin=this.items[i][1]; }
  return ymin;
}

// Trouve Sokoban dans le niveau niv et place son indice dans iSoko.
function array_foundSoko( niv )
{ var i=0;
  for (i=0 ; i<this.items.length ; i++) if (this.items[i][niv+2]==1) { this.iSoko=i; return i; }
  this.iSoko=-1;
  return -1;
}

// Retourne l'indice de l'élément de coordonnées (x,y) dans le tableau.
// Si cet élément n'est pas trouvé, retourne -1;
function array_indexOf( x, y )
{ var i=0;
  for (i=0 ; i<this.items.length ; i++) { if ((x==this.items[i][0]) && (y==this.items[i][1])) return i }
  return -1;
}

// Retourne l'indice de l'élément de coordonnées (x,y) dans le tableau.
// Si cet élément n'est pas trouvé, retourne -1;
function array_indexRel( dx, dy )
{ return this.indexOf( this.items[this.iSoko][0]+dx, this.items[this.iSoko][1]+dy )
}

// Retourne une chaine contenant une représentation au format XSB du niveau.
// niv_init est utilisé pour avoir la situation initiale du niveau et ni_final
// pour la position des caisses une fois la solution atteinte.
function array_draw( niv_init, niv_final )
{ if ( !(this.size( )>0) ) return "";
  var xmin=this.xmin();
  var xmax=this.xmax();
  var ymin=this.ymin();
  var ymax=this.ymax();
  var s='';
  var raw=0, col=0, i=0;
  for ( raw=ymax+1 ; raw>=ymin-1 ; raw-- )
  { for ( col=xmin-1 ; col<=xmax+1 ; col++ )
    { i=this.indexOf( col, raw );
      if (i<0)
      { s=s+'#';
      } else {
        if (this.items[i][niv_init+2]==0) if (this.items[i][niv_final+2]==2) s=s+'.'; else s=s+' ';
        if (this.items[i][niv_init+2]==1) if (this.items[i][niv_final+2]==2) s=s+'+'; else s=s+'@';
        if (this.items[i][niv_init+2]==2) if (this.items[i][niv_final+2]==2) s=s+'*'; else s=s+'$';
      }
    }
    s=s+"\r\n";
  }
  return s;
}

// Insere l'item dans le tableau à la position (x,y). Niv correspond au nombre de version
// du niveau.
// S'il existe déjà un item de coordonnées (x,y) la fonction retourne son indexe mais ne le
// modifie pas !
function array_insert( x, y, item, niv)
{ var i=this.indexOf( x, y );
  if ( i<0 )
  { var P=new Array(niv+2);
    P[0]=x; P[1]=y; for( i=0 ; i<niv ; i++ ) P[i+2]=item;
    i=this.items.length
    this.items[i]=P;
    return i;
  }
  return i;
}

// Identique à insert, mais la position d'insertion est relative à la position
// du Sokoban.
function array_insertRel( dx, dy, item, niv)
{ return this.insert( this.items[this.iSoko][0]+dx, this.items[this.iSoko][1]+dy, item, niv );
}

// Retourne le nombre de caisses dans le tableau
function array_countBoxes( )
{ var i=0, nbBoxes=0;
  for( i=0 ; i<this.items.length ; i++ ) if (this.items[i][2]==2) nbBoxes++;
  return nbBoxes;
}

// Retourne le nombre de couloirs dans le niveau
function array_size( )
{ return this.items.length;
}

// Opère une rotation à gauche sur le tableau
function array_leftRotate( )
{ var i, v;
  for( i=0 ; i<this.items.length ; i++ ) {
    v=this.items[i][0];
    this.items[i][0]=this.items[i][1];
    this.items[i][1]=-v;
  }
}

// Opère une rotation à droite sur le tableau
function array_rightRotate( )
{ var i, v;
  for( i=0 ; i<this.items.length ; i++ ) {
    v=this.items[i][0];
    this.items[i][0]=-this.items[i][1];
    this.items[i][1]=v;
  }
}

// Opère une symétrie d'axe horizontal sur le tableau
function array_horizontalSymetrie( )
{ var i;
  for( i=0 ; i<this.items.length ; i++ ) this.items[i][1]=-this.items[i][1];
}

// Opère une symétrie d'axe vertical sur le tableau
function array_verticalSymetrie( )
{ var i;
  for( i=0 ; i<this.items.length ; i++ ) this.items[i][0]=-this.items[i][0];
}

// Déclaration de l'objet oLevel
function oLevel( )
{ this.iSoko = -1;
  this.items = new Array();

  this.xmin = array_xmin;
  this.xmax = array_xmax;
  this.ymin = array_ymin;
  this.ymax = array_ymax;
  this.indexOf = array_indexOf;
  this.indexRel = array_indexRel;
  this.foundSoko = array_foundSoko;
  this.insert = array_insert;
  this.insertRel = array_insertRel;
  this.draw = array_draw;
  this.boxes = array_countBoxes;
  this.size = array_size;
  this.leftRotate = array_leftRotate;
  this.rightRotate = array_rightRotate;
  this.horizontalSymetrie = array_horizontalSymetrie;
  this.verticalSymetrie = array_verticalSymetrie;
}

// Déclaration des variables globales
var level=new oLevel(), level2=new oLevel();
var iLastBox, Moves, Pushes, LinePushes, BoxChanges, ShelvingSteps;
var ready=false, aboutBoxesPushes='', aboutBoxesChanges='';

//========================================================================
// Déclaration de fonctions pour le prototype String destiné à contenir
// un lurd.
//========================================================================

// Echange les caractères dans la première chaine par ceux dans la seconde
// placés à la même position.
function string_swap( s1, s2 )
{ var i=0, j=0, s="";
  for( i=0 ; i<this.string.length ; i++ )
  { j=s1.indexOf( this.string.charAt(i) );
    if (j<0)
    { s=s+this.string.charAt(i);
    } else {
      s=s+s2.charAt(j);
    }
  }
  this.string=s;
  return s;
}

// Opère une rotation à gauche sur le lurd
function string_leftRotate( )
{ return this.swap( "lurdLURD", "urdlURDL" );
}

// Opère une rotation à droite sur le lurd
function string_rightRotate( )
{ return this.swap( "lurdLURD", "dlurDLUR" );
}

// Opère une symétrie d'axe horizontal sur le lurd
function string_horizontalSymetrie( )
{ return this.swap( "lurdLURD", "ldruLDRU" );
}

// Opère une symétrie d'axe vertical sur le lurd
function string_verticalSymetrie( )
{ return this.swap( "lurdLURD", "ruldRULD" );
}

// Effectue l'expension du format CmpLuRd vers le format LuRd orinaire
function string_expand( )
{ var i=0, j=0, v=0, numbers="0123456789", s="", good_chars="0123456789lurdLURD";
  for( i=0 ; i<this.string.length ; i++ )
  { if (good_chars.indexOf( this.string.charAt(i) )>=0)
	  { j = numbers.indexOf( this.string.charAt(i) );
	    if (j>=0)
	    { v = v*10+j;
	    } else {
	    	if (v==0)
	    	{ v = 1;
	      }
	      for( ; v>0 ; v-- )
	      { s = s+this.string.charAt(i);
	      }
	    } 
	  }
	}
  this.string=s;
  return s;
}

// Effectue la compression du format LuRd orinaire vers le format CmpLuRd
function string_condense( )
{ var i=0, j=0, v=1, s="";
  for( i=1 ; i<this.string.length ; i++ )
  { if ( this.string.charAt(i) == this.string.charAt(i-1) )   
    { v++;
    } else {
    	if (v==1)
    	{ s=s+this.string.charAt(i-1);
      } else {
      	s=s+v+this.string.charAt(i-1);
      }
    	v=1;
    } 
  }
 	if (v==1)
 	{ s=s+this.string.charAt(this.string.length-1);
   } else {
   	s=s+v+this.string.charAt(this.string.length-1);
   }
  this.string=s;
  return s;
}

// Déclaration de l'objet oLurd
function oLurd( s )
{ this.string = ""+s;
  this.swap = string_swap;
  this.leftRotate = string_leftRotate;
  this.rightRotate = string_rightRotate;
  this.horizontalSymetrie = string_horizontalSymetrie;
  this.verticalSymetrie = string_verticalSymetrie;
  this.expand = string_expand;
  this.condense = string_condense;
}

//========================================================================
// Fonctions destinées à la conversion du lurd
//========================================================================

//------------------------------------------------------------------------
// Analyse de la description du niveau et stockage dans level2
//------------------------------------------------------------------------
function initialiseConversion( )
{ level2=new oLevel();
  var s=''+document.formulaire.elements['LEVEL'].value;
  var i=0, j=0, l=0, c=0, Ok=true;
  var nbSoko=0, nbBoxes=0, nbTargets=0;

  // On cherche la première ligne qui commence par un bon carractère :
  for( i=0 ; (i<s.length) && isBadChar(s.charAt(i)) ; )
  { for( ; (i<s.length) && (s.charCodeAt(i)!=10) ; i++ ); i++;
  }

  // Tant que les débuts de ligne correspondent à la description d'un niveau...
  while ( (i<s.length) && Ok )
  { for( ; (i<s.length) && (s.charCodeAt(i)!=10) ; i++ ); i++; // On efface jusqu'à la fin de la ligne...
    // Analyse d'une nouvelle ligne...
    Ok=false; c=0; l--;
    // On cherche le premier mur :
    for( ; (i<s.length) && (s.charAt(i)==' ') ; i++ ) c++ ;
    for( ; (i<s.length) && !isBadChar(s.charAt(i)) ; i++ )
    { if (s.charAt(i)!="#") Ok=true; // La ligne contient au moins un caractère utile.
       c++;
           if (s.charAt(i)==" ") level2.insert( c, l, 0, 3);
      else if (s.charAt(i)=="$") { j=level2.insert( c, l, 2, 3); level2.items[j][4]=0; nbBoxes++; }
      else if (s.charAt(i)=="*") { level2.insert( c, l, 2, 3); nbBoxes++ ; nbTargets++; }
      else if (s.charAt(i)=="+") { j=level2.insert( c, l, 1, 3); level2.items[j][4]=2; nbSoko++; nbTargets++ }
      else if (s.charAt(i)=="@") { j=level2.insert( c, l, 1, 3); level2.items[j][4]=0; nbSoko++; }
      else if (s.charAt(i)==".") { j=level2.insert( c, l, 0, 3); level2.items[j][4]=2; nbTargets++; }
    }
  }
  if (nbSoko==0) { message( errSokoNotFound ); return -1; }
  if (nbSoko>1)  { message( errToManySoko ); return -1; }
  if (nbBoxes<1) { message( errNoBox ); return -1; }
  if (nbBoxes!=nbTargets) { message( errBadNumberOfTargets ); return -1; }
  level2.foundSoko( 0 );
  return 0;
}

//------------------------------------------------------------------------
// Vérification : le mouvement en cours d'analyse est-il réalisable
// dans la position actuelle ? Si oui, est-ce un déplacement ou une
// poussée.
//------------------------------------------------------------------------
function trySokoMove( dir )
{ var dx=0, dy=0;
  dir=makeMove(dir);
       if (dir=='u') dy=+1;
  else if (dir=='d') dy=-1;
  else if (dir=='r') dx=+1;
  else if (dir=='l') dx=-1;
  else return '';
  var i=level2.indexRel( dx, dy );

  if (i<0) return 'X';
  if (level2.items[i][3]==0)         // Le mouvement est possible...
  { level2.items[i][3]=1;            // On place sokoban sur sa nouvelle case
    level2.items[level2.iSoko][3]=0; // Et on l'efface de son ancienne position.
    level2.iSoko=i;
    return dir;
  }

  // Il y a une caisse. Peut-on la pousser ?
  var i2=level2.indexRel( 2*dx, 2*dy );
  if ( (i2<0) || (level2.items[i2][3]!=0) ) return 'X';
  level2.items[i][3]=1;            // On place sokoban sur sa nouvelle case
  level2.items[level2.iSoko][3]=0; // Et on l'efface de son ancienne position.
  level2.items[i2][3]=2;           // On place la caisse sur sa nouvelle case
  level2.iSoko=i;
  return dir.toUpperCase();
}

//------------------------------------------------------------------------
// Fonction de convertion de solution
//------------------------------------------------------------------------
function convert( )
{ var soluce=''+document.formulaire.elements['SOLUTION'].value.toLowerCase( );
  var Ok=true, R='', m=0, s='';

  initialiseConversion( );
  soluce=soluce.toLowerCase( );

  // Exécution de la solution proposée
  for( m=0 ; (m<soluce.length) && Ok ; m++)
  { R=trySokoMove( soluce.charAt(m) );
    Ok=(R!='X');
    s=s+R;
  }
  if ( Ok==false )
  { message( errBadSolution );
    return Ok;
  }
  // Vérification : A-t-on réellement atteint la solution ?
  for( m=0 ; (m<level2.size()) && Ok ; m++ )
  { Ok=((level2.items[m][3]!=2) || (level2.items[m][4]==2));
  }
  if ( Ok==false ) message( warnPartialSolution );
  document.formulaire.elements['SOLUTION'].value=s;
  return true;
}

//========================================================================
// Fonctions destinées à l'analyse du lurd étendu
//========================================================================

// Initialisation des variables globales.
function initialise( )
{ level=new oLevel();
  level.insert( 0, 0, 1, 4 ) // On pace Sokoban dans le tableau.
  level.items[0][4]=0;
  level.items[0][5]=0;
  level.foundSoko( 0 )
  iLastBox=-1; Moves=0; Pushes=0; LinePushes=0; BoxChanges=0; ShelvingSteps=0;
  return;
}

// Déplace Sokoban dans la direction passée en paramêtre
// Si le déplacement est impossible retourne -1.
function SokoMove( dir )
{ var dx=0, dy=0;
  if (dir=='u') dy=+1;
  else if (dir=='d') dy=-1;
  else if (dir=='r') dx=+1;
  else if (dir=='l') dx=-1;
  else return -1;
  var i=level.insertRel( dx, dy, 0, 4);
  if (level.items[i][3]==0)        // Le mouvement est possible...
  { level.items[i][3]=1;           // On place sokoban sur sa nouvelle case
    level.items[level.iSoko][3]=0; // Et on l'efface de son ancienne position.
    level.iSoko=i;
    return i;
  }
  return -1;
}

// Effectue une poussée dans la direction passée en paramêtre
// Si la poussée est impossible retourne -1.
function SokoPush( dir )
{ var dx=0, dy=0;
  Pushes++;
  if (dir=='U') dy=+1;
  else if (dir=='D') dy=-1;
  else if (dir=='R') dx=+1;
  else if (dir=='L') dx=-1;
  else return -1;

  var i1=level.indexRel( dx, dy );
  if (i1<0)
  { i1=level.insertRel( dx, dy, 2, 4 );       // On ajoute une caisse dans le tableau initial.
    level.items[i1][4]=0;
    level.items[i1][5]=0;
  }
  var i2=level.insertRel( 2*dx, 2*dy, 0, 4 ); // On ajoute une case vide dans le tableau initial.
  if ((level.items[i1][3]==2) && (level.items[i2][3]==0)) // Le mouvement est possible...
  { level.items[i1][3]=1;                     // On place sokoban sur sa nouvelle case
    level.items[level.iSoko][3]=0;            // Et on l'efface de son ancienne position.
    level.items[i2][3]=2;                     // On place la caisse sur sa nouvelle case
    level.items[i2][4]=level.items[i1][4]+1;
    level.items[i1][4]=0;
    level.items[i2][5]=level.items[i1][5];
    level.items[i1][5]=0;
    level.iSoko=i1;
    if (i1!=iLastBox)
    { BoxChanges++;
      level.items[i2][5]++;
    }
    iLastBox=i2;
    return i1;
  }
  return -1;
}


//------------------------------------------------------------------------
// Fonction d'analyse de la solution
//------------------------------------------------------------------------
function analyse( )
{ clearResults();
  var Ok=true, m=0;

  if (document.formulaire.elements['LEVEL'].value.length>0) Ok=convert( );
  if (Ok==false) return;
  initialise( );

  var s=new oLurd( ""+document.formulaire.elements['SOLUTION'].value );  
  var soluce="";
  s.expand( );
  for(Moves=0 ; Moves<s.string.length ; Moves++ )
  { if ( isValid(s.string.charAt(Moves)) )
    { soluce=soluce+s.string.charAt(Moves);
    }
    else
    { // On efface jusqu'à la fin de la ligne...
      for( ; (Moves<s.string.length) && (s.string.charCodeAt(Moves)!=10) ; Moves++ );
    }
  }

  // Recherche de la dernière poussée :
  Moves=soluce.length;
  while ( (Moves>0) && isNotPush(soluce.charAt(Moves-1)) ) Moves--;
  soluce=soluce.substring( 0, Moves );

  while ( (Ok==true) && (m<Moves) )
  { Ok = (!isValid(soluce.charAt(m))) || !( ( SokoMove(soluce.charAt(m))<0 ) && ( SokoPush(soluce.charAt(m))<0) );
    m++;
  }
  if ( Ok==true )
  { // Décompte du nombre de poussées en ligne :
    if (isPush(soluce.charAt(0))) { LinePushes=1; ShelvingSteps=1; }
    for( i=1 ; i<Moves ; i++ )
    {
      if (isPush(soluce.charAt(i)))
      { if ((soluce.charAt(i)!=soluce.charAt(i-1))) LinePushes++;
        if (!isPush(soluce.charAt(i-1))) ShelvingSteps++;
      }
    }
    s.string=soluce;
    if (document.formulaire.elements['CBCONDENSE'].checked)
    { s.condense( );
    }
    
    document.formulaire.elements['LEVEL2'].value=level.draw( 0, 1 );
    document.formulaire.elements['SIZE'].value=level.size( );
    document.formulaire.elements['BOXES'].value=level.boxes( );
    document.formulaire.elements['MOVES'].value=Moves;
    document.formulaire.elements['PUSHES'].value=Pushes;
    document.formulaire.elements['LINEPUSHES'].value=LinePushes;
    document.formulaire.elements['BOXCHANGES'].value=BoxChanges;
    document.formulaire.elements['SHELVINGSTEPS'].value=ShelvingSteps;
    document.formulaire.elements['SOLUTION'].value=s.string;
  } else {
    message( errBadLurd );
  }

  var b=0;
  for ( i=0 ; i<level.size() ; i++ )
  { if (level.items[i][3]==2)
    { b++;
      aboutBoxesPushes=aboutBoxesPushes+msgCaisse+b+' : '+level.items[i][4]+'<BR>';
      aboutBoxesChanges=aboutBoxesChanges+msgCaisse+b+' : '+level.items[i][5]+'<BR>';
    }
  }
  ready=true;
  document.images['view1'].src=eyeoff.src;
  document.images['view2'].src=eyeoff.src;

  return;
}

//========================================================================
// Fonctions diverses
//========================================================================
function message( msg ) { document.formulaire.elements['MESSAGE'].value=msg; }
function displayLevel( ) { document.formulaire.elements['LEVEL2'].value=level.draw( 0, 1 ); }

function leftRotate( )
{ level.leftRotate( );
  var s=new oLurd( document.formulaire.elements['SOLUTION'].value );
  document.formulaire.elements['SOLUTION'].value=s.leftRotate( );
  displayLevel( );
}

function rightRotate( )
{ level.rightRotate( );
  var s=new oLurd( document.formulaire.elements['SOLUTION'].value );
  document.formulaire.elements['SOLUTION'].value=s.rightRotate( );
  displayLevel( );
}

function horizontalSymetrie( )
{ level.horizontalSymetrie( );
  var s=new oLurd( document.formulaire.elements['SOLUTION'].value );
  document.formulaire.elements['SOLUTION'].value=s.horizontalSymetrie( );
  displayLevel( );
}

function verticalSymetrie( )
{ level.verticalSymetrie( );
  var s=new oLurd( document.formulaire.elements['SOLUTION'].value );
  document.formulaire.elements['SOLUTION'].value=s.verticalSymetrie( );
  displayLevel( );
}

// Vérifie si un caractère est succeptible d'être utilisé dans la
// représentation d'un niveau.
function isBadChar( c ) { return ' #$*.@+'.indexOf( c )<0; }

// Convertie un caractère représentant un mouvement dans le standard lurd
function makeMove( c )
{ var i='lurd'.indexOf( c);
  if (i<0) return '';
  return 'lurd'.charAt(i%4);
}

// Vérification de la nature d'un mouvement :
function isPush( c ) { return (c=='L') || (c=='U') || (c=='R') || (c=='D'); }
function isNotPush ( c ) { return !isPush( c ); }
function isValid ( c ) { return isPush( c.toUpperCase() ); }

// Netoyage des champs destinés à recevoir les résultats :
function clearResults( )
{
  document.formulaire.elements['LEVEL2'].value='';
  document.formulaire.elements['SIZE'].value='';
  document.formulaire.elements['BOXES'].value='';
  document.formulaire.elements['MOVES'].value='';
  document.formulaire.elements['PUSHES'].value='';
  document.formulaire.elements['LINEPUSHES'].value='';
  document.formulaire.elements['BOXCHANGES'].value='';
  document.formulaire.elements['SHELVINGSTEPS'].value='';
  document.formulaire.elements['MESSAGE'].value='';
  aboutBoxesPushes='';
  aboutBoxesChanges='';
  ready=false;
  document.images['view1'].src=blank.src;
  document.images['view1'].src=blank.src;
}

// Netoyage des champs destinés à recevoir les résultats :
function updateSolution( )
{ var s=new oLurd( document.formulaire.elements['SOLUTION'].value );
  if (document.formulaire.elements['CBCONDENSE'].checked)
  { s.condense( );
  } else {
  	s.expand( );
  }
  document.formulaire.elements['SOLUTION'].value=s.string;
}