001/*
002 * $Id: OrderedSyzPairlist.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. For the Buchberger algorithm following the syzygy
028 * criterions by Gebauer & Möller. Implemented using GenPolynomial,
029 * TreeMap and BitSet.
030 * @author Heinz Kredel
031 */
032
033public class OrderedSyzPairlist<C extends RingElem<C>> extends OrderedPairlist<C> {
034
035
036    private static final Logger logger = LogManager.getLogger(OrderedSyzPairlist.class);
037
038
039    /**
040     * Constructor.
041     */
042    public OrderedSyzPairlist() {
043        super();
044    }
045
046
047    /**
048     * Constructor.
049     * @param r polynomial factory.
050     */
051    public OrderedSyzPairlist(GenPolynomialRing<C> r) {
052        this(0, r);
053    }
054
055
056    /**
057     * Constructor.
058     * @param m number of module variables.
059     * @param r polynomial factory.
060     */
061    public OrderedSyzPairlist(int m, GenPolynomialRing<C> r) {
062        super(m, r);
063    }
064
065
066    /**
067     * Create a new PairList.
068     * @param r polynomial ring.
069     */
070    @Override
071    public PairList<C> create(GenPolynomialRing<C> r) {
072        return new OrderedSyzPairlist<C>(r);
073    }
074
075
076    /**
077     * Create a new PairList.
078     * @param m number of module variables.
079     * @param r polynomial ring.
080     */
081    @Override
082    public PairList<C> create(int m, GenPolynomialRing<C> r) {
083        return new OrderedSyzPairlist<C>(m, r);
084    }
085
086
087    /**
088     * Put one Polynomial to the pairlist and reduction matrix. Removes all
089     * unnecessary pairs identified by the syzygy criterion and criterion 4.
090     * @param p polynomial.
091     * @return the index of the added polynomial.
092     */
093    @Override
094    public synchronized int put(GenPolynomial<C> p) {
095        putCount++;
096        if (oneInGB) {
097            return P.size() - 1;
098        }
099        ExpVector e = p.leadingExpVector();
100        int ps = P.size();
101        BitSet redi = new BitSet(); // all zeros
102        //redi.set( 0, ps ); // [0..ps-1] = true, i.e. all ones
103        red.add(redi);
104        P.add(p);
105        // remove from existing pairs:
106        List<ExpVector> es = new ArrayList<ExpVector>();
107        for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : pairlist.entrySet()) {
108            ExpVector g = me.getKey();
109            if (moduleVars > 0) {
110                if (!reduction.moduleCriterion(moduleVars, e, g)) {
111                    continue; // skip pair
112                }
113            }
114            ExpVector ge = g.lcm(e);
115            LinkedList<Pair<C>> ll = me.getValue();
116            if (g.compareTo(ge) == 0) {
117                LinkedList<Pair<C>> lle = new LinkedList<Pair<C>>();
118                for (Pair<C> pair : ll) {
119                    ExpVector eil = pair.pi.leadingExpVector().lcm(e);
120                    if (g.compareTo(eil) == 0) {
121                        continue;
122                    }
123                    ExpVector ejl = pair.pj.leadingExpVector().lcm(e);
124                    if (g.compareTo(ejl) == 0) {
125                        continue;
126                    }
127                    // g == ge && g != eil && g != ejl  
128                    red.get(pair.j).clear(pair.i);
129                    lle.add(pair);
130                }
131                if (lle.size() > 0) {
132                    for (Pair<C> pair : lle) {
133                        ll.remove(pair);
134                    }
135                    if (!es.contains(g)) {
136                        es.add(g);
137                    }
138                }
139            }
140        }
141        for (ExpVector ei : es) {
142            LinkedList<Pair<C>> ll = pairlist.get(ei);
143            if (ll != null && ll.size() == 0) {
144                ll = pairlist.remove(ei);
145            }
146        }
147        // generate new pairs:
148        SortedMap<ExpVector, LinkedList<Pair<C>>> npl = new TreeMap<ExpVector, LinkedList<Pair<C>>>(
149                        ring.tord.getAscendComparator());
150        for (int j = 0; j < ps; j++) {
151            GenPolynomial<C> pj = P.get(j);
152            ExpVector f = pj.leadingExpVector();
153            if (moduleVars > 0) {
154                if (!reduction.moduleCriterion(moduleVars, e, f)) {
155                    //red.get(j).clear(l); 
156                    continue; // skip pair
157                }
158            }
159            ExpVector g = e.lcm(f);
160            Pair<C> pair = new Pair<C>(pj, p, j, ps);
161            //System.out.println("pair.new      = " + pair);
162            //multiple pairs under same keys -> list of pairs
163            LinkedList<Pair<C>> xl = npl.get(g);
164            if (xl == null) {
165                xl = new LinkedList<Pair<C>>();
166            }
167            //xl.addLast( pair ); // first or last ?
168            xl.addFirst(pair); // first or last ? better for d- e-GBs
169            npl.put(g, xl);
170        }
171        //System.out.println("npl.new      = " + npl.keySet());
172        // skip by divisibility:
173        es = new ArrayList<ExpVector>(npl.size());
174        for (ExpVector eil : npl.keySet()) {
175            for (ExpVector ejl : npl.keySet()) {
176                if (eil.compareTo(ejl) == 0) {
177                    continue;
178                }
179                if (eil.multipleOf(ejl)) {
180                    if (!es.contains(eil)) {
181                        es.add(eil);
182                    }
183                }
184            }
185        }
186        //System.out.println("npl.skip div = " + es);
187        for (ExpVector ei : es) {
188            @SuppressWarnings("unused")
189            LinkedList<Pair<C>> ignored = npl.remove(ei);
190        }
191        // skip by criterion 4:
192        if (useCriterion4) {
193            es = new ArrayList<ExpVector>(npl.size());
194            for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : npl.entrySet()) {
195                ExpVector ei = me.getKey();
196                LinkedList<Pair<C>> exl = me.getValue(); //npl.get( ei );
197                //System.out.println("exl = " + exl ); 
198                boolean c = true;
199                for (Pair<C> pair : exl) {
200                    c = c && reduction.criterion4(pair.pi, pair.pj, pair.e);
201                }
202                if (c) {
203                    if (exl.size() > 1) {
204                        Pair<C> pair = exl.getFirst(); // or exl.getLast();
205                        exl.clear();
206                        exl.add(pair);
207                        //npl.put(ei,exl);
208                    }
209                } else {
210                    if (!es.contains(ei)) {
211                        es.add(ei);
212                    }
213                }
214            }
215            //System.out.println("npl.skip c4  = " + es);
216            for (ExpVector ei : es) {
217                @SuppressWarnings("unused")
218                LinkedList<Pair<C>> ignored = npl.remove(ei);
219            }
220        }
221        // add to existing pairlist:
222        //System.out.println("npl.put new  = " + npl.keySet() );  
223        for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : npl.entrySet()) {
224            ExpVector ei = me.getKey();
225            LinkedList<Pair<C>> exl = me.getValue(); //npl.get( ei );
226            for (Pair<C> pair : exl) {
227                red.get(pair.j).set(pair.i);
228            }
229            LinkedList<Pair<C>> ex = pairlist.get(ei); // wrong in findbugs
230            if (ex != null) {
231                exl.addAll(ex); // add new pairs first 
232                ex = exl;
233                //ex.addAll(exl); // add old pairs first
234            } else {
235                ex = exl;
236            }
237            pairlist.put(ei, ex); // replace ex
238        }
239        return P.size() - 1;
240    }
241
242
243    /**
244     * Remove the next required pair from the pairlist and reduction matrix.
245     * Appy the criterions 3 and 4 to see if the S-polynomial is required.
246     * @return the next pair if one exists, otherwise null.
247     */
248    @Override
249    public synchronized Pair<C> removeNext() {
250        if (oneInGB) {
251            return null;
252        }
253        Iterator<Map.Entry<ExpVector, LinkedList<Pair<C>>>> ip = pairlist.entrySet().iterator();
254        Pair<C> pair = null;
255        //boolean c = false;
256        int i, j;
257        while (ip.hasNext()) {
258            Map.Entry<ExpVector, LinkedList<Pair<C>>> me = ip.next();
259            ExpVector g = me.getKey();
260            LinkedList<Pair<C>> xl = me.getValue();
261            if (logger.isInfoEnabled())
262                logger.info("g  = " + g);
263            pair = null;
264            while (xl.size() > 0) {
265                pair = xl.removeFirst(); // xl is also modified in pairlist 
266                i = pair.i;
267                j = pair.j;
268                //System.out.println("pair.remove = " + pair );
269                if (!red.get(j).get(i)) { // should not happen
270                    System.out.println("c_red.get(" + j + ").get(" + i + ") = " + g);
271                    pair = null;
272                    continue;
273                }
274                red.get(j).clear(i);
275                break;
276            }
277            if (xl.size() == 0) {
278                ip.remove(); // = pairlist.remove( g );
279            }
280            if (pair != null) {
281                break;
282            }
283        }
284        if (pair != null) {
285            pair.maxIndex(P.size() - 1);
286            remCount++; // count only real pairs
287            if (logger.isDebugEnabled()) {
288                logger.info("pair(" + pair.j + "," + pair.i + ")");
289            }
290        }
291        return pair;
292    }
293
294
295    /**
296     * GB criterium 3.
297     * @return true if the S-polynomial(i,j) is required.
298     */
299    @Override
300    public boolean criterion3(int i, int j, ExpVector eij) {
301        throw new UnsupportedOperationException("not used in " + this.getClass().getName());
302    }
303
304}