diff options
| -rw-r--r-- | changelog.md | 3 | ||||
| -rw-r--r-- | lib/pure/algorithm.nim | 94 | ||||
| -rw-r--r-- | tests/stdlib/talgorithm.nim | 159 |
3 files changed, 255 insertions, 1 deletions
diff --git a/changelog.md b/changelog.md index 00fc970bf..78817cf85 100644 --- a/changelog.md +++ b/changelog.md @@ -212,6 +212,9 @@ - `std/options` changed `$some(3)` to `"some(3)"` instead of `"Some(3)"` and `$none(int)` to `"none(int)"` instead of `"None[int]"`. + +- Added `algorithm.merge`. + - Added `std/jsfetch` module [Fetch](https://developer.mozilla.org/docs/Web/API/Fetch_API) wrapper for JavaScript target. diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index a32df65bb..0410d65ee 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -42,6 +42,8 @@ runnableExamples: ## * `sequtils module<sequtils.html>`_ for working with the built-in seq type ## * `tables module<tables.html>`_ for sorting tables +import std/private/since + type SortOrder* = enum Descending, Ascending @@ -559,6 +561,98 @@ proc isSorted*[T](a: openArray[T], order = SortOrder.Ascending): bool = 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).} = + ## 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. ## Every element of the result is a combination of one element from each seq in `x`, diff --git a/tests/stdlib/talgorithm.nim b/tests/stdlib/talgorithm.nim index fecd85820..5bb5a6bdf 100644 --- a/tests/stdlib/talgorithm.nim +++ b/tests/stdlib/talgorithm.nim @@ -4,7 +4,8 @@ discard """ ''' """ #12928,10456 -import std/[sequtils, algorithm, json] + +import std/[sequtils, algorithm, json, sugar] proc test() = try: @@ -114,3 +115,159 @@ block: doAssert binarySearch(moreData, 6) == -1 doAssert binarySearch(moreData, 4711) == 4 doAssert binarySearch(moreData, 4712) == -1 + +# merge +proc main() = + block: + var x = @[1, 7, 8, 11, 21, 33, 45, 99] + var y = @[6, 7, 9, 12, 57, 66] + + var merged: seq[int] + merged.merge(x, y) + doAssert merged.isSorted + doAssert merged == sorted(x & y) + + block: + var x = @[111, 88, 76, 56, 45, 31, 22, 19, 11, 3] + var y = @[99, 85, 83, 82, 69, 64, 48, 42, 33, 31, 26, 13] + + var merged: seq[int] + merged.merge(x, y, (x, y) => -system.cmp(x, y)) + doAssert merged.isSorted((x, y) => -system.cmp(x, y)) + doAssert merged == sorted(x & y, SortOrder.Descending) + + block: + var x: seq[int] = @[] + var y = @[1] + + var merged: seq[int] + merged.merge(x, y) + doAssert merged.isSorted + doAssert merged.isSorted(SortOrder.Descending) + doAssert merged == @[1] + + block: + var x = [1, 3, 5, 5, 7] + var y: seq[int] = @[] + + var merged: seq[int] + merged.merge(x, y) + doAssert merged.isSorted + doAssert merged == @x + + block: + var x = [1, 3, 5, 5, 7] + var y: seq[int] = @[] + + var merged: seq[int] = @[1, 2, 3, 5, 6, 56, 99, 2, 34] + merged.merge(x, y) + doAssert merged == @[1, 2, 3, 5, 6, 56, 99, 2, 34, 1, 3, 5, 5, 7] + + + block: + var x: array[0, int] + var y = [1, 4, 6, 7, 9] + + var merged: seq[int] + merged.merge(x, y) + doAssert merged.isSorted + doAssert merged == @y + + block: + var x: array[0, int] + var y: array[0, int] + + var merged: seq[int] + merged.merge(x, y) + doAssert merged.isSorted + doAssert merged.len == 0 + + block: + var x: array[0, int] + var y: array[0, int] + + var merged: seq[int] = @[99, 99, 99] + merged.setLen(0) + merged.merge(x, y) + doAssert merged.isSorted + doAssert merged.len == 0 + + block: + var x: seq[int] + var y: seq[int] + + var merged: seq[int] + merged.merge(x, y) + doAssert merged.isSorted + doAssert merged.len == 0 + + block: + type + Record = object + id: int + + proc r(id: int): Record = + Record(id: id) + + proc cmp(x, y: Record): int = + if x.id == y.id: return 0 + if x.id < y.id: return -1 + result = 1 + + var x = @[r(-12), r(1), r(3), r(8), r(13), r(88)] + var y = @[r(4), r(7), r(12), r(13), r(77), r(99)] + + var merged: seq[Record] = @[] + merged.merge(x, y, cmp) + doAssert merged.isSorted(cmp) + doAssert merged.len == 12 + + block: + type + Record = object + id: int + + proc r(id: int): Record = + Record(id: id) + + proc ascendingCmp(x, y: Record): int = + if x.id == y.id: return 0 + if x.id < y.id: return -1 + result = 1 + + proc descendingCmp(x, y: Record): int = + if x.id == y.id: return 0 + if x.id < y.id: return 1 + result = -1 + + var x = @[r(-12), r(1), r(3), r(8), r(13), r(88)] + var y = @[r(4), r(7), r(12), r(13), r(77), r(99)] + + var merged: seq[Record] + merged.setLen(0) + merged.merge(x, y, ascendingCmp) + doAssert merged.isSorted(ascendingCmp) + doAssert merged == sorted(x & y, ascendingCmp) + + reverse(x) + reverse(y) + + merged.setLen(0) + merged.merge(x, y, descendingCmp) + doAssert merged.isSorted(descendingCmp) + doAssert merged == sorted(x & y, ascendingCmp, SortOrder.Descending) + + reverse(x) + reverse(y) + merged.setLen(0) + merged.merge(x, y, proc (x, y: Record): int = -descendingCmp(x, y)) + doAssert merged.isSorted(proc (x, y: Record): int = -descendingCmp(x, y)) + doAssert merged == sorted(x & y, ascendingCmp) + + + var x: seq[(int, int)] + x.merge([(1,1)], [(1,2)], (a,b) => a[0] - b[0]) + doAssert x == @[(1, 1), (1, 2)] + +static: main() +main() |