001/* 002 * $Id: WordFactory.java 5182 2015-04-01 21:12:44Z kredel $ 003 */ 004 005package edu.jas.poly; 006 007 008import java.io.Reader; 009import java.io.Serializable; 010import java.math.BigInteger; 011import java.util.ArrayList; 012import java.util.Arrays; 013import java.util.Comparator; 014import java.util.List; 015import java.util.Random; 016 017import org.apache.log4j.Logger; 018 019import edu.jas.kern.StringUtil; 020import edu.jas.structure.MonoidFactory; 021 022 023/** 024 * WordFactory implements alphabet related methods. 025 * @author Heinz Kredel 026 */ 027 028public final class WordFactory implements MonoidFactory<Word> { 029 030 031 /** 032 * The data structure is a String of characters which defines the alphabet. 033 */ 034 /*package*/final String alphabet; 035 036 037 /** 038 * The empty word for this monoid. 039 */ 040 public final Word ONE; 041 042 043 /** 044 * The translation reference string. 045 */ 046 public static final String transRef = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; 047 048 049 /** 050 * The translation array of Strings. 051 */ 052 public final String[] translation; 053 054 055 /** 056 * Random number generator. 057 */ 058 private final static Random random = new Random(); 059 060 061 /** 062 * Log4j logger object. 063 */ 064 private static final Logger logger = Logger.getLogger(WordFactory.class); 065 066 067 /** 068 * Comparator for Words. 069 */ 070 public static abstract class WordComparator implements Comparator<Word>, Serializable { 071 072 073 public abstract int compare(Word e1, Word e2); 074 } 075 076 077 /** 078 * Defined descending order comparator. Sorts the highest terms first. 079 */ 080 private static final WordComparator horder = new WordComparator() { 081 082 083 @Override 084 public int compare(Word e1, Word e2) { 085 //return e1.gradCompareTo(e2); 086 return e1.gradInvlexCompareTo(e2); 087 } 088 }; 089 090 091 /** 092 * Defined ascending order comparator. Sorts the lowest terms first. 093 */ 094 private static final WordComparator lorder = new WordComparator() { 095 096 097 @Override 098 public int compare(Word e1, Word e2) { 099 //return -e1.gradCompareTo(e2); 100 return -e1.gradInvlexCompareTo(e2); 101 } 102 }; 103 104 105 /** 106 * Constructor for WordFactory. 107 */ 108 public WordFactory() { 109 this(""); 110 } 111 112 113 /** 114 * Constructor for WordFactory. 115 * @param s String of single letters for alphabet 116 */ 117 public WordFactory(String s) { 118 if (s == null) { 119 throw new IllegalArgumentException("null string not allowed"); 120 } 121 alphabet = cleanSpace(s); 122 translation = null; 123 ONE = new Word(this, "", false); 124 } 125 126 127 /** 128 * Constructor for WordFactory. 129 * @param S String array for alphabet 130 */ 131 public WordFactory(String[] S) { 132 String[] V = cleanAll(S); 133 if (isSingleLetters(V)) { 134 alphabet = concat(V); 135 translation = null; 136 } else { 137 alphabet = transRef.substring(0, V.length); 138 translation = V; 139 logger.info("alphabet = " + alphabet + ", translation = " + Arrays.toString(translation)); 140 } 141 ONE = new Word(this, "", false); 142 } 143 144 145 /** 146 * Is this structure finite or infinite. 147 * @return true if this structure is finite, else false. 148 * @see edu.jas.structure.ElemFactory#isFinite() 149 */ 150 public boolean isFinite() { 151 if (alphabet.length() == 0) { 152 return true; 153 } 154 return false; 155 } 156 157 158 /** 159 * Query if this monoid is commutative. 160 * @return true if this monoid is commutative, else false. 161 */ 162 public boolean isCommutative() { 163 if (alphabet.length() == 0) { 164 return true; 165 } 166 return false; 167 } 168 169 170 /** 171 * Query if this monoid is associative. 172 * @return true if this monoid is associative, else false. 173 */ 174 public boolean isAssociative() { 175 return true; 176 } 177 178 179 /** 180 * Get the one element, the empty word. 181 * @return 1 as Word. 182 */ 183 public Word getONE() { 184 return ONE; 185 } 186 187 188 /** 189 * Copy word. 190 * @param w word to copy. 191 * @return copy of w. 192 */ 193 @Override 194 public Word copy(Word w) { 195 return new Word(this, w.getVal(), false); 196 } 197 198 199 /** 200 * Get the alphabet length. 201 * @return alphabet.length. 202 */ 203 public int length() { 204 return alphabet.length(); 205 } 206 207 208 /** 209 * Get the alphabet String. 210 * @return alphabet. 211 */ 212 /*package*/String getVal() { 213 return alphabet; 214 } 215 216 217 /** 218 * Get the translation array of Strings. 219 * @return alphabet. 220 */ 221 /*package*/String[] getTrans() { 222 return translation; 223 } 224 225 226 /** 227 * Get the alphabet letter at position i. 228 * @param i position. 229 * @return val[i]. 230 */ 231 public char getVal(int i) { 232 return alphabet.charAt(i); 233 } 234 235 236 /** 237 * Get the variable names. 238 * @return array of variable names 239 */ 240 public String[] getVars() { 241 String[] vars = new String[alphabet.length()]; 242 if (translation == null) { 243 for (int i = 0; i < alphabet.length(); i++) { 244 vars[i] = String.valueOf(getVal(i)); 245 } 246 } else { 247 for (int i = 0; i < alphabet.length(); i++) { 248 vars[i] = translation[i]; 249 } 250 } 251 return vars; 252 } 253 254 255 /** 256 * Get the string representation. 257 * @see java.lang.Object#toString() 258 */ 259 @Override 260 public String toString() { 261 StringBuffer s = new StringBuffer("\""); 262 if (translation == null) { 263 for (int i = 0; i < alphabet.length(); i++) { 264 if (i != 0) { 265 s.append(","); 266 } 267 s.append(getVal(i)); 268 } 269 } else { 270 for (int i = 0; i < alphabet.length(); i++) { 271 if (i != 0) { 272 s.append(","); 273 } 274 s.append(translation[i]); 275 } 276 } 277 s.append("\""); 278 return s.toString(); 279 } 280 281 282 /** 283 * Get a scripting compatible string representation. 284 * @return script compatible representation for this Element. 285 * @see edu.jas.structure.Element#toScript() 286 */ 287 @Override 288 public String toScript() { 289 return toString(); 290 } 291 292 293 /** 294 * Comparison with any other object. 295 * @see java.lang.Object#equals(java.lang.Object) 296 */ 297 @Override 298 public boolean equals(Object B) { 299 if (!(B instanceof WordFactory)) { 300 return false; 301 } 302 WordFactory b = (WordFactory) B; 303 return alphabet.equals(b.alphabet); 304 } 305 306 307 /** 308 * hashCode. 309 * @see java.lang.Object#hashCode() 310 */ 311 @Override 312 public int hashCode() { 313 return alphabet.hashCode(); 314 } 315 316 317 /** 318 * Get a list of the generating elements. 319 * @return list of generators for the algebraic structure. 320 */ 321 public List<Word> generators() { 322 int len = alphabet.length(); 323 List<Word> gens = new ArrayList<Word>(len); 324 //gens.add(ONE); not a word generator 325 // todo 326 for (int i = 0; i < len; i++) { 327 Word w = new Word(this, String.valueOf(alphabet.charAt(i)), false); 328 gens.add(w); 329 } 330 return gens; 331 } 332 333 334 /** 335 * Get the Element for a. 336 * @param a long 337 * @return element corresponding to a. 338 */ 339 public Word fromInteger(long a) { 340 throw new UnsupportedOperationException("not implemented for WordFactory"); 341 } 342 343 344 /** 345 * Get the Element for a. 346 * @param a java.math.BigInteger. 347 * @return element corresponding to a. 348 */ 349 public Word fromInteger(BigInteger a) { 350 throw new UnsupportedOperationException("not implemented for WordFactory"); 351 } 352 353 354 /** 355 * Get the Element for an ExpVector. 356 * @param e ExpVector. 357 * @return element corresponding to e. 358 */ 359 public Word valueOf(ExpVector e) { 360 Word w = ONE; 361 List<Word> gens = generators(); 362 int n = alphabet.length(); 363 int m = e.length(); 364 if (m > n) { 365 throw new IllegalArgumentException("alphabet to short for exponent " + e + ", alpahbet = " 366 + alphabet); 367 } 368 for (int i = 0; i < m; i++) { 369 int x = (int) e.getVal(m - i - 1); 370 Word y = gens.get(i); 371 Word u = ONE; 372 for (int j = 0; j < x; j++) { 373 u = u.multiply(y); 374 } 375 w = w.multiply(u); 376 } 377 return w; 378 } 379 380 381 /** 382 * IndexOf for letter in alphabet. 383 * @param s letter character. 384 * @return index of s in the alphabet, or -1 if s is not contained in the alphabet. 385 */ 386 public int indexOf(char s) { 387 return alphabet.indexOf(s); 388 } 389 390 391 /** 392 * Generate a random Element with size less equal to n. 393 * @param n 394 * @return a random element. 395 */ 396 public Word random(int n) { 397 return random(n, random); 398 } 399 400 401 /** 402 * Generate a random Element with size less equal to n. 403 * @param n 404 * @param random is a source for random bits. 405 * @return a random element. 406 */ 407 public Word random(int n, Random random) { 408 StringBuffer sb = new StringBuffer(); 409 int len = alphabet.length(); 410 for (int i = 0; i < n; i++) { 411 int r = Math.abs(random.nextInt() % len); 412 sb.append(alphabet.charAt(r)); 413 } 414 return new Word(this, sb.toString(), false); 415 } 416 417 418 /** 419 * Parse from String. 420 * @param s String. 421 * @return a Element corresponding to s. 422 */ 423 public Word parse(String s) { 424 String st = clean(s); 425 String regex; 426 if (translation == null) { 427 regex = "[" + alphabet + " ]*"; 428 } else { 429 regex = "[" + concat(translation) + " ]*"; 430 } 431 if (!st.matches(regex)) { 432 throw new IllegalArgumentException("word '" + st + "' contains letters not from: " + alphabet 433 + " or from " + concat(translation)); 434 } 435 // todo 436 return new Word(this, st, true); 437 } 438 439 440 /** 441 * Parse from Reader. White space is delimiter for word. 442 * @param r Reader. 443 * @return the next Element found on r. 444 */ 445 public Word parse(Reader r) { 446 return parse(StringUtil.nextString(r)); 447 } 448 449 450 /** 451 * Get the descending order comparator. Sorts the highest terms first. 452 * @return horder. 453 */ 454 public WordComparator getDescendComparator() { 455 return horder; 456 } 457 458 459 /** 460 * Get the ascending order comparator. Sorts the lowest terms first. 461 * @return lorder. 462 */ 463 public WordComparator getAscendComparator() { 464 return lorder; 465 } 466 467 468 /** 469 * Prepare parse from String. 470 * @param s String. 471 * @return a Element corresponding to s. 472 */ 473 public static String cleanSpace(String s) { 474 String st = s.trim(); 475 st = st.replaceAll("\\*", ""); 476 st = st.replaceAll("\\s", ""); 477 st = st.replaceAll("\\(", ""); 478 st = st.replaceAll("\\)", ""); 479 st = st.replaceAll("\\\"", ""); 480 return st; 481 } 482 483 484 /** 485 * Prepare parse from String. 486 * @param s String. 487 * @return a Element corresponding to s. 488 */ 489 public static String clean(String s) { 490 String st = s.trim(); 491 st = st.replaceAll("\\*", " "); 492 //st = st.replaceAll("\\s", ""); 493 st = st.replaceAll("\\(", ""); 494 st = st.replaceAll("\\)", ""); 495 st = st.replaceAll("\\\"", ""); 496 return st; 497 } 498 499 500 /** 501 * Prepare parse from String array. 502 * @param v String array. 503 * @return an array of cleaned strings. 504 */ 505 public static String[] cleanAll(String[] v) { 506 String[] t = new String[v.length]; 507 for (int i = 0; i < v.length; i++) { 508 t[i] = cleanSpace(v[i]); 509 if (t[i].length() == 0) { 510 logger.error("empty v[i]: '" + v[i] + "'"); 511 } 512 //System.out.println("clean all: " + v[i] + " --> " + t[i]); 513 } 514 return t; 515 } 516 517 518 /** 519 * Concat variable names. 520 * @param v an array of strings. 521 * @return the concatination of the strings in v. 522 */ 523 public static String concat(String[] v) { 524 StringBuffer s = new StringBuffer(); 525 if (v == null) { 526 return s.toString(); 527 } 528 for (int i = 0; i < v.length; i++) { 529 //String a = v[i]; 530 //if ( a.length() != 1 ) { 531 // //logger.error("v[i] not single letter "+ a); 532 // a = a.substring(0,1); 533 //} 534 s.append(v[i]); 535 } 536 return s.toString(); 537 } 538 539 540 /** 541 * Trim all variable names. 542 * @param v an array of strings. 543 * @return an array of strings with all elements trimmed. 544 */ 545 public static String[] trimAll(String[] v) { 546 String[] t = new String[v.length]; 547 for (int i = 0; i < v.length; i++) { 548 t[i] = v[i].trim(); 549 if (t[i].length() == 0) { 550 logger.error("empty v[i]: '" + v[i] + "'"); 551 } 552 } 553 return t; 554 } 555 556 557 /** 558 * IndexOf for String array. 559 * @param v an array of strings. 560 * @param s string. 561 * @return index of s in v, or -1 if s is not contained in v. 562 */ 563 public static int indexOf(String[] v, String s) { 564 for (int i = 0; i < v.length; i++) { 565 if (s.equals(v[i])) { 566 return i; 567 } 568 } 569 return -1; 570 } 571 572 573 /** 574 * Test if all variables are single letters. 575 * @param v an array of strings. 576 * @return true, if all variables have length 1, else false. 577 */ 578 public static boolean isSingleLetters(String[] v) { 579 for (int i = 0; i < v.length; i++) { 580 if (v[i].length() != 1) { 581 return false; 582 } 583 } 584 return true; 585 } 586 587 588 /** 589 * Translate variable names. 590 * @param v an array of strings. 591 * @return the translated string of v with respect to t. 592 */ 593 public String translate(String[] v) { 594 StringBuffer s = new StringBuffer(); 595 for (int i = 0; i < v.length; i++) { 596 String a = v[i]; 597 int k = indexOf(translation, a); 598 if (k < 0) { 599 System.out.println("t = " + Arrays.toString(translation)); 600 System.out.println("v = " + Arrays.toString(v)); 601 logger.error("v[i] not found in t: " + a); 602 //continue; 603 throw new IllegalArgumentException("v[i] not found in t: " + a); 604 } 605 s.append(transRef.charAt(k)); 606 } 607 return s.toString(); 608 } 609 610 611 /** 612 * Translate variable name. 613 * @param c internal char. 614 * @return the extenal translated string. 615 */ 616 public String transVar(char c) { 617 int k = alphabet.indexOf(c); 618 return translation[k]; 619 } 620 621}