FILE DE PRIORITÉ DYNAMIQUE

#define TAILLE_MAX 524288
/**
* @author Mehdi El Masaodui
*
*/
template <typename TYPE>
class FilePrioDyn{

    private:
    bool vide;
    int longueur;
    TYPE sommet;
    TYPE elements[TAILLE_MAX]; // éléments de la liste

    public:
    FilePrioDyn(TYPE[],int); // le constructeur vide est désactivé
    void ajouter(TYPE); // ajouter un element
    bool fileVide(); // etat de la file, vide ou non
    TYPE premier(); // retourne la valeur de la racine
    TYPE reduire(); // enlève la racine, puis tamise
    void tamiser(int); //organiser les élémeent du haut vers le bas
    void percoler(int); // organiser les éléments du bas vers le haut
    void construire(TYPE[],int); // construction de la file dynamique de priorité
    bool getVide(); // accesseur en lecture de (bool vide)
    void afficher(); // afficher la liste
};
/**
* @param TYPE temp : tableau à base duquel on va construire la file de priorité
* @param int taille : la taille du tableau, on la passe explicitement parceque on ne peut pas récuperer la taille du tableau sur l'objet tableau en C++
*
*/
template <typename TYPE>
FilePrioDyn<TYPE>::FilePrioDyn(TYPE temp[],int taille){
    construire(temp,taille);
}
/**
* @return L'état de la liste , true : vide , false : non-vide
*
*/

template <typename TYPE>
bool FilePrioDyn<TYPE>::fileVide(){
    return getVide();
}
/**
* @return L'état de la variable vide
*
*/
template <typename TYPE>
bool FilePrioDyn<TYPE>::getVide(){
    return vide;
}

/**
* @return Le sommet de la file de priorité
*/
template <typename TYPE>
TYPE FilePrioDyn<TYPE>::premier(){
    return elements[0];
}
/**
* @return l'élément qui a été supprimé
* @description retire un élément du sommet, réduit la taille de un et tamise
*/

template <typename TYPE>
TYPE FilePrioDyn<TYPE>::reduire(){
    TYPE temp;
    if(!fileVide()){
        elements[0]=elements[longueur];
        longueur=longueur--;
        tamiser(0);
    }else{
        /* la file est vide, aucun élément à retirer*/
    }
    return temp;
}

/**
* @param val élément à ajouter à la fin
*        percoler à partir de l'élement ajouté
*/

template <typename TYPE>
void FilePrioDyn<TYPE>::ajouter(TYPE val){
    longueur++;
    elements[longueur]=val;
    percoler(val);
}

/**
* @param temp tableau à partir duquel on construit la file de priorité
* @param int taille taille du tableau
*        on ajoute un élément à la fin à chaque itération, on percole après chaque élément ajouté
*
*/
template <typename TYPE>
void FilePrioDyn<TYPE>::construire(TYPE temp[],int taille){
    longueur=taille;
    int i;
    if(longueur>0){
        i=0;
        while(i<longueur){
            elements[i]=temp[i];
            percoler(i);
            i++;
        }
    }

}

/**
* @param i , l'élémentt ajouté à partir duquel tamiser,
*           on tamise vers la bas de la structure
*
*/
template <typename TYPE>
void FilePrioDyn<TYPE>::tamiser(int i){

    int k=i;
    int j=0; /* correction */
    while(j!=k){
        j=k;
        if(2*j<longueur && elements[2*j]>elements[k]){
            k=2*j;
        }
        if(2*j<longueur && elements[2*j+1]>elements[k]){
            k=2*j+1;
        }
        elements[j]=elements[k];
    }
}

/**
* @int i element à partir duquel percoler
* percoler est le fait de parcourir la structure à partir du dernier élément ajouté
* pour verifier le principe de priorité ( ordre )
*
*/
template <typename TYPE>
void FilePrioDyn<TYPE>::percoler(int i){
   int k=i;
   int j=0;
   while(j!=k){
       j=k;
       if(j>1 && elements[j/2]<elements[k]){
           k=j/2;
       }
       elements[j]=elements[k];
   }
}

/**
* Affichage de la liste sous forme d'un arbre
*/
template <typename TYPE>
void FilePrioDyn<TYPE>::afficher(){
    int i=0;
    while(elements[i]){
    std::cout<<"|Element "<<i<<" : "<<elements[i]<<"";
    i++;
    }
}