001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.List;
011import java.util.Map;
012import java.util.SortedSet;
013import java.util.TreeSet;
014
015import org.apache.logging.log4j.Logger;
016import org.apache.logging.log4j.LogManager; 
017
018import edu.jas.kern.Scripting;
019import edu.jas.structure.RingElem;
020
021
022/**
023 * List of polynomials. Mainly for storage and printing / toString and
024 * conversions to other representations.
025 * @author Heinz Kredel
026 */
027
028public class PolynomialList<C extends RingElem<C>> implements Comparable<PolynomialList<C>>, Serializable {
029
030
031    /**
032     * The factory for the solvable polynomial ring.
033     */
034    public final GenPolynomialRing<C> ring;
035
036
037    /**
038     * The data structure is a List of polynomials.
039     */
040    public final List<GenPolynomial<C>> list;
041
042
043    private static final Logger logger = LogManager.getLogger(PolynomialList.class);
044
045
046    /**
047     * Constructor.
048     * @param r polynomial ring factory.
049     * @param l list of polynomials.
050     */
051    public PolynomialList(GenPolynomialRing<C> r, List<GenPolynomial<C>> l) {
052        ring = r;
053        list = l;
054    }
055
056
057    /**
058     * Constructor.
059     * @param r solvable polynomial ring factory.
060     * @param l list of solvable polynomials.
061     */
062    public PolynomialList(GenSolvablePolynomialRing<C> r, List<GenSolvablePolynomial<C>> l) {
063        this(r, PolynomialList.<C> castToList(l));
064    }
065
066
067    /**
068     * Copy this.
069     * @return a copy of this.
070     */
071    public PolynomialList<C> copy() {
072        return new PolynomialList<C>(ring, new ArrayList<GenPolynomial<C>>(list));
073    }
074
075
076    /**
077     * Comparison with any other object.
078     * @see java.lang.Object#equals(java.lang.Object)
079     */
080    @Override
081    @SuppressWarnings("unchecked")
082    public boolean equals(Object p) {
083        if (p == null) {
084            return false;
085        }
086        if (!(p instanceof PolynomialList)) {
087            System.out.println("no PolynomialList");
088            return false;
089        }
090        PolynomialList<C> pl = (PolynomialList<C>) p;
091        if (!ring.equals(pl.ring)) {
092            System.out.println("not same Ring " + ring.toScript() + ", " + pl.ring.toScript());
093            return false;
094        }
095        return (compareTo(pl) == 0);
096        // otherwise tables may be different
097    }
098
099
100    /**
101     * Polynomial list comparison.
102     * @param L other PolynomialList.
103     * @return lexicographical comparison, sign of first different polynomials.
104     */
105    public int compareTo(PolynomialList<C> L) {
106        int si = L.list.size();
107        if (list.size() < si) { // minimum
108            si = list.size();
109        }
110        int s = 0;
111        List<GenPolynomial<C>> l1 = OrderedPolynomialList.<C> sort(ring, list);
112        List<GenPolynomial<C>> l2 = OrderedPolynomialList.<C> sort(ring, L.list);
113        for (int i = 0; i < si; i++) {
114            GenPolynomial<C> a = l1.get(i);
115            GenPolynomial<C> b = l2.get(i);
116            s = a.compareTo(b);
117            if (s != 0) {
118                return s;
119            }
120        }
121        if (list.size() > si) {
122            return 1;
123        }
124        if (L.list.size() > si) {
125            return -1;
126        }
127        return s;
128    }
129
130
131    /**
132     * Hash code for this polynomial list.
133     * @see java.lang.Object#hashCode()
134     */
135    @Override
136    public int hashCode() {
137        int h;
138        h = ring.hashCode();
139        h = 37 * h + (list == null ? 0 : list.hashCode());
140        return h;
141    }
142
143
144    /**
145     * Test if list is empty.
146     * @return true if this is empty, else false.
147     */
148    public boolean isEmpty() {
149        if (list == null) {
150            return true;
151        }
152        return list.isEmpty();
153    }
154
155
156    /**
157     * String representation of the polynomial list.
158     * @see java.lang.Object#toString()
159     */
160    @Override
161    public String toString() {
162        StringBuffer erg = new StringBuffer();
163        String[] vars = null;
164        if (ring != null) {
165            erg.append(ring.toString());
166            vars = ring.getVars();
167        }
168        boolean first = true;
169        erg.append("\n(\n");
170        String sa = null;
171        for (GenPolynomial<C> oa : list) {
172            if (vars != null) {
173                sa = oa.toString(vars);
174            } else {
175                sa = oa.toString();
176            }
177            if (first) {
178                first = false;
179            } else {
180                erg.append(", ");
181                if (sa.length() > 10) {
182                    erg.append("\n");
183                }
184            }
185            erg.append("( " + sa + " )");
186        }
187        erg.append("\n)");
188        return erg.toString();
189    }
190
191
192    /**
193     * Get a scripting compatible string representation.
194     * @return script compatible representation for this polynomial list.
195     */
196    public String toScript() {
197        StringBuffer s = new StringBuffer();
198        if (ring instanceof GenSolvablePolynomialRing) {
199            switch (Scripting.getLang()) {
200            case Ruby:
201                s.append("SolvIdeal.new(");
202                break;
203            case Python:
204            default:
205                s.append("SolvableIdeal(");
206            }
207        } else {
208            switch (Scripting.getLang()) {
209            case Ruby:
210                s.append("SimIdeal.new(");
211                break;
212            case Python:
213            default:
214                s.append("Ideal(");
215            }
216        }
217        if (ring != null) {
218            s.append(ring.toScript());
219        }
220        if (list == null) {
221            s.append(")");
222            return s.toString();
223        }
224        switch (Scripting.getLang()) {
225        case Ruby:
226            s.append(",\"\",[");
227            break;
228        case Python:
229        default:
230            s.append(",list=[");
231        }
232        boolean first = true;
233        String sa = null;
234        for (GenPolynomial<C> oa : list) {
235            sa = oa.toScript();
236            if (first) {
237                first = false;
238            } else {
239                s.append(", ");
240            }
241            //s.append("( " + sa + " )");
242            s.append(sa);
243        }
244        s.append("])");
245        return s.toString();
246    }
247
248
249    /**
250     * Get ModuleList from PolynomialList. Extract module from polynomial ring.
251     * @see edu.jas.poly.ModuleList
252     * @param i number of variables to be contract form the polynomials.
253     * @return module list corresponding to this.
254     */
255    @SuppressWarnings("unchecked")
256    public ModuleList<C> getModuleList(int i) {
257        GenPolynomialRing<C> pfac = ring.contract(i);
258        logger.debug("contracted ring = {}", pfac);
259        //System.out.println("contracted ring = " + pfac);
260
261        List<List<GenPolynomial<C>>> vecs = null;
262        if (list == null) {
263            return new ModuleList<C>(pfac, vecs);
264        }
265        int rows = list.size();
266        vecs = new ArrayList<List<GenPolynomial<C>>>(rows);
267        if (rows == 0) { // nothing to do
268            return new ModuleList<C>(pfac, vecs);
269        }
270
271        ArrayList<GenPolynomial<C>> zr = new ArrayList<GenPolynomial<C>>(i - 1);
272        GenPolynomial<C> zero = pfac.getZERO();
273        for (int j = 0; j < i; j++) {
274            zr.add(j, zero);
275        }
276
277        for (GenPolynomial<C> p : list) {
278            if (p != null) {
279                Map<ExpVector, GenPolynomial<C>> r = p.contract(pfac);
280                //System.out.println("r = " + r ); 
281                List<GenPolynomial<C>> row = new ArrayList<GenPolynomial<C>>(zr); //zr.clone();
282                for (Map.Entry<ExpVector, GenPolynomial<C>> me : r.entrySet()) {
283                    ExpVector e = me.getKey();
284                    int[] dov = e.dependencyOnVariables();
285                    int ix = 0;
286                    if (dov.length > 1) {
287                        throw new IllegalArgumentException("wrong dependencyOnVariables " + e);
288                    } else if (dov.length == 1) {
289                        ix = dov[0];
290                    }
291                    //ix = i-1 - ix; // revert
292                    //System.out.println("ix = " + ix ); 
293                    GenPolynomial<C> vi = me.getValue(); //r.get( e );
294                    row.set(ix, vi);
295                }
296                //System.out.println("row = " + row ); 
297                vecs.add(row);
298            }
299        }
300        return new ModuleList<C>(pfac, vecs);
301    }
302
303
304    /**
305     * Get list.
306     * @return list from this.
307     */
308    public List<GenPolynomial<C>> getList() {
309        return list;
310    }
311
312
313    /**
314     * Get list as List of GenSolvablePolynomials. Required because no List
315     * casts allowed. Equivalent to cast
316     * (List&lt;GenSolvablePolynomial&lt;C&gt;&gt;) list.
317     * @return solvable polynomial list from this.
318     */
319    public List<GenSolvablePolynomial<C>> castToSolvableList() {
320        return castToSolvableList(list);
321    }
322
323
324    /**
325     * Get list as List of GenSolvablePolynomials. Required because no List
326     * casts allowed. Equivalent to cast
327     * (List&lt;GenSolvablePolynomial&lt;C&gt;&gt;) list.
328     * @return solvable polynomial list from this.
329     */
330    public List<GenSolvablePolynomial<C>> getSolvableList() {
331        return castToSolvableList(list);
332    }
333
334
335    /**
336     * Get ring as GenSolvablePolynomialRing.
337     * @return solvable polynomial ring list from this.
338     */
339    public GenSolvablePolynomialRing<C> getSolvableRing() {
340        return (GenSolvablePolynomialRing<C>) ring;
341    }
342
343
344    /**
345     * Get list as List of GenSolvablePolynomials. Required because no List
346     * casts allowed. Equivalent to cast
347     * (List&lt;GenSolvablePolynomial&lt;C&gt;&gt;) list.
348     * @param list list of extensions of polynomials.
349     * @return solvable polynomial list from this.
350     */
351    public static <C extends RingElem<C>> List<GenSolvablePolynomial<C>> castToSolvableList(
352                    List<GenPolynomial<C>> list) {
353        List<GenSolvablePolynomial<C>> slist = null;
354        if (list == null) {
355            return slist;
356        }
357        slist = new ArrayList<GenSolvablePolynomial<C>>(list.size());
358        GenSolvablePolynomial<C> s;
359        for (GenPolynomial<C> p : list) {
360            if (p == null) {
361                s = null;
362            } else {
363                if (!(p instanceof GenSolvablePolynomial)) {
364                    throw new IllegalArgumentException("no solvable polynomial " + p);
365                }
366                s = (GenSolvablePolynomial<C>) p;
367            }
368            slist.add(s);
369        }
370        return slist;
371    }
372
373
374    /**
375     * Get list of list as List of List of GenSolvablePolynomials. Required
376     * because no List casts allowed. Equivalent to cast
377     * (List&lt;GenSolvablePolynomial&lt;C&gt;&gt;) list.
378     * @param list list of extensions of polynomials.
379     * @return solvable polynomial list from this.
380     */
381    public static <C extends RingElem<C>> List<List<GenSolvablePolynomial<C>>> castToSolvableMatrix(
382                    List<List<GenPolynomial<C>>> list) {
383        List<List<GenSolvablePolynomial<C>>> slist = null;
384        if (list == null) {
385            return slist;
386        }
387        slist = new ArrayList<List<GenSolvablePolynomial<C>>>(list.size());
388        List<GenSolvablePolynomial<C>> s;
389        for (List<GenPolynomial<C>> p : list) {
390            s = PolynomialList.<C> castToSolvableList(p);
391            slist.add(s);
392        }
393        return slist;
394    }
395
396
397    /**
398     * Get list of extensions of polynomials as List of GenPolynomials. Required
399     * because no List casts allowed. Equivalent to cast
400     * (List&lt;GenPolynomial&lt;C&gt;&gt;) list. Mainly used for lists of
401     * GenSolvablePolynomials.
402     * @param slist list of extensions of polynomials.
403     * @return polynomial list from slist.
404     */
405    public static <C extends RingElem<C>> List<GenPolynomial<C>> castToList(
406                    List<? extends GenPolynomial<C>> slist) {
407        logger.debug("warn: can lead to wrong method dispatch");
408        List<GenPolynomial<C>> list = null;
409        if (slist == null) {
410            return list;
411        }
412        list = new ArrayList<GenPolynomial<C>>(slist.size());
413        for (GenPolynomial<C> p : slist) {
414            list.add(p);
415        }
416        return list;
417    }
418
419
420    /**
421     * Get list of list of extensions of polynomials as List of List of
422     * GenPolynomials. Required because no List casts allowed. Equivalent to
423     * cast (List&lt;GenPolynomial&lt;C&gt;&gt;) list. Mainly used for lists of
424     * GenSolvablePolynomials.
425     * @param slist list of extensions of polynomials.
426     * @return polynomial list from slist.
427     */
428    public static <C extends RingElem<C>> List<List<GenPolynomial<C>>> castToMatrix(
429                    List<List<? extends GenPolynomial<C>>> slist) {
430        logger.debug("warn: can lead to wrong method dispatch");
431        List<List<GenPolynomial<C>>> list = null;
432        if (slist == null) {
433            return list;
434        }
435        list = new ArrayList<List<GenPolynomial<C>>>(slist.size());
436        for (List<? extends GenPolynomial<C>> p : slist) {
437            list.add(PolynomialList.<C> castToList(p));
438        }
439        return list;
440    }
441
442
443    /**
444     * Test if list contains only ZEROs.
445     * @return true, if this is the 0 list, else false
446     */
447    public boolean isZERO() {
448        if (list == null) {
449            return true;
450        }
451        for (GenPolynomial<C> p : list) {
452            if (p == null) {
453                continue;
454            }
455            if (!p.isZERO()) {
456                return false;
457            }
458        }
459        return true;
460    }
461
462
463    /**
464     * Test if list contains a ONE.
465     * @return true, if this contains 1, else false
466     */
467    public boolean isONE() {
468        if (list == null) {
469            return false;
470        }
471        for (GenPolynomial<C> p : list) {
472            if (p == null) {
473                continue;
474            }
475            if (p.isONE()) {
476                return true;
477            }
478        }
479        return false;
480    }
481
482
483    /**
484     * Make homogeneous.
485     * @return polynomial list of homogeneous polynomials.
486     */
487    public PolynomialList<C> homogenize() {
488        GenPolynomialRing<C> pfac = ring.extend(1);
489        List<GenPolynomial<C>> hom = new ArrayList<GenPolynomial<C>>(list.size());
490        for (GenPolynomial<C> p : list) {
491            GenPolynomial<C> h = p.homogenize(pfac);
492            hom.add(h);
493        }
494        return new PolynomialList<C>(pfac, hom);
495    }
496
497
498    /**
499     * Dehomogenize.
500     * @return polynomial list of de-homogenized polynomials.
501     */
502    public PolynomialList<C> deHomogenize() {
503        GenPolynomialRing<C> pfac = ring.contract(1);
504        List<GenPolynomial<C>> dehom = new ArrayList<GenPolynomial<C>>(list.size());
505        for (GenPolynomial<C> p : list) {
506            GenPolynomial<C> h = p.deHomogenize(pfac);
507            dehom.add(h);
508        }
509        return new PolynomialList<C>(pfac, dehom);
510    }
511
512
513    /**
514     * Test if all polynomials are homogeneous.
515     * @return true, if all polynomials are homogeneous, else false
516     */
517    public boolean isHomogeneous() {
518        if (list == null) {
519            return true;
520        }
521        for (GenPolynomial<C> p : list) {
522            if (p == null) {
523                continue;
524            }
525            if (!p.isHomogeneous()) {
526                return false;
527            }
528        }
529        return true;
530    }
531
532
533    /**
534     * Union of the delta of exponent vectors of all polynomials.
535     * @return list of u-v, where u = lt() and v != u in p in list.
536     */
537    public SortedSet<ExpVector> deltaExpVectors() {
538        SortedSet<ExpVector> de = new TreeSet<ExpVector>(ring.tord.getAscendComparator());
539        if (list.isEmpty()) {
540            return de;
541        }
542        for (GenPolynomial<C> p : list) {
543            List<ExpVector> pe = p.deltaExpVectors();
544            de.addAll(pe);
545        }
546        return de;
547    }
548
549
550    /**
551     * Union of the delta of exponent vectors of all polynomials.
552     * @param mark list of marked exp vectors of polynomials.
553     * @return list of u-v, where u in mark and v != u in p.expVectors in list.
554     */
555    public SortedSet<ExpVector> deltaExpVectors(List<ExpVector> mark) {
556        SortedSet<ExpVector> de = new TreeSet<ExpVector>(ring.tord.getAscendComparator());
557        if (list.isEmpty()) {
558            return de;
559        }
560        if (mark.isEmpty()) {
561            return deltaExpVectors();
562        }
563        if (list.size() != mark.size()) {
564            throw new IllegalArgumentException("#list != #mark");
565        }
566        int i = 0;
567        for (GenPolynomial<C> p : list) {
568            ExpVector u = mark.get(i);
569            List<ExpVector> pe = p.deltaExpVectors(u);
570            de.addAll(pe);
571            i++;
572        }
573        return de;
574    }
575
576
577    /**
578     * Leading weight polynomials.
579     * @return list of polynomials with terms of maximal weight degree.
580     */
581    public List<GenPolynomial<C>> leadingWeightPolynomials() {
582        List<GenPolynomial<C>> lw = new ArrayList<GenPolynomial<C>>(list.size());
583        if (list.isEmpty()) {
584            return lw;
585        }
586        for (GenPolynomial<C> p : list) {
587            GenPolynomial<C> pw = p.leadingWeightPolynomial();
588            lw.add(pw);
589        }
590        return lw;
591    }
592
593}