001/* 002 * $Id$ 003 */ 004 005package edu.jas.application; 006 007 008import java.io.Serializable; 009import java.util.ArrayList; 010import java.util.BitSet; 011import java.util.Iterator; 012import java.util.LinkedList; 013import java.util.List; 014import java.util.Map; 015import java.util.SortedMap; 016import java.util.TreeMap; 017 018import org.apache.logging.log4j.LogManager; 019import org.apache.logging.log4j.Logger; 020 021import edu.jas.poly.ExpVector; 022import edu.jas.poly.GenPolynomial; 023import edu.jas.poly.GenPolynomialRing; 024import edu.jas.poly.GenSolvablePolynomialRing; 025import edu.jas.structure.GcdRingElem; 026import edu.jas.structure.RingFactory; 027 028 029/** 030 * Pair list management. Implemented for ColorPolynomials using TreeMap and 031 * BitSet. 032 * @author Heinz Kredel 033 */ 034 035public class OrderedCPairlist<C extends GcdRingElem<C>> implements Serializable { 036 037 038 private static final Logger logger = LogManager.getLogger(OrderedCPairlist.class); 039 040 041 protected final GenPolynomialRing<GenPolynomial<C>> ring; 042 043 044 protected final List<ColorPolynomial<C>> P; 045 046 047 protected final SortedMap<ExpVector, LinkedList<CPair<C>>> pairlist; 048 049 050 protected final List<BitSet> red; 051 052 053 protected final CReductionSeq<C> reduction; 054 055 056 protected boolean oneInGB = false; 057 058 059 protected boolean useCriterion4 = false; // unused 060 061 062 protected int putCount; 063 064 065 protected int remCount; 066 067 068 protected final int moduleVars; // unused 069 070 071 /** 072 * Constructor for OrderedPairlist. 073 * @param r polynomial factory. 074 */ 075 public OrderedCPairlist(GenPolynomialRing<GenPolynomial<C>> r) { 076 this(0, r); 077 } 078 079 080 /** 081 * Constructor for OrderedPairlist. 082 * @param m number of module variables. 083 * @param r polynomial factory. 084 */ 085 public OrderedCPairlist(int m, GenPolynomialRing<GenPolynomial<C>> r) { 086 moduleVars = m; 087 ring = r; 088 P = new ArrayList<ColorPolynomial<C>>(); 089 pairlist = new TreeMap<ExpVector, LinkedList<CPair<C>>>(ring.tord.getAscendComparator()); 090 // pairlist = new TreeMap( to.getSugarComparator() ); 091 red = new ArrayList<BitSet>(); 092 putCount = 0; 093 remCount = 0; 094 if (ring instanceof GenSolvablePolynomialRing) { 095 useCriterion4 = false; 096 } 097 RingFactory<GenPolynomial<C>> rf = ring.coFac; 098 GenPolynomialRing<C> cf = (GenPolynomialRing<C>) rf; 099 reduction = new CReductionSeq<C>(cf.coFac); 100 } 101 102 103 /** 104 * Internal constructor for OrderedPairlist. Used to clone this pair list. 105 * @param m number of module variables. 106 * @param r polynomial factory. 107 * @param P list of color polynomials. 108 * @param pl critical pair list. 109 * @param red reduction matrix. 110 * @param cred color polynomial reduction engine. 111 * @param pc put count. 112 * @param rc remove count. 113 */ 114 private OrderedCPairlist(int m, GenPolynomialRing<GenPolynomial<C>> r, List<ColorPolynomial<C>> P, 115 SortedMap<ExpVector, LinkedList<CPair<C>>> pl, List<BitSet> red, CReductionSeq<C> cred, 116 int pc, int rc) { 117 moduleVars = m; 118 this.ring = r; 119 this.P = P; 120 pairlist = pl; 121 this.red = red; 122 reduction = cred; 123 putCount = pc; 124 remCount = rc; 125 } 126 127 128 /** 129 * Clone this OrderedPairlist. 130 * @return a 2 level clone of this. 131 */ 132 public synchronized OrderedCPairlist<C> copy() { 133 return new OrderedCPairlist<C>(moduleVars, ring, new ArrayList<ColorPolynomial<C>>(P), 134 clonePairlist(), cloneBitSet(), reduction, putCount, remCount); 135 } 136 137 138 /** 139 * Clone this pairlist. 140 * @return a 2 level clone of this pairlist. 141 */ 142 private SortedMap<ExpVector, LinkedList<CPair<C>>> clonePairlist() { 143 SortedMap<ExpVector, LinkedList<CPair<C>>> pl = new TreeMap<ExpVector, LinkedList<CPair<C>>>( 144 ring.tord.getAscendComparator()); 145 for (Map.Entry<ExpVector, LinkedList<CPair<C>>> m : pairlist.entrySet()) { 146 ExpVector e = m.getKey(); 147 LinkedList<CPair<C>> l = m.getValue(); 148 l = new LinkedList<CPair<C>>(l); 149 pl.put(e, l); 150 } 151 return pl; 152 } 153 154 155 /** 156 * Count remaining Pairs. 157 * @return number of pairs remaining in this pairlist. 158 */ 159 public int pairCount() { 160 int c = 0; 161 for (Map.Entry<ExpVector, LinkedList<CPair<C>>> m : pairlist.entrySet()) { 162 LinkedList<CPair<C>> l = m.getValue(); 163 c += l.size(); 164 } 165 return c; 166 } 167 168 169 /** 170 * Clone this reduction BitSet. 171 * @return a 2 level clone of this reduction BitSet. 172 */ 173 private List<BitSet> cloneBitSet() { 174 List<BitSet> r = new ArrayList<BitSet>(this.red.size()); 175 for (BitSet b : red) { 176 BitSet n = (BitSet) b.clone(); 177 r.add(n); 178 } 179 return r; 180 } 181 182 183 /** 184 * bitCount. 185 * @return number of bits set in this bitset. 186 */ 187 public int bitCount() { 188 int c = 0; 189 for (BitSet b : red) { 190 c += b.cardinality(); 191 } 192 return c; 193 } 194 195 196 /** 197 * toString. 198 * @return counters of this. 199 */ 200 @Override 201 public String toString() { 202 int p = pairCount(); 203 int b = bitCount(); 204 if (p != b) { 205 return "OrderedCPairlist( pairCount=" + p + ", bitCount=" + b + ", putCount=" + putCount 206 + ", remCount=" + remCount + " )"; 207 } 208 return "OrderedCPairlist( pairCount=" + p + ", putCount=" + putCount + ", remCount=" + remCount 209 + " )"; 210 } 211 212 213 /** 214 * Equals. 215 * @param ob an Object. 216 * @return true if this is equal to o, else false. 217 */ 218 @Override 219 @SuppressWarnings("unchecked") 220 public boolean equals(Object ob) { 221 OrderedCPairlist<C> c = null; 222 try { 223 c = (OrderedCPairlist<C>) ob; 224 } catch (ClassCastException e) { 225 return false; 226 } 227 if (c == null) { 228 return false; 229 } 230 boolean t = getList().equals(c.getList()); 231 if (!t) { 232 return t; 233 } 234 t = pairCount() == c.pairCount(); 235 if (!t) { 236 return t; 237 } 238 return true; 239 } 240 241 242 /** 243 * Hash code for this pair list. 244 * @see java.lang.Object#hashCode() 245 */ 246 @Override 247 public int hashCode() { 248 int h; 249 h = getList().hashCode(); 250 h = h << 7; 251 h += pairCount(); // findbugs 252 return h; 253 } 254 255 256 /** 257 * Put one Polynomial to the pairlist and reduction matrix. 258 * @param p polynomial. 259 * @return the index of the added polynomial. 260 */ 261 public synchronized int put(ColorPolynomial<C> p) { 262 putCount++; 263 if (oneInGB) { 264 return P.size() - 1; 265 } 266 ExpVector e = p.leadingExpVector(); 267 // System.out.println("p = " + p); 268 int l = P.size(); 269 for (int j = 0; j < l; j++) { 270 ColorPolynomial<C> pj = P.get(j); 271 // System.out.println("pj = " + pj); 272 ExpVector f = pj.leadingExpVector(); 273 if (moduleVars > 0) { 274 if (e.invLexCompareTo(f, 0, moduleVars) != 0) { 275 continue; // skip pair 276 } 277 } 278 // System.out.println("e = " + e + ", f = " + f); 279 ExpVector g = e.lcm(f); // EVLCM( e, f ); 280 CPair<C> pair = new CPair<C>(pj, p, j, l); 281 // redi = (BitSet)red.get(j); 282 // /if ( j < l ) redi.set( l ); 283 // System.out.println("bitset."+j+" = " + redi ); 284 285 // multiple pairs under same keys -> list of pairs 286 LinkedList<CPair<C>> xl = pairlist.get(g); 287 if (xl == null) { 288 xl = new LinkedList<CPair<C>>(); 289 } 290 // xl.addLast( pair ); // first or last ? 291 xl.addFirst(pair); // first or last ? better for d- e-GBs 292 pairlist.put(g, xl); 293 } 294 // System.out.println("pairlist.keys@put = " + pairlist.keySet() ); 295 P.add(p); 296 BitSet redi = new BitSet(); 297 redi.set(0, l); // jdk 1.4 298 red.add(redi); 299 return P.size() - 1; 300 } 301 302 303 /** 304 * Remove the next required pair from the pairlist and reduction matrix. 305 * Apply the criterions 3 and 4 to see if the S-polynomial is required. 306 * @return the next pair if one exists, otherwise null. 307 */ 308 public synchronized CPair<C> removeNext() { 309 if (oneInGB) { 310 return null; 311 } 312 Iterator<Map.Entry<ExpVector, LinkedList<CPair<C>>>> ip = pairlist.entrySet().iterator(); 313 314 CPair<C> pair = null; 315 boolean c = false; 316 int i, j; 317 318 while (!c && ip.hasNext()) { 319 Map.Entry<ExpVector, LinkedList<CPair<C>>> me = ip.next(); 320 ExpVector g = me.getKey(); 321 LinkedList<CPair<C>> xl = me.getValue(); 322 logger.info("g = {}", g); 323 pair = null; 324 while (!c && xl.size() > 0) { 325 pair = xl.removeFirst(); 326 // xl is also modified in pairlist 327 i = pair.i; 328 j = pair.j; 329 // System.out.println("pair(" + j + "," +i+") "); 330 //if (useCriterion4) { 331 // c = reduction.criterion4( pair.pi, pair.pj, g ); 332 // c = true; 333 //} 334 c = true; 335 // System.out.println("c4 = " + c); 336 //if (c) { 337 // c = criterion3( i, j, g ); 338 // System.out.println("c3 = " + c); 339 //} 340 red.get(j).clear(i); // set(i,false) jdk1.4 341 } 342 if (xl.size() == 0) 343 ip.remove(); 344 // = pairlist.remove( g ); 345 } 346 if (!c) { 347 pair = null; 348 } else { 349 remCount++; // count only real pairs 350 } 351 return pair; 352 } 353 354 355 /** 356 * Test if there is possibly a pair in the list. 357 * @return true if a next pair could exist, otherwise false. 358 */ 359 public synchronized boolean hasNext() { 360 return pairlist.size() > 0; 361 } 362 363 364 /** 365 * Get the list of polynomials. 366 * @return the polynomial list. 367 */ 368 public List<ColorPolynomial<C>> getList() { 369 return P; 370 } 371 372 373 /** 374 * Get the number of polynomials put to the pairlist. 375 * @return the number of calls to put. 376 */ 377 public synchronized int putCount() { 378 return putCount; 379 } 380 381 382 /** 383 * Get the number of required pairs removed from the pairlist. 384 * @return the number of non null pairs delivered. 385 */ 386 public synchronized int remCount() { 387 return remCount; 388 } 389 390 391 /** 392 * Put to ONE-Polynomial to the pairlist. 393 * @param one polynomial. (no more required) 394 * @return the index of the last polynomial. 395 */ 396 public synchronized int putOne(ColorPolynomial<C> one) { 397 putCount++; 398 if (one == null) { 399 return P.size() - 1; 400 } 401 if (!one.isONE()) { 402 return P.size() - 1; 403 } 404 oneInGB = true; 405 pairlist.clear(); 406 P.clear(); 407 P.add(one); 408 red.clear(); 409 return P.size() - 1; 410 } 411 412 413 /** 414 * GB criterium 3. 415 * @return true if the S-polynomial(i,j) is required. 416 */ 417 public boolean criterion3(int i, int j, ExpVector eij) { 418 // assert i < j; 419 boolean s = red.get(j).get(i); 420 if (!s) { 421 logger.warn("c3.s false for j = {}, i = {}", j, i); 422 return s; 423 } 424 // now s = true; 425 for (int k = 0; k < P.size(); k++) { 426 if (i != k && j != k) { 427 ColorPolynomial<C> A = P.get(k); 428 ExpVector ek = A.leadingExpVector(); 429 boolean m = eij.multipleOf(ek); // EVMT(eij,ek); 430 if (m) { 431 if (k < i) { 432 // System.out.println("k < i "+k+" "+i); 433 s = red.get(i).get(k) || red.get(j).get(k); 434 } else if (i < k && k < j) { 435 // System.out.println("i < k < j "+i+" "+k+" "+j); 436 s = red.get(k).get(i) || red.get(j).get(k); 437 } else if (j < k) { 438 // System.out.println("j < k "+j+" "+k); 439 s = red.get(k).get(i) || red.get(k).get(j); 440 } 441 // System.out.println("s."+k+" = " + s); 442 if (!s) { 443 return s; 444 } 445 } 446 } 447 } 448 return true; 449 } 450}