#include <iostream>
#include <iomanip>      // std::setprecision
#include <stdio.h>   // pour printf et sprintf
#include <math.h>   // utile ??
// c.f. http://www.cplusplus.com/reference/limits/numeric_limits/
#include <limits>
#include <stdlib.h> // pour random  : rand(...)
// c.f. http://www.cplusplus.com/reference/cstdlib/rand/
// rand() retourn un nombre entier entre 1 et RAND_MAX
// RAND_MAX vaut : 2'147'483'647 = 2^31 - 1  habituellement.
//##########################################################

// Les fonctions.
// Passage de paramètres par valeur et par référence
// Les tableaux
// Algorithmes de tris.

using namespace std;

// 1.
// Un simple exemple de fonction.

int FoisDeux(int nVal) {
//======================
// Retourn la valeur  nVal  multipliée par deux.
return nVal*2;
} // FoisDeux

void test01() {
//============
// test01 est un exemple de fonction.
// "void" signifie qu'elle ne retourne aucune valeur

int nVal = 7;
cout << "nVal=" << nVal << "  son double vaut " << FoisDeux(nVal) << endl;
} // test01
//#############################################################

// 2.
// Comment faire pour retourner deux valeurs ?
// Par exemple, retourner la valeur fois 2 et la valeur plus 2.
// Dans l'exemple précédent, on transmettait "nVal" par VALEUR.
// Ici, on va transmettre une variable par REFERENCE.

void FoisPlusDeux(int nVal, int& rnFois, int& rnPlus) {
//=====================================================
// Retourn dans rnFois la valeur  nVal  multipliée par deux.
// Retourn dans rnPlus la valeur  nVal  additionnée de deux.
// "void" signifie qu'elle ne retourne aucune valeur
rnFois = nVal * 2;
rnPlus = nVal + 2;
} // FoisPlusDeux

void test02() {
//============
// Test la transmission par VALEUR et par REFERENCE

int nVal = 7;
int nFois = 0, nPlus = 0;

FoisPlusDeux(nVal, nFois, nPlus);
cout << "nVal=" << nVal << "  son double vaut " << nFois
     << "  additionné de deux donne " << nPlus << endl;
} // test02
//#############################################################

// 3.
// Utilisation de transmission par REFERENCE pour échanger
// la valeur de deux variables.

void Echange(double& rvA, double& rvB) {
//======================================
// Echange les contenus des deux variables, rVa et rvB
double vTemp = rvA;
rvA = rvB;
rvB = vTemp;
} // Echange

void test03() {
//============
// Test l'exemple d'échange de deux valeurs.

double vA = 1.1, vB = 2.2;

cout << "A=" << vA << "  et  B=" << vB << endl;

Echange(vA, vB);
cout << "Après échange :" << endl;
cout << "A=" << vA << "  et  B=" << vB << endl;
} // test03
//#############################################################

// 4.
// Exemple de :
// i)   Déclaration de constante
// ii)  Utilisation de tableaux de valeurs
// iii) Transfert de tableaux comme paramètres.

void MinMax1( unsigned int nIndMax, double avVals[],
              double& rvMin, double& rvMax) {
//===========================================
// Retourn dans rvMin la valeur min. de avVals[nIndMax].
// Retourn dans rvMax la valeur max. de avVals[nIndMax].
// La règle est qu'un tableau est toujours transmis par référence
// Le défaut est que le programmeur peut se tromper et modifier
// une valeur du tableau, ce qui serai une erreur désagrable.
// C.f. l'amélioration  MinMax2.

unsigned int nn=0;
rvMin = avVals[0];
rvMax = rvMin;

for (nn=0; nn<=nIndMax; nn++) {
   if (rvMin > avVals[nn]) rvMin = avVals[nn];
   if (rvMax < avVals[nn]) rvMax = avVals[nn];
   }

// Le compilateur accepte que l'on modifie une valeur du tableau.
// Cela est parfois désiré, parfois mène à des erreurs.
avVals[0]=rvMin;
} // MinMax1

void MinMax2( unsigned int nIndMax, double const avVals[],
              double& rvMin, double& rvMax) {
//===========================================
// Retourn dans rvMin la valeur min. de avVals[nIndMax].
// Retourn dans rvMax la valeur max. de avVals[nIndMax].
// L'avantage de cette manière est que le compilateure vérifie
// que le tableau avVals n'est pas modifié, malgré qu'il est aussi
// transmis par référence.

unsigned int nn=0;
rvMin = avVals[0];
rvMax = rvMin;

for (nn=0; nn<=nIndMax; nn++) {
   if (rvMin > avVals[nn]) rvMin = avVals[nn];
   if (rvMax < avVals[nn]) rvMax = avVals[nn];
   }

// Le compilateur Refuse que l'on modifie une valeur du tableau.
// C'est une sécurité à la compilation, pour éliminer des erreurs potentiels.
// avVals[0]=rvMin;
} // MinMax2

void test04() {
//============
// Test les exemples de recherche de min et de max

// déclaration d'une constante qui sera la dimension du tableau avNb
unsigned int const nDim = 100;

// décalaration du tableau. L'indice ira de 0 à nDim-1
// Attention au "-1"
double avNb[nDim];

unsigned int nIndMax = 50; // Indice maximum utilisé du tableau.
double vX, vMin, vMax;
double vMin2, vMax2;

for (unsigned int nn=0; nn<=nIndMax; nn++) {
   // rempli le tableau avec des valeurs du polynome y = x^3 - x + 0.1
   vX = -1.0 + 2.0 * nn / nIndMax;  // varie de -1 à 1
   avNb[nn] = vX*vX*vX - vX + 0.1;

   // pour des vérifications
//   cout << "X=" << vX << "  Y=" << avNb[nn] << endl;
   printf("X=%9.3f,   Y=%9.5f\n", vX, avNb[nn]);
   }

MinMax1(nIndMax, avNb, vMin, vMax);
cout << "Min=" << vMin << "  Max=" << vMax << endl;

// Cette fonction et avantageuse sur la précédente.
MinMax2(nIndMax, avNb, vMin2, vMax2);
cout << "Min=" << vMin2 << "  Max=" << vMax2 << endl;
} // test04
//#############################################################

// 5.
// Exercice.
// Ecrivez une fonction qui trie les valeurs d'un tableau
// de la plus petite valeur à la plus grande.
// Il existe de nombreuses méthodes, certaines sont
// beaucoup plus efficaces que d'autres.

void Sort1( unsigned int const nIndMax, double avVals[]) {
//========================================================
// Trie les valeurs de avVals[nIndMax] du plus petit au plus grand.
// Le tableau est donc modifié.
// Non optimal, avec allocation dynamique de mémoire
unsigned int nn=0, nInd=0, nIndMin=0;
double vMin;

// alloue de la mémoire temporairement, pour le traitement.
double *pavT = NULL;  // NULL = 0, utile pour des pointeurs.
pavT = new double [nIndMax+1];
// double *pavT = new double [nIndMax+1]; // est aussi possible

// Recopie le tableau dans pavT[0..nIndMax]
for (nn=0; nn<=nIndMax; nn++) pavT[nn] = avVals[nn];

// le plus grand entier signé sur 32 bits
//cout << numeric_limits<int>::max() << endl;

// le plus grand double
//cout << std::numeric_limits<double>::max() << endl;
// c.f. http://www.cplusplus.com/reference/limits/numeric_limits/

// Tri
for (nInd=0; nInd<nIndMax; nInd++) {
   // recherche la plus petite valeur dans pavVals[nInd..nIndMax]
   vMin = pavT[nInd];
   nIndMin = nInd; // Mémorise l'indice de la plus petite valeur
   for (nn=1; nn<=nIndMax; nn++) {
      if (vMin > pavT[nn]) { vMin = pavT[nn]; nIndMin = nn; }
      }

   // Place la plus petite valeur trouvée dans le tableau d'origine
   avVals[nInd] = pavT[nIndMin];
   pavT[nIndMin] = std::numeric_limits<double>::max();  // détruit la valeur pour qu'elle ne réapparaisse pas
   }

// Libère la mémoire allouée temporairement
delete[] pavT;
pavT = NULL; // inutile ici, mais c'est une bonne habitude à prendre.
} // Sort1

void Sort2( unsigned int const nIndMax, double avVals[]) {
//========================================================
// Trie les valeurs de avVals[nIndMax] du plus petit au plus grand.
// Le tableau est donc modifié.

A COMPLETER...

} // Sort2

void test05() {
//============
// Test la fonction de tri par ordre croissant.

// déclaration d'une constante qui sera la dimension du tableau avNb
unsigned int const nDim = 100;

// décalaration du tableau. L'indice ira de 0 à nDim-1
// Attention au "-1"
double avNb[nDim];

unsigned int nIndMax = 30; // Indice maximum utilisé du tableau.
double vX;

// initialize random seed:
srand (time(NULL));

for (unsigned int nn=0; nn<=nIndMax; nn++) {
   // rempli le tableau avec des valeurs du polynome y = x^3 - x + 0.1
   vX = -1.0 + 2.0 * nn / nIndMax;  // varie de -1 à 1
   avNb[nn] = vX*vX*vX - vX + 0.1;

   // Autre manière, remplissage au hasard
//   avNb[nn] = 1.0 * rand() / RAND_MAX; // nombres entre 0 et 1.

   // pour des vérifications
   printf("X=%9.3f,   Y=%9.5f\n", vX, avNb[nn]);
   }

// Trie les valeurs du tableau par ordre croissant.
Sort1(nIndMax, avNb);

// Affiche les valeurs triées du tableau
cout << "Du plus petit au plus grand, avec Sort1 :" << endl;
for (unsigned int nn=0; nn<=nIndMax; nn++) {
   printf("%9.5f\n", avNb[nn]);
   }

} // test05
//#############################################################

// 6.
// Exercice.
// Ecrivez une fonction qui trie les valeurs d'un tableau
// de la plus petite valeur à la plus grande.
// Méthode quicksort, récursive, très rapide.

void QuickSort( int const nIndMin,
                int const nIndMax,
                double avVals[]) {
//==========================================================
// Trie les valeurs de avVals[nIndMin..nIndMax] du plus petit au plus grand.
// Le tableau est donc modifié.

// Place au début de tableau toutes les valeurs inférieurs à vRef
// ensuite place les valeurs égales à vRef
// place ensuite toutes les valeurs plus grandes que vRef.
int nL=0, nR=0; // Indices Left et Right
double vPivot;

nL=nIndMin;  nR=nIndMax;
vPivot=avVals[(nL+nR)/2];
// servira à séparer les éléments en plaçant à gauche les plus petit que vPivot
// et à droite les plus grand que vPivot.

do {
   // Cherche depuis la gauche un élément plus grand que vPivot
   while (avVals[nL] < vPivot) nL++; // s'arrête forcément !
   // Cherche depuis la droite un élément plus petit que vPivot
   while (avVals[nR] > vPivot) nR--; // s'arrête forcément !

   // Utilise la fonction Echange vue précédemment, pour
   // placer la plus petite valeur à gauche et la plus grande à droite.
   if (nL < nR) Echange(avVals[nL], avVals[nR]);

   if (nL <= nR) {nL++;  nR--; } // pour passer aux éléments suivants.
   } while (nL <= nR);

// Ici, les élèments "<=vPivot" sont à gauche  (nIndMin..nR)
// et ceux plus ">=vPivot" sont à droite (nL..nIndMax)
// On refait le même placement sur les sous-tableaux, gauche et droit.
// Pour cela on fait appelle à de la récursivité, c'est-à-dire
// qu'une fonction s'appelle elle-même.
if (nIndMin < nR   ) QuickSort(nIndMin, nR,      avVals);
if (nL    < nIndMax) QuickSort(nL,      nIndMax, avVals);
} // QuickSort
// Trois améliorations possibles.
// 1) Meilleur choix du pivot
// 2) Tri différent si moins de 6 éléments à trier
// 3) L'odre des appels récursifs à tester pour minimiser
//    la profondeur de récursivité.

void test06() {
//============
// Test la fonction de tri par ordre croissant.

// déclaration d'une constante qui sera la dimension du tableau avNb
unsigned int const nDim = 100;

// décalaration du tableau. L'indice ira de 0 à nDim-1
// Attention au "-1"
double avNb[nDim];

int nIndMax = 30; // Indice maximum utilisé du tableau.
double vX;

// initialize random seed:
srand (time(NULL));

for (int nn=0; nn<=nIndMax; nn++) {
   // rempli le tableau avec des valeurs du polynome y = x^3 - x + 0.1
   vX = -1.0 + 2.0 * nn / nIndMax;  // varie de -1 à 1
   avNb[nn] = vX*vX*vX - vX + 0.1;

   // Autre manière, remplissage au hasard
//   avNb[nn] = 1.0 * rand() / RAND_MAX; // nombres entre 0 et 1.

   // pour des vérifications
   printf("nn=%3d,  X=%9.3f,   Y=%9.5f\n", nn, vX, avNb[nn]);
   }

// Trie les valeurs du tableau par ordre croissant.
QuickSort(0, nIndMax, avNb);

// Affiche les valeurs triées du tableau
cout << "Du plus petit au plus grand, avec Quicksort :" << endl;
for (int nn=0; nn<=nIndMax; nn++) {
   printf("%9.0f\n", 10000*avNb[nn]);
   }

} // test06
//#############################################################

// 7.
// Exemple plus simple d'appel récursif.
// Calcul de la fonction factorielle.
// Par définition, n! = n * (n-1)!  et  0! = 1.

int64_t Factoriel(int const nNb) {
//================================
// Calcul la factoriel de nNb
// Fonctionne pour nNb compris entre 0 et 20,
// ensuite on dépasse les capacités de l'ordinateur.
if (nNb <= 0) return 1;
return nNb * Factoriel(nNb-1);
} // Factoriel

void test07() {
//============
// Test la fonction Factorielle.
int64_t nNb;

do {
   cout << "Entrez un nombre entier entre 0 et 20 : ";
   cin >> nNb;
   cout << nNb << "! = " << Factoriel(nNb) << endl;
   } while (nNb > 0);
} // test07
//#############################################################

int main() {
//==========
test05();
return 0;
}