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

**

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

**

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

#include "qtableview.h"

#ifndef QT_NO_TABLEVIEW

#include <qheaderview.h>

#include <qitemdelegate.h>

#include <qapplication.h>

#include <qpainter.h>

#include <qstyle.h>

#include <qsize.h>

#include <qevent.h>

#include <qbitarray.h>

#include <qscrollbar.h>

#include <qabstractbutton.h>

#include <private/qtableview_p.h>

#ifndef QT_NO_ACCESSIBILITY

#include <qaccessible.h>

#endif

QT_BEGIN_NAMESPACE

/** \internal

  Add a span to the collection. the collection takes the ownership.

  */

void QSpanCollection::addSpan(QSpanCollection::Span *span)

{

    spans.append(span);

    Index::iterator it_y = index.lowerBound(-span->top());

    if (it_y == index.end() || it_y.key() != -span->top()) {

        //there is no spans that starts with the row in the index, so create a sublist for it.

        SubIndex sub_index;

        if (it_y != index.end()) {

            //the previouslist is the list of spans that sarts _before_ the row of the span.

            // and which may intersect this row.

            const SubIndex previousList = it_y.value();

            foreach(Span *s, previousList) {

                //If a subspans intersect the row, we need to split it into subspans

                if(s->bottom() >= span->top())

                    sub_index.insert(-s->left(), s);

            }

        }

        it_y = index.insert(-span->top(), sub_index);

        //we will insert span to *it_y in the later loop

    }

    //insert the span as supspan in all the lists that intesects the span

    while(-it_y.key() <= span->bottom()) {

        (*it_y).insert(-span->left(), span);

        if(it_y == index.begin())

            break;

        --it_y;

    }

}

/** \internal

* Has to be called after the height and width of a span is changed.

*

* old_height is the height before the change

*

* if the size of the span is now 0x0 the span will be deleted.

*/

void QSpanCollection::updateSpan(QSpanCollection::Span *span, int old_height)

{

    if (old_height < span->height()) {

        //add the span as subspan in all the lists that intersect the new covered columns

        Index::iterator it_y = index.lowerBound(-(span->top() + old_height - 1));

        Q_ASSERT(it_y != index.end()); //it_y must exist since the span is in the list

        while (-it_y.key() <= span->bottom()) {

            (*it_y).insert(-span->left(), span);

            if(it_y == index.begin())

                break;

            --it_y;

        }

    } else if (old_height > span->height()) {

        //remove the span from all the subspans lists that intersect the columns not covered anymore

        Index::iterator it_y = index.lowerBound(qMin(-span->bottom(), 0));

        Q_ASSERT(it_y != index.end()); //it_y must exist since the span is in the list

        while (-it_y.key() <= span->top() + old_height -1) {

            if (-it_y.key() > span->bottom()) {

                (*it_y).remove(-span->left());

                if (it_y->isEmpty()) {

                    it_y = index.erase(it_y) - 1;

                }

            }

            if(it_y == index.begin())

                break;

            --it_y;

        }

    }

    if (span->width() == 0 && span->height() == 0) {

        spans.removeOne(span);

        delete span;

    }

}

/** \internal

 * \return a spans that spans over cell x,y  (column,row)  or 0 if there is none.

 */

QSpanCollection::Span *QSpanCollection::spanAt(int x, int y) const

{

    Index::const_iterator it_y = index.lowerBound(-y);

    if (it_y == index.end())

        return 0;

    SubIndex::const_iterator it_x = (*it_y).lowerBound(-x);

    if (it_x == (*it_y).end())

        return 0;

    Span *span = *it_x;

    if (span->right() >= x && span->bottom() >= y)

        return span;

    return 0;

}

/** \internal

* remove and deletes all spans inside the collection

*/

void QSpanCollection::clear()

{

    qDeleteAll(spans);

    index.clear();

    spans.clear();

}

/** \internal

 * return a list to all the spans that spans over cells in the given rectangle

 */

QList<QSpanCollection::Span *> QSpanCollection::spansInRect(int x, int y, int w, int h) const

{

    QSet<Span *> list;

    Index::const_iterator it_y = index.lowerBound(-y);

    if(it_y == index.end())

        --it_y;

    while(-it_y.key() <= y + h) {

        SubIndex::const_iterator it_x = (*it_y).lowerBound(-x);

        if (it_x == (*it_y).end())

            --it_x;

        while(-it_x.key() <= x + w) {

            Span *s = *it_x;

            if (s->bottom() >= y && s->right() >= x)

                list << s;

            if (it_x == (*it_y).begin())

                break;

            --it_x;

        }

        if(it_y == index.begin())

            break;

        --it_y;

    }

    return list.toList();

}

#undef DEBUG_SPAN_UPDATE

#ifdef DEBUG_SPAN_UPDATE

QDebug operator<<(QDebug str, const QSpanCollection::Span &span)

{

    str << "(" << span.top() << "," << span.left() << "," << span.bottom() << "," << span.right() << ")";

    return str;

}

#endif

/** \internal

* Updates the span collection after row insertion.

*/

void QSpanCollection::updateInsertedRows(int start, int end)

{

#ifdef DEBUG_SPAN_UPDATE

    qDebug() << Q_FUNC_INFO;

    qDebug() << start << end;

    qDebug() << index;

#endif

    if (spans.isEmpty())

        return;

    int delta = end - start + 1;

#ifdef DEBUG_SPAN_UPDATE

    qDebug("Before");

#endif

    for (SpanList::iterator it = spans.begin(); it != spans.end(); ++it) {

        Span *span = *it;

#ifdef DEBUG_SPAN_UPDATE

        qDebug() << span << *span;

#endif

        if (span->m_bottom < start)

            continue;

        if (span->m_top >= start)

            span->m_top += delta;

        span->m_bottom += delta;

    }

#ifdef DEBUG_SPAN_UPDATE

    qDebug("After");

    foreach (QSpanCollection::Span *span, spans)

        qDebug() << span << *span;

#endif

    for (Index::iterator it_y = index.begin(); it_y != index.end(); ) {

        int y = -it_y.key();

        if (y < start) {

            ++it_y;

            continue;

        }

        index.insert(-y - delta, it_y.value());

        it_y = index.erase(it_y);

    }

#ifdef DEBUG_SPAN_UPDATE

    qDebug() << index;

#endif

}

/** \internal

* Updates the span collection after column insertion.

*/

void QSpanCollection::updateInsertedColumns(int start, int end)

{

#ifdef DEBUG_SPAN_UPDATE

    qDebug() << Q_FUNC_INFO;

    qDebug() << start << end;

    qDebug() << index;

#endif

    if (spans.isEmpty())

        return;

    int delta = end - start + 1;

#ifdef DEBUG_SPAN_UPDATE

    qDebug("Before");

#endif

    for (SpanList::iterator it = spans.begin(); it != spans.end(); ++it) {

        Span *span = *it;

#ifdef DEBUG_SPAN_UPDATE

        qDebug() << span << *span;

#endif

        if (span->m_right < start)

            continue;

        if (span->m_left >= start)

            span->m_left += delta;

        span->m_right += delta;

    }

#ifdef DEBUG_SPAN_UPDATE

    qDebug("After");

    foreach (QSpanCollection::Span *span, spans)

        qDebug() << span << *span;

#endif

    for (Index::iterator it_y = index.begin(); it_y != index.end(); ++it_y) {

        SubIndex &subindex = it_y.value();

        for (SubIndex::iterator it = subindex.begin(); it != subindex.end(); ) {

            int x = -it.key();

            if (x < start) {

                ++it;

                continue;

            }

            subindex.insert(-x - delta, it.value());

            it = subindex.erase(it);

        }

    }

#ifdef DEBUG_SPAN_UPDATE

    qDebug() << index;

#endif

}

/** \internal

* Cleans a subindex from to be deleted spans. The update argument is used

* to move the spans inside the subindex, in case their anchor changed.

* \return true if no span in this subindex starts at y, and should thus be deleted.

*/

bool QSpanCollection::cleanSpanSubIndex(QSpanCollection::SubIndex &subindex, int y, bool update)

{

    if (subindex.isEmpty())

        return true;

    bool should_be_deleted = true;

    SubIndex::iterator it = subindex.end();

    do {

        --it;

        int x = -it.key();

        Span *span = it.value();

        if (span->will_be_deleted) {

            it = subindex.erase(it);

            continue;

        }

        if (update && span->m_left != x) {

            subindex.insert(-span->m_left, span);

            it = subindex.erase(it);

        }

        if (should_be_deleted && span->m_top == y)

            should_be_deleted = false;

    } while (it != subindex.begin());

    return should_be_deleted;

}

/** \internal

* Updates the span collection after row removal.

*/

void QSpanCollection::updateRemovedRows(int start, int end)

{

#ifdef DEBUG_SPAN_UPDATE

    qDebug() << Q_FUNC_INFO;

    qDebug() << start << end;

    qDebug() << index;

#endif

    if (spans.isEmpty())

        return;

    SpanList spansToBeDeleted;

    int delta = end - start + 1;

#ifdef DEBUG_SPAN_UPDATE

    qDebug("Before");

#endif

    for (SpanList::iterator it = spans.begin(); it != spans.end(); ) {

        Span *span = *it;

#ifdef DEBUG_SPAN_UPDATE

        qDebug() << span << *span;

#endif

        if (span->m_bottom < start) {

            ++it;

            continue;

        }

        if (span->m_top < start) {

            if (span->m_bottom <= end)

                span->m_bottom = start - 1;

            else

                span->m_bottom -= delta;

        } else {

            if (span->m_bottom > end) {

                if (span->m_top <= end)

                    span->m_top = start;

                else

                    span->m_top -= delta;

                span->m_bottom -= delta;

            } else {

                span->will_be_deleted = true;

            }

        }

        if (span->m_top == span->m_bottom && span->m_left == span->m_right)

            span->will_be_deleted = true;

        if (span->will_be_deleted) {

            spansToBeDeleted.append(span);

            it = spans.erase(it);

        } else {

            ++it;

        }

    }

#ifdef DEBUG_SPAN_UPDATE

    qDebug("After");

    foreach (QSpanCollection::Span *span, spans)

        qDebug() << span << *span;

#endif

    if (spans.isEmpty()) {

        qDeleteAll(spansToBeDeleted);

        index.clear();

        return;

    }

    Index::iterator it_y = index.end();

    do {

        --it_y;

        int y = -it_y.key();

        SubIndex &subindex = it_y.value();

        if (y < start) {

            if (cleanSpanSubIndex(subindex, y))

                it_y = index.erase(it_y);

        } else if (y >= start && y <= end) {

            bool span_at_start = false;

            SubIndex spansToBeMoved;

            for (SubIndex::iterator it = subindex.begin(); it != subindex.end(); ++it) {

                Span *span = it.value();

                if (span->will_be_deleted)

                    continue;

                if (!span_at_start && span->m_top == start)

                    span_at_start = true;

                spansToBeMoved.insert(it.key(), span);

            }

            if (y == start && span_at_start)

                subindex.clear();

            else

                it_y = index.erase(it_y);

            if (span_at_start) {

                Index::iterator it_start;

                if (y == start)

                    it_start = it_y;

                else {

                    it_start = index.find(-start);

                    if (it_start == index.end())

                        it_start = index.insert(-start, SubIndex());

                }

                SubIndex &start_subindex = it_start.value();

                for (SubIndex::iterator it = spansToBeMoved.begin(); it != spansToBeMoved.end(); ++it)

                    start_subindex.insert(it.key(), it.value());

            }

        } else {

            if (y == end + 1) {

                Index::iterator it_top = index.find(-y + delta);

                if (it_top == index.end())

                    it_top = index.insert(-y + delta, SubIndex());

                for (SubIndex::iterator it = subindex.begin(); it != subindex.end(); ) {

                    Span *span = it.value();

                    if (!span->will_be_deleted)

                        it_top.value().insert(it.key(), span);

                    ++it;

                }

            } else {

                index.insert(-y + delta, subindex);

            }

            it_y = index.erase(it_y);

        }

    } while (it_y != index.begin());

#ifdef DEBUG_SPAN_UPDATE

    qDebug() << index;

    qDebug("Deleted");

    foreach (QSpanCollection::Span *span, spansToBeDeleted)

        qDebug() << span << *span;

#endif

    qDeleteAll(spansToBeDeleted);

}

/** \internal

* Updates the span collection after column removal.

*/

void QSpanCollection::updateRemovedColumns(int start, int end)

{

#ifdef DEBUG_SPAN_UPDATE

    qDebug() << Q_FUNC_INFO;

    qDebug() << start << end;

    qDebug() << index;

#endif

    if (spans.isEmpty())

        return;

    SpanList toBeDeleted;

    int delta = end - start + 1;

#ifdef DEBUG_SPAN_UPDATE

    qDebug("Before");

#endif

    for (SpanList::iterator it = spans.begin(); it != spans.end(); ) {

        Span *span = *it;

#ifdef DEBUG_SPAN_UPDATE

        qDebug() << span << *span;

#endif

        if (span->m_right < start) {

            ++it;

            continue;

        }

        if (span->m_left < start) {

            if (span->m_right <= end)

                span->m_right = start - 1;

            else

                span->m_right -= delta;

        } else {

            if (span->m_right > end) {

                if (span->m_left <= end)

                    span->m_left = start;

                else

                    span->m_left -= delta;

                span->m_right -= delta;

            } else {

                span->will_be_deleted = true;

            }

        }

        if (span->m_top == span->m_bottom && span->m_left == span->m_right)

            span->will_be_deleted = true;

        if (span->will_be_deleted) {

            toBeDeleted.append(span);

            it = spans.erase(it);

        } else {

            ++it;

        }

    }

#ifdef DEBUG_SPAN_UPDATE

    qDebug("After");

    foreach (QSpanCollection::Span *span, spans)

        qDebug() << span << *span;

#endif

    if (spans.isEmpty()) {

        qDeleteAll(toBeDeleted);

        index.clear();

        return;