001/* 002 * $Id: GenWordPolynomialRing.java 4225 2012-09-29 20:27:56Z kredel $ 003 */ 004 005package edu.jas.poly; 006 007 008import java.io.Reader; 009import java.io.StringReader; 010import java.math.BigInteger; 011import java.util.ArrayList; 012import java.util.List; 013import java.util.Map; 014import java.util.Random; 015 016import org.apache.log4j.Logger; 017 018import edu.jas.kern.PreemptStatus; 019import edu.jas.kern.Scripting; 020import edu.jas.structure.RingElem; 021import edu.jas.structure.RingFactory; 022 023 024/** 025 * GenWordPolynomialRing generic polynomial factory implementing RingFactory; 026 * Factory for non-commutative string polynomials over C. 027 * @param <C> coefficient type 028 * @author Heinz Kredel 029 */ 030 031public final class GenWordPolynomialRing<C extends RingElem<C>> implements RingFactory<GenWordPolynomial<C>> 032 /*, Iterable<GenWordPolynomial<C>>*/{ 033 034 035 /** 036 * The factory for the coefficients. 037 */ 038 public final RingFactory<C> coFac; 039 040 041 /** 042 * The factory for the alphabet. 043 */ 044 public final WordFactory alphabet; 045 046 047 /** 048 * The constant polynomial 0 for this ring. 049 */ 050 public final GenWordPolynomial<C> ZERO; 051 052 053 /** 054 * The constant polynomial 1 for this ring. 055 */ 056 public final GenWordPolynomial<C> ONE; 057 058 059 /** 060 * The constant empty word exponent for this ring. 061 */ 062 public final Word wone; 063 064 065 /** 066 * A default random sequence generator. 067 */ 068 final static Random random = new Random(); 069 070 071 /** 072 * Indicator if this ring is a field. 073 */ 074 private int isField = -1; // initially unknown 075 076 077 /** 078 * Log4j logger object. 079 */ 080 private static final Logger logger = Logger.getLogger(GenWordPolynomialRing.class); 081 082 083 /** 084 * Flag to enable if preemptive interrrupt is checked. 085 */ 086 final boolean checkPreempt = PreemptStatus.isAllowed(); 087 088 089 /** 090 * The constructor creates a polynomial factory object with the default term 091 * order. 092 * @param cf factory for coefficients of type C. 093 * @param wf factory for strings. 094 */ 095 public GenWordPolynomialRing(RingFactory<C> cf, WordFactory wf) { 096 coFac = cf; 097 alphabet = wf; 098 ZERO = new GenWordPolynomial<C>(this); 099 C coeff = coFac.getONE(); 100 wone = wf.getONE(); 101 ONE = new GenWordPolynomial<C>(this, coeff, wone); 102 } 103 104 105 /** 106 * The constructor creates a polynomial factory object. 107 * @param cf factory for coefficients of type C. 108 * @param o other polynomial ring. 109 */ 110 public GenWordPolynomialRing(RingFactory<C> cf, GenWordPolynomialRing o) { 111 this(cf, o.alphabet); 112 } 113 114 115 /** 116 * The constructor creates a polynomial factory object. 117 * @param fac polynomial ring. 118 */ 119 public GenWordPolynomialRing(GenPolynomialRing fac) { 120 this(fac.coFac, new WordFactory(fac.vars)); 121 } 122 123 124 /** 125 * Copy this factory. 126 * @return a clone of this. 127 */ 128 public GenWordPolynomialRing<C> copy() { 129 return new GenWordPolynomialRing<C>(coFac, this); 130 } 131 132 133 /** 134 * Get the String representation. 135 * @see java.lang.Object#toString() 136 */ 137 @Override 138 public String toString() { 139 StringBuffer s = new StringBuffer(); 140 s.append("WordPolyRing("); 141 if (coFac instanceof RingElem) { 142 s.append(((RingElem<C>) coFac).toScriptFactory()); 143 } else { 144 s.append(coFac.toString().trim()); 145 } 146 s.append(","); 147 s.append(alphabet.toString()); 148 s.append(")"); 149 return s.toString(); 150 } 151 152 153 /** 154 * Get a scripting compatible string representation. 155 * @return script compatible representation for this Element. 156 * @see edu.jas.structure.Element#toScript() 157 */ 158 //JAVA6only: @Override 159 public String toScript() { 160 StringBuffer s = new StringBuffer(); 161 switch (Scripting.getLang()) { 162 case Ruby: 163 s.append("WordPolyRing.new("); 164 break; 165 case Python: 166 default: 167 s.append("WordPolyRing("); 168 } 169 if (coFac instanceof RingElem) { 170 s.append(((RingElem<C>) coFac).toScriptFactory()); 171 } else { 172 s.append(coFac.toScript().trim()); 173 } 174 s.append(","); 175 s.append(alphabet.toScript()); 176 s.append(")"); 177 return s.toString(); 178 } 179 180 181 /** 182 * Comparison with any other object. 183 * @see java.lang.Object#equals(java.lang.Object) 184 */ 185 @Override 186 @SuppressWarnings("unchecked") 187 public boolean equals(Object other) { 188 if (!(other instanceof GenWordPolynomialRing)) { 189 return false; 190 } 191 GenWordPolynomialRing<C> oring = null; 192 try { 193 oring = (GenWordPolynomialRing<C>) other; 194 } catch (ClassCastException ignored) { 195 } 196 if (oring == null) { 197 return false; 198 } 199 if (!coFac.equals(oring.coFac)) { 200 return false; 201 } 202 if (!alphabet.equals(oring.alphabet)) { 203 return false; 204 } 205 return true; 206 } 207 208 209 /** 210 * Hash code for this polynomial ring. 211 * @see java.lang.Object#hashCode() 212 */ 213 @Override 214 public int hashCode() { 215 int h; 216 h = (coFac.hashCode() << 11); 217 h += alphabet.hashCode(); 218 return h; 219 } 220 221 222 /** 223 * Get the variable names. 224 * @return vars. 225 */ 226 public String getVars() { 227 return alphabet.getVal(); // Java-5: Arrays.copyOf(vars,vars.length); 228 } 229 230 231 /** 232 * Get the zero element from the coefficients. 233 * @return 0 as C. 234 */ 235 public C getZEROCoefficient() { 236 return coFac.getZERO(); 237 } 238 239 240 /** 241 * Get the one element from the coefficients. 242 * @return 1 as C. 243 */ 244 public C getONECoefficient() { 245 return coFac.getONE(); 246 } 247 248 249 /** 250 * Get the zero element. 251 * @return 0 as GenWordPolynomial<C>. 252 */ 253 public GenWordPolynomial<C> getZERO() { 254 return ZERO; 255 } 256 257 258 /** 259 * Get the one element. 260 * @return 1 as GenWordPolynomial<C>. 261 */ 262 public GenWordPolynomial<C> getONE() { 263 return ONE; 264 } 265 266 267 /** 268 * Query if this ring is commutative. 269 * @return true if this ring is commutative, else false. 270 */ 271 public boolean isCommutative() { 272 return coFac.isCommutative() && alphabet.isFinite(); 273 } 274 275 276 /** 277 * Query if this ring is associative. 278 * @return true if this ring is associative, else false. 279 */ 280 public boolean isAssociative() { 281 return coFac.isAssociative(); 282 } 283 284 285 /** 286 * Is this structure finite or infinite. 287 * @return true if this structure is finite, else false. 288 * @see edu.jas.structure.ElemFactory#isFinite() 289 */ 290 public boolean isFinite() { 291 return alphabet.isFinite() && coFac.isFinite(); 292 } 293 294 295 /** 296 * Query if this ring is a field. 297 * @return false. 298 */ 299 public boolean isField() { 300 if (isField > 0) { 301 return true; 302 } 303 if (isField == 0) { 304 return false; 305 } 306 if (coFac.isField() && alphabet.isFinite()) { 307 isField = 1; 308 return true; 309 } 310 isField = 0; 311 return false; 312 } 313 314 315 /** 316 * Characteristic of this ring. 317 * @return characteristic of this ring. 318 */ 319 public java.math.BigInteger characteristic() { 320 return coFac.characteristic(); 321 } 322 323 324 /** 325 * Get a (constant) GenWordPolynomial<C> element from a coefficient 326 * value. 327 * @param a coefficient. 328 * @return a GenWordPolynomial<C>. 329 */ 330 public GenWordPolynomial<C> valueOf(C a) { 331 return new GenWordPolynomial<C>(this, a); 332 } 333 334 335 /** 336 * Get a GenWordPolynomial<C> element from a word. 337 * @param e word. 338 * @return a GenWordPolynomial<C>. 339 */ 340 public GenWordPolynomial<C> valueOf(Word e) { 341 return new GenWordPolynomial<C>(this, coFac.getONE(), e); 342 } 343 344 345 /** 346 * Get a GenWordPolynomial<C> element from a coeffcient and a word. 347 * @param a coefficient. 348 * @param e word. 349 * @return a GenWordPolynomial<C>. 350 */ 351 public GenWordPolynomial<C> valueOf(C a, Word e) { 352 return new GenWordPolynomial<C>(this, a, e); 353 } 354 355 356 /** 357 * Get a GenWordPolynomial<C> element from a GenPolynomial<C>. 358 * @param a GenPolynomial. 359 * @return a GenWordPolynomial<C>. 360 */ 361 public GenWordPolynomial<C> valueOf(GenPolynomial<C> a) { 362 if ( a.isZERO() ) { 363 return getZERO(); 364 } 365 if ( a.isONE() ) { 366 return getONE(); 367 } 368 GenWordPolynomial<C> p = this.getZERO().copy(); 369 for (Map.Entry<ExpVector, C> m : a.val.entrySet()) { 370 C c = m.getValue(); 371 ExpVector e = m.getKey(); 372 Word w = alphabet.valueOf(e); 373 p.doPutToMap(w,c); 374 } 375 return p; 376 } 377 378 379 /** 380 * Get a list of GenWordPolynomial<C> element from a list of GenPolynomial<C>. 381 * @param A GenPolynomial list. 382 * @return a GenWordPolynomial<C> list. 383 */ 384 public List<GenWordPolynomial<C>> valueOf(List<GenPolynomial<C>> A) { 385 List<GenWordPolynomial<C>> B = new ArrayList<GenWordPolynomial<C>>(A.size()); 386 if ( A.isEmpty() ) { 387 return B; 388 } 389 for (GenPolynomial<C> a : A) { 390 GenWordPolynomial<C> b = valueOf(a); 391 B.add(b); 392 } 393 return B; 394 } 395 396 397 /** 398 * Get a (constant) GenWordPolynomial<C> element from a long value. 399 * @param a long. 400 * @return a GenWordPolynomial<C>. 401 */ 402 public GenWordPolynomial<C> fromInteger(long a) { 403 return new GenWordPolynomial<C>(this, coFac.fromInteger(a), wone); 404 } 405 406 407 /** 408 * Get a (constant) GenWordPolynomial<C> element from a BigInteger 409 * value. 410 * @param a BigInteger. 411 * @return a GenWordPolynomial<C>. 412 */ 413 public GenWordPolynomial<C> fromInteger(BigInteger a) { 414 return new GenWordPolynomial<C>(this, coFac.fromInteger(a), wone); 415 } 416 417 418 /** 419 * Random polynomial. Generates a random polynomial. 420 * @param n number of terms. 421 * @return a random polynomial. 422 */ 423 public GenWordPolynomial<C> random(int n) { 424 return random(n, random); 425 } 426 427 428 /** 429 * Random polynomial. Generates a random polynomial with k = 5, l = n, d = 3. 430 * @param n number of terms. 431 * @param rnd is a source for random bits. 432 * @return a random polynomial. 433 */ 434 public GenWordPolynomial<C> random(int n, Random rnd) { 435 return random(5, n, 3, rnd); 436 } 437 438 439 /** 440 * Generate a random polynomial. 441 * @param k bitsize of random coefficients. 442 * @param l number of terms. 443 * @param d maximal length of a random word. 444 * @return a random polynomial. 445 */ 446 public GenWordPolynomial<C> random(int k, int l, int d) { 447 return random(k, l, d, random); 448 } 449 450 451 /** 452 * Generate a random polynomial. 453 * @param k bitsize of random coefficients. 454 * @param l number of terms. 455 * @param d maximal length of a random word. 456 * @param rnd is a source for random bits. 457 * @return a random polynomial. 458 */ 459 public GenWordPolynomial<C> random(int k, int l, int d, Random rnd) { 460 GenWordPolynomial<C> r = getZERO(); //.clone() or copy( ZERO ); 461 // add l random coeffs and words of maximal length d 462 for (int i = 0; i < l; i++) { 463 int di = Math.abs(rnd.nextInt() % d); 464 Word e = alphabet.random(di, rnd); 465 C a = coFac.random(k, rnd); 466 r = r.sum(a, e); // somewhat inefficient but clean 467 //System.out.println("e = " + e + " a = " + a); 468 } 469 return r; 470 } 471 472 473 /** 474 * Copy polynomial c. 475 * @param c polynomial to copy. 476 * @return a copy of c. 477 */ 478 public GenWordPolynomial<C> copy(GenWordPolynomial<C> c) { 479 return new GenWordPolynomial<C>(this, c.val); 480 } 481 482 483 /** 484 * Parse a polynomial with the use of GenWordPolynomialTokenizer. 485 * @param s String. 486 * @return GenWordPolynomial from s. 487 */ 488 public GenWordPolynomial<C> parse(String s) { 489 String val = s; 490 if (!s.contains("|")) { 491 val = val.replace("{", "").replace("}", ""); 492 } 493 return parse(new StringReader(val)); 494 } 495 496 497 /** 498 * Parse a polynomial with the use of GenWordPolynomialTokenizer. 499 * @param r Reader. 500 * @return next GenWordPolynomial from r. 501 */ 502 @SuppressWarnings("unchecked") 503 public GenWordPolynomial<C> parse(Reader r) { 504 logger.error("parse not implemented"); 505 throw new UnsupportedOperationException("not implemented"); 506 // GenWordPolynomialTokenizer pt = new GenWordPolynomialTokenizer(this, r); 507 // GenWordPolynomial<C> p = null; 508 // try { 509 // p = (GenWordPolynomial<C>) pt.nextPolynomial(); 510 // } catch (IOException e) { 511 // logger.error(e.toString() + " parse " + this); 512 // p = ZERO; 513 // } 514 // return p; 515 } 516 517 518 /** 519 * Generate univariate polynomial in a given variable. 520 * @param i the index of the variable. 521 * @return X_i as univariate polynomial. 522 */ 523 public GenWordPolynomial<C> univariate(int i) { 524 GenWordPolynomial<C> p = getZERO(); 525 List<Word> wgen = alphabet.generators(); 526 if (0 <= i && i < wgen.size()) { 527 C one = coFac.getONE(); 528 Word f = wgen.get(i); 529 p = p.sum(one, f); 530 } 531 return p; 532 } 533 534 535 /** 536 * Generate list of univariate polynomials in all variables. 537 * @return List(X_1,...,X_n) a list of univariate polynomials. 538 */ 539 public List<GenWordPolynomial<C>> univariateList() { 540 int n = alphabet.length(); 541 List<GenWordPolynomial<C>> pols = new ArrayList<GenWordPolynomial<C>>(n); 542 for (int i = 0; i < n; i++) { 543 GenWordPolynomial<C> p = univariate(i); 544 pols.add(p); 545 } 546 return pols; 547 } 548 549 550 /** 551 * Get the generating elements <b>excluding</b> the generators for the coefficient 552 * ring. 553 * @return a list of generating elements for this ring. 554 */ 555 public List<GenWordPolynomial<C>> getGenerators() { 556 List<GenWordPolynomial<C>> univs = univariateList(); 557 List<GenWordPolynomial<C>> gens = new ArrayList<GenWordPolynomial<C>>(univs.size() + 1); 558 gens.add(getONE()); 559 gens.addAll(univs); 560 return gens; 561 } 562 563 564 /** 565 * Get a list of all generating elements. 566 * @return list of generators for the algebraic structure. 567 * @see edu.jas.structure.ElemFactory#generators() 568 */ 569 public List<GenWordPolynomial<C>> generators() { 570 List<C> cogens = coFac.generators(); 571 List<GenWordPolynomial<C>> univs = univariateList(); 572 List<GenWordPolynomial<C>> gens = new ArrayList<GenWordPolynomial<C>>(univs.size() + cogens.size()); 573 for (C c : cogens) { 574 gens.add(getONE().multiply(c)); 575 } 576 gens.addAll(univs); 577 return gens; 578 } 579 580}