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