#include <stdio.h>
#include <math.h>
#include <vector>

using namespace std; 

#ifndef _Tri_
#define _Tri_

float Minimum(float a, float b);
template <typename T3, typename T4> void TriInterclassement(T3 n1, T3 n, T3 p1, T3 p, T3 s, T4 n12, T4 n2, T4 p12, T4 p2, T4 s2);
template <typename T3> void TriInterclassement(T3 n1, T3 n, T3 p1, T3 p, T3 s);
template<typename T1, typename T2> void TriVonNeumann(vector<T1> *t, vector<T2> *t2);
template<typename T1> void TriVonNeumann(vector<T1> *t);

//---------------------------------------------------------------------------
// Fonction renvoyant le minimum entre deux nombres
//---------------------------------------------------------------------------
float Minimum(float a, float b)
{
 float res;

 res = b;
 if(a <b)
        res = a;

 return(res);
}

//---------------------------------------------------------------------------
// Fonction d'interclassement - nécessaire à TriVonNeumann
// Fusion de deux tableaux :
//      - Comparaison des deux premiers éléments de chaque liste
//      - Le plus petit va dans la liste finale
//      - Recommence la comp avec l'élément qui reste et le suivant de l'autre liste
//      - Quand une des listes est épuisée on transfère l'autre dans s
//---------------------------------------------------------------------------
template <typename T3, typename T4> void TriInterclassement(T3 n1, T3 n, T3 p1, T3 p, T3 s, T4 n12, T4 n2, T4 p12, T4 p2, T4 s2)
{
 T3 i;
 T3 j;
 T3 k;
 T3 q;
 T4 i2;
 T4 j2;
 T4 k2;
 T4 q2;

 i = n1;
 j = p1;
 k = s;

 i2 = n12;
 j2 = p12;
 k2 = s2;

 while((i<=n) && (j<=p))        // Tant qu'on n'est pas à la fin d'une des deux listes
 {
        if(*i < *j)             // On met le minimum entre les éléments des deux listes dans la liste finale
        {                       // On avance le compteur de la liste dont on a pris le minimum
                *k = *i;
                *k2 = *i2;
                ++i;
                ++i2;
        }
        else
        {
                *k = *j;
                *k2 = *j2;
                ++j;
                ++j2;
        }
        ++k;
        ++k2;
 }

 // Quand les listes sont épuisées, on recopie le reste de la liste non épuisée dans la liste finale

 if(i > n)
 {
        q2 = j2;
        for(q=j;q<=p;++q)
        {
                *k = *q;
                *k2 = *q2;
                ++k;
                ++k2;
                ++q2;
        }
 }
 else
 {
        q2 = i2;
        for(q=i;q<=n;++q)
        {
                *k = *q;
                *k2 = *q2;
                ++k;
                ++k2;
                ++q2;
        }
 }
}

//---------------------------------------------------------------------------
// Fonction d'interclassement - nécessaire à TriVonNeumann
// Fusion de deux tableaux :
//      - Comparaison des deux premiers éléments de chaque liste
//      - Le plus petit va dans la liste finale
//      - Recommence la comp avec l'élément qui reste et le suivant de l'autre liste
//      - Quand une des listes est épuisée on transfère l'autre dans s
//---------------------------------------------------------------------------
template <typename T3> void TriInterclassement(T3 n1, T3 n, T3 p1, T3 p, T3 s)
{
 T3 i;
 T3 j;
 T3 k;
 T3 q;

 i = n1;
 j = p1;
 k = s;

 while((i<=n) && (j<=p))        // Tant qu'on n'est pas à la fin d'une des deux listes
 {
        if(*i < *j)             // On met le minimum entre les éléments des deux listes dans la liste finale
        {                       // On avance le compteur de la liste dont on a pris le minimum
                *k = *i;
                ++i;
        }
        else
        {
                *k = *j;
                ++j;
        }
        ++k;
 }

 // Quand les listes sont épuisées, on recopie le reste de la liste non épuisée dans la liste finale

 if(i > n)
 {
        for(q=j;q<=p;++q)
        {
                *k = *q;
                ++k;
        }
 }
 else
 {
        for(q=i;q<=n;++q)
        {
                *k = *q;
                ++k;
        }
 }
}


//---------------------------------------------------------------------------
// Tri de Von Neumann :
//      - On considère la liste initiale de n éléments comme n sous-listes triées de 1 élément
//      - Premier interclassement des sous listes deux à deux conduit à des sous-listes triées de deux éléments
//      - On recommence jusqu'à n'avoir qu'une seule liste triée
//      - Si, à une étape in a un nombre impaire de sous-listes, la dernière est reportée sans changement à
//      à l'étape suivante
//---------------------------------------------------------------------------
// Cette fonction prend 2 paramètres : le vecteur t, que l'on va trier par ordre croissant, et le vecteur t2
// associé : chaque indice de t2 correspond au même indice de t ; le tri va également associer ce vecteur t2.
//---------------------------------------------------------------------------
// Par exemple :
//      vector<float> t;
//      vector<String> t2;
//      t.push_back(5);
//      t2.push_back("Valeur 5");
//      t.push_back(1);
//      t2.push_back("Valeur 1");
//      t.push_back(6);
//      t2.push_back("Valeur 6");
//      TriVonNeumann(&t,&t2)
// On obtient :
//      t[0]  = 1
//      t2[0] = "Valeur 1"
//      t[1]  = 5
//      t2[1] = "Valeur 5"
//      t[2]  = 6
//      t2[2] = "Valeur 6"
//---------------------------------------------------------------------------
template<typename T1, typename T2> void TriVonNeumann(vector<T1> *t, vector<T2> *t2)
{
 int dim, i, size;
 double h;
 
 // Taille des vecteurs à traiter
 size = t->size();

 vector<T1> d(size);
 vector<T1> a(size);

 T1 * n1;
 T1 * n;
 T1 * p1;
 T1 * p;
 T1 * s;

 vector<T1> u(size);
 vector<T2> a2(size);
 vector<T2> d2(size);
 vector<T2> u2(size);

 T2 *n12;
 T2 *n2;
 T2 *p12;
 T2 *p2;
 T2  *s2;

 d = *t;

 d2 = *t2;

 dim = 1; //    Contient la longueur des sous listes déjà triées
 while(dim<size)
 {
        for(i=0;i<(size-dim);i+=2*dim) // i premier indice de première sous-liste issue d'un interclassement, on s'arrête quand dépasse dim-size car plus de deux listes à interclasser
        {
                h=Minimum(i+2*dim-1,size-1);    // Calcul de l'indice pour avoir l'indice de fin de la deuxième sous liste à fusionner
                n1 = &d[i] ;                    // Pointage sur le début et la fin de la première sous-liste
                n = &d[i + dim -1];
                p1 = &d[i + dim];               // Pointage sur le début et la fin de la deuxième sous liste
                p = &d[(int)h];
                s = &a[i];                      // Pointage sur l'indice de fin de la liste fusionnée

                n12 = &d2[i];
                n2 = &d2[i + dim -1];
                p12 = &d2[i +dim];
                p2 = &d2[(int)h];
                s2 = &a2[i];

                TriInterclassement(n1, n, p1, p, s, n12, n2, p12, p2, s2);
        }
        for(i=h+1;i<size;++i)  // Transfert de la fin de la liste si h <n
        {
                a[i] = d[i];
                a2[i] = d2[i];
        }
 u = d;
 d = a;
 a = u;

 u2 = d2;
 d2 = a2;
 a2 = u2;

 dim = 2 * dim; // Changement de taille des sous listes
 }

 *t = d;
 *t2 = d2;
}

//---------------------------------------------------------------------------
// Tri de Von Neumann :
//      - On considère la liste initiale de n éléments comme n sous-listes triées de 1 élément
//      - Premier interclassement des sous listes deux à deux conduit à des sous-listes triées de deux éléments
//      - On recommence jusqu'à n'avoir qu'une seule liste triée
//      - Si, à une étape in a un nombre impaire de sous-listes, la dernière est reportée sans changement à
//      à l'étape suivante
//---------------------------------------------------------------------------
// Cette fonction prend 1 paramètre : le vecteur t, que l'on va trier par ordre croissant
//---------------------------------------------------------------------------
// Par exemple :
//      vector<float> t;
//      t.push_back(5);
//      t.push_back(1);
//      t.push_back(6);
//      TriVonNeumann(&t)
// On obtient :
//      t[0]  = 1
//      t[1]  = 5
//      t[2]  = 6
//---------------------------------------------------------------------------
template<typename T1> void TriVonNeumann(vector<T1> *t)
{
 int dim, i, size;
 double h;
 
 // Taille des vecteurs à traiter
 size = t->size();

 vector<T1> d(size);
 vector<T1> a(size);

 T1 * n1;
 T1 * n;
 T1 * p1;
 T1 * p;
 T1 * s;

 vector<T1> u(size);

 d = *t;

 dim = 1; //    Contient la longueur des sous listes déjà triées
 while(dim<size)
 {
        for(i=0;i<(size-dim);i+=2*dim) // i premier indice de première sous-liste issue d'un interclassement, on s'arrête quand dépasse dim-size car plus de deux listes à interclasser
        {
                h=Minimum(i+2*dim-1,size-1);    // Calcul de l'indice pour avoir l'indice de fin de la deuxième sous liste à fusionner
                n1 = &d[i] ;                    // Pointage sur le début et la fin de la première sous-liste
                n = &d[i + dim -1];
                p1 = &d[i + dim];               // Pointage sur le début et la fin de la deuxième sous liste
                p = &d[(int)h];
                s = &a[i];                      // Pointage sur l'indice de fin de la liste fusionnée

                TriInterclassement(n1, n, p1, p, s);
        }
        for(i=h+1;i<size;++i)  // Transfert de la fin de la liste si h <n
        {
                a[i] = d[i];
        }
 u = d;
 d = a;
 a = u;

 dim = 2 * dim; // Changement de taille des sous listes
 }
 *t = d;
}

#endif