#include "cgraphe.h"

#include <cinstance.h>
#include <cinstancereduite.h>
#include "viterbi.h"
#include "cplan.h"

#include <algorithm>
#include <functional>

using std::pair ;


const std::vector<double> * CGraphe::m_u ;
std::vector<Ui> CGraphe::U ;

CGraphe::CGraphe(powerplants2_t i)
{
    m_i = i ;

    /* création des niveaux */
    creerNiveauxRestants();

    /* création des noeuds */
    creerNoeuds();

    /* création des arcs */
    creerArcs();

    /* initialisation du plan de production */
    m_plan = NULL ;
}

// Foncteur servant à libérer un pointeur - applicable à n'importe quel type
struct Delete 
{
    template <class T> void operator ()(T*& p) const
    {
        delete p;
        p = NULL;
    }
};

CGraphe::~CGraphe()
{
    if (m_plan) delete m_plan ;
    for_each(m_noeuds.begin(), m_noeuds.end(), Delete());
}

void CGraphe::creerNiveauxRestants()
{
    for (campaign_t k=(campaign_t)0; k<K(); k = (campaign_t) (k+1))
    {
        vector<double> * niv = new vector<double>;
        double level = 0 ;
        niv->push_back(level);

        level = BO(m_i,k);
        if (level>0 and level<AMAX(m_i,k))
            niv->push_back(level);

        level = SMAX(m_i,k)-RMAX(m_i,k) ;
        if ( level>0 and level<AMAX(m_i,k) )
            niv->push_back(level);

        level = std::min(AMAX(m_i,k), SMAX(m_i,k)-RMIN(m_i,k));
        if ( level>0)
            niv->push_back(level);

        m_remaining_levels.push_back(niv);
    }
}

/**
 * Création des noeuds du graphe
 */

void CGraphe::creerNoeuds()
{
    //
    // Création de la liste des semaines d'outage
    //

    m_campaigns.resize(H());
    for (campaign_t k=(campaign_t)0; k<K(); ++k)
    {
        for (week_t h=TO(m_i,k); h<=TA(m_i,k); ++h)
        {
            m_campaigns[h].push_back(k) ;
        }
    }

    //
    // CREATION du premier noeud
    //

    creer_noeud( (week_t)0,
                  (XI(m_i)-EMAX(m_i,(week_t)0)>BO(m_i, (campaign_t)-1)) ? TYPE_PREMIER : TYPE_BO,
                   (campaign_t)-1,
                    XI(m_i)
               );

    // Parcours des faisceaux d'arcs et création de nouveaux noeuds
    for ( week_t h=(week_t) 0; h<H(); ++h)
        // pour chaque semaine possédant des noeuds
        if ( m_map_noeuds.find(h)!=m_map_noeuds.end())
            for ( campaign_levels_t::iterator ik=m_map_noeuds[h].begin(); ik!=m_map_noeuds[h].end(); ik++)
                for (type_levels_t::iterator it=ik->second.begin(); it!=ik->second.end(); it++)
                    for( niveaux_t::iterator in=it->second.begin(); in!=it->second.end(); in++)
                        // pour chaque noeud
                        if (in->second!=NULL)
#ifdef VERBOSE_NB_NOEUDS
                        {
                            std::cout << "faisceau (centrale " << m_i << ", sem." << h << ", campagne " << ik->first << ", type " << it->first
                                    << ", niveau " << in->first << ") : " << m_noeuds.size() << " noeuds avant" ;
                            std::cout.flush();
#endif
                            faisceau(*in->second) ;
#ifdef VERBOSE_NB_NOEUDS
                            std::cout <<", " << m_noeuds.size() << " noeuds après." << std::endl;
                        }
#endif

    //
    // Création du dernier noeud
    //
    creer_noeud( H(), TYPE_DERNIER, (campaign_t)-1, 0 );
}


/**
 * création des noeuds auxquels un noeud de départ peut se brancher
 * 
 * @param depart 
 */
void CGraphe::faisceau( const CNoeud & depart )
{
    // début de la production
    week_t debut_production = depart.m_date_campaign ;
    // niveaux de fuel possibles au départ de la production :
    double _smax ;
    double _smin ;
    if (depart.m_type == TYPE_OUTAGE) {
        _smin = std::min(depart.m_fuel + RMIN(m_i, depart.m_campaign), SMAX(m_i,depart.m_campaign));
        _smax = std::min(depart.m_fuel + RMAX(m_i, depart.m_campaign), SMAX(m_i,depart.m_campaign));
    } else { // TYPE_BO et TYPE_PREMIER
        _smin = _smax = depart.m_fuel ;
    }
    // modulation restante
    double _modul = depart.m_type == TYPE_BO ? 0 : MMAX(m_i, depart.m_campaign) ;

    faisceau_suite( depart, debut_production, _smin, _smax, _modul ) ;
}


/**
 * Parcours récursif du faisceau partant d'un noeud
 * @param depart noeud de départ
 * @param h semaine courante
 * @param smin fuel min au début de la semaine courante
 * @param smax fuel max au début de la semaine courante
 * @param modul modulation possible à partir de la semaine courante (modulation totale - modulation utilisée pour smax)
 */
void CGraphe::faisceau_suite( const CNoeud & depart, week_t h, double smin, double smax, double modul )
{
    // test sur la date
    if (h>=H()) return ;

    // production de la semaine
    double smax_n, smin_n ;
    if (depart.m_type==TYPE_BO) {
        smax_n = smax - std::min(smax, (1-epsilon()) * PB(m_i, depart.m_campaign, smax, h, (wlen_t) 1) );
        smin_n = smin - std::min(smin, (1+epsilon()) * PB(m_i, depart.m_campaign, smin, h, (wlen_t) 1) );
        // création éventuelle d'un ou plusieurs noeuds
        ++h;
        noeuds_eventuels( depart, h, smin, smax, smin_n, smax_n ) ;
    } else {
        // test sur le seuil BO
        if ( smax < BO(m_i, depart.m_campaign) )
            return ;
        smin_n = smin - std::min( smin, EMAX(m_i, h) ) ;
        smax_n = smax - std::min( smax, EMAX(m_i, h) - std::min( EMAX(m_i,h), modul)) ;
        modul = modul - std::min( EMAX(m_i,h), modul );
        ++ h ;
        noeuds_eventuels( depart, h, smin, smax, std::max(smin_n, BO(m_i,depart.m_campaign)), smax_n );
    }


    // suite du faisceau
    faisceau_suite( depart, h, smin_n, smax_n, modul ) ;
}


/**
 * Création éventuelle de noeuds une semaine donnée.
 * La création dépend des bornes du fuel de la semaine courante et précédente (pour les noeuds BO)
 * et des dates d'outage autorisées (pour les noeuds OUTAGE)
 * @param depart noeud de départ
 * @param h semaine courante
 * @param smin_p min fuel de la semaine précédente
 * @param smax_p max fuel de la semaine précédente
 * @param smin min fuel de la semaine courante
 * @param smax max fuel de la semaine courante
 */
void CGraphe::noeuds_eventuels( const CNoeud & depart, week_t h, double smin_p, double smax_p, double smin, double smax )
{
    // création de noeuds de type BO
    if (depart.m_type != TYPE_BO and smax_p >= BO(m_i,depart.m_campaign) and smin <= BO(m_i,depart.m_campaign))
    {
        smin_p = std::max(smin_p, BO(m_i,depart.m_campaign)) ;
        smax_p = std::min(smax_p, BO(m_i,depart.m_campaign)+EMAX(m_i,(week_t) (h-1)));
        creer_noeuds_intervalle( (week_t)(h-1),
                                  TYPE_BO,
                                  depart.m_campaign,
                                  smin_p, smax_p,
                                  smin_p==BO(m_i,depart.m_campaign),
                                  false
                               );
    }

    // création de noeuds de type OUTAGE
    if (h==H()) return ;
    double cur_min = depart.m_type != TYPE_BO ?
                std::max(smin, BO(m_i,depart.m_campaign)) :
                std::max((double)0,smin);
    for (vector<campaign_t>::iterator kit=m_campaigns[h].begin(); kit!=m_campaigns[h].end(); kit++)
    {
        double cur_max = std::min(smax, AMAX(m_i,*kit));
        if (cur_max>=cur_min)
            creer_noeuds_intervalle( h, TYPE_OUTAGE, *kit, cur_min, cur_max, cur_min==BO(m_i,depart.m_campaign), cur_max==AMAX(m_i,*kit));
    }
}

struct DansIntervalle {
    double m_min, m_max;
    DansIntervalle(double min, double max) {m_min=min; m_max=max;}
    bool operator()(const double & x) {return (x >= m_min) and (x <= m_max);}
};
struct PairDansIntervalle {
    double m_min, m_max;
    PairDansIntervalle(double min, double max) {m_min=min; m_max=max;}
    bool operator()(const pair<double, CNoeud *> & x) {return (x.first >= m_min) and (x.first <= m_max);}
};
struct HorsIntervalle {
    double m_min, m_max;
    HorsIntervalle(double min, double max) {m_min=min; m_max=max;}
    bool operator()(const double & x) {return (x > m_min) or (x > m_max);}
};
template <class T1, class T2>
T1 First( const pair<T1,T2> & p ) { return p.first; }

/**
 * Création de noeuds une semaine donnée à l'intérieur d'un intervalle donné de fuel
 * @param h semaine de la création
 * @param type type des noeuds à créer
 * @param k campagne de production des noeuds à créer
 * @param min fuel min
 * @param max fuel max
 * @param force_min forcer la création d'un noeud au niveau de fuel min
 * @param force_max forcer la création d'un noeud au niveau de fuel max
 */
void CGraphe::creer_noeuds_intervalle( week_t h, noeud_t type, campaign_t k, double min, double max, bool force_min, bool force_max)
{
    // création des noeuds imposés
    if (force_min) creer_noeud( h, type, k, min );
    if (force_max) creer_noeud( h, type, k, max );

    // création d'un noeud entre min et max si aucun des deux n'est imposé et qu'il n'en existe aucun
    if (not force_min and not force_max and
        count_if(m_map_noeuds[h][k][type].begin(), m_map_noeuds[h][k][type].end(), PairDansIntervalle(min,max))==0)
        creer_noeud( h, type, k, (min+max)/2 );

    // liste des niveaux existants compris entre min et max
    vector<double> niveaux_existants ;
    for (std::map<double,CNoeud *>::iterator it=m_map_noeuds[h][k][type].begin(); it!=m_map_noeuds[h][k][type].end(); it++) {
        if (DansIntervalle(min,max)(it->first))
            niveaux_existants.push_back(it->first) ;
    }

    // création de noeuds intermédiaires entre min et le premier existant
    double premier = niveaux_existants.front() ;
    for (premier -= pavage(h); premier>=min; premier -= pavage(h)) {
        creer_noeud( h, type, k, premier ) ;
    }
    // création de noeuds intermédiaires entre le dernier existant et max
    double dernier = niveaux_existants.back() ;
    for (dernier += pavage(h); dernier<=max; dernier += pavage(h)) {
        creer_noeud( h, type, k, dernier ) ;
    }
    // création de noeuds intermédiaires entre les noeuds existants
    if (niveaux_existants.size()>=2) {
        premier = niveaux_existants.front() ;
        for ( vector<double>::iterator it = niveaux_existants.begin()+1; it!=niveaux_existants.end(); it++ )
        {
            double second = *it ;
            int nb_noeuds = (int)((second-premier) / pavage(h)) ;
            double pas = (second-premier) / (nb_noeuds+1) ;
            for ( premier+=pas; premier<second ; premier += pas ) {
                creer_noeud( h, type, k, premier ) ;
            }
            premier = *it ;
        }
    }
}

/**
 * pas de pavage : distance maximale entre deux niveaux de stocks
 * @param h semaine
 * @return 
 */
double CGraphe::pavage(week_t h)
{
    return EMAX(m_i,h)==0 ? 1 : EMAX(m_i,h) * FACTEUR_DE_PAVAGE ;
}

/**
 * Création d'un noeud
 * @param h semaine
 * @param type type de noeud
 * @param k campagne
 * @param fuel niveau de fuel
 */
void CGraphe::creer_noeud( week_t h, noeud_t type, campaign_t k, double fuel )
{
    // sortie si le noeud existe déjà
    if (m_map_noeuds.find(h) != m_map_noeuds.end() and
        m_map_noeuds[h].find(k) != m_map_noeuds[h].end() and
        m_map_noeuds[h][k].find(type) != m_map_noeuds[h][k].end() and
        m_map_noeuds[h][k][type].find(fuel) != m_map_noeuds[h][k][type].end())
        return;

    // création d'un nouveau noeud
    CNoeud * noeud_ptr = new CNoeud;
    CNoeud & noeud(*noeud_ptr);
    noeud.m_type        = type ;
    noeud.m_campaign    = k ;
    noeud.m_fuel        = fuel ;
    noeud.m_date        = h ;
    switch (type) {
        case TYPE_BO :
            noeud.m_date_outage     = (week_t) -1 ;
            noeud.m_date_campaign   = h ;
            break;
        case TYPE_OUTAGE :
            noeud.m_date_outage     = h ;
            noeud.m_date_campaign   = h + DA(m_i,k) ;
            break;
        case TYPE_PREMIER :
            if (h!=0) throw string("Mauvaise date pour le premier noeud");
            noeud.m_date_outage     = (week_t) -1 ;
            noeud.m_date_campaign   = h ;
            break ;
        case TYPE_DERNIER :
            if (h!=H()) throw string("Mauvaise date pour le dernier noeud");
            noeud.m_date_outage     = (week_t) -1 ;
            noeud.m_date_campaign   = (week_t) h ;
            break ;
    }
    m_noeuds.push_back( noeud_ptr ) ;
    m_map_noeuds[h][k][type][fuel] = noeud_ptr ;
}




/**
 *
 * creerArcs : création des arcs
 *
 */

void CGraphe::creerArcs()
{
#ifdef VERBOSE_CREATION_ARCS
    std::cout << "Tri des noeuds. Nb noeuds = " << m_noeuds.size() << std::endl ;
#endif
    // tri des noeuds
    std::sort(m_noeuds.begin(), m_noeuds.end(), OrdreCNoeud());

    // initialisation de la liste des arcs
    m_arcs.resize(0,CArc(NULL,-1,NULL,-1,0,0));

    // parcours des noeuds de départ

#ifdef VERBOSE_CREATION_ARCS
    unsigned int completion  = -1 ;
    size_t nb_arcs_precedent = -1 ;
#endif
    for (size_t dep=0; dep!=m_noeuds.size()-1; dep++)
    {
#ifdef VERBOSE_CREATION_ARCS
/*        if ( completion != (dep * 100) / m_noeuds.size() ) {
            completion = (dep * 100) / m_noeuds.size() ;*/
            std::cout << "Parcours des " << m_noeuds.size() << " noeuds :\t" << dep << " (" << m_arcs.size() << " arcs : + " << m_arcs.size() - nb_arcs_precedent << ")" << std::endl ;
//         }
            if (m_arcs.size()==nb_arcs_precedent) throw string("Aucun arc créé partant du noeud précédent");
            nb_arcs_precedent = m_arcs.size() ;
#endif
        CNoeud & depart = *m_noeuds[dep];

        // longueur minimale d'un arc non final
        wlen_t _dmin;
        switch (depart.m_type) {
            case TYPE_OUTAGE :
                _dmin = DA(m_i, depart.m_campaign);
                break ;
            default :
                _dmin = (wlen_t) 1 ;
                break ;
        }

        // niveaux de fuel possibles sur une semaine donnée
        double _smax ;
        double _smin ;
        double _modul ;
        if (depart.m_type == TYPE_OUTAGE) {
            _smin = std::min(depart.m_fuel + RMIN(m_i, depart.m_campaign), SMAX(m_i,depart.m_campaign));
            _smax = std::min(depart.m_fuel + RMAX(m_i, depart.m_campaign), SMAX(m_i,depart.m_campaign));
        } else { // TYPE_BO et TYPE_PREMIER
            _smin = _smax = depart.m_fuel ;
        }
        if (depart.m_type  == TYPE_BO)
            _modul = 0 ;
        else
            _modul = MMAX(m_i,depart.m_campaign) ;


        // semaine du noeud d'arrivée courant
        week_t _semaine_atteinte = depart.m_date_campaign ;
        // énergie produite
        double _emin = 0 ;
        double _emax = 0 ;

        // parcours des noeuds d'arrivée
        for (size_t arr=dep+1; arr!=m_noeuds.size(); arr++)
        {
            CNoeud & arrivee = *m_noeuds[arr];

            if (arrivee.m_type!=TYPE_DERNIER)
            {
                // passage au suivant si le début est incompatible avec la longueur minimale de l'arc
                if (depart.m_date + _dmin >  arrivee.m_date)
                    continue ;

                // passage au suivant si son fuel est plus bas que BO alors qu'on est dans une période de modulation
                if (depart.m_type!=TYPE_BO and arrivee.m_fuel<BO(m_i, depart.m_campaign))
                    continue ;

                // passage au suivant si son fuel est plus haut que smax
                if (arrivee.m_fuel>_smax)
                    continue ;

                // passage au suivant si arc BO vers BO
                if (depart.m_type==TYPE_BO and arrivee.m_type==TYPE_BO)
                    continue ;
            }

            // productions possibles sur la période :
            for (week_t h = _semaine_atteinte ; h < arrivee.m_date; ++ h ) {
                if (depart.m_type == TYPE_BO)
                {
                    _emax -= std::min(_smin, (1+epsilon()) * PB(m_i, depart.m_campaign, _smin, h, (wlen_t) 1));
                    _emin -= std::min(_smax,(1-epsilon()) * PB(m_i, depart.m_campaign, _smax, h, (wlen_t) 1));
                    _smax = _smax - std::min(_smax,(1-epsilon()) * PB(m_i, depart.m_campaign, _smax, h, (wlen_t) 1));
                    _smin = _smin - std::min(_smin,(1+epsilon()) * PB(m_i, depart.m_campaign, _smin, h, (wlen_t) 1));
                } else {
                    _emax += std::min(_smin, EMAX(m_i,h)) ;
                    _emin += std::min(_smax, EMAX(m_i, h) - std::min( EMAX(m_i,h), _modul)) ;
                    _smin = _smin - std::min(_smin, EMAX(m_i, h)) ;
                    _smax = _smax - std::min(_smax, EMAX(m_i, h) - std::min( EMAX(m_i,h), _modul)) ;
                    _modul = _modul - std::min( EMAX(m_i,h), _modul );
                }
            }
            _semaine_atteinte = arrivee.m_date ;

            // niveaux de fuel possibles à la fin de la production :
            double _smin_a ;
            double _smax_a ;
            if (arrivee.m_type == TYPE_DERNIER) {
                if (depart.m_type == TYPE_BO) {
                    _smin_a = 0;
                    _smax_a = depart.m_fuel;
                } else {
                    _smin_a = BO(m_i,depart.m_campaign);
                    _smax_a = _smax;
                }
            } else { // TYPE_BO et TYPE_OUTAGE
                _smin_a = _smax_a = arrivee.m_fuel ;
            }

            // ajout de l'arc, s'il est réalisable
            if ( _smax >= _smin_a and _smin <= _smax_a )
            {
                m_arcs.push_back( CArc(m_noeuds[dep],dep, m_noeuds[arr], arr, _emax, _emin) ) ;
            }
        }
    }

    // tri des arcs
    std::sort(m_arcs.begin(), m_arcs.end(), OrdreArc());

    // création des vecteurs de taille nb_arcs
    m_cout          .resize(m_arcs.size(), 0 );
    m_noeud_debut   .resize(m_arcs.size(), -1);
    m_noeud_fin     .resize(m_arcs.size(), -1);
    std::transform(m_arcs.begin(), m_arcs.end(), m_noeud_debut  .begin(), CArc::de);
    std::transform(m_arcs.begin(), m_arcs.end(), m_noeud_fin    .begin(), CArc::vers);

    // création du vecteur m_premier_arc
    m_premier_arc.resize( m_noeuds.size(), -1 );
    for (size_t index_noeud=-1, index_arc=0; index_arc<m_arcs.size(); index_arc++)
    {
        if (m_noeud_debut[index_arc]!=index_noeud) {
            do {
                m_premier_arc[++index_noeud] = index_arc ;
            } while (index_noeud<m_noeud_debut[index_arc]);
        }
    }
    m_premier_arc[m_noeuds.size()-1] = m_arcs.size() ; // arc fictif, adapté au parcours dans Viterbi

#ifdef VERBOSE_NB_ARCS
    printf("nombre d'arcs pour la centrale %d : %u\n", m_i, (unsigned int)m_noeud_debut.size());
#endif
#ifdef __DUMP_GRAPHE__
    dump() ;
#endif
}



void CGraphe::dump()
{
    std::cout << "********* dumping graph " << m_i << " ***"<<std::endl ;
    char types[][8] = { "PREMIER", "OUTAGE", "BO", "DERNIER" };

    for (size_t i=0; i<m_noeuds.size(); i++)
    {
        CNoeud & n = *(m_noeuds[i]);
        std::cout << "\tnoeud " << i << " (" << types[n.m_type] << "," << n.m_date << "," << n.m_fuel << ")\n" ;
    }
    
    for (size_t n=0; n<m_arcs.size(); n++)
    {
        CArc & a = m_arcs[n];
        std::cout << "\tarc "<< n << " : de " << a.ide << " ("<<types[a.m_de->m_type]<<","<<a.m_de->m_date<<")"
                << " vers " << a.ivers << " ("<<types[a.m_vers->m_type]<<","<<a.m_vers->m_date<<")" << std::endl;
    }
    std::cout << "********* fin dump *********" << std::endl << std::endl ;
}



void CGraphe::creer_colonnes( CGraphe * graphe )
{
    graphe->creer_colonne() ;
}

void CGraphe::creer_colonne()
{
           /* calculer les coûts de chaque arc */
            calcule_couts_des_arcs();

            /* viterbi pour extraire le meilleur chemin */
            viterbise();

            /* création d'une nouvelle colonne en fonction du meilleur chemin */
            // plan de production
            plan_de_production_apres_viterbi();
}








/**
 * calcule_couts_des_arcs
 */

// création d'un vecteur ordonné des u_i

struct CreerUi {
    CreerUi( const std::vector<double> * _u ) : u(_u) {
        n = 0 ;
    }
    Ui operator()() {
        return Ui(u->at(n), (week_t) n++);
    }
    const vector<double> * u ;
    size_t n ;
};

bool ordreUi(const Ui & a, const Ui & b) { return a.u > b.u ; }

void CGraphe::prepare_viterbi(const vector<double> * u)
{
    // conserve d'une référence à ui,vi
    m_u = u ;

    // création du vecteur ordonné des Ui
    U.resize( H() );
    std::generate(U.begin(), U.end(), CreerUi(u));
    std::sort(U.begin(), U.end(), ordreUi);
}

void CGraphe::calcule_couts_des_arcs( )
{

    for (size_t arc=0; arc<m_noeud_fin.size(); arc++)
    {
        m_cout[arc] = calcule_cout_arc<false>( arc ) ;
    }
}

/**
 * appel à Viterbi
 */

void CGraphe::viterbise()
{
    m_meilleur_chemin = Viterbi().minimise(m_premier_arc, m_noeud_fin, m_cout,
                                &m_cout_minimal);
}


/**
 * plan_de_production_apres_viterbi
 */

void CGraphe::plan_de_production_apres_viterbi()
{
    // création d'un plan de production vide
    if (m_plan) delete m_plan ; // m_plan vaut NULL si le plan a été accepté quelque part
    m_plan = new CPlan(m_i, H(),I());

    // appel à la fonction calcule_cout_arc pour les campagnes de production
    m_cout_minimal = 0 ;
    for (std::list<size_t>::const_iterator it_arc = m_meilleur_chemin.begin();
        it_arc!=m_meilleur_chemin.end(); it_arc++)
    {
        m_cout_minimal += calcule_cout_arc<true>(*it_arc);
    }
    m_plan->m_cout = m_cout_minimal ;
}


/**
 *
 * calcul du coût d'un arc
 * effet de bord : remplit le plan de production m_plan du graphe
 *
 */

struct EstDans{
    EstDans(size_t i, size_t j) {m_i=i; m_j=j;}
    bool operator()(const Ui & ui) { return (size_t)ui.i>=m_i and (size_t)ui.i<m_j;}
    size_t m_i; size_t m_j;
} ;


template<bool enregistrer_plan>
double CGraphe::calcule_cout_arc( size_t arc_idx )
{
    // noeud de départ
    const CNoeud & depart = *m_arcs[arc_idx].m_de ;
    const CNoeud & arrivee = *m_arcs[arc_idx].m_vers ;
    const double Cur = depart.m_campaign == -1 ? 0 : C(m_i, depart.m_campaign) ;
    double _cout = 0 ;
    double _r = 0; // recharge
    double _fuel = depart.m_fuel ;

    /**************************************/
    /*   cas facile du type BO            */
    /**************************************/

    if ( depart.m_type == TYPE_BO )
    {
            // facile : la production est imposée
            for (week_t h=depart.m_date_campaign; h<arrivee.m_date ; ++h)
            {
                if (_fuel<=0) break ;
                double prod = PB( m_i, depart.m_campaign, _fuel, h, (wlen_t) 1 );
                _fuel -= prod ;
                _cout -= (m_u->at(h)) * prod ;
                if (enregistrer_plan) {
                    m_plan->set_prod(h,prod) ;
                }
            }
            _cout += Cur * _r ;
            if (enregistrer_plan) {
                m_plan->push_back(depart, _r, _cout, Cur*_r);
            }
            return _cout ;
    }

    /*****************************************************/
    /*    cas des campagnes de productions non finales   */
    /*****************************************************/

    // Prédicat pour parcourir les Ui triés appartenant à la période de production courante */
    EstDans estDans(depart.m_date_campaign, arrivee.m_date) ;

    // Productions accomplie, max et min
    double _prod = 0 ;
    double _prod_max = m_arcs[arc_idx].emax ;
    double _prod_min = m_arcs[arc_idx].emin ;

    // calcul des productions et du coût
    if ( arrivee.m_type != TYPE_DERNIER )
    {
        do {
            vector<Ui>::iterator itui = find_if( U.begin(), U.end(), estDans);
            // remplissage tant qu'on y est forcé
            while ( itui!=U.end() and _prod + EMAX(m_i, itui->i)<=_prod_min ) {
                _prod += EMAX(m_i, itui->i);
                _cout -= (itui->u)*EMAX( m_i, itui->i ) ;
                if (enregistrer_plan) {
                    m_plan->set_prod(itui->i, EMAX(m_i, itui->i)) ;
                }
                itui = find_if( ++itui, U.end(), estDans ) ;
            }
            if (itui==U.end()) break ;

            // ajout du minimum si c'est coûteux
            if (Cur-itui->u > 0) {
                _cout -= (itui->u)*(_prod_min-_prod);
                _prod += _prod_min-_prod;
                if (enregistrer_plan) {
                    m_plan->set_prod(itui->i, _prod_min-_prod);
                }
                break ;
            }
            // seconde phase : ajout tant que c'est intéressant et possible
            while ( itui!= U.end() and (Cur-itui->u <= 0) and _prod+EMAX(m_i,itui->i)<_prod_max )
            {
                _prod += EMAX(m_i, itui->i);
                _cout -= (itui->u)*EMAX( m_i, itui->i ) ;
                if (enregistrer_plan) {
                    m_plan->set_prod(itui->i, EMAX(m_i, itui->i));
                }
                itui = find_if( ++itui, U.end(), estDans ) ;
            }
            // ajout du dernier s'il est intéressant
            if ( itui!=U.end() and (Cur-itui->u <= 0) ) {
                _prod += _prod_max - _prod ;
                _cout -= (itui->u)*(_prod_max-_prod);
                if (enregistrer_plan) {
                    m_plan->set_prod(itui->i, _prod_max - _prod);
                }
            }
        } while (false) ;

        _r = arrivee.m_fuel + _prod - depart.m_fuel ;
        _cout += Cur * _r ;
        if (enregistrer_plan) {
            m_plan->push_back(depart, _r, _cout, Cur*_r);
        }
        return _cout ;
    }

    /****************************************************************/
    /*    cas des campagnes de productions finales non BO           */
    /****************************************************************/

    double _seuil_augmentation_r;   // seuil de consommation au-delà duquel
                                    // on a intérêt à augmenter la recharge

    if (depart.m_type == TYPE_PREMIER) {
        // pas de recharge, tout ce qu'on consomme est pris sur le prix de revente
        _r = 0 ;
        _seuil_augmentation_r = _prod_max ;
    } else {
        if (CiTp1(m_i)>Cur) {
            // on charge au maximum, tout ce qu'on consomme est pris sur le prix de revente
            _r = std::min( RMAX(m_i, depart.m_campaign), SMAX(m_i, depart.m_campaign)-depart.m_fuel );
            _seuil_augmentation_r = _prod_max ;
        } else {
            // on charge au minimum, on commence par consommer sur la revente, puis on augmente
            // la recharge
            _r = RMIN(m_i, depart.m_campaign);
            _seuil_augmentation_r = depart.m_fuel + _r - BO(m_i,depart.m_campaign);
        }
    }

    // calcul de la production
    do {
        vector<Ui>::iterator itui = find_if( U.begin(), U.end(), estDans);

        // production tant qu'on y est forcé
        while ( itui!=U.end() and _prod + EMAX(m_i, itui->i)<=_prod_min ) {
            _prod += EMAX(m_i, itui->i);
            _cout -= (itui->u)*EMAX( m_i, itui->i ) ;
            if (enregistrer_plan) {
                m_plan->set_prod(itui->i, EMAX( m_i, itui->i ));
            }
            itui = find_if( ++itui, U.end(), estDans ) ;
        }
        if (itui==U.end()) break ;

        // deuxième phase : ajout sur la revente tant que c'est intéressant et possible
        while ( itui!= U.end() and (CiTp1(m_i) - itui->u <= 0) and _prod+EMAX(m_i,itui->i)<_seuil_augmentation_r )
        {
            _prod += EMAX(m_i, itui->i);
            _cout -= (itui->u)*EMAX( m_i, itui->i ) ;
            if (enregistrer_plan) {
                m_plan->set_prod(itui->i, EMAX( m_i, itui->i ));
            }
            itui = find_if( ++itui, U.end(), estDans ) ;
        }
        if (itui==U.end()) break ;

        // complétion au minimum s'il n'est pas atteint
        if (_prod<_prod_min)
        {
            _cout -= (itui->u)*(_prod_min-_prod);
            _prod += _prod_min-_prod;
            if (enregistrer_plan) {
                m_plan->set_prod(itui->i, _prod_min-_prod);
            }
            break;
        }
        // arrêt si la revente n'est plus intéressante
        if (CiTp1(m_i) - itui->u > 0) break ;

        // complétion au seuil d'augmentation de la recharge, voire plus
        if (Cur - itui->u <= 0) {
            _cout -= (itui->u)*std::min(EMAX(m_i,itui->i), _prod_max-_prod) ;
            _prod += std::min(EMAX(m_i,itui->i), _prod_max-_prod) ;
            if (enregistrer_plan) {
                m_plan->set_prod(itui->i, std::min(EMAX(m_i,itui->i), _prod_max-_prod)) ;
            }
            itui = find_if( ++itui, U.end(), estDans ) ;
        } else {
            _cout -= (itui->u)*std::min(EMAX(m_i,itui->i), _seuil_augmentation_r-_prod) ;
            _prod += std::min(EMAX(m_i,itui->i), _seuil_augmentation_r-_prod) ;
            if (enregistrer_plan) {
                m_plan->set_prod(itui->i, std::min(EMAX(m_i,itui->i), _seuil_augmentation_r-_prod)) ;
            }
            break ;
        }

        // troisième phase : augmentation de la recharge tant que c'est intéressant et possible
        while ( itui!= U.end() and (Cur - itui->u <= 0) and _prod+EMAX(m_i,itui->i)<=_prod_max )
        {
            _prod += EMAX(m_i, itui->i);
            _cout -= (itui->u)*EMAX( m_i, itui->i ) ;
            if (enregistrer_plan) {
                m_plan->set_prod(itui->i, EMAX(m_i, itui->i));
            }
            itui = find_if( ++itui, U.end(), estDans ) ;
        }
        if (itui==U.end()) break ;

        // complétion à prod_max si c'est intéressant
        if (Cur - itui->u <= 0)
        {
            _prod += (_prod_max-_prod);
            _cout -= (itui->u)*(_prod_max-_prod) ;
            if (enregistrer_plan) {
                m_plan->set_prod(itui->i, (_prod_max-_prod));
            }
        }
    } while (false);

    // calcul de la recharge
    if (_prod >_seuil_augmentation_r) {
        _r += (_prod - _seuil_augmentation_r) ;
    }
    // calcul du coût de l'arc
    _cout += (Cur * _r) // prix de la recharge
             - CiTp1(m_i) * (depart.m_fuel + _r - _prod) ; // prix de la revente

    if (enregistrer_plan) {
        m_plan->push_back(depart, _r, _cout,
                              (Cur * _r) - (CiTp1(m_i) * (depart.m_fuel + _r - _prod)),
                               depart.m_fuel + _r - _prod);
    }
    return _cout;
}