QTreeView: fix crash when starting a drag with hidden columns.
[qt:qt.git] / src / gui / itemviews / qtreeview.cpp
1 /****************************************************************************
2 **
3 ** Copyright (C) 2011 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 ** GNU Lesser General Public License Usage
11 ** This file may be used under the terms of the GNU Lesser General Public
12 ** License version 2.1 as published by the Free Software Foundation and
13 ** appearing in the file LICENSE.LGPL included in the packaging of this
14 ** file. Please review the following information to ensure the GNU Lesser
15 ** General Public License version 2.1 requirements will be met:
16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
17 **
18 ** In addition, as a special exception, Nokia gives you certain additional
19 ** rights. These rights are described in the Nokia Qt LGPL Exception
20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
21 **
22 ** GNU General Public License Usage
23 ** Alternatively, this file may be used under the terms of the GNU General
24 ** Public License version 3.0 as published by the Free Software Foundation
25 ** and appearing in the file LICENSE.GPL included in the packaging of this
26 ** file. Please review the following information to ensure the GNU General
27 ** Public License version 3.0 requirements will be met:
28 ** http://www.gnu.org/copyleft/gpl.html.
29 **
30 ** Other Usage
31 ** Alternatively, this file may be used in accordance with the terms and
32 ** conditions contained in a signed written agreement between you and Nokia.
33 **
34 **
35 **
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 #include "qtreeview.h"
42
43 #ifndef QT_NO_TREEVIEW
44 #include <qheaderview.h>
45 #include <qitemdelegate.h>
46 #include <qapplication.h>
47 #include <qscrollbar.h>
48 #include <qpainter.h>
49 #include <qstack.h>
50 #include <qstyle.h>
51 #include <qstyleoption.h>
52 #include <qevent.h>
53 #include <qpen.h>
54 #include <qdebug.h>
55 #ifndef QT_NO_ACCESSIBILITY
56 #include <qaccessible.h>
57 #include <qaccessible2.h>
58 #endif
59
60 #include <private/qtreeview_p.h>
61
62 QT_BEGIN_NAMESPACE
63
64 /*!
65     \class QTreeView
66     \brief The QTreeView class provides a default model/view implementation of a tree view.
67
68     \ingroup model-view
69     \ingroup advanced
70
71
72     A QTreeView implements a tree representation of items from a
73     model. This class is used to provide standard hierarchical lists that
74     were previously provided by the \c QListView class, but using the more
75     flexible approach provided by Qt's model/view architecture.
76
77     The QTreeView class is one of the \l{Model/View Classes} and is part of
78     Qt's \l{Model/View Programming}{model/view framework}.
79
80     QTreeView implements the interfaces defined by the
81     QAbstractItemView class to allow it to display data provided by
82     models derived from the QAbstractItemModel class.
83
84     It is simple to construct a tree view displaying data from a
85     model. In the following example, the contents of a directory are
86     supplied by a QDirModel and displayed as a tree:
87
88     \snippet doc/src/snippets/shareddirmodel/main.cpp 3
89     \snippet doc/src/snippets/shareddirmodel/main.cpp 6
90
91     The model/view architecture ensures that the contents of the tree view
92     are updated as the model changes.
93
94     Items that have children can be in an expanded (children are
95     visible) or collapsed (children are hidden) state. When this state
96     changes a collapsed() or expanded() signal is emitted with the
97     model index of the relevant item.
98
99     The amount of indentation used to indicate levels of hierarchy is
100     controlled by the \l indentation property.
101
102     Headers in tree views are constructed using the QHeaderView class and can
103     be hidden using \c{header()->hide()}. Note that each header is configured
104     with its \l{QHeaderView::}{stretchLastSection} property set to true,
105     ensuring that the view does not waste any of the space assigned to it for
106     its header. If this value is set to true, this property will override the
107     resize mode set on the last section in the header.
108
109
110     \section1 Key Bindings
111
112     QTreeView supports a set of key bindings that enable the user to
113     navigate in the view and interact with the contents of items:
114
115     \table
116     \header \o Key \o Action
117     \row \o Up   \o Moves the cursor to the item in the same column on
118          the previous row. If the parent of the current item has no more rows to
119          navigate to, the cursor moves to the relevant item in the last row
120          of the sibling that precedes the parent.
121     \row \o Down \o Moves the cursor to the item in the same column on
122          the next row. If the parent of the current item has no more rows to
123          navigate to, the cursor moves to the relevant item in the first row
124          of the sibling that follows the parent.
125     \row \o Left  \o Hides the children of the current item (if present)
126          by collapsing a branch.
127     \row \o Minus  \o Same as LeftArrow.
128     \row \o Right \o Reveals the children of the current item (if present)
129          by expanding a branch.
130     \row \o Plus  \o Same as RightArrow.
131     \row \o Asterisk  \o Expands all children of the current item (if present).
132     \row \o PageUp   \o Moves the cursor up one page.
133     \row \o PageDown \o Moves the cursor down one page.
134     \row \o Home \o Moves the cursor to an item in the same column of the first
135          row of the first top-level item in the model.
136     \row \o End  \o Moves the cursor to an item in the same column of the last
137          row of the last top-level item in the model.
138     \row \o F2   \o In editable models, this opens the current item for editing.
139          The Escape key can be used to cancel the editing process and revert
140          any changes to the data displayed.
141     \endtable
142
143     \omit
144     Describe the expanding/collapsing concept if not covered elsewhere.
145     \endomit
146
147     \table 100%
148     \row \o \inlineimage windowsxp-treeview.png Screenshot of a Windows XP style tree view
149          \o \inlineimage macintosh-treeview.png Screenshot of a Macintosh style tree view
150          \o \inlineimage plastique-treeview.png Screenshot of a Plastique style tree view
151     \row \o A \l{Windows XP Style Widget Gallery}{Windows XP style} tree view.
152          \o A \l{Macintosh Style Widget Gallery}{Macintosh style} tree view.
153          \o A \l{Plastique Style Widget Gallery}{Plastique style} tree view.
154     \endtable
155
156     \section1 Improving Performance
157
158     It is possible to give the view hints about the data it is handling in order
159     to improve its performance when displaying large numbers of items. One approach
160     that can be taken for views that are intended to display items with equal heights
161     is to set the \l uniformRowHeights property to true.
162
163     \sa QListView, QTreeWidget, {View Classes}, QAbstractItemModel, QAbstractItemView,
164         {Dir View Example}
165 */
166
167
168 /*!
169   \fn void QTreeView::expanded(const QModelIndex &index)
170
171   This signal is emitted when the item specified by \a index is expanded.
172 */
173
174
175 /*!
176   \fn void QTreeView::collapsed(const QModelIndex &index)
177
178   This signal is emitted when the item specified by \a index is collapsed.
179 */
180
181 /*!
182     Constructs a tree view with a \a parent to represent a model's
183     data. Use setModel() to set the model.
184
185     \sa QAbstractItemModel
186 */
187 QTreeView::QTreeView(QWidget *parent)
188     : QAbstractItemView(*new QTreeViewPrivate, parent)
189 {
190     Q_D(QTreeView);
191     d->initialize();
192 }
193
194 /*!
195   \internal
196 */
197 QTreeView::QTreeView(QTreeViewPrivate &dd, QWidget *parent)
198     : QAbstractItemView(dd, parent)
199 {
200     Q_D(QTreeView);
201     d->initialize();
202 }
203
204 /*!
205   Destroys the tree view.
206 */
207 QTreeView::~QTreeView()
208 {
209 }
210
211 /*!
212   \reimp
213 */
214 void QTreeView::setModel(QAbstractItemModel *model)
215 {
216     Q_D(QTreeView);
217     if (model == d->model)
218         return;
219     if (d->model && d->model != QAbstractItemModelPrivate::staticEmptyModel()) {
220         disconnect(d->model, SIGNAL(rowsRemoved(QModelIndex,int,int)),
221                 this, SLOT(rowsRemoved(QModelIndex,int,int)));
222
223         disconnect(d->model, SIGNAL(modelAboutToBeReset()), this, SLOT(_q_modelAboutToBeReset()));
224     }
225
226     if (d->selectionModel) { // support row editing
227         disconnect(d->selectionModel, SIGNAL(currentRowChanged(QModelIndex,QModelIndex)),
228                    d->model, SLOT(submit()));
229         disconnect(d->model, SIGNAL(rowsRemoved(QModelIndex,int,int)),
230                    this, SLOT(rowsRemoved(QModelIndex,int,int)));
231         disconnect(d->model, SIGNAL(modelAboutToBeReset()), this, SLOT(_q_modelAboutToBeReset()));
232     }
233     d->viewItems.clear();
234     d->expandedIndexes.clear();
235     d->hiddenIndexes.clear();
236     d->header->setModel(model);
237     QAbstractItemView::setModel(model);
238
239     // QAbstractItemView connects to a private slot
240     disconnect(d->model, SIGNAL(rowsRemoved(QModelIndex,int,int)),
241                this, SLOT(_q_rowsRemoved(QModelIndex,int,int)));
242     // do header layout after the tree
243     disconnect(d->model, SIGNAL(layoutChanged()),
244                d->header, SLOT(_q_layoutChanged()));
245     // QTreeView has a public slot for this
246     connect(d->model, SIGNAL(rowsRemoved(QModelIndex,int,int)),
247             this, SLOT(rowsRemoved(QModelIndex,int,int)));
248
249     connect(d->model, SIGNAL(modelAboutToBeReset()), SLOT(_q_modelAboutToBeReset()));
250
251     if (d->sortingEnabled)
252         d->_q_sortIndicatorChanged(header()->sortIndicatorSection(), header()->sortIndicatorOrder());
253 }
254
255 /*!
256   \reimp
257 */
258 void QTreeView::setRootIndex(const QModelIndex &index)
259 {
260     Q_D(QTreeView);
261     d->header->setRootIndex(index);
262     QAbstractItemView::setRootIndex(index);
263 }
264
265 /*!
266   \reimp
267 */
268 void QTreeView::setSelectionModel(QItemSelectionModel *selectionModel)
269 {
270     Q_D(QTreeView);
271     Q_ASSERT(selectionModel);
272     if (d->selectionModel) {
273         // support row editing
274         disconnect(d->selectionModel, SIGNAL(currentRowChanged(QModelIndex,QModelIndex)),
275                    d->model, SLOT(submit()));
276     }
277
278     d->header->setSelectionModel(selectionModel);
279     QAbstractItemView::setSelectionModel(selectionModel);
280
281     if (d->selectionModel) {
282         // support row editing
283         connect(d->selectionModel, SIGNAL(currentRowChanged(QModelIndex,QModelIndex)),
284                 d->model, SLOT(submit()));
285     }
286 }
287
288 /*!
289   Returns the header for the tree view.
290
291   \sa QAbstractItemModel::headerData()
292 */
293 QHeaderView *QTreeView::header() const
294 {
295     Q_D(const QTreeView);
296     return d->header;
297 }
298
299 /*!
300     Sets the header for the tree view, to the given \a header.
301
302     The view takes ownership over the given \a header and deletes it
303     when a new header is set.
304
305     \sa QAbstractItemModel::headerData()
306 */
307 void QTreeView::setHeader(QHeaderView *header)
308 {
309     Q_D(QTreeView);
310     if (header == d->header || !header)
311         return;
312     if (d->header && d->header->parent() == this)
313         delete d->header;
314     d->header = header;
315     d->header->setParent(this);
316
317     if (!d->header->model()) {
318         d->header->setModel(d->model);
319         if (d->selectionModel)
320             d->header->setSelectionModel(d->selectionModel);
321     }
322
323     connect(d->header, SIGNAL(sectionResized(int,int,int)),
324             this, SLOT(columnResized(int,int,int)));
325     connect(d->header, SIGNAL(sectionMoved(int,int,int)),
326             this, SLOT(columnMoved()));
327     connect(d->header, SIGNAL(sectionCountChanged(int,int)),
328             this, SLOT(columnCountChanged(int,int)));
329     connect(d->header, SIGNAL(sectionHandleDoubleClicked(int)),
330             this, SLOT(resizeColumnToContents(int)));
331     connect(d->header, SIGNAL(geometriesChanged()),
332             this, SLOT(updateGeometries()));
333
334     setSortingEnabled(d->sortingEnabled);
335 }
336
337 /*!
338   \property QTreeView::autoExpandDelay
339   \brief The delay time before items in a tree are opened during a drag and drop operation.
340   \since 4.3
341
342   This property holds the amount of time in milliseconds that the user must wait over
343   a node before that node will automatically open or close.  If the time is
344   set to less then 0 then it will not be activated.
345
346   By default, this property has a value of -1, meaning that auto-expansion is disabled.
347 */
348 int QTreeView::autoExpandDelay() const
349 {
350     Q_D(const QTreeView);
351     return d->autoExpandDelay;
352 }
353
354 void QTreeView::setAutoExpandDelay(int delay)
355 {
356     Q_D(QTreeView);
357     d->autoExpandDelay = delay;
358 }
359
360 /*!
361   \property QTreeView::indentation
362   \brief indentation of the items in the tree view.
363
364   This property holds the indentation measured in pixels of the items for each
365   level in the tree view. For top-level items, the indentation specifies the
366   horizontal distance from the viewport edge to the items in the first column;
367   for child items, it specifies their indentation from their parent items.
368
369   By default, this property has a value of 20.
370 */
371 int QTreeView::indentation() const
372 {
373     Q_D(const QTreeView);
374     return d->indent;
375 }
376
377 void QTreeView::setIndentation(int i)
378 {
379     Q_D(QTreeView);
380     if (i != d->indent) {
381         d->indent = i;
382         d->viewport->update();
383     }
384 }
385
386 /*!
387   \property QTreeView::rootIsDecorated
388   \brief whether to show controls for expanding and collapsing top-level items
389
390   Items with children are typically shown with controls to expand and collapse
391   them, allowing their children to be shown or hidden. If this property is
392   false, these controls are not shown for top-level items. This can be used to
393   make a single level tree structure appear like a simple list of items.
394
395   By default, this property is true.
396 */
397 bool QTreeView::rootIsDecorated() const
398 {
399     Q_D(const QTreeView);
400     return d->rootDecoration;
401 }
402
403 void QTreeView::setRootIsDecorated(bool show)
404 {
405     Q_D(QTreeView);
406     if (show != d->rootDecoration) {
407         d->rootDecoration = show;
408         d->viewport->update();
409     }
410 }
411
412 /*!
413   \property QTreeView::uniformRowHeights
414   \brief whether all items in the treeview have the same height
415
416   This property should only be set to true if it is guaranteed that all items
417   in the view has the same height. This enables the view to do some
418   optimizations.
419
420   The height is obtained from the first item in the view.  It is updated
421   when the data changes on that item.
422
423   By default, this property is false.
424 */
425 bool QTreeView::uniformRowHeights() const
426 {
427     Q_D(const QTreeView);
428     return d->uniformRowHeights;
429 }
430
431 void QTreeView::setUniformRowHeights(bool uniform)
432 {
433     Q_D(QTreeView);
434     d->uniformRowHeights = uniform;
435 }
436
437 /*!
438   \property QTreeView::itemsExpandable
439   \brief whether the items are expandable by the user.
440
441   This property holds whether the user can expand and collapse items
442   interactively.
443
444   By default, this property is true.
445
446 */
447 bool QTreeView::itemsExpandable() const
448 {
449     Q_D(const QTreeView);
450     return d->itemsExpandable;
451 }
452
453 void QTreeView::setItemsExpandable(bool enable)
454 {
455     Q_D(QTreeView);
456     d->itemsExpandable = enable;
457 }
458
459 /*!
460   \property QTreeView::expandsOnDoubleClick
461   \since 4.4
462   \brief whether the items can be expanded by double-clicking.
463
464   This property holds whether the user can expand and collapse items
465   by double-clicking. The default value is true.
466
467   \sa itemsExpandable
468 */
469 bool QTreeView::expandsOnDoubleClick() const
470 {
471     Q_D(const QTreeView);
472     return d->expandsOnDoubleClick;
473 }
474
475 void QTreeView::setExpandsOnDoubleClick(bool enable)
476 {
477     Q_D(QTreeView);
478     d->expandsOnDoubleClick = enable;
479 }
480
481 /*!
482   Returns the horizontal position of the \a column in the viewport.
483 */
484 int QTreeView::columnViewportPosition(int column) const
485 {
486     Q_D(const QTreeView);
487     return d->header->sectionViewportPosition(column);
488 }
489
490 /*!
491   Returns the width of the \a column.
492
493   \sa resizeColumnToContents(), setColumnWidth()
494 */
495 int QTreeView::columnWidth(int column) const
496 {
497     Q_D(const QTreeView);
498     return d->header->sectionSize(column);
499 }
500
501 /*!
502   \since 4.2
503
504   Sets the width of the given \a column to the \a width specified.
505
506   \sa columnWidth(), resizeColumnToContents()
507 */
508 void QTreeView::setColumnWidth(int column, int width)
509 {
510     Q_D(QTreeView);
511     d->header->resizeSection(column, width);
512 }
513
514 /*!
515   Returns the column in the tree view whose header covers the \a x
516   coordinate given.
517 */
518 int QTreeView::columnAt(int x) const
519 {
520     Q_D(const QTreeView);
521     return d->header->logicalIndexAt(x);
522 }
523
524 /*!
525     Returns true if the \a column is hidden; otherwise returns false.
526
527     \sa hideColumn(), isRowHidden()
528 */
529 bool QTreeView::isColumnHidden(int column) const
530 {
531     Q_D(const QTreeView);
532     return d->header->isSectionHidden(column);
533 }
534
535 /*!
536   If \a hide is true the \a column is hidden, otherwise the \a column is shown.
537
538   \sa hideColumn(), setRowHidden()
539 */
540 void QTreeView::setColumnHidden(int column, bool hide)
541 {
542     Q_D(QTreeView);
543     if (column < 0 || column >= d->header->count())
544         return;
545     d->header->setSectionHidden(column, hide);
546 }
547
548 /*!
549   \property QTreeView::headerHidden
550   \brief whether the header is shown or not.
551   \since 4.4
552
553   If this property is true, the header is not shown otherwise it is.
554   The default value is false.
555
556   \sa header()
557 */
558 bool QTreeView::isHeaderHidden() const
559 {
560     Q_D(const QTreeView);
561     return d->header->isHidden();
562 }
563
564 void QTreeView::setHeaderHidden(bool hide)
565 {
566     Q_D(QTreeView);
567     d->header->setHidden(hide);
568 }
569
570 /*!
571     Returns true if the item in the given \a row of the \a parent is hidden;
572     otherwise returns false.
573
574     \sa setRowHidden(), isColumnHidden()
575 */
576 bool QTreeView::isRowHidden(int row, const QModelIndex &parent) const
577 {
578     Q_D(const QTreeView);
579     if (!d->model)
580         return false;
581     return d->isRowHidden(d->model->index(row, 0, parent));
582 }
583
584 /*!
585   If \a hide is true the \a row with the given \a parent is hidden, otherwise the \a row is shown.
586
587   \sa isRowHidden(), setColumnHidden()
588 */
589 void QTreeView::setRowHidden(int row, const QModelIndex &parent, bool hide)
590 {
591     Q_D(QTreeView);
592     if (!d->model)
593         return;
594     QModelIndex index = d->model->index(row, 0, parent);
595     if (!index.isValid())
596         return;
597
598     if (hide) {
599         d->hiddenIndexes.insert(index);
600     } else if(d->isPersistent(index)) { //if the index is not persistent, it cannot be in the set
601         d->hiddenIndexes.remove(index);
602     }
603
604     d->doDelayedItemsLayout();
605 }
606
607 /*!
608   \since 4.3
609
610   Returns true if the item in first column in the given \a row
611   of the \a parent is spanning all the columns; otherwise returns false.
612
613   \sa setFirstColumnSpanned()
614 */
615 bool QTreeView::isFirstColumnSpanned(int row, const QModelIndex &parent) const
616 {
617     Q_D(const QTreeView);
618     if (d->spanningIndexes.isEmpty() || !d->model)
619         return false;
620     QModelIndex index = d->model->index(row, 0, parent);
621     for (int i = 0; i < d->spanningIndexes.count(); ++i)
622         if (d->spanningIndexes.at(i) == index)
623             return true;
624     return false;
625 }
626
627 /*!
628   \since 4.3
629
630   If \a span is true the item in the first column in the \a row
631   with the given \a parent is set to span all columns, otherwise all items
632   on the \a row are shown.
633
634   \sa isFirstColumnSpanned()
635 */
636 void QTreeView::setFirstColumnSpanned(int row, const QModelIndex &parent, bool span)
637 {
638     Q_D(QTreeView);
639     if (!d->model)
640         return;
641     QModelIndex index = d->model->index(row, 0, parent);
642     if (!index.isValid())
643         return;
644
645     if (span) {
646         QPersistentModelIndex persistent(index);
647         if (!d->spanningIndexes.contains(persistent))
648             d->spanningIndexes.append(persistent);
649     } else {
650         QPersistentModelIndex persistent(index);
651         int i = d->spanningIndexes.indexOf(persistent);
652         if (i >= 0)
653             d->spanningIndexes.remove(i);
654     }
655
656     d->executePostedLayout();
657     int i = d->viewIndex(index);
658     if (i >= 0)
659         d->viewItems[i].spanning = span;
660
661     d->viewport->update();
662 }
663
664 /*!
665   \reimp
666 */
667 void QTreeView::dataChanged(const QModelIndex &topLeft, const QModelIndex &bottomRight)
668 {
669     Q_D(QTreeView);
670
671     // if we are going to do a complete relayout anyway, there is no need to update
672     if (d->delayedPendingLayout)
673         return;
674
675     // refresh the height cache here; we don't really lose anything by getting the size hint,
676     // since QAbstractItemView::dataChanged() will get the visualRect for the items anyway
677
678     bool sizeChanged = false;
679     int topViewIndex = d->viewIndex(topLeft);
680     if (topViewIndex == 0) {
681         int newDefaultItemHeight = indexRowSizeHint(topLeft);
682         sizeChanged = d->defaultItemHeight != newDefaultItemHeight;
683         d->defaultItemHeight = newDefaultItemHeight;
684     }
685
686     if (topViewIndex != -1) {
687         if (topLeft.row() == bottomRight.row()) {
688             int oldHeight = d->itemHeight(topViewIndex);
689             d->invalidateHeightCache(topViewIndex);
690             sizeChanged |= (oldHeight != d->itemHeight(topViewIndex));
691             if (topLeft.column() == 0)
692                 d->viewItems[topViewIndex].hasChildren = d->hasVisibleChildren(topLeft);
693         } else {
694             int bottomViewIndex = d->viewIndex(bottomRight);
695             for (int i = topViewIndex; i <= bottomViewIndex; ++i) {
696                 int oldHeight = d->itemHeight(i);
697                 d->invalidateHeightCache(i);
698                 sizeChanged |= (oldHeight != d->itemHeight(i));
699                 if (topLeft.column() == 0)
700                     d->viewItems[i].hasChildren = d->hasVisibleChildren(d->viewItems.at(i).index);
701             }
702         }
703     }
704
705     if (sizeChanged) {
706         d->updateScrollBars();
707         d->viewport->update();
708     }
709     QAbstractItemView::dataChanged(topLeft, bottomRight);
710 }
711
712 /*!
713   Hides the \a column given.
714
715   \note This function should only be called after the model has been
716   initialized, as the view needs to know the number of columns in order to
717   hide \a column.
718
719   \sa showColumn(), setColumnHidden()
720 */
721 void QTreeView::hideColumn(int column)
722 {
723     Q_D(QTreeView);
724     d->header->hideSection(column);
725 }
726
727 /*!
728   Shows the given \a column in the tree view.
729
730   \sa hideColumn(), setColumnHidden()
731 */
732 void QTreeView::showColumn(int column)
733 {
734     Q_D(QTreeView);
735     d->header->showSection(column);
736 }
737
738 /*!
739   \fn void QTreeView::expand(const QModelIndex &index)
740
741   Expands the model item specified by the \a index.
742
743   \sa expanded()
744 */
745 void QTreeView::expand(const QModelIndex &index)
746 {
747     Q_D(QTreeView);
748     if (!d->isIndexValid(index))
749         return;
750     if (d->delayedPendingLayout) {
751         //A complete relayout is going to be performed, just store the expanded index, no need to layout.
752         if (d->storeExpanded(index))
753             emit expanded(index);
754         return;
755     }
756
757     int i = d->viewIndex(index);
758     if (i != -1) { // is visible
759         d->expand(i, true);
760         if (!d->isAnimating()) {
761             updateGeometries();
762             d->viewport->update();
763         }
764     } else if (d->storeExpanded(index)) {
765         emit expanded(index);
766     }
767 }
768
769 /*!
770   \fn void QTreeView::collapse(const QModelIndex &index)
771
772   Collapses the model item specified by the \a index.
773
774   \sa collapsed()
775 */
776 void QTreeView::collapse(const QModelIndex &index)
777 {
778     Q_D(QTreeView);
779     if (!d->isIndexValid(index))
780         return;
781     //if the current item is now invisible, the autoscroll will expand the tree to see it, so disable the autoscroll
782     d->delayedAutoScroll.stop();
783
784     if (d->delayedPendingLayout) {
785         //A complete relayout is going to be performed, just un-store the expanded index, no need to layout.
786         if (d->isPersistent(index) && d->expandedIndexes.remove(index))
787             emit collapsed(index);
788         return;
789     }
790     int i = d->viewIndex(index);
791     if (i != -1) { // is visible
792         d->collapse(i, true);
793         if (!d->isAnimating()) {
794             updateGeometries();
795             viewport()->update();
796         }
797     } else {
798         if (d->isPersistent(index) && d->expandedIndexes.remove(index))
799             emit collapsed(index);
800     }
801 }
802
803 /*!
804   \fn bool QTreeView::isExpanded(const QModelIndex &index) const
805
806   Returns true if the model item \a index is expanded; otherwise returns
807   false.
808
809   \sa expand(), expanded(), setExpanded()
810 */
811 bool QTreeView::isExpanded(const QModelIndex &index) const
812 {
813     Q_D(const QTreeView);
814     return d->isIndexExpanded(index);
815 }
816
817 /*!
818   Sets the item referred to by \a index to either collapse or expanded,
819   depending on the value of \a expanded.
820
821   \sa expanded(), expand(), isExpanded()
822 */
823 void QTreeView::setExpanded(const QModelIndex &index, bool expanded)
824 {
825     if (expanded)
826         this->expand(index);
827     else
828         this->collapse(index);
829 }
830
831 /*!
832     \since 4.2
833     \property QTreeView::sortingEnabled
834     \brief whether sorting is enabled
835
836     If this property is true, sorting is enabled for the tree; if the property
837     is false, sorting is not enabled. The default value is false.
838
839     \note In order to avoid performance issues, it is recommended that
840     sorting is enabled \e after inserting the items into the tree.
841     Alternatively, you could also insert the items into a list before inserting
842     the items into the tree.
843
844     \sa sortByColumn()
845 */
846
847 void QTreeView::setSortingEnabled(bool enable)
848 {
849     Q_D(QTreeView);
850     header()->setSortIndicatorShown(enable);
851     header()->setClickable(enable);
852     if (enable) {
853         //sortByColumn has to be called before we connect or set the sortingEnabled flag
854         // because otherwise it will not call sort on the model.
855         sortByColumn(header()->sortIndicatorSection(), header()->sortIndicatorOrder());
856         connect(header(), SIGNAL(sortIndicatorChanged(int,Qt::SortOrder)),
857                 this, SLOT(_q_sortIndicatorChanged(int,Qt::SortOrder)), Qt::UniqueConnection);
858     } else {
859         disconnect(header(), SIGNAL(sortIndicatorChanged(int,Qt::SortOrder)),
860                    this, SLOT(_q_sortIndicatorChanged(int,Qt::SortOrder)));
861     }
862     d->sortingEnabled = enable;
863 }
864
865 bool QTreeView::isSortingEnabled() const
866 {
867     Q_D(const QTreeView);
868     return d->sortingEnabled;
869 }
870
871 /*!
872     \since 4.2
873     \property QTreeView::animated
874     \brief whether animations are enabled
875
876     If this property is true the treeview will animate expandsion
877     and collasping of branches. If this property is false, the treeview
878     will expand or collapse branches immediately without showing
879     the animation.
880
881     By default, this property is false.
882 */
883
884 void QTreeView::setAnimated(bool animate)
885 {
886     Q_D(QTreeView);
887     d->animationsEnabled = animate;
888 }
889
890 bool QTreeView::isAnimated() const
891 {
892     Q_D(const QTreeView);
893     return d->animationsEnabled;
894 }
895
896 /*!
897     \since 4.2
898     \property QTreeView::allColumnsShowFocus
899     \brief whether items should show keyboard focus using all columns
900
901     If this property is true all columns will show focus, otherwise only
902     one column will show focus.
903
904     The default is false.
905 */
906
907 void QTreeView::setAllColumnsShowFocus(bool enable)
908 {
909     Q_D(QTreeView);
910     if (d->allColumnsShowFocus == enable)
911         return;
912     d->allColumnsShowFocus = enable;
913     d->viewport->update();
914 }
915
916 bool QTreeView::allColumnsShowFocus() const
917 {
918     Q_D(const QTreeView);
919     return d->allColumnsShowFocus;
920 }
921
922 /*!
923     \property QTreeView::wordWrap
924     \brief the item text word-wrapping policy
925     \since 4.3
926
927     If this property is true then the item text is wrapped where
928     necessary at word-breaks; otherwise it is not wrapped at all.
929     This property is false by default.
930
931     Note that even if wrapping is enabled, the cell will not be
932     expanded to fit all text. Ellipsis will be inserted according to
933     the current \l{QAbstractItemView::}{textElideMode}.
934 */
935 void QTreeView::setWordWrap(bool on)
936 {
937     Q_D(QTreeView);
938     if (d->wrapItemText == on)
939         return;
940     d->wrapItemText = on;
941     d->doDelayedItemsLayout();
942 }
943
944 bool QTreeView::wordWrap() const
945 {
946     Q_D(const QTreeView);
947     return d->wrapItemText;
948 }
949
950
951 /*!
952   \reimp
953  */
954 void QTreeView::keyboardSearch(const QString &search)
955 {
956     Q_D(QTreeView);
957     if (!d->model->rowCount(d->root) || !d->model->columnCount(d->root))
958         return;
959
960     QModelIndex start;
961     if (currentIndex().isValid())
962         start = currentIndex();
963     else
964         start = d->model->index(0, 0, d->root);
965
966     bool skipRow = false;
967     bool keyboardTimeWasValid = d->keyboardInputTime.isValid();
968     qint64 keyboardInputTimeElapsed = d->keyboardInputTime.restart();
969     if (search.isEmpty() || !keyboardTimeWasValid
970         || keyboardInputTimeElapsed > QApplication::keyboardInputInterval()) {
971         d->keyboardInput = search;
972         skipRow = currentIndex().isValid(); //if it is not valid we should really start at QModelIndex(0,0)
973     } else {
974         d->keyboardInput += search;
975     }
976
977     // special case for searches with same key like 'aaaaa'
978     bool sameKey = false;
979     if (d->keyboardInput.length() > 1) {
980         int c = d->keyboardInput.count(d->keyboardInput.at(d->keyboardInput.length() - 1));
981         sameKey = (c == d->keyboardInput.length());
982         if (sameKey)
983             skipRow = true;
984     }
985
986     // skip if we are searching for the same key or a new search started
987     if (skipRow) {
988         if (indexBelow(start).isValid())
989             start = indexBelow(start);
990         else
991             start = d->model->index(0, start.column(), d->root);
992     }
993
994     d->executePostedLayout();
995     int startIndex = d->viewIndex(start);
996     if (startIndex <= -1)
997         return;
998
999     int previousLevel = -1;
1000     int bestAbove = -1;
1001     int bestBelow = -1;
1002     QString searchString = sameKey ? QString(d->keyboardInput.at(0)) : d->keyboardInput;
1003     for (int i = 0; i < d->viewItems.count(); ++i) {
1004         if ((int)d->viewItems.at(i).level > previousLevel) {
1005             QModelIndex searchFrom = d->viewItems.at(i).index;
1006             if (searchFrom.parent() == start.parent())
1007                 searchFrom = start;
1008             QModelIndexList match = d->model->match(searchFrom, Qt::DisplayRole, searchString);
1009             if (match.count()) {
1010                 int hitIndex = d->viewIndex(match.at(0));
1011                 if (hitIndex >= 0 && hitIndex < startIndex)
1012                     bestAbove = bestAbove == -1 ? hitIndex : qMin(hitIndex, bestAbove);
1013                 else if (hitIndex >= startIndex)
1014                     bestBelow = bestBelow == -1 ? hitIndex : qMin(hitIndex, bestBelow);
1015             }
1016         }
1017         previousLevel = d->viewItems.at(i).level;
1018     }
1019
1020     QModelIndex index;
1021     if (bestBelow > -1)
1022         index = d->viewItems.at(bestBelow).index;
1023     else if (bestAbove > -1)
1024         index = d->viewItems.at(bestAbove).index;
1025
1026     if (index.isValid()) {
1027         QItemSelectionModel::SelectionFlags flags = (d->selectionMode == SingleSelection
1028                                                      ? QItemSelectionModel::SelectionFlags(
1029                                                          QItemSelectionModel::ClearAndSelect
1030                                                          |d->selectionBehaviorFlags())
1031                                                      : QItemSelectionModel::SelectionFlags(
1032                                                          QItemSelectionModel::NoUpdate));
1033         selectionModel()->setCurrentIndex(index, flags);
1034     }
1035 }
1036
1037 /*!
1038   Returns the rectangle on the viewport occupied by the item at \a index.
1039   If the index is not visible or explicitly hidden, the returned rectangle is invalid.
1040 */
1041 QRect QTreeView::visualRect(const QModelIndex &index) const
1042 {
1043     Q_D(const QTreeView);
1044
1045     if (!d->isIndexValid(index) || isIndexHidden(index))
1046         return QRect();
1047
1048     d->executePostedLayout();
1049
1050     int vi = d->viewIndex(index);
1051     if (vi < 0)
1052         return QRect();
1053
1054     bool spanning = d->viewItems.at(vi).spanning;
1055
1056     // if we have a spanning item, make the selection stretch from left to right
1057     int x = (spanning ? 0 : columnViewportPosition(index.column()));
1058     int w = (spanning ? d->header->length() : columnWidth(index.column()));
1059     // handle indentation
1060     if (index.column() == 0) {
1061         int i = d->indentationForItem(vi);
1062         w -= i;
1063         if (!isRightToLeft())
1064             x += i;
1065     }
1066
1067     int y = d->coordinateForItem(vi);
1068     int h = d->itemHeight(vi);
1069
1070     return QRect(x, y, w, h);
1071 }
1072
1073 /*!
1074     Scroll the contents of the tree view until the given model item
1075     \a index is visible. The \a hint parameter specifies more
1076     precisely where the item should be located after the
1077     operation.
1078     If any of the parents of the model item are collapsed, they will
1079     be expanded to ensure that the model item is visible.
1080 */
1081 void QTreeView::scrollTo(const QModelIndex &index, ScrollHint hint)
1082 {
1083     Q_D(QTreeView);
1084
1085     if (!d->isIndexValid(index))
1086         return;
1087
1088     d->executePostedLayout();
1089     d->updateScrollBars();
1090
1091     // Expand all parents if the parent(s) of the node are not expanded.
1092     QModelIndex parent = index.parent();
1093     while (parent.isValid() && state() == NoState && d->itemsExpandable) {
1094         if (!isExpanded(parent))
1095             expand(parent);
1096         parent = d->model->parent(parent);
1097     }
1098
1099     int item = d->viewIndex(index);
1100     if (item < 0)
1101         return;
1102
1103     QRect area = d->viewport->rect();
1104
1105     // vertical
1106     if (verticalScrollMode() == QAbstractItemView::ScrollPerItem) {
1107         int top = verticalScrollBar()->value();
1108         int bottom = top + verticalScrollBar()->pageStep();
1109         if (hint == EnsureVisible && item >= top && item < bottom) {
1110             // nothing to do
1111         } else if (hint == PositionAtTop || (hint == EnsureVisible && item < top)) {
1112             verticalScrollBar()->setValue(item);
1113         } else { // PositionAtBottom or PositionAtCenter
1114             const int currentItemHeight = d->itemHeight(item);
1115             int y = (hint == PositionAtCenter
1116                  //we center on the current item with a preference to the top item (ie. -1)
1117                      ? area.height() / 2 + currentItemHeight - 1
1118                  //otherwise we simply take the whole space
1119                      : area.height());
1120             if (y > currentItemHeight) {
1121                 while (item >= 0) {
1122                     y -= d->itemHeight(item);
1123                     if (y < 0) { //there is no more space left
1124                         item++;
1125                         break;
1126                     }
1127                     item--;
1128                 }
1129             }
1130             verticalScrollBar()->setValue(item);
1131         }
1132     } else { // ScrollPerPixel
1133         QRect rect(columnViewportPosition(index.column()),
1134                    d->coordinateForItem(item), // ### slow for items outside the view
1135                    columnWidth(index.column()),
1136                    d->itemHeight(item));
1137
1138         if (rect.isEmpty()) {
1139             // nothing to do
1140         } else if (hint == EnsureVisible && area.contains(rect)) {
1141             d->viewport->update(rect);
1142             // nothing to do
1143         } else {
1144             bool above = (hint == EnsureVisible
1145                         && (rect.top() < area.top()
1146                             || area.height() < rect.height()));
1147             bool below = (hint == EnsureVisible
1148                         && rect.bottom() > area.bottom()
1149                         && rect.height() < area.height());
1150
1151             int verticalValue = verticalScrollBar()->value();
1152             if (hint == PositionAtTop || above)
1153                 verticalValue += rect.top();
1154             else if (hint == PositionAtBottom || below)
1155                 verticalValue += rect.bottom() - area.height();
1156             else if (hint == PositionAtCenter)
1157                 verticalValue += rect.top() - ((area.height() - rect.height()) / 2);
1158             verticalScrollBar()->setValue(verticalValue);
1159         }
1160     }
1161     // horizontal
1162     int viewportWidth = d->viewport->width();
1163     int horizontalOffset = d->header->offset();
1164     int horizontalPosition = d->header->sectionPosition(index.column());
1165     int cellWidth = d->header->sectionSize(index.column());
1166
1167     if (hint == PositionAtCenter) {
1168         horizontalScrollBar()->setValue(horizontalPosition - ((viewportWidth - cellWidth) / 2));
1169     } else {
1170         if (horizontalPosition - horizontalOffset < 0 || cellWidth > viewportWidth)
1171             horizontalScrollBar()->setValue(horizontalPosition);
1172         else if (horizontalPosition - horizontalOffset + cellWidth > viewportWidth)
1173             horizontalScrollBar()->setValue(horizontalPosition - viewportWidth + cellWidth);
1174     }
1175 }
1176
1177 /*!
1178   \reimp
1179 */
1180 void QTreeView::timerEvent(QTimerEvent *event)
1181 {
1182     Q_D(QTreeView);
1183     if (event->timerId() == d->columnResizeTimerID) {
1184         updateGeometries();
1185         killTimer(d->columnResizeTimerID);
1186         d->columnResizeTimerID = 0;
1187         QRect rect;
1188         int viewportHeight = d->viewport->height();
1189         int viewportWidth = d->viewport->width();
1190         for (int i = d->columnsToUpdate.size() - 1; i >= 0; --i) {
1191             int column = d->columnsToUpdate.at(i);
1192             int x = columnViewportPosition(column);
1193             if (isRightToLeft())
1194                 rect |= QRect(0, 0, x + columnWidth(column), viewportHeight);
1195             else
1196                 rect |= QRect(x, 0, viewportWidth - x, viewportHeight);
1197         }
1198         d->viewport->update(rect.normalized());
1199         d->columnsToUpdate.clear();
1200     } else if (event->timerId() == d->openTimer.timerId()) {
1201         QPoint pos = d->viewport->mapFromGlobal(QCursor::pos());
1202         if (state() == QAbstractItemView::DraggingState
1203             && d->viewport->rect().contains(pos)) {
1204             QModelIndex index = indexAt(pos);
1205             setExpanded(index, !isExpanded(index));
1206         }
1207         d->openTimer.stop();
1208     }
1209
1210     QAbstractItemView::timerEvent(event);
1211 }
1212
1213 /*!
1214   \reimp
1215 */
1216 #ifndef QT_NO_DRAGANDDROP
1217 void QTreeView::dragMoveEvent(QDragMoveEvent *event)
1218 {
1219     Q_D(QTreeView);
1220     if (d->autoExpandDelay >= 0)
1221         d->openTimer.start(d->autoExpandDelay, this);
1222     QAbstractItemView::dragMoveEvent(event);
1223 }
1224 #endif
1225
1226 /*!
1227   \reimp
1228 */
1229 bool QTreeView::viewportEvent(QEvent *event)
1230 {
1231     Q_D(QTreeView);
1232     switch (event->type()) {
1233     case QEvent::HoverEnter:
1234     case QEvent::HoverLeave:
1235     case QEvent::HoverMove: {
1236         QHoverEvent *he = static_cast<QHoverEvent*>(event);
1237         int oldBranch = d->hoverBranch;
1238         d->hoverBranch = d->itemDecorationAt(he->pos());
1239         if (oldBranch != d->hoverBranch) {
1240             //we need to paint the whole items (including the decoration) so that when the user
1241             //moves the mouse over those elements they are updated
1242             if (oldBranch >= 0) {
1243                 int y = d->coordinateForItem(oldBranch);
1244                 int h = d->itemHeight(oldBranch);
1245                 viewport()->update(QRect(0, y, viewport()->width(), h));
1246             }
1247             if (d->hoverBranch >= 0) {
1248                 int y = d->coordinateForItem(d->hoverBranch);
1249                 int h = d->itemHeight(d->hoverBranch);
1250                 viewport()->update(QRect(0, y, viewport()->width(), h));
1251             }
1252         }
1253         break; }
1254     default:
1255         break;
1256     }
1257     return QAbstractItemView::viewportEvent(event);
1258 }
1259
1260 /*!
1261   \reimp
1262 */
1263 void QTreeView::paintEvent(QPaintEvent *event)
1264 {
1265     Q_D(QTreeView);
1266     d->executePostedLayout();
1267     QPainter painter(viewport());
1268 #ifndef QT_NO_ANIMATION
1269     if (d->isAnimating()) {
1270         drawTree(&painter, event->region() - d->animatedOperation.rect());
1271         d->drawAnimatedOperation(&painter);
1272     } else
1273 #endif //QT_NO_ANIMATION
1274     {
1275         drawTree(&painter, event->region());
1276 #ifndef QT_NO_DRAGANDDROP
1277         d->paintDropIndicator(&painter);
1278 #endif
1279     }
1280 }
1281
1282 void QTreeViewPrivate::paintAlternatingRowColors(QPainter *painter, QStyleOptionViewItemV4 *option, int y, int bottom) const
1283 {
1284     Q_Q(const QTreeView);
1285     if (!alternatingColors || !q->style()->styleHint(QStyle::SH_ItemView_PaintAlternatingRowColorsForEmptyArea, option, q))
1286         return;
1287     int rowHeight = defaultItemHeight;
1288     if (rowHeight <= 0) {
1289         rowHeight = itemDelegate->sizeHint(*option, QModelIndex()).height();
1290         if (rowHeight <= 0)
1291             return;
1292     }
1293     while (y <= bottom) {
1294         option->rect.setRect(0, y, viewport->width(), rowHeight);
1295         if (current & 1) {
1296             option->features |= QStyleOptionViewItemV2::Alternate;
1297         } else {
1298             option->features &= ~QStyleOptionViewItemV2::Alternate;
1299         }
1300         ++current;
1301         q->style()->drawPrimitive(QStyle::PE_PanelItemViewRow, option, painter, q);
1302         y += rowHeight;
1303     }
1304 }
1305
1306 bool QTreeViewPrivate::expandOrCollapseItemAtPos(const QPoint &pos)
1307 {
1308     Q_Q(QTreeView);
1309     // we want to handle mousePress in EditingState (persistent editors)
1310     if ((state != QAbstractItemView::NoState
1311                 && state != QAbstractItemView::EditingState)
1312                 || !viewport->rect().contains(pos))
1313         return true;
1314
1315     int i = itemDecorationAt(pos);
1316     if ((i != -1) && itemsExpandable && hasVisibleChildren(viewItems.at(i).index)) {
1317         if (viewItems.at(i).expanded)
1318             collapse(i, true);
1319         else
1320             expand(i, true);
1321         if (!isAnimating()) {
1322             q->updateGeometries();
1323             viewport->update();
1324         }
1325         return true;
1326     }
1327     return false;
1328 }
1329
1330 void QTreeViewPrivate::_q_modelDestroyed()
1331 {
1332     //we need to clear that list because it contais QModelIndex to 
1333     //the model currently being destroyed
1334     viewItems.clear();
1335     QAbstractItemViewPrivate::_q_modelDestroyed();
1336 }
1337
1338 /*!
1339   \reimp
1340
1341   We have a QTreeView way of knowing what elements are on the viewport
1342 */
1343 QItemViewPaintPairs QTreeViewPrivate::draggablePaintPairs(const QModelIndexList &indexes, QRect *r) const
1344 {
1345     Q_ASSERT(r);
1346     return QAbstractItemViewPrivate::draggablePaintPairs(indexes, r);
1347     Q_Q(const QTreeView);
1348     QRect &rect = *r;
1349     const QRect viewportRect = viewport->rect();
1350     int itemOffset = 0;
1351     int row = firstVisibleItem(&itemOffset);
1352     QPair<int, int> startEnd = startAndEndColumns(viewportRect);
1353     QVector<int> columns;
1354     for (int i = startEnd.first; i <= startEnd.second; ++i) {
1355         int logical = header->logicalIndex(i);
1356         if (!header->isSectionHidden(logical))
1357             columns += logical;
1358     }
1359     QSet<QModelIndex> visibleIndexes;
1360     for (; itemOffset < viewportRect.bottom() && row < viewItems.count(); ++row) {
1361         const QModelIndex &index = viewItems.at(row).index;
1362         for (int colIndex = 0; colIndex < columns.count(); ++colIndex)
1363             visibleIndexes += index.sibling(index.row(), columns.at(colIndex));
1364         itemOffset += itemHeight(row);
1365     }
1366
1367     //now that we have the visible indexes, we can try to find those which are selected
1368     QItemViewPaintPairs ret;
1369     for (int i = 0; i < indexes.count(); ++i) {
1370         const QModelIndex &index = indexes.at(i);
1371         if (visibleIndexes.contains(index)) {
1372             const QRect current = q->visualRect(index);
1373             ret += qMakePair(current, index);
1374             rect |= current;
1375         }
1376     }
1377     rect &= viewportRect;
1378     return ret;
1379 }
1380
1381 void QTreeViewPrivate::adjustViewOptionsForIndex(QStyleOptionViewItemV4 *option, const QModelIndex &current) const
1382 {
1383     const int row = current.row();
1384     option->state = option->state | (viewItems.at(row).expanded ? QStyle::State_Open : QStyle::State_None)
1385                                   | (viewItems.at(row).hasChildren ? QStyle::State_Children : QStyle::State_None)
1386                                   | (viewItems.at(row).hasMoreSiblings ? QStyle::State_Sibling : QStyle::State_None);
1387
1388     option->showDecorationSelected = (selectionBehavior & QTreeView::SelectRows)
1389                                      || option->showDecorationSelected;
1390
1391     QVector<int> logicalIndices; // index = visual index of visible columns only. data = logical index.
1392     QVector<QStyleOptionViewItemV4::ViewItemPosition> viewItemPosList; // vector of left/middle/end for each logicalIndex, visible columns only.
1393     calcLogicalIndices(&logicalIndices, &viewItemPosList);
1394
1395     int columnIndex = 0;
1396     for (int visualIndex = 0; visualIndex < current.column(); ++visualIndex) {
1397         int logicalIndex = header->logicalIndex(visualIndex);
1398         if (!header->isSectionHidden(logicalIndex)) {
1399             ++columnIndex;
1400         }
1401     }
1402
1403     option->viewItemPosition = viewItemPosList.at(columnIndex);
1404 }
1405
1406
1407 /*!
1408   \since 4.2
1409   Draws the part of the tree intersecting the given \a region using the specified
1410   \a painter.
1411
1412   \sa paintEvent()
1413 */
1414 void QTreeView::drawTree(QPainter *painter, const QRegion &region) const
1415 {
1416     Q_D(const QTreeView);
1417     const QVector<QTreeViewItem> viewItems = d->viewItems;
1418
1419     QStyleOptionViewItemV4 option = d->viewOptionsV4();
1420     const QStyle::State state = option.state;
1421     d->current = 0;
1422
1423     if (viewItems.count() == 0 || d->header->count() == 0 || !d->itemDelegate) {
1424         d->paintAlternatingRowColors(painter, &option, 0, region.boundingRect().bottom()+1);
1425         return;
1426     }
1427
1428     int firstVisibleItemOffset = 0;
1429     const int firstVisibleItem = d->firstVisibleItem(&firstVisibleItemOffset);
1430     if (firstVisibleItem < 0) {
1431         d->paintAlternatingRowColors(painter, &option, 0, region.boundingRect().bottom()+1);
1432         return;
1433     }
1434
1435     const int viewportWidth = d->viewport->width();
1436
1437     QVector<QRect> rects = region.rects();
1438     QVector<int> drawn;
1439     bool multipleRects = (rects.size() > 1);
1440     for (int a = 0; a < rects.size(); ++a) {
1441         const QRect area = (multipleRects
1442                             ? QRect(0, rects.at(a).y(), viewportWidth, rects.at(a).height())
1443                             : rects.at(a));
1444         d->leftAndRight = d->startAndEndColumns(area);
1445
1446         int i = firstVisibleItem; // the first item at the top of the viewport
1447         int y = firstVisibleItemOffset; // we may only see part of the first item
1448
1449         // start at the top of the viewport  and iterate down to the update area
1450         for (; i < viewItems.count(); ++i) {
1451             const int itemHeight = d->itemHeight(i);
1452             if (y + itemHeight > area.top())
1453                 break;
1454             y += itemHeight;
1455         }
1456
1457         // paint the visible rows
1458         for (; i < viewItems.count() && y <= area.bottom(); ++i) {
1459             const int itemHeight = d->itemHeight(i);
1460             option.rect.setRect(0, y, viewportWidth, itemHeight);
1461             option.state = state | (viewItems.at(i).expanded ? QStyle::State_Open : QStyle::State_None)
1462                                  | (viewItems.at(i).hasChildren ? QStyle::State_Children : QStyle::State_None)
1463                                  | (viewItems.at(i).hasMoreSiblings ? QStyle::State_Sibling : QStyle::State_None);
1464             d->current = i;
1465             d->spanning = viewItems.at(i).spanning;
1466             if (!multipleRects || !drawn.contains(i)) {
1467                 drawRow(painter, option, viewItems.at(i).index);
1468                 if (multipleRects)   // even if the rect only intersects the item,
1469                     drawn.append(i); // the entire item will be painted
1470             }
1471             y += itemHeight;
1472         }
1473
1474         if (y <= area.bottom()) {
1475             d->current = i;
1476             d->paintAlternatingRowColors(painter, &option, y, area.bottom());
1477         }
1478     }
1479 }
1480
1481 /// ### move to QObject :)
1482 static inline bool ancestorOf(QObject *widget, QObject *other)
1483 {
1484     for (QObject *parent = other; parent != 0; parent = parent->parent()) {
1485         if (parent == widget)
1486             return true;
1487     }
1488     return false;
1489 }
1490
1491 void QTreeViewPrivate::calcLogicalIndices(QVector<int> *logicalIndices, QVector<QStyleOptionViewItemV4::ViewItemPosition> *itemPositions) const
1492 {
1493     const int left = (spanning ? header->visualIndex(0) : leftAndRight.first);
1494     const int right = (spanning ? header->visualIndex(0) : leftAndRight.second);
1495     const int columnCount = header->count();
1496     /* 'left' and 'right' are the left-most and right-most visible visual indices.
1497        Compute the first visible logical indices before and after the left and right.
1498        We will use these values to determine the QStyleOptionViewItemV4::viewItemPosition. */
1499     int logicalIndexBeforeLeft = -1, logicalIndexAfterRight = -1;
1500     for (int visualIndex = left - 1; visualIndex >= 0; --visualIndex) {
1501         int logicalIndex = header->logicalIndex(visualIndex);
1502         if (!header->isSectionHidden(logicalIndex)) {
1503             logicalIndexBeforeLeft = logicalIndex;
1504             break;
1505         }
1506     }
1507
1508     for (int visualIndex = left; visualIndex < columnCount; ++visualIndex) {
1509         int logicalIndex = header->logicalIndex(visualIndex);
1510         if (!header->isSectionHidden(logicalIndex)) {
1511             if (visualIndex > right) {
1512                 logicalIndexAfterRight = logicalIndex;
1513                 break;
1514             }
1515             logicalIndices->append(logicalIndex);
1516         }
1517     }
1518
1519     itemPositions->resize(logicalIndices->count());
1520     for (int currentLogicalSection = 0; currentLogicalSection < logicalIndices->count(); ++currentLogicalSection) {
1521         const int headerSection = logicalIndices->at(currentLogicalSection);
1522         // determine the viewItemPosition depending on the position of column 0
1523         int nextLogicalSection = currentLogicalSection + 1 >= logicalIndices->count()
1524                                  ? logicalIndexAfterRight
1525                                  : logicalIndices->at(currentLogicalSection + 1);
1526         int prevLogicalSection = currentLogicalSection - 1 < 0
1527                                  ? logicalIndexBeforeLeft
1528                                  : logicalIndices->at(currentLogicalSection - 1);
1529         QStyleOptionViewItemV4::ViewItemPosition pos;
1530         if (columnCount == 1 || (nextLogicalSection == 0 && prevLogicalSection == -1)
1531             || (headerSection == 0 && nextLogicalSection == -1) || spanning)
1532             pos = QStyleOptionViewItemV4::OnlyOne;
1533         else if (headerSection == 0 || (nextLogicalSection != 0 && prevLogicalSection == -1))
1534             pos = QStyleOptionViewItemV4::Beginning;
1535         else if (nextLogicalSection == 0 || nextLogicalSection == -1)
1536             pos = QStyleOptionViewItemV4::End;
1537         else
1538             pos = QStyleOptionViewItemV4::Middle;
1539         (*itemPositions)[currentLogicalSection] = pos;
1540     }
1541 }
1542
1543
1544 /*!
1545     Draws the row in the tree view that contains the model item \a index,
1546     using the \a painter given. The \a option control how the item is
1547     displayed.
1548
1549     \sa setAlternatingRowColors()
1550 */
1551 void QTreeView::drawRow(QPainter *painter, const QStyleOptionViewItem &option,
1552                         const QModelIndex &index) const
1553 {
1554     Q_D(const QTreeView);
1555     QStyleOptionViewItemV4 opt = option;
1556     const QPoint offset = d->scrollDelayOffset;
1557     const int y = option.rect.y() + offset.y();
1558     const QModelIndex parent = index.parent();
1559     const QHeaderView *header = d->header;
1560     const QModelIndex current = currentIndex();
1561     const QModelIndex hover = d->hover;
1562     const bool reverse = isRightToLeft();
1563     const QStyle::State state = opt.state;
1564     const bool spanning = d->spanning;
1565     const int left = (spanning ? header->visualIndex(0) : d->leftAndRight.first);
1566     const int right = (spanning ? header->visualIndex(0) : d->leftAndRight.second);
1567     const bool alternate = d->alternatingColors;
1568     const bool enabled = (state & QStyle::State_Enabled) != 0;
1569     const bool allColumnsShowFocus = d->allColumnsShowFocus;
1570
1571
1572     // when the row contains an index widget which has focus,
1573     // we want to paint the entire row as active
1574     bool indexWidgetHasFocus = false;
1575     if ((current.row() == index.row()) && !d->editorIndexHash.isEmpty()) {
1576         const int r = index.row();
1577         QWidget *fw = QApplication::focusWidget();
1578         for (int c = 0; c < header->count(); ++c) {
1579             QModelIndex idx = d->model->index(r, c, parent);
1580             if (QWidget *editor = indexWidget(idx)) {
1581                 if (ancestorOf(editor, fw)) {
1582                     indexWidgetHasFocus = true;
1583                     break;
1584                 }
1585             }
1586         }
1587     }
1588
1589     const bool widgetHasFocus = hasFocus();
1590     bool currentRowHasFocus = false;
1591     if (allColumnsShowFocus && widgetHasFocus && current.isValid()) {
1592         // check if the focus index is before or after the visible columns
1593         const int r = index.row();
1594         for (int c = 0; c < left && !currentRowHasFocus; ++c) {
1595             QModelIndex idx = d->model->index(r, c, parent);
1596             currentRowHasFocus = (idx == current);
1597         }
1598         QModelIndex parent = d->model->parent(index);
1599         for (int c = right; c < header->count() && !currentRowHasFocus; ++c) {
1600             currentRowHasFocus = (d->model->index(r, c, parent) == current);
1601         }
1602     }
1603
1604     // ### special case: treeviews with multiple columns draw
1605     // the selections differently than with only one column
1606     opt.showDecorationSelected = (d->selectionBehavior & SelectRows)
1607                                  || option.showDecorationSelected;
1608
1609     int width, height = option.rect.height();
1610     int position;
1611     QModelIndex modelIndex;
1612     const bool hoverRow = selectionBehavior() == QAbstractItemView::SelectRows
1613                   && index.parent() == hover.parent()
1614                   && index.row() == hover.row();
1615
1616     QVector<int> logicalIndices;
1617     QVector<QStyleOptionViewItemV4::ViewItemPosition> viewItemPosList; // vector of left/middle/end for each logicalIndex
1618     d->calcLogicalIndices(&logicalIndices, &viewItemPosList);
1619
1620     for (int currentLogicalSection = 0; currentLogicalSection < logicalIndices.count(); ++currentLogicalSection) {
1621         int headerSection = logicalIndices.at(currentLogicalSection);
1622         position = columnViewportPosition(headerSection) + offset.x();
1623         width = header->sectionSize(headerSection);
1624
1625         if (spanning) {
1626             int lastSection = header->logicalIndex(header->count() - 1);
1627             if (!reverse) {
1628                 width = columnViewportPosition(lastSection) + header->sectionSize(lastSection) - position;
1629             } else {
1630                 width += position - columnViewportPosition(lastSection);
1631                 position = columnViewportPosition(lastSection);
1632             }
1633         }
1634
1635         modelIndex = d->model->index(index.row(), headerSection, parent);
1636         if (!modelIndex.isValid())
1637             continue;
1638         opt.state = state;
1639
1640         opt.viewItemPosition = viewItemPosList.at(currentLogicalSection);
1641
1642         // fake activeness when row editor has focus
1643         if (indexWidgetHasFocus)
1644             opt.state |= QStyle::State_Active;
1645
1646         if (d->selectionModel->isSelected(modelIndex))
1647             opt.state |= QStyle::State_Selected;
1648         if (widgetHasFocus && (current == modelIndex)) {
1649             if (allColumnsShowFocus)
1650                 currentRowHasFocus = true;
1651             else
1652                 opt.state |= QStyle::State_HasFocus;
1653         }
1654         if ((hoverRow || modelIndex == hover)
1655             && (option.showDecorationSelected || (d->hoverBranch == -1)))
1656             opt.state |= QStyle::State_MouseOver;
1657         else
1658             opt.state &= ~QStyle::State_MouseOver;
1659
1660         if (enabled) {
1661             QPalette::ColorGroup cg;
1662             if ((d->model->flags(modelIndex) & Qt::ItemIsEnabled) == 0) {
1663                 opt.state &= ~QStyle::State_Enabled;
1664                 cg = QPalette::Disabled;
1665             } else if (opt.state & QStyle::State_Active) {
1666                 cg = QPalette::Active;
1667             } else {
1668                 cg = QPalette::Inactive;
1669             }
1670             opt.palette.setCurrentColorGroup(cg);
1671         }
1672
1673         if (alternate) {
1674             if (d->current & 1) {
1675                 opt.features |= QStyleOptionViewItemV2::Alternate;
1676             } else {
1677                 opt.features &= ~QStyleOptionViewItemV2::Alternate;
1678             }
1679         }
1680
1681         /* Prior to Qt 4.3, the background of the branch (in selected state and
1682            alternate row color was provided by the view. For backward compatibility,
1683            this is now delegated to the style using PE_PanelViewItemRow which
1684            does the appropriate fill */
1685         if (headerSection == 0) {
1686             const int i = d->indentationForItem(d->current);
1687             QRect branches(reverse ? position + width - i : position, y, i, height);
1688             const bool setClipRect = branches.width() > width;
1689             if (setClipRect) {
1690                 painter->save();
1691                 painter->setClipRect(QRect(position, y, width, height));
1692             }
1693             // draw background for the branch (selection + alternate row)
1694             opt.rect = branches;
1695             style()->drawPrimitive(QStyle::PE_PanelItemViewRow, &opt, painter, this);
1696
1697             // draw background of the item (only alternate row). rest of the background
1698             // is provided by the delegate
1699             QStyle::State oldState = opt.state;
1700             opt.state &= ~QStyle::State_Selected;
1701             opt.rect.setRect(reverse ? position : i + position, y, width - i, height);
1702             style()->drawPrimitive(QStyle::PE_PanelItemViewRow, &opt, painter, this);
1703             opt.state = oldState;
1704
1705             drawBranches(painter, branches, index);
1706             if (setClipRect)
1707                 painter->restore();
1708         } else {
1709             QStyle::State oldState = opt.state;
1710             opt.state &= ~QStyle::State_Selected;
1711             opt.rect.setRect(position, y, width, height);
1712             style()->drawPrimitive(QStyle::PE_PanelItemViewRow, &opt, painter, this);
1713             opt.state = oldState;
1714         }
1715
1716         d->delegateForIndex(modelIndex)->paint(painter, opt, modelIndex);
1717     }
1718
1719     if (currentRowHasFocus) {
1720         QStyleOptionFocusRect o;
1721         o.QStyleOption::operator=(option);
1722         o.state |= QStyle::State_KeyboardFocusChange;
1723         QPalette::ColorGroup cg = (option.state & QStyle::State_Enabled)
1724                                   ? QPalette::Normal : QPalette::Disabled;
1725         o.backgroundColor = option.palette.color(cg, d->selectionModel->isSelected(index)
1726                                                  ? QPalette::Highlight : QPalette::Background);
1727         int x = 0;
1728         if (!option.showDecorationSelected)
1729             x = header->sectionPosition(0) + d->indentationForItem(d->current);
1730         QRect focusRect(x - header->offset(), y, header->length() - x, height);
1731         o.rect = style()->visualRect(layoutDirection(), d->viewport->rect(), focusRect);
1732         style()->drawPrimitive(QStyle::PE_FrameFocusRect, &o, painter);
1733         // if we show focus on all columns and the first section is moved,
1734         // we have to split the focus rect into two rects
1735         if (allColumnsShowFocus && !option.showDecorationSelected
1736             && header->sectionsMoved() && (header->visualIndex(0) != 0)) {
1737             QRect sectionRect(0, y, header->sectionPosition(0), height); 
1738             o.rect = style()->visualRect(layoutDirection(), d->viewport->rect(), sectionRect);
1739             style()->drawPrimitive(QStyle::PE_FrameFocusRect, &o, painter);
1740         }
1741     }
1742 }
1743
1744 /*!
1745   Draws the branches in the tree view on the same row as the model item
1746   \a index, using the \a painter given. The branches are drawn in the
1747   rectangle specified by \a rect.
1748 */
1749 void QTreeView::drawBranches(QPainter *painter, const QRect &rect,
1750                              const QModelIndex &index) const
1751 {
1752     Q_D(const QTreeView);
1753     const bool reverse = isRightToLeft();
1754     const int indent = d->indent;
1755     const int outer = d->rootDecoration ? 0 : 1;
1756     const int item = d->current;
1757     const QTreeViewItem &viewItem = d->viewItems.at(item);
1758     int level = viewItem.level;
1759     QRect primitive(reverse ? rect.left() : rect.right() + 1, rect.top(), indent, rect.height());
1760
1761     QModelIndex parent = index.parent();
1762     QModelIndex current = parent;
1763     QModelIndex ancestor = current.parent();
1764
1765     QStyleOptionViewItemV2 opt = viewOptions();
1766     QStyle::State extraFlags = QStyle::State_None;
1767     if (isEnabled())
1768         extraFlags |= QStyle::State_Enabled;
1769     if (window()->isActiveWindow())
1770         extraFlags |= QStyle::State_Active;
1771     QPoint oldBO = painter->brushOrigin();
1772     if (verticalScrollMode() == QAbstractItemView::ScrollPerPixel)
1773         painter->setBrushOrigin(QPoint(0, verticalOffset()));
1774
1775     if (d->alternatingColors) {
1776         if (d->current & 1) {
1777             opt.features |= QStyleOptionViewItemV2::Alternate;
1778         } else {
1779             opt.features &= ~QStyleOptionViewItemV2::Alternate;
1780         }
1781     }
1782
1783     // When hovering over a row, pass State_Hover for painting the branch
1784     // indicators if it has the decoration (aka branch) selected.
1785     bool hoverRow = selectionBehavior() == QAbstractItemView::SelectRows
1786                     && opt.showDecorationSelected
1787                     && index.parent() == d->hover.parent()
1788                     && index.row() == d->hover.row();
1789
1790     if (d->selectionModel->isSelected(index))
1791         extraFlags |= QStyle::State_Selected;
1792
1793     if (level >= outer) {
1794         // start with the innermost branch
1795         primitive.moveLeft(reverse ? primitive.left() : primitive.left() - indent);
1796         opt.rect = primitive;
1797
1798         const bool expanded = viewItem.expanded;
1799         const bool children = viewItem.hasChildren;
1800         bool moreSiblings = viewItem.hasMoreSiblings;
1801
1802         opt.state = QStyle::State_Item | extraFlags
1803                     | (moreSiblings ? QStyle::State_Sibling : QStyle::State_None)
1804                     | (children ? QStyle::State_Children : QStyle::State_None)
1805                     | (expanded ? QStyle::State_Open : QStyle::State_None);
1806         if (hoverRow || item == d->hoverBranch)
1807             opt.state |= QStyle::State_MouseOver;
1808         else
1809             opt.state &= ~QStyle::State_MouseOver;
1810         style()->drawPrimitive(QStyle::PE_IndicatorBranch, &opt, painter, this);
1811     }
1812     // then go out level by level
1813     for (--level; level >= outer; --level) { // we have already drawn the innermost branch
1814         primitive.moveLeft(reverse ? primitive.left() + indent : primitive.left() - indent);
1815         opt.rect = primitive;
1816         opt.state = extraFlags;
1817         bool moreSiblings = false;
1818         if (d->hiddenIndexes.isEmpty()) {
1819             moreSiblings = (d->model->rowCount(ancestor) - 1 > current.row());
1820         } else {
1821             int successor = item + viewItem.total + 1;
1822             while (successor < d->viewItems.size()
1823                    && d->viewItems.at(successor).level >= uint(level)) {
1824                 const QTreeViewItem &successorItem = d->viewItems.at(successor);
1825                 if (successorItem.level == uint(level)) {
1826                     moreSiblings = true;
1827                     break;
1828                 }
1829                 successor += successorItem.total + 1;
1830             }
1831         }
1832         if (moreSiblings)
1833             opt.state |= QStyle::State_Sibling;
1834         if (hoverRow || item == d->hoverBranch)
1835             opt.state |= QStyle::State_MouseOver;
1836         else
1837             opt.state &= ~QStyle::State_MouseOver;
1838         style()->drawPrimitive(QStyle::PE_IndicatorBranch, &opt, painter, this);
1839         current = ancestor;
1840         ancestor = current.parent();
1841     }
1842     painter->setBrushOrigin(oldBO);
1843 }
1844
1845 /*!
1846   \reimp
1847 */
1848 void QTreeView::mousePressEvent(QMouseEvent *event)
1849 {
1850         Q_D(QTreeView);
1851     bool handled = false;
1852     if (style()->styleHint(QStyle::SH_Q3ListViewExpand_SelectMouseType, 0, this) == QEvent::MouseButtonPress)
1853         handled = d->expandOrCollapseItemAtPos(event->pos());
1854         if (!handled && d->itemDecorationAt(event->pos()) == -1)
1855         QAbstractItemView::mousePressEvent(event);
1856 }
1857
1858 /*!
1859   \reimp
1860 */
1861 void QTreeView::mouseReleaseEvent(QMouseEvent *event)
1862 {
1863     Q_D(QTreeView);
1864     if (d->itemDecorationAt(event->pos()) == -1) {
1865         QAbstractItemView::mouseReleaseEvent(event);
1866     } else {
1867         if (state() == QAbstractItemView::DragSelectingState)
1868             setState(QAbstractItemView::NoState);
1869         if (style()->styleHint(QStyle::SH_Q3ListViewExpand_SelectMouseType, 0, this) == QEvent::MouseButtonRelease)
1870             d->expandOrCollapseItemAtPos(event->pos());
1871     }
1872 }
1873
1874 /*!
1875   \reimp
1876 */
1877 void QTreeView::mouseDoubleClickEvent(QMouseEvent *event)
1878 {
1879     Q_D(QTreeView);
1880     if (state() != NoState || !d->viewport->rect().contains(event->pos()))
1881         return;
1882
1883     int i = d->itemDecorationAt(event->pos());
1884     if (i == -1) {
1885         i = d->itemAtCoordinate(event->y());
1886         if (i == -1)
1887             return; // user clicked outside the items
1888
1889         const QPersistentModelIndex firstColumnIndex = d->viewItems.at(i).index;
1890         const QPersistentModelIndex persistent = indexAt(event->pos());
1891
1892         if (d->pressedIndex != persistent) {
1893             mousePressEvent(event);
1894             return;
1895         }
1896
1897         // signal handlers may change the model
1898         emit doubleClicked(persistent);
1899
1900         if (!persistent.isValid())
1901             return;
1902
1903         if (edit(persistent, DoubleClicked, event) || state() != NoState)
1904             return; // the double click triggered editing
1905
1906         if (!style()->styleHint(QStyle::SH_ItemView_ActivateItemOnSingleClick, 0, this))
1907             emit activated(persistent);
1908
1909         d->executePostedLayout(); // we need to make sure viewItems is updated
1910         if (d->itemsExpandable
1911             && d->expandsOnDoubleClick
1912             && d->hasVisibleChildren(persistent)) {
1913             if (!((i < d->viewItems.count()) && (d->viewItems.at(i).index == firstColumnIndex))) {
1914                 // find the new index of the item
1915                 for (i = 0; i < d->viewItems.count(); ++i) {
1916                     if (d->viewItems.at(i).index == firstColumnIndex)
1917                         break;
1918                 }
1919                 if (i == d->viewItems.count())
1920                     return;
1921             }
1922             if (d->viewItems.at(i).expanded)
1923                 d->collapse(i, true);
1924             else
1925                 d->expand(i, true);
1926             updateGeometries();
1927             viewport()->update();
1928         }
1929     }
1930 }
1931
1932 /*!
1933   \reimp
1934 */
1935 void QTreeView::mouseMoveEvent(QMouseEvent *event)
1936 {
1937     Q_D(QTreeView);
1938     if (d->itemDecorationAt(event->pos()) == -1) // ### what about expanding/collapsing state ?
1939         QAbstractItemView::mouseMoveEvent(event);
1940 }
1941
1942 /*!
1943   \reimp
1944 */
1945 void QTreeView::keyPressEvent(QKeyEvent *event)
1946 {
1947     Q_D(QTreeView);
1948     QModelIndex current = currentIndex();
1949     //this is the management of the expansion
1950     if (d->isIndexValid(current) && d->model && d->itemsExpandable) {
1951         switch (event->key()) {
1952         case Qt::Key_Asterisk: {
1953             QStack<QModelIndex> parents;
1954             parents.push(current);
1955                 while (!parents.isEmpty()) {
1956                     QModelIndex parent = parents.pop();
1957                     for (int row = 0; row < d->model->rowCount(parent); ++row) {
1958                         QModelIndex child = d->model->index(row, 0, parent);
1959                         if (!d->isIndexValid(child))
1960                             break;
1961                         parents.push(child);
1962                         expand(child);
1963                     }
1964                 }
1965                 expand(current);
1966             break; }
1967         case Qt::Key_Plus:
1968             expand(current);
1969             break;
1970         case Qt::Key_Minus:
1971             collapse(current);
1972             break;
1973         }
1974     }
1975
1976     QAbstractItemView::keyPressEvent(event);
1977 }
1978
1979 /*!
1980   \reimp
1981 */
1982 QModelIndex QTreeView::indexAt(const QPoint &point) const
1983 {
1984     Q_D(const QTreeView);
1985     d->executePostedLayout();
1986
1987     int visualIndex = d->itemAtCoordinate(point.y());
1988     QModelIndex idx = d->modelIndex(visualIndex);
1989     if (!idx.isValid())
1990         return QModelIndex();
1991
1992     if (d->viewItems.at(visualIndex).spanning)
1993         return idx;
1994
1995     int column = d->columnAt(point.x());
1996     if (column == idx.column())
1997         return idx;
1998     if (column < 0)
1999         return QModelIndex();
2000     return idx.sibling(idx.row(), column);
2001 }
2002
2003 /*!
2004   Returns the model index of the item above \a index.
2005 */
2006 QModelIndex QTreeView::indexAbove(const QModelIndex &index) const
2007 {
2008     Q_D(const QTreeView);
2009     if (!d->isIndexValid(index))
2010         return QModelIndex();
2011     d->executePostedLayout();
2012     int i = d->viewIndex(index);
2013     if (--i < 0)
2014         return QModelIndex();
2015     return d->viewItems.at(i).index;
2016 }
2017
2018 /*!
2019   Returns the model index of the item below \a index.
2020 */
2021 QModelIndex QTreeView::indexBelow(const QModelIndex &index) const
2022 {
2023     Q_D(const QTreeView);
2024     if (!d->isIndexValid(index))
2025         return QModelIndex();
2026     d->executePostedLayout();
2027     int i = d->viewIndex(index);
2028     if (++i >= d->viewItems.count())
2029         return QModelIndex();
2030     return d->viewItems.at(i).index;
2031 }
2032
2033 /*!
2034     \internal
2035
2036     Lays out the items in the tree view.
2037 */
2038 void QTreeView::doItemsLayout()
2039 {
2040     Q_D(QTreeView);
2041     if (d->hasRemovedItems) {
2042         //clean the QSet that may contains old (and this invalid) indexes
2043         d->hasRemovedItems = false;
2044         QSet<QPersistentModelIndex>::iterator it = d->expandedIndexes.begin();
2045         while (it != d->expandedIndexes.constEnd()) {
2046             if (!it->isValid())
2047                 it = d->expandedIndexes.erase(it);
2048             else
2049                 ++it;
2050         }
2051         it = d->hiddenIndexes.begin();
2052         while (it != d->hiddenIndexes.constEnd()) {
2053             if (!it->isValid())
2054                 it = d->hiddenIndexes.erase(it);
2055             else
2056                 ++it;
2057         }
2058     }
2059     d->viewItems.clear(); // prepare for new layout
2060     QModelIndex parent = d->root;
2061     if (d->model->hasChildren(parent)) {
2062         d->layout(-1);
2063     }
2064     QAbstractItemView::doItemsLayout();
2065     d->header->doItemsLayout();
2066 }
2067
2068 /*!
2069   \reimp
2070 */
2071 void QTreeView::reset()
2072 {
2073     Q_D(QTreeView);
2074     d->expandedIndexes.clear();
2075     d->hiddenIndexes.clear();
2076     d->spanningIndexes.clear();
2077     d->viewItems.clear();
2078     QAbstractItemView::reset();
2079 }
2080
2081 /*!
2082   Returns the horizontal offset of the items in the treeview.
2083
2084   Note that the tree view uses the horizontal header section
2085   positions to determine the positions of columns in the view.
2086
2087   \sa verticalOffset()
2088 */
2089 int QTreeView::horizontalOffset() const
2090 {
2091     Q_D(const QTreeView);
2092     return d->header->offset();
2093 }
2094
2095 /*!
2096   Returns the vertical offset of the items in the tree view.
2097
2098   \sa horizontalOffset()
2099 */
2100 int QTreeView::verticalOffset() const
2101 {
2102     Q_D(const QTreeView);
2103     if (d->verticalScrollMode == QAbstractItemView::ScrollPerItem) {
2104         if (d->uniformRowHeights)
2105             return verticalScrollBar()->value() * d->defaultItemHeight;
2106         // If we are scrolling per item and have non-uniform row heights,
2107         // finding the vertical offset in pixels is going to be relatively slow.
2108         // ### find a faster way to do this
2109         d->executePostedLayout();
2110         int offset = 0;
2111         for (int i = 0; i < d->viewItems.count(); ++i) {
2112             if (i == verticalScrollBar()->value())
2113                 return offset;
2114             offset += d->itemHeight(i);
2115         }
2116         return 0;
2117     }
2118     // scroll per pixel
2119     return verticalScrollBar()->value();
2120 }
2121
2122 /*!
2123     Move the cursor in the way described by \a cursorAction, using the
2124     information provided by the button \a modifiers.
2125 */
2126 QModelIndex QTreeView::moveCursor(CursorAction cursorAction, Qt::KeyboardModifiers modifiers)
2127 {
2128     Q_D(QTreeView);
2129     Q_UNUSED(modifiers);
2130
2131     d->executePostedLayout();
2132
2133     QModelIndex current = currentIndex();
2134     if (!current.isValid()) {
2135         int i = d->below(-1);
2136         int c = 0;
2137         while (c < d->header->count() && d->header->isSectionHidden(c))
2138             ++c;
2139         if (i < d->viewItems.count() && c < d->header->count()) {
2140             return d->modelIndex(i, c);
2141         }
2142         return QModelIndex();
2143     }
2144     int vi = -1;
2145 #if defined(Q_WS_MAC) && !defined(QT_NO_STYLE_MAC)
2146     // Selection behavior is slightly different on the Mac.
2147     if (d->selectionMode == QAbstractItemView::ExtendedSelection
2148         && d->selectionModel
2149         && d->selectionModel->hasSelection()) {
2150
2151         const bool moveUpDown = (cursorAction == MoveUp || cursorAction == MoveDown);
2152         const bool moveNextPrev = (cursorAction == MoveNext || cursorAction == MovePrevious);
2153         const bool contiguousSelection = moveUpDown && (modifiers & Qt::ShiftModifier);
2154
2155         // Use the outermost index in the selection as the current index
2156         if (!contiguousSelection && (moveUpDown || moveNextPrev)) {
2157
2158             // Find outermost index.
2159             const bool useTopIndex = (cursorAction == MoveUp || cursorAction == MovePrevious);
2160             int index = useTopIndex ? INT_MAX : INT_MIN;
2161             const QItemSelection selection = d->selectionModel->selection();
2162             for (int i = 0; i < selection.count(); ++i) {
2163                 const QItemSelectionRange &range = selection.at(i);
2164                 int candidate = d->viewIndex(useTopIndex ? range.topLeft() : range.bottomRight());
2165                 if (candidate >= 0)
2166                     index = useTopIndex ? qMin(index, candidate) : qMax(index, candidate);
2167             }
2168
2169             if (index >= 0 && index < INT_MAX)
2170                 vi = index;
2171         }
2172     }
2173 #endif
2174     if (vi < 0)
2175         vi = qMax(0, d->viewIndex(current));
2176
2177     if (isRightToLeft()) {
2178         if (cursorAction == MoveRight)
2179             cursorAction = MoveLeft;
2180         else if (cursorAction == MoveLeft)
2181             cursorAction = MoveRight;
2182     }
2183     switch (cursorAction) {
2184     case MoveNext:
2185     case MoveDown:
2186 #ifdef QT_KEYPAD_NAVIGATION
2187         if (vi == d->viewItems.count()-1 && QApplication::keypadNavigationEnabled())
2188             return d->model->index(0, current.column(), d->root);
2189 #endif
2190         return d->modelIndex(d->below(vi), current.column());
2191     case MovePrevious:
2192     case MoveUp:
2193 #ifdef QT_KEYPAD_NAVIGATION
2194         if (vi == 0 && QApplication::keypadNavigationEnabled())
2195             return d->modelIndex(d->viewItems.count() - 1, current.column());
2196 #endif
2197         return d->modelIndex(d->above(vi), current.column());
2198     case MoveLeft: {
2199         QScrollBar *sb = horizontalScrollBar();
2200         if (vi < d->viewItems.count() && d->viewItems.at(vi).expanded && d->itemsExpandable && sb->value() == sb->minimum()) {
2201             d->collapse(vi, true);
2202             d->moveCursorUpdatedView = true;
2203         } else {
2204             bool descend = style()->styleHint(QStyle::SH_ItemView_ArrowKeysNavigateIntoChildren, 0, this);
2205             if (descend) {
2206                 QModelIndex par = current.parent();
2207                 if (par.isValid() && par != rootIndex())
2208                     return par;
2209                 else
2210                     descend = false;
2211             }
2212             if (!descend) {
2213                 if (d->selectionBehavior == SelectItems || d->selectionBehavior == SelectColumns) {
2214                     int visualColumn = d->header->visualIndex(current.column()) - 1;
2215                     while (visualColumn >= 0 && isColumnHidden(d->header->logicalIndex(visualColumn)))
2216                         visualColumn--;
2217                     int newColumn = d->header->logicalIndex(visualColumn);
2218                     QModelIndex next = current.sibling(current.row(), newColumn);
2219                     if (next.isValid())
2220                         return next;
2221                 }
2222
2223                 int oldValue = sb->value();
2224                 sb->setValue(sb->value() - sb->singleStep());
2225                 if (oldValue != sb->value())
2226                     d->moveCursorUpdatedView = true;
2227             }
2228
2229         }
2230         updateGeometries();
2231         viewport()->update();
2232         break;
2233     }
2234     case MoveRight:
2235         if (vi < d->viewItems.count() && !d->viewItems.at(vi).expanded && d->itemsExpandable
2236             && d->hasVisibleChildren(d->viewItems.at(vi).index)) {
2237             d->expand(vi, true);
2238             d->moveCursorUpdatedView = true;
2239         } else {
2240             bool descend = style()->styleHint(QStyle::SH_ItemView_ArrowKeysNavigateIntoChildren, 0, this);
2241             if (descend) {
2242                 QModelIndex idx = d->modelIndex(d->below(vi));
2243                 if (idx.parent() == current)
2244                     return idx;
2245                 else
2246                     descend = false;
2247             }
2248             if (!descend) {
2249                 if (d->selectionBehavior == SelectItems || d->selectionBehavior == SelectColumns) {
2250                     int visualColumn = d->header->visualIndex(current.column()) + 1;
2251                     while (visualColumn < d->model->columnCount(current.parent()) && isColumnHidden(d->header->logicalIndex(visualColumn)))
2252                         visualColumn++;
2253
2254                     QModelIndex next = current.sibling(current.row(), visualColumn);
2255                     if (next.isValid())
2256                         return next;
2257                 }
2258
2259                 //last restort: we change the scrollbar value
2260                 QScrollBar *sb = horizontalScrollBar();
2261                 int oldValue = sb->value();
2262                 sb->setValue(sb->value() + sb->singleStep());
2263                 if (oldValue != sb->value())
2264                     d->moveCursorUpdatedView = true;
2265             }
2266         }
2267         updateGeometries();
2268         viewport()->update();
2269         break;
2270     case MovePageUp:
2271         return d->modelIndex(d->pageUp(vi), current.column());
2272     case MovePageDown:
2273         return d->modelIndex(d->pageDown(vi), current.column());
2274     case MoveHome:
2275         return d->model->index(0, current.column(), d->root);
2276     case MoveEnd:
2277         return d->modelIndex(d->viewItems.count() - 1, current.column());
2278     }
2279     return current;
2280 }
2281
2282 /*!
2283   Applies the selection \a command to the items in or touched by the
2284   rectangle, \a rect.
2285
2286   \sa selectionCommand()
2287 */
2288 void QTreeView::setSelection(const QRect &rect, QItemSelectionModel::SelectionFlags command)
2289 {
2290     Q_D(QTreeView);
2291     if (!selectionModel() || rect.isNull())
2292         return;
2293
2294     d->executePostedLayout();
2295     QPoint tl(isRightToLeft() ? qMax(rect.left(), rect.right())
2296               : qMin(rect.left(), rect.right()), qMin(rect.top(), rect.bottom()));
2297     QPoint br(isRightToLeft() ? qMin(rect.left(), rect.right()) :
2298               qMax(rect.left(), rect.right()), qMax(rect.top(), rect.bottom()));
2299     QModelIndex topLeft = indexAt(tl);
2300     QModelIndex bottomRight = indexAt(br);
2301     if (!topLeft.isValid() && !bottomRight.isValid()) {
2302         if (command & QItemSelectionModel::Clear)
2303             selectionModel()->clear();
2304         return;
2305     }
2306     if (!topLeft.isValid() && !d->viewItems.isEmpty())
2307         topLeft = d->viewItems.first().index;
2308     if (!bottomRight.isValid() && !d->viewItems.isEmpty()) {
2309         const int column = d->header->logicalIndex(d->header->count() - 1);
2310         const QModelIndex index = d->viewItems.last().index;
2311         bottomRight = index.sibling(index.row(), column);
2312     }
2313
2314     if (!d->isIndexEnabled(topLeft) || !d->isIndexEnabled(bottomRight))
2315         return;
2316
2317     d->select(topLeft, bottomRight, command);
2318 }
2319
2320 /*!
2321   Returns the rectangle from the viewport of the items in the given
2322   \a selection.
2323
2324   Since 4.7, the returned region only contains rectangles intersecting
2325   (or included in) the viewport.
2326 */
2327 QRegion QTreeView::visualRegionForSelection(const QItemSelection &selection) const
2328 {
2329     Q_D(const QTreeView);
2330     if (selection.isEmpty())
2331         return QRegion();
2332
2333     QRegion selectionRegion;
2334     const QRect &viewportRect = d->viewport->rect();
2335     for (int i = 0; i < selection.count(); ++i) {
2336         QItemSelectionRange range = selection.at(i);
2337         if (!range.isValid())
2338             continue;
2339         QModelIndex parent = range.parent();
2340         QModelIndex leftIndex = range.topLeft();
2341         int columnCount = d->model->columnCount(parent);
2342         while (leftIndex.isValid() && isIndexHidden(leftIndex)) {
2343             if (leftIndex.column() + 1 < columnCount)
2344                 leftIndex = d->model->index(leftIndex.row(), leftIndex.column() + 1, parent);
2345             else
2346                 leftIndex = QModelIndex();
2347         }
2348         if (!leftIndex.isValid())
2349             continue;
2350         const QRect leftRect = visualRect(leftIndex);
2351         int top = leftRect.top();
2352         QModelIndex rightIndex = range.bottomRight();
2353         while (rightIndex.isValid() && isIndexHidden(rightIndex)) {
2354             if (rightIndex.column() - 1 >= 0)
2355                 rightIndex = d->model->index(rightIndex.row(), rightIndex.column() - 1, parent);
2356             else
2357                 rightIndex = QModelIndex();
2358         }
2359         if (!rightIndex.isValid())
2360             continue;
2361         const QRect rightRect = visualRect(rightIndex);
2362         int bottom = rightRect.bottom();
2363         if (top > bottom)
2364             qSwap<int>(top, bottom);
2365         int height = bottom - top + 1;
2366         if (d->header->sectionsMoved()) {
2367             for (int c = range.left(); c <= range.right(); ++c) {
2368                 const QRect rangeRect(columnViewportPosition(c), top, columnWidth(c), height);
2369                 if (viewportRect.intersects(rangeRect))
2370                     selectionRegion += rangeRect;
2371             }
2372         } else {
2373             QRect combined = leftRect|rightRect;
2374             combined.setX(columnViewportPosition(isRightToLeft() ? range.right() : range.left()));
2375             if (viewportRect.intersects(combined))
2376                 selectionRegion += combined;
2377         }
2378     }
2379     return selectionRegion;
2380 }
2381
2382 /*!
2383   \reimp
2384 */
2385 QModelIndexList QTreeView::selectedIndexes() const
2386 {
2387     QModelIndexList viewSelected;
2388     QModelIndexList modelSelected;
2389     if (selectionModel())
2390         modelSelected = selectionModel()->selectedIndexes();
2391     for (int i = 0; i < modelSelected.count(); ++i) {
2392         // check that neither the parents nor the index is hidden before we add
2393         QModelIndex index = modelSelected.at(i);
2394         while (index.isValid() && !isIndexHidden(index))
2395             index = index.parent();
2396         if (index.isValid())
2397             continue;
2398         viewSelected.append(modelSelected.at(i));
2399     }
2400     return viewSelected;
2401 }
2402
2403 /*!
2404   Scrolls the contents of the tree view by (\a dx, \a dy).
2405 */
2406 void QTreeView::scrollContentsBy(int dx, int dy)
2407 {
2408     Q_D(QTreeView);
2409
2410     d->delayedAutoScroll.stop(); // auto scroll was canceled by the user scrolling
2411
2412     dx = isRightToLeft() ? -dx : dx;
2413     if (dx) {
2414         if (horizontalScrollMode() == QAbstractItemView::ScrollPerItem) {
2415             int oldOffset = d->header->offset();
2416             if (horizontalScrollBar()->value() == horizontalScrollBar()->maximum())
2417                 d->header->setOffsetToLastSection();
2418             else
2419                 d->header->setOffsetToSectionPosition(horizontalScrollBar()->value());
2420             int newOffset = d->header->offset();
2421             dx = isRightToLeft() ? newOffset - oldOffset : oldOffset - newOffset;
2422         } else {
2423             d->header->setOffset(horizontalScrollBar()->value());
2424         }
2425     }
2426
2427     const int itemHeight = d->defaultItemHeight <= 0 ? sizeHintForRow(0) : d->defaultItemHeight;
2428     if (d->viewItems.isEmpty() || itemHeight == 0)
2429         return;
2430
2431     // guestimate the number of items in the viewport
2432     int viewCount = d->viewport->height() / itemHeight;
2433     int maxDeltaY = qMin(d->viewItems.count(), viewCount);
2434     // no need to do a lot of work if we are going to redraw the whole thing anyway
2435     if (qAbs(dy) > qAbs(maxDeltaY) && d->editorIndexHash.isEmpty()) {
2436         verticalScrollBar()->update();
2437         d->viewport->update();
2438         return;
2439     }
2440
2441     if (dy && verticalScrollMode() == QAbstractItemView::ScrollPerItem) {
2442         int currentScrollbarValue = verticalScrollBar()->value();
2443         int previousScrollbarValue = currentScrollbarValue + dy; // -(-dy)
2444         int currentViewIndex = currentScrollbarValue; // the first visible item
2445         int previousViewIndex = previousScrollbarValue;
2446         const QVector<QTreeViewItem> viewItems = d->viewItems;
2447         dy = 0;
2448         if (previousViewIndex < currentViewIndex) { // scrolling down
2449             for (int i = previousViewIndex; i < currentViewIndex; ++i) {
2450                 if (i < d->viewItems.count())
2451                     dy -= d->itemHeight(i);
2452             }
2453         } else if (previousViewIndex > currentViewIndex) { // scrolling up
2454             for (int i = previousViewIndex - 1; i >= currentViewIndex; --i) {
2455                 if (i < d->viewItems.count())
2456                     dy += d->itemHeight(i);
2457             }
2458         }
2459     }
2460
2461     d->scrollContentsBy(dx, dy);
2462 }
2463
2464 /*!
2465   This slot is called whenever a column has been moved.
2466 */
2467 void QTreeView::columnMoved()
2468 {
2469     Q_D(QTreeView);
2470     updateEditorGeometries();
2471     d->viewport->update();
2472 }
2473
2474 /*!
2475   \internal
2476 */
2477 void QTreeView::reexpand()
2478 {
2479     // do nothing
2480 }
2481
2482 /*!
2483   Informs the view that the rows from the \a start row to the \a end row
2484   inclusive have been inserted into the \a parent model item.
2485 */
2486 void QTreeView::rowsInserted(const QModelIndex &parent, int start, int end)
2487 {
2488     Q_D(QTreeView);
2489     // if we are going to do a complete relayout anyway, there is no need to update
2490     if (d->delayedPendingLayout) {
2491         QAbstractItemView::rowsInserted(parent, start, end);
2492         return;
2493     }
2494
2495     //don't add a hierarchy on a column != 0
2496     if (parent.column() != 0 && parent.isValid()) {
2497         QAbstractItemView::rowsInserted(parent, start, end);
2498         return;
2499     }
2500
2501     const int parentRowCount = d->model->rowCount(parent);
2502     const int delta = end - start + 1;
2503     if (parent != d->root && !d->isIndexExpanded(parent) && parentRowCount > delta) {
2504         QAbstractItemView::rowsInserted(parent, start, end);
2505         return;
2506     }
2507
2508     const int parentItem = d->viewIndex(parent);
2509     if (((parentItem != -1) && d->viewItems.at(parentItem).expanded)
2510         || (parent == d->root)) {
2511         d->doDelayedItemsLayout();
2512     } else if (parentItem != -1 && (d->model->rowCount(parent) == end - start + 1)) {
2513         // the parent just went from 0 children to more. update to re-paint the decoration
2514         d->viewItems[parentItem].hasChildren = true;
2515         viewport()->update();
2516     }
2517     QAbstractItemView::rowsInserted(parent, start, end);
2518 }
2519
2520 /*!
2521   Informs the view that the rows from the \a start row to the \a end row
2522   inclusive are about to removed from the given \a parent model item.
2523 */
2524 void QTreeView::rowsAboutToBeRemoved(const QModelIndex &parent, int start, int end)
2525 {
2526     Q_D(QTreeView);
2527     QAbstractItemView::rowsAboutToBeRemoved(parent, start, end);
2528     d->viewItems.clear();
2529 }
2530
2531 /*!
2532     \since 4.1
2533
2534     Informs the view that the rows from the \a start row to the \a end row
2535     inclusive have been removed from the given \a parent model item.
2536 */
2537 void QTreeView::rowsRemoved(const QModelIndex &parent, int start, int end)
2538 {
2539     Q_D(QTreeView);
2540     d->viewItems.clear();
2541     d->doDelayedItemsLayout();
2542     d->hasRemovedItems = true;
2543     d->_q_rowsRemoved(parent, start, end);
2544 }
2545
2546 /*!
2547   Informs the tree view that the number of columns in the tree view has
2548   changed from \a oldCount to \a newCount.
2549 */
2550 void QTreeView::columnCountChanged(int oldCount, int newCount)
2551 {
2552     Q_D(QTreeView);
2553     if (oldCount == 0 && newCount > 0) {
2554         //if the first column has just been added we need to relayout.
2555         d->doDelayedItemsLayout();
2556     }
2557
2558     if (isVisible())
2559         updateGeometries();
2560         viewport()->update();
2561 }
2562
2563 /*!
2564   Resizes the \a column given to the size of its contents.
2565
2566   \sa columnWidth(), setColumnWidth()
2567 */
2568 void QTreeView::resizeColumnToContents(int column)
2569 {
2570     Q_D(QTreeView);
2571     d->executePostedLayout();
2572     if (column < 0 || column >= d->header->count())
2573         return;
2574     int contents = sizeHintForColumn(column);
2575     int header = d->header->isHidden() ? 0 : d->header->sectionSizeHint(column);
2576     d->header->resizeSection(column, qMax(contents, header));
2577 }
2578
2579 /*!
2580   \obsolete
2581   \overload
2582
2583   Sorts the model by the values in the given \a column.
2584 */
2585 void QTreeView::sortByColumn(int column)
2586 {
2587     Q_D(QTreeView);
2588     sortByColumn(column, d->header->sortIndicatorOrder());
2589 }
2590
2591 /*!
2592   \since 4.2
2593
2594   Sets the model up for sorting by the values in the given \a column and \a order.
2595
2596   \a column may be -1, in which case no sort indicator will be shown
2597   and the model will return to its natural, unsorted order. Note that not
2598   all models support this and may even crash in this case.
2599
2600   \sa sortingEnabled
2601 */
2602 void QTreeView::sortByColumn(int column, Qt::SortOrder order)
2603 {
2604     Q_D(QTreeView);
2605
2606     //If sorting is enabled  will emit a signal connected to _q_sortIndicatorChanged, which then actually sorts
2607     d->header->setSortIndicator(column, order);
2608     //If sorting is not enabled, force to sort now.
2609     if (!d->sortingEnabled)
2610         d->model->sort(column, order);
2611 }
2612
2613 /*!
2614   \reimp
2615 */
2616 void QTreeView::selectAll()
2617 {
2618     Q_D(QTreeView);
2619     if (!selectionModel())
2620         return;
2621     SelectionMode mode = d->selectionMode;
2622     d->executePostedLayout(); //make sure we lay out the items
2623     if (mode != SingleSelection && !d->viewItems.isEmpty()) {
2624         const QModelIndex &idx = d->viewItems.last().index;
2625         QModelIndex lastItemIndex = idx.sibling(idx.row(), d->model->columnCount(idx.parent()) - 1);
2626         d->select(d->viewItems.first().index, lastItemIndex,
2627                   QItemSelectionModel::ClearAndSelect
2628                   |QItemSelectionModel::Rows);
2629     }
2630 }
2631
2632 /*!
2633   \since 4.2
2634   Expands all expandable items.
2635
2636   Warning: if the model contains a large number of items,
2637   this function will take some time to execute.
2638
2639   \sa collapseAll() expand()  collapse() setExpanded()
2640 */
2641 void QTreeView::expandAll()
2642 {
2643     Q_D(QTreeView);
2644     d->viewItems.clear();
2645     d->interruptDelayedItemsLayout();
2646     d->layout(-1, true);
2647     updateGeometries();
2648     d->viewport->update();
2649 }
2650
2651 /*!
2652   \since 4.2
2653
2654   Collapses all expanded items.
2655
2656   \sa expandAll() expand()  collapse() setExpanded()
2657 */
2658 void QTreeView::collapseAll()
2659 {
2660     Q_D(QTreeView);
2661     d->expandedIndexes.clear();
2662     doItemsLayout();
2663 }
2664
2665 /*!
2666   \since 4.3
2667   Expands all expandable items to the given \a depth.
2668
2669   \sa expandAll() collapseAll() expand()  collapse() setExpanded()
2670 */
2671 void QTreeView::expandToDepth(int depth)
2672 {
2673     Q_D(QTreeView);
2674     d->viewItems.clear();
2675     d->expandedIndexes.clear();
2676     d->interruptDelayedItemsLayout();
2677     d->layout(-1);
2678     for (int i = 0; i < d->viewItems.count(); ++i) {
2679         if (d->viewItems.at(i).level <= (uint)depth) {
2680             d->viewItems[i].expanded = true;
2681             d->layout(i);
2682             d->storeExpanded(d->viewItems.at(i).index);
2683         }
2684     }
2685     updateGeometries();
2686     d->viewport->update();
2687 }
2688
2689 /*!
2690     This function is called whenever \a{column}'s size is changed in
2691     the header. \a oldSize and \a newSize give the previous size and
2692     the new size in pixels.
2693
2694     \sa setColumnWidth()
2695 */
2696 void QTreeView::columnResized(int column, int /* oldSize */, int /* newSize */)
2697 {
2698     Q_D(QTreeView);
2699     d->columnsToUpdate.append(column);
2700     if (d->columnResizeTimerID == 0)
2701         d->columnResizeTimerID = startTimer(0);
2702 }
2703
2704 /*!
2705   \reimp
2706 */
2707 void QTreeView::updateGeometries()
2708 {
2709     Q_D(QTreeView);
2710     if (d->header) {
2711         if (d->geometryRecursionBlock)
2712             return;
2713         d->geometryRecursionBlock = true;
2714         QSize hint = d->header->isHidden() ? QSize(0, 0) : d->header->sizeHint();
2715         setViewportMargins(0, hint.height(), 0, 0);
2716         QRect vg = d->viewport->geometry();
2717         QRect geometryRect(vg.left(), vg.top() - hint.height(), vg.width(), hint.height());
2718         d->header->setGeometry(geometryRect);
2719         //d->header->setOffset(horizontalScrollBar()->value()); // ### bug ???
2720         QMetaObject::invokeMethod(d->header, "updateGeometries");
2721         d->updateScrollBars();
2722         d->geometryRecursionBlock = false;
2723     }
2724     QAbstractItemView::updateGeometries();
2725 }
2726
2727 /*!
2728   Returns the size hint for the \a column's width or -1 if there is no
2729   model.
2730
2731   If you need to set the width of a given column to a fixed value, call
2732   QHeaderView::resizeSection() on the view's header.
2733
2734   If you reimplement this function in a subclass, note that the value you
2735   return is only used when resizeColumnToContents() is called. In that case,
2736   if a larger column width is required by either the view's header or
2737   the item delegate, that width will be used instead.
2738
2739   \sa QWidget::sizeHint, header()
2740 */
2741 int QTreeView::sizeHintForColumn(int column) const
2742 {
2743     Q_D(const QTreeView);
2744     d->executePostedLayout();
2745     if (d->viewItems.isEmpty())
2746         return -1;
2747     ensurePolished();
2748     int w = 0;
2749     QStyleOptionViewItemV4 option = d->viewOptionsV4();
2750     const QVector<QTreeViewItem> viewItems = d->viewItems;
2751
2752     int start = 0;
2753     int end = viewItems.count();
2754     if(end > 1000) { //if we have too many item this function would be too slow.
2755         //we get a good approximation by only iterate over 1000 items.
2756         start = qMax(0, d->firstVisibleItem() - 100);
2757         end = qMin(end, start + 900);
2758     }
2759
2760     for (int i = start; i < end; ++i) {
2761         if (viewItems.at(i).spanning)
2762             continue; // we have no good size hint
2763         QModelIndex index = viewItems.at(i).index;
2764         index = index.sibling(index.row(), column);
2765         QWidget *editor = d->editorForIndex(index).widget.data();
2766         if (editor && d->persistent.contains(editor)) {
2767             w = qMax(w, editor->sizeHint().width());
2768             int min = editor->minimumSize().width();
2769             int max = editor->maximumSize().width();
2770             w = qBound(min, w, max);
2771         }
2772         int hint = d->delegateForIndex(index)->sizeHint(option, index).width();
2773         w = qMax(w, hint + (column == 0 ? d->indentationForItem(i) : 0));
2774     }
2775     return w;
2776 }
2777
2778 /*!
2779   Returns the size hint for the row indicated by \a index.
2780
2781   \sa sizeHintForColumn(), uniformRowHeights()
2782 */
2783 int QTreeView::indexRowSizeHint(const QModelIndex &index) const
2784 {
2785     Q_D(const QTreeView);
2786     if (!d->isIndexValid(index) || !d->itemDelegate)
2787         return 0;
2788
2789     int start = -1;
2790     int end = -1;
2791     int indexRow = index.row();
2792     int count = d->header->count();
2793     bool emptyHeader = (count == 0);
2794     QModelIndex parent = index.parent();
2795
2796     if (count && isVisible()) {
2797         // If the sections have moved, we end up checking too many or too few
2798         start = d->header->visualIndexAt(0);
2799     } else {
2800         // If the header has not been laid out yet, we use the model directly
2801         count = d->model->columnCount(parent);
2802     }
2803
2804     if (isRightToLeft()) {
2805         start = (start == -1 ? count - 1 : start);
2806         end = 0;
2807     } else {
2808         start = (start == -1 ? 0 : start);
2809         end = count - 1;
2810     }
2811
2812     if (end < start)
2813         qSwap(end, start);
2814
2815     int height = -1;
2816     QStyleOptionViewItemV4 option = d->viewOptionsV4();
2817     // ### If we want word wrapping in the items,
2818     // ### we need to go through all the columns
2819     // ### and set the width of the column
2820
2821     // Hack to speed up the function
2822     option.rect.setWidth(-1);
2823
2824     for (int column = start; column <= end; ++column) {
2825         int logicalColumn = emptyHeader ? column : d->header->logicalIndex(column);
2826         if (d->header->isSectionHidden(logicalColumn))
2827             continue;
2828         QModelIndex idx = d->model->index(indexRow, logicalColumn, parent);
2829         if (idx.isValid()) {
2830             QWidget *editor = d->editorForIndex(idx).widget.data();
2831             if (editor && d->persistent.contains(editor)) {
2832                 height = qMax(height, editor->sizeHint().height());
2833                 int min = editor->minimumSize().height();
2834                 int max = editor->maximumSize().height();
2835                 height = qBound(min, height, max);
2836             }
2837             int hint = d->delegateForIndex(idx)->sizeHint(option, idx).height();
2838             height = qMax(height, hint);
2839         }
2840     }
2841
2842     return height;
2843 }
2844
2845 /*!
2846     \since 4.3
2847     Returns the height of the row indicated by the given \a index.
2848     \sa indexRowSizeHint()
2849 */
2850 int QTreeView::rowHeight(const QModelIndex &index) const
2851 {
2852     Q_D(const QTreeView);
2853     d->executePostedLayout();
2854     int i = d->viewIndex(index);
2855     if (i == -1)
2856         return 0;
2857     return d->itemHeight(i);
2858 }
2859
2860 /*!
2861   \internal
2862 */
2863 void QTreeView::horizontalScrollbarAction(int action)
2864 {
2865     QAbstractItemView::horizontalScrollbarAction(action);
2866 }
2867
2868 /*!
2869   \reimp
2870 */
2871 bool QTreeView::isIndexHidden(const QModelIndex &index) const
2872 {
2873     return (isColumnHidden(index.column()) || isRowHidden(index.row(), index.parent()));
2874 }
2875
2876 /*
2877   private implementation
2878 */
2879 void QTreeViewPrivate::initialize()
2880 {
2881     Q_Q(QTreeView);
2882     updateStyledFrameWidths();
2883     q->setSelectionBehavior(QAbstractItemView::SelectRows);
2884     q->setSelectionMode(QAbstractItemView::SingleSelection);
2885     q->setHorizontalScrollMode(QAbstractItemView::ScrollPerPixel);
2886     q->setAttribute(Qt::WA_MacShowFocusRect);
2887
2888     QHeaderView *header = new QHeaderView(Qt::Horizontal, q);
2889     header->setMovable(true);
2890     header->setStretchLastSection(true);
2891     header->setDefaultAlignment(Qt::AlignLeft|Qt::AlignVCenter);
2892     q->setHeader(header);
2893 #ifndef QT_NO_ANIMATION
2894     QObject::connect(&animatedOperation, SIGNAL(finished()), q, SLOT(_q_endAnimatedOperation()));
2895 #endif //QT_NO_ANIMATION
2896 }
2897
2898 void QTreeViewPrivate::expand(int item, bool emitSignal)
2899 {
2900     Q_Q(QTreeView);
2901
2902     if (item == -1 || viewItems.at(item).expanded)
2903         return;
2904
2905 #ifndef QT_NO_ANIMATION
2906     if (emitSignal && animationsEnabled)
2907         prepareAnimatedOperation(item, QVariantAnimation::Forward);
2908 #endif //QT_NO_ANIMATION
2909     stateBeforeAnimation = state;
2910     q->setState(QAbstractItemView::ExpandingState);
2911     const QModelIndex index = viewItems.at(item).index;
2912     storeExpanded(index);
2913     viewItems[item].expanded = true;
2914     layout(item);
2915     q->setState(stateBeforeAnimation);
2916
2917     if (model->canFetchMore(index))
2918         model->fetchMore(index);
2919     if (emitSignal) {
2920         emit q->expanded(index);
2921 #ifndef QT_NO_ANIMATION
2922         if (animationsEnabled)
2923             beginAnimatedOperation();
2924 #endif //QT_NO_ANIMATION
2925     }
2926 }
2927
2928 void QTreeViewPrivate::insertViewItems(int pos, int count, const QTreeViewItem &viewItem)
2929 {
2930     Q_Q(QTreeView);
2931     viewItems.insert(pos, count, viewItem);
2932     QTreeViewItem *items = viewItems.data();
2933     for (int i = pos + count; i < viewItems.count(); i++)
2934         if (items[i].parentItem >= pos)
2935             items[i].parentItem += count;
2936 #ifndef QT_NO_ACCESSIBILITY
2937 #ifdef Q_WS_X11
2938     if (QAccessible::isActive()) {
2939         QAccessible::updateAccessibility(q, 0, QAccessible::TableModelChanged);
2940     }
2941 #endif
2942 #endif
2943 }
2944
2945 void QTreeViewPrivate::removeViewItems(int pos, int count)
2946 {
2947     Q_Q(QTreeView);
2948     viewItems.remove(pos, count);
2949     QTreeViewItem *items = viewItems.data();
2950     for (int i = pos; i < viewItems.count(); i++)
2951         if (items[i].parentItem >= pos)
2952             items[i].parentItem -= count;
2953 #ifndef QT_NO_ACCESSIBILITY
2954 #ifdef Q_WS_X11
2955     if (QAccessible::isActive()) {
2956         QAccessible::updateAccessibility(q, 0, QAccessible::TableModelChanged);
2957     }
2958 #endif
2959 #endif
2960 }
2961
2962 #if 0
2963 bool QTreeViewPrivate::checkViewItems() const
2964 {
2965     for (int i = 0; i < viewItems.count(); ++i) {
2966         const QTreeViewItem &vi = viewItems.at(i);
2967         if (vi.parentItem == -1) {
2968             Q_ASSERT(!vi.index.parent().isValid() || vi.index.parent() == root);
2969         } else {
2970             Q_ASSERT(vi.index.parent() == viewItems.at(vi.parentItem).index);
2971         }
2972     }
2973     return true;
2974 }
2975 #endif
2976
2977 void QTreeViewPrivate::collapse(int item, bool emitSignal)
2978 {
2979     Q_Q(QTreeView);
2980
2981     if (item == -1 || expandedIndexes.isEmpty())
2982         return;
2983
2984     //if the current item is now invisible, the autoscroll will expand the tree to see it, so disable the autoscroll
2985     delayedAutoScroll.stop();
2986
2987     int total = viewItems.at(item).total;
2988     const QModelIndex &modelIndex = viewItems.at(item).index;
2989     if (!isPersistent(modelIndex))
2990         return; // if the index is not persistent, no chances it is expanded
2991     QSet<QPersistentModelIndex>::iterator it = expandedIndexes.find(modelIndex);
2992     if (it == expandedIndexes.end() || viewItems.at(item).expanded == false)
2993         return; // nothing to do
2994
2995 #ifndef QT_NO_ANIMATION
2996     if (emitSignal && animationsEnabled)
2997         prepareAnimatedOperation(item, QVariantAnimation::Backward);
2998 #endif //QT_NO_ANIMATION
2999
3000     stateBeforeAnimation = state;
3001     q->setState(QAbstractItemView::CollapsingState);
3002     expandedIndexes.erase(it);
3003     viewItems[item].expanded = false;
3004     int index = item;
3005     while (index > -1) {
3006         viewItems[index].total -= total;
3007         index = viewItems[index].parentItem;
3008     }
3009     removeViewItems(item + 1, total); // collapse
3010     q->setState(stateBeforeAnimation);
3011
3012     if (emitSignal) {
3013         emit q->collapsed(modelIndex);
3014 #ifndef QT_NO_ANIMATION
3015         if (animationsEnabled)
3016             beginAnimatedOperation();
3017 #endif //QT_NO_ANIMATION
3018     }
3019 }
3020
3021 #ifndef QT_NO_ANIMATION
3022 void QTreeViewPrivate::prepareAnimatedOperation(int item, QVariantAnimation::Direction direction)
3023 {
3024     animatedOperation.item = item;
3025     animatedOperation.viewport = viewport;
3026     animatedOperation.setDirection(direction);
3027
3028     int top = coordinateForItem(item) + itemHeight(item);
3029     QRect rect = viewport->rect();
3030     rect.setTop(top);
3031     if (direction == QVariantAnimation::Backward) {
3032         const int limit = rect.height() * 2;
3033         int h = 0;
3034         int c = item + viewItems.at(item).total + 1;
3035         for (int i = item + 1; i < c && h < limit; ++i)
3036             h += itemHeight(i);
3037         rect.setHeight(h);
3038         animatedOperation.setEndValue(top + h);
3039     }
3040     animatedOperation.setStartValue(top);
3041     animatedOperation.before = renderTreeToPixmapForAnimation(rect);
3042 }
3043
3044 void QTreeViewPrivate::beginAnimatedOperation()
3045 {
3046     Q_Q(QTreeView);
3047
3048     QRect rect = viewport->rect();
3049     rect.setTop(animatedOperation.top());
3050     if (animatedOperation.direction() == QVariantAnimation::Forward) {
3051         const int limit = rect.height() * 2;
3052         int h = 0;
3053         int c = animatedOperation.item + viewItems.at(animatedOperation.item).total + 1;
3054         for (int i = animatedOperation.item + 1; i < c && h < limit; ++i)
3055             h += itemHeight(i);
3056         rect.setHeight(h);
3057         animatedOperation.setEndValue(animatedOperation.top() + h);
3058     }
3059
3060     if (!rect.isEmpty()) {
3061         animatedOperation.after = renderTreeToPixmapForAnimation(rect);
3062
3063         q->setState(QAbstractItemView::AnimatingState);
3064         animatedOperation.start(); //let's start the animation
3065     }
3066 }
3067
3068 void QTreeViewPrivate::drawAnimatedOperation(QPainter *painter) const
3069 {
3070     const int start = animatedOperation.startValue().toInt(),
3071         end = animatedOperation.endValue().toInt(),
3072         current = animatedOperation.currentValue().toInt();
3073     bool collapsing = animatedOperation.direction() == QVariantAnimation::Backward;
3074     const QPixmap top = collapsing ? animatedOperation.before : animatedOperation.after;
3075     painter->drawPixmap(0, start, top, 0, end - current - 1, top.width(), top.height());
3076     const QPixmap bottom = collapsing ? animatedOperation.after : animatedOperation.before;
3077     painter->drawPixmap(0, current, bottom);
3078 }
3079
3080 QPixmap QTreeViewPrivate::renderTreeToPixmapForAnimation(const QRect &rect) const
3081 {
3082     Q_Q(const QTreeView);
3083     QPixmap pixmap(rect.size());
3084     if (rect.size().isEmpty())
3085         return pixmap;
3086     pixmap.fill(Qt::transparent); //the base might not be opaque, and we don't want uninitialized pixels.
3087     QPainter painter(&pixmap);
3088     painter.fillRect(QRect(QPoint(0,0), rect.size()), q->palette().base());
3089     painter.translate(0, -rect.top());
3090     q->drawTree(&painter, QRegion(rect));
3091     painter.end();
3092
3093     //and now let's render the editors the editors
3094     QStyleOptionViewItemV4 option = viewOptionsV4();
3095     for (QEditorIndexHash::const_iterator it = editorIndexHash.constBegin(); it != editorIndexHash.constEnd(); ++it) {
3096         QWidget *editor = it.key();
3097         const QModelIndex &index = it.value();
3098         option.rect = q->visualRect(index);
3099         if (option.rect.isValid()) {
3100
3101             if (QAbstractItemDelegate *delegate = delegateForIndex(index))
3102                 delegate->updateEditorGeometry(editor, option, index);
3103
3104             const QPoint pos = editor->pos();
3105             if (rect.contains(pos)) {
3106                 editor->render(&pixmap, pos - rect.topLeft());
3107                 //the animation uses pixmap to display the treeview's content
3108                 //the editor is rendered on this pixmap and thus can (should) be hidden
3109                 editor->hide();
3110             }
3111         }
3112     }
3113
3114
3115     return pixmap;
3116 }
3117
3118 void QTreeViewPrivate::_q_endAnimatedOperation()
3119 {
3120     Q_Q(QTreeView);
3121     q->setState(stateBeforeAnimation);
3122     q->updateGeometries();
3123     viewport->update();
3124 }
3125 #endif //QT_NO_ANIMATION
3126
3127 void QTreeViewPrivate::_q_modelAboutToBeReset()
3128 {
3129     viewItems.clear();
3130 }
3131
3132 void QTreeViewPrivate::_q_columnsAboutToBeRemoved(const QModelIndex &parent, int start, int end)
3133 {
3134     if (start <= 0 && 0 <= end)
3135         viewItems.clear();
3136     QAbstractItemViewPrivate::_q_columnsAboutToBeRemoved(parent, start, end);
3137 }
3138
3139 void QTreeViewPrivate::_q_columnsRemoved(const QModelIndex &parent, int start, int end)
3140 {
3141     if (start <= 0 && 0 <= end)
3142         doDelayedItemsLayout();
3143     QAbstractItemViewPrivate::_q_columnsRemoved(parent, start, end);
3144 }
3145
3146 /** \internal
3147     creates and initialize the viewItem structure of the children of the element \i
3148
3149     set \a recursiveExpanding if the function has to expand all the children (called from expandAll)
3150     \a afterIsUninitialized is when we recurse from layout(-1), it means all the items after 'i' are
3151     not yet initialized and need not to be moved
3152  */
3153 void QTreeViewPrivate::layout(int i, bool recursiveExpanding, bool afterIsUninitialized)
3154 {
3155     Q_Q(QTreeView);
3156     QModelIndex current;
3157     QModelIndex parent = (i < 0) ? (QModelIndex)root : modelIndex(i);
3158
3159     if (i>=0 && !parent.isValid()) {
3160         //modelIndex() should never return something invalid for the real items.
3161         //This can happen if columncount has been set to 0.
3162         //To avoid infinite loop we stop here.
3163         return;
3164     }
3165
3166     int count = 0;
3167     if (model->hasChildren(parent)) {
3168         if (model->canFetchMore(parent))
3169             model->fetchMore(parent);
3170         count = model->rowCount(parent);
3171     }
3172
3173     bool expanding = true;
3174     if (i == -1) {
3175         if (uniformRowHeights) {
3176             QModelIndex index = model->index(0, 0, parent);
3177             defaultItemHeight = q->indexRowSizeHint(index);
3178         }
3179         viewItems.resize(count);
3180         afterIsUninitialized = true;
3181     } else if (viewItems[i].total != (uint)count) {
3182         if (!afterIsUninitialized)
3183             insertViewItems(i + 1, count, QTreeViewItem()); // expand
3184         else if (count > 0)
3185             viewItems.resize(viewItems.count() + count);
3186     } else {
3187         expanding = false;
3188     }
3189
3190     int first = i + 1;
3191     int level = (i >= 0 ? viewItems.at(i).level + 1 : 0);
3192     int hidden = 0;
3193     int last = 0;
3194     int children = 0;
3195     QTreeViewItem *item = 0;
3196     for (int j = first; j < first + count; ++j) {
3197         current = model->index(j - first, 0, parent);
3198         if (isRowHidden(current)) {
3199             ++hidden;
3200             last = j - hidden + children;
3201         } else {
3202             last = j - hidden + children;
3203             if (item)
3204                 item->hasMoreSiblings = true;
3205             item = &viewItems[last];
3206             item->index = current;
3207             item->parentItem = i;
3208             item->level = level;
3209             item->height = 0;
3210             item->spanning = q->isFirstColumnSpanned(current.row(), parent);
3211             item->expanded = false;
3212             item->total = 0;
3213             item->hasMoreSiblings = false;
3214             if (recursiveExpanding || isIndexExpanded(current)) {
3215                 if (recursiveExpanding)
3216                     expandedIndexes.insert(current);
3217                 item->expanded = true;
3218                 layout(last, recursiveExpanding, afterIsUninitialized);
3219                 item = &viewItems[last];
3220                 children += item->total;
3221                 item->hasChildren = item->total > 0;
3222                 last = j - hidden + children;
3223             } else {
3224                 item->hasChildren = hasVisibleChildren(current);
3225             }
3226         }
3227     }
3228
3229     // remove hidden items
3230     if (hidden > 0) {
3231         if (!afterIsUninitialized)
3232             removeViewItems(last + 1, hidden);
3233         else
3234             viewItems.resize(viewItems.size() - hidden);
3235     }
3236
3237     if (!expanding)
3238         return; // nothing changed
3239
3240     while (i > -1) {
3241         viewItems[i].total += count - hidden;
3242         i = viewItems[i].parentItem;
3243     }
3244 }
3245
3246 int QTreeViewPrivate::pageUp(int i) const
3247 {
3248     int index = itemAtCoordinate(coordinateForItem(i) - viewport->height());
3249     while (isItemHiddenOrDisabled(index))
3250         index--;
3251     return index == -1 ? 0 : index;
3252 }
3253
3254 int QTreeViewPrivate::pageDown(int i) const
3255 {
3256     int index = itemAtCoordinate(coordinateForItem(i) + viewport->height());
3257     while (isItemHiddenOrDisabled(index))
3258         index++;
3259     return index == -1 ? viewItems.count() - 1 : index;
3260 }
3261
3262 int QTreeViewPrivate::indentationForItem(int item) const
3263 {
3264     if (item < 0 || item >= viewItems.count())
3265         return 0;
3266     int level = viewItems.at(item).level;
3267     if (rootDecoration)
3268         ++level;
3269     return level * indent;
3270 }
3271
3272 int QTreeViewPrivate::itemHeight(int item) const
3273 {
3274     if (uniformRowHeights)
3275         return defaultItemHeight;
3276     if (viewItems.isEmpty())
3277         return 0;
3278     const QModelIndex &index = viewItems.at(item).index;
3279     if (!index.isValid())
3280         return 0;
3281     int height = viewItems.at(item).height;
3282     if (height <= 0) {
3283         height = q_func()->indexRowSizeHint(index);
3284         viewItems[item].height = height;
3285     }
3286     return qMax(height, 0);
3287 }
3288
3289
3290 /*!
3291   \internal
3292   Returns the viewport y coordinate for \a item.
3293 */
3294 int QTreeViewPrivate::coordinateForItem(int item) const
3295 {
3296     if (verticalScrollMode == QAbstractItemView::ScrollPerPixel) {
3297         if (uniformRowHeights)
3298             return (item * defaultItemHeight) - vbar->value();
3299         // ### optimize (spans or caching)
3300         int y = 0;
3301         for (int i = 0; i < viewItems.count(); ++i) {
3302             if (i == item)
3303                 return y - vbar->value();
3304             y += itemHeight(i);
3305         }
3306     } else { // ScrollPerItem
3307         int topViewItemIndex = vbar->value();
3308         if (uniformRowHeights)
3309             return defaultItemHeight * (item - topViewItemIndex);
3310         if (item >= topViewItemIndex) {
3311             // search in the visible area first and continue down
3312             // ### slow if the item is not visible
3313             int viewItemCoordinate = 0;
3314             int viewItemIndex = topViewItemIndex;
3315             while (viewItemIndex < viewItems.count()) {
3316                 if (viewItemIndex == item)
3317                     return viewItemCoordinate;
3318                 viewItemCoordinate += itemHeight(viewItemIndex);
3319                 ++viewItemIndex;
3320             }
3321             // below the last item in the view
3322             Q_ASSERT(false);
3323             return viewItemCoordinate;
3324         } else {
3325             // search the area above the viewport (used for editor widgets)
3326             int viewItemCoordinate = 0;
3327             for (int viewItemIndex = topViewItemIndex; viewItemIndex > 0; --viewItemIndex) {
3328                 if (viewItemIndex == item)
3329                     return viewItemCoordinate;
3330                 viewItemCoordinate -= itemHeight(viewItemIndex - 1);
3331             }
3332             return viewItemCoordinate;
3333         }
3334     }
3335     return 0;
3336 }
3337
3338 /*!
3339   \internal
3340   Returns the index of the view item at the
3341   given viewport \a coordinate.
3342
3343   \sa modelIndex()
3344 */
3345 int QTreeViewPrivate::itemAtCoordinate(int coordinate) const
3346 {
3347     const int itemCount = viewItems.count();
3348     if (itemCount == 0)
3349         return -1;
3350     if (uniformRowHeights && defaultItemHeight <= 0)
3351         return -1;
3352     if (verticalScrollMode == QAbstractItemView::ScrollPerPixel) {
3353         if (uniformRowHeights) {
3354             const int viewItemIndex = (coordinate + vbar->value()) / defaultItemHeight;
3355             return ((viewItemIndex >= itemCount || viewItemIndex < 0) ? -1 : viewItemIndex);
3356         }
3357         // ### optimize
3358         int viewItemCoordinate = 0;
3359         const int contentsCoordinate = coordinate + vbar->value();
3360         for (int viewItemIndex = 0; viewItemIndex < viewItems.count(); ++viewItemIndex) {
3361             viewItemCoordinate += itemHeight(viewItemIndex);
3362             if (viewItemCoordinate >= contentsCoordinate)
3363                 return (viewItemIndex >= itemCount ? -1 : viewItemIndex);
3364         }
3365     } else { // ScrollPerItem
3366         int topViewItemIndex = vbar->value();
3367         if (uniformRowHeights) {
3368             if (coordinate < 0)
3369                 coordinate -= defaultItemHeight - 1;
3370             const int viewItemIndex = topViewItemIndex + (coordinate / defaultItemHeight);
3371             return ((viewItemIndex >= itemCount || viewItemIndex < 0) ? -1 : viewItemIndex);
3372         }
3373         if (coordinate >= 0) {
3374             // the coordinate is in or below the viewport
3375             int viewItemCoordinate = 0;
3376             for (int viewItemIndex = topViewItemIndex; viewItemIndex < viewItems.count(); ++viewItemIndex) {
3377                 viewItemCoordinate += itemHeight(viewItemIndex);
3378                 if (viewItemCoordinate > coordinate)
3379                     return (viewItemIndex >= itemCount ? -1 : viewItemIndex);
3380             }
3381         } else {
3382             // the coordinate is above the viewport
3383             int viewItemCoordinate = 0;
3384             for (int viewItemIndex = topViewItemIndex; viewItemIndex >= 0; --viewItemIndex) {
3385                 if (viewItemCoordinate <= coordinate)
3386                     return (viewItemIndex >= itemCount ? -1 : viewItemIndex);
3387                 viewItemCoordinate -= itemHeight(viewItemIndex);
3388             }
3389         }
3390     }
3391     return -1;
3392 }
3393
3394 int QTreeViewPrivate::viewIndex(const QModelIndex &_index) const
3395 {
3396     if (!_index.isValid() || viewItems.isEmpty())
3397         return -1;
3398
3399     const int totalCount = viewItems.count();
3400     const QModelIndex index = _index.sibling(_index.row(), 0);
3401     const int row = index.row();
3402     const qint64 internalId = index.internalId();
3403
3404     // We start nearest to the lastViewedItem
3405     int localCount = qMin(lastViewedItem - 1, totalCount - lastViewedItem);
3406     for (int i = 0; i < localCount; ++i) {
3407         const QModelIndex &idx1 = viewItems.at(lastViewedItem + i).index;
3408         if (idx1.row() == row && idx1.internalId() == internalId) {
3409             lastViewedItem = lastViewedItem + i;
3410             return lastViewedItem;
3411         }
3412         const QModelIndex &idx2 = viewItems.at(lastViewedItem - i - 1).index;
3413         if (idx2.row() == row && idx2.internalId() == internalId) {
3414             lastViewedItem = lastViewedItem - i - 1;
3415             return lastViewedItem;
3416         }
3417     }
3418
3419     for (int j = qMax(0, lastViewedItem + localCount); j < totalCount; ++j) {
3420         const QModelIndex &idx = viewItems.at(j).index;
3421         if (idx.row() == row && idx.internalId() == internalId) {
3422             lastViewedItem = j;
3423             return j;
3424         }
3425     }
3426     for (int j = qMin(totalCount, lastViewedItem - localCount) - 1; j >= 0; --j) {
3427         const QModelIndex &idx = viewItems.at(j).index;
3428         if (idx.row() == row && idx.internalId() == internalId) {
3429             lastViewedItem = j;
3430             return j;
3431         }
3432     }
3433
3434     // nothing found
3435     return -1;
3436 }
3437
3438 QModelIndex QTreeViewPrivate::modelIndex(int i, int column) const
3439 {
3440     if (i < 0 || i >= viewItems.count())
3441         return QModelIndex();
3442
3443     QModelIndex ret = viewItems.at(i).index;
3444     if (column)
3445         ret = ret.sibling(ret.row(), column);
3446     return ret;
3447 }
3448
3449 int QTreeViewPrivate::firstVisibleItem(int *offset) const
3450 {
3451     const int value = vbar->value();
3452     if (verticalScrollMode == QAbstractItemView::ScrollPerItem) {
3453         if (offset)
3454             *offset = 0;
3455         return (value < 0 || value >= viewItems.count()) ? -1 : value;
3456     }
3457     // ScrollMode == ScrollPerPixel
3458     if (uniformRowHeights) {
3459         if (!defaultItemHeight)
3460             return -1;
3461
3462         if (offset)
3463             *offset = -(value % defaultItemHeight);
3464         return value / defaultItemHeight;
3465     }
3466     int y = 0; // ### optimize (use spans ?)
3467     for (int i = 0; i < viewItems.count(); ++i) {
3468         y += itemHeight(i); // the height value is cached
3469         if (y > value) {
3470             if (offset)
3471                 *offset = y - value - itemHeight(i);
3472             return i;
3473         }
3474     }
3475     return -1;
3476 }
3477
3478 int QTreeViewPrivate::columnAt(int x) const
3479 {
3480     return header->logicalIndexAt(x);
3481 }
3482
3483 void QTreeViewPrivate::updateScrollBars()
3484 {
3485     Q_Q(QTreeView);
3486     QSize viewportSize = viewport->size();
3487     if (!viewportSize.isValid())
3488         viewportSize = QSize(0, 0);
3489
3490     if (viewItems.isEmpty()) {
3491         q->doItemsLayout();
3492     }
3493
3494     int itemsInViewport = 0;
3495     if (uniformRowHeights) {
3496         if (defaultItemHeight <= 0)
3497             itemsInViewport = viewItems.count();
3498         else
3499             itemsInViewport = viewportSize.height() / defaultItemHeight;
3500     } else {
3501         const int itemsCount = viewItems.count();
3502         const int viewportHeight = viewportSize.height();
3503         for (int height = 0, item = itemsCount - 1; item >= 0; --item) {
3504             height += itemHeight(item);
3505             if (height > viewportHeight)
3506                 break;
3507             ++itemsInViewport;
3508         }
3509     }
3510     if (verticalScrollMode == QAbstractItemView::ScrollPerItem) {
3511         if (!viewItems.isEmpty())
3512             itemsInViewport = qMax(1, itemsInViewport);
3513         vbar->setRange(0, viewItems.count() - itemsInViewport);
3514         vbar->setPageStep(itemsInViewport);
3515         vbar->setSingleStep(1);
3516     } else { // scroll per pixel
3517         int contentsHeight = 0;
3518         if (uniformRowHeights) {
3519             contentsHeight = defaultItemHeight * viewItems.count();
3520         } else { // ### optimize (spans or caching)
3521             for (int i = 0; i < viewItems.count(); ++i)
3522                 contentsHeight += itemHeight(i);
3523         }
3524         vbar->setRange(0, contentsHeight - viewportSize.height());
3525         vbar->setPageStep(viewportSize.height());
3526         vbar->setSingleStep(qMax(viewportSize.height() / (itemsInViewport + 1), 2));
3527     }
3528
3529     const int columnCount = header->count();
3530     const int viewportWidth = viewportSize.width();
3531     int columnsInViewport = 0;
3532     for (int width = 0, column = columnCount - 1; column >= 0; --column) {
3533         int logical = header->logicalIndex(column);
3534         width += header->sectionSize(logical);
3535         if (width > viewportWidth)
3536             break;
3537         ++columnsInViewport;
3538     }
3539     if (columnCount > 0)
3540         columnsInViewport = qMax(1, columnsInViewport);
3541     if (horizontalScrollMode == QAbstractItemView::ScrollPerItem) {
3542         hbar->setRange(0, columnCount - columnsInViewport);
3543         hbar->setPageStep(columnsInViewport);
3544         hbar->setSingleStep(1);
3545     } else { // scroll per pixel
3546         const int horizontalLength = header->length();
3547         const QSize maxSize = q->maximumViewportSize();
3548         if (maxSize.width() >= horizontalLength && vbar->maximum() <= 0)
3549             viewportSize = maxSize;
3550         hbar->setPageStep(viewportSize.width());
3551         hbar->setRange(0, qMax(horizontalLength - viewportSize.width(), 0));