001/*
002 * $Id: Word.java 5873 2018-07-22 14:40:25Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.util.SortedMap;
009import java.util.TreeMap;
010
011import edu.jas.structure.MonoidElem;
012import edu.jas.structure.MonoidFactory;
013import edu.jas.structure.NotInvertibleException;
014
015
016/**
017 * Word implements strings of letters for polynomials.
018 * @author Heinz Kredel
019 */
020
021public final class Word implements MonoidElem<Word> {
022
023
024    /**
025     * Defining alphabet in WordFactory.
026     */
027    public final WordFactory mono;
028
029
030    /**
031     * The data structure is a String of characters.
032     */
033    /*package*/final String val;
034
035
036    /**
037     * Stored hash code.
038     */
039    protected int hash = 0;
040
041
042    /**
043     * Constructor for Word.
044     * @param m factory for words.
045     */
046    public Word(WordFactory m) {
047        this(m, "");
048    }
049
050
051    /**
052     * Constructor for Word.
053     * @param m factory for words.
054     * @param s String
055     */
056    public Word(WordFactory m, String s) {
057        this(m, s, true);
058    }
059
060
061    /**
062     * Constructor for Word.
063     * @param m factory for words.
064     * @param s String
065     * @param translate indicator if s needs translation
066     */
067    public Word(WordFactory m, String s, boolean translate) {
068        mono = m;
069        hash = 0;
070        if (s == null) {
071            throw new IllegalArgumentException("null string not allowed");
072        }
073        if (translate) {
074            if (mono.translation != null) {
075                //System.out.println("s = " + s);
076                String[] S = GenPolynomialTokenizer.variableList(s);
077                //System.out.println("S = " + Arrays.toString(S));
078                val = mono.translate(S);
079                //System.out.println("val = " + val);
080            } else {
081                val = WordFactory.cleanSpace(s); //??
082            }
083        } else {
084            val = s;
085        }
086    }
087
088
089    /**
090     * Get the corresponding element factory.
091     * @return factory for this Element.
092     * @see edu.jas.structure.Element#factory()
093     */
094    public MonoidFactory<Word> factory() {
095        return mono;
096    }
097
098
099    /**
100     * Copy this.
101     * @return copy of this.
102     */
103    @Override
104    public Word copy() {
105        return new Word(mono, val, false);
106    }
107
108
109    /**
110     * Get the word String.
111     * @return val.
112     */
113    /*package*/String getVal() {
114        return val;
115    }
116
117
118    /**
119     * Get the letter at position i.
120     * @param i position.
121     * @return val[i].
122     */
123    public char getVal(int i) {
124        return val.charAt(i);
125    }
126
127
128    /**
129     * Get the length of this word.
130     * @return val.length.
131     */
132    public int length() {
133        return val.length();
134    }
135
136
137    /**
138     * Get the string representation.
139     * @see java.lang.Object#toString()
140     */
141    @Override
142    public String toString() {
143        if (val.length() == 0) {
144            return "";
145        }
146        StringBuffer s = new StringBuffer("\"");
147        if (mono.translation == null) {
148            for (int i = 0; i < length(); i++) {
149                if (i != 0) {
150                    s.append(" ");
151                }
152                s.append(getVal(i));
153            }
154        } else {
155            for (int i = 0; i < length(); i++) {
156                if (i != 0) {
157                    s.append(" ");
158                }
159                s.append(mono.transVar(getVal(i)));
160            }
161        }
162        s.append("\"");
163        return s.toString();
164    }
165
166
167    /**
168     * Get a scripting compatible string representation.
169     * @return script compatible representation for this Element.
170     * @see edu.jas.structure.Element#toScript()
171     */
172    @Override
173    public String toScript() {
174        if (val.length() == 0) {
175            return "";
176        }
177        StringBuffer s = new StringBuffer("");
178        if (mono.translation == null) {
179            for (int i = 0; i < length(); i++) {
180                if (i != 0) {
181                    s.append("*"); // checked for python vs ruby
182                }
183                s.append(getVal(i));
184            }
185        } else {
186            for (int i = 0; i < length(); i++) {
187                if (i != 0) {
188                    s.append("*"); // checked for python vs ruby
189                }
190                s.append(mono.transVar(getVal(i)));
191            }
192        }
193        s.append("");
194        return s.toString();
195    }
196
197
198    /**
199     * Get a scripting compatible string representation of the factory.
200     * @return script compatible representation for this ElemFactory.
201     * @see edu.jas.structure.Element#toScriptFactory()
202     */
203    @Override
204    public String toScriptFactory() {
205        // Python case
206        return mono.toString();
207    }
208
209
210    /**
211     * Comparison with any other object.
212     * @see java.lang.Object#equals(java.lang.Object)
213     */
214    @Override
215    public boolean equals(Object B) {
216        if (!(B instanceof Word)) {
217            return false;
218        }
219        Word b = (Word) B;
220        // mono == b.mono ??
221        int t = this.compareTo(b);
222        //System.out.println("equals: this = " + this.val + " b = " + b.val + " t = " + t);
223        return (0 == t);
224    }
225
226
227    /**
228     * hashCode.
229     * @see java.lang.Object#hashCode()
230     */
231    @Override
232    public int hashCode() {
233        if (hash == 0) {
234            hash = val.hashCode();
235        }
236        return hash;
237    }
238
239
240    /**
241     * Is Word one.
242     * @return If this is the empty word then true is returned, else false.
243     */
244    public boolean isONE() {
245        return val.isEmpty();
246    }
247
248
249    /**
250     * Is Word unit.
251     * @return If this is a unit then true is returned, else false.
252     */
253    public boolean isUnit() {
254        return isONE();
255    }
256
257
258    /**
259     * Word multiplication.
260     * @param V other word.
261     * @return this * V.
262     */
263    public Word multiply(Word V) {
264        return new Word(mono, this.val + V.val, false);
265    }
266
267
268    /**
269     * Word divide.
270     * @param V other word.
271     * @return this / V.
272     */
273    public Word divide(Word V) {
274        return divideLeft(V);
275    }
276
277
278    /**
279     * Word divide left.
280     * @param V other word.
281     * @return this / V = left, with left * V = this.
282     */
283    public Word divideLeft(Word V) {
284        Word[] ret = divideWord(V,false);
285        // fail if right is non zero
286        if (!ret[1].isONE()) {
287            throw new IllegalArgumentException("not simple left dividable: left = " + ret[0] + ", right = "
288                            + ret[1] + ", use divideWord");
289        }
290        return ret[0];
291    }
292
293
294    /**
295     * Word divide right.
296     * @param V other word.
297     * @return this / V = right, with V * right = this.
298     */
299    public Word divideRight(Word V) {
300        Word[] ret = divideWord(V,true);
301        // fail if left is non zero
302        if (!ret[0].isONE()) {
303            throw new IllegalArgumentException("not simple right dividable: left = " + ret[0] + ", right = "
304                            + ret[1] + ", use divideWord");
305        }
306        return ret[1];
307    }
308
309
310    /**
311     * Word divide with prefix and suffix.
312     * @param V other word.
313     * @return [left,right] with left * V * right = this.
314     */
315    public Word[] divideWord(Word V) {
316        return divideWord(V,true); 
317    }
318
319    /**
320     * Word divide with prefix and suffix.
321     * @param V other word.
322     * @param first is true for first index, false for last index.
323     * @return [left,right] with left * V * right = this.
324     */
325    public Word[] divideWord(Word V, boolean first) {
326        int i;
327        if (first) {
328            i = this.val.indexOf(V.val);
329        } else {
330            i = this.val.lastIndexOf(V.val);
331        }
332        if (i < 0) {
333            throw new NotInvertibleException("not dividable: " + this + ", other " + V);
334        }
335        int len = V.val.length();
336        String pre = this.val.substring(0, i);
337        String suf = this.val.substring(i + len);
338        Word[] ret = new Word[2];
339        ret[0] = new Word(mono, pre, false);
340        ret[1] = new Word(mono, suf, false);
341        return ret;
342    }
343
344
345    /**
346     * Word remainder.
347     * @param V other word.
348     * @return this (this/V). <b>Note:</b> not useful.
349     */
350    public Word remainder(Word V) {
351        int i = this.val.indexOf(V.val);
352        if (i < 0) {
353            throw new NotInvertibleException("not dividable: " + this + ", other " + V);
354        }
355        return V;
356    }
357
358
359    /**
360     * Quotient and remainder by division of this by S.
361     * @param S a Word
362     * @return [this/S, this - (this/S)*S]. <b>Note:</b> not useful.
363     */
364    public Word[] quotientRemainder(Word S) {
365        return new Word[] { divide(S), remainder(S) };
366    }
367
368
369    /**
370     * Word inverse.
371     * @return 1 / this.
372     */
373    public Word inverse() {
374        if (val.length() == 0) {
375            return this;
376        }
377        throw new NotInvertibleException("not inversible " + this);
378    }
379
380
381    /**
382     * Word signum.
383     * @return 0 if this is one, 1 if it is non empty.
384     */
385    public int signum() {
386        int i = val.length();
387        if (i > 0) {
388            i = 1;
389        }
390        assert i >= 0;
391        return i;
392    }
393
394
395    /**
396     * Word degree.
397     * @return total degree of all letters.
398     */
399    public long degree() {
400        return val.length();
401    }
402
403
404    /**
405     * Word dependency on letters.
406     * @return sorted map of letters and the number of its occurences.
407     */
408    public SortedMap<String, Integer> dependencyOnVariables() {
409        return histogram(val);
410    }
411
412
413    /**
414     * String dependency on letters.
415     * @param v string.
416     * @return sorted map of letters and the number of its occurences.
417     */
418    public static SortedMap<String, Integer> histogram(String v) {
419        SortedMap<String, Integer> map = new TreeMap<String, Integer>();
420        for (int i = 0; i < v.length(); i++) {
421            String s = String.valueOf(v.charAt(i));
422            Integer n = map.get(s);
423            if (n == null) {
424                n = 0;
425            }
426            n = n + 1;
427            map.put(s, n);
428        }
429        return map;
430    }
431
432
433    /**
434     * Word leading exponent vector.
435     * @return an ExpVector for the first power of a letter.
436     */
437    public ExpVector leadingExpVector() {
438        long n = 0;
439        char letter = ' ';
440        for (int i = 0; i < val.length(); i++) {
441            char s = val.charAt(i);
442            if (n == 0) {
443                letter = s;
444                n++;
445            } else if (letter == s) {
446                n++;
447            } else {
448                break;
449            }
450        }
451        int k = mono.length();
452        if (n == 0L){ // == isONE()
453            return ExpVector.create(k);
454        }
455        int j = k - mono.indexOf(letter) - 1;
456        return ExpVector.create(k,j,n);
457    }
458
459
460    /**
461     * Word without leading exponent vector.
462     * @return an Word without the first power of a letter.
463     */
464    public Word reductum() {
465        if (isONE()) {
466            return this;
467        }
468        int n = 0;
469        char letter = ' ';
470        for (int i = 0; i < val.length(); i++) {
471            char s = val.charAt(i);
472            if (n == 0) {
473                letter = s;
474                n++;
475            } else if (letter == s) {
476                n++;
477            } else {
478                break;
479            }
480        }
481        // n != 0
482        String r = val.substring(n); // n-1+1
483        return new Word(mono, r, false);
484    }
485
486
487    /**
488     * Word multiple test.
489     * @param V other word.
490     * @return true if this is a multiple of V, else false.
491     */
492    public boolean multipleOf(Word V) {
493        return this.val.contains(V.val);
494    }
495
496
497    /**
498     * Word divides test.
499     * @param V other word.
500     * @return true if this divides V, else false.
501     */
502    public boolean divides(Word V) {
503        return V.val.contains(this.val);
504    }
505
506
507    /**
508     * Word compareTo. Uses <code>String.compareTo</code>.
509     * @param V other word.
510     * @return 0 if U == V, -1 if U &lt; V, 1 if U &gt; V.
511     */
512    @Override
513    public int compareTo(Word V) {
514        if (mono == V.mono) {
515            return val.compareTo(V.val);
516        }
517        //System.out.println("compareTo: mono " + mono + ", V = " + V.mono);
518        return toString().compareTo(V.toString());
519    }
520
521
522    /**
523     * Word graded comparison. Compares first be degree, then lexicographical.
524     * @param V other word.
525     * @return 0 if U == V, -1 if U &lt; V, 1 if U &gt; V.
526     */
527    public int gradCompareTo(Word V) {
528        long e = this.degree();
529        long f = V.degree();
530        if (e < f) {
531            return 1;
532        } else if (e > f) {
533            return -1;
534        }
535        return this.compareTo(V);
536    }
537
538
539    /**
540     * Word graded comparison. Compares first be degree, then inverse
541     * lexicographical.
542     * @param V other word.
543     * @return 0 if U == V, -1 if U &lt; V, 1 if U &gt; V.
544     */
545    public int gradInvlexCompareTo(Word V) {
546        long e = this.degree();
547        long f = V.degree();
548        if (e < f) {
549            return 1;
550        } else if (e > f) {
551            return -1;
552        }
553        return -this.compareTo(V);
554    }
555
556
557    /**
558     * Is word overlap.
559     * @param ol = [l1,r1,l2,r2] an Overlap container of four words
560     * @param V word
561     * @return true if l1 * this * r1 = l2 * V * r2, else false.
562     */
563    public boolean isOverlap(Overlap ol, Word V) {
564        return ol.isOverlap(this, V);
565    }
566
567
568    /**
569     * Word overlap list.
570     * @param V other word.
571     * @return list of overlaps [l1,r1,l2,r2] with l1 * this * r1 = l2 * V * r2.
572     *         If no such overlaps exist the empty overlap list is returned.
573     */
574    public OverlapList overlap(Word V) {
575        OverlapList ret = new OverlapList();
576        Word wone = mono.getONE();
577        String a = this.val;
578        String b = V.val;
579        int ai = a.length();
580        int bi = b.length();
581        int j = b.indexOf(a);
582        if (j >= 0) {
583            while (j >= 0) {
584                String pre = b.substring(0, j);
585                String suf = b.substring(j + ai);
586                Word wpre = new Word(mono, pre, false);
587                Word wsuf = new Word(mono, suf, false);
588                ret.add(new Overlap(wpre, wsuf, wone, wone));
589                j = b.indexOf(a, j + ai); // +1 also inner overlaps ?
590            }
591            return ret;
592        }
593        j = a.indexOf(b);
594        if (j >= 0) {
595            while (j >= 0) {
596                String pre = a.substring(0, j);
597                String suf = a.substring(j + bi);
598                Word wpre = new Word(mono, pre, false);
599                Word wsuf = new Word(mono, suf, false);
600                ret.add(new Overlap(wone, wone, wpre, wsuf));
601                j = a.indexOf(b, j + bi); // +1 also inner overlaps ?
602            }
603            return ret;
604        }
605        if (ai >= bi) {
606            for (int i = 0; i < bi; i++) {
607                String as = a.substring(0, i + 1);
608                String bs = b.substring(bi - i - 1, bi);
609                //System.out.println("i = " + i + ", bs = " + bs + ", as = " + as);
610                if (as.equals(bs)) {
611                    Word w1 = new Word(mono, b.substring(0, bi - i - 1), false);
612                    Word w2 = new Word(mono, a.substring(i + 1), false);
613                    ret.add(new Overlap(w1, wone, wone, w2));
614                    break;
615                }
616            }
617            for (int i = 0; i < bi; i++) {
618                String as = a.substring(ai - i - 1, ai);
619                String bs = b.substring(0, i + 1);
620                //System.out.println("i = " + i + ", bs = " + bs + ", as = " + as);
621                if (as.equals(bs)) {
622                    Word w1 = new Word(mono, b.substring(i + 1), false);
623                    Word w2 = new Word(mono, a.substring(0, ai - i - 1), false);
624                    ret.add(new Overlap(wone, w1, w2, wone));
625                    break;
626                }
627            }
628        } else { // ai < bi
629            for (int i = 0; i < ai; i++) {
630                String as = a.substring(ai - i - 1, ai);
631                String bs = b.substring(0, i + 1);
632                //System.out.println("i = " + i + ", bs = " + bs + ", as = " + as);
633                if (as.equals(bs)) {
634                    Word w1 = new Word(mono, b.substring(i + 1), false);
635                    Word w2 = new Word(mono, a.substring(0, ai - i - 1), false);
636                    ret.add(new Overlap(wone, w1, w2, wone));
637                    break;
638                }
639            }
640            for (int i = 0; i < ai; i++) {
641                String as = a.substring(0, i + 1);
642                String bs = b.substring(bi - i - 1, bi);
643                //System.out.println("i = " + i + ", bs = " + bs + ", as = " + as);
644                if (as.equals(bs)) {
645                    Word w1 = new Word(mono, b.substring(0, bi - i - 1), false);
646                    Word w2 = new Word(mono, a.substring(i + 1), false);
647                    ret.add(new Overlap(w1, wone, wone, w2));
648                    break;
649                }
650            }
651        }
652        return ret;
653    }
654
655
656    /**
657     * Word pseudo least common multiple.
658     * @param V other word.
659     * @return w = l1*this*r1, with l1*this*r1 == l2*V*r2, if l1, r1, l2, r2
660     *         exist, else null is returned.
661     */
662    public Word lcm(Word V) {
663        OverlapList oll = overlap(V);
664        if (oll.ols.isEmpty()) {
665            return null;
666        }
667        Overlap ol = oll.ols.get(0);
668        Word w = ol.l1.multiply(this).multiply(ol.r1);
669        return w;
670    }
671
672}