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