Use ICU JNI wrappers for phonebook labels

Switch from using native code registered as sqlite callbacks to using
JNI wrappers for accessing ICU AlphabeticIndex. Stop using specialized
sort keys for Simplified Chinese because ICU code can correctly label
the characters directly.

Bug:
Change-Id: I0568b3a406495c147c7b9b3e72835d11d93f9d16
diff --git a/src/com/android/providers/contacts/ContactLocaleUtils.java b/src/com/android/providers/contacts/ContactLocaleUtils.java
index 0e7b292..0284c01 100644
--- a/src/com/android/providers/contacts/ContactLocaleUtils.java
+++ b/src/com/android/providers/contacts/ContactLocaleUtils.java
@@ -17,78 +17,263 @@
 package com.android.providers.contacts;
 
 import android.provider.ContactsContract.FullNameStyle;
-import android.util.SparseArray;
+import android.util.Log;
 
 import com.android.providers.contacts.HanziToPinyin.Token;
 
+import java.lang.Character.UnicodeBlock;
+import java.util.Arrays;
 import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.List;
 import java.util.Locale;
+import java.util.Map;
+import java.util.Set;
+
+import libcore.icu.AlphabeticIndex;
 
 /**
- * This utility class provides customized sort key and name lookup key according the locale.
+ * This utility class provides specialized handling for locale specific
+ * information: labels, name lookup keys.
  */
 public class ContactLocaleUtils {
+    public static final String TAG = "ContactLocale";
 
     /**
-     * This class is the default implementation.
-     * <p>
-     * It should be the base class for other locales' implementation.
+     * This class is the default implementation and should be the base class
+     * for other locales.
+     *
+     * sortKey: same as name
+     * nameLookupKeys: none
+     * labels: uses ICU AlphabeticIndex for labels and extends by labeling
+     *     phone numbers "#".  Eg English labels are: [A-Z], #, " "
      */
-    public class ContactLocaleUtilsBase {
-        public String getSortKey(String displayName) {
-            return displayName;
+    private static class ContactLocaleUtilsBase {
+        private static final String EMPTY_STRING = "";
+        private static final String NUMBER_STRING = "#";
+
+        protected final AlphabeticIndex mAlphabeticIndex;
+        private final int mAlphabeticIndexBucketCount;
+        private final int mNumberBucketIndex;
+
+        public ContactLocaleUtilsBase(Locale locale) {
+            mAlphabeticIndex = new AlphabeticIndex(locale);
+            mAlphabeticIndex.addLabels(Locale.US);
+            // Force creation of lazy-init data structures.
+            mAlphabeticIndexBucketCount = mAlphabeticIndex.getBucketCount();
+            mNumberBucketIndex = mAlphabeticIndexBucketCount - 1;
         }
+
+        public String getSortKey(String name) {
+            return name;
+        }
+
+        /**
+         * Returns the bucket index for the specified string. AlphabeticIndex
+         * sorts strings into buckets numbered in order from 0 to N, where the
+         * exact value of N depends on how many representative index labels are
+         * used in a particular locale. This routine adds one additional bucket
+         * for phone numbers. It attempts to detect phone numbers and shifts
+         * the bucket indexes returned by AlphabeticIndex in order to make room
+         * for the new # bucket, so the returned range becomes 0 to N+1.
+         */
+        public int getBucketIndex(String name) {
+            boolean prefixIsNumeric = false;
+            final int length = name.length();
+            int offset = 0;
+            while (offset < length) {
+                int codePoint = Character.codePointAt(name, offset);
+                // Ignore standard phone number separators and identify any
+                // string that otherwise starts with a number.
+                if (Character.isDigit(codePoint)) {
+                    prefixIsNumeric = true;
+                    break;
+                } else if (!Character.isSpaceChar(codePoint) &&
+                           codePoint != '+' && codePoint != '(' &&
+                           codePoint != ')' && codePoint != '.' &&
+                           codePoint != '-' && codePoint != '#') {
+                    break;
+                }
+                offset += Character.charCount(codePoint);
+            }
+            if (prefixIsNumeric) {
+                return mNumberBucketIndex;
+            }
+
+            final int bucket = mAlphabeticIndex.getBucketIndex(name);
+            if (bucket < 0) {
+                return -1;
+            }
+            if (bucket >= mNumberBucketIndex) {
+                return bucket + 1;
+            }
+            return bucket;
+        }
+
+        /**
+         * Returns the number of buckets in use (one more than AlphabeticIndex
+         * uses, because this class adds a bucket for phone numbers).
+         */
+        public int getBucketCount() {
+            return mAlphabeticIndexBucketCount + 1;
+        }
+
+        /**
+         * Returns the label for the specified bucket index if a valid index,
+         * otherwise returns an empty string. '#' is returned for the phone
+         * number bucket; for all others, the AlphabeticIndex label is returned.
+         */
+        public String getBucketLabel(int bucketIndex) {
+            if (bucketIndex < 0 || bucketIndex >= getBucketCount()) {
+                return EMPTY_STRING;
+            } else if (bucketIndex == mNumberBucketIndex) {
+                return NUMBER_STRING;
+            } else if (bucketIndex > mNumberBucketIndex) {
+                --bucketIndex;
+            }
+            return mAlphabeticIndex.getBucketLabel(bucketIndex);
+        }
+
         @SuppressWarnings("unused")
         public Iterator<String> getNameLookupKeys(String name) {
             return null;
         }
+
+        public ArrayList<String> getLabels() {
+            final int bucketCount = getBucketCount();
+            final ArrayList<String> labels = new ArrayList<String>(bucketCount);
+            for(int i = 0; i < bucketCount; ++i) {
+                labels.add(getBucketLabel(i));
+            }
+            return labels;
+        }
     }
 
     /**
-     * The classes to generate the Chinese style sort and search keys.
-     * <p>
-     * The sorting key is generated as each Chinese character' pinyin proceeding with
-     * space and character itself. If the character's pinyin unable to find, the character
-     * itself will be used.
-     * <p>
-     * The below additional name lookup keys will be generated.
-     * a. Chinese character's pinyin and pinyin's initial character.
-     * b. Latin word and the initial character for Latin word.
-     * The name lookup keys are generated to make sure the name can be found by from any
-     * initial character.
+     * Japanese specific locale overrides.
+     *
+     * sortKey: unchanged (same as name)
+     * nameLookupKeys: unchanged (none)
+     * labels: extends default labels by labeling unlabeled CJ characters
+     *     with the Japanese character 他 ("misc"). Japanese labels are:
+     *     あ, か, さ, た, な, は, ま, や, ら, わ, 他, [A-Z], #, " "
      */
-    private class ChineseContactUtils extends ContactLocaleUtilsBase {
+    private static class JapaneseContactUtils extends ContactLocaleUtilsBase {
+        // \u4ed6 is Japanese character 他 ("misc")
+        private static final String JAPANESE_MISC_LABEL = "\u4ed6";
+        private final int mMiscBucketIndex;
+
+        public JapaneseContactUtils(Locale locale) {
+            super(locale);
+            // Determine which bucket AlphabeticIndex is lumping unclassified
+            // Japanese characters into by looking up the bucket index for
+            // a representative Kanji/CJK unified ideograph (\u65e5 is the
+            // character '日').
+            mMiscBucketIndex = super.getBucketIndex("\u65e5");
+        }
+
+        // Set of UnicodeBlocks for unified CJK (Chinese) characters and
+        // Japanese characters. This includes all code blocks that might
+        // contain a character used in Japanese (which is why unified CJK
+        // blocks are included but Korean Hangul and jamo are not).
+        private static final Set<Character.UnicodeBlock> CJ_BLOCKS;
+        static {
+            Set<UnicodeBlock> set = new HashSet<UnicodeBlock>();
+            set.add(UnicodeBlock.HIRAGANA);
+            set.add(UnicodeBlock.KATAKANA);
+            set.add(UnicodeBlock.KATAKANA_PHONETIC_EXTENSIONS);
+            set.add(UnicodeBlock.HALFWIDTH_AND_FULLWIDTH_FORMS);
+            set.add(UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS);
+            set.add(UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS_EXTENSION_A);
+            set.add(UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS_EXTENSION_B);
+            set.add(UnicodeBlock.CJK_SYMBOLS_AND_PUNCTUATION);
+            set.add(UnicodeBlock.CJK_RADICALS_SUPPLEMENT);
+            set.add(UnicodeBlock.CJK_COMPATIBILITY);
+            set.add(UnicodeBlock.CJK_COMPATIBILITY_FORMS);
+            set.add(UnicodeBlock.CJK_COMPATIBILITY_IDEOGRAPHS);
+            set.add(UnicodeBlock.CJK_COMPATIBILITY_IDEOGRAPHS_SUPPLEMENT);
+            CJ_BLOCKS = Collections.unmodifiableSet(set);
+        }
+
+        /**
+         * Helper routine to identify unlabeled Chinese or Japanese characters
+         * to put in a 'misc' bucket.
+         *
+         * @return true if the specified Unicode code point is Chinese or
+         *              Japanese
+         */
+        private static boolean isChineseOrJapanese(int codePoint) {
+            return CJ_BLOCKS.contains(UnicodeBlock.of(codePoint));
+        }
+
+        /**
+         * Returns the bucket index for the specified string. Adds an
+         * additional 'misc' bucket for Kanji characters to the base class set.
+         */
         @Override
-        public String getSortKey(String displayName) {
-            ArrayList<Token> tokens = HanziToPinyin.getInstance().get(displayName);
-            if (tokens != null && tokens.size() > 0) {
-                StringBuilder sb = new StringBuilder();
-                for (Token token : tokens) {
-                    // Put Chinese character's pinyin, then proceed with the
-                    // character itself.
-                    if (Token.PINYIN == token.type) {
-                        if (sb.length() > 0) {
-                            sb.append(' ');
-                        }
-                        sb.append(token.target);
-                        sb.append(' ');
-                        sb.append(token.source);
-                    } else {
-                        if (sb.length() > 0) {
-                            sb.append(' ');
-                        }
-                        sb.append(token.source);
-                    }
-                }
-                return sb.toString();
+        public int getBucketIndex(String name) {
+            final int bucketIndex = super.getBucketIndex(name);
+            if ((bucketIndex == mMiscBucketIndex &&
+                 !isChineseOrJapanese(Character.codePointAt(name, 0))) ||
+                bucketIndex > mMiscBucketIndex) {
+                return bucketIndex + 1;
             }
-            return super.getSortKey(displayName);
+            return bucketIndex;
+        }
+
+        /**
+         * Returns the number of buckets in use (one more than the base class
+         * uses, because this class adds a bucket for Kanji).
+         */
+        @Override
+        public int getBucketCount() {
+            return super.getBucketCount() + 1;
+        }
+
+        /**
+         * Returns the label for the specified bucket index if a valid index,
+         * otherwise returns an empty string. '他' is returned for unclassified
+         * Kanji; for all others, the label determined by the base class is
+         * returned.
+         */
+        @Override
+        public String getBucketLabel(int bucketIndex) {
+            if (bucketIndex == mMiscBucketIndex) {
+                return JAPANESE_MISC_LABEL;
+            } else if (bucketIndex > mMiscBucketIndex) {
+                --bucketIndex;
+            }
+            return super.getBucketLabel(bucketIndex);
+        }
+    }
+
+    /**
+     * Chinese specific locale overrides. Uses ICU Transliterator for
+     * generating pinyin transliteration.
+     *
+     * sortKey: unchanged (same as name)
+     * nameLookupKeys: adds additional name lookup keys
+     *     - Chinese character's pinyin and pinyin's initial character.
+     *     - Latin word and initial character.
+     * labels: unchanged
+     *     Simplified Chinese labels are the same as English: [A-Z], #, " "
+     *     Traditional Chinese labels are stroke count, then English labels:
+     *         [1-18], [A-Z], #, " "
+     */
+    private static class ChineseContactUtils extends ContactLocaleUtilsBase {
+        public ChineseContactUtils(Locale locale) {
+            super(locale);
         }
 
         @Override
         public Iterator<String> getNameLookupKeys(String name) {
+            return getPinyinNameLookupKeys(name);
+        }
+
+        public static Iterator<String> getPinyinNameLookupKeys(String name) {
             // TODO : Reduce the object allocation.
             HashSet<String> keys = new HashSet<String>();
             ArrayList<Token> tokens = HanziToPinyin.getInstance().get(name);
@@ -96,9 +281,9 @@
             final StringBuilder keyPinyin = new StringBuilder();
             final StringBuilder keyInitial = new StringBuilder();
             // There is no space among the Chinese Characters, the variant name
-            // lookup key wouldn't work for Chinese. The keyOrignal is used to
+            // lookup key wouldn't work for Chinese. The keyOriginal is used to
             // build the lookup keys for itself.
-            final StringBuilder keyOrignal = new StringBuilder();
+            final StringBuilder keyOriginal = new StringBuilder();
             for (int i = tokenCount - 1; i >= 0; i--) {
                 final Token token = tokens.get(i);
                 if (Token.PINYIN == token.type) {
@@ -109,14 +294,14 @@
                     if (keyPinyin.length() > 0) {
                         keyPinyin.insert(0, ' ');
                     }
-                    if (keyOrignal.length() > 0) {
-                        keyOrignal.insert(0, ' ');
+                    if (keyOriginal.length() > 0) {
+                        keyOriginal.insert(0, ' ');
                     }
                     keyPinyin.insert(0, token.source);
                     keyInitial.insert(0, token.source.charAt(0));
                 }
-                keyOrignal.insert(0, token.source);
-                keys.add(keyOrignal.toString());
+                keyOriginal.insert(0, token.source);
+                keys.add(keyOriginal.toString());
                 keys.add(keyPinyin.toString());
                 keys.add(keyInitial.toString());
             }
@@ -124,89 +309,147 @@
         }
     }
 
+    /**
+     * Traditional Chinese specific locale overrides. Rewrites ICU labels
+     * to correct ICU 4.9 labels.
+     *
+     * TODO: remove once ICU is upgraded to 5.0 and labels are fixed
+     *
+     * sortKey: unchanged from base class (same as name)
+     * nameLookupKeys: unchanged from ChineseContactUtils
+     * labels: unchanged
+     *     Simplified Chinese labels are the same as English: [A-Z], #, " "
+     *     Traditional Chinese labels are stroke count, then English labels:
+     *         [1-18]劃, [A-Z], #, " "
+     */
+    private static class TraditionalChineseContactUtils
+        extends ChineseContactUtils {
+        // Remap ICU 4.9 labels to desired values
+        private static final Map<String, String> labelMap;
+        static {
+            Map<String, String> map = new HashMap<String, String>();
+            final List<String> oldLabels =
+                Arrays.asList("\u4E00", "\u4E01", "\u4E08", "\u4E0D",
+                              "\u4E14", "\u4E1E", "\u4E32", "\u4E26",
+                              "\u4EAD", "\u4E58", "\u4E7E", "\u5080",
+                              "\u4E82", "\u50CE", "\u50F5", "\u5110",
+                              "\u511F", "\u53E2", "\u5133", "\u56B4",
+                              "\u5137", "\u513B", "\u56CC", "\u56D1",
+                              "\u5EF3");
+            int strokeCount = 1;
+            for(String oldLabel : oldLabels) {
+                String newLabel = "" + strokeCount + "\u5283";
+                map.put(oldLabel, newLabel);
+                ++strokeCount;
+            }
+            labelMap = Collections.unmodifiableMap(map);
+        }
+
+        public TraditionalChineseContactUtils(Locale locale) {
+            super(locale);
+        }
+
+        @Override
+        public String getBucketLabel(int bucketIndex) {
+            final String label = super.getBucketLabel(bucketIndex);
+            final String remappedLabel = labelMap.get(label);
+            return remappedLabel != null ? remappedLabel : label;
+        }
+    }
+
     private static final String CHINESE_LANGUAGE = Locale.CHINESE.getLanguage().toLowerCase();
     private static final String JAPANESE_LANGUAGE = Locale.JAPANESE.getLanguage().toLowerCase();
     private static final String KOREAN_LANGUAGE = Locale.KOREAN.getLanguage().toLowerCase();
 
     private static ContactLocaleUtils sSingleton;
-    private final SparseArray<ContactLocaleUtilsBase> mUtils =
-            new SparseArray<ContactLocaleUtilsBase>();
 
-    private final ContactLocaleUtilsBase mBase = new ContactLocaleUtilsBase();
+    private final Locale mLocale;
+    private final String mLanguage;
+    private final ContactLocaleUtilsBase mUtils;
 
-    private String mLanguage;
-
-    private ContactLocaleUtils() {
-        setLocale(null);
-    }
-
-    public void setLocale(Locale currentLocale) {
-        if (currentLocale == null) {
-            mLanguage = Locale.getDefault().getLanguage().toLowerCase();
+    private ContactLocaleUtils(Locale locale) {
+        if (locale == null) {
+            mLocale = Locale.getDefault();
         } else {
-            mLanguage = currentLocale.getLanguage().toLowerCase();
+            mLocale = locale;
         }
-    }
-
-    public String getSortKey(String displayName, int nameStyle) {
-        return getForSort(Integer.valueOf(nameStyle)).getSortKey(displayName);
-    }
-
-    public Iterator<String> getNameLookupKeys(String name, int nameStyle) {
-        return getForNameLookup(Integer.valueOf(nameStyle)).getNameLookupKeys(name);
-    }
-
-    /**
-     *  Determine which utility should be used for generating NameLookupKey.
-     *  <p>
-     *  a. For Western style name, if the current language is Chinese, the
-     *     ChineseContactUtils should be used.
-     *  b. For Chinese and CJK style name if current language is neither Japanese or Korean,
-     *     the ChineseContactUtils should be used.
-     */
-    private ContactLocaleUtilsBase getForNameLookup(Integer nameStyle) {
-        int nameStyleInt = nameStyle.intValue();
-        Integer adjustedUtil = Integer.valueOf(getAdjustedStyle(nameStyleInt));
-        if (CHINESE_LANGUAGE.equals(mLanguage) && nameStyleInt == FullNameStyle.WESTERN) {
-            adjustedUtil = Integer.valueOf(FullNameStyle.CHINESE);
-        }
-        return get(adjustedUtil);
-    }
-
-    private synchronized ContactLocaleUtilsBase get(Integer nameStyle) {
-        ContactLocaleUtilsBase utils = mUtils.get(nameStyle);
-        if (utils == null) {
-            if (nameStyle.intValue() == FullNameStyle.CHINESE) {
-                utils = new ChineseContactUtils();
-                mUtils.put(nameStyle, utils);
+        mLanguage = mLocale.getLanguage().toLowerCase();
+        if (mLanguage.equals(JAPANESE_LANGUAGE)) {
+            mUtils = new JapaneseContactUtils(mLocale);
+        } else if (mLanguage.equals(CHINESE_LANGUAGE)) {
+            if (isLocale(Locale.TRADITIONAL_CHINESE)) {
+                mUtils = new TraditionalChineseContactUtils(mLocale);
+            } else {
+                mUtils = new ChineseContactUtils(mLocale);
             }
+        } else {
+            mUtils = new ContactLocaleUtilsBase(mLocale);
         }
-        return (utils == null) ? mBase : utils;
+        Log.i(TAG, "AddressBook Labels [" + mLocale.toString() + "]: "
+              + getLabels().toString());
     }
 
-    /**
-     *  Determine the which utility should be used for generating sort key.
-     *  <p>
-     *  For Chinese and CJK style name if current language is neither Japanese or Korean,
-     *  the ChineseContactUtils should be used.
-     */
-    private ContactLocaleUtilsBase getForSort(Integer nameStyle) {
-        return get(Integer.valueOf(getAdjustedStyle(nameStyle.intValue())));
+    public boolean isLocale(Locale locale) {
+        return mLocale.equals(locale);
     }
 
-    public static synchronized ContactLocaleUtils getIntance() {
+    public static synchronized ContactLocaleUtils getInstance() {
         if (sSingleton == null) {
-            sSingleton = new ContactLocaleUtils();
+            sSingleton = new ContactLocaleUtils(null);
         }
         return sSingleton;
     }
 
-    private int getAdjustedStyle(int nameStyle) {
-        if (nameStyle == FullNameStyle.CJK  && !JAPANESE_LANGUAGE.equals(mLanguage) &&
-                !KOREAN_LANGUAGE.equals(mLanguage)) {
-            return FullNameStyle.CHINESE;
-        } else {
-            return nameStyle;
+    public static synchronized void setLocale(Locale locale) {
+        if (sSingleton == null || !sSingleton.isLocale(locale)) {
+            sSingleton = new ContactLocaleUtils(locale);
         }
     }
+
+    public String getSortKey(String name, int nameStyle) {
+        return mUtils.getSortKey(name);
+    }
+
+    public int getBucketIndex(String name) {
+        return mUtils.getBucketIndex(name);
+    }
+
+    public int getBucketCount() {
+        return mUtils.getBucketCount();
+    }
+
+    public String getBucketLabel(int bucketIndex) {
+        return mUtils.getBucketLabel(bucketIndex);
+    }
+
+    public String getLabel(String name) {
+        return getBucketLabel(getBucketIndex(name));
+    }
+
+    public ArrayList<String> getLabels() {
+        return mUtils.getLabels();
+    }
+
+    /**
+     *  Determine which utility should be used for generating NameLookupKey.
+     *  (ie, whether we generate Pinyin lookup keys or not)
+     *
+     *  a. For unclassified CJK name, if current locale language is neither
+     *     Japanese nor Korean, use ChineseContactUtils.
+     *  b. If we're sure this is a Chinese name, always use ChineseContactUtils.
+     *  c. Otherwise, use whichever ContactUtils are appropriate for the locale
+     *     (so, Western names in Chinese locale will use ChineseContactUtils)
+     */
+    public Iterator<String> getNameLookupKeys(String name, int nameStyle) {
+        if (nameStyle == FullNameStyle.CJK &&
+            !JAPANESE_LANGUAGE.equals(mLanguage) &&
+            !KOREAN_LANGUAGE.equals(mLanguage)) {
+            return ChineseContactUtils.getPinyinNameLookupKeys(name);
+        }
+        if (nameStyle == FullNameStyle.CHINESE) {
+            return ChineseContactUtils.getPinyinNameLookupKeys(name);
+        }
+        return mUtils.getNameLookupKeys(name);
+    }
+
 }
diff --git a/src/com/android/providers/contacts/ContactsDatabaseHelper.java b/src/com/android/providers/contacts/ContactsDatabaseHelper.java
index 478cd68..6cd0a70 100644
--- a/src/com/android/providers/contacts/ContactsDatabaseHelper.java
+++ b/src/com/android/providers/contacts/ContactsDatabaseHelper.java
@@ -107,7 +107,7 @@
      *   700-799 Jelly Bean
      * </pre>
      */
-    static final int DATABASE_VERSION = 706;
+    static final int DATABASE_VERSION = 707;
 
     private static final String DATABASE_NAME = "contacts2.db";
     private static final String DATABASE_PRESENCE = "presence_db";
@@ -359,6 +359,10 @@
                 + Contacts.SEND_TO_VOICEMAIL;
         public static final String CONCRETE_LOOKUP_KEY = Tables.CONTACTS + "."
                 + Contacts.LOOKUP_KEY;
+        public static final String PHONEBOOK_LABEL_PRIMARY = "phonebook_label";
+        public static final String PHONEBOOK_BUCKET_PRIMARY = "phonebook_bucket";
+        public static final String PHONEBOOK_LABEL_ALTERNATIVE = "phonebook_label_alt";
+        public static final String PHONEBOOK_BUCKET_ALTERNATIVE = "phonebook_bucket_alt";
     }
 
     public interface RawContactsColumns {
@@ -403,7 +407,15 @@
         public static final String CONCRETE_CONTACT_ID =
                 Tables.RAW_CONTACTS + "." + RawContacts.CONTACT_ID;
         public static final String CONCRETE_NAME_VERIFIED =
-                Tables.RAW_CONTACTS + "." + RawContacts.NAME_VERIFIED;
+            Tables.RAW_CONTACTS + "." + RawContacts.NAME_VERIFIED;
+        public static final String PHONEBOOK_LABEL_PRIMARY =
+            ContactsColumns.PHONEBOOK_LABEL_PRIMARY;
+        public static final String PHONEBOOK_BUCKET_PRIMARY =
+            ContactsColumns.PHONEBOOK_BUCKET_PRIMARY;
+        public static final String PHONEBOOK_LABEL_ALTERNATIVE =
+            ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE;
+        public static final String PHONEBOOK_BUCKET_ALTERNATIVE =
+            ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE;
     }
 
     public interface ViewRawContactsColumns {
@@ -983,8 +995,12 @@
                 RawContacts.PHONETIC_NAME_STYLE + " TEXT," +
                 RawContacts.SORT_KEY_PRIMARY + " TEXT COLLATE " +
                         ContactsProvider2.PHONEBOOK_COLLATOR_NAME + "," +
+                RawContactsColumns.PHONEBOOK_LABEL_PRIMARY + " TEXT," +
+                RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY + " INTEGER," +
                 RawContacts.SORT_KEY_ALTERNATIVE + " TEXT COLLATE " +
                         ContactsProvider2.PHONEBOOK_COLLATOR_NAME + "," +
+                RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE + " TEXT," +
+                RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + " INTEGER," +
                 RawContacts.NAME_VERIFIED + " INTEGER NOT NULL DEFAULT 0," +
                 RawContacts.SYNC1 + " TEXT, " +
                 RawContacts.SYNC2 + " TEXT, " +
@@ -1612,8 +1628,16 @@
                         + " AS " + Contacts.PHONETIC_NAME_STYLE + ", "
                 + "name_raw_contact." + RawContacts.SORT_KEY_PRIMARY
                         + " AS " + Contacts.SORT_KEY_PRIMARY + ", "
+                + "name_raw_contact." + RawContactsColumns.PHONEBOOK_LABEL_PRIMARY
+                        + " AS " + ContactsColumns.PHONEBOOK_LABEL_PRIMARY + ", "
+                + "name_raw_contact." + RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY
+                        + " AS " + ContactsColumns.PHONEBOOK_BUCKET_PRIMARY + ", "
                 + "name_raw_contact." + RawContacts.SORT_KEY_ALTERNATIVE
-                        + " AS " + Contacts.SORT_KEY_ALTERNATIVE;
+                        + " AS " + Contacts.SORT_KEY_ALTERNATIVE + ", "
+                + "name_raw_contact." + RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE
+                        + " AS " + ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE + ", "
+                + "name_raw_contact." + RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE
+                        + " AS " + ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE;
 
         String dataSelect = "SELECT "
                 + DataColumns.CONCRETE_ID + " AS " + Data._ID + ","
@@ -1670,7 +1694,11 @@
                 + RawContacts.PHONETIC_NAME  + ", "
                 + RawContacts.PHONETIC_NAME_STYLE  + ", "
                 + RawContacts.SORT_KEY_PRIMARY  + ", "
+                + RawContactsColumns.PHONEBOOK_LABEL_PRIMARY  + ", "
+                + RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY  + ", "
                 + RawContacts.SORT_KEY_ALTERNATIVE + ", "
+                + RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE  + ", "
+                + RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE  + ", "
                 + dbForProfile() + " AS " + RawContacts.RAW_CONTACT_IS_USER_PROFILE + ", "
                 + rawContactOptionColumns + ", "
                 + syncColumns
@@ -2408,6 +2436,12 @@
             oldVersion = 706;
         }
 
+        if (oldVersion < 707) {
+            upgradeToVersion707(db);
+            upgradeViewsAndTriggers = true;
+            oldVersion = 707;
+        }
+
         if (upgradeViewsAndTriggers) {
             createContactsViews(db);
             createGroupsView(db);
@@ -2718,8 +2752,7 @@
                 sortKey = sortKeyAlternative = phoneticName;
             } else if (name.fullNameStyle == FullNameStyle.CHINESE ||
                     name.fullNameStyle == FullNameStyle.CJK) {
-                sortKey = sortKeyAlternative = ContactLocaleUtils.getIntance()
-                        .getSortKey(displayName, name.fullNameStyle);
+                sortKey = sortKeyAlternative = displayName;
             }
 
             if (sortKey == null) {
@@ -2776,20 +2809,7 @@
                 organizationUpdate.bindLong(2, dataId);
                 organizationUpdate.execute();
 
-                String sortKey = null;
-                if (phoneticName == null && company != null) {
-                    int nameStyle = splitter.guessFullNameStyle(company);
-                    nameStyle = splitter.getAdjustedFullNameStyle(nameStyle);
-                    if (nameStyle == FullNameStyle.CHINESE ||
-                            nameStyle == FullNameStyle.CJK ) {
-                        sortKey = ContactLocaleUtils.getIntance()
-                                .getSortKey(company, nameStyle);
-                    }
-                }
-
-                if (sortKey == null) {
-                    sortKey = company;
-                }
+                String sortKey = company;
 
                 updateRawContact205(rawContactUpdate, rawContactId, company,
                         company, phoneticNameStyle, phoneticName, sortKey, sortKey);
@@ -3810,6 +3830,17 @@
         }
     }
 
+    private void upgradeToVersion707(SQLiteDatabase db) {
+        db.execSQL("ALTER TABLE " + Tables.RAW_CONTACTS
+                + " ADD " + RawContactsColumns.PHONEBOOK_LABEL_PRIMARY + " TEXT;");
+        db.execSQL("ALTER TABLE " + Tables.RAW_CONTACTS
+                + " ADD " + RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY + " INTEGER;");
+        db.execSQL("ALTER TABLE " + Tables.RAW_CONTACTS
+                + " ADD " + RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE + " TEXT;");
+        db.execSQL("ALTER TABLE " + Tables.RAW_CONTACTS
+                + " ADD " + RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + " INTEGER;");
+    }
+
     public String extractHandleFromEmailAddress(String email) {
         Rfc822Token[] tokens = Rfc822Tokenizer.tokenize(email);
         if (tokens.length == 0) {
@@ -5172,9 +5203,7 @@
             }
             if (displayNameStyle == FullNameStyle.CHINESE ||
                     displayNameStyle == FullNameStyle.CJK) {
-                sortKeyPrimary = sortKeyAlternative =
-                        ContactLocaleUtils.getIntance().getSortKey(
-                                sortNamePrimary, displayNameStyle);
+                sortKeyPrimary = sortKeyAlternative = sortNamePrimary;
             }
         }
 
@@ -5183,6 +5212,21 @@
             sortKeyAlternative = sortNameAlternative;
         }
 
+        String phonebookLabelPrimary = "";
+        String phonebookLabelAlternative = "";
+        int phonebookBucketPrimary = 0;
+        int phonebookBucketAlternative = 0;
+        ContactLocaleUtils localeUtils = ContactLocaleUtils.getInstance();
+
+        if (sortKeyPrimary != null) {
+            phonebookBucketPrimary = localeUtils.getBucketIndex(sortKeyPrimary);
+            phonebookLabelPrimary = localeUtils.getBucketLabel(phonebookBucketPrimary);
+        }
+        if (sortKeyAlternative != null) {
+            phonebookBucketAlternative = localeUtils.getBucketIndex(sortKeyAlternative);
+            phonebookLabelAlternative = localeUtils.getBucketLabel(phonebookBucketAlternative);
+        }
+
         if (mRawContactDisplayNameUpdate == null) {
             mRawContactDisplayNameUpdate = db.compileStatement(
                     "UPDATE " + Tables.RAW_CONTACTS +
@@ -5193,7 +5237,11 @@
                             RawContacts.PHONETIC_NAME + "=?," +
                             RawContacts.PHONETIC_NAME_STYLE + "=?," +
                             RawContacts.SORT_KEY_PRIMARY + "=?," +
-                            RawContacts.SORT_KEY_ALTERNATIVE + "=?" +
+                            RawContactsColumns.PHONEBOOK_LABEL_PRIMARY + "=?," +
+                            RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY + "=?," +
+                            RawContacts.SORT_KEY_ALTERNATIVE + "=?," +
+                            RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE + "=?," +
+                            RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + "=?" +
                     " WHERE " + RawContacts._ID + "=?");
         }
 
@@ -5203,8 +5251,12 @@
         bindString(mRawContactDisplayNameUpdate, 4, bestPhoneticName);
         mRawContactDisplayNameUpdate.bindLong(5, bestPhoneticNameStyle);
         bindString(mRawContactDisplayNameUpdate, 6, sortKeyPrimary);
-        bindString(mRawContactDisplayNameUpdate, 7, sortKeyAlternative);
-        mRawContactDisplayNameUpdate.bindLong(8, rawContactId);
+        bindString(mRawContactDisplayNameUpdate, 7, phonebookLabelPrimary);
+        mRawContactDisplayNameUpdate.bindLong(8, phonebookBucketPrimary);
+        bindString(mRawContactDisplayNameUpdate, 9, sortKeyAlternative);
+        bindString(mRawContactDisplayNameUpdate, 10, phonebookLabelAlternative);
+        mRawContactDisplayNameUpdate.bindLong(11, phonebookBucketAlternative);
+        mRawContactDisplayNameUpdate.bindLong(12, rawContactId);
         mRawContactDisplayNameUpdate.execute();
     }
 
diff --git a/src/com/android/providers/contacts/ContactsProvider2.java b/src/com/android/providers/contacts/ContactsProvider2.java
index d828458..1d88298 100644
--- a/src/com/android/providers/contacts/ContactsProvider2.java
+++ b/src/com/android/providers/contacts/ContactsProvider2.java
@@ -565,6 +565,10 @@
             .add(Contacts.SEND_TO_VOICEMAIL)
             .add(Contacts.SORT_KEY_ALTERNATIVE)
             .add(Contacts.SORT_KEY_PRIMARY)
+            .add(ContactsColumns.PHONEBOOK_LABEL_PRIMARY)
+            .add(ContactsColumns.PHONEBOOK_BUCKET_PRIMARY)
+            .add(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE)
+            .add(ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE)
             .add(Contacts.STARRED)
             .add(Contacts.TIMES_CONTACTED)
             .add(Contacts.HAS_PHONE_NUMBER)
@@ -752,6 +756,10 @@
             .add(RawContacts.PHONETIC_NAME_STYLE)
             .add(RawContacts.SORT_KEY_PRIMARY)
             .add(RawContacts.SORT_KEY_ALTERNATIVE)
+            .add(RawContactsColumns.PHONEBOOK_LABEL_PRIMARY)
+            .add(RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY)
+            .add(RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE)
+            .add(RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE)
             .add(RawContacts.TIMES_CONTACTED)
             .add(RawContacts.LAST_TIME_CONTACTED)
             .add(RawContacts.CUSTOM_RINGTONE)
@@ -1443,7 +1451,7 @@
         mNameLookupBuilder = new StructuredNameLookupBuilder(mNameSplitter);
         mPostalSplitter = new PostalSplitter(mCurrentLocale);
         mCommonNicknameCache = new CommonNicknameCache(mContactsHelper.getReadableDatabase());
-        ContactLocaleUtils.getIntance().setLocale(mCurrentLocale);
+        ContactLocaleUtils.setLocale(mCurrentLocale);
         mContactAggregator = new ContactAggregator(this, mContactsHelper,
                 createPhotoPriorityResolver(context), mNameSplitter, mCommonNicknameCache);
         mContactAggregator.setEnabled(SystemProperties.getBoolean(AGGREGATE_CONTACTS, true));
@@ -6011,8 +6019,10 @@
 
         qb.setStrict(true);
 
+        // Auto-rewrite SORT_KEY_{PRIMARY, ALTERNATIVE} sort orders.
+        String localizedSortOrder = getLocalizedSortOrder(sortOrder);
         Cursor cursor =
-                query(db, qb, projection, selection, selectionArgs, sortOrder, groupBy,
+                query(db, qb, projection, selection, selectionArgs, localizedSortOrder, groupBy,
                 having, limit, cancellationSignal);
 
         if (readBooleanQueryParameter(uri, ContactCounts.ADDRESS_BOOK_INDEX_EXTRAS, false)) {
@@ -6028,6 +6038,34 @@
     }
 
 
+    // Rewrites query sort orders using SORT_KEY_{PRIMARY, ALTERNATIVE}
+    // to use PHONEBOOK_BUCKET_{PRIMARY, ALTERNATIVE} as primary key; all
+    // other sort orders are returned unchanged. Preserves ordering
+    // (eg 'DESC') if present.
+    protected static String getLocalizedSortOrder(String sortOrder) {
+        String localizedSortOrder = sortOrder;
+        if (sortOrder != null) {
+            String sortKey;
+            String sortOrderSuffix = "";
+            int spaceIndex = sortOrder.indexOf(' ');
+            if (spaceIndex != -1) {
+                sortKey = sortOrder.substring(0, spaceIndex);
+                sortOrderSuffix = sortOrder.substring(spaceIndex);
+            } else {
+                sortKey = sortOrder;
+            }
+            if (TextUtils.equals(sortKey, Contacts.SORT_KEY_PRIMARY)) {
+                localizedSortOrder = ContactsColumns.PHONEBOOK_BUCKET_PRIMARY
+                    + sortOrderSuffix + ", " + sortOrder;
+            } else if (TextUtils.equals(sortKey, Contacts.SORT_KEY_ALTERNATIVE)) {
+                localizedSortOrder = ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE
+                    + sortOrderSuffix + ", " + sortOrder;
+            }
+        }
+        return localizedSortOrder;
+    }
+
+
     private Cursor query(final SQLiteDatabase db, SQLiteQueryBuilder qb, String[] projection,
             String selection, String[] selectionArgs, String sortOrder, String groupBy,
             String having, String limit, CancellationSignal cancellationSignal) {
@@ -6122,7 +6160,7 @@
                 final long start = System.currentTimeMillis();
 
                 b = getFastScrollingIndexExtras(queryUri, db, qb, selection, selectionArgs,
-                        sortOrder, countExpression, cancellationSignal, getLocale());
+                        sortOrder, countExpression, cancellationSignal);
 
                 final long end = System.currentTimeMillis();
                 final int time = (int) (end - start);
@@ -6139,19 +6177,22 @@
 
     private static final class AddressBookIndexQuery {
         public static final String NAME = "name";
+        public static final String BUCKET = "bucket";
         public static final String LABEL = "label";
         public static final String COUNT = "count";
 
         public static final String[] COLUMNS = new String[] {
-                NAME, LABEL, COUNT
+            NAME, BUCKET, LABEL, COUNT
         };
 
         public static final int COLUMN_NAME = 0;
-        public static final int COLUMN_LABEL = 1;
-        public static final int COLUMN_COUNT = 2;
+        public static final int COLUMN_BUCKET = 1;
+        public static final int COLUMN_LABEL = 2;
+        public static final int COLUMN_COUNT = 3;
 
-        // PHONEBOOK collator registered in sqlite3_android.cpp
-        public static final String ORDER_BY = NAME + " COLLATE " + PHONEBOOK_COLLATOR_NAME;
+        public static final String GROUP_BY = BUCKET + ", " + LABEL;
+        public static final String ORDER_BY =
+            BUCKET + ", " +  NAME + " COLLATE " + PHONEBOOK_COLLATOR_NAME;
     }
 
     /**
@@ -6161,7 +6202,7 @@
     private static Bundle getFastScrollingIndexExtras(final Uri queryUri, final SQLiteDatabase db,
             final SQLiteQueryBuilder qb, final String selection, final String[] selectionArgs,
             final String sortOrder, String countExpression,
-            final CancellationSignal cancellationSignal, final Locale currentLocale) {
+            final CancellationSignal cancellationSignal) {
         String sortKey;
 
         // The sort order suffix could be something like "DESC".
@@ -6180,69 +6221,53 @@
             sortKey = Contacts.SORT_KEY_PRIMARY;
         }
 
+        String bucketKey;
+        String labelKey;
+        if (TextUtils.equals(sortKey, Contacts.SORT_KEY_PRIMARY)) {
+            bucketKey = ContactsColumns.PHONEBOOK_BUCKET_PRIMARY;
+            labelKey = ContactsColumns.PHONEBOOK_LABEL_PRIMARY;
+        } else if (TextUtils.equals(sortKey, Contacts.SORT_KEY_ALTERNATIVE)) {
+            bucketKey = ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE;
+            labelKey = ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE;
+        } else {
+            return null;
+        }
+
         HashMap<String, String> projectionMap = Maps.newHashMap();
         projectionMap.put(AddressBookIndexQuery.NAME,
                 sortKey + " AS " + AddressBookIndexQuery.NAME);
+        projectionMap.put(AddressBookIndexQuery.BUCKET,
+                bucketKey + " AS " + AddressBookIndexQuery.BUCKET);
+        projectionMap.put(AddressBookIndexQuery.LABEL,
+                labelKey + " AS " + AddressBookIndexQuery.LABEL);
 
         // If "what to count" is not specified, we just count all records.
         if (TextUtils.isEmpty(countExpression)) {
             countExpression = "*";
         }
 
-        /**
-         * Use the GET_PHONEBOOK_INDEX function, which is an android extension for SQLite3,
-         * to map the sort key to a character that is traditionally used in phonebooks to
-         * label its section.  For example, in Korean it will be the first consonant in the
-         * letter; for Japanese it will be Hiragana rather than Katakana. Note the label may
-         * be more than one character in some languages, such as "CH" in Czech.
-         */
-        projectionMap.put(AddressBookIndexQuery.LABEL,
-                "GET_PHONEBOOK_INDEX(" + sortKey + ",'" + currentLocale.toString() + "')"
-                        + " AS " + AddressBookIndexQuery.LABEL);
         projectionMap.put(AddressBookIndexQuery.COUNT,
                 "COUNT(" + countExpression + ") AS " + AddressBookIndexQuery.COUNT);
         qb.setProjectionMap(projectionMap);
+        String orderBy = AddressBookIndexQuery.BUCKET + sortOrderSuffix
+            + ", " + AddressBookIndexQuery.NAME + " COLLATE "
+            + PHONEBOOK_COLLATOR_NAME + sortOrderSuffix;
 
         Cursor indexCursor = qb.query(db, AddressBookIndexQuery.COLUMNS, selection, selectionArgs,
-                AddressBookIndexQuery.ORDER_BY, null /* having */,
-                AddressBookIndexQuery.ORDER_BY + sortOrderSuffix,
-                null, cancellationSignal);
+                AddressBookIndexQuery.GROUP_BY, null /* having */,
+                orderBy, null, cancellationSignal);
 
         try {
-            int groupCount = indexCursor.getCount();
-            String labels[] = new String[groupCount];
-            int counts[] = new int[groupCount];
-            int indexCount = 0;
-            String currentLabel = null;
+            int numLabels = indexCursor.getCount();
+            String labels[] = new String[numLabels];
+            int counts[] = new int[numLabels];
 
-            // Since GET_PHONEBOOK_INDEX is a many-to-1 function, we may end up
-            // with multiple entries for the same label.  The following code
-            // collapses those duplicates.
-            for (int i = 0; i < groupCount; i++) {
+            for (int i = 0; i < numLabels; i++) {
                 indexCursor.moveToNext();
-                String label = indexCursor.getString(AddressBookIndexQuery.COLUMN_LABEL);
-                if (label == null) {
-                    label = "";
-                }
-                int count = indexCursor.getInt(AddressBookIndexQuery.COLUMN_COUNT);
-                if (indexCount == 0 || !TextUtils.equals(label, currentLabel)) {
-                    labels[indexCount] = currentLabel = label;
-                    counts[indexCount] = count;
-                    indexCount++;
-                } else {
-                    counts[indexCount - 1] += count;
-                }
+                labels[i] = indexCursor.getString(AddressBookIndexQuery.COLUMN_LABEL);
+                counts[i] = indexCursor.getInt(AddressBookIndexQuery.COLUMN_COUNT);
             }
 
-            if (indexCount < groupCount) {
-                String[] newLabels = new String[indexCount];
-                System.arraycopy(labels, 0, newLabels, 0, indexCount);
-                labels = newLabels;
-
-                int[] newCounts = new int[indexCount];
-                System.arraycopy(counts, 0, newCounts, 0, indexCount);
-                counts = newCounts;
-            }
             return FastScrollingIndexCache.buildExtraBundle(labels, counts);
         } finally {
             indexCursor.close();
diff --git a/src/com/android/providers/contacts/NameLookupBuilder.java b/src/com/android/providers/contacts/NameLookupBuilder.java
index 8375b88..67dae46 100644
--- a/src/com/android/providers/contacts/NameLookupBuilder.java
+++ b/src/com/android/providers/contacts/NameLookupBuilder.java
@@ -321,7 +321,7 @@
 
     private void appendNameShorthandLookup(IndexBuilder builder, String name, int fullNameStyle) {
         Iterator<String> it =
-                ContactLocaleUtils.getIntance().getNameLookupKeys(name, fullNameStyle);
+                ContactLocaleUtils.getInstance().getNameLookupKeys(name, fullNameStyle);
         if (it != null) {
             while (it.hasNext()) {
                 builder.appendName(it.next());
diff --git a/tests/src/com/android/providers/contacts/ContactLocaleUtilsTest.java b/tests/src/com/android/providers/contacts/ContactLocaleUtilsTest.java
index cf18155..b43cff2 100644
--- a/tests/src/com/android/providers/contacts/ContactLocaleUtilsTest.java
+++ b/tests/src/com/android/providers/contacts/ContactLocaleUtilsTest.java
@@ -21,6 +21,7 @@
 import android.test.suitebuilder.annotation.SmallTest;
 
 import java.text.Collator;
+import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.Iterator;
@@ -28,7 +29,11 @@
 
 @SmallTest
 public class ContactLocaleUtilsTest extends AndroidTestCase {
+    private static final String PHONE_NUMBER_1 = "+1 (650) 555-1212";
+    private static final String PHONE_NUMBER_2 = "650-555-1212";
     private static final String LATIN_NAME = "John Smith";
+    private static final String LATIN_NAME_2 = "John Paul Jones";
+    private static final String KANJI_NAME = "\u65e5";
     private static final String CHINESE_NAME = "\u675C\u9D51";
     private static final String CHINESE_LATIN_MIX_NAME_1 = "D\u675C\u9D51";
     private static final String CHINESE_LATIN_MIX_NAME_2 = "MARY \u675C\u9D51";
@@ -39,15 +44,87 @@
     private static final String[] CHINESE_LATIN_MIX_NAME_2_KEY = {"\u9D51", "\u675C\u9D51",
         "MARY \u675C\u9D51", "JUAN", "DUJUAN", "MARY DUJUAN", "J", "DJ", "MDJ"};
     private static final String[] LATIN_NAME_KEY = {"John Smith", "Smith", "JS", "S"};
+    private static final String[] LATIN_NAME_KEY_2 = {
+        "John Paul Jones", "Paul Jones", "Jones", "JPJ", "PJ", "J"};
+    private static final String[] LABELS_EN_US = {
+        "", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
+        "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
+        "#", ""};
+    private static final String[] LABELS_JA_JP = {
+        "", "\u3042", "\u304B", "\u3055", "\u305F", "\u306A", "\u306F",
+        "\u307E", "\u3084", "\u3089", "\u308F", "\u4ED6",
+        "", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
+        "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
+        "#", ""};
+    private static final String[] LABELS_ZH_TW = {
+        "", "1\u5283", "2\u5283", "3\u5283", "4\u5283", "5\u5283", "6\u5283",
+        "7\u5283", "8\u5283", "9\u5283", "10\u5283", "11\u5283", "12\u5283",
+        "13\u5283", "14\u5283", "15\u5283", "16\u5283", "17\u5283", "18\u5283",
+        "19\u5283", "20\u5283", "21\u5283", "22\u5283", "23\u5283", "24\u5283",
+        "25\u5283",
+        "", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
+        "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
+        "#", ""};
+    private static final String[] LABELS_KO = {
+        "",  "\u1100", "\u1102", "\u1103", "\u1105", "\u1106", "\u1107",
+        "\u1109", "\u110B", "\u110C", "\u110E", "\u110F", "\u1110", "\u1111",
+        "\u1112",
+        "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
+        "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
+        "#", ""};
 
+    private static final String JAPANESE_MISC = "\u4ed6";
 
-    private ContactLocaleUtils mContactLocaleUtils = ContactLocaleUtils.getIntance();
+    private String getLabel(String name) {
+        ContactLocaleUtils utils = ContactLocaleUtils.getInstance();
+        int bucketIndex = utils.getBucketIndex(name);
+        return utils.getBucketLabel(bucketIndex);
+    }
 
-    public void testContactLocaleUtilsBase() throws Exception {
-        assertEquals(mContactLocaleUtils.getSortKey(LATIN_NAME, FullNameStyle.UNDEFINED),
-                LATIN_NAME);
-        assertNull(mContactLocaleUtils.getNameLookupKeys(LATIN_NAME,
-                FullNameStyle.UNDEFINED));
+    private Iterator<String> getNameLookupKeys(String name, int nameStyle) {
+        ContactLocaleUtils utils = ContactLocaleUtils.getInstance();
+        return utils.getNameLookupKeys(name, nameStyle);
+    }
+
+    private ArrayList<String> getLabels() {
+        ContactLocaleUtils utils = ContactLocaleUtils.getInstance();
+        return utils.getLabels();
+    }
+
+    public void testEnglishContactLocaleUtils() throws Exception {
+        ContactLocaleUtils.setLocale(Locale.ENGLISH);
+        assertEquals("#", getLabel(PHONE_NUMBER_1));
+        assertEquals("#", getLabel(PHONE_NUMBER_2));
+        assertEquals("J", getLabel(LATIN_NAME));
+        assertEquals("", getLabel(CHINESE_NAME));
+        assertEquals("D", getLabel(CHINESE_LATIN_MIX_NAME_1));
+        assertEquals("B", getLabel("Bob Smith"));
+
+        assertNull(getNameLookupKeys(LATIN_NAME, FullNameStyle.UNDEFINED));
+        verifyLabels(getLabels(), LABELS_EN_US);
+    }
+
+    public void testJapaneseContactLocaleUtils() throws Exception {
+        if (!hasJapaneseCollator()) {
+            return;
+        }
+
+        ContactLocaleUtils.setLocale(Locale.JAPAN);
+        assertEquals("#", getLabel(PHONE_NUMBER_1));
+        assertEquals("#", getLabel(PHONE_NUMBER_2));
+        assertEquals(JAPANESE_MISC, getLabel(KANJI_NAME));
+        assertEquals("J", getLabel(LATIN_NAME));
+        assertEquals(JAPANESE_MISC, getLabel(CHINESE_NAME));
+        assertEquals("D", getLabel(CHINESE_LATIN_MIX_NAME_1));
+
+        assertNull(getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK));
+        Iterator<String> keys = getNameLookupKeys(CHINESE_NAME,
+                FullNameStyle.CHINESE);
+        verifyKeys(keys, CHINESE_NAME_KEY);
+
+        // Following two tests are broken with ICU 4.9
+        verifyLabels(getLabels(), LABELS_JA_JP);
+        assertEquals("B", getLabel("Bob Smith"));
     }
 
     public void testChineseContactLocaleUtils() throws Exception {
@@ -55,56 +132,68 @@
             return;
         }
 
-        assertTrue(mContactLocaleUtils.getSortKey(CHINESE_NAME,
-                FullNameStyle.CHINESE).equalsIgnoreCase("DU \u675C JUAN \u9D51"));
+        ContactLocaleUtils.setLocale(Locale.SIMPLIFIED_CHINESE);
+        assertEquals("#", getLabel(PHONE_NUMBER_1));
+        assertEquals("#", getLabel(PHONE_NUMBER_2));
+        assertEquals("J", getLabel(LATIN_NAME));
+        assertEquals("D", getLabel(CHINESE_NAME));
+        assertEquals("D", getLabel(CHINESE_LATIN_MIX_NAME_1));
+        assertEquals("B", getLabel("Bob Smith"));
+        verifyLabels(getLabels(), LABELS_EN_US);
 
-        assertTrue(mContactLocaleUtils.getSortKey(CHINESE_LATIN_MIX_NAME_1,
-                FullNameStyle.CHINESE).equalsIgnoreCase("d DU \u675C JUAN \u9D51"));
+        ContactLocaleUtils.setLocale(Locale.TRADITIONAL_CHINESE);
+        assertEquals("#", getLabel(PHONE_NUMBER_1));
+        assertEquals("#", getLabel(PHONE_NUMBER_2));
+        assertEquals("J", getLabel(LATIN_NAME));
+        assertEquals("12\u5283", getLabel(CHINESE_NAME));
+        assertEquals("D", getLabel(CHINESE_LATIN_MIX_NAME_1));
 
-        assertTrue(mContactLocaleUtils.getSortKey(CHINESE_LATIN_MIX_NAME_2,
-                FullNameStyle.CHINESE).equalsIgnoreCase("mary DU \u675C JUAN \u9D51"));
-
-        Iterator<String> keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_NAME,
+        ContactLocaleUtils.setLocale(Locale.SIMPLIFIED_CHINESE);
+        Iterator<String> keys = getNameLookupKeys(CHINESE_NAME,
                 FullNameStyle.CHINESE);
         verifyKeys(keys, CHINESE_NAME_KEY);
 
-        keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_LATIN_MIX_NAME_1,
-                FullNameStyle.CHINESE);
+        keys = getNameLookupKeys(CHINESE_LATIN_MIX_NAME_1, FullNameStyle.CHINESE);
         verifyKeys(keys, CHINESE_LATIN_MIX_NAME_1_KEY);
 
-        keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_LATIN_MIX_NAME_2,
-                FullNameStyle.CHINESE);
+        keys = getNameLookupKeys(CHINESE_LATIN_MIX_NAME_2, FullNameStyle.CHINESE);
         verifyKeys(keys, CHINESE_LATIN_MIX_NAME_2_KEY);
+
+        // Following test broken with ICU 4.9
+        ContactLocaleUtils.setLocale(Locale.TRADITIONAL_CHINESE);
+        verifyLabels(getLabels(), LABELS_ZH_TW);
+        assertEquals("B", getLabel("Bob Smith"));
     }
 
     public void testChineseStyleNameWithDifferentLocale() throws Exception {
         if (!hasChineseCollator()) {
             return;
         }
-        mContactLocaleUtils.setLocale(Locale.ENGLISH);
-        assertEquals("DU \u675C JUAN \u9D51",
-                mContactLocaleUtils.getSortKey(CHINESE_NAME, FullNameStyle.CHINESE).toUpperCase());
-        assertEquals("DU \u675C JUAN \u9D51",
-                mContactLocaleUtils.getSortKey(CHINESE_NAME, FullNameStyle.CJK).toUpperCase());
-        mContactLocaleUtils.setLocale(Locale.CHINESE);
-        assertEquals("DU \u675C JUAN \u9D51",
-                mContactLocaleUtils.getSortKey(CHINESE_NAME, FullNameStyle.CHINESE).toUpperCase());
-        assertEquals("DU \u675C JUAN \u9D51",
-                mContactLocaleUtils.getSortKey(CHINESE_NAME, FullNameStyle.CJK).toUpperCase());
-        assertEquals(LATIN_NAME, mContactLocaleUtils.getSortKey(LATIN_NAME, FullNameStyle.WESTERN));
 
-        mContactLocaleUtils.setLocale(Locale.ENGLISH);
-        Iterator<String> keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_NAME,
+        ContactLocaleUtils.setLocale(Locale.ENGLISH);
+        Iterator<String> keys = getNameLookupKeys(CHINESE_NAME,
                 FullNameStyle.CHINESE);
         verifyKeys(keys, CHINESE_NAME_KEY);
-        keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
+        keys = getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
         verifyKeys(keys, CHINESE_NAME_KEY);
-        mContactLocaleUtils.setLocale(Locale.CHINESE);
-        keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
-        verifyKeys(keys, CHINESE_NAME_KEY);
-        keys = mContactLocaleUtils.getNameLookupKeys(LATIN_NAME, FullNameStyle.WESTERN);
-        verifyKeys(keys, LATIN_NAME_KEY);
 
+        ContactLocaleUtils.setLocale(Locale.CHINESE);
+        keys = getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
+        verifyKeys(keys, CHINESE_NAME_KEY);
+        keys = getNameLookupKeys(LATIN_NAME, FullNameStyle.WESTERN);
+        verifyKeys(keys, LATIN_NAME_KEY);
+        keys = getNameLookupKeys(LATIN_NAME_2, FullNameStyle.WESTERN);
+        verifyKeys(keys, LATIN_NAME_KEY_2);
+
+        ContactLocaleUtils.setLocale(Locale.TRADITIONAL_CHINESE);
+        keys = getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
+        verifyKeys(keys, CHINESE_NAME_KEY);
+    }
+
+    public void testKoreanContactLocaleUtils() throws Exception {
+        ContactLocaleUtils.setLocale(Locale.KOREA);
+        assertEquals("B", getLabel("Bob Smith"));
+        verifyLabels(getLabels(), LABELS_KO);
     }
 
     private void verifyKeys(final Iterator<String> resultKeys, final String[] expectedKeys)
@@ -113,7 +202,14 @@
         while (resultKeys.hasNext()) {
             allKeys.add(resultKeys.next());
         }
-        assertEquals(allKeys, new HashSet<String>(Arrays.asList(expectedKeys)));
+        assertEquals(new HashSet<String>(Arrays.asList(expectedKeys)), allKeys);
+    }
+
+    private void verifyLabels(final ArrayList<String> resultLabels,
+                              final String[] expectedLabels)
+            throws Exception {
+        assertEquals(new ArrayList<String>(Arrays.asList(expectedLabels)),
+                     resultLabels);
     }
 
     private boolean hasChineseCollator() {
@@ -125,4 +221,14 @@
         }
         return false;
     }
+
+    private boolean hasJapaneseCollator() {
+        final Locale locale[] = Collator.getAvailableLocales();
+        for (int i = 0; i < locale.length; i++) {
+            if (locale[i].equals(Locale.JAPAN)) {
+                return true;
+            }
+        }
+        return false;
+    }
 }
diff --git a/tests/src/com/android/providers/contacts/ContactsProvider2Test.java b/tests/src/com/android/providers/contacts/ContactsProvider2Test.java
index 1011ae2..9bcf54c 100644
--- a/tests/src/com/android/providers/contacts/ContactsProvider2Test.java
+++ b/tests/src/com/android/providers/contacts/ContactsProvider2Test.java
@@ -69,9 +69,11 @@
 import com.android.internal.util.ArrayUtils;
 import com.android.providers.contacts.ContactsDatabaseHelper;
 import com.android.providers.contacts.ContactsDatabaseHelper.AggregationExceptionColumns;
+import com.android.providers.contacts.ContactsDatabaseHelper.ContactsColumns;
 import com.android.providers.contacts.ContactsDatabaseHelper.DataUsageStatColumns;
 import com.android.providers.contacts.ContactsDatabaseHelper.DbProperties;
 import com.android.providers.contacts.ContactsDatabaseHelper.PresenceColumns;
+import com.android.providers.contacts.ContactsDatabaseHelper.RawContactsColumns;
 import com.android.providers.contacts.ContactsDatabaseHelper.Tables;
 import com.android.providers.contacts.tests.R;
 import com.google.android.collect.Lists;
@@ -112,6 +114,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -146,6 +152,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -184,6 +194,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -224,6 +238,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -271,6 +289,10 @@
                 RawContacts.NAME_VERIFIED,
                 RawContacts.SORT_KEY_PRIMARY,
                 RawContacts.SORT_KEY_ALTERNATIVE,
+                RawContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 RawContacts.TIMES_CONTACTED,
                 RawContacts.LAST_TIME_CONTACTED,
                 RawContacts.CUSTOM_RINGTONE,
@@ -337,6 +359,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -406,6 +432,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -490,6 +520,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -1212,7 +1246,6 @@
         // Sanity test. Run tests for "Chilled Guacamole" again and see nothing changes
         // after the Sip address being inserted.
         assertStoredValues(filterUri2, values);
-        assertStoredValues(filterUri3, values);
         assertEquals(0, getCount(filterUri4, null, null));
         assertEquals(0, getCount(filterUri5, null, null));
         assertStoredValues(filterUri6, new ContentValues[] {values1, values2, values3} );
@@ -3034,6 +3067,7 @@
     }
 
     public void testContactWithoutPhoneticName() {
+        ContactLocaleUtils.setLocale(Locale.ENGLISH);
         final long rawContactId = createRawContact(null);
 
         ContentValues values = new ContentValues();
@@ -3051,7 +3085,9 @@
         values.putNull(RawContacts.PHONETIC_NAME);
         values.put(RawContacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
         values.put(RawContacts.SORT_KEY_PRIMARY, "John K. Doe, Jr.");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_PRIMARY, "J");
         values.put(RawContacts.SORT_KEY_ALTERNATIVE, "Doe, John K., Jr.");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "D");
 
         Uri rawContactUri = ContentUris.withAppendedId(RawContacts.CONTENT_URI, rawContactId);
         assertStoredValues(rawContactUri, values);
@@ -3063,7 +3099,9 @@
         values.putNull(Contacts.PHONETIC_NAME);
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
         values.put(Contacts.SORT_KEY_PRIMARY, "John K. Doe, Jr.");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "J");
         values.put(Contacts.SORT_KEY_ALTERNATIVE, "Doe, John K., Jr.");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "D");
 
         Uri contactUri = ContentUris.withAppendedId(Contacts.CONTENT_URI,
                 queryContactId(rawContactId));
@@ -3074,15 +3112,15 @@
     }
 
     public void testContactWithChineseName() {
-
-        // Only run this test when Chinese collation is supported
-        if (!Arrays.asList(Collator.getAvailableLocales()).contains(Locale.CHINA)) {
+        if (!hasChineseCollator()) {
             return;
         }
+        ContactLocaleUtils.setLocale(Locale.SIMPLIFIED_CHINESE);
 
         long rawContactId = createRawContact(null);
 
         ContentValues values = new ContentValues();
+        // "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B"
         values.put(StructuredName.DISPLAY_NAME, "\u6BB5\u5C0F\u6D9B");
         Uri dataUri = insertStructuredName(rawContactId, values);
 
@@ -3092,8 +3130,10 @@
         values.put(RawContacts.DISPLAY_NAME_ALTERNATIVE, "\u6BB5\u5C0F\u6D9B");
         values.putNull(RawContacts.PHONETIC_NAME);
         values.put(RawContacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
-        values.put(RawContacts.SORT_KEY_PRIMARY, "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B");
-        values.put(RawContacts.SORT_KEY_ALTERNATIVE, "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B");
+        values.put(RawContacts.SORT_KEY_PRIMARY, "\u6BB5\u5C0F\u6D9B");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_PRIMARY, "D");
+        values.put(RawContacts.SORT_KEY_ALTERNATIVE, "\u6BB5\u5C0F\u6D9B");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "D");
 
         Uri rawContactUri = ContentUris.withAppendedId(RawContacts.CONTENT_URI, rawContactId);
         assertStoredValues(rawContactUri, values);
@@ -3104,8 +3144,10 @@
         values.put(Contacts.DISPLAY_NAME_ALTERNATIVE, "\u6BB5\u5C0F\u6D9B");
         values.putNull(Contacts.PHONETIC_NAME);
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
-        values.put(Contacts.SORT_KEY_PRIMARY, "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B");
-        values.put(Contacts.SORT_KEY_ALTERNATIVE, "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B");
+        values.put(Contacts.SORT_KEY_PRIMARY, "\u6BB5\u5C0F\u6D9B");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "D");
+        values.put(Contacts.SORT_KEY_ALTERNATIVE, "\u6BB5\u5C0F\u6D9B");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "D");
 
         Uri contactUri = ContentUris.withAppendedId(Contacts.CONTENT_URI,
                 queryContactId(rawContactId));
@@ -3116,6 +3158,10 @@
     }
 
     public void testContactWithJapaneseName() {
+        if (!hasJapaneseCollator()) {
+            return;
+        }
+        ContactLocaleUtils.setLocale(Locale.JAPAN);
         long rawContactId = createRawContact(null);
 
         ContentValues values = new ContentValues();
@@ -3131,6 +3177,8 @@
         values.put(RawContacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.JAPANESE);
         values.put(RawContacts.SORT_KEY_PRIMARY, "\u304B\u3044\u304F\u3046");
         values.put(RawContacts.SORT_KEY_ALTERNATIVE, "\u304B\u3044\u304F\u3046");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_PRIMARY, "\u304B");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "\u304B");
 
         Uri rawContactUri = ContentUris.withAppendedId(RawContacts.CONTENT_URI, rawContactId);
         assertStoredValues(rawContactUri, values);
@@ -3143,6 +3191,8 @@
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.JAPANESE);
         values.put(Contacts.SORT_KEY_PRIMARY, "\u304B\u3044\u304F\u3046");
         values.put(Contacts.SORT_KEY_ALTERNATIVE, "\u304B\u3044\u304F\u3046");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "\u304B");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "\u304B");
 
         Uri contactUri = ContentUris.withAppendedId(Contacts.CONTENT_URI,
                 queryContactId(rawContactId));
@@ -3230,10 +3280,16 @@
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
         values.put(Contacts.SORT_KEY_PRIMARY, "Monsters Inc");
         values.put(Contacts.SORT_KEY_ALTERNATIVE, "Monsters Inc");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "M");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "M");
         assertStoredValues(uri, values);
     }
 
     public void testDisplayNameFromOrganizationWithJapanesePhoneticName() {
+        if (!hasJapaneseCollator()) {
+            return;
+        }
+        ContactLocaleUtils.setLocale(Locale.JAPAN);
         long rawContactId = createRawContact();
         long contactId = queryContactId(rawContactId);
         ContentValues values = new ContentValues();
@@ -3252,22 +3308,16 @@
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.JAPANESE);
         values.put(Contacts.SORT_KEY_PRIMARY, "\u30C9\u30B3\u30E2");
         values.put(Contacts.SORT_KEY_ALTERNATIVE, "\u30C9\u30B3\u30E2");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "\u305F");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "\u305F");
         assertStoredValues(uri, values);
     }
 
     public void testDisplayNameFromOrganizationWithChineseName() {
-        boolean hasChineseCollator = false;
-        final Locale locale[] = Collator.getAvailableLocales();
-        for (int i = 0; i < locale.length; i++) {
-            if (locale[i].equals(Locale.CHINA)) {
-                hasChineseCollator = true;
-                break;
-            }
-        }
-
-        if (!hasChineseCollator) {
+        if (!hasChineseCollator()) {
             return;
         }
+        ContactLocaleUtils.setLocale(Locale.SIMPLIFIED_CHINESE);
 
         long rawContactId = createRawContact();
         long contactId = queryContactId(rawContactId);
@@ -3284,8 +3334,10 @@
         values.put(Contacts.DISPLAY_NAME, "\u4E2D\u56FD\u7535\u4FE1");
         values.putNull(Contacts.PHONETIC_NAME);
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
-        values.put(Contacts.SORT_KEY_PRIMARY, "ZHONG \u4E2D GUO \u56FD DIAN \u7535 XIN \u4FE1");
-        values.put(Contacts.SORT_KEY_ALTERNATIVE, "ZHONG \u4E2D GUO \u56FD DIAN \u7535 XIN \u4FE1");
+        values.put(Contacts.SORT_KEY_PRIMARY, "\u4E2D\u56FD\u7535\u4FE1");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "Z");
+        values.put(Contacts.SORT_KEY_ALTERNATIVE, "\u4E2D\u56FD\u7535\u4FE1");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "Z");
         assertStoredValues(uri, values);
     }
 
@@ -6186,6 +6238,23 @@
         testChangingPrimary(true, true);
     }
 
+    public void testContactSortOrder() {
+        assertEquals(ContactsColumns.PHONEBOOK_BUCKET_PRIMARY + ", "
+                     + Contacts.SORT_KEY_PRIMARY,
+                     ContactsProvider2.getLocalizedSortOrder(Contacts.SORT_KEY_PRIMARY));
+        assertEquals(ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + ", "
+                     + Contacts.SORT_KEY_ALTERNATIVE,
+                     ContactsProvider2.getLocalizedSortOrder(Contacts.SORT_KEY_ALTERNATIVE));
+        assertEquals(ContactsColumns.PHONEBOOK_BUCKET_PRIMARY + " DESC, "
+                     + Contacts.SORT_KEY_PRIMARY + " DESC",
+                     ContactsProvider2.getLocalizedSortOrder(Contacts.SORT_KEY_PRIMARY + " DESC"));
+        String suffix = " COLLATE LOCALIZED DESC";
+        assertEquals(ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + suffix
+                     + ", " + Contacts.SORT_KEY_ALTERNATIVE + suffix,
+                     ContactsProvider2.getLocalizedSortOrder(Contacts.SORT_KEY_ALTERNATIVE
+                                                             + suffix));
+    }
+
     public void testContactCounts() {
         Uri uri = Contacts.CONTENT_URI.buildUpon()
                 .appendQueryParameter(ContactCounts.ADDRESS_BOOK_INDEX_EXTRAS, "true").build();
@@ -6201,7 +6270,7 @@
 
         Cursor cursor = mResolver.query(uri,
                 new String[]{Contacts.DISPLAY_NAME},
-                null, null, Contacts.SORT_KEY_PRIMARY + " COLLATE LOCALIZED");
+                null, null, Contacts.SORT_KEY_PRIMARY);
 
         assertFirstLetterValues(cursor, "", "B", "J", "M", "R", "T");
         assertFirstLetterCounts(cursor,    1,   1,   1,   2,   2,   1);
@@ -7266,4 +7335,24 @@
                 .appendQueryParameter(DataUsageFeedback.USAGE_TYPE, usageType)
                 .build(), new ContentValues(), null, null);
     }
+
+    private boolean hasChineseCollator() {
+        final Locale locale[] = Collator.getAvailableLocales();
+        for (int i = 0; i < locale.length; i++) {
+            if (locale[i].equals(Locale.CHINA)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private boolean hasJapaneseCollator() {
+        final Locale locale[] = Collator.getAvailableLocales();
+        for (int i = 0; i < locale.length; i++) {
+            if (locale[i].equals(Locale.JAPAN)) {
+                return true;
+            }
+        }
+        return false;
+    }
 }