Source code

001/*
002 * $Id: GenPolynomialTokenizer.java 4266 2012-10-21 20:24:01Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.io.BufferedReader;
009import java.io.IOException;
010import java.io.InputStreamReader;
011import java.io.Reader;
012import java.io.StreamTokenizer;
013import java.nio.charset.Charset;
014import java.util.ArrayList;
015import java.util.Arrays;
016import java.util.Iterator;
017import java.util.List;
018import java.util.Scanner;
019import java.util.Set;
020import java.util.TreeSet;
021
022import org.apache.log4j.Logger;
023
024import edu.jas.arith.BigComplex;
025import edu.jas.arith.BigDecimal;
026import edu.jas.arith.BigInteger;
027import edu.jas.arith.BigQuaternion;
028import edu.jas.arith.BigRational;
029import edu.jas.arith.ModInteger;
030import edu.jas.arith.ModIntegerRing;
031import edu.jas.arith.ModLongRing;
032import edu.jas.structure.Power;
033import edu.jas.structure.RingElem;
034import edu.jas.structure.RingFactory;
035
036
037/**
038 * GenPolynomial Tokenizer. Used to read rational polynomials and lists of
039 * polynomials from input streams. Arbitrary polynomial rings and coefficient
040 * rings can be read with RingFactoryTokenizer. <b>Note:</b> Can no more read
041 * QuotientRing since end of 2010, revision 3441. Quotient coefficients and
042 * others can still be read if the respective factory is provided via the
043 * constructor.
044 * @see edu.jas.application.RingFactoryTokenizer
045 * @author Heinz Kredel
046 */
047public class GenPolynomialTokenizer {
048
049
050    private static final Logger logger = Logger.getLogger(GenPolynomialTokenizer.class);
051
052
053    private final boolean debug = logger.isDebugEnabled();
054
055
056    private String[] vars;
057
058
059    private int nvars = 1;
060
061
062    private TermOrder tord;
063
064
065    private RelationTable table;
066
067
068    //private Reader in;
069    private final StreamTokenizer tok;
070
071
072    private final Reader reader;
073
074
075    private RingFactory fac;
076
077
078    private static enum coeffType {
079        BigRat, BigInt, ModInt, BigC, BigQ, BigD, ANrat, ANmod, IntFunc
080    };
081
082
083    private coeffType parsedCoeff = coeffType.BigRat;
084
085
086    private GenPolynomialRing pfac;
087
088
089    private static enum polyType {
090        PolBigRat, PolBigInt, PolModInt, PolBigC, PolBigD, PolBigQ, PolANrat, PolANmod, PolIntFunc
091    };
092
093
094    private polyType parsedPoly = polyType.PolBigRat;
095
096
097    private GenSolvablePolynomialRing spfac;
098
099
100    /**
101     * noargs constructor reads from System.in.
102     */
103    public GenPolynomialTokenizer() {
104        this(new BufferedReader(new InputStreamReader(System.in,Charset.forName("UTF8"))));
105    }
106
107
108    /**
109     * constructor with Ring and Reader.
110     * @param rf ring factory.
111     * @param r reader stream.
112     */
113    public GenPolynomialTokenizer(GenPolynomialRing rf, Reader r) {
114        this(r);
115        if (rf == null) {
116            return;
117        }
118        if (rf instanceof GenSolvablePolynomialRing) {
119            pfac = rf;
120            spfac = (GenSolvablePolynomialRing) rf;
121        } else {
122            pfac = rf;
123            spfac = null;
124        }
125        fac = rf.coFac;
126        vars = rf.vars;
127        if (vars != null) {
128            nvars = vars.length;
129        }
130        tord = rf.tord;
131        // relation table
132        if (spfac != null) {
133            table = spfac.table;
134        } else {
135            table = null;
136        }
137    }
138
139
140    /**
141     * constructor with Reader.
142     * @param r reader stream.
143     */
144    @SuppressWarnings("unchecked")
145    public GenPolynomialTokenizer(Reader r) {
146        //BasicConfigurator.configure();
147        vars = null;
148        tord = new TermOrder();
149        nvars = 1;
150        fac = new BigRational(1);
151
152        pfac = new GenPolynomialRing<BigRational>(fac, nvars, tord, vars);
153        spfac = new GenSolvablePolynomialRing<BigRational>(fac, nvars, tord, vars);
154
155        reader = r;
156        tok = new StreamTokenizer(reader);
157        tok.resetSyntax();
158        // tok.eolIsSignificant(true); no more
159        tok.eolIsSignificant(false);
160        tok.wordChars('0', '9');
161        tok.wordChars('a', 'z');
162        tok.wordChars('A', 'Z');
163        tok.wordChars('_', '_'); // for subscripts x_i
164        tok.wordChars('/', '/'); // wg. rational numbers
165        tok.wordChars(128 + 32, 255);
166        tok.whitespaceChars(0, ' ');
167        tok.commentChar('#');
168        tok.quoteChar('"');
169        tok.quoteChar('\'');
170        //tok.slashStarComments(true); does not work
171
172    }
173
174
175    /**
176     * Initialize coefficient and polynomial factories.
177     * @param rf ring factory.
178     * @param ct coefficient type.
179     */
180    @SuppressWarnings("unchecked")
181    public void initFactory(RingFactory rf, coeffType ct) {
182        fac = rf;
183        parsedCoeff = ct;
184
185        switch (ct) {
186        case BigRat:
187            pfac = new GenPolynomialRing<BigRational>(fac, nvars, tord, vars);
188            parsedPoly = polyType.PolBigRat;
189            break;
190        case BigInt:
191            pfac = new GenPolynomialRing<BigInteger>(fac, nvars, tord, vars);
192            parsedPoly = polyType.PolBigInt;
193            break;
194        case ModInt:
195            pfac = new GenPolynomialRing<ModInteger>(fac, nvars, tord, vars);
196            parsedPoly = polyType.PolModInt;
197            break;
198        case BigC:
199            pfac = new GenPolynomialRing<BigComplex>(fac, nvars, tord, vars);
200            parsedPoly = polyType.PolBigC;
201            break;
202        case BigQ:
203            pfac = new GenPolynomialRing<BigQuaternion>(fac, nvars, tord, vars);
204            parsedPoly = polyType.PolBigQ;
205            break;
206        case BigD:
207            pfac = new GenPolynomialRing<BigDecimal>(fac, nvars, tord, vars);
208            parsedPoly = polyType.PolBigD;
209            break;
210        case IntFunc:
211            pfac = new GenPolynomialRing<GenPolynomial<BigRational>>(fac, nvars, tord, vars);
212            parsedPoly = polyType.PolIntFunc;
213            break;
214        default:
215            pfac = new GenPolynomialRing<BigRational>(fac, nvars, tord, vars);
216            parsedPoly = polyType.PolBigRat;
217        }
218    }
219
220
221    /**
222     * Initialize polynomial and solvable polynomial factories.
223     * @param rf ring factory.
224     * @param ct coefficient type.
225     */
226    @SuppressWarnings("unchecked")
227    public void initSolvableFactory(RingFactory rf, coeffType ct) {
228        fac = rf;
229        parsedCoeff = ct;
230
231        switch (ct) {
232        case BigRat:
233            spfac = new GenSolvablePolynomialRing<BigRational>(fac, nvars, tord, vars);
234            parsedPoly = polyType.PolBigRat;
235            break;
236        case BigInt:
237            spfac = new GenSolvablePolynomialRing<BigInteger>(fac, nvars, tord, vars);
238            parsedPoly = polyType.PolBigInt;
239            break;
240        case ModInt:
241            spfac = new GenSolvablePolynomialRing<ModInteger>(fac, nvars, tord, vars);
242            parsedPoly = polyType.PolModInt;
243            break;
244        case BigC:
245            spfac = new GenSolvablePolynomialRing<BigComplex>(fac, nvars, tord, vars);
246            parsedPoly = polyType.PolBigC;
247            break;
248        case BigQ:
249            spfac = new GenSolvablePolynomialRing<BigQuaternion>(fac, nvars, tord, vars);
250            parsedPoly = polyType.PolBigQ;
251            break;
252        case BigD:
253            spfac = new GenSolvablePolynomialRing<BigDecimal>(fac, nvars, tord, vars);
254            parsedPoly = polyType.PolBigD;
255            break;
256        case IntFunc:
257            spfac = new GenSolvablePolynomialRing<GenPolynomial<BigRational>>(fac, nvars, tord, vars);
258            parsedPoly = polyType.PolIntFunc;
259            break;
260        default:
261            spfac = new GenSolvablePolynomialRing<BigRational>(fac, nvars, tord, vars);
262            parsedPoly = polyType.PolBigRat;
263        }
264    }
265
266
267    /**
268     * Parsing method for GenPolynomial. syntax ? (simple)
269     * @return the next polynomial.
270     * @throws IOException
271     */
272    @SuppressWarnings("unchecked")
273    public GenPolynomial nextPolynomial() throws IOException {
274        if (debug) {
275            logger.debug("torder = " + tord);
276        }
277        GenPolynomial a = pfac.getZERO();
278        GenPolynomial a1 = pfac.getONE();
279        ExpVector leer = pfac.evzero;
280
281        if (debug) {
282            logger.debug("a = " + a);
283            logger.debug("a1 = " + a1);
284        }
285        GenPolynomial b = a1;
286        GenPolynomial c;
287        int tt; //, oldtt;
288        //String rat = "";
289        char first;
290        RingElem r;
291        ExpVector e;
292        int ix;
293        long ie;
294        boolean done = false;
295        while (!done) {
296            // next input. determine next action
297            tt = tok.nextToken();
298            //System.out.println("while tt = " + tok);
299            logger.debug("while tt = " + tok);
300            if (tt == StreamTokenizer.TT_EOF)
301                break;
302            switch (tt) {
303            case ')':
304            case ',':
305                return a; // do not change or remove
306            case '-':
307                b = b.negate();
308            case '+':
309            case '*':
310                tt = tok.nextToken();
311                break;
312            default: // skip
313            }
314            // read coefficient, monic monomial and polynomial
315            if (tt == StreamTokenizer.TT_EOF)
316                break;
317            switch (tt) {
318            // case '_': removed 
319            case '}':
320                throw new InvalidExpressionException("mismatch of braces after " + a + ", error at " + b);
321            case '{': // recursion
322                StringBuffer rf = new StringBuffer();
323                int level = 0;
324                do {
325                    tt = tok.nextToken();
326                    //System.out.println("token { = " + ((char)tt) + ", " + tt + ", level = " + level);
327                    if (tt == StreamTokenizer.TT_EOF) {
328                        throw new InvalidExpressionException("mismatch of braces after " + a + ", error at "
329                                        + b);
330                    }
331                    if (tt == '{') {
332                        level++;
333                    }
334                    if (tt == '}') {
335                        level--;
336                        if (level < 0) {
337                            continue; // skip last closing brace 
338                        }
339                    }
340                    if (tok.sval != null) {
341                        if (rf.length() > 0 && rf.charAt(rf.length() - 1) != '.') {
342                            rf.append(" ");
343                        }
344                        rf.append(tok.sval); // " " + 
345                    } else {
346                        rf.append((char) tt);
347                    }
348                } while (level >= 0);
349                //System.out.println("coeff{} = " + rf.toString() );
350                try {
351                    r = (RingElem) fac.parse(rf.toString());
352                } catch (NumberFormatException re) {
353                    throw new InvalidExpressionException("not a number " + rf, re);
354                }
355                if (debug)
356                    logger.debug("coeff " + r);
357                ie = nextExponent();
358                if (debug)
359                    logger.debug("ie " + ie);
360                r = Power.<RingElem> positivePower(r, ie);
361                if (debug)
362                    logger.debug("coeff^ie " + r);
363                b = b.multiply(r, leer);
364                tt = tok.nextToken();
365                if (debug)
366                    logger.debug("tt,digit = " + tok);
367                //no break;
368                break;
369
370            case StreamTokenizer.TT_WORD:
371                //System.out.println("TT_WORD: " + tok.sval);
372                if (tok.sval == null || tok.sval.length() == 0)
373                    break;
374                // read coefficient
375                first = tok.sval.charAt(0);
376                if (digit(first)) {
377                    //System.out.println("coeff 0 = " + tok.sval );
378                    StringBuffer df = new StringBuffer();
379                    df.append(tok.sval);
380                    if (tok.sval.charAt(tok.sval.length() - 1) == 'i') { // complex number
381                        tt = tok.nextToken();
382                        if (debug)
383                            logger.debug("tt,im = " + tok);
384                        if (tok.sval != null || tt == '-') {
385                            if (tok.sval != null) {
386                                df.append(tok.sval);
387                            } else {
388                                df.append("-");
389                            }
390                            if (tt == '-') {
391                                tt = tok.nextToken(); // todo: decimal number
392                                if (tok.sval != null && digit(tok.sval.charAt(0))) {
393                                    df.append(tok.sval);
394
395                                } else {
396                                    tok.pushBack();
397                                }
398                            }
399                        } else {
400                            tok.pushBack();
401                        }
402                    }
403                    tt = tok.nextToken();
404                    if (tt == '.') { // decimal number
405                        tt = tok.nextToken();
406                        if (debug)
407                            logger.debug("tt,dot = " + tok);
408                        if (tok.sval != null) {
409                            df.append(".");
410                            df.append(tok.sval);
411                        } else {
412                            tok.pushBack();
413                            tok.pushBack();
414                        }
415                    } else {
416                        tok.pushBack();
417                    }
418                    try {
419                        r = (RingElem) fac.parse(df.toString());
420                    } catch (NumberFormatException re) {
421                        throw new InvalidExpressionException("not a number " + df, re);
422                    }
423                    if (debug)
424                        logger.debug("coeff " + r);
425                    //System.out.println("r = " + r.toScriptFactory());
426                    ie = nextExponent();
427                    if (debug)
428                        logger.debug("ie " + ie);
429                    // r = r^ie;
430                    r = Power.<RingElem> positivePower(r, ie);
431                    if (debug)
432                        logger.debug("coeff^ie " + r);
433                    b = b.multiply(r, leer);
434                    tt = tok.nextToken();
435                    if (debug)
436                        logger.debug("tt,digit = " + tok);
437                }
438                if (tt == StreamTokenizer.TT_EOF)
439                    break;
440                if (tok.sval == null)
441                    break;
442                // read monomial or recursion 
443                first = tok.sval.charAt(0);
444                if (letter(first)) {
445                    ix = leer.indexVar(tok.sval, vars); //indexVar( tok.sval );
446                    if (ix < 0) { // not found
447                        try {
448                            r = (RingElem) fac.parse(tok.sval);
449                        } catch (NumberFormatException re) {
450                            throw new InvalidExpressionException("recursively unknown variable " + tok.sval);
451                        }
452                        if (debug)
453                            logger.info("coeff " + r);
454                        //if (r.isONE() || r.isZERO()) {
455                        //logger.error("Unknown varibable " + tok.sval);
456                        //done = true;
457                        //break;
458                        //throw new InvalidExpressionException("recursively unknown variable " + tok.sval);
459                        //}
460                        ie = nextExponent();
461                        //  System.out.println("ie: " + ie);
462                        r = Power.<RingElem> positivePower(r, ie);
463                        b = b.multiply(r);
464                    } else { // found
465                        //  System.out.println("ix: " + ix);
466                        ie = nextExponent();
467                        //  System.out.println("ie: " + ie);
468                        e = ExpVector.create(vars.length, ix, ie);
469                        b = b.multiply(e);
470                    }
471                    tt = tok.nextToken();
472                    if (debug)
473                        logger.debug("tt,letter = " + tok);
474                }
475                break;
476
477            case '(':
478                c = nextPolynomial();
479                if (debug)
480                    logger.debug("factor " + c);
481                ie = nextExponent();
482                if (debug)
483                    logger.debug("ie " + ie);
484                c = Power.<GenPolynomial> positivePower(c, ie);
485                if (debug)
486                    logger.debug("factor^ie " + c);
487                b = b.multiply(c);
488                tt = tok.nextToken();
489                if (debug)
490                    logger.debug("tt,digit = " + tok);
491                //no break;
492                break;
493
494            default: //skip 
495            }
496            if (done)
497                break; // unknown variable
498            if (tt == StreamTokenizer.TT_EOF)
499                break;
500            // complete polynomial
501            tok.pushBack();
502            switch (tt) {
503            case '-':
504            case '+':
505            case ')':
506            case ',':
507                logger.debug("b, = " + b);
508                a = a.sum(b);
509                b = a1;
510                break;
511            case '*':
512                logger.debug("b, = " + b);
513                //a = a.sum(b); 
514                //b = a1;
515                break;
516            case '\n':
517                tt = tok.nextToken();
518                if (debug)
519                    logger.debug("tt,nl = " + tt);
520                break;
521            default: // skip or finish ?
522                if (debug)
523                    logger.debug("default: " + tok);
524            }
525        }
526        if (debug)
527            logger.debug("b = " + b);
528        a = a.sum(b);
529        logger.debug("a = " + a);
530        // b = a1;
531        return a;
532    }
533
534
535    /**
536     * Parsing method for exponent (of variable). syntax: ^long | **long.
537     * @return the next exponent or 1.
538     * @throws IOException
539     */
540    public long nextExponent() throws IOException {
541        long e = 1;
542        char first;
543        int tt;
544        tt = tok.nextToken();
545        if (tt == '^') {
546            if (debug)
547                logger.debug("exponent ^");
548            tt = tok.nextToken();
549            if (tok.sval != null) {
550                first = tok.sval.charAt(0);
551                if (digit(first)) {
552                    e = Long.parseLong(tok.sval);
553                    return e;
554                }
555            }
556        }
557        if (tt == '*') {
558            tt = tok.nextToken();
559            if (tt == '*') {
560                if (debug)
561                    logger.debug("exponent **");
562                tt = tok.nextToken();
563                if (tok.sval != null) {
564                    first = tok.sval.charAt(0);
565                    if (digit(first)) {
566                        e = Long.parseLong(tok.sval);
567                        return e;
568                    }
569                }
570            }
571            tok.pushBack();
572        }
573        tok.pushBack();
574        return e;
575    }
576
577
578    /**
579     * Parsing method for comments. syntax: (* comment *) | /_* comment *_/
580     * without _ Does not work with this pushBack(), unused.
581     */
582    public String nextComment() throws IOException {
583        // syntax: (* comment *) | /* comment */ 
584        StringBuffer c = new StringBuffer();
585        int tt;
586        if (debug)
587            logger.debug("comment: " + tok);
588        tt = tok.nextToken();
589        if (debug)
590            logger.debug("comment: " + tok);
591        if (tt == '(') {
592            tt = tok.nextToken();
593            if (debug)
594                logger.debug("comment: " + tok);
595            if (tt == '*') {
596                if (debug)
597                    logger.debug("comment: ");
598                while (true) {
599                    tt = tok.nextToken();
600                    if (tt == '*') {
601                        tt = tok.nextToken();
602                        if (tt == ')') {
603                            return c.toString();
604                        }
605                        tok.pushBack();
606                    }
607                    c.append(tok.sval);
608                }
609            }
610            tok.pushBack();
611            if (debug)
612                logger.debug("comment: " + tok);
613        }
614        tok.pushBack();
615        if (debug)
616            logger.debug("comment: " + tok);
617        return c.toString();
618    }
619
620
621    /**
622     * Parsing method for variable list. syntax: (a, b c, de) gives [ "a", "b",
623     * "c", "de" ]
624     * @return the next variable list.
625     * @throws IOException
626     */
627    public String[] nextVariableList() throws IOException {
628        List<String> l = new ArrayList<String>();
629        int tt;
630        tt = tok.nextToken();
631        //System.out.println("vList tok = " + tok);
632        if (tt == '(' || tt == '{') {
633            logger.debug("variable list");
634            tt = tok.nextToken();
635            while (true) {
636                if (tt == StreamTokenizer.TT_EOF)
637                    break;
638                if (tt == ')' || tt == '}')
639                    break;
640                if (tt == StreamTokenizer.TT_WORD) {
641                    //System.out.println("TT_WORD: " + tok.sval);
642                    l.add(tok.sval);
643                }
644                tt = tok.nextToken();
645            }
646        }
647        Object[] ol = l.toArray();
648        String[] v = new String[ol.length];
649        for (int i = 0; i < v.length; i++) {
650            v[i] = (String) ol[i];
651        }
652        return v;
653    }
654
655
656    /**
657     * Parsing method for coefficient ring. syntax: Rat | Q | Int | Z | Mod
658     * modul | Complex | C | D | Quat | AN[ (var) ( poly ) ] | AN[ modul (var) (
659     * poly ) ] | IntFunc (var_list)
660     * @return the next coefficient factory.
661     * @throws IOException
662     */
663    @SuppressWarnings("unchecked")
664    public RingFactory nextCoefficientRing() throws IOException {
665        RingFactory coeff = null;
666        coeffType ct = null;
667        int tt;
668        tt = tok.nextToken();
669        if (tok.sval != null) {
670            if (tok.sval.equalsIgnoreCase("Q")) {
671                coeff = new BigRational(0);
672                ct = coeffType.BigRat;
673            } else if (tok.sval.equalsIgnoreCase("Rat")) {
674                coeff = new BigRational(0);
675                ct = coeffType.BigRat;
676            } else if (tok.sval.equalsIgnoreCase("D")) {
677                coeff = new BigDecimal(0);
678                ct = coeffType.BigD;
679            } else if (tok.sval.equalsIgnoreCase("Z")) {
680                coeff = new BigInteger(0);
681                ct = coeffType.BigInt;
682            } else if (tok.sval.equalsIgnoreCase("Int")) {
683                coeff = new BigInteger(0);
684                ct = coeffType.BigInt;
685            } else if (tok.sval.equalsIgnoreCase("C")) {
686                coeff = new BigComplex(0);
687                ct = coeffType.BigC;
688            } else if (tok.sval.equalsIgnoreCase("Complex")) {
689                coeff = new BigComplex(0);
690                ct = coeffType.BigC;
691            } else if (tok.sval.equalsIgnoreCase("Quat")) {
692                coeff = new BigQuaternion(0);
693                ct = coeffType.BigQ;
694            } else if (tok.sval.equalsIgnoreCase("Mod")) {
695                tt = tok.nextToken();
696                boolean openb = false;
697                if (tt == '[') { // optional
698                    openb = true;
699                    tt = tok.nextToken();
700                }
701                if (tok.sval != null && tok.sval.length() > 0) {
702                    if (digit(tok.sval.charAt(0))) {
703                        BigInteger mo = new BigInteger(tok.sval);
704                        BigInteger lm = new BigInteger(ModLongRing.MAX_LONG); //wrong: Long.MAX_VALUE);
705                        if (mo.compareTo(lm) < 0) {
706                            coeff = new ModLongRing(mo.getVal());
707                        } else {
708                            coeff = new ModIntegerRing(mo.getVal());
709                        }
710                        //System.out.println("coeff = " + coeff + " :: " + coeff.getClass());
711                        ct = coeffType.ModInt;
712                    } else {
713                        tok.pushBack();
714                    }
715                } else {
716                    tok.pushBack();
717                }
718                if (tt == ']' && openb) { // optional
719                    tt = tok.nextToken();
720                }
721            } else if (tok.sval.equalsIgnoreCase("RatFunc") || tok.sval.equalsIgnoreCase("ModFunc")) {
722                //logger.error("RatFunc and ModFunc can no more be read, see edu.jas.application.RingFactoryTokenizer.");
723                throw new InvalidExpressionException(
724                                "RatFunc and ModFunc can no more be read, see edu.jas.application.RingFactoryTokenizer.");
725            } else if (tok.sval.equalsIgnoreCase("IntFunc")) {
726                String[] rfv = nextVariableList();
727                //System.out.println("rfv = " + rfv.length + " " + rfv[0]);
728                int vr = rfv.length;
729                BigRational bi = new BigRational();
730                TermOrder to = new TermOrder(TermOrder.INVLEX);
731                GenPolynomialRing<BigRational> pcf = new GenPolynomialRing<BigRational>(bi, vr, to, rfv);
732                coeff = pcf;
733                ct = coeffType.IntFunc;
734            } else if (tok.sval.equalsIgnoreCase("AN")) {
735                tt = tok.nextToken();
736                if (tt == '[') {
737                    tt = tok.nextToken();
738                    RingFactory tcfac = new ModIntegerRing("19");
739                    if (tok.sval != null && tok.sval.length() > 0) {
740                        if (digit(tok.sval.charAt(0))) {
741                            tcfac = new ModIntegerRing(tok.sval);
742                        } else {
743                            tcfac = new BigRational();
744                            tok.pushBack();
745                        }
746                    } else {
747                        tcfac = new BigRational();
748                        tok.pushBack();
749                    }
750                    String[] anv = nextVariableList();
751                    //System.out.println("anv = " + anv.length + " " + anv[0]);
752                    int vs = anv.length;
753                    if (vs != 1) {
754                        throw new InvalidExpressionException(
755                                        "AlgebraicNumber only for univariate polynomials "
756                                                        + Arrays.toString(anv));
757                    }
758                    String[] ovars = vars;
759                    vars = anv;
760                    GenPolynomialRing tpfac = pfac;
761                    RingFactory tfac = fac;
762                    fac = tcfac;
763                    // pfac and fac used in nextPolynomial()
764                    if (tcfac instanceof ModIntegerRing) {
765                        pfac = new GenPolynomialRing<ModInteger>(tcfac, vs, new TermOrder(), anv);
766                    } else {
767                        pfac = new GenPolynomialRing<BigRational>(tcfac, vs, new TermOrder(), anv);
768                    }
769                    if (debug) {
770                        logger.debug("pfac = " + pfac);
771                    }
772                    tt = tok.nextToken();
773                    GenPolynomial mod;
774                    if (tt == '(') {
775                        mod = nextPolynomial();
776                        tt = tok.nextToken();
777                        if (tok.ttype != ')')
778                            tok.pushBack();
779                    } else {
780                        tok.pushBack();
781                        mod = nextPolynomial();
782                    }
783                    if (debug) {
784                        logger.debug("mod = " + mod);
785                    }
786                    pfac = tpfac;
787                    fac = tfac;
788                    vars = ovars;
789                    if (tcfac instanceof ModIntegerRing) {
790                        GenPolynomial<ModInteger> gfmod;
791                        gfmod = (GenPolynomial<ModInteger>) mod;
792                        coeff = new AlgebraicNumberRing<ModInteger>(gfmod);
793                        ct = coeffType.ANmod;
794                    } else {
795                        GenPolynomial<BigRational> anmod;
796                        anmod = (GenPolynomial<BigRational>) mod;
797                        coeff = new AlgebraicNumberRing<BigRational>(anmod);
798                        ct = coeffType.ANrat;
799                    }
800                    if (debug) {
801                        logger.debug("coeff = " + coeff);
802                    }
803                    tt = tok.nextToken();
804                    if (tt == ']') {
805                        //ok, no nextToken();
806                    } else {
807                        tok.pushBack();
808                    }
809                } else {
810                    tok.pushBack();
811                }
812            }
813        }
814        if (coeff == null) {
815            tok.pushBack();
816            coeff = new BigRational();
817            ct = coeffType.BigRat;
818        }
819        parsedCoeff = ct;
820        return coeff;
821    }
822
823
824    /**
825     * Parsing method for weight list. syntax: (w1, w2, w3, ..., wn)
826     * @return the next weight list.
827     * @throws IOException
828     */
829    public long[] nextWeightList() throws IOException {
830        List<Long> l = new ArrayList<Long>();
831        long[] w = null;
832        long e;
833        char first;
834        int tt;
835        tt = tok.nextToken();
836        if (tt == '(') {
837            logger.debug("weight list");
838            tt = tok.nextToken();
839            while (true) {
840                if (tt == StreamTokenizer.TT_EOF)
841                    break;
842                if (tt == ')')
843                    break;
844                if (tok.sval != null) {
845                    first = tok.sval.charAt(0);
846                    if (digit(first)) {
847                        e = Long.parseLong(tok.sval);
848                        l.add(Long.valueOf(e));
849                        //System.out.println("w: " + e);
850                    }
851                }
852                tt = tok.nextToken(); // also comma
853            }
854        }
855        Object[] ol = l.toArray();
856        w = new long[ol.length];
857        for (int i = 0; i < w.length; i++) {
858            w[i] = ((Long) ol[ol.length - i - 1]).longValue();
859        }
860        return w;
861    }
862
863
864    /**
865     * Parsing method for weight array. syntax: ( (w11, ...,w1n), ..., (wm1,
866     * ..., wmn) )
867     * @return the next weight array.
868     * @throws IOException
869     */
870    public long[][] nextWeightArray() throws IOException {
871        List<long[]> l = new ArrayList<long[]>();
872        long[][] w = null;
873        long[] e;
874        char first;
875        int tt;
876        tt = tok.nextToken();
877        if (tt == '(') {
878            logger.debug("weight array");
879            tt = tok.nextToken();
880            while (true) {
881                if (tt == StreamTokenizer.TT_EOF)
882                    break;
883                if (tt == ')')
884                    break;
885                if (tt == '(') {
886                    tok.pushBack();
887                    e = nextWeightList();
888                    l.add(e);
889                    //System.out.println("wa: " + e);
890                } else if (tok.sval != null) {
891                    first = tok.sval.charAt(0);
892                    if (digit(first)) {
893                        tok.pushBack();
894                        tok.pushBack();
895                        e = nextWeightList();
896                        l.add(e);
897                        break;
898                        //System.out.println("w: " + e);
899                    }
900                }
901                tt = tok.nextToken(); // also comma
902            }
903        }
904        Object[] ol = l.toArray();
905        w = new long[ol.length][];
906        for (int i = 0; i < w.length; i++) {
907            w[i] = (long[]) ol[i];
908        }
909        return w;
910    }
911
912
913    /**
914     * Parsing method for split index. syntax: |i|
915     * @return the next split index.
916     * @throws IOException
917     */
918    public int nextSplitIndex() throws IOException {
919        int e = -1; // =unknown
920        int e0 = -1; // =unknown
921        char first;
922        int tt;
923        tt = tok.nextToken();
924        if (tt == '|') {
925            logger.debug("split index");
926            tt = tok.nextToken();
927            if (tt == StreamTokenizer.TT_EOF) {
928                return e;
929            }
930            if (tok.sval != null) {
931                first = tok.sval.charAt(0);
932                if (digit(first)) {
933                    e = Integer.parseInt(tok.sval);
934                    //System.out.println("w: " + i);
935                }
936                tt = tok.nextToken();
937                if (tt != '|') {
938                    tok.pushBack();
939                }
940            }
941        } else if (tt == '[') {
942            logger.debug("split index");
943            tt = tok.nextToken();
944            if (tt == StreamTokenizer.TT_EOF) {
945                return e;
946            }
947            if (tok.sval != null) {
948                first = tok.sval.charAt(0);
949                if (digit(first)) {
950                    e0 = Integer.parseInt(tok.sval);
951                    //System.out.println("w: " + i);
952                }
953                tt = tok.nextToken();
954                if (tt == ',') {
955                    tt = tok.nextToken();
956                    if (tt == StreamTokenizer.TT_EOF) {
957                        return e0;
958                    }
959                    if (tok.sval != null) {
960                        first = tok.sval.charAt(0);
961                        if (digit(first)) {
962                            e = Integer.parseInt(tok.sval);
963                            //System.out.println("w: " + i);
964                        }
965                    }
966                    if (tt != ']') {
967                        tok.pushBack();
968                    }
969                }
970            }
971        } else {
972            tok.pushBack();
973        }
974        return e;
975    }
976
977
978    /**
979     * Parsing method for term order name. syntax: termOrderName = L, IL, LEX,
980     * G, IG, GRLEX, W(weights) |split index|
981     * @return the next term order.
982     * @throws IOException
983     */
984    public TermOrder nextTermOrder() throws IOException {
985        int evord = TermOrder.DEFAULT_EVORD;
986        int tt;
987        tt = tok.nextToken();
988        if (tt == StreamTokenizer.TT_EOF) { /* nop */
989        } else if (tt == StreamTokenizer.TT_WORD) {
990            // System.out.println("TT_WORD: " + tok.sval);
991            if (tok.sval != null) {
992                if (tok.sval.equalsIgnoreCase("L")) {
993                    evord = TermOrder.INVLEX;
994                } else if (tok.sval.equalsIgnoreCase("IL")) {
995                    evord = TermOrder.INVLEX;
996                } else if (tok.sval.equalsIgnoreCase("INVLEX")) {
997                    evord = TermOrder.INVLEX;
998                } else if (tok.sval.equalsIgnoreCase("LEX")) {
999                    evord = TermOrder.LEX;
1000                } else if (tok.sval.equalsIgnoreCase("G")) {
1001                    evord = TermOrder.IGRLEX;
1002                } else if (tok.sval.equalsIgnoreCase("IG")) {
1003                    evord = TermOrder.IGRLEX;
1004                } else if (tok.sval.equalsIgnoreCase("IGRLEX")) {
1005                    evord = TermOrder.IGRLEX;
1006                } else if (tok.sval.equalsIgnoreCase("GRLEX")) {
1007                    evord = TermOrder.GRLEX;
1008                } else if (tok.sval.equalsIgnoreCase("W")) {
1009                    long[][] w = nextWeightArray();
1010                    //int s = nextSplitIndex(); // no more
1011                    return new TermOrder(w);
1012                }
1013            }
1014        }
1015        int s = nextSplitIndex();
1016        if (s <= 0) {
1017            return new TermOrder(evord);
1018        }
1019        return new TermOrder(evord, evord, vars.length, s);
1020    }
1021
1022
1023    /**
1024     * Parsing method for polynomial list. syntax: ( p1, p2, p3, ..., pn )
1025     * @return the next polynomial list.
1026     * @throws IOException
1027     */
1028    public List<GenPolynomial> nextPolynomialList() throws IOException {
1029        GenPolynomial a;
1030        List<GenPolynomial> L = new ArrayList<GenPolynomial>();
1031        int tt;
1032        tt = tok.nextToken();
1033        if (tt == StreamTokenizer.TT_EOF)
1034            return L;
1035        if (tt != '(')
1036            return L;
1037        logger.debug("polynomial list");
1038        while (true) {
1039            tt = tok.nextToken();
1040            if (tok.ttype == ',')
1041                continue;
1042            if (tt == '(') {
1043                a = nextPolynomial();
1044                tt = tok.nextToken();
1045                if (tok.ttype != ')')
1046                    tok.pushBack();
1047            } else {
1048                tok.pushBack();
1049                a = nextPolynomial();
1050            }
1051            logger.info("next pol = " + a);
1052            L.add(a);
1053            if (tok.ttype == StreamTokenizer.TT_EOF)
1054                break;
1055            if (tok.ttype == ')')
1056                break;
1057        }
1058        return L;
1059    }
1060
1061
1062    /**
1063     * Parsing method for submodule list. syntax: ( ( p11, p12, p13, ..., p1n ),
1064     * ..., ( pm1, pm2, pm3, ..., pmn ) )
1065     * @return the next list of polynomial lists.
1066     * @throws IOException
1067     */
1068    public List<List<GenPolynomial>> nextSubModuleList() throws IOException {
1069        List<List<GenPolynomial>> L = new ArrayList<List<GenPolynomial>>();
1070        int tt;
1071        tt = tok.nextToken();
1072        if (tt == StreamTokenizer.TT_EOF)
1073            return L;
1074        if (tt != '(')
1075            return L;
1076        logger.debug("module list");
1077        List<GenPolynomial> v = null;
1078        while (true) {
1079            tt = tok.nextToken();
1080            if (tok.ttype == ',')
1081                continue;
1082            if (tok.ttype == ')')
1083                break;
1084            if (tok.ttype == StreamTokenizer.TT_EOF)
1085                break;
1086            if (tt == '(') {
1087                tok.pushBack();
1088                v = nextPolynomialList();
1089                logger.info("next vect = " + v);
1090                L.add(v);
1091            }
1092        }
1093        return L;
1094    }
1095
1096
1097    /**
1098     * Parsing method for solvable polynomial relation table. syntax: ( p_1,
1099     * p_2, p_3, ..., p_{n+3} ) semantics: p_{n+1} * p_{n+2} = p_{n+3} The next
1100     * relation table is stored into the solvable polynomial factory.
1101     * @throws IOException
1102     */
1103    @SuppressWarnings("unchecked")
1104    public void nextRelationTable() throws IOException {
1105        if (spfac == null) {
1106            return;
1107        }
1108        RelationTable table = spfac.table;
1109        List<GenPolynomial> rels = null;
1110        GenPolynomial p;
1111        GenSolvablePolynomial sp;
1112        int tt;
1113        tt = tok.nextToken();
1114        if (debug) {
1115            logger.debug("relation table: " + tt);
1116        }
1117        if (tok.sval != null) {
1118            if (tok.sval.equalsIgnoreCase("RelationTable")) {
1119                rels = nextPolynomialList();
1120            }
1121        }
1122        if (rels == null) {
1123            tok.pushBack();
1124            return;
1125        }
1126        for (Iterator<GenPolynomial> it = rels.iterator(); it.hasNext();) {
1127            p = it.next();
1128            ExpVector e = p.leadingExpVector();
1129            if (it.hasNext()) {
1130                p = it.next();
1131                ExpVector f = p.leadingExpVector();
1132                if (it.hasNext()) {
1133                    p = it.next();
1134                    sp = new GenSolvablePolynomial(spfac, p.val);
1135                    table.update(e, f, sp);
1136                }
1137            }
1138        }
1139        if (debug) {
1140            logger.info("table = " + table);
1141        }
1142        return;
1143    }
1144
1145
1146    /**
1147     * Parsing method for polynomial set. syntax: coeffRing varList
1148     * termOrderName polyList.
1149     * @return the next polynomial set.
1150     * @throws IOException
1151     */
1152    @SuppressWarnings("unchecked")
1153    public PolynomialList nextPolynomialSet() throws IOException {
1154        //String comments = "";
1155        //comments += nextComment();
1156        //if (debug) logger.debug("comment = " + comments);
1157
1158        RingFactory coeff = nextCoefficientRing();
1159        logger.info("coeff = " + coeff);
1160
1161        vars = nextVariableList();
1162        logger.info("vars = " + Arrays.toString(vars));
1163        if (vars != null) {
1164            nvars = vars.length;
1165        }
1166
1167        tord = nextTermOrder();
1168        logger.info("tord = " + tord);
1169        // check more TOs
1170
1171        initFactory(coeff, parsedCoeff); // global: nvars, tord, vars
1172        List<GenPolynomial> s = null;
1173        s = nextPolynomialList();
1174        logger.info("s = " + s);
1175        // comments += nextComment();
1176        return new PolynomialList(pfac, s);
1177    }
1178
1179
1180    /**
1181     * Parsing method for module set. syntax: coeffRing varList termOrderName
1182     * moduleList.
1183     * @return the next module set.
1184     * @throws IOException
1185     */
1186    @SuppressWarnings("unchecked")
1187    public ModuleList nextSubModuleSet() throws IOException {
1188        //String comments = "";
1189        //comments += nextComment();
1190        //if (debug) logger.debug("comment = " + comments);
1191
1192        RingFactory coeff = nextCoefficientRing();
1193        logger.info("coeff = " + coeff);
1194
1195        vars = nextVariableList();
1196        logger.info("vars = " + Arrays.toString(vars));
1197        if (vars != null) {
1198            nvars = vars.length;
1199        }
1200
1201        tord = nextTermOrder();
1202        logger.info("tord = " + tord);
1203        // check more TOs
1204
1205        initFactory(coeff, parsedCoeff); // global: nvars, tord, vars
1206        List<List<GenPolynomial>> m = null;
1207        m = nextSubModuleList();
1208        logger.info("m = " + m);
1209        // comments += nextComment();
1210
1211        return new ModuleList(pfac, m);
1212    }
1213
1214
1215    /**
1216     * Parsing method for solvable polynomial list. syntax: ( p1, p2, p3, ...,
1217     * pn )
1218     * @return the next solvable polynomial list.
1219     * @throws IOException
1220     */
1221    @SuppressWarnings("unchecked")
1222    public List<GenSolvablePolynomial> nextSolvablePolynomialList() throws IOException {
1223        List<GenPolynomial> s = nextPolynomialList();
1224        logger.info("s = " + s);
1225        // comments += nextComment();
1226
1227        GenPolynomial p;
1228        GenSolvablePolynomial ps;
1229        List<GenSolvablePolynomial> sp = new ArrayList<GenSolvablePolynomial>(s.size());
1230        for (Iterator<GenPolynomial> it = s.iterator(); it.hasNext();) {
1231            p = it.next();
1232            ps = new GenSolvablePolynomial(spfac, p.val);
1233            //System.out.println("ps = " + ps);
1234            sp.add(ps);
1235        }
1236        return sp;
1237    }
1238
1239
1240    /**
1241     * Parsing method for solvable polynomial. syntax: p.
1242     * @return the next polynomial.
1243     * @throws IOException
1244     */
1245    @SuppressWarnings("unchecked")
1246    public GenSolvablePolynomial nextSolvablePolynomial() throws IOException {
1247        GenPolynomial p = nextPolynomial();
1248        logger.info("p = " + p);
1249        // comments += nextComment();
1250
1251        GenSolvablePolynomial ps = new GenSolvablePolynomial(spfac, p.val);
1252        //System.out.println("ps = " + ps);
1253        return ps;
1254    }
1255
1256
1257    /**
1258     * Parsing method for solvable polynomial set. syntax: varList termOrderName
1259     * relationTable polyList.
1260     * @return the next solvable polynomial set.
1261     * @throws IOException
1262     */
1263
1264    @SuppressWarnings("unchecked")
1265    public PolynomialList nextSolvablePolynomialSet() throws IOException {
1266        //String comments = "";
1267        //comments += nextComment();
1268        //if (debug) logger.debug("comment = " + comments);
1269
1270        RingFactory coeff = nextCoefficientRing();
1271        logger.info("coeff = " + coeff);
1272
1273        vars = nextVariableList();
1274        logger.info("vars = " + Arrays.toString(vars));
1275        if (vars != null) {
1276            nvars = vars.length;
1277        }
1278
1279        tord = nextTermOrder();
1280        logger.info("tord = " + tord);
1281        // check more TOs
1282
1283        initFactory(coeff, parsedCoeff); // must be because of symmetric read
1284        initSolvableFactory(coeff, parsedCoeff); // global: nvars, tord, vars
1285        //System.out.println("pfac = " + pfac);
1286        //System.out.println("spfac = " + spfac);
1287
1288        nextRelationTable();
1289        if (logger.isInfoEnabled()) {
1290            logger.info("table = " + table);
1291        }
1292
1293        List<GenSolvablePolynomial> s = null;
1294        s = nextSolvablePolynomialList();
1295        logger.info("s = " + s);
1296        // comments += nextComment();
1297        return new PolynomialList(spfac, s); // Ordered ?
1298    }
1299
1300
1301    /**
1302     * Parsing method for solvable submodule list. syntax: ( ( p11, p12, p13,
1303     * ..., p1n ), ..., ( pm1, pm2, pm3, ..., pmn ) )
1304     * @return the next list of solvable polynomial lists.
1305     * @throws IOException
1306     */
1307    public List<List<GenSolvablePolynomial>> nextSolvableSubModuleList() throws IOException {
1308        List<List<GenSolvablePolynomial>> L = new ArrayList<List<GenSolvablePolynomial>>();
1309        int tt;
1310        tt = tok.nextToken();
1311        if (tt == StreamTokenizer.TT_EOF)
1312            return L;
1313        if (tt != '(')
1314            return L;
1315        logger.debug("module list");
1316        List<GenSolvablePolynomial> v = null;
1317        while (true) {
1318            tt = tok.nextToken();
1319            if (tok.ttype == ',')
1320                continue;
1321            if (tok.ttype == ')')
1322                break;
1323            if (tok.ttype == StreamTokenizer.TT_EOF)
1324                break;
1325            if (tt == '(') {
1326                tok.pushBack();
1327                v = nextSolvablePolynomialList();
1328                logger.info("next vect = " + v);
1329                L.add(v);
1330            }
1331        }
1332        return L;
1333    }
1334
1335
1336    /**
1337     * Parsing method for solvable module set. syntax: varList termOrderName
1338     * relationTable moduleList.
1339     * @return the next solvable module set.
1340     * @throws IOException
1341     */
1342    @SuppressWarnings("unchecked")
1343    public ModuleList nextSolvableSubModuleSet() throws IOException {
1344        //String comments = "";
1345        //comments += nextComment();
1346        //if (debug) logger.debug("comment = " + comments);
1347
1348        RingFactory coeff = nextCoefficientRing();
1349        logger.info("coeff = " + coeff);
1350
1351        vars = nextVariableList();
1352        logger.info("vars = " + Arrays.toString(vars));
1353        if (vars != null) {
1354            nvars = vars.length;
1355        }
1356
1357        tord = nextTermOrder();
1358        logger.info("tord = " + tord);
1359        // check more TOs
1360
1361        initFactory(coeff, parsedCoeff); // must be because of symmetric read
1362        initSolvableFactory(coeff, parsedCoeff); // global: nvars, tord, vars
1363
1364        //System.out.println("spfac = " + spfac);
1365
1366        nextRelationTable();
1367        if (logger.isInfoEnabled()) {
1368            logger.info("table = " + table);
1369        }
1370
1371        List<List<GenSolvablePolynomial>> s = null;
1372        s = nextSolvableSubModuleList();
1373        logger.info("s = " + s);
1374        // comments += nextComment();
1375
1376        return new OrderedModuleList(spfac, s); // Ordered
1377    }
1378
1379
1380    // must also allow +/- // does not work with tokenizer
1381    //private static boolean number(char x) {
1382    //    return digit(x) || x == '-' || x == '+';
1383    //}
1384
1385
1386    private static boolean digit(char x) {
1387        return '0' <= x && x <= '9';
1388    }
1389
1390
1391    private static boolean letter(char x) {
1392        return ('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z');
1393    }
1394
1395
1396    // unused
1397    public void nextComma() throws IOException {
1398        int tt;
1399        if (tok.ttype == ',') {
1400            tt = tok.nextToken();
1401            if (debug) {
1402                logger.debug("after comma: " + tt);
1403            }
1404        }
1405    }
1406
1407
1408    /**
1409     * Parse variable list from String.
1410     * @param s String. Syntax: (n1,...,nk) or (n1 ... nk), parenthesis are also
1411     *            optional.
1412     * @return array of variable names found in s.
1413     */
1414    public static String[] variableList(String s) {
1415        String[] vl = null;
1416        if (s == null) {
1417            return vl;
1418        }
1419        String st = s.trim();
1420        if (st.length() == 0) {
1421            return new String[0];
1422        }
1423        if (st.charAt(0) == '(') {
1424            st = st.substring(1);
1425        }
1426        if (st.charAt(st.length() - 1) == ')') {
1427            st = st.substring(0, st.length() - 1);
1428        }
1429        st = st.replaceAll(",", " ");
1430        List<String> sl = new ArrayList<String>();
1431        Scanner sc = new Scanner(st);
1432        while (sc.hasNext()) {
1433            String sn = sc.next();
1434            sl.add(sn);
1435        }
1436        vl = new String[sl.size()];
1437        int i = 0;
1438        for (String si : sl) {
1439            vl[i] = si;
1440            i++;
1441        }
1442        return vl;
1443    }
1444
1445
1446    /**
1447     * Extract variable list from expression.
1448     * @param s String. Syntax: any polynomial expression.
1449     * @return array of variable names found in s.
1450     */
1451    public static String[] expressionVariables(String s) {
1452        String[] vl = null;
1453        if (s == null) {
1454            return vl;
1455        }
1456        String st = s.trim();
1457        if (st.length() == 0) {
1458            return new String[0];
1459        }
1460        st = st.replaceAll(",", " ");
1461        st = st.replaceAll("\\+", " ");
1462        st = st.replaceAll("-", " ");
1463        st = st.replaceAll("\\*", " ");
1464        st = st.replaceAll("/", " ");
1465        st = st.replaceAll("\\(", " ");
1466        st = st.replaceAll("\\)", " ");
1467        st = st.replaceAll("\\{", " ");
1468        st = st.replaceAll("\\}", " ");
1469        st = st.replaceAll("\\[", " ");
1470        st = st.replaceAll("\\]", " ");
1471        st = st.replaceAll("\\^", " ");
1472        //System.out.println("st = " + st);
1473
1474        Set<String> sl = new TreeSet<String>();
1475        Scanner sc = new Scanner(st);
1476        while (sc.hasNext()) {
1477            String sn = sc.next();
1478            if (sn == null || sn.length() == 0) {
1479                continue;
1480            }
1481            //System.out.println("sn = " + sn);
1482            int i = 0;
1483            while (digit(sn.charAt(i)) && i < sn.length() - 1) {
1484                i++;
1485            }
1486            //System.out.println("sn = " + sn + ", i = " + i);
1487            if (i > 0) {
1488                sn = sn.substring(i, sn.length());
1489            }
1490            //System.out.println("sn = " + sn);
1491            if (sn.length() == 0) {
1492                continue;
1493            }
1494            if (!letter(sn.charAt(0))) {
1495                continue;
1496            }
1497            //System.out.println("sn = " + sn);
1498            sl.add(sn);
1499        }
1500        vl = new String[sl.size()];
1501        int i = 0;
1502        for (String si : sl) {
1503            vl[i] = si;
1504            i++;
1505        }
1506        return vl;
1507    }
1508
1509}