Source code

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