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 all elements or elements matching a predicate, specific element or sub-range.$(BR)
26 `count([1, 2, 1])` returns `3`,
27 `count([1, 2, 1], 1)` returns `2` and
28 `count!"a < 0"([1, -3, 0])` returns `1`.)
30 `countUntil(a, b)` returns the number of steps taken in `a` to
31 reach `b`; for example, `countUntil("hello!", "o")` returns
34 `commonPrefix("parakeet", "parachute")` returns `"para"`.)
36 `endsWith("rocks", "ks")` returns `true`.)
37 $(T2 extrema, `extrema([2, 1, 3, 5, 4])` returns `[1, 5]`.)
39 `find("hello world", "or")` returns `"orld"` using linear search.
40 (For binary search refer to $(REF SortedRange, std,range).))
42 `findAdjacent([1, 2, 3, 3, 4])` returns the subrange starting with
43 two equal adjacent elements, i.e. `[3, 3, 4]`.)
45 `findAmong("abcd", "qcx")` returns `"cd"` because `'c'` is
48 If `a = "abcde"`, then `findSkip(a, "x")` returns `false` and
49 leaves `a` unchanged, whereas `findSkip(a, "c")` advances `a`
50 to `"de"` and returns `true`.)
52 `findSplit("abcdefg", "de")` returns a tuple of three ranges `"abc"`,
55 `findSplitAfter("abcdefg", "de")` returns a tuple of two ranges `"abcde"`
58 `findSplitBefore("abcdefg", "de")` returns a tuple of two ranges `"abc"`
61 `minCount([2, 1, 1, 4, 1])` returns `tuple(1, 3)`.)
63 `maxCount([2, 4, 1, 4, 1])` returns `tuple(4, 2)`.)
65 Selects the minimal element of a range.
66 `minElement([3, 4, 1, 2])` returns `1`.)
68 Selects the maximal element of a range.
69 `maxElement([3, 4, 1, 2])` returns `4`.)
71 Index of the minimal element of a range.
72 `minIndex([3, 4, 1, 2])` returns `2`.)
74 Index of the maximal element of a range.
75 `maxIndex([3, 4, 1, 2])` returns `1`.)
77 `minPos([2, 3, 1, 3, 4, 1])` returns the subrange `[1, 3, 4, 1]`,
78 i.e., positions the range at the first occurrence of its minimal
81 `maxPos([2, 3, 1, 3, 4, 1])` returns the subrange `[4, 1]`,
82 i.e., positions the range at the first occurrence of its maximal
85 Assume `a = "blah"`. Then `skipOver(a, "bi")` leaves `a`
86 unchanged and returns `false`, whereas `skipOver(a, "bl")`
87 advances `a` to refer to `"ah"` and returns `true`.)
89 `startsWith("hello, world", "hello")` returns `true`.)
91 Lazily iterates a range until a specific value is found.)
94 Copyright: Andrei Alexandrescu 2008-.
96 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
98 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
100 Source: $(PHOBOSSRC std/algorithm/searching.d)
103 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
105 module std.algorithm.searching;
107 import std.functional : unaryFun, binaryFun;
108 import std.meta : allSatisfy;
109 import std.range.primitives;
111 import std.typecons : Tuple, Flag, Yes, No, tuple;
114 Checks if $(I _all) of the elements satisfy `pred`.
116 template all(alias pred = "a")
119 Returns `true` if and only if the input range `range` is empty
120 or $(I _all) values found in `range` satisfy the predicate `pred`.
121 Performs (at most) $(BIGOH range.length) evaluations of `pred`.
123 bool all(Range)(Range range)
124 if (isInputRange!Range &&
125 (__traits(isTemplate, pred) || is(typeof(unaryFun!pred(range.front)))))
127 import std.functional : not;
129 return find!(not!(unaryFun!pred))(range).empty;
136 assert( all!"a & 1"([1, 3, 5, 7, 9]));
137 assert(!all!"a & 1"([1, 2, 3, 5, 7, 9]));
141 `all` can also be used without a predicate, if its items can be
142 evaluated to true or false in a conditional statement. This can be a
143 convenient way to quickly evaluate that $(I _all) of the elements of a range
148 int[3] vals = [5, 3, 18];
149 assert( all(vals[]));
155 assert(all!(a => a > x)([2, 3]));
156 assert(all!"a == 0x00c9"("\xc3\x89")); // Test that `all` auto-decodes.
160 Checks if $(I _any) of the elements satisfies `pred`.
161 `!any` can be used to verify that $(I none) of the elements satisfy
163 This is sometimes called `exists` in other languages.
165 template any(alias pred = "a")
168 Returns `true` if and only if the input range `range` is non-empty
169 and $(I _any) value found in `range` satisfies the predicate
171 Performs (at most) $(BIGOH range.length) evaluations of `pred`.
173 bool any(Range)(Range range)
174 if (isInputRange!Range &&
175 (__traits(isTemplate, pred) || is(typeof(unaryFun!pred(range.front)))))
177 return !find!pred(range).empty;
184 import std.ascii : isWhite;
185 assert( all!(any!isWhite)(["a a", "b b"]));
186 assert(!any!(all!isWhite)(["a a", "b b"]));
190 `any` can also be used without a predicate, if its items can be
191 evaluated to true or false in a conditional statement. `!any` can be a
192 convenient way to quickly test that $(I none) of the elements of a range
197 int[3] vals1 = [0, 0, 0];
198 assert(!any(vals1[])); //none of vals1 evaluate to true
200 int[3] vals2 = [2, 0, 2];
201 assert( any(vals2[]));
202 assert(!all(vals2[]));
204 int[3] vals3 = [3, 3, 3];
205 assert( any(vals3[]));
206 assert( all(vals3[]));
211 auto a = [ 1, 2, 0, 4 ];
212 assert(any!"a == 2"(a));
213 assert(any!"a == 0x3000"("\xe3\x80\x80")); // Test that `any` auto-decodes.
218 Checks whether `r` has "balanced parentheses", i.e. all instances
219 of `lPar` are closed by corresponding instances of `rPar`. The
220 parameter `maxNestingLevel` controls the nesting level allowed. The
221 most common uses are the default or `0`. In the latter case, no
225 r = The range to check.
226 lPar = The element corresponding with a left (opening) parenthesis.
227 rPar = The element corresponding with a right (closing) parenthesis.
228 maxNestingLevel = The maximum allowed nesting level.
231 true if the given range has balanced parenthesis within the given maximum
232 nesting level; false otherwise.
234 bool balancedParens(Range, E)(Range r, E lPar, E rPar,
235 size_t maxNestingLevel = size_t.max)
236 if (isInputRange!(Range) && is(typeof(r.front == lPar)))
240 static if (is(immutable ElementEncodingType!Range == immutable E) && isNarrowString!Range)
242 import std.utf : byCodeUnit;
243 auto rn = r.byCodeUnit;
250 for (; !rn.empty; rn.popFront())
252 if (rn.front == lPar)
254 if (count > maxNestingLevel) return false;
257 else if (rn.front == rPar)
259 if (!count) return false;
269 auto s = "1 + (2 * (3 + 1 / 2)";
270 assert(!balancedParens(s, '(', ')'));
271 s = "1 + (2 * (3 + 1) / 2)";
272 assert(balancedParens(s, '(', ')'));
273 s = "1 + (2 * (3 + 1) / 2)";
274 assert(!balancedParens(s, '(', ')', 0));
275 s = "1 + (2 * 3 + 1) / (2 - 5)";
276 assert(balancedParens(s, '(', ')', 0));
278 assert(balancedParens(s, '⌈', '⌉'));
282 * Sets up Boyer-Moore matching for use with `find` below.
283 * By default, elements are compared for equality.
285 * `BoyerMooreFinder` allocates GC memory.
288 * pred = Predicate used to compare elements.
289 * needle = A random-access range with length and slicing.
292 * An instance of `BoyerMooreFinder` that can be used with `find()` to
293 * invoke the Boyer-Moore matching algorithm for finding of `needle` in a
296 struct BoyerMooreFinder(alias pred, Range)
299 size_t[] skip; // GC allocated
300 ptrdiff_t[ElementType!(Range)] occ; // GC allocated
303 ptrdiff_t occurrence(ElementType!(Range) c) scope
310 This helper function checks whether the last "portion" bytes of
311 "needle" (which is "nlen" bytes long) exist within the "needle" at
312 offset "offset" (counted from the end of the string), and whether the
313 character preceding "offset" is not a match. Notice that the range
314 being checked may reach beyond the beginning of the string. Such range
317 static bool needlematch(R)(R needle,
318 size_t portion, size_t offset)
320 import std.algorithm.comparison : equal;
321 ptrdiff_t virtual_begin = needle.length - offset - portion;
322 ptrdiff_t ignore = 0;
323 if (virtual_begin < 0)
325 ignore = -virtual_begin;
328 if (virtual_begin > 0
329 && needle[virtual_begin - 1] == needle[$ - portion - 1])
332 immutable delta = portion - ignore;
333 return equal(needle[needle.length - delta .. needle.length],
334 needle[virtual_begin .. virtual_begin + delta]);
341 if (!needle.length) return;
342 this.needle = needle;
343 /* Populate table with the analysis of the needle */
344 /* But ignoring the last letter */
345 foreach (i, n ; needle[0 .. $ - 1])
349 /* Preprocess #2: init skip[] */
350 /* Note: This step could be made a lot faster.
351 * A simple implementation is shown here. */
352 this.skip = new size_t[needle.length];
353 foreach (a; 0 .. needle.length)
356 while (value < needle.length
357 && !needlematch(needle, a, value))
361 this.skip[needle.length - a - 1] = value;
366 Range beFound(Range haystack) scope
368 import std.algorithm.comparison : max;
370 if (!needle.length) return haystack;
371 if (needle.length > haystack.length) return haystack[$ .. $];
373 immutable limit = haystack.length - needle.length;
374 for (size_t hpos = 0; hpos <= limit; )
376 size_t npos = needle.length - 1;
377 while (pred(needle[npos], haystack[npos+hpos]))
379 if (npos == 0) return haystack[hpos .. $];
382 hpos += max(skip[npos], cast(ptrdiff_t) npos - occurrence(haystack[npos+hpos]));
384 return haystack[$ .. $];
388 @property size_t length()
390 return needle.length;
394 alias opDollar = length;
398 BoyerMooreFinder!(binaryFun!(pred), Range) boyerMooreFinder
399 (alias pred = "a == b", Range)
401 if ((isRandomAccessRange!(Range) && hasSlicing!Range) || isSomeString!Range)
403 return typeof(return)(needle);
407 @safe pure nothrow unittest
409 auto bmFinder = boyerMooreFinder("TG");
411 string r = "TAGTGCCTGA";
412 // search for the first match in the haystack r
413 r = bmFinder.beFound(r);
414 assert(r == "TGCCTGA");
416 // continue search in haystack
417 r = bmFinder.beFound(r[2 .. $]);
422 Returns the common prefix of two ranges.
425 pred = The predicate to use in comparing elements for commonality. Defaults
426 to equality `"a == b"`.
428 r1 = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) of
431 r2 = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of
435 A slice of `r1` which contains the characters that both ranges start with,
436 if the first argument is a string; otherwise, the same as the result of
437 `takeExactly(r1, n)`, where `n` is the number of elements in the common
438 prefix of both ranges.
441 $(REF takeExactly, std,range)
443 auto commonPrefix(alias pred = "a == b", R1, R2)(R1 r1, R2 r2)
444 if (isForwardRange!R1 && isInputRange!R2 &&
445 !isNarrowString!R1 &&
446 is(typeof(binaryFun!pred(r1.front, r2.front))))
448 import std.algorithm.comparison : min;
449 static if (isRandomAccessRange!R1 && isRandomAccessRange!R2 &&
450 hasLength!R1 && hasLength!R2 &&
453 immutable limit = min(r1.length, r2.length);
454 foreach (i; 0 .. limit)
456 if (!binaryFun!pred(r1[i], r2[i]))
461 return r1[0 .. limit];
465 import std.range : takeExactly;
466 auto result = r1.save;
469 !r1.empty && !r2.empty && binaryFun!pred(r1.front, r2.front);
470 ++i, r1.popFront(), r2.popFront())
472 return takeExactly(result, i);
479 assert(commonPrefix("hello, world", "hello, there") == "hello, ");
483 auto commonPrefix(alias pred, R1, R2)(R1 r1, R2 r2)
484 if (isNarrowString!R1 && isInputRange!R2 &&
485 is(typeof(binaryFun!pred(r1.front, r2.front))))
487 import std.utf : decode;
489 auto result = r1.save;
490 immutable len = r1.length;
493 for (size_t j = 0; i < len && !r2.empty; r2.popFront(), i = j)
495 immutable f = decode(r1, j);
496 if (!binaryFun!pred(f, r2.front))
500 return result[0 .. i];
504 auto commonPrefix(R1, R2)(R1 r1, R2 r2)
505 if (isNarrowString!R1 && isInputRange!R2 && !isNarrowString!R2 &&
506 is(typeof(r1.front == r2.front)))
508 return commonPrefix!"a == b"(r1, r2);
512 auto commonPrefix(R1, R2)(R1 r1, R2 r2)
513 if (isNarrowString!R1 && isNarrowString!R2)
515 import std.algorithm.comparison : min;
517 static if (ElementEncodingType!R1.sizeof == ElementEncodingType!R2.sizeof)
519 import std.utf : stride, UTFException;
521 immutable limit = min(r1.length, r2.length);
522 for (size_t i = 0; i < limit;)
524 immutable codeLen = stride(r1, i);
527 for (; j < codeLen && i < limit; ++i, ++j)
530 return r1[0 .. i - j];
533 if (i == limit && j < codeLen)
534 throw new UTFException("Invalid UTF-8 sequence", i);
536 return r1[0 .. limit];
539 return commonPrefix!"a == b"(r1, r2);
544 import std.algorithm.comparison : equal;
545 import std.algorithm.iteration : filter;
546 import std.conv : to;
547 import std.exception : assertThrown;
548 import std.meta : AliasSeq;
550 import std.utf : UTFException;
552 assert(commonPrefix([1, 2, 3], [1, 2, 3, 4, 5]) == [1, 2, 3]);
553 assert(commonPrefix([1, 2, 3, 4, 5], [1, 2, 3]) == [1, 2, 3]);
554 assert(commonPrefix([1, 2, 3, 4], [1, 2, 3, 4]) == [1, 2, 3, 4]);
555 assert(commonPrefix([1, 2, 3], [7, 2, 3, 4, 5]).empty);
556 assert(commonPrefix([7, 2, 3, 4, 5], [1, 2, 3]).empty);
557 assert(commonPrefix([1, 2, 3], cast(int[]) null).empty);
558 assert(commonPrefix(cast(int[]) null, [1, 2, 3]).empty);
559 assert(commonPrefix(cast(int[]) null, cast(int[]) null).empty);
561 static foreach (S; AliasSeq!(char[], const(char)[], string,
562 wchar[], const(wchar)[], wstring,
563 dchar[], const(dchar)[], dstring))
565 static foreach (T; AliasSeq!(string, wstring, dstring))
567 assert(commonPrefix(to!S(""), to!T("")).empty);
568 assert(commonPrefix(to!S(""), to!T("hello")).empty);
569 assert(commonPrefix(to!S("hello"), to!T("")).empty);
570 assert(commonPrefix(to!S("hello, world"), to!T("hello, there")) == to!S("hello, "));
571 assert(commonPrefix(to!S("hello, there"), to!T("hello, world")) == to!S("hello, "));
572 assert(commonPrefix(to!S("hello, "), to!T("hello, world")) == to!S("hello, "));
573 assert(commonPrefix(to!S("hello, world"), to!T("hello, ")) == to!S("hello, "));
574 assert(commonPrefix(to!S("hello, world"), to!T("hello, world")) == to!S("hello, world"));
576 // https://issues.dlang.org/show_bug.cgi?id=8890
577 assert(commonPrefix(to!S("Пиво"), to!T("Пони"))== to!S("П"));
578 assert(commonPrefix(to!S("Пони"), to!T("Пиво"))== to!S("П"));
579 assert(commonPrefix(to!S("Пиво"), to!T("Пиво"))== to!S("Пиво"));
580 assert(commonPrefix(to!S("\U0010FFFF\U0010FFFB\U0010FFFE"),
581 to!T("\U0010FFFF\U0010FFFB\U0010FFFC")) == to!S("\U0010FFFF\U0010FFFB"));
582 assert(commonPrefix(to!S("\U0010FFFF\U0010FFFB\U0010FFFC"),
583 to!T("\U0010FFFF\U0010FFFB\U0010FFFE")) == to!S("\U0010FFFF\U0010FFFB"));
584 assert(commonPrefix!"a != b"(to!S("Пиво"), to!T("онво")) == to!S("Пи"));
585 assert(commonPrefix!"a != b"(to!S("онво"), to!T("Пиво")) == to!S("он"));
588 static assert(is(typeof(commonPrefix(to!S("Пиво"), filter!"true"("Пони"))) == S));
589 assert(equal(commonPrefix(to!S("Пиво"), filter!"true"("Пони")), to!S("П")));
591 static assert(is(typeof(commonPrefix(filter!"true"("Пиво"), to!S("Пони"))) ==
592 typeof(takeExactly(filter!"true"("П"), 1))));
593 assert(equal(commonPrefix(filter!"true"("Пиво"), to!S("Пони")), takeExactly(filter!"true"("П"), 1)));
596 assertThrown!UTFException(commonPrefix("\U0010FFFF\U0010FFFB", "\U0010FFFF\U0010FFFB"[0 .. $ - 1]));
598 assert(commonPrefix("12345"d, [49, 50, 51, 60, 60]) == "123"d);
599 assert(commonPrefix([49, 50, 51, 60, 60], "12345" ) == [49, 50, 51]);
600 assert(commonPrefix([49, 50, 51, 60, 60], "12345"d) == [49, 50, 51]);
602 assert(commonPrefix!"a == ('0' + b)"("12345" , [1, 2, 3, 9, 9]) == "123");
603 assert(commonPrefix!"a == ('0' + b)"("12345"d, [1, 2, 3, 9, 9]) == "123"d);
604 assert(commonPrefix!"('0' + a) == b"([1, 2, 3, 9, 9], "12345" ) == [1, 2, 3]);
605 assert(commonPrefix!"('0' + a) == b"([1, 2, 3, 9, 9], "12345"d) == [1, 2, 3]);
610 Counts matches of `needle` in `haystack`.
612 The first overload counts each element `e` in `haystack` for
613 which `pred(e, needle)` is `true`. `pred` defaults to
614 equality. Performs $(BIGOH haystack.length) evaluations of `pred`.
616 The second overload counts the number of times `needle` was matched in
617 `haystack`. `pred` compares elements in each range.
618 Throws an exception if `needle.empty` is `true`, as the _count
619 of the empty range in any range would be infinite. Overlapped counts
620 are *not* considered, for example `count("aaa", "aa")` is `1`, not
623 Note: Regardless of the overload, `count` will not accept
624 infinite ranges for `haystack`.
627 pred = The predicate to compare elements.
628 haystack = The range to _count.
629 needle = The element or sub-range to _count in `haystack`.
632 The number of matches in `haystack`.
634 size_t count(alias pred = "a == b", Range, E)(Range haystack, E needle)
635 if (isInputRange!Range && !isInfinite!Range &&
636 is(typeof(binaryFun!pred(haystack.front, needle))))
638 bool pred2(ElementType!Range a) { return binaryFun!pred(a, needle); }
639 return count!pred2(haystack);
645 // count elements in range
646 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
647 assert(count(a, 2) == 3);
648 assert(count!("a > b")(a, 2) == 5);
654 import std.uni : toLower;
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);
665 import std.conv : text;
667 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
668 assert(count(a, 2) == 3, text(count(a, 2)));
669 assert(count!("a > b")(a, 2) == 5, text(count!("a > b")(a, 2)));
672 assert(count("日本語") == 3);
673 assert(count("日本語"w) == 3);
674 assert(count("日本語"d) == 3);
676 assert(count!("a == '日'")("日本語") == 1);
677 assert(count!("a == '本'")("日本語"w) == 1);
678 assert(count!("a == '語'")("日本語"d) == 1);
683 string s = "This is a fofofof list";
685 assert(count(s, sub) == 2);
689 size_t count(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
690 if (isForwardRange!R1 && !isInfinite!R1 &&
692 is(typeof(binaryFun!pred(haystack.front, needle.front))))
694 assert(!needle.empty, "Cannot count occurrences of an empty range");
696 static if (isInfinite!R2)
698 //Note: This is the special case of looking for an infinite inside a finite...
699 //"How many instances of the Fibonacci sequence can you count in [1, 2, 3]?" - "None."
705 //Note: haystack is not saved, because findskip is designed to modify it
706 for ( ; findSkip!pred(haystack, needle.save) ; ++result)
713 Counts all elements or elements satisfying a predicate in `haystack`.
715 The first overload counts each element `e` in `haystack` for which `pred(e)` is $(D
716 true). Performs $(BIGOH haystack.length) evaluations of `pred`.
718 The second overload counts the number of elements in a range.
719 If the given range has the `length` property,
720 that is returned right away, otherwise
721 performs $(BIGOH haystack.length) to walk the range.
724 pred = Optional predicate to find elements.
725 haystack = The range to _count.
728 The number of elements in `haystack` (for which `pred` returned true).
730 size_t count(alias pred, R)(R haystack)
731 if (isInputRange!R && !isInfinite!R &&
732 is(typeof(unaryFun!pred(haystack.front))))
735 alias T = ElementType!R; //For narrow strings forces dchar iteration
736 foreach (T elem; haystack)
737 if (unaryFun!pred(elem)) ++result;
744 // count elements in range
745 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
746 assert(count(a) == 9);
747 // count predicate in range
748 assert(count!("a > 2")(a) == 5);
752 size_t count(R)(R haystack)
753 if (isInputRange!R && !isInfinite!R)
755 return walkLength(haystack);
760 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
761 assert(count!("a == 3")(a) == 2);
762 assert(count("日本語") == 3);
765 // https://issues.dlang.org/show_bug.cgi?id=11253
766 @safe nothrow unittest
768 assert([1, 2, 3].count([2, 3]) == 1);
771 // https://issues.dlang.org/show_bug.cgi?id=22582
774 assert([1, 2, 3].count!"a & 1" == 2);
778 Counts elements in the given
779 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
780 until the given predicate is true for one of the given `needles`.
783 pred = The predicate for determining when to stop counting.
785 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be
787 needles = Either a single element, or a
788 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
789 of elements, to be evaluated in turn against each
790 element in `haystack` under the given predicate.
792 Returns: The number of elements which must be popped from the front of
793 `haystack` before reaching an element for which
794 `startsWith!pred(haystack, needles)` is `true`. If
795 `startsWith!pred(haystack, needles)` is not `true` for any element in
796 `haystack`, then `-1` is returned. If more than one needle is provided,
797 `countUntil` will wrap the result in a tuple similar to
798 `Tuple!(ptrdiff_t, "steps", ptrdiff_t needle)`
800 See_Also: $(REF indexOf, std,string)
802 auto countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles)
805 && isForwardRange!(Rs[0]) == isInputRange!(Rs[0])
806 && allSatisfy!(canTestStartsWith!(pred, R), Rs))
808 static if (needles.length == 1)
810 static if (hasLength!R) //Note: Narrow strings don't have length.
812 //We delegate to find because find is very efficient.
813 //We store the length of the haystack so we don't have to save it.
814 auto len = haystack.length;
815 auto r2 = find!pred(haystack, needles[0]);
817 return ptrdiff_t(len - r2.length);
821 import std.range : dropOne;
823 if (needles[0].empty)
828 //Default case, slower route doing startsWith iteration
829 for ( ; !haystack.empty ; ++result )
831 //We compare the first elements of the ranges here before
832 //forwarding to startsWith. This avoids making useless saves to
833 //haystack/needle if they aren't even going to be mutated anyways.
834 //It also cuts down on the amount of pops on haystack.
835 if (binaryFun!pred(haystack.front, needles[0].front))
837 //Here, we need to save the needle before popping it.
838 //haystack we pop in all paths, so we do that, and then save.
840 if (startsWith!pred(haystack.save, needles[0].save.dropOne()))
849 return ptrdiff_t(-1);
855 ptrdiff_t steps, needle; // both -1 when nothing was found
856 alias steps this; // compatible with previous ptrdiff_t return type
857 ptrdiff_t opIndex(size_t idx) // faking a tuple
859 assert(idx < 2, "Type has only two members: pos and needle");
860 return idx == 0 ? steps : needle;
867 static if (isForwardRange!Ri)
869 if (needles[i].empty)
879 static if (!isForwardRange!Ri)
884 for (; !haystack.empty ; ++result.steps, haystack.popFront())
888 static if (isForwardRange!Ri)
890 t[i] = needles[i].save;
893 if (auto needle = startsWith!pred(haystack.save, t.expand))
895 result.needle = needle - 1;
900 // no match was found
908 ptrdiff_t countUntil(alias pred = "a == b", R, N)(R haystack, N needle)
909 if (isInputRange!R &&
910 is(typeof(binaryFun!pred(haystack.front, needle)) : bool))
912 bool pred2(ElementType!R a) { return binaryFun!pred(a, needle); }
913 return countUntil!pred2(haystack);
919 assert(countUntil("hello world", "world") == 6);
920 assert(countUntil("hello world", 'r') == 8);
921 assert(countUntil("hello world", "programming") == -1);
922 assert(countUntil("日本語", "本語") == 1);
923 assert(countUntil("日本語", '語') == 2);
924 assert(countUntil("日本語", "五") == -1);
925 assert(countUntil("日本語", '五') == -1);
926 assert(countUntil([0, 7, 12, 22, 9], [12, 22]) == 2);
927 assert(countUntil([0, 7, 12, 22, 9], 9) == 4);
928 assert(countUntil!"a > b"([0, 7, 12, 22, 9], 20) == 3);
930 // supports multiple needles
931 auto res = "...hello".countUntil("ha", "he");
932 assert(res.steps == 3);
933 assert(res.needle == 1);
935 // returns -1 if no needle was found
936 res = "hello".countUntil("ha", "hu");
937 assert(res.steps == -1);
938 assert(res.needle == -1);
943 import std.algorithm.iteration : filter;
944 import std.internal.test.dummyrange;
946 assert(countUntil("日本語", "") == 0);
947 assert(countUntil("日本語"d, "") == 0);
949 assert(countUntil("", "") == 0);
950 assert(countUntil("".filter!"true"(), "") == 0);
952 auto rf = [0, 20, 12, 22, 9].filter!"true"();
953 assert(rf.countUntil!"a > b"((int[]).init) == 0);
954 assert(rf.countUntil!"a > b"(20) == 3);
955 assert(rf.countUntil!"a > b"([20, 8]) == 3);
956 assert(rf.countUntil!"a > b"([20, 10]) == -1);
957 assert(rf.countUntil!"a > b"([20, 8, 0]) == -1);
959 auto r = new ReferenceForwardRange!int([0, 1, 2, 3, 4, 5, 6]);
960 auto r2 = new ReferenceForwardRange!int([3, 4]);
961 auto r3 = new ReferenceForwardRange!int([3, 5]);
962 assert(r.save.countUntil(3) == 3);
963 assert(r.save.countUntil(r2) == 3);
964 assert(r.save.countUntil(7) == -1);
965 assert(r.save.countUntil(r3) == -1);
970 assert(countUntil("hello world", "world", "asd") == 6);
971 assert(countUntil("hello world", "world", "ello") == 1);
972 assert(countUntil("hello world", "world", "") == 0);
973 assert(countUntil("hello world", "world", 'l') == 2);
978 auto res = "...hello".countUntil("hella", "hello");
980 assert(res.steps == 3);
981 assert(res.needle == 1);
982 // test tuple emulation
986 // the first matching needle is chosen
987 res = "...hello".countUntil("hell", "hello");
989 assert(res.needle == 0);
992 auto noMatch = "hello world".countUntil("ha", "hu");
993 assert(noMatch == -1);
994 assert(noMatch.steps == -1);
995 assert(noMatch.needle == -1);
996 // test tuple emulation
997 assert(noMatch[0] == -1);
998 assert(noMatch[1] == -1);
1001 // test infinite ranges
1004 import std.algorithm.iteration : joiner;
1005 import std.range : iota, repeat;
1007 assert(10.iota.repeat.joiner.countUntil(9) == 9);
1008 assert(10.iota.repeat.joiner.countUntil(1, 2) == 1);
1009 assert(10.iota.repeat.joiner.countUntil!(a => a >= 9) == 9);
1013 ptrdiff_t countUntil(alias pred, R)(R haystack)
1014 if (isInputRange!R &&
1015 is(typeof(unaryFun!pred(haystack.front)) : bool))
1018 static if (isRandomAccessRange!R)
1020 //Optimized RA implementation. Since we want to count *and* iterate at
1021 //the same time, it is more efficient this way.
1022 static if (hasLength!R)
1024 immutable len = cast(typeof(return)) haystack.length;
1025 for ( ; i < len ; ++i )
1026 if (unaryFun!pred(haystack[i])) return i;
1028 else //if (isInfinite!R)
1031 if (unaryFun!pred(haystack[i])) return i;
1034 else static if (hasLength!R)
1036 //For those odd ranges that have a length, but aren't RA.
1037 //It is faster to quick find, and then compare the lengths
1038 auto r2 = find!pred(haystack.save);
1039 if (!r2.empty) return cast(typeof(return)) (haystack.length - r2.length);
1041 else //Everything else
1043 alias T = ElementType!R; //For narrow strings forces dchar iteration
1044 foreach (T elem; haystack)
1046 if (unaryFun!pred(elem)) return i;
1051 // Because of https://issues.dlang.org/show_bug.cgi?id=8804
1052 // Avoids both "unreachable code" or "no return statement"
1053 static if (isInfinite!R) assert(false, R.stringof ~ " must not be an"
1054 ~ " inifite range");
1061 import std.ascii : isDigit;
1062 import std.uni : isWhite;
1064 assert(countUntil!(isWhite)("hello world") == 5);
1065 assert(countUntil!(isDigit)("hello world") == -1);
1066 assert(countUntil!"a > 20"([0, 7, 12, 22, 9]) == 3);
1071 import std.internal.test.dummyrange;
1076 ReferenceInputRange!int r;
1077 r = new ReferenceInputRange!int([0, 1, 2, 3, 4, 5, 6]);
1078 assert(r.countUntil(3) == 3);
1079 r = new ReferenceInputRange!int([0, 1, 2, 3, 4, 5, 6]);
1080 assert(r.countUntil(7) == -1);
1084 auto r = new ReferenceForwardRange!int([0, 1, 2, 3, 4, 5, 6]);
1085 assert(r.save.countUntil([3, 4]) == 3);
1086 assert(r.save.countUntil(3) == 3);
1087 assert(r.save.countUntil([3, 7]) == -1);
1088 assert(r.save.countUntil(7) == -1);
1092 auto r = new ReferenceInfiniteForwardRange!int(0);
1093 assert(r.save.countUntil([3, 4]) == 3);
1094 assert(r.save.countUntil(3) == 3);
1099 Checks if the given range ends with (one of) the given needle(s).
1100 The reciprocal of `startsWith`.
1103 pred = The predicate to use for comparing elements between the range and
1107 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
1110 withOneOfThese = The needles to check against, which may be single
1111 elements, or bidirectional ranges of elements.
1113 withThis = The single element to check.
1116 0 if the needle(s) do not occur at the end of the given range;
1117 otherwise the position of the matching needle, that is, 1 if the range ends
1118 with `withOneOfThese[0]`, 2 if it ends with `withOneOfThese[1]`, and so
1121 In the case when no needle parameters are given, return `true` iff back of
1122 `doesThisStart` fulfils predicate `pred`.
1124 uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese)
1125 if (isBidirectionalRange!Range && Needles.length > 1 &&
1126 allSatisfy!(canTestStartsWith!(pred, Range), Needles))
1128 alias haystack = doesThisEnd;
1129 alias needles = withOneOfThese;
1131 // Make one pass looking for empty ranges in needles
1132 foreach (i, Unused; Needles)
1134 // Empty range matches everything
1135 static if (!is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool))
1137 if (needles[i].empty) return i + 1;
1141 for (; !haystack.empty; haystack.popBack())
1143 foreach (i, Unused; Needles)
1145 static if (is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool))
1148 if (binaryFun!pred(haystack.back, needles[i]))
1150 // found, but continue to account for one-element
1151 // range matches (consider endsWith("ab", "b",
1152 // 'b') should return 1, not 2).
1158 if (binaryFun!pred(haystack.back, needles[i].back))
1162 // This code executed on failure to match
1163 // Out with this guy, check for the others
1164 uint result = endsWith!pred(haystack, needles[0 .. i], needles[i + 1 .. $]);
1165 if (result > i) ++result;
1169 // If execution reaches this point, then the back matches for all
1170 // needles ranges. What we need to do now is to lop off the back of
1171 // all ranges involved and recurse.
1172 foreach (i, Unused; Needles)
1174 static if (is(typeof(binaryFun!pred(haystack.back, needles[i])) : bool))
1176 // Test has passed in the previous loop
1181 needles[i].popBack();
1182 if (needles[i].empty) return i + 1;
1190 bool endsWith(alias pred = "a == b", R1, R2)(R1 doesThisEnd, R2 withThis)
1191 if (isBidirectionalRange!R1 &&
1192 isBidirectionalRange!R2 &&
1193 is(typeof(binaryFun!pred(doesThisEnd.back, withThis.back)) : bool))
1195 alias haystack = doesThisEnd;
1196 alias needle = withThis;
1198 static if (is(typeof(pred) : string))
1199 enum isDefaultPred = pred == "a == b";
1201 enum isDefaultPred = false;
1203 static if (isDefaultPred && isArray!R1 && isArray!R2 &&
1204 is(immutable ElementEncodingType!R1 == immutable ElementEncodingType!R2))
1206 if (haystack.length < needle.length) return false;
1208 return haystack[$ - needle.length .. $] == needle;
1212 import std.range : retro;
1213 return startsWith!pred(retro(doesThisEnd), retro(withThis));
1218 bool endsWith(alias pred = "a == b", R, E)(R doesThisEnd, E withThis)
1219 if (isBidirectionalRange!R &&
1220 is(typeof(binaryFun!pred(doesThisEnd.back, withThis)) : bool))
1222 if (doesThisEnd.empty)
1225 static if (is(typeof(pred) : string))
1226 enum isDefaultPred = pred == "a == b";
1228 enum isDefaultPred = false;
1230 alias predFunc = binaryFun!pred;
1232 // auto-decoding special case
1233 static if (isNarrowString!R)
1235 // statically determine decoding is unnecessary to evaluate pred
1236 static if (isDefaultPred && isSomeChar!E && E.sizeof <= ElementEncodingType!R.sizeof)
1237 return doesThisEnd[$ - 1] == withThis;
1238 // specialize for ASCII as to not change previous behavior
1241 if (withThis <= 0x7F)
1242 return predFunc(doesThisEnd[$ - 1], withThis);
1244 return predFunc(doesThisEnd.back, withThis);
1249 return predFunc(doesThisEnd.back, withThis);
1254 bool endsWith(alias pred, R)(R doesThisEnd)
1255 if (isInputRange!R &&
1256 ifTestable!(typeof(doesThisEnd.front), unaryFun!pred))
1258 return !doesThisEnd.empty && unaryFun!pred(doesThisEnd.back);
1264 import std.ascii : isAlpha;
1265 assert("abc".endsWith!(a => a.isAlpha));
1266 assert("abc".endsWith!isAlpha);
1268 assert(!"ab1".endsWith!(a => a.isAlpha));
1270 assert(!"ab1".endsWith!isAlpha);
1271 assert(!"".endsWith!(a => a.isAlpha));
1273 import std.algorithm.comparison : among;
1274 assert("abc".endsWith!(a => a.among('c', 'd') != 0));
1275 assert(!"abc".endsWith!(a => a.among('a', 'b') != 0));
1277 assert(endsWith("abc", ""));
1278 assert(!endsWith("abc", "b"));
1279 assert(endsWith("abc", "a", 'c') == 2);
1280 assert(endsWith("abc", "c", "a") == 1);
1281 assert(endsWith("abc", "c", "c") == 1);
1282 assert(endsWith("abc", "bc", "c") == 2);
1283 assert(endsWith("abc", "x", "c", "b") == 2);
1284 assert(endsWith("abc", "x", "aa", "bc") == 3);
1285 assert(endsWith("abc", "x", "aaa", "sab") == 0);
1286 assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);
1291 import std.algorithm.iteration : filterBidirectional;
1292 import std.conv : to;
1293 import std.meta : AliasSeq;
1295 static foreach (S; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
1296 (){ // workaround slow optimizations for large functions
1297 // https://issues.dlang.org/show_bug.cgi?id=2396
1298 assert(!endsWith(to!S("abc"), 'a'));
1299 assert(endsWith(to!S("abc"), 'a', 'c') == 2);
1300 assert(!endsWith(to!S("abc"), 'x', 'n', 'b'));
1301 assert(endsWith(to!S("abc"), 'x', 'n', 'c') == 3);
1302 assert(endsWith(to!S("abc\uFF28"), 'a', '\uFF28', 'c') == 2);
1304 static foreach (T; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
1307 assert(endsWith(to!S("abc"), to!T("")));
1308 assert(!endsWith(to!S("abc"), to!T("a")));
1309 assert(!endsWith(to!S("abc"), to!T("b")));
1310 assert(endsWith(to!S("abc"), to!T("bc"), 'c') == 2);
1311 assert(endsWith(to!S("abc"), to!T("a"), "c") == 2);
1312 assert(endsWith(to!S("abc"), to!T("c"), "a") == 1);
1313 assert(endsWith(to!S("abc"), to!T("c"), "c") == 1);
1314 assert(endsWith(to!S("abc"), to!T("x"), 'c', "b") == 2);
1315 assert(endsWith(to!S("abc"), 'x', to!T("aa"), "bc") == 3);
1316 assert(endsWith(to!S("abc"), to!T("x"), "aaa", "sab") == 0);
1317 assert(endsWith(to!S("abc"), to!T("x"), "aaa", "c", "sab") == 3);
1318 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("l\uFF4co")));
1319 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("lo"), to!T("l\uFF4co")) == 2);
1322 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("l\uFF4co")));
1323 assert(endsWith(to!S("\uFF28el\uFF4co"), to!T("lo"), to!T("l\uFF4co")) == 2);
1324 assert(endsWith(to!S("日本語"), to!T("本語")));
1325 assert(endsWith(to!S("日本語"), to!T("日本語")));
1326 assert(!endsWith(to!S("本語"), to!T("日本語")));
1329 assert(endsWith(to!S(""), T.init));
1330 assert(!endsWith(to!S(""), 'a'));
1331 assert(endsWith(to!S("a"), T.init));
1332 assert(endsWith(to!S("a"), T.init, "") == 1);
1333 assert(endsWith(to!S("a"), T.init, 'a') == 1);
1334 assert(endsWith(to!S("a"), 'a', T.init) == 2);
1338 static foreach (T; AliasSeq!(int, short))
1340 immutable arr = cast(T[])[0, 1, 2, 3, 4, 5];
1343 assert(endsWith(arr, cast(int[]) null));
1344 assert(!endsWith(arr, 0));
1345 assert(!endsWith(arr, 4));
1346 assert(endsWith(arr, 5));
1347 assert(endsWith(arr, 0, 4, 5) == 3);
1348 assert(endsWith(arr, [5]));
1349 assert(endsWith(arr, [4, 5]));
1350 assert(endsWith(arr, [4, 5], 7) == 1);
1351 assert(!endsWith(arr, [2, 4, 5]));
1352 assert(endsWith(arr, [2, 4, 5], [3, 4, 5]) == 2);
1354 //Normal input range
1355 assert(!endsWith(filterBidirectional!"true"(arr), 4));
1356 assert(endsWith(filterBidirectional!"true"(arr), 5));
1357 assert(endsWith(filterBidirectional!"true"(arr), [5]));
1358 assert(endsWith(filterBidirectional!"true"(arr), [4, 5]));
1359 assert(endsWith(filterBidirectional!"true"(arr), [4, 5], 7) == 1);
1360 assert(!endsWith(filterBidirectional!"true"(arr), [2, 4, 5]));
1361 assert(endsWith(filterBidirectional!"true"(arr), [2, 4, 5], [3, 4, 5]) == 2);
1362 assert(endsWith(arr, filterBidirectional!"true"([4, 5])));
1363 assert(endsWith(arr, filterBidirectional!"true"([4, 5]), 7) == 1);
1364 assert(!endsWith(arr, filterBidirectional!"true"([2, 4, 5])));
1365 assert(endsWith(arr, [2, 4, 5], filterBidirectional!"true"([3, 4, 5])) == 2);
1368 assert(endsWith!("a%10 == b%10")(arr, [14, 15]));
1369 assert(!endsWith!("a%10 == b%10")(arr, [15, 14]));
1375 //example from https://issues.dlang.org/show_bug.cgi?id=19727
1376 import std.path : asRelativePath;
1377 string[] ext = ["abc", "def", "ghi"];
1378 string path = "/foo/file.def";
1379 assert(ext.any!(e => path.asRelativePath("/foo").endsWith(e)) == true);
1380 assert(ext.any!(e => path.asRelativePath("/foo").startsWith(e)) == false);
1383 private enum bool hasConstEmptyMember(T) = is(typeof(((const T* a) => (*a).empty)(null)) : bool);
1386 Iterates the passed range and selects the extreme element with `less`.
1387 If the extreme element occurs multiple time, the first occurrence will be
1391 map = custom accessor for the comparison key
1392 selector = custom mapping for the extrema selection
1393 r = Range from which the extreme value will be selected
1394 seedElement = custom seed to use as initial element
1397 The extreme value according to `map` and `selector` of the passed-in values.
1399 private auto extremum(alias map, alias selector = "a < b", Range)(Range r)
1400 if (isInputRange!Range && !isInfinite!Range &&
1401 is(typeof(unaryFun!map(ElementType!(Range).init))))
1404 assert(!r.empty, "r is an empty range");
1408 import std.typecons : Rebindable2;
1410 alias Element = ElementType!Range;
1411 auto seed = Rebindable2!Element(r.front);
1413 return extremum!(map, selector)(r, seed.get);
1416 private auto extremum(alias map, alias selector = "a < b", Range,
1417 RangeElementType = ElementType!Range)
1418 (Range r, RangeElementType seedElement)
1419 if (isInputRange!Range && !isInfinite!Range &&
1420 !is(CommonType!(ElementType!Range, RangeElementType) == void) &&
1421 is(typeof(unaryFun!map(ElementType!(Range).init))))
1423 import std.typecons : Rebindable2;
1425 alias mapFun = unaryFun!map;
1426 alias selectorFun = binaryFun!selector;
1428 alias Element = ElementType!Range;
1429 alias CommonElement = CommonType!(Element, RangeElementType);
1430 auto extremeElement = Rebindable2!CommonElement(seedElement);
1432 // if we only have one statement in the loop, it can be optimized a lot better
1433 static if (__traits(isSame, map, a => a))
1435 // direct access via a random access range is faster
1436 static if (isRandomAccessRange!Range)
1438 foreach (const i; 0 .. r.length)
1440 if (selectorFun(r[i], extremeElement.get))
1442 extremeElement = r[i];
1450 if (selectorFun(r.front, extremeElement.get))
1452 extremeElement = r.front;
1460 alias MapType = Unqual!(typeof(mapFun(CommonElement.init)));
1461 MapType extremeElementMapped = mapFun(extremeElement.get);
1463 // direct access via a random access range is faster
1464 static if (isRandomAccessRange!Range)
1466 foreach (const i; 0 .. r.length)
1468 MapType mapElement = mapFun(r[i]);
1469 if (selectorFun(mapElement, extremeElementMapped))
1471 extremeElement = r[i];
1472 extremeElementMapped = mapElement;
1480 MapType mapElement = mapFun(r.front);
1481 if (selectorFun(mapElement, extremeElementMapped))
1483 extremeElement = r.front;
1484 extremeElementMapped = mapElement;
1490 return extremeElement.get;
1493 private auto extremum(alias selector = "a < b", Range)(Range r)
1494 if (isInputRange!Range && !isInfinite!Range &&
1495 !is(typeof(unaryFun!selector(ElementType!(Range).init))))
1497 return extremum!(a => a, selector)(r);
1500 // if we only have one statement in the loop it can be optimized a lot better
1501 private auto extremum(alias selector = "a < b", Range,
1502 RangeElementType = ElementType!Range)
1503 (Range r, RangeElementType seedElement)
1504 if (isInputRange!Range && !isInfinite!Range &&
1505 !is(CommonType!(ElementType!Range, RangeElementType) == void) &&
1506 !is(typeof(unaryFun!selector(ElementType!(Range).init))))
1508 return extremum!(a => a, selector)(r, seedElement);
1513 // allows a custom map to select the extremum
1514 assert([[0, 4], [1, 2]].extremum!"a[0]" == [0, 4]);
1515 assert([[0, 4], [1, 2]].extremum!"a[1]" == [1, 2]);
1517 // allows a custom selector for comparison
1518 assert([[0, 4], [1, 2]].extremum!("a[0]", "a > b") == [1, 2]);
1519 assert([[0, 4], [1, 2]].extremum!("a[1]", "a > b") == [0, 4]);
1521 // use a custom comparator
1522 import std.math.operations : cmp;
1523 assert([-2., 0, 5].extremum!cmp == 5.0);
1524 assert([-2., 0, 2].extremum!`cmp(a, b) < 0` == -2.0);
1527 import std.range : enumerate;
1528 assert([-3., 0, 5].enumerate.extremum!(`a.value`, cmp) == tuple(2, 5.0));
1529 assert([-2., 0, 2].enumerate.extremum!(`a.value`, `cmp(a, b) < 0`) == tuple(0, -2.0));
1531 // seed with a custom value
1533 assert(arr.extremum(1) == 1);
1536 @safe pure nothrow unittest
1540 assert(arr2d.extremum([1]) == [1]);
1542 // allow seeds of different types (implicit casting)
1543 assert(extremum([2, 3, 4], 1.5) == 1.5);
1548 import std.range : enumerate, iota;
1551 assert(iota(1, 5).extremum() == 1);
1552 assert(iota(2, 5).enumerate.extremum!"a.value" == tuple(0, 2));
1554 // should work with const
1555 const(int)[] immArr = [2, 1, 3];
1556 assert(immArr.extremum == 1);
1558 // should work with immutable
1559 immutable(int)[] immArr2 = [2, 1, 3];
1560 assert(immArr2.extremum == 1);
1563 assert(["b", "a", "c"].extremum == "a");
1565 // with all dummy ranges
1566 import std.internal.test.dummyrange;
1567 foreach (DummyType; AllDummyRanges)
1570 assert(d.extremum == 1);
1571 assert(d.extremum!(a => a) == 1);
1572 assert(d.extremum!`a > b` == 10);
1573 assert(d.extremum!(a => a, `a > b`) == 10);
1577 enum ctExtremum = iota(1, 5).extremum;
1578 assert(ctExtremum == 1);
1581 @nogc @safe nothrow pure unittest
1583 static immutable arr = [7, 3, 4, 2, 1, 8];
1584 assert(arr.extremum == 1);
1586 static immutable arr2d = [[1, 9], [3, 1], [4, 2]];
1587 assert(arr2d.extremum!"a[1]" == arr2d[1]);
1590 // https://issues.dlang.org/show_bug.cgi?id=17982
1596 this(int val){ this.val = val; }
1599 const(B) doStuff(const(B)[] v)
1601 return v.extremum!"a.val";
1603 assert(doStuff([new B(1), new B(0), new B(2)]).val == 0);
1605 const(B)[] arr = [new B(0), new B(1)];
1606 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
1607 assert(arr.extremum!"a.val".val == 0);
1610 // https://issues.dlang.org/show_bug.cgi?id=22786
1611 @nogc @safe nothrow pure unittest
1615 immutable int value;
1618 assert([S(5), S(6)].extremum!"a.value" == S(5));
1621 // https://issues.dlang.org/show_bug.cgi?id=24027
1622 @safe nothrow unittest
1633 auto test = new A(5);
1635 assert(maxElement!"a.a"(arr) is test);
1640 Finds an element `e` of an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1641 where `pred(e)` is `true`.
1645 $(LI `find` behaves similarly to `dropWhile` in other languages.)
1646 $(LI To _find the *last* matching element in a
1647 $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives) `haystack`,
1648 call `find!pred(retro(haystack))`. See $(REF retro, std,range).)
1652 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`.
1656 pred = The predicate to match an element.
1657 haystack = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1661 `haystack` advanced such that the front element satisfies `pred`.
1662 If no such element exists, returns an empty `haystack`.
1664 InputRange find(alias pred, InputRange)(InputRange haystack)
1665 if (isInputRange!InputRange)
1667 alias R = InputRange;
1668 alias predFun = unaryFun!pred;
1669 static if (isNarrowString!R)
1671 import std.utf : decode;
1673 immutable len = haystack.length;
1674 size_t i = 0, next = 0;
1677 if (predFun(decode(haystack, next)))
1678 return haystack[i .. $];
1681 return haystack[$ .. $];
1686 for ( ; !haystack.empty; haystack.popFront() )
1688 if (predFun(haystack.front))
1698 auto arr = [ 1, 2, 3, 4, 1 ];
1699 assert(find!("a > 2")(arr) == [ 3, 4, 1 ]);
1701 // with predicate alias
1702 bool pred(int e) => e + 1 > 1.5;
1703 assert(find!(pred)(arr) == arr);
1708 int[] r = [ 1, 2, 3 ];
1709 assert(find!(a=>a > 2)(r) == [3]);
1710 bool pred(int x) { return x + 1 > 1.5; }
1711 assert(find!(pred)(r) == r);
1713 assert(find!(a=>a > 'v')("hello world") == "world");
1714 assert(find!(a=>a%4 == 0)("日本語") == "本語");
1718 Finds an individual element in an $(REF_ALTTEXT input range, isInputRange, std,range,primitives).
1719 Elements of `haystack` are compared with `needle` by using predicate
1720 `pred` with `pred(haystack.front, needle)`.
1721 The predicate is passed to $(REF binaryFun, std, functional), and can either accept a
1722 string, or any callable that can be executed via `pred(element, element)`.
1724 If `haystack` is a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives),
1725 `needle` can be a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) too.
1726 In this case `startsWith!pred(haystack, needle)` is evaluated on each evaluation.
1728 $(NOTE To find the first element $(I not) matching the needle, use predicate `"a != b"`.)
1731 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`.
1732 There are specializations that improve performance by taking
1733 advantage of $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives)
1734 or $(REF_ALTTEXT random access, isRandomAccessRange, std,range,primitives)
1735 ranges (where possible).
1739 pred = The predicate for comparing each element with the needle, defaulting to equality `"a == b"`.
1740 haystack = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1742 needle = The element searched for.
1745 `haystack` advanced such that the front element is the one searched for;
1746 that is, until `binaryFun!pred(haystack.front, needle)` is `true`. If no
1747 such position exists, returns an empty `haystack`.
1749 See_Also: $(LREF findAdjacent), $(LREF findAmong), $(LREF findSkip), $(LREF findSplit), $(LREF startsWith)
1751 InputRange find(alias pred = "a == b", InputRange, Element)(InputRange haystack, scope Element needle)
1752 if (isInputRange!InputRange &&
1753 is (typeof(binaryFun!pred(haystack.front, needle)) : bool) &&
1754 !is (typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
1756 alias R = InputRange;
1758 alias predFun = binaryFun!pred;
1759 static if (is(typeof(pred == "a == b")))
1760 enum isDefaultPred = pred == "a == b";
1762 enum isDefaultPred = false;
1763 enum isIntegralNeedle = isSomeChar!E || isIntegral!E || isBoolean!E;
1765 alias EType = ElementType!R;
1767 // If the haystack is a SortedRange we can use binary search to find the needle.
1768 // Works only for the default find predicate and any SortedRange predicate.
1769 // https://issues.dlang.org/show_bug.cgi?id=8829
1770 import std.range : SortedRange;
1771 static if (is(InputRange : SortedRange!TT, TT) && isDefaultPred)
1773 auto lb = haystack.lowerBound(needle);
1774 if (lb.length == haystack.length || haystack[lb.length] != needle)
1775 return haystack[$ .. $];
1777 return haystack[lb.length .. $];
1779 else static if (isNarrowString!R)
1781 alias EEType = ElementEncodingType!R;
1782 alias UEEType = Unqual!EEType;
1784 //These are two special cases which can search without decoding the UTF stream.
1785 static if (isDefaultPred && isIntegralNeedle)
1787 import std.utf : canSearchInCodeUnits;
1789 //This special case deals with UTF8 search, when the needle
1790 //is represented by a single code point.
1791 //Note: "needle <= 0x7F" properly handles sign via unsigned promotion
1792 static if (is(UEEType == char))
1794 if (!__ctfe && canSearchInCodeUnits!char(needle))
1796 static inout(R) trustedMemchr(ref return scope inout(R) haystack,
1797 ref const scope E needle) @trusted nothrow pure
1799 import core.stdc.string : memchr;
1800 auto ptr = memchr(haystack.ptr, needle, haystack.length);
1802 haystack[cast(char*) ptr - haystack.ptr .. $] :
1805 return trustedMemchr(haystack, needle);
1809 //Ditto, but for UTF16
1810 static if (is(UEEType == wchar))
1812 if (canSearchInCodeUnits!wchar(needle))
1814 foreach (i, ref EEType e; haystack)
1817 return haystack[i .. $];
1819 return haystack[$ .. $];
1824 //Previous conditional optimizations did not succeed. Fallback to
1825 //unconditional implementations
1826 static if (isDefaultPred)
1828 import std.utf : encode;
1830 //In case of default pred, it is faster to do string/string search.
1831 UEEType[is(UEEType == char) ? 4 : 2] buf;
1833 size_t len = encode(buf, needle);
1834 return find(haystack, buf[0 .. len]);
1838 import std.utf : decode;
1840 //Explicit pred: we must test each character by the book.
1841 //We choose a manual decoding approach, because it is faster than
1842 //the built-in foreach, or doing a front/popFront for-loop.
1843 immutable len = haystack.length;
1844 size_t i = 0, next = 0;
1847 if (predFun(decode(haystack, next), needle))
1848 return haystack[i .. $];
1851 return haystack[$ .. $];
1854 else static if (isArray!R)
1856 // https://issues.dlang.org/show_bug.cgi?id=10403 optimization
1857 static if (isDefaultPred && isIntegral!EType && EType.sizeof == 1 && isIntegralNeedle)
1859 import std.algorithm.comparison : max, min;
1861 R findHelper(return scope ref R haystack, ref E needle) @trusted nothrow pure
1863 import core.stdc.string : memchr;
1866 //Note: we use "min/max" to handle sign mismatch.
1867 if (min(EType.min, needle) == EType.min &&
1868 max(EType.max, needle) == EType.max)
1870 ptr = cast(EType*) memchr(haystack.ptr, needle,
1875 haystack[ptr - haystack.ptr .. $] :
1880 return findHelper(haystack, needle);
1883 //Default implementation.
1884 foreach (i, ref e; haystack)
1885 if (predFun(e, needle))
1886 return haystack[i .. $];
1887 return haystack[$ .. $];
1891 //Everything else. Walk.
1892 for ( ; !haystack.empty; haystack.popFront() )
1894 if (predFun(haystack.front, needle))
1904 import std.range.primitives;
1906 auto arr = [1, 2, 4, 4, 4, 4, 5, 6, 9];
1907 assert(arr.find(4) == [4, 4, 4, 4, 5, 6, 9]);
1908 assert(arr.find(1) == arr);
1909 assert(arr.find(9) == [9]);
1910 assert(arr.find!((e, n) => e > n)(4) == [5, 6, 9]);
1911 assert(arr.find!((e, n) => e < n)(4) == arr);
1912 assert(arr.find(0).empty);
1913 assert(arr.find(10).empty);
1914 assert(arr.find(8).empty);
1916 assert(find("hello, world", ',') == ", world");
1919 /// Case-insensitive find of a string
1922 import std.range.primitives;
1923 import std.uni : toLower;
1925 string[] s = ["Hello", "world", "!"];
1926 assert(s.find!((e, n) => toLower(e) == n)("hello") == s);
1931 import std.algorithm.comparison : equal;
1932 import std.container : SList;
1934 auto lst = SList!int(1, 2, 5, 7, 3);
1935 assert(lst.front == 1);
1936 auto r = find(lst[], 5);
1937 assert(equal(r, SList!int(5, 7, 3)[]));
1938 assert(find([1, 2, 3, 5], 4).empty);
1939 assert(equal(find!"a > b"("hello", 'k'), "llo"));
1942 @safe pure nothrow unittest
1944 assert(!find ([1, 2, 3], 2).empty);
1945 assert(!find!((a,b)=>a == b)([1, 2, 3], 2).empty);
1946 assert(!find ([1, 2, 3], 2).empty);
1947 assert(!find!((a,b)=>a == b)([1, 2, 3], 2).empty);
1952 import std.meta : AliasSeq;
1953 static foreach (R; AliasSeq!(string, wstring, dstring))
1955 static foreach (E; AliasSeq!(char, wchar, dchar))
1957 assert(find ("hello world", 'w') == "world");
1958 assert(find!((a,b)=>a == b)("hello world", 'w') == "world");
1959 assert(find ("日c語", 'c') == "c語");
1960 assert(find!((a,b)=>a == b)("日c語", 'c') == "c語");
1961 assert(find ("0123456789", 'A').empty);
1962 static if (E.sizeof >= 2)
1964 assert(find ("日本語", '本') == "本語");
1965 assert(find!((a,b)=>a == b)("日本語", '本') == "本語");
1974 static assert(find("abc", 'b') == "bc");
1975 static assert(find("日b語", 'b') == "b語");
1976 static assert(find("日本語", '本') == "本語");
1977 static assert(find([1, 2, 3], 2) == [2, 3]);
1979 static assert(find ([1, 2, 3], 2));
1980 static assert(find!((a,b)=>a == b)([1, 2, 3], 2));
1981 static assert(find ([1, 2, 3], 2));
1982 static assert(find!((a,b)=>a == b)([1, 2, 3], 2));
1987 import std.exception : assertCTFEable;
1988 import std.meta : AliasSeq;
1990 void dg() @safe pure nothrow
1992 byte[] sarr = [1, 2, 3, 4];
1993 ubyte[] uarr = [1, 2, 3, 4];
1994 static foreach (arr; AliasSeq!(sarr, uarr))
1996 static foreach (T; AliasSeq!(byte, ubyte, int, uint))
1998 assert(find(arr, cast(T) 3) == arr[2 .. $]);
1999 assert(find(arr, cast(T) 9) == arr[$ .. $]);
2001 assert(find(arr, 256) == arr[$ .. $]);
2008 // https://issues.dlang.org/show_bug.cgi?id=11603
2011 enum Foo : ubyte { A }
2012 assert([Foo.A].find(Foo.A).empty == false);
2015 assert([x].find(x).empty == false);
2019 R1 find(alias pred = "a == b", R1, R2)(R1 haystack, scope R2 needle)
2020 if (isForwardRange!R1 && isForwardRange!R2
2021 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
2023 static if (!isRandomAccessRange!R1)
2025 static if (is(typeof(pred == "a == b")) && pred == "a == b" && isSomeString!R1 && isSomeString!R2
2026 && haystack[0].sizeof == needle[0].sizeof)
2028 // return cast(R1) find(representation(haystack), representation(needle));
2029 // Specialization for simple string search
2030 alias Representation =
2031 Select!(haystack[0].sizeof == 1, ubyte[],
2032 Select!(haystack[0].sizeof == 2, ushort[], uint[]));
2033 // Will use the array specialization
2034 static TO force(TO, T)(inout T r) @trusted { return cast(TO) r; }
2035 return force!R1(.find!(pred, Representation, Representation)
2036 (force!Representation(haystack), force!Representation(needle)));
2040 return simpleMindedFind!pred(haystack, needle);
2043 else static if (!isBidirectionalRange!R2 || !hasSlicing!R1)
2045 static if (!is(ElementType!R1 == ElementType!R2))
2047 return simpleMindedFind!pred(haystack, needle);
2051 // Prepare the search with needle's first element
2055 haystack = .find!pred(haystack, needle.front);
2057 static if (hasLength!R1 && hasLength!R2 && is(typeof(takeNone(haystack)) == R1))
2059 if (needle.length > haystack.length)
2060 return takeNone(haystack);
2069 size_t matchLen = 1;
2071 // Loop invariant: haystack[0 .. matchLen] matches everything in
2072 // the initial needle that was popped out of needle.
2075 // Extend matchLength as much as possible
2078 import std.range : takeNone;
2080 if (needle.empty || haystack.empty)
2083 static if (hasLength!R1 && is(typeof(takeNone(haystack)) == R1))
2085 if (matchLen == haystack.length)
2086 return takeNone(haystack);
2089 if (!binaryFun!pred(haystack[matchLen], needle.front))
2096 auto bestMatch = haystack[0 .. matchLen];
2097 haystack.popFront();
2098 haystack = .find!pred(haystack, bestMatch);
2102 else // static if (hasSlicing!R1 && isBidirectionalRange!R2)
2104 if (needle.empty) return haystack;
2106 static if (hasLength!R2)
2108 immutable needleLength = needle.length;
2112 immutable needleLength = walkLength(needle.save);
2114 if (needleLength > haystack.length)
2116 return haystack[haystack.length .. haystack.length];
2118 // Optimization in case the ranges are both SortedRanges.
2119 // Binary search can be used to find the first occurence
2120 // of the first element of the needle in haystack.
2121 // When it is found O(walklength(needle)) steps are performed.
2122 // https://issues.dlang.org/show_bug.cgi?id=8829 enhancement
2123 import std.algorithm.comparison : mismatch;
2124 import std.range : SortedRange;
2125 static if (is(R1 == R2)
2126 && is(R1 : SortedRange!TT, TT)
2127 && pred == "a == b")
2129 auto needleFirstElem = needle[0];
2130 auto partitions = haystack.trisect(needleFirstElem);
2131 auto firstElemLen = partitions[1].length;
2134 if (firstElemLen == 0)
2135 return haystack[$ .. $];
2137 while (needle.front() == needleFirstElem)
2142 if (count > firstElemLen)
2143 return haystack[$ .. $];
2146 auto m = mismatch(partitions[2], needle);
2149 return haystack[partitions[0].length + partitions[1].length - count .. $];
2151 else static if (isRandomAccessRange!R2)
2153 immutable lastIndex = needleLength - 1;
2154 auto last = needle[lastIndex];
2155 size_t j = lastIndex, skip = 0;
2156 for (; j < haystack.length;)
2158 if (!binaryFun!pred(haystack[j], last))
2163 immutable k = j - lastIndex;
2164 // last elements match
2165 for (size_t i = 0;; ++i)
2168 return haystack[k .. haystack.length];
2169 if (!binaryFun!pred(haystack[k + i], needle[i]))
2175 while (skip < needleLength && needle[needleLength - 1 - skip] != needle[needleLength - 1])
2186 // auto needleBack = moveBack(needle);
2187 // Stage 1: find the step
2189 auto needleBack = needle.back;
2191 for (auto i = needle.save; !i.empty && i.back != needleBack;
2192 i.popBack(), ++step)
2195 // Stage 2: linear find
2196 size_t scout = needleLength - 1;
2199 if (scout >= haystack.length)
2201 if (!binaryFun!pred(haystack[scout], needleBack))
2206 // Found a match with the last element in the needle
2207 auto cand = haystack[scout + 1 - needleLength .. haystack.length];
2208 if (startsWith!pred(cand, needle))
2216 return haystack[haystack.length .. haystack.length];
2223 import std.container : SList;
2224 import std.range.primitives : empty;
2225 import std.typecons : Tuple;
2227 assert(find("hello, world", "World").empty);
2228 assert(find("hello, world", "wo") == "world");
2229 assert([1, 2, 3, 4].find(SList!int(2, 3)[]) == [2, 3, 4]);
2230 alias C = Tuple!(int, "x", int, "y");
2231 auto a = [C(1,0), C(2,0), C(3,1), C(4,0)];
2232 assert(a.find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
2233 assert(a[1 .. $].find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
2238 import std.container : SList;
2239 alias C = Tuple!(int, "x", int, "y");
2240 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)]);
2243 // https://issues.dlang.org/show_bug.cgi?id=12470
2246 import std.array : replace;
2247 inout(char)[] sanitize(inout(char)[] p)
2249 return p.replace("\0", " ");
2251 assert(sanitize("O\x00o") == "O o");
2256 import std.algorithm.comparison : equal;
2257 import std.container : SList;
2259 auto lst = SList!int(1, 2, 5, 7, 3);
2260 static assert(isForwardRange!(int[]));
2261 static assert(isForwardRange!(typeof(lst[])));
2262 auto r = find(lst[], [2, 5]);
2263 assert(equal(r, SList!int(2, 5, 7, 3)[]));
2268 import std.range : assumeSorted;
2270 auto r1 = assumeSorted([1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 8, 10]);
2271 auto r2 = assumeSorted([3, 3, 4, 5, 6, 7, 8, 8]);
2272 auto r3 = assumeSorted([3, 4, 5, 6, 7, 8]);
2273 auto r4 = assumeSorted([4, 5, 6]);
2274 auto r5 = assumeSorted([12, 13]);
2275 auto r6 = assumeSorted([8, 8, 10, 11]);
2276 auto r7 = assumeSorted([3, 3, 3, 3, 3, 3, 3]);
2278 assert(find(r1, r2) == assumeSorted([3, 3, 4, 5, 6, 7, 8, 8, 8, 10]));
2279 assert(find(r1, r3) == assumeSorted([3, 4, 5, 6, 7, 8, 8, 8, 10]));
2280 assert(find(r1, r4) == assumeSorted([4, 5, 6, 7, 8, 8, 8, 10]));
2281 assert(find(r1, r5).empty());
2282 assert(find(r1, r6).empty());
2283 assert(find(r1, r7).empty());
2288 import std.algorithm.comparison : equal;
2289 // @@@BUG@@@ removing static below makes unittest fail
2290 static struct BiRange
2293 @property bool empty() { return payload.empty; }
2294 @property BiRange save() { return this; }
2295 @property ref int front() { return payload[0]; }
2296 @property ref int back() { return payload[$ - 1]; }
2297 void popFront() { return payload.popFront(); }
2298 void popBack() { return payload.popBack(); }
2300 auto r = BiRange([1, 2, 3, 10, 11, 4]);
2301 assert(equal(find(r, [10, 11]), [10, 11, 4]));
2306 import std.container : SList;
2308 assert(find([ 1, 2, 3 ], SList!int(2, 3)[]) == [ 2, 3 ]);
2309 assert(find([ 1, 2, 1, 2, 3, 3 ], SList!int(2, 3)[]) == [ 2, 3, 3 ]);
2312 // https://issues.dlang.org/show_bug.cgi?id=8334
2315 import std.algorithm.iteration : filter;
2318 auto haystack = [1, 2, 3, 4, 1, 9, 12, 42];
2319 auto needle = [12, 42, 27];
2321 //different overload of find, but it's the base case.
2322 assert(find(haystack, needle).empty);
2324 assert(find(haystack, takeExactly(filter!"true"(needle), 3)).empty);
2325 assert(find(haystack, filter!"true"(needle)).empty);
2328 // https://issues.dlang.org/show_bug.cgi?id=11013
2331 assert(find!"a == a"("abc","abc") == "abc");
2334 // Internally used by some find() overloads above
2335 private R1 simpleMindedFind(alias pred, R1, R2)(R1 haystack, scope R2 needle)
2337 enum estimateNeedleLength = hasLength!R1 && !hasLength!R2;
2339 static if (hasLength!R1)
2341 static if (!hasLength!R2)
2342 size_t estimatedNeedleLength = 0;
2344 immutable size_t estimatedNeedleLength = needle.length;
2347 bool haystackTooShort()
2349 static if (estimateNeedleLength)
2351 return haystack.length < estimatedNeedleLength;
2355 return haystack.empty;
2360 for (;; haystack.popFront())
2362 if (haystackTooShort())
2365 static if (hasLength!R1)
2367 static if (is(typeof(haystack[haystack.length ..
2368 haystack.length]) : R1))
2369 return haystack[haystack.length .. haystack.length];
2375 assert(haystack.empty, "Haystack must be empty by now");
2379 static if (estimateNeedleLength)
2380 size_t matchLength = 0;
2381 for (auto h = haystack.save, n = needle.save;
2383 h.popFront(), n.popFront())
2385 if (h.empty || !binaryFun!pred(h.front, n.front))
2387 // Failed searching n in h
2388 static if (estimateNeedleLength)
2390 if (estimatedNeedleLength < matchLength)
2391 estimatedNeedleLength = matchLength;
2395 static if (estimateNeedleLength)
2405 // Test simpleMindedFind for the case where both haystack and needle have
2412 // This is what triggers https://issues.dlang.org/show_bug.cgi?id=7992.
2413 @property size_t length() const { return _impl.length; }
2414 @property void length(size_t len) { _impl.length = len; }
2416 // This is for conformance to the forward range API (we deliberately
2417 // make it non-random access so that we will end up in
2418 // simpleMindedFind).
2419 @property bool empty() const { return _impl.empty; }
2420 @property dchar front() const { return _impl.front; }
2421 void popFront() { _impl.popFront(); }
2422 @property CustomString save() { return this; }
2425 // If https://issues.dlang.org/show_bug.cgi?id=7992 occurs, this will throw an exception from calling
2426 // popFront() on an empty range.
2427 auto r = find(CustomString("a"), CustomString("b"));
2432 Finds two or more `needles` into a `haystack`. The predicate $(D
2433 pred) is used throughout to compare elements. By default, elements are
2434 compared for equality.
2438 pred = The predicate to use for comparing elements.
2440 haystack = The target of the search. Must be an input range.
2441 If any of `needles` is a range with elements comparable to
2442 elements in `haystack`, then `haystack` must be a
2443 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2444 such that the search can backtrack.
2446 needles = One or more items to search for. Each of `needles` must
2447 be either comparable to one element in `haystack`, or be itself a
2448 forward range with elements comparable with elements in
2453 A tuple containing `haystack` positioned to match one of the
2454 needles and also the 1-based index of the matching element in $(D
2455 needles) (0 if none of `needles` matched, 1 if `needles[0]`
2456 matched, 2 if `needles[1]` matched...). The first needle to be found
2457 will be the one that matches. If multiple needles are found at the
2458 same spot in the range, then the shortest one is the one which matches
2459 (if multiple needles of the same length are found at the same spot (e.g
2460 `"a"` and `'a'`), then the left-most of them in the argument list
2463 The relationship between `haystack` and `needles` simply means
2464 that one can e.g. search for individual `int`s or arrays of $(D
2465 int)s in an array of `int`s. In addition, if elements are
2466 individually comparable, searches of heterogeneous types are allowed
2467 as well: a `double[]` can be searched for an `int` or a $(D
2468 short[]), and conversely a `long` can be searched for a `float`
2469 or a `double[]`. This makes for efficient searches without the need
2470 to coerce one side of the comparison into the other's side type.
2472 The complexity of the search is $(BIGOH haystack.length *
2473 max(needles.length)). (For needles that are individual items, length
2474 is considered to be 1.) The strategy used in searching several
2475 subranges at once maximizes cache usage by moving in `haystack` as
2476 few times as possible.
2478 Tuple!(Range, size_t) find(alias pred = "a == b", Range, Needles...)
2479 (Range haystack, Needles needles)
2480 if (Needles.length > 1 && is(typeof(startsWith!pred(haystack, needles))))
2482 for (;; haystack.popFront())
2484 size_t r = startsWith!pred(haystack, needles);
2485 if (r || haystack.empty)
2487 return tuple(haystack, r);
2495 import std.typecons : tuple;
2496 int[] a = [ 1, 4, 2, 3 ];
2497 assert(find(a, 4) == [ 4, 2, 3 ]);
2498 assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]);
2499 assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2));
2500 // Mixed types allowed if comparable
2501 assert(find(a, 5, [ 1.2, 3.5 ], 2.0) == tuple([ 2, 3 ], 3));
2506 auto s1 = "Mary has a little lamb";
2507 assert(find(s1, "has a", "has an") == tuple("has a little lamb", 1));
2508 assert(find(s1, 't', "has a", "has an") == tuple("has a little lamb", 2));
2509 assert(find(s1, 't', "has a", 'y', "has an") == tuple("y has a little lamb", 3));
2510 assert(find("abc", "bc").length == 2);
2515 import std.algorithm.internal : rndstuff;
2516 import std.meta : AliasSeq;
2517 import std.uni : toUpper;
2519 int[] a = [ 1, 2, 3 ];
2520 assert(find(a, 5).empty);
2521 assert(find(a, 2) == [2, 3]);
2523 foreach (T; AliasSeq!(int, double))
2525 auto b = rndstuff!(T)();
2526 if (!b.length) continue;
2529 assert(find(b, 200).length == b.length - b.length / 4);
2532 // Case-insensitive find of a string
2533 string[] s = [ "Hello", "world", "!" ];
2534 assert(find!("toUpper(a) == toUpper(b)")(s, "hello").length == 3);
2536 static bool f(string a, string b) { return toUpper(a) == toUpper(b); }
2537 assert(find!(f)(s, "hello").length == 3);
2542 import std.algorithm.comparison : equal;
2543 import std.algorithm.internal : rndstuff;
2544 import std.meta : AliasSeq;
2545 import std.range : retro;
2547 int[] a = [ 1, 2, 3, 2, 6 ];
2548 assert(find(retro(a), 5).empty);
2549 assert(equal(find(retro(a), 2), [ 2, 3, 2, 1 ][]));
2551 foreach (T; AliasSeq!(int, double))
2553 auto b = rndstuff!(T)();
2554 if (!b.length) continue;
2557 assert(find(retro(b), 200).length ==
2558 b.length - (b.length - 1) / 2);
2564 import std.algorithm.comparison : equal;
2565 import std.internal.test.dummyrange;
2567 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2568 int[] b = [ 1, 2, 3 ];
2569 assert(find(a, b) == [ 1, 2, 3, 4, 5 ]);
2570 assert(find(b, a).empty);
2572 foreach (DummyType; AllDummyRanges)
2575 auto findRes = find(d, 5);
2576 assert(equal(findRes, [5,6,7,8,9,10]));
2581 * Finds `needle` in `haystack` efficiently using the
2582 * $(LINK2 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm,
2583 * Boyer-Moore) method.
2586 * haystack = A random-access range with length and slicing.
2587 * needle = A $(LREF BoyerMooreFinder).
2590 * `haystack` advanced such that `needle` is a prefix of it (if no
2591 * such position exists, returns `haystack` advanced to termination).
2593 RandomAccessRange find(RandomAccessRange, alias pred, InputRange)(
2594 RandomAccessRange haystack, scope BoyerMooreFinder!(pred, InputRange) needle)
2596 return needle.beFound(haystack);
2601 string h = "/homes/aalexand/d/dmd/bin/../lib/libphobos.a(dmain2.o)"~
2602 "(.gnu.linkonce.tmain+0x74): In function `main' undefined reference"~
2604 string[] ns = ["libphobos", "function", " undefined", "`", ":"];
2607 auto p = find(h, boyerMooreFinder(n));
2615 import std.range.primitives : empty;
2616 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2617 int[] b = [ 1, 2, 3 ];
2619 assert(find(a, boyerMooreFinder(b)) == [ 1, 2, 3, 4, 5 ]);
2620 assert(find(b, boyerMooreFinder(a)).empty);
2625 auto bm = boyerMooreFinder("for");
2626 auto match = find("Moor", bm);
2627 assert(match.empty);
2632 Convenience function. Like find, but only returns whether or not the search
2635 For more information about `pred` see $(LREF find).
2638 $(REF among, std,algorithm,comparison) for checking a value against multiple arguments.
2640 template canFind(alias pred="a == b")
2643 Returns `true` if and only if `pred(e)` is true for any value `e` in the
2644 input range `range`.
2645 Performs (at most) $(BIGOH haystack.length) evaluations of `pred`.
2647 bool canFind(Range)(Range haystack)
2648 if (is(typeof(find!pred(haystack))))
2650 return any!pred(haystack);
2654 Returns `true` if and only if `needle` can be found in $(D
2655 range). Performs $(BIGOH haystack.length) evaluations of `pred`.
2657 bool canFind(Range, Element)(Range haystack, scope Element needle)
2658 if (is(typeof(find!pred(haystack, needle))))
2660 return !find!pred(haystack, needle).empty;
2664 Returns the 1-based index of the first needle found in `haystack`. If no
2665 needle is found, then `0` is returned.
2667 So, if used directly in the condition of an `if` statement or loop, the result
2668 will be `true` if one of the needles is found and `false` if none are
2669 found, whereas if the result is used elsewhere, it can either be cast to
2670 `bool` for the same effect or used to get which needle was found first
2671 without having to deal with the tuple that $(LREF find) returns for the
2674 size_t canFind(Range, Needles...)(Range haystack, scope Needles needles)
2675 if (Needles.length > 1 &&
2676 is(typeof(find!pred(haystack, needles))))
2678 return find!pred(haystack, needles)[1];
2685 const arr = [0, 1, 2, 3];
2686 assert(canFind(arr, 2));
2687 assert(!canFind(arr, 4));
2689 // find one of several needles
2690 assert(arr.canFind(3, 2));
2691 assert(arr.canFind(3, 2) == 2); // second needle found
2692 assert(arr.canFind([1, 3], 2) == 2);
2694 assert(canFind(arr, [1, 2], [2, 3]));
2695 assert(canFind(arr, [1, 2], [2, 3]) == 1);
2696 assert(canFind(arr, [1, 7], [2, 3]));
2697 assert(canFind(arr, [1, 7], [2, 3]) == 2);
2698 assert(!canFind(arr, [1, 3], [2, 4]));
2699 assert(canFind(arr, [1, 3], [2, 4]) == 0);
2703 * Example using a custom predicate.
2704 * Note that the needle appears as the second argument of the predicate.
2713 assert(!canFind(words, "bees"));
2714 assert( canFind!((string elem, string needle) => elem.startsWith(needle))(words, "bees"));
2717 /// Search for multiple items in an array of items (search for needles in an array of haystacks)
2720 string s1 = "aaa111aaa";
2721 string s2 = "aaa222aaa";
2722 string s3 = "aaa333aaa";
2723 string s4 = "aaa444aaa";
2724 const hay = [s1, s2, s3, s4];
2725 assert(hay.canFind!(e => e.canFind("111", "222")));
2730 import std.algorithm.internal : rndstuff;
2732 auto a = rndstuff!(int)();
2735 auto b = a[a.length / 2];
2736 assert(canFind(a, b));
2742 import std.algorithm.comparison : equal;
2743 assert(equal!(canFind!"a < b")([[1, 2, 3], [7, 8, 9]], [2, 8]));
2748 Advances `r` until it finds the first two adjacent elements `a`,
2749 `b` that satisfy `pred(a, b)`. Performs $(BIGOH r.length)
2750 evaluations of `pred`.
2752 For more information about `pred` see $(LREF find).
2755 pred = The predicate to satisfy.
2756 r = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to
2760 `r` advanced to the first occurrence of two adjacent elements that satisfy
2761 the given predicate. If there are no such two elements, returns `r` advanced
2765 $(LINK2 http://en.cppreference.com/w/cpp/algorithm/adjacent_find, STL's `adjacent_find`)
2767 Range findAdjacent(alias pred = "a == b", Range)(Range r)
2768 if (isForwardRange!(Range))
2770 auto ahead = r.save;
2773 for (ahead.popFront(); !ahead.empty; r.popFront(), ahead.popFront())
2775 if (binaryFun!(pred)(r.front, ahead.front)) return r;
2778 static if (!isInfinite!Range)
2786 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
2787 auto r = findAdjacent(a);
2788 assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]);
2789 auto p = findAdjacent!("a < b")(a);
2790 assert(p == [ 7, 8, 9 ]);
2796 import std.algorithm.comparison : equal;
2797 import std.internal.test.dummyrange;
2800 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
2801 auto p = findAdjacent(a);
2802 assert(p == [10, 10, 9, 8, 8, 7, 8, 9 ]);
2803 p = findAdjacent!("a < b")(a);
2804 assert(p == [7, 8, 9]);
2807 p = findAdjacent(a);
2810 a = [ 1, 2, 3, 4, 5 ];
2811 p = findAdjacent(a);
2813 p = findAdjacent!"a > b"(a);
2815 ReferenceForwardRange!int rfr = new ReferenceForwardRange!int([1, 2, 3, 2, 2, 3]);
2816 assert(equal(findAdjacent(rfr), [2, 2, 3]));
2818 // https://issues.dlang.org/show_bug.cgi?id=9350
2819 assert(!repeat(1).findAdjacent().empty);
2824 Searches the given range for an element that matches one of the given choices.
2826 Advances `seq` by calling `seq.popFront` until either
2827 `find!(pred)(choices, seq.front)` is `true`, or `seq` becomes empty.
2828 Performs $(BIGOH seq.length * choices.length) evaluations of `pred`.
2830 For more information about `pred` see $(LREF find).
2833 pred = The predicate to use for determining a match.
2834 seq = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to
2836 choices = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2837 of possible choices.
2840 `seq` advanced to the first matching element, or until empty if there are no
2843 See_Also: $(LREF find), $(REF among, std,algorithm,comparison)
2845 InputRange findAmong(alias pred = "a == b", InputRange, ForwardRange)(
2846 InputRange seq, ForwardRange choices)
2847 if (isInputRange!InputRange && isForwardRange!ForwardRange)
2849 for (; !seq.empty && find!pred(choices.save, seq.front).empty; seq.popFront())
2858 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2859 int[] b = [ 3, 1, 2 ];
2860 assert(findAmong(a, b) == a[2 .. $]);
2865 int[] a = [ -1, 0, 2, 1, 2, 3, 4, 5 ];
2866 int[] b = [ 1, 2, 3 ];
2867 assert(findAmong(a, b) == [2, 1, 2, 3, 4, 5 ]);
2868 assert(findAmong(b, [ 4, 6, 7 ][]).empty);
2869 assert(findAmong!("a == b")(a, b).length == a.length - 2);
2870 assert(findAmong!("a == b")(b, [ 4, 6, 7 ][]).empty);
2873 // https://issues.dlang.org/show_bug.cgi?id=19765
2876 import std.range.interfaces : inputRangeObject;
2877 auto choices = inputRangeObject("b");
2878 auto f = "foobar".findAmong(choices);
2884 * Finds `needle` in `haystack` and positions `haystack`
2885 * right after the first occurrence of `needle`.
2887 * If no needle is provided, the `haystack` is advanced as long as `pred`
2888 * evaluates to `true`.
2889 * Similarly, the haystack is positioned so as `pred` evaluates to `false` for
2892 * For more information about `pred` see $(LREF find).
2896 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search
2899 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search
2901 * pred = Custom predicate for comparison of haystack and needle
2903 * Returns: `true` if the needle was found, in which case `haystack` is
2904 * positioned after the end of the first occurrence of `needle`; otherwise
2905 * `false`, leaving `haystack` untouched. If no needle is provided, it returns
2906 * the number of times `pred(haystack.front)` returned true.
2908 * See_Also: $(LREF find)
2910 bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle)
2911 if (isForwardRange!R1 && isForwardRange!R2
2912 && is(typeof(binaryFun!pred(haystack.front, needle.front))))
2914 auto parts = findSplit!pred(haystack, needle);
2915 if (parts[1].empty) return false;
2917 haystack = parts[2];
2924 import std.range.primitives : empty;
2925 // Needle is found; s is replaced by the substring following the first
2926 // occurrence of the needle.
2927 string s = "abcdef";
2928 assert(findSkip(s, "cd") && s == "ef");
2930 // Needle is not found; s is left untouched.
2932 assert(!findSkip(s, "cxd") && s == "abcdef");
2934 // If the needle occurs at the end of the range, the range is left empty.
2936 assert(findSkip(s, "def") && s.empty);
2939 // https://issues.dlang.org/show_bug.cgi?id=19020
2942 static struct WrapperRange
2945 @property auto empty() { return _r.empty(); }
2946 @property auto front() { return _r.front(); }
2947 auto popFront() { return _r.popFront(); }
2948 @property auto save() { return WrapperRange(_r.save); }
2950 auto tmp = WrapperRange("there is a bug here: *");
2951 assert(!tmp.findSkip("*/"));
2952 assert(tmp._r == "there is a bug here: *");
2956 size_t findSkip(alias pred, R1)(ref R1 haystack)
2957 if (isForwardRange!R1 && ifTestable!(typeof(haystack.front), unaryFun!pred))
2960 while (!haystack.empty && unaryFun!pred(haystack.front))
2971 import std.ascii : isWhite;
2973 assert(findSkip!isWhite(s) && s == "abc");
2974 assert(!findSkip!isWhite(s) && s == "abc");
2977 assert(findSkip!isWhite(s) == 2);
2982 import std.ascii : isWhite;
2985 assert(findSkip!isWhite(s) == 2);
2988 private struct FindSplitResult(ubyte emptyRangeIndex, Types...)
2992 asTuple = typeof(asTuple)(vals);
2994 void opAssign(typeof(asTuple) rhs)
2998 Tuple!Types asTuple;
3001 static if (hasConstEmptyMember!(typeof(asTuple[emptyRangeIndex])))
3003 bool opCast(T : bool)() const => !asTuple[emptyRangeIndex].empty;
3007 bool opCast(T : bool)() => !asTuple[emptyRangeIndex].empty;
3012 These functions find the first occurrence of `needle` in `haystack` and then
3013 split `haystack` as follows.
3016 `findSplit` returns a tuple `result` containing $(I three) ranges.
3018 $(LI `result[0]` is the portion of `haystack` before `needle`)
3019 $(LI `result[1]` is the portion of
3020 `haystack` that matches `needle`)
3021 $(LI `result[2]` is the portion of `haystack`
3024 If `needle` was not found, `result[0]` comprehends `haystack`
3025 entirely and `result[1]` and `result[2]` are empty.
3027 `findSplitBefore` returns a tuple `result` containing two ranges.
3029 $(LI `result[0]` is the portion of `haystack` before `needle`)
3030 $(LI `result[1]` is the balance of `haystack` starting with the match.)
3032 If `needle` was not found, `result[0]`
3033 comprehends `haystack` entirely and `result[1]` is empty.
3035 `findSplitAfter` returns a tuple `result` containing two ranges.
3037 $(LI `result[0]` is the portion of `haystack` up to and including the
3039 $(LI `result[1]` is the balance of `haystack` starting
3042 If `needle` was not found, `result[0]` is empty
3043 and `result[1]` is `haystack`.
3046 In all cases, the concatenation of the returned ranges spans the
3049 If `haystack` is a random-access range, all three components of the tuple have
3050 the same type as `haystack`. Otherwise, `haystack` must be a
3051 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) and
3052 the type of `result[0]` (and `result[1]` for `findSplit`) is the same as
3053 the result of $(REF takeExactly, std,range).
3055 For more information about `pred` see $(LREF find).
3058 pred = Predicate to compare 2 elements.
3059 haystack = The forward range to search.
3060 needle = The forward range to look for.
3064 A sub-type of $(REF Tuple, std, typecons) of the split portions of `haystack` (see above for
3065 details). This sub-type of `Tuple` defines `opCast!bool`, which
3066 returns `true` when the separating `needle` was found and `false` otherwise.
3068 See_Also: $(LREF find)
3070 auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3071 if (isForwardRange!R1 && isForwardRange!R2)
3073 static if (isSomeString!R1 && isSomeString!R2
3074 || (isRandomAccessRange!R1 && hasSlicing!R1 && hasLength!R1 && hasLength!R2))
3076 auto balance = find!pred(haystack, needle);
3077 immutable pos1 = haystack.length - balance.length;
3078 immutable pos2 = balance.empty ? pos1 : pos1 + needle.length;
3079 alias Slice = typeof(haystack[0 .. pos1]);
3080 return FindSplitResult!(1, Slice, Slice, Slice)(
3081 haystack[0 .. pos1], haystack[pos1 .. pos2], haystack[pos2 .. haystack.length]);
3085 import std.range : takeExactly;
3086 auto original = haystack.save;
3087 auto h = haystack.save;
3088 auto n = needle.save;
3090 while (!n.empty && !h.empty)
3092 if (binaryFun!pred(h.front, n.front))
3100 haystack.popFront();
3106 if (!n.empty) // incomplete match at the end of haystack
3110 return FindSplitResult!(1,
3111 typeof(takeExactly(original, pos1)),
3112 typeof(takeExactly(original, pos1)), typeof(h))(
3113 takeExactly(original, pos1),
3114 takeExactly(haystack, pos2 - pos1), h);
3119 auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3120 if (isForwardRange!R1 && isForwardRange!R2)
3122 static if (isSomeString!R1 && isSomeString!R2
3123 || (isRandomAccessRange!R1 && hasLength!R1 && hasSlicing!R1 && hasLength!R2))
3125 auto balance = find!pred(haystack, needle);
3126 immutable pos = haystack.length - balance.length;
3127 return FindSplitResult!(1,
3128 typeof(haystack[0 .. pos]), typeof(haystack[0 .. pos]))(
3129 haystack[0 .. pos], haystack[pos .. haystack.length]);
3133 import std.range : takeExactly;
3134 auto original = haystack.save;
3135 auto h = haystack.save;
3136 auto n = needle.save;
3138 while (!n.empty && !h.empty)
3140 if (binaryFun!pred(h.front, n.front))
3148 haystack.popFront();
3154 if (!n.empty) // incomplete match at the end of haystack
3159 return FindSplitResult!(1,
3160 typeof(takeExactly(original, pos1)), typeof(haystack))(
3161 takeExactly(original, pos1), haystack);
3166 auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3167 if (isForwardRange!R1 && isForwardRange!R2)
3169 static if (isSomeString!R1 && isSomeString!R2
3170 || isRandomAccessRange!R1 && hasLength!R1 && hasSlicing!R1 && hasLength!R2)
3172 auto balance = find!pred(haystack, needle);
3173 immutable pos = balance.empty ? 0 : haystack.length - balance.length + needle.length;
3174 return FindSplitResult!(0,
3175 typeof(haystack[0 .. pos]), typeof(haystack[0 .. pos]))(
3176 haystack[0 .. pos], haystack[pos .. haystack.length]);
3180 import std.range : takeExactly;
3181 alias Res = FindSplitResult!(0, typeof(takeExactly(haystack, 0)), typeof(haystack));
3182 auto original = haystack.save;
3183 auto h = haystack.save;
3184 auto n = needle.save;
3191 return Res(takeExactly(original, 0), original);
3193 if (binaryFun!pred(h.front, n.front))
3201 haystack.popFront();
3207 return Res(takeExactly(original, pos2), h);
3211 /// Returning a subtype of $(REF Tuple, std,typecons) enables
3212 /// the following convenient idiom:
3213 @safe pure nothrow unittest
3215 // findSplit returns a triplet
3216 if (auto split = "dlang-rocks".findSplit("-"))
3218 assert(split[0] == "dlang");
3219 assert(split[1] == "-");
3220 assert(split[2] == "rocks");
3224 // findSplitBefore returns 2 ranges
3225 if (const split = [2, 3, 2, 3, 4, 1].findSplitBefore!"a > b"([2, 2]))
3227 assert(split[0] == [2, 3, 2]);
3228 // [3, 4] each greater than [2, 2]
3229 assert(split[1] == [3, 4, 1]);
3235 @safe pure nothrow unittest
3237 import std.range.primitives : empty;
3239 auto a = "Carl Sagan Memorial Station";
3240 auto r = findSplit(a, "Velikovsky");
3241 import std.typecons : isTuple;
3242 static assert(isTuple!(typeof(r.asTuple)));
3243 static assert(isTuple!(typeof(r)));
3248 r = findSplit(a, " ");
3249 assert(r[0] == "Carl");
3250 assert(r[1] == " ");
3251 assert(r[2] == "Sagan Memorial Station");
3252 if (const r1 = findSplitBefore(a, "Sagan"))
3255 assert(r1[0] == "Carl ");
3256 assert(r1[1] == "Sagan Memorial Station");
3258 if (const r2 = findSplitAfter(a, "Sagan"))
3261 assert(r2[0] == "Carl Sagan");
3262 assert(r2[1] == " Memorial Station");
3266 /// Use $(REF only, std,range) to find single elements:
3267 @safe pure nothrow unittest
3269 import std.range : only;
3270 assert([1, 2, 3, 4].findSplitBefore(only(3))[0] == [1, 2]);
3273 @safe pure nothrow unittest
3275 import std.range.primitives : empty;
3277 immutable a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3278 auto r = findSplit(a, [9, 1]);
3283 r = findSplit(a, [3]);
3285 assert(r[0] == a[0 .. 2]);
3286 assert(r[1] == a[2 .. 3]);
3287 assert(r[2] == a[3 .. $]);
3290 const r1 = findSplitBefore(a, [9, 1]);
3293 assert(r1[1].empty);
3296 if (immutable r1 = findSplitBefore(a, [3, 4]))
3299 assert(r1[0] == a[0 .. 2]);
3300 assert(r1[1] == a[2 .. $]);
3305 const r2 = findSplitAfter(a, [9, 1]);
3307 assert(r2[0].empty);
3311 if (immutable r3 = findSplitAfter(a, [3, 4]))
3314 assert(r3[0] == a[0 .. 4]);
3315 assert(r3[1] == a[4 .. $]);
3320 @safe pure nothrow unittest
3322 import std.algorithm.comparison : equal;
3323 import std.algorithm.iteration : filter;
3325 auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3326 auto fwd = filter!"a > 0"(a);
3327 auto r = findSplit(fwd, [9, 1]);
3329 assert(equal(r[0], a));
3332 r = findSplit(fwd, [3]);
3334 assert(equal(r[0], a[0 .. 2]));
3335 assert(equal(r[1], a[2 .. 3]));
3336 assert(equal(r[2], a[3 .. $]));
3337 r = findSplit(fwd, [8, 9]);
3339 assert(equal(r[0], a));
3343 // auto variable `r2` cannot be `const` because `fwd.front` is mutable
3345 auto r1 = findSplitBefore(fwd, [9, 1]);
3347 assert(equal(r1[0], a));
3348 assert(r1[1].empty);
3351 if (auto r1 = findSplitBefore(fwd, [3, 4]))
3354 assert(equal(r1[0], a[0 .. 2]));
3355 assert(equal(r1[1], a[2 .. $]));
3360 auto r1 = findSplitBefore(fwd, [8, 9]);
3362 assert(equal(r1[0], a));
3363 assert(r1[1].empty);
3367 auto r2 = findSplitAfter(fwd, [9, 1]);
3369 assert(r2[0].empty);
3370 assert(equal(r2[1], a));
3373 if (auto r2 = findSplitAfter(fwd, [3, 4]))
3376 assert(equal(r2[0], a[0 .. 4]));
3377 assert(equal(r2[1], a[4 .. $]));
3382 auto r2 = findSplitAfter(fwd, [8, 9]);
3384 assert(r2[0].empty);
3385 assert(equal(r2[1], a));
3389 @safe pure nothrow @nogc unittest
3391 auto str = "sep,one,sep,two";
3393 auto split = str.findSplitAfter(",");
3394 assert(split[0] == "sep,");
3396 split = split[1].findSplitAfter(",");
3397 assert(split[0] == "one,");
3399 split = split[1].findSplitBefore(",");
3400 assert(split[0] == "sep");
3403 @safe pure nothrow @nogc unittest
3405 auto str = "sep,one,sep,two";
3407 auto split = str.findSplitBefore(",two");
3408 assert(split[0] == "sep,one,sep");
3409 assert(split[1] == ",two");
3411 split = split[0].findSplitBefore(",sep");
3412 assert(split[0] == "sep,one");
3413 assert(split[1] == ",sep");
3415 split = split[0].findSplitAfter(",");
3416 assert(split[0] == "sep,");
3417 assert(split[1] == "one");
3420 // https://issues.dlang.org/show_bug.cgi?id=11013
3424 auto split = var.findSplitBefore!q{a == a}(var);
3425 assert(split[0] == "");
3426 assert(split[1] == "abc");
3432 Computes the minimum (respectively maximum) of `range` along with its number of
3433 occurrences. Formally, the minimum is a value `x` in `range` such that $(D
3434 pred(a, x)) is `false` for all values `a` in `range`. Conversely, the maximum is
3435 a value `x` in `range` such that `pred(x, a)` is `false` for all values `a`
3436 in `range` (note the swapped arguments to `pred`).
3438 These functions may be used for computing arbitrary extrema by choosing `pred`
3439 appropriately. For corrrect functioning, `pred` must be a strict partial order,
3440 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and
3441 irreflexive (`pred(a, a)` is `false`). The $(LUCKY trichotomy property of
3442 inequality) is not required: these algorithms consider elements `a` and `b` equal
3443 (for the purpose of counting) if `pred` puts them in the same equivalence class,
3444 i.e. `!pred(a, b) && !pred(b, a)`.
3447 pred = The ordering predicate to use to determine the extremum (minimum
3449 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to count.
3451 Returns: The minimum, respectively maximum element of a range together with the
3452 number it occurs in the range.
3454 Limitations: If at least one of the arguments is NaN, the result is
3455 an unspecified value. See $(REF maxElement, std,algorithm,searching)
3456 for examples on how to cope with NaNs.
3458 Throws: `Exception` if `range.empty`.
3460 See_Also: $(REF min, std,algorithm,comparison), $(LREF minIndex), $(LREF minElement), $(LREF minPos)
3462 Tuple!(ElementType!Range, size_t)
3463 minCount(alias pred = "a < b", Range)(Range range)
3464 if (isInputRange!Range && !isInfinite!Range &&
3465 is(typeof(binaryFun!pred(range.front, range.front))))
3467 import std.algorithm.internal : algoFormat;
3468 import std.exception : enforce;
3470 alias T = ElementType!Range;
3471 alias UT = Unqual!T;
3472 alias RetType = Tuple!(T, size_t);
3474 static assert(is(typeof(RetType(range.front, 1))),
3475 algoFormat("Error: Cannot call minCount on a %s, because it is not possible "~
3476 "to copy the result value (a %s) into a Tuple.", Range.stringof, T.stringof));
3478 enforce(!range.empty, "Can't count elements from an empty range");
3479 size_t occurrences = 1;
3481 static if (isForwardRange!Range)
3483 Range least = range.save;
3484 for (range.popFront(); !range.empty; range.popFront())
3486 if (binaryFun!pred(least.front, range.front))
3488 assert(!binaryFun!pred(range.front, least.front),
3489 "min/maxPos: predicate must be a strict partial order.");
3492 if (binaryFun!pred(range.front, least.front))
3501 return RetType(least.front, occurrences);
3503 else static if (isAssignable!(UT, T) || (!hasElaborateAssign!UT && isAssignable!UT))
3506 static if (isAssignable!(UT, T)) v = range.front;
3507 else v = cast(UT) range.front;
3509 for (range.popFront(); !range.empty; range.popFront())
3511 if (binaryFun!pred(*cast(T*)&v, range.front)) continue;
3512 if (binaryFun!pred(range.front, *cast(T*)&v))
3515 static if (isAssignable!(UT, T)) v = range.front;
3516 else v = cast(UT) range.front; //Safe because !hasElaborateAssign!UT
3522 return RetType(*cast(T*)&v, occurrences);
3524 else static if (hasLvalueElements!Range)
3526 import std.algorithm.internal : addressOf;
3527 T* p = addressOf(range.front);
3528 for (range.popFront(); !range.empty; range.popFront())
3530 if (binaryFun!pred(*p, range.front)) continue;
3531 if (binaryFun!pred(range.front, *p))
3534 p = addressOf(range.front);
3540 return RetType(*p, occurrences);
3543 static assert(false,
3544 algoFormat("Sorry, can't find the minCount of a %s: Don't know how "~
3545 "to keep track of the smallest %s element.", Range.stringof, T.stringof));
3549 Tuple!(ElementType!Range, size_t)
3550 maxCount(alias pred = "a < b", Range)(Range range)
3551 if (isInputRange!Range && !isInfinite!Range &&
3552 is(typeof(binaryFun!pred(range.front, range.front))))
3554 return range.minCount!((a, b) => binaryFun!pred(b, a));
3560 import std.conv : text;
3561 import std.typecons : tuple;
3563 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3564 // Minimum is 1 and occurs 3 times
3565 assert(a.minCount == tuple(1, 3));
3566 // Maximum is 4 and occurs 2 times
3567 assert(a.maxCount == tuple(4, 2));
3572 import std.conv : text;
3573 import std.exception : assertThrown;
3574 import std.internal.test.dummyrange;
3576 int[][] b = [ [4], [2, 4], [4], [4] ];
3577 auto c = minCount!("a[0] < b[0]")(b);
3578 assert(c == tuple([2, 4], 1), text(c[0]));
3581 assertThrown(minCount(b[$..$]));
3583 //test with reference ranges. Test both input and forward.
3584 assert(minCount(new ReferenceInputRange!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2));
3585 assert(minCount(new ReferenceForwardRange!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2));
3590 import std.conv : text;
3591 import std.meta : AliasSeq;
3593 static struct R(T) //input range
3599 immutable a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3600 R!(immutable int) b = R!(immutable int)(a);
3602 assert(minCount(a) == tuple(1, 3));
3603 assert(minCount(b) == tuple(1, 3));
3604 assert(minCount!((ref immutable int a, ref immutable int b) => (a > b))(a) == tuple(4, 2));
3605 assert(minCount!((ref immutable int a, ref immutable int b) => (a > b))(b) == tuple(4, 2));
3607 immutable(int[])[] c = [ [4], [2, 4], [4], [4] ];
3608 assert(minCount!("a[0] < b[0]")(c) == tuple([2, 4], 1), text(c[0]));
3614 alias IS1 = immutable(S1);
3615 static assert( isAssignable!S1);
3616 static assert( isAssignable!(S1, IS1));
3621 this(ref immutable int i) immutable {p = &i;}
3622 this(ref int i) {p = &i;}
3623 @property ref inout(int) i() inout {return *p;}
3624 bool opEquals(const S2 other) const {return i == other.i;}
3626 alias IS2 = immutable(S2);
3627 static assert( isAssignable!S2);
3628 static assert(!isAssignable!(S2, IS2));
3629 static assert(!hasElaborateAssign!S2);
3634 void opAssign(ref S3 other) @disable;
3636 static assert(!isAssignable!S3);
3638 static foreach (Type; AliasSeq!(S1, IS1, S2, IS2, S3))
3640 static if (is(Type == immutable)) alias V = immutable int;
3643 auto r1 = [Type(two), Type(one), Type(one)];
3644 auto r2 = R!Type(r1);
3645 assert(minCount!"a.i < b.i"(r1) == tuple(Type(one), 2));
3646 assert(minCount!"a.i < b.i"(r2) == tuple(Type(one), 2));
3647 assert(one == 1 && two == 2);
3652 Iterates the passed range and returns the minimal element.
3653 A custom mapping function can be passed to `map`.
3654 In other languages this is sometimes called `argmin`.
3657 Exactly `n - 1` comparisons are needed.
3660 map = custom accessor for the comparison key
3661 r = range from which the minimal element will be selected
3662 seed = custom seed to use as initial element
3664 Precondition: If a seed is not given, `r` must not be empty.
3666 Returns: The minimal element of the passed-in range.
3669 If at least one of the arguments is NaN, the result is an unspecified value.
3671 If you want to ignore NaNs, you can use $(REF filter, std,algorithm,iteration)
3672 and $(REF isNaN, std,math) to remove them, before applying minElement.
3673 Add a suitable seed, to avoid error messages if all elements are NaNs:
3676 <range>.filter!(a=>!a.isNaN).minElement(<seed>);
3679 If you want to get NaN as a result if a NaN is present in the range,
3680 you can use $(REF fold, std,algorithm,iteration) and $(REF isNaN, std,math):
3683 <range>.fold!((a,b)=>a.isNaN || b.isNaN ? real.nan : a < b ? a : b);
3688 $(LREF extrema), $(LREF maxElement), $(REF min, std,algorithm,comparison), $(LREF minCount),
3689 $(LREF minIndex), $(LREF minPos)
3691 auto minElement(alias map = (a => a), Range)(Range r)
3692 if (isInputRange!Range && !isInfinite!Range)
3694 return extremum!map(r);
3698 auto minElement(alias map = (a => a), Range, RangeElementType = ElementType!Range)
3699 (Range r, RangeElementType seed)
3700 if (isInputRange!Range && !isInfinite!Range &&
3701 !is(CommonType!(ElementType!Range, RangeElementType) == void))
3703 return extremum!map(r, seed);
3709 import std.range : enumerate;
3710 import std.typecons : tuple;
3712 assert([2, 7, 1, 3].minElement == 1);
3714 // allows to get the index of an element too
3715 assert([5, 3, 7, 9].enumerate.minElement!"a.value" == tuple(1, 3));
3717 // any custom accessor can be passed
3718 assert([[0, 4], [1, 2]].minElement!"a[1]" == [1, 2]);
3722 assert(arr.minElement(1) == 1);
3727 import std.range : enumerate, iota;
3729 assert([3, 4, 5, 1, 2].enumerate.minElement!"a.value" == tuple(3, 1));
3730 assert([5, 2, 4].enumerate.minElement!"a.value" == tuple(1, 2));
3733 assert(iota(1, 5).minElement() == 1);
3734 assert(iota(2, 5).enumerate.minElement!"a.value" == tuple(0, 2));
3736 // should work with const
3737 const(int)[] immArr = [2, 1, 3];
3738 assert(immArr.minElement == 1);
3740 // should work with immutable
3741 immutable(int)[] immArr2 = [2, 1, 3];
3742 assert(immArr2.minElement == 1);
3745 assert(["b", "a", "c"].minElement == "a");
3747 // with all dummy ranges
3748 import std.internal.test.dummyrange;
3749 foreach (DummyType; AllDummyRanges)
3752 assert(d.minElement == 1);
3753 assert(d.minElement!(a => a) == 1);
3754 assert(d.minElement!(a => -a) == 10);
3757 // with empty, but seeded ranges
3759 assert(arr.minElement(42) == 42);
3760 assert(arr.minElement!(a => a)(42) == 42);
3763 @nogc @safe nothrow pure unittest
3765 static immutable arr = [7, 3, 4, 2, 1, 8];
3766 assert(arr.minElement == 1);
3768 static immutable arr2d = [[1, 9], [3, 1], [4, 2]];
3769 assert(arr2d.minElement!"a[1]" == arr2d[1]);
3772 // https://issues.dlang.org/show_bug.cgi?id=17982
3780 const(A)[] v = [A(0)];
3781 assert(v.minElement!"a.val" == A(0));
3784 // https://issues.dlang.org/show_bug.cgi?id=17982
3790 this(int val){ this.val = val; }
3793 const(B) doStuff(const(B)[] v)
3795 return v.minElement!"a.val";
3797 assert(doStuff([new B(1), new B(0), new B(2)]).val == 0);
3799 const(B)[] arr = [new B(0), new B(1)];
3800 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
3801 assert(arr.minElement!"a.val".val == 0);
3804 // https://issues.dlang.org/show_bug.cgi?id=24827
3822 bool opEquals()(auto ref S rhs)
3824 return this.i == rhs.i;
3827 int opCmp()(auto ref S rhs)
3832 return this.i == rhs.i ? 0 : 1;
3841 auto arr = [S(19), S(2), S(145), S(7)];
3842 assert(minElement(arr) == S(2));
3846 Iterates the passed range and returns the maximal element.
3847 A custom mapping function can be passed to `map`.
3848 In other languages this is sometimes called `argmax`.
3851 Exactly `n - 1` comparisons are needed.
3854 map = custom accessor for the comparison key
3855 r = range from which the maximum element will be selected
3856 seed = custom seed to use as initial element
3858 Precondition: If a seed is not given, `r` must not be empty.
3860 Returns: The maximal element of the passed-in range.
3863 If at least one of the arguments is NaN, the result is an unspecified value.
3864 See $(REF minElement, std,algorithm,searching) for examples on how to cope
3869 $(LREF extrema), $(LREF minElement), $(REF max, std,algorithm,comparison), $(LREF maxCount),
3870 $(LREF maxIndex), $(LREF maxPos)
3872 auto maxElement(alias map = (a => a), Range)(Range r)
3873 if (isInputRange!Range && !isInfinite!Range)
3875 return extremum!(map, "a > b")(r);
3879 auto maxElement(alias map = (a => a), Range, RangeElementType = ElementType!Range)
3880 (Range r, RangeElementType seed)
3881 if (isInputRange!Range && !isInfinite!Range &&
3882 !is(CommonType!(ElementType!Range, RangeElementType) == void))
3884 return extremum!(map, "a > b")(r, seed);
3890 import std.range : enumerate;
3891 import std.typecons : tuple;
3892 assert([2, 1, 4, 3].maxElement == 4);
3894 // allows to get the index of an element too
3895 assert([2, 1, 4, 3].enumerate.maxElement!"a.value" == tuple(2, 4));
3897 // any custom accessor can be passed
3898 assert([[0, 4], [1, 2]].maxElement!"a[1]" == [0, 4]);
3902 assert(arr.minElement(1) == 1);
3907 import std.range : enumerate, iota;
3910 assert([3, 4, 5, 1, 2].enumerate.maxElement!"a.value" == tuple(2, 5));
3911 assert([5, 2, 4].enumerate.maxElement!"a.value" == tuple(0, 5));
3914 assert(iota(1, 5).maxElement() == 4);
3915 assert(iota(2, 5).enumerate.maxElement!"a.value" == tuple(2, 4));
3916 assert(iota(4, 14).enumerate.maxElement!"a.value" == tuple(9, 13));
3918 // should work with const
3919 const(int)[] immArr = [2, 3, 1];
3920 assert(immArr.maxElement == 3);
3922 // should work with immutable
3923 immutable(int)[] immArr2 = [2, 3, 1];
3924 assert(immArr2.maxElement == 3);
3927 assert(["a", "c", "b"].maxElement == "c");
3929 // with all dummy ranges
3930 import std.internal.test.dummyrange;
3931 foreach (DummyType; AllDummyRanges)
3934 assert(d.maxElement == 10);
3935 assert(d.maxElement!(a => a) == 10);
3936 assert(d.maxElement!(a => -a) == 1);
3939 // with empty, but seeded ranges
3941 assert(arr.maxElement(42) == 42);
3942 assert(arr.maxElement!(a => a)(42) == 42);
3946 @nogc @safe nothrow pure unittest
3948 static immutable arr = [7, 3, 8, 2, 1, 4];
3949 assert(arr.maxElement == 8);
3951 static immutable arr2d = [[1, 3], [3, 9], [4, 2]];
3952 assert(arr2d.maxElement!"a[1]" == arr2d[1]);
3955 // https://issues.dlang.org/show_bug.cgi?id=17982
3961 this(int val){ this.val = val; }
3964 const(B) doStuff(const(B)[] v)
3966 return v.maxElement!"a.val";
3968 assert(doStuff([new B(1), new B(0), new B(2)]).val == 2);
3970 const(B)[] arr = [new B(0), new B(1)];
3971 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
3972 assert(arr.maxElement!"a.val".val == 1);
3975 // https://issues.dlang.org/show_bug.cgi?id=23993
3978 import std.bigint : BigInt;
3980 assert([BigInt(2), BigInt(3)].maxElement == BigInt(3));
3983 // https://issues.dlang.org/show_bug.cgi?id=24596
3988 int getI() @safe => i;
3989 this(int i) @safe { this.i = i; }
3991 auto arr = [new A(2), new A(3)];
3993 arr.maxElement!(a => a.getI);
3995 assert(arr[0].getI == 2);
3998 // https://issues.dlang.org/show_bug.cgi?id=24827
4016 bool opEquals()(auto ref S rhs)
4018 return this.i == rhs.i;
4021 int opCmp()(auto ref S rhs)
4026 return this.i == rhs.i ? 0 : 1;
4035 auto arr = [S(19), S(2), S(145), S(7)];
4036 assert(maxElement(arr) == S(145));
4039 /** Returns an array of the minimum and maximum element in `r`.
4040 * Performs `< 3n/2` comparisons, unlike the naive `< 2n`.
4042 * r = The range to traverse.
4044 // TODO alias map = a => a
4045 ElementType!Range[2] extrema(Range)(Range r)
4046 if (isInputRange!Range && !isInfinite!Range)
4049 static if (isRandomAccessRange!Range && hasLength!Range)
4052 return [r[0], r[0]];
4054 typeof(return) result;
4056 if (r.length & 1) // odd
4058 result = [r[0], r[0]];
4063 result = (r[0] < r[1]) ? [r[0], r[1]] : [r[1], r[0]];
4067 const imax = r.length;
4068 for (; i != imax; i += 2)
4073 if (r[i] < result[0])
4075 if (r[i+1] > result[1])
4080 if (r[i+1] < result[0])
4082 if (r[i] > result[1])
4090 auto first = r.front;
4093 return [first, first];
4095 typeof(return) result = (first < r.front) ? [first, r.front] : [r.front, first];
4106 if (first < result[0])
4108 else if (first > result[1])
4113 if (first < r.front)
4115 if (first < result[0])
4117 if (r.front > result[1])
4118 result[1] = r.front;
4122 if (r.front < result[0])
4123 result[0] = r.front;
4124 if (first > result[1])
4134 assert(extrema([5,2,9,4,1]) == [1, 9]);
4139 assert(extrema([8,3,7,4,9]) == [3, 9]);
4140 assert(extrema([1,5,3,2]) == [1, 5]);
4141 assert(extrema([2,3,3,2]) == [2, 3]);
4144 assert(iota(2, 5).extrema == [2, 4]);
4145 assert(iota(3, 7).retro.extrema == [3, 6]);
4147 import std.internal.test.dummyrange;
4148 foreach (DummyType; AllDummyRanges)
4151 assert(d.extrema == [1, 10]);
4154 version (StdRandomTests)
4155 foreach (i; 0 .. 1000)
4158 auto arr = generate!(() => uniform(0, 100)).takeExactly(uniform(1, 10)).array;
4159 auto result = arr.extrema;
4160 assert(result[0] == arr.minElement);
4161 assert(result[1] == arr.maxElement);
4167 Computes a subrange of `range` starting at the first occurrence of `range`'s
4168 minimum (respectively maximum) and with the same ending as `range`, or the
4169 empty range if `range` itself is empty.
4171 Formally, the minimum is a value `x` in `range` such that `pred(a, x)` is
4172 `false` for all values `a` in `range`. Conversely, the maximum is a value `x` in
4173 `range` such that `pred(x, a)` is `false` for all values `a` in `range` (note
4174 the swapped arguments to `pred`).
4176 These functions may be used for computing arbitrary extrema by choosing `pred`
4177 appropriately. For corrrect functioning, `pred` must be a strict partial order,
4178 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and
4179 irreflexive (`pred(a, a)` is `false`).
4182 pred = The ordering predicate to use to determine the extremum (minimum or
4184 range = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search.
4186 Returns: The position of the minimum (respectively maximum) element of forward
4187 range `range`, i.e. a subrange of `range` starting at the position of its
4188 smallest (respectively largest) element and with the same ending as `range`.
4190 Limitations: If at least one of the arguments is NaN, the result is
4191 an unspecified value. See $(REF maxElement, std,algorithm,searching)
4192 for examples on how to cope with NaNs.
4195 $(REF max, std,algorithm,comparison), $(LREF minCount), $(LREF minIndex), $(LREF minElement)
4197 Range minPos(alias pred = "a < b", Range)(Range range)
4198 if (isForwardRange!Range && !isInfinite!Range &&
4199 is(typeof(binaryFun!pred(range.front, range.front))))
4201 static if (hasSlicing!Range && isRandomAccessRange!Range && hasLength!Range)
4203 // Prefer index-based access
4205 foreach (i; 1 .. range.length)
4207 if (binaryFun!pred(range[i], range[pos]))
4212 return range[pos .. range.length];
4216 auto result = range.save;
4217 if (range.empty) return result;
4218 for (range.popFront(); !range.empty; range.popFront())
4220 // Note: Unlike minCount, we do not care to find equivalence, so a
4221 // single pred call is enough.
4222 if (binaryFun!pred(range.front, result.front))
4225 result = range.save;
4233 Range maxPos(alias pred = "a < b", Range)(Range range)
4234 if (isForwardRange!Range && !isInfinite!Range &&
4235 is(typeof(binaryFun!pred(range.front, range.front))))
4237 return range.minPos!((a, b) => binaryFun!pred(b, a));
4243 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
4244 // Minimum is 1 and first occurs in position 3
4245 assert(a.minPos == [ 1, 2, 4, 1, 1, 2 ]);
4246 // Maximum is 4 and first occurs in position 2
4247 assert(a.maxPos == [ 4, 1, 2, 4, 1, 1, 2 ]);
4252 import std.algorithm.comparison : equal;
4253 import std.internal.test.dummyrange;
4255 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
4256 //Test that an empty range works
4258 assert(equal(minPos(b), b));
4260 //test with reference range.
4261 assert( equal( minPos(new ReferenceForwardRange!int([1, 2, 1, 0, 2, 0])), [0, 2, 0] ) );
4267 import std.algorithm.comparison : equal;
4268 import std.container : Array;
4270 assert(Array!int(2, 3, 4, 1, 2, 4, 1, 1, 2)
4273 .equal([ 1, 2, 4, 1, 1, 2 ]));
4279 immutable a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
4280 // Minimum is 1 and first occurs in position 3
4281 assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]);
4282 // Maximum is 4 and first occurs in position 5
4283 assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]);
4285 immutable(int[])[] b = [ [4], [2, 4], [4], [4] ];
4286 assert(minPos!("a[0] < b[0]")(b) == [ [2, 4], [4], [4] ]);
4290 Computes the index of the first occurrence of `range`'s minimum element.
4293 pred = The ordering predicate to use to determine the minimum element.
4294 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
4297 Complexity: $(BIGOH range.length)
4298 Exactly `range.length - 1` comparisons are needed.
4301 The index of the first encounter of the minimum element in `range`. If the
4302 `range` is empty, -1 is returned.
4305 If at least one of the arguments is NaN, the result is
4306 an unspecified value. See $(REF maxElement, std,algorithm,searching)
4307 for examples on how to cope with NaNs.
4310 $(LREF maxIndex), $(REF min, std,algorithm,comparison), $(LREF minCount), $(LREF minElement), $(LREF minPos)
4312 ptrdiff_t minIndex(alias pred = "a < b", Range)(Range range)
4313 if (isInputRange!Range && !isInfinite!Range &&
4314 is(typeof(binaryFun!pred(range.front, range.front))))
4316 if (range.empty) return -1;
4318 ptrdiff_t minPos = 0;
4320 static if (isRandomAccessRange!Range && hasLength!Range)
4322 foreach (i; 1 .. range.length)
4324 if (binaryFun!pred(range[i], range[minPos]))
4332 ptrdiff_t curPos = 0;
4333 Unqual!(typeof(range.front)) min = range.front;
4334 for (range.popFront(); !range.empty; range.popFront())
4337 if (binaryFun!pred(range.front, min))
4348 @safe pure nothrow unittest
4350 int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2];
4352 // Minimum is 1 and first occurs in position 3
4353 assert(a.minIndex == 3);
4354 // Get maximum index with minIndex
4355 assert(a.minIndex!"a > b" == 2);
4357 // Range is empty, so return value is -1
4359 assert(b.minIndex == -1);
4361 // Works with more custom types
4362 struct Dog { int age; }
4363 Dog[] dogs = [Dog(10), Dog(5), Dog(15)];
4364 assert(dogs.minIndex!"a.age < b.age" == 1);
4369 // should work with const
4370 const(int)[] immArr = [2, 1, 3];
4371 assert(immArr.minIndex == 1);
4373 // Works for const ranges too
4374 const int[] c = [2, 5, 4, 1, 2, 3];
4375 assert(c.minIndex == 3);
4377 // should work with immutable
4378 immutable(int)[] immArr2 = [2, 1, 3];
4379 assert(immArr2.minIndex == 1);
4382 assert(["b", "a", "c"].minIndex == 1);
4385 import std.range : cycle;
4386 static assert(!__traits(compiles, cycle([1]).minIndex));
4388 // with all dummy ranges
4389 import std.internal.test.dummyrange : AllDummyRanges;
4390 foreach (DummyType; AllDummyRanges)
4392 static if (isForwardRange!DummyType && !isInfinite!DummyType)
4395 d.arr = [5, 3, 7, 2, 1, 4];
4396 assert(d.minIndex == 4);
4399 assert(d.minIndex == -1);
4404 @nogc @safe nothrow pure unittest
4406 static immutable arr = [7, 3, 8, 2, 1, 4];
4407 assert(arr.minIndex == 4);
4409 static immutable arr2d = [[1, 3], [3, 9], [4, 2]];
4410 assert(arr2d.minIndex!"a[1] < b[1]" == 2);
4413 @safe nothrow pure unittest
4417 static struct InRange
4419 @property int front()
4426 return arr.length == index;
4438 static assert(isInputRange!InRange);
4440 auto arr1 = InRange([5, 2, 3, 4, 5, 3, 6]);
4441 auto arr2 = InRange([7, 3, 8, 2, 1, 4]);
4443 assert(arr1.minIndex == 1);
4444 assert(arr2.minIndex == 4);
4448 Computes the index of the first occurrence of `range`'s maximum element.
4450 Complexity: $(BIGOH range)
4451 Exactly `range.length - 1` comparisons are needed.
4454 pred = The ordering predicate to use to determine the maximum element.
4455 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to search.
4458 The index of the first encounter of the maximum in `range`. If the
4459 `range` is empty, -1 is returned.
4462 If at least one of the arguments is NaN, the result is
4463 an unspecified value. See $(REF maxElement, std,algorithm,searching)
4464 for examples on how to cope with NaNs.
4467 $(LREF minIndex), $(REF max, std,algorithm,comparison), $(LREF maxCount), $(LREF maxElement), $(LREF maxPos)
4469 ptrdiff_t maxIndex(alias pred = "a < b", Range)(Range range)
4470 if (isInputRange!Range && !isInfinite!Range &&
4471 is(typeof(binaryFun!pred(range.front, range.front))))
4473 return range.minIndex!((a, b) => binaryFun!pred(b, a));
4477 @safe pure nothrow unittest
4479 // Maximum is 4 and first occurs in position 2
4480 int[] a = [2, 3, 4, 1, 2, 4, 1, 1, 2];
4481 assert(a.maxIndex == 2);
4485 assert(b.maxIndex == -1);
4487 // Works with more custom types
4488 struct Dog { int age; }
4489 Dog[] dogs = [Dog(10), Dog(15), Dog(5)];
4490 assert(dogs.maxIndex!"a.age < b.age" == 1);
4495 // should work with const
4496 const(int)[] immArr = [5, 1, 3];
4497 assert(immArr.maxIndex == 0);
4499 // Works for const ranges too
4500 const int[] c = [2, 5, 4, 1, 2, 3];
4501 assert(c.maxIndex == 1);
4504 // should work with immutable
4505 immutable(int)[] immArr2 = [2, 1, 3];
4506 assert(immArr2.maxIndex == 2);
4509 assert(["b", "a", "c"].maxIndex == 2);
4512 import std.range : cycle;
4513 static assert(!__traits(compiles, cycle([1]).maxIndex));
4515 // with all dummy ranges
4516 import std.internal.test.dummyrange : AllDummyRanges;
4517 foreach (DummyType; AllDummyRanges)
4519 static if (isForwardRange!DummyType && !isInfinite!DummyType)
4523 d.arr = [5, 3, 7, 2, 1, 4];
4524 assert(d.maxIndex == 2);
4527 assert(d.maxIndex == -1);
4532 @nogc @safe nothrow pure unittest
4534 static immutable arr = [7, 3, 8, 2, 1, 4];
4535 assert(arr.maxIndex == 2);
4537 static immutable arr2d = [[1, 3], [3, 9], [4, 2]];
4538 assert(arr2d.maxIndex!"a[1] < b[1]" == 1);
4542 Skip over the initial portion of the first given range (`haystack`) that matches
4543 any of the additionally given ranges (`needles`) fully, or
4544 if no second range is given skip over the elements that fulfill pred.
4545 Do nothing if there is no match.
4548 pred = The predicate that determines whether elements from each respective
4549 range match. Defaults to equality `"a == b"`.
4551 template skipOver(alias pred = (a, b) => a == b)
4553 enum bool isPredComparable(T) = ifTestable!(T, binaryFun!pred);
4557 haystack = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to
4559 needles = The $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives)
4560 representing the prefix of `r1` to skip over.
4561 es = The element to match.
4564 `true` if the prefix of `haystack` matches any range of `needles` fully
4565 or `pred` evaluates to true, and `haystack` has been advanced to the point past this segment;
4566 otherwise false, and `haystack` is left in its original position.
4569 By definition, empty ranges are matched fully and if `needles` contains an empty range,
4570 `skipOver` will return `true`.
4572 bool skipOver(Haystack, Needles...)(ref Haystack haystack, Needles needles)
4573 if (is(typeof(binaryFun!pred(haystack.front, needles[0].front))) &&
4574 isForwardRange!Haystack &&
4575 allSatisfy!(isInputRange, Needles) &&
4576 !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Needles))) == void))
4578 static if (__traits(isSame, pred, (a, b) => a == b)
4579 && is(typeof(haystack[0 .. $] == needles[0]) : bool)
4580 && is(typeof(haystack = haystack[0 .. $]))
4581 && hasLength!Haystack && allSatisfy!(hasLength, Needles))
4583 ptrdiff_t longestMatch = -1;
4584 static foreach (r2; needles)
4586 if (r2.length <= haystack.length && longestMatch < ptrdiff_t(r2.length)
4587 && (haystack[0 .. r2.length] == r2 || r2.length == 0))
4588 longestMatch = r2.length;
4590 if (longestMatch >= 0)
4592 if (longestMatch > 0)
4593 haystack = haystack[longestMatch .. $];
4601 import std.algorithm.comparison : min;
4602 auto r = haystack.save;
4604 static if (hasLength!Haystack && allSatisfy!(hasLength, Needles))
4606 import std.algorithm.iteration : map;
4607 import std.algorithm.searching : minElement;
4608 import std.range : only;
4609 // Shortcut opportunity!
4610 if (needles.only.map!(a => a.length).minElement > haystack.length)
4614 // compatibility: return true if any range was empty
4615 bool hasEmptyRanges;
4616 static foreach (i, r2; needles)
4619 hasEmptyRanges = true;
4622 bool hasNeedleMatch;
4623 size_t inactiveNeedlesLen;
4624 bool[Needles.length] inactiveNeedles;
4625 for (; !r.empty; r.popFront)
4627 static foreach (i, r2; needles)
4629 if (!r2.empty && !inactiveNeedles[i])
4631 if (binaryFun!pred(r.front, r2.front))
4636 // we skipped over a new match
4637 hasNeedleMatch = true;
4638 inactiveNeedlesLen++;
4639 // skip over haystack
4645 inactiveNeedles[i] = true;
4646 inactiveNeedlesLen++;
4652 if (inactiveNeedlesLen == needles.length)
4659 return hasNeedleMatch || hasEmptyRanges;
4664 bool skipOver(R)(ref R r1)
4665 if (isForwardRange!R &&
4666 ifTestable!(typeof(r1.front), unaryFun!pred))
4668 if (r1.empty || !unaryFun!pred(r1.front))
4673 while (!r1.empty && unaryFun!pred(r1.front));
4678 bool skipOver(R, Es...)(ref R r, Es es)
4679 if (isInputRange!R && is(typeof(binaryFun!pred(r.front, es[0]))))
4684 static foreach (e; es)
4686 if (binaryFun!pred(r.front, e))
4699 import std.algorithm.comparison : equal;
4701 auto s1 = "Hello world";
4702 assert(!skipOver(s1, "Ha"));
4703 assert(s1 == "Hello world");
4704 assert(skipOver(s1, "Hell") && s1 == "o world", s1);
4706 string[] r1 = ["abc", "def", "hij"];
4707 dstring[] r2 = ["abc"d];
4708 assert(!skipOver!((a, b) => a.equal(b))(r1, ["def"d]), r1[0]);
4709 assert(r1 == ["abc", "def", "hij"]);
4710 assert(skipOver!((a, b) => a.equal(b))(r1, r2));
4711 assert(r1 == ["def", "hij"]);
4717 import std.ascii : isWhite;
4718 import std.range.primitives : empty;
4720 auto s2 = "\t\tvalue";
4723 assert(s2.skipOver!isWhite && s2 == "value");
4724 assert(!s3.skipOver!isWhite);
4725 assert(s4.skipOver!isWhite && s3.empty);
4728 /// Variadic skipOver
4731 auto s = "Hello world";
4732 assert(!skipOver(s, "hello", "HellO"));
4733 assert(s == "Hello world");
4735 // the range is skipped over the longest matching needle is skipped
4736 assert(skipOver(s, "foo", "hell", "Hello "));
4737 assert(s == "world");
4743 import std.algorithm.comparison : equal;
4745 auto s1 = "Hello world";
4746 assert(!skipOver(s1, 'a'));
4747 assert(s1 == "Hello world");
4748 assert(skipOver(s1, 'H') && s1 == "ello world");
4750 string[] r = ["abc", "def", "hij"];
4752 assert(!skipOver!((a, b) => a.equal(b))(r, "def"d));
4753 assert(r == ["abc", "def", "hij"]);
4754 assert(skipOver!((a, b) => a.equal(b))(r, e));
4755 assert(r == ["def", "hij"]);
4758 assert(!s2.skipOver('a'));
4761 /// Partial instantiation
4764 import std.ascii : isWhite;
4765 import std.range.primitives : empty;
4767 alias whitespaceSkiper = skipOver!isWhite;
4769 auto s2 = "\t\tvalue";
4772 assert(whitespaceSkiper(s2) && s2 == "value");
4773 assert(!whitespaceSkiper(s2));
4774 assert(whitespaceSkiper(s4) && s3.empty);
4777 // variadic skipOver
4780 auto s = "DLang.rocks";
4781 assert(!s.skipOver("dlang", "DLF", "DLang "));
4782 assert(s == "DLang.rocks");
4784 assert(s.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLanpp"));
4785 assert(s == "ang.rocks");
4788 assert(s.skipOver("DLang", "DLANG", "DLF", "D", "DL", "DLang "));
4789 assert(s == ".rocks");
4792 assert(s.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLang."));
4793 assert(s == "rocks");
4796 // variadic with custom pred
4799 import std.ascii : toLower;
4801 auto s = "DLang.rocks";
4802 assert(!s.skipOver("dlang", "DLF", "DLang "));
4803 assert(s == "DLang.rocks");
4805 assert(s.skipOver!((a, b) => a.toLower == b.toLower)("dlang", "DLF", "DLang "));
4806 assert(s == ".rocks");
4809 // variadic skipOver with mixed needles
4812 auto s = "DLang.rocks";
4813 assert(!s.skipOver("dlang"d, "DLF", "DLang "w));
4814 assert(s == "DLang.rocks");
4816 assert(s.skipOver("dlang", "DLANG"d, "DLF"w, "D"d, "DL", "DLanp"));
4817 assert(s == "ang.rocks");
4820 assert(s.skipOver("DLang", "DLANG"w, "DLF"d, "D"d, "DL", "DLang "));
4821 assert(s == ".rocks");
4824 assert(s.skipOver("dlang", "DLANG"w, "DLF", "D"d, "DL"w, "DLang."d));
4825 assert(s == "rocks");
4827 import std.algorithm.iteration : filter;
4829 assert(s.skipOver("dlang", "DLang".filter!(a => true)));
4830 assert(s == ".rocks");
4833 // variadic skipOver with auto-decoding
4837 assert(s.skipOver("a", "☢", "☢☣☠"));
4841 // skipOver with @nogc
4842 @safe @nogc pure nothrow unittest
4844 static immutable s = [0, 1, 2];
4845 immutable(int)[] s2 = s[];
4847 static immutable skip1 = [0, 2];
4848 static immutable skip2 = [0, 1];
4849 assert(s2.skipOver(skip1, skip2));
4850 assert(s2 == s[2 .. $]);
4853 // variadic skipOver with single elements
4856 auto s = "DLang.rocks";
4857 assert(!s.skipOver('a', 'd', 'e'));
4858 assert(s == "DLang.rocks");
4860 assert(s.skipOver('a', 'D', 'd', 'D'));
4861 assert(s == "Lang.rocks");
4864 assert(s.skipOver(wchar('a'), dchar('D'), 'd'));
4865 assert(s == "Lang.rocks");
4867 dstring dstr = "+Foo";
4868 assert(!dstr.skipOver('.', '-'));
4869 assert(dstr == "+Foo");
4871 assert(dstr.skipOver('+', '-'));
4872 assert(dstr == "Foo");
4875 // skipOver with empty ranges must return true (compatibility)
4878 auto s = "DLang.rocks";
4879 assert(s.skipOver(""));
4880 assert(s.skipOver("", ""));
4881 assert(s.skipOver("", "foo"));
4883 auto s2 = "DLang.rocks"d;
4884 assert(s2.skipOver(""));
4885 assert(s2.skipOver("", ""));
4886 assert(s2.skipOver("", "foo"));
4892 import std.utf : byCodeUnit;
4893 import std.algorithm.comparison : equal;
4895 bool stripStartsWith(Text)(ref Text text, string needle)
4897 return text.skipOver(needle.byCodeUnit());
4899 auto text = "<xml></xml>"d.byCodeUnit;
4900 assert(stripStartsWith(text, "<xml>"));
4901 assert(text.equal("</xml>"));
4905 Checks whether the given
4906 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) starts with (one
4907 of) the given needle(s) or, if no needles are given,
4908 if its front element fulfils predicate `pred`.
4910 For more information about `pred` see $(LREF find).
4914 pred = Predicate to use in comparing the elements of the haystack and the
4915 needle(s). Mandatory if no needles are given.
4917 doesThisStart = The input range to check.
4919 withOneOfThese = The needles against which the range is to be checked,
4920 which may be individual elements or input ranges of elements.
4922 withThis = The single needle to check, which may be either a single element
4923 or an input range of elements.
4927 0 if the needle(s) do not occur at the beginning of the given range;
4928 otherwise the position of the matching needle, that is, 1 if the range starts
4929 with `withOneOfThese[0]`, 2 if it starts with `withOneOfThese[1]`, and so
4932 In the case where `doesThisStart` starts with multiple of the ranges or
4933 elements in `withOneOfThese`, then the shortest one matches (if there are
4934 two which match which are of the same length (e.g. `"a"` and `'a'`), then
4935 the left-most of them in the argument
4938 In the case when no needle parameters are given, return `true` iff front of
4939 `doesThisStart` fulfils predicate `pred`.
4941 uint startsWith(alias pred = (a, b) => a == b, Range, Needles...)(Range doesThisStart, Needles withOneOfThese)
4942 if (isInputRange!Range && Needles.length > 1 &&
4943 allSatisfy!(canTestStartsWith!(pred, Range), Needles))
4945 template checkType(T)
4947 enum checkType = is(immutable ElementEncodingType!Range == immutable T);
4950 // auto-decoding special case
4951 static if (__traits(isSame, binaryFun!pred, (a, b) => a == b) &&
4952 isNarrowString!Range && allSatisfy!(checkType, Needles))
4954 import std.utf : byCodeUnit;
4955 auto haystack = doesThisStart.byCodeUnit;
4959 alias haystack = doesThisStart;
4961 alias needles = withOneOfThese;
4963 // Make one pass looking for empty ranges in needles
4964 foreach (i, Unused; Needles)
4966 // Empty range matches everything
4967 static if (!is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool))
4969 if (needles[i].empty) return i + 1;
4973 for (; !haystack.empty; haystack.popFront())
4975 foreach (i, Unused; Needles)
4977 static if (is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool))
4980 if (binaryFun!pred(haystack.front, needles[i]))
4982 // found, but instead of returning, we just stop searching.
4983 // This is to account for one-element
4984 // range matches (consider startsWith("ab", "a",
4985 // 'a') should return 1, not 2).
4991 if (binaryFun!pred(haystack.front, needles[i].front))
4997 // This code executed on failure to match
4998 // Out with this guy, check for the others
4999 uint result = startsWith!pred(haystack, needles[0 .. i], needles[i + 1 .. $]);
5000 if (result > i) ++result;
5004 // If execution reaches this point, then the front matches for all
5005 // needle ranges, or a needle element has been matched.
5006 // What we need to do now is iterate, lopping off the front of
5007 // the range and checking if the result is empty, or finding an
5008 // element needle and returning.
5009 // If neither happens, we drop to the end and loop.
5010 foreach (i, Unused; Needles)
5012 static if (is(typeof(binaryFun!pred(haystack.front, needles[i])) : bool))
5014 // Test has passed in the previous loop
5019 needles[i].popFront();
5020 if (needles[i].empty) return i + 1;
5028 bool startsWith(alias pred = "a == b", R1, R2)(R1 doesThisStart, R2 withThis)
5029 if (isInputRange!R1 &&
5031 is(typeof(binaryFun!pred(doesThisStart.front, withThis.front)) : bool))
5033 alias haystack = doesThisStart;
5034 alias needle = withThis;
5036 static if (is(typeof(pred) : string))
5037 enum isDefaultPred = pred == "a == b";
5039 enum isDefaultPred = false;
5041 // Note: Although narrow strings don't have a "true" length, for a narrow string to start with another
5042 // narrow string, it must have *at least* as many code units.
5043 static if ((hasLength!R1 && hasLength!R2) ||
5044 ((hasLength!R1 || isNarrowString!R1) && (hasLength!R2 || isNarrowString!R2)
5045 && (ElementEncodingType!R1.sizeof <= ElementEncodingType!R2.sizeof)))
5047 if (haystack.length < needle.length)
5051 static if (isDefaultPred && isArray!R1 && isArray!R2 &&
5052 is(immutable ElementEncodingType!R1 == immutable ElementEncodingType!R2))
5054 //Array slice comparison mode
5055 return haystack[0 .. needle.length] == needle;
5057 else static if (isRandomAccessRange!R1 && isRandomAccessRange!R2 && hasLength!R2)
5059 //RA dual indexing mode
5060 foreach (j; 0 .. needle.length)
5062 if (!binaryFun!pred(haystack[j], needle[j]))
5071 //Standard input range mode
5072 if (needle.empty) return true;
5073 static if (hasLength!R1 && hasLength!R2)
5075 //We have previously checked that haystack.length > needle.length,
5076 //So no need to check haystack.empty during iteration
5077 for ( ; ; haystack.popFront() )
5079 if (!binaryFun!pred(haystack.front, needle.front)) break;
5081 if (needle.empty) return true;
5086 for ( ; !haystack.empty ; haystack.popFront() )
5088 if (!binaryFun!pred(haystack.front, needle.front)) break;
5090 if (needle.empty) return true;
5098 bool startsWith(alias pred = "a == b", R, E)(R doesThisStart, E withThis)
5099 if (isInputRange!R &&
5100 is(typeof(binaryFun!pred(doesThisStart.front, withThis)) : bool))
5102 if (doesThisStart.empty)
5105 static if (is(typeof(pred) : string))
5106 enum isDefaultPred = pred == "a == b";
5108 enum isDefaultPred = false;
5110 alias predFunc = binaryFun!pred;
5112 // auto-decoding special case
5113 static if (isNarrowString!R)
5115 // statically determine decoding is unnecessary to evaluate pred
5116 static if (isDefaultPred && isSomeChar!E && E.sizeof <= ElementEncodingType!R.sizeof)
5117 return doesThisStart[0] == withThis;
5118 // specialize for ASCII as to not change previous behavior
5121 if (withThis <= 0x7F)
5122 return predFunc(doesThisStart[0], withThis);
5124 return predFunc(doesThisStart.front, withThis);
5129 return predFunc(doesThisStart.front, withThis);
5134 bool startsWith(alias pred, R)(R doesThisStart)
5135 if (isInputRange!R &&
5136 ifTestable!(typeof(doesThisStart.front), unaryFun!pred))
5138 return !doesThisStart.empty && unaryFun!pred(doesThisStart.front);
5144 import std.ascii : isAlpha;
5146 assert("abc".startsWith!(a => a.isAlpha));
5147 assert("abc".startsWith!isAlpha);
5148 assert(!"1ab".startsWith!(a => a.isAlpha));
5149 assert(!"".startsWith!(a => a.isAlpha));
5151 import std.algorithm.comparison : among;
5152 assert("abc".startsWith!(a => a.among('a', 'b') != 0));
5153 assert(!"abc".startsWith!(a => a.among('b', 'c') != 0));
5155 assert(startsWith("abc", ""));
5156 assert(startsWith("abc", "a"));
5157 assert(!startsWith("abc", "b"));
5158 assert(startsWith("abc", 'a', "b") == 1);
5159 assert(startsWith("abc", "b", "a") == 2);
5160 assert(startsWith("abc", "a", "a") == 1);
5161 assert(startsWith("abc", "ab", "a") == 2);
5162 assert(startsWith("abc", "x", "a", "b") == 2);
5163 assert(startsWith("abc", "x", "aa", "ab") == 3);
5164 assert(startsWith("abc", "x", "aaa", "sab") == 0);
5165 assert(startsWith("abc", "x", "aaa", "a", "sab") == 3);
5167 import std.typecons : Tuple;
5168 alias C = Tuple!(int, "x", int, "y");
5169 assert(startsWith!"a.x == b"([ C(1,1), C(1,2), C(2,2) ], [1, 1]));
5170 assert(startsWith!"a.x == b"([ C(1,1), C(2,1), C(2,2) ], [1, 1], [1, 2], [1, 3]) == 2);
5175 import std.algorithm.iteration : filter;
5176 import std.conv : to;
5177 import std.meta : AliasSeq;
5180 static foreach (S; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
5181 (){ // workaround slow optimizations for large functions
5182 // https://issues.dlang.org/show_bug.cgi?id=2396
5183 assert(!startsWith(to!S("abc"), 'c'));
5184 assert(startsWith(to!S("abc"), 'a', 'c') == 1);
5185 assert(!startsWith(to!S("abc"), 'x', 'n', 'b'));
5186 assert(startsWith(to!S("abc"), 'x', 'n', 'a') == 3);
5187 assert(startsWith(to!S("\uFF28abc"), 'a', '\uFF28', 'c') == 2);
5189 static foreach (T; AliasSeq!(char[], wchar[], dchar[], string, wstring, dstring))
5192 assert(startsWith(to!S("abc"), to!T("")));
5193 assert(startsWith(to!S("ab"), to!T("a")));
5194 assert(startsWith(to!S("abc"), to!T("a")));
5195 assert(!startsWith(to!S("abc"), to!T("b")));
5196 assert(!startsWith(to!S("abc"), to!T("b"), "bc", "abcd", "xyz"));
5197 assert(startsWith(to!S("abc"), to!T("ab"), 'a') == 2);
5198 assert(startsWith(to!S("abc"), to!T("a"), "b") == 1);
5199 assert(startsWith(to!S("abc"), to!T("b"), "a") == 2);
5200 assert(startsWith(to!S("abc"), to!T("a"), 'a') == 1);
5201 assert(startsWith(to!S("abc"), 'a', to!T("a")) == 1);
5202 assert(startsWith(to!S("abc"), to!T("x"), "a", "b") == 2);
5203 assert(startsWith(to!S("abc"), to!T("x"), "aa", "ab") == 3);
5204 assert(startsWith(to!S("abc"), to!T("x"), "aaa", "sab") == 0);
5205 assert(startsWith(to!S("abc"), 'a'));
5206 assert(!startsWith(to!S("abc"), to!T("sab")));
5207 assert(startsWith(to!S("abc"), 'x', to!T("aaa"), 'a', "sab") == 3);
5210 assert(startsWith(to!S("\uFF28el\uFF4co"), to!T("\uFF28el")));
5211 assert(startsWith(to!S("\uFF28el\uFF4co"), to!T("Hel"), to!T("\uFF28el")) == 2);
5212 assert(startsWith(to!S("日本語"), to!T("日本")));
5213 assert(startsWith(to!S("日本語"), to!T("日本語")));
5214 assert(!startsWith(to!S("日本"), to!T("日本語")));
5217 assert(startsWith(to!S(""), T.init));
5218 assert(!startsWith(to!S(""), 'a'));
5219 assert(startsWith(to!S("a"), T.init));
5220 assert(startsWith(to!S("a"), T.init, "") == 1);
5221 assert(startsWith(to!S("a"), T.init, 'a') == 1);
5222 assert(startsWith(to!S("a"), 'a', T.init) == 2);
5227 assert(!startsWith("abc".takeExactly(3), "abcd".takeExactly(4)));
5228 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(3)));
5229 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(1)));
5231 static foreach (T; AliasSeq!(int, short))
5233 immutable arr = cast(T[])[0, 1, 2, 3, 4, 5];
5236 assert(startsWith(arr, cast(int[]) null));
5237 assert(!startsWith(arr, 5));
5238 assert(!startsWith(arr, 1));
5239 assert(startsWith(arr, 0));
5240 assert(startsWith(arr, 5, 0, 1) == 2);
5241 assert(startsWith(arr, [0]));
5242 assert(startsWith(arr, [0, 1]));
5243 assert(startsWith(arr, [0, 1], 7) == 1);
5244 assert(!startsWith(arr, [0, 1, 7]));
5245 assert(startsWith(arr, [0, 1, 7], [0, 1, 2]) == 2);
5247 //Normal input range
5248 assert(!startsWith(filter!"true"(arr), 1));
5249 assert(startsWith(filter!"true"(arr), 0));
5250 assert(startsWith(filter!"true"(arr), [0]));
5251 assert(startsWith(filter!"true"(arr), [0, 1]));
5252 assert(startsWith(filter!"true"(arr), [0, 1], 7) == 1);
5253 assert(!startsWith(filter!"true"(arr), [0, 1, 7]));
5254 assert(startsWith(filter!"true"(arr), [0, 1, 7], [0, 1, 2]) == 2);
5255 assert(startsWith(arr, filter!"true"([0, 1])));
5256 assert(startsWith(arr, filter!"true"([0, 1]), 7) == 1);
5257 assert(!startsWith(arr, filter!"true"([0, 1, 7])));
5258 assert(startsWith(arr, [0, 1, 7], filter!"true"([0, 1, 2])) == 2);
5261 assert(startsWith!("a%10 == b%10")(arr, [10, 11]));
5262 assert(!startsWith!("a%10 == b%10")(arr, [10, 12]));
5266 private template canTestStartsWith(alias pred, Haystack)
5268 enum bool canTestStartsWith(Needle) = is(typeof(
5269 (ref Haystack h, ref Needle n) => startsWith!pred(h, n)));
5272 /* (Not yet documented.)
5273 Consume all elements from `r` that are equal to one of the elements
5276 private void skipAll(alias pred = "a == b", R, Es...)(ref R r, Es es)
5277 //if (is(typeof(binaryFun!pred(r1.front, es[0]))))
5280 for (; !r.empty; r.popFront())
5284 if (binaryFun!pred(r.front, es[i]))
5295 auto s1 = "Hello world";
5296 skipAll(s1, 'H', 'e');
5297 assert(s1 == "llo world");
5301 Interval option specifier for `until` (below) and others.
5303 If set to `OpenRight.yes`, then the interval is open to the right
5304 (last element is not included).
5306 Otherwise if set to `OpenRight.no`, then the interval is closed to the right
5307 including the entire sentinel.
5309 alias OpenRight = Flag!"openRight";
5312 Lazily iterates `range` _until the element `e` for which
5313 `pred(e, sentinel)` is true.
5315 This is similar to `takeWhile` in other languages.
5318 pred = Predicate to determine when to stop.
5319 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
5321 sentinel = The element to stop at.
5322 openRight = Determines whether the element for which the given predicate is
5323 true should be included in the resulting range (`No.openRight`), or
5324 not (`Yes.openRight`).
5327 An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) that
5328 iterates over the original range's elements, but ends when the specified
5329 predicate becomes true. If the original range is a
5330 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) or
5331 higher, this range will be a forward range.
5333 Until!(pred, Range, Sentinel)
5334 until(alias pred = "a == b", Range, Sentinel)
5335 (Range range, Sentinel sentinel, OpenRight openRight = Yes.openRight)
5336 if (!is(Sentinel == OpenRight))
5338 return typeof(return)(range, sentinel, openRight);
5342 Until!(pred, Range, void)
5343 until(alias pred, Range)
5344 (Range range, OpenRight openRight = Yes.openRight)
5346 return typeof(return)(range, openRight);
5350 struct Until(alias pred, Range, Sentinel)
5351 if (isInputRange!Range)
5353 private Range _input;
5354 static if (!is(Sentinel == void))
5355 private Sentinel _sentinel;
5356 private OpenRight _openRight;
5357 private bool _matchStarted;
5360 static if (!is(Sentinel == void))
5363 this(Range input, Sentinel sentinel,
5364 OpenRight openRight = Yes.openRight)
5367 _sentinel = sentinel;
5368 _openRight = openRight;
5369 static if (isInputRange!Sentinel
5370 && is(immutable ElementEncodingType!Sentinel == immutable ElementEncodingType!Range))
5372 _matchStarted = predSatisfied();
5373 _done = _input.empty || _sentinel.empty || openRight && _matchStarted;
5374 if (_matchStarted && !_done && !openRight)
5381 _done = _input.empty || openRight && predSatisfied();
5384 private this(Range input, Sentinel sentinel, OpenRight openRight,
5388 _sentinel = sentinel;
5389 _openRight = openRight;
5396 this(Range input, OpenRight openRight = Yes.openRight)
5399 _openRight = openRight;
5400 _done = _input.empty || openRight && predSatisfied();
5402 private this(Range input, OpenRight openRight, bool done)
5405 _openRight = openRight;
5411 @property bool empty()
5417 @property auto ref front()
5419 assert(!empty, "Can not get the front of an empty Until");
5420 return _input.front;
5423 private bool predSatisfied()
5425 static if (is(Sentinel == void))
5426 return cast(bool) unaryFun!pred(_input.front);
5428 return cast(bool) startsWith!pred(_input, _sentinel);
5434 assert(!empty, "Can not popFront of an empty Until");
5437 static if (isInputRange!Sentinel
5438 && is(immutable ElementEncodingType!Sentinel == immutable ElementEncodingType!Range))
5441 _done = _input.empty || _sentinel.empty;
5450 _matchStarted = predSatisfied();
5460 _done = predSatisfied();
5462 _done = _done || _input.empty;
5468 _done = _input.empty || predSatisfied();
5472 static if (isForwardRange!Range)
5475 @property Until save()
5477 static if (is(Sentinel == void))
5478 return Until(_input.save, _openRight, _done);
5480 return Until(_input.save, _sentinel, _openRight, _done);
5488 import std.algorithm.comparison : equal;
5489 import std.typecons : No;
5490 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
5491 assert(equal(a.until(7), [1, 2, 4]));
5492 assert(equal(a.until(7, No.openRight), [1, 2, 4, 7]));
5497 import std.algorithm.comparison : equal;
5498 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
5500 static assert(isForwardRange!(typeof(a.until(7))));
5501 static assert(isForwardRange!(typeof(until!"a == 2"(a, No.openRight))));
5503 assert(equal(a.until(7), [1, 2, 4]));
5504 assert(equal(a.until([7, 2]), [1, 2, 4, 7]));
5505 assert(equal(a.until(7, No.openRight), [1, 2, 4, 7]));
5506 assert(equal(until!"a == 2"(a, No.openRight), [1, 2]));
5509 // https://issues.dlang.org/show_bug.cgi?id=13171
5512 import std.algorithm.comparison : equal;
5514 auto a = [1, 2, 3, 4];
5515 assert(equal(refRange(&a).until(3, No.openRight), [1, 2, 3]));
5519 // https://issues.dlang.org/show_bug.cgi?id=10460
5522 import std.algorithm.comparison : equal;
5523 auto a = [1, 2, 3, 4];
5524 foreach (ref e; a.until(3))
5526 assert(equal(a, [0, 0, 3, 4]));
5529 // https://issues.dlang.org/show_bug.cgi?id=13124
5532 import std.algorithm.comparison : among, equal;
5533 auto s = "hello how\nare you";
5534 assert(equal(s.until!(c => c.among!('\n', '\r')), "hello how"));
5537 // https://issues.dlang.org/show_bug.cgi?id=18657
5540 import std.algorithm.comparison : equal;
5541 import std.range : refRange;
5543 string s = "foobar";
5544 auto r = refRange(&s).until("bar");
5545 assert(equal(r.save, "foo"));
5546 assert(equal(r.save, "foo"));
5549 string s = "foobar";
5550 auto r = refRange(&s).until!(e => e == 'b');
5551 assert(equal(r.save, "foo"));
5552 assert(equal(r.save, "foo"));
5556 // https://issues.dlang.org/show_bug.cgi?id=14543
5559 import std.algorithm.comparison : equal;
5560 import std.uni : toUpper;
5561 assert("one two three".until("two").equal("one "));
5562 assert("one two three".until("two", OpenRight.no).equal("one two"));
5564 assert("one two three".until("two", No.openRight).equal("one two"));
5565 assert("one two three".until("two", Yes.openRight).equal("one "));
5567 assert("one two three".until('t', Yes.openRight).equal("one "));
5568 assert("one two three".until("", Yes.openRight).equal(""));
5569 assert("one two three".until("", No.openRight).equal(""));
5571 assert("one two three".until("three", No.openRight).equal("one two three"));
5572 assert("one two three".until("three", Yes.openRight).equal("one two "));
5574 assert("one two three".until("one", No.openRight).equal("one"));
5575 assert("one two three".until("one", Yes.openRight).equal(""));
5577 assert("one two three".until("o", No.openRight).equal("o"));
5578 assert("one two three".until("o", Yes.openRight).equal(""));
5580 assert("one two three".until("", No.openRight).equal(""));
5581 assert("one two three".until("", Yes.openRight).equal(""));
5583 assert("one two three".until!((a,b)=>a.toUpper == b)("TWO", No.openRight).equal("one two"));
5586 // https://issues.dlang.org/show_bug.cgi?id=24342
5589 import std.algorithm.comparison : equal;
5590 assert(["A", "BC", "D"].until("BC", No.openRight).equal(["A", "BC"]));
5591 assert([[1], [2, 3], [4]].until([2, 3], No.openRight).equal([[1], [2, 3]]));