/*
 * prime-sieve.cpp
 *
 * This code implements the Sieve of Erathostenes in meta templates.
 * The type prime_sieve<n>::result expands to a list of integers that
 * represents the primes in [2..n]. This list of primes is computed
 * entirely at compile-time. The short example main() program at the
 * end demonstrates how to access that list.
 */

//////////////////////////////////////////////////////////////////////
// Meta-programming Infrastructure
//////////////////////////////////////////////////////////////////////

struct nulltype { };

template<typename head, typename tail>
struct typelist { };

template<unsigned int i>
struct integer
{
  enum { value = i };
};

template<bool cond, typename true_type, typename false_type>
struct ifelse
{
  typedef true_type result;
};

template<typename true_type, typename false_type>
struct ifelse<false, true_type, false_type>
{
  typedef false_type result;
};

//////////////////////////////////////////////////////////////////////
// Alorithm to create [i..n]
//////////////////////////////////////////////////////////////////////

template<unsigned int i, unsigned int n>
struct integer_range
{
  typedef typelist< integer<i>, typename integer_range<i+1, n>::result > result;
};

template<unsigned int n>
struct integer_range<n, n>
{
  typedef typelist< integer<n>, nulltype > result;
};

//////////////////////////////////////////////////////////////////////
// Sieve of Erathostenes
//////////////////////////////////////////////////////////////////////

template<unsigned int i, typename integers>
struct sieve_multiples_of;

template<unsigned int i, typename x, typename xs>
struct sieve_multiples_of< i, typelist<x,xs> >
{
  typedef typename ifelse
    < x::value % i != 0u
    , typelist<x, typename sieve_multiples_of<i, xs>::result>
    , typename sieve_multiples_of<i, xs>::result
    >::result result;
};

template<unsigned int i>
struct sieve_multiples_of<i, nulltype>
{
  typedef nulltype result;
};

template<typename integers>
struct sieve_list;

template<typename x, typename xs>
struct sieve_list< typelist<x,xs> >
{
  typedef typelist<x, typename sieve_list<typename sieve_multiples_of<x::value, xs>::result>::result> result;
};

template<>
struct sieve_list<nulltype>
{
  typedef nulltype result;
};

template<unsigned int n>
struct prime_sieve
{
  typedef typename sieve_list<typename integer_range<2,n>::result>::result result;
};


//////////////////////////////////////////////////////////////////////
// Copy a type list to an output iterator
//////////////////////////////////////////////////////////////////////

template<typename typelist>
struct copy_list;

template<typename x, typename xs>
struct copy_list< typelist<x,xs> >
{
  template<typename output_iterator>
  static output_iterator to(output_iterator i)
  {
    *i = x::value;
    return copy_list<xs>::to(++i);
  }
};

template<>
struct copy_list<nulltype>
{
  template<typename output_iterator>
  static output_iterator to(output_iterator i)
  {
    return i;
  }
};

//////////////////////////////////////////////////////////////////////
// Compute the primes in [2..100] and write them to standard output
//////////////////////////////////////////////////////////////////////

#include <iostream>
#include <iterator>

int main(int, char**)
{
  using std::ostream_iterator;
  using std::cout;
  using std::endl;

  enum { n = 100 };
  typedef prime_sieve<n>::result primes;

  cout << "Primes found in [2.." << n << "]:" << endl;
  copy_list<primes>::to(ostream_iterator<unsigned int>(cout, " "));
  cout << endl;

  return 0;
}