Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.io.IOException;
009import java.io.Reader;
010import java.io.StringReader;
011import java.math.BigInteger;
012import java.util.ArrayList;
013import java.util.List;
014import java.util.Map;
015import java.util.Random;
016
017import org.apache.logging.log4j.LogManager;
018import org.apache.logging.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 = LogManager.getLogger(GenWordPolynomialRing.class);
083
084
085    /**
086     * Flag to enable if preemptive interrupt 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     * Extend variables. Used e.g. in module embedding. Extend number of
205     * variables by i.
206     * @param i number of variables to extend.
207     * @return extended word polynomial ring factory.
208     */
209    public GenWordPolynomialRing<C> extend(int i) {
210        // add module variable names
211        String[] v = GenPolynomialRing.newVars("t", i);
212        return extend(v);
213    }
214
215
216    /**
217     * Extend variables. Extend number of variables by length(vn).
218     * @param vn names for extended variables.
219     * @return extended polynomial ring factory.
220     */
221    public GenWordPolynomialRing<C> extend(String[] vn) {
222        WordFactory wfe = alphabet.extend(vn);
223        return new GenWordPolynomialRing<C>(coFac, wfe);
224    }
225
226
227    /**
228     * Comparison with any other object.
229     * @see java.lang.Object#equals(java.lang.Object)
230     */
231    @Override
232    @SuppressWarnings("unchecked")
233    public boolean equals(Object other) {
234        if (other == null) {
235            return false;
236        }
237        if (!(other instanceof GenWordPolynomialRing)) {
238            return false;
239        }
240        GenWordPolynomialRing<C> oring = (GenWordPolynomialRing<C>) other;
241        if (!coFac.equals(oring.coFac)) {
242            return false;
243        }
244        if (!alphabet.equals(oring.alphabet)) {
245            return false;
246        }
247        return true;
248    }
249
250
251    /**
252     * Hash code for this polynomial ring.
253     * @see java.lang.Object#hashCode()
254     */
255    @Override
256    public int hashCode() {
257        int h;
258        h = (coFac.hashCode() << 11);
259        h += alphabet.hashCode();
260        return h;
261    }
262
263
264    /**
265     * Get the variable names.
266     * @return vars.
267     */
268    public String[] getVars() {
269        return alphabet.getVars(); // Java-5: Arrays.copyOf(vars,vars.length);
270    }
271
272
273    /**
274     * Get the zero element from the coefficients.
275     * @return 0 as C.
276     */
277    public C getZEROCoefficient() {
278        return coFac.getZERO();
279    }
280
281
282    /**
283     * Get the one element from the coefficients.
284     * @return 1 as C.
285     */
286    public C getONECoefficient() {
287        return coFac.getONE();
288    }
289
290
291    /**
292     * Get the zero element.
293     * @return 0 as GenWordPolynomial<C>.
294     */
295    public GenWordPolynomial<C> getZERO() {
296        return ZERO;
297    }
298
299
300    /**
301     * Get the one element.
302     * @return 1 as GenWordPolynomial<C>.
303     */
304    public GenWordPolynomial<C> getONE() {
305        return ONE;
306    }
307
308
309    /**
310     * Query if this ring is commutative.
311     * @return true if this ring is commutative, else false.
312     */
313    public boolean isCommutative() {
314        return coFac.isCommutative() && alphabet.isFinite();
315    }
316
317
318    /**
319     * Query if this ring is associative.
320     * @return true if this ring is associative, else false.
321     */
322    public boolean isAssociative() {
323        return coFac.isAssociative();
324    }
325
326
327    /**
328     * Is this structure finite or infinite.
329     * @return true if this structure is finite, else false.
330     * @see edu.jas.structure.ElemFactory#isFinite()
331     */
332    public boolean isFinite() {
333        return alphabet.isFinite() && coFac.isFinite();
334    }
335
336
337    /**
338     * Query if this ring is a field.
339     * @return false.
340     */
341    public boolean isField() {
342        if (isField > 0) {
343            return true;
344        }
345        if (isField == 0) {
346            return false;
347        }
348        if (coFac.isField() && alphabet.isFinite()) {
349            isField = 1;
350            return true;
351        }
352        isField = 0;
353        return false;
354    }
355
356
357    /**
358     * Characteristic of this ring.
359     * @return characteristic of this ring.
360     */
361    public java.math.BigInteger characteristic() {
362        return coFac.characteristic();
363    }
364
365
366    /**
367     * Get a (constant) GenWordPolynomial&lt;C&gt; element from a coefficient
368     * value.
369     * @param a coefficient.
370     * @return a GenWordPolynomial&lt;C&gt;.
371     */
372    public GenWordPolynomial<C> valueOf(C a) {
373        return new GenWordPolynomial<C>(this, a);
374    }
375
376
377    /**
378     * Get a GenWordPolynomial&lt;C&gt; element from a word.
379     * @param e word.
380     * @return a GenWordPolynomial&lt;C&gt;.
381     */
382    public GenWordPolynomial<C> valueOf(Word e) {
383        return valueOf(coFac.getONE(), e);
384    }
385
386
387    /**
388     * Get a GenWordPolynomial&lt;C&gt; element from an ExpVector.
389     * @param e exponent vector.
390     * @return a GenWordPolynomial&lt;C&gt;.
391     */
392    public GenWordPolynomial<C> valueOf(ExpVector e) {
393        return valueOf(coFac.getONE(), e);
394    }
395
396
397    /**
398     * Get a GenWordPolynomial&lt;C&gt; element from a coefficient and a word.
399     * @param a coefficient.
400     * @param e word.
401     * @return a GenWordPolynomial&lt;C&gt;.
402     */
403    public GenWordPolynomial<C> valueOf(C a, Word e) {
404        return new GenWordPolynomial<C>(this, a, e);
405    }
406
407
408    /**
409     * Get a GenWordPolynomial&lt;C&gt; element from a coefficient and an
410     * ExpVector.
411     * @param a coefficient.
412     * @param e exponent vector.
413     * @return a GenWordPolynomial&lt;C&gt;.
414     */
415    public GenWordPolynomial<C> valueOf(C a, ExpVector e) {
416        return new GenWordPolynomial<C>(this, a, alphabet.valueOf(e));
417    }
418
419
420    /**
421     * Get a GenWordPolynomial&lt;C&gt; element from a GenPolynomial&lt;C&gt;.
422     * @param a GenPolynomial.
423     * @return a GenWordPolynomial&lt;C&gt;.
424     */
425    public GenWordPolynomial<C> valueOf(GenPolynomial<C> a) {
426        if (a.isZERO()) {
427            return getZERO();
428        }
429        if (a.isONE()) {
430            return getONE();
431        }
432        GenWordPolynomial<C> p = this.getZERO().copy();
433        for (Map.Entry<ExpVector, C> m : a.val.entrySet()) {
434            C c = m.getValue();
435            ExpVector e = m.getKey();
436            Word w = alphabet.valueOf(e);
437            p.doPutToMap(w, c);
438        }
439        return p;
440    }
441
442
443    /**
444     * Get a GenWordPolynomial&lt;C&gt; element from a
445     * GenWordPolynomial&lt;C&gt;.
446     * @param a GenWordPolynomial.
447     * @return a GenWordPolynomial&lt;C&gt;.
448     */
449    public GenWordPolynomial<C> valueOf(GenWordPolynomial<C> a) {
450        if (a.isZERO()) {
451            return getZERO();
452        }
453        if (a.isONE()) {
454            return getONE();
455        }
456        GenWordPolynomial<C> p = this.getZERO().copy();
457        for (Map.Entry<Word, C> m : a.val.entrySet()) {
458            C c = m.getValue();
459            Word e = m.getKey();
460            Word w = alphabet.valueOf(e);
461            p.doPutToMap(w, c);
462        }
463        return p;
464    }
465
466
467    /**
468     * Get a list of GenWordPolynomial&lt;C&gt; element from a list of
469     * GenPolynomial&lt;C&gt;.
470     * @param A GenPolynomial list.
471     * @return a GenWordPolynomial&lt;C&gt; list.
472     */
473    public List<GenWordPolynomial<C>> valueOf(List<GenPolynomial<C>> A) {
474        List<GenWordPolynomial<C>> B = new ArrayList<GenWordPolynomial<C>>(A.size());
475        if (A.isEmpty()) {
476            return B;
477        }
478        for (GenPolynomial<C> a : A) {
479            GenWordPolynomial<C> b = valueOf(a);
480            B.add(b);
481        }
482        return B;
483    }
484
485
486    /**
487     * Get a (constant) GenWordPolynomial&lt;C&gt; element from a long value.
488     * @param a long.
489     * @return a GenWordPolynomial&lt;C&gt;.
490     */
491    public GenWordPolynomial<C> fromInteger(long a) {
492        return new GenWordPolynomial<C>(this, coFac.fromInteger(a), wone);
493    }
494
495
496    /**
497     * Get a (constant) GenWordPolynomial&lt;C&gt; element from a BigInteger
498     * value.
499     * @param a BigInteger.
500     * @return a GenWordPolynomial&lt;C&gt;.
501     */
502    public GenWordPolynomial<C> fromInteger(BigInteger a) {
503        return new GenWordPolynomial<C>(this, coFac.fromInteger(a), wone);
504    }
505
506
507    /**
508     * Random polynomial. Generates a random polynomial.
509     * @param n number of terms.
510     * @return a random polynomial.
511     */
512    public GenWordPolynomial<C> random(int n) {
513        return random(n, random);
514    }
515
516
517    /**
518     * Random polynomial. Generates a random polynomial with k = 5, l = n, d =
519     * 3.
520     * @param n number of terms.
521     * @param rnd is a source for random bits.
522     * @return a random polynomial.
523     */
524    public GenWordPolynomial<C> random(int n, Random rnd) {
525        return random(5, n, 3, rnd);
526    }
527
528
529    /**
530     * Generate a random polynomial.
531     * @param k bitsize of random coefficients.
532     * @param l number of terms.
533     * @param d maximal length of a random word.
534     * @return a random polynomial.
535     */
536    public GenWordPolynomial<C> random(int k, int l, int d) {
537        return random(k, l, d, random);
538    }
539
540
541    /**
542     * Generate a random polynomial.
543     * @param k bitsize of random coefficients.
544     * @param l number of terms.
545     * @param d maximal length of a random word.
546     * @param rnd is a source for random bits.
547     * @return a random polynomial.
548     */
549    public GenWordPolynomial<C> random(int k, int l, int d, Random rnd) {
550        GenWordPolynomial<C> r = getZERO(); //.clone() or copy( ZERO ); 
551        // add l random coeffs and words of maximal length d
552        for (int i = 0; i < l; i++) {
553            int di = Math.abs(rnd.nextInt() % d);
554            Word e = alphabet.random(di, rnd);
555            C a = coFac.random(k, rnd);
556            r = r.sum(a, e); // somewhat inefficient but clean
557            //System.out.println("e = " + e + " a = " + a);
558        }
559        return r;
560    }
561
562
563    /**
564     * Copy polynomial c.
565     * @param c polynomial to copy.
566     * @return a copy of c.
567     */
568    public GenWordPolynomial<C> copy(GenWordPolynomial<C> c) {
569        return new GenWordPolynomial<C>(this, c.val);
570    }
571
572
573    /**
574     * Parse a polynomial with the use of GenWordPolynomialTokenizer.
575     * @param s String.
576     * @return GenWordPolynomial from s.
577     */
578    public GenWordPolynomial<C> parse(String s) {
579        String val = s;
580        if (!s.contains("|")) {
581            val = val.replace("{", "").replace("}", "");
582        }
583        return parse(new StringReader(val));
584    }
585
586
587    /**
588     * Parse a polynomial with the use of GenWordPolynomialTokenizer.
589     * @param r Reader.
590     * @return next GenWordPolynomial from r.
591     */
592    @SuppressWarnings("unchecked")
593    public GenWordPolynomial<C> parse(Reader r) {
594        if (alphabet.length() <= 1) { // hack for univariate = commuative like cases
595            // obsolete case
596            GenPolynomialRing<C> cr = new GenPolynomialRing<C>(coFac, alphabet.getVars());
597            GenPolynomialTokenizer pt = new GenPolynomialTokenizer(cr, r);
598            GenPolynomial<C> p = cr.getZERO();
599            try {
600                p = pt.nextPolynomial();
601            } catch (IOException e) {
602                logger.error("{} parse {}", e, this);
603            }
604            GenWordPolynomial<C> wp = this.valueOf(p);
605            return wp;
606        }
607        GenPolynomialTokenizer tok = new GenPolynomialTokenizer(r);
608        GenWordPolynomial<C> a;
609        try {
610            a = tok.nextWordPolynomial(this);
611        } catch (IOException e) {
612            a = null;
613            e.printStackTrace();
614            logger.error("{} parse {}", e, this);
615        }
616        return a;
617        //throw new UnsupportedOperationException("not implemented");
618    }
619
620
621    /**
622     * Generate univariate polynomial in a given variable.
623     * @param i the index of the variable.
624     * @return X_i as univariate polynomial.
625     */
626    public GenWordPolynomial<C> univariate(int i) {
627        GenWordPolynomial<C> p = getZERO();
628        List<Word> wgen = alphabet.generators();
629        if (0 <= i && i < wgen.size()) {
630            C one = coFac.getONE();
631            Word f = wgen.get(i);
632            p = p.sum(one, f);
633        }
634        return p;
635    }
636
637
638    /**
639     * Generate commute polynomial in two variables.
640     * @param i the index of the first variable.
641     * @param j the index of the second variable.
642     * @return X_i * x_j - X_j * X_i as polynomial.
643     */
644    public GenWordPolynomial<C> commute(int i, int j) {
645        GenWordPolynomial<C> p = getZERO();
646        List<Word> wgen = alphabet.generators();
647        if (0 <= i && i < wgen.size() && 0 <= j && j < wgen.size()) {
648            C one = coFac.getONE();
649            Word f = wgen.get(i);
650            Word e = wgen.get(j);
651            p = p.sum(one, e.multiply(f));
652            p = p.subtract(one, f.multiply(e));
653            if (i > j) {
654                p = p.negate();
655            }
656        }
657        return p;
658    }
659
660
661    /**
662     * Generate commute polynomials for given variable.
663     * @param i the index of the variable.
664     * @return [X_i * x_j - X_j * X_i, i != j] as list of polynomials.
665     */
666    public List<GenWordPolynomial<C>> commute(int i) {
667        int n = alphabet.length();
668        List<GenWordPolynomial<C>> pols = new ArrayList<GenWordPolynomial<C>>(n - 1);
669        for (int j = 0; j < n; j++) {
670            if (i != j) {
671                pols.add(commute(i, j));
672            }
673        }
674        return pols;
675    }
676
677
678    /**
679     * Generate commute polynomials for all variables.
680     * @return [X_i * x_j - X_j * X_i, i != j] as list of polynomials.
681     */
682    public List<GenWordPolynomial<C>> commute() {
683        int n = alphabet.length();
684        List<GenWordPolynomial<C>> pols = new ArrayList<GenWordPolynomial<C>>(n * (n - 1));
685        for (int i = 0; i < n; i++) {
686            pols.addAll(commute(i));
687        }
688        return pols;
689    }
690
691
692    /**
693     * Generate list of univariate polynomials in all variables.
694     * @return List(X_1,...,X_n) a list of univariate polynomials.
695     */
696    public List<GenWordPolynomial<C>> univariateList() {
697        int n = alphabet.length();
698        List<GenWordPolynomial<C>> pols = new ArrayList<GenWordPolynomial<C>>(n);
699        for (int i = 0; i < n; i++) {
700            GenWordPolynomial<C> p = univariate(i);
701            pols.add(p);
702        }
703        return pols;
704    }
705
706
707    /**
708     * Get the generating elements <b>excluding</b> the generators for the
709     * coefficient ring.
710     * @return a list of generating elements for this ring.
711     */
712    public List<GenWordPolynomial<C>> getGenerators() {
713        List<GenWordPolynomial<C>> univs = univariateList();
714        List<GenWordPolynomial<C>> gens = new ArrayList<GenWordPolynomial<C>>(univs.size() + 1);
715        gens.add(getONE());
716        gens.addAll(univs);
717        return gens;
718    }
719
720
721    /**
722     * Get a list of all generating elements.
723     * @return list of generators for the algebraic structure.
724     * @see edu.jas.structure.ElemFactory#generators()
725     */
726    public List<GenWordPolynomial<C>> generators() {
727        List<C> cogens = coFac.generators();
728        List<GenWordPolynomial<C>> univs = univariateList();
729        List<GenWordPolynomial<C>> gens = new ArrayList<GenWordPolynomial<C>>(univs.size() + cogens.size());
730        for (C c : cogens) {
731            gens.add(getONE().multiply(c));
732        }
733        gens.addAll(univs);
734        return gens;
735    }
736
737}