/* 
  Pràctica de PS Quadrimestre Tardor 2004-2005 <EDAMAZE>
  Autors:
          Daniel Clemente Laboreo <www.danielclemente.com>
          Francesc Xavier Morales Pascual <www.xavimorales.biz>
*/

// teseus.cpp: resolució de qualsevol tipus de laberint (ortogonal)

/*
 
 
   Alguns algorismes pensats per la resolució:
 
 - A* : però no tenim cap funció heurística. Es podria utilitzar la "distància fins a la cambra de sortida" com a ajuda per caminar sempre en direcció a la sortida, però no sempre anirà bé: a vegades, encara que la sortida estigui per la dreta, el camí bo és el de l'esquerra.
 
 - Dijkstra: s'elimina la funció heurística, però és massa complicat perquè suporta associar un cost a cada moviment. Al laberint costa sempre el mateix fer un pas, per tant busquem un altre algorisme.
 
 - Best-first search: aquest ens convé més, però com que cada pas costa el mateix, ens queda simplificat a la cerca en amplada. (La funció de selecció serà f=g+h, on g=1 i h=0)
 
 - Breadth-first search: aquest és el que usarem. Assegura que es troba el camí més curt (és admissible) ja que els camins més llargs no s'exploren fins que s'han explorat els curts.
 
 - Depth-first search: aquest trobaria un camí ràpidament, però un qualsevol, no necessàriament el més curt.
 
 
 Per tant fem cerca en amplada (veure algorisme a la funció resoldre).
 
*/

#include "laberint.hpp"
#include "teseus.hpp"


// Definir membres static
const char laberint_teseus::nom_mod[];
const int laberint_teseus::SenseSolucio;
const int laberint_teseus::IniciFiNoValid;
const char laberint_teseus::MsgSenseSolucio[];
const char laberint_teseus::MsgIniciFiNoValid[];


laberint_teseus::laberint_teseus(nat num_fil=5, nat num_col=5) throw(error) : laberint(num_fil, num_col) {}

laberint_teseus::laberint_teseus(istream& is) throw(error) : laberint(is) {}

void laberint_teseus::resoldre(const posicio& ini, const posicio& final, list<posicio>& L) throw(error) {
  // Aquí s'implementa un Breadth-First Search

  /*
   
     Algorisme BFS:
  -----------------
     (l'ús de les estructures està explicat a l'arxiu .rep)
   
     - Començar amb una llista i un arbre buits, i tots els nodes marcats com a no visitats
     - El primer node (l'entrada):
       - L'afegim a l'arbre (el fem l'arrel)
       - L'afegim a la llista
       - El marquem com a visitat
     - Ara, mentre la llista tingui nodes, fer:
       - Mirar el primer node de la llista (per l'esquerra). Sigui x
       - Si x és la sortida, parar i acabar
       - Si no, treure x de la llista
       - Marcar-lo com a visitat
       - Per a cada node adjacent que encara no haguem visitat (sigui y), fer:
         - afegir a l'arbre el node y, com a fill de l'x
         - afegir el node y a la llista, per la dreta
         - marcar el node y com a visitat
     - En acabar:
       - Si la llista està buida, no hi ha solució
       - Si no, fer el següent per deixar la solució a la llista L:
         - Sigui p el node solució dins de l'arbre
         - Repetir mentre p no sigui nul:
           - Afegir p a L per l'esquerra
           - Fer que p apunti al node pare de p (o "nul" si p era l'arrel)
       - Retornar L com el camí des de l'entrada fins la sortida
   
  */

  // Variables utilitzades

  nat fil, col;
  paret p;

  // Per fer-ho més còmode:
  nat nf=this->num_files();
  nat nc=this->num_columnes();

  pos_i_parbre pos_i_pa; // Tupla d'aquestes dues:
  posicio pos; // Per anar llegint nodes de la llista de cambres perVisitar
  // Quan la informació es gravi en un pair (com 'posicio') és que comença en 1. Quan s'usen variables naturals, comencen per 0.
  node* pa; // Punter a l'arbre de solucions, diu on és cada cambra dins de l'arbre

  cambra camb; // Igual que la majoria d'aquestes variables, és per fer més simple i net el codi

  // Donar error si l'inici o el final no són cambres vàlides
  // No fa falta funció externa per tan poca cosa
  if (ini.first<1 || ini.first>nf || ini.second<1 || ini.second>nc || \
      final.first<1 || final.first>nf || final.second<1 || final.second>nc)
    throw error(nom_mod,IniciFiNoValid,MsgIniciFiNoValid);

  // Reservar memòria per a la matriu de booleans.
  // És igual que laberint::reserva_memòria, es justifica de la mateixa manera.
  try {
    visitats=new (bool*)[nf];
    for(fil=0;fil<nf;++fil)
      visitats[fil]=new (bool)[nc];
  } catch (error e) {
    for(;fil>=0;--fil)
      delete[] visitats[fil];
    delete[] visitats;
  }

  if (! L.empty())
    L.clear(); // Per si la llista que ens passen no està ja buida

  // Esperem que l'arbre també estigui buit (solucio apunta a NULL)


  // Marcar totes les cambres com no visitades
  for(fil=0;fil<nf;++fil)
    for(col=0;col<nc;++col)
      visitats[fil][col]=false;

  // Ara visitarem l'entrada del laberint.
  visitats[ini.first-1][ini.second-1]=true; // Marquem l'entrada com a visitada

  try {
    solucio=new node; // La creem a l'arbre
  } catch (error e) {
    // Alliberar la memòria dinàmica, ja que no es pot continuar
    // No hi ha res a l'arbre (perquè el new ha fallat) ni a la llista.
    // Destruir la matriu de booleans:
    for (fil=0;fil<nf;++fil)
      delete[] visitats[fil];
    delete[] visitats;
    // I després sortir de la funció
    throw;
  }

  solucio->cambra=ini;
  solucio->nfills=0; // De moment
  solucio->pred=NULL; // Predecessor

  // Ara l'afegim a la llista de posicions per visitar (encara que la visitarem en molt poc temps)
  pos_i_pa.pos=ini;
  pos_i_pa.parbre=solucio;
  perVisitar.push_back(pos_i_pa); // Ens l'apuntem per després.


  // Mentre quedin nodes per visitar, anar visitant-los
  while( ! perVisitar.empty() ) {
    pos_i_pa=perVisitar.front(); // (Agafa la que més temps portava esperant)

    if(pos_i_pa.pos==final)
      break; // Si és la sortida, acaba el bucle (sense fer el pop...)

    perVisitar.pop_front(); // El pop es fa per l'esquerra

    // Això no és necessari, però aclara molt el codi
    pos=pos_i_pa.pos;
    pa=pos_i_pa.parbre;

    fil=pos.first-1;
    col=pos.second-1;

    // Aquesta cambra ja la hem visitada
    visitats[fil][col]=true;


    // Ara hem de processar les cambres adjacents a l'actual (afegir-les a l'arbre i a la llista)
    // Recordatori de l'estat en aquest moment:
    // "pos" té les coordenades de la cambra que hem de processar. Està a l'arbre però hem de afegir els seus fills, que són les cambres adjacents per on encara no hem passat.
    // "pa" és un punter al node corresponent a la cambra "pos", però que està a l'arbre. El necessitem perquè aquest node serà el pare de les cambres adjacents.

    // Aquesta variable de tipus cambra és només per aclarar el codi
    camb=this->operator()( make_pair(fil+1,col+1) ); // Crida a l'operator(), que és públic

    // Per a cadascuna de les quatre parets
    for(p=paret("nord");p<=paret("oest");++p) {

      // Es restaura la fila i columna de la cambra que processem, per si han canviat (veure switch de sota)
      fil=pos.first-1;
      col=pos.second-1;

      if( camb.hi_ha_porta(p) ) { // Podem accedir a la sala contígua
        switch (p) {
        case paret::NORD:
          --fil;
          break;
        case paret::EST:
          ++col;
          break;
        case paret::SUD:
          ++fil;
          break;
        case paret::OEST:
          --col;
          break;
        }
        // Ja estem situats a la cambra adjacent (que, per cert, existeix, perquè no hi ha parets exteriors).

        //  if(make_pair(fil,col)==final)...
        //  Es guanyaria una mica si aquí mateix comprovem si estem afegint la sortida, però tampoc molt perquè la visitarem dintre de pocs turns (concretament, després de visitar una cambra de cada altre camí que estem recorrent en paral.lel)


        // Si no està visitada hem de fer coses
        if ( ! visitats[fil][col] ) {
          visitats[fil][col]=true; // Ja té la visita programada; en uns moments l'afegim a la llista

          // Primer la hem de registrar a l'arbre, perquè potser forma part del camí solució.
          // "pa" estava apuntant a la cambra original. Hem d'afegir-li un fill, que és precissament aquesta adjacent.
          node* padj;
          try {
            padj=new node;
          } catch (error e) {
            // No es pot fer res; destruir tota la memòria que s'ha reservat i sortir
            // Aquestes operacions estan explicades al final de resoldre, en el cas normal on no hi ha errors
            perVisitar.clear();
            esborra_arbre(solucio);
            for (fil=0;fil<nf;++fil)
              delete[] visitats[fil];
            delete[] visitats;

            throw; // Passar l'error a qui hagi cridat la funció
          }

          padj->cambra=make_pair(fil+1,col+1);
          padj->nfills=0; // De moment
          padj->pred=pa; // Aquesta adjacent és filla de la cambra orginal que estàvem processant
          pa->fills[pa->nfills]=padj; // Ja té un fill més
          pa->nfills=pa->nfills+1;
          // Es podria fer pa->fills[pa->nfills++]=padj, però volem codi portable


          pos_i_parbre temp;
          temp.pos=make_pair(fil+1,col+1);
          temp.parbre=padj;
          perVisitar.push_back(temp); // L'afegim a la llista de nodes pendents

        } // Fi del if( ! visitats[fil][col] )

      } // Fi del if( camb.hi_ha_porta(p) )

    } // Fi del for(cada paret...)

  }  // Fi del while( ! perVisitar.empty() )

  // Podem haver sortit del bucle per dos motius:
  // -Per un break per haver trobat la solució. En aquest cas la llista no està buida perquè no s'ha arribat a fer el pop.
  // -Perquè ja s'ha acabat la llista de nodes perVisitar. Llavors és que no hi ha solució.

  if ( ! perVisitar.empty()) { // En cas que hi hagi solució, ens la preparem
    // Hem d'anar trepant per l'arbre fins l'arrel, afegint a L cada node que trobem pel camí
    //Comencem al node solució. Sabem on és perquè tenim la tupla pos_i_pa actualitzada (hem sortit del bucle gran perquè pos_i_pa.pos==final)
    pa=pos_i_pa.parbre;
  } else
    pa=NULL; // Si no hi ha solució, que no faci res al següent bucle

  while (pa) { // Mentre no arribem al NULL (pare de l'arrel)
    pos=pa->cambra; // La posició a la que representa el node

    L.push_front(pos); // El fica per l'esquerra de forma que el més antic (la sortida) quedi a la dreta

    pa=pa->pred; // Pujar fins el seu pare (predecessor)
  }

  // Ara ja tenim la solució (si hi ha) ficada a L; si no hi ha, L està buida.
  // No importa si tenim la solució o no; de totes maneres hem de sanejar les variables que s'han utilitzat: destruir l'arbre, la llista perVisitar i la matriu de booleans.
  // Això no s'ha pogut fer a una destructora perquè no estava definida públicament a l'.hpp

  perVisitar.clear(); // Això és fàcil, però l'arbre.... buf!

  // Recursiu, que queda més curt i elegant.
  esborra_arbre(solucio); // Li passem l'arrel

  // A més destruïm la matriu de booleans
  for (fil=0;fil<nf;++fil)
    delete[] visitats[fil];
  delete[] visitats;

  // Acabem, hem esborrat les estructures auxiliars

  if ( L.empty() )  // Si no hi ha solució, error
    throw error(nom_mod,SenseSolucio,MsgSenseSolucio);

  // Si sí que hi ha, no cal fer res, L ja té la llista bona. Acabem (per fi...)

}

void laberint_teseus::esborra_arbre(laberint_teseus::node* pa) {
  nat k;
  for(k=0;k<pa->nfills;++k)
    esborra_arbre(pa->fills[k]);  // Esborrem tots els fills (o no fem res si no tenia)
  delete pa; // I esborrem el propi node
}