1 | // Copyright (C) 2022 The Qt Company Ltd. |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | |
4 | #ifndef QTCORE_QMINIMALFLATSET_P_H |
5 | #define QTCORE_QMINIMALFLATSET_P_H |
6 | |
7 | // |
8 | // W A R N I N G |
9 | // ------------- |
10 | // |
11 | // This file is not part of the Qt API. It exists purely as an |
12 | // implementation detail. This header file may change from version to |
13 | // version without notice, or even be removed. |
14 | // |
15 | // We mean it. |
16 | // |
17 | |
18 | #include <QtCore/qcontainerfwd.h> |
19 | #include <QtCore/qfunctionaltools_impl.h> // CompactStorage |
20 | #include <QtCore/private/qglobal_p.h> |
21 | |
22 | //#define QMINIMAL_FLAT_SET_DEBUG |
23 | #ifdef QMINIMAL_FLAT_SET_DEBUG |
24 | # include <QtCore/qscopeguard.h> |
25 | # include <QtCore/qdebug.h> |
26 | # define QMINIMAL_FLAT_SET_PRINT_AT_END \ |
27 | const auto sg = qScopeGuard([&] { qDebug() << this << *this; }); |
28 | #else |
29 | # define QMINIMAL_FLAT_SET_PRINT_AT_END |
30 | #endif |
31 | |
32 | #include <algorithm> // for std::lower_bound |
33 | #include <functional> // for std::less, std::ref |
34 | |
35 | QT_BEGIN_NAMESPACE |
36 | |
37 | /* |
38 | This is a minimal version of a QFlatSet, the std::set version of QFlatMap. |
39 | Like QFlatMap, it has linear insertion and removal, not logarithmic, like |
40 | real QMap and std::set, so it's only a good container if you either have |
41 | very few entries or lots, but with separate setup and lookup stages. |
42 | Because a full QFlatSet would be 10x the work on writing this minimal one, |
43 | we keep it here for now. When more users pop up and the class has matured a |
44 | bit, we can consider moving it as QFlatSet alongside QFlatMap. |
45 | */ |
46 | |
47 | template <typename T, typename Container = QList<T>, typename Compare = std::less<T>> |
48 | class QMinimalFlatSet : QtPrivate::CompactStorage<Compare> |
49 | { |
50 | Container c; |
51 | using CompareStorage = QtPrivate::CompactStorage<Compare>; |
52 | public: |
53 | QMinimalFlatSet() = default; |
54 | explicit QMinimalFlatSet(const Compare &cmp) : CompareStorage{cmp} {} |
55 | // Rule Of Zero applies |
56 | |
57 | using const_iterator = typename Container::const_iterator; |
58 | using iterator = const_iterator; |
59 | using const_reverse_iterator = typename Container::const_reverse_iterator; |
60 | using reverse_iterator = const_reverse_iterator; |
61 | using value_type = T; |
62 | using key_compare = Compare; |
63 | using value_compare = Compare; |
64 | |
65 | key_compare key_comp() const { return this->object(); } |
66 | value_compare value_comp() const { return key_comp(); } |
67 | |
68 | iterator begin() const { return c.cbegin(); } |
69 | iterator end() const { return c.cend(); } |
70 | iterator cbegin() const { return begin(); } |
71 | iterator cend() const { return cend(); } |
72 | |
73 | reverse_iterator rbegin() const { return c.crbegin(); } |
74 | reverse_iterator rend() const { return c.crend(); } |
75 | reverse_iterator crbegin() const { return rbegin(); } |
76 | reverse_iterator crend() const { return rend(); } |
77 | |
78 | void clear() { |
79 | QMINIMAL_FLAT_SET_PRINT_AT_END |
80 | c.clear(); |
81 | } |
82 | auto size() const { return c.size(); } |
83 | auto count() const { return size(); } |
84 | bool isEmpty() const { return size() == 0; } |
85 | |
86 | std::pair<iterator, bool> insert(value_type &&v) |
87 | { |
88 | QMINIMAL_FLAT_SET_PRINT_AT_END |
89 | const auto r = lookup(v); |
90 | if (r.exists) |
91 | return {r.it, false}; |
92 | else |
93 | return {c.insert(r.it, std::move(v)), true}; |
94 | } |
95 | |
96 | std::pair<iterator, bool> insert(const value_type &v) |
97 | { |
98 | QMINIMAL_FLAT_SET_PRINT_AT_END |
99 | const auto r = lookup(v); |
100 | if (r.exists) |
101 | return {r.it, false}; |
102 | else |
103 | return {c.insert(r.it, v), true}; |
104 | } |
105 | |
106 | void erase(const value_type &v) |
107 | { |
108 | QMINIMAL_FLAT_SET_PRINT_AT_END |
109 | const auto r = lookup(v); |
110 | if (r.exists) |
111 | c.erase(r.it); |
112 | } |
113 | void remove(const value_type &v) { erase(v); } |
114 | |
115 | bool contains(const value_type &v) const |
116 | { |
117 | return lookup(v).exists; |
118 | } |
119 | |
120 | const Container &values() const & { return c; } |
121 | Container values() && { return std::move(c); } |
122 | |
123 | private: |
124 | auto lookup(const value_type &v) const |
125 | { |
126 | struct R { |
127 | iterator it; |
128 | bool exists; |
129 | }; |
130 | |
131 | auto cmp = std::ref(this->object()); // don't let std::lower_bound copy it |
132 | |
133 | const auto it = std::lower_bound(c.cbegin(), c.cend(), v, cmp); |
134 | return R{it, it != c.cend() && !cmp(v, *it)}; |
135 | } |
136 | |
137 | #ifdef QMINIMAL_FLAT_SET_DEBUG |
138 | friend QDebug operator<<(QDebug dbg, const QMinimalFlatSet &set) |
139 | { |
140 | const QDebugStateSaver saver(dbg); |
141 | dbg.nospace() << "QMinimalFlatSet{" ; |
142 | for (auto &e : set) |
143 | dbg << e << ", " ; |
144 | return dbg << "}" ; |
145 | } |
146 | #endif |
147 | }; |
148 | |
149 | #undef QMINIMAL_FLAT_SET_PRINT_AT_END |
150 | |
151 | template <typename T, qsizetype N = QVarLengthArrayDefaultPrealloc> |
152 | using QMinimalVarLengthFlatSet = QMinimalFlatSet<T, QVarLengthArray<T, N>>; |
153 | |
154 | QT_END_NAMESPACE |
155 | |
156 | #endif // QTCORE_QMINIMALFLATSET_P_H |
157 | |