/*
Martin Robinson
Tri, recherche et fusion de vecteurs
lab11
============================================
directive du preprocesseur
*/

#include <iostream>

#include "../lib/algoMR.hpp"
#include "../lib/saisieMR.hpp"

using namespace std;

#define QTYA 5
#define QTYB 5

/*
============================================
prototype de fonction
*/
void saisieVecteur(saisie <int> saisirInt, int vecteur[], int qty, char finMessage[]);
void afficherVecteur(int[] , int , const char * );
void trieFusion(int vA[],int _qtyA, int vB[], int _qtyB, int vC[]);
int rechercheLineaire(int vecteur[], int qty, int nb);
int rechercheDichotomique(int vecteur[], int qty, int nb);

/*
===========================================
programme principale
*/


int main()
{
    
    //initialisation
    int vecteurA[QTYA],         //premier tableau
        vecteurB[QTYB],         //deuxieme tableau
        vecteurC[QTYA+QTYB],    //fusion des deux tableau
        nombre,                 //nombre à rechercher
        position=-1;            //position de recherche
        
    saisie <int> saisirInt("");
	saisie <void> pause("appuyer sur une touche pour continuer\n");
    
    //Lire 2 séries de 5 nombres qui sont stockés dans 2 vecteurs différents.
	saisieVecteur(saisirInt, vecteurA, QTYA, " nombres :\n");
    saisieVecteur(saisirInt, vecteurB, QTYB, "autres nombres :");
    
    //Trier en ordre croissant le 1er vecteur à l’aide du tri par sélection.
    selectSort <int,QTYA> (vecteurA);       //voir algoMR.hpp
    
    //Trier en ordre décroissant le 2e vecteur à l’aide du tri par insertion.
    insertSort <int,QTYB> (vecteurB,true);  //voir algoMR.hpp
    
    //Fusionner ensuite ces 2 vecteurs pour avoir un vecteur de 10 nombres triés.  
    //selectSort <int,QTYB>(vecteurA);
	trieFusion(vecteurA, QTYA, vecteurB, QTYB, vecteurC);   //j'ai triché, mon triefusion n'a pas besoin de vecteur préalablement trier, il le fait tout seul
    
    //Afficher ensuite les 2 vecteurs triés.
    afficherVecteur(vecteurA,QTYA,"Voici le premier vecteur trié croissant avec tri par sélection :");
    afficherVecteur(vecteurB,QTYB,"Voici le deuxième vecteur trié décroissant avec tri par insertion:");
    
    //Afficher le vecteur fusionné et trié
    afficherVecteur(vecteurC,QTYA+QTYB,"Voici la fusion des deux vecteurs triée en ordre croissant");
    
    //Demander un nombre à rechercher dans le vecteur fusionné 
    cout << "Entrer un nombre à recherché : ";

    saisirInt >> nombre;
    //position = rechercheLineaire(vecteurC, QTYA+QTYB, nombre);
    position = rechercheDichotomique(vecteurC, QTYA+QTYB, nombre);
    
    //et affiche sa position dans ce vecteur.  Si le vecteur ne contient pas le nombre voulu, un message affiche que ce nombre n’est pas dans le vecteur.
    if (position!=-1)
        cout << "Le nombre "<< nombre 
             << " fut trouvé à la position "
             << position <<" du vecteur fusionné\n";
    else
        cout << "ce nombre n’est pas dans le vecteur.\n";
    
	pause();    //pas la version microsoft mais une instance d'objet saisie
    return 0;
}

/*
===================================================================================
fonction
*/

//saisir vecteur
void saisieVecteur(saisie <int> saisirInt, int vecteur[], int qty, char finMessage[])
{
	cout << "Entrer "<< qty 
		 << " " << finMessage << endl;
    for (int i = 0;i<qty;i++)
        saisirInt >> vecteur[i];
}

//affiche le contenu d'un vecteur
void afficherVecteur(int vecteur[], int qty, const char * message)
{
    cout << message << endl;
    for (int i=0;i<qty;i++)
        cout << vecteur[i] << " ";
    cout << endl;
}

//fusionner les deux vecteurs avec un trie dans la meme boucle
void trieFusion(int vA[],int _qtyA, int vB[], int _qtyB, int vC[])
{
	int tmp,
		j;
	for (int i = 0; i<_qtyA;i++)        //une version inversé du gnomesort
	{
		vC[i] = vA[i];                  //ajout la variable dans la liste
		j = i;
		while (j>0 && vC[j]<vC[j-1])    //echange avec le precédant tant que plus petit que ce dernier ou index=0
		{
			tmp = vC[j];
			vC[j] = vC[j-1];
			vC[j-1] = tmp;
			j--;
		}
	}
	for (int i = 0; i<_qtyB;i++)        //meme algo avec la deuxieme liste, 
	{
		j = i+_qtyA;
		vC[j] = vB[i];
		while (j>0 && vC[j]<vC[j-1])
		{
			tmp = vC[j];
			vC[j] = vC[j-1];
			vC[j-1] = tmp;
			j--;
		}
	}

}

//recherche linéaire
int rechercheLineaire(int vecteur[], int qty, int nb)
{
    for (int i=0;i<qty;i++)
        if (vecteur[i]==nb)
            return i;
    return -1;
}

//recherche par méthode dichotomique
int rechercheDichotomique(int vecteur[], int qty, int nb)
{
    int a = 0,
        b = qty,
        pivot = qty/2;
    while (b-a > 1)
    {
        if (vecteur[pivot] < nb)
            a = pivot;
        else if (vecteur[pivot] > nb)
            b = pivot;
        else
            return pivot;
        pivot = a+((b-a)/2);
    }
    return -1;
}