core/java/android/widget/AlphabetIndexer.java - platform/frameworks/base - Git at Google

 /*
  * 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();
     }
 }
	/*
	* 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();
	}
	}