/*
 * Module ID: lab2.cpp
 * Titre    : Module principal du Lab 2 du cours ELE-440
 * Utilite  : Solution du projet P3 de la section 3.3
 *            du livre 'Data structures and program design in C'
 *            en eliminant la recursivite du probleme a l'aide
 *            de stack.
 *
 * Auteur   : Olivier Langlois <olivier@olivierlanglois.net>
 * Date     : 4 Fevrier 1998
 *
 */

#ifdef __BORLANDC__
// Indique au compilateur que les instances de template utilisees dans ce
// module seront definies dans un autre module.
#pragma option -Jgx
#endif

/*
 * Fichiers d'entetes
 */
#include "lab2ches.h"
#include "signon.h"
#include <stdlib.h>   /* Pour rand()   */
#include <time.h>

#ifdef WIN32
#include "diagwin.h"
#else
#include "diagdos.h"
#endif

/*
 * Un stack statique est plus approprie dans le present probleme car nous
 * savons que le nombre d'entrees dans le stack ne peut pas depasser 64
 * mais puisque le but de ce programme est de demontrer le bon fonctionnement
 * du stack dynamique pour le lab2, le stack dynamique est utilise par defaut.
 */
#ifdef STATICSTACK
#include "collect/stack.h"
#else
#include "collect/dynastck.cpp"
#endif

/*
 * Definitions
 */

/*
 * Declarations de fonctions & de classes locales
 */

/******************************************************************************
 *
 * Nom       : solveKnightTourPuzzle
 *
 * Utilite   : Resoud le probleme P3 (solveKnightTourPuzzle)
 *
 * Parametres:
 *     board    (ChessBoard *) Jeu a utilise.
 *     x ,y     (int) Position de depart
 *     strategy (int) Strategie a utilise (heuristique/force brutale)
 *
 * Note      : Avec la methode heuristique, l'algorithme choisit la case
 *             suivante en preferant les cases plus difficilement accessibles,
 *             C'est a dire les cases ayant moins d'origines possibles.
 *             (Ex.: les coins)
 *
 * Valeur de retour: (unsigned long) Nombre de backtracks utilises.
 *
 ****************************************************************************/
static unsigned long solveKnightTourPuzzle( ChessBoard &board,
                        int x,
                        int y,
                        int strategy
                        );

/*
 * Definition des fonctions
 */
void main( void )
{
#ifdef __GNUG__
  Lab2ChessBoard::sentinel = new Lab2ChessCase(-1);
#endif
  char answer;
  Lab2ChessBoard board;
  board.initColumns();

  srand((unsigned)time(NULL));

  try
  {
     signon("Lab2 de ELE-440");
     cout << "Voulez vous utiliser la methode heuristique (O/N) ?" << endl;
     cin.get(answer);
     cout << "Nombre de backtrack : "
            << solveKnightTourPuzzle( board, rand()%NUMCOL, rand()%NUMROW,
                         (answer == 'O' || answer == 'o') )
            << endl;
     cout << endl << "Solution :" << endl << board;
#ifdef __GNUG__
     delete Lab2ChessBoard::sentinel;
#endif

  }
  catch( ExceptionBase &x )
  {
#ifdef WIN32
     x.Explain( DiagOutWin("Exception") );
#else
     DiagOutDOS output = DiagOutDOS(cerr);
     x.Explain( output );
#endif
  }
#ifndef __GNUG__
  catch( bad_cast &x )
  {
     cerr << "Bad_cast" << endl;
  }
#else
  catch( exception &x )
  {
     cerr << x.what() << endl;
  }
#endif
}

/******************************************************************************
 *
 * Nom       : solveKnightTourPuzzle
 *
 ****************************************************************************/
static unsigned long solveKnightTourPuzzle( ChessBoard &board,
                        int x,
                        int y,
                        int strategy
                        )
{
  unsigned long result = 0;
#ifdef STATICSTACK
  stack_dcl(CasesStack,Lab2ChessCase *,64);
#else
  StackDynamic<Lab2ChessCase *> CasesStack;
#endif
  Lab2Knight knight( &board[x][y] );
  Lab2ChessCase *ptrCase, *nextMove;

  if( strategy )
     // Methode heuristique
     board.accept( knight );
     // Sinon methode force brutale

  // Initialise le jeu avec la case de depart
  ptrCase = dynamic_cast<Lab2ChessCase *>(&board[x][y]);
  ptrCase->accept( knight );

  while(1)
  {
     if( ptrCase->possibleNextMoves->isEmpty() == BOOL_FALSE )
     {
#ifdef STATICSTACK
        push(CasesStack,ptrCase);
        ptrCase->seq = stack_ele(CasesStack);
#else
        CasesStack.Push(ptrCase);
        ptrCase->seq = CasesStack.entries();
#endif
        nextMove = getNext( ptrCase );
        ptrCase  = nextMove;
        ptrCase->accept( knight );
     }
#ifdef STATICSTACK
     else if( stack_ele(CasesStack) == NUMROW*NUMCOL-1 )
#else
     else if( CasesStack.entries() == NUMROW*NUMCOL-1 )
#endif
     {
        ptrCase->seq = NUMROW*NUMCOL;
        break;
     }
     else
     {
#ifdef STATICSTACK
        nextMove = pop(CasesStack);
#else
        nextMove = CasesStack.Pop();
#endif
      nextMove->seq = 0;
        ptrCase  = nextMove;

        // Incremente le compteur de backtrack.
        // Affiche un . a chaque 1 000 000 ieme backtrack
        // pour ne pas laisser penser a l'usager que le programme
        // est mort car son execution (surtout avec la methode force brutale)
        // peu etre tres tres tres longue (Dans le pire des cas, le nombre
        // d'essais necessaires pour trouver une reponse peut etre de l'ordre de
        // 60! et plus).
        if(!(result++%1000000))
          cout << ".";
     }
  }
  return result;
}

#ifdef __GNUG__
#ifndef STATICSTACK
template class StackDynamic<Lab2ChessCase *>;
#endif
#endif