This module implements some common generic algorithms.
基本の用法
import algorithm type People = tuple year: int name: string var a: seq[People] a.add((2000, "John")) a.add((2005, "Marie")) a.add((2010, "Jane")) # Sorting with default system.cmp a.sort() assert a == @[(year: 2000, name: "John"), (year: 2005, name: "Marie"), (year: 2010, name: "Jane")] proc myCmp(x, y: People): int = if x.name < y.name: -1 else: 1 # Sorting with custom proc a.sort(myCmp) assert a == @[(year: 2010, name: "Jane"), (year: 2000, name: "John"), (year: 2005, name: "Marie")]
関連
- sequtils モジュール for working with the built-in seq type
- tables モジュール for sorting tables
プロシージャ
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.用例:
assert `*`(-123, Descending) == 123 assert `*`(123, Descending) == -123 assert `*`(-123, Ascending) == -123 assert `*`(123, Ascending) == 123
ソース 編集 proc fill[T](a: var openArray[T]; first, last: Natural; value: T)
-
Fills the slice a[first..last] with value.
If an invalid range is passed, it raises IndexError.
用例:
var a: array[6, int] a.fill(1, 3, 9) assert a == [0, 9, 9, 9, 0, 0] a.fill(3, 5, 7) assert a == [0, 9, 9, 7, 7, 7] doAssertRaises(IndexError, a.fill(1, 7, 9))
ソース 編集 proc fill[T](a: var openArray[T]; value: T)
-
Fills the container a with value.
用例:
var a: array[6, int] a.fill(9) assert a == [9, 9, 9, 9, 9, 9] a.fill(4) assert a == [4, 4, 4, 4, 4, 4]
ソース 編集 proc reverse[T](a: var openArray[T]; first, last: Natural)
-
Reverses the slice a[first..last].
If an invalid range is passed, it raises IndexError.
関連:
- reversed proc reverse a slice and returns a seq[T]
- reversed proc reverse and returns a seq[T]
用例:
var a = [1, 2, 3, 4, 5, 6] a.reverse(1, 3) assert a == [1, 4, 3, 2, 5, 6] a.reverse(1, 3) assert a == [1, 2, 3, 4, 5, 6] doAssertRaises(IndexError, a.reverse(1, 7))
ソース 編集 proc reverse[T](a: var openArray[T])
-
Reverses the contents of the container a.
関連:
- reversed proc reverse a slice and returns a seq[T]
- reversed proc reverse and returns a seq[T]
用例:
var a = [1, 2, 3, 4, 5, 6] a.reverse() assert a == [6, 5, 4, 3, 2, 1] a.reverse() assert a == [1, 2, 3, 4, 5, 6]
ソース 編集 proc reversed[T](a: openArray[T]; first: Natural; last: int): seq[T]
-
Returns the reverse of the slice a[first..last].
If an invalid range is passed, it raises IndexError.
関連:
- reverse proc reverse a slice
- reverse proc
用例:
let a = [1, 2, 3, 4, 5, 6] b = a.reversed(1, 3) assert b == @[4, 3, 2]
ソース 編集 proc reversed[T](a: openArray[T]): seq[T]
-
Returns the reverse of the container a.
関連:
- reverse proc reverse a slice
- reverse proc
用例:
let a = [1, 2, 3, 4, 5, 6] b = reversed(a) assert b == @[6, 5, 4, 3, 2, 1]
ソース 編集 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.
用例:
assert binarySearch(["a", "b", "c", "d"], "d", system.cmp[string]) == 3 assert binarySearch(["a", "b", "d", "c"], "d", system.cmp[string]) == 2
ソース 編集 proc binarySearch[T](a: openArray[T]; key: T): int
-
Binary search for key in a. Returns -1 if not found.
用例:
assert binarySearch([0, 1, 2, 3, 4], 4) == 4 assert binarySearch([0, 1, 4, 2, 3], 4) == 2
ソース 編集 proc smartBinarySearch[T](a: openArray[T]; key: T): int {...}{. deprecated: "Deprecated since v0.18.1; Use \'binarySearch\'".}
- ソース 編集
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.
If an invalid range is passed, it raises IndexError.
The version uses cmp to compare the elements. The expected return values are the same as that of system.cmp.
関連:
- upperBound proc sorted by cmp in the specified order
- upperBound proc
用例:
var arr = @[1, 2, 3, 5, 6, 7, 8, 9] assert arr.lowerBound(3, system.cmp[int]) == 2 assert arr.lowerBound(4, system.cmp[int]) == 3 assert arr.lowerBound(5, system.cmp[int]) == 3 arr.insert(4, arr.lowerBound(4, system.cmp[int])) assert arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]
ソース 編集 proc lowerBound[T](a: openArray[T]; key: T): 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 version uses the default comparison function cmp.
関連:
- upperBound proc sorted by cmp in the specified order
- upperBound proc
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.
If an invalid range is passed, it raises IndexError.
The version uses cmp to compare the elements. The expected return values are the same as that of system.cmp.
関連:
- lowerBound proc sorted by cmp in the specified order
- lowerBound proc
用例:
var arr = @[1, 2, 3, 5, 6, 7, 8, 9] assert arr.upperBound(2, system.cmp[int]) == 2 assert arr.upperBound(3, system.cmp[int]) == 3 assert arr.upperBound(4, system.cmp[int]) == 3 arr.insert(4, arr.upperBound(3, system.cmp[int])) assert arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]
ソース 編集 proc upperBound[T](a: openArray[T]; key: T): 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 version uses the default comparison function cmp.
関連:
- lowerBound proc sorted by cmp in the specified order
- lowerBound proc
proc sort[T](a: var openArray[T]; order = SortOrder.Ascending)
-
Shortcut version of sort that uses system.cmp[T] as the comparison function.
関連:
- sort func
- sorted proc sorted by cmp in the specified order
- sorted proc
- sortedByIt template
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.
関連:
用例:
let a = [2, 3, 1, 5, 4] b = sorted(a, system.cmp[int]) c = sorted(a, system.cmp[int], Descending) d = sorted(["adam", "dande", "brian", "cat"], system.cmp[string]) assert b == @[1, 2, 3, 4, 5] assert c == @[5, 4, 3, 2, 1] assert d == @["adam", "brian", "cat", "dande"]
ソース 編集 proc sorted[T](a: openArray[T]; order = SortOrder.Ascending): seq[T]
-
Shortcut version of sorted that uses system.cmp[T] as the comparison function.
関連:
用例:
let a = [2, 3, 1, 5, 4] b = sorted(a) c = sorted(a, Descending) d = sorted(["adam", "dande", "brian", "cat"]) assert b == @[1, 2, 3, 4, 5] assert c == @[5, 4, 3, 2, 1] assert d == @["adam", "brian", "cat", "dande"]
ソース 編集 proc isSorted[T](a: openArray[T]; order = SortOrder.Ascending): bool
-
Shortcut version of isSorted that uses system.cmp[T] as the comparison function.
関連:
用例:
let a = [2, 3, 1, 5, 4] b = [1, 2, 3, 4, 5] c = [5, 4, 3, 2, 1] d = ["adam", "brian", "cat", "dande"] e = ["adam", "dande", "brian", "cat"] assert isSorted(a) == false assert isSorted(b) == true assert isSorted(c) == false assert isSorted(c, Descending) == true assert isSorted(d) == true assert isSorted(e) == false
ソース 編集 proc product[T](x: openArray[seq[T]]): seq[seq[T]]
-
Produces the Cartesian product of the array. Warning: complexity may explode.
用例:
assert product(@[@[1], @[2]]) == @[@[1, 2]] assert product(@[@["A", "K"], @["Q"]]) == @[@["K", "Q"], @["A", "Q"]]
ソース 編集 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 last.
関連:
用例:
var v = @[0, 1, 2, 3] assert v.nextPermutation() == true assert v == @[0, 1, 3, 2] assert v.nextPermutation() == true assert v == @[0, 2, 1, 3] assert v.prevPermutation() == true assert v == @[0, 1, 3, 2] v = @[3, 2, 1, 0] assert v.nextPermutation() == false assert v == @[3, 2, 1, 0]
ソース 編集 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] assert v.prevPermutation() == false assert v == @[0, 1, 2, 3] assert v.nextPermutation() == true assert v == @[0, 1, 3, 2] assert v.prevPermutation() == true assert v == @[0, 1, 2, 3]
ソース 編集 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. If an invalid range (HSlice) is passed, it raises IndexError.
- 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.
関連:
- rotateLeft proc for a version which rotates the whole container
- rotatedLeft proc for a version which returns a seq[T]
用例:
var a = [0, 1, 2, 3, 4, 5] a.rotateLeft(1 .. 4, 3) assert a == [0, 4, 1, 2, 3, 5] a.rotateLeft(1 .. 4, 3) assert a == [0, 3, 4, 1, 2, 5] a.rotateLeft(1 .. 4, -3) assert a == [0, 4, 1, 2, 3, 5] doAssertRaises(IndexError, a.rotateLeft(1 .. 7, 2))
ソース 編集 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.
関連:
- rotateLeft proc for a version which rotates a range
- rotatedLeft proc for a version which returns a seq[T]
用例:
var a = [1, 2, 3, 4, 5] a.rotateLeft(2) assert a == [3, 4, 5, 1, 2] a.rotateLeft(4) assert a == [2, 3, 4, 5, 1] a.rotateLeft(-6) assert a == [1, 2, 3, 4, 5]
ソース 編集 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.
Elements outside of slice will be left unchanged. If an invalid range (HSlice) is passed, it raises IndexError.
- 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.
関連:
- rotateLeft proc for the in-place version of this proc
- rotatedLeft proc for a version which rotates the whole container
用例:
var a = @[1, 2, 3, 4, 5] a = rotatedLeft(a, 1 .. 4, 3) assert a == @[1, 5, 2, 3, 4] a = rotatedLeft(a, 1 .. 3, 2) assert a == @[1, 3, 5, 2, 4] a = rotatedLeft(a, 1 .. 3, -2) assert a == @[1, 5, 2, 3, 4]
ソース 編集 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.
関連:
- rotateLeft proc for the in-place version of this proc
- rotatedLeft proc for a version which rotates a range
用例:
var a = @[1, 2, 3, 4, 5] a = rotatedLeft(a, 2) assert a == @[3, 4, 5, 1, 2] a = rotatedLeft(a, 4) assert a == @[2, 3, 4, 5, 1] a = rotatedLeft(a, -6) assert a == @[1, 2, 3, 4, 5]
ソース 編集
関数
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. 用例:
people.sort do (x, y: Person) -> int: result = cmp(x.surname, y.surname) if result == 0: result = cmp(x.name, y.name)
関連:
- sort proc
- sorted proc sorted by cmp in the specified order
- sorted proc
- sortedByIt template
用例:
var d = ["boo", "fo", "barr", "qux"] proc myCmp(x, y: string): int = if x.len() > y.len() or x.len() == y.len(): 1 else: -1 sort(d, myCmp) assert d == ["fo", "qux", "boo", "barr"]
ソース 編集 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. Requires O(n) time.
関連:
用例:
let a = [2, 3, 1, 5, 4] b = [1, 2, 3, 4, 5] c = [5, 4, 3, 2, 1] d = ["adam", "brian", "cat", "dande"] e = ["adam", "dande", "brian", "cat"] assert isSorted(a) == false assert isSorted(b) == true assert isSorted(c) == false assert isSorted(c, Descending) == true assert isSorted(d) == true assert isSorted(e) == false
ソース 編集
テンプレート
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 do a nested sort.
関連:
- sort func
- sort proc
- sorted proc sorted by cmp in the specified order
- sorted proc
用例:
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] assert people.sortedByIt(it.name) == @[(name: "p1", age: 60), (name: "p2", age: 20), (name: "p3", age: 30), (name: "p4", age: 30)] assert people.sortedByIt((it.age, it.name)) == @[(name: "p2", age: 20), (name: "p3", age: 30), (name: "p4", age: 30), (name: "p1", age: 60)]
ソース 編集