Source code

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