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