Implemented the Sieve of Eratosthenes as a basic example

3 files changed, 84 insertions, 0 deletions

diff --git a/example/prime/CMakeLists.txt b/example/prime/CMakeLists.txt
new file mode 100644
index 0000000..7c7a757
--- /dev/null
+++ b/example/prime/CMakeLists.txt
@@ -0,0 +1,16 @@
+cmake_minimum_required(VERSION 2.8)
+project(prime)
+
+set(
+	CMAKE_CXX_FLAGS
+	"-std=c++14 -W -Wall -Wextra -Winline -pedantic -ftemplate-depth-1024"
+)
+
+include_directories(
+	../../src/
+)
+
+add_executable(
+	prime
+	prime.cc
+)
diff --git a/example/prime/README.md b/example/prime/README.md
new file mode 100644
index 0000000..8d2e10d
--- /dev/null
+++ b/example/prime/README.md
@@ -0,0 +1,5 @@
+# prime
+
+…is a small example of how _TypeAsValue_ may be used to perform compile time computations, in this case finding prime numbers using the _Sieve of Eratosthenes_.
+
+Note that this implements a rather plain version of the sieve lacking any kind of optimization. Currently used features of _TypeAsValue_ are `Remove` as a higher order filter function, `Iota` for generating the candidate list, `runtime::for_each` to ease runtime representation of the selected primes as well as basic math and type operators.
diff --git a/example/prime/prime.cc b/example/prime/prime.cc
new file mode 100644
index 0000000..9d10ff4
--- /dev/null
+++ b/example/prime/prime.cc
@@ -0,0 +1,63 @@
+#include <iostream>
+
+#include "type.h"
+#include "operation/math.h"
+
+#include "list/list.h"
+#include "list/operation/higher/filter.h"
+#include "list/generator/iota.h"
+
+#include "runtime/list/for_each.h"
+
+using candidates = tav::Iota<tav::Size<1000>, tav::Int<2>, tav::Int<1>>::type;
+
+template <
+	typename Candidate,
+	typename Base
+>
+using isMultipleOf = tav::EqualValue<
+	tav::Modulo<Candidate, Base>,
+	tav::Int<0>
+>;
+
+template <
+	typename Candidates,
+	typename Base
+>
+class removeMultiplesOf {
+	private:
+		template <typename Element>
+		using predicate_wrapper = isMultipleOf<Element, Base>;
+
+	public:
+		typedef typename tav::Remove<
+			predicate_wrapper,
+			Candidates
+		>::type type;
+};
+
+template <typename Candidates>
+struct Sieve {
+	typedef tav::Cons<
+		tav::Head<Candidates>,
+		typename Sieve<
+			typename removeMultiplesOf<
+				tav::Tail<Candidates>,
+				tav::Head<Candidates>
+			>::type
+		>::type
+	> type;
+};
+
+template <>
+struct Sieve<void> {
+	typedef void type;
+};
+
+using primes = Sieve<candidates>::type;
+
+int main(int, char **) {
+	tav::runtime::for_each<primes>([](const int x) {
+		std::cout << x << std::endl;
+	});
+}