001/*
002 * $Id: OrderedPolynomialList.java 5468 2016-03-25 15:27:51Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.util.ArrayList;
009import java.util.Arrays;
010import java.util.Comparator;
011import java.util.List;
012
013import edu.jas.structure.RingElem;
014
015
016/**
017 * Ordered list of polynomials. Mainly for storage and printing / toString and
018 * conversions to other representations. Polynomials in this list are sorted
019 * according to their head terms.
020 * @author Heinz Kredel
021 */
022
023public class OrderedPolynomialList<C extends RingElem<C>> extends PolynomialList<C> {
024
025
026    /**
027     * Constructor.
028     * @param r polynomial ring factory.
029     * @param l list of polynomials.
030     */
031    public OrderedPolynomialList(GenPolynomialRing<C> r, List<GenPolynomial<C>> l) {
032        super(r, sort(r, l));
033    }
034
035
036    /**
037     * Comparison with any other object.
038     * @see java.lang.Object#equals(java.lang.Object)
039     */
040    @Override
041    @SuppressWarnings("unchecked")
042    public boolean equals(Object p) {
043        if (!super.equals(p)) {
044            return false;
045        }
046        OrderedPolynomialList<C> pl = null;
047        try {
048            pl = (OrderedPolynomialList<C>) p;
049        } catch (ClassCastException ignored) {
050        }
051        if (pl == null) {
052            return false;
053        }
054        // compare sorted lists
055        // done already in super.equals()
056        return true;
057    }
058
059
060    /**
061     * Hash code for OrderedPolynomialList.
062     * @see java.lang.Object#hashCode()
063     */
064    @Override
065    public int hashCode() {
066        return super.hashCode();
067    }
068
069
070    /**
071     * Sort a list of polynomials with respect to the ascending order of the
072     * leading Exponent vectors. The term order is taken from the ring.
073     * @param L polynomial list.
074     * @return sorted polynomial list from L.
075     */
076    public static <C extends RingElem<C>> List<GenPolynomial<C>> sort(List<GenPolynomial<C>> L) {
077        if (L == null) {
078            return L;
079        }
080        if (L.size() <= 1) { // nothing to sort
081            return L;
082        }
083        GenPolynomialRing<C> r = L.get(0).ring;
084        return sort(r,L);
085    }
086
087
088    /**
089     * Sort a list of polynomials with respect to the ascending order of the
090     * leading Exponent vectors. The term order is taken from the ring.
091     * @param r polynomial ring factory.
092     * @param L polynomial list.
093     * @return sorted polynomial list from L.
094     */
095    @SuppressWarnings({ "unchecked", "cast" })
096    public static <C extends RingElem<C>> List<GenPolynomial<C>> sort(GenPolynomialRing<C> r,
097                    List<GenPolynomial<C>> L) {
098        if (L == null) {
099            return L;
100        }
101        if (L.size() <= 1) { // nothing to sort
102            return L;
103        }
104        final Comparator<ExpVector> evc = r.tord.getAscendComparator();
105        Comparator<GenPolynomial<C>> cmp = new Comparator<GenPolynomial<C>>() {
106
107
108            public int compare(GenPolynomial<C> p1, GenPolynomial<C> p2) {
109                ExpVector e1 = p1.leadingExpVector();
110                ExpVector e2 = p2.leadingExpVector();
111                if (e1 == null) {
112                    return -1; // dont care
113                }
114                if (e2 == null) {
115                    return 1; // dont care
116                }
117                if (e1.length() != e2.length()) {
118                    if (e1.length() > e2.length()) {
119                        return 1; // dont care
120                    }
121                    return -1; // dont care
122                }
123                return evc.compare(e1, e2);
124            }
125        };
126        GenPolynomial<C>[] s = null;
127        try {
128            s = (GenPolynomial<C>[]) new GenPolynomial[L.size()];
129            int i = 0;
130            for (GenPolynomial<C> p : L) {
131                s[i++] = p;
132            }
133            Arrays.<GenPolynomial<C>> sort(s, cmp);
134            return new ArrayList<GenPolynomial<C>>(Arrays.<GenPolynomial<C>> asList(s));
135        } catch (ClassCastException ok) {
136            System.out.println("Warning: polynomials not sorted");
137        }
138        return L; // unsorted
139    }
140
141
142    /**
143     * Sort a list of polynomials with respect to the ascending order of the
144     * degree. 
145     * @param L polynomial list.
146     * @return sorted polynomial list from L.
147     */
148    @SuppressWarnings({ "unchecked", "cast" })
149    public static <C extends RingElem<C>> List<GenPolynomial<C>> sortDegree(List<GenPolynomial<C>> L) {
150        if (L == null) {
151            return L;
152        }
153        if (L.size() <= 1) { // nothing to sort
154            return L;
155        }
156        Comparator<GenPolynomial<C>> cmp = new Comparator<GenPolynomial<C>>() {
157
158            public int compare(GenPolynomial<C> p1, GenPolynomial<C> p2) {
159                long d1 = p1.degree();
160                long d2 = p2.degree();
161                if (d1 > d2) {
162                    return -1;
163                } else if (d1 < d2) {
164                    return 1;
165                }
166                return 0;
167            }
168        };
169        GenPolynomial<C>[] s = null;
170        try {
171            s = (GenPolynomial<C>[]) new GenPolynomial[L.size()];
172            int i = 0;
173            for (GenPolynomial<C> p : L) {
174                s[i++] = p;
175            }
176            Arrays.<GenPolynomial<C>> sort(s, cmp);
177            return new ArrayList<GenPolynomial<C>>(Arrays.<GenPolynomial<C>> asList(s));
178        } catch (ClassCastException ok) {
179            System.out.println("Warning: polynomials not sorted");
180        }
181        return L; // unsorted
182    }
183
184}