std.algorithm

<script type="text/javascript">inhibitQuickIndex = 1</script>

$(BOOKTABLE ,
$(TR $(TH Category) $(TH Functions)
)
$(TR $(TDNW Searching) $(TD $(MYREF all) $(MYREF any) $(MYREF balancedParens) $(MYREF
boyerMooreFinder) $(MYREF canFind) $(MYREF commonPrefix) $(MYREF count)
$(MYREF countUntil) $(MYREF endsWith) $(MYREF find) $(MYREF
findAdjacent) $(MYREF findAmong) $(MYREF findSkip) $(MYREF findSplit)
$(MYREF findSplitAfter) $(MYREF findSplitBefore) $(MYREF minCount)
$(MYREF minPos) $(MYREF mismatch) $(MYREF skipOver) $(MYREF startsWith)
$(MYREF until) )
)
$(TR $(TDNW Comparison) $(TD $(MYREF among) $(MYREF cmp) $(MYREF equal) $(MYREF
levenshteinDistance) $(MYREF levenshteinDistanceAndPath) $(MYREF max)
$(MYREF min) $(MYREF mismatch) )
)
$(TR $(TDNW Iteration) $(TD $(MYREF filter) $(MYREF filterBidirectional)
$(MYREF group) $(MYREF joiner) $(MYREF map) $(MYREF reduce) $(MYREF
splitter) $(MYREF sum) $(MYREF uniq) )
)
$(TR $(TDNW Sorting) $(TD $(MYREF completeSort) $(MYREF isPartitioned)
$(MYREF isSorted) $(MYREF makeIndex) $(MYREF multiSort) $(MYREF nextPermutation)
$(MYREF nextEvenPermutation) $(MYREF partialSort) $(MYREF
partition) $(MYREF partition3) $(MYREF schwartzSort) $(MYREF sort)
$(MYREF topN) $(MYREF topNCopy) )
)
$(TR $(TDNW Set&nbsp;operations) $(TD $(MYREF cartesianProduct) $(MYREF
largestPartialIntersection) $(MYREF largestPartialIntersectionWeighted)
$(MYREF nWayUnion) $(MYREF setDifference) $(MYREF setIntersection) $(MYREF
setSymmetricDifference) $(MYREF setUnion) )
)
$(TR $(TDNW Mutation) $(TD $(MYREF bringToFront) $(MYREF copy) $(MYREF
fill) $(MYREF initializeAll) $(MYREF move) $(MYREF moveAll) $(MYREF
moveSome) $(MYREF remove) $(MYREF reverse) $(MYREF strip) $(MYREF stripLeft)
$(MYREF stripRight) $(MYREF swap) $(MYREF swapRanges) $(MYREF uninitializedFill) )
)
$(TR $(TDNW Utility) $(TD $(MYREF forward) ))
)

Implements algorithms oriented mainly towards processing of
sequences. Some functions are semantic equivalents or supersets of
those found in the $(D $(LESS)_algorithm$(GREATER)) header in $(WEB
sgi.com/tech/stl/, Alexander Stepanov's Standard Template Library) for
C++. Sequences processed by these functions define range-based interfaces.

$(LINK2 std_range.html, Reference on ranges)$(BR)
$(LINK2 http://ddili.org/ders/d.en/ranges.html, Tutorial on ranges)

Many functions in this module are parameterized with a function or a
$(GLOSSARY predicate). The predicate may be passed either as a
function name, a delegate name, a $(GLOSSARY functor) name, or a
compile-time string. The string may consist of $(B any) legal D
expression that uses the symbol $(D a) (for unary functions) or the
symbols $(D a) and $(D 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 $(D "a == b") for unordered operations and
$(D "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
----

$(BOOKTABLE Cheat Sheet,
$(TR $(TH Function Name) $(TH Description)
)
$(LEADINGROW Searching
)
$(TR $(TDNW $(LREF all)) $(TD $(D all!"a > 0"([1, 2, 3, 4])) returns $(D true) because all elements are positive)
)
$(TR $(TDNW $(LREF any)) $(TD $(D any!"a > 0"([1, 2, -3, -4])) returns $(D true) because at least one element is positive)
)
$(TR $(TDNW $(LREF balancedParens)) $(TD $(D
balancedParens("((1 + 1) / 2)")) returns $(D true) because the string
has balanced parentheses.)
)
$(TR $(TDNW $(LREF boyerMooreFinder)) $(TD $(D find("hello
world", boyerMooreFinder("or"))) returns $(D "orld") using the $(LUCKY
Boyer-Moore _algorithm).)
)
$(TR $(TDNW $(LREF canFind)) $(TD $(D canFind("hello world",
"or")) returns $(D true).)
)
$(TR $(TDNW $(LREF count)) $(TD Counts elements that are equal
to a specified value or satisfy a predicate. $(D count([1, 2, 1], 1))
returns $(D 2) and $(D count!"a < 0"([1, -3, 0])) returns $(D 1).)
)
$(TR $(TDNW $(LREF countUntil)) $(TD $(D countUntil(a, b))
returns the number of steps taken in $(D a) to reach $(D b); for
example, $(D countUntil("hello!", "o")) returns $(D 4).)
)
$(TR $(TDNW $(LREF commonPrefix)) $(TD $(D commonPrefix("parakeet",
"parachute")) returns $(D "para").)
)
$(TR $(TDNW $(LREF endsWith)) $(TD $(D endsWith("rocks", "ks"))
returns $(D true).)
)
$(TR $(TD $(LREF find)) $(TD $(D find("hello world",
"or")) returns $(D "orld") using linear search. (For binary search refer
to $(XREF range,sortedRange).))
)
$(TR $(TDNW $(LREF findAdjacent)) $(TD $(D findAdjacent([1, 2,
3, 3, 4])) returns the subrange starting with two equal adjacent
elements, i.e. $(D [3, 3, 4]).)
)
$(TR $(TDNW $(LREF findAmong)) $(TD $(D findAmong("abcd",
"qcx")) returns $(D "cd") because $(D 'c') is among $(D "qcx").)
)
$(TR $(TDNW $(LREF findSkip)) $(TD If $(D a = "abcde"), then
$(D findSkip(a, "x")) returns $(D false) and leaves $(D a) unchanged,
whereas $(D findSkip(a, 'c')) advances $(D a) to $(D "cde") and
returns $(D true).)
)
$(TR $(TDNW $(LREF findSplit)) $(TD $(D findSplit("abcdefg",
"de")) returns the three ranges $(D "abc"), $(D "de"), and $(D
"fg").)
)
$(TR $(TDNW $(LREF findSplitAfter)) $(TD $(D
findSplitAfter("abcdefg", "de")) returns the two ranges $(D "abcde")
and $(D "fg").)
)
$(TR $(TDNW $(LREF findSplitBefore)) $(TD $(D
findSplitBefore("abcdefg", "de")) returns the two ranges $(D "abc") and
$(D "defg").)
)
$(TR $(TDNW $(LREF minCount)) $(TD $(D minCount([2, 1, 1, 4,
1])) returns $(D tuple(1, 3)).)
)
$(TR $(TDNW $(LREF minPos)) $(TD $(D minPos([2, 3, 1, 3, 4,
1])) returns the subrange $(D [1, 3, 4, 1]), i.e., positions the range
at the first occurrence of its minimal element.)
)
$(TR $(TDNW $(LREF mismatch)) $(TD $(D mismatch("parakeet", "parachute"))
returns the two ranges $(D "keet") and $(D "chute").)
)
$(TR $(TDNW $(LREF skipOver)) $(TD Assume $(D a = "blah"). Then
$(D skipOver(a, "bi")) leaves $(D a) unchanged and returns $(D false),
whereas $(D skipOver(a, "bl")) advances $(D a) to refer to $(D "ah")
and returns $(D true).)
)
$(TR $(TDNW $(LREF startsWith)) $(TD $(D startsWith("hello,
world", "hello")) returns $(D true).)
)
$(TR $(TDNW $(LREF until)) $(TD Lazily iterates a range
until a specific value is found.)
)
$(LEADINGROW Comparison
)
$(TR $(TDNW $(LREF among)) $(TD Checks if a value is among a set
of values, e.g. $(D if (v.among(1, 2, 3)) // `v` is 1, 2 or 3))
)
$(TR $(TDNW $(LREF cmp)) $(TD $(D cmp("abc", "abcd")) is $(D
-1), $(D cmp("abc", "aba")) is $(D 1), and $(D cmp("abc", "abc")) is
$(D 0).)
)
$(TR $(TDNW $(LREF equal)) $(TD Compares ranges for
element-by-element equality, e.g. $(D equal([1, 2, 3], [1.0, 2.0,
3.0])) returns $(D true).)
)
$(TR $(TDNW $(LREF levenshteinDistance)) $(TD $(D
levenshteinDistance("kitten", "sitting")) returns $(D 3) by using the
$(LUCKY Levenshtein distance _algorithm).)
)
$(TR $(TDNW $(LREF levenshteinDistanceAndPath)) $(TD $(D
levenshteinDistanceAndPath("kitten", "sitting")) returns $(D tuple(3,
"snnnsni")) by using the $(LUCKY Levenshtein distance _algorithm).)
)
$(TR $(TDNW $(LREF max)) $(TD $(D max(3, 4, 2)) returns $(D
4).)
)
$(TR $(TDNW $(LREF min)) $(TD $(D min(3, 4, 2)) returns $(D
2).)
)
$(TR $(TDNW $(LREF mismatch)) $(TD $(D mismatch("oh hi",
"ohayo")) returns $(D tuple(" hi", "ayo")).)
)
$(LEADINGROW Iteration
)
$(TR $(TDNW $(LREF filter)) $(TD $(D filter!"a > 0"([1, -1, 2,
0, -3])) iterates over elements $(D 1) and $(D 2).)
)
$(TR $(TDNW $(LREF filterBidirectional)) $(TD Similar to $(D
filter), but also provides $(D back) and $(D popBack) at a small
increase in cost.)
)
$(TR $(TDNW $(LREF group)) $(TD $(D group([5, 2, 2, 3, 3]))
returns a range containing the tuples $(D tuple(5, 1)),
$(D tuple(2, 2)), and $(D tuple(3, 2)).)
)
$(TR $(TDNW $(LREF joiner)) $(TD $(D joiner(["hello",
"world!"], "; ")) returns a range that iterates over the characters $(D
"hello; world!"). No new string is created - the existing inputs are
iterated.)
)
$(TR $(TDNW $(LREF map)) $(TD $(D map!"2 * a"([1, 2, 3]))
lazily returns a range with the numbers $(D 2), $(D 4), $(D 6).)
)
$(TR $(TDNW $(LREF reduce)) $(TD $(D reduce!"a + b"([1, 2, 3,
4])) returns $(D 10).)
)
$(TR $(TDNW $(LREF splitter)) $(TD Lazily splits a range by a
separator.)
)
$(TR $(TDNW $(LREF sum)) $(TD Same as $(D reduce), but specialized for
accurate summation.)
)
$(TR $(TDNW $(LREF uniq)) $(TD Iterates over the unique elements
in a range, which is assumed sorted.)
)
$(LEADINGROW Sorting
)
$(TR $(TDNW $(LREF completeSort)) $(TD If $(D a = [10, 20, 30])
and $(D b = [40, 6, 15]), then $(D completeSort(a, b)) leaves $(D a =
[6, 10, 15]) and $(D b = [20, 30, 40]). The range $(D a) must be
sorted prior to the call, and as a result the combination $(D $(XREF
range,chain)(a, b)) is sorted.)
)
$(TR $(TDNW $(LREF isPartitioned)) $(TD $(D isPartitioned!"a <
0"([-1, -2, 1, 0, 2])) returns $(D true) because the predicate is $(D
true) for a portion of the range and $(D false) afterwards.)
)
$(TR $(TDNW $(LREF isSorted)) $(TD $(D isSorted([1, 1, 2, 3]))
returns $(D true).)
)
$(TR $(TDNW $(LREF makeIndex)) $(TD Creates a separate index
for a range.)
)
$(TR $(TDNW $(LREF nextPermutation)) $(TD Computes the next lexicographically
greater permutation of a range in-place.)
)
$(TR $(TDNW $(LREF nextEvenPermutation)) $(TD Computes the next
lexicographically greater even permutation of a range in-place.)
)
$(TR $(TDNW $(LREF partialSort)) $(TD If $(D a = [5, 4, 3, 2,
1]), then $(D partialSort(a, 3)) leaves $(D a[0 .. 3] = [1, 2,
3]). The other elements of $(D a) are left in an unspecified order.)
)
$(TR $(TDNW $(LREF partition)) $(TD Partitions a range
according to a predicate.)
)
$(TR $(TDNW $(LREF partition3)) $(TD Partitions a range
in three parts (less than, equal, greater than the given pivot).)
)
$(TR $(TDNW $(LREF schwartzSort)) $(TD Sorts with the help of
the $(LUCKY Schwartzian transform).)
)
$(TR $(TDNW $(LREF sort)) $(TD Sorts.)
)
$(TR $(TDNW $(LREF topN)) $(TD Separates the top elements in a
range.)
)
$(TR $(TDNW $(LREF topNCopy)) $(TD Copies out the top elements
of a range.)
)
$(LEADINGROW Set operations
)
$(TR $(TDNW $(LREF cartesianProduct)) $(TD Computes Cartesian product of two
ranges.)
)
$(TR $(TDNW $(LREF largestPartialIntersection)) $(TD Copies out
the values that occur most frequently in a range of ranges.)
)
$(TR $(TDNW $(LREF largestPartialIntersectionWeighted)) $(TD
Copies out the values that occur most frequently (multiplied by
per-value weights) in a range of ranges.)
)
$(TR $(TDNW $(LREF nWayUnion)) $(TD Computes the union of a set
of sets implemented as a range of sorted ranges.)
)
$(TR $(TDNW $(LREF setDifference)) $(TD Lazily computes the set
difference of two or more sorted ranges.)
)
$(TR $(TDNW $(LREF setIntersection)) $(TD Lazily computes the
intersection of two or more sorted ranges.)
)
$(TR $(TDNW $(LREF setSymmetricDifference)) $(TD Lazily
computes the symmetric set difference of two or more sorted ranges.)
)
$(TR $(TDNW $(LREF setUnion)) $(TD Lazily computes the set
union of two or more sorted ranges.)
)
$(LEADINGROW Mutation
)
$(TR $(TDNW $(LREF bringToFront)) $(TD If $(D a = [1, 2, 3])
and $(D b = [4, 5, 6, 7]), $(D bringToFront(a, b)) leaves $(D a = [4,
5, 6]) and $(D b = [7, 1, 2, 3]).)
)
$(TR $(TDNW $(LREF copy)) $(TD Copies a range to another. If
$(D a = [1, 2, 3]) and $(D b = new int[5]), then $(D copy(a, b))
leaves $(D b = [1, 2, 3, 0, 0]) and returns $(D b[3 .. $]).)
)
$(TR $(TDNW $(LREF fill)) $(TD Fills a range with a pattern,
e.g., if $(D a = new int[3]), then $(D fill(a, 4)) leaves $(D a = [4,
4, 4]) and $(D fill(a, [3, 4])) leaves $(D a = [3, 4, 3]).)
)
$(TR $(TDNW $(LREF initializeAll)) $(TD If $(D a = [1.2, 3.4]),
then $(D initializeAll(a)) leaves $(D a = [double.init,
double.init]).)
)
$(TR $(TDNW $(LREF move)) $(TD $(D move(a, b)) moves $(D a)
into $(D b). $(D move(a)) reads $(D a) destructively.)
)
$(TR $(TDNW $(LREF moveAll)) $(TD Moves all elements from one
range to another.)
)
$(TR $(TDNW $(LREF moveSome)) $(TD Moves as many elements as
possible from one range to another.)
)
$(TR $(TDNW $(LREF remove)) $(TD Removes elements from a range
in-place, and returns the shortened range.)
)
$(TR $(TDNW $(LREF reverse)) $(TD If $(D a = [1, 2, 3]), $(D
reverse(a)) changes it to $(D [3, 2, 1]).)
)
$(TR $(TDNW $(LREF strip)) $(TD Strips all leading and trailing
elements equal to a value, or that satisfy a predicate.
If $(D a = [1, 1, 0, 1, 1]), then $(D strip(a, 1)) and $(D strip!(e => e == 1)(a))
returns $(D [0]).)
)
$(TR $(TDNW $(LREF stripLeft)) $(TD Strips all leading elements equal to a value,
or that satisfy a predicate.
If $(D a = [1, 1, 0, 1, 1]), then $(D stripLeft(a, 1)) and $(D stripLeft!(e => e == 1)(a))
returns $(D [0, 1, 1]).)
)
$(TR $(TDNW $(LREF stripRight)) $(TD Strips all trailing elements equal to a value,
or that satisfy a predicate.
If $(D a = [1, 1, 0, 1, 1]), then $(D stripRight(a, 1)) and $(D stripRight!(e => e == 1)(a))
returns $(D [1, 1, 0]).)
)
$(TR $(TDNW $(LREF swap)) $(TD Swaps two values.)
)
$(TR $(TDNW $(LREF swapRanges)) $(TD Swaps all elements of two
ranges.)
)
$(TR $(TDNW $(LREF uninitializedFill)) $(TD Fills a range
(assumed uninitialized) with a value.)
)
)

Macros:
WIKI = Phobos/StdAlgorithm
MYREF = <font face='Consolas, "Bitstream Vera Sans Mono", "Andale Mono", Monaco, "DejaVu Sans Mono", "Lucida Console", monospace'><a href="#.$1">$1</a>&nbsp;</font>

Copyright: Andrei Alexandrescu 2008-.

License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).

Authors: $(WEB erdani.com, Andrei Alexandrescu)

Source: $(PHOBOSSRC std/_algorithm.d)
  • map

    $(D auto map(Range)(Range r) if (isInputRange!(Unqual!Range));)

  • __unittestL432_145

  • __unittestL445_146

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

  • __unittestL463_147

    You may alias $(D map) with some function(s) to a symbol and use it separately:

  • __unittestL579_153

  • __unittestL600_154

  • __unittestL698_155

  • __unittestL705_158

  • __unittestL719_159

  • __unittestL729_160

  • reduce

    $(D auto reduce(Args...)(Args args) if (Args.length > 0 && Args.length <= 2 && isIterable!(Args[$ - 1]));)

  • __unittestL895_167

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

  • __unittestL948_168

    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 $(D reduce) accepts multiple functions. If two or more functions are passed, $(D reduce) returns a $(XREF typecons, Tuple) object with one member per passed-in function. The number of seeds must be correspondingly increased.

  • __unittestL968_169

  • __unittestL1033_170

  • __unittestL1044_171

  • sum

    Sums elements of $(D r), which must be a finite input range. Although conceptually $(D sum(r)) is equivalent to $(D reduce!((a, b) => a + b)(0, r)), $(D sum) uses specialized algorithms to maximize accuracy, as follows.

  • sum

    Sums elements of $(D r), which must be a finite input range. Although conceptually $(D sum(r)) is equivalent to $(D reduce!((a, b) => a + b)(0, r)), $(D sum) uses specialized algorithms to maximize accuracy, as follows.

  • __unittestL1146_172

    Sums elements of $(D r), which must be a finite input range. Although conceptually $(D sum(r)) is equivalent to $(D reduce!((a, b) => a + b)(0, r)), $(D sum) uses specialized algorithms to maximize accuracy, as follows.

  • __unittestL1173_173

  • __unittestL1190_174

  • __unittestL1207_175

  • __unittestL1221_177

  • __unittestL1228_178

  • fill

    Fills $(D range) with a $(D filler).

  • __unittestL1265_179

  • __unittestL1272_180

  • __unittestL1303_181

  • __unittestL1324_182

  • fill

    Fills $(D range) with a pattern copied from $(D filler). The length of $(D range) does not have to be a multiple of the length of $(D filler). If $(D filler) is empty, an exception is thrown.

  • __unittestL1413_183

  • __unittestL1421_184

  • uninitializedFill

    Fills a range with a value. Assumes that the range does not currently contain meaningful content. This is of interest for structs that define copy constructors (for all other types, fill and uninitializedFill are equivalent).

  • initializeAll

    Initializes all elements of a range with their $(D .init) value. Assumes that the range does not currently contain meaningful content.

  • initializeAll

  • __unittestL1537_185

  • filter

    $(D auto filter(Range)(Range rs) if (isInputRange!(Unqual!Range));)

  • __unittestL1637_190

  • __unittestL1710_191

  • __unittestL1762_192

  • __unittestL1780_193

  • __unittestL1790_194

  • filterBidirectional

    $(D auto filterBidirectional(Range)(Range r) if (isBidirectionalRange!(Unqual!Range));)

  • __unittestL1818_195

  • move

    Moves $(D source) into $(D target) via a destructive copy.

  • __unittestL1931_196

  • move

  • __unittestL2029_197

  • __unittestL2079_198

  • __unittestL2085_199

  • __unittestL2105_200

  • moveAll

    For each element $(D a) in $(D src) and each element $(D b) in $(D tgt) in lockstep in increasing order, calls $(D move(a, b)). Returns the leftover portion of $(D tgt). Throws an exception if there is not enough room in $(D tgt) to accommodate all of $(D src).

  • __unittestL2177_201

  • moveSome

    For each element $(D a) in $(D src) and each element $(D b) in $(D tgt) in lockstep in increasing order, calls $(D move(a, b)). Stops when either $(D src) or $(D tgt) have been exhausted. Returns the leftover portions of the two ranges.

  • __unittestL2209_202

  • swap

    Swaps $(D lhs) and $(D rhs). The instances $(D lhs) and $(D rhs) are moved in memory, without ever calling $(D opAssign), nor any other function. $(D T) need not be assignable at all to be swapped.

  • swap

  • __unittestL2283_203

  • __unittestL2308_204

  • __unittestL2346_205

  • __unittestL2353_206

  • __unittestL2367_207

  • __unittestL2377_208

  • __unittestL2384_209

  • __unittestL2391_210

  • swapFront

  • forward

    Forwards function arguments with saving ref-ness.

  • __unittestL2453_211

  • __unittestL2468_212

  • __unittestL2485_213

  • __unittestL2516_214

  • splitter

    Splits a range using an element as a separator. This can be used with any narrow string type or sliceable range type, but is most popular with string types.

  • __unittestL2704_215

  • __unittestL2716_216

  • __unittestL2777_217

  • splitter

    Splits a range using another range as a separator. This can be used with any narrow string type or sliceable range type, but is most popular with string types.

  • __unittestL2950_218

  • __unittestL2991_219

  • __unittestL3004_220

  • __unittestL3011_221

  • splitter

  • __unittestL3142_222

  • __unittestL3153_223

  • __unittestL3186_224

  • __unittestL3209_225

  • splitter

    Lazily splits the string $(D s) into words, using whitespace as the delimiter.

  • __unittestL3280_226

  • __unittestL3286_227

  • __unittestL3301_228

  • __unittestL3327_238

  • joiner

    Lazily joins a range of ranges with a separator. The separator itself is a range. If you do not provide a separator, then the ranges are joined directly without anything in between them.

  • __unittestL3559_239

  • __unittestL3578_240

  • __unittestL3585_241

  • __unittestL3625_242

  • joiner

  • __unittestL3759_243

  • __unittestL3798_244

  • __unittestL3884_246

  • uniq

    Iterates unique consecutive elements of the given range (functionality akin to the $(WEB wikipedia.org/wiki/_Uniq, _uniq) system utility). Equivalence of elements is assessed by using the predicate $(D pred), by default $(D "a == b"). If the given range is bidirectional, $(D uniq) also yields a bidirectional range.

  • __unittestL3910_247

  • __unittestL3973_248

  • Group

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

  • group

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

  • __unittestL4073_249

  • __unittestL4080_250

  • find

    Finds an individual element in an input range. Elements of $(D haystack) are compared with $(D needle) by using predicate $(D pred). Performs $(BIGOH walkLength(haystack)) evaluations of $(D pred).

  • __unittestL4340_251

  • __unittestL4358_252

  • __unittestL4372_257

  • __unittestL4383_264

  • __unittestL4408_269

  • __unittestL4425_270

  • __unittestL4447_271

  • find

    Finds a forward range in another. Elements are compared for equality. Performs $(BIGOH walkLength(haystack) * walkLength(needle)) comparisons in the worst case. Specializations taking advantage of bidirectional or random access (where present) may accelerate search depending on the statistics of the two ranges' content.

  • __unittestL4504_272

  • __unittestL4513_273

  • find

  • __unittestL4575_274

  • find

  • __unittestL4660_275

  • __unittestL4669_276

  • simpleMindedFind

  • __unittestL4751_277

  • find

    Finds two or more $(D needles) into a $(D haystack). The predicate $(D pred) is used throughout to compare elements. By default, elements are compared for equality.

  • __unittestL4841_278

  • __unittestL4851_279

  • __unittestL4863_280

  • __unittestL4892_281

  • __unittestL4912_282

  • BoyerMooreFinder

  • boyerMooreFinder

  • find

  • __unittestL5037_283

  • __unittestL5057_284

  • find

    Advances the input range $(D haystack) by calling $(D haystack.popFront) until either $(D pred(haystack.front)), or $(D haystack.empty). Performs $(BIGOH haystack.length) evaluations of $(D pred).

  • __unittestL5120_285

  • __unittestL5130_289

  • findSkip

    If $(D needle) occurs in $(D haystack), positions $(D haystack) right after the first occurrence of $(D needle) and returns $(D true). Otherwise, leaves $(D haystack) as is and returns $(D false).

  • __unittestL5161_290

  • findSplit

    These functions find the first occurrence of $(D needle) in $(D haystack) and then split $(D haystack) as follows.

  • findSplitBefore

    These functions find the first occurrence of $(D needle) in $(D haystack) and then split $(D haystack) as follows.

  • findSplitAfter

    These functions find the first occurrence of $(D needle) in $(D haystack) and then split $(D haystack) as follows.

  • __unittestL5323_291

  • __unittestL5342_292

  • __unittestL5369_293

  • countUntil

    Returns the number of elements which must be popped from the front of $(D haystack) before reaching an element for which $(D startsWith!pred(haystack, needles)) is $(D true). If $(D startsWith!pred(haystack, needles)) is not $(D true) for any element in $(D haystack), then $(D -1) is returned.

  • countUntil

    Returns the number of elements which must be popped from the front of $(D haystack) before reaching an element for which $(D startsWith!pred(haystack, needles)) is $(D true). If $(D startsWith!pred(haystack, needles)) is not $(D true) for any element in $(D haystack), then $(D -1) is returned.

  • __unittestL5501_294

  • __unittestL5515_295

  • __unittestL5539_296

  • countUntil

    Returns the number of elements which must be popped from $(D haystack) before $(D pred(haystack.front)) is $(D true).

  • __unittestL5595_297

  • __unittestL5605_298

  • OpenRight

    Interval option specifier for $(D until) (below) and others.

  • Until

    Lazily iterates $(D range) until value $(D sentinel) is found, at which point it stops.

  • until

    Lazily iterates $(D range) until value $(D sentinel) is found, at which point it stops.

  • until

    Lazily iterates $(D range) until value $(D sentinel) is found, at which point it stops.

  • __unittestL5757_299

  • __unittestL5764_300

  • startsWith

    If the range $(D doesThisStart) starts with $(I any) of the $(D withOneOfThese) ranges or elements, returns 1 if it starts with $(D withOneOfThese[0]), 2 if it starts with $(D withOneOfThese[1]), and so on. If none match, returns 0. In the case where $(D doesThisStart) starts with multiple of the ranges or elements in $(D withOneOfThese), then the shortest one matches (if there are two which match which are of the same length (e.g. $(D "a") and $(D 'a')), then the left-most of them in the argument list matches).

  • startsWith

    If the range $(D doesThisStart) starts with $(I any) of the $(D withOneOfThese) ranges or elements, returns 1 if it starts with $(D withOneOfThese[0]), 2 if it starts with $(D withOneOfThese[1]), and so on. If none match, returns 0. In the case where $(D doesThisStart) starts with multiple of the ranges or elements in $(D withOneOfThese), then the shortest one matches (if there are two which match which are of the same length (e.g. $(D "a") and $(D 'a')), then the left-most of them in the argument list matches).

  • startsWith

    If the range $(D doesThisStart) starts with $(I any) of the $(D withOneOfThese) ranges or elements, returns 1 if it starts with $(D withOneOfThese[0]), 2 if it starts with $(D withOneOfThese[1]), and so on. If none match, returns 0. In the case where $(D doesThisStart) starts with multiple of the ranges or elements in $(D withOneOfThese), then the shortest one matches (if there are two which match which are of the same length (e.g. $(D "a") and $(D 'a')), then the left-most of them in the argument list matches).

  • __unittestL5940_301

  • __unittestL5955_302

  • skipOver

    If $(D startsWith(r1, r2)), consume the corresponding elements off $(D r1) and return $(D true). Otherwise, leave $(D r1) unchanged and return $(D false).

  • __unittestL6067_307

  • skipOver

    Checks whether a range starts with an element, and if so, consume that element off $(D r) and return $(D true). Otherwise, leave $(D r) unchanged and return $(D false).

  • __unittestL6097_312

  • skipAll

  • __unittestL6132_313

  • endsWith

    The reciprocal of $(D startsWith).

  • endsWith

    The reciprocal of $(D startsWith).

  • endsWith

    The reciprocal of $(D startsWith).

  • __unittestL6247_314

  • __unittestL6261_315

  • commonPrefix

    Returns the common prefix of two ranges.

  • __unittestL6388_316

  • commonPrefix

  • commonPrefix

  • commonPrefix

  • __unittestL6448_317

  • findAdjacent

    Advances $(D r) until it finds the first two adjacent elements $(D a), $(D b) that satisfy $(D pred(a, b)). Performs $(BIGOH r.length) evaluations of $(D pred).

  • __unittestL6535_318

  • __unittestL6545_319

  • findAmong

    Advances $(D seq) by calling $(D seq.popFront) until either $(D find!(pred)(choices, seq.front)) is $(D true), or $(D seq) becomes empty. Performs $(BIGOH seq.length * choices.length) evaluations of $(D pred).

  • __unittestL6591_320

  • __unittestL6598_321

  • count

    The first version counts the number of elements $(D x) in $(D r) for which $(D pred(x, value)) is $(D true). $(D pred) defaults to equality. Performs $(BIGOH haystack.length) evaluations of $(D pred).

  • __unittestL6636_324

  • __unittestL6654_325

  • __unittestL6675_326

  • count

  • count

  • __unittestL6719_327

  • __unittestL6729_328

  • balancedParens

    Checks whether $(D r) has "balanced parentheses", i.e. all instances of $(D lPar) are closed by corresponding instances of $(D rPar). The parameter $(D maxNestingLevel) controls the nesting level allowed. The most common uses are the default or $(D 0). In the latter case, no nesting is allowed.

  • __unittestL6764_329

  • equal

    Compares two ranges for equality, as defined by predicate $(D pred) (which is $(D ==) by default).

  • __unittestL6831_330

  • __unittestL6856_331

    Tip: $(D equal) can itself be used as a predicate to other functions. This can be very useful when the element type of a range is itself a range. In particular, $(D equal) can be its own predicate, allowing range of range (of range...) comparisons.

  • __unittestL6866_332

  • cmp

    Performs three-way lexicographical comparison on two input ranges according to predicate $(D pred). Iterating $(D r1) and $(D r2) in lockstep, $(D cmp) compares each element $(D e1) of $(D r1) with the corresponding element $(D e2) in $(D r2). If $(D binaryFun!pred(e1, e2)), $(D cmp) returns a negative value. If $(D binaryFun!pred(e2, e1)), $(D cmp) returns a positive value. If one of the ranges has been finished, $(D cmp) returns a negative value if $(D r1) has fewer elements than $(D r2), a positive value if $(D r1) has more elements than $(D r2), and $(D 0) if the ranges have the same number of elements.

  • cmp

  • __unittestL7026_333

  • min

    Returns the minimum of the passed-in values.

  • __unittestL7133_334

  • max

    Returns the maximum of the passed-in values.

  • __unittestL7226_335

  • __unittestL7239_336

  • minCount

    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 $(D maxCount) is not provided).

  • __unittestL7356_337

  • __unittestL7370_338

  • __unittestL7390_339

  • minPos

    Returns the position of the minimum element of forward range $(D range), i.e. a subrange of $(D range) starting at the position of its smallest element and with the same ending as $(D range). The function can actually be used for finding the maximum or any other ordering predicate (that's why $(D maxPos) is not provided).

  • __unittestL7483_340

  • __unittestL7492_341

  • __unittestL7505_342

  • __unittestL7519_343

  • mismatch

    Sequentially compares elements in $(D r1) and $(D r2) in lockstep, and stops at the first mismatch (according to $(D pred), by default equality). Returns a tuple with the reduced ranges that start with the two mismatched values. Performs $(BIGOH min(r1.length, r2.length)) evaluations of $(D pred).

  • __unittestL7557_344

  • __unittestL7566_345

  • EditOp

    Encodes $(WEB realityinteractive.com/rgrzywinski/archives/000249.html, edit operations) necessary to transform one sequence into another. Given sequences $(D s) (source) and $(D t) (target), a sequence of $(D EditOp) encodes the steps that need to be taken to convert $(D s) into $(D t). For example, if $(D s = "cat") and $(D "cars"), the minimal sequence that transforms $(D s) into $(D 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.

  • Levenshtein

  • levenshteinDistance

    Returns the $(WEB wikipedia.org/wiki/Levenshtein_distance, Levenshtein distance) between $(D s) and $(D t). The Levenshtein distance computes the minimal amount of edit operations necessary to transform $(D s) into $(D t). Performs $(BIGOH s.length * t.length) evaluations of $(D equals) and occupies $(BIGOH s.length * t.length) storage.

  • __unittestL7749_348

  • levenshteinDistanceAndPath

    Returns the Levenshtein distance and the edit path between $(D s) and $(D t).

  • __unittestL7777_349

  • __unittestL7785_350

  • copy

    Copies the content of $(D source) into $(D target) and returns the remaining (unfilled) part of $(D target).

  • __unittestL7863_351

  • __unittestL7877_352

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

  • __unittestL7890_354

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

  • __unittestL7902_355

    $(XREF range, retro) can be used to achieve behavior similar to $(WEB sgi.com/tech/stl/copy_backward.html, STL's copy_backward').

  • __unittestL7911_356

  • swapRanges

    Swaps all elements of $(D r1) with successive elements in $(D r2). Returns a tuple containing the remainder portions of $(D r1) and $(D 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.

  • __unittestL7962_357

  • reverse

    Reverses $(D r) in-place. Performs $(D r.length / 2) evaluations of $(D swap).

  • __unittestL7994_358

  • reverse

  • __unittestL8014_359

  • reverse

    Reverses $(D r) in-place, where $(D r) is a narrow string (having elements of type $(D char) or $(D wchar)). UTF sequences consisting of multiple code units are preserved properly.

  • __unittestL8060_360

  • __unittestL8067_361

  • strip

    The strip group of functions allow stripping of either leading, trailing, or both leading and trailing elements.

  • strip

    The strip group of functions allow stripping of either leading, trailing, or both leading and trailing elements.

  • stripLeft

    The strip group of functions allow stripping of either leading, trailing, or both leading and trailing elements.

  • stripLeft

    The strip group of functions allow stripping of either leading, trailing, or both leading and trailing elements.

  • stripRight

    The strip group of functions allow stripping of either leading, trailing, or both leading and trailing elements.

  • stripRight

    The strip group of functions allow stripping of either leading, trailing, or both leading and trailing elements.

  • __unittestL8157_363

    Strip leading and trailing elements equal to the target element.

  • __unittestL8167_369

    Strip leading and trailing elements while the predicate returns true.

  • __unittestL8177_370

    Strip leading elements equal to the target element.

  • __unittestL8187_376

    Strip leading elements while the predicate returns true.

  • __unittestL8197_377

    Strip trailing elements equal to the target element.

  • __unittestL8207_383

    Strip trailing elements while the predicate returns true.

  • bringToFront

    The $(D 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.

  • __unittestL8311_384

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

  • __unittestL8325_385

    The $(D front) range may actually "step over" the $(D back) range. This is very useful with forward ranges that cannot compute comfortably right-bounded subranges like $(D arr[0 .. 4]) above. In the example below, $(D r2) is a right subrange of $(D r1).

  • __unittestL8341_386

    Elements can be swapped across ranges of different types:

  • __unittestL8352_387

  • 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 $(D [ "abc", "b", "aBc" ]) according to $(D toUpper(a) < toUpper(b)). That algorithm might choose to swap the two equivalent strings $(D "abc") and $(D "aBc"). That does not affect the sorting since both $(D [ "abc", "aBc", "b" ]) and $(D [ "aBc", "abc", "b" ]) are valid outcomes.

  • remove

    Eliminates elements at given offsets from $(D range) and returns the shortened range. In the simplest call, one element is removed.

  • remove

  • __unittestL8672_388

  • __unittestL8684_389

  • __unittestL8728_390

  • __unittestL8737_391

  • remove

    Reduces the length of the bidirectional range $(D range) by removing elements that satisfy $(D pred). If $(D s = SwapStrategy.unstable), elements are moved from the right end of the range over the elements to eliminate. If $(D s = SwapStrategy.stable) (the default), elements are moved progressively to front such that their relative order is preserved. Returns the filtered range.

  • __unittestL8797_393

  • __unittestL8815_394

  • partition

    Partitions a range in two using $(D pred) as a predicate. Specifically, reorders the range $(D r = [left, right$(RPAREN)) using $(D swap) such that all elements $(D i) for which $(D pred(i)) is $(D true) come before all elements $(D j) for which $(D pred(j)) returns $(D false).

  • __unittestL9002_395

  • __unittestL9039_396

  • isPartitioned

    Returns $(D true) if $(D r) is partitioned according to predicate $(D pred).

  • __unittestL9072_397

  • partition3

    Rearranges elements in $(D r) in three adjacent ranges and returns them. The first and leftmost range only contains elements in $(D r) less than $(D pivot). The second and middle range only contains elements in $(D r) that are equal to $(D pivot). Finally, the third and rightmost range only contains elements in $(D r) that are greater than $(D pivot). The less-than test is defined by the binary function $(D less).

  • __unittestL9142_398

  • __unittestL9151_399

  • topN

    Reorders the range $(D r) using $(D swap) such that $(D r[nth]) refers to the element that would fall there if the range were fully sorted. In addition, it also partitions $(D r) such that all elements $(D e1) from $(D r[0]) to $(D r[nth]) satisfy $(D !less(r[nth], e1)), and all elements $(D e2) from $(D r[nth]) to $(D r[r.length]) satisfy $(D !less(e2, r[nth])). Effectively, it finds the nth smallest (according to $(D less)) elements in $(D r). Performs an expected $(BIGOH r.length) (if unstable) or $(BIGOH r.length * log(r.length)) (if stable) evaluations of $(D less) and $(D swap).

  • __unittestL9234_401

  • __unittestL9242_404

  • __unittestL9290_405

  • topN

    Stores the smallest elements of the two ranges in the left-hand range.

  • __unittestL9334_406

  • sort

    Sorts a random-access range according to the predicate $(D less). Performs $(BIGOH r.length * log(r.length)) evaluations of $(D less). Stable sorting requires $(D hasAssignableElements!Range) to be true.

  • __unittestL9418_407

  • __unittestL9433_408

  • __unittestL9441_409

  • multiSort

    $(D void multiSort(Range)(Range r) if (validPredicates!(ElementType!Range, less));)

  • __unittestL9606_410

  • __unittestL9615_411

  • __unittestL9629_412

  • __unittestL9727_413

  • swapAt

  • __unittestL10384_414

  • __unittestL10458_415

  • __unittestL10467_416

  • schwartzSort

    Sorts a range using an algorithm akin to the $(WEB wikipedia.org/wiki/Schwartzian_transform, Schwartzian transform), also known as the decorate-sort-undecorate pattern in Python and Lisp. (Not to be confused with $(WEB youtube.com/watch?v=UHw6KXbvazs, 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 $(D sort), but $(D schwartzSort) evaluates $(D transform) only $(D r.length) times (less than half when compared to regular sorting). The usage can be best illustrated with an example.

  • __unittestL10554_421

  • __unittestL10561_422

  • __unittestL10568_423

  • __unittestL10600_424

  • partialSort

    Reorders the random-access range $(D r) such that the range $(D r[0 .. mid]) is the same as if the entire $(D r) were sorted, and leaves the range $(D r[mid .. r.length]) in no particular order. Performs $(BIGOH r.length * log(mid)) evaluations of $(D pred). The implementation simply calls $(D topN!(less, ss)(r, n)) and then $(D sort!(less, ss)(r[0 .. n])).

  • __unittestL10650_425

  • completeSort

    Sorts the random-access range $(D chain(lhs, rhs)) according to predicate $(D less). The left-hand side of the range $(D lhs) is assumed to be already sorted; $(D rhs) is assumed to be unsorted. The exact strategy chosen depends on the relative sizes of $(D lhs) and $(D rhs). Performs $(BIGOH lhs.length + rhs.length * log(rhs.length)) (best case) to $(BIGOH (lhs.length + rhs.length) * log(lhs.length + rhs.length)) (worst-case) evaluations of $(D swap).

  • __unittestL10684_426

  • isSorted

    Checks whether a forward range is sorted according to the comparison operation $(D less). Performs $(BIGOH r.length) evaluations of $(D less).

  • __unittestL10737_427

  • __unittestL10747_428

  • makeIndex

    Computes an index for $(D r) based on the comparison $(D 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 immutable 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 $(D sort)'s.

  • makeIndex

    Computes an index for $(D r) based on the comparison $(D 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 immutable 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 $(D sort)'s.

  • __unittestL10857_435

  • __unittestL10872_436

  • SortOutput

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

  • topNIndex

  • topNIndex

  • __unittestL10967_437

  • canFind

    Convenience function. Like find, but only returns whether or not the search was successful.

  • __unittestL11310_438

  • __unittestL11323_439

  • __unittestL11335_440

  • any

    Checks if $(I _any) of the elements verifies $(D pred). $(D !any) can be used to verify that $(I none) of the elements verify $(D pred).

  • __unittestL11360_441

  • __unittestL11373_442

    $(D any) can also be used without a predicate, if its items can be evaluated to true or false in a conditional statement. $(D !any) can be a convenient way to quickly test that $(I none) of the elements of a range evaluate to true.

  • __unittestL11387_443

  • all

    Checks if $(I _all) of the elements verify $(D pred).

  • __unittestL11415_444

  • __unittestL11427_445

    $(D all) can also be used without a predicate, if its items can be evaluated to true or false in a conditional statement. This can be a convenient way to quickly evaluate that $(I _all) of the elements of a range are true.

  • __unittestL11432_447

  • __unittestL11438_449

  • topNCopy

    Copies the top $(D n) elements of the input range $(D source) into the random-access range $(D target), where $(D n = target.length). Elements of $(D source) are not touched. If $(D sorted) is $(D true), the target is sorted. Otherwise, the target respects the $(WEB en.wikipedia.org/wiki/Binary_heap, heap property).

  • __unittestL11470_450

  • __unittestL11478_451

  • SetUnion

    Lazily computes the union of two or more ranges $(D rs). The ranges are assumed to be sorted by $(D less). Elements in the output are not unique; the length of the output is the sum of the lengths of the inputs. (The $(D length) member is offered if all ranges also have length.) The element types of all ranges must have a common type.

  • setUnion

    Lazily computes the union of two or more ranges $(D rs). The ranges are assumed to be sorted by $(D less). Elements in the output are not unique; the length of the output is the sum of the lengths of the inputs. (The $(D length) member is offered if all ranges also have length.) The element types of all ranges must have a common type.

  • __unittestL11618_452

  • SetIntersection

    Lazily computes the intersection of two or more input ranges $(D ranges). The ranges are assumed to be sorted by $(D less). The element types of the ranges must have a common type.

  • setIntersection

    Lazily computes the intersection of two or more input ranges $(D ranges). The ranges are assumed to be sorted by $(D less). The element types of the ranges must have a common type.

  • __unittestL11733_453

  • __unittestL11743_458

  • SetDifference

    Lazily computes the difference of $(D r1) and $(D r2). The two ranges are assumed to be sorted by $(D less). The element types of the two ranges must have a common type.

  • setDifference

    Lazily computes the difference of $(D r1) and $(D r2). The two ranges are assumed to be sorted by $(D less). The element types of the two ranges must have a common type.

  • __unittestL11844_459

  • SetSymmetricDifference

    Lazily computes the symmetric difference of $(D r1) and $(D r2), i.e. the elements that are present in exactly one of $(D r1) and $(D r2). The two ranges are assumed to be sorted by $(D less), and the output is also sorted by $(D less). The element types of the two ranges must have a common type.

  • setSymmetricDifference

    Lazily computes the symmetric difference of $(D r1) and $(D r2), i.e. the elements that are present in exactly one of $(D r1) and $(D r2). The two ranges are assumed to be sorted by $(D less), and the output is also sorted by $(D less). The element types of the two ranges must have a common type.

  • __unittestL11948_460

  • NWayUnion

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

  • nWayUnion

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

  • __unittestL12132_461

  • largestPartialIntersection

    Given a range of sorted forward ranges $(D ror), copies to $(D tgt) the elements that are common to most ranges, along with their number of occurrences. All ranges in $(D ror) are assumed to be sorted by $(D less). Only the most frequent $(D tgt.length) elements are returned.

  • largestPartialIntersectionWeighted

    Similar to $(D largestPartialIntersection), but associates a weight with each distinct element in the intersection.

  • __unittestL12251_462

  • __unittestL12274_463

  • __unittestL12295_464

  • __unittestL12316_465

  • nextPermutation

    Permutes $(D range) in-place to the next lexicographically greater permutation.

  • __unittestL12395_467

  • __unittestL12414_468

  • __unittestL12426_469

  • __unittestL12438_470

  • __unittestL12515_471

  • nextEvenPermutation

    Permutes $(D range) in-place to the next lexicographically greater $(I even) permutation.

  • __unittestL12647_473

  • __unittestL12659_474

  • __unittestL12667_475

  • __unittestL12680_476

  • __unittestL12696_477

    Even permutations are useful for generating coordinates of certain geometric shapes. Here's a non-trivial example:

  • cartesianProduct

    Lazily computes the Cartesian product of two or more ranges. The product is a _range of tuples of elements from each respective range.

  • __unittestL12788_479

  • __unittestL12801_480

  • __unittestL12814_481

  • __unittestL12833_482

  • __unittestL12869_483

  • __unittestL12893_484

  • cartesianProduct

  • __unittestL12996_485

  • __unittestL13025_487

  • among

    Find $(D value) _among $(D values), returning the 1-based index of the first matching value in $(D values), or $(D 0) if $(D value) is not _among $(D values). The predicate $(D pred) is used to compare values, and uses equality by default.

  • among

  • __unittestL13085_492

  • __unittestL13102_493

    Alternatively, $(D values) can be passed at compile-time, allowing for a more efficient search, but one that only supports matching on equality:

  • __unittestL13108_494