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