Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008import java.util.Iterator;
009import java.util.Map;
010import java.util.SortedMap;
011import java.util.TreeMap;
012
013import org.apache.logging.log4j.LogManager;
014import org.apache.logging.log4j.Logger;
015
016import edu.jas.structure.NotInvertibleException;
017import edu.jas.structure.RegularRingElem;
018import edu.jas.structure.RingElem;
019import edu.jas.structure.RingFactory;
020
021
022/**
023 * Direct product element based on RingElem. Objects of this class are (nearly)
024 * immutable.
025 * @author Heinz Kredel
026 */
027public class Product<C extends RingElem<C>> implements RegularRingElem<Product<C>> {
028
029
030    private static final Logger logger = LogManager.getLogger(Product.class);
031
032
033    //private static final boolean debug = logger.isDebugEnabled();
034
035
036    /**
037     * Product class factory data structure.
038     */
039    public final ProductRing<C> ring;
040
041
042    /**
043     * Value part of the element data structure.
044     */
045    public final SortedMap<Integer, C> val;
046
047
048    /**
049     * Flag to remember if this product element is a unit in each cmponent. -1
050     * is unknown, 1 is unit, 0 not a unit.
051     */
052    protected int isunit = -1; // initially unknown
053
054
055    /**
056     * The constructor creates a Product object from a ring factory.
057     * @param r ring factory.
058     */
059    public Product(ProductRing<C> r) {
060        this(r, new TreeMap<Integer, C>(), 0);
061    }
062
063
064    /**
065     * The constructor creates a Product object from a ring factory and a ring
066     * element.
067     * @param r ring factory.
068     * @param a ring element.
069     */
070    public Product(ProductRing<C> r, SortedMap<Integer, C> a) {
071        this(r, a, -1);
072    }
073
074
075    /**
076     * The constructor creates a Product object from a ring factory, a ring
077     * element and an indicator if a is a unit.
078     * @param r ring factory.
079     * @param a ring element.
080     * @param u isunit indicator, -1, 0, 1.
081     */
082    public Product(ProductRing<C> r, SortedMap<Integer, C> a, int u) {
083        ring = r;
084        val = a;
085        isunit = u;
086    }
087
088
089    /**
090     * Get component.
091     * @param i index of component.
092     * @return val(i).
093     */
094    public C get(int i) {
095        return val.get(i); // auto-boxing
096    }
097
098
099    /**
100     * Get the corresponding element factory.
101     * @return factory for this Element.
102     * @see edu.jas.structure.Element#factory()
103     */
104    public ProductRing<C> factory() {
105        return ring;
106    }
107
108
109    /**
110     * Clone this.
111     * @see java.lang.Object#clone()
112     */
113    @Override
114    public Product<C> copy() {
115        return new Product<C>(ring, val, isunit);
116    }
117
118
119    /**
120     * Is Product zero.
121     * @return If this is 0 then true is returned, else false.
122     * @see edu.jas.structure.RingElem#isZERO()
123     */
124    public boolean isZERO() {
125        return val.size() == 0;
126    }
127
128
129    /**
130     * Is Product one.
131     * @return If this is 1 then true is returned, else false.
132     * @see edu.jas.structure.RingElem#isONE()
133     */
134    public boolean isONE() {
135        if (val.size() != ring.length()) {
136            return false;
137        }
138        for (C e : val.values()) {
139            if (!e.isONE()) {
140                return false;
141            }
142        }
143        return true;
144    }
145
146
147    /**
148     * Is Product full.
149     * @return If every component is non-zero, then true is returned, else
150     *         false.
151     */
152    public boolean isFull() {
153        if (val.size() != ring.length()) {
154            return false;
155        }
156        return true;
157    }
158
159
160    /**
161     * Is Product unit.
162     * @return If this is a unit then true is returned, else false.
163     * @see edu.jas.structure.RingElem#isUnit()
164     */
165    public boolean isUnit() {
166        if (isunit > 0) {
167            return true;
168        }
169        if (isunit == 0) {
170            return false;
171        }
172        if (isZERO()) {
173            isunit = 0;
174            return false;
175        }
176        for (C e : val.values()) {
177            if (!e.isUnit()) {
178                isunit = 0;
179                return false;
180            }
181        }
182        isunit = 1;
183        return true;
184    }
185
186
187    /**
188     * Is Product idempotent.
189     * @return If this is a idempotent element then true is returned, else
190     *         false.
191     */
192    public boolean isIdempotent() {
193        for (C e : val.values()) {
194            if (!e.isONE()) {
195                return false;
196            }
197        }
198        return true;
199    }
200
201
202    /**
203     * Get the String representation as RingElem.
204     * @see java.lang.Object#toString()
205     */
206    @Override
207    public String toString() {
208        return val.toString();
209    }
210
211
212    /**
213     * Get a scripting compatible string representation.
214     * @return script compatible representation for this Element.
215     * @see edu.jas.structure.Element#toScript()
216     */
217    @Override
218    public String toScript() {
219        // Python case
220        StringBuffer s = new StringBuffer("( ");
221        boolean first = true;
222        for (Map.Entry<Integer, C> me : val.entrySet()) {
223            Integer i = me.getKey();
224            C v = me.getValue();
225            if (first) {
226                first = false;
227            } else {
228                if (v.signum() < 0) {
229                    s.append(" - ");
230                    v = v.negate();
231                } else {
232                    s.append(" + ");
233                }
234            }
235            if (!v.isONE()) {
236                s.append(v.toScript() + "*");
237            }
238            s.append("pg" + i);
239        }
240        s.append(" )");
241        return s.toString();
242    }
243
244
245    /**
246     * Get a scripting compatible string representation of the factory.
247     * @return script compatible representation for this ElemFactory.
248     * @see edu.jas.structure.Element#toScriptFactory()
249     */
250    @Override
251    public String toScriptFactory() {
252        // Python case
253        return factory().toScript();
254    }
255
256
257    /**
258     * Product comparison.
259     * @param b Product.
260     * @return sign(this-b).
261     */
262    @Override
263    public int compareTo(Product<C> b) {
264        if (!ring.equals(b.ring)) {
265            logger.info("other ring {}", b.ring);
266            throw new IllegalArgumentException("rings not comparable " + this);
267        }
268        SortedMap<Integer, C> v = b.val;
269        Iterator<Map.Entry<Integer, C>> ti = val.entrySet().iterator();
270        Iterator<Map.Entry<Integer, C>> bi = v.entrySet().iterator();
271        int s;
272        while (ti.hasNext() && bi.hasNext()) {
273            Map.Entry<Integer, C> te = ti.next();
274            Map.Entry<Integer, C> be = bi.next();
275            s = te.getKey().compareTo(be.getKey());
276            if (s != 0) {
277                return s;
278            }
279            s = te.getValue().compareTo(be.getValue());
280            if (s != 0) {
281                return s;
282            }
283        }
284        if (ti.hasNext()) {
285            return -1;
286        }
287        if (bi.hasNext()) {
288            return 1;
289        }
290        return 0;
291    }
292
293
294    /**
295     * Comparison with any other object.
296     * @see java.lang.Object#equals(java.lang.Object)
297     */
298    @SuppressWarnings("unchecked")
299    @Override
300    public boolean equals(Object b) {
301        if (b == null) {
302            return false;
303        }
304        if (!(b instanceof Product)) {
305            return false;
306        }
307        Product<C> a = (Product<C>) b;
308        return (0 == compareTo(a));
309    }
310
311
312    /**
313     * Hash code for this local.
314     * @see java.lang.Object#hashCode()
315     */
316    @Override
317    public int hashCode() {
318        int h = ring.hashCode();
319        h = 37 * h + val.hashCode();
320        return h;
321    }
322
323
324    /**
325     * Product extend. Add new component j with value of component i.
326     * @param i from index.
327     * @param j to index.
328     * @return the extended value of this.
329     */
330    public Product<C> extend(int i, int j) {
331        RingFactory<C> rf = ring.getFactory(j);
332        SortedMap<Integer, C> elem = new TreeMap<Integer, C>(val);
333        C v = val.get(i);
334        C w = rf.copy(v); // valueOf
335        if (!w.isZERO()) {
336            elem.put(j, w);
337        }
338        return new Product<C>(ring, elem, isunit);
339    }
340
341
342    /**
343     * Product absolute value.
344     * @return the absolute value of this.
345     * @see edu.jas.structure.RingElem#abs()
346     */
347    public Product<C> abs() {
348        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
349        for (Map.Entry<Integer, C> e : val.entrySet()) {
350            Integer i = e.getKey();
351            C v = e.getValue().abs();
352            elem.put(i, v);
353        }
354        return new Product<C>(ring, elem, isunit);
355    }
356
357
358    /**
359     * Product summation.
360     * @param S Product.
361     * @return this+S.
362     */
363    public Product<C> sum(Product<C> S) {
364        if (S == null || S.isZERO()) {
365            return this;
366        }
367        if (this.isZERO()) {
368            return S;
369        }
370        SortedMap<Integer, C> elem = new TreeMap<Integer, C>(val); // clone
371        SortedMap<Integer, C> sel = S.val;
372        for (Map.Entry<Integer, C> is : sel.entrySet()) {
373            Integer i = is.getKey();
374            C x = elem.get(i);
375            C y = is.getValue(); //sel.get( i ); // assert y != null
376            if (x != null) {
377                x = x.sum(y);
378                if (!x.isZERO()) {
379                    elem.put(i, x);
380                } else {
381                    elem.remove(i);
382                }
383            } else {
384                elem.put(i, y);
385            }
386        }
387        return new Product<C>(ring, elem);
388    }
389
390
391    /**
392     * Product negate.
393     * @return -this.
394     * @see edu.jas.structure.RingElem#negate()
395     */
396    public Product<C> negate() {
397        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
398        for (Map.Entry<Integer, C> me : val.entrySet()) {
399            Integer i = me.getKey();
400            C v = me.getValue().negate();
401            elem.put(i, v);
402        }
403        return new Product<C>(ring, elem, isunit);
404    }
405
406
407    /**
408     * Product signum.
409     * @see edu.jas.structure.RingElem#signum()
410     * @return signum of first non-zero component.
411     */
412    public int signum() {
413        if (val.size() == 0) {
414            return 0;
415        }
416        C v = val.get(val.firstKey());
417        return v.signum();
418    }
419
420
421    /**
422     * Product subtraction.
423     * @param S Product.
424     * @return this-S.
425     */
426    public Product<C> subtract(Product<C> S) {
427        return sum(S.negate());
428    }
429
430
431    /**
432     * Product quasi-inverse.
433     * @see edu.jas.structure.RingElem#inverse()
434     * @return S with S = 1/this if defined.
435     */
436    public Product<C> inverse() {
437        if (this.isZERO()) {
438            return this;
439        }
440        int isu = 0;
441        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
442        for (Map.Entry<Integer, C> me : val.entrySet()) {
443            Integer i = me.getKey();
444            C x = me.getValue(); // is non zero
445            try {
446                x = x.inverse();
447            } catch (NotInvertibleException e) {
448                // could happen for e.g. ModInteger or AlgebraicNumber
449                x = null; //ring.getFactory(i).getZERO();
450            }
451            if (x != null && !x.isZERO()) { // can happen
452                elem.put(i, x);
453                isu = 1;
454            }
455        }
456        return new Product<C>(ring, elem, isu);
457    }
458
459
460    /**
461     * Product idempotent.
462     * @return smallest S with this*S = this.
463     */
464    public Product<C> idempotent() {
465        if (this.isZERO()) {
466            return this;
467        }
468        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
469        for (Integer i : val.keySet()) {
470            RingFactory<C> f = ring.getFactory(i);
471            C x = f.getONE();
472            elem.put(i, x);
473        }
474        return new Product<C>(ring, elem, 1);
475    }
476
477
478    /**
479     * Product idempotent complement.
480     * @return 1-this.idempotent().
481     */
482    public Product<C> idemComplement() {
483        if (this.isZERO()) {
484            return ring.getONE();
485        }
486        int isu = 0;
487        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
488        for (int i = 0; i < ring.length(); i++) {
489            C v = val.get(i);
490            if (v == null) {
491                RingFactory<C> f = ring.getFactory(i);
492                C x = f.getONE();
493                elem.put(i, x);
494                isu = 1;
495            }
496        }
497        return new Product<C>(ring, elem, isu);
498    }
499
500
501    /**
502     * Product idempotent and.
503     * @param S Product.
504     * @return this.idempotent() and S.idempotent().
505     */
506    public Product<C> idempotentAnd(Product<C> S) {
507        if (this.isZERO() && S.isZERO()) {
508            return this;
509        }
510        int isu = 0;
511        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
512        for (int i = 0; i < ring.length(); i++) {
513            C v = val.get(i);
514            C w = S.val.get(i);
515            if (v != null && w != null) {
516                RingFactory<C> f = ring.getFactory(i);
517                C x = f.getONE();
518                elem.put(i, x);
519                isu = 1;
520            }
521        }
522        return new Product<C>(ring, elem, isu);
523    }
524
525
526    /**
527     * Product idempotent or.
528     * @param S Product.
529     * @return this.idempotent() or S.idempotent().
530     */
531    public Product<C> idempotentOr(Product<C> S) {
532        if (this.isZERO() && S.isZERO()) {
533            return this;
534        }
535        int isu = 0;
536        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
537        for (int i = 0; i < ring.length(); i++) {
538            C v = val.get(i);
539            C w = S.val.get(i);
540            if (v != null || w != null) {
541                RingFactory<C> f = ring.getFactory(i);
542                C x = f.getONE();
543                elem.put(i, x);
544                isu = 1;
545            }
546        }
547        return new Product<C>(ring, elem, isu);
548    }
549
550
551    /**
552     * Product fill with idempotent.
553     * @param S Product.
554     * @return fill this with S.idempotent().
555     */
556    public Product<C> fillIdempotent(Product<C> S) {
557        if (S.isZERO()) {
558            return this;
559        }
560        SortedMap<Integer, C> elem = new TreeMap<Integer, C>(val);
561        for (int i = 0; i < ring.length(); i++) {
562            C v = elem.get(i);
563            if (v != null) {
564                continue;
565            }
566            C w = S.val.get(i);
567            if (w != null) {
568                RingFactory<C> f = ring.getFactory(i);
569                C x = f.getONE();
570                elem.put(i, x);
571            }
572        }
573        return new Product<C>(ring, elem, isunit);
574    }
575
576
577    /**
578     * Product fill with one.
579     * @return fill this with one.
580     */
581    public Product<C> fillOne() {
582        if (this.isFull()) {
583            return this;
584        }
585        if (this.isZERO()) {
586            return ring.getONE();
587        }
588        SortedMap<Integer, C> elem = new TreeMap<Integer, C>(val);
589        for (int i = 0; i < ring.length(); i++) {
590            C v = elem.get(i);
591            if (v != null) {
592                continue;
593            }
594            RingFactory<C> f = ring.getFactory(i);
595            C x = f.getONE();
596            elem.put(i, x);
597        }
598        return new Product<C>(ring, elem, isunit);
599    }
600
601
602    /**
603     * Product quasi-division.
604     * @param S Product.
605     * @return this/S.
606     */
607    public Product<C> divide(Product<C> S) {
608        if (S == null) {
609            return ring.getZERO();
610        }
611        if (S.isZERO()) {
612            return S;
613        }
614        if (this.isZERO()) {
615            return this;
616        }
617        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
618        SortedMap<Integer, C> sel = S.val;
619        for (Map.Entry<Integer, C> me : val.entrySet()) {
620            Integer i = me.getKey();
621            C y = sel.get(i);
622            if (y != null) {
623                C x = me.getValue();
624                try {
625                    x = x.divide(y);
626                } catch (NotInvertibleException e) {
627                    // should not happen any more
628                    System.out.println("product divide error: x = " + x + ", y = " + y);
629                    // could happen for e.g. ModInteger or AlgebraicNumber
630                    x = null; //ring.getFactory(i).getZERO();
631                }
632                if (x != null && !x.isZERO()) { // can happen
633                    elem.put(i, x);
634                }
635            }
636        }
637        return new Product<C>(ring, elem);
638    }
639
640
641    /**
642     * Product quasi-remainder.
643     * @param S Product.
644     * @return this - (this/S)*S.
645     */
646    public Product<C> remainder(Product<C> S) {
647        if (S == null) {
648            return this; //ring.getZERO();
649        }
650        if (S.isZERO()) {
651            return this;
652        }
653        if (this.isZERO()) {
654            return this;
655        }
656        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
657        SortedMap<Integer, C> sel = S.val;
658        for (Map.Entry<Integer, C> me : val.entrySet()) {
659            Integer i = me.getKey();
660            C y = sel.get(i);
661            if (y != null) {
662                C x = me.getValue();
663                x = x.remainder(y);
664                if (x != null && !x.isZERO()) { // can happen
665                    elem.put(i, x);
666                }
667            }
668        }
669        return new Product<C>(ring, elem);
670    }
671
672
673    /**
674     * Quotient and remainder by division of this by S.
675     * @param S a product
676     * @return [this/S, this - (this/S)*S].
677     */
678    @SuppressWarnings("unchecked")
679    public Product<C>[] quotientRemainder(Product<C> S) {
680        return new Product[] { divide(S), remainder(S) };
681    }
682
683
684    /**
685     * Product multiplication.
686     * @param S Product.
687     * @return this*S.
688     */
689    public Product<C> multiply(Product<C> S) {
690        if (S == null) {
691            return ring.getZERO();
692        }
693        if (S.isZERO()) {
694            return S;
695        }
696        if (this.isZERO()) {
697            return this;
698        }
699        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
700        SortedMap<Integer, C> sel = S.val;
701        for (Map.Entry<Integer, C> me : val.entrySet()) {
702            Integer i = me.getKey();
703            C y = sel.get(i);
704            if (y != null) {
705                C x = me.getValue();
706                x = x.multiply(y);
707                if (x != null && !x.isZERO()) {
708                    elem.put(i, x);
709                }
710            }
711        }
712        return new Product<C>(ring, elem);
713    }
714
715
716    /**
717     * Product multiply by coefficient.
718     * @param c coefficient.
719     * @return this*c.
720     */
721    public Product<C> multiply(C c) {
722        SortedMap<Integer, C> elem = new TreeMap<Integer, C>();
723        for (Map.Entry<Integer, C> me : val.entrySet()) {
724            Integer i = me.getKey();
725            C v = me.getValue().multiply(c);
726            if (v != null && !v.isZERO()) {
727                elem.put(i, v);
728            }
729        }
730        return new Product<C>(ring, elem);
731    }
732
733
734    /**
735     * Greatest common divisor.
736     * @param S other element.
737     * @return gcd(this,S).
738     */
739    public Product<C> gcd(Product<C> S) {
740        if (S == null || S.isZERO()) {
741            return this;
742        }
743        if (this.isZERO()) {
744            return S;
745        }
746        SortedMap<Integer, C> elem = new TreeMap<Integer, C>(val); // clone
747        SortedMap<Integer, C> sel = S.val;
748        for (Map.Entry<Integer, C> is : sel.entrySet()) {
749            Integer i = is.getKey();
750            C x = elem.get(i);
751            C y = is.getValue(); //sel.get( i ); // assert y != null
752            if (x != null) {
753                x = x.gcd(y);
754                if (x != null && !x.isZERO()) {
755                    elem.put(i, x);
756                } else {
757                    elem.remove(i);
758                }
759            } else {
760                elem.put(i, y);
761            }
762        }
763        return new Product<C>(ring, elem);
764    }
765
766
767    /**
768     * Extended greatest common divisor.
769     * @param S other element.
770     * @return [ gcd(this,S), c1, c2 ] with c1*this + c2*b = gcd(this,S).
771     */
772    @SuppressWarnings("unchecked")
773    public Product<C>[] egcd(Product<C> S) {
774        Product<C>[] ret = new Product[3];
775        ret[0] = null;
776        ret[1] = null;
777        ret[2] = null;
778        if (S == null || S.isZERO()) {
779            ret[0] = this;
780            return ret;
781        }
782        if (this.isZERO()) {
783            ret[0] = S;
784            return ret;
785        }
786        SortedMap<Integer, C> elem = new TreeMap<Integer, C>(val); // clone
787        SortedMap<Integer, C> elem1 = this.idempotent().val; // init with 1
788        SortedMap<Integer, C> elem2 = new TreeMap<Integer, C>(); // zero
789        SortedMap<Integer, C> sel = S.val;
790        for (Map.Entry<Integer, C> is : sel.entrySet()) {
791            Integer i = is.getKey();
792            C x = elem.get(i);
793            C y = is.getValue(); //sel.get( i ); // assert y != null
794            if (x != null) {
795                C[] g = x.egcd(y);
796                if (!g[0].isZERO()) {
797                    elem.put(i, g[0]);
798                    elem1.put(i, g[1]);
799                    elem2.put(i, g[2]);
800                } else {
801                    elem.remove(i);
802                }
803            } else {
804                elem.put(i, y);
805                elem2.put(i, ring.getFactory(i).getONE());
806            }
807        }
808        ret[0] = new Product<C>(ring, elem);
809        ret[1] = new Product<C>(ring, elem1);
810        ret[2] = new Product<C>(ring, elem2);
811        return ret;
812    }
813
814}