FileDocCategorySizeDatePackage
AlphabetIndexer.javaAPI DocAndroid 1.5 API10073Wed May 06 22:41:56 BST 2009android.widget

AlphabetIndexer

public class AlphabetIndexer extends android.database.DataSetObserver implements SectionIndexer
A helper class for adapters that implement the SectionIndexer interface. If the items in the adapter are sorted by simple alphabet-based sorting, then this class provides a way to do fast indexing of large lists using binary search. It caches the indices that have been determined through the binary search and also invalidates the cache if changes occur in the cursor.

Your adapter is responsible for updating the cursor by calling {@link #setCursor} if the cursor changes. {@link #getPositionForSection} method does the binary search for the starting index of a given section (alphabet).

Fields Summary
protected android.database.Cursor
mDataCursor
Cursor that is used by the adapter of the list view.
protected int
mColumnIndex
The index of the cursor column that this list is sorted on.
protected CharSequence
mAlphabet
The string of characters that make up the indexing sections.
private int
mAlphabetLength
Cached length of the alphabet array.
private android.util.SparseIntArray
mAlphaMap
This contains a cache of the computed indices so far. It will get reset whenever the dataset changes or the cursor changes.
private Collator
mCollator
Use a collator to compare strings in a localized manner.
private String[]
mAlphabetArray
The section array converted from the alphabet string.
Constructors Summary
public AlphabetIndexer(android.database.Cursor cursor, int sortedColumnIndex, CharSequence alphabet)
Constructs the indexer.

param
cursor the cursor containing the data set
param
sortedColumnIndex the column number in the cursor that is sorted alphabetically
param
alphabet string containing the alphabet, with space as the first character. For example, use the string " ABCDEFGHIJKLMNOPQRSTUVWXYZ" for English indexing. The characters must be uppercase and be sorted in ascii/unicode order. Basically characters in the alphabet will show up as preview letters.

        mDataCursor = cursor;
        mColumnIndex = sortedColumnIndex;
        mAlphabet = alphabet;
        mAlphabetLength = alphabet.length();
        mAlphabetArray = new String[mAlphabetLength];
        for (int i = 0; i < mAlphabetLength; i++) {
            mAlphabetArray[i] = Character.toString(mAlphabet.charAt(i));
        }
        mAlphaMap = new SparseIntArray(mAlphabetLength);
        if (cursor != null) {
            cursor.registerDataSetObserver(this);
        }
        // Get a Collator for the current locale for string comparisons.
        mCollator = java.text.Collator.getInstance();
        mCollator.setStrength(java.text.Collator.PRIMARY);
Methods Summary
protected intcompare(java.lang.String word, java.lang.String letter)
Default implementation compares the first character of word with letter.

        return mCollator.compare(word.substring(0, 1), letter);
public intgetPositionForSection(int sectionIndex)
Performs a binary search or cache lookup to find the first row that matches a given section's starting letter.

param
sectionIndex the section to search for
return
the row index of the first occurrence, or the nearest next letter. For instance, if searching for "T" and no "T" is found, then the first row starting with "U" or any higher letter is returned. If there is no data following "T" at all, then the list size is returned.

        final SparseIntArray alphaMap = mAlphaMap;
        final Cursor cursor = mDataCursor;

        if (cursor == null || mAlphabet == null) {
            return 0;
        }
        
        // Check bounds
        if (sectionIndex <= 0) {
            return 0;
        }
        if (sectionIndex >= mAlphabetLength) {
            sectionIndex = mAlphabetLength - 1;
        }

        int savedCursorPos = cursor.getPosition();

        int count = cursor.getCount();
        int start = 0;
        int end = count;
        int pos;

        char letter = mAlphabet.charAt(sectionIndex);
        String targetLetter = Character.toString(letter);
        int key = letter;
        // Check map
        if (Integer.MIN_VALUE != (pos = alphaMap.get(key, Integer.MIN_VALUE))) {
            // Is it approximate? Using negative value to indicate that it's 
            // an approximation and positive value when it is the accurate
            // position.
            if (pos < 0) {
                pos = -pos;
                end = pos;
            } else {
                // Not approximate, this is the confirmed start of section, return it
                return pos;
            }
        }

        // Do we have the position of the previous section?
        if (sectionIndex > 0) {
            int prevLetter =
                    mAlphabet.charAt(sectionIndex - 1);
            int prevLetterPos = alphaMap.get(prevLetter, Integer.MIN_VALUE);
            if (prevLetterPos != Integer.MIN_VALUE) {
                start = Math.abs(prevLetterPos);
            }
        }

        // Now that we have a possibly optimized start and end, let's binary search

        pos = (end + start) / 2;

        while (pos < end) {
            // Get letter at pos
            cursor.moveToPosition(pos);
            String curName = cursor.getString(mColumnIndex);
            if (curName == null) {
                if (pos == 0) {
                    break;
                } else {
                    pos--;
                    continue;
                }
            }
            int diff = compare(curName, targetLetter);
            if (diff != 0) {
                // Commenting out approximation code because it doesn't work for certain 
                // lists with custom comparators
                // Enter approximation in hash if a better solution doesn't exist
                // String startingLetter = Character.toString(getFirstLetter(curName));
                // int startingLetterKey = startingLetter.charAt(0);
                // int curPos = alphaMap.get(startingLetterKey, Integer.MIN_VALUE);
                // if (curPos == Integer.MIN_VALUE || Math.abs(curPos) > pos) {
                //     Negative pos indicates that it is an approximation
                //     alphaMap.put(startingLetterKey, -pos);
                // }
                // if (mCollator.compare(startingLetter, targetLetter) < 0) {
                if (diff < 0) {
                    start = pos + 1;
                    if (start >= count) {
                        pos = count;
                        break;
                    }
                } else {
                    end = pos;
                }
            } else {
                // They're the same, but that doesn't mean it's the start
                if (start == pos) {
                    // This is it
                    break;
                } else {
                    // Need to go further lower to find the starting row
                    end = pos;
                }
            }
            pos = (start + end) / 2;
        }
        alphaMap.put(key, pos);
        cursor.moveToPosition(savedCursorPos);
        return pos;
public intgetSectionForPosition(int position)
Returns the section index for a given position in the list by querying the item and comparing it with all items in the section array.

        int savedCursorPos = mDataCursor.getPosition();
        mDataCursor.moveToPosition(position);
        mDataCursor.moveToPosition(savedCursorPos);
        String curName = mDataCursor.getString(mColumnIndex);
        // Linear search, as there are only a few items in the section index
        // Could speed this up later if it actually gets used.
        for (int i = 0; i < mAlphabetLength; i++) {
            char letter = mAlphabet.charAt(i);
            String targetLetter = Character.toString(letter);
            if (compare(curName, targetLetter) == 0) {
                return i;
            }
        }
        return 0; // Don't recognize the letter - falls under zero'th section
public java.lang.Object[]getSections()
Returns the section array constructed from the alphabet provided in the constructor.

return
the section array

        return mAlphabetArray;
public voidonChanged()

        super.onChanged();
        mAlphaMap.clear();
public voidonInvalidated()

        super.onInvalidated();
        mAlphaMap.clear();
public voidsetCursor(android.database.Cursor cursor)
Sets a new cursor as the data set and resets the cache of indices.

param
cursor the new cursor to use as the data set

        if (mDataCursor != null) {
            mDataCursor.unregisterDataSetObserver(this);
        }
        mDataCursor = cursor;
        if (cursor != null) {
            mDataCursor.registerDataSetObserver(this);
        }
        mAlphaMap.clear();