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