/******************************************
 *
 *   Cedric Pradalier   2001
 *   mail : http://cedric.pradalier.free.fr/mail.html
 *
 *****************************************/



#include "output.h"
#include "vector.h"
#include <stdio.h>
/******************************************

  Implementation des tables extensibles,
  Insertion/Suppression en O(1) -- Cout amorti

********************************************/


/* La suppression ne conserve pas l'ordre */
void CVector::suppr(int i)
{
    /* Suppression valide */
    if ((i<0) || (i>=NbElem))
    {
        sprintf(outbuf,"CVector::supr : element inexistant %i\n",i);FlushBuffer();
        exit(1);
    }
    /* L'element passe a la fin et est remplace par
       le dernier */
    tElems[i] = tElems[NbElem-1];
    NbElem -= 1;
    /* Si le tableau n'est plus assez rempli, on le reduit
       physiquement,et on recopie */
    if (NbElem < (Size / 4))
    {
        CObjet ** temp;
        Size /= 2; /* Taile / 2 */
        temp = new (CObjet*)[Size];
        for (int j=0;j<NbElem;j++)
            temp[j] = tElems[j];
        delete [] tElems;
        tElems = temp;
    }
}

/* On ajoute, si le tableau est plain,
   on l'agrandit physiquement et on recopie */
void CVector::add(CObjet * elem)
{
//  sprintf(outbuf,"etat : ne %i -- sz %i \n",NbElem,Size);FlushBuffer();
    if (NbElem == Size)
    {
//      sprintf(outbuf,"on recopie...\n");FlushBuffer();
        CObjet ** temp;
        Size *= 2;/* Taille * 2 */
        temp = new (CObjet*)[Size];
        for (int j=0;j<NbElem;j++)
            temp[j] = tElems[j];
        delete [] tElems;
        tElems = temp;
    }
    tElems[NbElem] = elem;
    NbElem += 1;
}

void CVector::TrimToSize()
{
    if ((NbElem==0) || (NbElem==Size))
        return;
    else
    {
//      sprintf(outbuf,"on recopie...\n");FlushBuffer();
        CObjet ** temp;
        Size = NbElem;
        temp = new (CObjet*)[Size];
        for (int j=0;j<NbElem;j++)
            temp[j] = tElems[j];
        delete [] tElems;
        tElems = temp;
    }
}   

/* Accede a un element */
CObjet * CVector::operator[](int i)
{
    if ((i<0) || (i>=NbElem))
    {
        sprintf(outbuf,"CVector::operator[] : element inexistant %i\n",i);FlushBuffer();
        exit(1);
    }
    return tElems[i];
};

/* Pareil mais plus facile a appele pour des pointeurs */
CObjet * CVector::ElemAt(int i)
{
    if ((i<0) || (i>=NbElem))
    {
        sprintf(outbuf,"CVector::ElemAt : element inexistant %i\n",i);FlushBuffer();
        exit(1);
    }
    return tElems[i];
};

void CVector::Print()
{
    sprintf(outbuf,"[|");FlushBuffer();
    for (int i=0;i<NbElem;i++)
    {
        tElems[i]->Print();
        sprintf(outbuf," ;FlushBuffer(); ");
    }
    sprintf(outbuf,"\b|]");FlushBuffer();
}


// Fusionne 2 partie ordonnée du tableau T
void Fusionne(CObjet * T[],CObjet * Dest[],int i1, int j1,int i2,int j2)
{
    int k1 = i1;
    int k2 = i2;
    int k = i1;
//  sprintf(outbuf,"Entree de fusionne [%i,%i] & [%i,%i] \n",i1,j1,i2,j2);FlushBuffer();
    while ((k1 < j1) || (k2 < j2))
    {
        if (k2 == j2)
        {
            Dest[k] = T[k1];
            k += 1;
            k1 = (k1+1 > j1) ? j1 : (k1 + 1);
        } 
        else if ((T[k2]->Value() < T[k1]->Value()) || (k1 == j1))
        {
            Dest[k] = T[k2];
            k += 1;
            k2 = (k2+1 > j2) ? j2 : (k2 + 1);
        }
        else
        {
            Dest[k] = T[k1];
            k += 1;
            k1 = (k1+1 > j1) ? j1 : (k1 + 1);
        }
    }
    // Quand c'est trie on recopie
    for (k=i1;k<j2;k++)
        T[k] = Dest[k];
}
            


// Tri du tableau dont les indices sont k t.q.
//  i <= k < j
void TriPartition(CObjet * T[],CObjet * Dest[],int i,int j)
{
//  sprintf(outbuf,"Entree de Tri Partition (%i,%i) ",i,j);FlushBuffer();
    if (i<j-1)
    {
        int milieu = (i + j) / 2;
//      sprintf(outbuf," Avec Appel recursif (%i)\n ",milieu);FlushBuffer();
        TriPartition(T,Dest,i,milieu);
        TriPartition(T,Dest,milieu,j);
        Fusionne(T,Dest,i,milieu,milieu,j);
    }
    else
        Dest[i] = T[i];
        
}
        




void CVector::Sort()
{
    // Un petit tri fusion de derriere les fagots ...
    CObjet ** Dest = new (CObjet*)[NbElem];
    TriPartition(tElems,Dest,0,NbElem);
    delete [] Dest;
}






/*
int f(int x)
{ 
    return x*x;
};

int main()
{
    CVector v;
    int i,j;
    sprintf(outbuf,"on commence..\n");FlushBuffer();
    for (j=0;j<24;j++)
    {
        sprintf(outbuf,".\n");FlushBuffer();
        v.add((void*) f(j));
    }

    for (j=0;j<24;j++)
        sprintf(outbuf,"i: %i\n",(int)v[j]);FlushBuffer();
    for (j=0;j<24;j++)
    {
        v.suppr(0);
        sprintf(outbuf,"...\n");FlushBuffer();
        for (i=0;i<(23-j);i++)
            sprintf(outbuf,"-[ i: %i\n",(int)v[i]);FlushBuffer();
    }
}
*/