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 17 package android.widget; 18 19 import android.database.Cursor; 20 import android.database.DataSetObserver; 21 import 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 */ 34 public 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 final String firstLetter; 128 if (word.length() == 0) { 129 firstLetter = " "; 130 } else { 131 firstLetter = word.substring(0, 1); 132 } 133 134 return mCollator.compare(firstLetter, letter); 135 } 136 137 /** 138 * Performs a binary search or cache lookup to find the first row that 139 * matches a given section's starting letter. 140 * @param sectionIndex the section to search for 141 * @return the row index of the first occurrence, or the nearest next letter. 142 * For instance, if searching for "T" and no "T" is found, then the first 143 * row starting with "U" or any higher letter is returned. If there is no 144 * data following "T" at all, then the list size is returned. 145 */ 146 public int getPositionForSection(int sectionIndex) { 147 final SparseIntArray alphaMap = mAlphaMap; 148 final Cursor cursor = mDataCursor; 149 150 if (cursor == null || mAlphabet == null) { 151 return 0; 152 } 153 154 // Check bounds 155 if (sectionIndex <= 0) { 156 return 0; 157 } 158 if (sectionIndex >= mAlphabetLength) { 159 sectionIndex = mAlphabetLength - 1; 160 } 161 162 int savedCursorPos = cursor.getPosition(); 163 164 int count = cursor.getCount(); 165 int start = 0; 166 int end = count; 167 int pos; 168 169 char letter = mAlphabet.charAt(sectionIndex); 170 String targetLetter = Character.toString(letter); 171 int key = letter; 172 // Check map 173 if (Integer.MIN_VALUE != (pos = alphaMap.get(key, Integer.MIN_VALUE))) { 174 // Is it approximate? Using negative value to indicate that it's 175 // an approximation and positive value when it is the accurate 176 // position. 177 if (pos < 0) { 178 pos = -pos; 179 end = pos; 180 } else { 181 // Not approximate, this is the confirmed start of section, return it 182 return pos; 183 } 184 } 185 186 // Do we have the position of the previous section? 187 if (sectionIndex > 0) { 188 int prevLetter = 189 mAlphabet.charAt(sectionIndex - 1); 190 int prevLetterPos = alphaMap.get(prevLetter, Integer.MIN_VALUE); 191 if (prevLetterPos != Integer.MIN_VALUE) { 192 start = Math.abs(prevLetterPos); 193 } 194 } 195 196 // Now that we have a possibly optimized start and end, let's binary search 197 198 pos = (end + start) / 2; 199 200 while (pos < end) { 201 // Get letter at pos 202 cursor.moveToPosition(pos); 203 String curName = cursor.getString(mColumnIndex); 204 if (curName == null) { 205 if (pos == 0) { 206 break; 207 } else { 208 pos--; 209 continue; 210 } 211 } 212 int diff = compare(curName, targetLetter); 213 if (diff != 0) { 214 // TODO: Commenting out approximation code because it doesn't work for certain 215 // lists with custom comparators 216 // Enter approximation in hash if a better solution doesn't exist 217 // String startingLetter = Character.toString(getFirstLetter(curName)); 218 // int startingLetterKey = startingLetter.charAt(0); 219 // int curPos = alphaMap.get(startingLetterKey, Integer.MIN_VALUE); 220 // if (curPos == Integer.MIN_VALUE || Math.abs(curPos) > pos) { 221 // Negative pos indicates that it is an approximation 222 // alphaMap.put(startingLetterKey, -pos); 223 // } 224 // if (mCollator.compare(startingLetter, targetLetter) < 0) { 225 if (diff < 0) { 226 start = pos + 1; 227 if (start >= count) { 228 pos = count; 229 break; 230 } 231 } else { 232 end = pos; 233 } 234 } else { 235 // They're the same, but that doesn't mean it's the start 236 if (start == pos) { 237 // This is it 238 break; 239 } else { 240 // Need to go further lower to find the starting row 241 end = pos; 242 } 243 } 244 pos = (start + end) / 2; 245 } 246 alphaMap.put(key, pos); 247 cursor.moveToPosition(savedCursorPos); 248 return pos; 249 } 250 251 /** 252 * Returns the section index for a given position in the list by querying the item 253 * and comparing it with all items in the section array. 254 */ 255 public int getSectionForPosition(int position) { 256 int savedCursorPos = mDataCursor.getPosition(); 257 mDataCursor.moveToPosition(position); 258 String curName = mDataCursor.getString(mColumnIndex); 259 mDataCursor.moveToPosition(savedCursorPos); 260 // Linear search, as there are only a few items in the section index 261 // Could speed this up later if it actually gets used. 262 for (int i = 0; i < mAlphabetLength; i++) { 263 char letter = mAlphabet.charAt(i); 264 String targetLetter = Character.toString(letter); 265 if (compare(curName, targetLetter) == 0) { 266 return i; 267 } 268 } 269 return 0; // Don't recognize the letter - falls under zero'th section 270 } 271 272 /* 273 * @hide 274 */ 275 @Override 276 public void onChanged() { 277 super.onChanged(); 278 mAlphaMap.clear(); 279 } 280 281 /* 282 * @hide 283 */ 284 @Override 285 public void onInvalidated() { 286 super.onInvalidated(); 287 mAlphaMap.clear(); 288 } 289 } 290
