Utilities/std/cmext/enum_set

// -*-c++-*-
// vim: set ft=cpp:

/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file LICENSE.rst or https://cmake.org/licensing for details.  */
#pragma once

#include <bitset>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <utility>

#include <cm/type_traits>

//
// Class enum_set offers the capability to manage a set of enum values.
// Only the 'enum class' type with unsigned base type is supported. Moreover,
// all definitions must be specified without a value.
//
// The methods offered by 'enum_set' are close as possible to the 'std::set'
// container as well as the methods from 'std::bitset'.
//
// Internally, this class use 'std::bitset' container to manage the
// set of enum.
//
// The size of the bitset is deduced from the underlying type of
// the enum or can be set explicitly as template parameter:
//
// enum class Example : unsigned { A, B, C, D };
// using ExampleSet = enum_set<Example, 4>;
//
// To facilitate the usage of the enum_set, operators '+' and '|' can be used
// as alternate to the 'initializer_list':
//
//  auto set1 = Example::A | Example::B | Example::C;
//  auto set2 = Example::A + Example::B;
//  set2.set(Example::C | Example::D);
//

namespace cm {

template <typename EnumSet>
class enum_set_iterator
{
public:
  enum_set_iterator() = default;
  enum_set_iterator(enum_set_iterator const& other) = default;

  using iterator_category = std::bidirectional_iterator_tag;
  using value_type = typename EnumSet::value_type;
  using difference_type = typename EnumSet::difference_type;
  using reference = typename EnumSet::reference;
  using pointer = typename EnumSet::pointer;

  enum_set_iterator& operator++()
  {
    while (++this->Index < this->Set->max_size() &&
           !this->Set->test(this->Index))
      ;

    return *this;
  }
  enum_set_iterator operator++(int)
  {
    auto retval = *this;
    ++(*this);
    return retval;
  }

  enum_set_iterator& operator--()
  {
    if (this->Index == 0) {
      return *this;
    }

    while (!this->Set->test(--this->Index) && this->Index != 0)
      ;

    return *this;
  }
  enum_set_iterator operator--(int)
  {
    auto retval = *this;
    --(*this);
    return retval;
  }

  reference operator*() const { return static_cast<reference>(this->Index); }

  bool operator==(enum_set_iterator other) const
  {
    return (this->Set == other.Set) && (this->Index == other.Index);
  }

  bool operator!=(enum_set_iterator other) const { return !(*this == other); }

private:
  friend EnumSet;

  using size_type = typename EnumSet::size_type;

  enum_set_iterator(EnumSet* set, bool at_end = false)
    : Set(set)
  {
    if (at_end || this->Set->empty()) {
      this->Index = this->Set->max_size();
    } else {
      while (!this->Set->test(this->Index) &&
             ++this->Index < this->Set->max_size())
        ;
    }
  }
  enum_set_iterator(EnumSet* set, size_type pos)
    : Index(pos)
    , Set(set)
  {
  }

  std::size_t Index = 0;
  EnumSet* Set = nullptr;
};

template <
  typename Enum,
  std::size_t Size =
    std::numeric_limits<typename std::underlying_type<Enum>::type>::digits,
  typename cm::enable_if_t<
    cm::is_scoped_enum<Enum>::value &&
      std::is_unsigned<typename std::underlying_type<Enum>::type>::value,
    int> = 0>
class enum_set
{
public:
  static constexpr std::size_t set_size = Size;

  using key_type = Enum;
  using value_type = Enum;
  using size_type = typename std::underlying_type<Enum>::type;
  using difference_type = size_type;
  using reference = Enum;
  using const_reference = Enum;
  using pointer = Enum const*;
  using const_pointer = Enum const*;

  using iterator = enum_set_iterator<enum_set>;
  using const_iterator = enum_set_iterator<enum_set const>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  constexpr enum_set() noexcept {}
  enum_set(key_type e) { this->insert(e); }
  enum_set(enum_set const& other) noexcept { this->insert(other); }
  template <typename E,
            typename cm::enable_if_t<std::is_same<Enum, E>::value, int> = 0>
  enum_set(enum_set<E> const& other) noexcept
  {
    static_assert(Size < enum_set<E>::set_size, "Incompatible sizes");

    this->insert(other.cbegin(), other.cend());
  }
  enum_set(std::initializer_list<value_type> list) { this->insert(list); }

  enum_set& operator=(key_type e)
  {
    this->Set.reset();
    this->insert(e);
    return *this;
  }
  enum_set& operator=(enum_set const& other) noexcept
  {
    this->Set.reset();
    this->Set |= other.Set;
    return *this;
  }
  enum_set& operator=(std::initializer_list<value_type> list)
  {
    this->Set.reset();
    this->insert(list);
    return *this;
  }

  // Iterators
  iterator begin() noexcept { return iterator(this); }
  const_iterator begin() const noexcept { return const_iterator(this); }
  const_iterator cbegin() const noexcept { return const_iterator(this); }

  iterator end() noexcept { return iterator(this, true); }
  const_iterator end() const noexcept { return const_iterator(this, true); }
  const_iterator cend() const noexcept { return const_iterator(this, true); }

  reverse_iterator rbegin() noexcept { return reverse_iterator(this->end()); }
  const_reverse_iterator rbegin() const noexcept
  {
    return const_reverse_iterator(this->end());
  }
  const_reverse_iterator crbegin() const noexcept
  {
    return const_reverse_iterator(this->cend());
  }

  reverse_iterator rend() noexcept { return reverse_iterator(this->begin()); }
  const_reverse_iterator rend() const noexcept
  {
    return const_reverse_iterator(this->begin());
  }
  const_reverse_iterator crend() const noexcept
  {
    return const_reverse_iterator(this->cbegin());
  }

  // Capacity
  bool empty() const noexcept { return this->Set.none(); }

  size_type size() const noexcept { return this->Set.count(); }

  size_type max_size() const noexcept { return this->Set.size(); }

  // Modifiers

  // set all elements
  enum_set& set()
  {
    this->Set.set();
    return *this;
  }
  enum_set& set(key_type e)
  {
    this->insert(e);
    return *this;
  }
  enum_set& set(enum_set const& other) noexcept
  {
    this->insert(other);
    return *this;
  }
  enum_set& set(std::initializer_list<value_type> list)
  {
    this->insert(list);
    return *this;
  }
  // alternate syntax for bit set
  enum_set& operator+=(key_type e) { return this->set(e); }
  enum_set& operator+=(enum_set const& other) noexcept
  {
    return this->set(other);
  }
  enum_set& operator+=(std::initializer_list<value_type> list)
  {
    return this->set(list);
  }
  // alternate syntax for bit set
  enum_set& operator|=(key_type e) { return this->set(e); }
  enum_set& operator|=(enum_set const& other) noexcept
  {
    return this->set(other);
  }
  enum_set& operator|=(std::initializer_list<value_type> list)
  {
    return this->set(list);
  }

  // reset all elements
  void clear() noexcept { this->Set.reset(); }
  enum_set& reset()
  {
    this->Set.reset();
    return *this;
  }
  enum_set& reset(key_type e)
  {
    this->erase(e);
    return *this;
  }
  enum_set& reset(enum_set const& other) noexcept
  {
    this->erase(other);
    return *this;
  }
  enum_set& reset(std::initializer_list<value_type> list)
  {
    this->erase(list);
    return *this;
  }
  // alternate syntax for bit reset
  enum_set& operator-=(key_type e) { return this->reset(e); }
  enum_set& operator-=(enum_set const& other) noexcept
  {
    return this->reset(other);
  }
  enum_set& operator-=(std::initializer_list<value_type> list)
  {
    return this->reset(list);
  }

  // toggle the specified enum
  enum_set& flip(key_type e)
  {
    this->Set.flip(static_cast<size_type>(e));
    return *this;
  }
  // toggle all the enums stored in the other enum_set
  enum_set& flip(enum_set const& other) noexcept
  {
    this->Set ^= other.Set;
    return *this;
  }
  // toggle all the enums specified in the list
  enum_set& flip(std::initializer_list<value_type> list)
  {
    for (auto e : list) {
      this->Set.flip(static_cast<size_type>(e));
    }
    return *this;
  }
  // alternate syntax for bit toggle
  enum_set& operator^=(key_type key) { return this->flip(key); }
  // toggle all the enums stored in the other enum_set
  enum_set& operator^=(enum_set const& other) noexcept
  {
    return this->flip(other);
  }
  // toggle all the enums specified in the list
  enum_set& operator^=(std::initializer_list<value_type> list)
  {
    return this->flip(list);
  }

  std::pair<iterator, bool> insert(key_type value)
  {
    auto exist = this->contains(value);
    if (!exist) {
      this->Set.set(static_cast<size_type>(value));
    }

    return { iterator(this, static_cast<size_type>(value)), !exist };
  }
  template <typename InputIt>
  void insert(InputIt first, InputIt last)
  {
    for (auto i = first; i != last; i++) {
      this->insert(*i);
    }
  }
  void insert(enum_set const& other) noexcept { this->Set |= other.Set; }
  void insert(std::initializer_list<value_type> list)
  {
    for (auto e : list) {
      this->Set.set(static_cast<size_type>(e));
    }
  }

  size_type erase(key_type key)
  {
    if (this->contains(key)) {
      this->Set.reset(static_cast<size_type>(key));
      return 1;
    }

    return 0;
  }
  iterator erase(iterator pos)
  {
    this->erase(*pos++);
    return pos;
  }
  iterator erase(const_iterator pos)
  {
    this->erase(*pos++);

    return pos == this->cend() ? this->end()
                               : iterator(this, static_cast<size_type>(*pos));
  }
  void erase(enum_set const& other) noexcept { this->Set &= ~other.Set; }
  void erase(std::initializer_list<value_type> list)
  {
    for (auto e : list) {
      this->Set.reset(static_cast<size_type>(e));
    }
  }

  void swap(enum_set& other) noexcept
  {
    auto tmp = this->Set;
    this->Set = other.Set;
    other.Set = tmp;
  }

  // Lookup
  size_type count(key_type e) const { return this->contains(e) ? 1 : 0; }

  iterator find(key_type e)
  {
    if (this->contains(e)) {
      return iterator(this, static_cast<size_type>(e));
    }
    return this->end();
  }
  const_iterator find(key_type e) const
  {
    if (this->contains(e)) {
      return const_iterator(this, static_cast<size_type>(e));
    }
    return this->end();
  }

  // Checks
  bool contains(key_type e) const
  {
    return this->Set.test(static_cast<size_type>(e));
  }

  bool all() const { return this->Set.all(); }
  bool any() const { return this->Set.any(); }
  bool none() const { return this->Set.none(); }
  // alternate syntax to none()
  bool operator!() const { return this->Set.none(); }

  bool all_of(enum_set const& set) const
  {
    auto result = set;
    result.Set &= this->Set;
    return result == set;
  }
  bool any_of(enum_set const& set) const
  {
    auto result = set;
    result.Set &= this->Set;
    return result.any();
  }
  bool none_of(enum_set const& set) const
  {
    auto result = set;
    result.Set &= this->Set;
    return result.none();
  }

private:
  template <typename E, std::size_t S>
  friend inline bool operator==(enum_set<E, S> const& lhs,
                                enum_set<E, S> const& rhs) noexcept;

  template <typename E, std::size_t S, typename Predicate>
  friend inline void erase_if(enum_set<E, S>& set, Predicate pred);

  friend class enum_set_iterator<enum_set>;
  friend class enum_set_iterator<enum_set const>;

  bool test(size_type pos) const { return this->Set.test(pos); }

  std::bitset<Size> Set;
};

// non-member functions for enum_set
template <typename Enum, std::size_t Size>
inline enum_set<Enum, Size> operator+(enum_set<Enum, Size> const& lhs,
                                      Enum rhs)
{
  return enum_set<Enum, Size>{ lhs } += rhs;
}
template <typename Enum, std::size_t Size>
inline enum_set<Enum, Size> operator+(enum_set<Enum, Size> const& lhs,
                                      enum_set<Enum, Size> const& rhs) noexcept
{
  return enum_set<Enum, Size>{ lhs } += rhs;
}
template <typename Enum, std::size_t Size>
inline enum_set<Enum, Size> operator+(enum_set<Enum, Size> const& lhs,
                                      std::initializer_list<Enum> const rhs)
{
  return enum_set<Enum, Size>{ lhs } += rhs;
}

template <typename Enum, std::size_t Size>
inline cm::enum_set<Enum, Size> operator|(cm::enum_set<Enum, Size> const& lhs,
                                          Enum rhs)
{
  return enum_set<Enum, Size>{ lhs } |= rhs;
}
template <typename Enum, std::size_t Size>
inline cm::enum_set<Enum, Size> operator|(Enum lhs,
                                          cm::enum_set<Enum, Size> const& rhs)
{
  return enum_set<Enum, Size>{ lhs } |= rhs;
}
template <typename Enum, std::size_t Size>
inline cm::enum_set<Enum, Size> operator|(cm::enum_set<Enum, Size> const& lhs,
                                          cm::enum_set<Enum, Size> const& rhs)
{
  return enum_set<Enum, Size>{ lhs } |= rhs;
}

template <typename Enum, std::size_t Size>
inline enum_set<Enum, Size> operator-(enum_set<Enum, Size> const& lhs,
                                      Enum rhs)
{
  return enum_set<Enum, Size>{ lhs } -= rhs;
}
template <typename Enum, std::size_t Size>
inline enum_set<Enum, Size> operator-(enum_set<Enum, Size> const& lhs,
                                      enum_set<Enum, Size> const& rhs) noexcept
{
  return enum_set<Enum, Size>{ lhs } -= rhs;
}
template <typename Enum, std::size_t Size>
inline enum_set<Enum, Size> operator-(enum_set<Enum, Size> const& lhs,
                                      std::initializer_list<Enum> const rhs)
{
  return enum_set<Enum, Size>{ lhs } -= rhs;
}

template <typename Enum, std::size_t Size>
inline enum_set<Enum, Size> operator^(enum_set<Enum, Size> const& lhs,
                                      Enum rhs)
{
  return enum_set<Enum, Size>{ lhs } ^= rhs;
}
template <typename Enum, std::size_t Size>
inline enum_set<Enum, Size> operator^(enum_set<Enum, Size> const& lhs,
                                      enum_set<Enum, Size> const& rhs) noexcept
{
  return enum_set<Enum, Size>{ lhs } ^= rhs;
}
template <typename Enum, std::size_t Size>
inline enum_set<Enum, Size> operator^(enum_set<Enum, Size> const& lhs,
                                      std::initializer_list<Enum> const rhs)
{
  return enum_set<Enum, Size>{ lhs } ^= rhs;
}

template <typename Enum, std::size_t Size>
inline bool operator==(enum_set<Enum, Size> const& lhs,
                       enum_set<Enum, Size> const& rhs) noexcept
{
  return lhs.Set == rhs.Set;
}

template <typename Enum, std::size_t Size>
inline bool operator!=(enum_set<Enum, Size> const& lhs,
                       enum_set<Enum, Size> const& rhs) noexcept
{
  return !(lhs == rhs);
}

template <typename Enum, std::size_t Size>
inline void erase(enum_set<Enum, Size>& set, Enum value)
{
  set.erase(value);
}

template <typename Enum, std::size_t Size, typename Predicate>
inline void erase_if(enum_set<Enum, Size>& set, Predicate pred)
{
  for (std::size_t index = 0; index < set.Set.size(); ++index) {
    if (set.Set.test(index) && pred(static_cast<Enum>(index))) {
      set.Set.reset(index);
    }
  }
}
} // namespace cm

//
// WARNING: the following two operators rely on the enum_set_traits<Enum>
// struct definition.
// The macro CM_ENUM_SET_TRAITS(EnumSet) can be used to define this structure.
//
// Notes:
// When CM_ENUM_SET_TRAITS is used, the following restrictions applies:
//   * Due to language constraints, the enum_set_traits specialization must
//     occur outside of any namespace or function definition.
//   * Only one enum_set instantiation is supported per enum class type.
//

template <typename Enum>
struct cm_enum_set_traits
{
};

namespace cm {
template <typename Enum, typename = cm::void_t<>>
struct is_enum_set : std::false_type
{
};
template <typename Enum>
struct is_enum_set<Enum, cm::void_t<typename cm_enum_set_traits<Enum>::type>>
  : std::true_type
{
};
}

#if defined(__SUNPRO_CC) && defined(__sparc)
// Oracle DeveloperStudio C++ compiler on Solaris/Sparc crash on the following
// template declarations, so declare explicitly the operators.

// Helper macro to define the enum_set_traits struct specialization.
#  define CM_ENUM_SET_TRAITS(E)                                               \
    template <>                                                               \
    struct cm_enum_set_traits<E::value_type>                                  \
    {                                                                         \
      using type = E;                                                         \
      using value_type = E::value_type;                                       \
    };                                                                        \
                                                                              \
    inline E operator+(E::value_type lhs, E::value_type rhs)                  \
    {                                                                         \
      return { lhs, rhs };                                                    \
    }                                                                         \
                                                                              \
    inline E operator|(E::value_type lhs, E::value_type rhs)                  \
    {                                                                         \
      return { lhs, rhs };                                                    \
    }

#else

// Helper macro to define the enum_set_traits struct specialization.
#  define CM_ENUM_SET_TRAITS(E)                                               \
    template <>                                                               \
    struct cm_enum_set_traits<E::value_type>                                  \
    {                                                                         \
      using type = E;                                                         \
      using value_type = E::value_type;                                       \
    };

template <typename Enum,
          typename cm::enable_if_t<cm::is_enum_set<Enum>::value, int> = 0>
inline typename cm_enum_set_traits<Enum>::type operator+(Enum lhs, Enum rhs)
{
  return { lhs, rhs };
}
// Alternate syntax
template <typename Enum,
          typename cm::enable_if_t<cm::is_enum_set<Enum>::value, int> = 0>
inline typename cm_enum_set_traits<Enum>::type operator|(Enum lhs, Enum rhs)
{
  return { lhs, rhs };
}
#endif