diff options
| -rw-r--r-- | lib/pure/algorithm.nim | 161 |
1 files changed, 103 insertions, 58 deletions
diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 366a85ab5..7f3d5e936 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -10,14 +10,17 @@ ## This module implements some common generic algorithms. type - SortOrder* = enum ## sort order + SortOrder* = enum Descending, Ascending proc `*`*(x: int, order: SortOrder): int {.inline.} = - ## 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*. + ## 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*. var y = order.ord - 1 result = (x xor y) - y @@ -28,16 +31,28 @@ template fillImpl[T](a: var openArray[T], first, last: int, value: T) = inc(x) proc fill*[T](a: var openArray[T], first, last: Natural, value: T) = - ## fills the array ``a[first..last]`` with `value`. + ## fills the slice ``a[first..last]`` with ``value``. + runnableExamples: + var a: array[6, int] + a.fill(1, 3, 9) + doAssert a == [0, 9, 9, 9, 0, 0] fillImpl(a, first, last, value) proc fill*[T](a: var openArray[T], value: T) = - ## fills the array `a` with `value`. + ## fills the container ``a`` with ``value``. + runnableExamples: + var a: array[6, int] + a.fill(9) + doAssert a == [9, 9, 9, 9, 9, 9] fillImpl(a, 0, a.high, value) proc reverse*[T](a: var openArray[T], first, last: Natural) = - ## reverses the array ``a[first..last]``. + ## reverses the slice ``a[first..last]``. + runnableExamples: + var a = [1, 2, 3, 4, 5, 6] + a.reverse(1, 3) + doAssert a == [1, 4, 3, 2, 5, 6] var x = first var y = last while x < y: @@ -46,11 +61,20 @@ proc reverse*[T](a: var openArray[T], first, last: Natural) = inc(x) proc reverse*[T](a: var openArray[T]) = - ## reverses the array `a`. + ## reverses the contents of the container ``a``. + runnableExamples: + var a = [1, 2, 3, 4, 5, 6] + a.reverse() + doAssert a == [6, 5, 4, 3, 2, 1] reverse(a, 0, max(0, a.high)) proc reversed*[T](a: openArray[T], first: Natural, last: int): seq[T] = - ## returns the reverse of the array `a[first..last]`. + ## returns the reverse of the slice ``a[first..last]``. + runnableExamples: + let + a = [1, 2, 3, 4, 5, 6] + b = reversed(a, 1, 3) + doAssert b == @[4, 3, 2] assert last >= first-1 var i = last - first var x = first.int @@ -61,14 +85,19 @@ proc reversed*[T](a: openArray[T], first: Natural, last: int): seq[T] = inc(x) proc reversed*[T](a: openArray[T]): seq[T] = - ## returns the reverse of the array `a`. + ## returns the reverse of the container ``a``. + runnableExamples: + let + a = [1, 2, 3, 4, 5, 6] + b = reversed(a) + doAssert b == @[6, 5, 4, 3, 2, 1] reversed(a, 0, a.high) 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. + ## Binary search for ``key`` in ``a``. Returns -1 if not found. ## - ## `cmp` is the comparator function to use, the expected return values are + ## ``cmp`` is the comparator function to use, the expected return values are ## the same as that of system.cmp. if a.len == 0: return -1 @@ -111,7 +140,7 @@ proc binarySearch*[T, K](a: openArray[T], key: K, if result >= len or cmp(a[result], key) != 0: result = -1 proc binarySearch*[T](a: openArray[T], key: T): int = - ## binary search for `key` in `a`. Returns -1 if not found. + ## Binary search for ``key`` in ``a``. Returns -1 if not found. binarySearch(a, key, cmp[T]) proc smartBinarySearch*[T](a: openArray[T], key: T): int {.deprecated.} = @@ -122,16 +151,17 @@ const onlySafeCode = true 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)) + ## 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`. + ## 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:: + ## .. code-block:: nim ## ## var arr = @[1,2,3,5,6,7,8,9] ## arr.insert(4, arr.lowerBound(4)) @@ -151,17 +181,17 @@ proc lowerBound*[T, K](a: openArray[T], key: K, cmp: proc(x: T, k: K): int {.clo proc lowerBound*[T](a: openArray[T], key: T): int = lowerBound(a, key, cmp[T]) 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. + ## 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)) + ## ``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`. + ## 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:: + ## .. code-block:: nim ## ## var arr = @[1,2,3,4,6,7,8,9] ## arr.insert(5, arr.upperBound(4)) @@ -268,7 +298,7 @@ func sort*[T](a: var openArray[T], s = s*2 func sort*[T](a: var openArray[T], order = SortOrder.Ascending) = - ## Sort an openarray in-place with a default lexicographical ordering. + ## sorts an openarray in-place with a default lexicographical ordering. runnableExamples: var s = @[1,3,2,5,4] s.sort @@ -277,14 +307,21 @@ func sort*[T](a: var openArray[T], order = SortOrder.Ascending) = func 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`. + ## returns ``a`` sorted by ``cmp`` in the specified ``order``. + runnableExamples: + 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] result = newSeq[T](a.len) for i in 0 .. a.high: result[i] = a[i] sort(result, cmp, order) func sorted*[T](a: openArray[T], order = SortOrder.Ascending): seq[T] = - ## Returns `a` sorted with default lexicographical ordering + ## returns ``a`` sorted with default lexicographical ordering. runnableExamples: let orig = @[2,3,1,2] let copy = orig.sorted() @@ -328,16 +365,16 @@ template sortedByIt*(seq1, op: untyped): untyped = 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` + ## checks to see whether ``a`` is already sorted in ``order`` + ## using ``cmp`` for the comparison. Parameters identical + ## to ``sort``. result = true for i in 0..<len(a)-1: if cmp(a[i],a[i+1]) * order > 0: return false func isSorted*[T](a: openArray[T], order = SortOrder.Ascending): bool = - ## Checks whether `a` is sorted with a default lexicographical ordering + ## checks whether ``a`` is sorted with a default lexicographical ordering. runnableExamples: let test = @[1,1,2,3,5,8] doAssert test.isSorted() @@ -377,7 +414,7 @@ proc product*[T](x: openArray[seq[T]]): seq[seq[T]] = indexes[index] -= 1 proc nextPermutation*[T](x: var openarray[T]): bool {.discardable.} = - ## Calculates the next lexicographic permutation, directly modifying ``x``. + ## calculates the next lexicographic permutation, directly modifying ``x``. ## The result is whether a permutation happened, otherwise we have reached ## the last-ordered permutation. ## @@ -406,8 +443,8 @@ proc nextPermutation*[T](x: var openarray[T]): bool {.discardable.} = result = true 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 + ## calculates the previous lexicographic permutation, directly modifying + ## ``x``. The result is whether a permutation happened, otherwise we have ## reached the first-ordered permutation. ## ## .. code-block:: nim @@ -517,48 +554,56 @@ proc rotatedInternal[T](arg: openarray[T]; first, middle, last: int): seq[T] = for i in last ..< arg.len: result[i] = arg[i] -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``. - # - ## Elements outsize of ``slice`` will be left unchanged. +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. + ## 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. + ## The distance in amount of elements that the data should be rotated. + ## Can be negative, can be any number. ## ## .. code-block:: nim - ## 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] + ## + ## 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] let sliceLen = slice.b + 1 - slice.a let distLeft = ((dist mod sliceLen) + sliceLen) mod sliceLen arg.rotateInternal(slice.a, slice.a+distLeft, slice.b + 1) -proc rotateLeft*[T](arg: var openarray[T]; dist: int): int = - ## default arguments for slice, so that this procedure operates on the entire +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. + runnableExamples: + var a = [1, 2, 3, 4, 5] + a.rotateLeft(2) + doAssert a == [3, 4, 5, 1, 2] let arglen = arg.len let distLeft = ((dist mod arglen) + arglen) mod arglen arg.rotateInternal(0, distLeft, arglen) 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 + ## Same as ``rotateLeft``, just with the difference that it does + ## not modify the argument. It creates a new ``seq`` instead. let sliceLen = slice.b + 1 - slice.a let distLeft = ((dist mod sliceLen) + sliceLen) mod sliceLen arg.rotatedInternal(slice.a, slice.a+distLeft, slice.b+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 + ## Same as ``rotateLeft``, just with the difference that it does + ## not modify the argument. It creates a new ``seq`` instead. let arglen = arg.len let distLeft = ((dist mod arglen) + arglen) mod arglen arg.rotatedInternal(0, distLeft, arg.len) |