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 &&
123 (__traits(isTemplate, pred) || is(typeof(unaryFun!pred(range.front)))))
125 import std.functional : not;
127 return find!(not!(unaryFun!pred))(range).empty;
134 assert( all!"a & 1"([1, 3, 5, 7, 9]));
135 assert(!all!"a & 1"([1, 2, 3, 5, 7, 9]));
139 `all` can also be used without a predicate, if its items can be
140 evaluated to true or false in a conditional statement. This can be a
141 convenient way to quickly evaluate that $(I _all) of the elements of a range
146 int[3] vals = [5, 3, 18];
147 assert( all(vals[]));
153 assert(all!(a => a > x)([2, 3]));
154 assert(all!"a == 0x00c9"("\xc3\x89")); // Test that `all` auto-decodes.
158 Checks if $(I _any) of the elements satisfies `pred`.
159 `!any` can be used to verify that $(I none) of the elements satisfy
161 This is sometimes called `exists` in other languages.
163 template any(alias pred = "a")
166 Returns `true` if and only if the input range `range` is non-empty
167 and $(I _any) value found in `range` satisfies the predicate
169 Performs (at most) $(BIGOH range.length) evaluations of `pred`.
171 bool any(Range)(Range range)
172 if (isInputRange!Range &&
173 (__traits(isTemplate, pred) || 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));
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))))
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))))
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))))
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);
746 // https://issues.dlang.org/show_bug.cgi?id=22582
749 assert([1, 2, 3].count!"a & 1" == 2);
753 Counts elements in the given
754 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
755 until the given predicate is true for one of the given `needles`.
758 pred = The predicate for determining when to stop counting.
760 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be
762 needles = Either a single element, or a
763 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
764 of elements, to be evaluated in turn against each
765 element in `haystack` under the given predicate.
767 Returns: The number of elements which must be popped from the front of
768 `haystack` before reaching an element for which
769 `startsWith!pred(haystack, needles)` is `true`. If
770 `startsWith!pred(haystack, needles)` is not `true` for any element in
771 `haystack`, then `-1` is returned. If only `pred` is provided,
772 `pred(haystack)` is tested for each element.
774 See_Also: $(REF indexOf, std,string)
776 ptrdiff_t countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles)
779 && isForwardRange!(Rs[0]) == isInputRange!(Rs[0])
780 && allSatisfy!(canTestStartsWith!(pred, R), Rs))
782 typeof(return) result;
784 static if (needles.length == 1)
786 static if (hasLength!R) //Note: Narrow strings don't have length.
788 //We delegate to find because find is very efficient.
789 //We store the length of the haystack so we don't have to save it.
790 auto len = haystack.length;
791 auto r2 = find!pred(haystack, needles[0]);
793 return cast(typeof(return)) (len - r2.length);
797 import std.range : dropOne;
799 if (needles[0].empty)
802 //Default case, slower route doing startsWith iteration
803 for ( ; !haystack.empty ; ++result )
805 //We compare the first elements of the ranges here before
806 //forwarding to startsWith. This avoids making useless saves to
807 //haystack/needle if they aren't even going to be mutated anyways.
808 //It also cuts down on the amount of pops on haystack.
809 if (binaryFun!pred(haystack.front, needles[0].front))
811 //Here, we need to save the needle before popping it.
812 //haystack we pop in all paths, so we do that, and then save.
814 if (startsWith!pred(haystack.save, needles[0].save.dropOne()))
826 static if (isForwardRange!Ri)
828 if (needles[i].empty)
835 static if (!isForwardRange!Ri)
840 for (; !haystack.empty ; ++result, haystack.popFront())
844 static if (isForwardRange!Ri)
846 t[i] = needles[i].save;
849 if (startsWith!pred(haystack.save, t.expand))
856 // Because of https://issues.dlang.org/show_bug.cgi?id=8804
857 // Avoids both "unreachable code" or "no return statement"
858 static if (isInfinite!R) assert(false, R.stringof ~ " must not be an"
859 ~ " infinite range");
864 ptrdiff_t countUntil(alias pred = "a == b", R, N)(R haystack, N needle)
865 if (isInputRange!R &&
866 is(typeof(binaryFun!pred(haystack.front, needle)) : bool))
868 bool pred2(ElementType!R a) { return binaryFun!pred(a, needle); }
869 return countUntil!pred2(haystack);
875 assert(countUntil("hello world", "world") == 6);
876 assert(countUntil("hello world", 'r') == 8);
877 assert(countUntil("hello world", "programming") == -1);
878 assert(countUntil("日本語", "本語") == 1);
879 assert(countUntil("日本語", '語') == 2);
880 assert(countUntil("日本語", "五") == -1);
881 assert(countUntil("日本語", '五') == -1);
882 assert(countUntil([0, 7, 12, 22, 9], [12, 22]) == 2);
883 assert(countUntil([0, 7, 12, 22, 9], 9) == 4);
884 assert(countUntil!"a > b"([0, 7, 12, 22, 9], 20) == 3);
889 import std.algorithm.iteration : filter;
890 import std.internal.test.dummyrange;
892 assert(countUntil("日本語", "") == 0);
893 assert(countUntil("日本語"d, "") == 0);
895 assert(countUntil("", "") == 0);
896 assert(countUntil("".filter!"true"(), "") == 0);
898 auto rf = [0, 20, 12, 22, 9].filter!"true"();
899 assert(rf.countUntil!"a > b"((int[]).init) == 0);
900 assert(rf.countUntil!"a > b"(20) == 3);
901 assert(rf.countUntil!"a > b"([20, 8]) == 3);
902 assert(rf.countUntil!"a > b"([20, 10]) == -1);
903 assert(rf.countUntil!"a > b"([20, 8, 0]) == -1);
905 auto r = new ReferenceForwardRange!int([0, 1, 2, 3, 4, 5, 6]);
906 auto r2 = new ReferenceForwardRange!int([3, 4]);
907 auto r3 = new ReferenceForwardRange!int([3, 5]);
908 assert(r.save.countUntil(3) == 3);
909 assert(r.save.countUntil(r2) == 3);
910 assert(r.save.countUntil(7) == -1);
911 assert(r.save.countUntil(r3) == -1);
916 assert(countUntil("hello world", "world", "asd") == 6);
917 assert(countUntil("hello world", "world", "ello") == 1);
918 assert(countUntil("hello world", "world", "") == 0);
919 assert(countUntil("hello world", "world", 'l') == 2);
923 ptrdiff_t countUntil(alias pred, R)(R haystack)
924 if (isInputRange!R &&
925 is(typeof(unaryFun!pred(haystack.front)) : bool))
928 static if (isRandomAccessRange!R)
930 //Optimized RA implementation. Since we want to count *and* iterate at
931 //the same time, it is more efficient this way.
932 static if (hasLength!R)
934 immutable len = cast(typeof(return)) haystack.length;
935 for ( ; i < len ; ++i )
936 if (unaryFun!pred(haystack[i])) return i;
938 else //if (isInfinite!R)
941 if (unaryFun!pred(haystack[i])) return i;
944 else static if (hasLength!R)
946 //For those odd ranges that have a length, but aren't RA.
947 //It is faster to quick find, and then compare the lengths
948 auto r2 = find!pred(haystack.save);
949 if (!r2.empty) return cast(typeof(return)) (haystack.length - r2.length);
951 else //Everything else
953 alias T = ElementType!R; //For narrow strings forces dchar iteration
954 foreach (T elem; haystack)
956 if (unaryFun!pred(elem)) return i;
961 // Because of https://issues.dlang.org/show_bug.cgi?id=8804
962 // Avoids both "unreachable code" or "no return statement"
963 static if (isInfinite!R) assert(false, R.stringof ~ " must not be an"
971 import std.ascii : isDigit;
972 import std.uni : isWhite;
974 assert(countUntil!(isWhite)("hello world") == 5);
975 assert(countUntil!(isDigit)("hello world") == -1);
976 assert(countUntil!"a > 20"([0, 7, 12, 22, 9]) == 3);
981 import std.internal.test.dummyrange;
986 ReferenceInputRange!int r;
987 r = new ReferenceInputRange!int([0, 1, 2, 3, 4, 5, 6]);
988 assert(r.countUntil(3) == 3);
989 r = new ReferenceInputRange!int([0, 1, 2, 3, 4, 5, 6]);
990 assert(r.countUntil(7) == -1);
994 auto r = new ReferenceForwardRange!int([0, 1, 2, 3, 4, 5, 6]);
995 assert(r.save.countUntil([3, 4]) == 3);
996 assert(r.save.countUntil(3) == 3);
997 assert(r.save.countUntil([3, 7]) == -1);
998 assert(r.save.countUntil(7) == -1);
1002 auto r = new ReferenceInfiniteForwardRange!int(0);
1003 assert(r.save.countUntil([3, 4]) == 3);
1004 assert(r.save.countUntil(3) == 3);
1009 Checks if the given range ends with (one of) the given needle(s).
1010 The reciprocal of `startsWith`.
1013 pred = The predicate to use for comparing elements between the range and
1017 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
1020 withOneOfThese = The needles to check against, which may be single
1021 elements, or bidirectional ranges of elements.
1023 withThis = The single element to check.
1026 0 if the needle(s) do not occur at the end of the given range;
1027 otherwise the position of the matching needle, that is, 1 if the range ends
1028 with `withOneOfThese[0]`, 2 if it ends with `withOneOfThese[1]`, and so
1031 In the case when no needle parameters are given, return `true` iff back of
1032 `doesThisStart` fulfils predicate `pred`.
1034 uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese)
1035 if (isBidirectionalRange!Range && Needles.length > 1 &&
1036 allSatisfy!(canTestStartsWith!(pred, Range), Needles))
1038 alias haystack = doesThisEnd;
1039 alias needles = withOneOfThese;
1041 // Make one pass looking for empty ranges in needles
1042 foreach (i, Unused; Needles)
1044 // Empty range matches everything
1045 static if (!is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool))
1047 if (needles[i].empty) return i + 1;
1051 for (; !haystack.empty; haystack.popBack())
1053 foreach (i, Unused; Needles)
1055 static if (is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool))
1058 if (binaryFun!pred(haystack.back, needles[i]))
1060 // found, but continue to account for one-element
1061 // range matches (consider endsWith("ab", "b",
1062 // 'b') should return 1, not 2).
1068 if (binaryFun!pred(haystack.back, needles[i].back))
1072 // This code executed on failure to match
1073 // Out with this guy, check for the others
1074 uint result = endsWith!pred(haystack, needles[0 .. i], needles[i + 1 .. $]);
1075 if (result > i) ++result;
1079 // If execution reaches this point, then the back matches for all
1080 // needles ranges. What we need to do now is to lop off the back of
1081 // all ranges involved and recurse.
1082 foreach (i, Unused; Needles)
1084 static if (is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool))
1086 // Test has passed in the previous loop
1091 needles[i].popBack();
1092 if (needles[i].empty) return i + 1;
1100 bool endsWith(alias pred = "a == b", R1, R2)(R1 doesThisEnd, R2 withThis)
1101 if (isBidirectionalRange!R1 &&
1102 isBidirectionalRange!R2 &&
1103 is(typeof(binaryFun!pred(doesThisEnd.back, withThis.back)) : bool))
1105 alias haystack = doesThisEnd;
1106 alias needle = withThis;
1108 static if (is(typeof(pred) : string))
1109 enum isDefaultPred = pred == "a == b";
1111 enum isDefaultPred = false;
1113 static if (isDefaultPred && isArray!R1 && isArray!R2 &&
1114 is(immutable ElementEncodingType!R1 == immutable ElementEncodingType!R2))
1116 if (haystack.length < needle.length) return false;
1118 return haystack[$ - needle.length .. $] == needle;
1122 import std.range : retro;
1123 return startsWith!pred(retro(doesThisEnd), retro(withThis));
1128 bool endsWith(alias pred = "a == b", R, E)(R doesThisEnd, E withThis)
1129 if (isBidirectionalRange!R &&
1130 is(typeof(binaryFun!pred(doesThisEnd.back, withThis)) : bool))
1132 if (doesThisEnd.empty)
1135 static if (is(typeof(pred) : string))
1136 enum isDefaultPred = pred == "a == b";
1138 enum isDefaultPred = false;
1140 alias predFunc = binaryFun!pred;
1142 // auto-decoding special case
1143 static if (isNarrowString!R)
1145 // statically determine decoding is unnecessary to evaluate pred
1146 static if (isDefaultPred && isSomeChar!E && E.sizeof <= ElementEncodingType!R.sizeof)
1147 return doesThisEnd[$ - 1] == withThis;
1148 // specialize for ASCII as to not change previous behavior
1151 if (withThis <= 0x7F)
1152 return predFunc(doesThisEnd[$ - 1], withThis);
1154 return predFunc(doesThisEnd.back, withThis);
1159 return predFunc(doesThisEnd.back, withThis);
1164 bool endsWith(alias pred, R)(R doesThisEnd)
1165 if (isInputRange!R &&
1166 ifTestable!(typeof(doesThisEnd.front), unaryFun!pred))
1168 return !doesThisEnd.empty && unaryFun!pred(doesThisEnd.back);
1174 import std.ascii : isAlpha;
1175 assert("abc".endsWith!(a => a.isAlpha));
1176 assert("abc".endsWith!isAlpha);
1178 assert(!"ab1".endsWith!(a => a.isAlpha));
1180 assert(!"ab1".endsWith!isAlpha);
1181 assert(!"".endsWith!(a => a.isAlpha));
1183 import std.algorithm.comparison : among;
1184 assert("abc".endsWith!(a => a.among('c', 'd') != 0));
1185 assert(!"abc".endsWith!(a => a.among('a', 'b') != 0));
1187 assert(endsWith("abc", ""));
1188 assert(!endsWith("abc", "b"));
1189 assert(endsWith("abc", "a", 'c') == 2);
1190 assert(endsWith("abc", "c", "a") == 1);
1191 assert(endsWith("abc", "c", "c") == 1);
1192 assert(endsWith("abc", "bc", "c") == 2);
1193 assert(endsWith("abc", "x", "c", "b") == 2);
1194 assert(endsWith("abc", "x", "aa", "bc") == 3);
1195 assert(endsWith("abc", "x", "aaa", "sab") == 0);
1196 assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);
1201 import std.algorithm.iteration : filterBidirectional;
1202 import std.conv : to;
1203 import std.meta : AliasSeq;
1205 static foreach (S; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
1206 (){ // workaround slow optimizations for large functions
1207 // https://issues.dlang.org/show_bug.cgi?id=2396
1208 assert(!endsWith(to!S("abc"), 'a'));
1209 assert(endsWith(to!S("abc"), 'a', 'c') == 2);
1210 assert(!endsWith(to!S("abc"), 'x', 'n', 'b'));
1211 assert(endsWith(to!S("abc"), 'x', 'n', 'c') == 3);
1212 assert(endsWith(to!S("abc\uFF28"), 'a', '\uFF28', 'c') == 2);
1214 static foreach (T; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
1217 assert(endsWith(to!S("abc"), to!T("")));
1218 assert(!endsWith(to!S("abc"), to!T("a")));
1219 assert(!endsWith(to!S("abc"), to!T("b")));
1220 assert(endsWith(to!S("abc"), to!T("bc"), 'c') == 2);
1221 assert(endsWith(to!S("abc"), to!T("a"), "c") == 2);
1222 assert(endsWith(to!S("abc"), to!T("c"), "a") == 1);
1223 assert(endsWith(to!S("abc"), to!T("c"), "c") == 1);
1224 assert(endsWith(to!S("abc"), to!T("x"), 'c', "b") == 2);
1225 assert(endsWith(to!S("abc"), 'x', to!T("aa"), "bc") == 3);
1226 assert(endsWith(to!S("abc"), to!T("x"), "aaa", "sab") == 0);
1227 assert(endsWith(to!S("abc"), to!T("x"), "aaa", "c", "sab") == 3);
1228 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("l\uFF4co")));
1229 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("lo"), to!T("l\uFF4co")) == 2);
1232 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("l\uFF4co")));
1233 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("lo"), to!T("l\uFF4co")) == 2);
1234 assert(endsWith(to!S("日本語"), to!T("本語")));
1235 assert(endsWith(to!S("日本語"), to!T("日本語")));
1236 assert(!endsWith(to!S("本語"), to!T("日本語")));
1239 assert(endsWith(to!S(""), T.init));
1240 assert(!endsWith(to!S(""), 'a'));
1241 assert(endsWith(to!S("a"), T.init));
1242 assert(endsWith(to!S("a"), T.init, "") == 1);
1243 assert(endsWith(to!S("a"), T.init, 'a') == 1);
1244 assert(endsWith(to!S("a"), 'a', T.init) == 2);
1248 static foreach (T; AliasSeq!(int, short))
1250 immutable arr = cast(T[])[0, 1, 2, 3, 4, 5];
1253 assert(endsWith(arr, cast(int[]) null));
1254 assert(!endsWith(arr, 0));
1255 assert(!endsWith(arr, 4));
1256 assert(endsWith(arr, 5));
1257 assert(endsWith(arr, 0, 4, 5) == 3);
1258 assert(endsWith(arr, [5]));
1259 assert(endsWith(arr, [4, 5]));
1260 assert(endsWith(arr, [4, 5], 7) == 1);
1261 assert(!endsWith(arr, [2, 4, 5]));
1262 assert(endsWith(arr, [2, 4, 5], [3, 4, 5]) == 2);
1264 //Normal input range
1265 assert(!endsWith(filterBidirectional!"true"(arr), 4));
1266 assert(endsWith(filterBidirectional!"true"(arr), 5));
1267 assert(endsWith(filterBidirectional!"true"(arr), [5]));
1268 assert(endsWith(filterBidirectional!"true"(arr), [4, 5]));
1269 assert(endsWith(filterBidirectional!"true"(arr), [4, 5], 7) == 1);
1270 assert(!endsWith(filterBidirectional!"true"(arr), [2, 4, 5]));
1271 assert(endsWith(filterBidirectional!"true"(arr), [2, 4, 5], [3, 4, 5]) == 2);
1272 assert(endsWith(arr, filterBidirectional!"true"([4, 5])));
1273 assert(endsWith(arr, filterBidirectional!"true"([4, 5]), 7) == 1);
1274 assert(!endsWith(arr, filterBidirectional!"true"([2, 4, 5])));
1275 assert(endsWith(arr, [2, 4, 5], filterBidirectional!"true"([3, 4, 5])) == 2);
1278 assert(endsWith!("a%10 == b%10")(arr, [14, 15]));
1279 assert(!endsWith!("a%10 == b%10")(arr, [15, 14]));
1285 //example from https://issues.dlang.org/show_bug.cgi?id=19727
1286 import std.path : asRelativePath;
1287 string[] ext = ["abc", "def", "ghi"];
1288 string path = "/foo/file.def";
1289 assert(ext.any!(e => path.asRelativePath("/foo").endsWith(e)) == true);
1290 assert(ext.any!(e => path.asRelativePath("/foo").startsWith(e)) == false);
1293 private enum bool hasConstEmptyMember(T) = is(typeof(((const T* a) => (*a).empty)(null)) : bool);
1296 Iterates the passed range and selects the extreme element with `less`.
1297 If the extreme element occurs multiple time, the first occurrence will be
1301 map = custom accessor for the comparison key
1302 selector = custom mapping for the extrema selection
1303 r = Range from which the extreme value will be selected
1304 seedElement = custom seed to use as initial element
1307 The extreme value according to `map` and `selector` of the passed-in values.
1309 private auto extremum(alias map, alias selector = "a < b", Range)(Range r)
1310 if (isInputRange!Range && !isInfinite!Range &&
1311 is(typeof(unaryFun!map(ElementType!(Range).init))))
1314 assert(!r.empty, "r is an empty range");
1318 import std.typecons : Rebindable2;
1320 alias Element = ElementType!Range;
1321 auto seed = Rebindable2!Element(r.front);
1323 return extremum!(map, selector)(r, seed.get);
1326 private auto extremum(alias map, alias selector = "a < b", Range,
1327 RangeElementType = ElementType!Range)
1328 (Range r, RangeElementType seedElement)
1329 if (isInputRange!Range && !isInfinite!Range &&
1330 !is(CommonType!(ElementType!Range, RangeElementType) == void) &&
1331 is(typeof(unaryFun!map(ElementType!(Range).init))))
1333 import std.typecons : Rebindable2;
1335 alias mapFun = unaryFun!map;
1336 alias selectorFun = binaryFun!selector;
1338 alias Element = ElementType!Range;
1339 alias CommonElement = CommonType!(Element, RangeElementType);
1340 auto extremeElement = Rebindable2!CommonElement(seedElement);
1342 // if we only have one statement in the loop, it can be optimized a lot better
1343 static if (__traits(isSame, map, a => a))
1345 // direct access via a random access range is faster
1346 static if (isRandomAccessRange!Range)
1348 foreach (const i; 0 .. r.length)
1350 if (selectorFun(r[i], extremeElement.get))
1352 extremeElement = r[i];
1360 if (selectorFun(r.front, extremeElement.get))
1362 extremeElement = r.front;
1370 alias MapType = Unqual!(typeof(mapFun(CommonElement.init)));
1371 MapType extremeElementMapped = mapFun(extremeElement.get);
1373 // direct access via a random access range is faster
1374 static if (isRandomAccessRange!Range)
1376 foreach (const i; 0 .. r.length)
1378 MapType mapElement = mapFun(r[i]);
1379 if (selectorFun(mapElement, extremeElementMapped))
1381 extremeElement = r[i];
1382 extremeElementMapped = mapElement;
1390 MapType mapElement = mapFun(r.front);
1391 if (selectorFun(mapElement, extremeElementMapped))
1393 extremeElement = r.front;
1394 extremeElementMapped = mapElement;
1400 return extremeElement.get;
1403 private auto extremum(alias selector = "a < b", Range)(Range r)
1404 if (isInputRange!Range && !isInfinite!Range &&
1405 !is(typeof(unaryFun!selector(ElementType!(Range).init))))
1407 return extremum!(a => a, selector)(r);
1410 // if we only have one statement in the loop it can be optimized a lot better
1411 private auto extremum(alias selector = "a < b", Range,
1412 RangeElementType = ElementType!Range)
1413 (Range r, RangeElementType seedElement)
1414 if (isInputRange!Range && !isInfinite!Range &&
1415 !is(CommonType!(ElementType!Range, RangeElementType) == void) &&
1416 !is(typeof(unaryFun!selector(ElementType!(Range).init))))
1418 return extremum!(a => a, selector)(r, seedElement);
1423 // allows a custom map to select the extremum
1424 assert([[0, 4], [1, 2]].extremum!"a[0]" == [0, 4]);
1425 assert([[0, 4], [1, 2]].extremum!"a[1]" == [1, 2]);
1427 // allows a custom selector for comparison
1428 assert([[0, 4], [1, 2]].extremum!("a[0]", "a > b") == [1, 2]);
1429 assert([[0, 4], [1, 2]].extremum!("a[1]", "a > b") == [0, 4]);
1431 // use a custom comparator
1432 import std.math.operations : cmp;
1433 assert([-2., 0, 5].extremum!cmp == 5.0);
1434 assert([-2., 0, 2].extremum!`cmp(a, b) < 0` == -2.0);
1437 import std.range : enumerate;
1438 assert([-3., 0, 5].enumerate.extremum!(`a.value`, cmp) == tuple(2, 5.0));
1439 assert([-2., 0, 2].enumerate.extremum!(`a.value`, `cmp(a, b) < 0`) == tuple(0, -2.0));
1441 // seed with a custom value
1443 assert(arr.extremum(1) == 1);
1446 @safe pure nothrow unittest
1450 assert(arr2d.extremum([1]) == [1]);
1452 // allow seeds of different types (implicit casting)
1453 assert(extremum([2, 3, 4], 1.5) == 1.5);
1458 import std.range : enumerate, iota;
1461 assert(iota(1, 5).extremum() == 1);
1462 assert(iota(2, 5).enumerate.extremum!"a.value" == tuple(0, 2));
1464 // should work with const
1465 const(int)[] immArr = [2, 1, 3];
1466 assert(immArr.extremum == 1);
1468 // should work with immutable
1469 immutable(int)[] immArr2 = [2, 1, 3];
1470 assert(immArr2.extremum == 1);
1473 assert(["b", "a", "c"].extremum == "a");
1475 // with all dummy ranges
1476 import std.internal.test.dummyrange;
1477 foreach (DummyType; AllDummyRanges)
1480 assert(d.extremum == 1);
1481 assert(d.extremum!(a => a) == 1);
1482 assert(d.extremum!`a > b` == 10);
1483 assert(d.extremum!(a => a, `a > b`) == 10);
1487 enum ctExtremum = iota(1, 5).extremum;
1488 assert(ctExtremum == 1);
1491 @nogc @safe nothrow pure unittest
1493 static immutable arr = [7, 3, 4, 2, 1, 8];
1494 assert(arr.extremum == 1);
1496 static immutable arr2d = [[1, 9], [3, 1], [4, 2]];
1497 assert(arr2d.extremum!"a[1]" == arr2d[1]);
1500 // https://issues.dlang.org/show_bug.cgi?id=17982
1506 this(int val){ this.val = val; }
1509 const(B) doStuff(const(B)[] v)
1511 return v.extremum!"a.val";
1513 assert(doStuff([new B(1), new B(0), new B(2)]).val == 0);
1515 const(B)[] arr = [new B(0), new B(1)];
1516 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
1517 assert(arr.extremum!"a.val".val == 0);
1520 // https://issues.dlang.org/show_bug.cgi?id=22786
1521 @nogc @safe nothrow pure unittest
1525 immutable int value;
1528 assert([S(5), S(6)].extremum!"a.value" == S(5));
1531 // https://issues.dlang.org/show_bug.cgi?id=24027
1532 @safe nothrow unittest
1543 auto test = new A(5);
1545 assert(maxElement!"a.a"(arr) is test);
1550 Finds an element `e` of an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1551 where `pred(e)` is `true`.
1555 $(LI `find` behaves similarly to `dropWhile` in other languages.)
1556 $(LI To _find the *last* matching element in a
1557 $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives) `haystack`,
1558 call `find!pred(retro(haystack))`. See $(REF retro, std,range).)
1562 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`.
1566 pred = The predicate to match an element.
1567 haystack = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1571 `haystack` advanced such that the front element satisfies `pred`.
1572 If no such element exists, returns an empty `haystack`.
1574 InputRange find(alias pred, InputRange)(InputRange haystack)
1575 if (isInputRange!InputRange)
1577 alias R = InputRange;
1578 alias predFun = unaryFun!pred;
1579 static if (isNarrowString!R)
1581 import std.utf : decode;
1583 immutable len = haystack.length;
1584 size_t i = 0, next = 0;
1587 if (predFun(decode(haystack, next)))
1588 return haystack[i .. $];
1591 return haystack[$ .. $];
1596 for ( ; !haystack.empty; haystack.popFront() )
1598 if (predFun(haystack.front))
1608 auto arr = [ 1, 2, 3, 4, 1 ];
1609 assert(find!("a > 2")(arr) == [ 3, 4, 1 ]);
1611 // with predicate alias
1612 bool pred(int e) => e + 1 > 1.5;
1613 assert(find!(pred)(arr) == arr);
1618 int[] r = [ 1, 2, 3 ];
1619 assert(find!(a=>a > 2)(r) == [3]);
1620 bool pred(int x) { return x + 1 > 1.5; }
1621 assert(find!(pred)(r) == r);
1623 assert(find!(a=>a > 'v')("hello world") == "world");
1624 assert(find!(a=>a%4 == 0)("日本語") == "本語");
1628 Finds an individual element in an $(REF_ALTTEXT input range, isInputRange, std,range,primitives).
1629 Elements of `haystack` are compared with `needle` by using predicate
1630 `pred` with `pred(haystack.front, needle)`.
1631 The predicate is passed to $(REF binaryFun, std, functional), and can either accept a
1632 string, or any callable that can be executed via `pred(element, element)`.
1634 If `haystack` is a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives),
1635 `needle` can be a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) too.
1636 In this case `startsWith!pred(haystack, needle)` is evaluated on each evaluation.
1638 $(NOTE To find the first element $(I not) matching the needle, use predicate `"a != b"`.)
1641 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`.
1642 There are specializations that improve performance by taking
1643 advantage of $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives)
1644 or $(REF_ALTTEXT random access, isRandomAccessRange, std,range,primitives)
1645 ranges (where possible).
1649 pred = The predicate for comparing each element with the needle, defaulting to equality `"a == b"`.
1650 haystack = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1652 needle = The element searched for.
1655 `haystack` advanced such that the front element is the one searched for;
1656 that is, until `binaryFun!pred(haystack.front, needle)` is `true`. If no
1657 such position exists, returns an empty `haystack`.
1659 See_Also: $(LREF findAdjacent), $(LREF findAmong), $(LREF findSkip), $(LREF findSplit), $(LREF startsWith)
1661 InputRange find(alias pred = "a == b", InputRange, Element)(InputRange haystack, scope Element needle)
1662 if (isInputRange!InputRange &&
1663 is (typeof(binaryFun!pred(haystack.front, needle)) : bool) &&
1664 !is (typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
1666 alias R = InputRange;
1668 alias predFun = binaryFun!pred;
1669 static if (is(typeof(pred == "a == b")))
1670 enum isDefaultPred = pred == "a == b";
1672 enum isDefaultPred = false;
1673 enum isIntegralNeedle = isSomeChar!E || isIntegral!E || isBoolean!E;
1675 alias EType = ElementType!R;
1677 // If the haystack is a SortedRange we can use binary search to find the needle.
1678 // Works only for the default find predicate and any SortedRange predicate.
1679 // https://issues.dlang.org/show_bug.cgi?id=8829
1680 import std.range : SortedRange;
1681 static if (is(InputRange : SortedRange!TT, TT) && isDefaultPred)
1683 auto lb = haystack.lowerBound(needle);
1684 if (lb.length == haystack.length || haystack[lb.length] != needle)
1685 return haystack[$ .. $];
1687 return haystack[lb.length .. $];
1689 else static if (isNarrowString!R)
1691 alias EEType = ElementEncodingType!R;
1692 alias UEEType = Unqual!EEType;
1694 //These are two special cases which can search without decoding the UTF stream.
1695 static if (isDefaultPred && isIntegralNeedle)
1697 import std.utf : canSearchInCodeUnits;
1699 //This special case deals with UTF8 search, when the needle
1700 //is represented by a single code point.
1701 //Note: "needle <= 0x7F" properly handles sign via unsigned promotion
1702 static if (is(UEEType == char))
1704 if (!__ctfe && canSearchInCodeUnits!char(needle))
1706 static inout(R) trustedMemchr(ref return scope inout(R) haystack,
1707 ref const scope E needle) @trusted nothrow pure
1709 import core.stdc.string : memchr;
1710 auto ptr = memchr(haystack.ptr, needle, haystack.length);
1712 haystack[cast(char*) ptr - haystack.ptr .. $] :
1715 return trustedMemchr(haystack, needle);
1719 //Ditto, but for UTF16
1720 static if (is(UEEType == wchar))
1722 if (canSearchInCodeUnits!wchar(needle))
1724 foreach (i, ref EEType e; haystack)
1727 return haystack[i .. $];
1729 return haystack[$ .. $];
1734 //Previous conditional optimizations did not succeed. Fallback to
1735 //unconditional implementations
1736 static if (isDefaultPred)
1738 import std.utf : encode;
1740 //In case of default pred, it is faster to do string/string search.
1741 UEEType[is(UEEType == char) ? 4 : 2] buf;
1743 size_t len = encode(buf, needle);
1744 return find(haystack, buf[0 .. len]);
1748 import std.utf : decode;
1750 //Explicit pred: we must test each character by the book.
1751 //We choose a manual decoding approach, because it is faster than
1752 //the built-in foreach, or doing a front/popFront for-loop.
1753 immutable len = haystack.length;
1754 size_t i = 0, next = 0;
1757 if (predFun(decode(haystack, next), needle))
1758 return haystack[i .. $];
1761 return haystack[$ .. $];
1764 else static if (isArray!R)
1766 // https://issues.dlang.org/show_bug.cgi?id=10403 optimization
1767 static if (isDefaultPred && isIntegral!EType && EType.sizeof == 1 && isIntegralNeedle)
1769 import std.algorithm.comparison : max, min;
1771 R findHelper(return scope ref R haystack, ref E needle) @trusted nothrow pure
1773 import core.stdc.string : memchr;
1776 //Note: we use "min/max" to handle sign mismatch.
1777 if (min(EType.min, needle) == EType.min &&
1778 max(EType.max, needle) == EType.max)
1780 ptr = cast(EType*) memchr(haystack.ptr, needle,
1785 haystack[ptr - haystack.ptr .. $] :
1790 return findHelper(haystack, needle);
1793 //Default implementation.
1794 foreach (i, ref e; haystack)
1795 if (predFun(e, needle))
1796 return haystack[i .. $];
1797 return haystack[$ .. $];
1801 //Everything else. Walk.
1802 for ( ; !haystack.empty; haystack.popFront() )
1804 if (predFun(haystack.front, needle))
1814 import std.range.primitives;
1816 auto arr = [1, 2, 4, 4, 4, 4, 5, 6, 9];
1817 assert(arr.find(4) == [4, 4, 4, 4, 5, 6, 9]);
1818 assert(arr.find(1) == arr);
1819 assert(arr.find(9) == [9]);
1820 assert(arr.find!((e, n) => e > n)(4) == [5, 6, 9]);
1821 assert(arr.find!((e, n) => e < n)(4) == arr);
1822 assert(arr.find(0).empty);
1823 assert(arr.find(10).empty);
1824 assert(arr.find(8).empty);
1826 assert(find("hello, world", ',') == ", world");
1829 /// Case-insensitive find of a string
1832 import std.range.primitives;
1833 import std.uni : toLower;
1835 string[] s = ["Hello", "world", "!"];
1836 assert(s.find!((e, n) => toLower(e) == n)("hello") == s);
1841 import std.algorithm.comparison : equal;
1842 import std.container : SList;
1844 auto lst = SList!int(1, 2, 5, 7, 3);
1845 assert(lst.front == 1);
1846 auto r = find(lst[], 5);
1847 assert(equal(r, SList!int(5, 7, 3)[]));
1848 assert(find([1, 2, 3, 5], 4).empty);
1849 assert(equal(find!"a > b"("hello", 'k'), "llo"));
1852 @safe pure nothrow unittest
1854 assert(!find ([1, 2, 3], 2).empty);
1855 assert(!find!((a,b)=>a == b)([1, 2, 3], 2).empty);
1856 assert(!find ([1, 2, 3], 2).empty);
1857 assert(!find!((a,b)=>a == b)([1, 2, 3], 2).empty);
1862 import std.meta : AliasSeq;
1863 static foreach (R; AliasSeq!(string, wstring, dstring))
1865 static foreach (E; AliasSeq!(char, wchar, dchar))
1867 assert(find ("hello world", 'w') == "world");
1868 assert(find!((a,b)=>a == b)("hello world", 'w') == "world");
1869 assert(find ("日c語", 'c') == "c語");
1870 assert(find!((a,b)=>a == b)("日c語", 'c') == "c語");
1871 assert(find ("0123456789", 'A').empty);
1872 static if (E.sizeof >= 2)
1874 assert(find ("日本語", '本') == "本語");
1875 assert(find!((a,b)=>a == b)("日本語", '本') == "本語");
1884 static assert(find("abc", 'b') == "bc");
1885 static assert(find("日b語", 'b') == "b語");
1886 static assert(find("日本語", '本') == "本語");
1887 static assert(find([1, 2, 3], 2) == [2, 3]);
1889 static assert(find ([1, 2, 3], 2));
1890 static assert(find!((a,b)=>a == b)([1, 2, 3], 2));
1891 static assert(find ([1, 2, 3], 2));
1892 static assert(find!((a,b)=>a == b)([1, 2, 3], 2));
1897 import std.exception : assertCTFEable;
1898 import std.meta : AliasSeq;
1900 void dg() @safe pure nothrow
1902 byte[] sarr = [1, 2, 3, 4];
1903 ubyte[] uarr = [1, 2, 3, 4];
1904 static foreach (arr; AliasSeq!(sarr, uarr))
1906 static foreach (T; AliasSeq!(byte, ubyte, int, uint))
1908 assert(find(arr, cast(T) 3) == arr[2 .. $]);
1909 assert(find(arr, cast(T) 9) == arr[$ .. $]);
1911 assert(find(arr, 256) == arr[$ .. $]);
1918 // https://issues.dlang.org/show_bug.cgi?id=11603
1921 enum Foo : ubyte { A }
1922 assert([Foo.A].find(Foo.A).empty == false);
1925 assert([x].find(x).empty == false);
1929 R1 find(alias pred = "a == b", R1, R2)(R1 haystack, scope R2 needle)
1930 if (isForwardRange!R1 && isForwardRange!R2
1931 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
1933 static if (!isRandomAccessRange!R1)
1935 static if (is(typeof(pred == "a == b")) && pred == "a == b" && isSomeString!R1 && isSomeString!R2
1936 && haystack[0].sizeof == needle[0].sizeof)
1938 // return cast(R1) find(representation(haystack), representation(needle));
1939 // Specialization for simple string search
1940 alias Representation =
1941 Select!(haystack[0].sizeof == 1, ubyte[],
1942 Select!(haystack[0].sizeof == 2, ushort[], uint[]));
1943 // Will use the array specialization
1944 static TO force(TO, T)(inout T r) @trusted { return cast(TO) r; }
1945 return force!R1(.find!(pred, Representation, Representation)
1946 (force!Representation(haystack), force!Representation(needle)));
1950 return simpleMindedFind!pred(haystack, needle);
1953 else static if (!isBidirectionalRange!R2 || !hasSlicing!R1)
1955 static if (!is(ElementType!R1 == ElementType!R2))
1957 return simpleMindedFind!pred(haystack, needle);
1961 // Prepare the search with needle's first element
1965 haystack = .find!pred(haystack, needle.front);
1967 static if (hasLength!R1 && hasLength!R2 && is(typeof(takeNone(haystack)) == R1))
1969 if (needle.length > haystack.length)
1970 return takeNone(haystack);
1979 size_t matchLen = 1;
1981 // Loop invariant: haystack[0 .. matchLen] matches everything in
1982 // the initial needle that was popped out of needle.
1985 // Extend matchLength as much as possible
1988 import std.range : takeNone;
1990 if (needle.empty || haystack.empty)
1993 static if (hasLength!R1 && is(typeof(takeNone(haystack)) == R1))
1995 if (matchLen == haystack.length)
1996 return takeNone(haystack);
1999 if (!binaryFun!pred(haystack[matchLen], needle.front))
2006 auto bestMatch = haystack[0 .. matchLen];
2007 haystack.popFront();
2008 haystack = .find!pred(haystack, bestMatch);
2012 else // static if (hasSlicing!R1 && isBidirectionalRange!R2)
2014 if (needle.empty) return haystack;
2016 static if (hasLength!R2)
2018 immutable needleLength = needle.length;
2022 immutable needleLength = walkLength(needle.save);
2024 if (needleLength > haystack.length)
2026 return haystack[haystack.length .. haystack.length];
2028 // Optimization in case the ranges are both SortedRanges.
2029 // Binary search can be used to find the first occurence
2030 // of the first element of the needle in haystack.
2031 // When it is found O(walklength(needle)) steps are performed.
2032 // https://issues.dlang.org/show_bug.cgi?id=8829 enhancement
2033 import std.algorithm.comparison : mismatch;
2034 import std.range : SortedRange;
2035 static if (is(R1 == R2)
2036 && is(R1 : SortedRange!TT, TT)
2037 && pred == "a == b")
2039 auto needleFirstElem = needle[0];
2040 auto partitions = haystack.trisect(needleFirstElem);
2041 auto firstElemLen = partitions[1].length;
2044 if (firstElemLen == 0)
2045 return haystack[$ .. $];
2047 while (needle.front() == needleFirstElem)
2052 if (count > firstElemLen)
2053 return haystack[$ .. $];
2056 auto m = mismatch(partitions[2], needle);
2059 return haystack[partitions[0].length + partitions[1].length - count .. $];
2061 else static if (isRandomAccessRange!R2)
2063 immutable lastIndex = needleLength - 1;
2064 auto last = needle[lastIndex];
2065 size_t j = lastIndex, skip = 0;
2066 for (; j < haystack.length;)
2068 if (!binaryFun!pred(haystack[j], last))
2073 immutable k = j - lastIndex;
2074 // last elements match
2075 for (size_t i = 0;; ++i)
2078 return haystack[k .. haystack.length];
2079 if (!binaryFun!pred(haystack[k + i], needle[i]))
2085 while (skip < needleLength && needle[needleLength - 1 - skip] != needle[needleLength - 1])
2096 // auto needleBack = moveBack(needle);
2097 // Stage 1: find the step
2099 auto needleBack = needle.back;
2101 for (auto i = needle.save; !i.empty && i.back != needleBack;
2102 i.popBack(), ++step)
2105 // Stage 2: linear find
2106 size_t scout = needleLength - 1;
2109 if (scout >= haystack.length)
2111 if (!binaryFun!pred(haystack[scout], needleBack))
2116 // Found a match with the last element in the needle
2117 auto cand = haystack[scout + 1 - needleLength .. haystack.length];
2118 if (startsWith!pred(cand, needle))
2126 return haystack[haystack.length .. haystack.length];
2133 import std.container : SList;
2134 import std.range.primitives : empty;
2135 import std.typecons : Tuple;
2137 assert(find("hello, world", "World").empty);
2138 assert(find("hello, world", "wo") == "world");
2139 assert([1, 2, 3, 4].find(SList!int(2, 3)[]) == [2, 3, 4]);
2140 alias C = Tuple!(int, "x", int, "y");
2141 auto a = [C(1,0), C(2,0), C(3,1), C(4,0)];
2142 assert(a.find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
2143 assert(a[1 .. $].find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
2148 import std.container : SList;
2149 alias C = Tuple!(int, "x", int, "y");
2150 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)]);
2153 // https://issues.dlang.org/show_bug.cgi?id=12470
2156 import std.array : replace;
2157 inout(char)[] sanitize(inout(char)[] p)
2159 return p.replace("\0", " ");
2161 assert(sanitize("O\x00o") == "O o");
2166 import std.algorithm.comparison : equal;
2167 import std.container : SList;
2169 auto lst = SList!int(1, 2, 5, 7, 3);
2170 static assert(isForwardRange!(int[]));
2171 static assert(isForwardRange!(typeof(lst[])));
2172 auto r = find(lst[], [2, 5]);
2173 assert(equal(r, SList!int(2, 5, 7, 3)[]));
2178 import std.range : assumeSorted;
2180 auto r1 = assumeSorted([1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 8, 10]);
2181 auto r2 = assumeSorted([3, 3, 4, 5, 6, 7, 8, 8]);
2182 auto r3 = assumeSorted([3, 4, 5, 6, 7, 8]);
2183 auto r4 = assumeSorted([4, 5, 6]);
2184 auto r5 = assumeSorted([12, 13]);
2185 auto r6 = assumeSorted([8, 8, 10, 11]);
2186 auto r7 = assumeSorted([3, 3, 3, 3, 3, 3, 3]);
2188 assert(find(r1, r2) == assumeSorted([3, 3, 4, 5, 6, 7, 8, 8, 8, 10]));
2189 assert(find(r1, r3) == assumeSorted([3, 4, 5, 6, 7, 8, 8, 8, 10]));
2190 assert(find(r1, r4) == assumeSorted([4, 5, 6, 7, 8, 8, 8, 10]));
2191 assert(find(r1, r5).empty());
2192 assert(find(r1, r6).empty());
2193 assert(find(r1, r7).empty());
2198 import std.algorithm.comparison : equal;
2199 // @@@BUG@@@ removing static below makes unittest fail
2200 static struct BiRange
2203 @property bool empty() { return payload.empty; }
2204 @property BiRange save() { return this; }
2205 @property ref int front() { return payload[0]; }
2206 @property ref int back() { return payload[$ - 1]; }
2207 void popFront() { return payload.popFront(); }
2208 void popBack() { return payload.popBack(); }
2210 auto r = BiRange([1, 2, 3, 10, 11, 4]);
2211 assert(equal(find(r, [10, 11]), [10, 11, 4]));
2216 import std.container : SList;
2218 assert(find([ 1, 2, 3 ], SList!int(2, 3)[]) == [ 2, 3 ]);
2219 assert(find([ 1, 2, 1, 2, 3, 3 ], SList!int(2, 3)[]) == [ 2, 3, 3 ]);
2222 // https://issues.dlang.org/show_bug.cgi?id=8334
2225 import std.algorithm.iteration : filter;
2228 auto haystack = [1, 2, 3, 4, 1, 9, 12, 42];
2229 auto needle = [12, 42, 27];
2231 //different overload of find, but it's the base case.
2232 assert(find(haystack, needle).empty);
2234 assert(find(haystack, takeExactly(filter!"true"(needle), 3)).empty);
2235 assert(find(haystack, filter!"true"(needle)).empty);
2238 // https://issues.dlang.org/show_bug.cgi?id=11013
2241 assert(find!"a == a"("abc","abc") == "abc");
2244 // Internally used by some find() overloads above
2245 private R1 simpleMindedFind(alias pred, R1, R2)(R1 haystack, scope R2 needle)
2247 enum estimateNeedleLength = hasLength!R1 && !hasLength!R2;
2249 static if (hasLength!R1)
2251 static if (!hasLength!R2)
2252 size_t estimatedNeedleLength = 0;
2254 immutable size_t estimatedNeedleLength = needle.length;
2257 bool haystackTooShort()
2259 static if (estimateNeedleLength)
2261 return haystack.length < estimatedNeedleLength;
2265 return haystack.empty;
2270 for (;; haystack.popFront())
2272 if (haystackTooShort())
2275 static if (hasLength!R1)
2277 static if (is(typeof(haystack[haystack.length ..
2278 haystack.length]) : R1))
2279 return haystack[haystack.length .. haystack.length];
2285 assert(haystack.empty, "Haystack must be empty by now");
2289 static if (estimateNeedleLength)
2290 size_t matchLength = 0;
2291 for (auto h = haystack.save, n = needle.save;
2293 h.popFront(), n.popFront())
2295 if (h.empty || !binaryFun!pred(h.front, n.front))
2297 // Failed searching n in h
2298 static if (estimateNeedleLength)
2300 if (estimatedNeedleLength < matchLength)
2301 estimatedNeedleLength = matchLength;
2305 static if (estimateNeedleLength)
2315 // Test simpleMindedFind for the case where both haystack and needle have
2322 // This is what triggers https://issues.dlang.org/show_bug.cgi?id=7992.
2323 @property size_t length() const { return _impl.length; }
2324 @property void length(size_t len) { _impl.length = len; }
2326 // This is for conformance to the forward range API (we deliberately
2327 // make it non-random access so that we will end up in
2328 // simpleMindedFind).
2329 @property bool empty() const { return _impl.empty; }
2330 @property dchar front() const { return _impl.front; }
2331 void popFront() { _impl.popFront(); }
2332 @property CustomString save() { return this; }
2335 // If https://issues.dlang.org/show_bug.cgi?id=7992 occurs, this will throw an exception from calling
2336 // popFront() on an empty range.
2337 auto r = find(CustomString("a"), CustomString("b"));
2342 Finds two or more `needles` into a `haystack`. The predicate $(D
2343 pred) is used throughout to compare elements. By default, elements are
2344 compared for equality.
2348 pred = The predicate to use for comparing elements.
2350 haystack = The target of the search. Must be an input range.
2351 If any of `needles` is a range with elements comparable to
2352 elements in `haystack`, then `haystack` must be a
2353 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2354 such that the search can backtrack.
2356 needles = One or more items to search for. Each of `needles` must
2357 be either comparable to one element in `haystack`, or be itself a
2358 forward range with elements comparable with elements in
2363 A tuple containing `haystack` positioned to match one of the
2364 needles and also the 1-based index of the matching element in $(D
2365 needles) (0 if none of `needles` matched, 1 if `needles[0]`
2366 matched, 2 if `needles[1]` matched...). The first needle to be found
2367 will be the one that matches. If multiple needles are found at the
2368 same spot in the range, then the shortest one is the one which matches
2369 (if multiple needles of the same length are found at the same spot (e.g
2370 `"a"` and `'a'`), then the left-most of them in the argument list
2373 The relationship between `haystack` and `needles` simply means
2374 that one can e.g. search for individual `int`s or arrays of $(D
2375 int)s in an array of `int`s. In addition, if elements are
2376 individually comparable, searches of heterogeneous types are allowed
2377 as well: a `double[]` can be searched for an `int` or a $(D
2378 short[]), and conversely a `long` can be searched for a `float`
2379 or a `double[]`. This makes for efficient searches without the need
2380 to coerce one side of the comparison into the other's side type.
2382 The complexity of the search is $(BIGOH haystack.length *
2383 max(needles.length)). (For needles that are individual items, length
2384 is considered to be 1.) The strategy used in searching several
2385 subranges at once maximizes cache usage by moving in `haystack` as
2386 few times as possible.
2388 Tuple!(Range, size_t) find(alias pred = "a == b", Range, Needles...)
2389 (Range haystack, Needles needles)
2390 if (Needles.length > 1 && is(typeof(startsWith!pred(haystack, needles))))
2392 for (;; haystack.popFront())
2394 size_t r = startsWith!pred(haystack, needles);
2395 if (r || haystack.empty)
2397 return tuple(haystack, r);
2405 import std.typecons : tuple;
2406 int[] a = [ 1, 4, 2, 3 ];
2407 assert(find(a, 4) == [ 4, 2, 3 ]);
2408 assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]);
2409 assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2));
2410 // Mixed types allowed if comparable
2411 assert(find(a, 5, [ 1.2, 3.5 ], 2.0) == tuple([ 2, 3 ], 3));
2416 auto s1 = "Mary has a little lamb";
2417 assert(find(s1, "has a", "has an") == tuple("has a little lamb", 1));
2418 assert(find(s1, 't', "has a", "has an") == tuple("has a little lamb", 2));
2419 assert(find(s1, 't', "has a", 'y', "has an") == tuple("y has a little lamb", 3));
2420 assert(find("abc", "bc").length == 2);
2425 import std.algorithm.internal : rndstuff;
2426 import std.meta : AliasSeq;
2427 import std.uni : toUpper;
2429 int[] a = [ 1, 2, 3 ];
2430 assert(find(a, 5).empty);
2431 assert(find(a, 2) == [2, 3]);
2433 foreach (T; AliasSeq!(int, double))
2435 auto b = rndstuff!(T)();
2436 if (!b.length) continue;
2439 assert(find(b, 200).length == b.length - b.length / 4);
2442 // Case-insensitive find of a string
2443 string[] s = [ "Hello", "world", "!" ];
2444 assert(find!("toUpper(a) == toUpper(b)")(s, "hello").length == 3);
2446 static bool f(string a, string b) { return toUpper(a) == toUpper(b); }
2447 assert(find!(f)(s, "hello").length == 3);
2452 import std.algorithm.comparison : equal;
2453 import std.algorithm.internal : rndstuff;
2454 import std.meta : AliasSeq;
2455 import std.range : retro;
2457 int[] a = [ 1, 2, 3, 2, 6 ];
2458 assert(find(retro(a), 5).empty);
2459 assert(equal(find(retro(a), 2), [ 2, 3, 2, 1 ][]));
2461 foreach (T; AliasSeq!(int, double))
2463 auto b = rndstuff!(T)();
2464 if (!b.length) continue;
2467 assert(find(retro(b), 200).length ==
2468 b.length - (b.length - 1) / 2);
2474 import std.algorithm.comparison : equal;
2475 import std.internal.test.dummyrange;
2477 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2478 int[] b = [ 1, 2, 3 ];
2479 assert(find(a, b) == [ 1, 2, 3, 4, 5 ]);
2480 assert(find(b, a).empty);
2482 foreach (DummyType; AllDummyRanges)
2485 auto findRes = find(d, 5);
2486 assert(equal(findRes, [5,6,7,8,9,10]));
2491 * Finds `needle` in `haystack` efficiently using the
2492 * $(LINK2 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm,
2493 * Boyer-Moore) method.
2496 * haystack = A random-access range with length and slicing.
2497 * needle = A $(LREF BoyerMooreFinder).
2500 * `haystack` advanced such that `needle` is a prefix of it (if no
2501 * such position exists, returns `haystack` advanced to termination).
2503 RandomAccessRange find(RandomAccessRange, alias pred, InputRange)(
2504 RandomAccessRange haystack, scope BoyerMooreFinder!(pred, InputRange) needle)
2506 return needle.beFound(haystack);
2511 string h = "/homes/aalexand/d/dmd/bin/../lib/libphobos.a(dmain2.o)"~
2512 "(.gnu.linkonce.tmain+0x74): In function `main' undefined reference"~
2514 string[] ns = ["libphobos", "function", " undefined", "`", ":"];
2517 auto p = find(h, boyerMooreFinder(n));
2525 import std.range.primitives : empty;
2526 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2527 int[] b = [ 1, 2, 3 ];
2529 assert(find(a, boyerMooreFinder(b)) == [ 1, 2, 3, 4, 5 ]);
2530 assert(find(b, boyerMooreFinder(a)).empty);
2535 auto bm = boyerMooreFinder("for");
2536 auto match = find("Moor", bm);
2537 assert(match.empty);
2542 Convenience function. Like find, but only returns whether or not the search
2545 For more information about `pred` see $(LREF find).
2548 $(REF among, std,algorithm,comparison) for checking a value against multiple arguments.
2550 template canFind(alias pred="a == b")
2553 Returns `true` if and only if `pred(e)` is true for any value `e` in the
2554 input range `range`.
2555 Performs (at most) $(BIGOH haystack.length) evaluations of `pred`.
2557 bool canFind(Range)(Range haystack)
2558 if (is(typeof(find!pred(haystack))))
2560 return any!pred(haystack);
2564 Returns `true` if and only if `needle` can be found in $(D
2565 range). Performs $(BIGOH haystack.length) evaluations of `pred`.
2567 bool canFind(Range, Element)(Range haystack, scope Element needle)
2568 if (is(typeof(find!pred(haystack, needle))))
2570 return !find!pred(haystack, needle).empty;
2574 Returns the 1-based index of the first needle found in `haystack`. If no
2575 needle is found, then `0` is returned.
2577 So, if used directly in the condition of an `if` statement or loop, the result
2578 will be `true` if one of the needles is found and `false` if none are
2579 found, whereas if the result is used elsewhere, it can either be cast to
2580 `bool` for the same effect or used to get which needle was found first
2581 without having to deal with the tuple that $(LREF find) returns for the
2584 size_t canFind(Range, Needles...)(Range haystack, scope Needles needles)
2585 if (Needles.length > 1 &&
2586 is(typeof(find!pred(haystack, needles))))
2588 return find!pred(haystack, needles)[1];
2595 const arr = [0, 1, 2, 3];
2596 assert(canFind(arr, 2));
2597 assert(!canFind(arr, 4));
2599 // find one of several needles
2600 assert(arr.canFind(3, 2));
2601 assert(arr.canFind(3, 2) == 2); // second needle found
2602 assert(arr.canFind([1, 3], 2) == 2);
2604 assert(canFind(arr, [1, 2], [2, 3]));
2605 assert(canFind(arr, [1, 2], [2, 3]) == 1);
2606 assert(canFind(arr, [1, 7], [2, 3]));
2607 assert(canFind(arr, [1, 7], [2, 3]) == 2);
2608 assert(!canFind(arr, [1, 3], [2, 4]));
2609 assert(canFind(arr, [1, 3], [2, 4]) == 0);
2613 * Example using a custom predicate.
2614 * Note that the needle appears as the second argument of the predicate.
2623 assert(!canFind(words, "bees"));
2624 assert( canFind!((string elem, string needle) => elem.startsWith(needle))(words, "bees"));
2627 /// Search for multiple items in an array of items (search for needles in an array of haystacks)
2630 string s1 = "aaa111aaa";
2631 string s2 = "aaa222aaa";
2632 string s3 = "aaa333aaa";
2633 string s4 = "aaa444aaa";
2634 const hay = [s1, s2, s3, s4];
2635 assert(hay.canFind!(e => e.canFind("111", "222")));
2640 import std.algorithm.internal : rndstuff;
2642 auto a = rndstuff!(int)();
2645 auto b = a[a.length / 2];
2646 assert(canFind(a, b));
2652 import std.algorithm.comparison : equal;
2653 assert(equal!(canFind!"a < b")([[1, 2, 3], [7, 8, 9]], [2, 8]));
2658 Advances `r` until it finds the first two adjacent elements `a`,
2659 `b` that satisfy `pred(a, b)`. Performs $(BIGOH r.length)
2660 evaluations of `pred`.
2662 For more information about `pred` see $(LREF find).
2665 pred = The predicate to satisfy.
2666 r = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to
2670 `r` advanced to the first occurrence of two adjacent elements that satisfy
2671 the given predicate. If there are no such two elements, returns `r` advanced
2675 $(LINK2 http://en.cppreference.com/w/cpp/algorithm/adjacent_find, STL's `adjacent_find`)
2677 Range findAdjacent(alias pred = "a == b", Range)(Range r)
2678 if (isForwardRange!(Range))
2680 auto ahead = r.save;
2683 for (ahead.popFront(); !ahead.empty; r.popFront(), ahead.popFront())
2685 if (binaryFun!(pred)(r.front, ahead.front)) return r;
2688 static if (!isInfinite!Range)
2696 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
2697 auto r = findAdjacent(a);
2698 assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]);
2699 auto p = findAdjacent!("a < b")(a);
2700 assert(p == [ 7, 8, 9 ]);
2706 import std.algorithm.comparison : equal;
2707 import std.internal.test.dummyrange;
2710 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
2711 auto p = findAdjacent(a);
2712 assert(p == [10, 10, 9, 8, 8, 7, 8, 9 ]);
2713 p = findAdjacent!("a < b")(a);
2714 assert(p == [7, 8, 9]);
2717 p = findAdjacent(a);
2720 a = [ 1, 2, 3, 4, 5 ];
2721 p = findAdjacent(a);
2723 p = findAdjacent!"a > b"(a);
2725 ReferenceForwardRange!int rfr = new ReferenceForwardRange!int([1, 2, 3, 2, 2, 3]);
2726 assert(equal(findAdjacent(rfr), [2, 2, 3]));
2728 // https://issues.dlang.org/show_bug.cgi?id=9350
2729 assert(!repeat(1).findAdjacent().empty);
2734 Searches the given range for an element that matches one of the given choices.
2736 Advances `seq` by calling `seq.popFront` until either
2737 `find!(pred)(choices, seq.front)` is `true`, or `seq` becomes empty.
2738 Performs $(BIGOH seq.length * choices.length) evaluations of `pred`.
2740 For more information about `pred` see $(LREF find).
2743 pred = The predicate to use for determining a match.
2744 seq = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to
2746 choices = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2747 of possible choices.
2750 `seq` advanced to the first matching element, or until empty if there are no
2753 See_Also: $(LREF find), $(REF among, std,algorithm,comparison)
2755 InputRange findAmong(alias pred = "a == b", InputRange, ForwardRange)(
2756 InputRange seq, ForwardRange choices)
2757 if (isInputRange!InputRange && isForwardRange!ForwardRange)
2759 for (; !seq.empty && find!pred(choices.save, seq.front).empty; seq.popFront())
2768 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2769 int[] b = [ 3, 1, 2 ];
2770 assert(findAmong(a, b) == a[2 .. $]);
2775 int[] a = [ -1, 0, 2, 1, 2, 3, 4, 5 ];
2776 int[] b = [ 1, 2, 3 ];
2777 assert(findAmong(a, b) == [2, 1, 2, 3, 4, 5 ]);
2778 assert(findAmong(b, [ 4, 6, 7 ][]).empty);
2779 assert(findAmong!("a == b")(a, b).length == a.length - 2);
2780 assert(findAmong!("a == b")(b, [ 4, 6, 7 ][]).empty);
2783 // https://issues.dlang.org/show_bug.cgi?id=19765
2786 import std.range.interfaces : inputRangeObject;
2787 auto choices = inputRangeObject("b");
2788 auto f = "foobar".findAmong(choices);
2794 * Finds `needle` in `haystack` and positions `haystack`
2795 * right after the first occurrence of `needle`.
2797 * If no needle is provided, the `haystack` is advanced as long as `pred`
2798 * evaluates to `true`.
2799 * Similarly, the haystack is positioned so as `pred` evaluates to `false` for
2802 * For more information about `pred` see $(LREF find).
2806 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search
2809 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search
2811 * pred = Custom predicate for comparison of haystack and needle
2813 * Returns: `true` if the needle was found, in which case `haystack` is
2814 * positioned after the end of the first occurrence of `needle`; otherwise
2815 * `false`, leaving `haystack` untouched. If no needle is provided, it returns
2816 * the number of times `pred(haystack.front)` returned true.
2818 * See_Also: $(LREF find)
2820 bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle)
2821 if (isForwardRange!R1 && isForwardRange!R2
2822 && is(typeof(binaryFun!pred(haystack.front, needle.front))))
2824 auto parts = findSplit!pred(haystack, needle);
2825 if (parts[1].empty) return false;
2827 haystack = parts[2];
2834 import std.range.primitives : empty;
2835 // Needle is found; s is replaced by the substring following the first
2836 // occurrence of the needle.
2837 string s = "abcdef";
2838 assert(findSkip(s, "cd") && s == "ef");
2840 // Needle is not found; s is left untouched.
2842 assert(!findSkip(s, "cxd") && s == "abcdef");
2844 // If the needle occurs at the end of the range, the range is left empty.
2846 assert(findSkip(s, "def") && s.empty);
2849 // https://issues.dlang.org/show_bug.cgi?id=19020
2852 static struct WrapperRange
2855 @property auto empty() { return _r.empty(); }
2856 @property auto front() { return _r.front(); }
2857 auto popFront() { return _r.popFront(); }
2858 @property auto save() { return WrapperRange(_r.save); }
2860 auto tmp = WrapperRange("there is a bug here: *");
2861 assert(!tmp.findSkip("*/"));
2862 assert(tmp._r == "there is a bug here: *");
2866 size_t findSkip(alias pred, R1)(ref R1 haystack)
2867 if (isForwardRange!R1 && ifTestable!(typeof(haystack.front), unaryFun!pred))
2870 while (!haystack.empty && unaryFun!pred(haystack.front))
2881 import std.ascii : isWhite;
2883 assert(findSkip!isWhite(s) && s == "abc");
2884 assert(!findSkip!isWhite(s) && s == "abc");
2887 assert(findSkip!isWhite(s) == 2);
2892 import std.ascii : isWhite;
2895 assert(findSkip!isWhite(s) == 2);
2898 private struct FindSplitResult(ubyte emptyRangeIndex, Types...)
2902 asTuple = typeof(asTuple)(vals);
2904 void opAssign(typeof(asTuple) rhs)
2908 Tuple!Types asTuple;
2911 static if (hasConstEmptyMember!(typeof(asTuple[emptyRangeIndex])))
2913 bool opCast(T : bool)() const => !asTuple[emptyRangeIndex].empty;
2917 bool opCast(T : bool)() => !asTuple[emptyRangeIndex].empty;
2922 These functions find the first occurrence of `needle` in `haystack` and then
2923 split `haystack` as follows.
2926 `findSplit` returns a tuple `result` containing $(I three) ranges.
2928 $(LI `result[0]` is the portion of `haystack` before `needle`)
2929 $(LI `result[1]` is the portion of
2930 `haystack` that matches `needle`)
2931 $(LI `result[2]` is the portion of `haystack`
2934 If `needle` was not found, `result[0]` comprehends `haystack`
2935 entirely and `result[1]` and `result[2]` are empty.
2937 `findSplitBefore` returns a tuple `result` containing two ranges.
2939 $(LI `result[0]` is the portion of `haystack` before `needle`)
2940 $(LI `result[1]` is the balance of `haystack` starting with the match.)
2942 If `needle` was not found, `result[0]`
2943 comprehends `haystack` entirely and `result[1]` is empty.
2945 `findSplitAfter` returns a tuple `result` containing two ranges.
2947 $(LI `result[0]` is the portion of `haystack` up to and including the
2949 $(LI `result[1]` is the balance of `haystack` starting
2952 If `needle` was not found, `result[0]` is empty
2953 and `result[1]` is `haystack`.
2956 In all cases, the concatenation of the returned ranges spans the
2959 If `haystack` is a random-access range, all three components of the tuple have
2960 the same type as `haystack`. Otherwise, `haystack` must be a
2961 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) and
2962 the type of `result[0]` (and `result[1]` for `findSplit`) is the same as
2963 the result of $(REF takeExactly, std,range).
2965 For more information about `pred` see $(LREF find).
2968 pred = Predicate to compare 2 elements.
2969 haystack = The forward range to search.
2970 needle = The forward range to look for.
2974 A sub-type of $(REF Tuple, std, typecons) of the split portions of `haystack` (see above for
2975 details). This sub-type of `Tuple` defines `opCast!bool`, which
2976 returns `true` when the separating `needle` was found and `false` otherwise.
2978 See_Also: $(LREF find)
2980 auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
2981 if (isForwardRange!R1 && isForwardRange!R2)
2983 static if (isSomeString!R1 && isSomeString!R2
2984 || (isRandomAccessRange!R1 && hasSlicing!R1 && hasLength!R1 && hasLength!R2))
2986 auto balance = find!pred(haystack, needle);
2987 immutable pos1 = haystack.length - balance.length;
2988 immutable pos2 = balance.empty ? pos1 : pos1 + needle.length;
2989 alias Slice = typeof(haystack[0 .. pos1]);
2990 return FindSplitResult!(1, Slice, Slice, Slice)(
2991 haystack[0 .. pos1], haystack[pos1 .. pos2], haystack[pos2 .. haystack.length]);
2995 import std.range : takeExactly;
2996 auto original = haystack.save;
2997 auto h = haystack.save;
2998 auto n = needle.save;
3000 while (!n.empty && !h.empty)
3002 if (binaryFun!pred(h.front, n.front))
3010 haystack.popFront();
3016 if (!n.empty) // incomplete match at the end of haystack
3020 return FindSplitResult!(1,
3021 typeof(takeExactly(original, pos1)),
3022 typeof(takeExactly(original, pos1)), typeof(h))(
3023 takeExactly(original, pos1),
3024 takeExactly(haystack, pos2 - pos1), h);
3029 auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3030 if (isForwardRange!R1 && isForwardRange!R2)
3032 static if (isSomeString!R1 && isSomeString!R2
3033 || (isRandomAccessRange!R1 && hasLength!R1 && hasSlicing!R1 && hasLength!R2))
3035 auto balance = find!pred(haystack, needle);
3036 immutable pos = haystack.length - balance.length;
3037 return FindSplitResult!(1,
3038 typeof(haystack[0 .. pos]), typeof(haystack[0 .. pos]))(
3039 haystack[0 .. pos], haystack[pos .. haystack.length]);
3043 import std.range : takeExactly;
3044 auto original = haystack.save;
3045 auto h = haystack.save;
3046 auto n = needle.save;
3048 while (!n.empty && !h.empty)
3050 if (binaryFun!pred(h.front, n.front))
3058 haystack.popFront();
3064 if (!n.empty) // incomplete match at the end of haystack
3069 return FindSplitResult!(1,
3070 typeof(takeExactly(original, pos1)), typeof(haystack))(
3071 takeExactly(original, pos1), haystack);
3076 auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3077 if (isForwardRange!R1 && isForwardRange!R2)
3079 static if (isSomeString!R1 && isSomeString!R2
3080 || isRandomAccessRange!R1 && hasLength!R1 && hasSlicing!R1 && hasLength!R2)
3082 auto balance = find!pred(haystack, needle);
3083 immutable pos = balance.empty ? 0 : haystack.length - balance.length + needle.length;
3084 return FindSplitResult!(0,
3085 typeof(haystack[0 .. pos]), typeof(haystack[0 .. pos]))(
3086 haystack[0 .. pos], haystack[pos .. haystack.length]);
3090 import std.range : takeExactly;
3091 alias Res = FindSplitResult!(0, typeof(takeExactly(haystack, 0)), typeof(haystack));
3092 auto original = haystack.save;
3093 auto h = haystack.save;
3094 auto n = needle.save;
3101 return Res(takeExactly(original, 0), original);
3103 if (binaryFun!pred(h.front, n.front))
3111 haystack.popFront();
3117 return Res(takeExactly(original, pos2), h);
3121 /// Returning a subtype of $(REF Tuple, std,typecons) enables
3122 /// the following convenient idiom:
3123 @safe pure nothrow unittest
3125 // findSplit returns a triplet
3126 if (auto split = "dlang-rocks".findSplit("-"))
3128 assert(split[0] == "dlang");
3129 assert(split[1] == "-");
3130 assert(split[2] == "rocks");
3134 // findSplitBefore returns 2 ranges
3135 if (const split = [2, 3, 2, 3, 4, 1].findSplitBefore!"a > b"([2, 2]))
3137 assert(split[0] == [2, 3, 2]);
3138 // [3, 4] each greater than [2, 2]
3139 assert(split[1] == [3, 4, 1]);
3145 @safe pure nothrow unittest
3147 import std.range.primitives : empty;
3149 auto a = "Carl Sagan Memorial Station";
3150 auto r = findSplit(a, "Velikovsky");
3151 import std.typecons : isTuple;
3152 static assert(isTuple!(typeof(r.asTuple)));
3153 static assert(isTuple!(typeof(r)));
3158 r = findSplit(a, " ");
3159 assert(r[0] == "Carl");
3160 assert(r[1] == " ");
3161 assert(r[2] == "Sagan Memorial Station");
3162 if (const r1 = findSplitBefore(a, "Sagan"))
3165 assert(r1[0] == "Carl ");
3166 assert(r1[1] == "Sagan Memorial Station");
3168 if (const r2 = findSplitAfter(a, "Sagan"))
3171 assert(r2[0] == "Carl Sagan");
3172 assert(r2[1] == " Memorial Station");
3176 /// Use $(REF only, std,range) to find single elements:
3177 @safe pure nothrow unittest
3179 import std.range : only;
3180 assert([1, 2, 3, 4].findSplitBefore(only(3))[0] == [1, 2]);
3183 @safe pure nothrow unittest
3185 import std.range.primitives : empty;
3187 immutable a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3188 auto r = findSplit(a, [9, 1]);
3193 r = findSplit(a, [3]);
3195 assert(r[0] == a[0 .. 2]);
3196 assert(r[1] == a[2 .. 3]);
3197 assert(r[2] == a[3 .. $]);
3200 const r1 = findSplitBefore(a, [9, 1]);
3203 assert(r1[1].empty);
3206 if (immutable r1 = findSplitBefore(a, [3, 4]))
3209 assert(r1[0] == a[0 .. 2]);
3210 assert(r1[1] == a[2 .. $]);
3215 const r2 = findSplitAfter(a, [9, 1]);
3217 assert(r2[0].empty);
3221 if (immutable r3 = findSplitAfter(a, [3, 4]))
3224 assert(r3[0] == a[0 .. 4]);
3225 assert(r3[1] == a[4 .. $]);
3230 @safe pure nothrow unittest
3232 import std.algorithm.comparison : equal;
3233 import std.algorithm.iteration : filter;
3235 auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3236 auto fwd = filter!"a > 0"(a);
3237 auto r = findSplit(fwd, [9, 1]);
3239 assert(equal(r[0], a));
3242 r = findSplit(fwd, [3]);
3244 assert(equal(r[0], a[0 .. 2]));
3245 assert(equal(r[1], a[2 .. 3]));
3246 assert(equal(r[2], a[3 .. $]));
3247 r = findSplit(fwd, [8, 9]);
3249 assert(equal(r[0], a));
3253 // auto variable `r2` cannot be `const` because `fwd.front` is mutable
3255 auto r1 = findSplitBefore(fwd, [9, 1]);
3257 assert(equal(r1[0], a));
3258 assert(r1[1].empty);
3261 if (auto r1 = findSplitBefore(fwd, [3, 4]))
3264 assert(equal(r1[0], a[0 .. 2]));
3265 assert(equal(r1[1], a[2 .. $]));
3270 auto r1 = findSplitBefore(fwd, [8, 9]);
3272 assert(equal(r1[0], a));
3273 assert(r1[1].empty);
3277 auto r2 = findSplitAfter(fwd, [9, 1]);
3279 assert(r2[0].empty);
3280 assert(equal(r2[1], a));
3283 if (auto r2 = findSplitAfter(fwd, [3, 4]))
3286 assert(equal(r2[0], a[0 .. 4]));
3287 assert(equal(r2[1], a[4 .. $]));
3292 auto r2 = findSplitAfter(fwd, [8, 9]);
3294 assert(r2[0].empty);
3295 assert(equal(r2[1], a));
3299 @safe pure nothrow @nogc unittest
3301 auto str = "sep,one,sep,two";
3303 auto split = str.findSplitAfter(",");
3304 assert(split[0] == "sep,");
3306 split = split[1].findSplitAfter(",");
3307 assert(split[0] == "one,");
3309 split = split[1].findSplitBefore(",");
3310 assert(split[0] == "sep");
3313 @safe pure nothrow @nogc unittest
3315 auto str = "sep,one,sep,two";
3317 auto split = str.findSplitBefore(",two");
3318 assert(split[0] == "sep,one,sep");
3319 assert(split[1] == ",two");
3321 split = split[0].findSplitBefore(",sep");
3322 assert(split[0] == "sep,one");
3323 assert(split[1] == ",sep");
3325 split = split[0].findSplitAfter(",");
3326 assert(split[0] == "sep,");
3327 assert(split[1] == "one");
3330 // https://issues.dlang.org/show_bug.cgi?id=11013
3334 auto split = var.findSplitBefore!q{a == a}(var);
3335 assert(split[0] == "");
3336 assert(split[1] == "abc");
3342 Computes the minimum (respectively maximum) of `range` along with its number of
3343 occurrences. Formally, the minimum is a value `x` in `range` such that $(D
3344 pred(a, x)) is `false` for all values `a` in `range`. Conversely, the maximum is
3345 a value `x` in `range` such that `pred(x, a)` is `false` for all values `a`
3346 in `range` (note the swapped arguments to `pred`).
3348 These functions may be used for computing arbitrary extrema by choosing `pred`
3349 appropriately. For corrrect functioning, `pred` must be a strict partial order,
3350 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and
3351 irreflexive (`pred(a, a)` is `false`). The $(LUCKY trichotomy property of
3352 inequality) is not required: these algorithms consider elements `a` and `b` equal
3353 (for the purpose of counting) if `pred` puts them in the same equivalence class,
3354 i.e. `!pred(a, b) && !pred(b, a)`.
3357 pred = The ordering predicate to use to determine the extremum (minimum
3359 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to count.
3361 Returns: The minimum, respectively maximum element of a range together with the
3362 number it occurs in the range.
3364 Limitations: If at least one of the arguments is NaN, the result is
3365 an unspecified value. See $(REF maxElement, std,algorithm,searching)
3366 for examples on how to cope with NaNs.
3368 Throws: `Exception` if `range.empty`.
3370 See_Also: $(REF min, std,algorithm,comparison), $(LREF minIndex), $(LREF minElement), $(LREF minPos)
3372 Tuple!(ElementType!Range, size_t)
3373 minCount(alias pred = "a < b", Range)(Range range)
3374 if (isInputRange!Range && !isInfinite!Range &&
3375 is(typeof(binaryFun!pred(range.front, range.front))))
3377 import std.algorithm.internal : algoFormat;
3378 import std.exception : enforce;
3380 alias T = ElementType!Range;
3381 alias UT = Unqual!T;
3382 alias RetType = Tuple!(T, size_t);
3384 static assert(is(typeof(RetType(range.front, 1))),
3385 algoFormat("Error: Cannot call minCount on a %s, because it is not possible "~
3386 "to copy the result value (a %s) into a Tuple.", Range.stringof, T.stringof));
3388 enforce(!range.empty, "Can't count elements from an empty range");
3389 size_t occurrences = 1;
3391 static if (isForwardRange!Range)
3393 Range least = range.save;
3394 for (range.popFront(); !range.empty; range.popFront())
3396 if (binaryFun!pred(least.front, range.front))
3398 assert(!binaryFun!pred(range.front, least.front),
3399 "min/maxPos: predicate must be a strict partial order.");
3402 if (binaryFun!pred(range.front, least.front))
3411 return RetType(least.front, occurrences);
3413 else static if (isAssignable!(UT, T) || (!hasElaborateAssign!UT && isAssignable!UT))
3416 static if (isAssignable!(UT, T)) v = range.front;
3417 else v = cast(UT) range.front;
3419 for (range.popFront(); !range.empty; range.popFront())
3421 if (binaryFun!pred(*cast(T*)&v, range.front)) continue;
3422 if (binaryFun!pred(range.front, *cast(T*)&v))
3425 static if (isAssignable!(UT, T)) v = range.front;
3426 else v = cast(UT) range.front; //Safe because !hasElaborateAssign!UT
3432 return RetType(*cast(T*)&v, occurrences);
3434 else static if (hasLvalueElements!Range)
3436 import std.algorithm.internal : addressOf;
3437 T* p = addressOf(range.front);
3438 for (range.popFront(); !range.empty; range.popFront())
3440 if (binaryFun!pred(*p, range.front)) continue;
3441 if (binaryFun!pred(range.front, *p))
3444 p = addressOf(range.front);
3450 return RetType(*p, occurrences);
3453 static assert(false,
3454 algoFormat("Sorry, can't find the minCount of a %s: Don't know how "~
3455 "to keep track of the smallest %s element.", Range.stringof, T.stringof));
3459 Tuple!(ElementType!Range, size_t)
3460 maxCount(alias pred = "a < b", Range)(Range range)
3461 if (isInputRange!Range && !isInfinite!Range &&
3462 is(typeof(binaryFun!pred(range.front, range.front))))
3464 return range.minCount!((a, b) => binaryFun!pred(b, a));
3470 import std.conv : text;
3471 import std.typecons : tuple;
3473 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3474 // Minimum is 1 and occurs 3 times
3475 assert(a.minCount == tuple(1, 3));
3476 // Maximum is 4 and occurs 2 times
3477 assert(a.maxCount == tuple(4, 2));
3482 import std.conv : text;
3483 import std.exception : assertThrown;
3484 import std.internal.test.dummyrange;
3486 int[][] b = [ [4], [2, 4], [4], [4] ];
3487 auto c = minCount!("a[0] < b[0]")(b);
3488 assert(c == tuple([2, 4], 1), text(c[0]));
3491 assertThrown(minCount(b[$..$]));
3493 //test with reference ranges. Test both input and forward.
3494 assert(minCount(new ReferenceInputRange!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2));
3495 assert(minCount(new ReferenceForwardRange!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2));
3500 import std.conv : text;
3501 import std.meta : AliasSeq;
3503 static struct R(T) //input range
3509 immutable a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3510 R!(immutable int) b = R!(immutable int)(a);
3512 assert(minCount(a) == tuple(1, 3));
3513 assert(minCount(b) == tuple(1, 3));
3514 assert(minCount!((ref immutable int a, ref immutable int b) => (a > b))(a) == tuple(4, 2));
3515 assert(minCount!((ref immutable int a, ref immutable int b) => (a > b))(b) == tuple(4, 2));
3517 immutable(int[])[] c = [ [4], [2, 4], [4], [4] ];
3518 assert(minCount!("a[0] < b[0]")(c) == tuple([2, 4], 1), text(c[0]));
3524 alias IS1 = immutable(S1);
3525 static assert( isAssignable!S1);
3526 static assert( isAssignable!(S1, IS1));
3531 this(ref immutable int i) immutable {p = &i;}
3532 this(ref int i) {p = &i;}
3533 @property ref inout(int) i() inout {return *p;}
3534 bool opEquals(const S2 other) const {return i == other.i;}
3536 alias IS2 = immutable(S2);
3537 static assert( isAssignable!S2);
3538 static assert(!isAssignable!(S2, IS2));
3539 static assert(!hasElaborateAssign!S2);
3544 void opAssign(ref S3 other) @disable;
3546 static assert(!isAssignable!S3);
3548 static foreach (Type; AliasSeq!(S1, IS1, S2, IS2, S3))
3550 static if (is(Type == immutable)) alias V = immutable int;
3553 auto r1 = [Type(two), Type(one), Type(one)];
3554 auto r2 = R!Type(r1);
3555 assert(minCount!"a.i < b.i"(r1) == tuple(Type(one), 2));
3556 assert(minCount!"a.i < b.i"(r2) == tuple(Type(one), 2));
3557 assert(one == 1 && two == 2);
3562 Iterates the passed range and returns the minimal element.
3563 A custom mapping function can be passed to `map`.
3564 In other languages this is sometimes called `argmin`.
3567 Exactly `n - 1` comparisons are needed.
3570 map = custom accessor for the comparison key
3571 r = range from which the minimal element will be selected
3572 seed = custom seed to use as initial element
3574 Precondition: If a seed is not given, `r` must not be empty.
3576 Returns: The minimal element of the passed-in range.
3579 If at least one of the arguments is NaN, the result is an unspecified value.
3581 If you want to ignore NaNs, you can use $(REF filter, std,algorithm,iteration)
3582 and $(REF isNaN, std,math) to remove them, before applying minElement.
3583 Add a suitable seed, to avoid error messages if all elements are NaNs:
3586 <range>.filter!(a=>!a.isNaN).minElement(<seed>);
3589 If you want to get NaN as a result if a NaN is present in the range,
3590 you can use $(REF fold, std,algorithm,iteration) and $(REF isNaN, std,math):
3593 <range>.fold!((a,b)=>a.isNaN || b.isNaN ? real.nan : a < b ? a : b);
3598 $(LREF maxElement), $(REF min, std,algorithm,comparison), $(LREF minCount),
3599 $(LREF minIndex), $(LREF minPos)
3601 auto minElement(alias map = (a => a), Range)(Range r)
3602 if (isInputRange!Range && !isInfinite!Range)
3604 return extremum!map(r);
3608 auto minElement(alias map = (a => a), Range, RangeElementType = ElementType!Range)
3609 (Range r, RangeElementType seed)
3610 if (isInputRange!Range && !isInfinite!Range &&
3611 !is(CommonType!(ElementType!Range, RangeElementType) == void))
3613 return extremum!map(r, seed);
3619 import std.range : enumerate;
3620 import std.typecons : tuple;
3622 assert([2, 7, 1, 3].minElement == 1);
3624 // allows to get the index of an element too
3625 assert([5, 3, 7, 9].enumerate.minElement!"a.value" == tuple(1, 3));
3627 // any custom accessor can be passed
3628 assert([[0, 4], [1, 2]].minElement!"a[1]" == [1, 2]);
3632 assert(arr.minElement(1) == 1);
3637 import std.range : enumerate, iota;
3639 assert([3, 4, 5, 1, 2].enumerate.minElement!"a.value" == tuple(3, 1));
3640 assert([5, 2, 4].enumerate.minElement!"a.value" == tuple(1, 2));
3643 assert(iota(1, 5).minElement() == 1);
3644 assert(iota(2, 5).enumerate.minElement!"a.value" == tuple(0, 2));
3646 // should work with const
3647 const(int)[] immArr = [2, 1, 3];
3648 assert(immArr.minElement == 1);
3650 // should work with immutable
3651 immutable(int)[] immArr2 = [2, 1, 3];
3652 assert(immArr2.minElement == 1);
3655 assert(["b", "a", "c"].minElement == "a");
3657 // with all dummy ranges
3658 import std.internal.test.dummyrange;
3659 foreach (DummyType; AllDummyRanges)
3662 assert(d.minElement == 1);
3663 assert(d.minElement!(a => a) == 1);
3664 assert(d.minElement!(a => -a) == 10);
3667 // with empty, but seeded ranges
3669 assert(arr.minElement(42) == 42);
3670 assert(arr.minElement!(a => a)(42) == 42);
3673 @nogc @safe nothrow pure unittest
3675 static immutable arr = [7, 3, 4, 2, 1, 8];
3676 assert(arr.minElement == 1);
3678 static immutable arr2d = [[1, 9], [3, 1], [4, 2]];
3679 assert(arr2d.minElement!"a[1]" == arr2d[1]);
3682 // https://issues.dlang.org/show_bug.cgi?id=17982
3690 const(A)[] v = [A(0)];
3691 assert(v.minElement!"a.val" == A(0));
3694 // https://issues.dlang.org/show_bug.cgi?id=17982
3700 this(int val){ this.val = val; }
3703 const(B) doStuff(const(B)[] v)
3705 return v.minElement!"a.val";
3707 assert(doStuff([new B(1), new B(0), new B(2)]).val == 0);
3709 const(B)[] arr = [new B(0), new B(1)];
3710 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
3711 assert(arr.minElement!"a.val".val == 0);
3715 Iterates the passed range and returns the maximal element.
3716 A custom mapping function can be passed to `map`.
3717 In other languages this is sometimes called `argmax`.
3720 Exactly `n - 1` comparisons are needed.
3723 map = custom accessor for the comparison key
3724 r = range from which the maximum element will be selected
3725 seed = custom seed to use as initial element
3727 Precondition: If a seed is not given, `r` must not be empty.
3729 Returns: The maximal element of the passed-in range.
3732 If at least one of the arguments is NaN, the result is an unspecified value.
3733 See $(REF minElement, std,algorithm,searching) for examples on how to cope
3738 $(LREF minElement), $(REF max, std,algorithm,comparison), $(LREF maxCount),
3739 $(LREF maxIndex), $(LREF maxPos)
3741 auto maxElement(alias map = (a => a), Range)(Range r)
3742 if (isInputRange!Range && !isInfinite!Range)
3744 return extremum!(map, "a > b")(r);
3748 auto maxElement(alias map = (a => a), Range, RangeElementType = ElementType!Range)
3749 (Range r, RangeElementType seed)
3750 if (isInputRange!Range && !isInfinite!Range &&
3751 !is(CommonType!(ElementType!Range, RangeElementType) == void))
3753 return extremum!(map, "a > b")(r, seed);
3759 import std.range : enumerate;
3760 import std.typecons : tuple;
3761 assert([2, 1, 4, 3].maxElement == 4);
3763 // allows to get the index of an element too
3764 assert([2, 1, 4, 3].enumerate.maxElement!"a.value" == tuple(2, 4));
3766 // any custom accessor can be passed
3767 assert([[0, 4], [1, 2]].maxElement!"a[1]" == [0, 4]);
3771 assert(arr.minElement(1) == 1);
3776 import std.range : enumerate, iota;
3779 assert([3, 4, 5, 1, 2].enumerate.maxElement!"a.value" == tuple(2, 5));
3780 assert([5, 2, 4].enumerate.maxElement!"a.value" == tuple(0, 5));
3783 assert(iota(1, 5).maxElement() == 4);
3784 assert(iota(2, 5).enumerate.maxElement!"a.value" == tuple(2, 4));
3785 assert(iota(4, 14).enumerate.maxElement!"a.value" == tuple(9, 13));
3787 // should work with const
3788 const(int)[] immArr = [2, 3, 1];
3789 assert(immArr.maxElement == 3);
3791 // should work with immutable
3792 immutable(int)[] immArr2 = [2, 3, 1];
3793 assert(immArr2.maxElement == 3);
3796 assert(["a", "c", "b"].maxElement == "c");
3798 // with all dummy ranges
3799 import std.internal.test.dummyrange;
3800 foreach (DummyType; AllDummyRanges)
3803 assert(d.maxElement == 10);
3804 assert(d.maxElement!(a => a) == 10);
3805 assert(d.maxElement!(a => -a) == 1);
3808 // with empty, but seeded ranges
3810 assert(arr.maxElement(42) == 42);
3811 assert(arr.maxElement!(a => a)(42) == 42);
3815 @nogc @safe nothrow pure unittest
3817 static immutable arr = [7, 3, 8, 2, 1, 4];
3818 assert(arr.maxElement == 8);
3820 static immutable arr2d = [[1, 3], [3, 9], [4, 2]];
3821 assert(arr2d.maxElement!"a[1]" == arr2d[1]);
3824 // https://issues.dlang.org/show_bug.cgi?id=17982
3830 this(int val){ this.val = val; }
3833 const(B) doStuff(const(B)[] v)
3835 return v.maxElement!"a.val";
3837 assert(doStuff([new B(1), new B(0), new B(2)]).val == 2);
3839 const(B)[] arr = [new B(0), new B(1)];
3840 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
3841 assert(arr.maxElement!"a.val".val == 1);
3844 // https://issues.dlang.org/show_bug.cgi?id=23993
3847 import std.bigint : BigInt;
3849 assert([BigInt(2), BigInt(3)].maxElement == BigInt(3));
3854 Computes a subrange of `range` starting at the first occurrence of `range`'s
3855 minimum (respectively maximum) and with the same ending as `range`, or the
3856 empty range if `range` itself is empty.
3858 Formally, the minimum is a value `x` in `range` such that `pred(a, x)` is
3859 `false` for all values `a` in `range`. Conversely, the maximum is a value `x` in
3860 `range` such that `pred(x, a)` is `false` for all values `a` in `range` (note
3861 the swapped arguments to `pred`).
3863 These functions may be used for computing arbitrary extrema by choosing `pred`
3864 appropriately. For corrrect functioning, `pred` must be a strict partial order,
3865 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and
3866 irreflexive (`pred(a, a)` is `false`).
3869 pred = The ordering predicate to use to determine the extremum (minimum or
3871 range = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search.
3873 Returns: The position of the minimum (respectively maximum) element of forward
3874 range `range`, i.e. a subrange of `range` starting at the position of its
3875 smallest (respectively largest) element and with the same ending as `range`.
3877 Limitations: If at least one of the arguments is NaN, the result is
3878 an unspecified value. See $(REF maxElement, std,algorithm,searching)
3879 for examples on how to cope with NaNs.
3882 $(REF max, std,algorithm,comparison), $(LREF minCount), $(LREF minIndex), $(LREF minElement)
3884 Range minPos(alias pred = "a < b", Range)(Range range)
3885 if (isForwardRange!Range && !isInfinite!Range &&
3886 is(typeof(binaryFun!pred(range.front, range.front))))
3888 static if (hasSlicing!Range && isRandomAccessRange!Range && hasLength!Range)
3890 // Prefer index-based access
3892 foreach (i; 1 .. range.length)
3894 if (binaryFun!pred(range[i], range[pos]))
3899 return range[pos .. range.length];
3903 auto result = range.save;
3904 if (range.empty) return result;
3905 for (range.popFront(); !range.empty; range.popFront())
3907 // Note: Unlike minCount, we do not care to find equivalence, so a
3908 // single pred call is enough.
3909 if (binaryFun!pred(range.front, result.front))
3912 result = range.save;
3920 Range maxPos(alias pred = "a < b", Range)(Range range)
3921 if (isForwardRange!Range && !isInfinite!Range &&
3922 is(typeof(binaryFun!pred(range.front, range.front))))
3924 return range.minPos!((a, b) => binaryFun!pred(b, a));
3930 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3931 // Minimum is 1 and first occurs in position 3
3932 assert(a.minPos == [ 1, 2, 4, 1, 1, 2 ]);
3933 // Maximum is 4 and first occurs in position 2
3934 assert(a.maxPos == [ 4, 1, 2, 4, 1, 1, 2 ]);
3939 import std.algorithm.comparison : equal;
3940 import std.internal.test.dummyrange;
3942 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3943 //Test that an empty range works
3945 assert(equal(minPos(b), b));
3947 //test with reference range.
3948 assert( equal( minPos(new ReferenceForwardRange!int([1, 2, 1, 0, 2, 0])), [0, 2, 0] ) );
3954 import std.algorithm.comparison : equal;
3955 import std.container : Array;
3957 assert(Array!int(2, 3, 4, 1, 2, 4, 1, 1, 2)
3960 .equal([ 1, 2, 4, 1, 1, 2 ]));
3966 immutable a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3967 // Minimum is 1 and first occurs in position 3
3968 assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]);
3969 // Maximum is 4 and first occurs in position 5
3970 assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]);
3972 immutable(int[])[] b = [ [4], [2, 4], [4], [4] ];
3973 assert(minPos!("a[0] < b[0]")(b) == [ [2, 4], [4], [4] ]);
3977 Computes the index of the first occurrence of `range`'s minimum element.
3980 pred = The ordering predicate to use to determine the minimum element.
3981 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
3984 Complexity: $(BIGOH range.length)
3985 Exactly `range.length - 1` comparisons are needed.
3988 The index of the first encounter of the minimum element in `range`. If the
3989 `range` is empty, -1 is returned.
3992 If at least one of the arguments is NaN, the result is
3993 an unspecified value. See $(REF maxElement, std,algorithm,searching)
3994 for examples on how to cope with NaNs.
3997 $(LREF maxIndex), $(REF min, std,algorithm,comparison), $(LREF minCount), $(LREF minElement), $(LREF minPos)
3999 ptrdiff_t minIndex(alias pred = "a < b", Range)(Range range)
4000 if (isInputRange!Range && !isInfinite!Range &&
4001 is(typeof(binaryFun!pred(range.front, range.front))))
4003 if (range.empty) return -1;
4005 ptrdiff_t minPos = 0;
4007 static if (isRandomAccessRange!Range && hasLength!Range)
4009 foreach (i; 1 .. range.length)
4011 if (binaryFun!pred(range[i], range[minPos]))
4019 ptrdiff_t curPos = 0;
4020 Unqual!(typeof(range.front)) min = range.front;
4021 for (range.popFront(); !range.empty; range.popFront())
4024 if (binaryFun!pred(range.front, min))
4035 @safe pure nothrow unittest
4037 int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2];
4039 // Minimum is 1 and first occurs in position 3
4040 assert(a.minIndex == 3);
4041 // Get maximum index with minIndex
4042 assert(a.minIndex!"a > b" == 2);
4044 // Range is empty, so return value is -1
4046 assert(b.minIndex == -1);
4048 // Works with more custom types
4049 struct Dog { int age; }
4050 Dog[] dogs = [Dog(10), Dog(5), Dog(15)];
4051 assert(dogs.minIndex!"a.age < b.age" == 1);
4056 // should work with const
4057 const(int)[] immArr = [2, 1, 3];
4058 assert(immArr.minIndex == 1);
4060 // Works for const ranges too
4061 const int[] c = [2, 5, 4, 1, 2, 3];
4062 assert(c.minIndex == 3);
4064 // should work with immutable
4065 immutable(int)[] immArr2 = [2, 1, 3];
4066 assert(immArr2.minIndex == 1);
4069 assert(["b", "a", "c"].minIndex == 1);
4072 import std.range : cycle;
4073 static assert(!__traits(compiles, cycle([1]).minIndex));
4075 // with all dummy ranges
4076 import std.internal.test.dummyrange : AllDummyRanges;
4077 foreach (DummyType; AllDummyRanges)
4079 static if (isForwardRange!DummyType && !isInfinite!DummyType)
4082 d.arr = [5, 3, 7, 2, 1, 4];
4083 assert(d.minIndex == 4);
4086 assert(d.minIndex == -1);
4091 @nogc @safe nothrow pure unittest
4093 static immutable arr = [7, 3, 8, 2, 1, 4];
4094 assert(arr.minIndex == 4);
4096 static immutable arr2d = [[1, 3], [3, 9], [4, 2]];
4097 assert(arr2d.minIndex!"a[1] < b[1]" == 2);
4100 @safe nothrow pure unittest
4104 static struct InRange
4106 @property int front()
4113 return arr.length == index;
4125 static assert(isInputRange!InRange);
4127 auto arr1 = InRange([5, 2, 3, 4, 5, 3, 6]);
4128 auto arr2 = InRange([7, 3, 8, 2, 1, 4]);
4130 assert(arr1.minIndex == 1);
4131 assert(arr2.minIndex == 4);
4135 Computes the index of the first occurrence of `range`'s maximum element.
4137 Complexity: $(BIGOH range)
4138 Exactly `range.length - 1` comparisons are needed.
4141 pred = The ordering predicate to use to determine the maximum element.
4142 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to search.
4145 The index of the first encounter of the maximum in `range`. If the
4146 `range` is empty, -1 is returned.
4149 If at least one of the arguments is NaN, the result is
4150 an unspecified value. See $(REF maxElement, std,algorithm,searching)
4151 for examples on how to cope with NaNs.
4154 $(LREF minIndex), $(REF max, std,algorithm,comparison), $(LREF maxCount), $(LREF maxElement), $(LREF maxPos)
4156 ptrdiff_t maxIndex(alias pred = "a < b", Range)(Range range)
4157 if (isInputRange!Range && !isInfinite!Range &&
4158 is(typeof(binaryFun!pred(range.front, range.front))))
4160 return range.minIndex!((a, b) => binaryFun!pred(b, a));
4164 @safe pure nothrow unittest
4166 // Maximum is 4 and first occurs in position 2
4167 int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2];
4168 assert(a.maxIndex == 2);
4172 assert(b.maxIndex == -1);
4174 // Works with more custom types
4175 struct Dog { int age; }
4176 Dog[] dogs = [Dog(10), Dog(15), Dog(5)];
4177 assert(dogs.maxIndex!"a.age < b.age" == 1);
4182 // should work with const
4183 const(int)[] immArr = [5, 1, 3];
4184 assert(immArr.maxIndex == 0);
4186 // Works for const ranges too
4187 const int[] c = [2, 5, 4, 1, 2, 3];
4188 assert(c.maxIndex == 1);
4191 // should work with immutable
4192 immutable(int)[] immArr2 = [2, 1, 3];
4193 assert(immArr2.maxIndex == 2);
4196 assert(["b", "a", "c"].maxIndex == 2);
4199 import std.range : cycle;
4200 static assert(!__traits(compiles, cycle([1]).maxIndex));
4202 // with all dummy ranges
4203 import std.internal.test.dummyrange : AllDummyRanges;
4204 foreach (DummyType; AllDummyRanges)
4206 static if (isForwardRange!DummyType && !isInfinite!DummyType)
4210 d.arr = [5, 3, 7, 2, 1, 4];
4211 assert(d.maxIndex == 2);
4214 assert(d.maxIndex == -1);
4219 @nogc @safe nothrow pure unittest
4221 static immutable arr = [7, 3, 8, 2, 1, 4];
4222 assert(arr.maxIndex == 2);
4224 static immutable arr2d = [[1, 3], [3, 9], [4, 2]];
4225 assert(arr2d.maxIndex!"a[1] < b[1]" == 1);
4229 Skip over the initial portion of the first given range (`haystack`) that matches
4230 any of the additionally given ranges (`needles`) fully, or
4231 if no second range is given skip over the elements that fulfill pred.
4232 Do nothing if there is no match.
4235 pred = The predicate that determines whether elements from each respective
4236 range match. Defaults to equality `"a == b"`.
4238 template skipOver(alias pred = (a, b) => a == b)
4240 enum bool isPredComparable(T) = ifTestable!(T, binaryFun!pred);
4244 haystack = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to
4246 needles = The $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives)
4247 representing the prefix of `r1` to skip over.
4248 es = The element to match.
4251 `true` if the prefix of `haystack` matches any range of `needles` fully
4252 or `pred` evaluates to true, and `haystack` has been advanced to the point past this segment;
4253 otherwise false, and `haystack` is left in its original position.
4256 By definition, empty ranges are matched fully and if `needles` contains an empty range,
4257 `skipOver` will return `true`.
4259 bool skipOver(Haystack, Needles...)(ref Haystack haystack, Needles needles)
4260 if (is(typeof(binaryFun!pred(haystack.front, needles[0].front))) &&
4261 isForwardRange!Haystack &&
4262 allSatisfy!(isInputRange, Needles) &&
4263 !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Needles))) == void))
4265 static if (__traits(isSame, pred, (a, b) => a == b)
4266 && is(typeof(haystack[0 .. $] == needles[0]) : bool)
4267 && is(typeof(haystack = haystack[0 .. $]))
4268 && hasLength!Haystack && allSatisfy!(hasLength, Needles))
4270 ptrdiff_t longestMatch = -1;
4271 static foreach (r2; needles)
4273 if (r2.length <= haystack.length && longestMatch < ptrdiff_t(r2.length)
4274 && (haystack[0 .. r2.length] == r2 || r2.length == 0))
4275 longestMatch = r2.length;
4277 if (longestMatch >= 0)
4279 if (longestMatch > 0)
4280 haystack = haystack[longestMatch .. $];
4288 import std.algorithm.comparison : min;
4289 auto r = haystack.save;
4291 static if (hasLength!Haystack && allSatisfy!(hasLength, Needles))
4293 import std.algorithm.iteration : map;
4294 import std.algorithm.searching : minElement;
4295 import std.range : only;
4296 // Shortcut opportunity!
4297 if (needles.only.map!(a => a.length).minElement > haystack.length)
4301 // compatibility: return true if any range was empty
4302 bool hasEmptyRanges;
4303 static foreach (i, r2; needles)
4306 hasEmptyRanges = true;
4309 bool hasNeedleMatch;
4310 size_t inactiveNeedlesLen;
4311 bool[Needles.length] inactiveNeedles;
4312 for (; !r.empty; r.popFront)
4314 static foreach (i, r2; needles)
4316 if (!r2.empty && !inactiveNeedles[i])
4318 if (binaryFun!pred(r.front, r2.front))
4323 // we skipped over a new match
4324 hasNeedleMatch = true;
4325 inactiveNeedlesLen++;
4326 // skip over haystack
4332 inactiveNeedles[i] = true;
4333 inactiveNeedlesLen++;
4339 if (inactiveNeedlesLen == needles.length)
4346 return hasNeedleMatch || hasEmptyRanges;
4351 bool skipOver(R)(ref R r1)
4352 if (isForwardRange!R &&
4353 ifTestable!(typeof(r1.front), unaryFun!pred))
4355 if (r1.empty || !unaryFun!pred(r1.front))
4360 while (!r1.empty && unaryFun!pred(r1.front));
4365 bool skipOver(R, Es...)(ref R r, Es es)
4366 if (isInputRange!R && is(typeof(binaryFun!pred(r.front, es[0]))))
4371 static foreach (e; es)
4373 if (binaryFun!pred(r.front, e))
4386 import std.algorithm.comparison : equal;
4388 auto s1 = "Hello world";
4389 assert(!skipOver(s1, "Ha"));
4390 assert(s1 == "Hello world");
4391 assert(skipOver(s1, "Hell") && s1 == "o world", s1);
4393 string[] r1 = ["abc", "def", "hij"];
4394 dstring[] r2 = ["abc"d];
4395 assert(!skipOver!((a, b) => a.equal(b))(r1, ["def"d]), r1[0]);
4396 assert(r1 == ["abc", "def", "hij"]);
4397 assert(skipOver!((a, b) => a.equal(b))(r1, r2));
4398 assert(r1 == ["def", "hij"]);
4404 import std.ascii : isWhite;
4405 import std.range.primitives : empty;
4407 auto s2 = "\t\tvalue";
4410 assert(s2.skipOver!isWhite && s2 == "value");
4411 assert(!s3.skipOver!isWhite);
4412 assert(s4.skipOver!isWhite && s3.empty);
4415 /// Variadic skipOver
4418 auto s = "Hello world";
4419 assert(!skipOver(s, "hello", "HellO"));
4420 assert(s == "Hello world");
4422 // the range is skipped over the longest matching needle is skipped
4423 assert(skipOver(s, "foo", "hell", "Hello "));
4424 assert(s == "world");
4430 import std.algorithm.comparison : equal;
4432 auto s1 = "Hello world";
4433 assert(!skipOver(s1, 'a'));
4434 assert(s1 == "Hello world");
4435 assert(skipOver(s1, 'H') && s1 == "ello world");
4437 string[] r = ["abc", "def", "hij"];
4439 assert(!skipOver!((a, b) => a.equal(b))(r, "def"d));
4440 assert(r == ["abc", "def", "hij"]);
4441 assert(skipOver!((a, b) => a.equal(b))(r, e));
4442 assert(r == ["def", "hij"]);
4445 assert(!s2.skipOver('a'));
4448 /// Partial instantiation
4451 import std.ascii : isWhite;
4452 import std.range.primitives : empty;
4454 alias whitespaceSkiper = skipOver!isWhite;
4456 auto s2 = "\t\tvalue";
4459 assert(whitespaceSkiper(s2) && s2 == "value");
4460 assert(!whitespaceSkiper(s2));
4461 assert(whitespaceSkiper(s4) && s3.empty);
4464 // variadic skipOver
4467 auto s = "DLang.rocks";
4468 assert(!s.skipOver("dlang", "DLF", "DLang "));
4469 assert(s == "DLang.rocks");
4471 assert(s.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLanpp"));
4472 assert(s == "ang.rocks");
4475 assert(s.skipOver("DLang", "DLANG", "DLF", "D", "DL", "DLang "));
4476 assert(s == ".rocks");
4479 assert(s.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLang."));
4480 assert(s == "rocks");
4483 // variadic with custom pred
4486 import std.ascii : toLower;
4488 auto s = "DLang.rocks";
4489 assert(!s.skipOver("dlang", "DLF", "DLang "));
4490 assert(s == "DLang.rocks");
4492 assert(s.skipOver!((a, b) => a.toLower == b.toLower)("dlang", "DLF", "DLang "));
4493 assert(s == ".rocks");
4496 // variadic skipOver with mixed needles
4499 auto s = "DLang.rocks";
4500 assert(!s.skipOver("dlang"d, "DLF", "DLang "w));
4501 assert(s == "DLang.rocks");
4503 assert(s.skipOver("dlang", "DLANG"d, "DLF"w, "D"d, "DL", "DLanp"));
4504 assert(s == "ang.rocks");
4507 assert(s.skipOver("DLang", "DLANG"w, "DLF"d, "D"d, "DL", "DLang "));
4508 assert(s == ".rocks");
4511 assert(s.skipOver("dlang", "DLANG"w, "DLF", "D"d, "DL"w, "DLang."d));
4512 assert(s == "rocks");
4514 import std.algorithm.iteration : filter;
4516 assert(s.skipOver("dlang", "DLang".filter!(a => true)));
4517 assert(s == ".rocks");
4520 // variadic skipOver with auto-decoding
4524 assert(s.skipOver("a", "☢", "☢☣☠"));
4528 // skipOver with @nogc
4529 @safe @nogc pure nothrow unittest
4531 static immutable s = [0, 1, 2];
4532 immutable(int)[] s2 = s[];
4534 static immutable skip1 = [0, 2];
4535 static immutable skip2 = [0, 1];
4536 assert(s2.skipOver(skip1, skip2));
4537 assert(s2 == s[2 .. $]);
4540 // variadic skipOver with single elements
4543 auto s = "DLang.rocks";
4544 assert(!s.skipOver('a', 'd', 'e'));
4545 assert(s == "DLang.rocks");
4547 assert(s.skipOver('a', 'D', 'd', 'D'));
4548 assert(s == "Lang.rocks");
4551 assert(s.skipOver(wchar('a'), dchar('D'), 'd'));
4552 assert(s == "Lang.rocks");
4554 dstring dstr = "+Foo";
4555 assert(!dstr.skipOver('.', '-'));
4556 assert(dstr == "+Foo");
4558 assert(dstr.skipOver('+', '-'));
4559 assert(dstr == "Foo");
4562 // skipOver with empty ranges must return true (compatibility)
4565 auto s = "DLang.rocks";
4566 assert(s.skipOver(""));
4567 assert(s.skipOver("", ""));
4568 assert(s.skipOver("", "foo"));
4570 auto s2 = "DLang.rocks"d;
4571 assert(s2.skipOver(""));
4572 assert(s2.skipOver("", ""));
4573 assert(s2.skipOver("", "foo"));
4579 import std.utf : byCodeUnit;
4580 import std.algorithm.comparison : equal;
4582 bool stripStartsWith(Text)(ref Text text, string needle)
4584 return text.skipOver(needle.byCodeUnit());
4586 auto text = "<xml></xml>"d.byCodeUnit;
4587 assert(stripStartsWith(text, "<xml>"));
4588 assert(text.equal("</xml>"));
4592 Checks whether the given
4593 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) starts with (one
4594 of) the given needle(s) or, if no needles are given,
4595 if its front element fulfils predicate `pred`.
4597 For more information about `pred` see $(LREF find).
4601 pred = Predicate to use in comparing the elements of the haystack and the
4602 needle(s). Mandatory if no needles are given.
4604 doesThisStart = The input range to check.
4606 withOneOfThese = The needles against which the range is to be checked,
4607 which may be individual elements or input ranges of elements.
4609 withThis = The single needle to check, which may be either a single element
4610 or an input range of elements.
4614 0 if the needle(s) do not occur at the beginning of the given range;
4615 otherwise the position of the matching needle, that is, 1 if the range starts
4616 with `withOneOfThese[0]`, 2 if it starts with `withOneOfThese[1]`, and so
4619 In the case where `doesThisStart` starts with multiple of the ranges or
4620 elements in `withOneOfThese`, then the shortest one matches (if there are
4621 two which match which are of the same length (e.g. `"a"` and `'a'`), then
4622 the left-most of them in the argument
4625 In the case when no needle parameters are given, return `true` iff front of
4626 `doesThisStart` fulfils predicate `pred`.
4628 uint startsWith(alias pred = (a, b) => a == b, Range, Needles...)(Range doesThisStart, Needles withOneOfThese)
4629 if (isInputRange!Range && Needles.length > 1 &&
4630 allSatisfy!(canTestStartsWith!(pred, Range), Needles))
4632 template checkType(T)
4634 enum checkType = is(immutable ElementEncodingType!Range == immutable T);
4637 // auto-decoding special case
4638 static if (__traits(isSame, binaryFun!pred, (a, b) => a == b) &&
4639 isNarrowString!Range && allSatisfy!(checkType, Needles))
4641 import std.utf : byCodeUnit;
4642 auto haystack = doesThisStart.byCodeUnit;
4646 alias haystack = doesThisStart;
4648 alias needles = withOneOfThese;
4650 // Make one pass looking for empty ranges in needles
4651 foreach (i, Unused; Needles)
4653 // Empty range matches everything
4654 static if (!is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool))
4656 if (needles[i].empty) return i + 1;
4660 for (; !haystack.empty; haystack.popFront())
4662 foreach (i, Unused; Needles)
4664 static if (is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool))
4667 if (binaryFun!pred(haystack.front, needles[i]))
4669 // found, but instead of returning, we just stop searching.
4670 // This is to account for one-element
4671 // range matches (consider startsWith("ab", "a",
4672 // 'a') should return 1, not 2).
4678 if (binaryFun!pred(haystack.front, needles[i].front))
4684 // This code executed on failure to match
4685 // Out with this guy, check for the others
4686 uint result = startsWith!pred(haystack, needles[0 .. i], needles[i + 1 .. $]);
4687 if (result > i) ++result;
4691 // If execution reaches this point, then the front matches for all
4692 // needle ranges, or a needle element has been matched.
4693 // What we need to do now is iterate, lopping off the front of
4694 // the range and checking if the result is empty, or finding an
4695 // element needle and returning.
4696 // If neither happens, we drop to the end and loop.
4697 foreach (i, Unused; Needles)
4699 static if (is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool))
4701 // Test has passed in the previous loop
4706 needles[i].popFront();
4707 if (needles[i].empty) return i + 1;
4715 bool startsWith(alias pred = "a == b", R1, R2)(R1 doesThisStart, R2 withThis)
4716 if (isInputRange!R1 &&
4718 is(typeof(binaryFun!pred(doesThisStart.front, withThis.front)) : bool))
4720 alias haystack = doesThisStart;
4721 alias needle = withThis;
4723 static if (is(typeof(pred) : string))
4724 enum isDefaultPred = pred == "a == b";
4726 enum isDefaultPred = false;
4728 // Note: Although narrow strings don't have a "true" length, for a narrow string to start with another
4729 // narrow string, it must have *at least* as many code units.
4730 static if ((hasLength!R1 && hasLength!R2) ||
4731 ((hasLength!R1 || isNarrowString!R1) && (hasLength!R2 || isNarrowString!R2)
4732 && (ElementEncodingType!R1.sizeof <= ElementEncodingType!R2.sizeof)))
4734 if (haystack.length < needle.length)
4738 static if (isDefaultPred && isArray!R1 && isArray!R2 &&
4739 is(immutable ElementEncodingType!R1 == immutable ElementEncodingType!R2))
4741 //Array slice comparison mode
4742 return haystack[0 .. needle.length] == needle;
4744 else static if (isRandomAccessRange!R1 && isRandomAccessRange!R2 && hasLength!R2)
4746 //RA dual indexing mode
4747 foreach (j; 0 .. needle.length)
4749 if (!binaryFun!pred(haystack[j], needle[j]))
4758 //Standard input range mode
4759 if (needle.empty) return true;
4760 static if (hasLength!R1 && hasLength!R2)
4762 //We have previously checked that haystack.length > needle.length,
4763 //So no need to check haystack.empty during iteration
4764 for ( ; ; haystack.popFront() )
4766 if (!binaryFun!pred(haystack.front, needle.front)) break;
4768 if (needle.empty) return true;
4773 for ( ; !haystack.empty ; haystack.popFront() )
4775 if (!binaryFun!pred(haystack.front, needle.front)) break;
4777 if (needle.empty) return true;
4785 bool startsWith(alias pred = "a == b", R, E)(R doesThisStart, E withThis)
4786 if (isInputRange!R &&
4787 is(typeof(binaryFun!pred(doesThisStart.front, withThis)) : bool))
4789 if (doesThisStart.empty)
4792 static if (is(typeof(pred) : string))
4793 enum isDefaultPred = pred == "a == b";
4795 enum isDefaultPred = false;
4797 alias predFunc = binaryFun!pred;
4799 // auto-decoding special case
4800 static if (isNarrowString!R)
4802 // statically determine decoding is unnecessary to evaluate pred
4803 static if (isDefaultPred && isSomeChar!E && E.sizeof <= ElementEncodingType!R.sizeof)
4804 return doesThisStart[0] == withThis;
4805 // specialize for ASCII as to not change previous behavior
4808 if (withThis <= 0x7F)
4809 return predFunc(doesThisStart[0], withThis);
4811 return predFunc(doesThisStart.front, withThis);
4816 return predFunc(doesThisStart.front, withThis);
4821 bool startsWith(alias pred, R)(R doesThisStart)
4822 if (isInputRange!R &&
4823 ifTestable!(typeof(doesThisStart.front), unaryFun!pred))
4825 return !doesThisStart.empty && unaryFun!pred(doesThisStart.front);
4831 import std.ascii : isAlpha;
4833 assert("abc".startsWith!(a => a.isAlpha));
4834 assert("abc".startsWith!isAlpha);
4835 assert(!"1ab".startsWith!(a => a.isAlpha));
4836 assert(!"".startsWith!(a => a.isAlpha));
4838 import std.algorithm.comparison : among;
4839 assert("abc".startsWith!(a => a.among('a', 'b') != 0));
4840 assert(!"abc".startsWith!(a => a.among('b', 'c') != 0));
4842 assert(startsWith("abc", ""));
4843 assert(startsWith("abc", "a"));
4844 assert(!startsWith("abc", "b"));
4845 assert(startsWith("abc", 'a', "b") == 1);
4846 assert(startsWith("abc", "b", "a") == 2);
4847 assert(startsWith("abc", "a", "a") == 1);
4848 assert(startsWith("abc", "ab", "a") == 2);
4849 assert(startsWith("abc", "x", "a", "b") == 2);
4850 assert(startsWith("abc", "x", "aa", "ab") == 3);
4851 assert(startsWith("abc", "x", "aaa", "sab") == 0);
4852 assert(startsWith("abc", "x", "aaa", "a", "sab") == 3);
4854 import std.typecons : Tuple;
4855 alias C = Tuple!(int, "x", int, "y");
4856 assert(startsWith!"a.x == b"([ C(1,1), C(1,2), C(2,2) ], [1, 1]));
4857 assert(startsWith!"a.x == b"([ C(1,1), C(2,1), C(2,2) ], [1, 1], [1, 2], [1, 3]) == 2);
4862 import std.algorithm.iteration : filter;
4863 import std.conv : to;
4864 import std.meta : AliasSeq;
4867 static foreach (S; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
4868 (){ // workaround slow optimizations for large functions
4869 // https://issues.dlang.org/show_bug.cgi?id=2396
4870 assert(!startsWith(to!S("abc"), 'c'));
4871 assert(startsWith(to!S("abc"), 'a', 'c') == 1);
4872 assert(!startsWith(to!S("abc"), 'x', 'n', 'b'));
4873 assert(startsWith(to!S("abc"), 'x', 'n', 'a') == 3);
4874 assert(startsWith(to!S("\uFF28abc"), 'a', '\uFF28', 'c') == 2);
4876 static foreach (T; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
4879 assert(startsWith(to!S("abc"), to!T("")));
4880 assert(startsWith(to!S("ab"), to!T("a")));
4881 assert(startsWith(to!S("abc"), to!T("a")));
4882 assert(!startsWith(to!S("abc"), to!T("b")));
4883 assert(!startsWith(to!S("abc"), to!T("b"), "bc", "abcd", "xyz"));
4884 assert(startsWith(to!S("abc"), to!T("ab"), 'a') == 2);
4885 assert(startsWith(to!S("abc"), to!T("a"), "b") == 1);
4886 assert(startsWith(to!S("abc"), to!T("b"), "a") == 2);
4887 assert(startsWith(to!S("abc"), to!T("a"), 'a') == 1);
4888 assert(startsWith(to!S("abc"), 'a', to!T("a")) == 1);
4889 assert(startsWith(to!S("abc"), to!T("x"), "a", "b") == 2);
4890 assert(startsWith(to!S("abc"), to!T("x"), "aa", "ab") == 3);
4891 assert(startsWith(to!S("abc"), to!T("x"), "aaa", "sab") == 0);
4892 assert(startsWith(to!S("abc"), 'a'));
4893 assert(!startsWith(to!S("abc"), to!T("sab")));
4894 assert(startsWith(to!S("abc"), 'x', to!T("aaa"), 'a', "sab") == 3);
4897 assert(startsWith(to!S("\uFF28el\uFF4co"), to!T("\uFF28el")));
4898 assert(startsWith(to!S("\uFF28el\uFF4co"), to!T("Hel"), to!T("\uFF28el")) == 2);
4899 assert(startsWith(to!S("日本語"), to!T("日本")));
4900 assert(startsWith(to!S("日本語"), to!T("日本語")));
4901 assert(!startsWith(to!S("日本"), to!T("日本語")));
4904 assert(startsWith(to!S(""), T.init));
4905 assert(!startsWith(to!S(""), 'a'));
4906 assert(startsWith(to!S("a"), T.init));
4907 assert(startsWith(to!S("a"), T.init, "") == 1);
4908 assert(startsWith(to!S("a"), T.init, 'a') == 1);
4909 assert(startsWith(to!S("a"), 'a', T.init) == 2);
4914 assert(!startsWith("abc".takeExactly(3), "abcd".takeExactly(4)));
4915 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(3)));
4916 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(1)));
4918 static foreach (T; AliasSeq!(int, short))
4920 immutable arr = cast(T[])[0, 1, 2, 3, 4, 5];
4923 assert(startsWith(arr, cast(int[]) null));
4924 assert(!startsWith(arr, 5));
4925 assert(!startsWith(arr, 1));
4926 assert(startsWith(arr, 0));
4927 assert(startsWith(arr, 5, 0, 1) == 2);
4928 assert(startsWith(arr, [0]));
4929 assert(startsWith(arr, [0, 1]));
4930 assert(startsWith(arr, [0, 1], 7) == 1);
4931 assert(!startsWith(arr, [0, 1, 7]));
4932 assert(startsWith(arr, [0, 1, 7], [0, 1, 2]) == 2);
4934 //Normal input range
4935 assert(!startsWith(filter!"true"(arr), 1));
4936 assert(startsWith(filter!"true"(arr), 0));
4937 assert(startsWith(filter!"true"(arr), [0]));
4938 assert(startsWith(filter!"true"(arr), [0, 1]));
4939 assert(startsWith(filter!"true"(arr), [0, 1], 7) == 1);
4940 assert(!startsWith(filter!"true"(arr), [0, 1, 7]));
4941 assert(startsWith(filter!"true"(arr), [0, 1, 7], [0, 1, 2]) == 2);
4942 assert(startsWith(arr, filter!"true"([0, 1])));
4943 assert(startsWith(arr, filter!"true"([0, 1]), 7) == 1);
4944 assert(!startsWith(arr, filter!"true"([0, 1, 7])));
4945 assert(startsWith(arr, [0, 1, 7], filter!"true"([0, 1, 2])) == 2);
4948 assert(startsWith!("a%10 == b%10")(arr, [10, 11]));
4949 assert(!startsWith!("a%10 == b%10")(arr, [10, 12]));
4953 private template canTestStartsWith(alias pred, Haystack)
4955 enum bool canTestStartsWith(Needle) = is(typeof(
4956 (ref Haystack h, ref Needle n) => startsWith!pred(h, n)));
4959 /* (Not yet documented.)
4960 Consume all elements from `r` that are equal to one of the elements
4963 private void skipAll(alias pred = "a == b", R, Es...)(ref R r, Es es)
4964 //if (is(typeof(binaryFun!pred(r1.front, es[0]))))
4967 for (; !r.empty; r.popFront())
4971 if (binaryFun!pred(r.front, es[i]))
4982 auto s1 = "Hello world";
4983 skipAll(s1, 'H', 'e');
4984 assert(s1 == "llo world");
4988 Interval option specifier for `until` (below) and others.
4990 If set to `OpenRight.yes`, then the interval is open to the right
4991 (last element is not included).
4993 Otherwise if set to `OpenRight.no`, then the interval is closed to the right
4994 including the entire sentinel.
4996 alias OpenRight = Flag!"openRight";
4999 Lazily iterates `range` _until the element `e` for which
5000 `pred(e, sentinel)` is true.
5002 This is similar to `takeWhile` in other languages.
5005 pred = Predicate to determine when to stop.
5006 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
5008 sentinel = The element to stop at.
5009 openRight = Determines whether the element for which the given predicate is
5010 true should be included in the resulting range (`No.openRight`), or
5011 not (`Yes.openRight`).
5014 An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) that
5015 iterates over the original range's elements, but ends when the specified
5016 predicate becomes true. If the original range is a
5017 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) or
5018 higher, this range will be a forward range.
5020 Until!(pred, Range, Sentinel)
5021 until(alias pred = "a == b", Range, Sentinel)
5022 (Range range, Sentinel sentinel, OpenRight openRight = Yes.openRight)
5023 if (!is(Sentinel == OpenRight))
5025 return typeof(return)(range, sentinel, openRight);
5029 Until!(pred, Range, void)
5030 until(alias pred, Range)
5031 (Range range, OpenRight openRight = Yes.openRight)
5033 return typeof(return)(range, openRight);
5037 struct Until(alias pred, Range, Sentinel)
5038 if (isInputRange!Range)
5040 private Range _input;
5041 static if (!is(Sentinel == void))
5042 private Sentinel _sentinel;
5043 private OpenRight _openRight;
5044 private bool _matchStarted;
5047 static if (!is(Sentinel == void))
5050 this(Range input, Sentinel sentinel,
5051 OpenRight openRight = Yes.openRight)
5054 _sentinel = sentinel;
5055 _openRight = openRight;
5056 static if (isInputRange!Sentinel
5057 && is(immutable ElementEncodingType!Sentinel == immutable ElementEncodingType!Range))
5059 _matchStarted = predSatisfied();
5060 _done = _input.empty || _sentinel.empty || openRight && _matchStarted;
5061 if (_matchStarted && !_done && !openRight)
5068 _done = _input.empty || openRight && predSatisfied();
5071 private this(Range input, Sentinel sentinel, OpenRight openRight,
5075 _sentinel = sentinel;
5076 _openRight = openRight;
5083 this(Range input, OpenRight openRight = Yes.openRight)
5086 _openRight = openRight;
5087 _done = _input.empty || openRight && predSatisfied();
5089 private this(Range input, OpenRight openRight, bool done)
5092 _openRight = openRight;
5098 @property bool empty()
5104 @property auto ref front()
5106 assert(!empty, "Can not get the front of an empty Until");
5107 return _input.front;
5110 private bool predSatisfied()
5112 static if (is(Sentinel == void))
5113 return cast(bool) unaryFun!pred(_input.front);
5115 return cast(bool) startsWith!pred(_input, _sentinel);
5121 assert(!empty, "Can not popFront of an empty Until");
5124 static if (isInputRange!Sentinel
5125 && is(immutable ElementEncodingType!Sentinel == immutable ElementEncodingType!Range))
5128 _done = _input.empty || _sentinel.empty;
5137 _matchStarted = predSatisfied();
5147 _done = predSatisfied();
5149 _done = _done || _input.empty;
5155 _done = _input.empty || predSatisfied();
5159 static if (isForwardRange!Range)
5162 @property Until save()
5164 static if (is(Sentinel == void))
5165 return Until(_input.save, _openRight, _done);
5167 return Until(_input.save, _sentinel, _openRight, _done);
5175 import std.algorithm.comparison : equal;
5176 import std.typecons : No;
5177 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
5178 assert(equal(a.until(7), [1, 2, 4]));
5179 assert(equal(a.until(7, No.openRight), [1, 2, 4, 7]));
5184 import std.algorithm.comparison : equal;
5185 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
5187 static assert(isForwardRange!(typeof(a.until(7))));
5188 static assert(isForwardRange!(typeof(until!"a == 2"(a, No.openRight))));
5190 assert(equal(a.until(7), [1, 2, 4]));
5191 assert(equal(a.until([7, 2]), [1, 2, 4, 7]));
5192 assert(equal(a.until(7, No.openRight), [1, 2, 4, 7]));
5193 assert(equal(until!"a == 2"(a, No.openRight), [1, 2]));
5196 // https://issues.dlang.org/show_bug.cgi?id=13171
5199 import std.algorithm.comparison : equal;
5201 auto a = [1, 2, 3, 4];
5202 assert(equal(refRange(&a).until(3, No.openRight), [1, 2, 3]));
5206 // https://issues.dlang.org/show_bug.cgi?id=10460
5209 import std.algorithm.comparison : equal;
5210 auto a = [1, 2, 3, 4];
5211 foreach (ref e; a.until(3))
5213 assert(equal(a, [0, 0, 3, 4]));
5216 // https://issues.dlang.org/show_bug.cgi?id=13124
5219 import std.algorithm.comparison : among, equal;
5220 auto s = "hello how\nare you";
5221 assert(equal(s.until!(c => c.among!('\n', '\r')), "hello how"));
5224 // https://issues.dlang.org/show_bug.cgi?id=18657
5227 import std.algorithm.comparison : equal;
5228 import std.range : refRange;
5230 string s = "foobar";
5231 auto r = refRange(&s).until("bar");
5232 assert(equal(r.save, "foo"));
5233 assert(equal(r.save, "foo"));
5236 string s = "foobar";
5237 auto r = refRange(&s).until!(e => e == 'b');
5238 assert(equal(r.save, "foo"));
5239 assert(equal(r.save, "foo"));
5243 // https://issues.dlang.org/show_bug.cgi?id=14543
5246 import std.algorithm.comparison : equal;
5247 import std.uni : toUpper;
5248 assert("one two three".until("two").equal("one "));
5249 assert("one two three".until("two", OpenRight.no).equal("one two"));
5251 assert("one two three".until("two", No.openRight).equal("one two"));
5252 assert("one two three".until("two", Yes.openRight).equal("one "));
5254 assert("one two three".until('t', Yes.openRight).equal("one "));
5255 assert("one two three".until("", Yes.openRight).equal(""));
5256 assert("one two three".until("", No.openRight).equal(""));
5258 assert("one two three".until("three", No.openRight).equal("one two three"));
5259 assert("one two three".until("three", Yes.openRight).equal("one two "));
5261 assert("one two three".until("one", No.openRight).equal("one"));
5262 assert("one two three".until("one", Yes.openRight).equal(""));
5264 assert("one two three".until("o", No.openRight).equal("o"));
5265 assert("one two three".until("o", Yes.openRight).equal(""));
5267 assert("one two three".until("", No.openRight).equal(""));
5268 assert("one two three".until("", Yes.openRight).equal(""));
5270 assert("one two three".until!((a,b)=>a.toUpper == b)("TWO", No.openRight).equal("one two"));
5273 // https://issues.dlang.org/show_bug.cgi?id=24342
5276 import std.algorithm.comparison : equal;
5277 assert(["A", "BC", "D"].until("BC", No.openRight).equal(["A", "BC"]));
5278 assert([[1], [2, 3], [4]].until([2, 3], No.openRight).equal([[1], [2, 3]]));