// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
**********************************************************************
*   Copyright (C) 2001-2015 IBM and others. All rights reserved.
**********************************************************************
*   Date        Name        Description
*  07/02/2001   synwee      Creation.
**********************************************************************
*/

#include "unicode/utypes.h"

#if !UCONFIG_NO_COLLATION && !UCONFIG_NO_BREAK_ITERATION

#include "unicode/usearch.h"
#include "unicode/ustring.h"
#include "unicode/uchar.h"
#include "unicode/utf16.h"
#include "normalizer2impl.h"
#include "usrchimp.h"
#include "cmemory.h"
#include "ucln_in.h"
#include "uassert.h"
#include "ustr_imp.h"

U_NAMESPACE_USE

// internal definition ---------------------------------------------------

#define LAST_BYTE_MASK_          0xFF
#define SECOND_LAST_BYTE_SHIFT_  8
#define SUPPLEMENTARY_MIN_VALUE_ 0x10000

static const Normalizer2Impl *g_nfcImpl = nullptr;

// internal methods -------------------------------------------------

/**
* Fast collation element iterator setOffset.
* This function does not check for bounds.
* @param coleiter collation element iterator
* @param offset to set
*/
static
inline void setColEIterOffset(UCollationElements *elems,
                              int32_t offset,
                              UErrorCode &status)
{
    // Note: Not "fast" any more after the 2013 collation rewrite.
    // We do not want to expose more internals than necessary.
    ucol_setOffset(elems, offset, &status);
}

/**
* Getting the mask for collation strength
* @param strength collation strength
* @return collation element mask
*/
static
inline uint32_t getMask(UCollationStrength strength)
{
    switch (strength)
    {
    case UCOL_PRIMARY:
        return UCOL_PRIMARYORDERMASK;
    case UCOL_SECONDARY:
        return UCOL_SECONDARYORDERMASK | UCOL_PRIMARYORDERMASK;
    default:
        return UCOL_TERTIARYORDERMASK | UCOL_SECONDARYORDERMASK |
               UCOL_PRIMARYORDERMASK;
    }
}

U_CDECL_BEGIN
static UBool U_CALLCONV
usearch_cleanup(void) {
    g_nfcImpl = nullptr;
    return TRUE;
}
U_CDECL_END

/**
* Initializing the fcd tables.
* Internal method, status assumed to be a success.
* @param status output error if any, caller to check status before calling
*               method, status assumed to be success when passed in.
*/
static
inline void initializeFCD(UErrorCode *status)
{
    if (g_nfcImpl == nullptr) {
        g_nfcImpl = Normalizer2Factory::getNFCImpl(*status);
        ucln_i18n_registerCleanup(UCLN_I18N_USEARCH, usearch_cleanup);
    }
}

/**
* Gets the fcd value for a character at the argument index.
* This method takes into accounts of the supplementary characters.
* @param str UTF16 string where character for fcd retrieval resides
* @param offset position of the character whose fcd is to be retrieved, to be
*               overwritten with the next character position, taking
*               surrogate characters into consideration.
* @param strlength length of the argument string
* @return fcd value
*/
static
uint16_t getFCD(const UChar   *str, int32_t *offset,
                             int32_t  strlength)
{
    const UChar *temp = str + *offset;
    uint16_t    result = g_nfcImpl->nextFCD16(temp, str + strlength);
    *offset = (int32_t)(temp - str);
    return result;
}

/**
* Getting the modified collation elements taking into account the collation
* attributes
* @param strsrch string search data
* @param sourcece
* @return the modified collation element
*/
static
inline int32_t getCE(const UStringSearch *strsrch, uint32_t sourcece)
{
    // note for tertiary we can't use the collator->tertiaryMask, that
    // is a preprocessed mask that takes into account case options. since
    // we are only concerned with exact matches, we don't need that.
    sourcece &= strsrch->ceMask;

    if (strsrch->toShift) {
        // alternate handling here, since only the 16 most significant digits
        // is only used, we can safely do a compare without masking
        // if the ce is a variable, we mask and get only the primary values
        // no shifting to quartenary is required since all primary values
        // less than variabletop will need to be masked off anyway.
        if (strsrch->variableTop > sourcece) {
            if (strsrch->strength >= UCOL_QUATERNARY) {
                sourcece &= UCOL_PRIMARYORDERMASK;
            }
            else {
                sourcece = UCOL_IGNORABLE;
            }
        }
    } else if (strsrch->strength >= UCOL_QUATERNARY && sourcece == UCOL_IGNORABLE) {
        sourcece = 0xFFFF;
    }

    return sourcece;
}

/**
* Allocate a memory and returns nullptr if it failed.
* Internal method, status assumed to be a success.
* @param size to allocate
* @param status output error if any, caller to check status before calling
*               method, status assumed to be success when passed in.
* @return newly allocated array, nullptr otherwise
*/
static
inline void * allocateMemory(uint32_t size, UErrorCode *status)
{
    uint32_t *result = (uint32_t *)uprv_malloc(size);
    if (result == nullptr) {
        *status = U_MEMORY_ALLOCATION_ERROR;
    }
    return result;
}

/**
* Adds a uint32_t value to a destination array.
* Creates a new array if we run out of space. The caller will have to
* manually deallocate the newly allocated array.
* Internal method, status assumed to be success, caller has to check status
* before calling this method. destination not to be nullptr and has at least
* size destinationlength.
* @param destination target array
* @param offset destination offset to add value
* @param destinationlength target array size, return value for the new size
* @param value to be added
* @param increments incremental size expected
* @param status output error if any, caller to check status before calling
*               method, status assumed to be success when passed in.
* @return new destination array, destination if there was no new allocation
*/
static
inline int32_t * addTouint32_tArray(int32_t    *destination,
                                    uint32_t    offset,
                                    uint32_t   *destinationlength,
                                    uint32_t    value,
                                    uint32_t    increments,
                                    UErrorCode *status)
{
    uint32_t newlength = *destinationlength;
    if (offset + 1 == newlength) {
        newlength += increments;
        int32_t *temp = (int32_t *)allocateMemory(
                                         sizeof(int32_t) * newlength, status);
        if (U_FAILURE(*status)) {
            return nullptr;
        }
        uprv_memcpy(temp, destination, sizeof(int32_t) * (size_t)offset);
        *destinationlength = newlength;
        destination        = temp;
    }
    destination[offset] = value;
    return destination;
}

/**
* Adds a uint64_t value to a destination array.
* Creates a new array if we run out of space. The caller will have to
* manually deallocate the newly allocated array.
* Internal method, status assumed to be success, caller has to check status
* before calling this method. destination not to be nullptr and has at least
* size destinationlength.
* @param destination target array
* @param offset destination offset to add value
* @param destinationlength target array size, return value for the new size
* @param value to be added
* @param increments incremental size expected
* @param status output error if any, caller to check status before calling
*               method, status assumed to be success when passed in.
* @return new destination array, destination if there was no new allocation
*/
static
inline int64_t * addTouint64_tArray(int64_t    *destination,
                                    uint32_t    offset,
                                    uint32_t   *destinationlength,
                                    uint64_t    value,
                                    uint32_t    increments,
                                    UErrorCode *status)
{
    uint32_t newlength = *destinationlength;
    if (offset + 1 == newlength) {
        newlength += increments;
        int64_t *temp = (int64_t *)allocateMemory(
                                         sizeof(int64_t) * newlength, status);

        if (U_FAILURE(*status)) {
            return nullptr;
        }

        uprv_memcpy(temp, destination, sizeof(int64_t) * (size_t)offset);
        *destinationlength = newlength;
        destination        = temp;
    }

    destination[offset] = value;

    return destination;
}

/**
* Initializing the ce table for a pattern.
* Stores non-ignorable collation keys.
* Table size will be estimated by the size of the pattern text. Table
* expansion will be perform as we go along. Adding 1 to ensure that the table
* size definitely increases.
* Internal method, status assumed to be a success.
* @param strsrch string search data
* @param status output error if any, caller to check status before calling
*               method, status assumed to be success when passed in.
*/
static
inline void initializePatternCETable(UStringSearch *strsrch, UErrorCode *status)
{
    UPattern *pattern            = &(strsrch->pattern);
    uint32_t  cetablesize        = INITIAL_ARRAY_SIZE_;
    int32_t  *cetable            = pattern->cesBuffer;
    uint32_t  patternlength      = pattern->textLength;
    UCollationElements *coleiter = strsrch->utilIter;

    if (coleiter == nullptr) {
        coleiter = ucol_openElements(strsrch->collator, pattern->text,
                                     patternlength, status);
        // status will be checked in ucol_next(..) later and if it is an
        // error UCOL_NULLORDER the result of ucol_next(..) and 0 will be
        // returned.
        strsrch->utilIter = coleiter;
    }
    else {
        ucol_setText(coleiter, pattern->text, pattern->textLength, status);
    }
    if(U_FAILURE(*status)) {
        return;
    }

    if (pattern->ces != cetable && pattern->ces) {
        uprv_free(pattern->ces);
    }

    uint32_t  offset      = 0;
    int32_t   ce;

    while ((ce = ucol_next(coleiter, status)) != UCOL_NULLORDER &&
           U_SUCCESS(*status)) {
        uint32_t newce = getCE(strsrch, ce);
        if (newce) {
            int32_t *temp = addTouint32_tArray(cetable, offset, &cetablesize,
                                  newce,
                                  patternlength - ucol_getOffset(coleiter) + 1,
                                  status);
            if (U_FAILURE(*status)) {
                return;
            }
            offset ++;
            if (cetable != temp && cetable != pattern->cesBuffer) {
                uprv_free(cetable);
            }
            cetable = temp;
        }
    }

    cetable[offset]   = 0;
    pattern->ces       = cetable;
    pattern->cesLength = offset;
}

/**
* Initializing the pce table for a pattern.
* Stores non-ignorable collation keys.
* Table size will be estimated by the size of the pattern text. Table
* expansion will be perform as we go along. Adding 1 to ensure that the table
* size definitely increases.
* Internal method, status assumed to be a success.
* @param strsrch string search data
* @param status output error if any, caller to check status before calling
*               method, status assumed to be success when passed in.
*/
static
inline void initializePatternPCETable(UStringSearch *strsrch,
                                      UErrorCode    *status)
{
    UPattern *pattern            = &(strsrch->pattern);
    uint32_t  pcetablesize       = INITIAL_ARRAY_SIZE_;
    int64_t  *pcetable           = pattern->pcesBuffer;
    uint32_t  patternlength      = pattern->textLength;
    UCollationElements *coleiter = strsrch->utilIter;

    if (coleiter == nullptr) {
        coleiter = ucol_openElements(strsrch->collator, pattern->text,
                                     patternlength, status);
        // status will be checked in nextProcessed(..) later and if it is an error
        // then UCOL_PROCESSED_NULLORDER is returned by nextProcessed(..), so 0 will be
        // returned.
        strsrch->utilIter = coleiter;
    } else {
        ucol_setText(coleiter, pattern->text, pattern->textLength, status);
    }
    if(U_FAILURE(*status)) {
        return;
    }

    if (pattern->pces != pcetable && pattern->pces != nullptr) {
        uprv_free(pattern->pces);
    }

    uint32_t  offset = 0;
    int64_t   pce;

    icu::UCollationPCE iter(coleiter);

    // ** Should processed CEs be signed or unsigned?
    // ** (the rest of the code in this file seems to play fast-and-loose with
    // **  whether a CE is signed or unsigned. For example, look at routine above this one.)
    while ((pce = iter.nextProcessed(nullptr, nullptr, status)) != UCOL_PROCESSED_NULLORDER &&
           U_SUCCESS(*status)) {
        int64_t *temp = addTouint64_tArray(pcetable, offset, &pcetablesize,
                              pce,
                              patternlength - ucol_getOffset(coleiter) + 1,
                              status);

        if (U_FAILURE(*status)) {
            return;
        }

        offset += 1;

        if (pcetable != temp && pcetable != pattern->pcesBuffer) {
            uprv_free(pcetable);
        }

        pcetable = temp;
    }

    pcetable[offset]   = 0;
    pattern->pces       = pcetable;
    pattern->pcesLength = offset;
}

/**
* Initializes the pattern struct.
* @param strsrch UStringSearch data storage
* @param status output error if any, caller to check status before calling
*               method, status assumed to be success when passed in.
*/
static
inline void initializePattern(UStringSearch *strsrch, UErrorCode *status)
{
    if (U_FAILURE(*status)) { return; }

          UPattern   *pattern     = &(strsrch->pattern);
    const UChar      *patterntext = pattern->text;
          int32_t     length      = pattern->textLength;
          int32_t index       = 0;

    // Since the strength is primary, accents are ignored in the pattern.
    if (strsrch->strength == UCOL_PRIMARY) {
        pattern->hasPrefixAccents = 0;
        pattern->hasSuffixAccents = 0;
    } else {
        pattern->hasPrefixAccents = getFCD(patterntext, &index, length) >>
                                                         SECOND_LAST_BYTE_SHIFT_;
        index = length;
        U16_BACK_1(patterntext, 0, index);
        pattern->hasSuffixAccents = getFCD(patterntext, &index, length) &
                                                                 LAST_BYTE_MASK_;
    }

    // ** HACK **
    if (strsrch->pattern.pces != nullptr) {
        if (strsrch->pattern.pces != strsrch->pattern.pcesBuffer) {
            uprv_free(strsrch->pattern.pces);
        }

        strsrch->pattern.pces = nullptr;
    }

    initializePatternCETable(strsrch, status);
}

/**
* Initializes the pattern struct and builds the pattern collation element table.
* @param strsrch UStringSearch data storage
* @param status  for output errors if it occurs, status is assumed to be a
*                success when it is passed in.
*/
static
inline void initialize(UStringSearch *strsrch, UErrorCode *status)
{
    initializePattern(strsrch, status);
}

#if !UCONFIG_NO_BREAK_ITERATION
// If the caller provided a character breakiterator we'll return that,
// otherwise we lazily create the internal break iterator. 
static UBreakIterator* getBreakIterator(UStringSearch *strsrch, UErrorCode &status)
{
    if (U_FAILURE(status)) {
        return nullptr;
    }

    if (strsrch->search->breakIter != nullptr) {
        return strsrch->search->breakIter;
    }

    if (strsrch->search->internalBreakIter != nullptr) {
        return strsrch->search->internalBreakIter;
    }

    // Need to create the internal break iterator.
    strsrch->search->internalBreakIter = ubrk_open(UBRK_CHARACTER,
        ucol_getLocaleByType(strsrch->collator, ULOC_VALID_LOCALE, &status),
        strsrch->search->text, strsrch->search->textLength, &status);

    return strsrch->search->internalBreakIter;
}
#endif

/**
* Sets the match result to "not found", regardless of the incoming error status.
* If an error occurs while setting the result, it is reported back.
* 
* @param strsrch string search data
* @param status  for output errors, if they occur.
*/
static
inline void setMatchNotFound(UStringSearch *strsrch, UErrorCode &status)
{
    UErrorCode localStatus = U_ZERO_ERROR;

    strsrch->search->matchedIndex = USEARCH_DONE;
    strsrch->search->matchedLength = 0;
    if (strsrch->search->isForwardSearching) {
        setColEIterOffset(strsrch->textIter, strsrch->search->textLength, localStatus);
    }
    else {
        setColEIterOffset(strsrch->textIter, 0, localStatus);
    }

    // If an error occurred while setting the result to not found (ex: OOM),
    // then we want to report that error back to the caller.
    if (U_SUCCESS(status) && U_FAILURE(localStatus)) {
        status = localStatus;
    }
}

/**
* Checks if the offset runs out of the text string
* @param offset
* @param textlength of the text string
* @return TRUE if offset is out of bounds, FALSE otherwise
*/
static
inline UBool isOutOfBounds(int32_t textlength, int32_t offset)
{
    return offset < 0 || offset > textlength;
}

/**
* Checks for identical match
* @param strsrch string search data
* @param start offset of possible match
* @param end offset of possible match
* @return TRUE if identical match is found
*/
static
inline UBool checkIdentical(const UStringSearch *strsrch, int32_t start, int32_t end)
{
    if (strsrch->strength != UCOL_IDENTICAL) {
        return TRUE;
    }

    // Note: We could use Normalizer::compare() or similar, but for short strings
    // which may not be in FCD it might be faster to just NFD them.
    UErrorCode status = U_ZERO_ERROR;
    UnicodeString t2, p2;
    strsrch->nfd->normalize(
        UnicodeString(FALSE, strsrch->search->text + start, end - start), t2, status);
    strsrch->nfd->normalize(
        UnicodeString(FALSE, strsrch->pattern.text, strsrch->pattern.textLength), p2, status);
    // return FALSE if NFD failed
    return U_SUCCESS(status) && t2 == p2;
}

// constructors and destructor -------------------------------------------

U_CAPI UStringSearch * U_EXPORT2 usearch_open(const UChar *pattern,
                                          int32_t         patternlength,
                                    const UChar          *text,
                                          int32_t         textlength,
                                    const char           *locale,
                                          UBreakIterator *breakiter,
                                          UErrorCode     *status)
{
    if (U_FAILURE(*status)) {
        return nullptr;
    }
#if UCONFIG_NO_BREAK_ITERATION
    if (breakiter != nullptr) {
        *status = U_UNSUPPORTED_ERROR;
        return nullptr;
    }
#endif
    if (locale) {
        // ucol_open internally checks for status
        UCollator     *collator = ucol_open(locale, status);
        // pattern, text checks are done in usearch_openFromCollator
        UStringSearch *result   = usearch_openFromCollator(pattern,
                                              patternlength, text, textlength,
                                              collator, breakiter, status);

        if (result == nullptr || U_FAILURE(*status)) {
            if (collator) {
                ucol_close(collator);
            }
            return nullptr;
        }
        else {
            result->ownCollator = TRUE;
        }
        return result;
    }
    *status = U_ILLEGAL_ARGUMENT_ERROR;
    return nullptr;
}

U_CAPI UStringSearch * U_EXPORT2 usearch_openFromCollator(
                                  const UChar          *pattern,
                                        int32_t         patternlength,
                                  const UChar          *text,
                                        int32_t         textlength,
                                  const UCollator      *collator,
                                        UBreakIterator *breakiter,
                                        UErrorCode     *status)
{
    if (U_FAILURE(*status)) {
        return nullptr;
    }
#if UCONFIG_NO_BREAK_ITERATION
    if (breakiter != nullptr) {
        *status = U_UNSUPPORTED_ERROR;
        return nullptr;
    }
#endif
    if (pattern == nullptr || text == nullptr || collator == nullptr) {
        *status = U_ILLEGAL_ARGUMENT_ERROR;
        return nullptr;
    }

    // string search does not really work when numeric collation is turned on
    if(ucol_getAttribute(collator, UCOL_NUMERIC_COLLATION, status) == UCOL_ON) {
        *status = U_UNSUPPORTED_ERROR;
        return nullptr;
    }

    if (U_SUCCESS(*status)) {
        initializeFCD(status);
        if (U_FAILURE(*status)) {
            return nullptr;
        }

        UStringSearch *result;
        if (textlength == -1) {
            textlength = u_strlen(text);
        }
        if (patternlength == -1) {
            patternlength = u_strlen(pattern);
        }
        if (textlength <= 0 || patternlength <= 0) {
            *status = U_ILLEGAL_ARGUMENT_ERROR;
            return nullptr;
        }

        result = (UStringSearch *)uprv_malloc(sizeof(UStringSearch));
        if (result == nullptr) {
            *status = U_MEMORY_ALLOCATION_ERROR;
            return nullptr;
        }

        result->collator    = collator;
        result->strength    = ucol_getStrength(collator);
        result->ceMask      = getMask(result->strength);
        result->toShift     =
             ucol_getAttribute(collator, UCOL_ALTERNATE_HANDLING, status) ==
                                                            UCOL_SHIFTED;
        result->variableTop = ucol_getVariableTop(collator, status);

        result->nfd         = Normalizer2::getNFDInstance(*status);

        if (U_FAILURE(*status)) {
            uprv_free(result);
            return nullptr;
        }

        result->search             = (USearch *)uprv_malloc(sizeof(USearch));
        if (result->search == nullptr) {
            *status = U_MEMORY_ALLOCATION_ERROR;
            uprv_free(result);
            return nullptr;
        }

        result->search->text       = text;
        result->search->textLength = textlength;

        result->pattern.text       = pattern;
        result->pattern.textLength = patternlength;
        result->pattern.ces         = nullptr;
        result->pattern.pces        = nullptr;

        result->search->breakIter  = breakiter;
#if !UCONFIG_NO_BREAK_ITERATION
        result->search->internalBreakIter = nullptr; // Lazily created.
        if (breakiter) {
            ubrk_setText(breakiter, text, textlength, status);
        }
#endif

        result->ownCollator           = FALSE;
        result->search->matchedLength = 0;
        result->search->matchedIndex  = USEARCH_DONE;
        result->utilIter              = nullptr;
        result->textIter              = ucol_openElements(collator, text,
                                                          textlength, status);
        result->textProcessedIter     = nullptr;
        if (U_FAILURE(*status)) {
            usearch_close(result);
            return nullptr;
        }

        result->search->isOverlap          = FALSE;
        result->search->isCanonicalMatch   = FALSE;
        result->search->elementComparisonType = 0;
        result->search->isForwardSearching = TRUE;
        result->search->reset              = TRUE;

        initialize(result, status);

        if (U_FAILURE(*status)) {
            usearch_close(result);
            return nullptr;
        }

        return result;
    }
    return nullptr;
}

U_CAPI void U_EXPORT2 usearch_close(UStringSearch *strsrch)
{
    if (strsrch) {
        if (strsrch->pattern.ces != strsrch->pattern.cesBuffer &&
            strsrch->pattern.ces) {
            uprv_free(strsrch->pattern.ces);
        }

        if (strsrch->pattern.pces != nullptr &&
            strsrch->pattern.pces != strsrch->pattern.pcesBuffer) {
            uprv_free(strsrch->pattern.pces);
        }

        delete strsrch->textProcessedIter;
        ucol_closeElements(strsrch->textIter);
        ucol_closeElements(strsrch->utilIter);

        if (strsrch->ownCollator && strsrch->collator) {
            ucol_close((UCollator *)strsrch->collator);
        }

#if !UCONFIG_NO_BREAK_ITERATION
        if (strsrch->search->internalBreakIter != nullptr) {
            ubrk_close(strsrch->search->internalBreakIter);
        }
#endif

        uprv_free(strsrch->search);
        uprv_free(strsrch);
    }
}

namespace {

UBool initTextProcessedIter(UStringSearch *strsrch, UErrorCode *status) {
    if (U_FAILURE(*status)) { return FALSE; }
    if (strsrch->textProcessedIter == nullptr) {
        strsrch->textProcessedIter = new icu::UCollationPCE(strsrch->textIter);
        if (strsrch->textProcessedIter == nullptr) {
            *status = U_MEMORY_ALLOCATION_ERROR;
            return FALSE;
        }
    } else {
        strsrch->textProcessedIter->init(strsrch->textIter);
    }
    return TRUE;
}

}

// set and get methods --------------------------------------------------

U_CAPI void U_EXPORT2 usearch_setOffset(UStringSearch *strsrch,
                                        int32_t        position,
                                        UErrorCode    *status)
{
    if (U_SUCCESS(*status) && strsrch) {
        if (isOutOfBounds(strsrch->search->textLength, position)) {
            *status = U_INDEX_OUTOFBOUNDS_ERROR;
        }
        else {
            setColEIterOffset(strsrch->textIter, position, *status);
        }
        strsrch->search->matchedIndex  = USEARCH_DONE;
        strsrch->search->matchedLength = 0;
        strsrch->search->reset         = FALSE;
    }
}

U_CAPI int32_t U_EXPORT2 usearch_getOffset(const UStringSearch *strsrch)
{
    if (strsrch) {
        int32_t result = ucol_getOffset(strsrch->textIter);
        if (isOutOfBounds(strsrch->search->textLength, result)) {
            return USEARCH_DONE;
        }
        return result;
    }
    return USEARCH_DONE;
}

U_CAPI void U_EXPORT2 usearch_setAttribute(UStringSearch        *strsrch,
                                           USearchAttribute      attribute,
                                           USearchAttributeValue value,
                                           UErrorCode           *status)
{
    if (U_SUCCESS(*status) && strsrch) {
        switch (attribute)
        {
        case USEARCH_OVERLAP :
            strsrch->search->isOverlap = (value == USEARCH_ON ? TRUE : FALSE);
            break;
        case USEARCH_CANONICAL_MATCH :
            strsrch->search->isCanonicalMatch = (value == USEARCH_ON ? TRUE :
                                                                      FALSE);
            break;
        case USEARCH_ELEMENT_COMPARISON :
            if (value == USEARCH_PATTERN_BASE_WEIGHT_IS_WILDCARD || value == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD) {
                strsrch->search->elementComparisonType = (int16_t)value;
            } else {
                strsrch->search->elementComparisonType = 0;
            }
            break;
        case USEARCH_ATTRIBUTE_COUNT :
        default:
            *status = U_ILLEGAL_ARGUMENT_ERROR;
        }
    }
    if (value == USEARCH_ATTRIBUTE_VALUE_COUNT) {
        *status = U_ILLEGAL_ARGUMENT_ERROR;
    }
}

U_CAPI USearchAttributeValue U_EXPORT2 usearch_getAttribute(
                                                const UStringSearch *strsrch,
                                                USearchAttribute attribute)
{
    if (strsrch) {
        switch (attribute) {
        case USEARCH_OVERLAP :
            return (strsrch->search->isOverlap == TRUE ? USEARCH_ON :
                                                        USEARCH_OFF);
        case USEARCH_CANONICAL_MATCH :
            return (strsrch->search->isCanonicalMatch == TRUE ? USEARCH_ON :
                                                               USEARCH_OFF);
        case USEARCH_ELEMENT_COMPARISON :
            {
                int16_t value = strsrch->search->elementComparisonType;
                if (value == USEARCH_PATTERN_BASE_WEIGHT_IS_WILDCARD || value == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD) {
                    return (USearchAttributeValue)value;
                } else {
                    return USEARCH_STANDARD_ELEMENT_COMPARISON;
                }
            }
        case USEARCH_ATTRIBUTE_COUNT :
            return USEARCH_DEFAULT;
        }
    }
    return USEARCH_DEFAULT;
}

U_CAPI int32_t U_EXPORT2 usearch_getMatchedStart(
                                                const UStringSearch *strsrch)
{
    if (strsrch == nullptr) {
        return USEARCH_DONE;
    }
    return strsrch->search->matchedIndex;
}


U_CAPI int32_t U_EXPORT2 usearch_getMatchedText(const UStringSearch *strsrch,
                                            UChar         *result,
                                            int32_t        resultCapacity,
                                            UErrorCode    *status)
{
    if (U_FAILURE(*status)) {
        return USEARCH_DONE;
    }
    if (strsrch == nullptr || resultCapacity < 0 || (resultCapacity > 0 &&
        result == nullptr)) {
        *status = U_ILLEGAL_ARGUMENT_ERROR;
        return USEARCH_DONE;
    }

    int32_t     copylength = strsrch->search->matchedLength;
    int32_t copyindex  = strsrch->search->matchedIndex;
    if (copyindex == USEARCH_DONE) {
        u_terminateUChars(result, resultCapacity, 0, status);
        return USEARCH_DONE;
    }

    if (resultCapacity < copylength) {
        copylength = resultCapacity;
    }
    if (copylength > 0) {
        uprv_memcpy(result, strsrch->search->text + copyindex,
                    copylength * sizeof(UChar));
    }
    return u_terminateUChars(result, resultCapacity,
                             strsrch->search->matchedLength, status);
}

U_CAPI int32_t U_EXPORT2 usearch_getMatchedLength(
                                              const UStringSearch *strsrch)
{
    if (strsrch) {
        return strsrch->search->matchedLength;
    }
    return USEARCH_DONE;
}

#if !UCONFIG_NO_BREAK_ITERATION

U_CAPI void U_EXPORT2 usearch_setBreakIterator(UStringSearch  *strsrch,
                                               UBreakIterator *breakiter,
                                               UErrorCode     *status)
{
    if (U_SUCCESS(*status) && strsrch) {
        strsrch->search->breakIter = breakiter;
        if (breakiter) {
            ubrk_setText(breakiter, strsrch->search->text,
                         strsrch->search->textLength, status);
        }
    }
}

U_CAPI const UBreakIterator* U_EXPORT2
usearch_getBreakIterator(const UStringSearch *strsrch)
{
    if (strsrch) {
        return strsrch->search->breakIter;
    }
    return nullptr;
}

#endif

U_CAPI void U_EXPORT2 usearch_setText(      UStringSearch *strsrch,
                                      const UChar         *text,
                                            int32_t        textlength,
                                            UErrorCode    *status)
{
    if (U_SUCCESS(*status)) {
        if (strsrch == nullptr || text == nullptr || textlength < -1 ||
            textlength == 0) {
            *status = U_ILLEGAL_ARGUMENT_ERROR;
        }
        else {
            if (textlength == -1) {
                textlength = u_strlen(text);
            }
            strsrch->search->text       = text;
            strsrch->search->textLength = textlength;
            ucol_setText(strsrch->textIter, text, textlength, status);
            strsrch->search->matchedIndex  = USEARCH_DONE;
            strsrch->search->matchedLength = 0;
            strsrch->search->reset         = TRUE;
#if !UCONFIG_NO_BREAK_ITERATION
            if (strsrch->search->breakIter != nullptr) {
                ubrk_setText(strsrch->search->breakIter, text,
                             textlength, status);
            }
            if (strsrch->search->internalBreakIter != nullptr) {
                ubrk_setText(strsrch->search->internalBreakIter, text, textlength, status);
            }
#endif
        }
    }
}

U_CAPI const UChar * U_EXPORT2 usearch_getText(const UStringSearch *strsrch,
                                                     int32_t       *length)
{
    if (strsrch) {
        *length = strsrch->search->textLength;
        return strsrch->search->text;
    }
    return nullptr;
}

U_CAPI void U_EXPORT2 usearch_setCollator(      UStringSearch *strsrch,
                                          const UCollator     *collator,
                                                UErrorCode    *status)
{
    if (U_SUCCESS(*status)) {
        if (collator == nullptr) {
            *status = U_ILLEGAL_ARGUMENT_ERROR;
            return;
        }

        if (strsrch) {
            delete strsrch->textProcessedIter;
            strsrch->textProcessedIter = nullptr;
            ucol_closeElements(strsrch->textIter);
            ucol_closeElements(strsrch->utilIter);
            strsrch->textIter = strsrch->utilIter = nullptr;
            if (strsrch->ownCollator && (strsrch->collator != collator)) {
                ucol_close((UCollator *)strsrch->collator);
                strsrch->ownCollator = FALSE;
            }
            strsrch->collator    = collator;
            strsrch->strength    = ucol_getStrength(collator);
            strsrch->ceMask      = getMask(strsrch->strength);
#if !UCONFIG_NO_BREAK_ITERATION
            if (strsrch->search->internalBreakIter != nullptr) {
                ubrk_close(strsrch->search->internalBreakIter);
                strsrch->search->internalBreakIter = nullptr;   // Lazily created.
            }
#endif
            // if status is a failure, ucol_getAttribute returns UCOL_DEFAULT
            strsrch->toShift     =
               ucol_getAttribute(collator, UCOL_ALTERNATE_HANDLING, status) ==
                                                                UCOL_SHIFTED;
            // if status is a failure, ucol_getVariableTop returns 0
            strsrch->variableTop = ucol_getVariableTop(collator, status);
            strsrch->textIter = ucol_openElements(collator,
                                      strsrch->search->text,
                                      strsrch->search->textLength,
                                      status);
            strsrch->utilIter = ucol_openElements(
                    collator, strsrch->pattern.text, strsrch->pattern.textLength, status);
            // initialize() _after_ setting the iterators for the new collator.
            initialize(strsrch, status);
        }

        // **** are these calls needed?
        // **** we call uprv_init_pce in initializePatternPCETable
        // **** and the CEIBuffer constructor...
#if 0
        uprv_init_pce(strsrch->textIter);
        uprv_init_pce(strsrch->utilIter);
#endif
    }
}

U_CAPI UCollator * U_EXPORT2 usearch_getCollator(const UStringSearch *strsrch)
{
    if (strsrch) {
        return (UCollator *)strsrch->collator;
    }
    return nullptr;
}

U_CAPI void U_EXPORT2 usearch_setPattern(      UStringSearch *strsrch,
                                         const UChar         *pattern,
                                               int32_t        patternlength,
                                               UErrorCode    *status)
{
    if (U_SUCCESS(*status)) {
        if (strsrch == nullptr || pattern == nullptr) {
            *status = U_ILLEGAL_ARGUMENT_ERROR;
        }
        else {
            if (patternlength == -1) {
                patternlength = u_strlen(pattern);
            }
            if (patternlength == 0) {
                *status = U_ILLEGAL_ARGUMENT_ERROR;
                return;
            }
            strsrch->pattern.text       = pattern;
            strsrch->pattern.textLength = patternlength;
            initialize(strsrch, status);
        }
    }
}

U_CAPI const UChar* U_EXPORT2
usearch_getPattern(const UStringSearch *strsrch,
                   int32_t             *length)
{
    if (strsrch) {
        *length = strsrch->pattern.textLength;
        return strsrch->pattern.text;
    }
    return nullptr;
}

// miscellaneous methods --------------------------------------------------

U_CAPI int32_t U_EXPORT2 usearch_first(UStringSearch *strsrch,
                                       UErrorCode    *status)
{
    if (strsrch && U_SUCCESS(*status)) {
        strsrch->search->isForwardSearching = TRUE;
        usearch_setOffset(strsrch, 0, status);
        if (U_SUCCESS(*status)) {
            return usearch_next(strsrch, status);
        }
    }
    return USEARCH_DONE;
}

U_CAPI int32_t U_EXPORT2 usearch_following(UStringSearch *strsrch,
                                           int32_t        position,
                                           UErrorCode    *status)
{
    if (strsrch && U_SUCCESS(*status)) {
        strsrch->search->isForwardSearching = TRUE;
        // position checked in usearch_setOffset
        usearch_setOffset(strsrch, position, status);
        if (U_SUCCESS(*status)) {
            return usearch_next(strsrch, status);
        }
    }
    return USEARCH_DONE;
}

U_CAPI int32_t U_EXPORT2 usearch_last(UStringSearch *strsrch,
                                      UErrorCode    *status)
{
    if (strsrch && U_SUCCESS(*status)) {
        strsrch->search->isForwardSearching = FALSE;
        usearch_setOffset(strsrch, strsrch->search->textLength, status);
        if (U_SUCCESS(*status)) {
            return usearch_previous(strsrch, status);
        }
    }
    return USEARCH_DONE;
}

U_CAPI int32_t U_EXPORT2 usearch_preceding(UStringSearch *strsrch,
                                           int32_t        position,
                                           UErrorCode    *status)
{
    if (strsrch && U_SUCCESS(*status)) {
        strsrch->search->isForwardSearching = FALSE;
        // position checked in usearch_setOffset
        usearch_setOffset(strsrch, position, status);
        if (U_SUCCESS(*status)) {
            return usearch_previous(strsrch, status);
        }
    }
    return USEARCH_DONE;
}

/**
* If a direction switch is required, we'll count the number of ces till the
* beginning of the collation element iterator and iterate forwards that
* number of times. This is so that we get to the correct point within the
* string to continue the search in. Imagine when we are in the middle of the
* normalization buffer when the change in direction is request. arrrgghh....
* After searching the offset within the collation element iterator will be
* shifted to the start of the match. If a match is not found, the offset would
* have been set to the end of the text string in the collation element
* iterator.
* Okay, here's my take on normalization buffer. The only time when there can
* be 2 matches within the same normalization is when the pattern is consists
* of all accents. But since the offset returned is from the text string, we
* should not confuse the caller by returning the second match within the
* same normalization buffer. If we do, the 2 results will have the same match
* offsets, and that'll be confusing. I'll return the next match that doesn't
* fall within the same normalization buffer. Note this does not affect the
* results of matches spanning the text and the normalization buffer.
* The position to start searching is taken from the collation element
* iterator. Callers of this API would have to set the offset in the collation
* element iterator before using this method.
*/
U_CAPI int32_t U_EXPORT2 usearch_next(UStringSearch *strsrch,
                                      UErrorCode    *status)
{
    if (U_SUCCESS(*status) && strsrch) {
        // note offset is either equivalent to the start of the previous match
        // or is set by the user
        int32_t      offset       = usearch_getOffset(strsrch);
        USearch     *search       = strsrch->search;
        search->reset             = FALSE;
        int32_t      textlength   = search->textLength;
        if (search->isForwardSearching) {
            if (offset == textlength ||
                (! search->isOverlap &&
                (search->matchedIndex != USEARCH_DONE &&
                offset + search->matchedLength > textlength))) {
                    // not enough characters to match
                    setMatchNotFound(strsrch, *status);
                    return USEARCH_DONE;
            }
        }
        else {
            // switching direction.
            // if matchedIndex == USEARCH_DONE, it means that either a
            // setOffset has been called or that previous ran off the text
            // string. the iterator would have been set to offset 0 if a
            // match is not found.
            search->isForwardSearching = TRUE;
            if (search->matchedIndex != USEARCH_DONE) {
                // there's no need to set the collation element iterator
                // the next call to next will set the offset.
                return search->matchedIndex;
            }
        }

        if (U_SUCCESS(*status)) {
            if (strsrch->pattern.cesLength == 0) {
                if (search->matchedIndex == USEARCH_DONE) {
                    search->matchedIndex = offset;
                }
                else { // moves by codepoints
                    U16_FWD_1(search->text, search->matchedIndex, textlength);
                }

                search->matchedLength = 0;
                setColEIterOffset(strsrch->textIter, search->matchedIndex, *status);
                // status checked below
                if (search->matchedIndex == textlength) {
                    search->matchedIndex = USEARCH_DONE;
                }
            }
            else {
                if (search->matchedLength > 0) {
                    // if matchlength is 0 we are at the start of the iteration
                    if (search->isOverlap) {
                        ucol_setOffset(strsrch->textIter, offset + 1, status);
                    }
                    else {
                        ucol_setOffset(strsrch->textIter,
                                       offset + search->matchedLength, status);
                    }
                }
                else {
                    // for boundary check purposes. this will ensure that the
                    // next match will not precede the current offset
                    // note search->matchedIndex will always be set to something
                    // in the code
                    search->matchedIndex = offset - 1;
                }

                if (search->isCanonicalMatch) {
                    // can't use exact here since extra accents are allowed.
                    usearch_handleNextCanonical(strsrch, status);
                }
                else {
                    usearch_handleNextExact(strsrch, status);
                }
            }

            if (U_FAILURE(*status)) {
                return USEARCH_DONE;
            }

            if (search->matchedIndex == USEARCH_DONE) {
                ucol_setOffset(strsrch->textIter, search->textLength, status);
            } else {
                ucol_setOffset(strsrch->textIter, search->matchedIndex, status);
            }

            return search->matchedIndex;
        }
    }
    return USEARCH_DONE;
}

U_CAPI int32_t U_EXPORT2 usearch_previous(UStringSearch *strsrch,
                                          UErrorCode    *status)
{
    if (U_SUCCESS(*status) && strsrch) {
        int32_t offset;
        USearch *search = strsrch->search;
        if (search->reset) {
            offset                     = search->textLength;
            search->isForwardSearching = FALSE;
            search->reset              = FALSE;
            setColEIterOffset(strsrch->textIter, offset, *status);
        }
        else {
            offset = usearch_getOffset(strsrch);
        }

        int32_t matchedindex = search->matchedIndex;
        if (search->isForwardSearching == TRUE) {
            // switching direction.
            // if matchedIndex == USEARCH_DONE, it means that either a
            // setOffset has been called or that next ran off the text
            // string. the iterator would have been set to offset textLength if
            // a match is not found.
            search->isForwardSearching = FALSE;
            if (matchedindex != USEARCH_DONE) {
                return matchedindex;
            }
        }
        else {

            // Could check pattern length, but the
            // linear search will do the right thing
            if (offset == 0 || matchedindex == 0) {
                setMatchNotFound(strsrch, *status);
                return USEARCH_DONE;
            }
        }

        if (U_SUCCESS(*status)) {
            if (strsrch->pattern.cesLength == 0) {
                search->matchedIndex =
                      (matchedindex == USEARCH_DONE ? offset : matchedindex);
                if (search->matchedIndex == 0) {
                    setMatchNotFound(strsrch, *status);
                    // status checked below
                }
                else { // move by codepoints
                    U16_BACK_1(search->text, 0, search->matchedIndex);
                    setColEIterOffset(strsrch->textIter, search->matchedIndex, *status);
                    // status checked below
                    search->matchedLength = 0;
                }
            }
            else {
                if (strsrch->search->isCanonicalMatch) {
                    // can't use exact here since extra accents are allowed.
                    usearch_handlePreviousCanonical(strsrch, status);
                    // status checked below
                }
                else {
                    usearch_handlePreviousExact(strsrch, status);
                    // status checked below
                }
            }

            if (U_FAILURE(*status)) {
                return USEARCH_DONE;
            }

            return search->matchedIndex;
        }
    }
    return USEARCH_DONE;
}


U_CAPI void U_EXPORT2 usearch_reset(UStringSearch *strsrch)
{
    /*
    reset is setting the attributes that are already in
    string search, hence all attributes in the collator should
    be retrieved without any problems
    */
    if (strsrch) {
        UErrorCode status            = U_ZERO_ERROR;
        UBool      sameCollAttribute = TRUE;
        uint32_t   ceMask;
        UBool      shift;
        uint32_t   varTop;

        // **** hack to deal w/ how processed CEs encode quaternary ****
        UCollationStrength newStrength = ucol_getStrength(strsrch->collator);
        if ((strsrch->strength < UCOL_QUATERNARY && newStrength >= UCOL_QUATERNARY) ||
            (strsrch->strength >= UCOL_QUATERNARY && newStrength < UCOL_QUATERNARY)) {
                sameCollAttribute = FALSE;
        }

        strsrch->strength    = ucol_getStrength(strsrch->collator);
        ceMask = getMask(strsrch->strength);
        if (strsrch->ceMask != ceMask) {
            strsrch->ceMask = ceMask;
            sameCollAttribute = FALSE;
        }

        // if status is a failure, ucol_getAttribute returns UCOL_DEFAULT
        shift = ucol_getAttribute(strsrch->collator, UCOL_ALTERNATE_HANDLING,
                                  &status) == UCOL_SHIFTED;
        if (strsrch->toShift != shift) {
            strsrch->toShift  = shift;
            sameCollAttribute = FALSE;
        }

        // if status is a failure, ucol_getVariableTop returns 0
        varTop = ucol_getVariableTop(strsrch->collator, &status);
        if (strsrch->variableTop != varTop) {
            strsrch->variableTop = varTop;
            sameCollAttribute    = FALSE;
        }
        if (!sameCollAttribute) {
            initialize(strsrch, &status);
        }
        ucol_setText(strsrch->textIter, strsrch->search->text,
                              strsrch->search->textLength,
                              &status);
        strsrch->search->matchedLength      = 0;
        strsrch->search->matchedIndex       = USEARCH_DONE;
        strsrch->search->isOverlap          = FALSE;
        strsrch->search->isCanonicalMatch   = FALSE;
        strsrch->search->elementComparisonType = 0;
        strsrch->search->isForwardSearching = TRUE;
        strsrch->search->reset              = TRUE;
    }
}

//
//  CEI  Collation Element + source text index.
//       These structs are kept in the circular buffer.
//
struct  CEI {
    int64_t ce;
    int32_t lowIndex;
    int32_t highIndex;
};

U_NAMESPACE_BEGIN

namespace {
//
//  CEIBuffer   A circular buffer of CEs-with-index from the text being searched.
//
#define   DEFAULT_CEBUFFER_SIZE 96
#define   CEBUFFER_EXTRA 32
// Some typical max values to make buffer size more reasonable for asymmetric search.
// #8694 is for a better long-term solution to allocation of this buffer.
#define   MAX_TARGET_IGNORABLES_PER_PAT_JAMO_L 8
#define   MAX_TARGET_IGNORABLES_PER_PAT_OTHER 3
#define   MIGHT_BE_JAMO_L(c) ((c >= 0x1100 && c <= 0x115E) || (c >= 0x3131 && c <= 0x314E) || (c >= 0x3165 && c <= 0x3186))
struct CEIBuffer {
    CEI                  defBuf[DEFAULT_CEBUFFER_SIZE];
    CEI                 *buf;
    int32_t              bufSize;
    int32_t              firstIx;
    int32_t              limitIx;
    UCollationElements  *ceIter;
    UStringSearch       *strSearch;


               CEIBuffer(UStringSearch *ss, UErrorCode *status);
               ~CEIBuffer();
   const CEI   *get(int32_t index);
   const CEI   *getPrevious(int32_t index);
};


CEIBuffer::CEIBuffer(UStringSearch *ss, UErrorCode *status) {
    buf = defBuf;
    strSearch = ss;
    bufSize = ss->pattern.pcesLength + CEBUFFER_EXTRA;
    if (ss->search->elementComparisonType != 0) {
        const UChar * patText = ss->pattern.text;
        if (patText) {
            const UChar * patTextLimit = patText + ss->pattern.textLength;
            while ( patText < patTextLimit ) {
                UChar c = *patText++;
                if (MIGHT_BE_JAMO_L(c)) {
                    bufSize += MAX_TARGET_IGNORABLES_PER_PAT_JAMO_L;
                } else {
                    // No check for surrogates, we might allocate slightly more buffer than necessary.
                    bufSize += MAX_TARGET_IGNORABLES_PER_PAT_OTHER;
                }
            }
        }
    }
    ceIter    = ss->textIter;
    firstIx = 0;
    limitIx = 0;

    if (!initTextProcessedIter(ss, status)) { return; }

    if (bufSize>DEFAULT_CEBUFFER_SIZE) {
        buf = (CEI *)uprv_malloc(bufSize * sizeof(CEI));
        if (buf == nullptr) {
            *status = U_MEMORY_ALLOCATION_ERROR;
        }
    }
}

// TODO: add a reset or init function so that allocated
//       buffers can be retained & reused.

CEIBuffer::~CEIBuffer() {
    if (buf != defBuf) {
        uprv_free(buf);
    }
}


// Get the CE with the specified index.
//   Index must be in the range
//          n-history_size < index < n+1
//   where n is the largest index to have been fetched by some previous call to this function.
//   The CE value will be UCOL__PROCESSED_NULLORDER at end of input.
//
const CEI *CEIBuffer::get(int32_t index) {
    int i = index % bufSize;

    if (index>=firstIx && index<limitIx) {
        // The request was for an entry already in our buffer.
        //  Just return it.
        return &buf[i];
    }

    // Caller is requesting a new, never accessed before, CE.
    //   Verify that it is the next one in sequence, which is all
    //   that is allowed.
    if (index != limitIx) {
        UPRV_UNREACHABLE_ASSERT;
        // TODO: In ICU 64 the above was changed from U_ASSERT to UPRV_UNREACHABLE,
        // which unconditionally called abort(). However, there were cases in which it
        // was being hit, so it was changed back to U_ASSERT per ICU-20680. In ICU 70,
        // we now use the new UPRV_UNREACHABLE_ASSERT to better indicate the situation.
        // ICU-20792 tracks the follow-up work/further investigation on this.
        return nullptr;
    }

    // Manage the circular CE buffer indexing
    limitIx++;

    if (limitIx - firstIx >= bufSize) {
        // The buffer is full, knock out the lowest-indexed entry.
        firstIx++;
    }

    UErrorCode status = U_ZERO_ERROR;

    buf[i].ce = strSearch->textProcessedIter->nextProcessed(&buf[i].lowIndex, &buf[i].highIndex, &status);

    return &buf[i];
}

// Get the CE with the specified index.
//   Index must be in the range
//          n-history_size < index < n+1
//   where n is the largest index to have been fetched by some previous call to this function.
//   The CE value will be UCOL__PROCESSED_NULLORDER at end of input.
//
const CEI *CEIBuffer::getPrevious(int32_t index) {
    int i = index % bufSize;

    if (index>=firstIx && index<limitIx) {
        // The request was for an entry already in our buffer.
        //  Just return it.
        return &buf[i];
    }

    // Caller is requesting a new, never accessed before, CE.
    //   Verify that it is the next one in sequence, which is all
    //   that is allowed.
    if (index != limitIx) {
        UPRV_UNREACHABLE_ASSERT;
        // TODO: In ICU 64 the above was changed from U_ASSERT to UPRV_UNREACHABLE,
        // which unconditionally called abort(). However, there were cases in which it
        // was being hit, so it was changed back to U_ASSERT per ICU-20680. In ICU 70,
        // we now use the new UPRV_UNREACHABLE_ASSERT to better indicate the situation.
        // ICU-20792 tracks the follow-up work/further investigation on this.
        return nullptr;
    }

    // Manage the circular CE buffer indexing
    limitIx++;

    if (limitIx - firstIx >= bufSize) {
        // The buffer is full, knock out the lowest-indexed entry.
        firstIx++;
    }

    UErrorCode status = U_ZERO_ERROR;

    buf[i].ce = strSearch->textProcessedIter->previousProcessed(&buf[i].lowIndex, &buf[i].highIndex, &status);

    return &buf[i];
}

}

U_NAMESPACE_END


// #define USEARCH_DEBUG

#ifdef USEARCH_DEBUG
#include <stdio.h>
#include <stdlib.h>
#endif

/*
 * Find the next break boundary after startIndex. If the UStringSearch object
 * has an external break iterator, use that. Otherwise use the internal character
 * break iterator.
 */
static int32_t nextBoundaryAfter(UStringSearch *strsrch, int32_t startIndex, UErrorCode &status) {
    if (U_FAILURE(status)) {
        return startIndex;
    }
#if 0
    const UChar *text = strsrch->search->text;
    int32_t textLen   = strsrch->search->textLength;

    U_ASSERT(startIndex>=0);
    U_ASSERT(startIndex<=textLen);

    if (startIndex >= textLen) {
        return startIndex;
    }

    UChar32  c;
    int32_t  i = startIndex;
    U16_NEXT(text, i, textLen, c);

    // If we are on a control character, stop without looking for combining marks.
    //    Control characters do not combine.
    int32_t gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
    if (gcProperty==U_GCB_CONTROL || gcProperty==U_GCB_LF || gcProperty==U_GCB_CR) {
        return i;
    }

    // The initial character was not a control, and can thus accept trailing
    //   combining characters.  Advance over however many of them there are.
    int32_t  indexOfLastCharChecked;
    for (;;) {
        indexOfLastCharChecked = i;
        if (i>=textLen) {
            break;
        }
        U16_NEXT(text, i, textLen, c);
        gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
        if (gcProperty != U_GCB_EXTEND && gcProperty != U_GCB_SPACING_MARK) {
            break;
        }
    }
    return indexOfLastCharChecked;
#elif !UCONFIG_NO_BREAK_ITERATION
    UBreakIterator *breakiterator = getBreakIterator(strsrch, status);
    if (U_FAILURE(status)) {
        return startIndex;
    }

    return ubrk_following(breakiterator, startIndex);
#else
    // **** or should we use the original code? ****
    return startIndex;
#endif

}

/*
 * Returns TRUE if index is on a break boundary. If the UStringSearch
 * has an external break iterator, test using that, otherwise test
 * using the internal character break iterator.
 */
static UBool isBreakBoundary(UStringSearch *strsrch, int32_t index, UErrorCode &status) {
    if (U_FAILURE(status)) {
        return TRUE;
    }
#if 0
    const UChar *text = strsrch->search->text;
    int32_t textLen   = strsrch->search->textLength;

    U_ASSERT(index>=0);
    U_ASSERT(index<=textLen);

    if (index>=textLen || index<=0) {
        return TRUE;
    }

    // If the character at the current index is not a GRAPHEME_EXTEND
    //    then we can not be within a combining sequence.
    UChar32  c;
    U16_GET(text, 0, index, textLen, c);
    int32_t gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
    if (gcProperty != U_GCB_EXTEND && gcProperty != U_GCB_SPACING_MARK) {
        return TRUE;
    }

    // We are at a combining mark.  If the preceding character is anything
    //   except a CONTROL, CR or LF, we are in a combining sequence.
    U16_PREV(text, 0, index, c);
    gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
    UBool combining =  !(gcProperty==U_GCB_CONTROL || gcProperty==U_GCB_LF || gcProperty==U_GCB_CR);
    return !combining;
#elif !UCONFIG_NO_BREAK_ITERATION
    UBreakIterator *breakiterator = getBreakIterator(strsrch, status);
    if (U_FAILURE(status)) {
        return TRUE;
    }

    return ubrk_isBoundary(breakiterator, index);
#else
    // **** or use the original code? ****
    return TRUE;
#endif
}

#if 0
static UBool onBreakBoundaries(const UStringSearch *strsrch, int32_t start, int32_t end, UErrorCode &status)
{
    if (U_FAILURE(status)) {
        return TRUE;
    }

#if !UCONFIG_NO_BREAK_ITERATION
    UBreakIterator *breakiterator = getBreakIterator(strsrch, status);
    if (U_SUCCESS(status)) {
        int32_t startindex = ubrk_first(breakiterator);
        int32_t endindex   = ubrk_last(breakiterator);

        // out-of-range indexes are never boundary positions
        if (start < startindex || start > endindex ||
            end < startindex || end > endindex) {
            return FALSE;
        }

        return ubrk_isBoundary(breakiterator, start) &&
               ubrk_isBoundary(breakiterator, end);
    }
#endif

    return TRUE;
}
#endif

typedef enum {
    U_CE_MATCH = -1,
    U_CE_NO_MATCH = 0,
    U_CE_SKIP_TARG,
    U_CE_SKIP_PATN
} UCompareCEsResult;
#define U_CE_LEVEL2_BASE 0x00000005
#define U_CE_LEVEL3_BASE 0x00050000

static UCompareCEsResult compareCE64s(int64_t targCE, int64_t patCE, int16_t compareType) {
    if (targCE == patCE) {
        return U_CE_MATCH;
    }
    if (compareType == 0) {
        return U_CE_NO_MATCH;
    }
    
    int64_t targCEshifted = targCE >> 32;
    int64_t patCEshifted = patCE >> 32;
    int64_t mask;

    mask = 0xFFFF0000;
    int32_t targLev1 = (int32_t)(targCEshifted & mask);
    int32_t patLev1 = (int32_t)(patCEshifted & mask);
    if ( targLev1 != patLev1 ) {
        if ( targLev1 == 0 ) {
            return U_CE_SKIP_TARG;
        }
        if ( patLev1 == 0 && compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD ) {
            return U_CE_SKIP_PATN;
        }
        return U_CE_NO_MATCH;
    }

    mask = 0x0000FFFF;
    int32_t targLev2 = (int32_t)(targCEshifted & mask);
    int32_t patLev2 = (int32_t)(patCEshifted & mask);
    if ( targLev2 != patLev2 ) {
        if ( targLev2 == 0 ) {
            return U_CE_SKIP_TARG;
        }
        if ( patLev2 == 0 && compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD ) {
            return U_CE_SKIP_PATN;
        }
        return (patLev2 == U_CE_LEVEL2_BASE || (compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD && targLev2 == U_CE_LEVEL2_BASE) )?
            U_CE_MATCH: U_CE_NO_MATCH;
    }
    
    mask = 0xFFFF0000;
    int32_t targLev3 = (int32_t)(targCE & mask);
    int32_t patLev3 = (int32_t)(patCE & mask);
    if ( targLev3 != patLev3 ) {
        return (patLev3 == U_CE_LEVEL3_BASE || (compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD && targLev3 == U_CE_LEVEL3_BASE) )?
            U_CE_MATCH: U_CE_NO_MATCH;
   }

    return U_CE_MATCH;
}

namespace {

UChar32 codePointAt(const USearch &search, int32_t index) {
    if (index < search.textLength) {
        UChar32 c;
        U16_NEXT(search.text, index, search.textLength, c);
        return c;
    }
    return U_SENTINEL;
}

UChar32 codePointBefore(const USearch &search, int32_t index) {
    if (0 < index) {
        UChar32 c;
        U16_PREV(search.text, 0, index, c);
        return c;
    }
    return U_SENTINEL;
}

}  // namespace

U_CAPI UBool U_EXPORT2 usearch_search(UStringSearch  *strsrch,
                                       int32_t        startIdx,
                                       int32_t        *matchStart,
                                       int32_t        *matchLimit,
                                       UErrorCode     *status)
{
    if (U_FAILURE(*status)) {
        return FALSE;
    }

    // TODO:  reject search patterns beginning with a combining char.

#ifdef USEARCH_DEBUG
    if (getenv("USEARCH_DEBUG") != nullptr) {
        printf("Pattern CEs\n");
        for (int ii=0; ii<strsrch->pattern.cesLength; ii++) {
            printf(" %8x", strsrch->pattern.ces[ii]);
        }
        printf("\n");
    }

#endif
    // Input parameter sanity check.
    //  TODO:  should input indices clip to the text length
    //         in the same way that UText does.
    if(strsrch->pattern.cesLength == 0         ||
       startIdx < 0                           ||
       startIdx > strsrch->search->textLength ||
       strsrch->pattern.ces == nullptr) {
           *status = U_ILLEGAL_ARGUMENT_ERROR;
           return FALSE;
    }

    if (strsrch->pattern.pces == nullptr) {
        initializePatternPCETable(strsrch, status);
    }

    ucol_setOffset(strsrch->textIter, startIdx, status);
    CEIBuffer ceb(strsrch, status);

    // An out-of-memory (OOM) failure can occur in the initializePatternPCETable function
    // or CEIBuffer constructor above, so we need to check the status.
    if (U_FAILURE(*status)) {
        return FALSE;
    }

    int32_t    targetIx = 0;
    const CEI *targetCEI = nullptr;
    int32_t    patIx;
    UBool      found;

    int32_t  mStart = -1;
    int32_t  mLimit = -1;
    int32_t  minLimit;
    int32_t  maxLimit;


    // Outer loop moves over match starting positions in the
    //      target CE space.
    // Here we see the target as a sequence of collation elements, resulting from the following:
    // 1. Target characters were decomposed, and (if appropriate) other compressions and expansions are applied
    //    (for example, digraphs such as IJ may be broken into two characters).
    // 2. An int64_t CE weight is determined for each resulting unit (high 16 bits are primary strength, next
    //    16 bits are secondary, next 16 (the high 16 bits of the low 32-bit half) are tertiary. Any of these
    //    fields that are for strengths below that of the collator are set to 0. If this makes the int64_t
    //    CE weight 0 (as for a combining diacritic with secondary weight when the collator strength is primary),
    //    then the CE is deleted, so the following code sees only CEs that are relevant.
    // For each CE, the lowIndex and highIndex correspond to where this CE begins and ends in the original text.
    // If lowIndex==highIndex, either the CE resulted from an expansion/decomposition of one of the original text
    // characters, or the CE marks the limit of the target text (in which case the CE weight is UCOL_PROCESSED_NULLORDER).
    //
    for(targetIx=0; ; targetIx++)
    {
        found = TRUE;
        //  Inner loop checks for a match beginning at each
        //  position from the outer loop.
        int32_t targetIxOffset = 0;
        int64_t patCE = 0;
        // For targetIx > 0, this ceb.get gets a CE that is as far back in the ring buffer
        // (compared to the last CE fetched for the previous targetIx value) as we need to go
        // for this targetIx value, so if it is non-nullptr then other ceb.get calls should be OK.
        const CEI *firstCEI = ceb.get(targetIx);
        if (firstCEI == nullptr) {
            *status = U_INTERNAL_PROGRAM_ERROR;
            found = FALSE;
            break;
        }
        
        for (patIx=0; patIx<strsrch->pattern.pcesLength; patIx++) {
            patCE = strsrch->pattern.pces[patIx];
            targetCEI = ceb.get(targetIx+patIx+targetIxOffset);
            //  Compare CE from target string with CE from the pattern.
            //    Note that the target CE will be UCOL_PROCESSED_NULLORDER if we reach the end of input,
            //    which will fail the compare, below.
            UCompareCEsResult ceMatch = compareCE64s(targetCEI->ce, patCE, strsrch->search->elementComparisonType);
            if ( ceMatch == U_CE_NO_MATCH ) {
                found = FALSE;
                break;
            } else if ( ceMatch > U_CE_NO_MATCH ) {
                if ( ceMatch == U_CE_SKIP_TARG ) {
                    // redo with same patCE, next targCE
                    patIx--;
                    targetIxOffset++;
                } else { // ceMatch == U_CE_SKIP_PATN
                    // redo with same targCE, next patCE
                    targetIxOffset--;
                }
            }
        }
        targetIxOffset += strsrch->pattern.pcesLength; // this is now the offset in target CE space to end of the match so far

        if (!found && ((targetCEI == nullptr) || (targetCEI->ce != UCOL_PROCESSED_NULLORDER))) {
            // No match at this targetIx.  Try again at the next.
            continue;
        }

        if (!found) {
            // No match at all, we have run off the end of the target text.
            break;
        }


        // We have found a match in CE space.
        // Now determine the bounds in string index space.
        //  There still is a chance of match failure if the CE range not correspond to
        //     an acceptable character range.
        //
        const CEI *lastCEI  = ceb.get(targetIx + targetIxOffset - 1);

        mStart   = firstCEI->lowIndex;
        minLimit = lastCEI->lowIndex;

        // Look at the CE following the match.  If it is UCOL_NULLORDER the match
        //   extended to the end of input, and the match is good.

        // Look at the high and low indices of the CE following the match. If
        // they are the same it means one of two things:
        //    1. The match extended to the last CE from the target text, which is OK, or
        //    2. The last CE that was part of the match is in an expansion that extends
        //       to the first CE after the match. In this case, we reject the match.
        const CEI *nextCEI = 0;
        if (strsrch->search->elementComparisonType == 0) {
            nextCEI  = ceb.get(targetIx + targetIxOffset);
            maxLimit = nextCEI->lowIndex;
            if (nextCEI->lowIndex == nextCEI->highIndex && nextCEI->ce != UCOL_PROCESSED_NULLORDER) {
                found = FALSE;
            }
        } else {
            for ( ; ; ++targetIxOffset ) {
                nextCEI = ceb.get(targetIx + targetIxOffset);
                maxLimit = nextCEI->lowIndex;
                // If we are at the end of the target too, match succeeds
                if (  nextCEI->ce == UCOL_PROCESSED_NULLORDER ) {
                    break;
                }
                // As long as the next CE has primary weight of 0,
                // it is part of the last target element matched by the pattern;
                // make sure it can be part of a match with the last patCE
                if ( (((nextCEI->ce) >> 32) & 0xFFFF0000UL) == 0 ) {
                    UCompareCEsResult ceMatch = compareCE64s(nextCEI->ce, patCE, strsrch->search->elementComparisonType);
                    if ( ceMatch == U_CE_NO_MATCH || ceMatch == U_CE_SKIP_PATN ) {
                        found = FALSE;
                        break;
                    }
                // If lowIndex == highIndex, this target CE is part of an expansion of the last matched
                // target element, but it has non-zero primary weight => match fails
                } else if ( nextCEI->lowIndex == nextCEI->highIndex ) {
                    found = false;
                    break;
                // Else the target CE is not part of an expansion of the last matched element, match succeeds
                } else {
                    break;
                }
            }
        }


        // Check for the start of the match being within a combining sequence.
        //   This can happen if the pattern itself begins with a combining char, and
        //   the match found combining marks in the target text that were attached
        //    to something else.
        //   This type of match should be rejected for not completely consuming a
        //   combining sequence.
        if (!isBreakBoundary(strsrch, mStart, *status)) {
            found = FALSE;
        }
        if (U_FAILURE(*status)) {
            break;
        }

        // Check for the start of the match being within an Collation Element Expansion,
        //   meaning that the first char of the match is only partially matched.
        //   With expansions, the first CE will report the index of the source
        //   character, and all subsequent (expansions) CEs will report the source index of the
        //    _following_ character.
        int32_t secondIx = firstCEI->highIndex;
        if (mStart == secondIx) {
            found = FALSE;
        }

        // Allow matches to end in the middle of a grapheme cluster if the following
        // conditions are met; this is needed to make prefix search work properly in
        // Indic, see #11750
        // * the default breakIter is being used
        // * the next collation element after this combining sequence
        //   - has non-zero primary weight
        //   - corresponds to a separate character following the one at end of the current match
        //   (the second of these conditions, and perhaps both, may be redundant given the
        //   subsequent check for normalization boundary; however they are likely much faster
        //   tests in any case)
        // * the match limit is a normalization boundary
        UBool allowMidclusterMatch = FALSE;
        if (strsrch->search->text != nullptr && strsrch->search->textLength > maxLimit) {
            allowMidclusterMatch =
                    strsrch->search->breakIter == nullptr &&
                    nextCEI != nullptr && (((nextCEI->ce) >> 32) & 0xFFFF0000UL) != 0 &&
                    maxLimit >= lastCEI->highIndex && nextCEI->highIndex > maxLimit &&
                    (strsrch->nfd->hasBoundaryBefore(codePointAt(*strsrch->search, maxLimit)) ||
                        strsrch->nfd->hasBoundaryAfter(codePointBefore(*strsrch->search, maxLimit)));
        }
        // If those conditions are met, then:
        // * do NOT advance the candidate match limit (mLimit) to a break boundary; however
        //   the match limit may be backed off to a previous break boundary. This handles
        //   cases in which mLimit includes target characters that are ignorable with current
        //   settings (such as space) and which extend beyond the pattern match.
        // * do NOT require that end of the combining sequence not extend beyond the match in CE space
        // * do NOT require that match limit be on a breakIter boundary

        //  Advance the match end position to the first acceptable match boundary.
        //    This advances the index over any combining characters.
        mLimit = maxLimit;
        if (minLimit < maxLimit) {
            // When the last CE's low index is same with its high index, the CE is likely
            // a part of expansion. In this case, the index is located just after the
            // character corresponding to the CEs compared above. If the index is right
            // at the break boundary, move the position to the next boundary will result
            // incorrect match length when there are ignorable characters exist between
            // the position and the next character produces CE(s). See ticket#8482.
            if (minLimit == lastCEI->highIndex && isBreakBoundary(strsrch, minLimit, *status)) {
                mLimit = minLimit;
            } else {
                int32_t nba = nextBoundaryAfter(strsrch, minLimit, *status);
                // Note that we can have nba < maxLimit && nba >= minLImit, in which
                // case we want to set mLimit to nba regardless of allowMidclusterMatch
                // (i.e. we back off mLimit to the previous breakIterator boundary).
                if (nba >= lastCEI->highIndex && (!allowMidclusterMatch || nba < maxLimit)) {
                    mLimit = nba;
                }
            }
        }

        if (U_FAILURE(*status)) {
            break;
        }

    #ifdef USEARCH_DEBUG
        if (getenv("USEARCH_DEBUG") != nullptr) {
            printf("minLimit, maxLimit, mLimit = %d, %d, %d\n", minLimit, maxLimit, mLimit);
        }
    #endif

        if (!allowMidclusterMatch) {
            // If advancing to the end of a combining sequence in character indexing space
            //   advanced us beyond the end of the match in CE space, reject this match.
            if (mLimit > maxLimit) {
                found = FALSE;
            }

            if (!isBreakBoundary(strsrch, mLimit, *status)) {
                found = FALSE;
            }
            if (U_FAILURE(*status)) {
                break;
            }
        }

        if (! checkIdentical(strsrch, mStart, mLimit)) {
            found = FALSE;
        }

        if (found) {
            break;
        }
    }

    #ifdef USEARCH_DEBUG
    if (getenv("USEARCH_DEBUG") != nullptr) {
        printf("Target CEs [%d .. %d]\n", ceb.firstIx, ceb.limitIx);
        int32_t  lastToPrint = ceb.limitIx+2;
        for (int ii=ceb.firstIx; ii<lastToPrint; ii++) {
            printf("%8x@%d ", ceb.get(ii)->ce, ceb.get(ii)->srcIndex);
        }
        printf("\n%s\n", found? "match found" : "no match");
    }
    #endif

    // All Done.  Store back the match bounds to the caller.
    //

    if (U_FAILURE(*status)) {
        found = FALSE; // No match if a failure occured.
    }

    if (found==FALSE) {
        mLimit = -1;
        mStart = -1;
    }

    if (matchStart != nullptr) {
        *matchStart= mStart;
    }

    if (matchLimit != nullptr) {
        *matchLimit = mLimit;
    }

    return found;
}

U_CAPI UBool U_EXPORT2 usearch_searchBackwards(UStringSearch  *strsrch,
                                                int32_t        startIdx,
                                                int32_t        *matchStart,
                                                int32_t        *matchLimit,
                                                UErrorCode     *status)
{
    if (U_FAILURE(*status)) {
        return FALSE;
    }

    // TODO:  reject search patterns beginning with a combining char.

#ifdef USEARCH_DEBUG
    if (getenv("USEARCH_DEBUG") != nullptr) {
        printf("Pattern CEs\n");
        for (int ii=0; ii<strsrch->pattern.cesLength; ii++) {
            printf(" %8x", strsrch->pattern.ces[ii]);
        }
        printf("\n");
    }

#endif
    // Input parameter sanity check.
    //  TODO:  should input indices clip to the text length
    //         in the same way that UText does.
    if(strsrch->pattern.cesLength == 0        ||
       startIdx < 0                           ||
       startIdx > strsrch->search->textLength ||
       strsrch->pattern.ces == nullptr) {
           *status = U_ILLEGAL_ARGUMENT_ERROR;
           return FALSE;
    }

    if (strsrch->pattern.pces == nullptr) {
        initializePatternPCETable(strsrch, status);
    }

    CEIBuffer ceb(strsrch, status);
    int32_t    targetIx = 0;

    /*
     * Pre-load the buffer with the CE's for the grapheme
     * after our starting position so that we're sure that
     * we can look at the CE following the match when we
     * check the match boundaries.
     *
     * This will also pre-fetch the first CE that we'll
     * consider for the match.
     */
    if (startIdx < strsrch->search->textLength) {
        UBreakIterator *breakiterator = getBreakIterator(strsrch, *status);
        if (U_FAILURE(*status)) {
            return FALSE;
        }
        int32_t next = ubrk_following(breakiterator, startIdx);

        ucol_setOffset(strsrch->textIter, next, status);

        for (targetIx = 0; ; targetIx += 1) {
            if (ceb.getPrevious(targetIx)->lowIndex < startIdx) {
                break;
            }
        }
    } else {
        ucol_setOffset(strsrch->textIter, startIdx, status);
    }

    // An out-of-memory (OOM) failure can occur above, so we need to check the status.
    if (U_FAILURE(*status)) {
        return FALSE;
    }

    const CEI *targetCEI = nullptr;
    int32_t    patIx;
    UBool      found;

    int32_t  limitIx = targetIx;
    int32_t  mStart = -1;
    int32_t  mLimit = -1;
    int32_t  minLimit;
    int32_t  maxLimit;


    // Outer loop moves over match starting positions in the
    //      target CE space.
    // Here, targetIx values increase toward the beginning of the base text (i.e. we get the text CEs in reverse order).
    // But  patIx is 0 at the beginning of the pattern and increases toward the end.
    // So this loop performs a comparison starting with the end of pattern, and prcessd toward the beginning of the pattern
    // and the beginning of the base text.
    for(targetIx = limitIx; ; targetIx += 1)
    {
        found = TRUE;
        // For targetIx > limitIx, this ceb.getPrevious gets a CE that is as far back in the ring buffer
        // (compared to the last CE fetched for the previous targetIx value) as we need to go
        // for this targetIx value, so if it is non-nullptr then other ceb.getPrevious calls should be OK.
        const CEI *lastCEI  = ceb.getPrevious(targetIx);
        if (lastCEI == nullptr) {
            *status = U_INTERNAL_PROGRAM_ERROR;
            found = FALSE;
             break;
        }
        //  Inner loop checks for a match beginning at each
        //  position from the outer loop.
        int32_t targetIxOffset = 0;
        for (patIx = strsrch->pattern.pcesLength - 1; patIx >= 0; patIx -= 1) {
            int64_t patCE = strsrch->pattern.pces[patIx];

            targetCEI = ceb.getPrevious(targetIx + strsrch->pattern.pcesLength - 1 - patIx + targetIxOffset);
            //  Compare CE from target string with CE from the pattern.
            //    Note that the target CE will be UCOL_NULLORDER if we reach the end of input,
            //    which will fail the compare, below.
            UCompareCEsResult ceMatch = compareCE64s(targetCEI->ce, patCE, strsrch->search->elementComparisonType);
            if ( ceMatch == U_CE_NO_MATCH ) {
                found = FALSE;
                break;
            } else if ( ceMatch > U_CE_NO_MATCH ) {
                if ( ceMatch == U_CE_SKIP_TARG ) {
                    // redo with same patCE, next targCE
                    patIx++;
                    targetIxOffset++;
                } else { // ceMatch == U_CE_SKIP_PATN
                    // redo with same targCE, next patCE
                    targetIxOffset--;
                }
            }
        }

        if (!found && ((targetCEI == nullptr) || (targetCEI->ce != UCOL_PROCESSED_NULLORDER))) {
            // No match at this targetIx.  Try again at the next.
            continue;
        }

        if (!found) {
            // No match at all, we have run off the end of the target text.
            break;
        }


        // We have found a match in CE space.
        // Now determine the bounds in string index space.
        //  There still is a chance of match failure if the CE range not correspond to
        //     an acceptable character range.
        //
        const CEI *firstCEI = ceb.getPrevious(targetIx + strsrch->pattern.pcesLength - 1 + targetIxOffset);
        mStart   = firstCEI->lowIndex;

        // Check for the start of the match being within a combining sequence.
        //   This can happen if the pattern itself begins with a combining char, and
        //   the match found combining marks in the target text that were attached
        //    to something else.
        //   This type of match should be rejected for not completely consuming a
        //   combining sequence.
        if (!isBreakBoundary(strsrch, mStart, *status)) {
            found = FALSE;
        }
        if (U_FAILURE(*status)) {
            break;
        }

        // Look at the high index of the first CE in the match. If it's the same as the
        // low index, the first CE in the match is in the middle of an expansion.
        if (mStart == firstCEI->highIndex) {
            found = FALSE;
        }


        minLimit = lastCEI->lowIndex;

        if (targetIx > 0) {
            // Look at the CE following the match.  If it is UCOL_NULLORDER the match
            //   extended to the end of input, and the match is good.

            // Look at the high and low indices of the CE following the match. If
            // they are the same it means one of two things:
            //    1. The match extended to the last CE from the target text, which is OK, or
            //    2. The last CE that was part of the match is in an expansion that extends
            //       to the first CE after the match. In this case, we reject the match.
            const CEI *nextCEI  = ceb.getPrevious(targetIx - 1);

            if (nextCEI->lowIndex == nextCEI->highIndex && nextCEI->ce != UCOL_PROCESSED_NULLORDER) {
                found = FALSE;
            }

            mLimit = maxLimit = nextCEI->lowIndex;

            // Allow matches to end in the middle of a grapheme cluster if the following
            // conditions are met; this is needed to make prefix search work properly in
            // Indic, see #11750
            // * the default breakIter is being used
            // * the next collation element after this combining sequence
            //   - has non-zero primary weight
            //   - corresponds to a separate character following the one at end of the current match
            //   (the second of these conditions, and perhaps both, may be redundant given the
            //   subsequent check for normalization boundary; however they are likely much faster
            //   tests in any case)
            // * the match limit is a normalization boundary
            UBool allowMidclusterMatch = FALSE;
            if (strsrch->search->text != nullptr && strsrch->search->textLength > maxLimit) {
                allowMidclusterMatch =
                        strsrch->search->breakIter == nullptr &&
                        nextCEI != nullptr && (((nextCEI->ce) >> 32) & 0xFFFF0000UL) != 0 &&
                        maxLimit >= lastCEI->highIndex && nextCEI->highIndex > maxLimit &&
                        (strsrch->nfd->hasBoundaryBefore(codePointAt(*strsrch->search, maxLimit)) ||
                            strsrch->nfd->hasBoundaryAfter(codePointBefore(*strsrch->search, maxLimit)));
            }
            // If those conditions are met, then:
            // * do NOT advance the candidate match limit (mLimit) to a break boundary; however
            //   the match limit may be backed off to a previous break boundary. This handles
            //   cases in which mLimit includes target characters that are ignorable with current
            //   settings (such as space) and which extend beyond the pattern match.
            // * do NOT require that end of the combining sequence not extend beyond the match in CE space
            // * do NOT require that match limit be on a breakIter boundary

            //  Advance the match end position to the first acceptable match boundary.
            //    This advances the index over any combining characters.
            if (minLimit < maxLimit) {
                int32_t nba = nextBoundaryAfter(strsrch, minLimit, *status);
                // Note that we can have nba < maxLimit && nba >= minLImit, in which
                // case we want to set mLimit to nba regardless of allowMidclusterMatch
                // (i.e. we back off mLimit to the previous breakIterator boundary).
                if (nba >= lastCEI->highIndex && (!allowMidclusterMatch || nba < maxLimit)) {
                    mLimit = nba;
                }
            }

            if (!allowMidclusterMatch) {
                // If advancing to the end of a combining sequence in character indexing space
                //   advanced us beyond the end of the match in CE space, reject this match.
                if (mLimit > maxLimit) {
                    found = FALSE;
                }

                // Make sure the end of the match is on a break boundary
                if (!isBreakBoundary(strsrch, mLimit, *status)) {
                    found = FALSE;
                }
                if (U_FAILURE(*status)) {
                    break;
                }
            }

        } else {
            // No non-ignorable CEs after this point.
            // The maximum position is detected by boundary after
            // the last non-ignorable CE. Combining sequence
            // across the start index will be truncated.
            int32_t nba = nextBoundaryAfter(strsrch, minLimit, *status);
            mLimit = maxLimit = (nba > 0) && (startIdx > nba) ? nba : startIdx;
        }

    #ifdef USEARCH_DEBUG
        if (getenv("USEARCH_DEBUG") != nullptr) {
            printf("minLimit, maxLimit, mLimit = %d, %d, %d\n", minLimit, maxLimit, mLimit);
        }
    #endif


        if (! checkIdentical(strsrch, mStart, mLimit)) {
            found = FALSE;
        }

        if (found) {
            break;
        }
    }

    #ifdef USEARCH_DEBUG
    if (getenv("USEARCH_DEBUG") != nullptr) {
        printf("Target CEs [%d .. %d]\n", ceb.firstIx, ceb.limitIx);
        int32_t  lastToPrint = ceb.limitIx+2;
        for (int ii=ceb.firstIx; ii<lastToPrint; ii++) {
            printf("%8x@%d ", ceb.get(ii)->ce, ceb.get(ii)->srcIndex);
        }
        printf("\n%s\n", found? "match found" : "no match");
    }
    #endif

    // All Done.  Store back the match bounds to the caller.
    //

    if (U_FAILURE(*status)) {
        found = FALSE; // No match if a failure occured.
    }

    if (found==FALSE) {
        mLimit = -1;
        mStart = -1;
    }

    if (matchStart != nullptr) {
        *matchStart= mStart;
    }

    if (matchLimit != nullptr) {
        *matchLimit = mLimit;
    }

    return found;
}

// internal use methods declared in usrchimp.h -----------------------------

UBool usearch_handleNextExact(UStringSearch *strsrch, UErrorCode *status)
{
    if (U_FAILURE(*status)) {
        setMatchNotFound(strsrch, *status);
        return FALSE;
    }

    int32_t textOffset = ucol_getOffset(strsrch->textIter);
    int32_t start = -1;
    int32_t end = -1;

    if (usearch_search(strsrch, textOffset, &start, &end, status)) {
        strsrch->search->matchedIndex  = start;
        strsrch->search->matchedLength = end - start;
        return TRUE;
    } else {
        setMatchNotFound(strsrch, *status);
        return FALSE;
    }
}

UBool usearch_handleNextCanonical(UStringSearch *strsrch, UErrorCode *status)
{
    if (U_FAILURE(*status)) {
        setMatchNotFound(strsrch, *status);
        return FALSE;
    }

    int32_t textOffset = ucol_getOffset(strsrch->textIter);
    int32_t start = -1;
    int32_t end = -1;

    if (usearch_search(strsrch, textOffset, &start, &end, status)) {
        strsrch->search->matchedIndex  = start;
        strsrch->search->matchedLength = end - start;
        return TRUE;
    } else {
        setMatchNotFound(strsrch, *status);
        return FALSE;
    }
}

UBool usearch_handlePreviousExact(UStringSearch *strsrch, UErrorCode *status)
{
    if (U_FAILURE(*status)) {
        setMatchNotFound(strsrch, *status);
        return FALSE;
    }

    int32_t textOffset;

    if (strsrch->search->isOverlap) {
        if (strsrch->search->matchedIndex != USEARCH_DONE) {
            textOffset = strsrch->search->matchedIndex + strsrch->search->matchedLength - 1;
        } else {
            // move the start position at the end of possible match
            initializePatternPCETable(strsrch, status);
            if (!initTextProcessedIter(strsrch, status)) {
                setMatchNotFound(strsrch, *status);
                return FALSE;
            }
            for (int32_t nPCEs = 0; nPCEs < strsrch->pattern.pcesLength - 1; nPCEs++) {
                int64_t pce = strsrch->textProcessedIter->nextProcessed(nullptr, nullptr, status);
                if (pce == UCOL_PROCESSED_NULLORDER) {
                    // at the end of the text
                    break;
                }
            }
            if (U_FAILURE(*status)) {
                setMatchNotFound(strsrch, *status);
                return FALSE;
            }
            textOffset = ucol_getOffset(strsrch->textIter);
        }
    } else {
        textOffset = ucol_getOffset(strsrch->textIter);
    }

    int32_t start = -1;
    int32_t end = -1;

    if (usearch_searchBackwards(strsrch, textOffset, &start, &end, status)) {
        strsrch->search->matchedIndex = start;
        strsrch->search->matchedLength = end - start;
        return TRUE;
    } else {
        setMatchNotFound(strsrch, *status);
        return FALSE;
    }
}

UBool usearch_handlePreviousCanonical(UStringSearch *strsrch,
                                      UErrorCode    *status)
{
    if (U_FAILURE(*status)) {
        setMatchNotFound(strsrch, *status);
        return FALSE;
    }

    int32_t textOffset;

    if (strsrch->search->isOverlap) {
        if (strsrch->search->matchedIndex != USEARCH_DONE) {
            textOffset = strsrch->search->matchedIndex + strsrch->search->matchedLength - 1;
        } else {
            // move the start position at the end of possible match
            initializePatternPCETable(strsrch, status);
            if (!initTextProcessedIter(strsrch, status)) {
                setMatchNotFound(strsrch, *status);
                return FALSE;
            }
            for (int32_t nPCEs = 0; nPCEs < strsrch->pattern.pcesLength - 1; nPCEs++) {
                int64_t pce = strsrch->textProcessedIter->nextProcessed(nullptr, nullptr, status);
                if (pce == UCOL_PROCESSED_NULLORDER) {
                    // at the end of the text
                    break;
                }
            }
            if (U_FAILURE(*status)) {
                setMatchNotFound(strsrch, *status);
                return FALSE;
            }
            textOffset = ucol_getOffset(strsrch->textIter);
        }
    } else {
        textOffset = ucol_getOffset(strsrch->textIter);
    }

    int32_t start = -1;
    int32_t end = -1;

    if (usearch_searchBackwards(strsrch, textOffset, &start, &end, status)) {
        strsrch->search->matchedIndex = start;
        strsrch->search->matchedLength = end - start;
        return TRUE;
    } else {
        setMatchNotFound(strsrch, *status);
        return FALSE;
    }
}

#endif /* #if !UCONFIG_NO_COLLATION */