1 /* 2 ******************************************************************************* 3 * Copyright (C) 2002-2012, International Business Machines Corporation and * 4 * others. All Rights Reserved. * 5 ******************************************************************************* 6 */ 7 package com.ibm.icu.dev.util; 8 9 import java.util.ArrayList; 10 import java.util.Arrays; 11 import java.util.HashSet; 12 import java.util.Random; 13 import java.util.Set; 14 15 import com.ibm.icu.text.UTF16; 16 import com.ibm.icu.text.UnicodeSet; 17 18 abstract public class Pick { 19 private static boolean DEBUG = false; 20 21 // for using to get strings 22 23 static class Target { 24 private Pick pick; 25 private Random random; 26 private Quoter quoter; 27 28 public static Target make(Pick pick, Random random, Quoter quoter) { 29 Target result = new Target(); 30 result.pick = pick; 31 result.random = random; 32 result.quoter = quoter; 33 return result; 34 } 35 public String next() { 36 quoter.clear(); 37 pick.addTo(this); 38 return get(); 39 } 40 public String get() { 41 return quoter.toString(); 42 } 43 private void copyState(Target other) { 44 random = other.random; 45 } 46 private void clear() { 47 quoter.clear(); 48 } 49 /*private int length() { 50 return quoter.length(); 51 }*/ 52 private Target append(int codepoint) { 53 quoter.append(codepoint); 54 return this; 55 } 56 private Target append(String s) { 57 quoter.append(s); 58 return this; 59 } 60 // must return value between 0 (inc) and 1 (exc) 61 private double nextDouble() { 62 return random.nextDouble(); 63 } 64 } 65 66 // for Building 67 68 public Pick replace(String toReplace, Pick replacement) { 69 Replacer visitor = new Replacer(toReplace, replacement); 70 return visit(visitor); 71 } 72 73 public Pick name(String nameStr) { 74 name = nameStr; 75 return this; 76 } 77 78 static public Pick.Sequence makeSequence() { 79 return new Sequence(); 80 } 81 static public Pick.Alternation makeAlternation() { 82 return new Alternation(); 83 } 84 /* 85 static public Pick.Sequence and(Object item) { 86 return new Sequence().and2(item); 87 } 88 static public Pick.Sequence and(Object[] items) { 89 return new Sequence().and2(items); 90 } 91 static public Pick.Alternation or(int itemWeight, Object item) { 92 return new Alternation().or2(itemWeight, item); 93 } 94 static public Pick.Alternation or(Object[] items) { 95 return new Alternation().or2(1, items); 96 } 97 static public Pick.Alternation or(int itemWeight, Object[] items) { 98 return new Alternation().or2(itemWeight, items); 99 } 100 static public Pick.Alternation or(int[] itemWeights, Object[] items) { 101 return new Alternation().or2(itemWeights, items); 102 } 103 104 static public Pick maybe(int percent, Object item) { 105 return new Repeat(0, 1, new int[]{100-percent, percent}, item); 106 //return Pick.or(1.0-percent, NOTHING).or2(percent, item); 107 } 108 static public Pick repeat(int minCount, int maxCount, int itemWeights, Object item) { 109 return new Repeat(minCount, maxCount, itemWeights, item); 110 } 111 112 static public Pick codePoint(String source) { 113 return new CodePoint(new UnicodeSet(source)); 114 } 115 */ 116 117 static public Pick repeat(int minCount, int maxCount, int[] itemWeights, Pick item) { 118 return new Repeat(minCount, maxCount, itemWeights, item); 119 } 120 121 static public Pick codePoint(UnicodeSet source) { 122 return new CodePoint(source); 123 } 124 static public Pick string(String source) { 125 return new Literal(source); 126 } 127 /* 128 static public Pick unquoted(String source) { 129 return new Literal(source); 130 } 131 static public Pick string(int minLength, int maxLength, Pick item) { 132 return new Morph(item, minLength, maxLength); 133 } 134 */ 135 136 public abstract String getInternal(int depth, Set alreadySeen); 137 // Internals 138 139 protected String name; 140 141 protected abstract void addTo(Target target); 142 public abstract boolean match(String input, Position p); 143 144 public static class Sequence extends ListPick { 145 public Sequence and2 (Pick item) { 146 addInternal(new Pick[] {item}); // we don't care about perf 147 return this; // for chaining 148 } 149 public Sequence and2 (Pick[] itemArray) { 150 addInternal(itemArray); 151 return this; // for chaining 152 } 153 protected void addTo(Target target) { 154 for (int i = 0; i < items.length; ++i) { 155 items[i].addTo(target); 156 } 157 } 158 public String getInternal(int depth, Set alreadySeen) { 159 String result = checkName(name, alreadySeen); 160 if (result.startsWith("$")) return result; 161 result = indent(depth) + result + "SEQ("; 162 for (int i = 0; i < items.length; ++i) { 163 if (i != 0) result += ", "; 164 result += items[i].getInternal(depth+1, alreadySeen); 165 } 166 result += ")"; 167 return result; 168 } 169 // keep private 170 private Sequence() {} 171 public boolean match(String input, Position p) { 172 int originalIndex = p.index; 173 for (int i = 0; i < items.length; ++i) { 174 if (!items[i].match(input, p)) { 175 p.index = originalIndex; 176 return false; 177 } 178 } 179 return true; 180 } 181 } 182 183 String checkName(String nameStr, Set alreadySeen) { 184 if (nameStr == null) return ""; 185 if (alreadySeen.contains(nameStr)) return nameStr; 186 alreadySeen.add(nameStr); 187 return "{" + nameStr + "=}"; 188 } 189 190 public static class Alternation extends ListPick { 191 private WeightedIndex weightedIndex = new WeightedIndex(0); 192 193 public Alternation or2 (Pick[] newItems) { 194 return or2(1, newItems); 195 } 196 public Alternation or2 (int itemWeight, Pick item) { 197 return or2(itemWeight, new Pick[] {item}); // we don't care about perf 198 } 199 public Alternation or2 (int itemWeight, Pick[] newItems) { 200 int[] itemWeights = new int[newItems.length]; 201 Arrays.fill(itemWeights,itemWeight); 202 return or2(itemWeights, newItems); // we don't care about perf 203 } 204 public Alternation or2 (int[] itemWeights, Pick[] newItems) { 205 if (newItems.length != itemWeights.length) { 206 throw new ArrayIndexOutOfBoundsException( 207 "or lengths must be equal: " + newItems.length + " != " + itemWeights.length); 208 } 209 // int lastLen = this.items.length; 210 addInternal(newItems); 211 weightedIndex.add(itemWeights); 212 return this; // for chaining 213 } 214 protected void addTo(Target target) { 215 items[weightedIndex.toIndex(target.nextDouble())].addTo(target); 216 } 217 218 public String getInternal(int depth, Set alreadySeen) { 219 String result = checkName(name, alreadySeen); 220 if (result.startsWith("$")) return result; 221 result = indent(depth) + result + "OR("; 222 for (int i = 0; i < items.length; ++i) { 223 if (i != 0) result += ", "; 224 result += items[i].getInternal(depth+1, alreadySeen) + "/" + weightedIndex.weights[i]; 225 } 226 return result + ")"; 227 } 228 // keep private 229 private Alternation() {} 230 // take first matching option 231 public boolean match(String input, Position p) { 232 for (int i = 0; i < weightedIndex.weights.length; ++i) { 233 if (p.isFailure(this,i)) continue; 234 if (items[i].match(input, p)) return true; 235 p.setFailure(this, i); 236 } 237 return false; 238 } 239 } 240 241 private static String indent(int depth) { 242 String result = "\r\n"; 243 for (int i = 0; i < depth; ++i) { 244 result += " "; 245 } 246 return result; 247 } 248 249 private static class Repeat extends ItemPick { 250 WeightedIndex weightedIndex; 251 int minCount = 0; 252 253 private Repeat(int minCount, int maxCount, int[] itemWeights, Pick item) { 254 super(item); 255 weightedIndex = new WeightedIndex(minCount).add(maxCount-minCount+1, itemWeights); 256 } 257 /*private Repeat(int minCount, int maxCount, int itemWeight, Pick item) { 258 super(item); 259 weightedIndex = new WeightedIndex(minCount).add(maxCount-minCount+1, itemWeight); 260 }*/ 261 /* 262 private Repeat(int minCount, int maxCount, Object item) { 263 this.item = convert(item); 264 weightedIndex = new WeightedIndex(minCount).add(maxCount-minCount+1, 1); 265 } 266 */ 267 protected void addTo(Target target) { 268 //int count ; 269 for (int i = weightedIndex.toIndex(target.nextDouble()); i > 0; --i) { 270 item.addTo(target); 271 } 272 } 273 public String getInternal(int depth, Set alreadySeen) { 274 String result = checkName(name, alreadySeen); 275 if (result.startsWith("$")) return result; 276 result = indent(depth) + result + "REPEAT(" + weightedIndex 277 + "; "+ item.getInternal(depth+1, alreadySeen) 278 + ")"; 279 return result; 280 } 281 282 // match longest, e.g. up to just before a failure 283 public boolean match(String input, Position p) { 284 //int bestMatch = p.index; 285 int count = 0; 286 for (int i = 0; i < weightedIndex.weights.length; ++i) { 287 if (p.isFailure(this,i)) break; 288 if (!item.match(input, p)) { 289 p.setFailure(this,i); 290 break; 291 } 292 //bestMatch = p.index; 293 count++; 294 } 295 if (count >= minCount) { 296 return true; 297 } 298 // TODO fix failure 299 return false; 300 } 301 } 302 303 private static class CodePoint extends FinalPick { 304 private UnicodeSet source; 305 306 private CodePoint(UnicodeSet source) { 307 this.source = source; 308 } 309 protected void addTo(Target target) { 310 target.append(source.charAt(pick(target.random,0,source.size()-1))); 311 } 312 public boolean match(String s, Position p) { 313 int cp = UTF16.charAt(s, p.index); 314 if (source.contains(cp)) { 315 p.index += UTF16.getCharCount(cp); 316 return true; 317 } 318 p.setMax("codePoint"); 319 return false; 320 } 321 public String getInternal(int depth, Set alreadySeen) { 322 String result = checkName(name, alreadySeen); 323 if (result.startsWith("$")) return result; 324 return source.toString(); 325 } 326 } 327 328 static class Morph extends ItemPick { 329 Morph(Pick item) { 330 super(item); 331 } 332 333 private String lastValue = null; 334 private Target addBuffer = Target.make(this, null, new Quoter.RuleQuoter()); 335 private StringBuffer mergeBuffer = new StringBuffer(); 336 337 private static final int COPY_NEW = 0, COPY_BOTH = 1, COPY_LAST = 3, SKIP = 4, 338 LEAST_SKIP = 4; 339 // give weights to the above. make sure we delete about the same as we insert 340 private static final WeightedIndex choice = new WeightedIndex(0) 341 .add(new int[] {10, 10, 100, 10}); 342 343 protected void addTo(Target target) { 344 // get contents into separate buffer 345 addBuffer.copyState(target); 346 addBuffer.clear(); 347 item.addTo(addBuffer); 348 String newValue = addBuffer.get(); 349 if (DEBUG) System.out.println("Old: " + lastValue + ", New:" + newValue); 350 351 // if not first one, merge with old 352 if (lastValue != null) { 353 mergeBuffer.setLength(0); 354 int lastIndex = 0; 355 int newIndex = 0; 356 // the new length is a random value between old and new. 357 int newLenLimit = (int) pick(target.random, lastValue.length(), newValue.length()); 358 359 while (mergeBuffer.length() < newLenLimit 360 && newIndex < newValue.length() 361 && lastIndex < lastValue.length()) { 362 int c = choice.toIndex(target.nextDouble()); 363 if (c == COPY_NEW || c == COPY_BOTH || c == SKIP) { 364 newIndex = getChar(newValue, newIndex, mergeBuffer, c < LEAST_SKIP); 365 if (mergeBuffer.length() >= newLenLimit) break; 366 } 367 if (c == COPY_LAST || c == COPY_BOTH || c == SKIP) { 368 lastIndex = getChar(lastValue, lastIndex, mergeBuffer, c < LEAST_SKIP); 369 } 370 } 371 newValue = mergeBuffer.toString(); 372 } 373 lastValue = newValue; 374 target.append(newValue); 375 if (DEBUG) System.out.println("Result: " + newValue); 376 } 377 378 public String getInternal(int depth, Set alreadySeen) { 379 String result = checkName(name, alreadySeen); 380 if (result.startsWith("$")) return result; 381 return indent(depth) + result + "MORPH(" 382 + item.getInternal(depth+1, alreadySeen) 383 + ")"; 384 } 385 386 /* (non-Javadoc) 387 * @see Pick#match(java.lang.String, Pick.Position) 388 */ 389 public boolean match(String input, Position p) { 390 // TODO Auto-generated method stub 391 return false; 392 } 393 } 394 395 /* Add character if we can 396 */ 397 static int getChar(String newValue, int newIndex, StringBuffer mergeBuffer, boolean copy) { 398 if (newIndex >= newValue.length()) return newIndex; 399 int cp = UTF16.charAt(newValue,newIndex); 400 if (copy) UTF16.append(mergeBuffer, cp); 401 return newIndex + UTF16.getCharCount(cp); 402 } 403 404 /* 405 // quoted add 406 appendQuoted(target, addBuffer.toString(), quoteBuffer); 407 // fix buffers 408 StringBuffer swapTemp = addBuffer; 409 addBuffer = source; 410 source = swapTemp; 411 } 412 } 413 */ 414 415 416 static class Quote extends ItemPick { 417 Quote(Pick item) { 418 super(item); 419 } 420 protected void addTo(Target target) { 421 target.quoter.setQuoting(true); 422 item.addTo(target); 423 target.quoter.setQuoting(false); 424 } 425 426 public boolean match(String s, Position p) { 427 return false; 428 } 429 430 public String getInternal(int depth, Set alreadySeen) { 431 String result = checkName(name, alreadySeen); 432 if (result.startsWith("$")) return result; 433 return indent(depth) + result + "QUOTE(" + item.getInternal(depth+1, alreadySeen) 434 + ")"; 435 } 436 } 437 438 private static class Literal extends FinalPick { 439 public String toString() { 440 return name; 441 } 442 private Literal(String source) { 443 this.name = source; 444 } 445 protected void addTo(Target target) { 446 target.append(name); 447 } 448 public boolean match(String input, Position p) { 449 int len = name.length(); 450 if (input.regionMatches(p.index, name, 0, len)) { 451 p.index += len; 452 return true; 453 } 454 p.setMax("literal"); 455 return false; 456 } 457 public String getInternal(int depth, Set alreadySeen) { 458 return "'" + name + "'"; 459 } 460 } 461 462 public static class Position { 463 public ArrayList failures = new ArrayList(); 464 public int index; 465 public int maxInt; 466 public String maxType; 467 public void setMax(String type) { 468 if (index >= maxInt) { 469 maxType = type; 470 } 471 } 472 public String toString() { 473 return "index; " + index 474 + ", maxInt:" + maxInt 475 + ", maxType: " + maxType; 476 } 477 /*private static final Object BAD = new Object(); 478 private static final Object GOOD = new Object();*/ 479 480 public boolean isFailure(Pick pick, int item) { 481 ArrayList val = (ArrayList)failures.get(index); 482 if (val == null) return false; 483 Set set = (Set)val.get(item); 484 if (set == null) return false; 485 return !set.contains(pick); 486 } 487 public void setFailure(Pick pick, int item) { 488 ArrayList val = (ArrayList)failures.get(index); 489 if (val == null) { 490 val = new ArrayList(); 491 failures.set(index, val); 492 } 493 Set set = (Set)val.get(item); 494 if (set == null) { 495 set = new HashSet(); 496 val.set(item, set); 497 } 498 set.add(pick); 499 } 500 } 501 502 /* 503 public static final Pick NOTHING = new Nothing(); 504 505 506 private static class Nothing extends FinalPick { 507 protected void addTo(Target target) {} 508 protected boolean match(String input, Position p) { 509 return true; 510 } 511 public String getInternal(int depth, Set alreadySeen) { 512 return indent(depth) + "\u00F8"; 513 } 514 } 515 */ 516 517 // intermediates 518 519 abstract static class Visitor { 520 Set already = new HashSet(); 521 // Note: each visitor should return the Pick that will replace a (or a itself) 522 abstract Pick handle(Pick a); 523 boolean alreadyEntered(Pick item) { 524 boolean result = already.contains(item); 525 already.add(item); 526 return result; 527 } 528 void reset() { 529 already.clear(); 530 } 531 } 532 533 protected abstract Pick visit(Visitor visitor); 534 535 static class Replacer extends Visitor { 536 String toReplace; 537 Pick replacement; 538 Replacer(String toReplace, Pick replacement) { 539 this.toReplace = toReplace; 540 this.replacement = replacement; 541 } 542 public Pick handle(Pick a) { 543 if (toReplace.equals(a.name)) { 544 a = replacement; 545 } 546 return a; 547 } 548 } 549 550 abstract private static class FinalPick extends Pick { 551 public Pick visit(Visitor visitor) { 552 return visitor.handle(this); 553 } 554 } 555 556 private abstract static class ItemPick extends Pick { 557 protected Pick item; 558 559 ItemPick (Pick item) { 560 this.item = item; 561 } 562 563 public Pick visit(Visitor visitor) { 564 Pick result = visitor.handle(this); 565 if (visitor.alreadyEntered(this)) return result; 566 if (item != null) item = item.visit(visitor); 567 return result; 568 } 569 } 570 571 private abstract static class ListPick extends Pick { 572 protected Pick[] items = new Pick[0]; 573 574 Pick simplify() { 575 if (items.length > 1) return this; 576 if (items.length == 1) return items[0]; 577 return null; 578 } 579 580 int size() { 581 return items.length; 582 } 583 584 Pick getLast() { 585 return items[items.length-1]; 586 } 587 588 void setLast(Pick newOne) { 589 items[items.length-1] = newOne; 590 } 591 592 protected void addInternal(Pick[] objs) { 593 int lastLen = items.length; 594 items = realloc(items, items.length + objs.length); 595 for (int i = 0; i < objs.length; ++i) { 596 items[lastLen + i] = objs[i]; 597 } 598 } 599 600 public Pick visit(Visitor visitor) { 601 Pick result = visitor.handle(this); 602 if (visitor.alreadyEntered(this)) return result; 603 for (int i = 0; i < items.length; ++i) { 604 items[i] = items[i].visit(visitor); 605 } 606 return result; 607 } 608 } 609 610 /** 611 * Simple class to distribute a number between 0 (inclusive) and 1 (exclusive) among 612 * a number of indices, where each index is weighted. 613 * Item weights may be zero, but cannot be negative. 614 * @author Davis 615 */ 616 // As in other case, we use an array for runtime speed; don't care about buildspeed. 617 public static class WeightedIndex { 618 private int[] weights = new int[0]; 619 private int minCount = 0; 620 private double total; 621 622 public WeightedIndex(int minCount) { 623 this.minCount = minCount; 624 } 625 626 public WeightedIndex add(int count, int itemWeights) { 627 if (count > 0) { 628 int[] newWeights = new int[count]; 629 if (itemWeights < 1) itemWeights = 1; 630 Arrays.fill(newWeights, 0, count, itemWeights); 631 add(1, newWeights); 632 } 633 return this; // for chaining 634 } 635 636 public WeightedIndex add(int[] newWeights) { 637 return add(newWeights.length, newWeights); 638 } 639 640 public WeightedIndex add(int maxCount, int[] newWeights) { 641 if (newWeights == null) newWeights = new int[]{1}; 642 int oldLen = weights.length; 643 if (maxCount < newWeights.length) maxCount = newWeights.length; 644 weights = (int[]) realloc(weights, weights.length + maxCount); 645 System.arraycopy(newWeights, 0, weights, oldLen, newWeights.length); 646 int lastWeight = weights[oldLen + newWeights.length-1]; 647 for (int i = oldLen + newWeights.length; i < maxCount; ++i) { 648 weights[i] = lastWeight; 649 } 650 total = 0; 651 for (int i = 0; i < weights.length; ++i) { 652 if (weights[i] < 0) { 653 throw new RuntimeException("only positive weights: " + i); 654 } 655 total += weights[i]; 656 } 657 return this; // for chaining 658 } 659 660 // TODO, make this more efficient 661 public int toIndex(double zeroToOne) { 662 double weight = zeroToOne*total; 663 int i; 664 for (i = 0; i < weights.length; ++i) { 665 weight -= weights[i]; 666 if (weight <= 0) break; 667 } 668 return i + minCount; 669 } 670 public String toString() { 671 String result = ""; 672 for (int i = 0; i < minCount; ++i) { 673 if (result.length() != 0) result += ","; 674 result += "0"; 675 } 676 for (int i = 0; i < weights.length; ++i) { 677 if (result.length() != 0) result += ","; 678 result += weights[i]; 679 } 680 return result; 681 } 682 } 683 /* 684 private static Pick convert(Object obj) { 685 if (obj instanceof Pick) return (Pick)obj; 686 return new Literal(obj.toString(), false); 687 } 688 */ 689 // Useful statics 690 691 static public int pick(Random random, int start, int end) { 692 return start + (int)(random.nextDouble() * (end + 1 - start)); 693 } 694 695 static public double pick(Random random, double start, double end) { 696 return start + (random.nextDouble() * (end + 1 - start)); 697 } 698 699 static public boolean pick(Random random, double percent) { 700 return random.nextDouble() <= percent; 701 } 702 703 static public int pick(Random random, UnicodeSet s) { 704 return s.charAt(pick(random, 0,s.size()-1)); 705 } 706 707 static public String pick(Random random, String[] source) { 708 return source[pick(random, 0, source.length-1)]; 709 } 710 711 // these utilities really ought to be in Java 712 713 public static double[] realloc(double[] source, int newSize) { 714 double[] temp = new double[newSize]; 715 if (newSize > source.length) newSize = source.length; 716 if (newSize != 0) System.arraycopy(source,0,temp,0,newSize); 717 return temp; 718 } 719 720 public static int[] realloc(int[] source, int newSize) { 721 int[] temp = new int[newSize]; 722 if (newSize > source.length) newSize = source.length; 723 if (newSize != 0) System.arraycopy(source,0,temp,0,newSize); 724 return temp; 725 } 726 727 public static Pick[] realloc(Pick[] source, int newSize) { 728 Pick[] temp = new Pick[newSize]; 729 if (newSize > source.length) newSize = source.length; 730 if (newSize != 0) System.arraycopy(source,0,temp,0,newSize); 731 return temp; 732 } 733 734 // test utilities 735 /*private static void append(StringBuffer target, String toAdd, StringBuffer quoteBuffer) { 736 Utility.appendToRule(target, (int)-1, true, false, quoteBuffer); // close previous quote 737 if (DEBUG) System.out.println("\"" + toAdd + "\""); 738 target.append(toAdd); 739 } 740 741 private static void appendQuoted(StringBuffer target, String toAdd, StringBuffer quoteBuffer) { 742 if (DEBUG) System.out.println("\"" + toAdd + "\""); 743 Utility.appendToRule(target, toAdd, false, false, quoteBuffer); 744 }*/ 745 746 /* 747 public static abstract class MatchHandler { 748 public abstract void handleString(String source, int start, int limit); 749 public abstract void handleSequence(String source, int start, int limit); 750 public abstract void handleAlternation(String source, int start, int limit); 751 752 } 753 */ 754 /* 755 // redistributes random value 756 // values are still between 0 and 1, but with a different distribution 757 public interface Spread { 758 public double spread(double value); 759 } 760 761 // give the weight for the high end. 762 // values are linearly scaled according to the weight. 763 static public class SimpleSpread implements Spread { 764 static final Spread FLAT = new SimpleSpread(1.0); 765 boolean flat = false; 766 double aa, bb, cc; 767 public SimpleSpread(double maxWeight) { 768 if (maxWeight > 0.999 && maxWeight < 1.001) { 769 flat = true; 770 } else { 771 double q = (maxWeight - 1.0); 772 aa = -1/q; 773 bb = 1/(q*q); 774 cc = (2.0+q)/q; 775 } 776 } 777 public double spread(double value) { 778 if (flat) return value; 779 value = aa + Math.sqrt(bb + cc*value); 780 if (value < 0.0) return 0.0; // catch math gorp 781 if (value >= 1.0) return 1.0; 782 return value; 783 } 784 } 785 static public int pick(Spread spread, Random random, int start, int end) { 786 return start + (int)(spread.spread(random.nextDouble()) * (end + 1 - start)); 787 } 788 789 */ 790 791 792 }
