001 /*
002 * $Id: ExpVectorLong.java 3295 2010-08-26 17:01:10Z kredel $
003 */
004
005 package edu.jas.poly;
006
007
008 import java.util.Vector;
009
010
011 /**
012 * ExpVectorLong implements exponent vectors for polynomials using arrays of
013 * long as storage unit. This class is used by ExpVector internally, there is no
014 * need to use this class directly.
015 * @see ExpVector
016 * @author Heinz Kredel
017 */
018
019 public class ExpVectorLong extends ExpVector
020 /*implements AbelianGroupElem<ExpVectorLong>*/{
021
022
023 /**
024 * The data structure is an array of longs.
025 */
026 /*package*/final long[] val;
027
028
029 /**
030 * Constructor for ExpVector.
031 * @param n length of exponent vector.
032 */
033 public ExpVectorLong(int n) {
034 this(new long[n]);
035 }
036
037
038 /**
039 * Constructor for ExpVector. Sets exponent i to e.
040 * @param n length of exponent vector.
041 * @param i index of exponent to be set.
042 * @param e exponent to be set.
043 */
044 public ExpVectorLong(int n, int i, long e) {
045 this(new long[n]);
046 val[i] = e;
047 }
048
049
050 /**
051 * Constructor for ExpVector. Sets val.
052 * @param v internal representation array.
053 */
054 public ExpVectorLong(long[] v) {
055 super();
056 if (v == null) {
057 throw new IllegalArgumentException("null val not allowed");
058 }
059 val = v;
060 }
061
062
063 /**
064 * Constructor for ExpVector. Converts a String representation to an
065 * ExpVector. Accepted format = (1,2,3,4,5,6,7).
066 * @param s String representation.
067 */
068 public ExpVectorLong(String s) throws NumberFormatException {
069 super();
070 // first format = (1,2,3,4,5,6,7)
071 Vector<Long> exps = new Vector<Long>();
072 s = s.trim();
073 int b = s.indexOf('(');
074 int e = s.indexOf(')', b + 1);
075 String teil;
076 int k;
077 long a;
078 if (b >= 0 && e >= 0) {
079 b++;
080 while ((k = s.indexOf(',', b)) >= 0) {
081 teil = s.substring(b, k);
082 a = Long.parseLong(teil);
083 exps.add(new Long(a));
084 b = k + 1;
085 }
086 if (b <= e) {
087 teil = s.substring(b, e);
088 a = Long.parseLong(teil);
089 exps.add(new Long(a));
090 }
091 int length = exps.size();
092 val = new long[length];
093 for (int j = 0; j < length; j++) {
094 val[j] = exps.elementAt(j).longValue();
095 }
096 } else {
097 // not implemented
098 val = null;
099 // length = -1;
100 //Vector names = new Vector();
101 //vars = s;
102 }
103 }
104
105
106 /**
107 * Clone this.
108 * @see java.lang.Object#clone()
109 */
110 @Override
111 public ExpVectorLong clone() {
112 long[] w = new long[val.length];
113 System.arraycopy(val, 0, w, 0, val.length);
114 return new ExpVectorLong(w);
115 }
116
117
118 /**
119 * Get the exponent vector.
120 * @return val.
121 */
122 @Override
123 /*package*/long[] getVal() {
124 return val;
125 }
126
127
128 /**
129 * Get the exponent at position i.
130 * @param i position.
131 * @return val[i].
132 */
133 @Override
134 public long getVal(int i) {
135 return val[i];
136 }
137
138
139 /**
140 * Set the exponent at position i to e.
141 * @param i
142 * @param e
143 * @return old val[i].
144 */
145 @Override
146 protected long setVal(int i, long e) {
147 long x = val[i];
148 val[i] = e;
149 hash = 0; // beware of race condition
150 return x;
151 }
152
153
154 /**
155 * Get the length of this exponent vector.
156 * @return val.length.
157 */
158 @Override
159 public int length() {
160 return val.length;
161 }
162
163
164 /**
165 * Extend variables. Used e.g. in module embedding. Extend this by i
166 * elements and set val[j] to e.
167 * @param i number of elements to extend.
168 * @param j index of element to be set.
169 * @param e new exponent for val[j].
170 * @return extended exponent vector.
171 */
172 @Override
173 public ExpVectorLong extend(int i, int j, long e) {
174 long[] w = new long[val.length + i];
175 System.arraycopy(val, 0, w, i, val.length);
176 if (j >= i) {
177 throw new IllegalArgumentException("i " + i + " <= j " + j + " invalid");
178 }
179 w[j] = e;
180 return new ExpVectorLong(w);
181 }
182
183
184 /**
185 * Extend lower variables. Extend this by i lower elements and set val[j] to
186 * e.
187 * @param i number of elements to extend.
188 * @param j index of element to be set.
189 * @param e new exponent for val[j].
190 * @return extended exponent vector.
191 */
192 @Override
193 public ExpVectorLong extendLower(int i, int j, long e) {
194 long[] w = new long[val.length + i];
195 System.arraycopy(val, 0, w, 0, val.length);
196 if (j >= i) {
197 throw new IllegalArgumentException("i " + i + " <= j " + j + " invalid");
198 }
199 w[val.length + j] = e;
200 return new ExpVectorLong(w);
201 }
202
203
204 /**
205 * Contract variables. Used e.g. in module embedding. Contract this to len
206 * elements.
207 * @param i position of first element to be copied.
208 * @param len new length.
209 * @return contracted exponent vector.
210 */
211 @Override
212 public ExpVectorLong contract(int i, int len) {
213 if (i + len > val.length) {
214 throw new IllegalArgumentException("len " + len + " > val.len " + val.length);
215 }
216 long[] w = new long[len];
217 System.arraycopy(val, i, w, 0, len);
218 return new ExpVectorLong(w);
219 }
220
221
222 /**
223 * Reverse variables. Used e.g. in opposite rings.
224 * @return reversed exponent vector.
225 */
226 @Override
227 public ExpVectorLong reverse() {
228 long[] w = new long[val.length];
229 for (int i = 0; i < val.length; i++) {
230 w[i] = val[val.length - 1 - i];
231 }
232 return new ExpVectorLong(w);
233 }
234
235
236 /**
237 * Reverse j variables. Used e.g. in opposite rings. Reverses the first j-1
238 * variables, the rest is unchanged.
239 * @param j index of first variable not reversed.
240 * @return reversed exponent vector.
241 */
242 @Override
243 public ExpVectorLong reverse(int j) {
244 if (j <= 0 || j > val.length) {
245 return this;
246 }
247 long[] w = new long[val.length];
248 for (int i = 0; i < j; i++) {
249 w[i] = val[j - 1 - i];
250 }
251 // copy rest
252 for (int i = j; i < val.length; i++) {
253 w[i] = val[i];
254 }
255 return new ExpVectorLong(w);
256 }
257
258
259 /**
260 * Combine with ExpVector. Combine this with the other ExpVector V.
261 * @param V the other exponent vector.
262 * @return combined exponent vector.
263 */
264 @Override
265 public ExpVectorLong combine(ExpVector V) {
266 if (V == null || V.length() == 0) {
267 return this;
268 }
269 ExpVectorLong Vl = (ExpVectorLong) V;
270 if (val.length == 0) {
271 return Vl;
272 }
273 long[] w = new long[val.length + Vl.val.length];
274 System.arraycopy(val, 0, w, 0, val.length);
275 System.arraycopy(Vl.val, 0, w, val.length, Vl.val.length);
276 return new ExpVectorLong(w);
277 }
278
279
280 /**
281 * Get the string representation.
282 * @see java.lang.Object#toString()
283 */
284 @Override
285 public String toString() {
286 return super.toString() + ":long";
287 }
288
289
290 /**
291 * Comparison with any other object.
292 * @see java.lang.Object#equals(java.lang.Object)
293 */
294 @Override
295 public boolean equals(Object B) {
296 if (!(B instanceof ExpVectorLong)) {
297 return false;
298 }
299 ExpVectorLong b = (ExpVectorLong) B;
300 int t = this.invLexCompareTo(b);
301 //System.out.println("equals: this = " + this + " B = " + B + " t = " + t);
302 return (0 == t);
303 }
304
305
306 /**
307 * ExpVector absolute value.
308 * @return abs(this).
309 */
310 @Override
311 public ExpVectorLong abs() {
312 long[] u = val;
313 long[] w = new long[u.length];
314 for (int i = 0; i < u.length; i++) {
315 if (u[i] >= 0L) {
316 w[i] = u[i];
317 } else {
318 w[i] = -u[i];
319 }
320 }
321 return new ExpVectorLong(w);
322 //return EVABS(this);
323 }
324
325
326 /**
327 * ExpVector negate.
328 * @return -this.
329 */
330 @Override
331 public ExpVectorLong negate() {
332 long[] u = val;
333 long[] w = new long[u.length];
334 for (int i = 0; i < u.length; i++) {
335 w[i] = -u[i];
336 }
337 return new ExpVectorLong(w);
338 // return EVNEG(this);
339 }
340
341
342 /**
343 * ExpVector summation.
344 * @param V
345 * @return this+V.
346 */
347 @Override
348 public ExpVectorLong sum(ExpVector V) {
349 long[] u = val;
350 long[] v = ((ExpVectorLong) V).val;
351 long[] w = new long[u.length];
352 for (int i = 0; i < u.length; i++) {
353 w[i] = u[i] + v[i];
354 }
355 return new ExpVectorLong(w);
356 // return EVSUM(this, V);
357 }
358
359
360 /**
361 * ExpVector subtract. Result may have negative entries.
362 * @param V
363 * @return this-V.
364 */
365 @Override
366 public ExpVectorLong subtract(ExpVector V) {
367 long[] u = val;
368 long[] v = ((ExpVectorLong) V).val;
369 long[] w = new long[u.length];
370 for (int i = 0; i < u.length; i++) {
371 w[i] = u[i] - v[i];
372 }
373 return new ExpVectorLong(w);
374 //return EVDIF(this, V);
375 }
376
377
378 /**
379 * ExpVector substitution. Clone and set exponent to d at position i.
380 * @param i position.
381 * @param d new exponent.
382 * @return substituted ExpVector.
383 */
384 @Override
385 public ExpVectorLong subst(int i, long d) {
386 ExpVectorLong V = (ExpVectorLong) this.clone();
387 long e = V.setVal(i, d);
388 return V;
389 //return EVSU(this, i, d);
390 }
391
392
393 /**
394 * ExpVector signum.
395 * @return 0 if this is zero, -1 if some entry is negative, 1 if no entry is
396 * negative and at least one entry is positive.
397 */
398 @Override
399 public int signum() {
400 int t = 0;
401 long[] u = val;
402 for (int i = 0; i < u.length; i++) {
403 if (u[i] < 0) {
404 return -1;
405 }
406 if (u[i] > 0) {
407 t = 1;
408 }
409 }
410 return t;
411 //return EVSIGN(this);
412 }
413
414
415 /**
416 * ExpVector total degree.
417 * @return sum of all exponents.
418 */
419 @Override
420 public long totalDeg() {
421 long t = 0;
422 long[] u = val; // U.val;
423 for (int i = 0; i < u.length; i++) {
424 t += u[i];
425 }
426 return t;
427 //return EVTDEG(this);
428 }
429
430
431 /**
432 * ExpVector maximal degree.
433 * @return maximal exponent.
434 */
435 @Override
436 public long maxDeg() {
437 long t = 0;
438 long[] u = val;
439 for (int i = 0; i < u.length; i++) {
440 if (u[i] > t) {
441 t = u[i];
442 }
443 }
444 return t;
445 //return EVMDEG(this);
446 }
447
448
449 /**
450 * ExpVector weighted degree.
451 * @param w weights.
452 * @return weighted sum of all exponents.
453 */
454 @Override
455 public long weightDeg(long[][] w) {
456 if (w == null || w.length == 0) {
457 return totalDeg(); // assume weight 1
458 }
459 long t = 0;
460 long[] u = val;
461 for (int j = 0; j < w.length; j++) {
462 long[] wj = w[j];
463 for (int i = 0; i < u.length; i++) {
464 t += wj[i] * u[i];
465 }
466 }
467 return t;
468 //return EVWDEG( w, this );
469 }
470
471
472 /**
473 * ExpVector least common multiple.
474 * @param V
475 * @return component wise maximum of this and V.
476 */
477 @Override
478 public ExpVectorLong lcm(ExpVector V) {
479 long[] u = val;
480 long[] v = ((ExpVectorLong) V).val;
481 long[] w = new long[u.length];
482 for (int i = 0; i < u.length; i++) {
483 w[i] = (u[i] >= v[i] ? u[i] : v[i]);
484 }
485 return new ExpVectorLong(w);
486 //return EVLCM(this, V);
487 }
488
489
490 /**
491 * ExpVector greatest common divisor.
492 * @param V
493 * @return component wise minimum of this and V.
494 */
495 @Override
496 public ExpVectorLong gcd(ExpVector V) {
497 long[] u = val;
498 long[] v = ((ExpVectorLong) V).val;
499 long[] w = new long[u.length];
500 for (int i = 0; i < u.length; i++) {
501 w[i] = (u[i] <= v[i] ? u[i] : v[i]);
502 }
503 return new ExpVectorLong(w);
504 //return EVGCD(this, V);
505 }
506
507
508 /**
509 * ExpVector dependency on variables.
510 * @return array of indices where val has positive exponents.
511 */
512 @Override
513 public int[] dependencyOnVariables() {
514 long[] u = val;
515 int l = 0;
516 for (int i = 0; i < u.length; i++) {
517 if (u[i] > 0) {
518 l++;
519 }
520 }
521 int[] dep = new int[l];
522 if (l == 0) {
523 return dep;
524 }
525 int j = 0;
526 for (int i = 0; i < u.length; i++) {
527 if (u[i] > 0) {
528 dep[j] = i;
529 j++;
530 }
531 }
532 return dep;
533 }
534
535
536 /**
537 * ExpVector multiple test. Test if this is component wise greater or equal
538 * to V.
539 * @param V
540 * @return true if this is a multiple of V, else false.
541 */
542 @Override
543 public boolean multipleOf(ExpVector V) {
544 long[] u = val;
545 long[] v = ((ExpVectorLong) V).val;
546 boolean t = true;
547 for (int i = 0; i < u.length; i++) {
548 if (u[i] < v[i]) {
549 return false;
550 }
551 }
552 return t;
553 //return EVMT(this, V);
554 }
555
556
557 /**
558 * ExpVector compareTo.
559 * @param V
560 * @return 0 if U == V, -1 if U < V, 1 if U > V.
561 */
562 //@Override
563 public int compareTo(ExpVectorLong V) {
564 return this.invLexCompareTo(V);
565 }
566
567
568 /**
569 * ExpVector inverse lexicographical compareTo.
570 * @param V
571 * @return 0 if U == V, -1 if U < V, 1 if U > V.
572 */
573 @Override
574 public int invLexCompareTo(ExpVector V) {
575 long[] u = val;
576 long[] v = ((ExpVectorLong) V).val;
577 int t = 0;
578 for (int i = 0; i < u.length; i++) {
579 if (u[i] > v[i])
580 return 1;
581 if (u[i] < v[i])
582 return -1;
583 }
584 return t;
585 //return EVILCP(this, V);
586 }
587
588
589 /**
590 * ExpVector inverse lexicographical compareTo.
591 * @param V
592 * @param begin
593 * @param end
594 * @return 0 if U == V, -1 if U < V, 1 if U > V.
595 */
596 @Override
597 public int invLexCompareTo(ExpVector V, int begin, int end) {
598 long[] u = val;
599 long[] v = ((ExpVectorLong) V).val;
600 int t = 0;
601 for (int i = begin; i < end; i++) {
602 if (u[i] > v[i])
603 return 1;
604 if (u[i] < v[i])
605 return -1;
606 }
607 return t;
608 //return EVILCP(this, V, begin, end);
609 }
610
611
612 /**
613 * ExpVector inverse graded lexicographical compareTo.
614 * @param V
615 * @return 0 if U == V, -1 if U < V, 1 if U > V.
616 */
617 @Override
618 public int invGradCompareTo(ExpVector V) {
619 long[] u = val;
620 long[] v = ((ExpVectorLong) V).val;
621 int t = 0;
622 int i;
623 for (i = 0; i < u.length; i++) {
624 if (u[i] > v[i]) {
625 t = 1;
626 break;
627 }
628 if (u[i] < v[i]) {
629 t = -1;
630 break;
631 }
632 }
633 if (t == 0) {
634 return t;
635 }
636 long up = 0;
637 long vp = 0;
638 for (int j = i; j < u.length; j++) {
639 up += u[j];
640 vp += v[j];
641 }
642 if (up > vp) {
643 t = 1;
644 } else {
645 if (up < vp) {
646 t = -1;
647 }
648 }
649 return t;
650 //return EVIGLC(this, V);
651 }
652
653
654 /**
655 * ExpVector inverse graded lexicographical compareTo.
656 * @param V
657 * @param begin
658 * @param end
659 * @return 0 if U == V, -1 if U < V, 1 if U > V.
660 */
661 @Override
662 public int invGradCompareTo(ExpVector V, int begin, int end) {
663 long[] u = val;
664 long[] v = ((ExpVectorLong) V).val;
665 int t = 0;
666 int i;
667 for (i = begin; i < end; i++) {
668 if (u[i] > v[i]) {
669 t = 1;
670 break;
671 }
672 if (u[i] < v[i]) {
673 t = -1;
674 break;
675 }
676 }
677 if (t == 0) {
678 return t;
679 }
680 long up = 0;
681 long vp = 0;
682 for (int j = i; j < end; j++) {
683 up += u[j];
684 vp += v[j];
685 }
686 if (up > vp) {
687 t = 1;
688 } else {
689 if (up < vp) {
690 t = -1;
691 }
692 }
693 return t;
694 //return EVIGLC(this, V, begin, end);
695 }
696
697
698 /**
699 * ExpVector reverse inverse lexicographical compareTo.
700 * @param V
701 * @return 0 if U == V, -1 if U < V, 1 if U > V.
702 */
703 @Override
704 public int revInvLexCompareTo(ExpVector V) {
705 long[] u = val;
706 long[] v = ((ExpVectorLong) V).val;
707 int t = 0;
708 for (int i = u.length - 1; i >= 0; i--) {
709 if (u[i] > v[i])
710 return 1;
711 if (u[i] < v[i])
712 return -1;
713 }
714 return t;
715 //return EVRILCP(this, V);
716 }
717
718
719 /**
720 * ExpVector reverse inverse lexicographical compareTo.
721 * @param V
722 * @param begin
723 * @param end
724 * @return 0 if U == V, -1 if U < V, 1 if U > V.
725 */
726 @Override
727 public int revInvLexCompareTo(ExpVector V, int begin, int end) {
728 long[] u = val;
729 long[] v = ((ExpVectorLong) V).val;
730 int t = 0;
731 for (int i = end - 1; i >= begin; i--) {
732 if (u[i] > v[i])
733 return 1;
734 if (u[i] < v[i])
735 return -1;
736 }
737 return t;
738 //return EVRILCP(this, V, begin, end);
739 }
740
741
742 /**
743 * ExpVector reverse inverse graded compareTo.
744 * @param V
745 * @return 0 if U == V, -1 if U < V, 1 if U > V.
746 */
747 @Override
748 public int revInvGradCompareTo(ExpVector V) {
749 long[] u = val;
750 long[] v = ((ExpVectorLong) V).val;
751 int t = 0;
752 int i;
753 for (i = u.length - 1; i >= 0; i--) {
754 if (u[i] > v[i]) {
755 t = 1;
756 break;
757 }
758 if (u[i] < v[i]) {
759 t = -1;
760 break;
761 }
762 }
763 if (t == 0) {
764 return t;
765 }
766 long up = 0;
767 long vp = 0;
768 for (int j = i; j >= 0; j--) {
769 up += u[j];
770 vp += v[j];
771 }
772 if (up > vp) {
773 t = 1;
774 } else {
775 if (up < vp) {
776 t = -1;
777 }
778 }
779 return t;
780 //return EVRIGLC(this, V);
781 }
782
783
784 /**
785 * ExpVector reverse inverse graded compareTo.
786 * @param V
787 * @param begin
788 * @param end
789 * @return 0 if U == V, -1 if U < V, 1 if U > V.
790 */
791 @Override
792 public int revInvGradCompareTo(ExpVector V, int begin, int end) {
793 long[] u = val;
794 long[] v = ((ExpVectorLong) V).val;
795 int t = 0;
796 int i;
797 for (i = end - 1; i >= begin; i--) {
798 if (u[i] > v[i]) {
799 t = 1;
800 break;
801 }
802 if (u[i] < v[i]) {
803 t = -1;
804 break;
805 }
806 }
807 if (t == 0) {
808 return t;
809 }
810 long up = 0;
811 long vp = 0;
812 for (int j = i; j >= begin; j--) {
813 up += u[j];
814 vp += v[j];
815 }
816 if (up > vp) {
817 t = 1;
818 } else {
819 if (up < vp) {
820 t = -1;
821 }
822 }
823 return t;
824 //return EVRIGLC(this, V, begin, end);
825 }
826
827
828 /**
829 * ExpVector inverse weighted lexicographical compareTo.
830 * @param w weight array.
831 * @param V
832 * @return 0 if U == V, -1 if U < V, 1 if U > V.
833 */
834 @Override
835 public int invWeightCompareTo(long[][] w, ExpVector V) {
836 long[] u = val;
837 long[] v = ((ExpVectorLong) V).val;
838 int t = 0;
839 int i;
840 for (i = 0; i < u.length; i++) {
841 if (u[i] > v[i]) {
842 t = 1;
843 break;
844 }
845 if (u[i] < v[i]) {
846 t = -1;
847 break;
848 }
849 }
850 if (t == 0) {
851 return t;
852 }
853 for (int k = 0; k < w.length; k++) {
854 long[] wk = w[k];
855 long up = 0;
856 long vp = 0;
857 for (int j = i; j < u.length; j++) {
858 up += wk[j] * u[j];
859 vp += wk[j] * v[j];
860 }
861 if (up > vp) {
862 return 1;
863 } else if (up < vp) {
864 return -1;
865 }
866 }
867 return t;
868 //return EVIWLC(w, this, V);
869 }
870
871
872 /**
873 * ExpVector inverse weighted lexicographical compareTo.
874 * @param w weight array.
875 * @param V
876 * @param begin
877 * @param end
878 * @return 0 if U == V, -1 if U < V, 1 if U > V.
879 */
880 @Override
881 public int invWeightCompareTo(long[][] w, ExpVector V, int begin, int end) {
882 long[] u = val;
883 long[] v = ((ExpVectorLong) V).val;
884 int t = 0;
885 int i;
886 for (i = begin; i < end; i++) {
887 if (u[i] > v[i]) {
888 t = 1;
889 break;
890 }
891 if (u[i] < v[i]) {
892 t = -1;
893 break;
894 }
895 }
896 if (t == 0) {
897 return t;
898 }
899 for (int k = 0; k < w.length; k++) {
900 long[] wk = w[k];
901 long up = 0;
902 long vp = 0;
903 for (int j = i; j < end; j++) {
904 up += wk[j] * u[j];
905 vp += wk[j] * v[j];
906 }
907 if (up > vp) {
908 return 1;
909 } else if (up < vp) {
910 return -1;
911 }
912 }
913 return t;
914 //return EVIWLC(w, this, V, begin, end);
915 }
916
917 }