1/*
2 * Copyright (C) 2007 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 android.text;
18
19import android.content.res.Resources;
20import android.content.res.XmlResourceParser;
21
22import com.android.internal.util.XmlUtils;
23
24import android.view.View;
25
26import org.xmlpull.v1.XmlPullParser;
27import org.xmlpull.v1.XmlPullParserException;
28
29import java.io.IOException;
30import java.util.Locale;
31
32/**
33 * This class accesses a dictionary of corrections to frequent misspellings.
34 */
35public class AutoText {
36    // struct trie {
37    //     char c;
38    //     int off;
39    //     struct trie *child;
40    //     struct trie *next;
41    // };
42
43    private static final int TRIE_C = 0;
44    private static final int TRIE_OFF = 1;
45    private static final int TRIE_CHILD = 2;
46    private static final int TRIE_NEXT = 3;
47
48    private static final int TRIE_SIZEOF = 4;
49    private static final char TRIE_NULL = (char) -1;
50    private static final int TRIE_ROOT = 0;
51
52    private static final int INCREMENT = 1024;
53
54    private static final int DEFAULT = 14337; // Size of the Trie 13 Aug 2007
55
56    private static final int RIGHT = 9300; // Size of 'right' 13 Aug 2007
57
58    private static AutoText sInstance = new AutoText(Resources.getSystem());
59    private static Object sLock = new Object();
60
61    // TODO:
62    //
63    // Note the assumption that the destination strings total less than
64    // 64K characters and that the trie for the source side totals less
65    // than 64K chars/offsets/child pointers/next pointers.
66    //
67    // This seems very safe for English (currently 7K of destination,
68    // 14K of trie) but may need to be revisited.
69
70    private char[] mTrie;
71    private char mTrieUsed;
72    private String mText;
73    private Locale mLocale;
74    private int mSize;
75
76    private AutoText(Resources resources) {
77        mLocale = resources.getConfiguration().locale;
78        init(resources);
79    }
80
81    /**
82     * Returns the instance of AutoText. If the locale has changed, it will create a new
83     * instance of AutoText for the locale.
84     * @param view to get the resources from
85     * @return the single instance of AutoText
86     */
87    private static AutoText getInstance(View view) {
88        Resources res = view.getContext().getResources();
89        Locale locale = res.getConfiguration().locale;
90        AutoText instance;
91
92        synchronized (sLock) {
93            instance = sInstance;
94
95            if (!locale.equals(instance.mLocale)) {
96                instance = new AutoText(res);
97                sInstance = instance;
98            }
99        }
100
101        return instance;
102    }
103
104    /**
105     * Retrieves a possible spelling correction for the specified range
106     * of text.  Returns null if no correction can be found.
107     * The View is used to get the current Locale and Resources.
108     */
109    public static String get(CharSequence src, final int start, final int end,
110                             View view) {
111        return getInstance(view).lookup(src, start, end);
112    }
113
114    /**
115     * Returns the size of the auto text dictionary. The return value can be zero if there is
116     * no auto correction data available for the current locale.
117     * @param view used to retrieve the current Locale and Resources.
118     * @return the number of entries in the auto text dictionary
119     */
120    public static int getSize(View view) {
121
122        return getInstance(view).getSize();
123    }
124
125    /**
126     * Returns the size of the dictionary.
127     */
128    private int getSize() {
129        return mSize;
130    }
131
132    private String lookup(CharSequence src, final int start, final int end) {
133        int here = mTrie[TRIE_ROOT];
134
135        for (int i = start; i < end; i++) {
136            char c = src.charAt(i);
137
138            for (; here != TRIE_NULL; here = mTrie[here + TRIE_NEXT]) {
139                if (c == mTrie[here + TRIE_C]) {
140                    if ((i == end - 1)
141                            && (mTrie[here + TRIE_OFF] != TRIE_NULL)) {
142                        int off = mTrie[here + TRIE_OFF];
143                        int len = mText.charAt(off);
144
145                        return mText.substring(off + 1, off + 1 + len);
146                    }
147
148                    here = mTrie[here + TRIE_CHILD];
149                    break;
150                }
151            }
152
153            if (here == TRIE_NULL) {
154                return null;
155            }
156        }
157
158        return null;
159    }
160
161    private void init(Resources r) {
162        XmlResourceParser parser = r.getXml(com.android.internal.R.xml.autotext);
163
164        StringBuilder right = new StringBuilder(RIGHT);
165        mTrie = new char[DEFAULT];
166        mTrie[TRIE_ROOT] = TRIE_NULL;
167        mTrieUsed = TRIE_ROOT + 1;
168
169        try {
170            XmlUtils.beginDocument(parser, "words");
171            String odest = "";
172            char ooff = 0;
173
174            while (true) {
175                XmlUtils.nextElement(parser);
176
177                String element = parser.getName();
178                if (element == null || !(element.equals("word"))) {
179                    break;
180                }
181
182                String src = parser.getAttributeValue(null, "src");
183                if (parser.next() == XmlPullParser.TEXT) {
184                    String dest = parser.getText();
185                    char off;
186
187                    if (dest.equals(odest)) {
188                        off = ooff;
189                    } else {
190                        off = (char) right.length();
191                        right.append((char) dest.length());
192                        right.append(dest);
193                    }
194
195                    add(src, off);
196                }
197            }
198
199            // Don't let Resources cache a copy of all these strings.
200            r.flushLayoutCache();
201        } catch (XmlPullParserException e) {
202            throw new RuntimeException(e);
203        } catch (IOException e) {
204            throw new RuntimeException(e);
205        } finally {
206            parser.close();
207        }
208
209        mText = right.toString();
210    }
211
212    private void add(String src, char off) {
213        int slen = src.length();
214        int herep = TRIE_ROOT;
215        // Keep track of the size of the dictionary
216        mSize++;
217
218        for (int i = 0; i < slen; i++) {
219            char c = src.charAt(i);
220            boolean found = false;
221
222            for (; mTrie[herep] != TRIE_NULL;
223                    herep = mTrie[herep] + TRIE_NEXT) {
224                if (c == mTrie[mTrie[herep] + TRIE_C]) {
225                    // There is a node for this letter, and this is the
226                    // end, so fill in the right hand side fields.
227
228                    if (i == slen - 1) {
229                        mTrie[mTrie[herep] + TRIE_OFF] = off;
230                        return;
231                    }
232
233                    // There is a node for this letter, and we need
234                    // to go deeper into it to fill in the rest.
235
236                    herep = mTrie[herep] + TRIE_CHILD;
237                    found = true;
238                    break;
239                }
240            }
241
242            if (!found) {
243                // No node for this letter yet.  Make one.
244
245                char node = newTrieNode();
246                mTrie[herep] = node;
247
248                mTrie[mTrie[herep] + TRIE_C] = c;
249                mTrie[mTrie[herep] + TRIE_OFF] = TRIE_NULL;
250                mTrie[mTrie[herep] + TRIE_NEXT] = TRIE_NULL;
251                mTrie[mTrie[herep] + TRIE_CHILD] = TRIE_NULL;
252
253                // If this is the end of the word, fill in the offset.
254
255                if (i == slen - 1) {
256                    mTrie[mTrie[herep] + TRIE_OFF] = off;
257                    return;
258                }
259
260                // Otherwise, step in deeper and go to the next letter.
261
262                herep = mTrie[herep] + TRIE_CHILD;
263            }
264        }
265    }
266
267    private char newTrieNode() {
268        if (mTrieUsed + TRIE_SIZEOF > mTrie.length) {
269            char[] copy = new char[mTrie.length + INCREMENT];
270            System.arraycopy(mTrie, 0, copy, 0, mTrie.length);
271            mTrie = copy;
272        }
273
274        char ret = mTrieUsed;
275        mTrieUsed += TRIE_SIZEOF;
276
277        return ret;
278    }
279}
280