001/* 002 * $Id: Word.java 4198 2012-09-16 20:57:16Z kredel $ 003 */ 004 005package edu.jas.poly; 006 007 008import java.io.Serializable; 009import java.util.SortedMap; 010import java.util.TreeMap; 011import java.util.List; 012import java.util.ArrayList; 013import java.util.Arrays; 014 015import edu.jas.structure.MonoidElem; 016import edu.jas.structure.MonoidFactory; 017import edu.jas.structure.NotInvertibleException; 018 019 020/** 021 * Word implements strings of letters for polynomials. 022 * @author Heinz Kredel 023 */ 024 025public final class Word implements MonoidElem<Word> { 026 027 028 /** 029 * Defining alphabet in WordFactory. 030 */ 031 public final WordFactory mono; 032 033 034 /** 035 * The data structure is a String of characters. 036 */ 037 /*package*/final String val; 038 039 040 /** 041 * Stored hash code. 042 */ 043 protected int hash = 0; 044 045 046 /** 047 * Constructor for Word. 048 * @param m factory for words. 049 */ 050 public Word(WordFactory m) { 051 this(m, ""); 052 } 053 054 055 /** 056 * Constructor for Word. 057 * @param m factory for words. 058 * @param s String 059 */ 060 public Word(WordFactory m, String s) { 061 this(m,s,true); 062 } 063 064 065 /** 066 * Constructor for Word. 067 * @param m factory for words. 068 * @param s String 069 * @param translate indicator if s needs translation 070 */ 071 public Word(WordFactory m, String s, boolean translate) { 072 mono = m; 073 hash = 0; 074 if (s == null) { 075 throw new IllegalArgumentException("null string not allowed"); 076 } 077 if ( translate ) { 078 if ( mono.translation != null ) { 079 //System.out.println("s = " + s); 080 String[] S = GenPolynomialTokenizer.variableList(s); 081 //System.out.println("S = " + Arrays.toString(S)); 082 val = mono.translate(S); 083 //System.out.println("val = " + val); 084 } else { 085 val = WordFactory.cleanSpace(s); //?? 086 } 087 } else { 088 val = s; 089 } 090 } 091 092 093 /** 094 * Get the corresponding element factory. 095 * @return factory for this Element. 096 * @see edu.jas.structure.Element#factory() 097 */ 098 public MonoidFactory<Word> factory() { 099 return mono; 100 } 101 102 103 /** 104 * Copy this. 105 * @return copy of this. 106 */ 107 @Override 108 public Word copy() { 109 return new Word(mono, val, false); 110 } 111 112 113 /** 114 * Get the word String. 115 * @return val. 116 */ 117 /*package*/String getVal() { 118 return val; 119 } 120 121 122 /** 123 * Get the letter at position i. 124 * @param i position. 125 * @return val[i]. 126 */ 127 public char getVal(int i) { 128 return val.charAt(i); 129 } 130 131 132 /** 133 * Get the length of this word. 134 * @return val.length. 135 */ 136 public int length() { 137 return val.length(); 138 } 139 140 141 /** 142 * Get the string representation. 143 * @see java.lang.Object#toString() 144 */ 145 @Override 146 public String toString() { 147 if (val.length() == 0) { 148 return ""; 149 } 150 StringBuffer s = new StringBuffer("\""); 151 String vv; 152 if ( mono.translation == null ) { 153 for (int i = 0; i < length(); i++) { 154 if (i != 0) { 155 s.append(" "); 156 } 157 s.append(getVal(i)); 158 } 159 } else { 160 for (int i = 0; i < length(); i++) { 161 if (i != 0) { 162 s.append(" "); 163 } 164 s.append(mono.transVar(getVal(i))); 165 } 166 } 167 s.append("\""); 168 return s.toString(); 169 } 170 171 172 /** 173 * Get a scripting compatible string representation. 174 * @return script compatible representation for this Element. 175 * @see edu.jas.structure.Element#toScript() 176 */ 177 //JAVA6only: @Override 178 public String toScript() { 179 if (val.length() == 0) { 180 return ""; 181 } 182 StringBuffer s = new StringBuffer(""); 183 if ( mono.translation == null ) { 184 for (int i = 0; i < length(); i++) { 185 if (i != 0) { 186 s.append("*"); // checked for python vs ruby 187 } 188 s.append(getVal(i)); 189 } 190 } else { 191 for (int i = 0; i < length(); i++) { 192 if (i != 0) { 193 s.append("*"); // checked for python vs ruby 194 } 195 s.append(mono.transVar(getVal(i))); 196 } 197 } 198 s.append(""); 199 return s.toString(); 200 } 201 202 203 /** 204 * Get a scripting compatible string representation of the factory. 205 * @return script compatible representation for this ElemFactory. 206 * @see edu.jas.structure.Element#toScriptFactory() 207 */ 208 //JAVA6only: @Override 209 public String toScriptFactory() { 210 // Python case 211 return mono.toString(); 212 } 213 214 215 /** 216 * Comparison with any other object. 217 * @see java.lang.Object#equals(java.lang.Object) 218 */ 219 @Override 220 public boolean equals(Object B) { 221 if (!(B instanceof Word)) { 222 return false; 223 } 224 Word b = (Word) B; 225 // mono == b.mono ?? 226 int t = this.compareTo(b); 227 //System.out.println("equals: this = " + this + " B = " + B + " t = " + t); 228 return (0 == t); 229 } 230 231 232 /** 233 * hashCode. 234 * @see java.lang.Object#hashCode() 235 */ 236 @Override 237 public int hashCode() { 238 if (hash == 0) { 239 hash = val.hashCode(); 240 } 241 return hash; 242 } 243 244 245 /** 246 * Is Word one. 247 * @return If this is the empty word then true is returned, else false. 248 */ 249 public boolean isONE() { 250 return (0 == this.length()); 251 } 252 253 254 /** 255 * Is Word unit. 256 * @return If this is a unit then true is returned, else false. 257 */ 258 public boolean isUnit() { 259 return isONE(); 260 } 261 262 263 /** 264 * Word multiplication. 265 * @param V other word. 266 * @return this * V. 267 */ 268 public Word multiply(Word V) { 269 return new Word(mono, this.val + V.val, false); 270 } 271 272 273 /** 274 * Word divide. 275 * @param V other word. 276 * @return this / V. 277 */ 278 public Word divide(Word V) { 279 Word[] ret = divideWord(V); 280 // TODO: fail if both non zero? 281 if (!ret[0].isONE() && !ret[1].isONE()) { 282 throw new IllegalArgumentException("not simple dividable: left = " + ret[0] + ", right = " 283 + ret[1] + ", use divideWord"); 284 } 285 return ret[0].multiply(ret[1]); 286 } 287 288 289 /** 290 * Word divide with prefix and suffix. 291 * @param V other word. 292 * @return [prefix(this/V), suffix(this/V)] = [left,right] with left * V * right = this. 293 */ 294 public Word[] divideWord(Word V) { 295 int i = this.val.indexOf(V.val); 296 if (i < 0) { 297 throw new NotInvertibleException("not dividable: " + this + ", other " + V); 298 } 299 int len = V.val.length(); 300 String pre = this.val.substring(0, i); 301 String suf = this.val.substring(i + len); 302 Word[] ret = new Word[2]; 303 ret[0] = new Word(mono, pre, false); 304 ret[1] = new Word(mono, suf, false); 305 return ret; 306 } 307 308 309 /** 310 * Word remainder. 311 * @param V other word. 312 * @return this (this/V). <b>Note:</b> not useful. 313 */ 314 public Word remainder(Word V) { 315 int i = this.val.indexOf(V.val); 316 if (i < 0) { 317 throw new NotInvertibleException("not dividable: " + this + ", other " + V); 318 } 319 return V; 320 } 321 322 323 /** 324 * Word inverse. 325 * @return 1 / this. 326 */ 327 public Word inverse() { 328 if ( val.length() == 0 ) { 329 return this; 330 } 331 throw new NotInvertibleException("not inversible " + this); 332 } 333 334 335 /** 336 * Word signum. 337 * @return 0 if this is one, 1 if it is non empty. 338 */ 339 public int signum() { 340 int i = val.length(); 341 if (i > 0) { 342 i = 1; 343 } 344 assert i >= 0; 345 return i; 346 } 347 348 349 /** 350 * Word degree. 351 * @return total degree of all letters. 352 */ 353 public long degree() { 354 return val.length(); 355 } 356 357 358 /** 359 * Word dependency on letters. 360 * @return sorted map of letters and the number of its occurences. 361 */ 362 public SortedMap<String,Integer> dependencyOnVariables() { 363 SortedMap<String,Integer> map = new TreeMap<String,Integer>(); 364 for ( int i = 0; i < val.length(); i++ ) { 365 String s = String.valueOf( val.charAt(i) ); 366 Integer n = map.get(s); 367 if ( n == null ) { 368 n = 0; 369 } 370 n = n + 1; 371 map.put(s,n); 372 } 373 return map; 374 } 375 376 377 /** 378 * Word multiple test. 379 * @param V other word. 380 * @return true if this is a multiple of V, else false. 381 */ 382 public boolean multipleOf(Word V) { 383 return this.val.contains(V.val); 384 } 385 386 387 /** 388 * Word divides test. 389 * @param V other word. 390 * @return true if this divides V, else false. 391 */ 392 public boolean divides(Word V) { 393 return V.val.contains(this.val); 394 } 395 396 397 /** 398 * Word compareTo. Uses <pre>String.compareTo</pre>. 399 * @param V other word. 400 * @return 0 if U == V, -1 if U < V, 1 if U > V. 401 */ 402 //JAVA6only: @Override 403 public int compareTo(Word V) { 404 return this.val.compareTo(V.val); 405 } 406 407 408 /** 409 * Word graded comparison. Compares first be degree, then lexicographical. 410 * @param V other word. 411 * @return 0 if U == V, -1 if U < V, 1 if U > V. 412 */ 413 public int gradCompareTo(Word V) { 414 long e = this.degree(); 415 long f = V.degree(); 416 if (e < f) { 417 return 1; 418 } else if (e > f) { 419 return -1; 420 } 421 return this.compareTo(V); 422 } 423 424 425 /** 426 * Word graded comparison. Compares first be degree, then inverse lexicographical. 427 * @param V other word. 428 * @return 0 if U == V, -1 if U < V, 1 if U > V. 429 */ 430 public int gradInvlexCompareTo(Word V) { 431 long e = this.degree(); 432 long f = V.degree(); 433 if (e < f) { 434 return 1; 435 } else if (e > f) { 436 return -1; 437 } 438 return -this.compareTo(V); 439 } 440 441 442 /** 443 * Is word overlap. 444 * @param ol = [l1,r1,l2,r2] an Overlap container of four words 445 * @param V word 446 * @return true if l1 * this * r1 = l2 * V * r2, else false. 447 */ 448 public boolean isOverlap(Overlap ol, Word V) { 449 return ol.isOverlap(this,V); 450 } 451 452 453 /** 454 * Word overlap list. 455 * @param V other word. 456 * @return list of overlaps [l1,r1,l2,r2] with l1 * this * r1 = l2 * V * r2. 457 * If no such overlaps exist the empty overlap list is returned. 458 */ 459 public OverlapList overlap(Word V) { 460 OverlapList ret = new OverlapList(); 461 Word wone = mono.getONE(); 462 String a = this.val; 463 String b = V.val; 464 int ai = a.length(); 465 int bi = b.length(); 466 int j = b.indexOf(a); 467 if (j >= 0) { 468 while ( j >= 0 ) { 469 String pre = b.substring(0, j); 470 String suf = b.substring(j + ai); 471 Word wpre = new Word(mono, pre, false); 472 Word wsuf = new Word(mono, suf, false); 473 ret.add(new Overlap(wpre,wsuf,wone,wone)); 474 j = b.indexOf(a,j+ai); // +1 also inner overlaps ? 475 } 476 return ret; 477 } 478 j = a.indexOf(b); 479 if (j >= 0) { 480 while ( j >= 0 ) { 481 String pre = a.substring(0, j); 482 String suf = a.substring(j + bi); 483 Word wpre = new Word(mono, pre, false); 484 Word wsuf = new Word(mono, suf, false); 485 ret.add(new Overlap(wone,wone,wpre,wsuf)); 486 j = a.indexOf(b,j+bi); // +1 also inner overlaps ? 487 } 488 return ret; 489 } 490 if ( ai >= bi ) { 491 for ( int i = 0; i < bi; i++ ) { 492 String as = a.substring(0,i+1); 493 String bs = b.substring(bi-i-1,bi); 494 //System.out.println("i = " + i + ", bs = " + bs + ", as = " + as); 495 if ( as.equals(bs) ) { 496 Word w1 = new Word(mono, b.substring(0,bi-i-1), false); 497 Word w2 = new Word(mono, a.substring(i+1), false); 498 ret.add(new Overlap(w1, wone, wone, w2)); 499 break; 500 } 501 } 502 for ( int i = 0; i < bi; i++ ) { 503 String as = a.substring(ai-i-1,ai); 504 String bs = b.substring(0,i+1); 505 //System.out.println("i = " + i + ", bs = " + bs + ", as = " + as); 506 if ( as.equals(bs) ) { 507 Word w1 = new Word(mono, b.substring(i+1), false); 508 Word w2 = new Word(mono, a.substring(0,ai-i-1), false); 509 ret.add(new Overlap(wone, w1, w2, wone)); 510 break; 511 } 512 } 513 } else { // ai < bi 514 for ( int i = 0; i < ai; i++ ) { 515 String as = a.substring(ai-i-1,ai); 516 String bs = b.substring(0,i+1); 517 //System.out.println("i = " + i + ", bs = " + bs + ", as = " + as); 518 if ( as.equals(bs) ) { 519 Word w1 = new Word(mono, b.substring(i+1), false); 520 Word w2 = new Word(mono, a.substring(0,ai-i-1), false); 521 ret.add(new Overlap(wone, w1, w2, wone)); 522 break; 523 } 524 } 525 for ( int i = 0; i < ai; i++ ) { 526 String as = a.substring(0,i+1); 527 String bs = b.substring(bi-i-1,bi); 528 //System.out.println("i = " + i + ", bs = " + bs + ", as = " + as); 529 if ( as.equals(bs) ) { 530 Word w1 = new Word(mono, b.substring(0,bi-i-1), false); 531 Word w2 = new Word(mono, a.substring(i+1), false); 532 ret.add(new Overlap(w1, wone, wone, w2)); 533 break; 534 } 535 } 536 } 537 return ret; 538 } 539 540 541 /** 542 * Word pseudo least common multiple. 543 * @param V other word. 544 * @return w = l1*this*r1, with l1*this*r1 == l2*V*r2, if l1, r1, l2, r2 exist, 545 * else null is returned. 546 */ 547 public Word lcm(Word V) { 548 OverlapList oll = overlap(V); 549 if ( oll.ols.isEmpty() ) { 550 return null; 551 } 552 Overlap ol = oll.ols.get(0); 553 Word g = ol.l1.multiply(this).multiply(ol.r1); 554 return g; 555 } 556 557}