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