Add SmartDial database for the Dialer app.

- Creates a database helper to create a smartdial database for the Dialer app.
- Queries all rows in the Contact database and copies related columns to
  the smart dial database.
- Create another prefix database to contain all prefixes of a contact.
- During keypad input, the prefix databse is queried to find contact
  suggestions, and suggestions are ranked by the usage data and contact
  status (starred, primary contact, etc.)
- Created unit test for the SmartDial database insertion and prefix
  computing functions.

Change-Id: I4d7c3b3bcc52dd6efa4d6e69d3f1687c3abaeb69

11 files changed, 2092 insertions, 1686 deletions

diff --git a/src/com/android/dialer/database/DialerDatabaseHelper.java b/src/com/android/dialer/database/DialerDatabaseHelper.java
new file mode 100644
index 000000000..fd402c9ec
--- /dev/null
+++ b/src/com/android/dialer/database/DialerDatabaseHelper.java
@@ -0,0 +1,826 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dialer.database;
+
+import android.content.Context;
+import android.content.SharedPreferences;
+import android.database.Cursor;
+import android.database.DatabaseUtils;
+import android.database.sqlite.SQLiteDatabase;
+import android.database.sqlite.SQLiteOpenHelper;
+import android.database.sqlite.SQLiteStatement;
+import android.net.Uri;
+import android.os.AsyncTask;
+import android.provider.BaseColumns;
+import android.provider.ContactsContract;
+import android.provider.ContactsContract.CommonDataKinds.Phone;
+import android.provider.ContactsContract.Contacts;
+import android.provider.ContactsContract.Data;
+import android.provider.ContactsContract.Directory;
+import com.android.contacts.common.test.NeededForTesting;
+import android.util.Log;
+
+import com.android.contacts.common.util.StopWatch;
+import com.android.dialer.dialpad.SmartDialNameMatcher;
+import com.android.dialer.dialpad.SmartDialPrefix;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Objects;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.concurrent.atomic.AtomicBoolean;
+
+/**
+ * Database helper for smart dial. Designed as a singleton to make sure there is
+ * only one access point to the database. Provides methods to maintain, update,
+ * and query the database.
+ */
+public class DialerDatabaseHelper extends SQLiteOpenHelper {
+    private static final String TAG = "DialerDatabaseHelper";
+    private static final boolean DEBUG = false;
+
+    private static DialerDatabaseHelper sSingleton = null;
+
+    private static final Object mLock = new Object();
+    private static final AtomicBoolean sInUpdate = new AtomicBoolean(false);
+    private final Context mContext;
+
+    /**
+     * SmartDial DB version ranges:
+     * <pre>
+     *   0-98   KeyLimePie
+     * </pre>
+     */
+    private static final int DATABASE_VERSION = 1;
+    private static final String SMARTDIAL_DATABASE_NAME = "dialer.db";
+
+    /**
+     * Saves the last update time of smart dial databases to shared preferences.
+     */
+    private static final String DATABASE_LAST_CREATED_SHARED_PREF = "com.android.dialer_smartdial";
+    private static final String LAST_UPDATED_MILLIS = "last_updated_millis";
+
+    private static final int MAX_ENTRIES = 3;
+
+    public interface Tables {
+        /** Saves the necessary smart dial information of all contacts. */
+        static final String SMARTDIAL_TABLE = "smartdial_table";
+        /** Saves all possible prefixes to refer to a contacts.*/
+        static final String PREFIX_TABLE = "prefix_table";
+    }
+
+    public interface SmartDialDbColumns {
+        static final String _ID = "id";
+        static final String NUMBER = "phone_number";
+        static final String CONTACT_ID = "contact_id";
+        static final String LOOKUP_KEY = "lookup_key";
+        static final String DISPLAY_NAME_PRIMARY = "display_name";
+        static final String LAST_TIME_USED = "last_time_used";
+        static final String TIMES_USED = "times_used";
+        static final String STARRED = "starred";
+        static final String IS_SUPER_PRIMARY = "is_super_primary";
+        static final String IN_VISIBLE_GROUP = "in_visible_group";
+        static final String IS_PRIMARY = "is_primary";
+        static final String LAST_SMARTDIAL_UPDATE_TIME = "last_smartdial_update_time";
+    }
+
+    public static interface PrefixColumns extends BaseColumns {
+        static final String PREFIX = "prefix";
+        static final String CONTACT_ID = "contact_id";
+    }
+
+    /** Query options for querying the contact database.*/
+    public static interface PhoneQuery {
+       static final Uri URI = Phone.CONTENT_URI.buildUpon().
+               appendQueryParameter(ContactsContract.DIRECTORY_PARAM_KEY,
+                       String.valueOf(Directory.DEFAULT)).
+               appendQueryParameter(ContactsContract.REMOVE_DUPLICATE_ENTRIES, "true").
+               build();
+
+       static final String[] PROJECTION = new String[] {
+            Phone._ID,                          // 0
+            Phone.TYPE,                         // 1
+            Phone.LABEL,                        // 2
+            Phone.NUMBER,                       // 3
+            Phone.CONTACT_ID,                   // 4
+            Phone.LOOKUP_KEY,                   // 5
+            Phone.DISPLAY_NAME_PRIMARY,         // 6
+            Data.LAST_TIME_USED,                // 7
+            Data.TIMES_USED,                    // 8
+            Contacts.STARRED,                   // 9
+            Data.IS_SUPER_PRIMARY,              // 10
+            Contacts.IN_VISIBLE_GROUP,          // 11
+            Data.IS_PRIMARY,                    // 12
+        };
+
+        static final int PHONE_ID = 0;
+        static final int PHONE_TYPE = 1;
+        static final int PHONE_LABEL = 2;
+        static final int PHONE_NUMBER = 3;
+        static final int PHONE_CONTACT_ID = 4;
+        static final int PHONE_LOOKUP_KEY = 5;
+        static final int PHONE_DISPLAY_NAME = 6;
+        static final int PHONE_LAST_TIME_USED = 7;
+        static final int PHONE_TIMES_USED = 8;
+        static final int PHONE_STARRED = 9;
+        static final int PHONE_IS_SUPER_PRIMARY = 10;
+        static final int PHONE_IN_VISIBLE_GROUP = 11;
+        static final int PHONE_IS_PRIMARY = 12;
+
+        /** Selects only rows that have been updated after a certain time stamp.*/
+        static final String SELECT_UPDATED_CLAUSE =
+                Phone.CONTACT_LAST_UPDATED_TIMESTAMP + " > ?";
+    }
+
+    /** Query options for querying the deleted contact database.*/
+    public static interface DeleteContactQuery {
+       static final Uri URI = ContactsContract.DeletedContacts.CONTENT_URI;
+
+       static final String[] PROJECTION = new String[] {
+            ContactsContract.DeletedContacts.CONTACT_ID,                          // 0
+            ContactsContract.DeletedContacts.CONTACT_DELETED_TIMESTAMP,           // 1
+        };
+
+        static final int DELETED_CONTACT_ID = 0;
+        static final int DELECTED_TIMESTAMP = 1;
+
+        /** Selects only rows that have been deleted after a certain time stamp.*/
+        public static final String SELECT_UPDATED_CLAUSE =
+                ContactsContract.DeletedContacts.CONTACT_DELETED_TIMESTAMP + " > ?";
+    }
+
+    /**
+     * Gets the sorting order for the smartdial table. This computes a SQL "ORDER BY" argument by
+     * composing contact status and recent contact details together.
+     */
+    private static interface SmartDialSortingOrder {
+        /** Current contacts - those contacted within the last 3 days (in milliseconds) */
+        static final long LAST_TIME_USED_CURRENT_MS = 3L * 24 * 60 * 60 * 1000;
+        /** Recent contacts - those contacted within the last 30 days (in milliseconds) */
+        static final long LAST_TIME_USED_RECENT_MS = 30L * 24 * 60 * 60 * 1000;
+
+        /** Time since last contact. */
+        static final String TIME_SINCE_LAST_USED_MS = "( ?1 - " +
+                Tables.SMARTDIAL_TABLE + "." + SmartDialDbColumns.LAST_TIME_USED + ")";
+
+        /** Contacts that have been used in the past 3 days rank higher than contacts that have
+         * been used in the past 30 days, which rank higher than contacts that have not been used
+         * in recent 30 days.
+         */
+        static final String SORT_BY_DATA_USAGE =
+                "(CASE WHEN " + TIME_SINCE_LAST_USED_MS + " < " + LAST_TIME_USED_CURRENT_MS +
+                " THEN 0 " +
+                " WHEN " + TIME_SINCE_LAST_USED_MS + " < " + LAST_TIME_USED_RECENT_MS +
+                " THEN 1 " +
+                " ELSE 2 END)";
+
+        /** This sort order is similar to that used by the ContactsProvider when returning a list
+         * of frequently called contacts.
+         */
+        static final String SORT_ORDER =
+                Tables.SMARTDIAL_TABLE + "." + SmartDialDbColumns.STARRED + " DESC, "
+                + Tables.SMARTDIAL_TABLE + "." + SmartDialDbColumns.IS_SUPER_PRIMARY + " DESC, "
+                + SORT_BY_DATA_USAGE + ", "
+                + Tables.SMARTDIAL_TABLE + "." + SmartDialDbColumns.TIMES_USED + " DESC, "
+                + Tables.SMARTDIAL_TABLE + "." + SmartDialDbColumns.IN_VISIBLE_GROUP + " DESC, "
+                + Tables.SMARTDIAL_TABLE + "." + SmartDialDbColumns.DISPLAY_NAME_PRIMARY + ", "
+                + Tables.SMARTDIAL_TABLE + "." + SmartDialDbColumns.CONTACT_ID + ", "
+                + Tables.SMARTDIAL_TABLE + "." + SmartDialDbColumns.IS_PRIMARY + " DESC";
+    }
+
+    /**
+     * Simple data format for a contact, containing only information needed for showing up in
+     * smart dial interface.
+     */
+    public static class ContactNumber {
+        public final String displayName;
+        public final String lookupKey;
+        public final long id;
+        public final String phoneNumber;
+
+        public ContactNumber(long id, String displayName, String phoneNumber, String lookupKey) {
+            this.displayName = displayName;
+            this.lookupKey = lookupKey;
+            this.id = id;
+            this.phoneNumber = phoneNumber;
+        }
+
+        @Override
+        public int hashCode() {
+            return Objects.hashCode(displayName, id, lookupKey, phoneNumber);
+        }
+
+        @Override
+        public boolean equals(Object object) {
+            if (this == object) {
+                return true;
+            }
+            if (object instanceof ContactNumber) {
+                final ContactNumber that = (ContactNumber) object;
+                return Objects.equal(this.displayName, that.displayName)
+                        && Objects.equal(this.id, that.id)
+                        && Objects.equal(this.lookupKey, that.lookupKey)
+                        && Objects.equal(this.phoneNumber, that.phoneNumber);
+            }
+            return false;
+        }
+    }
+
+    /**
+     * Data format for finding duplicated contacts.
+     */
+    private class ContactMatch {
+        private final String lookupKey;
+        private final long id;
+
+        public ContactMatch(String lookupKey, long id) {
+            this.lookupKey = lookupKey;
+            this.id = id;
+        }
+
+        @Override
+        public int hashCode() {
+            return Objects.hashCode(lookupKey, id);
+        }
+
+        @Override
+        public boolean equals(Object object) {
+            if (this == object) {
+                return true;
+            }
+            if (object instanceof ContactMatch) {
+                final ContactMatch that = (ContactMatch) object;
+                return Objects.equal(this.lookupKey, that.lookupKey)
+                        && Objects.equal(this.id, that.id);
+            }
+            return false;
+        }
+    }
+
+    /**
+     * Access function to get the singleton instance of DialerDatabaseHelper.
+     */
+    public static synchronized DialerDatabaseHelper getInstance(Context context) {
+        if (DEBUG) {
+            Log.v(TAG, "Getting Instance");
+        }
+        if (sSingleton == null) {
+            sSingleton = new DialerDatabaseHelper(context, SMARTDIAL_DATABASE_NAME);
+        }
+        return sSingleton;
+    }
+
+    /**
+     * Returns a new instance for unit tests. The database will be created in memory.
+     */
+    @NeededForTesting
+    static DialerDatabaseHelper getNewInstanceForTest(Context context) {
+        return new DialerDatabaseHelper(context, null);
+    }
+
+    protected DialerDatabaseHelper(Context context, String databaseName) {
+        super(context, databaseName, null, DATABASE_VERSION);
+        mContext = Preconditions.checkNotNull(context, "Context must not be null");
+    }
+
+    /**
+     * Creates tables in the database when database is created for the first time.
+     *
+     * @param db The database.
+     */
+    @Override
+    public void onCreate(SQLiteDatabase db) {
+        db.execSQL("CREATE TABLE " + Tables.SMARTDIAL_TABLE + " (" +
+                SmartDialDbColumns._ID + " INTEGER PRIMARY KEY AUTOINCREMENT," +
+                SmartDialDbColumns.NUMBER + " TEXT," +
+                SmartDialDbColumns.CONTACT_ID + " INTEGER," +
+                SmartDialDbColumns.LOOKUP_KEY + " TEXT," +
+                SmartDialDbColumns.DISPLAY_NAME_PRIMARY + " TEXT, " +
+                SmartDialDbColumns.LAST_SMARTDIAL_UPDATE_TIME + " LONG, " +
+                SmartDialDbColumns.LAST_TIME_USED + " LONG, " +
+                SmartDialDbColumns.TIMES_USED + " INTEGER, " +
+                SmartDialDbColumns.STARRED + " INTEGER, " +
+                SmartDialDbColumns.IS_SUPER_PRIMARY + " INTEGER, " +
+                SmartDialDbColumns.IN_VISIBLE_GROUP + " INTEGER, " +
+                SmartDialDbColumns.IS_PRIMARY + " INTEGER" +
+        ");");
+
+        db.execSQL("CREATE TABLE " + Tables.PREFIX_TABLE + " (" +
+                PrefixColumns._ID + " INTEGER PRIMARY KEY AUTOINCREMENT," +
+                PrefixColumns.PREFIX + " TEXT COLLATE NOCASE, " +
+                PrefixColumns.CONTACT_ID + " INTEGER" +
+                ");");
+    }
+
+    /**
+     * Starts the database upgrade process in the background.
+     */
+    public void startSmartDialUpdateThread() {
+       new SmartDialUpdateAsyncTask().execute();
+    }
+
+    private class SmartDialUpdateAsyncTask extends AsyncTask {
+        @Override
+        protected Object doInBackground(Object[] objects) {
+            if (DEBUG) {
+                Log.v(TAG, "Updating database");
+            }
+            updateSmartDialDatabase();
+            return null;
+        }
+
+        @Override
+        protected void onCancelled() {
+            if (DEBUG) {
+                Log.v(TAG, "Updating Cancelled");
+            }
+            super.onCancelled();
+        }
+
+        @Override
+        protected void onPostExecute(Object o) {
+            if (DEBUG) {
+                Log.v(TAG, "Updating Finished");
+            }
+            super.onPostExecute(o);
+        }
+    }
+    /**
+     * Removes rows in the smartdial database that matches the contacts that have been deleted
+     * by other apps since last update.
+     *
+     * @param db Database pointer to the dialer database.
+     * @param last_update_time Time stamp of last update on the smartdial database
+     */
+    private void removeDeletedContacts(SQLiteDatabase db, String last_update_time) {
+        final Cursor deletedContactCursor = mContext.getContentResolver().query(
+                DeleteContactQuery.URI,
+                DeleteContactQuery.PROJECTION,
+                DeleteContactQuery.SELECT_UPDATED_CLAUSE,
+                new String[] {last_update_time}, null);
+
+        db.beginTransaction();
+        try {
+            while (deletedContactCursor.moveToNext()) {
+                final Long deleteContactId =
+                        deletedContactCursor.getLong(DeleteContactQuery.DELETED_CONTACT_ID);
+                db.delete(Tables.SMARTDIAL_TABLE,
+                        SmartDialDbColumns.CONTACT_ID + "=" + deleteContactId, null);
+                db.delete(Tables.PREFIX_TABLE,
+                        PrefixColumns.CONTACT_ID + "=" + deleteContactId, null);
+            }
+
+            db.setTransactionSuccessful();
+        } finally {
+            deletedContactCursor.close();
+            db.endTransaction();
+        }
+    }
+
+    /**
+     * Removes potentially corrupted entries in the database. These contacts may be added before
+     * the previous instance of the dialer was destroyed for some reason. For data integrity, we
+     * delete all of them.
+
+     * @param db Database pointer to the dialer database.
+     * @param last_update_time Time stamp of last successful update of the dialer database.
+     */
+    private void removePotentiallyCorruptedContacts(SQLiteDatabase db, String last_update_time) {
+        db.delete(Tables.PREFIX_TABLE,
+                PrefixColumns.CONTACT_ID + " IN " +
+                "(SELECT " + SmartDialDbColumns.CONTACT_ID + " FROM " + Tables.SMARTDIAL_TABLE +
+                " WHERE " + SmartDialDbColumns.LAST_SMARTDIAL_UPDATE_TIME + " > " +
+                last_update_time + ")",
+                null);
+        db.delete(Tables.SMARTDIAL_TABLE,
+                SmartDialDbColumns.LAST_SMARTDIAL_UPDATE_TIME + " > " + last_update_time, null);
+    }
+
+    /**
+     * Removes all entries in the smartdial contact database.
+     */
+    @VisibleForTesting
+    void removeAllContacts(SQLiteDatabase db) {
+        db.delete(Tables.SMARTDIAL_TABLE, null, null);
+        db.delete(Tables.PREFIX_TABLE, null, null);
+    }
+
+    /**
+     * Counts number of rows of the prefix table.
+     */
+    @VisibleForTesting
+    int countPrefixTableRows(SQLiteDatabase db) {
+        return (int)DatabaseUtils.longForQuery(db, "SELECT COUNT(1) FROM " + Tables.PREFIX_TABLE,
+                null);
+    }
+
+    /**
+     * Removes rows in the smartdial database that matches updated contacts.
+     *
+     * @param db Database pointer to the smartdial database
+     * @param updatedContactCursor Cursor pointing to the list of recently updated contacts.
+     */
+    private void removeUpdatedContacts(SQLiteDatabase db, Cursor updatedContactCursor) {
+        db.beginTransaction();
+        try {
+            while (updatedContactCursor.moveToNext()) {
+                final Long contactId = updatedContactCursor.getLong(PhoneQuery.PHONE_CONTACT_ID);
+
+                db.delete(Tables.SMARTDIAL_TABLE, SmartDialDbColumns.CONTACT_ID + "=" +
+                        contactId, null);
+                db.delete(Tables.PREFIX_TABLE, PrefixColumns.CONTACT_ID + "=" +
+                        contactId, null);
+            }
+
+            db.setTransactionSuccessful();
+        } finally {
+            db.endTransaction();
+        }
+    }
+
+    /**
+     * Inserts updated contacts as rows to the smartdial table.
+     *
+     * @param db Database pointer to the smartdial database.
+     * @param updatedContactCursor Cursor pointing to the list of recently updated contacts.
+     * @param currentMillis Current time to be recorded in the smartdial table as update timestamp.
+     */
+    @VisibleForTesting
+    protected void insertUpdatedContactsAndNumberPrefix(SQLiteDatabase db,
+            Cursor updatedContactCursor, Long currentMillis) {
+        db.beginTransaction();
+        try {
+            final String sqlInsert = "INSERT INTO " + Tables.SMARTDIAL_TABLE + " (" +
+                    SmartDialDbColumns.NUMBER + ", " +
+                    SmartDialDbColumns.CONTACT_ID + ", " +
+                    SmartDialDbColumns.LOOKUP_KEY + ", " +
+                    SmartDialDbColumns.DISPLAY_NAME_PRIMARY + ", " +
+                    SmartDialDbColumns.LAST_TIME_USED + ", " +
+                    SmartDialDbColumns.TIMES_USED + ", " +
+                    SmartDialDbColumns.STARRED + ", " +
+                    SmartDialDbColumns.IS_SUPER_PRIMARY + ", " +
+                    SmartDialDbColumns.IN_VISIBLE_GROUP+ ", " +
+                    SmartDialDbColumns.IS_PRIMARY + ", " +
+                    SmartDialDbColumns.LAST_SMARTDIAL_UPDATE_TIME + ") " +
+                    " VALUES (?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?)";
+            final SQLiteStatement insert = db.compileStatement(sqlInsert);
+
+            final String numberSqlInsert = "INSERT INTO " + Tables.PREFIX_TABLE + " (" +
+                    PrefixColumns.CONTACT_ID + ", " +
+                    PrefixColumns.PREFIX  + ") " +
+                    " VALUES (?, ?)";
+            final SQLiteStatement numberInsert = db.compileStatement(numberSqlInsert);
+
+            updatedContactCursor.moveToPosition(-1);
+            while (updatedContactCursor.moveToNext()) {
+                insert.bindString(1, updatedContactCursor.getString(PhoneQuery.PHONE_NUMBER));
+                insert.bindLong(2, updatedContactCursor.getLong(PhoneQuery.PHONE_CONTACT_ID));
+                insert.bindString(3, updatedContactCursor.getString(PhoneQuery.PHONE_LOOKUP_KEY));
+                insert.bindString(4, updatedContactCursor.getString(PhoneQuery.PHONE_DISPLAY_NAME));
+                insert.bindLong(5, updatedContactCursor.getLong(PhoneQuery.PHONE_LAST_TIME_USED));
+                insert.bindLong(6, updatedContactCursor.getInt(PhoneQuery.PHONE_TIMES_USED));
+                insert.bindLong(7, updatedContactCursor.getInt(PhoneQuery.PHONE_STARRED));
+                insert.bindLong(8, updatedContactCursor.getInt(PhoneQuery.PHONE_IS_SUPER_PRIMARY));
+                insert.bindLong(9, updatedContactCursor.getInt(PhoneQuery.PHONE_IN_VISIBLE_GROUP));
+                insert.bindLong(10, updatedContactCursor.getInt(PhoneQuery.PHONE_IS_PRIMARY));
+                insert.bindLong(11, currentMillis);
+                insert.executeInsert();
+                insert.clearBindings();
+
+                final String contactPhoneNumber =
+                        updatedContactCursor.getString(PhoneQuery.PHONE_NUMBER);
+                final ArrayList<String> numberPrefixes =
+                        SmartDialPrefix.parseToNumberTokens(contactPhoneNumber);
+
+                for (String numberPrefix : numberPrefixes) {
+                    numberInsert.bindLong(1, updatedContactCursor.getLong(
+                            PhoneQuery.PHONE_CONTACT_ID));
+                    numberInsert.bindString(2, numberPrefix);
+                    numberInsert.executeInsert();
+                    numberInsert.clearBindings();
+                }
+            }
+
+            db.setTransactionSuccessful();
+        } finally {
+            db.endTransaction();
+        }
+    }
+
+    /**
+     * Inserts prefixes of contact names to the prefix table.
+     *
+     * @param db Database pointer to the smartdial database.
+     * @param nameCursor Cursor pointing to the list of distinct updated contacts.
+     */
+    @VisibleForTesting
+    void insertNamePrefixes(SQLiteDatabase db, Cursor nameCursor) {
+        final int columnIndexName = nameCursor.getColumnIndex(
+                SmartDialDbColumns.DISPLAY_NAME_PRIMARY);
+        final int columnIndexContactId = nameCursor.getColumnIndex(SmartDialDbColumns.CONTACT_ID);
+
+        db.beginTransaction();
+        try {
+            final String sqlInsert = "INSERT INTO " + Tables.PREFIX_TABLE + " (" +
+                    PrefixColumns.CONTACT_ID + ", " +
+                    PrefixColumns.PREFIX  + ") " +
+                    " VALUES (?, ?)";
+            final SQLiteStatement insert = db.compileStatement(sqlInsert);
+
+            while (nameCursor.moveToNext()) {
+                /** Computes a list of prefixes of a given contact name. */
+                final ArrayList<String> namePrefixes =
+                        SmartDialPrefix.generateNamePrefixes(nameCursor.getString(columnIndexName));
+
+                for (String namePrefix : namePrefixes) {
+                    insert.bindLong(1, nameCursor.getLong(columnIndexContactId));
+                    insert.bindString(2, namePrefix);
+                    insert.executeInsert();
+                    insert.clearBindings();
+                }
+            }
+
+            db.setTransactionSuccessful();
+        } finally {
+            db.endTransaction();
+        }
+    }
+
+    /**
+     * Updates the smart dial and prefix database.
+     * This method queries the Delta API to get changed contacts since last update, and updates the
+     * records in smartdial database and prefix database accordingly.
+     * It also queries the deleted contact database to remove newly deleted contacts since last
+     * update.
+     */
+    public void updateSmartDialDatabase() {
+        final SQLiteDatabase db = getWritableDatabase();
+
+        synchronized(mLock) {
+            if (DEBUG) {
+                Log.v(TAG, "Starting to update database");
+            }
+            final StopWatch stopWatch = DEBUG ? StopWatch.start("Updating databases") : null;
+
+            /** Gets the last update time on the database. */
+            final SharedPreferences databaseLastUpdateSharedPref = mContext.getSharedPreferences(
+                    DATABASE_LAST_CREATED_SHARED_PREF, Context.MODE_PRIVATE);
+            final String lastUpdateMillis = String.valueOf(
+                    databaseLastUpdateSharedPref.getLong(LAST_UPDATED_MILLIS, 0));
+
+            if (DEBUG) {
+                Log.v(TAG, "Last updated at " + lastUpdateMillis);
+            }
+            /** Queries the contact database to get contacts that have been updated since the last
+             * update time.
+             */
+            final Cursor updatedContactCursor = mContext.getContentResolver().query(PhoneQuery.URI,
+                    PhoneQuery.PROJECTION, PhoneQuery.SELECT_UPDATED_CLAUSE,
+                    new String[]{lastUpdateMillis}, null);
+
+            /** Sets the time after querying the database as the current update time. */
+            final Long currentMillis = System.currentTimeMillis();
+
+            if (DEBUG) {
+                stopWatch.lap("Queried the Contacts database");
+            }
+
+            if (updatedContactCursor == null) {
+                if (DEBUG) {
+                    Log.e(TAG, "SmartDial query received null for cursor");
+                }
+                return;
+            }
+
+            /** Prevents the app from reading the dialer database when updating. */
+            sInUpdate.getAndSet(true);
+
+            /** Removes contacts that have been deleted. */
+            removeDeletedContacts(db, lastUpdateMillis);
+            removePotentiallyCorruptedContacts(db, lastUpdateMillis);
+
+            if (DEBUG) {
+                stopWatch.lap("Finished deleting deleted entries");
+            }
+
+            try {
+                /** If the database did not exist before, jump through deletion as there is nothing
+                 * to delete.
+                 */
+                if (!lastUpdateMillis.equals("0")) {
+                    /** Removes contacts that have been updated. Updated contact information will be
+                     * inserted later.
+                     */
+                    removeUpdatedContacts(db, updatedContactCursor);
+                    if (DEBUG) {
+                        stopWatch.lap("Finished deleting updated entries");
+                    }
+                }
+
+                /** Inserts recently updated contacts to the smartdial database.*/
+                insertUpdatedContactsAndNumberPrefix(db, updatedContactCursor, currentMillis);
+                if (DEBUG) {
+                    stopWatch.lap("Finished building the smart dial table");
+                }
+            } finally {
+                /** Inserts prefixes of phone numbers into the prefix table.*/
+                updatedContactCursor.close();
+            }
+
+            /** Gets a list of distinct contacts which have been updated, and adds the name prefixes
+             * of these contacts to the prefix table.
+             */
+            final Cursor nameCursor = db.rawQuery(
+                    "SELECT DISTINCT " +
+                    SmartDialDbColumns.DISPLAY_NAME_PRIMARY + ", " + SmartDialDbColumns.CONTACT_ID +
+                    " FROM " + Tables.SMARTDIAL_TABLE +
+                    " WHERE " + SmartDialDbColumns.LAST_SMARTDIAL_UPDATE_TIME +
+                    " = " + Long.toString(currentMillis),
+                    new String[] {});
+            if (DEBUG) {
+                stopWatch.lap("Queried the smart dial table for contact names");
+            }
+
+            if (nameCursor != null) {
+                try {
+                    /** Inserts prefixes of names into the prefix table.*/
+                    insertNamePrefixes(db, nameCursor);
+                    if (DEBUG) {
+                        stopWatch.lap("Finished building the name prefix table");
+                    }
+                } finally {
+                    nameCursor.close();
+                }
+            }
+
+            /** Creates index on contact_id for fast JOIN operation. */
+            db.execSQL("CREATE INDEX IF NOT EXISTS smartdial_contact_id_index ON " +
+                    Tables.SMARTDIAL_TABLE + " (" + SmartDialDbColumns.CONTACT_ID  + ");");
+            /** Creates index on last_smartdial_update_time for fast SELECT operation. */
+            db.execSQL("CREATE INDEX IF NOT EXISTS smartdial_last_update_index ON " +
+                    Tables.SMARTDIAL_TABLE + " (" +
+                    SmartDialDbColumns.LAST_SMARTDIAL_UPDATE_TIME + ");");
+            /** Creates index on sorting fields for fast sort operation. */
+            db.execSQL("CREATE INDEX IF NOT EXISTS smartdial_sort_index ON " +
+                    Tables.SMARTDIAL_TABLE + " (" +
+                    SmartDialDbColumns.STARRED + ", " +
+                    SmartDialDbColumns.IS_SUPER_PRIMARY + ", " +
+                    SmartDialDbColumns.LAST_TIME_USED + ", " +
+                    SmartDialDbColumns.TIMES_USED + ", " +
+                    SmartDialDbColumns.IN_VISIBLE_GROUP +  ", " +
+                    SmartDialDbColumns.DISPLAY_NAME_PRIMARY + ", " +
+                    SmartDialDbColumns.CONTACT_ID + ", " +
+                    SmartDialDbColumns.IS_PRIMARY +
+                    ");");
+            /** Creates index on prefix for fast SELECT operation. */
+            db.execSQL("CREATE INDEX IF NOT EXISTS nameprefix_index ON " +
+                    Tables.PREFIX_TABLE + " (" + PrefixColumns.PREFIX + ");");
+            /** Creates index on contact_id for fast JOIN operation. */
+            db.execSQL("CREATE INDEX IF NOT EXISTS nameprefix_contact_id_index ON " +
+                    Tables.PREFIX_TABLE + " (" + PrefixColumns.CONTACT_ID + ");");
+
+            if (DEBUG) {
+                stopWatch.lap(TAG + "Finished recreating index");
+            }
+
+            /** Updates the database index statistics.*/
+            db.execSQL("ANALYZE " + Tables.SMARTDIAL_TABLE);
+            db.execSQL("ANALYZE " + Tables.PREFIX_TABLE);
+            db.execSQL("ANALYZE smartdial_contact_id_index");
+            db.execSQL("ANALYZE smartdial_last_update_index");
+            db.execSQL("ANALYZE nameprefix_index");
+            db.execSQL("ANALYZE nameprefix_contact_id_index");
+            if (DEBUG) {
+                stopWatch.stopAndLog(TAG + "Finished updating index stats", 0);
+            }
+
+            sInUpdate.getAndSet(false);
+
+            final SharedPreferences.Editor editor = databaseLastUpdateSharedPref.edit();
+            editor.putLong(LAST_UPDATED_MILLIS, currentMillis);
+            editor.commit();
+        }
+    }
+
+
+    /**
+     * Returns a list of candidate contacts where the query is a prefix of the dialpad index of
+     * the contact's name or phone number.
+     *
+     * @param query The prefix of a contact's dialpad index.
+     * @return A list of top candidate contacts that will be suggested to user to match their input.
+     */
+    public ArrayList<ContactNumber>  getLooseMatches(String query,
+            SmartDialNameMatcher nameMatcher) {
+        final boolean inUpdate = sInUpdate.get();
+        if (inUpdate) {
+            return Lists.newArrayList();
+        }
+
+        final SQLiteDatabase db = getReadableDatabase();
+
+        /** Uses SQL query wildcard '%' to represent prefix matching.*/
+        final String looseQuery = query + "%";
+
+        final ArrayList<ContactNumber> result = Lists.newArrayList();
+
+        final StopWatch stopWatch = DEBUG ? StopWatch.start(":Name Prefix query") : null;
+
+        final String currentTimeStamp = Long.toString(System.currentTimeMillis());
+
+        /** Queries the database to find contacts that have an index matching the query prefix. */
+        final Cursor cursor = db.rawQuery("SELECT " +
+                SmartDialDbColumns.DISPLAY_NAME_PRIMARY + ", " +
+                SmartDialDbColumns.NUMBER + ", " +
+                SmartDialDbColumns.CONTACT_ID + ", " +
+                SmartDialDbColumns.LOOKUP_KEY +
+                " FROM " + Tables.SMARTDIAL_TABLE + " WHERE " +
+                SmartDialDbColumns.CONTACT_ID + " IN " +
+                    " (SELECT " + PrefixColumns.CONTACT_ID +
+                    " FROM " + Tables.PREFIX_TABLE +
+                    " WHERE " + Tables.PREFIX_TABLE + "." + PrefixColumns.PREFIX +
+                    " LIKE '" + looseQuery + "')" +
+                " ORDER BY " + SmartDialSortingOrder.SORT_ORDER,
+                new String[] {currentTimeStamp});
+
+        if (DEBUG) {
+            stopWatch.lap("Prefix query completed");
+        }
+
+        /** Gets the column ID from the cursor.*/
+        final int columnDisplayNamePrimary = 0;
+        final int columnNumber = 1;
+        final int columnId = 2;
+        final int columnLookupKey = 3;
+        if (DEBUG) {
+            stopWatch.lap("Found column IDs");
+        }
+
+        final Set<ContactMatch> duplicates = new HashSet<ContactMatch>();
+        int counter = 0;
+        try {
+            if (DEBUG) {
+                stopWatch.lap("Moved cursor to start");
+            }
+            /** Iterates the cursor to find top contact suggestions without duplication.*/
+            while ((cursor.moveToNext()) && (counter < MAX_ENTRIES)) {
+                final String displayName = cursor.getString(columnDisplayNamePrimary);
+                final String phoneNumber = cursor.getString(columnNumber);
+                final long id = cursor.getLong(columnId);
+                final String lookupKey = cursor.getString(columnLookupKey);
+
+                /** If a contact already exists and another phone number of the contact is being
+                 * processed, skip the second instance.
+                 */
+                final ContactMatch contactMatch = new ContactMatch(lookupKey, id);
+                if (duplicates.contains(contactMatch)) {
+                    continue;
+                }
+
+                /**
+                 * If the contact has either the name or number that matches the query, add to the
+                 * result.
+                 */
+                if (nameMatcher.matches(displayName) ||
+                        nameMatcher.matchesNumber(phoneNumber, query) != null) {
+                    /** If a contact has not been added, add it to the result and the hash set.*/
+                    duplicates.add(contactMatch);
+                    result.add(new ContactNumber(id, displayName, phoneNumber, lookupKey));
+                    counter++;
+                    if (DEBUG) {
+                        stopWatch.lap("Added one result");
+                    }
+                }
+            }
+
+            if (DEBUG) {
+                stopWatch.stopAndLog(TAG + "Finished loading cursor", 0);
+            }
+        } finally {
+            cursor.close();
+        }
+        return result;
+    }
+
+    @Override
+    public void onUpgrade(SQLiteDatabase db, int oldVersion, int newVersion) {
+
+    }
+}
diff --git a/src/com/android/dialer/dialpad/DialpadFragment.java b/src/com/android/dialer/dialpad/DialpadFragment.java
index a8984bd26..f783d2705 100644
--- a/src/com/android/dialer/dialpad/DialpadFragment.java
+++ b/src/com/android/dialer/dialpad/DialpadFragment.java
@@ -26,7 +26,6 @@ import android.content.Context;
 import android.content.DialogInterface;
 import android.content.Intent;
 import android.content.res.Resources;
-import android.database.ContentObserver;
 import android.database.Cursor;
 import android.graphics.Bitmap;
 import android.graphics.BitmapFactory;
@@ -35,7 +34,6 @@ import android.media.ToneGenerator;
 import android.net.Uri;
 import android.os.AsyncTask;
 import android.os.Bundle;
-import android.os.Handler;
 import android.os.RemoteException;
 import android.os.ServiceManager;
 import android.os.SystemProperties;
@@ -62,12 +60,10 @@ import android.view.MenuItem;
 import android.view.View;
 import android.view.ViewConfiguration;
 import android.view.ViewGroup;
-import android.widget.AbsListView;
 import android.widget.AdapterView;
 import android.widget.BaseAdapter;
 import android.widget.EditText;
 import android.widget.ImageView;
-import android.widget.LinearLayout;
 import android.widget.ListView;
 import android.widget.PopupMenu;
 import android.widget.RelativeLayout;
@@ -82,6 +78,7 @@ import com.android.contacts.common.util.StopWatch;
 import com.android.dialer.DialtactsActivity;
 import com.android.dialer.R;
 import com.android.dialer.SpecialCharSequenceMgr;
+import com.android.dialer.database.DialerDatabaseHelper;
 import com.android.dialer.interactions.PhoneNumberInteraction;
 import com.android.dialer.util.OrientationUtil;
 import com.android.internal.telephony.ITelephony;
@@ -156,8 +153,6 @@ public class DialpadFragment extends Fragment
      */
     private SmartDialController mSmartDialAdapter;
 
-    private SmartDialCache mSmartDialCache;
-
     /**
      * Use latin character map by default
      */
@@ -169,6 +164,8 @@ public class DialpadFragment extends Fragment
      */
     private boolean mSmartDialEnabled = false;
 
+    private DialerDatabaseHelper mDialerDatabaseHelper;
+
     /**
      * Regular expression prohibiting manual phone call. Can be empty, which means "no rule".
      */
@@ -300,6 +297,10 @@ public class DialpadFragment extends Fragment
         mFirstLaunch = true;
         mContactsPrefs = new ContactsPreferences(getActivity());
         mCurrentCountryIso = GeoUtil.getCurrentCountryIso(getActivity());
+
+        mDialerDatabaseHelper = DialerDatabaseHelper.getInstance(getActivity());
+        SmartDialPrefix.initializeNanpSettings(getActivity());
+
         try {
             mHaptic.init(getActivity(),
                          getResources().getBoolean(R.bool.config_enable_dialer_key_vibration));
@@ -1653,20 +1654,6 @@ public class DialpadFragment extends Fragment
         return intent;
     }
 
-    @Override
-    public void setUserVisibleHint(boolean isVisibleToUser) {
-        super.setUserVisibleHint(isVisibleToUser);
-        if (mSmartDialEnabled && isVisibleToUser && mSmartDialCache != null) {
-            // This is called every time the dialpad fragment comes into view. The first
-            // time the dialer is launched, mSmartDialEnabled is always false as it has not been
-            // read from settings(in onResume) yet at the point where setUserVisibleHint is called
-            // for the first time, so the caching on first launch will happen in onResume instead.
-            // This covers only the case where the dialer is launched in the call log or
-            // contacts tab, and then the user swipes to the dialpad.
-            mSmartDialCache.cacheIfNeeded(false);
-        }
-    }
-
     private String mLastDigitsForSmartDial;
 
     private void loadSmartDialEntries() {
@@ -1675,11 +1662,6 @@ public class DialpadFragment extends Fragment
             return;
         }
 
-        if (mSmartDialCache == null) {
-            Log.e(TAG, "Trying to load smart dialing entries from a null cache");
-            return;
-        }
-
         // Update only when the digits have changed.
         final String digits = SmartDialNameMatcher.normalizeNumber(mDigits.getText().toString(),
                 mSmartDialMap);
@@ -1691,7 +1673,7 @@ public class DialpadFragment extends Fragment
         if (digits.length() < 1) {
             mSmartDialAdapter.clear();
         } else {
-            final SmartDialLoaderTask task = new SmartDialLoaderTask(this, digits, mSmartDialCache);
+            final SmartDialLoaderTask task = new SmartDialLoaderTask(this, digits, getActivity());
             task.executeOnExecutor(AsyncTask.THREAD_POOL_EXECUTOR, new String[] {});
         }
     }
@@ -1708,24 +1690,15 @@ public class DialpadFragment extends Fragment
         // Handle smart dialing related state
         if (mSmartDialEnabled) {
             mSmartDialContainer.setVisibility(View.VISIBLE);
-            mSmartDialCache = SmartDialCache.getInstance(getActivity(),
-                    mContactsPrefs.getDisplayOrder(), mSmartDialMap);
-            // Don't force recache if this is the first time onResume is being called, since
-            // caching should already happen in setUserVisibleHint.
-            if (!mFirstLaunch || getUserVisibleHint()) {
-                // This forced recache covers the cases where the dialer was running before and
-                // was brought back into the foreground, or the dialer was launched for the first
-                // time and displays the dialpad fragment immediately. If the dialpad fragment
-                // hasn't actually become visible throughout the entire activity's lifecycle, it
-                // is possible that caching hasn't happened yet. In this case, we can force a
-                // recache anyway, since we are not worried about startup performance anymore.
-                mSmartDialCache.cacheIfNeeded(true);
+
+            if (DEBUG) {
+                Log.w(TAG, "Creating smart dial database");
             }
+            mDialerDatabaseHelper.startSmartDialUpdateThread();
         } else {
             if (mSmartDialContainer != null) {
                 mSmartDialContainer.setVisibility(View.GONE);
             }
-            mSmartDialCache = null;
         }
     }
 
diff --git a/src/com/android/dialer/dialpad/SmartDialCache.java b/src/com/android/dialer/dialpad/SmartDialCache.java
deleted file mode 100644
index 3d4a563af..000000000
--- a/src/com/android/dialer/dialpad/SmartDialCache.java
+++ /dev/null
@@ -1,408 +0,0 @@
-/*
- * Copyright (C) 2012 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.dialer.dialpad;
-
-import static com.android.dialer.dialpad.SmartDialController.LOG_TAG;
-
-import android.content.Context;
-import android.content.SharedPreferences;
-import android.database.Cursor;
-import android.net.Uri;
-import android.preference.PreferenceManager;
-import android.provider.ContactsContract;
-import android.provider.ContactsContract.CommonDataKinds.Phone;
-import android.provider.ContactsContract.Contacts;
-import android.provider.ContactsContract.Data;
-import android.provider.ContactsContract.Directory;
-import android.telephony.TelephonyManager;
-import android.text.TextUtils;
-import android.util.Log;
-
-import com.android.contacts.common.util.StopWatch;
-
-import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Preconditions;
-
-import java.util.Comparator;
-import java.util.HashSet;
-import java.util.Set;
-import java.util.concurrent.atomic.AtomicInteger;
-
-/**
- * Cache object used to cache Smart Dial contacts that handles various states of the cache at the
- * point in time when getContacts() is called
- * 1) Cache is currently empty and there is no caching thread running - getContacts() starts a
- * caching thread and returns the cache when completed
- * 2) The cache is currently empty, but a caching thread has been started - getContacts() waits
- * till the existing caching thread is completed before immediately returning the cache
- * 3) The cache has already been populated, and there is no caching thread running - getContacts()
- * returns the existing cache immediately
- * 4) The cache has already been populated, but there is another caching thread running (due to
- * a forced cache refresh due to content updates - getContacts() returns the existing cache
- * immediately
- */
-public class SmartDialCache {
-
-    public static class ContactNumber {
-        public final String displayName;
-        public final String lookupKey;
-        public final long id;
-        public final int affinity;
-        public final String phoneNumber;
-
-        public ContactNumber(long id, String displayName, String phoneNumber, String lookupKey,
-                int affinity) {
-            this.displayName = displayName;
-            this.lookupKey = lookupKey;
-            this.id = id;
-            this.affinity = affinity;
-            this.phoneNumber = phoneNumber;
-        }
-    }
-
-    public static interface PhoneQuery {
-
-       Uri URI = Phone.CONTENT_URI.buildUpon().
-               appendQueryParameter(ContactsContract.DIRECTORY_PARAM_KEY,
-               String.valueOf(Directory.DEFAULT)).
-               appendQueryParameter(ContactsContract.REMOVE_DUPLICATE_ENTRIES, "true").
-               build();
-
-       final String[] PROJECTION_PRIMARY = new String[] {
-            Phone._ID,                          // 0
-            Phone.TYPE,                         // 1
-            Phone.LABEL,                        // 2
-            Phone.NUMBER,                       // 3
-            Phone.CONTACT_ID,                   // 4
-            Phone.LOOKUP_KEY,                   // 5
-            Phone.DISPLAY_NAME_PRIMARY,         // 6
-        };
-
-        final String[] PROJECTION_ALTERNATIVE = new String[] {
-            Phone._ID,                          // 0
-            Phone.TYPE,                         // 1
-            Phone.LABEL,                        // 2
-            Phone.NUMBER,                       // 3
-            Phone.CONTACT_ID,                   // 4
-            Phone.LOOKUP_KEY,                   // 5
-            Phone.DISPLAY_NAME_ALTERNATIVE,     // 6
-        };
-
-        public static final int PHONE_ID           = 0;
-        public static final int PHONE_TYPE         = 1;
-        public static final int PHONE_LABEL        = 2;
-        public static final int PHONE_NUMBER       = 3;
-        public static final int PHONE_CONTACT_ID   = 4;
-        public static final int PHONE_LOOKUP_KEY   = 5;
-        public static final int PHONE_DISPLAY_NAME = 6;
-
-        // Current contacts - those contacted within the last 3 days (in milliseconds)
-        final static long LAST_TIME_USED_CURRENT_MS = 3L * 24 * 60 * 60 * 1000;
-
-        // Recent contacts - those contacted within the last 30 days (in milliseconds)
-        final static long LAST_TIME_USED_RECENT_MS = 30L * 24 * 60 * 60 * 1000;
-
-        final static String TIME_SINCE_LAST_USED_MS =
-                "(? - " + Data.LAST_TIME_USED + ")";
-
-        final static String SORT_BY_DATA_USAGE =
-                "(CASE WHEN " + TIME_SINCE_LAST_USED_MS + " < " + LAST_TIME_USED_CURRENT_MS +
-                " THEN 0 " +
-                " WHEN " + TIME_SINCE_LAST_USED_MS + " < " + LAST_TIME_USED_RECENT_MS +
-                " THEN 1 " +
-                " ELSE 2 END), " +
-                Data.TIMES_USED + " DESC";
-
-        // This sort order is similar to that used by the ContactsProvider when returning a list
-        // of frequently called contacts.
-        public static final String SORT_ORDER =
-                Contacts.STARRED + " DESC, "
-                + Data.IS_SUPER_PRIMARY + " DESC, "
-                + SORT_BY_DATA_USAGE + ", "
-                + Contacts.IN_VISIBLE_GROUP + " DESC, "
-                + Contacts.DISPLAY_NAME + ", "
-                + Data.CONTACT_ID + ", "
-                + Data.IS_PRIMARY + " DESC";
-    }
-
-    // Static set used to determine which countries use NANP numbers
-    public static Set<String> sNanpCountries = null;
-
-    private SmartDialTrie mContactsCache;
-    private static AtomicInteger mCacheStatus;
-    private final SmartDialMap mMap;
-    private final int mNameDisplayOrder;
-    private final Context mContext;
-    private final static Object mLock = new Object();
-
-    /** The country code of the user's sim card obtained by calling getSimCountryIso*/
-    private static final String PREF_USER_SIM_COUNTRY_CODE =
-            "DialtactsActivity_user_sim_country_code";
-    private static final String PREF_USER_SIM_COUNTRY_CODE_DEFAULT = null;
-
-    private static String sUserSimCountryCode = PREF_USER_SIM_COUNTRY_CODE_DEFAULT;
-    private static boolean sUserInNanpRegion = false;
-
-    public static final int CACHE_NEEDS_RECACHE = 1;
-    public static final int CACHE_IN_PROGRESS = 2;
-    public static final int CACHE_COMPLETED = 3;
-
-    private static final boolean DEBUG = false;
-
-    private SmartDialCache(Context context, int nameDisplayOrder, SmartDialMap map) {
-        mNameDisplayOrder = nameDisplayOrder;
-        mMap = map;
-        Preconditions.checkNotNull(context, "Context must not be null");
-        mContext = context.getApplicationContext();
-        mCacheStatus = new AtomicInteger(CACHE_NEEDS_RECACHE);
-
-        final TelephonyManager manager = (TelephonyManager) context.getSystemService(
-                Context.TELEPHONY_SERVICE);
-        if (manager != null) {
-            sUserSimCountryCode = manager.getSimCountryIso();
-        }
-
-        final SharedPreferences prefs = PreferenceManager.getDefaultSharedPreferences(context);
-
-        if (sUserSimCountryCode != null) {
-            // Update shared preferences with the latest country obtained from getSimCountryIso
-            prefs.edit().putString(PREF_USER_SIM_COUNTRY_CODE, sUserSimCountryCode).apply();
-        } else {
-            // Couldn't get the country from getSimCountryIso. Maybe we are in airplane mode.
-            // Try to load the settings, if any from SharedPreferences.
-            sUserSimCountryCode = prefs.getString(PREF_USER_SIM_COUNTRY_CODE,
-                    PREF_USER_SIM_COUNTRY_CODE_DEFAULT);
-        }
-
-        sUserInNanpRegion = isCountryNanp(sUserSimCountryCode);
-
-    }
-
-    private static SmartDialCache instance;
-
-    /**
-     * Returns an instance of SmartDialCache.
-     *
-     * @param context A context that provides a valid ContentResolver.
-     * @param nameDisplayOrder One of the two name display order integer constants (1 or 2) as saved
-     *        in settings under the key
-     *        {@link android.provider.ContactsContract.Preferences#DISPLAY_ORDER}.
-     * @return An instance of SmartDialCache
-     */
-    public static synchronized SmartDialCache getInstance(Context context, int nameDisplayOrder,
-            SmartDialMap map) {
-        if (instance == null) {
-            instance = new SmartDialCache(context, nameDisplayOrder, map);
-        }
-        return instance;
-    }
-
-    /**
-     * Performs a database query, iterates through the returned cursor and saves the retrieved
-     * contacts to a local cache.
-     */
-    private void cacheContacts(Context context) {
-        mCacheStatus.set(CACHE_IN_PROGRESS);
-        synchronized(mLock) {
-            if (DEBUG) {
-                Log.d(LOG_TAG, "Starting caching thread");
-            }
-            final StopWatch stopWatch = DEBUG ? StopWatch.start("SmartDial Cache") : null;
-            final String millis = String.valueOf(System.currentTimeMillis());
-            final Cursor c = context.getContentResolver().query(PhoneQuery.URI,
-                    (mNameDisplayOrder == ContactsContract.Preferences.DISPLAY_ORDER_PRIMARY)
-                        ? PhoneQuery.PROJECTION_PRIMARY : PhoneQuery.PROJECTION_ALTERNATIVE,
-                    null, new String[] {millis, millis},
-                    PhoneQuery.SORT_ORDER);
-            if (DEBUG) {
-                stopWatch.lap("SmartDial query complete");
-            }
-            if (c == null) {
-                Log.w(LOG_TAG, "SmartDial query received null for cursor");
-                if (DEBUG) {
-                    stopWatch.stopAndLog("SmartDial query received null for cursor", 0);
-                }
-                mCacheStatus.getAndSet(CACHE_NEEDS_RECACHE);
-                return;
-            }
-            final SmartDialTrie cache = new SmartDialTrie(mMap, sUserInNanpRegion);
-            try {
-                c.moveToPosition(-1);
-                int affinityCount = 0;
-                while (c.moveToNext()) {
-                    final String displayName = c.getString(PhoneQuery.PHONE_DISPLAY_NAME);
-                    final String phoneNumber = c.getString(PhoneQuery.PHONE_NUMBER);
-                    final long id = c.getLong(PhoneQuery.PHONE_CONTACT_ID);
-                    final String lookupKey = c.getString(PhoneQuery.PHONE_LOOKUP_KEY);
-                    cache.put(new ContactNumber(id, displayName, phoneNumber, lookupKey,
-                            affinityCount));
-                    affinityCount++;
-                }
-            } finally {
-                c.close();
-                mContactsCache = cache;
-                if (DEBUG) {
-                    stopWatch.stopAndLog("SmartDial caching completed", 0);
-                }
-            }
-        }
-        if (DEBUG) {
-            Log.d(LOG_TAG, "Caching thread completed");
-        }
-        mCacheStatus.getAndSet(CACHE_COMPLETED);
-    }
-
-    /**
-     * Returns the list of cached contacts. This is blocking so it should not be called from the UI
-     * thread. There are 4 possible scenarios:
-     *
-     * 1) Cache is currently empty and there is no caching thread running - getContacts() starts a
-     * caching thread and returns the cache when completed
-     * 2) The cache is currently empty, but a caching thread has been started - getContacts() waits
-     * till the existing caching thread is completed before immediately returning the cache
-     * 3) The cache has already been populated, and there is no caching thread running -
-     * getContacts() returns the existing cache immediately
-     * 4) The cache has already been populated, but there is another caching thread running (due to
-     * a forced cache refresh due to content updates - getContacts() returns the existing cache
-     * immediately
-     *
-     * @return List of already cached contacts, or an empty list if the caching failed for any
-     * reason.
-     */
-    public SmartDialTrie getContacts() {
-        // Either scenario 3 or 4 - This means just go ahead and return the existing cache
-        // immediately even if there is a caching thread currently running. We are guaranteed to
-        // have the newest value of mContactsCache at this point because it is volatile.
-        if (mContactsCache != null) {
-            return mContactsCache;
-        }
-        // At this point we are forced to wait for cacheContacts to complete in another thread(if
-        // one currently exists) because of mLock.
-        synchronized(mLock) {
-            // If mContactsCache is still null at this point, either there was never any caching
-            // process running, or it failed (Scenario 1). If so, just go ahead and try to cache
-            // the contacts again.
-            if (mContactsCache == null) {
-                cacheContacts(mContext);
-                return (mContactsCache == null) ? new SmartDialTrie() : mContactsCache;
-            } else {
-                // After waiting for the lock on mLock to be released, mContactsCache is now
-                // non-null due to the completion of the caching thread (Scenario 2). Go ahead
-                // and return the existing cache.
-                return mContactsCache;
-            }
-        }
-    }
-
-    /**
-     * Cache contacts only if there is a need to (forced cache refresh or no attempt to cache yet).
-     * This method is called in 2 places: whenever the DialpadFragment comes into view, and in
-     * onResume.
-     *
-     * @param forceRecache If true, force a cache refresh.
-     */
-
-    public void cacheIfNeeded(boolean forceRecache) {
-        if (DEBUG) {
-            Log.d("SmartDial", "cacheIfNeeded called with " + String.valueOf(forceRecache));
-        }
-        if (mCacheStatus.get() == CACHE_IN_PROGRESS) {
-            return;
-        }
-        if (forceRecache || mCacheStatus.get() == CACHE_NEEDS_RECACHE) {
-            // Because this method can be possibly be called multiple times in rapid succession,
-            // set the cache status even before starting a caching thread to avoid unnecessarily
-            // spawning extra threads.
-            mCacheStatus.set(CACHE_IN_PROGRESS);
-            startCachingThread();
-        }
-    }
-
-    private void startCachingThread() {
-        new Thread(new Runnable() {
-            @Override
-            public void run() {
-                cacheContacts(mContext);
-            }
-        }).start();
-    }
-
-    public static class ContactAffinityComparator implements Comparator<ContactNumber> {
-        @Override
-        public int compare(ContactNumber lhs, ContactNumber rhs) {
-            // Smaller affinity is better because they are numbered in ascending order in
-            // the order the contacts were returned from the ContactsProvider (sorted by
-            // frequency of use and time last used
-            return Integer.compare(lhs.affinity, rhs.affinity);
-        }
-
-    }
-
-    public SmartDialMap getMap() {
-        return mMap;
-    }
-
-    public boolean getUserInNanpRegion() {
-        return sUserInNanpRegion;
-    }
-
-    /**
-     * Indicates whether the given country uses NANP numbers
-     *
-     * @param country ISO 3166 country code (case doesn't matter)
-     * @return True if country uses NANP numbers (e.g. US, Canada), false otherwise
-     */
-    @VisibleForTesting
-    static boolean isCountryNanp(String country) {
-        if (TextUtils.isEmpty(country)) {
-            return false;
-        }
-        if (sNanpCountries == null) {
-            sNanpCountries = initNanpCountries();
-        }
-        return sNanpCountries.contains(country.toUpperCase());
-    }
-
-    private static Set<String> initNanpCountries() {
-        final HashSet<String> result = new HashSet<String>();
-        result.add("US"); // United States
-        result.add("CA"); // Canada
-        result.add("AS"); // American Samoa
-        result.add("AI"); // Anguilla
-        result.add("AG"); // Antigua and Barbuda
-        result.add("BS"); // Bahamas
-        result.add("BB"); // Barbados
-        result.add("BM"); // Bermuda
-        result.add("VG"); // British Virgin Islands
-        result.add("KY"); // Cayman Islands
-        result.add("DM"); // Dominica
-        result.add("DO"); // Dominican Republic
-        result.add("GD"); // Grenada
-        result.add("GU"); // Guam
-        result.add("JM"); // Jamaica
-        result.add("PR"); // Puerto Rico
-        result.add("MS"); // Montserrat
-        result.add("MP"); // Northern Mariana Islands
-        result.add("KN"); // Saint Kitts and Nevis
-        result.add("LC"); // Saint Lucia
-        result.add("VC"); // Saint Vincent and the Grenadines
-        result.add("TT"); // Trinidad and Tobago
-        result.add("TC"); // Turks and Caicos Islands
-        result.add("VI"); // U.S. Virgin Islands
-        return result;
-    }
-}
diff --git a/src/com/android/dialer/dialpad/SmartDialLoaderTask.java b/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
index d584c1793..71cbfa27d 100644
--- a/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
+++ b/src/com/android/dialer/dialpad/SmartDialLoaderTask.java
@@ -18,24 +18,21 @@ package com.android.dialer.dialpad;
 
 import static com.android.dialer.dialpad.SmartDialController.LOG_TAG;
 
+import android.content.Context;
 import android.os.AsyncTask;
 import android.provider.ContactsContract;
 import android.provider.ContactsContract.Contacts;
 import android.telephony.PhoneNumberUtils;
-import android.util.Log;
 
 import com.android.contacts.common.preference.ContactsPreferences;
 import com.android.contacts.common.util.StopWatch;
-import com.android.dialer.dialpad.SmartDialCache.ContactNumber;
+import com.android.dialer.database.DialerDatabaseHelper;
+import com.android.dialer.database.DialerDatabaseHelper.ContactNumber;
 
-import com.google.common.base.Objects;
 import com.google.common.collect.Lists;
 
 import java.util.ArrayList;
-import java.util.Collections;
-import java.util.HashSet;
 import java.util.List;
-import java.util.Set;
 
 /**
  * This task searches through the provided cache to return the top 3 contacts(ranked by confidence)
@@ -50,28 +47,20 @@ public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDi
 
     static private final boolean DEBUG = false;
 
-    private static final int MAX_ENTRIES = 3;
-
-    private final SmartDialCache mContactsCache;
-
     private final SmartDialLoaderCallback mCallback;
 
+    private final DialerDatabaseHelper mDialerDatabaseHelper;
+
     private final String mQuery;
 
-    /**
-     * See {@link ContactsPreferences#getDisplayOrder()}.
-     * {@link ContactsContract.Preferences#DISPLAY_ORDER_PRIMARY} (first name first)
-     * {@link ContactsContract.Preferences#DISPLAY_ORDER_ALTERNATIVE} (last name first)
-     */
     private final SmartDialNameMatcher mNameMatcher;
 
-    public SmartDialLoaderTask(SmartDialLoaderCallback callback, String query,
-            SmartDialCache cache) {
+    public SmartDialLoaderTask(SmartDialLoaderCallback callback, String query, Context context) {
         this.mCallback = callback;
-        this.mContactsCache = cache;
-        this.mNameMatcher = new SmartDialNameMatcher(PhoneNumberUtils.normalizeNumber(query),
-                cache.getMap());
+        mDialerDatabaseHelper = DialerDatabaseHelper.getInstance(context);
         this.mQuery = query;
+        this.mNameMatcher = new SmartDialNameMatcher(PhoneNumberUtils.normalizeNumber(query),
+                SmartDialPrefix.getMap());
     }
 
     @Override
@@ -87,85 +76,33 @@ public class SmartDialLoaderTask extends AsyncTask<String, Integer, List<SmartDi
     }
 
     /**
-     * Loads all visible contacts with phone numbers and check if their display names match the
-     * query.  Return at most {@link #MAX_ENTRIES} {@link SmartDialEntry}'s for the matching
-     * contacts.
+     * Loads top visible contacts with phone numbers and check if their display names match the
+     * query.
      */
     private ArrayList<SmartDialEntry> getContactMatches() {
 
-        final SmartDialTrie trie = mContactsCache.getContacts();
-        final boolean matchNanp = mContactsCache.getUserInNanpRegion();
-
-        if (DEBUG) {
-            Log.d(LOG_TAG, "Size of cache: " + trie.size());
-        }
-
         final StopWatch stopWatch = DEBUG ? StopWatch.start("Start Match") : null;
-        final ArrayList<ContactNumber> allMatches = trie.getAllWithPrefix(mNameMatcher.getQuery());
+
+        final ArrayList<ContactNumber> allMatches = mDialerDatabaseHelper.getLooseMatches(mQuery,
+                mNameMatcher);
         if (DEBUG) {
             stopWatch.lap("Find matches");
         }
-        // Sort matches in order of ascending contact affinity (lower is better)
-        Collections.sort(allMatches, new SmartDialCache.ContactAffinityComparator());
-        if (DEBUG) {
-            stopWatch.lap("Sort");
-        }
-        final Set<ContactMatch> duplicates = new HashSet<ContactMatch>();
+
         final ArrayList<SmartDialEntry> candidates = Lists.newArrayList();
         for (ContactNumber contact : allMatches) {
-            final ContactMatch contactMatch = new ContactMatch(contact.lookupKey, contact.id);
-            // Don't add multiple contact numbers from the same contact into suggestions if
-            // there are multiple matches. Instead, just keep the highest priority number
-            // instead.
-            if (duplicates.contains(contactMatch)) {
-                continue;
-            }
-            duplicates.add(contactMatch);
             final boolean matches = mNameMatcher.matches(contact.displayName);
-
             candidates.add(new SmartDialEntry(
                     contact.displayName,
                     Contacts.getLookupUri(contact.id, contact.lookupKey),
                     contact.phoneNumber,
                     mNameMatcher.getMatchPositions(),
-                    mNameMatcher.matchesNumber(contact.phoneNumber,
-                            mNameMatcher.getQuery(), matchNanp)
+                    mNameMatcher.matchesNumber(contact.phoneNumber, mNameMatcher.getQuery())
                     ));
-            if (candidates.size() >= MAX_ENTRIES) {
-                break;
-            }
         }
         if (DEBUG) {
             stopWatch.stopAndLog(LOG_TAG + " Match Complete", 0);
         }
         return candidates;
     }
-
-    private class ContactMatch {
-        public final String lookupKey;
-        public final long id;
-
-        public ContactMatch(String lookupKey, long id) {
-            this.lookupKey = lookupKey;
-            this.id = id;
-        }
-
-        @Override
-        public int hashCode() {
-            return Objects.hashCode(lookupKey, id);
-        }
-
-        @Override
-        public boolean equals(Object object) {
-            if (this == object) {
-                return true;
-            }
-            if (object instanceof ContactMatch) {
-                ContactMatch that = (ContactMatch) object;
-                return Objects.equal(this.lookupKey, that.lookupKey)
-                        && Objects.equal(this.id, that.id);
-            }
-            return false;
-        }
-    }
 }
diff --git a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
index d7d5ad523..fe88e930d 100644
--- a/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
+++ b/src/com/android/dialer/dialpad/SmartDialNameMatcher.java
@@ -18,7 +18,7 @@ package com.android.dialer.dialpad;
 
 import android.text.TextUtils;
 
-import com.android.dialer.dialpad.SmartDialTrie.CountryCodeWithOffset;
+import com.android.dialer.dialpad.SmartDialPrefix.PhoneNumberTokens;
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.Lists;
@@ -88,40 +88,51 @@ public class SmartDialNameMatcher {
     }
 
     /**
-     * Matches a phone number against a query, taking care of formatting characters and also
-     * taking into account country code prefixes and special NANP number treatment.
+     * Matches a phone number against a query. Let the test application overwrite the NANP setting.
      *
      * @param phoneNumber - Raw phone number
      * @param query - Normalized query (only contains numbers from 0-9)
-     * @param matchNanp - Whether or not to do special matching for NANP numbers
+     * @param useNanp - Overwriting nanp setting boolean, used for testing.
      * @return {@literal null} if the number and the query don't match, a valid
      *         SmartDialMatchPosition with the matching positions otherwise
      */
-    public SmartDialMatchPosition matchesNumber(String phoneNumber, String query,
-            boolean matchNanp) {
+    @VisibleForTesting
+    public SmartDialMatchPosition matchesNumber(String phoneNumber, String query, boolean useNanp) {
         // Try matching the number as is
         SmartDialMatchPosition matchPos = matchesNumberWithOffset(phoneNumber, query, 0);
         if (matchPos == null) {
-            // Try matching the number without the '+' prefix, if any
-            final CountryCodeWithOffset code = SmartDialTrie.getOffsetWithoutCountryCode(
-                    phoneNumber);
-            if (code != null) {
-                matchPos = matchesNumberWithOffset(phoneNumber, query, code.offset);
+            final PhoneNumberTokens phoneNumberTokens =
+                    SmartDialPrefix.parsePhoneNumber(phoneNumber);
+
+            if (phoneNumberTokens == null) {
+                return matchPos;
             }
-            if (matchPos == null && matchNanp) {
-                // Try matching NANP numbers
-                final int[] offsets = SmartDialTrie.getOffsetForNANPNumbers(phoneNumber,
-                        mMap);
-                for (int i = 0; i < offsets.length; i++) {
-                    matchPos = matchesNumberWithOffset(phoneNumber, query, offsets[i]);
-                    if (matchPos != null) break;
-                }
+            if (phoneNumberTokens.countryCodeOffset != 0) {
+                matchPos = matchesNumberWithOffset(phoneNumber, query,
+                        phoneNumberTokens.countryCodeOffset);
+            }
+            if (matchPos == null && phoneNumberTokens.nanpCodeOffset != 0 && useNanp) {
+                matchPos = matchesNumberWithOffset(phoneNumber, query,
+                        phoneNumberTokens.nanpCodeOffset);
             }
         }
         return matchPos;
     }
 
     /**
+     * Matches a phone number against a query, taking care of formatting characters and also
+     * taking into account country code prefixes and special NANP number treatment.
+     *
+     * @param phoneNumber - Raw phone number
+     * @param query - Normalized query (only contains numbers from 0-9)
+     * @return {@literal null} if the number and the query don't match, a valid
+     *         SmartDialMatchPosition with the matching positions otherwise
+     */
+    public SmartDialMatchPosition matchesNumber(String phoneNumber, String query) {
+        return matchesNumber(phoneNumber, query, true);
+    }
+
+    /**
      * Matches a phone number against a query, taking care of formatting characters
      *
      * @param phoneNumber - Raw phone number
diff --git a/src/com/android/dialer/dialpad/SmartDialPrefix.java b/src/com/android/dialer/dialpad/SmartDialPrefix.java
new file mode 100644
index 000000000..857f6408a
--- /dev/null
+++ b/src/com/android/dialer/dialpad/SmartDialPrefix.java
@@ -0,0 +1,608 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dialer.dialpad;
+
+import android.content.Context;
+
+import android.content.SharedPreferences;
+import android.preference.PreferenceManager;
+import android.telephony.TelephonyManager;
+import android.text.TextUtils;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.Lists;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * Smart Dial utility class to find prefixes of contacts. It contains both methods to find supported
+ * prefix combinations for contact names, and also methods to find supported prefix combinations for
+ * contacts' phone numbers. Each contact name is separated into several tokens, such as first name,
+ * middle name, family name etc. Each phone number is also separated into country code, NANP area
+ * code, and local number if such separation is possible.
+ */
+public class SmartDialPrefix {
+
+    /** The number of starting and ending tokens in a contact's name considered for initials.
+     * For example, if both constants are set to 2, and a contact's name is
+     * "Albert Ben Charles Daniel Ed Foster", the first two tokens "Albert" "Ben", and last two
+     * tokens "Ed" "Foster" can be replaced by their initials in contact name matching.
+     * Users can look up this contact by combinations of his initials such as "AF" "BF" "EF" "ABF"
+     * "BEF" "ABEF" etc, but can not use combinations such as "CF" "DF" "ACF" "ADF" etc.
+     */
+    private static final int LAST_TOKENS_FOR_INITIALS = 2;
+    private static final int FIRST_TOKENS_FOR_INITIALS = 2;
+
+    /** The country code of the user's sim card obtained by calling getSimCountryIso*/
+    private static final String PREF_USER_SIM_COUNTRY_CODE =
+            "DialtactsActivity_user_sim_country_code";
+    private static final String PREF_USER_SIM_COUNTRY_CODE_DEFAULT = null;
+    private static String sUserSimCountryCode = PREF_USER_SIM_COUNTRY_CODE_DEFAULT;
+
+    /** Indicates whether user is in NANP regions.*/
+    private static boolean sUserInNanpRegion = false;
+
+    /** Set of country names that use NANP code.*/
+    private static Set<String> sNanpCountries = null;
+
+    /** Set of supported country codes in front of the phone number. */
+    private static Set<String> sCountryCodes = null;
+
+    /** Dialpad mapping. */
+    private static final SmartDialMap mMap = new LatinSmartDialMap();
+
+    private static boolean sNanpInitialized = false;
+
+    /** Initializes the Nanp settings, and finds out whether user is in a NANP region.*/
+    public static void initializeNanpSettings(Context context){
+        final TelephonyManager manager = (TelephonyManager) context.getSystemService(
+                Context.TELEPHONY_SERVICE);
+        if (manager != null) {
+            sUserSimCountryCode = manager.getSimCountryIso();
+        }
+
+        final SharedPreferences prefs = PreferenceManager.getDefaultSharedPreferences(context);
+
+        if (sUserSimCountryCode != null) {
+            /** Updates shared preferences with the latest country obtained from getSimCountryIso.*/
+            prefs.edit().putString(PREF_USER_SIM_COUNTRY_CODE, sUserSimCountryCode).apply();
+        } else {
+            /** Uses previously stored country code if loading fails. */
+            sUserSimCountryCode = prefs.getString(PREF_USER_SIM_COUNTRY_CODE,
+                    PREF_USER_SIM_COUNTRY_CODE_DEFAULT);
+        }
+        /** Queries the NANP country list to find out whether user is in a NANP region.*/
+        sUserInNanpRegion = isCountryNanp(sUserSimCountryCode);
+        sNanpInitialized = true;
+    }
+
+    /**
+     * Explicitly setting the user Nanp to the given boolean
+     */
+    @VisibleForTesting
+    public static void setUserInNanpRegion(boolean userInNanpRegion) {
+        sUserInNanpRegion = userInNanpRegion;
+    }
+
+    /**
+     * Class to record phone number parsing information.
+     */
+    public static class PhoneNumberTokens {
+        /** Country code of the phone number. */
+        final String countryCode;
+
+        /** Offset of national number after the country code. */
+        final int countryCodeOffset;
+
+        /** Offset of local number after NANP area code.*/
+        final int nanpCodeOffset;
+
+        public PhoneNumberTokens(String countryCode, int countryCodeOffset, int nanpCodeOffset) {
+            this.countryCode = countryCode;
+            this.countryCodeOffset = countryCodeOffset;
+            this.nanpCodeOffset = nanpCodeOffset;
+        }
+    }
+
+    /**
+     * Parses a contact's name into a list of separated tokens.
+     *
+     * @param contactName Contact's name stored in string.
+     * @return A list of name tokens, for example separated first names, last name, etc.
+     */
+    public static ArrayList<String> parseToIndexTokens(String contactName) {
+        final int length = contactName.length();
+        final ArrayList<String> result = Lists.newArrayList();
+        char c;
+        final StringBuilder currentIndexToken = new StringBuilder();
+        /**
+         * Iterates through the whole name string. If the current character is a valid character,
+         * append it to the current token. If the current character is not a valid character, for
+         * example space " ", mark the current token as complete and add it to the list of tokens.
+         */
+        for (int i = 0; i < length; i++) {
+            c = mMap.normalizeCharacter(contactName.charAt(i));
+            if (mMap.isValidDialpadCharacter(c)) {
+                /** Converts a character into the number on dialpad that represents the character.*/
+                currentIndexToken.append(mMap.getDialpadIndex(c));
+            } else {
+                if (currentIndexToken.length() != 0) {
+                    result.add(currentIndexToken.toString());
+                }
+                currentIndexToken.delete(0, currentIndexToken.length());
+            }
+        }
+
+        /** Adds the last token in case it has not been added.*/
+        if (currentIndexToken.length() != 0) {
+            result.add(currentIndexToken.toString());
+        }
+        return result;
+    }
+
+    /**
+     * Generates a list of strings that any prefix of any string in the list can be used to look
+     * up the contact's name.
+     *
+     * @param index The contact's name in string.
+     * @return A List of strings, whose prefix can be used to look up the contact.
+     */
+    public static ArrayList<String> generateNamePrefixes(String index) {
+        final ArrayList<String> result = Lists.newArrayList();
+
+        /** Parses the name into a list of tokens.*/
+        final ArrayList<String> indexTokens = parseToIndexTokens(index);
+
+        if (indexTokens.size() > 0) {
+            /** Adds the full token combinations to the list. For example, a contact with name
+             * "Albert Ben Ed Foster" can be looked up by any prefix of the following strings
+             * "Foster" "EdFoster" "BenEdFoster" and "AlbertBenEdFoster". This covers all cases of
+             * look up that contains only one token, and that spans multiple continuous tokens.
+             */
+            final StringBuilder fullNameToken = new StringBuilder();
+            for (int i = indexTokens.size() - 1; i >= 0; i--) {
+                fullNameToken.insert(0, indexTokens.get(i));
+                result.add(fullNameToken.toString());
+            }
+
+            /** Adds initial combinations to the list, with the number of initials restricted by
+             * {@link #LAST_TOKENS_FOR_INITIALS} and {@link #FIRST_TOKENS_FOR_INITIALS}.
+             * For example, a contact with name "Albert Ben Ed Foster" can be looked up by any
+             * prefix of the following strings "EFoster" "BFoster" "BEFoster" "AFoster" "ABFoster"
+             * "AEFoster" and "ABEFoster". This covers all cases of initial lookup.
+             */
+            ArrayList<String> fullNames = Lists.newArrayList();
+            fullNames.add(indexTokens.get(indexTokens.size() - 1));
+            final int recursiveNameStart = result.size();
+            int recursiveNameEnd = result.size();
+            String initial = "";
+            for (int i = indexTokens.size() - 2; i >= 0; i--) {
+                if ((i >= indexTokens.size() - LAST_TOKENS_FOR_INITIALS) ||
+                        (i < FIRST_TOKENS_FOR_INITIALS)) {
+                    initial = indexTokens.get(i).substring(0, 1);
+
+                    /** Recursively adds initial combinations to the list.*/
+                    for (int j = 0; j < fullNames.size(); ++j) {
+                        result.add(initial + fullNames.get(j));
+                    }
+                    for (int j = recursiveNameStart; j < recursiveNameEnd; ++j) {
+                       result.add(initial + result.get(j));
+                    }
+                    recursiveNameEnd = result.size();
+                    final String currentFullName = fullNames.get(fullNames.size() - 1);
+                    fullNames.add(indexTokens.get(i) +  currentFullName);
+                }
+            }
+        }
+
+        return result;
+    }
+
+    /**
+     * Computes a list of number strings based on tokens of a given phone number. Any prefix
+     * of any string in the list can be used to look up the phone number. The list include the
+     * full phone number, the national number if there is a country code in the phone number, and
+     * the local number if there is an area code in the phone number following the NANP format.
+     * For example, if a user has phone number +41 71 394 8392, the list will contain 41713948392
+     * and 713948392. Any prefix to either of the strings can be used to look up the phone number.
+     * If a user has a phone number +1 555-302-3029 (NANP format), the list will contain
+     * 15553023029, 5553023029, and 3023029.
+     *
+     * @param number String of user's phone number.
+     * @return A list of strings where any prefix of any entry can be used to look up the number.
+     */
+    public static ArrayList<String> parseToNumberTokens(String number) {
+        final ArrayList<String> result = Lists.newArrayList();
+        if (!TextUtils.isEmpty(number)) {
+            /** Adds the full number to the list.*/
+            result.add(SmartDialNameMatcher.normalizeNumber(number, mMap));
+
+            final PhoneNumberTokens phoneNumberTokens = parsePhoneNumber(number);
+            if (phoneNumberTokens == null) {
+                return result;
+            }
+
+            if (phoneNumberTokens.countryCodeOffset != 0) {
+                result.add(SmartDialNameMatcher.normalizeNumber(number,
+                        phoneNumberTokens.countryCodeOffset, mMap));
+            }
+
+            if (phoneNumberTokens.nanpCodeOffset != 0) {
+                result.add(SmartDialNameMatcher.normalizeNumber(number,
+                        phoneNumberTokens.nanpCodeOffset, mMap));
+            }
+        }
+        return result;
+    }
+
+    /**
+     * Parses a phone number to find out whether it has country code and NANP area code.
+     *
+     * @param number Raw phone number.
+     * @return a PhoneNumberToken instance with country code, NANP code information.
+     */
+    public static PhoneNumberTokens parsePhoneNumber(String number) {
+        String countryCode = "";
+        int countryCodeOffset = 0;
+        int nanpNumberOffset = 0;
+
+        if (!TextUtils.isEmpty(number)) {
+            String normalizedNumber = SmartDialNameMatcher.normalizeNumber(number, mMap);
+            if (number.charAt(0) == '+') {
+                /** If the number starts with '+', tries to find valid country code. */
+                for (int i = 1; i <= 1 + 3; i++) {
+                    if (number.length() <= i) {
+                        break;
+                    }
+                    countryCode = number.substring(1, i);
+                    if (isValidCountryCode(countryCode)) {
+                        countryCodeOffset = i;
+                        break;
+                    }
+                }
+            } else {
+                /** If the number does not start with '+', finds out whether it is in NANP
+                 * format and has '1' preceding the number.
+                 */
+                if ((normalizedNumber.charAt(0) == '1') && (normalizedNumber.length() == 11) &&
+                        (sUserInNanpRegion)) {
+                    countryCode = "1";
+                    countryCodeOffset = number.indexOf(normalizedNumber.charAt(1));
+                    if (countryCodeOffset == -1) {
+                        countryCodeOffset = 0;
+                    }
+                }
+            }
+
+            /** If user is in NANP region, finds out whether a number is in NANP format.*/
+            if (sUserInNanpRegion)  {
+                String areaCode = "";
+                if (countryCode.equals("") && normalizedNumber.length() == 10){
+                    /** if the number has no country code but fits the NANP format, extracts the
+                     * NANP area code, and finds out offset of the local number.
+                     */
+                    areaCode = normalizedNumber.substring(0, 3);
+                } else if (countryCode.equals("1") && normalizedNumber.length() == 11) {
+                    /** If the number has country code '1', finds out area code and offset of the
+                     * local number.
+                     */
+                    areaCode = normalizedNumber.substring(1, 4);
+                }
+                if (!areaCode.equals("")) {
+                    final int areaCodeIndex = number.indexOf(areaCode);
+                    if (areaCodeIndex != -1) {
+                        nanpNumberOffset = number.indexOf(areaCode) + 3;
+                    }
+                }
+            }
+        }
+        return new PhoneNumberTokens(countryCode, countryCodeOffset, nanpNumberOffset);
+    }
+
+    /**
+     * Checkes whether a country code is valid.
+     */
+    private static boolean isValidCountryCode(String countryCode) {
+        if (sCountryCodes == null) {
+            sCountryCodes = initCountryCodes();
+        }
+        return sCountryCodes.contains(countryCode);
+    }
+
+    private static Set<String> initCountryCodes() {
+        final HashSet<String> result = new HashSet<String>();
+        result.add("1");
+        result.add("7");
+        result.add("20");
+        result.add("27");
+        result.add("30");
+        result.add("31");
+        result.add("32");
+        result.add("33");
+        result.add("34");
+        result.add("36");
+        result.add("39");
+        result.add("40");
+        result.add("41");
+        result.add("43");
+        result.add("44");
+        result.add("45");
+        result.add("46");
+        result.add("47");
+        result.add("48");
+        result.add("49");
+        result.add("51");
+        result.add("52");
+        result.add("53");
+        result.add("54");
+        result.add("55");
+        result.add("56");
+        result.add("57");
+        result.add("58");
+        result.add("60");
+        result.add("61");
+        result.add("62");
+        result.add("63");
+        result.add("64");
+        result.add("65");
+        result.add("66");
+        result.add("81");
+        result.add("82");
+        result.add("84");
+        result.add("86");
+        result.add("90");
+        result.add("91");
+        result.add("92");
+        result.add("93");
+        result.add("94");
+        result.add("95");
+        result.add("98");
+        result.add("211");
+        result.add("212");
+        result.add("213");
+        result.add("216");
+        result.add("218");
+        result.add("220");
+        result.add("221");
+        result.add("222");
+        result.add("223");
+        result.add("224");
+        result.add("225");
+        result.add("226");
+        result.add("227");
+        result.add("228");
+        result.add("229");
+        result.add("230");
+        result.add("231");
+        result.add("232");
+        result.add("233");
+        result.add("234");
+        result.add("235");
+        result.add("236");
+        result.add("237");
+        result.add("238");
+        result.add("239");
+        result.add("240");
+        result.add("241");
+        result.add("242");
+        result.add("243");
+        result.add("244");
+        result.add("245");
+        result.add("246");
+        result.add("247");
+        result.add("248");
+        result.add("249");
+        result.add("250");
+        result.add("251");
+        result.add("252");
+        result.add("253");
+        result.add("254");
+        result.add("255");
+        result.add("256");
+        result.add("257");
+        result.add("258");
+        result.add("260");
+        result.add("261");
+        result.add("262");
+        result.add("263");
+        result.add("264");
+        result.add("265");
+        result.add("266");
+        result.add("267");
+        result.add("268");
+        result.add("269");
+        result.add("290");
+        result.add("291");
+        result.add("297");
+        result.add("298");
+        result.add("299");
+        result.add("350");
+        result.add("351");
+        result.add("352");
+        result.add("353");
+        result.add("354");
+        result.add("355");
+        result.add("356");
+        result.add("357");
+        result.add("358");
+        result.add("359");
+        result.add("370");
+        result.add("371");
+        result.add("372");
+        result.add("373");
+        result.add("374");
+        result.add("375");
+        result.add("376");
+        result.add("377");
+        result.add("378");
+        result.add("379");
+        result.add("380");
+        result.add("381");
+        result.add("382");
+        result.add("385");
+        result.add("386");
+        result.add("387");
+        result.add("389");
+        result.add("420");
+        result.add("421");
+        result.add("423");
+        result.add("500");
+        result.add("501");
+        result.add("502");
+        result.add("503");
+        result.add("504");
+        result.add("505");
+        result.add("506");
+        result.add("507");
+        result.add("508");
+        result.add("509");
+        result.add("590");
+        result.add("591");
+        result.add("592");
+        result.add("593");
+        result.add("594");
+        result.add("595");
+        result.add("596");
+        result.add("597");
+        result.add("598");
+        result.add("599");
+        result.add("670");
+        result.add("672");
+        result.add("673");
+        result.add("674");
+        result.add("675");
+        result.add("676");
+        result.add("677");
+        result.add("678");
+        result.add("679");
+        result.add("680");
+        result.add("681");
+        result.add("682");
+        result.add("683");
+        result.add("685");
+        result.add("686");
+        result.add("687");
+        result.add("688");
+        result.add("689");
+        result.add("690");
+        result.add("691");
+        result.add("692");
+        result.add("800");
+        result.add("808");
+        result.add("850");
+        result.add("852");
+        result.add("853");
+        result.add("855");
+        result.add("856");
+        result.add("870");
+        result.add("878");
+        result.add("880");
+        result.add("881");
+        result.add("882");
+        result.add("883");
+        result.add("886");
+        result.add("888");
+        result.add("960");
+        result.add("961");
+        result.add("962");
+        result.add("963");
+        result.add("964");
+        result.add("965");
+        result.add("966");
+        result.add("967");
+        result.add("968");
+        result.add("970");
+        result.add("971");
+        result.add("972");
+        result.add("973");
+        result.add("974");
+        result.add("975");
+        result.add("976");
+        result.add("977");
+        result.add("979");
+        result.add("992");
+        result.add("993");
+        result.add("994");
+        result.add("995");
+        result.add("996");
+        result.add("998");
+        return result;
+    }
+
+    public static SmartDialMap getMap() {
+        return mMap;
+    }
+
+    /**
+     * Indicates whether the given country uses NANP numbers
+     * @see <a href="https://en.wikipedia.org/wiki/North_American_Numbering_Plan">
+     *     https://en.wikipedia.org/wiki/North_American_Numbering_Plan</a>
+     *
+     * @param country ISO 3166 country code (case doesn't matter)
+     * @return True if country uses NANP numbers (e.g. US, Canada), false otherwise
+     */
+    @VisibleForTesting
+    public static boolean isCountryNanp(String country) {
+        if (TextUtils.isEmpty(country)) {
+            return false;
+        }
+        if (sNanpCountries == null) {
+            sNanpCountries = initNanpCountries();
+        }
+        return sNanpCountries.contains(country.toUpperCase());
+    }
+
+    private static Set<String> initNanpCountries() {
+        final HashSet<String> result = new HashSet<String>();
+        result.add("US"); // United States
+        result.add("CA"); // Canada
+        result.add("AS"); // American Samoa
+        result.add("AI"); // Anguilla
+        result.add("AG"); // Antigua and Barbuda
+        result.add("BS"); // Bahamas
+        result.add("BB"); // Barbados
+        result.add("BM"); // Bermuda
+        result.add("VG"); // British Virgin Islands
+        result.add("KY"); // Cayman Islands
+        result.add("DM"); // Dominica
+        result.add("DO"); // Dominican Republic
+        result.add("GD"); // Grenada
+        result.add("GU"); // Guam
+        result.add("JM"); // Jamaica
+        result.add("PR"); // Puerto Rico
+        result.add("MS"); // Montserrat
+        result.add("MP"); // Northern Mariana Islands
+        result.add("KN"); // Saint Kitts and Nevis
+        result.add("LC"); // Saint Lucia
+        result.add("VC"); // Saint Vincent and the Grenadines
+        result.add("TT"); // Trinidad and Tobago
+        result.add("TC"); // Turks and Caicos Islands
+        result.add("VI"); // U.S. Virgin Islands
+        return result;
+    }
+
+    /**
+     * Returns whether the user is in a region that uses Nanp format based on the sim location.
+     *
+     * @return Whether user is in Nanp region.
+     */
+    public static boolean getUserInNanpRegion() {
+        return sUserInNanpRegion;
+    }
+}
diff --git a/src/com/android/dialer/dialpad/SmartDialTrie.java b/src/com/android/dialer/dialpad/SmartDialTrie.java
deleted file mode 100644
index c62210b17..000000000
--- a/src/com/android/dialer/dialpad/SmartDialTrie.java
+++ /dev/null
@@ -1,671 +0,0 @@
-/*
- * Copyright (C) 2013 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.dialer.dialpad;
-
-import android.text.TextUtils;
-
-import com.android.dialer.dialpad.SmartDialCache.ContactNumber;
-import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.Lists;
-
-import java.util.ArrayList;
-import java.util.HashSet;
-import java.util.Set;
-
-/**
- * Prefix trie where the only allowed characters are the characters '0' to '9'. Multiple contacts
- * can occupy the same nodes.
- *
- * <p>Provides functions to get all contacts that lie on or below a node.
- * This is useful for retrieving all contacts that start with that prefix.</p>
- *
- * <p>Also contains special logic to handle NANP numbers in the case that the user is from a region
- * that uses NANP numbers.</p>
- */
-public class SmartDialTrie {
-    @VisibleForTesting
-    static class ParseInfo {
-        byte[] indexes;
-        int nthFirstTokenPos;
-        int nthLastTokenPos;
-    }
-
-    /**
-     * A country code and integer offset pair that represents the parsed country code in a
-     * phone number. The country code is a string containing the numeric country-code prefix in
-     * a phone number (e.g. 1 or 852). The offset is the integer position of where the country code
-     * ends in a phone number.
-     */
-    public static class CountryCodeWithOffset {
-        public static final CountryCodeWithOffset NO_COUNTRY_CODE = new CountryCodeWithOffset(0,
-                "");
-
-        final String countryCode;
-        final int offset;
-
-        public CountryCodeWithOffset(int offset, String countryCode) {
-            this.countryCode = countryCode;
-            this.offset = offset;
-        }
-    }
-
-    final Node mRoot = new Node();
-    private int mSize = 0;
-    private final SmartDialMap mMap;
-    private final boolean mFormatNanp;
-
-    private static final int LAST_TOKENS_FOR_INITIALS = 2;
-    private static final int FIRST_TOKENS_FOR_INITIALS = 2;
-
-    // Static set of all possible country codes in the world
-    public static Set<String> sCountryCodes = null;
-
-    public SmartDialTrie() {
-        // Use the latin letter to digit map by default if none provided
-        this(new LatinSmartDialMap(), false);
-    }
-
-    /**
-     * Creates a new SmartDialTrie.
-     *
-     * @param formatNanp True if inserted numbers are to be treated as NANP numbers
-     * such that numbers are automatically broken up by country prefix and area code.
-     */
-    @VisibleForTesting
-    public SmartDialTrie(boolean formatNanp) {
-        this(new LatinSmartDialMap(), formatNanp);
-    }
-
-    /**
-     * Creates a new SmartDialTrie.
-     *
-     * @param charMap Mapping of characters to digits to use when inserting names into the trie.
-     * @param formatNanp True if inserted numbers are to be treated as NANP numbers
-     * such that numbers are automatically broken up by country prefix and area code.
-     */
-    public SmartDialTrie(SmartDialMap map, boolean formatNanp) {
-        mMap = map;
-        mFormatNanp = formatNanp;
-    }
-
-    /**
-     * Returns all contacts in the prefix tree that correspond to this prefix.
-     */
-    public ArrayList<ContactNumber> getAllWithPrefix(CharSequence prefix) {
-        final ArrayList<ContactNumber> result = Lists.newArrayList();
-        if (TextUtils.isEmpty(prefix)) {
-            return result;
-        }
-        Node current = mRoot;
-        for (int i = 0; i < prefix.length(); i++) {
-            char ch = prefix.charAt(i);
-            current = current.getChild(ch, false);
-            if (current == null) {
-                return result;
-            }
-        }
-        // return all contacts that correspond to this prefix
-        getAll(current, result);
-        return result;
-    }
-
-    /**
-     * Returns all the contacts located at and under the provided node(including its children)
-     */
-    private void getAll(Node root, ArrayList<ContactNumber> output) {
-        if (root == null) {
-            return;
-        }
-        if (root.getContents() != null) {
-            output.addAll(root.getContents());
-        }
-        for (int i = 0; i < root.getChildrenSize(); i++) {
-            getAll(root.getChild(i, false), output);
-        }
-    }
-
-    /**
-     * Adds the display name and phone number of a contact into the prefix trie.
-     *
-     * @param contact Desired contact to add
-     */
-    public void put(ContactNumber contact) {
-        // Preconvert the display name into a byte array containing indexes to avoid having to
-        // remap each character over multiple passes
-        final ParseInfo info = parseToIndexes(contact.displayName, FIRST_TOKENS_FOR_INITIALS,
-                LAST_TOKENS_FOR_INITIALS);
-        putForPrefix(contact, mRoot, info, 0, true);
-        // We don't need to do the same for phone numbers since we only make one pass over them.
-        // Strip the calling code from the phone number here
-        if (!TextUtils.isEmpty(contact.phoneNumber)) {
-            // Handle country codes for numbers with a + prefix
-            final CountryCodeWithOffset code = getOffsetWithoutCountryCode(contact.phoneNumber);
-            if (code.offset != 0) {
-                putNumber(contact, contact.phoneNumber, code.offset);
-            }
-            if ((code.countryCode.equals("1") || code.offset == 0) && mFormatNanp) {
-                // Special case handling for NANP numbers (1-xxx-xxx-xxxx)
-                final String stripped = SmartDialNameMatcher.normalizeNumber(
-                        contact.phoneNumber, code.offset, mMap);
-                if (!TextUtils.isEmpty(stripped)) {
-                    int trunkPrefixOffset = 0;
-                    if (stripped.charAt(0) == '1') {
-                        // If the number starts with 1, we can assume its the trunk prefix.
-                        trunkPrefixOffset = 1;
-                    }
-                    if (stripped.length() == (10 + trunkPrefixOffset)) {
-                        // Valid NANP number
-                        if (trunkPrefixOffset != 0) {
-                            // Add the digits that follow the 1st digit (trunk prefix)
-                            // If trunkPrefixOffset is 0, we will add the number as is anyway, so
-                            // don't bother.
-                            putNumber(contact, stripped, trunkPrefixOffset);
-                        }
-                        // Add the digits that follow the next 3 digits (area code)
-                        putNumber(contact, stripped, 3 + trunkPrefixOffset);
-                    }
-                }
-            }
-            putNumber(contact, contact.phoneNumber, 0);
-        }
-        mSize++;
-    }
-
-    public static CountryCodeWithOffset getOffsetWithoutCountryCode(String number) {
-        if (!TextUtils.isEmpty(number)) {
-            if (number.charAt(0) == '+') {
-                // check for international code here
-                for (int i = 1; i <= 1 + 3; i++) {
-                    if (number.length() <= i) break;
-                    final String countryCode = number.substring(1, i);
-                    if (isValidCountryCode(countryCode)) {
-                        return new CountryCodeWithOffset(i, countryCode);
-                    }
-                }
-            }
-        }
-        return CountryCodeWithOffset.NO_COUNTRY_CODE;
-    }
-
-    /**
-     * Used by SmartDialNameMatcher to determine which character in the phone number to start
-     * the matching process from for a NANP formatted number.
-     *
-     * @param number Raw phone number
-     * @return An empty array if the provided number does not appear to be an NANP number,
-     * and an array containing integer offsets for the number (starting after the '1' prefix,
-     * and the area code prefix respectively.
-     */
-    public static int[] getOffsetForNANPNumbers(String number, SmartDialMap map) {
-        int validDigits = 0;
-        boolean hasPrefix = false;
-        int firstOffset = 0; // Tracks the location of the first digit after the '1' prefix
-        int secondOffset = 0; // Tracks the location of the first digit after the area code
-        for (int i = 0; i < number.length(); i++) {
-            final char ch = number.charAt(i);
-            if (map.isValidDialpadNumericChar(ch)) {
-                if (validDigits == 0) {
-                    // Check the first digit to see if it is 1
-                    if (ch == '1') {
-                        if (hasPrefix) {
-                            // Prefix has two '1's in a row. Invalid number, since area codes
-                            // cannot start with 1, so just bail
-                            break;
-                        }
-                        hasPrefix = true;
-                        continue;
-                    }
-                }
-                validDigits++;
-                if (validDigits == 1) {
-                    // Found the first digit after the country code
-                    firstOffset = i;
-                } else if (validDigits == 4) {
-                    // Found the first digit after the area code
-                    secondOffset = i;
-                }
-            }
-
-        }
-        if (validDigits == 10) {
-            return hasPrefix ? new int[] {firstOffset, secondOffset} : new int[] {secondOffset};
-        }
-        return new int[0];
-    }
-
-    /**
-     * Converts the given characters into a byte array of index and returns it together with offset
-     * information in a {@link ParseInfo} data structure.
-     * @param chars Characters to convert into indexes
-     * @param firstNTokens The first n tokens we want the offset for
-     * @param lastNTokens The last n tokens we want the offset for
-     */
-    @VisibleForTesting
-    ParseInfo parseToIndexes(CharSequence chars, int firstNTokens, int lastNTokens) {
-        final int length = chars.length();
-        final byte[] result = new byte[length];
-        final ArrayList<Integer> offSets = new ArrayList<Integer>();
-        char c;
-        int tokenCount = 0;
-        boolean atSeparator = true;
-        for (int i = 0; i < length; i++) {
-            c = mMap.normalizeCharacter(chars.charAt(i));
-            if (mMap.isValidDialpadCharacter(c)) {
-                if (atSeparator) {
-                    tokenCount++;
-                }
-                atSeparator = false;
-                result[i] = mMap.getDialpadIndex(c);
-            } else {
-                // Found the last character of the current token
-                if (!atSeparator) {
-                    offSets.add(i);
-                }
-                result[i] = -1;
-                atSeparator = true;
-            }
-        }
-
-        final ParseInfo info = new ParseInfo();
-        info.indexes = result;
-        info.nthFirstTokenPos = offSets.size() >= firstNTokens ? offSets.get(firstNTokens - 1) :
-                length - 1;
-        info.nthLastTokenPos = offSets.size() >= lastNTokens ? offSets.get(offSets.size() -
-                lastNTokens) : 0;
-        return info;
-    }
-
-    /**
-     * Puts a phone number and its associated contact into the prefix trie.
-     *
-     * @param contact - Contact to add to the trie
-     * @param phoneNumber - Phone number of the contact
-     * @param offSet - The nth character of the phone number to start from
-     */
-    private void putNumber(ContactNumber contact, String phoneNumber, int offSet) {
-        Preconditions.checkArgument(offSet < phoneNumber.length());
-        Node current = mRoot;
-        final int length = phoneNumber.length();
-        char ch;
-        for (int i = offSet; i < length; i++) {
-            ch = phoneNumber.charAt(i);
-            if (mMap.isValidDialpadNumericChar(ch)) {
-                current = current.getChild(ch, true);
-            }
-        }
-        current.add(contact);
-    }
-
-    /**
-     * Place an contact into the trie using at the provided node using the provided prefix. Uses as
-     * the input prefix a byte array instead of a CharSequence, as we will be traversing the array
-     * multiple times and it is more efficient to pre-convert the prefix into indexes before hand.
-     * Adds initial matches for the first token, and the last N tokens in the name.
-     *
-     * @param contact Contact to put
-     * @param root Root node to use as the starting point
-     * @param parseInfo ParseInfo data structure containing the converted byte array, as well as
-     *        token offsets that determine which tokens should have entries added for initial
-     *        search
-     * @param start - Starting index of the byte array
-     * @param isFullName If true, prefix will be treated as a full name and everytime a new name
-     *        token is encountered, the rest of the name segment is added into the trie.
-     */
-    private void putForPrefix(ContactNumber contact, Node root, ParseInfo info, int start,
-            boolean isFullName) {
-        final boolean addInitialMatches = (start >= info.nthLastTokenPos ||
-                start <= info.nthFirstTokenPos);
-        final byte[] indexes = info.indexes;
-        Node current = root;
-        Node initialNode = root;
-        final int length = indexes.length;
-        boolean atSeparator = true;
-        byte index;
-        for (int i = start; i < length; i++) {
-            index = indexes[i];
-            if (index > -1) {
-                if (atSeparator) {
-                    atSeparator = false;
-                    // encountered a new name token, so add this token into the tree starting from
-                    // the root node
-                    if (initialNode != this.mRoot) {
-                        if (isFullName) {
-                            putForPrefix(contact, this.mRoot, info, i, false);
-                        }
-                        if (addInitialMatches &&
-                                (i >= info.nthLastTokenPos || i <= info.nthFirstTokenPos) &&
-                                initialNode != root) {
-                            putForPrefix(contact, initialNode, info, i, false);
-                        }
-                    }
-                    // Set initial node to the node indexed by the first character of the current
-                    // prefix
-                    if (initialNode == root) {
-                        initialNode = initialNode.getChild(index, true);
-                    }
-                }
-                current = current.getChild(index, true);
-            } else {
-                atSeparator = true;
-            }
-        }
-        current.add(contact);
-    }
-
-    /* Used only for testing to verify we insert the correct number of entries into the trie */
-    @VisibleForTesting
-    int numEntries() {
-        final ArrayList<ContactNumber> result = Lists.newArrayList();
-        getAll(mRoot, result);
-        return result.size();
-    }
-
-
-    @VisibleForTesting
-    public int size() {
-        return mSize;
-    }
-
-    @VisibleForTesting
-    /* package */ static class Node {
-        Node[] mChildren;
-        private ArrayList<ContactNumber> mContents;
-
-        public Node() {
-            // don't allocate array or contents unless needed
-        }
-
-        public int getChildrenSize() {
-            if (mChildren == null) {
-                return -1;
-            }
-            return mChildren.length;
-        }
-
-        /**
-         * Returns a specific child of the current node.
-         *
-         * @param index Index of the child to return.
-         * @param createIfDoesNotExist Whether or not to create a node in that child slot if one
-         *        does not already currently exist.
-         * @return The existing or newly created child, or {@literal null} if the child does not
-         *         exist and createIfDoesNotExist is false.
-         */
-        public Node getChild(int index, boolean createIfDoesNotExist) {
-            if (createIfDoesNotExist) {
-                if (mChildren == null) {
-                    mChildren = new Node[10];
-                }
-                if (mChildren[index] == null) {
-                    mChildren[index] = new Node();
-                }
-            } else {
-                if (mChildren == null) {
-                    return null;
-                }
-            }
-            return mChildren[index];
-        }
-
-        /**
-         * Same as getChild(int index, boolean createIfDoesNotExist), but takes a character from '0'
-         * to '9' as an index.
-         */
-        public Node getChild(char index, boolean createIfDoesNotExist) {
-            return getChild(index - '0', createIfDoesNotExist);
-        }
-
-        public void add(ContactNumber contact) {
-            if (mContents == null) {
-                mContents = Lists.newArrayList();
-            }
-            mContents.add(contact);
-        }
-
-        public ArrayList<ContactNumber> getContents() {
-            return mContents;
-        }
-    }
-
-    private static boolean isValidCountryCode(String countryCode) {
-        if (sCountryCodes == null) {
-            sCountryCodes = initCountryCodes();
-        }
-        return sCountryCodes.contains(countryCode);
-    }
-
-    private static Set<String> initCountryCodes() {
-        final HashSet<String> result = new HashSet<String>();
-        result.add("1");
-        result.add("7");
-        result.add("20");
-        result.add("27");
-        result.add("30");
-        result.add("31");
-        result.add("32");
-        result.add("33");
-        result.add("34");
-        result.add("36");
-        result.add("39");
-        result.add("40");
-        result.add("41");
-        result.add("43");
-        result.add("44");
-        result.add("45");
-        result.add("46");
-        result.add("47");
-        result.add("48");
-        result.add("49");
-        result.add("51");
-        result.add("52");
-        result.add("53");
-        result.add("54");
-        result.add("55");
-        result.add("56");
-        result.add("57");
-        result.add("58");
-        result.add("60");
-        result.add("61");
-        result.add("62");
-        result.add("63");
-        result.add("64");
-        result.add("65");
-        result.add("66");
-        result.add("81");
-        result.add("82");
-        result.add("84");
-        result.add("86");
-        result.add("90");
-        result.add("91");
-        result.add("92");
-        result.add("93");
-        result.add("94");
-        result.add("95");
-        result.add("98");
-        result.add("211");
-        result.add("212");
-        result.add("213");
-        result.add("216");
-        result.add("218");
-        result.add("220");
-        result.add("221");
-        result.add("222");
-        result.add("223");
-        result.add("224");
-        result.add("225");
-        result.add("226");
-        result.add("227");
-        result.add("228");
-        result.add("229");
-        result.add("230");
-        result.add("231");
-        result.add("232");
-        result.add("233");
-        result.add("234");
-        result.add("235");
-        result.add("236");
-        result.add("237");
-        result.add("238");
-        result.add("239");
-        result.add("240");
-        result.add("241");
-        result.add("242");
-        result.add("243");
-        result.add("244");
-        result.add("245");
-        result.add("246");
-        result.add("247");
-        result.add("248");
-        result.add("249");
-        result.add("250");
-        result.add("251");
-        result.add("252");
-        result.add("253");
-        result.add("254");
-        result.add("255");
-        result.add("256");
-        result.add("257");
-        result.add("258");
-        result.add("260");
-        result.add("261");
-        result.add("262");
-        result.add("263");
-        result.add("264");
-        result.add("265");
-        result.add("266");
-        result.add("267");
-        result.add("268");
-        result.add("269");
-        result.add("290");
-        result.add("291");
-        result.add("297");
-        result.add("298");
-        result.add("299");
-        result.add("350");
-        result.add("351");
-        result.add("352");
-        result.add("353");
-        result.add("354");
-        result.add("355");
-        result.add("356");
-        result.add("357");
-        result.add("358");
-        result.add("359");
-        result.add("370");
-        result.add("371");
-        result.add("372");
-        result.add("373");
-        result.add("374");
-        result.add("375");
-        result.add("376");
-        result.add("377");
-        result.add("378");
-        result.add("379");
-        result.add("380");
-        result.add("381");
-        result.add("382");
-        result.add("385");
-        result.add("386");
-        result.add("387");
-        result.add("389");
-        result.add("420");
-        result.add("421");
-        result.add("423");
-        result.add("500");
-        result.add("501");
-        result.add("502");
-        result.add("503");
-        result.add("504");
-        result.add("505");
-        result.add("506");
-        result.add("507");
-        result.add("508");
-        result.add("509");
-        result.add("590");
-        result.add("591");
-        result.add("592");
-        result.add("593");
-        result.add("594");
-        result.add("595");
-        result.add("596");
-        result.add("597");
-        result.add("598");
-        result.add("599");
-        result.add("670");
-        result.add("672");
-        result.add("673");
-        result.add("674");
-        result.add("675");
-        result.add("676");
-        result.add("677");
-        result.add("678");
-        result.add("679");
-        result.add("680");
-        result.add("681");
-        result.add("682");
-        result.add("683");
-        result.add("685");
-        result.add("686");
-        result.add("687");
-        result.add("688");
-        result.add("689");
-        result.add("690");
-        result.add("691");
-        result.add("692");
-        result.add("800");
-        result.add("808");
-        result.add("850");
-        result.add("852");
-        result.add("853");
-        result.add("855");
-        result.add("856");
-        result.add("870");
-        result.add("878");
-        result.add("880");
-        result.add("881");
-        result.add("882");
-        result.add("883");
-        result.add("886");
-        result.add("888");
-        result.add("960");
-        result.add("961");
-        result.add("962");
-        result.add("963");
-        result.add("964");
-        result.add("965");
-        result.add("966");
-        result.add("967");
-        result.add("968");
-        result.add("970");
-        result.add("971");
-        result.add("972");
-        result.add("973");
-        result.add("974");
-        result.add("975");
-        result.add("976");
-        result.add("977");
-        result.add("979");
-        result.add("992");
-        result.add("993");
-        result.add("994");
-        result.add("995");
-        result.add("996");
-        result.add("998");
-        return result;
-    }
-}
diff --git a/tests/src/com/android/dialer/database/SmartDialPrefixTest.java b/tests/src/com/android/dialer/database/SmartDialPrefixTest.java
new file mode 100644
index 000000000..db0a0f38a
--- /dev/null
+++ b/tests/src/com/android/dialer/database/SmartDialPrefixTest.java
@@ -0,0 +1,597 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.dialer.database;
+
+import android.database.MatrixCursor;
+import android.database.sqlite.SQLiteDatabase;
+import android.provider.ContactsContract;
+import android.provider.ContactsContract.CommonDataKinds.Phone;
+import android.provider.ContactsContract.Contacts;
+import android.provider.ContactsContract.Data;
+import android.provider.ContactsContract.Directory;
+import android.test.suitebuilder.annotation.SmallTest;
+import android.test.suitebuilder.annotation.Suppress;
+import android.test.AndroidTestCase;
+
+import com.android.dialer.database.DialerDatabaseHelper;
+import com.android.dialer.database.DialerDatabaseHelper.ContactNumber;
+import com.android.dialer.dialpad.SmartDialNameMatcher;
+import com.android.dialer.dialpad.SmartDialPrefix;
+
+import junit.framework.TestCase;
+
+import java.lang.Exception;
+import java.lang.FindBugsSuppressWarnings;
+import java.lang.Override;
+import java.lang.String;
+import java.util.ArrayList;
+
+/**
+ * To run this test, use the command:
+ * adb shell am instrument -w -e class com.android.dialer.dialpad.SmartDialPrefixTest /
+ * com.android.dialer.tests/android.test.InstrumentationTestRunner
+ */
+@SmallTest
+public class SmartDialPrefixTest extends AndroidTestCase {
+
+    private DialerDatabaseHelper mTestHelper;
+
+    public void testIsCountryNanp_CaseInsensitive() {
+        assertFalse(SmartDialPrefix.isCountryNanp(null));
+        assertFalse(SmartDialPrefix.isCountryNanp("CN"));
+        assertFalse(SmartDialPrefix.isCountryNanp("HK"));
+        assertFalse(SmartDialPrefix.isCountryNanp("uk"));
+        assertFalse(SmartDialPrefix.isCountryNanp("sg"));
+        assertTrue(SmartDialPrefix.isCountryNanp("US"));
+        assertTrue(SmartDialPrefix.isCountryNanp("CA"));
+        assertTrue(SmartDialPrefix.isCountryNanp("AS"));
+        assertTrue(SmartDialPrefix.isCountryNanp("AI"));
+        assertTrue(SmartDialPrefix.isCountryNanp("AG"));
+        assertTrue(SmartDialPrefix.isCountryNanp("BS"));
+        assertTrue(SmartDialPrefix.isCountryNanp("BB"));
+        assertTrue(SmartDialPrefix.isCountryNanp("bm"));
+        assertTrue(SmartDialPrefix.isCountryNanp("vg"));
+        assertTrue(SmartDialPrefix.isCountryNanp("ky"));
+        assertTrue(SmartDialPrefix.isCountryNanp("dm"));
+        assertTrue(SmartDialPrefix.isCountryNanp("do"));
+        assertTrue(SmartDialPrefix.isCountryNanp("gd"));
+        assertTrue(SmartDialPrefix.isCountryNanp("gu"));
+        assertTrue(SmartDialPrefix.isCountryNanp("jm"));
+        assertTrue(SmartDialPrefix.isCountryNanp("pr"));
+        assertTrue(SmartDialPrefix.isCountryNanp("ms"));
+        assertTrue(SmartDialPrefix.isCountryNanp("mp"));
+        assertTrue(SmartDialPrefix.isCountryNanp("kn"));
+        assertTrue(SmartDialPrefix.isCountryNanp("lc"));
+        assertTrue(SmartDialPrefix.isCountryNanp("vc"));
+        assertTrue(SmartDialPrefix.isCountryNanp("tt"));
+        assertTrue(SmartDialPrefix.isCountryNanp("tc"));
+        assertTrue(SmartDialPrefix.isCountryNanp("vi"));
+    }
+
+    protected void setUp() {
+        mTestHelper = DialerDatabaseHelper.getNewInstanceForTest(getContext());
+    }
+
+    @Override
+    protected void tearDown() throws Exception {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+        mTestHelper.removeAllContacts(db);
+        super.tearDown();
+    }
+
+    @Suppress
+    public void testForNewContacts() {
+    }
+
+    @Suppress
+    public void testForUpdatedContacts() {
+    }
+
+    @Suppress
+    public void testForDeletedContacts() {
+    }
+
+    @Suppress
+    public void testSize() {
+    }
+
+
+    private MatrixCursor constructNewNameCursor() {
+        final MatrixCursor cursor = new MatrixCursor(new String[]{
+                DialerDatabaseHelper.SmartDialDbColumns.DISPLAY_NAME_PRIMARY,
+                DialerDatabaseHelper.SmartDialDbColumns.CONTACT_ID});
+        return cursor;
+    }
+
+    private MatrixCursor constructNewContactCursor() {
+        final MatrixCursor cursor = new MatrixCursor(new String[]{
+                Phone._ID,
+                Phone.TYPE,
+                Phone.LABEL,
+                Phone.NUMBER,
+                Phone.CONTACT_ID,
+                Phone.LOOKUP_KEY,
+                Phone.DISPLAY_NAME_PRIMARY,
+                Data.LAST_TIME_USED,
+                Data.TIMES_USED,
+                Contacts.STARRED,
+                Data.IS_SUPER_PRIMARY,
+                Contacts.IN_VISIBLE_GROUP,
+                Data.IS_PRIMARY});
+
+        return cursor;
+    }
+
+    private ContactNumber constructNewContact(MatrixCursor contactCursor, MatrixCursor nameCursor,
+            int id, String number, int contactId, String lookupKey, String displayName,
+            int lastTimeUsed, int timesUsed, int starred, int isSuperPrimary, int inVisibleGroup,
+            int isPrimary) {
+        assertNotNull(contactCursor);
+        assertNotNull(nameCursor);
+
+        contactCursor.addRow(new Object[]{id, "", "", number, contactId, lookupKey, displayName,
+                lastTimeUsed, timesUsed, starred, isSuperPrimary, inVisibleGroup, isPrimary});
+        nameCursor.addRow(new Object[]{displayName, contactId});
+
+        return new ContactNumber(contactId, displayName, number, lookupKey);
+    }
+
+    private ArrayList<ContactNumber> getLooseMatchesFromDb(String query) {
+        final SmartDialNameMatcher nameMatcher = new SmartDialNameMatcher(query,
+                SmartDialPrefix.getMap());
+        return mTestHelper.getLooseMatches(query, nameMatcher);
+    }
+
+    public void testPutForFullName() {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber jasonsmith = constructNewContact(contactCursor, nameCursor,
+                0, "", 0, "", "Jason Smith", 0, 0, 0, 0, 0, 0);
+        final ContactNumber jasonsmitt = constructNewContact(contactCursor, nameCursor,
+                1, "", 1, "", "Jason Smitt", 0, 0, 0, 0, 0, 0);
+        final ContactNumber alphabet = constructNewContact(contactCursor, nameCursor,
+                0, "12345678", 0, "", "abc def ghi jkl mno pqrs tuv wxyz", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        final ArrayList<ContactNumber> result1 = getLooseMatchesFromDb("5276676484");
+        assertFalse(result1.contains(jasonsmitt));
+
+        final ArrayList<ContactNumber> result2 = getLooseMatchesFromDb("5276676488");
+        assertFalse(result2.contains(jasonsmith));
+        assertTrue(result2.contains(jasonsmitt));
+
+        assertTrue(getLooseMatchesFromDb("22233344455566677778889999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("33344455566677778889999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("44455566677778889999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("55566677778889999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("66677778889999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("77778889999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("8889999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("9999").contains(alphabet));
+
+        // Makes sure the phone number is correctly added.
+        assertTrue(getLooseMatchesFromDb("12345678").contains(alphabet));
+    }
+
+    public void testPutForPartialName() {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber maryjane = constructNewContact(contactCursor, nameCursor,
+                0, "", 0, "", "Mary Jane", 0, 0, 0, 0, 0, 0);
+        final ContactNumber sarahsmith = constructNewContact(contactCursor, nameCursor,
+                0, "", 1, "", "Sarah Smith", 0, 0, 0, 0, 0, 0);
+        final ContactNumber jasonsmitt = constructNewContact(contactCursor, nameCursor,
+                0, "", 2, "", "Jason Smitt", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        final ArrayList<ContactNumber> result1 = getLooseMatchesFromDb("6279");
+        assertTrue(result1.contains(maryjane));
+        assertFalse(result1.contains(jasonsmitt));
+
+        // 72 corresponds to sa = "Sarah Smith" but not "Jason Smitt" or "Mary Jane"
+        final ArrayList<ContactNumber> result2 = getLooseMatchesFromDb("72");
+        assertFalse(result2.contains(maryjane));
+        assertTrue(result2.contains(sarahsmith));
+        assertFalse(result2.contains(jasonsmitt));
+
+        // 76 corresponds to sm = "Sarah Smith" and "Jason Smitt" but not "Mary Jane"
+        final ArrayList<ContactNumber> result3 = getLooseMatchesFromDb("76");
+        assertFalse(result3.contains(maryjane));
+        assertTrue(result3.contains(sarahsmith));
+        assertTrue(result3.contains(jasonsmitt));
+    }
+
+    public void testPutForNameTokens() {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber jasonfwilliams = constructNewContact(contactCursor, nameCursor,
+                0, "", 0, "", "Jason F. Williams", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        assertTrue(getLooseMatchesFromDb("527").contains(jasonfwilliams));
+        // 72 corresponds to sa = "Sarah Smith" but not "Jason Smitt" or "Mary Jane"
+        assertTrue(getLooseMatchesFromDb("945").contains(jasonfwilliams));
+        // 76 corresponds to sm = "Sarah Smith" and "Jason Smitt" but not "Mary Jane"
+        assertFalse(getLooseMatchesFromDb("66").contains(jasonfwilliams));
+    }
+
+    public void testPutForInitialMatches() {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber martinjuniorharry = constructNewContact(contactCursor, nameCursor,
+                0, "", 0, "", "Martin Jr Harry", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        // 654 corresponds to mjh = "(M)artin (J)r (H)arry"
+        assertTrue(getLooseMatchesFromDb("654").contains(martinjuniorharry));
+        // The reverse (456) does not match (for now)
+        assertFalse(getLooseMatchesFromDb("456").contains(martinjuniorharry));
+        // 6542 corresponds to mjha = "(M)artin (J)r (Ha)rry"
+        assertTrue(getLooseMatchesFromDb("6542").contains(martinjuniorharry));
+        // 542 corresponds to jha = "Martin (J)r (Ha)rry"
+        assertTrue(getLooseMatchesFromDb("542").contains(martinjuniorharry));
+        // 642 corresponds to mha = "(M)artin Jr (Ha)rry"
+        assertTrue(getLooseMatchesFromDb("642").contains(martinjuniorharry));
+        // 6542779 (M)artin (J)r (Harry)
+        assertTrue(getLooseMatchesFromDb("6542779").contains(martinjuniorharry));
+        // 65742779 (M)artin (Jr) (Harry)
+        assertTrue(getLooseMatchesFromDb("65742779").contains(martinjuniorharry));
+        // 542779 Martin (J)r (Harry)
+        assertTrue(getLooseMatchesFromDb("542779").contains(martinjuniorharry));
+        // 547 doesn't match
+        assertFalse(getLooseMatchesFromDb("547").contains(martinjuniorharry));
+        // 655 doesn't match
+        assertFalse(getLooseMatchesFromDb("655").contains(martinjuniorharry));
+        // 653 doesn't match
+        assertFalse(getLooseMatchesFromDb("653").contains(martinjuniorharry));
+        // 6543 doesn't match
+        assertFalse(getLooseMatchesFromDb("6543").contains(martinjuniorharry));
+
+        assertEquals(7, mTestHelper.countPrefixTableRows(db));
+    }
+
+    public void testPutForInitialMatchesForLongTokenNames() {
+
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber alphabet = constructNewContact(contactCursor, nameCursor,
+                0, "12345678", 0, "", "abc def ghi jkl mno pqrs tuv wxyz", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        // Makes sure only only the first two and last two token are considered for initials.
+        // The cut-off constant can be set in SmartDialPrefix.java
+        assertTrue(getLooseMatchesFromDb("2389999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("239999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("23888").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("2333").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("289999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("2888").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("29999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("3888").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("39999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("389999").contains(alphabet));
+        assertTrue(getLooseMatchesFromDb("89999").contains(alphabet));
+    }
+
+    public void testCheckLongToken() {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber alphabet = constructNewContact(contactCursor, nameCursor,
+                0, "1", 0, "", " aaaa bbbb cccc dddd eeee ffff gggg" +
+                " hhhh iiii jjjj kkkk llll mmmm nnnn oooo pppp qqqq rrrr ssss tttt uuuu vvvv " +
+                " wwww xxxx yyyy zzzz", 0, 0, 0, 0, 0, 0);
+
+        final ContactNumber alphabet2 = constructNewContact(contactCursor, nameCursor,
+                0, "1", 1, "", "aaaabbbbccccddddeeeeffffgggghhhhiiiijjjjkkkkllllmmmmnnnnoooopppp" +
+                "qqqqrrrrssssttttuuuuvvvvwwwwxxxxyyyyzzzz", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        assertTrue(getLooseMatchesFromDb("2222").contains(alphabet));
+        assertEquals(40, mTestHelper.countPrefixTableRows(db));
+    }
+
+    public void testParseInfo() {
+        final String name = "Mcdonald Jamie-Cullum";
+        final ArrayList<String> info = SmartDialPrefix.parseToIndexTokens(name);
+        assertEquals(3, info.size());
+        assertEquals(8, info.get(0).length());
+        assertEquals(5, info.get(1).length());
+        assertEquals(6, info.get(2).length());
+
+        final String name2 = "aaa bbb ccc ddd eee fff ggg hhh iii jjj kkk";
+        final ArrayList<String> info2 = SmartDialPrefix.parseToIndexTokens(name2);
+        assertEquals(11, info2.size());
+        assertEquals(3, info2.get(0).length());
+        assertEquals(3, info2.get(10).length());
+
+        final String name3 = "this  is- a,test    name";
+        final ArrayList<String> info3 = SmartDialPrefix.parseToIndexTokens(name3);
+        assertEquals(5, info3.size());
+        assertEquals(2, info3.get(1).length());
+        assertEquals(1, info3.get(2).length());
+        assertEquals(4, info3.get(3).length());
+        assertEquals(4, info3.get(4).length());
+
+        final String name4 = "M c-Donald James";
+        final ArrayList<String> info4 = SmartDialPrefix.parseToIndexTokens(name4);
+        assertEquals(4, info4.size());
+        assertEquals(1, info4.get(1).length());
+        assertEquals(6, info4.get(2).length());
+
+        final String name5 = "   Aa'Bb    c    dddd  e'e";
+        final ArrayList<String> info5 = SmartDialPrefix.parseToIndexTokens(name5);
+        assertEquals(6, info5.size());
+        assertEquals(2, info5.get(0).length());
+        assertEquals(1, info5.get(5).length());
+    }
+
+    public void testAccentedCharacters() {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber reene = constructNewContact(contactCursor, nameCursor,
+                0, "0", 0, "", "Reenée", 0, 0, 0, 0, 0, 0);
+        final ContactNumber bronte = constructNewContact(contactCursor, nameCursor,
+                0, "0", 1, "", "Brontë", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        assertTrue(getLooseMatchesFromDb("733633").contains(reene));
+        assertTrue(getLooseMatchesFromDb("276683").contains(bronte));
+    }
+
+    public void testNumbersInName() {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber contact = constructNewContact(contactCursor, nameCursor,
+                0, "0", 0, "", "12345678", 0, 0, 0, 0, 0, 0);
+        final ContactNumber teacher = constructNewContact(contactCursor, nameCursor,
+                0, "0", 1, "", "1st Grade Teacher", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        assertTrue(getLooseMatchesFromDb("12345678").contains(contact));
+        assertTrue(getLooseMatchesFromDb("17847233").contains(teacher));
+        assertTrue(getLooseMatchesFromDb("14832").contains(teacher));
+    }
+
+    public void testPutForNumbers() {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber contactno1 = constructNewContact(contactCursor, nameCursor,
+                0, "510-527-2357", 0, "", "James", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno2 = constructNewContact(contactCursor, nameCursor,
+                0, "77212862357", 1, "", "James", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno3 = constructNewContact(contactCursor, nameCursor,
+                0, "+13684976334", 2, "", "James", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        assertTrue(getLooseMatchesFromDb("510").contains(contactno1));
+        assertFalse(getLooseMatchesFromDb("511").contains(contactno1));
+        assertTrue(getLooseMatchesFromDb("77212862357").contains(contactno2));
+        assertFalse(getLooseMatchesFromDb("77212862356").contains(contactno2));
+        assertTrue(getLooseMatchesFromDb("1368").contains(contactno3));
+        assertFalse(getLooseMatchesFromDb("1367").contains(contactno3));
+    }
+
+    public void testPutNumbersCountryCode() {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber contactno1 = constructNewContact(contactCursor, nameCursor,
+                0, "+13684976334", 0, "", "James", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno2 = constructNewContact(contactCursor, nameCursor,
+                0, "+65 9177-6930", 1, "", "Jason", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno3 = constructNewContact(contactCursor, nameCursor,
+                0, "+85212345678", 2, "", "Mike", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno4 = constructNewContact(contactCursor, nameCursor,
+                0, "+85112345678", 3, "", "Invalid", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno5 = constructNewContact(contactCursor, nameCursor,
+                0, "+852", 4, "", "Invalid", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        assertTrue(getLooseMatchesFromDb("1368").contains(contactno1));
+        assertTrue(getLooseMatchesFromDb("368497").contains(contactno1));
+        assertFalse(getLooseMatchesFromDb("2368497").contains(contactno1));
+
+        assertTrue(getLooseMatchesFromDb("6591776930").contains(contactno2));
+        assertTrue(getLooseMatchesFromDb("91776930").contains(contactno2));
+        assertFalse(getLooseMatchesFromDb("591776930").contains(contactno2));
+
+        assertTrue(getLooseMatchesFromDb("85212345678").contains(contactno3));
+        assertTrue(getLooseMatchesFromDb("12345678").contains(contactno3));
+        assertFalse(getLooseMatchesFromDb("5212345678").contains(contactno3));
+
+        assertTrue(getLooseMatchesFromDb("85112345678").contains(contactno4));
+        assertFalse(getLooseMatchesFromDb("12345678").contains(contactno4));
+    }
+
+    // Tests special case handling for NANP numbers
+    public void testPutNumbersNANP() {
+        SmartDialPrefix.setUserInNanpRegion(true);
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        final ContactNumber contactno1 = constructNewContact(contactCursor, nameCursor,
+                0, "16503337596", 0, "", "James", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno2 = constructNewContact(contactCursor, nameCursor,
+                0, "5109921234", 1, "", "Michael", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno3 = constructNewContact(contactCursor, nameCursor,
+                0, "(415)-123-4567", 2, "", "Jason", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno4 = constructNewContact(contactCursor, nameCursor,
+                0, "1 510-284-9170", 3, "", "Mike", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno5 = constructNewContact(contactCursor, nameCursor,
+                0, "1-415-123-123", 4, "", "Invalid", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno6 = constructNewContact(contactCursor, nameCursor,
+                0, "415-123-123", 5, "", "Invalid2", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno7 = constructNewContact(contactCursor, nameCursor,
+                0, "+1-510-284-9170", 6, "", "Mike", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno8 = constructNewContact(contactCursor, nameCursor,
+                0, "+1-510-284-917", 7, "", "Invalid", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno9 = constructNewContact(contactCursor, nameCursor,
+                0, "+857-510-284-9170", 8, "", "Inv", 0, 0, 0, 0, 0, 0);
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        assertTrue(getLooseMatchesFromDb("16503337596").contains(contactno1));
+        assertTrue(getLooseMatchesFromDb("6503337596").contains(contactno1));
+        assertTrue(getLooseMatchesFromDb("3337596").contains(contactno1));
+
+        assertTrue(getLooseMatchesFromDb("5109921234").contains(contactno2));
+        assertTrue(getLooseMatchesFromDb("9921234").contains(contactno2));
+
+        assertTrue(getLooseMatchesFromDb("4151234567").contains(contactno3));
+        assertTrue(getLooseMatchesFromDb("1234567").contains(contactno3));
+
+        assertTrue(getLooseMatchesFromDb("15102849170").contains(contactno4));
+        assertTrue(getLooseMatchesFromDb("5102849170").contains(contactno4));
+        assertTrue(getLooseMatchesFromDb("2849170").contains(contactno4));
+
+        assertTrue(getLooseMatchesFromDb("1415123123").contains(contactno5));
+        assertFalse(getLooseMatchesFromDb("415123123").contains(contactno5));
+        assertFalse(getLooseMatchesFromDb("123123").contains(contactno5));
+
+        assertTrue(getLooseMatchesFromDb("415123123").contains(contactno6));
+        assertFalse(getLooseMatchesFromDb("123123").contains(contactno6));
+
+        assertTrue(getLooseMatchesFromDb("15102849170").contains(contactno7));
+        assertTrue(getLooseMatchesFromDb("5102849170").contains(contactno7));
+        assertTrue(getLooseMatchesFromDb("2849170").contains(contactno7));
+        assertFalse(getLooseMatchesFromDb("849170").contains(contactno7));
+        assertFalse(getLooseMatchesFromDb("10849170").contains(contactno7));
+
+        assertTrue(getLooseMatchesFromDb("1510284917").contains(contactno8));
+        assertTrue(getLooseMatchesFromDb("510284917").contains(contactno8));
+        assertFalse(getLooseMatchesFromDb("2849170").contains(contactno8));
+
+        assertTrue(getLooseMatchesFromDb("8575102849170").contains(contactno9));
+        assertFalse(getLooseMatchesFromDb("5102849170").contains(contactno9));
+        assertFalse(getLooseMatchesFromDb("2849170").contains(contactno9));
+
+//        // If user's region is determined to be not in North America, then the NANP number
+//        // workarounds should not be applied
+//        final SmartDialTrie trieNonNANP = new SmartDialTrie();
+//
+//        trieNonNANP.put(contactno3);
+//        assertTrue(checkContains(trieNonNANP, contactno3, "4151234567"));
+//        assertFalse(checkContains(trieNonNANP, contactno3, "1234567"));
+//
+//        trieNonNANP.put(contactno4);
+//        assertTrue(checkContains(trieNonNANP, contactno4, "15102849170"));
+//        assertFalse(checkContains(trieNonNANP, contactno4, "5102849170"));
+//        assertFalse(checkContains(trieNonNANP, contactno4, "2849170"));
+    }
+
+    // Tests special case handling for non-NANP numbers
+    public void testPutNumbersNonNANP() {
+        SmartDialPrefix.setUserInNanpRegion(false);
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+
+        final ContactNumber contactno0 = constructNewContact(contactCursor, nameCursor,
+                0, "(415)-123-4567", 0, "", "Jason", 0, 0, 0, 0, 0, 0);
+        final ContactNumber contactno1 = constructNewContact(contactCursor, nameCursor,
+                0, "1 510-284-9170", 1, "", "Mike", 0, 0, 0, 0, 0, 0);
+
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(db, contactCursor, Long.valueOf(0));
+        mTestHelper.insertNamePrefixes(db, nameCursor);
+
+        nameCursor.close();
+        contactCursor.close();
+
+        assertTrue(getLooseMatchesFromDb("4151234567").contains(contactno0));
+        assertFalse(getLooseMatchesFromDb("1234567").contains(contactno0));
+
+        assertTrue(getLooseMatchesFromDb("15102849170").contains(contactno1));
+        assertFalse(getLooseMatchesFromDb("5102849170").contains(contactno1));
+        assertFalse(getLooseMatchesFromDb("2849170").contains(contactno1));
+    }
+}
diff --git a/tests/src/com/android/dialer/dialpad/SmartDialCacheTest.java b/tests/src/com/android/dialer/dialpad/SmartDialCacheTest.java
deleted file mode 100644
index 8d96edafc..000000000
--- a/tests/src/com/android/dialer/dialpad/SmartDialCacheTest.java
+++ /dev/null
@@ -1,56 +0,0 @@
-/*
- * Copyright (C) 2013 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.dialer.dialpad;
-
-import android.test.suitebuilder.annotation.SmallTest;
-
-import junit.framework.TestCase;
-
-@SmallTest
-public class SmartDialCacheTest extends TestCase {
-    public void testIsCountryNanp_CaseInsensitive() {
-        assertFalse(SmartDialCache.isCountryNanp(null));
-        assertFalse(SmartDialCache.isCountryNanp("CN"));
-        assertFalse(SmartDialCache.isCountryNanp("HK"));
-        assertFalse(SmartDialCache.isCountryNanp("uk"));
-        assertFalse(SmartDialCache.isCountryNanp("sg"));
-        assertTrue(SmartDialCache.isCountryNanp("US"));
-        assertTrue(SmartDialCache.isCountryNanp("CA"));
-        assertTrue(SmartDialCache.isCountryNanp("AS"));
-        assertTrue(SmartDialCache.isCountryNanp("AI"));
-        assertTrue(SmartDialCache.isCountryNanp("AG"));
-        assertTrue(SmartDialCache.isCountryNanp("BS"));
-        assertTrue(SmartDialCache.isCountryNanp("BB"));
-        assertTrue(SmartDialCache.isCountryNanp("bm"));
-        assertTrue(SmartDialCache.isCountryNanp("vg"));
-        assertTrue(SmartDialCache.isCountryNanp("ky"));
-        assertTrue(SmartDialCache.isCountryNanp("dm"));
-        assertTrue(SmartDialCache.isCountryNanp("do"));
-        assertTrue(SmartDialCache.isCountryNanp("gd"));
-        assertTrue(SmartDialCache.isCountryNanp("gu"));
-        assertTrue(SmartDialCache.isCountryNanp("jm"));
-        assertTrue(SmartDialCache.isCountryNanp("pr"));
-        assertTrue(SmartDialCache.isCountryNanp("ms"));
-        assertTrue(SmartDialCache.isCountryNanp("mp"));
-        assertTrue(SmartDialCache.isCountryNanp("kn"));
-        assertTrue(SmartDialCache.isCountryNanp("lc"));
-        assertTrue(SmartDialCache.isCountryNanp("vc"));
-        assertTrue(SmartDialCache.isCountryNanp("tt"));
-        assertTrue(SmartDialCache.isCountryNanp("tc"));
-        assertTrue(SmartDialCache.isCountryNanp("vi"));
-    }
-}
diff --git a/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java b/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java
index 47edaf371..1e578eee7 100644
--- a/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java
+++ b/tests/src/com/android/dialer/dialpad/SmartDialNameMatcherTest.java
@@ -19,8 +19,10 @@ package com.android.dialer.dialpad;
 import android.test.suitebuilder.annotation.SmallTest;
 import android.test.suitebuilder.annotation.Suppress;
 import android.util.Log;
+import android.test.AndroidTestCase;
 
 import com.android.dialer.dialpad.SmartDialNameMatcher;
+import com.android.dialer.dialpad.SmartDialPrefix;
 
 import java.text.Normalizer;
 import java.util.ArrayList;
@@ -237,8 +239,7 @@ public class SmartDialNameMatcherTest extends TestCase {
     private void checkMatchesNumber(String number, String query, boolean expectedMatches,
             boolean matchNanp, int matchStart, int matchEnd) {
         final SmartDialNameMatcher matcher = new SmartDialNameMatcher(query);
-        final SmartDialMatchPosition pos = matcher.matchesNumber(number, query,
-                matchNanp);
+        final SmartDialMatchPosition pos = matcher.matchesNumber(number, query, matchNanp);
         assertEquals(expectedMatches, pos != null);
         if (expectedMatches) {
             assertEquals("start", matchStart, pos.start);
diff --git a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java
deleted file mode 100644
index f0c4cbb46..000000000
--- a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java
+++ /dev/null
@@ -1,412 +0,0 @@
-/*
- * Copyright (C) 2013 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.dialer.dialpad;
-
-import static com.android.dialer.dialpad.SmartDialCache.ContactNumber;
-
-import com.android.dialer.dialpad.SmartDialTrie.Node;
-import com.android.dialer.dialpad.SmartDialTrie.ParseInfo;
-
-import android.test.suitebuilder.annotation.SmallTest;
-
-import junit.framework.TestCase;
-
-/**
- * To run this test, use the command:
- * adb shell am instrument -w -e class com.android.dialer.dialpad.SmartDialTrieTest /
- * com.android.dialer.tests/android.test.InstrumentationTestRunner
- */
-@SmallTest
-public class SmartDialTrieTest extends TestCase{
-
-    public void testSize() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        trie.put(new ContactNumber(0, "Jason", "0", "0", 1));
-        assertEquals(1, trie.size());
-        trie.put(new ContactNumber(1, "Mary", "0", "1", 2));
-        assertEquals(2, trie.size());
-        trie.put(new ContactNumber(2, "John", "0", "2", 3));
-        assertEquals(3, trie.size());
-    }
-
-    public void testPutForFullName() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber jasonsmith = new ContactNumber(0, "Jason Smith", "0", "0", 1);
-        final ContactNumber jasonsmitt = new ContactNumber(1, "Jason Smitt", "0", "1", 2);
-        trie.put(jasonsmith);
-        trie.put(jasonsmitt);
-        assertTrue(trie.getAllWithPrefix("5276676484").contains(jasonsmith));
-        assertFalse(trie.getAllWithPrefix("5276676484").contains(jasonsmitt));
-
-        assertFalse(trie.getAllWithPrefix("5276676488").contains(jasonsmith));
-        assertTrue(trie.getAllWithPrefix("5276676488").contains(jasonsmitt));
-
-    }
-
-    public void testPutForPartialName() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber maryjane = new ContactNumber(0, "Mary Jane", "0", "0", 1);
-        final ContactNumber sarahsmith = new ContactNumber(1, "Sarah Smith", "0", "1", 2);
-        final ContactNumber jasonsmitt = new ContactNumber(2, "Jason Smitt", "0", "2", 3);
-        trie.put(maryjane);
-        trie.put(sarahsmith);
-        trie.put(jasonsmitt);
-
-        // 6279 corresponds to mary = "Mary Jane" but not "Jason Smitt"
-        assertTrue(checkContains(trie, maryjane, "6279"));
-        assertFalse(checkContains(trie, jasonsmitt, "6279"));
-
-        // 72 corresponds to sa = "Sarah Smith" but not "Jason Smitt" or "Mary Jane"
-        assertFalse(checkContains(trie, maryjane, "72"));
-        assertTrue(checkContains(trie, sarahsmith, "72"));
-        assertFalse(checkContains(trie, jasonsmitt, "72"));
-
-        // 76 corresponds to sm = "Sarah Smith" and "Jason Smitt" but not "Mary Jane"
-        assertFalse(checkContains(trie, maryjane, "76"));
-        assertTrue(checkContains(trie, sarahsmith, "76"));
-        assertTrue(checkContains(trie, jasonsmitt, "76"));
-    }
-
-    public void testPutForNameTokens() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber jasonfwilliams = new ContactNumber(0, "Jason F. Williams", "0", "0", 1);
-        trie.put(jasonfwilliams);
-
-        // 527 corresponds to jas = "Jason"
-        assertTrue(checkContains(trie, jasonfwilliams, "527"));
-        // 945 corresponds to wil = "Wil"
-        assertTrue(checkContains(trie, jasonfwilliams, "945"));
-        // 66 doesn't match
-        assertFalse(checkContains(trie, jasonfwilliams, "66"));
-    }
-
-    public void testPutForInitialMatches() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber martinjuniorharry =
-                new ContactNumber(0, "Martin Jr Harry", "0", "0", 1);
-        trie.put(martinjuniorharry);
-        // 654 corresponds to mjh = "(M)artin (J)r (H)arry"
-        assertTrue(checkContains(trie, martinjuniorharry, "654"));
-        // The reverse (456) does not match (for now)
-        assertFalse(checkContains(trie, martinjuniorharry, "456"));
-        // 6542 corresponds to mjha = "(M)artin (J)r (Ha)rry"
-        assertTrue(checkContains(trie, martinjuniorharry, "6542"));
-        // 542 corresponds to jha = "Martin (J)r (Ha)rry"
-        assertTrue(checkContains(trie, martinjuniorharry, "542"));
-        // 642 corresponds to mha = "(M)artin Jr (Ha)rry"
-        assertTrue(checkContains(trie, martinjuniorharry, "642"));
-        // 6542779 (M)artin (J)r (Harry)
-        assertTrue(checkContains(trie, martinjuniorharry, "6542779"));
-        // 65742779 (M)artin (Jr) (Harry)
-        assertTrue(checkContains(trie, martinjuniorharry, "65742779"));
-        // 542779 Martin (J)r (Harry)
-        assertTrue(checkContains(trie, martinjuniorharry, "542779"));
-        // 547 doesn't match
-        assertFalse(checkContains(trie, martinjuniorharry, "547"));
-        // 655 doesn't match
-        assertFalse(checkContains(trie, martinjuniorharry, "655"));
-        // 653 doesn't match
-        assertFalse(checkContains(trie, martinjuniorharry, "653"));
-        // 6543 doesn't match
-        assertFalse(checkContains(trie, martinjuniorharry, "6543"));
-        // 7(2^3 -1) entries for the name, and 1 for the number
-        assertEquals(8, trie.numEntries());
-    }
-
-    public void testPutForInitialMatchesCombinations() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber alphabet = new ContactNumber(0, "abc def ghi jkl mno pqrs tuv wxyz",
-                "12345678", "1", 2);
-        trie.put(alphabet);
-        assertEquals(20, trie.numEntries());
-        // 8 name entries (abcdefghi..., defghi..., ...)
-        assertTrue(checkContains(trie, alphabet, "22233344455566677778889999"));
-        assertTrue(checkContains(trie, alphabet, "33344455566677778889999"));
-        assertTrue(checkContains(trie, alphabet, "44455566677778889999"));
-        assertTrue(checkContains(trie, alphabet, "55566677778889999"));
-        assertTrue(checkContains(trie, alphabet, "66677778889999"));
-        assertTrue(checkContains(trie, alphabet, "77778889999"));
-        assertTrue(checkContains(trie, alphabet, "8889999"));
-        assertTrue(checkContains(trie, alphabet, "9999"));
-        // 1 number entry
-        assertTrue(checkContains(trie, alphabet, "12345678"));
-        // 11 initial entries (adtw, adw, adt, ad, atw, at, aw, dt, dw, dtw, tw)
-        // 4c2(6) + 4c3(4) + 4c4(1)
-        assertTrue(checkContains(trie, alphabet, "2389999"));
-        assertTrue(checkContains(trie, alphabet, "239999"));
-        assertTrue(checkContains(trie, alphabet, "23888"));
-        assertTrue(checkContains(trie, alphabet, "2333"));
-        assertTrue(checkContains(trie, alphabet, "289999"));
-        assertTrue(checkContains(trie, alphabet, "2888"));
-        assertTrue(checkContains(trie, alphabet, "29999"));
-        assertTrue(checkContains(trie, alphabet, "3888"));
-        assertTrue(checkContains(trie, alphabet, "39999"));
-        assertTrue(checkContains(trie, alphabet, "389999"));
-        assertTrue(checkContains(trie, alphabet, "89999"));
-    }
-
-    public void testCheckLongToken() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber alphabet = new ContactNumber(0, " aaaa bbbb cccc dddd eeee ffff gggg" +
-                " hhhh iiii jjjj kkkk llll mmmm nnnn oooo pppp qqqq rrrr ssss tttt uuuu vvvv " +
-                " wwww xxxx yyyy zzzz", "1", "1", 2);
-        // Make sure the check to prevent overly long tokens from causing an OOM kicks in
-        trie.put(alphabet);
-        assertTrue(checkContains(trie, alphabet, "2222"));
-        // 26 name entries (aaaabbbbcccc...., bbbbccccdddd...., ccccdddd...)
-        // 1 number entry
-        // 11 initial entries 4c2(6) + 4c3(4) + 4c4(1)
-        assertEquals(38, trie.numEntries());
-
-        final ContactNumber alphabet2 = new ContactNumber(0, "aaaabbbbccccddddeeeeffffgggg" +
-                "hhhhiiiijjjjkkkkllllmmmmnnnnooooppppqqqqrrrrssssttttuuuuvvvvwwwwxxxxyyyyzzzz",
-                "1", "1", 2);
-        trie.put(alphabet2);
-        // added one name, and one number entry
-        assertEquals(40, trie.numEntries());
-    }
-
-    public void testParseInfo() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final String name = "Mcdonald Jamie-Cullum";
-        final ParseInfo info = trie.parseToIndexes(name, 2, 2);
-        // Make sure the dash is correctly converted to a separator character
-        for (int i = 0; i < name.length(); i++) {
-            // separators at position 8 and 12
-            if (i == 8 || i == 14) {
-                assertTrue(info.indexes[i] == -1);
-            } else {
-                assertFalse(info.indexes[i] == -1);
-            }
-        }
-        assertEquals(14, info.nthFirstTokenPos);
-        assertEquals(8, info.nthLastTokenPos);
-
-        final String name2 = "aaa bbb ccc ddd eee fff ggg hhh iii jjj kkk";
-        final ParseInfo info2 = trie.parseToIndexes(name2, 2, 2);
-        assertEquals(7, info2.nthFirstTokenPos);
-        assertEquals(35, info2.nthLastTokenPos);
-
-        final String name3 = "this  is- a,test    name";
-        final ParseInfo info3 = trie.parseToIndexes(name3, 3, 3);
-        assertEquals(11, info3.nthFirstTokenPos);
-        assertEquals(8, info3.nthLastTokenPos);
-
-        final String name4 = "M c-Donald James";
-        final ParseInfo info4 = trie.parseToIndexes(name4, 2, 3);
-        assertEquals(3, info4.nthFirstTokenPos);
-        assertEquals(1, info4.nthLastTokenPos);
-
-        final String name5 = "   Aa'Bb    c    dddd  e'e";
-        final ParseInfo info5 = trie.parseToIndexes(name5, 4, 4);
-        assertEquals(21, info5.nthFirstTokenPos);
-        assertEquals(8, info5.nthLastTokenPos);
-    }
-
-    public void testAccentedCharacters() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber reenee = new ContactNumber(0, "Reenée", "0", "0", 1);
-        final ContactNumber bronte = new ContactNumber(2, "Brontë", "0", "1", 2);
-        trie.put(reenee);
-        trie.put(bronte);
-        assertTrue(checkContains(trie, reenee, "733633"));
-        assertTrue(checkContains(trie, bronte, "276683"));
-    }
-
-    public void testNumbersInName() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber contact = new ContactNumber(0, "12345678", "0", "0", 1);
-        final ContactNumber teacher = new ContactNumber(1, "1st Grade Teacher", "0", "1", 2);
-        trie.put(contact);
-        trie.put(teacher);
-        assertTrue(checkContains(trie, contact, "12345678"));
-        // (1st Grade) Teacher
-        assertTrue(checkContains(trie, teacher, "17847233"));
-        // (1)st (G)rade (Tea)cher
-        assertTrue(checkContains(trie, teacher, "14832"));
-    }
-
-    public void testPutForNumbers() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber contactno1 = new ContactNumber(0, "James", "510-527-2357", "0", 1);
-        trie.put(contactno1);
-        final ContactNumber contactno2 = new ContactNumber(0, "James", "77212862357", "0", 1);
-        trie.put(contactno2);
-        final ContactNumber contactno3 = new ContactNumber(0, "James", "+13684976334", "0", 1);
-        trie.put(contactno3);
-        // all phone numbers belonging to the contact should correspond to it
-        assertTrue(checkContains(trie, contactno1, "510"));
-        assertFalse(checkContains(trie, contactno1, "511"));
-        assertTrue(checkContains(trie, contactno2, "77212862357"));
-        assertFalse(checkContains(trie, contactno2, "77212862356"));
-        assertTrue(checkContains(trie, contactno3, "1368"));
-        assertFalse(checkContains(trie, contactno3, "1367"));
-
-    }
-
-    public void testPutNumbersCountryCode() {
-        final SmartDialTrie trie = new SmartDialTrie();
-        final ContactNumber contactno1 = new ContactNumber(0, "James", "+13684976334", "0", 1);
-        trie.put(contactno1);
-
-        // all phone numbers belonging to the contact should correspond to it
-        assertTrue(checkContains(trie, contactno1, "1368"));
-        assertTrue(checkContains(trie, contactno1, "368497"));
-        assertFalse(checkContains(trie, contactno1, "2368497"));
-
-        final ContactNumber contactno2 = new ContactNumber(0, "Jason", "+65 9177-6930", "0", 1);
-        trie.put(contactno2);
-
-        assertTrue(checkContains(trie, contactno2, "6591776930"));
-        assertTrue(checkContains(trie, contactno2, "91776930"));
-        assertFalse(checkContains(trie, contactno2, "591776930"));
-
-        final ContactNumber contactno3 = new ContactNumber(0, "Mike", "+85212345678", "0", 1);
-        trie.put(contactno3);
-        assertTrue(checkContains(trie, contactno3, "85212345678"));
-        assertTrue(checkContains(trie, contactno3, "12345678"));
-        assertFalse(checkContains(trie, contactno2, "5212345678"));
-
-        // Invalid country code, don't try to parse it
-        final ContactNumber contactno4 = new ContactNumber(0, "Invalid", "+85112345678", "0", 1);
-        trie.put(contactno4);
-        assertTrue(checkContains(trie, contactno4, "85112345678"));
-        assertFalse(checkContains(trie, contactno4, "12345678"));
-
-        final ContactNumber contactno5 = new ContactNumber(0, "Invalid", "+852", "0", 1);
-        // Shouldn't crash
-        trie.put(contactno5);
-    }
-
-    // Tests special case handling for NANP numbers
-    public void testPutNumbersNANP() {
-        final SmartDialTrie trie = new SmartDialTrie(true /* formatNanp */);
-        // Unformatted number with 1 prefix
-        final ContactNumber contactno1 = new ContactNumber(0, "James", "16503337596", "0", 1);
-        trie.put(contactno1);
-
-        assertTrue(checkContains(trie, contactno1, "16503337596"));
-        assertTrue(checkContains(trie, contactno1, "6503337596"));
-        assertTrue(checkContains(trie, contactno1, "3337596"));
-
-        // Number with seperators
-        final ContactNumber contactno2 = new ContactNumber(0, "Michael", "5109921234", "0", 1);
-        trie.put(contactno2);
-        assertTrue(checkContains(trie, contactno2, "5109921234"));
-        assertTrue(checkContains(trie, contactno2, "9921234"));
-
-        // Number with area code only + separators
-        final ContactNumber contactno3 = new ContactNumber(0, "Jason", "(415)-123-4567", "0", 1);
-        trie.put(contactno3);
-        assertTrue(checkContains(trie, contactno3, "4151234567"));
-        assertTrue(checkContains(trie, contactno3, "1234567"));
-
-        // Number without +1 prefix but is a NANP number
-        final ContactNumber contactno4 = new ContactNumber(0, "Mike", "1 510-284-9170", "0", 1);
-        trie.put(contactno4);
-        assertTrue(checkContains(trie, contactno4, "15102849170"));
-        assertTrue(checkContains(trie, contactno4, "5102849170"));
-        assertTrue(checkContains(trie, contactno4, "2849170"));
-
-        // Invalid number(has 1 prefix, but is only 10 characters long)
-        final ContactNumber contactno5 = new ContactNumber(0, "Invalid", "1-415-123-123", "0", 1);
-        trie.put(contactno5);
-        // It should still be inserted as is
-        assertTrue(checkContains(trie, contactno5, "1415123123"));
-        // But the NANP special case handling should not work
-        assertFalse(checkContains(trie, contactno5, "415123123"));
-        assertFalse(checkContains(trie, contactno5, "123123"));
-
-        // Invalid number(only 9 characters long)
-        final ContactNumber contactno6 = new ContactNumber(0, "Invalid2", "415-123-123", "0", 1);
-        trie.put(contactno6);
-        // It should still be inserted as is
-        assertTrue(checkContains(trie, contactno6, "415123123"));
-        // But the NANP special case handling should not work
-        assertFalse(checkContains(trie, contactno6, "123123"));
-
-        // Number with +1 prefix and is a NANP number
-        final ContactNumber contactno7 = new ContactNumber(0, "Mike", "+1-510-284-9170", "0", 1);
-        trie.put(contactno7);
-        assertTrue(checkContains(trie, contactno7, "15102849170"));
-        assertTrue(checkContains(trie, contactno7, "5102849170"));
-        assertTrue(checkContains(trie, contactno7, "2849170"));
-        assertFalse(checkContains(trie, contactno7, "849170"));
-        assertFalse(checkContains(trie, contactno7, "10849170"));
-
-        // Number with +1 prefix but is an invalid NANP number
-        final ContactNumber contactno8 = new ContactNumber(0, "Invalid", "+1-510-284-917", "0", 1);
-        trie.put(contactno8);
-        assertTrue(checkContains(trie, contactno8, "1510284917"));
-        assertTrue(checkContains(trie, contactno8, "510284917"));
-        assertFalse(checkContains(trie, contactno8, "2849170"));
-
-        // Number with invalid country code prefix
-        final ContactNumber contactno9 = new ContactNumber(0, "Inv", "+857-510-284-9170", "0", 1);
-        trie.put(contactno9);
-        assertTrue(checkContains(trie, contactno9, "8575102849170"));
-        assertFalse(checkContains(trie, contactno9, "5102849170"));
-        assertFalse(checkContains(trie, contactno9, "2849170"));
-
-        // If user's region is determined to be not in North America, then the NANP number
-        // workarounds should not be applied
-        final SmartDialTrie trieNonNANP = new SmartDialTrie();
-
-        trieNonNANP.put(contactno3);
-        assertTrue(checkContains(trieNonNANP, contactno3, "4151234567"));
-        assertFalse(checkContains(trieNonNANP, contactno3, "1234567"));
-
-        trieNonNANP.put(contactno4);
-        assertTrue(checkContains(trieNonNANP, contactno4, "15102849170"));
-        assertFalse(checkContains(trieNonNANP, contactno4, "5102849170"));
-        assertFalse(checkContains(trieNonNANP, contactno4, "2849170"));
-    }
-
-    public void testNodeConstructor() {
-        final Node n = new Node();
-        // Node member variables should not be initialized by default at construction to reduce
-        // unnecessary memory usage
-        assertEquals(-1, n.getChildrenSize());
-        assertNull(n.getChild(5, false));
-        assertNull(n.getChild(0, false));
-    }
-
-    public void testNodeGetChild() {
-        final Node n = new Node();
-        // A node shouldn't contain children until getChild(index, true) is called
-        assertEquals(-1, n.getChildrenSize());
-        final Node child = n.getChild(1, true);
-        // A node should always have 10 children once the child array is created
-        assertEquals(10, n.getChildrenSize());
-        // getChild(index, true) should never return null
-        assertNotNull(child);
-    }
-
-    public void testNodeAddContact() {
-        final Node n = new Node();
-        assertNull(n.getContents());
-        final ContactNumber contact = new ContactNumber(0, "James", "510-527-2357", "0", 1);
-        final ContactNumber contactNotIn = new ContactNumber(2, "Jason Smitt", "0", "2", 3);
-        n.add(contact);
-        assertTrue(n.getContents().contains(contact));
-        assertFalse(n.getContents().contains(contactNotIn));
-    }
-
-    private boolean checkContains(SmartDialTrie trie, ContactNumber contact, CharSequence prefix) {
-        return trie.getAllWithPrefix(prefix).contains(contact);
-    }
-}