diff options
-rw-r--r-- | src/corelib/tools/qflatmap_p.h | 982 | ||||
-rw-r--r-- | src/corelib/tools/tools.pri | 1 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qflatmap/qflatmap.pro | 4 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp | 453 | ||||
-rw-r--r-- | tests/auto/corelib/tools/tools.pro | 1 |
5 files changed, 1441 insertions, 0 deletions
diff --git a/src/corelib/tools/qflatmap_p.h b/src/corelib/tools/qflatmap_p.h new file mode 100644 index 0000000000..590b0d942f --- /dev/null +++ b/src/corelib/tools/qflatmap_p.h @@ -0,0 +1,982 @@ +/**************************************************************************** +** +** Copyright (C) 2020 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 QFLATMAP_P_H +#define QFLATMAP_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of a number of Qt sources files. This header file may change from +// version to version without notice, or even be removed. +// +// We mean it. +// + +#include "qvector.h" + +#include <algorithm> +#include <functional> +#include <initializer_list> +#include <iterator> +#include <numeric> +#include <type_traits> +#include <utility> + +QT_BEGIN_NAMESPACE + +/* + QFlatMap provides an associative container backed by sorted sequential + containers. By default, QVector is used. + + Keys and values are stored in two separate containers. This provides improved + cache locality for key iteration and makes keys() and values() fast + operations. + + One can customize the underlying container type by passing the KeyContainer + and MappedContainer template arguments: + QFlatMap<float, int, std::less<float>, std::vector<float>, std::vector<int>> +*/ + +namespace Qt { + +struct OrderedUniqueRange_t {}; +constexpr OrderedUniqueRange_t OrderedUniqueRange = {}; + +} // namespace Qt + +template <class Key, class T, class Compare> +class QFlatMapValueCompare : protected Compare +{ +public: + QFlatMapValueCompare() = default; + QFlatMapValueCompare(const Compare &key_compare) + : Compare(key_compare) + { + } + + using value_type = std::pair<const Key, T>; + static constexpr bool is_comparator_noexcept = noexcept( + std::declval<Compare>()(std::declval<Key>(), std::declval<Key>())); + + bool operator()(const value_type &lhs, const value_type &rhs) const + noexcept(is_comparator_noexcept) + { + return Compare::operator()(lhs.first, rhs.first); + } +}; + +template <class Key, class T, + class Compare = std::less<Key>, + class KeyContainer = QVector<Key>, + class MappedContainer = QVector<T>> +class QFlatMap : private QFlatMapValueCompare<Key, T, Compare> +{ + using full_map_t = QFlatMap<Key, T, Compare, KeyContainer, MappedContainer>; + + template <class U> + class mock_pointer + { + U ref; + public: + mock_pointer(U r) + : ref(r) + { + } + + U *operator->() + { + return &ref; + } + }; + +public: + using key_type = Key; + using mapped_type = T; + using value_compare = QFlatMapValueCompare<Key, T, Compare>; + using value_type = typename value_compare::value_type; + using key_container_type = KeyContainer; + using mapped_container_type = MappedContainer; + using size_type = typename key_container_type::size_type; + using key_compare = Compare; + + struct containers + { + key_container_type keys; + mapped_container_type values; + }; + + class iterator + { + public: + using difference_type = ptrdiff_t; + using value_type = std::pair<const Key, T>; + using reference = std::pair<const Key &, T &>; + using pointer = mock_pointer<reference>; + using iterator_category = std::random_access_iterator_tag; + + iterator() = default; + + iterator(containers *ac, size_type ai) + : c(ac), i(ai) + { + } + + reference operator*() + { + return { c->keys[i], c->values[i] }; + } + + pointer operator->() + { + return { operator*() }; + } + + bool operator==(const iterator &o) const + { + return c == o.c && i == o.i; + } + + bool operator!=(const iterator &o) const + { + return !operator==(o); + } + + iterator &operator++() + { + ++i; + return *this; + } + + iterator operator++(int) + { + + iterator r = *this; + i++; + return r; + } + + iterator &operator--() + { + --i; + return *this; + } + + iterator operator--(int) + { + iterator r = *this; + i--; + return r; + } + + iterator &operator+=(size_type n) + { + i += n; + return *this; + } + + friend iterator operator+(size_type n, const iterator a) + { + iterator ret = a; + return ret += n; + } + + friend iterator operator+(const iterator a, size_type n) + { + return n + a; + } + + iterator &operator-=(size_type n) + { + i -= n; + return *this; + } + + friend iterator operator-(const iterator a, size_type n) + { + iterator ret = a; + return ret -= n; + } + + friend difference_type operator-(const iterator b, const iterator a) + { + return b.i - a.i; + } + + reference operator[](size_type n) + { + size_type k = i + n; + return { c->keys[k], c->values[k] }; + } + + bool operator<(const iterator &other) const + { + return i < other.i; + } + + bool operator>(const iterator &other) const + { + return i > other.i; + } + + bool operator<=(const iterator &other) const + { + return i <= other.i; + } + + bool operator>=(const iterator &other) const + { + return i >= other.i; + } + + const Key &key() const { return c->keys[i]; } + T &value() { return c->values[i]; } + + private: + containers *c = nullptr; + size_type i = 0; + friend full_map_t; + }; + + class const_iterator + { + public: + using difference_type = ptrdiff_t; + using value_type = std::pair<const Key, const T>; + using reference = std::pair<const Key &, const T &>; + using pointer = mock_pointer<reference>; + using iterator_category = std::random_access_iterator_tag; + + const_iterator() = default; + + const_iterator(const containers *ac, size_type ai) + : c(ac), i(ai) + { + } + + const_iterator(iterator o) + : c(o.c), i(o.i) + { + } + + reference operator*() + { + return { c->keys[i], c->values[i] }; + } + + pointer operator->() + { + return { operator*() }; + } + + bool operator==(const const_iterator &o) const + { + return c == o.c && i == o.i; + } + + bool operator!=(const const_iterator &o) const + { + return !operator==(o); + } + + const_iterator &operator++() + { + ++i; + return *this; + } + + const_iterator operator++(int) + { + + const_iterator r = *this; + i++; + return r; + } + + const_iterator &operator--() + { + --i; + return *this; + } + + const_iterator operator--(int) + { + const_iterator r = *this; + i--; + return r; + } + + const_iterator &operator+=(size_type n) + { + i += n; + return *this; + } + + friend const_iterator operator+(size_type n, const const_iterator a) + { + const_iterator ret = a; + return ret += n; + } + + friend const_iterator operator+(const const_iterator a, size_type n) + { + return n + a; + } + + const_iterator &operator-=(size_type n) + { + i -= n; + return *this; + } + + friend const_iterator operator-(const const_iterator a, size_type n) + { + const_iterator ret = a; + return ret -= n; + } + + friend difference_type operator-(const const_iterator b, const const_iterator a) + { + return b.i - a.i; + } + + reference operator[](size_type n) + { + size_type k = i + n; + return { c->keys[k], c->values[k] }; + } + + bool operator<(const const_iterator &other) const + { + return i < other.i; + } + + bool operator>(const const_iterator &other) const + { + return i > other.i; + } + + bool operator<=(const const_iterator &other) const + { + return i <= other.i; + } + + bool operator>=(const const_iterator &other) const + { + return i >= other.i; + } + + const Key &key() const { return c->keys[i]; } + const T &value() { return c->values[i]; } + + private: + const containers *c = nullptr; + size_type i = 0; + friend full_map_t; + }; + +private: + template <class, class = void> + struct is_marked_transparent_type : std::false_type { }; + + template <class X> + struct is_marked_transparent_type<X, typename X::is_transparent> : std::true_type { }; + + template <class X> + using is_marked_transparent = typename std::enable_if< + is_marked_transparent_type<X>::value>::type *; + + template <typename It> + using is_compatible_iterator = typename std::enable_if< + std::is_same<value_type, typename std::iterator_traits<It>::value_type>::value>::type *; + +public: + QFlatMap() = default; + + explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values) + : c{keys, values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values) + { + c.keys = std::move(keys); + c.values = values; + ensureOrderedUnique(); + } + + explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values) + { + c.keys = keys; + c.values = std::move(values); + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values) + { + c.keys = std::move(keys); + c.values = std::move(values); + ensureOrderedUnique(); + } + + explicit QFlatMap(std::initializer_list<value_type> lst) + : QFlatMap(lst.begin(), lst.end()) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(InputIt first, InputIt last) + { + initWithRange(first, last); + ensureOrderedUnique(); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + const mapped_container_type &values) + { + c.keys = keys; + c.values = values; + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + const mapped_container_type &values) + { + c.keys = std::move(keys); + c.values = values; + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + mapped_container_type &&values) + { + c.keys = keys; + c.values = std::move(values); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + mapped_container_type &&values) + { + c.keys = std::move(keys); + c.values = std::move(values); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst) + : QFlatMap(lst.begin(), lst.end()) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last) + { + initWithRange(first, last); + } + + explicit QFlatMap(const Compare &compare) + : value_compare(compare) + { + } + + explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values, + const Compare &compare) + : value_compare(compare), c{keys, values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values, + const Compare &compare) + : value_compare(compare), c{std::move(keys), values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values, + const Compare &compare) + : value_compare(compare), c{keys, std::move(values)} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values, + const Compare &compare) + : value_compare(compare), c{std::move(keys), std::move(values)} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(std::initializer_list<value_type> lst, const Compare &compare) + : QFlatMap(lst.begin(), lst.end(), compare) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(InputIt first, InputIt last, const Compare &compare) + : value_compare(compare) + { + initWithRange(first, last); + ensureOrderedUnique(); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + const mapped_container_type &values, const Compare &compare) + : value_compare(compare), c{keys, values} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + const mapped_container_type &values, const Compare &compare) + : value_compare(compare), c{std::move(keys), values} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + mapped_container_type &&values, const Compare &compare) + : value_compare(compare), c{keys, std::move(values)} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + mapped_container_type &&values, const Compare &compare) + : value_compare(compare), c{std::move(keys), std::move(values)} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst, + const Compare &compare) + : QFlatMap(Qt::OrderedUniqueRange, lst.begin(), lst.end(), compare) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last, const Compare &compare) + : value_compare(compare) + { + initWithRange(first, last); + } + + size_type count() const noexcept { return c.keys.size(); } + size_type size() const noexcept { return c.keys.size(); } + size_type capacity() const noexcept { return c.keys.capacity(); } + bool isEmpty() const noexcept { return c.keys.empty(); } + bool empty() const noexcept { return c.keys.empty(); } + containers extract() && { return std::move(c); } + const key_container_type &keys() const noexcept { return c.keys; } + const mapped_container_type &values() const noexcept { return c.values; } + + void reserve(size_type s) + { + c.keys.reserve(s); + c.values.reserve(s); + } + + void clear() + { + c.keys.clear(); + c.values.clear(); + } + + bool remove(const Key &key) + { + auto it = binary_find(key); + if (it != end()) { + c.keys.erase(toKeysIterator(it)); + c.values.erase(toValuesIterator(it)); + return true; + } + return false; + } + + iterator erase(iterator it) + { + c.values.erase(toValuesIterator(it)); + return fromKeysIterator(c.keys.erase(toKeysIterator(it))); + } + + T take(const Key &key) + { + auto it = binary_find(key); + if (it != end()) { + T result = std::move(it.value()); + erase(it); + return result; + } + return {}; + } + + bool contains(const Key &key) const + { + return binary_find(key) != end(); + } + + T value(const Key &key, const T &defaultValue) const + { + auto it = binary_find(key); + return it == end() ? defaultValue : it.value(); + } + + T value(const Key &key) const + { + auto it = binary_find(key); + return it == end() ? T() : it.value(); + } + + T &operator[](const Key &key) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.keys.insert(toKeysIterator(it), key); + return *c.values.insert(toValuesIterator(it), T()); + } + return it.value(); + } + + T &operator[](Key &&key) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.keys.insert(toKeysIterator(it), key); + return *c.values.insert(toValuesIterator(it), T()); + } + return it.value(); + } + + T operator[](const Key &key) const + { + return value(key); + } + + std::pair<iterator, bool> insert(const Key &key, const T &value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), value); + auto k = c.keys.insert(toKeysIterator(it), key); + return { fromKeysIterator(k), true }; + } else { + it.value() = value; + return {it, false}; + } + } + + std::pair<iterator, bool> insert(Key &&key, const T &value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), value); + return { c.keys.insert(it, std::move(key)), true }; + } else { + *toValuesIterator(it) = value; + return {it, false}; + } + } + + std::pair<iterator, bool> insert(const Key &key, T &&value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), std::move(value)); + return { c.keys.insert(it, key), true }; + } else { + *toValuesIterator(it) = std::move(value); + return {it, false}; + } + } + + std::pair<iterator, bool> insert(Key &&key, T &&value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), std::move(value)); + return { fromKeysIterator(c.keys.insert(toKeysIterator(it), std::move(key))), true }; + } else { + *toValuesIterator(it) = std::move(value); + return {it, false}; + } + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + void insert(InputIt first, InputIt last) + { + insertRange(first, last); + } + + // ### Merge with the templated version above + // once we can use std::disjunction in is_compatible_iterator. + void insert(const value_type *first, const value_type *last) + { + insertRange(first, last); + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + void insert(Qt::OrderedUniqueRange_t, InputIt first, InputIt last) + { + insertOrderedUniqueRange(first, last); + } + + // ### Merge with the templated version above + // once we can use std::disjunction in is_compatible_iterator. + void insert(Qt::OrderedUniqueRange_t, const value_type *first, const value_type *last) + { + insertOrderedUniqueRange(first, last); + } + + iterator begin() { return { &c, 0 }; } + const_iterator begin() const { return { &c, 0 }; } + const_iterator cbegin() const { return begin(); } + const_iterator constBegin() const { return cbegin(); } + iterator end() { return { &c, c.keys.size() }; } + const_iterator end() const { return { &c, c.keys.size() }; } + const_iterator cend() const { return end(); } + const_iterator constEnd() const { return cend(); } + std::reverse_iterator<iterator> rbegin() { return std::reverse_iterator<iterator>(end()); } + std::reverse_iterator<const_iterator> rbegin() const + { + return std::reverse_iterator<const_iterator>(end()); + } + std::reverse_iterator<const_iterator> crbegin() const { return rbegin(); } + std::reverse_iterator<iterator> rend() { + return std::reverse_iterator<iterator>(begin()); + } + std::reverse_iterator<const_iterator> rend() const + { + return std::reverse_iterator<const_iterator>(begin()); + } + std::reverse_iterator<const_iterator> crend() const { return rend(); } + + iterator lower_bound(const Key &key) + { + auto cit = const_cast<const full_map_t *>(this)->lower_bound(key); + return { &c, cit.i }; + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + iterator lower_bound(const X &key) + { + auto cit = const_cast<const full_map_t *>(this)->lower_bound(key); + return { &c, cit.i }; + } + + const_iterator lower_bound(const Key &key) const + { + return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp())); + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + const_iterator lower_bound(const X &key) const + { + return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp())); + } + + iterator find(const key_type &k) + { + return binary_find(k); + } + + const_iterator find(const key_type &k) const + { + return binary_find(k); + } + + key_compare key_comp() const noexcept + { + return static_cast<key_compare>(*this); + } + + value_compare value_comp() const noexcept + { + return static_cast<value_compare>(*this); + } + +private: + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + void initWithRange(InputIt first, InputIt last) + { + QtPrivate::reserveIfForwardIterator(this, first, last); + while (first != last) { + c.keys.push_back(first->first); + c.values.push_back(first->second); + ++first; + } + } + + iterator fromKeysIterator(typename key_container_type::iterator kit) + { + return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) }; + } + + const_iterator fromKeysIterator(typename key_container_type::const_iterator kit) const + { + return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) }; + } + + typename key_container_type::iterator toKeysIterator(iterator it) + { + return c.keys.begin() + it.i; + } + + typename mapped_container_type::iterator toValuesIterator(iterator it) + { + return c.values.begin() + it.i; + } + + template <class InputIt> + void insertRange(InputIt first, InputIt last) + { + size_type i = c.keys.size(); + c.keys.resize(i + std::distance(first, last)); + c.values.resize(c.keys.size()); + for (; first != last; ++first, ++i) { + c.keys[i] = first->first; + c.values[i] = first->second; + } + ensureOrderedUnique(); + } + + class IndexedKeyComparator + { + public: + IndexedKeyComparator(const full_map_t *am) + : m(am) + { + } + + bool operator()(size_type i, size_type k) const + { + return m->key_comp()(m->c.keys[i], m->c.keys[k]); + } + + private: + const full_map_t *m; + }; + + template <class InputIt> + void insertOrderedUniqueRange(InputIt first, InputIt last) + { + const size_type s = c.keys.size(); + c.keys.resize(s + std::distance(first, last)); + c.values.resize(c.keys.size()); + for (size_type i = s; first != last; ++first, ++i) { + c.keys[i] = first->first; + c.values[i] = first->second; + } + + std::vector<size_type> p(size_t(c.keys.size())); + std::iota(p.begin(), p.end(), 0); + std::inplace_merge(p.begin(), p.begin() + s, p.end(), IndexedKeyComparator(this)); + applyPermutation(p); + makeUnique(); + } + + iterator binary_find(const Key &key) + { + return { &c, const_cast<const full_map_t *>(this)->binary_find(key).i }; + } + + const_iterator binary_find(const Key &key) const + { + auto it = lower_bound(key); + if (it != end()) { + if (!key_compare::operator()(key, it.key())) + return it; + it = end(); + } + return it; + } + + void ensureOrderedUnique() + { + std::vector<size_type> p(size_t(c.keys.size())); + std::iota(p.begin(), p.end(), 0); + std::stable_sort(p.begin(), p.end(), IndexedKeyComparator(this)); + applyPermutation(p); + makeUnique(); + } + + void applyPermutation(const std::vector<size_type> &p) + { + const size_type s = c.keys.size(); + std::vector<bool> done(s); + for (size_type i = 0; i < s; ++i) { + if (done[i]) + continue; + done[i] = true; + size_type j = i; + size_type k = p[i]; + while (i != k) { + qSwap(c.keys[j], c.keys[k]); + qSwap(c.values[j], c.values[k]); + done[k] = true; + j = k; + k = p[j]; + } + } + } + + void makeUnique() + { + if (c.keys.size() < 2) + return; + auto k = std::end(c.keys) - 1; + auto i = k - 1; + for (;;) { + if (key_compare::operator()(*i, *k) || key_compare::operator()(*k, *i)) { + if (i == std::begin(c.keys)) + break; + --i; + --k; + } else { + c.values.erase(std::begin(c.values) + std::distance(std::begin(c.keys), i)); + i = c.keys.erase(i); + if (i == std::begin(c.keys)) + break; + k = i + 1; + } + } + c.keys.shrink_to_fit(); + c.values.shrink_to_fit(); + } + + containers c; +}; + +QT_END_NAMESPACE + +#endif // QFLATMAP_P_H diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri index a1b243dd5f..230456bef9 100644 --- a/src/corelib/tools/tools.pri +++ b/src/corelib/tools/tools.pri @@ -12,6 +12,7 @@ HEADERS += \ tools/qcontainerfwd.h \ tools/qcontainertools_impl.h \ tools/qcryptographichash.h \ + tools/qflatmap_p.h \ tools/qfreelist_p.h \ tools/qhash.h \ tools/qhashfunctions.h \ diff --git a/tests/auto/corelib/tools/qflatmap/qflatmap.pro b/tests/auto/corelib/tools/qflatmap/qflatmap.pro new file mode 100644 index 0000000000..3927cee30c --- /dev/null +++ b/tests/auto/corelib/tools/qflatmap/qflatmap.pro @@ -0,0 +1,4 @@ +CONFIG += testcase +TARGET = tst_qflatmap +QT = core-private testlib +SOURCES = tst_qflatmap.cpp diff --git a/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp b/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp new file mode 100644 index 0000000000..a5ae6f5f44 --- /dev/null +++ b/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp @@ -0,0 +1,453 @@ +/**************************************************************************** +** +** Copyright (C) 2020 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/qflatmap_p.h> +#include <qbytearray.h> +#include <qstring.h> +#include <qstringview.h> +#include <qvarlengtharray.h> +#include <qvector.h> + +#include <algorithm> +#include <list> +#include <tuple> + +class tst_QFlatMap : public QObject +{ + Q_OBJECT +private slots: + void constructing(); + void constAccess(); + void insertion(); + void removal(); + void extraction(); + void iterators(); + void statefulComparator(); + void transparency(); + void viewIterators(); + void varLengthArray(); +}; + +void tst_QFlatMap::constructing() +{ + using Map = QFlatMap<int, QByteArray>; + Map fmDefault; + QVERIFY(fmDefault.isEmpty()); + QCOMPARE(fmDefault.size(), Map::size_type(0)); + QCOMPARE(fmDefault.size(), fmDefault.count()); + + auto key_compare = fmDefault.key_comp(); + auto selfbuilt_value_compare + = [&key_compare](const Map::value_type &a, const Map::value_type &b) + { + return key_compare(a.first, b.first); + }; + auto value_compare = fmDefault.value_comp(); + + Map::key_container_type kv = { 6, 2, 1 }; + Map::mapped_container_type mv = { "foo", "bar", "baz" }; + Map fmCopy{kv, mv}; + QCOMPARE(fmCopy.size(), Map::size_type(3)); + QVERIFY(std::is_sorted(fmCopy.begin(), fmCopy.end(), selfbuilt_value_compare)); + QVERIFY(std::is_sorted(fmCopy.begin(), fmCopy.end(), value_compare)); + + Map fmMove{ + Map::key_container_type{ 6, 2, 1 }, + Map::mapped_container_type{ "foo", "bar", "baz" } + }; + QCOMPARE(fmMove.size(), Map::size_type(3)); + QVERIFY(std::is_sorted(fmMove.begin(), fmMove.end(), value_compare)); + + auto fmInitList = Map{ { 1, 2 }, { "foo", "bar" } }; + QVERIFY(std::is_sorted(fmInitList.begin(), fmInitList.end(), value_compare)); + + auto fmRange = Map(fmCopy.begin(), fmCopy.end()); + QVERIFY(std::is_sorted(fmRange.begin(), fmRange.end(), value_compare)); + + kv.clear(); + mv.clear(); + std::vector<Map::value_type> sv; + for (auto it = fmRange.begin(); it != fmRange.end(); ++it) { + kv.push_back(it->first); + mv.push_back(it->second); + sv.push_back(*it); + } + auto fmFromSortedVectorCopy = Map(Qt::OrderedUniqueRange, kv, mv); + auto fmFromSortedVectorMove = Map(Qt::OrderedUniqueRange, Map::key_container_type(kv), + Map::mapped_container_type(mv)); + auto fmFromSortedInitList = Map(Qt::OrderedUniqueRange, { { 1, "foo" }, { 2, "bar" } }); + auto fmFromSortedRange = Map(Qt::OrderedUniqueRange, sv.begin(), sv.end()); +} + +void tst_QFlatMap::constAccess() +{ + using Map = QFlatMap<QByteArray, QByteArray>; + const Map m{ { { "foo", "FOO" }, { "bar", "BAR" } } }; + + const std::vector<Map::value_type> v{ { "foo", "FOO" }, { "bar", "BAR" } }; + + QCOMPARE(m.value("foo").data(), "FOO"); + QCOMPARE(m.value("bar").data(), "BAR"); + QCOMPARE(m.value("nix"), QByteArray()); + QCOMPARE(m.value("nix", "NIX").data(), "NIX"); + QCOMPARE(m["foo"].data(), "FOO"); + QCOMPARE(m["bar"].data(), "BAR"); + QCOMPARE(m["nix"], QByteArray()); + QVERIFY(m.contains("foo")); + QVERIFY(!m.contains("nix")); +} + +void tst_QFlatMap::insertion() +{ + using Map = QFlatMap<QByteArray, QByteArray>; + Map m; + QByteArray foo = "foo"; + m[foo] = foo.toUpper(); + m["bar"] = "BAR"; + m["baz"] = "BAZ"; + QVERIFY(m.insert("oof", "eek").second); + QVERIFY(!m.insert("oof", "OOF").second); + const std::vector<Map::value_type> container = { { "bla", "BLA" }, { "blubb", "BLUBB" } }; + m.insert(container.begin(), container.end()); + QCOMPARE(m.value("foo").data(), "FOO"); + QCOMPARE(m.value("bar").data(), "BAR"); + QCOMPARE(m.value("baz").data(), "BAZ"); + QCOMPARE(m.value("oof").data(), "OOF"); + QCOMPARE(m.value("bla").data(), "BLA"); + QCOMPARE(m.value("blubb").data(), "BLUBB"); + + Map::value_type a1[] = { { "narf", "NARF" }, + { "zort", "ZORT" }, + { "troz", "TROZ" } }; + Map::value_type a2[] = { { "gnampf", "GNAMPF" }, + { "narf", "NARFFFF" }, + { "narf", "NARFFFFF" }, + { "narf", "NARFFFFFF" } }; + m.insert(std::begin(a1), std::end(a1)); + m.insert(Qt::OrderedUniqueRange, std::begin(a2), std::end(a2)); + QCOMPARE(m.size(), 10); + QCOMPARE(m.value("narf").data(), "NARFFFFFF"); + QCOMPARE(m.value("gnampf").data(), "GNAMPF"); +} + +void tst_QFlatMap::extraction() +{ + using Map = QFlatMap<int, QByteArray>; + Map::key_container_type expectedKeys = { 1, 2, 3 }; + Map::mapped_container_type expectedValues = { "een", "twee", "dree" }; + Map m(expectedKeys, expectedValues); + auto keys = m.keys(); + auto values = m.values(); + QCOMPARE(keys, expectedKeys); + QCOMPARE(values, expectedValues); + Map::containers c = std::move(m).extract(); + QCOMPARE(c.keys, expectedKeys); + QCOMPARE(c.values, expectedValues); +} + +void tst_QFlatMap::iterators() +{ + using Map = QFlatMap<int, QByteArray>; + auto m = Map{ { 1, "foo" }, { 2, "bar" }, { 3, "baz" } }; + { + // forward / backward + Map::iterator a = m.begin(); + QVERIFY(a != m.end()); + QCOMPARE(a.key(), 1); + QCOMPARE(a.value(), "foo"); + ++a; + QCOMPARE(a.key(), 2); + QCOMPARE(a.value(), "bar"); + Map::iterator b = a++; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz")); + QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(2, "bar")); + QCOMPARE(++a, m.end()); + --a; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz")); + a.value() = "buzz"; + b = a--; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar")); + QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(3, "buzz")); + b.value() = "baz"; + + // random access + a = m.begin(); + a += 2; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz")); + a = m.begin() + 1; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar")); + a = 1 + m.begin(); + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar")); + a = m.end() - 1; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz")); + b = m.end(); + b -= 1; + QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(3, "baz")); + QCOMPARE(m.end() - m.begin(), m.size()); + + // comparison + a = m.begin() + m.size() - 1; + b = m.end() - 1; + QVERIFY(a == b); + a = m.begin(); + b = m.end(); + QVERIFY(a < b); + QVERIFY(a <= b); + QVERIFY(b > a); + QVERIFY(b >= a); + a = b; + QVERIFY(!(a < b)); + QVERIFY(a <= b); + QVERIFY(!(b > a)); + QVERIFY(b >= a); + + // de-referencing + a = m.begin(); + auto ref0 = *a; + QCOMPARE(ref0.first, 1); + QCOMPARE(ref0.second, "foo"); + auto ref1 = a[1]; + QCOMPARE(ref1.first, 2); + QCOMPARE(ref1.second, "bar"); + } + { + // forward / backward + Map::const_iterator a = m.cbegin(); + QVERIFY(a != m.cend()); + QCOMPARE(a.key(), 1); + QCOMPARE(a.value(), "foo"); + ++a; + QCOMPARE(a.key(), 2); + QCOMPARE(a.value(), "bar"); + Map::const_iterator b = a++; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz")); + QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(2, "bar")); + QCOMPARE(++a, m.cend()); + --a; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz")); + b = a--; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar")); + + // random access + a = m.cbegin(); + a += 2; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz")); + a = m.cbegin() + 1; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar")); + a = 1 + m.cbegin(); + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(2, "bar")); + a = m.cend() - 1; + QCOMPARE(std::tie(a.key(), a.value()), std::make_tuple(3, "baz")); + b = m.cend(); + b -= 1; + QCOMPARE(std::tie(b.key(), b.value()), std::make_tuple(3, "baz")); + QCOMPARE(m.cend() - m.cbegin(), m.size()); + + // comparison + a = m.cbegin() + m.size() - 1; + b = m.cend() - 1; + QVERIFY(a == b); + a = m.cbegin(); + b = m.cend(); + QVERIFY(a < b); + QVERIFY(a <= b); + QVERIFY(b > a); + QVERIFY(b >= a); + a = b; + QVERIFY(!(a < b)); + QVERIFY(a <= b); + QVERIFY(!(b > a)); + QVERIFY(b >= a); + + // de-referencing + a = m.cbegin(); + auto ref0 = *a; + QCOMPARE(ref0.first, 1); + QCOMPARE(ref0.second, "foo"); + auto ref1 = a[1]; + QCOMPARE(ref1.first, 2); + QCOMPARE(ref1.second, "bar"); + } + { + Map::iterator it = m.begin(); + Map::const_iterator cit = it; + Q_UNUSED(it); + Q_UNUSED(cit); + } + { + std::list<Map::value_type> revlst; + std::copy(m.begin(), m.end(), std::front_inserter(revlst)); + std::vector<Map::value_type> v0; + std::copy(revlst.begin(), revlst.end(), std::back_inserter(v0)); + std::vector<Map::value_type> v1; + std::copy(m.rbegin(), m.rend(), std::back_inserter(v1)); + const Map cm = m; + std::vector<Map::value_type> v2; + std::copy(cm.rbegin(), cm.rend(), std::back_inserter(v2)); + std::vector<Map::value_type> v3; + std::copy(m.crbegin(), m.crend(), std::back_inserter(v3)); + QCOMPARE(v0, v1); + QCOMPARE(v1, v2); + QCOMPARE(v2, v3); + } +} + +void tst_QFlatMap::removal() +{ + using Map = QFlatMap<int, QByteArray>; + Map m({ { 2, "bar" }, { 3, "baz" }, { 1, "foo" } }); + QCOMPARE(m.value(2).data(), "bar"); + QCOMPARE(m.take(2).data(), "bar"); + QVERIFY(!m.contains(2)); + QCOMPARE(m.size(), Map::size_type(2)); + QVERIFY(m.remove(1)); + QVERIFY(!m.contains(1)); + QVERIFY(!m.remove(1)); + QCOMPARE(m.size(), Map::size_type(1)); + m.clear(); + QVERIFY(m.isEmpty()); + QVERIFY(m.empty()); + + m[1] = "een"; + m[2] = "twee"; + m[3] = "dree"; + auto it = m.lower_bound(1); + QCOMPARE(it.key(), 1); + it = m.erase(it); + QCOMPARE(it.key(), 2); + QVERIFY(!m.contains(1)); +} + +void tst_QFlatMap::statefulComparator() +{ + struct CountingCompare { + mutable int count = 0; + + bool operator()(const QString &lhs, const QString &rhs) const + { + ++count; + return lhs < rhs; + } + }; + + using Map = QFlatMap<QString, QString, CountingCompare>; + auto m1 = Map{ { "en", "een"}, { "to", "twee" }, { "tre", "dree" } }; + QVERIFY(m1.key_comp().count > 0); + auto m2 = Map(m1.key_comp()); + QCOMPARE(m2.key_comp().count, m1.key_comp().count); + m2.insert(m1.begin(), m1.end()); + QVERIFY(m2.key_comp().count > m1.key_comp().count); +} + +void tst_QFlatMap::transparency() +{ + struct StringViewCompare + { + using is_transparent = void; + bool operator()(const QStringView &lhs, const QStringView &rhs) const + { + return lhs < rhs; + } + }; + + using Map = QFlatMap<QString, QString, StringViewCompare>; + auto m = Map{ { "one", "een" }, { "two", "twee" }, { "three", "dree" } }; + + const QString numbers = "one two three"; + const QStringView sv1{numbers.constData(), 3}; + const QStringView sv2{numbers.constData() + 4, 3}; + const QStringView sv3{numbers.constData() + 8, 5}; + QCOMPARE(m.lower_bound(sv1).value(), "een"); + QCOMPARE(m.lower_bound(sv2).value(), "twee"); + QCOMPARE(m.lower_bound(sv3).value(), "dree"); +} + +void tst_QFlatMap::viewIterators() +{ + using Map = QFlatMap<QByteArray, QByteArray>; + Map m({ { "yksi", "een"}, { "kaksi", "twee" }, { "kolme", "dree" } }); + { + std::vector<QByteArray> keys; + std::transform(m.begin(), m.end(), std::back_inserter(keys), + [](const Map::value_type &v) + { + return v.first; + }); + auto it = keys.begin(); + QCOMPARE(*it, "kaksi"); + QCOMPARE(it->length(), 5); + ++it; + QCOMPARE(*it, "kolme"); + it++; + QCOMPARE(*it, "yksi"); + ++it; + QCOMPARE(it, keys.end()); + --it; + QCOMPARE(*it, "yksi"); + it--; + QCOMPARE(*it, "kolme"); + } + { + std::vector<QByteArray> values; + std::transform(m.begin(), m.end(), std::back_inserter(values), + [](const Map::value_type &v) + { + return v.second; + }); + auto it = values.begin(); + QCOMPARE(*it, "twee"); + QCOMPARE(it->length(), 4); + ++it; + QCOMPARE(*it, "dree"); + it++; + QCOMPARE(*it, "een"); + ++it; + QCOMPARE(it, values.end()); + --it; + QCOMPARE(*it, "een"); + it--; + QCOMPARE(*it, "dree"); + } +} + +void tst_QFlatMap::varLengthArray() +{ + using Map = QFlatMap<int, QByteArray, std::less<int>, + QVarLengthArray<int, 1024>, QVarLengthArray<QByteArray, 1024>>; + Map m{ { 2, "twee" } }; + m.insert(1, "een"); + m.remove(1); + QVERIFY(!m.isEmpty()); + m.remove(2); + QVERIFY(m.isEmpty()); +} + +QTEST_APPLESS_MAIN(tst_QFlatMap) +#include "tst_qflatmap.moc" diff --git a/tests/auto/corelib/tools/tools.pro b/tests/auto/corelib/tools/tools.pro index 5a7c8478f1..be195ea037 100644 --- a/tests/auto/corelib/tools/tools.pro +++ b/tests/auto/corelib/tools/tools.pro @@ -11,6 +11,7 @@ SUBDIRS=\ qcryptographichash \ qeasingcurve \ qexplicitlyshareddatapointer \ + qflatmap \ qfreelist \ qhash \ qhashfunctions \ |