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