This module implements some common generic algorithms.
TSortOrder = enum
Descending, Ascending
-
sort order
proc `*`(x: int; order: TSortOrder): 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.
proc reverse[T](a: var openArray[T]; first, last: int)
-
reverses the array a[first..last].
proc reverse[T](a: var openArray[T])
-
reverses the array a.
proc binarySearch[T](a: openArray[T]; key: T): int
-
binary search for key in a. Returns -1 if not found.
proc smartBinarySearch[T](a: openArray[T]; key: T): int
-
a.len must be a power of 2 for this to work.
proc sort[T](a: var openArray[T]; cmp: proc (x, y: T): int {.closure.};
order = TSortOrder.Ascending)
-
Default Nimrod 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 Nimrod 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])
sort(myStrArray, system.cmp)
proc product[T](x: openArray[seq[T]]): seq[seq[T]]
-
produces the Cartesian product of the array. Warning: complexity may explode.