Source code

001/*
002 * $Id: Condition.java 4058 2012-07-26 21:03:53Z 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;
017import edu.jas.poly.ExpVector;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import 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 */
029public 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("undetermined cond       = " + this);
360                System.out.println("undetermined poly     A = " + A);
361                System.out.println("undetermined poly green = " + green);
362                System.out.println("undetermined poly   red = " + red);
363                System.out.println("undetermined poly    Ap = " + Ap);
364                System.out.println("undetermined coeff    c = " + c);
365                throw new RuntimeException("undetermined, 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}