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
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 alongside QFlatMap in QtCore.
45*/
46
47template <typename T, typename Container = QList<T>>
48class QMinimalFlatSet
49{
50 Container c;
51public:
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
117private:
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
141QT_END_NAMESPACE
142
143#endif // QMINIMALFLATSET_P_H
144

source code of qtdeclarative/src/quick/util/qminimalflatset_p.h