CursorAdapter with Alphabet-indexed Section Headers

Hey everyone, today I would like to share how to organize a CursorAdapter into sections alphabetically. It works as long as your queries in the Cursor are alphabetically sorted (so the sortOrder parameter of your query is ASC by the column you want to alphabetize by).

This is made easier by the AlphabetIndexer widget, which uses binary search to finds the position of the first word of each starting letter in your data. However, there are still a few subtleties that must be addressed.

We wish to go from a un-sectioned data set to a list with the alphabet headers in the correct positions, like above. Here is my solution to this problem.

There are two methods inherited from BaseAdapter that we need to consider:
–getCount(): the number of items the ListView should display. Since now we wish to include one extra header in the list, for every alphabetical section, this should return num_items_in_data + num_sections
–getItem(positition): returns the item in the data set associated with the position in the ListView. Note that there is an offset depending on how many section headers appear in the data. So in the picture above, to get Fig in the list with headers, since 4 headers appear (A,B,C,F), we want the data item with position 6, instead of the list index which has position 10.

And there are two methods that we implement for SectionIndexer:
–getPositionForSection(section): returns the position of the beginning of each section (which in our case is alphabetical). As mentioned before, the AlphabetIndexer will give us the position of the first word starting with each letter in our data set (so it will tell us where A cooresponds to 0, B cooresponds to 1, F to 6, etc). We must offset these positions by the number of other headers that have appeared, so the new position of A is 0 + 0, new position of B is 1 + 1, new position of F is 6 + 3.
–getSectionForPosition(position): returns which section each position belongs to. The AlphabetIndexer does this by linearly comparing the first letter of each word to each possible letter in the alphabet, but in our case we now have an offset to consider. I choose to not use the AlphabetIndexer at all for this, but do a similar thing.

The first issue is to find out which alphabetical headers we actually need (in the above picture we only need A, B, C, F). Since at very least the number of headers we actually use needs to be quickly on the spot (say when getCount() is called), and the only way to determine this is to scan the entire data set, we should do some pre-computation.

The second issue is to calculate the offset for each section. This isn’t very hard, because each time we have a new section, there is a new extra header in our list, so the offset increases by 1. So convenience, we can define a map from section number to offset.

Here is the set-up:

private AlphabetIndexer indexer;

//this array is for fast lookup later and will contain the just the
//alphabet sections that actually appear in the data set
private int[] usedSectionIndicies;

//map from alphabet section to the index it ought
//to appear in
private Map<Integer, Integer> sectionToPosition;

//map from alphabet section to the number of other sections
//that appear before it
private Map<Integer, Integer> sectionToOffset;

	{
			indexer = new AlphabetIndexer(c, c.getColumnIndexOrThrow(YOU_COLUMN_NAME), "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
			sectionToPosition = new TreeMap<Integer, Integer>(); //use a TreeMap because we are going to iterate over its keys in sorted order
			sectionToOffset = new HashMap<Integer, Integer>();

			final int count = super.getCount();
			
			int i;
			//temporarily have a map alphabet section to first index it appears
			//(this map is going to be doing somethine else later)
			for (i = count - 1 ; i >= 0; i--){
				sectionToPosition.put(indexer.getSectionForPosition(i), i);
			}

			i = 0;
			usedSectionNumbers = new int[sectionToPosition.keySet().size()];
			
			//note that for each section that appears before a position, we must offset our
			//indices by 1, to make room for an alphabetical header in our list
			for (Integer section : sectionToPosition.keySet()){
				sectionToOffset.put(section, i);
				usedSectionNumbers[i] = section;
				i++;
			}

			//use offset to map the alphabet sections to their actual indicies in the list
			for(Integer section: sectionToPosition.keySet()){
				sectionToPosition.put(section, sectionToPosition.get(section) + sectionToOffset.get(section));
			}
	}

Now for the four discussed methods above, there are a few more subtleties with the implementation of ListView and FastScroller that must be considered.

		@Override
		public int getCount() {
			if (super.getCount() != 0){
				//sometimes your data set gets invalidated. In this case getCount()
				//should return 0 and not our adjusted count for the headers.
				//Any easy way to know if data is invalidated is to check if
				//super.getCount() is 0.
				return super.getCount() + usedSectionNumbers.length;
			}
			
			return 0;
		}
		
		@Override
		public Object getItem(int position) {
			if (getItemViewType(position) == TYPE_NORMAL){//we define this function in the full code later
				//if the list item is not a header, then we fetch the data set item with the same position
				//off-setted by the number of headers that appear before the item in the list
				return super.getItem(position - sectionToOffset.get(getSectionForPosition(position)) - 1);
			}

			return null;
		}

		@Override
		public int getPositionForSection(int section) {
			if (! sectionToOffset.containsKey(section)){ 
				//This is only the case when the FastScroller is scrolling,
				//and so this section doesn't appear in our data set. The implementation
				//of Fastscroller requires that missing sections have the same index as the
				//beginning of the next non-missing section (or the end of the the list if 
				//if the rest of the sections are missing).
				//So, in pictorial example, the sections D and E would appear at position 9
				//and G to Z appear in position 11.
				int i = 0;
				int maxLength = usedSectionNumbers.length;
				
				//linear scan over the sections (constant number of these) that appear in the 
				//data set to find the first used section that is greater than the given section, so in the
				//example D and E correspond to F
				while (i < maxLength && section > usedSectionNumbers[i]){
					i++;
				}
				if (i == maxLength) return getCount(); //the given section is past all our data

				return indexer.getPositionForSection(usedSectionNumbers[i]) + sectionToOffset.get(usedSectionNumbers[i]);
			}

			return indexer.getPositionForSection(section) + sectionToOffset.get(section);
		}

		@Override
		public int getSectionForPosition(int position) {
			int i = 0;		
			int maxLength = usedSectionNumbers.length;
	
			//linear scan over the used alphabetical sections' positions
			//to find where the given section fits in
			while (i < maxLength && position >= sectionToPosition.get(usedSectionNumbers[i])){
				i++;
			}
			return usedSectionNumbers[i-1];
		}

Now to put it all together, first we need a layout for the header. A simple TextView will suffice:

<?xml version="1.0" encoding="utf-8"?>
<TextView xmlns:android="http://schemas.android.com/apk/res/android"
	android:id="@+id/header"
    android:layout_width="fill_parent"
    android:layout_height="wrap_content"
    android:padding="6dp"
    android:textSize="18sp" 
    android:textStyle="bold"
    android:gravity="center"
    android:background="@android:color/white"
    android:textColor="@android:color/black"
    />

Now we need our CursorAdapter to implement SectionIndexer, and use the previously discussed method, with a few additional methods (also I’m just extending a SimpleCursorAdapter so I don’t need to implement newView() or bindView() ).

	public class MyAlphabetizedAdapter extends SimpleCursorAdapter implements SectionIndexer{

		private static final int TYPE_HEADER = 1;
		private static final int TYPE_NORMAL = 0;

		private static final int TYPE_COUNT = 2;

		private AlphabetIndexer indexer;

		private int[] usedSectionNumbers;

		private Map<Integer, Integer> sectionToOffset;
		private Map<Integer, Integer> sectionToPosition;
	
		public MyAlphabetizedAdapter(Context context, int layout, Cursor c,
				String[] from, int[] to) {
			super(context, layout, c, from, to);
			
			indexer = new AlphabetIndexer(c, c.getColumnIndexOrThrow(YOUR_COLUMN_NAME, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
			sectionToPosition = new TreeMap<Integer, Integer>();
			sectionToOffset = new HashMap<Integer, Integer>();

			final int count = super.getCount();
			
			int i;
			for (i = count - 1 ; i >= 0; i--){
				sectionToPosition.put(indexer.getSectionForPosition(i), i);
			}

			i = 0;
			usedSectionNumbers = new int[sectionToPosition.keySet().size()];
			
			for (Integer section : sectionToPosition.keySet()){
				sectionToOffset.put(section, i);
				usedSectionNumbers[i] = section;
				i++;
			}

			for(Integer section: sectionToPosition.keySet()){
				sectionToPosition.put(section, sectionToPosition.get(section) + sectionToOffset.get(section));
			}
		}

		@Override
		public int getCount() {
			if (super.getCount() != 0){
				return super.getCount() + usedSectionNumbers.length;
			}
			
			return 0;
		}
		
		@Override
		public Object getItem(int position) {
			if (getItemViewType(position) == TYPE_NORMAL){//we define this function later
				return super.getItem(position - sectionToOffset.get(getSectionForPosition(position)) - 1);
			}

			return null;
		}

		@Override
		public int getPositionForSection(int section) {
			if (! sectionToOffset.containsKey(section)){ 
				int i = 0;
				int maxLength = usedSectionNumbers.length;
				
				while (i < maxLength && section > usedSectionNumbers[i]){
					i++;
				}
				if (i == maxLength) return getCount();

				return indexer.getPositionForSection(usedSectionNumbers[i]) + sectionToOffset.get(usedSectionNumbers[i]);
			}

			return indexer.getPositionForSection(section) + sectionToOffset.get(section);
		}

		@Override
		public int getSectionForPosition(int position) {
			int i = 0;		
			int maxLength = usedSectionNumbers.length;

			while (i < maxLength && position >= sectionToPosition.get(usedSectionNumbers[i])){
				i++;
			}
			return usedSectionNumbers[i-1];
		}

		@Override
		public Object[] getSections() {
			return indexer.getSections();
		}

		//nothing much to this: headers have positions that the sectionIndexer manages.
		@Override
		public int getItemViewType(int position) {
			if (position == getPositionForSection(getSectionForPosition(position))){
				return TYPE_HEADER;
			} return TYPE_NORMAL;
		}

		@Override
		public int getViewTypeCount() {
			return TYPE_COUNT;
		}

		//return the header view, if it's in a section header position
		@Override
		public View getView(int position, View convertView, ViewGroup parent) {
			final int type = getItemViewType(position);
			if (type == TYPE_HEADER){
				if (convertView == null){
					convertView = getLayoutInflater().inflate(R.layout.header, parent, false); 
				}
				((TextView)convertView.findViewById(R.id.header)).setText((String)getSections()[getSectionForPosition(position)]);
				return convertView;
			}
			return super.getView(position - sectionToOffset.get(getSectionForPosition(position)) - 1, convertView, parent); 
		}


		//these two methods just disable the headers
		@Override
		public boolean areAllItemsEnabled() {
			return false;
		}

		@Override
		public boolean isEnabled(int position) {
			if (getItemViewType(position) == TYPE_HEADER){
				return false;
			}
			return true;
		}
	}

Finally, make sure to make sure that fastScroll is enabled for your ListView, so you can take advantage of the sweet fast scrolling tab 🙂

There is one more subtle problem, which is if the size of the cursor changes (so say in the pictorial example, our data set only contains Apple, Banana, Cranberry now) and a new instance of this list adapter isn’t made, then must take care to redo all the pre-computation. If this is the case and the new cursor has non-zero count, then you might want to wrap the pre-computation in its own method and call it during onCursorChanged().

Edit: As requested by Nick, here is a full-working demo of this list adapter in action!

/**
 * ListActivity demonstrating using the AlphabetIndexer to derive section headers
 * @author Eric
 *
 */
public class DemoActivity extends ListActivity {

	private SQLiteDatabase db;
	
	@Override
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		
		//NOTE: you should never actually start database operations from the context of the UI thread
		final DbHelper helper = new DbHelper(this);
		db = helper.getWritableDatabase();
		
		//populate the db with our dummy data, might take a while, so in real scenarios spawn a 
		//new thread to do this
		final int result = helper.insertDummyData(db); 
		
		if (result > 0){ 
			//query the db to obtain our cursor and set the list adapter, only if the rows were 
			//successfully inserted
			
			final Cursor cursor = db.query(DbHelper.TABLE_COUNTRIES, null, null, 
					null, null, null, DbHelper.COUNTRIES_NAME + " ASC" );
			startManagingCursor(cursor);
			Toast.makeText(this, "Finished populating.", Toast.LENGTH_SHORT).show();	
			
			setListAdapter(new MyAlphabetizedAdapter(this, android.R.layout.simple_list_item_1, 
					cursor, new String[]{DbHelper.COUNTRIES_NAME}, new int[]{android.R.id.text1}));
			
			//don't ever forget to do this, either here or in your ListView layout
			getListView().setFastScrollEnabled(true);
			
		} else {
			Toast.makeText(this, "Database could not be populated. Restart the activity.", Toast.LENGTH_LONG).show();	
		}

	}

	@Override
	protected void onDestroy() {
		db.close();
		super.onDestroy();
	}

	/**
	 * CursorAdapter that uses an AlphabetIndexer widget to keep track of the section indicies.
	 * These are the positions where we want to show a section header showing the respective alphabet letter.
	 * @author Eric
	 *
	 */
	public class MyAlphabetizedAdapter extends SimpleCursorAdapter implements SectionIndexer{

		private static final int TYPE_HEADER = 1;
		private static final int TYPE_NORMAL = 0;

		private static final int TYPE_COUNT = 2;

		private AlphabetIndexer indexer;

		private int[] usedSectionNumbers;

		private Map<Integer, Integer> sectionToOffset;
		private Map<Integer, Integer> sectionToPosition;
	
		public MyAlphabetizedAdapter(Context context, int layout, Cursor c,
				String[] from, int[] to) {
			super(context, layout, c, from, to);
			
			indexer = new AlphabetIndexer(c, c.getColumnIndexOrThrow(DbHelper.COUNTRIES_NAME), "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
			sectionToPosition = new TreeMap<Integer, Integer>(); //use a TreeMap because we are going to iterate over its keys in sorted order
			sectionToOffset = new HashMap<Integer, Integer>();

			final int count = super.getCount();
			
			int i;
			//temporarily have a map alphabet section to first index it appears
			//(this map is going to be doing somethine else later)
			for (i = count - 1 ; i >= 0; i--){
				sectionToPosition.put(indexer.getSectionForPosition(i), i);
			}

			i = 0;
			usedSectionNumbers = new int[sectionToPosition.keySet().size()];
			
			//note that for each section that appears before a position, we must offset our
			//indices by 1, to make room for an alphabetical header in our list
			for (Integer section : sectionToPosition.keySet()){
				sectionToOffset.put(section, i);
				usedSectionNumbers[i] = section;
				i++;
			}

			//use offset to map the alphabet sections to their actual indicies in the list
			for(Integer section: sectionToPosition.keySet()){
				sectionToPosition.put(section, sectionToPosition.get(section) + sectionToOffset.get(section));
			}
		}

		@Override
		public int getCount() {
			if (super.getCount() != 0){
				//sometimes your data set gets invalidated. In this case getCount()
				//should return 0 and not our adjusted count for the headers.
				//The only way to know if data is invalidated is to check if
				//super.getCount() is 0.
				return super.getCount() + usedSectionNumbers.length;
			}
			
			return 0;
		}
		
		@Override
		public Object getItem(int position) {
			if (getItemViewType(position) == TYPE_NORMAL){//we define this function in the full code later
				//if the list item is not a header, then we fetch the data set item with the same position
				//off-setted by the number of headers that appear before the item in the list
				return super.getItem(position - sectionToOffset.get(getSectionForPosition(position)) - 1);
			}

			return null;
		}

		@Override
		public int getPositionForSection(int section) {
			if (! sectionToOffset.containsKey(section)){ 
				//This is only the case when the FastScroller is scrolling,
				//and so this section doesn't appear in our data set. The implementation
				//of Fastscroller requires that missing sections have the same index as the
				//beginning of the next non-missing section (or the end of the the list if 
				//if the rest of the sections are missing).
				//So, in pictorial example, the sections D and E would appear at position 9
				//and G to Z appear in position 11.
				int i = 0;
				int maxLength = usedSectionNumbers.length;
				
				//linear scan over the sections (constant number of these) that appear in the 
				//data set to find the first used section that is greater than the given section, so in the
				//example D and E correspond to F
				while (i < maxLength && section > usedSectionNumbers[i]){
					i++;
				}
				if (i == maxLength) return getCount(); //the given section is past all our data

				return indexer.getPositionForSection(usedSectionNumbers[i]) + sectionToOffset.get(usedSectionNumbers[i]);
			}

			return indexer.getPositionForSection(section) + sectionToOffset.get(section);
		}

		@Override
		public int getSectionForPosition(int position) {
			int i = 0;		
			int maxLength = usedSectionNumbers.length;
	
			//linear scan over the used alphabetical sections' positions
			//to find where the given section fits in
			while (i < maxLength && position >= sectionToPosition.get(usedSectionNumbers[i])){
				i++;
			}
			return usedSectionNumbers[i-1];
		}

		@Override
		public Object[] getSections() {
			return indexer.getSections();
		}
		//nothing much to this: headers have positions that the sectionIndexer manages.
		@Override
		public int getItemViewType(int position) {
			if (position == getPositionForSection(getSectionForPosition(position))){
				return TYPE_HEADER;
			} return TYPE_NORMAL;
		}

		@Override
		public int getViewTypeCount() {
			return TYPE_COUNT;
		}

		//return the header view, if it's in a section header position
		@Override
		public View getView(int position, View convertView, ViewGroup parent) {
			final int type = getItemViewType(position);
			if (type == TYPE_HEADER){
				if (convertView == null){
					convertView = getLayoutInflater().inflate(R.layout.header, parent, false); 
				}
				((TextView)convertView.findViewById(R.id.header)).setText((String)getSections()[getSectionForPosition(position)]);
				return convertView;
			}
			return super.getView(position - sectionToOffset.get(getSectionForPosition(position)) - 1, convertView, parent); 
		}


		//these two methods just disable the headers
		@Override
		public boolean areAllItemsEnabled() {
			return false;
		}

		@Override
		public boolean isEnabled(int position) {
			if (getItemViewType(position) == TYPE_HEADER){
				return false;
			}
			return true;
		}
	}
}

/**
 * A database helper to create the db table with country names
 * @author Eric
 *
 */
public class DbHelper extends SQLiteOpenHelper {

	public static final String TABLE_COUNTRIES = "countries";
	public static final String COUNTRIES_NAME = "name";

	private static final String DATABASE_NAME = "alphabetical_tutorial.db";
	private static final int DATABASE_VERSION = 1;

	public DbHelper(Context context) {
		super(context, DATABASE_NAME, null, DATABASE_VERSION);
	}

	@Override
	public void onCreate(SQLiteDatabase db) {
		db.execSQL("create table " + TABLE_COUNTRIES + " (" + 
				BaseColumns._ID + " integer primary key autoincrement,"
				+ COUNTRIES_NAME + " text not null,"
				+ "unique (" + COUNTRIES_NAME + ") on conflict replace)");
	}

	@Override
	public void onUpgrade(SQLiteDatabase db, int oldVersion, int newVersion) {
		db.execSQL("drop table exists" + TABLE_COUNTRIES);
		onCreate(db);
	}

	/**
	 * Inserts the list of country names into the db.
	 * We use SQL transactions for data integrity and efficiency.
	 * @param db
	 * @return
	 */
	public int insertDummyData(SQLiteDatabase db){
		int numInserted = 0;
		db.beginTransaction();
		try {
			SQLiteStatement insert = db.compileStatement("insert into " + 
					TABLE_COUNTRIES + "(" + COUNTRIES_NAME + ")" 
					+ "values " + "(?)");
			for (String country : COUNTRIES){
				insert.bindString(1, country);
				insert.execute();
			}
			db.setTransactionSuccessful();
			numInserted = COUNTRIES.length;
		} finally {
			db.endTransaction();
		}
		return numInserted;
	}

	//borrow the list of countries from the ListView tutorial on developer.android.com/
	static final String[] COUNTRIES = new String[] {
		"Afghanistan", "Albania", "Algeria", "American Samoa", "Andorra",
		"Angola", "Anguilla", "Antarctica", "Antigua and Barbuda", "Argentina",
		"Armenia", "Aruba", "Australia", "Austria", "Azerbaijan",
		"Bahrain", "Bangladesh", "Barbados", "Belarus", "Belgium",
		"Belize", "Benin", "Bermuda", "Bhutan", "Bolivia",
		"Bosnia and Herzegovina", "Botswana", "Bouvet Island", "Brazil", "British Indian Ocean Territory",
		"British Virgin Islands", "Brunei", "Bulgaria", "Burkina Faso", "Burundi",
		"Cote d'Ivoire", "Cambodia", "Cameroon", "Canada", "Cape Verde",
		"Cayman Islands", "Central African Republic", "Chad", "Chile", "China",
		"Christmas Island", "Cocos (Keeling) Islands", "Colombia", "Comoros", "Congo",
		"Cook Islands", "Costa Rica", "Croatia", "Cuba", "Cyprus", "Czech Republic",
		"Democratic Republic of the Congo", "Denmark", "Djibouti", "Dominica", "Dominican Republic",
		"East Timor", "Ecuador", "Egypt", "El Salvador", "Equatorial Guinea", "Eritrea",
		"Estonia", "Ethiopia", "Faeroe Islands", "Falkland Islands", "Fiji", "Finland",
		"Former Yugoslav Republic of Macedonia", "France", "French Guiana", "French Polynesia",
		"French Southern Territories", "Gabon", "Georgia", "Germany", "Ghana", "Gibraltar",
		"Greece", "Greenland", "Grenada", "Guadeloupe", "Guam", "Guatemala", "Guinea", "Guinea-Bissau",
		"Guyana", "Haiti", "Heard Island and McDonald Islands", "Honduras", "Hong Kong", "Hungary",
		"Iceland", "India", "Indonesia", "Iran", "Iraq", "Ireland", "Israel", "Italy", "Jamaica",
		"Japan", "Jordan", "Kazakhstan", "Kenya", "Kiribati", "Kuwait", "Kyrgyzstan", "Laos",
		"Latvia", "Lebanon", "Lesotho", "Liberia", "Libya", "Liechtenstein", "Lithuania", "Luxembourg",
		"Macau", "Madagascar", "Malawi", "Malaysia", "Maldives", "Mali", "Malta", "Marshall Islands",
		"Martinique", "Mauritania", "Mauritius", "Mayotte", "Mexico", "Micronesia", "Moldova",
		"Monaco", "Mongolia", "Montserrat", "Morocco", "Mozambique", "Myanmar", "Namibia",
		"Nauru", "Nepal", "Netherlands", "Netherlands Antilles", "New Caledonia", "New Zealand",
		"Nicaragua", "Niger", "Nigeria", "Niue", "Norfolk Island", "North Korea", "Northern Marianas",
		"Norway", "Oman", "Pakistan", "Palau", "Panama", "Papua New Guinea", "Paraguay", "Peru",
		"Philippines", "Pitcairn Islands", "Poland", "Portugal", "Puerto Rico", "Qatar",
		"Reunion", "Romania", "Russia", "Rwanda", "Sqo Tome and Principe", "Saint Helena",
		"Saint Kitts and Nevis", "Saint Lucia", "Saint Pierre and Miquelon",
		"Saint Vincent and the Grenadines", "Samoa", "San Marino", "Saudi Arabia", "Senegal",
		"Seychelles", "Sierra Leone", "Singapore", "Slovakia", "Slovenia", "Solomon Islands",
		"Somalia", "South Africa", "South Georgia and the South Sandwich Islands", "South Korea",
		"Spain", "Sri Lanka", "Sudan", "Suriname", "Svalbard and Jan Mayen", "Swaziland", "Sweden",
		"Switzerland", "Syria", "Taiwan", "Tajikistan", "Tanzania", "Thailand", "The Bahamas",
		"The Gambia", "Togo", "Tokelau", "Tonga", "Trinidad and Tobago", "Tunisia", "Turkey",
		"Turkmenistan", "Turks and Caicos Islands", "Tuvalu", "Virgin Islands", "Uganda",
		"Ukraine", "United Arab Emirates", "United Kingdom",
		"United States", "United States Minor Outlying Islands", "Uruguay", "Uzbekistan",
		"Vanuatu", "Vatican City", "Venezuela", "Vietnam", "Wallis and Futuna", "Western Sahara",
		"Yemen", "Yugoslavia", "Zambia", "Zimbabwe"
	};
}

This also demonstrates using SQL transactions, which my next post is about.