Adding alphabetical separators to the ContactList
diff --git a/res/layout-finger/contacts_list_item.xml b/res/layout-finger/contacts_list_item.xml
index e695f90..d05bbbf 100644
--- a/res/layout-finger/contacts_list_item.xml
+++ b/res/layout-finger/contacts_list_item.xml
@@ -17,66 +17,77 @@
  */
 -->
 
-<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
+<LinearLayout  xmlns:android="http://schemas.android.com/apk/res/android"
     android:layout_width="fill_parent"
-    android:layout_height="?android:attr/listPreferredItemHeight"
-    android:paddingLeft="14dip"
-    android:paddingRight="5dip"
+    android:layout_height="wrap_content"
+    android:orientation="vertical"
 >
-
-    <ImageView android:id="@+id/presence"
-        android:layout_width="32dip"
-        android:layout_height="32dip"
-        android:layout_alignParentRight="true"
-        android:layout_marginLeft="5dip"
-        android:layout_centerVertical="true"
-
-        android:gravity="center"
-        android:scaleType="centerInside"
+    <include 
+        android:id="@+id/header" 
+        layout="@layout/list_separator"
     />
-
-    <TextView android:id="@+id/label"
-        android:layout_width="wrap_content"
-        android:layout_height="wrap_content"
-        android:layout_alignParentLeft="true"
-        android:layout_alignParentBottom="true"
-        android:layout_marginBottom="8dip"
-        android:layout_marginTop="-8dip"
-
-        android:singleLine="true"
-        android:ellipsize="marquee"
-        android:textAppearance="?android:attr/textAppearanceSmall"
-        android:textStyle="bold"
-    />
-
-    <TextView android:id="@+id/number"
-        android:layout_width="wrap_content"
-        android:layout_height="wrap_content"
-        android:layout_marginLeft="5dip"
-        android:layout_toRightOf="@id/label"
-        android:layout_alignBaseline="@id/label"
-        android:layout_toLeftOf="@id/presence"
-        android:layout_alignWithParentIfMissing="true"
-
-        android:singleLine="true"
-        android:ellipsize="marquee"
-        android:textAppearance="?android:attr/textAppearanceSmall"
-    />
-
-    <TextView android:id="@+id/name"
-        android:layout_width="0dip"
-        android:layout_height="0dip"
-        android:layout_above="@id/label"
-        android:layout_alignWithParentIfMissing="true"
-        android:layout_alignParentTop="true"
-        android:layout_alignParentLeft="true"
-        android:layout_toLeftOf="@id/presence"
-        android:layout_marginBottom="1dip"
-
-        android:singleLine="true"
-        android:ellipsize="marquee"
-        android:gravity="center_vertical|left"
-        android:textAppearance="?android:attr/textAppearanceLarge"
-    />
-
-</RelativeLayout>
+    
+    <RelativeLayout
+        android:layout_width="fill_parent"
+        android:layout_height="?android:attr/listPreferredItemHeight"
+        android:paddingLeft="14dip"
+        android:paddingRight="5dip"
+    >
+    
+        <ImageView android:id="@+id/presence"
+            android:layout_width="32dip"
+            android:layout_height="32dip"
+            android:layout_alignParentRight="true"
+            android:layout_marginLeft="5dip"
+            android:layout_centerVertical="true"
+    
+            android:gravity="center"
+            android:scaleType="centerInside"
+        />
+    
+        <TextView android:id="@+id/label"
+            android:layout_width="wrap_content"
+            android:layout_height="wrap_content"
+            android:layout_alignParentLeft="true"
+            android:layout_alignParentBottom="true"
+            android:layout_marginBottom="8dip"
+            android:layout_marginTop="-8dip"
+    
+            android:singleLine="true"
+            android:ellipsize="marquee"
+            android:textAppearance="?android:attr/textAppearanceSmall"
+            android:textStyle="bold"
+        />
+    
+        <TextView android:id="@+id/number"
+            android:layout_width="wrap_content"
+            android:layout_height="wrap_content"
+            android:layout_marginLeft="5dip"
+            android:layout_toRightOf="@id/label"
+            android:layout_alignBaseline="@id/label"
+            android:layout_toLeftOf="@id/presence"
+            android:layout_alignWithParentIfMissing="true"
+    
+            android:singleLine="true"
+            android:ellipsize="marquee"
+            android:textAppearance="?android:attr/textAppearanceSmall"
+        />
+    
+        <TextView android:id="@+id/name"
+            android:layout_width="0dip"
+            android:layout_height="0dip"
+            android:layout_above="@id/label"
+            android:layout_alignWithParentIfMissing="true"
+            android:layout_alignParentTop="true"
+            android:layout_alignParentLeft="true"
+            android:layout_toLeftOf="@id/presence"
+            android:layout_marginBottom="1dip"
+    
+            android:singleLine="true"
+            android:ellipsize="marquee"
+            android:gravity="center_vertical|left"
+            android:textAppearance="?android:attr/textAppearanceLarge"
+        />
+    
+    </RelativeLayout>
+</LinearLayout>
\ No newline at end of file
diff --git a/res/layout-finger/contacts_list_item_photo.xml b/res/layout-finger/contacts_list_item_photo.xml
index c208b93..db00dd6 100644
--- a/res/layout-finger/contacts_list_item_photo.xml
+++ b/res/layout-finger/contacts_list_item_photo.xml
@@ -17,77 +17,88 @@
  */
 -->
 
-<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
+<LinearLayout  xmlns:android="http://schemas.android.com/apk/res/android"
     android:layout_width="fill_parent"
-    android:layout_height="?android:attr/listPreferredItemHeight"
-    android:paddingLeft="5dip"
-    android:paddingRight="5dip"
+    android:layout_height="wrap_content"
+    android:orientation="vertical"
 >
-
-    <ImageView android:id="@+id/presence"
-        android:layout_width="32dip"
-        android:layout_height="32dip"
-        android:layout_alignParentRight="true"
-        android:layout_marginLeft="5dip"
-        android:layout_centerVertical="true"
-
-        android:gravity="center"
-        android:scaleType="centerInside"
+    <include 
+        android:id="@+id/header" 
+        layout="@layout/list_separator"
     />
-
-    <ImageView android:id="@+id/photo"
-        android:layout_width="54dip"
-        android:layout_height="54dip"
-        android:layout_alignParentLeft="true"
-        android:layout_centerVertical="true"
-        android:layout_marginRight="8dip"
-
-        android:gravity="center"
-        android:scaleType="fitCenter"
-        android:background="@drawable/contact_picture_border_in_list"
-    />
-
-    <TextView android:id="@+id/label"
-        android:layout_width="wrap_content"
-        android:layout_height="wrap_content"
-        android:layout_toRightOf="@id/photo"
-        android:layout_alignParentBottom="true"
-        android:layout_marginBottom="8dip"
-        android:layout_marginTop="-10dip"
-
-        android:singleLine="true"
-        android:ellipsize="marquee"
-        android:textAppearance="?android:attr/textAppearanceSmall"
-        android:textStyle="bold"
-    />
-
-    <TextView android:id="@+id/number"
-        android:layout_width="wrap_content"
-        android:layout_height="wrap_content"
-        android:layout_marginLeft="5dip"
-        android:layout_toRightOf="@id/label"
-        android:layout_toLeftOf="@id/presence"
-        android:layout_alignBaseline="@id/label"
-        android:layout_alignWithParentIfMissing="true"
-
-        android:singleLine="true"
-        android:ellipsize="marquee"
-        android:textAppearance="?android:attr/textAppearanceSmall"
-    />
-
-    <TextView android:id="@+id/name"
-        android:layout_width="0dip"
-        android:layout_height="0dip"
-        android:layout_toRightOf="@id/photo"
-        android:layout_toLeftOf="@id/presence"
-        android:layout_alignParentTop="true"
-        android:layout_above="@id/label"
-        android:layout_alignWithParentIfMissing="true"
-
-        android:singleLine="true"
-        android:ellipsize="marquee"
-        android:gravity="center_vertical|left"
-        android:textAppearance="?android:attr/textAppearanceLarge"
-    />
-
-</RelativeLayout>
+    
+    <RelativeLayout
+        android:layout_width="fill_parent"
+        android:layout_height="?android:attr/listPreferredItemHeight"
+        android:paddingLeft="5dip"
+        android:paddingRight="5dip"
+    >
+    
+        <ImageView android:id="@+id/presence"
+            android:layout_width="32dip"
+            android:layout_height="32dip"
+            android:layout_alignParentRight="true"
+            android:layout_marginLeft="5dip"
+            android:layout_centerVertical="true"
+    
+            android:gravity="center"
+            android:scaleType="centerInside"
+        />
+    
+        <ImageView android:id="@+id/photo"
+            android:layout_width="54dip"
+            android:layout_height="54dip"
+            android:layout_alignParentLeft="true"
+            android:layout_centerVertical="true"
+            android:layout_marginRight="8dip"
+    
+            android:gravity="center"
+            android:scaleType="fitCenter"
+            android:background="@drawable/contact_picture_border_in_list"
+        />
+    
+        <TextView android:id="@+id/label"
+            android:layout_width="wrap_content"
+            android:layout_height="wrap_content"
+            android:layout_toRightOf="@id/photo"
+            android:layout_alignParentBottom="true"
+            android:layout_marginBottom="8dip"
+            android:layout_marginTop="-10dip"
+    
+            android:singleLine="true"
+            android:ellipsize="marquee"
+            android:textAppearance="?android:attr/textAppearanceSmall"
+            android:textStyle="bold"
+        />
+    
+        <TextView android:id="@+id/number"
+            android:layout_width="wrap_content"
+            android:layout_height="wrap_content"
+            android:layout_marginLeft="5dip"
+            android:layout_toRightOf="@id/label"
+            android:layout_toLeftOf="@id/presence"
+            android:layout_alignBaseline="@id/label"
+            android:layout_alignWithParentIfMissing="true"
+    
+            android:singleLine="true"
+            android:ellipsize="marquee"
+            android:textAppearance="?android:attr/textAppearanceSmall"
+        />
+    
+        <TextView android:id="@+id/name"
+            android:layout_width="0dip"
+            android:layout_height="0dip"
+            android:layout_toRightOf="@id/photo"
+            android:layout_toLeftOf="@id/presence"
+            android:layout_alignParentTop="true"
+            android:layout_above="@id/label"
+            android:layout_alignWithParentIfMissing="true"
+    
+            android:singleLine="true"
+            android:ellipsize="marquee"
+            android:gravity="center_vertical|left"
+            android:textAppearance="?android:attr/textAppearanceLarge"
+        />
+    
+    </RelativeLayout>
+</LinearLayout>
diff --git a/src/com/android/contacts/ContactsListActivity.java b/src/com/android/contacts/ContactsListActivity.java
index fefb815..b8abc29 100644
--- a/src/com/android/contacts/ContactsListActivity.java
+++ b/src/com/android/contacts/ContactsListActivity.java
@@ -1411,6 +1411,7 @@
     }
 
     final static class ContactListItemCache {
+        public TextView header;
         public TextView nameView;
         public CharArrayBuffer nameBuffer = new CharArrayBuffer(128);
         public TextView labelView;
@@ -1431,6 +1432,8 @@
         private boolean mDisplayPhotos = false;
         private SparseArray<SoftReference<Bitmap>> mBitmapCache = null;
         private int mFrequentSeparatorPos = ListView.INVALID_POSITION;
+        private boolean mDisplaySectionHeaders = true;
+        private int[] mSectionPositions;
 
         public ContactItemListAdapter(Context context) {
             super(context, R.layout.contacts_list_item, null, false);
@@ -1454,6 +1457,10 @@
                 setViewResource(R.layout.contacts_list_item_photo);
                 mBitmapCache = new SparseArray<SoftReference<Bitmap>>();
             }
+
+            if (mMode == MODE_STREQUENT) {
+                mDisplaySectionHeaders = false;
+            }
         }
 
         private SectionIndexer getNewIndexer(Cursor cursor) {
@@ -1527,7 +1534,8 @@
                 return view;
             }
 
-            if (!mCursor.moveToPosition(getRealPosition(position))) {
+            int realPosition = getRealPosition(position);
+            if (!mCursor.moveToPosition(realPosition)) {
                 throw new IllegalStateException("couldn't move cursor to position " + position);
             }
 
@@ -1538,6 +1546,7 @@
                 v = convertView;
             }
             bindView(v, mContext, mCursor);
+            bindSectionHeader(v, realPosition);
             return v;
         }
 
@@ -1546,6 +1555,7 @@
             final View view = super.newView(context, cursor, parent);
 
             final ContactListItemCache cache = new ContactListItemCache();
+            cache.header = (TextView) view.findViewById(R.id.header);
             cache.nameView = (TextView) view.findViewById(R.id.name);
             cache.labelView = (TextView) view.findViewById(R.id.label);
             cache.numberView = (TextView) view.findViewById(R.id.number);
@@ -1665,6 +1675,21 @@
             }
         }
 
+        private void bindSectionHeader(View view, int position) {
+            final ContactListItemCache cache = (ContactListItemCache) view.getTag();
+            if (!mDisplaySectionHeaders) {
+                cache.header.setVisibility(View.GONE);
+            } else {
+                final int section = getSectionForPosition(position);
+                if (getPositionForSection(section) == position) {
+                    cache.header.setText(mIndexer.getSections()[section].toString());
+                    cache.header.setVisibility(View.VISIBLE);
+                } else {
+                    cache.header.setVisibility(View.GONE);
+                }
+            }
+        }
+
         @Override
         public void changeCursor(Cursor cursor) {
             // Get the split between starred and frequent items, if the mode is strequent
@@ -1712,6 +1737,14 @@
                     }
                 }
             }
+
+            int sectionCount = mIndexer.getSections().length;
+            if (mSectionPositions == null || mSectionPositions.length != sectionCount) {
+                mSectionPositions = new int[sectionCount];
+            }
+            for (int i = 0; i < sectionCount; i++) {
+                mSectionPositions[i] = ListView.INVALID_POSITION;
+            }
         }
 
         /**
@@ -1745,14 +1778,40 @@
                 mIndexer = getNewIndexer(cursor);
             }
 
-            return mIndexer.getPositionForSection(sectionIndex);
+            int position = mSectionPositions[sectionIndex];
+            if (position == ListView.INVALID_POSITION) {
+                position = mSectionPositions[sectionIndex] = mIndexer.getPositionForSection(sectionIndex);
+            }
+
+            return position;
         }
 
         public int getSectionForPosition(int position) {
-            // Note: JapaneseContactListIndexer depends on the fact
-            // this method always returns 0. If you change this,
-            // please care it too.
-            return 0;
+            // The current implementations of SectionIndexers (specifically the Japanese indexer)
+            // only work in one direction: given a section they can calculate the position.
+            // Here we are using that existing functionality to do the reverse mapping. We are
+            // performing binary search in the mSectionPositions array, which itself is populated
+            // lazily using the "forward" mapping supported by the indexer.
+
+            int start = 0;
+            int end = mSectionPositions.length;
+            while (start != end) {
+
+                // We are making the binary search slightly asymmetrical, because the
+                // user is more likely to be scrolling the list from the top down.
+                int pivot = start + (end - start) / 4;
+
+                int value = getPositionForSection(pivot);
+                if (value <= position) {
+                    start = pivot + 1;
+                } else {
+                    end = pivot;
+                }
+            }
+
+            // The variable "start" cannot be 0, as long as the indexer is implemented properly
+            // and actually maps position = 0 to section = 0
+            return start - 1;
         }
 
         @Override