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


#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 Vector::deleteElement(int i)
{
    /* Suppression non valide */
    if ((i<0) || (i>=NbElem))
    {
        printf("Vector::deleteElement : element inexistant %i\n",i);
        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))
    {
        Object ** temp;
        Size /= 2; /* Taile / 2 */
        temp = new (Object*)[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 Vector::addElement(Object * elem)
{
    if (NbElem == Size)
    {
        Object ** temp;
        Size *= 2;/* Taille * 2 */
        temp = new (Object*)[Size];
        for (int j=0;j<NbElem;j++)
            temp[j] = tElems[j];
        delete [] tElems;
        tElems = temp;
    }
    tElems[NbElem] = elem;
    NbElem += 1;
}

void Vector::setElement(int i,Object * elem)
{
    /* Modification non valide */
    if ((i<0) || (i>=NbElem))
    {
        printf("Vector::setElement : element inexistant %i\n",i);
        exit(1);
    }
    tElems[i] = elem;
}


void Vector::trimToSize()
{
    if ((NbElem==0) || (NbElem==Size))
        return;
    else
    {
        Object ** temp;
        Size = NbElem;
        temp = new (Object*)[Size];
        for (int j=0;j<NbElem;j++)
            temp[j] = tElems[j];
        delete [] tElems;
        tElems = temp;
    }
}   

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

/* Pareil mais plus facile a appele pour des pointeurs */
Object * Vector::elementAt(int i)
{
    if ((i<0) || (i>=NbElem))
    {
        printf("Vector::elementAt : element inexistant %i\n",i);
        exit(1);
    }
    return tElems[i];
};

void Vector::Print()
{
    printf("[|");
    for (int i=0;i<NbElem;i++)
    {
        tElems[i]->Print();
        printf(" ; ");
    }
    printf("\b|]");
}


// Fusionne 2 partie ordonnée du tableau T
void Fusionne(Object * T[],Object * Dest[],int i1, int j1,int i2,int j2)
{
    int k1 = i1;
    int k2 = i2;
    int k = i1;
    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(Object * T[],Object * Dest[],int i,int j)
{
    if (i<j-1)
    {
        int milieu = (i + j) / 2;
        TriPartition(T,Dest,i,milieu);
        TriPartition(T,Dest,milieu,j);
        Fusionne(T,Dest,i,milieu,milieu,j);
    }
    else
        Dest[i] = T[i];
        
}
        




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

void Vector::deleteAll()
{
    int i;
    for(i=0;i<NbElem;i++)
        delete tElems[i];
    delete [] tElems;
    NbElem = 0;
    Size = 2 ; 
    tElems = new (Object *)[2];
}