root/trunk/phobos/std/algorithm.d

Revision 2373, 218.3 kB (checked in by andrei, 4 years ago)

findSplit, findSplitBefore, findSplitAfter

  • Property svn:eol-style set to native
Line 
1 // Written in the D programming language.
2
3 /**
4 Implements algorithms oriented mainly towards processing of
5 sequences. Some functions are semantic equivalents or supersets of
6 those found in the $(D $(LESS)_algorithm$(GREATER)) header in $(WEB
7 sgi.com/tech/stl/, Alexander Stepanov's Standard Template Library) for
8 C++.
9
10 Note:
11
12 Many functions in this module are parameterized with a function or a
13 $(GLOSSARY predicate). The predicate may be passed either as a
14 function name, a delegate name, a $(GLOSSARY functor) name, or a
15 compile-time string. The string may consist of $(B any) legal D
16 expression that uses the symbol $(D a) (for unary functions) or the
17 symbols $(D a) and $(D b) (for binary functions). These names will NOT
18 interfere with other homonym symbols in user code because they are
19 evaluated in a different context. The default for all binary
20 comparison predicates is $(D "a == b") for unordered operations and
21 $(D "a < b") for ordered operations.
22
23 Example:
24
25 ----
26 int[] a = ...;
27 static bool greater(int a, int b)
28 {
29     return a > b;
30 }
31 sort!(greater)(a);  // predicate as alias
32 sort!("a > b")(a);  // predicate as string
33                     // (no ambiguity with array name)
34 sort(a);            // no predicate, "a < b" is implicit
35 ----
36
37 Macros:
38 WIKI = Phobos/StdAlgorithm
39
40 Copyright: Andrei Alexandrescu 2008-.
41
42 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
43
44 Authors:   $(WEB erdani.com, Andrei Alexandrescu)
45  */
46 module std.algorithm;
47 //debug = std_algorithm;
48
49 import std.c.string;
50 import std.array, std.container, std.conv, std.exception,
51     std.functional, std.math, std.metastrings, std.range, std.string,
52     std.traits, std.typecons, std.typetuple, std.stdio;
53
54 version(unittest)
55 {
56     import std.random, std.stdio, std.string;
57     mixin(dummyRanges);
58 }
59
60 /**
61 Implements the homonym function (also known as $(D transform)) present
62 in many languages of functional flavor. The call $(D map!(fun)(range))
63 returns a range of which elements are obtained by applying $(D fun(x))
64 left to right for all $(D x) in $(D range). The original ranges are
65 not changed. Evaluation is done lazily. The range returned by $(D map)
66 caches the last value such that evaluating $(D front) multiple times
67 does not result in multiple calls to $(D fun).
68
69 Example:
70 ----
71 int[] arr1 = [ 1, 2, 3, 4 ];
72 int[] arr2 = [ 5, 6 ];
73 auto squares = map!("a * a")(chain(arr1, arr2));
74 assert(equal(squares, [ 1, 4, 9, 16, 25, 36 ]));
75 ----
76
77 Multiple functions can be passed to $(D map). In that case, the
78 element type of $(D map) is a tuple containing one element for each
79 function.
80
81 Example:
82
83 ----
84 auto arr1 = [ 1, 2, 3, 4 ];
85 foreach (e; map!("a + a", "a * a")(arr1))
86 {
87     writeln(e[0], " ", e[1]);
88 }
89 ----
90
91 You may alias $(D map) with some function(s) to a symbol and use it
92 separately:
93
94 ----
95 alias map!(to!string) stringize;
96 assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));
97 ----
98  */
99 template map(fun...)
100 {
101     auto map(Range)(Range r)
102     {
103         static if (fun.length > 1)
104         {
105             return Map!(adjoin!(staticMap!(unaryFun, fun)), Range)(r);
106         }
107         else
108         {
109             return Map!(unaryFun!fun, Range)(r);
110         }
111     }
112 }
113
114 struct Map(alias fun, Range) if (isInputRange!(Unqual!Range))
115 {
116     alias Unqual!Range R;
117     alias fun _fun;
118     // Uncomment this to reveal a @@@BUG@@@ in the compiler
119     //alias typeof(fun(.ElementType!R.init)) ElementType;
120     alias typeof({ return fun(.ElementType!R.init); }()) ElementType;
121     R _input;
122
123     static if (isBidirectionalRange!(R))
124     {
125         @property ElementType back()
126         {
127             return _fun(_input.back);
128         }
129
130         void popBack()
131         {
132             _input.popBack();
133         }
134     }
135
136     this(R input)
137     {
138         _input = input;
139     }
140
141     static if (isInfinite!R)
142     {
143         // Propagate infinite-ness.
144         enum bool empty = false;
145     }
146     else
147     {
148         @property bool empty()
149         {
150             return _input.empty;
151         }
152     }
153
154     void popFront()
155     {
156         _input.popFront();
157     }
158
159     @property ElementType front()
160     {
161         return _fun(_input.front);
162     }
163
164     static if (isRandomAccessRange!R)
165     {
166         ElementType opIndex(size_t index)
167         {
168             return _fun(_input[index]);
169         }
170     }
171
172     // hasLength is busted, Bug 2873
173     static if (is(typeof(_input.length) : size_t)
174         || is(typeof(_input.length()) : size_t))
175     {
176         @property size_t length()
177         {
178             return _input.length;
179         }
180     }
181
182     static if (hasSlicing!(R))
183     {
184         typeof(this) opSlice(size_t lowerBound, size_t upperBound)
185         {
186             return typeof(this)(_input[lowerBound..upperBound]);
187         }
188     }
189
190     static if (isForwardRange!R)
191     @property Map save()
192     {
193         auto result = this;
194         result._input = result._input.save;
195         return result;
196     }
197 }
198
199 unittest
200 {
201     debug(std_algorithm) scope(success)
202         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
203     alias map!(to!string) stringize;
204     assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));
205     uint counter;
206     alias map!((a) { return counter++; }) count;
207     assert(equal(count([ 10, 2, 30, 4 ]), [ 0, 1, 2, 3 ]));
208     counter = 0;
209     adjoin!((a) { return counter++; }, (a) { return counter++; })(1);
210     alias map!((a) { return counter++; }, (a) { return counter++; }) countAndSquare;
211     //assert(equal(countAndSquare([ 10, 2 ]), [ tuple(0u, 100), tuple(1u, 4) ]));
212 }
213
214 unittest
215 {
216     debug(std_algorithm) scope(success)
217         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
218     int[] arr1 = [ 1, 2, 3, 4 ];
219     const int[] arr1Const = arr1;
220     int[] arr2 = [ 5, 6 ];
221     auto squares = map!("a * a")(arr1Const);
222     assert(equal(squares, [ 1, 4, 9, 16 ][]));
223     assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][]));
224
225     // Test the caching stuff.
226     assert(squares.back == 16);
227     auto squares2 = squares.save;
228     assert(squares2.back == 16);
229
230     assert(squares2.front == 1);
231     squares2.popFront;
232     assert(squares2.front == 4);
233     squares2.popBack;
234     assert(squares2.front == 4);
235     assert(squares2.back == 9);
236
237     assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][]));
238
239     uint i;
240     foreach (e; map!("a", "a * a")(arr1))
241     {
242         assert(e[0] == ++i);
243         assert(e[1] == i * i);
244     }
245
246     // Test length.
247     assert(squares.length == 4);
248     assert(map!"a * a"(chain(arr1, arr2)).length == 6);
249
250     // Test indexing.
251     assert(squares[0] == 1);
252     assert(squares[1] == 4);
253     assert(squares[2] == 9);
254     assert(squares[3] == 16);
255
256     // Test slicing.
257     auto squareSlice = squares[1..squares.length - 1];
258     assert(equal(squareSlice, [4, 9][]));
259     assert(squareSlice.back == 9);
260     assert(squareSlice[1] == 9);
261
262     // Test on a forward range to make sure it compiles when all the fancy
263     // stuff is disabled.
264     auto fibsSquares = map!"a * a"(recurrence!("a[n-1] + a[n-2]")(1, 1));
265     assert(fibsSquares.front == 1);
266     fibsSquares.popFront;
267     fibsSquares.popFront;
268     assert(fibsSquares.front == 4);
269     fibsSquares.popFront;
270     assert(fibsSquares.front == 9);
271
272     auto repeatMap = map!"a"(repeat(1));
273     static assert(isInfinite!(typeof(repeatMap)));
274    
275     auto intRange = map!"a"([1,2,3]);
276     static assert(isRandomAccessRange!(typeof(intRange)));
277    
278     foreach(DummyType; AllDummyRanges)
279     {
280         DummyType d;
281         auto m = map!"a * a"(d);
282
283         static assert(propagatesRangeType!(typeof(m), DummyType));
284         assert(equal(m, [1,4,9,16,25,36,49,64,81,100]));
285     }
286 }
287
288 // reduce
289 /**
290 Implements the homonym function (also known as $(D accumulate), $(D
291 compress), $(D inject), or $(D foldl)) present in various programming
292 languages of functional flavor. The call $(D reduce!(fun)(seed,
293 range)) first assigns $(D seed) to an internal variable $(D result),
294 also called the accumulator. Then, for each element $(D x) in $(D
295 range), $(D result = fun(result, x)) gets evaluated. Finally, $(D
296 result) is returned. The one-argument version $(D reduce!(fun)(range))
297 works similarly, but it uses the first element of the range as the
298 seed (the range must be non-empty).
299
300 Many aggregate range operations turn out to be solved with $(D reduce)
301 quickly and easily. The example below illustrates $(D reduce)'s
302 remarkable power and flexibility.
303
304 Example:
305 ----
306 int[] arr = [ 1, 2, 3, 4, 5 ];
307 // Sum all elements
308 auto sum = reduce!("a + b")(0, arr);
309 assert(sum == 15);
310
311 // Compute the maximum of all elements
312 auto largest = reduce!(max)(arr);
313 assert(largest == 5);
314
315 // Compute the number of odd elements
316 auto odds = reduce!("a + (b & 1)")(0, arr);
317 assert(odds == 3);
318
319 // Compute the sum of squares
320 auto ssquares = reduce!("a + b * b")(0, arr);
321 assert(ssquares == 55);
322
323 // Chain multiple ranges into seed
324 int[] a = [ 3, 4 ];
325 int[] b = [ 100 ];
326 auto r = reduce!("a + b")(chain(a, b));
327 assert(r == 107);
328
329 // Mixing convertible types is fair game, too
330 double[] c = [ 2.5, 3.0 ];
331 auto r1 = reduce!("a + b")(chain(a, b, c));
332 assert(r1 == 112.5);
333 ----
334
335 $(DDOC_SECTION_H Multiple functions:) Sometimes it is very useful to
336 compute multiple aggregates in one pass. One advantage is that the
337 computation is faster because the looping overhead is shared. That's
338 why $(D reduce) accepts multiple functions. If two or more functions
339 are passed, $(D reduce) returns a $(XREF typecons, Tuple) object with
340 one member per passed-in function. The number of seeds must be
341 correspondingly increased.
342
343 Example:
344 ----
345 double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
346 // Compute minimum and maximum in one pass
347 auto r = reduce!(min, max)(a);
348 // The type of r is Tuple!(double, double)
349 assert(r[0] == 2);  // minimum
350 assert(r[1] == 11); // maximum
351
352 // Compute sum and sum of squares in one pass
353 r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
354 assert(r[0] == 35);  // sum
355 assert(r[1] == 233); // sum of squares
356 // Compute average and standard deviation from the above
357 auto avg = r[0] / a.length;
358 auto stdev = sqrt(r[1] / a.length - avg * avg);
359 ----
360  */
361
362 template reduce(fun...)
363 {
364     auto reduce(Args...)(Args args)
365     if (Args.length > 0 && Args.length <= 2 && isIterable!(Args[$ - 1]))
366     {
367         static if(isInputRange!(Args[$ - 1]))
368         {
369             static if (Args.length == 2)
370             {
371                 alias args[0] seed;
372                 alias args[1] r;
373                 Unqual!(Args[0]) result = seed;
374                 for (; !r.empty; r.popFront)
375                 {
376                     static if (fun.length == 1)
377                     {
378                         result = binaryFun!(fun[0])(result, r.front);
379                     }
380                     else
381                     {
382                         foreach (i, Unused; Args[0].Types)
383                         {
384                             result[i] = binaryFun!(fun[i])(result[i], r.front);
385                         }
386                     }
387                 }
388                 return result;
389             }
390             else
391             {
392                 enforce(!args[$ - 1].empty,
393                     "Cannot reduce an empty range w/o an explicit seed value.");
394                 alias args[0] r;
395                 static if (fun.length == 1)
396                 {
397                     return reduce(r.front, (r.popFront(), r));
398                 }
399                 else
400                 {
401                     static assert(fun.length > 1);
402                     typeof(adjoin!(staticMap!(binaryFun, fun))(r.front, r.front))
403                         result = void;
404                     foreach (i, T; result.Types)
405                     {
406                         auto p = (cast(void*) &result[i])[0 .. result[i].sizeof];
407                         emplace!T(p, r.front);
408                     }
409                     r.popFront();
410                     return reduce(result, r);
411                 }
412             }
413         }
414         else
415         {   // opApply case.  Coded as a separate case because efficiently
416             // handling all of the small details like avoiding unnecessary
417             // copying, iterating by dchar over strings, and dealing with the
418             // no explicit start value case would become an unreadable mess
419             // if these were merged.
420             alias args[$ - 1] r;
421             alias Args[$ - 1] R;
422             alias ForeachType!R E;
423
424             static if(args.length == 2)
425             {
426                 static if(fun.length == 1)
427                 {
428                     auto result = Tuple!(Unqual!(Args[0]))(args[0]);
429                 }
430                 else
431                 {
432                     Unqual!(Args[0]) result = args[0];
433                 }
434
435                 enum bool initialized = true;
436             }
437             else static if(fun.length == 1)
438             {
439                 Tuple!(typeof(binaryFun!fun(E.init, E.init))) result = void;
440                 bool initialized = false;
441             }
442             else
443             {
444                 typeof(adjoin!(staticMap!(binaryFun, fun))(E.init, E.init))
445                     result = void;
446                 bool initialized = false;
447             }
448
449             // For now, just iterate using ref to avoid unnecessary copying.
450             // When Bug 2443 is fixed, this may need to change.
451             foreach(ref elem; r)
452             {
453                 if(initialized)
454                 {
455                     foreach(i, T; result.Types)
456                     {
457                         result[i] = binaryFun!(fun[i])(result[i], elem);
458                     }
459                 }
460                 else
461                 {
462                     static if(is(typeof(&initialized)))
463                     {
464                         initialized = true;
465                     }
466
467                     foreach (i, T; result.Types)
468                     {
469                         auto p = (cast(void*) &result[i])
470                             [0 .. result[i].sizeof];
471                         emplace!T(p, elem);
472                     }
473                 }
474             }
475
476             enforce(initialized,
477                 "Cannot reduce an empty iterable w/o an explicit seed value.");
478
479             static if(fun.length == 1)
480             {
481                 return result[0];
482             }
483             else
484             {
485                 return result;
486             }
487         }
488     }
489 }
490
491 unittest
492 {
493     debug(std_algorithm) scope(success)
494         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
495     double[] a = [ 3, 4 ];
496     auto r = reduce!("a + b")(0.0, a);
497     assert(r == 7);
498     r = reduce!("a + b")(a);
499     assert(r == 7);
500     r = reduce!(min)(a);
501     assert(r == 3);
502     double[] b = [ 100 ];
503     auto r1 = reduce!("a + b")(chain(a, b));
504     assert(r1 == 107);
505
506     // two funs
507     auto r2 = reduce!("a + b", "a - b")(tuple(0., 0.), a);
508     assert(r2[0] == 7 && r2[1] == -7);
509     auto r3 = reduce!("a + b", "a - b")(a);
510     assert(r3[0] == 7 && r3[1] == -1);
511
512     a = [ 1, 2, 3, 4, 5 ];
513     // Stringize with commas
514     string rep = reduce!("a ~ `, ` ~ to!(string)(b)")("", a);
515     assert(rep[2 .. $] == "1, 2, 3, 4, 5", "["~rep[2 .. $]~"]");
516
517     // Test the opApply case.
518     struct OpApply
519     {
520         bool actEmpty;
521
522         int opApply(int delegate(ref int) dg)
523         {
524             int res;
525             if(actEmpty) return res;
526
527             foreach(i; 0..100)
528             {
529                 res = dg(i);
530                 if(res) break;
531             }
532             return res;
533         }
534     }
535
536     OpApply oa;
537     auto hundredSum = reduce!"a + b"(iota(100));
538     assert(reduce!"a + b"(5, oa) == hundredSum + 5);
539     assert(reduce!"a + b"(oa) == hundredSum);
540     assert(reduce!("a + b", max)(oa) == tuple(hundredSum, 99));
541     assert(reduce!("a + b", max)(tuple(5, 0), oa) == tuple(hundredSum + 5, 99));
542
543     // Test for throwing on empty range plus no seed.
544     try {
545         reduce!"a + b"([1, 2][0..0]);
546         assert(0);
547     } catch(Exception) {}
548
549     oa.actEmpty = true;
550     try {
551         reduce!"a + b"(oa);
552         assert(0);
553     } catch(Exception) {}
554 }
555
556 unittest
557 {
558     debug(std_algorithm) scope(success)
559         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
560     const float a = 0.0;
561     const float[] b = [ 1.2, 3, 3.3 ];
562     float[] c = [ 1.2, 3, 3.3 ];
563     auto r = reduce!"a + b"(a, b);
564     r = reduce!"a + b"(a, c);
565 }
566
567 /**
568 Fills a range with a value.
569
570 Example:
571 ----
572 int[] a = [ 1, 2, 3, 4 ];
573 fill(a, 5);
574 assert(a == [ 5, 5, 5, 5 ]);
575 ----
576  */
577 void fill(Range, Value)(Range range, Value filler)
578 if (isForwardRange!Range && is(typeof(range.front = filler)))
579 {
580     alias ElementType!Range T;
581     static if (hasElaborateCopyConstructor!T || !isDynamicArray!Range)
582     {
583         for (; !range.empty; range.popFront)
584         {
585             range.front = filler;
586         }
587     }
588     else
589     {
590         if (range.empty) return;
591         // Range is a dynamic array of bald values, just fill memory
592         // Can't use memcpy or memmove coz ranges overlap
593         range.front = filler;
594         auto bytesToFill = T.sizeof * (range.length - 1);
595         auto bytesFilled = T.sizeof;
596         while (bytesToFill)
597         {
598             auto fillNow = min(bytesToFill, bytesFilled);
599             memcpy(cast(void*) range.ptr + bytesFilled,
600                     cast(void*) range.ptr,
601                   fillNow);
602             bytesToFill -= fillNow;
603             bytesFilled += fillNow;
604         }
605     }
606 }
607
608 unittest
609 {
610     debug(std_algorithm) scope(success)
611         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
612     int[] a = [ 1, 2, 3 ];
613     fill(a, 6);
614     assert(a == [ 6, 6, 6 ], text(a));
615     void fun0()
616     {
617         foreach (i; 0 .. 1000)
618         {
619             foreach (ref e; a) e = 6;
620         }
621     }
622     void fun1() { foreach (i; 0 .. 1000) fill(a, 6); }
623     //void fun2() { foreach (i; 0 .. 1000) fill2(a, 6); }
624     //writeln(benchmark!(fun0, fun1, fun2)(10000));
625 }
626
627 /**
628 Fills $(D range) with a pattern copied from $(D filler). The length of
629 $(D range) does not have to be a multiple of the length of $(D
630 filler). If $(D filler) is empty, an exception is thrown.
631
632 Example:
633 ----
634 int[] a = [ 1, 2, 3, 4, 5 ];
635 int[] b = [ 8, 9 ];
636 fill(a, b);
637 assert(a == [ 8, 9, 8, 9, 8 ]);
638 ----
639  */
640
641 void fill(Range1, Range2)(Range1 range, Range2 filler)
642 if (isForwardRange!Range1 && isForwardRange!Range2
643         && is(typeof(Range1.init.front = Range2.init.front)))
644 {
645     enforce(!filler.empty);
646     auto t = filler.save;
647     for (; !range.empty; range.popFront, t.popFront)
648     {
649         if (t.empty) t = filler;
650         range.front = t.front;
651     }
652 }
653
654 unittest
655 {
656     debug(std_algorithm) scope(success)
657         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
658     int[] a = [ 1, 2, 3, 4, 5 ];
659     int[] b = [1, 2];
660     fill(a, b);
661     assert(a == [ 1, 2, 1, 2, 1 ]);
662 }
663
664 /**
665 Fills a range with a value. Assumes that the range does not currently
666 contain meaningful content. This is of interest for structs that
667 define copy constructors (for all other types, fill and
668 uninitializedFill are equivalent).
669
670 Example:
671 ----
672 struct S { ... }
673 S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
674 uninitializedFill(s, 42);
675 assert(s == [ 42, 42, 42, 42, 42 ]);
676 ----
677  */
678 void uninitializedFill(Range, Value)(Range range, Value filler)
679 if (isForwardRange!Range && is(typeof(range.front = filler)))
680 {
681     alias ElementType!Range T;
682     static if (hasElaborateCopyConstructor!T)
683     {
684         // Must construct stuff by the book
685         for (; !range.empty; range.popFront)
686         {
687             emplace!T((cast(void*) &range.front)[0 .. T.sizeof], filler);
688         }
689     }
690     else
691     {
692         // Doesn't matter whether fill is initialized or not
693         return fill(range, filler);
694     }
695 }
696
697 unittest
698 {
699     debug(std_algorithm) scope(success)
700         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
701     int[] a = [ 1, 2, 3 ];
702     uninitializedFill(a, 6);
703     assert(a == [ 6, 6, 6 ]);
704     void fun0()
705     {
706         foreach (i; 0 .. 1000)
707         {
708             foreach (ref e; a) e = 6;
709         }
710     }
711     void fun1() { foreach (i; 0 .. 1000) fill(a, 6); }
712     //void fun2() { foreach (i; 0 .. 1000) fill2(a, 6); }
713     //writeln(benchmark!(fun0, fun1, fun2)(10000));
714 }
715
716 /**
717 Initializes all elements of a range with their $(D .init)
718 value. Assumes that the range does not currently contain meaningful
719 content.
720
721 Example:
722 ----
723 struct S { ... }
724 S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
725 initialize(s);
726 assert(s == [ 0, 0, 0, 0, 0 ]);
727 ----
728  */
729 void initializeAll(Range)(Range range)
730 if (isForwardRange!Range && is(typeof(range.front = range.front)))
731 {
732     alias ElementType!Range T;
733     static assert(is(typeof(&(range.front()))) || !hasElaborateAssign!T,
734             "Cannot initialize a range that does not expose"
735             " references to its elements");
736     static if (!isDynamicArray!Range)
737     {
738         static if (is(typeof(&(range.front()))))
739         {
740             // Range exposes references
741             for (; !range.empty; range.popFront)
742             {
743                 memcpy(&(range.front()), &T.init, T.sizeof);
744             }
745         }
746         else
747         {
748             // Go the slow route
749             for (; !range.empty; range.popFront)
750             {
751                 range.front = filler;
752             }
753         }
754     }
755     else
756     {
757         fill(range, T.init);
758     }
759 }
760
761 unittest
762 {
763     debug(std_algorithm) scope(success)
764         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
765     int[] a = [ 1, 2, 3 ];
766     uninitializedFill(a, 6);
767     assert(a == [ 6, 6, 6 ]);
768     initializeAll(a);
769     assert(a == [ 0, 0, 0 ]);
770     void fun0()
771     {
772         foreach (i; 0 .. 1000)
773         {
774             foreach (ref e; a) e = 6;
775         }
776     }
777     void fun1() { foreach (i; 0 .. 1000) fill(a, 6); }
778     //void fun2() { foreach (i; 0 .. 1000) fill2(a, 6); }
779     //writeln(benchmark!(fun0, fun1, fun2)(10000));
780 }
781
782 // filter
783 /**
784 Implements the homonym function present in various programming
785 languages of functional flavor. The call $(D filter!(fun)(range))
786 returns a new range only containing elements $(D x) in $(D r) for
787 which $(D predicate(x)) is $(D true).
788
789 Example:
790 ----
791 int[] arr = [ 1, 2, 3, 4, 5 ];
792 // Sum all elements
793 auto small = filter!("a < 3")(arr);
794 assert(small == [ 1, 2 ]);
795 // In combination with chain() to span multiple ranges
796 int[] a = [ 3, -2, 400 ];
797 int[] b = [ 100, -101, 102 ];
798 auto r = filter!("a > 0")(chain(a, b));
799 assert(equal(r, [ 3, 400, 100, 102 ]));
800 // Mixing convertible types is fair game, too
801 double[] c = [ 2.5, 3.0 ];
802 auto r1 = filter!("cast(int) a != a")(chain(c, a, b));
803 assert(r1 == [ 2.5 ]);
804 ----
805  */
806 template filter(alias pred)
807 {
808     auto filter(Range)(Range rs)
809     {
810         return Filter!(unaryFun!(pred), Range)(rs);
811     }
812 }
813
814 struct Filter(alias pred, Range) if (isInputRange!(Unqual!Range))
815 {
816     alias Unqual!Range R;
817     R _input;
818
819     this(R r)
820     {
821         _input = r;
822         while (!_input.empty && !pred(_input.front)) _input.popFront;
823     }
824
825     ref Filter opSlice()
826     {
827         return this;
828     }
829
830     static if (isInfinite!Range)
831     {
832         enum bool empty = false;
833     }
834     else
835     {
836         @property bool empty() { return _input.empty; }
837     }
838
839     void popFront()
840     {
841         do
842         {
843             _input.popFront;
844         } while (!_input.empty && !pred(_input.front));
845     }
846
847     @property auto ref front()
848     {
849         return _input.front;
850     }
851
852     static if(isForwardRange!R)
853     {
854         @property typeof(this) save()
855         {
856             return typeof(this)(_input);
857         }
858     }
859 }
860
861 unittest
862 {
863     debug(std_algorithm) scope(success)
864         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
865     int[] a = [ 3, 4, 2 ];
866     auto r = filter!("a > 3")(a);
867     static assert(isForwardRange!(typeof(r)));
868     assert(equal(r, [ 4 ][]));
869
870     a = [ 1, 22, 3, 42, 5 ];
871     auto under10 = filter!("a < 10")(a);
872     assert(equal(under10, [1, 3, 5][]));
873     static assert(isForwardRange!(typeof(under10)));
874     under10.front() = 4;
875     assert(equal(under10, [4, 3, 5][]));
876     under10.front() = 40;
877     assert(equal(under10, [40, 3, 5][]));
878     under10.front() = 1;
879
880     auto infinite = filter!"a > 2"(repeat(3));
881     static assert(isInfinite!(typeof(infinite)));
882     static assert(isForwardRange!(typeof(infinite)));
883    
884     foreach(DummyType; AllDummyRanges) {
885         DummyType d;
886         auto f = filter!"a & 1"(d);
887         assert(equal(f, [1,3,5,7,9]));
888        
889         static if (isForwardRange!DummyType) {
890             static assert(isForwardRange!(typeof(f)));
891         }
892     }
893    
894     // With delegates
895     int x = 10;
896     int overX(int a) { return a > x; }
897     typeof(filter!overX(a)) getFilter()
898     {
899         return filter!overX(a);
900     }
901     auto r1 = getFilter();
902     assert(equal(r1, [22, 42]));
903    
904     // With chain
905     auto nums = [0,1,2,3,4];
906     assert(equal(filter!overX(chain(a, nums)), [22, 42]));
907    
908     // With copying of inner struct Filter to Map
909     auto arr = [1,2,3,4,5];
910     auto m = map!"a + 1"(filter!"a < 4"(arr));
911 }
912
913 unittest
914 {
915     int[] a = [ 3, 4 ];
916     const aConst = a;
917     auto r = filter!("a > 3")(aConst);
918     assert(equal(r, [ 4 ][]));
919
920     a = [ 1, 22, 3, 42, 5 ];
921     auto under10 = filter!("a < 10")(a);
922     assert(equal(under10, [1, 3, 5][]));
923     assert(under10.save == under10);
924
925     // With copying of inner struct Filter to Map
926     auto arr = [1,2,3,4,5];
927     auto m = map!"a + 1"(filter!"a < 4"(arr));
928 }
929
930 unittest
931 {
932     assert(equal(compose!(map!"2 * a", filter!"a & 1")([1,2,3,4,5]),
933                     [2,6,10]));
934     assert(equal(pipe!(filter!"a & 1", map!"2 * a")([1,2,3,4,5]),
935             [2,6,10]));
936 }
937
938 unittest
939 {
940     int x = 10;
941     int underX(int a) { return a < x; }
942     const(int)[] list = [ 1, 2, 10, 11, 3, 4 ];
943     assert(equal(filter!underX(list), [ 1, 2, 3, 4 ]));
944 }
945
946 // filterBidirectional
947 /**
948  * Similar to $(D filter), except it defines a bidirectional
949  * range. There is a speed disadvantage - the constructor spends time
950  * finding the last element in the range that satisfies the filtering
951  * condition (in addition to finding the first one). The advantage is
952  * that the filtered range can be spanned from both directions. Also,
953  * $(XREF range, retro) can be applied against the filtered range.
954  *
955 Example:
956 ----
957 int[] arr = [ 1, 2, 3, 4, 5 ];
958 auto small = filterBidirectional!("a < 3")(arr);
959 assert(small.back == 2);
960 assert(equal(small, [ 1, 2 ]));
961 assert(equal(retro(small), [ 2, 1 ]));
962 // In combination with chain() to span multiple ranges
963 int[] a = [ 3, -2, 400 ];
964 int[] b = [ 100, -101, 102 ];
965 auto r = filterBidirectional!("a > 0")(chain(a, b));
966 assert(r.back == 102);
967 ----
968  */
969 template filterBidirectional(alias pred)
970 {
971     FilterBidirectional!(unaryFun!(pred), Range)
972     filterBidirectional(Range)(Range rs)
973     {
974         return typeof(return)(rs);
975     }
976 }
977
978 struct FilterBidirectional(alias pred, Range) if (isBidirectionalRange!(Unqual!Range))
979 {
980     alias Unqual!Range R;
981     R _input;
982
983     this(R r)
984     {
985         _input = r;
986         while (!_input.empty && !pred(_input.front)) _input.popFront();
987         while (!_input.empty && !pred(_input.back)) _input.popBack();
988     }
989
990     @property bool empty() { return _input.empty; }
991
992     void popFront()
993     {
994         do
995         {
996             _input.popFront;
997         } while (!_input.empty && !pred(_input.front));
998     }
999
1000     @property auto ref front()
1001     {
1002         return _input.front;
1003     }
1004
1005     void popBack()
1006     {
1007         do
1008         {
1009             _input.popBack;
1010         } while (!_input.empty && !pred(_input.back));
1011     }
1012
1013     @property auto ref back()
1014     {
1015         return _input.back;
1016     }
1017
1018     @property typeof(this) save()
1019     {
1020         return typeof(this)(_input);
1021     }
1022 }
1023
1024 unittest
1025 {
1026     int[] arr = [ 1, 2, 3, 4, 5 ];
1027     auto small = filterBidirectional!("a < 3")(arr);
1028     static assert(isBidirectionalRange!(typeof(small)));
1029     assert(small.back == 2);
1030     assert(equal(small, [ 1, 2 ]));
1031     assert(equal(retro(small), [ 2, 1 ]));
1032     // In combination with chain() to span multiple ranges
1033     int[] a = [ 3, -2, 400 ];
1034     int[] b = [ 100, -101, 102 ];
1035     auto r = filterBidirectional!("a > 0")(chain(a, b));
1036     assert(r.back == 102);
1037 }
1038
1039 // move
1040 /**
1041 Moves $(D source) into $(D target) via a destructive
1042 copy. Specifically: $(UL $(LI If $(D hasAliasing!T) is true (see
1043 $(XREF traits, hasAliasing)), then the representation of $(D source)
1044 is bitwise copied into $(D target) and then $(D source = T.init) is
1045 evaluated.)  $(LI Otherwise, $(D target = source) is evaluated.)) See
1046 also $(XREF contracts, pointsTo).
1047
1048 Preconditions:
1049 $(D &source == &target || !pointsTo(source, source))
1050 */
1051 void move(T)(ref T source, ref T target)
1052 {
1053     if (&source == &target) return;
1054     assert(!pointsTo(source, source));
1055     static if (is(T == struct))
1056     {
1057         // Most complicated case. Destroy whatever target had in it
1058         // and bitblast source over it
1059         static if (is(typeof(target.__dtor()))) target.__dtor();
1060         memcpy(&target, &source, T.sizeof);
1061         // If the source defines a destructor or a postblit hook, we must obliterate the
1062         // object in order to avoid double freeing and undue aliasing
1063         static if (is(typeof(source.__dtor())) || is(typeof(source.__postblit())))
1064         {
1065             static T empty;
1066             memcpy(&source, &empty, T.sizeof);
1067         }
1068     }
1069     else
1070     {
1071         // Primitive data (including pointers and arrays) or class -
1072         // assignment works great
1073         target = source;
1074         // static if (is(typeof(source = null)))
1075         // {
1076         //     // Nullify the source to help the garbage collector
1077         //     source = null;
1078         // }
1079     }
1080 }
1081
1082 unittest
1083 {
1084     debug(std_algorithm) scope(success)
1085         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
1086     Object obj1 = new Object;
1087     Object obj2 = obj1;
1088     Object obj3;
1089     move(obj2, obj3);
1090     assert(obj3 is obj1);
1091
1092     struct S1 { int a = 1, b = 2; }
1093     S1 s11 = { 10, 11 };
1094     S1 s12;
1095     move(s11, s12);
1096     assert(s11.a == 10 && s11.b == 11 && s12.a == 10 && s12.b == 11);
1097
1098     struct S2 { int a = 1; int * b; }
1099     S2 s21 = { 10, new int };
1100     S2 s22;
1101     move(s21, s22);
1102     assert(s21 == s22);
1103 }
1104
1105 /// Ditto
1106 T move(T)(ref T src)
1107 {
1108     T result;
1109     move(src, result);
1110     return result;
1111 }
1112
1113 // moveAll
1114 /**
1115 For each element $(D a) in $(D src) and each element $(D b) in $(D
1116 tgt) in lockstep in increasing order, calls $(D move(a, b)). Returns
1117 the leftover portion of $(D tgt). Throws an exeption if there is not
1118 enough room in $(D tgt) to acommodate all of $(D src).
1119
1120 Preconditions:
1121 $(D walkLength(src) >= walkLength(tgt))
1122  */
1123 Range2 moveAll(Range1, Range2)(Range1 src, Range2 tgt)
1124 {
1125     for (; !src.empty; src.popFront, tgt.popFront)
1126     {
1127         enforce(!tgt.empty);
1128         move(src.front, tgt.front);
1129     }
1130     return tgt;
1131 }
1132
1133 unittest
1134 {
1135     debug(std_algorithm) scope(success)
1136         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
1137     int[] a = [ 1, 2, 3 ];
1138     int[] b = new int[5];
1139     assert(moveAll(a, b) is b[3 .. $]);
1140     assert(a == b[0 .. 3]);
1141     assert(a == [ 1, 2, 3 ]);
1142 }
1143
1144 // moveSome
1145 /**
1146 For each element $(D a) in $(D src) and each element $(D b) in $(D
1147 tgt) in lockstep in increasing order, calls $(D move(a, b)). Stops
1148 when either $(D src) or $(D tgt) have been exhausted. Returns the
1149 leftover portions of the two ranges.
1150  */
1151 Tuple!(Range1, Range2) moveSome(Range1, Range2)(Range1 src, Range2 tgt)
1152 {
1153     for (; !src.empty && !tgt.empty; src.popFront, tgt.popFront)
1154     {
1155         enforce(!tgt.empty);
1156         move(src.front, tgt.front);
1157     }
1158     return tuple(src, tgt);
1159 }
1160
1161 unittest
1162 {
1163     debug(std_algorithm) scope(success)
1164         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
1165     int[] a = [ 1, 2, 3, 4, 5 ];
1166     int[] b = new int[3];
1167     assert(moveSome(a, b)[0] is a[3 .. $]);
1168     assert(a[0 .. 3] == b);
1169     assert(a == [ 1, 2, 3, 4, 5 ]);
1170 }
1171
1172 // swap
1173 /**
1174 Swaps $(D lhs) and $(D rhs). See also $(XREF exception, pointsTo).
1175
1176 Preconditions:
1177
1178 $(D !pointsTo(lhs, lhs) && !pointsTo(lhs, rhs) && !pointsTo(rhs, lhs)
1179 && !pointsTo(rhs, rhs))
1180  */
1181 void swap(T)(ref T lhs, ref T rhs) @trusted pure nothrow
1182 if (isMutable!T && !is(typeof(T.init.proxySwap(T.init))))
1183 {
1184     static if (hasElaborateAssign!T)
1185     {
1186         // For structs with non-trivial assignment, move memory directly
1187         // First check for undue aliasing
1188         assert(!pointsTo(lhs, rhs) && !pointsTo(rhs, lhs)
1189             && !pointsTo(lhs, lhs) && !pointsTo(rhs, rhs));
1190         // Swap bits
1191         ubyte[T.sizeof] t = void;
1192         auto a = (cast(ubyte*) &lhs)[0 .. T.sizeof];
1193         auto b = (cast(ubyte*) &rhs)[0 .. T.sizeof];
1194         t[] = a[];
1195         a[] = b[];
1196         b[] = t[];
1197     }
1198     else
1199     {
1200         // Temporary fix Bug 4789.  Wor around the fact that assigning a static
1201         // array to itself doesn't work properly.
1202         static if(isStaticArray!T) {
1203             if(lhs.ptr is rhs.ptr) {
1204                 return;
1205             }
1206         }
1207
1208         // For non-struct types, suffice to do the classic swap
1209         auto tmp = lhs;
1210         lhs = rhs;
1211         rhs = tmp;
1212     }
1213 }
1214
1215 // Not yet documented
1216 void swap(T)(T lhs, T rhs) if (is(typeof(T.init.proxySwap(T.init))))
1217 {
1218     lhs.proxySwap(rhs);
1219 }
1220
1221 unittest
1222 {
1223     debug(std_algorithm) scope(success)
1224         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
1225     int a = 42, b = 34;
1226     swap(a, b);
1227     assert(a == 34 && b == 42);
1228
1229     struct S { int x; char c; int[] y; }
1230     S s1 = { 0, 'z', [ 1, 2 ] };
1231     S s2 = { 42, 'a', [ 4, 6 ] };
1232     //writeln(s2.tupleof.stringof);
1233     swap(s1, s2);
1234     assert(s1.x == 42);
1235     assert(s1.c == 'a');
1236     assert(s1.y == [ 4, 6 ]);
1237
1238     assert(s2.x == 0);
1239     assert(s2.c == 'z');
1240     assert(s2.y == [ 1, 2 ]);
1241
1242     immutable int imm1, imm2;
1243     static assert(!__traits(compiles, swap(imm1, imm2)));
1244 }
1245
1246 unittest
1247 {
1248     struct NoCopy
1249     {
1250         this(this) { assert(0); }
1251         int n;
1252         string s;
1253     }
1254     NoCopy nc1, nc2;
1255     nc1.n = 127; nc1.s = "abc";
1256     nc2.n = 513; nc2.s = "uvwxyz";
1257     swap(nc1, nc2);
1258     assert(nc1.n == 513 && nc1.s == "uvwxyz");
1259     assert(nc2.n == 127 && nc2.s == "abc");
1260
1261     struct NoCopyHolder
1262     {
1263         NoCopy noCopy;
1264     }
1265     NoCopyHolder h1, h2;
1266     h1.noCopy.n = 31; h1.noCopy.s = "abc";
1267     h2.noCopy.n = 65; h2.noCopy.s = null;
1268     swap(h1, h2);
1269     assert(h1.noCopy.n == 65 && h1.noCopy.s == null);
1270     assert(h2.noCopy.n == 31 && h2.noCopy.s == "abc");
1271
1272     const NoCopy const1, const2;
1273     static assert(!__traits(compiles, swap(const1, const2)));
1274 }
1275
1276 void swapFront(R1, R2)(R1 r1, R2 r2)
1277     if (isInputRange!R1 && isInputRange!R2)
1278 {
1279     static if (is(typeof(swap(r1.front, r2.front))))
1280     {
1281         swap(r1.front, r2.front);
1282     }
1283     else
1284     {
1285         auto t1 = moveFront(r1), t2 = moveFront(r2);
1286         r1.front = move(t2);
1287         r2.front = move(t1);
1288     }
1289 }
1290
1291 // splitter
1292 /**
1293 Splits a range using an element as a separator. This can be used with
1294 any range type, but is most popular with string types.
1295
1296 Two adjacent separators are considered to surround an empty element in
1297 the split range.
1298
1299 If the empty range is given, the result is a range with one empty
1300 element. If a range with one separator is given, the result is a range
1301 with two empty elements.
1302
1303 Example:
1304 ---
1305 assert(equal(splitter("hello  world", ' '), [ "hello", "", "world" ]));
1306 int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
1307 int[][] w = [ [1, 2], [], [3], [4, 5] ];
1308 assert(equal(splitter(a, 0), w));
1309 a = null;
1310 assert(equal(splitter(a, 0), [ (int[]).init ]));
1311 a = [ 0 ];
1312 assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ]));
1313 a = [ 0, 1 ];
1314 assert(equal(splitter(a, 0), [ [], [1] ]));
1315 ----
1316 */
1317 struct Splitter(Range, Separator)
1318     if (is(typeof(ElementType!Range.init == Separator.init)) && hasSlicing!Range)
1319 {
1320 private:
1321     Range _input;
1322     Separator _separator;
1323     enum size_t _unComputed = size_t.max - 1, _atEnd = size_t.max;
1324     size_t _frontLength = _unComputed;
1325     size_t _backLength = _unComputed;
1326
1327     static if(isBidirectionalRange!Range)
1328     {
1329         static sizediff_t lastIndexOf(Range haystack, Separator needle)
1330         {
1331             immutable index = countUntil(retro(haystack), needle);
1332             return (index == -1) ? -1 : haystack.length - 1 - index;
1333         }
1334     }
1335
1336 public:
1337     this(Range input, Separator separator)
1338     {
1339         _input = input;
1340         _separator = separator;
1341         // computeFront();
1342         // computeBack();
1343     }
1344
1345     static if (isInfinite!Range)
1346     {
1347         enum bool empty = false;
1348     }
1349     else
1350     {
1351         @property bool empty()
1352         {
1353             return _frontLength == _atEnd;
1354         }
1355     }
1356
1357     @property Range front()
1358     {
1359         assert(!empty);
1360         if (_frontLength == _unComputed)
1361         {
1362             _frontLength = countUntil(_input, _separator);
1363             if (_frontLength == -1) _frontLength = _input.length;
1364         }
1365         return _input[0 .. _frontLength];
1366     }
1367
1368     void popFront()
1369     {
1370         assert(!empty);
1371         if (_frontLength == _unComputed)
1372         {
1373             front;
1374         }
1375         assert(_frontLength <= _input.length);
1376         if (_frontLength == _input.length)
1377         {
1378             // no more input and need to fetch => done
1379             _frontLength = _atEnd;
1380
1381             // Probably don't need this, but just for consistency:
1382             _backLength = _atEnd;
1383         }
1384         else
1385         {
1386             _input = _input[_frontLength .. _input.length];
1387             skipOver(_input, _separator) || assert(false);
1388             _frontLength = _unComputed;
1389         }
1390     }
1391
1392     static if(isForwardRange!Range)
1393     {
1394         @property typeof(this) save()
1395         {
1396             auto ret = this;
1397             ret._input = _input.save;
1398             return ret;
1399         }
1400     }
1401
1402     static if(isBidirectionalRange!Range)
1403     {
1404         @property Range back()
1405         {
1406             assert(!empty);
1407             if (_backLength == _unComputed)
1408             {
1409                 immutable lastIndex = lastIndexOf(_input, _separator);
1410                 if(lastIndex == -1)
1411                 {
1412                     _backLength = _input.length;
1413                 }
1414                 else
1415                 {
1416                     _backLength = _input.length - lastIndex - 1;
1417                 }
1418             }
1419             return _input[_input.length - _backLength .. _input.length];
1420         }
1421
1422         void popBack()
1423         {
1424             assert(!empty);
1425             if (_backLength == _unComputed)
1426             {
1427                 back;
1428             }
1429             assert(_backLength <= _input.length);
1430             if (_backLength == _input.length)
1431             {
1432                 // no more input and need to fetch => done
1433                 _frontLength = _atEnd;
1434                 _backLength = _atEnd;
1435             }
1436             else
1437             {
1438                 _input = _input[0 .. _input.length - _backLength];
1439                 if(!_input.empty && _input.back == _separator)
1440                 {
1441                     _input.popBack();
1442                 }
1443                 else
1444                 {
1445                     assert(false);
1446                 }
1447                 _backLength = _unComputed;
1448             }
1449         }
1450     }
1451 }
1452
1453 /// Ditto
1454 Splitter!(Range, Separator)
1455 splitter(Range, Separator)(Range r, Separator s)
1456 if (is(typeof(ElementType!Range.init == ElementType!Separator.init))
1457        ||
1458     is(typeof(ElementType!Range.init == Separator.init))
1459     )
1460 {
1461     return typeof(return)(r, s);
1462 }
1463
1464 unittest
1465 {
1466     debug(std_algorithm) scope(success)
1467         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
1468     assert(equal(splitter("hello  world", ' '), [ "hello", "", "world" ]));
1469     int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
1470     int[][] w = [ [1, 2], [], [3], [4, 5], [] ];
1471     static assert(isForwardRange!(typeof(splitter(a, 0))));
1472
1473     // foreach (x; splitter(a, 0)) {
1474     //     writeln("[", x, "]");
1475     // }
1476     assert(equal(splitter(a, 0), w));
1477     a = null;
1478     assert(equal(splitter(a, 0), [ (int[]).init ][]));
1479     a = [ 0 ];
1480     assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ][]));
1481     a = [ 0, 1 ];
1482     assert(equal(splitter(a, 0), [ [], [1] ][]));
1483
1484     // Thoroughly exercise the bidirectional stuff.
1485     auto str = "abc abcd abcde ab abcdefg abcdefghij ab ac ar an at ada";
1486     assert(equal(
1487         retro(splitter(str, 'a')),
1488         retro(array(splitter(str, 'a')))
1489     ));
1490
1491     // Test interleaving front and back.
1492     auto split = splitter(str, 'a');
1493     assert(split.front == "");
1494     assert(split.back == "");
1495     split.popBack();
1496     assert(split.back == "d");
1497     split.popFront();
1498     assert(split.front == "bc ");
1499     assert(split.back == "d");
1500     split.popFront();
1501     split.popBack();
1502     assert(split.back == "t ");
1503     split.popBack();
1504     split.popBack();
1505     split.popFront();
1506     split.popFront();
1507     assert(split.front == "b ");
1508     assert(split.back == "r ");
1509
1510     foreach(DummyType; AllDummyRanges) {  // Bug 4408
1511         static if(isRandomAccessRange!DummyType) {
1512             static assert(isBidirectionalRange!DummyType);
1513             DummyType d;
1514             auto s = splitter(d, 5);
1515             assert(equal(s.front, [1,2,3,4]));
1516             assert(equal(s.back, [6,7,8,9,10]));
1517
1518
1519             auto s2 = splitter(d, [4, 5]);
1520             assert(equal(s2.front, [1,2,3]));
1521             assert(equal(s2.back, [6,7,8,9,10]));
1522         }
1523     }
1524 }
1525
1526 /**
1527 Splits a range using another range as a separator. This can be used
1528 with any range type, but is most popular with string types.
1529  */
1530 struct Splitter(Range, Separator)
1531 if (is(typeof(Range.init.front == Separator.init.front) : bool))
1532 {
1533 private:
1534     Range _input;
1535     Separator _separator;
1536     // _frontLength == size_t.max means empty
1537     size_t _frontLength = size_t.max;
1538     static if (isBidirectionalRange!Range)
1539         size_t _backLength = size_t.max;
1540
1541     size_t separatorLength() { return _separator.length; }
1542
1543     void ensureFrontLength()
1544     {
1545         if (_frontLength != _frontLength.max) return;
1546         assert(!_input.empty);
1547         // compute front length
1548         _frontLength = _input.length - find(_input, _separator).length;
1549         static if (isBidirectionalRange!Range)
1550             if (_frontLength == _input.length) _backLength = _frontLength;
1551     }
1552
1553     void ensureBackLength()
1554     {
1555         static if (isBidirectionalRange!Range)
1556             if (_backLength != _backLength.max) return;
1557         assert(!_input.empty);
1558         // compute back length
1559         static if (isBidirectionalRange!Range)
1560         {
1561             _backLength = _input.length -
1562                 find(retro(_input), retro(_separator)).length;
1563         }
1564     }
1565
1566 public:
1567     this(Range input, Separator separator)
1568     {
1569         _input = input;
1570         _separator = separator;
1571     }
1572
1573     @property Range front()
1574     {
1575         assert(!empty);
1576         ensureFrontLength();
1577         return _input[0 .. _frontLength];
1578     }
1579
1580     static if (isInfinite!Range)
1581     {
1582         enum bool empty = false;  // Propagate infiniteness
1583     }
1584     else
1585     {
1586         @property bool empty()
1587         {
1588             return _frontLength == size_t.max && _input.empty;
1589         }
1590     }
1591
1592     void popFront()
1593     {
1594         assert(!empty);
1595         ensureFrontLength;
1596         if (_frontLength == _input.length)
1597         {
1598             // done, there's no separator in sight
1599             _input = _input[_frontLength .. _frontLength];
1600             _frontLength = _frontLength.max;
1601             static if (isBidirectionalRange!Range)
1602                 _backLength = _backLength.max;
1603             return;
1604         }
1605         if (_frontLength + separatorLength == _input.length)
1606         {
1607             // Special case: popping the first-to-last item; there is
1608             // an empty item right after this.
1609             _input = _input[_input.length .. _input.length];
1610             _frontLength = 0;
1611             static if (isBidirectionalRange!Range)
1612                 _backLength = 0;
1613             return;
1614         }
1615         // Normal case, pop one item and the separator, get ready for
1616         // reading the next item
1617         _input = _input[_frontLength + separatorLength .. _input.length];
1618         // mark _frontLength as uninitialized
1619         _frontLength = _frontLength.max;
1620     }
1621
1622     static if(isForwardRange!Range)
1623     {
1624         @property typeof(this) save()
1625         {
1626             auto ret = this;
1627             ret._input = _input.save;
1628             return ret;
1629         }
1630     }
1631
1632 // Bidirectional functionality as suggested by Brad Roberts.
1633     static if (isBidirectionalRange!Range)
1634     {
1635         @property Range back()
1636         {
1637             ensureBackLength;
1638             return _input[_input.length - _backLength .. _input.length];
1639         }
1640
1641         void popBack()
1642         {
1643             ensureBackLength;
1644             if (_backLength == _input.length)
1645             {
1646                 // done
1647                 _input = _input[0 .. 0];
1648                 _frontLength = _frontLength.max;
1649                 _backLength = _backLength.max;
1650                 return;
1651             }
1652             if (_backLength + separatorLength == _input.length)
1653             {
1654                 // Special case: popping the first-to-first item; there is
1655                 // an empty item right before this. Leave the separator in.
1656                 _input = _input[0 .. 0];
1657                 _frontLength = 0;
1658                 _backLength = 0;
1659                 return;
1660             }
1661             // Normal case
1662             _input = _input[0 .. _input.length - _backLength - separatorLength];
1663             _backLength = _backLength.max;
1664         }
1665     }
1666 }
1667
1668 unittest
1669 {
1670     debug(std_algorithm) scope(success)
1671         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
1672     auto s = ",abc, de, fg,hi,";
1673     auto sp0 = splitter(s, ',');
1674     // //foreach (e; sp0) writeln("[", e, "]");
1675     assert(equal(sp0, ["", "abc", " de", " fg", "hi", ""][]));
1676
1677     auto s1 = ", abc, de,  fg, hi, ";
1678     auto sp1 = splitter(s1, ", ");
1679     //foreach (e; sp1) writeln("[", e, "]");
1680     assert(equal(sp1, ["", "abc", "de", " fg", "hi", ""][]));
1681     static assert(isForwardRange!(typeof(sp1)));
1682
1683     int[] a = [ 1, 2, 0, 3, 0, 4, 5, 0 ];
1684     int[][] w = [ [1, 2], [3], [4, 5], [] ];
1685     uint i;
1686     foreach (e; splitter(a, 0))
1687     {
1688         assert(i < w.length);
1689         assert(e == w[i++]);
1690     }
1691     assert(i == w.length);
1692     // // Now go back
1693     // auto s2 = splitter(a, 0);
1694
1695     // foreach (e; retro(s2))
1696     // {
1697     //     assert(i > 0);
1698     //     assert(equal(e, w[--i]), text(e));
1699     // }
1700     // assert(i == 0);
1701
1702     wstring names = ",peter,paul,jerry,";
1703     auto words = split(names, ",");
1704     assert(walkLength(words) == 5, text(walkLength(words)));
1705 }
1706
1707 unittest
1708 {
1709     debug(std_algorithm) scope(success)
1710         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
1711     auto s6 = ",";
1712     auto sp6 = splitter(s6, ',');
1713     foreach (e; sp6)
1714     {
1715         //writeln("{", e, "}");
1716     }
1717     assert(equal(sp6, ["", ""][]));
1718 }
1719
1720 struct Splitter(alias isTerminator, Range,
1721         Slice = Select!(is(typeof(Range.init[0 .. 1])),
1722                 Range,
1723                 ElementType!(Range)[]))
1724 if(!is(isTerminator))
1725 {
1726     private Range _input;
1727     private size_t _end;
1728     private alias unaryFun!isTerminator _isTerminator;
1729
1730     this(Range input)
1731     {
1732         _input = input;
1733         if (_input.empty)
1734         {
1735             _end = _end.max;
1736         }
1737         else
1738         {
1739             // Chase first terminator
1740             while (_end < _input.length && !_isTerminator(_input[_end]))
1741             {
1742                 ++_end;
1743             }
1744         }
1745     }
1746
1747     static if (isInfinite!Range)
1748     {
1749         enum bool empty = false;  // Propagate infiniteness.
1750     }
1751     else
1752     {
1753         @property bool empty()
1754         {
1755             return _end == _end.max;
1756         }
1757     }
1758
1759     @property Range front()
1760     {
1761         assert(!empty);
1762         return _input[0 .. _end];
1763     }
1764
1765     void popFront()
1766     {
1767         assert(!empty);
1768         if (_input.empty)
1769         {
1770             _end = _end.max;
1771             return;
1772         }
1773         // Skip over existing word
1774         _input = _input[_end .. _input.length];
1775         // Skip terminator
1776         for (;;)
1777         {
1778             if (_input.empty)
1779             {
1780                 // Nothing following the terminator - done
1781                 _end = _end.max;
1782                 return;
1783             }
1784             if (!_isTerminator(_input.front))
1785             {
1786                 // Found a legit next field
1787                 break;
1788             }
1789             _input.popFront();
1790         }
1791         assert(!_input.empty && !_isTerminator(_input.front));
1792         // Prepare _end
1793         _end = 1;
1794         while (_end < _input.length && !_isTerminator(_input[_end]))
1795         {
1796             ++_end;
1797         }
1798     }
1799
1800     static if(isForwardRange!Range)
1801     {
1802         @property typeof(this) save()
1803         {
1804             auto ret = this;
1805             ret._input = _input.save;
1806             return ret;
1807         }
1808     }
1809 }
1810
1811 Splitter!(isTerminator, Range)
1812 splitter(alias isTerminator, Range)(Range input)
1813 if (is(typeof(unaryFun!(isTerminator)(ElementType!(Range).init))))
1814 {
1815     return typeof(return)(input);
1816 }
1817
1818 unittest
1819 {
1820     debug(std_algorithm) scope(success)
1821         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
1822     void compare(string sentence, string[] witness)
1823     {
1824         foreach (word; splitter!"a == ' '"(sentence))
1825         {
1826             assert(word == witness.front, word);
1827             witness.popFront();
1828         }
1829         assert(witness.empty, witness[0]);
1830     }
1831
1832     compare(" Mary    has a little lamb.   ",
1833             ["", "Mary", "has", "a", "little", "lamb."]);
1834     compare("Mary    has a little lamb.   ",
1835             ["Mary", "has", "a", "little", "lamb."]);
1836     compare("Mary    has a little lamb.",
1837             ["Mary", "has", "a", "little", "lamb."]);
1838     compare("", []);
1839     compare(" ", [""]);
1840
1841     static assert(isForwardRange!(typeof(splitter!"a == ' '"("ABC"))));
1842
1843     foreach(DummyType; AllDummyRanges)
1844     {
1845         static if(isRandomAccessRange!DummyType)
1846         {
1847             auto rangeSplit = splitter!"a == 5"(DummyType.init);
1848             assert(equal(rangeSplit.front, [1,2,3,4]));
1849             rangeSplit.popFront();
1850             assert(equal(rangeSplit.front, [6,7,8,9,10]));
1851         }
1852     }
1853 }
1854
1855 // joiner
1856 /**
1857 Lazily joins a range of ranges with a separator. The separator itself
1858 is a range.
1859
1860 Example:
1861 ----
1862 assert(equal(joiner([""], "xyz"), ""));
1863 assert(equal(joiner(["", ""], "xyz"), "xyz"));
1864 assert(equal(joiner(["", "abc"], "xyz"), "xyzabc"));
1865 assert(equal(joiner(["abc", ""], "xyz"), "abcxyz"));
1866 assert(equal(joiner(["abc", "def"], "xyz"), "abcxyzdef"));
1867 assert(equal(joiner(["Mary", "has", "a", "little", "lamb"], "..."),
1868   "Mary...has...a...little...lamb"));
1869 ----
1870  */
1871 auto joiner(RoR, Separator)(RoR r, Separator sep)
1872 if (isForwardRange!RoR && isInputRange!(ElementType!RoR)
1873         && isForwardRange!Separator
1874         && is(ElementType!Separator : ElementType!(ElementType!RoR)))
1875 {
1876     static struct Result
1877     {
1878         private RoR _items;
1879         private ElementType!RoR _current;
1880         private Separator _sep, _currentSep;
1881
1882         private void useSeparator()
1883         {
1884             assert(_currentSep.empty && _current.empty,
1885                     "joiner: internal error");
1886             if (_sep.empty)
1887             {
1888                 // Advance to the next range in the
1889                 // input
1890                 //_items.popFront();
1891                 for (;; _items.popFront())
1892                 {
1893                     if (_items.empty) return;
1894                     if (!_items.front.empty) break;
1895                 }
1896                 _current = _items.front;
1897                 _items.popFront();
1898             }
1899             else
1900             {
1901                 // Must make sure something is coming after the
1902                 // separator - it's a separator, not a terminator!
1903                 if (_items.empty) return;
1904                 _currentSep = _sep.save;
1905                 assert(!_currentSep.empty);
1906             }
1907         }
1908
1909         private void useItem()
1910         {
1911             assert(_currentSep.empty && _current.empty,
1912                     "joiner: internal error");
1913             // Use the input
1914             if (_items.empty) return;
1915             _current = _items.front;
1916             _items.popFront();
1917             if (!_current.empty)
1918             {
1919                 return;
1920             }
1921             // No data in the current item - toggle to use the
1922             // separator
1923             useSeparator();
1924         }
1925        
1926         this(RoR items, Separator sep)
1927         {
1928             _items = items;
1929             _sep = sep;
1930             useItem();
1931             // We need the separator if the input has at least two
1932             // elements
1933             if (_current.empty && _items.empty)
1934             {
1935                 // Vacate the whole thing
1936                 _currentSep = _currentSep.init;
1937             }
1938         }
1939
1940         @property auto empty()
1941         {
1942             return _current.empty && _currentSep.empty;
1943         }
1944        
1945         @property ElementType!(ElementType!RoR) front()
1946         {
1947             if (!_currentSep.empty) return _currentSep.front;
1948             assert(!_current.empty);
1949             return _current.front;
1950         }
1951        
1952         void popFront()
1953         {
1954             assert(!empty);
1955             // Using separator?
1956             if (!_currentSep.empty)
1957             {
1958                 _currentSep.popFront();
1959                 if (!_currentSep.empty) return;
1960                 useItem();
1961             }
1962             else
1963             {
1964                 // we're using the range
1965                 _current.popFront();
1966                 if (!_current.empty) return;
1967                 useSeparator();
1968             }
1969         }
1970
1971         static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
1972         {
1973             @property auto save()
1974             {
1975                 Result copy;
1976                 copy._items = _items.save;
1977                 copy._current = _current.save;
1978                 copy._sep = _sep.save;
1979                 copy._currentSep = _currentSep.save;
1980                 return copy;
1981             }
1982         }
1983     }
1984     return Result(r, sep);
1985 }
1986
1987 unittest
1988 {
1989     debug(std_algorithm) scope(success)
1990         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
1991     static assert(isInputRange!(typeof(joiner([""], ""))));
1992     static assert(isForwardRange!(typeof(joiner([""], ""))));
1993     assert(equal(joiner([""], "xyz"), ""), text(joiner([""], "xyz")));
1994     assert(equal(joiner(["", ""], "xyz"), "xyz"), text(joiner(["", ""], "xyz")));
1995     assert(equal(joiner(["", "abc"], "xyz"), "xyzabc"));
1996     assert(equal(joiner(["abc", ""], "xyz"), "abcxyz"));
1997     assert(equal(joiner(["abc", "def"], "xyz"), "abcxyzdef"));
1998     assert(equal(joiner(["Mary", "has", "a", "little", "lamb"], "..."),
1999                     "Mary...has...a...little...lamb"));
2000 }
2001
2002 auto joiner(RoR)(RoR r)
2003 if (isInputRange!RoR && isInputRange!(ElementType!RoR))
2004 {
2005     static struct Result
2006     {
2007     private:
2008         RoR _items;
2009         ElementType!RoR _current;
2010         void prepare()
2011         {
2012             for (;; _items.popFront())
2013             {
2014                 if (_items.empty) return;
2015                 if (!_items.front.empty) break;
2016             }
2017             _current = _items.front;
2018             _items.popFront();
2019         }
2020     public:
2021         this(RoR r)
2022         {
2023             _items = r;
2024             prepare();
2025         }
2026         static if (isInfinite!(ElementType!RoR))
2027         {
2028             enum bool empty = false;
2029         }
2030         else
2031         {
2032             @property auto empty()
2033             {
2034                 return _current.empty;
2035             }
2036         }
2037         @property auto ref front()
2038         {
2039             assert(!empty);
2040             return _current.front;
2041         }
2042         void popFront()
2043         {
2044             assert(!_current.empty);
2045             _current.popFront();
2046             if (_current.empty) prepare();
2047         }
2048         static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
2049         {
2050             @property auto save()
2051             {
2052                 Result copy;
2053                 copy._items = _items.save;
2054                 copy._current = _current.save;
2055                 return copy;
2056             }
2057         }
2058     }
2059     return Result(r);
2060 }
2061
2062 unittest
2063 {
2064     debug(std_algorithm) scope(success)
2065         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2066     static assert(isInputRange!(typeof(joiner([""]))));
2067     static assert(isForwardRange!(typeof(joiner([""]))));
2068     assert(equal(joiner([""]), ""));
2069     assert(equal(joiner(["", ""]), ""));
2070     assert(equal(joiner(["", "abc"]), "abc"));
2071     assert(equal(joiner(["abc", ""]), "abc"));
2072     assert(equal(joiner(["abc", "def"]), "abcdef"));
2073     assert(equal(joiner(["Mary", "has", "a", "little", "lamb"]),
2074                     "Maryhasalittlelamb"));
2075     assert(equal(joiner(std.range.repeat("abc", 3)), "abcabcabc"));
2076
2077     // joiner allows in-place mutation!
2078     auto a = [ [1, 2, 3], [42, 43] ];
2079     auto j = joiner(a);
2080     j.front() = 44;
2081     assert(a == [ [44, 2, 3], [42, 43] ]);
2082 }
2083
2084 // uniq
2085 /**
2086 Iterates unique consecutive elements of the given range (functionality
2087 akin to the $(WEB wikipedia.org/wiki/_Uniq, _uniq) system
2088 utility). Equivalence of elements is assessed by using the predicate
2089 $(D pred), by default $(D "a == b"). If the given range is
2090 bidirectional, $(D uniq) also yields a bidirectional range.
2091
2092 Example:
2093 ----
2094 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
2095 assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));
2096 ----
2097 */
2098 struct Uniq(alias pred, R)
2099 {
2100     R _input;
2101
2102     this(R input)
2103     {
2104         _input = input;
2105     }
2106
2107     ref Uniq opSlice()
2108     {
2109         return this;
2110     }
2111
2112     void popFront()
2113     {
2114         auto last = _input.front;
2115         do
2116         {
2117             _input.popFront;
2118         }
2119         while (!_input.empty && binaryFun!(pred)(last, _input.front));
2120     }
2121
2122     @property ElementType!(R) front() { return _input.front; }
2123
2124     static if (isBidirectionalRange!R)
2125     {
2126         void popBack()
2127         {
2128             auto last = _input.back;
2129             do
2130             {
2131                 _input.popBack;
2132             }
2133             while (!_input.empty && binaryFun!(pred)(last, _input.back));
2134         }
2135
2136         @property ElementType!(R) back() { return _input.back; }
2137     }
2138
2139     static if (isInfinite!R)
2140     {
2141         enum bool empty = false;  // Propagate infiniteness.
2142     }
2143     else
2144     {
2145         @property bool empty() { return _input.empty; }
2146     }
2147
2148
2149     static if (isForwardRange!R) {
2150         @property typeof(this) save() {
2151             return typeof(this)(_input.save);
2152         }
2153     }
2154 }
2155
2156 /// Ditto
2157 Uniq!(pred, Range) uniq(alias pred = "a == b", Range)(Range r)
2158 {
2159     return typeof(return)(r);
2160 }
2161
2162 unittest
2163 {
2164     debug(std_algorithm) scope(success)
2165         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2166     int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
2167     auto r = uniq(arr);
2168     static assert(isForwardRange!(typeof(r)));
2169
2170     assert(equal(r, [ 1, 2, 3, 4, 5 ][]));
2171     assert(equal(retro(r), retro([ 1, 2, 3, 4, 5 ][])));
2172
2173     foreach(DummyType; AllDummyRanges) {
2174         DummyType d;
2175         auto u = uniq(d);
2176         assert(equal(u, [1,2,3,4,5,6,7,8,9,10]));
2177
2178         static assert(d.rt == RangeType.Input || isForwardRange!(typeof(u)));
2179
2180         static if (d.rt >= RangeType.Bidirectional) {
2181             assert(equal(retro(u), [10,9,8,7,6,5,4,3,2,1]));
2182         }
2183     }
2184 }
2185
2186 // group
2187 /**
2188 Similarly to $(D uniq), $(D group) iterates unique consecutive
2189 elements of the given range. The element type is $(D
2190 Tuple!(ElementType!R, uint)) because it includes the count of
2191 equivalent elements seen. Equivalence of elements is assessed by using
2192 the predicate $(D pred), by default $(D "a == b").
2193
2194 $(D Group) is an input range if $(D R) is an input range, and a
2195 forward range in all other cases.
2196
2197 Example:
2198 ----
2199 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
2200 assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
2201     tuple(4, 3u), tuple(5, 1u) ][]));
2202 ----
2203 */
2204 struct Group(alias pred, R) if (isInputRange!R)
2205 {
2206     private R _input;
2207     private Tuple!(ElementType!R, uint) _current;
2208     private alias binaryFun!pred comp;
2209
2210     this(R input)
2211     {
2212         _input = input;
2213         if (!_input.empty) popFront;
2214     }
2215
2216     void popFront()
2217     {
2218         if (_input.empty)
2219         {
2220             _current[1] = 0;
2221         }
2222         else
2223         {
2224             _current = tuple(_input.front, 1u);
2225             _input.popFront;
2226             while (!_input.empty && comp(_current[0], _input.front))
2227             {
2228                 ++_current[1];
2229                 _input.popFront;
2230             }
2231         }
2232     }
2233
2234     static if (isInfinite!R)
2235     {
2236         enum bool empty = false;  // Propagate infiniteness.
2237     }
2238     else
2239     {
2240         @property bool empty()
2241         {
2242             return _current[1] == 0;
2243         }
2244     }
2245
2246     @property ref Tuple!(ElementType!R, uint) front()
2247     {
2248         assert(!empty);
2249         return _current;
2250     }
2251
2252     static if (isForwardRange!R) {
2253         @property typeof(this) save() {
2254             typeof(this) ret;
2255             ret._input = this._input.save;
2256             ret._current = this._current;
2257
2258             return ret;
2259         }
2260     }
2261 }
2262
2263 /// Ditto
2264 Group!(pred, Range) group(alias pred = "a == b", Range)(Range r)
2265 {
2266     return typeof(return)(r);
2267 }
2268
2269 unittest
2270 {
2271     debug(std_algorithm) scope(success)
2272         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2273     int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
2274     assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
2275                             tuple(4, 3u), tuple(5, 1u) ][]));
2276     static assert(isForwardRange!(typeof(group(arr))));
2277
2278     foreach(DummyType; AllDummyRanges) {
2279         DummyType d;
2280         auto g = group(d);
2281
2282         static assert(d.rt == RangeType.Input || isForwardRange!(typeof(g)));
2283
2284         assert(equal(g, [tuple(1, 1u), tuple(2, 1u), tuple(3, 1u), tuple(4, 1u),
2285             tuple(5, 1u), tuple(6, 1u), tuple(7, 1u), tuple(8, 1u),
2286             tuple(9, 1u), tuple(10, 1u)]));
2287     }
2288 }
2289
2290 // overwriteAdjacent
2291 /*
2292 Reduces $(D r) by shifting it to the left until no adjacent elements
2293 $(D a), $(D b) remain in $(D r) such that $(D pred(a, b)). Shifting is
2294 performed by evaluating $(D move(source, target)) as a primitive. The
2295 algorithm is stable and runs in $(BIGOH r.length) time. Returns the
2296 reduced range.
2297
2298 The default $(XREF _algorithm, move) performs a potentially
2299 destructive assignment of $(D source) to $(D target), so the objects
2300 beyond the returned range should be considered "empty". By default $(D
2301 pred) compares for equality, in which case $(D overwriteAdjacent)
2302 collapses adjacent duplicate elements to one (functionality akin to
2303 the $(WEB wikipedia.org/wiki/Uniq, uniq) system utility).
2304
2305 Example:
2306 ----
2307 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
2308 auto r = overwriteAdjacent(arr);
2309 assert(r == [ 1, 2, 3, 4, 5 ]);
2310 ----
2311 */
2312 // Range overwriteAdjacent(alias pred, alias move, Range)(Range r)
2313 // {
2314 //     if (r.empty) return r;
2315 //     //auto target = begin(r), e = end(r);
2316 //     auto target = r;
2317 //     auto source = r;
2318 //     source.popFront;
2319 //     while (!source.empty)
2320 //     {
2321 //         if (!pred(target.front, source.front))
2322 //         {
2323 //             target.popFront;
2324 //             continue;
2325 //         }
2326 //         // found an equal *source and *target
2327 //         for (;;)
2328 //         {
2329 //             //@@@
2330 //             //move(source.front, target.front);
2331 //             target[0] = source[0];
2332 //             source.popFront;
2333 //             if (source.empty) break;
2334 //             if (!pred(target.front, source.front)) target.popFront;
2335 //         }
2336 //         break;
2337 //     }
2338 //     return range(begin(r), target + 1);
2339 // }
2340
2341 // /// Ditto
2342 // Range overwriteAdjacent(
2343 //     string fun = "a == b",
2344 //     alias move = .move,
2345 //     Range)(Range r)
2346 // {
2347 //     return .overwriteAdjacent!(binaryFun!(fun), move, Range)(r);
2348 // }
2349
2350 // unittest
2351 // {
2352 //     int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
2353 //     auto r = overwriteAdjacent(arr);
2354 //     assert(r == [ 1, 2, 3, 4, 5 ]);
2355 //     assert(arr == [ 1, 2, 3, 4, 5, 3, 4, 4, 4, 5 ]);
2356
2357 // }
2358
2359 // find
2360 /**
2361 Finds an individual element in an input range. Elements of $(D
2362 haystack) are compared with $(D needle) by using predicate $(D
2363 pred). Performs $(BIGOH walkLength(haystack)) evaluations of $(D
2364 pred). See also $(WEB sgi.com/tech/stl/_find.html, STL's _find).
2365
2366 To _find the last occurence of $(D needle) in $(D haystack), call $(D
2367 find(retro(haystack), needle)). See also $(XREF range, retro).
2368
2369 Params:
2370
2371 haystack = The range searched in.
2372
2373 needle = The element searched for.
2374
2375 Constraints:
2376
2377 $(D isInputRange!R && is(typeof(binaryFun!pred(haystack.front, needle)
2378 : bool)))
2379
2380 Returns:
2381
2382 $(D haystack) advanced such that $(D binaryFun!pred(haystack.front,
2383 needle)) is $(D true) (if no such position exists, returns $(D
2384 haystack) after exhaustion).
2385
2386 Example:
2387
2388 ----
2389 assert(find("hello, world", ',') == ", world");
2390 assert(find([1, 2, 3, 5], 4) == []);
2391 assert(find(SList!int(1, 2, 3, 4, 5)[], 4) == SList!int(4, 5)[]);
2392 assert(find!"a > b"([1, 2, 3, 5], 2) == [3, 5]);
2393
2394 auto a = [ 1, 2, 3 ];
2395 assert(find(a, 5).empty);       // not found
2396 assert(!find(a, 2).empty);      // found
2397
2398 // Case-insensitive find of a string
2399 string[] s = [ "Hello", "world", "!" ];
2400 assert(!find!("tolower(a) == b")(s, "hello").empty);
2401 ----
2402  */
2403 R find(alias pred = "a == b", R, E)(R haystack, E needle)
2404 if (isInputRange!R &&
2405         is(typeof(binaryFun!pred(haystack.front, needle)) : bool))
2406 {
2407     for (; !haystack.empty; haystack.popFront())
2408     {
2409         if (binaryFun!pred(haystack.front, needle)) break;
2410     }
2411     return haystack;
2412 }
2413
2414 unittest
2415 {
2416     debug(std_algorithm) scope(success)
2417         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2418     auto lst = SList!int(1, 2, 5, 7, 3);
2419     assert(lst.front == 1);
2420     auto r = find(lst[], 5);
2421     assert(equal(r, SList!int(5, 7, 3)[]));
2422     assert(find([1, 2, 3, 5], 4).empty);
2423 }
2424
2425 /**
2426 Finds a forward range in another. Elements are compared for
2427 equality. Performs $(BIGOH walkLength(haystack) * walkLength(needle))
2428 comparisons in the worst case. Specializations taking advantage of
2429 bidirectional or random access (where present) may accelerate search
2430 depending on the statistics of the two ranges' content.
2431
2432 Params:
2433
2434 haystack = The range searched in.
2435
2436 needle = The range searched for.
2437
2438 Constraints:
2439
2440 $(D isForwardRange!R1 && isForwardRange!R2 &&
2441 is(typeof(binaryFun!pred(haystack.front, needle.front) : bool)))
2442
2443 Returns:
2444
2445 $(D haystack) advanced such that $(D needle) is a prefix of it (if no
2446 such position exists, returns $(D haystack) advanced to termination).
2447
2448 ----
2449 assert(find("hello, world", "World").empty);
2450 assert(find("hello, world", "wo") == "world");
2451 assert(find([1, 2, 3, 4], SList!(2, 3)[]) == [2, 3, 4]);
2452 ----
2453  */
2454 R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
2455 if (isForwardRange!R1 && isForwardRange!R2
2456         && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool)
2457         && !isRandomAccessRange!R1)
2458 {
2459     static if (is(typeof(pred == "a == b")) && pred == "a == b" && isSomeString!R1 && isSomeString!R2
2460             && haystack[0].sizeof == needle[0].sizeof)
2461     {
2462         //return cast(R1) find(representation(haystack), representation(needle));
2463         // Specialization for simple string search
2464         alias Select!(haystack[0].sizeof == 1, ubyte[],
2465                 Select!(haystack[0].sizeof == 2, ushort[], uint[]))
2466             Representation;
2467         // Will use the array specialization
2468         return cast(R1) .find!(pred, Representation, Representation)
2469             (cast(Representation) haystack, cast(Representation) needle);
2470     }
2471     else
2472     {
2473         return simpleMindedFind!pred(haystack, needle);
2474     }
2475 }
2476
2477 unittest
2478 {
2479     debug(std_algorithm) scope(success)
2480         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2481     auto lst = SList!int(1, 2, 5, 7, 3);
2482     static assert(isForwardRange!(int[]));
2483     static assert(isForwardRange!(typeof(lst[])));
2484     auto r = find(lst[], [2, 5]);
2485     assert(equal(r, SList!int(2, 5, 7, 3)[]));
2486 }
2487
2488 // Specialization for searching a random-access range for a
2489 // bidirectional range
2490 R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
2491 if (isRandomAccessRange!R1 && isBidirectionalRange!R2
2492         && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
2493 {
2494     if (needle.empty) return haystack;
2495     const needleLength = walkLength(needle);
2496     if (needleLength > haystack.length)
2497     {
2498         // @@@BUG@@@
2499         //return haystack[$ .. $];
2500         return haystack[haystack.length .. haystack.length];
2501     }
2502     // @@@BUG@@@
2503     // auto needleBack = moveBack(needle);
2504     // Stage 1: find the step
2505     size_t step = 1;
2506     auto needleBack = needle.back;
2507     needle.popBack();
2508     for (auto i = needle.save; !i.empty && !binaryFun!pred(i.back, needleBack);
2509          i.popBack(), ++step)
2510     {
2511     }
2512     // Stage 2: linear find
2513     size_t scout = needleLength - 1;
2514     for (;;)
2515     {
2516         if (scout >= haystack.length)
2517         {
2518             return haystack[haystack.length .. haystack.length];
2519         }
2520         if (!binaryFun!pred(haystack[scout], needleBack))
2521         {
2522             ++scout;
2523             continue;
2524         }
2525         // Found a match with the last element in the needle
2526         auto cand = haystack[scout + 1 - needleLength .. haystack.length];
2527         if (startsWith!pred(cand, needle))
2528         {
2529             // found
2530             return cand;
2531         }
2532         // Continue with the stride
2533         scout += step;
2534     }
2535 }
2536
2537 unittest
2538 {
2539     //scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2540     // @@@BUG@@@ removing static below makes unittest fail
2541     static struct BiRange
2542     {
2543         int[] payload;
2544         @property bool empty() { return payload.empty; }
2545         @property BiRange save() { return this; }
2546         @property ref int front() { return payload[0]; }
2547         @property ref int back() { return payload[$ - 1]; }
2548         void popFront() { return payload.popFront(); }
2549         void popBack() { return payload.popBack(); }
2550     }
2551     //static assert(isBidirectionalRange!BiRange);
2552     auto r = BiRange([1, 2, 3, 10, 11, 4]);
2553     //assert(equal(find(r, [3, 10]), BiRange([3, 10, 11, 4])));
2554     //assert(find("abc", "bc").length == 2);
2555     debug(std_algorithm) scope(success)
2556         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2557     //assert(find!"a == b"("abc", "bc").length == 2);
2558 }
2559
2560 // Leftover specialization: searching a random-access range for a
2561 // non-bidirectional forward range
2562 R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
2563 if (isRandomAccessRange!R1 && isForwardRange!R2 && !isBidirectionalRange!R2
2564         && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
2565 {
2566     static if (!is(ElementType!R1 == ElementType!R2))
2567     {
2568         return simpleMindedFind!pred(haystack, needle);
2569     }
2570     else
2571     {
2572         // Prepare the search with needle's first element
2573         if (needle.empty) return haystack;
2574         haystack = .find!pred(haystack, needle.front);
2575         if (haystack.empty) return haystack;
2576         needle.popFront();
2577         size_t matchLen = 1;
2578         // Loop invariant: haystack[0 .. matchLen] matches everything in
2579         // the initial needle that was popped out of needle.
2580         for (;;)
2581         {
2582             // Extend matchLength as much as possible
2583             for (;;)
2584             {
2585                 if (needle.empty || haystack.empty) return haystack;
2586                 if (!binaryFun!pred(haystack[matchLen], needle.front)) break;
2587                 ++matchLen;
2588                 needle.popFront();
2589             }
2590             auto bestMatch = haystack[0 .. matchLen];
2591             haystack.popFront();
2592             haystack = .find!pred(haystack, bestMatch);
2593         }
2594     }
2595 }
2596
2597 unittest
2598 {
2599     assert(find([ 1, 2, 3 ], SList!int(2, 3)[]) == [ 2, 3 ]);
2600     assert(find([ 1, 2, 1, 2, 3, 3 ], SList!int(2, 3)[]) == [ 2, 3, 3 ]);
2601 }
2602
2603 // Internally used by some find() overloads above. Can't make it
2604 // private due to bugs in the compiler.
2605 /*private*/ R1 simpleMindedFind(alias pred, R1, R2)(R1 haystack, R2 needle)
2606 {
2607     enum estimateNeedleLength = hasLength!R1 && !hasLength!R2;
2608
2609     static if (hasLength!R1)
2610     {
2611         static if (hasLength!R2)
2612             size_t estimatedNeedleLength = 0;
2613         else
2614             immutable size_t estimatedNeedleLength = needle.length;
2615     }
2616
2617     bool haystackTooShort()
2618     {
2619         static if (hasLength!R1)
2620         {
2621             return haystack.length < estimatedNeedleLength;
2622         }
2623         else
2624         {
2625             return haystack.empty;
2626         }
2627     }
2628
2629   searching:
2630     for (;; haystack.popFront())
2631     {
2632         if (haystackTooShort())
2633         {
2634             // Failed search
2635             static if (hasLength!R1)
2636             {
2637                 static if (is(typeof(haystack[haystack.length ..
2638                                                 haystack.length]) : R1))
2639                     return haystack[haystack.length .. haystack.length];
2640                 else
2641                     return R1.init;
2642             }
2643             else
2644             {
2645                 assert(haystack.empty);
2646                 return haystack;
2647             }
2648         }
2649         static if (estimateNeedleLength)
2650             size_t matchLength = 0;
2651         for (auto h = haystack.save, n = needle.save;
2652              !n.empty;
2653              h.popFront(), n.popFront())
2654         {
2655             if (h.empty || !binaryFun!pred(h.front, n.front))
2656             {
2657                 // Failed searching n in h
2658                 static if (estimateNeedleLength)
2659                 {
2660                     if (estimatedNeedleLength < matchLength)
2661                         estimatedNeedleLength = matchLength;
2662                 }
2663                 continue searching;
2664             }
2665             static if (estimateNeedleLength)
2666                 ++matchLength;
2667         }
2668         break;
2669     }
2670     return haystack;
2671 }
2672
2673 /**
2674 Finds two or more $(D needles) into a $(D haystack). The predicate $(D
2675 pred) is used throughout to compare elements. By default, elements are
2676 compared for equality.
2677
2678 Params:
2679
2680 haystack = The target of the search. Must be an $(GLOSSARY input
2681 range). If any of $(D needles) is a range with elements comparable to
2682 elements in $(D haystack), then $(D haystack) must be a $(GLOSSARY
2683 forward range) such that the search can backtrack.
2684
2685 needles = One or more items to search for. Each of $(D needles) must
2686 be either comparable to one element in $(D haystack), or be itself a
2687 $(GLOSSARY forward range) with elements comparable with elements in
2688 $(D haystack).
2689
2690 Returns:
2691
2692 A tuple containing $(D haystack) positioned to match one of the
2693 needles and also the 1-based index of the matching element in $(D
2694 needles) (0 if none of $(D needles) matched, 1 if $(D needles[0])
2695 matched, 2 if $(D needles[1]) matched...).
2696
2697 The relationship between $(D haystack) and $(D needles) simply means
2698 that one can e.g. search for individual $(D int)s or arrays of $(D
2699 int)s in an array of $(D int)s. In addition, if elements are
2700 individually comparable, searches of heterogeneous types are allowed
2701 as well: a $(D double[]) can be searched for an $(D int) or a $(D
2702 short[]), and conversely a $(D long) can be searched for a $(D float)
2703 or a $(D double[]). This makes for efficient searches without the need
2704 to coerce one side of the comparison into the other's side type.
2705
2706 Example:
2707 ----
2708 int[] a = [ 1, 4, 2, 3 ];
2709 assert(find(a, 4) == [ 4, 2, 3 ]);
2710 assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]);
2711 assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2));
2712 // Mixed types allowed if comparable
2713 assert(find(a, 5, [ 1.2, 3.5 ], 2.0, [ 1 ]) == tuple([ 2, 3 ], 3));
2714 ----
2715
2716 The complexity of the search is $(BIGOH haystack.length *
2717 max(needles.length)). (For needles that are individual items, length
2718 is considered to be 1.) The strategy used in searching several
2719 subranges at once maximizes cache usage by moving in $(D haystack) as
2720 few times as possible.
2721  */
2722 Tuple!(Range, size_t) find(alias pred = "a == b", Range, Ranges...)
2723 (Range haystack, Ranges needles)
2724 if (Ranges.length > 1 && allSatisfy!(isForwardRange, Ranges))
2725 {
2726     for (;; haystack.popFront)
2727     {
2728         size_t r = startsWith!pred(haystack, needles);
2729         if (r || haystack.empty)
2730         {
2731             return tuple(haystack, r);
2732         }
2733     }
2734 }
2735
2736 unittest
2737 {
2738     debug(std_algorithm) scope(success)
2739         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2740     auto s1 = "Mary has a little lamb";
2741     //writeln(find(s1, "has a", "has an"));
2742     assert(find(s1, "has a", "has an") == tuple("has a little lamb", 1));
2743     assert(find("abc", "bc").length == 2);
2744 }
2745
2746 unittest
2747 {
2748     debug(std_algorithm) scope(success)
2749         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2750     int[] a = [ 1, 2, 3 ];
2751     assert(find(a, 5).empty);
2752     assert(find(a, 2) == [2, 3]);
2753
2754     foreach (T; TypeTuple!(int, double))
2755     {
2756         auto b = rndstuff!(T)();
2757         if (!b.length) continue;
2758         b[$ / 2] = 200;
2759         b[$ / 4] = 200;
2760         assert(find(b, 200).length == b.length - b.length / 4);
2761     }
2762
2763 // Case-insensitive find of a string
2764     string[] s = [ "Hello", "world", "!" ];
2765     //writeln(find!("toupper(a) == toupper(b)")(s, "hello"));
2766     assert(find!("toupper(a) == toupper(b)")(s, "hello").length == 3);
2767
2768     static bool f(string a, string b) { return toupper(a) == toupper(b); }
2769     assert(find!(f)(s, "hello").length == 3);
2770 }
2771
2772 unittest
2773 {
2774     debug(std_algorithm) scope(success)
2775         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2776     int[] a = [ 1, 2, 3, 2, 6 ];
2777     assert(find(std.range.retro(a), 5).empty);
2778     assert(equal(find(std.range.retro(a), 2), [ 2, 3, 2, 1 ][]));
2779
2780     foreach (T; TypeTuple!(int, double))
2781     {
2782         auto b = rndstuff!(T)();
2783         if (!b.length) continue;
2784         b[$ / 2] = 200;
2785         b[$ / 4] = 200;
2786         assert(find(std.range.retro(b), 200).length ==
2787                 b.length - (b.length - 1) / 2);
2788     }
2789 }
2790
2791 unittest
2792 {
2793     debug(std_algorithm) scope(success)
2794         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2795     int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2796     int[] b = [ 1, 2, 3 ];
2797     assert(find(a, b) == [ 1, 2, 3, 4, 5 ]);
2798     assert(find(b, a).empty);
2799
2800     foreach(DummyType; AllDummyRanges) {
2801         DummyType d;
2802         auto findRes = find(d, 5);
2803         assert(equal(findRes, [5,6,7,8,9,10]));
2804     }
2805 }
2806
2807 /// Ditto
2808 struct BoyerMooreFinder(alias pred, Range)
2809 {
2810 private:
2811     size_t skip[];
2812     sizediff_t[ElementType!(Range)] occ;
2813     Range needle;
2814
2815     sizediff_t occurrence(ElementType!(Range) c)
2816     {
2817         auto p = c in occ;
2818         return p ? *p : -1;
2819     }
2820
2821 /*
2822 This helper function checks whether the last "portion" bytes of
2823 "needle" (which is "nlen" bytes long) exist within the "needle" at
2824 offset "offset" (counted from the end of the string), and whether the
2825 character preceding "offset" is not a match.  Notice that the range
2826 being checked may reach beyond the beginning of the string. Such range
2827 is ignored.
2828  */
2829     static bool needlematch(R)(R needle,
2830                               size_t portion, size_t offset)
2831     {
2832         sizediff_t virtual_begin = needle.length - offset - portion;
2833         sizediff_t ignore = 0;
2834         if (virtual_begin < 0) {
2835             ignore = -virtual_begin;
2836             virtual_begin = 0;
2837         }
2838         if (virtual_begin > 0
2839             && needle[virtual_begin - 1] == needle[$ - portion - 1])
2840             return 0;
2841
2842         immutable delta = portion - ignore;
2843         return equal(needle[needle.length - delta .. needle.length],
2844                 needle[virtual_begin .. virtual_begin + delta]);
2845     }
2846
2847 public:
2848     this(Range needle)
2849     {
2850         if (!needle.length) return;
2851         this.needle = needle;
2852         /* Populate table with the analysis of the needle */
2853         /* But ignoring the last letter */
2854         foreach (i, n ; needle[0 .. $ - 1])
2855         {
2856             this.occ[n] = i;
2857         }
2858         /* Preprocess #2: init skip[] */
2859         /* Note: This step could be made a lot faster.
2860          * A simple implementation is shown here. */
2861         this.skip = new size_t[needle.length];
2862         foreach (a; 0 .. needle.length)
2863         {
2864             size_t value = 0;
2865             while (value < needle.length
2866                    && !needlematch(needle, a, value))
2867             {
2868                 ++value;
2869             }
2870             this.skip[needle.length - a - 1] = value;
2871         }
2872     }
2873
2874     Range beFound(Range haystack)
2875     {
2876         if (!needle.length) return haystack;
2877         if (needle.length > haystack.length) return haystack[$ .. $];
2878         /* Search: */
2879         auto limit = haystack.length - needle.length;
2880         for (size_t hpos = 0; hpos <= limit; )
2881         {
2882             size_t npos = needle.length - 1;
2883             while (pred(needle[npos], haystack[npos+hpos]))
2884             {
2885                 if (npos == 0) return haystack[hpos .. $];
2886                 --npos;
2887             }
2888             hpos += max(skip[npos], npos - occurrence(haystack[npos+hpos]));
2889         }
2890         return haystack[$ .. $];
2891     }
2892
2893     @property size_t length()
2894     {
2895         return needle.length;
2896     }
2897 }
2898
2899 /// Ditto
2900 BoyerMooreFinder!(binaryFun!(pred), Range) boyerMooreFinder
2901 (alias pred = "a == b", Range)
2902 (Range needle) if (isRandomAccessRange!(Range) || isSomeString!Range)
2903 {
2904     return typeof(return)(needle);
2905 }
2906
2907 // Oddly this is not disabled by bug 4759
2908 Range1 find(Range1, alias pred, Range2)(
2909     Range1 haystack, BoyerMooreFinder!(pred, Range2) needle)
2910 {
2911     return needle.beFound(haystack);
2912 }
2913
2914 unittest
2915 {
2916     debug(std_algorithm) scope(success)
2917         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2918     string h = "/homes/aalexand/d/dmd/bin/../lib/libphobos.a(dmain2.o)"
2919         "(.gnu.linkonce.tmain+0x74): In function `main' undefined reference"
2920         " to `_Dmain':";
2921     string[] ns = ["libphobos", "function", " undefined", "`", ":"];
2922     foreach (n ; ns) {
2923         auto p = find(h, boyerMooreFinder(n));
2924         assert(!p.empty);
2925     }
2926
2927     int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
2928     int[] b = [ 1, 2, 3 ];
2929     //writeln(find(a, boyerMooreFinder(b)));
2930     assert(find(a, boyerMooreFinder(b)) == [ 1, 2, 3, 4, 5 ]);
2931     assert(find(b, boyerMooreFinder(a)).empty);
2932 }
2933
2934 /**
2935 Advances the input range $(D haystack) by calling $(D haystack.popFront)
2936 until either $(D pred(haystack.front)), or $(D
2937 haystack.empty). Performs $(BIGOH haystack.length) evaluations of $(D
2938 pred). See also $(WEB sgi.com/tech/stl/find_if.html, STL's find_if).
2939
2940 To find the last element of a bidirectional $(D haystack) satisfying
2941 $(D pred), call $(D find!(pred)(retro(haystack))). See also $(XREF
2942 range, retro).
2943
2944 Example:
2945 ----
2946 auto arr = [ 1, 2, 3, 4, 1 ];
2947 assert(find!("a > 2")(arr) == [ 3, 4, 1 ]);
2948
2949 // with predicate alias
2950 bool pred(int x) { return x + 1 > 1.5; }
2951 assert(find!(pred)(arr) == arr);
2952 ----
2953 */
2954 Range find(alias pred, Range)(Range haystack) if (isInputRange!(Range))
2955 {
2956     alias unaryFun!(pred) predFun;
2957     for (; !haystack.empty && !predFun(haystack.front); haystack.popFront)
2958     {
2959     }
2960     return haystack;
2961 }
2962
2963 unittest
2964 {
2965     //scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done.");
2966     int[] a = [ 1, 2, 3 ];
2967     assert(find!("a > 2")(a) == [3]);
2968     bool pred(int x) { return x + 1 > 1.5; }
2969     assert(find!(pred)(a) == a);
2970 }
2971
2972 // findSkip
2973 /**
2974  * If $(D needle) occurs in $(D haystack), positions $(D haystack)
2975  * right after the first occurrence of $(D needle) and returns $(D
2976  * true). Otherwise, leaves $(D haystack) as is and returns $(D
2977  * false).
2978  *
2979  * Example:
2980 ----
2981 string s = "abcdef";
2982 assert(findSkip("abcdef", "cd") && s == "ef");
2983 s = "abcdef";
2984 assert(!findSkip("abcdef", "cxd") && s == "abcdef");
2985 assert(findSkip("abcdef", "def") && s.empty);
2986 ----
2987  */
2988 bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle)
2989 if (isForwardRange!R1 && isForwardRange!R2
2990         && is(typeof(binaryFun!pred(haystack.front, needle.front))))
2991 {
2992     auto parts = findSplit!pred(haystack, needle);
2993     if (parts[1].empty) return false;
2994     // found
2995     haystack = parts[2];
2996     return true;
2997 }
2998
2999 unittest
3000 {
3001     string s = "abcdef";
3002     assert(findSkip(s, "cd") && s == "ef");
3003     s = "abcdef";
3004     assert(!findSkip(s, "cxd") && s == "abcdef");
3005     s = "abcdef";
3006     assert(findSkip(s, "def") && s.empty);
3007 }
3008
3009 /**
3010 These functions find the first occurrence of $(D needle) in $(D
3011 haystack) and then split $(D haystack) as follows.
3012
3013 $(D findSplit) returns a tuple $(D result) containing $(I three)
3014 ranges. $(D result[0]) is the portion of $(D haystack) before $(D
3015 needle), $(D result[1]) is the portion of $(D haystack) that matches
3016 $(D needle), and $(D result[2]) is the portion of $(D haystack) after
3017 the match.
3018  
3019 $(D findSplitBefore) returns a tuple $(D result) containing two
3020 ranges. $(D result[0]) is the portion of $(D haystack) before $(D
3021 needle), and $(D result[1]) is the balance of $(D haystack) starting
3022 with the match. If $(D needle) was not found, $(D result[0])
3023 comprehends $(D haystack) entirely and $(D result[1]) is empty.
3024
3025 $(D findSplitAfter) returns a tuple $(D result) containing two ranges.
3026 $(D result[0]) is the portion of $(D haystack) up to and including the
3027 match, and $(D result[1]) is the balance of $(D haystack) starting
3028 after the match. If $(D needle) was not found, $(D result[0]) is empty
3029 and $(D result[1]) is $(D haystack).
3030
3031 In all cases, the concatenation of the returned ranges spans the
3032 entire $(D haystack).
3033
3034 If $(D haystack) is a random-access range, all three components of the
3035 tuple have the same type as $(D haystack). Otherwise, $(D haystack)
3036 must be a forward range and the type of $(D result[0]) and $(D
3037 result[1]) is the same as $(XREF range,takeExactly).
3038
3039 Example:
3040 ----
3041 auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3042 auto r = findSplit(a, [9, 1]);
3043 assert(r[0] == a);
3044 assert(r[1].empty);
3045 assert(r[2].empty);
3046 r = findSplit(a, [ 3, 4 ]);
3047 assert(r[0] == a[0 .. 2]);
3048 assert(r[1] == a[2 .. 4]);
3049 assert(r[2] == a[4 .. $]);
3050 auto r1 = findSplitBefore(a, [ 7, 8 ]);
3051 assert(r1[0] == a[0 .. 6]);
3052 assert(r1[1] == a[6 .. $]);
3053 auto r1 = findSplitAfter(a, [ 7, 8 ]);
3054 assert(r1[0] == a);
3055 assert(r1[1].empty);
3056 ----
3057  */
3058 auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3059 if (isForwardRange!R1 && isForwardRange!R2)
3060 {
3061     static if (isSomeString!R1 && isSomeString!R2
3062             || isRandomAccessRange!R1 && hasLength!R2)
3063     {
3064         auto balance = find!pred(haystack, needle);
3065         immutable pos1 = haystack.length - balance.length;
3066         immutable pos2 = balance.empty ? pos1 : pos1 + needle.length;
3067         return tuple(haystack[0 .. pos1],
3068                 haystack[pos1 .. pos2],
3069                 haystack[pos2 .. haystack.length]);
3070     }
3071     else
3072     {
3073         auto original = haystack.save;
3074         auto h = haystack.save;
3075         auto n = needle.save;
3076         size_t pos1, pos2;
3077         while (!n.empty && !h.empty)
3078         {
3079             if (binaryFun!pred(h.front, n.front))
3080             {
3081                 h.popFront();
3082                 n.popFront();
3083                 ++pos2;
3084             }
3085             else
3086             {
3087                 haystack.popFront();
3088                 n = needle.save;
3089                 h = haystack.save;
3090                 pos2 = ++pos1;
3091             }
3092         }
3093         return tuple(takeExactly(original, pos1),
3094                 takeExactly(haystack, pos2 - pos1),
3095                 h);
3096     }
3097 }
3098
3099 /// Ditto
3100 auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3101 if (isForwardRange!R1 && isForwardRange!R2)
3102 {
3103     static if (isSomeString!R1 && isSomeString!R2
3104             || isRandomAccessRange!R1 && hasLength!R2)
3105     {
3106         auto balance = find!pred(haystack, needle);
3107         immutable pos = haystack.length - balance.length;
3108         return tuple(haystack[0 .. pos], haystack[pos .. haystack.length]);
3109     }
3110     else
3111     {
3112         auto original = haystack.save;
3113         auto h = haystack.save;
3114         auto n = needle.save;
3115         size_t pos;
3116         while (!n.empty && !h.empty)
3117         {
3118             if (binaryFun!pred(h.front, n.front))
3119             {
3120                 h.popFront();
3121                 n.popFront();
3122             }
3123             else
3124             {
3125                 haystack.popFront();
3126                 n = needle.save;
3127                 h = haystack.save;
3128                 ++pos;
3129             }
3130         }
3131         return tuple(takeExactly(original, pos), haystack);
3132     }
3133 }
3134
3135 /// Ditto
3136 auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3137 if (isForwardRange!R1 && isForwardRange!R2)
3138 {
3139     static if (isSomeString!R1 && isSomeString!R2
3140             || isRandomAccessRange!R1 && hasLength!R2)
3141     {
3142         auto balance = find!pred(haystack, needle);
3143         immutable pos = balance.empty ? 0 : haystack.length - balance.length + needle.length;
3144         return tuple(haystack[0 .. pos], haystack[pos .. haystack.length]);
3145     }
3146     else
3147     {
3148         auto original = haystack.save;
3149         auto h = haystack.save;
3150         auto n = needle.save;
3151         size_t pos1, pos2;
3152         while (!n.empty)
3153         {
3154             if (h.empty)
3155             {
3156                 // Failed search
3157                 return tuple(takeExactly(original, 0), original);
3158             }
3159             if (binaryFun!pred(h.front, n.front))
3160             {
3161                 h.popFront();
3162                 n.popFront();
3163                 ++pos2;
3164             }
3165             else
3166             {
3167                 haystack.popFront();
3168                 n = needle.save;
3169                 h = haystack.save;
3170                 pos2 = ++pos1;
3171             }
3172         }
3173         return tuple(takeExactly(original, pos2), h);
3174     }
3175 }
3176
3177 unittest
3178 {
3179     auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3180     auto r = findSplit(a, [9, 1]);
3181     assert(r[0] == a);
3182     assert(r[1].empty);
3183     assert(r[2].empty);
3184     r = findSplit(a, [3]);
3185     assert(r[0] == a[0 .. 2]);
3186     assert(r[1] == a[2 .. 3]);
3187     assert(r[2] == a[3 .. $]);
3188
3189     auto r1 = findSplitBefore(a, [9, 1]);
3190     assert(r1[0] == a);
3191     assert(r1[1].empty);
3192     r1 = findSplitBefore(a, [3, 4]);
3193     assert(r1[0] == a[0 .. 2]);
3194     assert(r1[1] == a[2 .. $]);
3195
3196     r1 = findSplitAfter(a, [9, 1]);
3197     assert(r1[0].empty);
3198     assert(r1[1] == a);
3199     r1 = findSplitAfter(a, [3, 4]);
3200     assert(r1[0] == a[0 .. 4]);
3201     assert(r1[1] == a[4 .. $]);
3202 }
3203
3204 unittest
3205 {
3206     auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
3207     auto fwd = filter!"a > 0"(a);
3208     auto r = findSplit(fwd, [9, 1]);
3209     assert(equal(r[0], a));
3210     assert(r[1].empty);
3211     assert(r[2].empty);
3212     r = findSplit(fwd, [3]);
3213     assert(equal(r[0],  a[0 .. 2]));
3214     assert(equal(r[1], a[2 .. 3]));
3215     assert(equal(r[2], a[3 .. $]));
3216    
3217     auto r1 = findSplitBefore(fwd, [9, 1]);
3218     assert(equal(r1[0], a));
3219     assert(r1[1].empty);
3220     r1 = findSplitBefore(fwd, [3, 4]);
3221     assert(equal(r1[0], a[0 .. 2]));
3222     assert(equal(r1[1], a[2 .. $]));
3223
3224     r1 = findSplitAfter(fwd, [9, 1]);
3225     assert(r1[0].empty);
3226     assert(equal(r1[1], a));
3227     r1 = findSplitAfter(fwd, [3, 4]);
3228     assert(equal(r1[0], a[0 .. 4]));
3229     assert(equal(r1[1], a[4 .. $]));
3230 }
3231
3232 /**
3233 If $(D haystack) supports slicing, returns the smallest number $(D n)
3234 such that $(D haystack[n .. $].startsWith!pred(needle)). Oherwise,
3235 returns the smallest $(D n) such that after $(D n) calls to $(D
3236 haystack.popFront), $(D haystack.startsWith!pred(needle)). If no such
3237 number could be found, return $(D -1).
3238  */
3239 sizediff_t countUntil(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3240 if (is(typeof(startsWith!pred(haystack, needle))))
3241 {
3242     static if (isNarrowString!R1)
3243     {
3244         // Narrow strings are handled a bit differently
3245         auto length = haystack.length;
3246         for (; !haystack.empty; haystack.popFront)
3247         {
3248             if (startsWith!pred(haystack, needle))
3249             {
3250                 return length - haystack.length;
3251             }
3252         }
3253     }
3254     else
3255     {
3256         typeof(return) result;
3257         for (; !haystack.empty; ++result, haystack.popFront())
3258         {
3259             if (startsWith!pred(haystack, needle)) return result;
3260         }
3261     }
3262     return -1;
3263 }
3264
3265 /**
3266  * Same as $(D countUntil). This symbol has been scheduled for
3267  * deprecation because it is easily confused with the homonym function
3268  * in $(D std.string).
3269  */
3270 sizediff_t indexOf(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3271 if (is(typeof(startsWith!pred(haystack, needle))))
3272 {
3273     pragma(msg, "std.algorithm.indexOf has been scheduled for deprecation."
3274             " You may want to use std.algorithm.countUntil instead.");
3275     return countUntil!pred(haystack, needle);
3276 }
3277
3278 /**
3279 Interval option specifier for $(D until) (below) and others.
3280  */
3281 enum OpenRight
3282 {
3283     no, /// Interval is closed to the right (last element included)
3284     yes /// Interval is open to the right (last element is not included)
3285 }
3286
3287 /**
3288 Lazily iterates $(D range) until value $(D sentinel) is found, at
3289 which point it stops.
3290
3291 Example:
3292 ----
3293 int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
3294 assert(equal(a.until(7), [1, 2, 4][]));
3295 assert(equal(a.until(7, OpenRight.no), [1, 2, 4, 7][]));
3296 ----
3297  */
3298 struct Until(alias pred, Range, Sentinel) if (isInputRange!Range)
3299 {
3300     private Range _input;
3301     static if (!is(Sentinel == void))
3302         private Sentinel _sentinel;
3303     // mixin(bitfields!(
3304     //             OpenRight, "_openRight", 1,
3305     //             bool,  "_done", 1,
3306     //             uint, "", 6));
3307     //             OpenRight, "_openRight", 1,
3308     //             bool,  "_done", 1,
3309     OpenRight _openRight;
3310     bool _done;
3311
3312     static if (!is(Sentinel == void))
3313         this(Range input, Sentinel sentinel,
3314                 OpenRight openRight = OpenRight.yes)
3315         {
3316             _input = input;
3317             _sentinel = sentinel;
3318             _openRight = openRight;
3319             _done = _input.empty || openRight && predSatisfied();
3320         }
3321     else
3322         this(Range input, OpenRight openRight = OpenRight.yes)
3323         {
3324             _input = input;
3325             _openRight = openRight;
3326             _done = _input.empty || openRight && predSatisfied();
3327         }
3328
3329     @property bool empty()
3330     {
3331         return _done;
3332     }
3333
3334     @property ElementType!Range front()
3335     {
3336         assert(!empty);
3337         return _input.front;
3338     }
3339
3340     bool predSatisfied()
3341     {
3342         static if (is(Sentinel == void))
3343             return unaryFun!pred(_input.front);
3344         else
3345             return startsWith!pred(_input, _sentinel);
3346     }
3347
3348     void popFront()
3349     {
3350         assert(!empty);
3351         if (!_openRight)
3352         {
3353             if (predSatisfied())
3354             {
3355                 _done = true;
3356                 return;
3357             }
3358             _input.popFront;
3359             _done = _input.empty;
3360         }
3361         else
3362         {
3363             _input.popFront;
3364             _done = _input.empty || predSatisfied;
3365         }
3366     }
3367
3368     static if (!is(Sentinel == void))
3369         @property Until save()
3370         {
3371             Until result;
3372
3373             result._input     = _input.save;
3374             result._sentinel  = _sentinel;
3375             result._openRight = _openRight;
3376             result._done      = _done;
3377
3378             return result;
3379         }
3380     else
3381         @property Until save()
3382         {
3383             Until result;
3384
3385             result._input     = _input.save;
3386             result._openRight = _openRight;
3387             result._done      = _done;
3388
3389             return result;
3390         }
3391 }
3392
3393 /// Ditto
3394 Until!(pred, Range, Sentinel)
3395 until(alias pred = "a == b", Range, Sentinel)
3396 (Range range, Sentinel sentinel, OpenRight openRight = OpenRight.yes)
3397 if (!is(Sentinel == OpenRight))
3398 {
3399     return typeof(return)(range, sentinel, openRight);
3400 }
3401
3402 /// Ditto
3403 Until!(pred, Range, void)
3404 until(alias pred, Range)
3405 (Range range, OpenRight openRight = OpenRight.yes)
3406 {
3407     return typeof(return)(range, openRight);
3408 }
3409
3410 unittest
3411 {
3412     //scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3413     int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
3414
3415     static assert(isForwardRange!(typeof(a.until(7))));
3416     static assert(isForwardRange!(typeof(until!"a == 2"(a, OpenRight.no))));
3417
3418     assert(equal(a.until(7), [1, 2, 4][]));
3419     assert(equal(a.until([7, 2]), [1, 2, 4, 7][]));
3420     assert(equal(a.until(7, OpenRight.no), [1, 2, 4, 7][]));
3421     assert(equal(until!"a == 2"(a, OpenRight.no), [1, 2][]));
3422 }
3423
3424 /**
3425 If the range $(D doesThisStart) starts with $(I any) of the $(D
3426 withOneOfThese) ranges or elements, returns 1 if it starts with $(D
3427 withOneOfThese[0]), 2 if it starts with $(D withOneOfThese[1]), and so
3428 on. If no match, returns 0.
3429
3430 Example:
3431 ----
3432 assert(startsWith("abc", ""));
3433 assert(startsWith("abc", "a"));
3434 assert(!startsWith("abc", "b"));
3435 assert(startsWith("abc", 'a', "b") == 1);
3436 assert(startsWith("abc", "b", "a") == 2);
3437 assert(startsWith("abc", "a", "a") == 1);
3438 assert(startsWith("abc", "x", "a", "b") == 2);
3439 assert(startsWith("abc", "x", "aa", "ab") == 3);
3440 assert(startsWith("abc", "x", "aaa", "sab") == 0);
3441 assert(startsWith("abc", "x", "aaa", "a", "sab") == 3);
3442 ----
3443  */
3444 uint startsWith(alias pred = "a == b", Range, Ranges...)
3445 (Range doesThisStart, Ranges withOneOfThese)
3446 if (Ranges.length > 1 && isInputRange!Range
3447         && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[0]))
3448                 : bool)
3449         && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[1 .. $]))
3450                 : uint))
3451 {
3452     alias doesThisStart lhs;
3453     alias withOneOfThese rhs;
3454
3455     // Make one pass looking for empty ranges
3456     foreach (i, Unused; Ranges)
3457     {
3458         // Empty range matches everything
3459         static if (!is(typeof(binaryFun!pred(lhs.front, rhs[i])) : bool))
3460         {
3461             if (rhs[i].empty) return i + 1;
3462         }
3463     }
3464
3465     for (; !lhs.empty; lhs.popFront())
3466     {
3467         foreach (i, Unused; Ranges)
3468         {
3469             static if (is(typeof(binaryFun!pred(lhs.front, rhs[i])) : bool))
3470             {
3471                 // Single-element
3472                 if (binaryFun!pred(lhs.front, rhs[i]))
3473                 {
3474                     // found, but continue to account for one-element
3475                     // range matches (consider startsWith("ab", "a",
3476                     // 'a') should return 1, not 2).
3477                     continue;
3478                 }
3479             }
3480             else
3481             {
3482                 if (binaryFun!pred(lhs.front, rhs[i].front))
3483                 {
3484                     continue;
3485                 }
3486             }
3487             // This code executed on failure to match
3488             // Out with this guy, check for the others
3489             uint result = startsWith!pred(lhs, rhs[0 .. i], rhs[i + 1 .. $]);
3490             if (result > i) ++result;
3491             return result;
3492         }
3493
3494         // If execution reaches this point, then the front matches for all
3495         // rhs ranges. What we need to do now is to lop off the front of
3496         // all ranges involved and recurse.
3497         foreach (i, Unused; Ranges)
3498         {
3499             static if (is(typeof(binaryFun!pred(lhs.front, rhs[i])) : bool))
3500             {
3501                 // Test has passed in the previous loop
3502                 return i + 1;
3503             }
3504             else
3505             {
3506                 rhs[i].popFront();
3507                 if (rhs[i].empty) return i + 1;
3508             }
3509         }
3510     }
3511     return 0;
3512 }
3513
3514
3515 /// Ditto
3516 bool startsWith(alias pred = "a == b", R1, R2)
3517 (R1 doesThisStart, R2 withThis)
3518 if (isInputRange!R1 && isInputRange!R2
3519         && is(typeof(binaryFun!pred(doesThisStart.front, withThis.front))
3520                 : bool))
3521 {
3522     // Special  case for two arrays
3523     static if (isArray!R1 && isArray!R2)
3524     {
3525         alias doesThisStart haystack;
3526         alias withThis needle;
3527         //writeln("Matching: ", haystack, " with ", needle);
3528         if (haystack.length < needle.length) return 0;
3529         foreach (j; 0 .. needle.length)
3530         {
3531             if (!binaryFun!pred(needle[j], haystack[j]))
3532                 // not found
3533                 return false;
3534         }
3535         // found!
3536         return true;
3537     }
3538     else
3539     {
3540         static if (hasLength!R1 && hasLength!R2)
3541         {
3542             if (doesThisStart.length < withThis.length) return false;
3543         }
3544         if (withThis.empty) return true;
3545         for (; !doesThisStart.empty; doesThisStart.popFront())
3546         {
3547             if (!binaryFun!pred(doesThisStart.front, withThis.front))
3548                 break;
3549             withThis.popFront();
3550             if (withThis.empty) return true;
3551         }
3552         return false;
3553     }
3554 }
3555
3556 /// Ditto
3557 bool startsWith(alias pred = "a == b", R, E)
3558 (R doesThisStart, E withThis)
3559 if (isInputRange!R && is(typeof(binaryFun!pred(doesThisStart.front, withThis))
3560                 : bool))
3561 {
3562     return doesThisStart.empty
3563         ? false
3564         : binaryFun!pred(doesThisStart.front, withThis);
3565 }
3566
3567 unittest
3568 {
3569     debug(std_algorithm) scope(success)
3570         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3571     bool x = startsWith("ab", "a");
3572     assert(startsWith("abc", ""));
3573     assert(startsWith("abc", "a"));
3574     assert(!startsWith("abc", "b"));
3575     assert(!startsWith("abc", "b", "bc", "abcd", "xyz"));
3576     assert(startsWith("abc", "a", "b") == 1);
3577     assert(startsWith("abc", "b", "a") == 2);
3578     assert(startsWith("abc", "a", 'a') == 1);
3579     assert(startsWith("abc", 'a', "a") == 1);
3580     assert(startsWith("abc", "x", "a", "b") == 2);
3581     assert(startsWith("abc", "x", "aa", "ab") == 3);
3582     assert(startsWith("abc", "x", "aaa", "sab") == 0);
3583     assert(startsWith("abc", 'a'));
3584     assert(!startsWith("abc", "sab"));
3585     assert(startsWith("abc", 'x', "aaa", 'a', "sab") == 3);
3586 }
3587
3588 unittest
3589 {
3590     debug(std_algorithm) scope(success)
3591         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3592     assert(!startsWith("abc", 'x', 'n', 'b'));
3593     assert(startsWith("abc", 'x', 'n', 'a') == 3);
3594 }
3595
3596 /**
3597 If $(D startsWith(r1, r2)), consume the corresponding elements off $(D
3598 r1) and return $(D true). Otherwise, leave $(D r1) unchanged and
3599 return $(D false).
3600  */
3601 bool skipOver(alias pred = "a == b", R1, R2)(ref R1 r1, R2 r2)
3602 if (is(typeof(binaryFun!pred(r1.front, r2.front))))
3603 {
3604     auto r = r1.save;
3605     while (!r2.empty && !r.empty && binaryFun!pred(r.front, r2.front))
3606     {
3607         r.popFront();
3608         r2.popFront();
3609     }
3610     return r2.empty ? (r1 = r, true) : false;
3611 }
3612
3613 unittest
3614 {
3615     //scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3616     auto s1 = "Hello world";
3617     assert(!skipOver(s1, "Ha"));
3618     assert(s1 == "Hello world");
3619     assert(skipOver(s1, "Hell") && s1 == "o world");
3620 }
3621
3622 /**
3623 Checks whether a range starts with an element, and if so, consume that
3624 element off $(D r) and return $(D true). Otherwise, leave $(D r)
3625 unchanged and return $(D false).
3626  */
3627 bool skipOver(alias pred = "a == b", R, E)(ref R r, E e)
3628 if (is(typeof(binaryFun!pred(r.front, e))))
3629 {
3630     return binaryFun!pred(r.front, e)
3631         ? (r.popFront(), true)
3632         : false;
3633 }
3634
3635 unittest {
3636     auto s1 = "Hello world";
3637     assert(!skipOver(s1, "Ha"));
3638     assert(s1 == "Hello world");
3639     assert(skipOver(s1, "Hell") && s1 == "o world");
3640 }
3641
3642 /* (Not yet documented.)
3643 Consume all elements from $(D r) that are equal to one of the elements
3644 $(D es).
3645  */
3646 void skipAll(alias pred = "a == b", R, Es...)(ref R r, Es es)
3647 //if (is(typeof(binaryFun!pred(r1.front, es[0]))))
3648 {
3649   loop:
3650     for (; !r.empty; r.popFront())
3651     {
3652         foreach (i, E; Es)
3653         {
3654             if (binaryFun!pred(r.front, es[i]))
3655             {
3656                 continue loop;
3657             }
3658         }
3659         break;
3660     }
3661 }
3662
3663 unittest
3664 {
3665     //scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3666     auto s1 = "Hello world";
3667     skipAll(s1, 'H', 'e');
3668     assert(s1 == "llo world");
3669 }
3670
3671 /**
3672 The reciprocal of $(D startsWith).
3673
3674 Example:
3675 ----
3676 assert(endsWith("abc", ""));
3677 assert(!endsWith("abc", "b"));
3678 assert(endsWith("abc", "a", 'c') == 2);
3679 assert(endsWith("abc", "c", "a") == 1);
3680 assert(endsWith("abc", "c", "c") == 1);
3681 assert(endsWith("abc", "x", "c", "b") == 2);
3682 assert(endsWith("abc", "x", "aa", "bc") == 3);
3683 assert(endsWith("abc", "x", "aaa", "sab") == 0);
3684 assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);
3685 ----
3686  */
3687 uint
3688 endsWith(alias pred = "a == b", Range, Ranges...)
3689 (Range doesThisEnd, Ranges withOneOfThese)
3690 if (isInputRange!(Range) && Ranges.length > 0
3691         && is(typeof(binaryFun!pred(doesThisEnd.back, withOneOfThese[0].back))))
3692 {
3693     alias doesThisEnd lhs;
3694     alias withOneOfThese rhs;
3695     // Special  case for two arrays
3696     static if (Ranges.length == 1 && isArray!Range && isArray!(Ranges[0])
3697             && is(typeof(binaryFun!(pred)(lhs[0], rhs[0][0]))))
3698     {
3699         if (lhs.length < rhs[0].length) return 0;
3700         auto k = lhs.length - rhs[0].length;
3701         foreach (j; 0 .. rhs[0].length)
3702         {
3703             if (!binaryFun!(pred)(rhs[0][j], lhs[j + k]))
3704                 // not found
3705                 return 0u;
3706         }
3707         // found!
3708         return 1u;
3709     }
3710     else
3711     {
3712         // Make one pass looking for empty ranges
3713         foreach (i, Unused; Ranges)
3714         {
3715             // Empty range matches everything
3716             if (rhs[i].empty) return i + 1;
3717         }
3718         bool mismatch[Ranges.length];
3719         for (; !lhs.empty; lhs.popBack)
3720         {
3721             foreach (i, Unused; Ranges)
3722             {
3723                 if (mismatch[i]) continue;
3724                 if (binaryFun!pred(lhs.back, rhs[i].back))
3725                 {
3726                     // Stay in the game
3727                     rhs[i].popBack();
3728                     // Done with success if exhausted
3729                     if (rhs[i].empty) return i + 1;
3730                 }
3731                 else
3732                 {
3733                     // Out
3734                     mismatch[i] = true;
3735                 }
3736             }
3737         }
3738         return 0;
3739     }
3740 }
3741
3742 unittest
3743 {
3744     debug(std_algorithm) scope(success)
3745         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3746     assert(endsWith("abc", ""));
3747     assert(!endsWith("abc", "a"));
3748     assert(!endsWith("abc", 'a'));
3749     assert(!endsWith("abc", "b"));
3750     assert(endsWith("abc", "a", "c") == 2);
3751     assert(endsWith("abc", 'a', 'c') == 2);
3752     assert(endsWith("abc", "c", "a") == 1);
3753     assert(endsWith("abc", "c", "c") == 1);
3754     assert(endsWith("abc", "x", "c", "b") == 2);
3755     assert(endsWith("abc", "x", "aa", "bc") == 3);
3756     assert(endsWith("abc", "x", "aaa", "sab") == 0);
3757     assert(endsWith("abc", "x", "aaa", "c", "sab") == 3);
3758     // string a = "abc";
3759     // immutable(char[1]) b = "c";
3760     // assert(wyda(a, b));
3761 }
3762
3763 /**
3764 Checks whether $(D doesThisEnd) starts with one of the individual
3765 elements $(D withOneOfThese) according to $(D pred).
3766
3767 Example:
3768 ----
3769 assert(endsWith("abc", 'x', 'c', 'a') == 2);
3770 ----
3771  */
3772 uint endsWith(alias pred = "a == b", Range, Elements...)
3773 (Range doesThisEnd, Elements withOneOfThese)
3774 if (isInputRange!Range && Elements.length > 0
3775         && is(typeof(binaryFun!pred(doesThisEnd.front, withOneOfThese[0]))))
3776 {
3777     if (doesThisEnd.empty) return 0;
3778     auto back = doesThisEnd.back;
3779     foreach (i, Unused; Elements)
3780     {
3781         if (binaryFun!pred(back, withOneOfThese[i])) return i + 1;
3782     }
3783     return 0;
3784 }
3785
3786 unittest
3787 {
3788     debug(std_algorithm) scope(success)
3789         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3790     assert(!startsWith("abc", 'x', 'n', 'b'));
3791     assert(startsWith("abc", 'x', 'n', 'a') == 3);
3792 }
3793
3794 // findAdjacent
3795 /**
3796 Advances $(D r) until it finds the first two adjacent elements $(D a),
3797 $(D b) that satisfy $(D pred(a, b)). Performs $(BIGOH r.length)
3798 evaluations of $(D pred). See also $(WEB
3799 sgi.com/tech/stl/adjacent_find.html, STL's adjacent_find).
3800
3801 Example:
3802 ----
3803 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
3804 auto r = findAdjacent(a);
3805 assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]);
3806 p = findAdjacent!("a < b")(a);
3807 assert(p == [ 7, 8, 9 ]);
3808 ----
3809 */
3810 Range findAdjacent(alias pred = "a == b", Range)(Range r)
3811     if (isForwardRange!(Range))
3812 {
3813     auto ahead = r;
3814     if (!ahead.empty)
3815     {
3816         for (ahead.popFront; !ahead.empty; r.popFront, ahead.popFront)
3817         {
3818             if (binaryFun!(pred)(r.front, ahead.front)) return r;
3819         }
3820     }
3821     return ahead;
3822 }
3823
3824 unittest
3825 {
3826     //scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3827     int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
3828     auto p = findAdjacent(a);
3829     assert(p == [10, 10, 9, 8, 8, 7, 8, 9 ]);
3830     p = findAdjacent!("a < b")(a);
3831     assert(p == [7, 8, 9]);
3832     // empty
3833     a = [];
3834     p = findAdjacent(a);
3835     assert(p.empty);
3836     // not found
3837     a = [ 1, 2, 3, 4, 5 ];
3838     p = findAdjacent(a);
3839     assert(p.empty);
3840     p = findAdjacent!"a > b"(a);
3841     assert(p.empty);
3842 }
3843
3844 // findAmong
3845 /**
3846 Advances $(D seq) by calling $(D seq.popFront) until either $(D
3847 find!(pred)(choices, seq.front)) is $(D true), or $(D seq) becomes
3848 empty. Performs $(BIGOH seq.length * choices.length) evaluations of
3849 $(D pred). See also $(WEB sgi.com/tech/stl/find_first_of.html, STL's
3850 find_first_of).
3851
3852 Example:
3853 ----
3854 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
3855 int[] b = [ 3, 1, 2 ];
3856 assert(findAmong(a, b) == a[2 .. $]);
3857 ----
3858 */
3859 Range1 findAmong(alias pred = "a == b", Range1, Range2)(
3860     Range1 seq, Range2 choices)
3861     if (isInputRange!Range1 && isForwardRange!Range2)
3862 {
3863     for (; !seq.empty && find!pred(choices, seq.front).empty; seq.popFront)
3864     {
3865     }
3866     return seq;
3867 }
3868
3869 unittest
3870 {
3871     //scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3872     int[] a = [ -1, 0, 2, 1, 2, 3, 4, 5 ];
3873     int[] b = [ 1, 2, 3 ];
3874     assert(findAmong(a, b) == [2, 1, 2, 3, 4, 5 ]);
3875     assert(findAmong(b, [ 4, 6, 7 ][]).empty);
3876     assert(findAmong!("a==b")(a, b).length == a.length - 2);
3877     assert(findAmong!("a==b")(b, [ 4, 6, 7 ][]).empty);
3878 }
3879
3880 // count
3881 /**
3882 The first version counts the number of elements $(D x) in $(D r) for
3883 which $(D pred(x, value)) is $(D true). $(D pred) defaults to
3884 equality. Performs $(BIGOH r.length) evaluations of $(D pred).
3885
3886 The second version returns the number of times $(D needle) occurs in
3887 $(D haystack). Throws an exception if $(D needle.empty), as the _count
3888 of the empty range in any range would be infinite. Overlapped counts
3889 are not considered, for example $(D count("aaa", "aa")) is $(D 1), not
3890 $(D 2).
3891
3892 The third version counts the elements for which $(D pred(x)) is $(D
3893 true). Performs $(BIGOH r.length) evaluations of $(D pred).
3894
3895 Example:
3896 ----
3897 // count elements in range
3898 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
3899 assert(count(a, 2) == 3);
3900 assert(count!("a > b")(a, 2) == 5);
3901 // count range in range
3902 assert(count("abcadfabf", "ab") == 2);
3903 assert(count("ababab", "abab") == 1);
3904 assert(count("ababab", "abx") == 0);
3905 // count predicate in range
3906 assert(count!("a > 1")(a) == 8);
3907 ----
3908 */
3909 size_t count(alias pred = "a == b", Range, E)(Range r, E value)
3910 if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, value)) == bool))
3911 {
3912     bool pred2(ElementType!(Range) a) { return binaryFun!pred(a, value); }
3913     return count!(pred2)(r);
3914 }
3915
3916 unittest
3917 {
3918     debug(std_algorithm) scope(success)
3919         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3920     int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
3921     assert(count(a, 2) == 3, text(count(a, 2)));
3922     assert(count!("a > b")(a, 2) == 5, text(count!("a > b")(a, 2)));
3923
3924     // check strings
3925     assert(count("日本語")  == 3);
3926     assert(count("日本語"w) == 3);
3927     assert(count("日本語"d) == 3);
3928
3929     assert(count!("a == '日'")("日本語")  == 1);
3930     assert(count!("a == '本'")("日本語"w) == 1);
3931     assert(count!("a == '語'")("日本語"d) == 1);
3932 }
3933
3934 unittest
3935 {
3936     debug(std_algorithm) printf("algorithm.count.unittest\n");
3937     string s = "This is a fofofof list";
3938     string sub = "fof";
3939     assert(count(s, sub) == 2);
3940 }
3941
3942 /// Ditto
3943 size_t count(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
3944 if (isInputRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack, needle)) == bool))
3945 {
3946     enforce(!needle.empty, "Cannot count occurrences of an empty range");
3947     size_t result;
3948     for (; findSkip!pred(haystack, needle); ++result)
3949     {
3950     }
3951     return result;
3952 }
3953
3954 unittest
3955 {
3956     assert(count("abcadfabf", "ab") == 2);
3957     assert(count("ababab", "abab") == 1);
3958     assert(count("ababab", "abx") == 0);
3959 }
3960
3961 /// Ditto
3962 size_t count(alias pred = "true", Range)(Range r) if (isInputRange!(Range))
3963 {
3964     size_t result;
3965     for (; !r.empty; r.popFront())
3966     {
3967         if (unaryFun!pred(r.front)) ++result;
3968     }
3969     return result;
3970 }
3971
3972 unittest
3973 {
3974     debug(std_algorithm) scope(success)
3975         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
3976     int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
3977     assert(count!("a == 3")(a) == 2);
3978 }
3979
3980 // balancedParens
3981 /**
3982 Checks whether $(D r) has "balanced parentheses", i.e. all instances
3983 of $(D lPar) are closed by corresponding instances of $(D rPar). The
3984 parameter $(D maxNestingLevel) controls the nesting level allowed. The
3985 most common uses are the default or $(D 0). In the latter case, no
3986 nesting is allowed.
3987
3988 Example:
3989 ----
3990 auto s = "1 + (2 * (3 + 1 / 2)";
3991 assert(!balancedParens(s, '(', ')'));
3992 s = "1 + (2 * (3 + 1) / 2)";
3993 assert(balancedParens(s, '(', ')'));
3994 s = "1 + (2 * (3 + 1) / 2)";
3995 assert(!balancedParens(s, '(', ')', 1));
3996 s = "1 + (2 * 3 + 1) / (2 - 5)";
3997 assert(balancedParens(s, '(', ')', 1));
3998 ----
3999 */
4000
4001 bool balancedParens(Range, E)(Range r, E lPar, E rPar,
4002         size_t maxNestingLevel = size_t.max)
4003 if (isInputRange!(Range) && is(typeof(r.front == lPar)))
4004 {
4005     size_t count;
4006     for (; !r.empty; r.popFront())
4007     {
4008         if (r.front == lPar)
4009         {
4010             if (count > maxNestingLevel) return false;
4011             ++count;
4012         }
4013         else if (r.front == rPar)
4014         {
4015             if (!count) return false;
4016             --count;
4017         }
4018     }
4019     return count == 0;
4020 }
4021
4022 unittest
4023 {
4024     auto s = "1 + (2 * (3 + 1 / 2)";
4025     assert(!balancedParens(s, '(', ')'));
4026     s = "1 + (2 * (3 + 1) / 2)";
4027     assert(balancedParens(s, '(', ')'));
4028     s = "1 + (2 * (3 + 1) / 2)";
4029     assert(!balancedParens(s, '(', ')', 0));
4030     s = "1 + (2 * 3 + 1) / (2 - 5)";
4031     assert(balancedParens(s, '(', ')', 0));
4032 }
4033
4034 // equal
4035 /**
4036 Returns $(D true) if and only if the two ranges compare equal element
4037 for element, according to binary predicate $(D pred). The ranges may
4038 have different element types, as long as $(D pred(a, b)) evaluates to
4039 $(D bool) for $(D a) in $(D r1) and $(D b) in $(D r2). Performs
4040 $(BIGOH min(r1.length, r2.length)) evaluations of $(D pred). See also
4041 $(WEB sgi.com/tech/stl/_equal.html, STL's equal).
4042
4043 Example:
4044 ----
4045 int[] a = [ 1, 2, 4, 3 ];
4046 assert(!equal(a, a[1..$]));
4047 assert(equal(a, a));
4048
4049 // different types
4050 double[] b = [ 1., 2, 4, 3];
4051 assert(!equal(a, b[1..$]));
4052 assert(equal(a, b));
4053
4054 // predicated: ensure that two vectors are approximately equal
4055 double[] c = [ 1.005, 2, 4, 3];
4056 assert(equal!(approxEqual)(b, c));
4057 ----
4058 */
4059 bool equal(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2)
4060 if (isInputRange!(Range1) && isInputRange!(Range2)
4061         && is(typeof(binaryFun!pred(r1.front, r2.front))))
4062 {
4063     foreach (e1; r1)
4064     {
4065         if (r2.empty) return false;
4066         if (!binaryFun!(pred)(e1, r2.front)) return false;
4067         r2.popFront;
4068     }
4069     return r2.empty;
4070 }
4071
4072 unittest
4073 {
4074     debug(std_algorithm) scope(success)
4075         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4076     int[] a = [ 1, 2, 4, 3];
4077     assert(!equal(a, a[1..$]));
4078     assert(equal(a, a));
4079     // test with different types
4080     double[] b = [ 1., 2, 4, 3];
4081     assert(!equal(a, b[1..$]));
4082     assert(equal(a, b));
4083
4084     // predicated
4085     double[] c = [ 1.005, 2, 4, 3];
4086     assert(equal!(approxEqual)(b, c));
4087 }
4088
4089 // cmp
4090 /**********************************
4091 Performs three-way lexicographical comparison on two input ranges
4092 according to predicate $(D pred). Iterating $(D r1) and $(D r2) in
4093 lockstep, $(D cmp) compares each element $(D e1) of $(D r1) with the
4094 corresponding element $(D e2) in $(D r2). If $(D binaryFun!pred(e1,
4095 e2)), $(D cmp) returns a negative value. If $(D binaryFun!pred(e2,
4096 e1)), $(D cmp) returns a positive value. If one of the ranges has been
4097 finished, $(D cmp) returns a negative value if $(D r1) has fewer
4098 elements than $(D r2), a positive value if $(D r1) has more elements
4099 than $(D r2), and $(D 0) if the ranges have the same number of
4100 elements.
4101
4102 If the ranges are strings, $(D cmp) performs UTF decoding
4103 appropriately and compares the ranges one code point at a time.
4104 */
4105
4106 int cmp(alias pred = "a < b", R1, R2)(R1 r1, R2 r2)
4107 if (isInputRange!R1 && isInputRange!R2 && !(isSomeString!R1 && isSomeString!R2))
4108 {
4109     for (;; r1.popFront(), r2.popFront())
4110     {
4111         if (r1.empty) return -r2.empty;
4112         if (r2.empty) return r1.empty;
4113         auto a = r1.front, b = r2.front;
4114         if (binaryFun!pred(a, b)) return -1;
4115         if (binaryFun!pred(b, a)) return 1;
4116     }
4117 }
4118
4119 // Specialization for strings (for speed purposes)
4120 int cmp(alias pred = "a < b", R1, R2)(R1 r1, R2 r2) if (isSomeString!R1 && isSomeString!R2)
4121 {
4122     enum isLessThan = is(pred : string) && pred == "a < b";
4123     // For speed only
4124     static int threeWay(size_t a, size_t b)
4125     {
4126         static if (size_t.sizeof == int.sizeof && isLessThan)
4127             return a - b;
4128         else
4129             return binaryFun!pred(b, a) ? 1 : binaryFun!pred(a, b) ? -1 : 0;
4130     }
4131     // For speed only
4132     // @@@BUG@@@ overloading should be allowed for nested functions
4133     static int threeWayInt(int a, int b)
4134     {
4135         static if (isLessThan)
4136             return a - b;
4137         else
4138             return binaryFun!pred(b, a) ? 1 : binaryFun!pred(a, b) ? -1 : 0;
4139     }
4140    
4141     static if (typeof(r1[0]).sizeof == typeof(r2[0]).sizeof && isLessThan)
4142     {
4143         static if (typeof(r1[0]).sizeof == 1)
4144         {
4145             immutable len = min(r1.length, r2.length);
4146             immutable result = std.c.string.memcmp(r1.ptr, r2.ptr, len);
4147             if (result) return result;
4148         }
4149         else
4150         {
4151             auto p1 = r1.ptr, p2 = r2.ptr,
4152                 pEnd = p1 + min(r1.length, r2.length);
4153             for (; p1 != pEnd; ++p1, ++p2)
4154             {
4155                 if (*p1 != *p2) return threeWayInt(cast(int) *p1, cast(int) *p2);
4156             }
4157         }
4158         return threeWay(r1.length, r2.length);
4159     }
4160     else
4161     {
4162         for (size_t i1, i2;;)
4163         {
4164             if (i1 == r1.length) return threeWay(i2, r2.length);
4165             if (i2 == r2.length) return threeWay(r1.length, i1);
4166             immutable c1 = std.utf.decode(r1, i1),
4167                 c2 = std.utf.decode(r2, i2);
4168             if (c1 != c2) return threeWayInt(cast(int) c1, cast(int) c2);
4169         }
4170     }
4171 }
4172
4173 unittest
4174 {
4175     int result;
4176
4177     debug(string) printf("string.cmp.unittest\n");
4178     result = cmp("abc", "abc");
4179     assert(result == 0);
4180     //    result = cmp(null, null);
4181     //    assert(result == 0);
4182     result = cmp("", "");
4183     assert(result == 0);
4184     result = cmp("abc", "abcd");
4185     assert(result < 0);
4186     result = cmp("abcd", "abc");
4187     assert(result > 0);
4188     result = cmp("abc"d, "abd");
4189     assert(result < 0);
4190     result = cmp("bbc", "abc"w);
4191     assert(result > 0);
4192     result = cmp("aaa", "aaaa"d);
4193     assert(result < 0);
4194     result = cmp("aaaa", "aaa"d);
4195     assert(result > 0);
4196     result = cmp("aaa", "aaa"d);
4197     assert(result == 0);
4198 }
4199
4200 // MinType
4201 template MinType(T...)
4202 {
4203     static assert(T.length >= 2);
4204     static if (T.length == 2)
4205     {
4206         static if (!is(typeof(T[0].min)))
4207             alias CommonType!(T[0 .. 2]) MinType;
4208         else static if (mostNegative!(T[1]) < mostNegative!(T[0]))
4209             alias T[1] MinType;
4210         else static if (mostNegative!(T[1]) > mostNegative!(T[0]))
4211             alias T[0] MinType;
4212         else static if (T[1].max < T[0].max)
4213             alias T[1] MinType;
4214         else
4215             alias T[0] MinType;
4216     }
4217     else
4218     {
4219         alias MinType!(MinType!(T[0 .. 2]), T[2 .. $]) MinType;
4220     }
4221 }
4222
4223 // min
4224 /**
4225 Returns the minimum of the passed-in values. The type of the result is
4226 computed by using $(XREF traits, CommonType).
4227 */
4228 MinType!(T1, T2, T) min(T1, T2, T...)(T1 a, T2 b, T xs)
4229 {
4230     static if (T.length == 0)
4231     {
4232         static if (isIntegral!(T1) && isIntegral!(T2)
4233                    && (mostNegative!(T1) < 0) != (mostNegative!(T2) < 0))
4234             static if (mostNegative!(T1) < 0)
4235                 immutable chooseB = b < a && a > 0;
4236             else
4237                 immutable chooseB = b < a || b < 0;
4238         else
4239                 immutable chooseB = b < a;
4240         return cast(typeof(return)) (chooseB ? b : a);
4241     }
4242     else
4243     {
4244         return min(min(a, b), xs);
4245     }
4246 }
4247
4248 unittest
4249 {
4250     debug(std_algorithm) scope(success)
4251         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4252     int a = 5;
4253     short b = 6;
4254     double c = 2;
4255     auto d = min(a, b);
4256     assert(is(typeof(d) == int));
4257     assert(d == 5);
4258     auto e = min(a, b, c);
4259     assert(is(typeof(e) == double));
4260     assert(e == 2);
4261     // mixed signedness test
4262     a = -10;
4263     uint f = 10;
4264     static assert(is(typeof(min(a, f)) == int));
4265     assert(min(a, f) == -10);
4266 }
4267
4268 // MaxType
4269 template MaxType(T...)
4270 {
4271     static assert(T.length >= 2);
4272     static if (T.length == 2)
4273     {
4274         static if (!is(typeof(T[0].min)))
4275             alias CommonType!(T[0 .. 2]) MaxType;
4276         else static if (T[1].max > T[0].max)
4277             alias T[1] MaxType;
4278         else
4279             alias T[0] MaxType;
4280     }
4281     else
4282     {
4283         alias MaxType!(MaxType!(T[0], T[1]), T[2 .. $]) MaxType;
4284     }
4285 }
4286
4287 // max
4288 /**
4289 Returns the maximum of the passed-in values. The type of the result is
4290 computed by using $(XREF traits, CommonType).
4291
4292 Example:
4293 ----
4294 int a = 5;
4295 short b = 6;
4296 double c = 2;
4297 auto d = max(a, b);
4298 assert(is(typeof(d) == int));
4299 assert(d == 6);
4300 auto e = min(a, b, c);
4301 assert(is(typeof(e) == double));
4302 assert(e == 2);
4303 ----
4304 */
4305 MaxType!(T1, T2, T) max(T1, T2, T...)(T1 a, T2 b, T xs)
4306 {
4307     static if (T.length == 0)
4308     {
4309         static if (isIntegral!(T1) && isIntegral!(T2)
4310                    && (mostNegative!(T1) < 0) != (mostNegative!(T2) < 0))
4311             static if (mostNegative!(T1) < 0)
4312                 immutable chooseB = b > a || a < 0;
4313             else
4314                 immutable chooseB = b > a && b > 0;
4315         else
4316             immutable chooseB = b > a;
4317         return cast(typeof(return)) (chooseB ? b : a);
4318     }
4319     else
4320     {
4321         return max(max(a, b), xs);
4322     }
4323 }
4324
4325 unittest
4326 {
4327     debug(std_algorithm) scope(success)
4328         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4329     int a = 5;
4330     short b = 6;
4331     double c = 2;
4332     auto d = max(a, b);
4333     assert(is(typeof(d) == int));
4334     assert(d == 6);
4335     auto e = max(a, b, c);
4336     assert(is(typeof(e) == double));
4337     assert(e == 6);
4338     // mixed sign
4339     a = -5;
4340     uint f = 5;
4341     static assert(is(typeof(max(a, f)) == uint));
4342     assert(max(a, f) == 5);
4343 }
4344
4345 /**
4346 Returns the minimum element of a range together with the number of
4347 occurrences. The function can actually be used for counting the
4348 maximum or any other ordering predicate (that's why $(D maxCount) is
4349 not provided).
4350
4351 Example:
4352 ----
4353 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
4354 // Minimum is 1 and occurs 3 times
4355 assert(minCount(a) == tuple(1, 3));
4356 // Maximum is 4 and occurs 2 times
4357 assert(minCount!("a > b")(a) == tuple(4, 2));
4358 ----
4359  */
4360 Tuple!(ElementType!(Range), size_t)
4361 minCount(alias pred = "a < b", Range)(Range range)
4362 {
4363     if (range.empty) return typeof(return)();
4364     auto p = &(range.front());
4365     size_t occurrences = 1;
4366     for (range.popFront; !range.empty; range.popFront)
4367     {
4368         if (binaryFun!(pred)(*p, range.front)) continue;
4369         if (binaryFun!(pred)(range.front, *p))
4370         {
4371             // change the min
4372             p = &(range.front());
4373             occurrences = 1;
4374         }
4375         else
4376         {
4377             ++occurrences;
4378         }
4379     }
4380     return tuple(*p, occurrences);
4381 }
4382
4383 unittest
4384 {
4385     debug(std_algorithm) scope(success)
4386         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4387     int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
4388     assert(minCount(a) == tuple(1, 3));
4389     assert(minCount!("a > b")(a) == tuple(4, 2));
4390     int[][] b = [ [4], [2, 4], [4], [4] ];
4391     auto c = minCount!("a[0] < b[0]")(b);
4392     assert(c == tuple([2, 4], 1), text(c[0]));
4393 }
4394
4395 // minPos
4396 /**
4397 Returns the position of the minimum element of forward range $(D
4398 range), i.e. a subrange of $(D range) starting at the position of its
4399 smallest element and with the same ending as $(D range). The function
4400 can actually be used for counting the maximum or any other ordering
4401 predicate (that's why $(D maxPos) is not provided).
4402
4403 Example:
4404 ----
4405 int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
4406 // Minimum is 1 and first occurs in position 3
4407 assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]);
4408 // Maximum is 4 and first occurs in position 2
4409 assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]);
4410 ----
4411  */
4412 Range minPos(alias pred = "a < b", Range)(Range range)
4413 {
4414     if (range.empty) return range;
4415     auto result = range;
4416     for (range.popFront; !range.empty; range.popFront)
4417     {
4418         if (binaryFun!(pred)(result.front, range.front)
4419                 || !binaryFun!(pred)(range.front, result.front)) continue;
4420         // change the min
4421         result = range;
4422     }
4423     return result;
4424 }
4425
4426 unittest
4427 {
4428     debug(std_algorithm) scope(success)
4429         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4430     int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
4431 // Minimum is 1 and first occurs in position 3
4432     assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]);
4433 // Maximum is 4 and first occurs in position 5
4434     assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]);
4435 }
4436
4437 // mismatch
4438 /**
4439 Sequentially compares elements in $(D r1) and $(D r2) in lockstep, and
4440 stops at the first mismatch (according to $(D pred), by default
4441 equality). Returns a tuple with the reduced ranges that start with the
4442 two mismatched values. Performs $(BIGOH min(r1.length, r2.length))
4443 evaluations of $(D pred). See also $(WEB
4444 sgi.com/tech/stl/_mismatch.html, STL's mismatch).
4445
4446 Example:
4447 ----
4448 int[]    x = [ 1,  5, 2, 7,   4, 3 ];
4449 double[] y = [ 1., 5, 2, 7.3, 4, 8 ];
4450 auto m = mismatch(x, y);
4451 assert(m[0] == x[3 .. $]);
4452 assert(m[1] == y[3 .. $]);
4453 ----
4454 */
4455
4456 Tuple!(Range1, Range2)
4457 mismatch(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2)
4458     if (isInputRange!(Range1) && isInputRange!(Range2))
4459 {
4460     for (; !r1.empty && !r2.empty; r1.popFront(), r2.popFront())
4461     {
4462         if (!binaryFun!(pred)(r1.front, r2.front)) break;
4463     }
4464     return tuple(r1, r2);
4465 }
4466
4467 unittest
4468 {
4469     debug(std_algorithm) scope(success)
4470         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4471     // doc example
4472     int[]    x = [ 1,  5, 2, 7,   4, 3 ];
4473     double[] y = [ 1., 5, 2, 7.3, 4, 8 ];
4474     auto m = mismatch(x, y);
4475     assert(m[0] == [ 7, 4, 3 ]);
4476     assert(m[1] == [ 7.3, 4, 8 ]);
4477
4478     int[] a = [ 1, 2, 3 ];
4479     int[] b = [ 1, 2, 4, 5 ];
4480     auto mm = mismatch(a, b);
4481     assert(mm[0] == [3]);
4482     assert(mm[1] == [4, 5]);
4483 }
4484
4485 // levenshteinDistance
4486 /**
4487 Encodes $(WEB realityinteractive.com/rgrzywinski/archives/000249.html,
4488 edit operations) necessary to transform one sequence into
4489 another. Given sequences $(D s) (source) and $(D t) (target), a
4490 sequence of $(D EditOp) encodes the steps that need to be taken to
4491 convert $(D s) into $(D t). For example, if $(D s = "cat") and $(D
4492 "cars"), the minimal sequence that transforms $(D s) into $(D t) is:
4493 skip two characters, replace 't' with 'r', and insert an 's'. Working
4494 with edit operations is useful in applications such as spell-checkers
4495 (to find the closest word to a given misspelled word), approximate
4496 searches, diff-style programs that compute the difference between
4497 files, efficient encoding of patches, DNA sequence analysis, and
4498 plagiarism detection.
4499 */
4500
4501 enum EditOp : char
4502 {
4503     /** Current items are equal; no editing is necessary. */
4504     none = 'n',
4505     /** Substitute current item in target with current item in source. */
4506     substitute = 's',
4507     /** Insert current item from the source into the target. */
4508     insert = 'i',
4509     /** Remove current item from the target. */
4510     remove = 'r'
4511 }
4512
4513 struct Levenshtein(Range, alias equals, CostType = size_t)
4514 {
4515     void deletionIncrement(CostType n)
4516     {
4517         _deletionIncrement = n;
4518         InitMatrix();
4519     }
4520
4521     void insertionIncrement(CostType n)
4522     {
4523         _insertionIncrement = n;
4524         InitMatrix();
4525     }
4526
4527     CostType distance(Range s, Range t)
4528     {
4529         auto slen = walkLength(s), tlen = walkLength(t);
4530         AllocMatrix(slen + 1, tlen + 1);
4531         foreach (i; 1 .. rows)
4532         {
4533             auto sfront = s.front;
4534             s.popFront();
4535             auto tt = t;
4536             foreach (j; 1 .. cols)
4537             {
4538                 auto cSub = _matrix[i - 1][j - 1]
4539                     + (equals(sfront, tt.front) ? 0 : _substitutionIncrement);
4540                 tt.popFront();
4541                 auto cIns = _matrix[i][j - 1] + _insertionIncrement;
4542                 auto cDel = _matrix[i - 1][j] + _deletionIncrement;
4543                 switch (min_index(cSub, cIns, cDel)) {
4544                 case 0:
4545                     _matrix[i][j] = cSub;
4546                     break;
4547                 case 1:
4548                     _matrix[i][j] = cIns;
4549                     break;
4550                 default:
4551                     _matrix[i][j] = cDel;
4552                     break;
4553                 }
4554             }
4555         }
4556         return _matrix[slen][tlen];
4557     }
4558
4559     EditOp[] path(Range s, Range t)
4560     {
4561         distance(s, t);
4562         return path();
4563     }
4564
4565     EditOp[] path()
4566     {
4567         EditOp[] result;
4568         size_t i = rows - 1, j = cols - 1;
4569         // restore the path
4570         while (i || j) {
4571             auto cIns = j == 0 ? CostType.max : _matrix[i][j - 1];
4572             auto cDel = i == 0 ? CostType.max : _matrix[i - 1][j];
4573             auto cSub = i == 0 || j == 0
4574                 ? CostType.max
4575                 : _matrix[i - 1][j - 1];
4576             switch (min_index(cSub, cIns, cDel)) {
4577             case 0:
4578                 result ~= _matrix[i - 1][j - 1] == _matrix[i][j]
4579                     ? EditOp.none
4580                     : EditOp.substitute;
4581                 --i;
4582                 --j;
4583                 break;
4584             case 1:
4585                 result ~= EditOp.insert;
4586                 --j;
4587                 break;
4588             default:
4589                 result ~= EditOp.remove;
4590                 --i;
4591                 break;
4592             }
4593         }
4594         reverse(result);
4595         return result;
4596     }
4597
4598 private:
4599     CostType _deletionIncrement = 1,
4600         _insertionIncrement = 1,
4601         _substitutionIncrement = 1;
4602     CostType[][] _matrix;
4603     size_t rows, cols;
4604
4605     void AllocMatrix(size_t r, size_t c) {
4606         rows = r;
4607         cols = c;
4608         if (!_matrix || _matrix.length < r || _matrix[0].length < c) {
4609             delete _matrix;
4610             _matrix = new CostType[][](r, c);
4611             InitMatrix();
4612         }
4613     }
4614
4615     void InitMatrix() {
4616         foreach (i, row; _matrix) {
4617             row[0] = i * _deletionIncrement;
4618         }
4619         if (!_matrix) return;
4620         for (auto i = 0u; i != _matrix[0].length; ++i) {
4621             _matrix[0][i] = i * _insertionIncrement;
4622         }
4623     }
4624
4625     static uint min_index(CostType i0, CostType i1, CostType i2)
4626     {
4627         if (i0 <= i1)
4628         {
4629             return i0 <= i2 ? 0 : 2;
4630         }
4631         else
4632         {
4633             return i1 <= i2 ? 1 : 2;
4634         }
4635     }
4636 }
4637
4638 /**
4639 Returns the $(WEB wikipedia.org/wiki/Levenshtein_distance, Levenshtein
4640 distance) between $(D s) and $(D t). The Levenshtein distance computes
4641 the minimal amount of edit operations necessary to transform $(D s)
4642 into $(D t).  Performs $(BIGOH s.length * t.length) evaluations of $(D
4643 equals) and occupies $(BIGOH s.length * t.length) storage.
4644
4645 Example:
4646 ----
4647 assert(levenshteinDistance("cat", "rat") == 1);
4648 assert(levenshteinDistance("parks", "spark") == 2);
4649 assert(levenshteinDistance("kitten", "sitting") == 3);
4650 // ignore case
4651 assert(levenshteinDistance!("toupper(a) == toupper(b)")
4652     ("parks", "SPARK") == 2);
4653 ----
4654 */
4655 size_t levenshteinDistance(alias equals = "a == b", Range1, Range2)
4656     (Range1 s, Range2 t)
4657     if (isForwardRange!(Range1) && isForwardRange!(Range2))
4658 {
4659     Levenshtein!(Range1, binaryFun!(equals), size_t) lev;
4660     return lev.distance(s, t);
4661 }
4662
4663 /**
4664 Returns the Levenshtein distance and the edit path between $(D s) and
4665 $(D t).
4666
4667 Example:
4668 ---
4669 string a = "Saturday", b = "Sunday";
4670 auto p = levenshteinDistanceAndPath(a, b);
4671 assert(p[0] == 3);
4672 assert(equal(p[1], "nrrnsnnn"));
4673 ---
4674 */
4675 Tuple!(size_t, EditOp[])
4676 levenshteinDistanceAndPath(alias equals = "a == b", Range1, Range2)
4677     (Range1 s, Range2 t)
4678     if (isForwardRange!(Range1) && isForwardRange!(Range2))
4679 {
4680     Levenshtein!(Range1, binaryFun!(equals)) lev;
4681     auto d = lev.distance(s, t);
4682     return tuple(d, lev.path);
4683 }
4684
4685 unittest
4686 {
4687     debug(std_algorithm) scope(success)
4688         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4689     assert(levenshteinDistance("a", "a") == 0);
4690     assert(levenshteinDistance("a", "b") == 1);
4691     assert(levenshteinDistance("aa", "ab") == 1);
4692     assert(levenshteinDistance("aa", "abc") == 2);
4693     assert(levenshteinDistance("Saturday", "Sunday") == 3);
4694     assert(levenshteinDistance("kitten", "sitting") == 3);
4695     //lev.deletionIncrement = 2;
4696     //lev.insertionIncrement = 100;
4697     string a = "Saturday", b = "Sunday";
4698     auto p = levenshteinDistanceAndPath(a, b);
4699     assert(cast(string) p[1] == "nrrnsnnn");
4700 }
4701
4702 // copy
4703 /**
4704 Copies the content of $(D source) into $(D target) and returns the
4705 remaining (unfilled) part of $(D target). See also $(WEB
4706 sgi.com/tech/stl/_copy.html, STL's copy). If a behavior similar to
4707 $(WEB sgi.com/tech/stl/copy_backward.html, STL's copy_backward) is
4708 needed, use $(D copy(retro(source), retro(target))). See also $(XREF
4709 range, retro).
4710
4711 Example:
4712 ----
4713 int[] a = [ 1, 5 ];
4714 int[] b = [ 9, 8 ];
4715 int[] c = new int[a.length + b.length + 10];
4716 auto d = copy(b, copy(a, c));
4717 assert(c[0 .. a.length + b.length] == a ~ b);
4718 assert(d.length == 10);
4719 ----
4720
4721 As long as the target range elements support assignment from source
4722 range elements, different types of ranges are accepted.
4723
4724 Example:
4725 ----
4726 float[] a = [ 1.0f, 5 ];
4727 double[] b = new double[a.length];
4728 auto d = copy(a, b);
4729 ----
4730
4731 To copy at most $(D n) elements from range $(D a) to range $(D b), you
4732 may want to use $(D copy(take(a, n), b)). To copy those elements from
4733 range $(D a) that satisfy predicate $(D pred) to range $(D b), you may
4734 want to use $(D copy(filter!(pred)(a), b)).
4735
4736 Example:
4737 ----
4738 int[] a = [ 1, 5, 8, 9, 10, 1, 2, 0 ];
4739 auto b = new int[a.length];
4740 auto c = copy(filter!("(a & 1) == 1")(a), b);
4741 assert(b[0 .. $ - c.length] == [ 1, 5, 9, 1 ]);
4742 ----
4743
4744  */
4745 Range2 copy(Range1, Range2)(Range1 source, Range2 target)
4746 if (isInputRange!Range1 && isOutputRange!(Range2, ElementType!Range1))
4747 {
4748     for (; !source.empty; source.popFront())
4749     {
4750         put(target, source.front);
4751     }
4752     return target;
4753 }
4754
4755 unittest
4756 {
4757     debug(std_algorithm) scope(success)
4758         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4759     {
4760         int[] a = [ 1, 5 ];
4761         int[] b = [ 9, 8 ];
4762         int[] c = new int[a.length + b.length + 10];
4763         auto d = copy(b, copy(a, c));
4764         assert(c[0 .. a.length + b.length] == a ~ b);
4765         assert(d.length == 10);
4766     }
4767     {
4768         int[] a = [ 1, 5 ];
4769         int[] b = [ 9, 8 ];
4770         auto e = copy(filter!("a > 1")(a), b);
4771         assert(b[0] == 5 && e.length == 1);
4772     }
4773 }
4774
4775 // swapRanges
4776 /**
4777 Swaps all elements of $(D r1) with successive elements in $(D r2).
4778 Returns a tuple containing the remainder portions of $(D r1) and $(D
4779 r2) that were not swapped (one of them will be empty). The ranges may
4780 be of different types but must have the same element type and support
4781 swapping.
4782
4783 Example:
4784 ----
4785 int[] a = [ 100, 101, 102, 103 ];
4786 int[] b = [ 0, 1, 2, 3 ];
4787 auto c = swapRanges(a[1 .. 3], b[2 .. 4]);
4788 assert(c[0].empty && c[1].empty);
4789 assert(a == [ 100, 2, 3, 103 ]);
4790 assert(b == [ 0, 1, 101, 102 ]);
4791 ----
4792 */
4793 Tuple!(Range1, Range2)
4794 swapRanges(Range1, Range2)(Range1 r1, Range2 r2)
4795     if (isInputRange!(Range1) && isInputRange!(Range2)
4796             && hasSwappableElements!(Range1) && hasSwappableElements!(Range2)
4797             && is(ElementType!(Range1) == ElementType!(Range2)))
4798 {
4799     for (; !r1.empty && !r2.empty; r1.popFront, r2.popFront)
4800     {
4801         swap(r1.front, r2.front);
4802     }
4803     return tuple(r1, r2);
4804 }
4805
4806 unittest
4807 {
4808     debug(std_algorithm) scope(success)
4809         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4810     int[] a = [ 100, 101, 102, 103 ];
4811     int[] b = [ 0, 1, 2, 3 ];
4812     auto c = swapRanges(a[1 .. 3], b[2 .. 4]);
4813     assert(c[0].empty && c[1].empty);
4814     assert(a == [ 100, 2, 3, 103 ]);
4815     assert(b == [ 0, 1, 101, 102 ]);
4816 }
4817
4818 // reverse
4819 /**
4820 Reverses $(D r) in-place.  Performs $(D r.length) evaluations of $(D
4821 swap). See also $(WEB sgi.com/tech/stl/_reverse.html, STL's reverse).
4822
4823 Example:
4824 ----
4825 int[] arr = [ 1, 2, 3 ];
4826 reverse(arr);
4827 assert(arr == [ 3, 2, 1 ]);
4828 ----
4829 */
4830 void reverse(Range)(Range r)
4831 if (isBidirectionalRange!(Range) && hasSwappableElements!(Range))
4832 {
4833     while (!r.empty)
4834     {
4835         swap(r.front, r.back);
4836         r.popFront;
4837         if (r.empty) break;
4838         r.popBack;
4839     }
4840 }
4841
4842 unittest
4843 {
4844     debug(std_algorithm) scope(success)
4845         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4846     int[] range = null;
4847     reverse(range);
4848     range = [ 1 ];
4849     reverse(range);
4850     assert(range == [1]);
4851     range = [1, 2];
4852     reverse(range);
4853     assert(range == [2, 1]);
4854     range = [1, 2, 3];
4855     reverse(range);
4856     assert(range == [3, 2, 1]);
4857 }
4858
4859 // bringToFront
4860 /**
4861 The $(D bringToFront) function has considerable flexibility and
4862 usefulness. It can rotate elements in one buffer left or right, swap
4863 buffers of equal length, and even move elements across disjoint
4864 buffers of different types and different lengths.
4865
4866 $(D bringToFront) takes two ranges $(D front) and $(D back), which may
4867 be of different types. Considering the concatenation of $(D front) and
4868 $(D back) one unified range, $(D bringToFront) rotates that unified
4869 range such that all elements in $(D back) are brought to the beginning
4870 of the unified range. The relative ordering of elements in $(D front)
4871 and $(D back), respectively, remains unchanged.
4872
4873 The simplest use of $(D bringToFront) is for rotating elements in a
4874 buffer. For example:
4875
4876 ----
4877 auto arr = [4, 5, 6, 7, 1, 2, 3];
4878 bringToFront(arr[0 .. 4], arr[4 .. $]);
4879 assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);
4880 ----
4881
4882 The $(D front) range may actually "step over" the $(D back)
4883 range. This is very useful with forward ranges that cannot compute
4884 comfortably right-bounded subranges like $(D arr[0 .. 4]) above. In
4885 the example below, $(D r2) is a right subrange of $(D r1).
4886
4887 ----
4888 auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3);
4889 auto r1 = list[];
4890 auto r2 = list[]; popFrontN(r2, 4);
4891 assert(equal(r2, [ 1, 2, 3 ]));
4892 bringToFront(r1, r2);
4893 assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ]));
4894 ----
4895
4896 Elements can be swapped across ranges of different types:
4897
4898 ----
4899 auto list = SList!(int)(4, 5, 6, 7);
4900 auto vec = [ 1, 2, 3 ];
4901 bringToFront(list[], vec);
4902 assert(equal(list[], [ 1, 2, 3, 4 ]));
4903 assert(equal(vec, [ 5, 6, 7 ]));
4904 ----
4905
4906 Performs $(BIGOH max(front.length, back.length)) evaluations of $(D
4907 swap). See also $(WEB sgi.com/tech/stl/_rotate.html, STL's rotate).
4908
4909 Preconditions:
4910
4911 Either $(D front) and $(D back) are disjoint, or $(D back) is
4912 reachable from $(D front) and $(D front) is not reachable from $(D
4913 back).
4914
4915 Returns:
4916
4917 The number of elements brought to the front, i.e., the length of $(D
4918 back).
4919 */
4920 size_t bringToFront(Range1, Range2)(Range1 front, Range2 back)
4921     if (isInputRange!Range1 && isForwardRange!Range2)
4922 {
4923     enum bool sameHeadExists = is(typeof(front.sameHead(back)));
4924     size_t result;
4925     for (bool semidone; !front.empty && !back.empty; )
4926     {
4927         static if (sameHeadExists)
4928         {
4929             if (front.sameHead(back)) break; // shortcut
4930         }
4931         // Swap elements until front and/or back ends.
4932         auto back0 = back.save;
4933         size_t nswaps;
4934         do
4935         {
4936             static if (sameHeadExists)
4937             {
4938                 // Detect the stepping-over condition.
4939                 if (front.sameHead(back0)) back0 = back.save;
4940             }
4941             swapFront(front, back);
4942             ++nswaps;
4943             front.popFront();
4944             back.popFront();
4945         }
4946         while (!front.empty && !back.empty);
4947
4948         if (!semidone) result += nswaps;
4949
4950         // Now deal with the remaining elements.
4951         if (back.empty)
4952         {
4953             if (front.empty) break;
4954             // Right side was shorter, which means that we've brought
4955             // all the back elements to the front.
4956             semidone = true;
4957             // Next pass: bringToFront(front, back0) to adjust the rest.
4958             back = back0;
4959         }
4960         else
4961         {
4962             assert(front.empty);
4963             // Left side was shorter. Let's step into the back.
4964             static if (is(Range1 == Take!Range2))
4965             {
4966                 front = take(back0, nswaps);
4967             }
4968             else
4969             {
4970                 immutable subresult = bringToFront(take(back0, nswaps),
4971                                                    back);
4972                 if (!semidone) result += subresult;
4973                 break; // done
4974             }
4975         }
4976     }
4977     return result;
4978 }
4979
4980 unittest
4981 {
4982     debug(std_algorithm) scope(success)
4983         writeln("unittest @", __FILE__, ":", __LINE__, " done.");
4984     // doc example
4985     {
4986         int[] arr = [4, 5, 6, 7, 1, 2, 3];
4987         auto p = bringToFront(arr[0 .. 4], arr[4 .. $]);
4988         assert(p == arr.length - 4);
4989         assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ], text(arr));
4990     }
4991     {
4992         auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3);
4993         auto r1 = list[];
4994         <