1 /*******************************************************************************
2 
3     Collection of utilities to modify arrays and buffers in-place.
4 
5     All functions in this module only work on mutable arguments and modify them
6     in place. New memory must never be allocated.
7 
8     Based on `tango.core.Array` module from Tango library.
9 
10     Copyright:
11         Copyright (C) 2005-2006 Sean Kelly.
12         Some parts copyright (c) 2009-2016 dunnhumby Germany GmbH.
13         All rights reserved.
14 
15     License:
16         Tango Dual License: 3-Clause BSD License / Academic Free License v3.0.
17         See LICENSE_TANGO.txt for details.
18 
19 *******************************************************************************/
20 
21 module ocean.core.array.Mutation;
22 
23 
24 import core.stdc.string; // memmove, memset
25 import core.stdc.math; // fabs;
26 
27 import ocean.meta.traits.Basic;
28 import ocean.meta.types.Function;
29 import ocean.meta.AliasSeq;
30 import ocean.core.Buffer;
31 import ocean.core.array.DefaultPredicates;
32 import ocean.core.Verify;
33 
34 version (unittest)
35 {
36     import ocean.core.Test;
37     import ocean.meta.types.Qualifiers;
38     import ocean.text.convert.Formatter;
39 }
40 
41 /*******************************************************************************
42 
43     Performs a linear scan of complete array, replacing occurrences of
44     specified element with the new element.  Comparisons will be performed
45     using the supplied predicate or '==' if none is supplied.
46 
47     Params:
48         array = The array to scan.
49         element = The pattern to match.
50         new_element = The value to substitute.
51         pred  = The evaluation predicate, which should return true if e1 is
52             equal to e2 and false if not.  This predicate may be any
53             callable type.
54 
55     Returns:
56         The number of elements replaced.
57 
58 *******************************************************************************/
59 
60 size_t replace ( T, Pred = DefaultPredicates.IsEqual!(T) )
61     ( T[] array, in T element, T new_element, Pred pred = Pred.init )
62 {
63     static assert( isCallableType!(Pred) );
64 
65     size_t cnt = 0;
66 
67     foreach( size_t pos, ref T cur; array )
68     {
69         if( pred( cur, element ) )
70         {
71             cur = new_element;
72             ++cnt;
73         }
74     }
75 
76     return cnt;
77 }
78 
79 ///
80 unittest
81 {
82     auto array = "abbbbc".dup;
83     test!("==")(replace(array, 'b', 'x'), 4);
84     test!("==")(array, "axxxxc");
85 }
86 
87 unittest
88 {
89     test!("==")( replace( "gbbbi".dup, 'a', 'b' ), 0 );
90     test!("==")( replace( "gbbbi".dup, 'g', 'h' ), 1 );
91     test!("==")( replace( "gbbbi".dup, 'b', 'c' ), 3 );
92     test!("==")( replace( "gbbbi".dup, 'i', 'j' ), 1 );
93     test!("==")( replace( "gbbbi".dup, 'd', 'e' ), 0 );
94 }
95 
96 /// ditto
97 size_t replace ( T, Pred = DefaultPredicates.IsEqual!(T) )
98     ( ref Buffer!(T) array, in T element, T new_element, Pred pred = Pred.init )
99 {
100     return replace(array[0..array.length], element, new_element, pred);
101 }
102 
103 ///
104 unittest
105 {
106     auto buffer = createBuffer("abbbbc");
107     test!("==")(replace(buffer, 'b', 'x'), 4);
108     test!("==")(buffer[], "axxxxc");
109 }
110 
111 /*******************************************************************************
112 
113     Performs a linear scan of the complete array, replacing elements where pred
114     returns true.
115 
116     Params:
117         array = The array to scan.
118         new_element = The value to substitute.
119         pred = The evaluation predicate, which should return true if the
120             element is a valid match and false if not.  This predicate
121             may be any callable type.
122 
123     Returns:
124     The number of elements replaced.
125 
126 *******************************************************************************/
127 
128 size_t replaceIf ( T, Pred ) ( T[] array, T new_element, Pred pred )
129 {
130     static assert( isCallableType!(Pred) );
131 
132     size_t cnt = 0;
133 
134     foreach( size_t pos, ref T cur; array )
135     {
136         if( pred( cur ) )
137         {
138             cur = new_element;
139             ++cnt;
140         }
141     }
142     return cnt;
143 }
144 
145 ///
146 unittest
147 {
148     auto array = "abbc".dup;
149     test!("==")(replaceIf(array, 'x', (char c) { return c > 'a'; }), 3);
150     test!("==")(array, "axxx");
151 }
152 
153 /// ditto
154 size_t replaceIf ( T, Pred ) ( ref Buffer!(T) array, T new_element, Pred pred )
155 {
156     return replaceIf(array[0..array.length], new_element, pred);
157 }
158 
159 ///
160 unittest
161 {
162     auto buffer = createBuffer("abbc");
163     test!("==")(replaceIf(buffer, 'x', (char c) { return c > 'a'; }), 3);
164     test!("==")(buffer[], "axxx");
165 }
166 
167 unittest
168 {
169     test!("==")( replaceIf( "gbbbi".dup, 'b', ( char c ) { return c == 'a'; } ), 0 );
170     test!("==")( replaceIf( "gbbbi".dup, 'h', ( char c ) { return c == 'g'; } ), 1 );
171     test!("==")( replaceIf( "gbbbi".dup, 'c', ( char c ) { return c == 'b'; } ), 3 );
172     test!("==")( replaceIf( "gbbbi".dup, 'j', ( char c ) { return c == 'i'; } ), 1 );
173     test!("==")( replaceIf( "gbbbi".dup, 'e', ( char c ) { return c == 'd'; } ), 0 );
174 }
175 
176 /*******************************************************************************
177 
178     Performs a linear scan of complete array, moving all items matching
179     element to the end of the sequence.  The relative order of items not
180     matching the matching element will be preserved.  Comparisons will be
181     performed using the supplied predicate or '==' if none is supplied.
182 
183     Params:
184         array = The array to scan. This parameter is not marked 'ref'
185             to allow temporary slices to be modified.  As array is not resized
186             in any way, omitting the 'ref' qualifier has no effect on the
187             result of this operation, even though it may be viewed as a
188             side-effect.
189         element = The element value to look for
190         pred = The evaluation predicate, which should return true if e1 is
191             equal to e2 and false if not.  This predicate may be any
192             callable type.
193 
194     Returns:
195         The number of elements that do not match element.
196 
197 *******************************************************************************/
198 
199 size_t moveToEnd ( T, Pred = DefaultPredicates.IsEqual!(T) )
200     ( T[] array, in T element, Pred pred = Pred.init )
201 {
202     static assert( isCallableType!(Pred) );
203 
204     // NOTE: Indexes are passed instead of references because DMD does
205     //       not inline the reference-based version.
206     void exch( size_t p1, size_t p2 )
207     {
208         T t = array[p1];
209         array[p1] = array[p2];
210         array[p2] = t;
211     }
212 
213     size_t cnt = 0;
214 
215     for( size_t pos = 0, len = array.length; pos < len; ++pos )
216     {
217         if( pred( array[pos], element ) )
218             ++cnt;
219         else
220             exch( pos, pos - cnt );
221     }
222     return array.length - cnt;
223 }
224 
225 /// ditto
226 size_t moveToEnd ( T, Pred = DefaultPredicates.IsEqual!(T) )
227     ( ref Buffer!(T) array, in T element, Pred pred = Pred.init )
228 {
229     return moveToEnd(array[0..array.length], element, pred);
230 }
231 
232 ///
233 unittest
234 {
235     auto buffer = createBuffer("abbcc");
236     test!("==")(moveToEnd(buffer, 'b'), 3);
237     test!("==")(buffer[], "accbb");
238 }
239 
240 unittest
241 {
242     static void testOne ( cstring _array,
243         char element, size_t num, int line = __LINE__ )
244     {
245         auto array = _array.dup;
246         auto t = new NamedTest(format("moveToEnd.testOne:{}", line));
247         t.test!("==")(moveToEnd(array, element), num);
248         foreach (pos, cur; array)
249             t.test(pos < num ? cur != element : cur == element);
250     }
251 
252     testOne("abcdefghij", 'x', 10);
253     testOne("xabcdefghi", 'x',  9);
254     testOne("abcdefghix", 'x',  9);
255     testOne("abxxcdefgh", 'x',  8);
256     testOne("xaxbcdxxex", 'x',  5);
257 }
258 
259 /*******************************************************************************
260 
261     Performs a linear scan of complete array, removing all elements that satisfy
262     pred from the sequence.  The relative order of elements that do not satisfy
263     pred will be preserved.
264 
265     Params:
266     array = The array to scan.  This parameter is not marked 'ref'
267            to allow temporary slices to be modified.  As array is not resized
268            in any way, omitting the 'ref' qualifier has no effect on the
269            result of this operation, even though it may be viewed as a
270            side-effect.
271     pred = The evaluation predicate, which should return true if the
272            element satisfies the condition and false if not.  This
273            predicate may be any callable type.
274 
275     Returns:
276         The number of elements that do not satisfy pred.
277 
278 *******************************************************************************/
279 
280 size_t removeIf ( T, Pred ) ( T[] array, Pred pred )
281 {
282     static assert( isCallableType!(Pred) );
283 
284     // NOTE: Indexes are passed instead of references because DMD does
285     //       not inline the reference-based version.
286     void exch( size_t p1, size_t p2 )
287     {
288         T t  = array[p1];
289         array[p1] = array[p2];
290         array[p2] = t;
291     }
292 
293     size_t cnt = 0;
294 
295     for( size_t pos = 0, len = array.length; pos < len; ++pos )
296     {
297         if( pred( array[pos] ) )
298             ++cnt;
299         else
300             exch( pos, pos - cnt );
301     }
302     return array.length - cnt;
303 }
304 
305 ///
306 unittest
307 {
308     auto array = "abbcc".dup;
309     test!("==")(removeIf(array, (char c) { return c == 'b'; }), 3);
310     test!("==")(array, "accbb");
311 }
312 
313 /// ditto
314 size_t removeIf ( T, Pred ) ( ref Buffer!(T) array, Pred pred )
315 {
316     return removeIf(array[0..array.length], pred);
317 }
318 
319 ///
320 unittest
321 {
322     auto buffer = createBuffer("abbcc");
323     test!("==")(removeIf(buffer, (char c) { return c == 'b'; }), 3);
324     test!("==")(buffer[], "accbb");
325 }
326 
327 unittest
328 {
329     static void testOne ( cstring _array,
330         scope bool delegate(char) dg, size_t num, int line = __LINE__ )
331     {
332         auto array = _array.dup;
333         auto t = new NamedTest(format("removeIf.testOne:{}", line));
334         t.test!("==")(removeIf( array, dg ), num);
335         foreach (pos, cur; array)
336             t.test(pos < num ? !dg( cur ) : dg( cur ));
337     }
338 
339     testOne("abcdefghij", ( char c ) { return c == 'x'; }, 10);
340     testOne("xabcdefghi", ( char c ) { return c == 'x'; },  9);
341     testOne("abcdefghix", ( char c ) { return c == 'x'; },  9);
342     testOne("abxxcdefgh", ( char c ) { return c == 'x'; },  8);
343     testOne("xaxbcdxxex", ( char c ) { return c == 'x'; },  5);
344 }
345 
346 /*******************************************************************************
347 
348     Performs a linear scan of complete array, moving all but the first element
349     of each consecutive group of duplicate elements to the end of the sequence.
350     The relative order of all remaining elements will be preserved.  Comparisons
351     will be performed using the supplied predicate or '==' if none is supplied.
352 
353     Params:
354         array = The array to scan.  This parameter is not marked 'ref'
355            to allow temporary slices to be modified.  As array is not resized
356            in any way, omitting the 'ref' qualifier has no effect on the
357            result of this operation, even though it may be viewed as a
358            side-effect.
359         pred = The evaluation predicate, which should return true if e1 is
360            equal to e2 and false if not.  This predicate may be any
361            callable type.
362 
363     Returns:
364         The number of distinct sub-sequences in array.
365 
366 *******************************************************************************/
367 
368 size_t distinct ( T, Pred = DefaultPredicates.IsEqual!(T) )
369     ( T[] array, Pred pred = Pred.init )
370 {
371     static assert( isCallableType!(Pred) );
372 
373     // NOTE: Indexes are passed instead of references because DMD does
374     //       not inline the reference-based version.
375     void exch( size_t p1, size_t p2 )
376     {
377         T t  = array[p1];
378         array[p1] = array[p2];
379         array[p2] = t;
380     }
381 
382     if( array.length < 2 )
383         return array.length;
384 
385     size_t cnt = 0;
386     T element = array[0];
387 
388     for( size_t pos = 1, len = array.length; pos < len; ++pos )
389     {
390         if( pred( array[pos], element ) )
391             ++cnt;
392         else
393         {
394             element = array[pos];
395             exch( pos, pos - cnt );
396         }
397     }
398     return array.length - cnt;
399 }
400 
401 ///
402 unittest
403 {
404     auto array = "aabbcdd".dup;
405     auto last = distinct(array);
406     test!("==")(array[0 .. last], "abcd");
407 }
408 
409 /// ditto
410 size_t distinct ( T, Pred = DefaultPredicates.IsEqual!(T) )
411     ( ref Buffer!(T) array, Pred pred = Pred.init )
412 {
413     return distinct(array[0..array.length], pred);
414 }
415 
416 ///
417 unittest
418 {
419     auto buffer = createBuffer("aabbcdd");
420     auto last = distinct(buffer);
421     test!("==")(buffer[0 .. last], "abcd");
422 }
423 
424 unittest
425 {
426     test!("==")(distinct("a".dup), 1);
427 
428     static void testOne ( cstring _array,
429         cstring expected, int line = __LINE__ )
430     {
431         auto array = _array.dup;
432         auto t = new NamedTest(format("distinct.testOne:{}", line));
433         t.test!("==")(distinct(array), expected.length);
434         t.test!("==")(array[0 .. expected.length], expected);
435     }
436 
437     testOne("abcdefghij", "abcdefghij");
438     testOne("aabcdefghi", "abcdefghi");
439     testOne("bcdefghijj", "bcdefghij");
440     testOne("abccdefghi", "abcdefghi");
441     testOne("abccdddefg", "abcdefg");
442 }
443 
444 /*******************************************************************************
445 
446     Partitions array such that all elements that satisfy pred will be placed
447     before the elements that do not satisfy pred.  The algorithm is not
448     required to be stable.
449 
450     Params:
451         array  = The array to partition.  This parameter is not marked 'ref'
452             to allow temporary slices to be sorted.  As array is not resized
453             in any way, omitting the 'ref' qualifier has no effect on
454             the result of this operation, even though it may be viewed
455             as a side-effect.
456         pred = The evaluation predicate, which should return true if the
457             element satisfies the condition and false if not.  This
458             predicate may be any callable type.
459 
460     Returns:
461         The number of elements that satisfy pred.
462 
463 *******************************************************************************/
464 
465 size_t partition ( T, Pred ) ( T[] array, Pred pred )
466 {
467     static assert( isCallableType!(Pred ) );
468 
469     // NOTE: Indexes are passed instead of references because DMD does
470     //       not inline the reference-based version.
471     void exch( size_t p1, size_t p2 )
472     {
473         T t = array[p1];
474         array[p1] = array[p2];
475         array[p2] = t;
476     }
477 
478     if( array.length == 0 )
479         return 0;
480 
481     size_t  l = 0,
482             r = array.length,
483             i = l,
484             j = r - 1;
485 
486     while( true )
487     {
488         while( i < r && pred( array[i] ) )
489             ++i;
490         while( j > l && !pred( array[j] ) )
491             --j;
492         if( i >= j )
493             break;
494         exch( i++, j-- );
495     }
496     return i;
497 }
498 
499 ///
500 unittest
501 {
502     auto array = "af242df56s2".dup;
503     test!("==")(partition(array, (char c) { return c >= '0' && c <= '9'; }), 6);
504 }
505 
506 /// ditto
507 size_t partition ( T, Pred ) ( ref Buffer!(T) array, Pred pred )
508 {
509     return partition(array[0..array.length], pred);
510 }
511 
512 ///
513 unittest
514 {
515     auto buffer = createBuffer("af242df56s2");
516     test!("==")(partition(buffer, (char c) { return c >= '0' && c <= '9'; }), 6);
517 }
518 
519 unittest
520 {
521     test!("==")(partition("".dup, (char c) { return true; }), 0);
522 
523     static void testOne ( cstring _array,
524         scope bool delegate(char) dg, size_t num, int line = __LINE__ )
525     {
526         auto array = _array.dup;
527         auto t = new NamedTest(format("partition.testOne:{}", line));
528         t.test!("==")(partition(array, dg), num);
529         for ( size_t pos = 0; pos < array.length; ++pos )
530             t.test( pos < num ? dg( array[pos] ) : !dg( array[pos] ) );
531     }
532 
533     testOne("abcdefg".dup, ( char c ) { return c < 'a'; }, 0);
534     testOne("gfedcba".dup, ( char c ) { return c < 'a'; }, 0);
535     testOne("abcdefg".dup, ( char c ) { return c < 'h'; }, 7);
536     testOne("gfedcba".dup, ( char c ) { return c < 'h'; }, 7);
537     testOne("abcdefg".dup, ( char c ) { return c < 'd'; }, 3);
538     testOne("gfedcba".dup, ( char c ) { return c < 'd'; }, 3);
539     testOne("bbdaabc".dup, ( char c ) { return c < 'c'; }, 5);
540     testOne("f".dup,       ( char c ) { return c == 'f'; }, 1);
541 }
542 
543 /*******************************************************************************
544 
545     Sorts array using the supplied predicate or '<' if none is supplied.  The
546     algorithm is not required to be stable.  The current implementation is
547     based on quicksort, but uses a three-way partitioning scheme to improve
548     performance for ranges containing duplicate values (Bentley and McIlroy,
549     1993).
550 
551     Params:
552         array = The array to sort.  This parameter is not marked 'ref' to
553             allow temporary slices to be sorted.  As array is not resized
554             in any way, omitting the 'ref' qualifier has no effect on
555             the result of this operation, even though it may be viewed
556             as a side-effect.
557         pred = The evaluation predicate, which should return true if e1 is
558             less than e2 and false if not.  This predicate may be any
559             callable type.
560 
561 *******************************************************************************/
562 
563 T[] sort ( T, Pred = DefaultPredicates.IsLess!(T) )
564     ( T[] array, Pred pred = Pred.init )
565 {
566     static assert( isCallableType!(Pred ) );
567 
568     bool equiv( T p1, T p2 )
569     {
570         return !pred( p1, p2 ) && !pred( p2, p1 );
571     }
572 
573     // NOTE: Indexes are passed instead of references because DMD does
574     //       not inline the reference-based version.
575     void exch( size_t p1, size_t p2 )
576     {
577         T t  = array[p1];
578         array[p1] = array[p2];
579         array[p2] = t;
580     }
581 
582     // NOTE: This algorithm operates on the inclusive range [l .. r].
583     void insertionSort( size_t l, size_t r )
584     {
585         for( size_t i = r; i > l; --i )
586         {
587             // swap the min element to array[0] to act as a sentinel
588             if( pred( array[i], array[i - 1] ) )
589                 exch( i, i - 1 );
590         }
591         for( size_t i = l + 2; i <= r; ++i )
592         {
593             size_t  j = i;
594             T    v = array[i];
595 
596             // don't need to test (j != l) because of the sentinel
597             while( pred( v, array[j - 1] ) )
598             {
599                 array[j] = array[j - 1];
600                 j--;
601             }
602             array[j] = v;
603         }
604     }
605 
606     size_t medianOf( size_t l, size_t m, size_t r )
607     {
608         if( pred( array[m], array[l] ) )
609         {
610             if( pred( array[r], array[m] ) )
611                 return m;
612             else
613             {
614                 if( pred( array[r], array[l] ) )
615                     return r;
616                 else
617                     return l;
618             }
619         }
620         else
621         {
622             if( pred( array[r], array[m] ) )
623             {
624                 if( pred( array[r], array[l] ) )
625                     return l;
626                 else
627                     return r;
628             }
629             else
630                 return m;
631         }
632     }
633 
634     // NOTE: This algorithm operates on the inclusive range [l .. r].
635     void quicksort( size_t l, size_t r, size_t d )
636     {
637         if( r <= l )
638             return;
639 
640         // HEURISTIC: Use insertion sort for sufficiently small arrays.
641         enum { MIN_LENGTH = 80 }
642         if( r - l < MIN_LENGTH )
643             return insertionSort( l, r );
644 
645         // HEURISTIC: Use the median-of-3 value as a pivot.  Swap this
646         //            into r so quicksort remains untouched.
647         exch( r, medianOf( l, l + (r - l) / 2, r ) );
648 
649         // This implementation of quicksort improves upon the classic
650         // algorithm by partitioning the array into three parts, one
651         // each for keys smaller than, equal to, and larger than the
652         // partitioning element, v:
653         //
654         // |--less than v--|--equal to v--|--greater than v--[v]
655         // l               j              i                   r
656         //
657         // This approach sorts ranges containing duplicate elements
658         // more quickly.  During processing, the following situation
659         // is maintained:
660         //
661         // |--equal--|--less--|--[###]--|--greater--|--equal--[v]
662         // l         p        i         j           q          r
663         //
664         // Please note that this implementation varies from the typical
665         // algorithm by replacing the use of signed index values with
666         // unsigned values.
667 
668         T v = array[r];
669         size_t  i = l,
670                 j = r,
671                 p = l,
672                 q = r;
673 
674         while( true )
675         {
676             while( pred( array[i], v ) )
677                 ++i;
678             while( pred( v, array[--j] ) )
679                 if( j == l ) break;
680             if( i >= j )
681                 break;
682             exch( i, j );
683             if( equiv( array[i], v ) )
684                 exch( p++, i );
685             if( equiv( v, array[j] ) )
686                 exch( --q, j );
687             ++i;
688         }
689         exch( i, r );
690         if( p < i )
691         {
692             j = i - 1;
693             for( size_t k = l; k < p; k++, j-- )
694                 exch( k, j );
695             quicksort( l, j, d );
696         }
697         if( ++i < q )
698         {
699             for( size_t k = r - 1; k >= q; k--, i++ )
700                 exch( k, i );
701             quicksort( i, r, d );
702         }
703     }
704 
705     size_t maxDepth( size_t x )
706     {
707         size_t d = 0;
708 
709         do
710         {
711             ++d;
712             x /= 2;
713         } while( x > 1 );
714         return d * 2; // same as "floor( log( x ) / log( 2 ) ) * 2"
715     }
716 
717     if( array.length > 1 )
718     {
719         quicksort( 0, array.length - 1, maxDepth( array.length ) );
720     }
721 
722     return array;
723 }
724 
725 unittest
726 {
727     static void testOne ( cstring _array, int line = __LINE__ )
728     {
729         auto array = _array.dup;
730         auto t = new NamedTest(format("sort.testOne:{}", line));
731         sort( array );
732         for ( ptrdiff_t i = 0; i + 1 < array.length; ++ i )
733             t.test!(">=")(array[i+1], array[i]);
734     }
735 
736     testOne("");
737     testOne("a");
738     testOne("mkcvalsidivjoaisjdvmzlksvdjioawmdsvmsdfefewv");
739     testOne("asdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdf");
740     testOne("the quick brown fox jumped over the lazy dog");
741     testOne("abcdefghijklmnopqrstuvwxyz");
742     testOne("zyxwvutsrqponmlkjihgfedcba");
743 
744     auto longer = new char[500];
745     foreach (i, ref c; longer)
746         c = cast(char) (i % 7);
747     testOne(longer);
748 
749     auto very_long = new char[100_000];
750     foreach (i, ref c; very_long)
751         c = cast(char) (i % 34);
752     testOne(very_long);
753 }
754 
755 // Test for static arrays
756 unittest
757 {
758     char[2][] arr = [ "EN", "FR", "DE" ];
759     sort(arr);
760     test!("==")(arr[0], "DE");
761     test!("==")(arr[1], "EN");
762     test!("==")(arr[2], "FR");
763     reverse(arr);
764     test!("==")(arr[2], "DE");
765     test!("==")(arr[1], "EN");
766     test!("==")(arr[0], "FR");
767 }
768 
769 /*******************************************************************************
770 
771     Swaps elements of argument array so they all come in reverse order
772 
773     Params:
774         array = array slice to reverse in-place
775 
776     Returns:
777         slice of the argument
778 
779 *******************************************************************************/
780 
781 T[] reverse (T) (T[] array)
782 {
783     for (ptrdiff_t i = 0; i < array.length / 2; ++i)
784     {
785         auto tmp = array[i];
786         array[i] = array[$-i-1];
787         array[$-i-1] = tmp;
788     }
789 
790     return array;
791 }
792 
793 ///
794 unittest
795 {
796     test (reverse((int[]).init) == (int[]).init);
797     test (reverse([1, 2, 3]) == [3, 2, 1]);
798     test (reverse([1, 2, 3, 4]) == [4, 3, 2, 1]);
799 }
800 
801 ////////////////////////////////////////////////////////////////////////////////
802 //          Functions below originally come from ocean.core.Array             //
803 ////////////////////////////////////////////////////////////////////////////////
804 
805 /*******************************************************************************
806 
807     Copies the contents of one element of arrays to another, starting at
808     dest[start], setting the length of the destination array first.
809     Note that start may be greater than the initial length of dest; dest will
810     then be extended appropriately.
811 
812     Template params:
813         func = function name for static assertion messages
814 
815     Params:
816         dest   = reference to the destination array
817         arrays = arrays to copy; a null parameter has the same effect as an
818                  empty array.
819 
820     Returns:
821         dest
822 
823     TODO: Could be made public but must then not rely on elements to be arrays.
824 
825 *******************************************************************************/
826 
827 public DE[] append ( DE, T... ) ( ref Buffer!(DE) dest, T arrays )
828 {
829     size_t appended_length = 0;
830     foreach (array; arrays)
831         appended_length += array.length;
832     dest.reserve(dest.length + appended_length);
833 
834     foreach (array; arrays)
835         dest ~= array;
836 
837     return dest[];
838 }
839 
840 public DE[] append ( DE, T... ) ( ref DE[] dest, T arrays )
841 {
842     return append( *(cast(Buffer!(DE)*) &dest), arrays);
843 }
844 
845 ///
846 unittest
847 {
848     auto buffer = createBuffer("zero");
849     append(buffer, "one", "two", "three");
850     test!("==")(buffer[], "zeroonetwothree");
851 }
852 
853 /*******************************************************************************
854 
855     Concatenates a list of arrays into a destination array. The function results
856     in at most a single memory allocation, if the destination array is too small
857     to contain the concatenation results.
858 
859     The destination array is passed as a reference, so its length can be
860     modified in-place as required. This avoids any per-element memory
861     allocation, which the normal ~ operator suffers from.
862 
863     Template params:
864         T = type of array element
865 
866     Params:
867         dest = reference to the destination array
868         arrays = variadic list of arrays to concatenate
869 
870     Returns:
871         dest
872 
873 ********************************************************************************/
874 
875 public DE[] concat ( DE, T... ) ( ref Buffer!(DE) dest, T arrays )
876 {
877     dest.reset();
878     return append(dest, arrays);
879 }
880 
881 ///
882 unittest
883 {
884     Buffer!(char) dest;
885     concat(dest, "hello "[], "world"[]);
886     test!("==")(dest[], "hello world");
887 }
888 
889 
890 public DE[] concat ( DE, T... ) ( ref DE[] dest, T arrays )
891 {
892     return concat(*(cast(Buffer!(DE)*) &dest), arrays);
893 }
894 
895 unittest
896 {
897     mstring dest;
898     concat(dest, "hello "[], "world"[]);
899     test!("==")(dest, "hello world");
900 }
901 
902 /*******************************************************************************
903 
904     Copies the contents of one array to another, setting the length of the
905     destination array first.
906 
907     This function is provided as a shorthand for this common operation.
908 
909     Template params:
910         T = type of array element
911 
912     Params:
913         dest = reference to the destination array
914         array = array to copy; null has the same effect as an empty array
915 
916     Returns:
917         dest
918 
919 *******************************************************************************/
920 
921 public T[] copy ( T, T2 ) ( ref Buffer!(T) dest, T2[] src )
922 {
923     static assert (is(typeof({ dest[] = src[]; })),
924                    "Type " ~ T2.stringof ~ " cannot be assigned to " ~ T.stringof);
925 
926     dest.length = src.length;
927     dest[] = src[];
928     return dest[];
929 }
930 
931 ///
932 unittest
933 {
934     Buffer!(char) dest;
935     cstring src = "hello";
936     copy(dest, src);
937     test!("==")(dest[], "hello"[]);
938 }
939 
940 unittest
941 {
942     Buffer!(cstring) dest;
943     mstring[] src = [ "Hello".dup, "World".dup ];
944     copy(dest, src);
945     // Doesn't compile in D2...
946     //test!("==")(dest[], src);
947 }
948 
949 public T[] copy ( T, T2 ) ( ref T[] dest, T2[] src )
950 {
951     return copy(*(cast(Buffer!(T)*) &dest), src);
952 }
953 
954 unittest
955 {
956     mstring dest;
957     cstring src = "hello";
958     copy(dest, src);
959     test!("==")(dest[], "hello"[]);
960 }
961 
962 /*******************************************************************************
963 
964     Copies the contents of src to dest, increasing dest.length if required.
965     Since dest.length will not be decreased, dest will contain tailing garbage
966     if src.length < dest.length.
967 
968     Template params:
969         T = type of array element
970 
971     Params:
972         dest  = reference to the destination array
973         array = array to copy; null has the same effect as an empty array
974 
975     Returns:
976         slice to copied elements in dest
977 
978 *******************************************************************************/
979 
980 public T[] copyExtend ( T, T2 ) ( ref Buffer!(T) dest, T2[] src )
981 {
982     static assert (is(typeof({ dest[] = src[]; })),
983                    "Type " ~ T2.stringof ~ " cannot be assigned to " ~ T.stringof);
984 
985     if (dest.length < src.length)
986         dest.length = src.length;
987     dest[0 .. src.length] = src[];
988     return dest[0 .. src.length];
989 }
990 
991 ///
992 unittest
993 {
994     auto dst = createBuffer("aa");
995     copyExtend(dst, "bbbb");
996     test!("==")(dst[], "bbbb");
997     copyExtend(dst, "ccc");
998     test!("==")(dst[], "cccb");
999 }
1000 
1001 public T[] copyExtend ( T, T2 ) ( ref T[] dest, T2[] src )
1002 {
1003     return copyExtend(*(cast(Buffer!(T)*) &dest), src);
1004 }
1005 
1006 unittest
1007 {
1008     auto dst = "aa".dup;
1009     copyExtend(dst, "bbbb");
1010     test!("==")(dst[], "bbbb");
1011     copyExtend(dst, "ccc");
1012     test!("==")(dst[], "cccb");
1013 }
1014 
1015 /*******************************************************************************
1016 
1017     Appends an element to a list of arrays, and copies the contents of the
1018     passed source array into the new element, setting the length of the
1019     destination array first.
1020 
1021     This function is provided as a shorthand for this common operation.
1022 
1023     Template params:
1024         T = type of array element
1025 
1026     Params:
1027         dest = reference to the destination array list
1028         array = array to copy
1029 
1030     Returns:
1031         dest
1032 
1033 *******************************************************************************/
1034 
1035 public void appendCopy ( T, T2 ) ( ref Buffer!(T)[] dest, T2[] src )
1036 {
1037     dest.length = dest.length + 1;
1038     copy(dest[dest.length - 1], src);
1039 }
1040 
1041 ///
1042 unittest
1043 {
1044     Buffer!(char)[] dest;
1045     cstring src = "hello";
1046     appendCopy(dest, src);
1047     test!("==")(dest[0][], "hello");
1048 }
1049 
1050 unittest
1051 {
1052     Buffer!(cstring)[] dest;
1053     mstring[] src = [ "Hello".dup, "World".dup ];
1054     appendCopy(dest, src);
1055     // Doesn't compile in D2...
1056     //test!("==")(dest[0][], src);
1057 }
1058 
1059 
1060 public void appendCopy ( T, T2 ) ( ref T[][] dest, T2[] src )
1061 {
1062     appendCopy(*(cast(Buffer!(T)[]*) &dest), src);
1063 }
1064 
1065 ///
1066 unittest
1067 {
1068     mstring[] dest;
1069     cstring src = "hello";
1070     appendCopy(dest, src);
1071     test!("==")(dest[0][], "hello");
1072 }
1073 
1074 /*******************************************************************************
1075 
1076     Removes and returns (via the 'popped' out parameter) the last element in an
1077     array. If the provided array is empty, the function returns false.
1078 
1079     Template params:
1080         T = type of array element
1081 
1082     Params:
1083         buffer = buffer to pop an element from
1084         popped = popped element (if array contains > 0 elements)
1085 
1086     Returns:
1087         true if an element was popped
1088 
1089 *******************************************************************************/
1090 
1091 public bool pop ( T ) ( ref Buffer!(T) buffer, out T popped )
1092 {
1093     if (buffer.length == 0)
1094         return false;
1095 
1096     popped = *buffer[buffer.length - 1];
1097     buffer.length = buffer.length - 1;
1098     return true;
1099 }
1100 
1101 ///
1102 unittest
1103 {
1104     auto buffer = createBuffer("something");
1105     char elem;
1106     test(pop(buffer, elem));
1107     test!("==")(buffer[], "somethin"[]);
1108     test!("==")(elem, 'g');
1109 }
1110 
1111 public bool pop ( T ) ( ref T[] array, out T popped )
1112 {
1113     return pop (* cast(Buffer!(T)*) &array, popped);
1114 }
1115 
1116 unittest
1117 {
1118     auto buffer = "something".dup;
1119     char elem;
1120     test(pop(buffer, elem));
1121     test!("==")(buffer, "somethin"[]);
1122     test!("==")(elem, 'g');
1123 }
1124 
1125 /*******************************************************************************
1126 
1127     Removes elements from the middle of a buffer, maintaining the order of the
1128     remaining elements by shifting them left using memmove.
1129 
1130     Template params:
1131         T = type of buffer element
1132 
1133     Params:
1134         buffer = buffer to remove from
1135         index = position in buffer from which to remove elements
1136         remove_elems = number of elements to remove, defaults to one
1137 
1138     Returns:
1139         slice of buffer
1140 
1141 *******************************************************************************/
1142 
1143 public T[] removeShift ( T ) ( ref Buffer!(T) buffer, size_t index,
1144     size_t remove_elems = 1 )
1145 {
1146     if ( remove_elems == 0 )
1147         return buffer[];
1148 
1149     verify(index < buffer.length, "removeShift: index is >= buffer length");
1150     verify(index + remove_elems - 1 < buffer.length,
1151         "removeShift: end is >= buffer length");
1152 
1153     auto end = index + remove_elems - 1;
1154     auto shift_elems = (buffer.length - end) - 1;
1155 
1156     if ( shift_elems )
1157     {
1158         // shift after elements to the left
1159         void* src = buffer[].ptr + end + 1;
1160         void* dst = buffer[].ptr + index;
1161         size_t num = T.sizeof * shift_elems;
1162 
1163         memmove(dst, src, num);
1164     }
1165 
1166     // adjust buffer length
1167     buffer.length = buffer.length - remove_elems;
1168     return buffer[];
1169 }
1170 
1171 ///
1172 unittest
1173 {
1174     auto arr = createBuffer("something");
1175     removeShift(arr, 3, 4);
1176     test!("==")(arr[], "somng"[]);
1177 }
1178 
1179 public T[] removeShift ( T ) ( ref T[] buffer, size_t index,
1180     size_t remove_elems = 1 )
1181 {
1182     return removeShift(*cast(Buffer!(T)*) &buffer, index, remove_elems);
1183 }
1184 
1185 unittest
1186 {
1187     mstring arr = "something".dup;
1188     removeShift(arr, 3, 4);
1189     test!("==")(arr, "somng"[]);
1190 }
1191 
1192 /*******************************************************************************
1193 
1194     Inserts elements into the middle of a buffer, maintaining the order of the
1195     existing elements by shifting them right using memmove.
1196 
1197     Template params:
1198         T = type of buffer element
1199 
1200     Params:
1201         buffer = buffer to insert into
1202         index = position in buffer at which to insert new elements
1203         insert_elems = number of elements to insert, defaults to one
1204 
1205     Returns:
1206         slice of buffer
1207 
1208 *******************************************************************************/
1209 
1210 public T[] insertShift ( T ) ( ref Buffer!(T) buffer, size_t index,
1211     size_t insert_elems = 1)
1212 {
1213     verify(index <= buffer.length, "insertShift: index is > buffer length");
1214 
1215     if ( insert_elems == 0 )
1216         return buffer[];
1217 
1218     auto shift_elems = buffer.length - index;
1219 
1220     // adjust buffer length
1221     buffer.length = buffer.length + insert_elems;
1222 
1223     // shift required elements one place to the right
1224     if ( shift_elems )
1225     {
1226         void* src = buffer[].ptr + index;
1227         void* dst = buffer[].ptr + index + insert_elems;
1228         size_t num = T.sizeof * shift_elems;
1229         memmove(dst, src, num);
1230     }
1231 
1232     return buffer[];
1233 }
1234 
1235 ///
1236 unittest
1237 {
1238     auto arr = createBuffer("something");
1239     insertShift(arr, 2, 2);
1240     test!("==")(arr[], "somemething");
1241 }
1242 
1243 public T[] insertShift ( T ) ( ref T[] buffer, size_t index,
1244     size_t insert_elems = 1)
1245 {
1246     return insertShift(* cast(Buffer!(T)*) &buffer, index, insert_elems);
1247 }
1248 
1249 /*******************************************************************************
1250 
1251     Sorts array and removes all value duplicates.
1252 
1253     Template params:
1254         T    = type of array element
1255         sort = true: do array.sort first; false: array is already sorted
1256 
1257     Params:
1258         array = array to clean from duplicate values
1259 
1260     Returns:
1261         result
1262 
1263 *******************************************************************************/
1264 
1265 public T[] uniq ( T, bool sort = true ) ( T[] array )
1266 {
1267     if (array.length)
1268     {
1269         size_t n = 0;
1270 
1271         static if (sort)
1272         {
1273             .sort(array);
1274         }
1275 
1276         T item = array[n];
1277 
1278         foreach (element; array)
1279         {
1280             if (element != item)
1281             {
1282                 array[++n] = element;
1283                 item       = element;
1284             }
1285         }
1286 
1287         return array[0 .. n + 1];
1288     }
1289     else
1290     {
1291         return array;
1292     }
1293 }
1294 
1295 ///
1296 unittest
1297 {
1298     int[] arr = [ 42, 43, 43, 42, 2 ];
1299     auto slice = uniq(arr);
1300     test!("==")(slice, [ 2, 42, 43 ]);
1301     test!("==")(arr, [ 2, 42, 43, 43, 43 ]);
1302 }
1303 
1304 unittest
1305 {
1306     auto buffer = createBuffer([ 42, 43, 43, 42, 2 ]);
1307     auto slice = uniq(buffer[]);
1308     test!("==")(slice, [ 2, 42, 43 ][]);
1309     test!("==")(buffer[], [ 2, 42, 43, 43, 43 ][]);
1310 }
1311 
1312 /*******************************************************************************
1313 
1314     Sorts array and checks if it contains at least one duplicate.
1315 
1316     Template params:
1317         T    = type of array element
1318         sort = true: do array.sort first; false: array is already sorted
1319 
1320     Params:
1321         array = array to clean from duplicate values
1322 
1323     Returns:
1324         true if array contains a duplicate or false if not. Returns false if
1325         array is empty.
1326 
1327 *******************************************************************************/
1328 
1329 public bool containsDuplicate ( T, bool sort = true ) ( T[] array )
1330 {
1331     return !!findDuplicates!(T, sort)(
1332         array,
1333         delegate int(ref size_t index, ref T element) {return true;}
1334     );
1335 }
1336 
1337 /*******************************************************************************
1338 
1339     Sorts array and iterates over each array element that compares equal to the
1340     previous element.
1341 
1342     To just check for the existence of duplicates it's recommended to make
1343     found() return true (or some other value different from 0) to stop the
1344     iteration after the first duplicate.
1345 
1346     To assert array has no duplicates or throw an exception if it has, put the
1347     `assert(false)` or `throw ...` in `found()`:
1348     ---
1349         int[] array;
1350 
1351         findDuplicates(array,
1352                        (ref size_t index, ref int element)
1353                        {
1354                            throw new Exception("array contains duplicates");
1355                            return 0; // pacify the compiler
1356                        });
1357     ---
1358 
1359     Template params:
1360         T    = type of array element
1361         sort = true: do array.sort first; false: array is already sorted
1362 
1363     Params:
1364         array = array to clean from duplicate values
1365         found = `foreach`/`opApply()` style delegate, called with the index and
1366                 the value of each array element that is equal to the previous
1367                 element, returns 0 to continue or a value different from 0 to
1368                 stop iteration.
1369 
1370     Returns:
1371         - 0 if no duplicates were found so `found()` was not called or
1372         - 0 if `found()` returned 0 on each call or
1373         - the non-zero value returned by `found()` on the last call.
1374 
1375 *******************************************************************************/
1376 
1377 public int findDuplicates ( T, bool sort = true )
1378     ( T[] array, scope int delegate ( ref size_t index, ref T element ) found )
1379 {
1380     if (array.length)
1381     {
1382         static if (sort)
1383         {
1384             .sort(array);
1385         }
1386 
1387         foreach (i, ref element; array[1 .. $])
1388         {
1389             if (element == array[i])
1390             {
1391                 auto j = i + 1;
1392                 if (int x = found(j, element))
1393                 {
1394                     return x;
1395                 }
1396             }
1397         }
1398     }
1399 
1400     return 0;
1401 }
1402 
1403 unittest
1404 {
1405     uint n_iterations, n_duplicates;
1406 
1407     struct Found
1408     {
1409         int    value;
1410         size_t index;
1411     }
1412 
1413     Found[8] found;
1414     int[8] array;
1415     alias findDuplicates!(typeof(array[0]), false) fd;
1416 
1417     int found_cb ( ref size_t index, ref int element )
1418     in
1419     {
1420         test(n_iterations);
1421     }
1422     do
1423     {
1424         test(index);
1425         test(index < array.length);
1426         test(array[index] == array[index - 1]);
1427         found[n_duplicates++] = Found(element, index);
1428         return !--n_iterations;
1429     }
1430 
1431     array[] = 2;
1432 
1433     test(containsDuplicate(array));
1434 
1435     for (uint i = 1; i < array.length; i++)
1436     {
1437         n_iterations = i;
1438         n_duplicates = 0;
1439         int ret = fd(array, &found_cb);
1440         test(ret);
1441         test(n_duplicates == i);
1442     }
1443 
1444     n_iterations = array.length;
1445     n_duplicates = 0;
1446     {
1447         int ret = fd(array, &found_cb);
1448         test(!ret);
1449     }
1450     test(n_duplicates == array.length - 1);
1451 
1452     array[] = [2, 3, 5, 7, 11, 13, 17, 19];
1453 
1454     test(!containsDuplicate(array));
1455 
1456     n_duplicates = 0;
1457 
1458     for (uint i = 1; i <= array.length; i++)
1459     {
1460         n_iterations = i;
1461         int ret = fd(array, &found_cb);
1462         test(!ret);
1463         test(!n_duplicates);
1464     }
1465 
1466     n_iterations = array.length;
1467     array[] = 2;
1468     {
1469         n_duplicates = 0;
1470         int ret = fd(array[0 .. 0], &found_cb);
1471         test(!ret);
1472         test(!n_duplicates);
1473         ret = fd(array[0 .. 1], &found_cb);
1474         test(!ret);
1475         test(!n_duplicates);
1476         ret = fd(array[0 .. 2], &found_cb);
1477         test(!ret);
1478         test(n_duplicates == 1);
1479     }
1480 }
1481 
1482 /*******************************************************************************
1483 
1484     Moves all elements from array which match the exclusion criterum
1485     represented by exclude to the back of array so that the elements that do not
1486     match this criterium are in the front.
1487 
1488     array is modified in-place, the order of the elements may change.
1489 
1490     exclude is expected to be callable (function or delegate), accepting exactly
1491     one T argument and returning an integer (bool, (u)int, (u)short or (u)long).
1492     It is called with the element in question and should return true if that
1493     element should moved to the back or false if to the front.
1494 
1495     Params:
1496         array   = array to move values matching the exclusion criterum to the
1497                   back
1498         exclude = returns true if the element matches the exclusion criterium
1499 
1500     Returns:
1501         the index of the first excluded elements in array. This element and all
1502         following ones matched the exclusion criterum; all elements before it
1503         did not match.
1504         0 indicates that all elements matched the exclusion criterium
1505         and array.length that none matched.
1506 
1507         This allows the calling code to keep only the non-excluded items
1508         by calling: `arr.length = filterInPlace(arr, filterFunc);`
1509 
1510     Out:
1511         The returned index is at most array.length.
1512 
1513 *******************************************************************************/
1514 
1515 public size_t filterInPlace ( T, Exclude ) ( T[] array, Exclude exclude )
1516 out (end)
1517 {
1518     assert(end <= array.length, "result index out of bounds");
1519 }
1520 do
1521 {
1522     static assert (
1523         isCallableType!(Exclude),
1524         "exclude is expected to be callable, not \"" ~ Exclude.stringof ~ '"'
1525     );
1526 
1527     static assert(
1528         is(ParametersOf!(Exclude) == AliasSeq!(T)),
1529         "exclude is expected to accept one " ~ T.stringof ~ " argument"
1530     );
1531 
1532     static assert(
1533         is(ReturnTypeOf!(Exclude) : long),
1534         "the return type of exclude is expected to be an integer type"
1535     );
1536 
1537     return filterInPlaceCore(
1538         array.length,
1539         (size_t i)
1540         {
1541             return !!exclude(array[i]);
1542         },
1543         (size_t i, size_t j)
1544         {
1545             typeid(T).swap(&array[i], &array[j]);
1546         }
1547     );
1548 }
1549 
1550 unittest
1551 {
1552     auto arr = "something".dup;
1553     filterInPlace(arr, (char c) { return c / 2; });
1554 }
1555 
1556 /*******************************************************************************
1557 
1558     Moves all elements in an array which match the exclusion criterum
1559     represented by exclude to the back of array so that the elements that do not
1560     match this criterium are in the front.
1561 
1562     array is modified in-place, the order of the elements may change.
1563 
1564     exclude is called with the index of the element in question and should
1565     return true if array[index] should moved to the back or false if to the
1566     front. At the time exclude is called, the order of the array elements may
1567     have changed so exclude should index the same array instance this function
1568     is working on (i.e. not a copy).
1569 
1570     Params:
1571         length  = array length
1572         exclude = returns true if array)[index] matches the exclusion
1573                   criterium
1574         swap    = swaps array[i] and array[j]
1575 
1576     Returns:
1577         the index of the first excluded elements in the array. This element
1578         and all following ones matched the exclusion criterum; all elements
1579         before it did not match.
1580         length indicates that all elements matched the exclusion criterium and
1581         0 that none matched.
1582 
1583 *******************************************************************************/
1584 
1585 private size_t filterInPlaceCore ( size_t length,
1586     scope bool delegate ( size_t index ) exclude,
1587     scope void delegate ( size_t i, size_t j ) swap )
1588 out (end)
1589 {
1590     assert(end <= length, "result length out of bounds");
1591 }
1592 do
1593 {
1594     for (size_t i = 0; i < length; i++)
1595     {
1596         if (exclude(i))
1597         {
1598             length--;
1599 
1600             while (length > i)
1601             {
1602                 if (exclude(length))
1603                 {
1604                     length--;
1605                 }
1606                 else
1607                 {
1608                     swap(i, length);
1609                     break;
1610                 }
1611             }
1612         }
1613     }
1614 
1615     return length;
1616 }
1617 
1618 /******************************************************************************/
1619 
1620 unittest
1621 {
1622     uint[] array = [2, 3, 5, 8, 13, 21, 34, 55, 89, 144];
1623     size_t end;
1624 
1625     /***************************************************************************
1626 
1627         Returns true if array[0 .. end] contains n or false if not.
1628 
1629     ***************************************************************************/
1630 
1631     bool inIncluded ( uint n )
1632     {
1633         foreach (element; array[0 .. end])
1634         {
1635             if (element == n) return true;
1636         }
1637 
1638         return false;
1639     }
1640 
1641     /***************************************************************************
1642 
1643         Returns true if array[end .. $] contains n or false if not.
1644 
1645     ***************************************************************************/
1646 
1647     bool inExcluded ( uint n )
1648     {
1649         foreach (element; array[end .. $])
1650         {
1651             if (element == n) return true;
1652         }
1653 
1654         return false;
1655     }
1656 
1657     /***************************************************************************
1658 
1659         Returns true n is even or false if n is odd.
1660 
1661     ***************************************************************************/
1662 
1663     bool even ( uint n )
1664     {
1665         return !(n & 1);
1666     }
1667 
1668     end = .filterInPlace(array, &even);
1669     test(end == 6);
1670     test(inIncluded(3));
1671     test(inIncluded(5));
1672     test(inIncluded(13));
1673     test(inIncluded(21));
1674     test(inIncluded(55));
1675     test(inIncluded(89));
1676     test(inExcluded(2));
1677     test(inExcluded(8));
1678     test(inExcluded(34));
1679     test(inExcluded(144));
1680 
1681     array    = [2, 4, 6];
1682     end = .filterInPlace(array, &even);
1683     test(!end);
1684     test(inExcluded(2));
1685     test(inExcluded(4));
1686     test(inExcluded(6));
1687 
1688     array    = [8];
1689     end = .filterInPlace(array, &even);
1690     test(!end);
1691     test(array[end] == 8);
1692 
1693     array    = [12345];
1694     end = .filterInPlace(array, &even);
1695     test(end == array.length);
1696     test(array[0] == 12345);
1697 
1698     array = [1, 2, 4, 6];
1699     end = .filterInPlace(array, &even);
1700     test(end == 1);
1701     test(array[0] == 1);
1702     test(inExcluded(2));
1703     test(inExcluded(4));
1704     test(inExcluded(6));
1705 
1706     array = [1, 3, 5, 7];
1707     end = .filterInPlace(array, &even);
1708     test(end == array.length);
1709     test(inIncluded(1));
1710     test(inIncluded(3));
1711     test(inIncluded(5));
1712     test(inIncluded(7));
1713 
1714     array = [1, 2, 5, 7];
1715     end = .filterInPlace(array, &even);
1716     test(end == 3);
1717     test(inIncluded(1));
1718     test(inIncluded(5));
1719     test(inIncluded(7));
1720     test(inExcluded(2));
1721 }
1722 
1723 /*******************************************************************************
1724 
1725     Shuffles the elements of array in-place.
1726 
1727     Params:
1728         array = array with elements to shuffle
1729         rand  = random number generator whose generated numbers must have range
1730                 ]-1..0] or [0..1[, will be invoked array.length - 1 times
1731 
1732     Returns:
1733         shuffled array
1734 
1735 *******************************************************************************/
1736 
1737 public T[] shuffle ( T ) ( T[] array, lazy double rand )
1738 {
1739     auto result = shuffle(
1740         array,
1741         (size_t i) { return cast(size_t) (fabs(rand) * (i + 1)); }
1742     );
1743     return result;
1744 }
1745 
1746 ///
1747 unittest
1748 {
1749     int[] arr = [ 1, 2, 3, 4 ];
1750     auto random_generator = () { return 0.42; }; // not proven by the dice roll
1751     shuffle(arr, random_generator());
1752 }
1753 
1754 /*******************************************************************************
1755 
1756     Shuffles the elements of array in-place.
1757 
1758     Params:
1759         array     = array with elements to shuffle
1760         new_index = returns the new index for the array element whose index is
1761                     currently i. i is guaranteed to be in the range
1762                     [1 .. array.length - 1]; the returned index should be in the
1763                     range [0 .. i] and must be in range [0 .. array.length - 1].
1764 
1765     Returns:
1766         shuffled array
1767 
1768 *******************************************************************************/
1769 
1770 public T[] shuffle ( T ) ( T[] array, scope size_t delegate ( size_t i ) new_index )
1771 {
1772     for (auto i = array.length? array.length - 1 : 0; i; i--)
1773     {
1774         auto j = new_index(i);
1775         auto tmp = array[i];
1776         array[i] = array[j];
1777         array[j] = tmp;
1778     }
1779 
1780     return array;
1781 }
1782 
1783 ///
1784 unittest
1785 {
1786     int[] arr = [ 1, 2, 3, 4 ];
1787     int[] orig = arr.dup;
1788     auto modified = shuffle(arr, (size_t i) { return i; });
1789     test!("==")(modified, orig);
1790 }
1791 
1792 /******************************************************************************
1793 
1794     Resets each elements of array to its initial value.
1795 
1796     T.init must consist only of zero bytes.
1797 
1798     Params:
1799         array = array to clear elements
1800 
1801     Returns:
1802         array with cleared elements
1803 
1804  ******************************************************************************/
1805 
1806 public T[] clear ( T ) ( T[] array )
1807 {
1808     verify(isClearable!(T), T.stringof ~ ".init contains a non-zero byte so " ~
1809         (T[]).stringof ~ " cannot be simply cleared");
1810 
1811     memset(array.ptr, 0, array.length * array[0].sizeof);
1812 
1813     return array;
1814 }
1815 
1816 unittest
1817 {
1818     auto arr = [ 1, 2, 3 ];
1819     clear(arr);
1820 }
1821 
1822 /******************************************************************************
1823 
1824     Checks if T.init consists only of zero bytes so that a T[] array can be
1825     cleared by clear().
1826 
1827     Returns:
1828         true if a T[] array can be cleared by clear() or false if not.
1829 
1830  ******************************************************************************/
1831 
1832 bool isClearable ( T ) ( )
1833 {
1834     static immutable size_t n = T.sizeof;
1835 
1836     T init;
1837 
1838     ubyte[n] zero_data;
1839 
1840     return (cast (void*) &init)[0 .. n] == zero_data;
1841 }
1842 
1843 unittest
1844 {
1845     auto x = isClearable!(double);
1846 }
1847 
1848 /*******************************************************************************
1849 
1850     Selects the kth element of an array as defined by the given predicate.
1851 
1852     Notes:
1853         -> Uses the Quickselect selection algorithm
1854            (http://en.wikipedia.org/wiki/Quickselect)
1855         -> Typically, Quickselect is used to select the kth smallest element
1856            of an array, but this function can also be used to select elements
1857            ordered in any fashion, as defined by the given predicate.
1858         -> The array elements may be reordered during the selection process.
1859         -> The following would be true if the selection happens successfully
1860            (i.e. if no exception is thrown):
1861                * the kth element in the array as defined by the given
1862                  predicate would have been moved to index 'k'.
1863                * All elements before index 'k' are guaranteed to be passed by
1864                  the predicate compared to element 'k' (i.e. the predicate
1865                  would return true) whereas all elements after index 'k' are
1866                  guaranteed to not be passed by the predicate compared to
1867                  element 'k' (i.e.  the predicate would return false).  This
1868                  means that, if the kth smallest element is being selected,
1869                  then all elements before the kth smallest element would be
1870                  lesser than it and all elements after the kth smallest
1871                  element would be greater than or equal to it. However, no
1872                  guarantees are made about the sorting order of the elements
1873                  before/after the kth smallest element. In other words,
1874                  unordered partial sorting of the array will take place.
1875         -> The result is defined only if all values in the array are ordered
1876            (unordered values like floating-point NaNs could result in
1877            undefined behaviour).
1878 
1879     Params:
1880         arr  = the array being worked upon.
1881         k    = the order statistic being looked for (starting from zero). In
1882                particular, there should be 'k' elements in the array for which
1883                the predicate will return true.
1884         pred = predicate used for array element comparisons. Takes two array
1885                elements to be compared and returns true/false based upon the
1886                comparison.
1887                (defaults to a comparison using "<" if no predicate is given)
1888 
1889     Returns:
1890         the index of the kth element in the array as defined by the ordering
1891         predicate.
1892 
1893     Throws:
1894         new Exception if input array is empty.
1895 
1896 *******************************************************************************/
1897 
1898 size_t select ( T, Pred = DefaultPredicates.IsLess!(T) )
1899     ( T[] arr, size_t k, Pred pred = Pred.init )
1900 {
1901     /* For best results, i.e. to achieve O(n) performance from
1902      * Quickselect, it is recommended to choose a random initial pivot
1903      * value. But for now, for the sake of simplicity, the selection
1904      * function is called with its default value of zero which causes
1905      * the first value in the array to be treated as the initial pivot
1906      * value. */
1907 
1908     quickselect(arr, k, pred);
1909 
1910     if ( k >= arr.length )
1911     {
1912         k = arr.length - 1;
1913     }
1914 
1915     return k;
1916 }
1917 
1918 /*******************************************************************************
1919 
1920     Same as `select` with two changes:
1921 
1922     1. An additional input parameter:
1923            initial_pivot_index = the array index at which the first pivot
1924                                  value can be found. In theory, the pivot
1925                                  value can be chosen at random, but
1926                                  making an intelligent first guess close
1927                                  to the expected kth smallest (or
1928                                  largest) element is a good idea as that
1929                                  reduces the number of iterations needed
1930                                  to close-in on the target value
1931                                  (defaults to zero).
1932     2. The return value:
1933            returns the kth element in the array as defined by the
1934            ordering predicate.
1935 
1936 *******************************************************************************/
1937 
1938 T quickselect ( T, Pred = DefaultPredicates.IsLess!(T) )
1939     ( T[] arr, size_t k, Pred pred = Pred.init, size_t initial_pivot_index = 0 )
1940 {
1941     static assert (isCallableType!(Pred));
1942 
1943     /*
1944      * Partitions a range of elements within an array based on a pivot
1945      * value.
1946      *
1947      * At the end of the partition function in a typical Quickselect
1948      * example, the range of elements being worked upon would be
1949      * modified such that all elements before the pivot element will be
1950      * smaller than it, while all elements after the pivot element will
1951      * be greater than it. This function is capable of this typical
1952      * behaviour as well as the opposite behaviour depending upon the
1953      * given predicate.
1954      *
1955      * Params:
1956      *  arr         = array being worked upon.
1957      *  left        = leftmost index of the range of elements to
1958      *                partition.
1959      *  right       = rightmost index of the range of elements to
1960      *                partition.
1961      *  pivot_index = index of the pivot value to be used.
1962      *  pred        = predicate used for array element comparisons.
1963      *                Takes two array elements to be compared and
1964      *                returns true/false based upon the comparison.
1965      *
1966      * Returns:
1967      *  the new index to which the pivot value has moved.
1968      */
1969 
1970     static size_t partition( T[] arr, size_t left, size_t right,
1971                       size_t pivot_index, Pred pred )
1972     {
1973         if( left >= right )
1974         {
1975             return left;
1976         }
1977 
1978         if( pivot_index < left || pivot_index > right )
1979         {
1980             pivot_index = left;
1981         }
1982 
1983         auto pivot_value = arr[pivot_index];
1984 
1985         // Move the pivot value to the last index in the current range.
1986 
1987         if( pivot_index != right )
1988         {
1989             /* Note that the following line will result in a
1990              * compile-time error in D1 if 'Elem' is a static array.
1991              * This is because D1 does not allow assignment to a static
1992              * array. */
1993 
1994             arr[pivot_index] = arr[right];
1995             arr[right] = pivot_value;
1996         }
1997 
1998         auto store_index = left;
1999 
2000         for( auto i = left; i < right; ++i )
2001         {
2002             if( pred(arr[i], pivot_value) )
2003             {
2004                 if( i != store_index )
2005                 {
2006                     typeid(T).swap(&arr[i], &arr[store_index]);
2007                 }
2008 
2009                 ++store_index;
2010             }
2011         }
2012 
2013         // Move the pivot value from the last index to its rightful
2014         // place.
2015 
2016         if( store_index != right )
2017         {
2018             arr[right] = arr[store_index];
2019             arr[store_index] = pivot_value;
2020         }
2021 
2022         return store_index;
2023     }
2024 
2025     if( arr.length == 0 )
2026     {
2027         throw new Exception("Zero-length arrays are not supported");
2028     }
2029 
2030     if( arr.length == 1 )
2031     {
2032         return arr[0];
2033     }
2034 
2035     /* The initial pivot index must be a valid array index. */
2036 
2037     if( initial_pivot_index >= arr.length )
2038     {
2039         initial_pivot_index = 0;
2040     }
2041 
2042     /* One cannot have "the fifth largest element in an array" if the
2043      * array contains only three elements. In such a case, 'k' is set to
2044      * the largest valid index of the array. */
2045 
2046     if( k >= arr.length )
2047     {
2048         k = arr.length - 1;
2049     }
2050 
2051     /*
2052      * Important Note:
2053      * ---------------
2054      *     This function uses 'left' and 'right' markers to define a
2055      *     range of elements in the array being searched. At first
2056      *     glance, this may seem unnecessary as D's slicing operations
2057      *     could be used to inspect a range of elements in an array.
2058      *     However, the QuickSelect algorithm works in such a way that
2059      *     the kth element in the array will move to index 'k' of the
2060      *     original array at the end of computation. This makes it
2061      *     necessary for us to maintain the original length of the
2062      *     array, and not use slices.
2063      */
2064 
2065     /* The selection process works on a constantly reducing range of
2066      * elements within the given array, with the search range being
2067      * halved in each iteration. To begin with, the range is set to the
2068      * entire array. */
2069 
2070     size_t left = 0;
2071     size_t right = arr.length - 1;
2072 
2073     size_t pivot_index = initial_pivot_index;
2074 
2075     while( 1 )
2076     {
2077         pivot_index = partition(arr, left, right, pivot_index, pred);
2078 
2079         if( pivot_index == k )
2080         {
2081             /* The kth element in the array is the current pivot. */
2082 
2083             break;
2084         }
2085         else if( pivot_index > k )
2086         {
2087             /* The kth element is before the current pivot, so restrict
2088              * further searching to the first half of the current range
2089              * by shortening the range from the right. */
2090 
2091             right = pivot_index - 1;
2092             pivot_index = right;
2093         }
2094         else
2095         {
2096             /* The kth element is after the current pivot, so restrict
2097              * further searching to the second half of the current range
2098              * by shortening the range from the left. */
2099 
2100             left = pivot_index + 1;
2101             pivot_index = left;
2102         }
2103     }
2104 
2105     return arr[pivot_index];
2106 }
2107 
2108 version (unittest)
2109 {
2110     void verifySelect ( T, istring file = __FILE__, int line = __LINE__ )
2111         ( T[] buf, size_t k, T expected_value )
2112     {
2113         auto t = new NamedTest(file ~ ":" ~ line.stringof);
2114         auto kth_element_index = select(buf, k);
2115 
2116         t.test!("<")(kth_element_index, buf.length);
2117         t.test!("==")(buf[kth_element_index], expected_value);
2118 
2119         /* Confirm that unordered partial sorting of the array has also
2120          * happened as expected. */
2121 
2122         if( k > buf.length )
2123             k = buf.length;
2124 
2125         foreach (cur; buf[0 .. k])
2126             t.test!("<=")(cur, expected_value);
2127 
2128         foreach (cur; buf[k .. $])
2129             test!(">=")(cur, expected_value);
2130     }
2131 
2132 }
2133 
2134 unittest
2135 {
2136     testThrown!(Exception)(select((int[]).init, 0));
2137 
2138     verifySelect("efedcaabca".dup, 5, 'c');
2139 
2140     verifySelect(['x'], 0, 'x');
2141     verifySelect([42], 10, 42);
2142 
2143     verifySelect([7, 3, 4, 1, 9], 0, 1);
2144     verifySelect([7, 3, 4, 1, 9], 1, 3);
2145     verifySelect([7, 3, 4, 1, 9], 2, 4);
2146     verifySelect([7, 3, 4, 1, 9], 3, 7);
2147     verifySelect([7, 3, 4, 1, 9], 4, 9);
2148     verifySelect([7, 3, 4, 1, 9], 5, 9);
2149 
2150     verifySelect([7.4, 3.57, 4.2, 1.23, 3.56], 1, 3.56);
2151 
2152     struct Person
2153     {
2154         istring name;
2155         int age;
2156     }
2157 
2158     Person a = Person("Gautam", 18);
2159     Person b = Person("Tom",    52);
2160     Person c = Person("George", 53);
2161     Person d = Person("Arnold", 67);
2162 
2163     bool person_age_predicate( Person p1, Person p2 )
2164     {
2165         return p1.age < p2.age;
2166     }
2167 
2168     Person[] buf = [a, b, c, d];
2169 
2170     auto kth_element_index = select(buf, 0, &person_age_predicate);
2171     test!("==")(buf[kth_element_index].name, "Gautam");
2172 
2173     kth_element_index = select(buf, 2, &person_age_predicate);
2174     test!("==")(buf[kth_element_index].name, "George");
2175 
2176     test!("==")(quickselect([7, 3, 4, 1, 9][], 1), 3);
2177 
2178     bool greater_than_predicate( int a, int b )
2179     {
2180         return a > b;
2181     }
2182 
2183     test!("==")(quickselect([7, 3, 4, 1, 9][], 1, &greater_than_predicate), 7);
2184     test!("==")(quickselect([7, 3, 4, 1][], 1, &greater_than_predicate, 2), 4);
2185 }