001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.io.Reader;
009import java.io.Serializable;
010import java.util.ArrayList;
011import java.util.Arrays;
012import java.util.Collection;
013import java.util.Comparator;
014import java.util.List;
015import java.util.Random;
016
017import org.apache.logging.log4j.LogManager;
018import org.apache.logging.log4j.Logger;
019
020import edu.jas.kern.StringUtil;
021import edu.jas.structure.MonoidFactory;
022
023
024/**
025 * IndexList factory implements a factory for index lists for exterior
026 * polynomials. Objects of this class are intended to be immutable. If in doubt
027 * use <code>valueOf</code> to get a conformant index list.
028 * @see "masnc.DIPE.mi#ILEXPR from SAC2/MAS"
029 * @author Heinz Kredel
030 */
031
032public class IndexFactory implements MonoidFactory<IndexList> {
033
034
035    /**
036     * The maximal length index list for this factory.
037     */
038    public final int imaxlength;
039
040
041    /**
042     * The coordinate variable name.
043     */
044    public final String vname;
045
046
047    /**
048     * The maximal index list for this factory.
049     */
050    public final IndexList imax;
051
052
053    /**
054     * Defined index list comparison.
055     * Strong compare: false, weak compare: true.
056     */
057    final boolean weak;
058
059
060    /**
061     * Random number generator.
062     */
063    private final static Random random = new Random();
064
065
066    /**
067     * Log4j logger object.
068     */
069    private static final Logger logger = LogManager.getLogger(WordFactory.class);
070
071
072    /**
073     * The one element index list.
074     */
075    public final IndexList ONE;
076
077
078    /**
079     * The default coordinate variable name.
080     */
081    public static final String DEFAULT_VNAME = "E";
082
083
084    /**
085     * The default imaxlength for this index lists.
086     */
087    public static final int DEFAULT_SIZE = 4;
088
089
090    /**
091     * Constructor for IndexFactory. No argument constructor .
092     */
093    public IndexFactory() {
094        this(DEFAULT_SIZE, DEFAULT_VNAME);
095    }
096
097
098    /**
099     * Constructor for IndexFactory.
100     * @param r length of index lists, starting with index 1.
101     */
102    public IndexFactory(int r) {
103        this(1, r, DEFAULT_VNAME, false);
104    }
105
106
107    /**
108     * Constructor for IndexFactory.
109     * @param r length of index lists, starting with index 1.
110     * @param w termorder for index lists: true for weak, false for strong.
111     */
112    public IndexFactory(int r, boolean w) {
113        this(1, r, DEFAULT_VNAME, w);
114    }
115
116
117    /**
118     * Constructor for IndexFactory.
119     * @param r length of index lists, starting with index 1.
120     * @param v coordinate vname.
121     */
122    public IndexFactory(int r, String v) {
123        this(1, r, v, false);
124    }
125
126
127    /**
128     * Constructor for IndexFactory.
129     * @param r length of index lists, starting with index 1.
130     * @param v coordinate vname.
131     * @param w termorder for index lists: true for weak, false for strong.
132     */
133    public IndexFactory(int r, String v, boolean w) {
134        this(1, r, v, w);
135    }
136
137
138    /**
139     * Constructor for IndexFactory.
140     * @param s start index.
141     * @param t length of index lists.
142     */
143    public IndexFactory(int s, int t) {
144        this(s, t, DEFAULT_VNAME, false);
145    }
146
147
148    /**
149     * Constructor for IndexFactory.
150     * @param s start index.
151     * @param t length of index lists.
152     * @param v coordinate vname.
153     * @param w termorder for index lists: true for weak, false for strong.
154     */
155    public IndexFactory(int s, int t, String v, boolean w) {
156        // not possible: this(new IndexList(this, 1, sequenceArray(s, t)), v);
157        if (t < 0) {
158            throw new IllegalArgumentException("negative length index not allowed");
159        }
160        if (s < 0) {
161            throw new IllegalArgumentException("negative start index not allowed");
162        }
163        imaxlength = t;
164        vname = v;
165        weak = w;
166        imax = new IndexList(this, 1, sequenceArray(s, imaxlength));
167        ONE = new IndexList(this, 1, sequenceArray(s, 0));
168    }
169
170
171    // /** not meaningful
172    //  * Constructor for IndexFactory.
173    //  * @param o some index list.
174    //  * @param v coordinate vname.
175    //  */
176    // public IndexFactory(IndexList o, String v) {
177    //     if (o == null) {
178    //         throw new IllegalArgumentException("null index list not allowed");
179    //     }
180    //     int b = o.minDeg();
181    //     int e = o.maxDeg();
182    //     imaxlength = e - b + 1;
183    //     vname = v;
184    //     imax = new IndexList(this, 1, sequenceArray(b, imaxlength));
185    //     if (imaxlength != o.length()) {
186    //         logger.warn("length do not match: {} != {}", imaxlength, o.length());
187    //     }
188    //     ONE = new IndexList(this, 1, sequenceArray(1, 0));
189    // }
190
191
192    // /**
193    //  * Constructor for IndexFactory.
194    //  * @param o some index list.
195    //  */
196    // public IndexFactory(IndexList o) {
197    //     this(o, o.mono.vname);
198    // }
199
200
201    /**
202     * Is this structure finite or infinite.
203     * @return true if this structure is finite, else false.
204     * @see edu.jas.structure.ElemFactory#isFinite() <b>Note: </b> returns true
205     *      because of finite set of values in each index.
206     */
207    public boolean isFinite() {
208        return true;
209    }
210
211
212    /**
213     * Query if this monoid is commutative.
214     * @return true if this monoid is commutative, else false.
215     */
216    public boolean isCommutative() {
217        if (imaxlength == 0) {
218            return true;
219        }
220        return false;
221    }
222
223
224    /**
225     * Query if this monoid is associative.
226     * @return true if this monoid is associative, else false.
227     */
228    public boolean isAssociative() {
229        return true;
230    }
231
232
233    /**
234     * Get the Element for a.
235     * @param a long
236     * @return element corresponding to a.
237     */
238    @Override
239    public IndexList fromInteger(long a) {
240        throw new UnsupportedOperationException("not implemented for IndexFactory");
241    }
242
243
244    /**
245     * Get the Element for a.
246     * @param a java.math.BigInteger.
247     * @return element corresponding to a.
248     */
249    @Override
250    public IndexList fromInteger(java.math.BigInteger a) {
251        throw new UnsupportedOperationException("not implemented for IndexFactory");
252    }
253
254
255    /**
256     * Value of other.
257     * @param e other ExpVector.
258     * @return value as IndexList.
259     */
260    public IndexList valueOf(ExpVector e) {
261        if (e == null) {
262            return getZERO();
263        }
264        int r = e.length();
265        int[] w = new int[r];
266        int ii = 0;
267        for (int i = 0; i < r; i++) {
268            long x = e.getVal(i);
269            if (x <= 0l) {
270                continue;
271            }
272            if (x > 1l) {
273                return getZERO();
274            }
275            w[ii++] = i;
276        }
277        int[] v = Arrays.copyOf(w, ii);
278        return new IndexList(this, v);
279    }
280
281
282    /**
283     * Value of other.
284     * @param var String of index names.
285     * @return value as IndexList.
286     */
287    public IndexList valueOf(String var) {
288        return sequence(0, var.length());
289    }
290
291
292    /**
293     * Value of other.
294     * @param e other Collection of Integer indexes.
295     * @return value as IndexList.
296     */
297    public IndexList valueOf(Collection<Integer> e) {
298        if (e == null) {
299            return getZERO();
300        }
301        int r = e.size();
302        int[] w = new int[r];
303        int ii = 0;
304        for (Integer x : e) {
305            int xi = (int) x;
306            if (xi < 0) {
307                continue;
308            }
309            w[ii++] = xi;
310        }
311        int[] v = Arrays.copyOf(w, ii);
312        return new IndexList(this, v);
313    }
314
315
316    /**
317     * Value of other.
318     * @param e other int[] of indexes, may not be conform to IndexList
319     *            specification.
320     * @return value as IndexList.
321     */
322    public IndexList valueOf(int[] e) {
323        if (e == null) {
324            return getZERO();
325        }
326        int r = e.length;
327        IndexList w = new IndexList(this, new int[] {}); // = 1
328        int[] v = new int[1];
329        for (int i = 0; i < r; i++) {
330            v[0] = e[i];
331            IndexList vs = new IndexList(this, v);
332            w = w.exteriorProduct(vs);
333            if (w.isZERO()) {
334                return w;
335            }
336        }
337        //System.out.println("valueOf: " + w);
338        return w;
339    }
340
341
342    /**
343     * Value of other.
344     * @param e other IndexList, may not be conform to IndexList specification.
345     * @return value as IndexList.
346     */
347    public IndexList valueOf(IndexList e) {
348        if (e == null) {
349            return getZERO();
350        }
351        return valueOf(e.val);
352    }
353
354
355    /**
356     * Generators.
357     * @return list of generators for this index list.
358     */
359    public List<IndexList> generators() {
360        List<IndexList> gens = new ArrayList<IndexList>();
361        //IndexList one = getONE();
362        //gens.add(one);
363        for (int i = 0; i < imax.val.length; i++) {
364            int[] v = new int[1];
365            v[0] = imax.val[i];
366            IndexList vs = new IndexList(this, v);
367            gens.add(vs);
368        }
369        //System.out.println("gens: " + gens + ", val = " + Arrays.toString(val));
370        return gens;
371    }
372
373
374    /**
375     * Clone IndexList.
376     * @see java.lang.Object#clone()
377     */
378    @Override
379    public IndexList copy(IndexList o) {
380        if (o == null) {
381            return o;
382        }
383        return o.copy();
384    }
385
386
387    /**
388     * Get the maximal length of index lists of this factory.
389     * @return imaxlength.
390     */
391    public int length() {
392        return imaxlength;
393    }
394
395
396    /**
397     * Get the string representation.
398     * @see java.lang.Object#toString()
399     */
400    @Override
401    public String toString() {
402        if (! weak) {
403            return imax.toString();
404        }
405        StringBuffer s = new StringBuffer(imax.toString());
406        s.append("[" + weak + "]");
407        return s.toString();
408    }
409
410
411    /**
412     * Get a scripting compatible string representation.
413     * @return script compatible representation for this Element.
414     * @see edu.jas.structure.Element#toScript()
415     */
416    @Override
417    public String toScript() {
418        if (! weak) {
419            return imax.toScript();
420        }
421        StringBuffer s = new StringBuffer(imax.toScript());
422        s.append("[" + weak + "]");
423        return s.toString();
424    }
425
426
427    /**
428     * Constructor for IndexList. Converts a String representation to an
429     * IndexList. Accepted format = E(1,2,3,4,5,6,7).
430     * @param s String representation.
431     */
432    // public IndexFactory(String s) throws NumberFormatException {
433    //     this(parse(s).val);
434    // }
435
436
437    /**
438     * Parser for IndexList. Converts a String representation to an IndexList.
439     * Accepted format = E(1,2,3,4,5,6,7).
440     * @param s String representation.
441     * @return parsed IndexList
442     */
443    public IndexList parse(String s) throws NumberFormatException {
444        int[] v = null;
445        // first format = (1,2,3,4,5,6,7)
446        List<Integer> idxs = new ArrayList<Integer>();
447        s = s.trim();
448        int b = s.indexOf('(');
449        int e = s.indexOf(')', b + 1);
450        String teil;
451        int k;
452        int a;
453        if (b >= 0 && e >= 0) {
454            b++;
455            while ((k = s.indexOf(',', b)) >= 0) {
456                teil = s.substring(b, k);
457                a = Integer.parseInt(teil);
458                idxs.add(Integer.valueOf(a));
459                b = k + 1;
460            }
461            if (b <= e) {
462                teil = s.substring(b, e);
463                a = Integer.parseInt(teil);
464                idxs.add(Integer.valueOf(a));
465            }
466            int length = idxs.size();
467            v = new int[length];
468            for (int j = 0; j < length; j++) {
469                v[j] = idxs.get(j).intValue();
470            }
471        }
472        return valueOf(v); // sort and compute sign
473    }
474
475
476    /**
477     * Parse from Reader. White space is delimiter for index list.
478     * @param r Reader.
479     * @return the next Element found on r.
480     */
481    public IndexList parse(Reader r) {
482        return parse(StringUtil.nextString(r));
483    }
484
485
486    /**
487     * Comparison with any other object.
488     * @see java.lang.Object#equals(java.lang.Object)
489     */
490    @Override
491    public boolean equals(Object B) {
492        if (!(B instanceof IndexFactory)) {
493            return false;
494        }
495        IndexFactory b = (IndexFactory) B;
496        int t = imax.compareTo(b.imax);
497        //System.out.println("equals: this = " + this + " B = " + B + " t = " + t);
498        return (0 == t);
499    }
500
501
502    /**
503     * hashCode. Optimized for small indexes, i.e. &le; 2<sup>4</sup> and small
504     * number of variables, i.e. &le; 8.
505     * @see java.lang.Object#hashCode()
506     */
507    @Override
508    public int hashCode() {
509        int hash = imax.hashCode();
510        return hash;
511    }
512
513
514    /**
515     * Get IndexList zero.
516     * @return 0 IndexList.
517     */
518    public IndexList getZERO() {
519        return new IndexList(this);
520    }
521
522
523    /**
524     * Get IndexList one.
525     * @return 1 IndexList.
526     */
527    public IndexList getONE() {
528        return ONE; //?? .copy()
529    }
530
531
532    /**
533     * Generate a random IndexList.
534     * @param r length of new IndexList.
535     * @return random IndexList.
536     */
537    public final IndexList random(int r) {
538        return random(r, 0.5f, random);
539    }
540
541
542    /**
543     * Generate a random IndexList.
544     * @param r length of new IndexList.
545     * @param rnd is a source for random bits.
546     * @return random IndexList.
547     */
548    public final IndexList random(int r, Random rnd) {
549        return random(r, 0.5f, rnd);
550    }
551
552
553    /**
554     * Generate a random IndexList.
555     * @param r length of new IndexList.
556     * @param q density of nozero indexes.
557     * @return random IndexList.
558     */
559    public final IndexList random(int r, float q) {
560        return random(r, q, random);
561    }
562
563
564    /**
565     * Generate a random IndexList.
566     * @param r length of new IndexList.
567     * @param q density of nozero indexes.
568     * @param rnd is a source for random bits.
569     * @return random IndexList.
570     */
571    public final IndexList random(int r, float q, Random rnd) {
572        if (r > imaxlength || r < 0) {
573            throw new IllegalArgumentException("r > imaxlength not allowed: " + r + " > " + imaxlength);
574        }
575        if (r == 0) {
576            return getZERO();
577        }
578        int[] w = new int[r];
579        int s = 1;
580        float f;
581        f = rnd.nextFloat();
582        if (f < q * 0.001f) {
583            return getONE(); // = 0, 1 ??
584        }
585        if (f < q * q) {
586            s = -1;
587        }
588        int ii = 0;
589        int b = Math.max(Math.min(Math.abs(rnd.nextInt()) % imaxlength, imaxlength - r - 1), 1);
590        for (int i = b; i <= imaxlength && ii < r; i++) {
591            f = rnd.nextFloat();
592            if (f < q) {
593                w[ii++] = i;
594            }
595        }
596        int[] v = Arrays.copyOf(w, ii);
597        //System.out.println("v = " + Arrays.toString(v));
598        //System.out.println("this = " + this);
599        return new IndexList(this, s, v);
600    }
601
602
603    /**
604     * Generate a sequence IndexList.
605     * @param s starting index.
606     * @param r length of new IndexList.
607     * @return sequence (s, s+1, ..., s+r-1) IndexList.
608     */
609    public final IndexList sequence(int s, int r) {
610        return new IndexList(this, 1, sequenceArray(s, r));
611    }
612
613
614    /**
615     * Generate a sequence array.
616     * @param s starting index.
617     * @param r length of array.
618     * @return sequence (s, s+1, ..., s+r-1) array.
619     */
620    public static int[] sequenceArray(int s, int r) {
621        if (s < 0) {
622            throw new IllegalArgumentException("s < 0 not allowed: " + s + " < 0");
623        }
624        int[] w = new int[r];
625        for (int i = 0; i < w.length; i++) {
626            w[i] = s + i;
627        }
628        //System.out.println("v = " + Arrays.toString(w));
629        return w;
630    }
631
632
633    /**
634     * Comparator for IndexLists.
635     */
636    public static abstract class IndexListComparator implements Comparator<IndexList>, Serializable {
637
638
639        public abstract int compare(IndexList e1, IndexList e2);
640    }
641
642
643    /**
644     * Defined descending order comparator. Sorts the highest terms first.
645     */
646    private final IndexListComparator horder = new IndexListComparator() {
647
648
649        @Override
650        public int compare(IndexList e1, IndexList e2) {
651            return -e1.strongCompareTo(e2);
652        }
653    };
654
655
656    /**
657     * Defined ascending order comparator. Sorts the lowest terms first.
658     */
659    private final IndexListComparator lorder = new IndexListComparator() {
660
661
662        @Override
663        public int compare(IndexList e1, IndexList e2) {
664            return e1.strongCompareTo(e2);
665        }
666    };
667
668
669    /**
670     * Defined descending weak order comparator. Sorts the highest terms first.
671     */
672    private final IndexListComparator hweak = new IndexListComparator() {
673
674
675        @Override
676        public int compare(IndexList e1, IndexList e2) {
677            return -e1.weakCompareTo(e2);
678        }
679    };
680
681
682    /**
683     * Defined ascending weak order comparator. Sorts the lowest terms first.
684     */
685    private final IndexListComparator lweak = new IndexListComparator() {
686
687
688        @Override
689        public int compare(IndexList e1, IndexList e2) {
690            return e1.weakCompareTo(e2);
691        }
692    };
693
694
695    /**
696     * Get the descending order comparator. Sorts the highest terms first.
697     * @return horder.
698     */
699    public IndexListComparator getDescendComparator() {
700        if (weak) {
701            return hweak;
702        }
703        return horder;
704    }
705
706
707    /**
708     * Get the ascending order comparator. Sorts the lowest terms first.
709     * @return lorder.
710     */
711    public IndexListComparator getAscendComparator() {
712        if (weak) {
713            return lweak;
714        }
715        return lorder;
716    }
717
718}