Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.application;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.Collections;
011import java.util.Comparator;
012import java.util.List;
013import java.util.SortedSet;
014import java.util.TreeSet;
015
016import org.apache.logging.log4j.LogManager;
017import org.apache.logging.log4j.Logger;
018
019import edu.jas.gb.WordGroebnerBaseAbstract;
020import edu.jas.gb.WordGroebnerBaseSeq;
021import edu.jas.gb.WordReduction;
022import edu.jas.gb.WordReductionSeq;
023import edu.jas.gbufd.PolyGBUtil;
024import edu.jas.kern.Scripting;
025import edu.jas.poly.GenWordPolynomial;
026import edu.jas.poly.GenWordPolynomialRing;
027import edu.jas.poly.PolyUtil;
028import edu.jas.poly.Word;
029import edu.jas.structure.GcdRingElem;
030import edu.jas.structure.NotInvertibleException;
031
032
033/**
034 * Word Ideal implements some methods for ideal arithmetic, for example
035 * containment, sum or product. <b>Note:</b> only two-sided ideals.
036 * @author Heinz Kredel
037 */
038public class WordIdeal<C extends GcdRingElem<C>> implements Comparable<WordIdeal<C>>, Serializable {
039
040
041    private static final Logger logger = LogManager.getLogger(WordIdeal.class);
042
043
044    private static final boolean debug = logger.isDebugEnabled();
045
046
047    /**
048     * The data structure is a list of word polynomials.
049     */
050    protected List<GenWordPolynomial<C>> list;
051
052
053    /**
054     * Reference to the word polynomial ring.
055     */
056    protected GenWordPolynomialRing<C> ring;
057
058
059    /**
060     * Indicator if list is a Groebner Base.
061     */
062    protected boolean isGB;
063
064
065    /**
066     * Indicator if test has been performed if this is a Groebner Base.
067     */
068    protected boolean testGB;
069
070
071    /**
072     * Groebner base engine.
073     */
074    protected final WordGroebnerBaseAbstract<C> bb;
075
076
077    /**
078     * Reduction engine.
079     */
080    protected final WordReduction<C> red;
081
082
083    /**
084     * Constructor.
085     * @param ring word polynomial ring
086     */
087    public WordIdeal(GenWordPolynomialRing<C> ring) {
088        this(ring, new ArrayList<GenWordPolynomial<C>>());
089    }
090
091
092    /**
093     * Constructor.
094     * @param ring word polynomial ring
095     * @param list word polynomial list
096     */
097    public WordIdeal(GenWordPolynomialRing<C> ring, List<GenWordPolynomial<C>> list) {
098        this(ring, list, false);
099    }
100
101
102    /**
103     * Constructor.
104     * @param ring word polynomial ring
105     * @param list word polynomial list
106     * @param bb Groebner Base engine
107     * @param red Reduction engine
108     */
109    public WordIdeal(GenWordPolynomialRing<C> ring, List<GenWordPolynomial<C>> list,
110                    WordGroebnerBaseAbstract<C> bb, WordReduction<C> red) {
111        this(ring, list, false, bb, red);
112    }
113
114
115    /**
116     * Constructor.
117     * @param ring word polynomial ring
118     * @param list word polynomial list
119     * @param gb true if list is known to be a Groebner Base, else false
120     */
121    public WordIdeal(GenWordPolynomialRing<C> ring, List<GenWordPolynomial<C>> list, boolean gb) {
122        this(ring, list, gb, new WordGroebnerBaseSeq<C>(), new WordReductionSeq<C>());
123        //this(list, gb, topt, GBFactory.getImplementation(list.ring.coFac));
124    }
125
126
127    /**
128     * Constructor.
129     * @param ring word polynomial ring
130     * @param list word polynomial list
131     * @param gb true if list is known to be a Groebner Base, else false
132     * @param bb Groebner Base engine
133     */
134    public WordIdeal(GenWordPolynomialRing<C> ring, List<GenWordPolynomial<C>> list, boolean gb,
135                    WordGroebnerBaseAbstract<C> bb) {
136        this(ring, list, gb, bb, bb.red);
137    }
138
139
140    /**
141     * Constructor.
142     * @param ring word polynomial ring
143     * @param list word polynomial list
144     * @param gb true if list is known to be a Groebner Base, else false
145     * @param bb Groebner Base engine
146     * @param red Reduction engine
147     */
148    public WordIdeal(GenWordPolynomialRing<C> ring, List<GenWordPolynomial<C>> list, boolean gb,
149                    WordGroebnerBaseAbstract<C> bb, WordReduction<C> red) {
150        if (ring == null) {
151            throw new IllegalArgumentException("ring may not be null");
152        }
153        if (list == null) {
154            throw new IllegalArgumentException("list may not be null");
155        }
156        this.ring = ring;
157        this.list = list;
158        this.isGB = gb;
159        this.testGB = (gb ? true : false); // ??
160        this.bb = bb;
161        this.red = red;
162        if (debug) {
163            logger.info("constructed: {}", this);
164        }
165    }
166
167
168    /**
169     * Clone this.
170     * @return a copy of this.
171     */
172    public WordIdeal<C> copy() {
173        return new WordIdeal<C>(ring, new ArrayList<GenWordPolynomial<C>>(list), isGB, bb, red);
174    }
175
176
177    /**
178     * Get the List of GenWordPolynomials.
179     * @return (cast) list.list
180     */
181    public List<GenWordPolynomial<C>> getList() {
182        return list;
183    }
184
185
186    /**
187     * Get the GenWordPolynomialRing.
188     * @return (cast) list.ring
189     */
190    public GenWordPolynomialRing<C> getRing() {
191        return ring;
192    }
193
194
195    /**
196     * Get the zero ideal.
197     * @return ideal(0)
198     */
199    public WordIdeal<C> getZERO() {
200        List<GenWordPolynomial<C>> z = new ArrayList<GenWordPolynomial<C>>(0);
201        return new WordIdeal<C>(ring, z, true, bb, red);
202    }
203
204
205    /**
206     * Get the one ideal.
207     * @return ideal(1)
208     */
209    public WordIdeal<C> getONE() {
210        List<GenWordPolynomial<C>> one = new ArrayList<GenWordPolynomial<C>>(1);
211        one.add(getRing().getONE());
212        return new WordIdeal<C>(ring, one, true, bb, red);
213    }
214
215
216    /**
217     * String representation of the word ideal.
218     * @see java.lang.Object#toString()
219     */
220    @Override
221    public String toString() {
222        StringBuffer sb = new StringBuffer("(");
223        boolean first = true;
224        for (GenWordPolynomial<C> p : list) {
225            if (!first) {
226                sb.append(",");
227            } else {
228                first = false;
229            }
230            sb.append(p.toString());
231        }
232        sb.append(")");
233        return sb.toString();
234    }
235
236
237    /**
238     * Get a scripting compatible string representation.
239     * @return script compatible representation for this Element.
240     * @see edu.jas.structure.Element#toScript()
241     */
242    public String toScript() {
243        StringBuffer s = new StringBuffer();
244        switch (Scripting.getLang()) {
245        case Ruby:
246            s.append("WordPolyIdeal.new(");
247            break;
248        case Python:
249        default:
250            s.append("WordIdeal(");
251        }
252        if (ring != null) {
253            s.append(ring.toScript());
254        }
255        if (list == null) {
256            s.append(")");
257            return s.toString();
258        }
259        switch (Scripting.getLang()) {
260        case Ruby:
261            s.append(",\"\",[");
262            break;
263        case Python:
264        default:
265            s.append(",list=[");
266        }
267        boolean first = true;
268        String sa = null;
269        for (GenWordPolynomial<C> oa : list) {
270            sa = oa.toScript();
271            if (first) {
272                first = false;
273            } else {
274                s.append(", ");
275            }
276            //s.append("( " + sa + " )");
277            s.append(sa);
278        }
279        s.append("])");
280        return s.toString();
281    }
282
283
284    /**
285     * Comparison with any other object. <b>Note:</b> If not both ideals are
286     * Groebner Bases, then false may be returned even the ideals are equal.
287     * @see java.lang.Object#equals(java.lang.Object)
288     */
289    @Override
290    @SuppressWarnings("unchecked")
291    public boolean equals(Object b) {
292        if (!(b instanceof WordIdeal)) {
293            logger.warn("equals no Ideal");
294            return false;
295        }
296        WordIdeal<C> B = null;
297        try {
298            B = (WordIdeal<C>) b;
299        } catch (ClassCastException ignored) {
300            return false;
301        }
302        SortedSet<GenWordPolynomial<C>> s = new TreeSet<GenWordPolynomial<C>>(list);
303        SortedSet<GenWordPolynomial<C>> t = new TreeSet<GenWordPolynomial<C>>(B.list);
304        if (isGB && B.isGB) { //requires also monic polys
305            return s.equals(t);
306        }
307        if (s.equals(t)) {
308            return true;
309        }
310        //System.out.println("no GBs contains");
311        return this.contains(B) && B.contains(this);
312    }
313
314
315    /**
316     * WordIdeal comparison.
317     * @param L other word ideal.
318     * @return compareTo() of polynomial lists.
319     */
320    public int compareTo(WordIdeal<C> L) {
321        int si = Math.min(L.list.size(), list.size());
322        int s = 0;
323        final Comparator<Word> wc = ring.alphabet.getAscendComparator();
324        Comparator<GenWordPolynomial<C>> cmp = new Comparator<GenWordPolynomial<C>>() {
325
326
327            public int compare(GenWordPolynomial<C> p1, GenWordPolynomial<C> p2) {
328                Word w1 = p1.leadingWord();
329                Word w2 = p2.leadingWord();
330                if (w1 == null) {
331                    return -1; // dont care
332                }
333                if (w2 == null) {
334                    return 1; // dont care
335                }
336                if (w1.length() != w2.length()) {
337                    if (w1.length() > w2.length()) {
338                        return 1; // dont care
339                    }
340                    return -1; // dont care
341                }
342                return wc.compare(w1, w2);
343            }
344        };
345
346        List<GenWordPolynomial<C>> l1 = new ArrayList<GenWordPolynomial<C>>(list);
347        List<GenWordPolynomial<C>> l2 = new ArrayList<GenWordPolynomial<C>>(L.list);
348        //Collections.sort(l1);
349        //Collections.sort(l2);
350        Collections.sort(l1, cmp);
351        Collections.sort(l2, cmp);
352        for (int i = 0; i < si; i++) {
353            GenWordPolynomial<C> a = l1.get(i);
354            GenWordPolynomial<C> b = l2.get(i);
355            s = a.compareTo(b);
356            if (s != 0) {
357                return s;
358            }
359        }
360        if (list.size() > si) {
361            return 1;
362        }
363        if (L.list.size() > si) {
364            return -1;
365        }
366        return s;
367    }
368
369
370    /**
371     * Hash code for this word ideal.
372     * @see java.lang.Object#hashCode()
373     */
374    @Override
375    public int hashCode() {
376        int h;
377        h = list.hashCode();
378        if (isGB) {
379            h = h << 1;
380        }
381        if (testGB) {
382            h += 1;
383        }
384        return h;
385    }
386
387
388    /**
389     * Test if ZERO ideal.
390     * @return true, if this is the 0 ideal, else false
391     */
392    public boolean isZERO() {
393        //return list.isZERO();
394        if (list == null) { // never true
395            return true;
396        }
397        for (GenWordPolynomial<C> p : list) {
398            if (p == null) {
399                continue;
400            }
401            if (!p.isZERO()) {
402                return false;
403            }
404        }
405        return true;
406    }
407
408
409    /**
410     * Test if ONE is contained in the ideal. To test for a proper ideal use
411     * <code>! id.isONE()</code>.
412     * @return true, if this is the 1 ideal, else false
413     */
414    public boolean isONE() {
415        //return list.isONE();
416        if (list == null) {
417            return false;
418        }
419        for (GenWordPolynomial<C> p : list) {
420            if (p == null) {
421                continue;
422            }
423            if (p.isONE()) {
424                return true;
425            }
426        }
427        return false;
428    }
429
430
431    /**
432     * Test if this is a twosided Groebner base.
433     * @return true, if this is a twosided Groebner base, else false
434     */
435    public boolean isGB() {
436        if (testGB) {
437            return isGB;
438        }
439        logger.warn("isGB computing");
440        isGB = bb.isGB(getList());
441        testGB = true;
442        return isGB;
443    }
444
445
446    /**
447     * Do Groebner Base. Compute the Groebner Base for this ideal.
448     */
449    @SuppressWarnings("unchecked")
450    public void doGB() {
451        if (isGB && testGB) {
452            return;
453        }
454        List<GenWordPolynomial<C>> G = getList();
455        logger.info("doGB computing = {}", G);
456        list = bb.GB(G);
457        isGB = true;
458        testGB = true;
459        return;
460    }
461
462
463    /**
464     * Groebner Base. Get a Groebner Base for this ideal.
465     * @return twosidedGB(this)
466     */
467    public WordIdeal<C> GB() {
468        if (isGB) {
469            return this;
470        }
471        doGB();
472        return this;
473    }
474
475
476    /**
477     * Word ideal containment. Test if B is contained in this ideal. Note: this
478     * is eventually modified to become a Groebner Base.
479     * @param B word ideal
480     * @return true, if B is contained in this, else false
481     */
482    public boolean contains(WordIdeal<C> B) {
483        if (B == null || B.isZERO()) {
484            return true;
485        }
486        return contains(B.getList());
487    }
488
489
490    /**
491     * Word ideal containment. Test if b is contained in this ideal. Note: this
492     * is eventually modified to become a Groebner Base.
493     * @param b word polynomial
494     * @return true, if b is contained in this, else false
495     */
496    public boolean contains(GenWordPolynomial<C> b) {
497        if (b == null || b.isZERO()) {
498            return true;
499        }
500        if (this.isONE()) {
501            return true;
502        }
503        if (this.isZERO()) {
504            return false;
505        }
506        if (!isGB) {
507            doGB();
508        }
509        GenWordPolynomial<C> z = red.normalform(getList(), b);
510        if (z == null || z.isZERO()) {
511            return true;
512        }
513        return false;
514    }
515
516
517    /**
518     * Word ideal containment. Test if each b in B is contained in this ideal.
519     * Note: this is eventually modified to become a Groebner Base.
520     * @param B list of word polynomials
521     * @return true, if each b in B is contained in this, else false
522     */
523    public boolean contains(List<GenWordPolynomial<C>> B) {
524        if (B == null || B.size() == 0) {
525            return true;
526        }
527        if (this.isONE()) {
528            return true;
529        }
530        if (!isGB) {
531            doGB();
532        }
533        for (GenWordPolynomial<C> b : B) {
534            if (b == null) {
535                continue;
536            }
537            if (!contains(b)) {
538                System.out.println("contains nf(b) != 0: " + b);
539                return false;
540            }
541        }
542        return true;
543    }
544
545
546    /**
547     * Word ideal summation. Generators for the sum of ideals. Note: if both
548     * ideals are Groebner bases, a Groebner base is returned.
549     * @param B word ideal
550     * @return ideal(this+B)
551     */
552    public WordIdeal<C> sum(WordIdeal<C> B) {
553        if (B == null || B.isZERO()) {
554            return this;
555        }
556        if (this.isZERO()) {
557            return B;
558        }
559        return sum(B.getList());
560        // int s = getList().size() + B.getList().size();
561        // List<GenWordPolynomial<C>> c;
562        // c = new ArrayList<GenWordPolynomial<C>>(s);
563        // c.addAll(getList());
564        // c.addAll(B.getList());
565        // WordIdeal<C> I = new WordIdeal<C>(getRing(), c, false, bb);
566        // if (isGB && B.isGB) {
567        //     I.doGB();
568        // }
569        // return I;
570    }
571
572
573    /**
574     * Word summation. Generators for the sum of ideal and a polynomial. Note:
575     * if this ideal is a Groebner base, a Groebner base is returned.
576     * @param b word polynomial
577     * @return ideal(this+{b})
578     */
579    public WordIdeal<C> sum(GenWordPolynomial<C> b) {
580        if (b == null || b.isZERO()) {
581            return this;
582        }
583        int s = getList().size() + 1;
584        List<GenWordPolynomial<C>> c;
585        c = new ArrayList<GenWordPolynomial<C>>(s);
586        c.addAll(getList());
587        c.add(b);
588        WordIdeal<C> I = new WordIdeal<C>(getRing(), c, false, bb);
589        if (isGB) {
590            I.doGB();
591        }
592        return I;
593    }
594
595
596    /**
597     * Word summation. Generators for the sum of this ideal and a list of
598     * polynomials. Note: if this ideal is a Groebner base, a Groebner base is
599     * returned.
600     * @param L list of word polynomials
601     * @return ideal(this+L)
602     */
603    public WordIdeal<C> sum(List<GenWordPolynomial<C>> L) {
604        if (L == null || L.isEmpty()) {
605            return this;
606        }
607        int s = getList().size() + L.size();
608        List<GenWordPolynomial<C>> c = new ArrayList<GenWordPolynomial<C>>(s);
609        c.addAll(getList());
610        c.addAll(L);
611        WordIdeal<C> I = new WordIdeal<C>(getRing(), c, false, bb);
612        if (isGB) {
613            I.doGB();
614        }
615        return I;
616    }
617
618
619    /**
620     * Product. Generators for the product of ideals. Note: if both ideals are
621     * Groebner bases, a Groebner base is returned.
622     * @param B word ideal
623     * @return ideal(this*B)
624     */
625    public WordIdeal<C> product(WordIdeal<C> B) {
626        if (B == null || B.isZERO()) {
627            return B;
628        }
629        if (this.isZERO()) {
630            return this;
631        }
632        int s = getList().size() * B.getList().size();
633        List<GenWordPolynomial<C>> c;
634        c = new ArrayList<GenWordPolynomial<C>>(s);
635        for (GenWordPolynomial<C> p : getList()) {
636            for (GenWordPolynomial<C> q : B.getList()) {
637                q = p.multiply(q);
638                c.add(q);
639            }
640        }
641        WordIdeal<C> I = new WordIdeal<C>(getRing(), c, false, bb);
642        if (isGB && B.isGB) {
643            I.doGB();
644        }
645        return I;
646    }
647
648
649    /**
650     * Left product. Generators for the product this by a polynomial.
651     * @param b word polynomial
652     * @return ideal(this*b)
653     */
654    public WordIdeal<C> product(GenWordPolynomial<C> b) {
655        if (b == null || b.isZERO()) {
656            return getZERO();
657        }
658        if (this.isZERO()) {
659            return this;
660        }
661        List<GenWordPolynomial<C>> c;
662        c = new ArrayList<GenWordPolynomial<C>>(getList().size());
663        for (GenWordPolynomial<C> p : getList()) {
664            GenWordPolynomial<C> q = p.multiply(b);
665            c.add(q);
666        }
667        WordIdeal<C> I = new WordIdeal<C>(getRing(), c, false, bb);
668        if (isGB) {
669            I.doGB();
670        }
671        return I;
672    }
673
674
675    /*
676     * Intersection. Generators for the intersection of ideals. Using an
677     * iterative algorithm.
678     * @param Bl list of word ideals
679     * @return ideal(cap_i B_i), a Groebner base
680     */
681    public WordIdeal<C> intersect(List<WordIdeal<C>> Bl) {
682        if (Bl == null || Bl.size() == 0) {
683            return getZERO();
684        }
685        WordIdeal<C> I = null;
686        for (WordIdeal<C> B : Bl) {
687            if (I == null) {
688                I = B;
689                continue;
690            }
691            if (I.isONE()) {
692                return I;
693            }
694            I = I.intersect(B);
695        }
696        return I;
697    }
698
699
700    /*
701     * Intersection. Generators for the intersection of ideals.
702     * @param B word ideal
703     * @return ideal(this cap B), a Groebner base
704     */
705    public WordIdeal<C> intersect(WordIdeal<C> B) {
706        if (B == null || B.isZERO()) { // (0)
707            return B;
708        }
709        if (this.isZERO()) {
710            return this;
711        }
712        List<GenWordPolynomial<C>> c = PolyGBUtil.<C> intersect(getRing(), getList(), B.getList(), bb);
713        WordIdeal<C> I = new WordIdeal<C>(getRing(), c, true, bb);
714        return I;
715    }
716
717
718    /*
719     * Intersection. Generators for the intersection of a ideal with a
720     * word polynomial ring. The polynomial ring of this ideal must be
721     * a contraction of R and the TermOrder must be an elimination
722     * order.
723     * @param R word polynomial ring
724     * @return ideal(this cap R)
725     */
726    public WordIdeal<C> intersect(GenWordPolynomialRing<C> R) {
727        if (R == null) {
728            throw new IllegalArgumentException("R may not be null");
729        }
730        List<GenWordPolynomial<C>> H = PolyUtil.<C> intersect(R, getList());
731        return new WordIdeal<C>(R, H, isGB, bb);
732    }
733
734
735    /*
736     * Eliminate. Generators for the intersection of this ideal with a word
737     * polynomial ring. The word polynomial ring of this ideal must be a
738     * contraction of R and the TermOrder must be an elimination order.
739     * @param R word polynomial ring
740     * @return ideal(this cap R)
741     */
742    public WordIdeal<C> eliminate(GenWordPolynomialRing<C> R) {
743        if (R == null) {
744            throw new IllegalArgumentException("R may not be null");
745        }
746        if (getRing().equals(R)) {
747            return this;
748        }
749        return intersect(R);
750    }
751
752
753    /*
754     * Quotient. Generators for the word ideal quotient.
755     * @param h word polynomial
756     * @return ideal(this : h), a Groebner base
757    public WordIdeal<C> quotient(GenWordPolynomial<C> h) {
758        if (h == null) { // == (0)
759            return this;
760        }
761        if (h.isZERO()) {
762            return this;
763        }
764        if (this.isZERO()) {
765            return this;
766        }
767        List<GenWordPolynomial<C>> H;
768        H = new ArrayList<GenWordPolynomial<C>>(1);
769        H.add(h);
770        WordIdeal<C> Hi = new WordIdeal<C>(getRing(), H, true, bb);
771        WordIdeal<C> I = this.intersect(Hi);
772        List<GenWordPolynomial<C>> Q;
773        Q = new ArrayList<GenWordPolynomial<C>>(I.getList().size());
774        for (GenWordPolynomial<C> q : I.getList()) {
775            q = (GenWordPolynomial<C>) q.divide(h); // remainder == 0
776            Q.add(q);
777        }
778        return new WordIdeal<C>(getRing(), Q, true, bb);
779    }
780     */
781
782
783    /*
784     * Quotient. Generators for the word ideal quotient.
785     * @param H word ideal
786     * @return ideal(this : H), a Groebner base
787    public WordIdeal<C> quotient(WordIdeal<C> H) {
788        if (H == null || H.isZERO()) { // == (0)
789            return this;
790        }
791        if (this.isZERO()) {
792            return this;
793        }
794        WordIdeal<C> Q = null;
795        for (GenWordPolynomial<C> h : H.getList()) {
796            WordIdeal<C> Hi = this.quotient(h);
797            if (Q == null) {
798                Q = Hi;
799            } else {
800                Q = Q.intersect(Hi);
801            }
802        }
803        return Q;
804    }
805     */
806
807
808    /**
809     * Power. Generators for the power of this word ideal. Note: if this ideal
810     * is a Groebner base, a Groebner base is returned.
811     * @param d integer
812     * @return ideal(this^d)
813     */
814    public WordIdeal<C> power(int d) {
815        if (d <= 0) {
816            return getONE();
817        }
818        if (this.isZERO() || this.isONE()) {
819            return this;
820        }
821        WordIdeal<C> c = this;
822        for (int i = 1; i < d; i++) {
823            c = c.product(this);
824        }
825        return c;
826    }
827
828
829    /**
830     * Normalform for element.
831     * @param h word polynomial
832     * @return left normalform of h with respect to this
833     */
834    public GenWordPolynomial<C> normalform(GenWordPolynomial<C> h) {
835        if (h == null) {
836            return h;
837        }
838        if (h.isZERO()) {
839            return h;
840        }
841        if (this.isZERO()) {
842            return h;
843        }
844        GenWordPolynomial<C> r;
845        r = red.normalform(getList(), h);
846        return r;
847    }
848
849
850    /**
851     * Normalform for list of word elements.
852     * @param L word polynomial list
853     * @return list of left normalforms of the elements of L with respect to
854     *         this
855     */
856    public List<GenWordPolynomial<C>> normalform(List<GenWordPolynomial<C>> L) {
857        if (L == null) {
858            return L;
859        }
860        if (L.size() == 0) {
861            return L;
862        }
863        if (this.isZERO()) {
864            return L;
865        }
866        List<GenWordPolynomial<C>> M = new ArrayList<GenWordPolynomial<C>>(L.size());
867        for (GenWordPolynomial<C> h : L) {
868            GenWordPolynomial<C> r = normalform(h);
869            if (r != null && !r.isZERO()) {
870                M.add(r);
871            }
872        }
873        return M;
874    }
875
876
877    /**
878     * Inverse for element modulo this ideal.
879     * @param h word polynomial
880     * @return inverse of h with respect to this, if defined
881     */
882    public GenWordPolynomial<C> inverse(GenWordPolynomial<C> h) {
883        if (h == null || h.isZERO()) {
884            throw new NotInvertibleException("zero not invertible");
885        }
886        if (this.isZERO()) {
887            throw new NotInvertibleException("zero ideal");
888        }
889        if (h.isUnit()) {
890            return h.inverse();
891        }
892        if (isUnit(h)) {
893            logger.warn("{} is invertable, but inverse not computed", h);
894        }
895        throw new UnsupportedOperationException("inverse of " + h);
896        /* TODO compute inverse
897        doGB();
898        List<GenWordPolynomial<C>> F = new ArrayList<GenWordPolynomial<C>>(1 + list.list.size());
899        F.add(h);
900        F.addAll(getList());
901        //System.out.println("F = " + F);
902        WordExtendedGB<C> x = bb.extLeftGB(F);
903        List<GenWordPolynomial<C>> G = x.G;
904        //System.out.println("G = " + G);
905        GenWordPolynomial<C> one = null;
906        int i = -1;
907        for (GenWordPolynomial<C> p : G) {
908            i++;
909            if (p == null) {
910                continue;
911            }
912            if (p.isUnit()) {
913                one = p;
914                break;
915            }
916        }
917        if (one == null) {
918            throw new NotInvertibleException("one == null: h = " + h);
919        }
920        List<GenWordPolynomial<C>> row = x.G2F.get(i); // != -1
921        //System.out.println("row = " + row);
922        GenWordPolynomial<C> g = row.get(0);
923        if (g == null || g.isZERO()) {
924            throw new NotInvertibleException("g == 0: h = " + h);
925        }
926        GenWordPolynomial<C> gp = red.leftNormalform(getList(), g);
927        if (gp.isZERO()) { // can happen with solvable rings
928            throw new NotInvertibleException("solv|gp == 0: h = " + h + ", g = " + g);
929        }
930        // adjust leading coefficient of g to get g*h == 1
931        GenWordPolynomial<C> f = g.multiply(h);
932        //System.out.println("f = " + f);
933        GenWordPolynomial<C> k = red.leftNormalform(getList(), f);
934        //System.out.println("k = " + k);
935        if (!k.isONE()) {
936            C lbc = k.leadingBaseCoefficient();
937            lbc = lbc.inverse();
938            g = g.multiply(lbc);
939        }
940        return g;
941        */
942    }
943
944
945    /**
946     * Test if element is a unit modulo this ideal.
947     * @param h word polynomial
948     * @return true if h is a unit with respect to this, else false
949     */
950    public boolean isUnit(GenWordPolynomial<C> h) {
951        if (h == null || h.isZERO()) {
952            return false;
953        }
954        if (this.isZERO()) {
955            return false;
956        }
957        if (h.isUnit()) {
958            return true;
959        }
960        // test this + (h) == 1: then ex p, q: pp*this**qq + p*h*q = 1
961        List<GenWordPolynomial<C>> F = new ArrayList<GenWordPolynomial<C>>(1 + list.size());
962        F.add(h);
963        F.addAll(getList());
964        List<GenWordPolynomial<C>> G = bb.GB(F);
965        if (debug) {
966            logger.info("isUnit GB = {}", G);
967        }
968        for (GenWordPolynomial<C> p : G) {
969            if (p == null) {
970                continue;
971            }
972            if (p.isUnit()) {
973                return true;
974            }
975        }
976        return false;
977    }
978
979
980    /**
981     * Ideal common zero test.
982     * @return -1, 0 or 1 if dimension(this) &eq; -1, 0 or &ge; 1.
983     */
984    public int commonZeroTest() {
985        if (this.isZERO()) {
986            return 1;
987        }
988        if (!isGB) {
989            doGB();
990        }
991        if (this.isONE()) {
992            return -1;
993        }
994        return bb.commonZeroTest(getList());
995    }
996
997
998    /**
999     * Test if this ideal is maximal.
1000     * @return true, if this is certainly maximal and not one, 
1001     *         false, if this is one, has dimension &ge; 1 or it is not jet determined if it is maximal.
1002     */
1003    public boolean isMaximal() {
1004        if (commonZeroTest() != 0) {
1005            return false;
1006        }
1007        for (Long d : univariateDegrees()) {
1008            if (d > 1L) {
1009                return false;
1010            }
1011        }
1012        return true;
1013    }
1014
1015
1016    /**
1017     * Univariate head term degrees.
1018     * @return a list of the degrees of univariate head terms.
1019     */
1020    public List<Long> univariateDegrees() {
1021        List<Long> ud = new ArrayList<Long>();
1022        if (this.isZERO()) {
1023            return ud;
1024        }
1025        if (!isGB) {
1026            doGB();
1027        }
1028        if (this.isONE()) {
1029            return ud;
1030        }
1031        return bb.univariateDegrees(getList());
1032    }
1033
1034
1035    /*
1036     * Construct univariate polynomials of minimal degree in all variables in
1037     * zero dimensional ideal(G).
1038     * @return list of univariate word polynomial of minimal degree in each
1039     *         variable in ideal(G)
1040     */
1041
1042
1043    /*
1044     * Construct univariate polynomial of minimal degree in variable i in zero
1045     * dimensional ideal(G).
1046     * @param i variable index.
1047     * @return univariate word polynomial of minimal degree in variable i in
1048     *         ideal(G)
1049     */
1050
1051}