Quick guide to quick autocomplete textview

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

SDK Version:

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.

public class Main extends Activity {
        AutoCompleteTextView mAutoCompleteTextViewOriginal;
        AutoCompleteTextView mAutoCompleteTextViewQuick;
 
        @Override
        public void onCreate(Bundle savedInstanceState) {
                super.onCreate(savedInstanceState);
                setContentView(R.layout.main);
                
                String[] values =  createLongSortedStringArray(4);
        
                mAutoCompleteTextViewOriginal = (AutoCompleteTextView) findViewById(R.id.autoCompleteTextViewOriginal);
                ArrayAdapter<String> originalAdapter = new ArrayAdapter<String>(this, R.layout.autocomplete_listitem, values);
                mAutoCompleteTextViewOriginal.setAdapter(originalAdapter);
 
                mAutoCompleteTextViewQuick = (AutoCompleteTextView) findViewById(R.id.autoCompleteTextViewQuick);
                BinaryArrayAdapter<String> binaryAdapter = new BinaryArrayAdapter<String>(this, R.layout.autocomplete_listitem, values);
                mAutoCompleteTextViewQuick.setAdapter(binaryAdapter);
        }
 
        private String[] createLongSortedStringArray(int length) {
                NumberFormat nf = NumberFormat.getInstance(); 
                nf.setMinimumIntegerDigits(length);
                nf.setMaximumIntegerDigits(length);
                nf.setGroupingUsed(false);
 
                String[] values = new String[(int) Math.pow(10.0, (double)length)];
                for (int i = 0; i < values.length; i++) {
                        values[i] = nf.format(i);
                }
 
                return values;
        }
}

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:

public class BinarySearch<T> {
        List<T> mList;
 
        Comparator<String> mComparator;
 
        /**
         * Create Search list of item and comparator
         * 
         * @param list
         * @param comparator
         */
        public BinarySearch(List<T> list, Comparator<String> comparator) {
                mList = list;
                mComparator = comparator;
        }
 
        /**
         * Select sub list with given prefix
         * 
         * @param prefixString
         * @return
         */
        public List<T> select(String prefixString) {
                int first = findFirstIndex(0, mList.size() - 1, prefixString);;
                if (-1 == first) {
                        return new ArrayList<T>();
                }
 
                int last = findLastIndex(0, mList.size() - 1, prefixString);
 
                return mList.subList(first, last + 1);
        }
 
        private int findFirstIndex(int start, int end, String prefixString) {
                int size = end - start;
                if (size < 0) {
                        return -1;
                }
 
                if (size == 0) {
                        if (mComparator.compare(mList.get(start).toString(), prefixString) == 0) {
                                return start;
                        } else {
                                return -1;
                        }
                } else {
                        int half = (start + end) / 2;
                        T halfItem = mList.get(half);
                        String halfItemString = halfItem.toString();
                        int result = mComparator.compare(halfItemString, prefixString);
 
                        if (result > 0) {
                                // Search in first half
                                return findFirstIndex(start, half - 1, prefixString);
                        } else if (result < 0) {
                                // Search in second half
                                return findFirstIndex(half + 1, end, prefixString);
                        } else /* if (result == 0) */{
                                // Search in first half
                                return findFirstIndex(start, half, prefixString);
                        }
                }
        }
 
        /**
         * Find last index
         * 
         * @param array
         * @param prefixString
         * @return
         */
        private int findLastIndex(int start, int end, String prefixString) {
                int size = end - start;
                if (size < 0) {
                        return -1;
                }
 
                if (size == 0) {
                        if (mComparator.compare(mList.get(start).toString(), prefixString) == 0) {
                                return start;
                        } else {
                                return -1;
                        }
                } else {
                        int half = (start + end + 1) / 2;
                        T halfItem = mList.get(half);
                        String halfItemString = halfItem.toString();
                        int result = mComparator.compare(halfItemString, prefixString);
                        if (result > 0) {
                                // Search in first half
                                return findLastIndex(start, half - 1, prefixString);
                        } else if (mComparator.compare(halfItemString, prefixString) < 0) {
                                // Search in second half
                                return findLastIndex(half + 1, end, prefixString);
                        } else /* if (mComparator.compare(halfItem, prefixString) == 0) */{
                                // Search in second half
                                return findLastIndex(half, end, prefixString);
                        }
                }
        }
}

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

        if (prefix == null || prefix.length() == 0) {
                synchronized (mLock) {
                        ArrayList<T> list = new ArrayList<T>(mOriginalValues);
                        results.values = list;
                        results.count = list.size();
                }
        } else {
                String prefixString = prefix.toString().toLowerCase();
                final ArrayList<T> values = mOriginalValues;
                final int count = values.size();
 
//              final ArrayList<T> newValues = new ArrayList<T>(count);
//
//              for (int i = 0; i < count; i++) {
//                      final T value = values.get(i);
//                      final String valueText = value.toString().toLowerCase();
//                              // First match against the whole, non-splitted value
//                      if (valueText.startsWith(prefixString)) {
//                              newValues.add(value);
//                      } else {
//                              final String[] words = valueText.split(" ");
//                              final int wordCount = words.length;
//
//                              for (int k = 0; k < wordCount; k++) {
//                                      if (words[k].startsWith(prefixString)) {
//                                              newValues.add(value);
//                                              break;
//                                      }
//                              }
//                      }
//              }
                                
                // CHANGED TO 
                BinarySearch<T> logSearch = new BinarySearch<T>(values, new Comparator<String>() {
 
                        @Override
                        public int compare(String object1, String object2) {
                                final String temp = object1.substring(0, Math.min(object2.length(), object1.length()));
                                return temp.compareTo(object2);
                        }
                });
 
                final List<T> newValues = logSearch.select(prefixString);
                Log.d("Search", "count: " + newValues.size());
                                
 
                results.values = newValues;
                results.count = newValues.size();
        }