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