/******************************************
 *
 *   Cedric Pradalier   2001
 *   mail : http://cedric.pradalier.free.fr/mail.html
 *
 *****************************************/



#include "recherche.h"
#include "lignes.h"
#include "lignes_gen.h"
#include "arrets.h"
#include "horaire.h"
#include "vector.h"
#include "ensemble.h"
#include "corresp.h"
#include "date.h"
#include "treillis.h"
#include "output.h"
#include <string.h>



/* Recherche l'itineraire permettant d'aller de l'arret IndDepart, a l'arret
   IndArrivee avant limite connaissant la BD des arrets, la BD des lignes
   et le nombre max de correspondance que l'on tolere */
void Recherche(CBDArrets * pBDA, CBDLignes * pBDL, CommunicationStruct * S)
{
    // D'abord trouver les arrets depart et arrivee */
    CArrets * ADep = S->ADep;
    CArrets * AArr = S->AArr;
    CVector Etape; // tableau des ensembles de correspondances
//  CVector S->Itineraires; // tableau des itineraires
    // Ensemble intermediaire pour parcourir le graphe
    CEnsemble * Li,* Lj,* Lt; // j = i+1
    CEnsemble LignesSensUnique;
    //  bool DepartSensUnique = false; // A priori, le départ n'est pas un 
    // arret desservi en sens unique
    int i,j,k;


    /******************************************************
Principe : A chaque etape Li contient l'ensemble des 
arrets qu'on peut atteindre (en i correspondance).
-- Initialement, Li contient les correspondances constituees
de l'arret de depart et des lignes presentes a cet arret --

Ensuite, Pour chaque arret deja atteint, on calcule toutes
les lignes accessibles dans Lk, on extrait ensuite celles qui sont
nouvelles et on les met dans Lj qui devient Li pour l'iteration 
suivante 
     ***********************************************************/

    // #define DEBUG



    Li = new CEnsemble;
#ifdef DEBUG
    sprintf(outbuf,"Extraction lignes presentes \n");
    FlushBuffer();
#endif
    ADep->ExtraitPresentes(Li,pBDL);
    S->ArretDepSensUnique = false;

    // On recherche si l'arret de depart est desservi
    // en sens unique.
    for (j=0;j<Li->GetNbElem();j++)
    {
        CCorresp * L = (CCorresp *)Li->ElemAt(j);
        if (L->ligne->IsUnique(ADep))
        {
            LignesSensUnique.ajoute((CObjet *) L);
            S->ArretDepSensUnique = true;
#ifdef DEBUG
            sprintf(outbuf,"ATTENTION : Sur la ligne %s, l'arret \n\t%s est desservi en sens unique \n",
                    L->ligne->mName,ADep->mNom);
            FlushBuffer();
#endif
        }
    }

    Etape.add((CObjet *)Li);

#ifdef DEBUG
    sprintf(outbuf,"Extraction OK\n");
    FlushBuffer();
#endif
    // On itere sur le nombre maximum de correspondances
    // autorisées.
    for (i=0;i<S->MaxNbCorresp;i++)
    {
#ifdef DEBUG
        sprintf(outbuf,"Correspondance %i \n",i);
        FlushBuffer();
#endif
        Lj = new CEnsemble;
#ifdef DEBUG
        sprintf(outbuf,"#Li : %i \n",Li->GetNbElem());
        FlushBuffer();
#endif
        /* Pour tous les elem de Li */
        for (j=0;j<Li->GetNbElem();j++)
        {
            CCorresp * L = (CCorresp *)Li->ElemAt(j);
            /********************************************** 
              Si l'arret d'arrivee appartient a la
              ligne etudiee, on est arrivee, on ajoute
              l'itineraires constitue de la liste chainee
              des correspondance empruntees jusqu'alors
              a l'ensemble des itineraires connus et 
              on s'arrete la 
             ***********************************************/

            if (L->ligne->IsKnown(AArr))
            {
                S->Itineraires.add(L->ExtraitTreillis(ADep,AArr,S->Limite));
                if (L->ligne->IsUnique(AArr))
                {
#ifdef DEBUG
                    sprintf(outbuf,"Arrivée : Sur la ligne %s, l'arret %s est unique \n",
                            L->ligne->mName,AArr->mNom);
                    FlushBuffer();
#endif
                    CCorresp corr(*L);
                    corr.precedent = L;
                    S->Itineraires.add(corr.ExtraitTreillis(ADep,AArr,S->Limite));
                }
            }
            else
            {
                Lt = new CEnsemble;
#ifdef DEBUG
                sprintf(outbuf,":(\n");
                FlushBuffer();
#endif
                // Sinon on extrait les lignes 
                // accessibles dans Lt
                L->ExtraitAccessibles(Lt,pBDL);
#ifdef DEBUG
                sprintf(outbuf,"%s :| %i \n",L->ligne->mName,Lt->GetNbElem());
                FlushBuffer();
#endif
                /***************************************
                  Pour toutes les lignes accessibles :
                  si on ne les a pas utilises sur cet
                  itineraires, on construit une 
                  nouvelle correspondance
                 ***************************************/
                for (k=0;k<Lt->GetNbElem();k++)
                {
#ifdef DEBUG
                    sprintf(outbuf,"element %i\n",k);
                    FlushBuffer();
#endif
                    CCorresp * corresp=(CCorresp *)Lt->ElemAt(k);
#ifdef DEBUG
                    sprintf(outbuf,"A-t-on deja utilise cette ligne ? [%s] \n",corresp->ligne->mName);
                    FlushBuffer();
#endif
                    if (!L->Contains(corresp->ligne))
                    {
#ifdef DEBUG
                        sprintf(outbuf,"Baah non !\n");
                        FlushBuffer();
#endif
                        Lj->ajoute((CObjet *)corresp);
                    }
                    else  
                    {
#ifdef DEBUG
                        sprintf(outbuf,"Baah oui !\n");
                        FlushBuffer();
#endif
                        delete corresp;
                    }
                }
                delete Lt;
            }
        }
        Etape.add((CObjet *)Lj);
        Li = Lj;
    }

    S->NbItinTrouves = S->Itineraires.GetNbElem();
#ifdef DEBUG
    sprintf(outbuf,"Recherche itineraires effectuee.\n");
    FlushBuffer();
    sprintf(outbuf,"--> %i itineraires trouves\n",S->Itineraires.GetNbElem());
    FlushBuffer();
    sprintf(outbuf,"Mise a jour des horaires de correspondance.\n");
    FlushBuffer();
#endif
    /************************************************
      Quand on a tous les itineraires,
      on met a jours les horaires et on supprime
      l'itineraire quand il y a un pb 
     ************************************************/
    int NbSupprimes = 0;
    for (i=S->Itineraires.GetNbElem()-1;i>=0;i--)
    {
        CTreillis * iti = (CTreillis *) S->Itineraires.ElemAt(i);
        /* on supprime les itineraires sans horaires possibles */
#ifdef DEBUG
        sprintf(outbuf,"Traitement d'un itineraire \n");
        FlushBuffer();
#endif
        if (!(iti->MaJHoraires(S->TpsCorresp)))
        {
            NbSupprimes += 1;
            S->Itineraires.suppr(i);
        }
    }
    S->NbItinRejetes = NbSupprimes;

#ifdef DEBUG
    sprintf(outbuf,"--> Nombre d'itinéraires impossibles : %i\n",NbSupprimes);
    FlushBuffer(); 
#endif


    // Menage...
//  for (i=0;i<S->Itineraires.GetNbElem();i++)
//      delete (CTreillis *) S->Itineraires.ElemAt(i);
    for (i=0;i<S->MaxNbCorresp;i++)
    {
        Li = (CEnsemble *)(Etape.ElemAt(i));
        for (j=0;j<Li->GetNbElem();j++)
            delete ((CCorresp *)Li->ElemAt(j));
        delete Li;
    }

}