xref: /aosp_15_r20/external/cldr/tools/cldr-code/src/main/java/org/unicode/cldr/util/Pick.java (revision 912701f9769bb47905792267661f0baf2b85bed5)

/*
 *******************************************************************************
 * Copyright (C) 2002-2012, International Business Machines Corporation and    *
 * others. All Rights Reserved.                                                *
 *******************************************************************************
 */
package org.unicode.cldr.util;

import com.google.common.collect.LinkedHashMultiset;
import com.google.common.collect.Multiset;
import com.ibm.icu.text.UTF16;
import com.ibm.icu.text.UnicodeSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public abstract class Pick {
    private static boolean DEBUG = false;

    // for using to get strings

    static class Target {

        static int MAX_COUNT = 5;

        private Pick pick;
        private Random random;
        private Quoter quoter;
        private Multiset<Pick> stack = LinkedHashMultiset.create();

        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();
            stack.clear();
            while (true) {
                try {
                    pick.addTo(this);
                    return get();
                } catch (DepthExceededException e) {
                    for (Pick pick : e.target.stack.elementSet()) {
                        System.out.println(pick.name + ": " + e.target.stack.count(pick));
                    }
                    int debug = 0;
                }
            }
        }

        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) {
            if (codepoint == '-') {
                int debug = 0;
            }
            quoter.append(codepoint);
            return this;
        }

        private Target append(String s) {
            if (s.contains("-")) {
                int debug = 0;
            }
            quoter.append(s);
            return this;
        }

        // must return value between 0 (inc) and 1 (exc)
        private double nextDouble() {
            return random.nextDouble();
        }

        public void exitStack(Pick pick) {
            stack.remove(pick);
        }

        public void enterStack(Pick pick) {
            int count = stack.count(pick);
            if (count > MAX_COUNT) {
                throw new DepthExceededException(this, pick);
            }
            stack.add(pick);
        }
    }

    // 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;
    }

    public static Pick.Sequence makeSequence() {
        return new Sequence();
    }

    public static 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));
    }
     */

    public static Pick repeat(int minCount, int maxCount, int[] itemWeights, Pick item) {
        return new Repeat(minCount, maxCount, itemWeights, item);
    }

    public static Pick codePoint(UnicodeSet source) {
        return new CodePoint(source);
    }

    public static 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);

    static class DepthExceededException extends RuntimeException {
        private static final long serialVersionUID = -2478735802169169979L;
        private final Target target;
        private final Pick pick;

        public DepthExceededException(Target target, Pick pick) {
            this.target = target;
            this.pick = pick;
        }
    }

    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
        }

        @Override
        protected void addTo(Target target) {
            for (int i = 0; i < items.length; ++i) {
                items[i].addTo(target);
            }
        }

        @Override
        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() {}

        @Override
        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
        }

        @Override
        protected void addTo(Target target) {
            final int index = weightedIndex.toIndex(target.nextDouble());
            int last = index - 1;
            if (last < weightedIndex.minCount) {
                last -= weightedIndex.minCount;
                last += weightedIndex.weights.length;
            }
            for (int i = index; ; ) {
                try {
                    target.enterStack(this);
                    items[index].addTo(target); // may cause exception if stack overflows
                    // no exception, continue normally
                    target.exitStack(this);
                    return;
                } catch (DepthExceededException e) {
                    target.exitStack(this);
                    if (i == last) {
                        throw e; // we tried all the options, and none of them work.
                    }
                    i++;
                    if (i >= weightedIndex.weights.length) {
                        i -= weightedIndex.weights.length - weightedIndex.minCount;
                    }
                }
            }
        }

        @Override
        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
        @Override
        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);
        }
         */
        @Override
        protected void addTo(Target target) {
            // int count ;
            final int count = weightedIndex.toIndex(target.nextDouble());
            for (int i = count; i > 0; --i) {
                item.addTo(target);
            }
        }

        @Override
        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
        @Override
        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;
        }

        @Override
        protected void addTo(Target target) {
            target.append(source.charAt(pick(target.random, 0, source.size() - 1)));
        }

        @Override
        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;
        }

        @Override
        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});

        @Override
        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 = 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);
        }

        @Override
        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)
         */
        @Override
        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);
        }

        @Override
        protected void addTo(Target target) {
            target.quoter.setQuoting(true);
            item.addTo(target);
            target.quoter.setQuoting(false);
        }

        @Override
        public boolean match(String s, Position p) {
            return false;
        }

        @Override
        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 {
        @Override
        public String toString() {
            return name;
        }

        private Literal(String source) {
            this.name = source;
        }

        @Override
        protected void addTo(Target target) {
            target.append(name);
        }

        @Override
        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;
        }

        @Override
        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;
            }
        }

        @Override
        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;
        }

        @Override
        public Pick handle(Pick a) {
            if (toReplace.equals(a.name)) {
                a = replacement;
            }
            return a;
        }
    }

    private abstract static class FinalPick extends Pick {
        @Override
        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;
        }

        @Override
        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];
            }
        }

        @Override
        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 = 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;
        }

        @Override
        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

    public static int pick(Random random, int start, int end) {
        return start + (int) (random.nextDouble() * (end + 1 - start));
    }

    public static double pick(Random random, double start, double end) {
        return start + (random.nextDouble() * (end + 1 - start));
    }

    public static boolean pick(Random random, double percent) {
        return random.nextDouble() <= percent;
    }

    public static int pick(Random random, UnicodeSet s) {
        return s.charAt(pick(random, 0, s.size() - 1));
    }

    public static 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));
    }

     */

}