001/* 002 * $Id$ 003 */ 004 005package edu.jas.poly; 006 007 008import java.io.Serializable; 009import java.util.ArrayList; 010import java.util.List; 011import java.util.Map; 012import java.util.SortedSet; 013import java.util.TreeSet; 014 015import org.apache.logging.log4j.Logger; 016import org.apache.logging.log4j.LogManager; 017 018import edu.jas.kern.Scripting; 019import edu.jas.structure.RingElem; 020 021 022/** 023 * List of polynomials. Mainly for storage and printing / toString and 024 * conversions to other representations. 025 * @author Heinz Kredel 026 */ 027 028public class PolynomialList<C extends RingElem<C>> implements Comparable<PolynomialList<C>>, Serializable { 029 030 031 /** 032 * The factory for the solvable polynomial ring. 033 */ 034 public final GenPolynomialRing<C> ring; 035 036 037 /** 038 * The data structure is a List of polynomials. 039 */ 040 public final List<GenPolynomial<C>> list; 041 042 043 private static final Logger logger = LogManager.getLogger(PolynomialList.class); 044 045 046 /** 047 * Constructor. 048 * @param r polynomial ring factory. 049 * @param l list of polynomials. 050 */ 051 public PolynomialList(GenPolynomialRing<C> r, List<GenPolynomial<C>> l) { 052 ring = r; 053 list = l; 054 } 055 056 057 /** 058 * Constructor. 059 * @param r solvable polynomial ring factory. 060 * @param l list of solvable polynomials. 061 */ 062 public PolynomialList(GenSolvablePolynomialRing<C> r, List<GenSolvablePolynomial<C>> l) { 063 this(r, PolynomialList.<C> castToList(l)); 064 } 065 066 067 /** 068 * Copy this. 069 * @return a copy of this. 070 */ 071 public PolynomialList<C> copy() { 072 return new PolynomialList<C>(ring, new ArrayList<GenPolynomial<C>>(list)); 073 } 074 075 076 /** 077 * Comparison with any other object. 078 * @see java.lang.Object#equals(java.lang.Object) 079 */ 080 @Override 081 @SuppressWarnings("unchecked") 082 public boolean equals(Object p) { 083 if (p == null) { 084 return false; 085 } 086 if (!(p instanceof PolynomialList)) { 087 System.out.println("no PolynomialList"); 088 return false; 089 } 090 PolynomialList<C> pl = (PolynomialList<C>) p; 091 if (!ring.equals(pl.ring)) { 092 System.out.println("not same Ring " + ring.toScript() + ", " + pl.ring.toScript()); 093 return false; 094 } 095 return (compareTo(pl) == 0); 096 // otherwise tables may be different 097 } 098 099 100 /** 101 * Polynomial list comparison. 102 * @param L other PolynomialList. 103 * @return lexicographical comparison, sign of first different polynomials. 104 */ 105 public int compareTo(PolynomialList<C> L) { 106 int si = L.list.size(); 107 if (list.size() < si) { // minimum 108 si = list.size(); 109 } 110 int s = 0; 111 List<GenPolynomial<C>> l1 = OrderedPolynomialList.<C> sort(ring, list); 112 List<GenPolynomial<C>> l2 = OrderedPolynomialList.<C> sort(ring, L.list); 113 for (int i = 0; i < si; i++) { 114 GenPolynomial<C> a = l1.get(i); 115 GenPolynomial<C> b = l2.get(i); 116 s = a.compareTo(b); 117 if (s != 0) { 118 return s; 119 } 120 } 121 if (list.size() > si) { 122 return 1; 123 } 124 if (L.list.size() > si) { 125 return -1; 126 } 127 return s; 128 } 129 130 131 /** 132 * Hash code for this polynomial list. 133 * @see java.lang.Object#hashCode() 134 */ 135 @Override 136 public int hashCode() { 137 int h; 138 h = ring.hashCode(); 139 h = 37 * h + (list == null ? 0 : list.hashCode()); 140 return h; 141 } 142 143 144 /** 145 * Test if list is empty. 146 * @return true if this is empty, else false. 147 */ 148 public boolean isEmpty() { 149 if (list == null) { 150 return true; 151 } 152 return list.isEmpty(); 153 } 154 155 156 /** 157 * String representation of the polynomial list. 158 * @see java.lang.Object#toString() 159 */ 160 @Override 161 public String toString() { 162 StringBuffer erg = new StringBuffer(); 163 String[] vars = null; 164 if (ring != null) { 165 erg.append(ring.toString()); 166 vars = ring.getVars(); 167 } 168 boolean first = true; 169 erg.append("\n(\n"); 170 String sa = null; 171 for (GenPolynomial<C> oa : list) { 172 if (vars != null) { 173 sa = oa.toString(vars); 174 } else { 175 sa = oa.toString(); 176 } 177 if (first) { 178 first = false; 179 } else { 180 erg.append(", "); 181 if (sa.length() > 10) { 182 erg.append("\n"); 183 } 184 } 185 erg.append("( " + sa + " )"); 186 } 187 erg.append("\n)"); 188 return erg.toString(); 189 } 190 191 192 /** 193 * Get a scripting compatible string representation. 194 * @return script compatible representation for this polynomial list. 195 */ 196 public String toScript() { 197 StringBuffer s = new StringBuffer(); 198 if (ring instanceof GenSolvablePolynomialRing) { 199 switch (Scripting.getLang()) { 200 case Ruby: 201 s.append("SolvIdeal.new("); 202 break; 203 case Python: 204 default: 205 s.append("SolvableIdeal("); 206 } 207 } else { 208 switch (Scripting.getLang()) { 209 case Ruby: 210 s.append("SimIdeal.new("); 211 break; 212 case Python: 213 default: 214 s.append("Ideal("); 215 } 216 } 217 if (ring != null) { 218 s.append(ring.toScript()); 219 } 220 if (list == null) { 221 s.append(")"); 222 return s.toString(); 223 } 224 switch (Scripting.getLang()) { 225 case Ruby: 226 s.append(",\"\",["); 227 break; 228 case Python: 229 default: 230 s.append(",list=["); 231 } 232 boolean first = true; 233 String sa = null; 234 for (GenPolynomial<C> oa : list) { 235 sa = oa.toScript(); 236 if (first) { 237 first = false; 238 } else { 239 s.append(", "); 240 } 241 //s.append("( " + sa + " )"); 242 s.append(sa); 243 } 244 s.append("])"); 245 return s.toString(); 246 } 247 248 249 /** 250 * Get ModuleList from PolynomialList. Extract module from polynomial ring. 251 * @see edu.jas.poly.ModuleList 252 * @param i number of variables to be contract form the polynomials. 253 * @return module list corresponding to this. 254 */ 255 @SuppressWarnings("unchecked") 256 public ModuleList<C> getModuleList(int i) { 257 GenPolynomialRing<C> pfac = ring.contract(i); 258 logger.debug("contracted ring = {}", pfac); 259 //System.out.println("contracted ring = " + pfac); 260 261 List<List<GenPolynomial<C>>> vecs = null; 262 if (list == null) { 263 return new ModuleList<C>(pfac, vecs); 264 } 265 int rows = list.size(); 266 vecs = new ArrayList<List<GenPolynomial<C>>>(rows); 267 if (rows == 0) { // nothing to do 268 return new ModuleList<C>(pfac, vecs); 269 } 270 271 ArrayList<GenPolynomial<C>> zr = new ArrayList<GenPolynomial<C>>(i - 1); 272 GenPolynomial<C> zero = pfac.getZERO(); 273 for (int j = 0; j < i; j++) { 274 zr.add(j, zero); 275 } 276 277 for (GenPolynomial<C> p : list) { 278 if (p != null) { 279 Map<ExpVector, GenPolynomial<C>> r = p.contract(pfac); 280 //System.out.println("r = " + r ); 281 List<GenPolynomial<C>> row = new ArrayList<GenPolynomial<C>>(zr); //zr.clone(); 282 for (Map.Entry<ExpVector, GenPolynomial<C>> me : r.entrySet()) { 283 ExpVector e = me.getKey(); 284 int[] dov = e.dependencyOnVariables(); 285 int ix = 0; 286 if (dov.length > 1) { 287 throw new IllegalArgumentException("wrong dependencyOnVariables " + e); 288 } else if (dov.length == 1) { 289 ix = dov[0]; 290 } 291 //ix = i-1 - ix; // revert 292 //System.out.println("ix = " + ix ); 293 GenPolynomial<C> vi = me.getValue(); //r.get( e ); 294 row.set(ix, vi); 295 } 296 //System.out.println("row = " + row ); 297 vecs.add(row); 298 } 299 } 300 return new ModuleList<C>(pfac, vecs); 301 } 302 303 304 /** 305 * Get list. 306 * @return list from this. 307 */ 308 public List<GenPolynomial<C>> getList() { 309 return list; 310 } 311 312 313 /** 314 * Get list as List of GenSolvablePolynomials. Required because no List 315 * casts allowed. Equivalent to cast 316 * (List<GenSolvablePolynomial<C>>) list. 317 * @return solvable polynomial list from this. 318 */ 319 public List<GenSolvablePolynomial<C>> castToSolvableList() { 320 return castToSolvableList(list); 321 } 322 323 324 /** 325 * Get list as List of GenSolvablePolynomials. Required because no List 326 * casts allowed. Equivalent to cast 327 * (List<GenSolvablePolynomial<C>>) list. 328 * @return solvable polynomial list from this. 329 */ 330 public List<GenSolvablePolynomial<C>> getSolvableList() { 331 return castToSolvableList(list); 332 } 333 334 335 /** 336 * Get ring as GenSolvablePolynomialRing. 337 * @return solvable polynomial ring list from this. 338 */ 339 public GenSolvablePolynomialRing<C> getSolvableRing() { 340 return (GenSolvablePolynomialRing<C>) ring; 341 } 342 343 344 /** 345 * Get list as List of GenSolvablePolynomials. Required because no List 346 * casts allowed. Equivalent to cast 347 * (List<GenSolvablePolynomial<C>>) list. 348 * @param list list of extensions of polynomials. 349 * @return solvable polynomial list from this. 350 */ 351 public static <C extends RingElem<C>> List<GenSolvablePolynomial<C>> castToSolvableList( 352 List<GenPolynomial<C>> list) { 353 List<GenSolvablePolynomial<C>> slist = null; 354 if (list == null) { 355 return slist; 356 } 357 slist = new ArrayList<GenSolvablePolynomial<C>>(list.size()); 358 GenSolvablePolynomial<C> s; 359 for (GenPolynomial<C> p : list) { 360 if (p == null) { 361 s = null; 362 } else { 363 if (!(p instanceof GenSolvablePolynomial)) { 364 throw new IllegalArgumentException("no solvable polynomial " + p); 365 } 366 s = (GenSolvablePolynomial<C>) p; 367 } 368 slist.add(s); 369 } 370 return slist; 371 } 372 373 374 /** 375 * Get list of list as List of List of GenSolvablePolynomials. Required 376 * because no List casts allowed. Equivalent to cast 377 * (List<GenSolvablePolynomial<C>>) list. 378 * @param list list of extensions of polynomials. 379 * @return solvable polynomial list from this. 380 */ 381 public static <C extends RingElem<C>> List<List<GenSolvablePolynomial<C>>> castToSolvableMatrix( 382 List<List<GenPolynomial<C>>> list) { 383 List<List<GenSolvablePolynomial<C>>> slist = null; 384 if (list == null) { 385 return slist; 386 } 387 slist = new ArrayList<List<GenSolvablePolynomial<C>>>(list.size()); 388 List<GenSolvablePolynomial<C>> s; 389 for (List<GenPolynomial<C>> p : list) { 390 s = PolynomialList.<C> castToSolvableList(p); 391 slist.add(s); 392 } 393 return slist; 394 } 395 396 397 /** 398 * Get list of extensions of polynomials as List of GenPolynomials. Required 399 * because no List casts allowed. Equivalent to cast 400 * (List<GenPolynomial<C>>) list. Mainly used for lists of 401 * GenSolvablePolynomials. 402 * @param slist list of extensions of polynomials. 403 * @return polynomial list from slist. 404 */ 405 public static <C extends RingElem<C>> List<GenPolynomial<C>> castToList( 406 List<? extends GenPolynomial<C>> slist) { 407 logger.debug("warn: can lead to wrong method dispatch"); 408 List<GenPolynomial<C>> list = null; 409 if (slist == null) { 410 return list; 411 } 412 list = new ArrayList<GenPolynomial<C>>(slist.size()); 413 for (GenPolynomial<C> p : slist) { 414 list.add(p); 415 } 416 return list; 417 } 418 419 420 /** 421 * Get list of list of extensions of polynomials as List of List of 422 * GenPolynomials. Required because no List casts allowed. Equivalent to 423 * cast (List<GenPolynomial<C>>) list. Mainly used for lists of 424 * GenSolvablePolynomials. 425 * @param slist list of extensions of polynomials. 426 * @return polynomial list from slist. 427 */ 428 public static <C extends RingElem<C>> List<List<GenPolynomial<C>>> castToMatrix( 429 List<List<? extends GenPolynomial<C>>> slist) { 430 logger.debug("warn: can lead to wrong method dispatch"); 431 List<List<GenPolynomial<C>>> list = null; 432 if (slist == null) { 433 return list; 434 } 435 list = new ArrayList<List<GenPolynomial<C>>>(slist.size()); 436 for (List<? extends GenPolynomial<C>> p : slist) { 437 list.add(PolynomialList.<C> castToList(p)); 438 } 439 return list; 440 } 441 442 443 /** 444 * Test if list contains only ZEROs. 445 * @return true, if this is the 0 list, else false 446 */ 447 public boolean isZERO() { 448 if (list == null) { 449 return true; 450 } 451 for (GenPolynomial<C> p : list) { 452 if (p == null) { 453 continue; 454 } 455 if (!p.isZERO()) { 456 return false; 457 } 458 } 459 return true; 460 } 461 462 463 /** 464 * Test if list contains a ONE. 465 * @return true, if this contains 1, else false 466 */ 467 public boolean isONE() { 468 if (list == null) { 469 return false; 470 } 471 for (GenPolynomial<C> p : list) { 472 if (p == null) { 473 continue; 474 } 475 if (p.isONE()) { 476 return true; 477 } 478 } 479 return false; 480 } 481 482 483 /** 484 * Make homogeneous. 485 * @return polynomial list of homogeneous polynomials. 486 */ 487 public PolynomialList<C> homogenize() { 488 GenPolynomialRing<C> pfac = ring.extend(1); 489 List<GenPolynomial<C>> hom = new ArrayList<GenPolynomial<C>>(list.size()); 490 for (GenPolynomial<C> p : list) { 491 GenPolynomial<C> h = p.homogenize(pfac); 492 hom.add(h); 493 } 494 return new PolynomialList<C>(pfac, hom); 495 } 496 497 498 /** 499 * Dehomogenize. 500 * @return polynomial list of de-homogenized polynomials. 501 */ 502 public PolynomialList<C> deHomogenize() { 503 GenPolynomialRing<C> pfac = ring.contract(1); 504 List<GenPolynomial<C>> dehom = new ArrayList<GenPolynomial<C>>(list.size()); 505 for (GenPolynomial<C> p : list) { 506 GenPolynomial<C> h = p.deHomogenize(pfac); 507 dehom.add(h); 508 } 509 return new PolynomialList<C>(pfac, dehom); 510 } 511 512 513 /** 514 * Test if all polynomials are homogeneous. 515 * @return true, if all polynomials are homogeneous, else false 516 */ 517 public boolean isHomogeneous() { 518 if (list == null) { 519 return true; 520 } 521 for (GenPolynomial<C> p : list) { 522 if (p == null) { 523 continue; 524 } 525 if (!p.isHomogeneous()) { 526 return false; 527 } 528 } 529 return true; 530 } 531 532 533 /** 534 * Union of the delta of exponent vectors of all polynomials. 535 * @return list of u-v, where u = lt() and v != u in p in list. 536 */ 537 public SortedSet<ExpVector> deltaExpVectors() { 538 SortedSet<ExpVector> de = new TreeSet<ExpVector>(ring.tord.getAscendComparator()); 539 if (list.isEmpty()) { 540 return de; 541 } 542 for (GenPolynomial<C> p : list) { 543 List<ExpVector> pe = p.deltaExpVectors(); 544 de.addAll(pe); 545 } 546 return de; 547 } 548 549 550 /** 551 * Union of the delta of exponent vectors of all polynomials. 552 * @param mark list of marked exp vectors of polynomials. 553 * @return list of u-v, where u in mark and v != u in p.expVectors in list. 554 */ 555 public SortedSet<ExpVector> deltaExpVectors(List<ExpVector> mark) { 556 SortedSet<ExpVector> de = new TreeSet<ExpVector>(ring.tord.getAscendComparator()); 557 if (list.isEmpty()) { 558 return de; 559 } 560 if (mark.isEmpty()) { 561 return deltaExpVectors(); 562 } 563 if (list.size() != mark.size()) { 564 throw new IllegalArgumentException("#list != #mark"); 565 } 566 int i = 0; 567 for (GenPolynomial<C> p : list) { 568 ExpVector u = mark.get(i); 569 List<ExpVector> pe = p.deltaExpVectors(u); 570 de.addAll(pe); 571 i++; 572 } 573 return de; 574 } 575 576 577 /** 578 * Leading weight polynomials. 579 * @return list of polynomials with terms of maximal weight degree. 580 */ 581 public List<GenPolynomial<C>> leadingWeightPolynomials() { 582 List<GenPolynomial<C>> lw = new ArrayList<GenPolynomial<C>>(list.size()); 583 if (list.isEmpty()) { 584 return lw; 585 } 586 for (GenPolynomial<C> p : list) { 587 GenPolynomial<C> pw = p.leadingWeightPolynomial(); 588 lw.add(pw); 589 } 590 return lw; 591 } 592 593}