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}