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 QMINIMALFLATSET_P_H |
5 | #define 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 <QtQuick/qtquickglobal.h> |
19 | |
20 | #include <QtCore/qcontainerfwd.h> |
21 | #include <QtCore/private/qglobal_p.h> |
22 | |
23 | //#define QMINIMAL_FLAT_SET_DEBUG |
24 | #ifdef QMINIMAL_FLAT_SET_DEBUG |
25 | # include <QtCore/qscopeguard.h> |
26 | # include <QtCore/qdebug.h> |
27 | # define QMINIMAL_FLAT_SET_PRINT_AT_END \ |
28 | const auto sg = qScopeGuard([&] { qDebug() << this << *this; }); |
29 | #else |
30 | # define QMINIMAL_FLAT_SET_PRINT_AT_END |
31 | #endif |
32 | |
33 | #include <algorithm> // for std::lower_bound |
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 alongside QFlatMap in QtCore. |
45 | */ |
46 | |
47 | template <typename T, typename Container = QList<T>> |
48 | class QMinimalFlatSet |
49 | { |
50 | Container c; |
51 | public: |
52 | // compiler-generated default ctor is ok! |
53 | // compiler-generated copy/move ctor/assignment operators are ok! |
54 | // compiler-generated dtor is ok! |
55 | |
56 | using const_iterator = typename Container::const_iterator; |
57 | using iterator = const_iterator; |
58 | using const_reverse_iterator = typename Container::const_reverse_iterator; |
59 | using reverse_iterator = const_reverse_iterator; |
60 | using value_type = T; |
61 | |
62 | iterator begin() const { return c.cbegin(); } |
63 | iterator end() const { return c.cend(); } |
64 | iterator cbegin() const { return begin(); } |
65 | iterator cend() const { return cend(); } |
66 | |
67 | reverse_iterator rbegin() const { return c.crbegin(); } |
68 | reverse_iterator rend() const { return c.crend(); } |
69 | reverse_iterator crbegin() const { return rbegin(); } |
70 | reverse_iterator crend() const { return rend(); } |
71 | |
72 | void clear() { |
73 | QMINIMAL_FLAT_SET_PRINT_AT_END |
74 | c.clear(); |
75 | } |
76 | auto size() const { return c.size(); } |
77 | auto count() const { return size(); } |
78 | bool isEmpty() const { return size() == 0; } |
79 | |
80 | std::pair<iterator, bool> insert(value_type &&v) |
81 | { |
82 | QMINIMAL_FLAT_SET_PRINT_AT_END |
83 | const auto r = lookup(v); |
84 | if (r.exists) |
85 | return {r.it, false}; |
86 | else |
87 | return {c.insert(r.it, std::move(v)), true}; |
88 | } |
89 | |
90 | std::pair<iterator, bool> insert(const value_type &v) |
91 | { |
92 | QMINIMAL_FLAT_SET_PRINT_AT_END |
93 | const auto r = lookup(v); |
94 | if (r.exists) |
95 | return {r.it, false}; |
96 | else |
97 | return {c.insert(r.it, v), true}; |
98 | } |
99 | |
100 | void erase(const value_type &v) |
101 | { |
102 | QMINIMAL_FLAT_SET_PRINT_AT_END |
103 | const auto r = lookup(v); |
104 | if (r.exists) |
105 | c.erase(r.it); |
106 | } |
107 | void remove(const value_type &v) { erase(v); } |
108 | |
109 | bool contains(const value_type &v) const |
110 | { |
111 | return lookup(v).exists; |
112 | } |
113 | |
114 | const Container &values() const & { return c; } |
115 | Container values() && { return std::move(c); } |
116 | |
117 | private: |
118 | auto lookup(const value_type &v) const |
119 | { |
120 | struct R { |
121 | iterator it; |
122 | bool exists; |
123 | }; |
124 | |
125 | const auto it = std::lower_bound(c.cbegin(), c.cend(), v); |
126 | return R{it, it != c.cend() && !(v < *it)}; |
127 | } |
128 | |
129 | #ifdef QMINIMAL_FLAT_SET_DEBUG |
130 | friend QDebug operator<<(QDebug dbg, const QMinimalFlatSet &set) |
131 | { |
132 | const QDebugStateSaver saver(dbg); |
133 | dbg.nospace() << "QMinimalFlatSet{" ; |
134 | for (auto &e : set) |
135 | dbg << e << ", " ; |
136 | return dbg << "}" ; |
137 | } |
138 | #endif |
139 | }; |
140 | |
141 | QT_END_NAMESPACE |
142 | |
143 | #endif // QMINIMALFLATSET_P_H |
144 | |