icu4j/main/classes/core/src/com/ibm/icu/impl/locale/XLikelySubtags.java - external/github.com/unicode-org/icu - Git at Google

 // © 2017 and later: Unicode, Inc. and others.
 // License & terms of use: http://www.unicode.org/copyright.html
 package com.ibm.icu.impl.locale;

 import java.nio.ByteBuffer;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.Locale;
 import java.util.Map;
 import java.util.MissingResourceException;
 import java.util.TreeMap;

 import com.ibm.icu.impl.ICUData;
 import com.ibm.icu.impl.ICUResourceBundle;
 import com.ibm.icu.impl.UResource;
 import com.ibm.icu.util.BytesTrie;
 import com.ibm.icu.util.ULocale;

 public final class XLikelySubtags {
     private static final String PSEUDO_ACCENTS_PREFIX = "'";  // -XA, -PSACCENT
     private static final String PSEUDO_BIDI_PREFIX = "+";  // -XB, -PSBIDI
     private static final String PSEUDO_CRACKED_PREFIX = ",";  // -XC, -PSCRACK

     public static final int SKIP_SCRIPT = 1;

     private static final boolean DEBUG_OUTPUT = LSR.DEBUG_OUTPUT;

     // VisibleForTesting
     public static final class Data {
         public final Map<String, String> languageAliases;
         public final Map<String, String> regionAliases;
         public final byte[] trie;
         public final LSR[] lsrs;

         public Data(Map<String, String> languageAliases, Map<String, String> regionAliases,
                 byte[] trie, LSR[] lsrs) {
             this.languageAliases = languageAliases;
             this.regionAliases = regionAliases;
             this.trie = trie;
             this.lsrs = lsrs;
         }

         private static UResource.Value getValue(UResource.Table table,
                 String key, UResource.Value value) {
             if (!table.findValue(key, value)) {
                 throw new MissingResourceException(
                         "langInfo.res missing data", "", "likely/" + key);
             }
             return value;
         }

         // VisibleForTesting
         public static Data load() throws MissingResourceException {
             ICUResourceBundle langInfo = ICUResourceBundle.getBundleInstance(
                     ICUData.ICU_BASE_NAME, "langInfo",
                     ICUResourceBundle.ICU_DATA_CLASS_LOADER, ICUResourceBundle.OpenType.DIRECT);
             UResource.Value value = langInfo.getValueWithFallback("likely");
             UResource.Table likelyTable = value.getTable();

             Map<String, String> languageAliases;
             if (likelyTable.findValue("languageAliases", value)) {
                 String[] pairs = value.getStringArray();
                 languageAliases = new HashMap<>(pairs.length / 2);
                 for (int i = 0; i < pairs.length; i += 2) {
                     languageAliases.put(pairs[i], pairs[i + 1]);
                 }
             } else {
                 languageAliases = Collections.emptyMap();
             }

             Map<String, String> regionAliases;
             if (likelyTable.findValue("regionAliases", value)) {
                 String[] pairs = value.getStringArray();
                 regionAliases = new HashMap<>(pairs.length / 2);
                 for (int i = 0; i < pairs.length; i += 2) {
                     regionAliases.put(pairs[i], pairs[i + 1]);
                 }
             } else {
                 regionAliases = Collections.emptyMap();
             }

             ByteBuffer buffer = getValue(likelyTable, "trie", value).getBinary();
             byte[] trie = new byte[buffer.remaining()];
             buffer.get(trie);

             String[] lsrSubtags = getValue(likelyTable, "lsrs", value).getStringArray();
             LSR[] lsrs = new LSR[lsrSubtags.length / 3];
             for (int i = 0, j = 0; i < lsrSubtags.length; i += 3, ++j) {
                 lsrs[j] = new LSR(lsrSubtags[i], lsrSubtags[i + 1], lsrSubtags[i + 2],
                         LSR.IMPLICIT_LSR);
             }

             return new Data(languageAliases, regionAliases, trie, lsrs);
         }

         @Override
         public boolean equals(Object other) {
             if (this == other) { return true; }
             if (other == null || !getClass().equals(other.getClass())) { return false; }
             Data od = (Data)other;
             return
                     languageAliases.equals(od.languageAliases) &&
                     regionAliases.equals(od.regionAliases) &&
                     Arrays.equals(trie, od.trie) &&
                     Arrays.equals(lsrs, od.lsrs);
         }

         @Override
         public int hashCode() {  // unused; silence ErrorProne
             return 1;
         }
     }

     // VisibleForTesting
     public static final XLikelySubtags INSTANCE = new XLikelySubtags(Data.load());

     private final Map<String, String> languageAliases;
     private final Map<String, String> regionAliases;

     // The trie maps each lang+script+region (encoded in ASCII) to an index into lsrs.
     // There is also a trie value for each intermediate lang and lang+script.
     // '*' is used instead of "und", "Zzzz"/"" and "ZZ"/"".
     private final BytesTrie trie;
     private final long trieUndState;
     private final long trieUndZzzzState;
     private final int defaultLsrIndex;
     private final long[] trieFirstLetterStates = new long[26];
     private final LSR[] lsrs;

     private XLikelySubtags(XLikelySubtags.Data data) {
         languageAliases = data.languageAliases;
         regionAliases = data.regionAliases;
         trie = new BytesTrie(data.trie, 0);
         lsrs = data.lsrs;

         // Cache the result of looking up language="und" encoded as "*", and "und-Zzzz" ("**").
         BytesTrie.Result result = trie.next('*');
         assert result.hasNext();
         trieUndState = trie.getState64();
         result = trie.next('*');
         assert result.hasNext();
         trieUndZzzzState = trie.getState64();
         result = trie.next('*');
         assert result.hasValue();
         defaultLsrIndex = trie.getValue();
         trie.reset();

         for (char c = 'a'; c <= 'z'; ++c) {
             result = trie.next(c);
             if (result == BytesTrie.Result.NO_VALUE) {
                 trieFirstLetterStates[c - 'a'] = trie.getState64();
             }
             trie.reset();
         }

         if (DEBUG_OUTPUT) {
             System.out.println("*** likely subtags");
             for (Map.Entry<String, LSR> mapping : getTable().entrySet()) {
                 System.out.println(mapping);
             }
         }
     }

     /**
      * Implementation of LocaleMatcher.canonicalize(ULocale).
      */
     public ULocale canonicalize(ULocale locale) {
         String lang = locale.getLanguage();
         String lang2 = languageAliases.get(lang);
         String region = locale.getCountry();
         String region2 = regionAliases.get(region);
         if (lang2 != null || region2 != null) {
             return new ULocale(
                 lang2 == null ? lang : lang2,
                 locale.getScript(),
                 region2 == null ? region : region2);
         }
         return locale;
     }

     private static String getCanonical(Map<String, String> aliases, String alias) {
         String canonical = aliases.get(alias);
         return canonical == null ? alias : canonical;
     }

     // VisibleForTesting
     public LSR makeMaximizedLsrFrom(ULocale locale) {
         String name = locale.getName();  // Faster than .toLanguageTag().
         if (name.startsWith("@x=")) {
             String tag = locale.toLanguageTag();
             assert tag.startsWith("und-x-");
             // Private use language tag x-subtag-subtag... which CLDR changes to
             // und-x-subtag-subtag...
             return new LSR(tag, "", "", LSR.EXPLICIT_LSR);
         }
         return makeMaximizedLsr(locale.getLanguage(), locale.getScript(), locale.getCountry(),
                 locale.getVariant());
     }

     public LSR makeMaximizedLsrFrom(Locale locale) {
         String tag = locale.toLanguageTag();
         if (tag.startsWith("x-") || tag.startsWith("und-x-")) {
             // Private use language tag x-subtag-subtag... which CLDR changes to
             // und-x-subtag-subtag...
             return new LSR(tag, "", "", LSR.EXPLICIT_LSR);
         }
         return makeMaximizedLsr(locale.getLanguage(), locale.getScript(), locale.getCountry(),
                 locale.getVariant());
     }

     private LSR makeMaximizedLsr(String language, String script, String region, String variant) {
         // Handle pseudolocales like en-XA, ar-XB, fr-PSCRACK.
         // They should match only themselves,
         // not other locales with what looks like the same language and script subtags.
         if (region.length() == 2 && region.charAt(0) == 'X') {
             switch (region.charAt(1)) {
             case 'A':
                 return new LSR(PSEUDO_ACCENTS_PREFIX + language,
                         PSEUDO_ACCENTS_PREFIX + script, region, LSR.EXPLICIT_LSR);
             case 'B':
                 return new LSR(PSEUDO_BIDI_PREFIX + language,
                         PSEUDO_BIDI_PREFIX + script, region, LSR.EXPLICIT_LSR);
             case 'C':
                 return new LSR(PSEUDO_CRACKED_PREFIX + language,
                         PSEUDO_CRACKED_PREFIX + script, region, LSR.EXPLICIT_LSR);
             default:  // normal locale
                 break;
             }
         }

         if (variant.startsWith("PS")) {
             int lsrFlags = region.isEmpty() ?
                     LSR.EXPLICIT_LANGUAGE | LSR.EXPLICIT_SCRIPT : LSR.EXPLICIT_LSR;
             switch (variant) {
             case "PSACCENT":
                 return new LSR(PSEUDO_ACCENTS_PREFIX + language,
                         PSEUDO_ACCENTS_PREFIX + script,
                         region.isEmpty() ? "XA" : region, lsrFlags);
             case "PSBIDI":
                 return new LSR(PSEUDO_BIDI_PREFIX + language,
                         PSEUDO_BIDI_PREFIX + script,
                         region.isEmpty() ? "XB" : region, lsrFlags);
             case "PSCRACK":
                 return new LSR(PSEUDO_CRACKED_PREFIX + language,
                         PSEUDO_CRACKED_PREFIX + script,
                         region.isEmpty() ? "XC" : region, lsrFlags);
             default:  // normal locale
                 break;
             }
         }

         language = getCanonical(languageAliases, language);
         // (We have no script mappings.)
         region = getCanonical(regionAliases, region);
         return maximize(language, script, region);
     }

     /**
      * Raw access to addLikelySubtags. Input must be in canonical format, eg "en", not "eng" or "EN".
      */
     private LSR maximize(String language, String script, String region) {
         if (language.equals("und")) {
             language = "";
         }
         if (script.equals("Zzzz")) {
             script = "";
         }
         if (region.equals("ZZ")) {
             region = "";
         }
         if (!script.isEmpty() && !region.isEmpty() && !language.isEmpty()) {
             return new LSR(language, script, region, LSR.EXPLICIT_LSR);  // already maximized
         }

         int retainOldMask = 0;
         BytesTrie iter = new BytesTrie(trie);
         long state;
         int value;
         // Small optimization: Array lookup for first language letter.
         int c0;
         if (language.length() >= 2 && 0 <= (c0 = language.charAt(0) - 'a') && c0 <= 25 &&
                 (state = trieFirstLetterStates[c0]) != 0) {
             value = trieNext(iter.resetToState64(state), language, 1);
         } else {
             value = trieNext(iter, language, 0);
         }
         if (value >= 0) {
             if (!language.isEmpty()) {
                 retainOldMask |= 4;
             }
             state = iter.getState64();
         } else {
             retainOldMask |= 4;
             iter.resetToState64(trieUndState);  // "und" ("*")
             state = 0;
         }

         if (value > 0) {
             // Intermediate or final value from just language.
             if (value == SKIP_SCRIPT) {
                 value = 0;
             }
             if (!script.isEmpty()) {
                 retainOldMask |= 2;
             }
         } else {
             value = trieNext(iter, script, 0);
             if (value >= 0) {
                 if (!script.isEmpty()) {
                     retainOldMask |= 2;
                 }
                 state = iter.getState64();
             } else {
                 retainOldMask |= 2;
                 if (state == 0) {
                     iter.resetToState64(trieUndZzzzState);  // "und-Zzzz" ("**")
                 } else {
                     iter.resetToState64(state);
                     value = trieNext(iter, "", 0);
                     assert value >= 0;
                     state = iter.getState64();
                 }
             }
         }

         if (value > 0) {
             // Final value from just language or language+script.
             if (!region.isEmpty()) {
                 retainOldMask |= 1;
             }
         } else {
             value = trieNext(iter, region, 0);
             if (value >= 0) {
                 if (!region.isEmpty()) {
                     retainOldMask |= 1;
                 }
             } else {
                 retainOldMask |= 1;
                 if (state == 0) {
                     value = defaultLsrIndex;
                 } else {
                     iter.resetToState64(state);
                     value = trieNext(iter, "", 0);
                     assert value > 0;
                 }
             }
         }
         LSR result = lsrs[value];

         if (language.isEmpty()) {
             language = "und";
         }

         if (retainOldMask == 0) {
             assert result.flags == LSR.IMPLICIT_LSR;
             return result;
         }
         if ((retainOldMask & 4) == 0) {
             language = result.language;
         }
         if ((retainOldMask & 2) == 0) {
             script = result.script;
         }
         if ((retainOldMask & 1) == 0) {
             region = result.region;
         }
         // retainOldMask flags = LSR explicit-subtag flags
         return new LSR(language, script, region, retainOldMask);
     }

     /**
      * Tests whether lsr is "more likely" than other.
      * For example, fr-Latn-FR is more likely than fr-Latn-CH because
      * FR is the default region for fr-Latn.
      *
      * <p>The likelyInfo caches lookup information between calls.
      * The return value is an updated likelyInfo value,
      * with bit 0 set if lsr is "more likely".
      * The initial value of likelyInfo must be negative.
      */
     int compareLikely(LSR lsr, LSR other, int likelyInfo) {
         // If likelyInfo >= 0:
         // likelyInfo bit 1 is set if the previous comparison with lsr
         // was for equal language and script.
         // Otherwise the scripts differed.
         if (!lsr.language.equals(other.language)) {
             return 0xfffffffc;  // negative, lsr not better than other
         }
         if (!lsr.script.equals(other.script)) {
             int index;
             if (likelyInfo >= 0 && (likelyInfo & 2) == 0) {
                 index = likelyInfo >> 2;
             } else {
                 index = getLikelyIndex(lsr.language, "");
                 likelyInfo = index << 2;
             }
             LSR likely = lsrs[index];
             if (lsr.script.equals(likely.script)) {
                 return likelyInfo | 1;
             } else {
                 return likelyInfo & ~1;
             }
         }
         if (!lsr.region.equals(other.region)) {
             int index;
             if (likelyInfo >= 0 && (likelyInfo & 2) != 0) {
                 index = likelyInfo >> 2;
             } else {
                 index = getLikelyIndex(lsr.language, lsr.region);
                 likelyInfo = (index << 2) | 2;
             }
             LSR likely = lsrs[index];
             if (lsr.region.equals(likely.region)) {
                 return likelyInfo | 1;
             } else {
                 return likelyInfo & ~1;
             }
         }
         return likelyInfo & ~1;  // lsr not better than other
     }

     // Subset of maximize().
     private int getLikelyIndex(String language, String script) {
         if (language.equals("und")) {
             language = "";
         }
         if (script.equals("Zzzz")) {
             script = "";
         }

         BytesTrie iter = new BytesTrie(trie);
         long state;
         int value;
         // Small optimization: Array lookup for first language letter.
         int c0;
         if (language.length() >= 2 && 0 <= (c0 = language.charAt(0) - 'a') && c0 <= 25 &&
                 (state = trieFirstLetterStates[c0]) != 0) {
             value = trieNext(iter.resetToState64(state), language, 1);
         } else {
             value = trieNext(iter, language, 0);
         }
         if (value >= 0) {
             state = iter.getState64();
         } else {
             iter.resetToState64(trieUndState);  // "und" ("*")
             state = 0;
         }

         if (value > 0) {
             // Intermediate or final value from just language.
             if (value == SKIP_SCRIPT) {
                 value = 0;
             }
         } else {
             value = trieNext(iter, script, 0);
             if (value >= 0) {
                 state = iter.getState64();
             } else {
                 if (state == 0) {
                     iter.resetToState64(trieUndZzzzState);  // "und-Zzzz" ("**")
                 } else {
                     iter.resetToState64(state);
                     value = trieNext(iter, "", 0);
                     assert value >= 0;
                     state = iter.getState64();
                 }
             }
         }

         if (value > 0) {
             // Final value from just language or language+script.
         } else {
             value = trieNext(iter, "", 0);
             assert value > 0;
         }
         return value;
     }

     private static final int trieNext(BytesTrie iter, String s, int i) {
         BytesTrie.Result result;
         if (s.isEmpty()) {
             result = iter.next('*');
         } else {
             int end = s.length() - 1;
             for (;; ++i) {
                 int c = s.charAt(i);
                 if (i < end) {
                     if (!iter.next(c).hasNext()) {
                         return -1;
                     }
                 } else {
                     // last character of this subtag
                     result = iter.next(c | 0x80);
                     break;
                 }
             }
         }
         switch (result) {
         case NO_MATCH: return -1;
         case NO_VALUE: return 0;
         case INTERMEDIATE_VALUE:
             assert iter.getValue() == SKIP_SCRIPT;
             return SKIP_SCRIPT;
         case FINAL_VALUE: return iter.getValue();
         default: return -1;
         }
     }

     LSR minimizeSubtags(String languageIn, String scriptIn, String regionIn,
             ULocale.Minimize fieldToFavor) {
         LSR result = maximize(languageIn, scriptIn, regionIn);

         // We could try just a series of checks, like:
         // LSR result2 = addLikelySubtags(languageIn, "", "");
         // if result.equals(result2) return result2;
         // However, we can optimize 2 of the cases:
         //   (languageIn, "", "")
         //   (languageIn, "", regionIn)

         // value00 = lookup(result.language, "", "")
         BytesTrie iter = new BytesTrie(trie);
         int value = trieNext(iter, result.language, 0);
         assert value >= 0;
         if (value == 0) {
             value = trieNext(iter, "", 0);
             assert value >= 0;
             if (value == 0) {
                 value = trieNext(iter, "", 0);
             }
         }
         assert value > 0;
         LSR value00 = lsrs[value];
         boolean favorRegionOk = false;
         if (result.script.equals(value00.script)) { //script is default
             if (result.region.equals(value00.region)) {
                 return new LSR(result.language, "", "", LSR.DONT_CARE_FLAGS);
             } else if (fieldToFavor == ULocale.Minimize.FAVOR_REGION) {
                 return new LSR(result.language, "", result.region, LSR.DONT_CARE_FLAGS);
             } else {
                 favorRegionOk = true;
             }
         }

         // The last case is not as easy to optimize.
         // Maybe do later, but for now use the straightforward code.
         LSR result2 = maximize(languageIn, scriptIn, "");
         if (result2.equals(result)) {
             return new LSR(result.language, result.script, "", LSR.DONT_CARE_FLAGS);
         } else if (favorRegionOk) {
             return new LSR(result.language, "", result.region, LSR.DONT_CARE_FLAGS);
         }
         return result;
     }

     private Map<String, LSR> getTable() {
         Map<String, LSR> map = new TreeMap<>();
         StringBuilder sb = new StringBuilder();
         for (BytesTrie.Entry entry : trie) {
             sb.setLength(0);
             int length = entry.bytesLength();
             for (int i = 0; i < length;) {
                 byte b = entry.byteAt(i++);
                 if (b == '*') {
                     sb.append("*-");
                 } else if (b >= 0) {
                     sb.append((char) b);
                 } else {  // end of subtag
                     sb.append((char) (b & 0x7f)).append('-');
                 }
             }
             assert sb.length() > 0 && sb.charAt(sb.length() - 1) == '-';
             sb.setLength(sb.length() - 1);
             map.put(sb.toString(), lsrs[entry.value]);
         }
         return map;
     }

     @Override
     public String toString() {
         return getTable().toString();
     }
 }
	// © 2017 and later: Unicode, Inc. and others.
	// License & terms of use: http://www.unicode.org/copyright.html
	package com.ibm.icu.impl.locale;

	import java.nio.ByteBuffer;
	import java.util.Arrays;
	import java.util.Collections;
	import java.util.HashMap;
	import java.util.Locale;
	import java.util.Map;
	import java.util.MissingResourceException;
	import java.util.TreeMap;

	import com.ibm.icu.impl.ICUData;
	import com.ibm.icu.impl.ICUResourceBundle;
	import com.ibm.icu.impl.UResource;
	import com.ibm.icu.util.BytesTrie;
	import com.ibm.icu.util.ULocale;

	public final class XLikelySubtags {
	private static final String PSEUDO_ACCENTS_PREFIX = "'"; // -XA, -PSACCENT
	private static final String PSEUDO_BIDI_PREFIX = "+"; // -XB, -PSBIDI
	private static final String PSEUDO_CRACKED_PREFIX = ","; // -XC, -PSCRACK

	public static final int SKIP_SCRIPT = 1;

	private static final boolean DEBUG_OUTPUT = LSR.DEBUG_OUTPUT;

	// VisibleForTesting
	public static final class Data {
	public final Map<String, String> languageAliases;
	public final Map<String, String> regionAliases;
	public final byte[] trie;
	public final LSR[] lsrs;

	public Data(Map<String, String> languageAliases, Map<String, String> regionAliases,
	byte[] trie, LSR[] lsrs) {
	this.languageAliases = languageAliases;
	this.regionAliases = regionAliases;
	this.trie = trie;
	this.lsrs = lsrs;
	}

	private static UResource.Value getValue(UResource.Table table,
	String key, UResource.Value value) {
	if (!table.findValue(key, value)) {
	throw new MissingResourceException(
	"langInfo.res missing data", "", "likely/" + key);
	}
	return value;
	}

	// VisibleForTesting
	public static Data load() throws MissingResourceException {
	ICUResourceBundle langInfo = ICUResourceBundle.getBundleInstance(
	ICUData.ICU_BASE_NAME, "langInfo",
	ICUResourceBundle.ICU_DATA_CLASS_LOADER, ICUResourceBundle.OpenType.DIRECT);
	UResource.Value value = langInfo.getValueWithFallback("likely");
	UResource.Table likelyTable = value.getTable();

	Map<String, String> languageAliases;
	if (likelyTable.findValue("languageAliases", value)) {
	String[] pairs = value.getStringArray();
	languageAliases = new HashMap<>(pairs.length / 2);
	for (int i = 0; i < pairs.length; i += 2) {
	languageAliases.put(pairs[i], pairs[i + 1]);
	}
	} else {
	languageAliases = Collections.emptyMap();
	}

	Map<String, String> regionAliases;
	if (likelyTable.findValue("regionAliases", value)) {
	String[] pairs = value.getStringArray();
	regionAliases = new HashMap<>(pairs.length / 2);
	for (int i = 0; i < pairs.length; i += 2) {
	regionAliases.put(pairs[i], pairs[i + 1]);
	}
	} else {
	regionAliases = Collections.emptyMap();
	}

	ByteBuffer buffer = getValue(likelyTable, "trie", value).getBinary();
	byte[] trie = new byte[buffer.remaining()];
	buffer.get(trie);

	String[] lsrSubtags = getValue(likelyTable, "lsrs", value).getStringArray();
	LSR[] lsrs = new LSR[lsrSubtags.length / 3];
	for (int i = 0, j = 0; i < lsrSubtags.length; i += 3, ++j) {
	lsrs[j] = new LSR(lsrSubtags[i], lsrSubtags[i + 1], lsrSubtags[i + 2],
	LSR.IMPLICIT_LSR);
	}

	return new Data(languageAliases, regionAliases, trie, lsrs);
	}

	@Override
	public boolean equals(Object other) {
	if (this == other) { return true; }
	if (other == null \|\| !getClass().equals(other.getClass())) { return false; }
	Data od = (Data)other;
	return
	languageAliases.equals(od.languageAliases) &&
	regionAliases.equals(od.regionAliases) &&
	Arrays.equals(trie, od.trie) &&
	Arrays.equals(lsrs, od.lsrs);
	}

	@Override
	public int hashCode() { // unused; silence ErrorProne
	return 1;
	}
	}

	// VisibleForTesting
	public static final XLikelySubtags INSTANCE = new XLikelySubtags(Data.load());

	private final Map<String, String> languageAliases;
	private final Map<String, String> regionAliases;

	// The trie maps each lang+script+region (encoded in ASCII) to an index into lsrs.
	// There is also a trie value for each intermediate lang and lang+script.
	// '*' is used instead of "und", "Zzzz"/"" and "ZZ"/"".
	private final BytesTrie trie;
	private final long trieUndState;
	private final long trieUndZzzzState;
	private final int defaultLsrIndex;
	private final long[] trieFirstLetterStates = new long[26];
	private final LSR[] lsrs;

	private XLikelySubtags(XLikelySubtags.Data data) {
	languageAliases = data.languageAliases;
	regionAliases = data.regionAliases;
	trie = new BytesTrie(data.trie, 0);
	lsrs = data.lsrs;

	// Cache the result of looking up language="und" encoded as "", and "und-Zzzz" ("*").
	BytesTrie.Result result = trie.next('*');
	assert result.hasNext();
	trieUndState = trie.getState64();
	result = trie.next('*');
	assert result.hasNext();
	trieUndZzzzState = trie.getState64();
	result = trie.next('*');
	assert result.hasValue();
	defaultLsrIndex = trie.getValue();
	trie.reset();

	for (char c = 'a'; c <= 'z'; ++c) {
	result = trie.next(c);
	if (result == BytesTrie.Result.NO_VALUE) {
	trieFirstLetterStates[c - 'a'] = trie.getState64();
	}
	trie.reset();
	}

	if (DEBUG_OUTPUT) {
	System.out.println("*** likely subtags");
	for (Map.Entry<String, LSR> mapping : getTable().entrySet()) {
	System.out.println(mapping);
	}
	}
	}

	/**
	* Implementation of LocaleMatcher.canonicalize(ULocale).
	*/
	public ULocale canonicalize(ULocale locale) {
	String lang = locale.getLanguage();
	String lang2 = languageAliases.get(lang);
	String region = locale.getCountry();
	String region2 = regionAliases.get(region);
	if (lang2 != null \|\| region2 != null) {
	return new ULocale(
	lang2 == null ? lang : lang2,
	locale.getScript(),
	region2 == null ? region : region2);
	}
	return locale;
	}

	private static String getCanonical(Map<String, String> aliases, String alias) {
	String canonical = aliases.get(alias);
	return canonical == null ? alias : canonical;
	}

	// VisibleForTesting
	public LSR makeMaximizedLsrFrom(ULocale locale) {
	String name = locale.getName(); // Faster than .toLanguageTag().
	if (name.startsWith("@x=")) {
	String tag = locale.toLanguageTag();
	assert tag.startsWith("und-x-");
	// Private use language tag x-subtag-subtag... which CLDR changes to
	// und-x-subtag-subtag...
	return new LSR(tag, "", "", LSR.EXPLICIT_LSR);
	}
	return makeMaximizedLsr(locale.getLanguage(), locale.getScript(), locale.getCountry(),
	locale.getVariant());
	}

	public LSR makeMaximizedLsrFrom(Locale locale) {
	String tag = locale.toLanguageTag();
	if (tag.startsWith("x-") \|\| tag.startsWith("und-x-")) {
	// Private use language tag x-subtag-subtag... which CLDR changes to
	// und-x-subtag-subtag...
	return new LSR(tag, "", "", LSR.EXPLICIT_LSR);
	}
	return makeMaximizedLsr(locale.getLanguage(), locale.getScript(), locale.getCountry(),
	locale.getVariant());
	}

	private LSR makeMaximizedLsr(String language, String script, String region, String variant) {
	// Handle pseudolocales like en-XA, ar-XB, fr-PSCRACK.
	// They should match only themselves,
	// not other locales with what looks like the same language and script subtags.
	if (region.length() == 2 && region.charAt(0) == 'X') {
	switch (region.charAt(1)) {
	case 'A':
	return new LSR(PSEUDO_ACCENTS_PREFIX + language,
	PSEUDO_ACCENTS_PREFIX + script, region, LSR.EXPLICIT_LSR);
	case 'B':
	return new LSR(PSEUDO_BIDI_PREFIX + language,
	PSEUDO_BIDI_PREFIX + script, region, LSR.EXPLICIT_LSR);
	case 'C':
	return new LSR(PSEUDO_CRACKED_PREFIX + language,
	PSEUDO_CRACKED_PREFIX + script, region, LSR.EXPLICIT_LSR);
	default: // normal locale
	break;
	}
	}

	if (variant.startsWith("PS")) {
	int lsrFlags = region.isEmpty() ?
	LSR.EXPLICIT_LANGUAGE \| LSR.EXPLICIT_SCRIPT : LSR.EXPLICIT_LSR;
	switch (variant) {
	case "PSACCENT":
	return new LSR(PSEUDO_ACCENTS_PREFIX + language,
	PSEUDO_ACCENTS_PREFIX + script,
	region.isEmpty() ? "XA" : region, lsrFlags);
	case "PSBIDI":
	return new LSR(PSEUDO_BIDI_PREFIX + language,
	PSEUDO_BIDI_PREFIX + script,
	region.isEmpty() ? "XB" : region, lsrFlags);
	case "PSCRACK":
	return new LSR(PSEUDO_CRACKED_PREFIX + language,
	PSEUDO_CRACKED_PREFIX + script,
	region.isEmpty() ? "XC" : region, lsrFlags);
	default: // normal locale
	break;
	}
	}

	language = getCanonical(languageAliases, language);
	// (We have no script mappings.)
	region = getCanonical(regionAliases, region);
	return maximize(language, script, region);
	}

	/**
	* Raw access to addLikelySubtags. Input must be in canonical format, eg "en", not "eng" or "EN".
	*/
	private LSR maximize(String language, String script, String region) {
	if (language.equals("und")) {
	language = "";
	}
	if (script.equals("Zzzz")) {
	script = "";
	}
	if (region.equals("ZZ")) {
	region = "";
	}
	if (!script.isEmpty() && !region.isEmpty() && !language.isEmpty()) {
	return new LSR(language, script, region, LSR.EXPLICIT_LSR); // already maximized
	}

	int retainOldMask = 0;
	BytesTrie iter = new BytesTrie(trie);
	long state;
	int value;
	// Small optimization: Array lookup for first language letter.
	int c0;
	if (language.length() >= 2 && 0 <= (c0 = language.charAt(0) - 'a') && c0 <= 25 &&
	(state = trieFirstLetterStates[c0]) != 0) {
	value = trieNext(iter.resetToState64(state), language, 1);
	} else {
	value = trieNext(iter, language, 0);
	}
	if (value >= 0) {
	if (!language.isEmpty()) {
	retainOldMask \|= 4;
	}
	state = iter.getState64();
	} else {
	retainOldMask \|= 4;
	iter.resetToState64(trieUndState); // "und" ("*")
	state = 0;
	}

	if (value > 0) {
	// Intermediate or final value from just language.
	if (value == SKIP_SCRIPT) {
	value = 0;
	}
	if (!script.isEmpty()) {
	retainOldMask \|= 2;
	}
	} else {
	value = trieNext(iter, script, 0);
	if (value >= 0) {
	if (!script.isEmpty()) {
	retainOldMask \|= 2;
	}
	state = iter.getState64();
	} else {
	retainOldMask \|= 2;
	if (state == 0) {
	iter.resetToState64(trieUndZzzzState); // "und-Zzzz" ("**")
	} else {
	iter.resetToState64(state);
	value = trieNext(iter, "", 0);
	assert value >= 0;
	state = iter.getState64();
	}
	}
	}

	if (value > 0) {
	// Final value from just language or language+script.
	if (!region.isEmpty()) {
	retainOldMask \|= 1;
	}
	} else {
	value = trieNext(iter, region, 0);
	if (value >= 0) {
	if (!region.isEmpty()) {
	retainOldMask \|= 1;
	}
	} else {
	retainOldMask \|= 1;
	if (state == 0) {
	value = defaultLsrIndex;
	} else {
	iter.resetToState64(state);
	value = trieNext(iter, "", 0);
	assert value > 0;
	}
	}
	}
	LSR result = lsrs[value];

	if (language.isEmpty()) {
	language = "und";
	}

	if (retainOldMask == 0) {
	assert result.flags == LSR.IMPLICIT_LSR;
	return result;
	}
	if ((retainOldMask & 4) == 0) {
	language = result.language;
	}
	if ((retainOldMask & 2) == 0) {
	script = result.script;
	}
	if ((retainOldMask & 1) == 0) {
	region = result.region;
	}
	// retainOldMask flags = LSR explicit-subtag flags
	return new LSR(language, script, region, retainOldMask);
	}

	/**
	* Tests whether lsr is "more likely" than other.
	* For example, fr-Latn-FR is more likely than fr-Latn-CH because
	* FR is the default region for fr-Latn.
	*
	* <p>The likelyInfo caches lookup information between calls.
	* The return value is an updated likelyInfo value,
	* with bit 0 set if lsr is "more likely".
	* The initial value of likelyInfo must be negative.
	*/
	int compareLikely(LSR lsr, LSR other, int likelyInfo) {
	// If likelyInfo >= 0:
	// likelyInfo bit 1 is set if the previous comparison with lsr
	// was for equal language and script.
	// Otherwise the scripts differed.
	if (!lsr.language.equals(other.language)) {
	return 0xfffffffc; // negative, lsr not better than other
	}
	if (!lsr.script.equals(other.script)) {
	int index;
	if (likelyInfo >= 0 && (likelyInfo & 2) == 0) {
	index = likelyInfo >> 2;
	} else {
	index = getLikelyIndex(lsr.language, "");
	likelyInfo = index << 2;
	}
	LSR likely = lsrs[index];
	if (lsr.script.equals(likely.script)) {
	return likelyInfo \| 1;
	} else {
	return likelyInfo & ~1;
	}
	}
	if (!lsr.region.equals(other.region)) {
	int index;
	if (likelyInfo >= 0 && (likelyInfo & 2) != 0) {
	index = likelyInfo >> 2;
	} else {
	index = getLikelyIndex(lsr.language, lsr.region);
	likelyInfo = (index << 2) \| 2;
	}
	LSR likely = lsrs[index];
	if (lsr.region.equals(likely.region)) {
	return likelyInfo \| 1;
	} else {
	return likelyInfo & ~1;
	}
	}
	return likelyInfo & ~1; // lsr not better than other
	}

	// Subset of maximize().
	private int getLikelyIndex(String language, String script) {
	if (language.equals("und")) {
	language = "";
	}
	if (script.equals("Zzzz")) {
	script = "";
	}

	BytesTrie iter = new BytesTrie(trie);
	long state;
	int value;
	// Small optimization: Array lookup for first language letter.
	int c0;
	if (language.length() >= 2 && 0 <= (c0 = language.charAt(0) - 'a') && c0 <= 25 &&
	(state = trieFirstLetterStates[c0]) != 0) {
	value = trieNext(iter.resetToState64(state), language, 1);
	} else {
	value = trieNext(iter, language, 0);
	}
	if (value >= 0) {
	state = iter.getState64();
	} else {
	iter.resetToState64(trieUndState); // "und" ("*")
	state = 0;
	}

	if (value > 0) {
	// Intermediate or final value from just language.
	if (value == SKIP_SCRIPT) {
	value = 0;
	}
	} else {
	value = trieNext(iter, script, 0);
	if (value >= 0) {
	state = iter.getState64();
	} else {
	if (state == 0) {
	iter.resetToState64(trieUndZzzzState); // "und-Zzzz" ("**")
	} else {
	iter.resetToState64(state);
	value = trieNext(iter, "", 0);
	assert value >= 0;
	state = iter.getState64();
	}
	}
	}

	if (value > 0) {
	// Final value from just language or language+script.
	} else {
	value = trieNext(iter, "", 0);
	assert value > 0;
	}
	return value;
	}

	private static final int trieNext(BytesTrie iter, String s, int i) {
	BytesTrie.Result result;
	if (s.isEmpty()) {
	result = iter.next('*');
	} else {
	int end = s.length() - 1;
	for (;; ++i) {
	int c = s.charAt(i);
	if (i < end) {
	if (!iter.next(c).hasNext()) {
	return -1;
	}
	} else {
	// last character of this subtag
	result = iter.next(c \| 0x80);
	break;
	}
	}
	}
	switch (result) {
	case NO_MATCH: return -1;
	case NO_VALUE: return 0;
	case INTERMEDIATE_VALUE:
	assert iter.getValue() == SKIP_SCRIPT;
	return SKIP_SCRIPT;
	case FINAL_VALUE: return iter.getValue();
	default: return -1;
	}
	}

	LSR minimizeSubtags(String languageIn, String scriptIn, String regionIn,
	ULocale.Minimize fieldToFavor) {
	LSR result = maximize(languageIn, scriptIn, regionIn);

	// We could try just a series of checks, like:
	// LSR result2 = addLikelySubtags(languageIn, "", "");
	// if result.equals(result2) return result2;
	// However, we can optimize 2 of the cases:
	// (languageIn, "", "")
	// (languageIn, "", regionIn)

	// value00 = lookup(result.language, "", "")
	BytesTrie iter = new BytesTrie(trie);
	int value = trieNext(iter, result.language, 0);
	assert value >= 0;
	if (value == 0) {
	value = trieNext(iter, "", 0);
	assert value >= 0;
	if (value == 0) {
	value = trieNext(iter, "", 0);
	}
	}
	assert value > 0;
	LSR value00 = lsrs[value];
	boolean favorRegionOk = false;
	if (result.script.equals(value00.script)) { //script is default
	if (result.region.equals(value00.region)) {
	return new LSR(result.language, "", "", LSR.DONT_CARE_FLAGS);
	} else if (fieldToFavor == ULocale.Minimize.FAVOR_REGION) {
	return new LSR(result.language, "", result.region, LSR.DONT_CARE_FLAGS);
	} else {
	favorRegionOk = true;
	}
	}

	// The last case is not as easy to optimize.
	// Maybe do later, but for now use the straightforward code.
	LSR result2 = maximize(languageIn, scriptIn, "");
	if (result2.equals(result)) {
	return new LSR(result.language, result.script, "", LSR.DONT_CARE_FLAGS);
	} else if (favorRegionOk) {
	return new LSR(result.language, "", result.region, LSR.DONT_CARE_FLAGS);
	}
	return result;
	}

	private Map<String, LSR> getTable() {
	Map<String, LSR> map = new TreeMap<>();
	StringBuilder sb = new StringBuilder();
	for (BytesTrie.Entry entry : trie) {
	sb.setLength(0);
	int length = entry.bytesLength();
	for (int i = 0; i < length;) {
	byte b = entry.byteAt(i++);
	if (b == '*') {
	sb.append("*-");
	} else if (b >= 0) {
	sb.append((char) b);
	} else { // end of subtag
	sb.append((char) (b & 0x7f)).append('-');
	}
	}
	assert sb.length() > 0 && sb.charAt(sb.length() - 1) == '-';
	sb.setLength(sb.length() - 1);
	map.put(sb.toString(), lsrs[entry.value]);
	}
	return map;
	}

	@Override
	public String toString() {
	return getTable().toString();
	}
	}