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