/*
 * coeflist(P,T,N) outputs the list of coefficients of terms in polynomial P 
 * with T-degree greater than N.
 */
def coeflist(P,T,N)
{
	L=[];
	D=deg(P,T);
	while(D!=N-1){
		C=coef(P,D,T);
		if(C!=0) L=cons(C,L);
		D=D-1;
	}
	return(reverse(L));
}

/*
 * eliminate_list(PL,VL) outputs the list of new polynomials eliminated 
 * variables VL from the polynomial system PL. 
 */
def eliminate_list(PL,VL){
	T=find_linear(PL,VL);
	CP=T[0];
	PL=T[1];
	CP=subst_tmp(CP,VL);
	return list_subst_list(PL,CP);
}

/*
 * eliminate(PL,V) outputs the list of new polynomials eliminated V
 * from the polynomial system PL. 
 */
def eliminate(PL,V){
	N=coef_1(PL,V);
	if(N==length(PL)) return(-1);/* fail */
	P=PL[N];
	PL=omit_n(PL,N);
	return list_ptozp(list_subst_list(PL,[[V,-(P-1*coef(P,1,V)*V)/coef(P,1,V)]]));
}

/* Find linear polynomials for variables VL */
def find_linear(PL,VL){
	Ex=[];
	while(VL!=[]){
		V=car(VL);
		for(I=0;I<length(PL);I++){
			P=PL[I];
			if(deg(P,V)==1){
				T=P-1*coef(P,1,V)*V;
				if(deg_all0(T,cdr(VL))==1){
				/*	Ex=cons([V,-T/coef(P,1,V)],Ex);*/
					Ex=cons(-T/coef(P,1,V),Ex);
					PL=omit_n(PL,I);
					break;
				}
			}
		}
		VL=cdr(VL);
	}
	return [reverse(Ex),PL];
}

/*
 * Return 1 if polynomial P does not include variables VL,
 * otherwise return 0 
 */
def deg_all0(P,VL){
	while(VL!=[]){
		if(deg(P,car(VL))!=0) return 0;
		VL=cdr(VL);
	}
	return 1;
}

/* auxiliary function for substitution */
def subst_tmp(CP,C){
	R=[car(CP)];L=[[car(C),car(R)]];
	CP=cdr(CP);C=cdr(C);
	while(CP!=[]){
		R=cons(subst_list(car(CP),L),R);
		L=cons([car(C),car(R)],L);
		CP=cdr(CP);C=cdr(C);
	}
	return(reverse(L));
}

/* Omit N-th element from list L */
def omit_n(L,N)
{
	L1=[];
	for(I=0;I<N;I++){
		L1=cons(car(L),L1);
		L=cdr(L);
	}
	return append(reverse(L1),cdr(L));
}

/* Omit elements with the indices list NL from list L */
def omit_nl(L,NL)
{
	I=0;
	while(NL!=[]){
		L=omit_n(L,car(NL)-I);
		NL=cdr(NL);
		I=I+1;
	}
	return(L);
}

/* subst_list(P,[[x,a],[y,b],...]) substitute x=a, y=b,... in polynomial P */
def subst_list(P,L){
	while(L!=[]){
		T=car(L);
		P=subst(P,car(T),car(cdr(T)));
		L=cdr(L);
	}
	return(P);
}

/*
 * list_subst_list(PL,[[x,a],[y,b],...]) substitute x=a, y=b,...
 * in polynomial system PL
 */
def list_subst_list(PL,L){
	R=[];
	while(PL!=[]){
		R=cons(subst_list(car(PL),L),R);
		PL=cdr(PL);
	}
	return(reverse(R));
}

/* Return index of linear polynomial w.r.t X from list L */
def coef_1(L,X){
	N=0;
	while(L!=[]){
		if(deg(car(L),X)==1 && vars(coef(car(L),1,X))==[]) break;
		L=cdr(L);
		N++;
	}
	return(N);
}

/*
 * list_ptozp(PL) converts the list PL of polynomials with rational 
 * coefficients into the list of integral polynomials such that GCD 
 * of all its coefficients is 1.
 */
def list_ptozp(PL){
	R=[];
	while(PL!=[]){
		R=cons(ptozp(car(PL)),R);
		PL=cdr(PL);
	}
	return reverse(R);
}
end$