This module implements some common generic algorithms.

Types

TSortOrder = enum Descending, Ascending: sort order

Procs

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])

# do not use cmp[string] here as we want to use the specialized
# overload:
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.

Module algorithm

Types

Procs