1 // Written in the D programming language.
3 This is a submodule of $(MREF std, algorithm).
4 It contains generic searching algorithms.
6 $(SCRIPT inhibitQuickIndex = 1;)
7 $(BOOKTABLE Cheat Sheet,
8 $(TR $(TH Function Name) $(TH Description))
10 `all!"a > 0"([1, 2, 3, 4])` returns `true` because all elements
13 `any!"a > 0"([1, 2, -3, -4])` returns `true` because at least one
16 `balancedParens("((1 + 1) / 2)", '(', ')')` returns `true` because the
17 string has balanced parentheses.)
18 $(T2 boyerMooreFinder,
19 `find("hello world", boyerMooreFinder("or"))` returns `"orld"`
20 using the $(LINK2 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm,
21 Boyer-Moore _algorithm).)
23 `canFind("hello world", "or")` returns `true`.)
25 Counts elements that are equal to a specified value or satisfy a
26 predicate. `count([1, 2, 1], 1)` returns `2` and
27 `count!"a < 0"([1, -3, 0])` returns `1`.)
29 `countUntil(a, b)` returns the number of steps taken in `a` to
30 reach `b`; for example, `countUntil("hello!", "o")` returns
33 `commonPrefix("parakeet", "parachute")` returns `"para"`.)
35 `endsWith("rocks", "ks")` returns `true`.)
37 `find("hello world", "or")` returns `"orld"` using linear search.
38 (For binary search refer to $(REF SortedRange, std,range).))
40 `findAdjacent([1, 2, 3, 3, 4])` returns the subrange starting with
41 two equal adjacent elements, i.e. `[3, 3, 4]`.)
43 `findAmong("abcd", "qcx")` returns `"cd"` because `'c'` is
46 If `a = "abcde"`, then `findSkip(a, "x")` returns `false` and
47 leaves `a` unchanged, whereas `findSkip(a, "c")` advances `a`
48 to `"de"` and returns `true`.)
50 `findSplit("abcdefg", "de")` returns a tuple of three ranges `"abc"`,
53 `findSplitAfter("abcdefg", "de")` returns a tuple of two ranges `"abcde"`
56 `findSplitBefore("abcdefg", "de")` returns a tuple of two ranges `"abc"`
59 `minCount([2, 1, 1, 4, 1])` returns `tuple(1, 3)`.)
61 `maxCount([2, 4, 1, 4, 1])` returns `tuple(4, 2)`.)
63 Selects the minimal element of a range.
64 `minElement([3, 4, 1, 2])` returns `1`.)
66 Selects the maximal element of a range.
67 `maxElement([3, 4, 1, 2])` returns `4`.)
69 Index of the minimal element of a range.
70 `minIndex([3, 4, 1, 2])` returns `2`.)
72 Index of the maximal element of a range.
73 `maxIndex([3, 4, 1, 2])` returns `1`.)
75 `minPos([2, 3, 1, 3, 4, 1])` returns the subrange `[1, 3, 4, 1]`,
76 i.e., positions the range at the first occurrence of its minimal
79 `maxPos([2, 3, 1, 3, 4, 1])` returns the subrange `[4, 1]`,
80 i.e., positions the range at the first occurrence of its maximal
83 Assume `a = "blah"`. Then `skipOver(a, "bi")` leaves `a`
84 unchanged and returns `false`, whereas `skipOver(a, "bl")`
85 advances `a` to refer to `"ah"` and returns `true`.)
87 `startsWith("hello, world", "hello")` returns `true`.)
89 Lazily iterates a range until a specific value is found.)
92 Copyright: Andrei Alexandrescu 2008-.
94 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
96 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
98 Source: $(PHOBOSSRC std/algorithm/searching.d)
101 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
103 module std
.algorithm
.searching
;
105 import std
.functional
: unaryFun
, binaryFun
;
106 import std
.meta
: allSatisfy
;
107 import std
.range
.primitives
;
109 import std
.typecons
: Tuple
, Flag
, Yes
, No
, tuple
;
112 Checks if $(I _all) of the elements satisfy `pred`.
114 template all(alias pred
= "a")
117 Returns `true` if and only if the input range `range` is empty
118 or $(I _all) values found in `range` satisfy the predicate `pred`.
119 Performs (at most) $(BIGOH range.length) evaluations of `pred`.
121 bool all(Range
)(Range range
)
122 if (isInputRange
!Range
&&
123 (__traits(isTemplate
, pred
) ||
is(typeof(unaryFun
!pred(range
.front
)))))
125 import std
.functional
: not;
127 return find
!(not!(unaryFun
!pred
))(range
).empty
;
134 assert( all
!"a & 1"([1, 3, 5, 7, 9]));
135 assert(!all
!"a & 1"([1, 2, 3, 5, 7, 9]));
139 `all` can also be used without a predicate, if its items can be
140 evaluated to true or false in a conditional statement. This can be a
141 convenient way to quickly evaluate that $(I _all) of the elements of a range
146 int[3] vals
= [5, 3, 18];
147 assert( all(vals
[]));
153 assert(all
!(a
=> a
> x
)([2, 3]));
154 assert(all
!"a == 0x00c9"("\xc3\x89")); // Test that `all` auto-decodes.
158 Checks if $(I _any) of the elements satisfies `pred`.
159 `!any` can be used to verify that $(I none) of the elements satisfy
161 This is sometimes called `exists` in other languages.
163 template any(alias pred
= "a")
166 Returns `true` if and only if the input range `range` is non-empty
167 and $(I _any) value found in `range` satisfies the predicate
169 Performs (at most) $(BIGOH range.length) evaluations of `pred`.
171 bool any(Range
)(Range range
)
172 if (isInputRange
!Range
&&
173 (__traits(isTemplate
, pred
) ||
is(typeof(unaryFun
!pred(range
.front
)))))
175 return !find
!pred(range
).empty
;
182 import std
.ascii
: isWhite
;
183 assert( all
!(any
!isWhite
)(["a a", "b b"]));
184 assert(!any
!(all
!isWhite
)(["a a", "b b"]));
188 `any` can also be used without a predicate, if its items can be
189 evaluated to true or false in a conditional statement. `!any` can be a
190 convenient way to quickly test that $(I none) of the elements of a range
195 int[3] vals1
= [0, 0, 0];
196 assert(!any(vals1
[])); //none of vals1 evaluate to true
198 int[3] vals2
= [2, 0, 2];
199 assert( any(vals2
[]));
200 assert(!all(vals2
[]));
202 int[3] vals3
= [3, 3, 3];
203 assert( any(vals3
[]));
204 assert( all(vals3
[]));
209 auto a
= [ 1, 2, 0, 4 ];
210 assert(any
!"a == 2"(a
));
211 assert(any
!"a == 0x3000"("\xe3\x80\x80")); // Test that `any` auto-decodes.
216 Checks whether `r` has "balanced parentheses", i.e. all instances
217 of `lPar` are closed by corresponding instances of `rPar`. The
218 parameter `maxNestingLevel` controls the nesting level allowed. The
219 most common uses are the default or `0`. In the latter case, no
223 r = The range to check.
224 lPar = The element corresponding with a left (opening) parenthesis.
225 rPar = The element corresponding with a right (closing) parenthesis.
226 maxNestingLevel = The maximum allowed nesting level.
229 true if the given range has balanced parenthesis within the given maximum
230 nesting level; false otherwise.
232 bool balancedParens(Range
, E
)(Range r
, E lPar
, E rPar
,
233 size_t maxNestingLevel
= size_t
.max
)
234 if (isInputRange
!(Range
) && is(typeof(r
.front
== lPar
)))
238 static if (is(immutable ElementEncodingType
!Range
== immutable E
) && isNarrowString
!Range
)
240 import std
.utf
: byCodeUnit
;
241 auto rn
= r
.byCodeUnit
;
248 for (; !rn
.empty
; rn
.popFront())
250 if (rn
.front
== lPar
)
252 if (count
> maxNestingLevel
) return false;
255 else if (rn
.front
== rPar
)
257 if (!count
) return false;
267 auto s
= "1 + (2 * (3 + 1 / 2)";
268 assert(!balancedParens(s
, '(', ')'));
269 s
= "1 + (2 * (3 + 1) / 2)";
270 assert(balancedParens(s
, '(', ')'));
271 s
= "1 + (2 * (3 + 1) / 2)";
272 assert(!balancedParens(s
, '(', ')', 0));
273 s
= "1 + (2 * 3 + 1) / (2 - 5)";
274 assert(balancedParens(s
, '(', ')', 0));
275 s
= "f(x) = ⌈x⌉";
276 assert(balancedParens(s
, '⌈', '⌉'));
280 * Sets up Boyer-Moore matching for use with `find` below.
281 * By default, elements are compared for equality.
283 * `BoyerMooreFinder` allocates GC memory.
286 * pred = Predicate used to compare elements.
287 * needle = A random-access range with length and slicing.
290 * An instance of `BoyerMooreFinder` that can be used with `find()` to
291 * invoke the Boyer-Moore matching algorithm for finding of `needle` in a
294 struct BoyerMooreFinder(alias pred
, Range
)
297 size_t
[] skip
; // GC allocated
298 ptrdiff_t
[ElementType
!(Range
)] occ
; // GC allocated
301 ptrdiff_t
occurrence(ElementType
!(Range
) c
) scope
308 This helper function checks whether the last "portion" bytes of
309 "needle" (which is "nlen" bytes long) exist within the "needle" at
310 offset "offset" (counted from the end of the string), and whether the
311 character preceding "offset" is not a match. Notice that the range
312 being checked may reach beyond the beginning of the string. Such range
315 static bool needlematch(R
)(R needle
,
316 size_t portion
, size_t offset
)
318 import std
.algorithm
.comparison
: equal
;
319 ptrdiff_t virtual_begin
= needle
.length
- offset
- portion
;
320 ptrdiff_t ignore
= 0;
321 if (virtual_begin
< 0)
323 ignore
= -virtual_begin
;
326 if (virtual_begin
> 0
327 && needle
[virtual_begin
- 1] == needle
[$ - portion
- 1])
330 immutable delta
= portion
- ignore
;
331 return equal(needle
[needle
.length
- delta
.. needle
.length
],
332 needle
[virtual_begin
.. virtual_begin
+ delta
]);
339 if (!needle
.length
) return;
340 this.needle
= needle
;
341 /* Populate table with the analysis of the needle */
342 /* But ignoring the last letter */
343 foreach (i
, n
; needle
[0 .. $ - 1])
347 /* Preprocess #2: init skip[] */
348 /* Note: This step could be made a lot faster.
349 * A simple implementation is shown here. */
350 this.skip
= new size_t
[needle
.length
];
351 foreach (a
; 0 .. needle
.length
)
354 while (value
< needle
.length
355 && !needlematch(needle
, a
, value
))
359 this.skip
[needle
.length
- a
- 1] = value
;
364 Range
beFound(Range haystack
) scope
366 import std
.algorithm
.comparison
: max
;
368 if (!needle
.length
) return haystack
;
369 if (needle
.length
> haystack
.length
) return haystack
[$ .. $];
371 immutable limit
= haystack
.length
- needle
.length
;
372 for (size_t hpos
= 0; hpos
<= limit
; )
374 size_t npos
= needle
.length
- 1;
375 while (pred(needle
[npos
], haystack
[npos
+hpos
]))
377 if (npos
== 0) return haystack
[hpos
.. $];
380 hpos
+= max(skip
[npos
], cast(ptrdiff_t
) npos
- occurrence(haystack
[npos
+hpos
]));
382 return haystack
[$ .. $];
386 @property size_t
length()
388 return needle
.length
;
392 alias opDollar
= length
;
396 BoyerMooreFinder
!(binaryFun
!(pred
), Range
) boyerMooreFinder
397 (alias pred
= "a == b", Range
)
399 if ((isRandomAccessRange
!(Range
) && hasSlicing
!Range
) || isSomeString
!Range
)
401 return typeof(return)(needle
);
405 @safe pure nothrow unittest
407 auto bmFinder
= boyerMooreFinder("TG");
409 string r
= "TAGTGCCTGA";
410 // search for the first match in the haystack r
411 r
= bmFinder
.beFound(r
);
412 assert(r
== "TGCCTGA");
414 // continue search in haystack
415 r
= bmFinder
.beFound(r
[2 .. $]);
420 Returns the common prefix of two ranges.
423 pred = The predicate to use in comparing elements for commonality. Defaults
424 to equality `"a == b"`.
426 r1 = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) of
429 r2 = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of
433 A slice of `r1` which contains the characters that both ranges start with,
434 if the first argument is a string; otherwise, the same as the result of
435 `takeExactly(r1, n)`, where `n` is the number of elements in the common
436 prefix of both ranges.
439 $(REF takeExactly, std,range)
441 auto commonPrefix(alias pred
= "a == b", R1
, R2
)(R1 r1
, R2 r2
)
442 if (isForwardRange
!R1
&& isInputRange
!R2
&&
443 !isNarrowString
!R1
&&
444 is(typeof(binaryFun
!pred(r1
.front
, r2
.front
))))
446 import std
.algorithm
.comparison
: min
;
447 static if (isRandomAccessRange
!R1
&& isRandomAccessRange
!R2
&&
448 hasLength
!R1
&& hasLength
!R2
&&
451 immutable limit
= min(r1
.length
, r2
.length
);
452 foreach (i
; 0 .. limit
)
454 if (!binaryFun
!pred(r1
[i
], r2
[i
]))
459 return r1
[0 .. limit
];
463 import std
.range
: takeExactly
;
464 auto result
= r1
.save
;
467 !r1
.empty
&& !r2
.empty
&& binaryFun
!pred(r1
.front
, r2
.front
);
468 ++i
, r1
.popFront(), r2
.popFront())
470 return takeExactly(result
, i
);
477 assert(commonPrefix("hello, world", "hello, there") == "hello, ");
481 auto commonPrefix(alias pred
, R1
, R2
)(R1 r1
, R2 r2
)
482 if (isNarrowString
!R1
&& isInputRange
!R2
&&
483 is(typeof(binaryFun
!pred(r1
.front
, r2
.front
))))
485 import std
.utf
: decode
;
487 auto result
= r1
.save
;
488 immutable len
= r1
.length
;
491 for (size_t j
= 0; i
< len
&& !r2
.empty
; r2
.popFront(), i
= j
)
493 immutable f
= decode(r1
, j
);
494 if (!binaryFun
!pred(f
, r2
.front
))
498 return result
[0 .. i
];
502 auto commonPrefix(R1
, R2
)(R1 r1
, R2 r2
)
503 if (isNarrowString
!R1
&& isInputRange
!R2
&& !isNarrowString
!R2
&&
504 is(typeof(r1
.front
== r2
.front
)))
506 return commonPrefix
!"a == b"(r1
, r2
);
510 auto commonPrefix(R1
, R2
)(R1 r1
, R2 r2
)
511 if (isNarrowString
!R1
&& isNarrowString
!R2
)
513 import std
.algorithm
.comparison
: min
;
515 static if (ElementEncodingType
!R1
.sizeof
== ElementEncodingType
!R2
.sizeof
)
517 import std
.utf
: stride
, UTFException
;
519 immutable limit
= min(r1
.length
, r2
.length
);
520 for (size_t i
= 0; i
< limit
;)
522 immutable codeLen
= stride(r1
, i
);
525 for (; j
< codeLen
&& i
< limit
; ++i
, ++j
)
528 return r1
[0 .. i
- j
];
531 if (i
== limit
&& j
< codeLen
)
532 throw new UTFException("Invalid UTF-8 sequence", i
);
534 return r1
[0 .. limit
];
537 return commonPrefix
!"a == b"(r1
, r2
);
542 import std
.algorithm
.comparison
: equal
;
543 import std
.algorithm
.iteration
: filter
;
544 import std
.conv
: to
;
545 import std
.exception
: assertThrown
;
546 import std
.meta
: AliasSeq
;
548 import std
.utf
: UTFException
;
550 assert(commonPrefix([1, 2, 3], [1, 2, 3, 4, 5]) == [1, 2, 3]);
551 assert(commonPrefix([1, 2, 3, 4, 5], [1, 2, 3]) == [1, 2, 3]);
552 assert(commonPrefix([1, 2, 3, 4], [1, 2, 3, 4]) == [1, 2, 3, 4]);
553 assert(commonPrefix([1, 2, 3], [7, 2, 3, 4, 5]).empty
);
554 assert(commonPrefix([7, 2, 3, 4, 5], [1, 2, 3]).empty
);
555 assert(commonPrefix([1, 2, 3], cast(int[]) null).empty
);
556 assert(commonPrefix(cast(int[]) null, [1, 2, 3]).empty
);
557 assert(commonPrefix(cast(int[]) null, cast(int[]) null).empty
);
559 static foreach (S
; AliasSeq
!(char[], const(char)[], string
,
560 wchar[], const(wchar)[], wstring
,
561 dchar[], const(dchar)[], dstring
))
563 static foreach (T
; AliasSeq
!(string
, wstring
, dstring
))
565 assert(commonPrefix(to
!S(""), to
!T("")).empty
);
566 assert(commonPrefix(to
!S(""), to
!T("hello")).empty
);
567 assert(commonPrefix(to
!S("hello"), to
!T("")).empty
);
568 assert(commonPrefix(to
!S("hello, world"), to
!T("hello, there")) == to
!S("hello, "));
569 assert(commonPrefix(to
!S("hello, there"), to
!T("hello, world")) == to
!S("hello, "));
570 assert(commonPrefix(to
!S("hello, "), to
!T("hello, world")) == to
!S("hello, "));
571 assert(commonPrefix(to
!S("hello, world"), to
!T("hello, ")) == to
!S("hello, "));
572 assert(commonPrefix(to
!S("hello, world"), to
!T("hello, world")) == to
!S("hello, world"));
574 // https://issues.dlang.org/show_bug.cgi?id=8890
575 assert(commonPrefix(to
!S("Пиво"), to
!T("Пони"))== to
!S("П"));
576 assert(commonPrefix(to
!S("Пони"), to
!T("Пиво"))== to
!S("П"));
577 assert(commonPrefix(to
!S("Пиво"), to
!T("Пиво"))== to
!S("Пиво"));
578 assert(commonPrefix(to
!S("\U0010FFFF\U0010FFFB\U0010FFFE"),
579 to
!T("\U0010FFFF\U0010FFFB\U0010FFFC")) == to
!S("\U0010FFFF\U0010FFFB"));
580 assert(commonPrefix(to
!S("\U0010FFFF\U0010FFFB\U0010FFFC"),
581 to
!T("\U0010FFFF\U0010FFFB\U0010FFFE")) == to
!S("\U0010FFFF\U0010FFFB"));
582 assert(commonPrefix
!"a != b"(to
!S("Пиво"), to
!T("онво")) == to
!S("Пи"));
583 assert(commonPrefix
!"a != b"(to
!S("онво"), to
!T("Пиво")) == to
!S("он"));
586 static assert(is(typeof(commonPrefix(to
!S("Пиво"), filter
!"true"("Пони"))) == S
));
587 assert(equal(commonPrefix(to
!S("Пиво"), filter
!"true"("Пони")), to
!S("П")));
589 static assert(is(typeof(commonPrefix(filter
!"true"("Пиво"), to
!S("Пони"))) ==
590 typeof(takeExactly(filter
!"true"("П"), 1))));
591 assert(equal(commonPrefix(filter
!"true"("Пиво"), to
!S("Пони")), takeExactly(filter
!"true"("П"), 1)));
594 assertThrown
!UTFException(commonPrefix("\U0010FFFF\U0010FFFB", "\U0010FFFF\U0010FFFB"[0 .. $ - 1]));
596 assert(commonPrefix("12345"d
, [49, 50, 51, 60, 60]) == "123"d
);
597 assert(commonPrefix([49, 50, 51, 60, 60], "12345" ) == [49, 50, 51]);
598 assert(commonPrefix([49, 50, 51, 60, 60], "12345"d
) == [49, 50, 51]);
600 assert(commonPrefix
!"a == ('0' + b)"("12345" , [1, 2, 3, 9, 9]) == "123");
601 assert(commonPrefix
!"a == ('0' + b)"("12345"d
, [1, 2, 3, 9, 9]) == "123"d
);
602 assert(commonPrefix
!"('0' + a) == b"([1, 2, 3, 9, 9], "12345" ) == [1, 2, 3]);
603 assert(commonPrefix
!"('0' + a) == b"([1, 2, 3, 9, 9], "12345"d
) == [1, 2, 3]);
608 The first version counts the number of elements `x` in `r` for
609 which `pred(x, value)` is `true`. `pred` defaults to
610 equality. Performs $(BIGOH haystack.length) evaluations of `pred`.
612 The second version returns the number of times `needle` occurs in
613 `haystack`. Throws an exception if `needle.empty`, as the _count
614 of the empty range in any range would be infinite. Overlapped counts
615 are not considered, for example `count("aaa", "aa")` is `1`, not
618 The third version counts the elements for which `pred(x)` is $(D
619 true). Performs $(BIGOH haystack.length) evaluations of `pred`.
621 The fourth version counts the number of elements in a range. It is
622 an optimization for the third version: if the given range has the
623 `length` property the count is returned right away, otherwise
624 performs $(BIGOH haystack.length) to walk the range.
626 Note: Regardless of the overload, `count` will not accept
627 infinite ranges for `haystack`.
630 pred = The predicate to evaluate.
631 haystack = The range to _count.
632 needle = The element or sub-range to _count in the `haystack`.
635 The number of positions in the `haystack` for which `pred` returned true.
637 size_t
count(alias pred
= "a == b", Range
, E
)(Range haystack
, E needle
)
638 if (isInputRange
!Range
&& !isInfinite
!Range
&&
639 is(typeof(binaryFun
!pred(haystack
.front
, needle
))))
641 bool pred2(ElementType
!Range a
) { return binaryFun
!pred(a
, needle
); }
642 return count
!pred2(haystack
);
648 import std
.uni
: toLower
;
650 // count elements in range
651 int[] a
= [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
652 assert(count(a
) == 9);
653 assert(count(a
, 2) == 3);
654 assert(count
!("a > b")(a
, 2) == 5);
655 // count range in range
656 assert(count("abcadfabf", "ab") == 2);
657 assert(count("ababab", "abab") == 1);
658 assert(count("ababab", "abx") == 0);
659 // fuzzy count range in range
660 assert(count
!((a
, b
) => toLower(a
) == toLower(b
))("AbcAdFaBf", "ab") == 2);
661 // count predicate in range
662 assert(count
!("a > 1")(a
) == 8);
667 import std
.conv
: text
;
669 int[] a
= [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
670 assert(count(a
, 2) == 3, text(count(a
, 2)));
671 assert(count
!("a > b")(a
, 2) == 5, text(count
!("a > b")(a
, 2)));
674 assert(count("日本語") == 3);
675 assert(count("日本語"w
) == 3);
676 assert(count("日本語"d
) == 3);
678 assert(count
!("a == '日'")("日本語") == 1);
679 assert(count
!("a == '本'")("日本語"w
) == 1);
680 assert(count
!("a == '語'")("日本語"d
) == 1);
685 string s
= "This is a fofofof list";
687 assert(count(s
, sub) == 2);
691 size_t
count(alias pred
= "a == b", R1
, R2
)(R1 haystack
, R2 needle
)
692 if (isForwardRange
!R1
&& !isInfinite
!R1
&&
694 is(typeof(binaryFun
!pred(haystack
.front
, needle
.front
))))
696 assert(!needle
.empty
, "Cannot count occurrences of an empty range");
698 static if (isInfinite
!R2
)
700 //Note: This is the special case of looking for an infinite inside a finite...
701 //"How many instances of the Fibonacci sequence can you count in [1, 2, 3]?" - "None."
707 //Note: haystack is not saved, because findskip is designed to modify it
708 for ( ; findSkip
!pred(haystack
, needle
.save
) ; ++result
)
715 size_t
count(alias pred
, R
)(R haystack
)
716 if (isInputRange
!R
&& !isInfinite
!R
&&
717 is(typeof(unaryFun
!pred(haystack
.front
))))
720 alias T
= ElementType
!R
; //For narrow strings forces dchar iteration
721 foreach (T elem
; haystack
)
722 if (unaryFun
!pred(elem
)) ++result
;
727 size_t
count(R
)(R haystack
)
728 if (isInputRange
!R
&& !isInfinite
!R
)
730 return walkLength(haystack
);
735 int[] a
= [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
736 assert(count
!("a == 3")(a
) == 2);
737 assert(count("日本語") == 3);
740 // https://issues.dlang.org/show_bug.cgi?id=11253
741 @safe nothrow unittest
743 assert([1, 2, 3].count([2, 3]) == 1);
746 // https://issues.dlang.org/show_bug.cgi?id=22582
749 assert([1, 2, 3].count
!"a & 1" == 2);
753 Counts elements in the given
754 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
755 until the given predicate is true for one of the given `needles`.
758 pred = The predicate for determining when to stop counting.
760 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be
762 needles = Either a single element, or a
763 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
764 of elements, to be evaluated in turn against each
765 element in `haystack` under the given predicate.
767 Returns: The number of elements which must be popped from the front of
768 `haystack` before reaching an element for which
769 `startsWith!pred(haystack, needles)` is `true`. If
770 `startsWith!pred(haystack, needles)` is not `true` for any element in
771 `haystack`, then `-1` is returned. If only `pred` is provided,
772 `pred(haystack)` is tested for each element.
774 See_Also: $(REF indexOf, std,string)
776 ptrdiff_t
countUntil(alias pred
= "a == b", R
, Rs
...)(R haystack
, Rs needles
)
779 && isForwardRange
!(Rs
[0]) == isInputRange
!(Rs
[0])
780 && allSatisfy
!(canTestStartsWith
!(pred
, R
), Rs
))
782 typeof(return) result
;
784 static if (needles
.length
== 1)
786 static if (hasLength
!R
) //Note: Narrow strings don't have length.
788 //We delegate to find because find is very efficient.
789 //We store the length of the haystack so we don't have to save it.
790 auto len
= haystack
.length
;
791 auto r2
= find
!pred(haystack
, needles
[0]);
793 return cast(typeof(return)) (len
- r2
.length
);
797 import std
.range
: dropOne
;
799 if (needles
[0].empty
)
802 //Default case, slower route doing startsWith iteration
803 for ( ; !haystack
.empty
; ++result
)
805 //We compare the first elements of the ranges here before
806 //forwarding to startsWith. This avoids making useless saves to
807 //haystack/needle if they aren't even going to be mutated anyways.
808 //It also cuts down on the amount of pops on haystack.
809 if (binaryFun
!pred(haystack
.front
, needles
[0].front
))
811 //Here, we need to save the needle before popping it.
812 //haystack we pop in all paths, so we do that, and then save.
814 if (startsWith
!pred(haystack
.save
, needles
[0].save
.dropOne()))
826 static if (isForwardRange
!Ri
)
828 if (needles
[i
].empty
)
835 static if (!isForwardRange
!Ri
)
840 for (; !haystack
.empty
; ++result
, haystack
.popFront())
844 static if (isForwardRange
!Ri
)
846 t
[i
] = needles
[i
].save
;
849 if (startsWith
!pred(haystack
.save
, t
.expand
))
856 // Because of https://issues.dlang.org/show_bug.cgi?id=8804
857 // Avoids both "unreachable code" or "no return statement"
858 static if (isInfinite
!R
) assert(false, R
.stringof
~ " must not be an"
859 ~ " infinite range");
864 ptrdiff_t
countUntil(alias pred
= "a == b", R
, N
)(R haystack
, N needle
)
865 if (isInputRange
!R
&&
866 is(typeof(binaryFun
!pred(haystack
.front
, needle
)) : bool))
868 bool pred2(ElementType
!R a
) { return binaryFun
!pred(a
, needle
); }
869 return countUntil
!pred2(haystack
);
875 assert(countUntil("hello world", "world") == 6);
876 assert(countUntil("hello world", 'r') == 8);
877 assert(countUntil("hello world", "programming") == -1);
878 assert(countUntil("日本語", "本語") == 1);
879 assert(countUntil("日本語", '語') == 2);
880 assert(countUntil("日本語", "五") == -1);
881 assert(countUntil("日本語", '五') == -1);
882 assert(countUntil([0, 7, 12, 22, 9], [12, 22]) == 2);
883 assert(countUntil([0, 7, 12, 22, 9], 9) == 4);
884 assert(countUntil
!"a > b"([0, 7, 12, 22, 9], 20) == 3);
889 import std
.algorithm
.iteration
: filter
;
890 import std
.internal
.test.dummyrange
;
892 assert(countUntil("日本語", "") == 0);
893 assert(countUntil("日本語"d
, "") == 0);
895 assert(countUntil("", "") == 0);
896 assert(countUntil("".filter
!"true"(), "") == 0);
898 auto rf
= [0, 20, 12, 22, 9].filter
!"true"();
899 assert(rf
.countUntil
!"a > b"((int[]).init
) == 0);
900 assert(rf
.countUntil
!"a > b"(20) == 3);
901 assert(rf
.countUntil
!"a > b"([20, 8]) == 3);
902 assert(rf
.countUntil
!"a > b"([20, 10]) == -1);
903 assert(rf
.countUntil
!"a > b"([20, 8, 0]) == -1);
905 auto r
= new ReferenceForwardRange
!int([0, 1, 2, 3, 4, 5, 6]);
906 auto r2
= new ReferenceForwardRange
!int([3, 4]);
907 auto r3
= new ReferenceForwardRange
!int([3, 5]);
908 assert(r
.save
.countUntil(3) == 3);
909 assert(r
.save
.countUntil(r2
) == 3);
910 assert(r
.save
.countUntil(7) == -1);
911 assert(r
.save
.countUntil(r3
) == -1);
916 assert(countUntil("hello world", "world", "asd") == 6);
917 assert(countUntil("hello world", "world", "ello") == 1);
918 assert(countUntil("hello world", "world", "") == 0);
919 assert(countUntil("hello world", "world", 'l') == 2);
923 ptrdiff_t
countUntil(alias pred
, R
)(R haystack
)
924 if (isInputRange
!R
&&
925 is(typeof(unaryFun
!pred(haystack
.front
)) : bool))
928 static if (isRandomAccessRange
!R
)
930 //Optimized RA implementation. Since we want to count *and* iterate at
931 //the same time, it is more efficient this way.
932 static if (hasLength
!R
)
934 immutable len
= cast(typeof(return)) haystack
.length
;
935 for ( ; i
< len
; ++i
)
936 if (unaryFun
!pred(haystack
[i
])) return i
;
938 else //if (isInfinite!R)
941 if (unaryFun
!pred(haystack
[i
])) return i
;
944 else static if (hasLength
!R
)
946 //For those odd ranges that have a length, but aren't RA.
947 //It is faster to quick find, and then compare the lengths
948 auto r2
= find
!pred(haystack
.save
);
949 if (!r2
.empty
) return cast(typeof(return)) (haystack
.length
- r2
.length
);
951 else //Everything else
953 alias T
= ElementType
!R
; //For narrow strings forces dchar iteration
954 foreach (T elem
; haystack
)
956 if (unaryFun
!pred(elem
)) return i
;
961 // Because of https://issues.dlang.org/show_bug.cgi?id=8804
962 // Avoids both "unreachable code" or "no return statement"
963 static if (isInfinite
!R
) assert(false, R
.stringof
~ " must not be an"
971 import std
.ascii
: isDigit
;
972 import std
.uni
: isWhite
;
974 assert(countUntil
!(isWhite
)("hello world") == 5);
975 assert(countUntil
!(isDigit
)("hello world") == -1);
976 assert(countUntil
!"a > 20"([0, 7, 12, 22, 9]) == 3);
981 import std
.internal
.test.dummyrange
;
986 ReferenceInputRange
!int r
;
987 r
= new ReferenceInputRange
!int([0, 1, 2, 3, 4, 5, 6]);
988 assert(r
.countUntil(3) == 3);
989 r
= new ReferenceInputRange
!int([0, 1, 2, 3, 4, 5, 6]);
990 assert(r
.countUntil(7) == -1);
994 auto r
= new ReferenceForwardRange
!int([0, 1, 2, 3, 4, 5, 6]);
995 assert(r
.save
.countUntil([3, 4]) == 3);
996 assert(r
.save
.countUntil(3) == 3);
997 assert(r
.save
.countUntil([3, 7]) == -1);
998 assert(r
.save
.countUntil(7) == -1);
1002 auto r
= new ReferenceInfiniteForwardRange
!int(0);
1003 assert(r
.save
.countUntil([3, 4]) == 3);
1004 assert(r
.save
.countUntil(3) == 3);
1009 Checks if the given range ends with (one of) the given needle(s).
1010 The reciprocal of `startsWith`.
1013 pred = The predicate to use for comparing elements between the range and
1017 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
1020 withOneOfThese = The needles to check against, which may be single
1021 elements, or bidirectional ranges of elements.
1023 withThis = The single element to check.
1026 0 if the needle(s) do not occur at the end of the given range;
1027 otherwise the position of the matching needle, that is, 1 if the range ends
1028 with `withOneOfThese[0]`, 2 if it ends with `withOneOfThese[1]`, and so
1031 In the case when no needle parameters are given, return `true` iff back of
1032 `doesThisStart` fulfils predicate `pred`.
1034 uint endsWith(alias pred
= "a == b", Range
, Needles
...)(Range doesThisEnd
, Needles withOneOfThese
)
1035 if (isBidirectionalRange
!Range
&& Needles
.length
> 1 &&
1036 allSatisfy
!(canTestStartsWith
!(pred
, Range
), Needles
))
1038 alias haystack
= doesThisEnd
;
1039 alias needles
= withOneOfThese
;
1041 // Make one pass looking for empty ranges in needles
1042 foreach (i
, Unused
; Needles
)
1044 // Empty range matches everything
1045 static if (!is(typeof(binaryFun
!pred(haystack
.back
, needles
[i
])) : bool))
1047 if (needles
[i
].empty
) return i
+ 1;
1051 for (; !haystack
.empty
; haystack
.popBack())
1053 foreach (i
, Unused
; Needles
)
1055 static if (is(typeof(binaryFun
!pred(haystack
.back
, needles
[i
])) : bool))
1058 if (binaryFun
!pred(haystack
.back
, needles
[i
]))
1060 // found, but continue to account for one-element
1061 // range matches (consider endsWith("ab", "b",
1062 // 'b') should return 1, not 2).
1068 if (binaryFun
!pred(haystack
.back
, needles
[i
].back
))
1072 // This code executed on failure to match
1073 // Out with this guy, check for the others
1074 uint result
= endsWith
!pred(haystack
, needles
[0 .. i
], needles
[i
+ 1 .. $]);
1075 if (result
> i
) ++result
;
1079 // If execution reaches this point, then the back matches for all
1080 // needles ranges. What we need to do now is to lop off the back of
1081 // all ranges involved and recurse.
1082 foreach (i
, Unused
; Needles
)
1084 static if (is(typeof(binaryFun
!pred(haystack
.back
, needles
[i
])) : bool))
1086 // Test has passed in the previous loop
1091 needles
[i
].popBack();
1092 if (needles
[i
].empty
) return i
+ 1;
1100 bool endsWith(alias pred
= "a == b", R1
, R2
)(R1 doesThisEnd
, R2 withThis
)
1101 if (isBidirectionalRange
!R1
&&
1102 isBidirectionalRange
!R2
&&
1103 is(typeof(binaryFun
!pred(doesThisEnd
.back
, withThis
.back
)) : bool))
1105 alias haystack
= doesThisEnd
;
1106 alias needle
= withThis
;
1108 static if (is(typeof(pred
) : string
))
1109 enum isDefaultPred
= pred
== "a == b";
1111 enum isDefaultPred
= false;
1113 static if (isDefaultPred
&& isArray
!R1
&& isArray
!R2
&&
1114 is(immutable ElementEncodingType
!R1
== immutable ElementEncodingType
!R2
))
1116 if (haystack
.length
< needle
.length
) return false;
1118 return haystack
[$ - needle
.length
.. $] == needle
;
1122 import std
.range
: retro
;
1123 return startsWith
!pred(retro(doesThisEnd
), retro(withThis
));
1128 bool endsWith(alias pred
= "a == b", R
, E
)(R doesThisEnd
, E withThis
)
1129 if (isBidirectionalRange
!R
&&
1130 is(typeof(binaryFun
!pred(doesThisEnd
.back
, withThis
)) : bool))
1132 if (doesThisEnd
.empty
)
1135 static if (is(typeof(pred
) : string
))
1136 enum isDefaultPred
= pred
== "a == b";
1138 enum isDefaultPred
= false;
1140 alias predFunc
= binaryFun
!pred
;
1142 // auto-decoding special case
1143 static if (isNarrowString
!R
)
1145 // statically determine decoding is unnecessary to evaluate pred
1146 static if (isDefaultPred
&& isSomeChar
!E
&& E
.sizeof
<= ElementEncodingType
!R
.sizeof
)
1147 return doesThisEnd
[$ - 1] == withThis
;
1148 // specialize for ASCII as to not change previous behavior
1151 if (withThis
<= 0x7F)
1152 return predFunc(doesThisEnd
[$ - 1], withThis
);
1154 return predFunc(doesThisEnd
.back
, withThis
);
1159 return predFunc(doesThisEnd
.back
, withThis
);
1164 bool endsWith(alias pred
, R
)(R doesThisEnd
)
1165 if (isInputRange
!R
&&
1166 ifTestable
!(typeof(doesThisEnd
.front
), unaryFun
!pred
))
1168 return !doesThisEnd
.empty
&& unaryFun
!pred(doesThisEnd
.back
);
1174 import std
.ascii
: isAlpha
;
1175 assert("abc".endsWith
!(a
=> a
.isAlpha
));
1176 assert("abc".endsWith
!isAlpha
);
1178 assert(!"ab1".endsWith
!(a
=> a
.isAlpha
));
1180 assert(!"ab1".endsWith
!isAlpha
);
1181 assert(!"".endsWith
!(a
=> a
.isAlpha
));
1183 import std
.algorithm
.comparison
: among
;
1184 assert("abc".endsWith
!(a
=> a
.among('c', 'd') != 0));
1185 assert(!"abc".endsWith
!(a
=> a
.among('a', 'b') != 0));
1187 assert(endsWith("abc", ""));
1188 assert(!endsWith("abc", "b"));
1189 assert(endsWith("abc", "a", 'c') == 2);
1190 assert(endsWith("abc", "c", "a") == 1);
1191 assert(endsWith("abc", "c", "c") == 1);
1192 assert(endsWith("abc", "bc", "c") == 2);
1193 assert(endsWith("abc", "x", "c", "b") == 2);
1194 assert(endsWith("abc", "x", "aa", "bc") == 3);
1195 assert(endsWith("abc", "x", "aaa", "sab") == 0);
1196 assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);
1201 import std
.algorithm
.iteration
: filterBidirectional
;
1202 import std
.conv
: to
;
1203 import std
.meta
: AliasSeq
;
1205 static foreach (S
; AliasSeq
!(char[], wchar[], dchar[], string
, wstring
, dstring
))
1206 (){ // workaround slow optimizations for large functions
1207 // https://issues.dlang.org/show_bug.cgi?id=2396
1208 assert(!endsWith(to
!S("abc"), 'a'));
1209 assert(endsWith(to
!S("abc"), 'a', 'c') == 2);
1210 assert(!endsWith(to
!S("abc"), 'x', 'n', 'b'));
1211 assert(endsWith(to
!S("abc"), 'x', 'n', 'c') == 3);
1212 assert(endsWith(to
!S("abc\uFF28"), 'a', '\uFF28', 'c') == 2);
1214 static foreach (T
; AliasSeq
!(char[], wchar[], dchar[], string
, wstring
, dstring
))
1217 assert(endsWith(to
!S("abc"), to
!T("")));
1218 assert(!endsWith(to
!S("abc"), to
!T("a")));
1219 assert(!endsWith(to
!S("abc"), to
!T("b")));
1220 assert(endsWith(to
!S("abc"), to
!T("bc"), 'c') == 2);
1221 assert(endsWith(to
!S("abc"), to
!T("a"), "c") == 2);
1222 assert(endsWith(to
!S("abc"), to
!T("c"), "a") == 1);
1223 assert(endsWith(to
!S("abc"), to
!T("c"), "c") == 1);
1224 assert(endsWith(to
!S("abc"), to
!T("x"), 'c', "b") == 2);
1225 assert(endsWith(to
!S("abc"), 'x', to
!T("aa"), "bc") == 3);
1226 assert(endsWith(to
!S("abc"), to
!T("x"), "aaa", "sab") == 0);
1227 assert(endsWith(to
!S("abc"), to
!T("x"), "aaa", "c", "sab") == 3);
1228 assert(endsWith(to
!S("\uFF28el\uFF4co"), to
!T("l\uFF4co")));
1229 assert(endsWith(to
!S("\uFF28el\uFF4co"), to
!T("lo"), to
!T("l\uFF4co")) == 2);
1232 assert(endsWith(to
!S("\uFF28el\uFF4co"), to
!T("l\uFF4co")));
1233 assert(endsWith(to
!S("\uFF28el\uFF4co"), to
!T("lo"), to
!T("l\uFF4co")) == 2);
1234 assert(endsWith(to
!S("日本語"), to
!T("本語")));
1235 assert(endsWith(to
!S("日本語"), to
!T("日本語")));
1236 assert(!endsWith(to
!S("本語"), to
!T("日本語")));
1239 assert(endsWith(to
!S(""), T
.init
));
1240 assert(!endsWith(to
!S(""), 'a'));
1241 assert(endsWith(to
!S("a"), T
.init
));
1242 assert(endsWith(to
!S("a"), T
.init
, "") == 1);
1243 assert(endsWith(to
!S("a"), T
.init
, 'a') == 1);
1244 assert(endsWith(to
!S("a"), 'a', T
.init
) == 2);
1248 static foreach (T
; AliasSeq
!(int, short))
1250 immutable arr
= cast(T
[])[0, 1, 2, 3, 4, 5];
1253 assert(endsWith(arr
, cast(int[]) null));
1254 assert(!endsWith(arr
, 0));
1255 assert(!endsWith(arr
, 4));
1256 assert(endsWith(arr
, 5));
1257 assert(endsWith(arr
, 0, 4, 5) == 3);
1258 assert(endsWith(arr
, [5]));
1259 assert(endsWith(arr
, [4, 5]));
1260 assert(endsWith(arr
, [4, 5], 7) == 1);
1261 assert(!endsWith(arr
, [2, 4, 5]));
1262 assert(endsWith(arr
, [2, 4, 5], [3, 4, 5]) == 2);
1264 //Normal input range
1265 assert(!endsWith(filterBidirectional
!"true"(arr
), 4));
1266 assert(endsWith(filterBidirectional
!"true"(arr
), 5));
1267 assert(endsWith(filterBidirectional
!"true"(arr
), [5]));
1268 assert(endsWith(filterBidirectional
!"true"(arr
), [4, 5]));
1269 assert(endsWith(filterBidirectional
!"true"(arr
), [4, 5], 7) == 1);
1270 assert(!endsWith(filterBidirectional
!"true"(arr
), [2, 4, 5]));
1271 assert(endsWith(filterBidirectional
!"true"(arr
), [2, 4, 5], [3, 4, 5]) == 2);
1272 assert(endsWith(arr
, filterBidirectional
!"true"([4, 5])));
1273 assert(endsWith(arr
, filterBidirectional
!"true"([4, 5]), 7) == 1);
1274 assert(!endsWith(arr
, filterBidirectional
!"true"([2, 4, 5])));
1275 assert(endsWith(arr
, [2, 4, 5], filterBidirectional
!"true"([3, 4, 5])) == 2);
1278 assert(endsWith
!("a%10 == b%10")(arr
, [14, 15]));
1279 assert(!endsWith
!("a%10 == b%10")(arr
, [15, 14]));
1285 //example from https://issues.dlang.org/show_bug.cgi?id=19727
1286 import std
.path
: asRelativePath
;
1287 string
[] ext
= ["abc", "def", "ghi"];
1288 string path
= "/foo/file.def";
1289 assert(ext
.any
!(e
=> path
.asRelativePath("/foo").endsWith(e
)) == true);
1290 assert(ext
.any
!(e
=> path
.asRelativePath("/foo").startsWith(e
)) == false);
1293 private enum bool hasConstEmptyMember(T
) = is(typeof(((const T
* a
) => (*a
).empty
)(null)) : bool);
1296 Iterates the passed range and selects the extreme element with `less`.
1297 If the extreme element occurs multiple time, the first occurrence will be
1301 map = custom accessor for the comparison key
1302 selector = custom mapping for the extrema selection
1303 r = Range from which the extreme value will be selected
1304 seedElement = custom seed to use as initial element
1307 The extreme value according to `map` and `selector` of the passed-in values.
1309 private auto extremum(alias map
, alias selector
= "a < b", Range
)(Range r
)
1310 if (isInputRange
!Range
&& !isInfinite
!Range
&&
1311 is(typeof(unaryFun
!map(ElementType
!(Range
).init
))))
1314 assert(!r
.empty
, "r is an empty range");
1318 import std
.typecons
: Rebindable2
;
1320 alias Element
= ElementType
!Range
;
1321 auto seed
= Rebindable2
!Element(r
.front
);
1323 return extremum
!(map
, selector
)(r
, seed
.get
);
1326 private auto extremum(alias map
, alias selector
= "a < b", Range
,
1327 RangeElementType
= ElementType
!Range
)
1328 (Range r
, RangeElementType seedElement
)
1329 if (isInputRange
!Range
&& !isInfinite
!Range
&&
1330 !is(CommonType
!(ElementType
!Range
, RangeElementType
) == void) &&
1331 is(typeof(unaryFun
!map(ElementType
!(Range
).init
))))
1333 import std
.typecons
: Rebindable2
;
1335 alias mapFun
= unaryFun
!map
;
1336 alias selectorFun
= binaryFun
!selector
;
1338 alias Element
= ElementType
!Range
;
1339 alias CommonElement
= CommonType
!(Element
, RangeElementType
);
1340 auto extremeElement
= Rebindable2
!CommonElement(seedElement
);
1342 // if we only have one statement in the loop, it can be optimized a lot better
1343 static if (__traits(isSame
, map
, a
=> a
))
1345 // direct access via a random access range is faster
1346 static if (isRandomAccessRange
!Range
)
1348 foreach (const i
; 0 .. r
.length
)
1350 if (selectorFun(r
[i
], extremeElement
.get
))
1352 extremeElement
= r
[i
];
1360 if (selectorFun(r
.front
, extremeElement
.get
))
1362 extremeElement
= r
.front
;
1370 alias MapType
= Unqual
!(typeof(mapFun(CommonElement
.init
)));
1371 MapType extremeElementMapped
= mapFun(extremeElement
.get
);
1373 // direct access via a random access range is faster
1374 static if (isRandomAccessRange
!Range
)
1376 foreach (const i
; 0 .. r
.length
)
1378 MapType mapElement
= mapFun(r
[i
]);
1379 if (selectorFun(mapElement
, extremeElementMapped
))
1381 extremeElement
= r
[i
];
1382 extremeElementMapped
= mapElement
;
1390 MapType mapElement
= mapFun(r
.front
);
1391 if (selectorFun(mapElement
, extremeElementMapped
))
1393 extremeElement
= r
.front
;
1394 extremeElementMapped
= mapElement
;
1400 return extremeElement
.get
;
1403 private auto extremum(alias selector
= "a < b", Range
)(Range r
)
1404 if (isInputRange
!Range
&& !isInfinite
!Range
&&
1405 !is(typeof(unaryFun
!selector(ElementType
!(Range
).init
))))
1407 return extremum
!(a
=> a
, selector
)(r
);
1410 // if we only have one statement in the loop it can be optimized a lot better
1411 private auto extremum(alias selector
= "a < b", Range
,
1412 RangeElementType
= ElementType
!Range
)
1413 (Range r
, RangeElementType seedElement
)
1414 if (isInputRange
!Range
&& !isInfinite
!Range
&&
1415 !is(CommonType
!(ElementType
!Range
, RangeElementType
) == void) &&
1416 !is(typeof(unaryFun
!selector(ElementType
!(Range
).init
))))
1418 return extremum
!(a
=> a
, selector
)(r
, seedElement
);
1423 // allows a custom map to select the extremum
1424 assert([[0, 4], [1, 2]].extremum
!"a[0]" == [0, 4]);
1425 assert([[0, 4], [1, 2]].extremum
!"a[1]" == [1, 2]);
1427 // allows a custom selector for comparison
1428 assert([[0, 4], [1, 2]].extremum
!("a[0]", "a > b") == [1, 2]);
1429 assert([[0, 4], [1, 2]].extremum
!("a[1]", "a > b") == [0, 4]);
1431 // use a custom comparator
1432 import std
.math
.operations
: cmp;
1433 assert([-2., 0, 5].extremum
!cmp == 5.0);
1434 assert([-2., 0, 2].extremum
!`cmp(a, b) < 0` == -2.0);
1437 import std
.range
: enumerate
;
1438 assert([-3., 0, 5].enumerate
.extremum
!(`a.value`, cmp) == tuple(2, 5.0));
1439 assert([-2., 0, 2].enumerate
.extremum
!(`a.value`, `cmp(a, b) < 0`) == tuple(0, -2.0));
1441 // seed with a custom value
1443 assert(arr
.extremum(1) == 1);
1446 @safe pure nothrow unittest
1450 assert(arr2d
.extremum([1]) == [1]);
1452 // allow seeds of different types (implicit casting)
1453 assert(extremum([2, 3, 4], 1.5) == 1.5);
1458 import std
.range
: enumerate
, iota
;
1461 assert(iota(1, 5).extremum() == 1);
1462 assert(iota(2, 5).enumerate
.extremum
!"a.value" == tuple(0, 2));
1464 // should work with const
1465 const(int)[] immArr
= [2, 1, 3];
1466 assert(immArr
.extremum
== 1);
1468 // should work with immutable
1469 immutable(int)[] immArr2
= [2, 1, 3];
1470 assert(immArr2
.extremum
== 1);
1473 assert(["b", "a", "c"].extremum
== "a");
1475 // with all dummy ranges
1476 import std
.internal
.test.dummyrange
;
1477 foreach (DummyType
; AllDummyRanges
)
1480 assert(d
.extremum
== 1);
1481 assert(d
.extremum
!(a
=> a
) == 1);
1482 assert(d
.extremum
!`a > b` == 10);
1483 assert(d
.extremum
!(a
=> a
, `a > b`) == 10);
1487 enum ctExtremum
= iota(1, 5).extremum
;
1488 assert(ctExtremum
== 1);
1491 @nogc @safe nothrow pure unittest
1493 static immutable arr
= [7, 3, 4, 2, 1, 8];
1494 assert(arr
.extremum
== 1);
1496 static immutable arr2d
= [[1, 9], [3, 1], [4, 2]];
1497 assert(arr2d
.extremum
!"a[1]" == arr2d
[1]);
1500 // https://issues.dlang.org/show_bug.cgi?id=17982
1506 this(int val
){ this.val
= val
; }
1509 const(B
) doStuff(const(B
)[] v
)
1511 return v
.extremum
!"a.val";
1513 assert(doStuff([new B(1), new B(0), new B(2)]).val
== 0);
1515 const(B
)[] arr
= [new B(0), new B(1)];
1516 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
1517 assert(arr
.extremum
!"a.val".val
== 0);
1520 // https://issues.dlang.org/show_bug.cgi?id=22786
1521 @nogc @safe nothrow pure unittest
1525 immutable int value
;
1528 assert([S(5), S(6)].extremum
!"a.value" == S(5));
1531 // https://issues.dlang.org/show_bug.cgi?id=24027
1532 @safe nothrow unittest
1543 auto test = new A(5);
1545 assert(maxElement
!"a.a"(arr
) is test);
1550 Finds an individual element in an $(REF_ALTTEXT input range, isInputRange, std,range,primitives).
1551 Elements of `haystack` are compared with `needle` by using predicate
1552 `pred` with `pred(haystack.front, needle)`.
1553 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`.
1555 The predicate is passed to $(REF binaryFun, std, functional), and can either accept a
1556 string, or any callable that can be executed via `pred(element, element)`.
1558 To _find the last occurrence of `needle` in a
1559 $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives) `haystack`,
1560 call `find(retro(haystack), needle)`. See $(REF retro, std,range).
1562 If no `needle` is provided, `pred(haystack.front)` will be evaluated on each
1563 element of the input range.
1565 If `input` is a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives),
1566 `needle` can be a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) too.
1567 In this case `startsWith!pred(haystack, needle)` is evaluated on each evaluation.
1570 `find` behaves similar to `dropWhile` in other languages.
1573 `find` performs $(BIGOH walkLength(haystack)) evaluations of `pred`.
1574 There are specializations that improve performance by taking
1575 advantage of $(REF_ALTTEXT bidirectional, isBidirectionalRange, std,range,primitives)
1576 or $(REF_ALTTEXT random access, isRandomAccessRange, std,range,primitives)
1577 ranges (where possible).
1581 pred = The predicate for comparing each element with the needle, defaulting to equality `"a == b"`.
1582 The negated predicate `"a != b"` can be used to search instead for the first
1583 element $(I not) matching the needle.
1585 haystack = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1588 needle = The element searched for.
1592 `haystack` advanced such that the front element is the one searched for;
1593 that is, until `binaryFun!pred(haystack.front, needle)` is `true`. If no
1594 such position exists, returns an empty `haystack`.
1596 See_ALso: $(LREF findAdjacent), $(LREF findAmong), $(LREF findSkip), $(LREF findSplit), $(LREF startsWith)
1598 InputRange
find(alias pred
= "a == b", InputRange
, Element
)(InputRange haystack
, scope Element needle
)
1599 if (isInputRange
!InputRange
&&
1600 is (typeof(binaryFun
!pred(haystack
.front
, needle
)) : bool) &&
1601 !is (typeof(binaryFun
!pred(haystack
.front
, needle
.front
)) : bool))
1603 alias R
= InputRange
;
1605 alias predFun
= binaryFun
!pred
;
1606 static if (is(typeof(pred
== "a == b")))
1607 enum isDefaultPred
= pred
== "a == b";
1609 enum isDefaultPred
= false;
1610 enum isIntegralNeedle
= isSomeChar
!E || isIntegral
!E || isBoolean
!E
;
1612 alias EType
= ElementType
!R
;
1614 // If the haystack is a SortedRange we can use binary search to find the needle.
1615 // Works only for the default find predicate and any SortedRange predicate.
1616 // https://issues.dlang.org/show_bug.cgi?id=8829
1617 import std
.range
: SortedRange
;
1618 static if (is(InputRange
: SortedRange
!TT
, TT
) && isDefaultPred
)
1620 auto lb
= haystack
.lowerBound(needle
);
1621 if (lb
.length
== haystack
.length || haystack
[lb
.length
] != needle
)
1622 return haystack
[$ .. $];
1624 return haystack
[lb
.length
.. $];
1626 else static if (isNarrowString
!R
)
1628 alias EEType
= ElementEncodingType
!R
;
1629 alias UEEType
= Unqual
!EEType
;
1631 //These are two special cases which can search without decoding the UTF stream.
1632 static if (isDefaultPred
&& isIntegralNeedle
)
1634 import std
.utf
: canSearchInCodeUnits
;
1636 //This special case deals with UTF8 search, when the needle
1637 //is represented by a single code point.
1638 //Note: "needle <= 0x7F" properly handles sign via unsigned promotion
1639 static if (is(UEEType
== char))
1641 if (!__ctfe
&& canSearchInCodeUnits
!char(needle
))
1643 static inout(R
) trustedMemchr(ref return scope inout(R
) haystack
,
1644 ref const scope E needle
) @trusted nothrow pure
1646 import core
.stdc
.string
: memchr
;
1647 auto ptr
= memchr(haystack
.ptr
, needle
, haystack
.length
);
1649 haystack
[cast(char*) ptr
- haystack
.ptr
.. $] :
1652 return trustedMemchr(haystack
, needle
);
1656 //Ditto, but for UTF16
1657 static if (is(UEEType
== wchar))
1659 if (canSearchInCodeUnits
!wchar(needle
))
1661 foreach (i
, ref EEType e
; haystack
)
1664 return haystack
[i
.. $];
1666 return haystack
[$ .. $];
1671 //Previous conditional optimizations did not succeed. Fallback to
1672 //unconditional implementations
1673 static if (isDefaultPred
)
1675 import std
.utf
: encode
;
1677 //In case of default pred, it is faster to do string/string search.
1678 UEEType
[is(UEEType
== char) ?
4 : 2] buf
;
1680 size_t len
= encode(buf
, needle
);
1681 return find(haystack
, buf
[0 .. len
]);
1685 import std
.utf
: decode
;
1687 //Explicit pred: we must test each character by the book.
1688 //We choose a manual decoding approach, because it is faster than
1689 //the built-in foreach, or doing a front/popFront for-loop.
1690 immutable len
= haystack
.length
;
1691 size_t i
= 0, next
= 0;
1694 if (predFun(decode(haystack
, next
), needle
))
1695 return haystack
[i
.. $];
1698 return haystack
[$ .. $];
1701 else static if (isArray
!R
)
1703 // https://issues.dlang.org/show_bug.cgi?id=10403 optimization
1704 static if (isDefaultPred
&& isIntegral
!EType
&& EType
.sizeof
== 1 && isIntegralNeedle
)
1706 import std
.algorithm
.comparison
: max
, min
;
1708 R
findHelper(return scope ref R haystack
, ref E needle
) @trusted nothrow pure
1710 import core
.stdc
.string
: memchr
;
1713 //Note: we use "min/max" to handle sign mismatch.
1714 if (min(EType
.min
, needle
) == EType
.min
&&
1715 max(EType
.max
, needle
) == EType
.max
)
1717 ptr
= cast(EType
*) memchr(haystack
.ptr
, needle
,
1722 haystack
[ptr
- haystack
.ptr
.. $] :
1727 return findHelper(haystack
, needle
);
1730 //Default implementation.
1731 foreach (i
, ref e
; haystack
)
1732 if (predFun(e
, needle
))
1733 return haystack
[i
.. $];
1734 return haystack
[$ .. $];
1738 //Everything else. Walk.
1739 for ( ; !haystack
.empty
; haystack
.popFront() )
1741 if (predFun(haystack
.front
, needle
))
1751 import std
.range
.primitives
;
1753 auto arr
= [1, 2, 4, 4, 4, 4, 5, 6, 9];
1754 assert(arr
.find(4) == [4, 4, 4, 4, 5, 6, 9]);
1755 assert(arr
.find(1) == arr
);
1756 assert(arr
.find(9) == [9]);
1757 assert(arr
.find
!((a
, b
) => a
> b
)(4) == [5, 6, 9]);
1758 assert(arr
.find
!((a
, b
) => a
< b
)(4) == arr
);
1759 assert(arr
.find(0).empty
);
1760 assert(arr
.find(10).empty
);
1761 assert(arr
.find(8).empty
);
1763 assert(find("hello, world", ',') == ", world");
1766 /// Case-insensitive find of a string
1769 import std
.range
.primitives
;
1770 import std
.uni
: toLower
;
1772 string
[] s
= ["Hello", "world", "!"];
1773 assert(s
.find
!((a
, b
) => toLower(a
) == b
)("hello") == s
);
1778 import std
.algorithm
.comparison
: equal
;
1779 import std
.container
: SList
;
1781 auto lst
= SList
!int(1, 2, 5, 7, 3);
1782 assert(lst
.front
== 1);
1783 auto r
= find(lst
[], 5);
1784 assert(equal(r
, SList
!int(5, 7, 3)[]));
1785 assert(find([1, 2, 3, 5], 4).empty
);
1786 assert(equal(find
!"a > b"("hello", 'k'), "llo"));
1789 @safe pure nothrow unittest
1791 assert(!find ([1, 2, 3], 2).empty
);
1792 assert(!find
!((a
,b
)=>a
== b
)([1, 2, 3], 2).empty
);
1793 assert(!find ([1, 2, 3], 2).empty
);
1794 assert(!find
!((a
,b
)=>a
== b
)([1, 2, 3], 2).empty
);
1799 import std
.meta
: AliasSeq
;
1800 static foreach (R
; AliasSeq
!(string
, wstring
, dstring
))
1802 static foreach (E
; AliasSeq
!(char, wchar, dchar))
1804 assert(find ("hello world", 'w') == "world");
1805 assert(find
!((a
,b
)=>a
== b
)("hello world", 'w') == "world");
1806 assert(find ("日c語", 'c') == "c語");
1807 assert(find
!((a
,b
)=>a
== b
)("日c語", 'c') == "c語");
1808 assert(find ("0123456789", 'A').empty
);
1809 static if (E
.sizeof
>= 2)
1811 assert(find ("日本語", '本') == "本語");
1812 assert(find
!((a
,b
)=>a
== b
)("日本語", '本') == "本語");
1821 static assert(find("abc", 'b') == "bc");
1822 static assert(find("日b語", 'b') == "b語");
1823 static assert(find("日本語", '本') == "本語");
1824 static assert(find([1, 2, 3], 2) == [2, 3]);
1826 static assert(find ([1, 2, 3], 2));
1827 static assert(find
!((a
,b
)=>a
== b
)([1, 2, 3], 2));
1828 static assert(find ([1, 2, 3], 2));
1829 static assert(find
!((a
,b
)=>a
== b
)([1, 2, 3], 2));
1834 import std
.exception
: assertCTFEable
;
1835 import std
.meta
: AliasSeq
;
1837 void dg() @safe pure nothrow
1839 byte[] sarr
= [1, 2, 3, 4];
1840 ubyte[] uarr
= [1, 2, 3, 4];
1841 static foreach (arr
; AliasSeq
!(sarr
, uarr
))
1843 static foreach (T
; AliasSeq
!(byte, ubyte, int, uint))
1845 assert(find(arr
, cast(T
) 3) == arr
[2 .. $]);
1846 assert(find(arr
, cast(T
) 9) == arr
[$ .. $]);
1848 assert(find(arr
, 256) == arr
[$ .. $]);
1855 // https://issues.dlang.org/show_bug.cgi?id=11603
1858 enum Foo
: ubyte { A
}
1859 assert([Foo
.A
].find(Foo
.A
).empty
== false);
1862 assert([x
].find(x
).empty
== false);
1866 InputRange
find(alias pred
, InputRange
)(InputRange haystack
)
1867 if (isInputRange
!InputRange
)
1869 alias R
= InputRange
;
1870 alias predFun
= unaryFun
!pred
;
1871 static if (isNarrowString
!R
)
1873 import std
.utf
: decode
;
1875 immutable len
= haystack
.length
;
1876 size_t i
= 0, next
= 0;
1879 if (predFun(decode(haystack
, next
)))
1880 return haystack
[i
.. $];
1883 return haystack
[$ .. $];
1888 for ( ; !haystack
.empty
; haystack
.popFront() )
1890 if (predFun(haystack
.front
))
1900 auto arr
= [ 1, 2, 3, 4, 1 ];
1901 assert(find
!("a > 2")(arr
) == [ 3, 4, 1 ]);
1903 // with predicate alias
1904 bool pred(int x
) { return x
+ 1 > 1.5; }
1905 assert(find
!(pred
)(arr
) == arr
);
1910 int[] r
= [ 1, 2, 3 ];
1911 assert(find
!(a
=>a
> 2)(r
) == [3]);
1912 bool pred(int x
) { return x
+ 1 > 1.5; }
1913 assert(find
!(pred
)(r
) == r
);
1915 assert(find
!(a
=>a
> 'v')("hello world") == "world");
1916 assert(find
!(a
=>a
%4 == 0)("日本語") == "本語");
1920 R1
find(alias pred
= "a == b", R1
, R2
)(R1 haystack
, scope R2 needle
)
1921 if (isForwardRange
!R1
&& isForwardRange
!R2
1922 && is(typeof(binaryFun
!pred(haystack
.front
, needle
.front
)) : bool))
1924 static if (!isRandomAccessRange
!R1
)
1926 static if (is(typeof(pred
== "a == b")) && pred
== "a == b" && isSomeString
!R1
&& isSomeString
!R2
1927 && haystack
[0].sizeof
== needle
[0].sizeof
)
1929 // return cast(R1) find(representation(haystack), representation(needle));
1930 // Specialization for simple string search
1931 alias Representation
=
1932 Select
!(haystack
[0].sizeof
== 1, ubyte[],
1933 Select
!(haystack
[0].sizeof
== 2, ushort[], uint[]));
1934 // Will use the array specialization
1935 static TO
force(TO
, T
)(inout T r
) @trusted { return cast(TO
) r
; }
1936 return force
!R1(.find
!(pred
, Representation
, Representation
)
1937 (force
!Representation(haystack
), force
!Representation(needle
)));
1941 return simpleMindedFind
!pred(haystack
, needle
);
1944 else static if (!isBidirectionalRange
!R2 ||
!hasSlicing
!R1
)
1946 static if (!is(ElementType
!R1
== ElementType
!R2
))
1948 return simpleMindedFind
!pred(haystack
, needle
);
1952 // Prepare the search with needle's first element
1956 haystack
= .find
!pred(haystack
, needle
.front
);
1958 static if (hasLength
!R1
&& hasLength
!R2
&& is(typeof(takeNone(haystack
)) == R1
))
1960 if (needle
.length
> haystack
.length
)
1961 return takeNone(haystack
);
1970 size_t matchLen
= 1;
1972 // Loop invariant: haystack[0 .. matchLen] matches everything in
1973 // the initial needle that was popped out of needle.
1976 // Extend matchLength as much as possible
1979 import std
.range
: takeNone
;
1981 if (needle
.empty || haystack
.empty
)
1984 static if (hasLength
!R1
&& is(typeof(takeNone(haystack
)) == R1
))
1986 if (matchLen
== haystack
.length
)
1987 return takeNone(haystack
);
1990 if (!binaryFun
!pred(haystack
[matchLen
], needle
.front
))
1997 auto bestMatch
= haystack
[0 .. matchLen
];
1998 haystack
.popFront();
1999 haystack
= .find
!pred(haystack
, bestMatch
);
2003 else // static if (hasSlicing!R1 && isBidirectionalRange!R2)
2005 if (needle
.empty
) return haystack
;
2007 static if (hasLength
!R2
)
2009 immutable needleLength
= needle
.length
;
2013 immutable needleLength
= walkLength(needle
.save
);
2015 if (needleLength
> haystack
.length
)
2017 return haystack
[haystack
.length
.. haystack
.length
];
2019 // Optimization in case the ranges are both SortedRanges.
2020 // Binary search can be used to find the first occurence
2021 // of the first element of the needle in haystack.
2022 // When it is found O(walklength(needle)) steps are performed.
2023 // https://issues.dlang.org/show_bug.cgi?id=8829 enhancement
2024 import std
.algorithm
.comparison
: mismatch
;
2025 import std
.range
: SortedRange
;
2026 static if (is(R1
== R2
)
2027 && is(R1
: SortedRange
!TT
, TT
)
2028 && pred
== "a == b")
2030 auto needleFirstElem
= needle
[0];
2031 auto partitions
= haystack
.trisect(needleFirstElem
);
2032 auto firstElemLen
= partitions
[1].length
;
2035 if (firstElemLen
== 0)
2036 return haystack
[$ .. $];
2038 while (needle
.front() == needleFirstElem
)
2043 if (count
> firstElemLen
)
2044 return haystack
[$ .. $];
2047 auto m
= mismatch(partitions
[2], needle
);
2050 return haystack
[partitions
[0].length
+ partitions
[1].length
- count
.. $];
2052 else static if (isRandomAccessRange
!R2
)
2054 immutable lastIndex
= needleLength
- 1;
2055 auto last
= needle
[lastIndex
];
2056 size_t j
= lastIndex
, skip
= 0;
2057 for (; j
< haystack
.length
;)
2059 if (!binaryFun
!pred(haystack
[j
], last
))
2064 immutable k
= j
- lastIndex
;
2065 // last elements match
2066 for (size_t i
= 0;; ++i
)
2069 return haystack
[k
.. haystack
.length
];
2070 if (!binaryFun
!pred(haystack
[k
+ i
], needle
[i
]))
2076 while (skip
< needleLength
&& needle
[needleLength
- 1 - skip
] != needle
[needleLength
- 1])
2087 // auto needleBack = moveBack(needle);
2088 // Stage 1: find the step
2090 auto needleBack
= needle
.back
;
2092 for (auto i
= needle
.save
; !i
.empty
&& i
.back
!= needleBack
;
2093 i
.popBack(), ++step
)
2096 // Stage 2: linear find
2097 size_t scout
= needleLength
- 1;
2100 if (scout
>= haystack
.length
)
2102 if (!binaryFun
!pred(haystack
[scout
], needleBack
))
2107 // Found a match with the last element in the needle
2108 auto cand
= haystack
[scout
+ 1 - needleLength
.. haystack
.length
];
2109 if (startsWith
!pred(cand
, needle
))
2117 return haystack
[haystack
.length
.. haystack
.length
];
2124 import std
.container
: SList
;
2125 import std
.range
.primitives
: empty
;
2126 import std
.typecons
: Tuple
;
2128 assert(find("hello, world", "World").empty
);
2129 assert(find("hello, world", "wo") == "world");
2130 assert([1, 2, 3, 4].find(SList
!int(2, 3)[]) == [2, 3, 4]);
2131 alias C
= Tuple
!(int, "x", int, "y");
2132 auto a
= [C(1,0), C(2,0), C(3,1), C(4,0)];
2133 assert(a
.find
!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
2134 assert(a
[1 .. $].find
!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
2139 import std
.container
: SList
;
2140 alias C
= Tuple
!(int, "x", int, "y");
2141 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)]);
2144 // https://issues.dlang.org/show_bug.cgi?id=12470
2147 import std
.array
: replace
;
2148 inout(char)[] sanitize(inout(char)[] p
)
2150 return p
.replace("\0", " ");
2152 assert(sanitize("O\x00o") == "O o");
2157 import std
.algorithm
.comparison
: equal
;
2158 import std
.container
: SList
;
2160 auto lst
= SList
!int(1, 2, 5, 7, 3);
2161 static assert(isForwardRange
!(int[]));
2162 static assert(isForwardRange
!(typeof(lst
[])));
2163 auto r
= find(lst
[], [2, 5]);
2164 assert(equal(r
, SList
!int(2, 5, 7, 3)[]));
2169 import std
.range
: assumeSorted
;
2171 auto r1
= assumeSorted([1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 8, 10]);
2172 auto r2
= assumeSorted([3, 3, 4, 5, 6, 7, 8, 8]);
2173 auto r3
= assumeSorted([3, 4, 5, 6, 7, 8]);
2174 auto r4
= assumeSorted([4, 5, 6]);
2175 auto r5
= assumeSorted([12, 13]);
2176 auto r6
= assumeSorted([8, 8, 10, 11]);
2177 auto r7
= assumeSorted([3, 3, 3, 3, 3, 3, 3]);
2179 assert(find(r1
, r2
) == assumeSorted([3, 3, 4, 5, 6, 7, 8, 8, 8, 10]));
2180 assert(find(r1
, r3
) == assumeSorted([3, 4, 5, 6, 7, 8, 8, 8, 10]));
2181 assert(find(r1
, r4
) == assumeSorted([4, 5, 6, 7, 8, 8, 8, 10]));
2182 assert(find(r1
, r5
).empty());
2183 assert(find(r1
, r6
).empty());
2184 assert(find(r1
, r7
).empty());
2189 import std
.algorithm
.comparison
: equal
;
2190 // @@@BUG@@@ removing static below makes unittest fail
2191 static struct BiRange
2194 @property bool empty() { return payload
.empty
; }
2195 @property BiRange
save() { return this; }
2196 @property ref int front() { return payload
[0]; }
2197 @property ref int back() { return payload
[$ - 1]; }
2198 void popFront() { return payload
.popFront(); }
2199 void popBack() { return payload
.popBack(); }
2201 auto r
= BiRange([1, 2, 3, 10, 11, 4]);
2202 assert(equal(find(r
, [10, 11]), [10, 11, 4]));
2207 import std
.container
: SList
;
2209 assert(find([ 1, 2, 3 ], SList
!int(2, 3)[]) == [ 2, 3 ]);
2210 assert(find([ 1, 2, 1, 2, 3, 3 ], SList
!int(2, 3)[]) == [ 2, 3, 3 ]);
2213 // https://issues.dlang.org/show_bug.cgi?id=8334
2216 import std
.algorithm
.iteration
: filter
;
2219 auto haystack
= [1, 2, 3, 4, 1, 9, 12, 42];
2220 auto needle
= [12, 42, 27];
2222 //different overload of find, but it's the base case.
2223 assert(find(haystack
, needle
).empty
);
2225 assert(find(haystack
, takeExactly(filter
!"true"(needle
), 3)).empty
);
2226 assert(find(haystack
, filter
!"true"(needle
)).empty
);
2229 // https://issues.dlang.org/show_bug.cgi?id=11013
2232 assert(find
!"a == a"("abc","abc") == "abc");
2235 // Internally used by some find() overloads above
2236 private R1
simpleMindedFind(alias pred
, R1
, R2
)(R1 haystack
, scope R2 needle
)
2238 enum estimateNeedleLength
= hasLength
!R1
&& !hasLength
!R2
;
2240 static if (hasLength
!R1
)
2242 static if (!hasLength
!R2
)
2243 size_t estimatedNeedleLength
= 0;
2245 immutable size_t estimatedNeedleLength
= needle
.length
;
2248 bool haystackTooShort()
2250 static if (estimateNeedleLength
)
2252 return haystack
.length
< estimatedNeedleLength
;
2256 return haystack
.empty
;
2261 for (;; haystack
.popFront())
2263 if (haystackTooShort())
2266 static if (hasLength
!R1
)
2268 static if (is(typeof(haystack
[haystack
.length
..
2269 haystack
.length
]) : R1
))
2270 return haystack
[haystack
.length
.. haystack
.length
];
2276 assert(haystack
.empty
, "Haystack must be empty by now");
2280 static if (estimateNeedleLength
)
2281 size_t matchLength
= 0;
2282 for (auto h
= haystack
.save
, n
= needle
.save
;
2284 h
.popFront(), n
.popFront())
2286 if (h
.empty ||
!binaryFun
!pred(h
.front
, n
.front
))
2288 // Failed searching n in h
2289 static if (estimateNeedleLength
)
2291 if (estimatedNeedleLength
< matchLength
)
2292 estimatedNeedleLength
= matchLength
;
2296 static if (estimateNeedleLength
)
2306 // Test simpleMindedFind for the case where both haystack and needle have
2313 // This is what triggers https://issues.dlang.org/show_bug.cgi?id=7992.
2314 @property size_t
length() const { return _impl
.length
; }
2315 @property void length(size_t len
) { _impl
.length
= len
; }
2317 // This is for conformance to the forward range API (we deliberately
2318 // make it non-random access so that we will end up in
2319 // simpleMindedFind).
2320 @property bool empty() const { return _impl
.empty
; }
2321 @property dchar front() const { return _impl
.front
; }
2322 void popFront() { _impl
.popFront(); }
2323 @property CustomString
save() { return this; }
2326 // If https://issues.dlang.org/show_bug.cgi?id=7992 occurs, this will throw an exception from calling
2327 // popFront() on an empty range.
2328 auto r
= find(CustomString("a"), CustomString("b"));
2333 Finds two or more `needles` into a `haystack`. The predicate $(D
2334 pred) is used throughout to compare elements. By default, elements are
2335 compared for equality.
2339 pred = The predicate to use for comparing elements.
2341 haystack = The target of the search. Must be an input range.
2342 If any of `needles` is a range with elements comparable to
2343 elements in `haystack`, then `haystack` must be a
2344 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2345 such that the search can backtrack.
2347 needles = One or more items to search for. Each of `needles` must
2348 be either comparable to one element in `haystack`, or be itself a
2349 forward range with elements comparable with elements in
2354 A tuple containing `haystack` positioned to match one of the
2355 needles and also the 1-based index of the matching element in $(D
2356 needles) (0 if none of `needles` matched, 1 if `needles[0]`
2357 matched, 2 if `needles[1]` matched...). The first needle to be found
2358 will be the one that matches. If multiple needles are found at the
2359 same spot in the range, then the shortest one is the one which matches
2360 (if multiple needles of the same length are found at the same spot (e.g
2361 `"a"` and `'a'`), then the left-most of them in the argument list
2364 The relationship between `haystack` and `needles` simply means
2365 that one can e.g. search for individual `int`s or arrays of $(D
2366 int)s in an array of `int`s. In addition, if elements are
2367 individually comparable, searches of heterogeneous types are allowed
2368 as well: a `double[]` can be searched for an `int` or a $(D
2369 short[]), and conversely a `long` can be searched for a `float`
2370 or a `double[]`. This makes for efficient searches without the need
2371 to coerce one side of the comparison into the other's side type.
2373 The complexity of the search is $(BIGOH haystack.length *
2374 max(needles.length)). (For needles that are individual items, length
2375 is considered to be 1.) The strategy used in searching several
2376 subranges at once maximizes cache usage by moving in `haystack` as
2377 few times as possible.
2379 Tuple
!(Range
, size_t
) find(alias pred
= "a == b", Range
, Ranges
...)
2380 (Range haystack
, Ranges needles
)
2381 if (Ranges
.length
> 1 && is(typeof(startsWith
!pred(haystack
, needles
))))
2383 for (;; haystack
.popFront())
2385 size_t r
= startsWith
!pred(haystack
, needles
);
2386 if (r || haystack
.empty
)
2388 return tuple(haystack
, r
);
2396 import std
.typecons
: tuple
;
2397 int[] a
= [ 1, 4, 2, 3 ];
2398 assert(find(a
, 4) == [ 4, 2, 3 ]);
2399 assert(find(a
, [ 1, 4 ]) == [ 1, 4, 2, 3 ]);
2400 assert(find(a
, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2));
2401 // Mixed types allowed if comparable
2402 assert(find(a
, 5, [ 1.2, 3.5 ], 2.0) == tuple([ 2, 3 ], 3));
2407 auto s1
= "Mary has a little lamb";
2408 assert(find(s1
, "has a", "has an") == tuple("has a little lamb", 1));
2409 assert(find(s1
, 't', "has a", "has an") == tuple("has a little lamb", 2));
2410 assert(find(s1
, 't', "has a", 'y', "has an") == tuple("y has a little lamb", 3));
2411 assert(find("abc", "bc").length
== 2);
2416 import std
.algorithm
.internal
: rndstuff
;
2417 import std
.meta
: AliasSeq
;
2418 import std
.uni
: toUpper
;
2420 int[] a
= [ 1, 2, 3 ];
2421 assert(find(a
, 5).empty
);
2422 assert(find(a
, 2) == [2, 3]);
2424 foreach (T
; AliasSeq
!(int, double))
2426 auto b
= rndstuff
!(T
)();
2427 if (!b
.length
) continue;
2430 assert(find(b
, 200).length
== b
.length
- b
.length
/ 4);
2433 // Case-insensitive find of a string
2434 string
[] s
= [ "Hello", "world", "!" ];
2435 assert(find
!("toUpper(a) == toUpper(b)")(s
, "hello").length
== 3);
2437 static bool f(string a
, string b
) { return toUpper(a
) == toUpper(b
); }
2438 assert(find
!(f
)(s
, "hello").length
== 3);
2443 import std
.algorithm
.comparison
: equal
;
2444 import std
.algorithm
.internal
: rndstuff
;
2445 import std
.meta
: AliasSeq
;
2446 import std
.range
: retro
;
2448 int[] a
= [ 1, 2, 3, 2, 6 ];
2449 assert(find(retro(a
), 5).empty
);
2450 assert(equal(find(retro(a
), 2), [ 2, 3, 2, 1 ][]));
2452 foreach (T
; AliasSeq
!(int, double))
2454 auto b
= rndstuff
!(T
)();
2455 if (!b
.length
) continue;
2458 assert(find(retro(b
), 200).length
==
2459 b
.length
- (b
.length
- 1) / 2);
2465 import std
.algorithm
.comparison
: equal
;
2466 import std
.internal
.test.dummyrange
;
2468 int[] a
= [ -1, 0, 1, 2, 3, 4, 5 ];
2469 int[] b
= [ 1, 2, 3 ];
2470 assert(find(a
, b
) == [ 1, 2, 3, 4, 5 ]);
2471 assert(find(b
, a
).empty
);
2473 foreach (DummyType
; AllDummyRanges
)
2476 auto findRes
= find(d
, 5);
2477 assert(equal(findRes
, [5,6,7,8,9,10]));
2482 * Finds `needle` in `haystack` efficiently using the
2483 * $(LINK2 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm,
2484 * Boyer-Moore) method.
2487 * haystack = A random-access range with length and slicing.
2488 * needle = A $(LREF BoyerMooreFinder).
2491 * `haystack` advanced such that `needle` is a prefix of it (if no
2492 * such position exists, returns `haystack` advanced to termination).
2494 RandomAccessRange
find(RandomAccessRange
, alias pred
, InputRange
)(
2495 RandomAccessRange haystack
, scope BoyerMooreFinder
!(pred
, InputRange
) needle
)
2497 return needle
.beFound(haystack
);
2502 string h
= "/homes/aalexand/d/dmd/bin/../lib/libphobos.a(dmain2.o)"~
2503 "(.gnu.linkonce.tmain+0x74): In function `main' undefined reference"~
2505 string
[] ns
= ["libphobos", "function", " undefined", "`", ":"];
2508 auto p
= find(h
, boyerMooreFinder(n
));
2516 import std
.range
.primitives
: empty
;
2517 int[] a
= [ -1, 0, 1, 2, 3, 4, 5 ];
2518 int[] b
= [ 1, 2, 3 ];
2520 assert(find(a
, boyerMooreFinder(b
)) == [ 1, 2, 3, 4, 5 ]);
2521 assert(find(b
, boyerMooreFinder(a
)).empty
);
2526 auto bm
= boyerMooreFinder("for");
2527 auto match
= find("Moor", bm
);
2528 assert(match
.empty
);
2533 Convenience function. Like find, but only returns whether or not the search
2536 For more information about `pred` see $(LREF find).
2539 $(REF among, std,algorithm,comparison) for checking a value against multiple possibilities.
2541 template canFind(alias pred
="a == b")
2544 Returns `true` if and only if any value `v` found in the
2545 input range `range` satisfies the predicate `pred`.
2546 Performs (at most) $(BIGOH haystack.length) evaluations of `pred`.
2548 bool canFind(Range
)(Range haystack
)
2549 if (is(typeof(find
!pred(haystack
))))
2551 return any
!pred(haystack
);
2555 Returns `true` if and only if `needle` can be found in $(D
2556 range). Performs $(BIGOH haystack.length) evaluations of `pred`.
2558 bool canFind(Range
, Element
)(Range haystack
, scope Element needle
)
2559 if (is(typeof(find
!pred(haystack
, needle
))))
2561 return !find
!pred(haystack
, needle
).empty
;
2565 Returns the 1-based index of the first needle found in `haystack`. If no
2566 needle is found, then `0` is returned.
2568 So, if used directly in the condition of an if statement or loop, the result
2569 will be `true` if one of the needles is found and `false` if none are
2570 found, whereas if the result is used elsewhere, it can either be cast to
2571 `bool` for the same effect or used to get which needle was found first
2572 without having to deal with the tuple that `LREF find` returns for the
2575 size_t
canFind(Range
, Ranges
...)(Range haystack
, scope Ranges needles
)
2576 if (Ranges
.length
> 1 &&
2577 allSatisfy
!(isForwardRange
, Ranges
) &&
2578 is(typeof(find
!pred(haystack
, needles
))))
2580 return find
!pred(haystack
, needles
)[1];
2587 assert(canFind([0, 1, 2, 3], 2) == true);
2588 assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]));
2589 assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]) == 1);
2590 assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]));
2591 assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]) == 2);
2593 assert(canFind([0, 1, 2, 3], 4) == false);
2594 assert(!canFind([0, 1, 2, 3], [1, 3], [2, 4]));
2595 assert(canFind([0, 1, 2, 3], [1, 3], [2, 4]) == 0);
2599 * Example using a custom predicate.
2600 * Note that the needle appears as the second argument of the predicate.
2609 assert(!canFind(words
, "bees"));
2610 assert( canFind
!((string a
, string b
) => a
.startsWith(b
))(words
, "bees"));
2613 /// Search for mutliple items in an array of items (search for needles in an array of hay stacks)
2616 string s1
= "aaa111aaa";
2617 string s2
= "aaa222aaa";
2618 string s3
= "aaa333aaa";
2619 string s4
= "aaa444aaa";
2620 const hay
= [s1
, s2
, s3
, s4
];
2621 assert(hay
.canFind
!(e
=> (e
.canFind("111", "222"))));
2626 import std
.algorithm
.internal
: rndstuff
;
2628 auto a
= rndstuff
!(int)();
2631 auto b
= a
[a
.length
/ 2];
2632 assert(canFind(a
, b
));
2638 import std
.algorithm
.comparison
: equal
;
2639 assert(equal
!(canFind
!"a < b")([[1, 2, 3], [7, 8, 9]], [2, 8]));
2644 Advances `r` until it finds the first two adjacent elements `a`,
2645 `b` that satisfy `pred(a, b)`. Performs $(BIGOH r.length)
2646 evaluations of `pred`.
2648 For more information about `pred` see $(LREF find).
2651 pred = The predicate to satisfy.
2652 r = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to
2656 `r` advanced to the first occurrence of two adjacent elements that satisfy
2657 the given predicate. If there are no such two elements, returns `r` advanced
2661 $(LINK2 http://en.cppreference.com/w/cpp/algorithm/adjacent_find, STL's `adjacent_find`)
2663 Range
findAdjacent(alias pred
= "a == b", Range
)(Range r
)
2664 if (isForwardRange
!(Range
))
2666 auto ahead
= r
.save
;
2669 for (ahead
.popFront(); !ahead
.empty
; r
.popFront(), ahead
.popFront())
2671 if (binaryFun
!(pred
)(r
.front
, ahead
.front
)) return r
;
2674 static if (!isInfinite
!Range
)
2682 int[] a
= [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
2683 auto r
= findAdjacent(a
);
2684 assert(r
== [ 10, 10, 9, 8, 8, 7, 8, 9 ]);
2685 auto p
= findAdjacent
!("a < b")(a
);
2686 assert(p
== [ 7, 8, 9 ]);
2692 import std
.algorithm
.comparison
: equal
;
2693 import std
.internal
.test.dummyrange
;
2696 int[] a
= [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
2697 auto p
= findAdjacent(a
);
2698 assert(p
== [10, 10, 9, 8, 8, 7, 8, 9 ]);
2699 p
= findAdjacent
!("a < b")(a
);
2700 assert(p
== [7, 8, 9]);
2703 p
= findAdjacent(a
);
2706 a
= [ 1, 2, 3, 4, 5 ];
2707 p
= findAdjacent(a
);
2709 p
= findAdjacent
!"a > b"(a
);
2711 ReferenceForwardRange
!int rfr
= new ReferenceForwardRange
!int([1, 2, 3, 2, 2, 3]);
2712 assert(equal(findAdjacent(rfr
), [2, 2, 3]));
2714 // https://issues.dlang.org/show_bug.cgi?id=9350
2715 assert(!repeat(1).findAdjacent().empty
);
2720 Searches the given range for an element that matches one of the given choices.
2722 Advances `seq` by calling `seq.popFront` until either
2723 `find!(pred)(choices, seq.front)` is `true`, or `seq` becomes empty.
2724 Performs $(BIGOH seq.length * choices.length) evaluations of `pred`.
2726 For more information about `pred` see $(LREF find).
2729 pred = The predicate to use for determining a match.
2730 seq = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to
2732 choices = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
2733 of possible choices.
2736 `seq` advanced to the first matching element, or until empty if there are no
2739 See_Also: $(LREF find), $(REF std,algorithm,comparison,among)
2741 InputRange
findAmong(alias pred
= "a == b", InputRange
, ForwardRange
)(
2742 InputRange seq
, ForwardRange choices
)
2743 if (isInputRange
!InputRange
&& isForwardRange
!ForwardRange
)
2745 for (; !seq
.empty
&& find
!pred(choices
.save
, seq
.front
).empty
; seq
.popFront())
2754 int[] a
= [ -1, 0, 1, 2, 3, 4, 5 ];
2755 int[] b
= [ 3, 1, 2 ];
2756 assert(findAmong(a
, b
) == a
[2 .. $]);
2761 int[] a
= [ -1, 0, 2, 1, 2, 3, 4, 5 ];
2762 int[] b
= [ 1, 2, 3 ];
2763 assert(findAmong(a
, b
) == [2, 1, 2, 3, 4, 5 ]);
2764 assert(findAmong(b
, [ 4, 6, 7 ][]).empty
);
2765 assert(findAmong
!("a == b")(a
, b
).length
== a
.length
- 2);
2766 assert(findAmong
!("a == b")(b
, [ 4, 6, 7 ][]).empty
);
2769 // https://issues.dlang.org/show_bug.cgi?id=19765
2772 import std
.range
.interfaces
: inputRangeObject
;
2773 auto choices
= inputRangeObject("b");
2774 auto f
= "foobar".findAmong(choices
);
2780 * Finds `needle` in `haystack` and positions `haystack`
2781 * right after the first occurrence of `needle`.
2783 * If no needle is provided, the `haystack` is advanced as long as `pred`
2784 * evaluates to `true`.
2785 * Similarly, the haystack is positioned so as `pred` evaluates to `false` for
2788 * For more information about `pred` see $(LREF find).
2792 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search
2795 * $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search
2797 * pred = Custom predicate for comparison of haystack and needle
2799 * Returns: `true` if the needle was found, in which case `haystack` is
2800 * positioned after the end of the first occurrence of `needle`; otherwise
2801 * `false`, leaving `haystack` untouched. If no needle is provided, it returns
2802 * the number of times `pred(haystack.front)` returned true.
2804 * See_Also: $(LREF find)
2806 bool findSkip(alias pred
= "a == b", R1
, R2
)(ref R1 haystack
, R2 needle
)
2807 if (isForwardRange
!R1
&& isForwardRange
!R2
2808 && is(typeof(binaryFun
!pred(haystack
.front
, needle
.front
))))
2810 auto parts
= findSplit
!pred(haystack
, needle
);
2811 if (parts
[1].empty
) return false;
2813 haystack
= parts
[2];
2820 import std
.range
.primitives
: empty
;
2821 // Needle is found; s is replaced by the substring following the first
2822 // occurrence of the needle.
2823 string s
= "abcdef";
2824 assert(findSkip(s
, "cd") && s
== "ef");
2826 // Needle is not found; s is left untouched.
2828 assert(!findSkip(s
, "cxd") && s
== "abcdef");
2830 // If the needle occurs at the end of the range, the range is left empty.
2832 assert(findSkip(s
, "def") && s
.empty
);
2835 // https://issues.dlang.org/show_bug.cgi?id=19020
2838 static struct WrapperRange
2841 @property auto empty() { return _r
.empty(); }
2842 @property auto front() { return _r
.front(); }
2843 auto popFront() { return _r
.popFront(); }
2844 @property auto save() { return WrapperRange(_r
.save
); }
2846 auto tmp
= WrapperRange("there is a bug here: *");
2847 assert(!tmp
.findSkip("*/"));
2848 assert(tmp
._r
== "there is a bug here: *");
2852 size_t
findSkip(alias pred
, R1
)(ref R1 haystack
)
2853 if (isForwardRange
!R1
&& ifTestable
!(typeof(haystack
.front
), unaryFun
!pred
))
2856 while (!haystack
.empty
&& unaryFun
!pred(haystack
.front
))
2867 import std
.ascii
: isWhite
;
2869 assert(findSkip
!isWhite(s
) && s
== "abc");
2870 assert(!findSkip
!isWhite(s
) && s
== "abc");
2873 assert(findSkip
!isWhite(s
) == 2);
2878 import std
.ascii
: isWhite
;
2881 assert(findSkip
!isWhite(s
) == 2);
2885 These functions find the first occurrence of `needle` in `haystack` and then
2886 split `haystack` as follows.
2888 `findSplit` returns a tuple `result` containing $(I three) ranges. `result[0]`
2889 is the portion of `haystack` before `needle`, `result[1]` is the portion of
2890 `haystack` that matches `needle`, and `result[2]` is the portion of `haystack`
2891 after the match. If `needle` was not found, `result[0]` comprehends `haystack`
2892 entirely and `result[1]` and `result[2]` are empty.
2894 `findSplitBefore` returns a tuple `result` containing two ranges. `result[0]` is
2895 the portion of `haystack` before `needle`, and `result[1]` is the balance of
2896 `haystack` starting with the match. If `needle` was not found, `result[0]`
2897 comprehends `haystack` entirely and `result[1]` is empty.
2899 `findSplitAfter` returns a tuple `result` containing two ranges.
2900 `result[0]` is the portion of `haystack` up to and including the
2901 match, and `result[1]` is the balance of `haystack` starting
2902 after the match. If `needle` was not found, `result[0]` is empty
2903 and `result[1]` is `haystack`.
2905 In all cases, the concatenation of the returned ranges spans the
2908 If `haystack` is a random-access range, all three components of the tuple have
2909 the same type as `haystack`. Otherwise, `haystack` must be a
2910 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) and
2911 the type of `result[0]` and `result[1]` is the same as $(REF takeExactly,
2914 For more information about `pred` see $(LREF find).
2917 pred = Predicate to use for comparing needle against haystack.
2918 haystack = The range to search.
2919 needle = What to look for.
2923 A sub-type of `Tuple!()` of the split portions of `haystack` (see above for
2924 details). This sub-type of `Tuple!()` has `opCast` defined for `bool`. This
2925 `opCast` returns `true` when the separating `needle` was found
2926 and `false` otherwise.
2928 See_Also: $(LREF find)
2930 auto findSplit(alias pred
= "a == b", R1
, R2
)(R1 haystack
, R2 needle
)
2931 if (isForwardRange
!R1
&& isForwardRange
!R2
)
2933 static struct Result(S1
, S2
) if (isForwardRange
!S1
&&
2936 this(S1 pre
, S1 separator
, S2 post
)
2938 asTuple
= typeof(asTuple
)(pre
, separator
, post
);
2940 void opAssign(typeof(asTuple
) rhs
)
2944 Tuple
!(S1
, S1
, S2
) asTuple
;
2945 static if (hasConstEmptyMember
!(typeof(asTuple
[1])))
2947 bool opCast(T
: bool)() const
2949 return !asTuple
[1].empty
;
2954 bool opCast(T
: bool)()
2956 return !asTuple
[1].empty
;
2962 static if (isSomeString
!R1
&& isSomeString
!R2
2963 ||
(isRandomAccessRange
!R1
&& hasSlicing
!R1
&& hasLength
!R1
&& hasLength
!R2
))
2965 auto balance
= find
!pred(haystack
, needle
);
2966 immutable pos1
= haystack
.length
- balance
.length
;
2967 immutable pos2
= balance
.empty ? pos1
: pos1
+ needle
.length
;
2968 return Result
!(typeof(haystack
[0 .. pos1
]),
2969 typeof(haystack
[pos2
.. haystack
.length
]))(haystack
[0 .. pos1
],
2970 haystack
[pos1
.. pos2
],
2971 haystack
[pos2
.. haystack
.length
]);
2975 import std
.range
: takeExactly
;
2976 auto original
= haystack
.save
;
2977 auto h
= haystack
.save
;
2978 auto n
= needle
.save
;
2980 while (!n
.empty
&& !h
.empty
)
2982 if (binaryFun
!pred(h
.front
, n
.front
))
2990 haystack
.popFront();
2996 if (!n
.empty
) // incomplete match at the end of haystack
3000 return Result
!(typeof(takeExactly(original
, pos1
)),
3001 typeof(h
))(takeExactly(original
, pos1
),
3002 takeExactly(haystack
, pos2
- pos1
),
3008 auto findSplitBefore(alias pred
= "a == b", R1
, R2
)(R1 haystack
, R2 needle
)
3009 if (isForwardRange
!R1
&& isForwardRange
!R2
)
3011 static struct Result(S1
, S2
) if (isForwardRange
!S1
&&
3014 this(S1 pre
, S2 post
)
3016 asTuple
= typeof(asTuple
)(pre
, post
);
3018 void opAssign(typeof(asTuple
) rhs
)
3022 Tuple
!(S1
, S2
) asTuple
;
3023 static if (hasConstEmptyMember
!(typeof(asTuple
[1])))
3025 bool opCast(T
: bool)() const
3027 return !asTuple
[1].empty
;
3032 bool opCast(T
: bool)()
3034 return !asTuple
[1].empty
;
3040 static if (isSomeString
!R1
&& isSomeString
!R2
3041 ||
(isRandomAccessRange
!R1
&& hasLength
!R1
&& hasSlicing
!R1
&& hasLength
!R2
))
3043 auto balance
= find
!pred(haystack
, needle
);
3044 immutable pos
= haystack
.length
- balance
.length
;
3045 return Result
!(typeof(haystack
[0 .. pos
]),
3046 typeof(haystack
[pos
.. haystack
.length
]))(haystack
[0 .. pos
],
3047 haystack
[pos
.. haystack
.length
]);
3051 import std
.range
: takeExactly
;
3052 auto original
= haystack
.save
;
3053 auto h
= haystack
.save
;
3054 auto n
= needle
.save
;
3056 while (!n
.empty
&& !h
.empty
)
3058 if (binaryFun
!pred(h
.front
, n
.front
))
3066 haystack
.popFront();
3072 if (!n
.empty
) // incomplete match at the end of haystack
3077 return Result
!(typeof(takeExactly(original
, pos1
)),
3078 typeof(haystack
))(takeExactly(original
, pos1
),
3084 auto findSplitAfter(alias pred
= "a == b", R1
, R2
)(R1 haystack
, R2 needle
)
3085 if (isForwardRange
!R1
&& isForwardRange
!R2
)
3087 static struct Result(S1
, S2
) if (isForwardRange
!S1
&&
3090 this(S1 pre
, S2 post
)
3092 asTuple
= typeof(asTuple
)(pre
, post
);
3094 void opAssign(typeof(asTuple
) rhs
)
3098 Tuple
!(S1
, S2
) asTuple
;
3099 static if (hasConstEmptyMember
!(typeof(asTuple
[1])))
3101 bool opCast(T
: bool)() const
3103 return !asTuple
[0].empty
;
3108 bool opCast(T
: bool)()
3110 return !asTuple
[0].empty
;
3116 static if (isSomeString
!R1
&& isSomeString
!R2
3117 || isRandomAccessRange
!R1
&& hasLength
!R1
&& hasSlicing
!R1
&& hasLength
!R2
)
3119 auto balance
= find
!pred(haystack
, needle
);
3120 immutable pos
= balance
.empty ?
0 : haystack
.length
- balance
.length
+ needle
.length
;
3121 return Result
!(typeof(haystack
[0 .. pos
]),
3122 typeof(haystack
[pos
.. haystack
.length
]))(haystack
[0 .. pos
],
3123 haystack
[pos
.. haystack
.length
]);
3127 import std
.range
: takeExactly
;
3128 auto original
= haystack
.save
;
3129 auto h
= haystack
.save
;
3130 auto n
= needle
.save
;
3137 return Result
!(typeof(takeExactly(original
, 0)),
3138 typeof(original
))(takeExactly(original
, 0),
3141 if (binaryFun
!pred(h
.front
, n
.front
))
3149 haystack
.popFront();
3155 return Result
!(typeof(takeExactly(original
, pos2
)),
3156 typeof(h
))(takeExactly(original
, pos2
),
3161 /// Returning a subtype of $(REF Tuple, std,typecons) enables
3162 /// the following convenient idiom:
3163 @safe pure nothrow unittest
3165 // findSplit returns a triplet
3166 if (auto split
= "dlang-rocks".findSplit("-"))
3168 assert(split
[0] == "dlang");
3169 assert(split
[1] == "-");
3170 assert(split
[2] == "rocks");
3174 // works with const aswell
3175 if (const split
= "dlang-rocks".findSplit("-"))
3177 assert(split
[0] == "dlang");
3178 assert(split
[1] == "-");
3179 assert(split
[2] == "rocks");
3185 @safe pure nothrow unittest
3187 import std
.range
.primitives
: empty
;
3189 auto a
= "Carl Sagan Memorial Station";
3190 auto r
= findSplit(a
, "Velikovsky");
3191 import std
.typecons
: isTuple
;
3192 static assert(isTuple
!(typeof(r
.asTuple
)));
3193 static assert(isTuple
!(typeof(r
)));
3198 r
= findSplit(a
, " ");
3199 assert(r
[0] == "Carl");
3200 assert(r
[1] == " ");
3201 assert(r
[2] == "Sagan Memorial Station");
3202 if (const r1
= findSplitBefore(a
, "Sagan"))
3205 assert(r1
[0] == "Carl ");
3206 assert(r1
[1] == "Sagan Memorial Station");
3208 if (const r2
= findSplitAfter(a
, "Sagan"))
3211 assert(r2
[0] == "Carl Sagan");
3212 assert(r2
[1] == " Memorial Station");
3216 /// Use $(REF only, std,range) to find single elements:
3217 @safe pure nothrow unittest
3219 import std
.range
: only
;
3220 assert([1, 2, 3, 4].findSplitBefore(only(3))[0] == [1, 2]);
3223 @safe pure nothrow unittest
3225 import std
.range
.primitives
: empty
;
3227 immutable a
= [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3228 auto r
= findSplit(a
, [9, 1]);
3233 r
= findSplit(a
, [3]);
3235 assert(r
[0] == a
[0 .. 2]);
3236 assert(r
[1] == a
[2 .. 3]);
3237 assert(r
[2] == a
[3 .. $]);
3240 const r1
= findSplitBefore(a
, [9, 1]);
3243 assert(r1
[1].empty
);
3246 if (immutable r1
= findSplitBefore(a
, [3, 4]))
3249 assert(r1
[0] == a
[0 .. 2]);
3250 assert(r1
[1] == a
[2 .. $]);
3255 const r2
= findSplitAfter(a
, [9, 1]);
3257 assert(r2
[0].empty
);
3261 if (immutable r3
= findSplitAfter(a
, [3, 4]))
3264 assert(r3
[0] == a
[0 .. 4]);
3265 assert(r3
[1] == a
[4 .. $]);
3270 @safe pure nothrow unittest
3272 import std
.algorithm
.comparison
: equal
;
3273 import std
.algorithm
.iteration
: filter
;
3275 auto a
= [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3276 auto fwd
= filter
!"a > 0"(a
);
3277 auto r
= findSplit(fwd
, [9, 1]);
3279 assert(equal(r
[0], a
));
3282 r
= findSplit(fwd
, [3]);
3284 assert(equal(r
[0], a
[0 .. 2]));
3285 assert(equal(r
[1], a
[2 .. 3]));
3286 assert(equal(r
[2], a
[3 .. $]));
3287 r
= findSplit(fwd
, [8, 9]);
3289 assert(equal(r
[0], a
));
3293 // auto variable `r2` cannot be `const` because `fwd.front` is mutable
3295 auto r1
= findSplitBefore(fwd
, [9, 1]);
3297 assert(equal(r1
[0], a
));
3298 assert(r1
[1].empty
);
3301 if (auto r1
= findSplitBefore(fwd
, [3, 4]))
3304 assert(equal(r1
[0], a
[0 .. 2]));
3305 assert(equal(r1
[1], a
[2 .. $]));
3310 auto r1
= findSplitBefore(fwd
, [8, 9]);
3312 assert(equal(r1
[0], a
));
3313 assert(r1
[1].empty
);
3317 auto r2
= findSplitAfter(fwd
, [9, 1]);
3319 assert(r2
[0].empty
);
3320 assert(equal(r2
[1], a
));
3323 if (auto r2
= findSplitAfter(fwd
, [3, 4]))
3326 assert(equal(r2
[0], a
[0 .. 4]));
3327 assert(equal(r2
[1], a
[4 .. $]));
3332 auto r2
= findSplitAfter(fwd
, [8, 9]);
3334 assert(r2
[0].empty
);
3335 assert(equal(r2
[1], a
));
3339 @safe pure nothrow @nogc unittest
3341 auto str = "sep,one,sep,two";
3343 auto split
= str.findSplitAfter(",");
3344 assert(split
[0] == "sep,");
3346 split
= split
[1].findSplitAfter(",");
3347 assert(split
[0] == "one,");
3349 split
= split
[1].findSplitBefore(",");
3350 assert(split
[0] == "sep");
3353 @safe pure nothrow @nogc unittest
3355 auto str = "sep,one,sep,two";
3357 auto split
= str.findSplitBefore(",two");
3358 assert(split
[0] == "sep,one,sep");
3359 assert(split
[1] == ",two");
3361 split
= split
[0].findSplitBefore(",sep");
3362 assert(split
[0] == "sep,one");
3363 assert(split
[1] == ",sep");
3365 split
= split
[0].findSplitAfter(",");
3366 assert(split
[0] == "sep,");
3367 assert(split
[1] == "one");
3370 // https://issues.dlang.org/show_bug.cgi?id=11013
3374 auto split
= var
.findSplitBefore
!q
{a
== a
}(var
);
3375 assert(split
[0] == "");
3376 assert(split
[1] == "abc");
3382 Computes the minimum (respectively maximum) of `range` along with its number of
3383 occurrences. Formally, the minimum is a value `x` in `range` such that $(D
3384 pred(a, x)) is `false` for all values `a` in `range`. Conversely, the maximum is
3385 a value `x` in `range` such that `pred(x, a)` is `false` for all values `a`
3386 in `range` (note the swapped arguments to `pred`).
3388 These functions may be used for computing arbitrary extrema by choosing `pred`
3389 appropriately. For corrrect functioning, `pred` must be a strict partial order,
3390 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and
3391 irreflexive (`pred(a, a)` is `false`). The $(LUCKY trichotomy property of
3392 inequality) is not required: these algorithms consider elements `a` and `b` equal
3393 (for the purpose of counting) if `pred` puts them in the same equivalence class,
3394 i.e. `!pred(a, b) && !pred(b, a)`.
3397 pred = The ordering predicate to use to determine the extremum (minimum
3399 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to count.
3401 Returns: The minimum, respectively maximum element of a range together with the
3402 number it occurs in the range.
3404 Limitations: If at least one of the arguments is NaN, the result is
3405 an unspecified value. See $(REF maxElement, std,algorithm,searching)
3406 for examples on how to cope with NaNs.
3408 Throws: `Exception` if `range.empty`.
3410 See_Also: $(REF min, std,algorithm,comparison), $(LREF minIndex), $(LREF minElement), $(LREF minPos)
3412 Tuple
!(ElementType
!Range
, size_t
)
3413 minCount(alias pred
= "a < b", Range
)(Range range
)
3414 if (isInputRange
!Range
&& !isInfinite
!Range
&&
3415 is(typeof(binaryFun
!pred(range
.front
, range
.front
))))
3417 import std
.algorithm
.internal
: algoFormat
;
3418 import std
.exception
: enforce
;
3420 alias T
= ElementType
!Range
;
3421 alias UT
= Unqual
!T
;
3422 alias RetType
= Tuple
!(T
, size_t
);
3424 static assert(is(typeof(RetType(range
.front
, 1))),
3425 algoFormat("Error: Cannot call minCount on a %s, because it is not possible "~
3426 "to copy the result value (a %s) into a Tuple.", Range
.stringof
, T
.stringof
));
3428 enforce(!range
.empty
, "Can't count elements from an empty range");
3429 size_t occurrences
= 1;
3431 static if (isForwardRange
!Range
)
3433 Range least
= range
.save
;
3434 for (range
.popFront(); !range
.empty
; range
.popFront())
3436 if (binaryFun
!pred(least
.front
, range
.front
))
3438 assert(!binaryFun
!pred(range
.front
, least
.front
),
3439 "min/maxPos: predicate must be a strict partial order.");
3442 if (binaryFun
!pred(range
.front
, least
.front
))
3451 return RetType(least
.front
, occurrences
);
3453 else static if (isAssignable
!(UT
, T
) ||
(!hasElaborateAssign
!UT
&& isAssignable
!UT
))
3456 static if (isAssignable
!(UT
, T
)) v
= range
.front
;
3457 else v
= cast(UT
) range
.front
;
3459 for (range
.popFront(); !range
.empty
; range
.popFront())
3461 if (binaryFun
!pred(*cast(T
*)&v
, range
.front
)) continue;
3462 if (binaryFun
!pred(range
.front
, *cast(T
*)&v
))
3465 static if (isAssignable
!(UT
, T
)) v
= range
.front
;
3466 else v
= cast(UT
) range
.front
; //Safe because !hasElaborateAssign!UT
3472 return RetType(*cast(T
*)&v
, occurrences
);
3474 else static if (hasLvalueElements
!Range
)
3476 import std
.algorithm
.internal
: addressOf
;
3477 T
* p
= addressOf(range
.front
);
3478 for (range
.popFront(); !range
.empty
; range
.popFront())
3480 if (binaryFun
!pred(*p
, range
.front
)) continue;
3481 if (binaryFun
!pred(range
.front
, *p
))
3484 p
= addressOf(range
.front
);
3490 return RetType(*p
, occurrences
);
3493 static assert(false,
3494 algoFormat("Sorry, can't find the minCount of a %s: Don't know how "~
3495 "to keep track of the smallest %s element.", Range
.stringof
, T
.stringof
));
3499 Tuple
!(ElementType
!Range
, size_t
)
3500 maxCount(alias pred
= "a < b", Range
)(Range range
)
3501 if (isInputRange
!Range
&& !isInfinite
!Range
&&
3502 is(typeof(binaryFun
!pred(range
.front
, range
.front
))))
3504 return range
.minCount
!((a
, b
) => binaryFun
!pred(b
, a
));
3510 import std
.conv
: text
;
3511 import std
.typecons
: tuple
;
3513 int[] a
= [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3514 // Minimum is 1 and occurs 3 times
3515 assert(a
.minCount
== tuple(1, 3));
3516 // Maximum is 4 and occurs 2 times
3517 assert(a
.maxCount
== tuple(4, 2));
3522 import std
.conv
: text
;
3523 import std
.exception
: assertThrown
;
3524 import std
.internal
.test.dummyrange
;
3526 int[][] b
= [ [4], [2, 4], [4], [4] ];
3527 auto c
= minCount
!("a[0] < b[0]")(b
);
3528 assert(c
== tuple([2, 4], 1), text(c
[0]));
3531 assertThrown(minCount(b
[$..$]));
3533 //test with reference ranges. Test both input and forward.
3534 assert(minCount(new ReferenceInputRange
!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2));
3535 assert(minCount(new ReferenceForwardRange
!int([1, 2, 1, 0, 2, 0])) == tuple(0, 2));
3540 import std
.conv
: text
;
3541 import std
.meta
: AliasSeq
;
3543 static struct R(T
) //input range
3549 immutable a
= [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3550 R
!(immutable int) b
= R
!(immutable int)(a
);
3552 assert(minCount(a
) == tuple(1, 3));
3553 assert(minCount(b
) == tuple(1, 3));
3554 assert(minCount
!((ref immutable int a
, ref immutable int b
) => (a
> b
))(a
) == tuple(4, 2));
3555 assert(minCount
!((ref immutable int a
, ref immutable int b
) => (a
> b
))(b
) == tuple(4, 2));
3557 immutable(int[])[] c
= [ [4], [2, 4], [4], [4] ];
3558 assert(minCount
!("a[0] < b[0]")(c
) == tuple([2, 4], 1), text(c
[0]));
3564 alias IS1
= immutable(S1
);
3565 static assert( isAssignable
!S1
);
3566 static assert( isAssignable
!(S1
, IS1
));
3571 this(ref immutable int i
) immutable {p
= &i
;}
3572 this(ref int i
) {p
= &i
;}
3573 @property ref inout(int) i() inout {return *p
;}
3574 bool opEquals(const S2 other
) const {return i
== other
.i
;}
3576 alias IS2
= immutable(S2
);
3577 static assert( isAssignable
!S2
);
3578 static assert(!isAssignable
!(S2
, IS2
));
3579 static assert(!hasElaborateAssign
!S2
);
3584 void opAssign(ref S3 other
) @disable;
3586 static assert(!isAssignable
!S3
);
3588 static foreach (Type
; AliasSeq
!(S1
, IS1
, S2
, IS2
, S3
))
3590 static if (is(Type
== immutable)) alias V
= immutable int;
3593 auto r1
= [Type(two
), Type(one
), Type(one
)];
3594 auto r2
= R
!Type(r1
);
3595 assert(minCount
!"a.i < b.i"(r1
) == tuple(Type(one
), 2));
3596 assert(minCount
!"a.i < b.i"(r2
) == tuple(Type(one
), 2));
3597 assert(one
== 1 && two
== 2);
3602 Iterates the passed range and returns the minimal element.
3603 A custom mapping function can be passed to `map`.
3604 In other languages this is sometimes called `argmin`.
3607 Exactly `n - 1` comparisons are needed.
3610 map = custom accessor for the comparison key
3611 r = range from which the minimal element will be selected
3612 seed = custom seed to use as initial element
3614 Precondition: If a seed is not given, `r` must not be empty.
3616 Returns: The minimal element of the passed-in range.
3619 If at least one of the arguments is NaN, the result is an unspecified value.
3621 If you want to ignore NaNs, you can use $(REF filter, std,algorithm,iteration)
3622 and $(REF isNaN, std,math) to remove them, before applying minElement.
3623 Add a suitable seed, to avoid error messages if all elements are NaNs:
3626 <range>.filter!(a=>!a.isNaN).minElement(<seed>);
3629 If you want to get NaN as a result if a NaN is present in the range,
3630 you can use $(REF fold, std,algorithm,iteration) and $(REF isNaN, std,math):
3633 <range>.fold!((a,b)=>a.isNaN || b.isNaN ? real.nan : a < b ? a : b);
3638 $(LREF maxElement), $(REF min, std,algorithm,comparison), $(LREF minCount),
3639 $(LREF minIndex), $(LREF minPos)
3641 auto minElement(alias map
= (a
=> a
), Range
)(Range r
)
3642 if (isInputRange
!Range
&& !isInfinite
!Range
)
3644 return extremum
!map(r
);
3648 auto minElement(alias map
= (a
=> a
), Range
, RangeElementType
= ElementType
!Range
)
3649 (Range r
, RangeElementType seed
)
3650 if (isInputRange
!Range
&& !isInfinite
!Range
&&
3651 !is(CommonType
!(ElementType
!Range
, RangeElementType
) == void))
3653 return extremum
!map(r
, seed
);
3659 import std
.range
: enumerate
;
3660 import std
.typecons
: tuple
;
3662 assert([2, 7, 1, 3].minElement
== 1);
3664 // allows to get the index of an element too
3665 assert([5, 3, 7, 9].enumerate
.minElement
!"a.value" == tuple(1, 3));
3667 // any custom accessor can be passed
3668 assert([[0, 4], [1, 2]].minElement
!"a[1]" == [1, 2]);
3672 assert(arr
.minElement(1) == 1);
3677 import std
.range
: enumerate
, iota
;
3679 assert([3, 4, 5, 1, 2].enumerate
.minElement
!"a.value" == tuple(3, 1));
3680 assert([5, 2, 4].enumerate
.minElement
!"a.value" == tuple(1, 2));
3683 assert(iota(1, 5).minElement() == 1);
3684 assert(iota(2, 5).enumerate
.minElement
!"a.value" == tuple(0, 2));
3686 // should work with const
3687 const(int)[] immArr
= [2, 1, 3];
3688 assert(immArr
.minElement
== 1);
3690 // should work with immutable
3691 immutable(int)[] immArr2
= [2, 1, 3];
3692 assert(immArr2
.minElement
== 1);
3695 assert(["b", "a", "c"].minElement
== "a");
3697 // with all dummy ranges
3698 import std
.internal
.test.dummyrange
;
3699 foreach (DummyType
; AllDummyRanges
)
3702 assert(d
.minElement
== 1);
3703 assert(d
.minElement
!(a
=> a
) == 1);
3704 assert(d
.minElement
!(a
=> -a
) == 10);
3707 // with empty, but seeded ranges
3709 assert(arr
.minElement(42) == 42);
3710 assert(arr
.minElement
!(a
=> a
)(42) == 42);
3713 @nogc @safe nothrow pure unittest
3715 static immutable arr
= [7, 3, 4, 2, 1, 8];
3716 assert(arr
.minElement
== 1);
3718 static immutable arr2d
= [[1, 9], [3, 1], [4, 2]];
3719 assert(arr2d
.minElement
!"a[1]" == arr2d
[1]);
3722 // https://issues.dlang.org/show_bug.cgi?id=17982
3730 const(A
)[] v
= [A(0)];
3731 assert(v
.minElement
!"a.val" == A(0));
3734 // https://issues.dlang.org/show_bug.cgi?id=17982
3740 this(int val
){ this.val
= val
; }
3743 const(B
) doStuff(const(B
)[] v
)
3745 return v
.minElement
!"a.val";
3747 assert(doStuff([new B(1), new B(0), new B(2)]).val
== 0);
3749 const(B
)[] arr
= [new B(0), new B(1)];
3750 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
3751 assert(arr
.minElement
!"a.val".val
== 0);
3755 Iterates the passed range and returns the maximal element.
3756 A custom mapping function can be passed to `map`.
3757 In other languages this is sometimes called `argmax`.
3760 Exactly `n - 1` comparisons are needed.
3763 map = custom accessor for the comparison key
3764 r = range from which the maximum element will be selected
3765 seed = custom seed to use as initial element
3767 Precondition: If a seed is not given, `r` must not be empty.
3769 Returns: The maximal element of the passed-in range.
3772 If at least one of the arguments is NaN, the result is an unspecified value.
3773 See $(REF minElement, std,algorithm,searching) for examples on how to cope
3778 $(LREF minElement), $(REF max, std,algorithm,comparison), $(LREF maxCount),
3779 $(LREF maxIndex), $(LREF maxPos)
3781 auto maxElement(alias map
= (a
=> a
), Range
)(Range r
)
3782 if (isInputRange
!Range
&& !isInfinite
!Range
)
3784 return extremum
!(map
, "a > b")(r
);
3788 auto maxElement(alias map
= (a
=> a
), Range
, RangeElementType
= ElementType
!Range
)
3789 (Range r
, RangeElementType seed
)
3790 if (isInputRange
!Range
&& !isInfinite
!Range
&&
3791 !is(CommonType
!(ElementType
!Range
, RangeElementType
) == void))
3793 return extremum
!(map
, "a > b")(r
, seed
);
3799 import std
.range
: enumerate
;
3800 import std
.typecons
: tuple
;
3801 assert([2, 1, 4, 3].maxElement
== 4);
3803 // allows to get the index of an element too
3804 assert([2, 1, 4, 3].enumerate
.maxElement
!"a.value" == tuple(2, 4));
3806 // any custom accessor can be passed
3807 assert([[0, 4], [1, 2]].maxElement
!"a[1]" == [0, 4]);
3811 assert(arr
.minElement(1) == 1);
3816 import std
.range
: enumerate
, iota
;
3819 assert([3, 4, 5, 1, 2].enumerate
.maxElement
!"a.value" == tuple(2, 5));
3820 assert([5, 2, 4].enumerate
.maxElement
!"a.value" == tuple(0, 5));
3823 assert(iota(1, 5).maxElement() == 4);
3824 assert(iota(2, 5).enumerate
.maxElement
!"a.value" == tuple(2, 4));
3825 assert(iota(4, 14).enumerate
.maxElement
!"a.value" == tuple(9, 13));
3827 // should work with const
3828 const(int)[] immArr
= [2, 3, 1];
3829 assert(immArr
.maxElement
== 3);
3831 // should work with immutable
3832 immutable(int)[] immArr2
= [2, 3, 1];
3833 assert(immArr2
.maxElement
== 3);
3836 assert(["a", "c", "b"].maxElement
== "c");
3838 // with all dummy ranges
3839 import std
.internal
.test.dummyrange
;
3840 foreach (DummyType
; AllDummyRanges
)
3843 assert(d
.maxElement
== 10);
3844 assert(d
.maxElement
!(a
=> a
) == 10);
3845 assert(d
.maxElement
!(a
=> -a
) == 1);
3848 // with empty, but seeded ranges
3850 assert(arr
.maxElement(42) == 42);
3851 assert(arr
.maxElement
!(a
=> a
)(42) == 42);
3855 @nogc @safe nothrow pure unittest
3857 static immutable arr
= [7, 3, 8, 2, 1, 4];
3858 assert(arr
.maxElement
== 8);
3860 static immutable arr2d
= [[1, 3], [3, 9], [4, 2]];
3861 assert(arr2d
.maxElement
!"a[1]" == arr2d
[1]);
3864 // https://issues.dlang.org/show_bug.cgi?id=17982
3870 this(int val
){ this.val
= val
; }
3873 const(B
) doStuff(const(B
)[] v
)
3875 return v
.maxElement
!"a.val";
3877 assert(doStuff([new B(1), new B(0), new B(2)]).val
== 2);
3879 const(B
)[] arr
= [new B(0), new B(1)];
3880 // can't compare directly - https://issues.dlang.org/show_bug.cgi?id=1824
3881 assert(arr
.maxElement
!"a.val".val
== 1);
3884 // https://issues.dlang.org/show_bug.cgi?id=23993
3887 import std
.bigint
: BigInt
;
3889 assert([BigInt(2), BigInt(3)].maxElement
== BigInt(3));
3894 Computes a subrange of `range` starting at the first occurrence of `range`'s
3895 minimum (respectively maximum) and with the same ending as `range`, or the
3896 empty range if `range` itself is empty.
3898 Formally, the minimum is a value `x` in `range` such that `pred(a, x)` is
3899 `false` for all values `a` in `range`. Conversely, the maximum is a value `x` in
3900 `range` such that `pred(x, a)` is `false` for all values `a` in `range` (note
3901 the swapped arguments to `pred`).
3903 These functions may be used for computing arbitrary extrema by choosing `pred`
3904 appropriately. For corrrect functioning, `pred` must be a strict partial order,
3905 i.e. transitive (if `pred(a, b) && pred(b, c)` then `pred(a, c)`) and
3906 irreflexive (`pred(a, a)` is `false`).
3909 pred = The ordering predicate to use to determine the extremum (minimum or
3911 range = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to search.
3913 Returns: The position of the minimum (respectively maximum) element of forward
3914 range `range`, i.e. a subrange of `range` starting at the position of its
3915 smallest (respectively largest) element and with the same ending as `range`.
3917 Limitations: If at least one of the arguments is NaN, the result is
3918 an unspecified value. See $(REF maxElement, std,algorithm,searching)
3919 for examples on how to cope with NaNs.
3922 $(REF max, std,algorithm,comparison), $(LREF minCount), $(LREF minIndex), $(LREF minElement)
3924 Range
minPos(alias pred
= "a < b", Range
)(Range range
)
3925 if (isForwardRange
!Range
&& !isInfinite
!Range
&&
3926 is(typeof(binaryFun
!pred(range
.front
, range
.front
))))
3928 static if (hasSlicing
!Range
&& isRandomAccessRange
!Range
&& hasLength
!Range
)
3930 // Prefer index-based access
3932 foreach (i
; 1 .. range
.length
)
3934 if (binaryFun
!pred(range
[i
], range
[pos
]))
3939 return range
[pos
.. range
.length
];
3943 auto result
= range
.save
;
3944 if (range
.empty
) return result
;
3945 for (range
.popFront(); !range
.empty
; range
.popFront())
3947 // Note: Unlike minCount, we do not care to find equivalence, so a
3948 // single pred call is enough.
3949 if (binaryFun
!pred(range
.front
, result
.front
))
3952 result
= range
.save
;
3960 Range
maxPos(alias pred
= "a < b", Range
)(Range range
)
3961 if (isForwardRange
!Range
&& !isInfinite
!Range
&&
3962 is(typeof(binaryFun
!pred(range
.front
, range
.front
))))
3964 return range
.minPos
!((a
, b
) => binaryFun
!pred(b
, a
));
3970 int[] a
= [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3971 // Minimum is 1 and first occurs in position 3
3972 assert(a
.minPos
== [ 1, 2, 4, 1, 1, 2 ]);
3973 // Maximum is 4 and first occurs in position 2
3974 assert(a
.maxPos
== [ 4, 1, 2, 4, 1, 1, 2 ]);
3979 import std
.algorithm
.comparison
: equal
;
3980 import std
.internal
.test.dummyrange
;
3982 int[] a
= [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
3983 //Test that an empty range works
3985 assert(equal(minPos(b
), b
));
3987 //test with reference range.
3988 assert( equal( minPos(new ReferenceForwardRange
!int([1, 2, 1, 0, 2, 0])), [0, 2, 0] ) );
3994 import std
.algorithm
.comparison
: equal
;
3995 import std
.container
: Array
;
3997 assert(Array
!int(2, 3, 4, 1, 2, 4, 1, 1, 2)
4000 .equal([ 1, 2, 4, 1, 1, 2 ]));
4006 immutable a
= [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
4007 // Minimum is 1 and first occurs in position 3
4008 assert(minPos(a
) == [ 1, 2, 4, 1, 1, 2 ]);
4009 // Maximum is 4 and first occurs in position 5
4010 assert(minPos
!("a > b")(a
) == [ 4, 1, 2, 4, 1, 1, 2 ]);
4012 immutable(int[])[] b
= [ [4], [2, 4], [4], [4] ];
4013 assert(minPos
!("a[0] < b[0]")(b
) == [ [2, 4], [4], [4] ]);
4017 Computes the index of the first occurrence of `range`'s minimum element.
4020 pred = The ordering predicate to use to determine the minimum element.
4021 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
4024 Complexity: $(BIGOH range.length)
4025 Exactly `range.length - 1` comparisons are needed.
4028 The index of the first encounter of the minimum element in `range`. If the
4029 `range` is empty, -1 is returned.
4032 If at least one of the arguments is NaN, the result is
4033 an unspecified value. See $(REF maxElement, std,algorithm,searching)
4034 for examples on how to cope with NaNs.
4037 $(LREF maxIndex), $(REF min, std,algorithm,comparison), $(LREF minCount), $(LREF minElement), $(LREF minPos)
4039 ptrdiff_t
minIndex(alias pred
= "a < b", Range
)(Range range
)
4040 if (isInputRange
!Range
&& !isInfinite
!Range
&&
4041 is(typeof(binaryFun
!pred(range
.front
, range
.front
))))
4043 if (range
.empty
) return -1;
4045 ptrdiff_t minPos
= 0;
4047 static if (isRandomAccessRange
!Range
&& hasLength
!Range
)
4049 foreach (i
; 1 .. range
.length
)
4051 if (binaryFun
!pred(range
[i
], range
[minPos
]))
4059 ptrdiff_t curPos
= 0;
4060 Unqual
!(typeof(range
.front
)) min
= range
.front
;
4061 for (range
.popFront(); !range
.empty
; range
.popFront())
4064 if (binaryFun
!pred(range
.front
, min
))
4075 @safe pure nothrow unittest
4077 int[] a
= [2, 3, 4, 1, 2, 4, 1, 1, 2];
4079 // Minimum is 1 and first occurs in position 3
4080 assert(a
.minIndex
== 3);
4081 // Get maximum index with minIndex
4082 assert(a
.minIndex
!"a > b" == 2);
4084 // Range is empty, so return value is -1
4086 assert(b
.minIndex
== -1);
4088 // Works with more custom types
4089 struct Dog
{ int age
; }
4090 Dog
[] dogs
= [Dog(10), Dog(5), Dog(15)];
4091 assert(dogs
.minIndex
!"a.age < b.age" == 1);
4096 // should work with const
4097 const(int)[] immArr
= [2, 1, 3];
4098 assert(immArr
.minIndex
== 1);
4100 // Works for const ranges too
4101 const int[] c
= [2, 5, 4, 1, 2, 3];
4102 assert(c
.minIndex
== 3);
4104 // should work with immutable
4105 immutable(int)[] immArr2
= [2, 1, 3];
4106 assert(immArr2
.minIndex
== 1);
4109 assert(["b", "a", "c"].minIndex
== 1);
4112 import std
.range
: cycle
;
4113 static assert(!__traits(compiles
, cycle([1]).minIndex
));
4115 // with all dummy ranges
4116 import std
.internal
.test.dummyrange
: AllDummyRanges
;
4117 foreach (DummyType
; AllDummyRanges
)
4119 static if (isForwardRange
!DummyType
&& !isInfinite
!DummyType
)
4122 d
.arr
= [5, 3, 7, 2, 1, 4];
4123 assert(d
.minIndex
== 4);
4126 assert(d
.minIndex
== -1);
4131 @nogc @safe nothrow pure unittest
4133 static immutable arr
= [7, 3, 8, 2, 1, 4];
4134 assert(arr
.minIndex
== 4);
4136 static immutable arr2d
= [[1, 3], [3, 9], [4, 2]];
4137 assert(arr2d
.minIndex
!"a[1] < b[1]" == 2);
4140 @safe nothrow pure unittest
4144 static struct InRange
4146 @property int front()
4153 return arr
.length
== index
;
4165 static assert(isInputRange
!InRange
);
4167 auto arr1
= InRange([5, 2, 3, 4, 5, 3, 6]);
4168 auto arr2
= InRange([7, 3, 8, 2, 1, 4]);
4170 assert(arr1
.minIndex
== 1);
4171 assert(arr2
.minIndex
== 4);
4175 Computes the index of the first occurrence of `range`'s maximum element.
4177 Complexity: $(BIGOH range)
4178 Exactly `range.length - 1` comparisons are needed.
4181 pred = The ordering predicate to use to determine the maximum element.
4182 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to search.
4185 The index of the first encounter of the maximum in `range`. If the
4186 `range` is empty, -1 is returned.
4189 If at least one of the arguments is NaN, the result is
4190 an unspecified value. See $(REF maxElement, std,algorithm,searching)
4191 for examples on how to cope with NaNs.
4194 $(LREF minIndex), $(REF max, std,algorithm,comparison), $(LREF maxCount), $(LREF maxElement), $(LREF maxPos)
4196 ptrdiff_t
maxIndex(alias pred
= "a < b", Range
)(Range range
)
4197 if (isInputRange
!Range
&& !isInfinite
!Range
&&
4198 is(typeof(binaryFun
!pred(range
.front
, range
.front
))))
4200 return range
.minIndex
!((a
, b
) => binaryFun
!pred(b
, a
));
4204 @safe pure nothrow unittest
4206 // Maximum is 4 and first occurs in position 2
4207 int[] a
= [2, 3, 4, 1, 2, 4, 1, 1, 2];
4208 assert(a
.maxIndex
== 2);
4212 assert(b
.maxIndex
== -1);
4214 // Works with more custom types
4215 struct Dog
{ int age
; }
4216 Dog
[] dogs
= [Dog(10), Dog(15), Dog(5)];
4217 assert(dogs
.maxIndex
!"a.age < b.age" == 1);
4222 // should work with const
4223 const(int)[] immArr
= [5, 1, 3];
4224 assert(immArr
.maxIndex
== 0);
4226 // Works for const ranges too
4227 const int[] c
= [2, 5, 4, 1, 2, 3];
4228 assert(c
.maxIndex
== 1);
4231 // should work with immutable
4232 immutable(int)[] immArr2
= [2, 1, 3];
4233 assert(immArr2
.maxIndex
== 2);
4236 assert(["b", "a", "c"].maxIndex
== 2);
4239 import std
.range
: cycle
;
4240 static assert(!__traits(compiles
, cycle([1]).maxIndex
));
4242 // with all dummy ranges
4243 import std
.internal
.test.dummyrange
: AllDummyRanges
;
4244 foreach (DummyType
; AllDummyRanges
)
4246 static if (isForwardRange
!DummyType
&& !isInfinite
!DummyType
)
4250 d
.arr
= [5, 3, 7, 2, 1, 4];
4251 assert(d
.maxIndex
== 2);
4254 assert(d
.maxIndex
== -1);
4259 @nogc @safe nothrow pure unittest
4261 static immutable arr
= [7, 3, 8, 2, 1, 4];
4262 assert(arr
.maxIndex
== 2);
4264 static immutable arr2d
= [[1, 3], [3, 9], [4, 2]];
4265 assert(arr2d
.maxIndex
!"a[1] < b[1]" == 1);
4269 Skip over the initial portion of the first given range (`haystack`) that matches
4270 any of the additionally given ranges (`needles`) fully, or
4271 if no second range is given skip over the elements that fulfill pred.
4272 Do nothing if there is no match.
4275 pred = The predicate that determines whether elements from each respective
4276 range match. Defaults to equality `"a == b"`.
4278 template skipOver(alias pred
= (a
, b
) => a
== b
)
4280 enum bool isPredComparable(T
) = ifTestable
!(T
, binaryFun
!pred
);
4284 haystack = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to
4286 needles = The $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives)
4287 representing the prefix of `r1` to skip over.
4288 es = The element to match.
4291 `true` if the prefix of `haystack` matches any range of `needles` fully
4292 or `pred` evaluates to true, and `haystack` has been advanced to the point past this segment;
4293 otherwise false, and `haystack` is left in its original position.
4296 By definition, empty ranges are matched fully and if `needles` contains an empty range,
4297 `skipOver` will return `true`.
4299 bool skipOver(Haystack
, Needles
...)(ref Haystack haystack
, Needles needles
)
4300 if (is(typeof(binaryFun
!pred(haystack
.front
, needles
[0].front
))) &&
4301 isForwardRange
!Haystack
&&
4302 allSatisfy
!(isInputRange
, Needles
) &&
4303 !is(CommonType
!(staticMap
!(ElementType
, staticMap
!(Unqual
, Needles
))) == void))
4305 static if (__traits(isSame
, pred
, (a
, b
) => a
== b
)
4306 && is(typeof(haystack
[0 .. $] == needles
[0]) : bool)
4307 && is(typeof(haystack
= haystack
[0 .. $]))
4308 && hasLength
!Haystack
&& allSatisfy
!(hasLength
, Needles
))
4310 ptrdiff_t longestMatch
= -1;
4311 static foreach (r2
; needles
)
4313 if (r2
.length
<= haystack
.length
&& longestMatch
< ptrdiff_t(r2
.length
)
4314 && (haystack
[0 .. r2
.length
] == r2 || r2
.length
== 0))
4315 longestMatch
= r2
.length
;
4317 if (longestMatch
>= 0)
4319 if (longestMatch
> 0)
4320 haystack
= haystack
[longestMatch
.. $];
4328 import std
.algorithm
.comparison
: min
;
4329 auto r
= haystack
.save
;
4331 static if (hasLength
!Haystack
&& allSatisfy
!(hasLength
, Needles
))
4333 import std
.algorithm
.iteration
: map
;
4334 import std
.algorithm
.searching
: minElement
;
4335 import std
.range
: only
;
4336 // Shortcut opportunity!
4337 if (needles
.only
.map
!(a
=> a
.length
).minElement
> haystack
.length
)
4341 // compatibility: return true if any range was empty
4342 bool hasEmptyRanges
;
4343 static foreach (i
, r2
; needles
)
4346 hasEmptyRanges
= true;
4349 bool hasNeedleMatch
;
4350 size_t inactiveNeedlesLen
;
4351 bool[Needles
.length
] inactiveNeedles
;
4352 for (; !r
.empty
; r
.popFront
)
4354 static foreach (i
, r2
; needles
)
4356 if (!r2
.empty
&& !inactiveNeedles
[i
])
4358 if (binaryFun
!pred(r
.front
, r2
.front
))
4363 // we skipped over a new match
4364 hasNeedleMatch
= true;
4365 inactiveNeedlesLen
++;
4366 // skip over haystack
4372 inactiveNeedles
[i
] = true;
4373 inactiveNeedlesLen
++;
4379 if (inactiveNeedlesLen
== needles
.length
)
4386 return hasNeedleMatch || hasEmptyRanges
;
4391 bool skipOver(R
)(ref R r1
)
4392 if (isForwardRange
!R
&&
4393 ifTestable
!(typeof(r1
.front
), unaryFun
!pred
))
4395 if (r1
.empty ||
!unaryFun
!pred(r1
.front
))
4400 while (!r1
.empty
&& unaryFun
!pred(r1
.front
));
4405 bool skipOver(R
, Es
...)(ref R r
, Es es
)
4406 if (isInputRange
!R
&& is(typeof(binaryFun
!pred(r
.front
, es
[0]))))
4411 static foreach (e
; es
)
4413 if (binaryFun
!pred(r
.front
, e
))
4426 import std
.algorithm
.comparison
: equal
;
4428 auto s1
= "Hello world";
4429 assert(!skipOver(s1
, "Ha"));
4430 assert(s1
== "Hello world");
4431 assert(skipOver(s1
, "Hell") && s1
== "o world", s1
);
4433 string
[] r1
= ["abc", "def", "hij"];
4434 dstring
[] r2
= ["abc"d
];
4435 assert(!skipOver
!((a
, b
) => a
.equal(b
))(r1
, ["def"d
]), r1
[0]);
4436 assert(r1
== ["abc", "def", "hij"]);
4437 assert(skipOver
!((a
, b
) => a
.equal(b
))(r1
, r2
));
4438 assert(r1
== ["def", "hij"]);
4444 import std
.ascii
: isWhite
;
4445 import std
.range
.primitives
: empty
;
4447 auto s2
= "\t\tvalue";
4450 assert(s2
.skipOver
!isWhite
&& s2
== "value");
4451 assert(!s3
.skipOver
!isWhite
);
4452 assert(s4
.skipOver
!isWhite
&& s3
.empty
);
4455 /// Variadic skipOver
4458 auto s
= "Hello world";
4459 assert(!skipOver(s
, "hello", "HellO"));
4460 assert(s
== "Hello world");
4462 // the range is skipped over the longest matching needle is skipped
4463 assert(skipOver(s
, "foo", "hell", "Hello "));
4464 assert(s
== "world");
4470 import std
.algorithm
.comparison
: equal
;
4472 auto s1
= "Hello world";
4473 assert(!skipOver(s1
, 'a'));
4474 assert(s1
== "Hello world");
4475 assert(skipOver(s1
, 'H') && s1
== "ello world");
4477 string
[] r
= ["abc", "def", "hij"];
4479 assert(!skipOver
!((a
, b
) => a
.equal(b
))(r
, "def"d
));
4480 assert(r
== ["abc", "def", "hij"]);
4481 assert(skipOver
!((a
, b
) => a
.equal(b
))(r
, e
));
4482 assert(r
== ["def", "hij"]);
4485 assert(!s2
.skipOver('a'));
4488 /// Partial instantiation
4491 import std
.ascii
: isWhite
;
4492 import std
.range
.primitives
: empty
;
4494 alias whitespaceSkiper
= skipOver
!isWhite
;
4496 auto s2
= "\t\tvalue";
4499 assert(whitespaceSkiper(s2
) && s2
== "value");
4500 assert(!whitespaceSkiper(s2
));
4501 assert(whitespaceSkiper(s4
) && s3
.empty
);
4504 // variadic skipOver
4507 auto s
= "DLang.rocks";
4508 assert(!s
.skipOver("dlang", "DLF", "DLang "));
4509 assert(s
== "DLang.rocks");
4511 assert(s
.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLanpp"));
4512 assert(s
== "ang.rocks");
4515 assert(s
.skipOver("DLang", "DLANG", "DLF", "D", "DL", "DLang "));
4516 assert(s
== ".rocks");
4519 assert(s
.skipOver("dlang", "DLANG", "DLF", "D", "DL", "DLang."));
4520 assert(s
== "rocks");
4523 // variadic with custom pred
4526 import std
.ascii
: toLower
;
4528 auto s
= "DLang.rocks";
4529 assert(!s
.skipOver("dlang", "DLF", "DLang "));
4530 assert(s
== "DLang.rocks");
4532 assert(s
.skipOver
!((a
, b
) => a
.toLower
== b
.toLower
)("dlang", "DLF", "DLang "));
4533 assert(s
== ".rocks");
4536 // variadic skipOver with mixed needles
4539 auto s
= "DLang.rocks";
4540 assert(!s
.skipOver("dlang"d
, "DLF", "DLang "w
));
4541 assert(s
== "DLang.rocks");
4543 assert(s
.skipOver("dlang", "DLANG"d
, "DLF"w
, "D"d
, "DL", "DLanp"));
4544 assert(s
== "ang.rocks");
4547 assert(s
.skipOver("DLang", "DLANG"w
, "DLF"d
, "D"d
, "DL", "DLang "));
4548 assert(s
== ".rocks");
4551 assert(s
.skipOver("dlang", "DLANG"w
, "DLF", "D"d
, "DL"w
, "DLang."d
));
4552 assert(s
== "rocks");
4554 import std
.algorithm
.iteration
: filter
;
4556 assert(s
.skipOver("dlang", "DLang".filter
!(a
=> true)));
4557 assert(s
== ".rocks");
4560 // variadic skipOver with auto-decoding
4563 auto s
= "☢☣☠.☺";
4564 assert(s
.skipOver("a", "☢", "☢☣☠"));
4565 assert(s
== ".☺");
4568 // skipOver with @nogc
4569 @safe @nogc pure nothrow unittest
4571 static immutable s
= [0, 1, 2];
4572 immutable(int)[] s2
= s
[];
4574 static immutable skip1
= [0, 2];
4575 static immutable skip2
= [0, 1];
4576 assert(s2
.skipOver(skip1
, skip2
));
4577 assert(s2
== s
[2 .. $]);
4580 // variadic skipOver with single elements
4583 auto s
= "DLang.rocks";
4584 assert(!s
.skipOver('a', 'd', 'e'));
4585 assert(s
== "DLang.rocks");
4587 assert(s
.skipOver('a', 'D', 'd', 'D'));
4588 assert(s
== "Lang.rocks");
4591 assert(s
.skipOver(wchar('a'), dchar('D'), 'd'));
4592 assert(s
== "Lang.rocks");
4594 dstring dstr
= "+Foo";
4595 assert(!dstr
.skipOver('.', '-'));
4596 assert(dstr
== "+Foo");
4598 assert(dstr
.skipOver('+', '-'));
4599 assert(dstr
== "Foo");
4602 // skipOver with empty ranges must return true (compatibility)
4605 auto s
= "DLang.rocks";
4606 assert(s
.skipOver(""));
4607 assert(s
.skipOver("", ""));
4608 assert(s
.skipOver("", "foo"));
4610 auto s2
= "DLang.rocks"d
;
4611 assert(s2
.skipOver(""));
4612 assert(s2
.skipOver("", ""));
4613 assert(s2
.skipOver("", "foo"));
4619 import std
.utf
: byCodeUnit
;
4620 import std
.algorithm
.comparison
: equal
;
4622 bool stripStartsWith(Text
)(ref Text text
, string needle
)
4624 return text
.skipOver(needle
.byCodeUnit());
4626 auto text
= "<xml></xml>"d
.byCodeUnit
;
4627 assert(stripStartsWith(text
, "<xml>"));
4628 assert(text
.equal("</xml>"));
4632 Checks whether the given
4633 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) starts with (one
4634 of) the given needle(s) or, if no needles are given,
4635 if its front element fulfils predicate `pred`.
4637 For more information about `pred` see $(LREF find).
4641 pred = Predicate to use in comparing the elements of the haystack and the
4642 needle(s). Mandatory if no needles are given.
4644 doesThisStart = The input range to check.
4646 withOneOfThese = The needles against which the range is to be checked,
4647 which may be individual elements or input ranges of elements.
4649 withThis = The single needle to check, which may be either a single element
4650 or an input range of elements.
4654 0 if the needle(s) do not occur at the beginning of the given range;
4655 otherwise the position of the matching needle, that is, 1 if the range starts
4656 with `withOneOfThese[0]`, 2 if it starts with `withOneOfThese[1]`, and so
4659 In the case where `doesThisStart` starts with multiple of the ranges or
4660 elements in `withOneOfThese`, then the shortest one matches (if there are
4661 two which match which are of the same length (e.g. `"a"` and `'a'`), then
4662 the left-most of them in the argument
4665 In the case when no needle parameters are given, return `true` iff front of
4666 `doesThisStart` fulfils predicate `pred`.
4668 uint startsWith(alias pred
= (a
, b
) => a
== b
, Range
, Needles
...)(Range doesThisStart
, Needles withOneOfThese
)
4669 if (isInputRange
!Range
&& Needles
.length
> 1 &&
4670 allSatisfy
!(canTestStartsWith
!(pred
, Range
), Needles
))
4672 template checkType(T
)
4674 enum checkType
= is(immutable ElementEncodingType
!Range
== immutable T
);
4677 // auto-decoding special case
4678 static if (__traits(isSame
, binaryFun
!pred
, (a
, b
) => a
== b
) &&
4679 isNarrowString
!Range
&& allSatisfy
!(checkType
, Needles
))
4681 import std
.utf
: byCodeUnit
;
4682 auto haystack
= doesThisStart
.byCodeUnit
;
4686 alias haystack
= doesThisStart
;
4688 alias needles
= withOneOfThese
;
4690 // Make one pass looking for empty ranges in needles
4691 foreach (i
, Unused
; Needles
)
4693 // Empty range matches everything
4694 static if (!is(typeof(binaryFun
!pred(haystack
.front
, needles
[i
])) : bool))
4696 if (needles
[i
].empty
) return i
+ 1;
4700 for (; !haystack
.empty
; haystack
.popFront())
4702 foreach (i
, Unused
; Needles
)
4704 static if (is(typeof(binaryFun
!pred(haystack
.front
, needles
[i
])) : bool))
4707 if (binaryFun
!pred(haystack
.front
, needles
[i
]))
4709 // found, but instead of returning, we just stop searching.
4710 // This is to account for one-element
4711 // range matches (consider startsWith("ab", "a",
4712 // 'a') should return 1, not 2).
4718 if (binaryFun
!pred(haystack
.front
, needles
[i
].front
))
4724 // This code executed on failure to match
4725 // Out with this guy, check for the others
4726 uint result
= startsWith
!pred(haystack
, needles
[0 .. i
], needles
[i
+ 1 .. $]);
4727 if (result
> i
) ++result
;
4731 // If execution reaches this point, then the front matches for all
4732 // needle ranges, or a needle element has been matched.
4733 // What we need to do now is iterate, lopping off the front of
4734 // the range and checking if the result is empty, or finding an
4735 // element needle and returning.
4736 // If neither happens, we drop to the end and loop.
4737 foreach (i
, Unused
; Needles
)
4739 static if (is(typeof(binaryFun
!pred(haystack
.front
, needles
[i
])) : bool))
4741 // Test has passed in the previous loop
4746 needles
[i
].popFront();
4747 if (needles
[i
].empty
) return i
+ 1;
4755 bool startsWith(alias pred
= "a == b", R1
, R2
)(R1 doesThisStart
, R2 withThis
)
4756 if (isInputRange
!R1
&&
4758 is(typeof(binaryFun
!pred(doesThisStart
.front
, withThis
.front
)) : bool))
4760 alias haystack
= doesThisStart
;
4761 alias needle
= withThis
;
4763 static if (is(typeof(pred
) : string
))
4764 enum isDefaultPred
= pred
== "a == b";
4766 enum isDefaultPred
= false;
4768 // Note: Although narrow strings don't have a "true" length, for a narrow string to start with another
4769 // narrow string, it must have *at least* as many code units.
4770 static if ((hasLength
!R1
&& hasLength
!R2
) ||
4771 ((hasLength
!R1 || isNarrowString
!R1
) && (hasLength
!R2 || isNarrowString
!R2
)
4772 && (ElementEncodingType
!R1
.sizeof
<= ElementEncodingType
!R2
.sizeof
)))
4774 if (haystack
.length
< needle
.length
)
4778 static if (isDefaultPred
&& isArray
!R1
&& isArray
!R2
&&
4779 is(immutable ElementEncodingType
!R1
== immutable ElementEncodingType
!R2
))
4781 //Array slice comparison mode
4782 return haystack
[0 .. needle
.length
] == needle
;
4784 else static if (isRandomAccessRange
!R1
&& isRandomAccessRange
!R2
&& hasLength
!R2
)
4786 //RA dual indexing mode
4787 foreach (j
; 0 .. needle
.length
)
4789 if (!binaryFun
!pred(haystack
[j
], needle
[j
]))
4798 //Standard input range mode
4799 if (needle
.empty
) return true;
4800 static if (hasLength
!R1
&& hasLength
!R2
)
4802 //We have previously checked that haystack.length > needle.length,
4803 //So no need to check haystack.empty during iteration
4804 for ( ; ; haystack
.popFront() )
4806 if (!binaryFun
!pred(haystack
.front
, needle
.front
)) break;
4808 if (needle
.empty
) return true;
4813 for ( ; !haystack
.empty
; haystack
.popFront() )
4815 if (!binaryFun
!pred(haystack
.front
, needle
.front
)) break;
4817 if (needle
.empty
) return true;
4825 bool startsWith(alias pred
= "a == b", R
, E
)(R doesThisStart
, E withThis
)
4826 if (isInputRange
!R
&&
4827 is(typeof(binaryFun
!pred(doesThisStart
.front
, withThis
)) : bool))
4829 if (doesThisStart
.empty
)
4832 static if (is(typeof(pred
) : string
))
4833 enum isDefaultPred
= pred
== "a == b";
4835 enum isDefaultPred
= false;
4837 alias predFunc
= binaryFun
!pred
;
4839 // auto-decoding special case
4840 static if (isNarrowString
!R
)
4842 // statically determine decoding is unnecessary to evaluate pred
4843 static if (isDefaultPred
&& isSomeChar
!E
&& E
.sizeof
<= ElementEncodingType
!R
.sizeof
)
4844 return doesThisStart
[0] == withThis
;
4845 // specialize for ASCII as to not change previous behavior
4848 if (withThis
<= 0x7F)
4849 return predFunc(doesThisStart
[0], withThis
);
4851 return predFunc(doesThisStart
.front
, withThis
);
4856 return predFunc(doesThisStart
.front
, withThis
);
4861 bool startsWith(alias pred
, R
)(R doesThisStart
)
4862 if (isInputRange
!R
&&
4863 ifTestable
!(typeof(doesThisStart
.front
), unaryFun
!pred
))
4865 return !doesThisStart
.empty
&& unaryFun
!pred(doesThisStart
.front
);
4871 import std
.ascii
: isAlpha
;
4873 assert("abc".startsWith
!(a
=> a
.isAlpha
));
4874 assert("abc".startsWith
!isAlpha
);
4875 assert(!"1ab".startsWith
!(a
=> a
.isAlpha
));
4876 assert(!"".startsWith
!(a
=> a
.isAlpha
));
4878 import std
.algorithm
.comparison
: among
;
4879 assert("abc".startsWith
!(a
=> a
.among('a', 'b') != 0));
4880 assert(!"abc".startsWith
!(a
=> a
.among('b', 'c') != 0));
4882 assert(startsWith("abc", ""));
4883 assert(startsWith("abc", "a"));
4884 assert(!startsWith("abc", "b"));
4885 assert(startsWith("abc", 'a', "b") == 1);
4886 assert(startsWith("abc", "b", "a") == 2);
4887 assert(startsWith("abc", "a", "a") == 1);
4888 assert(startsWith("abc", "ab", "a") == 2);
4889 assert(startsWith("abc", "x", "a", "b") == 2);
4890 assert(startsWith("abc", "x", "aa", "ab") == 3);
4891 assert(startsWith("abc", "x", "aaa", "sab") == 0);
4892 assert(startsWith("abc", "x", "aaa", "a", "sab") == 3);
4894 import std
.typecons
: Tuple
;
4895 alias C
= Tuple
!(int, "x", int, "y");
4896 assert(startsWith
!"a.x == b"([ C(1,1), C(1,2), C(2,2) ], [1, 1]));
4897 assert(startsWith
!"a.x == b"([ C(1,1), C(2,1), C(2,2) ], [1, 1], [1, 2], [1, 3]) == 2);
4902 import std
.algorithm
.iteration
: filter
;
4903 import std
.conv
: to
;
4904 import std
.meta
: AliasSeq
;
4907 static foreach (S
; AliasSeq
!(char[], wchar[], dchar[], string
, wstring
, dstring
))
4908 (){ // workaround slow optimizations for large functions
4909 // https://issues.dlang.org/show_bug.cgi?id=2396
4910 assert(!startsWith(to
!S("abc"), 'c'));
4911 assert(startsWith(to
!S("abc"), 'a', 'c') == 1);
4912 assert(!startsWith(to
!S("abc"), 'x', 'n', 'b'));
4913 assert(startsWith(to
!S("abc"), 'x', 'n', 'a') == 3);
4914 assert(startsWith(to
!S("\uFF28abc"), 'a', '\uFF28', 'c') == 2);
4916 static foreach (T
; AliasSeq
!(char[], wchar[], dchar[], string
, wstring
, dstring
))
4919 assert(startsWith(to
!S("abc"), to
!T("")));
4920 assert(startsWith(to
!S("ab"), to
!T("a")));
4921 assert(startsWith(to
!S("abc"), to
!T("a")));
4922 assert(!startsWith(to
!S("abc"), to
!T("b")));
4923 assert(!startsWith(to
!S("abc"), to
!T("b"), "bc", "abcd", "xyz"));
4924 assert(startsWith(to
!S("abc"), to
!T("ab"), 'a') == 2);
4925 assert(startsWith(to
!S("abc"), to
!T("a"), "b") == 1);
4926 assert(startsWith(to
!S("abc"), to
!T("b"), "a") == 2);
4927 assert(startsWith(to
!S("abc"), to
!T("a"), 'a') == 1);
4928 assert(startsWith(to
!S("abc"), 'a', to
!T("a")) == 1);
4929 assert(startsWith(to
!S("abc"), to
!T("x"), "a", "b") == 2);
4930 assert(startsWith(to
!S("abc"), to
!T("x"), "aa", "ab") == 3);
4931 assert(startsWith(to
!S("abc"), to
!T("x"), "aaa", "sab") == 0);
4932 assert(startsWith(to
!S("abc"), 'a'));
4933 assert(!startsWith(to
!S("abc"), to
!T("sab")));
4934 assert(startsWith(to
!S("abc"), 'x', to
!T("aaa"), 'a', "sab") == 3);
4937 assert(startsWith(to
!S("\uFF28el\uFF4co"), to
!T("\uFF28el")));
4938 assert(startsWith(to
!S("\uFF28el\uFF4co"), to
!T("Hel"), to
!T("\uFF28el")) == 2);
4939 assert(startsWith(to
!S("日本語"), to
!T("日本")));
4940 assert(startsWith(to
!S("日本語"), to
!T("日本語")));
4941 assert(!startsWith(to
!S("日本"), to
!T("日本語")));
4944 assert(startsWith(to
!S(""), T
.init
));
4945 assert(!startsWith(to
!S(""), 'a'));
4946 assert(startsWith(to
!S("a"), T
.init
));
4947 assert(startsWith(to
!S("a"), T
.init
, "") == 1);
4948 assert(startsWith(to
!S("a"), T
.init
, 'a') == 1);
4949 assert(startsWith(to
!S("a"), 'a', T
.init
) == 2);
4954 assert(!startsWith("abc".takeExactly(3), "abcd".takeExactly(4)));
4955 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(3)));
4956 assert(startsWith("abc".takeExactly(3), "abcd".takeExactly(1)));
4958 static foreach (T
; AliasSeq
!(int, short))
4960 immutable arr
= cast(T
[])[0, 1, 2, 3, 4, 5];
4963 assert(startsWith(arr
, cast(int[]) null));
4964 assert(!startsWith(arr
, 5));
4965 assert(!startsWith(arr
, 1));
4966 assert(startsWith(arr
, 0));
4967 assert(startsWith(arr
, 5, 0, 1) == 2);
4968 assert(startsWith(arr
, [0]));
4969 assert(startsWith(arr
, [0, 1]));
4970 assert(startsWith(arr
, [0, 1], 7) == 1);
4971 assert(!startsWith(arr
, [0, 1, 7]));
4972 assert(startsWith(arr
, [0, 1, 7], [0, 1, 2]) == 2);
4974 //Normal input range
4975 assert(!startsWith(filter
!"true"(arr
), 1));
4976 assert(startsWith(filter
!"true"(arr
), 0));
4977 assert(startsWith(filter
!"true"(arr
), [0]));
4978 assert(startsWith(filter
!"true"(arr
), [0, 1]));
4979 assert(startsWith(filter
!"true"(arr
), [0, 1], 7) == 1);
4980 assert(!startsWith(filter
!"true"(arr
), [0, 1, 7]));
4981 assert(startsWith(filter
!"true"(arr
), [0, 1, 7], [0, 1, 2]) == 2);
4982 assert(startsWith(arr
, filter
!"true"([0, 1])));
4983 assert(startsWith(arr
, filter
!"true"([0, 1]), 7) == 1);
4984 assert(!startsWith(arr
, filter
!"true"([0, 1, 7])));
4985 assert(startsWith(arr
, [0, 1, 7], filter
!"true"([0, 1, 2])) == 2);
4988 assert(startsWith
!("a%10 == b%10")(arr
, [10, 11]));
4989 assert(!startsWith
!("a%10 == b%10")(arr
, [10, 12]));
4993 private template canTestStartsWith(alias pred
, Haystack
)
4995 enum bool canTestStartsWith(Needle
) = is(typeof(
4996 (ref Haystack h
, ref Needle n
) => startsWith
!pred(h
, n
)));
4999 /* (Not yet documented.)
5000 Consume all elements from `r` that are equal to one of the elements
5003 private void skipAll(alias pred
= "a == b", R
, Es
...)(ref R r
, Es es
)
5004 //if (is(typeof(binaryFun!pred(r1.front, es[0]))))
5007 for (; !r
.empty
; r
.popFront())
5011 if (binaryFun
!pred(r
.front
, es
[i
]))
5022 auto s1
= "Hello world";
5023 skipAll(s1
, 'H', 'e');
5024 assert(s1
== "llo world");
5028 Interval option specifier for `until` (below) and others.
5030 If set to `OpenRight.yes`, then the interval is open to the right
5031 (last element is not included).
5033 Otherwise if set to `OpenRight.no`, then the interval is closed to the right
5034 including the entire sentinel.
5036 alias OpenRight
= Flag
!"openRight";
5039 Lazily iterates `range` _until the element `e` for which
5040 `pred(e, sentinel)` is true.
5042 This is similar to `takeWhile` in other languages.
5045 pred = Predicate to determine when to stop.
5046 range = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
5048 sentinel = The element to stop at.
5049 openRight = Determines whether the element for which the given predicate is
5050 true should be included in the resulting range (`No.openRight`), or
5051 not (`Yes.openRight`).
5054 An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) that
5055 iterates over the original range's elements, but ends when the specified
5056 predicate becomes true. If the original range is a
5057 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) or
5058 higher, this range will be a forward range.
5060 Until
!(pred
, Range
, Sentinel
)
5061 until(alias pred
= "a == b", Range
, Sentinel
)
5062 (Range range
, Sentinel sentinel
, OpenRight openRight
= Yes
.openRight
)
5063 if (!is(Sentinel
== OpenRight
))
5065 return typeof(return)(range
, sentinel
, openRight
);
5069 Until
!(pred
, Range
, void)
5070 until(alias pred
, Range
)
5071 (Range range
, OpenRight openRight
= Yes
.openRight
)
5073 return typeof(return)(range
, openRight
);
5077 struct Until(alias pred
, Range
, Sentinel
)
5078 if (isInputRange
!Range
)
5080 private Range _input
;
5081 static if (!is(Sentinel
== void))
5082 private Sentinel _sentinel
;
5083 private OpenRight _openRight
;
5084 private bool _matchStarted
;
5087 static if (!is(Sentinel
== void))
5090 this(Range input
, Sentinel sentinel
,
5091 OpenRight openRight
= Yes
.openRight
)
5094 _sentinel
= sentinel
;
5095 _openRight
= openRight
;
5096 static if (isInputRange
!Sentinel
)
5098 _matchStarted
= predSatisfied();
5099 _done
= _input
.empty || _sentinel
.empty || openRight
&& _matchStarted
;
5100 if (_matchStarted
&& !_done
&& !openRight
)
5107 _done
= _input
.empty || openRight
&& predSatisfied();
5110 private this(Range input
, Sentinel sentinel
, OpenRight openRight
,
5114 _sentinel
= sentinel
;
5115 _openRight
= openRight
;
5122 this(Range input
, OpenRight openRight
= Yes
.openRight
)
5125 _openRight
= openRight
;
5126 _done
= _input
.empty || openRight
&& predSatisfied();
5128 private this(Range input
, OpenRight openRight
, bool done
)
5131 _openRight
= openRight
;
5137 @property bool empty()
5143 @property auto ref front()
5145 assert(!empty
, "Can not get the front of an empty Until");
5146 return _input
.front
;
5149 private bool predSatisfied()
5151 static if (is(Sentinel
== void))
5152 return cast(bool) unaryFun
!pred(_input
.front
);
5154 return cast(bool) startsWith
!pred(_input
, _sentinel
);
5160 assert(!empty
, "Can not popFront of an empty Until");
5163 static if (isInputRange
!Sentinel
)
5166 _done
= _input
.empty || _sentinel
.empty
;
5175 _matchStarted
= predSatisfied();
5185 _done
= predSatisfied();
5187 _done
= _done || _input
.empty
;
5193 _done
= _input
.empty ||
predSatisfied();
5197 static if (isForwardRange
!Range
)
5200 @property Until
save()
5202 static if (is(Sentinel
== void))
5203 return Until(_input
.save
, _openRight
, _done
);
5205 return Until(_input
.save
, _sentinel
, _openRight
, _done
);
5213 import std
.algorithm
.comparison
: equal
;
5214 import std
.typecons
: No
;
5215 int[] a
= [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
5216 assert(equal(a
.until(7), [1, 2, 4]));
5217 assert(equal(a
.until(7, No
.openRight
), [1, 2, 4, 7]));
5222 import std
.algorithm
.comparison
: equal
;
5223 int[] a
= [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
5225 static assert(isForwardRange
!(typeof(a
.until(7))));
5226 static assert(isForwardRange
!(typeof(until
!"a == 2"(a
, No
.openRight
))));
5228 assert(equal(a
.until(7), [1, 2, 4]));
5229 assert(equal(a
.until([7, 2]), [1, 2, 4, 7]));
5230 assert(equal(a
.until(7, No
.openRight
), [1, 2, 4, 7]));
5231 assert(equal(until
!"a == 2"(a
, No
.openRight
), [1, 2]));
5234 // https://issues.dlang.org/show_bug.cgi?id=13171
5237 import std
.algorithm
.comparison
: equal
;
5239 auto a
= [1, 2, 3, 4];
5240 assert(equal(refRange(&a
).until(3, No
.openRight
), [1, 2, 3]));
5244 // https://issues.dlang.org/show_bug.cgi?id=10460
5247 import std
.algorithm
.comparison
: equal
;
5248 auto a
= [1, 2, 3, 4];
5249 foreach (ref e
; a
.until(3))
5251 assert(equal(a
, [0, 0, 3, 4]));
5254 // https://issues.dlang.org/show_bug.cgi?id=13124
5257 import std
.algorithm
.comparison
: among
, equal
;
5258 auto s
= "hello how\nare you";
5259 assert(equal(s
.until
!(c
=> c
.among
!('\n', '\r')), "hello how"));
5262 // https://issues.dlang.org/show_bug.cgi?id=18657
5265 import std
.algorithm
.comparison
: equal
;
5266 import std
.range
: refRange
;
5268 string s
= "foobar";
5269 auto r
= refRange(&s
).until("bar");
5270 assert(equal(r
.save
, "foo"));
5271 assert(equal(r
.save
, "foo"));
5274 string s
= "foobar";
5275 auto r
= refRange(&s
).until
!(e
=> e
== 'b');
5276 assert(equal(r
.save
, "foo"));
5277 assert(equal(r
.save
, "foo"));
5280 // https://issues.dlang.org/show_bug.cgi?id=14543
5283 import std
.algorithm
.comparison
: equal
;
5284 import std
.uni
: toUpper
;
5285 assert("one two three".until("two").equal("one "));
5286 assert("one two three".until("two", OpenRight
.no
).equal("one two"));
5288 assert("one two three".until("two", No
.openRight
).equal("one two"));
5289 assert("one two three".until("two", Yes
.openRight
).equal("one "));
5291 assert("one two three".until('t', Yes
.openRight
).equal("one "));
5292 assert("one two three".until("", Yes
.openRight
).equal(""));
5293 assert("one two three".until("", No
.openRight
).equal(""));
5295 assert("one two three".until("three", No
.openRight
).equal("one two three"));
5296 assert("one two three".until("three", Yes
.openRight
).equal("one two "));
5298 assert("one two three".until("one", No
.openRight
).equal("one"));
5299 assert("one two three".until("one", Yes
.openRight
).equal(""));
5301 assert("one two three".until("o", No
.openRight
).equal("o"));
5302 assert("one two three".until("o", Yes
.openRight
).equal(""));
5304 assert("one two three".until("", No
.openRight
).equal(""));
5305 assert("one two three".until("", Yes
.openRight
).equal(""));
5307 assert("one two three".until
!((a
,b
)=>a
.toUpper
== b
)("TWO", No
.openRight
).equal("one two"));