This module implements some common generic algorithms.
SortOrder = enum Descending, Ascending
proc `*`(x: int; order: SortOrder): int {...}{.inline, raises: [], tags: [].}
order == Descending
; if order == Ascending
then x is returned. x is supposed to be the result of a comparator, ie < 0
for less than, == 0
for equal, > 0
for greater than. proc fill[T](a: var openArray[T]; first, last: Natural; value: T)
a[first..last]
with value. proc fill[T](a: var openArray[T]; value: T)
proc reverse[T](a: var openArray[T]; first, last: Natural)
a[first..last]
. proc reverse[T](a: var openArray[T])
proc reversed[T](a: openArray[T]; first: Natural; last: int): seq[T]
proc reversed[T](a: openArray[T]): seq[T]
proc binarySearch[T, K](a: openArray[T]; key: K; cmp: proc (x: T; y: K): int {...}{.closure.}): int
binary search for key in a. Returns -1 if not found.
cmp is the comparator function to use, the expected return values are the same as that of system.cmp.
proc binarySearch[T](a: openArray[T]; key: T): int
proc smartBinarySearch[T](a: openArray[T]; key: T): int {...}{.deprecated.}
binarySearch
instead. proc lowerBound[T, K](a: openArray[T]; key: K; cmp: proc (x: T; k: K): int {...}{.closure.}): int
Returns a position to the first element in the a that is greater than key, or last if no such element is found. In other words if you have a sorted sequence and you call insert(thing, elm, lowerBound(thing, elm)) the sequence will still be sorted.
The first version uses cmp to compare the elements. The expected return values are the same as that of system.cmp. The second version uses the default comparison function cmp.
example:
var arr = @[1,2,3,5,6,7,8,9] arr.insert(4, arr.lowerBound(4)) # after running the above arr is `[1,2,3,4,5,6,7,8,9]`
proc lowerBound[T](a: openArray[T]; key: T): int
proc upperBound[T, K](a: openArray[T]; key: K; cmp: proc (x: T; k: K): int {...}{.closure.}): int
Returns a position to the first element in the a that is not less (i.e. greater or equal to) than key, or last if no such element is found. In other words if you have a sorted sequence and you call insert(thing, elm, upperBound(thing, elm)) the sequence will still be sorted.
The first version uses cmp to compare the elements. The expected return values are the same as that of system.cmp. The second version uses the default comparison function cmp.
example:
var arr = @[1,2,3,4,6,7,8,9] arr.insert(5, arr.upperBound(4)) # after running the above arr is `[1,2,3,4,5,6,7,8,9]`
proc upperBound[T](a: openArray[T]; key: T): int
proc sort[T](a: var openArray[T]; cmp: proc (x, y: T): int {...}{.closure.}; order = SortOrder.Ascending)
a.len div 2
. Currently Nim does not support a sensible default argument for cmp
, so you have to provide one of your own. However, the system.cmp
procs can be used:sort(myIntArray, system.cmp[int]) # do not use cmp[string] here as we want to use the specialized # overload: sort(myStrArray, system.cmp)
You can inline adhoc comparison procs with the do notation. Example:
people.sort do (x, y: Person) -> int: result = cmp(x.surname, y.surname) if result == 0: result = cmp(x.name, y.name)
proc sorted[T](a: openArray[T]; cmp: proc (x, y: T): int {...}{.closure.}; order = SortOrder.Ascending): seq[T]
proc isSorted[T](a: openArray[T]; cmp: proc (x, y: T): int {...}{.closure.}; order = SortOrder.Ascending): bool
proc product[T](x: openArray[seq[T]]): seq[seq[T]]
proc nextPermutation[T](x: var openArray[T]): bool {...}{.discardable.}
x
. The result is whether a permutation happened, otherwise we have reached the last-ordered permutation.var v = @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] v.nextPermutation() echo v # @[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
proc prevPermutation[T](x: var openArray[T]): bool {...}{.discardable.}
x
. The result is whether a permutation happened, otherwise we have reached the first-ordered permutation.var v = @[0, 1, 2, 3, 4, 5, 6, 7, 9, 8] v.prevPermutation() echo v # @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
proc rotateLeft[T](arg: var openArray[T]; slice: HSlice[int, int]; dist: int): int
dist
. Specifically, rotateLeft
rotates the elements at slice
by dist
positions. The element at index slice.a + dist
will be at index slice.a
. The element at index slice.b
will be at slice.a + dist -1
. The element at index slice.a
will be at slice.b + 1 - dist
. The element at index slice.a + dist - 1
will be at slice.b
. proc rotateLeft[T](arg: var openArray[T]; dist: int): int
arg
, and not just on a part of it. proc rotatedLeft[T](arg: openArray[T]; slice: HSlice[int, int]; dist: int): seq[T]
rotateLeft
, just with the difference that it does not modify the argument. It creates a new seq
instead proc rotatedLeft[T](arg: openArray[T]; dist: int): seq[T]
rotateLeft
, just with the difference that it does not modify the argument. It creates a new seq
instead template sortedByIt(seq1, op: untyped): untyped
Convenience template around the sorted
proc to reduce typing.
The template injects the it
variable which you can use directly in an expression. Example:
type Person = tuple[name: string, age: int] var p1: Person = (name: "p1", age: 60) p2: Person = (name: "p2", age: 20) p3: Person = (name: "p3", age: 30) p4: Person = (name: "p4", age: 30) people = @[p1,p2,p4,p3] echo people.sortedByIt(it.name)
Because the underlying cmp()
is defined for tuples you can do a nested sort like in the following example:
echo people.sortedByIt((it.age, it.name))
© 2006–2018 Andreas Rumpf
Licensed under the MIT License.
https://nim-lang.org/docs/algorithm.html