001/* 002 * $Id$ 003 */ 004 005package edu.jas.poly; 006 007 008import java.util.Arrays; 009 010import edu.jas.arith.BigInteger; 011import edu.jas.structure.MonoidElem; 012import edu.jas.structure.MonoidFactory; 013 014 015/** 016 * IndexList implements index lists for exterior polynomials. Index lists are 017 * implemented as arrays of Java int type. Objects of this class are intended to 018 * be immutable, except for the sign. If in doubt use <code>valueOf</code> to 019 * get a conformant index list. 020 * @see "masnc.DIPE.mi#ILEXPR from SAC2/MAS" 021 * @author Heinz Kredel 022 */ 023 024public class IndexList implements MonoidElem<IndexList> { 025 026 027 /** 028 * Representation of index list as int arrays. 029 */ 030 public final int[] val; // != null, when s != 0 031 032 033 /** 034 * Sign of index list. 035 */ 036 public int sign; // = -1, 0, 1 037 038 039 /** 040 * Reference to IndexFactory. 041 */ 042 public final IndexFactory mono; 043 044 045 /** 046 * Constructor for IndexList. No argument constructor defining 0 index list. 047 */ 048 public IndexList(IndexFactory m) { 049 this(m, 0, null); 050 } 051 052 053 /** 054 * Constructor for IndexList. 055 * @param v array with indices. 056 */ 057 public IndexList(IndexFactory m, int[] v) { 058 this(m, 1, v); 059 } 060 061 062 /** 063 * Constructor for IndexList. <b>Note:</b> A copy of v is internally 064 * created. 065 * @param s sign of index list. 066 * @param v array with indices. 067 */ 068 public IndexList(IndexFactory m, int s, int[] v) { 069 sign = s; 070 mono = m; 071 if (v == null) { 072 if (s != 0) { 073 throw new IllegalArgumentException("inconsistent: s = " + s + ", v = " + v); 074 } 075 val = v; 076 sign = 0; // only when exception deactivated 077 } else { 078 val = Arrays.copyOf(v, v.length); 079 } 080 //if (v != null && v.length > 0) System.out.println("v[0]: " + v[0]); 081 } 082 083 084 /** 085 * Constructor for IndexList. Converts a String representation to an 086 * IndexList. Accepted format = E(1,2,3,4,5,6,7). 087 * @param s String representation. 088 */ 089 public IndexList(IndexFactory m, String s) throws NumberFormatException { 090 this(m, m.parse(s).val); 091 } 092 093 094 /** 095 * Get the corresponding element factory. 096 * @return factory for this Element. 097 * @see edu.jas.structure.Element#factory() 098 */ 099 public MonoidFactory<IndexList> factory() { 100 return mono; //(MonoidFactory<IndexList>) this; 101 //throw new UnsupportedOperationException("no factory implemented for IndexList"); 102 } 103 104 105 /** 106 * Check for IndexList conformant specification. 107 * @return true if this a a conformant IndexList, else false. 108 */ 109 public boolean isConformant() { 110 if (sign == 0 && val == null) { 111 return true; 112 } 113 IndexList ck = mono.valueOf(val); 114 return this.abs().equals(ck.abs()); 115 } 116 117 118 /** 119 * Clone this. 120 * @see java.lang.Object#clone() 121 */ 122 @Override 123 public IndexList copy() { 124 return new IndexList(mono, sign, val); 125 } 126 127 128 /** 129 * Get the index vector. 130 * @return val. 131 */ 132 public int[] getVal() { 133 return val; 134 } 135 136 137 /** 138 * Get the index at position i. 139 * @param i position. 140 * @return val[i]. 141 */ 142 public int getVal(int i) { 143 return val[i]; 144 } 145 146 147 /** 148 * Set the index at position i to e. 149 * @param i position 150 * @param e new index 151 * @return old val[i]. 152 */ 153 protected int setVal(int i, int e) { 154 int v = val[i]; 155 val[i] = e; 156 return v; 157 } 158 159 160 /** 161 * Get the length of this index list. 162 * @return val.length or -1 for 0 index list. 163 */ 164 public int length() { 165 if (sign == 0) { 166 return -1; 167 } 168 return val.length; 169 } 170 171 172 /** 173 * Get the string representation. 174 * @see java.lang.Object#toString() 175 */ 176 @Override 177 public String toString() { 178 //System.out.println("(" + sign + ", " + Arrays.toString(val) + ")"); 179 if (sign == 0) { 180 return "0"; 181 } 182 StringBuffer s = new StringBuffer(); 183 if (sign > 0) { 184 s.append(mono.vname + "("); 185 } else { 186 s.append(mono.vname + "[-1]("); 187 } 188 for (int i = 0; i < length(); i++) { 189 s.append(getVal(i)); 190 if (i < length() - 1) { 191 s.append(","); 192 } 193 } 194 s.append(")"); 195 return s.toString(); 196 } 197 198 199 /** 200 * Get a scripting compatible string representation. 201 * @return script compatible representation for this Element. 202 * @see edu.jas.structure.Element#toScript() 203 */ 204 @Override 205 public String toScript() { 206 return toString(); 207 } 208 209 210 /** 211 * Get a scripting compatible string representation of the factory. 212 * @return script compatible representation for this ElemFactory. 213 * @see edu.jas.structure.Element#toScriptFactory() 214 */ 215 @Override 216 public String toScriptFactory() { 217 // Python case 218 return "IndexFactory()"; 219 } 220 221 222 /** 223 * Comparison with any other object. 224 * @see java.lang.Object#equals(java.lang.Object) 225 */ 226 @Override 227 public boolean equals(Object B) { 228 if (!(B instanceof IndexList)) { 229 return false; 230 } 231 IndexList b = (IndexList) B; 232 int t = this.compareTo(b); 233 //System.out.println("equals: this = " + this + " B = " + B + " t = " + t); 234 return (0 == t); 235 } 236 237 238 /** 239 * hashCode. Optimized for small indexes, i.e. ≤ 2<sup>4</sup> and small 240 * number of variables, i.e. ≤ 8. 241 * @see java.lang.Object#hashCode() 242 */ 243 @Override 244 public int hashCode() { 245 int hash = Arrays.hashCode(val) + sign; 246 return hash; 247 } 248 249 250 /** 251 * Returns the number of bits in the representation of this index vector. 252 * @return number of bits in the representation of this IndexList, including 253 * sign bits. 254 */ 255 public long bitLength() { 256 long blen = 2; // sign 257 for (int i = 0; i < val.length; i++) { 258 blen += BigInteger.bitLength(val[i]); 259 } 260 return blen; 261 } 262 263 264 /** 265 * Is IndexList zero. 266 * @return If this sign is 0 then true is returned, else false. 267 */ 268 public boolean isZERO() { 269 return (sign == 0); 270 } 271 272 273 /** 274 * Is IndexList one. 275 * @return If this sign != 0 and length val is zero then true returned, else 276 * false. 277 */ 278 public boolean isONE() { 279 return (sign != 0 && val.length == 0); 280 } 281 282 283 /** 284 * Is IndexList a unit. 285 * @return If this is a unit then true is returned, else false. 286 */ 287 public boolean isUnit() { 288 return isONE() || negate().isONE(); 289 } 290 291 292 /** 293 * IndexList absolute value. 294 * @return abs(this). 295 */ 296 public IndexList abs() { 297 if (sign >= 0) { 298 return this; 299 } 300 return new IndexList(mono, 1, val); 301 } 302 303 304 /** 305 * IndexList negate. 306 * @return -this. 307 */ 308 public IndexList negate() { 309 if (sign == 0) { 310 return this; 311 } 312 return new IndexList(mono, -sign, val); 313 } 314 315 316 /** 317 * IndexList exterior product. Also called wegde product. 318 * @param V other index list 319 * @return this /\ V. 320 */ 321 public IndexList exteriorProduct(IndexList V) { 322 if (isZERO() || V.isZERO()) { 323 return mono.getZERO(); // = 0 324 } 325 int s = 1; 326 int m = 0, n = 0; // todo: remove or rename 327 int[] u = val; 328 int[] v = V.val; 329 int ii = 0; 330 int[] w = new int[u.length + v.length]; 331 int i = 0, j = 0; 332 while (i < u.length && j < v.length) { 333 int ul = u[i]; 334 int vl = v[j]; 335 if (ul == vl) { 336 return mono.getZERO(); // = 0 337 } 338 if (ul < vl) { 339 w[ii++] = ul; 340 i++; 341 m++; 342 } else { 343 w[ii++] = vl; 344 j++; 345 n++; 346 if (m % 2 != 0) { 347 s = -s; 348 } 349 } 350 } 351 if (i == u.length) { 352 while (j < v.length) { 353 w[ii++] = v[j++]; 354 } 355 } else { 356 m += u.length - i; // - 1; 357 while (i < u.length) { 358 w[ii++] = u[i++]; 359 } 360 } 361 if (m % 2 != 0 && n % 2 != 0) { 362 s = -s; 363 } 364 //System.out.println("i = " + i + ", j = " + j + ", m = " + m + ", n = " + n); 365 //System.out.println("s = " + s + ", w = " + Arrays.toString(w)); 366 //int[] x = Arrays.copyOf(w, ii); 367 return new IndexList(mono, s, w); 368 } 369 370 371 /** 372 * IndexList multiply. <b>Note:</b> implemented by exteriorProduct. 373 * @param V other index list 374 * @return this * V. 375 */ 376 public IndexList multiply(IndexList V) { 377 return exteriorProduct(V); 378 } 379 380 381 /** 382 * IndexList interior left product. 383 * @param V other index list 384 * @return this _| V. 385 */ 386 public IndexList interiorLeftProduct(IndexList V) { 387 return V.interiorRightProduct(this); 388 } 389 390 391 /** 392 * IndexList interior right product. 393 * @param V other index list 394 * @return this |_ V. 395 */ 396 public IndexList interiorRightProduct(IndexList V) { 397 if (!this.divides(V)) { 398 return mono.getZERO(); // = 0 399 } 400 int[] u = val; 401 int[] v = V.val; 402 int[] w = new int[v.length - u.length]; 403 int ii = 0; 404 int s = 1; 405 int m = 0; // todo: remove or rename 406 for (int i = 0; i < v.length; i++) { 407 int vl = v[i]; 408 boolean found = false; 409 for (int j = 0; j < u.length; j++) { 410 if (vl == u[j]) { 411 found = true; 412 break; 413 } 414 } 415 if (!found) { 416 w[ii++] = vl; 417 m++; 418 } else { 419 if (m % 2 != 0) { 420 s = -s; 421 } 422 } 423 } 424 //int[] x = Arrays.copyOf(w, ii); 425 return new IndexList(mono, s, w); 426 } 427 428 429 /** 430 * IndexList divides test. Test if this is contained in V. 431 * @param V other index list 432 * @return true if this divides V, else false. 433 */ 434 public boolean divides(IndexList V) { 435 if (isZERO() || V.isZERO()) { 436 return false; 437 } 438 if (val.length > V.val.length) { 439 return false; 440 } 441 int[] vval = V.val; 442 for (int i = 0; i < val.length; i++) { 443 int v = val[i]; 444 boolean found = false; 445 for (int j = i; j < vval.length; j++) { 446 if (v == vval[j]) { 447 found = true; 448 break; 449 } 450 } 451 if (!found) { 452 return false; 453 } 454 } 455 return true; 456 } 457 458 459 /** 460 * IndexList inverse. <b>Note:</b> not implemented. 461 * @return 1 / this. 462 */ 463 public IndexList inverse() { 464 throw new UnsupportedOperationException("inverse not implemented"); 465 } 466 467 468 /** 469 * IndexList divide. <b>Note:</b> experimental. 470 * @param V other IndexList. 471 * @return this/V. <b>Note:</b> computed as interiorRightProduct, eventually 472 * useful. 473 */ 474 public IndexList divide(IndexList V) { 475 return interiorRightProduct(V); 476 //throw new UnsupportedOperationException("divide not implemented"); 477 } 478 479 480 /** 481 * IndexList remainder. <b>Note:</b> not implemented. 482 * @param V other IndexList. 483 * @return this - (this/V). <b>Note:</b> not useful. 484 */ 485 public IndexList remainder(IndexList V) { 486 throw new UnsupportedOperationException("remainder not implemented"); 487 } 488 489 490 /** 491 * IndexList signum. 492 * @return sign; 493 */ 494 public int signum() { 495 return sign; 496 } 497 498 499 /** 500 * IndexList degree. 501 * @return number of of all indexes. 502 */ 503 public int degree() { 504 if (sign == 0) { 505 return -1; 506 } 507 return val.length; 508 } 509 510 511 /** 512 * IndexList maximal degree. 513 * @return maximal index. 514 */ 515 public int maxDeg() { 516 if (degree() < 1) { 517 return -1; 518 } 519 return val[val.length - 1]; 520 } 521 522 523 /** 524 * IndexList minimal degree. 525 * @return minimal index. 526 */ 527 public int minDeg() { 528 if (degree() < 1) { 529 return -1; 530 } 531 return val[0]; 532 } 533 534 535 /** 536 * IndexList compareTo. 537 * @param V other index list 538 * @return 0 if U == V, -1 if U < V, 1 if U > V. 539 */ 540 @Override 541 public int compareTo(IndexList V) { 542 return strongCompareTo(V); 543 } 544 545 546 /** 547 * IndexList weakCompareTo. Ignoring the degree in first pass. 548 * @param V other index list 549 * @return 0 if U == V, -1 if U < V, 1 if U > V. 550 */ 551 public int weakCompareTo(IndexList V) { 552 if (sign == 0 && V.sign == 0) { 553 return 0; 554 } 555 if (sign == 0) { 556 return -1; 557 } 558 if (V.sign == 0) { 559 return +1; 560 } 561 // both not zero 562 if (sign < V.sign) { 563 return -1; 564 } 565 if (sign > V.sign) { 566 return 1; 567 } 568 // both have same sign 569 int[] vval = V.val; 570 int m = Math.min(val.length, vval.length); 571 for (int i = 0; i < m; i++) { 572 if (val[i] < vval[i]) { 573 return -1; 574 } 575 if (val[i] > vval[i]) { 576 return 1; 577 } 578 } 579 if (val.length < vval.length) { 580 return -1; 581 } 582 if (val.length > vval.length) { 583 return 1; 584 } 585 return 0; 586 } 587 588 589 /** 590 * IndexList strongCompareTo. Sort by degree in first pass, then by indices. 591 * @param V other index list 592 * @return 0 if U == V, -1 if U < V, 1 if U > V. 593 */ 594 public int strongCompareTo(IndexList V) { 595 if (sign == 0 && V.sign == 0) { 596 return 0; 597 } 598 if (sign == 0) { 599 return -1; 600 } 601 if (V.sign == 0) { 602 return +1; 603 } 604 // both not zero :: ignore sign 605 int[] vval = V.val; 606 if (val.length < vval.length) { 607 return -1; 608 } 609 if (val.length > vval.length) { 610 return 1; 611 } 612 int m = Math.min(val.length, vval.length); 613 int tl = 0; 614 for (int i = 0; i < m; i++) { 615 if (val[i] < vval[i]) { 616 tl = -1; 617 break; 618 } 619 if (val[i] > vval[i]) { 620 tl = 1; 621 break; 622 } 623 } 624 // now val.length == vval.length 625 return tl; 626 } 627 628}