001 /*
002 * $Id: Product.java 3368 2010-10-24 13:53:32Z kredel $
003 */
004
005 package edu.jas.arith;
006
007 import java.util.Map;
008 import java.util.Iterator;
009 import java.util.SortedMap;
010 import java.util.TreeMap;
011
012 import org.apache.log4j.Logger;
013
014 import edu.jas.structure.Element;
015 import edu.jas.structure.RegularRingElem;
016 import edu.jas.structure.RingElem;
017 import edu.jas.structure.RingFactory;
018 import edu.jas.structure.NotInvertibleException;
019
020
021 /**
022 * Direct product element based on RingElem.
023 * Objects of this class are (nearly) immutable.
024 * @author Heinz Kredel
025 */
026 public class Product<C extends RingElem<C> >
027 implements RegularRingElem< Product<C> > {
028
029 private static final Logger logger = Logger.getLogger(Product.class);
030 private boolean debug = logger.isDebugEnabled();
031
032
033 /** Product class factory data structure.
034 */
035 public final ProductRing<C> ring;
036
037
038 /** Value part of the element data structure.
039 */
040 public final SortedMap<Integer,C> val;
041
042
043 /** Flag to remember if this product element is a unit in each cmponent.
044 * -1 is unknown, 1 is unit, 0 not a unit.
045 */
046 protected int isunit = -1; // initially unknown
047
048
049 /** The constructor creates a Product object
050 * from a ring factory.
051 * @param r ring factory.
052 */
053 public Product(ProductRing<C> r) {
054 this( r, new TreeMap<Integer,C>(), 0 );
055 }
056
057
058 /** The constructor creates a Product object
059 * from a ring factory and a ring element.
060 * @param r ring factory.
061 * @param a ring element.
062 */
063 public Product(ProductRing<C> r, SortedMap<Integer,C> a) {
064 this( r, a, -1 );
065 }
066
067
068 /** The constructor creates a Product object
069 * from a ring factory, a ring element and an indicator if a is a unit.
070 * @param r ring factory.
071 * @param a ring element.
072 * @param u isunit indicator, -1, 0, 1.
073 */
074 public Product(ProductRing<C> r, SortedMap<Integer,C> a, int u) {
075 ring = r;
076 val = a;
077 isunit = u;
078 }
079
080
081 /** Get component.
082 * @param i index of component.
083 * @return val(i).
084 */
085 public C get(int i) {
086 return val.get(i); // auto-boxing
087 }
088
089
090 /**
091 * Get the corresponding element factory.
092 * @return factory for this Element.
093 * @see edu.jas.structure.Element#factory()
094 */
095 public ProductRing<C> factory() {
096 return ring;
097 }
098
099
100 /** Clone this.
101 * @see java.lang.Object#clone()
102 */
103 @Override
104 public Product<C> clone() {
105 return new Product<C>( ring, val, isunit );
106 }
107
108
109 /** Is Product zero.
110 * @return If this is 0 then true is returned, else false.
111 * @see edu.jas.structure.RingElem#isZERO()
112 */
113 public boolean isZERO() {
114 return val.size() == 0;
115 }
116
117
118 /** Is Product one.
119 * @return If this is 1 then true is returned, else false.
120 * @see edu.jas.structure.RingElem#isONE()
121 */
122 public boolean isONE() {
123 if ( val.size() != ring.length() ) {
124 return false;
125 }
126 for ( C e : val.values() ) {
127 if ( ! e.isONE() ) {
128 return false;
129 }
130 }
131 return true;
132 }
133
134
135 /** Is Product full.
136 * @return If every component is non-zero,
137 * then true is returned, else false.
138 */
139 public boolean isFull() {
140 if ( val.size() != ring.length() ) {
141 return false;
142 }
143 return true;
144 }
145
146
147 /** Is Product unit.
148 * @return If this is a unit then true is returned, else false.
149 * @see edu.jas.structure.RingElem#isUnit()
150 */
151 public boolean isUnit() {
152 if ( isunit > 0 ) {
153 return true;
154 }
155 if ( isunit == 0 ) {
156 return false;
157 }
158 if ( isZERO() ) {
159 isunit = 0;
160 return false;
161 }
162 for ( C e : val.values() ) {
163 if ( ! e.isUnit() ) {
164 isunit = 0;
165 return false;
166 }
167 }
168 isunit = 1;
169 return true;
170 }
171
172
173 /** Is Product idempotent.
174 * @return If this is a idempotent element then true is returned, else false.
175 */
176 public boolean isIdempotent() {
177 for ( C e : val.values() ) {
178 if ( ! e.isONE() ) {
179 return false;
180 }
181 }
182 return true;
183 }
184
185
186 /** Get the String representation as RingElem.
187 * @see java.lang.Object#toString()
188 */
189 @Override
190 public String toString() {
191 return val.toString();
192 }
193
194
195 /** Get a scripting compatible string representation.
196 * @return script compatible representation for this Element.
197 * @see edu.jas.structure.Element#toScript()
198 */
199 //JAVA6only: @Override
200 public String toScript() {
201 // Python case
202 StringBuffer s = new StringBuffer("( ");
203 boolean first = true;
204 for ( Integer i : val.keySet() ) {
205 C v = val.get(i);
206 if ( first ) {
207 first = false;
208 } else {
209 if ( v.signum() < 0 ) {
210 s.append(" - ");
211 v = v.negate();
212 } else {
213 s.append(" + ");
214 }
215 }
216 if ( !v.isONE() ) {
217 s.append( v.toScript() + "*" );
218 }
219 s.append( "pg"+i );
220 }
221 s.append(" )");
222 return s.toString();
223 }
224
225
226 /** Get a scripting compatible string representation of the factory.
227 * @return script compatible representation for this ElemFactory.
228 * @see edu.jas.structure.Element#toScriptFactory()
229 */
230 //JAVA6only: @Override
231 public String toScriptFactory() {
232 // Python case
233 return factory().toScript();
234 }
235
236
237 /** Product comparison.
238 * @param b Product.
239 * @return sign(this-b).
240 */
241 //JAVA6only: @Override
242 public int compareTo(Product<C> b) {
243 if ( ! ring.equals( b.ring ) ) {
244 throw new IllegalArgumentException("rings not comparable " + this);
245 }
246 SortedMap<Integer,C> v = b.val;
247 Iterator<Map.Entry<Integer,C>> ti = val.entrySet().iterator();
248 Iterator<Map.Entry<Integer,C>> bi = v.entrySet().iterator();
249 int s;
250 while ( ti.hasNext() && bi.hasNext() ) {
251 Map.Entry<Integer,C> te = ti.next();
252 Map.Entry<Integer,C> be = bi.next();
253 s = te.getKey().compareTo( be.getKey() );
254 if ( s != 0 ) {
255 return s;
256 }
257 s = te.getValue().compareTo( be.getValue() );
258 if ( s != 0 ) {
259 return s;
260 }
261 }
262 if ( ti.hasNext() ) {
263 return -1;
264 }
265 if ( bi.hasNext() ) {
266 return 1;
267 }
268 return 0;
269 }
270
271
272 /** Comparison with any other object.
273 * @see java.lang.Object#equals(java.lang.Object)
274 */
275 @SuppressWarnings("unchecked")
276 @Override
277 public boolean equals(Object b) {
278 if ( ! ( b instanceof Product ) ) {
279 return false;
280 }
281 Product<C> a = null;
282 try {
283 a = (Product<C>) b;
284 } catch (ClassCastException e) {
285 }
286 if ( a == null ) {
287 return false;
288 }
289 return ( 0 == compareTo( a ) );
290 }
291
292
293 /** Hash code for this local.
294 * @see java.lang.Object#hashCode()
295 */
296 @Override
297 public int hashCode() {
298 int h = ring.hashCode();
299 h = 37 * h + val.hashCode();
300 return h;
301 }
302
303
304 /** Product extend.
305 * Add new component j with value of component i.
306 * @param i from index.
307 * @param j to index.
308 * @return the extended value of this.
309 */
310 public Product<C> extend( int i, int j ) {
311 RingFactory<C> rf = ring.getFactory( j );
312 SortedMap<Integer,C> elem = new TreeMap<Integer,C>( val );
313 C v = val.get( i );
314 C w = rf.copy( v ); // valueOf
315 if ( ! w.isZERO() ) {
316 elem.put( j , w );
317 }
318 return new Product<C>( ring, elem, isunit );
319 }
320
321
322 /** Product absolute value.
323 * @return the absolute value of this.
324 * @see edu.jas.structure.RingElem#abs()
325 */
326 public Product<C> abs() {
327 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
328 for ( Integer i : val.keySet() ) {
329 C v = val.get(i).abs();
330 elem.put( i, v );
331 }
332 return new Product<C>( ring, elem, isunit );
333 }
334
335
336 /** Product summation.
337 * @param S Product.
338 * @return this+S.
339 */
340 public Product<C> sum(Product<C> S) {
341 if ( S == null || S.isZERO() ) {
342 return this;
343 }
344 if ( this.isZERO() ) {
345 return S;
346 }
347 SortedMap<Integer,C> elem = new TreeMap<Integer,C>( val ); // clone
348 SortedMap<Integer,C> sel = S.val;
349 for ( Integer i : sel.keySet() ) {
350 C x = elem.get( i );
351 C y = sel.get( i ); // assert y != null
352 if ( x != null ) {
353 x = x.sum(y);
354 if ( ! x.isZERO() ) {
355 elem.put( i, x );
356 } else {
357 elem.remove( i );
358 }
359 } else {
360 elem.put( i, y );
361 }
362 }
363 return new Product<C>( ring, elem );
364 }
365
366
367 /** Product negate.
368 * @return -this.
369 * @see edu.jas.structure.RingElem#negate()
370 */
371 public Product<C> negate() {
372 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
373 for ( Integer i : val.keySet() ) {
374 C v = val.get(i).negate();
375 elem.put( i, v );
376 }
377 return new Product<C>( ring, elem, isunit );
378 }
379
380
381 /** Product signum.
382 * @see edu.jas.structure.RingElem#signum()
383 * @return signum of first non-zero component.
384 */
385 public int signum() {
386 if ( val.size() == 0 ) {
387 return 0;
388 }
389 C v = val.get( val.firstKey() );
390 return v.signum();
391 }
392
393
394 /** Product subtraction.
395 * @param S Product.
396 * @return this-S.
397 */
398 public Product<C> subtract(Product<C> S) {
399 return sum( S.negate() );
400 }
401
402
403 /** Product quasi-inverse.
404 * @see edu.jas.structure.RingElem#inverse()
405 * @return S with S = 1/this if defined.
406 */
407 public Product<C> inverse() {
408 if ( this.isZERO() ) {
409 return this;
410 }
411 int isu = 0;
412 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
413 for ( Integer i : val.keySet() ) {
414 C x = val.get( i ); // is non zero
415 try {
416 x = x.inverse();
417 } catch(NotInvertibleException e) {
418 // could happen for e.g. ModInteger or AlgebraicNumber
419 x = null; //ring.getFactory(i).getZERO();
420 }
421 if ( x != null && ! x.isZERO() ) { // can happen
422 elem.put( i, x );
423 isu = 1;
424 }
425 }
426 return new Product<C>( ring, elem, isu );
427 }
428
429
430 /** Product idempotent.
431 * @return smallest S with this*S = this.
432 */
433 public Product<C> idempotent() {
434 if ( this.isZERO() ) {
435 return this;
436 }
437 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
438 for ( Integer i : val.keySet() ) {
439 RingFactory<C> f = ring.getFactory( i );
440 C x = f.getONE();
441 elem.put( i, x );
442 }
443 return new Product<C>( ring, elem, 1 );
444 }
445
446
447 /** Product idempotent complement.
448 * @return 1-this.idempotent().
449 */
450 public Product<C> idemComplement() {
451 if ( this.isZERO() ) {
452 return ring.getONE();
453 }
454 int isu = 0;
455 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
456 for ( int i = 0; i < ring.length(); i++ ) {
457 C v = val.get( i );
458 if ( v == null ) {
459 RingFactory<C> f = ring.getFactory( i );
460 C x = f.getONE();
461 elem.put( i, x );
462 isu = 1;
463 }
464 }
465 return new Product<C>( ring, elem, isu );
466 }
467
468
469 /** Product idempotent and.
470 * @param S Product.
471 * @return this.idempotent() and S.idempotent().
472 */
473 public Product<C> idempotentAnd(Product<C> S) {
474 if ( this.isZERO() && S.isZERO() ) {
475 return this;
476 }
477 int isu = 0;
478 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
479 for ( int i = 0; i < ring.length(); i++ ) {
480 C v = val.get( i );
481 C w = S.val.get( i );
482 if ( v != null && w != null ) {
483 RingFactory<C> f = ring.getFactory( i );
484 C x = f.getONE();
485 elem.put( i, x );
486 isu = 1;
487 }
488 }
489 return new Product<C>( ring, elem, isu );
490 }
491
492
493 /** Product idempotent or.
494 * @param S Product.
495 * @return this.idempotent() or S.idempotent().
496 */
497 public Product<C> idempotentOr(Product<C> S) {
498 if ( this.isZERO() && S.isZERO() ) {
499 return this;
500 }
501 int isu = 0;
502 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
503 for ( int i = 0; i < ring.length(); i++ ) {
504 C v = val.get( i );
505 C w = S.val.get( i );
506 if ( v != null || w != null ) {
507 RingFactory<C> f = ring.getFactory( i );
508 C x = f.getONE();
509 elem.put( i, x );
510 isu = 1;
511 }
512 }
513 return new Product<C>( ring, elem, isu );
514 }
515
516
517 /** Product fill with idempotent.
518 * @param S Product.
519 * @return fill this with S.idempotent().
520 */
521 public Product<C> fillIdempotent(Product<C> S) {
522 if ( S.isZERO() ) {
523 return this;
524 }
525 SortedMap<Integer,C> elem = new TreeMap<Integer,C>( val );
526 for ( int i = 0; i < ring.length(); i++ ) {
527 C v = elem.get( i );
528 if ( v != null ) {
529 continue;
530 }
531 C w = S.val.get( i );
532 if ( w != null ) {
533 RingFactory<C> f = ring.getFactory( i );
534 C x = f.getONE();
535 elem.put( i, x );
536 }
537 }
538 return new Product<C>( ring, elem, isunit );
539 }
540
541
542 /** Product fill with one.
543 * @return fill this with one.
544 */
545 public Product<C> fillOne() {
546 if ( this.isFull() ) {
547 return this;
548 }
549 if ( this.isZERO() ) {
550 return ring.getONE();
551 }
552 SortedMap<Integer,C> elem = new TreeMap<Integer,C>( val );
553 for ( int i = 0; i < ring.length(); i++ ) {
554 C v = elem.get( i );
555 if ( v != null ) {
556 continue;
557 }
558 RingFactory<C> f = ring.getFactory( i );
559 C x = f.getONE();
560 elem.put( i, x );
561 }
562 return new Product<C>( ring, elem, isunit );
563 }
564
565
566 /** Product quasi-division.
567 * @param S Product.
568 * @return this/S.
569 */
570 public Product<C> divide(Product<C> S) {
571 if ( S == null ) {
572 return ring.getZERO();
573 }
574 if ( S.isZERO() ) {
575 return S;
576 }
577 if ( this.isZERO() ) {
578 return this;
579 }
580 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
581 SortedMap<Integer,C> sel = S.val;
582 for ( Integer i : val.keySet() ) {
583 C y = sel.get( i );
584 if ( y != null ) {
585 C x = val.get( i );
586 try {
587 x = x.divide(y);
588 } catch(NotInvertibleException e) {
589 // should not happen any more
590 System.out.println("product divide error: x = " + x + ", y = " + y);
591 // could happen for e.g. ModInteger or AlgebraicNumber
592 x = null; //ring.getFactory(i).getZERO();
593 }
594 if ( x != null && ! x.isZERO() ) { // can happen
595 elem.put( i, x );
596 }
597 }
598 }
599 return new Product<C>( ring, elem );
600 }
601
602
603 /** Product quasi-remainder.
604 * @param S Product.
605 * @return this - (this/S)*S.
606 */
607 public Product<C> remainder(Product<C> S) {
608 if ( S == null ) {
609 return this; //ring.getZERO();
610 }
611 if ( S.isZERO() ) {
612 return this;
613 }
614 if ( this.isZERO() ) {
615 return this;
616 }
617 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
618 SortedMap<Integer,C> sel = S.val;
619 for ( Integer i : val.keySet() ) {
620 C y = sel.get( i );
621 if ( y != null ) {
622 C x = val.get( i );
623 x = x.remainder(y);
624 if ( x != null && ! x.isZERO() ) { // can happen
625 elem.put( i, x );
626 }
627 }
628 }
629 return new Product<C>( ring, elem );
630 }
631
632
633 /** Product multiplication.
634 * @param S Product.
635 * @return this*S.
636 */
637 public Product<C> multiply(Product<C> S) {
638 if ( S == null ) {
639 return ring.getZERO();
640 }
641 if ( S.isZERO() ) {
642 return S;
643 }
644 if ( this.isZERO() ) {
645 return this;
646 }
647 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
648 SortedMap<Integer,C> sel = S.val;
649 for ( Integer i : val.keySet() ) {
650 C y = sel.get( i );
651 if ( y != null ) {
652 C x = val.get( i );
653 x = x.multiply(y);
654 if ( x != null && ! x.isZERO() ) {
655 elem.put( i, x );
656 }
657 }
658 }
659 return new Product<C>( ring, elem );
660 }
661
662
663 /** Product multiply by coefficient.
664 * @param c coefficient.
665 * @return this*c.
666 */
667 public Product<C> multiply(C c) {
668 SortedMap<Integer,C> elem = new TreeMap<Integer,C>();
669 for ( Integer i : val.keySet() ) {
670 C v = val.get(i).multiply(c);
671 if ( v != null && ! v.isZERO() ) {
672 elem.put( i, v );
673 }
674 }
675 return new Product<C>( ring, elem );
676 }
677
678
679 /**
680 * Greatest common divisor.
681 * @param S other element.
682 * @return gcd(this,S).
683 */
684 public Product<C> gcd(Product<C> S) {
685 if ( S == null || S.isZERO() ) {
686 return this;
687 }
688 if ( this.isZERO() ) {
689 return S;
690 }
691 SortedMap<Integer,C> elem = new TreeMap<Integer,C>( val ); // clone
692 SortedMap<Integer,C> sel = S.val;
693 for ( Integer i : sel.keySet() ) {
694 C x = elem.get( i );
695 C y = sel.get( i ); // assert y != null
696 if ( x != null ) {
697 x = x.gcd(y);
698 if ( x != null && ! x.isZERO() ) {
699 elem.put( i, x );
700 } else {
701 elem.remove( i );
702 }
703 } else {
704 elem.put( i, y );
705 }
706 }
707 return new Product<C>( ring, elem );
708 }
709
710
711 /**
712 * Extended greatest common divisor.
713 * @param S other element.
714 * @return [ gcd(this,S), c1, c2 ] with c1*this + c2*b = gcd(this,S).
715 */
716 @SuppressWarnings("unchecked")
717 public Product<C>[] egcd(Product<C> S) {
718 Product<C>[] ret = (Product<C>[]) new Product[3];
719 ret[0] = null;
720 ret[1] = null;
721 ret[2] = null;
722 if ( S == null || S.isZERO() ) {
723 ret[0] = this;
724 return ret;
725 }
726 if ( this.isZERO() ) {
727 ret[0] = S;
728 return ret;
729 }
730 SortedMap<Integer,C> elem = new TreeMap<Integer,C>( val ); // clone
731 SortedMap<Integer,C> elem1 = this.idempotent().val; // init with 1
732 SortedMap<Integer,C> elem2 = new TreeMap<Integer,C>(); // zero
733 SortedMap<Integer,C> sel = S.val;
734 for ( Integer i : sel.keySet() ) {
735 C x = elem.get( i );
736 C y = sel.get( i ); // assert y != null
737 if ( x != null ) {
738 C[] g = x.egcd(y);
739 if ( ! g[0].isZERO() ) {
740 elem.put( i, g[0] );
741 elem1.put( i, g[1] );
742 elem2.put( i, g[2] );
743 } else {
744 elem.remove( i );
745 }
746 } else {
747 elem.put( i, y );
748 elem2.put( i, ring.getFactory(i).getONE() );
749 }
750 }
751 ret[0] = new Product<C>( ring, elem );
752 ret[1] = new Product<C>( ring, elem1 );
753 ret[2] = new Product<C>( ring, elem2 );
754 return ret;
755 }
756
757 }