/******************************************
*
* 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();
}
}
*/