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