/*
* $Id$
*/
package edu.jas.ps;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import org.apache.log4j.Logger;
import edu.jas.poly.ExpVector;
import edu.jas.structure.RingElem;
/**
* Pair list management. Implemented using MultiVarPowerSeries, TreeMap and
* BitSet.
* @author Heinz Kredel
*/
public class OrderedPairlist> {
protected final ArrayList> P;
protected final TreeMap>> pairlist;
protected final ArrayList red;
protected final MultiVarPowerSeriesRing ring;
protected final ReductionSeq reduction;
protected boolean oneInGB = false;
protected boolean useCriterion4 = true;
protected boolean useCriterion3 = true;
protected int putCount;
protected int remCount;
protected final int moduleVars;
private static final Logger logger = Logger.getLogger(OrderedPairlist.class);
/**
* Constructor for OrderedPairlist.
* @param r power series factory.
*/
public OrderedPairlist(MultiVarPowerSeriesRing r) {
this(0, r);
}
/**
* Constructor for OrderedPairlist.
* @param m number of module variables.
* @param r power series factory.
*/
public OrderedPairlist(int m, MultiVarPowerSeriesRing r) {
moduleVars = m;
ring = r;
P = new ArrayList>();
pairlist = new TreeMap>>(ring.polyRing().tord.getAscendComparator());
//pairlist = new TreeMap>>(ring.polyRing().tord.getDescendComparator());
red = new ArrayList();
putCount = 0;
remCount = 0;
reduction = new ReductionSeq();
}
/**
* toString.
*/
@Override
public String toString() {
StringBuffer s = new StringBuffer("OrderedPairlist(");
//s.append("ps="+P.size());
s.append("#put=" + putCount);
s.append(", #rem=" + remCount);
if (pairlist.size() != 0) {
s.append(", size=" + pairlist.size());
}
s.append(")");
return s.toString();
}
/**
* Put one power Series to the pairlist and reduction matrix.
* @param p power series.
* @return the index of the added power series.
*/
public synchronized int put(MultiVarPowerSeries p) {
putCount++;
if (oneInGB) {
return P.size() - 1;
}
ExpVector e = p.orderExpVector();
int l = P.size();
for (int j = 0; j < l; j++) {
MultiVarPowerSeries pj = P.get(j);
ExpVector f = pj.orderExpVector();
if (moduleVars > 0) {
if (!reduction.moduleCriterion(moduleVars, e, f)) {
continue; // skip pair
}
}
ExpVector g = e.lcm(f);
Pair pair = new Pair(pj, p, j, l);
// redi = (BitSet)red.get(j);
///if ( j < l ) redi.set( l );
// System.out.println("bitset."+j+" = " + redi );
//multiple pairs under same keys -> list of pairs
LinkedList> xl = pairlist.get(g);
if (xl == null) {
xl = new LinkedList>();
}
//xl.addLast( pair ); // first or last ?
xl.addFirst(pair); // first or last ? better for d- e-GBs
pairlist.put(g, xl);
}
// System.out.println("pairlist.keys@put = " + pairlist.keySet() );
P.add(p);
BitSet redi = new BitSet();
redi.set(0, l); // jdk 1.4
red.add(redi);
return P.size() - 1;
}
/**
* Remove the next required pair from the pairlist and reduction matrix.
* Apply the criterions 3 and 4 to see if the S-power-series is required.
* @return the next pair if one exists, otherwise null.
*/
public synchronized Pair removeNext() {
if (oneInGB) {
return null;
}
Iterator>>> ip = pairlist.entrySet().iterator();
Pair pair = null;
boolean c = false;
int i, j;
while (!c && ip.hasNext()) {
Map.Entry>> me = ip.next();
ExpVector g = me.getKey();
LinkedList> xl = me.getValue();
if (logger.isInfoEnabled())
logger.info("g = " + g);
pair = null;
while (!c && xl.size() > 0) {
pair = xl.removeFirst();
// xl is also modified in pairlist
i = pair.i;
j = pair.j;
// System.out.println("pair(" + j + "," +i+") ");
c = true;
if (useCriterion4) {
c = reduction.criterion4(pair.pi, pair.pj, g);
}
//System.out.println("c4 = " + c);
if (c && useCriterion3) {
c = criterion3(i, j, g);
//System.out.println("c3 = " + c);
}
red.get(j).clear(i); // set(i,false) jdk1.4
}
if (xl.size() == 0)
ip.remove();
// = pairlist.remove( g );
}
if (!c) {
pair = null;
} else {
remCount++; // count only real pairs
}
return pair;
}
/**
* Test if there is possibly a pair in the list.
* @return true if a next pair could exist, otherwise false.
*/
public synchronized boolean hasNext() {
return pairlist.size() > 0;
}
/**
* Get the list of power series.
* @return the power series list.
*/
public List> getList() {
return P;
}
/**
* Get the number of power series put to the pairlist.
* @return the number of calls to put.
*/
public synchronized int putCount() {
return putCount;
}
/**
* Get the number of required pairs removed from the pairlist.
* @return the number of non null pairs delivered.
*/
public synchronized int remCount() {
return remCount;
}
/**
* Put to ONE-power-series to the pairlist.
* @param one power series. (no more required)
* @return the index of the last power series.
*/
public synchronized int putOne(MultiVarPowerSeries one) {
putCount++;
if (one == null) {
return P.size() - 1;
}
if (!one.isONE()) {
return P.size() - 1;
}
return putOne();
}
/**
* Put the ONE-power-series to the pairlist.
* @return the index of the last power-series.
*/
public synchronized int putOne() {
oneInGB = true;
pairlist.clear();
P.clear();
P.add(ring.getONE());
red.clear();
return P.size() - 1;
}
/**
* GB criterion 3.
* @return true if the S-power-series(i,j) is required.
*/
public boolean criterion3(int i, int j, ExpVector eij) {
// assert i < j;
boolean s = red.get(j).get(i);
if (!s) {
logger.warn("c3.s false for " + j + " " + i);
return s;
}
// now s = true;
for (int k = 0; k < P.size(); k++) {
MultiVarPowerSeries A = P.get(k);
ExpVector ek = A.orderExpVector();
boolean m = eij.multipleOf(ek);
if (m) {
if (k < i) {
// System.out.println("k < i "+k+" "+i);
s = red.get(i).get(k) || red.get(j).get(k);
} else if (i < k && k < j) {
// System.out.println("i < k < j "+i+" "+k+" "+j);
s = red.get(k).get(i) || red.get(j).get(k);
} else if (j < k) {
//System.out.println("j < k "+j+" "+k);
s = red.get(k).get(i) || red.get(k).get(j);
}
//System.out.println("s."+k+" = " + s);
if (!s) {
return s;
}
}
}
return true;
}
}
Ads help maintain this website.