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