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