/*
   $Id: gordan_part00.c,v 1.1.1.2 2003/10/21 22:39:58 nthiery Exp $
   Name:	gordan_part00.cc
   Purpose:	MuPAD dynamic module for ... C part
   Author:	Christophe Carre <Christophe.Carre@dir.univ-rouen.fr>
   Created:	2001/03
   Copyright:	LGPL
*/

/*Trace
*/

#include "gordan00.h"

/*
frees the linked list
*/

void freelst(struct list *plst)
{
        struct list *q;
        while(plst!=NULL)
        {
                free((char *)plst->tab);
                q=plst; plst=plst->next;
                free((char *)q);
        }
}

/*
frees the linked list
*/

void freelstdble(struct listdble *plst)
{
        struct listdble *q;
        while(plst!=NULL)
        {
                free((char *)plst->tab);
                q=plst; plst=plst->next;
                free((char *)q);
        }
}

/*
Visualise un tableau dont la taille est specifiee dans la premiere case
*/

void voirbuf(UENT *buf)
{
  int lg= *buf++, i;
  for(i=0;i<lg;i++)
    printf("%d ",(int)(*buf++));
}

void voirlist(struct list *bp)
{
  while (bp != NULL)
  {
    printf("%ld ( ",bp->cof);
    voirbuf(bp->tab);
    printf(")\n");
    bp = bp->next;
  }
}

void voirlistdble(struct listdble *bp)
{
  while (bp != NULL)
  {
    printf("%ld ( ",bp->cof);
    voirbuf(bp->tab);
    printf(")\n");
    bp = bp->next;
  }
  putchar('\n');
}

/*
Retourne *baf
*/

void rev(UENT *baf){
	UENT *bs= baf+ *baf, tmp;
	signed int i= *baf/2; baf++;
	for(;i>0; i--, bs--, baf++){
		tmp= *bs;
		*bs= *baf;
		*baf=tmp;
	}
}

/*
Les constantes 1 ou 0 representees comme des fonctions de Schur
Alloue une case dans la liste
*/

int case_01(struct list **res, unsigned char  t){
	if(t==1){
		*res=(struct list *) malloc(sizeof(struct list));
		(*res)->cof=1;
		(*res)->tab=(UENT *)calloc(2, sizeof(UENT)); 
		*(*res)->tab=1;
		(*res)->next=NULL;
	}
	else *res=NULL;
	return 0;
}

/*
Les constantes 1 ou 0 representees comme des fonctions de Schur
Alloue une case dans la liste
*/

int case_01dble(struct listdble **res, unsigned char  t){
	if(t==1){
		*res=(struct listdble *) malloc(sizeof(struct listdble));
		(*res)->cof=1;
		(*res)->tab=(UENT *)calloc(2, sizeof(UENT)); 
		*(*res)->tab=1;
		(*res)->next=NULL;
		(*res)->prev=NULL;
	}
	else *res=NULL;
	return 0;
}

/* 
Renvoie la conjuguee d'une partition passee en parametre
Le parametre v est une partition croissante se terminant par 0
dont la premiere case est la longueur de la partition
La conjuguee commence par la longueur. Suit la partition decroissante
EX v= 3 1 3 4 => Retour 4 3 2 2 1 
*/

UENT * cjg2(UENT *v)
{
	UENT *tab,*btab,tp,ttp,lg;
		
	lg= *v;  v+=lg;
	btab=tab=(UENT *)malloc((*v+1)*sizeof(UENT));
	*btab= *v; btab= tab+ *btab;
	tp=1;
	while(tp<lg){
		if(*(v-1) < *v){
			ttp= *v- *(v-1);
			for(; ttp>0; ttp--)
				*btab-- =tp;
		}
		tp++; v--;
	}
	ttp= *v;
	for(; ttp>0; ttp--) *btab-- = tp;
	return tab;
}

/* Conjugue une somme de fonctions de Schur en utilisant la fonction cjg2 */

void cjg2_lst(struct list *bp){
	UENT *btab;
	while(bp!=NULL){
		btab=bp->tab;
		bp->tab=cjg2(bp->tab);
		free((char *)btab);
		bp=bp->next;
	}
}

/* Conjugue une somme de fonctions de Schur en utilisant la fonction cjg2 */

void cjg2_lstdble(struct listdble *bp){
	UENT *btab;
	while(bp!=NULL){
		btab=bp->tab;
		bp->tab=cjg2(bp->tab);
		free((char *)btab);
		bp=bp->next;
	}
}

/* Retourne une somme de fonctions de Schur en utilisant la fonction rev */

void rev_lst(struct list *bp){
	while(bp!=NULL){
		rev(bp->tab);
		bp=bp->next;
	}
}

/* Retourne une somme de fonctions de Schur en utilisant la fonction rev */

void rev_lstdble(struct listdble *bp){
	while(bp!=NULL){
		rev(bp->tab);
		bp=bp->next;
	}
}

/*
Le tableau af est place a droite de *plst. Si la fonction desalloue
une cellule d'adresse *li, *li prend une autre valeur
*/

int versdroite(UENT *af, long int cof, struct listdble** li, struct listdble **plst){
register struct listdble *bp,*bpp;
struct listdble *bc;
register UENT *baf,*btab;
UENT i;

    bpp= *plst;
    bp=bpp->next;
    while(bp!=NULL)
    {
      baf=af;
      btab=bp->tab;
      if(*baf < *btab)
        goto out1;
      if(*baf > *btab)
        goto out2;
      i= *baf; baf++; btab++;
      for(; i>1; i--) 
      {
        if(*baf < *btab)
        goto out1;
        if(*baf > *btab)
          goto out2;
        baf++;btab++;
      }
      goto out3;
  out1:
      bpp=bp;
      bp=bp->next;
    }
  
  /*
  On sort avec bp==NULL ou avant un plus grand element dans la liste
  */  
  out2:
    bc=(struct listdble *)malloc(sizeof(struct listdble));
    bc->cof=cof;
    bc->next=bp; bc->prev=bpp;
    bc->tab=af;
    bpp->next=bc; 
    if (bp!=NULL) bp->prev=bc;
    *plst=bc;
    return 0;

  out3:
    if(cof== -bp->cof){
      bpp->next=bp->next;
      if(bp->next!=NULL) (bp->next)->prev=bpp;
      if(*li==bp) *li=bpp;
      free(bp->tab);
      free((char *)bp); free((char *)af);
      *plst=bpp;
      return 0;
    }
    bp->cof +=cof; free((char *)af);
    *plst=bp;
    return 0;
}

/*
Le tableau af est place a gauche de *plst. Si la fonction desalloue
une cellule d'adresse *li, *li prend une autre valeur
*/

int versgauche(UENT *af, long int cof, struct listdble **li, struct listdble **plst){
register struct listdble *bp,*bpp;
struct listdble *bc;
register UENT *baf,*btab;
UENT i;

    bpp= *plst;
    bp=bpp->prev;
    while(bp!=NULL)
    {
      baf=af;
      btab=bp->tab;
      if(*baf < *btab)
        goto out2;
      if(*baf > *btab)
        goto out1;
      i= *baf; baf++; btab++;
      for(; i>1; i--) 
      {
        if(*baf < *btab)
        goto out2;
        if(*baf > *btab)
          goto out1;
        baf++;btab++;
      }
      goto out3;
  out1:
      bpp=bp;
      bp=bp->prev;
    }
  
  /*
  On ne sort jamais avec bp==NULL
  */  
  out2:
    bc=(struct listdble *)malloc(sizeof(struct listdble));
    bc->cof=cof;
    bc->prev=bp; bc->next=bpp;
    bc->tab=af;
    bpp->prev=bc; 
    if (bp!=NULL) bp->next=bc;
    *plst=bc;
    return 0;

  out3:
    if(cof== -bp->cof){
      bpp->prev=bp->prev;
      if(bp->prev!=NULL) (bp->prev)->next=bpp;
      if(*li==bp) *li=bpp;
      free(bp->tab);
      free((char *)bp); free((char *)af);
      *plst=bpp;
      return 0;
    }
    bp->cof +=cof; free((char *)af);
    *plst=bp;
    return 0;
}

/*
Compare la partition en af avec la partition en *plst->tab
Si af est pour l'ordre lexico < *plst->tab => appel a versdroite
Si af est pour l'ordre lexico > *plst->tab  => appel a versgauche
Sinon af= *plst->tab et selon le coefficient, le traitement est fait
Si la fonction desalloue
une cellule d'adresse *li, *li prend une autre valeur
*/

int ins_lstdble(UENT *af, long int cof, struct listdble **li, struct listdble **plst){
	register struct listdble *bp;
	register UENT *baf,*btab;
	UENT i, boo;

	bp= *plst;
	baf=af;
	btab=bp->tab;
	if(*baf < *btab)
		return (versdroite(af, cof, li, plst));
	if(*baf > *btab)
		return (versgauche(af, cof, li, plst));
	i= *baf; baf++; btab++;
	for(; i>1; i--){
		if(*baf < *btab)
			return(versdroite(af, cof, li, plst));
		if (*baf > *btab)
			return(versgauche(af, cof, li, plst));
		baf++;btab++;
	}
	if (cof== -bp->cof){
		boo=0;
		if(bp->prev!= NULL){
			(bp->prev)->next=bp->next;
      			if(*li==bp) *li=bp->prev;
			*plst= bp->prev; boo=1;
		}
		if(bp->next!=NULL){
			(bp->next)->prev=bp->prev;
			if(boo==0){ *plst= bp->next;
      					if(*li==bp) *li=bp->next;
			 		boo=1;
				}
		}
		free(bp->tab); free((char *)bp); free((char *)af);
		return 0;
	}
	bp->cof += cof; free((char *)af);
	*plst=bp;
	return 0;
}

/*
insere une partition croissante, af, avec son coefficient, coef,
avec son coefficient dans une liste triee, *plst.
L'insertion se fait apres la premiere cellule de *plst.
A la fin *plst est la cellule juste avant la cellule inseree ou supprimee.
*/

int ins_lst(UENT *af,long int coef,struct list **plst)
{
  register struct list *bp,*bpp;
  struct list *bc;
  register UENT *baf,*btab;
  UENT i;

  if(*plst==NULL){
    bp=(struct list *)malloc(sizeof(struct list));
    bp->tab=af;
    bp->cof=coef;
    bp->next=NULL;
    *plst=bp;
  }
  else{
    bpp= *plst;
    bp=bpp->next;
    while(bp!=NULL)
    {
      baf=af;
      btab=bp->tab;
      if(*baf < *btab)
        goto out1;
      if(*baf > *btab)
        goto out2;
      i= *baf; baf++; btab++;
      for(; i>1; i--) 
      {
        if(*baf < *btab)
        goto out1;
        if(*baf > *btab)
          goto out2;
        baf++;btab++;
      }
      goto out3;
  out1:
      bpp=bp;
      bp=bp->next;
    }
  
  /*
  On sort avec bp==NULL ou avant un plus grand element dans la liste
  */  
  out2:
    bc=(struct list *)malloc(sizeof(struct list));
    bc->cof=coef;
    bc->next=bp;
    bc->tab=af;
    bpp->next=bc;
    *plst=bc;
    return 0;
  
  /*
  l'element existe deja dans la liste
  */
  out3:
    if(coef== -bp->cof)
    {
      bpp->next=bp->next;
      free(bp->tab);
      free((char *)bp); free((char *)af); *plst=bpp;
    }
    else{
      bp->cof +=coef; free((char *)af); *plst=bp;
    }
  }
  return 0;
}

int	moteur(UENT *init, UENT *s, UENT *lien, UENT *pos, UENT *w,
		 UENT n, UENT p, UENT lgvn, long int cof, struct list **li)
{
	UENT ind, boo, ggv, tp, ttp, tttp, av, j, i;
	UENT *bs, *blien, *bpos, *tab, *btab, *bu;
	int sig;
	signed char rst;
	struct list *bp;

	ggv=0;
	boo=0;
	
	bpos=pos+p;
	tp= *bpos;
	bs=s+tp+1;	
	ind=p+1;
	bpos=pos+ind;

	while(ind>=1){
		if(ind==p+1){

			boo=0; bpos--; bs--; ind--;
			if(pos[1] <= n && pos[1] >1){
				tttp=s[pos[1]]-pos[1]+1;
				tttp= tttp>s[1]?tttp:s[1];
			}
			else tttp=s[1];

			tab=(UENT *)calloc(tttp+1,sizeof(UENT));
			*tab=tttp;
			bu=w; i= *bu++; btab=tab+tttp-i+1;
			for(; i>0; i--)
				*btab++ =  *bu++;

			bu=pos+1; sig=1;
			for(i=0; i<p; i++, bu++){
				j= *bu;
				btab= tab+tttp-(s[j]-n);
				rst=n;
				while(rst >0){
					av= *btab+1;
					*btab-- =j;
					rst -= j-av+1;
					j=av;
				}
				if((*bu-j) %2 != 0) sig= -sig;
			}
			if(ggv==0)
			{
				ins_lst(tab, sig*cof, li);
				bp= *li;
				ggv=1;
			}
			else
				ins_lst(tab, sig*cof, &bp);

		}/* End of ind==p+1*/
		if(boo==0){
			*bs -=n;
			tp= *bpos+1; bs++;
		}
		if(tp<=lgvn){
			blien=lien+tp;
			while(tp<lgvn){
				ttp= *blien;
				if(ttp>0){
					if(s[ttp] !=init[ttp]) goto enavant;
					tp++; blien++;
				}
				else goto enavant;
			}
			goto enavant;
		}
		else{
			bs -=n;
			for(i=1; i<= n;i++){
				if(*bs){
					goto enavant;
				}
				bs++; tp++;
			}

			ind--; bpos--; boo=0;
			bs=s+ *bpos;
			continue;
		}/*End of else of if(tp<=lgvp)*/
enavant:	*bpos=tp;
		bs=s+tp; *bs+=n;
		boo=1; ind++; bpos++; tp++;
		bs++;
	} /*End of while(ind>=1)*/
	return 0;
}



int	moteurdble(UENT *init, UENT *s, UENT *lien, UENT *pos, UENT *w,
		 UENT n, UENT p, UENT lgvn, long int cof, struct listdble **li)
{
	UENT ind, boo, ggv, tp, ttp, tttp, av, j, i;
	UENT *bs, *blien, *bpos, *tab, *btab, *bu;
	int sig;
	signed char rst;
	struct listdble *bp;

	ggv=0;
	boo=0;
	
	bpos=pos+p;
	tp= *bpos;
	bs=s+tp+1;	
	ind=p+1;
	bpos=pos+ind;

	while(ind>=1){
		if(ind==p+1){

			boo=0; bpos--; bs--; ind--;
			if(pos[1] <= n && pos[1] >1){
				tttp=s[pos[1]]-pos[1]+1;
				tttp= tttp>s[1]?tttp:s[1];
			}
			else tttp=s[1];

			tab=(UENT *)calloc(tttp+1,sizeof(UENT));
			*tab=tttp;
			bu=w; i= *bu++; btab=tab+tttp-i+1;
			for(; i>0; i--)
				*btab++ =  *bu++;

			bu=pos+1; sig=1;

			for(i=0; i<p; i++, bu++){
				j= *bu;
				btab=tab+tttp-(s[j]-n);
				rst=n;
				while(rst >0){
					av= *btab+1;
					*btab-- =j;
					rst -= j-av+1;
					j=av;
				}
				if((*bu-j) %2 != 0) sig= -sig;
			}
			if(ggv==0)
			{
				ins_lstdble(tab, sig*cof, li, li);
				bp= *li;
				ggv=1;
			}
			else
				ins_lstdble(tab, sig*cof, li, &bp);

		}/* End of ind==p+1*/
		if(boo==0){
			*bs -=n;
			tp= *bpos+1; bs++;
		}
		if(tp<=lgvn){
			blien=lien+tp;
			while(tp<lgvn){
				ttp= *blien;
				if(ttp>0){
					if(s[ttp] !=init[ttp]) goto enavant;
					tp++; blien++;
				}
				else goto enavant;
			}
			goto enavant;
		}
		else{
			bs -=n;
			for(i=1; i<= n;i++){
				if(*bs){
					goto enavant;
				}
				bs++; tp++;
			}

			ind--; bpos--; boo=0;
			bs=s+ *bpos;
			continue;
		}/*End of else of if(tp<=lgvp)*/
enavant:	*bpos=tp;
		bs=s+tp; *bs+=n;
		boo=1; ind++; bpos++; tp++;
		bs++;
	} /*End of while(ind>=1)*/
	return 0;
}

int init_gordan(int n, int p, int lgvn, UENT *v, UENT *init, UENT *s, UENT *lien, UENT *pos){
	UENT *bu, *bs, *binit, *blien, *bpos;
	UENT ttp, tttp;
	UENT i, ind;
	UENT lgv;

	bs=s; binit=init;
	bu=v;
	lgv= *bu++;
	if(p>lgv){
		bs++ ;/*CC Ote la longueur de s*/ binit++;
		for(i=0; i<lgv;i++,  bu++, binit++, bs++){
			*bs=  *bu+n;
			*binit= *bu;
		}
		for(;i<p;i++)
			*bs++ =n;
	}
	else{
		bs++;/*CC Ote la longueur de s*/
		binit++;
		for(i=0; i<p; i++, bu++, binit++, bs++){
			*bs = *bu+n; *binit= *bu;
		}
		for(; i<lgv;i++)
			*bs++ =*binit++ =  *bu++;
	}

	binit=init+2; blien=lien+2;
	for(ind=2; ind<=lgvn; ind++){
		bu=binit-1;
		ttp= *binit+n-1; tttp=ind-1;
		while(binit-bu<ind){
			if(*bu==ttp){
				*blien= tttp; break;
			}
			if(*bu>ttp) break;
			ttp--; tttp--; bu--;
		}
		binit++; blien++;
	}

	bpos=pos; bpos++;
	for(i=1; i<=p; i++) *bpos++ =i;
	return 0;
}

/*
	Retourne dans li la decomposition \sum c_I\Lambda_I= \psi_{n n     n} \Lambda_w,
	ou \psi a p parts de valeur n
	les partitions I ont leur plus grande part inferieure a lg_prt.
	p doit etre positif
	Exemple: gordan_lim(3, 2, [1,3], 1, 2, li); 
	retourne dans li la somme \sum c_I\Lambda_I=\psi_{3,3} \Lambda_{3,1}
*/

void gordan_lim(UENT n,UENT p, UENT *w,
long int cof, UENT lim, struct list **li){
	UENT *init, *s, *pos, *lien, *v, *tab;
	UENT *bu, *bs, *blien, *bpos, *btab;
	UENT lgv, lgvn, lgvn_lim;
	UENT tp, ttp, tttp;
	UENT i, ind, j, rst, av, gv;
	UENT boo;
	signed char sig;
	struct list *bp= *li;

	v=cjg2(w); /*ou cjg */
	gv=0;
	bu=v;
	lgv= *bu++;
	lgvn=lgv+n;
	lgvn_lim=lim>=lgvn?lgvn-1:lim;
	
	init=(UENT *)calloc(lgvn_lim+1, sizeof(UENT));
	tp=lgv+n*p+1;
	tp=(tp>lim+1)? lim+1:tp;
	s=(UENT *)calloc(tp, sizeof(UENT));
	lien=(UENT *)calloc(lgvn_lim+1, sizeof(UENT));
	pos=(UENT *) malloc((p+1)*sizeof(UENT));
	init_gordan(n, p, lgvn_lim,  v, init, s, lien, pos);

	ind=p+1;
	bpos=pos+ind;
	bs=s+ind;
	while(ind>=1){
		if(ind==p+1){
			boo=0; bpos--; bs--; ind--;

			if(pos[1] <= n && pos[1] >1){
				tttp=s[pos[1]]-pos[1]+1;
				tttp= tttp>s[1]?tttp:s[1];
			}
			else tttp=s[1];

			tab=(UENT *)calloc((tttp+1),sizeof(UENT));
			*tab=tttp;

			bu=w; i= *bu++; btab=tab+tttp-i+1;
			for(; i>0; i--)
				*btab++ =  *bu++;

			bu=pos+1; sig=1;

			for(i=0; i<p; i++, bu++){
				j= *bu;
				btab=tab+tttp-(s[j]-n);
				rst=n;
				while(rst >0){
					av= *btab+1;
					*btab-- =j;
					rst -= j-av+1;
					j=av;
				}
				if((*bu-j) %2 != 0) sig= -sig;
			}
			if(gv==0)
			{
				ins_lst(tab, sig*cof, li);
				bp= *li;
				gv=1;
			}
			else
				ins_lst(tab, sig*cof, &bp);

		}/* End of ind==p+1*/

		if(boo==0){
			*bs -=n;
			tp= *bpos+1; bs++;
		}
		if(lim<lgvn){
			blien=lien+tp;
			while(tp<=lim){
				ttp= *blien;
				if(ttp>0){
					if(s[ttp] !=init[ttp]) goto enavant;
					tp++; blien++;
				}
				else goto enavant;
			}
			ind--; bpos--; boo=0;
			bs=s+ *bpos;
			continue;
		}
		if(tp<=lgvn){
			blien=lien+tp;
			while(tp<lgvn){
				ttp= *blien;
				if(ttp>0){
					if(s[ttp] !=init[ttp]) goto enavant;
					tp++; blien++;
				}
				else goto enavant;
			}
			goto enavant;
		}
		else{
			bs -=n;
			if(tp+n<=lim){
				for(i=1; i<= n;i++){
					if(*bs){
						goto enavant;
					}
					bs++; tp++;
				}
			}
			else{
				while(tp<=lim){
					if(*bs) goto enavant;
					bs++;tp++;
				}
			}

			ind--; bpos--; boo=0;
			bs=s+ *bpos;
			continue;
		}/*End of else of if(tp<=lgvp)*/

enavant:	*bpos=tp;
		bs=s+tp; *bs+=n;
		boo=1; ind++; bpos++; tp++;
		bs++;
	}

/*
	voirbuf(init);
putchar('\n'); voirbuf(s); putchar('\n');
	voirbuf(lien); putchar('\n');
*/
	free(init); free(s); free(lien); free(pos); free(v);
}


/*
	Retourne dans li la decomposition \sum c_I\Lambda_I= \psi_{n n     n} \Lambda_w,
	ou \psi a p parts de valeur n
	Exemple: gordan(3, 2, [1,3], 1, li); 
	retourne dans li la somme \sum c_I\Lambda_I=\psi_{3,3} \Lambda_{3,1}
*/

int gordan(UENT n,UENT p, UENT *w, long int cof, struct list **li){
	UENT *init, *s, *pos, *lien,  *v;
	UENT *bu;
	UENT lgv, lgvn;

	v=cjg2(w);
	
	bu=v;
	lgv= *bu++;
	lgvn=lgv+n;
	init=(UENT *)calloc(lgvn,sizeof(UENT));
	s=(UENT *)calloc(lgv+n*p+1,sizeof(UENT));
	lien=(UENT *)calloc(lgvn,sizeof(UENT));
	pos=(UENT *) malloc((p+1)*sizeof(UENT));
	
	init_gordan(n, p, lgvn-1, v, init, s, lien, pos);

	moteur(init, s, lien, pos, w, n, p, lgvn, cof, li);
	free(init); free(s); free(lien); free(pos); free(v);
	return 0;
}

/*
	Retourne dans li la decomposition \sum c_I\Lambda_I= \psi_{n n     n} \Lambda_w,
	ou \psi a p parts de valeur n
	les partitions I sont de longueur inferieure a lg_prt.
	Exemple: gordan_part(3, 2, [1,3], 1, 2, li); 
	retourne dans li la somme \sum c_I\Lambda_I=\psi_{3,3} \Lambda_{3,1}
*/

int gordan_part(UENT n,UENT p, UENT *w, long int cof, UENT lg_prt, struct listdble **li){
	UENT *init, *s, *pos, *lien, *v;
	UENT *bu, *bs, *binit, *blien, *bpos;
	UENT lgv, lgvn;
	UENT tp, ttp, tttp;
	UENT i, ind;

	v=cjg2(w);
	bu=v;
	lgv= *bu++;
	lgvn=lgv+n;
	init=(UENT *)calloc(lgvn,sizeof(UENT));
	s=(UENT *)calloc(lgv+n*p+1,sizeof(UENT));
	bs=s+1; binit=init+1;

	for(i=0; i<lgv; i++, binit++, bu++) *binit= *bu;

	lien=(UENT *)calloc(lgvn,sizeof(UENT));
	binit=init+2; blien=lien+2;
	for(ind=2; ind<lgvn; ind++){
		bu=binit-1;
		ttp= *binit+n-1; tttp=ind-1;
		while(binit-bu<ind){
			if(*bu==ttp){
				*blien= tttp; break;
			}
			if(*bu>ttp) break;
			ttp--; tttp--; bu--;
		}
		binit++; blien++;
	}

	pos=(UENT *) malloc((p+1)*sizeof(UENT));
	bpos=pos; bpos++; binit=init+1;
	if(*binit+n<= lg_prt){
		if(p<lgv){
			for(i=1; i<=p; i++, bs++, bpos++, binit++){
				*bpos =i;
				*bs = *binit+n;
			}
			for(;i<=lgv; i++, bs++, binit++) *bs= *binit;
		}
		else{
			for(i=1; i<=lgv; i++, bs++, bpos++, binit++){
				*bpos =i;
				*bs = *binit+n;
			}
			for(; i<=p; i++, bs++, bpos++){
				*bpos =i;
				*bs =n;
			}
		}
	}
	else{
		*bs++= *binit++; blien= lien+2;
		for(i=2; i< lgvn; i++, bs++, binit++, blien++){
			if( *binit+n+1 <= lg_prt+i){
				ttp= *blien;
				if(ttp>1){
					if(s[ttp]!=init[ttp]){
						*bs= *binit +n;
						*bpos++=i;
						if(bpos - pos == p+1) break;
					}
					else *bs= *binit;
				}
				else {
					if(ttp==1) *bs=*binit;
					else{
					*bs= *binit +n;
					*bpos++=i;
					if(bpos - pos == p+1) break;
					}
				}
			}
			else *bs= *binit;
		}
		if(bpos-pos != p+1){
			tp=p-(bpos-pos-1);
			while(1){
				if(*(bs-n)|| bs-s == n){
					*bs=n;
					tp--; *bpos=i;
					bpos++;
					if(tp==0) break;
				}
				i++; bs++;
			}
		}
		else{
			i++; bs++, binit++;
			for(;i<=lgv;i++, bs++, binit++) *bs= *binit;
		}
	}

	moteurdble(init, s, lien, pos, w, n, p, lgvn, cof, li);

	free(init); free(s); free(lien); free(pos); free(v);
	return 0;
}

/*
	Retourne dans li la
	decomposition \sum C_I \Lambda_I 
	du produit  de \psi_{n n     n} par \sum C_I \Lambda_I
	ou \sum C_I \Lambda_I est le contenu de  dep
	\psi a p parts de valeur n
*/


int gordan_lst(UENT n, UENT p, struct list *dep, signed char boo, UENT mx,   struct list *li){

	while( dep!=NULL){
		if(boo==1){
			if (mx==0)  gordan(n, p, dep->tab, dep->cof, &li);
			else  gordan_lim(n, p, dep->tab, dep->cof, mx, &li);
		}
		else{
			if (mx==0) gordan(n, p, dep->tab, -dep->cof, &li);
			else gordan_lim(n, p, dep->tab, -dep->cof, mx, &li);
		}
		dep= dep->next;
	}
	return 0;
}

/*
Si cond=1, calcule dans res la decomposition \sum C_I\Lambda_I =\Lambda_n(\Lambda_p)
Si cond=0, calcule dans res la decomposition \sum C_I\Lambda_I =S_n(\Lambda_p)
Si mx=0, pas de limite sur les longueurs ou sur la plus grande part de I
Si mx<>0, limite sur les parts de I: I_j <= mx
*/

int plet( UENT n, UENT p, signed char cond,  UENT mx, struct list **res){
	struct list **newton, **bb, *bp;
	UENT *btab;
	UENT i,j;
	signed char sig;

	newton=(struct list **)malloc(sizeof(struct list *)*(n+1));
	bb=newton;
	for(i=0;i<=n;i++){
		*bb=(struct list *)malloc(sizeof(struct list ));
		(*bb)->tab=(UENT *)malloc(sizeof(UENT));
		if(sizeof(UENT)==sizeof(unsigned char)) *((*bb)->tab)= UCHAR_MAX;
		else if (sizeof(UENT)==sizeof(unsigned int)) *((*bb)->tab)= UINT_MAX;
		(*bb)->next=NULL;
		bb++;
	}

	bb=newton;
	bp=(struct list *)malloc(sizeof(struct list));
	bp->cof=1;
	bp->tab=(UENT *)calloc(1,sizeof(UENT));
	bp->next=NULL;
	(*bb)->next=bp; bb++;

	bp=(struct list *)malloc(sizeof(struct list));
	bp->cof=1;
	btab=(UENT *)malloc(2*sizeof(UENT));
	bp->tab=btab;
	*btab++ =1; *btab=p;
	bp->next=NULL;
	(*bb)->next=bp; bb++;

	if(cond==0){
		for(i=2;i<=n; i++){
			for(j=i; j>0; j--){
				gordan_lst(j,p,(*(newton+i-j))->next,1, mx, *bb);
			}
			bp= (*bb)->next;
			while(bp!=NULL){
				bp->cof /= i; bp=bp->next;
			}
			bb++;
		}
	}
	
	else{
		for(i=2;i<=n; i++){
			if(i%2==0) sig= -1; else sig=1;
			for(j=i; j>0; j--){
				gordan_lst(j,p,(*(newton+i-j))->next,sig , mx, *bb);
				sig= -sig;
			}
			bp= (*bb)->next;
			while(bp!=NULL){
				bp->cof /= i; bp=bp->next;
			}
			bb++;
		}
	}

	*res= (*(newton+n))->next;
	bb=newton+n;
	(*bb)->next=NULL;
	freelst(*bb);
	bb=newton;
	for(i=0; i<n; i++, bb++)
		freelst(*bb);

	free(newton);
	return 0;
}

/*
	Retourne dans li la
	decomposition \sum C_I \Lambda_I 
	du produit  de \psi_{n n     n} par \sum C_I \Lambda_I
	ou \sum C_I \Lambda_I est le contenu de  dep
	\psi a p parts de valeur n
	La longueur des partitions I de dep et li est <=mx.
*/

int gordan_lstdble(UENT n, UENT p, struct listdble *dep, signed char boo, UENT mx,   struct listdble *li){
	while( dep!=NULL){
		if(boo==1) gordan_part(n, p, dep->tab, dep->cof, mx, &li);
		else gordan_part(n, p, dep->tab, -dep->cof, mx, &li);
		dep= dep->next;
	}
	
	return 0;
}

/*
Si cond=1, calcule dans res la decomposition \sum C_I\Lambda_I =\Lambda_n(\Lambda_p)
Si cond=0, calcule dans res la decomposition \sum C_I\Lambda_I =S_n(\Lambda_p)
Limite sur les longueurs de I: l(I) <= mx
*/

int pletdble( UENT n, UENT p, signed char cond, UENT mx, struct listdble **res){
	struct listdble **newton, **bb, *bp;
	UENT *btab;
	UENT i,j;
	signed char sig;

	newton=(struct listdble **)malloc(sizeof(struct listdble *)*(n+1));
	bb=newton;
	for(i=0;i<=n;i++){
		*bb=(struct listdble *)malloc(sizeof(struct listdble ));
		(*bb)->tab=(UENT *)malloc(sizeof(UENT));
		if(sizeof(UENT)==sizeof(unsigned char)) *((*bb)->tab)= UCHAR_MAX;
		else if (sizeof(UENT)==sizeof(unsigned int)) *((*bb)->tab)= UINT_MAX;
		(*bb)->next=NULL; (*bb)->prev= NULL;
		bb++;
	}
	bb=newton;
	bp=(struct listdble *)malloc(sizeof(struct listdble));
	bp->cof=1;
	bp->tab=(UENT *)calloc(1,sizeof(UENT));
	bp->next=NULL; bp->prev= *bb;
	(*bb)->next=bp; bb++;

	bp=(struct listdble *)malloc(sizeof(struct listdble));
	bp->cof=1;
	btab=(UENT *)malloc(2*sizeof(UENT));
	bp->tab=btab;
	*btab++ =1; *btab=p;
	bp->next=NULL; bp->prev= *bb;
	(*bb)->next=bp; bb++;

	if(cond==0){
		for(i=2;i<=n; i++){
			for(j=i; j>0; j--){
				gordan_lstdble(j,p,(*(newton+i-j))->next,1, mx, *bb);
			}
			bp= (*bb)->next;
			while(bp!=NULL){
				bp->cof /= i; bp=bp->next;
			}
			bb++;
		}
	}
	
	else{
		for(i=2;i<=n; i++){
			if(i%2==0) sig= -1; else sig=1;
			for(j=i; j>0; j--){
				gordan_lstdble(j,p,(*(newton+i-j))->next,sig , mx, *bb);
				sig= -sig;
			}
			bp= (*bb)->next;
			while(bp!=NULL){
				bp->cof /= i; bp=bp->next;
			}
			bb++;
		}
	}

	*res= (*(newton+n))->next;
	bb=newton+n;
	(*bb)->next=NULL;
	freelstdble(*bb);
	bb=newton;
	for(i=0; i<n; i++, bb++)
		freelstdble(*bb);

	free(newton);
	return 0;
}

/*
Calcule dans res la decomposition \sum C_I s_I= sn(sm)
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n et m doivent etre positifs.
*/

int snsm(UENT n, UENT m,struct list **res){
	if(n==0){
		case_01(res, 1); return 1;
	}
	if(m==0){
		case_01(res, 0); return 0;
	}
	if(m%2!=0)
		plet(n,m,1,0,res);
	else
		plet(n,m,0,0,res);
	rev_lst(*res);
	return 2;
}


/*
Calcule dans res la decomposition \sum C_I s_I= ln(sm)
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n et m doivent etre positifs.
*/

int lnsm(UENT n, UENT m, struct list **res){
	if(n==0){
		case_01(res, 1); return 1;
	}
	if(m==0){
		case_01(res, 0); return 0;
	}
	if(m%2!=0)
		plet(n,m,0,0,res);
	else
		plet(n,m,1,0,res);
	rev_lst(*res);
	return 2;
}

/*
Calcule dans res la decomposition \sum C_I s_I= sn(lm)
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n et m doivent etre positifs.
*/

int snlm(UENT n, UENT m,struct list **res){
	if(n==0){
		case_01(res, 1); return 1;
	}
	if(m==0){
		case_01(res, 0); return 0;
	}
	plet(n,m,0,0,res);
	cjg2_lst(*res);
	return 2;
}

/*
Calcule dans res la decomposition \sum C_I s_I= ln(lm)
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n et m doivent etre positifs.
*/

int lnlm(UENT n, UENT m, struct list **res){
	if(n==0){
		case_01(res, 1); return 1;
	}
	if(m==0){
		case_01(res, 0); return 0;
	}
	plet(n,m,1,0,res);
	cjg2_lst(*res);
	return 2;
}

/*
Calcule dans res la restriction de la decomposition \sum C_I s_I= sn(sm)
aux partitions I ayant la plus grande part  <= lim 
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n, m et lim doivent etre positifs.
*/

int snsm_part(UENT n, UENT m, UENT lim, struct list **res){
	if(n==0){
		case_01(res, 1); return 1;
	}
	if(m==0 || lim<m){
		case_01(res, 0); return 0;
	}
	if(m%2!=0)
		plet(n,m,1,lim,res);
	else
		plet(n,m,0,lim,res);
	rev_lst(*res);
	return 2;
}


/*
Calcule dans res la restriction de la decomposition \sum C_I s_I= ln(sm)
aux partitions I ayant la plus grande part  <= lim 
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n, m et lim doivent etre positifs.
*/

int lnsm_part(UENT n, UENT m, UENT lim, struct list **res){
	if(n==0){
		case_01(res, 1); return 1;
	}
	if(m==0||lim<m){
		case_01(res, 0); return 0;
	}
	if(m%2!=0)
		plet(n,m,0,lim,res);
	else
		plet(n,m,1,lim,res);
	rev_lst(*res);
	return 2;
}

/*
Calcule dans res la restriction de la decomposition \sum C_I s_I= sn(lm)
aux partitions I de longueur <= lim
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n, m et lim doivent etre positifs.
*/

int snlm_lim(UENT n, UENT m, UENT lim, struct list **res){
	if(n==0){
		case_01(res, 1); return 1;
	}
	if(m==0 || lim<m ){
		case_01(res, 0); return 0;
	}
	plet(n,m,0,lim,res);
	cjg2_lst(*res);
	return 2;
}

/*
Calcule dans res la restriction de la decomposition \sum C_I s_I= ln(lm)
aux partitions I de longueur <= lim
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n, m et lim doivent etre positifs.
*/

int lnlm_lim(UENT n, UENT m, UENT lim,  struct list **res){
	if(n==0){
		case_01(res, 1); return 1;
	}
	if(m==0 || lim< m){
		case_01(res, 0); return 0;
	}
	plet(n,m,1,lim ,res);
	cjg2_lst(*res);
	return 2;
}

/*
Calcule dans res la restriction de la decomposition \sum C_I s_I= sn(sm)
aux partitions I de longueur  <= lim 
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n, m et lim doivent etre positifs.
*/

int snsm_lim(UENT n, UENT m, UENT lim, struct listdble **res){
	if(n==0){
		case_01dble(res, 1); return 1;
	}
	if(m==0 || lim==0){
		case_01dble(res, 0); return 0;
	}
	if(m%2!=0)
		pletdble(n,m,1,lim,res);
	else
		pletdble(n,m,0,lim,res);
	rev_lstdble(*res);
	return 2;
}


/*
Calcule dans res la restriction de la decomposition \sum C_I s_I= ln(sm)
aux partitions I de longueur  <= lim 
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n, m et lim doivent etre positifs.
*/

int lnsm_lim(UENT n, UENT m, UENT lim, struct listdble **res){
	if(n==0){
		case_01dble(res, 1); return 1;
	}
	if(m==0||lim==0){
		case_01dble(res, 0); return 0;
	}
	if(m%2!=0)
		pletdble(n,m,0, lim,res);
	else
		pletdble(n,m,1,lim,res);
	rev_lstdble(*res);
	return 2;
}

/*
Calcule dans res la restriction de la decomposition \sum C_I s_I= sn(lm)
aux partitions I ayant la plus grande part  <= lim 
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n, m et lim doivent etre positifs.
*/

int snlm_part(UENT n, UENT m, UENT lim, struct listdble **res){
	if(n==0){
		case_01dble(res, 1); return 1;
	}
	if(m==0 || lim==0){
		case_01dble(res, 0); return 0;
	}
	pletdble(n,m,0, lim,res);
	cjg2_lstdble(*res);
	return 2;
}

/*
Calcule dans res la restriction de la decomposition \sum C_I s_I= ln(lm)
aux partitions I ayant la plus grande part  <= lim 
Retourne 0 si c'est 0
1 si c'est 1,
2 autrement.
n, m et lim doivent etre positifs.
*/

int lnlm_part(UENT n, UENT m, UENT lim,  struct listdble **res){
	if(n==0){
		case_01dble(res, 1); return 1;
	}
	if(m==0 || lim==0){
		case_01dble(res, 0); return 0;
	}
	pletdble(n,m,1,lim ,res);
	cjg2_lstdble(*res);
	return 2;
}

int test(int (*f)(UENT, UENT, struct list **)){
	struct list *res;
	UENT n,p;
	int c;

	scanf("%d",&c);
	p=c;
	scanf("%d",&c);
	n=c;

	f(p,n,&res);	
	voirlist(res);
	freelst(res);
	putchar('\n');
	return 0;
}

int test_lim(int (*f)(UENT, UENT, UENT,  struct list **)){
	struct list *res;
	UENT n,p, lim;
	int c;

	scanf("%d",&c);
	p=c;
	scanf("%d",&c);
	n=c;
	scanf("%d",&c);
	lim=c;

	f(p,n,lim,&res);	
	voirlist(res);
	freelst(res);
	putchar('\n');
	return 0;
}


int test_lm(int (*f)(UENT, UENT, UENT, struct listdble **)){
	struct listdble *res;
	UENT n,p, lim;
	int c;

	scanf("%d",&c);
	p=c;
	scanf("%d",&c);
	n=c;
	scanf("%d",&c);
	lim=c;

	f(p,n,lim,&res);	
	voirlistdble(res);
	freelstdble(res);
	putchar('\n');
	return 0;
}

int test1(){
	printf("Entrer 2 entiers n et m. Sn(Sm) sera calcule\n");
	return (test(snsm));
}

int test2(){
	printf("Entrer 2 entiers n et m. Ln(Sm) sera calcule\n");
	return (test(lnsm));
}

int test3(){
	printf("Entrer 2 entiers n et m. Sn(Lm) sera calcule\n");
	return (test(snlm));
}

int test4(){
	printf("Entrer 2 entiers n et m. Ln(Lm) sera calcule\n");
	return (test(lnlm));
}

int test5(){
	printf("Entrer 3 entiers n, m et lim. Sn(Sm) sera calcule "
"pour les partitions aux parts <= lim\n");
	 return (test_lim(snsm_part));
}

int test6(){
	printf("Entrer 3 entiers n, m et lim. Ln(Sm) sera calcule "
"pour les partitions aux parts <= lim\n");
	 return (test_lim(lnsm_part));
}

int test7(){
	printf("Entrer 3 entiers n, m et lim. Sn(Lm) sera calcule "
"pour les partitions de longueur <= lim\n");
	 return (test_lim(snlm_lim));
}

int test8(){
	printf("Entrer 3 entiers n, m et lim. Ln(Lm) sera calcule "
"pour les partitions de longueur <= lim\n");
	 return (test_lim(lnlm_lim));
}

int test9(){
	printf("Entrer 3 entiers n, m et lim. Sn(Sm) sera calcule "
"pour les partitions de longueur <= lim\n");
	 return (test_lm(snsm_lim));
}

int test10(){
	printf("Entrer 3 entiers n, m et lim. Ln(Sm) sera calcule "
"pour les partitions de longueur <= lim\n");
	 return (test_lm(lnsm_lim));
}

int test11(){
	printf("Entrer 3 entiers n, m et lim. Sn(Lm) sera calcule "
"pour les partitions aux parts <= lim\n");
	 return (test_lm(snlm_part));
}

int test12(){
	printf("Entrer 3 entiers n, m et lim. Ln(Lm) sera calcule "
"pour les partitions aux parts <= lim\n");
	 return (test_lm(lnlm_part));
}

int mode(int i){
	if(i==0){
		printf("\n\n\nTaper un nombre\n");
		printf("	1		=>		Sn(Sm)\n"
			"	2		=>		Ln(Sm)\n"	
			"	3		=>		Sn(Lm)\n"	
			"	4		=>		Ln(Lm)\n"	
			"	5		=>		Sn(Sm) + Restriction sur les parts\n"	
			"	6		=>		Ln(Sm) + Restriction sur les parts\n"	
			"	7		=>		Sn(Lm) + Rstr sur la lg des partitions\n"	
			"	8		=>		Ln(Lm) + Rstr sur la lg des partitions\n"
			"	9		=>		Sn(Sm) + Restriction sur la lg des partitions\n"	
			"	10		=>		Ln(Sm) + Restriction sur la lg des partitions\n"	
			"	11		=>		Sn(Lm) + Rstr sur les parts\n"	
			"	12		=>		Ln(Lm) + Rstr sur les parts\n"
			"	 -1 pour arreter le programme\n"	);
	}
	else{
		printf("Taper comme precedemment le service puis les arguments, -1 pour arreter\n");
	}
 	return 0;
}

int main(){
 	int n, i;

	i=0;
	while(1){
		mode(i); i++;
		scanf("%d",&n);
		switch(n){
			case 1: test1(); break;
			case 2: test2(); break;
			case 3: test3(); break;
			case 4: test4(); break;
			case 5: test5(); break;
			case 6: test6(); break;
			case 7: test7(); break;
			case 8: test8(); break;
			case 9: test9(); break;
			case 10: test10(); break;
			case 11: test11(); break;
			case 12: test12(); break;
			default : return 0;
		}
	}
	return 0;
}
