Source code

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