From fc2ab478989fb4effc14c06aa56fdb29d3143b35 Mon Sep 17 00:00:00 2001 From: Frank Reininghaus Date: Wed, 30 Oct 2013 23:21:09 +0100 Subject: Store the selected items in a more efficient way Since Dolphin 2.0, we have stored the selected items in a QSet, which is neither space-efficient nor particularly fast when inserting many items which are in a consecutive range. This commit replaces the QSet by a new class "KItemSet", which stores the items in a sorted list of ranges. For each range, we only store the first index and the length of the range, so we need a lot less memory for most common selection patterns, and we also save quite a few CPU cycles in many situations, because adding an item to the KItemSet will in many cases not need a memory allocation at all, and it's particularly easy when inserting sorted items into the KItemSet in a row. KItemSet contains a minimal subset of QSet's API which makes it suitable as a drop-in replacement for our needs. It also has iterators, such that the items can be iterated through easily, also with foreach. One advantage of KItemSet compared to QSet is that the items are always iterated through in ascending order. REVIEW: 113488 --- src/tests/CMakeLists.txt | 12 + src/tests/kitemlistcontrollertest.cpp | 202 ++++----- src/tests/kitemlistselectionmanagertest.cpp | 100 ++--- src/tests/kitemsettest.cpp | 612 ++++++++++++++++++++++++++++ 4 files changed, 775 insertions(+), 151 deletions(-) create mode 100644 src/tests/kitemsettest.cpp (limited to 'src/tests') diff --git a/src/tests/CMakeLists.txt b/src/tests/CMakeLists.txt index dd761fc90..9b152ed07 100644 --- a/src/tests/CMakeLists.txt +++ b/src/tests/CMakeLists.txt @@ -3,11 +3,21 @@ include_directories( ${CMAKE_CURRENT_SOURCE_DIR}/.. ${CMAKE_CURRENT_BUILD_DIR}/. # needed on windows to correctly use the files from dolphinprivate add_definitions(-DLIBDOLPHINPRIVATE_EXPORT=) + +# KItemSetTest +set(kitemsettest_SRCS + kitemsettest.cpp + ../kitemviews/kitemset.cpp +) +kde4_add_unit_test(kitemsettest TEST ${kitemsettest_SRCS}) +target_link_libraries(kitemsettest dolphinprivate ${KDE4_KIO_LIBS} ${QT_QTTEST_LIBRARY}) + # KItemListSelectionManagerTest set(kitemlistselectionmanagertest_SRCS kitemlistselectionmanagertest.cpp ../kitemviews/kitemlistselectionmanager.cpp ../kitemviews/kitemmodelbase.cpp + ../kitemviews/kitemset.cpp ) kde4_add_unit_test(kitemlistselectionmanagertest TEST ${kitemlistselectionmanagertest_SRCS}) target_link_libraries(kitemlistselectionmanagertest dolphinprivate ${KDE4_KIO_LIBS} ${QT_QTTEST_LIBRARY}) @@ -24,6 +34,7 @@ set(kitemlistcontrollertest_SRCS ../kitemviews/kitemlistcontainer.cpp ../kitemviews/kitemlistwidget.cpp ../kitemviews/kitemlistviewaccessible.cpp + ../kitemviews/kitemset.cpp ../kitemviews/kstandarditemlistview.cpp ../kitemviews/kstandarditemlistwidget.cpp ) @@ -41,6 +52,7 @@ set(kfileitemlistviewtest_SRCS ../kitemviews/kitemlistviewaccessible.cpp ../kitemviews/kitemlistcontainer.cpp ../kitemviews/kitemlistwidget.cpp + ../kitemviews/kitemset.cpp ../kitemviews/kstandarditemlistview.cpp ../kitemviews/kstandarditemlistwidget.cpp ) diff --git a/src/tests/kitemlistcontrollertest.cpp b/src/tests/kitemlistcontrollertest.cpp index 60e93e539..7dd37bf0a 100644 --- a/src/tests/kitemlistcontrollertest.cpp +++ b/src/tests/kitemlistcontrollertest.cpp @@ -41,7 +41,7 @@ namespace { Q_DECLARE_METATYPE(KFileItemListView::ItemLayout); Q_DECLARE_METATYPE(Qt::Orientation); Q_DECLARE_METATYPE(KItemListController::SelectionBehavior); -Q_DECLARE_METATYPE(QSet); +Q_DECLARE_METATYPE(KItemSet); class KItemListControllerTest : public QObject { @@ -81,7 +81,7 @@ private: */ void KItemListControllerTest::initTestCase() { - qRegisterMetaType >("QSet"); + qRegisterMetaType("KItemSet"); m_testDir = new TestDir(); m_model = new KFileItemModel(); @@ -159,14 +159,14 @@ struct KeyPress { */ struct ViewState { - ViewState(int current, const QSet selection, bool activated = false) : + ViewState(int current, const KItemSet selection, bool activated = false) : m_current(current), m_selection(selection), m_activated(activated) {} int m_current; - QSet m_selection; + KItemSet m_selection; bool m_activated; }; @@ -262,34 +262,34 @@ void KItemListControllerTest::testKeyboardNavigation_data() // First, key presses which should have the same effect // for any layout and any number of columns. testList - << qMakePair(KeyPress(nextItemKey), ViewState(1, QSet() << 1)) - << qMakePair(KeyPress(Qt::Key_Return), ViewState(1, QSet() << 1, true)) - << qMakePair(KeyPress(Qt::Key_Enter), ViewState(1, QSet() << 1, true)) - << qMakePair(KeyPress(nextItemKey), ViewState(2, QSet() << 2)) - << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(3, QSet() << 2 << 3)) - << qMakePair(KeyPress(Qt::Key_Return), ViewState(3, QSet() << 2 << 3, true)) - << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(2, QSet() << 2)) - << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(3, QSet() << 2 << 3)) - << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(4, QSet() << 2 << 3)) - << qMakePair(KeyPress(Qt::Key_Return), ViewState(4, QSet() << 2 << 3, true)) - << qMakePair(KeyPress(previousItemKey), ViewState(3, QSet() << 3)) - << qMakePair(KeyPress(Qt::Key_Home, Qt::ShiftModifier), ViewState(0, QSet() << 0 << 1 << 2 << 3)) - << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(1, QSet() << 0 << 1 << 2 << 3)) - << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(1, QSet() << 0 << 2 << 3)) - << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(1, QSet() << 0 << 1 << 2 << 3)) - << qMakePair(KeyPress(Qt::Key_End), ViewState(19, QSet() << 19)) - << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(18, QSet() << 18 << 19)) - << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet() << 0)) - << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, QSet())) - << qMakePair(KeyPress(Qt::Key_Enter), ViewState(0, QSet(), true)) - << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, QSet() << 0)) - << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, QSet())) - << qMakePair(KeyPress(Qt::Key_Space), ViewState(0, QSet() << 0)) - << qMakePair(KeyPress(Qt::Key_E), ViewState(13, QSet() << 13)) - << qMakePair(KeyPress(Qt::Key_Space), ViewState(14, QSet() << 14)) - << qMakePair(KeyPress(Qt::Key_3), ViewState(15, QSet() << 15)) - << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet() << 0)) - << qMakePair(KeyPress(Qt::Key_Escape), ViewState(0, QSet())); + << qMakePair(KeyPress(nextItemKey), ViewState(1, KItemSet() << 1)) + << qMakePair(KeyPress(Qt::Key_Return), ViewState(1, KItemSet() << 1, true)) + << qMakePair(KeyPress(Qt::Key_Enter), ViewState(1, KItemSet() << 1, true)) + << qMakePair(KeyPress(nextItemKey), ViewState(2, KItemSet() << 2)) + << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(3, KItemSet() << 2 << 3)) + << qMakePair(KeyPress(Qt::Key_Return), ViewState(3, KItemSet() << 2 << 3, true)) + << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(2, KItemSet() << 2)) + << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(3, KItemSet() << 2 << 3)) + << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(4, KItemSet() << 2 << 3)) + << qMakePair(KeyPress(Qt::Key_Return), ViewState(4, KItemSet() << 2 << 3, true)) + << qMakePair(KeyPress(previousItemKey), ViewState(3, KItemSet() << 3)) + << qMakePair(KeyPress(Qt::Key_Home, Qt::ShiftModifier), ViewState(0, KItemSet() << 0 << 1 << 2 << 3)) + << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(1, KItemSet() << 0 << 1 << 2 << 3)) + << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(1, KItemSet() << 0 << 2 << 3)) + << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(1, KItemSet() << 0 << 1 << 2 << 3)) + << qMakePair(KeyPress(Qt::Key_End), ViewState(19, KItemSet() << 19)) + << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(18, KItemSet() << 18 << 19)) + << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0)) + << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, KItemSet())) + << qMakePair(KeyPress(Qt::Key_Enter), ViewState(0, KItemSet(), true)) + << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, KItemSet() << 0)) + << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, KItemSet())) + << qMakePair(KeyPress(Qt::Key_Space), ViewState(0, KItemSet() << 0)) + << qMakePair(KeyPress(Qt::Key_E), ViewState(13, KItemSet() << 13)) + << qMakePair(KeyPress(Qt::Key_Space), ViewState(14, KItemSet() << 14)) + << qMakePair(KeyPress(Qt::Key_3), ViewState(15, KItemSet() << 15)) + << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0)) + << qMakePair(KeyPress(Qt::Key_Escape), ViewState(0, KItemSet())); // Next, we test combinations of key presses which only work for a // particular number of columns and either enabled or disabled grouping. @@ -297,12 +297,12 @@ void KItemListControllerTest::testKeyboardNavigation_data() // One column. if (columnCount == 1) { testList - << qMakePair(KeyPress(nextRowKey), ViewState(1, QSet() << 1)) - << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(2, QSet() << 1 << 2)) - << qMakePair(KeyPress(nextRowKey, Qt::ControlModifier), ViewState(3, QSet() << 1 << 2)) - << qMakePair(KeyPress(previousRowKey), ViewState(2, QSet() << 2)) - << qMakePair(KeyPress(previousItemKey), ViewState(1, QSet() << 1)) - << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet() << 0)); + << qMakePair(KeyPress(nextRowKey), ViewState(1, KItemSet() << 1)) + << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(2, KItemSet() << 1 << 2)) + << qMakePair(KeyPress(nextRowKey, Qt::ControlModifier), ViewState(3, KItemSet() << 1 << 2)) + << qMakePair(KeyPress(previousRowKey), ViewState(2, KItemSet() << 2)) + << qMakePair(KeyPress(previousItemKey), ViewState(1, KItemSet() << 1)) + << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0)); } // Multiple columns: we test both 3 and 5 columns with grouping @@ -321,26 +321,26 @@ void KItemListControllerTest::testKeyboardNavigation_data() // e3 e4 e5 | 15 16 17 // e6 e7 | 18 19 testList - << qMakePair(KeyPress(nextRowKey), ViewState(3, QSet() << 3)) - << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(4, QSet() << 3)) - << qMakePair(KeyPress(nextRowKey), ViewState(7, QSet() << 7)) - << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(8, QSet() << 7 << 8)) - << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(9, QSet() << 7 << 8 << 9)) - << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(8, QSet() << 7 << 8)) - << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(7, QSet() << 7)) - << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(6, QSet() << 6 << 7)) - << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(5, QSet() << 5 << 6 << 7)) - << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(6, QSet() << 6 << 7)) - << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(7, QSet() << 7)) - << qMakePair(KeyPress(nextRowKey), ViewState(10, QSet() << 10)) - << qMakePair(KeyPress(nextItemKey), ViewState(11, QSet() << 11)) - << qMakePair(KeyPress(nextRowKey), ViewState(14, QSet() << 14)) - << qMakePair(KeyPress(nextRowKey), ViewState(17, QSet() << 17)) - << qMakePair(KeyPress(nextRowKey), ViewState(19, QSet() << 19)) - << qMakePair(KeyPress(previousRowKey), ViewState(17, QSet() << 17)) - << qMakePair(KeyPress(Qt::Key_End), ViewState(19, QSet() << 19)) - << qMakePair(KeyPress(previousRowKey), ViewState(16, QSet() << 16)) - << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet() << 0)); + << qMakePair(KeyPress(nextRowKey), ViewState(3, KItemSet() << 3)) + << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(4, KItemSet() << 3)) + << qMakePair(KeyPress(nextRowKey), ViewState(7, KItemSet() << 7)) + << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(8, KItemSet() << 7 << 8)) + << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(9, KItemSet() << 7 << 8 << 9)) + << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(8, KItemSet() << 7 << 8)) + << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(7, KItemSet() << 7)) + << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(6, KItemSet() << 6 << 7)) + << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(5, KItemSet() << 5 << 6 << 7)) + << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(6, KItemSet() << 6 << 7)) + << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(7, KItemSet() << 7)) + << qMakePair(KeyPress(nextRowKey), ViewState(10, KItemSet() << 10)) + << qMakePair(KeyPress(nextItemKey), ViewState(11, KItemSet() << 11)) + << qMakePair(KeyPress(nextRowKey), ViewState(14, KItemSet() << 14)) + << qMakePair(KeyPress(nextRowKey), ViewState(17, KItemSet() << 17)) + << qMakePair(KeyPress(nextRowKey), ViewState(19, KItemSet() << 19)) + << qMakePair(KeyPress(previousRowKey), ViewState(17, KItemSet() << 17)) + << qMakePair(KeyPress(Qt::Key_End), ViewState(19, KItemSet() << 19)) + << qMakePair(KeyPress(previousRowKey), ViewState(16, KItemSet() << 16)) + << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0)); } if (columnCount == 5 && !groupingEnabled) { @@ -351,17 +351,17 @@ void KItemListControllerTest::testKeyboardNavigation_data() // d2 d3 d4 e1 e2 | 10 11 12 13 14 // e3 e4 e5 e6 e7 | 15 16 17 18 19 testList - << qMakePair(KeyPress(nextRowKey), ViewState(5, QSet() << 5)) - << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(6, QSet() << 5)) - << qMakePair(KeyPress(nextRowKey), ViewState(11, QSet() << 11)) - << qMakePair(KeyPress(nextItemKey), ViewState(12, QSet() << 12)) - << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(17, QSet() << 12 << 13 << 14 << 15 << 16 << 17)) - << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(12, QSet() << 12)) - << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(7, QSet() << 7 << 8 << 9 << 10 << 11 << 12)) - << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(12, QSet() << 12)) - << qMakePair(KeyPress(Qt::Key_End, Qt::ControlModifier), ViewState(19, QSet() << 12)) - << qMakePair(KeyPress(previousRowKey), ViewState(14, QSet() << 14)) - << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet() << 0)); + << qMakePair(KeyPress(nextRowKey), ViewState(5, KItemSet() << 5)) + << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(6, KItemSet() << 5)) + << qMakePair(KeyPress(nextRowKey), ViewState(11, KItemSet() << 11)) + << qMakePair(KeyPress(nextItemKey), ViewState(12, KItemSet() << 12)) + << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(17, KItemSet() << 12 << 13 << 14 << 15 << 16 << 17)) + << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(12, KItemSet() << 12)) + << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(7, KItemSet() << 7 << 8 << 9 << 10 << 11 << 12)) + << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(12, KItemSet() << 12)) + << qMakePair(KeyPress(Qt::Key_End, Qt::ControlModifier), ViewState(19, KItemSet() << 12)) + << qMakePair(KeyPress(previousRowKey), ViewState(14, KItemSet() << 14)) + << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0)); } if (columnCount == 3 && groupingEnabled) { @@ -377,19 +377,19 @@ void KItemListControllerTest::testKeyboardNavigation_data() // e4 e5 e6 | 16 17 18 // e7 | 19 testList - << qMakePair(KeyPress(nextItemKey), ViewState(1, QSet() << 1)) - << qMakePair(KeyPress(nextItemKey), ViewState(2, QSet() << 2)) - << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(3, QSet() << 2 << 3)) - << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(6, QSet() << 2 << 3 << 4 << 5 << 6)) - << qMakePair(KeyPress(nextRowKey), ViewState(8, QSet() << 8)) - << qMakePair(KeyPress(nextRowKey), ViewState(11, QSet() << 11)) - << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(12, QSet() << 11)) - << qMakePair(KeyPress(nextRowKey), ViewState(13, QSet() << 13)) - << qMakePair(KeyPress(nextRowKey), ViewState(16, QSet() << 16)) - << qMakePair(KeyPress(nextItemKey), ViewState(17, QSet() << 17)) - << qMakePair(KeyPress(nextRowKey), ViewState(19, QSet() << 19)) - << qMakePair(KeyPress(previousRowKey), ViewState(17, QSet() << 17)) - << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet() << 0)); + << qMakePair(KeyPress(nextItemKey), ViewState(1, KItemSet() << 1)) + << qMakePair(KeyPress(nextItemKey), ViewState(2, KItemSet() << 2)) + << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(3, KItemSet() << 2 << 3)) + << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(6, KItemSet() << 2 << 3 << 4 << 5 << 6)) + << qMakePair(KeyPress(nextRowKey), ViewState(8, KItemSet() << 8)) + << qMakePair(KeyPress(nextRowKey), ViewState(11, KItemSet() << 11)) + << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(12, KItemSet() << 11)) + << qMakePair(KeyPress(nextRowKey), ViewState(13, KItemSet() << 13)) + << qMakePair(KeyPress(nextRowKey), ViewState(16, KItemSet() << 16)) + << qMakePair(KeyPress(nextItemKey), ViewState(17, KItemSet() << 17)) + << qMakePair(KeyPress(nextRowKey), ViewState(19, KItemSet() << 19)) + << qMakePair(KeyPress(previousRowKey), ViewState(17, KItemSet() << 17)) + << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0)); } if (columnCount == 5 && groupingEnabled) { @@ -402,19 +402,19 @@ void KItemListControllerTest::testKeyboardNavigation_data() // e1 e2 e3 e4 e5 | 13 14 15 16 17 // e6 e7 | 18 19 testList - << qMakePair(KeyPress(nextItemKey), ViewState(1, QSet() << 1)) - << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(3, QSet() << 1 << 2 << 3)) - << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(5, QSet() << 1 << 2 << 3 << 4 << 5)) - << qMakePair(KeyPress(nextItemKey), ViewState(6, QSet() << 6)) - << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(7, QSet() << 6)) - << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(8, QSet() << 6)) - << qMakePair(KeyPress(nextRowKey), ViewState(12, QSet() << 12)) - << qMakePair(KeyPress(nextRowKey), ViewState(17, QSet() << 17)) - << qMakePair(KeyPress(nextRowKey), ViewState(19, QSet() << 19)) - << qMakePair(KeyPress(previousRowKey), ViewState(17, QSet() << 17)) - << qMakePair(KeyPress(Qt::Key_End, Qt::ShiftModifier), ViewState(19, QSet() << 17 << 18 << 19)) - << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(14, QSet() << 14 << 15 << 16 << 17)) - << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet() << 0)); + << qMakePair(KeyPress(nextItemKey), ViewState(1, KItemSet() << 1)) + << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(3, KItemSet() << 1 << 2 << 3)) + << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(5, KItemSet() << 1 << 2 << 3 << 4 << 5)) + << qMakePair(KeyPress(nextItemKey), ViewState(6, KItemSet() << 6)) + << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(7, KItemSet() << 6)) + << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(8, KItemSet() << 6)) + << qMakePair(KeyPress(nextRowKey), ViewState(12, KItemSet() << 12)) + << qMakePair(KeyPress(nextRowKey), ViewState(17, KItemSet() << 17)) + << qMakePair(KeyPress(nextRowKey), ViewState(19, KItemSet() << 19)) + << qMakePair(KeyPress(previousRowKey), ViewState(17, KItemSet() << 17)) + << qMakePair(KeyPress(Qt::Key_End, Qt::ShiftModifier), ViewState(19, KItemSet() << 17 << 18 << 19)) + << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(14, KItemSet() << 14 << 15 << 16 << 17)) + << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0)); } const QString testName = @@ -470,14 +470,14 @@ void KItemListControllerTest::testKeyboardNavigation() QCOMPARE(m_view->m_layouter->m_columnCount, columnCount); QSignalSpy spySingleItemActivated(m_controller, SIGNAL(itemActivated(int))); - QSignalSpy spyMultipleItemsActivated(m_controller, SIGNAL(itemsActivated(QSet))); + QSignalSpy spyMultipleItemsActivated(m_controller, SIGNAL(itemsActivated(KItemSet))); while (!testList.isEmpty()) { const QPair test = testList.takeFirst(); const Qt::Key key = test.first.m_key; const Qt::KeyboardModifiers modifier = test.first.m_modifier; const int current = test.second.m_current; - const QSet selection = test.second.m_selection; + const KItemSet selection = test.second.m_selection; const bool activated = test.second.m_activated; QTest::keyClick(m_container, key, modifier); @@ -485,7 +485,7 @@ void KItemListControllerTest::testKeyboardNavigation() QCOMPARE(m_selectionManager->currentItem(), current); switch (selectionBehavior) { case KItemListController::NoSelection: QVERIFY(m_selectionManager->selectedItems().isEmpty()); break; - case KItemListController::SingleSelection: QCOMPARE(m_selectionManager->selectedItems(), QSet() << current); break; + case KItemListController::SingleSelection: QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << current); break; case KItemListController::MultiSelection: QCOMPARE(m_selectionManager->selectedItems(), selection); break; } @@ -496,12 +496,12 @@ void KItemListControllerTest::testKeyboardNavigation() // The selected items should be activated. if (selection.count() == 1) { QVERIFY(!spySingleItemActivated.isEmpty()); - QCOMPARE(qvariant_cast(spySingleItemActivated.takeFirst().at(0)), selection.toList().at(0)); + QCOMPARE(qvariant_cast(spySingleItemActivated.takeFirst().at(0)), selection.first()); QVERIFY(spyMultipleItemsActivated.isEmpty()); } else { QVERIFY(spySingleItemActivated.isEmpty()); QVERIFY(!spyMultipleItemsActivated.isEmpty()); - QCOMPARE(qvariant_cast >(spyMultipleItemsActivated.takeFirst().at(0)), selection); + QCOMPARE(qvariant_cast(spyMultipleItemsActivated.takeFirst().at(0)), selection); } break; } @@ -641,7 +641,7 @@ void KItemListControllerTest::testMouseClickActivation() group.writeEntry("SingleClick", restoreKGlobalSettingsSingleClick, KConfig::Persistent|KConfig::Global); config.sync(); KGlobalSettings::self()->emitChange(KGlobalSettings::SettingsChanged, KGlobalSettings::SETTINGS_MOUSE); - + iterations = 0; while (KGlobalSettings::singleClick() != restoreKGlobalSettingsSingleClick && iterations < maxIterations) { QTest::qWait(50); diff --git a/src/tests/kitemlistselectionmanagertest.cpp b/src/tests/kitemlistselectionmanagertest.cpp index 302985a5f..af2610d8c 100644 --- a/src/tests/kitemlistselectionmanagertest.cpp +++ b/src/tests/kitemlistselectionmanagertest.cpp @@ -80,7 +80,7 @@ private slots: void testDeleteCurrentItem(); private: - void verifySelectionChange(QSignalSpy& spy, const QSet& currentSelection, const QSet& previousSelection) const; + void verifySelectionChange(QSignalSpy& spy, const KItemSet& currentSelection, const KItemSet& previousSelection) const; KItemListSelectionManager* m_selectionManager; DummyModel* m_model; @@ -127,7 +127,7 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem() QCOMPARE(m_selectionManager->m_anchorItem, 5); // Items between current and anchor should be selected now - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 4 << 5); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 4 << 5); QVERIFY(m_selectionManager->hasSelection()); // Change current item again and check the selection @@ -138,7 +138,7 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem() QCOMPARE(qvariant_cast(spyCurrent.at(0).at(1)), 4); spyCurrent.takeFirst(); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 2 << 3 << 4 << 5); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 2 << 3 << 4 << 5); QVERIFY(m_selectionManager->hasSelection()); // Inserting items should update current item and anchor item. @@ -155,7 +155,7 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem() QCOMPARE(m_selectionManager->m_anchorItem, 8); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7 << 8); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 8); QVERIFY(m_selectionManager->hasSelection()); // Removing items should update current item and anchor item. @@ -172,12 +172,12 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem() QCOMPARE(m_selectionManager->m_anchorItem, 5); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 2 << 3 << 4 << 5); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 2 << 3 << 4 << 5); QVERIFY(m_selectionManager->hasSelection()); // Verify that clearSelection() also clears the anchored selection. m_selectionManager->clearSelection(); - QCOMPARE(m_selectionManager->selectedItems(), QSet()); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet()); QVERIFY(!m_selectionManager->hasSelection()); m_selectionManager->endAnchoredSelection(); @@ -212,7 +212,7 @@ void KItemListSelectionManagerTest::testItemsInserted() { // Select items 10 to 12 m_selectionManager->setSelected(10, 3); - QSet selectedItems = m_selectionManager->selectedItems(); + KItemSet selectedItems = m_selectionManager->selectedItems(); QCOMPARE(selectedItems.count(), 3); QVERIFY(selectedItems.contains(10)); QVERIFY(selectedItems.contains(11)); @@ -242,7 +242,7 @@ void KItemListSelectionManagerTest::testItemsRemoved() { // Select items 10 to 15 m_selectionManager->setSelected(10, 6); - QSet selectedItems = m_selectionManager->selectedItems(); + KItemSet selectedItems = m_selectionManager->selectedItems(); QCOMPARE(selectedItems.count(), 6); for (int i = 10; i <= 15; ++i) { QVERIFY(selectedItems.contains(i)); @@ -276,20 +276,20 @@ void KItemListSelectionManagerTest::testAnchoredSelection() m_selectionManager->setCurrentItem(6); QCOMPARE(m_selectionManager->currentItem(), 6); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6); m_selectionManager->setCurrentItem(4); QCOMPARE(m_selectionManager->currentItem(), 4); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 4 << 5); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 4 << 5); m_selectionManager->setCurrentItem(7); QCOMPARE(m_selectionManager->currentItem(), 7); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7); // Ending the anchored selection should not change the selected items. m_selectionManager->endAnchoredSelection(); QVERIFY(!m_selectionManager->isAnchoredSelectionActive()); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7); // Start a new anchored selection that overlaps the previous one m_selectionManager->beginAnchoredSelection(9); @@ -298,15 +298,15 @@ void KItemListSelectionManagerTest::testAnchoredSelection() m_selectionManager->setCurrentItem(6); QCOMPARE(m_selectionManager->currentItem(), 6); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7 << 8 << 9); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 8 << 9); m_selectionManager->setCurrentItem(10); QCOMPARE(m_selectionManager->currentItem(), 10); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7 << 9 << 10); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 9 << 10); m_selectionManager->endAnchoredSelection(); QVERIFY(!m_selectionManager->isAnchoredSelectionActive()); - QCOMPARE(m_selectionManager->selectedItems(), QSet() << 5 << 6 << 7 << 9 << 10); + QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 9 << 10); } namespace { @@ -320,7 +320,7 @@ namespace { }; } -Q_DECLARE_METATYPE(QSet); +Q_DECLARE_METATYPE(KItemSet); Q_DECLARE_METATYPE(ChangeType); Q_DECLARE_METATYPE(KItemRange); Q_DECLARE_METATYPE(KItemRangeList); @@ -355,86 +355,86 @@ Q_DECLARE_METATYPE(QList); void KItemListSelectionManagerTest::testChangeSelection_data() { - QTest::addColumn >("initialSelection"); + QTest::addColumn("initialSelection"); QTest::addColumn("anchor"); QTest::addColumn("current"); - QTest::addColumn >("expectedSelection"); + QTest::addColumn("expectedSelection"); QTest::addColumn("changeType"); QTest::addColumn >("data"); - QTest::addColumn >("finalSelection"); + QTest::addColumn("finalSelection"); QTest::newRow("No change") - << (QSet() << 5 << 6) + << (KItemSet() << 5 << 6) << 2 << 3 - << (QSet() << 2 << 3 << 5 << 6) + << (KItemSet() << 2 << 3 << 5 << 6) << NoChange << QList() - << (QSet() << 2 << 3 << 5 << 6); + << (KItemSet() << 2 << 3 << 5 << 6); QTest::newRow("Insert Items") - << (QSet() << 5 << 6) + << (KItemSet() << 5 << 6) << 2 << 3 - << (QSet() << 2 << 3 << 5 << 6) + << (KItemSet() << 2 << 3 << 5 << 6) << InsertItems << (QList() << QVariant::fromValue(KItemRangeList() << KItemRange(1, 1) << KItemRange(5, 2) << KItemRange(10, 5))) - << (QSet() << 3 << 4 << 8 << 9); + << (KItemSet() << 3 << 4 << 8 << 9); QTest::newRow("Remove Items") - << (QSet() << 5 << 6) + << (KItemSet() << 5 << 6) << 2 << 3 - << (QSet() << 2 << 3 << 5 << 6) + << (KItemSet() << 2 << 3 << 5 << 6) << RemoveItems << (QList() << QVariant::fromValue(KItemRangeList() << KItemRange(1, 1) << KItemRange(3, 1) << KItemRange(10, 5))) - << (QSet() << 1 << 2 << 3 << 4); + << (KItemSet() << 1 << 2 << 3 << 4); QTest::newRow("Empty Anchored Selection") - << QSet() + << KItemSet() << 2 << 2 - << QSet() + << KItemSet() << EndAnchoredSelection << QList() - << QSet(); + << KItemSet(); QTest::newRow("Toggle selection") - << (QSet() << 1 << 3 << 4) + << (KItemSet() << 1 << 3 << 4) << 6 << 8 - << (QSet() << 1 << 3 << 4 << 6 << 7 << 8) + << (KItemSet() << 1 << 3 << 4 << 6 << 7 << 8) << SetSelected << (QList() << 0 << 10 << QVariant::fromValue(KItemListSelectionManager::Toggle)) - << (QSet() << 0 << 2 << 5 << 9); + << (KItemSet() << 0 << 2 << 5 << 9); // Swap items 2, 3 and 4, 5 QTest::newRow("Move items") - << (QSet() << 0 << 1 << 2 << 3) + << (KItemSet() << 0 << 1 << 2 << 3) << -1 << -1 - << (QSet() << 0 << 1 << 2 << 3) + << (KItemSet() << 0 << 1 << 2 << 3) << MoveItems << (QList() << QVariant::fromValue(KItemRange(2, 4)) << QVariant::fromValue(QList() << 4 << 5 << 2 << 3)) - << (QSet() << 0 << 1 << 4 << 5); + << (KItemSet() << 0 << 1 << 4 << 5); // Revert sort order QTest::newRow("Revert sort order") - << (QSet() << 0 << 1) + << (KItemSet() << 0 << 1) << 3 << 4 - << (QSet() << 0 << 1 << 3 << 4) + << (KItemSet() << 0 << 1 << 3 << 4) << MoveItems << (QList() << QVariant::fromValue(KItemRange(0, 10)) << QVariant::fromValue(QList() << 9 << 8 << 7 << 6 << 5 << 4 << 3 << 2 << 1 << 0)) - << (QSet() << 5 << 6 << 8 << 9); + << (KItemSet() << 5 << 6 << 8 << 9); } void KItemListSelectionManagerTest::testChangeSelection() { - QFETCH(QSet, initialSelection); + QFETCH(KItemSet, initialSelection); QFETCH(int, anchor); QFETCH(int, current); - QFETCH(QSet, expectedSelection); + QFETCH(KItemSet, expectedSelection); QFETCH(ChangeType, changeType); QFETCH(QList, data); - QFETCH(QSet, finalSelection); + QFETCH(KItemSet, finalSelection); - QSignalSpy spySelectionChanged(m_selectionManager, SIGNAL(selectionChanged(QSet,QSet))); + QSignalSpy spySelectionChanged(m_selectionManager, SIGNAL(selectionChanged(KItemSet,KItemSet))); // Initial selection should be empty QVERIFY(!m_selectionManager->hasSelection()); @@ -443,7 +443,7 @@ void KItemListSelectionManagerTest::testChangeSelection() // Perform the initial selectiion m_selectionManager->setSelectedItems(initialSelection); - verifySelectionChange(spySelectionChanged, initialSelection, QSet()); + verifySelectionChange(spySelectionChanged, initialSelection, KItemSet()); // Perform an anchored selection. // Note that current and anchor index are equal first because this is the case in typical uses of the @@ -486,7 +486,7 @@ void KItemListSelectionManagerTest::testChangeSelection() // Finally, clear the selection m_selectionManager->clearSelection(); - verifySelectionChange(spySelectionChanged, QSet(), finalSelection); + verifySelectionChange(spySelectionChanged, KItemSet(), finalSelection); } void KItemListSelectionManagerTest::testDeleteCurrentItem_data() @@ -520,8 +520,8 @@ void KItemListSelectionManagerTest::testDeleteCurrentItem() } void KItemListSelectionManagerTest::verifySelectionChange(QSignalSpy& spy, - const QSet& currentSelection, - const QSet& previousSelection) const + const KItemSet& currentSelection, + const KItemSet& previousSelection) const { QCOMPARE(m_selectionManager->selectedItems(), currentSelection); QCOMPARE(m_selectionManager->hasSelection(), !currentSelection.isEmpty()); @@ -540,8 +540,8 @@ void KItemListSelectionManagerTest::verifySelectionChange(QSignalSpy& spy, else { QCOMPARE(spy.count(), 1); QList arguments = spy.takeFirst(); - QCOMPARE(qvariant_cast >(arguments.at(0)), currentSelection); - QCOMPARE(qvariant_cast >(arguments.at(1)), previousSelection); + QCOMPARE(qvariant_cast(arguments.at(0)), currentSelection); + QCOMPARE(qvariant_cast(arguments.at(1)), previousSelection); } } diff --git a/src/tests/kitemsettest.cpp b/src/tests/kitemsettest.cpp new file mode 100644 index 000000000..2832596ba --- /dev/null +++ b/src/tests/kitemsettest.cpp @@ -0,0 +1,612 @@ +/*************************************************************************** + * Copyright (C) 2013 by Frank Reininghaus * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU General Public License as published by * + * the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * + ***************************************************************************/ + +#include + +#include "kitemviews/kitemset.h" + +#include + +Q_DECLARE_METATYPE(KItemRangeList); + +/** + * Converts a KItemRangeList to a KItemSet. + */ +KItemSet KItemRangeList2KItemSet(const KItemRangeList& itemRanges) +{ + KItemSet result; + foreach (const KItemRange& range, itemRanges) { + for (int i = range.index; i < range.index + range.count; ++i) { + result.insert(i); + } + } + return result; +} + +/** + * Converts a KItemRangeList to a QSet. + */ +QSet KItemRangeList2QSet(const KItemRangeList& itemRanges) +{ + QSet result; + foreach (const KItemRange& range, itemRanges) { + for (int i = range.index; i < range.index + range.count; ++i) { + result.insert(i); + } + } + return result; +} + +/** + * Converts a KItemRangeList to a QVector. + */ +QVector KItemRangeList2QVector(const KItemRangeList& itemRanges) +{ + QVector result; + foreach (const KItemRange& range, itemRanges) { + for (int i = range.index; i < range.index + range.count; ++i) { + result.append(i); + } + } + return result; +} + +/** + * Converts a KItemSet to a QSet. + */ +static QSet KItemSet2QSet(const KItemSet& itemSet) +{ + QSet result; + foreach (int i, itemSet) { + result.insert(i); + } + + // Check that the conversion was successful. + Q_ASSERT(itemSet.count() == result.count()); + + foreach (int i, itemSet) { + Q_ASSERT(result.contains(i)); + } + + foreach (int i, result) { + Q_ASSERT(itemSet.contains(i)); + } + + return result; +} + + +/** + * The main test class. + */ +class KItemSetTest : public QObject +{ + Q_OBJECT + +private slots: + void initTestCase(); + + void testConstruction_data(); + void testConstruction(); + void testIterators_data(); + void testIterators(); + void testFind_data(); + void testFind(); + void testChangingOneItem_data(); + void testChangingOneItem(); + void testAddSets_data(); + void testAddSets(); + /* + void testSubtractSets_data(); + void testSubtractSets(); + */ + void testSymmetricDifference_data(); + void testSymmetricDifference(); + +private: + QHash m_testCases; +}; + +void KItemSetTest::initTestCase() +{ + m_testCases.insert("empty", KItemRangeList()); + m_testCases.insert("[0]", KItemRangeList() << KItemRange(0, 1)); + m_testCases.insert("[1]", KItemRangeList() << KItemRange(1, 1)); + m_testCases.insert("[1, 2]", KItemRangeList() << KItemRange(1, 2)); + m_testCases.insert("[1, 2] [5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(5, 1)); + m_testCases.insert("[1] [4, 5]", KItemRangeList() << KItemRange(1, 1) << KItemRange(4, 2)); + m_testCases.insert("[1, 2] [4, 5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2)); + m_testCases.insert("[1, 5]", KItemRangeList() << KItemRange(1, 5)); + m_testCases.insert("[1, 2] [4, 5] [7] [9, 10] [13] [20, 25] [30]", + KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2) << KItemRange(7, 1) << KItemRange(9, 2) << KItemRange(20, 6) << KItemRange(30, 1)); + m_testCases.insert("[-10, -1]", KItemRangeList() << KItemRange(-10, 10)); + m_testCases.insert("[-10, 0]", KItemRangeList() << KItemRange(-10, 11)); + m_testCases.insert("[-10, 1]", KItemRangeList() << KItemRange(-10, 12)); + m_testCases.insert("[0, 9]", KItemRangeList() << KItemRange(0, 10)); + m_testCases.insert("[0, 19]", KItemRangeList() << KItemRange(0, 10)); +} + +void KItemSetTest::testConstruction_data() +{ + QTest::addColumn("itemRanges"); + + QHash::const_iterator it = m_testCases.constBegin(); + const QHash::const_iterator end = m_testCases.constEnd(); + + while (it != end) { + QTest::newRow(it.key()) << it.value(); + ++it; + } +} + +void KItemSetTest::testConstruction() +{ + QFETCH(KItemRangeList, itemRanges); + + KItemSet itemSet = KItemRangeList2KItemSet(itemRanges); + QSet itemsQSet = KItemRangeList2QSet(itemRanges); + + QVERIFY(itemSet.isValid()); + QVERIFY(itemSet.count() == itemsQSet.count()); + QCOMPARE(KItemSet2QSet(itemSet), itemsQSet); + + // Test copy constructor. + KItemSet copy(itemSet); + QCOMPARE(itemSet, copy); + copy.clear(); + QVERIFY(itemSet != copy || itemSet.isEmpty()); + + // Clear the set. + itemSet.clear(); + QVERIFY(itemSet.isEmpty()); + QCOMPARE(itemSet.count(), 0); +} + +void KItemSetTest::testIterators_data() +{ + QTest::addColumn("itemRanges"); + + QHash::const_iterator it = m_testCases.constBegin(); + const QHash::const_iterator end = m_testCases.constEnd(); + + while (it != end) { + QTest::newRow(it.key()) << it.value(); + ++it; + } +} + +/** + * Verify that the iterators work exactly like their counterparts for the + * equivalent QVector. + */ +void KItemSetTest::testIterators() +{ + QFETCH(KItemRangeList, itemRanges); + + KItemSet itemSet = KItemRangeList2KItemSet(itemRanges); + QVector itemsQVector = KItemRangeList2QVector(itemRanges); + + QVERIFY(itemSet.isValid()); + QVERIFY(itemSet.count() == itemsQVector.count()); + + if (itemSet.count() == 0) { + QVERIFY(itemSet.isEmpty()); + QVERIFY(itemSet.begin() == itemSet.end()); + QVERIFY(itemSet.constBegin() == itemSet.constEnd()); + } else { + QVERIFY(!itemSet.isEmpty()); + QVERIFY(itemSet.begin() != itemSet.end()); + QVERIFY(itemSet.constBegin() != itemSet.constEnd()); + + const int min = itemsQVector.first(); + const int max = itemsQVector.last(); + + QCOMPARE(*itemSet.begin(), min); + QCOMPARE(*itemSet.constBegin(), min); + QCOMPARE(itemSet.first(), min); + + QCOMPARE(*(--itemSet.end()), max); + QCOMPARE(*(--itemSet.constEnd()), max); + QCOMPARE(itemSet.last(), max); + } + + // Test iterating using the different iterators. + QVector testQVector; + for (KItemSet::iterator it = itemSet.begin(), end = itemSet.end(); it != end; ++it) { + testQVector.append(*it); + } + QCOMPARE(testQVector, itemsQVector); + + testQVector.clear(); + for (KItemSet::const_iterator it = itemSet.constBegin(), end = itemSet.constEnd(); it != end; ++it) { + testQVector.append(*it); + } + QCOMPARE(testQVector, itemsQVector); + + testQVector.clear(); + foreach (int i, itemSet) { + testQVector.append(i); + } + QCOMPARE(testQVector, itemsQVector); + + // Verify that both variants of the (const)iterator's operator++ and + // operator-- functions behave exactly like their QVector equivalents. + KItemSet::iterator it1 = itemSet.begin(); + KItemSet::iterator it2 = itemSet.begin(); + KItemSet::const_iterator constIt1 = itemSet.constBegin(); + KItemSet::const_iterator constIt2 = itemSet.constBegin(); + QVector::iterator vectorIt1 = itemsQVector.begin(); + QVector::iterator vectorIt2 = itemsQVector.begin(); + QVector::const_iterator vectorConstIt1 = itemsQVector.constBegin(); + QVector::const_iterator vectorConstIt2 = itemsQVector.constBegin(); + + while (it1 != itemSet.end()) { + if (it1 != --itemSet.end()) { + QCOMPARE(*(++it1), *(++vectorIt1)); + QCOMPARE(*(++constIt1), *(++vectorConstIt1)); + } else { + QCOMPARE(++it1, itemSet.end()); + QCOMPARE(++vectorIt1, itemsQVector.end()); + QCOMPARE(++constIt1, itemSet.constEnd()); + QCOMPARE(++vectorConstIt1, itemsQVector.constEnd()); + } + + QCOMPARE(*(it2++), *(vectorIt2++)); + QCOMPARE(*(constIt2++), *(vectorConstIt2++)); + + QCOMPARE(it1, it2); + QCOMPARE(constIt1, constIt2); + QCOMPARE(KItemSet::const_iterator(it1), constIt1); + } + + QCOMPARE(it1, itemSet.end()); + QCOMPARE(it2, itemSet.end()); + QCOMPARE(constIt1, itemSet.constEnd()); + QCOMPARE(constIt2, itemSet.constEnd()); + QCOMPARE(vectorIt1, itemsQVector.end()); + QCOMPARE(vectorIt2, itemsQVector.end()); + QCOMPARE(vectorConstIt1, itemsQVector.constEnd()); + QCOMPARE(vectorConstIt2, itemsQVector.constEnd()); + + while (it1 != itemSet.begin()) { + QCOMPARE(*(--it1), *(--vectorIt1)); + QCOMPARE(*(--constIt1), *(--vectorConstIt1)); + + if (it2 != itemSet.end()) { + QCOMPARE(*(it2--), *(vectorIt2--)); + QCOMPARE(*(constIt2--), *(vectorConstIt2--)); + } else { + QCOMPARE(it2--, itemSet.end()); + QCOMPARE(vectorIt2--, itemsQVector.end()); + QCOMPARE(constIt2--, itemSet.constEnd()); + QCOMPARE(vectorConstIt2--, itemsQVector.constEnd()); + } + + QCOMPARE(it1, it2); + QCOMPARE(constIt1, constIt2); + QCOMPARE(KItemSet::const_iterator(it1), constIt1); + } + + QCOMPARE(it1, itemSet.begin()); + QCOMPARE(it2, itemSet.begin()); + QCOMPARE(constIt1, itemSet.constBegin()); + QCOMPARE(constIt2, itemSet.constBegin()); + QCOMPARE(vectorIt1, itemsQVector.begin()); + QCOMPARE(vectorIt2, itemsQVector.begin()); + QCOMPARE(vectorConstIt1, itemsQVector.constBegin()); + QCOMPARE(vectorConstIt2, itemsQVector.constBegin()); +} + +void KItemSetTest::testFind_data() +{ + QTest::addColumn("itemRanges"); + + QHash::const_iterator it = m_testCases.constBegin(); + const QHash::const_iterator end = m_testCases.constEnd(); + + while (it != end) { + QTest::newRow(it.key()) << it.value(); + ++it; + } +} + +/** + * Test all functions that find items: + * contais(int), find(int), constFind(int) + */ +void KItemSetTest::testFind() +{ + QFETCH(KItemRangeList, itemRanges); + + KItemSet itemSet = KItemRangeList2KItemSet(itemRanges); + QSet itemsQSet = KItemRangeList2QSet(itemRanges); + + QVERIFY(itemSet.isValid()); + QVERIFY(itemSet.count() == itemsQSet.count()); + + // Find the minimum and maximum items. + int min; + int max; + + if (itemSet.count() == 0) { + // Use some arbitrary values for the upcoming tests. + min = 0; + max = 5; + } else { + min = *itemSet.begin(); + max = *(--itemSet.end()); + } + + // Test contains(int), find(int), and constFind(int) + // for items between min - 2 and max + 2. + for (int i = min - 2; i <= max + 2; ++i) { + const KItemSet::iterator it = itemSet.find(i); + const KItemSet::const_iterator constIt = itemSet.constFind(i); + QCOMPARE(KItemSet::const_iterator(it), constIt); + + if (itemsQSet.contains(i)) { + QVERIFY(itemSet.contains(i)); + QCOMPARE(*it, i); + QCOMPARE(*constIt, i); + } else { + QVERIFY(!itemSet.contains(i)); + QCOMPARE(it, itemSet.end()); + QCOMPARE(constIt, itemSet.constEnd()); + } + } +} + +void KItemSetTest::testChangingOneItem_data() +{ + QTest::addColumn("itemRanges"); + + QHash::const_iterator it = m_testCases.constBegin(); + const QHash::const_iterator end = m_testCases.constEnd(); + + while (it != end) { + QTest::newRow(it.key()) << it.value(); + ++it; + } +} + +/** + * Test all functions that change a single item: + * insert(int), remove(int), erase(KItemSet::iterator) + */ +void KItemSetTest::testChangingOneItem() +{ + QFETCH(KItemRangeList, itemRanges); + + KItemSet itemSet = KItemRangeList2KItemSet(itemRanges); + QSet itemsQSet = KItemRangeList2QSet(itemRanges); + + QVERIFY(itemSet.isValid()); + QVERIFY(itemSet.count() == itemsQSet.count()); + + // Find the minimum and maximum items. + int min; + int max; + + if (itemSet.count() == 0) { + // Use some arbitrary values for the upcoming tests. + min = 0; + max = 5; + } else { + min = *itemSet.begin(); + max = *(--itemSet.end()); + } + + // Test insert(int), remove(int), and erase(KItemSet::iterator) + // for items between min - 2 and max + 2. + for (int i = min - 2; i <= max + 2; ++i) { + + // Test insert(int). + { + KItemSet tmp(itemSet); + const KItemSet::iterator insertedIt = tmp.insert(i); + QCOMPARE(*insertedIt, i); + + QVERIFY(tmp.isValid()); + QVERIFY(tmp.contains(i)); + + QSet expectedQSet = itemsQSet; + expectedQSet.insert(i); + QCOMPARE(KItemSet2QSet(tmp), expectedQSet); + + if (!itemSet.contains(i)) { + QVERIFY(itemSet != tmp); + QCOMPARE(tmp.count(), itemSet.count() + 1); + } else { + QCOMPARE(itemSet, tmp); + } + + QCOMPARE(i, *tmp.find(i)); + QCOMPARE(i, *tmp.constFind(i)); + + // Erase the new item and check that we get the old KItemSet back. + tmp.erase(tmp.find(i)); + QVERIFY(tmp.isValid()); + QVERIFY(!tmp.contains(i)); + + if (!itemSet.contains(i)) { + QCOMPARE(itemSet, tmp); + } + + expectedQSet.remove(i); + QCOMPARE(KItemSet2QSet(tmp), expectedQSet); + } + + // Test remove(int). + { + KItemSet tmp(itemSet); + const bool removed = tmp.remove(i); + + QCOMPARE(removed, itemSet.contains(i)); + + QVERIFY(tmp.isValid()); + QVERIFY(!tmp.contains(i)); + + QSet expectedQSet = itemsQSet; + expectedQSet.remove(i); + QCOMPARE(KItemSet2QSet(tmp), expectedQSet); + + if (itemSet.contains(i)) { + QVERIFY(itemSet != tmp); + QCOMPARE(tmp.count(), itemSet.count() - 1); + } else { + QCOMPARE(itemSet, tmp); + } + + QCOMPARE(tmp.end(), tmp.find(i)); + QCOMPARE(tmp.constEnd(), tmp.constFind(i)); + } + + // Test erase(KItemSet::iterator). + if (itemSet.contains(i)) { + KItemSet tmp(itemSet); + KItemSet::iterator it = tmp.find(i); + it = tmp.erase(it); + + QVERIFY(tmp.isValid()); + QVERIFY(!tmp.contains(i)); + + QSet expectedQSet = itemsQSet; + expectedQSet.remove(i); + QCOMPARE(KItemSet2QSet(tmp), expectedQSet); + + if (itemSet.contains(i)) { + QVERIFY(itemSet != tmp); + QCOMPARE(tmp.count(), itemSet.count() - 1); + } else { + QCOMPARE(itemSet, tmp); + } + + QCOMPARE(tmp.end(), tmp.find(i)); + QCOMPARE(tmp.constEnd(), tmp.constFind(i)); + + // Check the returen value, now contained in 'it'. + if (i == max) { + QCOMPARE(it, tmp.end()); + } else { + // it now points to the next item. + QVERIFY(tmp.contains(*it)); + for (int j = i; j < *it; ++j) { + QVERIFY(!tmp.contains(j)); + } + } + } + } + + // Clear the set. + itemSet.clear(); + QVERIFY(itemSet.isEmpty()); + QCOMPARE(itemSet.count(), 0); +} + +void KItemSetTest::testAddSets_data() +{ + QTest::addColumn("itemRanges1"); + QTest::addColumn("itemRanges2"); + + QHash::const_iterator it1 = m_testCases.constBegin(); + const QHash::const_iterator end = m_testCases.constEnd(); + + while (it1 != end) { + QHash::const_iterator it2 = m_testCases.constBegin(); + + while (it2 != end) { + QByteArray name = it1.key() + QByteArray(" + ") + it2.key(); + QTest::newRow(name) << it1.value() << it2.value(); + ++it2; + } + + ++it1; + } +} + +void KItemSetTest::testAddSets() +{ + QFETCH(KItemRangeList, itemRanges1); + QFETCH(KItemRangeList, itemRanges2); + + KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1); + QSet itemsQSet1 = KItemRangeList2QSet(itemRanges1); + + KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2); + QSet itemsQSet2 = KItemRangeList2QSet(itemRanges2); + + KItemSet sum = itemSet1 + itemSet2; + QSet sumQSet = itemsQSet1 + itemsQSet2; + + QCOMPARE(sum.count(), sumQSet.count()); + QCOMPARE(KItemSet2QSet(sum), sumQSet); +} + +void KItemSetTest::testSymmetricDifference_data() +{ + QTest::addColumn("itemRanges1"); + QTest::addColumn("itemRanges2"); + + QHash::const_iterator it1 = m_testCases.constBegin(); + const QHash::const_iterator end = m_testCases.constEnd(); + + while (it1 != end) { + QHash::const_iterator it2 = m_testCases.constBegin(); + + while (it2 != end) { + QByteArray name = it1.key() + QByteArray(" ^ ") + it2.key(); + QTest::newRow(name) << it1.value() << it2.value(); + ++it2; + } + + ++it1; + } +} + +void KItemSetTest::testSymmetricDifference() +{ + QFETCH(KItemRangeList, itemRanges1); + QFETCH(KItemRangeList, itemRanges2); + + KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1); + QSet itemsQSet1 = KItemRangeList2QSet(itemRanges1); + + KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2); + QSet itemsQSet2 = KItemRangeList2QSet(itemRanges2); + + KItemSet symmetricDifference = itemSet1 ^ itemSet2; + QSet symmetricDifferenceQSet = (itemsQSet1 - itemsQSet2) + (itemsQSet2 - itemsQSet1); + + QCOMPARE(symmetricDifference.count(), symmetricDifferenceQSet.count()); + QCOMPARE(KItemSet2QSet(symmetricDifference), symmetricDifferenceQSet); + + // Check commutativity. + QCOMPARE(itemSet2 ^ itemSet1, symmetricDifference); + + // Some more checks: + // itemSet1 ^ symmetricDifference == itemSet2, + // itemSet2 ^ symmetricDifference == itemSet1. + QCOMPARE(itemSet1 ^ symmetricDifference, itemSet2); + QCOMPARE(itemSet2 ^ symmetricDifference, itemSet1); +} + + +QTEST_KDEMAIN(KItemSetTest, NoGUI) + +#include "kitemsettest.moc" -- cgit v1.3