Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.application;
006
007
008import edu.jas.kern.PrettyPrint;
009import edu.jas.poly.GenPolynomial;
010import edu.jas.poly.PolyUtil;
011import edu.jas.structure.GcdRingElem;
012
013
014/**
015 * Residue ring element based on GenPolynomial with RingElem interface. Objects
016 * of this class are (nearly) immutable.
017 * @author Heinz Kredel
018 */
019public class Residue<C extends GcdRingElem<C>> implements GcdRingElem<Residue<C>> {
020
021
022    /**
023     * Residue class factory data structure.
024     */
025    public final ResidueRing<C> ring;
026
027
028    /**
029     * Value part of the element data structure.
030     */
031    public final GenPolynomial<C> val;
032
033
034    /**
035     * Flag to remember if this residue element is a unit. -1 is unknown, 1 is
036     * unit, 0 not a unit.
037     */
038    protected int isunit = -1; // initially unknown
039
040
041    /**
042     * The constructor creates a Residue object from a ring factory.
043     * @param r residue ring factory.
044     */
045    public Residue(ResidueRing<C> r) {
046        this(r, r.ring.getZERO(), 0);
047    }
048
049
050    /**
051     * The constructor creates a Residue object from a ring factory and a
052     * polynomial.
053     * @param r residue ring factory.
054     * @param a polynomial.
055     */
056    public Residue(ResidueRing<C> r, GenPolynomial<C> a) {
057        this(r, a, -1);
058    }
059
060
061    /**
062     * The constructor creates a Residue object from a ring factory, a
063     * polynomial and an indicator if a is a unit.
064     * @param r residue ring factory.
065     * @param a polynomial.
066     * @param u isunit indicator, -1, 0, 1.
067     */
068    public Residue(ResidueRing<C> r, GenPolynomial<C> a, int u) {
069        ring = r;
070        val = ring.ideal.normalform(a); //.monic() no go
071        if (u == 0 || u == 1) {
072            isunit = u;
073            return;
074        }
075        if (val.isZERO()) {
076            isunit = 0;
077            return;
078        }
079        if (ring.isField()) {
080            isunit = 1;
081            return;
082        }
083        if (val.isUnit()) {
084            isunit = 1;
085            //} else { // not possible
086            //isunit = 0;
087        }
088        isunit = -1;
089    }
090
091
092    /**
093     * Get the corresponding element factory.
094     * @return factory for this Element.
095     * @see edu.jas.structure.Element#factory()
096     */
097    public ResidueRing<C> factory() {
098        return ring;
099    }
100
101
102    /**
103     * Clone this.
104     * @see java.lang.Object#clone()
105     */
106    @Override
107    public Residue<C> copy() {
108        return new Residue<C>(ring, val, isunit);
109    }
110
111
112    /**
113     * Is Residue zero.
114     * @return If this is 0 then true is returned, else false.
115     * @see edu.jas.structure.RingElem#isZERO()
116     */
117    public boolean isZERO() {
118        return val.isZERO();
119    }
120
121
122    /**
123     * Is Residue one.
124     * @return If this is 1 then true is returned, else false.
125     * @see edu.jas.structure.RingElem#isONE()
126     */
127    public boolean isONE() {
128        return val.isONE();
129    }
130
131
132    /**
133     * Is Residue unit.
134     * @return If this is a unit then true is returned, else false.
135     * @see edu.jas.structure.RingElem#isUnit()
136     */
137    public boolean isUnit() {
138        if (isunit > 0) {
139            return true;
140        }
141        if (isunit == 0) {
142            return false;
143        }
144        // not jet known
145        boolean u = ring.ideal.isUnit(val);
146        if (u) {
147            isunit = 1;
148        } else {
149            isunit = 0;
150        }
151        return (u);
152    }
153
154
155    /**
156     * Is Residue a constant.
157     * @return true if this.val is a constant polynomial, else false.
158     */
159    public boolean isConstant() {
160        return val.isConstant();
161    }
162
163
164    /**
165     * Get the String representation as RingElem.
166     * @see java.lang.Object#toString()
167     */
168    @Override
169    public String toString() {
170        if (PrettyPrint.isTrue()) {
171            return val.toString(ring.ring.getVars());
172        }
173        return "Residue[ " + val.toString() + " mod " + ring.toString() + " ]";
174    }
175
176
177    /**
178     * Get a scripting compatible string representation.
179     * @return script compatible representation for this Element.
180     * @see edu.jas.structure.Element#toScript()
181     */
182    @Override
183    public String toScript() {
184        // Python case
185        return val.toScript();
186        //         return "PolyResidue( " + val.toScript() 
187        //                         + ", " + ring.toScript() + " )";
188    }
189
190
191    /**
192     * Get a scripting compatible string representation of the factory.
193     * @return script compatible representation for this ElemFactory.
194     * @see edu.jas.structure.Element#toScriptFactory()
195     */
196    @Override
197    public String toScriptFactory() {
198        // Python case
199        return factory().toScript();
200    }
201
202
203    /**
204     * Residue comparison.
205     * @param b Residue.
206     * @return sign(this-b), 0 means that this and b are equivalent in this
207     *         residue class ring.
208     */
209    @Override
210    public int compareTo(Residue<C> b) {
211        GenPolynomial<C> v = b.val;
212        if (!ring.equals(b.ring)) {
213            v = ring.ideal.normalform(v);
214        }
215        return val.compareTo(v);
216    }
217
218
219    /**
220     * Comparison with any other object.
221     * @see java.lang.Object#equals(java.lang.Object)
222     * @return true means that this and b are equivalent in this residue class
223     *         ring.
224     */
225    @Override
226    @SuppressWarnings("unchecked")
227    public boolean equals(Object b) {
228        if (!(b instanceof Residue)) {
229            return false;
230        }
231        Residue<C> a = null;
232        try {
233            a = (Residue<C>) b;
234        } catch (ClassCastException e) {
235        }
236        if (a == null) {
237            return false;
238        }
239        return compareTo(a) == 0;
240    }
241
242
243    /**
244     * Hash code for this residue.
245     * @see java.lang.Object#hashCode()
246     */
247    @Override
248    public int hashCode() {
249        int h;
250        h = ring.hashCode();
251        h = 37 * h + val.hashCode();
252        return h;
253    }
254
255
256    /**
257     * Residue absolute value.
258     * @return the absolute value of this.
259     * @see edu.jas.structure.RingElem#abs()
260     */
261    public Residue<C> abs() {
262        return new Residue<C>(ring, val.abs(), isunit);
263    }
264
265
266    /**
267     * Residue summation.
268     * @param S Residue.
269     * @return this+S.
270     */
271    public Residue<C> sum(Residue<C> S) {
272        return new Residue<C>(ring, val.sum(S.val));
273    }
274
275
276    /**
277     * Residue negate.
278     * @return -this.
279     * @see edu.jas.structure.RingElem#negate()
280     */
281    public Residue<C> negate() {
282        return new Residue<C>(ring, val.negate(), isunit);
283    }
284
285
286    /**
287     * Residue signum.
288     * @see edu.jas.structure.RingElem#signum()
289     * @return signum(this).
290     */
291    public int signum() {
292        return val.signum();
293    }
294
295
296    /**
297     * Residue subtraction.
298     * @param S Residue.
299     * @return this-S.
300     */
301    public Residue<C> subtract(Residue<C> S) {
302        return new Residue<C>(ring, val.subtract(S.val));
303    }
304
305
306    /**
307     * Residue division.
308     * @param S Residue.
309     * @return this/S.
310     */
311    public Residue<C> divide(Residue<C> S) {
312        if (ring.isField()) {
313            return multiply(S.inverse());
314        }
315        GenPolynomial<C> x = PolyUtil.<C> basePseudoDivide(val, S.val);
316        return new Residue<C>(ring, x);
317    }
318
319
320    /**
321     * Residue inverse.
322     * @see edu.jas.structure.RingElem#inverse()
323     * @return S with S = 1/this if defined.
324     */
325    public Residue<C> inverse() {
326        GenPolynomial<C> x = ring.ideal.inverse(val);
327        return new Residue<C>(ring, x, 1);
328    }
329
330
331    /**
332     * Residue remainder.
333     * @param S Residue.
334     * @return this - (this/S)*S.
335     */
336    public Residue<C> remainder(Residue<C> S) {
337        //GenPolynomial<C> x = val.remainder( S.val );
338        GenPolynomial<C> x = PolyUtil.<C> baseSparsePseudoRemainder(val, S.val);
339        return new Residue<C>(ring, x);
340    }
341
342
343    /**
344     * Residue multiplication.
345     * @param S Residue.
346     * @return this*S.
347     */
348    public Residue<C> multiply(Residue<C> S) {
349        GenPolynomial<C> x = val.multiply(S.val);
350        int i = -1;
351        if (isunit == 1 && S.isunit == 1) {
352            i = 1;
353        } else if (isunit == 0 || S.isunit == 0) {
354            i = 0;
355        }
356        return new Residue<C>(ring, x, i);
357    }
358
359
360    /**
361     * Residue monic.
362     * @return this with monic value part.
363     */
364    public Residue<C> monic() {
365        return new Residue<C>(ring, val.monic(), isunit);
366    }
367
368
369    /**
370     * Greatest common divisor.
371     * @param b other element.
372     * @return gcd(this,b).
373     */
374    public Residue<C> gcd(Residue<C> b) {
375        GenPolynomial<C> x = ring.engine.gcd(val, b.val);
376        int i = -1; // gcd might become a unit
377        if (x.isONE()) {
378            i = 1;
379            //} else {
380            //System.out.println("Residue gcd = " + x);
381        }
382        if (isunit == 1 && b.isunit == 1) {
383            i = 1;
384        }
385        return new Residue<C>(ring, x, i);
386    }
387
388
389    /**
390     * Extended greatest common divisor. <b>Note: </b>Not implemented, throws
391     * UnsupportedOperationException.
392     * @param b other element.
393     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
394     */
395    public Residue<C>[] egcd(Residue<C> b) {
396        throw new UnsupportedOperationException("egcd not implemented");
397    }
398}