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