001/* 002 * $Id: Condition.java 5120 2015-02-16 22:46:51Z kredel $ 003 */ 004 005package edu.jas.application; 006 007 008import java.io.Serializable; 009import java.util.ArrayList; 010import java.util.List; 011import java.util.Map; 012 013import org.apache.log4j.Logger; 014 015import edu.jas.gbufd.MultiplicativeSet; 016import edu.jas.gbufd.MultiplicativeSetSquarefree; 017//import edu.jas.gbufd.MultiplicativeSetFactors; 018import edu.jas.poly.ExpVector; 019import edu.jas.poly.GenPolynomial; 020import edu.jas.poly.GenPolynomialRing; 021import edu.jas.structure.GcdRingElem; 022 023 024/** 025 * Condition. Container for an ideal of polynomials considered to be zero and a 026 * multiplicative set of polynomials considered to be non-zero. 027 * @param <C> coefficient type 028 * @author Heinz Kredel. 029 */ 030public class Condition<C extends GcdRingElem<C>> implements Serializable { 031 032 033 private static final Logger logger = Logger.getLogger(Condition.class); 034 035 036 //private final boolean debug = logger.isDebugEnabled(); 037 038 039 /** 040 * Colors. 041 */ 042 public static enum Color { 043 GREEN, RED, WHITE 044 }; 045 046 047 /** 048 * Data structure for condition zero. 049 */ 050 public final Ideal<C> zero; 051 052 053 /** 054 * Data structure for condition non-zero. 055 */ 056 public final MultiplicativeSet<C> nonZero; 057 058 059 /** 060 * Condition constructor. Constructs an empty condition with squarefree 061 * multiplicative set. 062 * @param ring polynomial ring factory for coefficients. 063 */ 064 public Condition(GenPolynomialRing<C> ring) { 065 this(new Ideal<C>(ring), new MultiplicativeSetSquarefree<C>(ring)); 066 //this(new Ideal<C>(ring), new MultiplicativeSetFactors<C>(ring)); 067 //if (ring == null) { // too late to test 068 // throw new IllegalArgumentException("only for non null rings"); 069 //} 070 } 071 072 073 /** 074 * Condition constructor. Constructs a condition with squarefree 075 * multiplicative set. 076 * @param z an ideal of zero polynomials. 077 */ 078 public Condition(Ideal<C> z) { 079 this(z, new MultiplicativeSetSquarefree<C>(z.list.ring)); 080 //this(z,new MultiplicativeSetFactors<C>(z.list.ring)); 081 } 082 083 084 /** 085 * Condition constructor. 086 * @param nz a list of non-zero polynomials. 087 */ 088 public Condition(MultiplicativeSet<C> nz) { 089 this(new Ideal<C>(nz.ring), nz); 090 } 091 092 093 /** 094 * Condition constructor. 095 * @param z an ideal of zero polynomials. 096 * @param nz a list of non-zero polynomials. 097 */ 098 public Condition(Ideal<C> z, MultiplicativeSet<C> nz) { 099 if (z == null || nz == null) { 100 throw new IllegalArgumentException("only for non null condition parts"); 101 } 102 zero = z; 103 nonZero = nz; 104 } 105 106 107 /** 108 * toString. 109 * @see java.lang.Object#toString() 110 */ 111 @Override 112 public String toString() { 113 return "Condition[ 0 == " + zero.getList().toString() + ", 0 != " + nonZero.mset.toString() + " ]"; 114 } 115 116 117 /** 118 * toScript. 119 * @see edu.jas.structure.Element#toScript() 120 */ 121 public String toScript() { 122 return "Condition[ 0 == " + zero.getList().toString() + ", 0 != " + nonZero.mset.toString() + " ]"; 123 } 124 125 126 /** 127 * equals. 128 * @param ob an Object. 129 * @return true if this is equal to o, else false. 130 */ 131 @Override 132 @SuppressWarnings("unchecked") 133 public boolean equals(Object ob) { 134 Condition<C> c = null; 135 try { 136 c = (Condition<C>) ob; 137 } catch (ClassCastException e) { 138 return false; 139 } 140 if (c == null) { 141 return false; 142 } 143 if (!zero.equals(c.zero)) { 144 return false; 145 } 146 if (!nonZero.equals(c.nonZero)) { 147 return false; 148 } 149 // better: 150 //if ( nonZero.removeFactors(c.nonZero).size() != 0 ) { 151 // return false; 152 //} 153 //if ( c.nonZero.removeFactors(nonZero).size() != 0 ) { 154 // return false; 155 //} 156 return true; 157 } 158 159 160 /** 161 * Hash code for this condition. 162 * @see java.lang.Object#hashCode() 163 */ 164 @Override 165 public int hashCode() { 166 int h; 167 h = zero.getList().hashCode(); 168 h = h << 17; 169 h += nonZero.hashCode(); 170 // h = h << 11; 171 // h += pairlist.hashCode(); 172 return h; 173 } 174 175 176 /** 177 * Is empty condition. 178 * @return true if this is the empty condition, else false. 179 */ 180 public boolean isEmpty() { 181 return (zero.isZERO() && nonZero.isEmpty()); 182 } 183 184 185 /** 186 * Is contradictory. 187 * @return true if this condition is contradictory, else false. 188 */ 189 public boolean isContradictory() { 190 if (zero.isZERO()) { 191 return false; 192 } 193 boolean t = zero.isONE(); 194 if (t) { 195 logger.info("contradiction zero.isONE(): " + this); 196 return t; 197 } 198 for (GenPolynomial<C> p : zero.getList()) { 199 t = nonZero.contains(p); 200 if (t) { 201 logger.info("contradiction nonZero.contains(zero): " + this + ", pol = " + p); 202 return t; 203 } 204 } 205 for (GenPolynomial<C> p : nonZero.mset) { 206 t = zero.contains(p); 207 if (t) { 208 logger.info("contradiction zero.contains(nonZero): " + this + ", pol = " + p); 209 return t; 210 } 211 } 212 return false; 213 } 214 215 216 /** 217 * Extend condition with zero polynomial. 218 * @param z a polynomial to be treated as zero. 219 * @return new condition. 220 */ 221 public Condition<C> extendZero(GenPolynomial<C> z) { 222 // assert color(z) == white 223 z = z.monic(); 224 Ideal<C> idz = zero.sum(z); 225 logger.info("added to ideal: " + z); 226 227 Condition<C> nc = new Condition<C>(idz, nonZero); 228 //if (true) { 229 return nc.simplify(); 230 //} 231 //return nc; 232 } 233 234 235 /** 236 * Extend condition with non-zero polynomial. 237 * @param nz a polynomial to be treated as non-zero. 238 * @return new condition. 239 */ 240 public Condition<C> extendNonZero(GenPolynomial<C> nz) { 241 // assert color(nz) == white 242 GenPolynomial<C> n = zero.normalform(nz).monic(); 243 if (n == null || n.isZERO()) { 244 return this; 245 } 246 MultiplicativeSet<C> ms = nonZero.add(n); 247 logger.info("added to non zero: " + n); 248 249 Condition<C> nc = new Condition<C>(zero, ms); 250 //if (true) { 251 return nc.simplify(); 252 //} 253 //return nc; 254 } 255 256 257 /** 258 * Simplify zero and non-zero polynomial conditions. 259 * @return new simplified condition. 260 */ 261 public Condition<C> simplify() { 262 //if (false) { // no simplification 263 // return this; 264 //} 265 Ideal<C> idz = zero.squarefree(); 266 if (!idz.getList().equals(zero.getList())) { 267 logger.info("simplify squarefree: " + zero.getList() + " to " + idz.getList()); 268 } 269 List<GenPolynomial<C>> ml = idz.normalform(nonZero.mset); 270 MultiplicativeSet<C> ms = nonZero; 271 if (!ml.equals(nonZero.mset)) { 272 if (ml.size() != nonZero.mset.size()) { 273 logger.info("contradiction(==0):"); 274 logger.info("simplify normalform contradiction: " + nonZero.mset + " to " + ml); 275 return null; 276 } 277 logger.info("simplify normalform: " + nonZero.mset + " to " + ml); 278 ms = nonZero.replace(ml); 279 } 280 List<GenPolynomial<C>> Z = ms.removeFactors(idz.getList()); 281 if (!Z.equals(idz.getList())) { 282 if (Z.size() != idz.getList().size()) { // never true 283 logger.info("contradiction(!=0):"); 284 logger.info("simplify removeFactors contradiction: " + idz.getList() + " to " + Z); 285 return null; 286 } 287 logger.info("simplify removeFactors: " + idz.getList() + " to " + Z); 288 idz = new Ideal<C>(zero.getRing(), Z); // changes ideal 289 } 290 Condition<C> nc = new Condition<C>(idz, ms); 291 if (nc.isContradictory()) { // eventually a factor became 1 292 logger.info("simplify contradiction: " + nc); 293 return null; 294 } 295 if (idz.equals(zero) && ms.equals(nonZero)) { 296 return this; 297 } 298 logger.info("condition simplified: " + this + " to " + nc); 299 //if (false) { // no further simplification 300 // return nc; 301 //} 302 return nc.simplify(); 303 } 304 305 306 /** 307 * Determine color of polynomial. 308 * @param c polynomial to be colored. 309 * @return color of c. 310 */ 311 public Color color(GenPolynomial<C> c) { 312 GenPolynomial<C> m = zero.normalform(c).monic(); 313 //non-sense: m = nonZero.removeFactors(m); 314 if (m.isZERO()) { // zero.contains(m) 315 // System.out.println("m in id = " + m); 316 return Color.GREEN; 317 } 318 if (m.isConstant()) { 319 // System.out.println("m constant " + m); 320 return Color.RED; 321 } 322 if (nonZero.contains(m) || nonZero.contains(c)) { 323 // System.out.println("m or c in nonzero " + m); 324 return Color.RED; 325 } 326 //System.out.println("m white " + m + ", c = " + c); 327 return Color.WHITE; 328 } 329 330 331 /** 332 * Determine polynomial. If this condition does not determine the 333 * polynomial, then a run-time exception is thrown. 334 * @param A polynomial. 335 * @return new determined colored polynomial. 336 */ 337 public ColorPolynomial<C> determine(GenPolynomial<GenPolynomial<C>> A) { 338 ColorPolynomial<C> cp = null; 339 if (A == null) { 340 return cp; 341 } 342 GenPolynomial<GenPolynomial<C>> zero = A.ring.getZERO(); 343 GenPolynomial<GenPolynomial<C>> green = zero; 344 GenPolynomial<GenPolynomial<C>> red = zero; 345 GenPolynomial<GenPolynomial<C>> white = zero; 346 if (A.isZERO()) { 347 cp = new ColorPolynomial<C>(green, red, white); 348 return cp; 349 } 350 GenPolynomial<GenPolynomial<C>> Ap = A; 351 GenPolynomial<GenPolynomial<C>> Bp; 352 while (!Ap.isZERO()) { 353 Map.Entry<ExpVector, GenPolynomial<C>> m = Ap.leadingMonomial(); 354 ExpVector e = m.getKey(); 355 GenPolynomial<C> c = m.getValue(); 356 Bp = Ap.reductum(); 357 // System.out.println( "color(" + c + ") = " + color(c) ); 358 switch (color(c)) { 359 case GREEN: 360 green = green.sum(c, e); 361 Ap = Bp; 362 continue; 363 case RED: 364 red = red.sum(c, e); 365 white = Bp; 366 return new ColorPolynomial<C>(green, red, white); 367 // since break is not possible 368 case WHITE: 369 default: 370 logger.info("recheck undetermined coeff c = " + c + ", cond = " + this); 371 if (extendZero(c) == null) { // contradiction if colored green 372 logger.info("recheck assume red"); 373 red = red.sum(c, e); // assume red 374 white = Bp; 375 return new ColorPolynomial<C>(green, red, white); 376 } 377 if (extendNonZero(c) == null) { // contradiction if colored red 378 logger.info("recheck assume green"); 379 green = green.sum(c, e); // assume green 380 Ap = Bp; 381 continue; 382 } 383 System.out.println("undetermined cond = " + this); 384 System.out.println("undetermined poly A = " + A); 385 System.out.println("undetermined poly green = " + green); 386 System.out.println("undetermined poly red = " + red); 387 System.out.println("undetermined poly Bp = " + Bp); 388 System.out.println("undetermined coeff c = " + c); 389 throw new RuntimeException("undetermined, c is white = " + c); 390 // is catched in minimalGB 391 } 392 } 393 cp = new ColorPolynomial<C>(green, red, white); 394 // System.out.println("determined = " + cp); 395 return cp; 396 } 397 398 399 /** 400 * Determine list of polynomials. If this condition does not determine all 401 * polynomials, then a run-time exception is thrown. The returned list does 402 * not contain polynomials with all green terms. 403 * @param L list of polynomial. 404 * @return new determined list of colored polynomials. 405 */ 406 public List<ColorPolynomial<C>> determine(List<GenPolynomial<GenPolynomial<C>>> L) { 407 List<ColorPolynomial<C>> cl = null; 408 if (L == null) { 409 return cl; 410 } 411 cl = new ArrayList<ColorPolynomial<C>>(L.size()); 412 for (GenPolynomial<GenPolynomial<C>> A : L) { 413 ColorPolynomial<C> c = determine(A); 414 if (c != null && !c.isZERO()) { 415 cl.add(c); 416 } 417 } 418 return cl; 419 } 420 421 422 /** 423 * Re determine colored polynomial. 424 * @param s colored polynomial. 425 * @return determined colored polynomial wrt. this.conditions. 426 */ 427 public ColorPolynomial<C> reDetermine(ColorPolynomial<C> s) { 428 ColorPolynomial<C> p = determine(s.getEssentialPolynomial()); 429 // assume green terms stay green wrt. this condition 430 GenPolynomial<GenPolynomial<C>> g = s.green.sum(p.green); 431 p = new ColorPolynomial<C>(g, p.red, p.white); 432 return p; 433 } 434 435 436 /** 437 * Re determine list of colored polynomials. 438 * @param S list of colored polynomials. 439 * @return list of determined colored polynomials wrt. this.conditions. 440 */ 441 public List<ColorPolynomial<C>> reDetermine(List<ColorPolynomial<C>> S) { 442 if (S == null || S.isEmpty()) { 443 return S; 444 } 445 List<ColorPolynomial<C>> P = new ArrayList<ColorPolynomial<C>>(); 446 for (ColorPolynomial<C> s : S) { 447 ColorPolynomial<C> p = reDetermine(s); 448 P.add(p); 449 } 450 return P; 451 } 452 453 454 /** 455 * Is determined colored polynomial. 456 * @param s colored polynomial. 457 * @return true if the colored polynomial is correctly determined wrt. 458 * this.condition. 459 */ 460 public boolean isDetermined(ColorPolynomial<C> s) { 461 ColorPolynomial<C> p = determine(s.getPolynomial()); 462 boolean t = p.equals(s); 463 if (!t) { 464 System.out.println("not determined s = " + s); 465 System.out.println("not determined p = " + p); 466 System.out.println("not determined cond = " + this); 467 } 468 return t; 469 } 470 471 472 /** 473 * Is determined list of colored polynomial. 474 * @param S list of colored polynomials. 475 * @return true if the colored polynomials in S are correctly determined 476 * wrt. this.condition. 477 */ 478 public boolean isDetermined(List<ColorPolynomial<C>> S) { 479 if (S == null) { 480 return true; 481 } 482 for (ColorPolynomial<C> p : S) { 483 if (!isDetermined(p)) { 484 return false; 485 } 486 } 487 return true; 488 } 489 490}