Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.util.Collections;
009import java.util.Iterator;
010import java.util.Map;
011import java.util.SortedMap;
012import java.util.TreeMap;
013
014import org.apache.logging.log4j.LogManager;
015import org.apache.logging.log4j.Logger;
016
017import edu.jas.kern.PreemptingException;
018import edu.jas.structure.NotInvertibleException;
019import edu.jas.structure.RingElem;
020import edu.jas.structure.UnaryFunctor;
021
022
023/**
024 * GenWordPolynomial generic polynomials implementing RingElem. Non-commutative
025 * string polynomials over C. Objects of this class are intended to be
026 * immutable. The implementation is based on TreeMap respectively SortedMap from
027 * words to coefficients. Only the coefficients are modeled with generic types,
028 * the "exponents" are fixed to Word. C can also be a non integral domain, e.g.
029 * a ModInteger, i.e. it may contain zero divisors, since multiply() does check
030 * for zeros.
031 * @param <C> coefficient type
032 * @author Heinz Kredel
033 */
034public final class GenWordPolynomial<C extends RingElem<C>>
035                implements RingElem<GenWordPolynomial<C>>, Iterable<WordMonomial<C>> {
036
037
038    /**
039     * The factory for the polynomial ring.
040     */
041    public final GenWordPolynomialRing<C> ring;
042
043
044    /**
045     * The data structure for polynomials.
046     */
047    final SortedMap<Word, C> val; // do not change to TreeMap
048
049
050    private static final Logger logger = LogManager.getLogger(GenWordPolynomial.class);
051
052
053    private static final boolean debug = logger.isDebugEnabled();
054
055
056    // protected GenWordPolynomial() { ring = null; val = null; } // don't use
057
058
059    /**
060     * Private constructor for GenWordPolynomial.
061     * @param r polynomial ring factory.
062     * @param t TreeMap with correct ordering.
063     */
064    private GenWordPolynomial(GenWordPolynomialRing<C> r, TreeMap<Word, C> t) {
065        ring = r;
066        val = t;
067        if (ring.checkPreempt) {
068            if (Thread.currentThread().isInterrupted()) {
069                logger.debug("throw PreemptingException");
070                throw new PreemptingException();
071            }
072        }
073    }
074
075
076    /**
077     * Constructor for zero GenWordPolynomial.
078     * @param r polynomial ring factory.
079     */
080    public GenWordPolynomial(GenWordPolynomialRing<C> r) {
081        this(r, new TreeMap<Word, C>(r.alphabet.getDescendComparator()));
082    }
083
084
085    /**
086     * Constructor for GenWordPolynomial c * x<sup>e</sup>.
087     * @param r polynomial ring factory.
088     * @param c coefficient.
089     * @param e word.
090     */
091    public GenWordPolynomial(GenWordPolynomialRing<C> r, C c, Word e) {
092        this(r);
093        if (!c.isZERO()) {
094            val.put(e, c);
095        }
096    }
097
098
099    /**
100     * Constructor for GenWordPolynomial c * x<sup>0</sup>.
101     * @param r polynomial ring factory.
102     * @param c coefficient.
103     */
104    public GenWordPolynomial(GenWordPolynomialRing<C> r, C c) {
105        this(r, c, r.wone);
106    }
107
108
109    /**
110     * Constructor for GenWordPolynomial x<sup>e</sup>.
111     * @param r polynomial ring factory.
112     * @param e word.
113     */
114    public GenWordPolynomial(GenWordPolynomialRing<C> r, Word e) {
115        this(r, r.coFac.getONE(), e);
116    }
117
118
119    /**
120     * Constructor for GenWordPolynomial x<sup>e</sup>.
121     * @param r polynomial ring factory.
122     * @param e exponent vector.
123     */
124    public GenWordPolynomial(GenWordPolynomialRing<C> r, ExpVector e) {
125        this(r, r.coFac.getONE(), r.alphabet.valueOf(e));
126    }
127
128
129    /**
130     * Constructor for GenWordPolynomial c * x<sup>e</sup>.
131     * @param r polynomial ring factory.
132     * @param c coefficient.
133     * @param e exponent vector.
134     */
135    public GenWordPolynomial(GenWordPolynomialRing<C> r, C c, ExpVector e) {
136        this(r, c, r.alphabet.valueOf(e));
137    }
138
139
140    /**
141     * Constructor for GenWordPolynomial.
142     * @param r polynomial ring factory.
143     * @param v the SortedMap of some other polynomial.
144     */
145    protected GenWordPolynomial(GenWordPolynomialRing<C> r, SortedMap<Word, C> v) {
146        this(r);
147        val.putAll(v); // assume no zero coefficients
148    }
149
150
151    /**
152     * Get the corresponding element factory.
153     * @return factory for this Element.
154     * @see edu.jas.structure.Element#factory()
155     */
156    public GenWordPolynomialRing<C> factory() {
157        return ring;
158    }
159
160
161    /**
162     * Copy this GenWordPolynomial.
163     * @return copy of this.
164     */
165    public GenWordPolynomial<C> copy() {
166        return new GenWordPolynomial<C>(ring, this.val);
167    }
168
169
170    /**
171     * Length of GenWordPolynomial.
172     * @return number of coefficients of this GenWordPolynomial.
173     */
174    public int length() {
175        return val.size();
176    }
177
178
179    /**
180     * Word to coefficient map of GenWordPolynomial.
181     * @return val as unmodifiable SortedMap.
182     */
183    public SortedMap<Word, C> getMap() {
184        // return val;
185        return Collections.<Word, C> unmodifiableSortedMap(val);
186    }
187
188
189    /**
190     * Put a Word to coefficient entry into the internal map of this
191     * GenWordPolynomial. <b>Note:</b> Do not use this method unless you are
192     * constructing a new polynomial. this is modified and breaks the
193     * immutability promise of this class.
194     * @param c coefficient.
195     * @param e word.
196     */
197    public void doPutToMap(Word e, C c) {
198        if (debug) {
199            C a = val.get(e);
200            if (a != null) {
201                logger.error("map entry exists {} to {} new {}", e, a, c);
202            }
203        }
204        if (!c.isZERO()) {
205            val.put(e, c);
206        }
207    }
208
209
210    /**
211     * Remove a Word to coefficient entry from the internal map of this
212     * GenWordPolynomial. <b>Note:</b> Do not use this method unless you are
213     * constructing a new polynomial. this is modified and breaks the
214     * immutability promise of this class.
215     * @param e Word.
216     * @param c expected coefficient, null for ignore.
217     */
218    public void doRemoveFromMap(Word e, C c) {
219        C b = val.remove(e);
220        if (debug) {
221            if (c == null) { // ignore b
222                return;
223            }
224            if (!c.equals(b)) {
225                logger.error("map entry wrong {} to {} old {}", e, c, b);
226            }
227        }
228    }
229
230
231    /**
232     * Put an a sorted map of words to coefficients into the internal map of
233     * this GenWordPolynomial. <b>Note:</b> Do not use this method unless you
234     * are constructing a new polynomial. this is modified and breaks the
235     * immutability promise of this class.
236     * @param vals sorted map of wordss and coefficients.
237     */
238    public void doPutToMap(SortedMap<Word, C> vals) {
239        for (Map.Entry<Word, C> me : vals.entrySet()) {
240            Word e = me.getKey();
241            if (debug) {
242                C a = val.get(e);
243                if (a != null) {
244                    logger.error("map entry exists {} to {} new {}", e, a, me.getValue());
245                }
246            }
247            C c = me.getValue();
248            if (!c.isZERO()) {
249                val.put(e, c);
250            }
251        }
252    }
253
254
255    /**
256     * String representation of GenWordPolynomial.
257     * @see java.lang.Object#toString()
258     */
259    @Override
260    public String toString() {
261        if (isZERO()) {
262            return "0";
263        }
264        if (isONE()) {
265            return "1";
266        }
267        StringBuffer s = new StringBuffer();
268        if (val.size() > 1) {
269            s.append("( ");
270        }
271        boolean parenthesis = false;
272        boolean first = true;
273        for (Map.Entry<Word, C> m : val.entrySet()) {
274            C c = m.getValue();
275            if (first) {
276                first = false;
277            } else {
278                if (c.signum() < 0) {
279                    s.append(" - ");
280                    c = c.negate();
281                } else {
282                    s.append(" + ");
283                }
284            }
285            Word e = m.getKey();
286            if (!c.isONE() || e.isONE()) {
287                if (parenthesis) {
288                    s.append("( ");
289                }
290                String cs = c.toString();
291                if (cs.indexOf("+") >= 0 || cs.indexOf("-") >= 0) {
292                    s.append("( " + cs + " )");
293                } else {
294                    s.append(cs);
295                }
296                if (parenthesis) {
297                    s.append(" )");
298                }
299                if (!e.isONE()) {
300                    s.append(" ");
301                }
302            }
303            s.append(e.toString());
304        }
305        if (val.size() > 1) {
306            s.append(" )");
307        }
308        return s.toString();
309    }
310
311
312    /**
313     * Get a scripting compatible string representation.
314     * @return script compatible representation for this Element.
315     * @see edu.jas.structure.Element#toScript()
316     */
317    @Override
318    public String toScript() {
319        if (isZERO()) {
320            return "0";
321        }
322        if (isONE()) {
323            return "1";
324        }
325        StringBuffer s = new StringBuffer();
326        if (val.size() > 1) {
327            s.append("( ");
328        }
329        final boolean parenthesis = false;
330        boolean first = true;
331        for (Map.Entry<Word, C> m : val.entrySet()) {
332            C c = m.getValue();
333            if (first) {
334                first = false;
335            } else {
336                if (c.signum() < 0) {
337                    s.append(" - ");
338                    c = c.negate();
339                } else {
340                    s.append(" + ");
341                }
342            }
343            Word e = m.getKey();
344            if (!c.isONE() || e.isONE()) {
345                if (parenthesis) {
346                    s.append("( ");
347                }
348                String cs = c.toScript();
349                if (cs.indexOf("+") >= 0 || cs.indexOf("-") >= 0) {
350                    s.append("( " + cs + " )");
351                } else {
352                    s.append(cs);
353                }
354                if (parenthesis) {
355                    s.append(" )");
356                }
357                if (!e.isONE()) {
358                    s.append(" * ");
359                }
360            }
361            s.append(e.toScript());
362        }
363        if (val.size() > 1) {
364            s.append(" )");
365        }
366        return s.toString();
367    }
368
369
370    /**
371     * Get a scripting compatible string representation of the factory.
372     * @return script compatible representation for this ElemFactory.
373     * @see edu.jas.structure.Element#toScriptFactory()
374     */
375    @Override
376    public String toScriptFactory() {
377        // Python case
378        return factory().toScript();
379    }
380
381
382    /**
383     * Is GenWordPolynomial&lt;C&gt; zero.
384     * @return If this is 0 then true is returned, else false.
385     * @see edu.jas.structure.RingElem#isZERO()
386     */
387    public boolean isZERO() {
388        return (val.size() == 0);
389    }
390
391
392    /**
393     * Is GenWordPolynomial&lt;C&gt; one.
394     * @return If this is 1 then true is returned, else false.
395     * @see edu.jas.structure.RingElem#isONE()
396     */
397    public boolean isONE() {
398        if (val.size() != 1) {
399            return false;
400        }
401        C c = val.get(ring.wone);
402        if (c == null) {
403            return false;
404        }
405        return c.isONE();
406    }
407
408
409    /**
410     * Is GenWordPolynomial&lt;C&gt; a unit.
411     * @return If this is a unit then true is returned, else false.
412     * @see edu.jas.structure.RingElem#isUnit()
413     */
414    public boolean isUnit() {
415        if (val.size() != 1) {
416            return false;
417        }
418        C c = val.get(ring.wone);
419        if (c == null) {
420            return false;
421        }
422        return c.isUnit();
423    }
424
425
426    /**
427     * Is GenWordPolynomial&lt;C&gt; a constant.
428     * @return If this is a constant polynomial then true is returned, else
429     *         false.
430     */
431    public boolean isConstant() {
432        if (val.size() != 1) {
433            return false;
434        }
435        C c = val.get(ring.wone);
436        if (c == null) {
437            return false;
438        }
439        return true;
440    }
441
442
443    /**
444     * Is GenWordPolynomial&lt;C&gt; homogeneous.
445     * @return true, if this is homogeneous, else false.
446     */
447    public boolean isHomogeneous() {
448        if (val.size() <= 1) {
449            return true;
450        }
451        long deg = -1;
452        for (Word e : val.keySet()) {
453            if (deg < 0) {
454                deg = e.degree();
455            } else if (deg != e.degree()) {
456                return false;
457            }
458        }
459        return true;
460    }
461
462
463    /**
464     * Comparison with any other object.
465     * @see java.lang.Object#equals(java.lang.Object)
466     */
467    @Override
468    @SuppressWarnings("unchecked")
469    public boolean equals(Object B) {
470        if (B == null) {
471            return false;
472        }
473        if (!(B instanceof GenWordPolynomial)) {
474            return false;
475        }
476        GenWordPolynomial<C> a = (GenWordPolynomial<C>) B;
477        return this.compareTo(a) == 0;
478    }
479
480
481    /**
482     * Hash code for this polynomial.
483     * @see java.lang.Object#hashCode()
484     */
485    @Override
486    public int hashCode() {
487        int h;
488        h = (ring.hashCode() << 27);
489        h += val.hashCode();
490        return h;
491    }
492
493
494    /**
495     * GenWordPolynomial comparison.
496     * @param b GenWordPolynomial.
497     * @return sign(this-b).
498     */
499    public int compareTo(GenWordPolynomial<C> b) {
500        if (b == null) {
501            return 1;
502        }
503        SortedMap<Word, C> av = this.val;
504        SortedMap<Word, C> bv = b.val;
505        Iterator<Map.Entry<Word, C>> ai = av.entrySet().iterator();
506        Iterator<Map.Entry<Word, C>> bi = bv.entrySet().iterator();
507        int s = 0;
508        int c = 0;
509        while (ai.hasNext() && bi.hasNext()) {
510            Map.Entry<Word, C> aie = ai.next();
511            Map.Entry<Word, C> bie = bi.next();
512            Word ae = aie.getKey();
513            Word be = bie.getKey();
514            s = ae.compareTo(be);
515            //System.out.println("s = " + s + ", " + ae + ", " +be);
516            if (s != 0) {
517                return s;
518            }
519            if (c == 0) {
520                C ac = aie.getValue(); //av.get(ae);
521                C bc = bie.getValue(); //bv.get(be);
522                c = ac.compareTo(bc);
523            }
524        }
525        if (ai.hasNext()) {
526            return 1;
527        }
528        if (bi.hasNext()) {
529            return -1;
530        }
531        // now all keys are equal
532        return c;
533    }
534
535
536    /**
537     * GenWordPolynomial signum.
538     * @return sign(ldcf(this)).
539     */
540    public int signum() {
541        if (this.isZERO()) {
542            return 0;
543        }
544        Word t = val.firstKey();
545        C c = val.get(t);
546        return c.signum();
547    }
548
549
550    /**
551     * Number of variables.
552     * @return ring.alphabet.length().
553     */
554    public int numberOfVariables() {
555        return ring.alphabet.length();
556    }
557
558
559    /**
560     * Leading monomial.
561     * @return first map entry.
562     */
563    public Map.Entry<Word, C> leadingMonomial() {
564        if (val.size() == 0)
565            return null;
566        Iterator<Map.Entry<Word, C>> ai = val.entrySet().iterator();
567        return ai.next();
568    }
569
570
571    /**
572     * Leading word.
573     * @return first highest word.
574     */
575    public Word leadingWord() {
576        if (val.size() == 0) {
577            return ring.wone; // null? needs changes? 
578        }
579        return val.firstKey();
580    }
581
582
583    /**
584     * Trailing word.
585     * @return last lowest word.
586     */
587    public Word trailingWord() {
588        if (val.size() == 0) {
589            return ring.wone; // or null ?;
590        }
591        return val.lastKey();
592    }
593
594
595    /**
596     * Leading base coefficient.
597     * @return first coefficient.
598     */
599    public C leadingBaseCoefficient() {
600        if (val.size() == 0) {
601            return ring.coFac.getZERO();
602        }
603        return val.get(val.firstKey());
604    }
605
606
607    /**
608     * Trailing base coefficient.
609     * @return coefficient of constant term.
610     */
611    public C trailingBaseCoefficient() {
612        C c = val.get(ring.wone);
613        if (c == null) {
614            return ring.coFac.getZERO();
615        }
616        return c;
617    }
618
619
620    /**
621     * Coefficient.
622     * @param e word.
623     * @return coefficient for given word.
624     */
625    public C coefficient(Word e) {
626        C c = val.get(e);
627        if (c == null) {
628            c = ring.coFac.getZERO();
629        }
630        return c;
631    }
632
633
634    /**
635     * Reductum.
636     * @return this - leading monomial.
637     */
638    public GenWordPolynomial<C> reductum() {
639        if (val.size() <= 1) {
640            return ring.getZERO();
641        }
642        Iterator<Word> ai = val.keySet().iterator();
643        Word lt = ai.next();
644        lt = ai.next(); // size > 1
645        SortedMap<Word, C> red = val.tailMap(lt);
646        return new GenWordPolynomial<C>(ring, red);
647    }
648
649
650    /**
651     * Maximal degree.
652     * @return maximal degree in any variables.
653     */
654    public long degree() {
655        if (val.size() == 0) {
656            return 0; // 0 or -1 ?;
657        }
658        long deg = 0;
659        for (Word e : val.keySet()) {
660            long d = e.degree();
661            if (d > deg) {
662                deg = d;
663            }
664        }
665        return deg;
666    }
667
668
669    /**
670     * GenWordPolynomial maximum norm.
671     * @return ||this||.
672     */
673    public C maxNorm() {
674        C n = ring.getZEROCoefficient();
675        for (C c : val.values()) {
676            C x = c.abs();
677            if (n.compareTo(x) < 0) {
678                n = x;
679            }
680        }
681        return n;
682    }
683
684
685    /**
686     * GenWordPolynomial sum norm.
687     * @return sum of all absolute values of coefficients.
688     */
689    public C sumNorm() {
690        C n = ring.getZEROCoefficient();
691        for (C c : val.values()) {
692            C x = c.abs();
693            n = n.sum(x);
694        }
695        return n;
696    }
697
698
699    /**
700     * GenWordPolynomial summation.
701     * @param S GenWordPolynomial.
702     * @return this+S.
703     */
704    public GenWordPolynomial<C> sum(GenWordPolynomial<C> S) {
705        if (S == null) {
706            return this;
707        }
708        if (S.isZERO()) {
709            return this;
710        }
711        if (this.isZERO()) {
712            return S;
713        }
714        assert (ring.alphabet == S.ring.alphabet);
715        GenWordPolynomial<C> n = this.copy(); //new GenWordPolynomial<C>(ring, val); 
716        SortedMap<Word, C> nv = n.val;
717        SortedMap<Word, C> sv = S.val;
718        for (Map.Entry<Word, C> me : sv.entrySet()) {
719            Word e = me.getKey();
720            C y = me.getValue(); //sv.get(e); // assert y != null
721            C x = nv.get(e);
722            if (x != null) {
723                x = x.sum(y);
724                if (!x.isZERO()) {
725                    nv.put(e, x);
726                } else {
727                    nv.remove(e);
728                }
729            } else {
730                nv.put(e, y);
731            }
732        }
733        return n;
734    }
735
736
737    /**
738     * GenWordPolynomial addition. This method is not very efficient, since this
739     * is copied.
740     * @param a coefficient.
741     * @param e word.
742     * @return this + a e.
743     */
744    public GenWordPolynomial<C> sum(C a, Word e) {
745        if (a == null) {
746            return this;
747        }
748        if (a.isZERO()) {
749            return this;
750        }
751        GenWordPolynomial<C> n = this.copy(); //new GenWordPolynomial<C>(ring, val); 
752        SortedMap<Word, C> nv = n.val;
753        C x = nv.get(e);
754        if (x != null) {
755            x = x.sum(a);
756            if (!x.isZERO()) {
757                nv.put(e, x);
758            } else {
759                nv.remove(e);
760            }
761        } else {
762            nv.put(e, a);
763        }
764        return n;
765    }
766
767
768    /**
769     * GenWordPolynomial addition. This method is not very efficient, since this
770     * is copied.
771     * @param a coefficient.
772     * @return this + a x<sup>0</sup>.
773     */
774    public GenWordPolynomial<C> sum(C a) {
775        return sum(a, ring.wone);
776    }
777
778
779    /**
780     * GenWordPolynomial subtraction.
781     * @param S GenWordPolynomial.
782     * @return this-S.
783     */
784    public GenWordPolynomial<C> subtract(GenWordPolynomial<C> S) {
785        if (S == null) {
786            return this;
787        }
788        if (S.isZERO()) {
789            return this;
790        }
791        if (this.isZERO()) {
792            return S.negate();
793        }
794        assert (ring.alphabet == S.ring.alphabet);
795        GenWordPolynomial<C> n = this.copy(); //new GenWordPolynomial<C>(ring, val); 
796        SortedMap<Word, C> nv = n.val;
797        SortedMap<Word, C> sv = S.val;
798        for (Map.Entry<Word, C> me : sv.entrySet()) {
799            Word e = me.getKey();
800            C y = me.getValue(); //sv.get(e); // assert y != null
801            C x = nv.get(e);
802            if (x != null) {
803                x = x.subtract(y);
804                if (!x.isZERO()) {
805                    nv.put(e, x);
806                } else {
807                    nv.remove(e);
808                }
809            } else {
810                nv.put(e, y.negate());
811            }
812        }
813        return n;
814    }
815
816
817    /**
818     * GenWordPolynomial subtraction. This method is not very efficient, since
819     * this is copied.
820     * @param a coefficient.
821     * @param e word.
822     * @return this - a e.
823     */
824    public GenWordPolynomial<C> subtract(C a, Word e) {
825        if (a == null) {
826            return this;
827        }
828        if (a.isZERO()) {
829            return this;
830        }
831        GenWordPolynomial<C> n = this.copy(); //new GenWordPolynomial<C>(ring, val); 
832        SortedMap<Word, C> nv = n.val;
833        C x = nv.get(e);
834        if (x != null) {
835            x = x.subtract(a);
836            if (!x.isZERO()) {
837                nv.put(e, x);
838            } else {
839                nv.remove(e);
840            }
841        } else {
842            nv.put(e, a.negate());
843        }
844        return n;
845    }
846
847
848    /**
849     * GenWordPolynomial subtract. This method is not very efficient, since this
850     * is copied.
851     * @param a coefficient.
852     * @return this + a x<sup>0</sup>.
853     */
854    public GenWordPolynomial<C> subtract(C a) {
855        return subtract(a, ring.wone);
856    }
857
858
859    /**
860     * GenWordPolynomial negation.
861     * @return -this.
862     */
863    public GenWordPolynomial<C> negate() {
864        GenWordPolynomial<C> n = ring.getZERO().copy();
865        SortedMap<Word, C> v = n.val;
866        for (Map.Entry<Word, C> m : val.entrySet()) {
867            C x = m.getValue(); // != null, 0
868            v.put(m.getKey(), x.negate());
869        }
870        return n;
871    }
872
873
874    /**
875     * GenWordPolynomial absolute value, i.e. leadingCoefficient &gt; 0.
876     * @return abs(this).
877     */
878    public GenWordPolynomial<C> abs() {
879        if (leadingBaseCoefficient().signum() < 0) {
880            return this.negate();
881        }
882        return this;
883    }
884
885
886    /**
887     * GenWordPolynomial multiplication.
888     * @param S GenWordPolynomial.
889     * @return this*S.
890     */
891    public GenWordPolynomial<C> multiply(GenWordPolynomial<C> S) {
892        if (S == null) {
893            return ring.getZERO();
894        }
895        if (S.isZERO()) {
896            return ring.getZERO();
897        }
898        if (this.isZERO()) {
899            return this;
900        }
901        assert (ring.alphabet == S.ring.alphabet) : " " + ring + " != " + S.ring;
902        GenWordPolynomial<C> p = ring.getZERO().copy();
903        SortedMap<Word, C> pv = p.val;
904        for (Map.Entry<Word, C> m1 : val.entrySet()) {
905            C c1 = m1.getValue();
906            Word e1 = m1.getKey();
907            for (Map.Entry<Word, C> m2 : S.val.entrySet()) {
908                C c2 = m2.getValue();
909                Word e2 = m2.getKey();
910                C c = c1.multiply(c2); // check non zero if not domain
911                if (!c.isZERO()) {
912                    Word e = e1.multiply(e2);
913                    C c0 = pv.get(e);
914                    if (c0 == null) {
915                        pv.put(e, c);
916                    } else {
917                        c0 = c0.sum(c);
918                        if (!c0.isZERO()) {
919                            pv.put(e, c0);
920                        } else {
921                            pv.remove(e);
922                        }
923                    }
924                }
925            }
926        }
927        return p;
928    }
929
930
931    /**
932     * GenWordPolynomial left and right multiplication. Product with two
933     * polynomials.
934     * @param S GenWordPolynomial.
935     * @param T GenWordPolynomial.
936     * @return S*this*T.
937     */
938    public GenWordPolynomial<C> multiply(GenWordPolynomial<C> S, GenWordPolynomial<C> T) {
939        if (S.isZERO() || T.isZERO()) {
940            return ring.getZERO();
941        }
942        if (S.isONE()) {
943            return multiply(T);
944        }
945        if (T.isONE()) {
946            return S.multiply(this);
947        }
948        return S.multiply(this).multiply(T);
949    }
950
951
952    /**
953     * GenWordPolynomial multiplication. Product with coefficient ring element.
954     * @param s coefficient.
955     * @return this*s.
956     */
957    public GenWordPolynomial<C> multiply(C s) {
958        if (s == null) {
959            return ring.getZERO();
960        }
961        if (s.isZERO()) {
962            return ring.getZERO();
963        }
964        if (this.isZERO()) {
965            return this;
966        }
967        GenWordPolynomial<C> p = ring.getZERO().copy();
968        SortedMap<Word, C> pv = p.val;
969        for (Map.Entry<Word, C> m1 : val.entrySet()) {
970            C c1 = m1.getValue();
971            Word e1 = m1.getKey();
972            C c = c1.multiply(s); // check non zero if not domain
973            if (!c.isZERO()) {
974                pv.put(e1, c); // or m1.setValue( c )
975            }
976        }
977        return p;
978    }
979
980
981    /**
982     * GenWordPolynomial multiplication. Product with coefficient ring element.
983     * @param s coefficient.
984     * @param t coefficient.
985     * @return s*this*t.
986     */
987    public GenWordPolynomial<C> multiply(C s, C t) {
988        if (s == null || t == null) {
989            return ring.getZERO();
990        }
991        if (s.isZERO() || t.isZERO()) {
992            return ring.getZERO();
993        }
994        if (this.isZERO()) {
995            return this;
996        }
997        GenWordPolynomial<C> p = ring.getZERO().copy();
998        SortedMap<Word, C> pv = p.val;
999        for (Map.Entry<Word, C> m1 : val.entrySet()) {
1000            C c1 = m1.getValue();
1001            Word e = m1.getKey();
1002            C c = s.multiply(c1).multiply(t); // check non zero if not domain
1003            if (!c.isZERO()) {
1004                pv.put(e, c); // or m1.setValue( c )
1005            }
1006        }
1007        return p;
1008    }
1009
1010
1011    /**
1012     * GenWordPolynomial monic, i.e. leadingCoefficient == 1. If
1013     * leadingCoefficient is not invertible returns this unmodified.
1014     * @return monic(this).
1015     */
1016    public GenWordPolynomial<C> monic() {
1017        if (this.isZERO()) {
1018            return this;
1019        }
1020        C lc = leadingBaseCoefficient();
1021        if (!lc.isUnit()) {
1022            //System.out.println("lc = "+lc);
1023            return this;
1024        }
1025        C lm = lc.inverse();
1026        return multiply(lm);
1027    }
1028
1029
1030    /**
1031     * GenWordPolynomial multiplication. Product with ring element and word.
1032     * @param s coefficient.
1033     * @param e left word.
1034     * @return this * s e.
1035     */
1036    public GenWordPolynomial<C> multiply(C s, Word e) {
1037        if (s == null) {
1038            return ring.getZERO();
1039        }
1040        if (s.isZERO()) {
1041            return ring.getZERO();
1042        }
1043        if (this.isZERO()) {
1044            return this;
1045        }
1046        GenWordPolynomial<C> p = ring.getZERO().copy();
1047        SortedMap<Word, C> pv = p.val;
1048        for (Map.Entry<Word, C> m1 : val.entrySet()) {
1049            C c1 = m1.getValue();
1050            Word e1 = m1.getKey();
1051            C c = c1.multiply(s); // check non zero if not domain
1052            if (!c.isZERO()) {
1053                Word e2 = e1.multiply(e);
1054                pv.put(e2, c);
1055            }
1056        }
1057        return p;
1058    }
1059
1060
1061    /**
1062     * GenWordPolynomial left and right multiplication. Product with ring
1063     * element and two words.
1064     * @param e left word.
1065     * @param f right word.
1066     * @return e * this * f.
1067     */
1068    public GenWordPolynomial<C> multiply(Word e, Word f) {
1069        if (this.isZERO()) {
1070            return this;
1071        }
1072        if (e.isONE()) {
1073            return multiply(f);
1074        }
1075        GenWordPolynomial<C> p = ring.getZERO().copy();
1076        SortedMap<Word, C> pv = p.val;
1077        for (Map.Entry<Word, C> m1 : val.entrySet()) {
1078            C c = m1.getValue();
1079            Word e1 = m1.getKey();
1080            Word e2 = e.multiply(e1.multiply(f));
1081            pv.put(e2, c);
1082        }
1083        return p;
1084    }
1085
1086
1087    /**
1088     * GenWordPolynomial left and right multiplication. Product with ring
1089     * element and two words.
1090     * @param s coefficient.
1091     * @param e left word.
1092     * @param f right word.
1093     * @return e * this * s * f.
1094     */
1095    public GenWordPolynomial<C> multiply(C s, Word e, Word f) {
1096        if (s == null) {
1097            return ring.getZERO();
1098        }
1099        if (s.isZERO()) {
1100            return ring.getZERO();
1101        }
1102        if (this.isZERO()) {
1103            return this;
1104        }
1105        if (e.isONE()) {
1106            return multiply(s, f);
1107        }
1108        C c = ring.coFac.getONE();
1109        return multiply(c, e, s, f); // sic, history
1110    }
1111
1112
1113    /**
1114     * GenWordPolynomial left and right multiplication. Product with ring
1115     * element and two words.
1116     * @param s coefficient.
1117     * @param e left word.
1118     * @param t coefficient.
1119     * @param f right word.
1120     * @return s * e * this * t * f.
1121     */
1122    public GenWordPolynomial<C> multiply(C s, Word e, C t, Word f) {
1123        if (s == null) {
1124            return ring.getZERO();
1125        }
1126        if (s.isZERO()) {
1127            return ring.getZERO();
1128        }
1129        if (this.isZERO()) {
1130            return this;
1131        }
1132        GenWordPolynomial<C> p = ring.getZERO().copy();
1133        SortedMap<Word, C> pv = p.val;
1134        for (Map.Entry<Word, C> m1 : val.entrySet()) {
1135            C c1 = m1.getValue();
1136            C c = s.multiply(c1).multiply(t); // check non zero if not domain
1137            if (!c.isZERO()) {
1138                Word e1 = m1.getKey();
1139                Word e2 = e.multiply(e1).multiply(f);
1140                pv.put(e2, c);
1141            }
1142        }
1143        return p;
1144    }
1145
1146
1147    /**
1148     * GenWordPolynomial multiplication. Product with word.
1149     * @param e word (!= null).
1150     * @return this * e.
1151     */
1152    public GenWordPolynomial<C> multiply(Word e) {
1153        if (this.isZERO()) {
1154            return this;
1155        }
1156        GenWordPolynomial<C> p = ring.getZERO().copy();
1157        SortedMap<Word, C> pv = p.val;
1158        for (Map.Entry<Word, C> m1 : val.entrySet()) {
1159            C c1 = m1.getValue();
1160            Word e1 = m1.getKey();
1161            Word e2 = e1.multiply(e);
1162            pv.put(e2, c1);
1163        }
1164        return p;
1165    }
1166
1167
1168    /**
1169     * GenWordPolynomial multiplication. Product with 'monomial'.
1170     * @param m 'monomial'.
1171     * @return this * m.
1172     */
1173    public GenWordPolynomial<C> multiply(Map.Entry<Word, C> m) {
1174        if (m == null) {
1175            return ring.getZERO();
1176        }
1177        return multiply(m.getValue(), m.getKey());
1178    }
1179
1180
1181    /**
1182     * GenWordPolynomial division. Division by coefficient ring element. Fails,
1183     * if exact division is not possible.
1184     * @param s coefficient.
1185     * @return this/s.
1186     */
1187    public GenWordPolynomial<C> divide(C s) {
1188        if (s == null || s.isZERO()) {
1189            throw new ArithmeticException(this.getClass().getName() + " division by zero");
1190        }
1191        if (this.isZERO()) {
1192            return this;
1193        }
1194        //C t = s.inverse();
1195        //return multiply(t);
1196        GenWordPolynomial<C> p = ring.getZERO().copy();
1197        SortedMap<Word, C> pv = p.val;
1198        for (Map.Entry<Word, C> m : val.entrySet()) {
1199            Word e = m.getKey();
1200            C c1 = m.getValue();
1201            C c = c1.divide(s); // is divideLeft
1202            if (debug) {
1203                C x = c1.remainder(s);
1204                if (!x.isZERO()) {
1205                    logger.info("divide x = {}", x);
1206                    throw new ArithmeticException(
1207                                    this.getClass().getName() + " no exact division: " + c1 + "/" + s);
1208                }
1209            }
1210            if (c.isZERO()) {
1211                throw new ArithmeticException(this.getClass().getName() + " no exact division: " + c1 + "/"
1212                                + s + ", in " + this);
1213            }
1214            pv.put(e, c); // or m1.setValue( c )
1215        }
1216        return p;
1217    }
1218
1219
1220    /**
1221     * GenWordPolynomial division with remainder. Fails, if exact division by
1222     * leading base coefficient is not possible. Meaningful only for univariate
1223     * polynomials over fields, but works in any case.
1224     * @param S nonzero GenWordPolynomial with invertible leading coefficient.
1225     * @return [ quotient , remainder ] with this = quotient * S + remainder and
1226     *         deg(remainder) &lt; deg(S) or remainder = 0.
1227     * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial)
1228     *      .
1229     */
1230    @SuppressWarnings("unchecked")
1231    public GenWordPolynomial<C>[] quotientRemainder(GenWordPolynomial<C> S) {
1232        if (S == null || S.isZERO()) {
1233            throw new ArithmeticException(this.getClass().getName() + " division by zero");
1234        }
1235        C c = S.leadingBaseCoefficient();
1236        if (!c.isUnit()) {
1237            throw new ArithmeticException(this.getClass().getName() + " lbcf not invertible " + c);
1238        }
1239        C ci = c.inverse();
1240        C one = ring.coFac.getONE();
1241        assert (ring.alphabet == S.ring.alphabet);
1242        WordFactory.WordComparator cmp = ring.alphabet.getDescendComparator();
1243        Word e = S.leadingWord();
1244        GenWordPolynomial<C> h;
1245        GenWordPolynomial<C> q = ring.getZERO().copy();
1246        GenWordPolynomial<C> r = this.copy();
1247        while (!r.isZERO()) {
1248            Word f = r.leadingWord();
1249            if (f.multipleOf(e)) {
1250                C a = r.leadingBaseCoefficient();
1251                Word[] g = f.divideWord(e); // divide not sufficient
1252                //logger.info("div: f = {}, e = {}, g = {}, {}", f, e, g[0], g[1]);
1253                a = a.multiply(ci);
1254                q = q.sum(a, g[0].multiply(g[1]));
1255                h = S.multiply(a, g[0], one, g[1]);
1256                r = r.subtract(h);
1257                Word fr = r.leadingWord();
1258                if (cmp.compare(f, fr) > 0) { // non noetherian reduction
1259                    throw new RuntimeException("possible infinite loop: f = " + f + ", fr = " + fr);
1260                }
1261            } else {
1262                break;
1263            }
1264        }
1265        GenWordPolynomial<C>[] ret = new GenWordPolynomial[2];
1266        ret[0] = q;
1267        ret[1] = r;
1268        return ret;
1269    }
1270
1271
1272    /**
1273     * GenWordPolynomial division. Fails, if exact division by leading base
1274     * coefficient is not possible. Meaningful only for univariate polynomials
1275     * over fields, but works in any case.
1276     * @param S nonzero GenWordPolynomial with invertible leading coefficient.
1277     * @return quotient with this = quotient * S + remainder.
1278     * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial)
1279     *      .
1280     */
1281    public GenWordPolynomial<C> divide(GenWordPolynomial<C> S) {
1282        return quotientRemainder(S)[0];
1283    }
1284
1285
1286    /**
1287     * GenWordPolynomial remainder. Fails, if exact division by leading base
1288     * coefficient is not possible. Meaningful only for univariate polynomials
1289     * over fields, but works in any case.
1290     * @param S nonzero GenWordPolynomial with invertible leading coefficient.
1291     * @return remainder with this = quotient * S + remainder.
1292     * @see edu.jas.poly.PolyUtil#baseSparsePseudoRemainder(edu.jas.poly.GenPolynomial,edu.jas.poly.GenPolynomial)
1293     *      .
1294     */
1295    public GenWordPolynomial<C> remainder(GenWordPolynomial<C> S) {
1296        if (S == null || S.isZERO()) {
1297            throw new ArithmeticException(this.getClass().getName() + " division by zero");
1298        }
1299        C c = S.leadingBaseCoefficient();
1300        if (!c.isUnit()) {
1301            throw new ArithmeticException(this.getClass().getName() + " lbc not invertible " + c);
1302        }
1303        C ci = c.inverse();
1304        C one = ring.coFac.getONE();
1305        assert (ring.alphabet == S.ring.alphabet);
1306        WordFactory.WordComparator cmp = ring.alphabet.getDescendComparator();
1307        Word e = S.leadingWord();
1308        GenWordPolynomial<C> h;
1309        GenWordPolynomial<C> r = this.copy();
1310        while (!r.isZERO()) {
1311            Word f = r.leadingWord();
1312            if (f.multipleOf(e)) {
1313                C a = r.leadingBaseCoefficient();
1314                Word[] g = f.divideWord(e); // divide not sufficient
1315                //logger.info("rem: f = {}, e = {}, g = {}, {}", f, e, g[0], g[1]);
1316                a = a.multiply(ci);
1317                h = S.multiply(a, g[0], one, g[1]);
1318                r = r.subtract(h);
1319                Word fr = r.leadingWord();
1320                if (cmp.compare(f, fr) > 0) { // non noetherian reduction
1321                    throw new RuntimeException("possible infinite loop: f = " + f + ", fr = " + fr);
1322                }
1323            } else {
1324                break;
1325            }
1326        }
1327        return r;
1328    }
1329
1330
1331    /**
1332     * GenWordPolynomial greatest common divisor. Only for univariate
1333     * polynomials over fields.
1334     * @param S GenWordPolynomial.
1335     * @return gcd(this,S).
1336     */
1337    public GenWordPolynomial<C> gcd(GenWordPolynomial<C> S) {
1338        if (S == null || S.isZERO()) {
1339            return this;
1340        }
1341        if (this.isZERO()) {
1342            return S;
1343        }
1344        if (ring.alphabet.length() != 1) {
1345            throw new IllegalArgumentException("no univariate polynomial " + ring);
1346        }
1347        GenWordPolynomial<C> x;
1348        GenWordPolynomial<C> q = this;
1349        GenWordPolynomial<C> r = S;
1350        while (!r.isZERO()) {
1351            x = q.remainder(r);
1352            q = r;
1353            r = x;
1354        }
1355        return q.monic(); // normalize
1356    }
1357
1358
1359    /**
1360     * GenWordPolynomial extended greatest common divisor. Only for univariate
1361     * polynomials over fields.
1362     * @param S GenWordPolynomial.
1363     * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
1364     */
1365    @SuppressWarnings("unchecked")
1366    public GenWordPolynomial<C>[] egcd(GenWordPolynomial<C> S) {
1367        GenWordPolynomial<C>[] ret = new GenWordPolynomial[3];
1368        ret[0] = null;
1369        ret[1] = null;
1370        ret[2] = null;
1371        if (S == null || S.isZERO()) {
1372            ret[0] = this;
1373            ret[1] = this.ring.getONE();
1374            ret[2] = this.ring.getZERO();
1375            return ret;
1376        }
1377        if (this.isZERO()) {
1378            ret[0] = S;
1379            ret[1] = this.ring.getZERO();
1380            ret[2] = this.ring.getONE();
1381            return ret;
1382        }
1383        if (ring.alphabet.length() != 1) {
1384            throw new IllegalArgumentException("no univariate polynomial " + ring);
1385        }
1386        if (this.isConstant() && S.isConstant()) {
1387            C t = this.leadingBaseCoefficient();
1388            C s = S.leadingBaseCoefficient();
1389            C[] gg = t.egcd(s);
1390            //System.out.println("coeff gcd = " + Arrays.toString(gg));
1391            GenWordPolynomial<C> z = this.ring.getZERO();
1392            ret[0] = z.sum(gg[0]);
1393            ret[1] = z.sum(gg[1]);
1394            ret[2] = z.sum(gg[2]);
1395            return ret;
1396        }
1397        GenWordPolynomial<C>[] qr;
1398        GenWordPolynomial<C> q = this;
1399        GenWordPolynomial<C> r = S;
1400        GenWordPolynomial<C> c1 = ring.getONE().copy();
1401        GenWordPolynomial<C> d1 = ring.getZERO().copy();
1402        GenWordPolynomial<C> c2 = ring.getZERO().copy();
1403        GenWordPolynomial<C> d2 = ring.getONE().copy();
1404        GenWordPolynomial<C> x1;
1405        GenWordPolynomial<C> x2;
1406        while (!r.isZERO()) {
1407            qr = q.quotientRemainder(r);
1408            q = qr[0];
1409            x1 = c1.subtract(q.multiply(d1));
1410            x2 = c2.subtract(q.multiply(d2));
1411            c1 = d1;
1412            c2 = d2;
1413            d1 = x1;
1414            d2 = x2;
1415            q = r;
1416            r = qr[1];
1417        }
1418        // normalize ldcf(q) to 1, i.e. make monic
1419        C g = q.leadingBaseCoefficient();
1420        if (g.isUnit()) {
1421            C h = g.inverse();
1422            q = q.multiply(h);
1423            c1 = c1.multiply(h);
1424            c2 = c2.multiply(h);
1425        }
1426        //assert ( ((c1.multiply(this)).sum( c2.multiply(S)).equals(q) )); 
1427        ret[0] = q;
1428        ret[1] = c1;
1429        ret[2] = c2;
1430        return ret;
1431    }
1432
1433
1434    /**
1435     * GenWordPolynomial half extended greatest common divisor. Only for
1436     * univariate polynomials over fields.
1437     * @param S GenWordPolynomial.
1438     * @return [ gcd(this,S), a ] with a*this + b*S = gcd(this,S).
1439     */
1440    @SuppressWarnings("unchecked")
1441    public GenWordPolynomial<C>[] hegcd(GenWordPolynomial<C> S) {
1442        GenWordPolynomial<C>[] ret = new GenWordPolynomial[2];
1443        ret[0] = null;
1444        ret[1] = null;
1445        if (S == null || S.isZERO()) {
1446            ret[0] = this;
1447            ret[1] = this.ring.getONE();
1448            return ret;
1449        }
1450        if (this.isZERO()) {
1451            ret[0] = S;
1452            return ret;
1453        }
1454        if (ring.alphabet.length() != 1) {
1455            throw new IllegalArgumentException("no univariate polynomial " + ring);
1456        }
1457        GenWordPolynomial<C>[] qr;
1458        GenWordPolynomial<C> q = this;
1459        GenWordPolynomial<C> r = S;
1460        GenWordPolynomial<C> c1 = ring.getONE().copy();
1461        GenWordPolynomial<C> d1 = ring.getZERO().copy();
1462        GenWordPolynomial<C> x1;
1463        while (!r.isZERO()) {
1464            qr = q.quotientRemainder(r);
1465            q = qr[0];
1466            x1 = c1.subtract(q.multiply(d1));
1467            c1 = d1;
1468            d1 = x1;
1469            q = r;
1470            r = qr[1];
1471        }
1472        // normalize ldcf(q) to 1, i.e. make monic
1473        C g = q.leadingBaseCoefficient();
1474        if (g.isUnit()) {
1475            C h = g.inverse();
1476            q = q.multiply(h);
1477            c1 = c1.multiply(h);
1478        }
1479        //assert ( ((c1.multiply(this)).remainder(S).equals(q) )); 
1480        ret[0] = q;
1481        ret[1] = c1;
1482        return ret;
1483    }
1484
1485
1486    /**
1487     * GenWordPolynomial inverse. Required by RingElem. Throws not invertible
1488     * exception.
1489     */
1490    public GenWordPolynomial<C> inverse() {
1491        if (isUnit()) { // only possible if ldbcf is unit
1492            C c = leadingBaseCoefficient().inverse();
1493            return ring.getONE().multiply(c);
1494        }
1495        throw new NotInvertibleException("element not invertible " + this + " :: " + ring);
1496    }
1497
1498
1499    /**
1500     * GenWordPolynomial modular inverse. Only for univariate polynomials over
1501     * fields.
1502     * @param m GenWordPolynomial.
1503     * @return a with with a*this = 1 mod m.
1504     */
1505    public GenWordPolynomial<C> modInverse(GenWordPolynomial<C> m) {
1506        if (this.isZERO()) {
1507            throw new NotInvertibleException("zero is not invertible");
1508        }
1509        GenWordPolynomial<C>[] hegcd = this.hegcd(m);
1510        GenWordPolynomial<C> a = hegcd[0];
1511        if (!a.isUnit()) { // gcd != 1
1512            throw new NotInvertibleException("element not invertible, gcd != 1");
1513        }
1514        GenWordPolynomial<C> b = hegcd[1];
1515        if (b.isZERO()) { // when m divides this, e.g. m.isUnit()
1516            throw new NotInvertibleException("element not invertible, divisible by modul");
1517        }
1518        return b;
1519    }
1520
1521
1522    /**
1523     * Iterator over coefficients.
1524     * @return val.values().iterator().
1525     */
1526    public Iterator<C> coefficientIterator() {
1527        return val.values().iterator();
1528    }
1529
1530
1531    /**
1532     * Iterator over words.
1533     * @return val.keySet().iterator().
1534     */
1535    public Iterator<Word> wordIterator() {
1536        return val.keySet().iterator();
1537    }
1538
1539
1540    /**
1541     * Iterator over monomials.
1542     * @return a PolyIterator.
1543     */
1544    public Iterator<WordMonomial<C>> iterator() {
1545        return new WordPolyIterator<C>(val);
1546    }
1547
1548
1549    /**
1550     * Map a unary function to the coefficients.
1551     * @param f evaluation functor.
1552     * @return new polynomial with coefficients f(this(e)).
1553     */
1554    public GenWordPolynomial<C> map(final UnaryFunctor<? super C, C> f) {
1555        GenWordPolynomial<C> n = ring.getZERO().copy();
1556        SortedMap<Word, C> nv = n.val;
1557        for (WordMonomial<C> m : this) {
1558            //logger.info("m = {}", m);
1559            C c = f.eval(m.c);
1560            if (c != null && !c.isZERO()) {
1561                nv.put(m.e, c);
1562            }
1563        }
1564        return n;
1565    }
1566
1567
1568    /**
1569     * GenWordPolynomial contraction.
1570     * @param fac GenWordPolynomialRing.
1571     * @return this contracted to fac ring, if this in fac ring, null else.
1572     */
1573    public GenWordPolynomial<C> contract(GenWordPolynomialRing<C> fac) {
1574        if (fac == null) {
1575            throw new IllegalArgumentException("fac ring may not be null");
1576        }
1577        GenWordPolynomial<C> S = fac.getZERO();
1578        if (this.isZERO()) {
1579            return S;
1580        }
1581        WordFactory wfac = fac.alphabet;
1582        //eventually: assert (ring.alphabet.isSubFactory(fac.alphabet));
1583        S = S.copy();
1584        SortedMap<Word, C> sv = S.val;
1585        SortedMap<Word, C> nv = this.val;
1586        for (Map.Entry<Word, C> me : nv.entrySet()) {
1587            Word e = me.getKey();
1588            Word ec = wfac.contract(e);
1589            if (ec == null) { // not contractable
1590                return fac.getZERO(); // or null?
1591            }
1592            C y = me.getValue();
1593            if (sv.get(ec) != null) { // eventually need sum
1594                throw new RuntimeException("x != null: need sum " + sv.get(ec) + " + " + y);
1595            }
1596            sv.put(ec, y);
1597        }
1598        return S;
1599    }
1600
1601}