aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAdrian Kummerlaender2015-02-08 20:38:00 +0100
committerAdrian Kummerlaender2015-02-08 20:38:00 +0100
commitbeb46377c075ccc07a22b45771f8ad993a4e088e (patch)
treefeffecf2f07b8f672cd1fcee80a63291824b7b04
parentdd504e4fcbf73750097024dce397754dc5883386 (diff)
downloadTypeAsValue-beb46377c075ccc07a22b45771f8ad993a4e088e.tar
TypeAsValue-beb46377c075ccc07a22b45771f8ad993a4e088e.tar.gz
TypeAsValue-beb46377c075ccc07a22b45771f8ad993a4e088e.tar.bz2
TypeAsValue-beb46377c075ccc07a22b45771f8ad993a4e088e.tar.lz
TypeAsValue-beb46377c075ccc07a22b45771f8ad993a4e088e.tar.xz
TypeAsValue-beb46377c075ccc07a22b45771f8ad993a4e088e.tar.zst
TypeAsValue-beb46377c075ccc07a22b45771f8ad993a4e088e.zip
Implemented higher order `Sort` list operation
* _Quicksort_ is the algorithm of choice ** it lends itself quite well to the _TypeAsValue_ approach because of its recursive nature ** this required implementation of a `Drop` counterpart to `Take` * the middle item of a given list is selected as the _pivot_ element * the `List` list contructor had to be expanded to allow `void` arguments inside its variadic parameter pack * added appropriate test cases
-rw-r--r--src/list/list.h11
-rw-r--r--src/list/operation/higher/sort.h46
-rw-r--r--test.cc72
3 files changed, 127 insertions, 2 deletions
diff --git a/src/list/list.h b/src/list/list.h
index 2e335e2..d2a5cb0 100644
--- a/src/list/list.h
+++ b/src/list/list.h
@@ -21,6 +21,16 @@ struct List<Head> {
typedef typename Cons<Head, void>::type type;
};
+template <typename Head>
+struct List<Head, void> {
+ typedef typename List<Head>::type type;
+};
+
+template <typename... Tail>
+struct List<void, Tail...> {
+ typedef typename List<Tail...>::type type;
+};
+
template <
typename Type,
Type... Values
@@ -40,6 +50,7 @@ using Tail = typename Cdr<Cons>::type;
#include "operation/basic.h"
#include "operation/nth.h"
#include "operation/take.h"
+#include "operation/drop.h"
#include "operation/append.h"
#include "operation/concatenate.h"
diff --git a/src/list/operation/higher/sort.h b/src/list/operation/higher/sort.h
new file mode 100644
index 0000000..0ff5c40
--- /dev/null
+++ b/src/list/operation/higher/sort.h
@@ -0,0 +1,46 @@
+#ifndef TYPEASVALUE_SRC_LIST_OPERATION_HIGHER_SORT_H_
+#define TYPEASVALUE_SRC_LIST_OPERATION_HIGHER_SORT_H_
+
+#include "filter.h"
+#include "list/operation/concatenate.h"
+
+namespace tav {
+
+template <
+ template<typename, typename> class Comparator,
+ typename Sequence
+>
+class Sort {
+ private:
+ using index = Divide<typename Length<Sequence>::type, Size<2>>;
+ using pivot = typename Nth<index, Sequence>::type;
+
+ using sequence_sans_pivot = typename Append<
+ typename Take<index, Sequence>::type,
+ typename Drop<Add<index, Size<1>>, Sequence>::type
+ >::type;
+
+ template <typename X>
+ using comparator_wrapper = Comparator<pivot, X>;
+
+ using lhs = typename Filter<comparator_wrapper, sequence_sans_pivot>::type;
+ using rhs = typename Remove<comparator_wrapper, sequence_sans_pivot>::type;
+
+ public:
+ typedef typename Concatenate<
+ typename List<
+ typename Sort<Comparator, lhs>::type,
+ typename List<pivot>::type,
+ typename Sort<Comparator, rhs>::type
+ >::type
+ >::type type;
+};
+
+template <template<typename, typename> class Comparator>
+struct Sort<Comparator, void> {
+ typedef void type;
+};
+
+}
+
+#endif // TYPEASVALUE_SRC_LIST_OPERATION_HIGHER_SORT_H_
diff --git a/test.cc b/test.cc
index 65a048b..0dafcb8 100644
--- a/test.cc
+++ b/test.cc
@@ -14,6 +14,7 @@
#include "list/operation/higher/find.h"
#include "list/operation/higher/take_while.h"
#include "list/operation/higher/drop_while.h"
+#include "list/operation/higher/sort.h"
#include "list/generator/iota.h"
#include "list/generator/make_list.h"
#include "list/generator/higher/list_tabulate.h"
@@ -282,7 +283,7 @@ static_assert(
tav::Pair<tav::Int<1>, void>,
tav::List<tav::Int<1>>::type
>::value,
- "(list 1) != (cons 1 void)"
+ "(list 1) != '(1)"
);
static_assert(
@@ -290,7 +291,15 @@ static_assert(
tav::Pair<tav::Int<1>, tav::Pair<tav::Int<2>, void>>,
tav::List<tav::Int<1>, tav::Int<2>>::type
>::value,
- "(list 1 2) != (cons 1 (cons 2 void))"
+ "(list 1 2) != '(1 . 2)"
+);
+
+static_assert(
+ std::is_same<
+ tav::Pair<tav::Int<1>, tav::Pair<tav::Int<2>, void>>,
+ tav::List<void, tav::Int<1>, void, tav::Int<2>, void>::type
+ >::value,
+ "(list void 1 void 2 void) != '(1 . 2)"
);
// list of type
@@ -403,6 +412,41 @@ static_assert(
"(take 3 (list 1 2)) != (list 1 2)"
);
+// list drop
+
+static_assert(
+ std::is_same<
+ tav::List<tav::Int<2>>::type,
+ tav::Drop<
+ tav::Size<1>,
+ tav::List<tav::Int<1>, tav::Int<2>>::type
+ >::type
+ >::value,
+ "(drop 1 (list 1 2)) != (list 2)"
+);
+
+static_assert(
+ std::is_same<
+ void,
+ tav::Drop<
+ tav::Size<2>,
+ tav::List<tav::Int<1>, tav::Int<2>>::type
+ >::type
+ >::value,
+ "(drop 2 (list 1 2)) != void"
+);
+
+static_assert(
+ std::is_same<
+ void,
+ tav::Drop<
+ tav::Size<3>,
+ tav::List<tav::Int<1>, tav::Int<2>>::type
+ >::type
+ >::value,
+ "(drop 3 (list 1 2)) != void"
+);
+
// list append
static_assert(
@@ -853,6 +897,30 @@ static_assert(
"(drop-while even? (list 2 4 6)) != void"
);
+// list sort
+
+static_assert(
+ std::is_same<
+ tav::List<tav::Int<1>, tav::Int<2>, tav::Int<3>>::type,
+ tav::Sort<
+ tav::GreaterThan,
+ tav::List<tav::Int<3>, tav::Int<2>, tav::Int<1>>::type
+ >::type
+ >::value,
+ "(sort > (list 3 2 1)) != (list 1 2 3)"
+);
+
+static_assert(
+ std::is_same<
+ tav::List<tav::Int<3>, tav::Int<2>, tav::Int<1>>::type,
+ tav::Sort<
+ tav::LowerThan,
+ tav::List<tav::Int<1>, tav::Int<3>, tav::Int<2>>::type
+ >::type
+ >::value,
+ "(sort < (list 1 3 2)) != (list 3 2 1)"
+);
+
// function apply
static_assert(