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