001/* 002 * $Id$ 003 */ 004 005package edu.jas.poly; 006 007 008import java.io.IOException; 009import java.io.Reader; 010import java.io.StringReader; 011import java.math.BigInteger; 012import java.util.ArrayList; 013import java.util.Arrays; 014import java.util.Iterator; 015import java.util.List; 016import java.util.Random; 017import java.util.SortedMap; 018import java.util.concurrent.atomic.AtomicLong; 019 020import org.apache.logging.log4j.LogManager; 021import org.apache.logging.log4j.Logger; 022 023import edu.jas.arith.ModIntegerRing; 024import edu.jas.kern.PreemptStatus; 025import edu.jas.kern.PrettyPrint; 026import edu.jas.kern.Scripting; 027import edu.jas.structure.RingElem; 028import edu.jas.structure.StarRingElem; 029import edu.jas.structure.RingFactory; 030import edu.jas.util.CartesianProduct; 031import edu.jas.util.CartesianProductInfinite; 032import edu.jas.util.LongIterable; 033import edu.jas.vector.GenVector; 034import edu.jas.vector.GenMatrix; 035import edu.jas.vector.GenMatrixRing; 036 037 038/** 039 * GenPolynomialRing generic polynomial factory. It implements RingFactory for 040 * n-variate ordered polynomials over coefficients C. The variables commute with 041 * each other and with the coefficients. For non-commutative coefficients some 042 * care is taken to respect the multiplication order. 043 * 044 * Almost immutable object, except variable names. 045 * @param <C> coefficient type 046 * @author Heinz Kredel 047 */ 048 049public class GenPolynomialRing<C extends RingElem<C>> 050 implements RingFactory<GenPolynomial<C>>, Iterable<GenPolynomial<C>> { 051 052 053 /** 054 * The factory for the coefficients. 055 */ 056 public final RingFactory<C> coFac; 057 058 059 /** 060 * The number of variables. 061 */ 062 public final int nvar; 063 064 065 /** 066 * The term order. 067 */ 068 public final TermOrder tord; 069 070 071 /** 072 * True for partially reversed variables. 073 */ 074 protected boolean partial; 075 076 077 /** 078 * The names of the variables. This value can be modified. 079 */ 080 protected String[] vars; 081 082 083 /** 084 * Counter to distinguish new variables. 085 */ 086 private static AtomicLong varCounter = new AtomicLong(0L); 087 088 089 /** 090 * The constant polynomial 0 for this ring. 091 */ 092 public /*final*/ GenPolynomial<C> ZERO; // volatile not meaningful by DL 093 094 095 /** 096 * The constant polynomial 1 for this ring. 097 */ 098 public /*final*/ GenPolynomial<C> ONE; // volatile not meaningful by DL 099 100 101 /** 102 * The constant exponent vector 0 for this ring. 103 */ 104 public final ExpVector evzero; // volatile not meaningful by DL 105 106 107 /** 108 * A default random sequence generator. 109 */ 110 protected final static Random random = new Random(); 111 112 113 /** 114 * Indicator if this ring is a field. 115 */ 116 protected int isField = -1; // initially unknown 117 118 119 /** 120 * Log4j logger object. 121 */ 122 private static final Logger logger = LogManager.getLogger(GenPolynomialRing.class); 123 124 125 /** 126 * Count for number of polynomial creations. 127 */ 128 static int creations = 0; 129 130 131 /** 132 * Flag to enable if preemptive interrupt is checked. 133 */ 134 volatile boolean checkPreempt = PreemptStatus.isAllowed(); 135 136 137 /** 138 * The constructor creates a polynomial factory object with the default term 139 * order. 140 * @param cf factory for coefficients of type C. 141 * @param n number of variables. 142 */ 143 public GenPolynomialRing(RingFactory<C> cf, int n) { 144 this(cf, n, new TermOrder(), null); 145 } 146 147 148 /** 149 * The constructor creates a polynomial factory object. 150 * @param cf factory for coefficients of type C. 151 * @param n number of variables. 152 * @param t a term order. 153 */ 154 public GenPolynomialRing(RingFactory<C> cf, int n, TermOrder t) { 155 this(cf, n, t, null); 156 } 157 158 159 /** 160 * The constructor creates a polynomial factory object. 161 * @param cf factory for coefficients of type C. 162 * @param v names for the variables. 163 */ 164 public GenPolynomialRing(RingFactory<C> cf, String[] v) { 165 this(cf, v.length, v); 166 } 167 168 169 /** 170 * The constructor creates a polynomial factory object. 171 * @param cf factory for coefficients of type C. 172 * @param n number of variables. 173 * @param v names for the variables. 174 */ 175 public GenPolynomialRing(RingFactory<C> cf, int n, String[] v) { 176 this(cf, n, new TermOrder(), v); 177 } 178 179 180 /** 181 * The constructor creates a polynomial factory object. 182 * @param cf factory for coefficients of type C. 183 * @param t a term order. 184 * @param v names for the variables. 185 */ 186 public GenPolynomialRing(RingFactory<C> cf, TermOrder t, String[] v) { 187 this(cf, v.length, t, v); 188 } 189 190 191 /** 192 * The constructor creates a polynomial factory object. 193 * @param cf factory for coefficients of type C. 194 * @param v names for the variables. 195 * @param t a term order. 196 */ 197 public GenPolynomialRing(RingFactory<C> cf, String[] v, TermOrder t) { 198 this(cf, v.length, t, v); 199 } 200 201 202 /** 203 * The constructor creates a polynomial factory object. 204 * @param cf factory for coefficients of type C. 205 * @param n number of variables. 206 * @param t a term order. 207 * @param v names for the variables. 208 */ 209 public GenPolynomialRing(RingFactory<C> cf, int n, TermOrder t, String[] v) { 210 coFac = cf; 211 nvar = n; 212 tord = t; 213 partial = false; 214 if (v == null) { 215 vars = null; 216 } else { 217 vars = Arrays.copyOf(v, v.length); // > Java-5 218 } 219 C coeff = coFac.getONE(); 220 synchronized (this) { 221 evzero = ExpVector.create(nvar); 222 ZERO = new GenPolynomial<C>(this); 223 ONE = new GenPolynomial<C>(this, coeff, evzero); 224 } 225 //logger.debug("ZERO {} {}", ZERO.toString(), ZERO.val); 226 //System.out.println("thread@ZERO: " + Thread.currentThread()); 227 if (vars == null) { 228 if (PrettyPrint.isTrue()) { 229 vars = newVars("x", nvar); 230 } 231 } else { 232 if (vars.length != nvar) { 233 throw new IllegalArgumentException("incompatible variable size " + vars.length + ", " + nvar); 234 } 235 // addVars(vars); 236 } 237 } 238 239 240 /** 241 * The constructor creates a polynomial factory object with the the same 242 * term order, number of variables and variable names as the given 243 * polynomial factory, only the coefficient factories differ. 244 * @param cf factory for coefficients of type C. 245 * @param o other polynomial ring. 246 */ 247 public GenPolynomialRing(RingFactory<C> cf, GenPolynomialRing o) { 248 this(cf, o.nvar, o.tord, o.vars); 249 } 250 251 252 /** 253 * The constructor creates a polynomial factory object with the the same 254 * coefficient factory, number of variables and variable names as the given 255 * polynomial factory, only the term order differs. 256 * @param to term order. 257 * @param o other polynomial ring. 258 */ 259 public GenPolynomialRing(GenPolynomialRing<C> o, TermOrder to) { 260 this(o.coFac, o.nvar, to, o.vars); 261 } 262 263 264 /** 265 * Copy this factory. 266 * @return a clone of this. 267 */ 268 public GenPolynomialRing<C> copy() { 269 return new GenPolynomialRing<C>(coFac, this); 270 } 271 272 273 /** 274 * Get the String representation. 275 * @see java.lang.Object#toString() 276 */ 277 @SuppressWarnings("cast") 278 @Override 279 public String toString() { 280 String res = null; 281 if (PrettyPrint.isTrue()) { // wrong: && coFac != null 282 String scf = coFac.getClass().getSimpleName(); 283 if (coFac instanceof AlgebraicNumberRing) { 284 AlgebraicNumberRing an = (AlgebraicNumberRing) coFac; 285 res = "AN[ (" + an.ring.varsToString() + ") (" + an.toString() + ") ]"; 286 } 287 if (coFac instanceof GenPolynomialRing) { 288 GenPolynomialRing rf = (GenPolynomialRing) coFac; 289 //String[] v = rf.vars; 290 //RingFactory cf = rf.coFac; 291 //String cs; 292 //if (cf instanceof ModIntegerRing) { 293 // cs = cf.toString(); 294 //} else { 295 // cs = " " + cf.getClass().getSimpleName(); 296 //} 297 //res = "IntFunc" + "{" + cs + "( " + rf.varsToString() + " )" + " } "; 298 res = "IntFunc" + "( " + rf.toString() + " )"; 299 } 300 if (((Object) coFac) instanceof ModIntegerRing) { 301 ModIntegerRing mn = (ModIntegerRing) ((Object) coFac); 302 res = "Mod " + mn.getModul() + " "; 303 } 304 if (res == null) { 305 res = coFac.toString(); 306 if (res.matches("[0-9].*")) { 307 res = scf; 308 } 309 } 310 res += "( " + varsToString() + " ) " + tord.toString() + " "; 311 } else { 312 res = this.getClass().getSimpleName() + "[ " + coFac.toString() + " "; 313 if (coFac instanceof AlgebraicNumberRing) { 314 AlgebraicNumberRing an = (AlgebraicNumberRing) coFac; 315 res = "AN[ (" + an.ring.varsToString() + ") (" + an.modul + ") ]"; 316 } 317 if (coFac instanceof GenPolynomialRing) { 318 GenPolynomialRing rf = (GenPolynomialRing) coFac; 319 //String[] v = rf.vars; 320 //RingFactory cf = rf.coFac; 321 //String cs; 322 //if (cf instanceof ModIntegerRing) { 323 // cs = cf.toString(); 324 //} else { 325 // cs = " " + cf.getClass().getSimpleName(); 326 //} 327 //res = "IntFunc{ " + cs + "( " + rf.varsToString() + " )" + " } "; 328 res = "IntFunc" + "( " + rf.toString() + " )"; 329 } 330 if (((Object) coFac) instanceof ModIntegerRing) { 331 ModIntegerRing mn = (ModIntegerRing) ((Object) coFac); 332 res = "Mod " + mn.getModul() + " "; 333 } 334 //res += ", " + nvar + ", " + tord.toString() + ", " + varsToString() + ", " + partial + " ]"; 335 res += "( " + varsToString() + " ) " + tord.toString() + " ]"; 336 } 337 return res; 338 } 339 340 341 /** 342 * Get a scripting compatible string representation. 343 * @return script compatible representation for this Element. 344 * @see edu.jas.structure.Element#toScript() 345 */ 346 @Override 347 public String toScript() { 348 StringBuffer s = new StringBuffer(); 349 switch (Scripting.getLang()) { 350 case Ruby: 351 s.append("PolyRing.new("); 352 break; 353 case Python: 354 default: 355 s.append("PolyRing("); 356 } 357 if (coFac instanceof RingElem) { 358 s.append(((RingElem<C>) coFac).toScriptFactory()); 359 } else { 360 s.append(coFac.toScript().trim()); 361 } 362 s.append(",\"" + varsToString() + "\""); 363 String to = tord.toScript(); 364 s.append("," + to); 365 s.append(")"); 366 return s.toString(); 367 } 368 369 370 /** 371 * Get a scripting compatible string representation of an ExpVector of this 372 * ring. 373 * @param e exponent vector 374 * @return script compatible representation for the ExpVector. 375 */ 376 public String toScript(ExpVector e) { 377 if (e == null) { 378 return "null"; 379 } 380 if (vars != null) { 381 return e.toScript(vars); 382 } 383 return e.toScript(); 384 } 385 386 387 /** 388 * Comparison with any other object. 389 * @see java.lang.Object#equals(java.lang.Object) 390 */ 391 @Override 392 @SuppressWarnings("unchecked") 393 public boolean equals(Object other) { 394 if (other == null) { 395 return false; 396 } 397 if (!(other instanceof GenPolynomialRing)) { 398 return false; 399 } 400 GenPolynomialRing<C> oring = (GenPolynomialRing<C>) other; 401 if (nvar != oring.nvar) { 402 return false; 403 } 404 if (!coFac.equals(oring.coFac)) { 405 return false; 406 } 407 if (!tord.equals(oring.tord)) { 408 return false; 409 } 410 // same variables required ? 411 if (!Arrays.deepEquals(vars, oring.vars)) { 412 return false; 413 } 414 return true; 415 } 416 417 418 /** 419 * Hash code for this polynomial ring. 420 * @see java.lang.Object#hashCode() 421 */ 422 @Override 423 public int hashCode() { 424 int h; 425 h = (nvar << 27); 426 h += (coFac.hashCode() << 11); 427 h += (tord.hashCode() << 9); 428 h += Arrays.hashCode(vars); 429 //System.out.println("GenPolynomialRing.hashCode: " + h); 430 return h; 431 } 432 433 434 /** 435 * Get the number of polynomial creations. 436 * @return creations. 437 */ 438 public int getCreations() { 439 return creations; 440 } 441 442 443 /** 444 * Get the variable names. 445 * @return vars. 446 */ 447 public String[] getVars() { 448 return Arrays.copyOf(vars, vars.length); // > Java-5 449 } 450 451 452 /** 453 * Set the variable names. 454 * @return old vars. 455 */ 456 public String[] setVars(String[] v) { 457 if (v.length != nvar) { 458 throw new IllegalArgumentException( 459 "v not matching number of variables: " + Arrays.toString(v) + ", nvar " + nvar); 460 } 461 String[] t = vars; 462 vars = Arrays.copyOf(v, v.length); // > Java-5 463 return t; 464 } 465 466 467 /** 468 * Get a String representation of the variable names. 469 * @return names separated by commas. 470 */ 471 public String varsToString() { 472 if (vars == null) { 473 return "#" + nvar; 474 } 475 //return Arrays.toString(vars); 476 return ExpVector.varsToString(vars); 477 } 478 479 480 /** 481 * Get the zero element from the coefficients. 482 * @return 0 as C. 483 */ 484 public C getZEROCoefficient() { 485 return coFac.getZERO(); 486 } 487 488 489 /** 490 * Get the one element from the coefficients. 491 * @return 1 as C. 492 */ 493 public C getONECoefficient() { 494 return coFac.getONE(); 495 } 496 497 498 /** 499 * Get the zero element. 500 * @return 0 as GenPolynomial<C>. 501 */ 502 public synchronized GenPolynomial<C> getZERO() { 503 if (ZERO == null || !ZERO.isZERO()) { // happened since May 5 2022 504 // Name : java-11-openjdk-headless, java-17-openjdk-headless 505 // Version : 11.0.15.0, 17.0.4 506 // Release : 150000.3.80.1, 150400.3.3.1 507 GenPolynomial<C> x = ZERO; 508 ZERO = new GenPolynomial<C>(this); 509 logger.info("warn: ZERO@get |{}| wrong fix to {}", x, ZERO); 510 } 511 return ZERO; 512 } 513 514 515 /** 516 * Get the one element. 517 * @return 1 as GenPolynomial<C>. 518 */ 519 public synchronized GenPolynomial<C> getONE() { 520 if (ONE == null || !ONE.isONE()) { 521 ONE = new GenPolynomial<C>(this, coFac.getONE(), evzero); 522 logger.info("warn: ONE@get {}", ONE); 523 } 524 return ONE; 525 } 526 527 528 /** 529 * Query if this ring is commutative. 530 * @return true if this ring is commutative, else false. 531 */ 532 public boolean isCommutative() { 533 return coFac.isCommutative(); 534 } 535 536 537 /** 538 * Query if this ring is associative. 539 * @return true if this ring is associative, else false. 540 */ 541 public boolean isAssociative() { 542 return coFac.isAssociative(); 543 } 544 545 546 /** 547 * Query if this ring is a field. 548 * @return false. 549 */ 550 public boolean isField() { 551 if (isField > 0) { 552 return true; 553 } 554 if (isField == 0) { 555 return false; 556 } 557 if (coFac.isField() && nvar == 0) { 558 isField = 1; 559 return true; 560 } 561 isField = 0; 562 return false; 563 } 564 565 566 /** 567 * Characteristic of this ring. 568 * @return characteristic of this ring. 569 */ 570 public java.math.BigInteger characteristic() { 571 return coFac.characteristic(); 572 } 573 574 575 /** 576 * Get a (constant) GenPolynomial<C> element from a coefficient value. 577 * @param a coefficient. 578 * @return a GenPolynomial<C>. 579 */ 580 public GenPolynomial<C> valueOf(C a) { 581 return new GenPolynomial<C>(this, a); 582 } 583 584 585 /** 586 * Get a GenPolynomial<C> element from an exponent vector. 587 * @param e exponent vector. 588 * @return a GenPolynomial<C>. 589 */ 590 public GenPolynomial<C> valueOf(ExpVector e) { 591 if (e == null) { 592 return getZERO(); 593 } 594 return new GenPolynomial<C>(this, coFac.getONE(), e); 595 } 596 597 598 /** 599 * Get a GenPolynomial<C> element from a list of exponent vectors. 600 * @param E list of exponent vector. 601 * @return a GenPolynomial<C>. 602 */ 603 public List<GenPolynomial<C>> valueOf(Iterable<ExpVector> E) { 604 if (E == null) { 605 return null; 606 } 607 List<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>(); //E.size()); 608 for (ExpVector e : E) { 609 GenPolynomial<C> p = valueOf(e); 610 P.add(p); 611 } 612 return P; 613 } 614 615 616 /** 617 * Get a GenPolynomial<C> element from a coefficient and an exponent 618 * vector. 619 * @param a coefficient. 620 * @param e exponent vector. 621 * @return a GenPolynomial<C>. 622 */ 623 public GenPolynomial<C> valueOf(C a, ExpVector e) { 624 return new GenPolynomial<C>(this, a, e); 625 } 626 627 628 /** 629 * Get a GenPolynomial<C> element from a monomial. 630 * @param m monomial. 631 * @return a GenPolynomial<C>. 632 */ 633 public GenPolynomial<C> valueOf(Monomial<C> m) { 634 return new GenPolynomial<C>(this, m.c, m.e); 635 } 636 637 638 /** 639 * Get a (constant) GenPolynomial<C> element from a long value. 640 * @param a long. 641 * @return a GenPolynomial<C>. 642 */ 643 public GenPolynomial<C> fromInteger(long a) { 644 return new GenPolynomial<C>(this, coFac.fromInteger(a), evzero); 645 } 646 647 648 /** 649 * Get a (constant) GenPolynomial<C> element from a BigInteger value. 650 * @param a BigInteger. 651 * @return a GenPolynomial<C>. 652 */ 653 public GenPolynomial<C> fromInteger(BigInteger a) { 654 return new GenPolynomial<C>(this, coFac.fromInteger(a), evzero); 655 } 656 657 658 /** 659 * Get a GenPolynomial<C> from a GenVector<C>. 660 * @param a GenVector<C>. 661 * @return a GenPolynomial<C>. 662 */ 663 public GenPolynomial<C> fromVector(GenVector<C> a) { 664 if (a == null || a.isZERO()) { 665 return ZERO; 666 } 667 if (nvar != 1) { 668 throw new IllegalArgumentException("no univariate polynomial ring"); 669 } 670 GenPolynomial<C> ret = copy(ZERO); 671 SortedMap<ExpVector, C> tm = ret.val; 672 long i = -1; 673 for (C m : a.val) { 674 i++; 675 if (m.isZERO()) { 676 continue; 677 } 678 ExpVector e = ExpVector.create(1, 0, i); 679 tm.put(e, m); 680 } 681 return ret; 682 } 683 684 685 /** 686 * Random polynomial. Generates a random polynomial with k = 5, l = n, d = 687 * (nvar == 1) ? n : 3, q = (nvar == 1) ? 0.7 : 0.3. 688 * @param n number of terms. 689 * @return a random polynomial. 690 */ 691 public GenPolynomial<C> random(int n) { 692 return random(n, random); 693 } 694 695 696 /** 697 * Random polynomial. Generates a random polynomial with k = 5, l = n, d = 698 * n, q = (nvar == 1) ? 0.5 : 0.3. 699 * @param n number of terms. 700 * @param rnd is a source for random bits. 701 * @return a random polynomial. 702 */ 703 public GenPolynomial<C> random(int n, Random rnd) { 704 if (nvar == 1) { 705 return random(3, n, n, 0.5f, rnd); 706 } 707 return random(3, n, n, 0.3f, rnd); 708 } 709 710 711 /** 712 * Generate a random polynomial. 713 * @param k bitsize of random coefficients. 714 * @param l number of terms. 715 * @param d maximal degree in each variable. 716 * @param q density of nozero exponents. 717 * @return a random polynomial. 718 */ 719 public GenPolynomial<C> random(int k, int l, int d, float q) { 720 return random(k, l, d, q, random); 721 } 722 723 724 /** 725 * Generate a random polynomial. 726 * @param k bitsize of random coefficients. 727 * @param l number of terms. 728 * @param d maximal degree in each variable. 729 * @param q density of nozero exponents. 730 * @param rnd is a source for random bits. 731 * @return a random polynomial. 732 */ 733 public GenPolynomial<C> random(int k, int l, int d, float q, Random rnd) { 734 GenPolynomial<C> r = getZERO(); //.clone() or copy( ZERO ); 735 ExpVector e; 736 C a; 737 // add l random coeffs and exponents 738 for (int i = 0; i < l; i++) { 739 e = ExpVector.random(nvar, d, q, rnd); 740 a = coFac.random(k, rnd); 741 r = r.sum(a, e); // somewhat inefficient but clean 742 //System.out.println("e = " + e + " a = " + a); 743 } 744 // System.out.println("r = " + r); 745 return r; 746 } 747 748 749 /** 750 * Copy polynomial c. 751 * @param c 752 * @return a copy of c. 753 */ 754 public GenPolynomial<C> copy(GenPolynomial<C> c) { 755 //System.out.println("GP copy = " + this); 756 return new GenPolynomial<C>(this, c.val); 757 } 758 759 760 /** 761 * Copy polynomial list. 762 * @param L polynomial list 763 * @return a copy of L in this ring. 764 */ 765 public List<GenPolynomial<C>> copy(List<GenPolynomial<C>> L) { 766 if (L == null) { 767 return L; 768 } 769 List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(L.size()); 770 for (GenPolynomial<C> a : L) { 771 R.add(copy(a)); 772 } 773 return R; 774 } 775 776 777 /** 778 * Parse a polynomial with the use of GenPolynomialTokenizer. 779 * @param s String. 780 * @return GenPolynomial from s. 781 */ 782 public GenPolynomial<C> parse(String s) { 783 String val = s; 784 if (!s.contains("|")) { 785 val = val.replace("{", "").replace("}", ""); 786 } 787 return parse(new StringReader(val)); 788 } 789 790 791 /** 792 * Parse a polynomial with the use of GenPolynomialTokenizer. 793 * @param r Reader. 794 * @return next GenPolynomial from r. 795 */ 796 @SuppressWarnings({ "unchecked", "cast" }) 797 public GenPolynomial<C> parse(Reader r) { 798 GenPolynomialTokenizer pt = new GenPolynomialTokenizer(this, r); 799 GenPolynomial<C> p = null; 800 try { 801 p = (GenPolynomial<C>) pt.nextPolynomial(); 802 } catch (IOException e) { 803 logger.error("{} parse {}", e, this); 804 p = ZERO; 805 } 806 return p; 807 } 808 809 810 /** 811 * Generate univariate polynomial in a given variable with given exponent. 812 * @param x the name of a variable. 813 * @return x as univariate polynomial. 814 */ 815 public GenPolynomial<C> univariate(String x) { 816 return univariate(x, 1L); 817 } 818 819 820 /** 821 * Generate univariate polynomial in a given variable with given exponent. 822 * @param x the name of the variable. 823 * @param e the exponent of the variable. 824 * @return x^e as univariate polynomial. 825 */ 826 public GenPolynomial<C> univariate(String x, long e) { 827 if (vars == null) { // should not happen 828 throw new IllegalArgumentException("no variables defined for polynomial ring"); 829 } 830 if (x == null || x.isEmpty()) { 831 throw new IllegalArgumentException("no variable name given"); 832 } 833 int i; 834 for (i = 0; i < vars.length; i++) { 835 if (x.equals(vars[i])) { // use HashMap or TreeMap 836 break; 837 } 838 } 839 if (i >= vars.length) { 840 throw new IllegalArgumentException("variable '" + x + "' not defined in polynomial ring"); 841 } 842 return univariate(0, nvar - i - 1, e); 843 } 844 845 846 /** 847 * Generate univariate polynomial in a given variable. 848 * @param i the index of the variable. 849 * @return X_i as univariate polynomial. 850 */ 851 public GenPolynomial<C> univariate(int i) { 852 return univariate(0, i, 1L); 853 } 854 855 856 /** 857 * Generate univariate polynomial in a given variable with given exponent. 858 * @param i the index of the variable. 859 * @param e the exponent of the variable. 860 * @return X_i^e as univariate polynomial. 861 */ 862 public GenPolynomial<C> univariate(int i, long e) { 863 return univariate(0, i, e); 864 } 865 866 867 /** 868 * Generate univariate polynomial in a given variable with given exponent. 869 * @param modv number of module variables. 870 * @param i the index of the variable. 871 * @param e the exponent of the variable. 872 * @return X_i^e as univariate polynomial. 873 */ 874 public GenPolynomial<C> univariate(int modv, int i, long e) { 875 GenPolynomial<C> p = getZERO(); 876 int r = nvar - modv; 877 if (0 <= i && i < r) { 878 C one = coFac.getONE(); 879 ExpVector f = ExpVector.create(r, i, e); 880 if (modv > 0) { 881 f = f.extend(modv, 0, 0l); 882 } 883 p = p.sum(one, f); 884 } 885 return p; 886 } 887 888 889 /** 890 * Get the generating elements excluding the generators for the coefficient 891 * ring. 892 * @return a list of generating elements for this ring. 893 */ 894 public List<GenPolynomial<C>> getGenerators() { 895 List<? extends GenPolynomial<C>> univs = univariateList(); 896 List<GenPolynomial<C>> gens = new ArrayList<GenPolynomial<C>>(univs.size() + 1); 897 gens.add(getONE()); 898 gens.addAll(univs); 899 return gens; 900 } 901 902 903 /** 904 * Get a list of the generating elements. 905 * @return list of generators for the algebraic structure. 906 * @see edu.jas.structure.ElemFactory#generators() 907 */ 908 public List<GenPolynomial<C>> generators() { 909 List<? extends C> cogens = coFac.generators(); 910 List<? extends GenPolynomial<C>> univs = univariateList(); 911 List<GenPolynomial<C>> gens = new ArrayList<GenPolynomial<C>>(univs.size() + cogens.size()); 912 for (C c : cogens) { 913 gens.add(getONE().multiply(c)); 914 } 915 gens.addAll(univs); 916 return gens; 917 } 918 919 920 /** 921 * Get a list of the generating elements excluding the module variables. 922 * @param modv number of module variables 923 * @return list of generators for the polynomial ring. 924 */ 925 public List<GenPolynomial<C>> generators(int modv) { 926 List<? extends C> cogens = coFac.generators(); 927 List<? extends GenPolynomial<C>> univs = univariateList(modv); 928 List<GenPolynomial<C>> gens = new ArrayList<GenPolynomial<C>>(univs.size() + cogens.size()); 929 for (C c : cogens) { 930 gens.add(getONE().multiply(c)); 931 } 932 gens.addAll(univs); 933 return gens; 934 } 935 936 937 /** 938 * Is this structure finite or infinite. 939 * @return true if this structure is finite, else false. 940 * @see edu.jas.structure.ElemFactory#isFinite() 941 */ 942 public boolean isFinite() { 943 return (nvar == 0) && coFac.isFinite(); 944 } 945 946 947 /** 948 * Generate list of univariate polynomials in all variables. 949 * @return List(X_1,...,X_n) a list of univariate polynomials. 950 */ 951 public List<? extends GenPolynomial<C>> univariateList() { 952 return univariateList(0, 1L); 953 } 954 955 956 /** 957 * Generate list of univariate polynomials in all variables. 958 * @param modv number of module variables. 959 * @return List(X_1,...,X_n) a list of univariate polynomials. 960 */ 961 public List<? extends GenPolynomial<C>> univariateList(int modv) { 962 return univariateList(modv, 1L); 963 } 964 965 966 /** 967 * Generate list of univariate polynomials in all variables with given 968 * exponent. 969 * @param modv number of module variables. 970 * @param e the exponent of the variables. 971 * @return List(X_1^e,...,X_n^e) a list of univariate polynomials. 972 */ 973 public List<? extends GenPolynomial<C>> univariateList(int modv, long e) { 974 List<GenPolynomial<C>> pols = new ArrayList<GenPolynomial<C>>(nvar); 975 int nm = nvar - modv; 976 for (int i = 0; i < nm; i++) { 977 GenPolynomial<C> p = univariate(modv, nm - 1 - i, e); 978 pols.add(p); 979 } 980 return pols; 981 } 982 983 984 /** 985 * Extend variables. Used e.g. in module embedding. Extend number of 986 * variables by i. 987 * @param i number of variables to extend. 988 * @return extended polynomial ring factory. 989 */ 990 public GenPolynomialRing<C> extend(int i) { 991 return extend(i, false); 992 } 993 994 995 /** 996 * Extend variables. Used e.g. in module embedding. Extend number of 997 * variables by i. 998 * @param i number of variables to extend. 999 * @param top true for TOP term order, false for POT term order. 1000 * @return extended polynomial ring factory. 1001 */ 1002 public GenPolynomialRing<C> extend(int i, boolean top) { 1003 // add module variable names 1004 String[] v = newVars("e", i); 1005 return extend(v, top); 1006 } 1007 1008 1009 /** 1010 * Extend variables. Used e.g. in module embedding. Extend number of 1011 * variables by length(vn). 1012 * @param vn names for extended variables. 1013 * @return extended polynomial ring factory. 1014 */ 1015 public GenPolynomialRing<C> extend(String[] vn) { 1016 return extend(vn, false); 1017 } 1018 1019 1020 /** 1021 * Extend variables. Used e.g. in module embedding. Extend number of 1022 * variables by length(vn). 1023 * @param vn names for extended variables. 1024 * @param top true for TOP term order, false for POT term order. 1025 * @return extended polynomial ring factory. 1026 */ 1027 public GenPolynomialRing<C> extend(String[] vn, boolean top) { 1028 if (vn == null || vars == null) { 1029 throw new IllegalArgumentException("vn and vars may not be null"); 1030 } 1031 int i = vn.length; 1032 String[] v = new String[vars.length + i]; 1033 for (int k = 0; k < vars.length; k++) { 1034 v[k] = vars[k]; 1035 } 1036 for (int k = 0; k < vn.length; k++) { 1037 v[vars.length + k] = vn[k]; 1038 } 1039 TermOrder to = tord.extend(nvar, i, top); 1040 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar + i, to, v); 1041 return pfac; 1042 } 1043 1044 1045 /** 1046 * Extend lower variables. Extend number of variables by i. 1047 * @param i number of variables to extend. 1048 * @return extended polynomial ring factory. 1049 */ 1050 public GenPolynomialRing<C> extendLower(int i) { 1051 String[] v = newVars("e", i); 1052 return extendLower(v); 1053 } 1054 1055 1056 /** 1057 * Extend lower variables. Extend number of variables by length(vn). 1058 * @param vn names for extended lower variables. 1059 * @return extended polynomial ring factory. 1060 */ 1061 public GenPolynomialRing<C> extendLower(String[] vn) { 1062 return extendLower(vn, false); 1063 } 1064 1065 1066 /** 1067 * Extend lower variables. Extend number of variables by length(vn). 1068 * @param vn names for extended lower variables. 1069 * @param top true for TOP term order, false for POT term order. 1070 * @return extended polynomial ring factory. 1071 */ 1072 public GenPolynomialRing<C> extendLower(String[] vn, boolean top) { 1073 if (vn == null || vars == null) { 1074 throw new IllegalArgumentException("vn and vars may not be null"); 1075 } 1076 int i = vn.length; 1077 String[] v = new String[vars.length + i]; 1078 for (int k = 0; k < vn.length; k++) { 1079 v[k] = vn[k]; 1080 } 1081 for (int k = 0; k < vars.length; k++) { 1082 v[vn.length + k] = vars[k]; 1083 } 1084 TermOrder to = tord.extendLower(nvar, i, top); 1085 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar + i, to, v); 1086 return pfac; 1087 } 1088 1089 1090 /** 1091 * Contract variables. Used e.g. in module embedding. Contract number of 1092 * variables by i. 1093 * @param i number of variables to remove. 1094 * @return contracted polynomial ring factory. 1095 */ 1096 public GenPolynomialRing<C> contract(int i) { 1097 String[] v = null; 1098 if (vars != null) { 1099 v = new String[vars.length - i]; 1100 for (int j = 0; j < vars.length - i; j++) { 1101 v[j] = vars[j]; 1102 } 1103 } 1104 TermOrder to = tord.contract(i, nvar - i); 1105 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar - i, to, v); 1106 return pfac; 1107 } 1108 1109 1110 /** 1111 * Recursive representation as polynomial with i main variables. 1112 * @param i number of main variables. 1113 * @return recursive polynomial ring factory. 1114 */ 1115 public GenPolynomialRing<GenPolynomial<C>> recursive(int i) { 1116 if (i <= 0 || i >= nvar) { 1117 throw new IllegalArgumentException("wrong: 0 < " + i + " < " + nvar); 1118 } 1119 GenPolynomialRing<C> cfac = contract(i); 1120 String[] v = null; 1121 if (vars != null) { 1122 v = new String[i]; 1123 int k = 0; 1124 for (int j = nvar - i; j < nvar; j++) { 1125 v[k++] = vars[j]; 1126 } 1127 } 1128 TermOrder to = tord.contract(0, i); // ?? 1129 GenPolynomialRing<GenPolynomial<C>> pfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, i, to, v); 1130 return pfac; 1131 } 1132 1133 1134 /** 1135 * Distributive representation as polynomial with all main variables. 1136 * @return distributive polynomial ring factory. 1137 */ 1138 @SuppressWarnings("unchecked") 1139 public GenPolynomialRing<C> distribute() { 1140 if (!(coFac instanceof GenPolynomialRing)) { 1141 return this; 1142 } 1143 RingFactory cf = coFac; 1144 RingFactory<GenPolynomial<C>> cfp = (RingFactory<GenPolynomial<C>>) cf; 1145 GenPolynomialRing cr = (GenPolynomialRing) cfp; 1146 GenPolynomialRing<C> pfac; 1147 if (cr.vars != null) { 1148 pfac = extend(cr.vars); 1149 } else { 1150 pfac = extend(cr.nvar); 1151 } 1152 return pfac; 1153 } 1154 1155 1156 /** 1157 * Reverse variables. Used e.g. in opposite rings. 1158 * @return polynomial ring factory with reversed variables. 1159 */ 1160 public GenPolynomialRing<C> reverse() { 1161 return reverse(false); 1162 } 1163 1164 1165 /** 1166 * Reverse variables. Used e.g. in opposite rings. The coefficient 1167 * ring must be commuative. 1168 * @param partial true for partially reversed term orders. 1169 * @return polynomial ring factory with reversed variables. 1170 */ 1171 public GenPolynomialRing<C> reverse(boolean partial) { 1172 if (!coFac.isCommutative() && !(coFac.getONE() instanceof StarRingElem)) { 1173 //throw new IllegalArgumentException("reverse coefficients must be commutative or StarRing: " + coFac); 1174 logger.warn("reverse coefficients should be commutative or StarRing elements: " + coFac); 1175 } 1176 String[] v = null; 1177 if (vars != null) { // vars are not inversed 1178 v = new String[vars.length]; 1179 int k = tord.getSplit(); 1180 if (partial && k < vars.length) { 1181 // copy upper 1182 for (int j = 0; j < k; j++) { 1183 //v[vars.length - k + j] = vars[vars.length - 1 - j]; // reverse upper 1184 v[vars.length - k + j] = vars[vars.length - k + j]; 1185 } 1186 // reverse lower 1187 for (int j = 0; j < vars.length - k; j++) { 1188 //v[j] = vars[j]; // copy upper 1189 v[j] = vars[vars.length - k - j - 1]; 1190 } 1191 } else { 1192 for (int j = 0; j < vars.length; j++) { 1193 v[j] = vars[vars.length - 1 - j]; 1194 } 1195 } 1196 //System.out.println("vars = " + Arrays.toString(vars)); 1197 //System.out.println("v = " + Arrays.toString(v)); 1198 } 1199 TermOrder to = tord.reverse(partial); 1200 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar, to, v); 1201 pfac.partial = partial; 1202 return pfac; 1203 } 1204 1205 1206 /** 1207 * Get PolynomialComparator. 1208 * @return polynomial comparator. 1209 */ 1210 public PolynomialComparator<C> getComparator() { 1211 return new PolynomialComparator<C>(tord, false); 1212 } 1213 1214 1215 /** 1216 * Get PolynomialComparator. 1217 * @param rev for reverse comparator. 1218 * @return polynomial comparator. 1219 */ 1220 public PolynomialComparator<C> getComparator(boolean rev) { 1221 return new PolynomialComparator<C>(tord, rev); 1222 } 1223 1224 1225 /** 1226 * New variable names. Generate new names for variables, 1227 * @param prefix name prefix. 1228 * @param n number of variables. 1229 * @return new variable names. 1230 */ 1231 public static String[] newVars(String prefix, int n) { 1232 String[] vars = new String[n]; 1233 for (int i = 0; i < n; i++) { 1234 long m = varCounter.getAndIncrement(); 1235 vars[i] = prefix + m; 1236 } 1237 return vars; 1238 } 1239 1240 1241 /** 1242 * New variable names. Generate new names for variables, 1243 * @param prefix name prefix. 1244 * @return new variable names. 1245 */ 1246 public String[] newVars(String prefix) { 1247 return newVars(prefix, nvar); 1248 } 1249 1250 1251 /** 1252 * New variable names. Generate new names for variables, 1253 * @param n number of variables. 1254 * @return new variable names. 1255 */ 1256 public static String[] newVars(int n) { 1257 return newVars("x", n); 1258 } 1259 1260 1261 /** 1262 * New variable names. Generate new names for variables, 1263 * @return new variable names. 1264 */ 1265 public String[] newVars() { 1266 return newVars(nvar); 1267 } 1268 1269 1270 /* 1271 * Add variable names. 1272 * @param vars variable names to be recorded. 1273 public static void addVars(String[] vars) { 1274 if (vars == null) { 1275 return; 1276 } 1277 // synchronized (knownVars) { 1278 // for (int i = 0; i < vars.length; i++) { 1279 // knownVars.add(vars[i]); // eventually names 'overwritten' 1280 // } 1281 // } 1282 } 1283 */ 1284 1285 1286 /** 1287 * Permute variable names. 1288 * @param vars variable names. 1289 * @param P permutation. 1290 * @return P(vars). 1291 */ 1292 public static String[] permuteVars(List<Integer> P, String[] vars) { 1293 if (vars == null || vars.length <= 1) { 1294 return vars; 1295 } 1296 String[] b = new String[vars.length]; 1297 int j = 0; 1298 for (Integer i : P) { 1299 b[j++] = vars[i]; 1300 } 1301 return b; 1302 } 1303 1304 1305 /** 1306 * Permutation of polynomial ring variables. 1307 * @param P permutation. 1308 * @return P(this). 1309 */ 1310 public GenPolynomialRing<C> permutation(List<Integer> P) { 1311 if (nvar <= 1) { 1312 return this; 1313 } 1314 TermOrder tp = tord.permutation(P); 1315 if (vars == null) { 1316 return new GenPolynomialRing<C>(coFac, nvar, tp); 1317 } 1318 String[] v1 = new String[vars.length]; 1319 for (int i = 0; i < v1.length; i++) { 1320 v1[i] = vars[v1.length - 1 - i]; 1321 } 1322 String[] vp = permuteVars(P, v1); 1323 String[] v2 = new String[vp.length]; 1324 for (int i = 0; i < vp.length; i++) { 1325 v2[i] = vp[vp.length - 1 - i]; 1326 } 1327 return new GenPolynomialRing<C>(coFac, nvar, tp, v2); 1328 } 1329 1330 1331 /** 1332 * Characteristic polynomial of matrix. 1333 * <b>Note:</b> using Faddeev–LeVerrier algorithm 1334 * @see https://en.wikipedia.org/wiki/Faddeev%E2%80%93LeVerrier_algorithm 1335 * @param A a square matrix. 1336 * @return characteristic polynomial of A. 1337 */ 1338 public GenPolynomial<C> charPolynomial(GenMatrix<C> A) { 1339 if (A == null || A.isZERO()) { 1340 return ZERO; 1341 } 1342 if (nvar != 1) { 1343 throw new IllegalArgumentException("no univariate polynomial ring"); 1344 } 1345 GenMatrixRing<C> mfac = A.ring; 1346 int n = mfac.rows; 1347 java.math.BigInteger c0 = coFac.characteristic(); 1348 if (c0.signum() > 0 && c0.compareTo(java.math.BigInteger.valueOf(n)) <= 0) { 1349 throw new UnsupportedOperationException("characteristic <= n: " + c0 + " <= " + n); 1350 } 1351 GenPolynomial<C> ret = copy(ZERO); 1352 //SortedMap<ExpVector, C> tm = ret.val; 1353 GenMatrix<C> M = mfac.getZERO(); //new GenMatrix<C>(A.ring); 1354 GenMatrix<C> I = mfac.getONE(); 1355 ExpVector e = ExpVector.create(1, 0, n); 1356 C one = coFac.getONE(); 1357 ret = ret.sum(one, e); 1358 C c = coFac.getONE(); 1359 GenMatrix<C> Ms = null; 1360 GenMatrix<C> Mp = null, Mc; 1361 // M_0 = 0, c_n = 1 1362 // k = 1..n: M_k = A*M_{k-1} + c_{n-k+1}*I, c_{n-k} = -1/k*trace(A*M_k) 1363 for (int k = 1; k <= n; k++) { 1364 if (Ms == null) { 1365 Mp = A.multiply(M); // reuse A*Mp? todo 1366 } else { 1367 Mp = Ms; 1368 } 1369 Mc = I.multiply(c); 1370 Mp = Mp.sum(Mc); 1371 Ms = A.multiply(Mp); 1372 C cp = Ms.trace(); 1373 C ki = coFac.fromInteger(k).inverse(); // characteristic != k 1374 cp = cp.multiply(ki).negate(); 1375 M = Mp; 1376 c = cp; 1377 e = ExpVector.create(1, 0, n-k); 1378 ret = ret.sum(c, e); 1379 //System.out.println("k = " + k + ", c = " + c + ", M = " + M); 1380 } 1381 // only for demonstrating how to get the determinant, trace and inverse: 1382 // C det = coFac.getZERO(); //ret.trailingBaseCoefficient(); 1383 // //System.out.println("n = " + n + ", deg = " + ret.degree()); 1384 // if (n % 2 != 0) { 1385 // det = det.negate(); 1386 // } 1387 // if (! det.isZERO()) { 1388 // C d = det.inverse(); 1389 // if ((n-1) % 2 != 0) { 1390 // d = d.negate(); 1391 // } 1392 // Mc = Mp.multiply(d); 1393 // } else { 1394 // Mc = null; 1395 // } 1396 // //System.out.println("det = " + det + ", trace = " + c + ", A^{-1} = " + Mc); 1397 return ret; 1398 } 1399 1400 1401 /** 1402 * Determinant of matrix from characteristic polynomial. 1403 * <b>Note:</b> using Faddeev–LeVerrier algorithm 1404 * @see https://en.wikipedia.org/wiki/Faddeev%E2%80%93LeVerrier_algorithm 1405 * @param P characteristic polynomial of a matrix. 1406 * @return determinant from characteristic polynomial. 1407 */ 1408 public C determinantFromCharPol(GenPolynomial<C> P) { 1409 C det = coFac.getZERO(); 1410 if (P == null || P.isZERO()) { 1411 return det; 1412 } 1413 det = P.trailingBaseCoefficient(); 1414 if (P.degree() % 2 != 0) { 1415 det = det.negate(); 1416 } 1417 return det; 1418 } 1419 1420 1421 /** 1422 * Determinant of matrix via characteristic polynomial. 1423 * <b>Note:</b> using Faddeev–LeVerrier algorithm 1424 * @see https://en.wikipedia.org/wiki/Faddeev%E2%80%93LeVerrier_algorithm 1425 * @param A square matrix. 1426 * @return determinant of A from characteristic polynomial of A. 1427 */ 1428 public C determinant(GenMatrix<C> A) { 1429 GenPolynomial<C> P = charPolynomial(A); 1430 return determinantFromCharPol(P); 1431 } 1432 1433 1434 /** 1435 * Trace of matrix from characteristic polynomial. 1436 * @param P characteristic polynomial of a matrix. 1437 * @return trace from characteristic polynomial. 1438 */ 1439 public C traceFromCharPol(GenPolynomial<C> P) { 1440 if (P == null || P.isZERO()) { 1441 return coFac.getZERO(); 1442 } 1443 long n = P.degree(); 1444 ExpVector e = ExpVector.create(1, 0, n-1); 1445 C t = P.coefficient(e).negate(); 1446 return t; 1447 } 1448 1449 1450 /** 1451 * Get a GenPolynomial iterator. 1452 * @return an iterator over all polynomials. 1453 */ 1454 public Iterator<GenPolynomial<C>> iterator() { 1455 if (coFac.isFinite()) { 1456 return new GenPolynomialIterator<C>(this); 1457 } 1458 logger.warn("ring of coefficients {} is infinite, constructing iterator only over monomials", coFac); 1459 return new GenPolynomialMonomialIterator<C>(this); 1460 //throw new IllegalArgumentException("only for finite iterable coefficients implemented"); 1461 } 1462 1463} 1464 1465 1466/** 1467 * Polynomial iterator. 1468 * @author Heinz Kredel 1469 */ 1470class GenPolynomialIterator<C extends RingElem<C>> implements Iterator<GenPolynomial<C>> { 1471 1472 1473 /** 1474 * data structure. 1475 */ 1476 final GenPolynomialRing<C> ring; 1477 1478 1479 final Iterator<List<Long>> eviter; 1480 1481 1482 final List<ExpVector> powers; 1483 1484 1485 final List<Iterable<C>> coeffiter; 1486 1487 1488 Iterator<List<C>> itercoeff; 1489 1490 1491 GenPolynomial<C> current; 1492 1493 1494 /** 1495 * Polynomial iterator constructor. 1496 */ 1497 @SuppressWarnings("unchecked") 1498 public GenPolynomialIterator(GenPolynomialRing<C> fac) { 1499 ring = fac; 1500 LongIterable li = new LongIterable(); 1501 li.setNonNegativeIterator(); 1502 List<Iterable<Long>> tlist = new ArrayList<Iterable<Long>>(ring.nvar); 1503 for (int i = 0; i < ring.nvar; i++) { 1504 tlist.add(li); 1505 } 1506 CartesianProductInfinite<Long> ei = new CartesianProductInfinite<Long>(tlist); 1507 eviter = ei.iterator(); 1508 RingFactory<C> cf = ring.coFac; 1509 coeffiter = new ArrayList<Iterable<C>>(); 1510 if (cf instanceof Iterable && cf.isFinite()) { 1511 Iterable<C> cfi = (Iterable<C>) cf; 1512 coeffiter.add(cfi); 1513 } else { 1514 throw new IllegalArgumentException("only for finite iterable coefficients implemented"); 1515 } 1516 CartesianProduct<C> tuples = new CartesianProduct<C>(coeffiter); 1517 itercoeff = tuples.iterator(); 1518 powers = new ArrayList<ExpVector>(); 1519 ExpVector e = ExpVector.create(eviter.next()); 1520 powers.add(e); 1521 //System.out.println("new e = " + e); 1522 //System.out.println("powers = " + powers); 1523 List<C> c = itercoeff.next(); 1524 //System.out.println("coeffs = " + c); 1525 current = new GenPolynomial<C>(ring, c.get(0), e); 1526 } 1527 1528 1529 /** 1530 * Test for availability of a next element. 1531 * @return true if the iteration has more elements, else false. 1532 */ 1533 public boolean hasNext() { 1534 return true; 1535 } 1536 1537 1538 /** 1539 * Get next polynomial. 1540 * @return next polynomial. 1541 */ 1542 public synchronized GenPolynomial<C> next() { 1543 GenPolynomial<C> res = current; 1544 if (!itercoeff.hasNext()) { 1545 ExpVector e = ExpVector.create(eviter.next()); 1546 powers.add(0, e); // add new ev at beginning 1547 //System.out.println("new e = " + e); 1548 //System.out.println("powers = " + powers); 1549 if (coeffiter.size() == 1) { // shorten first iterator by one element 1550 coeffiter.add(coeffiter.get(0)); 1551 Iterable<C> it = coeffiter.get(0); 1552 List<C> elms = new ArrayList<C>(); 1553 for (C elm : it) { 1554 elms.add(elm); 1555 } 1556 elms.remove(0); 1557 coeffiter.set(0, elms); 1558 } else { 1559 coeffiter.add(coeffiter.get(1)); 1560 } 1561 CartesianProduct<C> tuples = new CartesianProduct<C>(coeffiter); 1562 itercoeff = tuples.iterator(); 1563 } 1564 List<C> coeffs = itercoeff.next(); 1565 // while ( coeffs.get(0).isZERO() ) { 1566 // System.out.println(" skip zero "); 1567 // coeffs = itercoeff.next(); // skip tuples with zero in first component 1568 // } 1569 //System.out.println("coeffs = " + coeffs); 1570 GenPolynomial<C> pol = ring.getZERO().copy(); 1571 int i = 0; 1572 for (ExpVector f : powers) { 1573 C c = coeffs.get(i++); 1574 if (c.isZERO()) { 1575 continue; 1576 } 1577 if (pol.val.get(f) != null) { 1578 System.out.println("error f in pol = " + f + ", " + pol.getMap().get(f)); 1579 throw new RuntimeException("error in iterator"); 1580 } 1581 pol.doPutToMap(f, c); 1582 } 1583 current = pol; 1584 return res; 1585 } 1586 1587 1588 /** 1589 * Remove an element if allowed. 1590 */ 1591 public void remove() { 1592 throw new UnsupportedOperationException("cannot remove elements"); 1593 } 1594} 1595 1596 1597/** 1598 * Polynomial monomial iterator. 1599 * @author Heinz Kredel 1600 */ 1601class GenPolynomialMonomialIterator<C extends RingElem<C>> implements Iterator<GenPolynomial<C>> { 1602 1603 1604 /** 1605 * data structure. 1606 */ 1607 final GenPolynomialRing<C> ring; 1608 1609 1610 final Iterator<List> iter; 1611 1612 1613 GenPolynomial<C> current; 1614 1615 1616 /** 1617 * Polynomial iterator constructor. 1618 */ 1619 @SuppressWarnings("unchecked") 1620 public GenPolynomialMonomialIterator(GenPolynomialRing<C> fac) { 1621 ring = fac; 1622 LongIterable li = new LongIterable(); 1623 li.setNonNegativeIterator(); 1624 List<Iterable<Long>> tlist = new ArrayList<Iterable<Long>>(ring.nvar); 1625 for (int i = 0; i < ring.nvar; i++) { 1626 tlist.add(li); 1627 } 1628 CartesianProductInfinite<Long> ei = new CartesianProductInfinite<Long>(tlist); 1629 //Iterator<List<Long>> eviter = ei.iterator(); 1630 1631 RingFactory<C> cf = ring.coFac; 1632 Iterable<C> coeffiter; 1633 if (cf instanceof Iterable && !cf.isFinite()) { 1634 Iterable<C> cfi = (Iterable<C>) cf; 1635 coeffiter = cfi; 1636 } else { 1637 throw new IllegalArgumentException("only for infinite iterable coefficients implemented"); 1638 } 1639 1640 // Cantor iterator for exponents and coefficients 1641 List<Iterable> eci = new ArrayList<Iterable>(2); // no type parameter 1642 eci.add(ei); 1643 eci.add(coeffiter); 1644 CartesianProductInfinite ecp = new CartesianProductInfinite(eci); 1645 iter = ecp.iterator(); 1646 1647 List ec = iter.next(); 1648 List<Long> ecl = (List<Long>) ec.get(0); 1649 C c = (C) ec.get(1); // zero 1650 ExpVector e = ExpVector.create(ecl); 1651 //System.out.println("exp = " + e); 1652 //System.out.println("coeffs = " + c); 1653 current = new GenPolynomial<C>(ring, c, e); 1654 } 1655 1656 1657 /** 1658 * Test for availability of a next element. 1659 * @return true if the iteration has more elements, else false. 1660 */ 1661 public boolean hasNext() { 1662 return true; 1663 } 1664 1665 1666 /** 1667 * Get next polynomial. 1668 * @return next polynomial. 1669 */ 1670 @SuppressWarnings("unchecked") 1671 public synchronized GenPolynomial<C> next() { 1672 GenPolynomial<C> res = current; 1673 1674 List ec = iter.next(); 1675 C c = (C) ec.get(1); 1676 while (c.isZERO()) { // zero already done in first next 1677 ec = iter.next(); 1678 c = (C) ec.get(1); 1679 } 1680 List<Long> ecl = (List<Long>) ec.get(0); 1681 ExpVector e = ExpVector.create(ecl); 1682 //System.out.println("exp = " + e); 1683 //System.out.println("coeffs = " + c); 1684 current = new GenPolynomial<C>(ring, c, e); 1685 1686 return res; 1687 } 1688 1689 1690 /** 1691 * Remove an element if allowed. 1692 */ 1693 public void remove() { 1694 throw new UnsupportedOperationException("cannot remove elements"); 1695 } 1696}