libphobos/src/std/algorithm/package.d

   1 // Written in the D programming language.
   2
   3 /**
   4 This package implements generic algorithms oriented towards the processing of
   5 sequences. Sequences processed by these functions define range-based
   6 interfaces.  See also $(MREF_ALTTEXT Reference on ranges, std, range) and
   7 $(HTTP ddili.org/ders/d.en/ranges.html, tutorial on ranges).
   8
   9 $(SCRIPT inhibitQuickIndex = 1;)
  10
  11 Algorithms are categorized into the following submodules:
  12
  13 $(DIVC quickindex,
  14 $(BOOKTABLE ,
  15 $(TR $(TH Submodule) $(TH Functions)
  16 )
  17 $(TR
  18      $(TDNW $(SUBMODULE Searching, searching))
  19      $(TD
  20         $(SUBREF searching, all)
  21         $(SUBREF searching, any)
  22         $(SUBREF searching, balancedParens)
  23         $(SUBREF searching, boyerMooreFinder)
  24         $(SUBREF searching, canFind)
  25         $(SUBREF searching, commonPrefix)
  26         $(SUBREF searching, count)
  27         $(SUBREF searching, countUntil)
  28         $(SUBREF searching, endsWith)
  29         $(SUBREF searching, find)
  30         $(SUBREF searching, findAdjacent)
  31         $(SUBREF searching, findAmong)
  32         $(SUBREF searching, findSkip)
  33         $(SUBREF searching, findSplit)
  34         $(SUBREF searching, findSplitAfter)
  35         $(SUBREF searching, findSplitBefore)
  36         $(SUBREF searching, minCount)
  37         $(SUBREF searching, maxCount)
  38         $(SUBREF searching, minElement)
  39         $(SUBREF searching, maxElement)
  40         $(SUBREF searching, minIndex)
  41         $(SUBREF searching, maxIndex)
  42         $(SUBREF searching, minPos)
  43         $(SUBREF searching, maxPos)
  44         $(SUBREF searching, skipOver)
  45         $(SUBREF searching, startsWith)
  46         $(SUBREF searching, until)
  47     )
  48 )
  49 $(TR
  50     $(TDNW $(SUBMODULE Comparison, comparison))
  51     $(TD
  52         $(SUBREF comparison, among)
  53         $(SUBREF comparison, castSwitch)
  54         $(SUBREF comparison, clamp)
  55         $(SUBREF comparison, cmp)
  56         $(SUBREF comparison, either)
  57         $(SUBREF comparison, equal)
  58         $(SUBREF comparison, isPermutation)
  59         $(SUBREF comparison, isSameLength)
  60         $(SUBREF comparison, levenshteinDistance)
  61         $(SUBREF comparison, levenshteinDistanceAndPath)
  62         $(SUBREF comparison, max)
  63         $(SUBREF comparison, min)
  64         $(SUBREF comparison, mismatch)
  65         $(SUBREF comparison, predSwitch)
  66     )
  67 )
  68 $(TR
  69     $(TDNW $(SUBMODULE Iteration, iteration))
  70     $(TD
  71         $(SUBREF iteration, cache)
  72         $(SUBREF iteration, cacheBidirectional)
  73         $(SUBREF iteration, chunkBy)
  74         $(SUBREF iteration, cumulativeFold)
  75         $(SUBREF iteration, each)
  76         $(SUBREF iteration, filter)
  77         $(SUBREF iteration, filterBidirectional)
  78         $(SUBREF iteration, fold)
  79         $(SUBREF iteration, group)
  80         $(SUBREF iteration, joiner)
  81         $(SUBREF iteration, map)
  82         $(SUBREF iteration, permutations)
  83         $(SUBREF iteration, reduce)
  84         $(SUBREF iteration, splitter)
  85         $(SUBREF iteration, sum)
  86         $(SUBREF iteration, uniq)
  87     )
  88 )
  89 $(TR
  90     $(TDNW $(SUBMODULE Sorting, sorting))
  91     $(TD
  92         $(SUBREF sorting, completeSort)
  93         $(SUBREF sorting, isPartitioned)
  94         $(SUBREF sorting, isSorted)
  95         $(SUBREF sorting, isStrictlyMonotonic)
  96         $(SUBREF sorting, ordered)
  97         $(SUBREF sorting, strictlyOrdered)
  98         $(SUBREF sorting, makeIndex)
  99         $(SUBREF sorting, merge)
 100         $(SUBREF sorting, multiSort)
 101         $(SUBREF sorting, nextEvenPermutation)
 102         $(SUBREF sorting, nextPermutation)
 103         $(SUBREF sorting, partialSort)
 104         $(SUBREF sorting, partition)
 105         $(SUBREF sorting, partition3)
 106         $(SUBREF sorting, schwartzSort)
 107         $(SUBREF sorting, sort)
 108         $(SUBREF sorting, topN)
 109         $(SUBREF sorting, topNCopy)
 110         $(SUBREF sorting, topNIndex)
 111     )
 112 )
 113 $(TR
 114     $(TDNW Set operations $(BR)($(SUBMODULE setops, setops)))
 115     $(TD
 116         $(SUBREF setops, cartesianProduct)
 117         $(SUBREF setops, largestPartialIntersection)
 118         $(SUBREF setops, largestPartialIntersectionWeighted)
 119         $(SUBREF setops, multiwayMerge)
 120         $(SUBREF setops, multiwayUnion)
 121         $(SUBREF setops, setDifference)
 122         $(SUBREF setops, setIntersection)
 123         $(SUBREF setops, setSymmetricDifference)
 124     )
 125 )
 126 $(TR
 127     $(TDNW $(SUBMODULE Mutation, mutation))
 128     $(TD
 129         $(SUBREF mutation, bringToFront)
 130         $(SUBREF mutation, copy)
 131         $(SUBREF mutation, fill)
 132         $(SUBREF mutation, initializeAll)
 133         $(SUBREF mutation, move)
 134         $(SUBREF mutation, moveAll)
 135         $(SUBREF mutation, moveSome)
 136         $(SUBREF mutation, moveEmplace)
 137         $(SUBREF mutation, moveEmplaceAll)
 138         $(SUBREF mutation, moveEmplaceSome)
 139         $(SUBREF mutation, remove)
 140         $(SUBREF mutation, reverse)
 141         $(SUBREF mutation, strip)
 142         $(SUBREF mutation, stripLeft)
 143         $(SUBREF mutation, stripRight)
 144         $(SUBREF mutation, swap)
 145         $(SUBREF mutation, swapRanges)
 146         $(SUBREF mutation, uninitializedFill)
 147     )
 148 )
 149 ))
 150
 151 Many functions in this package are parameterized with a $(GLOSSARY predicate).
 152 The predicate may be any suitable callable type
 153 (a function, a delegate, a $(GLOSSARY functor), or a lambda), or a
 154 compile-time string. The string may consist of $(B any) legal D
 155 expression that uses the symbol $(D a) (for unary functions) or the
 156 symbols $(D a) and $(D b) (for binary functions). These names will NOT
 157 interfere with other homonym symbols in user code because they are
 158 evaluated in a different context. The default for all binary
 159 comparison predicates is $(D "a == b") for unordered operations and
 160 $(D "a < b") for ordered operations.
 161
 162 Example:
 163
 164 ----
 165 int[] a = ...;
 166 static bool greater(int a, int b)
 167 {
 168     return a > b;
 169 }
 170 sort!greater(a);           // predicate as alias
 171 sort!((a, b) => a > b)(a); // predicate as a lambda.
 172 sort!"a > b"(a);           // predicate as string
 173                            // (no ambiguity with array name)
 174 sort(a);                   // no predicate, "a < b" is implicit
 175 ----
 176
 177 Macros:
 178 SUBMODULE = $(MREF_ALTTEXT $1, std, algorithm, $2)
 179 SUBREF = $(REF_ALTTEXT $(TT $2), $2, std, algorithm, $1)$(NBSP)
 180
 181 Copyright: Andrei Alexandrescu 2008-.
 182
 183 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
 184
 185 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
 186
 187 Source: $(PHOBOSSRC std/_algorithm/package.d)
 188  */
 189 module std.algorithm;
 190
 191 public import std.algorithm.comparison;
 192 public import std.algorithm.iteration;
 193 public import std.algorithm.mutation;
 194 public import std.algorithm.searching;
 195 public import std.algorithm.setops;
 196 public import std.algorithm.sorting;
 197
 198 static import std.functional;