Source code

001/*
002 * $Id: GenWordPolynomialRing.java 5287 2015-08-01 17:21:40Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.io.Reader;
009import java.io.IOException;
010import java.io.StringReader;
011import java.math.BigInteger;
012import java.util.ArrayList;
013import java.util.List;
014import java.util.Arrays;
015import java.util.Map;
016import java.util.Random;
017
018import org.apache.log4j.Logger;
019
020import edu.jas.kern.PreemptStatus;
021import edu.jas.kern.Scripting;
022import edu.jas.structure.RingElem;
023import edu.jas.structure.RingFactory;
024
025
026/**
027 * GenWordPolynomialRing generic polynomial factory implementing RingFactory;
028 * Factory for non-commutative string polynomials over C.
029 * @param <C> coefficient type
030 * @author Heinz Kredel
031 */
032
033public final class GenWordPolynomialRing<C extends RingElem<C>> implements RingFactory<GenWordPolynomial<C>>
034/*, Iterable<GenWordPolynomial<C>>*/{
035
036
037    /**
038     * The factory for the coefficients.
039     */
040    public final RingFactory<C> coFac;
041
042
043    /**
044     * The factory for the alphabet.
045     */
046    public final WordFactory alphabet;
047
048
049    /**
050     * The constant polynomial 0 for this ring.
051     */
052    public final GenWordPolynomial<C> ZERO;
053
054
055    /**
056     * The constant polynomial 1 for this ring.
057     */
058    public final GenWordPolynomial<C> ONE;
059
060
061    /**
062     * The constant empty word exponent for this ring.
063     */
064    public final Word wone;
065
066
067    /**
068     * A default random sequence generator.
069     */
070    final static Random random = new Random();
071
072
073    /**
074     * Indicator if this ring is a field.
075     */
076    private int isField = -1; // initially unknown
077
078
079    /**
080     * Log4j logger object.
081     */
082    private static final Logger logger = Logger.getLogger(GenWordPolynomialRing.class);
083
084
085    /**
086     * Flag to enable if preemptive interrrupt is checked.
087     */
088    final boolean checkPreempt = PreemptStatus.isAllowed();
089
090
091    /**
092     * The constructor creates a polynomial factory object with the default term
093     * order.
094     * @param cf factory for coefficients of type C.
095     * @param wf factory for strings.
096     */
097    public GenWordPolynomialRing(RingFactory<C> cf, WordFactory wf) {
098        coFac = cf;
099        alphabet = wf;
100        ZERO = new GenWordPolynomial<C>(this);
101        C coeff = coFac.getONE();
102        wone = wf.getONE();
103        ONE = new GenWordPolynomial<C>(this, coeff, wone);
104    }
105
106
107    /**
108     * The constructor creates a polynomial factory object.
109     * @param cf factory for coefficients of type C.
110     * @param s array of variable names.
111     */
112    public GenWordPolynomialRing(RingFactory<C> cf, String[] s) {
113        this(cf, new WordFactory(s));
114    }
115
116
117    /**
118     * The constructor creates a polynomial factory object.
119     * @param cf factory for coefficients of type C.
120     * @param s string of single letter variable names.
121     */
122    public GenWordPolynomialRing(RingFactory<C> cf, String s) {
123        this(cf, new WordFactory(s));
124    }
125
126
127    /**
128     * The constructor creates a polynomial factory object.
129     * @param cf factory for coefficients of type C.
130     * @param o other polynomial ring.
131     */
132    public GenWordPolynomialRing(RingFactory<C> cf, GenWordPolynomialRing o) {
133        this(cf, o.alphabet);
134    }
135
136
137    /**
138     * The constructor creates a polynomial factory object.
139     * @param fac polynomial ring.
140     */
141    public GenWordPolynomialRing(GenPolynomialRing<C> fac) {
142        this(fac.coFac, new WordFactory(fac.vars));
143    }
144
145
146    /**
147     * Copy this factory.
148     * @return a clone of this.
149     */
150    public GenWordPolynomialRing<C> copy() {
151        return new GenWordPolynomialRing<C>(coFac, this);
152    }
153
154
155    /**
156     * Get the String representation.
157     * @see java.lang.Object#toString()
158     */
159    @Override
160    public String toString() {
161        StringBuffer s = new StringBuffer();
162        s.append("WordPolyRing(");
163        if (coFac instanceof RingElem) {
164            s.append(((RingElem<C>) coFac).toScriptFactory());
165        } else {
166            s.append(coFac.toString().trim());
167        }
168        s.append(",");
169        s.append(alphabet.toString());
170        s.append(")");
171        return s.toString();
172    }
173
174
175    /**
176     * Get a scripting compatible string representation.
177     * @return script compatible representation for this Element.
178     * @see edu.jas.structure.Element#toScript()
179     */
180    @Override
181    public String toScript() {
182        StringBuffer s = new StringBuffer();
183        switch (Scripting.getLang()) {
184        case Ruby:
185            s.append("WordPolyRing.new(");
186            break;
187        case Python:
188        default:
189            s.append("WordPolyRing(");
190        }
191        if (coFac instanceof RingElem) {
192            s.append(((RingElem<C>) coFac).toScriptFactory());
193        } else {
194            s.append(coFac.toScript().trim());
195        }
196        s.append(",");
197        s.append(alphabet.toScript());
198        s.append(")");
199        return s.toString();
200    }
201
202
203    /**
204     * Comparison with any other object.
205     * @see java.lang.Object#equals(java.lang.Object)
206     */
207    @Override
208    @SuppressWarnings("unchecked")
209    public boolean equals(Object other) {
210        if (other == null) {
211            return false;
212        }
213        if (!(other instanceof GenWordPolynomialRing)) {
214            return false;
215        }
216        GenWordPolynomialRing<C> oring = (GenWordPolynomialRing<C>) other;
217        if (!coFac.equals(oring.coFac)) {
218            return false;
219        }
220        if (!alphabet.equals(oring.alphabet)) {
221            return false;
222        }
223        return true;
224    }
225
226
227    /**
228     * Hash code for this polynomial ring.
229     * @see java.lang.Object#hashCode()
230     */
231    @Override
232    public int hashCode() {
233        int h;
234        h = (coFac.hashCode() << 11);
235        h += alphabet.hashCode();
236        return h;
237    }
238
239
240    /**
241     * Get the variable names.
242     * @return vars.
243     */
244    public String[] getVars() {
245        return alphabet.getVars(); // Java-5: Arrays.copyOf(vars,vars.length);
246    }
247
248
249    /**
250     * Get the zero element from the coefficients.
251     * @return 0 as C.
252     */
253    public C getZEROCoefficient() {
254        return coFac.getZERO();
255    }
256
257
258    /**
259     * Get the one element from the coefficients.
260     * @return 1 as C.
261     */
262    public C getONECoefficient() {
263        return coFac.getONE();
264    }
265
266
267    /**
268     * Get the zero element.
269     * @return 0 as GenWordPolynomial<C>.
270     */
271    public GenWordPolynomial<C> getZERO() {
272        return ZERO;
273    }
274
275
276    /**
277     * Get the one element.
278     * @return 1 as GenWordPolynomial<C>.
279     */
280    public GenWordPolynomial<C> getONE() {
281        return ONE;
282    }
283
284
285    /**
286     * Query if this ring is commutative.
287     * @return true if this ring is commutative, else false.
288     */
289    public boolean isCommutative() {
290        return coFac.isCommutative() && alphabet.isFinite();
291    }
292
293
294    /**
295     * Query if this ring is associative.
296     * @return true if this ring is associative, else false.
297     */
298    public boolean isAssociative() {
299        return coFac.isAssociative();
300    }
301
302
303    /**
304     * Is this structure finite or infinite.
305     * @return true if this structure is finite, else false.
306     * @see edu.jas.structure.ElemFactory#isFinite()
307     */
308    public boolean isFinite() {
309        return alphabet.isFinite() && coFac.isFinite();
310    }
311
312
313    /**
314     * Query if this ring is a field.
315     * @return false.
316     */
317    public boolean isField() {
318        if (isField > 0) {
319            return true;
320        }
321        if (isField == 0) {
322            return false;
323        }
324        if (coFac.isField() && alphabet.isFinite()) {
325            isField = 1;
326            return true;
327        }
328        isField = 0;
329        return false;
330    }
331
332
333    /**
334     * Characteristic of this ring.
335     * @return characteristic of this ring.
336     */
337    public java.math.BigInteger characteristic() {
338        return coFac.characteristic();
339    }
340
341
342    /**
343     * Get a (constant) GenWordPolynomial&lt;C&gt; element from a coefficient
344     * value.
345     * @param a coefficient.
346     * @return a GenWordPolynomial&lt;C&gt;.
347     */
348    public GenWordPolynomial<C> valueOf(C a) {
349        return new GenWordPolynomial<C>(this, a);
350    }
351
352
353    /**
354     * Get a GenWordPolynomial&lt;C&gt; element from a word.
355     * @param e word.
356     * @return a GenWordPolynomial&lt;C&gt;.
357     */
358    public GenWordPolynomial<C> valueOf(Word e) {
359        return valueOf(coFac.getONE(), e);
360    }
361
362
363    /**
364     * Get a GenWordPolynomial&lt;C&gt; element from an ExpVector.
365     * @param e exponent vector.
366     * @return a GenWordPolynomial&lt;C&gt;.
367     */
368    public GenWordPolynomial<C> valueOf(ExpVector e) {
369        return valueOf(coFac.getONE(), e);
370    }
371
372
373    /**
374     * Get a GenWordPolynomial&lt;C&gt; element from a coeffcient and a word.
375     * @param a coefficient.
376     * @param e word.
377     * @return a GenWordPolynomial&lt;C&gt;.
378     */
379    public GenWordPolynomial<C> valueOf(C a, Word e) {
380        return new GenWordPolynomial<C>(this, a, e);
381    }
382
383
384    /**
385     * Get a GenWordPolynomial&lt;C&gt; element from a coeffcient and an ExpVector.
386     * @param a coefficient.
387     * @param e exponent vector.
388     * @return a GenWordPolynomial&lt;C&gt;.
389     */
390    public GenWordPolynomial<C> valueOf(C a, ExpVector e) {
391        return new GenWordPolynomial<C>(this, a, alphabet.valueOf(e));
392    }
393
394
395    /**
396     * Get a GenWordPolynomial&lt;C&gt; element from a GenPolynomial&lt;C&gt;.
397     * @param a GenPolynomial.
398     * @return a GenWordPolynomial&lt;C&gt;.
399     */
400    public GenWordPolynomial<C> valueOf(GenPolynomial<C> a) {
401        if (a.isZERO()) {
402            return getZERO();
403        }
404        if (a.isONE()) {
405            return getONE();
406        }
407        GenWordPolynomial<C> p = this.getZERO().copy();
408        for (Map.Entry<ExpVector, C> m : a.val.entrySet()) {
409            C c = m.getValue();
410            ExpVector e = m.getKey();
411            Word w = alphabet.valueOf(e);
412            p.doPutToMap(w, c);
413        }
414        return p;
415    }
416
417
418    /**
419     * Get a list of GenWordPolynomial&lt;C&gt; element from a list of
420     * GenPolynomial&lt;C&gt;.
421     * @param A GenPolynomial list.
422     * @return a GenWordPolynomial&lt;C&gt; list.
423     */
424    public List<GenWordPolynomial<C>> valueOf(List<GenPolynomial<C>> A) {
425        List<GenWordPolynomial<C>> B = new ArrayList<GenWordPolynomial<C>>(A.size());
426        if (A.isEmpty()) {
427            return B;
428        }
429        for (GenPolynomial<C> a : A) {
430            GenWordPolynomial<C> b = valueOf(a);
431            B.add(b);
432        }
433        return B;
434    }
435
436
437    /**
438     * Get a (constant) GenWordPolynomial&lt;C&gt; element from a long value.
439     * @param a long.
440     * @return a GenWordPolynomial&lt;C&gt;.
441     */
442    public GenWordPolynomial<C> fromInteger(long a) {
443        return new GenWordPolynomial<C>(this, coFac.fromInteger(a), wone);
444    }
445
446
447    /**
448     * Get a (constant) GenWordPolynomial&lt;C&gt; element from a BigInteger
449     * value.
450     * @param a BigInteger.
451     * @return a GenWordPolynomial&lt;C&gt;.
452     */
453    public GenWordPolynomial<C> fromInteger(BigInteger a) {
454        return new GenWordPolynomial<C>(this, coFac.fromInteger(a), wone);
455    }
456
457
458    /**
459     * Random polynomial. Generates a random polynomial.
460     * @param n number of terms.
461     * @return a random polynomial.
462     */
463    public GenWordPolynomial<C> random(int n) {
464        return random(n, random);
465    }
466
467
468    /**
469     * Random polynomial. Generates a random polynomial with k = 5, l = n, d =
470     * 3.
471     * @param n number of terms.
472     * @param rnd is a source for random bits.
473     * @return a random polynomial.
474     */
475    public GenWordPolynomial<C> random(int n, Random rnd) {
476        return random(5, n, 3, rnd);
477    }
478
479
480    /**
481     * Generate a random polynomial.
482     * @param k bitsize of random coefficients.
483     * @param l number of terms.
484     * @param d maximal length of a random word.
485     * @return a random polynomial.
486     */
487    public GenWordPolynomial<C> random(int k, int l, int d) {
488        return random(k, l, d, random);
489    }
490
491
492    /**
493     * Generate a random polynomial.
494     * @param k bitsize of random coefficients.
495     * @param l number of terms.
496     * @param d maximal length of a random word.
497     * @param rnd is a source for random bits.
498     * @return a random polynomial.
499     */
500    public GenWordPolynomial<C> random(int k, int l, int d, Random rnd) {
501        GenWordPolynomial<C> r = getZERO(); //.clone() or copy( ZERO ); 
502        // add l random coeffs and words of maximal length d
503        for (int i = 0; i < l; i++) {
504            int di = Math.abs(rnd.nextInt() % d);
505            Word e = alphabet.random(di, rnd);
506            C a = coFac.random(k, rnd);
507            r = r.sum(a, e); // somewhat inefficient but clean
508            //System.out.println("e = " + e + " a = " + a);
509        }
510        return r;
511    }
512
513
514    /**
515     * Copy polynomial c.
516     * @param c polynomial to copy.
517     * @return a copy of c.
518     */
519    public GenWordPolynomial<C> copy(GenWordPolynomial<C> c) {
520        return new GenWordPolynomial<C>(this, c.val);
521    }
522
523
524    /**
525     * Parse a polynomial with the use of GenWordPolynomialTokenizer.
526     * @param s String.
527     * @return GenWordPolynomial from s.
528     */
529    public GenWordPolynomial<C> parse(String s) {
530        String val = s;
531        if (!s.contains("|")) {
532            val = val.replace("{", "").replace("}", "");
533        }
534        return parse(new StringReader(val));
535    }
536
537
538    /**
539     * Parse a polynomial with the use of GenWordPolynomialTokenizer.
540     * @param r Reader.
541     * @return next GenWordPolynomial from r.
542     */
543    @SuppressWarnings("unchecked")
544    public GenWordPolynomial<C> parse(Reader r) {
545        if (alphabet.length() <= 4) { // todo, hack for commuative like cases
546            GenPolynomialRing<C> cr = new GenPolynomialRing<C>(coFac, alphabet.getVars() );
547            GenPolynomialTokenizer pt = new GenPolynomialTokenizer(cr, r);
548            GenPolynomial<C> p = null;
549            try {
550                  p = pt.nextPolynomial();
551            } catch (IOException e) {
552                  logger.error(e.toString() + " parse " + this);
553            }
554            GenWordPolynomial<C> wp = this.valueOf(p);
555            return wp;
556        }
557        logger.error("parse not implemented");
558        throw new UnsupportedOperationException("not implemented");
559    }
560
561
562    /**
563     * Generate univariate polynomial in a given variable.
564     * @param i the index of the variable.
565     * @return X_i as univariate polynomial.
566     */
567    public GenWordPolynomial<C> univariate(int i) {
568        GenWordPolynomial<C> p = getZERO();
569        List<Word> wgen = alphabet.generators();
570        if (0 <= i && i < wgen.size()) {
571            C one = coFac.getONE();
572            Word f = wgen.get(i);
573            p = p.sum(one, f);
574        }
575        return p;
576    }
577
578
579    /**
580     * Generate commute polynomial in two variables.
581     * @param i the index of the first variable.
582     * @param j the index of the second variable.
583     * @return X_i * x_j - X_j * X_i as polynomial.
584     */
585    public GenWordPolynomial<C> commute(int i, int j) {
586        GenWordPolynomial<C> p = getZERO();
587        List<Word> wgen = alphabet.generators();
588        if (0 <= i && i < wgen.size() && 0 <= j && j < wgen.size()) {
589            C one = coFac.getONE();
590            Word f = wgen.get(i);
591            Word e = wgen.get(j);
592            p = p.sum(one, e.multiply(f));
593            p = p.subtract(one, f.multiply(e));
594            if (i > j) {
595                p = p.negate();
596            }
597        }
598        return p;
599    }
600
601
602    /**
603     * Generate commute polynomials for given variable.
604     * @param i the index of the variable.
605     * @return [X_i * x_j - X_j * X_i, i != j] as list of polynomials.
606     */
607    public List<GenWordPolynomial<C>> commute(int i) {
608        int n = alphabet.length();
609        List<GenWordPolynomial<C>> pols = new ArrayList<GenWordPolynomial<C>>(n-1);
610        for ( int j = 0; j < n; j++ ) {
611            if (i != j) {
612                pols.add(commute(i,j));
613            }
614        }
615        return pols;
616    }
617
618
619    /**
620     * Generate commute polynomials for all variables.
621     * @return [X_i * x_j - X_j * X_i, i != j] as list of polynomials.
622     */
623    public List<GenWordPolynomial<C>> commute() {
624        int n = alphabet.length();
625        List<GenWordPolynomial<C>> pols = new ArrayList<GenWordPolynomial<C>>(n*(n-1));
626        for ( int i = 0; i < n; i++ ) {
627             pols.addAll( commute(i) );
628        }
629        return pols;
630    }
631
632
633    /**
634     * Generate list of univariate polynomials in all variables.
635     * @return List(X_1,...,X_n) a list of univariate polynomials.
636     */
637    public List<GenWordPolynomial<C>> univariateList() {
638        int n = alphabet.length();
639        List<GenWordPolynomial<C>> pols = new ArrayList<GenWordPolynomial<C>>(n);
640        for (int i = 0; i < n; i++) {
641            GenWordPolynomial<C> p = univariate(i);
642            pols.add(p);
643        }
644        return pols;
645    }
646
647
648    /**
649     * Get the generating elements <b>excluding</b> the generators for the
650     * coefficient ring.
651     * @return a list of generating elements for this ring.
652     */
653    public List<GenWordPolynomial<C>> getGenerators() {
654        List<GenWordPolynomial<C>> univs = univariateList();
655        List<GenWordPolynomial<C>> gens = new ArrayList<GenWordPolynomial<C>>(univs.size() + 1);
656        gens.add(getONE());
657        gens.addAll(univs);
658        return gens;
659    }
660
661
662    /**
663     * Get a list of all generating elements.
664     * @return list of generators for the algebraic structure.
665     * @see edu.jas.structure.ElemFactory#generators()
666     */
667    public List<GenWordPolynomial<C>> generators() {
668        List<C> cogens = coFac.generators();
669        List<GenWordPolynomial<C>> univs = univariateList();
670        List<GenWordPolynomial<C>> gens = new ArrayList<GenWordPolynomial<C>>(univs.size() + cogens.size());
671        for (C c : cogens) {
672            gens.add(getONE().multiply(c));
673        }
674        gens.addAll(univs);
675        return gens;
676    }
677
678}