diff --git a/res/layout/dialpad_fragment.xml b/res/layout/dialpad_fragment.xml
index e672551..27ba2da 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 eed2570..54f2a08 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 ebdc2f6..288f58b 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 b862f76..f70a279 100644
--- a/src/com/android/dialer/dialpad/DialpadFragment.java
+++ b/src/com/android/dialer/dialpad/DialpadFragment.java
@@ -25,6 +25,7 @@
 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.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.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 @@
      * 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 @@
 
         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 @@
         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 @@
             mSmartDialAdapter = new SmartDialAdapter(getActivity());
             mSmartDialList.setAdapter(mSmartDialAdapter);
             mSmartDialList.setOnItemClickListener(new OnSmartDialItemClick());
+            mSmartDialList.setOnItemLongClickListener(new OnSmartDialLongClick());
         }
 
         return fragmentView;
@@ -608,6 +618,9 @@
         stopWatch.lap("bes");
 
         stopWatch.stopAndLog(TAG, 50);
+
+        this.getActivity().getContentResolver().registerContentObserver(
+                SmartDialCache.PhoneQuery.URI, true, mSmartDialObserver);
     }
 
     @Override
@@ -635,6 +648,8 @@
         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 void setUserVisibleHint(boolean isVisibleToUser) {
         super.setUserVisibleHint(isVisibleToUser);
         if (isVisibleToUser) {
-            mSmartDialCache.cacheIfNeeded();
+            mSmartDialCache.cacheIfNeeded(false);
         }
     }
 
@@ -1691,28 +1706,43 @@
             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 a484731..0a246e3 100644
--- a/src/com/android/dialer/dialpad/SmartDialAdapter.java
+++ b/src/com/android/dialer/dialpad/SmartDialAdapter.java
@@ -18,15 +18,16 @@
 
 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 @@
     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 @@
 
     @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 c4d184d..71f4dfe 100644
--- a/src/com/android/dialer/dialpad/SmartDialCache.java
+++ b/src/com/android/dialer/dialpad/SmartDialCache.java
@@ -19,80 +19,129 @@
 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 com.google.common.base.Preconditions;
+
+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
-            };
+    public static interface PhoneQuery {
 
-        int COLUMN_ID = 0;
-        int COLUMN_DISPLAY_NAME = 1;
-        int COLUMN_LOOKUP_KEY = 2;
+       Uri URI = Phone.CONTENT_URI.buildUpon().
+               appendQueryParameter(ContactsContract.DIRECTORY_PARAM_KEY,
+               String.valueOf(Directory.DEFAULT)).
+               appendQueryParameter(ContactsContract.REMOVE_DUPLICATE_ENTRIES, "true").
+               build();
 
-        String SELECTION =
-                Contacts.HAS_PHONE_NUMBER + "=1";
+       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
+        };
 
-        String ORDER_BY = Contacts.LAST_TIME_CONTACTED + " DESC";
+        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();
 
-    private static final boolean DEBUG = true; // STOPSHIP change to false.
+    public static final int CACHE_NEEDS_RECACHE = 1;
+    public static final int CACHE_IN_PROGRESS = 2;
+    public static final int CACHE_COMPLETED = 3;
 
-    public SmartDialCache(Context context, int nameDisplayOrder) {
+    private static final boolean DEBUG = true;
+
+    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 @@
      * 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 @@
         }).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 101678d..d658f3d 100644
--- a/src/com/android/dialer/dialpad/SmartDialEntry.java
+++ b/src/com/android/dialer/dialpad/SmartDialEntry.java
@@ -24,13 +24,18 @@
     /** 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 8ec9e9b..c2b1c2d 100644
--- a/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
+++ b/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
@@ -26,11 +26,16 @@
 
 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 @@
 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 @@
 
     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 @@
         this.mCallback = callback;
         this.mNameMatcher = new SmartDialNameMatcher(PhoneNumberUtils.normalizeNumber(query));
         this.mContactsCache = cache;
+        this.mQuery = query;
     }
 
     @Override
@@ -73,7 +81,7 @@
     @Override
     protected void onPostExecute(List<SmartDialEntry> result) {
         if (mCallback != null) {
-            mCallback.setSmartDialAdapterEntries(result);
+            mCallback.setSmartDialAdapterEntries(result, mQuery);
         }
     }
 
@@ -83,40 +91,76 @@
      * 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 6f0f354..381e747 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 @@
 
     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 @@
      * 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 @@
             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 'ǲ': return 'D';
-            case 'Ǵ': return 'G';
+            case 'ǲ': 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 @@
     }
 
     /**
-     * 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 @@
     }
 
     /**
+     * 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 @@
      * 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 @@
             }
             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 @@
                                 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 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 0000000..9819267
--- /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 365da26..5321bc2 100644
--- a/src/com/android/dialer/interactions/PhoneNumberInteraction.java
+++ b/src/com/android/dialer/interactions/PhoneNumberInteraction.java
@@ -268,6 +268,7 @@
     private final int mInteractionType;
 
     private final String mCallOrigin;
+    private boolean mUseDefault;
 
     private CursorLoader mLoader;
 
@@ -313,14 +314,29 @@
 
     /**
      * 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 @@
             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 @@
             cursor.close();
         }
 
-        if (primaryPhone != null) {
+        if (mUseDefault && primaryPhone != null) {
             performAction(primaryPhone);
             onDismiss();
             return;
@@ -423,7 +437,28 @@
      */
     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 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 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 0000000..0378555
--- /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);
+    }
+}