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 public import std.algorithm;
33 
34 import carbon.functional,
35        carbon.range,
36        carbon.templates;
37 
38 
39 import std.algorithm,
40        std.conv,
41        std.functional,
42        std.range,
43        std.string,
44        std.traits,
45        std.typetuple;
46 
47 debug import std.stdio;
48 
49 
50 /**
51 引数に与えられたレンジの総和を返します。
52 引数には、無限レンジを渡すことができません。
53 */
54 ElementType!R sum(R)(R range)
55 if(isInputRange!R && !isInfinite!R)
56 {
57     return reduce!"a + b"(to!(ElementType!R)(0), range);
58 }
59 
60 
61 ElementType!R product(R)(R range)
62 if(isInputRange!R && !isInfinite!R)
63 {
64     return reduce!"a * b"(to!(ElementType!R)(1), range);
65 }
66 
67 
68 ElementType!R maxOf(R)(R range)
69 if(isInputRange!R && !isInfinite!R)
70 {
71     return reduce!(std.algorithm.max)((ElementType!R).min, range);
72 }
73 
74 
75 ElementType!R minOf(R)(R range)
76 if(isInputRange!R && !isInfinite!R)
77 {
78     return reduce!(std.algorithm.min)((ElementType!R).max, range);
79 }
80 
81 
82 unittest
83 {
84     auto r1 = [1, 2, 3, 4, 5];
85 
86     assert(sum(r1) == 15);
87     assert(product(r1) == 120);
88     assert(maxOf(r1) == 5);
89     assert(minOf(r1) == 1);
90 
91     r1 = r1[$ .. $];
92     assert(sum(r1) == 0);
93     assert(product(r1) == 1);
94     assert(maxOf(r1) == typeof(r1[0]).min);
95     assert(minOf(r1) == typeof(r1[0]).max);
96 }
97 
98 
99 
100 /**
101 tmap
102 */
103 template tmap(fun...)
104 if(fun.length >= 1)
105 {
106     auto tmap(T...)(T args)
107     if(T.length > 1 || (T.length == 1 && !__traits(compiles, ElementType!(T[0]).Types)))
108     {
109         auto dst = TMap!(false, staticMap!(Unqual, T))(args);
110 
111         return dst;
112     }
113 
114 
115     // for tuple range
116     auto tmap(T)(T args)
117     if(__traits(compiles, ElementType!T.Types))
118     {
119         return map!(adaptTuple!(fun, ElementType!T.Types))(args);
120     }
121 
122 
123     struct TMap(bool asB, T...)
124     {
125       private:
126         T _input;
127 
128       static if(isArray!(typeof(fun[$-1]))
129                 && is(ElementType!(typeof(fun[$-1])) : long)
130                 && !isSomeString!(typeof(fun[$-1])))
131       {
132         alias _funWithoutArray = fun[0 .. $-1];
133 
134         alias IndexOfRangeTypeTF = IndexOfRangeTypeTFImpl!(0, fun[$-1]);
135 
136         template IndexOfRangeTypeTFImpl(size_t index, alias array)
137         {
138           static if(index == T.length)
139             alias IndexOfRangeTypeTFImpl = TypeTuple!();
140           else static if(array.length == 0)
141             alias IndexOfRangeTypeTFImpl = TypeTuple!(false, IndexOfRangeTypeTFImpl!(index + 1, array));
142           else static if(index == array[0])
143             alias IndexOfRangeTypeTFImpl = TypeTuple!(true, IndexOfRangeTypeTFImpl!(index + 1, array[1 .. $]));
144           else static if(index < array[0])
145             alias IndexOfRangeTypeTFImpl = TypeTuple!(false, IndexOfRangeTypeTFImpl!(index + 1, array));
146           else static if(index > array[0])
147             alias IndexOfRangeTypeTFImpl = TypeTuple!(false, IndexOfRangeTypeTFImpl!(index, array[1 .. $]));
148           else
149             static assert(0);
150         }
151       }
152       else
153       {
154         alias _funWithoutArray = fun;
155 
156         alias IndexOfRangeTypeTF = IndexOfRangeTypeTFImpl!T;
157 
158         template IndexOfRangeTypeTFImpl(T...)
159         {
160             static if(T.length == 0)
161                 alias IndexOfRangeTypeTFImpl = TypeTuple!();
162             else
163                 alias IndexOfRangeTypeTFImpl = TypeTuple!(isInputRange!(T[0]), IndexOfRangeTypeTFImpl!(T[1..$]));
164         }
165       }
166 
167       static if(_funWithoutArray.length == 1)
168         alias _fun = naryFun!(TypeTuple!(_funWithoutArray)[0]);
169       else
170         alias _fun = adjoin!(staticMap!(naryFun, _funWithoutArray));
171 
172         template RangesTypesImpl(size_t n)
173         {
174             static if(n < T.length)
175             {
176                 static if(IndexOfRangeTypeTF[n])
177                     alias TypeTuple!(T[n], RangesTypesImpl!(n+1)) RangesTypesImpl;
178                 else
179                     alias RangesTypesImpl!(n+1) RangesTypesImpl;
180             }
181             else
182                 alias TypeTuple!() RangesTypesImpl;
183         }
184         
185         alias RangesTypesImpl!(0) RangesTypes;
186         alias staticMap!(ElementType, RangesTypes) ElementTypeOfRanges;
187         alias ETSImpl!(0) ETS;      //_fun args type
188         
189         template ETSImpl(size_t n)
190         {
191             static if(n < T.length)
192             {
193                 static if(IndexOfRangeTypeTF[n])
194                     alias TypeTuple!(ElementType!(T[n]), ETSImpl!(n+1)) ETSImpl;
195                 else
196                     alias TypeTuple!(T[n], ETSImpl!(n+1)) ETSImpl;
197             }
198             else
199                 alias TypeTuple!() ETSImpl;
200         }
201 
202 
203         static assert(is(typeof(_fun(ETS.init))));
204 
205 
206         static string expandMacro(string a, string b)
207         {
208             string dst;
209             foreach(i, isRange; IndexOfRangeTypeTF)
210             {
211               static if(isRange)
212               {
213                 if(a)
214                     dst ~= format(a, i);
215               }
216               else
217               {
218                 if(b)
219                     dst ~= format(b, i);
220               }
221             }
222             return dst;
223         }
224 
225       public:
226 
227       static if(asB && allSatisfy!(isBidirectionalRange, RangesTypes) && allSatisfy!(hasLength, RangesTypes))
228       {
229         @property
230         auto ref back()
231         {
232             return mixin("_fun(" ~ expandMacro("_input[%1$s].back,", "_input[%1$s],") ~ ")");
233         }
234 
235 
236         void popBack()
237         {
238             mixin(expandMacro("_input[%1$s].popBack();\n", null));
239         }
240       }
241         
242         static if(allSatisfy!(isInfinite, RangesTypes))
243         {
244             enum bool empty = false;
245         }
246         else
247         {
248             @property
249             bool empty()
250             {
251                 mixin(expandMacro("if(_input[%1$s].empty) return true;\n", null));
252                 return false;
253             }
254         }
255 
256 
257         void popFront()
258         {
259             mixin(expandMacro("_input[%1$s].popFront();\n", null));
260         }
261 
262 
263         @property
264         auto ref front()
265         {
266             return mixin("_fun(" ~ expandMacro("_input[%1$s].front,", "_input[%1$s],") ~ ")");
267         }
268 
269 
270       static if(allSatisfy!(isRandomAccessRange, RangesTypes))
271       {
272         auto ref opIndex(size_t index)
273         {
274             return mixin("_fun(" ~ expandMacro("_input[%1$s][index],", "_input[%1$s],") ~ ")");
275         }
276       }
277         
278         static if(allSatisfy!(hasLength, RangesTypes))
279         {
280             @property
281             auto length()
282             {
283                 mixin("alias LT = CommonType!(" ~ expandMacro("typeof(_input[%1$s].length),", null) ~ ");");
284 
285                 LT m = LT.max;
286 
287                 mixin(expandMacro("m = min(m, _input[%1$s].length);\n", null));
288                 return m;
289             }
290 
291             alias length opDollar;
292         }
293         
294         static if(allSatisfy!(hasSlicing, RangesTypes))
295         {
296             auto opSlice(size_t idx1, size_t idx2)
297             {
298                 return mixin("TMap!(asB, T)(" ~ expandMacro("_input[%1$s][idx1 .. idx2],", "_input[%1$s],") ~ ")");
299             }
300         }
301         
302         static if(allSatisfy!(isForwardRange, RangesTypes))
303         {
304             @property
305             auto save()
306             {
307                 return mixin("TMap!(asB, T)(" ~ expandMacro("_input[%1$s].save,", "_input[%1$s],") ~ ")");
308             }
309         }
310 
311 
312       static if(allSatisfy!(isBidirectionalRange, RangesTypes) && allSatisfy!(hasLength, RangesTypes))
313       {
314         TMap!(true, T) asBidirectional() @property
315         {
316             auto dst = TMap!(true, T)(this._input);
317 
318             immutable size = dst.length;
319 
320             mixin(expandMacro(q{
321                 static if(hasSlicing!(T[%1$s]))
322                   dst._input[%1$s] = dst._input[%1$s][0 .. size];
323                 else
324                   dst._input[%1$s].popBackN(dst._input[%1$s].length - size);
325               }, null));
326 
327             return dst;
328         }
329       }
330     }
331 }
332 
333 
334 /// ditto
335 unittest
336 {
337     debug scope(failure) writefln("Unittest Failure :%s(%s) ", __FILE__, __LINE__);
338     debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();}
339 
340     auto r1 = [1, 3, 2, 4, 0, 0];
341     auto s = "abc".dup;
342     auto tm1 = tmap!("a", "b", (a, b) => b.repeat(a).array().idup)(r1, s);
343     assert(equal(tm1, [tuple(1, 'a', "a"d),
344                        tuple(3, 'b', "bbb"d),
345                        tuple(2, 'c', "cc"d)]));
346 
347     assert(tmap!"a"(r1, s, "").empty);
348 
349     auto r3 = [1, 2, 3];
350     //first element of [0] expresses r3 is used as range, but second element expresses "abcd" is not used as range.
351     auto ss = tmap!("b[a]", [0])(r3, "abcd");
352     assert(equal(ss, ['b', 'c', 'd'][]));
353     assert(ss.length == 3);
354     assert(equal(ss, ss.save));
355 
356     static assert(isForwardRange!(typeof(ss)));
357     static assert(!isBidirectionalRange!(typeof(ss)));
358     static assert(!isRandomAccessRange!(typeof(ss)));
359 
360     auto ss_b = ss.asBidirectional;
361     static assert(isBidirectionalRange!(typeof(ss_b)));
362     static assert(isRandomAccessRange!(typeof(ss_b)));
363     assert(equal(ss_b.retro, ['d', 'c', 'b']));
364 
365     ///multi function and range-choose test
366     auto tm5 = tmap!("b[a]", "b[a-1]", [0])(r3, "abcd");
367     assert(equal(tm5, [tuple('b', 'a'), tuple('c', 'b'), tuple('d', 'c')][]));
368 }
369 
370 
371 
372 /**
373 各要素にある関数を適用し、それらを結合します。
374 つまり、r.map!fun.concatと等価です
375 */
376 auto flatMap(alias fun, R)(R r)
377 if(isInputRange!R)
378 {
379     return r.map!fun.concat;
380 }
381 
382 ///
383 unittest
384 {
385     debug scope(failure) writefln("Unittest Failure :%s(%s) ", __FILE__, __LINE__);
386     debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();}
387 
388     auto r1 = [1, 2, 3, 4];
389     assert(equal(r1.flatMap!"repeat(a, a)", [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]));
390 
391     auto r2 = ["a b c", "de f", "ghi", "jkl mn"];
392     assert(equal(r2.flatMap!split, ["a", "b", "c", "de", "f", "ghi", "jkl", "mn"]));
393 
394     auto r3 = [1, 2];
395     assert(equal!equal(r3.flatMap!"repeat(a, a).repeat(a)",
396         [[1], [2, 2], [2, 2]]));
397 }
398 
399 
400 /**
401 Phobosの$(D std.algorithm.reduce)の拡張です。
402 つまり、$(D r.reduceEx!f(init))という呼び出しが有効になります。
403 */
404 template reduceEx(f...)
405 if(f.length >= 1)
406 {
407     auto ref reduceEx(R, E)(auto ref R r, auto ref E e)
408     if(is(typeof(std.algorithm.reduce!f(forward!e, forward!r))))
409     {
410         return std.algorithm.reduce!f(forward!e, forward!r);
411     }
412 
413 
414     auto ref reduceEx(R)(auto ref R r)
415     if(is(typeof(std.algorithm.reduce!f(forward!r))))
416     {
417         return std.algorithm.reduce!f(forward!r);
418     }
419 }
420 
421 ///
422 unittest{
423     debug scope(failure) writefln("Unittest Failure :%s(%s) ", __FILE__, __LINE__);
424     debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();}
425 
426     assert(reduceEx!"a+1"([1, 2, 3], 1) == reduce!"a+1"(1, [1, 2, 3]));
427     assert(reduceEx!"a+1"([1, 2, 3]) == reduce!"a+1"([1, 2, 3]));
428 }
429 
430 
431 /**
432 reduceは、レンジのすべての要素をたどりますが、scanはその途中結果を要素としてもつレンジです。
433 */
434 auto scan(alias fun, R)(R r)
435 if(isInputRange!R && !isInfinite!R)
436 {
437     alias E = Unqual!(ElementType!R);
438     E e;
439     return scan!fun(e, r);
440 }
441 
442 
443 /// ditto
444 auto scan(alias fun, R, E)(E iniValue, R r)
445 if(isInputRange!R && !isInfinite!R && is(typeof(binaryFun!fun(iniValue, r.front)) : E))
446 {
447     static struct Scan()
448     {
449         @property
450         auto ref front() inout
451         {
452             return _v;
453         }
454 
455 
456         void popFront()
457         {
458             if(!_rIsEmpty){
459                 _v = binaryFun!fun(_v, _r.front);
460                 _r.popFront();
461             }else
462               _isEmpty = true;
463         }
464 
465 
466         @property
467         bool empty()
468         {
469             if(!_rIsEmpty)
470                 _rIsEmpty = _r.empty;
471 
472             return _isEmpty;
473         }
474 
475 
476       static if(isForwardRange!R)
477       {
478         @property
479         auto save()
480         {
481             typeof(this) dst = this;
482 
483             dst._r = dst._r.save;
484 
485             return dst;
486         }
487       }
488 
489 
490       private:
491         E _v;
492         R _r;
493         bool _rIsEmpty = false;
494         bool _isEmpty = false;
495     }
496 
497 
498     return Scan!()(iniValue, r);
499 }
500 
501 ///
502 unittest
503 {
504     debug scope(failure) writefln("Unittest Failure :%s(%s) ", __FILE__, __LINE__);
505     debug scope(success) {writefln("Unittest Success :%s(%s)", __FILE__, __LINE__); stdout.flush();}
506 
507     // test cases : http://zvon.org/other/haskell/Outputprelude/scanl_f.html
508     assert(equal(scan!"a / b"(64, [4, 2, 4]), [64, 16, 8, 2]));
509 
510     int[] none;
511     assert(equal(scan!"a / b"(3, none), [3]));
512 
513     import std.algorithm : max;
514     assert(equal(scan!max(5, [1, 2, 3, 4]), [5, 5, 5, 5, 5]));
515 
516     assert(equal(scan!max(5, [1, 2, 3, 4, 5, 6, 7]), [5, 5, 5, 5, 5, 5, 6, 7]));
517 
518     assert(equal(scan!"2*a + b"(4, [1, 2, 3]), [4, 9, 20, 43]));
519 }