/Nim

# Module algorithm

This module implements some common generic algorithms.

## Types

```SortOrder = enum
Descending, Ascending```
sort order

## 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.
`proc fill[T](a: var openArray[T]; first, last: Natural; value: T)`
fills the array `a[first..last]` with value.
`proc fill[T](a: var openArray[T]; value: T)`
fills the array a with value.
`proc reverse[T](a: var openArray[T]; first, last: Natural)`
reverses the array `a[first..last]`.
`proc reverse[T](a: var openArray[T])`
reverses the array a.
`proc reversed[T](a: openArray[T]; first: Natural; last: int): seq[T]`
returns the reverse of the array a[first..last].
`proc reversed[T](a: openArray[T]): seq[T]`
returns the reverse of the array a.
```proc binarySearch[T, K](a: openArray[T]; key: K;
cmp: proc (x: T; y: K): int {...}{.closure.}): int```

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.}`
Deprecated since version 0.18.1; Use `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)```
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`. 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
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]```
returns a sorted by cmp in the specified order.
```proc 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
`proc product[T](x: openArray[seq[T]]): seq[seq[T]]`
produces the Cartesian product of the array. Warning: complexity may explode.
`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]```
`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]```
`proc rotateLeft[T](arg: var openArray[T]; slice: HSlice[int, int]; dist: int): int`
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`.
`proc rotateLeft[T](arg: var openArray[T]; dist: int): int`
default arguments for slice, so that this procedure operates on the entire `arg`, and not just on a part of it.
`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
`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

## 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))`