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