#include <iostream>
#include "Q2.h"

void lecture_sommets(vector<arc> &lesArcs, vector<sommet> &lesSommets)
{
    sommet tps;

    for(unsigned i=0 ; i<lesArcs.size() ; i++)
    {
        if(!estdans(lesSommets, lesArcs[i].villeDep))
        {
            lesSommets.push_back(tps);
            lesSommets[lesSommets.size()-1].name = lesArcs[i].villeDep;
            lesSommets[lesSommets.size()-1].rang = lesArcs.size() + 1;
        }
        if(!estdans(lesSommets, lesArcs[i].villeDest))
        {
            lesSommets.push_back(tps);
            lesSommets[lesSommets.size()-1].name = lesArcs[i].villeDest;
            lesSommets[lesSommets.size()-1].rang = lesArcs.size() + 1;
        }
    }
}
bool estdans(vector<sommet> &lesSommets, string &name)
{
    for(unsigned i=0 ; i<lesSommets.size() ; i++)
    {
        if(name == lesSommets[i].name)
        {
            return true;
        }
    }
    return false;
}

void afficher_sommet(vector<sommet> &lesSommets)
{
    for(unsigned i=0 ; i<lesSommets.size() ; i++)
    {
        cout << "Sommet : " << lesSommets[i].name << " Rang : " << lesSommets[i].rang << " Tag : " << lesSommets[i].tag << endl;
    }
}

void Q2(vector<arc> &lesArcs, vector<sommet> &lesSommets, string entree, string sortie,vector< vector<arc> > &trace, vector<string> &Trace_chemin, vector<int> &Trace_value)
{
    bool test = true;
    vector<sommet> chemin;
    trace.push_back(lesArcs);
    /// On tague les sommets
    do
    {
        test = true;
        taguer(get_sommet(entree, lesSommets), 1, entree+"1234");
        while(test)
        {
            test = false;
            for(unsigned i=0 ; i<lesArcs.size() && get_sommet(sortie , lesSommets).tag.size()==0; i++)
            {
                if(est_tague(get_sommet(lesArcs[i].villeDep, lesSommets)) && !est_tague(get_sommet(lesArcs[i].villeDest, lesSommets)) && !est_sature(lesArcs[i])) // positif
                {
                       taguer(get_sommet(lesArcs[i].villeDest, lesSommets), 1, lesArcs[i].villeDep);
                       test = true;
                }
                else if (!est_tague(get_sommet(lesArcs[i].villeDep, lesSommets)) && est_tague(get_sommet(lesArcs[i].villeDest, lesSommets)) && !est_vide(lesArcs[i])) // négatif
                {
                   taguer(get_sommet(lesArcs[i].villeDep, lesSommets), 0, lesArcs[i].villeDest);
                   test = true;
                }

            }

        }
        cout << "Tag : " << endl;
        afficher_sommet(lesSommets);
        /// Recherche d'un chemin
        chemin.clear();
        chemin = get_chemin(entree, sortie, lesSommets, lesArcs);
        cout << "Le chemin est : " << endl ;
        afficher_sommet(chemin);
        /// Modification des flots
        if(chemin.size()>0 && chemin[chemin.size()-1].name == sortie)
        {
            string a;
            Trace_chemin.push_back(a);
            for(unsigned h=0 ; h<chemin.size() ; h++)
            {
                if(h != (chemin.size()-1))Trace_chemin[Trace_chemin.size()-1] += chemin[h].name+" - ";
                else Trace_chemin[Trace_chemin.size()-1] += chemin[h].name;

            }
            unsigned minimum = 1000000000;
            // calcul du min
            for(unsigned i=1 ; i<chemin.size() ; i++)
            {
                if(chemin[i].signe) //positif
                {
                    //cout << "1 : " <<get_capa_resi(get_arc(chemin[i-1].name, chemin[i].name, lesArcs)) << endl;
                    if(minimum > get_capa_resi(get_arc(chemin[i-1].name, chemin[i].name, lesArcs))) minimum = get_capa_resi(get_arc(chemin[i-1].name, chemin[i].name, lesArcs));
                }
                else // négatif
                {
                    //cout << "2 : " << get_arc(chemin[i].name, chemin[i-1].name, lesArcs).flot << endl;
                    if(minimum > get_arc(chemin[i].name, chemin[i-1].name, lesArcs).flot) minimum = get_arc(chemin[i].name, chemin[i-1].name, lesArcs).flot;
                }
                // action
            }
            Trace_value.push_back(minimum);
            for(unsigned i=1 ; i<chemin.size() ; i++)
            {
                if(chemin[i].signe) //positif
                {
                    get_arc(chemin[i-1].name, chemin[i].name, lesArcs).flot += minimum;
                }
                else // négatif
                {
                    get_arc(chemin[i].name, chemin[i-1].name, lesArcs).flot -= minimum;
                }
                // action
            }
        }
        /// On recommence
        for(unsigned i=0 ; i<lesSommets.size() ; i++)
        {
            lesSommets[i].tag.clear();
        }
        trace.push_back(lesArcs);
    }while(chemin.size() > 0);
    trace.pop_back();
}

unsigned get_capa_resi(arc a)
{
    //cout << a.villeDep << " : " << a.capa << " : " << a.flot << endl;
    return a.capa - a.flot;
}
/*
void elimination_arcs(vector<arc> &lesArcs, vector<sommet> &lesSommets)
{
    for(unsigned i=0 ; i<lesArcs.size() ; i++)
    {

    }
}
*/
vector<sommet> get_chemin(string entree, string sortie, vector<sommet> &lesSommets, vector<arc> &lesArcs)
{
    vector <vector<sommet> > chemins;
    vector<sommet> temp;
    bool test=true;

    chemins.push_back(temp);
    chemins[0].push_back(get_sommet(entree, lesSommets));
    while(test)
    {
        test = false;
        for(unsigned j=0 ; j<chemins.size() ; j++)
        {
            for(unsigned i=0 ; i<lesSommets.size() ; i++)
            {
                //cout << lesSommets[i].name << " : " << lesSommets[i].tag << " : " << chemins[j][chemins[j].size()-1].name << endl;
                if(lesSommets[i].tag == chemins[j][chemins[j].size()-1].name)
                {
                    temp = chemins[j];
                    temp.push_back(lesSommets[i]);
                    //cout << " 1:ici " << endl;
                    if(!est_dans(temp, chemins))
                    {
                        //cout << " 2:ici " << endl;
                        test = true;
                        chemins.push_back(temp);
                        chemins[j].swap(chemins[chemins.size()-1]);
                        if(lesSommets[i].name == sortie) return chemins[j];
                    }
                }
            }
        }
    }
    temp.clear();
    return temp;
}
bool est_dans(vector<sommet> &a, vector< vector<sommet> > &tab)
{
    bool test = true;
    for(unsigned i=0 ; i<tab.size() ; i++)
    {
        test = true;
        if(a.size() != tab[i].size()) test = false;
        for(unsigned j=0 ; j<a.size() && a.size()==tab[i].size() ; j++)
        {
            if(a[j].name != tab[i][j].name) test=false;
        }
        if(test) return true;
    }
    return false;
}

sommet& get_sommet(string name, vector<sommet> &lesSommets)
{
  for(unsigned i=0 ; i<lesSommets.size() ; i++)
  {
      if(lesSommets[i].name == name) return lesSommets[i];
  }
  return lesSommets[0];
}

bool est_tague(sommet &s)
{
    string temp="";
    if(s.tag.size() != temp.size()) return true;
    return false;
}
void taguer(sommet &s, bool signe, string from)
{
    s.signe = signe;
    s.tag = from;
}
bool est_sature(arc &a)
{
    if(a.capa == a.flot) return true;
    return false;
}

bool est_vide(arc &a)
{
    if(a.flot == 0) return true;
    return false;

}

void set_rang_sommet(unsigned rang, string name, vector<sommet> &lesSommets)
{
    for(unsigned i=0 ; i<lesSommets.size() ; i++)
    {
        if(lesSommets[i].name == name) lesSommets[i].rang = rang;
    }
}

unsigned get_rang_sommet(string name, vector<sommet> &lesSommets)
{
    for(unsigned i=0 ; i<lesSommets.size() ; i++)
    {
        if(lesSommets[i].name == name) return lesSommets[i].rang;
    }
    return -1;
}

void set_rang_sommets(vector<arc> &lesArcs, vector<sommet> &lesSommets, string &entree)
{
    bool test=true;
    set_rang_sommet(0, entree, lesSommets);
    while(test)
    {
        test = false;
        for(unsigned i=0 ; i<lesArcs.size() ; i++)
        {
            if(get_rang_sommet(lesArcs[i].villeDep, lesSommets) != lesArcs.size() + 1)
            {
                if(min(get_rang_sommet(lesArcs[i].villeDest, lesSommets), get_rang_sommet(lesArcs[i].villeDep, lesSommets)+1) != get_rang_sommet(lesArcs[i].villeDest, lesSommets))test = true;
                set_rang_sommet(min(get_rang_sommet(lesArcs[i].villeDest, lesSommets), get_rang_sommet(lesArcs[i].villeDep, lesSommets)+1), lesArcs[i].villeDest, lesSommets);
            }
        }
    }
}

arc& get_arc(string villeDep, string villeDest, vector<arc> &lesArcs)
{
    arc a;
    for(unsigned i=0 ; i<lesArcs.size() ; i++)
    {
        if(villeDep == lesArcs[i].villeDep && villeDest == lesArcs[i].villeDest) return lesArcs[i];
    }
    return a;
}