Home › Tutorials ›

Quick guide to quick autocomplete textview

Tue, 12/20/2011 - 14:55 | by balazs.nemeth

SDK Version: 
M3

This demo shows how to speed up the original autocomplete textview assuming that we can work with ordered data.

Let's prepare a simple test environment, which demostrate the difference between the two versions. Then let's generate a few thousand test data, and create two textviews from which we will speed up the second one.

  1. public class Main extends Activity {
  2.         AutoCompleteTextView mAutoCompleteTextViewOriginal;
  3.         AutoCompleteTextView mAutoCompleteTextViewQuick;
  4.  
  5.         @Override
  6.         public void onCreate(Bundle savedInstanceState) {
  7.                 super.onCreate(savedInstanceState);
  8.                 setContentView(R.layout.main);
  9.                
  10.                 String[] values =  createLongSortedStringArray(4);
  11.        
  12.                 mAutoCompleteTextViewOriginal = (AutoCompleteTextView) findViewById(R.id.autoCompleteTextViewOriginal);
  13.                 ArrayAdapter<String> originalAdapter = new ArrayAdapter<String>(this, R.layout.autocomplete_listitem, values);
  14.                 mAutoCompleteTextViewOriginal.setAdapter(originalAdapter);
  15.  
  16.                 mAutoCompleteTextViewQuick = (AutoCompleteTextView) findViewById(R.id.autoCompleteTextViewQuick);
  17.                 BinaryArrayAdapter<String> binaryAdapter = new BinaryArrayAdapter<String>(this, R.layout.autocomplete_listitem, values);
  18.                 mAutoCompleteTextViewQuick.setAdapter(binaryAdapter);
  19.         }
  20.  
  21.         private String[] createLongSortedStringArray(int length) {
  22.                 NumberFormat nf = NumberFormat.getInstance();
  23.                 nf.setMinimumIntegerDigits(length);
  24.                 nf.setMaximumIntegerDigits(length);
  25.                 nf.setGroupingUsed(false);
  26.  
  27.                 String[] values = new String[(int) Math.pow(10.0, (double)length)];
  28.                 for (int i = 0; i < values.length; i++) {
  29.                         values[i] = nf.format(i);
  30.                 }
  31.  
  32.                 return values;
  33.         }
  34. }

The elements are selected by the ArrayAdapter, and within that the ArrayFilter, which is an inner class. We can exchange this, if we overwrite the getFilter () method of the ArrayAdapter.

Unfortunately, we cannot give back the received result to the parent class because of the private mObjects member. After a half-day trial, a less elegant, but in a few minutes feasible solution was: we copy the whole ArrayAdapter class, and we exchange few rows which are necessary to the binary search.

The used search class is the following:

  1. public class BinarySearch<T> {
  2.         List<T> mList;
  3.  
  4.         Comparator<String> mComparator;
  5.  
  6.         /**
  7.          * Create Search list of item and comparator
  8.          *
  9.          * @param list
  10.          * @param comparator
  11.          */
  12.         public BinarySearch(List<T> list, Comparator<String> comparator) {
  13.                 mList = list;
  14.                 mComparator = comparator;
  15.         }
  16.  
  17.         /**
  18.          * Select sub list with given prefix
  19.          *
  20.          * @param prefixString
  21.          * @return
  22.          */
  23.         public List<T> select(String prefixString) {
  24.                 int first = findFirstIndex(0, mList.size() - 1, prefixString);;
  25.                 if (-1 == first) {
  26.                         return new ArrayList<T>();
  27.                 }
  28.  
  29.                 int last = findLastIndex(0, mList.size() - 1, prefixString);
  30.  
  31.                 return mList.subList(first, last + 1);
  32.         }
  33.  
  34.         private int findFirstIndex(int start, int end, String prefixString) {
  35.                 int size = end - start;
  36.                 if (size < 0) {
  37.                         return -1;
  38.                 }
  39.  
  40.                 if (size == 0) {
  41.                         if (mComparator.compare(mList.get(start).toString(), prefixString) == 0) {
  42.                                 return start;
  43.                         } else {
  44.                                 return -1;
  45.                         }
  46.                 } else {
  47.                         int half = (start + end) / 2;
  48.                         T halfItem = mList.get(half);
  49.                         String halfItemString = halfItem.toString();
  50.                         int result = mComparator.compare(halfItemString, prefixString);
  51.  
  52.                         if (result > 0) {
  53.                                 // Search in first half
  54.                                 return findFirstIndex(start, half - 1, prefixString);
  55.                         } else if (result < 0) {
  56.                                 // Search in second half
  57.                                 return findFirstIndex(half + 1, end, prefixString);
  58.                         } else /* if (result == 0) */{
  59.                                 // Search in first half
  60.                                 return findFirstIndex(start, half, prefixString);
  61.                         }
  62.                 }
  63.         }
  64.  
  65.         /**
  66.          * Find last index
  67.          *
  68.          * @param array
  69.          * @param prefixString
  70.          * @return
  71.          */
  72.         private int findLastIndex(int start, int end, String prefixString) {
  73.                 int size = end - start;
  74.                 if (size < 0) {
  75.                         return -1;
  76.                 }
  77.  
  78.                 if (size == 0) {
  79.                         if (mComparator.compare(mList.get(start).toString(), prefixString) == 0) {
  80.                                 return start;
  81.                         } else {
  82.                                 return -1;
  83.                         }
  84.                 } else {
  85.                         int half = (start + end + 1) / 2;
  86.                         T halfItem = mList.get(half);
  87.                         String halfItemString = halfItem.toString();
  88.                         int result = mComparator.compare(halfItemString, prefixString);
  89.                         if (result > 0) {
  90.                                 // Search in first half
  91.                                 return findLastIndex(start, half - 1, prefixString);
  92.                         } else if (mComparator.compare(halfItemString, prefixString) < 0) {
  93.                                 // Search in second half
  94.                                 return findLastIndex(half + 1, end, prefixString);
  95.                         } else /* if (mComparator.compare(halfItem, prefixString) == 0) */{
  96.                                 // Search in second half
  97.                                 return findLastIndex(half, end, prefixString);
  98.                         }
  99.                 }
  100.         }
  101. }

This class can be used instead of the original ArrayFilter algorithm:

  1.         if (prefix == null || prefix.length() == 0) {
  2.                 synchronized (mLock) {
  3.                         ArrayList<T> list = new ArrayList<T>(mOriginalValues);
  4.                         results.values = list;
  5.                         results.count = list.size();
  6.                 }
  7.         } else {
  8.                 String prefixString = prefix.toString().toLowerCase();
  9.                 final ArrayList<T> values = mOriginalValues;
  10.                 final int count = values.size();
  11.  
  12. //              final ArrayList<T> newValues = new ArrayList<T>(count);
  13. //
  14. //              for (int i = 0; i < count; i++) {
  15. //                      final T value = values.get(i);
  16. //                      final String valueText = value.toString().toLowerCase();
  17. //                              // First match against the whole, non-splitted value
  18. //                      if (valueText.startsWith(prefixString)) {
  19. //                              newValues.add(value);
  20. //                      } else {
  21. //                              final String[] words = valueText.split(" ");
  22. //                              final int wordCount = words.length;
  23. //
  24. //                              for (int k = 0; k < wordCount; k++) {
  25. //                                      if (words[k].startsWith(prefixString)) {
  26. //                                              newValues.add(value);
  27. //                                              break;
  28. //                                      }
  29. //                              }
  30. //                      }
  31. //              }
  32.                                
  33.                 // CHANGED TO
  34.                 BinarySearch<T> logSearch = new BinarySearch<T>(values, new Comparator<String>() {
  35.  
  36.                         @Override
  37.                         public int compare(String object1, String object2) {
  38.                                 final String temp = object1.substring(0, Math.min(object2.length(), object1.length()));
  39.                                 return temp.compareTo(object2);
  40.                         }
  41.                 });
  42.  
  43.                 final List<T> newValues = logSearch.select(prefixString);
  44.                 Log.d("Search", "count: " + newValues.size());
  45.                                
  46.  
  47.                 results.values = newValues;
  48.                 results.count = newValues.size();
  49.         }

The autocomplete textview can be used with much data even on older apparatus.

Bookmark/Search this post with

arcus motion analyzer

GetBugzi

New tutorials from Helloandroid

More...

Android on Twitter

Join the conversation

Poll

What Version of Android do you have?: