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