001/*
002 * $Id$
003 */
004
005package edu.jas.ps;
006
007
008import java.io.Serializable;
009import java.util.BitSet;
010import java.util.HashMap;
011import java.util.HashSet;
012
013import edu.jas.poly.ExpVector;
014import edu.jas.poly.GenPolynomial;
015import edu.jas.poly.GenPolynomialRing;
016import edu.jas.structure.RingElem;
017
018
019/**
020 * Abstract class for generating functions for coefficients of multivariate
021 * power series. This class handles the caching itself.
022 * @param <C> ring element type
023 * @author Heinz Kredel
024 */
025
026public abstract class MultiVarCoefficients<C extends RingElem<C>> implements Serializable {
027
028
029    /**
030     * Ring factory for polynomials.
031     */
032    public final GenPolynomialRing<C> pfac;
033
034
035    /**
036     * Cache for already computed coefficients.
037     */
038    public final HashMap<Long, GenPolynomial<C>> coeffCache;
039
040
041    /**
042     * Indicator if all coefficients of a homogeneous degree have been
043     * constructed.
044     */
045    public final BitSet homCheck;
046
047
048    /**
049     * Cache for known zero coefficients. Required because zero coefficients are
050     * not stored in the polynomials.
051     */
052    public final HashSet<ExpVector> zeroCache;
053
054
055    /**
056     * Public constructor.
057     * @param pf multivariate power series ring factory.
058     */
059    public MultiVarCoefficients(MultiVarPowerSeriesRing<C> pf) {
060        this(pf.polyRing(), new HashMap<Long, GenPolynomial<C>>(), new HashSet<ExpVector>());
061    }
062
063
064    /*
065     * Public constructor with some pre-filled caches.
066     * @param pf multivariate power series ring factory.
067     * @param hc pre-filled homogeneous check bit-set.
068    public MultiVarCoefficients(MultiVarPowerSeriesRing<C> pf, BitSet hc) {
069        this(pf.polyRing(), new HashMap<Long, GenPolynomial<C>>(), new HashSet<ExpVector>(), hc);
070    }
071     */
072
073
074    /**
075     * Public constructor.
076     * @param pf polynomial ring factory.
077     */
078    public MultiVarCoefficients(GenPolynomialRing<C> pf) {
079        this(pf, new HashMap<Long, GenPolynomial<C>>(), new HashSet<ExpVector>());
080    }
081
082
083    /**
084     * Public with pre-filled coefficient cache.
085     * @param pf polynomial ring factory.
086     * @param cache pre-filled coefficient cache.
087     */
088    public MultiVarCoefficients(GenPolynomialRing<C> pf, HashMap<Long, GenPolynomial<C>> cache) {
089        this(pf, cache, new HashSet<ExpVector>());
090    }
091
092
093    /**
094     * Public constructor with pre-filled caches.
095     * @param pf polynomial ring factory.
096     * @param cache pre-filled coefficient cache.
097     * @param zeros pre-filled zero coefficient cache.
098     */
099    public MultiVarCoefficients(GenPolynomialRing<C> pf, HashMap<Long, GenPolynomial<C>> cache,
100            HashSet<ExpVector> zeros) {
101        this(pf, cache, zeros, new BitSet());
102    }
103
104
105    /*
106     * Public constructor with pre-filled caches.
107     * @param pf polynomial ring factory.
108     * @param hc pre-filled homogeneous check bit-set.
109    public MultiVarCoefficients(GenPolynomialRing<C> pf, BitSet hc) {
110        this(pf, new HashMap<Long, GenPolynomial<C>>(), new HashSet<ExpVector>(), hc);
111    }
112     */
113
114
115    /**
116     * Public constructor with pre-filled caches.
117     * @param pf polynomial ring factory.
118     * @param cache pre-filled coefficient cache.
119     * @param hc pre-filled homogeneous check bit-set.
120     */
121    public MultiVarCoefficients(GenPolynomialRing<C> pf, HashMap<Long, GenPolynomial<C>> cache, BitSet hc) {
122        this(pf, cache, new HashSet<ExpVector>(), hc);
123    }
124
125
126    /**
127     * Public constructor with pre-filled caches.
128     * @param pf polynomial ring factory.
129     * @param cache pre-filled coefficient cache.
130     * @param zeros pre-filled zero coefficient cache.
131     * @param hc pre-filled homogeneous check bit-set.
132     */
133    public MultiVarCoefficients(GenPolynomialRing<C> pf, HashMap<Long, GenPolynomial<C>> cache,
134            HashSet<ExpVector> zeros, BitSet hc) {
135        pfac = pf;
136        coeffCache = cache;
137        zeroCache = zeros;
138        homCheck = hc;
139    }
140
141
142    /**
143     * Get cached coefficient or generate coefficient.
144     * @param index of requested coefficient.
145     * @return coefficient at index.
146     */
147    public C get(ExpVector index) {
148        //if (index.signum() < 0) { // better assert
149        //    throw new IllegalArgumentException("negative signum not allowed " + index);
150        //}
151        //if (coeffCache == null) { // not possible
152        //    return generate(index);
153        //}
154        long tdeg = index.totalDeg();
155        GenPolynomial<C> p = coeffCache.get(tdeg);
156        if (p == null) {
157            p = pfac.getZERO().copy();
158            coeffCache.put(tdeg, p);
159        }
160        C c = p.coefficient(index);
161        if (!c.isZERO()) {
162            return c;
163        }
164        if (homCheck.get((int) tdeg)) { // rely on p
165            return c;
166        }
167        if (zeroCache.contains(index)) {
168            return c;
169        }
170        C g = generate(index);
171        if (g.isZERO()) {
172            zeroCache.add(index);
173        } else {
174            p.doPutToMap(index, g);
175        }
176        return g;
177    }
178
179
180    /**
181     * Homogeneous part.
182     * @param tdeg requested degree.
183     * @return polynomial part of given degree.
184     */
185    public GenPolynomial<C> getHomPart(long tdeg) {
186        if (coeffCache == null) {
187            throw new IllegalArgumentException("null cache not allowed");
188        }
189        GenPolynomial<C> p = coeffCache.get(tdeg);
190        if (p == null) {
191            p = pfac.getZERO().copy();
192            coeffCache.put(tdeg, p);
193        } 
194        // trust contents?
195        if (homCheck.get((int) tdeg)) {
196            return p;
197        }
198        // check correct contents or generate coefficients
199        ExpVectorIterable eiter = new ExpVectorIterable(pfac.nvar, tdeg);
200        for (ExpVector e : eiter) {
201            if (zeroCache.contains(e)) {
202                if ( !zeroCache.remove(e) ) { // clean-up unused
203                    System.out.println("not removed e = " + e); // cannot happen
204                }
205                continue;
206            }
207            if (!p.coefficient(e).isZERO()) {
208                continue;
209            }
210            C g = generate(e);
211            if (!g.isZERO()) {
212                p.doPutToMap(e, g);
213            }
214        }
215        homCheck.set((int) tdeg);
216        //System.out.println("homCheck = " + homCheck);
217        //System.out.println("coeffCache = " + coeffCache.keySet());
218        return p;
219    }
220
221
222    /**
223     * Generate coefficient.
224     * @param index of requested coefficient.
225     * @return coefficient at index.
226     */
227    protected abstract C generate(ExpVector index);
228
229}