Source code

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