001/* 002 * $Id: WordFactory.java 4225 2012-09-29 20:27:56Z 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() <b>Note: </b> returns true 149 * because of finite String value. 150 */ 151 public boolean isFinite() { 152 if (alphabet.length() == 0) { 153 return true; 154 } 155 return false; 156 } 157 158 159 /** 160 * Query if this monoid is commutative. 161 * @return true if this monoid is commutative, else false. 162 */ 163 public boolean isCommutative() { 164 return false; 165 } 166 167 168 /** 169 * Query if this monoid is associative. 170 * @return true if this monoid is associative, else false. 171 */ 172 public boolean isAssociative() { 173 return true; 174 } 175 176 177 /** 178 * Get the one element, the empty word. 179 * @return 1 as Word. 180 */ 181 public Word getONE() { 182 return ONE; 183 } 184 185 186 /** 187 * Copy word. 188 * @param w word to copy. 189 * @return copy of w. 190 */ 191 @Override 192 public Word copy(Word w) { 193 return new Word(this, w.getVal(), false); 194 } 195 196 197 /** 198 * Get the alphabet length. 199 * @return alphabet.length. 200 */ 201 public int length() { 202 return alphabet.length(); 203 } 204 205 206 /** 207 * Get the alphabet String. 208 * @return alphabet. 209 */ 210 /*package*/String getVal() { 211 return alphabet; 212 } 213 214 215 /** 216 * Get the translation array of Strings. 217 * @return alphabet. 218 */ 219 /*package*/String[] getTrans() { 220 return translation; 221 } 222 223 224 /** 225 * Get the alphabet letter at position i. 226 * @param i position. 227 * @return val[i]. 228 */ 229 public char getVal(int i) { 230 return alphabet.charAt(i); 231 } 232 233 234 /** 235 * Get the string representation. 236 * @see java.lang.Object#toString() 237 */ 238 @Override 239 public String toString() { 240 StringBuffer s = new StringBuffer("\""); 241 if ( translation == null ) { 242 for (int i = 0; i < alphabet.length(); i++) { 243 if (i != 0) { 244 s.append(","); 245 } 246 s.append(getVal(i)); 247 } 248 } else { 249 for (int i = 0; i < alphabet.length(); i++) { 250 if (i != 0) { 251 s.append(","); 252 } 253 s.append(translation[i]); 254 } 255 } 256 s.append("\""); 257 return s.toString(); 258 } 259 260 261 /** 262 * Get a scripting compatible string representation. 263 * @return script compatible representation for this Element. 264 * @see edu.jas.structure.Element#toScript() 265 */ 266 //JAVA6only: @Override 267 public String toScript() { 268 return toString(); 269 } 270 271 272 /** 273 * Comparison with any other object. 274 * @see java.lang.Object#equals(java.lang.Object) 275 */ 276 @Override 277 public boolean equals(Object B) { 278 if (!(B instanceof WordFactory)) { 279 return false; 280 } 281 WordFactory b = (WordFactory) B; 282 return alphabet.equals(b.alphabet); 283 } 284 285 286 /** 287 * hashCode. 288 * @see java.lang.Object#hashCode() 289 */ 290 @Override 291 public int hashCode() { 292 return alphabet.hashCode(); 293 } 294 295 296 /** 297 * Get a list of the generating elements. 298 * @return list of generators for the algebraic structure. 299 */ 300 public List<Word> generators() { 301 int len = alphabet.length(); 302 List<Word> gens = new ArrayList<Word>(len); 303 //gens.add(ONE); not a word generator 304 // todo 305 for (int i = 0; i < len; i++) { 306 Word w = new Word(this, String.valueOf(alphabet.charAt(i)), false); 307 gens.add(w); 308 } 309 return gens; 310 } 311 312 313 /** 314 * Get the Element for a. 315 * @param a long 316 * @return element corresponding to a. 317 */ 318 public Word fromInteger(long a) { 319 throw new UnsupportedOperationException("not implemented for WordFactory"); 320 } 321 322 323 /** 324 * Get the Element for a. 325 * @param a java.math.BigInteger. 326 * @return element corresponding to a. 327 */ 328 public Word fromInteger(BigInteger a) { 329 throw new UnsupportedOperationException("not implemented for WordFactory"); 330 } 331 332 333 /** 334 * Get the Element for an ExpVector. 335 * @param e ExpVector. 336 * @return element corresponding to e. 337 */ 338 public Word valueOf(ExpVector e) { 339 Word w = ONE; 340 List<Word> gens = generators(); 341 int n = alphabet.length(); 342 int m = e.length(); 343 if (m > n) { 344 throw new IllegalArgumentException("alphabet to short for exponent " + e + ", alpahbet = " + alphabet); 345 } 346 for ( int i = 0; i < m; i++ ) { 347 int x = (int) e.getVal(m-i-1); 348 Word y = gens.get(i); 349 Word u = ONE; 350 for ( int j = 0; j < x; j++ ) { 351 u = u.multiply(y); 352 } 353 w = w.multiply(u); 354 } 355 return w; 356 } 357 358 359 /** 360 * Generate a random Element with size less equal to n. 361 * @param n 362 * @return a random element. 363 */ 364 public Word random(int n) { 365 return random(n, random); 366 } 367 368 369 /** 370 * Generate a random Element with size less equal to n. 371 * @param n 372 * @param random is a source for random bits. 373 * @return a random element. 374 */ 375 public Word random(int n, Random random) { 376 StringBuffer sb = new StringBuffer(); 377 int len = alphabet.length(); 378 for (int i = 0; i < n; i++) { 379 int r = Math.abs(random.nextInt() % len); 380 sb.append(alphabet.charAt(r)); 381 } 382 return new Word(this, sb.toString(), false); 383 } 384 385 386 /** 387 * Parse from String. 388 * @param s String. 389 * @return a Element corresponding to s. 390 */ 391 public Word parse(String s) { 392 String st = clean(s); 393 String regex; 394 if ( translation == null ) { 395 regex = "[" + alphabet + " ]*"; 396 } else { 397 regex = "[" + concat(translation) + " ]*"; 398 } 399 if (!st.matches(regex)) { 400 throw new IllegalArgumentException("word '" + st + "' contains letters not from: " 401 + alphabet + " or from " + concat(translation)); 402 } 403 // todo 404 return new Word(this, st, true); 405 } 406 407 408 /** 409 * Parse from Reader. White space is delimiter for word. 410 * @param r Reader. 411 * @return the next Element found on r. 412 */ 413 public Word parse(Reader r) { 414 return parse(StringUtil.nextString(r)); 415 } 416 417 418 /** 419 * Get the descending order comparator. Sorts the highest terms first. 420 * @return horder. 421 */ 422 public WordComparator getDescendComparator() { 423 return horder; 424 } 425 426 427 /** 428 * Get the ascending order comparator. Sorts the lowest terms first. 429 * @return lorder. 430 */ 431 public WordComparator getAscendComparator() { 432 return lorder; 433 } 434 435 436 /** 437 * Prepare parse from String. 438 * @param s String. 439 * @return a Element corresponding to s. 440 */ 441 public static String cleanSpace(String s) { 442 String st = s.trim(); 443 st = st.replaceAll("\\*", ""); 444 st = st.replaceAll("\\s", ""); 445 st = st.replaceAll("\\(", ""); 446 st = st.replaceAll("\\)", ""); 447 st = st.replaceAll("\\\"", ""); 448 return st; 449 } 450 451 452 /** 453 * Prepare parse from String. 454 * @param s String. 455 * @return a Element corresponding to s. 456 */ 457 public static String clean(String s) { 458 String st = s.trim(); 459 st = st.replaceAll("\\*", " "); 460 //st = st.replaceAll("\\s", ""); 461 st = st.replaceAll("\\(", ""); 462 st = st.replaceAll("\\)", ""); 463 st = st.replaceAll("\\\"", ""); 464 return st; 465 } 466 467 468 /** 469 * Prepare parse from String array. 470 * @param v String array. 471 * @return an array of cleaned strings. 472 */ 473 public static String[] cleanAll(String[] v) { 474 String[] t = new String[v.length]; 475 for ( int i = 0; i < v.length; i++ ) { 476 t[i] = cleanSpace(v[i]); 477 if ( t[i].length() == 0 ) { 478 logger.error("empty v[i]: '"+ v[i] + "'"); 479 } 480 //System.out.println("clean all: " + v[i] + " --> " + t[i]); 481 } 482 return t; 483 } 484 485 486 /** 487 * Concat variable names. 488 * @param v an array of strings. 489 * @return the concatination of the strings in v. 490 */ 491 public static String concat(String[] v) { 492 StringBuffer s = new StringBuffer(); 493 if ( v == null ) { 494 return s.toString(); 495 } 496 for ( int i = 0; i < v.length; i++ ) { 497 //String a = v[i]; 498 //if ( a.length() != 1 ) { 499 // //logger.error("v[i] not single letter "+ a); 500 // a = a.substring(0,1); 501 //} 502 s.append(v[i]); 503 } 504 return s.toString(); 505 } 506 507 508 /** 509 * Trim all variable names. 510 * @param v an array of strings. 511 * @return an array of strings with all elements trimmed. 512 */ 513 public static String[] trimAll(String[] v) { 514 String[] t = new String[v.length]; 515 for ( int i = 0; i < v.length; i++ ) { 516 t[i] = v[i].trim(); 517 if ( t[i].length() == 0 ) { 518 logger.error("empty v[i]: '"+ v[i] + "'"); 519 } 520 } 521 return t; 522 } 523 524 525 /** 526 * IndexOf for String array. 527 * @param v an array of strings. 528 * @param s string. 529 * @return index of s in v, or -1 if s is not contained in v. 530 */ 531 public static int indexOf(String[] v, String s) { 532 for ( int i = 0; i < v.length; i++ ) { 533 if ( s.equals(v[i]) ) { 534 return i; 535 } 536 } 537 return -1; 538 } 539 540 541 /** 542 * Test if all variables are single letters. 543 * @param v an array of strings. 544 * @return true, if all variables have length 1, else false. 545 */ 546 public static boolean isSingleLetters(String[] v) { 547 for ( int i = 0; i < v.length; i++ ) { 548 if ( v[i].length() != 1 ) { 549 return false; 550 } 551 } 552 return true; 553 } 554 555 556 /** 557 * Translate variable names. 558 * @param v an array of strings. 559 * @return the translated string of v with respect to t. 560 */ 561 public String translate(String[] v) { 562 StringBuffer s = new StringBuffer(); 563 for ( int i = 0; i < v.length; i++ ) { 564 String a = v[i]; 565 int k = indexOf(translation,a); 566 if ( k < 0 ) { 567 System.out.println("t = " + Arrays.toString(translation)); 568 System.out.println("v = " + Arrays.toString(v)); 569 logger.error("v[i] not found in t: "+ a); 570 //continue; 571 throw new IllegalArgumentException("v[i] not found in t: "+ a); 572 } 573 s.append(transRef.charAt(k)); 574 } 575 return s.toString(); 576 } 577 578 579 /** 580 * Translate variable name. 581 * @param c internal char. 582 * @return the extenal translated string. 583 */ 584 public String transVar(char c) { 585 int k = alphabet.indexOf(c); 586 return translation[k]; 587 } 588 589}