Source code

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