19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * you may not use this file except in compliance with the License. 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * You may obtain a copy of the License at 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * See the License for the specific language governing permissions and 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * limitations under the License. 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpackage android.text; 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport android.content.res.Resources; 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport android.content.res.XmlResourceParser; 212269d1572e5fcfb725ea55f5764d8c3280d69f6dDianne Hackborn 222269d1572e5fcfb725ea55f5764d8c3280d69f6dDianne Hackbornimport com.android.internal.util.XmlUtils; 232269d1572e5fcfb725ea55f5764d8c3280d69f6dDianne Hackborn 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport android.view.View; 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport org.xmlpull.v1.XmlPullParser; 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport org.xmlpull.v1.XmlPullParserException; 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport java.io.IOException; 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport java.util.Locale; 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/** 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * This class accesses a dictionary of corrections to frequent misspellings. 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpublic class AutoText { 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // struct trie { 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // char c; 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // int off; 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // struct trie *child; 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // struct trie *next; 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // }; 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final int TRIE_C = 0; 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final int TRIE_OFF = 1; 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final int TRIE_CHILD = 2; 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final int TRIE_NEXT = 3; 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final int TRIE_SIZEOF = 4; 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final char TRIE_NULL = (char) -1; 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final int TRIE_ROOT = 0; 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final int INCREMENT = 1024; 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final int DEFAULT = 14337; // Size of the Trie 13 Aug 2007 559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static final int RIGHT = 9300; // Size of 'right' 13 Aug 2007 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static AutoText sInstance = new AutoText(Resources.getSystem()); 599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static Object sLock = new Object(); 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // TODO: 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Note the assumption that the destination strings total less than 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // 64K characters and that the trie for the source side totals less 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // than 64K chars/offsets/child pointers/next pointers. 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // This seems very safe for English (currently 7K of destination, 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // 14K of trie) but may need to be revisited. 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private char[] mTrie; 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private char mTrieUsed; 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private String mText; 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private Locale mLocale; 74a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani private int mSize; 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private AutoText(Resources resources) { 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mLocale = resources.getConfiguration().locale; 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project init(resources); 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 82a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * Returns the instance of AutoText. If the locale has changed, it will create a new 83a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * instance of AutoText for the locale. 84a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * @param view to get the resources from 85a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * @return the single instance of AutoText 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 87a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani private static AutoText getInstance(View view) { 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Resources res = view.getContext().getResources(); 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Locale locale = res.getConfiguration().locale; 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project AutoText instance; 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project synchronized (sLock) { 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project instance = sInstance; 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!locale.equals(instance.mLocale)) { 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project instance = new AutoText(res); 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project sInstance = instance; 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 100a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani 101a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani return instance; 102a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani } 103a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani 104a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani /** 105a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * Retrieves a possible spelling correction for the specified range 106a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * of text. Returns null if no correction can be found. 107a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * The View is used to get the current Locale and Resources. 108a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani */ 109a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani public static String get(CharSequence src, final int start, final int end, 110a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani View view) { 111a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani return getInstance(view).lookup(src, start, end); 112a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani } 113a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani 114a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani /** 115a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * Returns the size of the auto text dictionary. The return value can be zero if there is 116a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * no auto correction data available for the current locale. 117a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * @param view used to retrieve the current Locale and Resources. 118a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * @return the number of entries in the auto text dictionary 119a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani */ 120a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani public static int getSize(View view) { 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 122a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani return getInstance(view).getSize(); 123a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani } 124a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani 125a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani /** 126a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani * Returns the size of the dictionary. 127a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani */ 128a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani private int getSize() { 129a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani return mSize; 1309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private String lookup(CharSequence src, final int start, final int end) { 1339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int here = mTrie[TRIE_ROOT]; 1349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = start; i < end; i++) { 1369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char c = src.charAt(i); 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; here != TRIE_NULL; here = mTrie[here + TRIE_NEXT]) { 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (c == mTrie[here + TRIE_C]) { 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((i == end - 1) 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && (mTrie[here + TRIE_OFF] != TRIE_NULL)) { 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int off = mTrie[here + TRIE_OFF]; 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int len = mText.charAt(off); 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mText.substring(off + 1, off + 1 + len); 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project here = mTrie[here + TRIE_CHILD]; 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (here == TRIE_NULL) { 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return null; 1559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return null; 1599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private void init(Resources r) { 1629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project XmlResourceParser parser = r.getXml(com.android.internal.R.xml.autotext); 1639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project StringBuilder right = new StringBuilder(RIGHT); 1659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie = new char[DEFAULT]; 1669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie[TRIE_ROOT] = TRIE_NULL; 1679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrieUsed = TRIE_ROOT + 1; 1689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project try { 1709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project XmlUtils.beginDocument(parser, "words"); 1719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project String odest = ""; 1729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char ooff = 0; 1739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (true) { 1759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project XmlUtils.nextElement(parser); 1769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project String element = parser.getName(); 1789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (element == null || !(element.equals("word"))) { 1799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 1809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project String src = parser.getAttributeValue(null, "src"); 1839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (parser.next() == XmlPullParser.TEXT) { 1849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project String dest = parser.getText(); 1859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char off; 1869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (dest.equals(odest)) { 1889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project off = ooff; 1899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 1909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project off = (char) right.length(); 1919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project right.append((char) dest.length()); 1929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project right.append(dest); 1939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project add(src, off); 1969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Don't let Resources cache a copy of all these strings. 2009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project r.flushLayoutCache(); 2019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } catch (XmlPullParserException e) { 2029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project throw new RuntimeException(e); 2039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } catch (IOException e) { 2049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project throw new RuntimeException(e); 2059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } finally { 2069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project parser.close(); 2079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mText = right.toString(); 2109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private void add(String src, char off) { 2139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int slen = src.length(); 2149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int herep = TRIE_ROOT; 215a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani // Keep track of the size of the dictionary 216a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani mSize++; 217a565e5e3d084c4e5a21a094b1409e3b23f9dce48Amith Yamasani 2189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = 0; i < slen; i++) { 2199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char c = src.charAt(i); 2209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean found = false; 2219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; mTrie[herep] != TRIE_NULL; 2239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project herep = mTrie[herep] + TRIE_NEXT) { 2249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (c == mTrie[mTrie[herep] + TRIE_C]) { 2259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // There is a node for this letter, and this is the 2269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // end, so fill in the right hand side fields. 2279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i == slen - 1) { 2299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie[mTrie[herep] + TRIE_OFF] = off; 2309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return; 2319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // There is a node for this letter, and we need 2349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // to go deeper into it to fill in the rest. 2359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project herep = mTrie[herep] + TRIE_CHILD; 2379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project found = true; 2389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 2399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!found) { 2439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // No node for this letter yet. Make one. 2449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char node = newTrieNode(); 2469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie[herep] = node; 2479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie[mTrie[herep] + TRIE_C] = c; 2499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie[mTrie[herep] + TRIE_OFF] = TRIE_NULL; 2509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie[mTrie[herep] + TRIE_NEXT] = TRIE_NULL; 2519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie[mTrie[herep] + TRIE_CHILD] = TRIE_NULL; 2529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // If this is the end of the word, fill in the offset. 2549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i == slen - 1) { 2569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie[mTrie[herep] + TRIE_OFF] = off; 2579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return; 2589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Otherwise, step in deeper and go to the next letter. 2619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project herep = mTrie[herep] + TRIE_CHILD; 2639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private char newTrieNode() { 2689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mTrieUsed + TRIE_SIZEOF > mTrie.length) { 2699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char[] copy = new char[mTrie.length + INCREMENT]; 2709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mTrie, 0, copy, 0, mTrie.length); 2719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrie = copy; 2729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char ret = mTrieUsed; 2759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mTrieUsed += TRIE_SIZEOF; 2769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return ret; 2789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 280