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