001/*
002 * $Id$
003 */
004
005package edu.jas.fd;
006
007
008import java.util.Arrays;
009
010import org.apache.logging.log4j.LogManager;
011import org.apache.logging.log4j.Logger;
012
013import edu.jas.kern.PrettyPrint;
014import edu.jas.poly.ExpVector;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenSolvablePolynomial;
017import edu.jas.gbufd.PolyModUtil;
018import edu.jas.structure.GcdRingElem;
019import edu.jas.structure.QuotPair;
020
021
022/**
023 * SolvableQuotient, that is a (left) rational function, based on
024 * GenSolvablePolynomial with RingElem interface. Objects of this class are
025 * immutable.
026 * @author Heinz Kredel
027 */
028public class SolvableQuotient<C extends GcdRingElem<C>>
029                implements GcdRingElem<SolvableQuotient<C>>, QuotPair<GenPolynomial<C>> {
030    // should be QuotPair<GenSolvablePolynomial<C>
031
032
033    private static final Logger logger = LogManager.getLogger(SolvableQuotient.class);
034
035
036    private static final boolean debug = logger.isDebugEnabled();
037
038
039    /**
040     * SolvableQuotient class factory data structure.
041     */
042    public final SolvableQuotientRing<C> ring;
043
044
045    /**
046     * Numerator part of the element data structure.
047     */
048    public final GenSolvablePolynomial<C> num;
049
050
051    /**
052     * Denominator part of the element data structure.
053     */
054    public final GenSolvablePolynomial<C> den;
055
056
057    /**
058     * The constructor creates a SolvableQuotient object from a ring factory.
059     * @param r ring factory.
060     */
061    public SolvableQuotient(SolvableQuotientRing<C> r) {
062        this(r, r.ring.getZERO());
063    }
064
065
066    /**
067     * The constructor creates a SolvableQuotient object from a ring factory and
068     * a numerator polynomial. The denominator is assumed to be 1.
069     * @param r ring factory.
070     * @param n numerator solvable polynomial.
071     */
072    public SolvableQuotient(SolvableQuotientRing<C> r, GenSolvablePolynomial<C> n) {
073        this(r, n, r.ring.getONE(), true);
074    }
075
076
077    /**
078     * The constructor creates a SolvableQuotient object from a ring factory and
079     * a numerator and denominator solvable polynomial.
080     * @param r ring factory.
081     * @param n numerator polynomial.
082     * @param d denominator polynomial.
083     */
084    public SolvableQuotient(SolvableQuotientRing<C> r, GenSolvablePolynomial<C> n,
085                    GenSolvablePolynomial<C> d) {
086        this(r, n, d, false);
087    }
088
089
090    /**
091     * The constructor creates a SolvableQuotient object from a ring factory and
092     * a numerator and denominator polynomial.
093     * @param r ring factory.
094     * @param n numerator polynomial.
095     * @param d denominator polynomial.
096     * @param isred <em>unused at the moment</em>.
097     */
098    protected SolvableQuotient(SolvableQuotientRing<C> r, GenSolvablePolynomial<C> n,
099                    GenSolvablePolynomial<C> d, boolean isred) {
100        if (d == null || d.isZERO()) {
101            throw new IllegalArgumentException("denominator may not be zero");
102        }
103        ring = r;
104        if (d.signum() < 0) {
105            n = (GenSolvablePolynomial<C>) n.negate();
106            d = (GenSolvablePolynomial<C>) d.negate();
107        }
108        if (isred) {
109            num = n;
110            den = d;
111            return;
112        }
113        C lc = d.leadingBaseCoefficient();
114        if (!lc.isONE() && lc.isUnit()) {
115            lc = lc.inverse();
116            n = n.multiply(lc);
117            d = d.multiply(lc);
118        }
119        if (n.compareTo(d) == 0) {
120            num = ring.ring.getONE();
121            den = ring.ring.getONE();
122            return;
123        }
124        if (n.negate().compareTo(d) == 0) {
125            num = (GenSolvablePolynomial<C>) ring.ring.getONE().negate();
126            den = ring.ring.getONE();
127            return;
128        }
129        if (n.isZERO()) {
130            num = n;
131            den = ring.ring.getONE();
132            return;
133        }
134        //if (n.isONE() || d.isONE()) {
135        if (n.isConstant() || d.isConstant()) {
136            num = n;
137            den = d;
138            return;
139        }
140        // must reduce to lowest terms
141        // not perfect, TODO 
142        //GenSolvablePolynomial<C>[] gcd = PolyModUtil.<C> syzGcdCofactors(r.ring, n, d);
143        //GenSolvablePolynomial<C>[] gcd = FDUtil.<C> leftGcdCofactors(r.ring, n, d);
144        GenSolvablePolynomial<C>[] gcd = ring.fdengine.leftGcdCofactors(r.ring, n, d);
145        if (!gcd[0].isONE()) {
146            logger.info("constructor: gcd = {}", Arrays.toString(gcd)); // + ", {}", n + ", " +d);
147            n = gcd[1];
148            d = gcd[2];
149        }
150        //gcd = PolyModUtil.<C> syzGcdCofactors(r.ring, n, d);
151        //gcd = FDUtil.<C> rightGcdCofactors(r.ring, n, d);
152        gcd = ring.fdengine.rightGcdCofactors(r.ring, n, d);
153        if (!gcd[0].isONE()) {
154            logger.info("constructor: gcd = {}", Arrays.toString(gcd)); // + ", {}", n + ", " +d);
155            n = gcd[1];
156            d = gcd[2];
157        }
158        // not perfect, TODO 
159        GenSolvablePolynomial<C>[] simp = ring.engine.leftSimplifier(n, d);
160        logger.info("simp: {}, {}, {}", Arrays.toString(simp), n, d);
161        num = simp[0];
162        den = simp[1];
163    }
164
165
166    /**
167     * Get the corresponding element factory.
168     * @return factory for this Element.
169     * @see edu.jas.structure.Element#factory()
170     */
171    public SolvableQuotientRing<C> factory() {
172        return ring;
173    }
174
175
176    /**
177     * Numerator.
178     * @see edu.jas.structure.QuotPair#numerator()
179     */
180    public GenSolvablePolynomial<C> numerator() {
181        return num;
182    }
183
184
185    /**
186     * Denominator.
187     * @see edu.jas.structure.QuotPair#denominator()
188     */
189    public GenSolvablePolynomial<C> denominator() {
190        return den;
191    }
192
193
194    /**
195     * Clone this.
196     * @see java.lang.Object#clone()
197     */
198    @Override
199    public SolvableQuotient<C> copy() {
200        return new SolvableQuotient<C>(ring, num, den, true);
201    }
202
203
204    /**
205     * Is SolvableQuotient zero.
206     * @return If this is 0 then true is returned, else false.
207     * @see edu.jas.structure.RingElem#isZERO()
208     */
209    public boolean isZERO() {
210        return num.isZERO();
211    }
212
213
214    /**
215     * Is SolvableQuotient one.
216     * @return If this is 1 then true is returned, else false.
217     * @see edu.jas.structure.RingElem#isONE()
218     */
219    public boolean isONE() {
220        return num.compareTo(den) == 0;
221    }
222
223
224    /**
225     * Is SolvableQuotient a unit.
226     * @return If this is a unit then true is returned, else false.
227     * @see edu.jas.structure.RingElem#isUnit()
228     */
229    public boolean isUnit() {
230        if (num.isZERO()) {
231            return false;
232        }
233        return true;
234    }
235
236
237    /**
238     * Is Qoutient a constant.
239     * @return true, if this has constant numerator and denominator, else false.
240     */
241    public boolean isConstant() {
242        return num.isConstant() && den.isConstant();
243    }
244
245
246    /**
247     * Get the String representation as RingElem.
248     * @see java.lang.Object#toString()
249     */
250    @Override
251    public String toString() {
252        if (PrettyPrint.isTrue()) {
253            String s = "{ " + num.toString(ring.ring.getVars());
254            if (!den.isONE()) {
255                s += " | " + den.toString(ring.ring.getVars());
256            }
257            return s + " }";
258        }
259        return "SolvableQuotient[ " + num.toString() + " | " + den.toString() + " ]";
260    }
261
262
263    /**
264     * Get a scripting compatible string representation.
265     * @return script compatible representation for this Element.
266     * @see edu.jas.structure.Element#toScript()
267     */
268    @Override
269    public String toScript() {
270        // any scripting case
271        if (den.isONE()) {
272            return num.toScript();
273        }
274        return num.toScript() + " / " + den.toScript();
275    }
276
277
278    /**
279     * Get a scripting compatible string representation of the factory.
280     * @return script compatible representation for this ElemFactory.
281     * @see edu.jas.structure.Element#toScriptFactory()
282     */
283    @Override
284    public String toScriptFactory() {
285        return factory().toScript();
286    }
287
288
289    /**
290     * SolvableQuotient comparison.
291     * @param b SolvableQuotient.
292     * @return sign(this-b).
293     */
294    @Override
295    public int compareTo(SolvableQuotient<C> b) {
296        if (b == null || b.isZERO()) {
297            return this.signum();
298        }
299        if (this.isZERO()) {
300            return -b.signum();
301        }
302        // assume sign(den,b.den) > 0
303        int s1 = num.signum();
304        int s2 = b.num.signum();
305        int t = (s1 - s2) / 2;
306        if (t != 0) {
307            return t;
308        }
309        if (den.compareTo(b.den) == 0) {
310            return num.compareTo(b.num);
311        }
312        GenSolvablePolynomial<C> r, s;
313        // if (den.isONE()) {
314        //     r = b.den.multiply(num);
315        //     s = b.num;
316        //     return r.compareTo(s);
317        // }
318        // if (b.den.isONE()) {
319        //     r = num;
320        //     s = den.multiply(b.num);
321        //     return r.compareTo(s);
322        // }
323        GenSolvablePolynomial<C>[] oc = ring.engine.leftOreCond(den, b.den);
324        if (debug) {
325            System.out.println("oc[0] den =<>= oc[1] b.den: (" + oc[0] + ") (" + den + ") = (" + oc[1] + ") ("
326                            + b.den + ")");
327        }
328        r = oc[0].multiply(num);
329        s = oc[1].multiply(b.num);
330        //System.out.println("r = " + r);
331        //System.out.println("s = " + s);
332        return r.compareTo(s);
333    }
334
335
336    /**
337     * Comparison with any other object.
338     * @see java.lang.Object#equals(java.lang.Object)
339     */
340    @SuppressWarnings("unchecked")
341    @Override
342    public boolean equals(Object b) {
343        if (b == null) {
344            return false;
345        }
346        if (!(b instanceof SolvableQuotient)) {
347            return false;
348        }
349        SolvableQuotient<C> a = (SolvableQuotient<C>) b;
350        if (num.equals(a.num) && den.equals(a.den)) { // short cut
351            return true;
352        }
353        return compareTo(a) == 0;
354    }
355
356
357    /**
358     * Hash code for this element.
359     * @see java.lang.Object#hashCode()
360     */
361    @Override
362    public int hashCode() {
363        int h;
364        h = ring.hashCode();
365        h = 37 * h + num.hashCode();
366        h = 37 * h + den.hashCode();
367        return h;
368    }
369
370
371    /**
372     * SolvableQuotient right fraction. <b>Note:</b> It is not possible to
373     * distinguish right from left fractions in the current implementation. So
374     * it is not possible to compute with right fractions.
375     * @return SolvableQuotient(a,b), where den<sup>-1</sup> num = a b
376     *         <sup>-1</sup>
377     */
378    public SolvableQuotient<C> rightFraction() {
379        if (isZERO() || isONE()) {
380            return this;
381        }
382        GenSolvablePolynomial<C>[] oc = ring.engine.rightOreCond(num, den);
383        return new SolvableQuotient<C>(ring, oc[1], oc[0], true); // reversed, true is wrong but okay
384    }
385
386
387    /**
388     * Test if SolvableQuotient right fraction. <b>Note:</b> It is not possible
389     * to distinguish right from left fractions in the current implementation.
390     * So it is not possible to compute with right fractions.
391     * @param s = SolvableQuotient(a,b)
392     * @return true if s is a right fraction of this, i.e. den<sup>-1</sup> num
393     *         = a b<sup>-1</sup>
394     */
395    public boolean isRightFraction(SolvableQuotient<C> s) {
396        if (isZERO()) {
397            return s.isZERO();
398        }
399        if (isONE()) {
400            return s.isONE();
401        }
402        GenSolvablePolynomial<C> x = den.multiply(s.num);
403        GenSolvablePolynomial<C> y = num.multiply(s.den);
404        return x.compareTo(y) == 0;
405    }
406
407
408    /**
409     * SolvableQuotient absolute value.
410     * @return the absolute value of this.
411     * @see edu.jas.structure.RingElem#abs()
412     */
413    public SolvableQuotient<C> abs() {
414        return new SolvableQuotient<C>(ring, (GenSolvablePolynomial<C>) num.abs(), den, true);
415    }
416
417
418    /**
419     * SolvableQuotient summation.
420     * @param S SolvableQuotient.
421     * @return this+S.
422     */
423    public SolvableQuotient<C> sum(SolvableQuotient<C> S) {
424        if (S == null || S.isZERO()) {
425            return this;
426        }
427        if (this.isZERO()) {
428            return S;
429        }
430        GenSolvablePolynomial<C> n, d, n1, n2;
431        if (den.isONE() && S.den.isONE()) {
432            n = (GenSolvablePolynomial<C>) num.sum(S.num);
433            return new SolvableQuotient<C>(ring, n, den, true);
434        }
435        /* wrong:
436        if (den.isONE()) {
437            n = S.den.multiply(num);
438            n = (GenSolvablePolynomial<C>) n.sum(S.num);
439            return new SolvableQuotient<C>(ring, n, S.den, false);
440        }
441        if (S.den.isONE()) {
442            n = den.multiply(S.num);
443            n = (GenSolvablePolynomial<C>) n.sum(num);
444            return new SolvableQuotient<C>(ring, n, den, false);
445        }
446        */
447        if (den.compareTo(S.den) == 0) { // correct ?
448            //d = den.multiply(den);
449            //n1 = den.multiply(S.num);
450            //n2 = S.den.multiply(num);
451            n = (GenSolvablePolynomial<C>) num.sum(S.num);
452            return new SolvableQuotient<C>(ring, n, den, false);
453        }
454        // general case
455        GenSolvablePolynomial<C>[] oc = ring.engine.leftOreCond(den, S.den);
456        if (debug) {
457            System.out.println("oc[0] den =sum= oc[1] S.den: (" + oc[0] + ") (" + den + ") = (" + oc[1]
458                            + ") (" + S.den + ")");
459        }
460        d = oc[0].multiply(den);
461        n1 = oc[0].multiply(num);
462        n2 = oc[1].multiply(S.num);
463        n = (GenSolvablePolynomial<C>) n1.sum(n2);
464        //System.out.println("n = " + n);
465        //System.out.println("d = " + d);
466        return new SolvableQuotient<C>(ring, n, d, false);
467    }
468
469
470    /**
471     * SolvableQuotient negate.
472     * @return -this.
473     * @see edu.jas.structure.RingElem#negate()
474     */
475    public SolvableQuotient<C> negate() {
476        return new SolvableQuotient<C>(ring, (GenSolvablePolynomial<C>) num.negate(), den, true);
477    }
478
479
480    /**
481     * SolvableQuotient signum.
482     * @see edu.jas.structure.RingElem#signum()
483     * @return signum(this).
484     */
485    public int signum() {
486        // assume sign(den) > 0
487        return num.signum();
488    }
489
490
491    /**
492     * SolvableQuotient subtraction.
493     * @param S SolvableQuotient.
494     * @return this-S.
495     */
496    public SolvableQuotient<C> subtract(SolvableQuotient<C> S) {
497        return sum(S.negate());
498    }
499
500
501    /**
502     * SolvableQuotient division.
503     * @param S SolvableQuotient.
504     * @return this/S.
505     */
506    public SolvableQuotient<C> divide(SolvableQuotient<C> S) {
507        return multiply(S.inverse());
508    }
509
510
511    /**
512     * SolvableQuotient inverse.
513     * @see edu.jas.structure.RingElem#inverse()
514     * @return S with S = 1/this.
515     */
516    public SolvableQuotient<C> inverse() {
517        if (num.isZERO()) {
518            throw new ArithmeticException("element not invertible " + this);
519        }
520        return new SolvableQuotient<C>(ring, den, num, true);
521    }
522
523
524    /**
525     * SolvableQuotient remainder.
526     * @param S SolvableQuotient.
527     * @return this - (this/S)*S.
528     */
529    public SolvableQuotient<C> remainder(SolvableQuotient<C> S) {
530        if (S.isZERO()) {
531            throw new ArithmeticException("element not invertible " + S);
532        }
533        return ring.getZERO();
534    }
535
536
537    /**
538     * Quotient and remainder by division of this by S.
539     * @param S a SolvableQuotient
540     * @return [this/S, this - (this/S)*S].
541     */
542    @SuppressWarnings("unchecked")
543    public SolvableQuotient<C>[] quotientRemainder(SolvableQuotient<C> S) {
544        return new SolvableQuotient[] { divide(S), remainder(S) };
545    }
546
547
548    /**
549     * SolvableQuotient multiplication.
550     * @param S SolvableQuotient.
551     * @return this*S.
552     */
553    public SolvableQuotient<C> multiply(SolvableQuotient<C> S) {
554        if (S == null || S.isZERO()) {
555            return S;
556        }
557        if (num.isZERO()) {
558            return this;
559        }
560        if (S.isONE()) {
561            return this;
562        }
563        if (this.isONE()) {
564            return S;
565        }
566        GenSolvablePolynomial<C> n, d;
567        if (den.isONE() && S.den.isONE()) {
568            n = num.multiply(S.num);
569            return new SolvableQuotient<C>(ring, n, den, true);
570        }
571        /* wrong:
572        if (den.isONE()) { 
573            d = S.den;
574            n = num.multiply(S.num);
575            return new SolvableQuotient<C>(ring, n, d, false);
576        }
577        if (S.den.isONE()) { 
578            d = den;
579            n = num.multiply(S.num);
580            return new SolvableQuotient<C>(ring, n, d, false);
581        }
582        */
583        // if ( den.compareTo(S.den) == 0 ) { // not correct ?
584        //     d = den.multiply(den);
585        //     n = num.multiply(S.num);
586        //     return new SolvableQuotient<C>(ring, n, d, false);
587        // }
588        GenSolvablePolynomial<C>[] oc = ring.engine.leftOreCond(num, S.den);
589        n = oc[1].multiply(S.num);
590        d = oc[0].multiply(den);
591        if (debug) {
592            System.out.println("oc[0] num =mult= oc[1] S.den: (" + oc[0] + ") (" + num + ") = (" + oc[1]
593                            + ") (" + S.den + ")");
594        }
595        return new SolvableQuotient<C>(ring, n, d, false);
596    }
597
598
599    /**
600     * SolvableQuotient multiplication by GenSolvablePolynomial.
601     * @param b GenSolvablePolynomial<C>.
602     * @return this*b.
603     */
604    public SolvableQuotient<C> multiply(GenSolvablePolynomial<C> b) {
605        if (b == null || b.isZERO()) {
606            return ring.getZERO();
607        }
608        if (num.isZERO()) {
609            return this;
610        }
611        if (b.isONE()) {
612            return this;
613        }
614        GenSolvablePolynomial<C> n = num.multiply(b);
615        return new SolvableQuotient<C>(ring, n, den, false);
616    }
617
618
619    /**
620     * SolvableQuotient multiplication by coefficient.
621     * @param b coefficient.
622     * @return this*b.
623     */
624    public SolvableQuotient<C> multiply(C b) {
625        if (b == null || b.isZERO()) {
626            return ring.getZERO();
627        }
628        if (num.isZERO()) {
629            return this;
630        }
631        if (b.isONE()) {
632            return this;
633        }
634        GenSolvablePolynomial<C> n = num.multiply(b);
635        return new SolvableQuotient<C>(ring, n, den, true);
636    }
637
638
639    /**
640     * SolvableQuotient multiplication by exponent.
641     * @param e exponent vector.
642     * @return this*b.
643     */
644    public SolvableQuotient<C> multiply(ExpVector e) {
645        if (e == null || e.isZERO()) {
646            return this;
647        }
648        if (num.isZERO()) {
649            return this;
650        }
651        GenSolvablePolynomial<C> n = num.multiply(e);
652        return new SolvableQuotient<C>(ring, n, den, false);
653    }
654
655
656    /**
657     * SolvableQuotient monic.
658     * @return this with monic value part.
659     */
660    public SolvableQuotient<C> monic() {
661        if (num.isZERO()) {
662            return this;
663        }
664        C lbc = num.leadingBaseCoefficient();
665        if (!lbc.isUnit()) {
666            return this;
667        }
668        lbc = lbc.inverse();
669        //lbc = lbc.abs();
670        GenSolvablePolynomial<C> n = num.multiply(lbc);
671        //GenSolvablePolynomial<C> d = (GenSolvablePolynomial<C>) den.multiply(lbc);
672        return new SolvableQuotient<C>(ring, n, den, true);
673    }
674
675
676    /**
677     * Greatest common divisor.
678     * @param b other element.
679     * @return gcd(this,b).
680     */
681    public SolvableQuotient<C> gcd(SolvableQuotient<C> b) {
682        if (b == null || b.isZERO()) {
683            return this;
684        }
685        if (this.isZERO()) {
686            return b;
687        }
688        if (this.equals(b)) {
689            return this;
690        }
691        return ring.getONE();
692    }
693
694
695    /**
696     * Extended greatest common divisor.
697     * @param b other element.
698     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
699     */
700    @SuppressWarnings("unchecked")
701    public SolvableQuotient<C>[] egcd(SolvableQuotient<C> b) {
702        @SuppressWarnings("cast")
703        SolvableQuotient<C>[] ret = (SolvableQuotient<C>[]) new SolvableQuotient[3];
704        ret[0] = null;
705        ret[1] = null;
706        ret[2] = null;
707        if (b == null || b.isZERO()) {
708            ret[0] = this;
709            ret[1] = ring.getONE();
710            ret[2] = ring.getZERO();
711            return ret;
712        }
713        if (this.isZERO()) {
714            ret[0] = b;
715            ret[1] = ring.getZERO();
716            ret[2] = ring.getONE();
717            return ret;
718        }
719        GenSolvablePolynomial<C> two = ring.ring.fromInteger(2);
720        ret[0] = ring.getONE();
721        ret[1] = (this.multiply(two)).inverse();
722        ret[2] = (b.multiply(two)).inverse();
723        return ret;
724    }
725
726}