#include "viterbi.h"
#include "../tuning.h"

#include <limits>
#include <vector>
#include <iostream>

using std::vector;

static double s_infini = std::numeric_limits<double>::infinity() ;

Viterbi::Viterbi()
{
}

Viterbi::~Viterbi()
{
}


std::list<size_t> Viterbi::minimise(
                                    const vector<size_t> & premier_arc,
                                    const vector<size_t> & noeud_fin,
                                    const vector<double> & couts,
                                    double * cout_minimal )
{
    size_t nb_noeuds = premier_arc.size();
    std::list<size_t> meilleur_chemin[nb_noeuds] ;        // taille : nb_noeuds
    vector<double> meilleurs_couts(nb_noeuds, s_infini) ; // taille : nb_noeuds
    // le coût du premier nœud est fixé à 0
    meilleurs_couts[0] = 0 ;
    meilleur_chemin[0] = std::list<size_t>(0) ;

    // Pour chaque noeud, on met à jour les meilleurs chemins
    for ( size_t noeud=0 ; noeud+1<nb_noeuds ; noeud++ )
    {
#ifdef __DEBUG_VITERBI__
        std::cout << "noeud "<<noeud<< ", cout : "<<meilleurs_couts[noeud]<<std::endl;
#endif
        // Pour chaque arc partant du noeud, on met à jour les meilleurs chemins
        for (size_t arc=premier_arc[noeud]; arc<premier_arc[noeud+1]; arc++)
        {
#ifdef __DEBUG_VITERBI__
            std::cout << "\t" <<  "->"<< noeud_fin[arc]
                    << "\t" << couts[arc] << std::endl;
#endif
            double cout = meilleurs_couts[noeud] + couts[arc] ;
            if (cout<meilleurs_couts[noeud_fin[arc]])
            {
                meilleurs_couts[noeud_fin[arc]] = cout ;
                meilleur_chemin[noeud_fin[arc]] = meilleur_chemin[noeud] ;
                meilleur_chemin[noeud_fin[arc]].push_back(arc);
            }
        }
    }

#ifdef VERBOSE_VITERBI
    std::cout << "VITERBI : cout = " << meilleurs_couts[ nb_noeuds - 1 ] << std::endl;
    std::cout << "dernier noeud "<<nb_noeuds-1<< ", cout : "
            <<meilleurs_couts[nb_noeuds-1]<<std::endl;
    for (std::list<size_t>::iterator it=meilleur_chemin[ nb_noeuds - 1 ].begin(); it!=meilleur_chemin[ nb_noeuds - 1 ].end(); it++)
    {
        std::cout << "\n(arc " << *it << " vers noeud " << noeud_fin[*it] <<")";
    }
    std::cout << std::endl ;
#endif

    // on renvoie la liste des arcs arrivant au dernier noeud
    if (cout_minimal!=NULL)
        *cout_minimal = meilleurs_couts[ nb_noeuds - 1 ] ;

    return meilleur_chemin[ nb_noeuds - 1 ] ;
}

#ifdef TEST_VITERBI
#include <cstdlib>
#include <iostream>

int main()
{
#define nb_noeuds 5
#define nb_arcs_par_noeud 1000000
#define cout_max 10
    vector<size_t> noeuds(nb_noeuds);
    vector<size_t> arcs  (nb_noeuds * nb_arcs_par_noeud);
    vector<double> cout  (nb_noeuds * nb_arcs_par_noeud);
    for (int i=0; i<nb_noeuds-1; i++)
    {
//         std::cout << "noeud " << i << " :\n";
        noeuds[i] = i * nb_arcs_par_noeud ;
        for (int j=0; j<nb_arcs_par_noeud; j++)
        {
            arcs[i * nb_arcs_par_noeud + j] =
                    random() % (nb_noeuds-1-i) + i + 1 ;
            cout[i * nb_arcs_par_noeud + j] =
                    ((double)random())/RAND_MAX * 10 ;
/*            std::cout << "\tarc " << i * nb_arcs_par_noeud + j << "\t"
                    << "vers noeud " << arcs[i * nb_arcs_par_noeud + j] << "\t"
                    << "cout " << cout[i * nb_arcs_par_noeud + j] << "\n" ;*/
        }
    }
    noeuds[nb_noeuds-1] = ((nb_noeuds-1)*nb_arcs_par_noeud) ;

    std::list<size_t> meilleur = Viterbi().minimise(noeuds, arcs, cout);

    for (std::list<size_t>::iterator it=meilleur.begin(); it!=meilleur.end(); it++)
    {
        std::cout << "\n(" << *it << "," << cout[*it] << ") ";
    }
    std::cout << std::endl ;
}
#endif