001/*
002 * $Id: OrderedModuleList.java 4057 2012-07-26 20:35:44Z 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 vectors of polynomials. Mainly for storage and printing /
018 * toString and conversions to other representations. Lists of polynomials in
019 * this list are sorted according to the head terms of the first column.
020 * @author Heinz Kredel
021 */
022
023public class OrderedModuleList<C extends RingElem<C>> extends ModuleList<C> {
024
025
026    /**
027     * Constructor.
028     * @param r polynomial ring factory.
029     * @param l list of list of polynomials.
030     */
031    public OrderedModuleList(GenPolynomialRing<C> r, List<List<GenPolynomial<C>>> l) {
032        super(r, sort(r, ModuleList.padCols(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    // not jet working
043    public boolean equals(Object m) {
044        if (!super.equals(m)) {
045            return false;
046        }
047        OrderedModuleList<C> ml = null;
048        try {
049            ml = (OrderedModuleList<C>) m;
050        } catch (ClassCastException ignored) {
051        }
052        if (ml == null) {
053            return false;
054        }
055        // compare sorted lists
056        // done already in super.equals()
057        return true;
058    }
059
060
061    /**
062     * Hash code for OrderedModuleList.
063     * @see java.lang.Object#hashCode()
064     */
065    @Override
066    public int hashCode() {
067        return super.hashCode();
068    }
069
070
071    /**
072     * Sort a list of vectors of polynomials with respect to the ascending order
073     * of the leading Exponent vectors of the first column. The term order is
074     * taken from the ring.
075     * @param r polynomial ring factory.
076     * @param l list of polynomial lists.
077     * @return sorted list of polynomial lists from l.
078     */
079    @SuppressWarnings("unchecked")
080    public static <C extends RingElem<C>> List<List<GenPolynomial<C>>> sort(GenPolynomialRing<C> r,
081                    List<List<GenPolynomial<C>>> l) {
082        if (l == null) {
083            return l;
084        }
085        if (l.size() <= 1) { // nothing to sort
086            return l;
087        }
088        final Comparator<ExpVector> evc = r.tord.getAscendComparator();
089        Comparator<List<GenPolynomial<C>>> cmp = new Comparator<List<GenPolynomial<C>>>() {
090
091
092            public int compare(List<GenPolynomial<C>> l1, List<GenPolynomial<C>> l2) {
093                int c = 0;
094                for (int i = 0; i < l1.size(); i++) {
095                    GenPolynomial<C> p1 = l1.get(i);
096                    GenPolynomial<C> p2 = l2.get(i);
097                    ExpVector e1 = p1.leadingExpVector();
098                    ExpVector e2 = p2.leadingExpVector();
099                    if (e1 == e2) {
100                        continue;
101                    }
102                    if (e1 == null && e2 != null) {
103                        return -1;
104                    }
105                    if (e1 != null && e2 == null) {
106                        return 1;
107                    }
108                    if (e1 == null || e2 == null) { // for findbugs
109                        continue; // cannot happen
110                    }
111                    if (e1.length() != e2.length()) {
112                        if (e1.length() > e2.length()) {
113                            return 1;
114                        }
115                        return -1;
116                    }
117                    c = evc.compare(e1, e2);
118                    if (c != 0) {
119                        return c;
120                    }
121                }
122                return c;
123            }
124        };
125
126        List<GenPolynomial<C>>[] s = null;
127        try {
128            s = (List<GenPolynomial<C>>[]) new List[l.size()];
129            //System.out.println("s.length = " + s.length );
130            //s = l.toArray(s); does not work
131            //for ( int i = 0; i < l.size(); i++ ) {
132            //    s[i] = l.get(i);
133            //}
134            int i = 0;
135            for (List<GenPolynomial<C>> p : l) {
136                s[i++] = p;
137            }
138            Arrays.<List<GenPolynomial<C>>> sort(s, cmp);
139            return new ArrayList<List<GenPolynomial<C>>>(Arrays.<List<GenPolynomial<C>>> asList(s));
140        } catch (ClassCastException ok) {
141            System.out.println("Warning: polynomials not sorted");
142        }
143        return l; // unsorted
144    }
145
146}