D Programming Language
Improve this page Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone. Page wiki View or edit the community-maintained wiki page associated with this page.

# std.algorithm.mutation

This is a submodule of std.algorithm. It contains generic mutation algorithms.

Cheat Sheet

Function Name | Description
--- | ---

bringToFront | If a = [1, 2, 3] and b = [4, 5, 6, 7], bringToFront(a, b) leaves a = [4, 5, 6] and b = [7, 1, 2, 3].
copy | Copies a range to another. If a = [1, 2, 3] and b = new int[5], then copy(a, b) leaves b = [1, 2, 3, 0, 0] and returns b[3 .. $].
fill | Fills a range with a pattern, e.g., if a = new int[3], then fill(a, 4) leaves a = [4, 4, 4] and fill(a, [3, 4]) leaves a = [3, 4, 3].
initializeAll | If a = [1.2, 3.4], then initializeAll(a) leaves a = [double.init, double.init].
move | move(a, b) moves a into b. move(a) reads a destructively.
moveAll | Moves all elements from one range to another.
moveSome | Moves as many elements as possible from one range to another.
remove | Removes elements from a range in-place, and returns the shortened range.
reverse | If a = [1, 2, 3], reverse(a) changes it to [3, 2, 1].
strip | Strips all leading and trailing elements equal to a value, or that satisfy a predicate. If a = [1, 1, 0, 1, 1], then strip(a, 1) and strip!(e => e == 1)(a) returns [0].
stripLeft | Strips all leading elements equal to a value, or that satisfy a predicate. If a = [1, 1, 0, 1, 1], then stripLeft(a, 1) and stripLeft!(e => e == 1)(a) returns [0, 1, 1].
stripRight | Strips all trailing elements equal to a value, or that satisfy a predicate. If a = [1, 1, 0, 1, 1], then stripRight(a, 1) and stripRight!(e => e == 1)(a) returns [1, 1, 0].
swap | Swaps two values.
swapRanges | Swaps all elements of two ranges.
uninitializedFill | Fills a range (assumed uninitialized) with a value.

License:
Boost License 1.0.
Authors:
Andrei Alexandrescu

Source: std/algorithm/mutation.d

size_t bringToFront(Range1, Range2)(Range1 front, Range2 back) if (isInputRange!Range1 && isForwardRange!Range2);
  The bringToFront function has considerable flexibility and usefulness. It can rotate elements in one buffer left or right, swap buffers of equal length, and even move elements across disjoint buffers of different types and different lengths.
  bringToFront takes two ranges front and back, which may be of different types. Considering the concatenation of front and back one unified range, bringToFront rotates that unified range such that all elements in back are brought to the beginning of the unified range. The relative ordering of elements in front and back, respectively, remains unchanged.

  Performs Ο(max(front.length, back.length)) evaluations of swap.

  Preconditions: Either front and back are disjoint, or back is reachable from front and front is not reachable from back.

  Returns:
  The number of elements brought to the front, i.e., the length of back.
  See Also:
  STL's rotate
  Examples:
  The simplest use of bringToFront is for rotating elements in a buffer. For example:

      auto arr = [4, 5, 6, 7, 1, 2, 3];
      auto p = bringToFront(arr[0 .. 4], arr[4 .. $]);
      assert(p == arr.length - 4);
      assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);

  Examples:
  The front range may actually "step over" the back range. This is very useful with forward ranges that cannot compute comfortably right-bounded subranges like arr[0 .. 4] above. In the example below, r2 is a right subrange of r1.

      import std.algorithm.comparison : equal;
      import std.container : SList;

      auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3);
      auto r1 = list[];
      auto r2 = list[]; popFrontN(r2, 4);
      assert(equal(r2, [ 1, 2, 3 ]));
      bringToFront(r1, r2);
      assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ]));

  Examples:
  Elements can be swapped across ranges of different types:

      import std.algorithm.comparison : equal;
      import std.container : SList;

      auto list = SList!(int)(4, 5, 6, 7);
      auto vec = [ 1, 2, 3 ];
      bringToFront(list[], vec);
      assert(equal(list[], [ 1, 2, 3, 4 ]));
      assert(equal(vec, [ 5, 6, 7 ]));

Range2 copy(Range1, Range2)(Range1 source, Range2 target) if (isInputRange!Range1 && isOutputRange!(Range2, ElementType!Range1));
  Copies the content of source into target and returns the remaining (unfilled) part of target.

  Preconditions: target shall have enough room to accomodate source.

  See Also:
  STL's copy
  Examples:

      int[] a = [ 1, 5 ];
      int[] b = [ 9, 8 ];
      int[] buf = new int[a.length + b.length + 10];
      auto rem = copy(a, buf);    // copy a into buf
      rem = copy(b, rem);         // copy b into remainder of buf
      assert(buf[0 .. a.length + b.length] == [1, 5, 9, 8]);
      assert(rem.length == 10);   // unused slots in buf

  Examples:
  As long as the target range elements support assignment from source range elements, different types of ranges are accepted:

      float[] src = [ 1.0f, 5 ];
      double[] dest = new double[src.length];
      copy(src, dest);

  Examples:
  To copy at most n elements from a range, you may want to use std.range.take:

      import std.range;
      int[] src = [ 1, 5, 8, 9, 10 ];
      auto dest = new int[3];
      copy(take(src, dest.length), dest);
      assert(dest[0 .. $] == [ 1, 5, 8 ]);

  Examples:
  To copy just those elements from a range that satisfy a predicate you may want to use filter:

      import std.algorithm.iteration : filter;
      int[] src = [ 1, 5, 8, 9, 10, 1, 2, 0 ];
      auto dest = new int[src.length];
      auto rem = copy(src.filter!(a => (a & 1) == 1), dest);
      assert(dest[0 .. $ - rem.length] == [ 1, 5, 9, 1 ]);

  Examples:
  std.range.retro can be used to achieve behavior similar to STL's copy_backward':

      import std.algorithm, std.range;
      int[] src = [1, 2, 4];
      int[] dest = [0, 0, 0, 0, 0];
      copy(src.retro, dest.retro);
      assert(dest == [0, 0, 1, 2, 4]);

void fill(Range, Value)(Range range, Value value) if (isInputRange!Range && is(typeof(range.front = value)));
  Assigns value to each element of input range range.
  Parameters:

  Range range | An input range that exposes references to its elements and has assignable elements
  Value value | Assigned to each element of range

  See Also:
  uninitializedFill initializeAll
  Examples:

      int[] a = [ 1, 2, 3, 4 ];
      fill(a, 5);
      assert(a == [ 5, 5, 5, 5 ]);

void fill(Range1, Range2)(Range1 range, Range2 filler) if (isInputRange!Range1 && (isForwardRange!Range2 || isInputRange!Range2 && isInfinite!Range2) && is(typeof(Range1.init.front = Range2.init.front)));
  Fills range with a pattern copied from filler. The length of range does not have to be a multiple of the length of filler. If filler is empty, an exception is thrown.
  Parameters:

  Range1 range | An input range that exposes references to its elements and has assignable elements.
  Range2 filler | The forward range representing the fill pattern.

  Examples:

      int[] a = [ 1, 2, 3, 4, 5 ];
      int[] b = [ 8, 9 ];
      fill(a, b);
      assert(a == [ 8, 9, 8, 9, 8 ]);

void initializeAll(Range)(Range range) if (isInputRange!Range && hasLvalueElements!Range && hasAssignableElements!Range);
  Initializes all elements of range with their .init value. Assumes that the elements of the range are uninitialized.
  Parameters:

  Range range | An input range that exposes references to its elements and has assignable elements

  See Also:
  fill uninitializeFill

  Example:

      struct S { ... }
      S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
      initializeAll(s);
      assert(s == [ 0, 0, 0, 0, 0 ]);

void move(T)(ref T source, ref T target);
T move(T)(ref T source);
  Moves source into target via a destructive copy.
  Parameters:

  T source | Data to copy. If a destructor or postblit is defined, it is reset to its .init value after it is moved into target. Note that data with internal pointers that point to itself cannot be moved, and will trigger an assertion failure.
  T target | Where to copy into. The destructor, if any, is invoked before the copy is performed.

Range2 moveAll(Range1, Range2)(Range1 src, Range2 tgt) if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(move(src.front, tgt.front))));
  For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b).

  Preconditions: walkLength(src) <= walkLength(tgt). An exception will be thrown if this condition does not hold, i.e., there is not enough room in tgt to accommodate all of src.

  Parameters:

  Range1 src | An input range with movable elements.
  Range2 tgt | An input range with elements that elements from src can be moved into.

  Returns:
  The leftover portion of tgt after all elements from src have been moved.
Tuple!(Range1, Range2) moveSome(Range1, Range2)(Range1 src, Range2 tgt) if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(move(src.front, tgt.front))));
  For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b). Stops when either src or tgt have been exhausted.
  Parameters:

  Range1 src | An input range with movable elements.
  Range2 tgt | An input range with elements that elements from src can be moved into.

  Returns:
  The leftover portions of the two ranges after one or the other of the ranges have been exhausted.
enum SwapStrategy: int;
  Defines the swapping strategy for algorithms that need to swap elements in a range (such as partition and sort). The strategy concerns the swapping of elements that are not the core concern of the algorithm. For example, consider an algorithm that sorts [ "abc", "b", "aBc" ] according to toUpper(a) < toUpper(b). That algorithm might choose to swap the two equivalent strings "abc" and "aBc". That does not affect the sorting since both [ "abc", "aBc", "b" ] and [ "aBc", "abc", "b" ] are valid outcomes.
  Some situations require that the algorithm must NOT ever change the relative ordering of equivalent elements (in the example above, only [ "abc", "aBc", "b" ] would be the correct result). Such algorithms are called stable. If the ordering algorithm may swap equivalent elements discretionarily, the ordering is called unstable.

  Yet another class of algorithms may choose an intermediate tradeoff by being stable only on a well-defined subrange of the range. There is no established terminology for such behavior; this library calls it semistable.

  Generally, the stable ordering strategy may be more costly in time and/or space than the other two because it imposes additional constraints. Similarly, semistable may be costlier than unstable. As (semi-)stability is not needed very often, the ordering algorithms in this module parameterized by SwapStrategy all choose SwapStrategy.unstable as the default.
  unstable
    Allows freely swapping of elements as long as the output satisfies the algorithm's requirements.
  semistable
    In algorithms partitioning ranges in two, preserve relative ordering of elements only to the left of the partition point.
  stable
    Preserve the relative ordering of elements to the largest extent allowed by the algorithm's requirements.
Range remove(SwapStrategy s = SwapStrategy.stable, Range, Offset...)(Range range, Offset offset) if (s != SwapStrategy.stable && isBidirectionalRange!Range && hasLvalueElements!Range && hasLength!Range && Offset.length >= 1);
  Eliminates elements at given offsets from range and returns the shortened range. In the simplest call, one element is removed.

      int[] a = [ 3, 5, 7, 8 ];
      assert(remove(a, 1) == [ 3, 7, 8 ]);
      assert(a == [ 3, 7, 8, 8 ]);

  In the case above the element at offset 1 is removed and remove returns the range smaller by one element. The original array has remained of the same length because all functions in std.algorithm only change content, not topology. The value 8 is repeated because std.algorithm.move was invoked to move elements around and on integers move simply copies the source to the destination. To replace a with the effect of the removal, simply assign a = remove(a, 1). The slice will be rebound to the shorter array and the operation completes with maximal efficiency.

  Multiple indices can be passed into remove. In that case, elements at the respective indices are all removed. The indices must be passed in increasing order, otherwise an exception occurs.

      int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
      assert(remove(a, 1, 3, 5) ==
          [ 0, 2, 4, 6, 7, 8, 9, 10 ]);

  (Note how all indices refer to slots in the original array, not in the array as it is being progressively shortened.) Finally, any combination of integral offsets and tuples composed of two integral offsets can be passed in.

      int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
      assert(remove(a, 1, tuple(3, 5), 9) == [ 0, 2, 6, 7, 8, 10 ]);

  In this case, the slots at positions 1, 3, 4, and 9 are removed from the array. The tuple passes in a range closed to the left and open to the right (consistent with built-in slices), e.g. tuple(3, 5) means indices 3 and 4 but not 5.

  If the need is to remove some elements in the range but the order of the remaining elements does not have to be preserved, you may want to pass SwapStrategy.unstable to remove.

      int[] a = [ 0, 1, 2, 3 ];
      assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]);

  In the case above, the element at slot 1 is removed, but replaced with the last element of the range. Taking advantage of the relaxation of the stability requirement, remove moved elements from the end of the array over the slots to be removed. This way there is less data movement to be done which improves the execution time of the function.

  The function remove works on any forward range. The moving strategy is (listed from fastest to slowest):
  - If s == SwapStrategy.unstable && isRandomAccessRange!Range && hasLength!Range && hasLvalueElements!Range, then elements are moved from the end of the range into the slots to be filled. In this case, the absolute minimum of moves is performed.
  - Otherwise, if s == SwapStrategy.unstable && isBidirectionalRange!Range && hasLength!Range && hasLvalueElements!Range, then elements are still moved from the end of the range, but time is spent on advancing between slots by repeated calls to range.popFront.
  - Otherwise, elements are moved incrementally towards the front of range; a given element is never moved several times, but more elements are moved than in the previous cases.
Range remove(alias pred, SwapStrategy s = SwapStrategy.stable, Range)(Range range) if (isBidirectionalRange!Range && hasLvalueElements!Range);
  Reduces the length of the bidirectional range range by removing elements that satisfy pred. If s = SwapStrategy.unstable, elements are moved from the right end of the range over the elements to eliminate. If s = SwapStrategy.stable (the default), elements are moved progressively to front such that their relative order is preserved. Returns the filtered range.
  Examples:

      static immutable base = [1, 2, 3, 2, 4, 2, 5, 2];

      int[] arr = base[].dup;

      // using a string-based predicate
      assert(remove!("a == 2")(arr) == [ 1, 3, 4, 5 ]);

      // The original array contents have been modified,
      // so we need to reset it to its original state.
      // The length is unmodified however.
      arr[] = base[];

      // using a lambda predicate
      assert(remove!(a => a == 2)(arr) == [ 1, 3, 4, 5 ]);

void reverse(Range)(Range r) if (isBidirectionalRange!Range && !isRandomAccessRange!Range && hasSwappableElements!Range);
void reverse(Range)(Range r) if (isRandomAccessRange!Range && hasLength!Range);
  Reverses r in-place. Performs r.length / 2 evaluations of swap.
  See Also:
  STL's reverse
  Examples:

      int[] arr = [ 1, 2, 3 ];
      reverse(arr);
      assert(arr == [ 3, 2, 1 ]);

void reverse(Char)(Char[] s) if (isNarrowString!(Char[]) && !is(Char == const) && !is(Char == immutable));
  Reverses r in-place, where r is a narrow string (having elements of type char or wchar). UTF sequences consisting of multiple code units are preserved properly.
  Examples:

      char[] arr = "hello\U00010143\u0100\U00010143".dup;
      reverse(arr);
      assert(arr == "\U00010143\u0100\U00010143olleh");

Range strip(Range, E)(Range range, E element) if (isBidirectionalRange!Range && is(typeof(range.front == element) : bool));
Range strip(alias pred, Range)(Range range) if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool));
Range stripLeft(Range, E)(Range range, E element) if (isInputRange!Range && is(typeof(range.front == element) : bool));
Range stripLeft(alias pred, Range)(Range range) if (isInputRange!Range && is(typeof(pred(range.front)) : bool));
Range stripRight(Range, E)(Range range, E element) if (isBidirectionalRange!Range && is(typeof(range.back == element) : bool));
Range stripRight(alias pred, Range)(Range range) if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool));
  The strip group of functions allow stripping of either leading, trailing, or both leading and trailing elements.
  The stripLeft function will strip the front of the range, the stripRight function will strip the back of the range, while the strip function will strip both the front and back of the range.

  Note that the strip and stripRight functions require the range to be a BidirectionalRange range.

  All of these functions come in two varieties: one takes a target element, where the range will be stripped as long as this element can be found. The other takes a lambda predicate, where the range will be stripped as long as the predicate returns true.
  Examples:
  Strip leading and trailing elements equal to the target element.

      assert("  foobar  ".strip(' ') == "foobar");
      assert("00223.444500".strip('0') == "223.4445");
      assert("ëëêéüŗōpéêëë".strip('ë') == "êéüŗōpéê");
      assert([1, 1, 0, 1, 1].strip(1) == [0]);
      assert([0.0, 0.01, 0.01, 0.0].strip(0).length == 2);

  Examples:
  Strip leading and trailing elements while the predicate returns true.

      assert("  foobar  ".strip!(a => a == ' ')() == "foobar");
      assert("00223.444500".strip!(a => a == '0')() == "223.4445");
      assert("ëëêéüŗōpéêëë".strip!(a => a == 'ë')() == "êéüŗōpéê");
      assert([1, 1, 0, 1, 1].strip!(a => a == 1)() == [0]);
      assert([0.0, 0.01, 0.5, 0.6, 0.01, 0.0].strip!(a => a < 0.4)().length == 2);

  Examples:
  Strip leading elements equal to the target element.

      assert("  foobar  ".stripLeft(' ') == "foobar  ");
      assert("00223.444500".stripLeft('0') == "223.444500");
      assert("ůůűniçodêéé".stripLeft('ů') == "űniçodêéé");
      assert([1, 1, 0, 1, 1].stripLeft(1) == [0, 1, 1]);
      assert([0.0, 0.01, 0.01, 0.0].stripLeft(0).length == 3);

  Examples:
  Strip leading elements while the predicate returns true.

      assert("  foobar  ".stripLeft!(a => a == ' ')() == "foobar  ");
      assert("00223.444500".stripLeft!(a => a == '0')() == "223.444500");
      assert("ůůűniçodêéé".stripLeft!(a => a == 'ů')() == "űniçodêéé");
      assert([1, 1, 0, 1, 1].stripLeft!(a => a == 1)() == [0, 1, 1]);
      assert([0.0, 0.01, 0.10, 0.5, 0.6].stripLeft!(a => a < 0.4)().length == 2);

  Examples:
  Strip trailing elements equal to the target element.

      assert("  foobar  ".stripRight(' ') == "  foobar");
      assert("00223.444500".stripRight('0') == "00223.4445");
      assert("ùniçodêéé".stripRight('é') == "ùniçodê");
      assert([1, 1, 0, 1, 1].stripRight(1) == [1, 1, 0]);
      assert([0.0, 0.01, 0.01, 0.0].stripRight(0).length == 3);

  Examples:
  Strip trailing elements while the predicate returns true.

      assert("  foobar  ".stripRight!(a => a == ' ')() == "  foobar");
      assert("00223.444500".stripRight!(a => a == '0')() == "00223.4445");
      assert("ùniçodêéé".stripRight!(a => a == 'é')() == "ùniçodê");
      assert([1, 1, 0, 1, 1].stripRight!(a => a == 1)() == [1, 1, 0]);
      assert([0.0, 0.01, 0.10, 0.5, 0.6].stripRight!(a => a > 0.4)().length == 3);

pure nothrow @nogc @trusted void swap(T)(ref T lhs, ref T rhs) if (isBlitAssignable!T && !is(typeof(lhs.proxySwap(rhs))));
  Swaps lhs and rhs. The instances lhs and rhs are moved in memory, without ever calling opAssign, nor any other function. T need not be assignable at all to be swapped.
  If lhs and rhs reference the same instance, then nothing is done.

  lhs and rhs must be mutable. If T is a struct or union, then its fields must also all be (recursively) mutable.
  Parameters:

  T lhs | Data to be swapped with rhs.
  T rhs | Data to be swapped with lhs.

Tuple!(Range1, Range2) swapRanges(Range1, Range2)(Range1 r1, Range2 r2) if (isInputRange!Range1 && isInputRange!Range2 && hasSwappableElements!Range1 && hasSwappableElements!Range2 && is(ElementType!Range1 == ElementType!Range2));
  Swaps all elements of r1 with successive elements in r2. Returns a tuple containing the remainder portions of r1 and r2 that were not swapped (one of them will be empty). The ranges may be of different types but must have the same element type and support swapping.
  Examples:

      int[] a = [ 100, 101, 102, 103 ];
      int[] b = [ 0, 1, 2, 3 ];
      auto c = swapRanges(a[1 .. 3], b[2 .. 4]);
      assert(c[0].empty && c[1].empty);
      assert(a == [ 100, 2, 3, 103 ]);
      assert(b == [ 0, 1, 101, 102 ]);

void uninitializedFill(Range, Value)(Range range, Value value) if (isInputRange!Range && hasLvalueElements!Range && is(typeof(range.front = value)));
  Initializes each element of range with value. Assumes that the elements of the range are uninitialized. This is of interest for structs that define copy constructors (for all other types, fill and uninitializedFill are equivalent).
  Parameters:

  Range range | An input range that exposes references to its elements and has assignable elements
  Value value | Assigned to each element of range

  See Also:
  fill initializeAll

  Example:

      struct S { ... }
      S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
      uninitializedFill(s, 42);
      assert(s == [ 42, 42, 42, 42, 42 ]);

Andrei Alexandrescu 2008-. | Page generated by Ddoc on Tue Mar 24 14:30:34 2015