Source code

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