diff options
Diffstat (limited to 'lib/pure/algorithm.nim')
| -rw-r--r-- | lib/pure/algorithm.nim | 897 |
1 files changed, 745 insertions, 152 deletions
diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index a1ab7be13..b12ed7cdd 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -1,31 +1,118 @@ # # # Nim's Runtime Library -# (c) Copyright 2012 Andreas Rumpf +# (c) Copyright 2015 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. # -## This module implements some common generic algorithms. +## This module implements some common generic algorithms on `openArray`s. +## +## Basic usage +## =========== +## -type - SortOrder* = enum ## sort order - Descending, Ascending +runnableExamples: + 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 = + cmp(x.name, y.name) + + # Sorting with custom proc + a.sort(myCmp) + assert a == @[(year: 2010, name: "Jane"), (year: 2000, name: "John"), + (year: 2005, name: "Marie")] + +## See also +## ======== +## * `sequtils module<sequtils.html>`_ for working with the built-in seq type +## * `tables module<tables.html>`_ for sorting tables + +import std/private/since -{.deprecated: [TSortOrder: SortOrder].} +when defined(nimPreviewSlimSystem): + import std/assertions +type + 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 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*. + runnableExamples: + assert -123 * Descending == 123 + assert 123 * Descending == -123 + assert -123 * Ascending == -123 + assert 123 * Ascending == 123 var y = order.ord - 1 result = (x xor y) - y -proc reverse*[T](a: var openArray[T], first, last: int) = - ## reverses the array ``a[first..last]``. +template fillImpl[T](a: var openArray[T], first, last: int, value: T) = + var x = first + while x <= last: + a[x] = value + inc(x) + +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`. + runnableExamples: + 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(IndexDefect, a.fill(1, 7, 9)) + fillImpl(a, first, last, value) + +proc fill*[T](a: var openArray[T], value: T) = + ## Assigns `value` to all elements of the container `a`. + runnableExamples: + 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] + fillImpl(a, 0, a.high, value) + + +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:** + ## * `reversed proc<#reversed,openArray[T],Natural,int>`_ reverse a slice and returns a `seq[T]` + ## * `reversed proc<#reversed,openArray[T]>`_ reverse and returns a `seq[T]` + runnableExamples: + 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(IndexDefect, a.reverse(1, 7)) var x = first var y = last while x < y: @@ -34,88 +121,217 @@ proc reverse*[T](a: var openArray[T], first, last: int) = inc(x) proc reverse*[T](a: var openArray[T]) = - ## reverses the array `a`. - reverse(a, 0, a.high) + ## Reverses the contents of the container `a`. + ## + ## **See also:** + ## * `reversed proc<#reversed,openArray[T],Natural,int>`_ reverse a slice and returns a `seq[T]` + ## * `reversed proc<#reversed,openArray[T]>`_ reverse and returns a `seq[T]` + runnableExamples: + 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] + # the max is needed, since a.high is -1 if a is empty + reverse(a, 0, max(0, a.high)) -proc reversed*[T](a: openArray[T], first, last: int): seq[T] = - ## returns the reverse of the array `a[first..last]`. - result = newSeq[T](last - first + 1) - var x = first - var y = last - while x <= last: - result[x] = a[y] - dec(y) - inc(x) +proc reversed*[T](a: openArray[T]): seq[T] {.inline.} = + ## Returns the elements of `a` in reverse order. + ## + ## **See also:** + ## * `reverse proc<#reverse,openArray[T]>`_ + runnableExamples: + assert [10, 11, 12].reversed == @[12, 11, 10] + assert seq[string].default.reversed == @[] + let n = a.len + result.setLen(n) + for i in 0..<n: result[i] = a[n - (i + 1)] + +proc reversed*[T](a: openArray[T], first: Natural, last: int): seq[T] + {.inline, deprecated: "use: `reversed(toOpenArray(a, first, last))`".} = + reversed(toOpenArray(a, first, last)) -proc reversed*[T](a: openArray[T]): seq[T] = - ## returns the reverse of the array `a`. - reversed(a, 0, a.high) +when defined(nimHasEffectsOf): + {.experimental: "strictEffects".} +else: + {.pragma: effectsOf.} + +proc binarySearch*[T, K](a: openArray[T], key: K, + cmp: proc (x: T, y: K): int {.closure.}): int {.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. + runnableExamples: + assert binarySearch(["a", "b", "c", "d"], "d", system.cmp[string]) == 3 + assert binarySearch(["a", "b", "c", "d"], "c", system.cmp[string]) == 2 + let len = a.len + + if len == 0: + return -1 + + if len == 1: + if cmp(a[0], key) == 0: + return 0 + else: + return -1 + + result = 0 + if (len and (len - 1)) == 0: + # when `len` is a power of 2, a faster shr can be used. + var step = len shr 1 + var cmpRes: int + while step > 0: + let i = result or step + cmpRes = cmp(a[i], key) + if cmpRes == 0: + return i + + if cmpRes < 0: + result = i + step = step shr 1 + if cmp(a[result], key) != 0: result = -1 + else: + var b = len + var cmpRes: int + while result < b: + var mid = (result + b) shr 1 + cmpRes = cmp(a[mid], key) + if cmpRes == 0: + return mid + + if cmpRes < 0: + result = mid + 1 + else: + b = mid + 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. - var b = len(a) - while result < b: - var mid = (result + b) div 2 - if a[mid] < key: result = mid + 1 - else: b = mid - if result >= len(a) or a[result] != key: result = -1 - -proc smartBinarySearch*[T](a: openArray[T], key: T): int = - ## ``a.len`` must be a power of 2 for this to work. - var step = a.len div 2 - while step > 0: - if a[result or step] <= key: - result = result or step - step = step shr 1 - if a[result] != key: result = -1 + ## Binary search for `key` in `a`. Return the index of `key` or -1 if not found. + ## Assumes that `a` is sorted. + runnableExamples: + assert binarySearch([0, 1, 2, 3, 4], 4) == 4 + assert binarySearch([0, 1, 2, 3, 4], 2) == 2 + binarySearch(a, key, cmp[T]) const onlySafeCode = true -proc lowerBound*[T](a: openArray[T], key: T, cmp: proc(x,y: T): int {.closure.}): int = - ## same as binarySearch except that if key is not in `a` then this - ## returns the location where `key` would be if it were. In other - ## words if you have a sorted sequence and you call - ## insert(thing, elm, lowerBound(thing, elm)) +proc lowerBound*[T, K](a: openArray[T], key: K, + cmp: proc(x: T, k: K): int {.closure.}): int {.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`. ## - ## `cmp` is the comparator function to use, the expected return values are - ## the same as that of system.cmp. + ## If an invalid range is passed, it raises `IndexDefect`. ## - ## example:: + ## This version uses `cmp` to compare the elements. + ## The expected return values are the same as those of `system.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]` + ## **See also:** + ## * `upperBound proc<#upperBound,openArray[T],K,proc(T,K)>`_ sorted by `cmp` in the specified order + ## * `upperBound proc<#upperBound,openArray[T],T>`_ + runnableExamples: + 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] result = a.low - var pos = result - var count, step: int - count = a.high - a.low + 1 + var count = a.high - a.low + 1 + var step, pos: int while count != 0: - pos = result - step = count div 2 - pos += step + step = count shr 1 + pos = result + step if cmp(a[pos], key) < 0: - pos.inc - result = pos + result = pos + 1 count -= step + 1 else: count = step proc lowerBound*[T](a: openArray[T], key: T): int = lowerBound(a, key, cmp[T]) -proc merge[T](a, b: var openArray[T], lo, m, hi: int, - cmp: proc (x, y: T): int {.closure.}, order: SortOrder) = - template `<-` (a, b: expr) = - when false: - a = b - elif onlySafeCode: - shallowCopy(a, b) + ## 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:** + ## * `upperBound proc<#upperBound,openArray[T],K,proc(T,K)>`_ sorted by `cmp` in the specified order + ## * `upperBound proc<#upperBound,openArray[T],T>`_ + +proc upperBound*[T, K](a: openArray[T], key: K, + cmp: proc(x: T, k: K): int {.closure.}): int {.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:** + ## * `lowerBound proc<#lowerBound,openArray[T],K,proc(T,K)>`_ sorted by `cmp` in the specified order + ## * `lowerBound proc<#lowerBound,openArray[T],T>`_ + runnableExamples: + 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] + result = a.low + var count = a.high - a.low + 1 + var step, pos: int + while count != 0: + step = count shr 1 + pos = result + step + if cmp(a[pos], key) <= 0: + result = pos + 1 + count -= step + 1 else: - copyMem(addr(a), addr(b), sizeof(T)) - # optimization: If max(left) <= min(right) there is nothing to do! - # 1 2 3 4 ## 5 6 7 8 + count = step + +proc upperBound*[T](a: openArray[T], key: T): int = upperBound(a, key, cmp[T]) + ## 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:** + ## * `lowerBound proc<#lowerBound,openArray[T],K,proc(T,K)>`_ sorted by `cmp` in the specified order + ## * `lowerBound proc<#lowerBound,openArray[T],T>`_ + +template `<-`(a, b) = + when defined(gcDestructors): + a = move b + elif onlySafeCode: + shallowCopy(a, b) + else: + copyMem(addr(a), addr(b), sizeof(T)) + +proc mergeAlt[T](a, b: var openArray[T], lo, m, hi: int, + cmp: proc (x, y: T): int {.closure.}, order: SortOrder) {.effectsOf: cmp.} = + # Optimization: If max(left) <= min(right) there is nothing to do! + # 1 2 3 4 ## 5 6 7 8 # -> O(n) for sorted arrays. - # On random data this safes up to 40% of merge calls + # On random data this saves up to 40% of mergeAlt calls. if cmp(a[m], a[m+1]) * order <= 0: return var j = lo # copy a[j..m] into b: @@ -149,80 +365,138 @@ proc merge[T](a, b: var openArray[T], lo, m, hi: int, else: if k < j: copyMem(addr(a[k]), addr(b[i]), sizeof(T)*(j-k)) -proc sort*[T](a: var openArray[T], +func sort*[T](a: var openArray[T], cmp: proc (x, y: T): int {.closure.}, - order = SortOrder.Ascending) = - ## Default Nim sort. The sorting is guaranteed to be stable and - ## the worst case is guaranteed to be O(n log n). + 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``. 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: - ## - ## .. code-block:: nim + ## 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) + ## ```nim + ## 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 - ## <manual.html#do-notation>`_. Example: - ## - ## .. code-block:: nim + ## <manual.html#procedures-do-notation>`_. Example: ## + ## ```nim ## people.sort do (x, y: Person) -> int: ## result = cmp(x.surname, y.surname) ## if result == 0: ## result = cmp(x.name, y.name) + ## ``` + ## + ## **See also:** + ## * `sort proc<#sort,openArray[T]>`_ + ## * `sorted proc<#sorted,openArray[T],proc(T,T)>`_ sorted by `cmp` in the specified order + ## * `sorted proc<#sorted,openArray[T]>`_ + ## * `sortedByIt template<#sortedByIt.t,untyped,untyped>`_ + runnableExamples: + 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"] var n = a.len - var b: seq[T] - newSeq(b, n div 2) + var b = newSeq[T](n div 2) var s = 1 while s < n: var m = n-1-s while m >= 0: - merge(a, b, max(m-s+1, 0), m, m+s, cmp, order) + mergeAlt(a, b, max(m-s+1, 0), m, m+s, cmp, order) dec(m, s*2) s = s*2 +proc sort*[T](a: var openArray[T], order = SortOrder.Ascending) = sort[T](a, + system.cmp[T], order) + ## Shortcut version of `sort` that uses `system.cmp[T]` as the comparison function. + ## + ## **See also:** + ## * `sort func<#sort,openArray[T],proc(T,T)>`_ + ## * `sorted proc<#sorted,openArray[T],proc(T,T)>`_ sorted by `cmp` in the specified order + ## * `sorted proc<#sorted,openArray[T]>`_ + ## * `sortedByIt template<#sortedByIt.t,untyped,untyped>`_ + 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`. + order = SortOrder.Ascending): seq[T] {.effectsOf: cmp.} = + ## Returns `a` sorted by `cmp` in the specified `order`. + ## + ## **See also:** + ## * `sort func<#sort,openArray[T],proc(T,T)>`_ + ## * `sort proc<#sort,openArray[T]>`_ + ## * `sortedByIt template<#sortedByIt.t,untyped,untyped>`_ + runnableExamples: + 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"] result = newSeq[T](a.len) for i in 0 .. a.high: result[i] = a[i] sort(result, cmp, order) -template sortedByIt*(seq1, op: expr): expr = - ## Convenience template around the ``sorted`` proc to reduce typing. - ## - ## The template injects the ``it`` variable which you can use directly in an - ## expression. Example: - ## - ## .. code-block:: nim - ## - ## 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) +proc sorted*[T](a: openArray[T], order = SortOrder.Ascending): seq[T] = + ## Shortcut version of `sorted` that uses `system.cmp[T]` as the comparison function. ## - ## Because the underlying ``cmp()`` is defined for tuples you can do - ## a nested sort like in the following example: + ## **See also:** + ## * `sort func<#sort,openArray[T],proc(T,T)>`_ + ## * `sort proc<#sort,openArray[T]>`_ + ## * `sortedByIt template<#sortedByIt.t,untyped,untyped>`_ + runnableExamples: + 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"] + sorted[T](a, system.cmp[T], order) + +template sortedByIt*(seq1, op: untyped): untyped = + ## Convenience template around the `sorted` proc to reduce typing. ## - ## .. code-block:: nim + ## The template injects the `it` variable which you can use directly in an + ## expression. ## - ## echo people.sortedByIt((it.age, it.name)) + ## Because the underlying `cmp()` is defined for tuples you can also do + ## a nested sort. ## - var result {.gensym.} = sorted(seq1, proc(x, y: type(seq1[0])): int = + ## **See also:** + ## * `sort func<#sort,openArray[T],proc(T,T)>`_ + ## * `sort proc<#sort,openArray[T]>`_ + ## * `sorted proc<#sorted,openArray[T],proc(T,T)>`_ sorted by `cmp` in the specified order + ## * `sorted proc<#sorted,openArray[T]>`_ + runnableExamples: + 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)] + # Nested sort + assert people.sortedByIt((it.age, it.name)) == @[(name: "p2", age: 20), + (name: "p3", age: 30), (name: "p4", age: 30), (name: "p1", age: 60)] + var result = sorted(seq1, proc(x, y: typeof(items(seq1), typeOfIter)): int = var it {.inject.} = x let a = op it = y @@ -230,50 +504,203 @@ template sortedByIt*(seq1, op: expr): expr = result = cmp(a, b)) result +func isSorted*[T](a: openArray[T], + cmp: proc(x, y: T): int {.closure.}, + 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:** + ## * `isSorted proc<#isSorted,openArray[T]>`_ + runnableExamples: + 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 + result = true + for i in 0..<len(a)-1: + if cmp(a[i], a[i+1]) * order > 0: + return false + +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:** + ## * `isSorted func<#isSorted,openArray[T],proc(T,T)>`_ + runnableExamples: + 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 + isSorted(a, system.cmp[T], order) + +proc merge*[T]( + result: var seq[T], + x, y: openArray[T], cmp: proc(x, y: T): int {.closure.} +) {.since: (1, 5, 1), 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:** + ## * `merge proc<#merge,seq[T],openArray[T],openArray[T]>`_ + runnableExamples: + let x = @[1, 3, 6] + let y = @[2, 3, 4] + + block: + var merged = @[7] # new data is appended to merged sequence + merged.merge(x, y, system.cmp[int]) + assert merged == @[7, 1, 2, 3, 3, 4, 6] + + block: + var merged = @[7] # if you only want new data, clear merged sequence first + merged.setLen(0) + merged.merge(x, y, system.cmp[int]) + assert merged.isSorted + assert merged == @[1, 2, 3, 3, 4, 6] + + import std/sugar + + var res: seq[(int, int)] + res.merge([(1, 1)], [(1, 2)], (a, b) => a[0] - b[0]) + assert res == @[(1, 1), (1, 2)] + + assert seq[int].default.dup(merge([1, 3], [2, 4])) == @[1, 2, 3, 4] + + let + sizeX = x.len + sizeY = y.len + oldLen = result.len + + result.setLen(oldLen + sizeX + sizeY) + + var + ix = 0 + iy = 0 + i = oldLen + + while true: + if ix == sizeX: + while iy < sizeY: + result[i] = y[iy] + inc i + inc iy + return + + if iy == sizeY: + while ix < sizeX: + result[i] = x[ix] + inc i + inc ix + return + + let itemX = x[ix] + let itemY = y[iy] + + if cmp(itemX, itemY) > 0: # to have a stable sort + result[i] = itemY + inc iy + else: + result[i] = itemX + inc ix + + inc i + +proc merge*[T](result: var seq[T], x, y: openArray[T]) {.inline, since: (1, 5, 1).} = + ## Shortcut version of `merge` that uses `system.cmp[T]` as the comparison function. + ## + ## **See also:** + ## * `merge proc<#merge,seq[T],openArray[T],openArray[T],proc(T,T)>`_ + runnableExamples: + let x = [5, 10, 15, 20, 25] + let y = [50, 40, 30, 20, 10].sorted + + var merged: seq[int] + merged.merge(x, y) + assert merged.isSorted + assert merged == @[5, 10, 10, 15, 20, 20, 25, 30, 40, 50] + merge(result, x, y, system.cmp) + proc product*[T](x: openArray[seq[T]]): seq[seq[T]] = - ## produces the Cartesian product of the array. Warning: complexity - ## may explode. - result = @[] - if x.len == 0: + ## 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. + runnableExamples: + assert product(@[@[1], @[2]]) == @[@[1, 2]] + assert product(@[@["A", "K"], @["Q"]]) == @[@["K", "Q"], @["A", "Q"]] + let xLen = x.len + result = newSeq[seq[T]]() + if xLen == 0: return - if x.len == 1: + if xLen == 1: result = @x return var - indexes = newSeq[int](x.len) - initial = newSeq[int](x.len) + indices = newSeq[int](xLen) + initial = newSeq[int](xLen) index = 0 - # replace with newSeq as soon as #853 is fixed - var next: seq[T] = @[] - next.setLen(x.len) - for i in 0..(x.len-1): + var next = newSeq[T](xLen) + for i in 0 ..< xLen: if len(x[i]) == 0: return - initial[i] = len(x[i])-1 - indexes = initial + initial[i] = len(x[i]) - 1 + indices = initial while true: - while indexes[index] == -1: - indexes[index] = initial[index] + while indices[index] == -1: + indices[index] = initial[index] index += 1 - if index == x.len: return - indexes[index] -= 1 - for ni, i in indexes: + if index == xLen: return + indices[index] -= 1 + for ni, i in indices: next[ni] = x[ni][i] - var res: seq[T] - shallowCopy(res, next) - result.add(res) + result.add(next) index = 0 - indexes[index] -= 1 + indices[index] -= 1 -proc nextPermutation*[T](x: var openarray[T]): bool {.discardable.} = - ## Calculates the next lexicographic permutation, directly modifying ``x``. +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. ## - ## .. code-block:: nim + ## If you start with an unsorted array/seq, the repeated permutations + ## will **not** give you all permutations but stop with the last. ## - ## var v = @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] - ## v.nextPermutation() - ## echo v + ## **See also:** + ## * `prevPermutation proc<#prevPermutation,openArray[T]>`_ + runnableExamples: + 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] if x.len < 2: return false @@ -293,16 +720,21 @@ proc nextPermutation*[T](x: var openarray[T]): bool {.discardable.} = result = true -proc prevPermutation*[T](x: var openarray[T]): bool {.discardable.} = +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 + ## `x`. The result is whether a permutation happened, otherwise we have ## reached the first-ordered permutation. ## - ## .. code-block:: nim - ## - ## var v = @[0, 1, 2, 3, 4, 5, 6, 7, 9, 8] - ## v.prevPermutation() - ## echo v + ## **See also:** + ## * `nextPermutation proc<#nextPermutation,openArray[T]>`_ + runnableExamples: + 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] if x.len < 2: return false @@ -322,3 +754,164 @@ proc prevPermutation*[T](x: var openarray[T]): bool {.discardable.} = swap x[i-1], x[j] result = true + +proc rotateInternal[T](arg: var openArray[T]; first, middle, last: int): int = + ## A port of std::rotate from C++. + ## Ported from [this reference](http://www.cplusplus.com/reference/algorithm/rotate/). + result = first + last - middle + + if first == middle or middle == last: + return + + assert first < middle + assert middle < last + + # m prefix for mutable + var + mFirst = first + mMiddle = middle + next = middle + + swap(arg[mFirst], arg[next]) + mFirst += 1 + next += 1 + if mFirst == mMiddle: + mMiddle = next + + while next != last: + swap(arg[mFirst], arg[next]) + mFirst += 1 + next += 1 + if mFirst == mMiddle: + mMiddle = next + + next = mMiddle + while next != last: + swap(arg[mFirst], arg[next]) + mFirst += 1 + next += 1 + if mFirst == mMiddle: + mMiddle = next + elif next == last: + next = mMiddle + +proc rotatedInternal[T](arg: openArray[T]; first, middle, last: int): seq[T] = + let argLen = arg.len + result = newSeq[T](argLen) + for i in 0 ..< first: + result[i] = arg[i] + let n = last - middle + let m = middle - first + for i in 0 ..< n: + result[first+i] = arg[middle+i] + for i in 0 ..< m: + result[first+n+i] = arg[first+i] + for i in last ..< argLen: + result[i] = arg[i] + +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 `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:** + ## * `rotateLeft proc<#rotateLeft,openArray[T],int>`_ for a version which rotates the whole container + ## * `rotatedLeft proc<#rotatedLeft,openArray[T],HSlice[int,int],int>`_ for a version which returns a `seq[T]` + runnableExamples: + 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(IndexDefect, a.rotateLeft(1 .. 7, 2)) + 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 {.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:** + ## * `rotateLeft proc<#rotateLeft,openArray[T],HSlice[int,int],int>`_ for a version which rotates a range + ## * `rotatedLeft proc<#rotatedLeft,openArray[T],int>`_ for a version which returns a `seq[T]` + runnableExamples: + 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] + 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. + ## + ## 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:** + ## * `rotateLeft proc<#rotateLeft,openArray[T],HSlice[int,int],int>`_ for the in-place version of this proc + ## * `rotatedLeft proc<#rotatedLeft,openArray[T],int>`_ for a version which rotates the whole container + runnableExamples: + 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] + 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. + ## + ## **See also:** + ## * `rotateLeft proc<#rotateLeft,openArray[T],int>`_ for the in-place version of this proc + ## * `rotatedLeft proc<#rotatedLeft,openArray[T],HSlice[int,int],int>`_ for a version which rotates a range + runnableExamples: + 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] + let argLen = arg.len + let distLeft = ((dist mod argLen) + argLen) mod argLen + arg.rotatedInternal(0, distLeft, argLen) |