1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 /*!

    43     \class QCompleter

    44     \brief The QCompleter class provides completions based on an item model.

    45     \since 4.2

    46 

    47     You can use QCompleter to provide auto completions in any Qt

    48     widget, such as QLineEdit and QComboBox.

    49     When the user starts typing a word, QCompleter suggests possible ways of

    50     completing the word, based on a word list. The word list is

    51     provided as a QAbstractItemModel. (For simple applications, where

    52     the word list is static, you can pass a QStringList to

    53     QCompleter's constructor.)

    54 

    55     \tableofcontents

    56 

    57     \section1 Basic Usage

    58 

    59     A QCompleter is used typically with a QLineEdit or QComboBox.

    60     For example, here's how to provide auto completions from a simple

    61     word list in a QLineEdit:

    62 

    63     \snippet doc/src/snippets/code/src_gui_util_qcompleter.cpp 0

    64 

    65     A QDirModel can be used to provide auto completion of file names.

    66     For example:

    67 

    68     \snippet doc/src/snippets/code/src_gui_util_qcompleter.cpp 1

    69 

    70     To set the model on which QCompleter should operate, call

    71     setModel(). By default, QCompleter will attempt to match the \l

    72     {completionPrefix}{completion prefix} (i.e., the word that the

    73     user has started typing) against the Qt::EditRole data stored in

    74     column 0 in the  model case sensitively. This can be changed

    75     using setCompletionRole(), setCompletionColumn(), and

    76     setCaseSensitivity().

    77 

    78     If the model is sorted on the column and role that are used for completion,

    79     you can call setModelSorting() with either

    80     QCompleter::CaseSensitivelySortedModel or

    81     QCompleter::CaseInsensitivelySortedModel as the argument. On large models,

    82     this can lead to significant performance improvements, because QCompleter

    83     can then use binary search instead of linear search.

    84 

    85     The model can be a \l{QAbstractListModel}{list model},

    86     a \l{QAbstractTableModel}{table model}, or a

    87     \l{QAbstractItemModel}{tree model}. Completion on tree models

    88     is slightly more involved and is covered in the \l{Handling

    89     Tree Models} section below.

    90 

    91     The completionMode() determines the mode used to provide completions to

    92     the user.

    93 

    94     \section1 Iterating Through Completions

    95 

    96     To retrieve a single candidate string, call setCompletionPrefix()

    97     with the text that needs to be completed and call

    98     currentCompletion(). You can iterate through the list of

    99     completions as below:

   100 

   101     \snippet doc/src/snippets/code/src_gui_util_qcompleter.cpp 2

   102 

   103     completionCount() returns the total number of completions for the

   104     current prefix. completionCount() should be avoided when possible,

   105     since it requires a scan of the entire model.

   106 

   107     \section1 The Completion Model

   108 

   109     completionModel() return a list model that contains all possible

   110     completions for the current completion prefix, in the order in which

   111     they appear in the model. This model can be used to display the current

   112     completions in a custom view. Calling setCompletionPrefix() automatically

   113     refreshes the completion model.

   114 

   115     \section1 Handling Tree Models

   116 

   117     QCompleter can look for completions in tree models, assuming

   118     that any item (or sub-item or sub-sub-item) can be unambiguously

   119     represented as a string by specifying the path to the item. The

   120     completion is then performed one level at a time.

   121 

   122     Let's take the example of a user typing in a file system path.

   123     The model is a (hierarchical) QDirModel. The completion

   124     occurs for every element in the path. For example, if the current

   125     text is \c C:\Wind, QCompleter might suggest \c Windows to

   126     complete the current path element. Similarly, if the current text

   127     is \c C:\Windows\Sy, QCompleter might suggest \c System.

   128 

   129     For this kind of completion to work, QCompleter needs to be able to

   130     split the path into a list of strings that are matched at each level.

   131     For \c C:\Windows\Sy, it needs to be split as "C:", "Windows" and "Sy".

   132     The default implementation of splitPath(), splits the completionPrefix

   133     using QDir::separator() if the model is a QDirModel.

   134 

   135     To provide completions, QCompleter needs to know the path from an index.

   136     This is provided by pathFromIndex(). The default implementation of

   137     pathFromIndex(), returns the data for the \l{Qt::EditRole}{edit role}

   138     for list models and the absolute file path if the mode is a QDirModel.

   139 

   140     \sa QAbstractItemModel, QLineEdit, QComboBox, {Completer Example}

   141 */

   142 

   143 #include "qcompleter_p.h"

   144 

   145 #ifndef QT_NO_COMPLETER

   146 

   147 #include "QtGui/qscrollbar.h"

   148 #include "QtGui/qstringlistmodel.h"

   149 #include "QtGui/qdirmodel.h"

   150 #include "QtGui/qheaderview.h"

   151 #include "QtGui/qlistview.h"

   152 #include "QtGui/qapplication.h"

   153 #include "QtGui/qevent.h"

   154 #include "QtGui/qheaderview.h"

   155 #include "QtGui/qdesktopwidget.h"

   156 

   157 QT_BEGIN_NAMESPACE

   158 

   159 QCompletionModel::QCompletionModel(QCompleterPrivate *c, QObject *parent)

   160     : QAbstractProxyModel(*new QCompletionModelPrivate, parent),

   161       c(c), showAll(false)

   162 {

   163     createEngine();

   164 }

   165 

   166 int QCompletionModel::columnCount(const QModelIndex &) const

   167 {

   168     Q_D(const QCompletionModel);

   169     return d->model->columnCount();

   170 }

   171 

   172 void QCompletionModel::setSourceModel(QAbstractItemModel *source)

   173 {

   174     bool hadModel = (sourceModel() != 0);

   175 

   176     if (hadModel)

   177         QObject::disconnect(sourceModel(), 0, this, 0);

   178 

   179     QAbstractProxyModel::setSourceModel(source);

   180 

   181     if (source) {

   182         // TODO: Optimize updates in the source model

   183         connect(source, SIGNAL(modelReset()), this, SLOT(invalidate()));

   184         connect(source, SIGNAL(destroyed()), this, SLOT(modelDestroyed()));

   185         connect(source, SIGNAL(layoutChanged()), this, SLOT(invalidate()));

   186         connect(source, SIGNAL(rowsInserted(QModelIndex,int,int)), this, SLOT(rowsInserted()));

   187         connect(source, SIGNAL(rowsRemoved(QModelIndex,int,int)), this, SLOT(invalidate()));

   188         connect(source, SIGNAL(columnsInserted(QModelIndex,int,int)), this, SLOT(invalidate()));

   189         connect(source, SIGNAL(columnsRemoved(QModelIndex,int,int)), this, SLOT(invalidate()));

   190         connect(source, SIGNAL(dataChanged(QModelIndex,QModelIndex)), this, SLOT(invalidate()));

   191     }

   192 

   193     invalidate();

   194 }

   195 

   196 void QCompletionModel::createEngine()

   197 {

   198     bool sortedEngine = false;

   199     switch (c->sorting) {

   200     case QCompleter::UnsortedModel:

   201         sortedEngine = false;

   202         break;

   203     case QCompleter::CaseSensitivelySortedModel:

   204         sortedEngine = c->cs == Qt::CaseSensitive;

   205         break;

   206     case QCompleter::CaseInsensitivelySortedModel:

   207         sortedEngine = c->cs == Qt::CaseInsensitive;

   208         break;

   209     }

   210 

   211     if (sortedEngine)

   212         engine.reset(new QSortedModelEngine(c));

   213     else

   214         engine.reset(new QUnsortedModelEngine(c));

   215 }

   216 

   217 QModelIndex QCompletionModel::mapToSource(const QModelIndex& index) const

   218 {

   219     Q_D(const QCompletionModel);

   220     if (!index.isValid())

   221         return QModelIndex();

   222 

   223     int row;

   224     QModelIndex parent = engine->curParent;

   225     if (!showAll) {

   226         if (!engine->matchCount())

   227             return QModelIndex();

   228         Q_ASSERT(index.row() < engine->matchCount());

   229         QIndexMapper& rootIndices = engine->historyMatch.indices;

   230         if (index.row() < rootIndices.count()) {

   231             row = rootIndices[index.row()];

   232             parent = QModelIndex();

   233         } else {

   234             row = engine->curMatch.indices[index.row() - rootIndices.count()];

   235         }

   236     } else {

   237         row = index.row();

   238     }

   239 

   240     return d->model->index(row, index.column(), parent);

   241 }

   242 

   243 QModelIndex QCompletionModel::mapFromSource(const QModelIndex& idx) const

   244 {

   245     if (!idx.isValid())

   246         return QModelIndex();

   247 

   248     int row = -1;

   249     if (!showAll) {

   250         if (!engine->matchCount())

   251             return QModelIndex();

   252 

   253         QIndexMapper& rootIndices = engine->historyMatch.indices;

   254         if (idx.parent().isValid()) {

   255             if (idx.parent() != engine->curParent)

   256                 return QModelIndex();

   257         } else {

   258             row = rootIndices.indexOf(idx.row());

   259             if (row == -1 && engine->curParent.isValid())

   260                 return QModelIndex(); // source parent and our parent don't match

   261         }

   262 

   263         if (row == -1) {

   264             QIndexMapper& indices = engine->curMatch.indices;

   265             engine->filterOnDemand(idx.row() - indices.last());

   266             row = indices.indexOf(idx.row()) + rootIndices.count();

   267         }

   268 

   269         if (row == -1)

   270             return QModelIndex();

   271     } else {

   272         if (idx.parent() != engine->curParent)

   273             return QModelIndex();

   274         row = idx.row();

   275     }

   276 

   277     return createIndex(row, idx.column());

   278 }

   279 

   280 bool QCompletionModel::setCurrentRow(int row)

   281 {

   282     if (row < 0 || !engine->matchCount())

   283         return false;

   284 

   285     if (row >= engine->matchCount())

   286         engine->filterOnDemand(row + 1 - engine->matchCount());

   287 

   288     if (row >= engine->matchCount()) // invalid row

   289         return false;

   290 

   291     engine->curRow = row;

   292     return true;

   293 }

   294 

   295 QModelIndex QCompletionModel::currentIndex(bool sourceIndex) const

   296 {

   297     if (!engine->matchCount())

   298         return QModelIndex();

   299 

   300     int row = engine->curRow;

   301     if (showAll)

   302         row = engine->curMatch.indices[engine->curRow];

   303 

   304     QModelIndex idx = createIndex(row, c->column);

   305     if (!sourceIndex)

   306         return idx;

   307     return mapToSource(idx);

   308 }

   309 

   310 QModelIndex QCompletionModel::index(int row, int column, const QModelIndex& parent) const

   311 {

   312     Q_D(const QCompletionModel);

   313     if (row < 0 || column < 0 || column >= columnCount(parent) || parent.isValid())

   314         return QModelIndex();

   315 

   316     if (!showAll) {

   317         if (!engine->matchCount())

   318             return QModelIndex();

   319         if (row >= engine->historyMatch.indices.count()) {

   320             int want = row + 1 - engine->matchCount();

   321             if (want > 0)

   322                 engine->filterOnDemand(want);

   323             if (row >= engine->matchCount())

   324                 return QModelIndex();

   325         }

   326     } else {

   327         if (row >= d->model->rowCount(engine->curParent))

   328             return QModelIndex();

   329     }

   330 

   331     return createIndex(row, column);

   332 }

   333 

   334 int QCompletionModel::completionCount() const

   335 {

   336     if (!engine->matchCount())

   337         return 0;

   338 

   339     engine->filterOnDemand(INT_MAX);

   340     return engine->matchCount();

   341 }

   342 

   343 int QCompletionModel::rowCount(const QModelIndex &parent) const

   344 {

   345     Q_D(const QCompletionModel);

   346     if (parent.isValid())

   347         return 0;

   348 

   349     if (showAll) {

   350         // Show all items below current parent, even if we have no valid matches

   351         if (engine->curParts.count() != 1  && !engine->matchCount()

   352             && !engine->curParent.isValid())

   353             return 0;

   354         return d->model->rowCount(engine->curParent);

   355     }

   356 

   357     return completionCount();

   358 }

   359 

   360 void QCompletionModel::setFiltered(bool filtered)

   361 {

   362     if (showAll == !filtered)

   363         return;

   364     showAll = !filtered;

   365     resetModel();

   366 }

   367 

   368 bool QCompletionModel::hasChildren(const QModelIndex &parent) const

   369 {

   370     Q_D(const QCompletionModel);

   371     if (parent.isValid())

   372         return false;

   373 

   374     if (showAll)

   375         return d->model->hasChildren(mapToSource(parent));

   376 

   377     if (!engine->matchCount())

   378         return false;

   379 

   380     return true;

   381 }

   382 

   383 QVariant QCompletionModel::data(const QModelIndex& index, int role) const

   384 {

   385     Q_D(const QCompletionModel);

   386     return d->model->data(mapToSource(index), role);

   387 }

   388 

   389 void QCompletionModel::modelDestroyed()

   390 {

   391     QAbstractProxyModel::setSourceModel(0); // switch to static empty model

   392     invalidate();

   393 }

   394 

   395 void QCompletionModel::rowsInserted()

   396 {

   397     invalidate();

   398     emit rowsAdded();

   399 }

   400 

   401 void QCompletionModel::invalidate()

   402 {

   403     engine->cache.clear();

   404     filter(engine->curParts);

   405 }

   406 

   407 void QCompletionModel::filter(const QStringList& parts)

   408 {

   409     Q_D(QCompletionModel);

   410     engine->filter(parts);

   411     resetModel();

   412 

   413     if (d->model->canFetchMore(engine->curParent))

   414         d->model->fetchMore(engine->curParent);

   415 }

   416 

   417 void QCompletionModel::resetModel()

   418 {

   419     if (rowCount() == 0) {

   420         reset();

   421         return;

   422     }

   423 

   424     emit layoutAboutToBeChanged();

   425     QModelIndexList piList = persistentIndexList();

   426     QModelIndexList empty;

   427     for (int i = 0; i < piList.size(); i++)

   428         empty.append(QModelIndex());

   429     changePersistentIndexList(piList, empty);

   430     emit layoutChanged();

   431 }

   432 

   433 //////////////////////////////////////////////////////////////////////////////

   434 void QCompletionEngine::filter(const QStringList& parts)

   435 {

   436     const QAbstractItemModel *model = c->proxy->sourceModel();

   437     curParts = parts;

   438     if (curParts.isEmpty())

   439         curParts.append(QString());

   440 

   441     curRow = -1;

   442     curParent = QModelIndex();

   443     curMatch = QMatchData();

   444     historyMatch = filterHistory();

   445 

   446     if (!model)

   447         return;

   448 

   449     QModelIndex parent;

   450     for (int i = 0; i < curParts.count() - 1; i++) {

   451         QString part = curParts[i];

   452         int emi = filter(part, parent, -1).exactMatchIndex;

   453         if (emi == -1)

   454             return;

   455         parent = model->index(emi, c->column, parent);

   456     }

   457 

   458     // Note that we set the curParent to a valid parent, even if we have no matches

   459     // When filtering is disabled, we show all the items under this parent

   460     curParent = parent;

   461     if (curParts.last().isEmpty())

   462         curMatch = QMatchData(QIndexMapper(0, model->rowCount(curParent) - 1), -1, false);

   463     else

   464         curMatch = filter(curParts.last(), curParent, 1); // build at least one

   465     curRow = curMatch.isValid() ? 0 : -1;

   466 }

   467 

   468 QMatchData QCompletionEngine::filterHistory()

   469 {

   470     QAbstractItemModel *source = c->proxy->sourceModel();

   471     if (curParts.count() <= 1 || c->proxy->showAll || !source)

   472         return QMatchData();

   473     bool dirModel = false;

   474 #ifndef QT_NO_DIRMODEL

   475     dirModel = (qobject_cast<QDirModel *>(source) != 0);

   476 #endif

   477     QVector<int> v;

   478     QIndexMapper im(v);

   479     QMatchData m(im, -1, true);

   480 

   481     for (int i = 0; i < source->rowCount(); i++) {

   482         QString str = source->index(i, c->column).data().toString();

   483         if (str.startsWith(c->prefix, c->cs)

   484 #if (!defined(Q_OS_WIN) || defined(Q_OS_WINCE)) && !defined(Q_OS_SYMBIAN)

   485             && (!dirModel || QDir::toNativeSeparators(str) != QDir::separator())

   486 #endif

   487             )

   488             m.indices.append(i);

   489     }

   490     return m;

   491 }

   492 

   493 // Returns a match hint from the cache by chopping the search string

   494 bool QCompletionEngine::matchHint(QString part, const QModelIndex& parent, QMatchData *hint)

   495 {

   496     if (c->cs == Qt::CaseInsensitive)

   497         part = part.toLower();

   498 

   499     const CacheItem& map = cache[parent];

   500 

   501     QString key = part;

   502     while (!key.isEmpty()) {

   503         key.chop(1);

   504         if (map.contains(key)) {

   505             *hint = map[key];

   506             return true;

   507         }

   508     }

   509 

   510     return false;

   511 }

   512 

   513 bool QCompletionEngine::lookupCache(QString part, const QModelIndex& parent, QMatchData *m)

   514 {

   515    if (c->cs == Qt::CaseInsensitive)

   516         part = part.toLower();

   517    const CacheItem& map = cache[parent];

   518    if (!map.contains(part))

   519        return false;

   520    *m = map[part];

   521    return true;

   522 }

   523 

   524 // When the cache size exceeds 1MB, it clears out about 1/2 of the cache.

   525 void QCompletionEngine::saveInCache(QString part, const QModelIndex& parent, const QMatchData& m)

   526 {

   527     QMatchData old = cache[parent].take(part);

   528     cost = cost + m.indices.cost() - old.indices.cost();

   529     if (cost * sizeof(int) > 1024 * 1024) {

   530         QMap<QModelIndex, CacheItem>::iterator it1 ;

   531         for (it1 = cache.begin(); it1 != cache.end(); ++it1) {

   532             CacheItem& ci = it1.value();

   533             int sz = ci.count()/2;

   534             QMap<QString, QMatchData>::iterator it2 = ci.begin();

   535             for (int i = 0; it2 != ci.end() && i < sz; i++, ++it2) {

   536                 cost -= it2.value().indices.cost();

   537                 ci.erase(it2);

   538             }

   539             if (ci.count() == 0)

   540                 cache.erase(it1);

   541         }

   542     }

   543 

   544     if (c->cs == Qt::CaseInsensitive)

   545         part = part.toLower();

   546     cache[parent][part] = m;

   547 }

   548 

   549 ///////////////////////////////////////////////////////////////////////////////////

   550 QIndexMapper QSortedModelEngine::indexHint(QString part, const QModelIndex& parent, Qt::SortOrder order)

   551 {

   552     const QAbstractItemModel *model = c->proxy->sourceModel();

   553 

   554     if (c->cs == Qt::CaseInsensitive)

   555         part = part.toLower();

   556 

   557     const CacheItem& map = cache[parent];

   558 

   559     // Try to find a lower and upper bound for the search from previous results

   560     int to = model->rowCount(parent) - 1;

   561     int from = 0;

   562     const CacheItem::const_iterator it = map.lowerBound(part);

   563 

   564     // look backward for first valid hint

   565     for(CacheItem::const_iterator it1 = it; it1-- != map.constBegin();) {

   566         const QMatchData& value = it1.value();

   567         if (value.isValid()) {

   568             if (order == Qt::AscendingOrder) {

   569                 from = value.indices.last() + 1;

   570             } else {

   571                 to = value.indices.first() - 1;

   572             }

   573             break;

   574         }

   575     }

   576 

   577     // look forward for first valid hint

   578     for(CacheItem::const_iterator it2 = it; it2 != map.constEnd(); ++it2) {

   579         const QMatchData& value = it2.value();

   580         if (value.isValid() && !it2.key().startsWith(part)) {

   581             if (order == Qt::AscendingOrder) {

   582                 to = value.indices.first() - 1;

   583             } else {

   584                 from = value.indices.first() + 1;

   585             }

   586             break;

   587         }

   588     }

   589 

   590     return QIndexMapper(from, to);

   591 }

   592 

   593 Qt::SortOrder QSortedModelEngine::sortOrder(const QModelIndex &parent) const

   594 {

   595     const QAbstractItemModel *model = c->proxy->sourceModel();

   596 

   597     int rowCount = model->rowCount(parent);

   598     if (rowCount < 2)

   599         return Qt::AscendingOrder;

   600     QString first = model->data(model->index(0, c->column, parent), c->role).toString();

   601     QString last = model->data(model->index(rowCount - 1, c->column, parent), c->role).toString();

   602     return QString::compare(first, last, c->cs) <= 0 ? Qt::AscendingOrder : Qt::DescendingOrder;

   603 }

   604 

   605 QMatchData QSortedModelEngine::filter(const QString& part, const QModelIndex& parent, int)

   606 {

   607     const QAbstractItemModel *model = c->proxy->sourceModel();

   608 

   609     QMatchData hint;

   610     if (lookupCache(part, parent, &hint))

   611         return hint;

   612 

   613     QIndexMapper indices;

   614     Qt::SortOrder order = sortOrder(parent);

   615 

   616     if (matchHint(part, parent, &hint)) {

   617         if (!hint.isValid())

   618             return QMatchData();

   619         indices = hint.indices;

   620     } else {

   621         indices = indexHint(part, parent, order);

   622     }

   623 

   624     // binary search the model within 'indices' for 'part' under 'parent'

   625     int high = indices.to() + 1;

   626     int low = indices.from() - 1;

   627     int probe;

   628     QModelIndex probeIndex;

   629     QString probeData;

   630 

   631     while (high - low > 1)

   632     {

   633         probe = (high + low) / 2;

   634         probeIndex = model->index(probe, c->column, parent);

   635         probeData = model->data(probeIndex, c->role).toString();

   636         const int cmp = QString::compare(probeData, part, c->cs);

   637         if ((order == Qt::AscendingOrder && cmp >= 0)

   638             || (order == Qt::DescendingOrder && cmp < 0)) {

   639             high = probe;

   640         } else {

   641             low = probe;

   642         }

   643     }

   644 

   645     if ((order == Qt::AscendingOrder && low == indices.to())

   646         || (order == Qt::DescendingOrder && high == indices.from())) { // not found

   647         saveInCache(part, parent, QMatchData());

   648         return QMatchData();

   649     }

   650 

   651     probeIndex = model->index(order == Qt::AscendingOrder ? low+1 : high-1, c->column, parent);

   652     probeData = model->data(probeIndex, c->role).toString();

   653     if (!probeData.startsWith(part, c->cs)) {

   654         saveInCache(part, parent, QMatchData());

   655         return QMatchData();

   656     }

   657 

   658     const bool exactMatch = QString::compare(probeData, part, c->cs) == 0;

   659     int emi =  exactMatch ? (order == Qt::AscendingOrder ? low+1 : high-1) : -1;

   660 

   661     int from = 0;

   662     int to = 0;

   663     if (order == Qt::AscendingOrder) {

   664         from = low + 1;

   665         high = indices.to() + 1;

   666         low = from;

   667     } else {

   668         to = high - 1;

   669         low = indices.from() - 1;

   670         high = to;

   671     }

   672 

   673     while (high - low > 1)

   674     {

   675         probe = (high + low) / 2;

   676         probeIndex = model->index(probe, c->column, parent);

   677         probeData = model->data(probeIndex, c->role).toString();

   678         const bool startsWith = probeData.startsWith(part, c->cs);

   679         if ((order == Qt::AscendingOrder && startsWith)

   680             || (order == Qt::DescendingOrder && !startsWith)) {

   681             low = probe;

   682         } else {

   683             high = probe;

   684         }

   685     }

   686 

   687     QMatchData m(order == Qt::AscendingOrder ? QIndexMapper(from, high - 1) : QIndexMapper(low+1, to), emi, false);

   688     saveInCache(part, parent, m);

   689     return m;

   690 }

   691 

   692 ////////////////////////////////////////////////////////////////////////////////////////

   693 int QUnsortedModelEngine::buildIndices(const QString& str, const QModelIndex& parent, int n,

   694                                       const QIndexMapper& indices, QMatchData* m)

   695 {

   696     Q_ASSERT(m->partial);

   697     Q_ASSERT(n != -1 || m->exactMatchIndex == -1);

   698     const QAbstractItemModel *model = c->proxy->sourceModel();

   699     int i, count = 0;

   700 

   701     for (i = 0; i < indices.count() && count != n; ++i) {

   702         QModelIndex idx = model->index(indices[i], c->column, parent);

   703         QString data = model->data(idx, c->role).toString();

   704         if (!data.startsWith(str, c->cs) || !(model->flags(idx) & Qt::ItemIsSelectable))

   705             continue;

   706         m->indices.append(indices[i]);

   707         ++count;

   708         if (m->exactMatchIndex == -1 && QString::compare(data, str, c->cs) == 0) {

   709             m->exactMatchIndex = indices[i];

   710             if (n == -1)

   711                 return indices[i];

   712         }

   713     }

   714     return indices[i-1];

   715 }

   716 

   717 void QUnsortedModelEngine::filterOnDemand(int n)

   718 {

   719     Q_ASSERT(matchCount());

   720     if (!curMatch.partial)

   721         return;

   722     Q_ASSERT(n >= -1);

   723     const QAbstractItemModel *model = c->proxy->sourceModel();

   724     int lastRow = model->rowCount(curParent) - 1;

   725     QIndexMapper im(curMatch.indices.last() + 1, lastRow);

   726     int lastIndex = buildIndices(curParts.last(), curParent, n, im, &curMatch);

   727     curMatch.partial = (lastRow != lastIndex);

   728     saveInCache(curParts.last(), curParent, curMatch);

   729 }

   730 

   731 QMatchData QUnsortedModelEngine::filter(const QString& part, const QModelIndex& parent, int n)

   732 {

   733     QMatchData hint;

   734 

   735     QVector<int> v;

   736     QIndexMapper im(v);

   737     QMatchData m(im, -1, true);

   738 

   739     const QAbstractItemModel *model = c->proxy->sourceModel();

   740     bool foundInCache = lookupCache(part, parent, &m);

   741 

   742     if (!foundInCache) {

   743         if (matchHint(part, parent, &hint) && !hint.isValid())

   744             return QMatchData();

   745     }

   746 

   747     if (!foundInCache && !hint.isValid()) {

   748         const int lastRow = model->rowCount(parent) - 1;

   749         QIndexMapper all(0, lastRow);

   750         int lastIndex = buildIndices(part, parent, n, all, &m);

   751         m.partial = (lastIndex != lastRow);

   752     } else {

   753         if (!foundInCache) { // build from hint as much as we can

   754             buildIndices(part, parent, INT_MAX, hint.indices, &m);

   755             m.partial = hint.partial;

   756         }

   757         if (m.partial && ((n == -1 && m.exactMatchIndex == -1) || (m.indices.count() < n))) {

   758             // need more and have more

   759             const int lastRow = model->rowCount(parent) - 1;

   760             QIndexMapper rest(hint.indices.last() + 1, lastRow);

   761             int want = n == -1 ? -1 : n - m.indices.count();

   762             int lastIndex = buildIndices(part, parent, want, rest, &m);

   763             m.partial = (lastRow != lastIndex);

   764         }

   765     }

   766 

   767     saveInCache(part, parent, m);

   768     return m;

   769 }

   770 

   771 ///////////////////////////////////////////////////////////////////////////////

   772 QCompleterPrivate::QCompleterPrivate()

   773 : widget(0), proxy(0), popup(0), cs(Qt::CaseSensitive), role(Qt::EditRole), column(0),

   774   maxVisibleItems(7), sorting(QCompleter::UnsortedModel), wrap(true), eatFocusOut(true)

   775 {

   776 }

   777 

   778 void QCompleterPrivate::init(QAbstractItemModel *m)

   779 {

   780     Q_Q(QCompleter);

   781     proxy = new QCompletionModel(this, q);

   782     QObject::connect(proxy, SIGNAL(rowsAdded()), q, SLOT(_q_autoResizePopup()));

   783     q->setModel(m);

   784 #ifdef QT_NO_LISTVIEW

   785     q->setCompletionMode(QCompleter::InlineCompletion);

   786 #else

   787     q->setCompletionMode(QCompleter::PopupCompletion);

   788 #endif // QT_NO_LISTVIEW

   789 }

   790 

   791 void QCompleterPrivate::setCurrentIndex(QModelIndex index, bool select)

   792 {

   793     Q_Q(QCompleter);

   794     if (!q->popup())

   795         return;

   796     if (!select) {

   797         popup->selectionModel()->setCurrentIndex(index, QItemSelectionModel::NoUpdate);

   798     } else {

   799         if (!index.isValid())

   800             popup->selectionModel()->clear();

   801         else

   802             popup->selectionModel()->setCurrentIndex(index, QItemSelectionModel::Select

   803                                                             | QItemSelectionModel::Rows);

   804     }

   805     index = popup->selectionModel()->currentIndex();

   806     if (!index.isValid())

   807         popup->scrollToTop();

   808     else

   809         popup->scrollTo(index, QAbstractItemView::PositionAtTop);

   810 }

   811 

   812 void QCompleterPrivate::_q_completionSelected(const QItemSelection& selection)

   813 {

   814     QModelIndex index;

   815     if (!selection.indexes().isEmpty())

   816         index = selection.indexes().first();

   817 

   818     _q_complete(index, true);

   819 }

   820 

   821 void QCompleterPrivate::_q_complete(QModelIndex index, bool highlighted)

   822 {

   823     Q_Q(QCompleter);

   824     QString completion;

   825 

   826     if (!index.isValid() || (!proxy->showAll && (index.row() >= proxy->engine->matchCount()))) {

   827         completion = prefix;

   828     } else {

   829         if (!(index.flags() & Qt::ItemIsEnabled))

   830             return;

   831         QModelIndex si = proxy->mapToSource(index);

   832         si = si.sibling(si.row(), column); // for clicked()

   833         completion = q->pathFromIndex(si);

   834 #ifndef QT_NO_DIRMODEL

   835         // add a trailing separator in inline

   836         if (mode == QCompleter::InlineCompletion) {

   837             if (qobject_cast<QDirModel *>(proxy->sourceModel()) && QFileInfo(completion).isDir())

   838                 completion += QDir::separator();

   839         }

   840 #endif

   841     }

   842 

   843     if (highlighted) {

   844         emit q->highlighted(index);

   845         emit q->highlighted(completion);

   846     } else {

   847         emit q->activated(index);

   848         emit q->activated(completion);

   849     }

   850 }

   851 

   852 void QCompleterPrivate::_q_autoResizePopup()

   853 {

   854     if (!popup || !popup->isVisible())

   855         return;

   856     showPopup(popupRect);

   857 }

   858 

   859 void QCompleterPrivate::showPopup(const QRect& rect)

   860 {

   861     const QRect screen = QApplication::desktop()->availableGeometry(widget);

   862     Qt::LayoutDirection dir = widget->layoutDirection();

   863     QPoint pos;

   864     int rw, rh, w;

   865     int h = (popup->sizeHintForRow(0) * qMin(maxVisibleItems, popup->model()->rowCount()) + 3) + 3;

   866     QScrollBar *hsb = popup->horizontalScrollBar();

   867     if (hsb && hsb->isVisible())

   868         h += popup->horizontalScrollBar()->sizeHint().height();

   869 

   870     if (rect.isValid()) {

   871         rh = rect.height();

   872         w = rw = rect.width();

   873         pos = widget->mapToGlobal(dir == Qt::RightToLeft ? rect.bottomRight() : rect.bottomLeft());

   874     } else {

   875         rh = widget->height();

   876         rw = widget->width();

   877         pos = widget->mapToGlobal(QPoint(0, widget->height() - 2));

   878         w = widget->width();

   879     }

   880 

   881     if ((pos.x() + rw) > (screen.x() + screen.width()))

   882         pos.setX(screen.x() + screen.width() - w);

   883     if (pos.x() < screen.x())

   884         pos.setX(screen.x());

   885     if (((pos.y() + rh) > (screen.y() + screen.height())) && ((pos.y() - h - rh) >= 0))

   886         pos.setY(pos.y() - qMax(h, popup->minimumHeight()) - rh + 2);

   887 

   888     popup->setGeometry(pos.x(), pos.y(), w, h);

   889 

   890     if (!popup->isVisible())

   891         popup->show();

   892 }

   893 

   894 /*!

   895     Constructs a completer object with the given \a parent.

   896 */

   897 QCompleter::QCompleter(QObject *parent)

   898 : QObject(*new QCompleterPrivate(), parent)

   899 {

   900     Q_D(QCompleter);

   901     d->init();

   902 }

   903 

   904 /*!

   905     Constructs a completer object with the given \a parent that provides completions

   906     from the specified \a model.

   907 */

   908 QCompleter::QCompleter(QAbstractItemModel *model, QObject *parent)

   909     : QObject(*new QCompleterPrivate(), parent)

   910 {

   911     Q_D(QCompleter);

   912     d->init(model);

   913 }

   914 

   915 #ifndef QT_NO_STRINGLISTMODEL

   916 /*!

   917     Constructs a QCompleter object with the given \a parent that uses the specified

   918     \a list as a source of possible completions.

   919 */

   920 QCompleter::QCompleter(const QStringList& list, QObject *parent)

   921 : QObject(*new QCompleterPrivate(), parent)

   922 {

   923     Q_D(QCompleter);

   924     d->init(new QStringListModel(list, this));

   925 }

   926 #endif // QT_NO_STRINGLISTMODEL

   927 

   928 /*!

   929     Destroys the completer object.

   930 */

   931 QCompleter::~QCompleter()

   932 {

   933 }

   934 

   935 /*!

   936     Sets the widget for which completion are provided for to \a widget. This

   937     function is automatically called when a QCompleter is set on a QLineEdit

   938     using QLineEdit::setCompleter() or on a QComboBox using

   939     QComboBox::setCompleter(). The widget needs to be set explicitly when

   940     providing completions for custom widgets.

   941 

   942     \sa widget(), setModel(), setPopup()

   943  */

   944 void QCompleter::setWidget(QWidget *widget)

   945 {

   946     Q_D(QCompleter);

   947     if (d->widget)

   948         d->widget->removeEventFilter(this);

   949     d->widget = widget;

   950     if (d->widget)

   951         d->widget->installEventFilter(this);

   952     if (d->popup) {

   953         d->popup->hide();

   954         d->popup->setFocusProxy(d->widget);

   955     }

   956 }

   957 

   958 /*!

   959     Returns the widget for which the completer object is providing completions.

   960 

   961     \sa setWidget()

   962  */

   963 QWidget *QCompleter::widget() const

   964 {

   965     Q_D(const QCompleter);

   966     return d->widget;

   967 }

   968 

   969 /*!

   970     Sets the model which provides completions to \a model. The \a model can

   971     be list model or a tree model. If a model has been already previously set

   972     and it has the QCompleter as its parent, it is deleted.

   973 

   974     For convenience, if \a model is a QDirModel, QCompleter switches its

   975     caseSensitivity to Qt::CaseInsensitive on Windows and Qt::CaseSensitive

   976     on other platforms.

   977 

   978     \sa completionModel(), modelSorting, {Handling Tree Models}

   979 */

   980 void QCompleter::setModel(QAbstractItemModel *model)

   981 {

   982     Q_D(QCompleter);

   983     QAbstractItemModel *oldModel = d->proxy->sourceModel();

   984     d->proxy->setSourceModel(model);

   985     if (d->popup)

   986         setPopup(d->popup); // set the model and make new connections

   987     if (oldModel && oldModel->QObject::parent() == this)

   988         delete oldModel;

   989 #ifndef QT_NO_DIRMODEL

   990     if (qobject_cast<QDirModel *>(model)) {

   991 #if (defined(Q_OS_WIN) && !defined(Q_OS_WINCE)) || defined(Q_OS_SYMBIAN)

   992         setCaseSensitivity(Qt::CaseInsensitive);

   993 #else

   994         setCaseSensitivity(Qt::CaseSensitive);

   995 #endif

   996     }

   997 #endif // QT_NO_DIRMODEL

   998 }

   999 

  1000 /*!

  1001     Returns the model that provides completion strings.

  1002 

  1003     \sa completionModel()

  1004 */

  1005 QAbstractItemModel *QCompleter::model() const

  1006 {

  1007     Q_D(const QCompleter);

  1008     return d->proxy->sourceModel();

  1009 }

  1010 

  1011 /*!

  1012     \enum QCompleter::CompletionMode

  1013 

  1014     This enum specifies how completions are provided to the user.

  1015 

  1016     \value PopupCompletion            Current completions are displayed in a popup window.

  1017     \value InlineCompletion           Completions appear inline (as selected text).

  1018     \value UnfilteredPopupCompletion  All possible completions are displayed in a popup window with the most likely suggestion indicated as current.

  1019 

  1020     \sa setCompletionMode()

  1021 */

  1022 

  1023 /*!

  1024     \property QCompleter::completionMode

  1025     \brief how the completions are provided to the user

  1026 

  1027     The default value is QCompleter::PopupCompletion.

  1028 */

  1029 void QCompleter::setCompletionMode(QCompleter::CompletionMode mode)

  1030 {

  1031     Q_D(QCompleter);

  1032     d->mode = mode;

  1033     d->proxy->setFiltered(mode != QCompleter::UnfilteredPopupCompletion);

  1034 

  1035     if (mode == QCompleter::InlineCompletion) {

  1036         if (d->widget)

  1037             d->widget->removeEventFilter(this);

  1038         if (d->popup) {

  1039             d->popup->deleteLater();

  1040             d->popup = 0;

  1041         }

  1042     } else {

  1043         if (d->widget)

  1044             d->widget->installEventFilter(this);

  1045     }

  1046 }

  1047 

  1048 QCompleter::CompletionMode QCompleter::completionMode() const

  1049 {

  1050     Q_D(const QCompleter);

  1051     return d->mode;

  1052 }

  1053 

  1054 /*!

  1055     Sets the popup used to display completions to \a popup. QCompleter takes

  1056     ownership of the view.

  1057 

  1058     A QListView is automatically created when the completionMode() is set to

  1059     QCompleter::PopupCompletion or QCompleter::UnfilteredPopupCompletion. The

  1060     default popup displays the completionColumn().

  1061 

  1062     Ensure that this function is called before the view settings are modified.

  1063     This is required since view's properties may require that a model has been

  1064     set on the view (for example, hiding columns in the view requires a model

  1065     to be set on the view).

  1066 

  1067     \sa popup()

  1068 */

  1069 void QCompleter::setPopup(QAbstractItemView *popup)

  1070 {

  1071     Q_D(QCompleter);

  1072     Q_ASSERT(popup != 0);

  1073     if (d->popup) {

  1074         QObject::disconnect(d->popup->selectionModel(), 0, this, 0);

  1075         QObject::disconnect(d->popup, 0, this, 0);

  1076     }

  1077     if (d->popup != popup)

  1078         delete d->popup;

  1079     if (popup->model() != d->proxy)

  1080         popup->setModel(d->proxy);

  1081 #ifdef Q_OS_MAC

  1082      popup->show();

  1083 #else

  1084      popup->hide();

  1085 #endif

  1086 

  1087     Qt::FocusPolicy origPolicy = Qt::NoFocus;

  1088     if (d->widget)

  1089         origPolicy = d->widget->focusPolicy();

  1090     popup->setParent(0, Qt::Popup);

  1091     popup->setFocusPolicy(Qt::NoFocus);

  1092     if (d->widget)

  1093         d->widget->setFocusPolicy(origPolicy);

  1094 

  1095     popup->setFocusProxy(d->widget);

  1096     popup->installEventFilter(this);

  1097     popup->setItemDelegate(new QCompleterItemDelegate(popup));

  1098 #ifndef QT_NO_LISTVIEW

  1099     if (QListView *listView = qobject_cast<QListView *>(popup)) {

  1100         listView->setModelColumn(d->column);

  1101     }

  1102 #endif

  1103 

  1104     QObject::connect(popup, SIGNAL(clicked(QModelIndex)),

  1105                      this, SLOT(_q_complete(QModelIndex)));

  1106     QObject::connect(this, SIGNAL(activated(QModelIndex)),

  1107                      popup, SLOT(hide()));

  1108 

  1109     QObject::connect(popup->selectionModel(), SIGNAL(selectionChanged(QItemSelection,QItemSelection)),

  1110                      this, SLOT(_q_completionSelected(QItemSelection)));

  1111     d->popup = popup;

  1112 }

  1113 

  1114 /*!

  1115     Returns the popup used to display completions.

  1116 

  1117     \sa setPopup()

  1118 */

  1119 QAbstractItemView *QCompleter::popup() const

  1120 {

  1121     Q_D(const QCompleter);

  1122 #ifndef QT_NO_LISTVIEW

  1123     if (!d->popup && completionMode() != QCompleter::InlineCompletion) {

  1124         QListView *listView = new QListView;

  1125         listView->setEditTriggers(QAbstractItemView::NoEditTriggers);

  1126         listView->setHorizontalScrollBarPolicy(Qt::ScrollBarAlwaysOff);

  1127         listView->setSelectionBehavior(QAbstractItemView::SelectRows);

  1128         listView->setSelectionMode(QAbstractItemView::SingleSelection);

  1129         listView->setModelColumn(d->column);

  1130         QCompleter *that = const_cast<QCompleter*>(this);

  1131         that->setPopup(listView);

  1132     }

  1133 #endif // QT_NO_LISTVIEW

  1134     return d->popup;