carbon.algorithm source code

1 // Written in the D programming language.
2 /*
3 NYSL Version 0.9982
4 
5 A. This software is "Everyone'sWare". It means:
6   Anybody who has this software can use it as if he/she is
7   the author.
8 
9   A-1. Freeware. No fee is required.
10   A-2. You can freely redistribute this software.
11   A-3. You can freely modify this software. And the source
12       may be used in any software with no limitation.
13   A-4. When you release a modified version to public, you
14       must publish it with your name.
15 
16 B. The author is not responsible for any kind of damages or loss
17   while using or misusing this software, which is distributed
18   "AS IS". No warranty of any kind is expressed or implied.
19   You use AT YOUR OWN RISK.
20 
21 C. Copyrighted to Kazuki KOMATSU
22 
23 D. Above three clauses are applied both to source and binary
24   form of this software.
25 */
26 
27 /**
28 このモジュールは、標準ライブラリのstd.algorithmを強化します。
29 */
30 module carbon.algorithm;
31 
32 import carbon.functional,
33        carbon.range,
34        carbon.templates;
35 
36 
37 import std.algorithm,
38        std.conv,
39        std.functional,
40        std.range,
41        std.string,
42        std.traits;
43 
44 debug import std.stdio;
45 
46 ElementType!R sum(R)(R range)
47 if(isInputRange!R)
48 {
49     return reduce!"a + b"(to!(ElementType!R)(0), range);
50 }
51 
52 
53 ElementType!R product(R)(R range)
54 if(isInputRange!R)
55 {
56     return reduce!"a * b"(to!(ElementType!R)(1), range);
57 }
58 
59 
60 ElementType!R maxOf(R)(R range)
61 if(isInputRange!R)
62 {
63     return reduce!(std.algorithm.max)((ElementType!R).min, range);
64 }
65 
66 
67 ElementType!R minOf(R)(R range)
68 if(isInputRange!R)
69 {
70     return reduce!(std.algorithm.min)((ElementType!R).max, range);
71 }
72 
73 
74 unittest
75 {
76     auto r1 = [1, 2, 3, 4, 5];
77 
78     assert(sum(r1) == 15);
79     assert(product(r1) == 120);
80     assert(maxOf(r1) == 5);
81     assert(minOf(r1) == 1);
82 
83     r1 = r1[$ .. $];
84     assert(sum(r1) == 0);
85     assert(product(r1) == 1);
86     assert(maxOf(r1) == typeof(r1[0]).min);
87     assert(minOf(r1) == typeof(r1[0]).max);
88 }
89 
90 
91 
92 /**
93 tmap
94 */
95 template tmap(fun...)
96 if(fun.length >= 1)
97 {
98     auto tmap(T...)(T args)
99     if(T.length > 1 || (T.length == 1 && !__traits(compiles, ElementType!(T[0]).Types)))
100     {
101         auto dst = TMap!(false, staticMap!(Unqual, T))(args);
102 
103         return dst;
104     }
105 
106 
107     // for tuple range
108     auto tmap(T)(T args)
109     if(__traits(compiles, ElementType!T.Types))
110     {
111         return map!(adaptTuple!(fun, ElementType!T.Types))(args);
112     }
113 
114 
115     struct TMap(bool asB, T...)
116     {
117       private:
118         T _input;
119 
120       static if(isArray!(typeof(fun[$-1]))
121                 && is(ElementType!(typeof(fun[$-1])) : long)
122                 && !isSomeString!(typeof(fun[$-1])))
123       {
124         alias _funWithoutArray = fun[0 .. $-1];
125 
126         alias IndexOfRangeTypeTF = IndexOfRangeTypeTFImpl!(0, fun[$-1]);
127 
128         template IndexOfRangeTypeTFImpl(size_t index, alias array)
129         {
130           static if(index == T.length)
131             alias IndexOfRangeTypeTFImpl = TypeTuple!();
132           else static if(array.length == 0)
133             alias IndexOfRangeTypeTFImpl = TypeTuple!(false, IndexOfRangeTypeTFImpl!(index + 1, array));
134           else static if(index == array[0])
135             alias IndexOfRangeTypeTFImpl = TypeTuple!(true, IndexOfRangeTypeTFImpl!(index + 1, array[1 .. $]));
136           else static if(index < array[0])
137             alias IndexOfRangeTypeTFImpl = TypeTuple!(false, IndexOfRangeTypeTFImpl!(index + 1, array));
138           else static if(index > array[0])
139             alias IndexOfRangeTypeTFImpl = TypeTuple!(false, IndexOfRangeTypeTFImpl!(index, array[1 .. $]));
140           else
141             static assert(0);
142         }
143       }
144       else
145       {
146         alias _funWithoutArray = fun;
147 
148         alias IndexOfRangeTypeTF = IndexOfRangeTypeTFImpl!T;
149 
150         template IndexOfRangeTypeTFImpl(T...)
151         {
152             static if(T.length == 0)
153                 alias IndexOfRangeTypeTFImpl = TypeTuple!();
154             else
155                 alias IndexOfRangeTypeTFImpl = TypeTuple!(isInputRange!(T[0]), IndexOfRangeTypeTFImpl!(T[1..$]));
156         }
157       }
158 
159       static if(_funWithoutArray.length == 1)
160         alias _fun = naryFun!(TypeTuple!(_funWithoutArray)[0]);
161       else
162         alias _fun = adjoin!(staticMap!(naryFun, _funWithoutArray));
163 
164         template RangesTypesImpl(size_t n)
165         {
166             static if(n < T.length)
167             {
168                 static if(IndexOfRangeTypeTF[n])
169                     alias TypeTuple!(T[n], RangesTypesImpl!(n+1)) RangesTypesImpl;
170                 else
171                     alias RangesTypesImpl!(n+1) RangesTypesImpl;
172             }
173             else
174                 alias TypeTuple!() RangesTypesImpl;
175         }
176         
177         alias RangesTypesImpl!(0) RangesTypes;
178         alias staticMap!(ElementType, RangesTypes) ElementTypeOfRanges;
179         alias ETSImpl!(0) ETS;      //_fun args type
180         
181         template ETSImpl(size_t n)
182         {
183             static if(n < T.length)
184             {
185                 static if(IndexOfRangeTypeTF[n])
186                     alias TypeTuple!(ElementType!(T[n]), ETSImpl!(n+1)) ETSImpl;
187                 else
188                     alias TypeTuple!(T[n], ETSImpl!(n+1)) ETSImpl;
189             }
190             else
191                 alias TypeTuple!() ETSImpl;
192         }
193 
194 
195         static assert(is(typeof(_fun(ETS.init))));
196 
197 
198         static string expandMacro(string a, string b)
199         {
200             string dst;
201             foreach(i, isRange; IndexOfRangeTypeTF)
202             {
203               static if(isRange)
204               {
205                 if(a)
206                     dst ~= format(a, i);
207               }
208               else
209               {
210                 if(b)
211                     dst ~= format(b, i);
212               }
213             }
214             return dst;
215         }
216 
217       public:
218 
219       static if(asB && allSatisfy!(isBidirectionalRange, RangesTypes) && allSatisfy!(hasLength, RangesTypes))
220       {
221         @property
222         auto ref back()
223         {
224             return mixin("_fun(" ~ expandMacro("_input[%1$s].back,", "_input[%1$s],") ~ ")");
225         }
226 
227 
228         void popBack()
229         {
230             mixin(expandMacro("_input[%1$s].popBack();\n", null));
231         }
232       }
233         
234         static if(allSatisfy!(isInfinite, RangesTypes))
235         {
236             enum bool empty = false;
237         }
238         else
239         {
240             @property
241             bool empty()
242             {
243                 mixin(expandMacro("if(_input[%1$s].empty) return true;\n", null));
244                 return false;
245             }
246         }
247 
248 
249         void popFront()
250         {
251             mixin(expandMacro("_input[%1$s].popFront();\n", null));
252         }
253 
254 
255         @property
256         auto ref front()
257         {
258             return mixin("_fun(" ~ expandMacro("_input[%1$s].front,", "_input[%1$s],") ~ ")");
259         }
260 
261 
262       static if(allSatisfy!(isRandomAccessRange, RangesTypes))
263       {
264         auto ref opIndex(size_t index)
265         {
266             return mixin("_fun(" ~ expandMacro("_input[%1$s][index],", "_input[%1$s],") ~ ")");
267         }
268       }
269         
270         static if(allSatisfy!(hasLength, RangesTypes))
271         {
272             @property
273             auto length()
274             {
275                 mixin("alias LT = CommonType!(" ~ expandMacro("typeof(_input[%1$s].length),", null) ~ ");");
276 
277                 LT m = LT.max;
278 
279                 mixin(expandMacro("m = min(m, _input[%1$s].length);\n", null));
280                 return m;
281             }
282 
283             alias length opDollar;
284         }
285         
286         static if(allSatisfy!(hasSlicing, RangesTypes))
287         {
288             auto opSlice(size_t idx1, size_t idx2)
289             {
290                 return mixin("TMap!(asB, T)(" ~ expandMacro("_input[%1$s][idx1 .. idx2],", "_input[%1$s],") ~ ")");
291             }
292         }
293         
294         static if(allSatisfy!(isForwardRange, RangesTypes))
295         {
296             @property
297             auto save()
298             {
299                 return mixin("TMap!(asB, T)(" ~ expandMacro("_input[%1$s].save,", "_input[%1$s],") ~ ")");
300             }
301         }
302 
303 
304       static if(allSatisfy!(isBidirectionalRange, RangesTypes) && allSatisfy!(hasLength, RangesTypes))
305       {
306         TMap!(true, T) asBidirectional() @property
307         {
308             auto dst = TMap!(true, T)(this._input);
309 
310             immutable size = dst.length;
311 
312             mixin(expandMacro(q{
313                 static if(hasSlicing!(T[%1$s]))
314                   dst._input[%1$s] = dst._input[%1$s][0 .. size];
315                 else
316                   dst._input[%1$s].popBackN(dst._input[%1$s].length - size);
317               }, null));
318 
319             return dst;
320         }
321       }
322     }
323 }
324 
325 
326 /// ditto
327 unittest
328 {
329     debug scope(failure) writefln("Unittest Failure :%s(%s) ", __FILE__, __LINE__);
330     debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();}
331 
332     auto r1 = [1, 3, 2, 4, 0, 0];
333     auto s = "abc".dup;
334     auto tm1 = tmap!("a", "b", (a, b) => b.repeat(a).array().idup)(r1, s);
335     assert(equal(tm1, [tuple(1, 'a', "a"d),
336                        tuple(3, 'b', "bbb"d),
337                        tuple(2, 'c', "cc"d)]));
338 
339     assert(tmap!"a"(r1, s, "").empty);
340 
341     auto r3 = [1, 2, 3];
342     //first element of [0] expresses r3 is used as range, but second element expresses "abcd" is not used as range.
343     auto ss = tmap!("b[a]", [0])(r3, "abcd");
344     assert(equal(ss, ['b', 'c', 'd'][]));
345     assert(ss.length == 3);
346     assert(equal(ss, ss.save));
347 
348     static assert(isForwardRange!(typeof(ss)));
349     static assert(!isBidirectionalRange!(typeof(ss)));
350     static assert(!isRandomAccessRange!(typeof(ss)));
351 
352     auto ss_b = ss.asBidirectional;
353     static assert(isBidirectionalRange!(typeof(ss_b)));
354     static assert(isRandomAccessRange!(typeof(ss_b)));
355     assert(equal(ss_b.retro, ['d', 'c', 'b']));
356 
357     ///multi function and range-choose test
358     auto tm5 = tmap!("b[a]", "b[a-1]", [0])(r3, "abcd");
359     assert(equal(tm5, [tuple('b', 'a'), tuple('c', 'b'), tuple('d', 'c')][]));
360 }
361 
362 
363 auto flatMap(alias fun, R)(R r)
364 if(isInputRange!R)
365 {
366     return r.map!fun.concat;
367 }
368 
369 unittest
370 {
371     auto r1 = [1, 2, 3, 4];
372     assert(equal(r1.flatMap!"repeat(a, a)", [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]));
373 
374     auto r2 = ["a b c", "de f", "ghi", "jkl mn"];
375     assert(equal(r2.flatMap!split, ["a", "b", "c", "de", "f", "ghi", "jkl", "mn"]));
376 
377     auto r3 = [1, 2];
378     assert(equal!equal(r3.flatMap!"repeat(a, a).repeat(a)",
379         [[1], [2, 2], [2, 2]]));
380 }