001/*
002 * $Id: OrderedMinPairlist.java 4334 2012-12-28 11:49:57Z 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.Map;
012import java.util.TreeMap;
013
014import org.apache.log4j.Logger;
015
016import edu.jas.poly.ExpVector;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.poly.GenPolynomialRing;
019import edu.jas.poly.GenSolvablePolynomialRing;
020import edu.jas.structure.RingElem;
021
022/**
023 * Pair list management.
024 * The original Buchberger algorithm with criterions 
025 * using early pair exclusion.
026 * Implemented using GenPolynomial, TreeMap and BitSet.
027 * @author Heinz Kredel
028 */
029
030public class OrderedMinPairlist<C extends RingElem<C> > extends OrderedPairlist<C> {
031
032    private static final Logger logger = Logger.getLogger(OrderedMinPairlist.class);
033
034
035    /**
036     * Constructor.
037     */
038    public OrderedMinPairlist() {
039        super();
040    }
041
042
043    /**
044     * Constructor.
045     * @param r polynomial factory.
046     */
047    public OrderedMinPairlist(GenPolynomialRing<C> r) {
048        this(0,r);
049    }
050
051
052    /**
053     * Constructor.
054     * @param m number of module variables.
055     * @param r polynomial factory.
056     */
057    public OrderedMinPairlist(int m, GenPolynomialRing<C> r) {
058        super(m,r);
059    }
060
061
062    /**
063     * Create a new PairList.
064     * @param r polynomial ring.
065     */
066    public PairList<C> create(GenPolynomialRing<C> r) {
067        return new OrderedMinPairlist<C>(r);
068    }
069
070
071    /**
072     * Create a new PairList.
073     * @param m number of module variables.
074     * @param r polynomial ring.
075     */
076    public PairList<C> create(int m, GenPolynomialRing<C> r) {
077        return new OrderedMinPairlist<C>(m,r);
078    }
079
080
081    /**
082     * Put one Polynomial to the pairlist and reduction matrix.
083     * @param p polynomial.
084     * @return the index of the added polynomial.
085     */
086    public synchronized int put(GenPolynomial<C> p) { 
087        putCount++;
088        if ( oneInGB ) { 
089            return P.size()-1;
090        }
091        ExpVector e = p.leadingExpVector();
092        int l = P.size();
093        BitSet redi = new BitSet();
094        redi.set( 0, l ); // [0..l-1] = true
095        red.add( redi );
096        P.add(  p );
097        for ( int j = 0; j < l; j++ ) {
098            GenPolynomial<C> pj = P.get(j);
099            ExpVector f = pj.leadingExpVector(); 
100            if ( moduleVars > 0 ) {
101                if ( !reduction.moduleCriterion( moduleVars, e, f) ) {
102                    red.get(j).clear(l); 
103                    continue; // skip pair
104                }
105            }
106            ExpVector g =  e.lcm( f );
107            //System.out.println("g  = " + g);  
108            Pair<C> pair = new Pair<C>( pj, p, j, l);
109            boolean c = true;
110            if ( useCriterion4 ) {
111                c = reduction.criterion4( pair.pi, pair.pj, g ); 
112            }
113            //System.out.println("c4  = " + c);  
114            if ( c ) {
115                c = criterion3( j, l, g );
116                //System.out.println("c3  = " + c); 
117            }
118            if ( !c ) { // skip pair
119                red.get(j).clear(l); 
120                //System.out.println("c_skip = " + g); 
121                continue; 
122            }
123            //multiple pairs under same keys -> list of pairs
124            LinkedList<Pair<C>> xl = pairlist.get( g );
125            if ( xl == null ) {
126                xl = new LinkedList<Pair<C>>();
127            }
128            //xl.addLast( pair ); // first or last ?
129            xl.addFirst( pair ); // first or last ? better for d- e-GBs
130            pairlist.put( g, xl );
131        }
132        // System.out.println("pairlist.keys@put = " + pairlist.keySet() );  
133        return P.size()-1;
134    }
135
136
137    /**
138     * Remove the next required pair from the pairlist and reduction matrix.
139     * Appy the criterions 3 and 4 to see if the S-polynomial is required.
140     * @return the next pair if one exists, otherwise null.
141     */
142    public synchronized Pair<C> removeNext() { 
143        if ( oneInGB ) {
144            return null;
145        }
146        Iterator< Map.Entry<ExpVector,LinkedList<Pair<C>>> > ip 
147            = pairlist.entrySet().iterator();
148
149        Pair<C> pair = null;
150        boolean c = false;
151        int i, j;
152
153        while ( !c && ip.hasNext() )  {
154            Map.Entry<ExpVector,LinkedList<Pair<C>>> me = ip.next();
155            ExpVector g =  me.getKey();
156            LinkedList<Pair<C>> xl = me.getValue();
157            if ( logger.isInfoEnabled() ) {
158                logger.info("g  = " + g);
159            }
160            pair = null;
161            while ( !c && xl.size() > 0 ) {
162                pair = xl.removeFirst();
163                // xl is also modified in pairlist 
164                i = pair.i; 
165                j = pair.j; 
166                // System.out.println("pair(" + j + "," +i+") ");
167                if ( !red.get(j).get(i) ) {
168                    System.out.println("c_y = " + g); // + ", " + red.get(j).get(i)); 
169                    continue;
170                }
171                c = true;
172                if ( useCriterion4 ) {
173                    c = reduction.criterion4( pair.pi, pair.pj, g ); 
174                }
175                //System.out.println("c4_x = " + c);  
176                if ( c ) {
177                    c = criterion3( i, j, g );
178                    //System.out.println("c3_x = " + c); 
179                }
180                if ( !c ) {
181                    //System.out.println("c_x = " + g); 
182                }
183                red.get( j ).clear(i); // set(i,false) jdk1.4
184            }
185            if ( xl.size() == 0 ) {
186                ip.remove(); 
187                // = pairlist.remove( g );
188            }
189        }
190        if ( ! c ) {
191            pair = null;
192        } else {
193            pair.maxIndex(P.size()-1);
194            remCount++; // count only real pairs
195            if ( logger.isDebugEnabled() ) {
196                logger.info("pair(" + pair.j + "," + pair.i + ")");
197            }
198        }
199        return pair; 
200    }
201
202
203    /**
204     * GB criterium 3.
205     * @return true if the S-polynomial(i,j) is required.
206     */
207    public boolean criterion3(int i, int j, ExpVector eij) {  
208        // assert i < j;
209        boolean s;
210        s = red.get( j ).get(i); 
211        if ( ! s ) { 
212            logger.warn("c3.s false for " + j + " " + i); 
213            return s;
214        }
215        s = true;
216        boolean m;
217        GenPolynomial<C> A;
218        ExpVector ek;
219        for ( int k = 0; k < P.size(); k++ ) {
220            A = P.get( k );
221            ek = A.leadingExpVector();
222            m = eij.multipleOf(ek) && eij.compareTo(ek) != 0;
223            if ( m ) {
224                if ( k < i ) {
225                    // System.out.println("k < i "+k+" "+i); 
226                    s =    red.get( i ).get(k) 
227                        || red.get( j ).get(k); 
228                }
229                if ( i < k && k < j ) {
230                    // System.out.println("i < k < j "+i+" "+k+" "+j); 
231                    s =    red.get( k ).get(i) 
232                        || red.get( j ).get(k); 
233                }
234                if ( j < k ) {
235                    //System.out.println("j < k "+j+" "+k); 
236                    s =    red.get( k ).get(i) 
237                        || red.get( k ).get(j); 
238                }
239                //System.out.println("s."+k+" = " + s); 
240                if ( ! s ) return s;
241            }
242        }
243        return true;
244    }
245
246}