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