Source code

001/*
002 * $Id: RelationTable.java 5888 2018-07-29 20:58:45Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.HashMap;
011import java.util.Iterator;
012import java.util.LinkedList;
013import java.util.List;
014import java.util.ListIterator;
015import java.util.Map;
016
017import org.apache.logging.log4j.Logger;
018import org.apache.logging.log4j.LogManager; 
019
020import edu.jas.kern.PrettyPrint;
021import edu.jas.structure.RingElem;
022
023
024/**
025 * RelationTable for solvable polynomials. This class maintains the
026 * non-commutative multiplication relations of solvable polynomial rings. The
027 * table entries are initialized with relations of the form x<sub>j</sub> *
028 * x<sub>i</sub> = p<sub>ij</sub>. During multiplication the relations are
029 * updated by relations of the form x<sub>j</sub><sup>k</sup> *
030 * x<sub>i</sub><sup>l</sup> = p<sub>ijkl</sub>. If no relation for
031 * x<sub>j</sub> * x<sub>i</sub> is found in the table, this multiplication is
032 * assumed to be commutative x<sub>i</sub> x<sub>j</sub>. Can also be used for
033 * relations between coefficients and main variables.
034 * @author Heinz Kredel
035 */
036
037public class RelationTable<C extends RingElem<C>> implements Serializable {
038
039
040    /**
041     * The data structure for the relations.
042     */
043    public final Map<List<Integer>, List> table;
044
045
046    /**
047     * The factory for the solvable polynomial ring.
048     */
049    public final GenSolvablePolynomialRing<C> ring;
050
051
052    /**
053     * Usage indicator: table or coeffTable.
054     */
055    public final boolean coeffTable;
056
057
058    private static final Logger logger = LogManager.getLogger(RelationTable.class);
059
060
061    private static final boolean debug = logger.isDebugEnabled();
062
063
064    /**
065     * Constructor for RelationTable requires ring factory. Note: This
066     * constructor is called within the constructor of the ring factory, so
067     * methods of this class can only be used after the other constructor has
068     * terminated.
069     * @param r solvable polynomial ring factory.
070     */
071    public RelationTable(GenSolvablePolynomialRing<C> r) {
072        this(r, false);
073    }
074
075
076    /**
077     * Constructor for RelationTable requires ring factory. Note: This
078     * constructor is called within the constructor of the ring factory, so
079     * methods of this class can only be used after the other constructor has
080     * terminated.
081     * @param r solvable polynomial ring factory.
082     * @param coeffTable indicator for coeffTable.
083     */
084    public RelationTable(GenSolvablePolynomialRing<C> r, boolean coeffTable) {
085        table = new HashMap<List<Integer>, List>();
086        ring = r;
087        if (ring == null) {
088            throw new IllegalArgumentException("RelationTable no ring");
089        }
090        this.coeffTable = coeffTable;
091    }
092
093
094    /**
095     * RelationTable equals. Tests same keySets and base relations.
096     * @see java.lang.Object#equals(java.lang.Object)
097     */
098    @Override
099    @SuppressWarnings("unchecked")
100    public boolean equals(Object p) {
101        if (p == null) {
102            return false;
103        }
104        if (!(p instanceof RelationTable)) {
105            logger.info("no RelationTable");
106            return false;
107        }
108        RelationTable<C> tab = (RelationTable<C>) p;
109        // not possible because of infinite recursion:
110        //if (!ring.equals(tab.ring)) {
111        //    logger.info("not same Ring " + ring.toScript() + ", " + tab.ring.toScript());
112        //    return false;
113        //}
114        if (!table.keySet().equals(tab.table.keySet())) {
115            logger.info("keySet != :  a = " + table.keySet() + ", b = " + tab.table.keySet());
116            return false;
117        }
118        for (Map.Entry<List<Integer>, List> me : table.entrySet()) {
119            List<Integer> k = me.getKey();
120            List a = me.getValue();
121            List b = tab.table.get(k);
122            // check contents, but only base relations
123            Map<ExpVectorPair, GenPolynomial<C>> t1ex = fromListDeg2(a);
124            Map<ExpVectorPair, GenPolynomial<C>> t2ex = fromListDeg2(b);
125            if (!equalMaps(t1ex, t2ex)) {
126                //System.out.println("a != b, a = " + t1ex + ", b = " + t2ex);
127                return false;
128            }
129        }
130        return true;
131    }
132
133
134    /**
135     * Convert mixed list to map for base relations.
136     * @param a mixed list
137     * @returns a map constructed from the list with deg(key) == 2.
138     */
139    @SuppressWarnings("unchecked")
140    Map<ExpVectorPair, GenPolynomial<C>> fromListDeg2(List a) {
141        Map<ExpVectorPair, GenPolynomial<C>> tex = new HashMap<ExpVectorPair, GenPolynomial<C>>();
142        Iterator ait = a.iterator();
143        while (ait.hasNext()) {
144            ExpVectorPair ae = (ExpVectorPair) ait.next();
145            if (!ait.hasNext()) {
146                break;
147            }
148            GenPolynomial<C> p = (GenPolynomial<C>) ait.next();
149            if (ae.totalDeg() == 2) { // only base relations
150                //System.out.println("ae => p: " + ae + " => " + p);
151                tex.put(ae, p);
152            }
153        }
154        return tex;
155    }
156
157
158    /**
159     * Hash code for base relations.
160     * @param a mixed list
161     * @returns hashCode(a)
162     */
163    @SuppressWarnings("unchecked")
164    int fromListDeg2HashCode(List a) {
165        int h = 0;
166        Iterator ait = a.iterator();
167        while (ait.hasNext()) {
168            ExpVectorPair ae = (ExpVectorPair) ait.next();
169            h = 31 * h + ae.hashCode();
170            if (!ait.hasNext()) {
171                break;
172            }
173            GenPolynomial<C> p = (GenPolynomial<C>) ait.next();
174            if (ae.totalDeg() == 2) { // only base relations
175                //System.out.println("ae => p: " + ae + " => " + p);
176                h = 31 * h + p.val.hashCode(); // avoid hash of ring
177            }
178        }
179        return h;
180    }
181
182
183    /**
184     * Equals for special maps.
185     * @param m1 first map
186     * @param m2 second map
187     * @returns true if both maps are equal
188     */
189    @SuppressWarnings("unchecked")
190    boolean equalMaps(Map<ExpVectorPair, GenPolynomial<C>> m1, Map<ExpVectorPair, GenPolynomial<C>> m2) {
191        if (!m1.keySet().equals(m2.keySet())) {
192            return false;
193        }
194        for (Map.Entry<ExpVectorPair, GenPolynomial<C>> me : m1.entrySet()) {
195            GenPolynomial<C> p1 = me.getValue();
196            ExpVectorPair ep = me.getKey();
197            GenPolynomial<C> p2 = m2.get(ep);
198            if (p1.compareTo(p2) != 0) { // not working: !p1.equals(p2)
199                logger.info("ep = " + ep + ", p1 = " + p1 + ", p2 = " + p2);
200                //logger.info("p1.compareTo(p2) = " + p1.compareTo(p2));
201                //logger.info("p1.equals(p2) = " + p1.equals(p2));
202                return false;
203            }
204        }
205        return true;
206    }
207
208
209    /**
210     * Hash code for this relation table.
211     * @see java.lang.Object#hashCode()
212     */
213    @Override
214    public int hashCode() {
215        //int h = ring.hashCode(); // infinite recursion
216        int h = 0; //table.hashCode();
217        h = table.keySet().hashCode();
218        for (Map.Entry<List<Integer>, List> me : table.entrySet()) {
219            //List<Integer> k = me.getKey();
220            List a = me.getValue();
221            int t1 = fromListDeg2HashCode(a);
222            h = 31 * h + t1;
223        }
224        return h;
225    }
226
227
228    /**
229     * Test if the table is empty.
230     * @return true if the table is empty, else false.
231     */
232    public boolean isEmpty() {
233        return table.isEmpty();
234    }
235
236
237    /**
238     * Get the String representation.
239     * @see java.lang.Object#toString()
240     */
241    @Override
242    public String toString() {
243        List v;
244        StringBuffer s = new StringBuffer("RelationTable[");
245        boolean first = true;
246        for (Map.Entry<List<Integer>, List> me : table.entrySet()) {
247            List<Integer> k = me.getKey();
248            if (first) {
249                first = false;
250            } else {
251                s.append(", ");
252            }
253            s.append(k.toString());
254            v = me.getValue();
255            s.append("=");
256            s.append(v.toString());
257        }
258        s.append("]");
259        return s.toString();
260    }
261
262
263    /**
264     * Get the String representation.
265     * @param vars names for the variables.
266     * @see java.lang.Object#toString()
267     */
268    @SuppressWarnings({ "unchecked", "cast" })
269    public String toString(String[] vars) {
270        if (vars == null) {
271            return toString();
272        }
273        StringBuffer s = new StringBuffer("");
274        String[] cvars = null;
275        if (coeffTable) {
276            if (ring.coFac instanceof GenPolynomialRing) {
277                cvars = ((GenPolynomialRing<C>) (Object) ring.coFac).getVars();
278            } else if (ring.coFac instanceof GenWordPolynomialRing) {
279                cvars = ((GenWordPolynomialRing<C>) (Object) ring.coFac).getVars();
280            }
281            s.append("Coefficient ");
282        }
283        s.append("RelationTable\n(");
284        List v;
285        if (PrettyPrint.isTrue()) {
286            boolean first = true;
287            for (Map.Entry<List<Integer>, List> me : table.entrySet()) {
288                //List<Integer> k = me.getKey();
289                if (first) {
290                    first = false;
291                    s.append("\n");
292                } else {
293                    s.append(",\n");
294                }
295                v = me.getValue();
296                for (Iterator jt = v.iterator(); jt.hasNext();) {
297                    ExpVectorPair ep = (ExpVectorPair) jt.next();
298                    GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next();
299                    if (ep.totalDeg() != 2) { // only base relations
300                        continue;
301                    }
302                    s.append("( " + ep.getFirst().toString(vars) + " ), ");
303                    if (cvars == null) {
304                        s.append("( " + ep.getSecond().toString(vars) + " ), ");
305                    } else {
306                        s.append("( " + ep.getSecond().toString(cvars) + " ), ");
307                    }
308                    s.append("( " + p.toString(vars) + " )");
309                    if (jt.hasNext()) {
310                        s.append(",\n");
311                    }
312                }
313            }
314        } else {
315            boolean first = true;
316            for (Map.Entry<List<Integer>, List> me : table.entrySet()) {
317                //List<Integer> k = me.getKey();
318                if (first) {
319                    first = false;
320                } else {
321                    s.append(",\n");
322                }
323                v = me.getValue();
324                for (Iterator jt = v.iterator(); jt.hasNext();) {
325                    ExpVectorPair ep = (ExpVectorPair) jt.next();
326                    s.append("( " + ep.getFirst().toString(vars) + " ), ");
327                    if (cvars == null) {
328                        s.append("( " + ep.getSecond().toString(vars) + " ), ");
329                    } else {
330                        s.append("( " + ep.getSecond().toString(cvars) + " ), ");
331                    }
332                    GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next();
333                    //s.append("( " + p.toString(vars) + " )");
334                    s.append(" " + p.toString(vars));
335                    if (jt.hasNext()) {
336                        s.append(",\n");
337                    }
338                }
339            }
340        }
341        s.append("\n)\n");
342        return s.toString();
343    }
344
345
346    /**
347     * Get a scripting compatible string representation.
348     * @return script compatible representation for this relation table.
349     */
350    @SuppressWarnings({ "unchecked", "cast" })
351    public String toScript() {
352        // Python case
353        String[] vars = ring.vars;
354        String[] cvars = null;
355        if (coeffTable) {
356            if (ring.coFac instanceof GenPolynomialRing) {
357                cvars = ((GenPolynomialRing<C>) (Object) ring.coFac).getVars();
358            } else if (ring.coFac instanceof GenWordPolynomialRing) {
359                cvars = ((GenWordPolynomialRing<C>) (Object) ring.coFac).getVars();
360            }
361        }
362        List v;
363        StringBuffer s = new StringBuffer("[");
364        boolean first = true;
365        for (Map.Entry<List<Integer>, List> me : table.entrySet()) {
366            //List<Integer> k = me.getKey();
367            if (first) {
368                first = false;
369                s.append("");
370            } else {
371                s.append(", ");
372            }
373            v = me.getValue();
374            for (Iterator jt = v.iterator(); jt.hasNext();) {
375                ExpVectorPair ep = (ExpVectorPair) jt.next();
376                GenPolynomial<C> p = (GenPolynomial<C>) jt.next();
377                if (ep.totalDeg() > 2) { // only base relations
378                    continue;
379                }
380                s.append("" + ep.getFirst().toScript(vars) + ", ");
381                if (coeffTable) {
382                    String eps = ep.getSecond().toScript(cvars);
383                    if (eps.isEmpty()) { // if from a deeper down ring
384                        eps = p.leadingBaseCoefficient().abs().toScript();
385                    }
386                    s.append("" + eps + ", ");
387                } else {
388                    s.append("" + ep.getSecond().toScript(vars) + ", ");
389                }
390                //s.append("( " + p.toScript() + " )");
391                s.append(" " + p.toScript());
392                if (jt.hasNext()) {
393                    s.append(", ");
394                }
395            }
396        }
397        s.append("]");
398        return s.toString();
399    }
400
401
402    /**
403     * Update or initialize RelationTable with new relation. relation is e * f =
404     * p.
405     * @param e first term.
406     * @param f second term.
407     * @param p solvable product polynomial.
408     */
409    @SuppressWarnings({ "unchecked", "cast" })
410    public synchronized void update(ExpVector e, ExpVector f, GenSolvablePolynomial<C> p) {
411        if (p == null || e == null || f == null) {
412            throw new IllegalArgumentException("RelationTable update e|f|p == null");
413        }
414        GenSolvablePolynomialRing<C> sring = p.ring;
415        if (debug) {
416            logger.info("new relation = " + sring.toScript(e) + " .*. " + sring.toScript(f) + " = "
417                            + p.toScript());
418        }
419        // test equal HTs for left and right side
420        if (!coeffTable) { // old case
421            if (e.totalDeg() == 1 && f.totalDeg() == 1) { // higher or mixed degrees todo
422                int[] de = e.dependencyOnVariables();
423                int[] df = f.dependencyOnVariables();
424                logger.debug("update e ? f " + de[0] + " " + df[0]);
425                //int t = ring.tord.getDescendComparator().compare(e,f);
426                //System.out.println("update compare(e,f) = " + t);
427                if (de[0] == df[0]) { // error 
428                    throw new IllegalArgumentException("RelationTable update e==f");
429                }
430                if (de[0] > df[0]) { // invalid update 
431                    logger.error("update e < f: " + sring.toScript(e) + " < " + sring.toScript(f));
432                    //if (debug && false) {
433                    //    throw new IllegalArgumentException("update e < f");
434                    //}
435                    ExpVector tmp = e;
436                    e = f;
437                    f = tmp;
438                    Map.Entry<ExpVector, C> m = p.leadingMonomial();
439                    ExpVector ef = e.sum(f);
440                    if (!ef.equals(m.getKey())) {
441                        throw new IllegalArgumentException("update e*f != lt(p): " + sring.toScript(ef)
442                                        + ", lt = " + sring.toScript(m.getKey()));
443                    }
444                    GenPolynomial<C> r = p.reductum(); //subtract(m.getValue(), m.getKey());
445                    r = r.negate();
446                    //p = (GenSolvablePolynomial<C>) r.sum(m.getValue(), m.getKey());
447                    p = (GenSolvablePolynomial<C>) r;
448                    p.doPutToMap(m.getKey(), m.getValue());
449                }
450            }
451            ExpVector ef = e.sum(f);
452            ExpVector lp = p.leadingExpVector();
453            if (!ef.equals(lp)) { // check for suitable term order
454                logger.error("relation term order = " + ring.tord);
455                throw new IllegalArgumentException("update e*f != lt(p): " + sring.toScript(ef) + " != "
456                                + sring.toScript(lp));
457            }
458        } else { // is coeffTable
459            ExpVector lp = p.leadingExpVector();
460            if (!e.equals(lp)) { // check for suitable term order
461                logger.error("relation term order = " + ring.tord);
462                throw new IllegalArgumentException("Coefficient RelationTable update e != lt(p): "
463                                + sring.toScript(e) + " != " + sring.toScript(lp));
464            }
465            if (p.leadingBaseCoefficient() instanceof GenPolynomial) {
466                lp = ((GenPolynomial<C>) (Object) p.leadingBaseCoefficient()).leadingExpVector();
467                if (!f.equals(lp)) { // check for suitable term order
468                    logger.error("relation term order = " + ring.tord);
469                    logger.error("Coefficient RelationTable update f != lt(lfcd(p)): " + sring.toScript(e)
470                                    + ", f = " + f + ", p = " + p.toScript());
471                    throw new IllegalArgumentException("Coefficient RelationTable update f != lt(lfcd(p)): "
472                                    + e + ", f = " + f + ", p = " + p);
473                }
474            } else if (p.leadingBaseCoefficient() instanceof GenWordPolynomial) {
475                lp = ((GenWordPolynomial<C>) (Object) p.leadingBaseCoefficient()).leadingWord()
476                                .leadingExpVector();
477                if (!f.equals(lp)) { // check for suitable term order and word structure
478                    logger.error("relation term order = " + ring.tord);
479                    logger.error("Coefficient RelationTable update f != lt(lfcd(p)): " + sring.toScript(e)
480                                    + ", f = " + f + ", p = " + p.toScript());
481                    throw new IllegalArgumentException("Coefficient RelationTable update f != lt(lfcd(p)): "
482                                    + e + ", f = " + f + ", p = " + p);
483                }
484            }
485        }
486        List<Integer> key = makeKey(e, f);
487        ExpVectorPair evp = new ExpVectorPair(e, f);
488        if (key.size() != 2) {
489            logger.warn("key = " + key + ", evp = " + evp);
490        }
491        List part = table.get(key);
492        if (part == null) { // initialization only
493            part = new LinkedList();
494            part.add(evp);
495            part.add(p);
496            table.put(key, part);
497            return;
498        }
499        @SuppressWarnings("unused")
500        Object skip;
501        int index = -1;
502        synchronized (part) { // with lookup()
503            for (ListIterator it = part.listIterator(); it.hasNext();) {
504                ExpVectorPair look = (ExpVectorPair) it.next();
505                skip = it.next(); // skip poly
506                if (look.isMultiple(evp)) {
507                    index = it.nextIndex();
508                    // last index of or first index of: break
509                }
510            }
511            if (index < 0) {
512                index = 0;
513            }
514            part.add(index, evp);
515            part.add(index + 1, p);
516        }
517        // table.put( key, part ); // required??
518    }
519
520
521    /**
522     * Update or initialize RelationTable with new relation. relation is e * f =
523     * p.
524     * @param E first term polynomial.
525     * @param F second term polynomial.
526     * @param p solvable product polynomial.
527     */
528    @SuppressWarnings({ "unchecked", "cast" })
529    public void update(GenPolynomial<C> E, GenPolynomial<C> F, GenSolvablePolynomial<C> p) {
530        if (E.isZERO() || F.isZERO()) {
531            throw new IllegalArgumentException("polynomials may not be zero: " + E + ", " + F);
532        }
533        C ce = E.leadingBaseCoefficient();
534        C cf = F.leadingBaseCoefficient();
535        if (!ce.isONE()) {
536            throw new IllegalArgumentException("lbcf of polynomials must be one: " + ce + ", " + cf
537                            + ", p = " + p);
538        }
539        ExpVector e = E.leadingExpVector();
540        ExpVector f = F.leadingExpVector();
541        if (coeffTable && f.isZERO()) {
542            if (cf instanceof GenPolynomial) {
543                f = ((GenPolynomial<C>) (Object) cf).leadingExpVector();
544            } else if (cf instanceof GenWordPolynomial) {
545                f = ((GenWordPolynomial<C>) (Object) cf).leadingWord().leadingExpVector();
546            }
547        }
548        //logger.info("update: " + e + " .*. " + f + " = " + p);
549        update(e, f, p);
550    }
551
552
553    /**
554     * Update or initialize RelationTable with new relation. relation is e * f =
555     * p.
556     * @param E first term polynomial.
557     * @param F second term polynomial.
558     * @param p product polynomial.
559     */
560    public void update(GenPolynomial<C> E, GenPolynomial<C> F, GenPolynomial<C> p) {
561        if (p.isZERO()) {
562            throw new IllegalArgumentException("polynomial may not be zero: " + p);
563        }
564        if (p.isONE()) {
565            throw new IllegalArgumentException("product of polynomials may not be one: " + p);
566        }
567        GenSolvablePolynomial<C> sp = new GenSolvablePolynomial<C>(ring, p.val);
568        update(E, F, sp);
569    }
570
571
572    /**
573     * Update or initialize RelationTable with new relation. relation is e * f =
574     * p.
575     * @param e first term.
576     * @param f second term.
577     * @param p solvable product polynomial.
578     */
579    public void update(ExpVector e, ExpVector f, GenPolynomial<C> p) {
580        if (p.isZERO()) {
581            throw new IllegalArgumentException("polynomial may not be zero: " + p);
582        }
583        if (p.isONE()) {
584            throw new IllegalArgumentException("product of polynomials may not be one: " + p);
585        }
586        GenSolvablePolynomial<C> sp = new GenSolvablePolynomial<C>(ring, p.val);
587        update(e, f, sp);
588    }
589
590
591    /**
592     * Lookup RelationTable for existing relation. Find p with e * f = p. If no
593     * relation for e * f is contained in the table then return the symmetric
594     * product p = 1 e f.
595     * @param e first term.
596     * @param f second term.
597     * @return t table relation container, contains e' and f' with e f = e'
598     *         lt(p) f'.
599     */
600    @SuppressWarnings({ "unchecked", "cast" })
601    public TableRelation<C> lookup(ExpVector e, ExpVector f) {
602        List<Integer> key = makeKey(e, f);
603        List part = table.get(key);
604        if (part == null) { // symmetric product
605            GenSolvablePolynomial<C> p = null;
606            C c = null;
607            if (!coeffTable) {
608                ExpVector ef = e.sum(f);
609                //p = new GenSolvablePolynomial<C>(ring, ring.getONECoefficient(), ef);
610                p = ring.valueOf(ef);
611            } else {
612                if (ring.coFac instanceof GenPolynomialRing) {
613                    GenPolynomialRing<C> cofac = (GenPolynomialRing<C>) (Object) ring.coFac;
614                    //System.out.println("f = " + f + ", e = " + e);
615                    GenPolynomial<C> pc = cofac.valueOf(f);
616                    c = (C) (Object) pc;
617                } else if (ring.coFac instanceof GenWordPolynomialRing) {
618                    GenWordPolynomialRing<C> cofac = (GenWordPolynomialRing<C>) (Object) ring.coFac;
619                    //System.out.println("f = " + f + ", e = " + e);
620                    GenWordPolynomial<C> pc = cofac.valueOf(f);
621                    c = (C) (Object) pc;
622                }
623                p = new GenSolvablePolynomial<C>(ring, c, e);
624                //System.out.println("pc = " + pc + ", p = " + p);
625            }
626            return new TableRelation<C>(null, null, p);
627        }
628        // no distinction between coefficient f or polynomial f
629        ExpVectorPair evp = new ExpVectorPair(e, f);
630        ExpVector ep = null;
631        ExpVector fp = null;
632        ExpVectorPair look = null;
633        GenSolvablePolynomial<C> p = null;
634        synchronized (part) { // with update()
635            for (Iterator it = part.iterator(); it.hasNext();) {
636                look = (ExpVectorPair) it.next();
637                p = (GenSolvablePolynomial<C>) it.next();
638                if (evp.isMultiple(look)) {
639                    ep = e.subtract(look.getFirst());
640                    fp = f.subtract(look.getSecond());
641                    if (ep.isZERO()) {
642                        ep = null;
643                    }
644                    if (fp.isZERO()) {
645                        fp = null;
646                    }
647                    if (debug) {
648                        if (p != null && p.ring.vars != null) {
649                            logger.info("found relation = " + e.toString(p.ring.vars) + " .*. "
650                                            + f.toString(p.ring.vars) + " = " + p);
651                        } else {
652                            logger.info("found relation = " + e + " .*. " + f + " = " + p);
653                        }
654                    }
655                    return new TableRelation<C>(ep, fp, p);
656                }
657            }
658        }
659        // unreacheable code!
660        throw new RuntimeException("no entry found in relation table for " + evp);
661    }
662
663
664    /**
665     * Construct a key for (e,f).
666     * @param e first term.
667     * @param f second term.
668     * @return k key for (e,f).
669     */
670    protected List<Integer> makeKey(ExpVector e, ExpVector f) {
671        int[] de = e.dependencyOnVariables();
672        int[] df = f.dependencyOnVariables();
673        List<Integer> key = new ArrayList<Integer>(de.length + df.length);
674        for (int i = 0; i < de.length; i++) {
675            key.add(Integer.valueOf(de[i]));
676        }
677        for (int i = 0; i < df.length; i++) {
678            key.add(Integer.valueOf(df[i]));
679        }
680        return key;
681    }
682
683
684    /**
685     * Size of the table.
686     * @return n number of non-commutative relations.
687     */
688    public int size() {
689        int s = 0;
690        if (table == null || table.isEmpty()) {
691            return s;
692        }
693        for (Iterator<List> it = table.values().iterator(); it.hasNext();) {
694            List list = it.next();
695            s += list.size() / 2;
696        }
697        return s;
698    }
699
700
701    /**
702     * Extend variables. Used e.g. in module embedding. Extend all ExpVectors
703     * and polynomials of the given relation table by i elements and put the
704     * relations into this table, i.e. this should be empty.
705     * @param tab a relation table to be extended and inserted into this.
706     */
707    @SuppressWarnings("unchecked")
708    public void extend(RelationTable<C> tab) {
709        if (tab.table.isEmpty()) {
710            return;
711        }
712        // assert this.size() == 0
713        int i = ring.nvar - tab.ring.nvar;
714        int j = 0;
715        long k = 0l;
716        List val;
717        for (List<Integer> key : tab.table.keySet()) {
718            val = tab.table.get(key);
719            for (Iterator jt = val.iterator(); jt.hasNext();) {
720                ExpVectorPair ep = (ExpVectorPair) jt.next();
721                ExpVector e = ep.getFirst();
722                ExpVector f = ep.getSecond();
723                GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next();
724                ExpVector ex = e.extend(i, j, k);
725                ExpVector fx;
726                if (coeffTable) {
727                    fx = f;
728                } else {
729                    fx = f.extend(i, j, k);
730                }
731                GenSolvablePolynomial<C> px = (GenSolvablePolynomial<C>) p.extend(ring, j, k);
732                this.update(ex, fx, px);
733            }
734        }
735        return;
736    }
737
738
739    /**
740     * Contract variables. Used e.g. in module embedding. Contract all
741     * ExpVectors and polynomials of the given relation table by i elements and
742     * put the relations into this table, i.e. this should be empty.
743     * @param tab a relation table to be contracted and inserted into this.
744     */
745    @SuppressWarnings("unchecked")
746    public void contract(RelationTable<C> tab) {
747        if (tab.table.isEmpty()) {
748            return;
749        }
750        // assert this.size() == 0
751        int i = tab.ring.nvar - ring.nvar;
752        List val;
753        for (List<Integer> key : tab.table.keySet()) {
754            val = tab.table.get(key);
755            //System.out.println("key = " + key + ", val = " + val);
756            for (Iterator jt = val.iterator(); jt.hasNext();) {
757                ExpVectorPair ep = (ExpVectorPair) jt.next();
758                ExpVector e = ep.getFirst();
759                ExpVector f = ep.getSecond();
760                GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next();
761                ExpVector ec = e.contract(i, e.length() - i);
762                ExpVector fc;
763                if (coeffTable) {
764                    fc = f;
765                } else {
766                    fc = f.contract(i, f.length() - i);
767                }
768                //System.out.println("ec = " + ec + ", fc = " + fc);
769                if (ec.isZERO()) {
770                    continue;
771                }
772                Map<ExpVector, GenPolynomial<C>> mc = p.contract(ring);
773                if (mc.size() != 1) {
774                    continue;
775                }
776                GenPolynomial<C> pc = mc.values().iterator().next();
777                this.update(ec, fc, pc);
778            }
779        }
780        return;
781    }
782
783
784    /**
785     * Recursive representation. Split all ExpVectors and polynomials of the
786     * given relation table to lower elements and upper elements and put the
787     * relations into this table or this as coefficient table, i.e. this should
788     * be empty.
789     * @param tab a relation table to be contracted and inserted into this.
790     */
791    @SuppressWarnings({ "unchecked", "cast" })
792    public void recursive(RelationTable tab) { //<C>
793        if (tab.table.isEmpty()) {
794            return;
795        }
796        //System.out.println("rel ring = " + ring.toScript());
797        // assert this.size() == 0
798        GenPolynomialRing<C> cring = (GenPolynomialRing<C>) (Object) ring.coFac;
799        //System.out.println("cring    = " + cring.toScript());
800        GenSolvablePolynomial<C> pc;
801        int i = ring.nvar; // tab.ring.nvar -
802        for (Object okey : tab.table.keySet()) {
803            List<Integer> key = (List<Integer>) okey;
804            List val = (List) tab.table.get(key);
805            //System.out.println("key = " + key + ", val = " + val);
806            for (Iterator jt = val.iterator(); jt.hasNext();) {
807                ExpVectorPair ep = (ExpVectorPair) jt.next(); // ?? concurrent mod exception 
808                ExpVector e = ep.getFirst();
809                ExpVector f = ep.getSecond();
810                GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next();
811                ExpVector ec = e.contract(0, i);
812                ExpVector fc;
813                if (coeffTable) {
814                    fc = f;
815                } else {
816                    fc = f.contract(0, i);
817                }
818                //System.out.println("ec = " + ec + ", fc = " + fc);
819                if (ec.isZERO()) {
820                    continue;
821                }
822                Map<ExpVector, GenPolynomial<C>> mc = p.contract(cring);
823                //System.out.println("mc = " + mc + ", p = " + p);
824                //System.out.println("mc.ring = " + mc.values().iterator().next().ring.toScript());
825                if (mc.size() == 1) { // < 1 only for p == 0
826                    pc = (GenSolvablePolynomial<C>) mc.values().iterator().next();
827                    this.update(ec, fc, pc);
828                } else { // construct recursive polynomial
829                    GenSolvablePolynomial<C> qr = ring.getZERO();
830                    for (Map.Entry<ExpVector, GenPolynomial<C>> mce : mc.entrySet()) {
831                        ExpVector g = mce.getKey();
832                        GenPolynomial<C> q = mce.getValue();
833                        C cq = (C) (Object) q;
834                        GenSolvablePolynomial<C> qp = new GenSolvablePolynomial<C>(ring, cq, g);
835                        qr = (GenSolvablePolynomial<C>) qr.sum(qp);
836                    }
837                    if (coeffTable) {
838                        fc = ((GenPolynomial<C>) (Object) qr.leadingBaseCoefficient()).leadingExpVector();
839                    }
840                    if (fc.isZERO()) {
841                        continue;
842                    }
843                    //System.out.println("ec = " + ec + ", fc = " + fc + ", qr = " + qr);
844                    if (coeffTable) {
845                        String qrs = ring.toScript(ec) + " * " + qr.leadingBaseCoefficient() + " = " + qr.toScript();
846                        logger.info("coeffTable: adding " + qrs);
847                    } else {
848                        String qrs = ring.toScript(ec) + " * " + ring.toScript(fc) + " = " + qr.toScript();
849                        logger.info("no coeffTable: adding " + qrs);
850                    }
851                    this.update(ec, fc, qr);
852                }
853            }
854        }
855        return;
856    }
857
858
859    /**
860     * Reverse variables and relations. Used e.g. in opposite rings. Reverse all
861     * ExpVectors and polynomials of the given relation table and put the
862     * modified relations into this table, i.e. this should be empty.
863     * @param tab a relation table to be reverted and inserted into this.
864     */
865    @SuppressWarnings("unchecked")
866    public void reverse(RelationTable<C> tab) {
867        if (tab.table.isEmpty()) {
868            return;
869        }
870        if (!table.isEmpty()) {
871            logger.error("reverse table not empty");
872        }
873        int k = -1;
874        if (ring.tord.getEvord2() != 0 && ring.partial) {
875            k = ring.tord.getSplit();
876        }
877        logger.debug("k split = " + k);
878        //System.out.println("k split = " + k );
879        //System.out.println("reversed ring = " + ring.toScript() );
880        for (List<Integer> key : tab.table.keySet()) {
881            List val = tab.table.get(key);
882            for (Iterator jt = val.iterator(); jt.hasNext();) {
883                ExpVectorPair ep = (ExpVectorPair) jt.next();
884                ExpVector e = ep.getFirst();
885                ExpVector f = ep.getSecond();
886                GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next();
887                //logger.info("e pre reverse = " + e );
888                //logger.info("f pre reverse = " + f );
889                //logger.info("p pre reverse = " + p );
890                //if (e.degree() > 1 || f.degree() > 1) { // not required
891                //    continue; // revert only base relations
892                //}
893                ExpVector ex;
894                ExpVector fx;
895                GenSolvablePolynomial<C> px;
896                boolean change = true; // if relevant vars reversed
897                if (k >= 0) {
898                    ex = e.reverse(k);
899                    if (coeffTable) {
900                        fx = f;
901                    } else {
902                        fx = f.reverse(k);
903                    }
904                    // todo check relevant vars
905                    //int[] ed = ex.dependencyOnVariables(); // = e
906                    //if (ed.length == 0 || ed[0] >= k) { // k >= 0
907                    //    change = false; 
908                    //}
909                    //int[] fd = fx.dependencyOnVariables(); // = f
910                    //if (fd.length == 0 || fd[0] >= k) { // k >= 0
911                    //    change = false; 
912                    //}
913                } else {
914                    ex = e.reverse();
915                    if (coeffTable) {
916                        fx = f;
917                    } else {
918                        fx = f.reverse();
919                    }
920                }
921                px = (GenSolvablePolynomial<C>) p.reverse(ring);
922                //System.out.println("update, p, px: " + p.toScript() + " reverse:" + px.toScript() );
923                if (!change) {
924                    this.update(e, f, px); // same order
925                } else {
926                    if (coeffTable) {
927                        this.update(ex, fx, px); // same order
928                    } else {
929                        this.update(fx, ex, px); // opposite order
930                    }
931                }
932            }
933        }
934        return;
935    }
936
937
938    /**
939     * Convert relation table to list of polynomial triples.
940     * @return rel = (e1,f1,p1, ...) where ei * fi = pi are solvable relations.
941     */
942    @SuppressWarnings({ "unchecked", "cast" })
943    public List<GenSolvablePolynomial<C>> relationList() {
944        List<GenSolvablePolynomial<C>> rels = new ArrayList<GenSolvablePolynomial<C>>();
945        for (Map.Entry<List<Integer>, List> me : table.entrySet()) {
946            List v = me.getValue();
947            for (Iterator jt = v.iterator(); jt.hasNext();) {
948                ExpVectorPair ep = (ExpVectorPair) jt.next();
949                ExpVector e = ep.getFirst();
950                GenSolvablePolynomial<C> pe = ring.valueOf(e);
951                ExpVector f = ep.getSecond();
952                GenSolvablePolynomial<C> pf = null;
953                if (coeffTable) { 
954                    C cf = null;
955                    if (ring.coFac instanceof GenPolynomialRing) {
956                        GenPolynomial<C> cpf;
957                        cpf = ((GenPolynomialRing<C>) (Object) ring.coFac).valueOf(f);
958                        cf = (C) (Object) cpf; // down cast
959                    } else if (ring.coFac instanceof GenWordPolynomialRing) {
960                        GenWordPolynomial<C> cpf;
961                        cpf = ((GenWordPolynomialRing<C>) (Object) ring.coFac).valueOf(f);
962                        cf = (C) (Object) cpf; // down cast
963                    }
964                    pf = ring.valueOf(cf);
965                } else {
966                    pf = ring.valueOf(f);
967                }
968                GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next();
969                rels.add(pe);
970                rels.add(pf);
971                rels.add(p);
972            }
973        }
974        return rels;
975    }
976
977
978    /**
979     * Add list of polynomial triples as relations.
980     * @param rel = (e1,f1,p1, ...) where ei * fi = pi are solvable relations.
981     *            <b>Note:</b> Only because of type erasure, aequivalent to
982     *            addRelations().
983     */
984    public void addSolvRelations(List<GenSolvablePolynomial<C>> rel) {
985        PolynomialList<C> Prel = new PolynomialList<C>(ring, rel);
986        addRelations(Prel.getList());
987    }
988
989
990    /**
991     * Add list of polynomial triples as relations.
992     * @param rel = (e1,f1,p1, ...) where ei * fi = pi are solvable relations.
993     */
994    @SuppressWarnings({ "unchecked", "cast" })
995    public void addRelations(List<GenPolynomial<C>> rel) {
996        if (rel == null || rel.isEmpty()) {
997            return;
998        }
999        Iterator<GenPolynomial<C>> relit = rel.iterator();
1000        while (relit.hasNext()) {
1001            GenPolynomial<C> E = relit.next();
1002            ExpVector e = E.leadingExpVector();
1003            ExpVector f = null;
1004            if (!relit.hasNext()) {
1005                throw new IllegalArgumentException("F and poly part missing");
1006            }
1007            GenPolynomial<C> F = relit.next();
1008            if (!relit.hasNext()) {
1009                throw new IllegalArgumentException("poly part missing");
1010            }
1011            GenPolynomial<C> P = relit.next();
1012            if (coeffTable) { 
1013                if (!F.isConstant()) { 
1014                    throw new IllegalArgumentException("F  not constant for coeffTable: " + F);
1015                }
1016                if (ring.coFac instanceof GenPolynomialRing) {
1017                    f = ((GenPolynomial<C>) (Object) F.leadingBaseCoefficient()).leadingExpVector();
1018                } else if (ring.coFac instanceof GenWordPolynomialRing) {
1019                    f = ((GenWordPolynomial<C>) (Object) F.leadingBaseCoefficient()).leadingWord()
1020                                    .leadingExpVector();
1021                }
1022            } else {
1023                f = F.leadingExpVector();
1024            }
1025            update(e, f, P);
1026        }
1027        return;
1028    }
1029
1030}