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