001/*
002 * $Id: OrderedSyzPairlist.java 4249 2012-10-14 10:13:04Z 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            LinkedList<Pair<C>> ignored = npl.remove(ei);
188        }
189        // skip by criterion 4:
190        if (useCriterion4) {
191            es = new ArrayList<ExpVector>(npl.size());
192            for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : npl.entrySet()) {
193                ExpVector ei = me.getKey();
194                LinkedList<Pair<C>> exl = me.getValue(); //npl.get( ei );
195                //System.out.println("exl = " + exl ); 
196                boolean c = true;
197                for (Pair<C> pair : exl) {
198                    c = c && reduction.criterion4(pair.pi, pair.pj, pair.e);
199                }
200                if (c) {
201                    if (exl.size() > 1) {
202                        Pair<C> pair = exl.getFirst(); // or exl.getLast();
203                        exl.clear();
204                        exl.add(pair);
205                        //npl.put(ei,exl);
206                    }
207                } else {
208                    if (!es.contains(ei)) {
209                        es.add(ei);
210                    }
211                }
212            }
213            //System.out.println("npl.skip c4  = " + es);
214            for (ExpVector ei : es) {
215                LinkedList<Pair<C>> ignored = npl.remove(ei);
216            }
217        }
218        // add to existing pairlist:
219        //System.out.println("npl.put new  = " + npl.keySet() );  
220        for (Map.Entry<ExpVector, LinkedList<Pair<C>>> me : npl.entrySet()) {
221            ExpVector ei = me.getKey();
222            LinkedList<Pair<C>> exl = me.getValue(); //npl.get( ei );
223            for (Pair<C> pair : exl) {
224                red.get(pair.j).set(pair.i);
225            }
226            LinkedList<Pair<C>> ex = pairlist.get(ei); // wrong in findbugs
227            if (ex != null) {
228                exl.addAll(ex); // add new pairs first 
229                ex = exl;
230                //ex.addAll(exl); // add old pairs first
231            } else {
232                ex = exl;
233            }
234            pairlist.put(ei, ex); // replace ex
235        }
236        return P.size() - 1;
237    }
238
239
240    /**
241     * Remove the next required pair from the pairlist and reduction matrix.
242     * Appy the criterions 3 and 4 to see if the S-polynomial is required.
243     * @return the next pair if one exists, otherwise null.
244     */
245    @Override
246    public synchronized Pair<C> removeNext() {
247        if (oneInGB) {
248            return null;
249        }
250        Iterator<Map.Entry<ExpVector, LinkedList<Pair<C>>>> ip = pairlist.entrySet().iterator();
251        Pair<C> pair = null;
252        //boolean c = false;
253        int i, j;
254        while (ip.hasNext()) {
255            Map.Entry<ExpVector, LinkedList<Pair<C>>> me = ip.next();
256            ExpVector g = me.getKey();
257            LinkedList<Pair<C>> xl = me.getValue();
258            if (logger.isInfoEnabled())
259                logger.info("g  = " + g);
260            pair = null;
261            while (xl.size() > 0) {
262                pair = xl.removeFirst(); // xl is also modified in pairlist 
263                i = pair.i;
264                j = pair.j;
265                //System.out.println("pair.remove = " + pair );
266                if (!red.get(j).get(i)) { // should not happen
267                    System.out.println("c_red.get(" + j + ").get(" + i + ") = " + g);
268                    pair = null;
269                    continue;
270                }
271                red.get(j).clear(i);
272                break;
273            }
274            if (xl.size() == 0) {
275                ip.remove(); // = pairlist.remove( g );
276            }
277            if (pair != null) {
278                break;
279            }
280        }
281        if ( pair != null ) {
282            remCount++; // count only real pairs
283            if ( logger.isDebugEnabled() ) {
284                logger.info("pair(" + pair.j + "," + pair.i + ")");
285            }
286        }
287        return pair;
288    }
289
290
291    /**
292     * GB criterium 3.
293     * @return true if the S-polynomial(i,j) is required.
294     */
295    @Override
296    public boolean criterion3(int i, int j, ExpVector eij) {
297        throw new UnsupportedOperationException("not used in " + this.getClass().getName());
298    }
299
300}