diff options
Diffstat (limited to 'src/com/android/dialer/dialpad')
| -rw-r--r-- | src/com/android/dialer/dialpad/DialpadFragment.java | 51 | ||||
| -rw-r--r-- | src/com/android/dialer/dialpad/SmartDialCache.java | 408 | ||||
| -rw-r--r-- | src/com/android/dialer/dialpad/SmartDialLoaderTask.java | 95 | ||||
| -rw-r--r-- | src/com/android/dialer/dialpad/SmartDialNameMatcher.java | 49 | ||||
| -rw-r--r-- | src/com/android/dialer/dialpad/SmartDialPrefix.java | 608 | ||||
| -rw-r--r-- | src/com/android/dialer/dialpad/SmartDialTrie.java | 671 |
6 files changed, 666 insertions, 1216 deletions
diff --git a/src/com/android/dialer/dialpad/DialpadFragment.java b/src/com/android/dialer/dialpad/DialpadFragment.java index a8984bd26..f783d2705 100644 --- a/src/com/android/dialer/dialpad/DialpadFragment.java +++ b/src/com/android/dialer/dialpad/DialpadFragment.java @@ -26,7 +26,6 @@ import android.content.Context; import android.content.DialogInterface; import android.content.Intent; import android.content.res.Resources; -import android.database.ContentObserver; import android.database.Cursor; import android.graphics.Bitmap; import android.graphics.BitmapFactory; @@ -35,7 +34,6 @@ import android.media.ToneGenerator; import android.net.Uri; import android.os.AsyncTask; import android.os.Bundle; -import android.os.Handler; import android.os.RemoteException; import android.os.ServiceManager; import android.os.SystemProperties; @@ -62,12 +60,10 @@ import android.view.MenuItem; import android.view.View; import android.view.ViewConfiguration; import android.view.ViewGroup; -import android.widget.AbsListView; import android.widget.AdapterView; import android.widget.BaseAdapter; import android.widget.EditText; import android.widget.ImageView; -import android.widget.LinearLayout; import android.widget.ListView; import android.widget.PopupMenu; import android.widget.RelativeLayout; @@ -82,6 +78,7 @@ import com.android.contacts.common.util.StopWatch; import com.android.dialer.DialtactsActivity; import com.android.dialer.R; import com.android.dialer.SpecialCharSequenceMgr; +import com.android.dialer.database.DialerDatabaseHelper; import com.android.dialer.interactions.PhoneNumberInteraction; import com.android.dialer.util.OrientationUtil; import com.android.internal.telephony.ITelephony; @@ -156,8 +153,6 @@ public class DialpadFragment extends Fragment */ private SmartDialController mSmartDialAdapter; - private SmartDialCache mSmartDialCache; - /** * Use latin character map by default */ @@ -169,6 +164,8 @@ public class DialpadFragment extends Fragment */ private boolean mSmartDialEnabled = false; + private DialerDatabaseHelper mDialerDatabaseHelper; + /** * Regular expression prohibiting manual phone call. Can be empty, which means "no rule". */ @@ -300,6 +297,10 @@ public class DialpadFragment extends Fragment mFirstLaunch = true; mContactsPrefs = new ContactsPreferences(getActivity()); mCurrentCountryIso = GeoUtil.getCurrentCountryIso(getActivity()); + + mDialerDatabaseHelper = DialerDatabaseHelper.getInstance(getActivity()); + SmartDialPrefix.initializeNanpSettings(getActivity()); + try { mHaptic.init(getActivity(), getResources().getBoolean(R.bool.config_enable_dialer_key_vibration)); @@ -1653,20 +1654,6 @@ public class DialpadFragment extends Fragment return intent; } - @Override - public void setUserVisibleHint(boolean isVisibleToUser) { - super.setUserVisibleHint(isVisibleToUser); - if (mSmartDialEnabled && isVisibleToUser && mSmartDialCache != null) { - // This is called every time the dialpad fragment comes into view. The first - // time the dialer is launched, mSmartDialEnabled is always false as it has not been - // read from settings(in onResume) yet at the point where setUserVisibleHint is called - // for the first time, so the caching on first launch will happen in onResume instead. - // This covers only the case where the dialer is launched in the call log or - // contacts tab, and then the user swipes to the dialpad. - mSmartDialCache.cacheIfNeeded(false); - } - } - private String mLastDigitsForSmartDial; private void loadSmartDialEntries() { @@ -1675,11 +1662,6 @@ public class DialpadFragment extends Fragment return; } - if (mSmartDialCache == null) { - Log.e(TAG, "Trying to load smart dialing entries from a null cache"); - return; - } - // Update only when the digits have changed. final String digits = SmartDialNameMatcher.normalizeNumber(mDigits.getText().toString(), mSmartDialMap); @@ -1691,7 +1673,7 @@ public class DialpadFragment extends Fragment if (digits.length() < 1) { mSmartDialAdapter.clear(); } else { - final SmartDialLoaderTask task = new SmartDialLoaderTask(this, digits, mSmartDialCache); + final SmartDialLoaderTask task = new SmartDialLoaderTask(this, digits, getActivity()); task.executeOnExecutor(AsyncTask.THREAD_POOL_EXECUTOR, new String[] {}); } } @@ -1708,24 +1690,15 @@ public class DialpadFragment extends Fragment // Handle smart dialing related state if (mSmartDialEnabled) { mSmartDialContainer.setVisibility(View.VISIBLE); - mSmartDialCache = SmartDialCache.getInstance(getActivity(), - mContactsPrefs.getDisplayOrder(), mSmartDialMap); - // Don't force recache if this is the first time onResume is being called, since - // caching should already happen in setUserVisibleHint. - if (!mFirstLaunch || getUserVisibleHint()) { - // This forced recache covers the cases where the dialer was running before and - // was brought back into the foreground, or the dialer was launched for the first - // time and displays the dialpad fragment immediately. If the dialpad fragment - // hasn't actually become visible throughout the entire activity's lifecycle, it - // is possible that caching hasn't happened yet. In this case, we can force a - // recache anyway, since we are not worried about startup performance anymore. - mSmartDialCache.cacheIfNeeded(true); + + if (DEBUG) { + Log.w(TAG, "Creating smart dial database"); } + mDialerDatabaseHelper.startSmartDialUpdateThread(); } else { if (mSmartDialContainer != null) { mSmartDialContainer.setVisibility(View.GONE); } - mSmartDialCache = null; } } diff --git a/src/com/android/dialer/dialpad/SmartDialCache.java b/src/com/android/dialer/dialpad/SmartDialCache.java deleted file mode 100644 index 3d4a563af..000000000 --- a/src/com/android/dialer/dialpad/SmartDialCache.java +++ /dev/null @@ -1,408 +0,0 @@ -/* - * Copyright (C) 2012 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package com.android.dialer.dialpad; - -import static com.android.dialer.dialpad.SmartDialController.LOG_TAG; - -import android.content.Context; -import android.content.SharedPreferences; -import android.database.Cursor; -import android.net.Uri; -import android.preference.PreferenceManager; -import android.provider.ContactsContract; -import android.provider.ContactsContract.CommonDataKinds.Phone; -import android.provider.ContactsContract.Contacts; -import android.provider.ContactsContract.Data; -import android.provider.ContactsContract.Directory; -import android.telephony.TelephonyManager; -import android.text.TextUtils; -import android.util.Log; - -import com.android.contacts.common.util.StopWatch; - -import com.google.common.annotations.VisibleForTesting; -import com.google.common.base.Preconditions; - -import java.util.Comparator; -import java.util.HashSet; -import java.util.Set; -import java.util.concurrent.atomic.AtomicInteger; - -/** - * Cache object used to cache Smart Dial contacts that handles various states of the cache at the - * point in time when getContacts() is called - * 1) Cache is currently empty and there is no caching thread running - getContacts() starts a - * caching thread and returns the cache when completed - * 2) The cache is currently empty, but a caching thread has been started - getContacts() waits - * till the existing caching thread is completed before immediately returning the cache - * 3) The cache has already been populated, and there is no caching thread running - getContacts() - * returns the existing cache immediately - * 4) The cache has already been populated, but there is another caching thread running (due to - * a forced cache refresh due to content updates - getContacts() returns the existing cache - * immediately - */ -public class SmartDialCache { - - public static class ContactNumber { - public final String displayName; - public final String lookupKey; - public final long id; - public final int affinity; - public final String phoneNumber; - - public ContactNumber(long id, String displayName, String phoneNumber, String lookupKey, - int affinity) { - this.displayName = displayName; - this.lookupKey = lookupKey; - this.id = id; - this.affinity = affinity; - this.phoneNumber = phoneNumber; - } - } - - public static interface PhoneQuery { - - Uri URI = Phone.CONTENT_URI.buildUpon(). - appendQueryParameter(ContactsContract.DIRECTORY_PARAM_KEY, - String.valueOf(Directory.DEFAULT)). - appendQueryParameter(ContactsContract.REMOVE_DUPLICATE_ENTRIES, "true"). - build(); - - final String[] PROJECTION_PRIMARY = new String[] { - Phone._ID, // 0 - Phone.TYPE, // 1 - Phone.LABEL, // 2 - Phone.NUMBER, // 3 - Phone.CONTACT_ID, // 4 - Phone.LOOKUP_KEY, // 5 - Phone.DISPLAY_NAME_PRIMARY, // 6 - }; - - final String[] PROJECTION_ALTERNATIVE = new String[] { - Phone._ID, // 0 - Phone.TYPE, // 1 - Phone.LABEL, // 2 - Phone.NUMBER, // 3 - Phone.CONTACT_ID, // 4 - Phone.LOOKUP_KEY, // 5 - Phone.DISPLAY_NAME_ALTERNATIVE, // 6 - }; - - public static final int PHONE_ID = 0; - public static final int PHONE_TYPE = 1; - public static final int PHONE_LABEL = 2; - public static final int PHONE_NUMBER = 3; - public static final int PHONE_CONTACT_ID = 4; - public static final int PHONE_LOOKUP_KEY = 5; - public static final int PHONE_DISPLAY_NAME = 6; - - // Current contacts - those contacted within the last 3 days (in milliseconds) - final static long LAST_TIME_USED_CURRENT_MS = 3L * 24 * 60 * 60 * 1000; - - // Recent contacts - those contacted within the last 30 days (in milliseconds) - final static long LAST_TIME_USED_RECENT_MS = 30L * 24 * 60 * 60 * 1000; - - final static String TIME_SINCE_LAST_USED_MS = - "(? - " + Data.LAST_TIME_USED + ")"; - - final static String SORT_BY_DATA_USAGE = - "(CASE WHEN " + TIME_SINCE_LAST_USED_MS + " < " + LAST_TIME_USED_CURRENT_MS + - " THEN 0 " + - " WHEN " + TIME_SINCE_LAST_USED_MS + " < " + LAST_TIME_USED_RECENT_MS + - " THEN 1 " + - " ELSE 2 END), " + - Data.TIMES_USED + " DESC"; - - // This sort order is similar to that used by the ContactsProvider when returning a list - // of frequently called contacts. - public static final String SORT_ORDER = - Contacts.STARRED + " DESC, " - + Data.IS_SUPER_PRIMARY + " DESC, " - + SORT_BY_DATA_USAGE + ", " - + Contacts.IN_VISIBLE_GROUP + " DESC, " - + Contacts.DISPLAY_NAME + ", " - + Data.CONTACT_ID + ", " - + Data.IS_PRIMARY + " DESC"; - } - - // Static set used to determine which countries use NANP numbers - public static Set<String> sNanpCountries = null; - - private SmartDialTrie mContactsCache; - private static AtomicInteger mCacheStatus; - private final SmartDialMap mMap; - private final int mNameDisplayOrder; - private final Context mContext; - private final static Object mLock = new Object(); - - /** The country code of the user's sim card obtained by calling getSimCountryIso*/ - private static final String PREF_USER_SIM_COUNTRY_CODE = - "DialtactsActivity_user_sim_country_code"; - private static final String PREF_USER_SIM_COUNTRY_CODE_DEFAULT = null; - - private static String sUserSimCountryCode = PREF_USER_SIM_COUNTRY_CODE_DEFAULT; - private static boolean sUserInNanpRegion = false; - - public static final int CACHE_NEEDS_RECACHE = 1; - public static final int CACHE_IN_PROGRESS = 2; - public static final int CACHE_COMPLETED = 3; - - private static final boolean DEBUG = false; - - private SmartDialCache(Context context, int nameDisplayOrder, SmartDialMap map) { - mNameDisplayOrder = nameDisplayOrder; - mMap = map; - Preconditions.checkNotNull(context, "Context must not be null"); - mContext = context.getApplicationContext(); - mCacheStatus = new AtomicInteger(CACHE_NEEDS_RECACHE); - - final TelephonyManager manager = (TelephonyManager) context.getSystemService( - Context.TELEPHONY_SERVICE); - if (manager != null) { - sUserSimCountryCode = manager.getSimCountryIso(); - } - - final SharedPreferences prefs = PreferenceManager.getDefaultSharedPreferences(context); - - if (sUserSimCountryCode != null) { - // Update shared preferences with the latest country obtained from getSimCountryIso - prefs.edit().putString(PREF_USER_SIM_COUNTRY_CODE, sUserSimCountryCode).apply(); - } else { - // Couldn't get the country from getSimCountryIso. Maybe we are in airplane mode. - // Try to load the settings, if any from SharedPreferences. - sUserSimCountryCode = prefs.getString(PREF_USER_SIM_COUNTRY_CODE, - PREF_USER_SIM_COUNTRY_CODE_DEFAULT); - } - - sUserInNanpRegion = isCountryNanp(sUserSimCountryCode); - - } - - private static SmartDialCache instance; - - /** - * Returns an instance of SmartDialCache. - * - * @param context A context that provides a valid ContentResolver. - * @param nameDisplayOrder One of the two name display order integer constants (1 or 2) as saved - * in settings under the key - * {@link android.provider.ContactsContract.Preferences#DISPLAY_ORDER}. - * @return An instance of SmartDialCache - */ - public static synchronized SmartDialCache getInstance(Context context, int nameDisplayOrder, - SmartDialMap map) { - if (instance == null) { - instance = new SmartDialCache(context, nameDisplayOrder, map); - } - return instance; - } - - /** - * Performs a database query, iterates through the returned cursor and saves the retrieved - * contacts to a local cache. - */ - private void cacheContacts(Context context) { - mCacheStatus.set(CACHE_IN_PROGRESS); - synchronized(mLock) { - if (DEBUG) { - Log.d(LOG_TAG, "Starting caching thread"); - } - final StopWatch stopWatch = DEBUG ? StopWatch.start("SmartDial Cache") : null; - final String millis = String.valueOf(System.currentTimeMillis()); - final Cursor c = context.getContentResolver().query(PhoneQuery.URI, - (mNameDisplayOrder == ContactsContract.Preferences.DISPLAY_ORDER_PRIMARY) - ? PhoneQuery.PROJECTION_PRIMARY : PhoneQuery.PROJECTION_ALTERNATIVE, - null, new String[] {millis, millis}, - PhoneQuery.SORT_ORDER); - if (DEBUG) { - stopWatch.lap("SmartDial query complete"); - } - if (c == null) { - Log.w(LOG_TAG, "SmartDial query received null for cursor"); - if (DEBUG) { - stopWatch.stopAndLog("SmartDial query received null for cursor", 0); - } - mCacheStatus.getAndSet(CACHE_NEEDS_RECACHE); - return; - } - final SmartDialTrie cache = new SmartDialTrie(mMap, sUserInNanpRegion); - try { - c.moveToPosition(-1); - int affinityCount = 0; - while (c.moveToNext()) { - final String displayName = c.getString(PhoneQuery.PHONE_DISPLAY_NAME); - final String phoneNumber = c.getString(PhoneQuery.PHONE_NUMBER); - final long id = c.getLong(PhoneQuery.PHONE_CONTACT_ID); - final String lookupKey = c.getString(PhoneQuery.PHONE_LOOKUP_KEY); - cache.put(new ContactNumber(id, displayName, phoneNumber, lookupKey, - affinityCount)); - affinityCount++; - } - } finally { - c.close(); - mContactsCache = cache; - if (DEBUG) { - stopWatch.stopAndLog("SmartDial caching completed", 0); - } - } - } - if (DEBUG) { - Log.d(LOG_TAG, "Caching thread completed"); - } - mCacheStatus.getAndSet(CACHE_COMPLETED); - } - - /** - * Returns the list of cached contacts. This is blocking so it should not be called from the UI - * thread. There are 4 possible scenarios: - * - * 1) Cache is currently empty and there is no caching thread running - getContacts() starts a - * caching thread and returns the cache when completed - * 2) The cache is currently empty, but a caching thread has been started - getContacts() waits - * till the existing caching thread is completed before immediately returning the cache - * 3) The cache has already been populated, and there is no caching thread running - - * getContacts() returns the existing cache immediately - * 4) The cache has already been populated, but there is another caching thread running (due to - * a forced cache refresh due to content updates - getContacts() returns the existing cache - * immediately - * - * @return List of already cached contacts, or an empty list if the caching failed for any - * reason. - */ - public SmartDialTrie getContacts() { - // Either scenario 3 or 4 - This means just go ahead and return the existing cache - // immediately even if there is a caching thread currently running. We are guaranteed to - // have the newest value of mContactsCache at this point because it is volatile. - if (mContactsCache != null) { - return mContactsCache; - } - // At this point we are forced to wait for cacheContacts to complete in another thread(if - // one currently exists) because of mLock. - synchronized(mLock) { - // If mContactsCache is still null at this point, either there was never any caching - // process running, or it failed (Scenario 1). If so, just go ahead and try to cache - // the contacts again. - if (mContactsCache == null) { - cacheContacts(mContext); - return (mContactsCache == null) ? new SmartDialTrie() : mContactsCache; - } else { - // After waiting for the lock on mLock to be released, mContactsCache is now - // non-null due to the completion of the caching thread (Scenario 2). Go ahead - // and return the existing cache. - return mContactsCache; - } - } - } - - /** - * Cache contacts only if there is a need to (forced cache refresh or no attempt to cache yet). - * This method is called in 2 places: whenever the DialpadFragment comes into view, and in - * onResume. - * - * @param forceRecache If true, force a cache refresh. - */ - - public void cacheIfNeeded(boolean forceRecache) { - if (DEBUG) { - Log.d("SmartDial", "cacheIfNeeded called with " + String.valueOf(forceRecache)); - } - if (mCacheStatus.get() == CACHE_IN_PROGRESS) { - return; - } - if (forceRecache || mCacheStatus.get() == CACHE_NEEDS_RECACHE) { - // Because this method can be possibly be called multiple times in rapid succession, - // set the cache status even before starting a caching thread to avoid unnecessarily - // spawning extra threads. - mCacheStatus.set(CACHE_IN_PROGRESS); - startCachingThread(); - } - } - - private void startCachingThread() { - new Thread(new Runnable() { - @Override - public void run() { - cacheContacts(mContext); - } - }).start(); - } - - public static class ContactAffinityComparator implements Comparator<ContactNumber> { - @Override - public int compare(ContactNumber lhs, ContactNumber rhs) { - // Smaller affinity is better because they are numbered in ascending order in - // the order the contacts were returned from the ContactsProvider (sorted by - // frequency of use and time last used - return Integer.compare(lhs.affinity, rhs.affinity); - } - - } - - public SmartDialMap getMap() { - return mMap; - } - - public boolean getUserInNanpRegion() { - return sUserInNanpRegion; - } - - /** - * Indicates whether the given country uses NANP numbers - * - * @param country ISO 3166 country code (case doesn't matter) - * @return True if country uses NANP numbers (e.g. US, Canada), false otherwise - */ - @VisibleForTesting - static boolean isCountryNanp(String country) { - if (TextUtils.isEmpty(country)) { - return false; - } - if (sNanpCountries == null) { - sNanpCountries = initNanpCountries(); - } - return sNanpCountries.contains(country.toUpperCase()); - } - - private static Set<String> initNanpCountries() { - final HashSet<String> result = new HashSet<String>(); - result.add("US"); // United States - result.add("CA"); // Canada - result.add("AS"); // American Samoa - result.add("AI"); // Anguilla - result.add("AG"); // Antigua and Barbuda - result.add("BS"); // Bahamas - result.add("BB"); // Barbados - result.add("BM"); // Bermuda - result.add("VG"); // British Virgin Islands - result.add("KY"); // Cayman Islands - result.add("DM"); // Dominica - result.add("DO"); // Dominican Republic - result.add("GD"); // Grenada - result.add("GU"); // Guam - result.add("JM"); // Jamaica - result.add("PR"); // Puerto Rico - result.add("MS"); // Montserrat - result.add("MP"); // Northern Mariana Islands - result.add("KN"); // Saint Kitts and Nevis - result.add("LC"); // Saint Lucia - result.add("VC"); // Saint Vincent and the Grenadines - result.add("TT"); // Trinidad and Tobago - result.add("TC"); // Turks and Caicos Islands - result.add("VI"); // U.S. Virgin Islands - return result; - } -} diff --git a/src/com/android/dialer/dialpad/SmartDialLoaderTask.java b/src/com/android/dialer/dialpad/SmartDialLoaderTask.java index d584c1793..71cbfa27d 100644 --- a/src/com/android/dialer/dialpad/SmartDialLoaderTask.java +++ b/src/com/android/dialer/dialpad/SmartDialLoaderTask.java @@ -18,24 +18,21 @@ package com.android.dialer.dialpad; import static com.android.dialer.dialpad.SmartDialController.LOG_TAG; +import android.content.Context; import android.os.AsyncTask; import android.provider.ContactsContract; import android.provider.ContactsContract.Contacts; import android.telephony.PhoneNumberUtils; -import android.util.Log; import com.android.contacts.common.preference.ContactsPreferences; import com.android.contacts.common.util.StopWatch; -import com.android.dialer.dialpad.SmartDialCache.ContactNumber; +import com.android.dialer.database.DialerDatabaseHelper; +import com.android.dialer.database.DialerDatabaseHelper.ContactNumber; -import com.google.common.base.Objects; import com.google.common.collect.Lists; import java.util.ArrayList; -import java.util.Collections; -import java.util.HashSet; import java.util.List; -import java.util.Set; /** * This task searches through the provided cache to return the top 3 contacts(ranked by confidence) @@ -50,28 +47,20 @@ public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDi static private final boolean DEBUG = false; - private static final int MAX_ENTRIES = 3; - - private final SmartDialCache mContactsCache; - private final SmartDialLoaderCallback mCallback; + private final DialerDatabaseHelper mDialerDatabaseHelper; + private final String mQuery; - /** - * See {@link ContactsPreferences#getDisplayOrder()}. - * {@link ContactsContract.Preferences#DISPLAY_ORDER_PRIMARY} (first name first) - * {@link ContactsContract.Preferences#DISPLAY_ORDER_ALTERNATIVE} (last name first) - */ private final SmartDialNameMatcher mNameMatcher; - public SmartDialLoaderTask(SmartDialLoaderCallback callback, String query, - SmartDialCache cache) { + public SmartDialLoaderTask(SmartDialLoaderCallback callback, String query, Context context) { this.mCallback = callback; - this.mContactsCache = cache; - this.mNameMatcher = new SmartDialNameMatcher(PhoneNumberUtils.normalizeNumber(query), - cache.getMap()); + mDialerDatabaseHelper = DialerDatabaseHelper.getInstance(context); this.mQuery = query; + this.mNameMatcher = new SmartDialNameMatcher(PhoneNumberUtils.normalizeNumber(query), + SmartDialPrefix.getMap()); } @Override @@ -87,85 +76,33 @@ public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDi } /** - * Loads all visible contacts with phone numbers and check if their display names match the - * query. Return at most {@link #MAX_ENTRIES} {@link SmartDialEntry}'s for the matching - * contacts. + * Loads top visible contacts with phone numbers and check if their display names match the + * query. */ private ArrayList<SmartDialEntry> getContactMatches() { - final SmartDialTrie trie = mContactsCache.getContacts(); - final boolean matchNanp = mContactsCache.getUserInNanpRegion(); - - if (DEBUG) { - Log.d(LOG_TAG, "Size of cache: " + trie.size()); - } - final StopWatch stopWatch = DEBUG ? StopWatch.start("Start Match") : null; - final ArrayList<ContactNumber> allMatches = trie.getAllWithPrefix(mNameMatcher.getQuery()); + + final ArrayList<ContactNumber> allMatches = mDialerDatabaseHelper.getLooseMatches(mQuery, + mNameMatcher); if (DEBUG) { stopWatch.lap("Find matches"); } - // Sort matches in order of ascending contact affinity (lower is better) - Collections.sort(allMatches, new SmartDialCache.ContactAffinityComparator()); - if (DEBUG) { - stopWatch.lap("Sort"); - } - final Set<ContactMatch> duplicates = new HashSet<ContactMatch>(); + final ArrayList<SmartDialEntry> candidates = Lists.newArrayList(); for (ContactNumber contact : allMatches) { - final ContactMatch contactMatch = new ContactMatch(contact.lookupKey, contact.id); - // Don't add multiple contact numbers from the same contact into suggestions if - // there are multiple matches. Instead, just keep the highest priority number - // instead. - if (duplicates.contains(contactMatch)) { - continue; - } - duplicates.add(contactMatch); final boolean matches = mNameMatcher.matches(contact.displayName); - candidates.add(new SmartDialEntry( contact.displayName, Contacts.getLookupUri(contact.id, contact.lookupKey), contact.phoneNumber, mNameMatcher.getMatchPositions(), - mNameMatcher.matchesNumber(contact.phoneNumber, - mNameMatcher.getQuery(), matchNanp) + mNameMatcher.matchesNumber(contact.phoneNumber, mNameMatcher.getQuery()) )); - if (candidates.size() >= MAX_ENTRIES) { - break; - } } if (DEBUG) { stopWatch.stopAndLog(LOG_TAG + " Match Complete", 0); } return candidates; } - - private class ContactMatch { - public final String lookupKey; - public final long id; - - public ContactMatch(String lookupKey, long id) { - this.lookupKey = lookupKey; - this.id = id; - } - - @Override - public int hashCode() { - return Objects.hashCode(lookupKey, id); - } - - @Override - public boolean equals(Object object) { - if (this == object) { - return true; - } - if (object instanceof ContactMatch) { - ContactMatch that = (ContactMatch) object; - return Objects.equal(this.lookupKey, that.lookupKey) - && Objects.equal(this.id, that.id); - } - return false; - } - } } diff --git a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java index d7d5ad523..fe88e930d 100644 --- a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java +++ b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java @@ -18,7 +18,7 @@ package com.android.dialer.dialpad; import android.text.TextUtils; -import com.android.dialer.dialpad.SmartDialTrie.CountryCodeWithOffset; +import com.android.dialer.dialpad.SmartDialPrefix.PhoneNumberTokens; import com.google.common.annotations.VisibleForTesting; import com.google.common.collect.Lists; @@ -88,40 +88,51 @@ public class SmartDialNameMatcher { } /** - * Matches a phone number against a query, taking care of formatting characters and also - * taking into account country code prefixes and special NANP number treatment. + * Matches a phone number against a query. Let the test application overwrite the NANP setting. * * @param phoneNumber - Raw phone number * @param query - Normalized query (only contains numbers from 0-9) - * @param matchNanp - Whether or not to do special matching for NANP numbers + * @param useNanp - Overwriting nanp setting boolean, used for testing. * @return {@literal null} if the number and the query don't match, a valid * SmartDialMatchPosition with the matching positions otherwise */ - public SmartDialMatchPosition matchesNumber(String phoneNumber, String query, - boolean matchNanp) { + @VisibleForTesting + public SmartDialMatchPosition matchesNumber(String phoneNumber, String query, boolean useNanp) { // Try matching the number as is SmartDialMatchPosition matchPos = matchesNumberWithOffset(phoneNumber, query, 0); if (matchPos == null) { - // Try matching the number without the '+' prefix, if any - final CountryCodeWithOffset code = SmartDialTrie.getOffsetWithoutCountryCode( - phoneNumber); - if (code != null) { - matchPos = matchesNumberWithOffset(phoneNumber, query, code.offset); + final PhoneNumberTokens phoneNumberTokens = + SmartDialPrefix.parsePhoneNumber(phoneNumber); + + if (phoneNumberTokens == null) { + return matchPos; } - if (matchPos == null && matchNanp) { - // Try matching NANP numbers - final int[] offsets = SmartDialTrie.getOffsetForNANPNumbers(phoneNumber, - mMap); - for (int i = 0; i < offsets.length; i++) { - matchPos = matchesNumberWithOffset(phoneNumber, query, offsets[i]); - if (matchPos != null) break; - } + if (phoneNumberTokens.countryCodeOffset != 0) { + matchPos = matchesNumberWithOffset(phoneNumber, query, + phoneNumberTokens.countryCodeOffset); + } + if (matchPos == null && phoneNumberTokens.nanpCodeOffset != 0 && useNanp) { + matchPos = matchesNumberWithOffset(phoneNumber, query, + phoneNumberTokens.nanpCodeOffset); } } return matchPos; } /** + * Matches a phone number against a query, taking care of formatting characters and also + * taking into account country code prefixes and special NANP number treatment. + * + * @param phoneNumber - Raw phone number + * @param query - Normalized query (only contains numbers from 0-9) + * @return {@literal null} if the number and the query don't match, a valid + * SmartDialMatchPosition with the matching positions otherwise + */ + public SmartDialMatchPosition matchesNumber(String phoneNumber, String query) { + return matchesNumber(phoneNumber, query, true); + } + + /** * Matches a phone number against a query, taking care of formatting characters * * @param phoneNumber - Raw phone number diff --git a/src/com/android/dialer/dialpad/SmartDialPrefix.java b/src/com/android/dialer/dialpad/SmartDialPrefix.java new file mode 100644 index 000000000..857f6408a --- /dev/null +++ b/src/com/android/dialer/dialpad/SmartDialPrefix.java @@ -0,0 +1,608 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.dialer.dialpad; + +import android.content.Context; + +import android.content.SharedPreferences; +import android.preference.PreferenceManager; +import android.telephony.TelephonyManager; +import android.text.TextUtils; + +import com.google.common.annotations.VisibleForTesting; +import com.google.common.collect.Lists; + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.Set; + +/** + * Smart Dial utility class to find prefixes of contacts. It contains both methods to find supported + * prefix combinations for contact names, and also methods to find supported prefix combinations for + * contacts' phone numbers. Each contact name is separated into several tokens, such as first name, + * middle name, family name etc. Each phone number is also separated into country code, NANP area + * code, and local number if such separation is possible. + */ +public class SmartDialPrefix { + + /** The number of starting and ending tokens in a contact's name considered for initials. + * For example, if both constants are set to 2, and a contact's name is + * "Albert Ben Charles Daniel Ed Foster", the first two tokens "Albert" "Ben", and last two + * tokens "Ed" "Foster" can be replaced by their initials in contact name matching. + * Users can look up this contact by combinations of his initials such as "AF" "BF" "EF" "ABF" + * "BEF" "ABEF" etc, but can not use combinations such as "CF" "DF" "ACF" "ADF" etc. + */ + private static final int LAST_TOKENS_FOR_INITIALS = 2; + private static final int FIRST_TOKENS_FOR_INITIALS = 2; + + /** The country code of the user's sim card obtained by calling getSimCountryIso*/ + private static final String PREF_USER_SIM_COUNTRY_CODE = + "DialtactsActivity_user_sim_country_code"; + private static final String PREF_USER_SIM_COUNTRY_CODE_DEFAULT = null; + private static String sUserSimCountryCode = PREF_USER_SIM_COUNTRY_CODE_DEFAULT; + + /** Indicates whether user is in NANP regions.*/ + private static boolean sUserInNanpRegion = false; + + /** Set of country names that use NANP code.*/ + private static Set<String> sNanpCountries = null; + + /** Set of supported country codes in front of the phone number. */ + private static Set<String> sCountryCodes = null; + + /** Dialpad mapping. */ + private static final SmartDialMap mMap = new LatinSmartDialMap(); + + private static boolean sNanpInitialized = false; + + /** Initializes the Nanp settings, and finds out whether user is in a NANP region.*/ + public static void initializeNanpSettings(Context context){ + final TelephonyManager manager = (TelephonyManager) context.getSystemService( + Context.TELEPHONY_SERVICE); + if (manager != null) { + sUserSimCountryCode = manager.getSimCountryIso(); + } + + final SharedPreferences prefs = PreferenceManager.getDefaultSharedPreferences(context); + + if (sUserSimCountryCode != null) { + /** Updates shared preferences with the latest country obtained from getSimCountryIso.*/ + prefs.edit().putString(PREF_USER_SIM_COUNTRY_CODE, sUserSimCountryCode).apply(); + } else { + /** Uses previously stored country code if loading fails. */ + sUserSimCountryCode = prefs.getString(PREF_USER_SIM_COUNTRY_CODE, + PREF_USER_SIM_COUNTRY_CODE_DEFAULT); + } + /** Queries the NANP country list to find out whether user is in a NANP region.*/ + sUserInNanpRegion = isCountryNanp(sUserSimCountryCode); + sNanpInitialized = true; + } + + /** + * Explicitly setting the user Nanp to the given boolean + */ + @VisibleForTesting + public static void setUserInNanpRegion(boolean userInNanpRegion) { + sUserInNanpRegion = userInNanpRegion; + } + + /** + * Class to record phone number parsing information. + */ + public static class PhoneNumberTokens { + /** Country code of the phone number. */ + final String countryCode; + + /** Offset of national number after the country code. */ + final int countryCodeOffset; + + /** Offset of local number after NANP area code.*/ + final int nanpCodeOffset; + + public PhoneNumberTokens(String countryCode, int countryCodeOffset, int nanpCodeOffset) { + this.countryCode = countryCode; + this.countryCodeOffset = countryCodeOffset; + this.nanpCodeOffset = nanpCodeOffset; + } + } + + /** + * Parses a contact's name into a list of separated tokens. + * + * @param contactName Contact's name stored in string. + * @return A list of name tokens, for example separated first names, last name, etc. + */ + public static ArrayList<String> parseToIndexTokens(String contactName) { + final int length = contactName.length(); + final ArrayList<String> result = Lists.newArrayList(); + char c; + final StringBuilder currentIndexToken = new StringBuilder(); + /** + * Iterates through the whole name string. If the current character is a valid character, + * append it to the current token. If the current character is not a valid character, for + * example space " ", mark the current token as complete and add it to the list of tokens. + */ + for (int i = 0; i < length; i++) { + c = mMap.normalizeCharacter(contactName.charAt(i)); + if (mMap.isValidDialpadCharacter(c)) { + /** Converts a character into the number on dialpad that represents the character.*/ + currentIndexToken.append(mMap.getDialpadIndex(c)); + } else { + if (currentIndexToken.length() != 0) { + result.add(currentIndexToken.toString()); + } + currentIndexToken.delete(0, currentIndexToken.length()); + } + } + + /** Adds the last token in case it has not been added.*/ + if (currentIndexToken.length() != 0) { + result.add(currentIndexToken.toString()); + } + return result; + } + + /** + * Generates a list of strings that any prefix of any string in the list can be used to look + * up the contact's name. + * + * @param index The contact's name in string. + * @return A List of strings, whose prefix can be used to look up the contact. + */ + public static ArrayList<String> generateNamePrefixes(String index) { + final ArrayList<String> result = Lists.newArrayList(); + + /** Parses the name into a list of tokens.*/ + final ArrayList<String> indexTokens = parseToIndexTokens(index); + + if (indexTokens.size() > 0) { + /** Adds the full token combinations to the list. For example, a contact with name + * "Albert Ben Ed Foster" can be looked up by any prefix of the following strings + * "Foster" "EdFoster" "BenEdFoster" and "AlbertBenEdFoster". This covers all cases of + * look up that contains only one token, and that spans multiple continuous tokens. + */ + final StringBuilder fullNameToken = new StringBuilder(); + for (int i = indexTokens.size() - 1; i >= 0; i--) { + fullNameToken.insert(0, indexTokens.get(i)); + result.add(fullNameToken.toString()); + } + + /** Adds initial combinations to the list, with the number of initials restricted by + * {@link #LAST_TOKENS_FOR_INITIALS} and {@link #FIRST_TOKENS_FOR_INITIALS}. + * For example, a contact with name "Albert Ben Ed Foster" can be looked up by any + * prefix of the following strings "EFoster" "BFoster" "BEFoster" "AFoster" "ABFoster" + * "AEFoster" and "ABEFoster". This covers all cases of initial lookup. + */ + ArrayList<String> fullNames = Lists.newArrayList(); + fullNames.add(indexTokens.get(indexTokens.size() - 1)); + final int recursiveNameStart = result.size(); + int recursiveNameEnd = result.size(); + String initial = ""; + for (int i = indexTokens.size() - 2; i >= 0; i--) { + if ((i >= indexTokens.size() - LAST_TOKENS_FOR_INITIALS) || + (i < FIRST_TOKENS_FOR_INITIALS)) { + initial = indexTokens.get(i).substring(0, 1); + + /** Recursively adds initial combinations to the list.*/ + for (int j = 0; j < fullNames.size(); ++j) { + result.add(initial + fullNames.get(j)); + } + for (int j = recursiveNameStart; j < recursiveNameEnd; ++j) { + result.add(initial + result.get(j)); + } + recursiveNameEnd = result.size(); + final String currentFullName = fullNames.get(fullNames.size() - 1); + fullNames.add(indexTokens.get(i) + currentFullName); + } + } + } + + return result; + } + + /** + * Computes a list of number strings based on tokens of a given phone number. Any prefix + * of any string in the list can be used to look up the phone number. The list include the + * full phone number, the national number if there is a country code in the phone number, and + * the local number if there is an area code in the phone number following the NANP format. + * For example, if a user has phone number +41 71 394 8392, the list will contain 41713948392 + * and 713948392. Any prefix to either of the strings can be used to look up the phone number. + * If a user has a phone number +1 555-302-3029 (NANP format), the list will contain + * 15553023029, 5553023029, and 3023029. + * + * @param number String of user's phone number. + * @return A list of strings where any prefix of any entry can be used to look up the number. + */ + public static ArrayList<String> parseToNumberTokens(String number) { + final ArrayList<String> result = Lists.newArrayList(); + if (!TextUtils.isEmpty(number)) { + /** Adds the full number to the list.*/ + result.add(SmartDialNameMatcher.normalizeNumber(number, mMap)); + + final PhoneNumberTokens phoneNumberTokens = parsePhoneNumber(number); + if (phoneNumberTokens == null) { + return result; + } + + if (phoneNumberTokens.countryCodeOffset != 0) { + result.add(SmartDialNameMatcher.normalizeNumber(number, + phoneNumberTokens.countryCodeOffset, mMap)); + } + + if (phoneNumberTokens.nanpCodeOffset != 0) { + result.add(SmartDialNameMatcher.normalizeNumber(number, + phoneNumberTokens.nanpCodeOffset, mMap)); + } + } + return result; + } + + /** + * Parses a phone number to find out whether it has country code and NANP area code. + * + * @param number Raw phone number. + * @return a PhoneNumberToken instance with country code, NANP code information. + */ + public static PhoneNumberTokens parsePhoneNumber(String number) { + String countryCode = ""; + int countryCodeOffset = 0; + int nanpNumberOffset = 0; + + if (!TextUtils.isEmpty(number)) { + String normalizedNumber = SmartDialNameMatcher.normalizeNumber(number, mMap); + if (number.charAt(0) == '+') { + /** If the number starts with '+', tries to find valid country code. */ + for (int i = 1; i <= 1 + 3; i++) { + if (number.length() <= i) { + break; + } + countryCode = number.substring(1, i); + if (isValidCountryCode(countryCode)) { + countryCodeOffset = i; + break; + } + } + } else { + /** If the number does not start with '+', finds out whether it is in NANP + * format and has '1' preceding the number. + */ + if ((normalizedNumber.charAt(0) == '1') && (normalizedNumber.length() == 11) && + (sUserInNanpRegion)) { + countryCode = "1"; + countryCodeOffset = number.indexOf(normalizedNumber.charAt(1)); + if (countryCodeOffset == -1) { + countryCodeOffset = 0; + } + } + } + + /** If user is in NANP region, finds out whether a number is in NANP format.*/ + if (sUserInNanpRegion) { + String areaCode = ""; + if (countryCode.equals("") && normalizedNumber.length() == 10){ + /** if the number has no country code but fits the NANP format, extracts the + * NANP area code, and finds out offset of the local number. + */ + areaCode = normalizedNumber.substring(0, 3); + } else if (countryCode.equals("1") && normalizedNumber.length() == 11) { + /** If the number has country code '1', finds out area code and offset of the + * local number. + */ + areaCode = normalizedNumber.substring(1, 4); + } + if (!areaCode.equals("")) { + final int areaCodeIndex = number.indexOf(areaCode); + if (areaCodeIndex != -1) { + nanpNumberOffset = number.indexOf(areaCode) + 3; + } + } + } + } + return new PhoneNumberTokens(countryCode, countryCodeOffset, nanpNumberOffset); + } + + /** + * Checkes whether a country code is valid. + */ + private static boolean isValidCountryCode(String countryCode) { + if (sCountryCodes == null) { + sCountryCodes = initCountryCodes(); + } + return sCountryCodes.contains(countryCode); + } + + private static Set<String> initCountryCodes() { + final HashSet<String> result = new HashSet<String>(); + result.add("1"); + result.add("7"); + result.add("20"); + result.add("27"); + result.add("30"); + result.add("31"); + result.add("32"); + result.add("33"); + result.add("34"); + result.add("36"); + result.add("39"); + result.add("40"); + result.add("41"); + result.add("43"); + result.add("44"); + result.add("45"); + result.add("46"); + result.add("47"); + result.add("48"); + result.add("49"); + result.add("51"); + result.add("52"); + result.add("53"); + result.add("54"); + result.add("55"); + result.add("56"); + result.add("57"); + result.add("58"); + result.add("60"); + result.add("61"); + result.add("62"); + result.add("63"); + result.add("64"); + result.add("65"); + result.add("66"); + result.add("81"); + result.add("82"); + result.add("84"); + result.add("86"); + result.add("90"); + result.add("91"); + result.add("92"); + result.add("93"); + result.add("94"); + result.add("95"); + result.add("98"); + result.add("211"); + result.add("212"); + result.add("213"); + result.add("216"); + result.add("218"); + result.add("220"); + result.add("221"); + result.add("222"); + result.add("223"); + result.add("224"); + result.add("225"); + result.add("226"); + result.add("227"); + result.add("228"); + result.add("229"); + result.add("230"); + result.add("231"); + result.add("232"); + result.add("233"); + result.add("234"); + result.add("235"); + result.add("236"); + result.add("237"); + result.add("238"); + result.add("239"); + result.add("240"); + result.add("241"); + result.add("242"); + result.add("243"); + result.add("244"); + result.add("245"); + result.add("246"); + result.add("247"); + result.add("248"); + result.add("249"); + result.add("250"); + result.add("251"); + result.add("252"); + result.add("253"); + result.add("254"); + result.add("255"); + result.add("256"); + result.add("257"); + result.add("258"); + result.add("260"); + result.add("261"); + result.add("262"); + result.add("263"); + result.add("264"); + result.add("265"); + result.add("266"); + result.add("267"); + result.add("268"); + result.add("269"); + result.add("290"); + result.add("291"); + result.add("297"); + result.add("298"); + result.add("299"); + result.add("350"); + result.add("351"); + result.add("352"); + result.add("353"); + result.add("354"); + result.add("355"); + result.add("356"); + result.add("357"); + result.add("358"); + result.add("359"); + result.add("370"); + result.add("371"); + result.add("372"); + result.add("373"); + result.add("374"); + result.add("375"); + result.add("376"); + result.add("377"); + result.add("378"); + result.add("379"); + result.add("380"); + result.add("381"); + result.add("382"); + result.add("385"); + result.add("386"); + result.add("387"); + result.add("389"); + result.add("420"); + result.add("421"); + result.add("423"); + result.add("500"); + result.add("501"); + result.add("502"); + result.add("503"); + result.add("504"); + result.add("505"); + result.add("506"); + result.add("507"); + result.add("508"); + result.add("509"); + result.add("590"); + result.add("591"); + result.add("592"); + result.add("593"); + result.add("594"); + result.add("595"); + result.add("596"); + result.add("597"); + result.add("598"); + result.add("599"); + result.add("670"); + result.add("672"); + result.add("673"); + result.add("674"); + result.add("675"); + result.add("676"); + result.add("677"); + result.add("678"); + result.add("679"); + result.add("680"); + result.add("681"); + result.add("682"); + result.add("683"); + result.add("685"); + result.add("686"); + result.add("687"); + result.add("688"); + result.add("689"); + result.add("690"); + result.add("691"); + result.add("692"); + result.add("800"); + result.add("808"); + result.add("850"); + result.add("852"); + result.add("853"); + result.add("855"); + result.add("856"); + result.add("870"); + result.add("878"); + result.add("880"); + result.add("881"); + result.add("882"); + result.add("883"); + result.add("886"); + result.add("888"); + result.add("960"); + result.add("961"); + result.add("962"); + result.add("963"); + result.add("964"); + result.add("965"); + result.add("966"); + result.add("967"); + result.add("968"); + result.add("970"); + result.add("971"); + result.add("972"); + result.add("973"); + result.add("974"); + result.add("975"); + result.add("976"); + result.add("977"); + result.add("979"); + result.add("992"); + result.add("993"); + result.add("994"); + result.add("995"); + result.add("996"); + result.add("998"); + return result; + } + + public static SmartDialMap getMap() { + return mMap; + } + + /** + * Indicates whether the given country uses NANP numbers + * @see <a href="https://en.wikipedia.org/wiki/North_American_Numbering_Plan"> + * https://en.wikipedia.org/wiki/North_American_Numbering_Plan</a> + * + * @param country ISO 3166 country code (case doesn't matter) + * @return True if country uses NANP numbers (e.g. US, Canada), false otherwise + */ + @VisibleForTesting + public static boolean isCountryNanp(String country) { + if (TextUtils.isEmpty(country)) { + return false; + } + if (sNanpCountries == null) { + sNanpCountries = initNanpCountries(); + } + return sNanpCountries.contains(country.toUpperCase()); + } + + private static Set<String> initNanpCountries() { + final HashSet<String> result = new HashSet<String>(); + result.add("US"); // United States + result.add("CA"); // Canada + result.add("AS"); // American Samoa + result.add("AI"); // Anguilla + result.add("AG"); // Antigua and Barbuda + result.add("BS"); // Bahamas + result.add("BB"); // Barbados + result.add("BM"); // Bermuda + result.add("VG"); // British Virgin Islands + result.add("KY"); // Cayman Islands + result.add("DM"); // Dominica + result.add("DO"); // Dominican Republic + result.add("GD"); // Grenada + result.add("GU"); // Guam + result.add("JM"); // Jamaica + result.add("PR"); // Puerto Rico + result.add("MS"); // Montserrat + result.add("MP"); // Northern Mariana Islands + result.add("KN"); // Saint Kitts and Nevis + result.add("LC"); // Saint Lucia + result.add("VC"); // Saint Vincent and the Grenadines + result.add("TT"); // Trinidad and Tobago + result.add("TC"); // Turks and Caicos Islands + result.add("VI"); // U.S. Virgin Islands + return result; + } + + /** + * Returns whether the user is in a region that uses Nanp format based on the sim location. + * + * @return Whether user is in Nanp region. + */ + public static boolean getUserInNanpRegion() { + return sUserInNanpRegion; + } +} diff --git a/src/com/android/dialer/dialpad/SmartDialTrie.java b/src/com/android/dialer/dialpad/SmartDialTrie.java deleted file mode 100644 index c62210b17..000000000 --- a/src/com/android/dialer/dialpad/SmartDialTrie.java +++ /dev/null @@ -1,671 +0,0 @@ -/* - * Copyright (C) 2013 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package com.android.dialer.dialpad; - -import android.text.TextUtils; - -import com.android.dialer.dialpad.SmartDialCache.ContactNumber; -import com.google.common.annotations.VisibleForTesting; -import com.google.common.base.Preconditions; -import com.google.common.collect.Lists; - -import java.util.ArrayList; -import java.util.HashSet; -import java.util.Set; - -/** - * Prefix trie where the only allowed characters are the characters '0' to '9'. Multiple contacts - * can occupy the same nodes. - * - * <p>Provides functions to get all contacts that lie on or below a node. - * This is useful for retrieving all contacts that start with that prefix.</p> - * - * <p>Also contains special logic to handle NANP numbers in the case that the user is from a region - * that uses NANP numbers.</p> - */ -public class SmartDialTrie { - @VisibleForTesting - static class ParseInfo { - byte[] indexes; - int nthFirstTokenPos; - int nthLastTokenPos; - } - - /** - * A country code and integer offset pair that represents the parsed country code in a - * phone number. The country code is a string containing the numeric country-code prefix in - * a phone number (e.g. 1 or 852). The offset is the integer position of where the country code - * ends in a phone number. - */ - public static class CountryCodeWithOffset { - public static final CountryCodeWithOffset NO_COUNTRY_CODE = new CountryCodeWithOffset(0, - ""); - - final String countryCode; - final int offset; - - public CountryCodeWithOffset(int offset, String countryCode) { - this.countryCode = countryCode; - this.offset = offset; - } - } - - final Node mRoot = new Node(); - private int mSize = 0; - private final SmartDialMap mMap; - private final boolean mFormatNanp; - - private static final int LAST_TOKENS_FOR_INITIALS = 2; - private static final int FIRST_TOKENS_FOR_INITIALS = 2; - - // Static set of all possible country codes in the world - public static Set<String> sCountryCodes = null; - - public SmartDialTrie() { - // Use the latin letter to digit map by default if none provided - this(new LatinSmartDialMap(), false); - } - - /** - * Creates a new SmartDialTrie. - * - * @param formatNanp True if inserted numbers are to be treated as NANP numbers - * such that numbers are automatically broken up by country prefix and area code. - */ - @VisibleForTesting - public SmartDialTrie(boolean formatNanp) { - this(new LatinSmartDialMap(), formatNanp); - } - - /** - * Creates a new SmartDialTrie. - * - * @param charMap Mapping of characters to digits to use when inserting names into the trie. - * @param formatNanp True if inserted numbers are to be treated as NANP numbers - * such that numbers are automatically broken up by country prefix and area code. - */ - public SmartDialTrie(SmartDialMap map, boolean formatNanp) { - mMap = map; - mFormatNanp = formatNanp; - } - - /** - * Returns all contacts in the prefix tree that correspond to this prefix. - */ - public ArrayList<ContactNumber> getAllWithPrefix(CharSequence prefix) { - final ArrayList<ContactNumber> result = Lists.newArrayList(); - if (TextUtils.isEmpty(prefix)) { - return result; - } - Node current = mRoot; - for (int i = 0; i < prefix.length(); i++) { - char ch = prefix.charAt(i); - current = current.getChild(ch, false); - if (current == null) { - return result; - } - } - // return all contacts that correspond to this prefix - getAll(current, result); - return result; - } - - /** - * Returns all the contacts located at and under the provided node(including its children) - */ - private void getAll(Node root, ArrayList<ContactNumber> output) { - if (root == null) { - return; - } - if (root.getContents() != null) { - output.addAll(root.getContents()); - } - for (int i = 0; i < root.getChildrenSize(); i++) { - getAll(root.getChild(i, false), output); - } - } - - /** - * Adds the display name and phone number of a contact into the prefix trie. - * - * @param contact Desired contact to add - */ - public void put(ContactNumber contact) { - // Preconvert the display name into a byte array containing indexes to avoid having to - // remap each character over multiple passes - final ParseInfo info = parseToIndexes(contact.displayName, FIRST_TOKENS_FOR_INITIALS, - LAST_TOKENS_FOR_INITIALS); - putForPrefix(contact, mRoot, info, 0, true); - // We don't need to do the same for phone numbers since we only make one pass over them. - // Strip the calling code from the phone number here - if (!TextUtils.isEmpty(contact.phoneNumber)) { - // Handle country codes for numbers with a + prefix - final CountryCodeWithOffset code = getOffsetWithoutCountryCode(contact.phoneNumber); - if (code.offset != 0) { - putNumber(contact, contact.phoneNumber, code.offset); - } - if ((code.countryCode.equals("1") || code.offset == 0) && mFormatNanp) { - // Special case handling for NANP numbers (1-xxx-xxx-xxxx) - final String stripped = SmartDialNameMatcher.normalizeNumber( - contact.phoneNumber, code.offset, mMap); - if (!TextUtils.isEmpty(stripped)) { - int trunkPrefixOffset = 0; - if (stripped.charAt(0) == '1') { - // If the number starts with 1, we can assume its the trunk prefix. - trunkPrefixOffset = 1; - } - if (stripped.length() == (10 + trunkPrefixOffset)) { - // Valid NANP number - if (trunkPrefixOffset != 0) { - // Add the digits that follow the 1st digit (trunk prefix) - // If trunkPrefixOffset is 0, we will add the number as is anyway, so - // don't bother. - putNumber(contact, stripped, trunkPrefixOffset); - } - // Add the digits that follow the next 3 digits (area code) - putNumber(contact, stripped, 3 + trunkPrefixOffset); - } - } - } - putNumber(contact, contact.phoneNumber, 0); - } - mSize++; - } - - public static CountryCodeWithOffset getOffsetWithoutCountryCode(String number) { - if (!TextUtils.isEmpty(number)) { - if (number.charAt(0) == '+') { - // check for international code here - for (int i = 1; i <= 1 + 3; i++) { - if (number.length() <= i) break; - final String countryCode = number.substring(1, i); - if (isValidCountryCode(countryCode)) { - return new CountryCodeWithOffset(i, countryCode); - } - } - } - } - return CountryCodeWithOffset.NO_COUNTRY_CODE; - } - - /** - * Used by SmartDialNameMatcher to determine which character in the phone number to start - * the matching process from for a NANP formatted number. - * - * @param number Raw phone number - * @return An empty array if the provided number does not appear to be an NANP number, - * and an array containing integer offsets for the number (starting after the '1' prefix, - * and the area code prefix respectively. - */ - public static int[] getOffsetForNANPNumbers(String number, SmartDialMap map) { - int validDigits = 0; - boolean hasPrefix = false; - int firstOffset = 0; // Tracks the location of the first digit after the '1' prefix - int secondOffset = 0; // Tracks the location of the first digit after the area code - for (int i = 0; i < number.length(); i++) { - final char ch = number.charAt(i); - if (map.isValidDialpadNumericChar(ch)) { - if (validDigits == 0) { - // Check the first digit to see if it is 1 - if (ch == '1') { - if (hasPrefix) { - // Prefix has two '1's in a row. Invalid number, since area codes - // cannot start with 1, so just bail - break; - } - hasPrefix = true; - continue; - } - } - validDigits++; - if (validDigits == 1) { - // Found the first digit after the country code - firstOffset = i; - } else if (validDigits == 4) { - // Found the first digit after the area code - secondOffset = i; - } - } - - } - if (validDigits == 10) { - return hasPrefix ? new int[] {firstOffset, secondOffset} : new int[] {secondOffset}; - } - return new int[0]; - } - - /** - * Converts the given characters into a byte array of index and returns it together with offset - * information in a {@link ParseInfo} data structure. - * @param chars Characters to convert into indexes - * @param firstNTokens The first n tokens we want the offset for - * @param lastNTokens The last n tokens we want the offset for - */ - @VisibleForTesting - ParseInfo parseToIndexes(CharSequence chars, int firstNTokens, int lastNTokens) { - final int length = chars.length(); - final byte[] result = new byte[length]; - final ArrayList<Integer> offSets = new ArrayList<Integer>(); - char c; - int tokenCount = 0; - boolean atSeparator = true; - for (int i = 0; i < length; i++) { - c = mMap.normalizeCharacter(chars.charAt(i)); - if (mMap.isValidDialpadCharacter(c)) { - if (atSeparator) { - tokenCount++; - } - atSeparator = false; - result[i] = mMap.getDialpadIndex(c); - } else { - // Found the last character of the current token - if (!atSeparator) { - offSets.add(i); - } - result[i] = -1; - atSeparator = true; - } - } - - final ParseInfo info = new ParseInfo(); - info.indexes = result; - info.nthFirstTokenPos = offSets.size() >= firstNTokens ? offSets.get(firstNTokens - 1) : - length - 1; - info.nthLastTokenPos = offSets.size() >= lastNTokens ? offSets.get(offSets.size() - - lastNTokens) : 0; - return info; - } - - /** - * Puts a phone number and its associated contact into the prefix trie. - * - * @param contact - Contact to add to the trie - * @param phoneNumber - Phone number of the contact - * @param offSet - The nth character of the phone number to start from - */ - private void putNumber(ContactNumber contact, String phoneNumber, int offSet) { - Preconditions.checkArgument(offSet < phoneNumber.length()); - Node current = mRoot; - final int length = phoneNumber.length(); - char ch; - for (int i = offSet; i < length; i++) { - ch = phoneNumber.charAt(i); - if (mMap.isValidDialpadNumericChar(ch)) { - current = current.getChild(ch, true); - } - } - current.add(contact); - } - - /** - * Place an contact into the trie using at the provided node using the provided prefix. Uses as - * the input prefix a byte array instead of a CharSequence, as we will be traversing the array - * multiple times and it is more efficient to pre-convert the prefix into indexes before hand. - * Adds initial matches for the first token, and the last N tokens in the name. - * - * @param contact Contact to put - * @param root Root node to use as the starting point - * @param parseInfo ParseInfo data structure containing the converted byte array, as well as - * token offsets that determine which tokens should have entries added for initial - * search - * @param start - Starting index of the byte array - * @param isFullName If true, prefix will be treated as a full name and everytime a new name - * token is encountered, the rest of the name segment is added into the trie. - */ - private void putForPrefix(ContactNumber contact, Node root, ParseInfo info, int start, - boolean isFullName) { - final boolean addInitialMatches = (start >= info.nthLastTokenPos || - start <= info.nthFirstTokenPos); - final byte[] indexes = info.indexes; - Node current = root; - Node initialNode = root; - final int length = indexes.length; - boolean atSeparator = true; - byte index; - for (int i = start; i < length; i++) { - index = indexes[i]; - if (index > -1) { - if (atSeparator) { - atSeparator = false; - // encountered a new name token, so add this token into the tree starting from - // the root node - if (initialNode != this.mRoot) { - if (isFullName) { - putForPrefix(contact, this.mRoot, info, i, false); - } - if (addInitialMatches && - (i >= info.nthLastTokenPos || i <= info.nthFirstTokenPos) && - initialNode != root) { - putForPrefix(contact, initialNode, info, i, false); - } - } - // Set initial node to the node indexed by the first character of the current - // prefix - if (initialNode == root) { - initialNode = initialNode.getChild(index, true); - } - } - current = current.getChild(index, true); - } else { - atSeparator = true; - } - } - current.add(contact); - } - - /* Used only for testing to verify we insert the correct number of entries into the trie */ - @VisibleForTesting - int numEntries() { - final ArrayList<ContactNumber> result = Lists.newArrayList(); - getAll(mRoot, result); - return result.size(); - } - - - @VisibleForTesting - public int size() { - return mSize; - } - - @VisibleForTesting - /* package */ static class Node { - Node[] mChildren; - private ArrayList<ContactNumber> mContents; - - public Node() { - // don't allocate array or contents unless needed - } - - public int getChildrenSize() { - if (mChildren == null) { - return -1; - } - return mChildren.length; - } - - /** - * Returns a specific child of the current node. - * - * @param index Index of the child to return. - * @param createIfDoesNotExist Whether or not to create a node in that child slot if one - * does not already currently exist. - * @return The existing or newly created child, or {@literal null} if the child does not - * exist and createIfDoesNotExist is false. - */ - public Node getChild(int index, boolean createIfDoesNotExist) { - if (createIfDoesNotExist) { - if (mChildren == null) { - mChildren = new Node[10]; - } - if (mChildren[index] == null) { - mChildren[index] = new Node(); - } - } else { - if (mChildren == null) { - return null; - } - } - return mChildren[index]; - } - - /** - * Same as getChild(int index, boolean createIfDoesNotExist), but takes a character from '0' - * to '9' as an index. - */ - public Node getChild(char index, boolean createIfDoesNotExist) { - return getChild(index - '0', createIfDoesNotExist); - } - - public void add(ContactNumber contact) { - if (mContents == null) { - mContents = Lists.newArrayList(); - } - mContents.add(contact); - } - - public ArrayList<ContactNumber> getContents() { - return mContents; - } - } - - private static boolean isValidCountryCode(String countryCode) { - if (sCountryCodes == null) { - sCountryCodes = initCountryCodes(); - } - return sCountryCodes.contains(countryCode); - } - - private static Set<String> initCountryCodes() { - final HashSet<String> result = new HashSet<String>(); - result.add("1"); - result.add("7"); - result.add("20"); - result.add("27"); - result.add("30"); - result.add("31"); - result.add("32"); - result.add("33"); - result.add("34"); - result.add("36"); - result.add("39"); - result.add("40"); - result.add("41"); - result.add("43"); - result.add("44"); - result.add("45"); - result.add("46"); - result.add("47"); - result.add("48"); - result.add("49"); - result.add("51"); - result.add("52"); - result.add("53"); - result.add("54"); - result.add("55"); - result.add("56"); - result.add("57"); - result.add("58"); - result.add("60"); - result.add("61"); - result.add("62"); - result.add("63"); - result.add("64"); - result.add("65"); - result.add("66"); - result.add("81"); - result.add("82"); - result.add("84"); - result.add("86"); - result.add("90"); - result.add("91"); - result.add("92"); - result.add("93"); - result.add("94"); - result.add("95"); - result.add("98"); - result.add("211"); - result.add("212"); - result.add("213"); - result.add("216"); - result.add("218"); - result.add("220"); - result.add("221"); - result.add("222"); - result.add("223"); - result.add("224"); - result.add("225"); - result.add("226"); - result.add("227"); - result.add("228"); - result.add("229"); - result.add("230"); - result.add("231"); - result.add("232"); - result.add("233"); - result.add("234"); - result.add("235"); - result.add("236"); - result.add("237"); - result.add("238"); - result.add("239"); - result.add("240"); - result.add("241"); - result.add("242"); - result.add("243"); - result.add("244"); - result.add("245"); - result.add("246"); - result.add("247"); - result.add("248"); - result.add("249"); - result.add("250"); - result.add("251"); - result.add("252"); - result.add("253"); - result.add("254"); - result.add("255"); - result.add("256"); - result.add("257"); - result.add("258"); - result.add("260"); - result.add("261"); - result.add("262"); - result.add("263"); - result.add("264"); - result.add("265"); - result.add("266"); - result.add("267"); - result.add("268"); - result.add("269"); - result.add("290"); - result.add("291"); - result.add("297"); - result.add("298"); - result.add("299"); - result.add("350"); - result.add("351"); - result.add("352"); - result.add("353"); - result.add("354"); - result.add("355"); - result.add("356"); - result.add("357"); - result.add("358"); - result.add("359"); - result.add("370"); - result.add("371"); - result.add("372"); - result.add("373"); - result.add("374"); - result.add("375"); - result.add("376"); - result.add("377"); - result.add("378"); - result.add("379"); - result.add("380"); - result.add("381"); - result.add("382"); - result.add("385"); - result.add("386"); - result.add("387"); - result.add("389"); - result.add("420"); - result.add("421"); - result.add("423"); - result.add("500"); - result.add("501"); - result.add("502"); - result.add("503"); - result.add("504"); - result.add("505"); - result.add("506"); - result.add("507"); - result.add("508"); - result.add("509"); - result.add("590"); - result.add("591"); - result.add("592"); - result.add("593"); - result.add("594"); - result.add("595"); - result.add("596"); - result.add("597"); - result.add("598"); - result.add("599"); - result.add("670"); - result.add("672"); - result.add("673"); - result.add("674"); - result.add("675"); - result.add("676"); - result.add("677"); - result.add("678"); - result.add("679"); - result.add("680"); - result.add("681"); - result.add("682"); - result.add("683"); - result.add("685"); - result.add("686"); - result.add("687"); - result.add("688"); - result.add("689"); - result.add("690"); - result.add("691"); - result.add("692"); - result.add("800"); - result.add("808"); - result.add("850"); - result.add("852"); - result.add("853"); - result.add("855"); - result.add("856"); - result.add("870"); - result.add("878"); - result.add("880"); - result.add("881"); - result.add("882"); - result.add("883"); - result.add("886"); - result.add("888"); - result.add("960"); - result.add("961"); - result.add("962"); - result.add("963"); - result.add("964"); - result.add("965"); - result.add("966"); - result.add("967"); - result.add("968"); - result.add("970"); - result.add("971"); - result.add("972"); - result.add("973"); - result.add("974"); - result.add("975"); - result.add("976"); - result.add("977"); - result.add("979"); - result.add("992"); - result.add("993"); - result.add("994"); - result.add("995"); - result.add("996"); - result.add("998"); - return result; - } -} |