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