/*
* Copyright (C) 2008 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package android.widget;
import android.database.Cursor;
import android.database.DataSetObserver;
import android.util.SparseIntArray;
/**
* 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.
* <p/>
* 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).
*/
public class AlphabetIndexer extends DataSetObserver implements SectionIndexer {
/**
* Cursor that is used by the adapter of the list view.
*/
protected Cursor mDataCursor;
/**
* The index of the cursor column that this list is sorted on.
*/
protected int mColumnIndex;
/**
* The string of characters that make up the indexing sections.
*/
protected CharSequence mAlphabet;
/**
* Cached length of the alphabet array.
*/
private int mAlphabetLength;
/**
* This contains a cache of the computed indices so far. It will get reset whenever
* the dataset changes or the cursor changes.
*/
private SparseIntArray mAlphaMap;
/**
* Use a collator to compare strings in a localized manner.
*/
private java.text.Collator mCollator;
/**
* The section array converted from the alphabet string.
*/
private String[] mAlphabetArray;
/**
* 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.
*/
public AlphabetIndexer(Cursor cursor, int sortedColumnIndex, CharSequence alphabet) {
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);
}
/**
* Returns the section array constructed from the alphabet provided in the constructor.
* @return the section array
*/
public Object[] getSections() {
return mAlphabetArray;
}
/**
* 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
*/
public void setCursor(Cursor cursor) {
if (mDataCursor != null) {
mDataCursor.unregisterDataSetObserver(this);
}
mDataCursor = cursor;
if (cursor != null) {
mDataCursor.registerDataSetObserver(this);
}
mAlphaMap.clear();
}
/**
* Default implementation compares the first character of word with letter.
*/
protected int compare(String word, String letter) {
final String firstLetter;
if (word.length() == 0) {
firstLetter = " ";
} else {
firstLetter = word.substring(0, 1);
}
return mCollator.compare(firstLetter, letter);
}
/**
* 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.
*/
public int getPositionForSection(int sectionIndex) {
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) {
// TODO: 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;
}
/**
* 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.
*/
public int getSectionForPosition(int position) {
int savedCursorPos = mDataCursor.getPosition();
mDataCursor.moveToPosition(position);
String curName = mDataCursor.getString(mColumnIndex);
mDataCursor.moveToPosition(savedCursorPos);
// 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
}
/*
* @hide
*/
@Override
public void onChanged() {
super.onChanged();
mAlphaMap.clear();
}
/*
* @hide
*/
@Override
public void onInvalidated() {
super.onInvalidated();
mAlphaMap.clear();
}
}
|
