1 // Written in the D programming language. 2 /** 3 This is a submodule of $(MREF std, algorithm). 4 It contains generic searching algorithms. 5 6 $(SCRIPT inhibitQuickIndex = 1;) 7 $(BOOKTABLE Cheat Sheet, 8 $(TR $(TH Function Name) $(TH Description)) 9 $(T2 all, 10 `all!"a > 0"([1, 2, 3, 4])` returns `true` because all elements 11 are positive) 12 $(T2 any, 13 `any!"a > 0"([1, 2, -3, -4])` returns `true` because at least one 14 element is positive) 15 $(T2 balancedParens, 16 `balancedParens("((1 + 1) / 2)")` returns `true` because the 17 string has balanced parentheses.) 18 $(T2 boyerMooreFinder, 19 `find("hello world", boyerMooreFinder("or"))` returns `"orld"` 20 using the $(LINK2 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm, 21 Boyer-Moore _algorithm).) 22 $(T2 canFind, 23 `canFind("hello world", "or")` returns `true`.) 24 $(T2 count, 25 Counts elements that are equal to a specified value or satisfy a 26 predicate. `count([1, 2, 1], 1)` returns `2` and 27 `count!"a < 0"([1, -3, 0])` returns `1`.) 28 $(T2 countUntil, 29 `countUntil(a, b)` returns the number of steps taken in `a` to 30 reach `b`; for example, `countUntil("hello!", "o")` returns 31 `4`.) 32 $(T2 commonPrefix, 33 `commonPrefix("parakeet", "parachute")` returns `"para"`.) 34 $(T2 endsWith, 35 `endsWith("rocks", "ks")` returns `true`.) 36 $(T2 find, 37 `find("hello world", "or")` returns `"orld"` using linear search. 38 (For binary search refer to $(REF SortedRange, std,range).)) 39 $(T2 findAdjacent, 40 `findAdjacent([1, 2, 3, 3, 4])` returns the subrange starting with 41 two equal adjacent elements, i.e. `[3, 3, 4]`.) 42 $(T2 findAmong, 43 `findAmong("abcd", "qcx")` returns `"cd"` because `'c'` is 44 among `"qcx"`.) 45 $(T2 findSkip, 46 If `a = "abcde"`, then `findSkip(a, "x")` returns `false` and 47 leaves `a` unchanged, whereas `findSkip(a, "c")` advances `a` 48 to `"de"` and returns `true`.) 49 $(T2 findSplit, 50 `findSplit("abcdefg", "de")` returns the three ranges `"abc"`, 51 `"de"`, and `"fg"`.) 52 $(T2 findSplitAfter, 53 `findSplitAfter("abcdefg", "de")` returns the two ranges 54 `"abcde"` and `"fg"`.) 55 $(T2 findSplitBefore, 56 `findSplitBefore("abcdefg", "de")` returns the two ranges `"abc"` 57 and `"defg"`.) 58 $(T2 minCount, 59 `minCount([2, 1, 1, 4, 1])` returns `tuple(1, 3)`.) 60 $(T2 maxCount, 61 `maxCount([2, 4, 1, 4, 1])` returns `tuple(4, 2)`.) 62 $(T2 minElement, 63 Selects the minimal element of a range. 64 `minElement([3, 4, 1, 2])` returns `1`.) 65 $(T2 maxElement, 66 Selects the maximal element of a range. 67 `maxElement([3, 4, 1, 2])` returns `4`.) 68 $(T2 minIndex, 69 Index of the minimal element of a range. 70 `minElement([3, 4, 1, 2])` returns `2`.) 71 $(T2 maxIndex, 72 Index of the maximal element of a range. 73 `maxElement([3, 4, 1, 2])` returns `1`.) 74 $(T2 minPos, 75 `minPos([2, 3, 1, 3, 4, 1])` returns the subrange `[1, 3, 4, 1]`, 76 i.e., positions the range at the first occurrence of its minimal 77 element.) 78 $(T2 maxPos, 79 `maxPos([2, 3, 1, 3, 4, 1])` returns the subrange `[4, 1]`, 80 i.e., positions the range at the first occurrence of its maximal 81 element.) 82 $(T2 skipOver, 83 Assume `a = "blah"`. Then `skipOver(a, "bi")` leaves `a` 84 unchanged and returns `false`, whereas `skipOver(a, "bl")` 85 advances `a` to refer to `"ah"` and returns `true`.) 86 $(T2 startsWith, 87 `startsWith("hello, world", "hello")` returns `true`.) 88 $(T2 until, 89 Lazily iterates a range until a specific value is found.) 90 ) 91 92 Copyright: Andrei Alexandrescu 2008-. 93 94 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). 95 96 Authors: $(HTTP erdani.com, Andrei Alexandrescu) 97 98 Source: $(PHOBOSSRC std/algorithm/searching.d) 99 100 Macros: 101 T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) 102 */ 103 module std.algorithm.searching; 104 105 import std.functional : unaryFun, binaryFun; 106 import std.range.primitives; 107 import std.traits; 108 import std.typecons : Tuple, Flag, Yes, No, tuple; 109 110 /++ 111 Checks if $(I _all) of the elements verify `pred`. 112 +/ 113 template all(alias pred = "a") 114 { 115 /++ 116 Returns `true` if and only if $(I _all) values `v` found in the 117 input range `range` satisfy the predicate `pred`. 118 Performs (at most) $(BIGOH range.length) evaluations of `pred`. 119 +/ 120 bool all(Range)(Range range) 121 if (isInputRange!Range) 122 { 123 static assert(is(typeof(unaryFun!pred(range.front))), 124 "`" ~ pred.stringof[1..$-1] ~ "` isn't a unary predicate function for range.front"); 125 import std.functional : not; 126 127 return find!(not!(unaryFun!pred))(range).empty; 128 } 129 } 130 131 /// 132 @safe unittest 133 { 134 assert( all!"a & 1"([1, 3, 5, 7, 9])); 135 assert(!all!"a & 1"([1, 2, 3, 5, 7, 9])); 136 } 137 138 /++ 139 `all` can also be used without a predicate, if its items can be 140 evaluated to true or false in a conditional statement. This can be a 141 convenient way to quickly evaluate that $(I _all) of the elements of a range 142 are true. 143 +/ 144 @safe unittest 145 { 146 int[3] vals = [5, 3, 18]; 147 assert( all(vals[])); 148 } 149 150 @safe unittest 151 { 152 int x = 1; 153 assert(all!(a => a > x)([2, 3])); 154 assert(all!"a == 0x00c9"("\xc3\x89")); // Test that `all` auto-decodes. 155 } 156 157 /++ 158 Checks if $(I _any) of the elements verifies `pred`. 159 `!any` can be used to verify that $(I none) of the elements verify 160 `pred`. 161 This is sometimes called `exists` in other languages. 162 +/ 163 template any(alias pred = "a") 164 { 165 /++ 166 Returns `true` if and only if $(I _any) value `v` found in the 167 input range `range` satisfies the predicate `pred`. 168 Performs (at most) $(BIGOH range.length) evaluations of `pred`. 169 +/ 170 bool any(Range)(Range range) 171 if (isInputRange!Range && is(typeof(unaryFun!pred(range.front)))) 172 { 173 return !find!pred(range).empty; 174 } 175 } 176 177 /// 178 @safe unittest 179 { 180 import std.ascii : isWhite; 181 assert( all!(any!isWhite)(["a a", "b b"])); 182 assert(!any!(all!isWhite)(["a a", "b b"])); 183 } 184 185 /++ 186 `any` can also be used without a predicate, if its items can be 187 evaluated to true or false in a conditional statement. `!any` can be a 188 convenient way to quickly test that $(I none) of the elements of a range 189 evaluate to true. 190 +/ 191 @safe unittest 192 { 193 int[3] vals1 = [0, 0, 0]; 194 assert(!any(vals1[])); //none of vals1 evaluate to true 195 196 int[3] vals2 = [2, 0, 2]; 197 assert( any(vals2[])); 198 assert(!all(vals2[])); 199 200 int[3] vals3 = [3, 3, 3]; 201 assert( any(vals3[])); 202 assert( all(vals3[])); 203 } 204 205 @safe unittest 206 { 207 auto a = [ 1, 2, 0, 4 ]; 208 assert(any!"a == 2"(a)); 209 assert(any!"a == 0x3000"("\xe3\x80\x80")); // Test that `any` auto-decodes. 210 } 211 212 // balancedParens 213 /** 214 Checks whether `r` has "balanced parentheses", i.e. all instances 215 of `lPar` are closed by corresponding instances of `rPar`. The 216 parameter `maxNestingLevel` controls the nesting level allowed. The 217 most common uses are the default or `0`. In the latter case, no 218 nesting is allowed. 219 220 Params: 221 r = The range to check. 222 lPar = The element corresponding with a left (opening) parenthesis. 223 rPar = The element corresponding with a right (closing) parenthesis. 224 maxNestingLevel = The maximum allowed nesting level. 225 226 Returns: 227 true if the given range has balanced parenthesis within the given maximum 228 nesting level; false otherwise. 229 */ 230 bool balancedParens(Range, E)(Range r, E lPar, E rPar, 231 size_t maxNestingLevel = size_t.max) 232 if (isInputRange!(Range) && is(typeof(r.front == lPar))) 233 { 234 size_t count; 235 236 static if (is(immutable ElementEncodingType!Range == immutable E) && isNarrowString!Range) 237 { 238 import std.utf : byCodeUnit; 239 auto rn = r.byCodeUnit; 240 } 241 else 242 { 243 alias rn = r; 244 } 245 246 for (; !rn.empty; rn.popFront()) 247 { 248 if (rn.front == lPar) 249 { 250 if (count > maxNestingLevel) return false; 251 ++count; 252 } 253 else if (rn.front == rPar) 254 { 255 if (!count) return false; 256 --count; 257 } 258 } 259 return count == 0; 260 } 261 262 /// 263 @safe pure unittest 264 { 265 auto s = "1 + (2 * (3 + 1 / 2)"; 266 assert(!balancedParens(s, '(', ')')); 267 s = "1 + (2 * (3 + 1) / 2)"; 268 assert(balancedParens(s, '(', ')')); 269 s = "1 + (2 * (3 + 1) / 2)"; 270 assert(!balancedParens(s, '(', ')', 0)); 271 s = "1 + (2 * 3 + 1) / (2 - 5)"; 272 assert(balancedParens(s, '(', ')', 0)); 273 s = "f(x) = ⌈x⌉"; 274 assert(balancedParens(s, '⌈', '⌉')); 275 } 276 277 /** 278 * Sets up Boyer-Moore matching for use with `find` below. 279 * By default, elements are compared for equality. 280 * 281 * `BoyerMooreFinder` allocates GC memory. 282 * 283 * Params: 284 * pred = Predicate used to compare elements. 285 * needle = A random-access range with length and slicing. 286 * 287 * Returns: 288 * An instance of `BoyerMooreFinder` that can be used with `find()` to 289 * invoke the Boyer-Moore matching algorithm for finding of `needle` in a 290 * given haystack. 291 */ 292 struct BoyerMooreFinder(alias pred, Range) 293 { 294 private: 295 size_t[] skip; // GC allocated 296 ptrdiff_t[ElementType!(Range)] occ; // GC allocated 297 Range needle; 298 299 ptrdiff_t occurrence(ElementType!(Range) c) scope 300 { 301 auto p = c in occ; 302 return p ? *p : -1; 303 } 304 305 /* 306 This helper function checks whether the last "portion" bytes of 307 "needle" (which is "nlen" bytes long) exist within the "needle" at 308 offset "offset" (counted from the end of the string), and whether the 309 character preceding "offset" is not a match. Notice that the range 310 being checked may reach beyond the beginning of the string. Such range 311 is ignored. 312 */ 313 static bool needlematch(R)(R needle, 314 size_t portion, size_t offset) 315 { 316 import std.algorithm.comparison : equal; 317 ptrdiff_t virtual_begin = needle.length - offset - portion; 318 ptrdiff_t ignore = 0; 319 if (virtual_begin < 0) 320 { 321 ignore = -virtual_begin; 322 virtual_begin = 0; 323 } 324 if (virtual_begin > 0 325 && needle[virtual_begin - 1] == needle[$ - portion - 1]) 326 return 0; 327 328 immutable delta = portion - ignore; 329 return equal(needle[needle.length - delta .. needle.length], 330 needle[virtual_begin .. virtual_begin + delta]); 331 } 332 333 public: 334 /// 335 this(Range needle) 336 { 337 if (!needle.length) return; 338 this.needle = needle; 339 /* Populate table with the analysis of the needle */ 340 /* But ignoring the last letter */ 341 foreach (i, n ; needle[0 .. $ - 1]) 342 { 343 this.occ[n] = i; 344 } 345 /* Preprocess #2: init skip[] */ 346 /* Note: This step could be made a lot faster. 347 * A simple implementation is shown here. */ 348 this.skip = new size_t[needle.length]; 349 foreach (a; 0 .. needle.length) 350 { 351 size_t value = 0; 352 while (value < needle.length 353 && !needlematch(needle, a, value)) 354 { 355 ++value; 356 } 357 this.skip[needle.length - a - 1] = value; 358 } 359 } 360 361 /// 362 Range beFound(Range haystack) scope 363 { 364 import std.algorithm.comparison : max; 365 366 if (!needle.length) return haystack; 367 if (needle.length > haystack.length) return haystack[$ .. $]; 368 /* Search: */ 369 immutable limit = haystack.length - needle.length; 370 for (size_t hpos = 0; hpos <= limit; ) 371 { 372 size_t npos = needle.length - 1; 373 while (pred(needle[npos], haystack[npos+hpos])) 374 { 375 if (npos == 0) return haystack[hpos .. $]; 376 --npos; 377 } 378 hpos += max(skip[npos], cast(ptrdiff_t) npos - occurrence(haystack[npos+hpos])); 379 } 380 return haystack[$ .. $]; 381 } 382 383 /// 384 @property size_t length() 385 { 386 return needle.length; 387 } 388 389 /// 390 alias opDollar = length; 391 } 392 393 /// Ditto 394 BoyerMooreFinder!(binaryFun!(pred), Range) boyerMooreFinder 395 (alias pred = "a == b", Range) 396 (Range needle) 397 if ((isRandomAccessRange!(Range) && hasSlicing!Range) || isSomeString!Range) 398 { 399 return typeof(return)(needle); 400 } 401 402 /// 403 @safe pure nothrow unittest 404 { 405 auto bmFinder = boyerMooreFinder("TG"); 406 407 string r = "TAGTGCCTGA"; 408 // search for the first match in the haystack r 409 r = bmFinder.beFound(r); 410 assert(r == "TGCCTGA"); 411 412 // continue search in haystack 413 r = bmFinder.beFound(r[2 .. $]); 414 assert(r == "TGA"); 415 } 416 417 /** 418 Returns the common prefix of two ranges. 419 420 Params: 421 pred = The predicate to use in comparing elements for commonality. Defaults 422 to equality `"a == b"`. 423 424 r1 = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) of 425 elements. 426 427 r2 = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of 428 elements. 429 430 Returns: 431 A slice of `r1` which contains the characters that both ranges start with, 432 if the first argument is a string; otherwise, the same as the result of 433 `takeExactly(r1, n)`, where `n` is the number of elements in the common 434 prefix of both ranges. 435 436 See_Also: 437 $(REF takeExactly, std,range) 438 */ 439 auto commonPrefix(alias pred = "a == b", R1, R2)(R1 r1, R2 r2) 440 if (isForwardRange!R1 && isInputRange!R2 && 441 !isNarrowString!R1 && 442 is(typeof(binaryFun!pred(r1.front, r2.front)))) 443 { 444 import std.algorithm.comparison : min; 445 static if (isRandomAccessRange!R1 && isRandomAccessRange!R2 && 446 hasLength!R1 && hasLength!R2 && 447 hasSlicing!R1) 448 { 449 immutable limit = min(r1.length, r2.length); 450 foreach (i; 0 .. limit) 451 { 452 if (!binaryFun!pred(r1[i], r2[i])) 453 { 454 return r1[0 .. i]; 455 } 456 } 457 return r1[0 .. limit]; 458 } 459 else 460 { 461 import std.range : takeExactly; 462 auto result = r1.save; 463 size_t i = 0; 464 for (; 465 !r1.empty && !r2.empty && binaryFun!pred(r1.front, r2.front); 466 ++i, r1.popFront(), r2.popFront()) 467 {} 468 return takeExactly(result, i); 469 } 470 } 471 472 /// 473 @safe unittest 474 { 475 assert(commonPrefix("hello, world", "hello, there") == "hello, "); 476 } 477 478 /// ditto 479 auto commonPrefix(alias pred, R1, R2)(R1 r1, R2 r2) 480 if (isNarrowString!R1 && isInputRange!R2 && 481 is(typeof(binaryFun!pred(r1.front, r2.front)))) 482 { 483 import std.utf : decode; 484 485 auto result = r1.save; 486 immutable len = r1.length; 487 size_t i = 0; 488 489 for (size_t j = 0; i < len && !r2.empty; r2.popFront(), i = j) 490 { 491 immutable f = decode(r1, j); 492 if (!binaryFun!pred(f, r2.front)) 493 break; 494 } 495 496 return result[0 .. i]; 497 } 498 499 /// ditto 500 auto commonPrefix(R1, R2)(R1 r1, R2 r2) 501 if (isNarrowString!R1 && isInputRange!R2 && !isNarrowString!R2 && 502 is(typeof(r1.front == r2.front))) 503 { 504 return commonPrefix!"a == b"(r1, r2); 505 } 506 507 /// ditto 508 auto commonPrefix(R1, R2)(R1 r1, R2 r2) 509 if (isNarrowString!R1 && isNarrowString!R2) 510 { 511 import std.algorithm.comparison : min; 512 513 static if (ElementEncodingType!R1.sizeof == ElementEncodingType!R2.sizeof) 514 { 515 import std.utf : stride, UTFException; 516 517 immutable limit = min(r1.length, r2.length); 518 for (size_t i = 0; i < limit;) 519 { 520 immutable codeLen = stride(r1, i); 521 size_t j = 0; 522 523 for (; j < codeLen && i < limit; ++i, ++j) 524 { 525 if (r1[i] != r2[i]) 526 return r1[0 .. i - j]; 527 } 528 529 if (i == limit && j < codeLen) 530 throw new UTFException("Invalid UTF-8 sequence", i); 531 } 532 return r1[0 .. limit]; 533 } 534 else 535 return commonPrefix!"a == b"(r1, r2); 536 } 537 538 @safe unittest 539 { 540 import std.algorithm.comparison : equal; 541 import std.algorithm.iteration : filter; 542 import std.conv : to; 543 import std.exception : assertThrown; 544 import std.meta : AliasSeq; 545 import std.range; 546 import std.utf : UTFException; 547 548 assert(commonPrefix([1, 2, 3], [1, 2, 3, 4, 5]) == [1, 2, 3]); 549 assert(commonPrefix([1, 2, 3, 4, 5], [1, 2, 3]) == [1, 2, 3]); 550 assert(commonPrefix([1, 2, 3, 4], [1, 2, 3, 4]) == [1, 2, 3, 4]); 551 assert(commonPrefix([1, 2, 3], [7, 2, 3, 4, 5]).empty); 552 assert(commonPrefix([7, 2, 3, 4, 5], [1, 2, 3]).empty); 553 assert(commonPrefix([1, 2, 3], cast(int[]) null).empty); 554 assert(commonPrefix(cast(int[]) null, [1, 2, 3]).empty); 555 assert(commonPrefix(cast(int[]) null, cast(int[]) null).empty); 556 557 static foreach (S; AliasSeq!(char[], const(char)[], string, 558 wchar[], const(wchar)[], wstring, 559 dchar[], const(dchar)[], dstring)) 560 { 561 static foreach (T; AliasSeq!(string, wstring, dstring)) 562 { 563 assert(commonPrefix(to!S(""), to!T("")).empty); 564 assert(commonPrefix(to!S(""), to!T("hello")).empty); 565 assert(commonPrefix(to!S("hello"), to!T("")).empty); 566 assert(commonPrefix(to!S("hello, world"), to!T("hello, there")) == to!S("hello, ")); 567 assert(commonPrefix(to!S("hello, there"), to!T("hello, world")) == to!S("hello, ")); 568 assert(commonPrefix(to!S("hello, "), to!T("hello, world")) == to!S("hello, ")); 569 assert(commonPrefix(to!S("hello, world"), to!T("hello, ")) == to!S("hello, ")); 570 assert(commonPrefix(to!S("hello, world"), to!T("hello, world")) == to!S("hello, world")); 571 572 // https://issues.dlang.org/show_bug.cgi?id=8890 573 assert(commonPrefix(to!S("Пиво"), to!T("Пони"))== to!S("П")); 574 assert(commonPrefix(to!S("Пони"), to!T("Пиво"))== to!S("П")); 575 assert(commonPrefix(to!S("Пиво"), to!T("Пиво"))== to!S("Пиво")); 576 assert(commonPrefix(to!S("\U0010FFFF\U0010FFFB\U0010FFFE"), 577 to!T("\U0010FFFF\U0010FFFB\U0010FFFC")) == to!S("\U0010FFFF\U0010FFFB")); 578 assert(commonPrefix(to!S("\U0010FFFF\U0010FFFB\U0010FFFC"), 579 to!T("\U0010FFFF\U0010FFFB\U0010FFFE")) == to!S("\U0010FFFF\U0010FFFB")); 580 assert(commonPrefix!"a != b"(to!S("Пиво"), to!T("онво")) == to!S("Пи")); 581 assert(commonPrefix!"a != b"(to!S("онво"), to!T("Пиво")) == to!S("он")); 582 } 583 584 static assert(is(typeof(commonPrefix(to!S("Пиво"), filter!"true"("Пони"))) == S)); 585 assert(equal(commonPrefix(to!S("Пиво"), filter!"true"("Пони")), to!S("П"))); 586 587 static assert(is(typeof(commonPrefix(filter!"true"("Пиво"), to!S("Пони"))) == 588 typeof(takeExactly(filter!"true"("П"), 1)))); 589 assert(equal(commonPrefix(filter!"true"("Пиво"), to!S("Пони")), takeExactly(filter!"true"("П"), 1))); 590 } 591 592 assertThrown!UTFException(commonPrefix("\U0010FFFF\U0010FFFB", "\U0010FFFF\U0010FFFB"[0 .. $ - 1])); 593 594 assert(commonPrefix("12345"d, [49, 50, 51, 60, 60]) == "123"d); 595 assert(commonPrefix([49, 50, 51, 60, 60], "12345" ) == [49, 50, 51]); 596 assert(commonPrefix([49, 50, 51, 60, 60], "12345"d) == [49, 50, 51]); 597 598 assert(commonPrefix!"a == ('0' + b)"("12345" , [1, 2, 3, 9, 9]) == "123"); 599 assert(commonPrefix!"a == ('0' + b)"("12345"d, [1, 2, 3, 9, 9]) == "123"d); 600 assert(commonPrefix!"('0' + a) == b"([1, 2, 3, 9, 9], "12345" ) == [1, 2, 3]); 601 assert(commonPrefix!"('0' + a) == b"([1, 2, 3, 9, 9], "12345"d) == [1, 2, 3]); 602 } 603 604 // count 605 /** 606 The first version counts the number of elements `x` in `r` for 607 which `pred(x, value)` is `true`. `pred` defaults to 608 equality. Performs $(BIGOH haystack.length) evaluations of `pred`. 609 610 The second version returns the number of times `needle` occurs in 611 `haystack`. Throws an exception if `needle.empty`, as the _count 612 of the empty range in any range would be infinite. Overlapped counts 613 are not considered, for example `count("aaa", "aa")` is `1`, not 614 `2`. 615 616 The third version counts the elements for which `pred(x)` is $(D 617 true). Performs $(BIGOH haystack.length) evaluations of `pred`. 618 619 The fourth version counts the number of elements in a range. It is 620 an optimization for the third version: if the given range has the 621 `length` property the count is returned right away, otherwise 622 performs $(BIGOH haystack.length) to walk the range. 623 624 Note: Regardless of the overload, `count` will not accept 625 infinite ranges for `haystack`. 626 627 Params: 628 pred = The predicate to evaluate. 629 haystack = The range to _count. 630 needle = The element or sub-range to _count in the `haystack`. 631 632 Returns: 633 The number of positions in the `haystack` for which `pred` returned true. 634 */ 635 size_t count(alias pred = "a == b", Range, E)(Range haystack, E needle) 636 if (isInputRange!Range && !isInfinite!Range && 637 is(typeof(binaryFun!pred(haystack.front, needle)) : bool)) 638 { 639 bool pred2(ElementType!Range a) { return binaryFun!pred(a, needle); } 640 return count!pred2(haystack); 641 } 642 643 /// 644 @safe unittest 645 { 646 import std.uni : toLower; 647 648 // count elements in range 649 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; 650 assert(count(a) == 9); 651 assert(count(a, 2) == 3); 652 assert(count!("a > b")(a, 2) == 5); 653 // count range in range 654 assert(count("abcadfabf", "ab") == 2); 655 assert(count("ababab", "abab") == 1); 656 assert(count("ababab", "abx") == 0); 657 // fuzzy count range in range 658 assert(count!((a, b) => toLower(a) == toLower(b))("AbcAdFaBf", "ab") == 2); 659 // count predicate in range 660 assert(count!("a > 1")(a) == 8); 661 } 662 663 @safe unittest 664 { 665 import std.conv : text; 666 667 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; 668 assert(count(a, 2) == 3, text(count(a, 2))); 669 assert(count!("a > b")(a, 2) == 5, text(count!("a > b")(a, 2))); 670 671 // check strings 672 assert(count("日本語") == 3); 673 assert(count("日本語"w) == 3); 674 assert(count("日本語"d) == 3); 675 676 assert(count!("a == '日'")("日本語") == 1); 677 assert(count!("a == '本'")("日本語"w) == 1); 678 assert(count!("a == '語'")("日本語"d) == 1); 679 } 680 681 @safe unittest 682 { 683 string s = "This is a fofofof list"; 684 string sub = "fof"; 685 assert(count(s, sub) == 2); 686 } 687 688 /// Ditto 689 size_t count(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 690 if (isForwardRange!R1 && !isInfinite!R1 && 691 isForwardRange!R2 && 692 is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool)) 693 { 694 assert(!needle.empty, "Cannot count occurrences of an empty range"); 695 696 static if (isInfinite!R2) 697 { 698 //Note: This is the special case of looking for an infinite inside a finite... 699 //"How many instances of the Fibonacci sequence can you count in [1, 2, 3]?" - "None." 700 return 0; 701 } 702 else 703 { 704 size_t result; 705 //Note: haystack is not saved, because findskip is designed to modify it 706 for ( ; findSkip!pred(haystack, needle.save) ; ++result) 707 {} 708 return result; 709 } 710 } 711 712 /// Ditto 713 size_t count(alias pred, R)(R haystack) 714 if (isInputRange!R && !isInfinite!R && 715 is(typeof(unaryFun!pred(haystack.front)) : bool)) 716 { 717 size_t result; 718 alias T = ElementType!R; //For narrow strings forces dchar iteration 719 foreach (T elem; haystack) 720 if (unaryFun!pred(elem)) ++result; 721 return result; 722 } 723 724 /// Ditto 725 size_t count(R)(R haystack) 726 if (isInputRange!R && !isInfinite!R) 727 { 728 return walkLength(haystack); 729 } 730 731 @safe unittest 732 { 733 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; 734 assert(count!("a == 3")(a) == 2); 735 assert(count("日本語") == 3); 736 } 737 738 // https://issues.dlang.org/show_bug.cgi?id=11253 739 @safe nothrow unittest 740 { 741 assert([1, 2, 3].count([2, 3]) == 1); 742 } 743 744 /++ 745 Counts elements in the given 746 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) 747 until the given predicate is true for one of the given `needles`. 748 749 Params: 750 pred = The predicate for determining when to stop counting. 751 haystack = The 752 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be 753 counted. 754 needles = Either a single element, or a 755 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) 756 of elements, to be evaluated in turn against each 757 element in `haystack` under the given predicate. 758 759 Returns: The number of elements which must be popped from the front of 760 `haystack` before reaching an element for which 761 `startsWith!pred(haystack, needles)` is `true`. If 762 `startsWith!pred(haystack, needles)` is not `true` for any element in 763 `haystack`, then `-1` is returned. If only `pred` is provided, 764 `pred(haystack)` is tested for each element. 765 766 See_Also: $(REF indexOf, std,string) 767 +/ 768 ptrdiff_t countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles) 769 if (isForwardRange!R 770 && Rs.length > 0 771 && isForwardRange!(Rs[0]) == isInputRange!(Rs[0]) 772 && is(typeof(startsWith!pred(haystack, needles[0]))) 773 && (Rs.length == 1 774 || is(typeof(countUntil!pred(haystack, needles[1 .. $]))))) 775 { 776 typeof(return) result; 777 778 static if (needles.length == 1) 779 { 780 static if (hasLength!R) //Note: Narrow strings don't have length. 781 { 782 //We delegate to find because find is very efficient. 783 //We store the length of the haystack so we don't have to save it. 784 auto len = haystack.length; 785 auto r2 = find!pred(haystack, needles[0]); 786 if (!r2.empty) 787 return cast(typeof(return)) (len - r2.length); 788 } 789 else 790 { 791 import std.range : dropOne; 792 793 if (needles[0].empty) 794 return 0; 795 796 //Default case, slower route doing startsWith iteration 797 for ( ; !haystack.empty ; ++result ) 798 { 799 //We compare the first elements of the ranges here before 800 //forwarding to startsWith. This avoids making useless saves to 801 //haystack/needle if they aren't even going to be mutated anyways. 802 //It also cuts down on the amount of pops on haystack. 803 if (binaryFun!pred(haystack.front, needles[0].front)) 804 { 805 //Here, we need to save the needle before popping it. 806 //haystack we pop in all paths, so we do that, and then save. 807 haystack.popFront(); 808 if (startsWith!pred(haystack.save, needles[0].save.dropOne())) 809 return result; 810 } 811 else 812 haystack.popFront(); 813 } 814 } 815 } 816 else 817 { 818 foreach (i, Ri; Rs) 819 { 820 static if (isForwardRange!Ri) 821 { 822 if (needles[i].empty) 823 return 0; 824 } 825 } 826 Tuple!Rs t; 827 foreach (i, Ri; Rs) 828 { 829 static if (!isForwardRange!Ri) 830 { 831 t[i] = needles[i]; 832 } 833 } 834 for (; !haystack.empty ; ++result, haystack.popFront()) 835 { 836 foreach (i, Ri; Rs) 837 { 838 static if (isForwardRange!Ri) 839 { 840 t[i] = needles[i].save; 841 } 842 } 843 if (startsWith!pred(haystack.save, t.expand)) 844 { 845 return result; 846 } 847 } 848 } 849 850 // Because of https://issues.dlang.org/show_bug.cgi?id=8804 851 // Avoids both "unreachable code" or "no return statement" 852 static if (isInfinite!R) assert(false, R.stringof ~ " must not be an" 853 ~ " infinite range"); 854 else return -1; 855 } 856 857 /// ditto 858 ptrdiff_t countUntil(alias pred = "a == b", R, N)(R haystack, N needle) 859 if (isInputRange!R && 860 is(typeof(binaryFun!pred(haystack.front, needle)) : bool)) 861 { 862 bool pred2(ElementType!R a) { return binaryFun!pred(a, needle); } 863 return countUntil!pred2(haystack); 864 } 865 866 /// 867 @safe unittest 868 { 869 assert(countUntil("hello world", "world") == 6); 870 assert(countUntil("hello world", 'r') == 8); 871 assert(countUntil("hello world", "programming") == -1); 872 assert(countUntil("日本語", "本語") == 1); 873 assert(countUntil("日本語", '語') == 2); 874 assert(countUntil("日本語", "五") == -1); 875 assert(countUntil("日本語", '五') == -1); 876 assert(countUntil([0, 7, 12, 22, 9], [12, 22]) == 2); 877 assert(countUntil([0, 7, 12, 22, 9], 9) == 4); 878 assert(countUntil!"a > b"([0, 7, 12, 22, 9], 20) == 3); 879 } 880 881 @safe unittest 882 { 883 import std.algorithm.iteration : filter; 884 import std.internal.test.dummyrange; 885 886 assert(countUntil("日本語", "") == 0); 887 assert(countUntil("日本語"d, "") == 0); 888 889 assert(countUntil("", "") == 0); 890 assert(countUntil("".filter!"true"(), "") == 0); 891 892 auto rf = [0, 20, 12, 22, 9].filter!"true"(); 893 assert(rf.countUntil!"a > b"((int[]).init) == 0); 894 assert(rf.countUntil!"a > b"(20) == 3); 895 assert(rf.countUntil!"a > b"([20, 8]) == 3); 896 assert(rf.countUntil!"a > b"([20, 10]) == -1); 897 assert(rf.countUntil!"a > b"([20, 8, 0]) == -1); 898 899 auto r = new ReferenceForwardRange!int([0, 1, 2, 3, 4, 5, 6]); 900 auto r2 = new ReferenceForwardRange!int([3, 4]); 901 auto r3 = new ReferenceForwardRange!int([3, 5]); 902 assert(r.save.countUntil(3) == 3); 903 assert(r.save.countUntil(r2) == 3); 904 assert(r.save.countUntil(7) == -1); 905 assert(r.save.countUntil(r3) == -1); 906 } 907 908 @safe unittest 909 { 910 assert(countUntil("hello world", "world", "asd") == 6); 911 assert(countUntil("hello world", "world", "ello") == 1); 912 assert(countUntil("hello world", "world", "") == 0); 913 assert(countUntil("hello world", "world", 'l') == 2); 914 } 915 916 /// ditto 917 ptrdiff_t countUntil(alias pred, R)(R haystack) 918 if (isInputRange!R && 919 is(typeof(unaryFun!pred(haystack.front)) : bool)) 920 { 921 typeof(return) i; 922 static if (isRandomAccessRange!R) 923 { 924 //Optimized RA implementation. Since we want to count *and* iterate at 925 //the same time, it is more efficient this way. 926 static if (hasLength!R) 927 { 928 immutable len = cast(typeof(return)) haystack.length; 929 for ( ; i < len ; ++i ) 930 if (unaryFun!pred(haystack[i])) return i; 931 } 932 else //if (isInfinite!R) 933 { 934 for ( ; ; ++i ) 935 if (unaryFun!pred(haystack[i])) return i; 936 } 937 } 938 else static if (hasLength!R) 939 { 940 //For those odd ranges that have a length, but aren't RA. 941 //It is faster to quick find, and then compare the lengths 942 auto r2 = find!pred(haystack.save); 943 if (!r2.empty) return cast(typeof(return)) (haystack.length - r2.length); 944 } 945 else //Everything else 946 { 947 alias T = ElementType!R; //For narrow strings forces dchar iteration 948 foreach (T elem; haystack) 949 { 950 if (unaryFun!pred(elem)) return i; 951 ++i; 952 } 953 } 954 955 // Because of https://issues.dlang.org/show_bug.cgi?id=8804 956 // Avoids both "unreachable code" or "no return statement" 957 static if (isInfinite!R) assert(false, R.stringof ~ " must not be an" 958 ~ " inifite range"); 959 else return -1; 960 } 961 962 /// 963 @safe unittest 964 { 965 import std.ascii : isDigit; 966 import std.uni : isWhite; 967 968 assert(countUntil!(std.uni.isWhite)("hello world") == 5); 969 assert(countUntil!(std.ascii.isDigit)("hello world") == -1); 970 assert(countUntil!"a > 20"([0, 7, 12, 22, 9]) == 3); 971 } 972 973 @safe unittest 974 { 975 import std.internal.test.dummyrange; 976 977 // References 978 { 979 // input 980 ReferenceInputRange!int r; 981 r = new ReferenceInputRange!int([0, 1, 2, 3, 4, 5, 6]); 982 assert(r.countUntil(3) == 3); 983 r = new ReferenceInputRange!int([0, 1, 2, 3, 4, 5, 6]); 984 assert(r.countUntil(7) == -1); 985 } 986 { 987 // forward 988 auto r = new ReferenceForwardRange!int([0, 1, 2, 3, 4, 5, 6]); 989 assert(r.save.countUntil([3, 4]) == 3); 990 assert(r.save.countUntil(3) == 3); 991 assert(r.save.countUntil([3, 7]) == -1); 992 assert(r.save.countUntil(7) == -1); 993 } 994 { 995 // infinite forward 996 auto r = new ReferenceInfiniteForwardRange!int(0); 997 assert(r.save.countUntil([3, 4]) == 3); 998 assert(r.save.countUntil(3) == 3); 999 } 1000 } 1001 1002 /** 1003 Checks if the given range ends with (one of) the given needle(s). 1004 The reciprocal of `startsWith`. 1005 1006 Params: 1007 pred = The predicate to use for comparing elements between the range and 1008 the needle(s). 1009 1010 doesThisEnd = The 1011 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives) 1012 to check. 1013 1014 withOneOfThese = The needles to check against, which may be single 1015 elements, or bidirectional ranges of elements. 1016 1017 withThis = The single element to check. 1018 1019 Returns: 1020 0 if the needle(s) do not occur at the end of the given range; 1021 otherwise the position of the matching needle, that is, 1 if the range ends 1022 with `withOneOfThese[0]`, 2 if it ends with `withOneOfThese[1]`, and so 1023 on. 1024 1025 In the case when no needle parameters are given, return `true` iff back of 1026 `doesThisStart` fulfils predicate `pred`. 1027 */ 1028 uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese) 1029 if (isBidirectionalRange!Range && Needles.length > 1 && 1030 is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[0])) : bool) && 1031 is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[1 .. $])) : uint)) 1032 { 1033 alias haystack = doesThisEnd; 1034 alias needles = withOneOfThese; 1035 1036 // Make one pass looking for empty ranges in needles 1037 foreach (i, Unused; Needles) 1038 { 1039 // Empty range matches everything 1040 static if (!is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool)) 1041 { 1042 if (needles[i].empty) return i + 1; 1043 } 1044 } 1045 1046 for (; !haystack.empty; haystack.popBack()) 1047 { 1048 foreach (i, Unused; Needles) 1049 { 1050 static if (is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool)) 1051 { 1052 // Single-element 1053 if (binaryFun!pred(haystack.back, needles[i])) 1054 { 1055 // found, but continue to account for one-element 1056 // range matches (consider endsWith("ab", "b", 1057 // 'b') should return 1, not 2). 1058 continue; 1059 } 1060 } 1061 else 1062 { 1063 if (binaryFun!pred(haystack.back, needles[i].back)) 1064 continue; 1065 } 1066 1067 // This code executed on failure to match 1068 // Out with this guy, check for the others 1069 uint result = endsWith!pred(haystack, needles[0 .. i], needles[i + 1 .. $]); 1070 if (result > i) ++result; 1071 return result; 1072 } 1073 1074 // If execution reaches this point, then the back matches for all 1075 // needles ranges. What we need to do now is to lop off the back of 1076 // all ranges involved and recurse. 1077 foreach (i, Unused; Needles) 1078 { 1079 static if (is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool)) 1080 { 1081 // Test has passed in the previous loop 1082 return i + 1; 1083 } 1084 else 1085 { 1086 needles[i].popBack(); 1087 if (needles[i].empty) return i + 1; 1088 } 1089 } 1090 } 1091 return 0; 1092 } 1093 1094 /// Ditto 1095 bool endsWith(alias pred = "a == b", R1, R2)(R1 doesThisEnd, R2 withThis) 1096 if (isBidirectionalRange!R1 && 1097 isBidirectionalRange!R2 && 1098 is(typeof(binaryFun!pred(doesThisEnd.back, withThis.back)) : bool)) 1099 { 1100 alias haystack = doesThisEnd; 1101 alias needle = withThis; 1102 1103 static if (is(typeof(pred) : string)) 1104 enum isDefaultPred = pred == "a == b"; 1105 else 1106 enum isDefaultPred = false; 1107 1108 static if (isDefaultPred && isArray!R1 && isArray!R2 && 1109 is(immutable ElementEncodingType!R1 == immutable ElementEncodingType!R2)) 1110 { 1111 if (haystack.length < needle.length) return false; 1112 1113 return haystack[$ - needle.length .. $] == needle; 1114 } 1115 else 1116 { 1117 import std.range : retro; 1118 return startsWith!pred(retro(doesThisEnd), retro(withThis)); 1119 } 1120 } 1121 1122 /// Ditto 1123 bool endsWith(alias pred = "a == b", R, E)(R doesThisEnd, E withThis) 1124 if (isBidirectionalRange!R && 1125 is(typeof(binaryFun!pred(doesThisEnd.back, withThis)) : bool)) 1126 { 1127 if (doesThisEnd.empty) 1128 return false; 1129 1130 static if (is(typeof(pred) : string)) 1131 enum isDefaultPred = pred == "a == b"; 1132 else 1133 enum isDefaultPred = false; 1134 1135 alias predFunc = binaryFun!pred; 1136 1137 // auto-decoding special case 1138 static if (isNarrowString!R) 1139 { 1140 // statically determine decoding is unnecessary to evaluate pred 1141 static if (isDefaultPred && isSomeChar!E && E.sizeof <= ElementEncodingType!R.sizeof) 1142 return doesThisEnd[$ - 1] == withThis; 1143 // specialize for ASCII as to not change previous behavior 1144 else 1145 { 1146 if (withThis <= 0x7F) 1147 return predFunc(doesThisEnd[$ - 1], withThis); 1148 else 1149 return predFunc(doesThisEnd.back, withThis); 1150 } 1151 } 1152 else 1153 { 1154 return predFunc(doesThisEnd.back, withThis); 1155 } 1156 } 1157 1158 /// Ditto 1159 bool endsWith(alias pred, R)(R doesThisEnd) 1160 if (isInputRange!R && 1161 ifTestable!(typeof(doesThisEnd.front), unaryFun!pred)) 1162 { 1163 return !doesThisEnd.empty && unaryFun!pred(doesThisEnd.back); 1164 } 1165 1166 /// 1167 @safe unittest 1168 { 1169 import std.ascii : isAlpha; 1170 assert("abc".endsWith!(a => a.isAlpha)); 1171 assert("abc".endsWith!isAlpha); 1172 1173 assert(!"ab1".endsWith!(a => a.isAlpha)); 1174 1175 assert(!"ab1".endsWith!isAlpha); 1176 assert(!"".endsWith!(a => a.isAlpha)); 1177 1178 import std.algorithm.comparison : among; 1179 assert("abc".endsWith!(a => a.among('c', 'd') != 0)); 1180 assert(!"abc".endsWith!(a => a.among('a', 'b') != 0)); 1181 1182 assert(endsWith("abc", "")); 1183 assert(!endsWith("abc", "b")); 1184 assert(endsWith("abc", "a", 'c') == 2); 1185 assert(endsWith("abc", "c", "a") == 1); 1186 assert(endsWith("abc", "c", "c") == 1); 1187 assert(endsWith("abc", "bc", "c") == 2); 1188 assert(endsWith("abc", "x", "c", "b") == 2); 1189 assert(endsWith("abc", "x", "aa", "bc") == 3); 1190 assert(endsWith("abc", "x", "aaa", "sab") == 0); 1191 assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3); 1192 } 1193 1194 @safe unittest 1195 { 1196 import std.algorithm.iteration : filterBidirectional; 1197 import std.conv : to; 1198 import std.meta : AliasSeq; 1199 1200 static foreach (S; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring)) 1201 (){ // workaround slow optimizations for large functions 1202 // https://issues.dlang.org/show_bug.cgi?id=2396 1203 assert(!endsWith(to!S("abc"), 'a')); 1204 assert(endsWith(to!S("abc"), 'a', 'c') == 2); 1205 assert(!endsWith(to!S("abc"), 'x', 'n', 'b')); 1206 assert(endsWith(to!S("abc"), 'x', 'n', 'c') == 3); 1207 assert(endsWith(to!S("abc\uFF28"), 'a', '\uFF28', 'c') == 2); 1208 1209 static foreach (T; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring)) 1210 { 1211 //Lots of strings 1212 assert(endsWith(to!S("abc"), to!T(""))); 1213 assert(!endsWith(to!S("abc"), to!T("a"))); 1214 assert(!endsWith(to!S("abc"), to!T("b"))); 1215 assert(endsWith(to!S("abc"), to!T("bc"), 'c') == 2); 1216 assert(endsWith(to!S("abc"), to!T("a"), "c") == 2); 1217 assert(endsWith(to!S("abc"), to!T("c"), "a") == 1); 1218 assert(endsWith(to!S("abc"), to!T("c"), "c") == 1); 1219 assert(endsWith(to!S("abc"), to!T("x"), 'c', "b") == 2); 1220 assert(endsWith(to!S("abc"), 'x', to!T("aa"), "bc") == 3); 1221 assert(endsWith(to!S("abc"), to!T("x"), "aaa", "sab") == 0); 1222 assert(endsWith(to!S("abc"), to!T("x"), "aaa", "c", "sab") == 3); 1223 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("l\uFF4co"))); 1224 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("lo"), to!T("l\uFF4co")) == 2); 1225 1226 //Unicode 1227 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("l\uFF4co"))); 1228 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("lo"), to!T("l\uFF4co")) == 2); 1229 assert(endsWith(to!S("日本語"), to!T("本語"))); 1230 assert(endsWith(to!S("日本語"), to!T("日本語"))); 1231 assert(!endsWith(to!S("本語"), to!T("日本語"))); 1232 1233 //Empty 1234 assert(endsWith(to!S(""), T.init)); 1235 assert(!endsWith(to!S(""), 'a')); 1236 assert(endsWith(to!S("a"), T.init)); 1237 assert(endsWith(to!S("a"), T.init, "") == 1); 1238 assert(endsWith(to!S("a"), T.init, 'a') == 1); 1239 assert(endsWith(to!S("a"), 'a', T.init) == 2); 1240 } 1241 }(); 1242 1243 static foreach (T; AliasSeq!(int, short)) 1244 {{ 1245 immutable arr = cast(T[])[0, 1, 2, 3, 4, 5]; 1246 1247 //RA range 1248 assert(endsWith(arr, cast(int[]) null)); 1249 assert(!endsWith(arr, 0)); 1250 assert(!endsWith(arr, 4)); 1251 assert(endsWith(arr, 5)); 1252 assert(endsWith(arr, 0, 4, 5) == 3); 1253 assert(endsWith(arr, [5])); 1254 assert(endsWith(arr, [4, 5])); 1255 assert(endsWith(arr, [4, 5], 7) == 1); 1256 assert(!endsWith(arr, [2, 4, 5])); 1257 assert(endsWith(arr, [2, 4, 5], [3, 4, 5]) == 2); 1258 1259 //Normal input range 1260 assert(!endsWith(filterBidirectional!"true"(arr), 4)); 1261 assert(endsWith(filterBidirectional!"true"(arr), 5)); 1262 assert(endsWith(filterBidirectional!"true"(arr), [5])); 1263 assert(endsWith(filterBidirectional!"true"(arr), [4, 5])); 1264 assert(endsWith(filterBidirectional!"true"(arr), [4, 5], 7) == 1); 1265 assert(!endsWith(filterBidirectional!"true"(arr), [2, 4, 5])); 1266 assert(endsWith(filterBidirectional!"true"(arr), [2, 4, 5], [3, 4, 5]) == 2); 1267 assert(endsWith(arr, filterBidirectional!"true"([4, 5]))); 1268 assert(endsWith(arr, filterBidirectional!"true"([4, 5]), 7) == 1); 1269 assert(!endsWith(arr, filterBidirectional!"true"([2, 4, 5]))); 1270 assert(endsWith(arr, [2, 4, 5], filterBidirectional!"true"([3, 4, 5])) == 2); 1271 1272 //Non-default pred 1273 assert(endsWith!("a%10 == b%10")(arr, [14, 15])); 1274 assert(!endsWith!("a%10 == b%10")(arr, [15, 14])); 1275 }} 1276 } 1277 1278 private enum bool hasConstEmptyMember(T) = is(typeof(((const T* a) => (*a).empty)(null)) : bool); 1279 1280 // Rebindable doesn't work with structs 1281 // see: https://github.com/dlang/phobos/pull/6136 1282 private template RebindableOrUnqual(T) 1283 { 1284 import std.typecons : Rebindable; 1285 static if (is(T == class) || is(T == interface) || isDynamicArray!T || isAssociativeArray!T) 1286 alias RebindableOrUnqual = Rebindable!T; 1287 else 1288 alias RebindableOrUnqual = Unqual!T; 1289 } 1290 1291 /** 1292 Iterates the passed range and selects the extreme element with `less`. 1293 If the extreme element occurs multiple time, the first occurrence will be 1294 returned. 1295 1296 Params: 1297 map = custom accessor for the comparison key 1298 selector = custom mapping for the extrema selection 1299 seed = custom seed to use as initial element 1300 r = Range from which the extreme value will be selected 1301 1302 Returns: 1303 The extreme value according to `map` and `selector` of the passed-in values. 1304 */ 1305 private auto extremum(alias map, alias selector = "a < b", Range)(Range r) 1306 if (isInputRange!Range && !isInfinite!Range && 1307 is(typeof(unaryFun!map(ElementType!(Range).init)))) 1308 in 1309 { 1310 assert(!r.empty, "r is an empty range"); 1311 } 1312 do 1313 { 1314 alias Element = ElementType!Range; 1315 RebindableOrUnqual!Element seed = r.front; 1316 r.popFront(); 1317 return extremum!(map, selector)(r, seed); 1318 } 1319 1320 private auto extremum(alias map, alias selector = "a < b", Range, 1321 RangeElementType = ElementType!Range) 1322 (Range r, RangeElementType seedElement) 1323 if (isInputRange!Range && !isInfinite!Range && 1324 !is(CommonType!(ElementType!Range, RangeElementType) == void) && 1325 is(typeof(unaryFun!map(ElementType!(Range).init)))) 1326 { 1327 alias mapFun = unaryFun!map; 1328 alias selectorFun = binaryFun!selector; 1329 1330 alias Element = ElementType!Range; 1331 alias CommonElement = CommonType!(Element, RangeElementType); 1332 RebindableOrUnqual!CommonElement extremeElement = seedElement; 1333 1334 1335 // if we only have one statement in the loop, it can be optimized a lot better 1336 static if (__traits(isSame, map, a => a)) 1337 { 1338 1339 // direct access via a random access range is faster 1340 static if (isRandomAccessRange!Range) 1341 { 1342 foreach (const i; 0 .. r.length) 1343 { 1344 if (selectorFun(r[i], extremeElement)) 1345 { 1346 extremeElement = r[i]; 1347 } 1348 } 1349 } 1350 else 1351 { 1352 while (!r.empty) 1353 { 1354 if (selectorFun(r.front, extremeElement)) 1355 { 1356 extremeElement = r.front; 1357 } 1358 r.popFront(); 1359 } 1360 } 1361 } 1362 else 1363 { 1364 alias MapType = Unqual!(typeof(mapFun(CommonElement.init))); 1365 MapType extremeElementMapped = mapFun(extremeElement); 1366 1367 // direct access via a random access range is faster 1368 static if (isRandomAccessRange!Range) 1369 { 1370 foreach (const i; 0 .. r.length) 1371 { 1372 MapType mapElement = mapFun(r[i]); 1373 if (selectorFun(mapElement, extremeElementMapped)) 1374 { 1375 extremeElement = r[i]; 1376 extremeElementMapped = mapElement; 1377 } 1378 } 1379 } 1380 else 1381 { 1382 while (!r.empty) 1383 { 1384 MapType mapElement = mapFun(r.front); 1385 if (selectorFun(mapElement, extremeElementMapped)) 1386 { 1387 extremeElement = r.front; 1388 extremeElementMapped = mapElement; 1389 } 1390 r.popFront(); 1391 } 1392 } 1393 } 1394 return extremeElement; 1395 } 1396 1397 private auto extremum(alias selector = "a < b", Range)(Range r) 1398 if (isInputRange!Range && !isInfinite!Range && 1399 !is(typeof(unaryFun!selector(ElementType!(Range).init)))) 1400 { 1401 return extremum!(a => a, selector)(r); 1402 } 1403 1404 // if we only have one statement in the loop it can be optimized a lot better 1405 private auto extremum(alias selector = "a < b", Range, 1406 RangeElementType = ElementType!Range) 1407 (Range r, RangeElementType seedElement) 1408 if (isInputRange!Range && !isInfinite!Range && 1409 !is(CommonType!(ElementType!Range, RangeElementType) == void) && 1410 !is(typeof(unaryFun!selector(ElementType!(Range).init)))) 1411 { 1412 return extremum!(a => a, selector)(r, seedElement); 1413 } 1414 1415 @safe pure unittest 1416 { 1417 // allows a custom map to select the extremum 1418 assert([[0, 4], [1, 2]].extremum!"a[0]" == [0, 4]); 1419 assert([[0, 4], [1, 2]].extremum!"a[1]" == [1, 2]); 1420 1421 // allows a custom selector for comparison 1422 assert([[0, 4], [1, 2]].extremum!("a[0]", "a > b") == [1, 2]); 1423 assert([[0, 4], [1, 2]].extremum!("a[1]", "a > b") == [0, 4]); 1424 1425 // use a custom comparator 1426 import std.math : cmp; 1427 assert([-2., 0, 5].extremum!cmp == 5.0); 1428 assert([-2., 0, 2].extremum!`cmp(a, b) < 0` == -2.0); 1429 1430 // combine with map 1431 import std.range : enumerate; 1432 assert([-3., 0, 5].enumerate.extremum!(`a.value`, cmp) == tuple(2, 5.0)); 1433 assert([-2., 0, 2].enumerate.extremum!(`a.value`, `cmp(a, b) < 0`) == tuple(0, -2.0)); 1434 1435 // seed with a custom value 1436 int[] arr; 1437 assert(arr.extremum(1) == 1); 1438 } 1439 1440 @safe pure nothrow unittest 1441 { 1442 // 2d seeds 1443 int[][] arr2d; 1444 assert(arr2d.extremum([1]) == [1]); 1445 1446 // allow seeds of different types (implicit casting) 1447 assert(extremum([2, 3, 4], 1.5) == 1.5); 1448 } 1449 1450 @safe pure unittest 1451 { 1452 import std.range : enumerate, iota; 1453 1454 // forward ranges 1455 assert(iota(1, 5).extremum() == 1); 1456 assert(iota(2, 5).enumerate.extremum!"a.value" == tuple(0, 2)); 1457 1458 // should work with const 1459 const(int)[] immArr = [2, 1, 3]; 1460 assert(immArr.extremum == 1); 1461 1462 // should work with immutable 1463 immutable(int)[] immArr2 = [2, 1, 3]; 1464 assert(immArr2.extremum == 1); 1465 1466 // with strings 1467 assert(["b", "a", "c"].extremum == "a"); 1468 1469 // with all dummy ranges 1470 import std.internal.test.dummyrange; 1471 foreach (DummyType; AllDummyRanges) 1472 { 1473 DummyType d; 1474 assert(d.extremum == 1); 1475 assert(d.extremum!(a => a) == 1); 1476 assert(d.extremum!`a > b` == 10); 1477 assert(d.extremum!(a => a, `a > b`) == 10); 1478 } 1479 } 1480 1481 @nogc @safe nothrow pure unittest 1482 { 1483 static immutable arr = [7, 3, 4, 2, 1, 8]; 1484 assert(arr.extremum == 1); 1485 1486 static immutable arr2d = [[1, 9], [3, 1], [4, 2]]; 1487 assert(arr2d.extremum!"a[1]" == arr2d[1]); 1488 } 1489 1490 // https://issues.dlang.org/show_bug.cgi?id=17982 1491 @safe unittest 1492 { 1493 class B 1494 { 1495 int val; 1496 this(int val){ this.val = val; } 1497 } 1498 1499 const(B) doStuff(const(B)[] v) 1500 { 1501 return v.extremum!"a.val"; 1502 } 1503 assert(doStuff([new B(1), new B(0), new B(2)]).val == 0); 1504 1505 const(B)[] arr = [new B(0), new B(1)]; 1506 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824 1507 assert(arr.extremum!"a.val".val == 0); 1508 } 1509 1510 // find 1511 /** 1512 Finds an individual element in an $(REF_ALTTEXT input range, isInputRange, std,range,primitives). 1513 Elements of `haystack` are compared with `needle` by using predicate 1514 `pred` with `pred(haystack.front, needle)`. 1515 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`. 1516 1517 The predicate is passed to $(REF binaryFun, std, functional), and can either accept a 1518 string, or any callable that can be executed via `pred(element, element)`. 1519 1520 To _find the last occurrence of `needle` in a 1521 $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives) `haystack`, 1522 call `find(retro(haystack), needle)`. See $(REF retro, std,range). 1523 1524 If no `needle` is provided, `pred(haystack.front)` will be evaluated on each 1525 element of the input range. 1526 1527 If `input` is a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives), 1528 `needle` can be a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) too. 1529 In this case `startsWith!pred(haystack, needle)` is evaluated on each evaluation. 1530 1531 Note: 1532 `find` behaves similar to `dropWhile` in other languages. 1533 1534 Complexity: 1535 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`. 1536 There are specializations that improve performance by taking 1537 advantage of $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives) 1538 or $(REF_ALTTEXT random access, isRandomAccess, std,range,primitives) 1539 ranges (where possible). 1540 1541 Params: 1542 1543 pred = The predicate for comparing each element with the needle, defaulting to equality `"a == b"`. 1544 The negated predicate `"a != b"` can be used to search instead for the first 1545 element $(I not) matching the needle. 1546 1547 haystack = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 1548 searched in. 1549 1550 needle = The element searched for. 1551 1552 Returns: 1553 1554 `haystack` advanced such that the front element is the one searched for; 1555 that is, until `binaryFun!pred(haystack.front, needle)` is `true`. If no 1556 such position exists, returns an empty `haystack`. 1557 1558 See_ALso: $(LREF findAdjacent), $(LREF findAmong), $(LREF findSkip), $(LREF findSplit), $(LREF startsWith) 1559 */ 1560 InputRange find(alias pred = "a == b", InputRange, Element)(InputRange haystack, scope Element needle) 1561 if (isInputRange!InputRange && 1562 is (typeof(binaryFun!pred(haystack.front, needle)) : bool) && 1563 !is (typeof(binaryFun!pred(haystack.front, needle.front)) : bool)) 1564 { 1565 alias R = InputRange; 1566 alias E = Element; 1567 alias predFun = binaryFun!pred; 1568 static if (is(typeof(pred == "a == b"))) 1569 enum isDefaultPred = pred == "a == b"; 1570 else 1571 enum isDefaultPred = false; 1572 enum isIntegralNeedle = isSomeChar!E || isIntegral!E || isBoolean!E; 1573 1574 alias EType = ElementType!R; 1575 1576 // If the haystack is a SortedRange we can use binary search to find the needle. 1577 // Works only for the default find predicate and any SortedRange predicate. 1578 // https://issues.dlang.org/show_bug.cgi?id=8829 1579 import std.range : SortedRange; 1580 static if (is(InputRange : SortedRange!TT, TT) && isDefaultPred) 1581 { 1582 auto lb = haystack.lowerBound(needle); 1583 if (lb.length == haystack.length || haystack[lb.length] != needle) 1584 return haystack[$ .. $]; 1585 1586 return haystack[lb.length .. $]; 1587 } 1588 else static if (isNarrowString!R) 1589 { 1590 alias EEType = ElementEncodingType!R; 1591 alias UEEType = Unqual!EEType; 1592 1593 //These are two special cases which can search without decoding the UTF stream. 1594 static if (isDefaultPred && isIntegralNeedle) 1595 { 1596 import std.utf : canSearchInCodeUnits; 1597 1598 //This special case deals with UTF8 search, when the needle 1599 //is represented by a single code point. 1600 //Note: "needle <= 0x7F" properly handles sign via unsigned promotion 1601 static if (is(UEEType == char)) 1602 { 1603 if (!__ctfe && canSearchInCodeUnits!char(needle)) 1604 { 1605 static R trustedMemchr(ref R haystack, ref E needle) @trusted nothrow pure 1606 { 1607 import core.stdc..string : memchr; 1608 auto ptr = memchr(haystack.ptr, needle, haystack.length); 1609 return ptr ? 1610 haystack[cast(char*) ptr - haystack.ptr .. $] : 1611 haystack[$ .. $]; 1612 } 1613 return trustedMemchr(haystack, needle); 1614 } 1615 } 1616 1617 //Ditto, but for UTF16 1618 static if (is(UEEType == wchar)) 1619 { 1620 if (canSearchInCodeUnits!wchar(needle)) 1621 { 1622 foreach (i, ref EEType e; haystack) 1623 { 1624 if (e == needle) 1625 return haystack[i .. $]; 1626 } 1627 return haystack[$ .. $]; 1628 } 1629 } 1630 } 1631 1632 //Previous conditional optimizations did not succeed. Fallback to 1633 //unconditional implementations 1634 static if (isDefaultPred) 1635 { 1636 import std.utf : encode; 1637 1638 //In case of default pred, it is faster to do string/string search. 1639 UEEType[is(UEEType == char) ? 4 : 2] buf; 1640 1641 size_t len = encode(buf, needle); 1642 return find(haystack, buf[0 .. len]); 1643 } 1644 else 1645 { 1646 import std.utf : decode; 1647 1648 //Explicit pred: we must test each character by the book. 1649 //We choose a manual decoding approach, because it is faster than 1650 //the built-in foreach, or doing a front/popFront for-loop. 1651 immutable len = haystack.length; 1652 size_t i = 0, next = 0; 1653 while (next < len) 1654 { 1655 if (predFun(decode(haystack, next), needle)) 1656 return haystack[i .. $]; 1657 i = next; 1658 } 1659 return haystack[$ .. $]; 1660 } 1661 } 1662 else static if (isArray!R) 1663 { 1664 // https://issues.dlang.org/show_bug.cgi?id=10403 optimization 1665 static if (isDefaultPred && isIntegral!EType && EType.sizeof == 1 && isIntegralNeedle) 1666 { 1667 import std.algorithm.comparison : max, min; 1668 1669 R findHelper(ref R haystack, ref E needle) @trusted nothrow pure 1670 { 1671 import core.stdc..string : memchr; 1672 1673 EType* ptr = null; 1674 //Note: we use "min/max" to handle sign mismatch. 1675 if (min(EType.min, needle) == EType.min && 1676 max(EType.max, needle) == EType.max) 1677 { 1678 ptr = cast(EType*) memchr(haystack.ptr, needle, 1679 haystack.length); 1680 } 1681 1682 return ptr ? 1683 haystack[ptr - haystack.ptr .. $] : 1684 haystack[$ .. $]; 1685 } 1686 1687 if (!__ctfe) 1688 return findHelper(haystack, needle); 1689 } 1690 1691 //Default implementation. 1692 foreach (i, ref e; haystack) 1693 if (predFun(e, needle)) 1694 return haystack[i .. $]; 1695 return haystack[$ .. $]; 1696 } 1697 else 1698 { 1699 //Everything else. Walk. 1700 for ( ; !haystack.empty; haystack.popFront() ) 1701 { 1702 if (predFun(haystack.front, needle)) 1703 break; 1704 } 1705 return haystack; 1706 } 1707 } 1708 1709 /// 1710 @safe unittest 1711 { 1712 import std.range.primitives; 1713 1714 auto arr = [1, 2, 4, 4, 4, 4, 5, 6, 9]; 1715 assert(arr.find(4) == [4, 4, 4, 4, 5, 6, 9]); 1716 assert(arr.find(1) == arr); 1717 assert(arr.find(9) == [9]); 1718 assert(arr.find!((a, b) => a > b)(4) == [5, 6, 9]); 1719 assert(arr.find!((a, b) => a < b)(4) == arr); 1720 assert(arr.find(0).empty); 1721 assert(arr.find(10).empty); 1722 assert(arr.find(8).empty); 1723 1724 assert(find("hello, world", ',') == ", world"); 1725 } 1726 1727 /// Case-insensitive find of a string 1728 @safe unittest 1729 { 1730 import std.range.primitives; 1731 import std.uni : toLower; 1732 1733 string[] s = ["Hello", "world", "!"]; 1734 assert(s.find!((a, b) => toLower(a) == b)("hello") == s); 1735 } 1736 1737 @safe unittest 1738 { 1739 import std.algorithm.comparison : equal; 1740 import std.container : SList; 1741 1742 auto lst = SList!int(1, 2, 5, 7, 3); 1743 assert(lst.front == 1); 1744 auto r = find(lst[], 5); 1745 assert(equal(r, SList!int(5, 7, 3)[])); 1746 assert(find([1, 2, 3, 5], 4).empty); 1747 assert(equal(find!"a > b"("hello", 'k'), "llo")); 1748 } 1749 1750 @safe pure nothrow unittest 1751 { 1752 assert(!find ([1, 2, 3], 2).empty); 1753 assert(!find!((a,b)=>a == b)([1, 2, 3], 2).empty); 1754 assert(!find ([1, 2, 3], 2).empty); 1755 assert(!find!((a,b)=>a == b)([1, 2, 3], 2).empty); 1756 } 1757 1758 @safe pure unittest 1759 { 1760 import std.meta : AliasSeq; 1761 static foreach (R; AliasSeq!(string, wstring, dstring)) 1762 { 1763 static foreach (E; AliasSeq!(char, wchar, dchar)) 1764 { 1765 assert(find ("hello world", 'w') == "world"); 1766 assert(find!((a,b)=>a == b)("hello world", 'w') == "world"); 1767 assert(find ("日c語", 'c') == "c語"); 1768 assert(find!((a,b)=>a == b)("日c語", 'c') == "c語"); 1769 assert(find ("0123456789", 'A').empty); 1770 static if (E.sizeof >= 2) 1771 { 1772 assert(find ("日本語", '本') == "本語"); 1773 assert(find!((a,b)=>a == b)("日本語", '本') == "本語"); 1774 } 1775 } 1776 } 1777 } 1778 1779 @safe unittest 1780 { 1781 //CTFE 1782 static assert(find("abc", 'b') == "bc"); 1783 static assert(find("日b語", 'b') == "b語"); 1784 static assert(find("日本語", '本') == "本語"); 1785 static assert(find([1, 2, 3], 2) == [2, 3]); 1786 1787 static assert(find ([1, 2, 3], 2)); 1788 static assert(find!((a,b)=>a == b)([1, 2, 3], 2)); 1789 static assert(find ([1, 2, 3], 2)); 1790 static assert(find!((a,b)=>a == b)([1, 2, 3], 2)); 1791 } 1792 1793 @safe unittest 1794 { 1795 import std.exception : assertCTFEable; 1796 import std.meta : AliasSeq; 1797 1798 void dg() @safe pure nothrow 1799 { 1800 byte[] sarr = [1, 2, 3, 4]; 1801 ubyte[] uarr = [1, 2, 3, 4]; 1802 static foreach (arr; AliasSeq!(sarr, uarr)) 1803 { 1804 static foreach (T; AliasSeq!(byte, ubyte, int, uint)) 1805 { 1806 assert(find(arr, cast(T) 3) == arr[2 .. $]); 1807 assert(find(arr, cast(T) 9) == arr[$ .. $]); 1808 } 1809 assert(find(arr, 256) == arr[$ .. $]); 1810 } 1811 } 1812 dg(); 1813 assertCTFEable!dg; 1814 } 1815 1816 // https://issues.dlang.org/show_bug.cgi?id=11603 1817 @safe unittest 1818 { 1819 enum Foo : ubyte { A } 1820 assert([Foo.A].find(Foo.A).empty == false); 1821 1822 ubyte x = 0; 1823 assert([x].find(x).empty == false); 1824 } 1825 1826 /// ditto 1827 InputRange find(alias pred, InputRange)(InputRange haystack) 1828 if (isInputRange!InputRange) 1829 { 1830 alias R = InputRange; 1831 alias predFun = unaryFun!pred; 1832 static if (isNarrowString!R) 1833 { 1834 import std.utf : decode; 1835 1836 immutable len = haystack.length; 1837 size_t i = 0, next = 0; 1838 while (next < len) 1839 { 1840 if (predFun(decode(haystack, next))) 1841 return haystack[i .. $]; 1842 i = next; 1843 } 1844 return haystack[$ .. $]; 1845 } 1846 else 1847 { 1848 //standard range 1849 for ( ; !haystack.empty; haystack.popFront() ) 1850 { 1851 if (predFun(haystack.front)) 1852 break; 1853 } 1854 return haystack; 1855 } 1856 } 1857 1858 /// 1859 @safe unittest 1860 { 1861 auto arr = [ 1, 2, 3, 4, 1 ]; 1862 assert(find!("a > 2")(arr) == [ 3, 4, 1 ]); 1863 1864 // with predicate alias 1865 bool pred(int x) { return x + 1 > 1.5; } 1866 assert(find!(pred)(arr) == arr); 1867 } 1868 1869 @safe pure unittest 1870 { 1871 int[] r = [ 1, 2, 3 ]; 1872 assert(find!(a=>a > 2)(r) == [3]); 1873 bool pred(int x) { return x + 1 > 1.5; } 1874 assert(find!(pred)(r) == r); 1875 1876 assert(find!(a=>a > 'v')("hello world") == "world"); 1877 assert(find!(a=>a%4 == 0)("日本語") == "本語"); 1878 } 1879 1880 /// ditto 1881 R1 find(alias pred = "a == b", R1, R2)(R1 haystack, scope R2 needle) 1882 if (isForwardRange!R1 && isForwardRange!R2 1883 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool)) 1884 { 1885 static if (!isRandomAccessRange!R1) 1886 { 1887 static if (is(typeof(pred == "a == b")) && pred == "a == b" && isSomeString!R1 && isSomeString!R2 1888 && haystack[0].sizeof == needle[0].sizeof) 1889 { 1890 // return cast(R1) find(representation(haystack), representation(needle)); 1891 // Specialization for simple string search 1892 alias Representation = 1893 Select!(haystack[0].sizeof == 1, ubyte[], 1894 Select!(haystack[0].sizeof == 2, ushort[], uint[])); 1895 // Will use the array specialization 1896 static TO force(TO, T)(inout T r) @trusted { return cast(TO) r; } 1897 return force!R1(.find!(pred, Representation, Representation) 1898 (force!Representation(haystack), force!Representation(needle))); 1899 } 1900 else 1901 { 1902 return simpleMindedFind!pred(haystack, needle); 1903 } 1904 } 1905 else static if (!isBidirectionalRange!R2 || !hasSlicing!R1) 1906 { 1907 static if (!is(ElementType!R1 == ElementType!R2)) 1908 { 1909 return simpleMindedFind!pred(haystack, needle); 1910 } 1911 else 1912 { 1913 // Prepare the search with needle's first element 1914 if (needle.empty) 1915 return haystack; 1916 1917 haystack = .find!pred(haystack, needle.front); 1918 1919 static if (hasLength!R1 && hasLength!R2 && is(typeof(takeNone(haystack)) == R1)) 1920 { 1921 if (needle.length > haystack.length) 1922 return takeNone(haystack); 1923 } 1924 else 1925 { 1926 if (haystack.empty) 1927 return haystack; 1928 } 1929 1930 needle.popFront(); 1931 size_t matchLen = 1; 1932 1933 // Loop invariant: haystack[0 .. matchLen] matches everything in 1934 // the initial needle that was popped out of needle. 1935 for (;;) 1936 { 1937 // Extend matchLength as much as possible 1938 for (;;) 1939 { 1940 import std.range : takeNone; 1941 1942 if (needle.empty || haystack.empty) 1943 return haystack; 1944 1945 static if (hasLength!R1 && is(typeof(takeNone(haystack)) == R1)) 1946 { 1947 if (matchLen == haystack.length) 1948 return takeNone(haystack); 1949 } 1950 1951 if (!binaryFun!pred(haystack[matchLen], needle.front)) 1952 break; 1953 1954 ++matchLen; 1955 needle.popFront(); 1956 } 1957 1958 auto bestMatch = haystack[0 .. matchLen]; 1959 haystack.popFront(); 1960 haystack = .find!pred(haystack, bestMatch); 1961 } 1962 } 1963 } 1964 else // static if (hasSlicing!R1 && isBidirectionalRange!R2) 1965 { 1966 if (needle.empty) return haystack; 1967 1968 static if (hasLength!R2) 1969 { 1970 immutable needleLength = needle.length; 1971 } 1972 else 1973 { 1974 immutable needleLength = walkLength(needle.save); 1975 } 1976 if (needleLength > haystack.length) 1977 { 1978 return haystack[haystack.length .. haystack.length]; 1979 } 1980 // Optimization in case the ranges are both SortedRanges. 1981 // Binary search can be used to find the first occurence 1982 // of the first element of the needle in haystack. 1983 // When it is found O(walklength(needle)) steps are performed. 1984 // https://issues.dlang.org/show_bug.cgi?id=8829 enhancement 1985 import std.algorithm.comparison : mismatch; 1986 import std.range : SortedRange; 1987 static if (is(R1 == R2) 1988 && is(R1 : SortedRange!TT, TT) 1989 && pred == "a == b") 1990 { 1991 auto needleFirstElem = needle[0]; 1992 auto partitions = haystack.trisect(needleFirstElem); 1993 auto firstElemLen = partitions[1].length; 1994 size_t count = 0; 1995 1996 if (firstElemLen == 0) 1997 return haystack[$ .. $]; 1998 1999 while (needle.front() == needleFirstElem) 2000 { 2001 needle.popFront(); 2002 ++count; 2003 2004 if (count > firstElemLen) 2005 return haystack[$ .. $]; 2006 } 2007 2008 auto m = mismatch(partitions[2], needle); 2009 2010 if (m[1].empty) 2011 return haystack[partitions[0].length + partitions[1].length - count .. $]; 2012 } 2013 else static if (isRandomAccessRange!R2) 2014 { 2015 immutable lastIndex = needleLength - 1; 2016 auto last = needle[lastIndex]; 2017 size_t j = lastIndex, skip = 0; 2018 for (; j < haystack.length;) 2019 { 2020 if (!binaryFun!pred(haystack[j], last)) 2021 { 2022 ++j; 2023 continue; 2024 } 2025 immutable k = j - lastIndex; 2026 // last elements match 2027 for (size_t i = 0;; ++i) 2028 { 2029 if (i == lastIndex) 2030 return haystack[k .. haystack.length]; 2031 if (!binaryFun!pred(haystack[k + i], needle[i])) 2032 break; 2033 } 2034 if (skip == 0) 2035 { 2036 skip = 1; 2037 while (skip < needleLength && needle[needleLength - 1 - skip] != needle[needleLength - 1]) 2038 { 2039 ++skip; 2040 } 2041 } 2042 j += skip; 2043 } 2044 } 2045 else 2046 { 2047 // @@@BUG@@@ 2048 // auto needleBack = moveBack(needle); 2049 // Stage 1: find the step 2050 size_t step = 1; 2051 auto needleBack = needle.back; 2052 needle.popBack(); 2053 for (auto i = needle.save; !i.empty && i.back != needleBack; 2054 i.popBack(), ++step) 2055 { 2056 } 2057 // Stage 2: linear find 2058 size_t scout = needleLength - 1; 2059 for (;;) 2060 { 2061 if (scout >= haystack.length) 2062 break; 2063 if (!binaryFun!pred(haystack[scout], needleBack)) 2064 { 2065 ++scout; 2066 continue; 2067 } 2068 // Found a match with the last element in the needle 2069 auto cand = haystack[scout + 1 - needleLength .. haystack.length]; 2070 if (startsWith!pred(cand, needle)) 2071 { 2072 // found 2073 return cand; 2074 } 2075 scout += step; 2076 } 2077 } 2078 return haystack[haystack.length .. haystack.length]; 2079 } 2080 } 2081 2082 /// 2083 @safe unittest 2084 { 2085 import std.container : SList; 2086 import std.range.primitives : empty; 2087 import std.typecons : Tuple; 2088 2089 assert(find("hello, world", "World").empty); 2090 assert(find("hello, world", "wo") == "world"); 2091 assert([1, 2, 3, 4].find(SList!int(2, 3)[]) == [2, 3, 4]); 2092 alias C = Tuple!(int, "x", int, "y"); 2093 auto a = [C(1,0), C(2,0), C(3,1), C(4,0)]; 2094 assert(a.find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]); 2095 assert(a[1 .. $].find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]); 2096 } 2097 2098 @safe unittest 2099 { 2100 import std.container : SList; 2101 alias C = Tuple!(int, "x", int, "y"); 2102 assert([C(1,0), C(2,0), C(3,1), C(4,0)].find!"a.x == b"(SList!int(2, 3)[]) == [C(2,0), C(3,1), C(4,0)]); 2103 } 2104 2105 // https://issues.dlang.org/show_bug.cgi?id=12470 2106 @safe unittest 2107 { 2108 import std.array : replace; 2109 inout(char)[] sanitize(inout(char)[] p) 2110 { 2111 return p.replace("\0", " "); 2112 } 2113 assert(sanitize("O\x00o") == "O o"); 2114 } 2115 2116 @safe unittest 2117 { 2118 import std.algorithm.comparison : equal; 2119 import std.container : SList; 2120 2121 auto lst = SList!int(1, 2, 5, 7, 3); 2122 static assert(isForwardRange!(int[])); 2123 static assert(isForwardRange!(typeof(lst[]))); 2124 auto r = find(lst[], [2, 5]); 2125 assert(equal(r, SList!int(2, 5, 7, 3)[])); 2126 } 2127 2128 @safe unittest 2129 { 2130 import std.range : assumeSorted; 2131 2132 auto r1 = assumeSorted([1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 8, 10]); 2133 auto r2 = assumeSorted([3, 3, 4, 5, 6, 7, 8, 8]); 2134 auto r3 = assumeSorted([3, 4, 5, 6, 7, 8]); 2135 auto r4 = assumeSorted([4, 5, 6]); 2136 auto r5 = assumeSorted([12, 13]); 2137 auto r6 = assumeSorted([8, 8, 10, 11]); 2138 auto r7 = assumeSorted([3, 3, 3, 3, 3, 3, 3]); 2139 2140 assert(find(r1, r2) == assumeSorted([3, 3, 4, 5, 6, 7, 8, 8, 8, 10])); 2141 assert(find(r1, r3) == assumeSorted([3, 4, 5, 6, 7, 8, 8, 8, 10])); 2142 assert(find(r1, r4) == assumeSorted([4, 5, 6, 7, 8, 8, 8, 10])); 2143 assert(find(r1, r5).empty()); 2144 assert(find(r1, r6).empty()); 2145 assert(find(r1, r7).empty()); 2146 } 2147 2148 @safe unittest 2149 { 2150 import std.algorithm.comparison : equal; 2151 // @@@BUG@@@ removing static below makes unittest fail 2152 static struct BiRange 2153 { 2154 int[] payload; 2155 @property bool empty() { return payload.empty; } 2156 @property BiRange save() { return this; } 2157 @property ref int front() { return payload[0]; } 2158 @property ref int back() { return payload[$ - 1]; } 2159 void popFront() { return payload.popFront(); } 2160 void popBack() { return payload.popBack(); } 2161 } 2162 auto r = BiRange([1, 2, 3, 10, 11, 4]); 2163 assert(equal(find(r, [10, 11]), [10, 11, 4])); 2164 } 2165 2166 @safe unittest 2167 { 2168 import std.container : SList; 2169 2170 assert(find([ 1, 2, 3 ], SList!int(2, 3)[]) == [ 2, 3 ]); 2171 assert(find([ 1, 2, 1, 2, 3, 3 ], SList!int(2, 3)[]) == [ 2, 3, 3 ]); 2172 } 2173 2174 // https://issues.dlang.org/show_bug.cgi?id=8334 2175 @safe unittest 2176 { 2177 import std.algorithm.iteration : filter; 2178 import std.range; 2179 2180 auto haystack = [1, 2, 3, 4, 1, 9, 12, 42]; 2181 auto needle = [12, 42, 27]; 2182 2183 //different overload of find, but it's the base case. 2184 assert(find(haystack, needle).empty); 2185 2186 assert(find(haystack, takeExactly(filter!"true"(needle), 3)).empty); 2187 assert(find(haystack, filter!"true"(needle)).empty); 2188 } 2189 2190 // https://issues.dlang.org/show_bug.cgi?id=11013 2191 @safe unittest 2192 { 2193 assert(find!"a == a"("abc","abc") == "abc"); 2194 } 2195 2196 // Internally used by some find() overloads above 2197 private R1 simpleMindedFind(alias pred, R1, R2)(R1 haystack, scope R2 needle) 2198 { 2199 enum estimateNeedleLength = hasLength!R1 && !hasLength!R2; 2200 2201 static if (hasLength!R1) 2202 { 2203 static if (!hasLength!R2) 2204 size_t estimatedNeedleLength = 0; 2205 else 2206 immutable size_t estimatedNeedleLength = needle.length; 2207 } 2208 2209 bool haystackTooShort() 2210 { 2211 static if (estimateNeedleLength) 2212 { 2213 return haystack.length < estimatedNeedleLength; 2214 } 2215 else 2216 { 2217 return haystack.empty; 2218 } 2219 } 2220 2221 searching: 2222 for (;; haystack.popFront()) 2223 { 2224 if (haystackTooShort()) 2225 { 2226 // Failed search 2227 static if (hasLength!R1) 2228 { 2229 static if (is(typeof(haystack[haystack.length .. 2230 haystack.length]) : R1)) 2231 return haystack[haystack.length .. haystack.length]; 2232 else 2233 return R1.init; 2234 } 2235 else 2236 { 2237 assert(haystack.empty, "Haystack must be empty by now"); 2238 return haystack; 2239 } 2240 } 2241 static if (estimateNeedleLength) 2242 size_t matchLength = 0; 2243 for (auto h = haystack.save, n = needle.save; 2244 !n.empty; 2245 h.popFront(), n.popFront()) 2246 { 2247 if (h.empty || !binaryFun!pred(h.front, n.front)) 2248 { 2249 // Failed searching n in h 2250 static if (estimateNeedleLength) 2251 { 2252 if (estimatedNeedleLength < matchLength) 2253 estimatedNeedleLength = matchLength; 2254 } 2255 continue searching; 2256 } 2257 static if (estimateNeedleLength) 2258 ++matchLength; 2259 } 2260 break; 2261 } 2262 return haystack; 2263 } 2264 2265 @safe unittest 2266 { 2267 // Test simpleMindedFind for the case where both haystack and needle have 2268 // length. 2269 struct CustomString 2270 { 2271 @safe: 2272 string _impl; 2273 2274 // This is what triggers issue 7992. 2275 @property size_t length() const { return _impl.length; } 2276 @property void length(size_t len) { _impl.length = len; } 2277 2278 // This is for conformance to the forward range API (we deliberately 2279 // make it non-random access so that we will end up in 2280 // simpleMindedFind). 2281 @property bool empty() const { return _impl.empty; } 2282 @property dchar front() const { return _impl.front; } 2283 void popFront() { _impl.popFront(); } 2284 @property CustomString save() { return this; } 2285 } 2286 2287 // If issue 7992 occurs, this will throw an exception from calling 2288 // popFront() on an empty range. 2289 auto r = find(CustomString("a"), CustomString("b")); 2290 assert(r.empty); 2291 } 2292 2293 /** 2294 Finds two or more `needles` into a `haystack`. The predicate $(D 2295 pred) is used throughout to compare elements. By default, elements are 2296 compared for equality. 2297 2298 Params: 2299 2300 pred = The predicate to use for comparing elements. 2301 2302 haystack = The target of the search. Must be an input range. 2303 If any of `needles` is a range with elements comparable to 2304 elements in `haystack`, then `haystack` must be a 2305 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) 2306 such that the search can backtrack. 2307 2308 needles = One or more items to search for. Each of `needles` must 2309 be either comparable to one element in `haystack`, or be itself a 2310 forward range with elements comparable with elements in 2311 `haystack`. 2312 2313 Returns: 2314 2315 A tuple containing `haystack` positioned to match one of the 2316 needles and also the 1-based index of the matching element in $(D 2317 needles) (0 if none of `needles` matched, 1 if `needles[0]` 2318 matched, 2 if `needles[1]` matched...). The first needle to be found 2319 will be the one that matches. If multiple needles are found at the 2320 same spot in the range, then the shortest one is the one which matches 2321 (if multiple needles of the same length are found at the same spot (e.g 2322 `"a"` and `'a'`), then the left-most of them in the argument list 2323 matches). 2324 2325 The relationship between `haystack` and `needles` simply means 2326 that one can e.g. search for individual `int`s or arrays of $(D 2327 int)s in an array of `int`s. In addition, if elements are 2328 individually comparable, searches of heterogeneous types are allowed 2329 as well: a `double[]` can be searched for an `int` or a $(D 2330 short[]), and conversely a `long` can be searched for a `float` 2331 or a `double[]`. This makes for efficient searches without the need 2332 to coerce one side of the comparison into the other's side type. 2333 2334 The complexity of the search is $(BIGOH haystack.length * 2335 max(needles.length)). (For needles that are individual items, length 2336 is considered to be 1.) The strategy used in searching several 2337 subranges at once maximizes cache usage by moving in `haystack` as 2338 few times as possible. 2339 */ 2340 Tuple!(Range, size_t) find(alias pred = "a == b", Range, Ranges...) 2341 (Range haystack, Ranges needles) 2342 if (Ranges.length > 1 && is(typeof(startsWith!pred(haystack, needles)))) 2343 { 2344 for (;; haystack.popFront()) 2345 { 2346 size_t r = startsWith!pred(haystack, needles); 2347 if (r || haystack.empty) 2348 { 2349 return tuple(haystack, r); 2350 } 2351 } 2352 } 2353 2354 /// 2355 @safe unittest 2356 { 2357 import std.typecons : tuple; 2358 int[] a = [ 1, 4, 2, 3 ]; 2359 assert(find(a, 4) == [ 4, 2, 3 ]); 2360 assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]); 2361 assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2)); 2362 // Mixed types allowed if comparable 2363 assert(find(a, 5, [ 1.2, 3.5 ], 2.0) == tuple([ 2, 3 ], 3)); 2364 } 2365 2366 @safe unittest 2367 { 2368 auto s1 = "Mary has a little lamb"; 2369 assert(find(s1, "has a", "has an") == tuple("has a little lamb", 1)); 2370 assert(find(s1, 't', "has a", "has an") == tuple("has a little lamb", 2)); 2371 assert(find(s1, 't', "has a", 'y', "has an") == tuple("y has a little lamb", 3)); 2372 assert(find("abc", "bc").length == 2); 2373 } 2374 2375 @safe unittest 2376 { 2377 import std.algorithm.internal : rndstuff; 2378 import std.meta : AliasSeq; 2379 import std.uni : toUpper; 2380 2381 int[] a = [ 1, 2, 3 ]; 2382 assert(find(a, 5).empty); 2383 assert(find(a, 2) == [2, 3]); 2384 2385 foreach (T; AliasSeq!(int, double)) 2386 { 2387 auto b = rndstuff!(T)(); 2388 if (!b.length) continue; 2389 b[$ / 2] = 200; 2390 b[$ / 4] = 200; 2391 assert(find(b, 200).length == b.length - b.length / 4); 2392 } 2393 2394 // Case-insensitive find of a string 2395 string[] s = [ "Hello", "world", "!" ]; 2396 assert(find!("toUpper(a) == toUpper(b)")(s, "hello").length == 3); 2397 2398 static bool f(string a, string b) { return toUpper(a) == toUpper(b); } 2399 assert(find!(f)(s, "hello").length == 3); 2400 } 2401 2402 @safe unittest 2403 { 2404 import std.algorithm.comparison : equal; 2405 import std.algorithm.internal : rndstuff; 2406 import std.meta : AliasSeq; 2407 import std.range : retro; 2408 2409 int[] a = [ 1, 2, 3, 2, 6 ]; 2410 assert(find(retro(a), 5).empty); 2411 assert(equal(find(retro(a), 2), [ 2, 3, 2, 1 ][])); 2412 2413 foreach (T; AliasSeq!(int, double)) 2414 { 2415 auto b = rndstuff!(T)(); 2416 if (!b.length) continue; 2417 b[$ / 2] = 200; 2418 b[$ / 4] = 200; 2419 assert(find(retro(b), 200).length == 2420 b.length - (b.length - 1) / 2); 2421 } 2422 } 2423 2424 @safe unittest 2425 { 2426 import std.algorithm.comparison : equal; 2427 import std.internal.test.dummyrange; 2428 2429 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; 2430 int[] b = [ 1, 2, 3 ]; 2431 assert(find(a, b) == [ 1, 2, 3, 4, 5 ]); 2432 assert(find(b, a).empty); 2433 2434 foreach (DummyType; AllDummyRanges) 2435 { 2436 DummyType d; 2437 auto findRes = find(d, 5); 2438 assert(equal(findRes, [5,6,7,8,9,10])); 2439 } 2440 } 2441 2442 /** 2443 * Finds `needle` in `haystack` efficiently using the 2444 * $(LINK2 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm, 2445 * Boyer-Moore) method. 2446 * 2447 * Params: 2448 * haystack = A random-access range with length and slicing. 2449 * needle = A $(LREF BoyerMooreFinder). 2450 * 2451 * Returns: 2452 * `haystack` advanced such that `needle` is a prefix of it (if no 2453 * such position exists, returns `haystack` advanced to termination). 2454 */ 2455 RandomAccessRange find(RandomAccessRange, alias pred, InputRange)( 2456 RandomAccessRange haystack, scope BoyerMooreFinder!(pred, InputRange) needle) 2457 { 2458 return needle.beFound(haystack); 2459 } 2460 2461 @safe unittest 2462 { 2463 string h = "/homes/aalexand/d/dmd/bin/../lib/libphobos.a(dmain2.o)"~ 2464 "(.gnu.linkonce.tmain+0x74): In function `main' undefined reference"~ 2465 " to `_Dmain':"; 2466 string[] ns = ["libphobos", "function", " undefined", "`", ":"]; 2467 foreach (n ; ns) 2468 { 2469 auto p = find(h, boyerMooreFinder(n)); 2470 assert(!p.empty); 2471 } 2472 } 2473 2474 /// 2475 @safe unittest 2476 { 2477 import std.range.primitives : empty; 2478 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; 2479 int[] b = [ 1, 2, 3 ]; 2480 2481 assert(find(a, boyerMooreFinder(b)) == [ 1, 2, 3, 4, 5 ]); 2482 assert(find(b, boyerMooreFinder(a)).empty); 2483 } 2484 2485 @safe unittest 2486 { 2487 auto bm = boyerMooreFinder("for"); 2488 auto match = find("Moor", bm); 2489 assert(match.empty); 2490 } 2491 2492 // canFind 2493 /++ 2494 Convenience function. Like find, but only returns whether or not the search 2495 was successful. 2496 2497 See_Also: 2498 $(REF among, std,algorithm,comparison) for checking a value against multiple possibilities. 2499 +/ 2500 template canFind(alias pred="a == b") 2501 { 2502 import std.meta : allSatisfy; 2503 2504 /++ 2505 Returns `true` if and only if any value `v` found in the 2506 input range `range` satisfies the predicate `pred`. 2507 Performs (at most) $(BIGOH haystack.length) evaluations of `pred`. 2508 +/ 2509 bool canFind(Range)(Range haystack) 2510 if (is(typeof(find!pred(haystack)))) 2511 { 2512 return any!pred(haystack); 2513 } 2514 2515 /++ 2516 Returns `true` if and only if `needle` can be found in $(D 2517 range). Performs $(BIGOH haystack.length) evaluations of `pred`. 2518 +/ 2519 bool canFind(Range, Element)(Range haystack, scope Element needle) 2520 if (is(typeof(find!pred(haystack, needle)))) 2521 { 2522 return !find!pred(haystack, needle).empty; 2523 } 2524 2525 /++ 2526 Returns the 1-based index of the first needle found in `haystack`. If no 2527 needle is found, then `0` is returned. 2528 2529 So, if used directly in the condition of an if statement or loop, the result 2530 will be `true` if one of the needles is found and `false` if none are 2531 found, whereas if the result is used elsewhere, it can either be cast to 2532 `bool` for the same effect or used to get which needle was found first 2533 without having to deal with the tuple that `LREF find` returns for the 2534 same operation. 2535 +/ 2536 size_t canFind(Range, Ranges...)(Range haystack, scope Ranges needles) 2537 if (Ranges.length > 1 && 2538 allSatisfy!(isForwardRange, Ranges) && 2539 is(typeof(find!pred(haystack, needles)))) 2540 { 2541 return find!pred(haystack, needles)[1]; 2542 } 2543 } 2544 2545 /// 2546 @safe unittest 2547 { 2548 assert(canFind([0, 1, 2, 3], 2) == true); 2549 assert(canFind([0, 1, 2, 3], [1, 2], [2, 3])); 2550 assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]) == 1); 2551 assert(canFind([0, 1, 2, 3], [1, 7], [2, 3])); 2552 assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]) == 2); 2553 2554 assert(canFind([0, 1, 2, 3], 4) == false); 2555 assert(!canFind([0, 1, 2, 3], [1, 3], [2, 4])); 2556 assert(canFind([0, 1, 2, 3], [1, 3], [2, 4]) == 0); 2557 } 2558 2559 /** 2560 * Example using a custom predicate. 2561 * Note that the needle appears as the second argument of the predicate. 2562 */ 2563 @safe unittest 2564 { 2565 auto words = [ 2566 "apple", 2567 "beeswax", 2568 "cardboard" 2569 ]; 2570 assert(!canFind(words, "bees")); 2571 assert( canFind!((string a, string b) => a.startsWith(b))(words, "bees")); 2572 } 2573 2574 /// Search for mutliple items in an array of items (search for needles in an array of hay stacks) 2575 @safe unittest 2576 { 2577 string s1 = "aaa111aaa"; 2578 string s2 = "aaa222aaa"; 2579 string s3 = "aaa333aaa"; 2580 string s4 = "aaa444aaa"; 2581 const hay = [s1, s2, s3, s4]; 2582 assert(hay.canFind!(e => (e.canFind("111", "222")))); 2583 } 2584 2585 @safe unittest 2586 { 2587 import std.algorithm.internal : rndstuff; 2588 2589 auto a = rndstuff!(int)(); 2590 if (a.length) 2591 { 2592 auto b = a[a.length / 2]; 2593 assert(canFind(a, b)); 2594 } 2595 } 2596 2597 @safe unittest 2598 { 2599 import std.algorithm.comparison : equal; 2600 assert(equal!(canFind!"a < b")([[1, 2, 3], [7, 8, 9]], [2, 8])); 2601 } 2602 2603 // findAdjacent 2604 /** 2605 Advances `r` until it finds the first two adjacent elements `a`, 2606 `b` that satisfy `pred(a, b)`. Performs $(BIGOH r.length) 2607 evaluations of `pred`. 2608 2609 Params: 2610 pred = The predicate to satisfy. 2611 r = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to 2612 search in. 2613 2614 Returns: 2615 `r` advanced to the first occurrence of two adjacent elements that satisfy 2616 the given predicate. If there are no such two elements, returns `r` advanced 2617 until empty. 2618 2619 See_Also: 2620 $(LINK2 http://en.cppreference.com/w/cpp/algorithm/adjacent_find, STL's `adjacent_find`) 2621 */ 2622 Range findAdjacent(alias pred = "a == b", Range)(Range r) 2623 if (isForwardRange!(Range)) 2624 { 2625 auto ahead = r.save; 2626 if (!ahead.empty) 2627 { 2628 for (ahead.popFront(); !ahead.empty; r.popFront(), ahead.popFront()) 2629 { 2630 if (binaryFun!(pred)(r.front, ahead.front)) return r; 2631 } 2632 } 2633 static if (!isInfinite!Range) 2634 return ahead; 2635 } 2636 2637 /// 2638 @safe unittest 2639 { 2640 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ]; 2641 auto r = findAdjacent(a); 2642 assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]); 2643 auto p = findAdjacent!("a < b")(a); 2644 assert(p == [ 7, 8, 9 ]); 2645 2646 } 2647 2648 @safe unittest 2649 { 2650 import std.algorithm.comparison : equal; 2651 import std.internal.test.dummyrange; 2652 import std.range; 2653 2654 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ]; 2655 auto p = findAdjacent(a); 2656 assert(p == [10, 10, 9, 8, 8, 7, 8, 9 ]); 2657 p = findAdjacent!("a < b")(a); 2658 assert(p == [7, 8, 9]); 2659 // empty 2660 a = []; 2661 p = findAdjacent(a); 2662 assert(p.empty); 2663 // not found 2664 a = [ 1, 2, 3, 4, 5 ]; 2665 p = findAdjacent(a); 2666 assert(p.empty); 2667 p = findAdjacent!"a > b"(a); 2668 assert(p.empty); 2669 ReferenceForwardRange!int rfr = new ReferenceForwardRange!int([1, 2, 3, 2, 2, 3]); 2670 assert(equal(findAdjacent(rfr), [2, 2, 3])); 2671 2672 // https://issues.dlang.org/show_bug.cgi?id=9350 2673 assert(!repeat(1).findAdjacent().empty); 2674 } 2675 2676 // findAmong 2677 /** 2678 Searches the given range for an element that matches one of the given choices. 2679 2680 Advances `seq` by calling `seq.popFront` until either 2681 `find!(pred)(choices, seq.front)` is `true`, or `seq` becomes empty. 2682 Performs $(BIGOH seq.length * choices.length) evaluations of `pred`. 2683 2684 Params: 2685 pred = The predicate to use for determining a match. 2686 seq = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to 2687 search. 2688 choices = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) 2689 of possible choices. 2690 2691 Returns: 2692 `seq` advanced to the first matching element, or until empty if there are no 2693 matching elements. 2694 2695 See_Also: $(LREF find), $(REF std,algorithm,comparison,among) 2696 */ 2697 InputRange findAmong(alias pred = "a == b", InputRange, ForwardRange)( 2698 InputRange seq, ForwardRange choices) 2699 if (isInputRange!InputRange && isForwardRange!ForwardRange) 2700 { 2701 for (; !seq.empty && find!pred(choices.save, seq.front).empty; seq.popFront()) 2702 { 2703 } 2704 return seq; 2705 } 2706 2707 /// 2708 @safe unittest 2709 { 2710 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; 2711 int[] b = [ 3, 1, 2 ]; 2712 assert(findAmong(a, b) == a[2 .. $]); 2713 } 2714 2715 @safe unittest 2716 { 2717 int[] a = [ -1, 0, 2, 1, 2, 3, 4, 5 ]; 2718 int[] b = [ 1, 2, 3 ]; 2719 assert(findAmong(a, b) == [2, 1, 2, 3, 4, 5 ]); 2720 assert(findAmong(b, [ 4, 6, 7 ][]).empty); 2721 assert(findAmong!("a == b")(a, b).length == a.length - 2); 2722 assert(findAmong!("a == b")(b, [ 4, 6, 7 ][]).empty); 2723 } 2724 2725 // https://issues.dlang.org/show_bug.cgi?id=19765 2726 @system unittest 2727 { 2728 import std.range.interfaces : inputRangeObject; 2729 auto choices = inputRangeObject("b"); 2730 auto f = "foobar".findAmong(choices); 2731 assert(f == "bar"); 2732 } 2733 2734 // findSkip 2735 /** 2736 * Finds `needle` in `haystack` and positions `haystack` 2737 * right after the first occurrence of `needle`. 2738 * 2739 * If no needle is provided, the `haystack` is advanced as long as `pred` 2740 * evaluates to `true`. 2741 * Similarly, the haystack is positioned so as `pred` evaluates to `false` for 2742 * `haystack.front`. 2743 * 2744 * Params: 2745 * haystack = The 2746 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search 2747 * in. 2748 * needle = The 2749 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search 2750 * for. 2751 * pred = Custom predicate for comparison of haystack and needle 2752 * 2753 * Returns: `true` if the needle was found, in which case `haystack` is 2754 * positioned after the end of the first occurrence of `needle`; otherwise 2755 * `false`, leaving `haystack` untouched. If no needle is provided, it returns 2756 * the number of times `pred(haystack.front)` returned true. 2757 * 2758 * See_Also: $(LREF find) 2759 */ 2760 bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle) 2761 if (isForwardRange!R1 && isForwardRange!R2 2762 && is(typeof(binaryFun!pred(haystack.front, needle.front)))) 2763 { 2764 auto parts = findSplit!pred(haystack, needle); 2765 if (parts[1].empty) return false; 2766 // found 2767 haystack = parts[2]; 2768 return true; 2769 } 2770 2771 /// 2772 @safe unittest 2773 { 2774 import std.range.primitives : empty; 2775 // Needle is found; s is replaced by the substring following the first 2776 // occurrence of the needle. 2777 string s = "abcdef"; 2778 assert(findSkip(s, "cd") && s == "ef"); 2779 2780 // Needle is not found; s is left untouched. 2781 s = "abcdef"; 2782 assert(!findSkip(s, "cxd") && s == "abcdef"); 2783 2784 // If the needle occurs at the end of the range, the range is left empty. 2785 s = "abcdef"; 2786 assert(findSkip(s, "def") && s.empty); 2787 } 2788 2789 // https://issues.dlang.org/show_bug.cgi?id=19020 2790 @safe unittest 2791 { 2792 static struct WrapperRange 2793 { 2794 string _r; 2795 @property auto empty() { return _r.empty(); } 2796 @property auto front() { return _r.front(); } 2797 auto popFront() { return _r.popFront(); } 2798 @property auto save() { return WrapperRange(_r.save); } 2799 } 2800 auto tmp = WrapperRange("there is a bug here: *"); 2801 assert(!tmp.findSkip("*/")); 2802 assert(tmp._r == "there is a bug here: *"); 2803 } 2804 2805 /// ditto 2806 size_t findSkip(alias pred, R1)(ref R1 haystack) 2807 if (isForwardRange!R1 && ifTestable!(typeof(haystack.front), unaryFun!pred)) 2808 { 2809 size_t result; 2810 while (!haystack.empty && unaryFun!pred(haystack.front)) 2811 { 2812 result++; 2813 haystack.popFront; 2814 } 2815 return result; 2816 } 2817 2818 /// 2819 @safe unittest 2820 { 2821 import std.ascii : isWhite; 2822 string s = " abc"; 2823 assert(findSkip!isWhite(s) && s == "abc"); 2824 assert(!findSkip!isWhite(s) && s == "abc"); 2825 2826 s = " "; 2827 assert(findSkip!isWhite(s) == 2); 2828 } 2829 2830 @safe unittest 2831 { 2832 import std.ascii : isWhite; 2833 2834 auto s = " "; 2835 assert(findSkip!isWhite(s) == 2); 2836 } 2837 2838 /** 2839 These functions find the first occurrence of `needle` in `haystack` and then 2840 split `haystack` as follows. 2841 2842 `findSplit` returns a tuple `result` containing $(I three) ranges. `result[0]` 2843 is the portion of `haystack` before `needle`, `result[1]` is the portion of 2844 `haystack` that matches `needle`, and `result[2]` is the portion of `haystack` 2845 after the match. If `needle` was not found, `result[0]` comprehends `haystack` 2846 entirely and `result[1]` and `result[2]` are empty. 2847 2848 `findSplitBefore` returns a tuple `result` containing two ranges. `result[0]` is 2849 the portion of `haystack` before `needle`, and `result[1]` is the balance of 2850 `haystack` starting with the match. If `needle` was not found, `result[0]` 2851 comprehends `haystack` entirely and `result[1]` is empty. 2852 2853 `findSplitAfter` returns a tuple `result` containing two ranges. 2854 `result[0]` is the portion of `haystack` up to and including the 2855 match, and `result[1]` is the balance of `haystack` starting 2856 after the match. If `needle` was not found, `result[0]` is empty 2857 and `result[1]` is `haystack`. 2858 2859 In all cases, the concatenation of the returned ranges spans the 2860 entire `haystack`. 2861 2862 If `haystack` is a random-access range, all three components of the tuple have 2863 the same type as `haystack`. Otherwise, `haystack` must be a 2864 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) and 2865 the type of `result[0]` and `result[1]` is the same as $(REF takeExactly, 2866 std,range). 2867 2868 Params: 2869 pred = Predicate to use for comparing needle against haystack. 2870 haystack = The range to search. 2871 needle = What to look for. 2872 2873 Returns: 2874 2875 A sub-type of `Tuple!()` of the split portions of `haystack` (see above for 2876 details). This sub-type of `Tuple!()` has `opCast` defined for `bool`. This 2877 `opCast` returns `true` when the separating `needle` was found 2878 and `false` otherwise. 2879 2880 See_Also: $(LREF find) 2881 */ 2882 auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 2883 if (isForwardRange!R1 && isForwardRange!R2) 2884 { 2885 static struct Result(S1, S2) if (isForwardRange!S1 && 2886 isForwardRange!S2) 2887 { 2888 this(S1 pre, S1 separator, S2 post) 2889 { 2890 asTuple = typeof(asTuple)(pre, separator, post); 2891 } 2892 void opAssign(typeof(asTuple) rhs) 2893 { 2894 asTuple = rhs; 2895 } 2896 Tuple!(S1, S1, S2) asTuple; 2897 static if (hasConstEmptyMember!(typeof(asTuple[1]))) 2898 { 2899 bool opCast(T : bool)() const 2900 { 2901 return !asTuple[1].empty; 2902 } 2903 } 2904 else 2905 { 2906 bool opCast(T : bool)() 2907 { 2908 return !asTuple[1].empty; 2909 } 2910 } 2911 alias asTuple this; 2912 } 2913 2914 static if (isSomeString!R1 && isSomeString!R2 2915 || (isRandomAccessRange!R1 && hasSlicing!R1 && hasLength!R1 && hasLength!R2)) 2916 { 2917 auto balance = find!pred(haystack, needle); 2918 immutable pos1 = haystack.length - balance.length; 2919 immutable pos2 = balance.empty ? pos1 : pos1 + needle.length; 2920 return Result!(typeof(haystack[0 .. pos1]), 2921 typeof(haystack[pos2 .. haystack.length]))(haystack[0 .. pos1], 2922 haystack[pos1 .. pos2], 2923 haystack[pos2 .. haystack.length]); 2924 } 2925 else 2926 { 2927 import std.range : takeExactly; 2928 auto original = haystack.save; 2929 auto h = haystack.save; 2930 auto n = needle.save; 2931 size_t pos1, pos2; 2932 while (!n.empty && !h.empty) 2933 { 2934 if (binaryFun!pred(h.front, n.front)) 2935 { 2936 h.popFront(); 2937 n.popFront(); 2938 ++pos2; 2939 } 2940 else 2941 { 2942 haystack.popFront(); 2943 n = needle.save; 2944 h = haystack.save; 2945 pos2 = ++pos1; 2946 } 2947 } 2948 if (!n.empty) // incomplete match at the end of haystack 2949 { 2950 pos1 = pos2; 2951 } 2952 return Result!(typeof(takeExactly(original, pos1)), 2953 typeof(h))(takeExactly(original, pos1), 2954 takeExactly(haystack, pos2 - pos1), 2955 h); 2956 } 2957 } 2958 2959 /// Ditto 2960 auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 2961 if (isForwardRange!R1 && isForwardRange!R2) 2962 { 2963 static struct Result(S1, S2) if (isForwardRange!S1 && 2964 isForwardRange!S2) 2965 { 2966 this(S1 pre, S2 post) 2967 { 2968 asTuple = typeof(asTuple)(pre, post); 2969 } 2970 void opAssign(typeof(asTuple) rhs) 2971 { 2972 asTuple = rhs; 2973 } 2974 Tuple!(S1, S2) asTuple; 2975 static if (hasConstEmptyMember!(typeof(asTuple[1]))) 2976 { 2977 bool opCast(T : bool)() const 2978 { 2979 return !asTuple[1].empty; 2980 } 2981 } 2982 else 2983 { 2984 bool opCast(T : bool)() 2985 { 2986 return !asTuple[1].empty; 2987 } 2988 } 2989 alias asTuple this; 2990 } 2991 2992 static if (isSomeString!R1 && isSomeString!R2 2993 || (isRandomAccessRange!R1 && hasLength!R1 && hasSlicing!R1 && hasLength!R2)) 2994 { 2995 auto balance = find!pred(haystack, needle); 2996 immutable pos = haystack.length - balance.length; 2997 return Result!(typeof(haystack[0 .. pos]), 2998 typeof(haystack[pos .. haystack.length]))(haystack[0 .. pos], 2999 haystack[pos .. haystack.length]); 3000 } 3001 else 3002 { 3003 import std.range : takeExactly; 3004 auto original = haystack.save; 3005 auto h = haystack.save; 3006 auto n = needle.save; 3007 size_t pos1, pos2; 3008 while (!n.empty && !h.empty) 3009 { 3010 if (binaryFun!pred(h.front, n.front)) 3011 { 3012 h.popFront(); 3013 n.popFront(); 3014 ++pos2; 3015 } 3016 else 3017 { 3018 haystack.popFront(); 3019 n = needle.save; 3020 h = haystack.save; 3021 pos2 = ++pos1; 3022 } 3023 } 3024 if (!n.empty) // incomplete match at the end of haystack 3025 { 3026 pos1 = pos2; 3027 haystack = h; 3028 } 3029 return Result!(typeof(takeExactly(original, pos1)), 3030 typeof(haystack))(takeExactly(original, pos1), 3031 haystack); 3032 } 3033 } 3034 3035 /// Ditto 3036 auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 3037 if (isForwardRange!R1 && isForwardRange!R2) 3038 { 3039 static struct Result(S1, S2) if (isForwardRange!S1 && 3040 isForwardRange!S2) 3041 { 3042 this(S1 pre, S2 post) 3043 { 3044 asTuple = typeof(asTuple)(pre, post); 3045 } 3046 void opAssign(typeof(asTuple) rhs) 3047 { 3048 asTuple = rhs; 3049 } 3050 Tuple!(S1, S2) asTuple; 3051 static if (hasConstEmptyMember!(typeof(asTuple[1]))) 3052 { 3053 bool opCast(T : bool)() const 3054 { 3055 return !asTuple[0].empty; 3056 } 3057 } 3058 else 3059 { 3060 bool opCast(T : bool)() 3061 { 3062 return !asTuple[0].empty; 3063 } 3064 } 3065 alias asTuple this; 3066 } 3067 3068 static if (isSomeString!R1 && isSomeString!R2 3069 || isRandomAccessRange!R1 && hasLength!R1 && hasSlicing!R1 && hasLength!R2) 3070 { 3071 auto balance = find!pred(haystack, needle); 3072 immutable pos = balance.empty ? 0 : haystack.length - balance.length + needle.length; 3073 return Result!(typeof(haystack[0 .. pos]), 3074 typeof(haystack[pos .. haystack.length]))(haystack[0 .. pos], 3075 haystack[pos .. haystack.length]); 3076 } 3077 else 3078 { 3079 import std.range : takeExactly; 3080 auto original = haystack.save; 3081 auto h = haystack.save; 3082 auto n = needle.save; 3083 size_t pos1, pos2; 3084 while (!n.empty) 3085 { 3086 if (h.empty) 3087 { 3088 // Failed search 3089 return Result!(typeof(takeExactly(original, 0)), 3090 typeof(original))(takeExactly(original, 0), 3091 original); 3092 } 3093 if (binaryFun!pred(h.front, n.front)) 3094 { 3095 h.popFront(); 3096 n.popFront(); 3097 ++pos2; 3098 } 3099 else 3100 { 3101 haystack.popFront(); 3102 n = needle.save; 3103 h = haystack.save; 3104 pos2 = ++pos1; 3105 } 3106 } 3107 return Result!(typeof(takeExactly(original, pos2)), 3108 typeof(h))(takeExactly(original, pos2), 3109 h); 3110 } 3111 } 3112 3113 /// Returning a subtype of $(REF Tuple, std,typecons) enables 3114 /// the following convenient idiom: 3115 @safe pure nothrow unittest 3116 { 3117 // findSplit returns a triplet 3118 if (auto split = "dlang-rocks".findSplit("-")) 3119 { 3120 assert(split[0] == "dlang"); 3121 assert(split[1] == "-"); 3122 assert(split[2] == "rocks"); 3123 } 3124 else assert(0); 3125 3126 // works with const aswell 3127 if (const split = "dlang-rocks".findSplit("-")) 3128 { 3129 assert(split[0] == "dlang"); 3130 assert(split[1] == "-"); 3131 assert(split[2] == "rocks"); 3132 } 3133 else assert(0); 3134 } 3135 3136 /// 3137 @safe pure nothrow unittest 3138 { 3139 import std.range.primitives : empty; 3140 3141 auto a = "Carl Sagan Memorial Station"; 3142 auto r = findSplit(a, "Velikovsky"); 3143 import std.typecons : isTuple; 3144 static assert(isTuple!(typeof(r.asTuple))); 3145 static assert(isTuple!(typeof(r))); 3146 assert(!r); 3147 assert(r[0] == a); 3148 assert(r[1].empty); 3149 assert(r[2].empty); 3150 r = findSplit(a, " "); 3151 assert(r[0] == "Carl"); 3152 assert(r[1] == " "); 3153 assert(r[2] == "Sagan Memorial Station"); 3154 if (const r1 = findSplitBefore(a, "Sagan")) 3155 { 3156 assert(r1); 3157 assert(r1[0] == "Carl "); 3158 assert(r1[1] == "Sagan Memorial Station"); 3159 } 3160 if (const r2 = findSplitAfter(a, "Sagan")) 3161 { 3162 assert(r2); 3163 assert(r2[0] == "Carl Sagan"); 3164 assert(r2[1] == " Memorial Station"); 3165 } 3166 } 3167 3168 /// Use $(REF only, std,range) to find single elements: 3169 @safe pure nothrow unittest 3170 { 3171 import std.range : only; 3172 assert([1, 2, 3, 4].findSplitBefore(only(3))[0] == [1, 2]); 3173 } 3174 3175 @safe pure nothrow unittest 3176 { 3177 import std.range.primitives : empty; 3178 3179 immutable a = [ 1, 2, 3, 4, 5, 6, 7, 8 ]; 3180 auto r = findSplit(a, [9, 1]); 3181 assert(!r); 3182 assert(r[0] == a); 3183 assert(r[1].empty); 3184 assert(r[2].empty); 3185 r = findSplit(a, [3]); 3186 assert(r); 3187 assert(r[0] == a[0 .. 2]); 3188 assert(r[1] == a[2 .. 3]); 3189 assert(r[2] == a[3 .. $]); 3190 3191 { 3192 const r1 = findSplitBefore(a, [9, 1]); 3193 assert(!r1); 3194 assert(r1[0] == a); 3195 assert(r1[1].empty); 3196 } 3197 3198 if (immutable r1 = findSplitBefore(a, [3, 4])) 3199 { 3200 assert(r1); 3201 assert(r1[0] == a[0 .. 2]); 3202 assert(r1[1] == a[2 .. $]); 3203 } 3204 else assert(0); 3205 3206 { 3207 const r2 = findSplitAfter(a, [9, 1]); 3208 assert(!r2); 3209 assert(r2[0].empty); 3210 assert(r2[1] == a); 3211 } 3212 3213 if (immutable r3 = findSplitAfter(a, [3, 4])) 3214 { 3215 assert(r3); 3216 assert(r3[0] == a[0 .. 4]); 3217 assert(r3[1] == a[4 .. $]); 3218 } 3219 else assert(0); 3220 } 3221 3222 @safe pure nothrow unittest 3223 { 3224 import std.algorithm.comparison : equal; 3225 import std.algorithm.iteration : filter; 3226 3227 auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ]; 3228 auto fwd = filter!"a > 0"(a); 3229 auto r = findSplit(fwd, [9, 1]); 3230 assert(!r); 3231 assert(equal(r[0], a)); 3232 assert(r[1].empty); 3233 assert(r[2].empty); 3234 r = findSplit(fwd, [3]); 3235 assert(r); 3236 assert(equal(r[0], a[0 .. 2])); 3237 assert(equal(r[1], a[2 .. 3])); 3238 assert(equal(r[2], a[3 .. $])); 3239 r = findSplit(fwd, [8, 9]); 3240 assert(!r); 3241 assert(equal(r[0], a)); 3242 assert(r[1].empty); 3243 assert(r[2].empty); 3244 3245 // auto variable `r2` cannot be `const` because `fwd.front` is mutable 3246 { 3247 auto r1 = findSplitBefore(fwd, [9, 1]); 3248 assert(!r1); 3249 assert(equal(r1[0], a)); 3250 assert(r1[1].empty); 3251 } 3252 3253 if (auto r1 = findSplitBefore(fwd, [3, 4])) 3254 { 3255 assert(r1); 3256 assert(equal(r1[0], a[0 .. 2])); 3257 assert(equal(r1[1], a[2 .. $])); 3258 } 3259 else assert(0); 3260 3261 { 3262 auto r1 = findSplitBefore(fwd, [8, 9]); 3263 assert(!r1); 3264 assert(equal(r1[0], a)); 3265 assert(r1[1].empty); 3266 } 3267 3268 { 3269 auto r2 = findSplitAfter(fwd, [9, 1]); 3270 assert(!r2); 3271 assert(r2[0].empty); 3272 assert(equal(r2[1], a)); 3273 } 3274 3275 if (auto r2 = findSplitAfter(fwd, [3, 4])) 3276 { 3277 assert(r2); 3278 assert(equal(r2[0], a[0 .. 4])); 3279 assert(equal(r2[1], a[4 .. $])); 3280 } 3281 else assert(0); 3282 3283 { 3284 auto r2 = findSplitAfter(fwd, [8, 9]); 3285 assert(!r2); 3286 assert(r2[0].empty); 3287 assert(equal(r2[1], a)); 3288 } 3289 } 3290 3291 @safe pure nothrow @nogc unittest 3292 { 3293 auto str = "sep,one,sep,two"; 3294 3295 auto split = str.findSplitAfter(","); 3296 assert(split[0] == "sep,"); 3297 3298 split = split[1].findSplitAfter(","); 3299 assert(split[0] == "one,"); 3300 3301 split = split[1].findSplitBefore(","); 3302 assert(split[0] == "sep"); 3303 } 3304 3305 @safe pure nothrow @nogc unittest 3306 { 3307 auto str = "sep,one,sep,two"; 3308 3309 auto split = str.findSplitBefore(",two"); 3310 assert(split[0] == "sep,one,sep"); 3311 assert(split[1] == ",two"); 3312 3313 split = split[0].findSplitBefore(",sep"); 3314 assert(split[0] == "sep,one"); 3315 assert(split[1] == ",sep"); 3316 3317 split = split[0].findSplitAfter(","); 3318 assert(split[0] == "sep,"); 3319 assert(split[1] == "one"); 3320 } 3321 3322 // https://issues.dlang.org/show_bug.cgi?id=11013 3323 @safe pure unittest 3324 { 3325 auto var = "abc"; 3326 auto split = var.findSplitBefore!q{a == a}(var); 3327 assert(split[0] == ""); 3328 assert(split[1] == "abc"); 3329 } 3330 3331 // minCount 3332 /** 3333 3334 Computes the minimum (respectively maximum) of `range` along with its number of 3335 occurrences. Formally, the minimum is a value `x` in `range` such that $(D 3336 pred(a, x)) is `false` for all values `a` in `range`. Conversely, the maximum is 3337 a value `x` in `range` such that `pred(x, a)` is `false` for all values `a` 3338 in `range` (note the swapped arguments to `pred`). 3339 3340 These functions may be used for computing arbitrary extrema by choosing `pred` 3341 appropriately. For corrrect functioning, `pred` must be a strict partial order, 3342 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and 3343 irreflexive (`pred(a, a)` is `false`). The $(LUCKY trichotomy property of 3344 inequality) is not required: these algorithms consider elements `a` and `b` equal 3345 (for the purpose of counting) if `pred` puts them in the same equivalence class, 3346 i.e. `!pred(a, b) && !pred(b, a)`. 3347 3348 Params: 3349 pred = The ordering predicate to use to determine the extremum (minimum 3350 or maximum). 3351 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to count. 3352 3353 Returns: The minimum, respectively maximum element of a range together with the 3354 number it occurs in the range. 3355 3356 Limitations: If at least one of the arguments is NaN, the result is 3357 an unspecified value. See $(REF maxElement, std,algorithm,searching) 3358 for examples on how to cope with NaNs. 3359 3360 Throws: `Exception` if `range.empty`. 3361 3362 See_Also: $(REF min, std,algorithm,comparison), $(LREF minIndex), $(LREF minElement), $(LREF minPos) 3363 */ 3364 Tuple!(ElementType!Range, size_t) 3365 minCount(alias pred = "a < b", Range)(Range range) 3366 if (isInputRange!Range && !isInfinite!Range && 3367 is(typeof(binaryFun!pred(range.front, range.front)))) 3368 { 3369 import std.algorithm.internal : algoFormat; 3370 import std.exception : enforce; 3371 3372 alias T = ElementType!Range; 3373 alias UT = Unqual!T; 3374 alias RetType = Tuple!(T, size_t); 3375 3376 static assert(is(typeof(RetType(range.front, 1))), 3377 algoFormat("Error: Cannot call minCount on a %s, because it is not possible "~ 3378 "to copy the result value (a %s) into a Tuple.", Range.stringof, T.stringof)); 3379 3380 enforce(!range.empty, "Can't count elements from an empty range"); 3381 size_t occurrences = 1; 3382 3383 static if (isForwardRange!Range) 3384 { 3385 Range least = range.save; 3386 for (range.popFront(); !range.empty; range.popFront()) 3387 { 3388 if (binaryFun!pred(least.front, range.front)) 3389 { 3390 assert(!binaryFun!pred(range.front, least.front), 3391 "min/maxPos: predicate must be a strict partial order."); 3392 continue; 3393 } 3394 if (binaryFun!pred(range.front, least.front)) 3395 { 3396 // change the min 3397 least = range.save; 3398 occurrences = 1; 3399 } 3400 else 3401 ++occurrences; 3402 } 3403 return RetType(least.front, occurrences); 3404 } 3405 else static if (isAssignable!(UT, T) || (!hasElaborateAssign!UT && isAssignable!UT)) 3406 { 3407 UT v = UT.init; 3408 static if (isAssignable!(UT, T)) v = range.front; 3409 else v = cast(UT) range.front; 3410 3411 for (range.popFront(); !range.empty; range.popFront()) 3412 { 3413 if (binaryFun!pred(*cast(T*)&v, range.front)) continue; 3414 if (binaryFun!pred(range.front, *cast(T*)&v)) 3415 { 3416 // change the min 3417 static if (isAssignable!(UT, T)) v = range.front; 3418 else v = cast(UT) range.front; //Safe because !hasElaborateAssign!UT 3419 occurrences = 1; 3420 } 3421 else 3422 ++occurrences; 3423 } 3424 return RetType(*cast(T*)&v, occurrences); 3425 } 3426 else static if (hasLvalueElements!Range) 3427 { 3428 import std.algorithm.internal : addressOf; 3429 T* p = addressOf(range.front); 3430 for (range.popFront(); !range.empty; range.popFront()) 3431 { 3432 if (binaryFun!pred(*p, range.front)) continue; 3433 if (binaryFun!pred(range.front, *p)) 3434 { 3435 // change the min 3436 p = addressOf(range.front); 3437 occurrences = 1; 3438 } 3439 else 3440 ++occurrences; 3441 } 3442 return RetType(*p, occurrences); 3443 } 3444 else 3445 static assert(false, 3446 algoFormat("Sorry, can't find the minCount of a %s: Don't know how "~ 3447 "to keep track of the smallest %s element.", Range.stringof, T.stringof)); 3448 } 3449 3450 /// Ditto 3451 Tuple!(ElementType!Range, size_t) 3452 maxCount(alias pred = "a < b", Range)(Range range) 3453 if (isInputRange!Range && !isInfinite!Range && 3454 is(typeof(binaryFun!pred(range.front, range.front)))) 3455 { 3456 return range.minCount!((a, b) => binaryFun!pred(b, a)); 3457 } 3458 3459 /// 3460 @safe unittest 3461 { 3462 import std.conv : text; 3463 import std.typecons : tuple; 3464 3465 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; 3466 // Minimum is 1 and occurs 3 times 3467 assert(a.minCount == tuple(1, 3)); 3468 // Maximum is 4 and occurs 2 times 3469 assert(a.maxCount == tuple(4, 2)); 3470 } 3471 3472 @system unittest 3473 { 3474 import std.conv : text; 3475 import std.exception : assertThrown; 3476 import std.internal.test.dummyrange; 3477 3478 int[][] b = [ [4], [2, 4], [4], [4] ]; 3479 auto c = minCount!("a[0] < b[0]")(b); 3480 assert(c == tuple([2, 4], 1), text(c[0])); 3481 3482 //Test empty range 3483 assertThrown(minCount(b[$..$])); 3484 3485 //test with reference ranges. Test both input and forward. 3486 assert(minCount(new ReferenceInputRange!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2)); 3487 assert(minCount(new ReferenceForwardRange!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2)); 3488 } 3489 3490 @system unittest 3491 { 3492 import std.conv : text; 3493 import std.meta : AliasSeq; 3494 3495 static struct R(T) //input range 3496 { 3497 T[] arr; 3498 alias arr this; 3499 } 3500 3501 immutable a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; 3502 R!(immutable int) b = R!(immutable int)(a); 3503 3504 assert(minCount(a) == tuple(1, 3)); 3505 assert(minCount(b) == tuple(1, 3)); 3506 assert(minCount!((ref immutable int a, ref immutable int b) => (a > b))(a) == tuple(4, 2)); 3507 assert(minCount!((ref immutable int a, ref immutable int b) => (a > b))(b) == tuple(4, 2)); 3508 3509 immutable(int[])[] c = [ [4], [2, 4], [4], [4] ]; 3510 assert(minCount!("a[0] < b[0]")(c) == tuple([2, 4], 1), text(c[0])); 3511 3512 static struct S1 3513 { 3514 int i; 3515 } 3516 alias IS1 = immutable(S1); 3517 static assert( isAssignable!S1); 3518 static assert( isAssignable!(S1, IS1)); 3519 3520 static struct S2 3521 { 3522 int* p; 3523 this(ref immutable int i) immutable {p = &i;} 3524 this(ref int i) {p = &i;} 3525 @property ref inout(int) i() inout {return *p;} 3526 bool opEquals(const S2 other) const {return i == other.i;} 3527 } 3528 alias IS2 = immutable(S2); 3529 static assert( isAssignable!S2); 3530 static assert(!isAssignable!(S2, IS2)); 3531 static assert(!hasElaborateAssign!S2); 3532 3533 static struct S3 3534 { 3535 int i; 3536 void opAssign(ref S3 other) @disable; 3537 } 3538 static assert(!isAssignable!S3); 3539 3540 static foreach (Type; AliasSeq!(S1, IS1, S2, IS2, S3)) 3541 {{ 3542 static if (is(Type == immutable)) alias V = immutable int; 3543 else alias V = int; 3544 V one = 1, two = 2; 3545 auto r1 = [Type(two), Type(one), Type(one)]; 3546 auto r2 = R!Type(r1); 3547 assert(minCount!"a.i < b.i"(r1) == tuple(Type(one), 2)); 3548 assert(minCount!"a.i < b.i"(r2) == tuple(Type(one), 2)); 3549 assert(one == 1 && two == 2); 3550 }} 3551 } 3552 3553 /** 3554 Iterates the passed range and returns the minimal element. 3555 A custom mapping function can be passed to `map`. 3556 In other languages this is sometimes called `argmin`. 3557 3558 Complexity: O(n) 3559 Exactly `n - 1` comparisons are needed. 3560 3561 Params: 3562 map = custom accessor for the comparison key 3563 r = range from which the minimal element will be selected 3564 seed = custom seed to use as initial element 3565 3566 Returns: The minimal element of the passed-in range. 3567 3568 Note: 3569 If at least one of the arguments is NaN, the result is an unspecified value. 3570 3571 If you want to ignore NaNs, you can use $(REF filter, std,algorithm,iteration) 3572 and $(REF isNaN, std,math) to remove them, before applying minElement. 3573 Add a suitable seed, to avoid error messages if all elements are NaNs: 3574 3575 --- 3576 <range>.filter!(a=>!a.isNaN).minElement(<seed>); 3577 --- 3578 3579 If you want to get NaN as a result if a NaN is present in the range, 3580 you can use $(REF fold, std.algorithm,iteration) and $(REF isNaN, std,math): 3581 3582 --- 3583 <range>.fold!((a,b)=>a.isNaN || b.isNaN ? real.nan : a < b ? a : b); 3584 --- 3585 3586 See_Also: 3587 3588 $(LREF maxElement), $(REF min, std,algorithm,comparison), $(LREF minCount), 3589 $(LREF minIndex), $(LREF minPos) 3590 */ 3591 auto minElement(alias map = (a => a), Range)(Range r) 3592 if (isInputRange!Range && !isInfinite!Range) 3593 { 3594 return extremum!map(r); 3595 } 3596 3597 /// ditto 3598 auto minElement(alias map = (a => a), Range, RangeElementType = ElementType!Range) 3599 (Range r, RangeElementType seed) 3600 if (isInputRange!Range && !isInfinite!Range && 3601 !is(CommonType!(ElementType!Range, RangeElementType) == void)) 3602 { 3603 return extremum!map(r, seed); 3604 } 3605 3606 /// 3607 @safe pure unittest 3608 { 3609 import std.range : enumerate; 3610 import std.typecons : tuple; 3611 3612 assert([2, 7, 1, 3].minElement == 1); 3613 3614 // allows to get the index of an element too 3615 assert([5, 3, 7, 9].enumerate.minElement!"a.value" == tuple(1, 3)); 3616 3617 // any custom accessor can be passed 3618 assert([[0, 4], [1, 2]].minElement!"a[1]" == [1, 2]); 3619 3620 // can be seeded 3621 int[] arr; 3622 assert(arr.minElement(1) == 1); 3623 } 3624 3625 @safe pure unittest 3626 { 3627 import std.range : enumerate, iota; 3628 // supports mapping 3629 assert([3, 4, 5, 1, 2].enumerate.minElement!"a.value" == tuple(3, 1)); 3630 assert([5, 2, 4].enumerate.minElement!"a.value" == tuple(1, 2)); 3631 3632 // forward ranges 3633 assert(iota(1, 5).minElement() == 1); 3634 assert(iota(2, 5).enumerate.minElement!"a.value" == tuple(0, 2)); 3635 3636 // should work with const 3637 const(int)[] immArr = [2, 1, 3]; 3638 assert(immArr.minElement == 1); 3639 3640 // should work with immutable 3641 immutable(int)[] immArr2 = [2, 1, 3]; 3642 assert(immArr2.minElement == 1); 3643 3644 // with strings 3645 assert(["b", "a", "c"].minElement == "a"); 3646 3647 // with all dummy ranges 3648 import std.internal.test.dummyrange; 3649 foreach (DummyType; AllDummyRanges) 3650 { 3651 DummyType d; 3652 assert(d.minElement == 1); 3653 assert(d.minElement!(a => a) == 1); 3654 assert(d.minElement!(a => -a) == 10); 3655 } 3656 3657 // with empty, but seeded ranges 3658 int[] arr; 3659 assert(arr.minElement(42) == 42); 3660 assert(arr.minElement!(a => a)(42) == 42); 3661 } 3662 3663 @nogc @safe nothrow pure unittest 3664 { 3665 static immutable arr = [7, 3, 4, 2, 1, 8]; 3666 assert(arr.minElement == 1); 3667 3668 static immutable arr2d = [[1, 9], [3, 1], [4, 2]]; 3669 assert(arr2d.minElement!"a[1]" == arr2d[1]); 3670 } 3671 3672 // https://issues.dlang.org/show_bug.cgi?id=17982 3673 @safe unittest 3674 { 3675 struct A 3676 { 3677 int val; 3678 } 3679 3680 const(A)[] v = [A(0)]; 3681 assert(v.minElement!"a.val" == A(0)); 3682 } 3683 3684 // https://issues.dlang.org/show_bug.cgi?id=17982 3685 @safe unittest 3686 { 3687 class B 3688 { 3689 int val; 3690 this(int val){ this.val = val; } 3691 } 3692 3693 const(B) doStuff(const(B)[] v) 3694 { 3695 return v.minElement!"a.val"; 3696 } 3697 assert(doStuff([new B(1), new B(0), new B(2)]).val == 0); 3698 3699 const(B)[] arr = [new B(0), new B(1)]; 3700 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824 3701 assert(arr.minElement!"a.val".val == 0); 3702 } 3703 3704 /** 3705 Iterates the passed range and returns the maximal element. 3706 A custom mapping function can be passed to `map`. 3707 In other languages this is sometimes called `argmax`. 3708 3709 Complexity: O(n) 3710 Exactly `n - 1` comparisons are needed. 3711 3712 Params: 3713 map = custom accessor for the comparison key 3714 r = range from which the maximum element will be selected 3715 seed = custom seed to use as initial element 3716 3717 Returns: The maximal element of the passed-in range. 3718 3719 Note: 3720 If at least one of the arguments is NaN, the result is an unspecified value. 3721 See $(REF minElement, std,algorithm,searching) for examples on how to cope 3722 with NaNs. 3723 3724 See_Also: 3725 3726 $(LREF minElement), $(REF max, std,algorithm,comparison), $(LREF maxCount), 3727 $(LREF maxIndex), $(LREF maxPos) 3728 */ 3729 auto maxElement(alias map = (a => a), Range)(Range r) 3730 if (isInputRange!Range && !isInfinite!Range) 3731 { 3732 return extremum!(map, "a > b")(r); 3733 } 3734 3735 /// ditto 3736 auto maxElement(alias map = (a => a), Range, RangeElementType = ElementType!Range) 3737 (Range r, RangeElementType seed) 3738 if (isInputRange!Range && !isInfinite!Range && 3739 !is(CommonType!(ElementType!Range, RangeElementType) == void)) 3740 { 3741 return extremum!(map, "a > b")(r, seed); 3742 } 3743 3744 /// 3745 @safe pure unittest 3746 { 3747 import std.range : enumerate; 3748 import std.typecons : tuple; 3749 assert([2, 1, 4, 3].maxElement == 4); 3750 3751 // allows to get the index of an element too 3752 assert([2, 1, 4, 3].enumerate.maxElement!"a.value" == tuple(2, 4)); 3753 3754 // any custom accessor can be passed 3755 assert([[0, 4], [1, 2]].maxElement!"a[1]" == [0, 4]); 3756 3757 // can be seeded 3758 int[] arr; 3759 assert(arr.minElement(1) == 1); 3760 } 3761 3762 @safe pure unittest 3763 { 3764 import std.range : enumerate, iota; 3765 3766 // supports mapping 3767 assert([3, 4, 5, 1, 2].enumerate.maxElement!"a.value" == tuple(2, 5)); 3768 assert([5, 2, 4].enumerate.maxElement!"a.value" == tuple(0, 5)); 3769 3770 // forward ranges 3771 assert(iota(1, 5).maxElement() == 4); 3772 assert(iota(2, 5).enumerate.maxElement!"a.value" == tuple(2, 4)); 3773 assert(iota(4, 14).enumerate.maxElement!"a.value" == tuple(9, 13)); 3774 3775 // should work with const 3776 const(int)[] immArr = [2, 3, 1]; 3777 assert(immArr.maxElement == 3); 3778 3779 // should work with immutable 3780 immutable(int)[] immArr2 = [2, 3, 1]; 3781 assert(immArr2.maxElement == 3); 3782 3783 // with strings 3784 assert(["a", "c", "b"].maxElement == "c"); 3785 3786 // with all dummy ranges 3787 import std.internal.test.dummyrange; 3788 foreach (DummyType; AllDummyRanges) 3789 { 3790 DummyType d; 3791 assert(d.maxElement == 10); 3792 assert(d.maxElement!(a => a) == 10); 3793 assert(d.maxElement!(a => -a) == 1); 3794 } 3795 3796 // with empty, but seeded ranges 3797 int[] arr; 3798 assert(arr.maxElement(42) == 42); 3799 assert(arr.maxElement!(a => a)(42) == 42); 3800 3801 } 3802 3803 @nogc @safe nothrow pure unittest 3804 { 3805 static immutable arr = [7, 3, 8, 2, 1, 4]; 3806 assert(arr.maxElement == 8); 3807 3808 static immutable arr2d = [[1, 3], [3, 9], [4, 2]]; 3809 assert(arr2d.maxElement!"a[1]" == arr2d[1]); 3810 } 3811 3812 // https://issues.dlang.org/show_bug.cgi?id=17982 3813 @safe unittest 3814 { 3815 class B 3816 { 3817 int val; 3818 this(int val){ this.val = val; } 3819 } 3820 3821 const(B) doStuff(const(B)[] v) 3822 { 3823 return v.maxElement!"a.val"; 3824 } 3825 assert(doStuff([new B(1), new B(0), new B(2)]).val == 2); 3826 3827 const(B)[] arr = [new B(0), new B(1)]; 3828 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824 3829 assert(arr.maxElement!"a.val".val == 1); 3830 } 3831 3832 // minPos 3833 /** 3834 Computes a subrange of `range` starting at the first occurrence of `range`'s 3835 minimum (respectively maximum) and with the same ending as `range`, or the 3836 empty range if `range` itself is empty. 3837 3838 Formally, the minimum is a value `x` in `range` such that `pred(a, x)` is 3839 `false` for all values `a` in `range`. Conversely, the maximum is a value `x` in 3840 `range` such that `pred(x, a)` is `false` for all values `a` in `range` (note 3841 the swapped arguments to `pred`). 3842 3843 These functions may be used for computing arbitrary extrema by choosing `pred` 3844 appropriately. For corrrect functioning, `pred` must be a strict partial order, 3845 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and 3846 irreflexive (`pred(a, a)` is `false`). 3847 3848 Params: 3849 pred = The ordering predicate to use to determine the extremum (minimum or 3850 maximum) element. 3851 range = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search. 3852 3853 Returns: The position of the minimum (respectively maximum) element of forward 3854 range `range`, i.e. a subrange of `range` starting at the position of its 3855 smallest (respectively largest) element and with the same ending as `range`. 3856 3857 Limitations: If at least one of the arguments is NaN, the result is 3858 an unspecified value. See $(REF maxElement, std,algorithm,searching) 3859 for examples on how to cope with NaNs. 3860 3861 See_Also: 3862 $(REF max, std,algorithm,comparison), $(LREF minCount), $(LREF minIndex), $(LREF minElement) 3863 */ 3864 Range minPos(alias pred = "a < b", Range)(Range range) 3865 if (isForwardRange!Range && !isInfinite!Range && 3866 is(typeof(binaryFun!pred(range.front, range.front)))) 3867 { 3868 static if (hasSlicing!Range && isRandomAccessRange!Range && hasLength!Range) 3869 { 3870 // Prefer index-based access 3871 size_t pos = 0; 3872 foreach (i; 1 .. range.length) 3873 { 3874 if (binaryFun!pred(range[i], range[pos])) 3875 { 3876 pos = i; 3877 } 3878 } 3879 return range[pos .. range.length]; 3880 } 3881 else 3882 { 3883 auto result = range.save; 3884 if (range.empty) return result; 3885 for (range.popFront(); !range.empty; range.popFront()) 3886 { 3887 // Note: Unlike minCount, we do not care to find equivalence, so a 3888 // single pred call is enough. 3889 if (binaryFun!pred(range.front, result.front)) 3890 { 3891 // change the min 3892 result = range.save; 3893 } 3894 } 3895 return result; 3896 } 3897 } 3898 3899 /// Ditto 3900 Range maxPos(alias pred = "a < b", Range)(Range range) 3901 if (isForwardRange!Range && !isInfinite!Range && 3902 is(typeof(binaryFun!pred(range.front, range.front)))) 3903 { 3904 return range.minPos!((a, b) => binaryFun!pred(b, a)); 3905 } 3906 3907 /// 3908 @safe unittest 3909 { 3910 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; 3911 // Minimum is 1 and first occurs in position 3 3912 assert(a.minPos == [ 1, 2, 4, 1, 1, 2 ]); 3913 // Maximum is 4 and first occurs in position 2 3914 assert(a.maxPos == [ 4, 1, 2, 4, 1, 1, 2 ]); 3915 } 3916 3917 @safe unittest 3918 { 3919 import std.algorithm.comparison : equal; 3920 import std.internal.test.dummyrange; 3921 3922 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; 3923 //Test that an empty range works 3924 int[] b = a[$..$]; 3925 assert(equal(minPos(b), b)); 3926 3927 //test with reference range. 3928 assert( equal( minPos(new ReferenceForwardRange!int([1, 2, 1, 0, 2, 0])), [0, 2, 0] ) ); 3929 } 3930 3931 @system unittest 3932 { 3933 //Rvalue range 3934 import std.algorithm.comparison : equal; 3935 import std.container : Array; 3936 3937 assert(Array!int(2, 3, 4, 1, 2, 4, 1, 1, 2) 3938 [] 3939 .minPos() 3940 .equal([ 1, 2, 4, 1, 1, 2 ])); 3941 } 3942 3943 @safe unittest 3944 { 3945 //BUG 9299 3946 immutable a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; 3947 // Minimum is 1 and first occurs in position 3 3948 assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]); 3949 // Maximum is 4 and first occurs in position 5 3950 assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]); 3951 3952 immutable(int[])[] b = [ [4], [2, 4], [4], [4] ]; 3953 assert(minPos!("a[0] < b[0]")(b) == [ [2, 4], [4], [4] ]); 3954 } 3955 3956 /** 3957 Computes the index of the first occurrence of `range`'s minimum element. 3958 3959 Params: 3960 pred = The ordering predicate to use to determine the minimum element. 3961 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 3962 to search. 3963 3964 Complexity: $(BIGOH range.length) 3965 Exactly `range.length - 1` comparisons are needed. 3966 3967 Returns: 3968 The index of the first encounter of the minimum element in `range`. If the 3969 `range` is empty, -1 is returned. 3970 3971 Limitations: 3972 If at least one of the arguments is NaN, the result is 3973 an unspecified value. See $(REF maxElement, std,algorithm,searching) 3974 for examples on how to cope with NaNs. 3975 3976 See_Also: 3977 $(LREF maxIndex), $(REF min, std,algorithm,comparison), $(LREF minCount), $(LREF minElement), $(LREF minPos) 3978 */ 3979 ptrdiff_t minIndex(alias pred = "a < b", Range)(Range range) 3980 if (isInputRange!Range && !isInfinite!Range && 3981 is(typeof(binaryFun!pred(range.front, range.front)))) 3982 { 3983 if (range.empty) return -1; 3984 3985 ptrdiff_t minPos = 0; 3986 3987 static if (isRandomAccessRange!Range && hasLength!Range) 3988 { 3989 foreach (i; 1 .. range.length) 3990 { 3991 if (binaryFun!pred(range[i], range[minPos])) 3992 { 3993 minPos = i; 3994 } 3995 } 3996 } 3997 else 3998 { 3999 ptrdiff_t curPos = 0; 4000 Unqual!(typeof(range.front)) min = range.front; 4001 for (range.popFront(); !range.empty; range.popFront()) 4002 { 4003 ++curPos; 4004 if (binaryFun!pred(range.front, min)) 4005 { 4006 min = range.front; 4007 minPos = curPos; 4008 } 4009 } 4010 } 4011 return minPos; 4012 } 4013 4014 /// 4015 @safe pure nothrow unittest 4016 { 4017 int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2]; 4018 4019 // Minimum is 1 and first occurs in position 3 4020 assert(a.minIndex == 3); 4021 // Get maximum index with minIndex 4022 assert(a.minIndex!"a > b" == 2); 4023 4024 // Range is empty, so return value is -1 4025 int[] b; 4026 assert(b.minIndex == -1); 4027 4028 // Works with more custom types 4029 struct Dog { int age; } 4030 Dog[] dogs = [Dog(10), Dog(5), Dog(15)]; 4031 assert(dogs.minIndex!"a.age < b.age" == 1); 4032 } 4033 4034 @safe pure unittest 4035 { 4036 // should work with const 4037 const(int)[] immArr = [2, 1, 3]; 4038 assert(immArr.minIndex == 1); 4039 4040 // Works for const ranges too 4041 const int[] c = [2, 5, 4, 1, 2, 3]; 4042 assert(c.minIndex == 3); 4043 4044 // should work with immutable 4045 immutable(int)[] immArr2 = [2, 1, 3]; 4046 assert(immArr2.minIndex == 1); 4047 4048 // with strings 4049 assert(["b", "a", "c"].minIndex == 1); 4050 4051 // infinite range 4052 import std.range : cycle; 4053 static assert(!__traits(compiles, cycle([1]).minIndex)); 4054 4055 // with all dummy ranges 4056 import std.internal.test.dummyrange : AllDummyRanges; 4057 foreach (DummyType; AllDummyRanges) 4058 { 4059 static if (isForwardRange!DummyType && !isInfinite!DummyType) 4060 { 4061 DummyType d; 4062 d.arr = [5, 3, 7, 2, 1, 4]; 4063 assert(d.minIndex == 4); 4064 4065 d.arr = []; 4066 assert(d.minIndex == -1); 4067 } 4068 } 4069 } 4070 4071 @nogc @safe nothrow pure unittest 4072 { 4073 static immutable arr = [7, 3, 8, 2, 1, 4]; 4074 assert(arr.minIndex == 4); 4075 4076 static immutable arr2d = [[1, 3], [3, 9], [4, 2]]; 4077 assert(arr2d.minIndex!"a[1] < b[1]" == 2); 4078 } 4079 4080 @safe nothrow pure unittest 4081 { 4082 // InputRange test 4083 4084 static struct InRange 4085 { 4086 @property int front() 4087 { 4088 return arr[index]; 4089 } 4090 4091 bool empty() const 4092 { 4093 return arr.length == index; 4094 } 4095 4096 void popFront() 4097 { 4098 index++; 4099 } 4100 4101 int[] arr; 4102 size_t index = 0; 4103 } 4104 4105 static assert(isInputRange!InRange); 4106 4107 auto arr1 = InRange([5, 2, 3, 4, 5, 3, 6]); 4108 auto arr2 = InRange([7, 3, 8, 2, 1, 4]); 4109 4110 assert(arr1.minIndex == 1); 4111 assert(arr2.minIndex == 4); 4112 } 4113 4114 /** 4115 Computes the index of the first occurrence of `range`'s maximum element. 4116 4117 Complexity: $(BIGOH range) 4118 Exactly `range.length - 1` comparisons are needed. 4119 4120 Params: 4121 pred = The ordering predicate to use to determine the maximum element. 4122 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to search. 4123 4124 Returns: 4125 The index of the first encounter of the maximum in `range`. If the 4126 `range` is empty, -1 is returned. 4127 4128 Limitations: 4129 If at least one of the arguments is NaN, the result is 4130 an unspecified value. See $(REF maxElement, std,algorithm,searching) 4131 for examples on how to cope with NaNs. 4132 4133 See_Also: 4134 $(LREF minIndex), $(REF max, std,algorithm,comparison), $(LREF maxCount), $(LREF maxElement), $(LREF maxPos) 4135 */ 4136 ptrdiff_t maxIndex(alias pred = "a < b", Range)(Range range) 4137 if (isInputRange!Range && !isInfinite!Range && 4138 is(typeof(binaryFun!pred(range.front, range.front)))) 4139 { 4140 return range.minIndex!((a, b) => binaryFun!pred(b, a)); 4141 } 4142 4143 /// 4144 @safe pure nothrow unittest 4145 { 4146 // Maximum is 4 and first occurs in position 2 4147 int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2]; 4148 assert(a.maxIndex == 2); 4149 4150 // Empty range 4151 int[] b; 4152 assert(b.maxIndex == -1); 4153 4154 // Works with more custom types 4155 struct Dog { int age; } 4156 Dog[] dogs = [Dog(10), Dog(15), Dog(5)]; 4157 assert(dogs.maxIndex!"a.age < b.age" == 1); 4158 } 4159 4160 @safe pure unittest 4161 { 4162 // should work with const 4163 const(int)[] immArr = [5, 1, 3]; 4164 assert(immArr.maxIndex == 0); 4165 4166 // Works for const ranges too 4167 const int[] c = [2, 5, 4, 1, 2, 3]; 4168 assert(c.maxIndex == 1); 4169 4170 4171 // should work with immutable 4172 immutable(int)[] immArr2 = [2, 1, 3]; 4173 assert(immArr2.maxIndex == 2); 4174 4175 // with strings 4176 assert(["b", "a", "c"].maxIndex == 2); 4177 4178 // infinite range 4179 import std.range : cycle; 4180 static assert(!__traits(compiles, cycle([1]).maxIndex)); 4181 4182 // with all dummy ranges 4183 import std.internal.test.dummyrange : AllDummyRanges; 4184 foreach (DummyType; AllDummyRanges) 4185 { 4186 static if (isForwardRange!DummyType && !isInfinite!DummyType) 4187 { 4188 DummyType d; 4189 4190 d.arr = [5, 3, 7, 2, 1, 4]; 4191 assert(d.maxIndex == 2); 4192 4193 d.arr = []; 4194 assert(d.maxIndex == -1); 4195 } 4196 } 4197 } 4198 4199 @nogc @safe nothrow pure unittest 4200 { 4201 static immutable arr = [7, 3, 8, 2, 1, 4]; 4202 assert(arr.maxIndex == 2); 4203 4204 static immutable arr2d = [[1, 3], [3, 9], [4, 2]]; 4205 assert(arr2d.maxIndex!"a[1] < b[1]" == 1); 4206 } 4207 4208 /** 4209 Skip over the initial portion of the first given range (`haystack`) that matches 4210 any of the additionally given ranges (`needles`) fully, or 4211 if no second range is given skip over the elements that fulfill pred. 4212 Do nothing if there is no match. 4213 4214 Params: 4215 pred = The predicate that determines whether elements from each respective 4216 range match. Defaults to equality `"a == b"`. 4217 */ 4218 template skipOver(alias pred = (a, b) => a == b) 4219 { 4220 import std.meta : allSatisfy; 4221 4222 enum bool isPredComparable(T) = ifTestable!(T, binaryFun!pred); 4223 4224 /** 4225 Params: 4226 haystack = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to 4227 move forward. 4228 needles = The $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives) 4229 representing the prefix of `r1` to skip over. 4230 es = The element to match. 4231 4232 Returns: 4233 `true` if the prefix of `haystack` matches any range of `needles` fully 4234 or `pred` evaluates to true, and `haystack` has been advanced to the point past this segment; 4235 otherwise false, and `haystack` is left in its original position. 4236 4237 Note: 4238 By definition, empty ranges are matched fully and if `needles` contains an empty range, 4239 `skipOver` will return `true`. 4240 */ 4241 bool skipOver(Haystack, Needles...)(ref Haystack haystack, Needles needles) 4242 if (is(typeof(binaryFun!pred(haystack.front, needles[0].front))) && 4243 isForwardRange!Haystack && 4244 allSatisfy!(isInputRange, Needles) && 4245 !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Needles))) == void)) 4246 { 4247 static if (__traits(isSame, pred, (a, b) => a == b) 4248 && is(typeof(haystack[0 .. $] == needles[0]) : bool) 4249 && is(typeof(haystack = haystack[0 .. $])) 4250 && hasLength!Haystack && allSatisfy!(hasLength, Needles)) 4251 { 4252 ptrdiff_t longestMatch = -1; 4253 static foreach (r2; needles) 4254 { 4255 if (r2.length <= haystack.length && longestMatch < ptrdiff_t(r2.length) 4256 && (haystack[0 .. r2.length] == r2 || r2.length == 0)) 4257 longestMatch = r2.length; 4258 } 4259 if (longestMatch >= 0) 4260 { 4261 if (longestMatch > 0) 4262 haystack = haystack[longestMatch .. $]; 4263 4264 return true; 4265 } 4266 return false; 4267 } 4268 else 4269 { 4270 import std.algorithm.comparison : min; 4271 auto r = haystack.save; 4272 4273 static if (hasLength!Haystack && allSatisfy!(hasLength, Needles)) 4274 { 4275 import std.algorithm.iteration : map; 4276 import std.algorithm.searching : minElement; 4277 import std.range : only; 4278 // Shortcut opportunity! 4279 if (needles.only.map!(a => a.length).minElement > haystack.length) 4280 return false; 4281 } 4282 4283 // compatibility: return true if any range was empty 4284 bool hasEmptyRanges; 4285 static foreach (i, r2; needles) 4286 { 4287 if (r2.empty) 4288 hasEmptyRanges = true; 4289 } 4290 4291 bool hasNeedleMatch; 4292 size_t inactiveNeedlesLen; 4293 bool[Needles.length] inactiveNeedles; 4294 for (; !r.empty; r.popFront) 4295 { 4296 static foreach (i, r2; needles) 4297 { 4298 if (!r2.empty && !inactiveNeedles[i]) 4299 { 4300 if (binaryFun!pred(r.front, r2.front)) 4301 { 4302 r2.popFront; 4303 if (r2.empty) 4304 { 4305 // we skipped over a new match 4306 hasNeedleMatch = true; 4307 inactiveNeedlesLen++; 4308 // skip over haystack 4309 haystack = r; 4310 } 4311 } 4312 else 4313 { 4314 inactiveNeedles[i] = true; 4315 inactiveNeedlesLen++; 4316 } 4317 } 4318 } 4319 4320 // are we done? 4321 if (inactiveNeedlesLen == needles.length) 4322 break; 4323 } 4324 4325 if (hasNeedleMatch) 4326 haystack.popFront; 4327 4328 return hasNeedleMatch || hasEmptyRanges; 4329 } 4330 } 4331 4332 /// Ditto 4333 bool skipOver(R)(ref R r1) 4334 if (isForwardRange!R && 4335 ifTestable!(typeof(r1.front), unaryFun!pred)) 4336 { 4337 if (r1.empty || !unaryFun!pred(r1.front)) 4338 return false; 4339 4340 do 4341 r1.popFront(); 4342 while (!r1.empty && unaryFun!pred(r1.front)); 4343 return true; 4344 } 4345 4346 /// Ditto 4347 bool skipOver(R, Es...)(ref R r, Es es) 4348 if (isInputRange!R && is(typeof(binaryFun!pred(r.front, es[0])))) 4349 { 4350 if (r.empty) 4351 return false; 4352 4353 static foreach (e; es) 4354 { 4355 if (binaryFun!pred(r.front, e)) 4356 { 4357 r.popFront(); 4358 return true; 4359 } 4360 } 4361 return false; 4362 } 4363 } 4364 4365 /// 4366 @safe unittest 4367 { 4368 import std.algorithm.comparison : equal; 4369 4370 auto s1 = "Hello world"; 4371 assert(!skipOver(s1, "Ha")); 4372 assert(s1 == "Hello world"); 4373 assert(skipOver(s1, "Hell") && s1 == "o world", s1); 4374 4375 string[] r1 = ["abc", "def", "hij"]; 4376 dstring[] r2 = ["abc"d]; 4377 assert(!skipOver!((a, b) => a.equal(b))(r1, ["def"d]), r1[0]); 4378 assert(r1 == ["abc", "def", "hij"]); 4379 assert(skipOver!((a, b) => a.equal(b))(r1, r2)); 4380 assert(r1 == ["def", "hij"]); 4381 } 4382 4383 /// 4384 @safe unittest 4385 { 4386 import std.ascii : isWhite; 4387 import std.range.primitives : empty; 4388 4389 auto s2 = "\t\tvalue"; 4390 auto s3 = ""; 4391 auto s4 = "\t\t\t"; 4392 assert(s2.skipOver!isWhite && s2 == "value"); 4393 assert(!s3.skipOver!isWhite); 4394 assert(s4.skipOver!isWhite && s3.empty); 4395 } 4396 4397 /// Variadic skipOver 4398 @safe unittest 4399 { 4400 auto s = "Hello world"; 4401 assert(!skipOver(s, "hello", "HellO")); 4402 assert(s == "Hello world"); 4403 4404 // the range is skipped over the longest matching needle is skipped 4405 assert(skipOver(s, "foo", "hell", "Hello ")); 4406 assert(s == "world"); 4407 } 4408 4409 /// 4410 @safe unittest 4411 { 4412 import std.algorithm.comparison : equal; 4413 4414 auto s1 = "Hello world"; 4415 assert(!skipOver(s1, 'a')); 4416 assert(s1 == "Hello world"); 4417 assert(skipOver(s1, 'H') && s1 == "ello world"); 4418 4419 string[] r = ["abc", "def", "hij"]; 4420 dstring e = "abc"d; 4421 assert(!skipOver!((a, b) => a.equal(b))(r, "def"d)); 4422 assert(r == ["abc", "def", "hij"]); 4423 assert(skipOver!((a, b) => a.equal(b))(r, e)); 4424 assert(r == ["def", "hij"]); 4425 4426 auto s2 = ""; 4427 assert(!s2.skipOver('a')); 4428 } 4429 4430 /// Partial instantiation 4431 @safe unittest 4432 { 4433 import std.ascii : isWhite; 4434 import std.range.primitives : empty; 4435 4436 alias whitespaceSkiper = skipOver!isWhite; 4437 4438 auto s2 = "\t\tvalue"; 4439 auto s3 = ""; 4440 auto s4 = "\t\t\t"; 4441 assert(whitespaceSkiper(s2) && s2 == "value"); 4442 assert(!whitespaceSkiper(s2)); 4443 assert(whitespaceSkiper(s4) && s3.empty); 4444 } 4445 4446 // variadic skipOver 4447 @safe unittest 4448 { 4449 auto s = "DLang.rocks"; 4450 assert(!s.skipOver("dlang", "DLF", "DLang ")); 4451 assert(s == "DLang.rocks"); 4452 4453 assert(s.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLanpp")); 4454 assert(s == "ang.rocks"); 4455 s = "DLang.rocks"; 4456 4457 assert(s.skipOver("DLang", "DLANG", "DLF", "D", "DL", "DLang ")); 4458 assert(s == ".rocks"); 4459 s = "DLang.rocks"; 4460 4461 assert(s.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLang.")); 4462 assert(s == "rocks"); 4463 } 4464 4465 // variadic with custom pred 4466 @safe unittest 4467 { 4468 import std.ascii : toLower; 4469 4470 auto s = "DLang.rocks"; 4471 assert(!s.skipOver("dlang", "DLF", "DLang ")); 4472 assert(s == "DLang.rocks"); 4473 4474 assert(s.skipOver!((a, b) => a.toLower == b.toLower)("dlang", "DLF", "DLang ")); 4475 assert(s == ".rocks"); 4476 } 4477 4478 // variadic skipOver with mixed needles 4479 @safe unittest 4480 { 4481 auto s = "DLang.rocks"; 4482 assert(!s.skipOver("dlang"d, "DLF", "DLang "w)); 4483 assert(s == "DLang.rocks"); 4484 4485 assert(s.skipOver("dlang", "DLANG"d, "DLF"w, "D"d, "DL", "DLanp")); 4486 assert(s == "ang.rocks"); 4487 s = "DLang.rocks"; 4488 4489 assert(s.skipOver("DLang", "DLANG"w, "DLF"d, "D"d, "DL", "DLang ")); 4490 assert(s == ".rocks"); 4491 s = "DLang.rocks"; 4492 4493 assert(s.skipOver("dlang", "DLANG"w, "DLF", "D"d, "DL"w, "DLang."d)); 4494 assert(s == "rocks"); 4495 4496 import std.algorithm.iteration : filter; 4497 s = "DLang.rocks"; 4498 assert(s.skipOver("dlang", "DLang".filter!(a => true))); 4499 assert(s == ".rocks"); 4500 } 4501 4502 // variadic skipOver with auto-decoding 4503 @safe unittest 4504 { 4505 auto s = "☢☣☠.☺"; 4506 assert(s.skipOver("a", "☢", "☢☣☠")); 4507 assert(s == ".☺"); 4508 } 4509 4510 // skipOver with @nogc 4511 @safe @nogc pure nothrow unittest 4512 { 4513 static immutable s = [0, 1, 2]; 4514 immutable(int)[] s2 = s[]; 4515 4516 static immutable skip1 = [0, 2]; 4517 static immutable skip2 = [0, 1]; 4518 assert(s2.skipOver(skip1, skip2)); 4519 assert(s2 == s[2 .. $]); 4520 } 4521 4522 // variadic skipOver with single elements 4523 @safe unittest 4524 { 4525 auto s = "DLang.rocks"; 4526 assert(!s.skipOver('a', 'd', 'e')); 4527 assert(s == "DLang.rocks"); 4528 4529 assert(s.skipOver('a', 'D', 'd', 'D')); 4530 assert(s == "Lang.rocks"); 4531 s = "DLang.rocks"; 4532 4533 assert(s.skipOver(wchar('a'), dchar('D'), 'd')); 4534 assert(s == "Lang.rocks"); 4535 4536 dstring dstr = "+Foo"; 4537 assert(!dstr.skipOver('.', '-')); 4538 assert(dstr == "+Foo"); 4539 4540 assert(dstr.skipOver('+', '-')); 4541 assert(dstr == "Foo"); 4542 } 4543 4544 // skipOver with empty ranges must return true (compatibility) 4545 @safe unittest 4546 { 4547 auto s = "DLang.rocks"; 4548 assert(s.skipOver("")); 4549 assert(s.skipOver("", "")); 4550 assert(s.skipOver("", "foo")); 4551 4552 auto s2 = "DLang.rocks"d; 4553 assert(s2.skipOver("")); 4554 assert(s2.skipOver("", "")); 4555 assert(s2.skipOver("", "foo")); 4556 } 4557 4558 // dxml regression 4559 @safe unittest 4560 { 4561 import std.utf : byCodeUnit; 4562 import std.algorithm.comparison : equal; 4563 4564 bool stripStartsWith(Text)(ref Text text, string needle) 4565 { 4566 return text.skipOver(needle.byCodeUnit()); 4567 } 4568 auto text = "<xml></xml>"d.byCodeUnit; 4569 assert(stripStartsWith(text, "<xml>")); 4570 assert(text.equal("</xml>")); 4571 } 4572 4573 /** 4574 Checks whether the given 4575 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) starts with (one 4576 of) the given needle(s) or, if no needles are given, 4577 if its front element fulfils predicate `pred`. 4578 4579 Params: 4580 4581 pred = Predicate to use in comparing the elements of the haystack and the 4582 needle(s). Mandatory if no needles are given. 4583 4584 doesThisStart = The input range to check. 4585 4586 withOneOfThese = The needles against which the range is to be checked, 4587 which may be individual elements or input ranges of elements. 4588 4589 withThis = The single needle to check, which may be either a single element 4590 or an input range of elements. 4591 4592 Returns: 4593 4594 0 if the needle(s) do not occur at the beginning of the given range; 4595 otherwise the position of the matching needle, that is, 1 if the range starts 4596 with `withOneOfThese[0]`, 2 if it starts with `withOneOfThese[1]`, and so 4597 on. 4598 4599 In the case where `doesThisStart` starts with multiple of the ranges or 4600 elements in `withOneOfThese`, then the shortest one matches (if there are 4601 two which match which are of the same length (e.g. `"a"` and `'a'`), then 4602 the left-most of them in the argument 4603 list matches). 4604 4605 In the case when no needle parameters are given, return `true` iff front of 4606 `doesThisStart` fulfils predicate `pred`. 4607 */ 4608 uint startsWith(alias pred = (a, b) => a == b, Range, Needles...)(Range doesThisStart, Needles withOneOfThese) 4609 if (isInputRange!Range && Needles.length > 1 && 4610 is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[0])) : bool ) && 4611 is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[1 .. $])) : uint)) 4612 { 4613 import std.meta : allSatisfy; 4614 4615 template checkType(T) 4616 { 4617 enum checkType = is(immutable ElementEncodingType!Range == immutable T); 4618 } 4619 4620 // auto-decoding special case 4621 static if (__traits(isSame, binaryFun!pred, (a, b) => a == b) && 4622 isNarrowString!Range && allSatisfy!(checkType, Needles)) 4623 { 4624 import std.utf : byCodeUnit; 4625 auto haystack = doesThisStart.byCodeUnit; 4626 } 4627 else 4628 { 4629 alias haystack = doesThisStart; 4630 } 4631 alias needles = withOneOfThese; 4632 4633 // Make one pass looking for empty ranges in needles 4634 foreach (i, Unused; Needles) 4635 { 4636 // Empty range matches everything 4637 static if (!is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool)) 4638 { 4639 if (needles[i].empty) return i + 1; 4640 } 4641 } 4642 4643 for (; !haystack.empty; haystack.popFront()) 4644 { 4645 foreach (i, Unused; Needles) 4646 { 4647 static if (is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool)) 4648 { 4649 // Single-element 4650 if (binaryFun!pred(haystack.front, needles[i])) 4651 { 4652 // found, but instead of returning, we just stop searching. 4653 // This is to account for one-element 4654 // range matches (consider startsWith("ab", "a", 4655 // 'a') should return 1, not 2). 4656 break; 4657 } 4658 } 4659 else 4660 { 4661 if (binaryFun!pred(haystack.front, needles[i].front)) 4662 { 4663 continue; 4664 } 4665 } 4666 4667 // This code executed on failure to match 4668 // Out with this guy, check for the others 4669 uint result = startsWith!pred(haystack, needles[0 .. i], needles[i + 1 .. $]); 4670 if (result > i) ++result; 4671 return result; 4672 } 4673 4674 // If execution reaches this point, then the front matches for all 4675 // needle ranges, or a needle element has been matched. 4676 // What we need to do now is iterate, lopping off the front of 4677 // the range and checking if the result is empty, or finding an 4678 // element needle and returning. 4679 // If neither happens, we drop to the end and loop. 4680 foreach (i, Unused; Needles) 4681 { 4682 static if (is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool)) 4683 { 4684 // Test has passed in the previous loop 4685 return i + 1; 4686 } 4687 else 4688 { 4689 needles[i].popFront(); 4690 if (needles[i].empty) return i + 1; 4691 } 4692 } 4693 } 4694 return 0; 4695 } 4696 4697 /// Ditto 4698 bool startsWith(alias pred = "a == b", R1, R2)(R1 doesThisStart, R2 withThis) 4699 if (isInputRange!R1 && 4700 isInputRange!R2 && 4701 is(typeof(binaryFun!pred(doesThisStart.front, withThis.front)) : bool)) 4702 { 4703 alias haystack = doesThisStart; 4704 alias needle = withThis; 4705 4706 static if (is(typeof(pred) : string)) 4707 enum isDefaultPred = pred == "a == b"; 4708 else 4709 enum isDefaultPred = false; 4710 4711 // Note: Although narrow strings don't have a "true" length, for a narrow string to start with another 4712 // narrow string, it must have *at least* as many code units. 4713 static if ((hasLength!R1 && hasLength!R2) || 4714 ((hasLength!R1 || isNarrowString!R1) && (hasLength!R2 || isNarrowString!R2) 4715 && (ElementEncodingType!R1.sizeof <= ElementEncodingType!R2.sizeof))) 4716 { 4717 if (haystack.length < needle.length) 4718 return false; 4719 } 4720 4721 static if (isDefaultPred && isArray!R1 && isArray!R2 && 4722 is(immutable ElementEncodingType!R1 == immutable ElementEncodingType!R2)) 4723 { 4724 //Array slice comparison mode 4725 return haystack[0 .. needle.length] == needle; 4726 } 4727 else static if (isRandomAccessRange!R1 && isRandomAccessRange!R2 && hasLength!R2) 4728 { 4729 //RA dual indexing mode 4730 foreach (j; 0 .. needle.length) 4731 { 4732 if (!binaryFun!pred(haystack[j], needle[j])) 4733 // not found 4734 return false; 4735 } 4736 // found! 4737 return true; 4738 } 4739 else 4740 { 4741 //Standard input range mode 4742 if (needle.empty) return true; 4743 static if (hasLength!R1 && hasLength!R2) 4744 { 4745 //We have previously checked that haystack.length > needle.length, 4746 //So no need to check haystack.empty during iteration 4747 for ( ; ; haystack.popFront() ) 4748 { 4749 if (!binaryFun!pred(haystack.front, needle.front)) break; 4750 needle.popFront(); 4751 if (needle.empty) return true; 4752 } 4753 } 4754 else 4755 { 4756 for ( ; !haystack.empty ; haystack.popFront() ) 4757 { 4758 if (!binaryFun!pred(haystack.front, needle.front)) break; 4759 needle.popFront(); 4760 if (needle.empty) return true; 4761 } 4762 } 4763 return false; 4764 } 4765 } 4766 4767 /// Ditto 4768 bool startsWith(alias pred = "a == b", R, E)(R doesThisStart, E withThis) 4769 if (isInputRange!R && 4770 is(typeof(binaryFun!pred(doesThisStart.front, withThis)) : bool)) 4771 { 4772 if (doesThisStart.empty) 4773 return false; 4774 4775 static if (is(typeof(pred) : string)) 4776 enum isDefaultPred = pred == "a == b"; 4777 else 4778 enum isDefaultPred = false; 4779 4780 alias predFunc = binaryFun!pred; 4781 4782 // auto-decoding special case 4783 static if (isNarrowString!R) 4784 { 4785 // statically determine decoding is unnecessary to evaluate pred 4786 static if (isDefaultPred && isSomeChar!E && E.sizeof <= ElementEncodingType!R.sizeof) 4787 return doesThisStart[0] == withThis; 4788 // specialize for ASCII as to not change previous behavior 4789 else 4790 { 4791 if (withThis <= 0x7F) 4792 return predFunc(doesThisStart[0], withThis); 4793 else 4794 return predFunc(doesThisStart.front, withThis); 4795 } 4796 } 4797 else 4798 { 4799 return predFunc(doesThisStart.front, withThis); 4800 } 4801 } 4802 4803 /// Ditto 4804 bool startsWith(alias pred, R)(R doesThisStart) 4805 if (isInputRange!R && 4806 ifTestable!(typeof(doesThisStart.front), unaryFun!pred)) 4807 { 4808 return !doesThisStart.empty && unaryFun!pred(doesThisStart.front); 4809 } 4810 4811 /// 4812 @safe unittest 4813 { 4814 import std.ascii : isAlpha; 4815 4816 assert("abc".startsWith!(a => a.isAlpha)); 4817 assert("abc".startsWith!isAlpha); 4818 assert(!"1ab".startsWith!(a => a.isAlpha)); 4819 assert(!"".startsWith!(a => a.isAlpha)); 4820 4821 import std.algorithm.comparison : among; 4822 assert("abc".startsWith!(a => a.among('a', 'b') != 0)); 4823 assert(!"abc".startsWith!(a => a.among('b', 'c') != 0)); 4824 4825 assert(startsWith("abc", "")); 4826 assert(startsWith("abc", "a")); 4827 assert(!startsWith("abc", "b")); 4828 assert(startsWith("abc", 'a', "b") == 1); 4829 assert(startsWith("abc", "b", "a") == 2); 4830 assert(startsWith("abc", "a", "a") == 1); 4831 assert(startsWith("abc", "ab", "a") == 2); 4832 assert(startsWith("abc", "x", "a", "b") == 2); 4833 assert(startsWith("abc", "x", "aa", "ab") == 3); 4834 assert(startsWith("abc", "x", "aaa", "sab") == 0); 4835 assert(startsWith("abc", "x", "aaa", "a", "sab") == 3); 4836 4837 import std.typecons : Tuple; 4838 alias C = Tuple!(int, "x", int, "y"); 4839 assert(startsWith!"a.x == b"([ C(1,1), C(1,2), C(2,2) ], [1, 1])); 4840 assert(startsWith!"a.x == b"([ C(1,1), C(2,1), C(2,2) ], [1, 1], [1, 2], [1, 3]) == 2); 4841 } 4842 4843 @safe unittest 4844 { 4845 import std.algorithm.iteration : filter; 4846 import std.conv : to; 4847 import std.meta : AliasSeq; 4848 import std.range; 4849 4850 static foreach (S; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring)) 4851 (){ // workaround slow optimizations for large functions 4852 // https://issues.dlang.org/show_bug.cgi?id=2396 4853 assert(!startsWith(to!S("abc"), 'c')); 4854 assert(startsWith(to!S("abc"), 'a', 'c') == 1); 4855 assert(!startsWith(to!S("abc"), 'x', 'n', 'b')); 4856 assert(startsWith(to!S("abc"), 'x', 'n', 'a') == 3); 4857 assert(startsWith(to!S("\uFF28abc"), 'a', '\uFF28', 'c') == 2); 4858 4859 static foreach (T; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring)) 4860 { 4861 //Lots of strings 4862 assert(startsWith(to!S("abc"), to!T(""))); 4863 assert(startsWith(to!S("ab"), to!T("a"))); 4864 assert(startsWith(to!S("abc"), to!T("a"))); 4865 assert(!startsWith(to!S("abc"), to!T("b"))); 4866 assert(!startsWith(to!S("abc"), to!T("b"), "bc", "abcd", "xyz")); 4867 assert(startsWith(to!S("abc"), to!T("ab"), 'a') == 2); 4868 assert(startsWith(to!S("abc"), to!T("a"), "b") == 1); 4869 assert(startsWith(to!S("abc"), to!T("b"), "a") == 2); 4870 assert(startsWith(to!S("abc"), to!T("a"), 'a') == 1); 4871 assert(startsWith(to!S("abc"), 'a', to!T("a")) == 1); 4872 assert(startsWith(to!S("abc"), to!T("x"), "a", "b") == 2); 4873 assert(startsWith(to!S("abc"), to!T("x"), "aa", "ab") == 3); 4874 assert(startsWith(to!S("abc"), to!T("x"), "aaa", "sab") == 0); 4875 assert(startsWith(to!S("abc"), 'a')); 4876 assert(!startsWith(to!S("abc"), to!T("sab"))); 4877 assert(startsWith(to!S("abc"), 'x', to!T("aaa"), 'a', "sab") == 3); 4878 4879 //Unicode 4880 assert(startsWith(to!S("\uFF28el\uFF4co"), to!T("\uFF28el"))); 4881 assert(startsWith(to!S("\uFF28el\uFF4co"), to!T("Hel"), to!T("\uFF28el")) == 2); 4882 assert(startsWith(to!S("日本語"), to!T("日本"))); 4883 assert(startsWith(to!S("日本語"), to!T("日本語"))); 4884 assert(!startsWith(to!S("日本"), to!T("日本語"))); 4885 4886 //Empty 4887 assert(startsWith(to!S(""), T.init)); 4888 assert(!startsWith(to!S(""), 'a')); 4889 assert(startsWith(to!S("a"), T.init)); 4890 assert(startsWith(to!S("a"), T.init, "") == 1); 4891 assert(startsWith(to!S("a"), T.init, 'a') == 1); 4892 assert(startsWith(to!S("a"), 'a', T.init) == 2); 4893 } 4894 }(); 4895 4896 //Length but no RA 4897 assert(!startsWith("abc".takeExactly(3), "abcd".takeExactly(4))); 4898 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(3))); 4899 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(1))); 4900 4901 static foreach (T; AliasSeq!(int, short)) 4902 {{ 4903 immutable arr = cast(T[])[0, 1, 2, 3, 4, 5]; 4904 4905 //RA range 4906 assert(startsWith(arr, cast(int[]) null)); 4907 assert(!startsWith(arr, 5)); 4908 assert(!startsWith(arr, 1)); 4909 assert(startsWith(arr, 0)); 4910 assert(startsWith(arr, 5, 0, 1) == 2); 4911 assert(startsWith(arr, [0])); 4912 assert(startsWith(arr, [0, 1])); 4913 assert(startsWith(arr, [0, 1], 7) == 1); 4914 assert(!startsWith(arr, [0, 1, 7])); 4915 assert(startsWith(arr, [0, 1, 7], [0, 1, 2]) == 2); 4916 4917 //Normal input range 4918 assert(!startsWith(filter!"true"(arr), 1)); 4919 assert(startsWith(filter!"true"(arr), 0)); 4920 assert(startsWith(filter!"true"(arr), [0])); 4921 assert(startsWith(filter!"true"(arr), [0, 1])); 4922 assert(startsWith(filter!"true"(arr), [0, 1], 7) == 1); 4923 assert(!startsWith(filter!"true"(arr), [0, 1, 7])); 4924 assert(startsWith(filter!"true"(arr), [0, 1, 7], [0, 1, 2]) == 2); 4925 assert(startsWith(arr, filter!"true"([0, 1]))); 4926 assert(startsWith(arr, filter!"true"([0, 1]), 7) == 1); 4927 assert(!startsWith(arr, filter!"true"([0, 1, 7]))); 4928 assert(startsWith(arr, [0, 1, 7], filter!"true"([0, 1, 2])) == 2); 4929 4930 //Non-default pred 4931 assert(startsWith!("a%10 == b%10")(arr, [10, 11])); 4932 assert(!startsWith!("a%10 == b%10")(arr, [10, 12])); 4933 }} 4934 } 4935 4936 /* (Not yet documented.) 4937 Consume all elements from `r` that are equal to one of the elements 4938 `es`. 4939 */ 4940 private void skipAll(alias pred = "a == b", R, Es...)(ref R r, Es es) 4941 //if (is(typeof(binaryFun!pred(r1.front, es[0])))) 4942 { 4943 loop: 4944 for (; !r.empty; r.popFront()) 4945 { 4946 foreach (i, E; Es) 4947 { 4948 if (binaryFun!pred(r.front, es[i])) 4949 { 4950 continue loop; 4951 } 4952 } 4953 break; 4954 } 4955 } 4956 4957 @safe unittest 4958 { 4959 auto s1 = "Hello world"; 4960 skipAll(s1, 'H', 'e'); 4961 assert(s1 == "llo world"); 4962 } 4963 4964 /** 4965 Interval option specifier for `until` (below) and others. 4966 4967 If set to `OpenRight.yes`, then the interval is open to the right 4968 (last element is not included). 4969 4970 Otherwise if set to `OpenRight.no`, then the interval is closed to the right 4971 (last element included). 4972 */ 4973 alias OpenRight = Flag!"openRight"; 4974 4975 /** 4976 Lazily iterates `range` _until the element `e` for which 4977 `pred(e, sentinel)` is true. 4978 4979 This is similar to `takeWhile` in other languages. 4980 4981 Params: 4982 pred = Predicate to determine when to stop. 4983 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 4984 to iterate over. 4985 sentinel = The element to stop at. 4986 openRight = Determines whether the element for which the given predicate is 4987 true should be included in the resulting range (`No.openRight`), or 4988 not (`Yes.openRight`). 4989 4990 Returns: 4991 An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) that 4992 iterates over the original range's elements, but ends when the specified 4993 predicate becomes true. If the original range is a 4994 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) or 4995 higher, this range will be a forward range. 4996 */ 4997 Until!(pred, Range, Sentinel) 4998 until(alias pred = "a == b", Range, Sentinel) 4999 (Range range, Sentinel sentinel, OpenRight openRight = Yes.openRight) 5000 if (!is(Sentinel == OpenRight)) 5001 { 5002 return typeof(return)(range, sentinel, openRight); 5003 } 5004 5005 /// Ditto 5006 Until!(pred, Range, void) 5007 until(alias pred, Range) 5008 (Range range, OpenRight openRight = Yes.openRight) 5009 { 5010 return typeof(return)(range, openRight); 5011 } 5012 5013 /// ditto 5014 struct Until(alias pred, Range, Sentinel) 5015 if (isInputRange!Range) 5016 { 5017 private Range _input; 5018 static if (!is(Sentinel == void)) 5019 private Sentinel _sentinel; 5020 private OpenRight _openRight; 5021 private bool _done; 5022 5023 static if (!is(Sentinel == void)) 5024 { 5025 /// 5026 this(Range input, Sentinel sentinel, 5027 OpenRight openRight = Yes.openRight) 5028 { 5029 _input = input; 5030 _sentinel = sentinel; 5031 _openRight = openRight; 5032 _done = _input.empty || openRight && predSatisfied(); 5033 } 5034 private this(Range input, Sentinel sentinel, OpenRight openRight, 5035 bool done) 5036 { 5037 _input = input; 5038 _sentinel = sentinel; 5039 _openRight = openRight; 5040 _done = done; 5041 } 5042 } 5043 else 5044 { 5045 /// 5046 this(Range input, OpenRight openRight = Yes.openRight) 5047 { 5048 _input = input; 5049 _openRight = openRight; 5050 _done = _input.empty || openRight && predSatisfied(); 5051 } 5052 private this(Range input, OpenRight openRight, bool done) 5053 { 5054 _input = input; 5055 _openRight = openRight; 5056 _done = done; 5057 } 5058 } 5059 5060 /// 5061 @property bool empty() 5062 { 5063 return _done; 5064 } 5065 5066 /// 5067 @property auto ref front() 5068 { 5069 assert(!empty, "Can not get the front of an empty Until"); 5070 return _input.front; 5071 } 5072 5073 private bool predSatisfied() 5074 { 5075 static if (is(Sentinel == void)) 5076 return cast(bool) unaryFun!pred(_input.front); 5077 else 5078 return cast(bool) startsWith!pred(_input, _sentinel); 5079 } 5080 5081 /// 5082 void popFront() 5083 { 5084 assert(!empty, "Can not popFront of an empty Until"); 5085 if (!_openRight) 5086 { 5087 _done = predSatisfied(); 5088 _input.popFront(); 5089 _done = _done || _input.empty; 5090 } 5091 else 5092 { 5093 _input.popFront(); 5094 _done = _input.empty || predSatisfied(); 5095 } 5096 } 5097 5098 static if (isForwardRange!Range) 5099 { 5100 /// 5101 @property Until save() 5102 { 5103 static if (is(Sentinel == void)) 5104 return Until(_input.save, _openRight, _done); 5105 else 5106 return Until(_input.save, _sentinel, _openRight, _done); 5107 } 5108 } 5109 } 5110 5111 /// 5112 @safe unittest 5113 { 5114 import std.algorithm.comparison : equal; 5115 import std.typecons : No; 5116 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5]; 5117 assert(equal(a.until(7), [1, 2, 4])); 5118 assert(equal(a.until(7, No.openRight), [1, 2, 4, 7])); 5119 } 5120 5121 @safe unittest 5122 { 5123 import std.algorithm.comparison : equal; 5124 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5]; 5125 5126 static assert(isForwardRange!(typeof(a.until(7)))); 5127 static assert(isForwardRange!(typeof(until!"a == 2"(a, No.openRight)))); 5128 5129 assert(equal(a.until(7), [1, 2, 4])); 5130 assert(equal(a.until([7, 2]), [1, 2, 4, 7])); 5131 assert(equal(a.until(7, No.openRight), [1, 2, 4, 7])); 5132 assert(equal(until!"a == 2"(a, No.openRight), [1, 2])); 5133 } 5134 5135 // https://issues.dlang.org/show_bug.cgi?id=13171 5136 @system unittest 5137 { 5138 import std.algorithm.comparison : equal; 5139 import std.range; 5140 auto a = [1, 2, 3, 4]; 5141 assert(equal(refRange(&a).until(3, No.openRight), [1, 2, 3])); 5142 assert(a == [4]); 5143 } 5144 5145 // https://issues.dlang.org/show_bug.cgi?id=10460 5146 @safe unittest 5147 { 5148 import std.algorithm.comparison : equal; 5149 auto a = [1, 2, 3, 4]; 5150 foreach (ref e; a.until(3)) 5151 e = 0; 5152 assert(equal(a, [0, 0, 3, 4])); 5153 } 5154 5155 // https://issues.dlang.org/show_bug.cgi?id=13124 5156 @safe unittest 5157 { 5158 import std.algorithm.comparison : among, equal; 5159 auto s = "hello how\nare you"; 5160 assert(equal(s.until!(c => c.among!('\n', '\r')), "hello how")); 5161 } 5162 5163 // https://issues.dlang.org/show_bug.cgi?id=18657 5164 pure @safe unittest 5165 { 5166 import std.algorithm.comparison : equal; 5167 import std.range : refRange; 5168 { 5169 string s = "foobar"; 5170 auto r = refRange(&s).until("bar"); 5171 assert(equal(r.save, "foo")); 5172 assert(equal(r.save, "foo")); 5173 } 5174 { 5175 string s = "foobar"; 5176 auto r = refRange(&s).until!(e => e == 'b'); 5177 assert(equal(r.save, "foo")); 5178 assert(equal(r.save, "foo")); 5179 } 5180 }