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