001 /*
002 * $Id: GenPolynomialRing.java 3641 2011-05-22 12:23:54Z kredel $
003 */
004
005 package edu.jas.poly;
006
007
008 import java.io.IOException;
009 import java.io.Reader;
010 import java.io.StringReader;
011 import java.math.BigInteger;
012 import java.util.ArrayList;
013 import java.util.Arrays;
014 import java.util.HashSet;
015 import java.util.Iterator;
016 import java.util.List;
017 import java.util.Random;
018 import java.util.Set;
019
020 import org.apache.log4j.Logger;
021
022 import edu.jas.arith.ModIntegerRing;
023 import edu.jas.kern.PreemptStatus;
024 import edu.jas.kern.PrettyPrint;
025 import edu.jas.kern.Scripting;
026 import edu.jas.structure.RingElem;
027 import edu.jas.structure.RingFactory;
028 import edu.jas.util.CartesianProduct;
029 import edu.jas.util.CartesianProductInfinite;
030 import edu.jas.util.LongIterable;
031
032
033 /**
034 * GenPolynomialRing generic polynomial factory implementing RingFactory;
035 * Factory for n-variate ordered polynomials over C. Almost immutable object,
036 * except variable names.
037 * @param <C> coefficient type
038 * @author Heinz Kredel
039 */
040
041 public class GenPolynomialRing<C extends RingElem<C>> implements RingFactory<GenPolynomial<C>>, Cloneable,
042 Iterable<GenPolynomial<C>> {
043
044
045 /**
046 * The factory for the coefficients.
047 */
048 public final RingFactory<C> coFac;
049
050
051 /**
052 * The number of variables.
053 */
054 public final int nvar;
055
056
057 /**
058 * The term order.
059 */
060 public final TermOrder tord;
061
062
063 /**
064 * True for partially reversed variables.
065 */
066 protected boolean partial;
067
068
069 /**
070 * The names of the variables. This value can be modified.
071 */
072 protected String[] vars;
073
074
075 /**
076 * The names of all known variables.
077 */
078 private static Set<String> knownVars = new HashSet<String>();
079
080
081 /**
082 * The constant polynomial 0 for this ring.
083 */
084 public final GenPolynomial<C> ZERO;
085
086
087 /**
088 * The constant polynomial 1 for this ring.
089 */
090 public final GenPolynomial<C> ONE;
091
092
093 /**
094 * The constant exponent vector 0 for this ring.
095 */
096 public final ExpVector evzero;
097
098
099 /**
100 * A default random sequence generator.
101 */
102 protected final static Random random = new Random();
103
104
105 /**
106 * Indicator if this ring is a field.
107 */
108 protected int isField = -1; // initially unknown
109
110
111 /**
112 * Log4j logger object.
113 */
114 private static final Logger logger = Logger.getLogger(GenPolynomialRing.class);
115
116
117 /**
118 * Flag to enable if preemptive interrrupt is checked.
119 */
120 final boolean checkPreempt = PreemptStatus.isAllowed();
121
122
123 /**
124 * The constructor creates a polynomial factory object with the default term
125 * order.
126 * @param cf factory for coefficients of type C.
127 * @param n number of variables.
128 */
129 public GenPolynomialRing(RingFactory<C> cf, int n) {
130 this(cf, n, new TermOrder(), null);
131 }
132
133
134 /**
135 * The constructor creates a polynomial factory object.
136 * @param cf factory for coefficients of type C.
137 * @param n number of variables.
138 * @param t a term order.
139 */
140 public GenPolynomialRing(RingFactory<C> cf, int n, TermOrder t) {
141 this(cf, n, t, null);
142 }
143
144
145 /**
146 * The constructor creates a polynomial factory object.
147 * @param cf factory for coefficients of type C.
148 * @param v names for the variables.
149 */
150 public GenPolynomialRing(RingFactory<C> cf, String[] v) {
151 this(cf, v.length, v);
152 }
153
154
155 /**
156 * The constructor creates a polynomial factory object.
157 * @param cf factory for coefficients of type C.
158 * @param n number of variables.
159 * @param v names for the variables.
160 */
161 public GenPolynomialRing(RingFactory<C> cf, int n, String[] v) {
162 this(cf, n, new TermOrder(), v);
163 }
164
165
166 /**
167 * The constructor creates a polynomial factory object.
168 * @param cf factory for coefficients of type C.
169 * @param t a term order.
170 * @param v names for the variables.
171 */
172 public GenPolynomialRing(RingFactory<C> cf, TermOrder t, String[] v) {
173 this(cf, v.length, t, v);
174 }
175
176
177 /**
178 * The constructor creates a polynomial factory object.
179 * @param cf factory for coefficients of type C.
180 * @param n number of variables.
181 * @param t a term order.
182 * @param v names for the variables.
183 */
184 public GenPolynomialRing(RingFactory<C> cf, int n, TermOrder t, String[] v) {
185 coFac = cf;
186 nvar = n;
187 tord = t;
188 partial = false;
189 vars = v;
190 ZERO = new GenPolynomial<C>(this);
191 C coeff = coFac.getONE();
192 evzero = ExpVector.create(nvar);
193 ONE = new GenPolynomial<C>(this, coeff, evzero);
194 if (vars == null && PrettyPrint.isTrue()) {
195 vars = newVars("x", nvar);
196 } else {
197 if (vars.length != nvar) {
198 throw new IllegalArgumentException("incompatible variable size " + vars.length + ", " + nvar);
199 }
200 addVars(vars);
201 }
202 }
203
204
205 /**
206 * The constructor creates a polynomial factory object with the the same
207 * term order, number of variables and variable names as the given
208 * polynomial factory, only the coefficient factories differ.
209 * @param cf factory for coefficients of type C.
210 * @param o other polynomial ring.
211 */
212 public GenPolynomialRing(RingFactory<C> cf, GenPolynomialRing o) {
213 this(cf, o.nvar, o.tord, o.getVars());
214 }
215
216
217 /**
218 * Clone this factory.
219 * @see java.lang.Object#clone()
220 */
221 @Override
222 public GenPolynomialRing<C> clone() {
223 return new GenPolynomialRing<C>(coFac, this);
224 }
225
226
227 /**
228 * Get the String representation.
229 * @see java.lang.Object#toString()
230 */
231 @Override
232 public String toString() {
233 String res = null;
234 if (PrettyPrint.isTrue()) {
235 String scf = coFac.getClass().getSimpleName();
236 if (coFac instanceof AlgebraicNumberRing) {
237 AlgebraicNumberRing an = (AlgebraicNumberRing) coFac;
238 //String[] v = an.ring.vars;
239 res = "AN[ (" + an.ring.varsToString() + ") (" + an.toString() + ") ]";
240 }
241 if (coFac instanceof GenPolynomialRing) {
242 GenPolynomialRing rf = (GenPolynomialRing) coFac;
243 //String[] v = rf.vars;
244 RingFactory cf = rf.coFac;
245 String cs;
246 if (cf instanceof ModIntegerRing) {
247 cs = cf.toString();
248 } else {
249 cs = " " + cf.getClass().getSimpleName();
250 }
251 //res = "IntFunc" + "{" + cs + "( " + rf.varsToString() + " )" + " } ";
252 res = "IntFunc" + "( " + rf.toString() + " )";
253 }
254 if (((Object) coFac) instanceof ModIntegerRing) {
255 ModIntegerRing mn = (ModIntegerRing) ((Object) coFac);
256 res = "Mod " + mn.getModul() + " ";
257 }
258 if (res == null) {
259 if (coFac != null) {
260 res = coFac.toString();
261 if (res.matches("[0-9].*")) {
262 res = scf;
263 }
264 } else {
265 res = scf;
266 }
267 }
268 res += "( " + varsToString() + " ) " + tord.toString() + " ";
269 } else {
270 res = this.getClass().getSimpleName() + "[ " + coFac.toString() + " ";
271 // + coFac.getClass().getSimpleName();
272 if (coFac instanceof AlgebraicNumberRing) {
273 AlgebraicNumberRing an = (AlgebraicNumberRing) coFac;
274 res = "AN[ (" + an.ring.varsToString() + ") (" + an.modul + ") ]";
275 }
276 if (coFac instanceof GenPolynomialRing) {
277 GenPolynomialRing rf = (GenPolynomialRing) coFac;
278 //String[] v = rf.vars;
279 RingFactory cf = rf.coFac;
280 String cs;
281 if (cf instanceof ModIntegerRing) {
282 cs = cf.toString();
283 } else {
284 cs = " " + cf.getClass().getSimpleName();
285 }
286 //res = "IntFunc{ " + cs + "( " + rf.varsToString() + " )" + " } ";
287 res = "IntFunc" + "( " + rf.toString() + " )";
288 }
289 if (((Object) coFac) instanceof ModIntegerRing) {
290 ModIntegerRing mn = (ModIntegerRing) ((Object) coFac);
291 res = "Mod " + mn.getModul() + " ";
292 }
293 //res += ", " + nvar + ", " + tord.toString() + ", " + varsToString() + ", " + partial + " ]";
294 res += "( " + varsToString() + " ) " + tord.toString() + " ]";
295 }
296 return res;
297 }
298
299
300 /**
301 * Get a scripting compatible string representation.
302 * @return script compatible representation for this Element.
303 * @see edu.jas.structure.Element#toScript()
304 */
305 //JAVA6only: @Override
306 public String toScript() {
307 StringBuffer s = new StringBuffer();
308 switch (Scripting.getLang()) {
309 case Ruby:
310 s.append("PolyRing.new(");
311 break;
312 case Python:
313 default:
314 s.append("PolyRing(");
315 }
316 if (coFac instanceof RingElem) {
317 s.append(((RingElem<C>) coFac).toScriptFactory());
318 } else {
319 s.append(coFac.toScript().trim());
320 }
321 s.append(",\"" + varsToString() + "\",");
322 String to = tord.toString();
323 if (tord.getEvord() == TermOrder.INVLEX) {
324 to = "PolyRing.lex";
325 }
326 if (tord.getEvord() == TermOrder.IGRLEX) {
327 to = "PolyRing.grad";
328 }
329 s.append(to);
330 s.append(")");
331 return s.toString();
332 }
333
334
335 /**
336 * Comparison with any other object.
337 * @see java.lang.Object#equals(java.lang.Object)
338 */
339 @Override
340 @SuppressWarnings("unchecked")
341 public boolean equals(Object other) {
342 if (!(other instanceof GenPolynomialRing)) {
343 return false;
344 }
345 GenPolynomialRing<C> oring = null;
346 try {
347 oring = (GenPolynomialRing<C>) other;
348 } catch (ClassCastException ignored) {
349 }
350 if (oring == null) {
351 return false;
352 }
353 if (nvar != oring.nvar) {
354 return false;
355 }
356 if (!coFac.equals(oring.coFac)) {
357 return false;
358 }
359 if (!tord.equals(oring.tord)) {
360 return false;
361 }
362 // same variables required ?
363 if (!Arrays.equals(vars, oring.vars)) {
364 return false;
365 }
366 return true;
367 }
368
369
370 /**
371 * Hash code for this polynomial ring.
372 * @see java.lang.Object#hashCode()
373 */
374 @Override
375 public int hashCode() {
376 int h;
377 h = (nvar << 27);
378 h += (coFac.hashCode() << 11);
379 h += tord.hashCode();
380 return h;
381 }
382
383
384 /**
385 * Get the variable names.
386 * @return vars.
387 */
388 public String[] getVars() {
389 return vars;
390 }
391
392
393 /**
394 * Set the variable names.
395 * @return old vars.
396 */
397 public String[] setVars(String[] v) {
398 String[] t = vars;
399 vars = v;
400 return t;
401 }
402
403
404 /**
405 * Get a String representation of the variable names.
406 * @return names seperated by commas.
407 */
408 public String varsToString() {
409 String s = "";
410 if (vars == null) {
411 return s + "#" + nvar;
412 }
413 for (int i = 0; i < vars.length; i++) {
414 if (i != 0) {
415 s += ", ";
416 }
417 s += vars[i];
418 }
419 return s;
420 }
421
422
423 /**
424 * Get the zero element from the coefficients.
425 * @return 0 as C.
426 */
427 public C getZEROCoefficient() {
428 return coFac.getZERO();
429 }
430
431
432 /**
433 * Get the one element from the coefficients.
434 * @return 1 as C.
435 */
436 public C getONECoefficient() {
437 return coFac.getONE();
438 }
439
440
441 /**
442 * Get the zero element.
443 * @return 0 as GenPolynomial<C>.
444 */
445 public GenPolynomial<C> getZERO() {
446 return ZERO;
447 }
448
449
450 /**
451 * Get the one element.
452 * @return 1 as GenPolynomial<C>.
453 */
454 public GenPolynomial<C> getONE() {
455 return ONE;
456 }
457
458
459 /**
460 * Query if this ring is commutative.
461 * @return true if this ring is commutative, else false.
462 */
463 public boolean isCommutative() {
464 return coFac.isCommutative();
465 }
466
467
468 /**
469 * Query if this ring is associative.
470 * @return true if this ring is associative, else false.
471 */
472 public boolean isAssociative() {
473 return coFac.isAssociative();
474 }
475
476
477 /**
478 * Query if this ring is a field.
479 * @return false.
480 */
481 public boolean isField() {
482 if (isField > 0) {
483 return true;
484 }
485 if (isField == 0) {
486 return false;
487 }
488 if (coFac.isField() && nvar == 0) {
489 isField = 1;
490 return true;
491 }
492 isField = 0;
493 return false;
494 }
495
496
497 /**
498 * Characteristic of this ring.
499 * @return characteristic of this ring.
500 */
501 public java.math.BigInteger characteristic() {
502 return coFac.characteristic();
503 }
504
505
506 /**
507 * Get a (constant) GenPolynomial<C> element from a long value.
508 * @param a long.
509 * @return a GenPolynomial<C>.
510 */
511 public GenPolynomial<C> fromInteger(long a) {
512 return new GenPolynomial<C>(this, coFac.fromInteger(a), evzero);
513 }
514
515
516 /**
517 * Get a (constant) GenPolynomial<C> element from a BigInteger value.
518 * @param a BigInteger.
519 * @return a GenPolynomial<C>.
520 */
521 public GenPolynomial<C> fromInteger(BigInteger a) {
522 return new GenPolynomial<C>(this, coFac.fromInteger(a), evzero);
523 }
524
525
526 /**
527 * Random polynomial. Generates a random polynomial with k = 5, l = n, d =
528 * (nvar == 1) ? n : 3, q = (nvar == 1) ? 0.7 : 0.3.
529 * @param n number of terms.
530 * @return a random polynomial.
531 */
532 public GenPolynomial<C> random(int n) {
533 return random(n, random);
534 }
535
536
537 /**
538 * Random polynomial. Generates a random polynomial with k = 5, l = n, d =
539 * (nvar == 1) ? n : 3, q = (nvar == 1) ? 0.7 : 0.3.
540 * @param n number of terms.
541 * @param rnd is a source for random bits.
542 * @return a random polynomial.
543 */
544 public GenPolynomial<C> random(int n, Random rnd) {
545 if (nvar == 1) {
546 return random(3, n, n, 0.7f, rnd);
547 }
548 return random(5, n, 3, 0.3f, rnd);
549 }
550
551
552 /**
553 * Generate a random polynomial.
554 * @param k bitsize of random coefficients.
555 * @param l number of terms.
556 * @param d maximal degree in each variable.
557 * @param q density of nozero exponents.
558 * @return a random polynomial.
559 */
560 public GenPolynomial<C> random(int k, int l, int d, float q) {
561 return random(k, l, d, q, random);
562 }
563
564
565 /**
566 * Generate a random polynomial.
567 * @param k bitsize of random coefficients.
568 * @param l number of terms.
569 * @param d maximal degree in each variable.
570 * @param q density of nozero exponents.
571 * @param rnd is a source for random bits.
572 * @return a random polynomial.
573 */
574 public GenPolynomial<C> random(int k, int l, int d, float q, Random rnd) {
575 GenPolynomial<C> r = getZERO(); //.clone() or copy( ZERO );
576 ExpVector e;
577 C a;
578 // add l random coeffs and exponents
579 for (int i = 0; i < l; i++) {
580 e = ExpVector.EVRAND(nvar, d, q, rnd);
581 a = coFac.random(k, rnd);
582 r = r.sum(a, e); // somewhat inefficient but clean
583 //System.out.println("e = " + e + " a = " + a);
584 }
585 // System.out.println("r = " + r);
586 return r;
587 }
588
589
590 /**
591 * Copy polynomial c.
592 * @param c
593 * @return a copy of c.
594 */
595 public GenPolynomial<C> copy(GenPolynomial<C> c) {
596 //System.out.println("GP copy = " + this);
597 return new GenPolynomial<C>(this, c.val);
598 }
599
600
601 /**
602 * Parse a polynomial with the use of GenPolynomialTokenizer.
603 * @param s String.
604 * @return GenPolynomial from s.
605 */
606 public GenPolynomial<C> parse(String s) {
607 String val = s;
608 if ( !s.contains("|") ) {
609 val = val.replace("{","").replace("}","");
610 }
611 return parse(new StringReader(val));
612 }
613
614
615 /**
616 * Parse a polynomial with the use of GenPolynomialTokenizer.
617 * @param r Reader.
618 * @return next GenPolynomial from r.
619 */
620 @SuppressWarnings("unchecked")
621 public GenPolynomial<C> parse(Reader r) {
622 GenPolynomialTokenizer pt = new GenPolynomialTokenizer(this, r);
623 GenPolynomial<C> p = null;
624 try {
625 p = (GenPolynomial<C>) pt.nextPolynomial();
626 } catch (IOException e) {
627 logger.error(e.toString() + " parse " + this);
628 p = ZERO;
629 }
630 return p;
631 }
632
633
634 /**
635 * Generate univariate polynomial in a given variable.
636 * @param i the index of the variable.
637 * @return X_i as univariate polynomial.
638 */
639 public GenPolynomial<C> univariate(int i) {
640 return univariate(0, i, 1L);
641 }
642
643
644 /**
645 * Generate univariate polynomial in a given variable with given exponent.
646 * @param i the index of the variable.
647 * @param e the exponent of the variable.
648 * @return X_i^e as univariate polynomial.
649 */
650 public GenPolynomial<C> univariate(int i, long e) {
651 return univariate(0, i, e);
652 }
653
654
655 /**
656 * Generate univariate polynomial in a given variable with given exponent.
657 * @param modv number of module variables.
658 * @param i the index of the variable.
659 * @param e the exponent of the variable.
660 * @return X_i^e as univariate polynomial.
661 */
662 public GenPolynomial<C> univariate(int modv, int i, long e) {
663 GenPolynomial<C> p = getZERO();
664 int r = nvar - modv;
665 if (0 <= i && i < r) {
666 C one = coFac.getONE();
667 ExpVector f = ExpVector.create(r, i, e);
668 if (modv > 0) {
669 f = f.extend(modv, 0, 0l);
670 }
671 p = p.sum(one, f);
672 }
673 return p;
674 }
675
676
677 /**
678 * Get the generating elements excluding the generators for the coefficient
679 * ring.
680 * @return a list of generating elements for this ring.
681 */
682 public List<GenPolynomial<C>> getGenerators() {
683 List<? extends GenPolynomial<C>> univs = univariateList();
684 List<GenPolynomial<C>> gens = new ArrayList<GenPolynomial<C>>(univs.size() + 1);
685 gens.add(getONE());
686 gens.addAll(univs);
687 return gens;
688 }
689
690
691 /**
692 * Get a list of the generating elements.
693 * @return list of generators for the algebraic structure.
694 * @see edu.jas.structure.ElemFactory#generators()
695 */
696 public List<GenPolynomial<C>> generators() {
697 List<? extends C> cogens = coFac.generators();
698 List<? extends GenPolynomial<C>> univs = univariateList();
699 List<GenPolynomial<C>> gens = new ArrayList<GenPolynomial<C>>(univs.size() + cogens.size());
700 for (C c : cogens) {
701 gens.add(getONE().multiply(c));
702 }
703 gens.addAll(univs);
704 return gens;
705 }
706
707
708 /**
709 * Is this structure finite or infinite.
710 * @return true if this structure is finite, else false.
711 * @see edu.jas.structure.ElemFactory#isFinite()
712 */
713 public boolean isFinite() {
714 return (nvar == 0) && coFac.isFinite();
715 }
716
717
718 /**
719 * Generate list of univariate polynomials in all variables.
720 * @return List(X_1,...,X_n) a list of univariate polynomials.
721 */
722 public List<? extends GenPolynomial<C>> univariateList() {
723 return univariateList(0, 1L);
724 }
725
726
727 /**
728 * Generate list of univariate polynomials in all variables.
729 * @param modv number of module variables.
730 * @return List(X_1,...,X_n) a list of univariate polynomials.
731 */
732 public List<? extends GenPolynomial<C>> univariateList(int modv) {
733 return univariateList(modv, 1L);
734 }
735
736
737 /**
738 * Generate list of univariate polynomials in all variables with given
739 * exponent.
740 * @param modv number of module variables.
741 * @param e the exponent of the variables.
742 * @return List(X_1^e,...,X_n^e) a list of univariate polynomials.
743 */
744 public List<? extends GenPolynomial<C>> univariateList(int modv, long e) {
745 List<GenPolynomial<C>> pols = new ArrayList<GenPolynomial<C>>(nvar);
746 int nm = nvar - modv;
747 for (int i = 0; i < nm; i++) {
748 GenPolynomial<C> p = univariate(modv, nm - 1 - i, e);
749 pols.add(p);
750 }
751 return pols;
752 }
753
754
755 /**
756 * Extend variables. Used e.g. in module embedding. Extend number of
757 * variables by i.
758 * @param i number of variables to extend.
759 * @return extended polynomial ring factory.
760 */
761 public GenPolynomialRing<C> extend(int i) {
762 // add module variable names
763 String[] v = newVars("e", i);
764 return extend(v);
765 }
766
767
768 /**
769 * Extend variables. Used e.g. in module embedding. Extend number of
770 * variables by length(vn).
771 * @param vn names for extended variables.
772 * @return extended polynomial ring factory.
773 */
774 public GenPolynomialRing<C> extend(String[] vn) {
775 if (vn == null || vars == null) {
776 throw new IllegalArgumentException("vn and vars may not be null");
777 }
778 int i = vn.length;
779 String[] v = new String[vars.length + i];
780 for (int k = 0; k < vars.length; k++) {
781 v[k] = vars[k];
782 }
783 for (int k = 0; k < vn.length; k++) {
784 v[vars.length + k] = vn[k];
785 }
786
787 TermOrder to = tord.extend(nvar, i);
788 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar + i, to, v);
789 return pfac;
790 }
791
792
793 /**
794 * Extend lower variables. Extend number of variables by i.
795 * @param i number of variables to extend.
796 * @return extended polynomial ring factory.
797 */
798 public GenPolynomialRing<C> extendLower(int i) {
799 String[] v = newVars("e", i);
800 return extendLower(v);
801 }
802
803
804 /**
805 * Extend lower variables. Extend number of variables by length(vn).
806 * @param vn names for extended lower variables.
807 * @return extended polynomial ring factory.
808 */
809 public GenPolynomialRing<C> extendLower(String[] vn) {
810 if (vn == null || vars == null) {
811 throw new IllegalArgumentException("vn and vars may not be null");
812 }
813 int i = vn.length;
814 String[] v = new String[vars.length + i];
815 for (int k = 0; k < vn.length; k++) {
816 v[k] = vn[k];
817 }
818 for (int k = 0; k < vars.length; k++) {
819 v[vn.length + k] = vars[k];
820 }
821 TermOrder to = tord.extendLower(nvar, i);
822 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar + i, to, v);
823 return pfac;
824 }
825
826
827 /**
828 * Contract variables. Used e.g. in module embedding. Contract number of
829 * variables by i.
830 * @param i number of variables to remove.
831 * @return contracted polynomial ring factory.
832 */
833 public GenPolynomialRing<C> contract(int i) {
834 String[] v = null;
835 if (vars != null) {
836 v = new String[vars.length - i];
837 for (int j = 0; j < vars.length - i; j++) {
838 v[j] = vars[j];
839 }
840 }
841 TermOrder to = tord.contract(i, nvar - i);
842 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar - i, to, v);
843 return pfac;
844 }
845
846
847 /**
848 * Recursive representation as polynomial with i main variables.
849 * @param i number of main variables.
850 * @return recursive polynomial ring factory.
851 */
852 public GenPolynomialRing<GenPolynomial<C>> recursive(int i) {
853 if ( i <= 0 || i >= nvar ) {
854 throw new IllegalArgumentException("wrong: 0 < " + i + " < " + nvar);
855 }
856 GenPolynomialRing<C> cfac = contract(i);
857 String[] v = null;
858 if (vars != null) {
859 v = new String[i];
860 int k = 0;
861 for (int j = nvar-i; j < nvar; j++) {
862 v[k++] = vars[j];
863 }
864 }
865 TermOrder to = tord.contract(0,i); // ??
866 GenPolynomialRing<GenPolynomial<C>> pfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, i, to, v);
867 return pfac;
868 }
869
870
871 /**
872 * Reverse variables. Used e.g. in opposite rings.
873 * @return polynomial ring factory with reversed variables.
874 */
875 public GenPolynomialRing<C> reverse() {
876 return reverse(false);
877 }
878
879
880 /**
881 * Reverse variables. Used e.g. in opposite rings.
882 * @param partial true for partialy reversed term orders.
883 * @return polynomial ring factory with reversed variables.
884 */
885 public GenPolynomialRing<C> reverse(boolean partial) {
886 String[] v = null;
887 if (vars != null) { // vars are not inversed
888 v = new String[vars.length];
889 int k = tord.getSplit();
890 if (partial && k < vars.length) {
891 for (int j = 0; j < k; j++) {
892 v[vars.length - k + j] = vars[vars.length - 1 - j];
893 }
894 for (int j = 0; j < vars.length - k; j++) {
895 v[j] = vars[j];
896 }
897 } else {
898 for (int j = 0; j < vars.length; j++) {
899 v[j] = vars[vars.length - 1 - j];
900 }
901 }
902 }
903 TermOrder to = tord.reverse(partial);
904 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar, to, v);
905 pfac.partial = partial;
906 return pfac;
907 }
908
909
910 /**
911 * Get PolynomialComparator.
912 * @return polynomial comparator.
913 */
914 public PolynomialComparator<C> getComparator() {
915 return new PolynomialComparator<C>(tord, false);
916 }
917
918
919 /**
920 * Get PolynomialComparator.
921 * @param rev for reverse comparator.
922 * @return polynomial comparator.
923 */
924 public PolynomialComparator<C> getComparator(boolean rev) {
925 return new PolynomialComparator<C>(tord, rev);
926 }
927
928
929 /**
930 * New variable names. Generate new names for variables,
931 * @param prefix name prefix.
932 * @param n number of variables.
933 * @return new variable names.
934 */
935 public static String[] newVars(String prefix, int n) {
936 String[] vars = new String[n];
937 synchronized (knownVars) {
938 int m = knownVars.size();
939 String name = prefix + m;
940 for (int i = 0; i < n; i++) {
941 while (knownVars.contains(name)) {
942 m++;
943 name = prefix + m;
944 }
945 vars[i] = name;
946 //System.out.println("new variable: " + name);
947 knownVars.add(name);
948 m++;
949 name = prefix + m;
950 }
951 }
952 return vars;
953 }
954
955
956 /**
957 * New variable names. Generate new names for variables,
958 * @param prefix name prefix.
959 * @return new variable names.
960 */
961 public String[] newVars(String prefix) {
962 return newVars(prefix, nvar);
963 }
964
965
966 /**
967 * New variable names. Generate new names for variables,
968 * @param n number of variables.
969 * @return new variable names.
970 */
971 public static String[] newVars(int n) {
972 return newVars("x", n);
973 }
974
975
976 /**
977 * New variable names. Generate new names for variables,
978 * @return new variable names.
979 */
980 public String[] newVars() {
981 return newVars(nvar);
982 }
983
984
985 /**
986 * Add variable names.
987 * @param vars variable names to be recorded.
988 */
989 public static void addVars(String[] vars) {
990 if (vars == null) {
991 return;
992 }
993 synchronized (knownVars) {
994 for (int i = 0; i < vars.length; i++) {
995 knownVars.add(vars[i]); // eventualy names 'overwritten'
996 }
997 }
998 }
999
1000
1001 /**
1002 * Get a GenPolynomial iterator.
1003 * @return a iterator over all polynomials.
1004 */
1005 public Iterator<GenPolynomial<C>> iterator() {
1006 if (coFac.isFinite()) {
1007 return new GenPolynomialIterator<C>(this);
1008 }
1009 logger.warn("ring of coefficients " + coFac
1010 + " is infinite, constructing iterator only over monomials");
1011 return new GenPolynomialMonomialIterator<C>(this);
1012 //throw new IllegalArgumentException("only for finite iterable coefficients implemented");
1013 }
1014
1015 }
1016
1017
1018 /**
1019 * Polynomial iterator.
1020 * @author Heinz Kredel
1021 */
1022 class GenPolynomialIterator<C extends RingElem<C>> implements Iterator<GenPolynomial<C>> {
1023
1024
1025 /**
1026 * data structure.
1027 */
1028 final GenPolynomialRing<C> ring;
1029
1030
1031 final Iterator<List<Long>> eviter;
1032
1033
1034 final List<ExpVector> powers;
1035
1036
1037 final List<Iterable<C>> coeffiter;
1038
1039
1040 Iterator<List<C>> itercoeff;
1041
1042
1043 GenPolynomial<C> current;
1044
1045
1046 /**
1047 * Polynomial iterator constructor.
1048 */
1049 public GenPolynomialIterator(GenPolynomialRing<C> fac) {
1050 ring = fac;
1051 LongIterable li = new LongIterable();
1052 li.setNonNegativeIterator();
1053 List<Iterable<Long>> tlist = new ArrayList<Iterable<Long>>(ring.nvar);
1054 for (int i = 0; i < ring.nvar; i++) {
1055 tlist.add(li);
1056 }
1057 CartesianProductInfinite<Long> ei = new CartesianProductInfinite<Long>(tlist);
1058 eviter = ei.iterator();
1059 RingFactory<C> cf = ring.coFac;
1060 coeffiter = new ArrayList<Iterable<C>>();
1061 if (cf instanceof Iterable && cf.isFinite()) {
1062 Iterable<C> cfi = (Iterable<C>) cf;
1063 coeffiter.add(cfi);
1064 } else {
1065 throw new IllegalArgumentException("only for finite iterable coefficients implemented");
1066 }
1067 CartesianProduct<C> tuples = new CartesianProduct<C>(coeffiter);
1068 itercoeff = tuples.iterator();
1069 powers = new ArrayList<ExpVector>();
1070 ExpVector e = ExpVector.create(eviter.next());
1071 powers.add(e);
1072 //System.out.println("new e = " + e);
1073 //System.out.println("powers = " + powers);
1074 List<C> c = itercoeff.next();
1075 //System.out.println("coeffs = " + c);
1076 current = new GenPolynomial<C>(ring, c.get(0), e);
1077 }
1078
1079
1080 /**
1081 * Test for availability of a next element.
1082 * @return true if the iteration has more elements, else false.
1083 */
1084 public boolean hasNext() {
1085 return true;
1086 }
1087
1088
1089 /**
1090 * Get next polynomial.
1091 * @return next polynomial.
1092 */
1093 public synchronized GenPolynomial<C> next() {
1094 GenPolynomial<C> res = current;
1095 if (!itercoeff.hasNext()) {
1096 ExpVector e = ExpVector.create(eviter.next());
1097 powers.add(0, e); // add new ev at beginning
1098 //System.out.println("new e = " + e);
1099 //System.out.println("powers = " + powers);
1100 if (coeffiter.size() == 1) { // shorten frist iterator by one element
1101 coeffiter.add(coeffiter.get(0));
1102 Iterable<C> it = coeffiter.get(0);
1103 List<C> elms = new ArrayList<C>();
1104 for (C elm : it) {
1105 elms.add(elm);
1106 }
1107 elms.remove(0);
1108 coeffiter.set(0, elms);
1109 } else {
1110 coeffiter.add(coeffiter.get(1));
1111 }
1112 CartesianProduct<C> tuples = new CartesianProduct<C>(coeffiter);
1113 itercoeff = tuples.iterator();
1114 }
1115 List<C> coeffs = itercoeff.next();
1116 // while ( coeffs.get(0).isZERO() ) {
1117 // System.out.println(" skip zero ");
1118 // coeffs = itercoeff.next(); // skip tuples with zero in first component
1119 // }
1120 //System.out.println("coeffs = " + coeffs);
1121 GenPolynomial<C> pol = ring.getZERO().clone();
1122 int i = 0;
1123 for (ExpVector f : powers) {
1124 C c = coeffs.get(i++);
1125 if (c.isZERO()) {
1126 continue;
1127 }
1128 if (pol.val.get(f) != null) {
1129 System.out.println("error f in pol = " + f + ", " + pol.getMap().get(f));
1130 throw new RuntimeException("error in iterator");
1131 }
1132 pol.doPutToMap(f, c);
1133 }
1134 current = pol;
1135 return res;
1136 }
1137
1138
1139 /**
1140 * Remove an element if allowed.
1141 */
1142 public void remove() {
1143 throw new UnsupportedOperationException("cannnot remove elements");
1144 }
1145 }
1146
1147
1148 /**
1149 * Polynomial monomial iterator.
1150 * @author Heinz Kredel
1151 */
1152 class GenPolynomialMonomialIterator<C extends RingElem<C>> implements Iterator<GenPolynomial<C>> {
1153
1154
1155 /**
1156 * data structure.
1157 */
1158 final GenPolynomialRing<C> ring;
1159
1160
1161 final Iterator<List> iter;
1162
1163
1164 GenPolynomial<C> current;
1165
1166
1167 /**
1168 * Polynomial iterator constructor.
1169 */
1170 @SuppressWarnings("unchecked")
1171 public GenPolynomialMonomialIterator(GenPolynomialRing<C> fac) {
1172 ring = fac;
1173 LongIterable li = new LongIterable();
1174 li.setNonNegativeIterator();
1175 List<Iterable<Long>> tlist = new ArrayList<Iterable<Long>>(ring.nvar);
1176 for (int i = 0; i < ring.nvar; i++) {
1177 tlist.add(li);
1178 }
1179 CartesianProductInfinite<Long> ei = new CartesianProductInfinite<Long>(tlist);
1180 Iterator<List<Long>> eviter = ei.iterator();
1181
1182 RingFactory<C> cf = ring.coFac;
1183 Iterable<C> coeffiter;
1184 if (cf instanceof Iterable && !cf.isFinite()) {
1185 Iterable<C> cfi = (Iterable<C>) cf;
1186 coeffiter = cfi;
1187 } else {
1188 throw new IllegalArgumentException("only for infinite iterable coefficients implemented");
1189 }
1190
1191 // Cantor iterator for exponents and coeffcients
1192 List<Iterable> eci = new ArrayList<Iterable>(2); // no type parameter
1193 eci.add(ei);
1194 eci.add(coeffiter);
1195 CartesianProductInfinite ecp = new CartesianProductInfinite(eci);
1196 iter = ecp.iterator();
1197
1198 List ec = iter.next();
1199 List<Long> ecl = (List<Long>) ec.get(0);
1200 C c = (C) ec.get(1); // zero
1201 ExpVector e = ExpVector.create(ecl);
1202 //System.out.println("exp = " + e);
1203 //System.out.println("coeffs = " + c);
1204 current = new GenPolynomial<C>(ring, c, e);
1205 }
1206
1207
1208 /**
1209 * Test for availability of a next element.
1210 * @return true if the iteration has more elements, else false.
1211 */
1212 public boolean hasNext() {
1213 return true;
1214 }
1215
1216
1217 /**
1218 * Get next polynomial.
1219 * @return next polynomial.
1220 */
1221 public synchronized GenPolynomial<C> next() {
1222 GenPolynomial<C> res = current;
1223
1224 List ec = iter.next();
1225 C c = (C) ec.get(1);
1226 while (c.isZERO()) { // zero already done in first next
1227 ec = iter.next();
1228 c = (C) ec.get(1);
1229 }
1230 List<Long> ecl = (List<Long>) ec.get(0);
1231 ExpVector e = ExpVector.create(ecl);
1232 //System.out.println("exp = " + e);
1233 //System.out.println("coeffs = " + c);
1234 current = new GenPolynomial<C>(ring, c, e);
1235
1236 return res;
1237 }
1238
1239
1240 /**
1241 * Remove an element if allowed.
1242 */
1243 public void remove() {
1244 throw new UnsupportedOperationException("cannnot remove elements");
1245 }
1246 }