#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "tas.h"
#include "arbrebinaire.h"
#define TAILLE_ELEMENT 258

struct Tas
{
 ArbreBinaire arb;
 fonction_comparer fct;
};

void Echanger(tas a,int indice1,int indice2)
{
 void * tmp = malloc(a->arb->taille_element);
 memcpy(tmp,a->arb->info[indice1],a->arb->taille_element);
 memcpy(a->arb->info[indice1],a->arb->info[indice2],a->arb->taille_element);
 memcpy(a->arb->info[indice2],tmp,a->arb->taille_element);
 free(tmp);
}

tas tas_creer(fonction_comparer f)
{
    tas t=(tas)malloc(sizeof(struct Tas));
	t->arb=CreerArbreBinaire(TAILLE_ELEMENT);
    t->fct=f;
    return t;
}
void tas_liberer(tas self)
{
 ArbreLiberer(self->arb);
 free(self);
}
static void OrganiseTasMontant( tas a, int indice_sommet)
{
 int p = pere(a->arb, indice_sommet);
 int signal= 1;
 while((indice_sommet!=Racine(a->arb)) && signal)
 {
  if(a->fct(ValeurSommet(a->arb,indice_sommet),ValeurSommet(a->arb,p))>0)
  {
   Echanger(a,p,indice_sommet);
   indice_sommet=p;
   p=pere(a->arb,indice_sommet);
  }
  else
    signal=0;  
 }
}
void tas_inserer(tas self, void *element)
{
 Ajouter(self->arb , element);
 OrganiseTasMontant(self,self->arb->Ind_dernier);
}
static void ReorganisTasDesc(tas a, int indice_sommet)
{
 int g =FilsGauche(a->arb, indice_sommet);
 int d =FilsDroite(a->arb, indice_sommet);
 if (g!=-1)
 {
  if(d!=-1)
  {
   if(a->fct(ValeurSommet(a->arb,d),ValeurSommet(a->arb,g))>0)
     g=d;
  }
  if(a->fct(ValeurSommet(a->arb,g),ValeurSommet(a->arb,indice_sommet))>0)
  {
   Echanger(a,indice_sommet,g);
   ReorganisTasDesc(a, g);
  }          
 }
}
void* tas_retirer_sommet(tas self)
{
 void * a= malloc(self->arb->taille_element);
 memcpy(a, self->arb->info[0],self->arb->taille_element);
 memcpy(self->arb->info[0], self->arb->info[self->arb->Ind_dernier], self->arb->taille_element); 
 free(self->arb->info[self->arb->Ind_dernier]);
 self->arb->info[self->arb->Ind_dernier]=NULL;
 self->arb->Ind_dernier=self->arb->Ind_dernier-1;
 ReorganisTasDesc(self,Racine(self->arb));
 return a;
}
unsigned tas_cardinal(tas self)
{
 return self->arb->Ind_dernier+1;
}