From 1be0178a11b1cc3b06867b14446e1e041e97a82c Mon Sep 17 00:00:00 2001
From: Yorke Lee <yorkelee@google.com>
Date: Wed, 7 Nov 2012 15:11:44 -0800
Subject: Add smart dialling capabilities to dialer

Layout changes to dialpad fragment to make space for smart dial suggestions.
This feature does not appear in landscape mode.
SmartDialTextView automatically resizes text to fit within the bounds of the view.
SmartDialAdapter highlights certain portions of the matching name based on match
positions provided by SmartDialNameMatcher.
SmartDialLoaderTask is an AsyncTask that caches all contacts with a phone number
into memory, or matches all contact names against a provided query to return a
list of matches (maximum of 3).
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.
Added some tests for SmartDialNameMatcher

Bug: 6977981
Change-Id: I43e1a70d8d0d46e02fc67fe1caaec9a1769124f5
---
 res/layout/dialpad_fragment.xml                    |  18 +-
 res/layout/dialpad_smartdial_item.xml              |  28 +++
 res/values/colors.xml                              |   2 +
 res/values/dimens.xml                              |   5 +
 res/values/styles.xml                              |   6 +
 .../android/dialer/dialpad/DialpadFragment.java    | 103 ++++++++-
 .../android/dialer/dialpad/SmartDialAdapter.java   | 169 ++++++++++++++
 src/com/android/dialer/dialpad/SmartDialEntry.java |  36 +++
 .../dialer/dialpad/SmartDialLoaderTask.java        | 249 +++++++++++++++++++++
 .../dialer/dialpad/SmartDialMatchPosition.java     |  70 ++++++
 .../dialer/dialpad/SmartDialNameMatcher.java       | 217 ++++++++++++++++++
 .../android/dialer/dialpad/SmartDialTextView.java  | 103 +++++++++
 .../android/dialer/SmartDialNameMatcherTest.java   | 124 ++++++++++
 13 files changed, 1124 insertions(+), 6 deletions(-)
 create mode 100644 res/layout/dialpad_smartdial_item.xml
 create mode 100644 src/com/android/dialer/dialpad/SmartDialAdapter.java
 create mode 100644 src/com/android/dialer/dialpad/SmartDialEntry.java
 create mode 100644 src/com/android/dialer/dialpad/SmartDialLoaderTask.java
 create mode 100644 src/com/android/dialer/dialpad/SmartDialMatchPosition.java
 create mode 100644 src/com/android/dialer/dialpad/SmartDialNameMatcher.java
 create mode 100644 src/com/android/dialer/dialpad/SmartDialTextView.java
 create mode 100644 tests/src/com/android/dialer/SmartDialNameMatcherTest.java

diff --git a/res/layout/dialpad_fragment.xml b/res/layout/dialpad_fragment.xml
index 6423638a3..e672551bb 100644
--- a/res/layout/dialpad_fragment.xml
+++ b/res/layout/dialpad_fragment.xml
@@ -56,13 +56,23 @@
             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:columnWidth="0dp"
+        android:numColumns="3"
+        android:stretchMode="columnWidth"
+        android:gravity="center"
+        android:background="@drawable/dialpad_background"/>
+
     <!-- Keypad section -->
     <include layout="@layout/dialpad" />
 
-    <View
-       android:layout_width="match_parent"
-       android:layout_height="@dimen/dialpad_vertical_margin"
-       android:background="#66000000"/>
+    <View style="@style/DialpadHorizontalSeparator"/>
 
     <!-- left and right paddings will be modified by the code. See DialpadFragment. -->
     <FrameLayout
diff --git a/res/layout/dialpad_smartdial_item.xml b/res/layout/dialpad_smartdial_item.xml
new file mode 100644
index 000000000..eed257035
--- /dev/null
+++ b/res/layout/dialpad_smartdial_item.xml
@@ -0,0 +1,28 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- 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.
+-->
+
+<com.android.dialer.dialpad.SmartDialTextView
+    xmlns:android="http://schemas.android.com/apk/res/android"
+    android:id="@+id/contact_name"
+    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"
+    />
diff --git a/res/values/colors.xml b/res/values/colors.xml
index 9f3e3a2b0..2828725ac 100644
--- a/res/values/colors.xml
+++ b/res/values/colors.xml
@@ -18,5 +18,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_highlighted_text_color">#ffffff</color>
 
 </resources>
diff --git a/res/values/dimens.xml b/res/values/dimens.xml
index 2c8d59662..4034f7303 100644
--- a/res/values/dimens.xml
+++ b/res/values/dimens.xml
@@ -50,4 +50,9 @@
 
     <!-- Min with of fake menu buttons, which should be same as ActionBar's one -->
     <dimen name="fake_menu_button_min_width">56dip</dimen>
+
+    <!--  Smart Dial -->
+    <dimen name="smartdial_suggestions_padding">4dp</dimen>
+    <dimen name="smartdial_suggestions_extra_padding">2dp</dimen>
+    <dimen name="smartdial_confidence_hint_text_size">27dp</dimen>
 </resources>
diff --git a/res/values/styles.xml b/res/values/styles.xml
index 6f36bf1d8..4f64cb37a 100644
--- a/res/values/styles.xml
+++ b/res/values/styles.xml
@@ -104,6 +104,12 @@
         <item name="android:soundEffectsEnabled">false</item>
     </style>
 
+    <style name="DialpadHorizontalSeparator">
+        <item name="android:layout_width">match_parent</item>
+        <item name="android:layout_height">@dimen/dialpad_vertical_margin</item>
+        <item name="android:background">#66000000</item>
+    </style>
+
     <style name="DialtactsActionBarStyle" parent="android:Widget.Holo.ActionBar">
         <item name="android:backgroundSplit">@null</item>
         <item name="android:backgroundStacked">@drawable/ab_stacked_opaque_dark_holo</item>
diff --git a/src/com/android/dialer/dialpad/DialpadFragment.java b/src/com/android/dialer/dialpad/DialpadFragment.java
index 2b77b4619..3af7f9bec 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";
 
@@ -246,14 +268,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));
@@ -269,6 +293,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
@@ -334,6 +365,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());
+        }
+
         configureScreenFromIntent(getActivity().getIntent());
 
         return fragmentView;
@@ -1115,6 +1154,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
@@ -1637,4 +1681,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);
+        }
+    }
+}
diff --git a/tests/src/com/android/dialer/SmartDialNameMatcherTest.java b/tests/src/com/android/dialer/SmartDialNameMatcherTest.java
new file mode 100644
index 000000000..babae55fa
--- /dev/null
+++ b/tests/src/com/android/dialer/SmartDialNameMatcherTest.java
@@ -0,0 +1,124 @@
+/*
+ * 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.test.suitebuilder.annotation.SmallTest;
+import android.test.suitebuilder.annotation.Suppress;
+import android.util.Log;
+
+import com.android.dialer.dialpad.SmartDialNameMatcher;
+
+import java.text.Normalizer;
+import java.util.ArrayList;
+
+import junit.framework.TestCase;
+
+@SmallTest
+public class SmartDialNameMatcherTest extends TestCase {
+    private static final String TAG = "SmartDialNameMatcherTest";
+
+    public void testMatches() {
+        // Test to ensure that all alphabetic characters are covered
+        checkMatches("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",
+                "22233344455566677778889999" + "22233344455566677778889999", true, 0, 26 * 2);
+        // Should fail because of a mistyped 2 instead of 9 in the second last character
+        checkMatches("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",
+                "22233344455566677778889999" + "22233344455566677778889929", false, 0, 0);
+
+        // Basic name test
+        checkMatches("joe", "5", true, 0, 1);
+        checkMatches("joe", "56", true, 0, 2);
+        checkMatches("joe", "563", true, 0, 3);
+
+        // Matches only word boundary.
+        checkMatches("joe", "63", false, 0, 0);
+        checkMatches("joe oe", "63", true, 4, 6);
+
+        // Test for a match across word boundaries
+        checkMatches("joe oe", "56363", true, 0, 6);
+    }
+
+    public void testMatches_repeatedLetters() {
+        checkMatches("aaaaaaaaaa", "2222222222", true, 0, 10);
+        // Fails because of one extra 2
+        checkMatches("aaaaaaaaaa", "22222222222", false, 0, 0);
+        checkMatches("zzzzzzzzzz zzzzzzzzzz", "99999999999999999999", true, 0, 21);
+    }
+
+    public void testMatches_repeatedSpaces() {
+        checkMatches("William     J  Smith", "9455426576", true, 0, 17);
+        checkMatches("William     J  Smith", "576", true, 12, 17);
+        // Fails because we start at non-word boundary
+        checkMatches("William     J  Smith", "6576", false, 0, 0);
+    }
+
+    // TODO: Do we want to make these pass anymore?
+    @Suppress
+    public void testMatches_repeatedSeparators() {
+        // Simple match for single token
+        checkMatches("John,,,,,Doe", "5646", true, 0, 4);
+        // Match across tokens
+        checkMatches("John,,,,,Doe", "56463", true, 0, 10);
+        // Match token after chain of separators
+        checkMatches("John,,,,,Doe", "363", true, 9, 12);
+    }
+
+    public void testMatches_umlaut() {
+        checkMatches("ÄÖÜäöü", "268268", true, 0, 6);
+    }
+    // TODO: Great if it was treated as "s" or "ss. Figure out if possible without prefix trie?
+    @Suppress
+    public void testMatches_germanSharpS() {
+        checkMatches("ß", "s", true, 0, 1);
+        checkMatches("ß", "ss", true, 0, 1);
+    }
+
+    // TODO: Add this and make it work
+    @Suppress
+    public void testMatches_greek() {
+        // http://en.wikipedia.org/wiki/Greek_alphabet
+        fail("Greek letters aren't supported yet.");
+    }
+
+    // TODO: Add this and make it work
+    @Suppress
+    public void testMatches_cyrillic() {
+        // http://en.wikipedia.org/wiki/Cyrillic_script
+        fail("Cyrillic letters aren't supported yet.");
+    }
+
+    private void checkMatches(String displayName, String query, boolean expectedMatches,
+            int expectedMatchStart, int expectedMatchEnd) {
+        final SmartDialNameMatcher matcher = new SmartDialNameMatcher(query);
+        final ArrayList<SmartDialMatchPosition> matchPositions =
+                new ArrayList<SmartDialMatchPosition>();
+        displayName = SmartDialNameMatcher.stripDiacritics(displayName);
+        final boolean matches = matcher.matchesCombination(
+                displayName, query, matchPositions);
+        Log.d(TAG, "query=" + query + "  text=" + displayName
+                + "  nfd=" + Normalizer.normalize(displayName, Normalizer.Form.NFD)
+                + "  nfc=" + Normalizer.normalize(displayName, Normalizer.Form.NFC)
+                + "  nfkd=" + Normalizer.normalize(displayName, Normalizer.Form.NFKD)
+                + "  nfkc=" + Normalizer.normalize(displayName, Normalizer.Form.NFKC)
+                + "  matches=" + matches);
+        assertEquals("matches", expectedMatches, matches);
+        if (matches) {
+            assertEquals("start", expectedMatchStart, matchPositions.get(0).start);
+            assertEquals("end", expectedMatchEnd, matchPositions.get(0).end);
+        }
+    }
+}
-- 
cgit v1.2.3