Source code

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