Source code

001/*
002 * $Id$
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     * Get polynomial ring.
135     * @return the polynomial ring.
136     */
137    public GenPolynomialRing<C> getRing() {
138        return ring;
139    }
140
141
142    /**
143     * toString.
144     */
145    @Override
146    public String toString() {
147        StringBuffer s = new StringBuffer(this.getClass().getSimpleName() + "(");
148        //s.append("polys="+P.size());
149        s.append("#put=" + putCount);
150        s.append(", #rem=" + remCount);
151        if (pairlist != null && pairlist.size() != 0) {
152            s.append(", size=" + pairlist.size());
153        }
154        if (moduleVars > 0) {
155            s.append(", modv=" + moduleVars);
156        }
157        s.append(")");
158        return s.toString();
159    }
160
161
162    /**
163     * Put one Polynomial to the pairlist and reduction matrix.
164     * @param p polynomial.
165     * @return the index of the added polynomial.
166     */
167    public synchronized int put(GenPolynomial<C> p) {
168        putCount++;
169        if (oneInGB) {
170            return P.size() - 1;
171        }
172        ExpVector e = p.leadingExpVector();
173        int l = P.size();
174        for (int j = 0; j < l; j++) {
175            GenPolynomial<C> pj = P.get(j);
176            ExpVector f = pj.leadingExpVector();
177            if (moduleVars > 0) {
178                if (!reduction.moduleCriterion(moduleVars, e, f)) {
179                    continue; // skip pair
180                }
181            }
182            ExpVector g = e.lcm(f);
183            Pair<C> pair = new Pair<C>(pj, p, j, l);
184            //System.out.println("pair.new      = " + pair);
185            //multiple pairs under same keys -> list of pairs
186            LinkedList<Pair<C>> xl = pairlist.get(g);
187            if (xl == null) {
188                xl = new LinkedList<Pair<C>>();
189            }
190            //xl.addLast( pair ); // first or last ?
191            xl.addFirst(pair); // first or last ? better for d- e-GBs
192            pairlist.put(g, xl);
193        }
194        //System.out.println("pairlist.keys@put = " + pairlist.keySet() );  
195        P.add(p);
196        BitSet redi = new BitSet();
197        redi.set(0, l);
198        red.add(redi);
199        //System.out.println("pairlist.red = " + red); //.get( pair.j )); //pair);
200        //System.out.println("pairlist.key = " + pairlist.keySet() );  
201        return P.size() - 1;
202    }
203
204
205    /**
206     * Put all polynomials in F to the pairlist and reduction matrix.
207     * @param F polynomial list.
208     * @return the index of the last added polynomial.
209     */
210    public int put(List<GenPolynomial<C>> F) {
211        int i = 0;
212        for (GenPolynomial<C> p : F) {
213            i = put(p);
214        }
215        return i;
216    }
217
218
219    /**
220     * Remove the next required pair from the pairlist and reduction matrix.
221     * Apply the criterions 3 and 4 to see if the S-polynomial is required.
222     * @return the next pair if one exists, otherwise null.
223     */
224    public synchronized Pair<C> removeNext() {
225        if (oneInGB) {
226            return null;
227        }
228        Iterator<Map.Entry<ExpVector, LinkedList<Pair<C>>>> ip = pairlist.entrySet().iterator();
229
230        Pair<C> pair = null;
231        boolean c = false;
232        int i, j;
233
234        while (!c && ip.hasNext()) {
235            Map.Entry<ExpVector, LinkedList<Pair<C>>> me = ip.next();
236            ExpVector g = me.getKey();
237            LinkedList<Pair<C>> xl = me.getValue();
238            if (logger.isInfoEnabled()) {
239                logger.info("g  = {}", g);
240            }
241            pair = null;
242            while (!c && xl.size() > 0) {
243                pair = xl.removeFirst();
244                // xl is also modified in pairlist 
245                i = pair.i;
246                j = pair.j;
247                // System.out.println("pair(" + j + "," +i+") ");
248                if (useCriterion4) {
249                    c = reduction.criterion4(pair.pi, pair.pj, g);
250                } else {
251                    c = true;
252                }
253                //System.out.println("c4_o  = " + c);  
254                if (c) {
255                    c = criterion3(i, j, g);
256                    //System.out.println("c3_o  = " + c); 
257                }
258                red.get(j).clear(i); // set(i,false) jdk1.4
259            }
260            if (xl.size() == 0) {
261                ip.remove();
262                // = pairlist.remove( g );
263            }
264        }
265        if (!c) {
266            pair = null;
267        } else {
268            pair.maxIndex(P.size() - 1);
269            remCount++; // count only real pairs
270            if (logger.isDebugEnabled()) {
271                logger.info("pair({},{})", pair.j, pair.i);
272            }
273        }
274        return pair;
275    }
276
277
278    /**
279     * Test if there is possibly a pair in the list.
280     * @return true if a next pair could exist, otherwise false.
281     */
282    public synchronized boolean hasNext() {
283        return pairlist.size() > 0;
284    }
285
286
287    /**
288     * Get the list of polynomials.
289     * @return the polynomial list.
290     */
291    public List<GenPolynomial<C>> getList() {
292        return P;
293    }
294
295
296    /**
297     * Set the list of polynomials.
298     * @param F the polynomial list.
299     */
300    public void setList(List<GenPolynomial<C>> F) {
301        if (!P.isEmpty()) {
302            throw new IllegalArgumentException("P not empty");
303        }
304        P.addAll(F);
305        for (int i = 0; i < P.size(); i++) {
306            BitSet redi = new BitSet();
307            red.add(redi);
308        }
309
310    }
311
312
313    /**
314     * Get the size of the list of polynomials.
315     * @return size of the polynomial list.
316     */
317    public int size() {
318        return P.size();
319    }
320
321
322    /**
323     * Get the number of polynomials put to the pairlist.
324     * @return the number of calls to put.
325     */
326    public synchronized int putCount() {
327        return putCount;
328    }
329
330
331    /**
332     * Get the number of required pairs removed from the pairlist.
333     * @return the number of non null pairs delivered.
334     */
335    public synchronized int remCount() {
336        return remCount;
337    }
338
339
340    /**
341     * Put the ONE-Polynomial to the pairlist.
342     * @param one polynomial. (no more required)
343     * @return the index of the last polynomial.
344     */
345    public synchronized int putOne(GenPolynomial<C> one) {
346        if (one == null) {
347            return P.size() - 1;
348        }
349        if (!one.isONE()) {
350            return P.size() - 1;
351        }
352        return putOne();
353    }
354
355
356    /**
357     * Put the ONE-Polynomial to the pairlist.
358     * @return the index of the last polynomial.
359     */
360    public synchronized int putOne() {
361        putCount++;
362        oneInGB = true;
363        pairlist.clear();
364        P.clear();
365        P.add(ring.getONE());
366        red.clear();
367        logger.info("outOne {}", this);
368        return P.size() - 1;
369    }
370
371
372    /**
373     * GB criterium 3.
374     * @return true if the S-polynomial(i,j) is required.
375     */
376    public boolean criterion3(int i, int j, ExpVector eij) {
377        // assert i < j;
378        boolean s = red.get(j).get(i);
379        if (!s) {
380            logger.warn("c3.s false for j, i = {}, {}", j, i);
381            return s;
382        }
383        // now s = true;
384        for (int k = 0; k < P.size(); k++) {
385            // System.out.println("i , k , j "+i+" "+k+" "+j); 
386            if (i != k && j != k) {
387                GenPolynomial<C> A = P.get(k);
388                ExpVector ek = A.leadingExpVector();
389                boolean m = eij.multipleOf(ek);
390                if (m) {
391                    if (k < i) {
392                        // System.out.println("k < i "+k+" "+i); 
393                        s = red.get(i).get(k) || red.get(j).get(k);
394                    } else if (i < k && k < j) {
395                        // System.out.println("i < k < j "+i+" "+k+" "+j); 
396                        s = red.get(k).get(i) || red.get(j).get(k);
397                    } else if (j < k) {
398                        //System.out.println("j < k "+j+" "+k); 
399                        s = red.get(k).get(i) || red.get(k).get(j);
400                    }
401                    //System.out.println("s."+k+" = " + s); 
402                    if (!s) {
403                        return s;
404                    }
405                }
406            }
407        }
408        return true;
409    }
410
411}