Debian Codegraph @

Utilities/std/cmext/enum_set

raw
1 // -*-c++-*-
2 // vim: set ft=cpp:
3
4 /* Distributed under the OSI-approved BSD 3-Clause License. See accompanying
5 file LICENSE.rst or https://cmake.org/licensing for details. */
6 #pragma once
7
8 #include <bitset>
9 #include <cstddef>
10 #include <initializer_list>
11 #include <iterator>
12 #include <limits>
13 #include <utility>
14
15 #include <cm/type_traits>
16
17 //
18 // Class enum_set offers the capability to manage a set of enum values.
19 // Only the 'enum class' type with unsigned base type is supported. Moreover,
20 // all definitions must be specified without a value.
21 //
22 // The methods offered by 'enum_set' are close as possible to the 'std::set'
23 // container as well as the methods from 'std::bitset'.
24 //
25 // Internally, this class use 'std::bitset' container to manage the
26 // set of enum.
27 //
28 // The size of the bitset is deduced from the underlying type of
29 // the enum or can be set explicitly as template parameter:
30 //
31 // enum class Example : unsigned { A, B, C, D };
32 // using ExampleSet = enum_set<Example, 4>;
33 //
34 // To facilitate the usage of the enum_set, operators '+' and '|' can be used
35 // as alternate to the 'initializer_list':
36 //
37 // auto set1 = Example::A | Example::B | Example::C;
38 // auto set2 = Example::A + Example::B;
39 // set2.set(Example::C | Example::D);
40 //
41
42 namespace cm {
43
44 template <typename EnumSet>
45 class enum_set_iterator
46 {
47 public:
48 enum_set_iterator() = default;
49 enum_set_iterator(enum_set_iterator const& other) = default;
50
51 using iterator_category = std::bidirectional_iterator_tag;
52 using value_type = typename EnumSet::value_type;
53 using difference_type = typename EnumSet::difference_type;
54 using reference = typename EnumSet::reference;
55 using pointer = typename EnumSet::pointer;
56
57 enum_set_iterator& operator++()
58 {
59 while (++this->Index < this->Set->max_size() &&
60 !this->Set->test(this->Index))
61 ;
62
63 return *this;
64 }
65 enum_set_iterator operator++(int)
66 {
67 auto retval = *this;
68 ++(*this);
69 return retval;
70 }
71
72 enum_set_iterator& operator--()
73 {
74 if (this->Index == 0) {
75 return *this;
76 }
77
78 while (!this->Set->test(--this->Index) && this->Index != 0)
79 ;
80
81 return *this;
82 }
83 enum_set_iterator operator--(int)
84 {
85 auto retval = *this;
86 --(*this);
87 return retval;
88 }
89
90 reference operator*() const { return static_cast<reference>(this->Index); }
91
92 bool operator==(enum_set_iterator other) const
93 {
94 return (this->Set == other.Set) && (this->Index == other.Index);
95 }
96
97 bool operator!=(enum_set_iterator other) const { return !(*this == other); }
98
99 private:
100 friend EnumSet;
101
102 using size_type = typename EnumSet::size_type;
103
104 enum_set_iterator(EnumSet* set, bool at_end = false)
105 : Set(set)
106 {
107 if (at_end || this->Set->empty()) {
108 this->Index = this->Set->max_size();
109 } else {
110 while (!this->Set->test(this->Index) &&
111 ++this->Index < this->Set->max_size())
112 ;
113 }
114 }
115 enum_set_iterator(EnumSet* set, size_type pos)
116 : Index(pos)
117 , Set(set)
118 {
119 }
120
121 std::size_t Index = 0;
122 EnumSet* Set = nullptr;
123 };
124
125 template <
126 typename Enum,
127 std::size_t Size =
128 std::numeric_limits<typename std::underlying_type<Enum>::type>::digits,
129 typename cm::enable_if_t<
130 cm::is_scoped_enum<Enum>::value &&
131 std::is_unsigned<typename std::underlying_type<Enum>::type>::value,
132 int> = 0>
133 class enum_set
134 {
135 public:
136 static constexpr std::size_t set_size = Size;
137
138 using key_type = Enum;
139 using value_type = Enum;
140 using size_type = typename std::underlying_type<Enum>::type;
141 using difference_type = size_type;
142 using reference = Enum;
143 using const_reference = Enum;
144 using pointer = Enum const*;
145 using const_pointer = Enum const*;
146
147 using iterator = enum_set_iterator<enum_set>;
148 using const_iterator = enum_set_iterator<enum_set const>;
149 using reverse_iterator = std::reverse_iterator<iterator>;
150 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
151
152 constexpr enum_set() noexcept {}
153 enum_set(key_type e) { this->insert(e); }
154 enum_set(enum_set const& other) noexcept { this->insert(other); }
155 template <typename E,
156 typename cm::enable_if_t<std::is_same<Enum, E>::value, int> = 0>
157 enum_set(enum_set<E> const& other) noexcept
158 {
159 static_assert(Size < enum_set<E>::set_size, "Incompatible sizes");
160
161 this->insert(other.cbegin(), other.cend());
162 }
163 enum_set(std::initializer_list<value_type> list) { this->insert(list); }
164
165 enum_set& operator=(key_type e)
166 {
167 this->Set.reset();
168 this->insert(e);
169 return *this;
170 }
171 enum_set& operator=(enum_set const& other) noexcept
172 {
173 this->Set.reset();
174 this->Set |= other.Set;
175 return *this;
176 }
177 enum_set& operator=(std::initializer_list<value_type> list)
178 {
179 this->Set.reset();
180 this->insert(list);
181 return *this;
182 }
183
184 // Iterators
185 iterator begin() noexcept { return iterator(this); }
186 const_iterator begin() const noexcept { return const_iterator(this); }
187 const_iterator cbegin() const noexcept { return const_iterator(this); }
188
189 iterator end() noexcept { return iterator(this, true); }
190 const_iterator end() const noexcept { return const_iterator(this, true); }
191 const_iterator cend() const noexcept { return const_iterator(this, true); }
192
193 reverse_iterator rbegin() noexcept { return reverse_iterator(this->end()); }
194 const_reverse_iterator rbegin() const noexcept
195 {
196 return const_reverse_iterator(this->end());
197 }
198 const_reverse_iterator crbegin() const noexcept
199 {
200 return const_reverse_iterator(this->cend());
201 }
202
203 reverse_iterator rend() noexcept { return reverse_iterator(this->begin()); }
204 const_reverse_iterator rend() const noexcept
205 {
206 return const_reverse_iterator(this->begin());
207 }
208 const_reverse_iterator crend() const noexcept
209 {
210 return const_reverse_iterator(this->cbegin());
211 }
212
213 // Capacity
214 bool empty() const noexcept { return this->Set.none(); }
215
216 size_type size() const noexcept { return this->Set.count(); }
217
218 size_type max_size() const noexcept { return this->Set.size(); }
219
220 // Modifiers
221
222 // set all elements
223 enum_set& set()
224 {
225 this->Set.set();
226 return *this;
227 }
228 enum_set& set(key_type e)
229 {
230 this->insert(e);
231 return *this;
232 }
233 enum_set& set(enum_set const& other) noexcept
234 {
235 this->insert(other);
236 return *this;
237 }
238 enum_set& set(std::initializer_list<value_type> list)
239 {
240 this->insert(list);
241 return *this;
242 }
243 // alternate syntax for bit set
244 enum_set& operator+=(key_type e) { return this->set(e); }
245 enum_set& operator+=(enum_set const& other) noexcept
246 {
247 return this->set(other);
248 }
249 enum_set& operator+=(std::initializer_list<value_type> list)
250 {
251 return this->set(list);
252 }
253 // alternate syntax for bit set
254 enum_set& operator|=(key_type e) { return this->set(e); }
255 enum_set& operator|=(enum_set const& other) noexcept
256 {
257 return this->set(other);
258 }
259 enum_set& operator|=(std::initializer_list<value_type> list)
260 {
261 return this->set(list);
262 }
263
264 // reset all elements
265 void clear() noexcept { this->Set.reset(); }
266 enum_set& reset()
267 {
268 this->Set.reset();
269 return *this;
270 }
271 enum_set& reset(key_type e)
272 {
273 this->erase(e);
274 return *this;
275 }
276 enum_set& reset(enum_set const& other) noexcept
277 {
278 this->erase(other);
279 return *this;
280 }
281 enum_set& reset(std::initializer_list<value_type> list)
282 {
283 this->erase(list);
284 return *this;
285 }
286 // alternate syntax for bit reset
287 enum_set& operator-=(key_type e) { return this->reset(e); }
288 enum_set& operator-=(enum_set const& other) noexcept
289 {
290 return this->reset(other);
291 }
292 enum_set& operator-=(std::initializer_list<value_type> list)
293 {
294 return this->reset(list);
295 }
296
297 // toggle the specified enum
298 enum_set& flip(key_type e)
299 {
300 this->Set.flip(static_cast<size_type>(e));
301 return *this;
302 }
303 // toggle all the enums stored in the other enum_set
304 enum_set& flip(enum_set const& other) noexcept
305 {
306 this->Set ^= other.Set;
307 return *this;
308 }
309 // toggle all the enums specified in the list
310 enum_set& flip(std::initializer_list<value_type> list)
311 {
312 for (auto e : list) {
313 this->Set.flip(static_cast<size_type>(e));
314 }
315 return *this;
316 }
317 // alternate syntax for bit toggle
318 enum_set& operator^=(key_type key) { return this->flip(key); }
319 // toggle all the enums stored in the other enum_set
320 enum_set& operator^=(enum_set const& other) noexcept
321 {
322 return this->flip(other);
323 }
324 // toggle all the enums specified in the list
325 enum_set& operator^=(std::initializer_list<value_type> list)
326 {
327 return this->flip(list);
328 }
329
330 std::pair<iterator, bool> insert(key_type value)
331 {
332 auto exist = this->contains(value);
333 if (!exist) {
334 this->Set.set(static_cast<size_type>(value));
335 }
336
337 return { iterator(this, static_cast<size_type>(value)), !exist };
338 }
339 template <typename InputIt>
340 void insert(InputIt first, InputIt last)
341 {
342 for (auto i = first; i != last; i++) {
343 this->insert(*i);
344 }
345 }
346 void insert(enum_set const& other) noexcept { this->Set |= other.Set; }
347 void insert(std::initializer_list<value_type> list)
348 {
349 for (auto e : list) {
350 this->Set.set(static_cast<size_type>(e));
351 }
352 }
353
354 size_type erase(key_type key)
355 {
356 if (this->contains(key)) {
357 this->Set.reset(static_cast<size_type>(key));
358 return 1;
359 }
360
361 return 0;
362 }
363 iterator erase(iterator pos)
364 {
365 this->erase(*pos++);
366 return pos;
367 }
368 iterator erase(const_iterator pos)
369 {
370 this->erase(*pos++);
371
372 return pos == this->cend() ? this->end()
373 : iterator(this, static_cast<size_type>(*pos));
374 }
375 void erase(enum_set const& other) noexcept { this->Set &= ~other.Set; }
376 void erase(std::initializer_list<value_type> list)
377 {
378 for (auto e : list) {
379 this->Set.reset(static_cast<size_type>(e));
380 }
381 }
382
383 void swap(enum_set& other) noexcept
384 {
385 auto tmp = this->Set;
386 this->Set = other.Set;
387 other.Set = tmp;
388 }
389
390 // Lookup
391 size_type count(key_type e) const { return this->contains(e) ? 1 : 0; }
392
393 iterator find(key_type e)
394 {
395 if (this->contains(e)) {
396 return iterator(this, static_cast<size_type>(e));
397 }
398 return this->end();
399 }
400 const_iterator find(key_type e) const
401 {
402 if (this->contains(e)) {
403 return const_iterator(this, static_cast<size_type>(e));
404 }
405 return this->end();
406 }
407
408 // Checks
409 bool contains(key_type e) const
410 {
411 return this->Set.test(static_cast<size_type>(e));
412 }
413
414 bool all() const { return this->Set.all(); }
415 bool any() const { return this->Set.any(); }
416 bool none() const { return this->Set.none(); }
417 // alternate syntax to none()
418 bool operator!() const { return this->Set.none(); }
419
420 bool all_of(enum_set const& set) const
421 {
422 auto result = set;
423 result.Set &= this->Set;
424 return result == set;
425 }
426 bool any_of(enum_set const& set) const
427 {
428 auto result = set;
429 result.Set &= this->Set;
430 return result.any();
431 }
432 bool none_of(enum_set const& set) const
433 {
434 auto result = set;
435 result.Set &= this->Set;
436 return result.none();
437 }
438
439 private:
440 template <typename E, std::size_t S>
441 friend inline bool operator==(enum_set<E, S> const& lhs,
442 enum_set<E, S> const& rhs) noexcept;
443
444 template <typename E, std::size_t S, typename Predicate>
445 friend inline void erase_if(enum_set<E, S>& set, Predicate pred);
446
447 friend class enum_set_iterator<enum_set>;
448 friend class enum_set_iterator<enum_set const>;
449
450 bool test(size_type pos) const { return this->Set.test(pos); }
451
452 std::bitset<Size> Set;
453 };
454
455 // non-member functions for enum_set
456 template <typename Enum, std::size_t Size>
457 inline enum_set<Enum, Size> operator+(enum_set<Enum, Size> const& lhs,
458 Enum rhs)
459 {
460 return enum_set<Enum, Size>{ lhs } += rhs;
461 }
462 template <typename Enum, std::size_t Size>
463 inline enum_set<Enum, Size> operator+(enum_set<Enum, Size> const& lhs,
464 enum_set<Enum, Size> const& rhs) noexcept
465 {
466 return enum_set<Enum, Size>{ lhs } += rhs;
467 }
468 template <typename Enum, std::size_t Size>
469 inline enum_set<Enum, Size> operator+(enum_set<Enum, Size> const& lhs,
470 std::initializer_list<Enum> const rhs)
471 {
472 return enum_set<Enum, Size>{ lhs } += rhs;
473 }
474
475 template <typename Enum, std::size_t Size>
476 inline cm::enum_set<Enum, Size> operator|(cm::enum_set<Enum, Size> const& lhs,
477 Enum rhs)
478 {
479 return enum_set<Enum, Size>{ lhs } |= rhs;
480 }
481 template <typename Enum, std::size_t Size>
482 inline cm::enum_set<Enum, Size> operator|(Enum lhs,
483 cm::enum_set<Enum, Size> const& rhs)
484 {
485 return enum_set<Enum, Size>{ lhs } |= rhs;
486 }
487 template <typename Enum, std::size_t Size>
488 inline cm::enum_set<Enum, Size> operator|(cm::enum_set<Enum, Size> const& lhs,
489 cm::enum_set<Enum, Size> const& rhs)
490 {
491 return enum_set<Enum, Size>{ lhs } |= rhs;
492 }
493
494 template <typename Enum, std::size_t Size>
495 inline enum_set<Enum, Size> operator-(enum_set<Enum, Size> const& lhs,
496 Enum rhs)
497 {
498 return enum_set<Enum, Size>{ lhs } -= rhs;
499 }
500 template <typename Enum, std::size_t Size>
501 inline enum_set<Enum, Size> operator-(enum_set<Enum, Size> const& lhs,
502 enum_set<Enum, Size> const& rhs) noexcept
503 {
504 return enum_set<Enum, Size>{ lhs } -= rhs;
505 }
506 template <typename Enum, std::size_t Size>
507 inline enum_set<Enum, Size> operator-(enum_set<Enum, Size> const& lhs,
508 std::initializer_list<Enum> const rhs)
509 {
510 return enum_set<Enum, Size>{ lhs } -= rhs;
511 }
512
513 template <typename Enum, std::size_t Size>
514 inline enum_set<Enum, Size> operator^(enum_set<Enum, Size> const& lhs,
515 Enum rhs)
516 {
517 return enum_set<Enum, Size>{ lhs } ^= rhs;
518 }
519 template <typename Enum, std::size_t Size>
520 inline enum_set<Enum, Size> operator^(enum_set<Enum, Size> const& lhs,
521 enum_set<Enum, Size> const& rhs) noexcept
522 {
523 return enum_set<Enum, Size>{ lhs } ^= rhs;
524 }
525 template <typename Enum, std::size_t Size>
526 inline enum_set<Enum, Size> operator^(enum_set<Enum, Size> const& lhs,
527 std::initializer_list<Enum> const rhs)
528 {
529 return enum_set<Enum, Size>{ lhs } ^= rhs;
530 }
531
532 template <typename Enum, std::size_t Size>
533 inline bool operator==(enum_set<Enum, Size> const& lhs,
534 enum_set<Enum, Size> const& rhs) noexcept
535 {
536 return lhs.Set == rhs.Set;
537 }
538
539 template <typename Enum, std::size_t Size>
540 inline bool operator!=(enum_set<Enum, Size> const& lhs,
541 enum_set<Enum, Size> const& rhs) noexcept
542 {
543 return !(lhs == rhs);
544 }
545
546 template <typename Enum, std::size_t Size>
547 inline void erase(enum_set<Enum, Size>& set, Enum value)
548 {
549 set.erase(value);
550 }
551
552 template <typename Enum, std::size_t Size, typename Predicate>
553 inline void erase_if(enum_set<Enum, Size>& set, Predicate pred)
554 {
555 for (std::size_t index = 0; index < set.Set.size(); ++index) {
556 if (set.Set.test(index) && pred(static_cast<Enum>(index))) {
557 set.Set.reset(index);
558 }
559 }
560 }
561 } // namespace cm
562
563 //
564 // WARNING: the following two operators rely on the enum_set_traits<Enum>
565 // struct definition.
566 // The macro CM_ENUM_SET_TRAITS(EnumSet) can be used to define this structure.
567 //
568 // Notes:
569 // When CM_ENUM_SET_TRAITS is used, the following restrictions applies:
570 // * Due to language constraints, the enum_set_traits specialization must
571 // occur outside of any namespace or function definition.
572 // * Only one enum_set instantiation is supported per enum class type.
573 //
574
575 template <typename Enum>
576 struct cm_enum_set_traits
577 {
578 };
579
580 namespace cm {
581 template <typename Enum, typename = cm::void_t<>>
582 struct is_enum_set : std::false_type
583 {
584 };
585 template <typename Enum>
586 struct is_enum_set<Enum, cm::void_t<typename cm_enum_set_traits<Enum>::type>>
587 : std::true_type
588 {
589 };
590 }
591
592 #if defined(__SUNPRO_CC) && defined(__sparc)
593 // Oracle DeveloperStudio C++ compiler on Solaris/Sparc crash on the following
594 // template declarations, so declare explicitly the operators.
595
596 // Helper macro to define the enum_set_traits struct specialization.
597 # define CM_ENUM_SET_TRAITS(E) \
598 template <> \
599 struct cm_enum_set_traits<E::value_type> \
600 { \
601 using type = E; \
602 using value_type = E::value_type; \
603 }; \
604 \
605 inline E operator+(E::value_type lhs, E::value_type rhs) \
606 { \
607 return { lhs, rhs }; \
608 } \
609 \
610 inline E operator|(E::value_type lhs, E::value_type rhs) \
611 { \
612 return { lhs, rhs }; \
613 }
614
615 #else
616
617 // Helper macro to define the enum_set_traits struct specialization.
618 # define CM_ENUM_SET_TRAITS(E) \
619 template <> \
620 struct cm_enum_set_traits<E::value_type> \
621 { \
622 using type = E; \
623 using value_type = E::value_type; \
624 };
625
626 template <typename Enum,
627 typename cm::enable_if_t<cm::is_enum_set<Enum>::value, int> = 0>
628 inline typename cm_enum_set_traits<Enum>::type operator+(Enum lhs, Enum rhs)
629 {
630 return { lhs, rhs };
631 }
632 // Alternate syntax
633 template <typename Enum,
634 typename cm::enable_if_t<cm::is_enum_set<Enum>::value, int> = 0>
635 inline typename cm_enum_set_traits<Enum>::type operator|(Enum lhs, Enum rhs)
636 {
637 return { lhs, rhs };
638 }
639 #endif