Program Listing for File primes.hpp

↰ Return to documentation for file (include/primes.hpp)

#pragma once

#include "primes/euler_sieve_mult.hpp"
#include "primes/euler_sieve_sqrt.hpp"

using madlib::euler_sieve_mult;
using madlib::euler_sieve_sqrt;
using madlib::primes_interface;

#ifndef DEFAULT_PRIMES_IMPLEMENTATION
#define DEFAULT_PRIMES_IMPLEMENTATION euler_sieve_sqrt
#endif

namespace madlib {

// class declarations

template <typename PRIMES_IMPLEMENTATION> class primes;

template <class PRIMES_IMPLEMENTATION> class primes_iterator;

template <class PRIMES_IMPLEMENTATION> class primes_generator;

class primes_iterator_sentinel_t {};

constexpr primes_iterator_sentinel_t primes_iterator_sentinel;

// class definitions

template <class PRIMES_IMPLEMENTATION = DEFAULT_PRIMES_IMPLEMENTATION>
class primes_iterator {

  /*
  Since this iterator needs to index into a container which may over the
  course of its operation invalidate iterators, both the owning class and and
  the raw index it is using need to be kept.
  */
  primes<PRIMES_IMPLEMENTATION> *owning_object;
  size_t raw_idx;

public:
  using value_type = typename madlib::prime_type;

  using difference_type = ssize_t;

  // Required by std::semi_regular, but if you use it then you are doing this
  // wrong and your code _will_ break.
  PRIMES_CONSTEXPR primes_iterator();

  explicit PRIMES_CONSTEXPR
  primes_iterator(primes<PRIMES_IMPLEMENTATION> *from);

  explicit PRIMES_CONSTEXPR
  primes_iterator(primes<PRIMES_IMPLEMENTATION> *from,
                  const unsigned_integral auto &initial_idx);

  friend PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
  operator+(const integral auto &lhs,
            const primes_iterator<PRIMES_IMPLEMENTATION> &rhs);

  friend PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
  operator+(const primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
            const integral auto &rhs);

  friend PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> &
  operator+=(primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
             const integral auto &rhs);

  friend PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
  operator-(const integral auto &lhs,
            const primes_iterator<PRIMES_IMPLEMENTATION> &rhs);

  friend PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
  operator-(const primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
            const integral auto &rhs);

  template <class PRIMES_IMPLEMENTATION_OTHER>
  friend PRIMES_CONSTEXPR difference_type
  operator-(const primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
            const primes_iterator<PRIMES_IMPLEMENTATION_OTHER> &rhs);

  friend PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> &
  operator-=(primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
             const integral auto &rhs);

  PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> &operator++();

  PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> operator++(int);

  PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> &operator--();

  PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> operator--(int);

  PRIMES_CONSTEXPR value_type operator*() const;

  template <class PRIMES_IMPLEMENTATION_OTHER>
  friend PRIMES_CONSTEXPR bool
  operator==(const primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
             const primes_iterator<PRIMES_IMPLEMENTATION_OTHER> &rhs) {
    return lhs.raw_idx == rhs.raw_idx;
  }

  PRIMES_CONSTEXPR bool operator==(primes_iterator_sentinel_t) { // NOLINT
    return false;
  }

  template <class PRIMES_IMPLEMENTATION_OTHER>
  PRIMES_CONSTEXPR auto
  operator<=>(const primes_iterator<PRIMES_IMPLEMENTATION_OTHER> &rhs) const {
    return static_cast<long>(raw_idx) <=> static_cast<long>(rhs.raw_idx);
  }

  PRIMES_CONSTEXPR value_type operator[](const integral auto &index_from) const;
};

// Ensure at compile time that at least the declarations for the iterator are
// compliant to std::random_access_iterator.
static_assert(std::random_access_iterator<primes_iterator<euler_sieve_sqrt>>);

template <typename PRIMES_IMPLEMENTATION = DEFAULT_PRIMES_IMPLEMENTATION>
class primes : public PRIMES_IMPLEMENTATION {
public:
  using value_type = prime_type;

  using iterator = primes_iterator<PRIMES_IMPLEMENTATION>;

  using const_iterator = const iterator;

  using difference_type =
      typename primes_iterator<PRIMES_IMPLEMENTATION>::difference_type;

  PRIMES_CONSTEXPR primes() : PRIMES_IMPLEMENTATION() {}

  explicit PRIMES_CONSTEXPR
  primes(const unsigned_integral auto &initially_through);

  explicit PRIMES_CONSTEXPR
  primes(const signed_integral auto &initially_through);

  PRIMES_CONSTEXPR primes<PRIMES_IMPLEMENTATION> &
  calculate_primes_through(const unsigned_integral auto &through_value);

  PRIMES_CONSTEXPR primes<PRIMES_IMPLEMENTATION> &
  calculate_primes_through(const signed_integral auto &through_value);

  PRIMES_CONSTEXPR bool is_prime(const unsigned_integral auto &number);

  PRIMES_CONSTEXPR bool is_prime(const signed_integral auto &number);

  PRIMES_CONSTEXPR prime_type get_nth_prime(const unsigned_integral auto &n);

  PRIMES_CONSTEXPR void auto_expand_mapped_primes();

  PRIMES_CONSTEXPR void map_next_prime();

  PRIMES_CONSTEXPR size_t number_of_mapped_primes();

  PRIMES_CONSTEXPR prime_type highest_odd_number_mapped();

  PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> begin();

  PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> cbegin() const;

  static constexpr primes_iterator_sentinel_t end() {
    return primes_iterator_sentinel;
  }
};

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes<PRIMES_IMPLEMENTATION>::primes(
    const unsigned_integral auto &initially_through)
    : PRIMES_IMPLEMENTATION(initially_through) {}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes<PRIMES_IMPLEMENTATION>::primes(
    const signed_integral auto &initially_through)
    : PRIMES_IMPLEMENTATION(initially_through > 0
                                ? static_cast<prime_type>(initially_through)
                                : 0) {}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes<PRIMES_IMPLEMENTATION> &
primes<PRIMES_IMPLEMENTATION>::calculate_primes_through(
    const unsigned_integral auto &through_value) {
  return static_cast<primes<PRIMES_IMPLEMENTATION> &>(
      primes_interface<PRIMES_IMPLEMENTATION>::
          _interface_calculate_primes_through(through_value));
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes<PRIMES_IMPLEMENTATION> &
primes<PRIMES_IMPLEMENTATION>::calculate_primes_through(
    const signed_integral auto &through_value) {
  if (through_value < 1) {
    return static_cast<primes<PRIMES_IMPLEMENTATION> &>(*this);
  }
  return calculate_primes_through(static_cast<prime_type>(through_value));
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR bool
primes<PRIMES_IMPLEMENTATION>::is_prime(const unsigned_integral auto &number) {
  return primes_interface<PRIMES_IMPLEMENTATION>::_interface_is_prime(number);
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR bool
primes<PRIMES_IMPLEMENTATION>::is_prime(const signed_integral auto &number) {
  if (number < 2) {
    return false;
  }
  return is_prime(static_cast<prime_type>(number));
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR prime_type
primes<PRIMES_IMPLEMENTATION>::get_nth_prime(const unsigned_integral auto &n) {
  return primes_interface<PRIMES_IMPLEMENTATION>::_interface_get_nth_prime(n);
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR void
primes<PRIMES_IMPLEMENTATION>::auto_expand_mapped_primes() {
  primes_interface<
      PRIMES_IMPLEMENTATION>::_interface_auto_expand_mapped_primes();
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR void primes<PRIMES_IMPLEMENTATION>::map_next_prime() {
  primes_interface<PRIMES_IMPLEMENTATION>::_interface_map_next_prime();
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR size_t
primes<PRIMES_IMPLEMENTATION>::number_of_mapped_primes() {
  return primes_interface<
      PRIMES_IMPLEMENTATION>::_interface_number_of_mapped_primes();
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR prime_type
primes<PRIMES_IMPLEMENTATION>::highest_odd_number_mapped() {
  return primes_interface<
      PRIMES_IMPLEMENTATION>::_interface_highest_odd_number_mapped();
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
primes<PRIMES_IMPLEMENTATION>::begin() {
  return primes_iterator<PRIMES_IMPLEMENTATION>(
      static_cast<primes<PRIMES_IMPLEMENTATION> *>(this));
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
primes<PRIMES_IMPLEMENTATION>::cbegin() const {
  return primes_iterator<PRIMES_IMPLEMENTATION>(
      static_cast<primes<PRIMES_IMPLEMENTATION> *>(this));
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR
primes_iterator<PRIMES_IMPLEMENTATION>::primes_iterator()
    : owning_object(static_cast<primes<PRIMES_IMPLEMENTATION>>(nullptr)),
      raw_idx(0) {}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>::primes_iterator(
    primes<PRIMES_IMPLEMENTATION> *from)
    : owning_object(from), raw_idx(0) {}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>::primes_iterator(
    primes<PRIMES_IMPLEMENTATION> *from,
    const unsigned_integral auto &initial_idx)
    : owning_object(from), raw_idx(initial_idx) {}

// Tell Doxygen to skip considering this code.
template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
operator+(const integral auto &lhs,
          const primes_iterator<PRIMES_IMPLEMENTATION> &rhs) {
  return primes_iterator(rhs.owning_object,
                         static_cast<size_t>(lhs) + rhs.raw_idx);
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
operator+(const primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
          const integral auto &rhs) {
  return primes_iterator(lhs.owning_object,
                         lhs.raw_idx + static_cast<size_t>(rhs));
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> &
operator+=(primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
           const integral auto &rhs) {
  lhs.raw_idx += rhs;
  return lhs;
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
operator-(const integral auto &lhs,
          const primes_iterator<PRIMES_IMPLEMENTATION> &rhs) {
  return primes_iterator(rhs.owning_object,
                         static_cast<size_t>(lhs) - rhs.raw_idx);
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
operator-(const primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
          const integral auto &rhs) {
  return primes_iterator(lhs.owning_object,
                         lhs.raw_idx + static_cast<size_t>(rhs));
}

template <class PRIMES_IMPLEMENTATION_LEFT, class PRIMES_IMPLEMENTATION_RIGHT>
inline PRIMES_CONSTEXPR ssize_t
operator-(const primes_iterator<PRIMES_IMPLEMENTATION_LEFT> &lhs,
          const primes_iterator<PRIMES_IMPLEMENTATION_RIGHT> &rhs) {
  return static_cast<ssize_t>(lhs.raw_idx - rhs.raw_idx);
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> &
operator-=(primes_iterator<PRIMES_IMPLEMENTATION> &lhs,
           const integral auto &rhs) {
  lhs.raw_idx -= rhs;
  return lhs;
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> &
primes_iterator<PRIMES_IMPLEMENTATION>::operator++() {
  ++raw_idx;

  return *this;
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
primes_iterator<PRIMES_IMPLEMENTATION>::operator++(int) {
  primes_iterator old = *this;

  ++raw_idx;

  return old;
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION> &
primes_iterator<PRIMES_IMPLEMENTATION>::operator--() {
  --raw_idx;

  return *this;
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR primes_iterator<PRIMES_IMPLEMENTATION>
primes_iterator<PRIMES_IMPLEMENTATION>::operator--(int) {
  primes_iterator old = *this;

  --raw_idx;

  return old;
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR
    typename primes_iterator<PRIMES_IMPLEMENTATION>::value_type
    primes_iterator<PRIMES_IMPLEMENTATION>::operator*() const {
  return owning_object->get_nth_prime(raw_idx);
}

template <class PRIMES_IMPLEMENTATION>
inline PRIMES_CONSTEXPR
    typename primes_iterator<PRIMES_IMPLEMENTATION>::value_type
    primes_iterator<PRIMES_IMPLEMENTATION>::operator[](
        const integral auto &index_from) const {
  // Here is a dragon.
  return owning_object->get_nth_prime(
      static_cast<size_t>(raw_idx + index_from));
}

template <class PRIMES_IMPLEMENTATION = DEFAULT_PRIMES_IMPLEMENTATION>
class prime_generator {
  typename primes<PRIMES_IMPLEMENTATION>::size_type prime_idx = 0;
  primes<PRIMES_IMPLEMENTATION> prime_object;

public:
  PRIMES_CONSTEXPR typename primes<PRIMES_IMPLEMENTATION>::value_type
  operator()() {
    return prime_object.get_nth_prime(prime_idx++);
  }
};

} // namespace madlib