001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.io.Reader;
009import java.io.Serializable;
010import java.math.BigInteger;
011import java.util.ArrayList;
012import java.util.Arrays;
013import java.util.Comparator;
014import java.util.List;
015import java.util.Map;
016//import java.util.Set;
017import java.util.Random;
018
019import org.apache.logging.log4j.Logger;
020import org.apache.logging.log4j.LogManager; 
021
022import edu.jas.kern.StringUtil;
023import edu.jas.structure.MonoidFactory;
024
025
026/**
027 * WordFactory implements alphabet related methods.
028 * @author Heinz Kredel
029 */
030
031public final class WordFactory implements MonoidFactory<Word> {
032
033
034    /**
035     * The data structure is a String of characters which defines the alphabet.
036     */
037    /*package*/final String alphabet;
038
039
040    /**
041     * The empty word for this monoid.
042     */
043    public final Word ONE;
044
045
046    /**
047     * The translation reference string.
048     */
049    public static final String transRef = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
050
051
052    /**
053     * The translation array of Strings.
054     */
055    public final String[] translation;
056
057
058    /**
059     * Random number generator.
060     */
061    private final static Random random = new Random();
062
063
064    /**
065     * Log4j logger object.
066     */
067    private static final Logger logger = LogManager.getLogger(WordFactory.class);
068
069
070    /**
071     * Comparator for Words.
072     */
073    public static abstract class WordComparator implements Comparator<Word>, Serializable {
074
075
076        public abstract int compare(Word e1, Word e2);
077    }
078
079
080    /**
081     * Defined descending order comparator. Sorts the highest terms first.
082     */
083    private static final WordComparator horder = new WordComparator() {
084
085
086        @Override
087        public int compare(Word e1, Word e2) {
088            //return e1.gradCompareTo(e2);
089            return e1.gradInvlexCompareTo(e2);
090        }
091    };
092
093
094    /**
095     * Defined ascending order comparator. Sorts the lowest terms first.
096     */
097    private static final WordComparator lorder = new WordComparator() {
098
099
100        @Override
101        public int compare(Word e1, Word e2) {
102            //return -e1.gradCompareTo(e2);
103            return -e1.gradInvlexCompareTo(e2);
104        }
105    };
106
107
108    /**
109     * Constructor for WordFactory.
110     */
111    public WordFactory() {
112        this("");
113    }
114
115
116    /**
117     * Constructor for WordFactory.
118     * @param s String of single letters for alphabet
119     */
120    public WordFactory(String s) {
121        if (s == null) {
122            throw new IllegalArgumentException("null string not allowed");
123        }
124        String alp = cleanSpace(s);
125        translation = null;
126        Map<String, Integer> hist = Word.histogram(alp);
127        if (hist.size() != alp.length()) {
128            logger.warn("multiple characters in String: {}", hist);
129            //Set<String> k = hist.keySet();
130            String[] ka = hist.keySet().toArray(new String[hist.size()]);
131            alphabet = concat(ka);
132        } else {
133            alphabet = alp;
134        }
135        //System.out.println("hist = " + hist);
136        ONE = new Word(this, "", false);
137    }
138
139
140    /**
141     * Constructor for WordFactory.
142     * @param S String array for alphabet
143     */
144    public WordFactory(String[] S) {
145        String[] V = cleanAll(S);
146        if (isSingleLetters(V)) {
147            alphabet = concat(V);
148            translation = null;
149        } else {
150            alphabet = transRef.substring(0, V.length);
151            translation = V;
152            logger.info("alphabet = {}, translation = {}", alphabet, Arrays.toString(translation));
153        }
154        ONE = new Word(this, "", false);
155    }
156
157
158    /**
159     * Is this structure finite or infinite.
160     * @return true if this structure is finite, else false.
161     * @see edu.jas.structure.ElemFactory#isFinite()
162     */
163    public boolean isFinite() {
164        if (alphabet.length() == 0) {
165            return true;
166        }
167        return false;
168    }
169
170
171    /**
172     * Query if this monoid is commutative.
173     * @return true if this monoid is commutative, else false.
174     */
175    public boolean isCommutative() {
176        if (alphabet.length() == 0) {
177            return true;
178        }
179        return false;
180    }
181
182
183    /**
184     * Query if this monoid is associative.
185     * @return true if this monoid is associative, else false.
186     */
187    public boolean isAssociative() {
188        return true;
189    }
190
191
192    /**
193     * Get the one element, the empty word.
194     * @return 1 as Word.
195     */
196    public Word getONE() {
197        return ONE;
198    }
199
200
201    /**
202     * Copy word.
203     * @param w word to copy.
204     * @return copy of w.
205     */
206    @Override
207    public Word copy(Word w) {
208        return new Word(this, w.getVal(), false);
209    }
210
211
212    /**
213     * Get the alphabet length.
214     * @return alphabet.length.
215     */
216    public int length() {
217        return alphabet.length();
218    }
219
220
221    /**
222     * Get the alphabet String.
223     * @return alphabet.
224     */
225    /*package*/String getVal() {
226        return alphabet;
227    }
228
229
230    /**
231     * Get the translation array of Strings.
232     * @return alphabet.
233     */
234    /*package*/String[] getTrans() {
235        return translation;
236    }
237
238
239    /**
240     * Get the alphabet letter at position i.
241     * @param i position.
242     * @return val[i].
243     */
244    public char getVal(int i) {
245        return alphabet.charAt(i);
246    }
247
248
249    /**
250     * Get the variable names.
251     * @return array of variable names
252     */
253    public String[] getVars() {
254        String[] vars = new String[alphabet.length()];
255        if (translation == null) {
256            for (int i = 0; i < alphabet.length(); i++) {
257                vars[i] = String.valueOf(getVal(i));
258            }
259        } else {
260            for (int i = 0; i < alphabet.length(); i++) {
261                vars[i] = translation[i];
262            }
263        }
264        return vars;
265    }
266
267
268    /**
269     * Extend variables. Extend number of variables by length(vn). 
270     * @param vn names for extended variables.
271     * @return extended word ring factory.
272     */
273    public WordFactory extend(String[] vn) {
274        String[] vars = new String[length() + vn.length];
275        int i = 0;
276        for (String v : getVars()) {
277            vars[i++] = v;
278        }
279        for (String v : vn) {
280            vars[i++] = v;
281        }
282        return new WordFactory(vars);
283    }
284
285    
286    /**
287     * Get the string representation.
288     * @see java.lang.Object#toString()
289     */
290    @Override
291    public String toString() {
292        StringBuffer s = new StringBuffer("\"");
293        if (translation == null) {
294            for (int i = 0; i < alphabet.length(); i++) {
295                if (i != 0) {
296                    s.append(",");
297                }
298                s.append(getVal(i));
299            }
300        } else {
301            for (int i = 0; i < alphabet.length(); i++) {
302                if (i != 0) {
303                    s.append(",");
304                }
305                s.append(translation[i]);
306            }
307        }
308        s.append("\"");
309        return s.toString();
310    }
311
312
313    /**
314     * Get a scripting compatible string representation.
315     * @return script compatible representation for this Element.
316     * @see edu.jas.structure.Element#toScript()
317     */
318    @Override
319    public String toScript() {
320        return toString();
321    }
322
323
324    /**
325     * Comparison with any other object.
326     * @see java.lang.Object#equals(java.lang.Object)
327     */
328    @Override
329    public boolean equals(Object B) {
330        if (!(B instanceof WordFactory)) {
331            return false;
332        }
333        WordFactory b = (WordFactory) B;
334        return alphabet.equals(b.alphabet);
335    }
336
337
338    /**
339     * hashCode.
340     * @see java.lang.Object#hashCode()
341     */
342    @Override
343    public int hashCode() {
344        return alphabet.hashCode();
345    }
346
347
348    /**
349     * Get a list of the generating elements.
350     * @return list of generators for the algebraic structure.
351     */
352    public List<Word> generators() {
353        int len = alphabet.length();
354        List<Word> gens = new ArrayList<Word>(len);
355        // ONE is not a word generator
356        for (int i = 0; i < len; i++) {
357            Word w = new Word(this, String.valueOf(alphabet.charAt(i)), false);
358            gens.add(w);
359        }
360        return gens;
361    }
362
363
364    /**
365     * Get the Element for a.
366     * @param a long
367     * @return element corresponding to a.
368     */
369    public Word fromInteger(long a) {
370        throw new UnsupportedOperationException("not implemented for WordFactory");
371    }
372
373
374    /**
375     * Get the Element for a.
376     * @param a java.math.BigInteger.
377     * @return element corresponding to a.
378     */
379    public Word fromInteger(BigInteger a) {
380        throw new UnsupportedOperationException("not implemented for WordFactory");
381    }
382
383
384    /**
385     * Get the Element for an ExpVector.
386     * @param e ExpVector.
387     * @return element corresponding to e.
388     */
389    public Word valueOf(ExpVector e) {
390        Word w = ONE;
391        List<Word> gens = generators();
392        int n = alphabet.length();
393        int m = e.length();
394        if (m > n) {
395            throw new IllegalArgumentException("alphabet to short for exponent " + e + ", alpahbet = "
396                            + alphabet);
397        }
398        for (int i = 0; i < m; i++) {
399            int x = (int) e.getVal(m - i - 1);
400            Word y = gens.get(i);
401            Word u = ONE;
402            for (int j = 0; j < x; j++) {
403                u = u.multiply(y);
404            }
405            w = w.multiply(u);
406        }
407        return w;
408    }
409
410
411    /**
412     * Get the element from an other word.
413     * @param w other word.
414     * @return w in this word factory.
415     */
416    public Word valueOf(Word w) {
417        String s = w.toString();
418        return parse(s);
419    }
420
421    
422    /**
423     * IndexOf for letter in alphabet.
424     * @param s letter character.
425     * @return index of s in the alphabet, or -1 if s is not contained in the alphabet.
426     */
427    public int indexOf(char s) {
428        return alphabet.indexOf(s);
429    }
430
431
432    /**
433     * Generate a random Element with size less equal to n.
434     * @param n
435     * @return a random element.
436     */
437    public Word random(int n) {
438        return random(n, random);
439    }
440
441
442    /**
443     * Generate a random Element with size less equal to n.
444     * @param n
445     * @param random is a source for random bits.
446     * @return a random element.
447     */
448    public Word random(int n, Random random) {
449        StringBuffer sb = new StringBuffer();
450        int len = alphabet.length();
451        for (int i = 0; i < n; i++) {
452            int r = Math.abs(random.nextInt() % len);
453            sb.append(alphabet.charAt(r));
454        }
455        return new Word(this, sb.toString(), false);
456    }
457
458
459    /**
460     * Parse from String.
461     * @param s String.
462     * @return a Element corresponding to s.
463     */
464    public Word parse(String s) {
465        String st = clean(s);
466        String regex;
467        if (translation == null) {
468            regex = "[" + alphabet + " ]*";
469        } else {
470            regex = "[" + concat(translation) + " ]*";
471        }
472        if (!st.matches(regex)) {
473            throw new IllegalArgumentException("word '" + st + "' contains letters not from: " + alphabet
474                            + " or from " + concat(translation));
475        }
476        // now only alphabet or translation chars are contained in st
477        return new Word(this, st, true);
478    }
479
480
481    /**
482     * Parse from Reader. White space is delimiter for word.
483     * @param r Reader.
484     * @return the next Element found on r.
485     */
486    public Word parse(Reader r) {
487        return parse(StringUtil.nextString(r));
488    }
489
490
491    /**
492     * Test if the alphabet of w is a subalphabet of this.
493     * @param w other word factory to test.
494     * @return true, if w is a subalphabet of this, else false.
495     */
496    public boolean isSubFactory(WordFactory w) {
497        if (w == null) {
498            throw new IllegalArgumentException("w may not be null");
499        }
500        String s = w.toString().replace(",", " ");
501        Word c = null;
502        try {
503            c = parse(s);
504        } catch (IllegalArgumentException ignored) {
505            // ignore
506        }
507        //System.out.println("c: " + c + ", s = " + s);
508        if (c != null) {
509            return true;
510        }
511        return false;
512    }
513
514
515    /**
516     * Contract word to this word factory.
517     * <code>this.isSubFactory(w.mono)</code> must be true, otherwise null is returned.
518     * @param w other word to contract.
519     * @return w with this factory, or null if not contractable.
520     */
521    public Word contract(Word w) {
522        if (w == null) {
523            throw new IllegalArgumentException("w may not be null");
524        }
525        Word c = null;
526        try {
527            c = parse(w.toString());
528        } catch (IllegalArgumentException ignored) {
529            // ignore
530        }
531        return c;
532    }
533
534    
535    /**
536     * Get the descending order comparator. Sorts the highest terms first.
537     * @return horder.
538     */
539    public WordComparator getDescendComparator() {
540        return horder;
541    }
542
543
544    /**
545     * Get the ascending order comparator. Sorts the lowest terms first.
546     * @return lorder.
547     */
548    public WordComparator getAscendComparator() {
549        return lorder;
550    }
551
552
553    /**
554     * Prepare parse from String.
555     * @param s String.
556     * @return a Element corresponding to s.
557     */
558    public static String cleanSpace(String s) {
559        String st = s.trim();
560        st = st.replaceAll("\\*", "");
561        st = st.replaceAll("\\s", "");
562        st = st.replaceAll("\\(", "");
563        st = st.replaceAll("\\)", "");
564        st = st.replaceAll("\\\"", "");
565        return st;
566    }
567
568
569    /**
570     * Prepare parse from String.
571     * @param s String.
572     * @return a Element corresponding to s.
573     */
574    public static String clean(String s) {
575        String st = s.trim();
576        st = st.replaceAll("\\*", " ");
577        //st = st.replaceAll("\\s", "");
578        st = st.replaceAll("\\(", "");
579        st = st.replaceAll("\\)", "");
580        st = st.replaceAll("\\\"", "");
581        return st;
582    }
583
584
585    /**
586     * Prepare parse from String array.
587     * @param v String array.
588     * @return an array of cleaned strings.
589     */
590    public static String[] cleanAll(String[] v) {
591        String[] t = new String[v.length];
592        for (int i = 0; i < v.length; i++) {
593            t[i] = cleanSpace(v[i]);
594            if (t[i].length() == 0) {
595                logger.error("empty v[i]: '{}'", v[i]);
596            }
597            //System.out.println("clean all: " + v[i] + " --> " + t[i]);
598        }
599        return t;
600    }
601
602
603    /**
604     * Concat variable names.
605     * @param v an array of strings.
606     * @return the concatenation of the strings in v.
607     */
608    public static String concat(String[] v) {
609        StringBuffer s = new StringBuffer();
610        if (v == null) {
611            return s.toString();
612        }
613        for (int i = 0; i < v.length; i++) {
614            s.append(v[i]);
615        }
616        return s.toString();
617    }
618
619
620    /**
621     * Trim all variable names.
622     * @param v an array of strings.
623     * @return an array of strings with all elements trimmed.
624     */
625    public static String[] trimAll(String[] v) {
626        String[] t = new String[v.length];
627        for (int i = 0; i < v.length; i++) {
628            t[i] = v[i].trim();
629            if (t[i].length() == 0) {
630                logger.error("empty v[i]: '{}'", v[i]);
631            }
632        }
633        return t;
634    }
635
636
637    /**
638     * IndexOf for String array.
639     * @param v an array of strings.
640     * @param s string.
641     * @return index of s in v, or -1 if s is not contained in v.
642     */
643    public static int indexOf(String[] v, String s) {
644        for (int i = 0; i < v.length; i++) {
645            if (s.equals(v[i])) {
646                return i;
647            }
648        }
649        return -1;
650    }
651
652
653    /**
654     * Test if all variables are single letters.
655     * @param v an array of strings.
656     * @return true, if all variables have length 1, else false.
657     */
658    public static boolean isSingleLetters(String[] v) {
659        for (int i = 0; i < v.length; i++) {
660            if (v[i].length() != 1) {
661                return false;
662            }
663        }
664        return true;
665    }
666
667
668    /**
669     * Translate variable names.
670     * @param v an array of strings.
671     * @return the translated string of v with respect to t.
672     */
673    public String translate(String[] v) {
674        StringBuffer s = new StringBuffer();
675        for (int i = 0; i < v.length; i++) {
676            String a = v[i];
677            int k = indexOf(translation, a);
678            if (k < 0) {
679                System.out.println("t = " + Arrays.toString(translation));
680                System.out.println("v = " + Arrays.toString(v));
681                logger.error("v[i] not found in t: {}", a);
682                //continue;
683                throw new IllegalArgumentException("v[i] not found in t: " + a);
684            }
685            s.append(transRef.charAt(k));
686        }
687        return s.toString();
688    }
689
690
691    /**
692     * Translate variable name.
693     * @param c internal char.
694     * @return the external translated string.
695     */
696    public String transVar(char c) {
697        int k = alphabet.indexOf(c);
698        return translation[k];
699    }
700
701}