2 * Copyright (C) 2024-2026 David C. Manuelda (StormBytePP)
4 * This is the base for StormByte Suite libraries.
6 * StormByte original source is dual-licensed:
8 * 1. GNU Lesser General Public License v3.0 (or later)
9 * You may redistribute and/or modify this file under the terms of the
10 * GNU Lesser General Public License as published by the Free Software
11 * Foundation, either version 3 of the License, or (at your option)
14 * 2. Commercial license
15 * Alternatively, this file may be used under the terms of a commercial
16 * license agreement with the copyright holder
17 * (David C. Manuelda <StormByte@gmail.com>).
19 * Both licenses apply only to original StormByte source in this repository.
20 * They do not cover other StormByte modules or any third-party material
21 * shipped with this repository (including everything under thirdparty/),
22 * which remains under its own license.
24 * Neither license grants any patent rights. Any patent licenses required
25 * to use this software or third-party components must be obtained separately
26 * from the patent holders.
28 * StormByte is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU Lesser General Public License for more details.
33 * You should have received a copy of the GNU Lesser General Public License
34 * version 3 along with StormByte. If not, see
35 * <https://www.gnu.org/licenses/lgpl-3.0.html>.
37 * SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-StormByte-Commercial
44 template<Type::SafeValue K, class Compare>
45 requires std::strict_weak_order<Compare, const K&, const K&>
46 Set<K, Compare>::Set() = default;
48 template<Type::SafeValue K, class Compare>
49 requires std::strict_weak_order<Compare, const K&, const K&>
50 Set<K, Compare>::Set(const Compare& compare): m_values(compare) {}
52 template<Type::SafeValue K, class Compare>
53 requires std::strict_weak_order<Compare, const K&, const K&>
54 Set<K, Compare>::Set(const Set& other): m_values(other.m_values) {}
56 template<Type::SafeValue K, class Compare>
57 requires std::strict_weak_order<Compare, const K&, const K&>
58 Set<K, Compare>::Set(Set&& other): m_values(std::move(other.m_values)) {}
60 template<Type::SafeValue K, class Compare>
61 requires std::strict_weak_order<Compare, const K&, const K&>
62 Set<K, Compare>::~Set() = default;
64 template<Type::SafeValue K, class Compare>
65 requires std::strict_weak_order<Compare, const K&, const K&>
66 Set<K, Compare>& Set<K, Compare>::operator=(const Set& other) {
67 m_values = other.m_values;
71 template<Type::SafeValue K, class Compare>
72 requires std::strict_weak_order<Compare, const K&, const K&>
73 Set<K, Compare>& Set<K, Compare>::operator=(Set&& other) noexcept {
74 m_values = std::move(other.m_values);
78 template<Type::SafeValue K, class Compare>
79 requires std::strict_weak_order<Compare, const K&, const K&>
80 Set<K, Compare>& Set<K, Compare>::operator=(std::initializer_list<K> values) {
81 Set replacement(values, key_comp());
86 template<Type::SafeValue K, class Compare>
87 requires std::strict_weak_order<Compare, const K&, const K&>
88 template<class InputIt>
89 Set<K, Compare>::Set(InputIt first, InputIt last) {
93 template<Type::SafeValue K, class Compare>
94 requires std::strict_weak_order<Compare, const K&, const K&>
95 template<class InputIt>
96 Set<K, Compare>::Set(InputIt first, InputIt last, const Compare& compare): m_values(compare) {
100 template<Type::SafeValue K, class Compare>
101 requires std::strict_weak_order<Compare, const K&, const K&>
102 Set<K, Compare>::Set(std::initializer_list<K> values) {
106 template<Type::SafeValue K, class Compare>
107 requires std::strict_weak_order<Compare, const K&, const K&>
108 Set<K, Compare>::Set(std::initializer_list<K> values, const Compare& compare): m_values(compare) {
112 template<Type::SafeValue K, class Compare>
113 requires std::strict_weak_order<Compare, const K&, const K&>
114 typename Set<K, Compare>::key_compare Set<K, Compare>::key_comp() const { return m_values.key_comp(); }
116 template<Type::SafeValue K, class Compare>
117 requires std::strict_weak_order<Compare, const K&, const K&>
118 typename Set<K, Compare>::value_compare Set<K, Compare>::value_comp() const { return key_comp(); }
120 template<Type::SafeValue K, class Compare>
121 requires std::strict_weak_order<Compare, const K&, const K&>
122 typename Set<K, Compare>::iterator Set<K, Compare>::begin() noexcept { return iterator(m_values.begin()); }
124 template<Type::SafeValue K, class Compare>
125 requires std::strict_weak_order<Compare, const K&, const K&>
126 typename Set<K, Compare>::const_iterator Set<K, Compare>::begin() const noexcept { return const_iterator(m_values.begin()); }
128 template<Type::SafeValue K, class Compare>
129 requires std::strict_weak_order<Compare, const K&, const K&>
130 typename Set<K, Compare>::const_iterator Set<K, Compare>::cbegin() const noexcept { return begin(); }
132 template<Type::SafeValue K, class Compare>
133 requires std::strict_weak_order<Compare, const K&, const K&>
134 typename Set<K, Compare>::iterator Set<K, Compare>::end() noexcept { return iterator(m_values.end()); }
136 template<Type::SafeValue K, class Compare>
137 requires std::strict_weak_order<Compare, const K&, const K&>
138 typename Set<K, Compare>::const_iterator Set<K, Compare>::end() const noexcept { return const_iterator(m_values.end()); }
140 template<Type::SafeValue K, class Compare>
141 requires std::strict_weak_order<Compare, const K&, const K&>
142 typename Set<K, Compare>::const_iterator Set<K, Compare>::cend() const noexcept { return end(); }
144 template<Type::SafeValue K, class Compare>
145 requires std::strict_weak_order<Compare, const K&, const K&>
146 typename Set<K, Compare>::reverse_iterator Set<K, Compare>::rbegin() noexcept { return reverse_iterator(end()); }
148 template<Type::SafeValue K, class Compare>
149 requires std::strict_weak_order<Compare, const K&, const K&>
150 typename Set<K, Compare>::const_reverse_iterator Set<K, Compare>::rbegin() const noexcept { return const_reverse_iterator(end()); }
152 template<Type::SafeValue K, class Compare>
153 requires std::strict_weak_order<Compare, const K&, const K&>
154 typename Set<K, Compare>::const_reverse_iterator Set<K, Compare>::crbegin() const noexcept { return rbegin(); }
156 template<Type::SafeValue K, class Compare>
157 requires std::strict_weak_order<Compare, const K&, const K&>
158 typename Set<K, Compare>::reverse_iterator Set<K, Compare>::rend() noexcept { return reverse_iterator(begin()); }
160 template<Type::SafeValue K, class Compare>
161 requires std::strict_weak_order<Compare, const K&, const K&>
162 typename Set<K, Compare>::const_reverse_iterator Set<K, Compare>::rend() const noexcept { return const_reverse_iterator(begin()); }
164 template<Type::SafeValue K, class Compare>
165 requires std::strict_weak_order<Compare, const K&, const K&>
166 typename Set<K, Compare>::const_reverse_iterator Set<K, Compare>::crend() const noexcept { return rend(); }
168 template<Type::SafeValue K, class Compare>
169 requires std::strict_weak_order<Compare, const K&, const K&>
170 bool Set<K, Compare>::empty() const noexcept { return m_values.empty(); }
172 template<Type::SafeValue K, class Compare>
173 requires std::strict_weak_order<Compare, const K&, const K&>
174 typename Set<K, Compare>::size_type Set<K, Compare>::size() const noexcept { return m_values.size(); }
176 template<Type::SafeValue K, class Compare>
177 requires std::strict_weak_order<Compare, const K&, const K&>
178 typename Set<K, Compare>::size_type Set<K, Compare>::max_size() const noexcept { return m_values.max_size(); }
180 template<Type::SafeValue K, class Compare>
181 requires std::strict_weak_order<Compare, const K&, const K&>
182 void Set<K, Compare>::clear() noexcept { m_values.clear(); }
184 template<Type::SafeValue K, class Compare>
185 requires std::strict_weak_order<Compare, const K&, const K&>
186 typename Set<K, Compare>::insert_result Set<K, Compare>::insert(const K& value) {
187 auto result = m_values.emplace(value, Monostate{});
188 return insert_result{iterator(result.first), result.second};
191 template<Type::SafeValue K, class Compare>
192 requires std::strict_weak_order<Compare, const K&, const K&>
193 typename Set<K, Compare>::insert_result Set<K, Compare>::insert(K&& value) {
194 auto result = m_values.emplace(std::move(value), Monostate{});
195 return insert_result{iterator(result.first), result.second};
198 template<Type::SafeValue K, class Compare>
199 requires std::strict_weak_order<Compare, const K&, const K&>
200 typename Set<K, Compare>::iterator Set<K, Compare>::insert(const_iterator hint, const K& value) {
201 return iterator(m_values.emplace_hint(hint.m_cursor, value, Monostate{}));
204 template<Type::SafeValue K, class Compare>
205 requires std::strict_weak_order<Compare, const K&, const K&>
206 typename Set<K, Compare>::iterator Set<K, Compare>::insert(const_iterator hint, K&& value) {
207 return iterator(m_values.emplace_hint(hint.m_cursor, std::move(value), Monostate{}));
210 template<Type::SafeValue K, class Compare>
211 requires std::strict_weak_order<Compare, const K&, const K&>
212 template<class InputIt>
213 void Set<K, Compare>::insert(InputIt first, InputIt last) {
214 for (; first != last; ++first)
215 insert(value_type(*first));
218 template<Type::SafeValue K, class Compare>
219 requires std::strict_weak_order<Compare, const K&, const K&>
220 void Set<K, Compare>::insert(std::initializer_list<K> values) { insert(values.begin(), values.end()); }
222 template<Type::SafeValue K, class Compare>
223 requires std::strict_weak_order<Compare, const K&, const K&>
224 template<class... Args>
225 typename Set<K, Compare>::insert_result Set<K, Compare>::emplace(Args&&... args) {
226 return insert(K(std::forward<Args>(args)...));
229 template<Type::SafeValue K, class Compare>
230 requires std::strict_weak_order<Compare, const K&, const K&>
231 template<class... Args>
232 typename Set<K, Compare>::iterator Set<K, Compare>::emplace_hint(const_iterator hint, Args&&... args) {
233 return insert(hint, K(std::forward<Args>(args)...));
236 template<Type::SafeValue K, class Compare>
237 requires std::strict_weak_order<Compare, const K&, const K&>
238 typename Set<K, Compare>::insert_return_type Set<K, Compare>::insert(node_type&& handle) {
239 auto result = m_values.insert(std::move(handle.m_node));
240 return insert_return_type{iterator(result.position), result.inserted, node_type(std::move(result.node))};
243 template<Type::SafeValue K, class Compare>
244 requires std::strict_weak_order<Compare, const K&, const K&>
245 typename Set<K, Compare>::iterator Set<K, Compare>::insert(const_iterator hint, node_type&& handle) {
246 return iterator(m_values.insert(hint.m_cursor, std::move(handle.m_node)));
249 template<Type::SafeValue K, class Compare>
250 requires std::strict_weak_order<Compare, const K&, const K&>
251 typename Set<K, Compare>::node_type Set<K, Compare>::extract(const_iterator position) {
252 return node_type(m_values.extract(position.m_cursor));
255 template<Type::SafeValue K, class Compare>
256 requires std::strict_weak_order<Compare, const K&, const K&>
257 typename Set<K, Compare>::node_type Set<K, Compare>::extract(const K& value) {
258 return node_type(m_values.extract(value));
261 template<Type::SafeValue K, class Compare>
262 requires std::strict_weak_order<Compare, const K&, const K&>
263 template<class OtherCompare>
264 void Set<K, Compare>::merge(Set<K, OtherCompare>& source) {
265 auto cursor = source.begin();
266 while (cursor != source.end()) {
267 if (contains(*cursor)) {
271 auto next = std::next(cursor);
272 if constexpr (std::same_as<Compare, OtherCompare>)
273 insert(source.extract(cursor));
276 source.erase(cursor);
277 insert(std::move(value));
283 template<Type::SafeValue K, class Compare>
284 requires std::strict_weak_order<Compare, const K&, const K&>
285 typename Set<K, Compare>::iterator Set<K, Compare>::erase(iterator position) noexcept {
286 return iterator(m_values.erase(position.m_cursor));
289 template<Type::SafeValue K, class Compare>
290 requires std::strict_weak_order<Compare, const K&, const K&>
291 typename Set<K, Compare>::iterator Set<K, Compare>::erase(const_iterator position) noexcept {
292 return iterator(m_values.erase(position.m_cursor));
295 template<Type::SafeValue K, class Compare>
296 requires std::strict_weak_order<Compare, const K&, const K&>
297 typename Set<K, Compare>::iterator Set<K, Compare>::erase(const_iterator first, const_iterator last) noexcept {
298 return iterator(m_values.erase(first.m_cursor, last.m_cursor));
301 template<Type::SafeValue K, class Compare>
302 requires std::strict_weak_order<Compare, const K&, const K&>
303 typename Set<K, Compare>::size_type Set<K, Compare>::erase(const K& value) noexcept { return m_values.erase(value); }
305 template<Type::SafeValue K, class Compare>
306 requires std::strict_weak_order<Compare, const K&, const K&>
307 void Set<K, Compare>::swap(Set& other) noexcept { m_values.swap(other.m_values); }
309 template<Type::SafeValue K, class Compare>
310 requires std::strict_weak_order<Compare, const K&, const K&>
311 typename Set<K, Compare>::iterator Set<K, Compare>::find(const K& value) { return iterator(m_values.find(value)); }
313 template<Type::SafeValue K, class Compare>
314 requires std::strict_weak_order<Compare, const K&, const K&>
315 typename Set<K, Compare>::const_iterator Set<K, Compare>::find(const K& value) const { return const_iterator(m_values.find(value)); }
317 template<Type::SafeValue K, class Compare>
318 requires std::strict_weak_order<Compare, const K&, const K&>
319 typename Set<K, Compare>::size_type Set<K, Compare>::count(const K& value) const { return m_values.count(value); }
321 template<Type::SafeValue K, class Compare>
322 requires std::strict_weak_order<Compare, const K&, const K&>
323 bool Set<K, Compare>::contains(const K& value) const { return m_values.contains(value); }
325 template<Type::SafeValue K, class Compare>
326 requires std::strict_weak_order<Compare, const K&, const K&>
327 typename Set<K, Compare>::iterator Set<K, Compare>::lower_bound(const K& value) { return iterator(m_values.lower_bound(value)); }
329 template<Type::SafeValue K, class Compare>
330 requires std::strict_weak_order<Compare, const K&, const K&>
331 typename Set<K, Compare>::const_iterator Set<K, Compare>::lower_bound(const K& value) const { return const_iterator(m_values.lower_bound(value)); }
333 template<Type::SafeValue K, class Compare>
334 requires std::strict_weak_order<Compare, const K&, const K&>
335 typename Set<K, Compare>::iterator Set<K, Compare>::upper_bound(const K& value) { return iterator(m_values.upper_bound(value)); }
337 template<Type::SafeValue K, class Compare>
338 requires std::strict_weak_order<Compare, const K&, const K&>
339 typename Set<K, Compare>::const_iterator Set<K, Compare>::upper_bound(const K& value) const { return const_iterator(m_values.upper_bound(value)); }
341 template<Type::SafeValue K, class Compare>
342 requires std::strict_weak_order<Compare, const K&, const K&>
343 Pair<typename Set<K, Compare>::iterator, typename Set<K, Compare>::iterator> Set<K, Compare>::equal_range(const K& value) {
344 auto range = m_values.equal_range(value);
345 return Pair<iterator, iterator>{iterator(range.first), iterator(range.second)};
348 template<Type::SafeValue K, class Compare>
349 requires std::strict_weak_order<Compare, const K&, const K&>
350 Pair<typename Set<K, Compare>::const_iterator, typename Set<K, Compare>::const_iterator> Set<K, Compare>::equal_range(const K& value) const {
351 auto range = m_values.equal_range(value);
352 return Pair<const_iterator, const_iterator>{const_iterator(range.first), const_iterator(range.second)};
355 template<Type::SafeValue K, class Compare>
356 requires std::strict_weak_order<Compare, const K&, const K&>
357 bool Set<K, Compare>::operator==(const Set& other) const {
358 if (size() != other.size())
361 auto right = other.begin();
362 for (; left != end(); ++left, ++right) {
363 if (!(*left == *right))
369 template<Type::SafeValue K, class Compare>
370 requires std::strict_weak_order<Compare, const K&, const K&>
371 bool Set<K, Compare>::operator!=(const Set& other) const { return !(*this == other); }
373 template<Type::SafeValue K, class Compare>
374 requires std::strict_weak_order<Compare, const K&, const K&>
375 bool Set<K, Compare>::operator<(const Set& other) const {
377 auto right = other.begin();
378 while (left != end() && right != other.end()) {
386 return left == end() && right != other.end();
389 template<Type::SafeValue K, class Compare>
390 requires std::strict_weak_order<Compare, const K&, const K&>
391 bool Set<K, Compare>::operator<=(const Set& other) const { return !(other < *this); }
393 template<Type::SafeValue K, class Compare>
394 requires std::strict_weak_order<Compare, const K&, const K&>
395 bool Set<K, Compare>::operator>(const Set& other) const { return other < *this; }
397 template<Type::SafeValue K, class Compare>
398 requires std::strict_weak_order<Compare, const K&, const K&>
399 bool Set<K, Compare>::operator>=(const Set& other) const { return !(*this < other); }