1/*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.internal.inputmethod;
18
19import com.android.internal.annotations.VisibleForTesting;
20
21import android.annotation.IntRange;
22import android.annotation.NonNull;
23import android.annotation.Nullable;
24import android.icu.util.ULocale;
25import android.os.LocaleList;
26import android.text.TextUtils;
27
28import java.util.ArrayList;
29import java.util.Arrays;
30import java.util.HashMap;
31import java.util.List;
32import java.util.Locale;
33
34public final class LocaleUtils {
35
36    @VisibleForTesting
37    public interface LocaleExtractor<T> {
38        @Nullable
39        Locale get(@Nullable T source);
40    }
41
42    /**
43     * Calculates a matching score for the single desired locale.
44     *
45     * @see LocaleUtils#filterByLanguage(List, LocaleExtractor, LocaleList, ArrayList)
46     *
47     * @param supported The locale supported by IME subtype.
48     * @param desired The locale preferred by user.
49     * @return A score based on the locale matching for the default subtype enabling.
50     */
51    @IntRange(from=1, to=3)
52    private static byte calculateMatchingSubScore(@NonNull final ULocale supported,
53            @NonNull final ULocale desired) {
54        // Assuming supported/desired is fully expanded.
55        if (supported.equals(desired)) {
56            return 3;  // Exact match.
57        }
58
59        // Skip language matching since it was already done in calculateMatchingScore.
60
61        final String supportedScript = supported.getScript();
62        if (supportedScript.isEmpty() || !supportedScript.equals(desired.getScript())) {
63            // TODO: Need subscript matching. For example, Hanb should match with Bopo.
64            return 1;
65        }
66
67        final String supportedCountry = supported.getCountry();
68        if (supportedCountry.isEmpty() || !supportedCountry.equals(desired.getCountry())) {
69            return 2;
70        }
71
72        // Ignore others e.g. variants, extensions.
73        return 3;
74    }
75
76    private static final class ScoreEntry implements Comparable<ScoreEntry> {
77        public int mIndex = -1;
78        @NonNull public final byte[] mScore;  // matching score of the i-th system languages.
79
80        ScoreEntry(@NonNull byte[] score, int index) {
81            mScore = new byte[score.length];
82            set(score, index);
83        }
84
85        private void set(@NonNull byte[] score, int index) {
86            for (int i = 0; i < mScore.length; ++i) {
87                mScore[i] = score[i];
88            }
89            mIndex = index;
90        }
91
92        /**
93         * Update score and index if the given score is better than this.
94         */
95        public void updateIfBetter(@NonNull byte[] score, int index) {
96            if (compare(mScore, score) == -1) {  // mScore < score
97                set(score, index);
98            }
99        }
100
101        /**
102         * Provides comaprison for bytes[].
103         *
104         * <p> Comparison does as follows. If the first value of {@code left} is larger than the
105         * first value of {@code right}, {@code left} is large than {@code right}.  If the first
106         * value of {@code left} is less than the first value of {@code right}, {@code left} is less
107         * than {@code right}. If the first value of {@code left} and the first value of
108         * {@code right} is equal, do the same comparison to the next value. Finally if all values
109         * in {@code left} and {@code right} are equal, {@code left} and {@code right} is equal.</p>
110         *
111         * @param left The length must be equal to {@code right}.
112         * @param right The length must be equal to {@code left}.
113         * @return 1 if {@code left} is larger than {@code right}. -1 if {@code left} is less than
114         * {@code right}. 0 if {@code left} and {@code right} is equal.
115         */
116        @IntRange(from=-1, to=1)
117        private static int compare(@NonNull byte[] left, @NonNull byte[] right) {
118            for (int i = 0; i < left.length; ++i) {
119                if (left[i] > right[i]) {
120                    return 1;
121                } else if (left[i] < right[i]) {
122                    return -1;
123                }
124            }
125            return 0;
126        }
127
128        @Override
129        public int compareTo(final ScoreEntry other) {
130            return -1 * compare(mScore, other.mScore);  // Order by descending order.
131        }
132    }
133
134    /**
135     * Filters the given items based on language preferences.
136     *
137     * <p>For each language found in {@code preferredLocales}, this method tries to copy at most
138     * one best-match item from {@code source} to {@code dest}.  For example, if
139     * {@code "en-GB", "ja", "en-AU", "fr-CA", "en-IN"} is specified to {@code preferredLocales},
140     * this method tries to copy at most one English locale, at most one Japanese, and at most one
141     * French locale from {@code source} to {@code dest}.  Here the best matching English locale
142     * will be searched from {@code source} based on matching score. For the score design, see
143     * {@link LocaleUtils#calculateMatchingSubScore(ULocale, ULocale)}</p>
144     *
145     * @param sources Source items to be filtered.
146     * @param extractor Type converter from the source items to {@link Locale} object.
147     * @param preferredLocales Ordered list of locales with which the input items will be
148     * filtered.
149     * @param dest Destination into which the filtered items will be added.
150     * @param <T> Type of the data items.
151     */
152    @VisibleForTesting
153    public static <T> void filterByLanguage(
154            @NonNull List<T> sources,
155            @NonNull LocaleExtractor<T> extractor,
156            @NonNull LocaleList preferredLocales,
157            @NonNull ArrayList<T> dest) {
158        if (preferredLocales.isEmpty()) {
159            return;
160        }
161
162        final int numPreferredLocales = preferredLocales.size();
163        final HashMap<String, ScoreEntry> scoreboard = new HashMap<>();
164        final byte[] score = new byte[numPreferredLocales];
165        final ULocale[] preferredULocaleCache = new ULocale[numPreferredLocales];
166
167        final int sourceSize = sources.size();
168        for (int i = 0; i < sourceSize; ++i) {
169            final Locale locale = extractor.get(sources.get(i));
170            if (locale == null) {
171                continue;
172            }
173
174            boolean canSkip = true;
175            for (int j = 0; j < numPreferredLocales; ++j) {
176                final Locale preferredLocale = preferredLocales.get(j);
177                if (!TextUtils.equals(locale.getLanguage(), preferredLocale.getLanguage())) {
178                    score[j] = 0;
179                    continue;
180                }
181                if (preferredULocaleCache[j] == null) {
182                    preferredULocaleCache[j] = ULocale.addLikelySubtags(
183                            ULocale.forLocale(preferredLocale));
184                }
185                score[j] = calculateMatchingSubScore(
186                        preferredULocaleCache[j],
187                        ULocale.addLikelySubtags(ULocale.forLocale(locale)));
188                if (canSkip && score[j] != 0) {
189                    canSkip = false;
190                }
191            }
192            if (canSkip) {
193                continue;
194            }
195
196            final String lang = locale.getLanguage();
197            final ScoreEntry bestScore = scoreboard.get(lang);
198            if (bestScore == null) {
199                scoreboard.put(lang, new ScoreEntry(score, i));
200            } else {
201                bestScore.updateIfBetter(score, i);
202            }
203        }
204
205        final ScoreEntry[] result = scoreboard.values().toArray(new ScoreEntry[scoreboard.size()]);
206        Arrays.sort(result);
207        for (final ScoreEntry entry : result) {
208            dest.add(sources.get(entry.mIndex));
209        }
210    }
211}
212