Source code

001/*
002 * $Id: ColorPolynomial.java 5122 2015-02-17 08:35:15Z kredel $
003 */
004
005package edu.jas.application;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.Collection;
011import java.util.Comparator;
012import java.util.List;
013import java.util.Map;
014
015import org.apache.log4j.Logger;
016
017import edu.jas.poly.ExpVector;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenSolvablePolynomial;
020import edu.jas.structure.RingElem;
021
022
023/**
024 * Colored Polynomials with green, red and white coefficients. Not implementing
025 * RingElem. <b>Note:</b> not general purpose, use only in comprehensive GB.
026 * @param <C> coefficient type
027 * @author Heinz Kredel
028 */
029
030public class ColorPolynomial<C extends RingElem<C>> implements Serializable
031    /* implements RingElem< ColorPolynomial<C> > */ {
032
033
034    private static final Logger logger = Logger.getLogger(ColorPolynomial.class);
035
036
037    /**
038     * The part with green (= zero) terms and coefficients.
039     */
040    public final GenPolynomial<GenPolynomial<C>> green;
041
042
043    /**
044     * The part with red (= non zero) terms and coefficients.
045     */
046    public final GenPolynomial<GenPolynomial<C>> red;
047
048
049    /**
050     * The part with white (= unknown color) terms and coefficients.
051     */
052    public final GenPolynomial<GenPolynomial<C>> white;
053
054
055    /**
056     * The constructor creates a colored polynomial from the colored parts.
057     * @param g green colored terms and coefficients.
058     * @param r red colored terms and coefficients.
059     * @param w white colored terms and coefficients.
060     */
061    public ColorPolynomial(GenPolynomial<GenPolynomial<C>> g,
062            GenPolynomial<GenPolynomial<C>> r, GenPolynomial<GenPolynomial<C>> w) {
063        if (g == null || r == null || w == null) {
064            throw new IllegalArgumentException("g,r,w may not be null");
065        }
066        green = g;
067        red = r;
068        white = w;
069    }
070
071
072    /**
073     * String representation of ColorPolynomial.
074     * @see java.lang.Object#toString()
075     */
076    @Override
077    public String toString() {
078        StringBuffer s = new StringBuffer();
079        s.append(":green: ");
080        s.append(green.toString());
081        s.append(" :red: ");
082        s.append(red.toString());
083        s.append(" :white: ");
084        s.append(white.toString());
085        return s.toString();
086    }
087
088
089    /**
090     * Script representation of ColorPolynomial.
091     * @see edu.jas.structure.Element#toScript()
092     */
093    public String toScript() {
094        StringBuffer s = new StringBuffer();
095        s.append(":green: ");
096        s.append(green.toScript());
097        s.append(" :red: ");
098        s.append(red.toScript());
099        s.append(" :white: ");
100        s.append(white.toScript());
101        return s.toString();
102    }
103
104
105    /**
106     * Is this polynomial ZERO.
107     * @return true, if there are only green terms, else false.
108     */
109    public boolean isZERO() {
110        return (red.isZERO() && white.isZERO());
111    }
112
113
114    /**
115     * Is this polynomial ONE.
116     * @return true, if the only non green term is 1, else false.
117     */
118    public boolean isONE() {
119        return ((red.isZERO() && white.isONE()) || (red.isONE() && white.isZERO()));
120    }
121
122
123    /**
124     * Is this polynomial equal to other.
125     * @param p other polynomial.
126     * @return true, if this is equal to other, else false.
127     */
128    @Override
129    @SuppressWarnings("unchecked")
130    public boolean equals(Object p) {
131        ColorPolynomial<C> cp = null;
132        try {
133            cp = (ColorPolynomial<C>) p;
134        } catch (ClassCastException e) {
135            return false;
136        }
137        if (cp == null) {
138            return false;
139        }
140        return (green.equals(cp.green) && red.equals(cp.red) && white.equals(cp.white));
141    }
142
143
144    /**
145     * Hash code for this colored polynomial.
146     * @see java.lang.Object#hashCode()
147     */
148    @Override
149    public int hashCode() {
150        int h;
151        h = green.hashCode();
152        h = h << 11;
153        h += red.hashCode();
154        h = h << 11;
155        h += white.hashCode();
156        return h;
157    }
158
159
160    /**
161     * Is this polynomial determined.
162     * @return true, if there are nonzero red terms or if this == 0, else false.
163     */
164    public boolean isDetermined() {
165        return (!red.isZERO() || white.isZERO());
166    }
167
168
169    /**
170     * Check ordering invariants. TT(green) > LT(red) and TT(red) > LT(white).
171     * @return true, if all ordering invariants are met, else false.
172     */
173    public boolean checkInvariant() {
174        boolean t = true;
175        ExpVector ttg, ltr, ttr, ltw;
176        Comparator<ExpVector> cmp;
177        if (green.isZERO() && red.isZERO() && white.isZERO()) {
178            return true;
179        }
180        if (green.isZERO() && red.isZERO()) {
181            return true;
182        }
183        if (red.isZERO() && white.isZERO()) {
184            return true;
185        }
186
187        if (!green.isZERO() && !red.isZERO()) {
188            ttg = green.trailingExpVector();
189            ltr = red.leadingExpVector();
190            cmp = green.ring.tord.getDescendComparator();
191            t = t && (cmp.compare(ttg, ltr) < 0);
192        }
193        if (!red.isZERO() && !white.isZERO()) {
194            ttr = red.trailingExpVector();
195            ltw = white.leadingExpVector();
196            cmp = white.ring.tord.getDescendComparator();
197            t = t && (cmp.compare(ttr, ltw) < 0);
198        }
199        if (red.isZERO() && !green.isZERO() && !white.isZERO()) {
200            ttg = green.trailingExpVector();
201            ltw = white.leadingExpVector();
202            cmp = white.ring.tord.getDescendComparator();
203            t = t && (cmp.compare(ttg, ltw) < 0);
204        }
205        if (!t) {
206            System.out.println("not invariant " + this);
207            // throw new RuntimeException("test");
208        }
209        return t;
210    }
211
212
213    /**
214     * Get zero condition on coefficients.
215     * @return green coefficients.
216     */
217    public List<GenPolynomial<C>> getGreenCoefficients() {
218        Collection<GenPolynomial<C>> c = green.getMap().values();
219        return new ArrayList<GenPolynomial<C>>(c);
220    }
221
222
223    /**
224     * Get non zero condition on coefficients.
225     * @return red coefficients.
226     */
227    public List<GenPolynomial<C>> getRedCoefficients() {
228        Collection<GenPolynomial<C>> c = red.getMap().values();
229        return new ArrayList<GenPolynomial<C>>(c);
230    }
231
232
233    /**
234     * Get full polynomial.
235     * @return sum of all parts.
236     */
237    public GenPolynomial<GenPolynomial<C>> getPolynomial() {
238        GenPolynomial<GenPolynomial<C>> f = green.sum(red).sum(white);
239        int s = green.length() + red.length() + white.length();
240        int t = f.length();
241        if (t != s) {
242            throw new RuntimeException("illegal coloring state " + s + " != " + t);
243        }
244        return f;
245    }
246
247
248    /**
249     * Get essential polynomial.
250     * @return sum of red and white parts.
251     */
252    public GenPolynomial<GenPolynomial<C>> getEssentialPolynomial() {
253        GenPolynomial<GenPolynomial<C>> f = red.sum(white);
254        int s = red.length() + white.length();
255        int t = f.length();
256        if (t != s) {
257            logger.warn("illegal coloring state " + s + " != " + t);
258            logger.info("f = " + f + ", red = " + red + ", white = " + white);
259            //throw new RuntimeException("illegal coloring state " + s + " != " + t);
260        }
261        return f;
262    }
263
264
265    /**
266     * Length of red and white parts.
267     * @return length of essential parts.
268     */
269    public int length() {
270        int s = red.length() + white.length();
271        return s;
272    }
273
274
275    /**
276     * Get leading exponent vector.
277     * @return LT of red or white parts.
278     */
279    public ExpVector leadingExpVector() {
280        if (!red.isZERO()) {
281            return red.leadingExpVector();
282        }
283        return white.leadingExpVector();
284    }
285
286
287    /**
288     * Get leading monomial.
289     * @return LM of red or white parts.
290     */
291    public Map.Entry<ExpVector, GenPolynomial<C>> leadingMonomial() {
292        if (!red.isZERO()) {
293            return red.leadingMonomial();
294        }
295        return white.leadingMonomial();
296    }
297
298
299    /**
300     * ColorPolynomial absolute value.
301     * @return abs(this).
302     */
303    public ColorPolynomial<C> abs() {
304        GenPolynomial<GenPolynomial<C>> g, r, w;
305        int s = green.signum();
306        if (s > 0) {
307            return this;
308        }
309        if (s < 0) {
310            g = green.negate();
311            r = red.negate();
312            w = white.negate();
313            return new ColorPolynomial<C>(g, r, w);
314        }
315        // green == 0
316        g = green;
317        s = red.signum();
318        if (s > 0) {
319            return this;
320        }
321        if (s < 0) {
322            r = red.negate();
323            w = white.negate();
324            return new ColorPolynomial<C>(g, r, w);
325        }
326        // red == 0
327        r = red;
328        s = white.signum();
329        if (s > 0) {
330            return this;
331        }
332        if (s < 0) {
333            w = white.negate();
334            return new ColorPolynomial<C>(g, r, w);
335        }
336        // white == 0
337        w = white;
338        return new ColorPolynomial<C>(g, r, w);
339    }
340
341
342    /**
343     * ColorPolynomial summation. <b>Note:</b> green coefficients stay green,
344     * all others become white.
345     * @param S ColorPolynomial.
346     * @return this+S.
347     */
348    public ColorPolynomial<C> sum(ColorPolynomial<C> S) {
349        GenPolynomial<GenPolynomial<C>> g, r, w;
350        g = green.sum(S.green);
351        r = red.ring.getZERO();
352        w = getEssentialPolynomial().sum(S.getEssentialPolynomial());
353        return new ColorPolynomial<C>(g, r, w);
354    }
355
356
357    /**
358     * ColorPolynomial summation.
359     * @param s GenPolynomial.
360     * @param e exponent vector.
361     * @return this+(c e).
362     */
363    public ColorPolynomial<C> sum(GenPolynomial<C> s, ExpVector e) {
364        GenPolynomial<GenPolynomial<C>> g, r, w;
365        g = green;
366        r = red;
367        w = white;
368        if (green.getMap().keySet().contains(e)) {
369            g = green.sum(s, e);
370        } else if (red.getMap().keySet().contains(e)) {
371            r = red.sum(s, e);
372        } else {
373            w = white.sum(s, e);
374        }
375        return new ColorPolynomial<C>(g, r, w);
376    }
377
378
379    /**
380     * ColorPolynomial subtraction. <b>Note:</b> green coefficients stay green,
381     * all others become white.
382     * @param S ColorPolynomial.
383     * @return this-S.
384     */
385    public ColorPolynomial<C> subtract(ColorPolynomial<C> S) {
386        GenPolynomial<GenPolynomial<C>> g, r, w;
387        g = green.subtract(S.green);
388        r = red.ring.getZERO();
389        w = getEssentialPolynomial().subtract(S.getEssentialPolynomial());
390        return new ColorPolynomial<C>(g, r, w);
391    }
392
393
394    /**
395     * ColorPolynomial subtract.
396     * @param s GenPolynomial.
397     * @param e exponent vector.
398     * @return this-(c e).
399     */
400    public ColorPolynomial<C> subtract(GenPolynomial<C> s, ExpVector e) {
401        GenPolynomial<GenPolynomial<C>> g, r, w;
402        g = green;
403        r = red;
404        w = white;
405        if (green.getMap().keySet().contains(e)) {
406            g = green.subtract(s, e);
407        } else if (red.getMap().keySet().contains(e)) {
408            r = red.subtract(s, e);
409        } else {
410            w = white.subtract(s, e);
411        }
412        return new ColorPolynomial<C>(g, r, w);
413    }
414
415
416    /**
417     * ColorPolynomial multiplication by monomial.
418     * @param s Coefficient.
419     * @param e Expvector.
420     * @return this * (c t).
421     */
422    public ColorPolynomial<C> multiply(GenPolynomial<C> s, ExpVector e) {
423        GenPolynomial<GenPolynomial<C>> g, r, w;
424        if (green instanceof GenSolvablePolynomial) {
425            logger.info("use left multiplication");
426            GenSolvablePolynomial<GenPolynomial<C>> gs, rs, ws;
427            gs = (GenSolvablePolynomial<GenPolynomial<C>>) green;
428            rs = (GenSolvablePolynomial<GenPolynomial<C>>) red;
429            ws = (GenSolvablePolynomial<GenPolynomial<C>>) white;
430            g = gs.multiplyLeft(s, e);
431            r = rs.multiplyLeft(s, e);
432            w = ws.multiplyLeft(s, e);
433        } else {
434            g = green.multiply(s, e);
435            r = red.multiply(s, e);
436            w = white.multiply(s, e);
437        }
438        return new ColorPolynomial<C>(g, r, w);
439    }
440
441
442    /**
443     * ColorPolynomial multiplication by coefficient.
444     * @param s Coefficient.
445     * @return this * (s).
446     */
447    public ColorPolynomial<C> multiply(GenPolynomial<C> s) {
448        GenPolynomial<GenPolynomial<C>> g, r, w;
449        // coefficients commute
450        g = green.multiply(s);
451        r = red.multiply(s);
452        w = white.multiply(s);
453        return new ColorPolynomial<C>(g, r, w);
454    }
455
456
457    /**
458     * ColorPolynomial division by coefficient.
459     * @param s Coefficient.
460     * @return this / (s).
461     */
462    public ColorPolynomial<C> divide(GenPolynomial<C> s) {
463        GenPolynomial<GenPolynomial<C>> g, r, w;
464        g = green.divide(s);
465        r = red.divide(s);
466        w = white.divide(s);
467        return new ColorPolynomial<C>(g, r, w);
468    }
469
470
471}