aboutsummaryrefslogtreecommitdiff
path: root/src/list
diff options
context:
space:
mode:
Diffstat (limited to 'src/list')
-rw-r--r--src/list/list.h11
-rw-r--r--src/list/operation/higher/sort.h46
2 files changed, 57 insertions, 0 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_