001/*
002 * $Id: OrderedDPairlist.java 3417 2010-12-19 16:24:24Z kredel $
003 */
004
005package edu.jas.gb;
006
007import java.util.Iterator;
008import java.util.LinkedList;
009import java.util.Map;
010import org.apache.log4j.Logger;
011
012import edu.jas.poly.ExpVector;
013import edu.jas.poly.GenPolynomial;
014import edu.jas.poly.GenPolynomialRing;
015import edu.jas.structure.RingElem;
016
017/**
018 * Pair list management for d-Groebner bases.
019 * Implemented using GenPolynomial, TreeMap and BitSet.
020 * @author Heinz Kredel
021 */
022
023public class OrderedDPairlist<C extends RingElem<C> > 
024    extends OrderedPairlist<C> {
025
026    private static final Logger logger = Logger.getLogger(OrderedDPairlist.class);
027
028    protected final DReduction<C> dreduction;
029
030
031    /**
032     * Constructor for OrderedDPairlist.
033     * @param r polynomial factory.
034     */
035    public OrderedDPairlist(GenPolynomialRing<C> r) {
036        this(0,r);
037    }
038
039
040    /**
041     * Constructor for OrderedDPairlist.
042     * @param m number of module variables.
043     * @param r polynomial factory.
044     */
045    public OrderedDPairlist(int m, GenPolynomialRing<C> r) {
046        super(m,r);
047        dreduction = new DReductionSeq<C>();
048    }
049
050
051    /**
052     * Create a new PairList.
053     * @param r polynomial ring.
054     */
055    public PairList<C> create(GenPolynomialRing<C> r) {
056        return new OrderedDPairlist<C>(r);
057    }
058
059
060    /**
061     * Create a new PairList.
062     * @param m number of module variables.
063     * @param r polynomial ring.
064     */
065    public PairList<C> create(int m, GenPolynomialRing<C> r) {
066        return new OrderedDPairlist<C>(m,r);
067    }
068
069
070    /**
071     * Remove the next required pair from the pairlist and reduction matrix.
072     * The results of the application of the criterions 3 and 4 to see if the S-polynomial 
073     * is required are recorded in the Pair.
074     * @return the next pair if one exists, otherwise null.
075     */
076    @Override
077    public synchronized Pair<C> removeNext() { 
078        if ( oneInGB ) {
079            return null;
080        }
081        Iterator< Map.Entry<ExpVector,LinkedList<Pair<C>>> > ip 
082            = pairlist.entrySet().iterator();
083
084        Pair<C> pair = null;
085        boolean c = false;
086        int i, j;
087
088        if  ( ip.hasNext() )  {
089            Map.Entry<ExpVector,LinkedList<Pair<C>>> me = ip.next();
090            ExpVector g =  me.getKey();
091            LinkedList<Pair<C>> xl = me.getValue();
092            if ( logger.isInfoEnabled() ) {
093                logger.info("g  = " + g);
094            }
095            pair = null;
096            if ( xl.size() > 0 ) {
097                pair = xl.removeFirst();
098                // xl is also modified in pairlist 
099                i = pair.i; 
100                j = pair.j; 
101                // System.out.println("pair(" + j + "," +i+") ");
102                if ( useCriterion4 ) {
103                    c = dreduction.criterion4( pair.pi, pair.pj, g ); 
104                } else {
105                    c = true;
106                }
107                pair.setUseCriterion4(c);
108                //System.out.println("c4  = " + c);  
109                if ( c ) {
110                    c = criterion3( i, j, g );
111                    //System.out.println("c3  = " + c); 
112                    pair.setUseCriterion3(c);
113                }
114                red.get( j ).clear(i); // set(i,false) jdk1.4
115            }
116            if ( xl.size() == 0 ) {
117                ip.remove(); // = pairlist.remove( g );
118            }
119        }
120        remCount++; // count pairs
121        return pair; 
122    }
123
124
125    /**
126     * GB criterium 3 with coefficient division test.
127     * @return true if the S-polynomial(i,j) is required.
128     */
129    @Override
130    public boolean criterion3(int i, int j, ExpVector eij) {  
131        // assert i < j;
132        boolean s;
133        s = red.get( j ).get(i); 
134        if ( ! s ) { 
135            logger.warn("c3.s false for " + j + " " + i); 
136            return s;
137        }
138        s = true;
139        boolean m;
140        GenPolynomial<C> A;
141        ExpVector ek;
142        C ci = P.get(i).leadingBaseCoefficient();
143        C cj = P.get(j).leadingBaseCoefficient();
144        C c = ci.gcd(cj);
145        for ( int k = 0; k < P.size(); k++ ) {
146            A = P.get( k );
147            ek = A.leadingExpVector();
148            m = eij.multipleOf(ek);
149            if ( m ) {
150                C ck = A.leadingBaseCoefficient();
151                C r = c.remainder(ck);
152                m = r.isZERO();
153            }
154            if ( m ) {
155                if ( k < i ) {
156                    // System.out.println("k < i "+k+" "+i); 
157                    s =    red.get( i ).get(k) 
158                        || red.get( j ).get(k); 
159                }
160                if ( i < k && k < j ) {
161                    // System.out.println("i < k < j "+i+" "+k+" "+j); 
162                    s =    red.get( k ).get(i) 
163                        || red.get( j ).get(k); 
164                }
165                if ( j < k ) {
166                    //System.out.println("j < k "+j+" "+k); 
167                    s =    red.get( k ).get(i) 
168                        || red.get( k ).get(j); 
169                }
170                //System.out.println("s."+k+" = " + s); 
171                if ( ! s ) return s;
172            }
173        }
174        return true;
175    }
176
177}