path: root/tools/java/org/unicode/cldr/util/StringRange.java

package org.unicode.cldr.util;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import com.ibm.icu.impl.Relation;
import com.ibm.icu.lang.CharSequences;
import com.ibm.icu.util.ICUException;

@SuppressWarnings("deprecation")
public class StringRange {
    private static final boolean DEBUG = false;

    public interface Adder {
        /**
         * @param start
         * @param end   may be null, for adding single string
         */
        void add(String start, String end);
    }

    public static final Comparator<int[]> COMPARE_INT_ARRAYS = new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            int minIndex = Math.min(o1.length, o2.length);
            for (int i = 0; i < minIndex; ++i) {
                int diff = o1[i] - o2[i];
                if (diff != 0) {
                    return diff;
                }
            }
            return o1.length - o2.length;
        }
    };

    /**
     * Compact the set of strings.
     * @param source
     * @param adder adds each pair to the output. See the {@link Adder} interface.
     * @param shorterPairs use abc-d instead of abc-abd
     * @param moreCompact use a more compact form, at the expense of more processing. If false, source must be sorted.
     */
    public static void compact(Set<String> source, Adder adder, boolean shorterPairs, boolean moreCompact) {
        if (!moreCompact) {
            String start = null;
            String end = null;
            int lastCp = 0;
            int prefixLen = 0;
            for (String s : source) {
                if (start != null) { // We have something queued up
                    if (s.regionMatches(0, start, 0, prefixLen)) {
                        int currentCp = s.codePointAt(prefixLen);
                        if (currentCp == 1 + lastCp && s.length() == prefixLen + Character.charCount(currentCp)) {
                            end = s;
                            lastCp = currentCp;
                            continue;
                        }
                    }
                    // We failed to find continuation. Add what we have and restart
                    adder.add(start, end == null ? null
                        : !shorterPairs ? end
                            : end.substring(prefixLen, end.length()));
                }
                // new possible range
                start = s;
                end = null;
                lastCp = s.codePointBefore(s.length());
                prefixLen = s.length() - Character.charCount(lastCp);
            }
            adder.add(start, end == null ? null
                : !shorterPairs ? end
                    : end.substring(prefixLen, end.length()));
        } else {
            // not a fast algorithm, but ok for now
            // TODO rewire to use the first (slower) algorithm to generate the ranges, then compact them from there.
            // first sort by lengths
            Relation<Integer, Ranges> lengthToArrays = Relation.of(new TreeMap<Integer, Set<Ranges>>(), TreeSet.class);
            for (String s : source) {
                Ranges item = new Ranges(s);
                lengthToArrays.put(item.size(), item);
            }
            // then compact items of each length and emit compacted sets
            for (Entry<Integer, Set<Ranges>> entry : lengthToArrays.keyValuesSet()) {
                LinkedList<Ranges> compacted = compact(entry.getKey(), entry.getValue());
                for (Ranges ranges : compacted) {
                    adder.add(ranges.start(), ranges.end(shorterPairs));
                }
            }
        }
    }

    /**
     * Faster but not as good compaction. Only looks at final codepoint.
     * @param source
     * @param adder
     * @param shorterPairs
     */
    public static void compact(Set<String> source, Adder adder, boolean shorterPairs) {
        compact(source, adder, shorterPairs, false);
    }

    private static LinkedList<Ranges> compact(int size, Set<Ranges> inputRanges) {
        LinkedList<Ranges> ranges = new LinkedList<>(inputRanges);
        for (int i = size - 1; i >= 0; --i) {
            Ranges last = null;
            for (Iterator<Ranges> it = ranges.iterator(); it.hasNext();) {
                Ranges item = it.next();
                if (last == null) {
                    last = item;
                } else if (last.merge(i, item)) {
                    it.remove();
                } else {
                    last = item; // go to next
                }
            }
        }
        ;
        return ranges;
    }

    static final class Range implements Comparable<Range> {
        int min;
        int max;

        public Range(int min, int max) {
            this.min = min;
            this.max = max;
        }

        @Override
        public boolean equals(Object obj) {
            return compareTo((Range) obj) == 0;
        }

        @Override
        public int compareTo(Range that) {
            int diff = min - that.min;
            if (diff != 0) {
                return diff;
            }
            return max - that.max;
        }

        @Override
        public int hashCode() {
            return min * 37 + max;
        }

        @Override
        public String toString() {
            StringBuilder result = new StringBuilder().appendCodePoint(min);
            return min == max ? result.toString() : result.append('~').appendCodePoint(max).toString();
        }
    }

    static final class Ranges implements Comparable<Ranges> {
        private final Range[] ranges;

        public Ranges(String s) {
            int[] array = CharSequences.codePoints(s);
            ranges = new Range[array.length];
            for (int i = 0; i < array.length; ++i) {
                ranges[i] = new Range(array[i], array[i]);
            }
        }

        public boolean merge(int pivot, Ranges other) {
//            if (this.toString().equals("afz")) {
//                int debug = 0;
//            }
            // we will merge items if the pivot is adjacent, and all other ranges are equal
            for (int i = ranges.length - 1; i >= 0; --i) {
                if (i == pivot) {
                    if (ranges[i].max != other.ranges[i].min - 1) { // not adjacent
                        return false;
                    }
                } else {
                    if (!ranges[i].equals(other.ranges[i])) {
                        return false;
                    }
                }
            }
            if (DEBUG) System.out.print("Merging: " + this + ", " + other);
            ranges[pivot].max = other.ranges[pivot].max;
            if (DEBUG) System.out.println(" => " + this);
            return true;
        }

        public String start() {
            StringBuilder result = new StringBuilder();
            for (int i = 0; i < ranges.length; ++i) {
                result.appendCodePoint(ranges[i].min);
            }
            return result.toString();
        }

        public String end(boolean mostCompact) {
            int firstDiff = firstDifference();
            if (firstDiff == ranges.length) {
                return null;
            }
            StringBuilder result = new StringBuilder();
            for (int i = mostCompact ? firstDiff : 0; i < ranges.length; ++i) {
                result.appendCodePoint(ranges[i].max);
            }
            return result.toString();
        }

        public int firstDifference() {
            for (int i = 0; i < ranges.length; ++i) {
                if (ranges[i].min != ranges[i].max) {
                    return i;
                }
            }
            return ranges.length;
        }

        public Integer size() {
            return ranges.length;
        }

        @Override
        public int compareTo(Ranges other) {
            int diff = ranges.length - other.ranges.length;
            if (diff != 0) {
                return diff;
            }
            for (int i = 0; i < ranges.length; ++i) {
                diff = ranges[i].compareTo(other.ranges[i]);
                if (diff != 0) {
                    return diff;
                }
            }
            return 0;
        }

        @Override
        public String toString() {
            String start = start();
            String end = end(false);
            return end == null ? start : start + "~" + end;
        }
    }

    static Collection<String> expand(String start, String end, Collection<String> output) {
        int[] startCps = CharSequences.codePoints(start);
        int[] endCps = CharSequences.codePoints(end);
        int startOffset = startCps.length - endCps.length;

        if (startOffset < 0) {
            throw new ICUException("Must have start-length ≥ end-length");
        } else if (endCps.length == 0) {
            throw new ICUException("Must have end-length > 0");
        }

        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < startOffset; ++i) {
            builder.appendCodePoint(startCps[i]);
        }
        add(0, startOffset, startCps, endCps, builder, output);
        return output;
    }

    private static void add(int endIndex, int startOffset, int[] starts, int[] ends, StringBuilder builder, Collection<String> output) {
        int start = starts[endIndex + startOffset];
        int end = ends[endIndex];
        if (start > end) {
            throw new ICUException("Each two corresponding characters ...x... and ...y... must have x ≤ y.");
        }
        boolean last = endIndex == ends.length - 1;
        int startLen = builder.length();
        for (int i = start; i <= end; ++i) {
            builder.appendCodePoint(i);
            if (last) {
                output.add(builder.toString());
            } else {
                add(endIndex + 1, startOffset, starts, ends, builder, output);
            }
            builder.setLength(startLen);
        }
    }
}