DIRECTORY
Rope,
Basics,
IO,
Ascii,
Convert,
AlgebraClasses,
Variables,
DistribPolys;

DistribPolysImpl: CEDAR PROGRAM
IMPORTS Rope, IO, Ascii, Convert, Variables 
EXPORTS DistribPolys =
BEGIN OPEN AC: AlgebraClasses, VARS: Variables, DistribPolys;
DollarProc: PUBLIC TermCharProc =  { RETURN[char='$] };

RightBracketProc: PUBLIC TermCharProc =  { RETURN[char='] OR char=')] };

DollarRope: PUBLIC Rope.ROPE _ " $";
ReadDPoly: PUBLIC PROC [in: IO.STREAM, V: VARS.VariableSeq, coeffRing: AC.Structure, termCharProc: TermCharProc _ DollarProc] RETURNS [poly: DPolynomial, termChar: CHAR] = {
char: CHAR;
firstTerm: BOOL _ TRUE;
legalTermStartSeen: BOOL;
coeff: REF;
sign: INTEGER;
exponent: CARDINAL;
degreeVec: DegreeVector;
variable: Rope.ROPE;
varIndex: CARDINAL;
ReadDPFail: PUBLIC ERROR [subclass: ATOM _ $Unspecified] = CODE;
exponentChar1, exponentChar2: CHAR;
ok: BOOL;
one: REF _ coeffRing.class.one[coeffRing];
poly _ NIL;
[]_ in.SkipWhitespace[];
IF in.PeekChar[] = '0 THEN {
[] _ in.GetChar[];  -- toss it (assumes that we can strip a leading zero)
[]_ in.SkipWhitespace[];
char _ in.PeekChar[];
IF termCharProc[char] THEN RETURN[ZeroDPoly, char];
};
DO  -- the terms of a nonzero polynomial
legalTermStartSeen _ FALSE;
sign _ 1;
coeff _ one;  -- default term is +1 
degreeVec _ NIL;
[]_ in.SkipWhitespace[];
IF in.PeekChar[] = '- THEN {
sign _ -1;
[] _ in.GetChar[];  -- toss it
[]_ in.SkipWhitespace[];
}
ELSE IF in.PeekChar[] = '+ THEN {
[] _ in.GetChar[];  -- toss it
[]_ in.SkipWhitespace[];
}
ELSE IF NOT firstTerm THEN ERROR;
firstTerm _ FALSE;
IF coeffRing.class.legalFirstChar[in.PeekChar[], coeffRing] THEN {  -- coefficient present this term
legalTermStartSeen _ TRUE;
coeff _ coeffRing.class.read[in, coeffRing];
[]_ in.SkipWhitespace[];
IF coeffRing.class.equal[coeff, coeffRing.class.zero[coeffRing], coeffRing] THEN ERROR ReadDPFail[$ZeroCoefficient];
};
IF sign < 1 THEN coeff _  coeffRing.class.negate[coeff, coeffRing];  -- if sign < 1, then negate either coeff read or default coeff of 1
WHILE Ascii.Letter[in.PeekChar[] ] DO -- variables present this term
legalTermStartSeen _ TRUE;
exponent _ 1;
variable _ in.GetID[];
[]_ in.SkipWhitespace[];
varIndex _ VARS.VariableIndex[variable, V];
IF varIndex = 0 THEN ERROR ReadDPFail[$UnknownVariable];
IF in.PeekChar[] = '* OR in.PeekChar[] = '^ THEN {  -- allow either ** or ^
exponentChar1 _ in.GetChar[];
IF exponentChar1 ='* THEN {
exponentChar2 _ in.GetChar[]; 
IF exponentChar2 # '* THEN ERROR ReadDPFail[$SingleAsteriskExponent];
};
[]_ in.SkipWhitespace[];
SELECT in.PeekChar[] FROM
IN ['0..'9] => {
exponent _ in.GetCard;
[]_ in.SkipWhitespace[];
IF exponent = 0 THEN ERROR ReadDPFail[$ZeroExponent];
};
ENDCASE=> ERROR ReadDPFail[$NonNumericExponent];
};
[ok, degreeVec] _ DVInsertVariablePower[varIndex, exponent, degreeVec];
IF NOT ok THEN ERROR ReadDPFail[$RepeatedVariable];
ENDLOOP;  -- end of this term
IF legalTermStartSeen THEN { -- if we arrive here, we saw a complete legal term
[ok, poly] _ DPInsertTerm[coeff, degreeVec, poly];
IF NOT ok THEN ERROR ReadDPFail[$RepeatedMonomial];
}
ELSE ERROR ReadDPFail[$UnexpectedCharacter];
IF termCharProc[in.PeekChar[]] THEN RETURN[poly, in.GetChar[] ]; 
ENDLOOP;
};


DPolyFromRope: PUBLIC PROC [in: Rope.ROPE, V: VARS.VariableSeq, coeffRing: AC.Structure, termCharProc: TermCharProc _ DollarProc] RETURNS [out: DPolynomial] = {
stream: IO.STREAM _ IO.RIS[in];
termChar: CHAR;
[out, termChar ] _ ReadDPoly[stream, V, coeffRing, termCharProc];
};

DPolyToRope: PUBLIC PROC [in: DPolynomial, V: VARS.VariableSeq, coeffRing: AC.Structure, termRope: Rope.ROPE _ DollarRope] RETURNS [out: Rope.ROPE]={
one: REF _ coeffRing.class.one[coeffRing];
firstTerm: BOOL _ TRUE;
trivialMonomial: BOOL;
coeff, coeffAbs: REF;
degreeVec: DegreeVector;
coeffSign: Basics.Comparison;
exponent, index:  CARDINAL;
IF in = ZeroDPoly THEN RETURN[Rope.Concat["0", termRope]];
out _ "";
WHILE in#NIL DO
[coeff, degreeVec] _ in.first;  in _ in.rest;
IF coeffRing.class.sign # NIL THEN {  -- coeffRing is ordered 
coeffSign _ coeffRing.class.sign[coeff, coeffRing];
coeffAbs _ coeffRing.class.abs[coeff, coeffRing]
}
ELSE { -- for unordered coeffRing, act as though coeff is positive
coeffSign _ greater;
coeffAbs _ coeff;
};
IF coeffSign = less THEN out _ Rope.Concat[out,"- "] ELSE IF NOT firstTerm THEN out _ Rope.Concat[out,"+ "];
firstTerm _ FALSE;
IF NOT coeffRing.class.equal[coeffAbs, one, coeffRing] THEN out _ Rope.Cat[out, coeffRing.class.toRope[coeffAbs, coeffRing], " "];
trivialMonomial _ TRUE;
degreeVec _ DVReverse[degreeVec];
WHILE degreeVec#NIL DO
trivialMonomial _ FALSE;
exponent _ degreeVec.first;  degreeVec _ degreeVec.rest;
index _ degreeVec.first;  degreeVec _ degreeVec.rest;
out _ Rope.Concat[out, V[index] ];
IF exponent>1 THEN out _ Rope.Cat[out, "^", Convert.RopeFromCard[exponent]];
out _ Rope.Concat[out," "];
ENDLOOP;
IF trivialMonomial AND coeffRing.class.equal[coeffAbs, one, coeffRing] THEN out _ Rope.Cat[out, coeffRing.class.toRope[one, coeffRing], " "];
ENDLOOP;
out _ Rope.Concat[out, termRope];
};

WriteDPoly: PUBLIC PROC [in: DPolynomial, V: VARS.VariableSeq, coeffRing: AC.Structure, out: IO.STREAM, termRope: Rope.ROPE _ DollarRope] = {
polyRope: Rope.ROPE _ DPolyToRope[in, V, coeffRing, termRope];
out.PutF["\n %g \n", IO.rope[polyRope] ];
};
DPInsertTerm: PROC [coefficient: REF, degreeVec: DegreeVector, inPoly: DPolynomial] RETURNS [ok: BOOL, outPoly: DPolynomial] ~ {
nextCoeff: REF;
nextDegreeVec: DegreeVector;
poly: DPolynomial _ inPoly;
degreeVecComparison: [-1..1];
ok _ TRUE;
IF inPoly=NIL THEN {
outPoly_CONS[ [coefficient, degreeVec], NIL ];
RETURN
};
outPoly _ inPoly;
[nextCoeff, nextDegreeVec] _ poly.first;  poly _ poly.rest;
degreeVecComparison _ DVCompare[degreeVec, nextDegreeVec];
SELECT degreeVecComparison FROM
0 => { ok _ FALSE;  RETURN };
1  => {
outPoly_CONS[ [coefficient, degreeVec], inPoly ];
RETURN
};
ENDCASE; 
outPoly _ CONS[ [nextCoeff, nextDegreeVec], NIL];
WHILE poly# NIL DO
[nextCoeff, nextDegreeVec] _ poly.first;  poly _ poly.rest;
degreeVecComparison _ DVCompare[degreeVec, nextDegreeVec];
SELECT degreeVecComparison FROM
0 => { outPoly _ inPoly; ok _ FALSE;  RETURN };
1 =>  {
outPoly _ CONS[ [nextCoeff, nextDegreeVec], CONS[ [coefficient, degreeVec], outPoly] ];
outPoly _ DPReverse[outPoly];
outPoly _ DPNconc[outPoly, poly];
RETURN
};
ENDCASE; 
outPoly _ CONS[ [nextCoeff, nextDegreeVec], outPoly];
ENDLOOP;
outPoly _ CONS[ [coefficient, degreeVec], outPoly];
outPoly _ DPReverse[outPoly];
};

DPNconc: PROC [l1, l2: DPolynomial] RETURNS [DPolynomial] ~ {
z: DPolynomial _ l1;
IF z = NIL THEN RETURN[l2];
UNTIL z.rest = NIL DO
z _ z.rest;
ENDLOOP;
z.rest _ l2;
RETURN[l1];
};

DPReverse: PUBLIC PROC [list: DPolynomial] RETURNS[val: DPolynomial] = {
val _ NIL;
UNTIL list = NIL DO
val _ CONS[list.first, val];
list _ list.rest;
ENDLOOP;
RETURN[val];
}; -- of Reverse
DVInsertVariablePower: PUBLIC PROC [varIndex, exponent: CARDINAL, inDegreeVec: DegreeVector] RETURNS [ok: BOOL, outDegreeVec: DegreeVector] ~ {
nextIndex, nextExponent: CARDINAL;
degreeVec: DegreeVector _ inDegreeVec;
outDegreeVec _ inDegreeVec;
ok _ TRUE;
IF inDegreeVec=NIL THEN {
IF exponent=0 THEN RETURN ELSE {
outDegreeVec_CONS[varIndex, CONS[ exponent, NIL] ];
RETURN
}
};
nextIndex _ degreeVec.first;  degreeVec _ degreeVec.rest;
nextExponent _ degreeVec.first;  degreeVec _ degreeVec.rest;
SELECT varIndex FROM
= nextIndex => { ok _ FALSE;  RETURN };
> nextIndex => IF exponent=0 THEN RETURN ELSE {
outDegreeVec_CONS[varIndex, CONS[exponent, inDegreeVec] ]; 
RETURN
};
ENDCASE; 
outDegreeVec _ CONS[nextExponent, CONS[nextIndex, NIL]];
WHILE degreeVec# NIL DO
nextIndex _ degreeVec.first;  degreeVec _ degreeVec.rest;
nextExponent _ degreeVec.first;  degreeVec _ degreeVec.rest;
SELECT varIndex FROM
= nextIndex => { outDegreeVec _ inDegreeVec;ok _ FALSE;  RETURN };
> nextIndex => IF exponent=0 THEN
{ outDegreeVec _ inDegreeVec; RETURN }
ELSE {
outDegreeVec_DVCons4[nextExponent, nextIndex, exponent, varIndex, outDegreeVec]; 
outDegreeVec _ DVReverse[outDegreeVec];
outDegreeVec _ DVNconc[outDegreeVec, degreeVec];
RETURN
};
ENDCASE; 
outDegreeVec _ CONS[nextExponent, CONS[nextIndex, outDegreeVec]];
ENDLOOP;
outDegreeVec _ CONS[exponent, CONS[varIndex, outDegreeVec]];
outDegreeVec _ DVReverse[outDegreeVec];
};

DVCompare: PUBLIC PROC [dv1, dv2: DegreeVector] RETURNS [ [-1..1] ] ~ {
index1, index2, exponent1, exponent2: CARDINAL;
WHILE dv1#NIL AND dv2#NIL DO
index1 _ dv1.first;  dv1 _ dv1.rest;
exponent1 _ dv1.first;  dv1 _ dv1.rest;
index2 _ dv2.first;  dv2 _ dv2.rest;
exponent2 _ dv2.first;  dv2 _ dv2.rest;
IF index1 > index2 THEN RETURN[1];
IF index1 < index2 THEN RETURN[-1];
IF exponent1 > exponent2 THEN RETURN[1];
IF exponent1 < exponent2 THEN RETURN[-1];
ENDLOOP;
IF dv1#NIL THEN RETURN[1];
IF dv2#NIL THEN RETURN[-1];
RETURN[0];
};

DVDegree: PUBLIC PROC [degreeVec: DegreeVector, numVars: CARDINAL] RETURNS [degree: CARDINAL] ~ {
IF degreeVec = NIL THEN RETURN[0];
IF degreeVec.first = numVars THEN RETURN[degreeVec.rest.first] ELSE RETURN[0];
};

DVRemoveMainVariablePower: PUBLIC PROC [in: DegreeVector, numVars: CARDINAL] RETURNS [out: DegreeVector] ~ {
IF in = NIL THEN RETURN[NIL];
IF in.first = numVars THEN RETURN [in.rest.rest] ELSE RETURN[in];
};

DVAddMainVariablePower: PUBLIC PROC [in: DegreeVector, varIndex, exponent: CARDINAL] RETURNS [out: DegreeVector] ~ {
IF exponent>0 THEN RETURN[ CONS[varIndex, CONS[ exponent, in] ] ] ELSE RETURN[in];
};

DVCons4: PUBLIC PROC [x1, x2, x3, x4: CARDINAL, degreeVec: DegreeVector] RETURNS [DegreeVector] ~ {
RETURN[ CONS[x1, CONS[x2, CONS[x3, CONS[x4, degreeVec]]]] ];
};

DVNconc: PUBLIC PROC [l1, l2: DegreeVector] RETURNS [DegreeVector] ~ {
z: DegreeVector _ l1;
IF z = NIL THEN RETURN[l2];
UNTIL z.rest = NIL DO
z _ z.rest;
ENDLOOP;
z.rest _ l2;
RETURN[l1];
};

DVReverse: PUBLIC PROC [list: DegreeVector] RETURNS[val: DegreeVector] = {
val _ NIL;
UNTIL list = NIL DO
val _ CONS[list.first, val];
list _ list.rest;
ENDLOOP;
RETURN[val];
}; -- of Reverse


END.
(DistribPolysImpl.mesa
Last Edited by: Arnon, June 10, 1985 4:19:22 pm PDT
Types


Distributed Polynomial IO

(termChar has been removed from input stream).


The term (coefficient, degreeVec) is inserted in the distributed polynoimal inPoly.  NOT ok if degreeVec already occurs (and inPoly unchanged). If degreeVec doesn't yet occur, then ok, and outPoly  is inPoly with (coefficient, degreeVec) inserted.
DPInsertTerm is an insertion sort.
Degree Vectors
Variable varIndex raised to the exponent power is recorded in inDegreeVec.  NOT ok if the variable already occurs (and inDegreeVec unchanged). If the variable doesn't yet occur, then ok; if exponent = 0, inDegreeVec unchanged, otherwise outDegreeVec  is inDegreeVec with (varIndex, exponent) inserted.
DVInsertVariablePower is an insertion sort.
Κ
˜Jš
œ™J™3J˜š
Οk	˜	Jš
œ˜J˜Jšœ
˜J˜J˜Jš
œ˜Jš
œ
˜
Jš
œ
˜
—J˜
head2šœœ
˜Jšœ%˜,Jšœ˜—Jšœ
œ
œœ˜=
headš
Οn™J™
codešž
œœœ˜7J˜—šžœœœ	œ˜HJ˜—šœœœ˜$M™——šœž™J™šž	œœ
œœ
œœœ5œœ˜­
Jš
œ.™.Jšœœ
˜Jšœœœ
˜Jšœœ
˜Jšœœ
˜Jšœœ
˜Jšœ
œ
˜Jš
œ˜Jšœœ
˜Jšœ
œ
˜Jš	œœ
œœœ
˜@Jšœœ
˜#Jšœœ
˜	Jšœœ"˜*Jšœœ
˜Jš
œ˜šœœ˜JšœΟc5˜IJš
œ˜Jš
œ˜Jšœœ
œ˜3J˜—šœŸ$˜(Jšœœ
˜Jš
œ	˜	JšœŸ˜$Jšœœ
˜Jš
œ˜šœœ˜J˜
JšœŸ
˜Jš
œ˜J˜
—šœ
œœ˜!JšœŸ
˜Jš
œ˜J˜
—Jš
œ
œ
œœ
œ
˜!Jšœœ
˜šœ:œŸ ˜dMšœœ
˜Mš
œ,˜,Jš
œ˜MšœJœ
œ˜tM˜—Mšœ
œ5ŸC˜ˆ
šœœ
Ÿ˜DMšœœ
˜Mš
œ
˜
Mš
œ˜Jš
œ˜Mšœœ˜+Mšœœ
œ˜8šœœœŸ˜KJš
œ˜šœœ˜Jš
œ˜Jšœœ
œ%˜EJ˜—Jš
œ˜šœ˜šœ˜Mš
œ˜Jš
œ˜Mšœœ
œ˜5M˜—Mšœœ!˜0—M˜—Mš
œG˜GMšœ
œ
œ˜3JšœŸ˜—šœœŸ2˜OMš
œ2˜2Mšœ
œœ
œ˜3J˜
—Jšœ
œ"˜,Jšœœ
œ˜AJšœ
˜—J˜J˜J˜—šž
œœœœœ5œ˜ 
Mš	œœ
œœ
œ˜Mšœ
œ
˜Mš
œA˜AM˜M˜—šžœœ
œœœœœœ˜•
Jšœœ"˜*Jšœœœ
˜Jšœœ
˜Jšœœ
˜Jš
œ˜Jš
œ˜Jšœœ
˜Jšœœ
œ˜:J˜	šœœ
˜Jš
œ-˜-šœœ
œŸ˜>Jš
œ3˜3Jš
œ0˜0J˜
—šœŸ;˜BJš
œ˜Jš
œ˜J˜—Jšœœœ
œ
œœ˜lJšœœ
˜Jšœ
œ1œG˜‚
Jšœœ
˜Jš
œ!˜!šœœ
˜Jšœœ
˜Jš
œ8˜8Jš
œ5˜5Jš
œ"˜"Jšœœ:˜LJš
œ˜Jšœ
˜—Jšœœ1œB˜
Jšœ
˜—Jš
œ!˜!J˜J˜—šž
œœ
œœœœ
œœ˜
Jšœœ+˜>Jšœœ˜)J˜M™M™—š
žœœœ0œœ˜€
Mš
œχ
™χ
Mš
œ"™"Mšœœ
˜Mš
œ˜Mš
œ˜M˜Mšœœ
˜
šœœ
œ˜Mšœœœ˜.Mš
˜M˜—Mš
œ˜Mš
œ;˜;Mš
œ:˜:šœ˜Mšœœœ˜š
œ˜Mšœœ%˜1Mš
˜Mš
œ˜—Mšœ˜	—Mšœ
œœ˜1šœœ
˜Mš
œ;˜;Mš
œ:˜:šœ˜Mšœœœ˜/š
œ˜Mšœ
œœ'˜WMš
œ˜Mš
œ!˜!Mš
˜Mš
œ˜—Mšœ˜	—Mšœ
œ'˜5Mšœ
˜—Mšœ
œ%˜3Mš
œ˜M˜M˜—šžœœœ˜=Mš
œ˜Mšœœ
œ
œ˜šœ
œ
˜Mš
œ˜Mšœ
˜—M˜Mšœ˜Mš
œ˜M˜—šž	œœ
œœ˜HMšœœ
˜
šœœ
˜Mšœœ˜M˜Mšœ
˜—Mšœ˜MšœŸ
˜——™šžœœ
œœœœ!˜
Mš
œ­™­Mš
œ+™+Mšœœ
˜"Mš
œ&˜&Mš
œ˜Mšœœ
˜
šœ
œ
œ˜šœœ
œ
œ˜ Mšœ
œœœ˜3Mš
˜M˜
—M˜—Mš
œ9˜9Mš
œ<˜<šœ
˜Mšœœœ˜'š	œœœ
œ
œ˜/Mšœ
œœ˜;Mš
˜Mš
œ˜—Mšœ˜	—Mšœœœœ˜8šœœ
˜Mš
œ9˜9Mš
œ<˜<šœ
˜Mšœ1œœ˜Bšœœ˜!Mšœœ˜&Mšœ˜Mš
œQ˜QMš
œ'˜'Mš
œ0˜0Mš
˜Mš
œ˜—Mšœ˜	—Mšœœœ˜AMšœ
˜—Mšœœœ˜<Mš
œ'˜'M˜M˜—šž	œœ
œœ˜GMšœ&œ
˜/š	œœ
œœ
˜Mš
œ$˜$Mš
œ'˜'Mš
œ$˜$Mš
œ'˜'Mšœœ
œ˜"Mšœœ
œ˜#Mšœœ
œ˜(Mšœœ
œ˜)Mšœ
˜—Mšœœ
œ
œ˜Mšœœ
œ
œ˜Mšœ˜
M˜M˜—šžœœ
œ$œœ
œ˜aMšœ
œ
œ
œ˜"Mš
œœ
œœ
œ˜NM˜M˜—š
žœœ
œœœ˜lMš
œœ
œ
œ
œ˜Mš
œœ
œœ
œ˜AM˜M˜—š
žœœ
œ(œœ˜tMšœœ
œœœœ
œ˜RM˜M˜—š
žœœ
œœœ˜cMš
œœœœœ˜<M˜M˜—šžœœ
œœ˜FMš
œ˜Mšœœ
œ
œ˜šœ
œ
˜Mš
œ˜Mšœ
˜—M˜Mšœ˜Mš
œ˜M˜—šž	œœ
œœ˜JMšœœ
˜
šœœ
˜Mšœœ˜M˜Mšœ
˜—Mšœ˜MšœŸ
˜M˜——J˜Jšœ
˜—…—' 7Ι