Source code

001/*
002 * $Id: OrderedCPairlist.java 5868 2018-07-20 15:44:13Z kredel $
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.Logger;
019import org.apache.logging.log4j.LogManager; 
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     */
108    private OrderedCPairlist(int m, GenPolynomialRing<GenPolynomial<C>> ring, List<ColorPolynomial<C>> P,
109                    SortedMap<ExpVector, LinkedList<CPair<C>>> pl, List<BitSet> red, CReductionSeq<C> cred,
110                    int pc, int rc) {
111        moduleVars = m;
112        this.ring = ring;
113        this.P = P;
114        pairlist = pl;
115        this.red = red;
116        reduction = cred;
117        putCount = pc;
118        remCount = rc;
119    }
120
121
122    /**
123     * Clone this OrderedPairlist.
124     * @return a 2 level clone of this.
125     */
126    public synchronized OrderedCPairlist<C> copy() {
127        return new OrderedCPairlist<C>(moduleVars, ring, new ArrayList<ColorPolynomial<C>>(P),
128                        clonePairlist(), cloneBitSet(), reduction, putCount, remCount);
129    }
130
131
132    /**
133     * Clone this pairlist.
134     * @return a 2 level clone of this pairlist.
135     */
136    private SortedMap<ExpVector, LinkedList<CPair<C>>> clonePairlist() {
137        SortedMap<ExpVector, LinkedList<CPair<C>>> pl = new TreeMap<ExpVector, LinkedList<CPair<C>>>(
138                        ring.tord.getAscendComparator());
139        for (Map.Entry<ExpVector, LinkedList<CPair<C>>> m : pairlist.entrySet()) {
140            ExpVector e = m.getKey();
141            LinkedList<CPair<C>> l = m.getValue();
142            l = new LinkedList<CPair<C>>(l);
143            pl.put(e, l);
144        }
145        return pl;
146    }
147
148
149    /**
150     * Count remaining Pairs.
151     * @return number of pairs remaining in this pairlist.
152     */
153    public int pairCount() {
154        int c = 0;
155        for (Map.Entry<ExpVector, LinkedList<CPair<C>>> m : pairlist.entrySet()) {
156            LinkedList<CPair<C>> l = m.getValue();
157            c += l.size();
158        }
159        return c;
160    }
161
162
163    /**
164     * Clone this reduction BitSet.
165     * @return a 2 level clone of this reduction BitSet.
166     */
167    private List<BitSet> cloneBitSet() {
168        List<BitSet> r = new ArrayList<BitSet>(this.red.size());
169        for (BitSet b : red) {
170            BitSet n = (BitSet) b.clone();
171            r.add(n);
172        }
173        return r;
174    }
175
176
177    /**
178     * bitCount.
179     * @return number of bits set in this bitset.
180     */
181    public int bitCount() {
182        int c = 0;
183        for (BitSet b : red) {
184            c += b.cardinality();
185        }
186        return c;
187    }
188
189
190    /**
191     * toString.
192     * @return counters of this.
193     */
194    @Override
195    public String toString() {
196        int p = pairCount();
197        int b = bitCount();
198        if (p != b) {
199            return "OrderedCPairlist( pairCount=" + p + ", bitCount=" + b + ", putCount=" + putCount
200                            + ", remCount=" + remCount + " )";
201        }
202        return "OrderedCPairlist( pairCount=" + p + ", putCount=" + putCount + ", remCount=" + remCount
203                        + " )";
204    }
205
206
207    /**
208     * Equals.
209     * @param ob an Object.
210     * @return true if this is equal to o, else false.
211     */
212    @Override
213    @SuppressWarnings("unchecked")
214    public boolean equals(Object ob) {
215        OrderedCPairlist<C> c = null;
216        try {
217            c = (OrderedCPairlist<C>) ob;
218        } catch (ClassCastException e) {
219            return false;
220        }
221        if (c == null) {
222            return false;
223        }
224        boolean t = getList().equals(c.getList());
225        if (!t) {
226            return t;
227        }
228        t = pairCount() == c.pairCount();
229        if (!t) {
230            return t;
231        }
232        return true;
233    }
234
235
236    /**
237     * Hash code for this pair list.
238     * @see java.lang.Object#hashCode()
239     */
240    @Override
241    public int hashCode() {
242        int h;
243        h = getList().hashCode();
244        h = h << 7;
245        h += pairCount(); // findbugs
246        return h;
247    }
248
249
250    /**
251     * Put one Polynomial to the pairlist and reduction matrix.
252     * @param p polynomial.
253     * @return the index of the added polynomial.
254     */
255    public synchronized int put(ColorPolynomial<C> p) {
256        putCount++;
257        if (oneInGB) {
258            return P.size() - 1;
259        }
260        ExpVector e = p.leadingExpVector();
261        // System.out.println("p = " + p);
262        int l = P.size();
263        for (int j = 0; j < l; j++) {
264            ColorPolynomial<C> pj = P.get(j);
265            // System.out.println("pj = " + pj);
266            ExpVector f = pj.leadingExpVector();
267            if (moduleVars > 0) {
268                if (e.invLexCompareTo(f, 0, moduleVars) != 0) {
269                    continue; // skip pair
270                }
271            }
272            // System.out.println("e = " + e + ", f = " + f);
273            ExpVector g = e.lcm(f); // EVLCM( e, f );
274            CPair<C> pair = new CPair<C>(pj, p, j, l);
275            // redi = (BitSet)red.get(j);
276            // /if ( j < l ) redi.set( l );
277            // System.out.println("bitset."+j+" = " + redi );
278
279            // multiple pairs under same keys -> list of pairs
280            LinkedList<CPair<C>> xl = pairlist.get(g);
281            if (xl == null) {
282                xl = new LinkedList<CPair<C>>();
283            }
284            // xl.addLast( pair ); // first or last ?
285            xl.addFirst(pair); // first or last ? better for d- e-GBs
286            pairlist.put(g, xl);
287        }
288        // System.out.println("pairlist.keys@put = " + pairlist.keySet() );
289        P.add(p);
290        BitSet redi = new BitSet();
291        redi.set(0, l); // jdk 1.4
292        red.add(redi);
293        return P.size() - 1;
294    }
295
296
297    /**
298     * Remove the next required pair from the pairlist and reduction matrix.
299     * Appy the criterions 3 and 4 to see if the S-polynomial is required.
300     * @return the next pair if one exists, otherwise null.
301     */
302    public synchronized CPair<C> removeNext() {
303        if (oneInGB) {
304            return null;
305        }
306        Iterator<Map.Entry<ExpVector, LinkedList<CPair<C>>>> ip = pairlist.entrySet().iterator();
307
308        CPair<C> pair = null;
309        boolean c = false;
310        int i, j;
311
312        while (!c && ip.hasNext()) {
313            Map.Entry<ExpVector, LinkedList<CPair<C>>> me = ip.next();
314            ExpVector g = me.getKey();
315            LinkedList<CPair<C>> xl = me.getValue();
316            if (logger.isInfoEnabled())
317                logger.info("g  = " + g);
318            pair = null;
319            while (!c && xl.size() > 0) {
320                pair = xl.removeFirst();
321                // xl is also modified in pairlist
322                i = pair.i;
323                j = pair.j;
324                // System.out.println("pair(" + j + "," +i+") ");
325                //if (useCriterion4) {
326                    // c = reduction.criterion4( pair.pi, pair.pj, g );
327                //    c = true;
328                //}
329                c = true; 
330                // System.out.println("c4 = " + c);
331                //if (c) {
332                    // c = criterion3( i, j, g );
333                    // System.out.println("c3 = " + c);
334                //}
335                red.get(j).clear(i); // set(i,false) jdk1.4
336            }
337            if (xl.size() == 0)
338                ip.remove();
339            // = pairlist.remove( g );
340        }
341        if (!c) {
342            pair = null;
343        } else {
344            remCount++; // count only real pairs
345        }
346        return pair;
347    }
348
349
350    /**
351     * Test if there is possibly a pair in the list.
352     * @return true if a next pair could exist, otherwise false.
353     */
354    public synchronized boolean hasNext() {
355        return pairlist.size() > 0;
356    }
357
358
359    /**
360     * Get the list of polynomials.
361     * @return the polynomial list.
362     */
363    public List<ColorPolynomial<C>> getList() {
364        return P;
365    }
366
367
368    /**
369     * Get the number of polynomials put to the pairlist.
370     * @return the number of calls to put.
371     */
372    public synchronized int putCount() {
373        return putCount;
374    }
375
376
377    /**
378     * Get the number of required pairs removed from the pairlist.
379     * @return the number of non null pairs delivered.
380     */
381    public synchronized int remCount() {
382        return remCount;
383    }
384
385
386    /**
387     * Put to ONE-Polynomial to the pairlist.
388     * @param one polynomial. (no more required)
389     * @return the index of the last polynomial.
390     */
391    public synchronized int putOne(ColorPolynomial<C> one) {
392        putCount++;
393        if (one == null) {
394            return P.size() - 1;
395        }
396        if (!one.isONE()) {
397            return P.size() - 1;
398        }
399        oneInGB = true;
400        pairlist.clear();
401        P.clear();
402        P.add(one);
403        red.clear();
404        return P.size() - 1;
405    }
406
407
408    /**
409     * GB criterium 3.
410     * @return true if the S-polynomial(i,j) is required.
411     */
412    public boolean criterion3(int i, int j, ExpVector eij) {
413        // assert i < j;
414        boolean s = red.get(j).get(i);
415        if (!s) {
416            logger.warn("c3.s false for " + j + " " + i);
417            return s;
418        }
419        // now s = true;
420        for (int k = 0; k < P.size(); k++) {
421            if (i != k && j != k) {
422                ColorPolynomial<C> A = P.get(k);
423                ExpVector ek = A.leadingExpVector();
424                boolean m = eij.multipleOf(ek); // EVMT(eij,ek);
425                if (m) {
426                    if (k < i) {
427                        // System.out.println("k < i "+k+" "+i);
428                        s = red.get(i).get(k) || red.get(j).get(k);
429                    } else if (i < k && k < j) {
430                        // System.out.println("i < k < j "+i+" "+k+" "+j);
431                        s = red.get(k).get(i) || red.get(j).get(k);
432                    } else if (j < k) {
433                        // System.out.println("j < k "+j+" "+k);
434                        s = red.get(k).get(i) || red.get(k).get(j);
435                    }
436                    // System.out.println("s."+k+" = " + s);
437                    if (!s) {
438                        return s;
439                    }
440                }
441            }
442        }
443        return true;
444    }
445}