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 }