// Javascript zur Division algebraischer Summen
// (c) Arndt Brünner, 3.11.2002
// Version: 10.11.2002
// Alle Rechte vorbehalten!

var EA, Rest_Merk, Rest_Merk_S=new Array(new Array(),new Array()),Rest_Merk_V=new Array();
var Rest_Merk_K;

function divAlgSums(s0,s1,VV)
{
	EA="Wie bei der schriftlichen Division von Zahlen zieht man auch bei der Division algebra-\n";
	EA+="ischer Summen vom Dividenden nach und nach passende Vielfache des Divisors ab, bis am \n";
	EA+="Ende möglichst kein Rest mehr bleibt.\n";
	EA+="Die Division wird nacheinander für jede der Variablen durchgeführt.\n";
	EA+="Für jede Variable werden nach Möglichkeit schrittweise diejenigen Summanden des Restes \n";
	EA+="eliminiert, bei denen die Variable in der jeweils höchsten Potenz steht.\n";
	EA+="Das ist bei allen Summanden im Dividenden möglich, die Vielfache des Summanden\n";
	EA+="des Divisors sind, der die betreffende Variable in der höchsten Potenz enthält.\n";
	EA+="Die Summanden des Quotienten erhält man durch Division dieses Summanden des jeweiligen\n";
	EA+="Restes durch den Summanden des Divisors mit der höchsten Potenz der betreffenden Variable.\n";
	EA+="\nIm einzelnen:\n\n";
	var TT="",TTT="",TR="",TQ="";
	var T=new Array(s0,s1);
	var S=new Array(2);
	var V=new Array();
	var Q=new Array();
	var ET=new Array();
	status="parse";
	var e=parseAlgSums(T,S,V);
	if(e!="")return "Fehler: "+e;
	var t="";
	//alert(V);
	var iv,iiv,i,j,nQ=0,keinRest=(1==9),iiiv=0;
	//for(i=0;i<V.length;i++)Rest_Merk_V[i]=V[i];
	status="sortiere";
	sort(S[0]);
	sort(S[1]);
	if((VV==null)||(VV.length==0))
	{
		var ExpDif=new Array(V.length),U=new Array(0),maxExpDif=0,maxExp0=new Array(),maxExp1=new Array();
		for(i=0;i<V.length;i++)
		{
			maxExp0[i]=0;maxExp1[i]=000000000;
			for(j=0;j<S[0].length;j++)maxExp0[i]=Math.max(S[0][j][i+1],maxExp0[i]);
			for(j=0;j<S[1].length;j++)maxExp1[i]=Math.max(S[1][j][i+1],maxExp1[i]);
			ExpDif[i]=maxExp0[i]-maxExp1[i];
			maxExpDif=Math.max(maxExpDif,ExpDif[i]);
		}
		j=0;
		for(i=maxExpDif;i>=0;i--)for(var ii=V.length-1;ii>=0;ii--)
			if((ExpDif[ii]==i)&&(maxExp0[ii]*maxExp1[ii]!=0))VV[j++]=V[ii];
	}
	document.f.p0.value=Rest_Merk=asStr(S[0],V);
	document.f.p1.value=TQ=asStr(S[1],V);Rest_Merk+="  <>  "+TQ; 
	if(vorherkuerzen)
	{
		t=asKuerzen(S[0],S[1],V);
		if((t!="")&&(t!="1"))
		{ 
			EA+="Die Polynome werden mit "+t+" gekürzt: \n";
			EA+=asStr(S[0],V)+"\n"+asStr(S[1],V)+"\n\n";
		}
	}
	TR=asStr(S[0],V);
	for(iiv=0;iiv<VV.length;iiv++) //Schleife für alle vorkommenden bzw. relevanten Variablen
	{
		for(iv=0;iv<V.length;iv++)if(V[iv]==VV[iiv])break;
		if(iv==V.length)continue;
		status="Schleife für Variable "+V[iv];
		iiiv++;
		var NO=new Array(0);
		var mi1=findMaxExp(S[1],iv+1,NO); // Index des Summanden mit maximalem Exponenten im Divisor
		if(mi1==-1)
		{
			EA+="Der Divisor enthält keinen Summanden mit "+V[iv]+"\n\n";
			if(iv==0)EA+="Alle Variablen abgearbeitet\n\n";
			continue;
		}
		EA+="Division nach Variable "+V[iv]+":\n\n";
		D=S[1][mi1]; //maßgeblicher Summand im Divisor
		ET[0]=D;
		TT=asStr(ET,V);
		EA+="Der Summand des Divisors mit maximaler Potenz von "+V[iv]+" ist "+TT+((TT==V[iv])?" selbst.":"") +"\n\n";
		if((TT.indexOf("-")>-1)||(TT.indexOf("·")>-1))TT="("+TT+")";
		var b=new RationaleZahl(1,1);
		b.setR(D[0]);
		var O=0;
		do{
			status="Schleife für Variable "+V[iv]+ "  Schritt "+(++O);
			EA+="Aktueller Rest: "+TR+"\n\n";
			//if(++O==5)return;
			var mi0=findMaxExp(S[0],iv+1,NO); // Index des Summanden mit maximalem Exponenten im Dividenden
			if(mi0==-1)
			{
				EA+="Kein "+((O>1)?"weiterer ":"")+"Summand mit einem Vielfachen von "+TT+" im Rest -> Abbruch\n\n";
				break;
			}
			ET[0]=S[0][mi0];
			TTT=asStr(ET,V);
			EA+="Der Summand im Rest mit der "+((O>1)?"nächstkleineren":"höchsten")+" Potenz von "+V[iv]+" ist "+TTT+((V[iv]==TTT)?" selbst":"")+  "\n";
			if(S[0][mi0][iv+1]<S[1][mi1][iv+1])
			{	
				EA+="\ngrad("+TTT+") < grad("+TT.replace(/\(/,"").replace(/\)/,"")+") -> Abbruch\n\n";
				break;
			}
			var c=new RationaleZahl(1,1);
			c.set(-1,1);
			c.mult(S[0][mi0][0]);
			if(c.z==0){break;}
			c.div(b);//alert("c="+c.str());
			var K=new Array(V.length);  // Differenzen der Exponenten = Exponenten des neuen Summanden im Quotienten
			for(i=0;i<V.length;i++){K[i]=S[0][mi0][i+1]-S[1][mi1][i+1];if(K[i]<0)break;}
			if(i<V.length)
			{
				EA+="Dies ist kein Vielfaches von "+TT.replace(/\(/,"").replace(/\)/,"")+" --> Weiter\n\n";
				NO[NO.length]=mi0;
				continue;
			}
			j=getFreeIndex(S[0]); 
			status="Berechne neuen Rest";
			SB=new Array(S[1].length);
			for(i=0;i<S[1].length;i++)
			{
				if(S[0][j]==null){S[0][j]=new Array();S[0][j][0]=new RationaleZahl(1,1);}
				S[0][j][0].setR(S[1][i][0]);
				S[0][j][0].mult(c);
				SB[i]=new Array(V.length+1);
				SB[i][0]=new RationaleZahl(1,1);
				for(var ii=0;ii<V.length;ii++)
				{
					S[0][j][ii+1]=K[ii]+S[1][i][ii+1];
					SB[i][ii+1]=S[0][j][ii+1];
				}
				SB[i][0].setR(S[0][j][0]);
				SB[i][0].z=-SB[i][0].z;
				j++;
			}
			Q[nQ]=new Array();
			c.z=-c.z;
			Q[nQ][0]=c;
			for(i=0;i<V.length;i++){Q[nQ][i+1]=K[i];}
			//alert(asStr(S[0],V));
			status="fasse zusammen";
			together(S[0]);
			//alert(asStr(S[0],V));
			ET[0]=Q[nQ];
			var TTTT=asStr(ET,V);
			EA+="Berechne den Quotienten "+TTT+" / "+TT+"  =  "+TTTT+"\n";
			var TQK=" · "+TQ;
			if((TQ.indexOf("-")>-1)||(TQ.indexOf("+")>-1))TQK="·("+TQ+")";
			EA+="Berechne das Produkt "+TTTT+TQK+" = "+asStr(SB,V) +"\n";
			EA+="und subtrahiere dieses Produkt vom letzten Rest.\n\n";
			//if(!confirm(EA))return;
			nQ++;			
			//alert(asStr(S[0],V));
			status="Überprüfe, ob Rest=0";
			for(i=0;i<S[0].length;i++)if(S[0][i][0].z!=0)break;
			if(i==S[0].length)
			{
				EA+="\nkein Rest mehr -> Abbruch\n\n";
				keinRest=true;break;
			}
			sort(S[0]);
			TR=asStr(S[0],V);
			
			//EA+=TR+"\n";
		}while(true);
		if(keinRest)break;
	}
	if(iiiv==0)
	{
		EA="In den Polynomen kommt ";
		if(VV.length>1)EA+="keine der angegebenen Variablen ("+VV.join(", ")+") vor.\n\n";
		else EA+="die Variable "+VV[0]+" nicht vor.\n\n";
		EA+="Die Einschränkung wird daher gelöscht. Klicken Sie erneut auf [=], \num die Division uneingeschränkt auszuführen.\n\n";
		return "";
	}
	EA+="Alle Variablen abgearbeitet\n\n";
	status="fasse Quotient zusammen";
	together(Q);
	sort(Q);
	status="OK";
	//document.f.Erkl.value=asStr(Q,V)+((!keinRest)? " + ("+asStr(S[0],V)+")/("+asStr(S[1],V)+")":"");
	var VZ="+";

	t=asStr(Q,V);
	Rest_Merk+="  <>  "+t;

	if(!keinRest)
	{
		sort(S[0]);
		
		EA+="Ergänze den Quotienten durch den Restquotienten: \" + Rest/Divisor\"\n\n";

		var krz=asKuerzen(S[0],S[1],V);
		if(krz!="1")EA+="Kürze den Restquotienten mit "+krz+"\n\n";

		Rest_Merk+="  <>  "+asStr(S[0],V)+"  <>  "+asStr(S[1],V);

		var am=-1,amm=(1==0),bm=-1,bmm=(1==0),vz=1;
		for(i=0;i<S[0].length;i++)
		{
			if(S[0][i][0].z!=0){if(am>-1){amm=false;break;} am=i;amm=true;}
		}
		if(amm)
		{
			for(i=0;i<S[1].length;i++)
				S[1][i][0].z*=S[0][am][0].n;
			S[0][am][0].n=1;
		}
		for(i=0;i<S[1].length;i++)
		{
			if(S[1][i][0].z!=0){if(bm>-1){bmm=false;break;} bm=i;bmm=true;}
		}
		if(bmm)
		{
			for(i=0;i<S[0].length;i++)
				S[0][i][0].z*=S[1][bm][0].n;
			S[1][bm][0].n=1;
		}
	
		if(S[0][am][0].z<0)
		{
			for(i=0;i<S[0].length;i++)S[0][i][0].z=-S[0][i][0].z;
			vz*=-1;
		}

		if(asStr(S[1],V).charAt(0)=="-")
		{
			for(i=0;i<S[1].length;i++)S[1][i][0].z=-S[1][i][0].z;
			vz*=-1;
		}
		VZ=(vz==1)?" + ":" - ";

		var ta=asStr(S[0],V), tb=asStr(S[1],V);
		if((tb.replace(/\d/g,"").length>0)&&(tb.length>1))tb="("+tb+")";
		if((ta.indexOf("+")>-1)||(ta.indexOf("- ")>-1))ta="("+ta+")";
	}



	if(t=="")VZ=(VZ==" - ")?"-":""; 

	t+= (!keinRest)? VZ+ta+"/"+tb:"";


	EA+="Ergebnis der Division:\n\n("+document.f.p0.value+") / ("+document.f.p1.value+") = "+t+"\n\n\n\n\n___________________________________________________\n  Erstellt durch ein Javascript von Arndt Brünner\n";
	
	return t;
}

function asStr(s,v)
{
	var t="",k="",e=0; //alert(s+"\n"+s.length);
	for(var i=0;i<s.length;i++)
	{	
		if((s[i][0].z==null)||(s[i][0].z==0))continue;
		if((s[i][0].z>0)&&(i>0))t+="+";
		k=s[i][0].str();
		if(k=="-1")k="-";
		if(k=="1")k="";
		for(var j=0;j<v.length;j++)
			if((e=s[i][j+1])>0)k+="·"+v[j]+((e>1)?"^"+e:"");
		if(k=="")k="1";
		if(k=="-")k="-1";
		if(k.charAt(0)=="·")k=k.substring(1,k.length);
		if(k.substr(0,2)=="-·")k="-"+k.substring(2,k.length);
		t+=k;
	}
	t=t.replace(/\+/g," + ").replace(/-/g," - ");
	if(t.substr(0,3)==" - ")t="-"+t.substring(3,t.length);
	if(t.substr(0,3)==" + ")t=t.substring(3,t.length);
	return t;
}

function findMaxExp(S,i,NO)
{
	var j,m=0,jm=-1,k; 
	for(j=0;j<S.length;j++)
	{
		if(S[j][0].z==0)continue;
		if((S[j][i]>m)&&(S[j][0].z!=0))
		{
			for(k=0;k<NO.length;k++)
				if(NO[k]==j)break;
			if(k<NO.length)continue;
			m=S[j][i];jm=j;
		}
	}
	return jm;
}

function parseAlgSums(Terms,S,v)
{
	var t="",i,j,k,m,mv,B=new Array(2),minus=(1==0),I;
	t=Terms.join(" ");
	status="extrahiere Variablen";
	var n=extractVars(t,v);
	for(I=0;I<Terms.length;I++)
	{
		status="Term "+I;
		s=new Array();
		t=Terms[I].replace(/ /g,"");
		t=t.replace(/,/g,".").replace(/²/g,"2").replace(/³/g,"3").replace(/\^/g,"");
		t=t.replace(/·/g,"").replace(/\*/g,"").replace(/•/g,"");
		minus=false;
		if(t.charAt(0)=="-"){minus=true;t=t.substring(1,t.length);}
		var T=(t.replace(/\+/g,"|").replace(/-/g,"|-")).split("|");
		if(minus){t="-"+t;T[0]="-"+T[0];}
		for(i=0;i<T.length;i++)
		{
			status="Term "+I+", Summand "+i;
			s[i]=new Array(n+1);
			for(j=0;j<n;j++)s[i][j+1]=0;
			mv=T[i].length;
			var TT=T[i].replace(/\d/g,"#").replace(/'/g,"#").replace(/\./g,"#").replace(/_/g,"#");
			for(j=0;j<n;j++)s[i][j+1]=0;
			for(j=0;j<n;j++)
			{
				status="Term "+(I+1)+", Summand "+(i+1)+", Variable "+v[j];
				do{
					k=T[i].indexOf(v[j]);
					if(k==-1)break;
					if(TT.charAt(k+1)=="-")return "negativer Exponent";
					if(k<mv)mv=k;
					for(m=k+1;m<TT.length;m++)
						if(TT.charAt(m)!="#")break;
					var ss=Number(T[i].substring(k+1,m));
					if(ss!=Math.floor(ss))return "Gebrochener Exponent";
					if(ss==0)ss=1;
					s[i][j+1]+=ss;
					T[i]=T[i].substr(0,k)+"$"+T[i].substring(k+1,T[i].length);
				}while(true);
			}
			//alert("T[i]="+T[i]+"\ns="+s[i]);
			TT=T[i].substr(0,mv);
			if(TT=="-")TT="-1";//alert(T[i].substr(0,mv)+"\nTT="+TT);
			if(TT.indexOf("/")>-1)
			{
				B=TT.split("/");
			}
			else if(TT.length>0)
				{
					status="getBruchFromDez("+TT+")";
					B=getBruchFromDez(TT).split("/");
					//alert("Rückgabe="+getBruchFromDez(TT));
				}
			else 
			{
				B[0]=1;B[1]=1;//alert("Hallo "+TT.length);
			}
			if(B.length==1)B[1]=1;
			status="erzeuge neue RationaleZahl mit "+B[0]+"/"+B[1];
			s[i][0]=new RationaleZahl(B[0],B[1]);
			//alert("s="+s[i][0].str());
		}
		status="Fasse zusammen";
		together(s);
		S[I]=s;
	}
	return "";
}

function together(s)
{
	var i,j,k,m;
	for(i=0;i<s.length;i++)
		if(s[i][0].z!=0)
		{
			for(j=i+1;j<s.length;j++)
			{
				for(k=1;k<s[i].length;k++)	
				{
					if(s[i][k]!=s[j][k])break;
				}
				if(k==s[i].length)
				{
					//alert(i+"  "+j+"\n"+s[i][0].str()+"  "+s[j][0].str()); 
					s[i][0].add(s[j][0]);
					for(m=1;m<s[j].length;m++)s[j][m]=0;s[j][0].z=0;
					if(s[i][0].z==0)break;
				}
			}
		}
		//var t="";for(X=0;X<s.length;X++)t+=s[X][0].str()+"  ";alert(t);
}

function getFreeIndex(s)
{
	for(var i=s.length-1;i>=0;i--)
	{
		if(s[i][0]==null)s[i][0]=new RationaleZahl(0,1);
		if(s[i][0].z!=0)return i+1;
	}
	return -1;
}

function extractVars(t,V)
{
	var v="xyzabcdefghijklmnoqrstuvw";
	t=t.toLowerCase();
	var i,j=0;
	for(i=0;i<v.length;i++)if(t.indexOf(v.charAt(i))>-1)V[j++]=v.charAt(i);
	return j;
}

function sort(X)
{
    L=new Array(32),R=new Array(32),x=new Array(20);
    var s, i, j, LL, rr, v, w, ii,n,m,B=new RationaleZahl(1,1);
    if((n=X.length)<=1)return;
    for(i=0;i<n;i++){x[i]=0;m=1;for(j=X[0].length-1;j>0;j--){x[i]+=m*X[i][j];m*=20;}}
    s=0; L[0]=0; R[0]=X.length-1;
    do
    {
        LL = L[s]; rr = R[s];
        s--;
        do
        {
            i = LL; j = rr;
            v = x[Math.floor((LL + rr) / 2)];
            do
		{
                while((x[i]>v)) i++;
                while((x[j]<v)) j--;
                if (i <= j)
                {
			  for(var I=1;I<X[i].length;I++)
	                    {w = X[i][I]; X[i][I] = X[j][I]; X[j][I] = w;}
				  B.setR(X[i][0]);X[i][0].setR(X[j][0]);X[j][0].setR(B);
				  w=x[i];x[i]=x[j];x[j]=w;
                    i++; j--;
                }
            } while (i <= j);
            if (j - LL >= rr - 1)
            {
                if (LL < j)
                {
                    s++;
                    L[s] = LL; R[s] = j;
                }
                LL = i;
            }
            else
            {
                if (i < rr)
                {
                    s++;
                    L[s] = i; R[s] = rr;
                }
                rr = j;
            }
        } while (LL < rr);
    } while (s >= 0);
}


function asKuerzen(A,B,V)
{
	var i=0,s="",v="";
	if((A[0][0].z<0)&&(B[0][0].z)<0)
	{
		for(i=0;i<A.length;i++)A[i][0].z=-A[i][0].z;
		for(i=0;i<B.length;i++)B[i][0].z=-B[i][0].z;
		s="-";
	}
	var gz=Math.abs(A[0][0].z),gn=A[0][0].n,i=0,a0=-1;b0=-1;
	for(i=1;i<A.length;i++)
	{
		if(A[i][0].z!=0)
		{
			gz=ggT(gz,Math.abs(A[i][0].z));
			gn=ggT(gn,A[i][0].n);
		}
		if((gn==1)&&(gz==1))break;
	}
	for(i=0;i<B.length;i++)
	{
		if(B[i][0].z!=0)
		{
			gz=ggT(gz,Math.abs(B[i][0].z));
			gn=ggT(gn,B[i][0].n);
		}
		if((gn==1)&&(gz==1))break;
	}
	for(i=0;i<A.length;i++){A[i][0].z/=gz;A[i][0].n/=gn;if((a0==-1)&&(A[i][0].z!=0))a0=i;}
	for(i=0;i<B.length;i++){B[i][0].z/=gz;B[i][0].n/=gn;if((b0==-1)&&(B[i][0].z!=0))b0=i;}
	if(s=="-")gz=-gz;
	var k= (gn!=1)?gz+"/"+gn:gz;
	for(i=1;i<A[0].length;i++)
	{
		var min=1e15,M;
		for(j=0;j<A.length;j++)
		{
			if(A[j][0].z==0)continue;
			M=A[j][i];
			if(M<min)min=M;
			if(M==0)break;
		}
		if(min==0)continue;
		for(j=0;j<B.length;j++)
		{
			if(B[j][0].z==0)continue;
			M=B[j][i];
			if(M<min)min=M;
			if(M==0)break;
		}
		if(min==0)continue;
		for(j=0;j<A.length;j++)	A[j][i]-=min;
		for(j=0;j<B.length;j++)	B[j][i]-=min;
		v+="·"+((min==1)?V[i-1]:((min>1)?V[i-1]+"^"+min:""));
		Rest_Merk_K+=k+"·"+V[i-1]+"^"+min+"#";//alert(Rest_Merk_K);
	}
	if(v.charAt(0)=="·")v=v.substring(1,v.length);
	if((k=="1")&&(v!=""))return v;
	if((k=="-1")&&(v!=""))return "-"+v;
	return k+v;
}