Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.application;
006
007
008import java.io.Reader;
009import java.util.ArrayList;
010import java.util.List;
011import java.util.Random;
012import java.util.SortedSet;
013import java.util.TreeSet;
014
015import org.apache.logging.log4j.Logger;
016import org.apache.logging.log4j.LogManager; 
017
018import edu.jas.gb.WordGroebnerBaseAbstract;
019import edu.jas.gb.WordGroebnerBaseSeq;
020import edu.jas.poly.GenWordPolynomial;
021import edu.jas.poly.GenWordPolynomialRing;
022import edu.jas.structure.GcdRingElem;
023import edu.jas.structure.QuotPairFactory;
024import edu.jas.structure.RingFactory;
025import edu.jas.structure.ValueFactory;
026
027
028/**
029 * WordResidue ring factory based on GenWordPolynomialRing with GcdRingFactory
030 * interface. Objects of this class are immutable.
031 * @author Heinz Kredel
032 */
033public class WordResidueRing<C extends GcdRingElem<C>> implements RingFactory<WordResidue<C>>,
034                QuotPairFactory<GenWordPolynomial<C>, WordResidue<C>>,
035                ValueFactory<GenWordPolynomial<C>, WordResidue<C>> {
036
037
038    private static final Logger logger = LogManager.getLogger(WordResidueRing.class);
039
040
041    //private static final boolean debug = logger.isDebugEnabled();
042
043
044    /**
045     * Groebner base engine.
046     */
047    protected final WordGroebnerBaseAbstract<C> bb;
048
049
050    /**
051     * Word polynomial ideal for the reduction.
052     */
053    public final WordIdeal<C> ideal;
054
055
056    /**
057     * Polynomial ring of the factory. Shortcut to ideal.list.ring.
058     */
059    public final GenWordPolynomialRing<C> ring;
060
061
062    /**
063     * Indicator if this ring is a field.
064     */
065    protected int isField = -1; // initially unknown
066
067
068    /**
069     * The constructor creates a WordResidueRing object from an Ideal.
070     * @param i polynomial ideal.
071     */
072    public WordResidueRing(WordIdeal<C> i) {
073        this(i, false);
074    }
075
076
077    /**
078     * The constructor creates a WordResidueRing object from an WordIdeal.
079     * @param i solvable polynomial ideal.
080     * @param isMaximal true, if ideal is maxmal.
081     */
082    public WordResidueRing(WordIdeal<C> i, boolean isMaximal) {
083        //System.out.println("i    = " + i);
084        ideal = i.GB(); // cheap if isGB
085        //System.out.println("i.GB = " + ideal);
086        ring = ideal.getRing();
087        bb = new WordGroebnerBaseSeq<C>();
088        if (isMaximal) {
089            isField = 1;
090            return;
091        }
092        if (ideal.isONE()) {
093            logger.warn("ideal is one, so all residues are 0");
094        }
095        //System.out.println("rr ring   = " + ring.getClass().getName());
096        //System.out.println("rr cofac  = " + ring.coFac.getClass().getName());
097    }
098
099
100    /**
101     * Factory for base elements.
102     */
103    public GenWordPolynomialRing<C> pairFactory() {
104        return ring;
105    }
106
107
108    /**
109     * Factory for base elements.
110     */
111    public GenWordPolynomialRing<C> valueFactory() {
112        return ring;
113    }
114
115
116    /**
117     * Create from numerator.
118     */
119    public WordResidue<C> create(GenWordPolynomial<C> n) {
120        return new WordResidue<C>(this, n);
121    }
122
123
124    /**
125     * Create from numerator, denominator pair.
126     */
127    public WordResidue<C> create(GenWordPolynomial<C> n, GenWordPolynomial<C> d) {
128        if (d != null && !d.isONE()) {
129            throw new UnsupportedOperationException("d must be 1, but d = " + d);
130        }
131        return new WordResidue<C>(this, n);
132    }
133
134
135    /**
136     * Is this structure finite or infinite.
137     * @return true if this structure is finite, else false.
138     * @see edu.jas.structure.ElemFactory#isFinite()
139     */
140    public boolean isFinite() {
141        return ideal.commonZeroTest() <= 0 && ring.coFac.isFinite();
142    }
143
144
145    /**
146     * Copy WordResidue element c.
147     * @param c
148     * @return a copy of c.
149     */
150    public WordResidue<C> copy(WordResidue<C> c) {
151        //System.out.println("rr copy in    = " + c.val);
152        if (c == null) { // where does this happen?
153            return getZERO(); // or null?
154        }
155        WordResidue<C> r = new WordResidue<C>(this, c.val);
156        //System.out.println("rr copy out   = " + r.val);
157        //System.out.println("rr copy ideal = " + ideal.list.list);
158        return r; //new WordResidue<C>( c.ring, c.val );
159    }
160
161
162    /**
163     * Get the zero element.
164     * @return 0 as WordResidue.
165     */
166    public WordResidue<C> getZERO() {
167        return new WordResidue<C>(this, ring.getZERO());
168    }
169
170
171    /**
172     * Get the one element.
173     * @return 1 as WordResidue.
174     */
175    public WordResidue<C> getONE() {
176        WordResidue<C> one = new WordResidue<C>(this, ring.getONE());
177        if (one.isZERO()) {
178            logger.warn("ideal is one, so all residues are 0");
179        }
180        return one;
181    }
182
183
184    /**
185     * Get a list of the generating elements.
186     * @return list of generators for the algebraic structure.
187     * @see edu.jas.structure.ElemFactory#generators()
188     */
189    public List<WordResidue<C>> generators() {
190        List<GenWordPolynomial<C>> pgens = ring.generators();
191        List<WordResidue<C>> gens = new ArrayList<WordResidue<C>>(pgens.size());
192        SortedSet<WordResidue<C>> sgens = new TreeSet<WordResidue<C>>();
193        List<GenWordPolynomial<C>> rgens = new ArrayList<GenWordPolynomial<C>>(pgens.size());
194        WordIdeal<C> gi = new WordIdeal<C>(ring, rgens);
195        WordResidueRing<C> gr = new WordResidueRing<C>(gi);
196        for (GenWordPolynomial<C> s : pgens) {
197            WordResidue<C> r = new WordResidue<C>(this, s);
198            if (r.isZERO()) {
199                continue;
200            }
201            if (!r.isONE() && r.val.isConstant()) {
202                continue;
203            }
204            // avoid duplicate generators with sgens
205            WordResidue<C> x = new WordResidue<C>(gr, r.val);
206            if (x.isZERO()) {
207                continue;
208            }
209            if (!x.isONE() && x.val.isConstant()) {
210                continue;
211            }
212            r = new WordResidue<C>(this, x.val);
213            if (r.isZERO()) {
214                continue;
215            }
216            r = r.monic();
217            if (!r.isONE() && !r.val.isConstant()) {
218                rgens.add(r.val);
219                //System.out.println("rgens = " + rgens);
220                gi = new WordIdeal<C>(ring, rgens);
221                gr = new WordResidueRing<C>(gi);
222            }
223            //gens.add(r);
224            sgens.add(r);
225        }
226        gens.addAll(sgens);
227        return gens;
228    }
229
230
231    /**
232     * Query if this ring is commutative.
233     * @return true if this ring is commutative, else false.
234     */
235    public boolean isCommutative() {
236        return ring.isCommutative(); // check also vector space structure
237    }
238
239
240    /**
241     * Query if this ring is associative.
242     * @return true if this ring is associative, else false.
243     */
244    public boolean isAssociative() {
245        return ring.isAssociative(); // sufficient ??
246    }
247
248
249    /**
250     * Query if this ring is a field.
251     * @return false.
252     */
253    public boolean isField() {
254        if (isField > 0) {
255            return true;
256        }
257        if (isField == 0) {
258            return false;
259        }
260        if (ideal.isMaximal()) {
261            isField = 1;
262            return true;
263        }
264        return false;
265    }
266
267
268    /**
269     * Characteristic of this ring.
270     * @return characteristic of this ring.
271     */
272    public java.math.BigInteger characteristic() {
273        return ring.characteristic();
274    }
275
276
277    /**
278     * Get a WordResidue element from a BigInteger value.
279     * @param a BigInteger.
280     * @return a WordResidue.
281     */
282    public WordResidue<C> fromInteger(java.math.BigInteger a) {
283        return new WordResidue<C>(this, ring.fromInteger(a));
284    }
285
286
287    /**
288     * Get a WordResidue element from a long value.
289     * @param a long.
290     * @return a WordResidue.
291     */
292    public WordResidue<C> fromInteger(long a) {
293        return new WordResidue<C>(this, ring.fromInteger(a));
294    }
295
296
297    /**
298     * Get the String representation as RingFactory.
299     * @see java.lang.Object#toString()
300     */
301    @Override
302    public String toString() {
303        return "WordResidueRing[ " + ideal.toString() + " ]";
304    }
305
306
307    /**
308     * Get a scripting compatible string representation.
309     * @return script compatible representation for this ElemFactory.
310     * @see edu.jas.structure.ElemFactory#toScript()
311     */
312    @Override
313    public String toScript() {
314        // Python case
315        return "WRC(" + ideal.toScript() + ")";
316        //return "WRC(" + ideal.toScript() + "," + ring.toScript()  + ")";
317    }
318
319
320    /**
321     * Comparison with any other object.
322     * @see java.lang.Object#equals(java.lang.Object)
323     */
324    @Override
325    @SuppressWarnings("unchecked")
326    public boolean equals(Object b) {
327        if (!(b instanceof WordResidueRing)) {
328            return false;
329        }
330        WordResidueRing<C> a = null;
331        try {
332            a = (WordResidueRing<C>) b;
333        } catch (ClassCastException e) {
334        }
335        if (a == null) {
336            return false;
337        }
338        if (!ring.equals(a.ring)) {
339            return false;
340        }
341        return ideal.equals(a.ideal);
342    }
343
344
345    /**
346     * Hash code for this residue ring.
347     * @see java.lang.Object#hashCode()
348     */
349    @Override
350    public int hashCode() {
351        int h;
352        h = ideal.hashCode();
353        return h;
354    }
355
356
357    /**
358     * WordResidue random.
359     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
360     * @return a random residue element.
361     */
362    public WordResidue<C> random(int n) {
363        GenWordPolynomial<C> x = ring.random(n).monic();
364        return new WordResidue<C>(this, x);
365    }
366
367
368    /**
369     * Generate a random residum polynomial.
370     * @param k bitsize of random coefficients.
371     * @param l number of terms.
372     * @param d maximal degree in each variable.
373     * @return a random residue polynomial.
374     */
375    public WordResidue<C> random(int k, int l, int d) {
376        GenWordPolynomial<C> x = ring.random(k, l, d).monic();
377        return new WordResidue<C>(this, x);
378    }
379
380
381    /**
382     * WordResidue random.
383     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
384     * @param rnd is a source for random bits.
385     * @return a random residue element.
386     */
387    public WordResidue<C> random(int n, Random rnd) {
388        GenWordPolynomial<C> x = ring.random(n, rnd).monic();
389        return new WordResidue<C>(this, x);
390    }
391
392
393    /**
394     * Parse WordResidue from String.
395     * @param s String.
396     * @return WordResidue from s.
397     */
398    public WordResidue<C> parse(String s) {
399        GenWordPolynomial<C> x = ring.parse(s);
400        return new WordResidue<C>(this, x);
401    }
402
403
404    /**
405     * Parse WordResidue from Reader.
406     * @param r Reader.
407     * @return next WordResidue from r.
408     */
409    public WordResidue<C> parse(Reader r) {
410        GenWordPolynomial<C> x = ring.parse(r);
411        return new WordResidue<C>(this, x);
412    }
413
414}