001/* 002 * $Id$ 003 */ 004 005package edu.jas.poly; 006 007 008import java.io.Reader; 009import java.io.Serializable; 010import java.util.ArrayList; 011import java.util.Arrays; 012import java.util.Collection; 013import java.util.Comparator; 014import java.util.List; 015import java.util.Random; 016 017import org.apache.logging.log4j.LogManager; 018import org.apache.logging.log4j.Logger; 019 020import edu.jas.kern.StringUtil; 021import edu.jas.structure.MonoidFactory; 022 023 024/** 025 * IndexList factory implements a factory for index lists for exterior 026 * polynomials. Objects of this class are intended to be immutable. If in doubt 027 * use <code>valueOf</code> to get a conformant index list. 028 * @see "masnc.DIPE.mi#ILEXPR from SAC2/MAS" 029 * @author Heinz Kredel 030 */ 031 032public class IndexFactory implements MonoidFactory<IndexList> { 033 034 035 /** 036 * The maximal length index list for this factory. 037 */ 038 public final int imaxlength; 039 040 041 /** 042 * The coordinate variable name. 043 */ 044 public final String vname; 045 046 047 /** 048 * The maximal index list for this factory. 049 */ 050 public final IndexList imax; 051 052 053 /** 054 * Defined index list comparison. 055 * Strong compare: false, weak compare: true. 056 */ 057 final boolean weak; 058 059 060 /** 061 * Random number generator. 062 */ 063 private final static Random random = new Random(); 064 065 066 /** 067 * Log4j logger object. 068 */ 069 private static final Logger logger = LogManager.getLogger(WordFactory.class); 070 071 072 /** 073 * The one element index list. 074 */ 075 public final IndexList ONE; 076 077 078 /** 079 * The default coordinate variable name. 080 */ 081 public static final String DEFAULT_VNAME = "E"; 082 083 084 /** 085 * The default imaxlength for this index lists. 086 */ 087 public static final int DEFAULT_SIZE = 4; 088 089 090 /** 091 * Constructor for IndexFactory. No argument constructor . 092 */ 093 public IndexFactory() { 094 this(DEFAULT_SIZE, DEFAULT_VNAME); 095 } 096 097 098 /** 099 * Constructor for IndexFactory. 100 * @param r length of index lists, starting with index 1. 101 */ 102 public IndexFactory(int r) { 103 this(1, r, DEFAULT_VNAME, false); 104 } 105 106 107 /** 108 * Constructor for IndexFactory. 109 * @param r length of index lists, starting with index 1. 110 * @param w termorder for index lists: true for weak, false for strong. 111 */ 112 public IndexFactory(int r, boolean w) { 113 this(1, r, DEFAULT_VNAME, w); 114 } 115 116 117 /** 118 * Constructor for IndexFactory. 119 * @param r length of index lists, starting with index 1. 120 * @param v coordinate vname. 121 */ 122 public IndexFactory(int r, String v) { 123 this(1, r, v, false); 124 } 125 126 127 /** 128 * Constructor for IndexFactory. 129 * @param r length of index lists, starting with index 1. 130 * @param v coordinate vname. 131 * @param w termorder for index lists: true for weak, false for strong. 132 */ 133 public IndexFactory(int r, String v, boolean w) { 134 this(1, r, v, w); 135 } 136 137 138 /** 139 * Constructor for IndexFactory. 140 * @param s start index. 141 * @param t length of index lists. 142 */ 143 public IndexFactory(int s, int t) { 144 this(s, t, DEFAULT_VNAME, false); 145 } 146 147 148 /** 149 * Constructor for IndexFactory. 150 * @param s start index. 151 * @param t length of index lists. 152 * @param v coordinate vname. 153 * @param w termorder for index lists: true for weak, false for strong. 154 */ 155 public IndexFactory(int s, int t, String v, boolean w) { 156 // not possible: this(new IndexList(this, 1, sequenceArray(s, t)), v); 157 if (t < 0) { 158 throw new IllegalArgumentException("negative length index not allowed"); 159 } 160 if (s < 0) { 161 throw new IllegalArgumentException("negative start index not allowed"); 162 } 163 imaxlength = t; 164 vname = v; 165 weak = w; 166 imax = new IndexList(this, 1, sequenceArray(s, imaxlength)); 167 ONE = new IndexList(this, 1, sequenceArray(s, 0)); 168 } 169 170 171 // /** not meaningful 172 // * Constructor for IndexFactory. 173 // * @param o some index list. 174 // * @param v coordinate vname. 175 // */ 176 // public IndexFactory(IndexList o, String v) { 177 // if (o == null) { 178 // throw new IllegalArgumentException("null index list not allowed"); 179 // } 180 // int b = o.minDeg(); 181 // int e = o.maxDeg(); 182 // imaxlength = e - b + 1; 183 // vname = v; 184 // imax = new IndexList(this, 1, sequenceArray(b, imaxlength)); 185 // if (imaxlength != o.length()) { 186 // logger.warn("length do not match: {} != {}", imaxlength, o.length()); 187 // } 188 // ONE = new IndexList(this, 1, sequenceArray(1, 0)); 189 // } 190 191 192 // /** 193 // * Constructor for IndexFactory. 194 // * @param o some index list. 195 // */ 196 // public IndexFactory(IndexList o) { 197 // this(o, o.mono.vname); 198 // } 199 200 201 /** 202 * Is this structure finite or infinite. 203 * @return true if this structure is finite, else false. 204 * @see edu.jas.structure.ElemFactory#isFinite() <b>Note: </b> returns true 205 * because of finite set of values in each index. 206 */ 207 public boolean isFinite() { 208 return true; 209 } 210 211 212 /** 213 * Query if this monoid is commutative. 214 * @return true if this monoid is commutative, else false. 215 */ 216 public boolean isCommutative() { 217 if (imaxlength == 0) { 218 return true; 219 } 220 return false; 221 } 222 223 224 /** 225 * Query if this monoid is associative. 226 * @return true if this monoid is associative, else false. 227 */ 228 public boolean isAssociative() { 229 return true; 230 } 231 232 233 /** 234 * Get the Element for a. 235 * @param a long 236 * @return element corresponding to a. 237 */ 238 @Override 239 public IndexList fromInteger(long a) { 240 throw new UnsupportedOperationException("not implemented for IndexFactory"); 241 } 242 243 244 /** 245 * Get the Element for a. 246 * @param a java.math.BigInteger. 247 * @return element corresponding to a. 248 */ 249 @Override 250 public IndexList fromInteger(java.math.BigInteger a) { 251 throw new UnsupportedOperationException("not implemented for IndexFactory"); 252 } 253 254 255 /** 256 * Value of other. 257 * @param e other ExpVector. 258 * @return value as IndexList. 259 */ 260 public IndexList valueOf(ExpVector e) { 261 if (e == null) { 262 return getZERO(); 263 } 264 int r = e.length(); 265 int[] w = new int[r]; 266 int ii = 0; 267 for (int i = 0; i < r; i++) { 268 long x = e.getVal(i); 269 if (x <= 0l) { 270 continue; 271 } 272 if (x > 1l) { 273 return getZERO(); 274 } 275 w[ii++] = i; 276 } 277 int[] v = Arrays.copyOf(w, ii); 278 return new IndexList(this, v); 279 } 280 281 282 /** 283 * Value of other. 284 * @param var String of index names. 285 * @return value as IndexList. 286 */ 287 public IndexList valueOf(String var) { 288 return sequence(0, var.length()); 289 } 290 291 292 /** 293 * Value of other. 294 * @param e other Collection of Integer indexes. 295 * @return value as IndexList. 296 */ 297 public IndexList valueOf(Collection<Integer> e) { 298 if (e == null) { 299 return getZERO(); 300 } 301 int r = e.size(); 302 int[] w = new int[r]; 303 int ii = 0; 304 for (Integer x : e) { 305 int xi = (int) x; 306 if (xi < 0) { 307 continue; 308 } 309 w[ii++] = xi; 310 } 311 int[] v = Arrays.copyOf(w, ii); 312 return new IndexList(this, v); 313 } 314 315 316 /** 317 * Value of other. 318 * @param e other int[] of indexes, may not be conform to IndexList 319 * specification. 320 * @return value as IndexList. 321 */ 322 public IndexList valueOf(int[] e) { 323 if (e == null) { 324 return getZERO(); 325 } 326 int r = e.length; 327 IndexList w = new IndexList(this, new int[] {}); // = 1 328 int[] v = new int[1]; 329 for (int i = 0; i < r; i++) { 330 v[0] = e[i]; 331 IndexList vs = new IndexList(this, v); 332 w = w.exteriorProduct(vs); 333 if (w.isZERO()) { 334 return w; 335 } 336 } 337 //System.out.println("valueOf: " + w); 338 return w; 339 } 340 341 342 /** 343 * Value of other. 344 * @param e other IndexList, may not be conform to IndexList specification. 345 * @return value as IndexList. 346 */ 347 public IndexList valueOf(IndexList e) { 348 if (e == null) { 349 return getZERO(); 350 } 351 return valueOf(e.val); 352 } 353 354 355 /** 356 * Generators. 357 * @return list of generators for this index list. 358 */ 359 public List<IndexList> generators() { 360 List<IndexList> gens = new ArrayList<IndexList>(); 361 //IndexList one = getONE(); 362 //gens.add(one); 363 for (int i = 0; i < imax.val.length; i++) { 364 int[] v = new int[1]; 365 v[0] = imax.val[i]; 366 IndexList vs = new IndexList(this, v); 367 gens.add(vs); 368 } 369 //System.out.println("gens: " + gens + ", val = " + Arrays.toString(val)); 370 return gens; 371 } 372 373 374 /** 375 * Clone IndexList. 376 * @see java.lang.Object#clone() 377 */ 378 @Override 379 public IndexList copy(IndexList o) { 380 if (o == null) { 381 return o; 382 } 383 return o.copy(); 384 } 385 386 387 /** 388 * Get the maximal length of index lists of this factory. 389 * @return imaxlength. 390 */ 391 public int length() { 392 return imaxlength; 393 } 394 395 396 /** 397 * Get the string representation. 398 * @see java.lang.Object#toString() 399 */ 400 @Override 401 public String toString() { 402 if (! weak) { 403 return imax.toString(); 404 } 405 StringBuffer s = new StringBuffer(imax.toString()); 406 s.append("[" + weak + "]"); 407 return s.toString(); 408 } 409 410 411 /** 412 * Get a scripting compatible string representation. 413 * @return script compatible representation for this Element. 414 * @see edu.jas.structure.Element#toScript() 415 */ 416 @Override 417 public String toScript() { 418 if (! weak) { 419 return imax.toScript(); 420 } 421 StringBuffer s = new StringBuffer(imax.toScript()); 422 s.append("[" + weak + "]"); 423 return s.toString(); 424 } 425 426 427 /** 428 * Constructor for IndexList. Converts a String representation to an 429 * IndexList. Accepted format = E(1,2,3,4,5,6,7). 430 * @param s String representation. 431 */ 432 // public IndexFactory(String s) throws NumberFormatException { 433 // this(parse(s).val); 434 // } 435 436 437 /** 438 * Parser for IndexList. Converts a String representation to an IndexList. 439 * Accepted format = E(1,2,3,4,5,6,7). 440 * @param s String representation. 441 * @return parsed IndexList 442 */ 443 public IndexList parse(String s) throws NumberFormatException { 444 int[] v = null; 445 // first format = (1,2,3,4,5,6,7) 446 List<Integer> idxs = new ArrayList<Integer>(); 447 s = s.trim(); 448 int b = s.indexOf('('); 449 int e = s.indexOf(')', b + 1); 450 String teil; 451 int k; 452 int a; 453 if (b >= 0 && e >= 0) { 454 b++; 455 while ((k = s.indexOf(',', b)) >= 0) { 456 teil = s.substring(b, k); 457 a = Integer.parseInt(teil); 458 idxs.add(Integer.valueOf(a)); 459 b = k + 1; 460 } 461 if (b <= e) { 462 teil = s.substring(b, e); 463 a = Integer.parseInt(teil); 464 idxs.add(Integer.valueOf(a)); 465 } 466 int length = idxs.size(); 467 v = new int[length]; 468 for (int j = 0; j < length; j++) { 469 v[j] = idxs.get(j).intValue(); 470 } 471 } 472 return valueOf(v); // sort and compute sign 473 } 474 475 476 /** 477 * Parse from Reader. White space is delimiter for index list. 478 * @param r Reader. 479 * @return the next Element found on r. 480 */ 481 public IndexList parse(Reader r) { 482 return parse(StringUtil.nextString(r)); 483 } 484 485 486 /** 487 * Comparison with any other object. 488 * @see java.lang.Object#equals(java.lang.Object) 489 */ 490 @Override 491 public boolean equals(Object B) { 492 if (!(B instanceof IndexFactory)) { 493 return false; 494 } 495 IndexFactory b = (IndexFactory) B; 496 int t = imax.compareTo(b.imax); 497 //System.out.println("equals: this = " + this + " B = " + B + " t = " + t); 498 return (0 == t); 499 } 500 501 502 /** 503 * hashCode. Optimized for small indexes, i.e. ≤ 2<sup>4</sup> and small 504 * number of variables, i.e. ≤ 8. 505 * @see java.lang.Object#hashCode() 506 */ 507 @Override 508 public int hashCode() { 509 int hash = imax.hashCode(); 510 return hash; 511 } 512 513 514 /** 515 * Get IndexList zero. 516 * @return 0 IndexList. 517 */ 518 public IndexList getZERO() { 519 return new IndexList(this); 520 } 521 522 523 /** 524 * Get IndexList one. 525 * @return 1 IndexList. 526 */ 527 public IndexList getONE() { 528 return ONE; //?? .copy() 529 } 530 531 532 /** 533 * Generate a random IndexList. 534 * @param r length of new IndexList. 535 * @return random IndexList. 536 */ 537 public final IndexList random(int r) { 538 return random(r, 0.5f, random); 539 } 540 541 542 /** 543 * Generate a random IndexList. 544 * @param r length of new IndexList. 545 * @param rnd is a source for random bits. 546 * @return random IndexList. 547 */ 548 public final IndexList random(int r, Random rnd) { 549 return random(r, 0.5f, rnd); 550 } 551 552 553 /** 554 * Generate a random IndexList. 555 * @param r length of new IndexList. 556 * @param q density of nozero indexes. 557 * @return random IndexList. 558 */ 559 public final IndexList random(int r, float q) { 560 return random(r, q, random); 561 } 562 563 564 /** 565 * Generate a random IndexList. 566 * @param r length of new IndexList. 567 * @param q density of nozero indexes. 568 * @param rnd is a source for random bits. 569 * @return random IndexList. 570 */ 571 public final IndexList random(int r, float q, Random rnd) { 572 if (r > imaxlength || r < 0) { 573 throw new IllegalArgumentException("r > imaxlength not allowed: " + r + " > " + imaxlength); 574 } 575 if (r == 0) { 576 return getZERO(); 577 } 578 int[] w = new int[r]; 579 int s = 1; 580 float f; 581 f = rnd.nextFloat(); 582 if (f < q * 0.001f) { 583 return getONE(); // = 0, 1 ?? 584 } 585 if (f < q * q) { 586 s = -1; 587 } 588 int ii = 0; 589 int b = Math.max(Math.min(Math.abs(rnd.nextInt()) % imaxlength, imaxlength - r - 1), 1); 590 for (int i = b; i <= imaxlength && ii < r; i++) { 591 f = rnd.nextFloat(); 592 if (f < q) { 593 w[ii++] = i; 594 } 595 } 596 int[] v = Arrays.copyOf(w, ii); 597 //System.out.println("v = " + Arrays.toString(v)); 598 //System.out.println("this = " + this); 599 return new IndexList(this, s, v); 600 } 601 602 603 /** 604 * Generate a sequence IndexList. 605 * @param s starting index. 606 * @param r length of new IndexList. 607 * @return sequence (s, s+1, ..., s+r-1) IndexList. 608 */ 609 public final IndexList sequence(int s, int r) { 610 return new IndexList(this, 1, sequenceArray(s, r)); 611 } 612 613 614 /** 615 * Generate a sequence array. 616 * @param s starting index. 617 * @param r length of array. 618 * @return sequence (s, s+1, ..., s+r-1) array. 619 */ 620 public static int[] sequenceArray(int s, int r) { 621 if (s < 0) { 622 throw new IllegalArgumentException("s < 0 not allowed: " + s + " < 0"); 623 } 624 int[] w = new int[r]; 625 for (int i = 0; i < w.length; i++) { 626 w[i] = s + i; 627 } 628 //System.out.println("v = " + Arrays.toString(w)); 629 return w; 630 } 631 632 633 /** 634 * Comparator for IndexLists. 635 */ 636 public static abstract class IndexListComparator implements Comparator<IndexList>, Serializable { 637 638 639 public abstract int compare(IndexList e1, IndexList e2); 640 } 641 642 643 /** 644 * Defined descending order comparator. Sorts the highest terms first. 645 */ 646 private final IndexListComparator horder = new IndexListComparator() { 647 648 649 @Override 650 public int compare(IndexList e1, IndexList e2) { 651 return -e1.strongCompareTo(e2); 652 } 653 }; 654 655 656 /** 657 * Defined ascending order comparator. Sorts the lowest terms first. 658 */ 659 private final IndexListComparator lorder = new IndexListComparator() { 660 661 662 @Override 663 public int compare(IndexList e1, IndexList e2) { 664 return e1.strongCompareTo(e2); 665 } 666 }; 667 668 669 /** 670 * Defined descending weak order comparator. Sorts the highest terms first. 671 */ 672 private final IndexListComparator hweak = new IndexListComparator() { 673 674 675 @Override 676 public int compare(IndexList e1, IndexList e2) { 677 return -e1.weakCompareTo(e2); 678 } 679 }; 680 681 682 /** 683 * Defined ascending weak order comparator. Sorts the lowest terms first. 684 */ 685 private final IndexListComparator lweak = new IndexListComparator() { 686 687 688 @Override 689 public int compare(IndexList e1, IndexList e2) { 690 return e1.weakCompareTo(e2); 691 } 692 }; 693 694 695 /** 696 * Get the descending order comparator. Sorts the highest terms first. 697 * @return horder. 698 */ 699 public IndexListComparator getDescendComparator() { 700 if (weak) { 701 return hweak; 702 } 703 return horder; 704 } 705 706 707 /** 708 * Get the ascending order comparator. Sorts the lowest terms first. 709 * @return lorder. 710 */ 711 public IndexListComparator getAscendComparator() { 712 if (weak) { 713 return lweak; 714 } 715 return lorder; 716 } 717 718}