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