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