001 /*
002 * $Id: MultiplicativeSet.java 3423 2010-12-24 10:56:50Z kredel $
003 */
004
005 package edu.jas.gbufd;
006
007
008 import java.io.Serializable;
009 import java.util.ArrayList;
010 import java.util.List;
011
012 import org.apache.log4j.Logger;
013
014 import edu.jas.poly.GenPolynomial;
015 import edu.jas.poly.GenPolynomialRing;
016 import edu.jas.structure.GcdRingElem;
017
018
019 /**
020 * Multiplicative set of polynomials. a, b in M implies a*b in M, 1 in M.
021 * @param <C> coefficient type
022 * @author Heinz Kredel.
023 */
024 public class MultiplicativeSet<C extends GcdRingElem<C>> implements Serializable {
025
026
027 private static final Logger logger = Logger.getLogger(MultiplicativeSet.class);
028
029
030 private final boolean debug = logger.isDebugEnabled();
031
032
033 /**
034 * Data structure.
035 */
036 public final List<GenPolynomial<C>> mset;
037
038
039 /**
040 * Polynomial ring factory.
041 */
042 public final GenPolynomialRing<C> ring;
043
044
045 /**
046 * MultiplicativeSet constructor. Constructs an empty multiplicative set.
047 * @param ring polynomial ring factory for coefficients.
048 */
049 public MultiplicativeSet(GenPolynomialRing<C> ring) {
050 this(ring, new ArrayList<GenPolynomial<C>>());
051 if (ring == null) {
052 throw new IllegalArgumentException("only for non null rings");
053 }
054 }
055
056
057 /**
058 * MultiplicativeSet constructor.
059 * @param ring polynomial ring factory for coefficients.
060 * @param ms a list of non-zero polynomials.
061 */
062 protected MultiplicativeSet(GenPolynomialRing<C> ring, List<GenPolynomial<C>> ms) {
063 if (ms == null || ring == null) {
064 throw new IllegalArgumentException("only for non null parts");
065 }
066 this.ring = ring;
067 mset = ms;
068 }
069
070
071 /**
072 * toString.
073 * @see java.lang.Object#toString()
074 */
075 @Override
076 public String toString() {
077 return "MultiplicativeSet" + mset;
078 }
079
080
081 /**
082 * Equals.
083 * @param ob an Object.
084 * @return true if this is equal to o, else false.
085 */
086 @Override
087 @SuppressWarnings("unchecked")
088 public boolean equals(Object ob) {
089 MultiplicativeSet<C> c = null;
090 try {
091 c = (MultiplicativeSet<C>) ob;
092 } catch (ClassCastException e) {
093 return false;
094 }
095 if (c == null) {
096 return false;
097 }
098 if (!ring.equals(c.ring)) {
099 return false;
100 }
101 return mset.equals(c.mset);
102 }
103
104
105 /**
106 * Hash code for this condition.
107 * @see java.lang.Object#hashCode()
108 */
109 @Override
110 public int hashCode() {
111 int h;
112 h = ring.hashCode();
113 h = h << 17;
114 h += mset.hashCode();
115 return h;
116 }
117
118
119 /**
120 * Is set.
121 * @return true if this is the empty set, else false.
122 */
123 public boolean isEmpty() {
124 return mset.size() == 0;
125 }
126
127
128 /**
129 * Test if a polynomial is contained in this multiplicative set.
130 * @param c polynomial searched in mset.
131 * @return true, if c = prod_{m in mset} m, else false
132 */
133 public boolean contains(GenPolynomial<C> c) {
134 if (c == null || c.isZERO()) {
135 return false;
136 }
137 if (c.isConstant()) {
138 return true;
139 }
140 if (mset.size() == 0) {
141 return false;
142 }
143 GenPolynomial<C> d = c;
144 for (GenPolynomial<C> n : mset) {
145 // System.out.println("mset n = " + n);
146 if (n.isONE()) { // do not use 1
147 continue;
148 }
149 GenPolynomial<C> q, r;
150 do {
151 GenPolynomial<C>[] qr = d.quotientRemainder(n);
152 q = qr[0];
153 r = qr[1];
154 // System.out.println("q = " + q + ", r = " + r + ", d = " + d +
155 // ", n = " + n);
156 if (r != null && !r.isZERO()) {
157 continue;
158 }
159 if (q != null && q.isConstant()) {
160 return true;
161 }
162 d = q;
163 } while (r.isZERO() && !d.isConstant());
164 }
165 return d.isConstant(); // false
166 }
167
168
169 /**
170 * Test if a list of polynomials is contained in multiplicative set.
171 * @param L list of polynomials to be searched in mset.
172 * @return true, if all c in L are in mset, else false
173 */
174 public boolean contains(List<GenPolynomial<C>> L) {
175 if (L == null || L.size() == 0) {
176 return true;
177 }
178 for (GenPolynomial<C> c : L) {
179 if (!contains(c)) {
180 return false;
181 }
182 }
183 return true;
184 }
185
186
187 /**
188 * Add polynomial to mset.
189 * @param cc polynomial to be added to mset.
190 * @return new multiplicative set. <b>Note:</b> must be overridden in
191 * sub-classes.
192 */
193 public MultiplicativeSet<C> add(GenPolynomial<C> cc) {
194 if (cc == null || cc.isZERO() || cc.isConstant()) {
195 return this;
196 }
197 if (ring.coFac.isField()) {
198 cc = cc.monic();
199 }
200 List<GenPolynomial<C>> list;
201 if (mset.size() == 0) {
202 list = new ArrayList<GenPolynomial<C>>(1);
203 list.add(cc);
204 return new MultiplicativeSet<C>(ring, list);
205 }
206 GenPolynomial<C> c = removeFactors(cc);
207 if (c.isConstant()) {
208 logger.info("skipped unit or constant = " + c);
209 return this;
210 }
211 if (ring.coFac.isField()) {
212 c = c.monic();
213 }
214 if (mset.size() == 0) {
215 logger.info("added to empty mset = " + c);
216 } else {
217 logger.info("added to mset = " + c);
218 }
219 list = new ArrayList<GenPolynomial<C>>(mset);
220 list.add(c);
221 return new MultiplicativeSet<C>(ring, list);
222 }
223
224
225 /**
226 * Replace polynomial list of mset.
227 * @param L polynomial list to replace mset.
228 * @return new multiplicative set. <b>Note:</b> must be overridden in
229 * sub-classes.
230 */
231 public MultiplicativeSet<C> replace(List<GenPolynomial<C>> L) {
232 MultiplicativeSet<C> ms = new MultiplicativeSet<C>(ring);
233 if (L == null || L.size() == 0) {
234 return ms;
235 }
236 for (GenPolynomial<C> p : L) {
237 ms = ms.add(p);
238 }
239 return ms;
240 }
241
242
243 /**
244 * Remove factors by mset factors division.
245 * @param cc polynomial to be removed factors from mset.
246 * @return quotient polynomial.
247 */
248 public GenPolynomial<C> removeFactors(GenPolynomial<C> cc) {
249 if (cc == null || cc.isZERO() || cc.isConstant()) {
250 return cc;
251 }
252 if (mset.size() == 0) {
253 return cc;
254 }
255 GenPolynomial<C> c = cc;
256 for (GenPolynomial<C> n : mset) {
257 if (n.isConstant()) { // do not use 1, should not be in mset
258 continue;
259 }
260 GenPolynomial<C> q, r;
261 do {
262 GenPolynomial<C>[] qr = c.quotientRemainder(n);
263 q = qr[0];
264 r = qr[1];
265 if (r != null && !r.isZERO()) {
266 continue;
267 }
268 if (q != null && q.isConstant()) {
269 return q;
270 }
271 c = q;
272 } while (r.isZERO() && !c.isConstant());
273 }
274 return c;
275 }
276
277
278 /**
279 * Remove factors by mset factors division.
280 * @param L list of polynomial to be removed factors from mset.
281 * @return quotient polynomial list.
282 */
283 public List<GenPolynomial<C>> removeFactors(List<GenPolynomial<C>> L) {
284 if (L == null || L.size() == 0) {
285 return L;
286 }
287 if (mset.size() == 0) {
288 return L;
289 }
290 List<GenPolynomial<C>> M = new ArrayList<GenPolynomial<C>>(L.size());
291 for (GenPolynomial<C> p : L) {
292 p = removeFactors(p);
293 // nono, really: if ( !p.isConstant() ) {
294 M.add(p);
295 }
296 return M;
297 }
298
299 }