From beb46377c075ccc07a22b45771f8ad993a4e088e Mon Sep 17 00:00:00 2001 From: Adrian Kummerlaender Date: Sun, 8 Feb 2015 20:38:00 +0100 Subject: 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 --- src/list/list.h | 11 ++++++ src/list/operation/higher/sort.h | 46 +++++++++++++++++++++++++ test.cc | 72 ++++++++++++++++++++++++++++++++++++++-- 3 files changed, 127 insertions(+), 2 deletions(-) create mode 100644 src/list/operation/higher/sort.h 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 { typedef typename Cons::type type; }; +template +struct List { + typedef typename List::type type; +}; + +template +struct List { + typedef typename List::type type; +}; + template < typename Type, Type... Values @@ -40,6 +50,7 @@ using Tail = typename Cdr::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 class Comparator, + typename Sequence +> +class Sort { + private: + using index = Divide::type, Size<2>>; + using pivot = typename Nth::type; + + using sequence_sans_pivot = typename Append< + typename Take::type, + typename Drop>, Sequence>::type + >::type; + + template + using comparator_wrapper = Comparator; + + using lhs = typename Filter::type; + using rhs = typename Remove::type; + + public: + typedef typename Concatenate< + typename List< + typename Sort::type, + typename List::type, + typename Sort::type + >::type + >::type type; +}; + +template class Comparator> +struct Sort { + 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, void>, tav::List>::type >::value, - "(list 1) != (cons 1 void)" + "(list 1) != '(1)" ); static_assert( @@ -290,7 +291,15 @@ static_assert( tav::Pair, tav::Pair, void>>, tav::List, 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::Pair, void>>, + tav::List, 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>::type, + tav::Drop< + tav::Size<1>, + tav::List, 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<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<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<2>, tav::Int<3>>::type, + tav::Sort< + tav::GreaterThan, + tav::List, 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<2>, tav::Int<1>>::type, + tav::Sort< + tav::LowerThan, + tav::List, tav::Int<3>, tav::Int<2>>::type + >::type + >::value, + "(sort < (list 1 3 2)) != (list 3 2 1)" +); + // function apply static_assert( -- cgit v1.2.3