Source Edit

This module implements some common generic algorithms on openArrays.

Basic usage

Example:

  1. import std/algorithm
  2. type People = tuple
  3. year: int
  4. name: string
  5. var a: seq[People]
  6. a.add((2000, "John"))
  7. a.add((2005, "Marie"))
  8. a.add((2010, "Jane"))
  9. # Sorting with default system.cmp
  10. a.sort()
  11. assert a == @[(year: 2000, name: "John"), (year: 2005, name: "Marie"),
  12. (year: 2010, name: "Jane")]
  13. proc myCmp(x, y: People): int =
  14. cmp(x.name, y.name)
  15. # Sorting with custom proc
  16. a.sort(myCmp)
  17. assert a == @[(year: 2010, name: "Jane"), (year: 2000, name: "John"),
  18. (year: 2005, name: "Marie")]

See also

Imports

since

Types

  1. SortOrder = enum
  2. Descending, Ascending

Source Edit

Procs

  1. proc `*`(x: int; order: SortOrder): int {.inline, ...raises: [], tags: [],
  2. forbids: [].}

Flips the sign of 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.

Example:

  1. assert -123 * Descending == 123
  2. assert 123 * Descending == -123
  3. assert -123 * Ascending == -123
  4. assert 123 * Ascending == 123

Source Edit

  1. proc binarySearch[T, K](a: openArray[T]; key: K;
  2. cmp: proc (x: T; y: K): int {.closure.}): int {.
  3. effectsOf: cmp.}

Binary search for key in a. Return the index of key or -1 if not found. Assumes that a is sorted according to cmp.

cmp is the comparator function to use, the expected return values are the same as those of system.cmp.

Example:

  1. assert binarySearch(["a", "b", "c", "d"], "d", system.cmp[string]) == 3
  2. assert binarySearch(["a", "b", "c", "d"], "c", system.cmp[string]) == 2

Source Edit

  1. proc binarySearch[T](a: openArray[T]; key: T): int

Binary search for key in a. Return the index of key or -1 if not found. Assumes that a is sorted.

Example:

  1. assert binarySearch([0, 1, 2, 3, 4], 4) == 4
  2. assert binarySearch([0, 1, 2, 3, 4], 2) == 2

Source Edit

  1. proc fill[T](a: var openArray[T]; first, last: Natural; value: T)

Assigns value to all elements of the slice a[first..last].

If an invalid range is passed, it raises IndexDefect.

Example:

  1. var a: array[6, int]
  2. a.fill(1, 3, 9)
  3. assert a == [0, 9, 9, 9, 0, 0]
  4. a.fill(3, 5, 7)
  5. assert a == [0, 9, 9, 7, 7, 7]
  6. doAssertRaises(IndexDefect, a.fill(1, 7, 9))

Source Edit

  1. proc fill[T](a: var openArray[T]; value: T)

Assigns value to all elements of the container a.

Example:

  1. var a: array[6, int]
  2. a.fill(9)
  3. assert a == [9, 9, 9, 9, 9, 9]
  4. a.fill(4)
  5. assert a == [4, 4, 4, 4, 4, 4]

Source Edit

  1. func isSorted[T](a: openArray[T]; cmp: proc (x, y: T): int {.closure.};
  2. order = SortOrder.Ascending): bool {.effectsOf: cmp.}

Checks to see whether a is already sorted in order using cmp for the comparison. The parameters are identical to sort. Requires O(n) time.

See also:

Example:

  1. let
  2. a = [2, 3, 1, 5, 4]
  3. b = [1, 2, 3, 4, 5]
  4. c = [5, 4, 3, 2, 1]
  5. d = ["adam", "brian", "cat", "dande"]
  6. e = ["adam", "dande", "brian", "cat"]
  7. assert isSorted(a) == false
  8. assert isSorted(b) == true
  9. assert isSorted(c) == false
  10. assert isSorted(c, Descending) == true
  11. assert isSorted(d) == true
  12. assert isSorted(e) == false

Source Edit

  1. proc isSorted[T](a: openArray[T]; order = SortOrder.Ascending): bool

Shortcut version of isSorted that uses system.cmp[T] as the comparison function.

See also:

Example:

  1. let
  2. a = [2, 3, 1, 5, 4]
  3. b = [1, 2, 3, 4, 5]
  4. c = [5, 4, 3, 2, 1]
  5. d = ["adam", "brian", "cat", "dande"]
  6. e = ["adam", "dande", "brian", "cat"]
  7. assert isSorted(a) == false
  8. assert isSorted(b) == true
  9. assert isSorted(c) == false
  10. assert isSorted(c, Descending) == true
  11. assert isSorted(d) == true
  12. assert isSorted(e) == false

Source Edit

  1. proc lowerBound[T, K](a: openArray[T]; key: K;
  2. cmp: proc (x: T; k: K): int {.closure.}): int {.
  3. effectsOf: cmp.}

Returns the index of the first element in a that is not less than (i.e. greater or equal to) 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. Assumes that a is sorted according to cmp.

If an invalid range is passed, it raises IndexDefect.

This version uses cmp to compare the elements. The expected return values are the same as those of system.cmp.

See also:

Example:

  1. var arr = @[1, 2, 3, 5, 6, 7, 8, 9]
  2. assert arr.lowerBound(3, system.cmp[int]) == 2
  3. assert arr.lowerBound(4, system.cmp[int]) == 3
  4. assert arr.lowerBound(5, system.cmp[int]) == 3
  5. arr.insert(4, arr.lowerBound(4, system.cmp[int]))
  6. assert arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]

Source Edit

  1. proc lowerBound[T](a: openArray[T]; key: T): int

Returns the index of the first element in a that is not less than (i.e. greater or equal to) 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. Assumes that a is sorted.

This version uses the default comparison function cmp.

See also:

Source Edit

  1. proc merge[T](result: var seq[T]; x, y: openArray[T]) {.inline.}

Shortcut version of merge that uses system.cmp[T] as the comparison function.

See also:

Example:

  1. let x = [5, 10, 15, 20, 25]
  2. let y = [50, 40, 30, 20, 10].sorted
  3. var merged: seq[int]
  4. merged.merge(x, y)
  5. assert merged.isSorted
  6. assert merged == @[5, 10, 10, 15, 20, 20, 25, 30, 40, 50]

Source Edit

  1. proc merge[T](result: var seq[T]; x, y: openArray[T];
  2. cmp: proc (x, y: T): int {.closure.}) {.effectsOf: cmp.}

Merges two sorted openArray. x and y are assumed to be sorted. If you do not wish to provide your own cmp, you may use system.cmp or instead call the overloaded version of merge, which uses system.cmp.

Note: The original data of result is not cleared, new data is appended to result.

See also:

Example:

  1. let x = @[1, 3, 6]
  2. let y = @[2, 3, 4]
  3. block:
  4. var merged = @[7] # new data is appended to merged sequence
  5. merged.merge(x, y, system.cmp[int])
  6. assert merged == @[7, 1, 2, 3, 3, 4, 6]
  7. block:
  8. var merged = @[7] # if you only want new data, clear merged sequence first
  9. merged.setLen(0)
  10. merged.merge(x, y, system.cmp[int])
  11. assert merged.isSorted
  12. assert merged == @[1, 2, 3, 3, 4, 6]
  13. import std/sugar
  14. var res: seq[(int, int)]
  15. res.merge([(1, 1)], [(1, 2)], (a, b) => a[0] - b[0])
  16. assert res == @[(1, 1), (1, 2)]
  17. assert seq[int].default.dup(merge([1, 3], [2, 4])) == @[1, 2, 3, 4]

Source Edit

  1. 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.

If you start with an unsorted array/seq, the repeated permutations will not give you all permutations but stop with the last.

See also:

Example:

  1. var v = @[0, 1, 2, 3]
  2. assert v.nextPermutation() == true
  3. assert v == @[0, 1, 3, 2]
  4. assert v.nextPermutation() == true
  5. assert v == @[0, 2, 1, 3]
  6. assert v.prevPermutation() == true
  7. assert v == @[0, 1, 3, 2]
  8. v = @[3, 2, 1, 0]
  9. assert v.nextPermutation() == false
  10. assert v == @[3, 2, 1, 0]

Source Edit

  1. 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.

See also:

Example:

  1. var v = @[0, 1, 2, 3]
  2. assert v.prevPermutation() == false
  3. assert v == @[0, 1, 2, 3]
  4. assert v.nextPermutation() == true
  5. assert v == @[0, 1, 3, 2]
  6. assert v.prevPermutation() == true
  7. assert v == @[0, 1, 2, 3]

Source Edit

  1. proc product[T](x: openArray[seq[T]]): seq[seq[T]]

Produces the Cartesian product of the array. Every element of the result is a combination of one element from each seq in x, with the ith element coming from x[i].

Warning: complexity may explode.

Example:

  1. assert product(@[@[1], @[2]]) == @[@[1, 2]]
  2. assert product(@[@["A", "K"], @["Q"]]) == @[@["K", "Q"], @["A", "Q"]]

Source Edit

  1. proc reverse[T](a: var openArray[T])

Reverses the contents of the container a.

See also:

Example:

  1. var a = [1, 2, 3, 4, 5, 6]
  2. a.reverse()
  3. assert a == [6, 5, 4, 3, 2, 1]
  4. a.reverse()
  5. assert a == [1, 2, 3, 4, 5, 6]

Source Edit

  1. proc reverse[T](a: var openArray[T]; first, last: Natural)

Reverses the slice a[first..last].

If an invalid range is passed, it raises IndexDefect.

See also:

Example:

  1. var a = [1, 2, 3, 4, 5, 6]
  2. a.reverse(1, 3)
  3. assert a == [1, 4, 3, 2, 5, 6]
  4. a.reverse(1, 3)
  5. assert a == [1, 2, 3, 4, 5, 6]
  6. doAssertRaises(IndexDefect, a.reverse(1, 7))

Source Edit

  1. proc reversed[T](a: openArray[T]): seq[T] {.inline.}

Returns the elements of a in reverse order.

See also:

Example:

  1. assert [10, 11, 12].reversed == @[12, 11, 10]
  2. assert seq[string].default.reversed == @[]

Source Edit

  1. proc reversed[T](a: openArray[T]; first: Natural; last: int): seq[T] {.inline,
  2. ...deprecated: "use: `reversed(toOpenArray(a, first, last))`".}

Deprecated: use: `reversed(toOpenArray(a, first, last))`

Source Edit

  1. 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.

See also:

Example:

  1. var a = @[1, 2, 3, 4, 5]
  2. a = rotatedLeft(a, 2)
  3. assert a == @[3, 4, 5, 1, 2]
  4. a = rotatedLeft(a, 4)
  5. assert a == @[2, 3, 4, 5, 1]
  6. a = rotatedLeft(a, -6)
  7. assert a == @[1, 2, 3, 4, 5]

Source Edit

  1. proc rotatedLeft[T](arg: openArray[T]; slice: HSlice[int, int]; dist: int): seq[
  2. T]

Same as rotateLeft, just with the difference that it does not modify the argument. It creates a new seq instead.

Elements outside of slice will be left unchanged. If an invalid range (HSlice) is passed, it raises IndexDefect.

  • 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.

See also:

Example:

  1. var a = @[1, 2, 3, 4, 5]
  2. a = rotatedLeft(a, 1 .. 4, 3)
  3. assert a == @[1, 5, 2, 3, 4]
  4. a = rotatedLeft(a, 1 .. 3, 2)
  5. assert a == @[1, 3, 5, 2, 4]
  6. a = rotatedLeft(a, 1 .. 3, -2)
  7. assert a == @[1, 5, 2, 3, 4]

Source Edit

  1. proc rotateLeft[T](arg: var openArray[T]; dist: int): int {.discardable.}

Same as rotateLeft, but with default arguments for slice, so that this procedure operates on the entire arg, and not just on a part of it.

See also:

Example:

  1. var a = [1, 2, 3, 4, 5]
  2. a.rotateLeft(2)
  3. assert a == [3, 4, 5, 1, 2]
  4. a.rotateLeft(4)
  5. assert a == [2, 3, 4, 5, 1]
  6. a.rotateLeft(-6)
  7. assert a == [1, 2, 3, 4, 5]

Source Edit

  1. proc rotateLeft[T](arg: var openArray[T]; slice: HSlice[int, int]; dist: int): int {.
  2. 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. If an invalid range (HSlice) is passed, it raises IndexDefect.

  • 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.

See also:

Example:

  1. var a = [0, 1, 2, 3, 4, 5]
  2. a.rotateLeft(1 .. 4, 3)
  3. assert a == [0, 4, 1, 2, 3, 5]
  4. a.rotateLeft(1 .. 4, 3)
  5. assert a == [0, 3, 4, 1, 2, 5]
  6. a.rotateLeft(1 .. 4, -3)
  7. assert a == [0, 4, 1, 2, 3, 5]
  8. doAssertRaises(IndexDefect, a.rotateLeft(1 .. 7, 2))

Source Edit

  1. func sort[T](a: var openArray[T]; cmp: proc (x, y: T): int {.closure.};
  2. order = SortOrder.Ascending) {.effectsOf: cmp.}

Default Nim sort (an implementation of merge sort). The sorting is guaranteed to be stable (that is, equal elements stay in the same order) and the worst case is guaranteed to be O(n log n). Sorts by cmp in the specified order.

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.

  1. sort(myIntArray, system.cmp[int])
  2. # do not use cmp[string] here as we want to use the specialized
  3. # overload:
  4. sort(myStrArray, system.cmp)

You can inline adhoc comparison procs with the do notation. Example:

  1. people.sort do (x, y: Person) -> int:
  2. result = cmp(x.surname, y.surname)
  3. if result == 0:
  4. result = cmp(x.name, y.name)

See also:

Example:

  1. var d = ["boo", "fo", "barr", "qux"]
  2. proc myCmp(x, y: string): int =
  3. if x.len() > y.len() or x.len() == y.len(): 1
  4. else: -1
  5. sort(d, myCmp)
  6. assert d == ["fo", "qux", "boo", "barr"]

Source Edit

  1. proc sort[T](a: var openArray[T]; order = SortOrder.Ascending)

Shortcut version of sort that uses system.cmp[T] as the comparison function.

See also:

Source Edit

  1. proc sorted[T](a: openArray[T]; cmp: proc (x, y: T): int {.closure.};
  2. order = SortOrder.Ascending): seq[T] {.effectsOf: cmp.}

Returns a sorted by cmp in the specified order.

See also:

Example:

  1. let
  2. a = [2, 3, 1, 5, 4]
  3. b = sorted(a, system.cmp[int])
  4. c = sorted(a, system.cmp[int], Descending)
  5. d = sorted(["adam", "dande", "brian", "cat"], system.cmp[string])
  6. assert b == @[1, 2, 3, 4, 5]
  7. assert c == @[5, 4, 3, 2, 1]
  8. assert d == @["adam", "brian", "cat", "dande"]

Source Edit

  1. proc sorted[T](a: openArray[T]; order = SortOrder.Ascending): seq[T]

Shortcut version of sorted that uses system.cmp[T] as the comparison function.

See also:

Example:

  1. let
  2. a = [2, 3, 1, 5, 4]
  3. b = sorted(a)
  4. c = sorted(a, Descending)
  5. d = sorted(["adam", "dande", "brian", "cat"])
  6. assert b == @[1, 2, 3, 4, 5]
  7. assert c == @[5, 4, 3, 2, 1]
  8. assert d == @["adam", "brian", "cat", "dande"]

Source Edit

  1. proc upperBound[T, K](a: openArray[T]; key: K;
  2. cmp: proc (x: T; k: K): int {.closure.}): int {.
  3. effectsOf: cmp.}

Returns the index of the first element in 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, upperBound(thing, elm)) the sequence will still be sorted. Assumes that a is sorted according to cmp.

If an invalid range is passed, it raises IndexDefect.

This version uses cmp to compare the elements. The expected return values are the same as those of system.cmp.

See also:

Example:

  1. var arr = @[1, 2, 3, 5, 6, 7, 8, 9]
  2. assert arr.upperBound(2, system.cmp[int]) == 2
  3. assert arr.upperBound(3, system.cmp[int]) == 3
  4. assert arr.upperBound(4, system.cmp[int]) == 3
  5. arr.insert(4, arr.upperBound(3, system.cmp[int]))
  6. assert arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]

Source Edit

  1. proc upperBound[T](a: openArray[T]; key: T): int

Returns the index of the first element in 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, upperBound(thing, elm)) the sequence will still be sorted. Assumes that a is sorted.

This version uses the default comparison function cmp.

See also:

Source Edit

Templates

  1. 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.

Because the underlying cmp() is defined for tuples you can also do a nested sort.

See also:

Example:

  1. type Person = tuple[name: string, age: int]
  2. var
  3. p1: Person = (name: "p1", age: 60)
  4. p2: Person = (name: "p2", age: 20)
  5. p3: Person = (name: "p3", age: 30)
  6. p4: Person = (name: "p4", age: 30)
  7. people = @[p1, p2, p4, p3]
  8. assert people.sortedByIt(it.name) == @[(name: "p1", age: 60), (name: "p2",
  9. age: 20), (name: "p3", age: 30), (name: "p4", age: 30)]
  10. # Nested sort
  11. assert people.sortedByIt((it.age, it.name)) == @[(name: "p2", age: 20),
  12. (name: "p3", age: 30), (name: "p4", age: 30), (name: "p1", age: 60)]

Source Edit