This module implements some common generic algorithms.
Procs
proc `*`(x: int; order: SortOrder): int {.inline, raises: [], tags: [].}
- flips x if 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. Source
proc reverse[T](a: var openArray[T]; first, last: Natural)
- reverses the array a[first..last]. Source
proc reverse[T](a: var openArray[T])
- reverses the array a. Source
proc reversed[T](a: openArray[T]; first, last: Natural): seq[T]
- returns the reverse of the array a[first..last]. Source
proc reversed[T](a: openArray[T]): seq[T]
- returns the reverse of the array a. Source
proc binarySearch[T](a: openArray[T]; key: T): int
- binary search for key in a. Returns -1 if not found. Source
proc smartBinarySearch[T](a: openArray[T]; key: T): int
- a.len must be a power of 2 for this to work. Source
proc lowerBound[T](a: openArray[T]; key: T; cmp: proc (x, y: T): int {.closure.}): int
-
same as binarySearch except that if key is not in a then this returns the location where key would be if it were. In other words if you have a sorted sequence and you call insert(thing, elm, lowerBound(thing, elm)) the sequence will still be sorted.
cmp is the comparator function to use, the expected return values are the same as that of system.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]
Source proc lowerBound[T](a: openArray[T]; key: T): int
- Source
proc sort[T](a: var openArray[T]; cmp: proc (x, y: T): int {.closure.}; order = SortOrder.Ascending)
-
Default Nim sort. The sorting is guaranteed to be stable and the worst case is guaranteed to be O(n log n). The current implementation uses an iterative mergesort to achieve this. It uses a temporary sequence of length 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)
Source proc sorted[T](a: openArray[T]; cmp: proc (x, y: T): int {.closure.}; order = SortOrder.Ascending): seq[T]
- returns a sorted by cmp in the specified order. Source
proc product[T](x: openArray[seq[T]]): seq[seq[T]]
- produces the Cartesian product of the array. Warning: complexity may explode. Source
proc nextPermutation[T](x: var openArray[T]): bool {.discardable.}
-
Calculates the next lexicographic permutation, directly modifying 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
Source proc prevPermutation[T](x: var openArray[T]): bool {.discardable.}
-
Calculates the previous lexicographic permutation, directly modifying 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
Source
Templates
template sortedByIt(seq1, op: expr): expr
-
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))
Source