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

**

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

** All rights reserved.

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

**

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

**

** $QT_BEGIN_LICENSE:LGPL$

** GNU Lesser General Public License Usage

** 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.

**

** GNU General Public License Usage

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

** Public License version 3.0 as published by the Free Software Foundation

** and appearing in the file LICENSE.GPL included in the packaging of this

** file. Please review the following information to ensure the GNU General

** Public License version 3.0 requirements will be met:

** http://www.gnu.org/copyleft/gpl.html.

**

** Other Usage

** Alternatively, this file may be used in accordance with the terms and

** conditions contained in a signed written agreement between you and Nokia.

**

**

**

**

**

** $QT_END_LICENSE$

**

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

#include "qabstractitemmodel.h"

#include <private/qabstractitemmodel_p.h>

#include <qdatastream.h>

#include <qstringlist.h>

#include <qsize.h>

#include <qmimedata.h>

#include <qdebug.h>

#include <qvector.h>

#include <qstack.h>

#include <qbitarray.h>

#include <limits.h>

QT_BEGIN_NAMESPACE

QPersistentModelIndexData *QPersistentModelIndexData::create(const QModelIndex &index)

{

    Q_ASSERT(index.isValid()); // we will _never_ insert an invalid index in the list

    QPersistentModelIndexData *d = 0;

    QAbstractItemModel *model = const_cast<QAbstractItemModel *>(index.model());

    QHash<QModelIndex, QPersistentModelIndexData *> &indexes = model->d_func()->persistent.indexes;

    const QHash<QModelIndex, QPersistentModelIndexData *>::iterator it = indexes.find(index);

    if (it != indexes.end()) {

        d = (*it);

    } else {

        d = new QPersistentModelIndexData(index);

        indexes.insert(index, d);

    }

    Q_ASSERT(d);

    return d;

}

void QPersistentModelIndexData::destroy(QPersistentModelIndexData *data)

{

    Q_ASSERT(data);

    Q_ASSERT(data->ref == 0);

    QAbstractItemModel *model = const_cast<QAbstractItemModel *>(data->model);

    // a valid persistent model index with a null model pointer can only happen if the model was destroyed

    if (model) {

        QAbstractItemModelPrivate *p = model->d_func();

        Q_ASSERT(p);

        p->removePersistentIndexData(data);

    }

    delete data;

}

/*!

  \class QPersistentModelIndex

  \brief The QPersistentModelIndex class is used to locate data in a data model.

  \ingroup model-view

  A QPersistentModelIndex is a model index that can be stored by an

  application, and later used to access information in a model.

  Unlike the QModelIndex class, it is safe to store a

  QPersistentModelIndex since the model will ensure that references

  to items will continue to be valid as long as they can be accessed

  by the model.

  It is good practice to check that persistent model indexes are valid

  before using them.

  \sa {Model/View Programming}, QModelIndex, QAbstractItemModel

*/

/*!

  \fn QPersistentModelIndex::QPersistentModelIndex()

  \internal

*/

QPersistentModelIndex::QPersistentModelIndex()

    : d(0)

{

}

/*!

  \fn QPersistentModelIndex::QPersistentModelIndex(const QPersistentModelIndex &other)

  Creates a new QPersistentModelIndex that is a copy of the \a other persistent

  model index.

*/

QPersistentModelIndex::QPersistentModelIndex(const QPersistentModelIndex &other)

    : d(other.d)

{

    if (d) d->ref.ref();

}

/*!

    Creates a new QPersistentModelIndex that is a copy of the model \a index.

*/

QPersistentModelIndex::QPersistentModelIndex(const QModelIndex &index)

    : d(0)

{

    if (index.isValid()) {

        d = QPersistentModelIndexData::create(index);

        d->ref.ref();

    }

}

/*!

    \fn QPersistentModelIndex::~QPersistentModelIndex()

    \internal

*/

QPersistentModelIndex::~QPersistentModelIndex()

{

    if (d && !d->ref.deref()) {

        QPersistentModelIndexData::destroy(d);

        d = 0;

    }

}

/*!

  Returns true if this persistent model index is equal to the \a other

  persistent model index; otherwise returns false.

  All values in the persistent model index are used when comparing

  with another persistent model index.

*/

bool QPersistentModelIndex::operator==(const QPersistentModelIndex &other) const

{

    if (d && other.d)

        return d->index == other.d->index;

    return d == other.d;

}

/*!

    \since 4.1

    Returns true if this persistent model index is smaller than the \a other

    persistent model index; otherwise returns false.

    All values in the persistent model index are used when comparing

    with another persistent model index.

*/

bool QPersistentModelIndex::operator<(const QPersistentModelIndex &other) const

{

    if (d && other.d)

        return d->index < other.d->index;

    return d < other.d;

}

/*!

    \fn bool QPersistentModelIndex::operator!=(const QPersistentModelIndex &other) const

    \since 4.2

    Returns true if this persistent model index is not equal to the \a

    other persistent model index; otherwise returns false.

*/

/*!

    Sets the persistent model index to refer to the same item in a model

    as the \a other persistent model index.

*/

QPersistentModelIndex &QPersistentModelIndex::operator=(const QPersistentModelIndex &other)

{

    if (d == other.d)

        return *this;

    if (d && !d->ref.deref())

        QPersistentModelIndexData::destroy(d);

    d = other.d;

    if (d) d->ref.ref();

    return *this;

}

/*!

    Sets the persistent model index to refer to the same item in a model

    as the \a other model index.

*/

QPersistentModelIndex &QPersistentModelIndex::operator=(const QModelIndex &other)

{

    if (d && !d->ref.deref())

        QPersistentModelIndexData::destroy(d);

    if (other.isValid()) {

        d = QPersistentModelIndexData::create(other);

        if (d) d->ref.ref();

    } else {

        d = 0;

    }

    return *this;

}

/*!

  \fn QPersistentModelIndex::operator const QModelIndex&() const

  Cast operator that returns a const QModelIndex&.

*/

QPersistentModelIndex::operator const QModelIndex&() const

{

    static const QModelIndex invalid;

    if (d)

        return d->index;

    return invalid;

}

/*!

    \fn bool QPersistentModelIndex::operator==(const QModelIndex &other) const

    Returns true if this persistent model index refers to the same location as

    the \a other model index; otherwise returns false.

    All values in the persistent model index are used when comparing with

    another model index.

*/

bool QPersistentModelIndex::operator==(const QModelIndex &other) const

{

    if (d)

        return d->index == other;

    return !other.isValid();

}

/*!

    \fn bool QPersistentModelIndex::operator!=(const QModelIndex &other) const

    Returns true if this persistent model index does not refer to the same

    location as the \a other model index; otherwise returns false.

*/

bool QPersistentModelIndex::operator!=(const QModelIndex &other) const

{

    if (d)

        return d->index != other;

    return other.isValid();

}

/*!

    \fn int QPersistentModelIndex::row() const

    Returns the row this persistent model index refers to.

*/

int QPersistentModelIndex::row() const

{

    if (d)

        return d->index.row();

    return -1;

}

/*!

    \fn int QPersistentModelIndex::column() const

    Returns the column this persistent model index refers to.

*/

int QPersistentModelIndex::column() const

{

    if (d)

        return d->index.column();

    return -1;

}

/*!

    \fn void *QPersistentModelIndex::internalPointer() const

    \internal

    Returns a \c{void} \c{*} pointer used by the model to associate the index with

    the internal data structure.

*/

void *QPersistentModelIndex::internalPointer() const

{

    if (d)

        return d->index.internalPointer();

    return 0;

}

/*!

    \fn void *QPersistentModelIndex::internalId() const

    \internal

    Returns a \c{qint64} used by the model to associate the index with

    the internal data structure.

*/

qint64 QPersistentModelIndex::internalId() const

{

    if (d)

        return d->index.internalId();

    return 0;

}

/*!

    Returns the parent QModelIndex for this persistent index, or an invalid

    QModelIndex if it has no parent.

    \sa child() sibling() model()

*/

QModelIndex QPersistentModelIndex::parent() const

{

    if (d)

        return d->index.parent();

    return QModelIndex();

}

/*!

    Returns the sibling at \a row and \a column or an invalid QModelIndex if

    there is no sibling at this position.

    \sa parent() child()

*/

QModelIndex QPersistentModelIndex::sibling(int row, int column) const

{

    if (d)

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

    return QModelIndex();

}

/*!

    Returns the child of the model index that is stored in the given \a row

    and \a column.

    \sa parent() sibling()

*/

QModelIndex QPersistentModelIndex::child(int row, int column) const

{

    if (d)

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

    return QModelIndex();

}

/*!

    Returns the data for the given \a role for the item referred to by the

    index.

    \sa Qt::ItemDataRole, QAbstractItemModel::setData()

*/

QVariant QPersistentModelIndex::data(int role) const

{

    if (d)

        return d->index.data(role);

    return QVariant();

}

/*!

    \since 4.2

    Returns the flags for the item referred to by the index.

*/

Qt::ItemFlags QPersistentModelIndex::flags() const

{

    if (d)

        return d->index.flags();

    return 0;

}

/*!

    Returns the model that the index belongs to.

*/

const QAbstractItemModel *QPersistentModelIndex::model() const

{

    if (d)

        return d->index.model();

    return 0;

}

/*!

    \fn bool QPersistentModelIndex::isValid() const

    Returns true if this persistent model index is valid; otherwise returns

    false.

    A valid index belongs to a model, and has non-negative row and column

    numbers.

    \sa model(), row(), column()

*/

bool QPersistentModelIndex::isValid() const

{

    return d && d->index.isValid();

}

#ifndef QT_NO_DEBUG_STREAM

QDebug operator<<(QDebug dbg, const QModelIndex &idx)

{

#ifndef Q_BROKEN_DEBUG_STREAM

    dbg.nospace() << "QModelIndex(" << idx.row() << ',' << idx.column()

                  << ',' << idx.internalPointer() << ',' << idx.model() << ')';

    return dbg.space();

#else

    qWarning("This compiler doesn't support streaming QModelIndex to QDebug");

    return dbg;

    Q_UNUSED(idx);

#endif

}

QDebug operator<<(QDebug dbg, const QPersistentModelIndex &idx)

{

    if (idx.d)

        dbg << idx.d->index;

    else

        dbg << QModelIndex();

    return dbg;

}

#endif

class QEmptyItemModel : public QAbstractItemModel

{

public:

    explicit QEmptyItemModel(QObject *parent = 0) : QAbstractItemModel(parent) {}

    QModelIndex index(int, int, const QModelIndex &) const { return QModelIndex(); }

    QModelIndex parent(const QModelIndex &) const { return QModelIndex(); }

    int rowCount(const QModelIndex &) const { return 0; }

    int columnCount(const QModelIndex &) const { return 0; }

    bool hasChildren(const QModelIndex &) const { return false; }

    QVariant data(const QModelIndex &, int) const { return QVariant(); }

};

Q_GLOBAL_STATIC(QEmptyItemModel, qEmptyModel)

QAbstractItemModel *QAbstractItemModelPrivate::staticEmptyModel()

{

    return qEmptyModel();

}

namespace {

    struct DefaultRoleNames : public QHash<int, QByteArray>

    {

        DefaultRoleNames() {

            (*this)[Qt::DisplayRole] = "display";

            (*this)[Qt::DecorationRole] = "decoration";

            (*this)[Qt::EditRole] = "edit";

            (*this)[Qt::ToolTipRole] = "toolTip";

            (*this)[Qt::StatusTipRole] = "statusTip";

            (*this)[Qt::WhatsThisRole] = "whatsThis";

        }

    };

}

Q_GLOBAL_STATIC(DefaultRoleNames, qDefaultRoleNames)

const QHash<int,QByteArray> &QAbstractItemModelPrivate::defaultRoleNames()

{

    return *qDefaultRoleNames();

}

static uint typeOfVariant(const QVariant &value)

{

    //return 0 for integer, 1 for floating point and 2 for other

    switch (value.userType()) {

        case QVariant::Bool:

        case QVariant::Int:

        case QVariant::UInt:

        case QVariant::LongLong:

        case QVariant::ULongLong:

        case QVariant::Char:

        case QMetaType::Short:

        case QMetaType::UShort:

        case QMetaType::UChar:

        case QMetaType::ULong:

        case QMetaType::Long:

            return 0;

        case QVariant::Double:

        case QMetaType::Float:

            return 1;

        default:

            return 2;

    }

}

/*!

    \internal

    return true if \a value contains a numerical type

    This function is used by our Q{Tree,Widget,Table}WidgetModel classes to sort.

*/

bool QAbstractItemModelPrivate::variantLessThan(const QVariant &v1, const QVariant &v2)

{

    switch(qMax(typeOfVariant(v1), typeOfVariant(v2)))

    {

    case 0: //integer type

        return v1.toLongLong() < v2.toLongLong();

    case 1: //floating point

        return v1.toReal() < v2.toReal();

    default:

        return v1.toString().localeAwareCompare(v2.toString()) < 0;

    }

}

void QAbstractItemModelPrivate::removePersistentIndexData(QPersistentModelIndexData *data)

{

    if (data->index.isValid()) {

        int removed = persistent.indexes.remove(data->index);

        Q_ASSERT_X(removed == 1, "QPersistentModelIndex::~QPersistentModelIndex",

                   "persistent model indexes corrupted"); //maybe the index was somewhat invalid?

        // This assert may happen if the model use changePersistentIndex in a way that could result on two

        // QPersistentModelIndex pointing to the same index.

        Q_UNUSED(removed);

    }

    // make sure our optimization still works

    for (int i = persistent.moved.count() - 1; i >= 0; --i) {

        int idx = persistent.moved[i].indexOf(data);

        if (idx >= 0)

            persistent.moved[i].remove(idx);

    }

    // update the references to invalidated persistent indexes

    for (int i = persistent.invalidated.count() - 1; i >= 0; --i) {

        int idx = persistent.invalidated[i].indexOf(data);

        if (idx >= 0)

            persistent.invalidated[i].remove(idx);

    }

}

void QAbstractItemModelPrivate::rowsAboutToBeInserted(const QModelIndex &parent,

                                                      int first, int last)

{

    Q_Q(QAbstractItemModel);

    Q_UNUSED(last);

    QVector<QPersistentModelIndexData *> persistent_moved;

    if (first < q->rowCount(parent)) {

        for (QHash<QModelIndex, QPersistentModelIndexData *>::const_iterator it = persistent.indexes.constBegin();

             it != persistent.indexes.constEnd(); ++it) {

            QPersistentModelIndexData *data = *it;

            const QModelIndex &index = data->index;

            if (index.row() >= first && index.isValid() && index.parent() == parent) {

                persistent_moved.append(data);

            }

        }

    }

    persistent.moved.push(persistent_moved);

}

void QAbstractItemModelPrivate::rowsInserted(const QModelIndex &parent,

                                             int first, int last)

{

    QVector<QPersistentModelIndexData *> persistent_moved = persistent.moved.pop();

    int count = (last - first) + 1; // it is important to only use the delta, because the change could be nested

    for (QVector<QPersistentModelIndexData *>::const_iterator it = persistent_moved.constBegin();

         it != persistent_moved.constEnd(); ++it) {

        QPersistentModelIndexData *data = *it;

        QModelIndex old = data->index;

        persistent.indexes.erase(persistent.indexes.find(old));

        data->index = q_func()->index(old.row() + count, old.column(), parent);

        if (data->index.isValid()) {

            persistent.insertMultiAtEnd(data->index, data);

        } else {

            qWarning() << "QAbstractItemModel::endInsertRows:  Invalid index (" << old.row() + count << ',' << old.column() << ") in model" << q_func();

        }

    }

}

void QAbstractItemModelPrivate::itemsAboutToBeMoved(const QModelIndex &srcParent, int srcFirst, int srcLast, const QModelIndex &destinationParent, int destinationChild, Qt::Orientation orientation)

{

    QVector<QPersistentModelIndexData *> persistent_moved_explicitly;

    QVector<QPersistentModelIndexData *> persistent_moved_in_source;

    QVector<QPersistentModelIndexData *> persistent_moved_in_destination;

    QHash<QModelIndex, QPersistentModelIndexData *>::const_iterator it;

    const QHash<QModelIndex, QPersistentModelIndexData *>::const_iterator begin = persistent.indexes.constBegin();

    const QHash<QModelIndex, QPersistentModelIndexData *>::const_iterator end = persistent.indexes.constEnd();

    const bool sameParent = (srcParent == destinationParent);

    const bool movingUp = (srcFirst > destinationChild);

    for ( it = begin; it != end; ++it) {

        QPersistentModelIndexData *data = *it;

        const QModelIndex &index = data->index;

        const QModelIndex &parent = index.parent();

        const bool isSourceIndex = (parent == srcParent);

        const bool isDestinationIndex = (parent == destinationParent);

        int childPosition;

        if (orientation == Qt::Vertical)

            childPosition = index.row();

        else

            childPosition = index.column();

        if (!index.isValid() || !(isSourceIndex || isDestinationIndex ) )

            continue;

        if (!sameParent && isDestinationIndex) {

            if (childPosition >= destinationChild)

                persistent_moved_in_destination.append(data);

            continue;

        }

        if (sameParent && movingUp && childPosition < destinationChild)

            continue;

        if (sameParent && !movingUp && childPosition < srcFirst )

            continue;

        if (!sameParent && childPosition < srcFirst)

            continue;

        if (sameParent && (childPosition > srcLast) && (childPosition >= destinationChild ))

            continue;

        if ((childPosition <= srcLast) && (childPosition >= srcFirst)) {

            persistent_moved_explicitly.append(data);

        } else {

            persistent_moved_in_source.append(data);

        }

    }

    persistent.moved.push(persistent_moved_explicitly);

    persistent.moved.push(persistent_moved_in_source);

    persistent.moved.push(persistent_moved_in_destination);

}

/*!

  \internal

  Moves persistent indexes \a indexes by amount \a change. The change will be either a change in row value or a change in

  column value depending on the value of \a orientation. The indexes may also be moved to a different parent if \a parent

  differs from the existing parent for the index.

*/

void QAbstractItemModelPrivate::movePersistentIndexes(QVector<QPersistentModelIndexData *> indexes, int change, const QModelIndex &parent, Qt::Orientation orientation)

{

    QVector<QPersistentModelIndexData *>::const_iterator it;

    const QVector<QPersistentModelIndexData *>::const_iterator begin = indexes.constBegin();

    const QVector<QPersistentModelIndexData *>::const_iterator end = indexes.constEnd();

    for (it = begin; it != end; ++it)

    {

        QPersistentModelIndexData *data = *it;

        int row = data->index.row();

        int column = data->index.column();

        if (Qt::Vertical == orientation)

            row += change;

        else

            column += change;

        persistent.indexes.erase(persistent.indexes.find(data->index));

        data->index = q_func()->index(row, column, parent);

        if (data->index.isValid()) {

            persistent.insertMultiAtEnd(data->index, data);

        } else {

            qWarning() << "QAbstractItemModel::endMoveRows:  Invalid index (" << row << "," << column << ") in model" << q_func();

        }

    }

}

void QAbstractItemModelPrivate::itemsMoved(const QModelIndex &sourceParent, int sourceFirst, int sourceLast, const QModelIndex &destinationParent, int destinationChild, Qt::Orientation orientation)

{

    QVector<QPersistentModelIndexData *> moved_in_destination = persistent.moved.pop();

    QVector<QPersistentModelIndexData *> moved_in_source = persistent.moved.pop();

    QVector<QPersistentModelIndexData *> moved_explicitly = persistent.moved.pop();

    const bool sameParent = (sourceParent == destinationParent);

    const bool movingUp = (sourceFirst > destinationChild);

    const int explicit_change = (!sameParent || movingUp) ? destinationChild - sourceFirst : destinationChild - sourceLast - 1 ;

    const int source_change = (!sameParent || !movingUp) ? -1*(sourceLast - sourceFirst + 1) : sourceLast - sourceFirst + 1 ;

    const int destination_change = sourceLast - sourceFirst + 1;

    movePersistentIndexes(moved_explicitly, explicit_change, destinationParent, orientation);

    movePersistentIndexes(moved_in_source, source_change, sourceParent, orientation);

    movePersistentIndexes(moved_in_destination, destination_change, destinationParent, orientation);

}

void QAbstractItemModelPrivate::rowsAboutToBeRemoved(const QModelIndex &parent,

                                                     int first, int last)

{

    QVector<QPersistentModelIndexData *>  persistent_moved;

    QVector<QPersistentModelIndexData *>  persistent_invalidated;

    // find the persistent indexes that are affected by the change, either by being in the removed subtree

    // or by being on the same level and below the removed rows

    for (QHash<QModelIndex, QPersistentModelIndexData *>::const_iterator it = persistent.indexes.constBegin();

         it != persistent.indexes.constEnd(); ++it) {

        QPersistentModelIndexData *data = *it;

        bool level_changed = false;

        QModelIndex current = data->index;

        while (current.isValid()) {

            QModelIndex current_parent = current.parent();

            if (current_parent == parent) { // on the same level as the change

                if (!level_changed && current.row() > last) // below the removed rows

                    persistent_moved.append(data);

                else if (current.row() <= last && current.row() >= first) // in the removed subtree

                    persistent_invalidated.append(data);

                break;

            }

            current = current_parent;

            level_changed = true;

        }

    }

    persistent.moved.push(persistent_moved);

    persistent.invalidated.push(persistent_invalidated);

}

void QAbstractItemModelPrivate::rowsRemoved(const QModelIndex &parent,

                                            int first, int last)

{

    QVector<QPersistentModelIndexData *> persistent_moved = persistent.moved.pop();

    int count = (last - first) + 1; // it is important to only use the delta, because the change could be nested

    for (QVector<QPersistentModelIndexData *>::const_iterator it = persistent_moved.constBegin();

         it != persistent_moved.constEnd(); ++it) {

        QPersistentModelIndexData *data = *it;

        QModelIndex old = data->index;

        persistent.indexes.erase(persistent.indexes.find(old));

        data->index = q_func()->index(old.row() - count, old.column(), parent);

        if (data->index.isValid()) {

            persistent.insertMultiAtEnd(data->index, data);

        } else {

            qWarning() << "QAbstractItemModel::endRemoveRows:  Invalid index (" << old.row() - count << ',' << old.column() << ") in model" << q_func();

        }

    }

    QVector<QPersistentModelIndexData *> persistent_invalidated = persistent.invalidated.pop();

    for (QVector<QPersistentModelIndexData *>::const_iterator it = persistent_invalidated.constBegin();

         it != persistent_invalidated.constEnd(); ++it) {

        QPersistentModelIndexData *data = *it;

        persistent.indexes.erase(persistent.indexes.find(data->index));

        data->index = QModelIndex();

        data->model = 0;

    }

}

void QAbstractItemModelPrivate::columnsAboutToBeInserted(const QModelIndex &parent,

                                                         int first, int last)

{

    Q_Q(QAbstractItemModel);

    Q_UNUSED(last);

    QVector<QPersistentModelIndexData *> persistent_moved;

    if (first < q->columnCount(parent)) {

        for (QHash<QModelIndex, QPersistentModelIndexData *>::const_iterator it = persistent.indexes.constBegin();

             it != persistent.indexes.constEnd(); ++it) {

            QPersistentModelIndexData *data = *it;

            const QModelIndex &index = data->index;

            if (index.column() >= first && index.isValid() && index.parent() == parent)

                persistent_moved.append(data);

        }

    }

    persistent.moved.push(persistent_moved);

}

void QAbstractItemModelPrivate::columnsInserted(const QModelIndex &parent,

                                                int first, int last)

{

    QVector<QPersistentModelIndexData *> persistent_moved = persistent.moved.pop();

    int count = (last - first) + 1; // it is important to only use the delta, because the change could be nested

    for (QVector<QPersistentModelIndexData *>::const_iterator it = persistent_moved.constBegin();

         it != persistent_moved.constEnd(); ++it) {

        QPersistentModelIndexData *data = *it;

        QModelIndex old = data->index;

        persistent.indexes.erase(persistent.indexes.find(old));

        data->index = q_func()->index(old.row(), old.column() + count, parent);

        if (data->index.isValid()) {

            persistent.insertMultiAtEnd(data->index, data);

        } else {

            qWarning() << "QAbstractItemModel::endInsertColumns:  Invalid index (" << old.row() << ',' << old.column() + count << ") in model" << q_func();

        }

     }

}

void QAbstractItemModelPrivate::columnsAboutToBeRemoved(const QModelIndex &parent,

                                                        int first, int last)

{

    QVector<QPersistentModelIndexData *> persistent_moved;

    QVector<QPersistentModelIndexData *> persistent_invalidated;

    // find the persistent indexes that are affected by the change, either by being in the removed subtree

    // or by being on the same level and to the right of the removed columns

    for (QHash<QModelIndex, QPersistentModelIndexData *>::const_iterator it = persistent.indexes.constBegin();

         it != persistent.indexes.constEnd(); ++it) {

        QPersistentModelIndexData *data = *it;

        bool level_changed = false;

        QModelIndex current = data->index;

        while (current.isValid()) {

            QModelIndex current_parent = current.parent();

            if (current_parent == parent) { // on the same level as the change

                if (!level_changed && current.column() > last) // right of the removed columns

                    persistent_moved.append(data);

                else if (current.column() <= last && current.column() >= first) // in the removed subtree

                    persistent_invalidated.append(data);

                break;

            }

            current = current_parent;

            level_changed = true;

        }

    }

    persistent.moved.push(persistent_moved);

    persistent.invalidated.push(persistent_invalidated);

}

void QAbstractItemModelPrivate::columnsRemoved(const QModelIndex &parent,

                                               int first, int last)

{

    QVector<QPersistentModelIndexData *> persistent_moved = persistent.moved.pop();

    int count = (last - first) + 1; // it is important to only use the delta, because the change could be nested

    for (QVector<QPersistentModelIndexData *>::const_iterator it = persistent_moved.constBegin();

         it != persistent_moved.constEnd(); ++it) {

        QPersistentModelIndexData *data = *it;

        QModelIndex old = data->index;

        persistent.indexes.erase(persistent.indexes.find(old));

        data->index = q_func()->index(old.row(), old.column() - count, parent);

        if (data->index.isValid()) {

            persistent.insertMultiAtEnd(data->index, data);

        } else {

            qWarning() << "QAbstractItemModel::endRemoveColumns:  Invalid index (" << old.row() << ',' << old.column() - count << ") in model" << q_func();

        }

    }

    QVector<QPersistentModelIndexData *> persistent_invalidated = persistent.invalidated.pop();

    for (QVector<QPersistentModelIndexData *>::const_iterator it = persistent_invalidated.constBegin();

         it != persistent_invalidated.constEnd(); ++it) {

        QPersistentModelIndexData *data = *it;

        persistent.indexes.erase(persistent.indexes.find(data->index));

        data->index = QModelIndex();

        data->model = 0;

    }

}

/*!

    \class QModelIndex

    \brief The QModelIndex class is used to locate data in a data model.

    \ingroup model-view

    This class is used as an index into item models derived from

    QAbstractItemModel. The index is used by item views, delegates, and

    selection models to locate an item in the model.

    New QModelIndex objects are created by the model using the

    QAbstractItemModel::createIndex() function. An \e invalid model index can

    be constructed with the QModelIndex constructor. Invalid indexes are often

    used as parent indexes when referring to top-level items in a model.

    Model indexes refer to items in models, and contain all the information

    required to specify their locations in those models. Each index is located

    in a given row and column, and may have a parent index; use row(),

    column(), and parent() to obtain this information. Each top-level item in a

    model is represented by a model index that does not have a parent index -

    in this case, parent() will return an invalid model index, equivalent to an

    index constructed with the zero argument form of the QModelIndex()

    constructor.

    To obtain a model index that refers to an existing item in a model, call

    QAbstractItemModel::index() with the required row and column values, and

    the model index of the parent. When referring to top-level items in a

    model, supply QModelIndex() as the parent index.

    The model() function returns the model that the index references as a

    QAbstractItemModel. The child() function is used to examine items held

    under the index in the model. The sibling() function allows you to traverse

    items in the model on the same level as the index.

    \note Model indexes should be used immediately and then discarded. You

    should not rely on indexes to remain valid after calling model functions

    that change the structure of the model or delete items. If you need to

    keep a model index over time use a QPersistentModelIndex.

    \sa {Model/View Programming}, QPersistentModelIndex, QAbstractItemModel

*/

/*!

    \fn QModelIndex::QModelIndex()

    Creates a new empty model index. This type of model index is used to

    indicate that the position in the model is invalid.

    \sa isValid() QAbstractItemModel

*/

/*!

    \fn QModelIndex::QModelIndex(int row, int column, void *data, const QAbstractItemModel *model)

    \internal

    Creates a new model index at the given \a row and \a column,

    pointing to some \a data.

*/

/*!

    \fn QModelIndex::QModelIndex(const QModelIndex &other)

    Creates a new model index that is a copy of the \a other model

    index.

*/

/*!

    \fn QModelIndex::~QModelIndex()

    Destroys the model index.

*/

/*!

    \fn int QModelIndex::row() const

    Returns the row this model index refers to.

*/

/*!

    \fn int QModelIndex::column() const

    Returns the column this model index refers to.

*/

/*!

    \fn void *QModelIndex::internalPointer() const

    Returns a \c{void} \c{*} pointer used by the model to associate

    the index with the internal data structure.

    \sa QAbstractItemModel::createIndex()

*/

/*!

    \fn void *QModelIndex::internalId() const

    Returns a \c{qint64} used by the model to associate

    the index with the internal data structure.

    \sa QAbstractItemModel::createIndex()

*/

/*!

    \fn bool QModelIndex::isValid() const

    Returns true if this model index is valid; otherwise returns false.

    A valid index belongs to a model, and has non-negative row and column

    numbers.

    \sa model(), row(), column()

*/

/*!

    \fn const QAbstractItemModel *QModelIndex::model() const

    Returns a pointer to the model containing the item that this index

    refers to.

    A const pointer to the model is returned because calls to non-const

    functions of the model might invalidate the model index and possibly

    crash your application.

*/

/*!

    \fn QModelIndex QModelIndex::sibling(int row, int column) const

    Returns the sibling at \a row and \a column. If there is no sibling at this

    position, an invalid QModelIndex is returned.

    \sa parent(), child()

*/

/*!

    \fn QModelIndex QModelIndex::child(int row, int column) const

    Returns the child of the model index that is stored in the given \a row and

    \a column.

    \note This function does not work for an invalid model index which is often

    used as the root index.

    \sa parent(), sibling()

*/

/*!

    \fn QVariant QModelIndex::data(int role) const

    Returns the data for the given \a role for the item referred to by the

    index.

*/

/*!

    \fn Qt::ItemFlags QModelIndex::flags() const

    \since 4.2

    Returns the flags for the item referred to by the index.

*/

/*!

    \fn bool QModelIndex::operator==(const QModelIndex &other) const

    Returns true if this model index refers to the same location as the

    \a other model index; otherwise returns false.

    All values in the model index are used when comparing with another model

    index.

*/

/*!

    \fn bool QModelIndex::operator!=(const QModelIndex &other) const

    Returns true if this model index does not refer to the same location as

    the \a other model index; otherwise returns false.

*/

/*!

    \fn QModelIndex QModelIndex::parent() const

    Returns the parent of the model index, or QModelIndex() if it has no

    parent.

    \sa child(), sibling(), model()

*/

/*!

    \class QAbstractItemModel

    \brief The QAbstractItemModel class provides the abstract interface for

    item model classes.

    \ingroup model-view

    The QAbstractItemModel class defines the standard interface that item

    models must use to be able to interoperate with other components in the

    model/view architecture. It is not supposed to be instantiated directly.

    Instead, you should subclass it to create new models.

    The QAbstractItemModel class is one of the \l{Model/View Classes}

    and is part of Qt's \l{Model/View Programming}{model/view framework}.

    If you need a model to use with a QListView or a QTableView, you should

    consider subclassing QAbstractListModel or QAbstractTableModel instead of

    this class.

    The underlying data model is exposed to views and delegates as a hierarchy

    of tables. If you do not make use of the hierarchy, then the model is a

    simple table of rows and columns. Each item has a unique index specified by

    a QModelIndex.

    \image modelindex-no-parent.png

    Every item of data that can be accessed via a model has an associated model

    index. You can obtain this model index using the index() function. Each

    index may have a sibling() index; child items have a parent() index.

    Each item has a number of data elements associated with it and they can be

    retrieved by specifying a role (see \l Qt::ItemDataRole) to the model's

    data() function. Data for all available roles can be obtained at the same

    time using the itemData() function.

    Data for each role is set using a particular \l Qt::ItemDataRole. Data for

    individual roles are set individually with setData(), or they can be set

    for all roles with setItemData().

    Items can be queried with flags() (see \l Qt::ItemFlag) to see if they can

    be selected, dragged, or manipulated in other ways.

    If an item has child objects, hasChildren() returns true for the

    corresponding index.

    The model has a rowCount() and a columnCount() for each level of the

    hierarchy. Rows and columns can be inserted and removed with insertRows(),

    insertColumns(), removeRows(), and removeColumns().

    The model emits signals to indicate changes. For example, dataChanged() is

    emitted whenever items of data made available by the model are changed.

    Changes to the headers supplied by the model cause headerDataChanged() to

    be emitted. If the structure of the underlying data changes, the model can

    emit layoutChanged() to indicate to any attached views that they should

    redisplay any items shown, taking the new structure into account.

    The items available through the model can be searched for particular data

    using the match() function.

    To sort the model, you can use sort().

    \section1 Subclassing

    \note Some general guidelines for subclassing models are available in the

    \l{Model Subclassing Reference}.

    When subclassing QAbstractItemModel, at the very least you must implement

    index(), parent(), rowCount(), columnCount(), and data(). These functions

    are used in all read-only models, and form the basis of editable models.

    You can also reimplement hasChildren() to provide special behavior for

    models where the implementation of rowCount() is expensive. This makes it

    possible for models to restrict the amount of data requested by views, and

    can be used as a way to implement lazy population of model data.

    To enable editing in your model, you must also implement setData(), and

    reimplement flags() to ensure that \c ItemIsEditable is returned.  You can

    also reimplement headerData() and setHeaderData() to control the way the

    headers for your model are presented.

    The dataChanged() and headerDataChanged() signals must be emitted

    explicitly when reimplementing the setData() and setHeaderData() functions,

    respectively.

    Custom models need to create model indexes for other components to use. To

    do this, call createIndex() with suitable row and column numbers for the

    item, and an identifier for it, either as a pointer or as an integer value.

    The combination of these values must be unique for each item. Custom models

    typically use these unique identifiers in other reimplemented functions to

    retrieve item data and access information about the item's parents and

    children. See the \l{Simple Tree Model Example} for more information about

    unique identifiers.

    It is not necessary to support every role defined in Qt::ItemDataRole.

    Depending on the type of data contained within a model, it may only be

    useful to implement the data() function to return valid information for

    some of the more common roles. Most models provide at least a textual

    representation of item data for the Qt::DisplayRole, and well-behaved

    models should also provide valid information for the Qt::ToolTipRole and

    Qt::WhatsThisRole. Supporting these roles enables models to be used with

    standard Qt views. However, for some models that handle highly-specialized

    data, it may be appropriate to provide data only for user-defined roles.

    Models that provide interfaces to resizable data structures can provide

    implementations of insertRows(), removeRows(), insertColumns(),and

    removeColumns(). When implementing these functions, it is important to

    notify any connected views about changes to the model's dimensions both

    \e before and \e after they occur:

    \list

        \o An insertRows() implementation must call beginInsertRows() \e before

           inserting new rows into the data structure, and endInsertRows()

           \e{immediately afterwards}.

        \o An insertColumns() implementation must call beginInsertColumns()

           \e before inserting new columns into the data structure, and

           endInsertColumns() \e{immediately afterwards}.

        \o A removeRows() implementation must call beginRemoveRows() \e before

           the rows are removed from the data structure, and endRemoveRows()

           \e{immediately afterwards}.

        \o A removeColumns() implementation must call beginRemoveColumns()

           \e before the columns are removed from the data structure, and

           endRemoveColumns() \e{immediately afterwards}.

    \endlist

    The \e private signals that these functions emit give attached components

    the chance to take action before any data becomes unavailable. The

    encapsulation of the insert and remove operations with these begin and end

    functions also enables the model to manage \l{QPersistentModelIndex}

    {persistent model indexes} correctly. \bold{If you want selections to be

    handled properly, you must ensure that you call these functions.} If you

    insert or remove an item with children, you do not need to call these

    functions for the child items. In other words, the parent item will take

    care of its child items.

    To create models that populate incrementally, you can reimplement

    fetchMore() and canFetchMore(). If the reimplementation of fetchMore() adds

    rows to the model, \l{QAbstractItemModel::}{beginInsertRows()} and

    \l{QAbstractItemModel::}{endInsertRows()} must be called.

    \sa {Model Classes}, {Model Subclassing Reference}, QModelIndex,

        QAbstractItemView, {Using drag and drop with item views},

        {Simple DOM Model Example}, {Simple Tree Model Example},

        {Editable Tree Model Example}, {Fetch More Example}

*/

/*!

    \fn QModelIndex QAbstractItemModel::index(int row, int column, const QModelIndex &parent) const = 0

    Returns the index of the item in the model specified by the given \a row,

    \a column and \a parent index.

    When reimplementing this function in a subclass, call createIndex() to

    generate model indexes that other components can use to refer to items in

    your model.

    \sa createIndex()

*/

/*!

    \fn bool QAbstractItemModel::insertColumn(int column, const QModelIndex &parent)

    Inserts a single column before the given \a column in the child items of

    the \a parent specified.

    Returns true if the column is inserted; otherwise returns false.

    \sa insertColumns() insertRow() removeColumn()

*/

/*!

    \fn bool QAbstractItemModel::insertRow(int row, const QModelIndex &parent)

    \note The base class implementation of this function does nothing and

    returns false.

    Inserts a single row before the given \a row in the child items of the

    \a parent specified.

    Returns true if the row is inserted; otherwise returns false.

    \sa insertRows() insertColumn() removeRow()

*/

/*!

    \fn QObject *QAbstractItemModel::parent() const

    \internal

*/

/*!

    \fn QModelIndex QAbstractItemModel::parent(const QModelIndex &index) const = 0

    Returns the parent of the model item with the given \a index. If the item

    has no parent, an invalid QModelIndex is returned.

    A common convention used in models that expose tree data structures is that

    only items in the first column have children. For that case, when

    reimplementing this function in a subclass the column of the returned

    QModelIndex would be 0.

    When reimplementing this function in a subclass, be careful to avoid

    calling QModelIndex member functions, such as QModelIndex::parent(), since

    indexes belonging to your model will simply call your implementation,

    leading to infinite recursion.

    \sa createIndex()

*/

/*!

    \fn bool QAbstractItemModel::removeColumn(int column, const QModelIndex &parent)

    Removes the given \a column from the child items of the \a parent

    specified.

    Returns true if the column is removed; otherwise returns false.

    \sa removeColumns(), removeRow(), insertColumn()

*/

/*!