D Programming Language 2.0

- Comments
- D
- Search
- Home

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));

Copyright © 1999-2007 by Digital Mars, All Rights Reserved | Page generated by Ddoc.