001 /*
002 * $Id: Factors.java 3329 2010-09-19 19:02:10Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.io.Serializable;
009 import java.util.List;
010 import java.util.ArrayList;
011
012 import edu.jas.poly.AlgebraicNumber;
013 import edu.jas.poly.AlgebraicNumberRing;
014 import edu.jas.poly.GenPolynomial;
015 import edu.jas.poly.GenPolynomialRing;
016 import edu.jas.poly.PolynomialList;
017 import edu.jas.structure.GcdRingElem;
018
019
020 /**
021 * Container for the factors of absolute factorization.
022 * @author Heinz Kredel
023 * @param <C> coefficient type
024 */
025
026 public class Factors<C extends GcdRingElem<C>> implements Comparable<Factors<C>>, Serializable {
027
028
029 /**
030 * Original (irreducible) polynomial to be factored with coefficients from C.
031 */
032 public final GenPolynomial<C> poly;
033
034
035 /**
036 * Algebraic field extension over C. Should be null, if p is absolutely
037 * irreducible.
038 */
039 public final AlgebraicNumberRing<C> afac;
040
041
042 /**
043 * Original polynomial to be factored with coefficients from
044 * AlgebraicNumberRing<C>. Should be null, if p is absolutely irreducible.
045 */
046 public final GenPolynomial<AlgebraicNumber<C>> apoly;
047
048
049 /**
050 * List of factors with coefficients from AlgebraicNumberRing<C>. Should be
051 * null, if p is absolutely irreducible.
052 */
053 public final List<GenPolynomial<AlgebraicNumber<C>>> afactors;
054
055
056 /**
057 * List of factors with coefficients from AlgebraicNumberRing<AlgebraicNumber<C>>.
058 * Should be null, if p is absolutely irreducible.
059 */
060 public final List<Factors<AlgebraicNumber<C>>> arfactors;
061
062
063 /**
064 * Constructor.
065 * @param p absolute irreducible GenPolynomial.
066 */
067 public Factors(GenPolynomial<C> p) {
068 this(p, null, null, null, null);
069 }
070
071
072 /**
073 * Constructor.
074 * @param p irreducible GenPolynomial over C.
075 * @param af algebraic extension field of C where p has factors from afact.
076 * @param ap GenPolynomial p represented with coefficients from af.
077 * @param afact absolute irreducible factors of p with coefficients from af.
078 */
079 public Factors(GenPolynomial<C> p, AlgebraicNumberRing<C> af, GenPolynomial<AlgebraicNumber<C>> ap,
080 List<GenPolynomial<AlgebraicNumber<C>>> afact) {
081 this(p, af, ap, afact, null);
082 }
083
084
085 /**
086 * Constructor.
087 * @param p irreducible GenPolynomial over C.
088 * @param af algebraic extension field of C where p has factors from afact.
089 * @param ap GenPolynomial p represented with coefficients from af.
090 * @param afact absolute irreducible factors of p with coefficients from af.
091 * @param arfact further absolute irreducible factors of p with coefficients from extensions of af.
092 */
093 public Factors(GenPolynomial<C> p, AlgebraicNumberRing<C> af, GenPolynomial<AlgebraicNumber<C>> ap,
094 List<GenPolynomial<AlgebraicNumber<C>>> afact, List<Factors<AlgebraicNumber<C>>> arfact) {
095 poly = p;
096 afac = af;
097 apoly = ap;
098 afactors = afact;
099 arfactors = arfact;
100 }
101
102
103 /**
104 * Get the String representation.
105 * @see java.lang.Object#toString()
106 */
107 @Override
108 public String toString() {
109 StringBuffer sb = new StringBuffer();
110 sb.append(poly.toString());
111 if (afac == null) {
112 return sb.toString();
113 }
114 sb.append(" = ");
115 boolean first = true;
116 for (GenPolynomial<AlgebraicNumber<C>> ap : afactors) {
117 if (first) {
118 first = false;
119 } else {
120 sb.append(", ");
121 }
122 sb.append(ap.toString());
123 }
124 sb.append("\n ## over " + afac.toString() + "\n");
125 if (arfactors == null) {
126 return sb.toString();
127 }
128 first = true;
129 for (Factors<AlgebraicNumber<C>> arp : arfactors) {
130 if (first) {
131 first = false;
132 } else {
133 sb.append(",\n");
134 }
135 sb.append(arp.toString());
136 }
137 return sb.toString();
138 }
139
140
141 /**
142 * Get a scripting compatible string representation.
143 * @return script compatible representation for this container.
144 * @see edu.jas.structure.ElemFactory#toScript()
145 */
146 public String toScript() {
147 // Python case
148 StringBuffer sb = new StringBuffer();
149 //sb.append(poly.toScript());
150 if (afac == null) {
151 return sb.toString();
152 }
153 //sb.append(" =\n");
154 boolean first = true;
155 for (GenPolynomial<AlgebraicNumber<C>> ap : afactors) {
156 if (first) {
157 first = false;
158 } else {
159 sb.append("\n * ");
160 }
161 //sb.append("( " + ap.toScript() + " )");
162 sb.append(ap.toScript());
163 }
164 sb.append(" ## over " + afac.toScript() + "\n");
165 if (arfactors == null) {
166 return sb.toString();
167 }
168 first = true;
169 for (Factors<AlgebraicNumber<C>> arp : arfactors) {
170 if (first) {
171 first = false;
172 } else {
173 sb.append("\n * ");
174 }
175 sb.append(arp.toScript());
176 }
177 return sb.toString();
178 }
179
180
181 /**
182 * Hash code for this Factors.
183 * @see java.lang.Object#hashCode()
184 */
185 @Override
186 public int hashCode() {
187 int h;
188 h = poly.hashCode();
189 if (afac == null) {
190 return h;
191 }
192 h = (h << 27);
193 h += afac.hashCode();
194 if ( afactors != null ) {
195 h = (h << 27);
196 h += afactors.hashCode();
197 }
198 if ( arfactors != null ) {
199 h = (h << 27);
200 h += arfactors.hashCode();
201 }
202 return h;
203 }
204
205
206 /**
207 * Comparison with any other object.
208 * @see java.lang.Object#equals(java.lang.Object)
209 */
210 @Override
211 @SuppressWarnings("unchecked")
212 public boolean equals(Object B) {
213 if (!(B instanceof Factors)) {
214 return false;
215 }
216 Factors<C> a = null;
217 try {
218 a = (Factors<C>) B;
219 } catch (ClassCastException ignored) {
220 }
221 if (a == null) {
222 return false;
223 }
224 return this.compareTo(a) == 0;
225 }
226
227
228 /**
229 * Comparison.
230 * @param facs factors container.
231 * @return sign(this.poly-facs.poly) lexicographic >
232 * sign(afac.modul-facs.afac.modul)
233 * lexicographic > afactors.compareTo(facs.afactors)
234 * lexicographic > arfactors[i].compareTo(facs.arfactors[i])
235 */
236 public int compareTo(Factors<C> facs) {
237 int s = poly.compareTo(facs.poly);
238 //System.out.println("s1 = " + s);
239 if (s != 0) {
240 return s;
241 }
242 if (afac == null) {
243 return -1;
244 }
245 if (facs.afac == null) {
246 return +1;
247 }
248 s = afac.modul.compareTo(facs.afac.modul);
249 //System.out.println("s2 = " + s);
250 if ( s != 0 ) {
251 return s;
252 }
253 GenPolynomialRing<AlgebraicNumber<C>> ar = afactors.get(0).ring;
254 GenPolynomialRing<AlgebraicNumber<C>> br = facs.afactors.get(0).ring;
255 PolynomialList<AlgebraicNumber<C>> ap = new PolynomialList<AlgebraicNumber<C>>(ar,afactors);
256 PolynomialList<AlgebraicNumber<C>> bp = new PolynomialList<AlgebraicNumber<C>>(br,facs.afactors);
257 s = ap.compareTo(bp);
258 //System.out.println("s3 = " + s);
259 if ( s != 0 ) {
260 return s;
261 }
262 if (arfactors == null && facs.arfactors == null) {
263 return 0;
264 }
265 if (arfactors == null) {
266 return -1;
267 }
268 if (facs.arfactors == null) {
269 return +1;
270 }
271 // lexicographic (?)
272 int i = 0;
273 for (Factors<AlgebraicNumber<C>> arp : arfactors) {
274 if ( i >= facs.arfactors.size() ) {
275 return +1;
276 }
277 Factors<AlgebraicNumber<C>> brp = facs.arfactors.get(i);
278 //System.out.println("arp = " + arp);
279 //System.out.println("brp = " + brp);
280 s = arp.compareTo(brp);
281 //System.out.println("s4 = " + s);
282 if ( s != 0 ) {
283 return s;
284 }
285 i++;
286 }
287 if ( i < facs.arfactors.size() ) {
288 return -1;
289 }
290 return 0;
291 }
292
293
294 /**
295 * Find largest extension field.
296 * @return largest extension field or null if no extension field
297 */
298 @SuppressWarnings("unchecked")
299 public AlgebraicNumberRing<C> findExtensionField() {
300 if (afac == null) {
301 return null;
302 }
303 if (arfactors == null) {
304 return afac;
305 }
306 AlgebraicNumberRing<C> arr = afac;
307 int depth = 1;
308 for (Factors<AlgebraicNumber<C>> af : arfactors) {
309 AlgebraicNumberRing<AlgebraicNumber<C>> aring = af.findExtensionField();
310 if (aring == null) {
311 continue;
312 }
313 int d = aring.depth();
314 if (d > depth) {
315 depth = d;
316 arr = (AlgebraicNumberRing<C>) (Object) aring;
317 }
318 }
319 return arr;
320 }
321
322
323 /**
324 * Get the list of factors at one level.
325 * @return list of algebraic factors
326 */
327 public List<GenPolynomial<AlgebraicNumber<C>>> getFactors() {
328 List<GenPolynomial<AlgebraicNumber<C>>> af = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
329 if ( afac == null ) {
330 return af;
331 }
332 af.addAll(afactors);
333 if ( arfactors == null ) {
334 return af;
335 }
336 for (Factors<AlgebraicNumber<C>> arp : arfactors) {
337 af.add( arp.poly );
338 }
339 return af;
340 }
341
342
343 /**
344 * Get the factor for polynomial.
345 * @return algebraic factor
346 */
347 public Factors<AlgebraicNumber<C>> getFactor(GenPolynomial<AlgebraicNumber<C>> p) {
348 if ( afac == null ) {
349 return null;
350 }
351 for (Factors<AlgebraicNumber<C>> arp : arfactors) {
352 if ( p.equals( arp.poly ) ) {
353 return arp;
354 }
355 }
356 return null;
357 }
358
359 }