001/* 002 * $Id: GenPolynomialRing.java 5372 2015-12-29 15:07:37Z kredel $ 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.HashSet; 015import java.util.Iterator; 016import java.util.List; 017import java.util.Random; 018import java.util.Set; 019 020import org.apache.log4j.Logger; 021 022import edu.jas.arith.ModIntegerRing; 023import edu.jas.kern.PreemptStatus; 024import edu.jas.kern.PrettyPrint; 025import edu.jas.kern.Scripting; 026import edu.jas.structure.RingElem; 027import edu.jas.structure.RingFactory; 028import edu.jas.util.CartesianProduct; 029import edu.jas.util.CartesianProductInfinite; 030import 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 041public class GenPolynomialRing<C extends RingElem<C>> implements RingFactory<GenPolynomial<C>>, 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 * Count for number of polynomial creations. 119 */ 120 static int creations = 0; 121 122 123 /** 124 * Flag to enable if preemptive interrrupt is checked. 125 */ 126 final boolean checkPreempt = PreemptStatus.isAllowed(); 127 128 129 /** 130 * The constructor creates a polynomial factory object with the default term 131 * order. 132 * @param cf factory for coefficients of type C. 133 * @param n number of variables. 134 */ 135 public GenPolynomialRing(RingFactory<C> cf, int n) { 136 this(cf, n, new TermOrder(), null); 137 } 138 139 140 /** 141 * The constructor creates a polynomial factory object. 142 * @param cf factory for coefficients of type C. 143 * @param n number of variables. 144 * @param t a term order. 145 */ 146 public GenPolynomialRing(RingFactory<C> cf, int n, TermOrder t) { 147 this(cf, n, t, null); 148 } 149 150 151 /** 152 * The constructor creates a polynomial factory object. 153 * @param cf factory for coefficients of type C. 154 * @param v names for the variables. 155 */ 156 public GenPolynomialRing(RingFactory<C> cf, String[] v) { 157 this(cf, v.length, v); 158 } 159 160 161 /** 162 * The constructor creates a polynomial factory object. 163 * @param cf factory for coefficients of type C. 164 * @param n number of variables. 165 * @param v names for the variables. 166 */ 167 public GenPolynomialRing(RingFactory<C> cf, int n, String[] v) { 168 this(cf, n, new TermOrder(), v); 169 } 170 171 172 /** 173 * The constructor creates a polynomial factory object. 174 * @param cf factory for coefficients of type C. 175 * @param t a term order. 176 * @param v names for the variables. 177 */ 178 public GenPolynomialRing(RingFactory<C> cf, TermOrder t, String[] v) { 179 this(cf, v.length, t, v); 180 } 181 182 183 /** 184 * The constructor creates a polynomial factory object. 185 * @param cf factory for coefficients of type C. 186 * @param v names for the variables. 187 * @param t a term order. 188 */ 189 public GenPolynomialRing(RingFactory<C> cf, String[] v, TermOrder t) { 190 this(cf, v.length, t, v); 191 } 192 193 194 /** 195 * The constructor creates a polynomial factory object. 196 * @param cf factory for coefficients of type C. 197 * @param n number of variables. 198 * @param t a term order. 199 * @param v names for the variables. 200 */ 201 public GenPolynomialRing(RingFactory<C> cf, int n, TermOrder t, String[] v) { 202 coFac = cf; 203 nvar = n; 204 tord = t; 205 partial = false; 206 if (v == null) { 207 vars = null; 208 } else { 209 vars = Arrays.copyOf(v, v.length); // > Java-5 210 } 211 ZERO = new GenPolynomial<C>(this); 212 C coeff = coFac.getONE(); 213 evzero = ExpVector.create(nvar); 214 ONE = new GenPolynomial<C>(this, coeff, evzero); 215 if (vars == null) { 216 if (PrettyPrint.isTrue()) { 217 vars = newVars("x", nvar); 218 } 219 } else { 220 if (vars.length != nvar) { 221 throw new IllegalArgumentException("incompatible variable size " + vars.length + ", " + nvar); 222 } 223 addVars(vars); 224 } 225 } 226 227 228 /** 229 * The constructor creates a polynomial factory object with the the same 230 * term order, number of variables and variable names as the given 231 * polynomial factory, only the coefficient factories differ. 232 * @param cf factory for coefficients of type C. 233 * @param o other polynomial ring. 234 */ 235 public GenPolynomialRing(RingFactory<C> cf, GenPolynomialRing o) { 236 this(cf, o.nvar, o.tord, o.vars); 237 } 238 239 240 /** 241 * The constructor creates a polynomial factory object with the the same 242 * coefficient factory, number of variables and variable names as the given 243 * polynomial factory, only the term order differs. 244 * @param to term order. 245 * @param o other polynomial ring. 246 */ 247 public GenPolynomialRing(GenPolynomialRing<C> o, TermOrder to) { 248 this(o.coFac, o.nvar, to, o.vars); 249 } 250 251 252 /** 253 * Copy this factory. 254 * @return a clone of this. 255 */ 256 public GenPolynomialRing<C> copy() { 257 return new GenPolynomialRing<C>(coFac, this); 258 } 259 260 261 /** 262 * Get the String representation. 263 * @see java.lang.Object#toString() 264 */ 265 @SuppressWarnings("cast") 266 @Override 267 public String toString() { 268 String res = null; 269 if (PrettyPrint.isTrue()) { // wrong: && coFac != null 270 String scf = coFac.getClass().getSimpleName(); 271 if (coFac instanceof AlgebraicNumberRing) { 272 AlgebraicNumberRing an = (AlgebraicNumberRing) coFac; 273 //String[] v = an.ring.vars; 274 res = "AN[ (" + an.ring.varsToString() + ") (" + an.toString() + ") ]"; 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 if (res == null) { 294 res = coFac.toString(); 295 if (res.matches("[0-9].*")) { 296 res = scf; 297 } 298 } 299 res += "( " + varsToString() + " ) " + tord.toString() + " "; 300 } else { 301 res = this.getClass().getSimpleName() + "[ " + coFac.toString() + " "; 302 // + coFac.getClass().getSimpleName(); 303 if (coFac instanceof AlgebraicNumberRing) { 304 AlgebraicNumberRing an = (AlgebraicNumberRing) coFac; 305 res = "AN[ (" + an.ring.varsToString() + ") (" + an.modul + ") ]"; 306 } 307 if (coFac instanceof GenPolynomialRing) { 308 GenPolynomialRing rf = (GenPolynomialRing) coFac; 309 //String[] v = rf.vars; 310 //RingFactory cf = rf.coFac; 311 //String cs; 312 //if (cf instanceof ModIntegerRing) { 313 // cs = cf.toString(); 314 //} else { 315 // cs = " " + cf.getClass().getSimpleName(); 316 //} 317 //res = "IntFunc{ " + cs + "( " + rf.varsToString() + " )" + " } "; 318 res = "IntFunc" + "( " + rf.toString() + " )"; 319 } 320 if (((Object) coFac) instanceof ModIntegerRing) { 321 ModIntegerRing mn = (ModIntegerRing) ((Object) coFac); 322 res = "Mod " + mn.getModul() + " "; 323 } 324 //res += ", " + nvar + ", " + tord.toString() + ", " + varsToString() + ", " + partial + " ]"; 325 res += "( " + varsToString() + " ) " + tord.toString() + " ]"; 326 } 327 return res; 328 } 329 330 331 /** 332 * Get a scripting compatible string representation. 333 * @return script compatible representation for this Element. 334 * @see edu.jas.structure.Element#toScript() 335 */ 336 @Override 337 public String toScript() { 338 StringBuffer s = new StringBuffer(); 339 switch (Scripting.getLang()) { 340 case Ruby: 341 s.append("PolyRing.new("); 342 break; 343 case Python: 344 default: 345 s.append("PolyRing("); 346 } 347 if (coFac instanceof RingElem) { 348 s.append(((RingElem<C>) coFac).toScriptFactory()); 349 } else { 350 s.append(coFac.toScript().trim()); 351 } 352 s.append(",\"" + varsToString() + "\""); 353 String to = tord.toScript(); 354 //if (tord.getEvord() == TermOrder.INVLEX) { 355 // to = "PolyRing.lex"; 356 //} 357 //if (tord.getEvord() == TermOrder.IGRLEX) { 358 // to = "PolyRing.grad"; 359 //} 360 s.append("," + to); 361 s.append(")"); 362 return s.toString(); 363 } 364 365 366 /** 367 * Get a scripting compatible string representation of an ExpVector of this 368 * ring. 369 * @param e exponent vector 370 * @return script compatible representation for the ExpVector. 371 */ 372 public String toScript(ExpVector e) { 373 if (vars != null) { 374 return e.toScript(vars); 375 } 376 return e.toScript(); 377 } 378 379 380 /** 381 * Comparison with any other object. 382 * @see java.lang.Object#equals(java.lang.Object) 383 */ 384 @Override 385 @SuppressWarnings("unchecked") 386 public boolean equals(Object other) { 387 if (other == null) { 388 return false; 389 } 390 if (!(other instanceof GenPolynomialRing)) { 391 return false; 392 } 393 GenPolynomialRing<C> oring = (GenPolynomialRing<C>) other; 394 if (nvar != oring.nvar) { 395 return false; 396 } 397 if (!coFac.equals(oring.coFac)) { 398 return false; 399 } 400 if (!tord.equals(oring.tord)) { 401 return false; 402 } 403 // same variables required ? 404 if (!Arrays.deepEquals(vars, oring.vars)) { 405 return false; 406 } 407 return true; 408 } 409 410 411 /** 412 * Hash code for this polynomial ring. 413 * @see java.lang.Object#hashCode() 414 */ 415 @Override 416 public int hashCode() { 417 int h; 418 h = (nvar << 27); 419 h += (coFac.hashCode() << 11); 420 h += tord.hashCode(); 421 return h; 422 } 423 424 425 /** 426 * Get the number of polynomial creations. 427 * @return creations. 428 */ 429 public int getCreations() { 430 return creations; 431 } 432 433 434 /** 435 * Get the variable names. 436 * @return vars. 437 */ 438 public String[] getVars() { 439 return Arrays.copyOf(vars, vars.length); // > Java-5 440 } 441 442 443 /** 444 * Set the variable names. 445 * @return old vars. 446 */ 447 public String[] setVars(String[] v) { 448 if (v.length != nvar) { 449 throw new IllegalArgumentException("v not matching number of variables: " + Arrays.toString(v) 450 + ", nvar " + nvar); 451 } 452 String[] t = vars; 453 vars = Arrays.copyOf(v, v.length); // > Java-5 454 return t; 455 } 456 457 458 /** 459 * Get a String representation of the variable names. 460 * @return names seperated by commas. 461 */ 462 public String varsToString() { 463 if (vars == null) { 464 return "#" + nvar; 465 } 466 //return Arrays.toString(vars); 467 return ExpVector.varsToString(vars); 468 } 469 470 471 /** 472 * Get the zero element from the coefficients. 473 * @return 0 as C. 474 */ 475 public C getZEROCoefficient() { 476 return coFac.getZERO(); 477 } 478 479 480 /** 481 * Get the one element from the coefficients. 482 * @return 1 as C. 483 */ 484 public C getONECoefficient() { 485 return coFac.getONE(); 486 } 487 488 489 /** 490 * Get the zero element. 491 * @return 0 as GenPolynomial<C>. 492 */ 493 public GenPolynomial<C> getZERO() { 494 return ZERO; 495 } 496 497 498 /** 499 * Get the one element. 500 * @return 1 as GenPolynomial<C>. 501 */ 502 public GenPolynomial<C> getONE() { 503 return ONE; 504 } 505 506 507 /** 508 * Query if this ring is commutative. 509 * @return true if this ring is commutative, else false. 510 */ 511 public boolean isCommutative() { 512 return coFac.isCommutative(); 513 } 514 515 516 /** 517 * Query if this ring is associative. 518 * @return true if this ring is associative, else false. 519 */ 520 public boolean isAssociative() { 521 return coFac.isAssociative(); 522 } 523 524 525 /** 526 * Query if this ring is a field. 527 * @return false. 528 */ 529 public boolean isField() { 530 if (isField > 0) { 531 return true; 532 } 533 if (isField == 0) { 534 return false; 535 } 536 if (coFac.isField() && nvar == 0) { 537 isField = 1; 538 return true; 539 } 540 isField = 0; 541 return false; 542 } 543 544 545 /** 546 * Characteristic of this ring. 547 * @return characteristic of this ring. 548 */ 549 public java.math.BigInteger characteristic() { 550 return coFac.characteristic(); 551 } 552 553 554 /** 555 * Get a (constant) GenPolynomial<C> element from a coefficient value. 556 * @param a coefficient. 557 * @return a GenPolynomial<C>. 558 */ 559 public GenPolynomial<C> valueOf(C a) { 560 return new GenPolynomial<C>(this, a); 561 } 562 563 564 /** 565 * Get a GenPolynomial<C> element from an exponent vector. 566 * @param e exponent vector. 567 * @return a GenPolynomial<C>. 568 */ 569 public GenPolynomial<C> valueOf(ExpVector e) { 570 return new GenPolynomial<C>(this, coFac.getONE(), e); 571 } 572 573 574 /** 575 * Get a GenPolynomial<C> element from a coeffcient and an exponent 576 * vector. 577 * @param a coefficient. 578 * @param e exponent vector. 579 * @return a GenPolynomial<C>. 580 */ 581 public GenPolynomial<C> valueOf(C a, ExpVector e) { 582 return new GenPolynomial<C>(this, a, e); 583 } 584 585 586 /** 587 * Get a (constant) GenPolynomial<C> element from a long value. 588 * @param a long. 589 * @return a GenPolynomial<C>. 590 */ 591 public GenPolynomial<C> fromInteger(long a) { 592 return new GenPolynomial<C>(this, coFac.fromInteger(a), evzero); 593 } 594 595 596 /** 597 * Get a (constant) GenPolynomial<C> element from a BigInteger value. 598 * @param a BigInteger. 599 * @return a GenPolynomial<C>. 600 */ 601 public GenPolynomial<C> fromInteger(BigInteger a) { 602 return new GenPolynomial<C>(this, coFac.fromInteger(a), evzero); 603 } 604 605 606 /** 607 * Random polynomial. Generates a random polynomial with k = 5, l = n, d = 608 * (nvar == 1) ? n : 3, q = (nvar == 1) ? 0.7 : 0.3. 609 * @param n number of terms. 610 * @return a random polynomial. 611 */ 612 public GenPolynomial<C> random(int n) { 613 return random(n, random); 614 } 615 616 617 /** 618 * Random polynomial. Generates a random polynomial with k = 5, l = n, d = 619 * n, q = (nvar == 1) ? 0.5 : 0.3. 620 * @param n number of terms. 621 * @param rnd is a source for random bits. 622 * @return a random polynomial. 623 */ 624 public GenPolynomial<C> random(int n, Random rnd) { 625 if (nvar == 1) { 626 return random(3, n, n, 0.5f, rnd); 627 } 628 return random(3, n, n, 0.3f, rnd); 629 } 630 631 632 /** 633 * Generate a random polynomial. 634 * @param k bitsize of random coefficients. 635 * @param l number of terms. 636 * @param d maximal degree in each variable. 637 * @param q density of nozero exponents. 638 * @return a random polynomial. 639 */ 640 public GenPolynomial<C> random(int k, int l, int d, float q) { 641 return random(k, l, d, q, random); 642 } 643 644 645 /** 646 * Generate a random polynomial. 647 * @param k bitsize of random coefficients. 648 * @param l number of terms. 649 * @param d maximal degree in each variable. 650 * @param q density of nozero exponents. 651 * @param rnd is a source for random bits. 652 * @return a random polynomial. 653 */ 654 public GenPolynomial<C> random(int k, int l, int d, float q, Random rnd) { 655 GenPolynomial<C> r = getZERO(); //.clone() or copy( ZERO ); 656 ExpVector e; 657 C a; 658 // add l random coeffs and exponents 659 for (int i = 0; i < l; i++) { 660 e = ExpVector.EVRAND(nvar, d, q, rnd); 661 a = coFac.random(k, rnd); 662 r = r.sum(a, e); // somewhat inefficient but clean 663 //System.out.println("e = " + e + " a = " + a); 664 } 665 // System.out.println("r = " + r); 666 return r; 667 } 668 669 670 /** 671 * Copy polynomial c. 672 * @param c 673 * @return a copy of c. 674 */ 675 public GenPolynomial<C> copy(GenPolynomial<C> c) { 676 //System.out.println("GP copy = " + this); 677 return new GenPolynomial<C>(this, c.val); 678 } 679 680 681 /** 682 * Copy polynomial list. 683 * @param L polynomial list 684 * @return a copy of L in this ring. 685 */ 686 public List<GenPolynomial<C>> copy(List<GenPolynomial<C>> L) { 687 if (L == null) { 688 return L; 689 } 690 List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(L.size()); 691 for ( GenPolynomial<C> a : L ) { 692 R.add( copy(a) ); 693 } 694 return R; 695 } 696 697 698 /** 699 * Parse a polynomial with the use of GenPolynomialTokenizer. 700 * @param s String. 701 * @return GenPolynomial from s. 702 */ 703 public GenPolynomial<C> parse(String s) { 704 String val = s; 705 if (!s.contains("|")) { 706 val = val.replace("{", "").replace("}", ""); 707 } 708 return parse(new StringReader(val)); 709 } 710 711 712 /** 713 * Parse a polynomial with the use of GenPolynomialTokenizer. 714 * @param r Reader. 715 * @return next GenPolynomial from r. 716 */ 717 @SuppressWarnings({ "unchecked", "cast" }) 718 public GenPolynomial<C> parse(Reader r) { 719 GenPolynomialTokenizer pt = new GenPolynomialTokenizer(this, r); 720 GenPolynomial<C> p = null; 721 try { 722 p = (GenPolynomial<C>) pt.nextPolynomial(); 723 } catch (IOException e) { 724 logger.error(e.toString() + " parse " + this); 725 p = ZERO; 726 } 727 return p; 728 } 729 730 731 /** 732 * Generate univariate polynomial in a given variable with given exponent. 733 * @param x the name of a variable. 734 * @return x as univariate polynomial. 735 */ 736 public GenPolynomial<C> univariate(String x) { 737 return univariate(x, 1L); 738 } 739 740 741 /** 742 * Generate univariate polynomial in a given variable with given exponent. 743 * @param x the name of the variable. 744 * @param e the exponent of the variable. 745 * @return x^e as univariate polynomial. 746 */ 747 public GenPolynomial<C> univariate(String x, long e) { 748 if (vars == null) { // should not happen 749 throw new IllegalArgumentException("no variables defined for polynomial ring"); 750 } 751 if (x == null || x.isEmpty()) { 752 throw new IllegalArgumentException("no variable name given"); 753 } 754 int i; 755 for ( i = 0 ; i < vars.length; i++ ) { 756 if (x.equals(vars[i])) { // use HashMap or TreeMap 757 break; 758 } 759 } 760 if (i >= vars.length) { 761 throw new IllegalArgumentException("variable '" + x + "' not defined in polynomial ring"); 762 } 763 return univariate(0, nvar - i - 1, e); 764 } 765 766 767 /** 768 * Generate univariate polynomial in a given variable. 769 * @param i the index of the variable. 770 * @return X_i as univariate polynomial. 771 */ 772 public GenPolynomial<C> univariate(int i) { 773 return univariate(0, i, 1L); 774 } 775 776 777 /** 778 * Generate univariate polynomial in a given variable with given exponent. 779 * @param i the index of the variable. 780 * @param e the exponent of the variable. 781 * @return X_i^e as univariate polynomial. 782 */ 783 public GenPolynomial<C> univariate(int i, long e) { 784 return univariate(0, i, e); 785 } 786 787 788 /** 789 * Generate univariate polynomial in a given variable with given exponent. 790 * @param modv number of module variables. 791 * @param i the index of the variable. 792 * @param e the exponent of the variable. 793 * @return X_i^e as univariate polynomial. 794 */ 795 public GenPolynomial<C> univariate(int modv, int i, long e) { 796 GenPolynomial<C> p = getZERO(); 797 int r = nvar - modv; 798 if (0 <= i && i < r) { 799 C one = coFac.getONE(); 800 ExpVector f = ExpVector.create(r, i, e); 801 if (modv > 0) { 802 f = f.extend(modv, 0, 0l); 803 } 804 p = p.sum(one, f); 805 } 806 return p; 807 } 808 809 810 /** 811 * Get the generating elements excluding the generators for the coefficient 812 * ring. 813 * @return a list of generating elements for this ring. 814 */ 815 public List<GenPolynomial<C>> getGenerators() { 816 List<? extends GenPolynomial<C>> univs = univariateList(); 817 List<GenPolynomial<C>> gens = new ArrayList<GenPolynomial<C>>(univs.size() + 1); 818 gens.add(getONE()); 819 gens.addAll(univs); 820 return gens; 821 } 822 823 824 /** 825 * Get a list of the generating elements. 826 * @return list of generators for the algebraic structure. 827 * @see edu.jas.structure.ElemFactory#generators() 828 */ 829 public List<GenPolynomial<C>> generators() { 830 List<? extends C> cogens = coFac.generators(); 831 List<? extends GenPolynomial<C>> univs = univariateList(); 832 List<GenPolynomial<C>> gens = new ArrayList<GenPolynomial<C>>(univs.size() + cogens.size()); 833 for (C c : cogens) { 834 gens.add(getONE().multiply(c)); 835 } 836 gens.addAll(univs); 837 return gens; 838 } 839 840 841 /** 842 * Get a list of the generating elements excluding the module variables. 843 * @param modv number of module variables 844 * @return list of generators for the polynomial ring. 845 */ 846 public List<GenPolynomial<C>> generators(int modv) { 847 List<? extends C> cogens = coFac.generators(); 848 List<? extends GenPolynomial<C>> univs = univariateList(modv); 849 List<GenPolynomial<C>> gens = new ArrayList<GenPolynomial<C>>(univs.size() + cogens.size()); 850 for (C c : cogens) { 851 gens.add(getONE().multiply(c)); 852 } 853 gens.addAll(univs); 854 return gens; 855 } 856 857 858 /** 859 * Is this structure finite or infinite. 860 * @return true if this structure is finite, else false. 861 * @see edu.jas.structure.ElemFactory#isFinite() 862 */ 863 public boolean isFinite() { 864 return (nvar == 0) && coFac.isFinite(); 865 } 866 867 868 /** 869 * Generate list of univariate polynomials in all variables. 870 * @return List(X_1,...,X_n) a list of univariate polynomials. 871 */ 872 public List<? extends GenPolynomial<C>> univariateList() { 873 return univariateList(0, 1L); 874 } 875 876 877 /** 878 * Generate list of univariate polynomials in all variables. 879 * @param modv number of module variables. 880 * @return List(X_1,...,X_n) a list of univariate polynomials. 881 */ 882 public List<? extends GenPolynomial<C>> univariateList(int modv) { 883 return univariateList(modv, 1L); 884 } 885 886 887 /** 888 * Generate list of univariate polynomials in all variables with given 889 * exponent. 890 * @param modv number of module variables. 891 * @param e the exponent of the variables. 892 * @return List(X_1^e,...,X_n^e) a list of univariate polynomials. 893 */ 894 public List<? extends GenPolynomial<C>> univariateList(int modv, long e) { 895 List<GenPolynomial<C>> pols = new ArrayList<GenPolynomial<C>>(nvar); 896 int nm = nvar - modv; 897 for (int i = 0; i < nm; i++) { 898 GenPolynomial<C> p = univariate(modv, nm - 1 - i, e); 899 pols.add(p); 900 } 901 return pols; 902 } 903 904 905 /** 906 * Extend variables. Used e.g. in module embedding. Extend number of 907 * variables by i. 908 * @param i number of variables to extend. 909 * @return extended polynomial ring factory. 910 */ 911 public GenPolynomialRing<C> extend(int i) { 912 // add module variable names 913 String[] v = newVars("e", i); 914 return extend(v); 915 } 916 917 918 /** 919 * Extend variables. Used e.g. in module embedding. Extend number of 920 * variables by length(vn). 921 * @param vn names for extended variables. 922 * @return extended polynomial ring factory. 923 */ 924 public GenPolynomialRing<C> extend(String[] vn) { 925 if (vn == null || vars == null) { 926 throw new IllegalArgumentException("vn and vars may not be null"); 927 } 928 int i = vn.length; 929 String[] v = new String[vars.length + i]; 930 for (int k = 0; k < vars.length; k++) { 931 v[k] = vars[k]; 932 } 933 for (int k = 0; k < vn.length; k++) { 934 v[vars.length + k] = vn[k]; 935 } 936 937 TermOrder to = tord.extend(nvar, i); 938 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar + i, to, v); 939 return pfac; 940 } 941 942 943 /** 944 * Extend lower variables. Extend number of variables by i. 945 * @param i number of variables to extend. 946 * @return extended polynomial ring factory. 947 */ 948 public GenPolynomialRing<C> extendLower(int i) { 949 String[] v = newVars("e", i); 950 return extendLower(v); 951 } 952 953 954 /** 955 * Extend lower variables. Extend number of variables by length(vn). 956 * @param vn names for extended lower variables. 957 * @return extended polynomial ring factory. 958 */ 959 public GenPolynomialRing<C> extendLower(String[] vn) { 960 if (vn == null || vars == null) { 961 throw new IllegalArgumentException("vn and vars may not be null"); 962 } 963 int i = vn.length; 964 String[] v = new String[vars.length + i]; 965 for (int k = 0; k < vn.length; k++) { 966 v[k] = vn[k]; 967 } 968 for (int k = 0; k < vars.length; k++) { 969 v[vn.length + k] = vars[k]; 970 } 971 TermOrder to = tord.extendLower(nvar, i); 972 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar + i, to, v); 973 return pfac; 974 } 975 976 977 /** 978 * Contract variables. Used e.g. in module embedding. Contract number of 979 * variables by i. 980 * @param i number of variables to remove. 981 * @return contracted polynomial ring factory. 982 */ 983 public GenPolynomialRing<C> contract(int i) { 984 String[] v = null; 985 if (vars != null) { 986 v = new String[vars.length - i]; 987 for (int j = 0; j < vars.length - i; j++) { 988 v[j] = vars[j]; 989 } 990 } 991 TermOrder to = tord.contract(i, nvar - i); 992 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar - i, to, v); 993 return pfac; 994 } 995 996 997 /** 998 * Recursive representation as polynomial with i main variables. 999 * @param i number of main variables. 1000 * @return recursive polynomial ring factory. 1001 */ 1002 public GenPolynomialRing<GenPolynomial<C>> recursive(int i) { 1003 if (i <= 0 || i >= nvar) { 1004 throw new IllegalArgumentException("wrong: 0 < " + i + " < " + nvar); 1005 } 1006 GenPolynomialRing<C> cfac = contract(i); 1007 String[] v = null; 1008 if (vars != null) { 1009 v = new String[i]; 1010 int k = 0; 1011 for (int j = nvar - i; j < nvar; j++) { 1012 v[k++] = vars[j]; 1013 } 1014 } 1015 TermOrder to = tord.contract(0, i); // ?? 1016 GenPolynomialRing<GenPolynomial<C>> pfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, i, to, v); 1017 return pfac; 1018 } 1019 1020 1021 /** 1022 * Distributive representation as polynomial with all main variables. 1023 * @return distributive polynomial ring factory. 1024 */ 1025 @SuppressWarnings("cast") 1026 public GenPolynomialRing<C> distribute() { 1027 if (!(coFac instanceof GenPolynomialRing)) { 1028 return this; 1029 } 1030 RingFactory cf = coFac; 1031 RingFactory<GenPolynomial<C>> cfp = (RingFactory<GenPolynomial<C>>) cf; 1032 GenPolynomialRing cr = (GenPolynomialRing) cfp; 1033 GenPolynomialRing<C> pfac; 1034 if (cr.vars != null) { 1035 pfac = extend(cr.vars); 1036 } else { 1037 pfac = extend(cr.nvar); 1038 } 1039 return pfac; 1040 } 1041 1042 1043 /** 1044 * Reverse variables. Used e.g. in opposite rings. 1045 * @return polynomial ring factory with reversed variables. 1046 */ 1047 public GenPolynomialRing<C> reverse() { 1048 return reverse(false); 1049 } 1050 1051 1052 /** 1053 * Reverse variables. Used e.g. in opposite rings. 1054 * @param partial true for partialy reversed term orders. 1055 * @return polynomial ring factory with reversed variables. 1056 */ 1057 public GenPolynomialRing<C> reverse(boolean partial) { 1058 String[] v = null; 1059 if (vars != null) { // vars are not inversed 1060 v = new String[vars.length]; 1061 int k = tord.getSplit(); 1062 if (partial && k < vars.length) { 1063 // copy upper 1064 for (int j = 0; j < k; j++) { 1065 //v[vars.length - k + j] = vars[vars.length - 1 - j]; // reverse upper 1066 v[vars.length - k + j] = vars[vars.length - k + j]; 1067 } 1068 // reverse lower 1069 for (int j = 0; j < vars.length - k; j++) { 1070 //v[j] = vars[j]; // copy upper 1071 v[j] = vars[vars.length - k - j - 1]; 1072 } 1073 } else { 1074 for (int j = 0; j < vars.length; j++) { 1075 v[j] = vars[vars.length - 1 - j]; 1076 } 1077 } 1078 //System.out.println("vars = " + Arrays.toString(vars)); 1079 //System.out.println("v = " + Arrays.toString(v)); 1080 } 1081 TermOrder to = tord.reverse(partial); 1082 GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(coFac, nvar, to, v); 1083 pfac.partial = partial; 1084 return pfac; 1085 } 1086 1087 1088 /** 1089 * Get PolynomialComparator. 1090 * @return polynomial comparator. 1091 */ 1092 public PolynomialComparator<C> getComparator() { 1093 return new PolynomialComparator<C>(tord, false); 1094 } 1095 1096 1097 /** 1098 * Get PolynomialComparator. 1099 * @param rev for reverse comparator. 1100 * @return polynomial comparator. 1101 */ 1102 public PolynomialComparator<C> getComparator(boolean rev) { 1103 return new PolynomialComparator<C>(tord, rev); 1104 } 1105 1106 1107 /** 1108 * New variable names. Generate new names for variables, 1109 * @param prefix name prefix. 1110 * @param n number of variables. 1111 * @return new variable names. 1112 */ 1113 public static String[] newVars(String prefix, int n) { 1114 String[] vars = new String[n]; 1115 synchronized (knownVars) { 1116 int m = knownVars.size(); 1117 String name = prefix + m; 1118 for (int i = 0; i < n; i++) { 1119 while (knownVars.contains(name)) { 1120 m++; 1121 name = prefix + m; 1122 } 1123 vars[i] = name; 1124 //System.out.println("new variable: " + name); 1125 knownVars.add(name); 1126 m++; 1127 name = prefix + m; 1128 } 1129 } 1130 return vars; 1131 } 1132 1133 1134 /** 1135 * New variable names. Generate new names for variables, 1136 * @param prefix name prefix. 1137 * @return new variable names. 1138 */ 1139 public String[] newVars(String prefix) { 1140 return newVars(prefix, nvar); 1141 } 1142 1143 1144 /** 1145 * New variable names. Generate new names for variables, 1146 * @param n number of variables. 1147 * @return new variable names. 1148 */ 1149 public static String[] newVars(int n) { 1150 return newVars("x", n); 1151 } 1152 1153 1154 /** 1155 * New variable names. Generate new names for variables, 1156 * @return new variable names. 1157 */ 1158 public String[] newVars() { 1159 return newVars(nvar); 1160 } 1161 1162 1163 /** 1164 * Add variable names. 1165 * @param vars variable names to be recorded. 1166 */ 1167 public static void addVars(String[] vars) { 1168 if (vars == null) { 1169 return; 1170 } 1171 synchronized (knownVars) { 1172 for (int i = 0; i < vars.length; i++) { 1173 knownVars.add(vars[i]); // eventualy names 'overwritten' 1174 } 1175 } 1176 } 1177 1178 1179 /** 1180 * Permute variable names. 1181 * @param vars variable names. 1182 * @param P permutation. 1183 * @return P(vars). 1184 */ 1185 public static String[] permuteVars(List<Integer> P, String[] vars) { 1186 if (vars == null || vars.length <= 1) { 1187 return vars; 1188 } 1189 String[] b = new String[vars.length]; 1190 int j = 0; 1191 for (Integer i : P) { 1192 b[j++] = vars[i]; 1193 } 1194 return b; 1195 } 1196 1197 1198 /** 1199 * Permutation of polynomial ring variables. 1200 * @param P permutation. 1201 * @return P(this). 1202 */ 1203 public GenPolynomialRing<C> permutation(List<Integer> P) { 1204 if (nvar <= 1) { 1205 return this; 1206 } 1207 TermOrder tp = tord.permutation(P); 1208 if (vars == null) { 1209 return new GenPolynomialRing<C>(coFac, nvar, tp); 1210 } 1211 String[] v1 = new String[vars.length]; 1212 for (int i = 0; i < v1.length; i++) { 1213 v1[i] = vars[v1.length - 1 - i]; 1214 } 1215 String[] vp = permuteVars(P, v1); 1216 String[] v2 = new String[vp.length]; 1217 for (int i = 0; i < vp.length; i++) { 1218 v2[i] = vp[vp.length - 1 - i]; 1219 } 1220 return new GenPolynomialRing<C>(coFac, nvar, tp, v2); 1221 } 1222 1223 1224 /** 1225 * Get a GenPolynomial iterator. 1226 * @return an iterator over all polynomials. 1227 */ 1228 public Iterator<GenPolynomial<C>> iterator() { 1229 if (coFac.isFinite()) { 1230 return new GenPolynomialIterator<C>(this); 1231 } 1232 logger.warn("ring of coefficients " + coFac 1233 + " is infinite, constructing iterator only over monomials"); 1234 return new GenPolynomialMonomialIterator<C>(this); 1235 //throw new IllegalArgumentException("only for finite iterable coefficients implemented"); 1236 } 1237 1238} 1239 1240 1241/** 1242 * Polynomial iterator. 1243 * @author Heinz Kredel 1244 */ 1245class GenPolynomialIterator<C extends RingElem<C>> implements Iterator<GenPolynomial<C>> { 1246 1247 1248 /** 1249 * data structure. 1250 */ 1251 final GenPolynomialRing<C> ring; 1252 1253 1254 final Iterator<List<Long>> eviter; 1255 1256 1257 final List<ExpVector> powers; 1258 1259 1260 final List<Iterable<C>> coeffiter; 1261 1262 1263 Iterator<List<C>> itercoeff; 1264 1265 1266 GenPolynomial<C> current; 1267 1268 1269 /** 1270 * Polynomial iterator constructor. 1271 */ 1272 @SuppressWarnings("unchecked") 1273 public GenPolynomialIterator(GenPolynomialRing<C> fac) { 1274 ring = fac; 1275 LongIterable li = new LongIterable(); 1276 li.setNonNegativeIterator(); 1277 List<Iterable<Long>> tlist = new ArrayList<Iterable<Long>>(ring.nvar); 1278 for (int i = 0; i < ring.nvar; i++) { 1279 tlist.add(li); 1280 } 1281 CartesianProductInfinite<Long> ei = new CartesianProductInfinite<Long>(tlist); 1282 eviter = ei.iterator(); 1283 RingFactory<C> cf = ring.coFac; 1284 coeffiter = new ArrayList<Iterable<C>>(); 1285 if (cf instanceof Iterable && cf.isFinite()) { 1286 Iterable<C> cfi = (Iterable<C>) cf; 1287 coeffiter.add(cfi); 1288 } else { 1289 throw new IllegalArgumentException("only for finite iterable coefficients implemented"); 1290 } 1291 CartesianProduct<C> tuples = new CartesianProduct<C>(coeffiter); 1292 itercoeff = tuples.iterator(); 1293 powers = new ArrayList<ExpVector>(); 1294 ExpVector e = ExpVector.create(eviter.next()); 1295 powers.add(e); 1296 //System.out.println("new e = " + e); 1297 //System.out.println("powers = " + powers); 1298 List<C> c = itercoeff.next(); 1299 //System.out.println("coeffs = " + c); 1300 current = new GenPolynomial<C>(ring, c.get(0), e); 1301 } 1302 1303 1304 /** 1305 * Test for availability of a next element. 1306 * @return true if the iteration has more elements, else false. 1307 */ 1308 public boolean hasNext() { 1309 return true; 1310 } 1311 1312 1313 /** 1314 * Get next polynomial. 1315 * @return next polynomial. 1316 */ 1317 public synchronized GenPolynomial<C> next() { 1318 GenPolynomial<C> res = current; 1319 if (!itercoeff.hasNext()) { 1320 ExpVector e = ExpVector.create(eviter.next()); 1321 powers.add(0, e); // add new ev at beginning 1322 //System.out.println("new e = " + e); 1323 //System.out.println("powers = " + powers); 1324 if (coeffiter.size() == 1) { // shorten frist iterator by one element 1325 coeffiter.add(coeffiter.get(0)); 1326 Iterable<C> it = coeffiter.get(0); 1327 List<C> elms = new ArrayList<C>(); 1328 for (C elm : it) { 1329 elms.add(elm); 1330 } 1331 elms.remove(0); 1332 coeffiter.set(0, elms); 1333 } else { 1334 coeffiter.add(coeffiter.get(1)); 1335 } 1336 CartesianProduct<C> tuples = new CartesianProduct<C>(coeffiter); 1337 itercoeff = tuples.iterator(); 1338 } 1339 List<C> coeffs = itercoeff.next(); 1340 // while ( coeffs.get(0).isZERO() ) { 1341 // System.out.println(" skip zero "); 1342 // coeffs = itercoeff.next(); // skip tuples with zero in first component 1343 // } 1344 //System.out.println("coeffs = " + coeffs); 1345 GenPolynomial<C> pol = ring.getZERO().copy(); 1346 int i = 0; 1347 for (ExpVector f : powers) { 1348 C c = coeffs.get(i++); 1349 if (c.isZERO()) { 1350 continue; 1351 } 1352 if (pol.val.get(f) != null) { 1353 System.out.println("error f in pol = " + f + ", " + pol.getMap().get(f)); 1354 throw new RuntimeException("error in iterator"); 1355 } 1356 pol.doPutToMap(f, c); 1357 } 1358 current = pol; 1359 return res; 1360 } 1361 1362 1363 /** 1364 * Remove an element if allowed. 1365 */ 1366 public void remove() { 1367 throw new UnsupportedOperationException("cannnot remove elements"); 1368 } 1369} 1370 1371 1372/** 1373 * Polynomial monomial iterator. 1374 * @author Heinz Kredel 1375 */ 1376class GenPolynomialMonomialIterator<C extends RingElem<C>> implements Iterator<GenPolynomial<C>> { 1377 1378 1379 /** 1380 * data structure. 1381 */ 1382 final GenPolynomialRing<C> ring; 1383 1384 1385 final Iterator<List> iter; 1386 1387 1388 GenPolynomial<C> current; 1389 1390 1391 /** 1392 * Polynomial iterator constructor. 1393 */ 1394 @SuppressWarnings("unchecked") 1395 public GenPolynomialMonomialIterator(GenPolynomialRing<C> fac) { 1396 ring = fac; 1397 LongIterable li = new LongIterable(); 1398 li.setNonNegativeIterator(); 1399 List<Iterable<Long>> tlist = new ArrayList<Iterable<Long>>(ring.nvar); 1400 for (int i = 0; i < ring.nvar; i++) { 1401 tlist.add(li); 1402 } 1403 CartesianProductInfinite<Long> ei = new CartesianProductInfinite<Long>(tlist); 1404 //Iterator<List<Long>> eviter = ei.iterator(); 1405 1406 RingFactory<C> cf = ring.coFac; 1407 Iterable<C> coeffiter; 1408 if (cf instanceof Iterable && !cf.isFinite()) { 1409 Iterable<C> cfi = (Iterable<C>) cf; 1410 coeffiter = cfi; 1411 } else { 1412 throw new IllegalArgumentException("only for infinite iterable coefficients implemented"); 1413 } 1414 1415 // Cantor iterator for exponents and coeffcients 1416 List<Iterable> eci = new ArrayList<Iterable>(2); // no type parameter 1417 eci.add(ei); 1418 eci.add(coeffiter); 1419 CartesianProductInfinite ecp = new CartesianProductInfinite(eci); 1420 iter = ecp.iterator(); 1421 1422 List ec = iter.next(); 1423 List<Long> ecl = (List<Long>) ec.get(0); 1424 C c = (C) ec.get(1); // zero 1425 ExpVector e = ExpVector.create(ecl); 1426 //System.out.println("exp = " + e); 1427 //System.out.println("coeffs = " + c); 1428 current = new GenPolynomial<C>(ring, c, e); 1429 } 1430 1431 1432 /** 1433 * Test for availability of a next element. 1434 * @return true if the iteration has more elements, else false. 1435 */ 1436 public boolean hasNext() { 1437 return true; 1438 } 1439 1440 1441 /** 1442 * Get next polynomial. 1443 * @return next polynomial. 1444 */ 1445 @SuppressWarnings("unchecked") 1446 public synchronized GenPolynomial<C> next() { 1447 GenPolynomial<C> res = current; 1448 1449 List ec = iter.next(); 1450 C c = (C) ec.get(1); 1451 while (c.isZERO()) { // zero already done in first next 1452 ec = iter.next(); 1453 c = (C) ec.get(1); 1454 } 1455 List<Long> ecl = (List<Long>) ec.get(0); 1456 ExpVector e = ExpVector.create(ecl); 1457 //System.out.println("exp = " + e); 1458 //System.out.println("coeffs = " + c); 1459 current = new GenPolynomial<C>(ring, c, e); 1460 1461 return res; 1462 } 1463 1464 1465 /** 1466 * Remove an element if allowed. 1467 */ 1468 public void remove() { 1469 throw new UnsupportedOperationException("cannnot remove elements"); 1470 } 1471}