<> <> DIRECTORY Rope, Convert USING [RopeFromCard], IO, <> RatNums, Polynomials; PolynomialsImpl: CEDAR PROGRAM IMPORTS Rope, Convert, IO, RatNums EXPORTS Polynomials = BEGIN OPEN RN: RatNums, Polynomials; <<***** Arithmetic *****>> 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; }; <<***** Constructors *****>> 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] = {}; <> <<>> <<>> <<>> <<***** Conversion and I/O - Public Routines *****>> <<>> <> 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] ]; }; <<>> <<>> <<>> <<***** Conversion and I/O - Private Routines *****>> <<>> <> 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.