Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.application;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.BitSet;
011import java.util.Iterator;
012import java.util.LinkedList;
013import java.util.List;
014import java.util.Map;
015import java.util.SortedMap;
016import java.util.TreeMap;
017
018import org.apache.logging.log4j.LogManager;
019import org.apache.logging.log4j.Logger;
020
021import edu.jas.poly.ExpVector;
022import edu.jas.poly.GenPolynomial;
023import edu.jas.poly.GenPolynomialRing;
024import edu.jas.poly.GenSolvablePolynomialRing;
025import edu.jas.structure.GcdRingElem;
026import edu.jas.structure.RingFactory;
027
028
029/**
030 * Pair list management. Implemented for ColorPolynomials using TreeMap and
031 * BitSet.
032 * @author Heinz Kredel
033 */
034
035public class OrderedCPairlist<C extends GcdRingElem<C>> implements Serializable {
036
037
038    private static final Logger logger = LogManager.getLogger(OrderedCPairlist.class);
039
040
041    protected final GenPolynomialRing<GenPolynomial<C>> ring;
042
043
044    protected final List<ColorPolynomial<C>> P;
045
046
047    protected final SortedMap<ExpVector, LinkedList<CPair<C>>> pairlist;
048
049
050    protected final List<BitSet> red;
051
052
053    protected final CReductionSeq<C> reduction;
054
055
056    protected boolean oneInGB = false;
057
058
059    protected boolean useCriterion4 = false; // unused
060
061
062    protected int putCount;
063
064
065    protected int remCount;
066
067
068    protected final int moduleVars; // unused
069
070
071    /**
072     * Constructor for OrderedPairlist.
073     * @param r polynomial factory.
074     */
075    public OrderedCPairlist(GenPolynomialRing<GenPolynomial<C>> r) {
076        this(0, r);
077    }
078
079
080    /**
081     * Constructor for OrderedPairlist.
082     * @param m number of module variables.
083     * @param r polynomial factory.
084     */
085    public OrderedCPairlist(int m, GenPolynomialRing<GenPolynomial<C>> r) {
086        moduleVars = m;
087        ring = r;
088        P = new ArrayList<ColorPolynomial<C>>();
089        pairlist = new TreeMap<ExpVector, LinkedList<CPair<C>>>(ring.tord.getAscendComparator());
090        // pairlist = new TreeMap( to.getSugarComparator() );
091        red = new ArrayList<BitSet>();
092        putCount = 0;
093        remCount = 0;
094        if (ring instanceof GenSolvablePolynomialRing) {
095            useCriterion4 = false;
096        }
097        RingFactory<GenPolynomial<C>> rf = ring.coFac;
098        GenPolynomialRing<C> cf = (GenPolynomialRing<C>) rf;
099        reduction = new CReductionSeq<C>(cf.coFac);
100    }
101
102
103    /**
104     * Internal constructor for OrderedPairlist. Used to clone this pair list.
105     * @param m number of module variables.
106     * @param r polynomial factory.
107     * @param P list of color polynomials.
108     * @param pl critical pair list.
109     * @param red reduction matrix.
110     * @param cred color polynomial reduction engine.
111     * @param pc put count.
112     * @param rc remove count.
113     */
114    private OrderedCPairlist(int m, GenPolynomialRing<GenPolynomial<C>> r, List<ColorPolynomial<C>> P,
115                    SortedMap<ExpVector, LinkedList<CPair<C>>> pl, List<BitSet> red, CReductionSeq<C> cred,
116                    int pc, int rc) {
117        moduleVars = m;
118        this.ring = r;
119        this.P = P;
120        pairlist = pl;
121        this.red = red;
122        reduction = cred;
123        putCount = pc;
124        remCount = rc;
125    }
126
127
128    /**
129     * Clone this OrderedPairlist.
130     * @return a 2 level clone of this.
131     */
132    public synchronized OrderedCPairlist<C> copy() {
133        return new OrderedCPairlist<C>(moduleVars, ring, new ArrayList<ColorPolynomial<C>>(P),
134                        clonePairlist(), cloneBitSet(), reduction, putCount, remCount);
135    }
136
137
138    /**
139     * Clone this pairlist.
140     * @return a 2 level clone of this pairlist.
141     */
142    private SortedMap<ExpVector, LinkedList<CPair<C>>> clonePairlist() {
143        SortedMap<ExpVector, LinkedList<CPair<C>>> pl = new TreeMap<ExpVector, LinkedList<CPair<C>>>(
144                        ring.tord.getAscendComparator());
145        for (Map.Entry<ExpVector, LinkedList<CPair<C>>> m : pairlist.entrySet()) {
146            ExpVector e = m.getKey();
147            LinkedList<CPair<C>> l = m.getValue();
148            l = new LinkedList<CPair<C>>(l);
149            pl.put(e, l);
150        }
151        return pl;
152    }
153
154
155    /**
156     * Count remaining Pairs.
157     * @return number of pairs remaining in this pairlist.
158     */
159    public int pairCount() {
160        int c = 0;
161        for (Map.Entry<ExpVector, LinkedList<CPair<C>>> m : pairlist.entrySet()) {
162            LinkedList<CPair<C>> l = m.getValue();
163            c += l.size();
164        }
165        return c;
166    }
167
168
169    /**
170     * Clone this reduction BitSet.
171     * @return a 2 level clone of this reduction BitSet.
172     */
173    private List<BitSet> cloneBitSet() {
174        List<BitSet> r = new ArrayList<BitSet>(this.red.size());
175        for (BitSet b : red) {
176            BitSet n = (BitSet) b.clone();
177            r.add(n);
178        }
179        return r;
180    }
181
182
183    /**
184     * bitCount.
185     * @return number of bits set in this bitset.
186     */
187    public int bitCount() {
188        int c = 0;
189        for (BitSet b : red) {
190            c += b.cardinality();
191        }
192        return c;
193    }
194
195
196    /**
197     * toString.
198     * @return counters of this.
199     */
200    @Override
201    public String toString() {
202        int p = pairCount();
203        int b = bitCount();
204        if (p != b) {
205            return "OrderedCPairlist( pairCount=" + p + ", bitCount=" + b + ", putCount=" + putCount
206                            + ", remCount=" + remCount + " )";
207        }
208        return "OrderedCPairlist( pairCount=" + p + ", putCount=" + putCount + ", remCount=" + remCount
209                        + " )";
210    }
211
212
213    /**
214     * Equals.
215     * @param ob an Object.
216     * @return true if this is equal to o, else false.
217     */
218    @Override
219    @SuppressWarnings("unchecked")
220    public boolean equals(Object ob) {
221        OrderedCPairlist<C> c = null;
222        try {
223            c = (OrderedCPairlist<C>) ob;
224        } catch (ClassCastException e) {
225            return false;
226        }
227        if (c == null) {
228            return false;
229        }
230        boolean t = getList().equals(c.getList());
231        if (!t) {
232            return t;
233        }
234        t = pairCount() == c.pairCount();
235        if (!t) {
236            return t;
237        }
238        return true;
239    }
240
241
242    /**
243     * Hash code for this pair list.
244     * @see java.lang.Object#hashCode()
245     */
246    @Override
247    public int hashCode() {
248        int h;
249        h = getList().hashCode();
250        h = h << 7;
251        h += pairCount(); // findbugs
252        return h;
253    }
254
255
256    /**
257     * Put one Polynomial to the pairlist and reduction matrix.
258     * @param p polynomial.
259     * @return the index of the added polynomial.
260     */
261    public synchronized int put(ColorPolynomial<C> p) {
262        putCount++;
263        if (oneInGB) {
264            return P.size() - 1;
265        }
266        ExpVector e = p.leadingExpVector();
267        // System.out.println("p = " + p);
268        int l = P.size();
269        for (int j = 0; j < l; j++) {
270            ColorPolynomial<C> pj = P.get(j);
271            // System.out.println("pj = " + pj);
272            ExpVector f = pj.leadingExpVector();
273            if (moduleVars > 0) {
274                if (e.invLexCompareTo(f, 0, moduleVars) != 0) {
275                    continue; // skip pair
276                }
277            }
278            // System.out.println("e = " + e + ", f = " + f);
279            ExpVector g = e.lcm(f); // EVLCM( e, f );
280            CPair<C> pair = new CPair<C>(pj, p, j, l);
281            // redi = (BitSet)red.get(j);
282            // /if ( j < l ) redi.set( l );
283            // System.out.println("bitset."+j+" = " + redi );
284
285            // multiple pairs under same keys -> list of pairs
286            LinkedList<CPair<C>> xl = pairlist.get(g);
287            if (xl == null) {
288                xl = new LinkedList<CPair<C>>();
289            }
290            // xl.addLast( pair ); // first or last ?
291            xl.addFirst(pair); // first or last ? better for d- e-GBs
292            pairlist.put(g, xl);
293        }
294        // System.out.println("pairlist.keys@put = " + pairlist.keySet() );
295        P.add(p);
296        BitSet redi = new BitSet();
297        redi.set(0, l); // jdk 1.4
298        red.add(redi);
299        return P.size() - 1;
300    }
301
302
303    /**
304     * Remove the next required pair from the pairlist and reduction matrix.
305     * Apply the criterions 3 and 4 to see if the S-polynomial is required.
306     * @return the next pair if one exists, otherwise null.
307     */
308    public synchronized CPair<C> removeNext() {
309        if (oneInGB) {
310            return null;
311        }
312        Iterator<Map.Entry<ExpVector, LinkedList<CPair<C>>>> ip = pairlist.entrySet().iterator();
313
314        CPair<C> pair = null;
315        boolean c = false;
316        int i, j;
317
318        while (!c && ip.hasNext()) {
319            Map.Entry<ExpVector, LinkedList<CPair<C>>> me = ip.next();
320            ExpVector g = me.getKey();
321            LinkedList<CPair<C>> xl = me.getValue();
322            logger.info("g = {}", g);
323            pair = null;
324            while (!c && xl.size() > 0) {
325                pair = xl.removeFirst();
326                // xl is also modified in pairlist
327                i = pair.i;
328                j = pair.j;
329                // System.out.println("pair(" + j + "," +i+") ");
330                //if (useCriterion4) {
331                // c = reduction.criterion4( pair.pi, pair.pj, g );
332                //    c = true;
333                //}
334                c = true;
335                // System.out.println("c4 = " + c);
336                //if (c) {
337                // c = criterion3( i, j, g );
338                // System.out.println("c3 = " + c);
339                //}
340                red.get(j).clear(i); // set(i,false) jdk1.4
341            }
342            if (xl.size() == 0)
343                ip.remove();
344            // = pairlist.remove( g );
345        }
346        if (!c) {
347            pair = null;
348        } else {
349            remCount++; // count only real pairs
350        }
351        return pair;
352    }
353
354
355    /**
356     * Test if there is possibly a pair in the list.
357     * @return true if a next pair could exist, otherwise false.
358     */
359    public synchronized boolean hasNext() {
360        return pairlist.size() > 0;
361    }
362
363
364    /**
365     * Get the list of polynomials.
366     * @return the polynomial list.
367     */
368    public List<ColorPolynomial<C>> getList() {
369        return P;
370    }
371
372
373    /**
374     * Get the number of polynomials put to the pairlist.
375     * @return the number of calls to put.
376     */
377    public synchronized int putCount() {
378        return putCount;
379    }
380
381
382    /**
383     * Get the number of required pairs removed from the pairlist.
384     * @return the number of non null pairs delivered.
385     */
386    public synchronized int remCount() {
387        return remCount;
388    }
389
390
391    /**
392     * Put to ONE-Polynomial to the pairlist.
393     * @param one polynomial. (no more required)
394     * @return the index of the last polynomial.
395     */
396    public synchronized int putOne(ColorPolynomial<C> one) {
397        putCount++;
398        if (one == null) {
399            return P.size() - 1;
400        }
401        if (!one.isONE()) {
402            return P.size() - 1;
403        }
404        oneInGB = true;
405        pairlist.clear();
406        P.clear();
407        P.add(one);
408        red.clear();
409        return P.size() - 1;
410    }
411
412
413    /**
414     * GB criterium 3.
415     * @return true if the S-polynomial(i,j) is required.
416     */
417    public boolean criterion3(int i, int j, ExpVector eij) {
418        // assert i < j;
419        boolean s = red.get(j).get(i);
420        if (!s) {
421            logger.warn("c3.s false for j = {}, i = {}", j, i);
422            return s;
423        }
424        // now s = true;
425        for (int k = 0; k < P.size(); k++) {
426            if (i != k && j != k) {
427                ColorPolynomial<C> A = P.get(k);
428                ExpVector ek = A.leadingExpVector();
429                boolean m = eij.multipleOf(ek); // EVMT(eij,ek);
430                if (m) {
431                    if (k < i) {
432                        // System.out.println("k < i "+k+" "+i);
433                        s = red.get(i).get(k) || red.get(j).get(k);
434                    } else if (i < k && k < j) {
435                        // System.out.println("i < k < j "+i+" "+k+" "+j);
436                        s = red.get(k).get(i) || red.get(j).get(k);
437                    } else if (j < k) {
438                        // System.out.println("j < k "+j+" "+k);
439                        s = red.get(k).get(i) || red.get(k).get(j);
440                    }
441                    // System.out.println("s."+k+" = " + s);
442                    if (!s) {
443                        return s;
444                    }
445                }
446            }
447        }
448        return true;
449    }
450}