- // iterate through the completions and cut off where s differs
- for (size_t i = 0; i < n && s.length() > 0; ++i) {
- QString const & is
- = model.data(model.index(i, 0), Qt::EditRole).toString();
-
- // find common prefix
- size_t j;
- size_t isn = is.length();
- size_t sn = s.length();
- for (j = 0; j < isn && j < sn; ++j) {
- if (s.at(j) != is.at(j))
- break;
+ if (modelSorting() == QCompleter::UnsortedModel) {
+ // For unsorted model we cannot do more than iteration.
+ // Iterate through the completions and cut off where s differs
+ for (size_t i = 0; i < n && s.length() > 0; ++i) {
+ QString const & is
+ = model.data(model.index(i, 0), Qt::EditRole).toString();
+
+ s = s.left(commonPrefix(is, s));
+ }
+ } else {
+ // For sorted models we can do binary search multiple times,
+ // each time to find the first string which has s not as prefix.
+ size_t i = 0;
+ while (i < n && s.length() > 0) {
+ // find first string that does not have s as prefix
+ // via binary search in [i,n-1]
+ size_t r = n - 1;
+ do {
+ // get common prefix with the middle string
+ size_t mid = (r + i) / 2;
+ QString const & mids
+ = model.data(model.index(mid, 0),
+ Qt::EditRole).toString();
+ size_t oldLen = s.length();
+ size_t len = commonPrefix(mids, s);
+ s = s.left(len);
+
+ // left or right?
+ if (oldLen == len) {
+ // middle is not far enough
+ i = mid + 1;
+ } else {
+ // middle is maybe too far
+ r = mid;
+ }
+ } while (r - i > 0 && i < n);