nxt.sort_ex source code

1 /** Extensions to std.algorithm.sort.
2  *
3  * License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
4  */
5 
6 module nxt.sort_ex;
7 
8 import std.traits : isAggregateType;
9 import std.range.primitives : ElementType, isRandomAccessRange;
10 
11 /** Sort random access range $(D R) of aggregates on value of calls to $(D xtor).
12     See_Also: http://forum.dlang.org/thread/nqwzojnlidlsmpunpqqy@forum.dlang.org#post-dmfvkbfhzigecnwglrur:40forum.dlang.org
13  */
14 auto sortBy(alias xtor, R)(R r)
15 if (isRandomAccessRange!R &&
16     isAggregateType!(ElementType!R))
17 {
18     import std.algorithm : sort;
19     import std.functional : unaryFun;
20     return r.sort!((a, b) => (xtorFun!xtor(a) <
21                               xtorFun!xtor(b)));
22 }
23 
24 /** Reverse sort random access range $(D R) of aggregates on value of calls to $(D xtor).
25     See_Also: http://forum.dlang.org/thread/nqwzojnlidlsmpunpqqy@forum.dlang.org#post-dmfvkbfhzigecnwglrur:40forum.dlang.org
26 */
27 auto rsortBy(alias xtor, R)(R r)
28 if (isRandomAccessRange!R &&
29     isAggregateType!(ElementType!R))
30 {
31     import std.algorithm : sort;
32     import std.functional : unaryFun;
33     return r.sort!((a, b) => (xtorFun!xtor(a) >
34                               xtorFun!xtor(b)));
35 }
36 
37 /* private alias makePredicate(alias xtor) = (a, b) => (xtorFun!xtor(a) < xtorFun!xtor(b)); */
38 
39 /// Extractor function used by `sortBy` and `rsortBy`.
40 private static template xtorFun(alias xtor)
41 {
42     import std.traits: isIntegral;
43     static if (is(typeof(xtor) : string))
44     {
45         pragma(inline, true)    // must be inlined
46         auto ref xtorFun(T)(auto ref T a)
47         {
48             mixin("with (a) { return " ~ xtor ~ "; }");
49         }
50     }
51     else static if (isIntegral!(typeof(xtor)))
52     {
53         pragma(inline, true)    // must be inlined
54         auto ref xtorFun(T)(auto ref T a)
55         {
56             import std.conv: to;
57             mixin("return a.tupleof[" ~ xtor.to!string ~ "];");
58         }
59     }
60     else
61     {
62         alias xtorFun = xtor;
63     }
64 }
65 
66 ///
67 @safe pure nothrow unittest
68 {
69     static struct X { int x, y, z; }
70 
71     auto r = [ X(1, 2, 1),
72                X(0, 1, 2),
73                X(2, 0, 0) ];
74 
75     r.sortBy!(a => a.x);
76     assert(r == [ X(0, 1, 2),
77                   X(1, 2, 1),
78                   X(2, 0, 0) ]);
79     r.sortBy!(a => a.y);
80     assert(r == [ X(2, 0, 0),
81                   X(0, 1, 2),
82                   X(1, 2, 1)] );
83     r.sortBy!(a => a.z);
84     assert(r == [ X(2, 0, 0),
85                   X(1, 2, 1),
86                   X(0, 1, 2) ]);
87 
88     r.sortBy!"x";
89     assert(r == [ X(0, 1, 2),
90                   X(1, 2, 1),
91                   X(2, 0, 0) ]);
92     r.sortBy!"y";
93     assert(r == [ X(2, 0, 0),
94                   X(0, 1, 2),
95                   X(1, 2, 1)] );
96     r.sortBy!"z";
97     assert(r == [ X(2, 0, 0),
98                   X(1, 2, 1),
99                   X(0, 1, 2) ]);
100 
101     r.sortBy!0;
102     assert(r == [ X(0, 1, 2),
103                   X(1, 2, 1),
104                   X(2, 0, 0) ]);
105     r.sortBy!1;
106     assert(r == [ X(2, 0, 0),
107                   X(0, 1, 2),
108                   X(1, 2, 1)] );
109     r.sortBy!2;
110     assert(r == [ X(2, 0, 0),
111                   X(1, 2, 1),
112                   X(0, 1, 2) ]);
113 }
114 
115 /** Returns: $(D r) sorted.
116     If needed a GC-copy of $(D r) is allocated, sorted and returned.
117     See_Also: http://forum.dlang.org/thread/tnrvudehinmkvbifovwo@forum.dlang.org#post-tnrvudehinmkvbifovwo:40forum.dlang.org
118     TODO Add to Phobos
119 */
120 auto sorted(R, E = ElementType!R)(R r)
121 {
122     import std.traits : isNarrowString;
123     import std.range: hasLength;
124     import nxt.range_ex : isSortedRange;
125 
126     static if (isSortedRange!R)
127     {
128         return r;
129     }
130     else
131     {
132         static if (isRandomAccessRange!R)
133         {
134             auto s = r.dup;     // TODO remove this
135         }
136         else static if (isNarrowString!R)
137         {
138             import std.conv : to;
139             auto s = r.to!(dchar[]); // need dchar for random access
140         }
141         else static if (hasLength!R)
142         {
143             import std.algorithm: copy;
144             auto s = new E[r.length];
145             static if (is(typeof(r[]))) // TODO unpretty
146             {
147                 r[].copy(s);
148             }
149             else
150             {
151                 r.copy(s);
152             }
153         }
154         else
155         {
156             E[] s; // TODO use Appender?
157             foreach (const ref e; r[])
158             {
159                 s ~= e;             // TODO optimize?
160             }
161         }
162 
163         import std.algorithm.sorting : sort;
164         return sort(s);
165     }
166 }
167 
168 version(unittest) import std.algorithm.comparison : equal;
169 
170 ///
171 @safe pure unittest
172 {
173     assert(equal("öaA".sorted, "Aaö"));
174     assert(equal("öaA"w.sorted, "Aaö"));
175     assert(equal("öaA"d.sorted, "Aaö"));
176 }
177 
178 ///
179 @safe pure unittest
180 {
181     import std.algorithm.sorting : sort;
182     auto x = "öaA"d;
183     auto y = sort(x.dup).sorted; // parameter to sorted is a SortedRange
184     assert(equal(y, "Aaö"));
185 }
186 
187 ///
188 @safe pure unittest
189 {
190     import std.algorithm.sorting : sort;
191     immutable x = [3, 2, 1];
192     auto y = x.dup;
193     sort(y);
194     assert(equal(x.sorted, y));
195 }
196 
197 ///
198 unittest
199 {
200     import std.container: Array;
201     auto x = Array!int(3, 2, 1);
202     assert(equal(x.sorted, [1, 2, 3]));
203 }
204 
205 ///
206 unittest
207 {
208     import std.container: SList;
209     auto x = SList!int(3, 2, 1);
210     assert(equal(x.sorted, [1, 2, 3]));
211 }
212 
213 import std.random : Random;
214 
215 /** Functional version of `std.random.randomShuffle`.
216  *
217  * Returns: $(D r) randomly shuffled.
218  *
219  * If needed a GC-copy of $(D r) is allocated, sorted and returned.
220 */
221 auto randomlyShuffled(Range, RandomGen)(Range r, ref RandomGen gen)
222 {
223     import std.random : randomShuffle;
224     r.randomShuffle(gen);
225     // TODO reuse copying logic in `sorted`
226     return r;
227 }
228 
229 ///
230 auto randomlyShuffled(Range)(Range r)
231 {
232     import std.random : randomShuffle;
233     r.randomShuffle();
234     // TODO reuse copying logic in `sorted`
235     return r;
236 }
237 
238 ///
239 @safe pure unittest
240 {
241     immutable x = [3, 2, 1];
242     auto y = x.dup;
243     Random random;
244     y.randomlyShuffled(random);
245 }
246 
247 /** Sort sub-range of `subrange` defined by index range [i..j].
248  *
249  * See_Also: https://forum.dlang.org/thread/lkggfpgvskvxvgwyjgcs@forum.dlang.org
250  */
251 auto sortSubRange(R)(R range, size_t i, size_t j)
252 if (isRandomAccessRange!R)
253 {
254     import std.algorithm.sorting : topN, partialSort;
255     size_t start = i;
256     if (i != 0)
257     {
258         topN(range, i);         // TODO `assumePure`
259         start++;
260     }
261     partialSort(range[start .. $], j-start);
262     return range[i .. j];
263 }
264 
265 unittest
266 {
267     auto x = [1,2,7,4,2,6,8,3,9,3];
268     auto y = sortSubRange(x, 3, 6);
269     assert(x == [2, 2, 1,
270                  3, 3, 4,
271                  6, 8, 9, 7]);
272     assert(y == [3, 3, 4]);
273 }