Utilities/std/cmext/enum_set

   1 // -*-c++-*-
   2 // vim: set ft=cpp:
   3
   4 /* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   5    file Copyright.txt 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 'enum class' with unsigned base type are supported.
  20 //
  21 // The methods offered by 'enum_set' are close as possible to the 'std::set'
  22 // container plus some useful methods from 'std::bitset' like 'flip'.
  23 //
  24 // Internally, this class use 'std::bitset' container to manage the
  25 // set of enum. The size of the bitset is deduced from the underlying type of
  26 // the enum.
  27 //
  28
  29 namespace cm {
  30
  31 template <typename EnumSet>
  32 class enum_set_iterator
  33 {
  34 public:
  35   enum_set_iterator() = default;
  36   enum_set_iterator(const enum_set_iterator& other) = default;
  37
  38   using iterator_category = std::bidirectional_iterator_tag;
  39   using value_type = typename EnumSet::value_type;
  40   using difference_type = typename EnumSet::difference_type;
  41   using reference = typename EnumSet::reference;
  42   using pointer = typename EnumSet::pointer;
  43
  44   enum_set_iterator& operator++()
  45   {
  46     while (++this->Index < this->Set->max_size() &&
  47            !this->Set->test(this->Index))
  48       ;
  49
  50     return *this;
  51   }
  52   enum_set_iterator operator++(int)
  53   {
  54     auto retval = *this;
  55     ++(*this);
  56     return retval;
  57   }
  58
  59   enum_set_iterator& operator--()
  60   {
  61     if (this->Index == 0) {
  62       return *this;
  63     }
  64
  65     while (!this->Set->test(--this->Index) && this->Index != 0)
  66       ;
  67
  68     return *this;
  69   }
  70   enum_set_iterator operator--(int)
  71   {
  72     auto retval = *this;
  73     --(*this);
  74     return retval;
  75   }
  76
  77   reference operator*() const { return static_cast<reference>(this->Index); }
  78
  79   bool operator==(enum_set_iterator other) const
  80   {
  81     return (this->Set == other.Set) && (this->Index == other.Index);
  82   }
  83
  84   bool operator!=(enum_set_iterator other) const { return !(*this == other); }
  85
  86 private:
  87   friend EnumSet;
  88
  89   using size_type = typename EnumSet::size_type;
  90
  91   enum_set_iterator(EnumSet* set, bool at_end = false)
  92     : Set(set)
  93   {
  94     if (at_end || this->Set->empty()) {
  95       this->Index = this->Set->max_size();
  96     } else {
  97       while (!this->Set->test(this->Index) &&
  98              ++this->Index < this->Set->max_size())
  99         ;
 100     }
 101   }
 102   enum_set_iterator(EnumSet* set, size_type pos)
 103     : Index(pos)
 104     , Set(set)
 105   {
 106   }
 107
 108   std::size_t Index = 0;
 109   EnumSet* Set = nullptr;
 110 };
 111
 112 template <
 113   typename Enum,
 114   typename cm::enable_if_t<
 115     std::is_enum<Enum>::value &&
 116       std::is_unsigned<typename std::underlying_type<Enum>::type>::value,
 117     int> = 0>
 118 class enum_set
 119 {
 120 public:
 121   using key_type = Enum;
 122   using value_type = Enum;
 123   using size_type = typename std::underlying_type<Enum>::type;
 124   using difference_type = size_type;
 125   using reference = Enum;
 126   using const_reference = Enum;
 127   using pointer = const Enum*;
 128   using const_pointer = const Enum*;
 129
 130   using iterator = enum_set_iterator<enum_set>;
 131   using const_iterator = enum_set_iterator<const enum_set>;
 132   using reverse_iterator = std::reverse_iterator<iterator>;
 133   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 134
 135   constexpr enum_set() noexcept = default;
 136   enum_set(const enum_set& other) noexcept { this->insert(other); }
 137   enum_set(std::initializer_list<value_type> list) { this->insert(list); }
 138
 139   enum_set& operator=(const enum_set& other) noexcept
 140   {
 141     this->Set.reset();
 142     this->Set |= other.Set;
 143     return *this;
 144   }
 145   enum_set& operator=(std::initializer_list<value_type> list)
 146   {
 147     this->Set.reset();
 148     this->insert(list);
 149   }
 150
 151   // Iterators
 152   iterator begin() noexcept { return iterator(this); }
 153   const_iterator begin() const noexcept { return const_iterator(this); }
 154   const_iterator cbegin() const noexcept { return const_iterator(this); }
 155
 156   iterator end() noexcept { return iterator(this, true); }
 157   const_iterator end() const noexcept { return const_iterator(this, true); }
 158   const_iterator cend() const noexcept { return const_iterator(this, true); }
 159
 160   reverse_iterator rbegin() noexcept { return reverse_iterator(this->end()); }
 161   const_reverse_iterator rbegin() const noexcept
 162   {
 163     return const_reverse_iterator(this->end());
 164   }
 165   const_reverse_iterator crbegin() const noexcept
 166   {
 167     return const_reverse_iterator(this->cend());
 168   }
 169
 170   reverse_iterator rend() noexcept { return reverse_iterator(this->begin()); }
 171   const_reverse_iterator rend() const noexcept
 172   {
 173     return const_reverse_iterator(this->begin());
 174   }
 175   const_reverse_iterator crend() const noexcept
 176   {
 177     return const_reverse_iterator(this->cbegin());
 178   }
 179
 180   // Capacity
 181   bool empty() const noexcept { return this->Set.none(); }
 182
 183   size_type size() const noexcept { return this->Set.count(); }
 184
 185   size_type max_size() const noexcept { return this->Set.size(); }
 186
 187   // Modifiers
 188   void clear() noexcept { this->Set.reset(); }
 189
 190   enum_set& operator+=(key_type e)
 191   {
 192     this->insert(e);
 193     return *this;
 194   }
 195   enum_set& operator+=(const enum_set& other) noexcept
 196   {
 197     this->erase(other);
 198     return *this;
 199   }
 200   enum_set& operator+=(std::initializer_list<value_type> list)
 201   {
 202     this->insert(list);
 203     return *this;
 204   }
 205
 206   enum_set& operator-=(key_type e)
 207   {
 208     this->erase(e);
 209     return *this;
 210   }
 211   enum_set& operator-=(const enum_set& other) noexcept
 212   {
 213     this->erase(other);
 214     return *this;
 215   }
 216   enum_set& operator-=(std::initializer_list<value_type> list)
 217   {
 218     this->erase(list);
 219     return *this;
 220   }
 221
 222   std::pair<iterator, bool> insert(value_type value)
 223   {
 224     auto exist = this->contains(value);
 225     if (!exist) {
 226       this->Set.set(static_cast<size_type>(value));
 227     }
 228
 229     return { iterator(this, static_cast<size_type>(value)), !exist };
 230   }
 231   template <typename InputIt>
 232   void insert(InputIt first, InputIt last)
 233   {
 234     for (auto i = first; i != last; i++) {
 235       this->insert(*i);
 236     }
 237   }
 238   void insert(const enum_set& other) noexcept { this->Set |= other.Set; }
 239   void insert(std::initializer_list<value_type> list)
 240   {
 241     for (auto e : list) {
 242       this->Set.set(static_cast<size_type>(e));
 243     }
 244   }
 245
 246   size_type erase(key_type key)
 247   {
 248     if (this->contains(key)) {
 249       this->Set.reset(static_cast<size_type>(key));
 250       return 1;
 251     }
 252
 253     return 0;
 254   }
 255   iterator erase(iterator pos)
 256   {
 257     this->erase(*pos++);
 258     return pos;
 259   }
 260   iterator erase(const_iterator pos)
 261   {
 262     this->erase(*pos++);
 263
 264     return pos == this->cend() ? this->end()
 265                                : iterator(this, static_cast<size_type>(*pos));
 266   }
 267   void erase(const enum_set& other) noexcept { this->Set &= ~other.Set; }
 268   void erase(std::initializer_list<value_type> list)
 269   {
 270     for (auto e : list) {
 271       this->Set.reset(static_cast<size_type>(e));
 272     }
 273   }
 274
 275   void swap(enum_set& other) noexcept
 276   {
 277     auto tmp = this->Set;
 278     this->Set = other.Set;
 279     other.Set = tmp;
 280   }
 281
 282   // toggle the specified enum
 283   void flip(key_type key) { this->Set.flip(static_cast<size_type>(key)); }
 284   // toggle all the enums stored in the other enum_set
 285   void flip(const enum_set& other) noexcept { this->Set ^= other.Set; }
 286   // toggle all the enums specified in the list
 287   void flip(std::initializer_list<value_type> list)
 288   {
 289     for (auto e : list) {
 290       this->Set.flip(static_cast<size_type>(e));
 291     }
 292   }
 293
 294   // Lookup
 295   size_type count(key_type e) const { return this->contains(e) ? 1 : 0; }
 296
 297   iterator find(key_type e)
 298   {
 299     if (this->contains(e)) {
 300       return iterator(this, static_cast<size_type>(e));
 301     } else {
 302       return this->end();
 303     }
 304   }
 305   const_iterator find(key_type e) const
 306   {
 307     if (this->contains(e)) {
 308       return const_iterator(this, static_cast<size_type>(e));
 309     } else {
 310       return this->end();
 311     }
 312   }
 313
 314   bool contains(key_type e) const
 315   {
 316     return this->Set.test(static_cast<size_type>(e));
 317   }
 318
 319 private:
 320   template <typename E, typename Predicate>
 321   friend inline void erase_if(enum_set<E>& set, Predicate pred);
 322
 323   friend class enum_set_iterator<enum_set>;
 324   friend class enum_set_iterator<const enum_set>;
 325
 326   bool test(size_type pos) const { return this->Set.test(pos); }
 327
 328   std::bitset<std::numeric_limits<size_type>::digits> Set;
 329 };
 330
 331 // non-member functions for enum_set
 332 template <typename Enum>
 333 inline enum_set<Enum> operator+(const enum_set<Enum>& lhs, Enum rhs)
 334 {
 335   return enum_set<Enum>(lhs) += rhs;
 336 }
 337 template <typename Enum>
 338 inline enum_set<Enum> operator+(const enum_set<Enum>& lhs,
 339                                 const enum_set<Enum>& rhs) noexcept
 340 {
 341   return enum_set<Enum>(lhs) += rhs;
 342 }
 343 template <typename Enum>
 344 inline enum_set<Enum> operator+(const enum_set<Enum>& lhs,
 345                                 const std::initializer_list<Enum> rhs)
 346 {
 347   return enum_set<Enum>(lhs) += rhs;
 348 }
 349
 350 template <typename Enum>
 351 inline enum_set<Enum> operator-(const enum_set<Enum>& lhs, Enum rhs)
 352 {
 353   return enum_set<Enum>(lhs) -= rhs;
 354 }
 355 template <typename Enum>
 356 inline enum_set<Enum> operator-(const enum_set<Enum>& lhs,
 357                                 const enum_set<Enum>& rhs) noexcept
 358 {
 359   return enum_set<Enum>(lhs) -= rhs;
 360 }
 361 template <typename Enum>
 362 inline enum_set<Enum> operator-(const enum_set<Enum>& lhs,
 363                                 const std::initializer_list<Enum> rhs)
 364 {
 365   return enum_set<Enum>(lhs) -= rhs;
 366 }
 367
 368 template <typename Enum>
 369 inline bool operator==(const enum_set<Enum>& lhs,
 370                        const enum_set<Enum>& rhs) noexcept
 371 {
 372   return lhs == rhs;
 373 }
 374
 375 template <typename Enum>
 376 inline bool operator!=(const enum_set<Enum>& lhs,
 377                        const enum_set<Enum>& rhs) noexcept
 378 {
 379   return !(lhs == rhs);
 380 }
 381
 382 template <typename Enum>
 383 inline void erase(enum_set<Enum>& set, Enum value)
 384 {
 385   set.erase(value);
 386 }
 387
 388 template <typename Enum, typename Predicate>
 389 inline void erase_if(enum_set<Enum>& set, Predicate pred)
 390 {
 391   for (std::size_t index = 0; index < set.Set.size(); ++index) {
 392     if (set.Set.test(index) && pred(static_cast<Enum>(index))) {
 393       set.Set.reset(index);
 394     }
 395   }
 396 }
 397 } // namespace cm