001 /*
002 * $Id: OrderedPairlist.java 3420 2010-12-19 21:34:25Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.ArrayList;
008 import java.util.BitSet;
009 import java.util.Iterator;
010 import java.util.LinkedList;
011 import java.util.List;
012 import java.util.Map;
013 import java.util.TreeMap;
014 import java.util.SortedMap;
015
016 import org.apache.log4j.Logger;
017
018 import edu.jas.poly.ExpVector;
019 import edu.jas.poly.GenPolynomial;
020 import edu.jas.poly.GenPolynomialRing;
021 import edu.jas.poly.GenSolvablePolynomialRing;
022
023 import edu.jas.structure.RingElem;
024
025 /**
026 * Pair list management.
027 * The original Buchberger algorithm with criterions following
028 * Winkler in SAC-1, Kredel in ALDES/SAC-2, Kredel in MAS.
029 * Implemented using GenPolynomial, TreeMap and BitSet.
030 * @author Heinz Kredel
031 */
032
033 public class OrderedPairlist<C extends RingElem<C> > implements PairList<C> {
034
035 protected final List<GenPolynomial<C>> P;
036 protected final SortedMap<ExpVector,LinkedList<Pair<C>>> pairlist;
037 protected final List<BitSet> red;
038 protected final GenPolynomialRing<C> ring;
039 protected final Reduction<C> reduction;
040 protected boolean oneInGB = false;
041 protected boolean useCriterion4 = true;
042 protected int putCount;
043 protected int remCount;
044 protected final int moduleVars;
045
046 private static final Logger logger = Logger.getLogger(OrderedPairlist.class);
047
048
049 /**
050 * Constructor.
051 */
052 public OrderedPairlist() {
053 moduleVars = 0;
054 ring = null;
055 P = null;
056 pairlist = null;
057 red = null;
058 reduction = null;
059 putCount = 0;
060 remCount = 0;
061 }
062
063
064 /**
065 * Constructor.
066 * @param r polynomial factory.
067 */
068 public OrderedPairlist(GenPolynomialRing<C> r) {
069 this(0,r);
070 }
071
072
073 /**
074 * Constructor.
075 * @param m number of module variables.
076 * @param r polynomial factory.
077 */
078 public OrderedPairlist(int m, GenPolynomialRing<C> r) {
079 moduleVars = m;
080 ring = r;
081 P = new ArrayList<GenPolynomial<C>>();
082 pairlist = new TreeMap<ExpVector,LinkedList<Pair<C>>>( ring.tord.getAscendComparator() );
083 //pairlist = new TreeMap( to.getSugarComparator() );
084 red = new ArrayList<BitSet>();
085 putCount = 0;
086 remCount = 0;
087 if ( !ring.isCommutative() ) {//ring instanceof GenSolvablePolynomialRing ) {
088 useCriterion4 = false;
089 }
090 reduction = new ReductionSeq<C>();
091 }
092
093
094 /**
095 * Create a new PairList.
096 * @param r polynomial ring.
097 */
098 public PairList<C> create(GenPolynomialRing<C> r) {
099 return new OrderedPairlist<C>(r);
100 }
101
102
103 /**
104 * Create a new PairList.
105 * @param m number of module variables.
106 * @param r polynomial ring.
107 */
108 public PairList<C> create(int m, GenPolynomialRing<C> r) {
109 return new OrderedPairlist<C>(m,r);
110 }
111
112
113 /**
114 * toString.
115 */
116 @Override
117 public String toString() {
118 StringBuffer s = new StringBuffer(this.getClass().getSimpleName() + "(");
119 //s.append("polys="+P.size());
120 s.append("#put="+putCount);
121 s.append(", #rem="+remCount);
122 if ( pairlist != null && pairlist.size() != 0 ) {
123 s.append(", size="+pairlist.size());
124 }
125 s.append(")");
126 return s.toString();
127 }
128
129
130 /**
131 * Put one Polynomial to the pairlist and reduction matrix.
132 * @param p polynomial.
133 * @return the index of the added polynomial.
134 */
135 public synchronized int put(GenPolynomial<C> p) {
136 putCount++;
137 if ( oneInGB ) {
138 return P.size()-1;
139 }
140 ExpVector e = p.leadingExpVector();
141 int l = P.size();
142 for ( int j = 0; j < l; j++ ) {
143 GenPolynomial<C> pj = P.get(j);
144 ExpVector f = pj.leadingExpVector();
145 if ( moduleVars > 0 ) {
146 if ( !reduction.moduleCriterion( moduleVars, e, f) ) {
147 continue; // skip pair
148 }
149 }
150 ExpVector g = e.lcm( f );
151 Pair<C> pair = new Pair<C>( pj, p, j, l);
152 //System.out.println("pair.new = " + pair);
153 //multiple pairs under same keys -> list of pairs
154 LinkedList<Pair<C>> xl = pairlist.get( g );
155 if ( xl == null ) {
156 xl = new LinkedList<Pair<C>>();
157 }
158 //xl.addLast( pair ); // first or last ?
159 xl.addFirst( pair ); // first or last ? better for d- e-GBs
160 pairlist.put( g, xl );
161 }
162 // System.out.println("pairlist.keys@put = " + pairlist.keySet() );
163 P.add( p );
164 BitSet redi = new BitSet();
165 redi.set( 0, l );
166 red.add( redi );
167 //System.out.println("pairlist.set = " + red); //.get( pair.j )); //pair);
168 //System.out.println("pairlist.key = " + pairlist.keySet() );
169 return P.size()-1;
170 }
171
172
173 /**
174 * Remove the next required pair from the pairlist and reduction matrix.
175 * Appy the criterions 3 and 4 to see if the S-polynomial is required.
176 * @return the next pair if one exists, otherwise null.
177 */
178 public synchronized Pair<C> removeNext() {
179 if ( oneInGB ) {
180 return null;
181 }
182 Iterator< Map.Entry<ExpVector,LinkedList<Pair<C>>> > ip
183 = pairlist.entrySet().iterator();
184
185 Pair<C> pair = null;
186 boolean c = false;
187 int i, j;
188
189 while ( !c && ip.hasNext() ) {
190 Map.Entry<ExpVector,LinkedList<Pair<C>>> me = ip.next();
191 ExpVector g = me.getKey();
192 LinkedList<Pair<C>> xl = me.getValue();
193 if ( logger.isInfoEnabled() ) {
194 logger.info("g = " + g);
195 }
196 pair = null;
197 while ( !c && xl.size() > 0 ) {
198 pair = xl.removeFirst();
199 // xl is also modified in pairlist
200 i = pair.i;
201 j = pair.j;
202 // System.out.println("pair(" + j + "," +i+") ");
203 if ( useCriterion4 ) {
204 c = reduction.criterion4( pair.pi, pair.pj, g );
205 } else {
206 c = true;
207 }
208 //System.out.println("c4_o = " + c);
209 if ( c ) {
210 c = criterion3( i, j, g );
211 //System.out.println("c3_o = " + c);
212 }
213 red.get( j ).clear(i); // set(i,false) jdk1.4
214 }
215 if ( xl.size() == 0 ) {
216 ip.remove();
217 // = pairlist.remove( g );
218 }
219 }
220 if ( ! c ) {
221 pair = null;
222 } else {
223 remCount++; // count only real pairs
224 }
225 return pair;
226 }
227
228
229 /**
230 * Test if there is possibly a pair in the list.
231 * @return true if a next pair could exist, otherwise false.
232 */
233 public synchronized boolean hasNext() {
234 return pairlist.size() > 0;
235 }
236
237
238 /**
239 * Get the list of polynomials.
240 * @return the polynomial list.
241 */
242 public List<GenPolynomial<C>> getList() {
243 return P;
244 }
245
246
247 /**
248 * Get the number of polynomials put to the pairlist.
249 * @return the number of calls to put.
250 */
251 public int putCount() {
252 return putCount;
253 }
254
255
256 /**
257 * Get the number of required pairs removed from the pairlist.
258 * @return the number of non null pairs delivered.
259 */
260 public int remCount() {
261 return remCount;
262 }
263
264
265 /**
266 * Put the ONE-Polynomial to the pairlist.
267 * @param one polynomial. (no more required)
268 * @return the index of the last polynomial.
269 */
270 public synchronized int putOne(GenPolynomial<C> one) {
271 if ( one == null ) {
272 return P.size()-1;
273 }
274 if ( ! one.isONE() ) {
275 return P.size()-1;
276 }
277 return putOne();
278 }
279
280
281 /**
282 * Put the ONE-Polynomial to the pairlist.
283 * @return the index of the last polynomial.
284 */
285 public synchronized int putOne() {
286 putCount++;
287 oneInGB = true;
288 pairlist.clear();
289 P.clear();
290 P.add(ring.getONE());
291 red.clear();
292 return P.size()-1;
293 }
294
295
296 /**
297 * GB criterium 3.
298 * @return true if the S-polynomial(i,j) is required.
299 */
300 public boolean criterion3(int i, int j, ExpVector eij) {
301 // assert i < j;
302 boolean s = red.get( j ).get(i);
303 if ( ! s ) {
304 logger.warn("c3.s false for " + j + " " + i);
305 return s;
306 }
307 // now s = true;
308 for ( int k = 0; k < P.size(); k++ ) {
309 // System.out.println("i , k , j "+i+" "+k+" "+j);
310 if ( i != k && j != k ) {
311 GenPolynomial<C> A = P.get( k );
312 ExpVector ek = A.leadingExpVector();
313 boolean m = eij.multipleOf(ek);
314 if ( m ) {
315 if ( k < i ) {
316 // System.out.println("k < i "+k+" "+i);
317 s = red.get( i ).get(k)
318 || red.get( j ).get(k);
319 } else if ( i < k && k < j ) {
320 // System.out.println("i < k < j "+i+" "+k+" "+j);
321 s = red.get( k ).get(i)
322 || red.get( j ).get(k);
323 } else if ( j < k ) {
324 //System.out.println("j < k "+j+" "+k);
325 s = red.get( k ).get(i)
326 || red.get( k ).get(j);
327 }
328 //System.out.println("s."+k+" = " + s);
329 if ( ! s ) {
330 return s;
331 }
332 }
333 }
334 }
335 return true;
336 }
337
338 }