algorithm

This module implements some common generic algorithms.

Types

SortOrder = enum
  Descending, Ascending
  Source Edit

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, i.e.

< 0 for less than,
== 0 for equal,
> 0 for greater than.

  Source Edit
proc fill[T](a: var openArray[T]; first, last: Natural; value: T)
fills the slice a[first..last] with value.

Examples:

var a: array[6, int]
a.fill(1, 3, 9)
doAssert a == [0, 9, 9, 9, 0, 0]
  Source Edit
proc fill[T](a: var openArray[T]; value: T)
fills the container a with value.

Examples:

var a: array[6, int]
a.fill(9)
doAssert a == [9, 9, 9, 9, 9, 9]
  Source Edit
proc reverse[T](a: var openArray[T]; first, last: Natural)
reverses the slice a[first..last].

Examples:

var a = [1, 2, 3, 4, 5, 6]
a.reverse(1, 3)
doAssert a == [1, 4, 3, 2, 5, 6]
  Source Edit
proc reverse[T](a: var openArray[T])
reverses the contents of the container a.

Examples:

var a = [1, 2, 3, 4, 5, 6]
a.reverse()
doAssert a == [6, 5, 4, 3, 2, 1]
  Source Edit
proc reversed[T](a: openArray[T]; first: Natural; last: int): seq[T]
returns the reverse of the slice a[first..last].

Examples:

let
  a = [1, 2, 3, 4, 5, 6]
  b = reversed(a, 1, 3)
doAssert b == @[4, 3, 2]
  Source Edit
proc reversed[T](a: openArray[T]): seq[T]
returns the reverse of the container a.

Examples:

let
  a = [1, 2, 3, 4, 5, 6]
  b = reversed(a)
doAssert b == @[6, 5, 4, 3, 2, 1]
  Source Edit
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.

  Source Edit
proc binarySearch[T](a: openArray[T]; key: T): int
Binary search for key in a. Returns -1 if not found.   Source Edit
proc smartBinarySearch[T](a: openArray[T]; key: T): int {...}{.deprecated.}
Deprecated since version 0.18.1; Use binarySearch instead.   Source Edit
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.

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 Edit
proc lowerBound[T](a: openArray[T]; key: T): int
  Source Edit
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.

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]`
  Source Edit
proc upperBound[T](a: openArray[T]; key: T): int
  Source Edit
proc sort[T](a: var openArray[T]; order = SortOrder.Ascending)
Shortcut version of sort that uses system.cmp[T] as the comparison function.   Source Edit
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.

Examples:

let
  a = [2, 3, 1, 5, 4]
  b = sorted(a, system.cmp)
  c = sorted(a, system.cmp, Descending)
doAssert b == @[1, 2, 3, 4, 5]
doAssert c == @[5, 4, 3, 2, 1]
  Source Edit
proc sorted[T](a: openArray[T]; order = SortOrder.Ascending): seq[T]
Shortcut version of sorted that uses system.cmp[T] as the comparison function.   Source Edit
proc isSorted[T](a: openArray[T]; order = SortOrder.Ascending): bool
Shortcut version of isSorted that uses system.cmp[T] as the comparison function.   Source Edit
proc product[T](x: openArray[seq[T]]): seq[seq[T]]
produces the Cartesian product of the array. Warning: complexity may explode.   Source Edit
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 # @[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
  Source Edit
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 # @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  Source Edit
proc rotateLeft[T](arg: var openArray[T]; slice: HSlice[int, int]; dist: int): int {...}{.
    discardable.}
performs a left rotation on a range of elements. If you want to rotate right, use a negative 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.

Elements outside of slice will be left unchanged. The time complexity is linear to slice.b - slice.a + 1.

slice
The indices of the element range that should be rotated.
dist
The distance in amount of elements that the data should be rotated. Can be negative, can be any number.
var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
list.rotateLeft(1 .. 8, 3)
doAssert list == [0, 4, 5, 6, 7, 8, 1, 2, 3, 9, 10]
  Source Edit
proc rotateLeft[T](arg: var openArray[T]; dist: int): int {...}{.discardable.}
Default arguments for slice, so that this procedure operates on the entire arg, and not just on a part of it.

Examples:

var a = [1, 2, 3, 4, 5]
a.rotateLeft(2)
doAssert a == [3, 4, 5, 1, 2]
  Source Edit
proc rotatedLeft[T](arg: openArray[T]; slice: HSlice[int, int]; dist: int): seq[T]
Same as rotateLeft, just with the difference that it does not modify the argument. It creates a new seq instead.   Source Edit
proc rotatedLeft[T](arg: openArray[T]; dist: int): seq[T]
Same as rotateLeft, just with the difference that it does not modify the argument. It creates a new seq instead.   Source Edit

Funcs

func sort[T](a: var openArray[T]; cmp: proc (x, y: T): int {...}{.closure.};
            order = SortOrder.Ascending)
Default Nim sort (an implementation of merge 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. If you do not wish to provide your own cmp, you may use system.cmp or instead call the overloaded version of sort, which uses system.cmp.
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 Edit
func isSorted[T](a: openArray[T]; cmp: proc (x, y: T): int {...}{.closure.};
                order = SortOrder.Ascending): bool
checks to see whether a is already sorted in order using cmp for the comparison. Parameters identical to sort.   Source Edit

Templates

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))
  Source Edit