19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Copyright (C) 2008 The Android Open Source Project 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * you may not use this file except in compliance with the License. 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * You may obtain a copy of the License at 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * See the License for the specific language governing permissions and 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * limitations under the License. 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpackage android.widget; 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport android.database.Cursor; 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport android.database.DataSetObserver; 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport android.util.SparseIntArray; 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/** 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * A helper class for adapters that implement the SectionIndexer interface. 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * If the items in the adapter are sorted by simple alphabet-based sorting, then 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * this class provides a way to do fast indexing of large lists using binary search. 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * It caches the indices that have been determined through the binary search and also 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * invalidates the cache if changes occur in the cursor. 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * <p/> 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Your adapter is responsible for updating the cursor by calling {@link #setCursor} if the 310918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov * cursor changes. {@link #getPositionForSection} method does the binary search for the starting 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * index of a given section (alphabet). 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpublic class AlphabetIndexer extends DataSetObserver implements SectionIndexer { 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Cursor that is used by the adapter of the list view. 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project protected Cursor mDataCursor; 400918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * The index of the cursor column that this list is sorted on. 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project protected int mColumnIndex; 450918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * The string of characters that make up the indexing sections. 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project protected CharSequence mAlphabet; 500918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Cached length of the alphabet array. 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private int mAlphabetLength; 550918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * This contains a cache of the computed indices so far. It will get reset whenever 589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * the dataset changes or the cursor changes. 599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private SparseIntArray mAlphaMap; 610918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Use a collator to compare strings in a localized manner. 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private java.text.Collator mCollator; 660918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * The section array converted from the alphabet string. 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private String[] mAlphabetArray; 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Constructs the indexer. 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param cursor the cursor containing the data set 750918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov * @param sortedColumnIndex the column number in the cursor that is sorted 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * alphabetically 770918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov * @param alphabet string containing the alphabet, with space as the first character. 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * For example, use the string " ABCDEFGHIJKLMNOPQRSTUVWXYZ" for English indexing. 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * The characters must be uppercase and be sorted in ascii/unicode order. Basically 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * characters in the alphabet will show up as preview letters. 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public AlphabetIndexer(Cursor cursor, int sortedColumnIndex, CharSequence alphabet) { 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mDataCursor = cursor; 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mColumnIndex = sortedColumnIndex; 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mAlphabet = alphabet; 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mAlphabetLength = alphabet.length(); 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mAlphabetArray = new String[mAlphabetLength]; 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = 0; i < mAlphabetLength; i++) { 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mAlphabetArray[i] = Character.toString(mAlphabet.charAt(i)); 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mAlphaMap = new SparseIntArray(mAlphabetLength); 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cursor != null) { 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cursor.registerDataSetObserver(this); 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Get a Collator for the current locale for string comparisons. 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mCollator = java.text.Collator.getInstance(); 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mCollator.setStrength(java.text.Collator.PRIMARY); 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns the section array constructed from the alphabet provided in the constructor. 1029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return the section array 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public Object[] getSections() { 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mAlphabetArray; 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1070918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Sets a new cursor as the data set and resets the cache of indices. 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param cursor the new cursor to use as the data set 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void setCursor(Cursor cursor) { 1139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mDataCursor != null) { 1149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mDataCursor.unregisterDataSetObserver(this); 1159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mDataCursor = cursor; 1179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cursor != null) { 1189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mDataCursor.registerDataSetObserver(this); 1199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mAlphaMap.clear(); 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Default implementation compares the first character of word with letter. 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project protected int compare(String word, String letter) { 1270918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov final String firstLetter; 1280918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov if (word.length() == 0) { 1290918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov firstLetter = " "; 1300918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov } else { 1310918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov firstLetter = word.substring(0, 1); 1320918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov } 1330918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 1340918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov return mCollator.compare(firstLetter, letter); 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1360918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Performs a binary search or cache lookup to find the first row that 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * matches a given section's starting letter. 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @param sectionIndex the section to search for 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @return the row index of the first occurrence, or the nearest next letter. 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * For instance, if searching for "T" and no "T" is found, then the first 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * row starting with "U" or any higher letter is returned. If there is no 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * data following "T" at all, then the list size is returned. 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int getPositionForSection(int sectionIndex) { 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project final SparseIntArray alphaMap = mAlphaMap; 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project final Cursor cursor = mDataCursor; 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (cursor == null || mAlphabet == null) { 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1530918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Check bounds 1559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (sectionIndex <= 0) { 1569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 1579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (sectionIndex >= mAlphabetLength) { 1599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project sectionIndex = mAlphabetLength - 1; 1609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int savedCursorPos = cursor.getPosition(); 1639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int count = cursor.getCount(); 1659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int start = 0; 1669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int end = count; 1679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int pos; 1689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char letter = mAlphabet.charAt(sectionIndex); 1709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project String targetLetter = Character.toString(letter); 1719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int key = letter; 1729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Check map 1739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (Integer.MIN_VALUE != (pos = alphaMap.get(key, Integer.MIN_VALUE))) { 1740918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov // Is it approximate? Using negative value to indicate that it's 1759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // an approximation and positive value when it is the accurate 1769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // position. 1779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (pos < 0) { 1789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project pos = -pos; 1799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project end = pos; 1809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 1819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Not approximate, this is the confirmed start of section, return it 1829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return pos; 1839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Do we have the position of the previous section? 1879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (sectionIndex > 0) { 1889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int prevLetter = 1899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mAlphabet.charAt(sectionIndex - 1); 1909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int prevLetterPos = alphaMap.get(prevLetter, Integer.MIN_VALUE); 1919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (prevLetterPos != Integer.MIN_VALUE) { 1929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project start = Math.abs(prevLetterPos); 1939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Now that we have a possibly optimized start and end, let's binary search 1979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project pos = (end + start) / 2; 1999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (pos < end) { 2019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Get letter at pos 2029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cursor.moveToPosition(pos); 2039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project String curName = cursor.getString(mColumnIndex); 2049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (curName == null) { 2059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (pos == 0) { 2069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 2079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 2089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project pos--; 2099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project continue; 2109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int diff = compare(curName, targetLetter); 2139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (diff != 0) { 2140918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov // TODO: Commenting out approximation code because it doesn't work for certain 2159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // lists with custom comparators 2169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Enter approximation in hash if a better solution doesn't exist 2179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // String startingLetter = Character.toString(getFirstLetter(curName)); 2189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // int startingLetterKey = startingLetter.charAt(0); 2199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // int curPos = alphaMap.get(startingLetterKey, Integer.MIN_VALUE); 2209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // if (curPos == Integer.MIN_VALUE || Math.abs(curPos) > pos) { 2219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Negative pos indicates that it is an approximation 2229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // alphaMap.put(startingLetterKey, -pos); 2239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // } 2249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // if (mCollator.compare(startingLetter, targetLetter) < 0) { 2259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (diff < 0) { 2269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project start = pos + 1; 2279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (start >= count) { 2289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project pos = count; 2299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 2309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 2329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project end = pos; 2339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 2359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // They're the same, but that doesn't mean it's the start 2369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (start == pos) { 2379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // This is it 2389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 2399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 2409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Need to go further lower to find the starting row 2419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project end = pos; 2429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project pos = (start + end) / 2; 2459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project alphaMap.put(key, pos); 2479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project cursor.moveToPosition(savedCursorPos); 2489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return pos; 2499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 2529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns the section index for a given position in the list by querying the item 2539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * and comparing it with all items in the section array. 2549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 2559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int getSectionForPosition(int position) { 2569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int savedCursorPos = mDataCursor.getPosition(); 2579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mDataCursor.moveToPosition(position); 2589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project String curName = mDataCursor.getString(mColumnIndex); 2591b111bb6e2a570fe5f88d018fb3ec3c1ae880dccPhil Dubach mDataCursor.moveToPosition(savedCursorPos); 2609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Linear search, as there are only a few items in the section index 2619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Could speed this up later if it actually gets used. 2629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = 0; i < mAlphabetLength; i++) { 2639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project char letter = mAlphabet.charAt(i); 2649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project String targetLetter = Character.toString(letter); 2659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (compare(curName, targetLetter) == 0) { 2669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return i; 2679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2690918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov return 0; // Don't recognize the letter - falls under zero'th section 2709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2710918bf06881f32e6e3cf750f713b16c7d65e4012Dmitri Plotnikov 2729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* 2739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @hide 2749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 2759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project @Override 2769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void onChanged() { 2779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project super.onChanged(); 2789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mAlphaMap.clear(); 2799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* 2829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * @hide 2839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 2849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project @Override 2859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void onInvalidated() { 2869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project super.onInvalidated(); 2879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mAlphaMap.clear(); 2889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 290