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         auto ref xtorFun(T)(auto ref T a)
46         {
47             version(LDC) pragma(inline, true);
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         alias xtorFun = xtor;
62 }
63 
64 ///
65 @safe pure nothrow unittest
66 {
67     static struct X { int x, y, z; }
68 
69     auto r = [ X(1, 2, 1),
70                X(0, 1, 2),
71                X(2, 0, 0) ];
72 
73     r.sortBy!(a => a.x);
74     assert(r == [ X(0, 1, 2),
75                   X(1, 2, 1),
76                   X(2, 0, 0) ]);
77     r.sortBy!(a => a.y);
78     assert(r == [ X(2, 0, 0),
79                   X(0, 1, 2),
80                   X(1, 2, 1)] );
81     r.sortBy!(a => a.z);
82     assert(r == [ X(2, 0, 0),
83                   X(1, 2, 1),
84                   X(0, 1, 2) ]);
85 
86     r.sortBy!"x";
87     assert(r == [ X(0, 1, 2),
88                   X(1, 2, 1),
89                   X(2, 0, 0) ]);
90     r.sortBy!"y";
91     assert(r == [ X(2, 0, 0),
92                   X(0, 1, 2),
93                   X(1, 2, 1)] );
94     r.sortBy!"z";
95     assert(r == [ X(2, 0, 0),
96                   X(1, 2, 1),
97                   X(0, 1, 2) ]);
98 
99     r.sortBy!0;
100     assert(r == [ X(0, 1, 2),
101                   X(1, 2, 1),
102                   X(2, 0, 0) ]);
103     r.sortBy!1;
104     assert(r == [ X(2, 0, 0),
105                   X(0, 1, 2),
106                   X(1, 2, 1)] );
107     r.sortBy!2;
108     assert(r == [ X(2, 0, 0),
109                   X(1, 2, 1),
110                   X(0, 1, 2) ]);
111 }
112 
113 /** Returns: $(D r) sorted.
114     If needed a GC-copy of $(D r) is allocated, sorted and returned.
115     See_Also: http://forum.dlang.org/thread/tnrvudehinmkvbifovwo@forum.dlang.org#post-tnrvudehinmkvbifovwo:40forum.dlang.org
116     TODO: Move to Phobos
117 */
118 auto sorted(R, E = ElementType!R)(R r)
119 {
120     import std.traits : isNarrowString;
121     import std.range: hasLength;
122     import nxt.range_ex : isSortedRange;
123 
124     static if (isSortedRange!R)
125         return r;
126     else
127     {
128         static if (isRandomAccessRange!R)
129             auto s = r.dup;     // TODO: remove this
130         else static if (isNarrowString!R)
131         {
132             import std.conv : to;
133             auto s = r.to!(dchar[]); // need dchar for random access
134         }
135         else static if (hasLength!R)
136         {
137             import std.algorithm: copy;
138             auto s = new E[r.length];
139             static if (is(typeof(r[]))) // TODO: unpretty
140                 r[].copy(s);
141             else
142                 r.copy(s);
143         }
144         else
145         {
146             E[] s; // TODO: use Appender?
147             foreach (const ref e; r[])
148                 s ~= e;             // TODO: optimize?
149         }
150 
151         import std.algorithm.sorting : sort;
152         return sort(s);
153     }
154 }
155 
156 version(unittest) import std.algorithm.comparison : equal;
157 
158 ///
159 @safe pure unittest
160 {
161     assert(equal("öaA".sorted, "Aaö"));
162     assert(equal("öaA"w.sorted, "Aaö"));
163     assert(equal("öaA"d.sorted, "Aaö"));
164 }
165 
166 ///
167 @safe pure unittest
168 {
169     import std.algorithm.sorting : sort;
170     auto x = "öaA"d;
171     auto y = sort(x.dup).sorted; // parameter to sorted is a SortedRange
172     assert(equal(y, "Aaö"));
173 }
174 
175 ///
176 @safe pure unittest
177 {
178     import std.algorithm.sorting : sort;
179     immutable x = [3, 2, 1];
180     auto y = x.dup;
181     sort(y);
182     assert(equal(x.sorted, y));
183 }
184 
185 ///
186 unittest
187 {
188     import std.container: Array;
189     auto x = Array!int(3, 2, 1);
190     assert(equal(x.sorted, [1, 2, 3]));
191 }
192 
193 ///
194 unittest
195 {
196     import std.container: SList;
197     auto x = SList!int(3, 2, 1);
198     assert(equal(x.sorted, [1, 2, 3]));
199 }
200 
201 import std.random : Random;
202 
203 /** Functional version of `std.random.randomShuffle`.
204  *
205  * Returns: $(D r) randomly shuffled.
206  *
207  * If needed a GC-copy of $(D r) is allocated, sorted and returned.
208 */
209 auto randomlyShuffled(Range, RandomGen)(Range r, ref RandomGen gen)
210 {
211     import std.random : randomShuffle;
212     r.randomShuffle(gen);
213     // TODO: reuse copying logic in `sorted`
214     return r;
215 }
216 
217 ///
218 auto randomlyShuffled(Range)(Range r)
219 {
220     import std.random : randomShuffle;
221     r.randomShuffle();
222     // TODO: reuse copying logic in `sorted`
223     return r;
224 }
225 
226 ///
227 @safe pure unittest
228 {
229     immutable x = [3, 2, 1];
230     auto y = x.dup;
231     Random random;
232     y.randomlyShuffled(random);
233 }
234 
235 /** Sort sub-range of `subrange` defined by index range [i..j].
236  *
237  * See_Also: https://forum.dlang.org/thread/lkggfpgvskvxvgwyjgcs@forum.dlang.org
238  */
239 auto sortSubRange(R)(R range, size_t i, size_t j)
240 if (isRandomAccessRange!R)
241 {
242     import std.algorithm.sorting : topN, partialSort;
243     size_t start = i;
244     if (i != 0)
245     {
246         topN(range, i);         // TODO: `assumePure`
247         start++;
248     }
249     partialSort(range[start .. $], j-start);
250     return range[i .. j];
251 }
252 
253 unittest
254 {
255     auto x = [1,2,7,4,2,6,8,3,9,3];
256     auto y = sortSubRange(x, 3, 6);
257     assert(x == [2, 2, 1,
258                  3, 3, 4,
259                  6, 8, 9, 7]);
260     assert(y == [3, 3, 4]);
261 }