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