Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.ps;
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.TreeMap;
015
016import org.apache.logging.log4j.Logger;
017import org.apache.logging.log4j.LogManager; 
018
019import edu.jas.poly.ExpVector;
020import edu.jas.structure.RingElem;
021
022
023/**
024 * Pair list management. Implemented using MultiVarPowerSeries, TreeMap and
025 * BitSet.
026 * @author Heinz Kredel
027 */
028
029public class OrderedPairlist<C extends RingElem<C>> {
030
031
032    protected final ArrayList<MultiVarPowerSeries<C>> P;
033
034
035    protected final TreeMap<ExpVector, LinkedList<Pair<C>>> pairlist;
036
037
038    protected final ArrayList<BitSet> red;
039
040
041    protected final MultiVarPowerSeriesRing<C> ring;
042
043
044    protected final ReductionSeq<C> reduction;
045
046
047    protected boolean oneInGB = false;
048
049
050    protected boolean useCriterion4 = true;
051
052
053    protected boolean useCriterion3 = 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 = LogManager.getLogger(OrderedPairlist.class);
066
067
068    /**
069     * Constructor for OrderedPairlist.
070     * @param r power series factory.
071     */
072    public OrderedPairlist(MultiVarPowerSeriesRing<C> r) {
073        this(0, r);
074    }
075
076
077    /**
078     * Constructor for OrderedPairlist.
079     * @param m number of module variables.
080     * @param r power series factory.
081     */
082    public OrderedPairlist(int m, MultiVarPowerSeriesRing<C> r) {
083        moduleVars = m;
084        ring = r;
085        P = new ArrayList<MultiVarPowerSeries<C>>();
086        pairlist = new TreeMap<ExpVector, LinkedList<Pair<C>>>(ring.polyRing().tord.getAscendComparator());
087        //pairlist = new TreeMap<ExpVector, LinkedList<Pair<C>>>(ring.polyRing().tord.getDescendComparator());
088        red = new ArrayList<BitSet>();
089        putCount = 0;
090        remCount = 0;
091        reduction = new ReductionSeq<C>();
092    }
093
094
095    /**
096     * toString.
097     */
098    @Override
099    public String toString() {
100        StringBuffer s = new StringBuffer("OrderedPairlist(");
101        //s.append("ps="+P.size());
102        s.append("#put=" + putCount);
103        s.append(", #rem=" + remCount);
104        if (pairlist.size() != 0) {
105            s.append(", size=" + pairlist.size());
106        }
107        s.append(")");
108        return s.toString();
109    }
110
111
112    /**
113     * Put one power Series to the pairlist and reduction matrix.
114     * @param p power series.
115     * @return the index of the added power series.
116     */
117    public synchronized int put(MultiVarPowerSeries<C> p) {
118        putCount++;
119        if (oneInGB) {
120            return P.size() - 1;
121        }
122        ExpVector e = p.orderExpVector();
123        int l = P.size();
124        for (int j = 0; j < l; j++) {
125            MultiVarPowerSeries<C> pj = P.get(j);
126            ExpVector f = pj.orderExpVector();
127            if (moduleVars > 0) {
128                if (!reduction.moduleCriterion(moduleVars, e, f)) {
129                    continue; // skip pair
130                }
131            }
132            ExpVector g = e.lcm(f);
133            Pair<C> pair = new Pair<C>(pj, p, j, l);
134            // redi = (BitSet)red.get(j);
135            ///if ( j < l ) redi.set( l );
136            // System.out.println("bitset."+j+" = " + redi );  
137
138            //multiple pairs under same keys -> list of pairs
139            LinkedList<Pair<C>> xl = pairlist.get(g);
140            if (xl == null) {
141                xl = new LinkedList<Pair<C>>();
142            }
143            //xl.addLast( pair ); // first or last ?
144            xl.addFirst(pair); // first or last ? better for d- e-GBs
145            pairlist.put(g, xl);
146        }
147        // System.out.println("pairlist.keys@put = " + pairlist.keySet() );  
148        P.add(p);
149        BitSet redi = new BitSet();
150        redi.set(0, l); // jdk 1.4
151        red.add(redi);
152        return P.size() - 1;
153    }
154
155
156    /**
157     * Put all power series in F to the pairlist and reduction matrix.
158     * @param F power series list.
159     * @return the index of the last added power series.
160     */
161    public int put(List<MultiVarPowerSeries<C>> F) {
162        int i = 0;
163        for (MultiVarPowerSeries<C> p : F) {
164            i = put(p);
165        }
166        return i;
167    }
168
169
170    /**
171     * Remove the next required pair from the pairlist and reduction matrix.
172     * Apply the criterions 3 and 4 to see if the S-power-series is required.
173     * @return the next pair if one exists, otherwise null.
174     */
175    public synchronized Pair<C> removeNext() {
176        if (oneInGB) {
177            return null;
178        }
179        Iterator<Map.Entry<ExpVector, LinkedList<Pair<C>>>> ip = pairlist.entrySet().iterator();
180
181        Pair<C> pair = null;
182        boolean c = false;
183        int i, j;
184
185        while (!c && ip.hasNext()) {
186            Map.Entry<ExpVector, LinkedList<Pair<C>>> me = ip.next();
187            ExpVector g = me.getKey();
188            LinkedList<Pair<C>> xl = me.getValue();
189            logger.info("g  = {}", g);
190            pair = null;
191            while (!c && xl.size() > 0) {
192                pair = xl.removeFirst();
193                // xl is also modified in pairlist 
194                i = pair.i;
195                j = pair.j;
196                // System.out.println("pair(" + j + "," +i+") ");
197                c = true;
198                if (useCriterion4) {
199                    c = reduction.criterion4(pair.pi, pair.pj, g);
200                }
201                //System.out.println("c4  = " + c);  
202                if (c && useCriterion3) {
203                    c = criterion3(i, j, g);
204                    //System.out.println("c3  = " + c); 
205                }
206                red.get(j).clear(i); // set(i,false) jdk1.4
207            }
208            if (xl.size() == 0)
209                ip.remove();
210            // = pairlist.remove( g );
211        }
212        if (!c) {
213            pair = null;
214        } else {
215            remCount++; // count only real pairs
216        }
217        return pair;
218    }
219
220
221    /**
222     * Test if there is possibly a pair in the list.
223     * @return true if a next pair could exist, otherwise false.
224     */
225    public synchronized boolean hasNext() {
226        return pairlist.size() > 0;
227    }
228
229
230    /**
231     * Get the list of power series.
232     * @return the power series list.
233     */
234    public List<MultiVarPowerSeries<C>> getList() {
235        return P;
236    }
237
238
239    /**
240     * Get the number of power series put to the pairlist.
241     * @return the number of calls to put.
242     */
243    public synchronized int putCount() {
244        return putCount;
245    }
246
247
248    /**
249     * Get the number of required pairs removed from the pairlist.
250     * @return the number of non null pairs delivered.
251     */
252    public synchronized int remCount() {
253        return remCount;
254    }
255
256
257    /**
258     * Put to ONE-power-series to the pairlist.
259     * @param one power series. (no more required)
260     * @return the index of the last power series.
261     */
262    public synchronized int putOne(MultiVarPowerSeries<C> one) {
263        putCount++;
264        if (one == null) {
265            return P.size() - 1;
266        }
267        if (!one.isONE()) {
268            return P.size() - 1;
269        }
270        return putOne();
271    }
272
273
274    /**
275     * Put the ONE-power-series to the pairlist.
276     * @return the index of the last power-series.
277     */
278    public synchronized int putOne() {
279        oneInGB = true;
280        pairlist.clear();
281        P.clear();
282        P.add(ring.getONE());
283        red.clear();
284        return P.size() - 1;
285    }
286
287
288    /**
289     * GB criterion 3.
290     * @return true if the S-power-series(i,j) is required.
291     */
292    public boolean criterion3(int i, int j, ExpVector eij) {
293        // assert i < j;
294        boolean s = red.get(j).get(i);
295        if (!s) {
296            logger.warn("c3.s false for {} {}", j, i);
297            return s;
298        }
299        // now s = true;
300        for (int k = 0; k < P.size(); k++) {
301            MultiVarPowerSeries<C> A = P.get(k);
302            ExpVector ek = A.orderExpVector();
303            boolean m = eij.multipleOf(ek);
304            if (m) {
305                if (k < i) {
306                    // System.out.println("k < i "+k+" "+i); 
307                    s = red.get(i).get(k) || red.get(j).get(k);
308                } else if (i < k && k < j) {
309                    // System.out.println("i < k < j "+i+" "+k+" "+j); 
310                    s = red.get(k).get(i) || red.get(j).get(k);
311                } else if (j < k) {
312                    //System.out.println("j < k "+j+" "+k); 
313                    s = red.get(k).get(i) || red.get(k).get(j);
314                }
315                //System.out.println("s."+k+" = " + s); 
316                if (!s) {
317                    return s;
318                }
319            }
320        }
321        return true;
322    }
323
324}