Source code

001/*
002 * $Id: OrderedPairlist.java 4975 2014-10-23 21:03:46Z kredel $
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.log4j.Logger;
017
018import edu.jas.poly.ExpVector;
019import edu.jas.structure.RingElem;
020
021
022/**
023 * Pair list management. Implemented using MultiVarPowerSeries, TreeMap and
024 * BitSet.
025 * @author Heinz Kredel
026 */
027
028public class OrderedPairlist<C extends RingElem<C>> {
029
030
031    protected final ArrayList<MultiVarPowerSeries<C>> P;
032
033
034    protected final TreeMap<ExpVector, LinkedList<Pair<C>>> pairlist;
035
036
037    protected final ArrayList<BitSet> red;
038
039
040    protected final MultiVarPowerSeriesRing<C> ring;
041
042
043    protected final ReductionSeq<C> reduction;
044
045
046    protected boolean oneInGB = false;
047
048
049    protected boolean useCriterion4 = true;
050
051
052    protected boolean useCriterion3 = true;
053
054
055    protected int putCount;
056
057
058    protected int remCount;
059
060
061    protected final int moduleVars;
062
063
064    private static final Logger logger = Logger.getLogger(OrderedPairlist.class);
065
066
067    /**
068     * Constructor for OrderedPairlist.
069     * @param r power series factory.
070     */
071    public OrderedPairlist(MultiVarPowerSeriesRing<C> r) {
072        this(0, r);
073    }
074
075
076    /**
077     * Constructor for OrderedPairlist.
078     * @param m number of module variables.
079     * @param r power series factory.
080     */
081    public OrderedPairlist(int m, MultiVarPowerSeriesRing<C> r) {
082        moduleVars = m;
083        ring = r;
084        P = new ArrayList<MultiVarPowerSeries<C>>();
085        pairlist = new TreeMap<ExpVector, LinkedList<Pair<C>>>(ring.polyRing().tord.getAscendComparator());
086        //pairlist = new TreeMap<ExpVector, LinkedList<Pair<C>>>(ring.polyRing().tord.getDescendComparator());
087        red = new ArrayList<BitSet>();
088        putCount = 0;
089        remCount = 0;
090        reduction = new ReductionSeq<C>();
091    }
092
093
094    /**
095     * toString.
096     */
097    @Override
098    public String toString() {
099        StringBuffer s = new StringBuffer("OrderedPairlist(");
100        //s.append("ps="+P.size());
101        s.append("#put=" + putCount);
102        s.append(", #rem=" + remCount);
103        if (pairlist.size() != 0) {
104            s.append(", size=" + pairlist.size());
105        }
106        s.append(")");
107        return s.toString();
108    }
109
110
111    /**
112     * Put one power Series to the pairlist and reduction matrix.
113     * @param p power series.
114     * @return the index of the added power series.
115     */
116    public synchronized int put(MultiVarPowerSeries<C> p) {
117        putCount++;
118        if (oneInGB) {
119            return P.size() - 1;
120        }
121        ExpVector e = p.orderExpVector();
122        int l = P.size();
123        for (int j = 0; j < l; j++) {
124            MultiVarPowerSeries<C> pj = P.get(j);
125            ExpVector f = pj.orderExpVector();
126            if (moduleVars > 0) {
127                if (!reduction.moduleCriterion(moduleVars, e, f)) {
128                    continue; // skip pair
129                }
130            }
131            ExpVector g = e.lcm(f);
132            Pair<C> pair = new Pair<C>(pj, p, j, l);
133            // redi = (BitSet)red.get(j);
134            ///if ( j < l ) redi.set( l );
135            // System.out.println("bitset."+j+" = " + redi );  
136
137            //multiple pairs under same keys -> list of pairs
138            LinkedList<Pair<C>> xl = pairlist.get(g);
139            if (xl == null) {
140                xl = new LinkedList<Pair<C>>();
141            }
142            //xl.addLast( pair ); // first or last ?
143            xl.addFirst(pair); // first or last ? better for d- e-GBs
144            pairlist.put(g, xl);
145        }
146        // System.out.println("pairlist.keys@put = " + pairlist.keySet() );  
147        P.add(p);
148        BitSet redi = new BitSet();
149        redi.set(0, l); // jdk 1.4
150        red.add(redi);
151        return P.size() - 1;
152    }
153
154
155    /**
156     * Put all power series in F to the pairlist and reduction matrix.
157     * @param F power series list.
158     * @return the index of the last added power series.
159     */
160    public int put(List<MultiVarPowerSeries<C>> F) {
161        int i = 0;
162        for (MultiVarPowerSeries<C> p : F) {
163            i = put(p);
164        }
165        return i;
166    }
167
168
169    /**
170     * Remove the next required pair from the pairlist and reduction matrix.
171     * Apply the criterions 3 and 4 to see if the S-power-series is required.
172     * @return the next pair if one exists, otherwise null.
173     */
174    public synchronized Pair<C> removeNext() {
175        if (oneInGB) {
176            return null;
177        }
178        Iterator<Map.Entry<ExpVector, LinkedList<Pair<C>>>> ip = pairlist.entrySet().iterator();
179
180        Pair<C> pair = null;
181        boolean c = false;
182        int i, j;
183
184        while (!c && ip.hasNext()) {
185            Map.Entry<ExpVector, LinkedList<Pair<C>>> me = ip.next();
186            ExpVector g = me.getKey();
187            LinkedList<Pair<C>> xl = me.getValue();
188            if (logger.isInfoEnabled())
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}