DIRECTORY
Rope,
Convert USING [RopeFromCard],
IO,
RatNums,
Polynomials;

PolynomialsImpl: CEDAR PROGRAM
IMPORTS Rope, Convert, IO, RatNums 
EXPORTS Polynomials =
BEGIN OPEN RN: RatNums, Polynomials;


PolynomialAdd: PUBLIC PROC [in1, in2: Polynomial] RETURNS [out: Polynomial] ~ {
previousOutTerm, outTerm, tail: Polynomial;
termToAdd: BOOL;
IF in1 = ZeroPoly THEN RETURN[ in2];
IF in2 = ZeroPoly THEN RETURN[ in1];
IF in1.numVars # in2.numVars THEN ERROR;
WITH in1 SELECT FROM
input1: REF PolynomialRec.constant => {
WITH in2 SELECT FROM
input2: REF PolynomialRec.constant => {
val: RN.RatNum _ RN.RatNumAdd[input1.value, input2.value];
IF RN.RatNumZero[val] THEN RETURN;
out _ NEW[PolynomialRec _ [
numVars: 0,
data: constant[value: val]
] ];
RETURN;
};
ENDCASE => ERROR;
};
input1: REF PolynomialRec.nonconstant => {
WITH in2 SELECT FROM
input2: REF PolynomialRec.nonconstant => {
out _ previousOutTerm _ ZeroPoly;
WHILE input1 # ZeroPoly AND input2 # ZeroPoly DO
termToAdd _ TRUE;
SELECT input1.leadingTerm.exponent FROM
< input2.leadingTerm.exponent => {
outTerm _ NEW[PolynomialRec _ [
numVars: input2.numVars,
data: nonconstant[leadingTerm: input2.leadingTerm, reductum: ZeroPoly]
] ]; 
input2 _ NARROW[ input2.reductum ];
};
> input2.leadingTerm.exponent => {
outTerm _ NEW[PolynomialRec _ [
numVars: input1.numVars,
data: nonconstant [leadingTerm: input1.leadingTerm, reductum: ZeroPoly ]
] ];
input1 _ NARROW[ input1.reductum ];
};
= input2.leadingTerm.exponent => {
coeff: Polynomial _ PolynomialAdd[
input1.leadingTerm.coefficient,
input2.leadingTerm.coefficient
];
IF coeff # ZeroPoly THEN
outTerm _ NEW[PolynomialRec _ [
numVars: input1.numVars,
data: nonconstant [ leadingTerm: [ exponent: input2.leadingTerm.exponent,
coefficient: coeff ],
reductum: ZeroPoly ]
] ]
ELSE
termToAdd _ FALSE;
input1 _ NARROW[ input1.reductum ];
input2 _ NARROW[ input2.reductum ];
};
ENDCASE;
IF termToAdd THEN IF previousOutTerm # ZeroPoly THEN {
WITH previousOutTerm SELECT FROM
previousOutTermVariant: REF PolynomialRec.nonconstant => {
previousOutTermVariant.reductum _ outTerm;
previousOutTerm _ outTerm;
};
ENDCASE => ERROR;
}
ELSE out _ previousOutTerm _ outTerm;
ENDLOOP;
IF input1 = ZeroPoly THEN tail _ input2 ELSE tail _ input1;
IF out # ZeroPoly THEN WITH previousOutTerm SELECT FROM
previousOutTermVariant: REF PolynomialRec.nonconstant => previousOutTermVariant.reductum _ tail;
ENDCASE => ERROR
ELSE out _ tail;
};
ENDCASE => ERROR;
};
ENDCASE;
};

PolynomialNegate: PUBLIC PROC [in: Polynomial] RETURNS [out: Polynomial] ~ {
outTerm, previousOutTerm: Polynomial;
IF in = ZeroPoly THEN RETURN[ZeroPoly];
WITH in SELECT FROM
input: REF PolynomialRec.constant => {
out _ NEW[PolynomialRec _ [
numVars: 0,
data: constant[value: RN.RatNumNegate[input.value] ]
] ];
RETURN;
};
input: REF PolynomialRec.nonconstant => {
previousOutTerm _ ZeroPoly;
WHILE input # ZeroPoly DO
outTerm _ NEW[PolynomialRec _ [
numVars: input.numVars,
data: nonconstant[leadingTerm: [
exponent: input.leadingTerm.exponent,
coefficient: PolynomialNegate[input.leadingTerm.coefficient]
],
reductum: ZeroPoly ]
] ]; 
input _ NARROW[input.reductum ];
IF previousOutTerm # ZeroPoly THEN {
WITH previousOutTerm SELECT FROM
previousOutTermVariant: REF PolynomialRec.nonconstant => {
previousOutTermVariant.reductum _ outTerm;
previousOutTerm _ outTerm;
};
ENDCASE => ERROR;
}
ELSE out _ previousOutTerm _ outTerm;
ENDLOOP;
};
ENDCASE;
};

PolynomialSubtract: PUBLIC PROC [in1, in2: Polynomial] RETURNS [Polynomial] ~ {
RETURN[ PolynomialAdd[ in1, PolynomialNegate[ in2] ] ];
};

PolynomialMultiply: PUBLIC PROC [in1, in2: Polynomial] RETURNS [out: Polynomial] ~ {
previousOutSummandTerm, outSummandTerm, outSummand: Polynomial;
IF in1 = ZeroPoly OR in2 = ZeroPoly THEN RETURN[ZeroPoly];
IF in1.numVars # in2.numVars THEN ERROR;
WITH in1 SELECT FROM
input1: REF PolynomialRec.constant => {
WITH in2 SELECT FROM
input2: REF PolynomialRec.constant => {
val: RN.RatNum _ RN.RatNumMultiply[input1.value, input2.value];
out _ NEW[PolynomialRec _ [
numVars: 0,
data: constant[value: val]
] ];
RETURN;
};
ENDCASE => ERROR;
};
input1: REF PolynomialRec.nonconstant => {
WITH in2 SELECT FROM
input2: REF PolynomialRec.nonconstant => {
scratchInput1: REF PolynomialRec.nonconstant;
out _ ZeroPoly;
WHILE input2 # ZeroPoly DO
previousOutSummandTerm _ ZeroPoly;
scratchInput1 _  input1;
WHILE scratchInput1 # ZeroPoly DO
coeff: Polynomial _ PolynomialMultiply[
scratchInput1.leadingTerm.coefficient,
input2.leadingTerm.coefficient
];
outSummandTerm _ NEW[PolynomialRec _ [
numVars: scratchInput1.numVars,
data: nonconstant [ leadingTerm: [
exponent: scratchInput1.leadingTerm.exponent + input2.leadingTerm.exponent,
coefficient: coeff ],
reductum: ZeroPoly ]
] ];
IF previousOutSummandTerm # ZeroPoly THEN
WITH previousOutSummandTerm SELECT FROM
previousOutSummandTermVariant: REF PolynomialRec.nonconstant => {
previousOutSummandTermVariant.reductum _ outSummandTerm;
previousOutSummandTerm _ outSummandTerm;
};
ENDCASE => ERROR
ELSE outSummand _ previousOutSummandTerm _ outSummandTerm;
scratchInput1 _ NARROW[ scratchInput1.reductum ];
ENDLOOP;
out _ PolynomialAdd[out, outSummand];
input2 _ NARROW[ input2.reductum ];
ENDLOOP;
};
ENDCASE => ERROR
};
ENDCASE;
};




UnivariateMonomial: PUBLIC PROC [coeff: RN.RatNum, exp: CARDINAL] RETURNS [out: Polynomial] = {
RETURN[ NEW[ PolynomialRec _ [
numVars: 1,
data: nonconstant [ leadingTerm: [ exponent: exp,
coefficient: NEW[ PolynomialRec _ [
numVars: 0,
data: constant [ coeff ]
] ] ],
reductum: ZeroPoly ]
] ] ];
};

MultivariateMonomial: PUBLIC PROC [coeff: Polynomial, exp: CARDINAL] RETURNS [out: Polynomial] = {
RETURN[ NEW[ PolynomialRec _ [
numVars: coeff.numVars + 1,
data: nonconstant [ leadingTerm: [ exponent: exp,
coefficient: coeff ],
reductum: ZeroPoly ]
] ] ];
};

MakePolynomialZero: PUBLIC PROC RETURNS [out: Polynomial _ ZeroPoly] = {};
ReadVariableList: PUBLIC PROC [in: IO.STREAM] RETURNS [V: VariableList] ~ {
puncChar: CHAR;
nextV: Rope.ROPE;
ReadVLFail: PUBLIC ERROR [subclass: ATOM _ $Unspecified] = CODE;
W, VTail: VariableList;
V _ NIL;
[]_ in.SkipWhitespace[];
puncChar _ in.GetChar[ ];
[]_ in.SkipWhitespace[];
IF puncChar # '( THEN ReadVLFail[$LeftParenExpected];
WHILE puncChar # ') DO
nextV _ IO.GetID[in];
[]_ in.SkipWhitespace[];
IF V=NIL THEN VTail _ V _LIST[nextV] ELSE
{ W _ LIST[nextV];  VTail.rest _ W;  VTail _ W };
puncChar _ in.GetChar[ ];
[]_ in.SkipWhitespace[];
IF puncChar # ') THEN IF puncChar # ', THEN ReadVLFail[$CommaExpected];
ENDLOOP;
};

VariableListFromRope: PUBLIC PROC [in: Rope.ROPE] RETURNS [V: VariableList]={
VLStream: IO.STREAM _ IO.RIS[in];
RETURN[ ReadVariableList[ VLStream ] ];
};

VariableListToRope: PUBLIC PROC [V: VariableList] RETURNS [out: Rope.ROPE]={
out _ "(";  WHILE V#NIL DO
out _ Rope.Concat[ out, V.first ];
V _ V.rest;
IF V#NIL THEN out _ Rope.Concat[ out, "," ];
ENDLOOP;
out _ Rope.Concat[ out, ")" ];
};

WriteVariableList: PUBLIC PROC [V: VariableList, out: IO.STREAM] = {
VLRope: Rope.ROPE _ VariableListToRope[V];
out.PutF["\n %g \n", IO.rope[VLRope] ];
};
ReadDPolynomial: PUBLIC PROC [in: IO.STREAM, V: VariableList] RETURNS [poly: DPolynomial] = {
legalTermStartSeen: BOOL;
coeff: RN.RatNum;
sign: INTEGER;
exponent: CARDINAL;
degreeVec: DegreeVector;
variable: Rope.ROPE;
varIndex: CARDINAL;
ReadDPFail: PUBLIC ERROR [subclass: ATOM _ $Unspecified] = CODE;
exponentChar1, exponentChar2: CHAR;
ok: BOOL;
poly _ NIL;
[]_ in.SkipWhitespace[];
IF in.PeekChar[] = '0 THEN {
[] _ in.GetChar[];  -- toss it
[]_ in.SkipWhitespace[];
IF in.GetChar[] = '$ THEN { poly_ ZeroDPoly; RETURN } ELSE ReadDPFail[$UnexpectedCharacter];
};
DO  -- the terms of a nonzero polynomial
legalTermStartSeen _ FALSE;
sign _ 1;  -- default term (+1)
coeff _ RN.RatNumFromSmallCards[1,1,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[];
};
SELECT in.PeekChar[] FROM
IN ['0..'9] => {  -- coefficient present this term
legalTermStartSeen _ TRUE;
[coeff, ok] _ RN.ReadRatNum[in];
[]_ in.SkipWhitespace[];
IF NOT ok THEN ReadDPFail[$BadCoefficient];
IF RN.RatNumZero[coeff] THEN ReadDPFail[$ZeroCoefficient];
};
ENDCASE;
IF sign < 1 THEN coeff _  RN.RatNumNegate[coeff];  -- if sign < 1, then negate either coeff read or default coeff of 1
WHILE Letter[in.PeekChar[] ] DO -- variables present this term
legalTermStartSeen _ TRUE;
exponent _ 1;
variable _ in.GetID[];
[]_ in.SkipWhitespace[];
varIndex _ VariableIndex[variable, V];
IF varIndex = 0 THEN ReadDPFail[$UnknownVariable];
IF in.PeekChar[] = '* OR in.PeekChar[] = '^ THEN {  -- allow either ** or ^
exponentChar1 _ in.GetChar[];
IF exponentChar1 ='* THEN {
exponentChar2 _ in.GetChar[]; 
IF exponentChar2 # '* THEN ReadDPFail[$SingleAsteriskExponent];
};
[]_ in.SkipWhitespace[];
SELECT in.PeekChar[] FROM
IN ['0..'9] => {
exponent _ in.GetCard;
[]_ in.SkipWhitespace[];
IF exponent = 0 THEN ReadDPFail[$ZeroExponent];
};
ENDCASE=> ReadDPFail[$NonNumericExponent];
};
[ok, degreeVec] _ DVInsertVariablePower[varIndex, exponent, degreeVec];
IF NOT ok THEN 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 ReadDPFail[$RepeatedMonomial];
}
ELSE ReadDPFail[$UnexpectedCharacter];
IF in.PeekChar[] = '$ THEN RETURN;
ENDLOOP;
};

DPolynomialFromRope: PUBLIC PROC [in: Rope.ROPE, V: VariableList] RETURNS [out: DPolynomial] = {
stream: IO.STREAM _ IO.RIS[in];
out _ ReadDPolynomial[stream, V];
};

DPolynomialToRope: PUBLIC PROC [in: DPolynomial, V: VariableList] RETURNS [out: Rope.ROPE]={
One: RN.RatNum = RN.RatNumFromSmallCards[1,1,1];
firstTerm: BOOL _ TRUE;
trivialMonomial: BOOL;
coeff, coeffAbs: RN.RatNum;
degreeVec: DegreeVector;
coeffSign: RN.Sign;
exponent, index:  CARDINAL;
IF in = ZeroDPoly THEN RETURN["0 $"];
out _ "";
WHILE in#NIL DO
[coeff, degreeVec] _ in.first;  in _ in.rest;
coeffSign _ coeff.sign;
coeffAbs _ RN.RatNumABS[coeff];
IF coeffSign=NEGATIVE THEN out _ Rope.Concat[out,"- "] ELSE IF NOT firstTerm THEN out _ Rope.Concat[out,"+ "];
firstTerm _ FALSE;
IF NOT RN.RatNumEqual[coeffAbs, One] THEN out _ Rope.Cat[out, RN.RatNumToRatRope[coeffAbs], " "];
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, Variable[V, index] ];
IF exponent>1 THEN out _ Rope.Cat[out, "^", Convert.RopeFromCard[exponent]];
out _ Rope.Concat[out," "];
ENDLOOP;
IF trivialMonomial AND RN.RatNumEqual[coeffAbs, One] THEN out _ Rope.Cat[out, RN.RatNumToRatRope[coeffAbs], " "];
ENDLOOP;
out _ Rope.Concat[out,"$"];
};

WriteDPolynomial: PUBLIC PROC [in: DPolynomial, V: VariableList, out: IO.STREAM] = {
polyRope: Rope.ROPE _ DPolynomialToRope[in, V];
out.PutF["\n %g \n", IO.rope[polyRope] ];
};

PolyFromDPoly: PUBLIC PROC [in: DPolynomial, V: VariableList] RETURNS [out: Polynomial] = {
numVars: CARDINAL = NumVars[V];  -- we need V arg to get this number
termDegree: CARDINAL; -- degree in main variable of current (output) term
outTermDCoefficient: DPolynomial;  -- output term coefficient, still in DP rep
outTermCoefficient: Polynomial; -- output term coefficient, converted to P rep
outTerm: Polynomial; -- completed output term
previousTerm: Polynomial;
IF in = ZeroDPoly THEN RETURN[ZeroPoly];
IF numVars=0 THEN {
out _ NEW[PolynomialRec _ [
numVars: 0,
data: constant[value: in.first.coefficient]
] ];
RETURN;
};
previousTerm _ ZeroPoly;
WHILE in#NIL DO
termDegree _ DVDegree[in.first.degreeVector, numVars]; -- degree in main variable
outTermDCoefficient _ LIST[ [in.first.coefficient, DVRemoveMainVariablePower[in.first.degreeVector, numVars] ] ];
in _ in.rest;
WHILE in#NIL AND DVDegree[in.first.degreeVector, numVars] = termDegree DO
outTermDCoefficient _ CONS[ [in.first.coefficient, DVRemoveMainVariablePower[in.first.degreeVector, numVars] ], outTermDCoefficient];
in _ in.rest;
ENDLOOP;
outTermDCoefficient _ DPReverse[ outTermDCoefficient ];
outTermCoefficient _ PolyFromDPoly[ outTermDCoefficient, VLRemoveMainVariable[V] ];
outTerm _ NEW[PolynomialRec _ [
numVars: numVars,
data: nonconstant [ leadingTerm: [ exponent: termDegree,
coefficient: outTermCoefficient ],
reductum: ZeroPoly ]
] ];
IF previousTerm # ZeroPoly THEN {
WITH previousTerm SELECT FROM
previousTermVariant: REF PolynomialRec.nonconstant => {
previousTermVariant.reductum _ outTerm;
previousTerm _ outTerm;
};
ENDCASE => ERROR;
}
ELSE out _ previousTerm _ outTerm;
ENDLOOP;
};

DPolyFromPoly: PUBLIC PROC [in: Polynomial, V: VariableList] RETURNS [out: DPolynomial] ~ {
numVars: CARDINAL = NumVars[V];  -- we need V arg to get this number
inTermDegree: CARDINAL; -- degree in main variable of current (input) term
inTermDPolynomial: DPolynomial;
IF in = ZeroPoly THEN RETURN[ZeroDPoly];
IF numVars#in.numVars THEN ERROR; -- consistency check
WITH in SELECT FROM
input: REF PolynomialRec.constant => RETURN[ LIST[ [input.value, NIL] ] ];
input: REF PolynomialRec.nonconstant => {
out _ ZeroDPoly;
WHILE input # ZeroPoly DO
inTermDegree _ input.leadingTerm.exponent;
inTermDPolynomial _ DPolyFromPoly[input.leadingTerm.coefficient, VLRemoveMainVariable[V] ];
WHILE inTermDPolynomial#NIL DO
out _ CONS[ [ inTermDPolynomial.first.coefficient, DVAddMainVariablePower[inTermDPolynomial.first.degreeVector, numVars, inTermDegree] ], out];
inTermDPolynomial _ inTermDPolynomial.rest;
ENDLOOP;
input _ NARROW[ input.reductum ];
ENDLOOP;
out _  DPReverse[out];
};
ENDCASE;
};



ReadPolynomial: PUBLIC PROC [in: IO.STREAM, V: VariableList] RETURNS [poly: Polynomial] = {
RETURN[ PolyFromDPoly[ ReadDPolynomial[in, V], V ] ];
};

PolynomialFromRope: PUBLIC PROC [in: Rope.ROPE, V: VariableList] RETURNS [out: Polynomial] = {
stream: IO.STREAM _ IO.RIS[in];
out _ ReadPolynomial[stream, V];
};

PolynomialSAC2RepToRope: PUBLIC PROC [in: Polynomial] RETURNS [out: Rope.ROPE] = {
IF in = ZeroPoly THEN RETURN[ "()"];
WITH in SELECT FROM
input: REF PolynomialRec.constant => 
RETURN[ RN.RatNumToRatRope[input.value, FALSE, TRUE] ]; -- show denom of 1
input: REF PolynomialRec.nonconstant => {
out _ "( ";
WHILE input # ZeroPoly DO
out _ Rope.Cat[ out,
Convert.RopeFromCard[input.leadingTerm.exponent],
", ", 
PolynomialSAC2RepToRope[ input.leadingTerm.coefficient]
];
input _ NARROW[ input.reductum ];
IF input # ZeroPoly THEN out _ Rope.Concat[ out, ", " ];
ENDLOOP;
RETURN[ Rope.Concat[ out, " )" ] ];
};
ENDCASE;
};

PolynomialToRope: PUBLIC PROC [in: Polynomial, V: VariableList] RETURNS [out: Rope.ROPE] = {
numVars: CARDINAL = NumVars[V];  -- we need V arg to get this number
IF in = ZeroPoly THEN RETURN["0"];
WITH in SELECT FROM
input: REF PolynomialRec.constant => { 
out _ "";
RETURN[ Rope.Concat[ out, RN.RatNumToRatRope[input.value] ] ];
};
input: REF PolynomialRec.nonconstant => {
out _ "( ";
WHILE input # ZeroPoly DO
out _ Rope.Cat[ out,
PolynomialToRope[ input.leadingTerm.coefficient, VLRemoveMainVariable[V]],
" ",
Variable[V, numVars],
Rope.Cat["^", Convert.RopeFromCard[input.leadingTerm.exponent] ]
];
input _ NARROW[ input.reductum ];
IF input # ZeroPoly THEN out _ Rope.Concat[ out, " + " ];
ENDLOOP;
RETURN[ Rope.Concat[ out, " )" ] ];
};
ENDCASE;
};
WritePolynomial: PUBLIC PROC [in: Polynomial, V: VariableList, out: IO.STREAM] = {
polyRope: Rope.ROPE _ PolynomialToRope[in, V];
out.PutF["\n %g \n", IO.rope[polyRope] ];
};
VariableIndex: PROC [var: Rope.ROPE, V: VariableList ] RETURNS [index: CARDINAL] ~ {
v: Rope.ROPE;
index _ 1;
WHILE V#NIL DO
v _ V.first;  V_ V.rest;
IF Rope.Equal[var, v] THEN RETURN;
index _ index+1;
ENDLOOP;
index _ 0;
};

Variable: PROC [V: VariableList, index: CARDINAL] RETURNS [var: Rope.ROPE] ~ {
FOR i: CARDINAL IN [1..index-1] DO V _ V.rest;  ENDLOOP;
RETURN[ V.first ]; 
};

VLRemoveMainVariable: PROC [V: VariableList] RETURNS [VariableList] ~ {
RETURN[VLReverse[ VLReverse[V].rest ] ];
};

NumVars: PROC [V: VariableList] RETURNS [r: CARDINAL] ~ {
r _ 0;  WHILE V#NIL DO
r _ r+1;  V _ V.rest;
ENDLOOP;
};

Letter: PROC [C: CHAR] RETURNS [BOOL] ~ INLINE {
RETURN[ (0 <= C - 'A AND C - 'A < 26) OR (0 <= C - 'a AND C - 'a < 26)];
};

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

DVInsertVariablePower: 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: 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: 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: 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: PROC [in: DegreeVector, varIndex, exponent: CARDINAL] RETURNS [out: DegreeVector] ~ {
IF exponent>0 THEN RETURN[ CONS[varIndex, CONS[ exponent, in] ] ] ELSE RETURN[in];
};

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

DVNconc: 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: 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

DPInsertTerm: PROC [coefficient: RN.RatNum, degreeVec: DegreeVector, inPoly: DPolynomial] RETURNS [ok: BOOL, outPoly: DPolynomial] ~ {
nextCoeff: RN.RatNum;
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: 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


END.
κPolynomialsImpl.mesa
Last Edited by: Arnon, June 10, 1985 4:19:22 pm PDT
BigCardinals,
***** Arithmetic *****
***** Constructors *****
Construct Polynomial representation for zero



***** Conversion and I/O - Public Routines *****

Variable Lists
Write in a reasonable format

Distributed Polynomials

Recursive Polynomials
Dump the internal representation in SAC2 list format
Write in a reasonable form
IF RN.RatNumPositive[input.value] THEN out _ " + " ELSE out _ "";

Write in a reasonable format



***** Conversion and I/O - Private Routines *****

Variable Lists
Length of V

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.

Distributed Polynomials
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.
Κ˜Jš
œ™J™3J˜š
Οk	˜	Jš
œ˜Jšœœ˜Jšœ
˜J™
J˜J˜—J˜šœœ
˜Jšœ˜#Jšœ˜—Jšœ
œ
œ˜$J˜J™J˜šΟn
œœ
œœ˜OJš
œ+˜+Jšœœ
˜Jšœœ
œ˜$Jšœœ
œ˜$Jšœœ
œ
˜(šœœ
˜šœœ˜'šœœ
˜šœœ˜'Jšœœ
œ'˜:Jšœ
œœ
œ
˜"šœœ˜Jš
œ˜Jš
œ˜J˜—Jšœ
˜J˜—Jšœœ
˜—J˜—šœœ˜*šœœ
˜šœœ˜*Jš
œ!˜!šœœ˜0Jšœœ
˜
codešœ˜'š
œ"˜"šœ
œ˜Jš
œ˜Jš
œF˜FJ˜—Jšœ	œ˜#J˜—š
œ"˜"šœ
œ˜Jš
œ˜Jš
œH˜HJ˜—Jšœ	œ˜#J˜—š
œ"˜"š
œ"˜"Jš
œ˜š
œ˜Jš
œ˜——šœ˜šœ
œ˜Jš
œ˜š
œI˜IJš
œ˜Jš
œ˜—J˜——š
˜Jšœœ
˜—Jšœ	œ˜#Jšœ	œ˜#J˜—Kšœ
˜—šœœœ˜6šœœ
˜ šœœ˜:Kš
œ*˜*Kš
œ˜K˜—Kšœœ
˜—K˜
Kšœ!˜%—Kšœ
˜—Kšœœœ˜;š	œœ
œœ
˜7KšœœE˜`Kšœ˜—Kšœ˜K˜—Kšœœ
˜—Kš
œ˜—Kšœ
˜—K˜J˜—šžœœ
œœ˜LJš
œ%˜%Jšœœ
œ˜'šœœ
˜šœœ˜&šœœ˜Jš
œ˜Jšœœ˜4J˜—Jšœ
˜J˜—šœœ˜)Jš
œ˜šœ˜šœ
œ˜Jš
œ˜š
œ ˜ Jš
œ%˜%Jšœžœ˜<Jš
œ˜Jš
œ˜—J˜—Jšœœ˜ šœœ˜$šœœ
˜ šœœ˜:Kš
œ*˜*Kš
œ˜K˜—Kšœœ
˜—K˜
Kšœ!˜%—Jšœ
˜—J˜—Jšœ
˜—K˜J˜—šžœœ
œœ˜OJšœ1˜7J˜J˜—šžœœ
œœ˜TJš
œ?˜?Jšœœœ
œ˜:Jšœœ
œ
˜(šœœ
˜šœœ˜'šœœ
˜šœœ˜'Jšœœ
œ,˜?šœœ˜Jš
œ˜Jš
œ˜J˜—Jšœ
˜J˜—Jšœœ
˜—J˜—šœœ˜*šœœ
˜šœœ˜*Jšœœ˜-Jš
œ˜šœ˜Jš
œ"˜"Jš
œ˜šœ˜!š
œ'˜'Jš
œ&˜&š
œ˜Jš
œ˜——šœœ˜&Jš
œ˜š
œ"˜"Jš
œK˜KJš
œ˜Jš
œ˜—J˜—šœ#˜)šœœ
˜'šœœ˜AKš
œ8˜8Kš
œ(˜(K˜—Kšœ˜——Kšœ6˜:Jšœœ˜1Jšœ
˜—Jš
œ%˜%Jšœ	œ˜#Jšœ
˜—J˜—Kšœ˜—Kš
œ˜—Kšœ
˜—K˜J˜—J˜J˜J™J˜šžœœ
œ	œœœ˜_šœœ˜Jš
œ˜š
œ1˜1šœ
œ˜#Jš
œ˜Jš
œ˜Jš
œ˜—Jš
œ˜—J˜—J˜J˜—š
žœœ
œœœ˜bšœœ˜Jš
œ˜š
œ1˜1Jš
œ˜Jš
œ˜—J˜—J˜J˜—šžœœ
œ
œ#˜JJš
œ,™,—J™™J™—J™0J™J™šžœœ
œœ
œœ˜KJšœ
œ
˜Kšœœ
˜Jš	œœ
œœœ
˜@Jš
œ˜Jšœœ
˜Jš
œ˜Jš
œ˜Jš
œ˜Jšœœ ˜5šœ˜Jšœœ˜Jš
œ˜š	œœ
œœ˜)Jšœœ'˜1—Jš
œ˜Jš
œ˜Jšœœ
œœ˜GKšœ
˜—K˜J˜—š
žœœ
œœœ˜MKš	œ
œ
œœ
œ˜!Kšœ!˜'K˜J˜—š
žœœ
œœœ˜Lšœœœ
˜Jš
œ"˜"J˜Jšœœ
œ˜,Jšœ
˜—Jš
œ˜K˜K˜—š
žœœ
œœ
œ˜D™Jšœ
œ˜*Jšœœ˜'J˜——J™š
œ™J™—šžœœ
œœ
œœ˜]Jšœœ
˜Jšœœ˜Jšœœ
˜Jšœ
œ
˜J˜Jšœœ
˜Jšœ
œ
˜Jš	œœ
œœœ
˜@Jšœœ
˜#Jšœœ
˜	Jšœœ
˜Jš
œ˜šœœ˜JšœΟc
˜Jš
œ˜Jšœœœœ"˜\J˜—šœŸ$˜(Jšœœ
˜JšœŸ˜Jšœœ˜'Jšœœ
˜Jš
œ˜šœœ˜J˜
JšœŸ
˜Jš
œ˜J˜
—šœ
œœ˜!JšœŸ
˜Jš
œ˜J˜—šœ˜šœŸ ˜2Kšœœ
˜Kšœœ˜ Jš
œ˜Kšœ
œœ˜+Kšœ
œœ˜:K˜—Kšœ
˜—Kšœ
œ
œŸC˜všœœ
Ÿ˜>Kšœœ
˜Kš
œ
˜
Kš
œ˜Jš
œ˜Kš
œ&˜&Kšœœ˜2šœœœŸ˜KJš
œ˜šœœ˜Jš
œ˜Jšœœ%˜?J˜—Jš
œ˜šœ˜šœ˜Kš
œ˜Jš
œ˜Kšœœ˜/K˜—Kšœ#˜*—K˜—Kš
œG˜GKšœ
œœ˜-JšœŸ˜—šœœŸ2˜OKš
œ2˜2Kšœ
œœ˜-J˜
—Jšœ"˜&Jšœœ
œ
˜"Jšœ
˜—J˜J˜—šžœœœœ˜`Kš	œœ
œœ
œ˜Kš
œ!˜!K˜K˜—š
žœœ
œ$œœ˜\Jšœœ
œ˜0Jšœœœ
˜Jšœœ
˜Jšœœ˜Jš
œ˜Jšœœ˜Jšœœ
˜Jšœœ
œ˜%J˜	šœœ
˜Jš
œ-˜-Jš
œ˜Jšœœ˜Jšœœ
œœ
œ
œœ˜nJšœœ
˜Jš
œ
œ
œœœ!˜aJšœœ
˜Jš
œ!˜!šœœ
˜Jšœœ
˜Jš
œ8˜8Jš
œ5˜5Jš
œ,˜,Jšœœ:˜LJš
œ˜Jšœ
˜—Jš
œœ
œœœ!˜qJšœ
˜—Jš
œ˜J˜J˜—š
žœœ
œ)œ
œ˜TJšœœ˜/Jšœœ˜)J˜J˜—šž
œœ
œ$œ˜[Kšœ	œŸ#˜DJšœœŸ3˜IJšœ#Ÿ+˜NJšœ Ÿ.˜NKšœŸ˜-Kš
œ˜Jšœœ
œ˜(šœœ˜šœœ˜Jš
œ˜Jš
œ+˜+J˜—Jšœ
˜J˜—J˜šœœ
˜Jšœ7Ÿ˜QJšœœW˜qJ˜
šœœ
œ7˜IJšœœk˜…
J˜
Jšœ
˜—Jš
œ7˜7Jš
œS˜Sšœ
œ˜Jš
œ˜š
œ8˜8Jš
œ"˜"Jš
œ˜—J˜—šœœ˜!šœœ
˜šœœ˜7Kš
œ'˜'Kš
œ˜K˜—Kšœœ
˜—K˜
—Kšœ˜"Kšœ
˜—K˜J˜—šž
œœ#œ˜[Kšœ	œŸ#˜DJšœœŸ2˜JJš
œ˜Jšœœ
œ˜(Kšœœ
œŸ˜6šœœ
˜Jš	œœœœœ˜Jšœœ˜)J˜šœ˜Kš
œ*˜*Jš
œ[˜[šœœ
˜Jšœœ…
˜
Jš
œ+˜+Jšœ
˜—Jšœœ˜!Jšœ
˜—Jš
œ˜J˜—Jšœ
˜—K˜K˜—K˜š
Ÿ™K˜—šžœœ
œœ
œœ˜[Jšœ/˜5J˜K˜—š
žœœ
œœœ˜^Kš	œœ
œœ
œ˜Kš
œ ˜ K˜K˜—š
žœœ
œœœ˜RJ™4Jšœœ
œ˜$šœœ
˜šœœ˜%Jš	œœœœŸ˜J—šœœ˜)J˜šœ˜š
œ˜Kš
œ1˜1Kš
œ˜Kš
œ7˜7K˜—Kšœœ˜!Kšœœ ˜8Kšœ
˜—Kšœ˜#K˜—Kšœ
˜—K˜K˜—š
žœœ
œ#œœ˜\J™Kšœ	œŸ#˜DJšœœ
œ˜"šœœ
˜šœœ˜'Jšœ
œœ
œ
™AJ˜	Jšœœ"˜>J˜—šœœ˜)J˜šœ˜š
œ˜Kš
œJ˜JKš
œ˜Kš
œ˜Kš
œ@˜@K˜—Kšœœ˜!Kšœœ!˜9Kšœ
˜—Kšœ˜#K˜—Kšœ
˜—K˜J™—šžœœ(œ
œ˜R™Jšœœ˜.Jšœœ˜)J˜—J™—J™J™J™1J™J™š
ž
œœœœ	œ˜TKšœœ
˜
K˜
šœœ
˜K˜Kšœœ
œ
˜"K˜Kšœ
˜—K˜
K˜K˜—š
žœœœœœ˜NJš
œœ
œœœ
˜8Jšœ
˜K˜K˜—šžœœœ˜GKšœ"˜(K˜K˜—šžœœœœ˜9Kš
œ™šœœœ
˜K˜Kšœ
˜—K˜K˜—šžœœœœœœ˜0Kšœœœœ˜HK˜J˜—šž	œœœ˜CKšœœ
˜
šœœ
˜Kšœœ˜K˜Kšœ
˜—Kšœ˜KšœŸ
˜K˜—K™Kš
œ™š
žœœœœœ!˜ˆ
Kš
œ­™­Kš
œ+™+Kšœœ
˜"Kš
œ&˜&Kš
œ˜Kšœœ
˜
šœ
œ
œ˜šœœ
œ
œ˜ Kšœ
œœœ˜3Kš
˜K˜
—K˜—Kš
œ9˜9Kš
œ<˜<šœ
˜Kšœœœ˜'š	œœœ
œ
œ˜/Kšœ
œœ˜;Kš
˜Kš
œ˜—Kšœ˜	—Kšœœœœ˜8šœœ
˜Kš
œ9˜9Kš
œ<˜<šœ
˜Kšœ1œœ˜Bšœœ˜!Kšœœ˜&Kšœ˜Kš
œQ˜QKš
œ'˜'Kš
œ0˜0Kš
˜Kš
œ˜—Kšœ˜	—Kšœœœ˜AKšœ
˜—Kšœœœ˜<Kš
œ'˜'K˜K˜—šž	œœœ˜@Kšœ&œ
˜/š	œœ
œœ
˜Kš
œ$˜$Kš
œ'˜'Kš
œ$˜$Kš
œ'˜'Kšœœ
œ˜"Kšœœ
œ˜#Kšœœ
œ˜(Kšœœ
œ˜)Kšœ
˜—Kšœœ
œ
œ˜Kšœœ
œ
œ˜Kšœ˜
K˜K˜—š
žœœ$œœ
œ˜ZKšœ
œ
œ
œ˜"Kš
œœ
œœ
œ˜NK˜K˜—šžœœœœ˜eKš
œœ
œ
œ
œ˜Kš
œœ
œœ
œ˜AK˜K˜—šžœœ(œœ˜mKšœœ
œœœœ
œ˜RK˜K˜—š
žœœœœœ˜cKš
œœœœœ˜<K˜K˜—šžœœœ˜?Kš
œ˜Kšœœ
œ
œ˜šœ
œ
˜Kš
œ˜Kšœ
˜—K˜Kšœ˜Kš
œ˜K˜—šž	œœœ˜CKšœœ
˜
šœœ
˜Kšœœ˜K˜Kšœ
˜—Kšœ˜KšœŸ
˜K˜—K™Kš
œ™šžœœœ7œ%˜†
Kš
œχ
™χ
Kš
œ"™"Kšœœ˜Kš
œ˜Kš
œ˜K˜Kšœœ
˜
šœœ
œ˜Kšœœœ˜.Kš
˜K˜—Kš
œ˜Kš
œ;˜;Kš
œ:˜:šœ˜Kšœœœ˜š
œ˜Kšœœ%˜1Kš
˜Kš
œ˜—Kšœ˜	—Kšœ
œœ˜1šœœ
˜Kš
œ;˜;Kš
œ:˜:šœ˜Kšœœœ˜/š
œ˜Kšœ
œœ'˜WKš
œ˜Kš
œ!˜!Kš
˜Kš
œ˜—Kšœ˜	—Kšœ
œ'˜5Kšœ
˜—Kšœ
œ%˜3Kš
œ˜K˜K˜—šžœœœ˜=Kš
œ˜Kšœœ
œ
œ˜šœ
œ
˜Kš
œ˜Kšœ
˜—K˜Kšœ˜Kš
œ˜K˜—šž	œœœ˜AKšœœ
˜
šœœ
˜Kšœœ˜K˜Kšœ
˜—Kšœ˜KšœŸ
˜—J˜J˜Jšœ
˜—…—RΚt5