std.algorithm.mutation

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

Copyright

Andrei Alexandrescu 2008-.

License

Boost License 1.0.

Authors

Andrei Alexandrescu

Source: std/algorithm/mutation.d

var areCopyCompatibleArrays

tmpl isValidIntegralTuple move

enum SwapStrategy

fn bringToFront bringToFrontImpl copy fill initializeAll move moveAll moveAllImpl moveEmplace moveEmplaceAll moveEmplaceImpl moveEmplaceSome moveImpl moveSome moveSomeImpl remove removeImpl removePredStable removePredString removePredUnstable removeStable removeStableString removeUnstable reverse strip stripLeft stripRight swap swapAt swapFront swapRanges trustedMoveImpl uninitializedFill

Types 1

enumSwapStrategy

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.

unstableAllows freely swapping of elements as long as the output satisfies the algorithm's requirements.

semistableIn algorithms partitioning ranges in two, preserve relative ordering of elements only to the left of the partition point.

stablePreserve the relative ordering of elements to the largest extent allowed by the algorithm's requirements.

Functions 43

size_t bringToFront(InputRange,  ForwardRange)(InputRange front,  ForwardRange back) if (isInputRange!InputRange &&  isForwardRange!ForwardRange)

`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...

private fn

size_t bringToFrontImpl(InputRange,  ForwardRange)(InputRange front,  ForwardRange back) if (isInputRange!InputRange &&  isForwardRange!ForwardRange)

TargetRange copy(SourceRange,  TargetRange)(SourceRange source,  TargetRange target) if (isInputRange!SourceRange &&  isOutputRange!(TargetRange,  ElementType!SourceRange))

Copies the content of `source` into `target` and returns the remaining (unfilled) part of `target`.

void fill(Range,  Value)(auto  ref  Range range,  auto  ref  Value value) if ((isInputRange!Range &&  is(typeof(range.front =  value))  ||
     isSomeChar!Value &&  is(typeof(range[]  =  value))))

Assigns `value` to each element of input range `range`.

void fill(InputRange,  ForwardRange)(InputRange range,  ForwardRange filler) if (isInputRange!InputRange
    && (isForwardRange!ForwardRange
    || (isInputRange!ForwardRange &&  isInfinite!ForwardRange))
     &&  is(typeof(InputRange.init.front =  ForwardRange.init.front)))

ditto

void initializeAll(Range)(Range range) if (isInputRange!Range &&  hasLvalueElements!Range &&  hasAssignableElements!Range
    &&  __traits(compiles,  {  static  ElementType!Range _;  }))

Initializes all elements of `range` with their `.init` value. Assumes that the elements of the range are uninitialized.

fnvoid initializeAll(Range)(Range range) if (is(Range == char[]) || is(Range == wchar[]))ditto

fnvoid move(T)(ref T source, ref T target) if (__traits(compiles, target = T.init))Moves `source` into `target`, via a destructive copy when necessary.

fnT move(T)(return scope ref T source)Ditto

private fnvoid moveImpl(T)(ref scope T target, ref return scope T source)

private fnT moveImpl(T)(ref return scope T source)

private fnT trustedMoveImpl(T)(ref return scope T source) @trusted

private fnvoid moveEmplaceImpl(T)(ref scope T target, ref return scope T source)

fnvoid moveEmplace(T)(ref T source, ref T target) pure @systemSimilar to move but assumes `target` is uninitialized. This is more efficient because `source` can be blitted over `target` without destroying or initializing it first.

InputRange2 moveAll(InputRange1,  InputRange2)(InputRange1 src,  InputRange2 tgt) if (isInputRange!InputRange1 &&  isInputRange!InputRange2
        &&  is(typeof(move(src.front,  tgt.front))))

Calls `move(a, b)` for each element `a` in `src` and the corresponding element `b` in `tgt`, in increasing order.

InputRange2 moveEmplaceAll(InputRange1,  InputRange2)(InputRange1 src,  InputRange2 tgt) if (isInputRange!InputRange1 &&  isInputRange!InputRange2
        &&  is(typeof(moveEmplace(src.front,  tgt.front))))

@systemSimilar to moveAll but assumes all elements in `tgt` are uninitialized. Uses moveEmplace to move elements from `src` over elements from `tgt`.

private fn

InputRange2 moveAllImpl(alias  moveOp,  InputRange1,  InputRange2)(
     ref  InputRange1 src,  ref  InputRange2 tgt)

Tuple!(InputRange1,  InputRange2) moveSome(InputRange1,  InputRange2)(InputRange1 src,  InputRange2 tgt) if (isInputRange!InputRange1 &&  isInputRange!InputRange2
        &&  is(typeof(move(src.front,  tgt.front))))

Calls `move(a, b)` for each element `a` in `src` and the corresponding element `b` in `tgt`, in increasing order, stopping when either range has been exhausted.

Tuple!(InputRange1,  InputRange2) moveEmplaceSome(InputRange1,  InputRange2)(InputRange1 src,  InputRange2 tgt) if (isInputRange!InputRange1 &&  isInputRange!InputRange2
        &&  is(typeof(move(src.front,  tgt.front))))

@systemSame as moveSome but assumes all elements in `tgt` are uninitialized. Uses moveEmplace to move elements from `src` over elements from `tgt`.

private fn

Tuple!(InputRange1,  InputRange2) moveSomeImpl(alias  moveOp,  InputRange1,  InputRange2)(
     ref  InputRange1 src,  ref  InputRange2 tgt)

Range remove(SwapStrategy s =  SwapStrategy.stable,  Range,  Offset ...)(Range range,  Offset offset) if (Offset.length >=  1 &&  allSatisfy!(isValidIntegralTuple,  Offset))

Eliminates elements at given offsets from `range` and returns the shortened range.

Range remove(SwapStrategy s =  SwapStrategy.stable,  Range,  Offset ...)(Range range,  Offset offset) if (Offset.length >=  1 && !allSatisfy!(isValidIntegralTuple,  Offset))

deprecated Use of non-integral tuples is deprecated. Use remove(tuple(start, end).

ditto

private fnauto removeImpl(SwapStrategy s, Range, Offset...)(Range range, Offset offset)

private fnRange removeUnstable(Range, Offset...)(Range range, Offset offset)

private fnRange removeStable(Range, Offset...)(Range range, Offset offset)

private fnRange removeStableString(Range, Offset...)(Range range, Offset offsets)

fnRange remove(alias pred, SwapStrategy s = SwapStrategy.stable, Range)(Range 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 ...

private fnRange removePredUnstable(alias pred, Range)(Range range)

private fnRange removePredStable(alias pred, Range)(Range range)

private fnRange removePredString(alias pred, SwapStrategy s = SwapStrategy.stable, Range)(Range range)

Range reverse(Range)(Range r) if (isBidirectionalRange!Range &&
        (hasSwappableElements!Range ||
         (hasAssignableElements!Range &&  hasLength!Range &&  isRandomAccessRange!Range)  ||
         (isNarrowString!Range &&  isAssignable!(ElementType!Range))))

Reverses `r` in-place. Performs `r.length / 2` evaluations of `swap`. UTF sequences consisting of multiple code units are preserved properly.

Range strip(Range,  E)(Range range,  E element) if (isBidirectionalRange!Range &&  is(typeof(range.front ==  element) :  bool))

The strip group of functions allow stripping of either leading, trailing, or both leading and trailing elements.

fnRange strip(alias pred, Range)(Range range) if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool))ditto

Range stripLeft(Range,  E)(Range range,  E element) if (isInputRange!Range &&  is(typeof(range.front ==  element) :  bool))

ditto

fnRange stripLeft(alias pred, Range)(Range range) if (isInputRange!Range && is(typeof(pred(range.front)) : bool))ditto

Range stripRight(Range,  E)(Range range,  E element) if (isBidirectionalRange!Range &&  is(typeof(range.back ==  element) :  bool))

ditto

Range stripRight(alias  pred,  Range)(Range range) if (isBidirectionalRange!Range &&  is(typeof(pred(range.back)) :  bool))

ditto

fnvoid swap(T)(ref T lhs, ref T rhs) if (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.

fnvoid swap(T)(ref T lhs, ref T rhs) if (isBlitAssignable!T && !is(typeof(lhs.proxySwap(rhs)))) @trusted pure nothrow @nogcditto

fnvoid swapAt(R)(auto ref R r, size_t i1, size_t i2)Swaps two elements in-place of a range `r`, specified by their indices `i1` and `i2`.

private fnvoid swapFront(R1, R2)(R1 r1, R2 r2) if (isInputRange!R1 && isInputRange!R2)

Tuple!(InputRange1,  InputRange2) swapRanges(InputRange1,  InputRange2)(InputRange1 r1,  InputRange2 r2) if (hasSwappableElements!InputRange1 &&  hasSwappableElements!InputRange2
    &&  is(ElementType!InputRange1 ==  ElementType!InputRange2))

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...

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 ...

Variables 1

private enumvarareCopyCompatibleArrays = isArray!T1 && isArray!T2 && is(typeof(T2.init[] = T1.init[]))

Templates 2

tmplmove(T) if (!__traits(compiles, imported!"std.traits".lvalueOf!T = T.init))

ditto

Functions

void move(ref T source, ref T target)

tmplisValidIntegralTuple(T)