#include "Ens32.h"
#include "Err.h"
#include "Pile.h"
#include "Commun.h"

void Pile::Qsort(){qsort(o, n, sizeof(Ens32), Pile::Cmp);}
void * Pile::Bsearch(const void* cl){return bsearch(cl,o,n,sizeof(Ens32),Pile::Cmp);}

Pile::Pile(const Pile & A){
	t = A.n + 2;
	n = A.n;
	o = Mem::Malloc(t);
	memcpy(o,A.o,sizeof(int[n]));
}
void Pile::Rand(int N){
	if (N>t){
		if (o) Mem::Free(o,t);
		t=N+2;
		o=Mem::Malloc(t);
	}
	n=N;
	int* o2=o+n;
	for(int*o1=o; o1<o2; o1++) *o1=lrand();
}
void Pile::Rand(){
	int*o2=o+n;
	for(int *o1=o;o1<o2;o1++) *o1=lrand();
}
void Pile::Muer(int t2){
	if (o) o=Mem::Realloc(o,t,t2); else o=Mem::Malloc(t2);
	t=t2;
	if (n>t) n=t;
}
ostream & Pile::put(ostream & f){
	int i=0;
	f<<"(";
	while (i<n-1) f<<o[i++]<<" ";
	if (i<n) f<<o[i];
	f<<")";
	return f;
}
istream & Pile::get(istream & f){
	int i;
	char c;

	n=0;
	f.get(c);while (c==' ') f.get(c);
	if (c!='(') Err::MI("Pile::get","Il manque le caractère '('");

	c=f.peek(); 
	while (c==' ') {f.get(c); c=f.peek();}
	while (c!=')'){	if (c==','){f.get(c);c=f.peek();while (c==' ') {f.get(c); c=f.peek();}}
		f>>i;
		Empile(i);
		c=f.peek(); while (c==' ') {f.get(c); c=f.peek();}
	}
return f;
} 
Pile & Pile::operator=(const Pile & B)
{	n=B.n;
	if (n>t)
	{	int y=n+2;
		int*a=Mem::Malloc(y);
		if (o) Mem::Free(o,t);
		t=y;
		o=a;
	}
	memcpy(o,B.o,sizeof(int[n]));
	return (Pile &)B;
}

bool Pile::operator==(const Pile & A)
{	int i;
	int*a1;
	int*o1;
	if (n==A.n)
	{	a1=A.o;
		o1=o;
		for(i=0;i<n;i++) if(!(*(o1++)==*(a1++)))return false;
		return true;
	}
	else return false;
}
void Pile::Empile(int x) 		// Empile l'entier x dans la pile.
{   if (n==t) Muer(t+5);
	o[n++]=x;
}
int Pile::Depile()              // Dépile un entier x dans la table P.
{	if (n) return o[--n]; 
	else Err::MI("Pile::Depile","Pile vide");
	return -1;
}
int Pile::Index(int x) 			// Retourne l'index de l'objet x dans la table P, ou -1 si absent.
{   for(int i=n-1;i>=0;i--) if (o[i]==x) return i;
	return -1;
}
void Pile::Supp(int x)			// Supprime une occurence de l'entier x de la pile.
{   int i=Index(x);
	if (i!=-1)if(i<n)memmove(o+i,o+i+1,sizeof(int[n-i-1]));
	if (i!=-1)n--;
}
void Pile::TriA()
{   Pile P1(n+2);
	// Trier e (n=nombre d'élément), avec un tableau ressource réservé v de n éléments.

if (n > 1)
{
int *v,*u,*w,*e;

register int *e1,*e2,*ef,*v1,*v2,*u1,*u2,*uf,*A1,*A2,*B1,*B2;
register int x1,x2,N;

e=o;
N=n;

v = P1.o;

e1=e;
e2=e+1;
ef=e+N;
v1=v;
v2=v+1;
while(e2<ef)
{   if (*e2<*e1){*v1=*e2;*v2=*e1;} else {*v1=*e1;*v2=*e2;}
    e1+=2;
    e2+=2;
    v1+=2;
    v2+=2;
}
if (e1<ef) *v1=*e1;
u=e;
x1=2;
x2=4;
while (x1<N)
{
    w=v;v=u;u=w;
    A1=u;
    B1=u+x1;
    A2=u+x1;
    B2=u+x2;
    uf=u+N;
    v1=v;
    while (B2<uf)
    {   u1=A1;
        u2=A2;
        while(u1<B1 && u2<B2) if (*u2<*u1) *v1++=*u2++; else *v1++=*u1++;
        while(u1<B1)*v1++=*u1++;
        while(u2<B2)*v1++=*u2++;
        A1+=x2;
        A2+=x2;
        B1+=x2;
        B2+=x2;
    }
    if (A2<uf)
    {   u1=A1;
        u2=A2;
        while(u1<B1 && u2<uf) if (*u2<*u1) *v1++=*u2++; else *v1++=*u1++;
        while(u1<B1)*v1++=*u1++;
        while(u2<uf)*v1++=*u2++;
        A1+=x2;
        A2+=x2;
        B1+=x2;
        B2+=x2;
    }
    u1=A1; while(u1<uf) *v1++=*u1++;
    x1*=2;
    x2*=2;
}
if (e!=v) {e1=e;v1=v;while(e1<ef)*e1++=*v1++;}
}
}
void Pile::SuppDoublon()
// Supprime les doublons dans une liste triée e (n=nombre d'élément).
{
if (n > 1)
{
register int *e1,*e2,*ef,*v1,ee;

e1=o;
ef=e1+n;
v1=e1+1;
e2=e1+1;

while (e2<ef)
{   ee=*e1;
    while(ee==*e2 && e2<ef) e2++;
    e1=e2;
    if(e2<ef) *v1++=*e2++;
}

n=((int) v1 - (int) (o))/sizeof(int);
}
}
void Pile::SuppPaire()
// Supprime les paires d'éléments égaux dans une liste triée e (n=nombre d'élément).
{
if (n > 1)
{
register int *e1,*e2,*ef,*v1;

e1=o;
ef=e1+n;
e2=e1+1;
v1=e1;

while (e2<ef)
{   if (*e1==*e2) {e1+=2;e2+=2;}
    else {*v1++=*e1++;e2++;}
}
if(e1<ef) *v1++=*e1;

n =((int)v1 - (int)(o))/sizeof(int);
}
}
void Pile::TriAD()
{
TriA();
SuppDoublon();
}
void Pile::TriAP()
{
TriA();
SuppPaire();
}