Restoring authorship annotation for <mcheshkov@yandex-team.ru>. Commit 1 of 2.

1 files changed, 794 insertions, 794 deletions

diff --git a/contrib/libs/icu/common/localematcher.cpp b/contrib/libs/icu/common/localematcher.cpp
index 85db8c8bf3..97fff49b92 100644
--- a/contrib/libs/icu/common/localematcher.cpp
+++ b/contrib/libs/icu/common/localematcher.cpp
@@ -1,794 +1,794 @@
-// © 2019 and later: Unicode, Inc. and others.
-// License & terms of use: http://www.unicode.org/copyright.html#License
-
-// localematcher.cpp
-// created: 2019may08 Markus W. Scherer
-
-#ifndef __LOCMATCHER_H__
-#define __LOCMATCHER_H__
-
-#include "unicode/utypes.h"
-#include "unicode/localebuilder.h"
-#include "unicode/localematcher.h"
-#include "unicode/locid.h"
-#include "unicode/stringpiece.h"
-#include "unicode/uloc.h"
-#include "unicode/uobject.h"
-#include "cstring.h"
-#include "localeprioritylist.h"
-#include "loclikelysubtags.h"
-#include "locdistance.h"
-#include "lsr.h"
-#include "uassert.h"
-#include "uhash.h"
-#include "ustr_imp.h"
-#include "uvector.h"
-
-#define UND_LSR LSR("und", "", "", LSR::EXPLICIT_LSR)
-
-/**
- * Indicator for the lifetime of desired-locale objects passed into the LocaleMatcher.
- *
- * @draft ICU 65
- */
-enum ULocMatchLifetime {
-    /**
-     * Locale objects are temporary.
-     * The matcher will make a copy of a locale that will be used beyond one function call.
-     *
-     * @draft ICU 65
-     */
-    ULOCMATCH_TEMPORARY_LOCALES,
-    /**
-     * Locale objects are stored at least as long as the matcher is used.
-     * The matcher will keep only a pointer to a locale that will be used beyond one function call,
-     * avoiding a copy.
-     *
-     * @draft ICU 65
-     */
-    ULOCMATCH_STORED_LOCALES  // TODO: permanent? cached? clone?
-};
-#ifndef U_IN_DOXYGEN
-typedef enum ULocMatchLifetime ULocMatchLifetime;
-#endif
-
-U_NAMESPACE_BEGIN
-
-LocaleMatcher::Result::Result(LocaleMatcher::Result &&src) U_NOEXCEPT :
-        desiredLocale(src.desiredLocale),
-        supportedLocale(src.supportedLocale),
-        desiredIndex(src.desiredIndex),
-        supportedIndex(src.supportedIndex),
-        desiredIsOwned(src.desiredIsOwned) {
-    if (desiredIsOwned) {
-        src.desiredLocale = nullptr;
-        src.desiredIndex = -1;
-        src.desiredIsOwned = FALSE;
-    }
-}
-
-LocaleMatcher::Result::~Result() {
-    if (desiredIsOwned) {
-        delete desiredLocale;
-    }
-}
-
-LocaleMatcher::Result &LocaleMatcher::Result::operator=(LocaleMatcher::Result &&src) U_NOEXCEPT {
-    this->~Result();
-
-    desiredLocale = src.desiredLocale;
-    supportedLocale = src.supportedLocale;
-    desiredIndex = src.desiredIndex;
-    supportedIndex = src.supportedIndex;
-    desiredIsOwned = src.desiredIsOwned;
-
-    if (desiredIsOwned) {
-        src.desiredLocale = nullptr;
-        src.desiredIndex = -1;
-        src.desiredIsOwned = FALSE;
-    }
-    return *this;
-}
-
-Locale LocaleMatcher::Result::makeResolvedLocale(UErrorCode &errorCode) const {
-    if (U_FAILURE(errorCode) || supportedLocale == nullptr) {
-        return Locale::getRoot();
-    }
-    const Locale *bestDesired = getDesiredLocale();
-    if (bestDesired == nullptr || *supportedLocale == *bestDesired) {
-        return *supportedLocale;
-    }
-    LocaleBuilder b;
-    b.setLocale(*supportedLocale);
-
-    // Copy the region from bestDesired, if there is one.
-    const char *region = bestDesired->getCountry();
-    if (*region != 0) {
-        b.setRegion(region);
-    }
-
-    // Copy the variants from bestDesired, if there are any.
-    // Note that this will override any supportedLocale variants.
-    // For example, "sco-ulster-fonipa" + "...-fonupa" => "sco-fonupa" (replacing ulster).
-    const char *variants = bestDesired->getVariant();
-    if (*variants != 0) {
-        b.setVariant(variants);
-    }
-
-    // Copy the extensions from bestDesired, if there are any.
-    // C++ note: The following note, copied from Java, may not be true,
-    // as long as C++ copies by legacy ICU keyword, not by extension singleton.
-    // Note that this will override any supportedLocale extensions.
-    // For example, "th-u-nu-latn-ca-buddhist" + "...-u-nu-native" => "th-u-nu-native"
-    // (replacing calendar).
-    b.copyExtensionsFrom(*bestDesired, errorCode);
-    return b.build(errorCode);
-}
-
-LocaleMatcher::Builder::Builder(LocaleMatcher::Builder &&src) U_NOEXCEPT :
-        errorCode_(src.errorCode_),
-        supportedLocales_(src.supportedLocales_),
-        thresholdDistance_(src.thresholdDistance_),
-        demotion_(src.demotion_),
-        defaultLocale_(src.defaultLocale_),
-        favor_(src.favor_),
-        direction_(src.direction_) {
-    src.supportedLocales_ = nullptr;
-    src.defaultLocale_ = nullptr;
-}
-
-LocaleMatcher::Builder::~Builder() {
-    delete supportedLocales_;
-    delete defaultLocale_;
-}
-
-LocaleMatcher::Builder &LocaleMatcher::Builder::operator=(LocaleMatcher::Builder &&src) U_NOEXCEPT {
-    this->~Builder();
-
-    errorCode_ = src.errorCode_;
-    supportedLocales_ = src.supportedLocales_;
-    thresholdDistance_ = src.thresholdDistance_;
-    demotion_ = src.demotion_;
-    defaultLocale_ = src.defaultLocale_;
-    favor_ = src.favor_;
-    direction_ = src.direction_;
-
-    src.supportedLocales_ = nullptr;
-    src.defaultLocale_ = nullptr;
-    return *this;
-}
-
-void LocaleMatcher::Builder::clearSupportedLocales() {
-    if (supportedLocales_ != nullptr) {
-        supportedLocales_->removeAllElements();
-    }
-}
-
-bool LocaleMatcher::Builder::ensureSupportedLocaleVector() {
-    if (U_FAILURE(errorCode_)) { return false; }
-    if (supportedLocales_ != nullptr) { return true; }
-    supportedLocales_ = new UVector(uprv_deleteUObject, nullptr, errorCode_);
-    if (U_FAILURE(errorCode_)) { return false; }
-    if (supportedLocales_ == nullptr) {
-        errorCode_ = U_MEMORY_ALLOCATION_ERROR;
-        return false;
-    }
-    return true;
-}
-
-LocaleMatcher::Builder &LocaleMatcher::Builder::setSupportedLocalesFromListString(
-        StringPiece locales) {
-    LocalePriorityList list(locales, errorCode_);
-    if (U_FAILURE(errorCode_)) { return *this; }
-    clearSupportedLocales();
-    if (!ensureSupportedLocaleVector()) { return *this; }
-    int32_t length = list.getLengthIncludingRemoved();
-    for (int32_t i = 0; i < length; ++i) {
-        Locale *locale = list.orphanLocaleAt(i);
-        if (locale == nullptr) { continue; }
-        supportedLocales_->addElement(locale, errorCode_);
-        if (U_FAILURE(errorCode_)) {
-            delete locale;
-            break;
-        }
-    }
-    return *this;
-}
-
-LocaleMatcher::Builder &LocaleMatcher::Builder::setSupportedLocales(Locale::Iterator &locales) {
-    if (U_FAILURE(errorCode_)) { return *this; }
-    clearSupportedLocales();
-    if (!ensureSupportedLocaleVector()) { return *this; }
-    while (locales.hasNext()) {
-        const Locale &locale = locales.next();
-        Locale *clone = locale.clone();
-        if (clone == nullptr) {
-            errorCode_ = U_MEMORY_ALLOCATION_ERROR;
-            break;
-        }
-        supportedLocales_->addElement(clone, errorCode_);
-        if (U_FAILURE(errorCode_)) {
-            delete clone;
-            break;
-        }
-    }
-    return *this;
-}
-
-LocaleMatcher::Builder &LocaleMatcher::Builder::addSupportedLocale(const Locale &locale) {
-    if (!ensureSupportedLocaleVector()) { return *this; }
-    Locale *clone = locale.clone();
-    if (clone == nullptr) {
-        errorCode_ = U_MEMORY_ALLOCATION_ERROR;
-        return *this;
-    }
-    supportedLocales_->addElement(clone, errorCode_);
-    if (U_FAILURE(errorCode_)) {
-        delete clone;
-    }
-    return *this;
-}
-
-LocaleMatcher::Builder &LocaleMatcher::Builder::setDefaultLocale(const Locale *defaultLocale) {
-    if (U_FAILURE(errorCode_)) { return *this; }
-    Locale *clone = nullptr;
-    if (defaultLocale != nullptr) {
-        clone = defaultLocale->clone();
-        if (clone == nullptr) {
-            errorCode_ = U_MEMORY_ALLOCATION_ERROR;
-            return *this;
-        }
-    }
-    delete defaultLocale_;
-    defaultLocale_ = clone;
-    return *this;
-}
-
-LocaleMatcher::Builder &LocaleMatcher::Builder::setFavorSubtag(ULocMatchFavorSubtag subtag) {
-    if (U_FAILURE(errorCode_)) { return *this; }
-    favor_ = subtag;
-    return *this;
-}
-
-LocaleMatcher::Builder &LocaleMatcher::Builder::setDemotionPerDesiredLocale(ULocMatchDemotion demotion) {
-    if (U_FAILURE(errorCode_)) { return *this; }
-    demotion_ = demotion;
-    return *this;
-}
-
-#if 0
-/**
- * <i>Internal only!</i>
- *
- * @param thresholdDistance the thresholdDistance to set, with -1 = default
- * @return this Builder object
- * @internal
- * @deprecated This API is ICU internal only.
- */
-@Deprecated
-LocaleMatcher::Builder &LocaleMatcher::Builder::internalSetThresholdDistance(int32_t thresholdDistance) {
-    if (U_FAILURE(errorCode_)) { return *this; }
-    if (thresholdDistance > 100) {
-        thresholdDistance = 100;
-    }
-    thresholdDistance_ = thresholdDistance;
-    return *this;
-}
-#endif
-
-UBool LocaleMatcher::Builder::copyErrorTo(UErrorCode &outErrorCode) const {
-    if (U_FAILURE(outErrorCode)) { return TRUE; }
-    if (U_SUCCESS(errorCode_)) { return FALSE; }
-    outErrorCode = errorCode_;
-    return TRUE;
-}
-
-LocaleMatcher LocaleMatcher::Builder::build(UErrorCode &errorCode) const {
-    if (U_SUCCESS(errorCode) && U_FAILURE(errorCode_)) {
-        errorCode = errorCode_;
-    }
-    return LocaleMatcher(*this, errorCode);
-}
-
-namespace {
-
-LSR getMaximalLsrOrUnd(const XLikelySubtags &likelySubtags, const Locale &locale,
-                       UErrorCode &errorCode) {
-    if (U_FAILURE(errorCode) || locale.isBogus() || *locale.getName() == 0 /* "und" */) {
-        return UND_LSR;
-    } else {
-        return likelySubtags.makeMaximizedLsrFrom(locale, errorCode);
-    }
-}
-
-int32_t hashLSR(const UHashTok token) {
-    const LSR *lsr = static_cast<const LSR *>(token.pointer);
-    return lsr->hashCode;
-}
-
-UBool compareLSRs(const UHashTok t1, const UHashTok t2) {
-    const LSR *lsr1 = static_cast<const LSR *>(t1.pointer);
-    const LSR *lsr2 = static_cast<const LSR *>(t2.pointer);
-    return *lsr1 == *lsr2;
-}
-
-}  // namespace
-
-int32_t LocaleMatcher::putIfAbsent(const LSR &lsr, int32_t i, int32_t suppLength,
-                                   UErrorCode &errorCode) {
-    if (U_FAILURE(errorCode)) { return suppLength; }
-    int32_t index = uhash_geti(supportedLsrToIndex, &lsr);
-    if (index == 0) {
-        uhash_puti(supportedLsrToIndex, const_cast<LSR *>(&lsr), i + 1, &errorCode);
-        if (U_SUCCESS(errorCode)) {
-            supportedLSRs[suppLength] = &lsr;
-            supportedIndexes[suppLength++] = i;
-        }
-    }
-    return suppLength;
-}
-
-LocaleMatcher::LocaleMatcher(const Builder &builder, UErrorCode &errorCode) :
-        likelySubtags(*XLikelySubtags::getSingleton(errorCode)),
-        localeDistance(*LocaleDistance::getSingleton(errorCode)),
-        thresholdDistance(builder.thresholdDistance_),
-        demotionPerDesiredLocale(0),
-        favorSubtag(builder.favor_),
-        direction(builder.direction_),
-        supportedLocales(nullptr), lsrs(nullptr), supportedLocalesLength(0),
-        supportedLsrToIndex(nullptr),
-        supportedLSRs(nullptr), supportedIndexes(nullptr), supportedLSRsLength(0),
-        ownedDefaultLocale(nullptr), defaultLocale(nullptr) {
-    if (U_FAILURE(errorCode)) { return; }
-    if (thresholdDistance < 0) {
-        thresholdDistance = localeDistance.getDefaultScriptDistance();
-    }
-    const Locale *def = builder.defaultLocale_;
-    LSR builderDefaultLSR;
-    const LSR *defLSR = nullptr;
-    if (def != nullptr) {
-        ownedDefaultLocale = def->clone();
-        if (ownedDefaultLocale == nullptr) {
-            errorCode = U_MEMORY_ALLOCATION_ERROR;
-            return;
-        }
-        def = ownedDefaultLocale;
-        builderDefaultLSR = getMaximalLsrOrUnd(likelySubtags, *def, errorCode);
-        if (U_FAILURE(errorCode)) { return; }
-        defLSR = &builderDefaultLSR;
-    }
-    supportedLocalesLength = builder.supportedLocales_ != nullptr ?
-        builder.supportedLocales_->size() : 0;
-    if (supportedLocalesLength > 0) {
-        // Store the supported locales in input order,
-        // so that when different types are used (e.g., language tag strings)
-        // we can return those by parallel index.
-        supportedLocales = static_cast<const Locale **>(
-            uprv_malloc(supportedLocalesLength * sizeof(const Locale *)));
-        // Supported LRSs in input order.
-        // In C++, we store these permanently to simplify ownership management
-        // in the hash tables. Duplicate LSRs (if any) are unused overhead.
-        lsrs = new LSR[supportedLocalesLength];
-        if (supportedLocales == nullptr || lsrs == nullptr) {
-            errorCode = U_MEMORY_ALLOCATION_ERROR;
-            return;
-        }
-        // If the constructor fails partway, we need null pointers for destructibility.
-        uprv_memset(supportedLocales, 0, supportedLocalesLength * sizeof(const Locale *));
-        for (int32_t i = 0; i < supportedLocalesLength; ++i) {
-            const Locale &locale = *static_cast<Locale *>(builder.supportedLocales_->elementAt(i));
-            supportedLocales[i] = locale.clone();
-            if (supportedLocales[i] == nullptr) {
-                errorCode = U_MEMORY_ALLOCATION_ERROR;
-                return;
-            }
-            const Locale &supportedLocale = *supportedLocales[i];
-            LSR &lsr = lsrs[i] = getMaximalLsrOrUnd(likelySubtags, supportedLocale, errorCode);
-            lsr.setHashCode();
-            if (U_FAILURE(errorCode)) { return; }
-        }
-
-        // We need an unordered map from LSR to first supported locale with that LSR,
-        // and an ordered list of (LSR, supported index) for
-        // the supported locales in the following order:
-        // 1. Default locale, if it is supported.
-        // 2. Priority locales (aka "paradigm locales") in builder order.
-        // 3. Remaining locales in builder order.
-        supportedLsrToIndex = uhash_openSize(hashLSR, compareLSRs, uhash_compareLong,
-                                             supportedLocalesLength, &errorCode);
-        if (U_FAILURE(errorCode)) { return; }
-        supportedLSRs = static_cast<const LSR **>(
-            uprv_malloc(supportedLocalesLength * sizeof(const LSR *)));
-        supportedIndexes = static_cast<int32_t *>(
-            uprv_malloc(supportedLocalesLength * sizeof(int32_t)));
-        if (supportedLSRs == nullptr || supportedIndexes == nullptr) {
-            errorCode = U_MEMORY_ALLOCATION_ERROR;
-            return;
-        }
-        int32_t suppLength = 0;
-        // Determine insertion order.
-        // Add locales immediately that are equivalent to the default.
-        MaybeStackArray<int8_t, 100> order(supportedLocalesLength);
-        if (order.getAlias() == nullptr) {
-            errorCode = U_MEMORY_ALLOCATION_ERROR;
-            return;
-        }
-        int32_t numParadigms = 0;
-        for (int32_t i = 0; i < supportedLocalesLength; ++i) {
-            const Locale &locale = *supportedLocales[i];
-            const LSR &lsr = lsrs[i];
-            if (defLSR == nullptr) {
-                U_ASSERT(i == 0);
-                def = &locale;
-                defLSR = &lsr;
-                order[i] = 1;
-                suppLength = putIfAbsent(lsr, 0, suppLength, errorCode);
-            } else if (lsr.isEquivalentTo(*defLSR)) {
-                order[i] = 1;
-                suppLength = putIfAbsent(lsr, i, suppLength, errorCode);
-            } else if (localeDistance.isParadigmLSR(lsr)) {
-                order[i] = 2;
-                ++numParadigms;
-            } else {
-                order[i] = 3;
-            }
-            if (U_FAILURE(errorCode)) { return; }
-        }
-        // Add supported paradigm locales.
-        int32_t paradigmLimit = suppLength + numParadigms;
-        for (int32_t i = 0; i < supportedLocalesLength && suppLength < paradigmLimit; ++i) {
-            if (order[i] == 2) {
-                suppLength = putIfAbsent(lsrs[i], i, suppLength, errorCode);
-            }
-        }
-        // Add remaining supported locales.
-        for (int32_t i = 0; i < supportedLocalesLength; ++i) {
-            if (order[i] == 3) {
-                suppLength = putIfAbsent(lsrs[i], i, suppLength, errorCode);
-            }
-        }
-        supportedLSRsLength = suppLength;
-        // If supportedLSRsLength < supportedLocalesLength then
-        // we waste as many array slots as there are duplicate supported LSRs,
-        // but the amount of wasted space is small as long as there are few duplicates.
-    }
-
-    defaultLocale = def;
-
-    if (builder.demotion_ == ULOCMATCH_DEMOTION_REGION) {
-        demotionPerDesiredLocale = localeDistance.getDefaultDemotionPerDesiredLocale();
-    }
-}
-
-LocaleMatcher::LocaleMatcher(LocaleMatcher &&src) U_NOEXCEPT :
-        likelySubtags(src.likelySubtags),
-        localeDistance(src.localeDistance),
-        thresholdDistance(src.thresholdDistance),
-        demotionPerDesiredLocale(src.demotionPerDesiredLocale),
-        favorSubtag(src.favorSubtag),
-        direction(src.direction),
-        supportedLocales(src.supportedLocales), lsrs(src.lsrs),
-        supportedLocalesLength(src.supportedLocalesLength),
-        supportedLsrToIndex(src.supportedLsrToIndex),
-        supportedLSRs(src.supportedLSRs),
-        supportedIndexes(src.supportedIndexes),
-        supportedLSRsLength(src.supportedLSRsLength),
-        ownedDefaultLocale(src.ownedDefaultLocale), defaultLocale(src.defaultLocale) {
-    src.supportedLocales = nullptr;
-    src.lsrs = nullptr;
-    src.supportedLocalesLength = 0;
-    src.supportedLsrToIndex = nullptr;
-    src.supportedLSRs = nullptr;
-    src.supportedIndexes = nullptr;
-    src.supportedLSRsLength = 0;
-    src.ownedDefaultLocale = nullptr;
-    src.defaultLocale = nullptr;
-}
-
-LocaleMatcher::~LocaleMatcher() {
-    for (int32_t i = 0; i < supportedLocalesLength; ++i) {
-        delete supportedLocales[i];
-    }
-    uprv_free(supportedLocales);
-    delete[] lsrs;
-    uhash_close(supportedLsrToIndex);
-    uprv_free(supportedLSRs);
-    uprv_free(supportedIndexes);
-    delete ownedDefaultLocale;
-}
-
-LocaleMatcher &LocaleMatcher::operator=(LocaleMatcher &&src) U_NOEXCEPT {
-    this->~LocaleMatcher();
-
-    thresholdDistance = src.thresholdDistance;
-    demotionPerDesiredLocale = src.demotionPerDesiredLocale;
-    favorSubtag = src.favorSubtag;
-    direction = src.direction;
-    supportedLocales = src.supportedLocales;
-    lsrs = src.lsrs;
-    supportedLocalesLength = src.supportedLocalesLength;
-    supportedLsrToIndex = src.supportedLsrToIndex;
-    supportedLSRs = src.supportedLSRs;
-    supportedIndexes = src.supportedIndexes;
-    supportedLSRsLength = src.supportedLSRsLength;
-    ownedDefaultLocale = src.ownedDefaultLocale;
-    defaultLocale = src.defaultLocale;
-
-    src.supportedLocales = nullptr;
-    src.lsrs = nullptr;
-    src.supportedLocalesLength = 0;
-    src.supportedLsrToIndex = nullptr;
-    src.supportedLSRs = nullptr;
-    src.supportedIndexes = nullptr;
-    src.supportedLSRsLength = 0;
-    src.ownedDefaultLocale = nullptr;
-    src.defaultLocale = nullptr;
-    return *this;
-}
-
-class LocaleLsrIterator {
-public:
-    LocaleLsrIterator(const XLikelySubtags &likelySubtags, Locale::Iterator &locales,
-                      ULocMatchLifetime lifetime) :
-            likelySubtags(likelySubtags), locales(locales), lifetime(lifetime) {}
-
-    ~LocaleLsrIterator() {
-        if (lifetime == ULOCMATCH_TEMPORARY_LOCALES) {
-            delete remembered;
-        }
-    }
-
-    bool hasNext() const {
-        return locales.hasNext();
-    }
-
-    LSR next(UErrorCode &errorCode) {
-        current = &locales.next();
-        return getMaximalLsrOrUnd(likelySubtags, *current, errorCode);
-    }
-
-    void rememberCurrent(int32_t desiredIndex, UErrorCode &errorCode) {
-        if (U_FAILURE(errorCode)) { return; }
-        bestDesiredIndex = desiredIndex;
-        if (lifetime == ULOCMATCH_STORED_LOCALES) {
-            remembered = current;
-        } else {
-            // ULOCMATCH_TEMPORARY_LOCALES
-            delete remembered;
-            remembered = new Locale(*current);
-            if (remembered == nullptr) {
-                errorCode = U_MEMORY_ALLOCATION_ERROR;
-            }
-        }
-    }
-
-    const Locale *orphanRemembered() {
-        const Locale *rem = remembered;
-        remembered = nullptr;
-        return rem;
-    }
-
-    int32_t getBestDesiredIndex() const {
-        return bestDesiredIndex;
-    }
-
-private:
-    const XLikelySubtags &likelySubtags;
-    Locale::Iterator &locales;
-    ULocMatchLifetime lifetime;
-    const Locale *current = nullptr, *remembered = nullptr;
-    int32_t bestDesiredIndex = -1;
-};
-
-const Locale *LocaleMatcher::getBestMatch(const Locale &desiredLocale, UErrorCode &errorCode) const {
-    if (U_FAILURE(errorCode)) { return nullptr; }
-    int32_t suppIndex = getBestSuppIndex(
-        getMaximalLsrOrUnd(likelySubtags, desiredLocale, errorCode),
-        nullptr, errorCode);
-    return U_SUCCESS(errorCode) && suppIndex >= 0 ? supportedLocales[suppIndex] : defaultLocale;
-}
-
-const Locale *LocaleMatcher::getBestMatch(Locale::Iterator &desiredLocales,
-                                          UErrorCode &errorCode) const {
-    if (U_FAILURE(errorCode)) { return nullptr; }
-    if (!desiredLocales.hasNext()) {
-        return defaultLocale;
-    }
-    LocaleLsrIterator lsrIter(likelySubtags, desiredLocales, ULOCMATCH_TEMPORARY_LOCALES);
-    int32_t suppIndex = getBestSuppIndex(lsrIter.next(errorCode), &lsrIter, errorCode);
-    return U_SUCCESS(errorCode) && suppIndex >= 0 ? supportedLocales[suppIndex] : defaultLocale;
-}
-
-const Locale *LocaleMatcher::getBestMatchForListString(
-        StringPiece desiredLocaleList, UErrorCode &errorCode) const {
-    LocalePriorityList list(desiredLocaleList, errorCode);
-    LocalePriorityList::Iterator iter = list.iterator();
-    return getBestMatch(iter, errorCode);
-}
-
-LocaleMatcher::Result LocaleMatcher::getBestMatchResult(
-        const Locale &desiredLocale, UErrorCode &errorCode) const {
-    if (U_FAILURE(errorCode)) {
-        return Result(nullptr, defaultLocale, -1, -1, FALSE);
-    }
-    int32_t suppIndex = getBestSuppIndex(
-        getMaximalLsrOrUnd(likelySubtags, desiredLocale, errorCode),
-        nullptr, errorCode);
-    if (U_FAILURE(errorCode) || suppIndex < 0) {
-        return Result(nullptr, defaultLocale, -1, -1, FALSE);
-    } else {
-        return Result(&desiredLocale, supportedLocales[suppIndex], 0, suppIndex, FALSE);
-    }
-}
-
-LocaleMatcher::Result LocaleMatcher::getBestMatchResult(
-        Locale::Iterator &desiredLocales, UErrorCode &errorCode) const {
-    if (U_FAILURE(errorCode) || !desiredLocales.hasNext()) {
-        return Result(nullptr, defaultLocale, -1, -1, FALSE);
-    }
-    LocaleLsrIterator lsrIter(likelySubtags, desiredLocales, ULOCMATCH_TEMPORARY_LOCALES);
-    int32_t suppIndex = getBestSuppIndex(lsrIter.next(errorCode), &lsrIter, errorCode);
-    if (U_FAILURE(errorCode) || suppIndex < 0) {
-        return Result(nullptr, defaultLocale, -1, -1, FALSE);
-    } else {
-        return Result(lsrIter.orphanRemembered(), supportedLocales[suppIndex],
-                      lsrIter.getBestDesiredIndex(), suppIndex, TRUE);
-    }
-}
-
-int32_t LocaleMatcher::getBestSuppIndex(LSR desiredLSR, LocaleLsrIterator *remainingIter,
-                                        UErrorCode &errorCode) const {
-    if (U_FAILURE(errorCode)) { return -1; }
-    int32_t desiredIndex = 0;
-    int32_t bestSupportedLsrIndex = -1;
-    for (int32_t bestShiftedDistance = LocaleDistance::shiftDistance(thresholdDistance);;) {
-        // Quick check for exact maximized LSR.
-        // Returns suppIndex+1 where 0 means not found.
-        if (supportedLsrToIndex != nullptr) {
-            desiredLSR.setHashCode();
-            int32_t index = uhash_geti(supportedLsrToIndex, &desiredLSR);
-            if (index != 0) {
-                int32_t suppIndex = index - 1;
-                if (remainingIter != nullptr) {
-                    remainingIter->rememberCurrent(desiredIndex, errorCode);
-                }
-                return suppIndex;
-            }
-        }
-        int32_t bestIndexAndDistance = localeDistance.getBestIndexAndDistance(
-                desiredLSR, supportedLSRs, supportedLSRsLength,
-                bestShiftedDistance, favorSubtag, direction);
-        if (bestIndexAndDistance >= 0) {
-            bestShiftedDistance = LocaleDistance::getShiftedDistance(bestIndexAndDistance);
-            if (remainingIter != nullptr) {
-                remainingIter->rememberCurrent(desiredIndex, errorCode);
-                if (U_FAILURE(errorCode)) { return -1; }
-            }
-            bestSupportedLsrIndex = LocaleDistance::getIndex(bestIndexAndDistance);
-        }
-        if ((bestShiftedDistance -= LocaleDistance::shiftDistance(demotionPerDesiredLocale)) <= 0) {
-            break;
-        }
-        if (remainingIter == nullptr || !remainingIter->hasNext()) {
-            break;
-        }
-        desiredLSR = remainingIter->next(errorCode);
-        if (U_FAILURE(errorCode)) { return -1; }
-        ++desiredIndex;
-    }
-    if (bestSupportedLsrIndex < 0) {
-        // no good match
-        return -1;
-    }
-    return supportedIndexes[bestSupportedLsrIndex];
-}
-
-double LocaleMatcher::internalMatch(const Locale &desired, const Locale &supported, UErrorCode &errorCode) const {
-    // Returns the inverse of the distance: That is, 1-distance(desired, supported).
-    LSR suppLSR = getMaximalLsrOrUnd(likelySubtags, supported, errorCode);
-    if (U_FAILURE(errorCode)) { return 0; }
-    const LSR *pSuppLSR = &suppLSR;
-    int32_t indexAndDistance = localeDistance.getBestIndexAndDistance(
-            getMaximalLsrOrUnd(likelySubtags, desired, errorCode),
-            &pSuppLSR, 1,
-            LocaleDistance::shiftDistance(thresholdDistance), favorSubtag, direction);
-    double distance = LocaleDistance::getDistanceDouble(indexAndDistance);
-    return (100.0 - distance) / 100.0;
-}
-
-U_NAMESPACE_END
-
-// uloc_acceptLanguage() --------------------------------------------------- ***
-
-U_NAMESPACE_USE
-
-namespace {
-
-class LocaleFromTag {
-public:
-    LocaleFromTag() : locale(Locale::getRoot()) {}
-    const Locale &operator()(const char *tag) { return locale = Locale(tag); }
-
-private:
-    // Store the locale in the converter, rather than return a reference to a temporary,
-    // or a value which could go out of scope with the caller's reference to it.
-    Locale locale;
-};
-
-int32_t acceptLanguage(UEnumeration &supportedLocales, Locale::Iterator &desiredLocales,
-                       char *dest, int32_t capacity, UAcceptResult *acceptResult,
-                       UErrorCode &errorCode) {
-    if (U_FAILURE(errorCode)) { return 0; }
-    LocaleMatcher::Builder builder;
-    const char *locString;
-    while ((locString = uenum_next(&supportedLocales, nullptr, &errorCode)) != nullptr) {
-        Locale loc(locString);
-        if (loc.isBogus()) {
-            errorCode = U_ILLEGAL_ARGUMENT_ERROR;
-            return 0;
-        }
-        builder.addSupportedLocale(loc);
-    }
-    LocaleMatcher matcher = builder.build(errorCode);
-    LocaleMatcher::Result result = matcher.getBestMatchResult(desiredLocales, errorCode);
-    if (U_FAILURE(errorCode)) { return 0; }
-    if (result.getDesiredIndex() >= 0) {
-        if (acceptResult != nullptr) {
-            *acceptResult = *result.getDesiredLocale() == *result.getSupportedLocale() ?
-                ULOC_ACCEPT_VALID : ULOC_ACCEPT_FALLBACK;
-        }
-        const char *bestStr = result.getSupportedLocale()->getName();
-        int32_t bestLength = (int32_t)uprv_strlen(bestStr);
-        if (bestLength <= capacity) {
-            uprv_memcpy(dest, bestStr, bestLength);
-        }
-        return u_terminateChars(dest, capacity, bestLength, &errorCode);
-    } else {
-        if (acceptResult != nullptr) {
-            *acceptResult = ULOC_ACCEPT_FAILED;
-        }
-        return u_terminateChars(dest, capacity, 0, &errorCode);
-    }
-}
-
-}  // namespace
-
-U_CAPI int32_t U_EXPORT2
-uloc_acceptLanguage(char *result, int32_t resultAvailable,
-                    UAcceptResult *outResult,
-                    const char **acceptList, int32_t acceptListCount,
-                    UEnumeration *availableLocales,
-                    UErrorCode *status) {
-    if (U_FAILURE(*status)) { return 0; }
-    if ((result == nullptr ? resultAvailable != 0 : resultAvailable < 0) ||
-            (acceptList == nullptr ? acceptListCount != 0 : acceptListCount < 0) ||
-            availableLocales == nullptr) {
-        *status = U_ILLEGAL_ARGUMENT_ERROR;
-        return 0;
-    }
-    LocaleFromTag converter;
-    Locale::ConvertingIterator<const char **, LocaleFromTag> desiredLocales(
-        acceptList, acceptList + acceptListCount, converter);
-    return acceptLanguage(*availableLocales, desiredLocales,
-                          result, resultAvailable, outResult, *status);
-}
-
-U_CAPI int32_t U_EXPORT2
-uloc_acceptLanguageFromHTTP(char *result, int32_t resultAvailable,
-                            UAcceptResult *outResult,
-                            const char *httpAcceptLanguage,
-                            UEnumeration *availableLocales,
-                            UErrorCode *status) {
-    if (U_FAILURE(*status)) { return 0; }
-    if ((result == nullptr ? resultAvailable != 0 : resultAvailable < 0) ||
-            httpAcceptLanguage == nullptr || availableLocales == nullptr) {
-        *status = U_ILLEGAL_ARGUMENT_ERROR;
-        return 0;
-    }
-    LocalePriorityList list(httpAcceptLanguage, *status);
-    LocalePriorityList::Iterator desiredLocales = list.iterator();
-    return acceptLanguage(*availableLocales, desiredLocales,
-                          result, resultAvailable, outResult, *status);
-}
-
-#endif  // __LOCMATCHER_H__
+// © 2019 and later: Unicode, Inc. and others. 
+// License & terms of use: http://www.unicode.org/copyright.html#License 
+ 
+// localematcher.cpp 
+// created: 2019may08 Markus W. Scherer 
+ 
+#ifndef __LOCMATCHER_H__ 
+#define __LOCMATCHER_H__ 
+ 
+#include "unicode/utypes.h" 
+#include "unicode/localebuilder.h" 
+#include "unicode/localematcher.h" 
+#include "unicode/locid.h" 
+#include "unicode/stringpiece.h" 
+#include "unicode/uloc.h" 
+#include "unicode/uobject.h" 
+#include "cstring.h" 
+#include "localeprioritylist.h" 
+#include "loclikelysubtags.h" 
+#include "locdistance.h" 
+#include "lsr.h" 
+#include "uassert.h" 
+#include "uhash.h" 
+#include "ustr_imp.h" 
+#include "uvector.h" 
+ 
+#define UND_LSR LSR("und", "", "", LSR::EXPLICIT_LSR) 
+ 
+/** 
+ * Indicator for the lifetime of desired-locale objects passed into the LocaleMatcher. 
+ * 
+ * @draft ICU 65 
+ */ 
+enum ULocMatchLifetime { 
+    /** 
+     * Locale objects are temporary. 
+     * The matcher will make a copy of a locale that will be used beyond one function call. 
+     * 
+     * @draft ICU 65 
+     */ 
+    ULOCMATCH_TEMPORARY_LOCALES, 
+    /** 
+     * Locale objects are stored at least as long as the matcher is used. 
+     * The matcher will keep only a pointer to a locale that will be used beyond one function call, 
+     * avoiding a copy. 
+     * 
+     * @draft ICU 65 
+     */ 
+    ULOCMATCH_STORED_LOCALES  // TODO: permanent? cached? clone? 
+}; 
+#ifndef U_IN_DOXYGEN 
+typedef enum ULocMatchLifetime ULocMatchLifetime; 
+#endif 
+ 
+U_NAMESPACE_BEGIN 
+ 
+LocaleMatcher::Result::Result(LocaleMatcher::Result &&src) U_NOEXCEPT : 
+        desiredLocale(src.desiredLocale), 
+        supportedLocale(src.supportedLocale), 
+        desiredIndex(src.desiredIndex), 
+        supportedIndex(src.supportedIndex), 
+        desiredIsOwned(src.desiredIsOwned) { 
+    if (desiredIsOwned) { 
+        src.desiredLocale = nullptr; 
+        src.desiredIndex = -1; 
+        src.desiredIsOwned = FALSE; 
+    } 
+} 
+ 
+LocaleMatcher::Result::~Result() { 
+    if (desiredIsOwned) { 
+        delete desiredLocale; 
+    } 
+} 
+ 
+LocaleMatcher::Result &LocaleMatcher::Result::operator=(LocaleMatcher::Result &&src) U_NOEXCEPT { 
+    this->~Result(); 
+ 
+    desiredLocale = src.desiredLocale; 
+    supportedLocale = src.supportedLocale; 
+    desiredIndex = src.desiredIndex; 
+    supportedIndex = src.supportedIndex; 
+    desiredIsOwned = src.desiredIsOwned; 
+ 
+    if (desiredIsOwned) { 
+        src.desiredLocale = nullptr; 
+        src.desiredIndex = -1; 
+        src.desiredIsOwned = FALSE; 
+    } 
+    return *this; 
+} 
+ 
+Locale LocaleMatcher::Result::makeResolvedLocale(UErrorCode &errorCode) const { 
+    if (U_FAILURE(errorCode) || supportedLocale == nullptr) { 
+        return Locale::getRoot(); 
+    } 
+    const Locale *bestDesired = getDesiredLocale(); 
+    if (bestDesired == nullptr || *supportedLocale == *bestDesired) { 
+        return *supportedLocale; 
+    } 
+    LocaleBuilder b; 
+    b.setLocale(*supportedLocale); 
+ 
+    // Copy the region from bestDesired, if there is one. 
+    const char *region = bestDesired->getCountry(); 
+    if (*region != 0) { 
+        b.setRegion(region); 
+    } 
+ 
+    // Copy the variants from bestDesired, if there are any. 
+    // Note that this will override any supportedLocale variants. 
+    // For example, "sco-ulster-fonipa" + "...-fonupa" => "sco-fonupa" (replacing ulster). 
+    const char *variants = bestDesired->getVariant(); 
+    if (*variants != 0) { 
+        b.setVariant(variants); 
+    } 
+ 
+    // Copy the extensions from bestDesired, if there are any. 
+    // C++ note: The following note, copied from Java, may not be true, 
+    // as long as C++ copies by legacy ICU keyword, not by extension singleton. 
+    // Note that this will override any supportedLocale extensions. 
+    // For example, "th-u-nu-latn-ca-buddhist" + "...-u-nu-native" => "th-u-nu-native" 
+    // (replacing calendar). 
+    b.copyExtensionsFrom(*bestDesired, errorCode); 
+    return b.build(errorCode); 
+} 
+ 
+LocaleMatcher::Builder::Builder(LocaleMatcher::Builder &&src) U_NOEXCEPT : 
+        errorCode_(src.errorCode_), 
+        supportedLocales_(src.supportedLocales_), 
+        thresholdDistance_(src.thresholdDistance_), 
+        demotion_(src.demotion_), 
+        defaultLocale_(src.defaultLocale_), 
+        favor_(src.favor_), 
+        direction_(src.direction_) { 
+    src.supportedLocales_ = nullptr; 
+    src.defaultLocale_ = nullptr; 
+} 
+ 
+LocaleMatcher::Builder::~Builder() { 
+    delete supportedLocales_; 
+    delete defaultLocale_; 
+} 
+ 
+LocaleMatcher::Builder &LocaleMatcher::Builder::operator=(LocaleMatcher::Builder &&src) U_NOEXCEPT { 
+    this->~Builder(); 
+ 
+    errorCode_ = src.errorCode_; 
+    supportedLocales_ = src.supportedLocales_; 
+    thresholdDistance_ = src.thresholdDistance_; 
+    demotion_ = src.demotion_; 
+    defaultLocale_ = src.defaultLocale_; 
+    favor_ = src.favor_; 
+    direction_ = src.direction_; 
+ 
+    src.supportedLocales_ = nullptr; 
+    src.defaultLocale_ = nullptr; 
+    return *this; 
+} 
+ 
+void LocaleMatcher::Builder::clearSupportedLocales() { 
+    if (supportedLocales_ != nullptr) { 
+        supportedLocales_->removeAllElements(); 
+    } 
+} 
+ 
+bool LocaleMatcher::Builder::ensureSupportedLocaleVector() { 
+    if (U_FAILURE(errorCode_)) { return false; } 
+    if (supportedLocales_ != nullptr) { return true; } 
+    supportedLocales_ = new UVector(uprv_deleteUObject, nullptr, errorCode_); 
+    if (U_FAILURE(errorCode_)) { return false; } 
+    if (supportedLocales_ == nullptr) { 
+        errorCode_ = U_MEMORY_ALLOCATION_ERROR; 
+        return false; 
+    } 
+    return true; 
+} 
+ 
+LocaleMatcher::Builder &LocaleMatcher::Builder::setSupportedLocalesFromListString( 
+        StringPiece locales) { 
+    LocalePriorityList list(locales, errorCode_); 
+    if (U_FAILURE(errorCode_)) { return *this; } 
+    clearSupportedLocales(); 
+    if (!ensureSupportedLocaleVector()) { return *this; } 
+    int32_t length = list.getLengthIncludingRemoved(); 
+    for (int32_t i = 0; i < length; ++i) { 
+        Locale *locale = list.orphanLocaleAt(i); 
+        if (locale == nullptr) { continue; } 
+        supportedLocales_->addElement(locale, errorCode_); 
+        if (U_FAILURE(errorCode_)) { 
+            delete locale; 
+            break; 
+        } 
+    } 
+    return *this; 
+} 
+ 
+LocaleMatcher::Builder &LocaleMatcher::Builder::setSupportedLocales(Locale::Iterator &locales) { 
+    if (U_FAILURE(errorCode_)) { return *this; } 
+    clearSupportedLocales(); 
+    if (!ensureSupportedLocaleVector()) { return *this; } 
+    while (locales.hasNext()) { 
+        const Locale &locale = locales.next(); 
+        Locale *clone = locale.clone(); 
+        if (clone == nullptr) { 
+            errorCode_ = U_MEMORY_ALLOCATION_ERROR; 
+            break; 
+        } 
+        supportedLocales_->addElement(clone, errorCode_); 
+        if (U_FAILURE(errorCode_)) { 
+            delete clone; 
+            break; 
+        } 
+    } 
+    return *this; 
+} 
+ 
+LocaleMatcher::Builder &LocaleMatcher::Builder::addSupportedLocale(const Locale &locale) { 
+    if (!ensureSupportedLocaleVector()) { return *this; } 
+    Locale *clone = locale.clone(); 
+    if (clone == nullptr) { 
+        errorCode_ = U_MEMORY_ALLOCATION_ERROR; 
+        return *this; 
+    } 
+    supportedLocales_->addElement(clone, errorCode_); 
+    if (U_FAILURE(errorCode_)) { 
+        delete clone; 
+    } 
+    return *this; 
+} 
+ 
+LocaleMatcher::Builder &LocaleMatcher::Builder::setDefaultLocale(const Locale *defaultLocale) { 
+    if (U_FAILURE(errorCode_)) { return *this; } 
+    Locale *clone = nullptr; 
+    if (defaultLocale != nullptr) { 
+        clone = defaultLocale->clone(); 
+        if (clone == nullptr) { 
+            errorCode_ = U_MEMORY_ALLOCATION_ERROR; 
+            return *this; 
+        } 
+    } 
+    delete defaultLocale_; 
+    defaultLocale_ = clone; 
+    return *this; 
+} 
+ 
+LocaleMatcher::Builder &LocaleMatcher::Builder::setFavorSubtag(ULocMatchFavorSubtag subtag) { 
+    if (U_FAILURE(errorCode_)) { return *this; } 
+    favor_ = subtag; 
+    return *this; 
+} 
+ 
+LocaleMatcher::Builder &LocaleMatcher::Builder::setDemotionPerDesiredLocale(ULocMatchDemotion demotion) { 
+    if (U_FAILURE(errorCode_)) { return *this; } 
+    demotion_ = demotion; 
+    return *this; 
+} 
+ 
+#if 0 
+/** 
+ * <i>Internal only!</i> 
+ * 
+ * @param thresholdDistance the thresholdDistance to set, with -1 = default 
+ * @return this Builder object 
+ * @internal 
+ * @deprecated This API is ICU internal only. 
+ */ 
+@Deprecated 
+LocaleMatcher::Builder &LocaleMatcher::Builder::internalSetThresholdDistance(int32_t thresholdDistance) { 
+    if (U_FAILURE(errorCode_)) { return *this; } 
+    if (thresholdDistance > 100) { 
+        thresholdDistance = 100; 
+    } 
+    thresholdDistance_ = thresholdDistance; 
+    return *this; 
+} 
+#endif 
+ 
+UBool LocaleMatcher::Builder::copyErrorTo(UErrorCode &outErrorCode) const { 
+    if (U_FAILURE(outErrorCode)) { return TRUE; } 
+    if (U_SUCCESS(errorCode_)) { return FALSE; } 
+    outErrorCode = errorCode_; 
+    return TRUE; 
+} 
+ 
+LocaleMatcher LocaleMatcher::Builder::build(UErrorCode &errorCode) const { 
+    if (U_SUCCESS(errorCode) && U_FAILURE(errorCode_)) { 
+        errorCode = errorCode_; 
+    } 
+    return LocaleMatcher(*this, errorCode); 
+} 
+ 
+namespace { 
+ 
+LSR getMaximalLsrOrUnd(const XLikelySubtags &likelySubtags, const Locale &locale, 
+                       UErrorCode &errorCode) { 
+    if (U_FAILURE(errorCode) || locale.isBogus() || *locale.getName() == 0 /* "und" */) { 
+        return UND_LSR; 
+    } else { 
+        return likelySubtags.makeMaximizedLsrFrom(locale, errorCode); 
+    } 
+} 
+ 
+int32_t hashLSR(const UHashTok token) { 
+    const LSR *lsr = static_cast<const LSR *>(token.pointer); 
+    return lsr->hashCode; 
+} 
+ 
+UBool compareLSRs(const UHashTok t1, const UHashTok t2) { 
+    const LSR *lsr1 = static_cast<const LSR *>(t1.pointer); 
+    const LSR *lsr2 = static_cast<const LSR *>(t2.pointer); 
+    return *lsr1 == *lsr2; 
+} 
+ 
+}  // namespace 
+ 
+int32_t LocaleMatcher::putIfAbsent(const LSR &lsr, int32_t i, int32_t suppLength, 
+                                   UErrorCode &errorCode) { 
+    if (U_FAILURE(errorCode)) { return suppLength; } 
+    int32_t index = uhash_geti(supportedLsrToIndex, &lsr); 
+    if (index == 0) { 
+        uhash_puti(supportedLsrToIndex, const_cast<LSR *>(&lsr), i + 1, &errorCode); 
+        if (U_SUCCESS(errorCode)) { 
+            supportedLSRs[suppLength] = &lsr; 
+            supportedIndexes[suppLength++] = i; 
+        } 
+    } 
+    return suppLength; 
+} 
+ 
+LocaleMatcher::LocaleMatcher(const Builder &builder, UErrorCode &errorCode) : 
+        likelySubtags(*XLikelySubtags::getSingleton(errorCode)), 
+        localeDistance(*LocaleDistance::getSingleton(errorCode)), 
+        thresholdDistance(builder.thresholdDistance_), 
+        demotionPerDesiredLocale(0), 
+        favorSubtag(builder.favor_), 
+        direction(builder.direction_), 
+        supportedLocales(nullptr), lsrs(nullptr), supportedLocalesLength(0), 
+        supportedLsrToIndex(nullptr), 
+        supportedLSRs(nullptr), supportedIndexes(nullptr), supportedLSRsLength(0), 
+        ownedDefaultLocale(nullptr), defaultLocale(nullptr) { 
+    if (U_FAILURE(errorCode)) { return; } 
+    if (thresholdDistance < 0) { 
+        thresholdDistance = localeDistance.getDefaultScriptDistance(); 
+    } 
+    const Locale *def = builder.defaultLocale_; 
+    LSR builderDefaultLSR; 
+    const LSR *defLSR = nullptr; 
+    if (def != nullptr) { 
+        ownedDefaultLocale = def->clone(); 
+        if (ownedDefaultLocale == nullptr) { 
+            errorCode = U_MEMORY_ALLOCATION_ERROR; 
+            return; 
+        } 
+        def = ownedDefaultLocale; 
+        builderDefaultLSR = getMaximalLsrOrUnd(likelySubtags, *def, errorCode); 
+        if (U_FAILURE(errorCode)) { return; } 
+        defLSR = &builderDefaultLSR; 
+    } 
+    supportedLocalesLength = builder.supportedLocales_ != nullptr ? 
+        builder.supportedLocales_->size() : 0; 
+    if (supportedLocalesLength > 0) { 
+        // Store the supported locales in input order, 
+        // so that when different types are used (e.g., language tag strings) 
+        // we can return those by parallel index. 
+        supportedLocales = static_cast<const Locale **>( 
+            uprv_malloc(supportedLocalesLength * sizeof(const Locale *))); 
+        // Supported LRSs in input order. 
+        // In C++, we store these permanently to simplify ownership management 
+        // in the hash tables. Duplicate LSRs (if any) are unused overhead. 
+        lsrs = new LSR[supportedLocalesLength]; 
+        if (supportedLocales == nullptr || lsrs == nullptr) { 
+            errorCode = U_MEMORY_ALLOCATION_ERROR; 
+            return; 
+        } 
+        // If the constructor fails partway, we need null pointers for destructibility. 
+        uprv_memset(supportedLocales, 0, supportedLocalesLength * sizeof(const Locale *)); 
+        for (int32_t i = 0; i < supportedLocalesLength; ++i) { 
+            const Locale &locale = *static_cast<Locale *>(builder.supportedLocales_->elementAt(i)); 
+            supportedLocales[i] = locale.clone(); 
+            if (supportedLocales[i] == nullptr) { 
+                errorCode = U_MEMORY_ALLOCATION_ERROR; 
+                return; 
+            } 
+            const Locale &supportedLocale = *supportedLocales[i]; 
+            LSR &lsr = lsrs[i] = getMaximalLsrOrUnd(likelySubtags, supportedLocale, errorCode); 
+            lsr.setHashCode(); 
+            if (U_FAILURE(errorCode)) { return; } 
+        } 
+ 
+        // We need an unordered map from LSR to first supported locale with that LSR, 
+        // and an ordered list of (LSR, supported index) for 
+        // the supported locales in the following order: 
+        // 1. Default locale, if it is supported. 
+        // 2. Priority locales (aka "paradigm locales") in builder order. 
+        // 3. Remaining locales in builder order. 
+        supportedLsrToIndex = uhash_openSize(hashLSR, compareLSRs, uhash_compareLong, 
+                                             supportedLocalesLength, &errorCode); 
+        if (U_FAILURE(errorCode)) { return; } 
+        supportedLSRs = static_cast<const LSR **>( 
+            uprv_malloc(supportedLocalesLength * sizeof(const LSR *))); 
+        supportedIndexes = static_cast<int32_t *>( 
+            uprv_malloc(supportedLocalesLength * sizeof(int32_t))); 
+        if (supportedLSRs == nullptr || supportedIndexes == nullptr) { 
+            errorCode = U_MEMORY_ALLOCATION_ERROR; 
+            return; 
+        } 
+        int32_t suppLength = 0; 
+        // Determine insertion order. 
+        // Add locales immediately that are equivalent to the default. 
+        MaybeStackArray<int8_t, 100> order(supportedLocalesLength); 
+        if (order.getAlias() == nullptr) { 
+            errorCode = U_MEMORY_ALLOCATION_ERROR; 
+            return; 
+        } 
+        int32_t numParadigms = 0; 
+        for (int32_t i = 0; i < supportedLocalesLength; ++i) { 
+            const Locale &locale = *supportedLocales[i]; 
+            const LSR &lsr = lsrs[i]; 
+            if (defLSR == nullptr) { 
+                U_ASSERT(i == 0); 
+                def = &locale; 
+                defLSR = &lsr; 
+                order[i] = 1; 
+                suppLength = putIfAbsent(lsr, 0, suppLength, errorCode); 
+            } else if (lsr.isEquivalentTo(*defLSR)) { 
+                order[i] = 1; 
+                suppLength = putIfAbsent(lsr, i, suppLength, errorCode); 
+            } else if (localeDistance.isParadigmLSR(lsr)) { 
+                order[i] = 2; 
+                ++numParadigms; 
+            } else { 
+                order[i] = 3; 
+            } 
+            if (U_FAILURE(errorCode)) { return; } 
+        } 
+        // Add supported paradigm locales. 
+        int32_t paradigmLimit = suppLength + numParadigms; 
+        for (int32_t i = 0; i < supportedLocalesLength && suppLength < paradigmLimit; ++i) { 
+            if (order[i] == 2) { 
+                suppLength = putIfAbsent(lsrs[i], i, suppLength, errorCode); 
+            } 
+        } 
+        // Add remaining supported locales. 
+        for (int32_t i = 0; i < supportedLocalesLength; ++i) { 
+            if (order[i] == 3) { 
+                suppLength = putIfAbsent(lsrs[i], i, suppLength, errorCode); 
+            } 
+        } 
+        supportedLSRsLength = suppLength; 
+        // If supportedLSRsLength < supportedLocalesLength then 
+        // we waste as many array slots as there are duplicate supported LSRs, 
+        // but the amount of wasted space is small as long as there are few duplicates. 
+    } 
+ 
+    defaultLocale = def; 
+ 
+    if (builder.demotion_ == ULOCMATCH_DEMOTION_REGION) { 
+        demotionPerDesiredLocale = localeDistance.getDefaultDemotionPerDesiredLocale(); 
+    } 
+} 
+ 
+LocaleMatcher::LocaleMatcher(LocaleMatcher &&src) U_NOEXCEPT : 
+        likelySubtags(src.likelySubtags), 
+        localeDistance(src.localeDistance), 
+        thresholdDistance(src.thresholdDistance), 
+        demotionPerDesiredLocale(src.demotionPerDesiredLocale), 
+        favorSubtag(src.favorSubtag), 
+        direction(src.direction), 
+        supportedLocales(src.supportedLocales), lsrs(src.lsrs), 
+        supportedLocalesLength(src.supportedLocalesLength), 
+        supportedLsrToIndex(src.supportedLsrToIndex), 
+        supportedLSRs(src.supportedLSRs), 
+        supportedIndexes(src.supportedIndexes), 
+        supportedLSRsLength(src.supportedLSRsLength), 
+        ownedDefaultLocale(src.ownedDefaultLocale), defaultLocale(src.defaultLocale) { 
+    src.supportedLocales = nullptr; 
+    src.lsrs = nullptr; 
+    src.supportedLocalesLength = 0; 
+    src.supportedLsrToIndex = nullptr; 
+    src.supportedLSRs = nullptr; 
+    src.supportedIndexes = nullptr; 
+    src.supportedLSRsLength = 0; 
+    src.ownedDefaultLocale = nullptr; 
+    src.defaultLocale = nullptr; 
+} 
+ 
+LocaleMatcher::~LocaleMatcher() { 
+    for (int32_t i = 0; i < supportedLocalesLength; ++i) { 
+        delete supportedLocales[i]; 
+    } 
+    uprv_free(supportedLocales); 
+    delete[] lsrs; 
+    uhash_close(supportedLsrToIndex); 
+    uprv_free(supportedLSRs); 
+    uprv_free(supportedIndexes); 
+    delete ownedDefaultLocale; 
+} 
+ 
+LocaleMatcher &LocaleMatcher::operator=(LocaleMatcher &&src) U_NOEXCEPT { 
+    this->~LocaleMatcher(); 
+ 
+    thresholdDistance = src.thresholdDistance; 
+    demotionPerDesiredLocale = src.demotionPerDesiredLocale; 
+    favorSubtag = src.favorSubtag; 
+    direction = src.direction; 
+    supportedLocales = src.supportedLocales; 
+    lsrs = src.lsrs; 
+    supportedLocalesLength = src.supportedLocalesLength; 
+    supportedLsrToIndex = src.supportedLsrToIndex; 
+    supportedLSRs = src.supportedLSRs; 
+    supportedIndexes = src.supportedIndexes; 
+    supportedLSRsLength = src.supportedLSRsLength; 
+    ownedDefaultLocale = src.ownedDefaultLocale; 
+    defaultLocale = src.defaultLocale; 
+ 
+    src.supportedLocales = nullptr; 
+    src.lsrs = nullptr; 
+    src.supportedLocalesLength = 0; 
+    src.supportedLsrToIndex = nullptr; 
+    src.supportedLSRs = nullptr; 
+    src.supportedIndexes = nullptr; 
+    src.supportedLSRsLength = 0; 
+    src.ownedDefaultLocale = nullptr; 
+    src.defaultLocale = nullptr; 
+    return *this; 
+} 
+ 
+class LocaleLsrIterator { 
+public: 
+    LocaleLsrIterator(const XLikelySubtags &likelySubtags, Locale::Iterator &locales, 
+                      ULocMatchLifetime lifetime) : 
+            likelySubtags(likelySubtags), locales(locales), lifetime(lifetime) {} 
+ 
+    ~LocaleLsrIterator() { 
+        if (lifetime == ULOCMATCH_TEMPORARY_LOCALES) { 
+            delete remembered; 
+        } 
+    } 
+ 
+    bool hasNext() const { 
+        return locales.hasNext(); 
+    } 
+ 
+    LSR next(UErrorCode &errorCode) { 
+        current = &locales.next(); 
+        return getMaximalLsrOrUnd(likelySubtags, *current, errorCode); 
+    } 
+ 
+    void rememberCurrent(int32_t desiredIndex, UErrorCode &errorCode) { 
+        if (U_FAILURE(errorCode)) { return; } 
+        bestDesiredIndex = desiredIndex; 
+        if (lifetime == ULOCMATCH_STORED_LOCALES) { 
+            remembered = current; 
+        } else { 
+            // ULOCMATCH_TEMPORARY_LOCALES 
+            delete remembered; 
+            remembered = new Locale(*current); 
+            if (remembered == nullptr) { 
+                errorCode = U_MEMORY_ALLOCATION_ERROR; 
+            } 
+        } 
+    } 
+ 
+    const Locale *orphanRemembered() { 
+        const Locale *rem = remembered; 
+        remembered = nullptr; 
+        return rem; 
+    } 
+ 
+    int32_t getBestDesiredIndex() const { 
+        return bestDesiredIndex; 
+    } 
+ 
+private: 
+    const XLikelySubtags &likelySubtags; 
+    Locale::Iterator &locales; 
+    ULocMatchLifetime lifetime; 
+    const Locale *current = nullptr, *remembered = nullptr; 
+    int32_t bestDesiredIndex = -1; 
+}; 
+ 
+const Locale *LocaleMatcher::getBestMatch(const Locale &desiredLocale, UErrorCode &errorCode) const { 
+    if (U_FAILURE(errorCode)) { return nullptr; } 
+    int32_t suppIndex = getBestSuppIndex( 
+        getMaximalLsrOrUnd(likelySubtags, desiredLocale, errorCode), 
+        nullptr, errorCode); 
+    return U_SUCCESS(errorCode) && suppIndex >= 0 ? supportedLocales[suppIndex] : defaultLocale; 
+} 
+ 
+const Locale *LocaleMatcher::getBestMatch(Locale::Iterator &desiredLocales, 
+                                          UErrorCode &errorCode) const { 
+    if (U_FAILURE(errorCode)) { return nullptr; } 
+    if (!desiredLocales.hasNext()) { 
+        return defaultLocale; 
+    } 
+    LocaleLsrIterator lsrIter(likelySubtags, desiredLocales, ULOCMATCH_TEMPORARY_LOCALES); 
+    int32_t suppIndex = getBestSuppIndex(lsrIter.next(errorCode), &lsrIter, errorCode); 
+    return U_SUCCESS(errorCode) && suppIndex >= 0 ? supportedLocales[suppIndex] : defaultLocale; 
+} 
+ 
+const Locale *LocaleMatcher::getBestMatchForListString( 
+        StringPiece desiredLocaleList, UErrorCode &errorCode) const { 
+    LocalePriorityList list(desiredLocaleList, errorCode); 
+    LocalePriorityList::Iterator iter = list.iterator(); 
+    return getBestMatch(iter, errorCode); 
+} 
+ 
+LocaleMatcher::Result LocaleMatcher::getBestMatchResult( 
+        const Locale &desiredLocale, UErrorCode &errorCode) const { 
+    if (U_FAILURE(errorCode)) { 
+        return Result(nullptr, defaultLocale, -1, -1, FALSE); 
+    } 
+    int32_t suppIndex = getBestSuppIndex( 
+        getMaximalLsrOrUnd(likelySubtags, desiredLocale, errorCode), 
+        nullptr, errorCode); 
+    if (U_FAILURE(errorCode) || suppIndex < 0) { 
+        return Result(nullptr, defaultLocale, -1, -1, FALSE); 
+    } else { 
+        return Result(&desiredLocale, supportedLocales[suppIndex], 0, suppIndex, FALSE); 
+    } 
+} 
+ 
+LocaleMatcher::Result LocaleMatcher::getBestMatchResult( 
+        Locale::Iterator &desiredLocales, UErrorCode &errorCode) const { 
+    if (U_FAILURE(errorCode) || !desiredLocales.hasNext()) { 
+        return Result(nullptr, defaultLocale, -1, -1, FALSE); 
+    } 
+    LocaleLsrIterator lsrIter(likelySubtags, desiredLocales, ULOCMATCH_TEMPORARY_LOCALES); 
+    int32_t suppIndex = getBestSuppIndex(lsrIter.next(errorCode), &lsrIter, errorCode); 
+    if (U_FAILURE(errorCode) || suppIndex < 0) { 
+        return Result(nullptr, defaultLocale, -1, -1, FALSE); 
+    } else { 
+        return Result(lsrIter.orphanRemembered(), supportedLocales[suppIndex], 
+                      lsrIter.getBestDesiredIndex(), suppIndex, TRUE); 
+    } 
+} 
+ 
+int32_t LocaleMatcher::getBestSuppIndex(LSR desiredLSR, LocaleLsrIterator *remainingIter, 
+                                        UErrorCode &errorCode) const { 
+    if (U_FAILURE(errorCode)) { return -1; } 
+    int32_t desiredIndex = 0; 
+    int32_t bestSupportedLsrIndex = -1; 
+    for (int32_t bestShiftedDistance = LocaleDistance::shiftDistance(thresholdDistance);;) { 
+        // Quick check for exact maximized LSR. 
+        // Returns suppIndex+1 where 0 means not found. 
+        if (supportedLsrToIndex != nullptr) { 
+            desiredLSR.setHashCode(); 
+            int32_t index = uhash_geti(supportedLsrToIndex, &desiredLSR); 
+            if (index != 0) { 
+                int32_t suppIndex = index - 1; 
+                if (remainingIter != nullptr) { 
+                    remainingIter->rememberCurrent(desiredIndex, errorCode); 
+                } 
+                return suppIndex; 
+            } 
+        } 
+        int32_t bestIndexAndDistance = localeDistance.getBestIndexAndDistance( 
+                desiredLSR, supportedLSRs, supportedLSRsLength, 
+                bestShiftedDistance, favorSubtag, direction); 
+        if (bestIndexAndDistance >= 0) { 
+            bestShiftedDistance = LocaleDistance::getShiftedDistance(bestIndexAndDistance); 
+            if (remainingIter != nullptr) { 
+                remainingIter->rememberCurrent(desiredIndex, errorCode); 
+                if (U_FAILURE(errorCode)) { return -1; } 
+            } 
+            bestSupportedLsrIndex = LocaleDistance::getIndex(bestIndexAndDistance); 
+        } 
+        if ((bestShiftedDistance -= LocaleDistance::shiftDistance(demotionPerDesiredLocale)) <= 0) { 
+            break; 
+        } 
+        if (remainingIter == nullptr || !remainingIter->hasNext()) { 
+            break; 
+        } 
+        desiredLSR = remainingIter->next(errorCode); 
+        if (U_FAILURE(errorCode)) { return -1; } 
+        ++desiredIndex; 
+    } 
+    if (bestSupportedLsrIndex < 0) { 
+        // no good match 
+        return -1; 
+    } 
+    return supportedIndexes[bestSupportedLsrIndex]; 
+} 
+ 
+double LocaleMatcher::internalMatch(const Locale &desired, const Locale &supported, UErrorCode &errorCode) const { 
+    // Returns the inverse of the distance: That is, 1-distance(desired, supported). 
+    LSR suppLSR = getMaximalLsrOrUnd(likelySubtags, supported, errorCode); 
+    if (U_FAILURE(errorCode)) { return 0; } 
+    const LSR *pSuppLSR = &suppLSR; 
+    int32_t indexAndDistance = localeDistance.getBestIndexAndDistance( 
+            getMaximalLsrOrUnd(likelySubtags, desired, errorCode), 
+            &pSuppLSR, 1, 
+            LocaleDistance::shiftDistance(thresholdDistance), favorSubtag, direction); 
+    double distance = LocaleDistance::getDistanceDouble(indexAndDistance); 
+    return (100.0 - distance) / 100.0; 
+} 
+ 
+U_NAMESPACE_END 
+ 
+// uloc_acceptLanguage() --------------------------------------------------- *** 
+ 
+U_NAMESPACE_USE 
+ 
+namespace { 
+ 
+class LocaleFromTag { 
+public: 
+    LocaleFromTag() : locale(Locale::getRoot()) {} 
+    const Locale &operator()(const char *tag) { return locale = Locale(tag); } 
+ 
+private: 
+    // Store the locale in the converter, rather than return a reference to a temporary, 
+    // or a value which could go out of scope with the caller's reference to it. 
+    Locale locale; 
+}; 
+ 
+int32_t acceptLanguage(UEnumeration &supportedLocales, Locale::Iterator &desiredLocales, 
+                       char *dest, int32_t capacity, UAcceptResult *acceptResult, 
+                       UErrorCode &errorCode) { 
+    if (U_FAILURE(errorCode)) { return 0; } 
+    LocaleMatcher::Builder builder; 
+    const char *locString; 
+    while ((locString = uenum_next(&supportedLocales, nullptr, &errorCode)) != nullptr) { 
+        Locale loc(locString); 
+        if (loc.isBogus()) { 
+            errorCode = U_ILLEGAL_ARGUMENT_ERROR; 
+            return 0; 
+        } 
+        builder.addSupportedLocale(loc); 
+    } 
+    LocaleMatcher matcher = builder.build(errorCode); 
+    LocaleMatcher::Result result = matcher.getBestMatchResult(desiredLocales, errorCode); 
+    if (U_FAILURE(errorCode)) { return 0; } 
+    if (result.getDesiredIndex() >= 0) { 
+        if (acceptResult != nullptr) { 
+            *acceptResult = *result.getDesiredLocale() == *result.getSupportedLocale() ? 
+                ULOC_ACCEPT_VALID : ULOC_ACCEPT_FALLBACK; 
+        } 
+        const char *bestStr = result.getSupportedLocale()->getName(); 
+        int32_t bestLength = (int32_t)uprv_strlen(bestStr); 
+        if (bestLength <= capacity) { 
+            uprv_memcpy(dest, bestStr, bestLength); 
+        } 
+        return u_terminateChars(dest, capacity, bestLength, &errorCode); 
+    } else { 
+        if (acceptResult != nullptr) { 
+            *acceptResult = ULOC_ACCEPT_FAILED; 
+        } 
+        return u_terminateChars(dest, capacity, 0, &errorCode); 
+    } 
+} 
+ 
+}  // namespace 
+ 
+U_CAPI int32_t U_EXPORT2 
+uloc_acceptLanguage(char *result, int32_t resultAvailable, 
+                    UAcceptResult *outResult, 
+                    const char **acceptList, int32_t acceptListCount, 
+                    UEnumeration *availableLocales, 
+                    UErrorCode *status) { 
+    if (U_FAILURE(*status)) { return 0; } 
+    if ((result == nullptr ? resultAvailable != 0 : resultAvailable < 0) || 
+            (acceptList == nullptr ? acceptListCount != 0 : acceptListCount < 0) || 
+            availableLocales == nullptr) { 
+        *status = U_ILLEGAL_ARGUMENT_ERROR; 
+        return 0; 
+    } 
+    LocaleFromTag converter; 
+    Locale::ConvertingIterator<const char **, LocaleFromTag> desiredLocales( 
+        acceptList, acceptList + acceptListCount, converter); 
+    return acceptLanguage(*availableLocales, desiredLocales, 
+                          result, resultAvailable, outResult, *status); 
+} 
+ 
+U_CAPI int32_t U_EXPORT2 
+uloc_acceptLanguageFromHTTP(char *result, int32_t resultAvailable, 
+                            UAcceptResult *outResult, 
+                            const char *httpAcceptLanguage, 
+                            UEnumeration *availableLocales, 
+                            UErrorCode *status) { 
+    if (U_FAILURE(*status)) { return 0; } 
+    if ((result == nullptr ? resultAvailable != 0 : resultAvailable < 0) || 
+            httpAcceptLanguage == nullptr || availableLocales == nullptr) { 
+        *status = U_ILLEGAL_ARGUMENT_ERROR; 
+        return 0; 
+    } 
+    LocalePriorityList list(httpAcceptLanguage, *status); 
+    LocalePriorityList::Iterator desiredLocales = list.iterator(); 
+    return acceptLanguage(*availableLocales, desiredLocales, 
+                          result, resultAvailable, outResult, *status); 
+} 
+ 
+#endif  // __LOCMATCHER_H__