001/* 002 * $Id: OrderedPairlist.java 6013 2020-04-29 17:04:16Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.BitSet; 010import java.util.Iterator; 011import java.util.LinkedList; 012import java.util.List; 013import java.util.Map; 014import java.util.SortedMap; 015import java.util.TreeMap; 016 017import org.apache.logging.log4j.LogManager; 018import org.apache.logging.log4j.Logger; 019 020import edu.jas.poly.ExpVector; 021import edu.jas.poly.GenPolynomial; 022import edu.jas.poly.GenPolynomialRing; 023import edu.jas.structure.RingElem; 024 025 026/** 027 * Pair list management. The original Buchberger algorithm with criterions 028 * following Winkler in SAC-1, Kredel in ALDES/SAC-2, Kredel in MAS. Implemented 029 * using GenPolynomial, TreeMap and BitSet. 030 * @author Heinz Kredel 031 */ 032 033public class OrderedPairlist<C extends RingElem<C>> implements PairList<C> { 034 035 036 protected final List<GenPolynomial<C>> P; 037 038 039 protected final SortedMap<ExpVector, LinkedList<Pair<C>>> pairlist; 040 041 042 protected final List<BitSet> red; 043 044 045 protected final GenPolynomialRing<C> ring; 046 047 048 protected final Reduction<C> reduction; 049 050 051 protected boolean oneInGB = false; 052 053 054 protected boolean useCriterion4 = true; 055 056 057 protected int putCount; 058 059 060 protected int remCount; 061 062 063 protected final int moduleVars; 064 065 066 private static final Logger logger = LogManager.getLogger(OrderedPairlist.class); 067 068 069 /** 070 * Constructor. 071 */ 072 public OrderedPairlist() { 073 moduleVars = 0; 074 ring = null; 075 P = null; 076 pairlist = null; 077 red = null; 078 reduction = null; 079 putCount = 0; 080 remCount = 0; 081 } 082 083 084 /** 085 * Constructor. 086 * @param r polynomial factory. 087 */ 088 public OrderedPairlist(GenPolynomialRing<C> r) { 089 this(0, r); 090 } 091 092 093 /** 094 * Constructor. 095 * @param m number of module variables. 096 * @param r polynomial factory. 097 */ 098 public OrderedPairlist(int m, GenPolynomialRing<C> r) { 099 moduleVars = m; 100 ring = r; 101 P = new ArrayList<GenPolynomial<C>>(); 102 pairlist = new TreeMap<ExpVector, LinkedList<Pair<C>>>(ring.tord.getAscendComparator()); 103 //pairlist = new TreeMap( to.getSugarComparator() ); 104 red = new ArrayList<BitSet>(); 105 putCount = 0; 106 remCount = 0; 107 if (!ring.isCommutative()) {//ring instanceof GenSolvablePolynomialRing ) { 108 useCriterion4 = false; 109 } 110 reduction = new ReductionSeq<C>(); 111 } 112 113 114 /** 115 * Create a new PairList. 116 * @param r polynomial ring. 117 */ 118 public PairList<C> create(GenPolynomialRing<C> r) { 119 return new OrderedPairlist<C>(r); 120 } 121 122 123 /** 124 * Create a new PairList. 125 * @param m number of module variables. 126 * @param r polynomial ring. 127 */ 128 public PairList<C> create(int m, GenPolynomialRing<C> r) { 129 return new OrderedPairlist<C>(m, r); 130 } 131 132 133 /** 134 * toString. 135 */ 136 @Override 137 public String toString() { 138 StringBuffer s = new StringBuffer(this.getClass().getSimpleName() + "("); 139 //s.append("polys="+P.size()); 140 s.append("#put=" + putCount); 141 s.append(", #rem=" + remCount); 142 if (pairlist != null && pairlist.size() != 0) { 143 s.append(", size=" + pairlist.size()); 144 } 145 if (moduleVars > 0) { 146 s.append(", modv=" + moduleVars); 147 } 148 s.append(")"); 149 return s.toString(); 150 } 151 152 153 /** 154 * Put one Polynomial to the pairlist and reduction matrix. 155 * @param p polynomial. 156 * @return the index of the added polynomial. 157 */ 158 public synchronized int put(GenPolynomial<C> p) { 159 putCount++; 160 if (oneInGB) { 161 return P.size() - 1; 162 } 163 ExpVector e = p.leadingExpVector(); 164 int l = P.size(); 165 for (int j = 0; j < l; j++) { 166 GenPolynomial<C> pj = P.get(j); 167 ExpVector f = pj.leadingExpVector(); 168 if (moduleVars > 0) { 169 if (!reduction.moduleCriterion(moduleVars, e, f)) { 170 continue; // skip pair 171 } 172 } 173 ExpVector g = e.lcm(f); 174 Pair<C> pair = new Pair<C>(pj, p, j, l); 175 //System.out.println("pair.new = " + pair); 176 //multiple pairs under same keys -> list of pairs 177 LinkedList<Pair<C>> xl = pairlist.get(g); 178 if (xl == null) { 179 xl = new LinkedList<Pair<C>>(); 180 } 181 //xl.addLast( pair ); // first or last ? 182 xl.addFirst(pair); // first or last ? better for d- e-GBs 183 pairlist.put(g, xl); 184 } 185 //System.out.println("pairlist.keys@put = " + pairlist.keySet() ); 186 P.add(p); 187 BitSet redi = new BitSet(); 188 redi.set(0, l); 189 red.add(redi); 190 //System.out.println("pairlist.red = " + red); //.get( pair.j )); //pair); 191 //System.out.println("pairlist.key = " + pairlist.keySet() ); 192 return P.size() - 1; 193 } 194 195 196 /** 197 * Put all polynomials in F to the pairlist and reduction matrix. 198 * @param F polynomial list. 199 * @return the index of the last added polynomial. 200 */ 201 public int put(List<GenPolynomial<C>> F) { 202 int i = 0; 203 for (GenPolynomial<C> p : F) { 204 i = put(p); 205 } 206 return i; 207 } 208 209 210 /** 211 * Remove the next required pair from the pairlist and reduction matrix. 212 * Appy the criterions 3 and 4 to see if the S-polynomial is required. 213 * @return the next pair if one exists, otherwise null. 214 */ 215 public synchronized Pair<C> removeNext() { 216 if (oneInGB) { 217 return null; 218 } 219 Iterator<Map.Entry<ExpVector, LinkedList<Pair<C>>>> ip = pairlist.entrySet().iterator(); 220 221 Pair<C> pair = null; 222 boolean c = false; 223 int i, j; 224 225 while (!c && ip.hasNext()) { 226 Map.Entry<ExpVector, LinkedList<Pair<C>>> me = ip.next(); 227 ExpVector g = me.getKey(); 228 LinkedList<Pair<C>> xl = me.getValue(); 229 if (logger.isInfoEnabled()) { 230 logger.info("g = " + g); 231 } 232 pair = null; 233 while (!c && xl.size() > 0) { 234 pair = xl.removeFirst(); 235 // xl is also modified in pairlist 236 i = pair.i; 237 j = pair.j; 238 // System.out.println("pair(" + j + "," +i+") "); 239 if (useCriterion4) { 240 c = reduction.criterion4(pair.pi, pair.pj, g); 241 } else { 242 c = true; 243 } 244 //System.out.println("c4_o = " + c); 245 if (c) { 246 c = criterion3(i, j, g); 247 //System.out.println("c3_o = " + c); 248 } 249 red.get(j).clear(i); // set(i,false) jdk1.4 250 } 251 if (xl.size() == 0) { 252 ip.remove(); 253 // = pairlist.remove( g ); 254 } 255 } 256 if (!c) { 257 pair = null; 258 } else { 259 pair.maxIndex(P.size() - 1); 260 remCount++; // count only real pairs 261 if (logger.isDebugEnabled()) { 262 logger.info("pair(" + pair.j + "," + pair.i + ")"); 263 } 264 } 265 return pair; 266 } 267 268 269 /** 270 * Test if there is possibly a pair in the list. 271 * @return true if a next pair could exist, otherwise false. 272 */ 273 public synchronized boolean hasNext() { 274 return pairlist.size() > 0; 275 } 276 277 278 /** 279 * Get the list of polynomials. 280 * @return the polynomial list. 281 */ 282 public List<GenPolynomial<C>> getList() { 283 return P; 284 } 285 286 287 /** 288 * Set the list of polynomials. 289 * @param F the polynomial list. 290 */ 291 public void setList(List<GenPolynomial<C>> F) { 292 if (!P.isEmpty()) { 293 throw new IllegalArgumentException("P not empty"); 294 } 295 P.addAll(F); 296 for (int i = 0; i < P.size(); i++) { 297 BitSet redi = new BitSet(); 298 red.add(redi); 299 } 300 301 } 302 303 304 /** 305 * Get the size of the list of polynomials. 306 * @return size of the polynomial list. 307 */ 308 public int size() { 309 return P.size(); 310 } 311 312 313 /** 314 * Get the number of polynomials put to the pairlist. 315 * @return the number of calls to put. 316 */ 317 public synchronized int putCount() { 318 return putCount; 319 } 320 321 322 /** 323 * Get the number of required pairs removed from the pairlist. 324 * @return the number of non null pairs delivered. 325 */ 326 public synchronized int remCount() { 327 return remCount; 328 } 329 330 331 /** 332 * Put the ONE-Polynomial to the pairlist. 333 * @param one polynomial. (no more required) 334 * @return the index of the last polynomial. 335 */ 336 public synchronized int putOne(GenPolynomial<C> one) { 337 if (one == null) { 338 return P.size() - 1; 339 } 340 if (!one.isONE()) { 341 return P.size() - 1; 342 } 343 return putOne(); 344 } 345 346 347 /** 348 * Put the ONE-Polynomial to the pairlist. 349 * @return the index of the last polynomial. 350 */ 351 public synchronized int putOne() { 352 putCount++; 353 oneInGB = true; 354 pairlist.clear(); 355 P.clear(); 356 P.add(ring.getONE()); 357 red.clear(); 358 logger.info("outOne " + this.toString()); 359 return P.size() - 1; 360 } 361 362 363 /** 364 * GB criterium 3. 365 * @return true if the S-polynomial(i,j) is required. 366 */ 367 public boolean criterion3(int i, int j, ExpVector eij) { 368 // assert i < j; 369 boolean s = red.get(j).get(i); 370 if (!s) { 371 logger.warn("c3.s false for " + j + " " + i); 372 return s; 373 } 374 // now s = true; 375 for (int k = 0; k < P.size(); k++) { 376 // System.out.println("i , k , j "+i+" "+k+" "+j); 377 if (i != k && j != k) { 378 GenPolynomial<C> A = P.get(k); 379 ExpVector ek = A.leadingExpVector(); 380 boolean m = eij.multipleOf(ek); 381 if (m) { 382 if (k < i) { 383 // System.out.println("k < i "+k+" "+i); 384 s = red.get(i).get(k) || red.get(j).get(k); 385 } else if (i < k && k < j) { 386 // System.out.println("i < k < j "+i+" "+k+" "+j); 387 s = red.get(k).get(i) || red.get(j).get(k); 388 } else if (j < k) { 389 //System.out.println("j < k "+j+" "+k); 390 s = red.get(k).get(i) || red.get(k).get(j); 391 } 392 //System.out.println("s."+k+" = " + s); 393 if (!s) { 394 return s; 395 } 396 } 397 } 398 } 399 return true; 400 } 401 402}