/************************************************************************/
/* Auteur : S. Gueye							*/
/* TP : Arbres Binaires	de Recherche					*/
/* Date dernière maj : 25/11/2019					*/
/************************************************************************/

#include <iostream>
#include <fstream>
#include <algorithm>
#include "tri.h"

using namespace std;


/****************************************/
/* Objectif : Echange
/* Complexité : 0(1)
/****************************************/
tas::tas(int max)
{
	this->max = max;
	T = new int[max];
	n = 0;
}

/****************************************/
/* Objectif : Constructeur
/* Complexité : 0(n)
/****************************************/
tas::tas(char* filename){
	ifstream file(filename);
	int nb,tmp;

	file >> nb;

	T = new int[nb];
	n = 0;
	for(int i = 0; i < nb ; i++){
		file >> tmp;
		insertion(tmp);
	}
	file.close();

}


/****************************************/
/* Objectif : Echange
/* Complexité : 0(1)
/****************************************/
void tas::echange(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}


/****************************************/
/* Objectif : Affichage
/* Complexité : 0(n)
/****************************************/
void tas::affiche()
{
	cout << "T =";
	for(int i = 0; i < n; i++)
		cout << " " <<  T[i];
	cout << endl;
}

/****************************************/
/* Objectif : Insertion d'un entier x
/* Complexité : 0(log(n))
/****************************************/
void tas::insertion(int x)
{
    // !!! A FAIRE !!! //
    T[n] = x;
    int i = n;
    while(i>=0 && T[i]<T[((i-1)/2)]){
        echange(T[i],T[((i-1)/2)]);
        i = ((i-1)/2);
    }
    n++;
}

/****************************************/
/* Objectif : Reorganiser en un tas à partir de l'élément T[j]
/* Complexité : 0(log(n))
/****************************************/
void tas::reorganiser(int j)
{
	// !!! A FAIRE !!! //
	if(n>0){
	    int i = j;
    	int m;
    	while(i<=((n/2)-1)){
    	    if(T[2*i+1] < T[2*i+2]){
    	        m = 2*i+1;
    	    }
    	    else{
    	        m = 2*i+2;
    	    }
    	    if(T[i]>T[m]){
    	        echange(T[i],T[m]);
    	        i = m;
    	    }
    	    else{
    	        i = n;
    	    }
    	}
	}
}

/****************************************/
/* Objectif : renvoie de l'élément de la valeur minimale et réorganisation du tableau
/* Complexité : 0(log(n))
/****************************************/
int tas::suppression()
{
    // !!! A FAIRE !!! //
    int min = T[0];
    T[0] = T[n-1];
    n--;
    reorganiser(0);
    return min;
}

/****************************************/
/* Objectif : Tri du tableau T
/* Complexité : 0(nlog(n))
/****************************************/
void tas::tri()
{
    // !!! A FAIRE !!! //
   /* for(int k=0; k=(n-1)/2; k--){
        reorganiser(k);
    }*/
    int k = n;
    int min;
    while(n>0){
        min = suppression();
        T[n] = min;
    }
    n=k;
}