1 // Written in the D programming language.
3 This is a submodule of $(MREF std, algorithm).
4 It contains generic searching algorithms.
6 $(SCRIPT inhibitQuickIndex = 1;)
7 $(BOOKTABLE Cheat Sheet,
8 $(TR $(TH Function Name) $(TH Description))
10 `all!"a > 0"([1, 2, 3, 4])` returns `true` because all elements
13 `any!"a > 0"([1, 2, -3, -4])` returns `true` because at least one
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).)
23 `canFind("hello world", "or")` returns `true`.)
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`.)
29 `countUntil(a, b)` returns the number of steps taken in `a` to
30 reach `b`; for example, `countUntil("hello!", "o")` returns
33 `commonPrefix("parakeet", "parachute")` returns `"para"`.)
35 `endsWith("rocks", "ks")` returns `true`.)
37 `find("hello world", "or")` returns `"orld"` using linear search.
38 (For binary search refer to $(REF SortedRange, std,range).))
40 `findAdjacent([1, 2, 3, 3, 4])` returns the subrange starting with
41 two equal adjacent elements, i.e. `[3, 3, 4]`.)
43 `findAmong("abcd", "qcx")` returns `"cd"` because `'c'` is
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`.)
50 `findSplit("abcdefg", "de")` returns a tuple of three ranges `"abc"`,
53 `findSplitAfter("abcdefg", "de")` returns a tuple of two ranges `"abcde"`
56 `findSplitBefore("abcdefg", "de")` returns a tuple of two ranges `"abc"`
59 `minCount([2, 1, 1, 4, 1])` returns `tuple(1, 3)`.)
61 `maxCount([2, 4, 1, 4, 1])` returns `tuple(4, 2)`.)
63 Selects the minimal element of a range.
64 `minElement([3, 4, 1, 2])` returns `1`.)
66 Selects the maximal element of a range.
67 `maxElement([3, 4, 1, 2])` returns `4`.)
69 Index of the minimal element of a range.
70 `minIndex([3, 4, 1, 2])` returns `2`.)
72 Index of the maximal element of a range.
73 `maxIndex([3, 4, 1, 2])` returns `1`.)
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
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
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`.)
87 `startsWith("hello, world", "hello")` returns `true`.)
89 Lazily iterates a range until a specific value is found.)
92 Copyright: Andrei Alexandrescu 2008-.
94 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
96 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
98 Source: $(PHOBOSSRC std/algorithm/searching.d)
101 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
103 module std.algorithm.searching;
105 import std.functional : unaryFun, binaryFun;
106 import std.meta : allSatisfy;
107 import std.range.primitives;
109 import std.typecons : Tuple, Flag, Yes, No, tuple;
112 Checks if $(I _all) of the elements satisfy `pred`.
114 template all(alias pred = "a")
117 Returns `true` if and only if the input range `range` is empty
118 or $(I _all) values found in `range` satisfy the predicate `pred`.
119 Performs (at most) $(BIGOH range.length) evaluations of `pred`.
121 bool all(Range)(Range range)
122 if (isInputRange!Range)
124 static assert(is(typeof(unaryFun!pred(range.front))),
125 "`" ~ pred.stringof[1..$-1] ~ "` isn't a unary predicate function for range.front");
126 import std.functional : not;
128 return find!(not!(unaryFun!pred))(range).empty;
135 assert( all!"a & 1"([1, 3, 5, 7, 9]));
136 assert(!all!"a & 1"([1, 2, 3, 5, 7, 9]));
140 `all` can also be used without a predicate, if its items can be
141 evaluated to true or false in a conditional statement. This can be a
142 convenient way to quickly evaluate that $(I _all) of the elements of a range
147 int[3] vals = [5, 3, 18];
148 assert( all(vals[]));
154 assert(all!(a => a > x)([2, 3]));
155 assert(all!"a == 0x00c9"("\xc3\x89")); // Test that `all` auto-decodes.
159 Checks if $(I _any) of the elements satisfies `pred`.
160 `!any` can be used to verify that $(I none) of the elements satisfy
162 This is sometimes called `exists` in other languages.
164 template any(alias pred = "a")
167 Returns `true` if and only if the input range `range` is non-empty
168 and $(I _any) value found in `range` satisfies the predicate
170 Performs (at most) $(BIGOH range.length) evaluations of `pred`.
172 bool any(Range)(Range range)
173 if (isInputRange!Range && is(typeof(unaryFun!pred(range.front))))
175 return !find!pred(range).empty;
182 import std.ascii : isWhite;
183 assert( all!(any!isWhite)(["a a", "b b"]));
184 assert(!any!(all!isWhite)(["a a", "b b"]));
188 `any` can also be used without a predicate, if its items can be
189 evaluated to true or false in a conditional statement. `!any` can be a
190 convenient way to quickly test that $(I none) of the elements of a range
195 int[3] vals1 = [0, 0, 0];
196 assert(!any(vals1[])); //none of vals1 evaluate to true
198 int[3] vals2 = [2, 0, 2];
199 assert( any(vals2[]));
200 assert(!all(vals2[]));
202 int[3] vals3 = [3, 3, 3];
203 assert( any(vals3[]));
204 assert( all(vals3[]));
209 auto a = [ 1, 2, 0, 4 ];
210 assert(any!"a == 2"(a));
211 assert(any!"a == 0x3000"("\xe3\x80\x80")); // Test that `any` auto-decodes.
216 Checks whether `r` has "balanced parentheses", i.e. all instances
217 of `lPar` are closed by corresponding instances of `rPar`. The
218 parameter `maxNestingLevel` controls the nesting level allowed. The
219 most common uses are the default or `0`. In the latter case, no
223 r = The range to check.
224 lPar = The element corresponding with a left (opening) parenthesis.
225 rPar = The element corresponding with a right (closing) parenthesis.
226 maxNestingLevel = The maximum allowed nesting level.
229 true if the given range has balanced parenthesis within the given maximum
230 nesting level; false otherwise.
232 bool balancedParens(Range, E)(Range r, E lPar, E rPar,
233 size_t maxNestingLevel = size_t.max)
234 if (isInputRange!(Range) && is(typeof(r.front == lPar)))
238 static if (is(immutable ElementEncodingType!Range == immutable E) && isNarrowString!Range)
240 import std.utf : byCodeUnit;
241 auto rn = r.byCodeUnit;
248 for (; !rn.empty; rn.popFront())
250 if (rn.front == lPar)
252 if (count > maxNestingLevel) return false;
255 else if (rn.front == rPar)
257 if (!count) return false;
267 auto s = "1 + (2 * (3 + 1 / 2)";
268 assert(!balancedParens(s, '(', ')'));
269 s = "1 + (2 * (3 + 1) / 2)";
270 assert(balancedParens(s, '(', ')'));
271 s = "1 + (2 * (3 + 1) / 2)";
272 assert(!balancedParens(s, '(', ')', 0));
273 s = "1 + (2 * 3 + 1) / (2 - 5)";
274 assert(balancedParens(s, '(', ')', 0));
275 s = "f(x) = ⌈x⌉";
276 assert(balancedParens(s, '⌈', '⌉'));
280 * Sets up Boyer-Moore matching for use with `find` below.
281 * By default, elements are compared for equality.
283 * `BoyerMooreFinder` allocates GC memory.
286 * pred = Predicate used to compare elements.
287 * needle = A random-access range with length and slicing.
290 * An instance of `BoyerMooreFinder` that can be used with `find()` to
291 * invoke the Boyer-Moore matching algorithm for finding of `needle` in a
294 struct BoyerMooreFinder(alias pred, Range)
297 size_t[] skip; // GC allocated
298 ptrdiff_t[ElementType!(Range)] occ; // GC allocated
301 ptrdiff_t occurrence(ElementType!(Range) c) scope
308 This helper function checks whether the last "portion" bytes of
309 "needle" (which is "nlen" bytes long) exist within the "needle" at
310 offset "offset" (counted from the end of the string), and whether the
311 character preceding "offset" is not a match. Notice that the range
312 being checked may reach beyond the beginning of the string. Such range
315 static bool needlematch(R)(R needle,
316 size_t portion, size_t offset)
318 import std.algorithm.comparison : equal;
319 ptrdiff_t virtual_begin = needle.length - offset - portion;
320 ptrdiff_t ignore = 0;
321 if (virtual_begin < 0)
323 ignore = -virtual_begin;
326 if (virtual_begin > 0
327 && needle[virtual_begin - 1] == needle[$ - portion - 1])
330 immutable delta = portion - ignore;
331 return equal(needle[needle.length - delta .. needle.length],
332 needle[virtual_begin .. virtual_begin + delta]);
339 if (!needle.length) return;
340 this.needle = needle;
341 /* Populate table with the analysis of the needle */
342 /* But ignoring the last letter */
343 foreach (i, n ; needle[0 .. $ - 1])
347 /* Preprocess #2: init skip[] */
348 /* Note: This step could be made a lot faster.
349 * A simple implementation is shown here. */
350 this.skip = new size_t[needle.length];
351 foreach (a; 0 .. needle.length)
354 while (value < needle.length
355 && !needlematch(needle, a, value))
359 this.skip[needle.length - a - 1] = value;
364 Range beFound(Range haystack) scope
366 import std.algorithm.comparison : max;
368 if (!needle.length) return haystack;
369 if (needle.length > haystack.length) return haystack[$ .. $];
371 immutable limit = haystack.length - needle.length;
372 for (size_t hpos = 0; hpos <= limit; )
374 size_t npos = needle.length - 1;
375 while (pred(needle[npos], haystack[npos+hpos]))
377 if (npos == 0) return haystack[hpos .. $];
380 hpos += max(skip[npos], cast(ptrdiff_t) npos - occurrence(haystack[npos+hpos]));
382 return haystack[$ .. $];
386 @property size_t length()
388 return needle.length;
392 alias opDollar = length;
396 BoyerMooreFinder!(binaryFun!(pred), Range) boyerMooreFinder
397 (alias pred = "a == b", Range)
399 if ((isRandomAccessRange!(Range) && hasSlicing!Range) || isSomeString!Range)
401 return typeof(return)(needle);
405 @safe pure nothrow unittest
407 auto bmFinder = boyerMooreFinder("TG");
409 string r = "TAGTGCCTGA";
410 // search for the first match in the haystack r
411 r = bmFinder.beFound(r);
412 assert(r == "TGCCTGA");
414 // continue search in haystack
415 r = bmFinder.beFound(r[2 .. $]);
420 Returns the common prefix of two ranges.
423 pred = The predicate to use in comparing elements for commonality. Defaults
424 to equality `"a == b"`.
426 r1 = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) of
429 r2 = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of
433 A slice of `r1` which contains the characters that both ranges start with,
434 if the first argument is a string; otherwise, the same as the result of
435 `takeExactly(r1, n)`, where `n` is the number of elements in the common
436 prefix of both ranges.
439 $(REF takeExactly, std,range)
441 auto commonPrefix(alias pred = "a == b", R1, R2)(R1 r1, R2 r2)
442 if (isForwardRange!R1 && isInputRange!R2 &&
443 !isNarrowString!R1 &&
444 is(typeof(binaryFun!pred(r1.front, r2.front))))
446 import std.algorithm.comparison : min;
447 static if (isRandomAccessRange!R1 && isRandomAccessRange!R2 &&
448 hasLength!R1 && hasLength!R2 &&
451 immutable limit = min(r1.length, r2.length);
452 foreach (i; 0 .. limit)
454 if (!binaryFun!pred(r1[i], r2[i]))
459 return r1[0 .. limit];
463 import std.range : takeExactly;
464 auto result = r1.save;
467 !r1.empty && !r2.empty && binaryFun!pred(r1.front, r2.front);
468 ++i, r1.popFront(), r2.popFront())
470 return takeExactly(result, i);
477 assert(commonPrefix("hello, world", "hello, there") == "hello, ");
481 auto commonPrefix(alias pred, R1, R2)(R1 r1, R2 r2)
482 if (isNarrowString!R1 && isInputRange!R2 &&
483 is(typeof(binaryFun!pred(r1.front, r2.front))))
485 import std.utf : decode;
487 auto result = r1.save;
488 immutable len = r1.length;
491 for (size_t j = 0; i < len && !r2.empty; r2.popFront(), i = j)
493 immutable f = decode(r1, j);
494 if (!binaryFun!pred(f, r2.front))
498 return result[0 .. i];
502 auto commonPrefix(R1, R2)(R1 r1, R2 r2)
503 if (isNarrowString!R1 && isInputRange!R2 && !isNarrowString!R2 &&
504 is(typeof(r1.front == r2.front)))
506 return commonPrefix!"a == b"(r1, r2);
510 auto commonPrefix(R1, R2)(R1 r1, R2 r2)
511 if (isNarrowString!R1 && isNarrowString!R2)
513 import std.algorithm.comparison : min;
515 static if (ElementEncodingType!R1.sizeof == ElementEncodingType!R2.sizeof)
517 import std.utf : stride, UTFException;
519 immutable limit = min(r1.length, r2.length);
520 for (size_t i = 0; i < limit;)
522 immutable codeLen = stride(r1, i);
525 for (; j < codeLen && i < limit; ++i, ++j)
528 return r1[0 .. i - j];
531 if (i == limit && j < codeLen)
532 throw new UTFException("Invalid UTF-8 sequence", i);
534 return r1[0 .. limit];
537 return commonPrefix!"a == b"(r1, r2);
542 import std.algorithm.comparison : equal;
543 import std.algorithm.iteration : filter;
544 import std.conv : to;
545 import std.exception : assertThrown;
546 import std.meta : AliasSeq;
548 import std.utf : UTFException;
550 assert(commonPrefix([1, 2, 3], [1, 2, 3, 4, 5]) == [1, 2, 3]);
551 assert(commonPrefix([1, 2, 3, 4, 5], [1, 2, 3]) == [1, 2, 3]);
552 assert(commonPrefix([1, 2, 3, 4], [1, 2, 3, 4]) == [1, 2, 3, 4]);
553 assert(commonPrefix([1, 2, 3], [7, 2, 3, 4, 5]).empty);
554 assert(commonPrefix([7, 2, 3, 4, 5], [1, 2, 3]).empty);
555 assert(commonPrefix([1, 2, 3], cast(int[]) null).empty);
556 assert(commonPrefix(cast(int[]) null, [1, 2, 3]).empty);
557 assert(commonPrefix(cast(int[]) null, cast(int[]) null).empty);
559 static foreach (S; AliasSeq!(char[], const(char)[], string,
560 wchar[], const(wchar)[], wstring,
561 dchar[], const(dchar)[], dstring))
563 static foreach (T; AliasSeq!(string, wstring, dstring))
565 assert(commonPrefix(to!S(""), to!T("")).empty);
566 assert(commonPrefix(to!S(""), to!T("hello")).empty);
567 assert(commonPrefix(to!S("hello"), to!T("")).empty);
568 assert(commonPrefix(to!S("hello, world"), to!T("hello, there")) == to!S("hello, "));
569 assert(commonPrefix(to!S("hello, there"), to!T("hello, world")) == to!S("hello, "));
570 assert(commonPrefix(to!S("hello, "), to!T("hello, world")) == to!S("hello, "));
571 assert(commonPrefix(to!S("hello, world"), to!T("hello, ")) == to!S("hello, "));
572 assert(commonPrefix(to!S("hello, world"), to!T("hello, world")) == to!S("hello, world"));
574 // https://issues.dlang.org/show_bug.cgi?id=8890
575 assert(commonPrefix(to!S("Пиво"), to!T("Пони"))== to!S("П"));
576 assert(commonPrefix(to!S("Пони"), to!T("Пиво"))== to!S("П"));
577 assert(commonPrefix(to!S("Пиво"), to!T("Пиво"))== to!S("Пиво"));
578 assert(commonPrefix(to!S("\U0010FFFF\U0010FFFB\U0010FFFE"),
579 to!T("\U0010FFFF\U0010FFFB\U0010FFFC")) == to!S("\U0010FFFF\U0010FFFB"));
580 assert(commonPrefix(to!S("\U0010FFFF\U0010FFFB\U0010FFFC"),
581 to!T("\U0010FFFF\U0010FFFB\U0010FFFE")) == to!S("\U0010FFFF\U0010FFFB"));
582 assert(commonPrefix!"a != b"(to!S("Пиво"), to!T("онво")) == to!S("Пи"));
583 assert(commonPrefix!"a != b"(to!S("онво"), to!T("Пиво")) == to!S("он"));
586 static assert(is(typeof(commonPrefix(to!S("Пиво"), filter!"true"("Пони"))) == S));
587 assert(equal(commonPrefix(to!S("Пиво"), filter!"true"("Пони")), to!S("П")));
589 static assert(is(typeof(commonPrefix(filter!"true"("Пиво"), to!S("Пони"))) ==
590 typeof(takeExactly(filter!"true"("П"), 1))));
591 assert(equal(commonPrefix(filter!"true"("Пиво"), to!S("Пони")), takeExactly(filter!"true"("П"), 1)));
594 assertThrown!UTFException(commonPrefix("\U0010FFFF\U0010FFFB", "\U0010FFFF\U0010FFFB"[0 .. $ - 1]));
596 assert(commonPrefix("12345"d, [49, 50, 51, 60, 60]) == "123"d);
597 assert(commonPrefix([49, 50, 51, 60, 60], "12345" ) == [49, 50, 51]);
598 assert(commonPrefix([49, 50, 51, 60, 60], "12345"d) == [49, 50, 51]);
600 assert(commonPrefix!"a == ('0' + b)"("12345" , [1, 2, 3, 9, 9]) == "123");
601 assert(commonPrefix!"a == ('0' + b)"("12345"d, [1, 2, 3, 9, 9]) == "123"d);
602 assert(commonPrefix!"('0' + a) == b"([1, 2, 3, 9, 9], "12345" ) == [1, 2, 3]);
603 assert(commonPrefix!"('0' + a) == b"([1, 2, 3, 9, 9], "12345"d) == [1, 2, 3]);
608 The first version counts the number of elements `x` in `r` for
609 which `pred(x, value)` is `true`. `pred` defaults to
610 equality. Performs $(BIGOH haystack.length) evaluations of `pred`.
612 The second version returns the number of times `needle` occurs in
613 `haystack`. Throws an exception if `needle.empty`, as the _count
614 of the empty range in any range would be infinite. Overlapped counts
615 are not considered, for example `count("aaa", "aa")` is `1`, not
618 The third version counts the elements for which `pred(x)` is $(D
619 true). Performs $(BIGOH haystack.length) evaluations of `pred`.
621 The fourth version counts the number of elements in a range. It is
622 an optimization for the third version: if the given range has the
623 `length` property the count is returned right away, otherwise
624 performs $(BIGOH haystack.length) to walk the range.
626 Note: Regardless of the overload, `count` will not accept
627 infinite ranges for `haystack`.
630 pred = The predicate to evaluate.
631 haystack = The range to _count.
632 needle = The element or sub-range to _count in the `haystack`.
635 The number of positions in the `haystack` for which `pred` returned true.
637 size_t count(alias pred = "a == b", Range, E)(Range haystack, E needle)
638 if (isInputRange!Range && !isInfinite!Range &&
639 is(typeof(binaryFun!pred(haystack.front, needle)) : bool))
641 bool pred2(ElementType!Range a) { return binaryFun!pred(a, needle); }
642 return count!pred2(haystack);
648 import std.uni : toLower;
650 // count elements in range
651 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
652 assert(count(a) == 9);
653 assert(count(a, 2) == 3);
654 assert(count!("a > b")(a, 2) == 5);
655 // count range in range
656 assert(count("abcadfabf", "ab") == 2);
657 assert(count("ababab", "abab") == 1);
658 assert(count("ababab", "abx") == 0);
659 // fuzzy count range in range
660 assert(count!((a, b) => toLower(a) == toLower(b))("AbcAdFaBf", "ab") == 2);
661 // count predicate in range
662 assert(count!("a > 1")(a) == 8);
667 import std.conv : text;
669 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
670 assert(count(a, 2) == 3, text(count(a, 2)));
671 assert(count!("a > b")(a, 2) == 5, text(count!("a > b")(a, 2)));
674 assert(count("日本語") == 3);
675 assert(count("日本語"w) == 3);
676 assert(count("日本語"d) == 3);
678 assert(count!("a == '日'")("日本語") == 1);
679 assert(count!("a == '本'")("日本語"w) == 1);
680 assert(count!("a == '語'")("日本語"d) == 1);
685 string s = "This is a fofofof list";
687 assert(count(s, sub) == 2);
691 size_t count(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
692 if (isForwardRange!R1 && !isInfinite!R1 &&
694 is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
696 assert(!needle.empty, "Cannot count occurrences of an empty range");
698 static if (isInfinite!R2)
700 //Note: This is the special case of looking for an infinite inside a finite...
701 //"How many instances of the Fibonacci sequence can you count in [1, 2, 3]?" - "None."
707 //Note: haystack is not saved, because findskip is designed to modify it
708 for ( ; findSkip!pred(haystack, needle.save) ; ++result)
715 size_t count(alias pred, R)(R haystack)
716 if (isInputRange!R && !isInfinite!R &&
717 is(typeof(unaryFun!pred(haystack.front)) : bool))
720 alias T = ElementType!R; //For narrow strings forces dchar iteration
721 foreach (T elem; haystack)
722 if (unaryFun!pred(elem)) ++result;
727 size_t count(R)(R haystack)
728 if (isInputRange!R && !isInfinite!R)
730 return walkLength(haystack);
735 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
736 assert(count!("a == 3")(a) == 2);
737 assert(count("日本語") == 3);
740 // https://issues.dlang.org/show_bug.cgi?id=11253
741 @safe nothrow unittest
743 assert([1, 2, 3].count([2, 3]) == 1);
747 Counts elements in the given
748 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
749 until the given predicate is true for one of the given `needles`.
752 pred = The predicate for determining when to stop counting.
754 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be
756 needles = Either a single element, or a
757 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
758 of elements, to be evaluated in turn against each
759 element in `haystack` under the given predicate.
761 Returns: The number of elements which must be popped from the front of
762 `haystack` before reaching an element for which
763 `startsWith!pred(haystack, needles)` is `true`. If
764 `startsWith!pred(haystack, needles)` is not `true` for any element in
765 `haystack`, then `-1` is returned. If only `pred` is provided,
766 `pred(haystack)` is tested for each element.
768 See_Also: $(REF indexOf, std,string)
770 ptrdiff_t countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles)
773 && isForwardRange!(Rs[0]) == isInputRange!(Rs[0])
774 && allSatisfy!(canTestStartsWith!(pred, R), Rs))
776 typeof(return) result;
778 static if (needles.length == 1)
780 static if (hasLength!R) //Note: Narrow strings don't have length.
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]);
787 return cast(typeof(return)) (len - r2.length);
791 import std.range : dropOne;
793 if (needles[0].empty)
796 //Default case, slower route doing startsWith iteration
797 for ( ; !haystack.empty ; ++result )
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))
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.
808 if (startsWith!pred(haystack.save, needles[0].save.dropOne()))
820 static if (isForwardRange!Ri)
822 if (needles[i].empty)
829 static if (!isForwardRange!Ri)
834 for (; !haystack.empty ; ++result, haystack.popFront())
838 static if (isForwardRange!Ri)
840 t[i] = needles[i].save;
843 if (startsWith!pred(haystack.save, t.expand))
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");
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))
862 bool pred2(ElementType!R a) { return binaryFun!pred(a, needle); }
863 return countUntil!pred2(haystack);
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);
883 import std.algorithm.iteration : filter;
884 import std.internal.test.dummyrange;
886 assert(countUntil("日本語", "") == 0);
887 assert(countUntil("日本語"d, "") == 0);
889 assert(countUntil("", "") == 0);
890 assert(countUntil("".filter!"true"(), "") == 0);
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);
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);
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);
917 ptrdiff_t countUntil(alias pred, R)(R haystack)
918 if (isInputRange!R &&
919 is(typeof(unaryFun!pred(haystack.front)) : bool))
922 static if (isRandomAccessRange!R)
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)
928 immutable len = cast(typeof(return)) haystack.length;
929 for ( ; i < len ; ++i )
930 if (unaryFun!pred(haystack[i])) return i;
932 else //if (isInfinite!R)
935 if (unaryFun!pred(haystack[i])) return i;
938 else static if (hasLength!R)
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);
945 else //Everything else
947 alias T = ElementType!R; //For narrow strings forces dchar iteration
948 foreach (T elem; haystack)
950 if (unaryFun!pred(elem)) return i;
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"
965 import std.ascii : isDigit;
966 import std.uni : isWhite;
968 assert(countUntil!(isWhite)("hello world") == 5);
969 assert(countUntil!(isDigit)("hello world") == -1);
970 assert(countUntil!"a > 20"([0, 7, 12, 22, 9]) == 3);
975 import std.internal.test.dummyrange;
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);
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);
996 auto r = new ReferenceInfiniteForwardRange!int(0);
997 assert(r.save.countUntil([3, 4]) == 3);
998 assert(r.save.countUntil(3) == 3);
1003 Checks if the given range ends with (one of) the given needle(s).
1004 The reciprocal of `startsWith`.
1007 pred = The predicate to use for comparing elements between the range and
1011 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
1014 withOneOfThese = The needles to check against, which may be single
1015 elements, or bidirectional ranges of elements.
1017 withThis = The single element to check.
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
1025 In the case when no needle parameters are given, return `true` iff back of
1026 `doesThisStart` fulfils predicate `pred`.
1028 uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese)
1029 if (isBidirectionalRange!Range && Needles.length > 1 &&
1030 allSatisfy!(canTestStartsWith!(pred, Range), Needles))
1032 alias haystack = doesThisEnd;
1033 alias needles = withOneOfThese;
1035 // Make one pass looking for empty ranges in needles
1036 foreach (i, Unused; Needles)
1038 // Empty range matches everything
1039 static if (!is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool))
1041 if (needles[i].empty) return i + 1;
1045 for (; !haystack.empty; haystack.popBack())
1047 foreach (i, Unused; Needles)
1049 static if (is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool))
1052 if (binaryFun!pred(haystack.back, needles[i]))
1054 // found, but continue to account for one-element
1055 // range matches (consider endsWith("ab", "b",
1056 // 'b') should return 1, not 2).
1062 if (binaryFun!pred(haystack.back, needles[i].back))
1066 // This code executed on failure to match
1067 // Out with this guy, check for the others
1068 uint result = endsWith!pred(haystack, needles[0 .. i], needles[i + 1 .. $]);
1069 if (result > i) ++result;
1073 // If execution reaches this point, then the back matches for all
1074 // needles ranges. What we need to do now is to lop off the back of
1075 // all ranges involved and recurse.
1076 foreach (i, Unused; Needles)
1078 static if (is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool))
1080 // Test has passed in the previous loop
1085 needles[i].popBack();
1086 if (needles[i].empty) return i + 1;
1094 bool endsWith(alias pred = "a == b", R1, R2)(R1 doesThisEnd, R2 withThis)
1095 if (isBidirectionalRange!R1 &&
1096 isBidirectionalRange!R2 &&
1097 is(typeof(binaryFun!pred(doesThisEnd.back, withThis.back)) : bool))
1099 alias haystack = doesThisEnd;
1100 alias needle = withThis;
1102 static if (is(typeof(pred) : string))
1103 enum isDefaultPred = pred == "a == b";
1105 enum isDefaultPred = false;
1107 static if (isDefaultPred && isArray!R1 && isArray!R2 &&
1108 is(immutable ElementEncodingType!R1 == immutable ElementEncodingType!R2))
1110 if (haystack.length < needle.length) return false;
1112 return haystack[$ - needle.length .. $] == needle;
1116 import std.range : retro;
1117 return startsWith!pred(retro(doesThisEnd), retro(withThis));
1122 bool endsWith(alias pred = "a == b", R, E)(R doesThisEnd, E withThis)
1123 if (isBidirectionalRange!R &&
1124 is(typeof(binaryFun!pred(doesThisEnd.back, withThis)) : bool))
1126 if (doesThisEnd.empty)
1129 static if (is(typeof(pred) : string))
1130 enum isDefaultPred = pred == "a == b";
1132 enum isDefaultPred = false;
1134 alias predFunc = binaryFun!pred;
1136 // auto-decoding special case
1137 static if (isNarrowString!R)
1139 // statically determine decoding is unnecessary to evaluate pred
1140 static if (isDefaultPred && isSomeChar!E && E.sizeof <= ElementEncodingType!R.sizeof)
1141 return doesThisEnd[$ - 1] == withThis;
1142 // specialize for ASCII as to not change previous behavior
1145 if (withThis <= 0x7F)
1146 return predFunc(doesThisEnd[$ - 1], withThis);
1148 return predFunc(doesThisEnd.back, withThis);
1153 return predFunc(doesThisEnd.back, withThis);
1158 bool endsWith(alias pred, R)(R doesThisEnd)
1159 if (isInputRange!R &&
1160 ifTestable!(typeof(doesThisEnd.front), unaryFun!pred))
1162 return !doesThisEnd.empty && unaryFun!pred(doesThisEnd.back);
1168 import std.ascii : isAlpha;
1169 assert("abc".endsWith!(a => a.isAlpha));
1170 assert("abc".endsWith!isAlpha);
1172 assert(!"ab1".endsWith!(a => a.isAlpha));
1174 assert(!"ab1".endsWith!isAlpha);
1175 assert(!"".endsWith!(a => a.isAlpha));
1177 import std.algorithm.comparison : among;
1178 assert("abc".endsWith!(a => a.among('c', 'd') != 0));
1179 assert(!"abc".endsWith!(a => a.among('a', 'b') != 0));
1181 assert(endsWith("abc", ""));
1182 assert(!endsWith("abc", "b"));
1183 assert(endsWith("abc", "a", 'c') == 2);
1184 assert(endsWith("abc", "c", "a") == 1);
1185 assert(endsWith("abc", "c", "c") == 1);
1186 assert(endsWith("abc", "bc", "c") == 2);
1187 assert(endsWith("abc", "x", "c", "b") == 2);
1188 assert(endsWith("abc", "x", "aa", "bc") == 3);
1189 assert(endsWith("abc", "x", "aaa", "sab") == 0);
1190 assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);
1195 import std.algorithm.iteration : filterBidirectional;
1196 import std.conv : to;
1197 import std.meta : AliasSeq;
1199 static foreach (S; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
1200 (){ // workaround slow optimizations for large functions
1201 // https://issues.dlang.org/show_bug.cgi?id=2396
1202 assert(!endsWith(to!S("abc"), 'a'));
1203 assert(endsWith(to!S("abc"), 'a', 'c') == 2);
1204 assert(!endsWith(to!S("abc"), 'x', 'n', 'b'));
1205 assert(endsWith(to!S("abc"), 'x', 'n', 'c') == 3);
1206 assert(endsWith(to!S("abc\uFF28"), 'a', '\uFF28', 'c') == 2);
1208 static foreach (T; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
1211 assert(endsWith(to!S("abc"), to!T("")));
1212 assert(!endsWith(to!S("abc"), to!T("a")));
1213 assert(!endsWith(to!S("abc"), to!T("b")));
1214 assert(endsWith(to!S("abc"), to!T("bc"), 'c') == 2);
1215 assert(endsWith(to!S("abc"), to!T("a"), "c") == 2);
1216 assert(endsWith(to!S("abc"), to!T("c"), "a") == 1);
1217 assert(endsWith(to!S("abc"), to!T("c"), "c") == 1);
1218 assert(endsWith(to!S("abc"), to!T("x"), 'c', "b") == 2);
1219 assert(endsWith(to!S("abc"), 'x', to!T("aa"), "bc") == 3);
1220 assert(endsWith(to!S("abc"), to!T("x"), "aaa", "sab") == 0);
1221 assert(endsWith(to!S("abc"), to!T("x"), "aaa", "c", "sab") == 3);
1222 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("l\uFF4co")));
1223 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("lo"), to!T("l\uFF4co")) == 2);
1226 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("l\uFF4co")));
1227 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("lo"), to!T("l\uFF4co")) == 2);
1228 assert(endsWith(to!S("日本語"), to!T("本語")));
1229 assert(endsWith(to!S("日本語"), to!T("日本語")));
1230 assert(!endsWith(to!S("本語"), to!T("日本語")));
1233 assert(endsWith(to!S(""), T.init));
1234 assert(!endsWith(to!S(""), 'a'));
1235 assert(endsWith(to!S("a"), T.init));
1236 assert(endsWith(to!S("a"), T.init, "") == 1);
1237 assert(endsWith(to!S("a"), T.init, 'a') == 1);
1238 assert(endsWith(to!S("a"), 'a', T.init) == 2);
1242 static foreach (T; AliasSeq!(int, short))
1244 immutable arr = cast(T[])[0, 1, 2, 3, 4, 5];
1247 assert(endsWith(arr, cast(int[]) null));
1248 assert(!endsWith(arr, 0));
1249 assert(!endsWith(arr, 4));
1250 assert(endsWith(arr, 5));
1251 assert(endsWith(arr, 0, 4, 5) == 3);
1252 assert(endsWith(arr, [5]));
1253 assert(endsWith(arr, [4, 5]));
1254 assert(endsWith(arr, [4, 5], 7) == 1);
1255 assert(!endsWith(arr, [2, 4, 5]));
1256 assert(endsWith(arr, [2, 4, 5], [3, 4, 5]) == 2);
1258 //Normal input range
1259 assert(!endsWith(filterBidirectional!"true"(arr), 4));
1260 assert(endsWith(filterBidirectional!"true"(arr), 5));
1261 assert(endsWith(filterBidirectional!"true"(arr), [5]));
1262 assert(endsWith(filterBidirectional!"true"(arr), [4, 5]));
1263 assert(endsWith(filterBidirectional!"true"(arr), [4, 5], 7) == 1);
1264 assert(!endsWith(filterBidirectional!"true"(arr), [2, 4, 5]));
1265 assert(endsWith(filterBidirectional!"true"(arr), [2, 4, 5], [3, 4, 5]) == 2);
1266 assert(endsWith(arr, filterBidirectional!"true"([4, 5])));
1267 assert(endsWith(arr, filterBidirectional!"true"([4, 5]), 7) == 1);
1268 assert(!endsWith(arr, filterBidirectional!"true"([2, 4, 5])));
1269 assert(endsWith(arr, [2, 4, 5], filterBidirectional!"true"([3, 4, 5])) == 2);
1272 assert(endsWith!("a%10 == b%10")(arr, [14, 15]));
1273 assert(!endsWith!("a%10 == b%10")(arr, [15, 14]));
1279 //example from issue 19727
1280 import std.path : asRelativePath;
1281 string[] ext = ["abc", "def", "ghi"];
1282 string path = "/foo/file.def";
1283 assert(ext.any!(e => path.asRelativePath("/foo").endsWith(e)) == true);
1284 assert(ext.any!(e => path.asRelativePath("/foo").startsWith(e)) == false);
1287 private enum bool hasConstEmptyMember(T) = is(typeof(((const T* a) => (*a).empty)(null)) : bool);
1289 // Rebindable doesn't work with structs
1290 // see: https://github.com/dlang/phobos/pull/6136
1291 private template RebindableOrUnqual(T)
1293 import std.typecons : Rebindable;
1294 static if (is(T == class) || is(T == interface) || isDynamicArray!T || isAssociativeArray!T)
1295 alias RebindableOrUnqual = Rebindable!T;
1297 alias RebindableOrUnqual = Unqual!T;
1301 Iterates the passed range and selects the extreme element with `less`.
1302 If the extreme element occurs multiple time, the first occurrence will be
1306 map = custom accessor for the comparison key
1307 selector = custom mapping for the extrema selection
1308 seed = custom seed to use as initial element
1309 r = Range from which the extreme value will be selected
1312 The extreme value according to `map` and `selector` of the passed-in values.
1314 private auto extremum(alias map, alias selector = "a < b", Range)(Range r)
1315 if (isInputRange!Range && !isInfinite!Range &&
1316 is(typeof(unaryFun!map(ElementType!(Range).init))))
1319 assert(!r.empty, "r is an empty range");
1323 alias Element = ElementType!Range;
1324 RebindableOrUnqual!Element seed = r.front;
1326 return extremum!(map, selector)(r, seed);
1329 private auto extremum(alias map, alias selector = "a < b", Range,
1330 RangeElementType = ElementType!Range)
1331 (Range r, RangeElementType seedElement)
1332 if (isInputRange!Range && !isInfinite!Range &&
1333 !is(CommonType!(ElementType!Range, RangeElementType) == void) &&
1334 is(typeof(unaryFun!map(ElementType!(Range).init))))
1336 alias mapFun = unaryFun!map;
1337 alias selectorFun = binaryFun!selector;
1339 alias Element = ElementType!Range;
1340 alias CommonElement = CommonType!(Element, RangeElementType);
1341 RebindableOrUnqual!CommonElement extremeElement = seedElement;
1344 // if we only have one statement in the loop, it can be optimized a lot better
1345 static if (__traits(isSame, map, a => a))
1348 // direct access via a random access range is faster
1349 static if (isRandomAccessRange!Range)
1351 foreach (const i; 0 .. r.length)
1353 if (selectorFun(r[i], extremeElement))
1355 extremeElement = r[i];
1363 if (selectorFun(r.front, extremeElement))
1365 extremeElement = r.front;
1373 alias MapType = Unqual!(typeof(mapFun(CommonElement.init)));
1374 MapType extremeElementMapped = mapFun(extremeElement);
1376 // direct access via a random access range is faster
1377 static if (isRandomAccessRange!Range)
1379 foreach (const i; 0 .. r.length)
1381 MapType mapElement = mapFun(r[i]);
1382 if (selectorFun(mapElement, extremeElementMapped))
1384 extremeElement = r[i];
1385 extremeElementMapped = mapElement;
1393 MapType mapElement = mapFun(r.front);
1394 if (selectorFun(mapElement, extremeElementMapped))
1396 extremeElement = r.front;
1397 extremeElementMapped = mapElement;
1403 return extremeElement;
1406 private auto extremum(alias selector = "a < b", Range)(Range r)
1407 if (isInputRange!Range && !isInfinite!Range &&
1408 !is(typeof(unaryFun!selector(ElementType!(Range).init))))
1410 return extremum!(a => a, selector)(r);
1413 // if we only have one statement in the loop it can be optimized a lot better
1414 private auto extremum(alias selector = "a < b", Range,
1415 RangeElementType = ElementType!Range)
1416 (Range r, RangeElementType seedElement)
1417 if (isInputRange!Range && !isInfinite!Range &&
1418 !is(CommonType!(ElementType!Range, RangeElementType) == void) &&
1419 !is(typeof(unaryFun!selector(ElementType!(Range).init))))
1421 return extremum!(a => a, selector)(r, seedElement);
1426 // allows a custom map to select the extremum
1427 assert([[0, 4], [1, 2]].extremum!"a[0]" == [0, 4]);
1428 assert([[0, 4], [1, 2]].extremum!"a[1]" == [1, 2]);
1430 // allows a custom selector for comparison
1431 assert([[0, 4], [1, 2]].extremum!("a[0]", "a > b") == [1, 2]);
1432 assert([[0, 4], [1, 2]].extremum!("a[1]", "a > b") == [0, 4]);
1434 // use a custom comparator
1435 import std.math.operations : cmp;
1436 assert([-2., 0, 5].extremum!cmp == 5.0);
1437 assert([-2., 0, 2].extremum!`cmp(a, b) < 0` == -2.0);
1440 import std.range : enumerate;
1441 assert([-3., 0, 5].enumerate.extremum!(`a.value`, cmp) == tuple(2, 5.0));
1442 assert([-2., 0, 2].enumerate.extremum!(`a.value`, `cmp(a, b) < 0`) == tuple(0, -2.0));
1444 // seed with a custom value
1446 assert(arr.extremum(1) == 1);
1449 @safe pure nothrow unittest
1453 assert(arr2d.extremum([1]) == [1]);
1455 // allow seeds of different types (implicit casting)
1456 assert(extremum([2, 3, 4], 1.5) == 1.5);
1461 import std.range : enumerate, iota;
1464 assert(iota(1, 5).extremum() == 1);
1465 assert(iota(2, 5).enumerate.extremum!"a.value" == tuple(0, 2));
1467 // should work with const
1468 const(int)[] immArr = [2, 1, 3];
1469 assert(immArr.extremum == 1);
1471 // should work with immutable
1472 immutable(int)[] immArr2 = [2, 1, 3];
1473 assert(immArr2.extremum == 1);
1476 assert(["b", "a", "c"].extremum == "a");
1478 // with all dummy ranges
1479 import std.internal.test.dummyrange;
1480 foreach (DummyType; AllDummyRanges)
1483 assert(d.extremum == 1);
1484 assert(d.extremum!(a => a) == 1);
1485 assert(d.extremum!`a > b` == 10);
1486 assert(d.extremum!(a => a, `a > b`) == 10);
1490 @nogc @safe nothrow pure unittest
1492 static immutable arr = [7, 3, 4, 2, 1, 8];
1493 assert(arr.extremum == 1);
1495 static immutable arr2d = [[1, 9], [3, 1], [4, 2]];
1496 assert(arr2d.extremum!"a[1]" == arr2d[1]);
1499 // https://issues.dlang.org/show_bug.cgi?id=17982
1505 this(int val){ this.val = val; }
1508 const(B) doStuff(const(B)[] v)
1510 return v.extremum!"a.val";
1512 assert(doStuff([new B(1), new B(0), new B(2)]).val == 0);
1514 const(B)[] arr = [new B(0), new B(1)];
1515 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
1516 assert(arr.extremum!"a.val".val == 0);
1521 Finds an individual element in an $(REF_ALTTEXT input range, isInputRange, std,range,primitives).
1522 Elements of `haystack` are compared with `needle` by using predicate
1523 `pred` with `pred(haystack.front, needle)`.
1524 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`.
1526 The predicate is passed to $(REF binaryFun, std, functional), and can either accept a
1527 string, or any callable that can be executed via `pred(element, element)`.
1529 To _find the last occurrence of `needle` in a
1530 $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives) `haystack`,
1531 call `find(retro(haystack), needle)`. See $(REF retro, std,range).
1533 If no `needle` is provided, `pred(haystack.front)` will be evaluated on each
1534 element of the input range.
1536 If `input` is a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives),
1537 `needle` can be a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) too.
1538 In this case `startsWith!pred(haystack, needle)` is evaluated on each evaluation.
1541 `find` behaves similar to `dropWhile` in other languages.
1544 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`.
1545 There are specializations that improve performance by taking
1546 advantage of $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives)
1547 or $(REF_ALTTEXT random access, isRandomAccess, std,range,primitives)
1548 ranges (where possible).
1552 pred = The predicate for comparing each element with the needle, defaulting to equality `"a == b"`.
1553 The negated predicate `"a != b"` can be used to search instead for the first
1554 element $(I not) matching the needle.
1556 haystack = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1559 needle = The element searched for.
1563 `haystack` advanced such that the front element is the one searched for;
1564 that is, until `binaryFun!pred(haystack.front, needle)` is `true`. If no
1565 such position exists, returns an empty `haystack`.
1567 See_ALso: $(LREF findAdjacent), $(LREF findAmong), $(LREF findSkip), $(LREF findSplit), $(LREF startsWith)
1569 InputRange find(alias pred = "a == b", InputRange, Element)(InputRange haystack, scope Element needle)
1570 if (isInputRange!InputRange &&
1571 is (typeof(binaryFun!pred(haystack.front, needle)) : bool) &&
1572 !is (typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
1574 alias R = InputRange;
1576 alias predFun = binaryFun!pred;
1577 static if (is(typeof(pred == "a == b")))
1578 enum isDefaultPred = pred == "a == b";
1580 enum isDefaultPred = false;
1581 enum isIntegralNeedle = isSomeChar!E || isIntegral!E || isBoolean!E;
1583 alias EType = ElementType!R;
1585 // If the haystack is a SortedRange we can use binary search to find the needle.
1586 // Works only for the default find predicate and any SortedRange predicate.
1587 // https://issues.dlang.org/show_bug.cgi?id=8829
1588 import std.range : SortedRange;
1589 static if (is(InputRange : SortedRange!TT, TT) && isDefaultPred)
1591 auto lb = haystack.lowerBound(needle);
1592 if (lb.length == haystack.length || haystack[lb.length] != needle)
1593 return haystack[$ .. $];
1595 return haystack[lb.length .. $];
1597 else static if (isNarrowString!R)
1599 alias EEType = ElementEncodingType!R;
1600 alias UEEType = Unqual!EEType;
1602 //These are two special cases which can search without decoding the UTF stream.
1603 static if (isDefaultPred && isIntegralNeedle)
1605 import std.utf : canSearchInCodeUnits;
1607 //This special case deals with UTF8 search, when the needle
1608 //is represented by a single code point.
1609 //Note: "needle <= 0x7F" properly handles sign via unsigned promotion
1610 static if (is(UEEType == char))
1612 if (!__ctfe && canSearchInCodeUnits!char(needle))
1614 static inout(R) trustedMemchr(ref return scope inout(R) haystack,
1615 ref const scope E needle) @trusted nothrow pure
1617 import core.stdc.string : memchr;
1618 auto ptr = memchr(haystack.ptr, needle, haystack.length);
1620 haystack[cast(char*) ptr - haystack.ptr .. $] :
1623 return trustedMemchr(haystack, needle);
1627 //Ditto, but for UTF16
1628 static if (is(UEEType == wchar))
1630 if (canSearchInCodeUnits!wchar(needle))
1632 foreach (i, ref EEType e; haystack)
1635 return haystack[i .. $];
1637 return haystack[$ .. $];
1642 //Previous conditional optimizations did not succeed. Fallback to
1643 //unconditional implementations
1644 static if (isDefaultPred)
1646 import std.utf : encode;
1648 //In case of default pred, it is faster to do string/string search.
1649 UEEType[is(UEEType == char) ? 4 : 2] buf;
1651 size_t len = encode(buf, needle);
1652 return find(haystack, buf[0 .. len]);
1656 import std.utf : decode;
1658 //Explicit pred: we must test each character by the book.
1659 //We choose a manual decoding approach, because it is faster than
1660 //the built-in foreach, or doing a front/popFront for-loop.
1661 immutable len = haystack.length;
1662 size_t i = 0, next = 0;
1665 if (predFun(decode(haystack, next), needle))
1666 return haystack[i .. $];
1669 return haystack[$ .. $];
1672 else static if (isArray!R)
1674 // https://issues.dlang.org/show_bug.cgi?id=10403 optimization
1675 static if (isDefaultPred && isIntegral!EType && EType.sizeof == 1 && isIntegralNeedle)
1677 import std.algorithm.comparison : max, min;
1679 R findHelper(return scope ref R haystack, ref E needle) @trusted nothrow pure
1681 import core.stdc.string : memchr;
1684 //Note: we use "min/max" to handle sign mismatch.
1685 if (min(EType.min, needle) == EType.min &&
1686 max(EType.max, needle) == EType.max)
1688 ptr = cast(EType*) memchr(haystack.ptr, needle,
1693 haystack[ptr - haystack.ptr .. $] :
1698 return findHelper(haystack, needle);
1701 //Default implementation.
1702 foreach (i, ref e; haystack)
1703 if (predFun(e, needle))
1704 return haystack[i .. $];
1705 return haystack[$ .. $];
1709 //Everything else. Walk.
1710 for ( ; !haystack.empty; haystack.popFront() )
1712 if (predFun(haystack.front, needle))
1722 import std.range.primitives;
1724 auto arr = [1, 2, 4, 4, 4, 4, 5, 6, 9];
1725 assert(arr.find(4) == [4, 4, 4, 4, 5, 6, 9]);
1726 assert(arr.find(1) == arr);
1727 assert(arr.find(9) == [9]);
1728 assert(arr.find!((a, b) => a > b)(4) == [5, 6, 9]);
1729 assert(arr.find!((a, b) => a < b)(4) == arr);
1730 assert(arr.find(0).empty);
1731 assert(arr.find(10).empty);
1732 assert(arr.find(8).empty);
1734 assert(find("hello, world", ',') == ", world");
1737 /// Case-insensitive find of a string
1740 import std.range.primitives;
1741 import std.uni : toLower;
1743 string[] s = ["Hello", "world", "!"];
1744 assert(s.find!((a, b) => toLower(a) == b)("hello") == s);
1749 import std.algorithm.comparison : equal;
1750 import std.container : SList;
1752 auto lst = SList!int(1, 2, 5, 7, 3);
1753 assert(lst.front == 1);
1754 auto r = find(lst[], 5);
1755 assert(equal(r, SList!int(5, 7, 3)[]));
1756 assert(find([1, 2, 3, 5], 4).empty);
1757 assert(equal(find!"a > b"("hello", 'k'), "llo"));
1760 @safe pure nothrow unittest
1762 assert(!find ([1, 2, 3], 2).empty);
1763 assert(!find!((a,b)=>a == b)([1, 2, 3], 2).empty);
1764 assert(!find ([1, 2, 3], 2).empty);
1765 assert(!find!((a,b)=>a == b)([1, 2, 3], 2).empty);
1770 import std.meta : AliasSeq;
1771 static foreach (R; AliasSeq!(string, wstring, dstring))
1773 static foreach (E; AliasSeq!(char, wchar, dchar))
1775 assert(find ("hello world", 'w') == "world");
1776 assert(find!((a,b)=>a == b)("hello world", 'w') == "world");
1777 assert(find ("日c語", 'c') == "c語");
1778 assert(find!((a,b)=>a == b)("日c語", 'c') == "c語");
1779 assert(find ("0123456789", 'A').empty);
1780 static if (E.sizeof >= 2)
1782 assert(find ("日本語", '本') == "本語");
1783 assert(find!((a,b)=>a == b)("日本語", '本') == "本語");
1792 static assert(find("abc", 'b') == "bc");
1793 static assert(find("日b語", 'b') == "b語");
1794 static assert(find("日本語", '本') == "本語");
1795 static assert(find([1, 2, 3], 2) == [2, 3]);
1797 static assert(find ([1, 2, 3], 2));
1798 static assert(find!((a,b)=>a == b)([1, 2, 3], 2));
1799 static assert(find ([1, 2, 3], 2));
1800 static assert(find!((a,b)=>a == b)([1, 2, 3], 2));
1805 import std.exception : assertCTFEable;
1806 import std.meta : AliasSeq;
1808 void dg() @safe pure nothrow
1810 byte[] sarr = [1, 2, 3, 4];
1811 ubyte[] uarr = [1, 2, 3, 4];
1812 static foreach (arr; AliasSeq!(sarr, uarr))
1814 static foreach (T; AliasSeq!(byte, ubyte, int, uint))
1816 assert(find(arr, cast(T) 3) == arr[2 .. $]);
1817 assert(find(arr, cast(T) 9) == arr[$ .. $]);
1819 assert(find(arr, 256) == arr[$ .. $]);
1826 // https://issues.dlang.org/show_bug.cgi?id=11603
1829 enum Foo : ubyte { A }
1830 assert([Foo.A].find(Foo.A).empty == false);
1833 assert([x].find(x).empty == false);
1837 InputRange find(alias pred, InputRange)(InputRange haystack)
1838 if (isInputRange!InputRange)
1840 alias R = InputRange;
1841 alias predFun = unaryFun!pred;
1842 static if (isNarrowString!R)
1844 import std.utf : decode;
1846 immutable len = haystack.length;
1847 size_t i = 0, next = 0;
1850 if (predFun(decode(haystack, next)))
1851 return haystack[i .. $];
1854 return haystack[$ .. $];
1859 for ( ; !haystack.empty; haystack.popFront() )
1861 if (predFun(haystack.front))
1871 auto arr = [ 1, 2, 3, 4, 1 ];
1872 assert(find!("a > 2")(arr) == [ 3, 4, 1 ]);
1874 // with predicate alias
1875 bool pred(int x) { return x + 1 > 1.5; }
1876 assert(find!(pred)(arr) == arr);
1881 int[] r = [ 1, 2, 3 ];
1882 assert(find!(a=>a > 2)(r) == [3]);
1883 bool pred(int x) { return x + 1 > 1.5; }
1884 assert(find!(pred)(r) == r);
1886 assert(find!(a=>a > 'v')("hello world") == "world");
1887 assert(find!(a=>a%4 == 0)("日本語") == "本語");
1891 R1 find(alias pred = "a == b", R1, R2)(R1 haystack, scope R2 needle)
1892 if (isForwardRange!R1 && isForwardRange!R2
1893 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
1895 static if (!isRandomAccessRange!R1)
1897 static if (is(typeof(pred == "a == b")) && pred == "a == b" && isSomeString!R1 && isSomeString!R2
1898 && haystack[0].sizeof == needle[0].sizeof)
1900 // return cast(R1) find(representation(haystack), representation(needle));
1901 // Specialization for simple string search
1902 alias Representation =
1903 Select!(haystack[0].sizeof == 1, ubyte[],
1904 Select!(haystack[0].sizeof == 2, ushort[], uint[]));
1905 // Will use the array specialization
1906 static TO force(TO, T)(inout T r) @trusted { return cast(TO) r; }
1907 return force!R1(.find!(pred, Representation, Representation)
1908 (force!Representation(haystack), force!Representation(needle)));
1912 return simpleMindedFind!pred(haystack, needle);
1915 else static if (!isBidirectionalRange!R2 || !hasSlicing!R1)
1917 static if (!is(ElementType!R1 == ElementType!R2))
1919 return simpleMindedFind!pred(haystack, needle);
1923 // Prepare the search with needle's first element
1927 haystack = .find!pred(haystack, needle.front);
1929 static if (hasLength!R1 && hasLength!R2 && is(typeof(takeNone(haystack)) == R1))
1931 if (needle.length > haystack.length)
1932 return takeNone(haystack);
1941 size_t matchLen = 1;
1943 // Loop invariant: haystack[0 .. matchLen] matches everything in
1944 // the initial needle that was popped out of needle.
1947 // Extend matchLength as much as possible
1950 import std.range : takeNone;
1952 if (needle.empty || haystack.empty)
1955 static if (hasLength!R1 && is(typeof(takeNone(haystack)) == R1))
1957 if (matchLen == haystack.length)
1958 return takeNone(haystack);
1961 if (!binaryFun!pred(haystack[matchLen], needle.front))
1968 auto bestMatch = haystack[0 .. matchLen];
1969 haystack.popFront();
1970 haystack = .find!pred(haystack, bestMatch);
1974 else // static if (hasSlicing!R1 && isBidirectionalRange!R2)
1976 if (needle.empty) return haystack;
1978 static if (hasLength!R2)
1980 immutable needleLength = needle.length;
1984 immutable needleLength = walkLength(needle.save);
1986 if (needleLength > haystack.length)
1988 return haystack[haystack.length .. haystack.length];
1990 // Optimization in case the ranges are both SortedRanges.
1991 // Binary search can be used to find the first occurence
1992 // of the first element of the needle in haystack.
1993 // When it is found O(walklength(needle)) steps are performed.
1994 // https://issues.dlang.org/show_bug.cgi?id=8829 enhancement
1995 import std.algorithm.comparison : mismatch;
1996 import std.range : SortedRange;
1997 static if (is(R1 == R2)
1998 && is(R1 : SortedRange!TT, TT)
1999 && pred == "a == b")
2001 auto needleFirstElem = needle[0];
2002 auto partitions = haystack.trisect(needleFirstElem);
2003 auto firstElemLen = partitions[1].length;
2006 if (firstElemLen == 0)
2007 return haystack[$ .. $];
2009 while (needle.front() == needleFirstElem)
2014 if (count > firstElemLen)
2015 return haystack[$ .. $];
2018 auto m = mismatch(partitions[2], needle);
2021 return haystack[partitions[0].length + partitions[1].length - count .. $];
2023 else static if (isRandomAccessRange!R2)
2025 immutable lastIndex = needleLength - 1;
2026 auto last = needle[lastIndex];
2027 size_t j = lastIndex, skip = 0;
2028 for (; j < haystack.length;)
2030 if (!binaryFun!pred(haystack[j], last))
2035 immutable k = j - lastIndex;
2036 // last elements match
2037 for (size_t i = 0;; ++i)
2040 return haystack[k .. haystack.length];
2041 if (!binaryFun!pred(haystack[k + i], needle[i]))
2047 while (skip < needleLength && needle[needleLength - 1 - skip] != needle[needleLength - 1])
2058 // auto needleBack = moveBack(needle);
2059 // Stage 1: find the step
2061 auto needleBack = needle.back;
2063 for (auto i = needle.save; !i.empty && i.back != needleBack;
2064 i.popBack(), ++step)
2067 // Stage 2: linear find
2068 size_t scout = needleLength - 1;
2071 if (scout >= haystack.length)
2073 if (!binaryFun!pred(haystack[scout], needleBack))
2078 // Found a match with the last element in the needle
2079 auto cand = haystack[scout + 1 - needleLength .. haystack.length];
2080 if (startsWith!pred(cand, needle))
2088 return haystack[haystack.length .. haystack.length];
2095 import std.container : SList;
2096 import std.range.primitives : empty;
2097 import std.typecons : Tuple;
2099 assert(find("hello, world", "World").empty);
2100 assert(find("hello, world", "wo") == "world");
2101 assert([1, 2, 3, 4].find(SList!int(2, 3)[]) == [2, 3, 4]);
2102 alias C = Tuple!(int, "x", int, "y");
2103 auto a = [C(1,0), C(2,0), C(3,1), C(4,0)];
2104 assert(a.find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
2105 assert(a[1 .. $].find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
2110 import std.container : SList;
2111 alias C = Tuple!(int, "x", int, "y");
2112 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)]);
2115 // https://issues.dlang.org/show_bug.cgi?id=12470
2118 import std.array : replace;
2119 inout(char)[] sanitize(inout(char)[] p)
2121 return p.replace("\0", " ");
2123 assert(sanitize("O\x00o") == "O o");
2128 import std.algorithm.comparison : equal;
2129 import std.container : SList;
2131 auto lst = SList!int(1, 2, 5, 7, 3);
2132 static assert(isForwardRange!(int[]));
2133 static assert(isForwardRange!(typeof(lst[])));
2134 auto r = find(lst[], [2, 5]);
2135 assert(equal(r, SList!int(2, 5, 7, 3)[]));
2140 import std.range : assumeSorted;
2142 auto r1 = assumeSorted([1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 8, 10]);
2143 auto r2 = assumeSorted([3, 3, 4, 5, 6, 7, 8, 8]);
2144 auto r3 = assumeSorted([3, 4, 5, 6, 7, 8]);
2145 auto r4 = assumeSorted([4, 5, 6]);
2146 auto r5 = assumeSorted([12, 13]);
2147 auto r6 = assumeSorted([8, 8, 10, 11]);
2148 auto r7 = assumeSorted([3, 3, 3, 3, 3, 3, 3]);
2150 assert(find(r1, r2) == assumeSorted([3, 3, 4, 5, 6, 7, 8, 8, 8, 10]));
2151 assert(find(r1, r3) == assumeSorted([3, 4, 5, 6, 7, 8, 8, 8, 10]));
2152 assert(find(r1, r4) == assumeSorted([4, 5, 6, 7, 8, 8, 8, 10]));
2153 assert(find(r1, r5).empty());
2154 assert(find(r1, r6).empty());
2155 assert(find(r1, r7).empty());
2160 import std.algorithm.comparison : equal;
2161 // @@@BUG@@@ removing static below makes unittest fail
2162 static struct BiRange
2165 @property bool empty() { return payload.empty; }
2166 @property BiRange save() { return this; }
2167 @property ref int front() { return payload[0]; }
2168 @property ref int back() { return payload[$ - 1]; }
2169 void popFront() { return payload.popFront(); }
2170 void popBack() { return payload.popBack(); }
2172 auto r = BiRange([1, 2, 3, 10, 11, 4]);
2173 assert(equal(find(r, [10, 11]), [10, 11, 4]));
2178 import std.container : SList;
2180 assert(find([ 1, 2, 3 ], SList!int(2, 3)[]) == [ 2, 3 ]);
2181 assert(find([ 1, 2, 1, 2, 3, 3 ], SList!int(2, 3)[]) == [ 2, 3, 3 ]);
2184 // https://issues.dlang.org/show_bug.cgi?id=8334
2187 import std.algorithm.iteration : filter;
2190 auto haystack = [1, 2, 3, 4, 1, 9, 12, 42];
2191 auto needle = [12, 42, 27];
2193 //different overload of find, but it's the base case.
2194 assert(find(haystack, needle).empty);
2196 assert(find(haystack, takeExactly(filter!"true"(needle), 3)).empty);
2197 assert(find(haystack, filter!"true"(needle)).empty);
2200 // https://issues.dlang.org/show_bug.cgi?id=11013
2203 assert(find!"a == a"("abc","abc") == "abc");
2206 // Internally used by some find() overloads above
2207 private R1 simpleMindedFind(alias pred, R1, R2)(R1 haystack, scope R2 needle)
2209 enum estimateNeedleLength = hasLength!R1 && !hasLength!R2;
2211 static if (hasLength!R1)
2213 static if (!hasLength!R2)
2214 size_t estimatedNeedleLength = 0;
2216 immutable size_t estimatedNeedleLength = needle.length;
2219 bool haystackTooShort()
2221 static if (estimateNeedleLength)
2223 return haystack.length < estimatedNeedleLength;
2227 return haystack.empty;
2232 for (;; haystack.popFront())
2234 if (haystackTooShort())
2237 static if (hasLength!R1)
2239 static if (is(typeof(haystack[haystack.length ..
2240 haystack.length]) : R1))
2241 return haystack[haystack.length .. haystack.length];
2247 assert(haystack.empty, "Haystack must be empty by now");
2251 static if (estimateNeedleLength)
2252 size_t matchLength = 0;
2253 for (auto h = haystack.save, n = needle.save;
2255 h.popFront(), n.popFront())
2257 if (h.empty || !binaryFun!pred(h.front, n.front))
2259 // Failed searching n in h
2260 static if (estimateNeedleLength)
2262 if (estimatedNeedleLength < matchLength)
2263 estimatedNeedleLength = matchLength;
2267 static if (estimateNeedleLength)
2277 // Test simpleMindedFind for the case where both haystack and needle have
2284 // This is what triggers issue 7992.
2285 @property size_t length() const { return _impl.length; }
2286 @property void length(size_t len) { _impl.length = len; }
2288 // This is for conformance to the forward range API (we deliberately
2289 // make it non-random access so that we will end up in
2290 // simpleMindedFind).
2291 @property bool empty() const { return _impl.empty; }
2292 @property dchar front() const { return _impl.front; }
2293 void popFront() { _impl.popFront(); }
2294 @property CustomString save() { return this; }
2297 // If issue 7992 occurs, this will throw an exception from calling
2298 // popFront() on an empty range.
2299 auto r = find(CustomString("a"), CustomString("b"));
2304 Finds two or more `needles` into a `haystack`. The predicate $(D
2305 pred) is used throughout to compare elements. By default, elements are
2306 compared for equality.
2310 pred = The predicate to use for comparing elements.
2312 haystack = The target of the search. Must be an input range.
2313 If any of `needles` is a range with elements comparable to
2314 elements in `haystack`, then `haystack` must be a
2315 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2316 such that the search can backtrack.
2318 needles = One or more items to search for. Each of `needles` must
2319 be either comparable to one element in `haystack`, or be itself a
2320 forward range with elements comparable with elements in
2325 A tuple containing `haystack` positioned to match one of the
2326 needles and also the 1-based index of the matching element in $(D
2327 needles) (0 if none of `needles` matched, 1 if `needles[0]`
2328 matched, 2 if `needles[1]` matched...). The first needle to be found
2329 will be the one that matches. If multiple needles are found at the
2330 same spot in the range, then the shortest one is the one which matches
2331 (if multiple needles of the same length are found at the same spot (e.g
2332 `"a"` and `'a'`), then the left-most of them in the argument list
2335 The relationship between `haystack` and `needles` simply means
2336 that one can e.g. search for individual `int`s or arrays of $(D
2337 int)s in an array of `int`s. In addition, if elements are
2338 individually comparable, searches of heterogeneous types are allowed
2339 as well: a `double[]` can be searched for an `int` or a $(D
2340 short[]), and conversely a `long` can be searched for a `float`
2341 or a `double[]`. This makes for efficient searches without the need
2342 to coerce one side of the comparison into the other's side type.
2344 The complexity of the search is $(BIGOH haystack.length *
2345 max(needles.length)). (For needles that are individual items, length
2346 is considered to be 1.) The strategy used in searching several
2347 subranges at once maximizes cache usage by moving in `haystack` as
2348 few times as possible.
2350 Tuple!(Range, size_t) find(alias pred = "a == b", Range, Ranges...)
2351 (Range haystack, Ranges needles)
2352 if (Ranges.length > 1 && is(typeof(startsWith!pred(haystack, needles))))
2354 for (;; haystack.popFront())
2356 size_t r = startsWith!pred(haystack, needles);
2357 if (r || haystack.empty)
2359 return tuple(haystack, r);
2367 import std.typecons : tuple;
2368 int[] a = [ 1, 4, 2, 3 ];
2369 assert(find(a, 4) == [ 4, 2, 3 ]);
2370 assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]);
2371 assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2));
2372 // Mixed types allowed if comparable
2373 assert(find(a, 5, [ 1.2, 3.5 ], 2.0) == tuple([ 2, 3 ], 3));
2378 auto s1 = "Mary has a little lamb";
2379 assert(find(s1, "has a", "has an") == tuple("has a little lamb", 1));
2380 assert(find(s1, 't', "has a", "has an") == tuple("has a little lamb", 2));
2381 assert(find(s1, 't', "has a", 'y', "has an") == tuple("y has a little lamb", 3));
2382 assert(find("abc", "bc").length == 2);
2387 import std.algorithm.internal : rndstuff;
2388 import std.meta : AliasSeq;
2389 import std.uni : toUpper;
2391 int[] a = [ 1, 2, 3 ];
2392 assert(find(a, 5).empty);
2393 assert(find(a, 2) == [2, 3]);
2395 foreach (T; AliasSeq!(int, double))
2397 auto b = rndstuff!(T)();
2398 if (!b.length) continue;
2401 assert(find(b, 200).length == b.length - b.length / 4);
2404 // Case-insensitive find of a string
2405 string[] s = [ "Hello", "world", "!" ];
2406 assert(find!("toUpper(a) == toUpper(b)")(s, "hello").length == 3);
2408 static bool f(string a, string b) { return toUpper(a) == toUpper(b); }
2409 assert(find!(f)(s, "hello").length == 3);
2414 import std.algorithm.comparison : equal;
2415 import std.algorithm.internal : rndstuff;
2416 import std.meta : AliasSeq;
2417 import std.range : retro;
2419 int[] a = [ 1, 2, 3, 2, 6 ];
2420 assert(find(retro(a), 5).empty);
2421 assert(equal(find(retro(a), 2), [ 2, 3, 2, 1 ][]));
2423 foreach (T; AliasSeq!(int, double))
2425 auto b = rndstuff!(T)();
2426 if (!b.length) continue;
2429 assert(find(retro(b), 200).length ==
2430 b.length - (b.length - 1) / 2);
2436 import std.algorithm.comparison : equal;
2437 import std.internal.test.dummyrange;
2439 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2440 int[] b = [ 1, 2, 3 ];
2441 assert(find(a, b) == [ 1, 2, 3, 4, 5 ]);
2442 assert(find(b, a).empty);
2444 foreach (DummyType; AllDummyRanges)
2447 auto findRes = find(d, 5);
2448 assert(equal(findRes, [5,6,7,8,9,10]));
2453 * Finds `needle` in `haystack` efficiently using the
2454 * $(LINK2 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm,
2455 * Boyer-Moore) method.
2458 * haystack = A random-access range with length and slicing.
2459 * needle = A $(LREF BoyerMooreFinder).
2462 * `haystack` advanced such that `needle` is a prefix of it (if no
2463 * such position exists, returns `haystack` advanced to termination).
2465 RandomAccessRange find(RandomAccessRange, alias pred, InputRange)(
2466 RandomAccessRange haystack, scope BoyerMooreFinder!(pred, InputRange) needle)
2468 return needle.beFound(haystack);
2473 string h = "/homes/aalexand/d/dmd/bin/../lib/libphobos.a(dmain2.o)"~
2474 "(.gnu.linkonce.tmain+0x74): In function `main' undefined reference"~
2476 string[] ns = ["libphobos", "function", " undefined", "`", ":"];
2479 auto p = find(h, boyerMooreFinder(n));
2487 import std.range.primitives : empty;
2488 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2489 int[] b = [ 1, 2, 3 ];
2491 assert(find(a, boyerMooreFinder(b)) == [ 1, 2, 3, 4, 5 ]);
2492 assert(find(b, boyerMooreFinder(a)).empty);
2497 auto bm = boyerMooreFinder("for");
2498 auto match = find("Moor", bm);
2499 assert(match.empty);
2504 Convenience function. Like find, but only returns whether or not the search
2508 $(REF among, std,algorithm,comparison) for checking a value against multiple possibilities.
2510 template canFind(alias pred="a == b")
2513 Returns `true` if and only if any value `v` found in the
2514 input range `range` satisfies the predicate `pred`.
2515 Performs (at most) $(BIGOH haystack.length) evaluations of `pred`.
2517 bool canFind(Range)(Range haystack)
2518 if (is(typeof(find!pred(haystack))))
2520 return any!pred(haystack);
2524 Returns `true` if and only if `needle` can be found in $(D
2525 range). Performs $(BIGOH haystack.length) evaluations of `pred`.
2527 bool canFind(Range, Element)(Range haystack, scope Element needle)
2528 if (is(typeof(find!pred(haystack, needle))))
2530 return !find!pred(haystack, needle).empty;
2534 Returns the 1-based index of the first needle found in `haystack`. If no
2535 needle is found, then `0` is returned.
2537 So, if used directly in the condition of an if statement or loop, the result
2538 will be `true` if one of the needles is found and `false` if none are
2539 found, whereas if the result is used elsewhere, it can either be cast to
2540 `bool` for the same effect or used to get which needle was found first
2541 without having to deal with the tuple that `LREF find` returns for the
2544 size_t canFind(Range, Ranges...)(Range haystack, scope Ranges needles)
2545 if (Ranges.length > 1 &&
2546 allSatisfy!(isForwardRange, Ranges) &&
2547 is(typeof(find!pred(haystack, needles))))
2549 return find!pred(haystack, needles)[1];
2556 assert(canFind([0, 1, 2, 3], 2) == true);
2557 assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]));
2558 assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]) == 1);
2559 assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]));
2560 assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]) == 2);
2562 assert(canFind([0, 1, 2, 3], 4) == false);
2563 assert(!canFind([0, 1, 2, 3], [1, 3], [2, 4]));
2564 assert(canFind([0, 1, 2, 3], [1, 3], [2, 4]) == 0);
2568 * Example using a custom predicate.
2569 * Note that the needle appears as the second argument of the predicate.
2578 assert(!canFind(words, "bees"));
2579 assert( canFind!((string a, string b) => a.startsWith(b))(words, "bees"));
2582 /// Search for mutliple items in an array of items (search for needles in an array of hay stacks)
2585 string s1 = "aaa111aaa";
2586 string s2 = "aaa222aaa";
2587 string s3 = "aaa333aaa";
2588 string s4 = "aaa444aaa";
2589 const hay = [s1, s2, s3, s4];
2590 assert(hay.canFind!(e => (e.canFind("111", "222"))));
2595 import std.algorithm.internal : rndstuff;
2597 auto a = rndstuff!(int)();
2600 auto b = a[a.length / 2];
2601 assert(canFind(a, b));
2607 import std.algorithm.comparison : equal;
2608 assert(equal!(canFind!"a < b")([[1, 2, 3], [7, 8, 9]], [2, 8]));
2613 Advances `r` until it finds the first two adjacent elements `a`,
2614 `b` that satisfy `pred(a, b)`. Performs $(BIGOH r.length)
2615 evaluations of `pred`.
2618 pred = The predicate to satisfy.
2619 r = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to
2623 `r` advanced to the first occurrence of two adjacent elements that satisfy
2624 the given predicate. If there are no such two elements, returns `r` advanced
2628 $(LINK2 http://en.cppreference.com/w/cpp/algorithm/adjacent_find, STL's `adjacent_find`)
2630 Range findAdjacent(alias pred = "a == b", Range)(Range r)
2631 if (isForwardRange!(Range))
2633 auto ahead = r.save;
2636 for (ahead.popFront(); !ahead.empty; r.popFront(), ahead.popFront())
2638 if (binaryFun!(pred)(r.front, ahead.front)) return r;
2641 static if (!isInfinite!Range)
2649 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
2650 auto r = findAdjacent(a);
2651 assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]);
2652 auto p = findAdjacent!("a < b")(a);
2653 assert(p == [ 7, 8, 9 ]);
2659 import std.algorithm.comparison : equal;
2660 import std.internal.test.dummyrange;
2663 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
2664 auto p = findAdjacent(a);
2665 assert(p == [10, 10, 9, 8, 8, 7, 8, 9 ]);
2666 p = findAdjacent!("a < b")(a);
2667 assert(p == [7, 8, 9]);
2670 p = findAdjacent(a);
2673 a = [ 1, 2, 3, 4, 5 ];
2674 p = findAdjacent(a);
2676 p = findAdjacent!"a > b"(a);
2678 ReferenceForwardRange!int rfr = new ReferenceForwardRange!int([1, 2, 3, 2, 2, 3]);
2679 assert(equal(findAdjacent(rfr), [2, 2, 3]));
2681 // https://issues.dlang.org/show_bug.cgi?id=9350
2682 assert(!repeat(1).findAdjacent().empty);
2687 Searches the given range for an element that matches one of the given choices.
2689 Advances `seq` by calling `seq.popFront` until either
2690 `find!(pred)(choices, seq.front)` is `true`, or `seq` becomes empty.
2691 Performs $(BIGOH seq.length * choices.length) evaluations of `pred`.
2694 pred = The predicate to use for determining a match.
2695 seq = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to
2697 choices = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2698 of possible choices.
2701 `seq` advanced to the first matching element, or until empty if there are no
2704 See_Also: $(LREF find), $(REF std,algorithm,comparison,among)
2706 InputRange findAmong(alias pred = "a == b", InputRange, ForwardRange)(
2707 InputRange seq, ForwardRange choices)
2708 if (isInputRange!InputRange && isForwardRange!ForwardRange)
2710 for (; !seq.empty && find!pred(choices.save, seq.front).empty; seq.popFront())
2719 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2720 int[] b = [ 3, 1, 2 ];
2721 assert(findAmong(a, b) == a[2 .. $]);
2726 int[] a = [ -1, 0, 2, 1, 2, 3, 4, 5 ];
2727 int[] b = [ 1, 2, 3 ];
2728 assert(findAmong(a, b) == [2, 1, 2, 3, 4, 5 ]);
2729 assert(findAmong(b, [ 4, 6, 7 ][]).empty);
2730 assert(findAmong!("a == b")(a, b).length == a.length - 2);
2731 assert(findAmong!("a == b")(b, [ 4, 6, 7 ][]).empty);
2734 // https://issues.dlang.org/show_bug.cgi?id=19765
2737 import std.range.interfaces : inputRangeObject;
2738 auto choices = inputRangeObject("b");
2739 auto f = "foobar".findAmong(choices);
2745 * Finds `needle` in `haystack` and positions `haystack`
2746 * right after the first occurrence of `needle`.
2748 * If no needle is provided, the `haystack` is advanced as long as `pred`
2749 * evaluates to `true`.
2750 * Similarly, the haystack is positioned so as `pred` evaluates to `false` for
2755 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search
2758 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search
2760 * pred = Custom predicate for comparison of haystack and needle
2762 * Returns: `true` if the needle was found, in which case `haystack` is
2763 * positioned after the end of the first occurrence of `needle`; otherwise
2764 * `false`, leaving `haystack` untouched. If no needle is provided, it returns
2765 * the number of times `pred(haystack.front)` returned true.
2767 * See_Also: $(LREF find)
2769 bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle)
2770 if (isForwardRange!R1 && isForwardRange!R2
2771 && is(typeof(binaryFun!pred(haystack.front, needle.front))))
2773 auto parts = findSplit!pred(haystack, needle);
2774 if (parts[1].empty) return false;
2776 haystack = parts[2];
2783 import std.range.primitives : empty;
2784 // Needle is found; s is replaced by the substring following the first
2785 // occurrence of the needle.
2786 string s = "abcdef";
2787 assert(findSkip(s, "cd") && s == "ef");
2789 // Needle is not found; s is left untouched.
2791 assert(!findSkip(s, "cxd") && s == "abcdef");
2793 // If the needle occurs at the end of the range, the range is left empty.
2795 assert(findSkip(s, "def") && s.empty);
2798 // https://issues.dlang.org/show_bug.cgi?id=19020
2801 static struct WrapperRange
2804 @property auto empty() { return _r.empty(); }
2805 @property auto front() { return _r.front(); }
2806 auto popFront() { return _r.popFront(); }
2807 @property auto save() { return WrapperRange(_r.save); }
2809 auto tmp = WrapperRange("there is a bug here: *");
2810 assert(!tmp.findSkip("*/"));
2811 assert(tmp._r == "there is a bug here: *");
2815 size_t findSkip(alias pred, R1)(ref R1 haystack)
2816 if (isForwardRange!R1 && ifTestable!(typeof(haystack.front), unaryFun!pred))
2819 while (!haystack.empty && unaryFun!pred(haystack.front))
2830 import std.ascii : isWhite;
2832 assert(findSkip!isWhite(s) && s == "abc");
2833 assert(!findSkip!isWhite(s) && s == "abc");
2836 assert(findSkip!isWhite(s) == 2);
2841 import std.ascii : isWhite;
2844 assert(findSkip!isWhite(s) == 2);
2848 These functions find the first occurrence of `needle` in `haystack` and then
2849 split `haystack` as follows.
2851 `findSplit` returns a tuple `result` containing $(I three) ranges. `result[0]`
2852 is the portion of `haystack` before `needle`, `result[1]` is the portion of
2853 `haystack` that matches `needle`, and `result[2]` is the portion of `haystack`
2854 after the match. If `needle` was not found, `result[0]` comprehends `haystack`
2855 entirely and `result[1]` and `result[2]` are empty.
2857 `findSplitBefore` returns a tuple `result` containing two ranges. `result[0]` is
2858 the portion of `haystack` before `needle`, and `result[1]` is the balance of
2859 `haystack` starting with the match. If `needle` was not found, `result[0]`
2860 comprehends `haystack` entirely and `result[1]` is empty.
2862 `findSplitAfter` returns a tuple `result` containing two ranges.
2863 `result[0]` is the portion of `haystack` up to and including the
2864 match, and `result[1]` is the balance of `haystack` starting
2865 after the match. If `needle` was not found, `result[0]` is empty
2866 and `result[1]` is `haystack`.
2868 In all cases, the concatenation of the returned ranges spans the
2871 If `haystack` is a random-access range, all three components of the tuple have
2872 the same type as `haystack`. Otherwise, `haystack` must be a
2873 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) and
2874 the type of `result[0]` and `result[1]` is the same as $(REF takeExactly,
2878 pred = Predicate to use for comparing needle against haystack.
2879 haystack = The range to search.
2880 needle = What to look for.
2884 A sub-type of `Tuple!()` of the split portions of `haystack` (see above for
2885 details). This sub-type of `Tuple!()` has `opCast` defined for `bool`. This
2886 `opCast` returns `true` when the separating `needle` was found
2887 and `false` otherwise.
2889 See_Also: $(LREF find)
2891 auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
2892 if (isForwardRange!R1 && isForwardRange!R2)
2894 static struct Result(S1, S2) if (isForwardRange!S1 &&
2897 this(S1 pre, S1 separator, S2 post)
2899 asTuple = typeof(asTuple)(pre, separator, post);
2901 void opAssign(typeof(asTuple) rhs)
2905 Tuple!(S1, S1, S2) asTuple;
2906 static if (hasConstEmptyMember!(typeof(asTuple[1])))
2908 bool opCast(T : bool)() const
2910 return !asTuple[1].empty;
2915 bool opCast(T : bool)()
2917 return !asTuple[1].empty;
2923 static if (isSomeString!R1 && isSomeString!R2
2924 || (isRandomAccessRange!R1 && hasSlicing!R1 && hasLength!R1 && hasLength!R2))
2926 auto balance = find!pred(haystack, needle);
2927 immutable pos1 = haystack.length - balance.length;
2928 immutable pos2 = balance.empty ? pos1 : pos1 + needle.length;
2929 return Result!(typeof(haystack[0 .. pos1]),
2930 typeof(haystack[pos2 .. haystack.length]))(haystack[0 .. pos1],
2931 haystack[pos1 .. pos2],
2932 haystack[pos2 .. haystack.length]);
2936 import std.range : takeExactly;
2937 auto original = haystack.save;
2938 auto h = haystack.save;
2939 auto n = needle.save;
2941 while (!n.empty && !h.empty)
2943 if (binaryFun!pred(h.front, n.front))
2951 haystack.popFront();
2957 if (!n.empty) // incomplete match at the end of haystack
2961 return Result!(typeof(takeExactly(original, pos1)),
2962 typeof(h))(takeExactly(original, pos1),
2963 takeExactly(haystack, pos2 - pos1),
2969 auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
2970 if (isForwardRange!R1 && isForwardRange!R2)
2972 static struct Result(S1, S2) if (isForwardRange!S1 &&
2975 this(S1 pre, S2 post)
2977 asTuple = typeof(asTuple)(pre, post);
2979 void opAssign(typeof(asTuple) rhs)
2983 Tuple!(S1, S2) asTuple;
2984 static if (hasConstEmptyMember!(typeof(asTuple[1])))
2986 bool opCast(T : bool)() const
2988 return !asTuple[1].empty;
2993 bool opCast(T : bool)()
2995 return !asTuple[1].empty;
3001 static if (isSomeString!R1 && isSomeString!R2
3002 || (isRandomAccessRange!R1 && hasLength!R1 && hasSlicing!R1 && hasLength!R2))
3004 auto balance = find!pred(haystack, needle);
3005 immutable pos = haystack.length - balance.length;
3006 return Result!(typeof(haystack[0 .. pos]),
3007 typeof(haystack[pos .. haystack.length]))(haystack[0 .. pos],
3008 haystack[pos .. haystack.length]);
3012 import std.range : takeExactly;
3013 auto original = haystack.save;
3014 auto h = haystack.save;
3015 auto n = needle.save;
3017 while (!n.empty && !h.empty)
3019 if (binaryFun!pred(h.front, n.front))
3027 haystack.popFront();
3033 if (!n.empty) // incomplete match at the end of haystack
3038 return Result!(typeof(takeExactly(original, pos1)),
3039 typeof(haystack))(takeExactly(original, pos1),
3045 auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3046 if (isForwardRange!R1 && isForwardRange!R2)
3048 static struct Result(S1, S2) if (isForwardRange!S1 &&
3051 this(S1 pre, S2 post)
3053 asTuple = typeof(asTuple)(pre, post);
3055 void opAssign(typeof(asTuple) rhs)
3059 Tuple!(S1, S2) asTuple;
3060 static if (hasConstEmptyMember!(typeof(asTuple[1])))
3062 bool opCast(T : bool)() const
3064 return !asTuple[0].empty;
3069 bool opCast(T : bool)()
3071 return !asTuple[0].empty;
3077 static if (isSomeString!R1 && isSomeString!R2
3078 || isRandomAccessRange!R1 && hasLength!R1 && hasSlicing!R1 && hasLength!R2)
3080 auto balance = find!pred(haystack, needle);
3081 immutable pos = balance.empty ? 0 : haystack.length - balance.length + needle.length;
3082 return Result!(typeof(haystack[0 .. pos]),
3083 typeof(haystack[pos .. haystack.length]))(haystack[0 .. pos],
3084 haystack[pos .. haystack.length]);
3088 import std.range : takeExactly;
3089 auto original = haystack.save;
3090 auto h = haystack.save;
3091 auto n = needle.save;
3098 return Result!(typeof(takeExactly(original, 0)),
3099 typeof(original))(takeExactly(original, 0),
3102 if (binaryFun!pred(h.front, n.front))
3110 haystack.popFront();
3116 return Result!(typeof(takeExactly(original, pos2)),
3117 typeof(h))(takeExactly(original, pos2),
3122 /// Returning a subtype of $(REF Tuple, std,typecons) enables
3123 /// the following convenient idiom:
3124 @safe pure nothrow unittest
3126 // findSplit returns a triplet
3127 if (auto split = "dlang-rocks".findSplit("-"))
3129 assert(split[0] == "dlang");
3130 assert(split[1] == "-");
3131 assert(split[2] == "rocks");
3135 // works with const aswell
3136 if (const split = "dlang-rocks".findSplit("-"))
3138 assert(split[0] == "dlang");
3139 assert(split[1] == "-");
3140 assert(split[2] == "rocks");
3146 @safe pure nothrow unittest
3148 import std.range.primitives : empty;
3150 auto a = "Carl Sagan Memorial Station";
3151 auto r = findSplit(a, "Velikovsky");
3152 import std.typecons : isTuple;
3153 static assert(isTuple!(typeof(r.asTuple)));
3154 static assert(isTuple!(typeof(r)));
3159 r = findSplit(a, " ");
3160 assert(r[0] == "Carl");
3161 assert(r[1] == " ");
3162 assert(r[2] == "Sagan Memorial Station");
3163 if (const r1 = findSplitBefore(a, "Sagan"))
3166 assert(r1[0] == "Carl ");
3167 assert(r1[1] == "Sagan Memorial Station");
3169 if (const r2 = findSplitAfter(a, "Sagan"))
3172 assert(r2[0] == "Carl Sagan");
3173 assert(r2[1] == " Memorial Station");
3177 /// Use $(REF only, std,range) to find single elements:
3178 @safe pure nothrow unittest
3180 import std.range : only;
3181 assert([1, 2, 3, 4].findSplitBefore(only(3))[0] == [1, 2]);
3184 @safe pure nothrow unittest
3186 import std.range.primitives : empty;
3188 immutable a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3189 auto r = findSplit(a, [9, 1]);
3194 r = findSplit(a, [3]);
3196 assert(r[0] == a[0 .. 2]);
3197 assert(r[1] == a[2 .. 3]);
3198 assert(r[2] == a[3 .. $]);
3201 const r1 = findSplitBefore(a, [9, 1]);
3204 assert(r1[1].empty);
3207 if (immutable r1 = findSplitBefore(a, [3, 4]))
3210 assert(r1[0] == a[0 .. 2]);
3211 assert(r1[1] == a[2 .. $]);
3216 const r2 = findSplitAfter(a, [9, 1]);
3218 assert(r2[0].empty);
3222 if (immutable r3 = findSplitAfter(a, [3, 4]))
3225 assert(r3[0] == a[0 .. 4]);
3226 assert(r3[1] == a[4 .. $]);
3231 @safe pure nothrow unittest
3233 import std.algorithm.comparison : equal;
3234 import std.algorithm.iteration : filter;
3236 auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3237 auto fwd = filter!"a > 0"(a);
3238 auto r = findSplit(fwd, [9, 1]);
3240 assert(equal(r[0], a));
3243 r = findSplit(fwd, [3]);
3245 assert(equal(r[0], a[0 .. 2]));
3246 assert(equal(r[1], a[2 .. 3]));
3247 assert(equal(r[2], a[3 .. $]));
3248 r = findSplit(fwd, [8, 9]);
3250 assert(equal(r[0], a));
3254 // auto variable `r2` cannot be `const` because `fwd.front` is mutable
3256 auto r1 = findSplitBefore(fwd, [9, 1]);
3258 assert(equal(r1[0], a));
3259 assert(r1[1].empty);
3262 if (auto r1 = findSplitBefore(fwd, [3, 4]))
3265 assert(equal(r1[0], a[0 .. 2]));
3266 assert(equal(r1[1], a[2 .. $]));
3271 auto r1 = findSplitBefore(fwd, [8, 9]);
3273 assert(equal(r1[0], a));
3274 assert(r1[1].empty);
3278 auto r2 = findSplitAfter(fwd, [9, 1]);
3280 assert(r2[0].empty);
3281 assert(equal(r2[1], a));
3284 if (auto r2 = findSplitAfter(fwd, [3, 4]))
3287 assert(equal(r2[0], a[0 .. 4]));
3288 assert(equal(r2[1], a[4 .. $]));
3293 auto r2 = findSplitAfter(fwd, [8, 9]);
3295 assert(r2[0].empty);
3296 assert(equal(r2[1], a));
3300 @safe pure nothrow @nogc unittest
3302 auto str = "sep,one,sep,two";
3304 auto split = str.findSplitAfter(",");
3305 assert(split[0] == "sep,");
3307 split = split[1].findSplitAfter(",");
3308 assert(split[0] == "one,");
3310 split = split[1].findSplitBefore(",");
3311 assert(split[0] == "sep");
3314 @safe pure nothrow @nogc unittest
3316 auto str = "sep,one,sep,two";
3318 auto split = str.findSplitBefore(",two");
3319 assert(split[0] == "sep,one,sep");
3320 assert(split[1] == ",two");
3322 split = split[0].findSplitBefore(",sep");
3323 assert(split[0] == "sep,one");
3324 assert(split[1] == ",sep");
3326 split = split[0].findSplitAfter(",");
3327 assert(split[0] == "sep,");
3328 assert(split[1] == "one");
3331 // https://issues.dlang.org/show_bug.cgi?id=11013
3335 auto split = var.findSplitBefore!q{a == a}(var);
3336 assert(split[0] == "");
3337 assert(split[1] == "abc");
3343 Computes the minimum (respectively maximum) of `range` along with its number of
3344 occurrences. Formally, the minimum is a value `x` in `range` such that $(D
3345 pred(a, x)) is `false` for all values `a` in `range`. Conversely, the maximum is
3346 a value `x` in `range` such that `pred(x, a)` is `false` for all values `a`
3347 in `range` (note the swapped arguments to `pred`).
3349 These functions may be used for computing arbitrary extrema by choosing `pred`
3350 appropriately. For corrrect functioning, `pred` must be a strict partial order,
3351 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and
3352 irreflexive (`pred(a, a)` is `false`). The $(LUCKY trichotomy property of
3353 inequality) is not required: these algorithms consider elements `a` and `b` equal
3354 (for the purpose of counting) if `pred` puts them in the same equivalence class,
3355 i.e. `!pred(a, b) && !pred(b, a)`.
3358 pred = The ordering predicate to use to determine the extremum (minimum
3360 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to count.
3362 Returns: The minimum, respectively maximum element of a range together with the
3363 number it occurs in the range.
3365 Limitations: If at least one of the arguments is NaN, the result is
3366 an unspecified value. See $(REF maxElement, std,algorithm,searching)
3367 for examples on how to cope with NaNs.
3369 Throws: `Exception` if `range.empty`.
3371 See_Also: $(REF min, std,algorithm,comparison), $(LREF minIndex), $(LREF minElement), $(LREF minPos)
3373 Tuple!(ElementType!Range, size_t)
3374 minCount(alias pred = "a < b", Range)(Range range)
3375 if (isInputRange!Range && !isInfinite!Range &&
3376 is(typeof(binaryFun!pred(range.front, range.front))))
3378 import std.algorithm.internal : algoFormat;
3379 import std.exception : enforce;
3381 alias T = ElementType!Range;
3382 alias UT = Unqual!T;
3383 alias RetType = Tuple!(T, size_t);
3385 static assert(is(typeof(RetType(range.front, 1))),
3386 algoFormat("Error: Cannot call minCount on a %s, because it is not possible "~
3387 "to copy the result value (a %s) into a Tuple.", Range.stringof, T.stringof));
3389 enforce(!range.empty, "Can't count elements from an empty range");
3390 size_t occurrences = 1;
3392 static if (isForwardRange!Range)
3394 Range least = range.save;
3395 for (range.popFront(); !range.empty; range.popFront())
3397 if (binaryFun!pred(least.front, range.front))
3399 assert(!binaryFun!pred(range.front, least.front),
3400 "min/maxPos: predicate must be a strict partial order.");
3403 if (binaryFun!pred(range.front, least.front))
3412 return RetType(least.front, occurrences);
3414 else static if (isAssignable!(UT, T) || (!hasElaborateAssign!UT && isAssignable!UT))
3417 static if (isAssignable!(UT, T)) v = range.front;
3418 else v = cast(UT) range.front;
3420 for (range.popFront(); !range.empty; range.popFront())
3422 if (binaryFun!pred(*cast(T*)&v, range.front)) continue;
3423 if (binaryFun!pred(range.front, *cast(T*)&v))
3426 static if (isAssignable!(UT, T)) v = range.front;
3427 else v = cast(UT) range.front; //Safe because !hasElaborateAssign!UT
3433 return RetType(*cast(T*)&v, occurrences);
3435 else static if (hasLvalueElements!Range)
3437 import std.algorithm.internal : addressOf;
3438 T* p = addressOf(range.front);
3439 for (range.popFront(); !range.empty; range.popFront())
3441 if (binaryFun!pred(*p, range.front)) continue;
3442 if (binaryFun!pred(range.front, *p))
3445 p = addressOf(range.front);
3451 return RetType(*p, occurrences);
3454 static assert(false,
3455 algoFormat("Sorry, can't find the minCount of a %s: Don't know how "~
3456 "to keep track of the smallest %s element.", Range.stringof, T.stringof));
3460 Tuple!(ElementType!Range, size_t)
3461 maxCount(alias pred = "a < b", Range)(Range range)
3462 if (isInputRange!Range && !isInfinite!Range &&
3463 is(typeof(binaryFun!pred(range.front, range.front))))
3465 return range.minCount!((a, b) => binaryFun!pred(b, a));
3471 import std.conv : text;
3472 import std.typecons : tuple;
3474 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3475 // Minimum is 1 and occurs 3 times
3476 assert(a.minCount == tuple(1, 3));
3477 // Maximum is 4 and occurs 2 times
3478 assert(a.maxCount == tuple(4, 2));
3483 import std.conv : text;
3484 import std.exception : assertThrown;
3485 import std.internal.test.dummyrange;
3487 int[][] b = [ [4], [2, 4], [4], [4] ];
3488 auto c = minCount!("a[0] < b[0]")(b);
3489 assert(c == tuple([2, 4], 1), text(c[0]));
3492 assertThrown(minCount(b[$..$]));
3494 //test with reference ranges. Test both input and forward.
3495 assert(minCount(new ReferenceInputRange!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2));
3496 assert(minCount(new ReferenceForwardRange!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2));
3501 import std.conv : text;
3502 import std.meta : AliasSeq;
3504 static struct R(T) //input range
3510 immutable a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3511 R!(immutable int) b = R!(immutable int)(a);
3513 assert(minCount(a) == tuple(1, 3));
3514 assert(minCount(b) == tuple(1, 3));
3515 assert(minCount!((ref immutable int a, ref immutable int b) => (a > b))(a) == tuple(4, 2));
3516 assert(minCount!((ref immutable int a, ref immutable int b) => (a > b))(b) == tuple(4, 2));
3518 immutable(int[])[] c = [ [4], [2, 4], [4], [4] ];
3519 assert(minCount!("a[0] < b[0]")(c) == tuple([2, 4], 1), text(c[0]));
3525 alias IS1 = immutable(S1);
3526 static assert( isAssignable!S1);
3527 static assert( isAssignable!(S1, IS1));
3532 this(ref immutable int i) immutable {p = &i;}
3533 this(ref int i) {p = &i;}
3534 @property ref inout(int) i() inout {return *p;}
3535 bool opEquals(const S2 other) const {return i == other.i;}
3537 alias IS2 = immutable(S2);
3538 static assert( isAssignable!S2);
3539 static assert(!isAssignable!(S2, IS2));
3540 static assert(!hasElaborateAssign!S2);
3545 void opAssign(ref S3 other) @disable;
3547 static assert(!isAssignable!S3);
3549 static foreach (Type; AliasSeq!(S1, IS1, S2, IS2, S3))
3551 static if (is(Type == immutable)) alias V = immutable int;
3554 auto r1 = [Type(two), Type(one), Type(one)];
3555 auto r2 = R!Type(r1);
3556 assert(minCount!"a.i < b.i"(r1) == tuple(Type(one), 2));
3557 assert(minCount!"a.i < b.i"(r2) == tuple(Type(one), 2));
3558 assert(one == 1 && two == 2);
3563 Iterates the passed range and returns the minimal element.
3564 A custom mapping function can be passed to `map`.
3565 In other languages this is sometimes called `argmin`.
3568 Exactly `n - 1` comparisons are needed.
3571 map = custom accessor for the comparison key
3572 r = range from which the minimal element will be selected
3573 seed = custom seed to use as initial element
3575 Returns: The minimal element of the passed-in range.
3578 If at least one of the arguments is NaN, the result is an unspecified value.
3580 If you want to ignore NaNs, you can use $(REF filter, std,algorithm,iteration)
3581 and $(REF isNaN, std,math) to remove them, before applying minElement.
3582 Add a suitable seed, to avoid error messages if all elements are NaNs:
3585 <range>.filter!(a=>!a.isNaN).minElement(<seed>);
3588 If you want to get NaN as a result if a NaN is present in the range,
3589 you can use $(REF fold, std,algorithm,iteration) and $(REF isNaN, std,math):
3592 <range>.fold!((a,b)=>a.isNaN || b.isNaN ? real.nan : a < b ? a : b);
3597 $(LREF maxElement), $(REF min, std,algorithm,comparison), $(LREF minCount),
3598 $(LREF minIndex), $(LREF minPos)
3600 auto minElement(alias map = (a => a), Range)(Range r)
3601 if (isInputRange!Range && !isInfinite!Range)
3603 return extremum!map(r);
3607 auto minElement(alias map = (a => a), Range, RangeElementType = ElementType!Range)
3608 (Range r, RangeElementType seed)
3609 if (isInputRange!Range && !isInfinite!Range &&
3610 !is(CommonType!(ElementType!Range, RangeElementType) == void))
3612 return extremum!map(r, seed);
3618 import std.range : enumerate;
3619 import std.typecons : tuple;
3621 assert([2, 7, 1, 3].minElement == 1);
3623 // allows to get the index of an element too
3624 assert([5, 3, 7, 9].enumerate.minElement!"a.value" == tuple(1, 3));
3626 // any custom accessor can be passed
3627 assert([[0, 4], [1, 2]].minElement!"a[1]" == [1, 2]);
3631 assert(arr.minElement(1) == 1);
3636 import std.range : enumerate, iota;
3638 assert([3, 4, 5, 1, 2].enumerate.minElement!"a.value" == tuple(3, 1));
3639 assert([5, 2, 4].enumerate.minElement!"a.value" == tuple(1, 2));
3642 assert(iota(1, 5).minElement() == 1);
3643 assert(iota(2, 5).enumerate.minElement!"a.value" == tuple(0, 2));
3645 // should work with const
3646 const(int)[] immArr = [2, 1, 3];
3647 assert(immArr.minElement == 1);
3649 // should work with immutable
3650 immutable(int)[] immArr2 = [2, 1, 3];
3651 assert(immArr2.minElement == 1);
3654 assert(["b", "a", "c"].minElement == "a");
3656 // with all dummy ranges
3657 import std.internal.test.dummyrange;
3658 foreach (DummyType; AllDummyRanges)
3661 assert(d.minElement == 1);
3662 assert(d.minElement!(a => a) == 1);
3663 assert(d.minElement!(a => -a) == 10);
3666 // with empty, but seeded ranges
3668 assert(arr.minElement(42) == 42);
3669 assert(arr.minElement!(a => a)(42) == 42);
3672 @nogc @safe nothrow pure unittest
3674 static immutable arr = [7, 3, 4, 2, 1, 8];
3675 assert(arr.minElement == 1);
3677 static immutable arr2d = [[1, 9], [3, 1], [4, 2]];
3678 assert(arr2d.minElement!"a[1]" == arr2d[1]);
3681 // https://issues.dlang.org/show_bug.cgi?id=17982
3689 const(A)[] v = [A(0)];
3690 assert(v.minElement!"a.val" == A(0));
3693 // https://issues.dlang.org/show_bug.cgi?id=17982
3699 this(int val){ this.val = val; }
3702 const(B) doStuff(const(B)[] v)
3704 return v.minElement!"a.val";
3706 assert(doStuff([new B(1), new B(0), new B(2)]).val == 0);
3708 const(B)[] arr = [new B(0), new B(1)];
3709 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
3710 assert(arr.minElement!"a.val".val == 0);
3714 Iterates the passed range and returns the maximal element.
3715 A custom mapping function can be passed to `map`.
3716 In other languages this is sometimes called `argmax`.
3719 Exactly `n - 1` comparisons are needed.
3722 map = custom accessor for the comparison key
3723 r = range from which the maximum element will be selected
3724 seed = custom seed to use as initial element
3726 Returns: The maximal element of the passed-in range.
3729 If at least one of the arguments is NaN, the result is an unspecified value.
3730 See $(REF minElement, std,algorithm,searching) for examples on how to cope
3735 $(LREF minElement), $(REF max, std,algorithm,comparison), $(LREF maxCount),
3736 $(LREF maxIndex), $(LREF maxPos)
3738 auto maxElement(alias map = (a => a), Range)(Range r)
3739 if (isInputRange!Range && !isInfinite!Range)
3741 return extremum!(map, "a > b")(r);
3745 auto maxElement(alias map = (a => a), Range, RangeElementType = ElementType!Range)
3746 (Range r, RangeElementType seed)
3747 if (isInputRange!Range && !isInfinite!Range &&
3748 !is(CommonType!(ElementType!Range, RangeElementType) == void))
3750 return extremum!(map, "a > b")(r, seed);
3756 import std.range : enumerate;
3757 import std.typecons : tuple;
3758 assert([2, 1, 4, 3].maxElement == 4);
3760 // allows to get the index of an element too
3761 assert([2, 1, 4, 3].enumerate.maxElement!"a.value" == tuple(2, 4));
3763 // any custom accessor can be passed
3764 assert([[0, 4], [1, 2]].maxElement!"a[1]" == [0, 4]);
3768 assert(arr.minElement(1) == 1);
3773 import std.range : enumerate, iota;
3776 assert([3, 4, 5, 1, 2].enumerate.maxElement!"a.value" == tuple(2, 5));
3777 assert([5, 2, 4].enumerate.maxElement!"a.value" == tuple(0, 5));
3780 assert(iota(1, 5).maxElement() == 4);
3781 assert(iota(2, 5).enumerate.maxElement!"a.value" == tuple(2, 4));
3782 assert(iota(4, 14).enumerate.maxElement!"a.value" == tuple(9, 13));
3784 // should work with const
3785 const(int)[] immArr = [2, 3, 1];
3786 assert(immArr.maxElement == 3);
3788 // should work with immutable
3789 immutable(int)[] immArr2 = [2, 3, 1];
3790 assert(immArr2.maxElement == 3);
3793 assert(["a", "c", "b"].maxElement == "c");
3795 // with all dummy ranges
3796 import std.internal.test.dummyrange;
3797 foreach (DummyType; AllDummyRanges)
3800 assert(d.maxElement == 10);
3801 assert(d.maxElement!(a => a) == 10);
3802 assert(d.maxElement!(a => -a) == 1);
3805 // with empty, but seeded ranges
3807 assert(arr.maxElement(42) == 42);
3808 assert(arr.maxElement!(a => a)(42) == 42);
3812 @nogc @safe nothrow pure unittest
3814 static immutable arr = [7, 3, 8, 2, 1, 4];
3815 assert(arr.maxElement == 8);
3817 static immutable arr2d = [[1, 3], [3, 9], [4, 2]];
3818 assert(arr2d.maxElement!"a[1]" == arr2d[1]);
3821 // https://issues.dlang.org/show_bug.cgi?id=17982
3827 this(int val){ this.val = val; }
3830 const(B) doStuff(const(B)[] v)
3832 return v.maxElement!"a.val";
3834 assert(doStuff([new B(1), new B(0), new B(2)]).val == 2);
3836 const(B)[] arr = [new B(0), new B(1)];
3837 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
3838 assert(arr.maxElement!"a.val".val == 1);
3843 Computes a subrange of `range` starting at the first occurrence of `range`'s
3844 minimum (respectively maximum) and with the same ending as `range`, or the
3845 empty range if `range` itself is empty.
3847 Formally, the minimum is a value `x` in `range` such that `pred(a, x)` is
3848 `false` for all values `a` in `range`. Conversely, the maximum is a value `x` in
3849 `range` such that `pred(x, a)` is `false` for all values `a` in `range` (note
3850 the swapped arguments to `pred`).
3852 These functions may be used for computing arbitrary extrema by choosing `pred`
3853 appropriately. For corrrect functioning, `pred` must be a strict partial order,
3854 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and
3855 irreflexive (`pred(a, a)` is `false`).
3858 pred = The ordering predicate to use to determine the extremum (minimum or
3860 range = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search.
3862 Returns: The position of the minimum (respectively maximum) element of forward
3863 range `range`, i.e. a subrange of `range` starting at the position of its
3864 smallest (respectively largest) element and with the same ending as `range`.
3866 Limitations: If at least one of the arguments is NaN, the result is
3867 an unspecified value. See $(REF maxElement, std,algorithm,searching)
3868 for examples on how to cope with NaNs.
3871 $(REF max, std,algorithm,comparison), $(LREF minCount), $(LREF minIndex), $(LREF minElement)
3873 Range minPos(alias pred = "a < b", Range)(Range range)
3874 if (isForwardRange!Range && !isInfinite!Range &&
3875 is(typeof(binaryFun!pred(range.front, range.front))))
3877 static if (hasSlicing!Range && isRandomAccessRange!Range && hasLength!Range)
3879 // Prefer index-based access
3881 foreach (i; 1 .. range.length)
3883 if (binaryFun!pred(range[i], range[pos]))
3888 return range[pos .. range.length];
3892 auto result = range.save;
3893 if (range.empty) return result;
3894 for (range.popFront(); !range.empty; range.popFront())
3896 // Note: Unlike minCount, we do not care to find equivalence, so a
3897 // single pred call is enough.
3898 if (binaryFun!pred(range.front, result.front))
3901 result = range.save;
3909 Range maxPos(alias pred = "a < b", Range)(Range range)
3910 if (isForwardRange!Range && !isInfinite!Range &&
3911 is(typeof(binaryFun!pred(range.front, range.front))))
3913 return range.minPos!((a, b) => binaryFun!pred(b, a));
3919 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3920 // Minimum is 1 and first occurs in position 3
3921 assert(a.minPos == [ 1, 2, 4, 1, 1, 2 ]);
3922 // Maximum is 4 and first occurs in position 2
3923 assert(a.maxPos == [ 4, 1, 2, 4, 1, 1, 2 ]);
3928 import std.algorithm.comparison : equal;
3929 import std.internal.test.dummyrange;
3931 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3932 //Test that an empty range works
3934 assert(equal(minPos(b), b));
3936 //test with reference range.
3937 assert( equal( minPos(new ReferenceForwardRange!int([1, 2, 1, 0, 2, 0])), [0, 2, 0] ) );
3943 import std.algorithm.comparison : equal;
3944 import std.container : Array;
3946 assert(Array!int(2, 3, 4, 1, 2, 4, 1, 1, 2)
3949 .equal([ 1, 2, 4, 1, 1, 2 ]));
3955 immutable a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3956 // Minimum is 1 and first occurs in position 3
3957 assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]);
3958 // Maximum is 4 and first occurs in position 5
3959 assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]);
3961 immutable(int[])[] b = [ [4], [2, 4], [4], [4] ];
3962 assert(minPos!("a[0] < b[0]")(b) == [ [2, 4], [4], [4] ]);
3966 Computes the index of the first occurrence of `range`'s minimum element.
3969 pred = The ordering predicate to use to determine the minimum element.
3970 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
3973 Complexity: $(BIGOH range.length)
3974 Exactly `range.length - 1` comparisons are needed.
3977 The index of the first encounter of the minimum element in `range`. If the
3978 `range` is empty, -1 is returned.
3981 If at least one of the arguments is NaN, the result is
3982 an unspecified value. See $(REF maxElement, std,algorithm,searching)
3983 for examples on how to cope with NaNs.
3986 $(LREF maxIndex), $(REF min, std,algorithm,comparison), $(LREF minCount), $(LREF minElement), $(LREF minPos)
3988 ptrdiff_t minIndex(alias pred = "a < b", Range)(Range range)
3989 if (isInputRange!Range && !isInfinite!Range &&
3990 is(typeof(binaryFun!pred(range.front, range.front))))
3992 if (range.empty) return -1;
3994 ptrdiff_t minPos = 0;
3996 static if (isRandomAccessRange!Range && hasLength!Range)
3998 foreach (i; 1 .. range.length)
4000 if (binaryFun!pred(range[i], range[minPos]))
4008 ptrdiff_t curPos = 0;
4009 Unqual!(typeof(range.front)) min = range.front;
4010 for (range.popFront(); !range.empty; range.popFront())
4013 if (binaryFun!pred(range.front, min))
4024 @safe pure nothrow unittest
4026 int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2];
4028 // Minimum is 1 and first occurs in position 3
4029 assert(a.minIndex == 3);
4030 // Get maximum index with minIndex
4031 assert(a.minIndex!"a > b" == 2);
4033 // Range is empty, so return value is -1
4035 assert(b.minIndex == -1);
4037 // Works with more custom types
4038 struct Dog { int age; }
4039 Dog[] dogs = [Dog(10), Dog(5), Dog(15)];
4040 assert(dogs.minIndex!"a.age < b.age" == 1);
4045 // should work with const
4046 const(int)[] immArr = [2, 1, 3];
4047 assert(immArr.minIndex == 1);
4049 // Works for const ranges too
4050 const int[] c = [2, 5, 4, 1, 2, 3];
4051 assert(c.minIndex == 3);
4053 // should work with immutable
4054 immutable(int)[] immArr2 = [2, 1, 3];
4055 assert(immArr2.minIndex == 1);
4058 assert(["b", "a", "c"].minIndex == 1);
4061 import std.range : cycle;
4062 static assert(!__traits(compiles, cycle([1]).minIndex));
4064 // with all dummy ranges
4065 import std.internal.test.dummyrange : AllDummyRanges;
4066 foreach (DummyType; AllDummyRanges)
4068 static if (isForwardRange!DummyType && !isInfinite!DummyType)
4071 d.arr = [5, 3, 7, 2, 1, 4];
4072 assert(d.minIndex == 4);
4075 assert(d.minIndex == -1);
4080 @nogc @safe nothrow pure unittest
4082 static immutable arr = [7, 3, 8, 2, 1, 4];
4083 assert(arr.minIndex == 4);
4085 static immutable arr2d = [[1, 3], [3, 9], [4, 2]];
4086 assert(arr2d.minIndex!"a[1] < b[1]" == 2);
4089 @safe nothrow pure unittest
4093 static struct InRange
4095 @property int front()
4102 return arr.length == index;
4114 static assert(isInputRange!InRange);
4116 auto arr1 = InRange([5, 2, 3, 4, 5, 3, 6]);
4117 auto arr2 = InRange([7, 3, 8, 2, 1, 4]);
4119 assert(arr1.minIndex == 1);
4120 assert(arr2.minIndex == 4);
4124 Computes the index of the first occurrence of `range`'s maximum element.
4126 Complexity: $(BIGOH range)
4127 Exactly `range.length - 1` comparisons are needed.
4130 pred = The ordering predicate to use to determine the maximum element.
4131 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to search.
4134 The index of the first encounter of the maximum in `range`. If the
4135 `range` is empty, -1 is returned.
4138 If at least one of the arguments is NaN, the result is
4139 an unspecified value. See $(REF maxElement, std,algorithm,searching)
4140 for examples on how to cope with NaNs.
4143 $(LREF minIndex), $(REF max, std,algorithm,comparison), $(LREF maxCount), $(LREF maxElement), $(LREF maxPos)
4145 ptrdiff_t maxIndex(alias pred = "a < b", Range)(Range range)
4146 if (isInputRange!Range && !isInfinite!Range &&
4147 is(typeof(binaryFun!pred(range.front, range.front))))
4149 return range.minIndex!((a, b) => binaryFun!pred(b, a));
4153 @safe pure nothrow unittest
4155 // Maximum is 4 and first occurs in position 2
4156 int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2];
4157 assert(a.maxIndex == 2);
4161 assert(b.maxIndex == -1);
4163 // Works with more custom types
4164 struct Dog { int age; }
4165 Dog[] dogs = [Dog(10), Dog(15), Dog(5)];
4166 assert(dogs.maxIndex!"a.age < b.age" == 1);
4171 // should work with const
4172 const(int)[] immArr = [5, 1, 3];
4173 assert(immArr.maxIndex == 0);
4175 // Works for const ranges too
4176 const int[] c = [2, 5, 4, 1, 2, 3];
4177 assert(c.maxIndex == 1);
4180 // should work with immutable
4181 immutable(int)[] immArr2 = [2, 1, 3];
4182 assert(immArr2.maxIndex == 2);
4185 assert(["b", "a", "c"].maxIndex == 2);
4188 import std.range : cycle;
4189 static assert(!__traits(compiles, cycle([1]).maxIndex));
4191 // with all dummy ranges
4192 import std.internal.test.dummyrange : AllDummyRanges;
4193 foreach (DummyType; AllDummyRanges)
4195 static if (isForwardRange!DummyType && !isInfinite!DummyType)
4199 d.arr = [5, 3, 7, 2, 1, 4];
4200 assert(d.maxIndex == 2);
4203 assert(d.maxIndex == -1);
4208 @nogc @safe nothrow pure unittest
4210 static immutable arr = [7, 3, 8, 2, 1, 4];
4211 assert(arr.maxIndex == 2);
4213 static immutable arr2d = [[1, 3], [3, 9], [4, 2]];
4214 assert(arr2d.maxIndex!"a[1] < b[1]" == 1);
4218 Skip over the initial portion of the first given range (`haystack`) that matches
4219 any of the additionally given ranges (`needles`) fully, or
4220 if no second range is given skip over the elements that fulfill pred.
4221 Do nothing if there is no match.
4224 pred = The predicate that determines whether elements from each respective
4225 range match. Defaults to equality `"a == b"`.
4227 template skipOver(alias pred = (a, b) => a == b)
4229 enum bool isPredComparable(T) = ifTestable!(T, binaryFun!pred);
4233 haystack = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to
4235 needles = The $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives)
4236 representing the prefix of `r1` to skip over.
4237 es = The element to match.
4240 `true` if the prefix of `haystack` matches any range of `needles` fully
4241 or `pred` evaluates to true, and `haystack` has been advanced to the point past this segment;
4242 otherwise false, and `haystack` is left in its original position.
4245 By definition, empty ranges are matched fully and if `needles` contains an empty range,
4246 `skipOver` will return `true`.
4248 bool skipOver(Haystack, Needles...)(ref Haystack haystack, Needles needles)
4249 if (is(typeof(binaryFun!pred(haystack.front, needles[0].front))) &&
4250 isForwardRange!Haystack &&
4251 allSatisfy!(isInputRange, Needles) &&
4252 !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Needles))) == void))
4254 static if (__traits(isSame, pred, (a, b) => a == b)
4255 && is(typeof(haystack[0 .. $] == needles[0]) : bool)
4256 && is(typeof(haystack = haystack[0 .. $]))
4257 && hasLength!Haystack && allSatisfy!(hasLength, Needles))
4259 ptrdiff_t longestMatch = -1;
4260 static foreach (r2; needles)
4262 if (r2.length <= haystack.length && longestMatch < ptrdiff_t(r2.length)
4263 && (haystack[0 .. r2.length] == r2 || r2.length == 0))
4264 longestMatch = r2.length;
4266 if (longestMatch >= 0)
4268 if (longestMatch > 0)
4269 haystack = haystack[longestMatch .. $];
4277 import std.algorithm.comparison : min;
4278 auto r = haystack.save;
4280 static if (hasLength!Haystack && allSatisfy!(hasLength, Needles))
4282 import std.algorithm.iteration : map;
4283 import std.algorithm.searching : minElement;
4284 import std.range : only;
4285 // Shortcut opportunity!
4286 if (needles.only.map!(a => a.length).minElement > haystack.length)
4290 // compatibility: return true if any range was empty
4291 bool hasEmptyRanges;
4292 static foreach (i, r2; needles)
4295 hasEmptyRanges = true;
4298 bool hasNeedleMatch;
4299 size_t inactiveNeedlesLen;
4300 bool[Needles.length] inactiveNeedles;
4301 for (; !r.empty; r.popFront)
4303 static foreach (i, r2; needles)
4305 if (!r2.empty && !inactiveNeedles[i])
4307 if (binaryFun!pred(r.front, r2.front))
4312 // we skipped over a new match
4313 hasNeedleMatch = true;
4314 inactiveNeedlesLen++;
4315 // skip over haystack
4321 inactiveNeedles[i] = true;
4322 inactiveNeedlesLen++;
4328 if (inactiveNeedlesLen == needles.length)
4335 return hasNeedleMatch || hasEmptyRanges;
4340 bool skipOver(R)(ref R r1)
4341 if (isForwardRange!R &&
4342 ifTestable!(typeof(r1.front), unaryFun!pred))
4344 if (r1.empty || !unaryFun!pred(r1.front))
4349 while (!r1.empty && unaryFun!pred(r1.front));
4354 bool skipOver(R, Es...)(ref R r, Es es)
4355 if (isInputRange!R && is(typeof(binaryFun!pred(r.front, es[0]))))
4360 static foreach (e; es)
4362 if (binaryFun!pred(r.front, e))
4375 import std.algorithm.comparison : equal;
4377 auto s1 = "Hello world";
4378 assert(!skipOver(s1, "Ha"));
4379 assert(s1 == "Hello world");
4380 assert(skipOver(s1, "Hell") && s1 == "o world", s1);
4382 string[] r1 = ["abc", "def", "hij"];
4383 dstring[] r2 = ["abc"d];
4384 assert(!skipOver!((a, b) => a.equal(b))(r1, ["def"d]), r1[0]);
4385 assert(r1 == ["abc", "def", "hij"]);
4386 assert(skipOver!((a, b) => a.equal(b))(r1, r2));
4387 assert(r1 == ["def", "hij"]);
4393 import std.ascii : isWhite;
4394 import std.range.primitives : empty;
4396 auto s2 = "\t\tvalue";
4399 assert(s2.skipOver!isWhite && s2 == "value");
4400 assert(!s3.skipOver!isWhite);
4401 assert(s4.skipOver!isWhite && s3.empty);
4404 /// Variadic skipOver
4407 auto s = "Hello world";
4408 assert(!skipOver(s, "hello", "HellO"));
4409 assert(s == "Hello world");
4411 // the range is skipped over the longest matching needle is skipped
4412 assert(skipOver(s, "foo", "hell", "Hello "));
4413 assert(s == "world");
4419 import std.algorithm.comparison : equal;
4421 auto s1 = "Hello world";
4422 assert(!skipOver(s1, 'a'));
4423 assert(s1 == "Hello world");
4424 assert(skipOver(s1, 'H') && s1 == "ello world");
4426 string[] r = ["abc", "def", "hij"];
4428 assert(!skipOver!((a, b) => a.equal(b))(r, "def"d));
4429 assert(r == ["abc", "def", "hij"]);
4430 assert(skipOver!((a, b) => a.equal(b))(r, e));
4431 assert(r == ["def", "hij"]);
4434 assert(!s2.skipOver('a'));
4437 /// Partial instantiation
4440 import std.ascii : isWhite;
4441 import std.range.primitives : empty;
4443 alias whitespaceSkiper = skipOver!isWhite;
4445 auto s2 = "\t\tvalue";
4448 assert(whitespaceSkiper(s2) && s2 == "value");
4449 assert(!whitespaceSkiper(s2));
4450 assert(whitespaceSkiper(s4) && s3.empty);
4453 // variadic skipOver
4456 auto s = "DLang.rocks";
4457 assert(!s.skipOver("dlang", "DLF", "DLang "));
4458 assert(s == "DLang.rocks");
4460 assert(s.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLanpp"));
4461 assert(s == "ang.rocks");
4464 assert(s.skipOver("DLang", "DLANG", "DLF", "D", "DL", "DLang "));
4465 assert(s == ".rocks");
4468 assert(s.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLang."));
4469 assert(s == "rocks");
4472 // variadic with custom pred
4475 import std.ascii : toLower;
4477 auto s = "DLang.rocks";
4478 assert(!s.skipOver("dlang", "DLF", "DLang "));
4479 assert(s == "DLang.rocks");
4481 assert(s.skipOver!((a, b) => a.toLower == b.toLower)("dlang", "DLF", "DLang "));
4482 assert(s == ".rocks");
4485 // variadic skipOver with mixed needles
4488 auto s = "DLang.rocks";
4489 assert(!s.skipOver("dlang"d, "DLF", "DLang "w));
4490 assert(s == "DLang.rocks");
4492 assert(s.skipOver("dlang", "DLANG"d, "DLF"w, "D"d, "DL", "DLanp"));
4493 assert(s == "ang.rocks");
4496 assert(s.skipOver("DLang", "DLANG"w, "DLF"d, "D"d, "DL", "DLang "));
4497 assert(s == ".rocks");
4500 assert(s.skipOver("dlang", "DLANG"w, "DLF", "D"d, "DL"w, "DLang."d));
4501 assert(s == "rocks");
4503 import std.algorithm.iteration : filter;
4505 assert(s.skipOver("dlang", "DLang".filter!(a => true)));
4506 assert(s == ".rocks");
4509 // variadic skipOver with auto-decoding
4512 auto s = "☢☣☠.☺";
4513 assert(s.skipOver("a", "☢", "☢☣☠"));
4514 assert(s == ".☺");
4517 // skipOver with @nogc
4518 @safe @nogc pure nothrow unittest
4520 static immutable s = [0, 1, 2];
4521 immutable(int)[] s2 = s[];
4523 static immutable skip1 = [0, 2];
4524 static immutable skip2 = [0, 1];
4525 assert(s2.skipOver(skip1, skip2));
4526 assert(s2 == s[2 .. $]);
4529 // variadic skipOver with single elements
4532 auto s = "DLang.rocks";
4533 assert(!s.skipOver('a', 'd', 'e'));
4534 assert(s == "DLang.rocks");
4536 assert(s.skipOver('a', 'D', 'd', 'D'));
4537 assert(s == "Lang.rocks");
4540 assert(s.skipOver(wchar('a'), dchar('D'), 'd'));
4541 assert(s == "Lang.rocks");
4543 dstring dstr = "+Foo";
4544 assert(!dstr.skipOver('.', '-'));
4545 assert(dstr == "+Foo");
4547 assert(dstr.skipOver('+', '-'));
4548 assert(dstr == "Foo");
4551 // skipOver with empty ranges must return true (compatibility)
4554 auto s = "DLang.rocks";
4555 assert(s.skipOver(""));
4556 assert(s.skipOver("", ""));
4557 assert(s.skipOver("", "foo"));
4559 auto s2 = "DLang.rocks"d;
4560 assert(s2.skipOver(""));
4561 assert(s2.skipOver("", ""));
4562 assert(s2.skipOver("", "foo"));
4568 import std.utf : byCodeUnit;
4569 import std.algorithm.comparison : equal;
4571 bool stripStartsWith(Text)(ref Text text, string needle)
4573 return text.skipOver(needle.byCodeUnit());
4575 auto text = "<xml></xml>"d.byCodeUnit;
4576 assert(stripStartsWith(text, "<xml>"));
4577 assert(text.equal("</xml>"));
4581 Checks whether the given
4582 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) starts with (one
4583 of) the given needle(s) or, if no needles are given,
4584 if its front element fulfils predicate `pred`.
4588 pred = Predicate to use in comparing the elements of the haystack and the
4589 needle(s). Mandatory if no needles are given.
4591 doesThisStart = The input range to check.
4593 withOneOfThese = The needles against which the range is to be checked,
4594 which may be individual elements or input ranges of elements.
4596 withThis = The single needle to check, which may be either a single element
4597 or an input range of elements.
4601 0 if the needle(s) do not occur at the beginning of the given range;
4602 otherwise the position of the matching needle, that is, 1 if the range starts
4603 with `withOneOfThese[0]`, 2 if it starts with `withOneOfThese[1]`, and so
4606 In the case where `doesThisStart` starts with multiple of the ranges or
4607 elements in `withOneOfThese`, then the shortest one matches (if there are
4608 two which match which are of the same length (e.g. `"a"` and `'a'`), then
4609 the left-most of them in the argument
4612 In the case when no needle parameters are given, return `true` iff front of
4613 `doesThisStart` fulfils predicate `pred`.
4615 uint startsWith(alias pred = (a, b) => a == b, Range, Needles...)(Range doesThisStart, Needles withOneOfThese)
4616 if (isInputRange!Range && Needles.length > 1 &&
4617 allSatisfy!(canTestStartsWith!(pred, Range), Needles))
4619 template checkType(T)
4621 enum checkType = is(immutable ElementEncodingType!Range == immutable T);
4624 // auto-decoding special case
4625 static if (__traits(isSame, binaryFun!pred, (a, b) => a == b) &&
4626 isNarrowString!Range && allSatisfy!(checkType, Needles))
4628 import std.utf : byCodeUnit;
4629 auto haystack = doesThisStart.byCodeUnit;
4633 alias haystack = doesThisStart;
4635 alias needles = withOneOfThese;
4637 // Make one pass looking for empty ranges in needles
4638 foreach (i, Unused; Needles)
4640 // Empty range matches everything
4641 static if (!is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool))
4643 if (needles[i].empty) return i + 1;
4647 for (; !haystack.empty; haystack.popFront())
4649 foreach (i, Unused; Needles)
4651 static if (is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool))
4654 if (binaryFun!pred(haystack.front, needles[i]))
4656 // found, but instead of returning, we just stop searching.
4657 // This is to account for one-element
4658 // range matches (consider startsWith("ab", "a",
4659 // 'a') should return 1, not 2).
4665 if (binaryFun!pred(haystack.front, needles[i].front))
4671 // This code executed on failure to match
4672 // Out with this guy, check for the others
4673 uint result = startsWith!pred(haystack, needles[0 .. i], needles[i + 1 .. $]);
4674 if (result > i) ++result;
4678 // If execution reaches this point, then the front matches for all
4679 // needle ranges, or a needle element has been matched.
4680 // What we need to do now is iterate, lopping off the front of
4681 // the range and checking if the result is empty, or finding an
4682 // element needle and returning.
4683 // If neither happens, we drop to the end and loop.
4684 foreach (i, Unused; Needles)
4686 static if (is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool))
4688 // Test has passed in the previous loop
4693 needles[i].popFront();
4694 if (needles[i].empty) return i + 1;
4702 bool startsWith(alias pred = "a == b", R1, R2)(R1 doesThisStart, R2 withThis)
4703 if (isInputRange!R1 &&
4705 is(typeof(binaryFun!pred(doesThisStart.front, withThis.front)) : bool))
4707 alias haystack = doesThisStart;
4708 alias needle = withThis;
4710 static if (is(typeof(pred) : string))
4711 enum isDefaultPred = pred == "a == b";
4713 enum isDefaultPred = false;
4715 // Note: Although narrow strings don't have a "true" length, for a narrow string to start with another
4716 // narrow string, it must have *at least* as many code units.
4717 static if ((hasLength!R1 && hasLength!R2) ||
4718 ((hasLength!R1 || isNarrowString!R1) && (hasLength!R2 || isNarrowString!R2)
4719 && (ElementEncodingType!R1.sizeof <= ElementEncodingType!R2.sizeof)))
4721 if (haystack.length < needle.length)
4725 static if (isDefaultPred && isArray!R1 && isArray!R2 &&
4726 is(immutable ElementEncodingType!R1 == immutable ElementEncodingType!R2))
4728 //Array slice comparison mode
4729 return haystack[0 .. needle.length] == needle;
4731 else static if (isRandomAccessRange!R1 && isRandomAccessRange!R2 && hasLength!R2)
4733 //RA dual indexing mode
4734 foreach (j; 0 .. needle.length)
4736 if (!binaryFun!pred(haystack[j], needle[j]))
4745 //Standard input range mode
4746 if (needle.empty) return true;
4747 static if (hasLength!R1 && hasLength!R2)
4749 //We have previously checked that haystack.length > needle.length,
4750 //So no need to check haystack.empty during iteration
4751 for ( ; ; haystack.popFront() )
4753 if (!binaryFun!pred(haystack.front, needle.front)) break;
4755 if (needle.empty) return true;
4760 for ( ; !haystack.empty ; haystack.popFront() )
4762 if (!binaryFun!pred(haystack.front, needle.front)) break;
4764 if (needle.empty) return true;
4772 bool startsWith(alias pred = "a == b", R, E)(R doesThisStart, E withThis)
4773 if (isInputRange!R &&
4774 is(typeof(binaryFun!pred(doesThisStart.front, withThis)) : bool))
4776 if (doesThisStart.empty)
4779 static if (is(typeof(pred) : string))
4780 enum isDefaultPred = pred == "a == b";
4782 enum isDefaultPred = false;
4784 alias predFunc = binaryFun!pred;
4786 // auto-decoding special case
4787 static if (isNarrowString!R)
4789 // statically determine decoding is unnecessary to evaluate pred
4790 static if (isDefaultPred && isSomeChar!E && E.sizeof <= ElementEncodingType!R.sizeof)
4791 return doesThisStart[0] == withThis;
4792 // specialize for ASCII as to not change previous behavior
4795 if (withThis <= 0x7F)
4796 return predFunc(doesThisStart[0], withThis);
4798 return predFunc(doesThisStart.front, withThis);
4803 return predFunc(doesThisStart.front, withThis);
4808 bool startsWith(alias pred, R)(R doesThisStart)
4809 if (isInputRange!R &&
4810 ifTestable!(typeof(doesThisStart.front), unaryFun!pred))
4812 return !doesThisStart.empty && unaryFun!pred(doesThisStart.front);
4818 import std.ascii : isAlpha;
4820 assert("abc".startsWith!(a => a.isAlpha));
4821 assert("abc".startsWith!isAlpha);
4822 assert(!"1ab".startsWith!(a => a.isAlpha));
4823 assert(!"".startsWith!(a => a.isAlpha));
4825 import std.algorithm.comparison : among;
4826 assert("abc".startsWith!(a => a.among('a', 'b') != 0));
4827 assert(!"abc".startsWith!(a => a.among('b', 'c') != 0));
4829 assert(startsWith("abc", ""));
4830 assert(startsWith("abc", "a"));
4831 assert(!startsWith("abc", "b"));
4832 assert(startsWith("abc", 'a', "b") == 1);
4833 assert(startsWith("abc", "b", "a") == 2);
4834 assert(startsWith("abc", "a", "a") == 1);
4835 assert(startsWith("abc", "ab", "a") == 2);
4836 assert(startsWith("abc", "x", "a", "b") == 2);
4837 assert(startsWith("abc", "x", "aa", "ab") == 3);
4838 assert(startsWith("abc", "x", "aaa", "sab") == 0);
4839 assert(startsWith("abc", "x", "aaa", "a", "sab") == 3);
4841 import std.typecons : Tuple;
4842 alias C = Tuple!(int, "x", int, "y");
4843 assert(startsWith!"a.x == b"([ C(1,1), C(1,2), C(2,2) ], [1, 1]));
4844 assert(startsWith!"a.x == b"([ C(1,1), C(2,1), C(2,2) ], [1, 1], [1, 2], [1, 3]) == 2);
4849 import std.algorithm.iteration : filter;
4850 import std.conv : to;
4851 import std.meta : AliasSeq;
4854 static foreach (S; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
4855 (){ // workaround slow optimizations for large functions
4856 // https://issues.dlang.org/show_bug.cgi?id=2396
4857 assert(!startsWith(to!S("abc"), 'c'));
4858 assert(startsWith(to!S("abc"), 'a', 'c') == 1);
4859 assert(!startsWith(to!S("abc"), 'x', 'n', 'b'));
4860 assert(startsWith(to!S("abc"), 'x', 'n', 'a') == 3);
4861 assert(startsWith(to!S("\uFF28abc"), 'a', '\uFF28', 'c') == 2);
4863 static foreach (T; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
4866 assert(startsWith(to!S("abc"), to!T("")));
4867 assert(startsWith(to!S("ab"), to!T("a")));
4868 assert(startsWith(to!S("abc"), to!T("a")));
4869 assert(!startsWith(to!S("abc"), to!T("b")));
4870 assert(!startsWith(to!S("abc"), to!T("b"), "bc", "abcd", "xyz"));
4871 assert(startsWith(to!S("abc"), to!T("ab"), 'a') == 2);
4872 assert(startsWith(to!S("abc"), to!T("a"), "b") == 1);
4873 assert(startsWith(to!S("abc"), to!T("b"), "a") == 2);
4874 assert(startsWith(to!S("abc"), to!T("a"), 'a') == 1);
4875 assert(startsWith(to!S("abc"), 'a', to!T("a")) == 1);
4876 assert(startsWith(to!S("abc"), to!T("x"), "a", "b") == 2);
4877 assert(startsWith(to!S("abc"), to!T("x"), "aa", "ab") == 3);
4878 assert(startsWith(to!S("abc"), to!T("x"), "aaa", "sab") == 0);
4879 assert(startsWith(to!S("abc"), 'a'));
4880 assert(!startsWith(to!S("abc"), to!T("sab")));
4881 assert(startsWith(to!S("abc"), 'x', to!T("aaa"), 'a', "sab") == 3);
4884 assert(startsWith(to!S("\uFF28el\uFF4co"), to!T("\uFF28el")));
4885 assert(startsWith(to!S("\uFF28el\uFF4co"), to!T("Hel"), to!T("\uFF28el")) == 2);
4886 assert(startsWith(to!S("日本語"), to!T("日本")));
4887 assert(startsWith(to!S("日本語"), to!T("日本語")));
4888 assert(!startsWith(to!S("日本"), to!T("日本語")));
4891 assert(startsWith(to!S(""), T.init));
4892 assert(!startsWith(to!S(""), 'a'));
4893 assert(startsWith(to!S("a"), T.init));
4894 assert(startsWith(to!S("a"), T.init, "") == 1);
4895 assert(startsWith(to!S("a"), T.init, 'a') == 1);
4896 assert(startsWith(to!S("a"), 'a', T.init) == 2);
4901 assert(!startsWith("abc".takeExactly(3), "abcd".takeExactly(4)));
4902 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(3)));
4903 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(1)));
4905 static foreach (T; AliasSeq!(int, short))
4907 immutable arr = cast(T[])[0, 1, 2, 3, 4, 5];
4910 assert(startsWith(arr, cast(int[]) null));
4911 assert(!startsWith(arr, 5));
4912 assert(!startsWith(arr, 1));
4913 assert(startsWith(arr, 0));
4914 assert(startsWith(arr, 5, 0, 1) == 2);
4915 assert(startsWith(arr, [0]));
4916 assert(startsWith(arr, [0, 1]));
4917 assert(startsWith(arr, [0, 1], 7) == 1);
4918 assert(!startsWith(arr, [0, 1, 7]));
4919 assert(startsWith(arr, [0, 1, 7], [0, 1, 2]) == 2);
4921 //Normal input range
4922 assert(!startsWith(filter!"true"(arr), 1));
4923 assert(startsWith(filter!"true"(arr), 0));
4924 assert(startsWith(filter!"true"(arr), [0]));
4925 assert(startsWith(filter!"true"(arr), [0, 1]));
4926 assert(startsWith(filter!"true"(arr), [0, 1], 7) == 1);
4927 assert(!startsWith(filter!"true"(arr), [0, 1, 7]));
4928 assert(startsWith(filter!"true"(arr), [0, 1, 7], [0, 1, 2]) == 2);
4929 assert(startsWith(arr, filter!"true"([0, 1])));
4930 assert(startsWith(arr, filter!"true"([0, 1]), 7) == 1);
4931 assert(!startsWith(arr, filter!"true"([0, 1, 7])));
4932 assert(startsWith(arr, [0, 1, 7], filter!"true"([0, 1, 2])) == 2);
4935 assert(startsWith!("a%10 == b%10")(arr, [10, 11]));
4936 assert(!startsWith!("a%10 == b%10")(arr, [10, 12]));
4940 private template canTestStartsWith(alias pred, Haystack)
4942 enum bool canTestStartsWith(Needle) = is(typeof(
4943 (ref Haystack h, ref Needle n) => startsWith!pred(h, n)));
4946 /* (Not yet documented.)
4947 Consume all elements from `r` that are equal to one of the elements
4950 private void skipAll(alias pred = "a == b", R, Es...)(ref R r, Es es)
4951 //if (is(typeof(binaryFun!pred(r1.front, es[0]))))
4954 for (; !r.empty; r.popFront())
4958 if (binaryFun!pred(r.front, es[i]))
4969 auto s1 = "Hello world";
4970 skipAll(s1, 'H', 'e');
4971 assert(s1 == "llo world");
4975 Interval option specifier for `until` (below) and others.
4977 If set to `OpenRight.yes`, then the interval is open to the right
4978 (last element is not included).
4980 Otherwise if set to `OpenRight.no`, then the interval is closed to the right
4981 (last element included).
4983 alias OpenRight = Flag!"openRight";
4986 Lazily iterates `range` _until the element `e` for which
4987 `pred(e, sentinel)` is true.
4989 This is similar to `takeWhile` in other languages.
4992 pred = Predicate to determine when to stop.
4993 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
4995 sentinel = The element to stop at.
4996 openRight = Determines whether the element for which the given predicate is
4997 true should be included in the resulting range (`No.openRight`), or
4998 not (`Yes.openRight`).
5001 An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) that
5002 iterates over the original range's elements, but ends when the specified
5003 predicate becomes true. If the original range is a
5004 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) or
5005 higher, this range will be a forward range.
5007 Until!(pred, Range, Sentinel)
5008 until(alias pred = "a == b", Range, Sentinel)
5009 (Range range, Sentinel sentinel, OpenRight openRight = Yes.openRight)
5010 if (!is(Sentinel == OpenRight))
5012 return typeof(return)(range, sentinel, openRight);
5016 Until!(pred, Range, void)
5017 until(alias pred, Range)
5018 (Range range, OpenRight openRight = Yes.openRight)
5020 return typeof(return)(range, openRight);
5024 struct Until(alias pred, Range, Sentinel)
5025 if (isInputRange!Range)
5027 private Range _input;
5028 static if (!is(Sentinel == void))
5029 private Sentinel _sentinel;
5030 private OpenRight _openRight;
5033 static if (!is(Sentinel == void))
5036 this(Range input, Sentinel sentinel,
5037 OpenRight openRight = Yes.openRight)
5040 _sentinel = sentinel;
5041 _openRight = openRight;
5042 _done = _input.empty || openRight && predSatisfied();
5044 private this(Range input, Sentinel sentinel, OpenRight openRight,
5048 _sentinel = sentinel;
5049 _openRight = openRight;
5056 this(Range input, OpenRight openRight = Yes.openRight)
5059 _openRight = openRight;
5060 _done = _input.empty || openRight && predSatisfied();
5062 private this(Range input, OpenRight openRight, bool done)
5065 _openRight = openRight;
5071 @property bool empty()
5077 @property auto ref front()
5079 assert(!empty, "Can not get the front of an empty Until");
5080 return _input.front;
5083 private bool predSatisfied()
5085 static if (is(Sentinel == void))
5086 return cast(bool) unaryFun!pred(_input.front);
5088 return cast(bool) startsWith!pred(_input, _sentinel);
5094 assert(!empty, "Can not popFront of an empty Until");
5097 _done = predSatisfied();
5099 _done = _done || _input.empty;
5104 _done = _input.empty || predSatisfied();
5108 static if (isForwardRange!Range)
5111 @property Until save()
5113 static if (is(Sentinel == void))
5114 return Until(_input.save, _openRight, _done);
5116 return Until(_input.save, _sentinel, _openRight, _done);
5124 import std.algorithm.comparison : equal;
5125 import std.typecons : No;
5126 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
5127 assert(equal(a.until(7), [1, 2, 4]));
5128 assert(equal(a.until(7, No.openRight), [1, 2, 4, 7]));
5133 import std.algorithm.comparison : equal;
5134 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
5136 static assert(isForwardRange!(typeof(a.until(7))));
5137 static assert(isForwardRange!(typeof(until!"a == 2"(a, No.openRight))));
5139 assert(equal(a.until(7), [1, 2, 4]));
5140 assert(equal(a.until([7, 2]), [1, 2, 4, 7]));
5141 assert(equal(a.until(7, No.openRight), [1, 2, 4, 7]));
5142 assert(equal(until!"a == 2"(a, No.openRight), [1, 2]));
5145 // https://issues.dlang.org/show_bug.cgi?id=13171
5148 import std.algorithm.comparison : equal;
5150 auto a = [1, 2, 3, 4];
5151 assert(equal(refRange(&a).until(3, No.openRight), [1, 2, 3]));
5155 // https://issues.dlang.org/show_bug.cgi?id=10460
5158 import std.algorithm.comparison : equal;
5159 auto a = [1, 2, 3, 4];
5160 foreach (ref e; a.until(3))
5162 assert(equal(a, [0, 0, 3, 4]));
5165 // https://issues.dlang.org/show_bug.cgi?id=13124
5168 import std.algorithm.comparison : among, equal;
5169 auto s = "hello how\nare you";
5170 assert(equal(s.until!(c => c.among!('\n', '\r')), "hello how"));
5173 // https://issues.dlang.org/show_bug.cgi?id=18657
5176 import std.algorithm.comparison : equal;
5177 import std.range : refRange;
5179 string s = "foobar";
5180 auto r = refRange(&s).until("bar");
5181 assert(equal(r.save, "foo"));
5182 assert(equal(r.save, "foo"));
5185 string s = "foobar";
5186 auto r = refRange(&s).until!(e => e == 'b');
5187 assert(equal(r.save, "foo"));
5188 assert(equal(r.save, "foo"));