std.algorithm source code

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, mean)
83         $(SUBREF iteration, permutations)
84         $(SUBREF iteration, reduce)
85         $(SUBREF iteration, splitter)
86         $(SUBREF iteration, substitute)
87         $(SUBREF iteration, sum)
88         $(SUBREF iteration, uniq)
89     )
90 )
91 $(TR
92     $(TDNW $(SUBMODULE Sorting, sorting))
93     $(TD
94         $(SUBREF sorting, completeSort)
95         $(SUBREF sorting, isPartitioned)
96         $(SUBREF sorting, isSorted)
97         $(SUBREF sorting, isStrictlyMonotonic)
98         $(SUBREF sorting, ordered)
99         $(SUBREF sorting, strictlyOrdered)
100         $(SUBREF sorting, makeIndex)
101         $(SUBREF sorting, merge)
102         $(SUBREF sorting, multiSort)
103         $(SUBREF sorting, nextEvenPermutation)
104         $(SUBREF sorting, nextPermutation)
105         $(SUBREF sorting, partialSort)
106         $(SUBREF sorting, partition)
107         $(SUBREF sorting, partition3)
108         $(SUBREF sorting, schwartzSort)
109         $(SUBREF sorting, sort)
110         $(SUBREF sorting, topN)
111         $(SUBREF sorting, topNCopy)
112         $(SUBREF sorting, topNIndex)
113     )
114 )
115 $(TR
116     $(TDNW Set operations $(BR)($(SUBMODULE setops, setops)))
117     $(TD
118         $(SUBREF setops, cartesianProduct)
119         $(SUBREF setops, largestPartialIntersection)
120         $(SUBREF setops, largestPartialIntersectionWeighted)
121         $(SUBREF setops, multiwayMerge)
122         $(SUBREF setops, multiwayUnion)
123         $(SUBREF setops, setDifference)
124         $(SUBREF setops, setIntersection)
125         $(SUBREF setops, setSymmetricDifference)
126     )
127 )
128 $(TR
129     $(TDNW $(SUBMODULE Mutation, mutation))
130     $(TD
131         $(SUBREF mutation, bringToFront)
132         $(SUBREF mutation, copy)
133         $(SUBREF mutation, fill)
134         $(SUBREF mutation, initializeAll)
135         $(SUBREF mutation, move)
136         $(SUBREF mutation, moveAll)
137         $(SUBREF mutation, moveSome)
138         $(SUBREF mutation, moveEmplace)
139         $(SUBREF mutation, moveEmplaceAll)
140         $(SUBREF mutation, moveEmplaceSome)
141         $(SUBREF mutation, remove)
142         $(SUBREF mutation, reverse)
143         $(SUBREF mutation, strip)
144         $(SUBREF mutation, stripLeft)
145         $(SUBREF mutation, stripRight)
146         $(SUBREF mutation, swap)
147         $(SUBREF mutation, swapRanges)
148         $(SUBREF mutation, uninitializedFill)
149     )
150 )
151 ))
152 
153 Many functions in this package are parameterized with a $(GLOSSARY predicate).
154 The predicate may be any suitable callable type
155 (a function, a delegate, a $(GLOSSARY functor), or a lambda), or a
156 compile-time string. The string may consist of $(B any) legal D
157 expression that uses the symbol `a` (for unary functions) or the
158 symbols `a` and `b` (for binary functions). These names will NOT
159 interfere with other homonym symbols in user code because they are
160 evaluated in a different context. The default for all binary
161 comparison predicates is `"a == b"` for unordered operations and
162 `"a < b"` for ordered operations.
163 
164 Example:
165 
166 ----
167 int[] a = ...;
168 static bool greater(int a, int b)
169 {
170     return a > b;
171 }
172 sort!greater(a);           // predicate as alias
173 sort!((a, b) => a > b)(a); // predicate as a lambda.
174 sort!"a > b"(a);           // predicate as string
175                            // (no ambiguity with array name)
176 sort(a);                   // no predicate, "a < b" is implicit
177 ----
178 
179 Macros:
180 SUBMODULE = $(MREF_ALTTEXT $1, std, algorithm, $2)
181 SUBREF = $(REF_ALTTEXT $(TT $2), $2, std, algorithm, $1)$(NBSP)
182 
183 Copyright: Andrei Alexandrescu 2008-.
184 
185 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
186 
187 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
188 
189 Source: $(PHOBOSSRC std/algorithm/package.d)
190  */
191 module std.algorithm;
192 
193 public import std.algorithm.comparison;
194 public import std.algorithm.iteration;
195 public import std.algorithm.mutation;
196 public import std.algorithm.searching;
197 public import std.algorithm.setops;
198 public import std.algorithm.sorting;
199 
200 static import std.functional;