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