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
35QT_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
47template <typename T, typename Container = QList<T>, typename Compare = std::less<T>>
48class QMinimalFlatSet : QtPrivate::CompactStorage<Compare>
49{
50 Container c;
51 using CompareStorage = QtPrivate::CompactStorage<Compare>;
52public:
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
123private:
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
151template <typename T, qsizetype N = QVarLengthArrayDefaultPrealloc>
152using QMinimalVarLengthFlatSet = QMinimalFlatSet<T, QVarLengthArray<T, N>>;
153
154QT_END_NAMESPACE
155
156#endif // QTCORE_QMINIMALFLATSET_P_H
157

source code of qtbase/src/corelib/tools/qminimalflatset_p.h