2 *******************************************************************************
\r
3 * Copyright (C) 2002-2010, International Business Machines Corporation and *
\r
4 * others. All Rights Reserved. *
\r
5 *******************************************************************************
\r
7 package com.ibm.icu.dev.test.util;
\r
9 import java.util.ArrayList;
\r
10 import java.util.Arrays;
\r
11 import java.util.HashSet;
\r
12 import java.util.Random;
\r
13 import java.util.Set;
\r
15 import com.ibm.icu.text.UTF16;
\r
16 import com.ibm.icu.text.UnicodeSet;
\r
18 abstract public class Pick {
\r
19 private static boolean DEBUG = false;
\r
21 // for using to get strings
\r
23 static class Target {
\r
25 private Random random;
\r
26 private Quoter quoter;
\r
28 public static Target make(Pick pick, Random random, Quoter quoter) {
\r
29 Target result = new Target();
\r
31 result.random = random;
\r
32 result.quoter = quoter;
\r
35 public String next() {
\r
40 public String get() {
\r
41 return quoter.toString();
\r
43 private void copyState(Target other) {
\r
44 random = other.random;
\r
46 private void clear() {
\r
49 /*private int length() {
\r
50 return quoter.length();
\r
52 private Target append(int codepoint) {
\r
53 quoter.append(codepoint);
\r
56 private Target append(String s) {
\r
60 // must return value between 0 (inc) and 1 (exc)
\r
61 private double nextDouble() {
\r
62 return random.nextDouble();
\r
68 public Pick replace(String toReplace, Pick replacement) {
\r
69 Replacer visitor = new Replacer(toReplace, replacement);
\r
70 return visit(visitor);
\r
73 public Pick name(String nameStr) {
\r
78 static public Pick.Sequence makeSequence() {
\r
79 return new Sequence();
\r
81 static public Pick.Alternation makeAlternation() {
\r
82 return new Alternation();
\r
85 static public Pick.Sequence and(Object item) {
\r
86 return new Sequence().and2(item);
\r
88 static public Pick.Sequence and(Object[] items) {
\r
89 return new Sequence().and2(items);
\r
91 static public Pick.Alternation or(int itemWeight, Object item) {
\r
92 return new Alternation().or2(itemWeight, item);
\r
94 static public Pick.Alternation or(Object[] items) {
\r
95 return new Alternation().or2(1, items);
\r
97 static public Pick.Alternation or(int itemWeight, Object[] items) {
\r
98 return new Alternation().or2(itemWeight, items);
\r
100 static public Pick.Alternation or(int[] itemWeights, Object[] items) {
\r
101 return new Alternation().or2(itemWeights, items);
\r
104 static public Pick maybe(int percent, Object item) {
\r
105 return new Repeat(0, 1, new int[]{100-percent, percent}, item);
\r
106 //return Pick.or(1.0-percent, NOTHING).or2(percent, item);
\r
108 static public Pick repeat(int minCount, int maxCount, int itemWeights, Object item) {
\r
109 return new Repeat(minCount, maxCount, itemWeights, item);
\r
112 static public Pick codePoint(String source) {
\r
113 return new CodePoint(new UnicodeSet(source));
\r
117 static public Pick repeat(int minCount, int maxCount, int[] itemWeights, Pick item) {
\r
118 return new Repeat(minCount, maxCount, itemWeights, item);
\r
121 static public Pick codePoint(UnicodeSet source) {
\r
122 return new CodePoint(source);
\r
124 static public Pick string(String source) {
\r
125 return new Literal(source);
\r
128 static public Pick unquoted(String source) {
\r
129 return new Literal(source);
\r
131 static public Pick string(int minLength, int maxLength, Pick item) {
\r
132 return new Morph(item, minLength, maxLength);
\r
136 public abstract String getInternal(int depth, Set alreadySeen);
\r
139 protected String name;
\r
141 protected abstract void addTo(Target target);
\r
142 protected abstract boolean match(String input, Position p);
\r
144 public static class Sequence extends ListPick {
\r
145 public Sequence and2 (Pick item) {
\r
146 addInternal(new Pick[] {item}); // we don't care about perf
\r
147 return this; // for chaining
\r
149 public Sequence and2 (Pick[] itemArray) {
\r
150 addInternal(itemArray);
\r
151 return this; // for chaining
\r
153 protected void addTo(Target target) {
\r
154 for (int i = 0; i < items.length; ++i) {
\r
155 items[i].addTo(target);
\r
158 public String getInternal(int depth, Set alreadySeen) {
\r
159 String result = checkName(name, alreadySeen);
\r
160 if (result.startsWith("$")) return result;
\r
161 result = indent(depth) + result + "SEQ(";
\r
162 for (int i = 0; i < items.length; ++i) {
\r
163 if (i != 0) result += ", ";
\r
164 result += items[i].getInternal(depth+1, alreadySeen);
\r
170 private Sequence() {}
\r
171 protected boolean match(String input, Position p) {
\r
172 int originalIndex = p.index;
\r
173 for (int i = 0; i < items.length; ++i) {
\r
174 if (!items[i].match(input, p)) {
\r
175 p.index = originalIndex;
\r
183 String checkName(String nameStr, Set alreadySeen) {
\r
184 if (nameStr == null) return "";
\r
185 if (alreadySeen.contains(nameStr)) return nameStr;
\r
186 alreadySeen.add(nameStr);
\r
187 return "{" + nameStr + "=}";
\r
190 public static class Alternation extends ListPick {
\r
191 private WeightedIndex weightedIndex = new WeightedIndex(0);
\r
193 public Alternation or2 (Pick[] newItems) {
\r
194 return or2(1, newItems);
\r
196 public Alternation or2 (int itemWeight, Pick item) {
\r
197 return or2(itemWeight, new Pick[] {item}); // we don't care about perf
\r
199 public Alternation or2 (int itemWeight, Pick[] newItems) {
\r
200 int[] itemWeights = new int[newItems.length];
\r
201 Arrays.fill(itemWeights,itemWeight);
\r
202 return or2(itemWeights, newItems); // we don't care about perf
\r
204 public Alternation or2 (int[] itemWeights, Pick[] newItems) {
\r
205 if (newItems.length != itemWeights.length) {
\r
206 throw new ArrayIndexOutOfBoundsException(
\r
207 "or lengths must be equal: " + newItems.length + " != " + itemWeights.length);
\r
209 // int lastLen = this.items.length;
\r
210 addInternal(newItems);
\r
211 weightedIndex.add(itemWeights);
\r
212 return this; // for chaining
\r
214 protected void addTo(Target target) {
\r
215 items[weightedIndex.toIndex(target.nextDouble())].addTo(target);
\r
218 public String getInternal(int depth, Set alreadySeen) {
\r
219 String result = checkName(name, alreadySeen);
\r
220 if (result.startsWith("$")) return result;
\r
221 result = indent(depth) + result + "OR(";
\r
222 for (int i = 0; i < items.length; ++i) {
\r
223 if (i != 0) result += ", ";
\r
224 result += items[i].getInternal(depth+1, alreadySeen) + "/" + weightedIndex.weights[i];
\r
226 return result + ")";
\r
229 private Alternation() {}
\r
230 // take first matching option
\r
231 protected boolean match(String input, Position p) {
\r
232 for (int i = 0; i < weightedIndex.weights.length; ++i) {
\r
233 if (p.isFailure(this,i)) continue;
\r
234 if (items[i].match(input, p)) return true;
\r
235 p.setFailure(this, i);
\r
241 private static String indent(int depth) {
\r
242 String result = "\r\n";
\r
243 for (int i = 0; i < depth; ++i) {
\r
249 private static class Repeat extends ItemPick {
\r
250 WeightedIndex weightedIndex;
\r
253 private Repeat(int minCount, int maxCount, int[] itemWeights, Pick item) {
\r
255 weightedIndex = new WeightedIndex(minCount).add(maxCount-minCount+1, itemWeights);
\r
257 /*private Repeat(int minCount, int maxCount, int itemWeight, Pick item) {
\r
259 weightedIndex = new WeightedIndex(minCount).add(maxCount-minCount+1, itemWeight);
\r
262 private Repeat(int minCount, int maxCount, Object item) {
\r
263 this.item = convert(item);
\r
264 weightedIndex = new WeightedIndex(minCount).add(maxCount-minCount+1, 1);
\r
267 protected void addTo(Target target) {
\r
269 for (int i = weightedIndex.toIndex(target.nextDouble()); i > 0; --i) {
\r
270 item.addTo(target);
\r
273 public String getInternal(int depth, Set alreadySeen) {
\r
274 String result = checkName(name, alreadySeen);
\r
275 if (result.startsWith("$")) return result;
\r
276 result = indent(depth) + result + "REPEAT(" + weightedIndex
\r
277 + "; "+ item.getInternal(depth+1, alreadySeen)
\r
282 // match longest, e.g. up to just before a failure
\r
283 protected boolean match(String input, Position p) {
\r
284 //int bestMatch = p.index;
\r
286 for (int i = 0; i < weightedIndex.weights.length; ++i) {
\r
287 if (p.isFailure(this,i)) break;
\r
288 if (!item.match(input, p)) {
\r
289 p.setFailure(this,i);
\r
292 //bestMatch = p.index;
\r
295 if (count >= minCount) {
\r
298 // TODO fix failure
\r
303 private static class CodePoint extends FinalPick {
\r
304 private UnicodeSet source;
\r
306 private CodePoint(UnicodeSet source) {
\r
307 this.source = source;
\r
309 protected void addTo(Target target) {
\r
310 target.append(source.charAt(pick(target.random,0,source.size()-1)));
\r
312 protected boolean match(String s, Position p) {
\r
313 int cp = UTF16.charAt(s, p.index);
\r
314 if (source.contains(cp)) {
\r
315 p.index += UTF16.getCharCount(cp);
\r
318 p.setMax("codePoint");
\r
321 public String getInternal(int depth, Set alreadySeen) {
\r
322 String result = checkName(name, alreadySeen);
\r
323 if (result.startsWith("$")) return result;
\r
324 return source.toString();
\r
328 static class Morph extends ItemPick {
\r
333 private String lastValue = null;
\r
334 private Target addBuffer = Target.make(this, null, new Quoter.RuleQuoter());
\r
335 private StringBuffer mergeBuffer = new StringBuffer();
\r
337 private static final int COPY_NEW = 0, COPY_BOTH = 1, COPY_LAST = 3, SKIP = 4,
\r
339 // give weights to the above. make sure we delete about the same as we insert
\r
340 private static final WeightedIndex choice = new WeightedIndex(0)
\r
341 .add(new int[] {10, 10, 100, 10});
\r
343 protected void addTo(Target target) {
\r
344 // get contents into separate buffer
\r
345 addBuffer.copyState(target);
\r
347 item.addTo(addBuffer);
\r
348 String newValue = addBuffer.get();
\r
349 if (DEBUG) System.out.println("Old: " + lastValue + ", New:" + newValue);
\r
351 // if not first one, merge with old
\r
352 if (lastValue != null) {
\r
353 mergeBuffer.setLength(0);
\r
356 // the new length is a random value between old and new.
\r
357 int newLenLimit = (int) pick(target.random, lastValue.length(), newValue.length());
\r
359 while (mergeBuffer.length() < newLenLimit
\r
360 && newIndex < newValue.length()
\r
361 && lastIndex < lastValue.length()) {
\r
362 int c = choice.toIndex(target.nextDouble());
\r
363 if (c == COPY_NEW || c == COPY_BOTH || c == SKIP) {
\r
364 newIndex = getChar(newValue, newIndex, mergeBuffer, c < LEAST_SKIP);
\r
365 if (mergeBuffer.length() >= newLenLimit) break;
\r
367 if (c == COPY_LAST || c == COPY_BOTH || c == SKIP) {
\r
368 lastIndex = getChar(lastValue, lastIndex, mergeBuffer, c < LEAST_SKIP);
\r
371 newValue = mergeBuffer.toString();
\r
373 lastValue = newValue;
\r
374 target.append(newValue);
\r
375 if (DEBUG) System.out.println("Result: " + newValue);
\r
378 public String getInternal(int depth, Set alreadySeen) {
\r
379 String result = checkName(name, alreadySeen);
\r
380 if (result.startsWith("$")) return result;
\r
381 return indent(depth) + result + "MORPH("
\r
382 + item.getInternal(depth+1, alreadySeen)
\r
387 * @see Pick#match(java.lang.String, Pick.Position)
\r
389 protected boolean match(String input, Position p) {
\r
390 // TODO Auto-generated method stub
\r
395 /* Add character if we can
\r
397 static int getChar(String newValue, int newIndex, StringBuffer mergeBuffer, boolean copy) {
\r
398 if (newIndex >= newValue.length()) return newIndex;
\r
399 int cp = UTF16.charAt(newValue,newIndex);
\r
400 if (copy) UTF16.append(mergeBuffer, cp);
\r
401 return newIndex + UTF16.getCharCount(cp);
\r
406 appendQuoted(target, addBuffer.toString(), quoteBuffer);
\r
408 StringBuffer swapTemp = addBuffer;
\r
409 addBuffer = source;
\r
416 static class Quote extends ItemPick {
\r
420 protected void addTo(Target target) {
\r
421 target.quoter.setQuoting(true);
\r
422 item.addTo(target);
\r
423 target.quoter.setQuoting(false);
\r
426 protected boolean match(String s, Position p) {
\r
430 public String getInternal(int depth, Set alreadySeen) {
\r
431 String result = checkName(name, alreadySeen);
\r
432 if (result.startsWith("$")) return result;
\r
433 return indent(depth) + result + "QUOTE(" + item.getInternal(depth+1, alreadySeen)
\r
438 private static class Literal extends FinalPick {
\r
439 public String toString() {
\r
442 private Literal(String source) {
\r
443 this.name = source;
\r
445 protected void addTo(Target target) {
\r
446 target.append(name);
\r
448 protected boolean match(String input, Position p) {
\r
449 int len = name.length();
\r
450 if (input.regionMatches(p.index, name, 0, len)) {
\r
454 p.setMax("literal");
\r
457 public String getInternal(int depth, Set alreadySeen) {
\r
458 return "'" + name + "'";
\r
462 public static class Position {
\r
463 public ArrayList failures = new ArrayList();
\r
466 public String maxType;
\r
467 public void setMax(String type) {
\r
468 if (index >= maxInt) {
\r
472 public String toString() {
\r
473 return "index; " + index
\r
474 + ", maxInt:" + maxInt
\r
475 + ", maxType: " + maxType;
\r
477 /*private static final Object BAD = new Object();
\r
478 private static final Object GOOD = new Object();*/
\r
480 public boolean isFailure(Pick pick, int item) {
\r
481 ArrayList val = (ArrayList)failures.get(index);
\r
482 if (val == null) return false;
\r
483 Set set = (Set)val.get(item);
\r
484 if (set == null) return false;
\r
485 return !set.contains(pick);
\r
487 public void setFailure(Pick pick, int item) {
\r
488 ArrayList val = (ArrayList)failures.get(index);
\r
490 val = new ArrayList();
\r
491 failures.set(index, val);
\r
493 Set set = (Set)val.get(item);
\r
495 set = new HashSet();
\r
496 val.set(item, set);
\r
503 public static final Pick NOTHING = new Nothing();
\r
506 private static class Nothing extends FinalPick {
\r
507 protected void addTo(Target target) {}
\r
508 protected boolean match(String input, Position p) {
\r
511 public String getInternal(int depth, Set alreadySeen) {
\r
512 return indent(depth) + "\u00F8";
\r
519 abstract static class Visitor {
\r
520 Set already = new HashSet();
\r
521 // Note: each visitor should return the Pick that will replace a (or a itself)
\r
522 abstract Pick handle(Pick a);
\r
523 boolean alreadyEntered(Pick item) {
\r
524 boolean result = already.contains(item);
\r
533 protected abstract Pick visit(Visitor visitor);
\r
535 static class Replacer extends Visitor {
\r
538 Replacer(String toReplace, Pick replacement) {
\r
539 this.toReplace = toReplace;
\r
540 this.replacement = replacement;
\r
542 public Pick handle(Pick a) {
\r
543 if (toReplace.equals(a.name)) {
\r
550 abstract private static class FinalPick extends Pick {
\r
551 public Pick visit(Visitor visitor) {
\r
552 return visitor.handle(this);
\r
556 private abstract static class ItemPick extends Pick {
\r
557 protected Pick item;
\r
559 ItemPick (Pick item) {
\r
563 public Pick visit(Visitor visitor) {
\r
564 Pick result = visitor.handle(this);
\r
565 if (visitor.alreadyEntered(this)) return result;
\r
566 if (item != null) item = item.visit(visitor);
\r
571 private abstract static class ListPick extends Pick {
\r
572 protected Pick[] items = new Pick[0];
\r
574 @SuppressWarnings("unused")
\r
576 if (items.length > 1) return this;
\r
577 if (items.length == 1) return items[0];
\r
581 @SuppressWarnings("unused")
\r
583 return items.length;
\r
586 @SuppressWarnings("unused")
\r
588 return items[items.length-1];
\r
591 @SuppressWarnings("unused")
\r
592 void setLast(Pick newOne) {
\r
593 items[items.length-1] = newOne;
\r
596 protected void addInternal(Pick[] objs) {
\r
597 int lastLen = items.length;
\r
598 items = realloc(items, items.length + objs.length);
\r
599 for (int i = 0; i < objs.length; ++i) {
\r
600 items[lastLen + i] = objs[i];
\r
604 public Pick visit(Visitor visitor) {
\r
605 Pick result = visitor.handle(this);
\r
606 if (visitor.alreadyEntered(this)) return result;
\r
607 for (int i = 0; i < items.length; ++i) {
\r
608 items[i] = items[i].visit(visitor);
\r
615 * Simple class to distribute a number between 0 (inclusive) and 1 (exclusive) among
\r
616 * a number of indices, where each index is weighted.
\r
617 * Item weights may be zero, but cannot be negative.
\r
620 // As in other case, we use an array for runtime speed; don't care about buildspeed.
\r
621 public static class WeightedIndex {
\r
622 private int[] weights = new int[0];
\r
623 private int minCount = 0;
\r
624 private double total;
\r
626 public WeightedIndex(int minCount) {
\r
627 this.minCount = minCount;
\r
630 public WeightedIndex add(int count, int itemWeights) {
\r
632 int[] newWeights = new int[count];
\r
633 if (itemWeights < 1) itemWeights = 1;
\r
634 Arrays.fill(newWeights, 0, count, itemWeights);
\r
635 add(1, newWeights);
\r
637 return this; // for chaining
\r
640 public WeightedIndex add(int[] newWeights) {
\r
641 return add(newWeights.length, newWeights);
\r
644 public WeightedIndex add(int maxCount, int[] newWeights) {
\r
645 if (newWeights == null) newWeights = new int[]{1};
\r
646 int oldLen = weights.length;
\r
647 if (maxCount < newWeights.length) maxCount = newWeights.length;
\r
648 weights = (int[]) realloc(weights, weights.length + maxCount);
\r
649 System.arraycopy(newWeights, 0, weights, oldLen, newWeights.length);
\r
650 int lastWeight = weights[oldLen + newWeights.length-1];
\r
651 for (int i = oldLen + newWeights.length; i < maxCount; ++i) {
\r
652 weights[i] = lastWeight;
\r
655 for (int i = 0; i < weights.length; ++i) {
\r
656 if (weights[i] < 0) {
\r
657 throw new RuntimeException("only positive weights: " + i);
\r
659 total += weights[i];
\r
661 return this; // for chaining
\r
664 // TODO, make this more efficient
\r
665 public int toIndex(double zeroToOne) {
\r
666 double weight = zeroToOne*total;
\r
668 for (i = 0; i < weights.length; ++i) {
\r
669 weight -= weights[i];
\r
670 if (weight <= 0) break;
\r
672 return i + minCount;
\r
674 public String toString() {
\r
675 String result = "";
\r
676 for (int i = 0; i < minCount; ++i) {
\r
677 if (result.length() != 0) result += ",";
\r
680 for (int i = 0; i < weights.length; ++i) {
\r
681 if (result.length() != 0) result += ",";
\r
682 result += weights[i];
\r
688 private static Pick convert(Object obj) {
\r
689 if (obj instanceof Pick) return (Pick)obj;
\r
690 return new Literal(obj.toString(), false);
\r
695 static public int pick(Random random, int start, int end) {
\r
696 return start + (int)(random.nextDouble() * (end + 1 - start));
\r
699 static public double pick(Random random, double start, double end) {
\r
700 return start + (random.nextDouble() * (end + 1 - start));
\r
703 static public boolean pick(Random random, double percent) {
\r
704 return random.nextDouble() <= percent;
\r
707 static public int pick(Random random, UnicodeSet s) {
\r
708 return s.charAt(pick(random, 0,s.size()-1));
\r
711 static public String pick(Random random, String[] source) {
\r
712 return source[pick(random, 0, source.length-1)];
\r
715 // these utilities really ought to be in Java
\r
717 public static double[] realloc(double[] source, int newSize) {
\r
718 double[] temp = new double[newSize];
\r
719 if (newSize > source.length) newSize = source.length;
\r
720 if (newSize != 0) System.arraycopy(source,0,temp,0,newSize);
\r
724 public static int[] realloc(int[] source, int newSize) {
\r
725 int[] temp = new int[newSize];
\r
726 if (newSize > source.length) newSize = source.length;
\r
727 if (newSize != 0) System.arraycopy(source,0,temp,0,newSize);
\r
731 public static Pick[] realloc(Pick[] source, int newSize) {
\r
732 Pick[] temp = new Pick[newSize];
\r
733 if (newSize > source.length) newSize = source.length;
\r
734 if (newSize != 0) System.arraycopy(source,0,temp,0,newSize);
\r
739 /*private static void append(StringBuffer target, String toAdd, StringBuffer quoteBuffer) {
\r
740 Utility.appendToRule(target, (int)-1, true, false, quoteBuffer); // close previous quote
\r
741 if (DEBUG) System.out.println("\"" + toAdd + "\"");
\r
742 target.append(toAdd);
\r
745 private static void appendQuoted(StringBuffer target, String toAdd, StringBuffer quoteBuffer) {
\r
746 if (DEBUG) System.out.println("\"" + toAdd + "\"");
\r
747 Utility.appendToRule(target, toAdd, false, false, quoteBuffer);
\r
751 public static abstract class MatchHandler {
\r
752 public abstract void handleString(String source, int start, int limit);
\r
753 public abstract void handleSequence(String source, int start, int limit);
\r
754 public abstract void handleAlternation(String source, int start, int limit);
\r
759 // redistributes random value
\r
760 // values are still between 0 and 1, but with a different distribution
\r
761 public interface Spread {
\r
762 public double spread(double value);
\r
765 // give the weight for the high end.
\r
766 // values are linearly scaled according to the weight.
\r
767 static public class SimpleSpread implements Spread {
\r
768 static final Spread FLAT = new SimpleSpread(1.0);
\r
769 boolean flat = false;
\r
771 public SimpleSpread(double maxWeight) {
\r
772 if (maxWeight > 0.999 && maxWeight < 1.001) {
\r
775 double q = (maxWeight - 1.0);
\r
781 public double spread(double value) {
\r
782 if (flat) return value;
\r
783 value = aa + Math.sqrt(bb + cc*value);
\r
784 if (value < 0.0) return 0.0; // catch math gorp
\r
785 if (value >= 1.0) return 1.0;
\r
789 static public int pick(Spread spread, Random random, int start, int end) {
\r
790 return start + (int)(spread.spread(random.nextDouble()) * (end + 1 - start));
\r