| /* |
| ******************************************************************************* |
| * Copyright (C) 2002-2012, International Business Machines Corporation and * |
| * others. All Rights Reserved. * |
| ******************************************************************************* |
| */ |
| package com.ibm.icu.dev.util; |
| |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.HashSet; |
| import java.util.Random; |
| import java.util.Set; |
| |
| import com.ibm.icu.text.UTF16; |
| import com.ibm.icu.text.UnicodeSet; |
| |
| abstract public class Pick { |
| private static boolean DEBUG = false; |
| |
| // for using to get strings |
| |
| static class Target { |
| private Pick pick; |
| private Random random; |
| private Quoter quoter; |
| |
| public static Target make(Pick pick, Random random, Quoter quoter) { |
| Target result = new Target(); |
| result.pick = pick; |
| result.random = random; |
| result.quoter = quoter; |
| return result; |
| } |
| public String next() { |
| quoter.clear(); |
| pick.addTo(this); |
| return get(); |
| } |
| public String get() { |
| return quoter.toString(); |
| } |
| private void copyState(Target other) { |
| random = other.random; |
| } |
| private void clear() { |
| quoter.clear(); |
| } |
| /*private int length() { |
| return quoter.length(); |
| }*/ |
| private Target append(int codepoint) { |
| quoter.append(codepoint); |
| return this; |
| } |
| private Target append(String s) { |
| quoter.append(s); |
| return this; |
| } |
| // must return value between 0 (inc) and 1 (exc) |
| private double nextDouble() { |
| return random.nextDouble(); |
| } |
| } |
| |
| // for Building |
| |
| public Pick replace(String toReplace, Pick replacement) { |
| Replacer visitor = new Replacer(toReplace, replacement); |
| return visit(visitor); |
| } |
| |
| public Pick name(String nameStr) { |
| name = nameStr; |
| return this; |
| } |
| |
| static public Pick.Sequence makeSequence() { |
| return new Sequence(); |
| } |
| static public Pick.Alternation makeAlternation() { |
| return new Alternation(); |
| } |
| /* |
| static public Pick.Sequence and(Object item) { |
| return new Sequence().and2(item); |
| } |
| static public Pick.Sequence and(Object[] items) { |
| return new Sequence().and2(items); |
| } |
| static public Pick.Alternation or(int itemWeight, Object item) { |
| return new Alternation().or2(itemWeight, item); |
| } |
| static public Pick.Alternation or(Object[] items) { |
| return new Alternation().or2(1, items); |
| } |
| static public Pick.Alternation or(int itemWeight, Object[] items) { |
| return new Alternation().or2(itemWeight, items); |
| } |
| static public Pick.Alternation or(int[] itemWeights, Object[] items) { |
| return new Alternation().or2(itemWeights, items); |
| } |
| |
| static public Pick maybe(int percent, Object item) { |
| return new Repeat(0, 1, new int[]{100-percent, percent}, item); |
| //return Pick.or(1.0-percent, NOTHING).or2(percent, item); |
| } |
| static public Pick repeat(int minCount, int maxCount, int itemWeights, Object item) { |
| return new Repeat(minCount, maxCount, itemWeights, item); |
| } |
| |
| static public Pick codePoint(String source) { |
| return new CodePoint(new UnicodeSet(source)); |
| } |
| */ |
| |
| static public Pick repeat(int minCount, int maxCount, int[] itemWeights, Pick item) { |
| return new Repeat(minCount, maxCount, itemWeights, item); |
| } |
| |
| static public Pick codePoint(UnicodeSet source) { |
| return new CodePoint(source); |
| } |
| static public Pick string(String source) { |
| return new Literal(source); |
| } |
| /* |
| static public Pick unquoted(String source) { |
| return new Literal(source); |
| } |
| static public Pick string(int minLength, int maxLength, Pick item) { |
| return new Morph(item, minLength, maxLength); |
| } |
| */ |
| |
| public abstract String getInternal(int depth, Set alreadySeen); |
| // Internals |
| |
| protected String name; |
| |
| protected abstract void addTo(Target target); |
| public abstract boolean match(String input, Position p); |
| |
| public static class Sequence extends ListPick { |
| public Sequence and2 (Pick item) { |
| addInternal(new Pick[] {item}); // we don't care about perf |
| return this; // for chaining |
| } |
| public Sequence and2 (Pick[] itemArray) { |
| addInternal(itemArray); |
| return this; // for chaining |
| } |
| protected void addTo(Target target) { |
| for (int i = 0; i < items.length; ++i) { |
| items[i].addTo(target); |
| } |
| } |
| public String getInternal(int depth, Set alreadySeen) { |
| String result = checkName(name, alreadySeen); |
| if (result.startsWith("$")) return result; |
| result = indent(depth) + result + "SEQ("; |
| for (int i = 0; i < items.length; ++i) { |
| if (i != 0) result += ", "; |
| result += items[i].getInternal(depth+1, alreadySeen); |
| } |
| result += ")"; |
| return result; |
| } |
| // keep private |
| private Sequence() {} |
| public boolean match(String input, Position p) { |
| int originalIndex = p.index; |
| for (int i = 0; i < items.length; ++i) { |
| if (!items[i].match(input, p)) { |
| p.index = originalIndex; |
| return false; |
| } |
| } |
| return true; |
| } |
| } |
| |
| String checkName(String nameStr, Set alreadySeen) { |
| if (nameStr == null) return ""; |
| if (alreadySeen.contains(nameStr)) return nameStr; |
| alreadySeen.add(nameStr); |
| return "{" + nameStr + "=}"; |
| } |
| |
| public static class Alternation extends ListPick { |
| private WeightedIndex weightedIndex = new WeightedIndex(0); |
| |
| public Alternation or2 (Pick[] newItems) { |
| return or2(1, newItems); |
| } |
| public Alternation or2 (int itemWeight, Pick item) { |
| return or2(itemWeight, new Pick[] {item}); // we don't care about perf |
| } |
| public Alternation or2 (int itemWeight, Pick[] newItems) { |
| int[] itemWeights = new int[newItems.length]; |
| Arrays.fill(itemWeights,itemWeight); |
| return or2(itemWeights, newItems); // we don't care about perf |
| } |
| public Alternation or2 (int[] itemWeights, Pick[] newItems) { |
| if (newItems.length != itemWeights.length) { |
| throw new ArrayIndexOutOfBoundsException( |
| "or lengths must be equal: " + newItems.length + " != " + itemWeights.length); |
| } |
| // int lastLen = this.items.length; |
| addInternal(newItems); |
| weightedIndex.add(itemWeights); |
| return this; // for chaining |
| } |
| protected void addTo(Target target) { |
| items[weightedIndex.toIndex(target.nextDouble())].addTo(target); |
| } |
| |
| public String getInternal(int depth, Set alreadySeen) { |
| String result = checkName(name, alreadySeen); |
| if (result.startsWith("$")) return result; |
| result = indent(depth) + result + "OR("; |
| for (int i = 0; i < items.length; ++i) { |
| if (i != 0) result += ", "; |
| result += items[i].getInternal(depth+1, alreadySeen) + "/" + weightedIndex.weights[i]; |
| } |
| return result + ")"; |
| } |
| // keep private |
| private Alternation() {} |
| // take first matching option |
| public boolean match(String input, Position p) { |
| for (int i = 0; i < weightedIndex.weights.length; ++i) { |
| if (p.isFailure(this,i)) continue; |
| if (items[i].match(input, p)) return true; |
| p.setFailure(this, i); |
| } |
| return false; |
| } |
| } |
| |
| private static String indent(int depth) { |
| String result = "\r\n"; |
| for (int i = 0; i < depth; ++i) { |
| result += " "; |
| } |
| return result; |
| } |
| |
| private static class Repeat extends ItemPick { |
| WeightedIndex weightedIndex; |
| int minCount = 0; |
| |
| private Repeat(int minCount, int maxCount, int[] itemWeights, Pick item) { |
| super(item); |
| weightedIndex = new WeightedIndex(minCount).add(maxCount-minCount+1, itemWeights); |
| } |
| /*private Repeat(int minCount, int maxCount, int itemWeight, Pick item) { |
| super(item); |
| weightedIndex = new WeightedIndex(minCount).add(maxCount-minCount+1, itemWeight); |
| }*/ |
| /* |
| private Repeat(int minCount, int maxCount, Object item) { |
| this.item = convert(item); |
| weightedIndex = new WeightedIndex(minCount).add(maxCount-minCount+1, 1); |
| } |
| */ |
| protected void addTo(Target target) { |
| //int count ; |
| for (int i = weightedIndex.toIndex(target.nextDouble()); i > 0; --i) { |
| item.addTo(target); |
| } |
| } |
| public String getInternal(int depth, Set alreadySeen) { |
| String result = checkName(name, alreadySeen); |
| if (result.startsWith("$")) return result; |
| result = indent(depth) + result + "REPEAT(" + weightedIndex |
| + "; "+ item.getInternal(depth+1, alreadySeen) |
| + ")"; |
| return result; |
| } |
| |
| // match longest, e.g. up to just before a failure |
| public boolean match(String input, Position p) { |
| //int bestMatch = p.index; |
| int count = 0; |
| for (int i = 0; i < weightedIndex.weights.length; ++i) { |
| if (p.isFailure(this,i)) break; |
| if (!item.match(input, p)) { |
| p.setFailure(this,i); |
| break; |
| } |
| //bestMatch = p.index; |
| count++; |
| } |
| if (count >= minCount) { |
| return true; |
| } |
| // TODO fix failure |
| return false; |
| } |
| } |
| |
| private static class CodePoint extends FinalPick { |
| private UnicodeSet source; |
| |
| private CodePoint(UnicodeSet source) { |
| this.source = source; |
| } |
| protected void addTo(Target target) { |
| target.append(source.charAt(pick(target.random,0,source.size()-1))); |
| } |
| public boolean match(String s, Position p) { |
| int cp = UTF16.charAt(s, p.index); |
| if (source.contains(cp)) { |
| p.index += UTF16.getCharCount(cp); |
| return true; |
| } |
| p.setMax("codePoint"); |
| return false; |
| } |
| public String getInternal(int depth, Set alreadySeen) { |
| String result = checkName(name, alreadySeen); |
| if (result.startsWith("$")) return result; |
| return source.toString(); |
| } |
| } |
| |
| static class Morph extends ItemPick { |
| Morph(Pick item) { |
| super(item); |
| } |
| |
| private String lastValue = null; |
| private Target addBuffer = Target.make(this, null, new Quoter.RuleQuoter()); |
| private StringBuffer mergeBuffer = new StringBuffer(); |
| |
| private static final int COPY_NEW = 0, COPY_BOTH = 1, COPY_LAST = 3, SKIP = 4, |
| LEAST_SKIP = 4; |
| // give weights to the above. make sure we delete about the same as we insert |
| private static final WeightedIndex choice = new WeightedIndex(0) |
| .add(new int[] {10, 10, 100, 10}); |
| |
| protected void addTo(Target target) { |
| // get contents into separate buffer |
| addBuffer.copyState(target); |
| addBuffer.clear(); |
| item.addTo(addBuffer); |
| String newValue = addBuffer.get(); |
| if (DEBUG) System.out.println("Old: " + lastValue + ", New:" + newValue); |
| |
| // if not first one, merge with old |
| if (lastValue != null) { |
| mergeBuffer.setLength(0); |
| int lastIndex = 0; |
| int newIndex = 0; |
| // the new length is a random value between old and new. |
| int newLenLimit = (int) pick(target.random, lastValue.length(), newValue.length()); |
| |
| while (mergeBuffer.length() < newLenLimit |
| && newIndex < newValue.length() |
| && lastIndex < lastValue.length()) { |
| int c = choice.toIndex(target.nextDouble()); |
| if (c == COPY_NEW || c == COPY_BOTH || c == SKIP) { |
| newIndex = getChar(newValue, newIndex, mergeBuffer, c < LEAST_SKIP); |
| if (mergeBuffer.length() >= newLenLimit) break; |
| } |
| if (c == COPY_LAST || c == COPY_BOTH || c == SKIP) { |
| lastIndex = getChar(lastValue, lastIndex, mergeBuffer, c < LEAST_SKIP); |
| } |
| } |
| newValue = mergeBuffer.toString(); |
| } |
| lastValue = newValue; |
| target.append(newValue); |
| if (DEBUG) System.out.println("Result: " + newValue); |
| } |
| |
| public String getInternal(int depth, Set alreadySeen) { |
| String result = checkName(name, alreadySeen); |
| if (result.startsWith("$")) return result; |
| return indent(depth) + result + "MORPH(" |
| + item.getInternal(depth+1, alreadySeen) |
| + ")"; |
| } |
| |
| /* (non-Javadoc) |
| * @see Pick#match(java.lang.String, Pick.Position) |
| */ |
| public boolean match(String input, Position p) { |
| // TODO Auto-generated method stub |
| return false; |
| } |
| } |
| |
| /* Add character if we can |
| */ |
| static int getChar(String newValue, int newIndex, StringBuffer mergeBuffer, boolean copy) { |
| if (newIndex >= newValue.length()) return newIndex; |
| int cp = UTF16.charAt(newValue,newIndex); |
| if (copy) UTF16.append(mergeBuffer, cp); |
| return newIndex + UTF16.getCharCount(cp); |
| } |
| |
| /* |
| // quoted add |
| appendQuoted(target, addBuffer.toString(), quoteBuffer); |
| // fix buffers |
| StringBuffer swapTemp = addBuffer; |
| addBuffer = source; |
| source = swapTemp; |
| } |
| } |
| */ |
| |
| |
| static class Quote extends ItemPick { |
| Quote(Pick item) { |
| super(item); |
| } |
| protected void addTo(Target target) { |
| target.quoter.setQuoting(true); |
| item.addTo(target); |
| target.quoter.setQuoting(false); |
| } |
| |
| public boolean match(String s, Position p) { |
| return false; |
| } |
| |
| public String getInternal(int depth, Set alreadySeen) { |
| String result = checkName(name, alreadySeen); |
| if (result.startsWith("$")) return result; |
| return indent(depth) + result + "QUOTE(" + item.getInternal(depth+1, alreadySeen) |
| + ")"; |
| } |
| } |
| |
| private static class Literal extends FinalPick { |
| public String toString() { |
| return name; |
| } |
| private Literal(String source) { |
| this.name = source; |
| } |
| protected void addTo(Target target) { |
| target.append(name); |
| } |
| public boolean match(String input, Position p) { |
| int len = name.length(); |
| if (input.regionMatches(p.index, name, 0, len)) { |
| p.index += len; |
| return true; |
| } |
| p.setMax("literal"); |
| return false; |
| } |
| public String getInternal(int depth, Set alreadySeen) { |
| return "'" + name + "'"; |
| } |
| } |
| |
| public static class Position { |
| public ArrayList failures = new ArrayList(); |
| public int index; |
| public int maxInt; |
| public String maxType; |
| public void setMax(String type) { |
| if (index >= maxInt) { |
| maxType = type; |
| } |
| } |
| public String toString() { |
| return "index; " + index |
| + ", maxInt:" + maxInt |
| + ", maxType: " + maxType; |
| } |
| /*private static final Object BAD = new Object(); |
| private static final Object GOOD = new Object();*/ |
| |
| public boolean isFailure(Pick pick, int item) { |
| ArrayList val = (ArrayList)failures.get(index); |
| if (val == null) return false; |
| Set set = (Set)val.get(item); |
| if (set == null) return false; |
| return !set.contains(pick); |
| } |
| public void setFailure(Pick pick, int item) { |
| ArrayList val = (ArrayList)failures.get(index); |
| if (val == null) { |
| val = new ArrayList(); |
| failures.set(index, val); |
| } |
| Set set = (Set)val.get(item); |
| if (set == null) { |
| set = new HashSet(); |
| val.set(item, set); |
| } |
| set.add(pick); |
| } |
| } |
| |
| /* |
| public static final Pick NOTHING = new Nothing(); |
| |
| |
| private static class Nothing extends FinalPick { |
| protected void addTo(Target target) {} |
| protected boolean match(String input, Position p) { |
| return true; |
| } |
| public String getInternal(int depth, Set alreadySeen) { |
| return indent(depth) + "\u00F8"; |
| } |
| } |
| */ |
| |
| // intermediates |
| |
| abstract static class Visitor { |
| Set already = new HashSet(); |
| // Note: each visitor should return the Pick that will replace a (or a itself) |
| abstract Pick handle(Pick a); |
| boolean alreadyEntered(Pick item) { |
| boolean result = already.contains(item); |
| already.add(item); |
| return result; |
| } |
| void reset() { |
| already.clear(); |
| } |
| } |
| |
| protected abstract Pick visit(Visitor visitor); |
| |
| static class Replacer extends Visitor { |
| String toReplace; |
| Pick replacement; |
| Replacer(String toReplace, Pick replacement) { |
| this.toReplace = toReplace; |
| this.replacement = replacement; |
| } |
| public Pick handle(Pick a) { |
| if (toReplace.equals(a.name)) { |
| a = replacement; |
| } |
| return a; |
| } |
| } |
| |
| abstract private static class FinalPick extends Pick { |
| public Pick visit(Visitor visitor) { |
| return visitor.handle(this); |
| } |
| } |
| |
| private abstract static class ItemPick extends Pick { |
| protected Pick item; |
| |
| ItemPick (Pick item) { |
| this.item = item; |
| } |
| |
| public Pick visit(Visitor visitor) { |
| Pick result = visitor.handle(this); |
| if (visitor.alreadyEntered(this)) return result; |
| if (item != null) item = item.visit(visitor); |
| return result; |
| } |
| } |
| |
| private abstract static class ListPick extends Pick { |
| protected Pick[] items = new Pick[0]; |
| |
| Pick simplify() { |
| if (items.length > 1) return this; |
| if (items.length == 1) return items[0]; |
| return null; |
| } |
| |
| int size() { |
| return items.length; |
| } |
| |
| Pick getLast() { |
| return items[items.length-1]; |
| } |
| |
| void setLast(Pick newOne) { |
| items[items.length-1] = newOne; |
| } |
| |
| protected void addInternal(Pick[] objs) { |
| int lastLen = items.length; |
| items = realloc(items, items.length + objs.length); |
| for (int i = 0; i < objs.length; ++i) { |
| items[lastLen + i] = objs[i]; |
| } |
| } |
| |
| public Pick visit(Visitor visitor) { |
| Pick result = visitor.handle(this); |
| if (visitor.alreadyEntered(this)) return result; |
| for (int i = 0; i < items.length; ++i) { |
| items[i] = items[i].visit(visitor); |
| } |
| return result; |
| } |
| } |
| |
| /** |
| * Simple class to distribute a number between 0 (inclusive) and 1 (exclusive) among |
| * a number of indices, where each index is weighted. |
| * Item weights may be zero, but cannot be negative. |
| * @author Davis |
| */ |
| // As in other case, we use an array for runtime speed; don't care about buildspeed. |
| public static class WeightedIndex { |
| private int[] weights = new int[0]; |
| private int minCount = 0; |
| private double total; |
| |
| public WeightedIndex(int minCount) { |
| this.minCount = minCount; |
| } |
| |
| public WeightedIndex add(int count, int itemWeights) { |
| if (count > 0) { |
| int[] newWeights = new int[count]; |
| if (itemWeights < 1) itemWeights = 1; |
| Arrays.fill(newWeights, 0, count, itemWeights); |
| add(1, newWeights); |
| } |
| return this; // for chaining |
| } |
| |
| public WeightedIndex add(int[] newWeights) { |
| return add(newWeights.length, newWeights); |
| } |
| |
| public WeightedIndex add(int maxCount, int[] newWeights) { |
| if (newWeights == null) newWeights = new int[]{1}; |
| int oldLen = weights.length; |
| if (maxCount < newWeights.length) maxCount = newWeights.length; |
| weights = (int[]) realloc(weights, weights.length + maxCount); |
| System.arraycopy(newWeights, 0, weights, oldLen, newWeights.length); |
| int lastWeight = weights[oldLen + newWeights.length-1]; |
| for (int i = oldLen + newWeights.length; i < maxCount; ++i) { |
| weights[i] = lastWeight; |
| } |
| total = 0; |
| for (int i = 0; i < weights.length; ++i) { |
| if (weights[i] < 0) { |
| throw new RuntimeException("only positive weights: " + i); |
| } |
| total += weights[i]; |
| } |
| return this; // for chaining |
| } |
| |
| // TODO, make this more efficient |
| public int toIndex(double zeroToOne) { |
| double weight = zeroToOne*total; |
| int i; |
| for (i = 0; i < weights.length; ++i) { |
| weight -= weights[i]; |
| if (weight <= 0) break; |
| } |
| return i + minCount; |
| } |
| public String toString() { |
| String result = ""; |
| for (int i = 0; i < minCount; ++i) { |
| if (result.length() != 0) result += ","; |
| result += "0"; |
| } |
| for (int i = 0; i < weights.length; ++i) { |
| if (result.length() != 0) result += ","; |
| result += weights[i]; |
| } |
| return result; |
| } |
| } |
| /* |
| private static Pick convert(Object obj) { |
| if (obj instanceof Pick) return (Pick)obj; |
| return new Literal(obj.toString(), false); |
| } |
| */ |
| // Useful statics |
| |
| static public int pick(Random random, int start, int end) { |
| return start + (int)(random.nextDouble() * (end + 1 - start)); |
| } |
| |
| static public double pick(Random random, double start, double end) { |
| return start + (random.nextDouble() * (end + 1 - start)); |
| } |
| |
| static public boolean pick(Random random, double percent) { |
| return random.nextDouble() <= percent; |
| } |
| |
| static public int pick(Random random, UnicodeSet s) { |
| return s.charAt(pick(random, 0,s.size()-1)); |
| } |
| |
| static public String pick(Random random, String[] source) { |
| return source[pick(random, 0, source.length-1)]; |
| } |
| |
| // these utilities really ought to be in Java |
| |
| public static double[] realloc(double[] source, int newSize) { |
| double[] temp = new double[newSize]; |
| if (newSize > source.length) newSize = source.length; |
| if (newSize != 0) System.arraycopy(source,0,temp,0,newSize); |
| return temp; |
| } |
| |
| public static int[] realloc(int[] source, int newSize) { |
| int[] temp = new int[newSize]; |
| if (newSize > source.length) newSize = source.length; |
| if (newSize != 0) System.arraycopy(source,0,temp,0,newSize); |
| return temp; |
| } |
| |
| public static Pick[] realloc(Pick[] source, int newSize) { |
| Pick[] temp = new Pick[newSize]; |
| if (newSize > source.length) newSize = source.length; |
| if (newSize != 0) System.arraycopy(source,0,temp,0,newSize); |
| return temp; |
| } |
| |
| // test utilities |
| /*private static void append(StringBuffer target, String toAdd, StringBuffer quoteBuffer) { |
| Utility.appendToRule(target, (int)-1, true, false, quoteBuffer); // close previous quote |
| if (DEBUG) System.out.println("\"" + toAdd + "\""); |
| target.append(toAdd); |
| } |
| |
| private static void appendQuoted(StringBuffer target, String toAdd, StringBuffer quoteBuffer) { |
| if (DEBUG) System.out.println("\"" + toAdd + "\""); |
| Utility.appendToRule(target, toAdd, false, false, quoteBuffer); |
| }*/ |
| |
| /* |
| public static abstract class MatchHandler { |
| public abstract void handleString(String source, int start, int limit); |
| public abstract void handleSequence(String source, int start, int limit); |
| public abstract void handleAlternation(String source, int start, int limit); |
| |
| } |
| */ |
| /* |
| // redistributes random value |
| // values are still between 0 and 1, but with a different distribution |
| public interface Spread { |
| public double spread(double value); |
| } |
| |
| // give the weight for the high end. |
| // values are linearly scaled according to the weight. |
| static public class SimpleSpread implements Spread { |
| static final Spread FLAT = new SimpleSpread(1.0); |
| boolean flat = false; |
| double aa, bb, cc; |
| public SimpleSpread(double maxWeight) { |
| if (maxWeight > 0.999 && maxWeight < 1.001) { |
| flat = true; |
| } else { |
| double q = (maxWeight - 1.0); |
| aa = -1/q; |
| bb = 1/(q*q); |
| cc = (2.0+q)/q; |
| } |
| } |
| public double spread(double value) { |
| if (flat) return value; |
| value = aa + Math.sqrt(bb + cc*value); |
| if (value < 0.0) return 0.0; // catch math gorp |
| if (value >= 1.0) return 1.0; |
| return value; |
| } |
| } |
| static public int pick(Spread spread, Random random, int start, int end) { |
| return start + (int)(spread.spread(random.nextDouble()) * (end + 1 - start)); |
| } |
| |
| */ |
| |
| |
| } |