// -*-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