001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.util.Arrays;
009
010import edu.jas.arith.BigInteger;
011import edu.jas.structure.MonoidElem;
012import edu.jas.structure.MonoidFactory;
013
014
015/**
016 * IndexList implements index lists for exterior polynomials. Index lists are
017 * implemented as arrays of Java int type. Objects of this class are intended to
018 * be immutable, except for the sign. If in doubt use <code>valueOf</code> to
019 * get a conformant index list.
020 * @see "masnc.DIPE.mi#ILEXPR from SAC2/MAS"
021 * @author Heinz Kredel
022 */
023
024public class IndexList implements MonoidElem<IndexList> {
025
026
027    /**
028     * Representation of index list as int arrays.
029     */
030    public final int[] val; // != null, when s != 0
031
032
033    /**
034     * Sign of index list.
035     */
036    public int sign; // = -1, 0, 1
037
038
039    /**
040     * Reference to IndexFactory.
041     */
042    public final IndexFactory mono;
043
044
045    /**
046     * Constructor for IndexList. No argument constructor defining 0 index list.
047     */
048    public IndexList(IndexFactory m) {
049        this(m, 0, null);
050    }
051
052
053    /**
054     * Constructor for IndexList.
055     * @param v array with indices.
056     */
057    public IndexList(IndexFactory m, int[] v) {
058        this(m, 1, v);
059    }
060
061
062    /**
063     * Constructor for IndexList. <b>Note:</b> A copy of v is internally
064     * created.
065     * @param s sign of index list.
066     * @param v array with indices.
067     */
068    public IndexList(IndexFactory m, int s, int[] v) {
069        sign = s;
070        mono = m;
071        if (v == null) {
072            if (s != 0) {
073                throw new IllegalArgumentException("inconsistent: s = " + s + ", v = " + v);
074            }
075            val = v;
076            sign = 0; // only when exception deactivated
077        } else {
078            val = Arrays.copyOf(v, v.length);
079        }
080        //if (v != null && v.length > 0) System.out.println("v[0]: " + v[0]);
081    }
082
083
084    /**
085     * Constructor for IndexList. Converts a String representation to an
086     * IndexList. Accepted format = E(1,2,3,4,5,6,7).
087     * @param s String representation.
088     */
089    public IndexList(IndexFactory m, String s) throws NumberFormatException {
090        this(m, m.parse(s).val);
091    }
092
093
094    /**
095     * Get the corresponding element factory.
096     * @return factory for this Element.
097     * @see edu.jas.structure.Element#factory()
098     */
099    public MonoidFactory<IndexList> factory() {
100        return mono; //(MonoidFactory<IndexList>) this;
101        //throw new UnsupportedOperationException("no factory implemented for IndexList");
102    }
103
104
105    /**
106     * Check for IndexList conformant specification.
107     * @return true if this a a conformant IndexList, else false.
108     */
109    public boolean isConformant() {
110        if (sign == 0 && val == null) {
111            return true;
112        }
113        IndexList ck = mono.valueOf(val);
114        return this.abs().equals(ck.abs());
115    }
116
117
118    /**
119     * Clone this.
120     * @see java.lang.Object#clone()
121     */
122    @Override
123    public IndexList copy() {
124        return new IndexList(mono, sign, val);
125    }
126
127
128    /**
129     * Get the index vector.
130     * @return val.
131     */
132    public int[] getVal() {
133        return val;
134    }
135
136
137    /**
138     * Get the index at position i.
139     * @param i position.
140     * @return val[i].
141     */
142    public int getVal(int i) {
143        return val[i];
144    }
145
146
147    /**
148     * Set the index at position i to e.
149     * @param i position
150     * @param e new index
151     * @return old val[i].
152     */
153    protected int setVal(int i, int e) {
154        int v = val[i];
155        val[i] = e;
156        return v;
157    }
158
159
160    /**
161     * Get the length of this index list.
162     * @return val.length or -1 for 0 index list.
163     */
164    public int length() {
165        if (sign == 0) {
166            return -1;
167        }
168        return val.length;
169    }
170
171
172    /**
173     * Get the string representation.
174     * @see java.lang.Object#toString()
175     */
176    @Override
177    public String toString() {
178        //System.out.println("(" + sign + ", " + Arrays.toString(val) + ")");
179        if (sign == 0) {
180            return "0";
181        }
182        StringBuffer s = new StringBuffer();
183        if (sign > 0) {
184            s.append(mono.vname + "(");
185        } else {
186            s.append(mono.vname + "[-1](");
187        }
188        for (int i = 0; i < length(); i++) {
189            s.append(getVal(i));
190            if (i < length() - 1) {
191                s.append(",");
192            }
193        }
194        s.append(")");
195        return s.toString();
196    }
197
198
199    /**
200     * Get a scripting compatible string representation.
201     * @return script compatible representation for this Element.
202     * @see edu.jas.structure.Element#toScript()
203     */
204    @Override
205    public String toScript() {
206        return toString();
207    }
208
209
210    /**
211     * Get a scripting compatible string representation of the factory.
212     * @return script compatible representation for this ElemFactory.
213     * @see edu.jas.structure.Element#toScriptFactory()
214     */
215    @Override
216    public String toScriptFactory() {
217        // Python case
218        return "IndexFactory()";
219    }
220
221
222    /**
223     * Comparison with any other object.
224     * @see java.lang.Object#equals(java.lang.Object)
225     */
226    @Override
227    public boolean equals(Object B) {
228        if (!(B instanceof IndexList)) {
229            return false;
230        }
231        IndexList b = (IndexList) B;
232        int t = this.compareTo(b);
233        //System.out.println("equals: this = " + this + " B = " + B + " t = " + t);
234        return (0 == t);
235    }
236
237
238    /**
239     * hashCode. Optimized for small indexes, i.e. &le; 2<sup>4</sup> and small
240     * number of variables, i.e. &le; 8.
241     * @see java.lang.Object#hashCode()
242     */
243    @Override
244    public int hashCode() {
245        int hash = Arrays.hashCode(val) + sign;
246        return hash;
247    }
248
249
250    /**
251     * Returns the number of bits in the representation of this index vector.
252     * @return number of bits in the representation of this IndexList, including
253     *         sign bits.
254     */
255    public long bitLength() {
256        long blen = 2; // sign
257        for (int i = 0; i < val.length; i++) {
258            blen += BigInteger.bitLength(val[i]);
259        }
260        return blen;
261    }
262
263
264    /**
265     * Is IndexList zero.
266     * @return If this sign is 0 then true is returned, else false.
267     */
268    public boolean isZERO() {
269        return (sign == 0);
270    }
271
272
273    /**
274     * Is IndexList one.
275     * @return If this sign != 0 and length val is zero then true returned, else
276     *         false.
277     */
278    public boolean isONE() {
279        return (sign != 0 && val.length == 0);
280    }
281
282
283    /**
284     * Is IndexList a unit.
285     * @return If this is a unit then true is returned, else false.
286     */
287    public boolean isUnit() {
288        return isONE() || negate().isONE();
289    }
290
291
292    /**
293     * IndexList absolute value.
294     * @return abs(this).
295     */
296    public IndexList abs() {
297        if (sign >= 0) {
298            return this;
299        }
300        return new IndexList(mono, 1, val);
301    }
302
303
304    /**
305     * IndexList negate.
306     * @return -this.
307     */
308    public IndexList negate() {
309        if (sign == 0) {
310            return this;
311        }
312        return new IndexList(mono, -sign, val);
313    }
314
315
316    /**
317     * IndexList exterior product. Also called wegde product.
318     * @param V other index list
319     * @return this /\ V.
320     */
321    public IndexList exteriorProduct(IndexList V) {
322        if (isZERO() || V.isZERO()) {
323            return mono.getZERO(); // = 0
324        }
325        int s = 1;
326        int m = 0, n = 0; // todo: remove or rename
327        int[] u = val;
328        int[] v = V.val;
329        int ii = 0;
330        int[] w = new int[u.length + v.length];
331        int i = 0, j = 0;
332        while (i < u.length && j < v.length) {
333            int ul = u[i];
334            int vl = v[j];
335            if (ul == vl) {
336                return mono.getZERO(); // = 0
337            }
338            if (ul < vl) {
339                w[ii++] = ul;
340                i++;
341                m++;
342            } else {
343                w[ii++] = vl;
344                j++;
345                n++;
346                if (m % 2 != 0) {
347                    s = -s;
348                }
349            }
350        }
351        if (i == u.length) {
352            while (j < v.length) {
353                w[ii++] = v[j++];
354            }
355        } else {
356            m += u.length - i; // - 1;
357            while (i < u.length) {
358                w[ii++] = u[i++];
359            }
360        }
361        if (m % 2 != 0 && n % 2 != 0) {
362            s = -s;
363        }
364        //System.out.println("i = " + i + ", j = " + j + ", m = " + m + ", n = " + n);
365        //System.out.println("s = " + s + ", w = " + Arrays.toString(w));
366        //int[] x = Arrays.copyOf(w, ii);
367        return new IndexList(mono, s, w);
368    }
369
370
371    /**
372     * IndexList multiply. <b>Note:</b> implemented by exteriorProduct.
373     * @param V other index list
374     * @return this * V.
375     */
376    public IndexList multiply(IndexList V) {
377        return exteriorProduct(V);
378    }
379
380
381    /**
382     * IndexList interior left product.
383     * @param V other index list
384     * @return this _| V.
385     */
386    public IndexList interiorLeftProduct(IndexList V) {
387        return V.interiorRightProduct(this);
388    }
389
390
391    /**
392     * IndexList interior right product.
393     * @param V other index list
394     * @return this |_ V.
395     */
396    public IndexList interiorRightProduct(IndexList V) {
397        if (!this.divides(V)) {
398            return mono.getZERO(); // = 0
399        }
400        int[] u = val;
401        int[] v = V.val;
402        int[] w = new int[v.length - u.length];
403        int ii = 0;
404        int s = 1;
405        int m = 0; // todo: remove or rename
406        for (int i = 0; i < v.length; i++) {
407            int vl = v[i];
408            boolean found = false;
409            for (int j = 0; j < u.length; j++) {
410                if (vl == u[j]) {
411                    found = true;
412                    break;
413                }
414            }
415            if (!found) {
416                w[ii++] = vl;
417                m++;
418            } else {
419                if (m % 2 != 0) {
420                    s = -s;
421                }
422            }
423        }
424        //int[] x = Arrays.copyOf(w, ii);
425        return new IndexList(mono, s, w);
426    }
427
428
429    /**
430     * IndexList divides test. Test if this is contained in V.
431     * @param V other index list
432     * @return true if this divides V, else false.
433     */
434    public boolean divides(IndexList V) {
435        if (isZERO() || V.isZERO()) {
436            return false;
437        }
438        if (val.length > V.val.length) {
439            return false;
440        }
441        int[] vval = V.val;
442        for (int i = 0; i < val.length; i++) {
443            int v = val[i];
444            boolean found = false;
445            for (int j = i; j < vval.length; j++) {
446                if (v == vval[j]) {
447                    found = true;
448                    break;
449                }
450            }
451            if (!found) {
452                return false;
453            }
454        }
455        return true;
456    }
457
458
459    /**
460     * IndexList inverse. <b>Note:</b> not implemented.
461     * @return 1 / this.
462     */
463    public IndexList inverse() {
464        throw new UnsupportedOperationException("inverse not implemented");
465    }
466
467
468    /**
469     * IndexList divide. <b>Note:</b> experimental.
470     * @param V other IndexList.
471     * @return this/V. <b>Note:</b> computed as interiorRightProduct, eventually
472     *         useful.
473     */
474    public IndexList divide(IndexList V) {
475        return interiorRightProduct(V);
476        //throw new UnsupportedOperationException("divide not implemented");
477    }
478
479
480    /**
481     * IndexList remainder. <b>Note:</b> not implemented.
482     * @param V other IndexList.
483     * @return this - (this/V). <b>Note:</b> not useful.
484     */
485    public IndexList remainder(IndexList V) {
486        throw new UnsupportedOperationException("remainder not implemented");
487    }
488
489
490    /**
491     * IndexList signum.
492     * @return sign;
493     */
494    public int signum() {
495        return sign;
496    }
497
498
499    /**
500     * IndexList degree.
501     * @return number of of all indexes.
502     */
503    public int degree() {
504        if (sign == 0) {
505            return -1;
506        }
507        return val.length;
508    }
509
510
511    /**
512     * IndexList maximal degree.
513     * @return maximal index.
514     */
515    public int maxDeg() {
516        if (degree() < 1) {
517            return -1;
518        }
519        return val[val.length - 1];
520    }
521
522
523    /**
524     * IndexList minimal degree.
525     * @return minimal index.
526     */
527    public int minDeg() {
528        if (degree() < 1) {
529            return -1;
530        }
531        return val[0];
532    }
533
534
535    /**
536     * IndexList compareTo.
537     * @param V other index list
538     * @return 0 if U == V, -1 if U &lt; V, 1 if U &gt; V.
539     */
540    @Override
541    public int compareTo(IndexList V) {
542        return strongCompareTo(V);
543    }
544
545
546    /**
547     * IndexList weakCompareTo. Ignoring the degree in first pass.
548     * @param V other index list
549     * @return 0 if U == V, -1 if U &lt; V, 1 if U &gt; V.
550     */
551    public int weakCompareTo(IndexList V) {
552        if (sign == 0 && V.sign == 0) {
553            return 0;
554        }
555        if (sign == 0) {
556            return -1;
557        }
558        if (V.sign == 0) {
559            return +1;
560        }
561        // both not zero
562        if (sign < V.sign) {
563            return -1;
564        }
565        if (sign > V.sign) {
566            return 1;
567        }
568        // both have same sign
569        int[] vval = V.val;
570        int m = Math.min(val.length, vval.length);
571        for (int i = 0; i < m; i++) {
572            if (val[i] < vval[i]) {
573                return -1;
574            }
575            if (val[i] > vval[i]) {
576                return 1;
577            }
578        }
579        if (val.length < vval.length) {
580            return -1;
581        }
582        if (val.length > vval.length) {
583            return 1;
584        }
585        return 0;
586    }
587
588
589    /**
590     * IndexList strongCompareTo. Sort by degree in first pass, then by indices.
591     * @param V other index list
592     * @return 0 if U == V, -1 if U &lt; V, 1 if U &gt; V.
593     */
594    public int strongCompareTo(IndexList V) {
595        if (sign == 0 && V.sign == 0) {
596            return 0;
597        }
598        if (sign == 0) {
599            return -1;
600        }
601        if (V.sign == 0) {
602            return +1;
603        }
604        // both not zero :: ignore sign
605        int[] vval = V.val;
606        if (val.length < vval.length) {
607            return -1;
608        }
609        if (val.length > vval.length) {
610            return 1;
611        }
612        int m = Math.min(val.length, vval.length);
613        int tl = 0;
614        for (int i = 0; i < m; i++) {
615            if (val[i] < vval[i]) {
616                tl = -1;
617                break;
618            }
619            if (val[i] > vval[i]) {
620                tl = 1;
621                break;
622            }
623        }
624        // now val.length == vval.length
625        return tl;
626    }
627
628}