Source code

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