/****************************************************************************

**

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

** All rights reserved.

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

**

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

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

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

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

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

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

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

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

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

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

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

**

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

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

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

**

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

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

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

/*!

    \class QCompleter

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

    \since 4.2

    You can use QCompleter to provide auto completions in any Qt

    widget, such as QLineEdit and QComboBox.

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

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

    provided as a QAbstractItemModel. (For simple applications, where

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

    QCompleter's constructor.)

    \tableofcontents

    \section1 Basic Usage

    A QCompleter is used typically with a QLineEdit or QComboBox.

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

    word list in a QLineEdit:

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

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

    For example:

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

    To set the model on which QCompleter should operate, call

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

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

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

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

    using setCompletionRole(), setCompletionColumn(), and

    setCaseSensitivity().

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

    you can call setModelSorting() with either

    QCompleter::CaseSensitivelySortedModel or

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

    this can lead to significant performance improvements, because QCompleter

    can then use binary search instead of linear search.

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

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

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

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

    Tree Models} section below.

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

    the user.

    \section1 Iterating Through Completions

    To retrieve a single candidate string, call setCompletionPrefix()

    with the text that needs to be completed and call

    currentCompletion(). You can iterate through the list of

    completions as below:

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

    completionCount() returns the total number of completions for the

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

    since it requires a scan of the entire model.

    \section1 The Completion Model

    completionModel() return a list model that contains all possible

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

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

    completions in a custom view. Calling setCompletionPrefix() automatically

    refreshes the completion model.

    \section1 Handling Tree Models

    QCompleter can look for completions in tree models, assuming

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

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

    completion is then performed one level at a time.

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

    The model is a (hierarchical) QDirModel. The completion

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

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

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

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

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

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

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

    The default implementation of splitPath(), splits the completionPrefix

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

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

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

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

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

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

*/

#include "qcompleter_p.h"

#ifndef QT_NO_COMPLETER

#include "QtGui/qscrollbar.h"

#include "QtGui/qstringlistmodel.h"

#include "QtGui/qdirmodel.h"

#include "QtGui/qheaderview.h"

#include "QtGui/qlistview.h"

#include "QtGui/qapplication.h"

#include "QtGui/qevent.h"

#include "QtGui/qheaderview.h"

#include "QtGui/qdesktopwidget.h"

QT_BEGIN_NAMESPACE

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

    : QAbstractProxyModel(*new QCompletionModelPrivate, parent),

      c(c), showAll(false)

{

    createEngine();

}

int QCompletionModel::columnCount(const QModelIndex &) const

{

    Q_D(const QCompletionModel);

    return d->model->columnCount();

}

void QCompletionModel::setSourceModel(QAbstractItemModel *source)

{

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

    if (hadModel)

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

    QAbstractProxyModel::setSourceModel(source);

    if (source) {

        // TODO: Optimize updates in the source model

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

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

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

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

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

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

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

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

    }

    invalidate();

}

void QCompletionModel::createEngine()

{

    bool sortedEngine = false;

    switch (c->sorting) {

    case QCompleter::UnsortedModel:

        sortedEngine = false;

        break;

    case QCompleter::CaseSensitivelySortedModel:

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

        break;

    case QCompleter::CaseInsensitivelySortedModel:

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

        break;

    }

    if (sortedEngine)

        engine.reset(new QSortedModelEngine(c));

    else

        engine.reset(new QUnsortedModelEngine(c));

}

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

{

    Q_D(const QCompletionModel);

    if (!index.isValid())

        return QModelIndex();

    int row;

    QModelIndex parent = engine->curParent;

    if (!showAll) {

        if (!engine->matchCount())

            return QModelIndex();

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

        QIndexMapper& rootIndices = engine->historyMatch.indices;

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

            row = rootIndices[index.row()];

            parent = QModelIndex();

        } else {

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

        }

    } else {

        row = index.row();

    }

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

}

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

{

    if (!idx.isValid())

        return QModelIndex();

    int row = -1;

    if (!showAll) {

        if (!engine->matchCount())

            return QModelIndex();

        QIndexMapper& rootIndices = engine->historyMatch.indices;

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

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

                return QModelIndex();

        } else {

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

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

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

        }

        if (row == -1) {

            QIndexMapper& indices = engine->curMatch.indices;

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

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

        }

        if (row == -1)

            return QModelIndex();

    } else {

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

            return QModelIndex();

        row = idx.row();

    }

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

}

bool QCompletionModel::setCurrentRow(int row)

{

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

        return false;

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

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

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

        return false;

    engine->curRow = row;

    return true;

}

QModelIndex QCompletionModel::currentIndex(bool sourceIndex) const

{

    if (!engine->matchCount())

        return QModelIndex();

    int row = engine->curRow;

    if (showAll)

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

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

    if (!sourceIndex)

        return idx;

    return mapToSource(idx);

}

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

{

    Q_D(const QCompletionModel);

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

        return QModelIndex();

    if (!showAll) {

        if (!engine->matchCount())

            return QModelIndex();

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

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

            if (want > 0)

                engine->filterOnDemand(want);

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

                return QModelIndex();

        }

    } else {

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

            return QModelIndex();

    }

    return createIndex(row, column);

}

int QCompletionModel::completionCount() const

{

    if (!engine->matchCount())

        return 0;

    engine->filterOnDemand(INT_MAX);

    return engine->matchCount();

}

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

{

    Q_D(const QCompletionModel);

    if (parent.isValid())

        return 0;

    if (showAll) {

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

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

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

            return 0;

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

    }

    return completionCount();

}

void QCompletionModel::setFiltered(bool filtered)

{

    if (showAll == !filtered)

        return;

    showAll = !filtered;

    resetModel();

}

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

{

    Q_D(const QCompletionModel);

    if (parent.isValid())

        return false;

    if (showAll)

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

    if (!engine->matchCount())

        return false;

    return true;

}

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

{

    Q_D(const QCompletionModel);

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

}

void QCompletionModel::modelDestroyed()

{

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

    invalidate();

}

void QCompletionModel::rowsInserted()

{

    invalidate();

    emit rowsAdded();

}

void QCompletionModel::invalidate()

{

    engine->cache.clear();

    filter(engine->curParts);

}

void QCompletionModel::filter(const QStringList& parts)

{

    Q_D(QCompletionModel);

    engine->filter(parts);

    resetModel();

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

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

}

void QCompletionModel::resetModel()

{

    if (rowCount() == 0) {

        reset();

        return;

    }

    emit layoutAboutToBeChanged();

    QModelIndexList piList = persistentIndexList();

    QModelIndexList empty;

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

        empty.append(QModelIndex());

    changePersistentIndexList(piList, empty);

    emit layoutChanged();

}

//////////////////////////////////////////////////////////////////////////////

void QCompletionEngine::filter(const QStringList& parts)

{

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

    curParts = parts;

    if (curParts.isEmpty())

        curParts.append(QString());

    curRow = -1;

    curParent = QModelIndex();

    curMatch = QMatchData();

    historyMatch = filterHistory();

    if (!model)

        return;

    QModelIndex parent;

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

        QString part = curParts[i];

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

        if (emi == -1)

            return;

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

    }

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

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

    curParent = parent;

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

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

    else

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

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

}

QMatchData QCompletionEngine::filterHistory()

{

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

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

        return QMatchData();

    bool dirModel = false;

#ifndef QT_NO_DIRMODEL

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

#endif

    QVector<int> v;

    QIndexMapper im(v);

    QMatchData m(im, -1, true);

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

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

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

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

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

#endif

            )

            m.indices.append(i);

    }

    return m;

}

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

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

{

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

        part = part.toLower();

    const CacheItem& map = cache[parent];

    QString key = part;

    while (!key.isEmpty()) {

        key.chop(1);

        if (map.contains(key)) {

            *hint = map[key];

            return true;

        }

    }

    return false;

}

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

{

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

        part = part.toLower();

   const CacheItem& map = cache[parent];

   if (!map.contains(part))

       return false;

   *m = map[part];

   return true;

}

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

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

{

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

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