001/*
002 * $Id: OrderedWordPairlist.java 4157 2012-09-02 18:18:43Z 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.List;
012import java.util.Map;
013import java.util.TreeMap;
014import java.util.SortedMap;
015
016import org.apache.log4j.Logger;
017
018import edu.jas.poly.Word;
019import edu.jas.poly.Overlap;
020import edu.jas.poly.OverlapList;
021import edu.jas.poly.GenWordPolynomial;
022import edu.jas.poly.GenWordPolynomialRing;
023import edu.jas.structure.RingElem;
024
025/**
026 * Pair list management of word polynomials.
027 * Implemented using GenWordPolynomial, TreeMap and BitSet.
028 * @author Heinz Kredel
029 */
030
031public class OrderedWordPairlist<C extends RingElem<C> > implements WordPairList<C> {
032
033    protected final List<GenWordPolynomial<C>> P;
034    protected final SortedMap<Word,LinkedList<WordPair<C>>> pairlist;
035    protected final List<BitSet> red;
036    protected final GenWordPolynomialRing<C> ring;
037    protected final WordReduction<C> reduction;
038    protected boolean oneInGB = false;
039    protected int putCount;
040    protected int remCount;
041
042    private static final Logger logger = Logger.getLogger(OrderedWordPairlist.class);
043
044
045    /**
046     * Constructor.
047     */
048    public OrderedWordPairlist() {
049        ring = null;
050        P = null;
051        pairlist = null; 
052        red = null;
053        reduction = null;
054        putCount = 0;
055        remCount = 0;
056    }
057
058
059    /**
060     * Constructor.
061     * @param r word polynomial factory.
062     */
063    public OrderedWordPairlist(GenWordPolynomialRing<C> r) {
064        ring = r;
065        P = new ArrayList<GenWordPolynomial<C>>();
066        pairlist = new TreeMap<Word,LinkedList<WordPair<C>>>( ring.alphabet.getAscendComparator() );
067        red = new ArrayList<BitSet>();
068        putCount = 0;
069        remCount = 0;
070        reduction = new WordReductionSeq<C>();
071    }
072
073
074    /**
075     * Create a new WordPairList.
076     * @param r word polynomial ring.
077     */
078    public WordPairList<C> create(GenWordPolynomialRing<C> r) {
079        return new OrderedWordPairlist<C>(r);
080    }
081
082
083    /**
084     * toString.
085     */
086    @Override
087    public String toString() {
088        StringBuffer s = new StringBuffer(this.getClass().getSimpleName() + "(");
089        //s.append("polys="+P.size());
090        s.append("#put="+putCount);
091        s.append(", #rem="+remCount);
092        if ( pairlist != null && pairlist.size() != 0 ) {
093            s.append(", size="+pairlist.size());
094        }
095        s.append(")");
096        return s.toString();
097    }
098
099
100    /**
101     * Put one Polynomial to the pairlist and reduction matrix.
102     * @param p polynomial.
103     * @return the index of the added polynomial.
104     */
105    public synchronized int put(GenWordPolynomial<C> p) { 
106        putCount++;
107        if ( oneInGB ) { 
108            return P.size()-1;
109        }
110        Word e = p.leadingWord();
111        int l = P.size();
112        for ( int j = 0; j < l; j++ ) {
113            GenWordPolynomial<C> pj = P.get(j);
114            Word f = pj.leadingWord();
115            Word g = f.lcm(e);
116            //System.out.println("g = " + g);
117            if ( g == null ) {
118                //System.out.println("criterion 4");
119                continue; // criterion 4
120            }
121            WordPair<C> pair = new WordPair<C>( pj, p, j, l);
122            //System.out.println("pair.new      = " + pair);
123            //multiple pairs under same keys -> list of pairs
124            LinkedList<WordPair<C>> xl = pairlist.get( g );
125            if ( xl == null ) {
126                xl = new LinkedList<WordPair<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        //System.out.println("#pairlist = " + pairlist.size() );  
134        P.add(  p );
135        BitSet redi = new BitSet();
136        redi.set( 0, l ); 
137        red.add( redi );
138        //System.out.println("pairlist.set = " + red); //.get( pair.j )); //pair);
139        //System.out.println("pairlist.key = " + pairlist.keySet() );  
140        return P.size()-1;
141    }
142
143
144    /**
145     * Remove the next required pair from the pairlist and reduction matrix.
146     * Appy the criterions 3 and 4 to see if the S-polynomial is required.
147     * @return the next pair if one exists, otherwise null.
148     */
149    public synchronized WordPair<C> removeNext() { 
150        if ( oneInGB ) {
151            return null;
152        }
153        Iterator< Map.Entry<Word,LinkedList<WordPair<C>>> > ip 
154            = pairlist.entrySet().iterator();
155
156        WordPair<C> pair = null;
157        boolean c = false;
158        int i, j;
159
160        while ( !c && ip.hasNext() )  {
161            Map.Entry<Word,LinkedList<WordPair<C>>> me = ip.next();
162            Word g =  me.getKey();
163            LinkedList<WordPair<C>> xl = me.getValue();
164            if ( logger.isInfoEnabled() ) {
165                logger.info("g  = " + g);
166            }
167            pair = null;
168            while ( !c && xl.size() > 0 ) {
169                pair = xl.removeFirst();
170                // xl is also modified in pairlist 
171                i = pair.i; 
172                j = pair.j; 
173                // System.out.println("pair(" + j + "," +i+") ");
174                c = criterion3( i, j, g ); // should be okay
175                //if ( !c ) {
176                //    System.out.println("criterion 3");
177                //}
178                //System.out.println("c3_o  = " + c); 
179                red.get( j ).clear(i); // set(i,false) jdk1.4
180            }
181            if ( xl.size() == 0 ) {
182                ip.remove(); 
183                // = pairlist.remove( g );
184            }
185        }
186        if ( ! c ) {
187            pair = null;
188        } else {
189            remCount++; // count only real pairs
190        }
191        return pair; 
192    }
193
194
195    /**
196     * Test if there is possibly a pair in the list.
197     * @return true if a next pair could exist, otherwise false.
198     */
199    public synchronized boolean hasNext() { 
200        return pairlist.size() > 0;
201    }
202
203
204    /**
205     * Get the list of polynomials.
206     * @return the polynomial list.
207     */
208    public List<GenWordPolynomial<C>> getList() { 
209        return P;
210    }
211
212
213    /**
214     * Get the number of polynomials put to the pairlist.
215     * @return the number of calls to put.
216     */
217    public synchronized int putCount() { 
218        return putCount;
219    }
220
221
222    /**
223     * Get the number of required pairs removed from the pairlist.
224     * @return the number of non null pairs delivered.
225     */
226    public synchronized int remCount() { 
227        return remCount;
228    }
229
230
231    /**
232     * Put the ONE-Polynomial to the pairlist.
233     * @param one polynomial. (no more required)
234     * @return the index of the last polynomial.
235     */
236    public synchronized int putOne(GenWordPolynomial<C> one) { 
237        if ( one == null ) {
238            return P.size()-1;
239        }
240        if ( ! one.isONE() ) {
241            return P.size()-1;
242        }
243        return putOne();
244    }
245
246
247    /**
248     * Put the ONE-Polynomial to the pairlist.
249     * @return the index of the last polynomial.
250     */
251    public synchronized int putOne() { 
252        putCount++;
253        oneInGB = true;
254        pairlist.clear();
255        P.clear();
256        P.add(ring.getONE());
257        red.clear();
258        return P.size()-1;
259    }
260
261
262    /**
263     * GB criterium 3.
264     * @return true if the S-polynomial(i,j) is required.
265     */
266    public boolean criterion3(int i, int j, Word eij) {  
267        // assert i < j;
268        boolean s = red.get( j ).get(i); 
269        if ( ! s ) { 
270            logger.warn("c3.s false for " + j + " " + i); 
271            return s;
272        }
273        // now s = true;
274        for ( int k = 0; k < P.size(); k++ ) {
275            // System.out.println("i , k , j "+i+" "+k+" "+j); 
276            if ( i != k && j != k ) {
277                GenWordPolynomial<C> A = P.get( k );
278                Word ek = A.leadingWord();
279                boolean m = eij.multipleOf(ek);
280                if ( m ) {
281                    if ( k < i ) {
282                        // System.out.println("k < i "+k+" "+i); 
283                        s =    red.get( i ).get(k) 
284                            || red.get( j ).get(k); 
285                    } else if ( i < k && k < j ) {
286                        // System.out.println("i < k < j "+i+" "+k+" "+j); 
287                        s =    red.get( k ).get(i) 
288                            || red.get( j ).get(k); 
289                    } else if ( j < k ) {
290                        //System.out.println("j < k "+j+" "+k); 
291                        s =    red.get( k ).get(i) 
292                            || red.get( k ).get(j); 
293                    }
294                    //System.out.println("s."+k+" = " + s); 
295                    if ( ! s ) {
296                        return s;
297                    }
298                }
299            }
300        }
301        return true;
302    }
303
304}