Smart Dialling v2 with phone number support

Behavior:
Use a prefix tree to cache contacts instead of an array list
Perform matches against phone numbers as well
DialpadFragment now ignores results from stale tasks where
queries no longer match
Add ability to not use default phone number for phone number
disambiguation dialog
Contacts are now ranked by the order which they were sorted
by in the ContactsProvider (affinity)
Change remapAccentedChars to always return lowercase characters to avoid
overhead of uppercase character conversion

Resource/Layout changes:
Tweak margins so that the section containing smart dial
suggestions looks cleaner
Use color resource instead of hardcoding color values
Add phone number to SmartDial items

ContentObserver:
Add a contentobserver to be notified on changes in contacts
Refactored cache to allow for forced cache refreshes
Use a single instance of SmartDialCache

Tests:
Added SmartDialTrie tests

Comments:
Comment cleanup

Change-Id: Ica2854e2845d4d75048aa1fd982f139496d21bf3

12 files changed, 1100 insertions, 364 deletions

diff --git a/res/layout/dialpad_fragment.xml b/res/layout/dialpad_fragment.xml
index e672551bb..27ba2da46 100644
--- a/res/layout/dialpad_fragment.xml
+++ b/res/layout/dialpad_fragment.xml
@@ -56,17 +56,16 @@
             android:src="@drawable/ic_dial_action_delete" />
     </LinearLayout>
 
-    <View style="@style/DialpadHorizontalSeparator"/>
-
     <!-- Smard dial suggestion section -->
     <GridView
         android:id="@+id/dialpad_smartdial_list"
         android:layout_width="match_parent"
-        android:layout_height="42sp"
+        android:layout_height="50sp"
         android:columnWidth="0dp"
         android:numColumns="3"
         android:stretchMode="columnWidth"
         android:gravity="center"
+        android:layout_marginTop="@dimen/dialpad_vertical_margin"
         android:background="@drawable/dialpad_background"/>
 
     <!-- Keypad section -->
diff --git a/res/layout/dialpad_smartdial_item.xml b/res/layout/dialpad_smartdial_item.xml
index eed257035..54f2a084e 100644
--- a/res/layout/dialpad_smartdial_item.xml
+++ b/res/layout/dialpad_smartdial_item.xml
@@ -13,16 +13,29 @@
      See the License for the specific language governing permissions and
      limitations under the License.
 -->
-
-<com.android.dialer.dialpad.SmartDialTextView
+<LinearLayout
     xmlns:android="http://schemas.android.com/apk/res/android"
-    android:id="@+id/contact_name"
+    android:orientation="vertical"
     android:layout_width="match_parent"
-    android:layout_height="42sp"
-    android:padding="@dimen/smartdial_suggestions_padding"
-    android:textColor="#39caff"
-    android:textSize="16sp"
-    android:singleLine="true"
-    android:ellipsize="none"
-    android:gravity="center"
+    android:layout_height="46sp">
+
+    <com.android.dialer.dialpad.SmartDialTextView
+        android:id="@+id/contact_name"
+        android:layout_width="match_parent"
+        android:layout_height="28sp"
+        android:padding="@dimen/smartdial_suggestions_padding"
+        android:textColor="@color/smartdial_primary_text_color"
+        android:textSize="16sp"
+        android:singleLine="true"
+        android:ellipsize="none"
+        android:gravity="center"
+    />
+    <com.android.dialer.dialpad.SmartDialTextView
+        android:id="@+id/contact_number"
+        android:layout_width="match_parent"
+        android:layout_height="16sp"
+        android:textColor="@color/dialtacts_secondary_text_color"
+        android:textSize="13sp"
+        android:gravity="center"
     />
+</LinearLayout>
diff --git a/res/values/colors.xml b/res/values/colors.xml
index ebdc2f60e..288f58b64 100644
--- a/res/values/colors.xml
+++ b/res/values/colors.xml
@@ -19,6 +19,7 @@
     <!-- Secondary text color in the Phone app -->
     <color name="dialtacts_secondary_text_color">#888888</color>
     <color name="smartdial_confidence_drawable_color">#39caff</color>
+    <color name="smartdial_primary_text_color">#39caff</color>
     <color name="smartdial_highlighted_text_color">#ffffff</color>
 
     <!-- Color of the text describing an unconsumed missed call. -->
diff --git a/src/com/android/dialer/dialpad/DialpadFragment.java b/src/com/android/dialer/dialpad/DialpadFragment.java
index b862f7678..f70a279e7 100644
--- a/src/com/android/dialer/dialpad/DialpadFragment.java
+++ b/src/com/android/dialer/dialpad/DialpadFragment.java
@@ -25,6 +25,7 @@ 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;
@@ -33,6 +34,7 @@ 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;
@@ -77,6 +79,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.dialpad.SmartDialCache.SmartDialContentObserver;
 import com.android.dialer.interactions.PhoneNumberInteraction;
 import com.android.dialer.util.OrientationUtil;
 import com.android.internal.telephony.ITelephony;
@@ -148,6 +151,7 @@ public class DialpadFragment extends Fragment
      * Will be set only if the view has the smart dialing section.
      */
     private SmartDialAdapter mSmartDialAdapter;
+    private SmartDialContentObserver mSmartDialObserver;
 
     /**
      * Regular expression prohibiting manual phone call. Can be empty, which means "no rule".
@@ -276,7 +280,8 @@ public class DialpadFragment extends Fragment
 
         mContactsPrefs = new ContactsPreferences(getActivity());
         mCurrentCountryIso = GeoUtil.getCurrentCountryIso(getActivity());
-        mSmartDialCache = new SmartDialCache(getActivity(), mContactsPrefs.getDisplayOrder());
+        mSmartDialCache = SmartDialCache.getInstance(getActivity(),
+                mContactsPrefs.getDisplayOrder());
         try {
             mHaptic.init(getActivity(),
                          getResources().getBoolean(R.bool.config_enable_dialer_key_vibration));
@@ -292,6 +297,10 @@ public class DialpadFragment extends Fragment
         if (state != null) {
             mDigitsFilledByIntent = state.getBoolean(PREF_DIGITS_FILLED_BY_INTENT);
         }
+
+        mSmartDialObserver = new SmartDialContentObserver(new Handler(), mSmartDialCache);
+        this.getActivity().getContentResolver().registerContentObserver(
+                SmartDialCache.PhoneQuery.URI, true, mSmartDialObserver);
     }
 
     @Override
@@ -361,6 +370,7 @@ public class DialpadFragment extends Fragment
             mSmartDialAdapter = new SmartDialAdapter(getActivity());
             mSmartDialList.setAdapter(mSmartDialAdapter);
             mSmartDialList.setOnItemClickListener(new OnSmartDialItemClick());
+            mSmartDialList.setOnItemLongClickListener(new OnSmartDialLongClick());
         }
 
         return fragmentView;
@@ -608,6 +618,9 @@ public class DialpadFragment extends Fragment
         stopWatch.lap("bes");
 
         stopWatch.stopAndLog(TAG, 50);
+
+        this.getActivity().getContentResolver().registerContentObserver(
+                SmartDialCache.PhoneQuery.URI, true, mSmartDialObserver);
     }
 
     @Override
@@ -635,6 +648,8 @@ public class DialpadFragment extends Fragment
         mLastNumberDialed = EMPTY_NUMBER;  // Since we are going to query again, free stale number.
 
         SpecialCharSequenceMgr.cleanup();
+
+        getActivity().getContentResolver().unregisterContentObserver(mSmartDialObserver);
     }
 
     @Override
@@ -1668,7 +1683,7 @@ public class DialpadFragment extends Fragment
     public void setUserVisibleHint(boolean isVisibleToUser) {
         super.setUserVisibleHint(isVisibleToUser);
         if (isVisibleToUser) {
-            mSmartDialCache.cacheIfNeeded();
+            mSmartDialCache.cacheIfNeeded(false);
         }
     }
 
@@ -1691,28 +1706,43 @@ public class DialpadFragment extends Fragment
             mSmartDialAdapter.clear();
         } else {
             final SmartDialLoaderTask task = new SmartDialLoaderTask(this, digits, mSmartDialCache);
-            // don't execute this in serial, otherwise we have to wait too long for results
             task.executeOnExecutor(AsyncTask.THREAD_POOL_EXECUTOR, new String[] {});
         }
     }
 
     @Override
-    public void setSmartDialAdapterEntries(List<SmartDialEntry> data) {
-        if (data == null) {
+    public void setSmartDialAdapterEntries(List<SmartDialEntry> data, String query) {
+        if (data == null || query == null || !query.equals(mLastDigitsForSmartDial)) {
             return;
         }
         mSmartDialAdapter.setEntries(data);
     }
 
+    private class OnSmartDialLongClick implements AdapterView.OnItemLongClickListener {
+        @Override
+        public boolean onItemLongClick(AdapterView<?> parent, View view, int position, long id) {
+            final SmartDialEntry entry = (SmartDialEntry) view.getTag();
+            if (entry == null) return false; // just in case.
+            mClearDigitsOnStop = true;
+            // Show the phone number disambiguation dialog without using the primary
+            // phone number so that the user can decide which number to call
+            PhoneNumberInteraction.startInteractionForPhoneCall(
+                    (TransactionSafeActivity) getActivity(), entry.contactUri, false);
+            return true;
+        }
+    }
+
     private class OnSmartDialItemClick implements AdapterView.OnItemClickListener {
         @Override
         public void onItemClick(AdapterView<?> parent, View view, int position, long id) {
             final SmartDialEntry entry = (SmartDialEntry) view.getTag();
             if (entry == null) return; // just in case.
-
+            // Dial the displayed phone number immediately
+            final Intent intent = CallUtil.getCallIntent(entry.phoneNumber.toString(),
+                    (getActivity() instanceof DialtactsActivity ?
+                            ((DialtactsActivity) getActivity()).getCallOrigin() : null));
+            startActivity(intent);
             mClearDigitsOnStop = true;
-            PhoneNumberInteraction.startInteractionForPhoneCall(
-                    (TransactionSafeActivity) getActivity(), entry.contactUri, getCallOrigin());
         }
     }
 }
diff --git a/src/com/android/dialer/dialpad/SmartDialAdapter.java b/src/com/android/dialer/dialpad/SmartDialAdapter.java
index a48473174..0a246e3e5 100644
--- a/src/com/android/dialer/dialpad/SmartDialAdapter.java
+++ b/src/com/android/dialer/dialpad/SmartDialAdapter.java
@@ -18,15 +18,16 @@ package com.android.dialer.dialpad;
 
 import android.content.Context;
 import android.content.res.Resources;
-import android.graphics.drawable.Drawable;
 import android.text.Spannable;
 import android.text.SpannableString;
+import android.text.TextUtils;
 import android.text.style.ForegroundColorSpan;
 import android.util.Log;
 import android.view.LayoutInflater;
 import android.view.View;
 import android.view.ViewGroup;
 import android.widget.BaseAdapter;
+import android.widget.LinearLayout;
 
 import com.android.dialer.R;
 import com.google.common.collect.Lists;
@@ -38,16 +39,12 @@ public class SmartDialAdapter extends BaseAdapter {
     private final LayoutInflater mInflater;
 
     private List<SmartDialEntry> mEntries;
-    private static Drawable mHighConfidenceHint;
 
     private final int mHighlightedTextColor;
 
     public SmartDialAdapter(Context context) {
         mInflater = (LayoutInflater) context.getSystemService(Context.LAYOUT_INFLATER_SERVICE);
         final Resources res = context.getResources();
-        mHighConfidenceHint = SmartDialTextView.getHighConfidenceHintDrawable(
-                res, res.getDimension(R.dimen.smartdial_confidence_hint_text_size),
-                res.getColor(R.color.smartdial_confidence_drawable_color));
         mHighlightedTextColor = res.getColor(R.color.smartdial_highlighted_text_color);
         clear();
     }
@@ -109,55 +106,59 @@ public class SmartDialAdapter extends BaseAdapter {
 
     @Override
     public View getView(int position, View convertView, ViewGroup parent) {
-        final SmartDialTextView view;
+        final LinearLayout view;
         if (convertView == null) {
-            view = (SmartDialTextView) mInflater.inflate(
+            view = (LinearLayout) mInflater.inflate(
                     R.layout.dialpad_smartdial_item, parent, false);
         } else {
-            view = (SmartDialTextView) convertView;
+            view = (LinearLayout) convertView;
         }
-        // Set the display name with highlight.
+
+        final SmartDialTextView nameView = (SmartDialTextView) view.findViewById(R.id.contact_name);
+
+        final SmartDialTextView numberView = (SmartDialTextView) view.findViewById(
+                R.id.contact_number);
 
         final SmartDialEntry item = mEntries.get(position);
 
         if (item == null) {
             // Clear the text in case the view was reused.
-            view.setText("");
+            nameView.setText("");
+            numberView.setText("");
             // Empty view. We use this to force a single entry to be in the middle
             return view;
         }
-        final SpannableString displayName = new SpannableString(item.displayName);
-        for (final SmartDialMatchPosition p : item.matchPositions) {
-            final int matchStart = p.start;
-            final int matchEnd = p.end;
-            if (matchStart < matchEnd) {
-                // Create a new ForegroundColorSpan for each section of the name to highlight,
-                // otherwise multiple highlights won't work.
-                try {
-                    displayName.setSpan(
-                            new ForegroundColorSpan(mHighlightedTextColor), matchStart, matchEnd,
-                            Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);
-                } catch (final IndexOutOfBoundsException e) {
-                    Log.wtf(LOG_TAG,
-                            "Invalid match positions provided - [" + matchStart + ","
-                            + matchEnd + "] for display name: " + item.displayName);
+
+        // Highlight the display name with the provided match positions
+        if (!TextUtils.isEmpty(item.displayName)) {
+            final SpannableString displayName = new SpannableString(item.displayName);
+            for (final SmartDialMatchPosition p : item.matchPositions) {
+                if (p.start < p.end) {
+                    if (p.end > displayName.length()) {
+                        p.end = displayName.length();
+                    }
+                    // Create a new ForegroundColorSpan for each section of the name to highlight,
+                    // otherwise multiple highlights won't work.
+                    displayName.setSpan(new ForegroundColorSpan(mHighlightedTextColor), p.start,
+                            p.end, Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);
                 }
             }
+            nameView.setText(displayName);
         }
 
-        if (position == 1) {
-            view.setCompoundDrawablesWithIntrinsicBounds(
-                    null, null, null, mHighConfidenceHint);
-            // Hack to align text in this view with text in other views without the
-            // overflow drawable
-            view.setCompoundDrawablePadding(-mHighConfidenceHint.getIntrinsicHeight());
-        } else {
-            view.setCompoundDrawablesWithIntrinsicBounds(
-                    null, null, null, null);
+        // Highlight the phone number with the provided match positions
+        if (!TextUtils.isEmpty(item.phoneNumber)) {
+            final SmartDialMatchPosition p = item.phoneNumberMatchPosition;
+            final SpannableString phoneNumber = new SpannableString(item.phoneNumber);
+            if (p != null && p.start < p.end) {
+                if (p.end > phoneNumber.length()) {
+                    p.end = phoneNumber.length();
+                }
+                phoneNumber.setSpan(new ForegroundColorSpan(mHighlightedTextColor), p.start, p.end,
+                        Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);
+            }
+            numberView.setText(phoneNumber);
         }
-
-
-        view.setText(displayName);
         view.setTag(item);
 
         return view;
diff --git a/src/com/android/dialer/dialpad/SmartDialCache.java b/src/com/android/dialer/dialpad/SmartDialCache.java
index c4d184d8f..71f4dfe57 100644
--- a/src/com/android/dialer/dialpad/SmartDialCache.java
+++ b/src/com/android/dialer/dialpad/SmartDialCache.java
@@ -19,80 +19,129 @@ package com.android.dialer.dialpad;
 import static com.android.dialer.dialpad.SmartDialAdapter.LOG_TAG;
 
 import android.content.Context;
+import android.database.ContentObserver;
 import android.database.Cursor;
 import android.net.Uri;
+import android.os.Handler;
 import android.provider.ContactsContract;
+import android.provider.ContactsContract.CommonDataKinds.Phone;
 import android.provider.ContactsContract.Contacts;
+import android.provider.ContactsContract.Directory;
 import android.util.Log;
 
 import com.android.contacts.common.util.StopWatch;
+
 import com.google.common.base.Preconditions;
-import com.google.common.collect.Lists;
 
-import java.util.ArrayList;
-import java.util.List;
+import java.util.Comparator;
+import java.util.concurrent.atomic.AtomicInteger;
 
 /**
- * Cache object used to cache Smart Dial contacts that handles various states of the cache:
- * 1) Cache has been populated
- * 2) Cache task is currently running
- * 3) Cache task failed
+ * 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 Contact {
+    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 Contact(long id, String displayName, String lookupKey) {
+        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;
         }
     }
 
-    /** Query used for loadByContactName */
-    private interface ContactQuery {
-        Uri URI = Contacts.CONTENT_URI.buildUpon()
-                // Visible contact only
-                //.appendQueryParameter(ContactsContract.DIRECTORY_PARAM_KEY, "0")
-                .build();
-        String[] PROJECTION = new String[] {
-                Contacts._ID,
-                Contacts.DISPLAY_NAME,
-                Contacts.LOOKUP_KEY
-            };
-        String[] PROJECTION_ALTERNATIVE = new String[] {
-                Contacts._ID,
-                Contacts.DISPLAY_NAME_ALTERNATIVE,
-                Contacts.LOOKUP_KEY
-            };
-
-        int COLUMN_ID = 0;
-        int COLUMN_DISPLAY_NAME = 1;
-        int COLUMN_LOOKUP_KEY = 2;
-
-        String SELECTION =
-                Contacts.HAS_PHONE_NUMBER + "=1";
-
-        String ORDER_BY = Contacts.LAST_TIME_CONTACTED + " DESC";
+    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;
+
+        public static final String SORT_ORDER = Contacts.LAST_TIME_CONTACTED + " DESC";
     }
 
-    // mContactsCache and mCachingStarted need to be volatile because we check for their status
-    // in cacheIfNeeded from the UI thread, to decided whether or not to fire up a caching thread.
-    private List<Contact> mContactsCache;
-    private volatile boolean mNeedsRecache = true;
+    private SmartDialTrie mContactsCache;
+    private static AtomicInteger mCacheStatus;
     private final int mNameDisplayOrder;
     private final Context mContext;
-    private final Object mLock = new Object();
+    private final static Object mLock = new Object();
+
+    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 = true; // STOPSHIP change to false.
+    private static final boolean DEBUG = true;
 
-    public SmartDialCache(Context context, int nameDisplayOrder) {
+    private SmartDialCache(Context context, int nameDisplayOrder) {
         mNameDisplayOrder = nameDisplayOrder;
         Preconditions.checkNotNull(context, "Context must not be null");
         mContext = context.getApplicationContext();
+        mCacheStatus = new AtomicInteger(CACHE_NEEDS_RECACHE);
+    }
+
+    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) {
+        if (instance == null) {
+            instance = new SmartDialCache(context, nameDisplayOrder);
+        }
+        return instance;
     }
 
     /**
@@ -100,76 +149,118 @@ public class SmartDialCache {
      * contacts to a local cache.
      */
     private void cacheContacts(Context context) {
+        mCacheStatus.set(CACHE_IN_PROGRESS);
         synchronized(mLock) {
-            // In extremely rare edge cases, getContacts() might be called and start caching
-            // between the time mCachingThread is added to the thread pool and it starts
-            // running. If so, at this point in time mContactsCache will no longer be null
-            // since it is populated by getContacts. We thus no longer have to perform any
-            // caching.
-            if (mContactsCache != null) {
-                if (DEBUG) {
-                    Log.d(LOG_TAG, "Contacts already cached");
-                }
-                return;
+            if (DEBUG) {
+                Log.d(LOG_TAG, "Starting caching thread");
             }
             final StopWatch stopWatch = DEBUG ? StopWatch.start("SmartDial Cache") : null;
-            final Cursor c = context.getContentResolver().query(ContactQuery.URI,
+            final Cursor c = context.getContentResolver().query(PhoneQuery.URI,
                     (mNameDisplayOrder == ContactsContract.Preferences.DISPLAY_ORDER_PRIMARY)
-                        ? ContactQuery.PROJECTION : ContactQuery.PROJECTION_ALTERNATIVE,
-                    ContactQuery.SELECTION, null,
-                    ContactQuery.ORDER_BY);
+                        ? PhoneQuery.PROJECTION_PRIMARY : PhoneQuery.PROJECTION_ALTERNATIVE,
+                    null, null, 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("Query Failure", 0);
+                    stopWatch.stopAndLog("SmartDial query received null for cursor", 0);
                 }
+                mCacheStatus.getAndSet(CACHE_NEEDS_RECACHE);
                 return;
             }
+            final SmartDialTrie cache = new SmartDialTrie(
+                    SmartDialNameMatcher.LATIN_LETTERS_TO_DIGITS);
             try {
-                mContactsCache = Lists.newArrayListWithCapacity(c.getCount());
                 c.moveToPosition(-1);
+                int affinityCount = 0;
                 while (c.moveToNext()) {
-                    final String displayName = c.getString(ContactQuery.COLUMN_DISPLAY_NAME);
-                    final long id = c.getLong(ContactQuery.COLUMN_ID);
-                    final String lookupKey = c.getString(ContactQuery.COLUMN_LOOKUP_KEY);
-                    mContactsCache.add(new Contact(id, displayName, lookupKey));
+                    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 Cache", 0);
+                    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. If the caching task has not started or been completed,
-     * the method blocks till the caching process is complete before returning the full list of
-     * cached contacts. This means that this method should not be called from the UI thread.
+     * 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 List<Contact> getContacts() {
+    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);
-                mNeedsRecache = false;
-                return (mContactsCache == null) ? new ArrayList<Contact>() : mContactsCache;
+                return (mContactsCache == null) ? new SmartDialTrie(
+                        SmartDialNameMatcher.LATIN_LETTERS_TO_DIGITS) : 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;
             }
         }
     }
 
     /**
-     * Only start a new caching task if {@link #mContactsCache} is null and there is no caching
-     * task that is currently running
+     * 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 when the
+     * ContentObserver observes a change in contacts.
+     *
+     * @param forceRecache If true, force a cache refresh.
      */
-    public void cacheIfNeeded() {
-        if (mNeedsRecache) {
-            mNeedsRecache = false;
+
+    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();
         }
     }
@@ -183,4 +274,42 @@ public class SmartDialCache {
         }).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 static class SmartDialContentObserver extends ContentObserver {
+        private final SmartDialCache mCache;
+        // throttle updates in case onChange is called too often due to syncing, etc.
+        private final long mThresholdBetweenUpdates = 5000;
+        private long mLastCalled = 0;
+        private long mLastUpdated = 0;
+        public SmartDialContentObserver(Handler handler, SmartDialCache cache) {
+            super(handler);
+            mCache = cache;
+        }
+
+        @Override
+        public void onChange(boolean selfChange) {
+            mLastCalled = System.currentTimeMillis();
+            if (DEBUG) {
+                Log.d(LOG_TAG, "Contacts change observed");
+            }
+            if (mLastCalled - mLastUpdated > mThresholdBetweenUpdates) {
+                mLastUpdated = mLastCalled;
+                if (DEBUG) {
+                    Log.d(LOG_TAG, "More than 5 seconds since last cache, forcing recache");
+                }
+                mCache.cacheIfNeeded(true);
+            }
+            super.onChange(selfChange);
+        }
+    }
 }
diff --git a/src/com/android/dialer/dialpad/SmartDialEntry.java b/src/com/android/dialer/dialpad/SmartDialEntry.java
index 101678de0..d658f3dca 100644
--- a/src/com/android/dialer/dialpad/SmartDialEntry.java
+++ b/src/com/android/dialer/dialpad/SmartDialEntry.java
@@ -24,13 +24,18 @@ public class SmartDialEntry {
     /** Display name for the contact. */
     public final CharSequence displayName;
     public final Uri contactUri;
+    public final CharSequence phoneNumber;
 
     public final ArrayList<SmartDialMatchPosition> matchPositions;
+    public final SmartDialMatchPosition phoneNumberMatchPosition;
 
-    public SmartDialEntry(CharSequence displayName, Uri contactUri,
-            ArrayList<SmartDialMatchPosition> matchPositions) {
+    public SmartDialEntry(CharSequence displayName, Uri contactUri, CharSequence phoneNumber,
+            ArrayList<SmartDialMatchPosition> matchPositions,
+            SmartDialMatchPosition phoneNumberMatchPosition) {
         this.displayName = displayName;
         this.contactUri = contactUri;
         this.matchPositions = matchPositions;
+        this.phoneNumber = phoneNumber;
+        this.phoneNumberMatchPosition = phoneNumberMatchPosition;
     }
 }
diff --git a/src/com/android/dialer/dialpad/SmartDialLoaderTask.java b/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
index 8ec9e9b71..c2b1c2d98 100644
--- a/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
+++ b/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
@@ -26,11 +26,16 @@ import android.util.Log;
 
 import com.android.contacts.common.preference.ContactsPreferences;
 import com.android.contacts.common.util.StopWatch;
-import com.android.dialer.dialpad.SmartDialCache.Contact;
+import com.android.dialer.dialpad.SmartDialCache.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)
@@ -40,7 +45,7 @@ import java.util.List;
 public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDialEntry>> {
 
     public interface SmartDialLoaderCallback {
-        void setSmartDialAdapterEntries(List<SmartDialEntry> list);
+        void setSmartDialAdapterEntries(List<SmartDialEntry> list, String query);
     }
 
     static private final boolean DEBUG = true; // STOPSHIP change to false.
@@ -51,6 +56,8 @@ public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDi
 
     private final SmartDialLoaderCallback mCallback;
 
+    private final String mQuery;
+
     /**
      * See {@link ContactsPreferences#getDisplayOrder()}.
      * {@link ContactsContract.Preferences#DISPLAY_ORDER_PRIMARY} (first name first)
@@ -63,6 +70,7 @@ public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDi
         this.mCallback = callback;
         this.mNameMatcher = new SmartDialNameMatcher(PhoneNumberUtils.normalizeNumber(query));
         this.mContactsCache = cache;
+        this.mQuery = query;
     }
 
     @Override
@@ -73,7 +81,7 @@ public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDi
     @Override
     protected void onPostExecute(List<SmartDialEntry> result) {
         if (mCallback != null) {
-            mCallback.setSmartDialAdapterEntries(result);
+            mCallback.setSmartDialAdapterEntries(result, mQuery);
         }
     }
 
@@ -83,40 +91,76 @@ public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDi
      * contacts.
      */
     private ArrayList<SmartDialEntry> getContactMatches() {
-        final List<Contact> cachedContactList = mContactsCache.getContacts();
-        // cachedContactList will never be null at this point
 
+        final SmartDialTrie trie = mContactsCache.getContacts();
         if (DEBUG) {
-            Log.d(LOG_TAG, "Size of cache: " + cachedContactList.size());
+            Log.d(LOG_TAG, "Size of cache: " + trie.size());
         }
 
-        final StopWatch stopWatch = DEBUG ? StopWatch.start(LOG_TAG + " Start Match") : null;
-        final ArrayList<SmartDialEntry> outList = Lists.newArrayList();
-
-        int count = 0;
-        for (int i = 0; i < cachedContactList.size(); i++) {
-            final Contact contact = cachedContactList.get(i);
-            final String displayName = contact.displayName;
-
-            if (!mNameMatcher.matches(displayName)) {
+        final StopWatch stopWatch = DEBUG ? StopWatch.start("Start Match") : null;
+        final ArrayList<ContactNumber> allMatches = trie.getAllWithPrefix(mNameMatcher.getQuery());
+        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;
             }
-            // Matched; create SmartDialEntry.
-            @SuppressWarnings("unchecked")
-            final SmartDialEntry entry = new SmartDialEntry(
-                     contact.displayName,
-                     Contacts.getLookupUri(contact.id, contact.lookupKey),
-                     (ArrayList<SmartDialMatchPosition>) mNameMatcher.getMatchPositions().clone()
-                     );
-            outList.add(entry);
-            count++;
-            if (count >= MAX_ENTRIES) {
+            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())
+                    ));
+            if (candidates.size() >= MAX_ENTRIES) {
                 break;
             }
         }
         if (DEBUG) {
             stopWatch.stopAndLog(LOG_TAG + " Match Complete", 0);
         }
-        return outList;
+        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 6f0f35423..381e74773 100644
--- a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
+++ b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
@@ -16,10 +16,11 @@
 
 package com.android.dialer.dialpad;
 
+import android.text.TextUtils;
+
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.Lists;
 
-import java.text.Normalizer;
 import java.util.ArrayList;
 
 /**
@@ -33,7 +34,7 @@ public class SmartDialNameMatcher {
 
     private final String mQuery;
 
-    private static final char[] LETTERS_TO_DIGITS = {
+    public static final char[] LATIN_LETTERS_TO_DIGITS = {
         '2', '2', '2', // A,B,C -> 2
         '3', '3', '3', // D,E,F -> 3
         '4', '4', '4', // G,H,I -> 4
@@ -66,37 +67,37 @@ public class SmartDialNameMatcher {
      * alphabetic equivalents. The unidecode library can be found at:
      * http://pypi.python.org/pypi/Unidecode/0.04.1
      */
-    private static char remapAccentedChars(char c) {
+    public static char remapAccentedChars(char c) {
         switch (c) {
-            case 'À': return 'A';
-            case 'Á': return 'A';
-            case 'Â': return 'A';
-            case 'Ã': return 'A';
-            case 'Ä': return 'A';
-            case 'Å': return 'A';
-            case 'Ç': return 'C';
-            case 'È': return 'E';
-            case 'É': return 'E';
-            case 'Ê': return 'E';
-            case 'Ë': return 'E';
-            case 'Ì': return 'I';
-            case 'Í': return 'I';
-            case 'Î': return 'I';
-            case 'Ï': return 'I';
-            case 'Ð': return 'D';
-            case 'Ñ': return 'N';
-            case 'Ò': return 'O';
-            case 'Ó': return 'O';
-            case 'Ô': return 'O';
-            case 'Õ': return 'O';
-            case 'Ö': return 'O';
+            case 'À': return 'a';
+            case 'Á': return 'a';
+            case 'Â': return 'a';
+            case 'Ã': return 'a';
+            case 'Ä': return 'a';
+            case 'Å': return 'a';
+            case 'Ç': return 'c';
+            case 'È': return 'e';
+            case 'É': return 'e';
+            case 'Ê': return 'e';
+            case 'Ë': return 'e';
+            case 'Ì': return 'i';
+            case 'Í': return 'i';
+            case 'Î': return 'i';
+            case 'Ï': return 'i';
+            case 'Ð': return 'd';
+            case 'Ñ': return 'n';
+            case 'Ò': return 'o';
+            case 'Ó': return 'o';
+            case 'Ô': return 'o';
+            case 'Õ': return 'o';
+            case 'Ö': return 'o';
             case '×': return 'x';
-            case 'Ø': return 'O';
-            case 'Ù': return 'U';
-            case 'Ú': return 'U';
-            case 'Û': return 'U';
-            case 'Ü': return 'U';
-            case 'Ý': return 'U';
+            case 'Ø': return 'o';
+            case 'Ù': return 'u';
+            case 'Ú': return 'u';
+            case 'Û': return 'u';
+            case 'Ü': return 'u';
+            case 'Ý': return 'u';
             case 'à': return 'a';
             case 'á': return 'a';
             case 'â': return 'a';
@@ -126,260 +127,286 @@ public class SmartDialNameMatcher {
             case 'ü': return 'u';
             case 'ý': return 'y';
             case 'ÿ': return 'y';
-            case 'Ā': return 'A';
+            case 'Ā': return 'a';
             case 'ā': return 'a';
-            case 'Ă': return 'A';
+            case 'Ă': return 'a';
             case 'ă': return 'a';
-            case 'Ą': return 'A';
+            case 'Ą': return 'a';
             case 'ą': return 'a';
-            case 'Ć': return 'C';
+            case 'Ć': return 'c';
             case 'ć': return 'c';
-            case 'Ĉ': return 'C';
+            case 'Ĉ': return 'c';
             case 'ĉ': return 'c';
-            case 'Ċ': return 'C';
+            case 'Ċ': return 'c';
             case 'ċ': return 'c';
-            case 'Č': return 'C';
+            case 'Č': return 'c';
             case 'č': return 'c';
-            case 'Ď': return 'D';
+            case 'Ď': return 'd';
             case 'ď': return 'd';
-            case 'Đ': return 'D';
+            case 'Đ': return 'd';
             case 'đ': return 'd';
-            case 'Ē': return 'E';
+            case 'Ē': return 'e';
             case 'ē': return 'e';
-            case 'Ĕ': return 'E';
+            case 'Ĕ': return 'e';
             case 'ĕ': return 'e';
-            case 'Ė': return 'E';
+            case 'Ė': return 'e';
             case 'ė': return 'e';
-            case 'Ę': return 'E';
+            case 'Ę': return 'e';
             case 'ę': return 'e';
-            case 'Ě': return 'E';
+            case 'Ě': return 'e';
             case 'ě': return 'e';
-            case 'Ĝ': return 'G';
+            case 'Ĝ': return 'g';
             case 'ĝ': return 'g';
-            case 'Ğ': return 'G';
+            case 'Ğ': return 'g';
             case 'ğ': return 'g';
-            case 'Ġ': return 'G';
+            case 'Ġ': return 'g';
             case 'ġ': return 'g';
-            case 'Ģ': return 'G';
+            case 'Ģ': return 'g';
             case 'ģ': return 'g';
-            case 'Ĥ': return 'H';
+            case 'Ĥ': return 'h';
             case 'ĥ': return 'h';
-            case 'Ħ': return 'H';
+            case 'Ħ': return 'h';
             case 'ħ': return 'h';
-            case 'Ĩ': return 'I';
+            case 'Ĩ': return 'i';
             case 'ĩ': return 'i';
-            case 'Ī': return 'I';
+            case 'Ī': return 'i';
             case 'ī': return 'i';
-            case 'Ĭ': return 'I';
+            case 'Ĭ': return 'i';
             case 'ĭ': return 'i';
-            case 'Į': return 'I';
+            case 'Į': return 'i';
             case 'į': return 'i';
-            case 'İ': return 'I';
+            case 'İ': return 'i';
             case 'ı': return 'i';
-            case 'Ĵ': return 'J';
+            case 'Ĵ': return 'j';
             case 'ĵ': return 'j';
-            case 'Ķ': return 'K';
+            case 'Ķ': return 'k';
             case 'ķ': return 'k';
             case 'ĸ': return 'k';
-            case 'Ĺ': return 'L';
+            case 'Ĺ': return 'l';
             case 'ĺ': return 'l';
-            case 'Ļ': return 'L';
+            case 'Ļ': return 'l';
             case 'ļ': return 'l';
-            case 'Ľ': return 'L';
+            case 'Ľ': return 'l';
             case 'ľ': return 'l';
-            case 'Ŀ': return 'L';
+            case 'Ŀ': return 'l';
             case 'ŀ': return 'l';
-            case 'Ł': return 'L';
+            case 'Ł': return 'l';
             case 'ł': return 'l';
-            case 'Ń': return 'N';
+            case 'Ń': return 'n';
             case 'ń': return 'n';
-            case 'Ņ': return 'N';
+            case 'Ņ': return 'n';
             case 'ņ': return 'n';
-            case 'Ň': return 'N';
+            case 'Ň': return 'n';
             case 'ň': return 'n';
-            case 'Ō': return 'O';
+            case 'Ō': return 'o';
             case 'ō': return 'o';
-            case 'Ŏ': return 'O';
+            case 'Ŏ': return 'o';
             case 'ŏ': return 'o';
-            case 'Ő': return 'O';
+            case 'Ő': return 'o';
             case 'ő': return 'o';
-            case 'Ŕ': return 'R';
+            case 'Ŕ': return 'r';
             case 'ŕ': return 'r';
-            case 'Ŗ': return 'R';
+            case 'Ŗ': return 'r';
             case 'ŗ': return 'r';
-            case 'Ř': return 'R';
+            case 'Ř': return 'r';
             case 'ř': return 'r';
-            case 'Ś': return 'S';
+            case 'Ś': return 's';
             case 'ś': return 's';
-            case 'Ŝ': return 'S';
+            case 'Ŝ': return 's';
             case 'ŝ': return 's';
-            case 'Ş': return 'S';
+            case 'Ş': return 's';
             case 'ş': return 's';
-            case 'Š': return 'S';
+            case 'Š': return 's';
             case 'š': return 's';
-            case 'Ţ': return 'T';
+            case 'Ţ': return 't';
             case 'ţ': return 't';
-            case 'Ť': return 'T';
+            case 'Ť': return 't';
             case 'ť': return 't';
-            case 'Ŧ': return 'T';
+            case 'Ŧ': return 't';
             case 'ŧ': return 't';
-            case 'Ũ': return 'U';
+            case 'Ũ': return 'u';
             case 'ũ': return 'u';
-            case 'Ū': return 'U';
+            case 'Ū': return 'u';
             case 'ū': return 'u';
-            case 'Ŭ': return 'U';
+            case 'Ŭ': return 'u';
             case 'ŭ': return 'u';
-            case 'Ů': return 'U';
+            case 'Ů': return 'u';
             case 'ů': return 'u';
-            case 'Ű': return 'U';
+            case 'Ű': return 'u';
             case 'ű': return 'u';
-            case 'Ų': return 'U';
+            case 'Ų': return 'u';
             case 'ų': return 'u';
-            case 'Ŵ': return 'W';
+            case 'Ŵ': return 'w';
             case 'ŵ': return 'w';
-            case 'Ŷ': return 'Y';
+            case 'Ŷ': return 'y';
             case 'ŷ': return 'y';
-            case 'Ÿ': return 'Y';
-            case 'Ź': return 'Z';
+            case 'Ÿ': return 'y';
+            case 'Ź': return 'z';
             case 'ź': return 'z';
-            case 'Ż': return 'Z';
+            case 'Ż': return 'z';
             case 'ż': return 'z';
-            case 'Ž': return 'Z';
+            case 'Ž': return 'z';
             case 'ž': return 'z';
             case 'ſ': return 's';
             case 'ƀ': return 'b';
-            case 'Ɓ': return 'B';
-            case 'Ƃ': return 'B';
+            case 'Ɓ': return 'b';
+            case 'Ƃ': return 'b';
             case 'ƃ': return 'b';
-            case 'Ɔ': return 'O';
-            case 'Ƈ': return 'C';
+            case 'Ɔ': return 'o';
+            case 'Ƈ': return 'c';
             case 'ƈ': return 'c';
-            case 'Ɖ': return 'D';
-            case 'Ɗ': return 'D';
-            case 'Ƌ': return 'D';
+            case 'Ɖ': return 'd';
+            case 'Ɗ': return 'd';
+            case 'Ƌ': return 'd';
             case 'ƌ': return 'd';
             case 'ƍ': return 'd';
-            case 'Ɛ': return 'E';
-            case 'Ƒ': return 'F';
+            case 'Ɛ': return 'e';
+            case 'Ƒ': return 'f';
             case 'ƒ': return 'f';
-            case 'Ɠ': return 'G';
-            case 'Ɣ': return 'G';
-            case 'Ɩ': return 'I';
-            case 'Ɨ': return 'I';
-            case 'Ƙ': return 'K';
+            case 'Ɠ': return 'g';
+            case 'Ɣ': return 'g';
+            case 'Ɩ': return 'i';
+            case 'Ɨ': return 'i';
+            case 'Ƙ': return 'k';
             case 'ƙ': return 'k';
             case 'ƚ': return 'l';
             case 'ƛ': return 'l';
-            case 'Ɯ': return 'W';
-            case 'Ɲ': return 'N';
+            case 'Ɯ': return 'w';
+            case 'Ɲ': return 'n';
             case 'ƞ': return 'n';
-            case 'Ɵ': return 'O';
-            case 'Ơ': return 'O';
+            case 'Ɵ': return 'o';
+            case 'Ơ': return 'o';
             case 'ơ': return 'o';
-            case 'Ƥ': return 'P';
+            case 'Ƥ': return 'p';
             case 'ƥ': return 'p';
             case 'ƫ': return 't';
-            case 'Ƭ': return 'T';
+            case 'Ƭ': return 't';
             case 'ƭ': return 't';
-            case 'Ʈ': return 'T';
-            case 'Ư': return 'U';
+            case 'Ʈ': return 't';
+            case 'Ư': return 'u';
             case 'ư': return 'u';
-            case 'Ʊ': return 'Y';
-            case 'Ʋ': return 'V';
-            case 'Ƴ': return 'Y';
+            case 'Ʊ': return 'y';
+            case 'Ʋ': return 'v';
+            case 'Ƴ': return 'y';
             case 'ƴ': return 'y';
-            case 'Ƶ': return 'Z';
+            case 'Ƶ': return 'z';
             case 'ƶ': return 'z';
             case 'ƿ': return 'w';
-            case 'Ǎ': return 'A';
+            case 'Ǎ': return 'a';
             case 'ǎ': return 'a';
-            case 'Ǐ': return 'I';
+            case 'Ǐ': return 'i';
             case 'ǐ': return 'i';
-            case 'Ǒ': return 'O';
+            case 'Ǒ': return 'o';
             case 'ǒ': return 'o';
-            case 'Ǔ': return 'U';
+            case 'Ǔ': return 'u';
             case 'ǔ': return 'u';
-            case 'Ǖ': return 'U';
+            case 'Ǖ': return 'u';
             case 'ǖ': return 'u';
-            case 'Ǘ': return 'U';
+            case 'Ǘ': return 'u';
             case 'ǘ': return 'u';
-            case 'Ǚ': return 'U';
+            case 'Ǚ': return 'u';
             case 'ǚ': return 'u';
-            case 'Ǜ': return 'U';
+            case 'Ǜ': return 'u';
             case 'ǜ': return 'u';
-            case 'Ǟ': return 'A';
+            case 'Ǟ': return 'a';
             case 'ǟ': return 'a';
-            case 'Ǡ': return 'A';
+            case 'Ǡ': return 'a';
             case 'ǡ': return 'a';
-            case 'Ǥ': return 'G';
+            case 'Ǥ': return 'g';
             case 'ǥ': return 'g';
-            case 'Ǧ': return 'G';
+            case 'Ǧ': return 'g';
             case 'ǧ': return 'g';
-            case 'Ǩ': return 'K';
+            case 'Ǩ': return 'k';
             case 'ǩ': return 'k';
-            case 'Ǫ': return 'O';
+            case 'Ǫ': return 'o';
             case 'ǫ': return 'o';
-            case 'Ǭ': return 'O';
+            case 'Ǭ': return 'o';
             case 'ǭ': return 'o';
             case 'ǰ': return 'j';
-            case 'Dz': return 'D';
-            case 'Ǵ': return 'G';
+            case 'Dz': return 'd';
+            case 'Ǵ': return 'g';
             case 'ǵ': return 'g';
-            case 'Ƿ': return 'W';
-            case 'Ǹ': return 'N';
+            case 'Ƿ': return 'w';
+            case 'Ǹ': return 'n';
             case 'ǹ': return 'n';
-            case 'Ǻ': return 'A';
+            case 'Ǻ': return 'a';
             case 'ǻ': return 'a';
-            case 'Ǿ': return 'O';
+            case 'Ǿ': return 'o';
             case 'ǿ': return 'o';
-            case 'Ȁ': return 'A';
+            case 'Ȁ': return 'a';
             case 'ȁ': return 'a';
-            case 'Ȃ': return 'A';
+            case 'Ȃ': return 'a';
             case 'ȃ': return 'a';
-            case 'Ȅ': return 'E';
+            case 'Ȅ': return 'e';
             case 'ȅ': return 'e';
-            case 'Ȇ': return 'E';
+            case 'Ȇ': return 'e';
             case 'ȇ': return 'e';
-            case 'Ȉ': return 'I';
+            case 'Ȉ': return 'i';
             case 'ȉ': return 'i';
-            case 'Ȋ': return 'I';
+            case 'Ȋ': return 'i';
             case 'ȋ': return 'i';
-            case 'Ȍ': return 'O';
+            case 'Ȍ': return 'o';
             case 'ȍ': return 'o';
-            case 'Ȏ': return 'O';
+            case 'Ȏ': return 'o';
             case 'ȏ': return 'o';
-            case 'Ȑ': return 'R';
+            case 'Ȑ': return 'r';
             case 'ȑ': return 'r';
-            case 'Ȓ': return 'R';
+            case 'Ȓ': return 'r';
             case 'ȓ': return 'r';
-            case 'Ȕ': return 'U';
+            case 'Ȕ': return 'u';
             case 'ȕ': return 'u';
-            case 'Ȗ': return 'U';
+            case 'Ȗ': return 'u';
             case 'ȗ': return 'u';
-            case 'Ș': return 'S';
+            case 'Ș': return 's';
             case 'ș': return 's';
-            case 'Ț': return 'T';
+            case 'Ț': return 't';
             case 'ț': return 't';
-            case 'Ȝ': return 'Y';
+            case 'Ȝ': return 'y';
             case 'ȝ': return 'y';
-            case 'Ȟ': return 'H';
+            case 'Ȟ': return 'h';
             case 'ȟ': return 'h';
-            case 'Ȥ': return 'Z';
+            case 'Ȥ': return 'z';
             case 'ȥ': return 'z';
-            case 'Ȧ': return 'A';
+            case 'Ȧ': return 'a';
             case 'ȧ': return 'a';
-            case 'Ȩ': return 'E';
+            case 'Ȩ': return 'e';
             case 'ȩ': return 'e';
-            case 'Ȫ': return 'O';
+            case 'Ȫ': return 'o';
             case 'ȫ': return 'o';
-            case 'Ȭ': return 'O';
+            case 'Ȭ': return 'o';
             case 'ȭ': return 'o';
-            case 'Ȯ': return 'O';
+            case 'Ȯ': return 'o';
             case 'ȯ': return 'o';
-            case 'Ȱ': return 'O';
+            case 'Ȱ': return 'o';
             case 'ȱ': return 'o';
-            case 'Ȳ': return 'Y';
+            case 'Ȳ': return 'y';
             case 'ȳ': return 'y';
+            case 'A': return 'a';
+            case 'B': return 'b';
+            case 'C': return 'c';
+            case 'D': return 'd';
+            case 'E': return 'e';
+            case 'F': return 'f';
+            case 'G': return 'g';
+            case 'H': return 'h';
+            case 'I': return 'i';
+            case 'J': return 'j';
+            case 'K': return 'k';
+            case 'L': return 'l';
+            case 'M': return 'm';
+            case 'N': return 'n';
+            case 'O': return 'o';
+            case 'P': return 'p';
+            case 'Q': return 'q';
+            case 'R': return 'r';
+            case 'S': return 's';
+            case 'T': return 't';
+            case 'U': return 'u';
+            case 'V': return 'v';
+            case 'W': return 'w';
+            case 'X': return 'x';
+            case 'Y': return 'y';
+            case 'Z': return 'z';
             default: return c;
         }
     }
@@ -391,41 +418,16 @@ public class SmartDialNameMatcher {
     }
 
     /**
-     * Strips all accented characters in a name and converts them to their alphabetic equivalents.
-     *
-     * @param name Name we want to remove accented characters from.
-     * @return Name without accents in characters
-     */
-    public static String stripDiacritics(String name) {
-        // NFD stands for normalization form D - Canonical Decomposition
-        // This means that for all characters with diacritics, e.g. ä, we decompose them into
-        // two characters, the first being the alphabetic equivalent, and the second being a
-        // a character that represents the diacritic.
-
-        final String normalized = Normalizer.normalize(name, Normalizer.Form.NFD);
-        final StringBuilder stripped = new StringBuilder();
-        for (int i = 0; i < normalized.length(); i++) {
-            // This pass through the string strips out all the diacritics by checking to see
-            // if they are in this list here:
-            // http://www.fileformat.info/info/unicode/category/Mn/list.htm
-            if (Character.getType(normalized.charAt(i)) != Character.NON_SPACING_MARK) {
-                stripped.append(normalized.charAt(i));
-            }
-        }
-        return stripped.toString();
-    }
-
-    /**
-     * Strips a phone number of unnecessary characters (zeros, ones, spaces, dashes, etc.)
+     * Strips a phone number of unnecessary characters (spaces, dashes, etc.)
      *
      * @param number Phone number we want to normalize
-     * @return Phone number consisting of digits from 2-9
+     * @return Phone number consisting of digits from 0-9
      */
     public static String normalizeNumber(String number) {
         final StringBuilder s = new StringBuilder();
         for (int i = 0; i < number.length(); i++) {
             char ch = number.charAt(i);
-            if (ch >= '2' && ch <= '9') {
+            if (ch >= '0' && ch <= '9') {
                 s.append(ch);
             }
         }
@@ -433,6 +435,39 @@ public class SmartDialNameMatcher {
     }
 
     /**
+     * Matches a phone number against a query, taking care of formatting characters
+     *
+     * @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) {
+        if (TextUtils.isEmpty(phoneNumber) || TextUtils.isEmpty(query)) {
+            return null;
+        }
+        int queryAt = 0;
+        int numberAt = 0;
+        for (int i = 0; i < phoneNumber.length(); i++) {
+            if (queryAt == query.length()) {
+                break;
+            }
+            char ch = phoneNumber.charAt(i);
+            if (ch >= '0' && ch <= '9') {
+                if (ch != query.charAt(queryAt)) {
+                    return null;
+                }
+                queryAt++;
+                numberAt++;
+            } else {
+                numberAt++;
+                continue;
+            }
+        }
+        return new SmartDialMatchPosition(0, numberAt);
+    }
+
+    /**
      * This function iterates through each token in the display name, trying to match the query
      * to the numeric equivalent of the token.
      *
@@ -452,9 +487,7 @@ public class SmartDialNameMatcher {
      * positions to.
      * @return Returns true if a combination of the tokens in displayName match the query
      * string contained in query. If the function returns true, matchList will contain an
-     * ArrayList of match positions. For now, matchList will contain a maximum of one match
-     * position. If we intend to support initial matching in the future, matchList could possibly
-     * contain more than one match position.
+     * ArrayList of match positions (multiple matches correspond to initial matches).
      */
     @VisibleForTesting
     boolean matchesCombination(String displayName, String query,
@@ -500,7 +533,7 @@ public class SmartDialNameMatcher {
             }
             if ((ch >= 'a') && (ch <= 'z')) {
                 // a starts at index 0
-                if (LETTERS_TO_DIGITS[ch - 'a'] != query.charAt(queryStart)) {
+                if (LATIN_LETTERS_TO_DIGITS[ch - 'a'] != query.charAt(queryStart)) {
                     // we did not find a match
                     queryStart = 0;
                     seperatorCount = 0;
@@ -539,7 +572,6 @@ public class SmartDialNameMatcher {
                                 SmartDialMatchPosition.advanceMatchPositions(partialTemp, j + 1);
                                 partialTemp.add(0,
                                         new SmartDialMatchPosition(nameStart, nameStart + 1));
-
                                 // we found a partial token match, store the data in a
                                 // temp buffer and return it if we end up not finding a full
                                 // token match
@@ -583,7 +615,9 @@ public class SmartDialNameMatcher {
     }
 
     public ArrayList<SmartDialMatchPosition> getMatchPositions() {
-        return mMatchPositions;
+        // Return a clone of mMatchPositions so that the caller can use it without
+        // worrying about it changing
+        return new ArrayList<SmartDialMatchPosition>(mMatchPositions);
     }
 
     public String getQuery() {
diff --git a/src/com/android/dialer/dialpad/SmartDialTrie.java b/src/com/android/dialer/dialpad/SmartDialTrie.java
new file mode 100644
index 000000000..981926717
--- /dev/null
+++ b/src/com/android/dialer/dialpad/SmartDialTrie.java
@@ -0,0 +1,250 @@
+/*
+ * 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.collect.Lists;
+
+import java.util.ArrayList;
+
+/**
+ * Prefix trie where the only allowed characters are the characters '0' to '9'. Multiple contacts
+ * can occupy the same nodes. 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.
+ */
+public class SmartDialTrie {
+    final Node mRoot = new Node();
+    private int mSize = 0;
+    private final char[] mCharacterMap;
+
+    public SmartDialTrie() {
+        // Use the latin letter to digit map by default if none provided
+        this(SmartDialNameMatcher.LATIN_LETTERS_TO_DIGITS);
+    }
+
+    public SmartDialTrie(char[] charMap) {
+        mCharacterMap = charMap;
+    }
+
+    /**
+     * 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
+        putForPrefix(contact, mRoot, toByteArray(contact.displayName), 0,
+                contact.displayName.length(), true, true);
+        // We don't need to do the same for phone numbers since we only make one pass over them.
+        putNumber(contact, contact.phoneNumber);
+        mSize++;
+    }
+
+    @VisibleForTesting
+    /* package */ byte[] toByteArray(CharSequence chars) {
+        final int length = chars.length();
+        final byte[] result = new byte[length];
+        char c;
+        for (int i = 0; i < length; i++) {
+            c = SmartDialNameMatcher.remapAccentedChars(chars.charAt(i));
+            if (c >= 'a' && c <= 'z') {
+                result[i] = (byte) (mCharacterMap[c - 'a'] - '0');
+            } else {
+                result[i] = -1;
+            }
+        }
+        return result;
+    }
+
+    /**
+     * 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
+     */
+    public void putNumber(ContactNumber contact, String phoneNumber) {
+        Node current = mRoot;
+        final int length = phoneNumber.length();
+        char ch;
+        for (int i = 0; i < length; i++) {
+            ch = phoneNumber.charAt(i);
+            if (ch >= '0' && ch <= '9') {
+                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.
+     *
+     * @param contact Contact to put
+     * @param root Root node to use as the starting point
+     * @param prefix Sequence of bytes which represent the index at
+     * @param start - Starting index of the byte array
+     * @param end - Last index(not inclusive) of the byte array
+     * @param isFullName If true, prefix will be treated as a full name and recursive calls to add
+     *        initial matches as well as name token matches into the trie will be made.
+     * @param addInitials If true, recursive calls to add initial matches into the trie will be
+     *        made.
+     */
+    private void putForPrefix(ContactNumber contact, Node root, byte[] prefix, int start, int end,
+            boolean isFullName, boolean addInitials) {
+        Node current = root;
+        Node initialNode = root;
+        final int length = end;
+        boolean atSeparator = true;
+        byte index;
+        for (int i = start; i < length; i++) {
+            index = prefix[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 (addInitials || isFullName) {
+                        if (initialNode != this.mRoot) {
+                            if (isFullName) {
+                                putForPrefix(contact, this.mRoot, prefix, i, prefix.length, false,
+                                        true);
+                            }
+                            putForPrefix(contact, initialNode,
+                                    prefix, i, prefix.length, false, false);
+                        }
+                    }
+
+                    // Finding a new name token means we find a new initial character as well.
+                    // Use initialNode to track the current node at which initial characters match.
+                    // E.g. If we are at character m of John W S(m)ith, then the current initial
+                    // node is indexed by the characters JWS.
+                    initialNode = initialNode.getChild(index, true);
+                }
+                current = current.getChild(index, true);
+            } else {
+                atSeparator = true;
+            }
+        }
+        current.add(contact);
+    }
+
+    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;
+        }
+    }
+}
diff --git a/src/com/android/dialer/interactions/PhoneNumberInteraction.java b/src/com/android/dialer/interactions/PhoneNumberInteraction.java
index 365da2684..5321bc285 100644
--- a/src/com/android/dialer/interactions/PhoneNumberInteraction.java
+++ b/src/com/android/dialer/interactions/PhoneNumberInteraction.java
@@ -268,6 +268,7 @@ public class PhoneNumberInteraction implements OnLoadCompleteListener<Cursor> {
     private final int mInteractionType;
 
     private final String mCallOrigin;
+    private boolean mUseDefault;
 
     private CursorLoader mLoader;
 
@@ -313,14 +314,29 @@ public class PhoneNumberInteraction implements OnLoadCompleteListener<Cursor> {
 
     /**
      * Initiates the interaction. This may result in a phone call or sms message started
-     * or a disambiguation dialog to determine which phone number should be used.
+     * or a disambiguation dialog to determine which phone number should be used. If there
+     * is a primary phone number, it will be automatically used and a disambiguation dialog
+     * will no be shown.
      */
     @VisibleForTesting
     /* package */ void startInteraction(Uri uri) {
+        startInteraction(uri, true);
+    }
+
+    /**
+     * Initiates the interaction to result in either a phone call or sms message for a contact.
+     * @param uri Contact Uri
+     * @param useDefault Whether or not to use the primary(default) phone number. If true, the
+     * primary phone number will always be used by default if one is available. If false, a
+     * disambiguation dialog will be shown regardless of whether or not a primary phone number
+     * is available.
+     */
+    @VisibleForTesting
+    /* package */ void startInteraction(Uri uri, boolean useDefault) {
         if (mLoader != null) {
             mLoader.reset();
         }
-
+        mUseDefault = useDefault;
         final Uri queryUri;
         final String inputUriAsString = uri.toString();
         if (inputUriAsString.startsWith(Contacts.CONTENT_URI.toString())) {
@@ -352,15 +368,13 @@ public class PhoneNumberInteraction implements OnLoadCompleteListener<Cursor> {
             onDismiss();
             return;
         }
-
         ArrayList<PhoneItem> phoneList = new ArrayList<PhoneItem>();
         String primaryPhone = null;
         try {
             while (cursor.moveToNext()) {
-                if (cursor.getInt(cursor.getColumnIndex(Phone.IS_SUPER_PRIMARY)) != 0) {
+                if (mUseDefault && cursor.getInt(cursor.getColumnIndex(Phone.IS_SUPER_PRIMARY)) != 0) {
                     // Found super primary, call it.
                     primaryPhone = cursor.getString(cursor.getColumnIndex(Phone.NUMBER));
-                    break;
                 }
 
                 PhoneItem item = new PhoneItem();
@@ -379,7 +393,7 @@ public class PhoneNumberInteraction implements OnLoadCompleteListener<Cursor> {
             cursor.close();
         }
 
-        if (primaryPhone != null) {
+        if (mUseDefault && primaryPhone != null) {
             performAction(primaryPhone);
             onDismiss();
             return;
@@ -423,7 +437,28 @@ public class PhoneNumberInteraction implements OnLoadCompleteListener<Cursor> {
      */
     public static void startInteractionForPhoneCall(TransactionSafeActivity activity, Uri uri) {
         (new PhoneNumberInteraction(activity, ContactDisplayUtils.INTERACTION_CALL, null))
-                .startInteraction(uri);
+                .startInteraction(uri, true);
+    }
+
+    /**
+     * Start call action using given contact Uri. If there are multiple candidates for the phone
+     * call, dialog is automatically shown and the user is asked to choose one.
+     *
+     * @param activity that is calling this interaction. This must be of type
+     * {@link TransactionSafeActivity} because we need to check on the activity state after the
+     * phone numbers have been queried for.
+     * @param uri contact Uri (built from {@link Contacts#CONTENT_URI}) or data Uri
+     * (built from {@link Data#CONTENT_URI}). Contact Uri may show the disambiguation dialog while
+     * data Uri won't.
+     * @param useDefault Whether or not to use the primary(default) phone number. If true, the
+     * primary phone number will always be used by default if one is available. If false, a
+     * disambiguation dialog will be shown regardless of whether or not a primary phone number
+     * is available.
+     */
+    public static void startInteractionForPhoneCall(TransactionSafeActivity activity, Uri uri,
+            boolean useDefault) {
+        (new PhoneNumberInteraction(activity, ContactDisplayUtils.INTERACTION_CALL, null))
+                .startInteraction(uri, useDefault);
     }
 
     /**
@@ -437,7 +472,7 @@ public class PhoneNumberInteraction implements OnLoadCompleteListener<Cursor> {
     public static void startInteractionForPhoneCall(TransactionSafeActivity activity, Uri uri,
             String callOrigin) {
         (new PhoneNumberInteraction(activity, ContactDisplayUtils.INTERACTION_CALL, null, callOrigin))
-                .startInteraction(uri);
+                .startInteraction(uri, true);
     }
 
     /**
@@ -454,7 +489,7 @@ public class PhoneNumberInteraction implements OnLoadCompleteListener<Cursor> {
      */
     public static void startInteractionForTextMessage(TransactionSafeActivity activity, Uri uri) {
         (new PhoneNumberInteraction(activity, ContactDisplayUtils.INTERACTION_SMS, null))
-                .startInteraction(uri);
+                .startInteraction(uri, true);
     }
 
     @VisibleForTesting
diff --git a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java
new file mode 100644
index 000000000..0378555d0
--- /dev/null
+++ b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java
@@ -0,0 +1,195 @@
+/*
+ * 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 static com.android.dialer.dialpad.SmartDialCache.ContactNumber;
+
+import com.android.dialer.dialpad.SmartDialTrie.Node;
+
+import android.test.suitebuilder.annotation.SmallTest;
+
+import junit.framework.TestCase;
+
+/**
+ * To run this test, use the command:
+ * adb shell am instrument -w -e class com.android.dialer.dialpad.SmartDialTrieTest /
+ * com.android.dialer.tests/android.test.InstrumentationTestRunner
+ */
+@SmallTest
+public class SmartDialTrieTest extends TestCase{
+
+    public void testSize() {
+        final SmartDialTrie trie = new SmartDialTrie();
+        trie.put(new ContactNumber(0, "Jason", "0", "0", 1));
+        assertEquals(1, trie.size());
+        trie.put(new ContactNumber(1, "Mary", "0", "1", 2));
+        assertEquals(2, trie.size());
+        trie.put(new ContactNumber(2, "John", "0", "2", 3));
+        assertEquals(3, trie.size());
+    }
+
+    public void testPutForFullName() {
+        final SmartDialTrie trie = new SmartDialTrie();
+        final ContactNumber jasonsmith = new ContactNumber(0, "Jason Smith", "0", "0", 1);
+        final ContactNumber jasonsmitt = new ContactNumber(1, "Jason Smitt", "0", "1", 2);
+        trie.put(jasonsmith);
+        trie.put(jasonsmitt);
+        assertEquals(true, trie.getAllWithPrefix("5276676484").contains(jasonsmith));
+        assertEquals(false, trie.getAllWithPrefix("5276676484").contains(jasonsmitt));
+
+        assertEquals(false, trie.getAllWithPrefix("5276676488").contains(jasonsmith));
+        assertEquals(true, trie.getAllWithPrefix("5276676488").contains(jasonsmitt));
+
+    }
+
+    public void testPutForPartialName() {
+        final SmartDialTrie trie = new SmartDialTrie();
+        final ContactNumber maryjane = new ContactNumber(0, "Mary Jane", "0", "0", 1);
+        final ContactNumber sarahsmith = new ContactNumber(1, "Sarah Smith", "0", "1", 2);
+        final ContactNumber jasonsmitt = new ContactNumber(2, "Jason Smitt", "0", "2", 3);
+        trie.put(maryjane);
+        trie.put(sarahsmith);
+        trie.put(jasonsmitt);
+
+        // 6279 corresponds to mary = "Mary Jane" but not "Jason Smitt"
+        assertEquals(true, checkContains(trie, maryjane, "6279"));
+        assertEquals(false, checkContains(trie, jasonsmitt, "6279"));
+
+        // 72 corresponds to sa = "Sarah Smith" but not "Jason Smitt" or "Mary Jane"
+        assertEquals(false, checkContains(trie, maryjane, "72"));
+        assertEquals(true, checkContains(trie, sarahsmith, "72"));
+        assertEquals(false, checkContains(trie, jasonsmitt, "72"));
+
+        // 76 corresponds to sm = "Sarah Smith" and "Jason Smitt" but not "Mary Jane"
+        assertEquals(false, checkContains(trie, maryjane, "76"));
+        assertEquals(true, checkContains(trie, sarahsmith, "76"));
+        assertEquals(true, checkContains(trie, jasonsmitt, "76"));
+    }
+
+    public void testPutForNameTokens() {
+        final SmartDialTrie trie = new SmartDialTrie();
+        final ContactNumber jasonfwilliams = new ContactNumber(0, "Jason F. Williams", "0", "0", 1);
+        trie.put(jasonfwilliams);
+
+        // 527 corresponds to jas = "Jason"
+        assertEquals(true, checkContains(trie, jasonfwilliams, "527"));
+        // 945 corresponds to wil = "Wil"
+        assertEquals(true, checkContains(trie, jasonfwilliams, "945"));
+        // 66 doesn't match
+        assertEquals(false, checkContains(trie, jasonfwilliams, "66"));
+    }
+
+    public void testPutForInitialMatches() {
+        final SmartDialTrie trie = new SmartDialTrie();
+        final ContactNumber martinjuniorharry =
+                new ContactNumber(0, "Martin Jr Harry", "0", "0", 1);
+        trie.put(martinjuniorharry);
+        // 654 corresponds to mjh = "(M)artin (J)r (H)arry"
+        assertEquals(true, checkContains(trie, martinjuniorharry, "654"));
+        // The reverse (456) does not match (for now)
+        assertEquals(false, checkContains(trie, martinjuniorharry, "456"));
+        // 6542 corresponds to mjha = "(M)artin (J)r (Ha)rry"
+        assertEquals(true, checkContains(trie, martinjuniorharry, "6542"));
+        // 542 corresponds to jha = "Martin (J)r (Ha)rry"
+        assertEquals(true, checkContains(trie, martinjuniorharry, "542"));
+        // 547 doesn't match
+        assertEquals(false, checkContains(trie, martinjuniorharry, "547"));
+        // 655 doesn't match
+        assertEquals(false, checkContains(trie, martinjuniorharry, "655"));
+        // 653 doesn't match
+        assertEquals(false, checkContains(trie, martinjuniorharry, "653"));
+        // 6543 doesn't match
+        assertEquals(false, checkContains(trie, martinjuniorharry, "6543"));
+    }
+
+    public void testSeparators() {
+        SmartDialTrie trie = new SmartDialTrie();
+        String name = "Mcdonald Jamie-Cullum";
+        byte[] bytes = trie.toByteArray(name);
+        // Make sure the dash is correctly converted to a separator character
+        for (int i = 0; i < name.length(); i++) {
+            // separators at position 8 and 12
+            if (i == 8 || i == 14) {
+                assertEquals(true, bytes[i] == -1);
+            } else {
+                assertEquals(false, bytes[i] == -1);
+            }
+        }
+    }
+
+    public void testAccentedCharacters() {
+        final SmartDialTrie trie = new SmartDialTrie();
+        final ContactNumber reenee = new ContactNumber(0, "Reenée", "0", "0", 1);
+        final ContactNumber bronte = new ContactNumber(2, "Brontë", "0", "1", 2);
+        trie.put(reenee);
+        trie.put(bronte);
+        assertEquals(true, checkContains(trie, reenee, "733633"));
+        assertEquals(true, checkContains(trie, bronte, "276683"));
+    }
+
+    public void testPutForNumbers() {
+        final SmartDialTrie trie = new SmartDialTrie();
+        final ContactNumber contactno1 = new ContactNumber(0, "James", "510-527-2357", "0", 1);
+        trie.put(contactno1);
+        final ContactNumber contactno2 = new ContactNumber(0, "James", "77212862357", "0", 1);
+        trie.put(contactno2);
+        final ContactNumber contactno3 = new ContactNumber(0, "James", "+13684976334", "0", 1);
+        trie.put(contactno3);
+        // all phone numbers belonging to the contact should correspond to it
+        assertEquals(true, checkContains(trie, contactno1, "510"));
+        assertEquals(false, checkContains(trie, contactno1, "511"));
+        assertEquals(true, checkContains(trie, contactno2, "77212862357"));
+        assertEquals(false, checkContains(trie, contactno2, "77212862356"));
+        assertEquals(true, checkContains(trie, contactno3, "1368"));
+        assertEquals(false, checkContains(trie, contactno3, "1367"));
+
+    }
+
+    public void testNodeConstructor() {
+        final Node n = new Node();
+        // Node member variables should not be initialized by default at construction to reduce
+        // unnecessary memory usage
+        assertEquals(-1, n.getChildrenSize());
+        assertNull(n.getChild(5, false));
+        assertNull(n.getChild(0, false));
+    }
+
+    public void testNodeGetChild() {
+        final Node n = new Node();
+        // A node shouldn't contain children until getChild(index, true) is called
+        assertEquals(-1, n.getChildrenSize());
+        final Node child = n.getChild(1, true);
+        // A node should always have 10 children once the child array is created
+        assertEquals(10, n.getChildrenSize());
+        // getChild(index, true) should never return null
+        assertNotNull(child);
+    }
+
+    public void testNodeAddContact() {
+        final Node n = new Node();
+        assertNull(n.getContents());
+        final ContactNumber contact = new ContactNumber(0, "James", "510-527-2357", "0", 1);
+        final ContactNumber contactNotIn = new ContactNumber(2, "Jason Smitt", "0", "2", 3);
+        n.add(contact);
+        assertEquals(true, n.getContents().contains(contact));
+        assertEquals(false, n.getContents().contains(contactNotIn));
+    }
+
+    private boolean checkContains(SmartDialTrie trie, ContactNumber contact, CharSequence prefix) {
+        return trie.getAllWithPrefix(prefix).contains(contact);
+    }
+}