001/*
002 * $Id$
003 */
004
005package edu.jas.gbufd;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.List;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenPolynomialRing;
017import edu.jas.structure.GcdRingElem;
018
019
020/**
021 * Multiplicative set of polynomials. a, b in M implies a*b in M, 1 in M.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 */
025public class MultiplicativeSet<C extends GcdRingElem<C>> implements Serializable {
026
027
028    private static final Logger logger = LogManager.getLogger(MultiplicativeSet.class);
029
030
031    //private static final boolean debug = logger.isDebugEnabled();
032
033
034    /**
035     * Data structure.
036     */
037    public final List<GenPolynomial<C>> mset;
038
039
040    /**
041     * Polynomial ring factory.
042     */
043    public final GenPolynomialRing<C> ring;
044
045
046    /**
047     * MultiplicativeSet constructor. Constructs an empty multiplicative set.
048     * @param ring polynomial ring factory for coefficients.
049     */
050    public MultiplicativeSet(GenPolynomialRing<C> ring) {
051        this(ring, new ArrayList<GenPolynomial<C>>());
052        if (ring == null) {
053            throw new IllegalArgumentException("only for non null rings");
054        }
055    }
056
057
058    /**
059     * MultiplicativeSet constructor.
060     * @param ring polynomial ring factory for coefficients.
061     * @param ms a list of non-zero polynomials.
062     */
063    protected MultiplicativeSet(GenPolynomialRing<C> ring, List<GenPolynomial<C>> ms) {
064        if (ms == null || ring == null) {
065            throw new IllegalArgumentException("only for non null parts");
066        }
067        this.ring = ring;
068        mset = ms;
069    }
070
071
072    /**
073     * toString.
074     * @see java.lang.Object#toString()
075     */
076    @Override
077    public String toString() {
078        return "MultiplicativeSet" + mset;
079    }
080
081
082    /**
083     * Equals.
084     * @param ob an Object.
085     * @return true if this is equal to o, else false.
086     */
087    @Override
088    @SuppressWarnings("unchecked")
089    public boolean equals(Object ob) {
090        MultiplicativeSet<C> c = null;
091        try {
092            c = (MultiplicativeSet<C>) ob;
093        } catch (ClassCastException e) {
094            return false;
095        }
096        if (c == null) {
097            return false;
098        }
099        if (!ring.equals(c.ring)) {
100            return false;
101        }
102        return mset.equals(c.mset);
103    }
104
105
106    /**
107     * Hash code for this condition.
108     * @see java.lang.Object#hashCode()
109     */
110    @Override
111    public int hashCode() {
112        int h;
113        h = ring.hashCode();
114        h = h << 17;
115        h += mset.hashCode();
116        return h;
117    }
118
119
120    /**
121     * Is set.
122     * @return true if this is the empty set, else false.
123     */
124    public boolean isEmpty() {
125        return mset.size() == 0;
126    }
127
128
129    /**
130     * Test if a polynomial is contained in this multiplicative set.
131     * @param c polynomial searched in mset.
132     * @return true, if c = prod_{m in mset} m, else false
133     */
134    public boolean contains(GenPolynomial<C> c) {
135        if (c == null || c.isZERO()) {
136            return false;
137        }
138        if (c.isConstant()) {
139            return true;
140        }
141        if (mset.isEmpty()) {
142            return false;
143        }
144        GenPolynomial<C> d = c;
145        for (GenPolynomial<C> n : mset) {
146            // System.out.println("mset n = " + n);
147            if (n.isONE()) { // do not use 1
148                continue;
149            }
150            GenPolynomial<C> q, r;
151            do {
152                GenPolynomial<C>[] qr = d.quotientRemainder(n);
153                q = qr[0];
154                r = qr[1];
155                // System.out.println("q = " + q + ", r = " + r + ", d = " + d +
156                // ", n = " + n);
157                if (!r.isZERO()) {
158                    continue;
159                }
160                if (q.isConstant()) {
161                    return true;
162                }
163                d = q;
164            } while (r.isZERO() && !d.isConstant());
165        }
166        return d.isConstant(); // false
167    }
168
169
170    /**
171     * Test if a list of polynomials is contained in multiplicative set.
172     * @param L list of polynomials to be searched in mset.
173     * @return true, if all c in L are in mset, else false
174     */
175    public boolean contains(List<GenPolynomial<C>> L) {
176        if (L == null || L.size() == 0) {
177            return true;
178        }
179        for (GenPolynomial<C> c : L) {
180            if (!contains(c)) {
181                return false;
182            }
183        }
184        return true;
185    }
186
187
188    /**
189     * Add polynomial to mset.
190     * @param cc polynomial to be added to mset.
191     * @return new multiplicative set. <b>Note:</b> must be overridden in
192     *         sub-classes.
193     */
194    public MultiplicativeSet<C> add(GenPolynomial<C> cc) {
195        if (cc == null || cc.isZERO() || cc.isConstant()) {
196            return this;
197        }
198        if (ring.coFac.isField()) {
199            cc = cc.monic();
200        }
201        List<GenPolynomial<C>> list;
202        if (mset.size() == 0) {
203            list = new ArrayList<GenPolynomial<C>>(1);
204            list.add(cc);
205            return new MultiplicativeSet<C>(ring, list);
206        }
207        GenPolynomial<C> c = removeFactors(cc);
208        if (c.isConstant()) {
209            logger.info("skipped unit or constant = {}", c);
210            return this;
211        }
212        if (ring.coFac.isField()) {
213            c = c.monic();
214        }
215        if (mset.size() == 0) {
216            logger.info("added to empty mset = {}", c);
217        } else {
218            logger.info("added to mset = {}", c);
219        }
220        list = new ArrayList<GenPolynomial<C>>(mset);
221        list.add(c);
222        return new MultiplicativeSet<C>(ring, list);
223    }
224
225
226    /**
227     * Replace polynomial list of mset.
228     * @param L polynomial list to replace mset.
229     * @return new multiplicative set. <b>Note:</b> must be overridden in
230     *         sub-classes.
231     */
232    public MultiplicativeSet<C> replace(List<GenPolynomial<C>> L) {
233        MultiplicativeSet<C> ms = new MultiplicativeSet<C>(ring);
234        if (L == null || L.size() == 0) {
235            return ms;
236        }
237        for (GenPolynomial<C> p : L) {
238            ms = ms.add(p);
239        }
240        return ms;
241    }
242
243
244    /**
245     * Remove factors by mset factors division.
246     * @param cc polynomial to be removed factors from mset.
247     * @return quotient polynomial.
248     */
249    public GenPolynomial<C> removeFactors(GenPolynomial<C> cc) {
250        if (cc == null || cc.isZERO() || cc.isConstant()) {
251            return cc;
252        }
253        if (mset.size() == 0) {
254            return cc;
255        }
256        GenPolynomial<C> c = cc;
257        for (GenPolynomial<C> n : mset) {
258            if (n.isConstant()) { // do not use 1, should not be in mset
259                continue;
260            }
261            GenPolynomial<C> q, r;
262            do {
263                GenPolynomial<C>[] qr = c.quotientRemainder(n);
264                q = qr[0];
265                r = qr[1];
266                if (!r.isZERO()) {
267                    continue;
268                }
269                if (q.isConstant()) {
270                    return q;
271                }
272                c = q;
273            } while (r.isZERO() && !c.isConstant());
274        }
275        return c;
276    }
277
278
279    /**
280     * Remove factors by mset factors division.
281     * @param L list of polynomial to be removed factors from mset.
282     * @return quotient polynomial list.
283     */
284    public List<GenPolynomial<C>> removeFactors(List<GenPolynomial<C>> L) {
285        if (L == null || L.size() == 0) {
286            return L;
287        }
288        if (mset.size() == 0) {
289            return L;
290        }
291        List<GenPolynomial<C>> M = new ArrayList<GenPolynomial<C>>(L.size());
292        for (GenPolynomial<C> p : L) {
293            p = removeFactors(p);
294            // nono, really: if ( !p.isConstant() ) {
295            M.add(p);
296        }
297        return M;
298    }
299
300}