std.algorithm - D Programming Language - Digital Mars

D Programming Language 2.0

- Comments
- D
- Search
- Home

Last update Wed Sep 2 00:11:52 2009

# std.algorithm

Implements algorithms oriented mainly towards processing of sequences. Some functions are semantic equivalents or supersets of those found in the <algorithm> header in Alexander Stepanov's Standard Template Library for C++.

Author:
Andrei Alexandrescu

Note:
Many functions in this module are parameterized with a function or a predicate . The predicate may be passed either as a function name, a delegate name, a functor name, or a compile-time string. The string may consist of any legal D expression that uses the symbol a (for unary functions) or the symbols a and b (for binary functions). These names will NOT interfere with other homonym symbols in user code because they are evaluated in a different context. The default for all binary comparison predicates is "a == b" for unordered operations and "a < b" for ordered operations.

Example:

    int[] a = ...;
    static bool greater(int a, int b)
    {
        return a > b;
    }
    sort!(greater)(a);  // predicate as alias
    sort!("a > b")(a);  // predicate as string
                        // (no ambiguity with array name)
    sort(a);            // no predicate, "a < b" is implicit

template map(fun...)
  Implements the homonym function (also known as transform) present in many languages of functional flavor. The call map!(fun)(range) returns a range of which elements are obtained by applying fun(x) left to right for all x in range. The original ranges are not changed. Evaluation is done lazily. The range returned by map caches the last value such that evaluating front multiple times does not result in multiple calls to fun.

  Example:

      int[] arr1 = [ 1, 2, 3, 4 ];
      int[] arr2 = [ 5, 6 ];
      auto squares = map!("a * a")(chain(arr1, arr2));
      assert(equal(squares, [ 1, 4, 9, 16, 25, 36 ]));

  Multiple functions can be passed to map. In that case, the element type of map is a tuple containing one element for each function.

  Example:

      auto arr1 = [ 1, 2, 3, 4 ];
      foreach (e; map!("a + a", "a * a")(arr1))
      {
          writeln(e.field[0], " ", e.field[1]);
      }

template reduce(fun...)
  Implements the homonym function (also known as accumulate, compress, inject, or foldl) present in various programming languages of functional flavor. The call reduce!(fun)(seed, range) first assigns seed to an internal variable result, also called the accumulator. Then, for each element x in range, result = fun(result, x) gets evaluated. Finally, result is returned. The one-argument version reduce!(fun)(range) works similarly, but it uses the first element of the range as the seed (the range must be non-empty).

  Many aggregate range operations turn out to be solved with reduce quickly and easily. The example below illustrates reduce's remarkable power and flexibility.

  Example:

      int[] arr = [ 1, 2, 3, 4, 5 ];
      // Sum all elements
      auto sum = reduce!("a + b")(0, arr);
      assert(sum == 15);

      // Compute the maximum of all elements
      auto largest = reduce!(max)(arr);
      assert(largest == 5);

      // Compute the number of odd elements
      auto odds = reduce!("a + (b & 1)")(0, arr);
      assert(odds == 3);

      // Compute the sum of squares
      auto ssquares = reduce!("a + b * b")(0, arr);
      assert(ssquares == 55);

      // Chain multiple ranges into seed
      int[] a = [ 3, 4 ];
      int[] b = [ 100 ];
      auto r = reduce!("a + b")(chain(a, b));
      assert(r == 107);

      // Mixing convertible types is fair game, too
      double[] c = [ 2.5, 3.0 ];
      auto r1 = reduce!("a + b")(chain(a, b, c));
      assert(r1 == 112.5);

  Multiple functions:
  Sometimes it is very useful to compute multiple aggregates in one pass. One advantage is that the computation is faster because the looping overhead is shared. That's why reduce accepts multiple functions. If two or more functions are passed, reduce returns a std.typecons.Tuple object with one member per passed-in function. The number of seeds must be correspondingly increased.

  Example:

      double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
      // Compute minimum and maximum in one pass
      auto r = reduce!(min, max)(a);
      // The type of r is Tuple!(double, double)
      assert(r.field[0] == 2);  // minimum
      assert(r.field[1] == 11); // maximum

      // Compute sum and sum of squares in one pass
      r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
      assert(r.field[0] == 35);  // sum
      assert(r.field[1] == 233); // sum of squares
      // Compute average and standard deviation from the above
      auto avg = r.field[0] / a.length;
      auto stdev = sqrt(r.field[1] / a.length - avg * avg);

void fill(Range, Value)(Range range, Value filler);
  Fills a range with a value.

  Example:

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

void fill(Range1, Range2)(Range1 range, Range2 filler);
  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.

  Example:

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

Filter!(unaryFun!(pred),Range) filter(alias pred, Range)(Range rs);
  Implements the homonym function present in various programming languages of functional flavor. The call filter!(fun)(range) returns a new range only containing elements x in r for which pred(x) is true.

  Example:

      int[] arr = [ 1, 2, 3, 4, 5 ];
      // Sum all elements
      auto small = filter!("a < 3")(arr);
      assert(small == [ 1, 2 ]);
      // In combination with chain() to span multiple ranges
      int[] a = [ 3, -2, 400 ];
      int[] b = [ 100, -101, 102 ];
      auto r = filter!("a > 0")(chain(a, b));
      assert(equals(r, [ 3, 400, 100, 102 ]));
      // Mixing convertible types is fair game, too
      double[] c = [ 2.5, 3.0 ];
      auto r1 = filter!("cast(int) a != a")(chain(c, a, b));
      assert(r1 == [ 2.5 ]);

void move(T)(ref T source, ref T target);
  Moves source into target via a destructive copy. Specifically:
  - If hasAliasing!T is true (see std.traits.hasAliasing), then the representation of source is bitwise copied into target and then source = T.init is evaluated.
  - Otherwise, target = source is evaluated.
  See also std.contracts.pointsTo.

  Preconditions:
  !pointsTo(source, source)

Range2 moveAll(Range1, Range2)(Range1 src, Range2 tgt);
  For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b). Returns the leftover portion of tgt. Throws an exeption if there is not enough room in tgt to acommodate all of src.

  Preconditions:
  walkLength(src) >= walkLength(tgt)

Tuple!(Range1,Range2) moveSome(Range1, Range2)(Range1 src, Range2 tgt);
  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. Returns the leftover portion of the two ranges.

void swap(T)(ref T a, ref T b);
  Swaps lhs and rhs. See also std.contracts.pointsTo.

  Preconditions:
  !pointsTo(lhs, lhs) && !pointsTo(lhs, rhs) && !pointsTo(rhs, lhs) && !pointsTo(rhs, rhs)

struct Splitter(Range,Separator);
Splitter!(Range,Separator) splitter(Range, Separator)(Range r, Separator s);
  Splits a range using another range or an element as a separator. This can be used with any range type, but is most popular with string types.

  Example:

      int[] a = [ 1, 2, 0, 3, 0, 4, 5, 0 ];
      int[][] w = [ [1, 2], [3], [4, 5] ];
      uint i;
      foreach (e; splitter(a)) assert(e == w[i++]);
      assert(i == 3);

struct Uniq(alias pred,R);
Uniq!(pred,Range) uniq(alias pred = "a == b", Range)(Range r);
  Iterates unique consecutive elements of the given range (functionality akin to the uniq system utility). Equivalence of elements is assessed by using the predicate pred, by default "a == b". If the given range is bidirectional, uniq also yields a bidirectional range.

  Example:

      int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
      assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));

struct Group(alias pred,R) if (isInputRange!(R));
Group!(pred,Range) group(alias pred = "a == b", Range)(Range r);
  Similarly to uniq, group iterates unique consecutive elements of the given range. The element type is Tuple!(ElementType!R, uint) because it includes the count of equivalent elements seen. Equivalence of elements is assessed by using the predicate pred, by default "a == b".

  Group is an input range if R is an input range, and a forward range in all other cases.

  Example:

      int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
      assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
          tuple(4, 3u), tuple(5, 1u) ][]));

FindResult!(Range,Ranges) find(alias pred = "a == b", Range, Ranges...)(Range haystack, Ranges needles);
struct BoyerMooreFinder(alias pred,Range);
BoyerMooreFinder!(binaryFun!(pred),Range) boyerMooreFinder(alias pred = "a == b", Range)(Range needle);
  Generalized routine for finding one or more needles into a haystack. Some or all of haystack and needles may be structured in various ways, which translates in the speed of find. The predicate pred is used throughout to compare elements. By default, elements are compared for equality.

  Parameters:

  haystack | The target of the search. Must be an input range . If any of needles is a range with elements comparable to elements in haystack, then haystack must be a forward range such that the search can backtrack.
  needles | One or more items to search for. Each of needles must be either comparable to one element in haystack, or be itself a forward range with elements comparable with elements in haystack.

  Returns:
  - If needles.length == 1, returns haystack advanced such that needles[0] is a prefix of it (if no such position exists, returns an empty range).
  - If needles.length > 1, returns a tuple containing haystack positioned as above and also the 1-based index of the matching element in needles (0 if none of needles matched, 1 if needles[0] matched, 2 if needles[1] matched...).

  The relationship between haystack and needles simply means that one can e.g. search for individual ints, or arrays of ints, in an array of ints. In addition, if elements are individually comparable, searches of heterogeneous types are allowed as well: a double[] can be searched for an int or a short[], and conversely a long can be searched for a float or a double[]. This makes for efficient searches without the need to coerce one side of the comparison into the other's side type.

  Example:

      int[] a = [ 1, 4, 2, 3 ];
      assert(find(a, 4) == [ 4, 2, 3 ]);
      assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]);
      assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2));
      // Mixed types allowed if comparable
      assert(find(a, 5, [ 1.2, 3.5 ], 2.0, [ 1 ]) == tuple([ 2, 3 ], 3));

  The complexity of the search is Ο(haystack.length * max(needles.length)). (For needles that are individual items, length is considered to be 1.) The strategy used in searching several subranges at once maximizes cache usage by moving in haystack as few times as possible.

  BoyerMoore:
  If one or more of the needles has type BoyerMooreFinder, the search for those particular needles is performed by using the Boyer-Moore algorithm. In this case haystack must offer random access. The algorithm has an upfront cost but scales sublinearly, so it is most suitable for large sequences. Performs Ο(haystack.length) evaluations of pred in the worst case and Ο(haystack.length / needle.length) evaluations in the best case.

  The BoyerMooreFinder-structured needles, if any, must be placed at the front of the searched items. This is because they will be searched separately, not in lockstep with any other needles. To add Boyer-Moore structure to any of needles, simply wrap it in a boyerMooreFinder call as shown below.

  Example:

      int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
      int[] b = [ 1, 2, 3 ];
      assert(find(a, boyerMooreFinder(b), 1) == tuple([ 1, 2, 3, 4, 5 ], 1));
      assert(find(b, boyerMooreFinder(a)).empty);

  Sorted:
  Searching can be sped up considerably if haystack is already sorted by an ordering predicate less. The speedup can only occur it the following relation between pred and less holds:

  pred(a, b) == (!less(a, b) && !less(b, a))

  The default predicate for find, which is "a == b", and the default predicate for assumeSorted, which is "a < b", already satisfy the relation.

  If the above condition is satisfied, only Ο(log(haystack.length)) steps are needed to position haystack at the beginning of the search. Also, once positioned, the search will continue only as long as haystack and the needle start with equal elements. To inform find that you want to perform a binary search, wrap haystack with a call to std.contracts.assumeSorted. Then find will assume that pred and less are in the right relation and also that haystack is already sorted by less.

  Example:

      int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
      assert(find(assumeSorted(a), 3) == [ 3, 4, 5 ]);
      assert(find(assumeSorted(a), [3, 4]) == [ 3, 4, 5 ]);
      assert(find(assumeSorted(a), [3, 5], [1, 3], 8).empty);

Range find(alias pred, Range)(Range haystack);
  Advances the input range haystack by calling haystack.popFront until either pred(haystack.front), or haystack.empty. Performs Ο(haystack.length) evaluations of pred. See also STL's find_if.

  To find the last element of a bidirectional haystack satisfying pred, call find!(pred)(retro(haystack)). See also std.range.retro.

  Example:

      auto arr = [ 1, 2, 3, 4, 1 ];
      assert(find!("a > 2")(arr) == [ 3, 4, 1 ]);

      // with predicate alias
      bool pred(int x) { return x + 1 > 1.5; }
      assert(find!(pred)(arr) == arr);

enum OpenRight;
  Interval option specifier for until (below) and others.

  no
    Interval is closed to the right (last element included)

  yes
    Interval is open to the right (last element is not included)

struct Until(alias pred,Range,Sentinel) if (isInputRange!(Range));
Until!(pred,Range,Sentinel) until(alias pred = "a == b", Range, Sentinel)(Range range, Sentinel sentinel, OpenRight openRight = OpenRight.yes);
Until!(pred,Range,void) until(alias pred, Range)(Range range, OpenRight openRight = OpenRight.yes);
  Lazily iterates range until value sentinel is found, at which point it stops.

  Example:

      int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
      assert(equal(a.until(7), [1, 2, 4][]));
      assert(equal(a.until(7, OpenRight.no), [1, 2, 4, 7][]));

uint startsWith(alias pred = "a == b", Range, Ranges...)(Range doesThisStart, Ranges withOneOfThese);
  If the range doesThisStart starts with any of the withOneOfThese ranges or elements, returns 1 if it starts with withOneOfThese[0], 2 if it starts with withOneOfThese[1], and so on. If no match, returns 0.

  Example:

      assert(startsWith("abc", ""));
      assert(startsWith("abc", "a"));
      assert(!startsWith("abc", "b"));
      assert(startsWith("abc", 'a', "b") == 1);
      assert(startsWith("abc", "b", "a") == 2);
      assert(startsWith("abc", "a", "a") == 1);
      assert(startsWith("abc", "x", "a", "b") == 2);
      assert(startsWith("abc", "x", "aa", "ab") == 3);
      assert(startsWith("abc", "x", "aaa", "sab") == 0);
      assert(startsWith("abc", "x", "aaa", 'a', "sab") == 3);

uint endsWith(alias pred = "a == b", Range, Ranges...)(Range doesThisEnd, Ranges withOneOfThese);
  The reciprocal of startsWith.

  Example:

      assert(endsWith("abc", ""));
      assert(!endsWith("abc", "b"));
      assert(endsWith("abc", "a", 'c') == 2);
      assert(endsWith("abc", "c", "a") == 1);
      assert(endsWith("abc", "c", "c") == 1);
      assert(endsWith("abc", "x", "c", "b") == 2);
      assert(endsWith("abc", "x", "aa", "bc") == 3);
      assert(endsWith("abc", "x", "aaa", "sab") == 0);
      assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);

Range findAdjacent(alias pred = "a == b", Range)(Range r);
  Advances r until it finds the first two adjacent elements a, b that satisfy pred(a, b). Performs Ο(r.length) evaluations of pred. See also STL's adjacent_find.

  Example:

      int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
      auto r = findAdjacent(a);
      assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]);
      p = findAdjacent!("a < b")(a);
      assert(p == [ 7, 8, 9 ]);

Range1 findAmong(alias pred = "a == b", Range1, Range2)(Range1 seq, Range2 choices);
  Advances seq by calling seq.popFront until either find!(pred)(choices, seq.front) is true, or seq becomes empty. Performs Ο(seq.length * choices.length) evaluations of pred. See also STL's find_first_of.

  Example:

      int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
      int[] b = [ 3, 1, 2 ];
      assert(findAmong(a, b) == begin(a) + 2);
      assert(findAmong(b, a) == begin(b));

Range1 findAmongSorted(alias less = "a < b", Range1, Range2)(Range1 seq, in Range2 choices);
  Finds the first element x in seq that compares equal with some element y in choices (meaning !less(x, y) && !less(y, x)). The choices range is sought by binary search. Consequently choices is assumed to be sorted according to pred, which by default is "a < b". Performs Ο(seq.length * log(choices.length)) evaluations of less.

  To find the last element of seq instead of the first, call findAmongSorted(retro(seq), choices) and compare the result against rEnd(seq). See also std.range.retro.

  Example:

      int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
      int[] b = [ 1, 2, 3 ];
      assert(findAmongSorted(a, b) == begin(a) + 2);
      assert(findAmongSorted(b, a) == end(b));

size_t count(alias pred = "a == b", Range, E)(Range r, E value);
  Counts the number of elements x in r for which pred(x, value) is true. pred defaults to equality. Performs Ο(r.length) evaluations of pred.

  Example:

      int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
      assert(count(a, 2) == 3);
      assert(count!("a > b")(a, 2) == 5);

size_t count(alias pred, Range)(Range r);
  Counts the number of elements x in r for which pred(x) is true. Performs Ο(r.length) evaluations of pred.

  Example:

      int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
      assert(count!("a > 1")(a) == 8);

bool equal(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2);
  Returns true if and only if the two ranges compare equal element for element, according to binary predicate pred. The ranges may have different element types, as long as pred(a, b) evaluates to bool for a in r1 and b in r2. Performs Ο(min(r1.length, r2.length)) evaluations of pred. See also STL's equal.

  Example:

      int[] a = [ 1, 2, 4, 3 ];
      assert(!equal(a, a[1..$]));
      assert(equal(a, a));

      // different types
      double[] b = [ 1., 2, 4, 3];
      assert(!equal(a, b[1..$]));
      assert(equal(a, b));

      // predicated: ensure that two vectors are approximately equal
      double[] c = [ 1.005, 2, 4, 3];
      assert(equal!(approxEqual)(b, c));

MinType!(T1,T2,T) min(T1, T2, T...)(T1 a, T2 b, T xs);
  Returns the minimum of the passed-in values. The type of the result is computed by using std.traits.CommonType.

MaxType!(T1,T2,T) max(T1, T2, T...)(T1 a, T2 b, T xs);
  Returns the maximum of the passed-in values. The type of the result is computed by using std.traits.CommonType.

  Example:

      int a = 5;
      short b = 6;
      double c = 2;
      auto d = max(a, b);
      assert(is(typeof(d) == int));
      assert(d == 6);
      auto e = min(a, b, c);
      assert(is(typeof(e) == double));
      assert(e == 2);

Tuple!(ElementType!(Range),size_t) minCount(alias pred = "a < b", Range)(Range range);
  Returns the minimum element of a range together with the number of occurrences. The function can actually be used for counting the maximum or any other ordering predicate (that's why maxCount is not provided).

  Example:

      int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
      // Minimum is 1 and occurs 3 times
      assert(minCount(a) == tuple(1, 3));
      // Maximum is 4 and occurs 2 times
      assert(minCount!("a > b")(a) == tuple(4, 2));

Range minPos(alias pred = "a < b", Range)(Range range);
  Returns the position of the minimum element of forward range range, i.e. a subrange of range starting at the position of its smallest element and with the same ending as range. The function can actually be used for counting the maximum or any other ordering predicate (that's why maxPos is not provided).

  Example:

      int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
      // Minimum is 1 and first occurs in position 3
      assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]);
      // Maximum is 4 and first occurs in position 2
      assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]);

Tuple!(Range1,Range2) mismatch(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2);
  Sequentially compares elements in r1 and r2 in lockstep, and stops at the first mismatch (according to pred, by default equality). Returns a tuple with the reduced ranges that start with the two mismatched values. Performs Ο(min(r1.length, r2.length)) evaluations of pred. See also STL's mismatch.

  Example:

      int[]    x = [ 1,  5, 2, 7,   4, 3 ];
      double[] y = [ 1., 5, 2, 7.3, 4, 8 ];
      auto m = mismatch(x, y);
      assert(m.field[0] == begin(x) + 3);
      assert(m.field[1] == begin(y) + 3);

enum EditOp;
  Encodes edit operations necessary to transform one sequence into another. Given sequences s (source) and t (target), a sequence of EditOp encodes the steps that need to be taken to convert s into t. For example, if s = "cat" and "cars", the minimal sequence that transforms s into t is: skip two characters, replace 't' with 'r', and insert an 's'. Working with edit operations is useful in applications such as spell-checkers (to find the closest word to a given misspelled word), approximate searches, diff-style programs that compute the difference between files, efficient encoding of patches, DNA sequence analysis, and plagiarism detection.

  none
    Current items are equal; no editing is necessary.

  substitute
    Substitute current item in target with current item in source.

  insert
    Insert current item from the source into the target.

  remove
    Remove current item from the target.

size_t levenshteinDistance(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t);
  Returns the Levenshtein distance between s and t. The Levenshtein distance computes the minimal amount of edit operations necessary to transform s into t. Performs Ο(s.length * t.length) evaluations of equals and occupies Ο(s.length * t.length) storage.

  Example:

      assert(levenshteinDistance("cat", "rat") == 1);
      assert(levenshteinDistance("parks", "spark") == 2);
      assert(levenshteinDistance("kitten", "sitting") == 3);
      // ignore case
      assert(levenshteinDistance!("toupper(a) == toupper(b)")
          ("parks", "SPARK") == 2);

Tuple!(size_t,EditOp[]) levenshteinDistanceAndPath(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t);
  Returns the Levenshtein distance and the edit path between s and t.

  Example:

      string a = "Saturday", b = "Sunday";
      auto p = levenshteinDistanceAndPath(a, b);
      assert(p.field[0], 3);
      assert(equals(p.field[1], "nrrnsnnn"));

Range2 copy(Range1, Range2)(Range1 source, Range2 target);
  Copies the content of source into target and returns the remaining (unfilled) part of target. See also STL's copy. If a behavior similar to STL's copy_backward is needed, use copy(retro(source), retro(target)). See also std.range.retro.

  Example:

      int[] a = [ 1, 5 ];
      int[] b = [ 9, 8 ];
      int[] c = new int[a.length + b.length + 10];
      auto d = copy(b, copy(a, c));
      assert(c[0 .. a.length + b.length] == a ~ b);
      assert(d.length == 10);

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

  Example:

      float[] a = [ 1.0f, 5 ];
      double[] b = new double[a.length];
      auto d = copy(a, b);

  To copy at most n elements from range a to range b, you may want to use copy(take(n, a), b). To copy those elements from range a that satisfy predicate pred to range b, you may want to use copy(filter!(pred)(a), b).

  Example:

      int[] a = [ 1, 5, 8, 9, 10, 1, 2, 0 ];
      auto b = new int[a.length];
      auto c = copy(filter!("(a & 1) == 1")(a), b);
      assert(b[0 .. $ - c.length] == [ 1, 5, 9, 1 ]);

Tuple!(Range1,Range2) swapRanges(Range1, Range2)(Range1 r1, Range2 r2);
  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.

  Example:

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

void reverse(Range)(Range r);
  Reverses r in-place. Performs r.length evaluations of swap. See also STL's reverse.

  Example:

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

size_t bringToFront(Range1, Range2)(Range1 front, Range2 back);
  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.

  The simplest use of bringToFront is for rotating elements in a buffer. For example:

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

  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, list1 is a right subrange of list.

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

  Elements can be swapped across ranges of different types:

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

  Performs Ο(max(front.length, back.length)) evaluations of swap. See also STL's rotate.

  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.

  Example:

      auto arr = [4, 5, 6, 7, 1, 2, 3];
      auto p = rotate(arr, begin(arr) + 4);
      assert(p - begin(arr) == 3);
      assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);

enum SwapStrategy;
  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);
  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, 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, 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);
  Reduces the length of the bidirectional range range by only keeping elements that satisfy pred. If , 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 tail portion of the range that was moved.

  Example:

      int[] a = [ 1, 2, 3, 2, 3, 4, 5, 2, 5, 6 ];
      assert(a[0 .. $ - remove!("a == 2")(a).length] == [ 1, 3, 3, 4, 5, 5, 6 ]);

Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r);
  Partitions a range in two using pred as a predicate. Specifically, reorders the range r = [left, right) using swap such that all elements i for which pred(i) is true come before all elements j for which pred(j) returns false.

  Performs Ο(r.length) (if unstable or semistable) or Ο(r.length * log(r.length)) (if stable) evaluations of less and swap. The unstable version computes the minimum possible evaluations of swap (roughly half of those performed by the semistable version).

  See also STL's partition and stable_partition.

  Returns:
  The right part of r after partitioning.

  If ss == SwapStrategy.stable, partition preserves the relative ordering of all elements a, b in r for which pred(a) == pred(b). If ss == SwapStrategy.semistable, partition preserves the relative ordering of all elements a, b in begin(r) .. p for which pred(a) == pred(b).

  Example:

      auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
      auto arr = Arr.dup;
      static bool even(int a) { return (a & 1) == 0; }
      // Partition a such that even numbers come first
      auto p = partition!(even)(arr);
      // Now arr is separated in evens and odds.
      // Numbers may have become shuffled due to instability
      assert(p == arr.ptr + 5);
      assert(count!(even)(range(begin(arr), p)) == p - begin(arr));
      assert(find!(even)(range(p, end(arr))) == end(arr));

      // Can also specify the predicate as a string.
      // Use 'a' as the predicate argument name
      arr[] = Arr[];
      p = partition!(q{(a & 1) == 0})(arr);
      assert(p == arr.ptr + 5);

      // Now for a stable partition:
      arr[] = Arr[];
      p = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
      // Now arr is [2 4 6 8 10 1 3 5 7 9], and p points to 1
      assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && p == arr.ptr + 5);

      // In case the predicate needs to hold its own state, use a delegate:
      arr[] = Arr[];
      int x = 3;
      // Put stuff greater than 3 on the left
      bool fun(int a) { return a > x; }
      p = partition!(fun, SwapStrategy.semistable)(arr);
      // Now arr is [4 5 6 7 8 9 10 2 3 1] and p points to 2
      assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && p == arr.ptr + 7);

bool isPartitioned(alias pred, Range)(Range r);
  Returns true if r is partitioned according to predicate pred.

  Example:

      int[] r = [ 1, 3, 5, 7, 8, 2, 4, ];
      assert(isPartitioned!("a & 1")(r));

void topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t nth);
  Reorders the range r using swap such that r[nth] refers to the element that would fall there if the range were fully sorted. In addition, it also partitions r such that all elements e1 from r[0] to r[nth] satisfy !less(r[nth], e1), and all elements e2 from r[nth] to r[r.length] satisfy !less(e2, r[nth]). Effectively, it finds the nth smallest (according to less) elements in r. Performs Ο(r.length) (if unstable) or Ο(r.length * log(r.length)) (if stable) evaluations of less and swap. See also STL's nth_element.

  Example:

      int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
      auto n = 4;
      topN!(less)(v, n);
      assert(v[n] == 9);
      // Equivalent form:
      topN!("a < b")(v, n);
      assert(v[n] == 9);

  BUGS:
  Stable topN has not been implemented yet.

void sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r);
  Sorts a random-access range according to predicate less. Performs Ο(r.length * log(r.length)) (if unstable) or Ο(r.length * log(r.length) * log(r.length)) (if stable) evaluations of less and swap. See also STL's sort and stable_sort.

  Example:

      int[] array = [ 1, 2, 3, 4 ];
      // sort in descending order
      sort!("a > b")(array);
      assert(array == [ 4, 3, 2, 1 ]);
      // sort in ascending order
      sort(array);
      assert(array == [ 1, 2, 3, 4 ]);
      // sort with a delegate
      bool myComp(int x, int y) { return x > y; }
      sort!(myComp)(array);
      assert(array == [ 4, 3, 2, 1 ]);
      // Showcase stable sorting
      string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
      sort!("toupper(a) < toupper(b)", SwapStrategy.stable)(words);
      assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);

void schwartzSort(alias transform, alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r);
  Sorts a range using an algorithm akin to the Schwartzian transform, also known as the decorate-sort-undecorate pattern in Python and Lisp. (Not to be confused with the other Schwartz.) This function is helpful when the sort comparison includes an expensive computation. The complexity is the same as that of the corresponding sort, but schwartzSort evaluates transform only r.length times (less than half when compared to regular sorting). The usage can be best illustrated with an example.

  Example:

      uint hashFun(string) { ... expensive computation ... }
      string[] array = ...;
      // Sort strings by hash, slow
      sort!("hashFun(a) < hashFun(b)")(array);
      // Sort strings by hash, fast (only computes arr.length hashes):
      schwartzSort!(hashFun, "a < b")(array);

  The schwartzSort function might require less temporary data and be faster than the Perl idiom or the decorate-sort-undecorate idiom present in Python and Lisp. This is because sorting is done in-place and only minimal extra data (one array of transformed elements) is created.

  To check whether an array was sorted and benefit of the speedup of Schwartz sorting, a function schwartzIsSorted is not provided because the effect can be achieved by calling isSorted!(less)(map!(transform)(r)).

void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t n);
  Reorders the random-access range r such that the range r[0 .. mid] is the same as if the entire r were sorted, and leaves the range r[mid .. r.length] in no particular order. Performs Ο(r.length * log(mid)) evaluations of pred. The implementation simply calls topN!(less, ss)(r, n) and then sort!(less, ss)(r[0 .. n]).

  Example:

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

void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1 lhs, Range2 rhs);
  Sorts the random-access range chain(lhs, rhs) according to predicate less. The left-hand side of the range lhs is assumed to be already sorted; rhs is assumed to be unsorted. The exact strategy chosen depends on the relative sizes of lhs and rhs. Performs Ο(lhs.length + rhs.length * log(rhs.length)) (best case) to Ο((lhs.length + rhs.length) * log(lhs.length + rhs.length)) (worst-case) evaluations of swap.

  Example:

      int[] a = [ 1, 2, 3 ];
      int[] b = [ 4, 0, 6, 5 ];
      completeSort(a, b);
      assert(a == [ 0, 1, 2 ]);
      assert(b == [ 3, 4, 5, 6 ]);

bool isSorted(alias less = "a < b", Range)(Range r);
  Checks whether a forward range is sorted according to the comparison operation less. Performs Ο(r.length) evaluations of less.

  Example:

      int[] arr = [4, 3, 2, 1];
      assert(!isSorted(arr));
      sort(arr);
      assert(isSorted(arr));
      sort!("a > b")(arr);
      assert(isSorted!("a > b")(arr));

void makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index);
void makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index);
  Computes an index for r based on the comparison less. The index is a sorted array of pointers or indices into the original range. This technique is similar to sorting, but it is more flexible because (1) it allows "sorting" of invariant collections, (2) allows binary search even if the original collection does not offer random access, (3) allows multiple indexes, each on a different predicate, and (4) may be faster when dealing with large objects. However, using an index may also be slower under certain circumstances due to the extra indirection, and is always larger than a sorting-based solution because it needs space for the index in addition to the original collection. The complexity is the same as sort's.

  makeIndex overwrites its second argument with the result, but never reallocates it. If the second argument's length is less than that of the range indexed, an exception is thrown.

  The first overload of makeIndex writes to a range containing pointers, and the second writes to a range containing offsets. The first overload requires Range to be a forward range, and the latter requires it to be a random-access range.

  Example:

      immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
      // index using pointers
      auto index1 = new immutable(int)*[arr.length];
      makeIndex!("a < b")(arr, index1);
      assert(isSorted!("*a < *b")(index1));
      // index using offsets
      auto index2 = new size_t[arr.length];
      makeIndex!("a < b")(arr, index2);
      assert(isSorted!
          ((size_t a, size_t b){ return arr[a] < arr[b];})
          (index2));

enum SortOutput;
  Specifies whether the output of certain algorithm is desired in sorted format.

  no
    Don't sort output

  yes
    Sort output

Range lowerBound(alias pred = "a < b", Range, V)(Range r, V value);
  This function assumes that range r consists of a subrange r1 of elements e1 for which pred(e1, value) is true, followed by a subrange r2 of elements e2 for which pred(e2, value) is false. Using this assumption, lowerBound uses binary search to find r1, i.e. the left subrange on which pred is always true. Performs Ο(log(r.length)) evaluations of pred. The precondition is not verified because it would deteriorate function's complexity. It is possible that the types of value and ElementType!(Range) are different, if the predicate accepts them. See also STL's lower_bound.

  Precondition:
  find!(not!(pred))(r, value).length + find!(pred)(retro(r), value).length == r.length

  Example:

      int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
      auto p = lowerBound!("a < b")(a, 4);
      assert(p == [ 0, 1, 2, 3 ]);
      p = lowerBound(a, 4); // uses "a < b" by default
      assert(p == [ 0, 1, 2, 3 ]);

Range upperBound(alias pred = "a < b", Range, V)(Range r, V value);
  This function assumes that range r consists of a subrange r1 of elements e1 for which pred(value, e1) is false, followed by a subrange r2 of elements e2 for which pred(value, e2) is true. (Note the differences in subrange definition and argument order for pred compared to lowerBound.) Using this assumption, upperBound uses binary search to find r2, i.e. the right subrange on which pred is always true. Performs Ο(log(r.length)) evaluations of pred. The precondition is not verified because it would deteriorate function's complexity. It is possible that the types of value and ElementType!(Range) are different, if the predicate accepts them. See also STL's upper_bound.

  Precondition:
  find!(pred)(r, value).length + find!(not!(pred))(retro(r), value).length == r.length

  Example:

      auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
      auto p = upperBound(a, 3);
      assert(p == begin(a) + 5);

Range equalRange(alias less = "a < b", Range, V)(Range r, V value);
  Assuming a range satisfying both preconditions for lowerBound!(pred)(r, value) and upperBound!(pred)(r, value), the call equalRange!(pred)(r, v) returns the subrange containing all elements e for which both pred(e, value) and pred(value, e) evaluate to false. Performs Ο(log(r.length)) evaluations of pred. See also STL's equal_range.

  Precondition:
  find!(not!(pred))(r, value).length + find!(pred)(retro(r), value).length == r.length && find!(pred)(r, value).length + find!(not!(pred))(retro(r), value).length == r.length

  Example:

      auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
      auto r = equalRange(a, 3);
      assert(r == [ 3, 3, 3 ]);

bool canFindSorted(alias less = "a < b", Range, V)(Range range, V value);
  Returns true if and only if value can be found in range, which is assumed to be sorted. Performs Ο(log(r.length)) evaluations of less. See also STL's binary_search.

struct BinaryHeap(Range,alias less = "a < b") if (isRandomAccessRange!(Range));
  Implements a binary heap collection on top of a given range type (usually T[]). The binary heap induces structure over the underlying range such that accessing the largest element is a Ο(1) operation and extracting it is done fast in Ο(log n) time. (If less is the less-than operator, BinaryHeap defines a so-called max-heap. To define a min-heap, instantiate BinaryHeap with "a > b" as its predicate.) Successive extractions of the largest element effect the heapsort algorithm, which will leave the original range sorted in ascending order according to less.

  Example:

      int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
      auto h = BinaryHeap!(int[])(a);
      auto b = h.pop(5);
      assert(b == [ 8, 9, 10, 14, 16 ]);
      b = h.pop(5);
      assert(b == [ 1, 2, 3, 4, 7 ]);
      assert(h.length == 0);

  this(Range r, size_t initialSize = size_t.max);
    Converts the range r into a heap. If initialSize is specified, only the first initialSize elements in r are transformed into a heap, after which the heap can grow up to r.length. Performs Ο(min(r.length, initialSize)) evaluations of less.

  void acquire(Range r, size_t initialSize = size_t.max);
    Takes ownership of a range.

  void assume(Range r, size_t initialSize = size_t.max);
    Takes ownership of a range assuming it already was organized as a heap.

  Range release();
    Clears the heap. Returns the contents of the store (which satisfies the heap property).

  void push(ElementType!(Range) value);
    Adds one element to the heap. If the length of the heap grows beyond the length of the range that the heap was associated with, a new range is allocated.

  bool conditionalPut(ElementType!(Range) value);
    If this.length < this.capacity, call this.push(value). Otherwise, if less(value, this.top), replace this.top with value and adjust the heap to maintain the heap property. This function is useful in scenarios where the largest N of a large set of candidates must be remembered.

    Returns:
    true if value was put in the heap, false otherwise.

  ElementType!(Range) top();
    Get the top element (the largest according to the predicate less).

  void pop();
    Pops the largest element (according to the predicate less).

  Range pop(size_t n);
    Pops the n largest elements (according to the predicate less) and returns a range containing them (which is in fact a subrange of the heap's underlying range). The returned range is sorted in increasing order by less, and after the call the heap does not contain those elements anymore. If n >= this.length, the entire heap is sorted and returned.

  const size_t length();
    Returns the length of the heap.

  size_t capacity();
    Returns the length of the range underlying the heap.

TRange topNCopy(alias less = "a < b", SRange, TRange)(SRange source, TRange target, SortOutput sorted = SortOutput.no);
  Copies the top n elements of the input range source into the random-access range target, where n = target.length. Elements of source are not touched. If sorted is true, the target is sorted. Otherwise, the target respects the heap property.

  Example:

      int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];
      int[] b = new int[3];
      topNCopy(a, b, true);
      assert(b == [ 0, 1, 2 ]);

struct SetUnion(alias less = "a < b",Rs...) if (allSatisfy!(isInputRange,Rs));
SetUnion!(less,Rs) setUnion(alias less = "a < b", Rs...)(Rs rs);
  Lazily computes the union of two or more ranges rs. The ranges are assumed to be sorted by less. Elements in the output are not unique; the length of the output is the sum of the lengths of the inputs. (The length member is offered if all ranges also have length.) The element types of all ranges must have a common type.

  Example:

      int[] a = [ 1, 2, 4, 5, 7, 9 ];
      int[] b = [ 0, 1, 2, 4, 7, 8 ];
      int[] c = [ 10 ];
      assert(setUnion(a, b).length == a.length + b.length);
      assert(equal(setUnion(a, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][]));
      assert(equal(setUnion(a, c, b),
          [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9, 10][]));

struct SetIntersection(alias less = "a < b",Rs...) if (allSatisfy!(isInputRange,Rs));
SetIntersection!(less,Rs) setIntersection(alias less = "a < b", Rs...)(Rs ranges);
  Lazily computes the intersection of two or more input ranges rs. The ranges are assumed to be sorted by less. The element types of all ranges must have a common type.

  Example:

      int[] a = [ 1, 2, 4, 5, 7, 9 ];
      int[] b = [ 0, 1, 2, 4, 7, 8 ];
      int[] c = [ 0, 1, 4, 5, 7, 8 ];
      assert(equal(setIntersection(a, a), a));
      assert(equal(setIntersection(a, b), [1, 2, 4, 7][]));
      assert(equal(setIntersection(a, b, c), [1, 4, 7][]));

struct SetDifference(alias less = "a < b",R1,R2) if (isInputRange!(R1) && isInputRange!(R2));
SetDifference!(less,R1,R2) setDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);
  Lazily computes the difference of r1 and r2. The two ranges are assumed to be sorted by less. The element types of the two ranges must have a common type.

  Example:

      int[] a = [ 1, 2, 4, 5, 7, 9 ];
      int[] b = [ 0, 1, 2, 4, 7, 8 ];
      assert(equal(setDifference(a, b), [5, 9][]));

struct SetSymmetricDifference(alias less = "a < b",R1,R2) if (isInputRange!(R1) && isInputRange!(R2));
SetSymmetricDifference!(less,R1,R2) setSymmetricDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);
  Lazily computes the symmetric difference of r1 and r2, i.e. the elements that are present in exactly one of r1 and r2. The two ranges are assumed to be sorted by less, and the output is also sorted by less. The element types of the two ranges must have a common type.

  Example:

      int[] a = [ 1, 2, 4, 5, 7, 9 ];
      int[] b = [ 0, 1, 2, 4, 7, 8 ];
      assert(equal(setSymmetricDifference(a, b), [0, 5, 8, 9][]));

struct NWayUnion(alias less,RangeOfRanges);
NWayUnion!(less,RangeOfRanges) nWayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror);
  Computes the union of multiple sets. The input sets are passed as a range of ranges and each is assumed to be sorted by less. Computation is done lazily, one union element at a time. The complexity of one popFront operation is Ο(log(ror.length)). However, the length of ror decreases as ranges in it are exhausted, so the complexity of a full pass through NWayUnion is dependent on the distribution of the lengths of ranges contained within ror. If all ranges have the same length n (worst case scenario), the complexity of a full pass through NWayUnion is Ο(n * ror.length * log(ror.length)), i.e., log(ror.length) times worse than just spanning all ranges in turn. The output comes sorted (unstably) by less.

  Warning:
  Because NWayUnion does not allocate extra memory, it will leave ror modified. Namely, NWayUnion assumes ownership of ror and discretionarily swaps and advances elements of it. If you want ror to preserve its contents after the call, you may want to pass a duplicate to NWayUnion (and perhaps cache the duplicate in between calls).

  Example:

      double[][] a =
      [
          [ 1, 4, 7, 8 ],
          [ 1, 7 ],
          [ 1, 7, 8],
          [ 4 ],
          [ 7 ],
      ];
      auto witness = [
          1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8
      ];
      assert(equal(nWayUnion(a), witness[]));

void largestPartialIntersection(alias less = "a < b", RangeOfRanges, Range)(RangeOfRanges ror, Range tgt, SortOutput sorted = SortOutput.no);
  Given a range of sorted forward ranges ror, copies to tgt the elements that are common to most ranges, along with their number of occurrences. All ranges in ror are assumed to be sorted by less. Only the most frequent tgt.length elements are returned.

  Example:

      // Figure which number can be found in most arrays of the set of
      // arrays below.
      double[][] a =
      [
          [ 1, 4, 7, 8 ],
          [ 1, 7 ],
          [ 1, 7, 8],
          [ 4 ],
          [ 7 ],
      ];
      auto b = new Tuple!(double, uint)[1];
      largestPartialIntersection(a, b);
      // First member is the item, second is the occurrence count
      assert(b[0] == tuple(7.0, 4u));

  7.0 is the correct answer because it occurs in 4 out of the 5 inputs, more than any other number. The second member of the resulting tuple is indeed 4 (recording the number of occurrences of 7.0). If more of the top-frequent numbers are needed, just create a larger tgt range. In the axample above, creating b with length 2 yields tuple(1.0, 3u) in the second position.

  The function largestPartialIntersection is useful for e.g. searching an inverted index for the documents most likely to contain some terms of interest. The complexity of the search is Ο(n * log(tgt.length)), where n is the sum of lengths of all input ranges. This approach is faster than keeping an associative array of the occurrences and then selecting its top items, and also requires less memory (largestPartialIntersection builds its result directly in tgt and requires no extra memory).

  Warning:
  Because largestPartialIntersection does not allocate extra memory, it will leave ror modified. Namely, largestPartialIntersection assumes ownership of ror and discretionarily swaps and advances elements of it. If you want ror to preserve its contents after the call, you may want to pass a duplicate to largestPartialIntersection (and perhaps cache the duplicate in between calls).

void largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRanges ror, Range tgt, WeightsAA weights, SortOutput sorted = SortOutput.no);
  Similar to largestPartialIntersection, but associates a weight with each distinct element in the intersection.

  Example:

      // Figure which number can be found in most arrays of the set of
      // arrays below, with specific per-element weights
      double[][] a =
      [
          [ 1, 4, 7, 8 ],
          [ 1, 7 ],
          [ 1, 7, 8],
          [ 4 ],
          [ 7 ],
      ];
      auto b = new Tuple!(double, uint)[1];
      double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ];
      largestPartialIntersectionWeighted(a, b, weights);
      // First member is the item, second is the occurrence count
      assert(b[0] == tuple(4.0, 2u));

  The correct answer in this case is 4.0, which, although only appears two times, has a total weight 4.6 (three times its weight 2.3). The value 7 is weighted with 1.1 and occurs four times for a total weight 4.4.

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