#include <cstdlib>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <conio.h>
#include <time.h>


int NbIteration;

void InitIterattion()
{
     NbIteration=0;
}

void Iteration()
{
     NbIteration++;
}

//Lineaire 

int Lineaire(int x, int v[],int n)
{
            int i;
            InitIterattion();
            for (i = 0; i < n && x > v[i]; i++)
            {
                Iteration();
            }
            if (i < n && v[i] == x) return i;
            return -1;
}

//Dichotomique

int Dichotomique(int x, int v[],int n)
{

     int Debut=0,Fin=n-1,Milieu;
     InitIterattion();
     while(Debut<=Fin)
     {
                      Iteration();
                      Milieu=(Debut+Fin)/2;
                      if(x<v[Milieu]) Fin=Milieu-1;
                      else if(x>v[Milieu]) Debut=Milieu+1;
                           else return Milieu;              
     }
     return -1;
}

//Hachage

typedef struct elt
{
        int *Pos;
        int n;
}ElementIndex;

ElementIndex Index[10];

void InitIndex(int n)
{
     int i;
     for(i=0;i<10;i++)
     {
                     Index[i].Pos=(int *)malloc(n*(sizeof (int)));
                     Index[i].n=0;
     }
}

void RomplireIndex(int x,int pos)
{
     int cle=x%10;
     Index[cle].Pos[Index[cle].n]=pos;
     Index[cle].n++;
}

void AfficheIndex()
{
     int i,j;
     ElementIndex EI;
     int n;
     printf ("\n");
     printf("Index:\n");
     printf("----- \n");
     for(i=0;i<9;i++)
     {
                      EI=Index[i];
                      n=EI.n;
                      printf(" Cle:%d\n",i);
                      for(j=0;j<n;j++) printf("  %d\n",EI.Pos[j]);
     }
}

int Hachage(int x, int v[],int n)
{
    InitIterattion();
    ElementIndex EI=Index[x%10];
    int i,Npos=EI.n;
    for(i=0;i<Npos && v[EI.Pos[i]]<x;i++) 
    {
                   Iteration();
    }
    if(i<Npos && v[EI.Pos[i]]==x) return EI.Pos[i];
    return -1;
}

//ArbreBinaire

typedef struct elt2
{
        int x;
        int Pos;
        struct elt2 *Inf;
        struct elt2 *Sup;
}Noeud;

Noeud *Arbre;

void RomplireArbre(int x,int Pos)
{
     if(Arbre==NULL)
     {
                    Arbre=(Noeud*)malloc(sizeof(Noeud));
                    Arbre->Inf=Arbre->Sup=NULL;
                    Arbre->x=x;
                    Arbre->Pos=Pos;
     }
     else
     {
         Noeud *N=Arbre,*NP=NULL;
         while(N!=NULL)
         {
                       NP=N;
                       if(x<N->x) N=N->Inf;
                       else N=N->Sup;
         }
         N=(Noeud*)malloc(sizeof(Noeud));
         N->Inf=N->Sup=NULL;
         N->x=x;
         N->Pos=Pos;
         if(NP!=NULL)
         {
                     if(x<NP->x) NP->Inf=N;
                     else NP->Sup=N;
         }
     }
}

void RomplireArbre(int v[],int Debut,int Fin)
{
     int Milieu;
     if(Debut<=Fin)
     {
                   Milieu=(Debut+Fin)/2;
                   RomplireArbre(v[Milieu],Milieu);
                   RomplireArbre(v,Debut,Milieu-1);
                   RomplireArbre(v,Milieu+1,Fin);         
     }
}

void AfficheArbre(Noeud *N)
{
     if(N!=NULL)
     {
                printf ("@N%d(%d,%d,%d,%d)\n",N,N->x,N->Pos,N->Inf,N->Sup);
                AfficheArbre(N->Inf);
                AfficheArbre(N->Sup);
     }
}

int ArbreBinaire(int x)
{
    InitIterattion();
    Noeud *N=Arbre;
    while(N!=NULL && N->x!=x)
    {
                  Iteration();
                  if(x<N->x) N=N->Inf;
                  else N=N->Sup;
    }
    if(N!=NULL) return N->Pos;
    return -1;
}

//fonction utile

void VecteurAleatoir(int v[],int n)
{
      int i;
      v[0]=0;
      RomplireIndex(v[0],0);
      //RomplireArbre(v[0],0);
      for(i=1;i<n;i++) 
      {
                       v[i]= v[i-1]+rand()%10;
                       RomplireIndex(v[i],i);
                       //RomplireArbre(v[i],i);
      }
}

void RemplireVecteur(int v[],int n)
{
     int i;
     for(i=0;i<n;i++)
     {
                     printf ("v[%d]=",i);
                     scanf ("%d",&v[i]);
                     RomplireIndex(v[i],i);
                     //RomplireArbre(v[i],i);
     }
}

void AfficherVecteur(int v[],int n)
{
     int i;
     for(i=0;i<n;i++) printf ("v[%d]=%d\n",i,v[i]);
}

int main()
{
    int i,pos, n, x,rep;
    printf ("n=");
    scanf("%d",&n);
    InitIndex(n);
    //int v[n];
    int *v=(int*)malloc(n*(sizeof(int)));
    printf ("Remplir(1|2):");
    scanf ("%d",&rep);
    if(rep==1) RemplireVecteur(v,n);
    if(rep==2)
    {
               VecteurAleatoir(v,n);
               AfficherVecteur(v,n);
    }
    printf ("x=");
    scanf("%d",&x);
    clock_t Debut,Fin;
    float Temp;
    //Lineaire
    Debut=clock();
    pos=Lineaire(x,v,n);
    Fin=clock();
    Temp=(float)(Fin-Debut)/CLOCKS_PER_SEC;
    printf ("\n");
    printf("Lineaire:\n");
    printf("--------\n");
    printf(" Position         :%d \n",pos);
    printf(" Temp d'execution :%f\n",Temp);
    printf(" Nombre iteration :%d\n",NbIteration);
    //Dichotomique
    Debut=clock();
    pos=Dichotomique(x,v,n);
    Fin=clock();
    Temp=(float)(Fin-Debut)/CLOCKS_PER_SEC;
    printf ("\n");
    printf("Dichotomique:\n");
    printf("------------\n");
    printf(" Position         :%d \n",pos);
    printf(" Temp d'execution :%f\n",Temp);
    printf(" Nombre iteration :%d\n",NbIteration);
    //Hachage
    //AfficheIndex();
    Debut=clock();
    pos=Hachage(x,v,n);
    Fin=clock();
    Temp=(float)(Fin-Debut)/CLOCKS_PER_SEC;
    printf ("\n");
    printf("Hachagee:\n");
    printf("--------\n");
    printf(" Position         :%d \n",pos);
    printf(" Temp d'execution :%f\n",Temp);
    printf(" Nombre iteration :%d\n",NbIteration);
    //ArbreBinaire
    RomplireArbre(v,0,n-1);
    //AfficheArbre(Arbre);
    Debut=clock();
    pos=ArbreBinaire(x);
    Fin=clock();
    Temp=(float)(Fin-Debut)/CLOCKS_PER_SEC;
    printf ("\n");
    printf("ArbreBinaire:\n");
    printf("------------\n");
    printf(" Position         :%d \n",pos);
    printf(" Temp d'execution :%f\n",Temp);
    printf(" Nombre iteration :%d\n",NbIteration);
    //
    scanf("%d",&n);
}