diff options
author | Mikhail Svetkin <mikhail.svetkin@qt.io> | 2018-05-29 14:13:59 +0200 |
---|---|---|
committer | Simon Hausmann <simon.hausmann@qt.io> | 2018-07-25 06:57:44 +0000 |
commit | d1dcc4d8cdc36520dcc6cda4ad02eca8607f7b79 (patch) | |
tree | 48a3c0814c2d2e25c9ecb937f33a150ecb54c25f | |
parent | 80dea66424c4887f66f64ea1920ab460f27b78af (diff) |
corelib/tools: add qMakeArray() API
This function can be used to create std::array without the need
to explicitly provide the size of array. It also has a specialization
that allow to generate sorted array at compile time. Sorted array can
be beneficial for example in binary search.
Change-Id: Ifc7e06e451812fce2ab94293959db5e9cc038793
Reviewed-by: Gatis Paeglis <gatis.paeglis@qt.io>
-rw-r--r-- | src/corelib/tools/qmakearray_p.h | 179 | ||||
-rw-r--r-- | src/corelib/tools/tools.pri | 1 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qmakearray/qmakearray.pro | 4 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qmakearray/tst_qmakearray.cpp | 103 | ||||
-rw-r--r-- | tests/auto/corelib/tools/tools.pro | 1 |
5 files changed, 288 insertions, 0 deletions
diff --git a/src/corelib/tools/qmakearray_p.h b/src/corelib/tools/qmakearray_p.h new file mode 100644 index 0000000000..ae4d7f07c6 --- /dev/null +++ b/src/corelib/tools/qmakearray_p.h @@ -0,0 +1,179 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QMAKEARRAY_P_H +#define QMAKEARRAY_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include "QtCore/qglobal.h" + +#include <array> +#include <type_traits> +#include <utility> + +QT_BEGIN_NAMESPACE + +namespace QtPrivate { +template<typename T> +constexpr T&& Forward(typename std::remove_reference<T>::type& t) noexcept +{ + return static_cast<T&&>(t); +} + +template<typename T> +constexpr T&& Forward(typename std::remove_reference<T>::type&& t) noexcept +{ + static_assert(!std::is_lvalue_reference<T>::value, + "template argument substituting T is an lvalue reference type"); + return static_cast<T&&>(t); +} + +template <typename ManualType, typename ...> +struct ArrayTypeHelper +{ + using type = ManualType; +}; + +template <typename ... Types> +struct ArrayTypeHelper<void, Types...> : std::common_type<Types...> { }; + +template <typename ManualType, typename... Types> +using ArrayType = std::array<typename ArrayTypeHelper<ManualType, Types...>::type, + sizeof...(Types)>; + +template<typename ... Values> +struct QuickSortData { }; + +template <template <typename> class Predicate, + typename ... Values> +struct QuickSortFilter; + +template <typename ... Right, typename ... Left> +constexpr QuickSortData<Right..., Left...> quickSortConcat( + QuickSortData<Right...>, QuickSortData<Left...>) noexcept; + +template<typename ... Right, typename Middle, typename ... Left> +constexpr QuickSortData<Right..., Middle, Left...> quickSortConcat( + QuickSortData<Right...>, + QuickSortData<Middle>, + QuickSortData<Left...>) noexcept; + +template <template <typename> class Predicate, + typename Head, typename ... Tail> +struct QuickSortFilter<Predicate, QuickSortData<Head, Tail...>> +{ + using TailFilteredData = typename QuickSortFilter< + Predicate, QuickSortData<Tail...>>::Type; + + using Type = typename QConditional< + Predicate<Head>::value, + decltype(quickSortConcat(QuickSortData<Head> {}, TailFilteredData{})), + TailFilteredData>::Type; +}; + +template <template <typename> class Predicate> +struct QuickSortFilter<Predicate, QuickSortData<>> +{ + using Type = QuickSortData<>; +}; + +template <typename ... Values> +struct QuickSort; + +template <typename Pivot, typename ... Values> +struct QuickSort<QuickSortData<Pivot, Values...>> +{ + template <typename Left> + struct LessThan { + static constexpr const bool value = Left::data() <= Pivot::data(); + }; + + template <typename Left> + struct MoreThan { + static constexpr const bool value = !(Left::data() <= Pivot::data()); + }; + + using LeftSide = typename QuickSortFilter<LessThan, QuickSortData<Values...>>::Type; + using RightSide = typename QuickSortFilter<MoreThan, QuickSortData<Values...>>::Type; + + using LeftQS = typename QuickSort<LeftSide>::Type; + using RightQS = typename QuickSort<RightSide>::Type; + + using Type = decltype(quickSortConcat(LeftQS{}, QuickSortData<Pivot> {}, RightQS{})); + +}; + +template <> +struct QuickSort<QuickSortData<>> +{ + using Type = QuickSortData<>; +}; +} // namespace QtPrivate + +template <typename ManualType = void, typename ... Types> +constexpr QtPrivate::ArrayType<ManualType, Types...> qMakeArray(Types && ... t) noexcept +{ + return {{QtPrivate::Forward<typename QtPrivate::ArrayType<ManualType, Types...>::value_type>(t)...}}; +} + +template<typename ... Values> +struct QSortedData { + using Data = typename QtPrivate::QuickSort<typename QtPrivate::QuickSortData<Values...>>::Type; +}; + +template<typename ... Values> +constexpr auto qMakeArray(QtPrivate::QuickSortData<Values...>) noexcept -> decltype(qMakeArray(Values::data()...)) +{ + return qMakeArray(Values::data() ...); +} + + +QT_END_NAMESPACE + +#endif // QMAKEARRAY_P_H diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri index 4f2d3dd4a3..7a74dfda3e 100644 --- a/src/corelib/tools/tools.pri +++ b/src/corelib/tools/tools.pri @@ -34,6 +34,7 @@ HEADERS += \ tools/qlocale_p.h \ tools/qlocale_tools_p.h \ tools/qlocale_data_p.h \ + tools/qmakearray_p.h \ tools/qmap.h \ tools/qmargins.h \ tools/qmessageauthenticationcode.h \ diff --git a/tests/auto/corelib/tools/qmakearray/qmakearray.pro b/tests/auto/corelib/tools/qmakearray/qmakearray.pro new file mode 100644 index 0000000000..abb3d9fdbc --- /dev/null +++ b/tests/auto/corelib/tools/qmakearray/qmakearray.pro @@ -0,0 +1,4 @@ +CONFIG += testcase +TARGET = tst_qmakearray +QT = core testlib core-private +SOURCES = $$PWD/tst_qmakearray.cpp diff --git a/tests/auto/corelib/tools/qmakearray/tst_qmakearray.cpp b/tests/auto/corelib/tools/qmakearray/tst_qmakearray.cpp new file mode 100644 index 0000000000..e0d3f52719 --- /dev/null +++ b/tests/auto/corelib/tools/qmakearray/tst_qmakearray.cpp @@ -0,0 +1,103 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the test suite of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:GPL-EXCEPT$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3 as published by the Free Software +** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtTest/QtTest> + +#include <private/qmakearray_p.h> + + +class tst_QMakeArray : public QObject +{ + Q_OBJECT + +private slots: + void quicksort(); +}; + +struct Pair { + unsigned int key; + unsigned int val; + + constexpr bool operator <=(const Pair &that) const noexcept + { + return key <= that.key; + } + + constexpr bool operator<(const Pair &that) const noexcept + { + return key < that.key; + } + + constexpr bool operator==(const Pair &that) const noexcept + { + return key == that.key; + } +}; + +template<std::size_t Key, std::size_t Val> +struct PairQuickSortElem +{ + using Type = Pair; + static constexpr Type data() noexcept { return Type{Key, Val}; } +}; + +void tst_QMakeArray::quicksort() +{ + constexpr const auto sorted_array = qMakeArray( + QSortedData< + PairQuickSortElem<10, 0>, + PairQuickSortElem<5, 0>, + PairQuickSortElem<7, 0>, + PairQuickSortElem<1, 0>, + PairQuickSortElem<8, 0>, + PairQuickSortElem<6, 0>, + PairQuickSortElem<4, 0>, + PairQuickSortElem<3, 0>, + PairQuickSortElem<1, 0>, + PairQuickSortElem<2, 0>, + PairQuickSortElem<10, 0>, + PairQuickSortElem<5, 0> + >::Data{}); + static_assert(sorted_array.size() == 12, "sorted_array.size() != 12"); + QCOMPARE(sorted_array[0].key, 1u); + QCOMPARE(sorted_array[1].key, 1u); + QCOMPARE(sorted_array[2].key, 2u); + QCOMPARE(sorted_array[3].key, 3u); + QCOMPARE(sorted_array[4].key, 4u); + QCOMPARE(sorted_array[5].key, 5u); + QCOMPARE(sorted_array[6].key, 5u); + QCOMPARE(sorted_array[7].key, 6u); + QCOMPARE(sorted_array[8].key, 7u); + QCOMPARE(sorted_array[9].key, 8u); + QCOMPARE(sorted_array[10].key, 10u); + QCOMPARE(sorted_array[11].key, 10u); +} + + +QTEST_APPLESS_MAIN(tst_QMakeArray) +#include "tst_qmakearray.moc" diff --git a/tests/auto/corelib/tools/tools.pro b/tests/auto/corelib/tools/tools.pro index f35ed026ac..f28cf21b8b 100644 --- a/tests/auto/corelib/tools/tools.pro +++ b/tests/auto/corelib/tools/tools.pro @@ -30,6 +30,7 @@ SUBDIRS=\ qlist \ qlist_strictiterators \ qlocale \ + qmakearray \ qmap \ qmap_strictiterators \ qmargins \ |