www.digitalmars.com

D Programming Language 2.0

Last update Tue Nov 27 20:24:58 2007

std.algorithm

This module is a port of a growing fragment of the algorithm header in Alexander Stepanov's Standard Template Library.

Author:
Andrei Alexandrescu

void swap(T)(ref T lhs, ref T rhs);
Swaps lhs and rhs.

template partition(alias compare)
Implements C.A.R. Hoare's partition algorithm. Specifically, reorders the range [left, right) such that everything strictly smaller (according to the predicate compare) than *mid is to the left of the returned pointer, and everything else is at the right of the returned pointer.

Precondition:
left == mid && mid == right || left <= mid && mid < right.

Returns:
If left == right, returns left. Otherwise, return a value p such that the following three conditions are simultaneously true:
  1. *p == *mid
  2. compare(*p1, *p) for all p1 in [left, p)
  3. !compare(*p2, *p) for all p2 in [p, right)


Example:
auto a = [3, 3, 2].dup;
p = partition!(less)(a.ptr, a.ptr, a.ptr + a.length);
assert(p == a.ptr + 1 && a == [2, 3, 3]);


template partition(T)


T partition(T left, T mid, T right);


template nthElement(alias compare)
Reorders the range [b, e) such that nth points to the element that would fall there if the range were fully sorted. Effectively, it finds the nth smallest (according to compare) element in the range [b, e).

Example:
auto v = ([ 25, 7, 9, 2, 0, 5, 21 ]).dup;
auto n = 4;
nthElement!(less)(v.ptr, v.ptr + n, v.ptr + v.length);
assert(v[n] == 9);


template nthElement(T)


void nthElement(T b, T nth, T e);


void reverse(T)(T range);
Reverses range in-place.

template sort(alias comp)
Sorts a random-access range according to predicate comp, which must be a function name.

Example:
int[] array = ([ 1, 2, 3, 4 ]).dup;
sort!(greater)(array);
assert(array == [ 4, 3, 2, 1 ]);
bool myComp(int x, int y) { return x < y; }
sort!(myComp)(array);
assert(array == [ 1, 2, 3, 4 ]);


template sort(invariant(char)[] comp)
Sorts a random-access range according to predicate comp, expressed as a string. The string can use the names "a" and "b" for the two elements being compared.

Example:
int[] array = ([ 1, 2, 3, 4 ]).dup;
sort!("a > b")(array);
assert(array == [ 4, 3, 2, 1 ]);


template isSorted(alias comp)
Checks whether a random-access range is sorted according to the comparison operation comp.

Example:
int[] arr = ([4, 3, 2, 1]).dup;
assert(!isSorted!(less)(arr));
sort!(less)(arr);
assert(isSorted!(less)(arr));