////////////////////////////////////////////////////////////////////////
// Algorithmische Algebra 2, Übungsblatt 1 - SS2003
// Aufgabe 3
// Implementierung von 2 Varianten des Buchberger-Algorithmus
// Thomas Bayer


ring R = 0,(x,y,z),lp;

ideal I = x2y2 + z, xy2 - y, x2y + yz;

proc myBuchberger2(ideal F)
{
	int i, j, k, s, t, count;
	list B, pair;
	ideal G;
	poly S;

	s = size(F);
	B = Pairs(s);
	G = F;
	t = s;

	count = 0;	

	while(size(B) > 0) {
		pair = B[1]; 
		i = pair[1]; 
		j = pair[2];
		count++;
		S = reduce(spoly(G[i], G[j]), G); print(S);
		if(S != 0) {
		     t = t + 1;
		     G = G, S;
		     for(k = 1; k <= t - 1; k++) {B = insert(B, list(k,t), size(B));} 
		}
		B = delete(B,1);
	}
	print(string(count) + " Reduktionen");
	return(G);
}

proc myBuchberger3(ideal F)
{
	int i, j, k, s, t, count;
	intvec LTf, LTg;
	list B, pair;
	ideal G;
	poly S;

	s = size(F);
	B = Pairs(s);
	G = F;
	t = s;

	count = 0;	

	while(size(B) > 0) {
		pair = B[1]; 
		i = pair[1]; 
		j = pair[2];
		LTf = leadexp(G[i]);
		LTg = leadexp(G[j]);
		if(LCM(LTf, LTg) != LTf + LTg) {
		    count++;
		    S = reduce(spoly(G[i], G[j]), G); print(S);
		    if(S != 0) {
			 t = t + 1;
			 G = G, S;
			 for(k = 1; k <= t - 1; k++) {B = insert(B, list(k,t), size(B));} 
		    }
		}
		B = delete(B,1);
	}
	print(string(count) + " Reduktionen");
	return(G);
}

proc Pairs(int s)
{
	int i, j, c;
	list B;

	int c = 1;
	for(j = 2; j <= s; j++) { 
		for(i = 1; i < j; i++) {
		      B[c] = list(i,j); c = c + 1;
		}
	}
	return(B);
}

proc LCM(intvec a, intvec b)
{
	int i;
	intvec cm;
	
	for(i = 1; i <= size(a); i++) { cm[i] = Max(list(a[i], b[i])); }
	return(cm);
}

proc spoly(poly f, poly g)
{
	intvec LTf, LTg, cm;
	poly sp;

	LTf = leadexp(f);
	LTg = leadexp(g);
	cm = LCM(leadexp(f),leadexp(g));
	print(LTf);

	sp = Monomial(cm - LTf) * f - Monomial(cm - LTg) * g;
	return(sp);
}

proc Max(data)
// Type : int
// Purpose : Maximal integer of data
{
        int i;
        int max = data[1];

        for(i = 1; i <= size(data); i = i + 1) {
                if(data[i] > max) { max = data[i]; }
        }
        return(max);
}

proc Monomial(intvec d)
// list of indices
{
        poly f = 1;

        for(int i = 1; i <= size(d); i++) { f = f * var(i)^d[i]; }
        return(f);
}