Source code

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