UnicodeSetStringSpan.java

/*
 * Copyright (c) 2015, 2020, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 ******************************************************************************
 *
 *   Copyright (C) 2009-2014, International Business Machines
 *   Corporation and others.  All Rights Reserved.
 *
 ******************************************************************************
 */

package jdk.internal.icu.impl;

import java.util.ArrayList;

import jdk.internal.icu.text.UTF16;
import jdk.internal.icu.text.UnicodeSet;
import jdk.internal.icu.text.UnicodeSet.SpanCondition;
import jdk.internal.icu.util.OutputInt;

/*
 * Implement span() etc. for a set with strings.
 * Avoid recursion because of its exponential complexity.
 * Instead, try multiple paths at once and track them with an IndexList.
 */
public class UnicodeSetStringSpan {

    /*
     * Which span() variant will be used? The object is either built for one variant and used once,
     * or built for all and may be used many times.
     */
    public static final int WITH_COUNT    = 0x40;  // spanAndCount() may be called
    public static final int FWD           = 0x20;
    public static final int BACK          = 0x10;
    // public static final int UTF16      = 8;
    public static final int CONTAINED     = 2;
    public static final int NOT_CONTAINED = 1;

    public static final int ALL = 0x7f;

    public static final int FWD_UTF16_CONTAINED      = FWD  | /* UTF16 | */    CONTAINED;
    public static final int FWD_UTF16_NOT_CONTAINED  = FWD  | /* UTF16 | */NOT_CONTAINED;
    public static final int BACK_UTF16_CONTAINED     = BACK | /* UTF16 | */    CONTAINED;
    public static final int BACK_UTF16_NOT_CONTAINED = BACK | /* UTF16 | */NOT_CONTAINED;

    /**
     * Special spanLength short values. (since Java has not unsigned byte type)
     * All code points in the string are contained in the parent set.
     */
    static final short ALL_CP_CONTAINED = 0xff;

    /** The spanLength is >=0xfe. */
    static final short LONG_SPAN = ALL_CP_CONTAINED - 1;

    /** Set for span(). Same as parent but without strings. */
    private UnicodeSet spanSet;

    /**
     * Set for span(not contained).
     * Same as spanSet, plus characters that start or end strings.
     */
    private UnicodeSet spanNotSet;

    /** The strings of the parent set. */
    private ArrayList<String> strings;

    /** The lengths of span(), spanBack() etc. for each string. */
    private short[] spanLengths;

    /** Maximum lengths of relevant strings. */
    private int maxLength16;

    /** Are there strings that are not fully contained in the code point set? */
    private boolean someRelevant;

    /** Set up for all variants of span()? */
    private boolean all;

    /** Span helper */
    private OffsetList offsets;

    /**
     * Constructs for all variants of span(), or only for any one variant.
     * Initializes as little as possible, for single use.
     */
    public UnicodeSetStringSpan(final UnicodeSet set, final ArrayList<String> setStrings, int which) {
        spanSet = new UnicodeSet(0, 0x10ffff);
        // TODO: With Java 6, just take the parent set's strings as is,
        // as a NavigableSet<String>, rather than as an ArrayList copy of the set of strings.
        // Then iterate via the first() and higher() methods.
        // (We do not want to create multiple Iterator objects in each span().)
        // See ICU ticket #7454.
        strings = setStrings;
        all = (which == ALL);
        spanSet.retainAll(set);
        if (0 != (which & NOT_CONTAINED)) {
            // Default to the same sets.
            // addToSpanNotSet() will create a separate set if necessary.
            spanNotSet = spanSet;
        }
        offsets = new OffsetList();

        // Determine if the strings even need to be taken into account at all for span() etc.
        // If any string is relevant, then all strings need to be used for
        // span(longest match) but only the relevant ones for span(while contained).
        // TODO: Possible optimization: Distinguish CONTAINED vs. LONGEST_MATCH
        // and do not store UTF-8 strings if !thisRelevant and CONTAINED.
        // (Only store irrelevant UTF-8 strings for LONGEST_MATCH where they are relevant after all.)
        // Also count the lengths of the UTF-8 versions of the strings for memory allocation.
        int stringsLength = strings.size();

        int i, spanLength;
        someRelevant = false;
        for (i = 0; i < stringsLength; ++i) {
            String string = strings.get(i);
            int length16 = string.length();
            spanLength = spanSet.span(string, SpanCondition.CONTAINED);
            if (spanLength < length16) { // Relevant string.
                someRelevant = true;
            }
            if (/* (0 != (which & UTF16)) && */ length16 > maxLength16) {
                maxLength16 = length16;
            }
        }
        if (!someRelevant && (which & WITH_COUNT) == 0) {
            return;
        }

        // Freeze after checking for the need to use strings at all because freezing
        // a set takes some time and memory which are wasted if there are no relevant strings.
        if (all) {
            spanSet.freeze();
        }

        int spanBackLengthsOffset;

        // Allocate a block of meta data.
        int allocSize;
        if (all) {
            // 2 sets of span lengths
            allocSize = stringsLength * (2);
        } else {
            allocSize = stringsLength; // One set of span lengths.
        }
        spanLengths = new short[allocSize];

        if (all) {
            // Store span lengths for all span() variants.
            spanBackLengthsOffset = stringsLength;
        } else {
            // Store span lengths for only one span() variant.
            spanBackLengthsOffset = 0;
        }

        // Set the meta data and spanNotSet and write the UTF-8 strings.

        for (i = 0; i < stringsLength; ++i) {
            String string = strings.get(i);
            int length16 = string.length();
            spanLength = spanSet.span(string, SpanCondition.CONTAINED);
            if (spanLength < length16) { // Relevant string.
                if (true /* 0 != (which & UTF16) */) {
                    if (0 != (which & CONTAINED)) {
                        if (0 != (which & FWD)) {
                            spanLengths[i] = makeSpanLengthByte(spanLength);
                        }
                        if (0 != (which & BACK)) {
                            spanLength = length16
                                    - spanSet.spanBack(string, length16, SpanCondition.CONTAINED);
                            spanLengths[spanBackLengthsOffset + i] = makeSpanLengthByte(spanLength);
                        }
                    } else /* not CONTAINED, not all, but NOT_CONTAINED */{
                        spanLengths[i] = spanLengths[spanBackLengthsOffset + i] = 0; // Only store a relevant/irrelevant
                                                                                     // flag.
                    }
                }
                if (0 != (which & NOT_CONTAINED)) {
                    // Add string start and end code points to the spanNotSet so that
                    // a span(while not contained) stops before any string.
                    int c;
                    if (0 != (which & FWD)) {
                        c = string.codePointAt(0);
                        addToSpanNotSet(c);
                    }
                    if (0 != (which & BACK)) {
                        c = string.codePointBefore(length16);
                        addToSpanNotSet(c);
                    }
                }
            } else { // Irrelevant string.
                if (all) {
                    spanLengths[i] = spanLengths[spanBackLengthsOffset + i] = ALL_CP_CONTAINED;
                } else {
                    // All spanXYZLengths pointers contain the same address.
                    spanLengths[i] = ALL_CP_CONTAINED;
                }
            }
        }

        // Finish.
        if (all) {
            spanNotSet.freeze();
        }
    }

    /**
     * Do the strings need to be checked in span() etc.?
     *
     * @return true if strings need to be checked (call span() here),
     *         false if not (use a BMPSet for best performance).
     */
    public boolean needsStringSpanUTF16() {
        return someRelevant;
    }

    /** For fast UnicodeSet::contains(c). */
    public boolean contains(int c) {
        return spanSet.contains(c);
    }

    /**
     * Adds a starting or ending string character to the spanNotSet
     * so that a character span ends before any string.
     */
    private void addToSpanNotSet(int c) {
        if (spanNotSet == null || spanNotSet == spanSet) {
            if (spanSet.contains(c)) {
                return; // Nothing to do.
            }
            spanNotSet = spanSet.cloneAsThawed();
        }
        spanNotSet.add(c);
    }

    /*
     * Note: In span() when spanLength==0
     * (after a string match, or at the beginning after an empty code point span)
     * and in spanNot() and spanNotUTF8(),
     * string matching could use a binary search because all string matches are done
     * from the same start index.
     *
     * For UTF-8, this would require a comparison function that returns UTF-16 order.
     *
     * This optimization should not be necessary for normal UnicodeSets because most sets have no strings, and most sets
     * with strings have very few very short strings. For cases with many strings, it might be better to use a different
     * API and implementation with a DFA (state machine).
     */

    /*
     * Algorithm for span(SpanCondition.CONTAINED)
     *
     * Theoretical algorithm:
     * - Iterate through the string, and at each code point boundary:
     *   + If the code point there is in the set, then remember to continue after it.
     *   + If a set string matches at the current position, then remember to continue after it.
     *   + Either recursively span for each code point or string match, or recursively span
     *     for all but the shortest one and iteratively continue the span with the shortest local match.
     *   + Remember the longest recursive span (the farthest end point).
     *   + If there is no match at the current position,
     *     neither for the code point there nor for any set string,
     *     then stop and return the longest recursive span length.
     *
     * Optimized implementation:
     *
     * (We assume that most sets will have very few very short strings.
     * A span using a string-less set is extremely fast.)
     *
     * Create and cache a spanSet which contains all of the single code points of the original set
     * but none of its strings.
     *
     * - Start with spanLength=spanSet.span(SpanCondition.CONTAINED).
     * - Loop:
     *   + Try to match each set string at the end of the spanLength.
     *     ~ Set strings that start with set-contained code points
     *       must be matched with a partial overlap
     *       because the recursive algorithm would have tried to match them at every position.
     *     ~ Set strings that entirely consist of set-contained code points
     *       are irrelevant for span(SpanCondition.CONTAINED)
     *       because the recursive algorithm would continue after them anyway and
     *       find the longest recursive match from their end.
     *     ~ Rather than recursing, note each end point of a set string match.
     *   + If no set string matched after spanSet.span(),
     *     then return with where the spanSet.span() ended.
     *   + If at least one set string matched after spanSet.span(),
     *     then pop the shortest string match end point and continue the loop,
     *     trying to match all set strings from there.
     *   + If at least one more set string matched after a previous string match, then test if the
     *     code point after the previous string match is also contained in the set.
     *     Continue the loop with the shortest end point of
     *     either this code point or a matching set string.
     *   + If no more set string matched after a previous string match,
     *     then try another spanLength=spanSet.span(SpanCondition.CONTAINED).
     *     Stop if spanLength==0, otherwise continue the loop.
     *
     * By noting each end point of a set string match, the function visits each string position at most once and
     * finishes in linear time.
     *
     * The recursive algorithm may visit the same string position many times
     * if multiple paths lead to it and finishes in exponential time.
     */

    /*
     * Algorithm for span(SIMPLE)
     *
     * Theoretical algorithm:
     * - Iterate through the string, and at each code point boundary:
     *   + If the code point there is in the set, then remember to continue after it.
     *   + If a set string matches at the current position, then remember to continue after it.
     *   + Continue from the farthest match position and ignore all others.
     *   + If there is no match at the current position, then stop and return the current position.
     *
     * Optimized implementation:
     *
     * (Same assumption and spanSet as above.)
     *
     * - Start with spanLength=spanSet.span(SpanCondition.CONTAINED).
     * - Loop:
     *   + Try to match each set string at the end of the spanLength.
     *     ~ Set strings that start with set-contained code points
     *       must be matched with a partial overlap
     *       because the standard algorithm would have tried to match them earlier.
     *     ~ Set strings that entirely consist of set-contained code points
     *       must be matched with a full overlap because the longest-match algorithm
     *       would hide set string matches that end earlier.
     *       Such set strings need not be matched earlier inside the code point span
     *       because the standard algorithm would then have
     *       continued after the set string match anyway.
     *     ~ Remember the longest set string match (farthest end point)
     *       from the earliest starting point.
     *   + If no set string matched after spanSet.span(),
     *     then return with where the spanSet.span() ended.
     *   + If at least one set string matched,
     *     then continue the loop after the longest match from the earliest position.
     *   + If no more set string matched after a previous string match,
     *     then try another spanLength=spanSet.span(SpanCondition.CONTAINED).
     *     Stop if spanLength==0, otherwise continue the loop.
     */
    /**
     * Spans a string.
     *
     * @param s The string to be spanned
     * @param start The start index that the span begins
     * @param spanCondition The span condition
     * @return the limit (exclusive end) of the span
     */
    public int span(CharSequence s, int start, SpanCondition spanCondition) {
        if (spanCondition == SpanCondition.NOT_CONTAINED) {
            return spanNot(s, start, null);
        }
        int spanLimit = spanSet.span(s, start, SpanCondition.CONTAINED);
        if (spanLimit == s.length()) {
            return spanLimit;
        }
        return spanWithStrings(s, start, spanLimit, spanCondition);
    }

    /**
     * Synchronized method for complicated spans using the offsets.
     * Avoids synchronization for simple cases.
     *
     * @param spanLimit = spanSet.span(s, start, CONTAINED)
     */
    private synchronized int spanWithStrings(CharSequence s, int start, int spanLimit,
            SpanCondition spanCondition) {
        // Consider strings; they may overlap with the span.
        int initSize = 0;
        if (spanCondition == SpanCondition.CONTAINED) {
            // Use offset list to try all possibilities.
            initSize = maxLength16;
        }
        offsets.setMaxLength(initSize);
        int length = s.length();
        int pos = spanLimit, rest = length - spanLimit;
        int spanLength = spanLimit - start;
        int i, stringsLength = strings.size();
        for (;;) {
            if (spanCondition == SpanCondition.CONTAINED) {
                for (i = 0; i < stringsLength; ++i) {
                    int overlap = spanLengths[i];
                    if (overlap == ALL_CP_CONTAINED) {
                        continue; // Irrelevant string.
                    }
                    String string = strings.get(i);

                    int length16 = string.length();

                    // Try to match this string at pos-overlap..pos.
                    if (overlap >= LONG_SPAN) {
                        overlap = length16;
                        // While contained: No point matching fully inside the code point span.
                        overlap = string.offsetByCodePoints(overlap, -1); // Length of the string minus the last code
                                                                          // point.
                    }
                    if (overlap > spanLength) {
                        overlap = spanLength;
                    }
                    int inc = length16 - overlap; // Keep overlap+inc==length16.
                    for (;;) {
                        if (inc > rest) {
                            break;
                        }
                        // Try to match if the increment is not listed already.
                        if (!offsets.containsOffset(inc) && matches16CPB(s, pos - overlap, length, string, length16)) {
                            if (inc == rest) {
                                return length; // Reached the end of the string.
                            }
                            offsets.addOffset(inc);
                        }
                        if (overlap == 0) {
                            break;
                        }
                        --overlap;
                        ++inc;
                    }
                }
            } else /* SIMPLE */{
                int maxInc = 0, maxOverlap = 0;
                for (i = 0; i < stringsLength; ++i) {
                    int overlap = spanLengths[i];
                    // For longest match, we do need to try to match even an all-contained string
                    // to find the match from the earliest start.

                    String string = strings.get(i);

                    int length16 = string.length();

                    // Try to match this string at pos-overlap..pos.
                    if (overlap >= LONG_SPAN) {
                        overlap = length16;
                        // Longest match: Need to match fully inside the code point span
                        // to find the match from the earliest start.
                    }
                    if (overlap > spanLength) {
                        overlap = spanLength;
                    }
                    int inc = length16 - overlap; // Keep overlap+inc==length16.
                    for (;;) {
                        if (inc > rest || overlap < maxOverlap) {
                            break;
                        }
                        // Try to match if the string is longer or starts earlier.
                        if ((overlap > maxOverlap || /* redundant overlap==maxOverlap && */inc > maxInc)
                                && matches16CPB(s, pos - overlap, length, string, length16)) {
                            maxInc = inc; // Longest match from earliest start.
                            maxOverlap = overlap;
                            break;
                        }
                        --overlap;
                        ++inc;
                    }
                }

                if (maxInc != 0 || maxOverlap != 0) {
                    // Longest-match algorithm, and there was a string match.
                    // Simply continue after it.
                    pos += maxInc;
                    rest -= maxInc;
                    if (rest == 0) {
                        return length; // Reached the end of the string.
                    }
                    spanLength = 0; // Match strings from after a string match.
                    continue;
                }
            }
            // Finished trying to match all strings at pos.

            if (spanLength != 0 || pos == 0) {
                // The position is after an unlimited code point span (spanLength!=0),
                // not after a string match.
                // The only position where spanLength==0 after a span is pos==0.
                // Otherwise, an unlimited code point span is only tried again when no
                // strings match, and if such a non-initial span fails we stop.
                if (offsets.isEmpty()) {
                    return pos; // No strings matched after a span.
                }
                // Match strings from after the next string match.
            } else {
                // The position is after a string match (or a single code point).
                if (offsets.isEmpty()) {
                    // No more strings matched after a previous string match.
                    // Try another code point span from after the last string match.
                    spanLimit = spanSet.span(s, pos, SpanCondition.CONTAINED);
                    spanLength = spanLimit - pos;
                    if (spanLength == rest || // Reached the end of the string, or
                            spanLength == 0 // neither strings nor span progressed.
                    ) {
                        return spanLimit;
                    }
                    pos += spanLength;
                    rest -= spanLength;
                    continue; // spanLength>0: Match strings from after a span.
                } else {
                    // Try to match only one code point from after a string match if some
                    // string matched beyond it, so that we try all possible positions
                    // and don't overshoot.
                    spanLength = spanOne(spanSet, s, pos, rest);
                    if (spanLength > 0) {
                        if (spanLength == rest) {
                            return length; // Reached the end of the string.
                        }
                        // Match strings after this code point.
                        // There cannot be any increments below it because UnicodeSet strings
                        // contain multiple code points.
                        pos += spanLength;
                        rest -= spanLength;
                        offsets.shift(spanLength);
                        spanLength = 0;
                        continue; // Match strings from after a single code point.
                    }
                    // Match strings from after the next string match.
                }
            }
            int minOffset = offsets.popMinimum(null);
            pos += minOffset;
            rest -= minOffset;
            spanLength = 0; // Match strings from after a string match.
        }
    }

    /**
     * Spans a string and counts the smallest number of set elements on any path across the span.
     *
     * <p>For proper counting, we cannot ignore strings that are fully contained in code point spans.
     *
     * <p>If the set does not have any fully-contained strings, then we could optimize this
     * like span(), but such sets are likely rare, and this is at least still linear.
     *
     * @param s The string to be spanned
     * @param start The start index that the span begins
     * @param spanCondition The span condition
     * @param outCount The count
     * @return the limit (exclusive end) of the span
     */
    public int spanAndCount(CharSequence s, int start, SpanCondition spanCondition,
            OutputInt outCount) {
        if (spanCondition == SpanCondition.NOT_CONTAINED) {
            return spanNot(s, start, outCount);
        }
        // Consider strings; they may overlap with the span,
        // and they may result in a smaller count that with just code points.
        if (spanCondition == SpanCondition.CONTAINED) {
            return spanContainedAndCount(s, start, outCount);
        }
        // SIMPLE (not synchronized, does not use offsets)
        int stringsLength = strings.size();
        int length = s.length();
        int pos = start;
        int rest = length - start;
        int count = 0;
        while (rest != 0) {
            // Try to match the next code point.
            int cpLength = spanOne(spanSet, s, pos, rest);
            int maxInc = (cpLength > 0) ? cpLength : 0;
            // Try to match all of the strings.
            for (int i = 0; i < stringsLength; ++i) {
                String string = strings.get(i);
                int length16 = string.length();
                if (maxInc < length16 && length16 <= rest &&
                        matches16CPB(s, pos, length, string, length16)) {
                    maxInc = length16;
                }
            }
            // We are done if there is no match beyond pos.
            if (maxInc == 0) {
                outCount.value = count;
                return pos;
            }
            // Continue from the longest match.
            ++count;
            pos += maxInc;
            rest -= maxInc;
        }
        outCount.value = count;
        return pos;
    }

    private synchronized int spanContainedAndCount(CharSequence s, int start, OutputInt outCount) {
        // Use offset list to try all possibilities.
        offsets.setMaxLength(maxLength16);
        int stringsLength = strings.size();
        int length = s.length();
        int pos = start;
        int rest = length - start;
        int count = 0;
        while (rest != 0) {
            // Try to match the next code point.
            int cpLength = spanOne(spanSet, s, pos, rest);
            if (cpLength > 0) {
                offsets.addOffsetAndCount(cpLength, count + 1);
            }
            // Try to match all of the strings.
            for (int i = 0; i < stringsLength; ++i) {
                String string = strings.get(i);
                int length16 = string.length();
                // Note: If the strings were sorted by length, then we could also
                // avoid trying to match if there is already a match of the same length.
                if (length16 <= rest && !offsets.hasCountAtOffset(length16, count + 1) &&
                        matches16CPB(s, pos, length, string, length16)) {
                    offsets.addOffsetAndCount(length16, count + 1);
                }
            }
            // We are done if there is no match beyond pos.
            if (offsets.isEmpty()) {
                outCount.value = count;
                return pos;
            }
            // Continue from the nearest match.
            int minOffset = offsets.popMinimum(outCount);
            count = outCount.value;
            pos += minOffset;
            rest -= minOffset;
        }
        outCount.value = count;
        return pos;
    }

    /**
     * Span a string backwards.
     *
     * @param s The string to be spanned
     * @param spanCondition The span condition
     * @return The string index which starts the span (i.e. inclusive).
     */
    public synchronized int spanBack(CharSequence s, int length, SpanCondition spanCondition) {
        if (spanCondition == SpanCondition.NOT_CONTAINED) {
            return spanNotBack(s, length);
        }
        int pos = spanSet.spanBack(s, length, SpanCondition.CONTAINED);
        if (pos == 0) {
            return 0;
        }
        int spanLength = length - pos;

        // Consider strings; they may overlap with the span.
        int initSize = 0;
        if (spanCondition == SpanCondition.CONTAINED) {
            // Use offset list to try all possibilities.
            initSize = maxLength16;
        }
        offsets.setMaxLength(initSize);
        int i, stringsLength = strings.size();
        int spanBackLengthsOffset = 0;
        if (all) {
            spanBackLengthsOffset = stringsLength;
        }
        for (;;) {
            if (spanCondition == SpanCondition.CONTAINED) {
                for (i = 0; i < stringsLength; ++i) {
                    int overlap = spanLengths[spanBackLengthsOffset + i];
                    if (overlap == ALL_CP_CONTAINED) {
                        continue; // Irrelevant string.
                    }
                    String string = strings.get(i);

                    int length16 = string.length();

                    // Try to match this string at pos-(length16-overlap)..pos-length16.
                    if (overlap >= LONG_SPAN) {
                        overlap = length16;
                        // While contained: No point matching fully inside the code point span.
                        int len1 = 0;
                        len1 = string.offsetByCodePoints(0, 1);
                        overlap -= len1; // Length of the string minus the first code point.
                    }
                    if (overlap > spanLength) {
                        overlap = spanLength;
                    }
                    int dec = length16 - overlap; // Keep dec+overlap==length16.
                    for (;;) {
                        if (dec > pos) {
                            break;
                        }
                        // Try to match if the decrement is not listed already.
                        if (!offsets.containsOffset(dec) && matches16CPB(s, pos - dec, length, string, length16)) {
                            if (dec == pos) {
                                return 0; // Reached the start of the string.
                            }
                            offsets.addOffset(dec);
                        }
                        if (overlap == 0) {
                            break;
                        }
                        --overlap;
                        ++dec;
                    }
                }
            } else /* SIMPLE */{
                int maxDec = 0, maxOverlap = 0;
                for (i = 0; i < stringsLength; ++i) {
                    int overlap = spanLengths[spanBackLengthsOffset + i];
                    // For longest match, we do need to try to match even an all-contained string
                    // to find the match from the latest end.

                    String string = strings.get(i);

                    int length16 = string.length();

                    // Try to match this string at pos-(length16-overlap)..pos-length16.
                    if (overlap >= LONG_SPAN) {
                        overlap = length16;
                        // Longest match: Need to match fully inside the code point span
                        // to find the match from the latest end.
                    }
                    if (overlap > spanLength) {
                      overlap = spanLength;
                    }
                    int dec = length16 - overlap; // Keep dec+overlap==length16.
                    for (;;) {
                        if (dec > pos || overlap < maxOverlap) {
                            break;
                        }
                        // Try to match if the string is longer or ends later.
                        if ((overlap > maxOverlap || /* redundant overlap==maxOverlap && */dec > maxDec)
                                && matches16CPB(s, pos - dec, length, string, length16)) {
                            maxDec = dec; // Longest match from latest end.
                            maxOverlap = overlap;
                            break;
                        }
                        --overlap;
                        ++dec;
                    }
                }

                if (maxDec != 0 || maxOverlap != 0) {
                    // Longest-match algorithm, and there was a string match.
                    // Simply continue before it.
                    pos -= maxDec;
                    if (pos == 0) {
                        return 0; // Reached the start of the string.
                    }
                    spanLength = 0; // Match strings from before a string match.
                    continue;
                }
            }
            // Finished trying to match all strings at pos.

            if (spanLength != 0 || pos == length) {
                // The position is before an unlimited code point span (spanLength!=0),
                // not before a string match.
                // The only position where spanLength==0 before a span is pos==length.
                // Otherwise, an unlimited code point span is only tried again when no
                // strings match, and if such a non-initial span fails we stop.
                if (offsets.isEmpty()) {
                    return pos; // No strings matched before a span.
                }
                // Match strings from before the next string match.
            } else {
                // The position is before a string match (or a single code point).
                if (offsets.isEmpty()) {
                    // No more strings matched before a previous string match.
                    // Try another code point span from before the last string match.
                    int oldPos = pos;
                    pos = spanSet.spanBack(s, oldPos, SpanCondition.CONTAINED);
                    spanLength = oldPos - pos;
                    if (pos == 0 || // Reached the start of the string, or
                            spanLength == 0 // neither strings nor span progressed.
                    ) {
                        return pos;
                    }
                    continue; // spanLength>0: Match strings from before a span.
                } else {
                    // Try to match only one code point from before a string match if some
                    // string matched beyond it, so that we try all possible positions
                    // and don't overshoot.
                    spanLength = spanOneBack(spanSet, s, pos);
                    if (spanLength > 0) {
                        if (spanLength == pos) {
                            return 0; // Reached the start of the string.
                        }
                        // Match strings before this code point.
                        // There cannot be any decrements below it because UnicodeSet strings
                        // contain multiple code points.
                        pos -= spanLength;
                        offsets.shift(spanLength);
                        spanLength = 0;
                        continue; // Match strings from before a single code point.
                    }
                    // Match strings from before the next string match.
                }
            }
            pos -= offsets.popMinimum(null);
            spanLength = 0; // Match strings from before a string match.
        }
    }

    /**
     * Algorithm for spanNot()==span(SpanCondition.NOT_CONTAINED)
     *
     * Theoretical algorithm:
     * - Iterate through the string, and at each code point boundary:
     *   + If the code point there is in the set, then return with the current position.
     *   + If a set string matches at the current position, then return with the current position.
     *
     * Optimized implementation:
     *
     * (Same assumption as for span() above.)
     *
     * Create and cache a spanNotSet which contains
     * all of the single code points of the original set but none of its strings.
     * For each set string add its initial code point to the spanNotSet.
     * (Also add its final code point for spanNotBack().)
     *
     * - Loop:
     *   + Do spanLength=spanNotSet.span(SpanCondition.NOT_CONTAINED).
     *   + If the current code point is in the original set, then return the current position.
     *   + If any set string matches at the current position, then return the current position.
     *   + If there is no match at the current position, neither for the code point
     *     there nor for any set string, then skip this code point and continue the loop.
     *     This happens for set-string-initial code points that were added to spanNotSet
     *     when there is not actually a match for such a set string.
     *
     * @param s The string to be spanned
     * @param start The start index that the span begins
     * @param outCount If not null: Receives the number of code points across the span.
     * @return the limit (exclusive end) of the span
     */
    private int spanNot(CharSequence s, int start, OutputInt outCount) {
        int length = s.length();
        int pos = start, rest = length - start;
        int stringsLength = strings.size();
        int count = 0;
        do {
            // Span until we find a code point from the set,
            // or a code point that starts or ends some string.
            int spanLimit;
            if (outCount == null) {
                spanLimit = spanNotSet.span(s, pos, SpanCondition.NOT_CONTAINED);
            } else {
                spanLimit = spanNotSet.spanAndCount(s, pos, SpanCondition.NOT_CONTAINED, outCount);
                outCount.value = count = count + outCount.value;
            }
            if (spanLimit == length) {
                return length; // Reached the end of the string.
            }
            pos = spanLimit;
            rest = length - spanLimit;

            // Check whether the current code point is in the original set,
            // without the string starts and ends.
            int cpLength = spanOne(spanSet, s, pos, rest);
            if (cpLength > 0) {
                return pos; // There is a set element at pos.
            }

            // Try to match the strings at pos.
            for (int i = 0; i < stringsLength; ++i) {
                if (spanLengths[i] == ALL_CP_CONTAINED) {
                    continue; // Irrelevant string.
                }
                String string = strings.get(i);

                int length16 = string.length();
                if (length16 <= rest && matches16CPB(s, pos, length, string, length16)) {
                    return pos; // There is a set element at pos.
                }
            }

            // The span(while not contained) ended on a string start/end which is
            // not in the original set. Skip this code point and continue.
            // cpLength<0
            pos -= cpLength;
            rest += cpLength;
            ++count;
        } while (rest != 0);
        if (outCount != null) {
            outCount.value = count;
        }
        return length; // Reached the end of the string.
    }

    private int spanNotBack(CharSequence s, int length) {
        int pos = length;
        int i, stringsLength = strings.size();
        do {
            // Span until we find a code point from the set,
            // or a code point that starts or ends some string.
            pos = spanNotSet.spanBack(s, pos, SpanCondition.NOT_CONTAINED);
            if (pos == 0) {
                return 0; // Reached the start of the string.
            }

            // Check whether the current code point is in the original set,
            // without the string starts and ends.
            int cpLength = spanOneBack(spanSet, s, pos);
            if (cpLength > 0) {
                return pos; // There is a set element at pos.
            }

            // Try to match the strings at pos.
            for (i = 0; i < stringsLength; ++i) {
                // Use spanLengths rather than a spanLengths pointer because
                // it is easier and we only need to know whether the string is irrelevant
                // which is the same in either array.
                if (spanLengths[i] == ALL_CP_CONTAINED) {
                    continue; // Irrelevant string.
                }
                String string = strings.get(i);

                int length16 = string.length();
                if (length16 <= pos && matches16CPB(s, pos - length16, length, string, length16)) {
                    return pos; // There is a set element at pos.
                }
            }

            // The span(while not contained) ended on a string start/end which is
            // not in the original set. Skip this code point and continue.
            // cpLength<0
            pos += cpLength;
        } while (pos != 0);
        return 0; // Reached the start of the string.
    }

    static short makeSpanLengthByte(int spanLength) {
        // 0xfe==UnicodeSetStringSpan::LONG_SPAN
        return spanLength < LONG_SPAN ? (short) spanLength : LONG_SPAN;
    }

    // Compare strings without any argument checks. Requires length>0.
    private static boolean matches16(CharSequence s, int start, final String t, int length) {
        int end = start + length;
        while (length-- > 0) {
            if (s.charAt(--end) != t.charAt(length)) {
                return false;
            }
        }
        return true;
    }

    /**
     * Compare 16-bit Unicode strings (which may be malformed UTF-16)
     * at code point boundaries.
     * That is, each edge of a match must not be in the middle of a surrogate pair.
     * @param s       The string to match in.
     * @param start   The start index of s.
     * @param limit   The limit of the subsequence of s being spanned.
     * @param t       The substring to be matched in s.
     * @param tlength The length of t.
     */
    static boolean matches16CPB(CharSequence s, int start, int limit, final String t, int tlength) {
        return matches16(s, start, t, tlength)
                && !(0 < start && Character.isHighSurrogate(s.charAt(start - 1)) &&
                        Character.isLowSurrogate(s.charAt(start)))
                && !((start + tlength) < limit && Character.isHighSurrogate(s.charAt(start + tlength - 1)) &&
                        Character.isLowSurrogate(s.charAt(start + tlength)));
    }

    /**
     * Does the set contain the next code point?
     * If so, return its length; otherwise return its negative length.
     */
    static int spanOne(final UnicodeSet set, CharSequence s, int start, int length) {
        char c = s.charAt(start);
        if (c >= 0xd800 && c <= 0xdbff && length >= 2) {
            char c2 = s.charAt(start + 1);
            if (UTF16.isTrailSurrogate(c2)) {
                int supplementary = UCharacterProperty.getRawSupplementary(c, c2);
                return set.contains(supplementary) ? 2 : -2;
            }
        }
        return set.contains(c) ? 1 : -1;
    }

    static int spanOneBack(final UnicodeSet set, CharSequence s, int length) {
        char c = s.charAt(length - 1);
        if (c >= 0xdc00 && c <= 0xdfff && length >= 2) {
            char c2 = s.charAt(length - 2);
            if (UTF16.isLeadSurrogate(c2)) {
                int supplementary = UCharacterProperty.getRawSupplementary(c2, c);
                return set.contains(supplementary) ? 2 : -2;
            }
        }
        return set.contains(c) ? 1 : -1;
    }

    /**
     * Helper class for UnicodeSetStringSpan.
     *
     * <p>List of offsets from the current position from where to try matching
     * a code point or a string.
     * Stores offsets rather than indexes to simplify the code and use the same list
     * for both increments (in span()) and decrements (in spanBack()).
     *
     * <p>Assumption: The maximum offset is limited, and the offsets that are stored at any one time
     * are relatively dense, that is,
     * there are normally no gaps of hundreds or thousands of offset values.
     *
     * <p>This class optionally also tracks the minimum non-negative count for each position,
     * intended to count the smallest number of elements of any path leading to that position.
     *
     * <p>The implementation uses a circular buffer of count integers,
     * each indicating whether the corresponding offset is in the list,
     * and its path element count.
     * This avoids inserting into a sorted list of offsets (or absolute indexes)
     * and physically moving part of the list.
     *
     * <p>Note: In principle, the caller should setMaxLength() to
     * the maximum of the max string length and U16_LENGTH/U8_LENGTH
     * to account for "long" single code points.
     *
     * <p>Note: An earlier version did not track counts and stored only byte flags.
     * With boolean flags, if maxLength were guaranteed to be no more than 32 or 64,
     * the list could be stored as bit flags in a single integer.
     * Rather than handling a circular buffer with a start list index,
     * the integer would simply be shifted when lower offsets are removed.
     * UnicodeSet does not have a limit on the lengths of strings.
     */
    private static final class OffsetList {
        private int[] list;
        private int length;
        private int start;

        public OffsetList() {
            list = new int[16];  // default size
        }

        public void setMaxLength(int maxLength) {
            if (maxLength > list.length) {
                list = new int[maxLength];
            }
            clear();
        }

        public void clear() {
            for (int i = list.length; i-- > 0;) {
                list[i] = 0;
            }
            start = length = 0;
        }

        public boolean isEmpty() {
            return (length == 0);
        }

        /**
         * Reduces all stored offsets by delta, used when the current position moves by delta.
         * There must not be any offsets lower than delta.
         * If there is an offset equal to delta, it is removed.
         *
         * @param delta [1..maxLength]
         */
        public void shift(int delta) {
            int i = start + delta;
            if (i >= list.length) {
                i -= list.length;
            }
            if (list[i] != 0) {
                list[i] = 0;
                --length;
            }
            start = i;
        }

        /**
         * Adds an offset. The list must not contain it yet.
         * @param offset [1..maxLength]
         */
        public void addOffset(int offset) {
            int i = start + offset;
            if (i >= list.length) {
                i -= list.length;
            }
            assert list[i] == 0;
            list[i] = 1;
            ++length;
        }

        /**
         * Adds an offset and updates its count.
         * The list may already contain the offset.
         * @param offset [1..maxLength]
         */
        public void addOffsetAndCount(int offset, int count) {
            assert count > 0;
            int i = start + offset;
            if (i >= list.length) {
                i -= list.length;
            }
            if (list[i] == 0) {
                list[i] = count;
                ++length;
            } else if (count < list[i]) {
                list[i] = count;
            }
        }

        /**
         * @param offset [1..maxLength]
         */
        public boolean containsOffset(int offset) {
            int i = start + offset;
            if (i >= list.length) {
                i -= list.length;
            }
            return list[i] != 0;
        }

        /**
         * @param offset [1..maxLength]
         */
        public boolean hasCountAtOffset(int offset, int count) {
            int i = start + offset;
            if (i >= list.length) {
                i -= list.length;
            }
            int oldCount = list[i];
            return oldCount != 0 && oldCount <= count;
        }

        /**
         * Finds the lowest stored offset from a non-empty list, removes it,
         * and reduces all other offsets by this minimum.
         * @return min=[1..maxLength]
         */
        public int popMinimum(OutputInt outCount) {
            // Look for the next offset in list[start+1..list.length-1].
            int i = start, result;
            while (++i < list.length) {
                int count = list[i];
                if (count != 0) {
                    list[i] = 0;
                    --length;
                    result = i - start;
                    start = i;
                    if (outCount != null) { outCount.value = count; }
                    return result;
                }
            }
            // i==list.length

            // Wrap around and look for the next offset in list[0..start].
            // Since the list is not empty, there will be one.
            result = list.length - start;
            i = 0;
            int count;
            while ((count = list[i]) == 0) {
                ++i;
            }
            list[i] = 0;
            --length;
            start = i;
            if (outCount != null) { outCount.value = count; }
            return result + i;
        }
    }
}