AlphabetIndexer.java revision 1b111bb6e2a570fe5f88d018fb3ec3c1ae880dcc
1/* 2 * Copyright (C) 2008 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package android.widget; 18 19import android.database.Cursor; 20import android.database.DataSetObserver; 21import android.util.SparseIntArray; 22 23/** 24 * A helper class for adapters that implement the SectionIndexer interface. 25 * If the items in the adapter are sorted by simple alphabet-based sorting, then 26 * this class provides a way to do fast indexing of large lists using binary search. 27 * It caches the indices that have been determined through the binary search and also 28 * invalidates the cache if changes occur in the cursor. 29 * <p/> 30 * Your adapter is responsible for updating the cursor by calling {@link #setCursor} if the 31 * cursor changes. {@link #getPositionForSection} method does the binary search for the starting 32 * index of a given section (alphabet). 33 */ 34public class AlphabetIndexer extends DataSetObserver implements SectionIndexer { 35 36 /** 37 * Cursor that is used by the adapter of the list view. 38 */ 39 protected Cursor mDataCursor; 40 41 /** 42 * The index of the cursor column that this list is sorted on. 43 */ 44 protected int mColumnIndex; 45 46 /** 47 * The string of characters that make up the indexing sections. 48 */ 49 protected CharSequence mAlphabet; 50 51 /** 52 * Cached length of the alphabet array. 53 */ 54 private int mAlphabetLength; 55 56 /** 57 * This contains a cache of the computed indices so far. It will get reset whenever 58 * the dataset changes or the cursor changes. 59 */ 60 private SparseIntArray mAlphaMap; 61 62 /** 63 * Use a collator to compare strings in a localized manner. 64 */ 65 private java.text.Collator mCollator; 66 67 /** 68 * The section array converted from the alphabet string. 69 */ 70 private String[] mAlphabetArray; 71 72 /** 73 * Constructs the indexer. 74 * @param cursor the cursor containing the data set 75 * @param sortedColumnIndex the column number in the cursor that is sorted 76 * alphabetically 77 * @param alphabet string containing the alphabet, with space as the first character. 78 * For example, use the string " ABCDEFGHIJKLMNOPQRSTUVWXYZ" for English indexing. 79 * The characters must be uppercase and be sorted in ascii/unicode order. Basically 80 * characters in the alphabet will show up as preview letters. 81 */ 82 public AlphabetIndexer(Cursor cursor, int sortedColumnIndex, CharSequence alphabet) { 83 mDataCursor = cursor; 84 mColumnIndex = sortedColumnIndex; 85 mAlphabet = alphabet; 86 mAlphabetLength = alphabet.length(); 87 mAlphabetArray = new String[mAlphabetLength]; 88 for (int i = 0; i < mAlphabetLength; i++) { 89 mAlphabetArray[i] = Character.toString(mAlphabet.charAt(i)); 90 } 91 mAlphaMap = new SparseIntArray(mAlphabetLength); 92 if (cursor != null) { 93 cursor.registerDataSetObserver(this); 94 } 95 // Get a Collator for the current locale for string comparisons. 96 mCollator = java.text.Collator.getInstance(); 97 mCollator.setStrength(java.text.Collator.PRIMARY); 98 } 99 100 /** 101 * Returns the section array constructed from the alphabet provided in the constructor. 102 * @return the section array 103 */ 104 public Object[] getSections() { 105 return mAlphabetArray; 106 } 107 108 /** 109 * Sets a new cursor as the data set and resets the cache of indices. 110 * @param cursor the new cursor to use as the data set 111 */ 112 public void setCursor(Cursor cursor) { 113 if (mDataCursor != null) { 114 mDataCursor.unregisterDataSetObserver(this); 115 } 116 mDataCursor = cursor; 117 if (cursor != null) { 118 mDataCursor.registerDataSetObserver(this); 119 } 120 mAlphaMap.clear(); 121 } 122 123 /** 124 * Default implementation compares the first character of word with letter. 125 */ 126 protected int compare(String word, String letter) { 127 return mCollator.compare(word.substring(0, 1), letter); 128 } 129 130 /** 131 * Performs a binary search or cache lookup to find the first row that 132 * matches a given section's starting letter. 133 * @param sectionIndex the section to search for 134 * @return the row index of the first occurrence, or the nearest next letter. 135 * For instance, if searching for "T" and no "T" is found, then the first 136 * row starting with "U" or any higher letter is returned. If there is no 137 * data following "T" at all, then the list size is returned. 138 */ 139 public int getPositionForSection(int sectionIndex) { 140 final SparseIntArray alphaMap = mAlphaMap; 141 final Cursor cursor = mDataCursor; 142 143 if (cursor == null || mAlphabet == null) { 144 return 0; 145 } 146 147 // Check bounds 148 if (sectionIndex <= 0) { 149 return 0; 150 } 151 if (sectionIndex >= mAlphabetLength) { 152 sectionIndex = mAlphabetLength - 1; 153 } 154 155 int savedCursorPos = cursor.getPosition(); 156 157 int count = cursor.getCount(); 158 int start = 0; 159 int end = count; 160 int pos; 161 162 char letter = mAlphabet.charAt(sectionIndex); 163 String targetLetter = Character.toString(letter); 164 int key = letter; 165 // Check map 166 if (Integer.MIN_VALUE != (pos = alphaMap.get(key, Integer.MIN_VALUE))) { 167 // Is it approximate? Using negative value to indicate that it's 168 // an approximation and positive value when it is the accurate 169 // position. 170 if (pos < 0) { 171 pos = -pos; 172 end = pos; 173 } else { 174 // Not approximate, this is the confirmed start of section, return it 175 return pos; 176 } 177 } 178 179 // Do we have the position of the previous section? 180 if (sectionIndex > 0) { 181 int prevLetter = 182 mAlphabet.charAt(sectionIndex - 1); 183 int prevLetterPos = alphaMap.get(prevLetter, Integer.MIN_VALUE); 184 if (prevLetterPos != Integer.MIN_VALUE) { 185 start = Math.abs(prevLetterPos); 186 } 187 } 188 189 // Now that we have a possibly optimized start and end, let's binary search 190 191 pos = (end + start) / 2; 192 193 while (pos < end) { 194 // Get letter at pos 195 cursor.moveToPosition(pos); 196 String curName = cursor.getString(mColumnIndex); 197 if (curName == null) { 198 if (pos == 0) { 199 break; 200 } else { 201 pos--; 202 continue; 203 } 204 } 205 int diff = compare(curName, targetLetter); 206 if (diff != 0) { 207 // Commenting out approximation code because it doesn't work for certain 208 // lists with custom comparators 209 // Enter approximation in hash if a better solution doesn't exist 210 // String startingLetter = Character.toString(getFirstLetter(curName)); 211 // int startingLetterKey = startingLetter.charAt(0); 212 // int curPos = alphaMap.get(startingLetterKey, Integer.MIN_VALUE); 213 // if (curPos == Integer.MIN_VALUE || Math.abs(curPos) > pos) { 214 // Negative pos indicates that it is an approximation 215 // alphaMap.put(startingLetterKey, -pos); 216 // } 217 // if (mCollator.compare(startingLetter, targetLetter) < 0) { 218 if (diff < 0) { 219 start = pos + 1; 220 if (start >= count) { 221 pos = count; 222 break; 223 } 224 } else { 225 end = pos; 226 } 227 } else { 228 // They're the same, but that doesn't mean it's the start 229 if (start == pos) { 230 // This is it 231 break; 232 } else { 233 // Need to go further lower to find the starting row 234 end = pos; 235 } 236 } 237 pos = (start + end) / 2; 238 } 239 alphaMap.put(key, pos); 240 cursor.moveToPosition(savedCursorPos); 241 return pos; 242 } 243 244 /** 245 * Returns the section index for a given position in the list by querying the item 246 * and comparing it with all items in the section array. 247 */ 248 public int getSectionForPosition(int position) { 249 int savedCursorPos = mDataCursor.getPosition(); 250 mDataCursor.moveToPosition(position); 251 String curName = mDataCursor.getString(mColumnIndex); 252 mDataCursor.moveToPosition(savedCursorPos); 253 // Linear search, as there are only a few items in the section index 254 // Could speed this up later if it actually gets used. 255 for (int i = 0; i < mAlphabetLength; i++) { 256 char letter = mAlphabet.charAt(i); 257 String targetLetter = Character.toString(letter); 258 if (compare(curName, targetLetter) == 0) { 259 return i; 260 } 261 } 262 return 0; // Don't recognize the letter - falls under zero'th section 263 } 264 265 /* 266 * @hide 267 */ 268 @Override 269 public void onChanged() { 270 super.onChanged(); 271 mAlphaMap.clear(); 272 } 273 274 /* 275 * @hide 276 */ 277 @Override 278 public void onInvalidated() { 279 super.onInvalidated(); 280 mAlphaMap.clear(); 281 } 282} 283