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