001 /*
002 * $Id: RelationTable.java 3297 2010-08-26 19:09:03Z kredel $
003 */
004
005 package edu.jas.poly;
006
007 import java.util.List;
008 import java.util.ArrayList;
009 import java.util.LinkedList;
010 import java.util.Map;
011 import java.util.HashMap;
012 import java.util.Iterator;
013 import java.util.ListIterator;
014
015 import java.io.Serializable;
016
017 import org.apache.log4j.Logger;
018
019 import edu.jas.structure.RingElem;
020
021 import edu.jas.kern.PrettyPrint;
022
023
024 /**
025 * RelationTable for solvable polynomials.
026 * This class maintains the non-commutative multiplication
027 * relations of solvable polynomial rings.
028 * The table entries are initialized with relations of the
029 * form x<sub>j</sub> * x<sub>i</sub> = p<sub>ij</sub>.
030 * During multiplication the ralations are updated by relations
031 * of the form x<sub>j</sub><sup>k</sup> * x<sub>i</sub><sup>l</sup>
032 * = p<sub>ijkl</sub>.
033 * If no relation for x<sub>j</sub> * x<sub>i</sub> is found in
034 * the table, this multiplication is assumed to be commutative
035 * x<sub>i</sub> x<sub>j</sub>.
036 * @author Heinz Kredel
037 */
038
039 public class RelationTable<C extends RingElem<C>> implements Serializable {
040
041
042 /** The data structure for the relations.
043 */
044 public final Map< List<Integer>, List > table;
045
046
047 /** The factory for the solvable polynomial ring.
048 */
049 public final GenSolvablePolynomialRing<C> ring;
050
051
052 private static final Logger logger = Logger.getLogger(RelationTable.class);
053
054 private final boolean debug = true; //logger.isDebugEnabled();
055
056
057 /**
058 * Constructor for RelationTable requires ring factory.
059 * Note: This constructor is called within the constructor
060 * of the ring factory, so methods of this class can only be used
061 * after the other constructor has terminated.
062 * @param r solvable polynomial ring factory.
063 */
064 protected RelationTable(GenSolvablePolynomialRing<C> r) {
065 table = new HashMap< List<Integer>, List >();
066 ring = r;
067 if ( ring == null ) {
068 throw new IllegalArgumentException("RelationTable no ring");
069 }
070 }
071
072
073 /**
074 * RelationTable equals.
075 * Tests same keySets only, not relations itself.
076 * Will be improved in the future.
077 * @see java.lang.Object#equals(java.lang.Object)
078 */
079 @Override
080 @SuppressWarnings("unchecked") // not jet working
081 public boolean equals(Object p) {
082 if ( ! (p instanceof RelationTable) ) {
083 System.out.println("no RelationTable");
084 return false;
085 }
086 RelationTable< C > tab = null;
087 try {
088 tab = (RelationTable< C >)p;
089 } catch (ClassCastException ignored) {
090 }
091 if ( tab == null ) {
092 return false;
093 }
094 if ( ! ring.equals( tab.ring ) ) {
095 System.out.println("not same Ring " + ring.toScript() + ", " + tab.ring.toScript());
096 return false;
097 }
098 for ( List<Integer> k: table.keySet() ) {
099 List a = table.get(k);
100 List b = tab.table.get(k);
101 if ( b == null ) {
102 return false;
103 }
104 // check contents, but only base relations
105 if ( ! a.equals(b) ) {
106 return false;
107 }
108 }
109 for ( List<Integer> k: tab.table.keySet() ) {
110 List a = table.get(k);
111 List b = tab.table.get(k);
112 if ( a == null ) {
113 return false;
114 }
115 // check contents, but only base relations
116 if ( ! a.equals(b) ) {
117 return false;
118 }
119 }
120 return true;
121 }
122
123
124 /** Hash code for this relation table.
125 * @see java.lang.Object#hashCode()
126 */
127 @Override
128 public int hashCode() {
129 int h;
130 h = ring.hashCode();
131 h = 31 * h + table.hashCode();
132 return h;
133 }
134
135
136 /** Get the String representation.
137 * @see java.lang.Object#toString()
138 */
139 @Override
140 public String toString() {
141 List v;
142 StringBuffer s = new StringBuffer("RelationTable[");
143 boolean first = true;
144 for ( List<Integer> k: table.keySet() ) {
145 if ( first ) {
146 first = false;
147 } else {
148 s.append( ", " );
149 }
150 s.append( k.toString() );
151 v = table.get( k );
152 s.append("=");
153 s.append( v.toString() );
154 }
155 s.append("]");
156 return s.toString();
157 }
158
159
160 /** Get the String representation.
161 * @param vars names for the variables.
162 * @see java.lang.Object#toString()
163 */
164 @SuppressWarnings("unchecked")
165 public String toString(String[] vars) {
166 if ( vars == null ) {
167 return toString();
168 }
169 List v;
170 StringBuffer s = new StringBuffer("RelationTable\n(");
171 if ( PrettyPrint.isTrue() ) {
172 boolean first = true;
173 for ( List<Integer> k: table.keySet() ) {
174 if ( first ) {
175 first = false;
176 s.append( "\n" );
177 } else {
178 s.append( ",\n" );
179 }
180 v = table.get( k );
181 for (Iterator jt = v.iterator(); jt.hasNext(); ) {
182 ExpVectorPair ep = (ExpVectorPair)jt.next();
183 s.append("( " + ep.getFirst().toString(vars) + " ), " );
184 s.append("( " + ep.getSecond().toString(vars) + " ), " );
185 GenSolvablePolynomial<C> p
186 = (GenSolvablePolynomial<C>)jt.next();
187 s.append("( " + p.toString(vars) + " )" );
188 if ( jt.hasNext() ) {
189 s.append(",\n");
190 }
191 }
192 }
193 } else {
194 boolean first = true;
195 for ( List<Integer> k: table.keySet() ) {
196 if ( first ) {
197 first = false;
198 } else {
199 s.append( ",\n" );
200 }
201 v = table.get( k );
202 for (Iterator jt = v.iterator(); jt.hasNext(); ) {
203 ExpVectorPair ep = (ExpVectorPair)jt.next();
204 s.append("( " + ep.getFirst().toString(vars) + " ), " );
205 s.append("( " + ep.getSecond().toString(vars) + " ), " );
206 GenSolvablePolynomial<C> p
207 = (GenSolvablePolynomial<C>)jt.next();
208 s.append("( " + p.toString(vars) + " )" );
209 if ( jt.hasNext() ) {
210 s.append(",\n");
211 }
212 }
213 }
214 }
215 s.append("\n)\n");
216 return s.toString();
217 }
218
219
220 /** Get a scripting compatible string representation.
221 * @return script compatible representation for this relation table.
222 */
223 public String toScript() {
224 // Python case
225 String[] vars = ring.vars;
226 List v;
227 StringBuffer s = new StringBuffer("[");
228 boolean first = true;
229 for ( List<Integer> k: table.keySet() ) {
230 if ( first ) {
231 first = false;
232 s.append( "" );
233 } else {
234 s.append( ", " );
235 }
236 v = table.get( k );
237 for (Iterator jt = v.iterator(); jt.hasNext(); ) {
238 ExpVectorPair ep = (ExpVectorPair)jt.next();
239 s.append("" + ep.getFirst().toScript(vars) + ", " );
240 s.append("" + ep.getSecond().toScript(vars) + ", " );
241 GenPolynomial<C> p = (GenPolynomial<C>)jt.next();
242 s.append("( " + p.toScript() + " )" );
243 if ( jt.hasNext() ) {
244 s.append(", ");
245 }
246 }
247 }
248 s.append( "]" );
249 return s.toString();
250 }
251
252
253 /**
254 * Update or initialize RelationTable with new relation.
255 * relation is e * f = p.
256 * @param e first term.
257 * @param f second term.
258 * @param p solvable product polynomial.
259 */
260 @SuppressWarnings("unchecked")
261 public synchronized void
262 update(ExpVector e, ExpVector f, GenSolvablePolynomial<C> p) {
263 if ( debug ) {
264 //System.out.println("new relation = " + e + " .*. " + f + " = " + p);
265 if ( p != null && p.ring.vars != null ) {
266 logger.info("new relation = " + e.toString(p.ring.vars) + " .*. " + f.toString(p.ring.vars) + " = " + p);
267 //logger.info("existing relations = " + toString(p.ring.vars));
268 } else {
269 logger.info("new relation = " + e + " .*. " + f + " = " + p);
270 }
271 }
272 if ( p == null || e == null || f == null ) {
273 throw new IllegalArgumentException("RelationTable update e|f|p == null");
274 }
275 if ( debug ) {
276 if ( e.totalDeg() == 1 && f.totalDeg() == 1 ) {
277 int[] de = e.dependencyOnVariables();
278 int[] df = f.dependencyOnVariables();
279 logger.debug("update e ? f " + de[0] + " " + df[0]);
280 //int t = ring.tord.getDescendComparator().compare(e,f);
281 //System.out.println("update compare(e,f) = " + t);
282 if ( de[0] == df[0] ) { // error
283 throw new IllegalArgumentException("RelationTable update e==f");
284 }
285 if ( de[0] > df[0] ) { // invalid update
286 logger.error("warning: update e > f " + e + " " + f + " changed");
287 ExpVector tmp = e;
288 e = f;
289 f = tmp;
290 Map.Entry<ExpVector,C> m = p.leadingMonomial();
291 GenPolynomial<C> r = p.subtract( m.getValue(), m.getKey() );
292 r = r.negate();
293 p = (GenSolvablePolynomial<C>)r.sum( m.getValue(), m.getKey() );
294 }
295 }
296 }
297 ExpVector ef = e.sum(f);
298 ExpVector lp = p.leadingExpVector();
299 if ( ! ef.equals(lp) ) { // check for suitable term order
300 logger.error("relation term order = " + ring.tord);
301 throw new IllegalArgumentException("RelationTable update e*f != lt(p)");
302 }
303 List<Integer> key = makeKey(e,f);
304 ExpVectorPair evp = new ExpVectorPair( e, f );
305 if ( key.size() != 2 ) {
306 System.out.println("key = " + key + ", evp = " + evp);
307 }
308 List part = table.get( key );
309 if ( part == null ) { // initialization only
310 part = new LinkedList();
311 part.add( evp );
312 part.add( p );
313 table.put( key, part );
314 return;
315 }
316 Object o;
317 int index = -1;
318 synchronized(part) { // with lookup()
319 for ( ListIterator it = part.listIterator(); it.hasNext(); ) {
320 ExpVectorPair look = (ExpVectorPair)it.next();
321 o = it.next(); // skip poly
322 if ( look.isMultiple( evp ) ) {
323 index = it.nextIndex();
324 // last index of or first index of: break
325 }
326 }
327 if ( index < 0 ) {
328 index = 0;
329 }
330 part.add( index, evp );
331 part.add( index+1, p );
332 }
333 // table.put( key, part ); // required??
334 }
335
336
337 /**
338 * Update or initialize RelationTable with new relation.
339 * relation is e * f = p.
340 * @param E first term polynomial.
341 * @param F second term polynomial.
342 * @param p solvable product polynomial.
343 */
344 public void update(GenPolynomial<C> E, GenPolynomial<C> F, GenSolvablePolynomial<C> p) {
345 if ( E.isZERO() || F.isZERO() ) {
346 throw new IllegalArgumentException("polynomials may not be zero: " + E + ", " + F);
347 }
348 C ce = E.leadingBaseCoefficient();
349 C cf = F.leadingBaseCoefficient();
350 if ( ! ce.isONE() || ! cf.isONE() ) {
351 throw new IllegalArgumentException("lbcf of polynomials must be one: " + ce + ", " + cf);
352 }
353 ExpVector e = E.leadingExpVector();
354 ExpVector f = F.leadingExpVector();
355 update(e,f,p);
356 }
357
358
359 /**
360 * Update or initialize RelationTable with new relation.
361 * relation is e * f = p.
362 * @param E first term polynomial.
363 * @param F second term polynomial.
364 * @param p product polynomial.
365 */
366 public void update(GenPolynomial<C> E, GenPolynomial<C> F, GenPolynomial<C> p) {
367 if ( p.isZERO() ) {
368 throw new IllegalArgumentException("polynomial may not be zero: " + p);
369 }
370 if ( p.isONE() ) {
371 throw new IllegalArgumentException("product of polynomials may not be one: " + p);
372 }
373 GenSolvablePolynomial<C> sp = new GenSolvablePolynomial<C>(ring,p.val);
374 update(E,F,sp);
375 }
376
377
378 /**
379 * Lookup RelationTable for existing relation.
380 * Find p with e * f = p.
381 * If no relation for e * f is contained in the table then
382 * return the symmetric product p = 1 e f.
383 * @param e first term.
384 * @param f second term.
385 * @return t table relation container,
386 * contains e' and f' with e f = e' lt(p) f'.
387 */
388 @SuppressWarnings("unchecked")
389 public TableRelation<C> lookup(ExpVector e, ExpVector f) {
390 List<Integer> key = makeKey(e,f);
391 List part = table.get( key );
392 if ( part == null ) { // symmetric product
393 ExpVector ef = e.sum( f );
394 GenSolvablePolynomial<C> p = ring.getONE().multiply( ef );
395 return new TableRelation<C>(null,null,p);
396 }
397 ExpVectorPair evp = new ExpVectorPair( e, f );
398 ExpVector ep = null;
399 ExpVector fp = null;
400 ExpVectorPair look = null;
401 GenSolvablePolynomial<C> p = null;
402 synchronized(part) { // with update()
403 for ( Iterator it = part.iterator(); it.hasNext(); ) {
404 look = (ExpVectorPair)it.next();
405 p = (GenSolvablePolynomial<C>)it.next();
406 if ( evp.isMultiple( look ) ) {
407 ep = e.subtract( look.getFirst() );
408 fp = f.subtract( look.getSecond() );
409 if ( ep.isZERO() ) {
410 ep = null;
411 }
412 if ( fp.isZERO() ) {
413 fp = null;
414 }
415 if ( false && debug ) {
416 if ( p != null && p.ring.vars != null ) {
417 logger.info("found relation = " + e.toString(p.ring.vars) + " .*. " + f.toString(p.ring.vars) + " = " + p);
418 } else {
419 logger.info("found relation = " + e + " .*. " + f + " = " + p);
420 }
421 }
422 return new TableRelation<C>(ep,fp,p);
423 }
424 }
425 }
426 // unreacheable code!
427 throw new RuntimeException("no entry found in relation table for " + evp);
428 }
429
430
431 /**
432 * Construct a key for (e,f).
433 * @param e first term.
434 * @param f second term.
435 * @return k key for (e,f).
436 */
437 protected List<Integer> makeKey(ExpVector e, ExpVector f) {
438 int[] de = e.dependencyOnVariables();
439 int[] df = f.dependencyOnVariables();
440 List<Integer> key = new ArrayList<Integer>( de.length + df.length );
441 for (int i = 0; i < de.length; i++ ) {
442 key.add( new Integer( de[i] ) );
443 }
444 for (int i = 0; i < df.length; i++ ) {
445 key.add( new Integer( df[i] ) );
446 }
447 return key;
448 }
449
450
451 /**
452 * Size of the table.
453 * @return n number of non-commutative relations.
454 */
455 public int size() {
456 int s = 0;
457 if ( table == null ) {
458 return s;
459 }
460 for ( Iterator<List> it = table.values().iterator(); it.hasNext(); ) {
461 List list = it.next();
462 s += list.size()/2;
463 }
464 return s;
465 }
466
467
468 /**
469 * Extend variables. Used e.g. in module embedding.
470 * Extend all ExpVectors and polynomials of the given
471 * relation table by i elements and put the relations into
472 * this table, i.e. this should be empty.
473 * @param tab a relation table to be extended and inserted into this.
474 */
475 @SuppressWarnings("unchecked")
476 public void extend(RelationTable<C> tab) {
477 if ( tab.table.size() == 0 ) {
478 return;
479 }
480 // assert this.size() == 0
481 int i = ring.nvar - tab.ring.nvar;
482 int j = 0;
483 long k = 0l;
484 List val;
485 for ( List<Integer> key: tab.table.keySet() ) {
486 val = tab.table.get( key );
487 for ( Iterator jt = val.iterator(); jt.hasNext(); ) {
488 ExpVectorPair ep = (ExpVectorPair)jt.next();
489 ExpVector e = ep.getFirst();
490 ExpVector f = ep.getSecond();
491 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>)jt.next();
492 ExpVector ex = e.extend(i,j,k);
493 ExpVector fx = f.extend(i,j,k);
494 GenSolvablePolynomial<C> px
495 = (GenSolvablePolynomial<C>)p.extend(ring,j,k);
496 this.update( ex, fx, px );
497 }
498 }
499 return;
500 }
501
502
503 /**
504 * Contract variables. Used e.g. in module embedding.
505 * Contract all ExpVectors and polynomials of the given
506 * relation table by i elements and put the relations into
507 * this table, i.e. this should be empty.
508 * @param tab a relation table to be contracted and inserted into this.
509 */
510 @SuppressWarnings("unchecked")
511 public void contract(RelationTable<C> tab) {
512 if ( tab.table.size() == 0 ) {
513 return;
514 }
515 // assert this.size() == 0
516 int i = tab.ring.nvar - ring.nvar;
517 List val;
518 for ( List<Integer> key: tab.table.keySet() ) {
519 val = tab.table.get( key );
520 for (Iterator jt = val.iterator(); jt.hasNext(); ) {
521 ExpVectorPair ep = (ExpVectorPair)jt.next();
522 ExpVector e = ep.getFirst();
523 ExpVector f = ep.getSecond();
524 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>)jt.next();
525 ExpVector ec = e.contract(i,e.length()-i);
526 ExpVector fc = f.contract(i,f.length()-i);
527 if ( ec.isZERO() || fc.isZERO() ) {
528 continue;
529 }
530 Map<ExpVector,GenPolynomial<C>> mc = p.contract(ring);
531 if ( mc.size() != 1 ) {
532 continue;
533 }
534 GenSolvablePolynomial<C> pc = null;
535 for ( GenPolynomial<C> x : mc.values() ) {
536 if ( pc != null ) {
537 // should not happen
538 logger.info("e = " + e + ", f = " + f + ", ec = " + ec + ", fc = " + fc);
539 logger.info("p = " + p + ", mc = " + mc);
540 throw new RuntimeException("Map.size() != 1: " + mc.size());
541 }
542 pc = (GenSolvablePolynomial<C>)x;
543 }
544 this.update( ec, fc, pc );
545 }
546 }
547 return;
548 }
549
550
551 /**
552 * Reverse variables and relations. Used e.g. in opposite rings.
553 * Reverse all ExpVectors and polynomials of the given
554 * relation table and put the modified relations into this table,
555 * i.e. this should be empty.
556 * @param tab a relation table to be reverted and inserted into this.
557 */
558 @SuppressWarnings("unchecked")
559 public void reverse(RelationTable<C> tab) {
560 if ( tab.table.size() == 0 ) {
561 return;
562 }
563 // assert this.size() == 0
564 if ( table.size() != 0 ) {
565 logger.error("reverse table not empty");
566 }
567 int k = -1;
568 if ( ring.tord.getEvord2() != 0 && ring.partial ) {
569 k = ring.tord.getSplit();
570 }
571 logger.debug("k split = " + k );
572 //System.out.println("k split = " + k );
573 for ( List<Integer> key: tab.table.keySet() ) {
574 List val = tab.table.get( key );
575 for ( Iterator jt = val.iterator(); jt.hasNext(); ) {
576 ExpVectorPair ep = (ExpVectorPair)jt.next();
577 ExpVector e = ep.getFirst();
578 ExpVector f = ep.getSecond();
579 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>)jt.next();
580 //logger.info("e pre reverse = " + e );
581 //logger.info("f pre reverse = " + f );
582 //logger.info("p pre reverse = " + p );
583 ExpVector ex;
584 ExpVector fx;
585 GenSolvablePolynomial<C> px;
586 boolean change = true; // if relevant vars reversed
587 if ( k >= 0 ) {
588 ex = e.reverse(k);
589 fx = f.reverse(k);
590 int[] ed = ex.dependencyOnVariables(); // = e
591 if ( ed.length == 0 || ed[0] >= k ) { // k >= 0
592 change = false;
593 }
594 int[] fd = fx.dependencyOnVariables(); // = f
595 if ( fd.length == 0 || fd[0] >= k ) { // k >= 0
596 change = false;
597 }
598 } else {
599 ex = e.reverse();
600 fx = f.reverse();
601 }
602 px = (GenSolvablePolynomial<C>)p.reverse(ring);
603 //System.out.println("change = " + change );
604 if ( ! change ) {
605 this.update( e, f, px ); // same order
606 } else {
607 this.update( fx, ex, px ); // opposite order
608 //this.update( ex, fx, px ); // same order
609 }
610 }
611 }
612 return;
613 }
614
615 }
616
617
618
619 /**
620 * TableRelation container for storage and printing in RelationTable.
621 * @author Heinz Kredel
622 */
623
624 class TableRelation<C extends RingElem<C>> implements Serializable {
625
626 /** First ExpVector of the data structure.
627 */
628 public final ExpVector e;
629
630
631 /** Second ExpVector of the data structure.
632 */
633 public final ExpVector f;
634
635
636 /** GenSolvablePolynomial of the data structure.
637 */
638 public final GenSolvablePolynomial<C> p;
639
640
641 /**
642 * Constructor to setup the data structure.
643 * @param e first term.
644 * @param f second term.
645 * @param p product polynomial.
646 */
647 public TableRelation(ExpVector e, ExpVector f,
648 GenSolvablePolynomial<C> p) {
649 this.e = e;
650 this.f = f;
651 this.p = p;
652 }
653
654
655 /** Get the String representation.
656 * @see java.lang.Object#toString()
657 */
658 @Override
659 public String toString() {
660 StringBuffer s = new StringBuffer("TableRelation[");
661 s.append(""+e);
662 s.append(" | ");
663 s.append(""+f);
664 s.append(" = ");
665 s.append(""+p);
666 s.append("]");
667 return s.toString();
668 }
669
670 }