001 /*
002 * $Id: CriticalPairList.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.Comparator;
010 import java.util.Iterator;
011 import java.util.List;
012 import java.util.SortedSet;
013 import java.util.TreeSet;
014
015 import org.apache.log4j.Logger;
016
017 import edu.jas.poly.ExpVector;
018 import edu.jas.poly.GenPolynomial;
019 import edu.jas.poly.GenPolynomialRing;
020 import edu.jas.poly.GenSolvablePolynomialRing;
021 import edu.jas.structure.RingElem;
022
023 /**
024 * Critical pair list management.
025 * Makes some effort to produce the same sequence of critical pairs
026 * as in the sequential case, when used in parallel.
027 * However already reduced pairs are not re-reduced if new
028 * polynomials appear.
029 * Implemented using GenPolynomial, SortedSet / TreeSet and BitSet.
030 * @author Heinz Kredel
031 */
032
033 public class CriticalPairList<C extends RingElem<C>> extends OrderedPairlist<C> {
034
035 protected final SortedSet< CriticalPair<C> > pairlist; // hide super
036
037 protected int recordCount;
038
039 private static final Logger logger = Logger.getLogger(CriticalPairList.class);
040
041
042 /**
043 * Constructor for CriticalPairList.
044 */
045 public CriticalPairList() {
046 super();
047 pairlist = null;
048 }
049
050
051 /**
052 * Constructor for CriticalPairList.
053 * @param r polynomial factory.
054 */
055 public CriticalPairList(GenPolynomialRing<C> r) {
056 this(0,r);
057 }
058
059
060 /**
061 * Constructor for CriticalPairList.
062 * @param m number of module variables.
063 * @param r polynomial factory.
064 */
065 public CriticalPairList(int m, GenPolynomialRing<C> r) {
066 super(m,r);
067 Comparator< AbstractPair<C> > cpc;
068 cpc = new CriticalPairComparator<C>( ring.tord );
069 pairlist = new TreeSet< CriticalPair<C> >( cpc );
070 recordCount = 0;
071 }
072
073
074 /**
075 * Create a new PairList.
076 * @param r polynomial ring.
077 */
078 public PairList<C> create(GenPolynomialRing<C> r) {
079 return new CriticalPairList<C>(r);
080 }
081
082
083 /**
084 * Create a new PairList.
085 * @param m number of module variables.
086 * @param r polynomial ring.
087 */
088 public PairList<C> create(int m, GenPolynomialRing<C> r) {
089 return new CriticalPairList<C>(m,r);
090 }
091
092
093 /**
094 * Put a polynomial to the pairlist and reduction matrix.
095 * @param p polynomial.
096 * @return the index of the added polynomial.
097 */
098 public synchronized int put(GenPolynomial<C> p) {
099 putCount++;
100 if ( oneInGB ) {
101 return P.size()-1;
102 }
103 ExpVector e = p.leadingExpVector();
104 int len = P.size();
105 for ( int j = 0; j < len; j++ ) {
106 GenPolynomial<C> pj = P.get(j);
107 ExpVector f = pj.leadingExpVector();
108 if ( moduleVars > 0 ) { // test moduleCriterion
109 if ( !reduction.moduleCriterion( moduleVars, e, f) ) {
110 continue; // skip pair
111 }
112 }
113 ExpVector g = e.lcm( f );
114 CriticalPair<C> pair = new CriticalPair<C>( g, pj, p, j, len );
115 //System.out.println("put pair = " + pair );
116 pairlist.add( pair );
117 }
118 P.add( p );
119 BitSet redi = new BitSet();
120 redi.set( 0, len ); // >= jdk 1.4
121 red.add( redi );
122 if ( recordCount < len ) {
123 recordCount = len;
124 }
125 return len;
126 }
127
128
129 /**
130 * Test if there is possibly a pair in the list.
131 * @return true if a next pair could exist, otherwise false.
132 */
133 public synchronized boolean hasNext() {
134 return pairlist.size() > 0;
135 }
136
137
138 /**
139 * Get and remove the next required pair from the pairlist.
140 * Appy the criterions 3 and 4 to see if the S-polynomial is required.
141 * The pair is not removed from the pair list.
142 * @return the next pair if one exists, otherwise null.
143 */
144 public Pair<C> removeNext() {
145 CriticalPair<C> cp = getNext();
146 if ( cp == null ) {
147 return null;
148 }
149 return new Pair<C>(cp.pi,cp.pj,cp.i,cp.j);
150 }
151
152
153 /**
154 * Get the next required pair from the pairlist.
155 * Appy the criterions 3 and 4 to see if the S-polynomial is required.
156 * The pair is not removed from the pair list.
157 * @return the next pair if one exists, otherwise null.
158 */
159 public synchronized CriticalPair<C> getNext() {
160 if ( oneInGB ) {
161 return null;
162 }
163 CriticalPair<C> pair = null;
164 Iterator< CriticalPair<C> > ip = pairlist.iterator();
165 boolean c = false;
166 while ( !c & ip.hasNext() ) {
167 pair = ip.next();
168 if ( pair.getInReduction() ) {
169 continue;
170 }
171 if ( pair.getReductum() != null ) {
172 continue;
173 }
174 if ( logger.isInfoEnabled() ) {
175 logger.info("" + pair);
176 }
177 if ( useCriterion4 ) {
178 c = reduction.criterion4( pair.pi, pair.pj, pair.e );
179 // System.out.println("c4 = " + c);
180 } else {
181 c = true;
182 }
183 if ( c ) {
184 c = criterion3( pair.i, pair.j, pair.e );
185 // System.out.println("c3 = " + c);
186 }
187 red.get( pair.j ).clear( pair.i ); // set(i,false) jdk1.4
188 if ( ! c ) { // set done
189 pair.setReductum( ring.getZERO() );
190 }
191 }
192 if ( ! c ) {
193 pair = null;
194 } else {
195 remCount++; // count only real pairs
196 pair.setInReduction(); // set to work
197 }
198 return pair;
199 }
200
201
202 /**
203 * Record reduced polynomial.
204 * @param pair the corresponding critical pair.
205 * @param p polynomial.
206 * @return index of recorded polynomial, or -1 if not added.
207 */
208 public int record(CriticalPair<C> pair, GenPolynomial<C> p) {
209 if ( p == null ) {
210 p = ring.getZERO();
211 }
212 pair.setReductum(p);
213 // trigger thread
214 if ( ! p.isZERO() && ! p.isONE() ) {
215 recordCount++;
216 return recordCount;
217 }
218 return -1;
219 }
220
221
222 /**
223 * Record reduced polynomial and update critical pair list.
224 * Note: it is better to use record and uptate separately.
225 * @param pair the corresponding critical pair.
226 * @param p polynomial.
227 * @return index of recorded polynomial
228 */
229 public int update(CriticalPair<C> pair, GenPolynomial<C> p) {
230 if ( p == null ) {
231 p = ring.getZERO();
232 }
233 pair.setReductum(p);
234 if ( ! p.isZERO() && ! p.isONE() ) {
235 recordCount++;
236 }
237 int c = update();
238 if ( ! p.isZERO() && ! p.isONE() ) {
239 return recordCount;
240 }
241 return -1;
242 }
243
244
245 /**
246 * Update pairlist.
247 * Preserve the sequential pair sequence.
248 * Remove pairs with completed reductions.
249 * @return the number of added polynomials.
250 */
251 public synchronized int update() {
252 int num = 0;
253 if ( oneInGB ) {
254 return num;
255 }
256 while ( pairlist.size() > 0 ) {
257 CriticalPair<C> pair = pairlist.first();
258 GenPolynomial<C> p = pair.getReductum();
259 if ( p != null ) {
260 pairlist.remove( pair );
261 num++;
262 if ( ! p.isZERO() ) {
263 if ( p.isONE() ) {
264 putOne(); // sets size = 1
265 } else {
266 put( p ); // changes pair list
267 }
268 }
269 } else {
270 break;
271 }
272 }
273 return num;
274 }
275
276
277 /**
278 * In work pairs. List pairs which are currently reduced.
279 * @return list of critical pairs which are in reduction.
280 */
281 public synchronized List<CriticalPair<C>> inWork() {
282 List<CriticalPair<C>> iw;
283 iw = new ArrayList<CriticalPair<C>>();
284 if ( oneInGB ) {
285 return iw;
286 }
287 for ( CriticalPair<C> pair : pairlist ) {
288 if ( pair.getInReduction() ) {
289 iw.add( pair );
290 }
291 }
292 return iw;
293 }
294
295
296 /**
297 * Update pairlist, several pairs at once.
298 * This version does not preserve the sequential pair sequence.
299 * Remove pairs with completed reductions.
300 * @return the number of added polynomials.
301 */
302 public synchronized int updateMany() {
303 int num = 0;
304 if ( oneInGB ) {
305 return num;
306 }
307 List<CriticalPair<C>> rem = new ArrayList<CriticalPair<C>>();
308 for ( CriticalPair<C> pair : pairlist ) {
309 if ( pair.getReductum() != null ) {
310 rem.add( pair );
311 num++;
312 } else {
313 break;
314 }
315 }
316 // must work on a copy to avoid concurrent modification
317 for ( CriticalPair<C> pair : rem ) {
318 // System.out.println("update = " + pair);
319 pairlist.remove( pair );
320 GenPolynomial<C> p = pair.getReductum();
321 if ( ! p.isZERO() ) {
322 if ( p.isONE() ) {
323 putOne();
324 } else {
325 put( p );
326 }
327 }
328 }
329 return num;
330 }
331
332
333 /**
334 * Put the ONE-Polynomial to the pairlist.
335 * @return the index of the last polynomial.
336 */
337 public synchronized int putOne() {
338 super.putOne();
339 pairlist.clear();
340 return 0;
341 }
342
343 }