stribog.meta.sort source code

1 /**
2 *   Copyright: © 2014-2015 Anton Gushcha
3 *   License: Subject to the terms of the Boost 1.0 license as specified in LICENSE file
4 *   Authors: Anton Gushcha <ncrashed@gmail.com>
5 *
6 *   Template sorting using merge sort algorithm
7 */
8 module stribog.meta.sort;
9 
10 import std.math;
11 import stribog.meta.base;
12 
13 /**
14 *   Perfoms merge sort algorithm on expression list $(B T) using
15 *   function/template $(B F) that takes two elements and returns
16 *   boolean.
17 */
18 template staticSort(alias F, T...)
19 {
20     static if(T.length <= 1) {
21         alias staticSort = T;
22     } else {
23         private template FWrapped(alias a, alias b) 
24         {
25             static if(__traits(compiles, F(T[0], T[1]))) {
26                 static assert(is(typeof(F(T[0], T[1])) == bool), "Predicate return type must be a boolean!");
27                 enum FWrapped = F(a, b);
28             } else {
29                 static assert(is(typeof(F!(T[0], T[1])) == bool), "Predicate return type must be a boolean!");
30                 enum FWrapped = F!(a, b);
31             }
32         }
33         
34         private template merge(alias as, alias bs)
35         {
36             static if(as.expand.length == 0) {
37                 alias merge = bs;
38             } else static if (bs.expand.length == 0) {
39                 alias merge = as;
40             } else {                
41                 static if(FWrapped!(as.expand[0], bs.expand[0])) {
42                     alias merge = StrictExpressionList!(bs.expand[0], merge!(as, StrictExpressionList!(bs.expand[1 .. $])).expand); 
43                 } else {
44                     alias merge = StrictExpressionList!(as.expand[0], merge!(StrictExpressionList!(as.expand[1 .. $]), bs).expand); 
45                 } 
46             }
47         }
48         
49         private template mergePairs(xs...)
50         {
51             static if(xs.length < 2) {
52                 alias mergePairs = xs;
53             } else {
54                 alias mergePairs = ExpressionList!(merge!(xs[0], xs[1]), mergePairs!(xs[2..$]));
55             }
56         }
57         
58         private template mergeAll(xs...)
59         {
60             static if(xs.length <= 1) {
61                 alias mergeAll = xs;
62             } else {
63                 alias mergeAll = mergeAll!(mergePairs!xs);
64             }
65         }
66         
67         private template ascending(alias a, alias as, bs...)
68         {
69             static if (bs.length > 1 && !FWrapped!(a, bs[0])) {
70                 alias ascending = ascending!(bs[0], StrictExpressionList!(as.expand, a), bs[1..$]);
71             } else {
72                 alias ascending = ExpressionList!(StrictExpressionList!(as.expand, a), sequences!bs);
73             }
74         }
75         
76         private template descending(alias a, alias as, bs...)
77         {
78             static if (bs.length > 1 && FWrapped!(a, bs[0])) {
79                 alias descending = descending!(bs[0], StrictExpressionList!(a, as.expand), bs[1..$]);
80             } else {
81                 alias descending = ExpressionList!(StrictExpressionList!(a, as.expand), sequences!bs);
82             }
83         }
84         
85         private template sequences(U...)
86         {
87             static if (U.length < 2) {
88                 alias sequences = StrictExpressionList!U;
89             } else static if(FWrapped!(U[0], U[1])) {
90                 alias sequences = descending!(U[1], StrictExpressionList!(U[0]), U[2 .. $]);
91             } else {
92                 alias sequences = ascending!(U[1], StrictExpressionList!(U[0]), U[2 .. $]);
93             }
94         }
95         
96         private alias temp = mergeAll!(sequences!T)[0];
97         alias staticSort = temp.expand;
98     }
99 }
100 /// Example
101 unittest
102 {
103     bool ascending(int a, int b)
104     {
105         return a > b;
106     }
107     
108     bool descending(int a, int b)
109     {
110         return a < b;
111     }
112     
113     template Ascending(int a, int b)
114     {
115         enum Ascending = a > b;
116     }
117     
118     template Descending(int a, int b)
119     {
120         enum Descending = a < b;
121     }
122     
123     static assert([staticSort!(ascending, 3, 1, 5, 2)] == [1, 2, 3, 5]);
124     static assert([staticSort!(Ascending, 3, 1, 5, 2)] == [1, 2, 3, 5]);
125     static assert([staticSort!(descending, 3, 1, 5, 2)] == [5, 3, 2, 1]);
126     static assert([staticSort!(Descending, 3, 1, 5, 2)] == [5, 3, 2, 1]);
127     
128     import std.string;
129     
130     bool wordsCmp(string a, string b)
131     {
132         return toUpper(a) > toUpper(b);
133     }
134     
135     alias words = ExpressionList!("aBc", "a", "abc", "b", "ABC", "c");
136     alias sortedWords = staticSort!(wordsCmp, words);
137     static assert([sortedWords] == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
138 }