001/*
002 * $Id: OrderedMinPairlist.java 6013 2020-04-29 17:04:16Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.BitSet;
009import java.util.Iterator;
010import java.util.LinkedList;
011import java.util.Map;
012
013import org.apache.logging.log4j.LogManager;
014import org.apache.logging.log4j.Logger;
015
016import edu.jas.poly.ExpVector;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.poly.GenPolynomialRing;
019import edu.jas.structure.RingElem;
020
021
022/**
023 * Pair list management. The original Buchberger algorithm with criterions using
024 * early pair exclusion. Implemented using GenPolynomial, TreeMap and BitSet.
025 * @author Heinz Kredel
026 */
027
028public class OrderedMinPairlist<C extends RingElem<C>> extends OrderedPairlist<C> {
029
030
031    private static final Logger logger = LogManager.getLogger(OrderedMinPairlist.class);
032
033
034    /**
035     * Constructor.
036     */
037    public OrderedMinPairlist() {
038        super();
039    }
040
041
042    /**
043     * Constructor.
044     * @param r polynomial factory.
045     */
046    public OrderedMinPairlist(GenPolynomialRing<C> r) {
047        this(0, r);
048    }
049
050
051    /**
052     * Constructor.
053     * @param m number of module variables.
054     * @param r polynomial factory.
055     */
056    public OrderedMinPairlist(int m, GenPolynomialRing<C> r) {
057        super(m, r);
058    }
059
060
061    /**
062     * Create a new PairList.
063     * @param r polynomial ring.
064     */
065    @Override
066    public PairList<C> create(GenPolynomialRing<C> r) {
067        return new OrderedMinPairlist<C>(r);
068    }
069
070
071    /**
072     * Create a new PairList.
073     * @param m number of module variables.
074     * @param r polynomial ring.
075     */
076    @Override
077    public PairList<C> create(int m, GenPolynomialRing<C> r) {
078        return new OrderedMinPairlist<C>(m, r);
079    }
080
081
082    /**
083     * Put one Polynomial to the pairlist and reduction matrix.
084     * @param p polynomial.
085     * @return the index of the added polynomial.
086     */
087    @Override
088    public synchronized int put(GenPolynomial<C> p) {
089        putCount++;
090        if (oneInGB) {
091            return P.size() - 1;
092        }
093        ExpVector e = p.leadingExpVector();
094        int l = P.size();
095        BitSet redi = new BitSet();
096        redi.set(0, l); // [0..l-1] = true
097        red.add(redi);
098        P.add(p);
099        for (int j = 0; j < l; j++) {
100            GenPolynomial<C> pj = P.get(j);
101            ExpVector f = pj.leadingExpVector();
102            if (moduleVars > 0) {
103                if (!reduction.moduleCriterion(moduleVars, e, f)) {
104                    red.get(j).clear(l);
105                    continue; // skip pair
106                }
107            }
108            ExpVector g = e.lcm(f);
109            //System.out.println("g  = " + g);  
110            Pair<C> pair = new Pair<C>(pj, p, j, l);
111            boolean c = true;
112            if (useCriterion4) {
113                c = reduction.criterion4(pair.pi, pair.pj, g);
114            }
115            //System.out.println("c4  = " + c);  
116            if (c) {
117                c = criterion3(j, l, g);
118                //System.out.println("c3  = " + c); 
119            }
120            if (!c) { // skip pair
121                red.get(j).clear(l);
122                //System.out.println("c_skip = " + g); 
123                continue;
124            }
125            //multiple pairs under same keys -> list of pairs
126            LinkedList<Pair<C>> xl = pairlist.get(g);
127            if (xl == null) {
128                xl = new LinkedList<Pair<C>>();
129            }
130            //xl.addLast( pair ); // first or last ?
131            xl.addFirst(pair); // first or last ? better for d- e-GBs
132            pairlist.put(g, xl);
133        }
134        // System.out.println("pairlist.keys@put = " + pairlist.keySet() );  
135        return P.size() - 1;
136    }
137
138
139    /**
140     * Remove the next required pair from the pairlist and reduction matrix.
141     * Appy the criterions 3 and 4 to see if the S-polynomial is required.
142     * @return the next pair if one exists, otherwise null.
143     */
144    @Override
145    public synchronized Pair<C> removeNext() {
146        if (oneInGB) {
147            return null;
148        }
149        Iterator<Map.Entry<ExpVector, LinkedList<Pair<C>>>> ip = pairlist.entrySet().iterator();
150
151        Pair<C> pair = null;
152        boolean c = false;
153        int i, j;
154
155        while (!c && ip.hasNext()) {
156            Map.Entry<ExpVector, LinkedList<Pair<C>>> me = ip.next();
157            ExpVector g = me.getKey();
158            LinkedList<Pair<C>> xl = me.getValue();
159            if (logger.isInfoEnabled()) {
160                logger.info("g  = " + g);
161            }
162            pair = null;
163            while (!c && xl.size() > 0) {
164                pair = xl.removeFirst();
165                // xl is also modified in pairlist 
166                i = pair.i;
167                j = pair.j;
168                // System.out.println("pair(" + j + "," +i+") ");
169                if (!red.get(j).get(i)) {
170                    System.out.println("c_y = " + g); // + ", " + red.get(j).get(i)); 
171                    continue;
172                }
173                c = true;
174                if (useCriterion4) {
175                    c = reduction.criterion4(pair.pi, pair.pj, g);
176                }
177                //System.out.println("c4_x = " + c);  
178                if (c) {
179                    c = criterion3(i, j, g);
180                    //System.out.println("c3_x = " + c); 
181                }
182                if (!c) {
183                    //System.out.println("c_x = " + g); 
184                }
185                red.get(j).clear(i); // set(i,false) jdk1.4
186            }
187            if (xl.size() == 0) {
188                ip.remove();
189                // = pairlist.remove( g );
190            }
191        }
192        if (!c) {
193            pair = null;
194        } else {
195            pair.maxIndex(P.size() - 1);
196            remCount++; // count only real pairs
197            if (logger.isDebugEnabled()) {
198                logger.info("pair(" + pair.j + "," + pair.i + ")");
199            }
200        }
201        return pair;
202    }
203
204
205    /**
206     * GB criterium 3.
207     * @return true if the S-polynomial(i,j) is required.
208     */
209    @Override
210    public boolean criterion3(int i, int j, ExpVector eij) {
211        // assert i < j;
212        boolean s;
213        s = red.get(j).get(i);
214        if (!s) {
215            logger.warn("c3.s false for " + j + " " + i);
216            return s;
217        }
218        s = true;
219        boolean m;
220        GenPolynomial<C> A;
221        ExpVector ek;
222        for (int k = 0; k < P.size(); k++) {
223            A = P.get(k);
224            ek = A.leadingExpVector();
225            m = eij.multipleOf(ek) && eij.compareTo(ek) != 0;
226            if (m) {
227                if (k < i) {
228                    // System.out.println("k < i "+k+" "+i); 
229                    s = red.get(i).get(k) || red.get(j).get(k);
230                }
231                if (i < k && k < j) {
232                    // System.out.println("i < k < j "+i+" "+k+" "+j); 
233                    s = red.get(k).get(i) || red.get(j).get(k);
234                }
235                if (j < k) {
236                    //System.out.println("j < k "+j+" "+k); 
237                    s = red.get(k).get(i) || red.get(k).get(j);
238                }
239                //System.out.println("s."+k+" = " + s); 
240                if (!s)
241                    return s;
242            }
243        }
244        return true;
245    }
246
247}