Implement group-header layouting

The most tricky part for groups - the layouting - basically works
now for all views (grouping was available only in the icons views
for Dolphin 1.x) and is nearly equally fast as without groups.

Still open:
- Group headers are ugly screen rectangles
- Return valid groups in KFileItemModel instead of the currently
  hardcoded testing values
- Dynamically turning on/off groups does not work currently, the
  directory must be reentered

6 files changed, 107 insertions, 154 deletions

diff --git a/src/kitemviews/kfileitemlistview.cpp b/src/kitemviews/kfileitemlistview.cpp
index a77ede50a..a3cf88290 100644
--- a/src/kitemviews/kfileitemlistview.cpp
+++ b/src/kitemviews/kfileitemlistview.cpp
@@ -68,8 +68,11 @@ KFileItemListView::KFileItemListView(QGraphicsWidget* parent) :
 
 KFileItemListView::~KFileItemListView()
 {
-    delete widgetCreator();
+    // The group headers are children of the widgets created by
+    // widgetCreator(). So it is mandatory to delete the group headers
+    // first.
     delete groupHeaderCreator();
+    delete widgetCreator();
 
     delete m_modelRolesUpdater;
     m_modelRolesUpdater = 0;
diff --git a/src/kitemviews/kfileitemmodel.cpp b/src/kitemviews/kfileitemmodel.cpp
index 3a49135f9..46de7c5aa 100644
--- a/src/kitemviews/kfileitemmodel.cpp
+++ b/src/kitemviews/kfileitemmodel.cpp
@@ -225,15 +225,19 @@ QString KFileItemModel::roleDescription(const QByteArray& role) const
 
 QList<QPair<int, QVariant> > KFileItemModel::groups() const
 {
-    // TODO:
+    // TODO: dirty hack for initial testing of grouping functionality
     QPair<int, QVariant> group1(0, "Group 1");
-    QPair<int, QVariant> group2(5, "Group 2");
+    QPair<int, QVariant> group2(2, "Group 2");
     QPair<int, QVariant> group3(10, "Group 3");
+    QPair<int, QVariant> group4(11, "Group 4");
+    QPair<int, QVariant> group5(40, "Group 5");
 
     QList<QPair<int, QVariant> > groups;
     groups.append(group1);
     groups.append(group2);
     groups.append(group3);
+    groups.append(group4);
+    groups.append(group5);
     return groups;
 }
 
diff --git a/src/kitemviews/kitemlistview.cpp b/src/kitemviews/kitemlistview.cpp
index a4cb4b041..eb464a9e7 100644
--- a/src/kitemviews/kitemlistview.cpp
+++ b/src/kitemviews/kitemlistview.cpp
@@ -23,7 +23,6 @@
 #include "kitemlistview.h"
 
 #include "kitemlistcontroller.h"
-#include "kitemlistgroupheader.h"
 #include "kitemlistheader_p.h"
 #include "kitemlistrubberband_p.h"
 #include "kitemlistselectionmanager.h"
@@ -1318,6 +1317,8 @@ KItemListWidget* KItemListView::createWidget(int index)
     if (m_grouped) {
         if (m_layouter->isFirstGroupItem(index)) {
             KItemListGroupHeader* header = m_groupHeaderCreator->create(widget);
+            header->show();
+            // TODO:
             header->setPos(0, -50);
             header->resize(50, 50);
             m_visibleGroups.insert(widget, header);
@@ -1358,6 +1359,8 @@ void KItemListView::setWidgetIndex(KItemListWidget* widget, int index)
 
         if (createHeader) {
             KItemListGroupHeader* header = m_groupHeaderCreator->create(widget);
+            header->show();
+            // TODO:
             header->setPos(0, -50);
             header->resize(50, 50);
             m_visibleGroups.insert(widget, header);
@@ -1667,6 +1670,7 @@ KItemListWidgetCreatorBase::~KItemListWidgetCreatorBase()
 
 void KItemListWidgetCreatorBase::recycle(KItemListWidget* widget)
 {
+    widget->setParentItem(0);
     widget->setOpacity(1.0);
     pushRecycleableWidget(widget);
 }
diff --git a/src/kitemviews/kitemlistview.h b/src/kitemviews/kitemlistview.h
index c18f8cb84..8a26a1535 100644
--- a/src/kitemviews/kitemlistview.h
+++ b/src/kitemviews/kitemlistview.h
@@ -25,6 +25,7 @@
 
 #include <libdolphin_export.h>
 
+#include <kitemviews/kitemlistgroupheader.h>
 #include <kitemviews/kitemliststyleoption.h>
 #include <kitemviews/kitemlistviewanimation_p.h>
 #include <kitemviews/kitemlistwidget.h>
@@ -33,7 +34,6 @@
 #include <QSet>
 
 class KItemListController;
-class KItemListGroupHeader;
 class KItemListGroupHeaderCreatorBase;
 class KItemListHeader;
 class KItemListSizeHintResolver;
@@ -477,7 +477,9 @@ template <class T>
 KItemListWidget* KItemListWidgetCreator<T>::create(KItemListView* view)
 {
     KItemListWidget* widget = static_cast<KItemListWidget*>(popRecycleableWidget());
-    if (!widget) {
+    if (widget) {
+        widget->setParentItem(view);
+    } else {
         widget = new T(view);
         addCreatedWidget(widget);
     }
@@ -517,7 +519,9 @@ template <class T>
 KItemListGroupHeader* KItemListGroupHeaderCreator<T>::create(QGraphicsWidget* parent)
 {
     KItemListGroupHeader* widget = static_cast<KItemListGroupHeader*>(popRecycleableWidget());
-    if (!widget) {
+    if (widget) {
+        widget->setParentItem(parent);
+    } else {
         widget = new T(parent);
         addCreatedWidget(widget);
     }
diff --git a/src/kitemviews/kitemlistviewlayouter.cpp b/src/kitemviews/kitemlistviewlayouter.cpp
index 30881abfd..4aae66f63 100644
--- a/src/kitemviews/kitemlistviewlayouter.cpp
+++ b/src/kitemviews/kitemlistviewlayouter.cpp
@@ -27,15 +27,14 @@
 #define KITEMLISTVIEWLAYOUTER_DEBUG
 
 namespace {
-    // TODO
-    const int HeaderHeight = 50;
+    // TODO: Calculate dynamically
+    const int GroupHeaderHeight = 50;
 };
 
 KItemListViewLayouter::KItemListViewLayouter(QObject* parent) :
     QObject(parent),
     m_dirty(true),
     m_visibleIndexesDirty(true),
-    m_grouped(false),
     m_scrollOrientation(Qt::Vertical),
     m_size(),
     m_itemSize(128, 128),
@@ -48,7 +47,6 @@ KItemListViewLayouter::KItemListViewLayouter(QObject* parent) :
     m_maximumItemOffset(0),
     m_firstVisibleIndex(-1),
     m_lastVisibleIndex(-1),
-    m_firstVisibleGroupIndex(-1),
     m_columnWidth(0),
     m_xPosInc(0),
     m_columnCount(0),
@@ -287,11 +285,41 @@ void KItemListViewLayouter::doLayout()
         qreal y = m_headerHeight;
         int rowIndex = 0;
 
+        const bool grouped = createGroupHeaders();
+        int groupIndex = 0;
+        int firstItemIndexOfGroup = 0;
+
         int index = 0;
         while (index < itemCount) {
             qreal x = m_xPosInc;
             qreal maxItemHeight = itemSize.height();
 
+            if (grouped) {
+                if (horizontalScrolling) {
+                    // All group headers will always be aligned on the top and not
+                    // flipped like the other properties
+                    x += GroupHeaderHeight;
+                }
+
+                if (index == firstItemIndexOfGroup) {
+                    if (!horizontalScrolling) {
+                        // The item is the first item of a group.
+                        // Increase the y-position to provide space
+                        // for the group header.
+                        y += GroupHeaderHeight;
+                    }
+
+                    // Calculate the index of the first item for
+                    // the next group
+                    ++groupIndex;
+                    if (groupIndex < m_groups.count()) {
+                        firstItemIndexOfGroup = m_groups.at(groupIndex);
+                    } else {
+                        firstItemIndexOfGroup = -1;
+                    }
+                }
+            }
+
             int column = 0;
             while (index < itemCount && column < m_columnCount) {
                 qreal requiredItemHeight = itemSize.height();
@@ -314,6 +342,12 @@ void KItemListViewLayouter::doLayout()
                 x += m_columnWidth;
                 ++index;
                 ++column;
+
+                if (grouped && index == firstItemIndexOfGroup) {
+                    // The item represents the first index of a group
+                    // and must aligned in the first column
+                    break;
+                }
             }
 
             y += maxItemHeight;
@@ -332,28 +366,13 @@ void KItemListViewLayouter::doLayout()
             m_maximumItemOffset = 0;
         }
 
-        m_grouped = m_model->groupedSorting();
-        if (m_grouped) {
-            createGroupHeaders();
-
-            const int lastGroupItemCount = m_model->count() - m_groups.last().firstItemIndex;
-            m_maximumScrollOffset = m_groups.last().y + (lastGroupItemCount / m_columnCount) * itemSize.height();
-            if (lastGroupItemCount % m_columnCount != 0) {
-                m_maximumScrollOffset += itemSize.height();
-            }
-        }
-
 #ifdef KITEMLISTVIEWLAYOUTER_DEBUG
         kDebug() << "[TIME] doLayout() for " << m_model->count() << "items:" << timer.elapsed();
 #endif
         m_dirty = false;
     }
 
-    if (m_grouped) {
-        updateGroupedVisibleIndexes();
-    } else {
-        updateVisibleIndexes();
-    }
+    updateVisibleIndexes();
 }
 
 void KItemListViewLayouter::updateVisibleIndexes()
@@ -362,7 +381,6 @@ void KItemListViewLayouter::updateVisibleIndexes()
         return;
     }
 
-    Q_ASSERT(!m_grouped);
     Q_ASSERT(!m_dirty);
 
     if (m_model->count() <= 0) {
@@ -372,145 +390,74 @@ void KItemListViewLayouter::updateVisibleIndexes()
         return;
     }
 
-    const bool horizontalScrolling = (m_scrollOrientation == Qt::Horizontal);
-    const int minimumHeight =  horizontalScrolling ? m_itemSize.width()
-                                                   : m_itemSize.height();
-
-    // Calculate the first visible index:
-    // 1. Guess the index by using the minimum row height
     const int maxIndex = m_model->count() - 1;
-    m_firstVisibleIndex = int(m_scrollOffset / minimumHeight) * m_columnCount;
-
-    // 2. Decrease the index by checking the real row heights
-    int prevRowIndex = m_firstVisibleIndex - m_columnCount;
-    while (prevRowIndex > maxIndex) {
-        prevRowIndex -= m_columnCount;
-    }
-
-    const qreal top = m_scrollOffset + m_headerHeight;
-    while (prevRowIndex >= 0 && m_itemBoundingRects[prevRowIndex].bottom() >= top) {
-        m_firstVisibleIndex = prevRowIndex;
-        prevRowIndex -= m_columnCount;
-    }
-    m_firstVisibleIndex = qBound(0, m_firstVisibleIndex, maxIndex);
-
-    // Calculate the last visible index
-    const int visibleHeight = horizontalScrolling ? m_size.width() : m_size.height();
-    const qreal bottom = m_scrollOffset + visibleHeight;
-    m_lastVisibleIndex = m_firstVisibleIndex; // first visible row, first column
-    int nextRowIndex = m_lastVisibleIndex + m_columnCount;
-    while (nextRowIndex <= maxIndex && m_itemBoundingRects[nextRowIndex].y() <= bottom) {
-        m_lastVisibleIndex = nextRowIndex;
-        nextRowIndex += m_columnCount;
-    }
-    m_lastVisibleIndex += m_columnCount - 1; // move it to the last column
-    m_lastVisibleIndex = qBound(0, m_lastVisibleIndex, maxIndex);
-
-    m_visibleIndexesDirty = false;
-}
-
-void KItemListViewLayouter::updateGroupedVisibleIndexes()
-{
-    if (!m_visibleIndexesDirty) {
-        return;
-    }
-
-    Q_ASSERT(m_grouped);
-    Q_ASSERT(!m_dirty);
 
-    if (m_model->count() <= 0) {
-        m_firstVisibleIndex = -1;
-        m_lastVisibleIndex = -1;
-        m_visibleIndexesDirty = false;
-        return;
-    }
-
-    // Find the first visible group
-    const int lastGroupIndex = m_groups.count() - 1;
-    int groupIndex = lastGroupIndex;
-    for (int i = 1; i < m_groups.count(); ++i) {
-        if (m_groups[i].y >= m_scrollOffset) {
-            groupIndex = i - 1;
-            break;
+    // Calculate the first visible index that is (at least partly) visible
+    int min = 0;
+    int max = maxIndex;
+    int mid = 0;
+    do {
+        mid = (min + max) / 2;
+        if (m_itemBoundingRects[mid].bottom() < m_scrollOffset) {
+            min = mid + 1;
+        } else {
+            max = mid - 1;
         }
-    }
+    } while (min <= max);
 
-    // Calculate the first visible index
-    qreal groupY = m_groups[groupIndex].y;
-    m_firstVisibleIndex = m_groups[groupIndex].firstItemIndex;
-    const int invisibleRowCount = int(m_scrollOffset - groupY) / int(m_itemSize.height());
-    m_firstVisibleIndex += invisibleRowCount * m_columnCount;
-    if (groupIndex + 1 <= lastGroupIndex) {
-        // Check whether the calculated first visible index remains inside the current
-        // group. If this is not the case let the first element of the next group be the first
-        // visible index.
-        const int nextGroupIndex = m_groups[groupIndex + 1].firstItemIndex;
-        if (m_firstVisibleIndex > nextGroupIndex) {
-            m_firstVisibleIndex = nextGroupIndex;
-        }
+    while (mid < maxIndex && m_itemBoundingRects[mid].bottom() < m_scrollOffset) {
+        ++mid;
     }
+    m_firstVisibleIndex = mid;
 
-    m_firstVisibleGroupIndex = groupIndex;
-
-    const int maxIndex = m_model->count() - 1;
-    m_firstVisibleIndex = qBound(0, m_firstVisibleIndex, maxIndex);
-
-    // Calculate the last visible index: Find group where the last visible item is shown.
-    const qreal visibleBottom = m_scrollOffset + m_size.height(); // TODO: respect Qt::Horizontal alignment
-    while ((groupIndex < lastGroupIndex) && (m_groups[groupIndex + 1].y < visibleBottom)) {
-        ++groupIndex;
-    }
-
-    groupY = m_groups[groupIndex].y;
-    m_lastVisibleIndex = m_groups[groupIndex].firstItemIndex;
-    const int availableHeight = static_cast<int>(visibleBottom - groupY);
-    int visibleRowCount = availableHeight / int(m_itemSize.height());
-    if (availableHeight % int(m_itemSize.height()) != 0) {
-        ++visibleRowCount;
+    // Calculate the last visible index that is (at least partly) visible
+    const int visibleHeight = (m_scrollOrientation == Qt::Horizontal) ? m_size.width() : m_size.height();
+    qreal bottom = m_scrollOffset + visibleHeight;
+    if (m_model->groupedSorting()) {
+        bottom += GroupHeaderHeight;
     }
-    m_lastVisibleIndex += visibleRowCount * m_columnCount - 1;
 
-    if (groupIndex + 1 <= lastGroupIndex) {
-        // Check whether the calculate last visible index remains inside the current group.
-        // If this is not the case let the last element of this group be the last visible index.
-        const int nextGroupIndex = m_groups[groupIndex + 1].firstItemIndex;
-        if (m_lastVisibleIndex >= nextGroupIndex) {
-            m_lastVisibleIndex = nextGroupIndex - 1;
+    min = m_firstVisibleIndex;
+    max = maxIndex;
+    do {
+        mid = (min + max) / 2;
+        if (m_itemBoundingRects[mid].y() <= bottom) {
+            min = mid + 1;
+        } else {
+            max = mid - 1;
         }
+    } while (min <= max);
+
+    while (mid > 0 && m_itemBoundingRects[mid].y() > bottom) {
+        --mid;
     }
-    m_lastVisibleIndex = qBound(0, m_lastVisibleIndex, maxIndex);
+    m_lastVisibleIndex = mid;
 
     m_visibleIndexesDirty = false;
 }
 
-void KItemListViewLayouter::createGroupHeaders()
+bool KItemListViewLayouter::createGroupHeaders()
 {
+    if (!m_model->groupedSorting()) {
+        return false;
+    }
+
     m_groups.clear();
     m_groupIndexes.clear();
 
     const QList<QPair<int, QVariant> > groups = m_model->groups();
+    if (groups.isEmpty()) {
+        return false;
+    }
 
-    qreal y = 0;
+    m_groups.reserve(groups.count());
     for (int i = 0; i < groups.count(); ++i) {
         const int firstItemIndex = groups.at(i).first;
-        if (i > 0) {
-            const int previousGroupItemCount = firstItemIndex - m_groups.last().firstItemIndex;
-            int previousGroupRowCount = previousGroupItemCount / m_columnCount;
-            if (previousGroupItemCount % m_columnCount != 0) {
-                ++previousGroupRowCount;
-            }
-            const qreal previousGroupHeight = previousGroupRowCount * m_itemSize.height();
-            y += previousGroupHeight;
-        }
-        y += HeaderHeight;
-
-        ItemGroup itemGroup;
-        itemGroup.firstItemIndex = firstItemIndex;
-        itemGroup.y = y;
-
-        m_groups.append(itemGroup);
+        m_groups.append(firstItemIndex);
         m_groupIndexes.insert(firstItemIndex);
     }
+
+    return true;
 }
 
 #include "kitemlistviewlayouter_p.moc"
diff --git a/src/kitemviews/kitemlistviewlayouter_p.h b/src/kitemviews/kitemlistviewlayouter_p.h
index c81995d9b..255db9188 100644
--- a/src/kitemviews/kitemlistviewlayouter_p.h
+++ b/src/kitemviews/kitemlistviewlayouter_p.h
@@ -95,15 +95,12 @@ public:
 
 private:
     void doLayout();
-
     void updateVisibleIndexes();
-    void updateGroupedVisibleIndexes();
-    void createGroupHeaders();
+    bool createGroupHeaders();
 
 private:
     bool m_dirty;
     bool m_visibleIndexesDirty;
-    bool m_grouped;
 
     Qt::Orientation m_scrollOrientation;
     QSizeF m_size;
@@ -122,17 +119,11 @@ private:
     int m_firstVisibleIndex;
     int m_lastVisibleIndex;
 
-    int m_firstVisibleGroupIndex;
-
     qreal m_columnWidth;
     qreal m_xPosInc;
     int m_columnCount;
 
-    struct ItemGroup {
-        int firstItemIndex;
-        qreal y;
-    };
-    QList<ItemGroup> m_groups;
+    QList<int> m_groups;
 
     // Stores all item indexes that are the first item of a group.
     // Assures fast access for KItemListViewLayouter::isFirstGroupItem().