Merge "Add smart dialling capabilities to dialer"

7 files changed, 945 insertions, 2 deletions

diff --git a/src/com/android/dialer/dialpad/DialpadFragment.java b/src/com/android/dialer/dialpad/DialpadFragment.java
index 093e47d97..f7a9056f5 100644
--- a/src/com/android/dialer/dialpad/DialpadFragment.java
+++ b/src/com/android/dialer/dialpad/DialpadFragment.java
@@ -31,6 +31,7 @@ import android.graphics.BitmapFactory;
 import android.media.AudioManager;
 import android.media.ToneGenerator;
 import android.net.Uri;
+import android.os.AsyncTask;
 import android.os.Bundle;
 import android.os.RemoteException;
 import android.os.ServiceManager;
@@ -39,6 +40,7 @@ import android.provider.Contacts.Intents.Insert;
 import android.provider.Contacts.People;
 import android.provider.Contacts.Phones;
 import android.provider.Contacts.PhonesColumns;
+import android.provider.ContactsContract.Contacts;
 import android.provider.Settings;
 import android.telephony.PhoneNumberUtils;
 import android.telephony.PhoneStateListener;
@@ -59,6 +61,7 @@ import android.view.MenuItem;
 import android.view.View;
 import android.view.ViewConfiguration;
 import android.view.ViewGroup;
+import android.widget.AbsListView;
 import android.widget.AdapterView;
 import android.widget.BaseAdapter;
 import android.widget.EditText;
@@ -68,9 +71,12 @@ import android.widget.PopupMenu;
 import android.widget.TextView;
 
 import com.android.contacts.common.CallUtil;
+import com.android.contacts.common.activity.TransactionSafeActivity;
+import com.android.dialer.interactions.PhoneNumberInteraction;
 import com.android.contacts.common.GeoUtil;
 import com.android.contacts.common.util.PhoneNumberFormatter;
 import com.android.contacts.common.util.StopWatch;
+import com.android.contacts.common.preference.ContactsPreferences;
 import com.android.dialer.DialtactsActivity;
 import com.android.dialer.R;
 import com.android.dialer.SpecialCharSequenceMgr;
@@ -79,6 +85,9 @@ import com.android.internal.telephony.ITelephony;
 import com.android.phone.common.CallLogAsync;
 import com.android.phone.common.HapticFeedback;
 
+import java.util.ArrayList;
+import java.util.List;
+
 /**
  * Fragment that displays a twelve-key phone dialpad.
  */
@@ -87,7 +96,8 @@ public class DialpadFragment extends Fragment
         View.OnLongClickListener, View.OnKeyListener,
         AdapterView.OnItemClickListener, TextWatcher,
         PopupMenu.OnMenuItemClickListener,
-        DialpadImageButton.OnPressedListener {
+        DialpadImageButton.OnPressedListener,
+        SmartDialLoaderTask.SmartDialLoaderCallback {
     private static final String TAG = DialpadFragment.class.getSimpleName();
 
     private static final boolean DEBUG = DialtactsActivity.DEBUG;
@@ -104,6 +114,8 @@ public class DialpadFragment extends Fragment
     /** Stream type used to play the DTMF tones off call, and mapped to the volume control keys */
     private static final int DIAL_TONE_STREAM_TYPE = AudioManager.STREAM_DTMF;
 
+    private ContactsPreferences mContactsPrefs;
+
     /**
      * View (usually FrameLayout) containing mDigits field. This can be null, in which mDigits
      * isn't enclosed by the container.
@@ -131,6 +143,15 @@ public class DialpadFragment extends Fragment
     private ListView mDialpadChooser;
     private DialpadChooserAdapter mDialpadChooserAdapter;
 
+    /** Will be set only if the view has the smart dialing section. */
+    private AbsListView mSmartDialList;
+
+    /**
+     * Adapter for {@link #mSmartDialList}.
+     * Will be set only if the view has the smart dialing section.
+     */
+    private SmartDialAdapter mSmartDialAdapter;
+
     /**
      * Regular expression prohibiting manual phone call. Can be empty, which means "no rule".
      */
@@ -149,6 +170,7 @@ public class DialpadFragment extends Fragment
     // Vibration (haptic feedback) for dialer key presses.
     private final HapticFeedback mHaptic = new HapticFeedback();
 
+    private boolean mNeedToCacheSmartDial = false;
     /** Identifier for the "Add Call" intent extra. */
     private static final String ADD_CALL_MODE_KEY = "add_call_mode";
 
@@ -248,14 +270,16 @@ public class DialpadFragment extends Fragment
         }
 
         updateDialAndDeleteButtonEnabledState();
+        loadSmartDialEntries();
     }
 
     @Override
     public void onCreate(Bundle state) {
         super.onCreate(state);
 
+        mContactsPrefs = new ContactsPreferences(getActivity());
         mCurrentCountryIso = GeoUtil.getCurrentCountryIso(getActivity());
-
+        mNeedToCacheSmartDial = true;
         try {
             mHaptic.init(getActivity(),
                          getResources().getBoolean(R.bool.config_enable_dialer_key_vibration));
@@ -271,6 +295,13 @@ public class DialpadFragment extends Fragment
         if (state != null) {
             mDigitsFilledByIntent = state.getBoolean(PREF_DIGITS_FILLED_BY_INTENT);
         }
+
+        // Start caching contacts to use for smart dialling only if the dialpad fragment is visible
+        if (getUserVisibleHint()) {
+            SmartDialLoaderTask.startCacheContactsTaskIfNeeded(
+                    getActivity(), mContactsPrefs.getDisplayOrder());
+            mNeedToCacheSmartDial = false;
+        }
     }
 
     @Override
@@ -336,6 +367,14 @@ public class DialpadFragment extends Fragment
         mDialpadChooser = (ListView) fragmentView.findViewById(R.id.dialpadChooser);
         mDialpadChooser.setOnItemClickListener(this);
 
+        // Smart dial
+        mSmartDialList = (AbsListView) fragmentView.findViewById(R.id.dialpad_smartdial_list);
+        if (mSmartDialList != null) {
+            mSmartDialAdapter = new SmartDialAdapter(getActivity());
+            mSmartDialList.setAdapter(mSmartDialAdapter);
+            mSmartDialList.setOnItemClickListener(new OnSmartDialItemClick());
+        }
+
         return fragmentView;
     }
 
@@ -1109,6 +1148,11 @@ public class DialpadFragment extends Fragment
         }
     }
 
+    private String getCallOrigin() {
+        return (getActivity() instanceof DialtactsActivity) ?
+                ((DialtactsActivity) getActivity()).getCallOrigin() : null;
+    }
+
     private void handleDialButtonClickWithEmptyDigits() {
         if (phoneIsCdma() && phoneIsOffhook()) {
             // This is really CDMA specific. On GSM is it possible
@@ -1631,4 +1675,59 @@ public class DialpadFragment extends Fragment
         intent.putExtra(EXTRA_SEND_EMPTY_FLASH, true);
         return intent;
     }
+
+    @Override
+    public void setUserVisibleHint(boolean isVisibleToUser) {
+        super.setUserVisibleHint(isVisibleToUser);
+        if (isVisibleToUser && mNeedToCacheSmartDial) {
+            SmartDialLoaderTask.startCacheContactsTaskIfNeeded(
+                    getActivity(), mContactsPrefs.getDisplayOrder());
+            mNeedToCacheSmartDial = false;
+        }
+    }
+
+    private String mLastDigitsForSmartDial;
+
+    private void loadSmartDialEntries() {
+        if (mSmartDialAdapter == null) {
+            // No smart dial views.  Landscape?
+            return;
+        }
+
+        // Update only when the digits have changed.
+        final String digits = SmartDialNameMatcher.normalizeNumber(mDigits.getText().toString());
+        if (TextUtils.equals(digits, mLastDigitsForSmartDial)) {
+            return;
+        }
+        mLastDigitsForSmartDial = digits;
+
+        if (digits.length() < 2) {
+            mSmartDialAdapter.clear();
+        } else {
+            final SmartDialLoaderTask task = new SmartDialLoaderTask(this, digits);
+            // 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 || data.isEmpty()) {
+            // No results found.  Keep the last results.
+            return;
+        }
+        mSmartDialAdapter.setEntries(data);
+    }
+
+    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.
+
+            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
new file mode 100644
index 000000000..9330909e7
--- /dev/null
+++ b/src/com/android/dialer/dialpad/SmartDialAdapter.java
@@ -0,0 +1,169 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dialer.dialpad;
+
+import com.android.contacts.R;
+import com.google.common.collect.Lists;
+
+import android.content.Context;
+import android.content.res.Resources;
+import android.graphics.Color;
+import android.graphics.Paint;
+import android.graphics.drawable.Drawable;
+import android.text.Spannable;
+import android.text.SpannableString;
+import android.text.style.CharacterStyle;
+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.TextView;
+
+import java.util.List;
+
+public class SmartDialAdapter extends BaseAdapter {
+    public static final String LOG_TAG = "SmartDial";
+    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();
+    }
+
+    /** Remove all entries. */
+    public void clear() {
+        mEntries = Lists.newArrayList();
+        notifyDataSetChanged();
+    }
+
+    /** Set entries. */
+    public void setEntries(List<SmartDialEntry> entries) {
+        if (entries == null) throw new IllegalArgumentException();
+        mEntries = entries;
+
+        if (mEntries.size() <= 1) {
+            // add a null entry to push the single entry into the middle
+            mEntries.add(0, null);
+        } else if (mEntries.size() >= 2){
+            // swap the 1st and 2nd entries so that the highest confidence match goes into the
+            // middle
+            final SmartDialEntry temp = mEntries.get(0);
+            mEntries.set(0, mEntries.get(1));
+            mEntries.set(1, temp);
+        }
+
+        notifyDataSetChanged();
+    }
+
+    @Override
+    public boolean isEnabled(int position) {
+        return !(mEntries.get(position) == null);
+    }
+
+    @Override
+    public boolean areAllItemsEnabled() {
+        return false;
+    }
+
+    @Override
+    public int getCount() {
+        return mEntries.size();
+    }
+
+    @Override
+    public Object getItem(int position) {
+        return mEntries.get(position);
+    }
+
+    @Override
+    public long getItemId(int position) {
+        return position; // Just use the position as the ID, so it's not stable.
+    }
+
+    @Override
+    public boolean hasStableIds() {
+        return false; // Not stable because we just use the position as the ID.
+    }
+
+    @Override
+    public View getView(int position, View convertView, ViewGroup parent) {
+        final SmartDialTextView view;
+        if (convertView == null) {
+            view = (SmartDialTextView) mInflater.inflate(
+                    R.layout.dialpad_smartdial_item, parent, false);
+        } else {
+            view = (SmartDialTextView) convertView;
+        }
+        // Set the display name with highlight.
+
+        final SmartDialEntry item = mEntries.get(position);
+
+        if (item == null) {
+            // Clear the text in case the view was reused.
+            view.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);
+                }
+            }
+        }
+
+        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);
+        }
+
+
+        view.setText(displayName);
+        view.setTag(item);
+
+        return view;
+    }
+}
diff --git a/src/com/android/dialer/dialpad/SmartDialEntry.java b/src/com/android/dialer/dialpad/SmartDialEntry.java
new file mode 100644
index 000000000..101678de0
--- /dev/null
+++ b/src/com/android/dialer/dialpad/SmartDialEntry.java
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dialer.dialpad;
+
+import android.net.Uri;
+
+import java.util.ArrayList;
+
+public class SmartDialEntry {
+    /** Display name for the contact. */
+    public final CharSequence displayName;
+    public final Uri contactUri;
+
+    public final ArrayList<SmartDialMatchPosition> matchPositions;
+
+    public SmartDialEntry(CharSequence displayName, Uri contactUri,
+            ArrayList<SmartDialMatchPosition> matchPositions) {
+        this.displayName = displayName;
+        this.contactUri = contactUri;
+        this.matchPositions = matchPositions;
+    }
+}
diff --git a/src/com/android/dialer/dialpad/SmartDialLoaderTask.java b/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
new file mode 100644
index 000000000..ec99d8a14
--- /dev/null
+++ b/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
@@ -0,0 +1,249 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dialer.dialpad;
+
+import static com.android.dialer.dialpad.SmartDialAdapter.LOG_TAG;
+
+import com.google.common.collect.Lists;
+
+import android.content.Context;
+import android.database.Cursor;
+import android.net.Uri;
+import android.os.AsyncTask;
+import android.provider.ContactsContract;
+import android.provider.ContactsContract.Contacts;
+import android.telephony.PhoneNumberUtils;
+import android.util.Log;
+
+import com.android.contacts.common.preference.ContactsPreferences;
+import com.android.contacts.common.util.StopWatch;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * AsyncTask that performs one of two functions depending on which constructor is used.
+ * If {@link #SmartDialLoaderTask(Context context, int nameDisplayOrder)} is used, the task
+ * caches all contacts with a phone number into the static variable {@link #sContactsCache}.
+ * If {@link #SmartDialLoaderTask(SmartDialLoaderCallback callback, String query)} is used, the
+ * task searches through the cache to return the top 3 contacts(ranked by confidence) that match
+ * the query, then passes it back to the {@link SmartDialLoaderCallback} through a callback
+ * function.
+ */
+// TODO: Make the cache a singleton class and refactor to fix possible concurrency issues in the
+// future
+public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDialEntry>> {
+
+    private class Contact {
+        final String mDisplayName;
+        final String mStrippedDisplayName;
+        final String mLookupKey;
+        final long mId;
+
+        public Contact(long id, String displayName, String lookupKey) {
+            mDisplayName = displayName;
+            mStrippedDisplayName = SmartDialNameMatcher.stripDiacritics(displayName);
+            mLookupKey = lookupKey;
+            mId = id;
+        }
+    }
+
+    public interface SmartDialLoaderCallback {
+        void setSmartDialAdapterEntries(List<SmartDialEntry> list);
+    }
+
+    static private final boolean DEBUG = true; // STOPSHIP change to false.
+
+    private static final int MAX_ENTRIES = 3;
+
+    private static List<Contact> sContactsCache;
+
+    private final boolean mCacheOnly;
+
+    private final SmartDialLoaderCallback mCallback;
+
+    private final Context mContext;
+    /**
+     * See {@link ContactsPreferences#getDisplayOrder()}.
+     * {@link ContactsContract.Preferences#DISPLAY_ORDER_PRIMARY} (first name first)
+     * {@link ContactsContract.Preferences#DISPLAY_ORDER_ALTERNATIVE} (last name first)
+     */
+    private final int mNameDisplayOrder;
+
+    private final SmartDialNameMatcher mNameMatcher;
+
+    // cache only constructor
+    private SmartDialLoaderTask(Context context, int nameDisplayOrder) {
+        this.mNameDisplayOrder = nameDisplayOrder;
+        this.mContext = context;
+        // we're just caching contacts so no need to initialize a SmartDialNameMatcher or callback
+        this.mNameMatcher = null;
+        this.mCallback = null;
+        this.mCacheOnly = true;
+    }
+
+    public SmartDialLoaderTask(SmartDialLoaderCallback callback, String query) {
+        this.mCallback = callback;
+        this.mContext = null;
+        this.mCacheOnly = false;
+        this.mNameDisplayOrder = 0;
+        this.mNameMatcher = new SmartDialNameMatcher(PhoneNumberUtils.normalizeNumber(query));
+    }
+
+    @Override
+    protected List<SmartDialEntry> doInBackground(String... params) {
+        if (mCacheOnly) {
+            cacheContacts();
+            return Lists.newArrayList();
+        }
+
+        return getContactMatches();
+    }
+
+    @Override
+    protected void onPostExecute(List<SmartDialEntry> result) {
+        if (mCallback != null) {
+            mCallback.setSmartDialAdapterEntries(result);
+        }
+    }
+
+    /** 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.IN_VISIBLE_GROUP + "=1 and " +
+                Contacts.HAS_PHONE_NUMBER + "=1";
+
+        String ORDER_BY = Contacts.LAST_TIME_CONTACTED + " DESC";
+    }
+
+    public static void startCacheContactsTaskIfNeeded(Context context, int displayOrder) {
+        if (sContactsCache != null) {
+            // contacts have already been cached, just return
+            return;
+        }
+        final SmartDialLoaderTask task =
+                new SmartDialLoaderTask(context, displayOrder);
+        task.execute();
+    }
+
+    /**
+     * Caches the contacts into an in memory array list. This is called once at startup and should
+     * not be cancelled.
+     */
+    private void cacheContacts() {
+        final StopWatch stopWatch = DEBUG ? StopWatch.start("SmartDial Cache") : null;
+        if (sContactsCache != null) {
+            // contacts have already been cached, just return
+            stopWatch.stopAndLog("SmartDial Already Cached", 0);
+            return;
+        }
+
+        final Cursor c = mContext.getContentResolver().query(ContactQuery.URI,
+                (mNameDisplayOrder == ContactsContract.Preferences.DISPLAY_ORDER_PRIMARY)
+                    ? ContactQuery.PROJECTION : ContactQuery.PROJECTION_ALTERNATIVE,
+                ContactQuery.SELECTION, null,
+                ContactQuery.ORDER_BY);
+        if (c == null) {
+            stopWatch.stopAndLog("Query Failuregi", 0);
+            return;
+        }
+        sContactsCache = Lists.newArrayListWithCapacity(c.getCount());
+        try {
+            c.moveToPosition(-1);
+            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);
+                sContactsCache.add(new Contact(id, displayName, lookupKey));
+            }
+        } finally {
+            c.close();
+            if (DEBUG) {
+                stopWatch.stopAndLog("SmartDial Cache", 0);
+            }
+        }
+    }
+
+    /**
+     * Loads all visible contacts with phone numbers and check if their display names match the
+     * query.  Return at most {@link #MAX_ENTRIES} {@link SmartDialEntry}'s for the matching
+     * contacts.
+     */
+    private ArrayList<SmartDialEntry> getContactMatches() {
+        final StopWatch stopWatch = DEBUG ? StopWatch.start(LOG_TAG + " Start Match") : null;
+        if (sContactsCache == null) {
+            // contacts should have been cached by this point in time, but in case they
+            // are not, we go ahead and cache them into memory.
+            if (DEBUG) {
+                Log.d(LOG_TAG, "empty cache");
+            }
+            cacheContacts();
+            // TODO: if sContactsCache is still null at this point we should try to recache
+        }
+        if (DEBUG) {
+            Log.d(LOG_TAG, "Size of cache: " + sContactsCache.size());
+        }
+        final ArrayList<SmartDialEntry> outList = Lists.newArrayList();
+        if (sContactsCache == null) {
+            return outList;
+        }
+        int count = 0;
+        for (int i = 0; i < sContactsCache.size(); i++) {
+            final Contact contact = sContactsCache.get(i);
+            final String strippedDisplayName = contact.mStrippedDisplayName;
+
+            if (!mNameMatcher.matches(strippedDisplayName)) {
+                continue;
+            }
+            // Matched; create SmartDialEntry.
+            @SuppressWarnings("unchecked")
+            final SmartDialEntry entry = new SmartDialEntry(
+                     contact.mDisplayName,
+                     Contacts.getLookupUri(contact.mId, contact.mLookupKey),
+                     (ArrayList<SmartDialMatchPosition>) mNameMatcher.getMatchPositions().clone()
+                     );
+            outList.add(entry);
+            count++;
+            if (count >= MAX_ENTRIES) {
+                break;
+            }
+        }
+        if (DEBUG) {
+            stopWatch.stopAndLog(LOG_TAG + " Match Complete", 0);
+        }
+        return outList;
+    }
+}
diff --git a/src/com/android/dialer/dialpad/SmartDialMatchPosition.java b/src/com/android/dialer/dialpad/SmartDialMatchPosition.java
new file mode 100644
index 000000000..3d248ccb2
--- /dev/null
+++ b/src/com/android/dialer/dialpad/SmartDialMatchPosition.java
@@ -0,0 +1,70 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dialer.dialpad;
+
+import static com.android.dialer.dialpad.SmartDialAdapter.LOG_TAG;
+
+import android.util.Log;
+
+import java.util.ArrayList;
+
+/**
+ * Stores information about a range of characters matched in a display name The integers
+ * start and end indicate that the range start to end (exclusive) correspond to some characters
+ * in the query. Used by {@link SmartDialAdapter} to highlight certain parts of the contact's
+ * display name to indicate that those ranges matched the user's query.
+ */
+class SmartDialMatchPosition {
+    public int start;
+    public int end;
+
+    public SmartDialMatchPosition(int start, int end) {
+        this.start = start;
+        this.end = end;
+    }
+
+    private void advance(int toAdvance) {
+        this.start += toAdvance;
+        this.end += toAdvance;
+    }
+
+    /**
+     * Used by {@link SmartDialNameMatcher} to advance the positions of a match position found in
+     * a sub query.
+     *
+     * @param inList ArrayList of SmartDialMatchPositions to modify.
+     * @param toAdvance Offset to modify by.
+     */
+    public static void advanceMatchPositions(ArrayList<SmartDialMatchPosition> inList,
+            int toAdvance) {
+        for (int i = 0; i < inList.size(); i++) {
+            inList.get(i).advance(toAdvance);
+        }
+    }
+
+    /**
+     * Used mainly for debug purposes. Displays contents of an ArrayList of SmartDialMatchPositions.
+     *
+     * @param list ArrayList of SmartDialMatchPositions to print out in a human readable fashion.
+     */
+    public static void print(ArrayList<SmartDialMatchPosition> list) {
+        for (int i = 0; i < list.size(); i ++) {
+            SmartDialMatchPosition m = list.get(i);
+            Log.d(LOG_TAG, "[" + m.start + "," + m.end + "]");
+        }
+    }
+}
diff --git a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
new file mode 100644
index 000000000..4a340f987
--- /dev/null
+++ b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
@@ -0,0 +1,217 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dialer.dialpad;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.Lists;
+
+import com.android.contacts.test.NeededForTesting;
+
+import java.text.Normalizer;
+import java.util.ArrayList;
+
+/**
+ * {@link #SmartDialNameMatcher} contains utility functions to remove accents from accented
+ * characters and normalize a phone number. It also contains the matching logic that determines if
+ * a contact's display name matches a numeric query. The boolean variable
+ * {@link #ALLOW_INITIAL_MATCH} controls the behavior of the matching logic and determines
+ * whether we allow matches like 57 - (J)ohn (S)mith.
+ */
+public class SmartDialNameMatcher {
+
+    private final String mQuery;
+
+    private static final char[] LETTERS_TO_DIGITS = {
+        '2', '2', '2', // A,B,C -> 2
+        '3', '3', '3', // D,E,F -> 3
+        '4', '4', '4', // G,H,I -> 4
+        '5', '5', '5', // J,K,L -> 5
+        '6', '6', '6', // M,N,O -> 6
+        '7', '7', '7', '7', // P,Q,R,S -> 7
+        '8', '8', '8', // T,U,V -> 8
+        '9', '9', '9', '9' // W,X,Y,Z -> 9
+    };
+
+    private final ArrayList<SmartDialMatchPosition> mMatchPositions = Lists.newArrayList();
+
+    public SmartDialNameMatcher(String query) {
+        mQuery = query;
+    }
+
+    /**
+     * 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.)
+     *
+     * @param number Phone number we want to normalize
+     * @return Phone number consisting of digits from 2-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') {
+                s.append(ch);
+            }
+        }
+        return s.toString();
+    }
+
+    /**
+     * This function iterates through each token in the display name, trying to match the query
+     * to the numeric equivalent of the token.
+     *
+     * A token is defined as a range in the display name delimited by whitespace. For example,
+     * the display name "Phillips Thomas Jr" contains three tokens: "phillips", "thomas", and "jr".
+     *
+     * A match must begin at the start of a token.
+     * For example, typing 846(Tho) would match "Phillips Thomas", but 466(hom) would not.
+     *
+     * Also, a match can extend across tokens.
+     * For example, typing 37337(FredS) would match (Fred S)mith.
+     *
+     * @param displayName The normalized(no accented characters) display name we intend to match
+     * against.
+     * @param query The string of digits that we want to match the display name to.
+     * @param matchList An array list of {@link SmartDialMatchPosition}s that we add matched
+     * 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.
+     */
+    @VisibleForTesting
+    boolean matchesCombination(String displayName, String query,
+            ArrayList<SmartDialMatchPosition> matchList) {
+        final int nameLength = displayName.length();
+        final int queryLength = query.length();
+
+        if (nameLength < queryLength) {
+            return false;
+        }
+
+        if (queryLength == 0) {
+            return false;
+        }
+
+        // The current character index in displayName
+        // E.g. 3 corresponds to 'd' in "Fred Smith"
+        int nameStart = 0;
+
+        // The current character in the query we are trying to match the displayName against
+        int queryStart = 0;
+
+        // The start position of the current token we are inspecting
+        int tokenStart = 0;
+
+        // The number of non-alphabetic characters we've encountered so far in the current match.
+        // E.g. if we've currently matched 3733764849 to (Fred Smith W)illiam, then the
+        // seperatorCount should be 2. This allows us to correctly calculate offsets for the match
+        // positions
+        int seperatorCount = 0;
+
+        ArrayList<SmartDialMatchPosition> partial = new ArrayList<SmartDialMatchPosition>();
+
+        // Keep going until we reach the end of displayName
+        while (nameStart < nameLength && queryStart < queryLength) {
+            char ch = displayName.charAt(nameStart);
+            if ((ch >= 'A') && (ch <= 'Z')) {
+                // Simply change the ascii code to the lower case version instead of using
+                // toLowerCase for efficiency
+                ch += 32;
+            }
+            if ((ch >= 'a') && (ch <= 'z')) {
+                // a starts at index 0
+                if (LETTERS_TO_DIGITS[ch - 'a'] != query.charAt(queryStart)) {
+                    // we did not find a match
+                    queryStart = 0;
+                    seperatorCount = 0;
+                    while (nameStart < nameLength &&
+                            !Character.isWhitespace(displayName.charAt(nameStart))) {
+                        nameStart++;
+                    }
+                    nameStart++;
+                    tokenStart = nameStart;
+                } else {
+                    if (queryStart == queryLength - 1) {
+
+                        // As much as possible, we prioritize a full token match over a sub token
+                        // one so if we find a full token match, we can return right away
+                        matchList.add(new SmartDialMatchPosition(
+                                tokenStart, queryLength + tokenStart + seperatorCount));
+                        return true;
+                    }
+                    nameStart++;
+                    queryStart++;
+                    // we matched the current character in the name against one in the query,
+                    // continue and see if the rest of the characters match
+                }
+            } else {
+                // found a separator, we skip this character and continue to the next one
+                nameStart++;
+                if (queryStart == 0) {
+                    // This means we found a separator before the start of a token,
+                    // so we should increment the token's start position to reflect its true
+                    // start position
+                    tokenStart = nameStart;
+                } else {
+                    // Otherwise this separator was found in the middle of a token being matched,
+                    // so increase the separator count
+                    seperatorCount++;
+                }
+            }
+        }
+        return false;
+    }
+
+    public boolean matches(String displayName) {
+        mMatchPositions.clear();
+        return matchesCombination(displayName, mQuery, mMatchPositions);
+    }
+
+    public ArrayList<SmartDialMatchPosition> getMatchPositions() {
+        return mMatchPositions;
+    }
+
+    public String getQuery() {
+        return mQuery;
+    }
+}
diff --git a/src/com/android/dialer/dialpad/SmartDialTextView.java b/src/com/android/dialer/dialpad/SmartDialTextView.java
new file mode 100644
index 000000000..b9df48ff0
--- /dev/null
+++ b/src/com/android/dialer/dialpad/SmartDialTextView.java
@@ -0,0 +1,103 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dialer.dialpad;
+
+import android.content.Context;
+import android.content.res.Resources;
+import android.graphics.Bitmap;
+import android.graphics.Canvas;
+import android.graphics.Paint;
+import android.graphics.Rect;
+import android.graphics.Paint.Align;
+import android.graphics.drawable.BitmapDrawable;
+import android.graphics.drawable.Drawable;
+import android.text.TextPaint;
+import android.util.AttributeSet;
+import android.util.Log;
+import android.widget.TextView;
+
+import com.android.dialer.R;
+
+public class SmartDialTextView extends TextView {
+
+    private final float mPadding;
+    private final float mExtraPadding;
+    private static final String HIGH_CONFIDENCE_HINT = "\u2026";
+
+    public SmartDialTextView(Context context) {
+        this(context, null);
+    }
+
+    public SmartDialTextView(Context context, AttributeSet attrs) {
+        super(context, attrs);
+        mPadding = getResources().getDimension(R.dimen.smartdial_suggestions_padding);
+        mExtraPadding = getResources().getDimension(R.dimen.smartdial_suggestions_extra_padding);
+    }
+
+    /**
+     * Returns a drawable that resembles a sideways overflow icon. Used to indicate the presence
+     * of a high confidence match.
+     *
+     * @param res Resources that we will use to create our BitmapDrawable with
+     * @param textSize Size of drawable to create
+     * @param color Color of drawable to create
+     * @return The drawable drawn according to the given parameters
+     */
+    public static Drawable getHighConfidenceHintDrawable(final Resources res, final float textSize,
+            final int color) {
+        final Paint paint = new Paint();
+        paint.setAntiAlias(true);
+        paint.setTextAlign(Align.CENTER);
+        paint.setTextSize(textSize);
+        paint.setColor(color);
+        final Rect bounds = new Rect();
+        paint.getTextBounds(HIGH_CONFIDENCE_HINT, 0, HIGH_CONFIDENCE_HINT.length(), bounds);
+        final int width = bounds.width();
+        final int height = bounds.height();
+        final Bitmap buffer = Bitmap.createBitmap(
+                width, (height * 3 / 2), Bitmap.Config.ARGB_8888);
+        final Canvas canvas = new Canvas(buffer);
+        canvas.drawText(HIGH_CONFIDENCE_HINT, width / 2, height, paint);
+        return new BitmapDrawable(res, buffer);
+    }
+
+    @Override
+    protected void onTextChanged(CharSequence text, int start, int lengthBefore, int lengthAfter) {
+        super.onTextChanged(text, start, lengthBefore, lengthAfter);
+        rescaleText(getWidth());
+    }
+
+    @Override
+    protected void onSizeChanged(int w, int h, int oldw, int oldh) {
+        super.onSizeChanged(w, h, oldw, oldh);
+        rescaleText(w);
+    }
+
+    private void rescaleText(int w) {
+        if (w == 0) {
+            return;
+        }
+        setTextScaleX(1);
+        final Paint paint = getPaint();
+        float width = w - 2 * mPadding - 2 * mExtraPadding;
+
+        float ratio = width / paint.measureText(getText().toString());
+        if (ratio < 1.0f) {
+            setTextScaleX(ratio);
+        }
+    }
+}