From c6c3ea599013d178f2df707f0b1fb833ff20b232 Mon Sep 17 00:00:00 2001 From: Arne Döring Date: Tue, 14 Feb 2017 01:01:36 +0100 Subject: added rotate in algorithm --- lib/pure/algorithm.nim | 112 ++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 111 insertions(+), 1 deletion(-) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 9eee04404..189e96593 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -343,7 +343,7 @@ proc prevPermutation*[T](x: var openarray[T]): bool {.discardable.} = swap x[i-1], x[j] result = true - + when isMainModule: # Tests for lowerBound var arr = @[1,2,3,5,6,7,8,9] @@ -371,3 +371,113 @@ when isMainModule: for i in 0 .. high(arr1): assert arr1.reversed(0, i) == arr1.reversed()[high(arr1) - i .. high(arr1)] assert arr1.reversed(i, high(arr1)) == arr1.reversed()[0 .. high(arr1) - i] + + +proc rotate*[T](arg: var openarray[T]; first, middle, last: int): int {.discardable.} = + ## Performs a left rotation on a range of elements. + ## Specifically, ``rotate`` swaps the elements in the range [first, last) in such a way + ## that the element at index ``middle`` becomes the first element of the sub range and + ## ``middle - 1`` becomes the last element of the sub range. The time complexity is + ## linear to ``last - first``. returns ``first + (last - middle)``. ``T`` must support swap operation + ## + ## ``first`` + ## the index of the first element that should be rotated. + ## + ## ``middle`` + ## the index of the element that should appear at the beginning of the rotated range. + ## + ## ``last`` + ## the index of the first element that should not be rotated anymore (exclusive upper bound). + ## + ## .. code-block:: nim + ## var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] + ## list.rotate(1,4,9) + ## echo @list # @[0, 4, 5, 6, 7, 8, 1, 2, 3, 9, 10] + + 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 rotate[T](arg: var openarray[T]; middle: int): int {.discardable.} = + ## default arguments for first and last, so that this procedure operates on the entire + ## argument, and not just on a portion of it. + arg.rotate(0, middle, arg.len) + +proc rotated*[T](arg: openarray[T]; first, middle, last: int): seq[T] = + ## same as ``rotate``, just with the difference that it does + ## not modify the argument, but writes into a new ``seq`` instead + + result = newSeq[T](arg.len) + + 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 ..< arg.len: + result[i] = arg[i] + +proc rotated*[T](arg: openarray[T]; middle: int): seq[T] = + ## same as ``rotate``, just with the difference that it does + ## not modify the argument, but writes into a new ``seq`` instead + arg.rotated(0, middle, arg.len) + +when isMainModule: + var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] + let list2 = list.rotated(1,4,9) + let expected = [0, 4, 5, 6, 7, 8, 1, 2, 3, 9, 10] + + doAssert list.rotate(1,4,9) == 6 + doAssert list == expected + doAssert list2 == @expected + + var s0,s1,s2 = "xxxabcdefgxxx" + + doAssert s0.rotate(3, 6, 10) == 7 + doAssert s0 == "xxxdefgabcxxx" + doAssert s1.rotate(3, 5, 10) == 8 + doAssert s1 == "xxxcdefgabxxx" + doAssert s2.rotate(3, 7, 10) == 6 + doassert s2 == "xxxefgabcdxxx" + + -- cgit 1.4.1-2-gfad0 From c6417515232b496952e12948cbb787d93084d3eb Mon Sep 17 00:00:00 2001 From: Arne Döring Date: Tue, 21 Mar 2017 12:03:41 +0100 Subject: fixes for feedback --- lib/pure/algorithm.nim | 27 ++++++++++++++------------- 1 file changed, 14 insertions(+), 13 deletions(-) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 189e96593..25d03a356 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -343,7 +343,7 @@ proc prevPermutation*[T](x: var openarray[T]): bool {.discardable.} = swap x[i-1], x[j] result = true - + when isMainModule: # Tests for lowerBound var arr = @[1,2,3,5,6,7,8,9] @@ -373,12 +373,14 @@ when isMainModule: assert arr1.reversed(i, high(arr1)) == arr1.reversed()[0 .. high(arr1) - i] -proc rotate*[T](arg: var openarray[T]; first, middle, last: int): int {.discardable.} = +proc rotate*[T](arg: var openarray[T]; first, middle, last: int): int = ## Performs a left rotation on a range of elements. ## Specifically, ``rotate`` swaps the elements in the range [first, last) in such a way ## that the element at index ``middle`` becomes the first element of the sub range and ## ``middle - 1`` becomes the last element of the sub range. The time complexity is ## linear to ``last - first``. returns ``first + (last - middle)``. ``T`` must support swap operation + ## returs ``first + last - middle``, the new index, where the element this was at index ``last`` will + ## be ater the rotation. ## ## ``first`` ## the index of the first element that should be rotated. @@ -388,7 +390,7 @@ proc rotate*[T](arg: var openarray[T]; first, middle, last: int): int {.discarda ## ## ``last`` ## the index of the first element that should not be rotated anymore (exclusive upper bound). - ## + ## ## .. code-block:: nim ## var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ## list.rotate(1,4,9) @@ -431,15 +433,15 @@ proc rotate*[T](arg: var openarray[T]; first, middle, last: int): int {.discarda elif next == last: next = mMiddle -proc rotate[T](arg: var openarray[T]; middle: int): int {.discardable.} = - ## default arguments for first and last, so that this procedure operates on the entire - ## argument, and not just on a portion of it. +proc rotate*[T](arg: var openarray[T]; middle: int): int = + ## default arguments for first and last, so that this procedure operates on entire + ## ``arg``, and not just on a part of it. arg.rotate(0, middle, arg.len) proc rotated*[T](arg: openarray[T]; first, middle, last: int): seq[T] = ## same as ``rotate``, just with the difference that it does - ## not modify the argument, but writes into a new ``seq`` instead - + ## not modify the argument. It creates a new ``seq`` instead + result = newSeq[T](arg.len) for i in 0 ..< first: @@ -459,14 +461,15 @@ proc rotated*[T](arg: openarray[T]; first, middle, last: int): seq[T] = proc rotated*[T](arg: openarray[T]; middle: int): seq[T] = ## same as ``rotate``, just with the difference that it does - ## not modify the argument, but writes into a new ``seq`` instead + ## not modify the argument. It creates a new ``seq`` instead + arg.rotated(0, middle, arg.len) - + when isMainModule: var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] let list2 = list.rotated(1,4,9) let expected = [0, 4, 5, 6, 7, 8, 1, 2, 3, 9, 10] - + doAssert list.rotate(1,4,9) == 6 doAssert list == expected doAssert list2 == @expected @@ -479,5 +482,3 @@ when isMainModule: doAssert s1 == "xxxcdefgabxxx" doAssert s2.rotate(3, 7, 10) == 6 doassert s2 == "xxxefgabcdxxx" - - -- cgit 1.4.1-2-gfad0 From 409854c91379610853103cabc3ec29c04fbd13e0 Mon Sep 17 00:00:00 2001 From: Arne Döring Date: Thu, 27 Jul 2017 17:39:34 +0200 Subject: changed rotate to rotateLeft with slice api --- lib/pure/algorithm.nim | 86 ++++++++++++++++++++++++-------------------------- 1 file changed, 41 insertions(+), 45 deletions(-) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 25d03a356..ea7752b18 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -373,29 +373,7 @@ when isMainModule: assert arr1.reversed(i, high(arr1)) == arr1.reversed()[0 .. high(arr1) - i] -proc rotate*[T](arg: var openarray[T]; first, middle, last: int): int = - ## Performs a left rotation on a range of elements. - ## Specifically, ``rotate`` swaps the elements in the range [first, last) in such a way - ## that the element at index ``middle`` becomes the first element of the sub range and - ## ``middle - 1`` becomes the last element of the sub range. The time complexity is - ## linear to ``last - first``. returns ``first + (last - middle)``. ``T`` must support swap operation - ## returs ``first + last - middle``, the new index, where the element this was at index ``last`` will - ## be ater the rotation. - ## - ## ``first`` - ## the index of the first element that should be rotated. - ## - ## ``middle`` - ## the index of the element that should appear at the beginning of the rotated range. - ## - ## ``last`` - ## the index of the first element that should not be rotated anymore (exclusive upper bound). - ## - ## .. code-block:: nim - ## var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] - ## list.rotate(1,4,9) - ## echo @list # @[0, 4, 5, 6, 7, 8, 1, 2, 3, 9, 10] - +proc rotate_internal[T](arg: var openarray[T]; first, middle, last: int): int = result = first + last - middle if first == middle or middle == last: @@ -433,52 +411,70 @@ proc rotate*[T](arg: var openarray[T]; first, middle, last: int): int = elif next == last: next = mMiddle -proc rotate*[T](arg: var openarray[T]; middle: int): int = - ## default arguments for first and last, so that this procedure operates on entire - ## ``arg``, and not just on a part of it. - arg.rotate(0, middle, arg.len) - -proc rotated*[T](arg: openarray[T]; first, middle, last: int): seq[T] = - ## same as ``rotate``, just with the difference that it does - ## not modify the argument. It creates a new ``seq`` instead - +proc rotated_internal[T](arg: openarray[T]; first, middle, last: int): seq[T] = result = newSeq[T](arg.len) - 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 ..< arg.len: result[i] = arg[i] -proc rotated*[T](arg: openarray[T]; middle: int): seq[T] = - ## same as ``rotate``, just with the difference that it does +proc rotateLeft*[T](arg: var openarray[T]; slice: Slice[int]; dist: int): int = + ## Performs a left rotation on a range of elements. + ## Specifically, ``rotate`` 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`` well 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. + ## + ## ``dist`` + ## the distance in amount of elements that the data should be rotated. + ## + ## .. code-block:: nim + ## var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] + ## list.rotateLeft(1 .. 8, 3) + ## echo @list # @[0, 4, 5, 6, 7, 8, 1, 2, 3, 9, 10] + arg.rotate_internal(slice.a, slice.a+dist, 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 + ## ``arg``, and not just on a part of it. + arg.rotate_internal(0, dist, arg.len) + +proc rotatedLeft*[T](arg: openarray[T]; slice: Slice[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 + arg.rotated_internal(slice.a, slice.a+dist, slice.b+1) - arg.rotated(0, middle, arg.len) +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 + arg.rotated_internal(0, dist, arg.len) when isMainModule: var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] - let list2 = list.rotated(1,4,9) + let list2 = list.rotatedLeft(1 ..< 9, 3) let expected = [0, 4, 5, 6, 7, 8, 1, 2, 3, 9, 10] - doAssert list.rotate(1,4,9) == 6 + doAssert list.rotateLeft(1 ..< 9, 3) == 6 doAssert list == expected doAssert list2 == @expected var s0,s1,s2 = "xxxabcdefgxxx" - doAssert s0.rotate(3, 6, 10) == 7 + doAssert s0.rotateLeft(3 ..< 10, 3) == 7 doAssert s0 == "xxxdefgabcxxx" - doAssert s1.rotate(3, 5, 10) == 8 + doAssert s1.rotateLeft(3 ..< 10, 2) == 8 doAssert s1 == "xxxcdefgabxxx" - doAssert s2.rotate(3, 7, 10) == 6 + doAssert s2.rotateLeft(3 ..< 10, 4) == 6 doassert s2 == "xxxefgabcdxxx" -- cgit 1.4.1-2-gfad0 From 316886542b0a7b9143e0ba96ef93b93a9caadbe6 Mon Sep 17 00:00:00 2001 From: Arne Döring Date: Thu, 27 Jul 2017 18:22:59 +0200 Subject: allow a negative distance argument. Improved documentation. --- lib/pure/algorithm.nim | 30 ++++++++++++++++++++++-------- 1 file changed, 22 insertions(+), 8 deletions(-) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index ea7752b18..a808b6703 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -425,7 +425,7 @@ proc rotated_internal[T](arg: openarray[T]; first, middle, last: int): seq[T] = result[i] = arg[i] proc rotateLeft*[T](arg: var openarray[T]; slice: Slice[int]; dist: int): int = - ## Performs a left rotation on a range of elements. + ## Performs a left rotation on a range of elements. If you want to rotate right, use a negative ``dist``. ## Specifically, ``rotate`` 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``. @@ -438,28 +438,36 @@ proc rotateLeft*[T](arg: var openarray[T]; slice: Slice[int]; dist: int): int = ## the indices of the element range that should be rotated. ## ## ``dist`` - ## the distance in amount of elements that the data should be rotated. + ## 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) ## echo @list # @[0, 4, 5, 6, 7, 8, 1, 2, 3, 9, 10] - arg.rotate_internal(slice.a, slice.a+dist, slice.b + 1) + let sliceLen = slice.b + 1 - slice.a + let distLeft = ((dist mod sliceLen) + sliceLen) mod sliceLen + arg.rotate_internal(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 ## ``arg``, and not just on a part of it. - arg.rotate_internal(0, dist, arg.len) + let arglen = arg.len + let distLeft = ((dist mod arglen) + arglen) mod arglen + arg.rotate_internal(0, distLeft, arglen) proc rotatedLeft*[T](arg: openarray[T]; slice: Slice[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 - arg.rotated_internal(slice.a, slice.a+dist, slice.b+1) + let sliceLen = slice.b + 1 - slice.a + let distLeft = ((dist mod sliceLen) + sliceLen) mod sliceLen + arg.rotated_internal(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 - arg.rotated_internal(0, dist, arg.len) + let arglen = arg.len + let distLeft = ((dist mod arglen) + arglen) mod arglen + arg.rotated_internal(0, distLeft, arg.len) when isMainModule: var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] @@ -470,11 +478,17 @@ when isMainModule: doAssert list == expected doAssert list2 == @expected - var s0,s1,s2 = "xxxabcdefgxxx" + var s0,s1,s2,s3,s4,s5 = "xxxabcdefgxxx" doAssert s0.rotateLeft(3 ..< 10, 3) == 7 doAssert s0 == "xxxdefgabcxxx" doAssert s1.rotateLeft(3 ..< 10, 2) == 8 doAssert s1 == "xxxcdefgabxxx" doAssert s2.rotateLeft(3 ..< 10, 4) == 6 - doassert s2 == "xxxefgabcdxxx" + doAssert s2 == "xxxefgabcdxxx" + doAssert s3.rotateLeft(3 ..< 10, -3) == 6 + doAssert s3 == "xxxefgabcdxxx" + doAssert s4.rotateLeft(3 ..< 10, -10) == 6 + doAssert s4 == "xxxefgabcdxxx" + doAssert s5.rotateLeft(3 ..< 10, 11) == 6 + doAssert s5 == "xxxefgabcdxxx" -- cgit 1.4.1-2-gfad0 From efe606ef81849984ec4de2e18be72ceff933d743 Mon Sep 17 00:00:00 2001 From: Arne Döring Date: Mon, 14 Aug 2017 13:55:38 +0200 Subject: fix for feedback on PR --- lib/pure/algorithm.nim | 20 +++++++++++--------- 1 file changed, 11 insertions(+), 9 deletions(-) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index a808b6703..2fac537e3 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -373,11 +373,12 @@ when isMainModule: assert arr1.reversed(i, high(arr1)) == arr1.reversed()[0 .. high(arr1) - i] -proc rotate_internal[T](arg: var openarray[T]; first, middle, last: int): int = +proc rotateInternal[T](arg: var openarray[T]; first, middle, last: int): int = + ## A port of std::rotate from c++. Ported from `this reference `_. result = first + last - middle if first == middle or middle == last: - return + return assert first < middle assert middle < last @@ -411,7 +412,7 @@ proc rotate_internal[T](arg: var openarray[T]; first, middle, last: int): int = elif next == last: next = mMiddle -proc rotated_internal[T](arg: openarray[T]; first, middle, last: int): seq[T] = +proc rotatedInternal[T](arg: openarray[T]; first, middle, last: int): seq[T] = result = newSeq[T](arg.len) for i in 0 ..< first: result[i] = arg[i] @@ -426,12 +427,13 @@ proc rotated_internal[T](arg: openarray[T]; first, middle, last: int): seq[T] = proc rotateLeft*[T](arg: var openarray[T]; slice: Slice[int]; dist: int): int = ## Performs a left rotation on a range of elements. If you want to rotate right, use a negative ``dist``. - ## Specifically, ``rotate`` rotates the elements at ``slice`` by ``dist`` positions.. + ## 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`` well be left unchanged. + # + ## Elements outsize of ``slice`` will be left unchanged. ## The time complexity is linear to ``slice.b - slice.a + 1``. ## ## ``slice`` @@ -446,28 +448,28 @@ proc rotateLeft*[T](arg: var openarray[T]; slice: Slice[int]; dist: int): int = ## echo @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.rotate_internal(slice.a, slice.a+distLeft, slice.b + 1) + 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 ## ``arg``, and not just on a part of it. let arglen = arg.len let distLeft = ((dist mod arglen) + arglen) mod arglen - arg.rotate_internal(0, distLeft, arglen) + arg.rotateInternal(0, distLeft, arglen) proc rotatedLeft*[T](arg: openarray[T]; slice: Slice[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 let sliceLen = slice.b + 1 - slice.a let distLeft = ((dist mod sliceLen) + sliceLen) mod sliceLen - arg.rotated_internal(slice.a, slice.a+distLeft, slice.b+1) + 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 let arglen = arg.len let distLeft = ((dist mod arglen) + arglen) mod arglen - arg.rotated_internal(0, distLeft, arg.len) + arg.rotatedInternal(0, distLeft, arg.len) when isMainModule: var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] -- cgit 1.4.1-2-gfad0 From 484f729e27f5d6f51120a207120627166bf4d240 Mon Sep 17 00:00:00 2001 From: Arne Döring Date: Thu, 17 Aug 2017 13:34:03 +0200 Subject: use doAssert in rotateLeft example --- lib/pure/algorithm.nim | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 2fac537e3..1b0790706 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -445,7 +445,7 @@ proc rotateLeft*[T](arg: var openarray[T]; slice: Slice[int]; dist: int): int = ## .. code-block:: nim ## var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ## list.rotateLeft(1 .. 8, 3) - ## echo @list # @[0, 4, 5, 6, 7, 8, 1, 2, 3, 9, 10] + ## 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) -- cgit 1.4.1-2-gfad0 From a62051e304a0ca5dd2d1923cb290a1f788bad453 Mon Sep 17 00:00:00 2001 From: Andreas Rumpf Date: Mon, 30 Oct 2017 08:42:44 +0100 Subject: updated algorithm.rotateLeft implementation --- lib/pure/algorithm.nim | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 1b0790706..02b381ad6 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -425,7 +425,7 @@ 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: Slice[int]; dist: int): int = +proc rotateLeft*[T](arg: var openarray[T]; slice: Slice[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``. @@ -457,7 +457,7 @@ proc rotateLeft*[T](arg: var openarray[T]; dist: int): int = let distLeft = ((dist mod arglen) + arglen) mod arglen arg.rotateInternal(0, distLeft, arglen) -proc rotatedLeft*[T](arg: openarray[T]; slice: Slice[int], dist: int): seq[T] = +proc rotatedLeft*[T](arg: openarray[T]; slice: Slice[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 let sliceLen = slice.b + 1 - slice.a -- cgit 1.4.1-2-gfad0 From b14cc1e3b2d8462018e1d2a8e92dfcb42398713e Mon Sep 17 00:00:00 2001 From: Andreas Rumpf Date: Mon, 30 Oct 2017 14:45:57 +0100 Subject: fixes #6631 --- changelog.md | 5 +++-- lib/impure/nre.nim | 26 ++++++++++++------------ lib/pure/algorithm.nim | 4 ++-- lib/pure/collections/sharedstrings.nim | 2 +- lib/pure/matchers.nim | 2 +- lib/pure/random.nim | 2 +- lib/system.nim | 36 ++++++++++++++++++---------------- tests/array/troof1.nim | 26 +++++++++++++++++++++++- 8 files changed, 65 insertions(+), 38 deletions(-) (limited to 'lib/pure/algorithm.nim') diff --git a/changelog.md b/changelog.md index c113505cd..f8ad88842 100644 --- a/changelog.md +++ b/changelog.md @@ -24,8 +24,9 @@ use the ``pred`` proc. - We changed how array accesses "from backwards" like ``a[^1]`` or ``a[0..^1]`` are implemented. These are now implemented purely in ``system.nim`` without compiler - support. ``system.Slice`` now takes 2 generic parameters so that it can - take ``BackwardsIndex`` indices. ``BackwardsIndex`` is produced by ``system.^``. + support. There is a new "heterogenous" slice type ``system.HSlice`` that takes 2 + generic parameters which can be ``BackwardsIndex`` indices. ``BackwardsIndex`` is + produced by ``system.^``. This means if you overload ``[]`` or ``[]=`` you need to ensure they also work with ``system.BackwardsIndex`` (if applicable for the accessors). - ``mod`` and bitwise ``and`` do not produce ``range`` subtypes anymore. This diff --git a/lib/impure/nre.nim b/lib/impure/nre.nim index 7df62f3b3..3d4afc0ae 100644 --- a/lib/impure/nre.nim +++ b/lib/impure/nre.nim @@ -155,7 +155,7 @@ type ## - ``"abc".match(re"(?\w)").captures["letter"] == "a"`` ## - ``"abc".match(re"(\w)\w").captures[-1] == "ab"`` ## - ## ``captureBounds[]: Option[Slice[int, int]]`` + ## ``captureBounds[]: Option[HSlice[int, int]]`` ## gets the bounds of the given capture according to the same rules as ## the above. If the capture is not filled, then ``None`` is returned. ## The bounds are both inclusive. @@ -167,7 +167,7 @@ type ## ``match: string`` ## the full text of the match. ## - ## ``matchBounds: Slice[int, int]`` + ## ``matchBounds: HSlice[int, int]`` ## the bounds of the match, as in ``captureBounds[]`` ## ## ``(captureBounds|captures).toTable`` @@ -182,7 +182,7 @@ type ## Not nil. str*: string ## The string that was matched against. ## Not nil. - pcreMatchBounds: seq[Slice[cint, cint]] ## First item is the bounds of the match + pcreMatchBounds: seq[HSlice[cint, cint]] ## First item is the bounds of the match ## Other items are the captures ## `a` is inclusive start, `b` is exclusive end @@ -251,13 +251,13 @@ proc captureBounds*(pattern: RegexMatch): CaptureBounds = return CaptureBounds(p proc captures*(pattern: RegexMatch): Captures = return Captures(pattern) -proc `[]`*(pattern: CaptureBounds, i: int): Option[Slice[int, int]] = +proc `[]`*(pattern: CaptureBounds, i: int): Option[HSlice[int, int]] = let pattern = RegexMatch(pattern) if pattern.pcreMatchBounds[i + 1].a != -1: let bounds = pattern.pcreMatchBounds[i + 1] return some(int(bounds.a) .. int(bounds.b-1)) else: - return none(Slice[int, int]) + return none(HSlice[int, int]) proc `[]`*(pattern: Captures, i: int): string = let pattern = RegexMatch(pattern) @@ -272,10 +272,10 @@ proc `[]`*(pattern: Captures, i: int): string = proc match*(pattern: RegexMatch): string = return pattern.captures[-1] -proc matchBounds*(pattern: RegexMatch): Slice[int, int] = +proc matchBounds*(pattern: RegexMatch): HSlice[int, int] = return pattern.captureBounds[-1].get -proc `[]`*(pattern: CaptureBounds, name: string): Option[Slice[int, int]] = +proc `[]`*(pattern: CaptureBounds, name: string): Option[HSlice[int, int]] = let pattern = RegexMatch(pattern) return pattern.captureBounds[pattern.pattern.captureNameToId.fget(name)] @@ -295,9 +295,9 @@ proc toTable*(pattern: Captures, default: string = nil): Table[string, string] = result = initTable[string, string]() toTableImpl(nextVal == nil) -proc toTable*(pattern: CaptureBounds, default = none(Slice[int, int])): - Table[string, Option[Slice[int, int]]] = - result = initTable[string, Option[Slice[int, int]]]() +proc toTable*(pattern: CaptureBounds, default = none(HSlice[int, int])): + Table[string, Option[HSlice[int, int]]] = + result = initTable[string, Option[HSlice[int, int]]]() toTableImpl(nextVal.isNone) template itemsImpl(cond: untyped) {.dirty.} = @@ -309,13 +309,13 @@ template itemsImpl(cond: untyped) {.dirty.} = yield nextYieldVal -iterator items*(pattern: CaptureBounds, default = none(Slice[int, int])): Option[Slice[int, int]] = +iterator items*(pattern: CaptureBounds, default = none(HSlice[int, int])): Option[HSlice[int, int]] = itemsImpl(nextVal.isNone) iterator items*(pattern: Captures, default: string = nil): string = itemsImpl(nextVal == nil) -proc toSeq*(pattern: CaptureBounds, default = none(Slice[int, int])): seq[Option[Slice[int, int]]] = +proc toSeq*(pattern: CaptureBounds, default = none(HSlice[int, int])): seq[Option[HSlice[int, int]]] = accumulateResult(pattern.items(default)) proc toSeq*(pattern: Captures, default: string = nil): seq[string] = @@ -462,7 +462,7 @@ proc matchImpl(str: string, pattern: Regex, start, endpos: int, flags: int): Opt # 1x capture count as slack space for PCRE let vecsize = (pattern.captureCount() + 1) * 3 # div 2 because each element is 2 cints long - myResult.pcreMatchBounds = newSeq[Slice[cint, cint]](ceil(vecsize / 2).int) + myResult.pcreMatchBounds = newSeq[HSlice[cint, cint]](ceil(vecsize / 2).int) myResult.pcreMatchBounds.setLen(vecsize div 3) let strlen = if endpos == int.high: str.len else: endpos+1 diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 02b381ad6..fdf2d7cbb 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -425,7 +425,7 @@ 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: Slice[int, int]; dist: int): int = +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``. @@ -457,7 +457,7 @@ proc rotateLeft*[T](arg: var openarray[T]; dist: int): int = let distLeft = ((dist mod arglen) + arglen) mod arglen arg.rotateInternal(0, distLeft, arglen) -proc rotatedLeft*[T](arg: openarray[T]; slice: Slice[int, int], dist: int): seq[T] = +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 let sliceLen = slice.b + 1 - slice.a diff --git a/lib/pure/collections/sharedstrings.nim b/lib/pure/collections/sharedstrings.nim index a9e194fb4..83edf8d94 100644 --- a/lib/pure/collections/sharedstrings.nim +++ b/lib/pure/collections/sharedstrings.nim @@ -55,7 +55,7 @@ proc `[]=`*(s: var SharedString; i: Natural; value: char) = if i < s.len: s.buffer.data[i+s.first] = value else: raise newException(IndexError, "index out of bounds") -proc `[]`*(s: SharedString; ab: Slice[int]): SharedString = +proc `[]`*(s: SharedString; ab: HSlice[int, int]): SharedString = #incRef(src.buffer) if ab.a < s.len: result.buffer = s.buffer diff --git a/lib/pure/matchers.nim b/lib/pure/matchers.nim index 36daef8d1..6366fee1a 100644 --- a/lib/pure/matchers.nim +++ b/lib/pure/matchers.nim @@ -48,7 +48,7 @@ proc validEmailAddress*(s: string): bool {.noSideEffect, "aero", "jobs", "museum": return true else: return false -proc parseInt*(s: string, value: var int, validRange: Slice[int, int]) {. +proc parseInt*(s: string, value: var int, validRange: HSlice[int, int]) {. noSideEffect, rtl, extern: "nmatchParseInt".} = ## parses `s` into an integer in the range `validRange`. If successful, ## `value` is modified to contain the result. Otherwise no exception is diff --git a/lib/pure/random.nim b/lib/pure/random.nim index 2c406faa1..e6a9162c5 100644 --- a/lib/pure/random.nim +++ b/lib/pure/random.nim @@ -93,7 +93,7 @@ proc random*(max: float): float {.benign.} = let u = (0x3FFu64 shl 52u64) or (x shr 12u64) result = (cast[float](u) - 1.0) * max -proc random*[T](x: Slice[T, T]): T = +proc random*[T](x: HSlice[T, T]): T = ## For a slice `a .. b` returns a value in the range `a .. b-1`. result = T(random(x.b - x.a)) + x.a diff --git a/lib/system.nim b/lib/system.nim index 955159c2e..eefad5e9c 100644 --- a/lib/system.nim +++ b/lib/system.nim @@ -308,14 +308,12 @@ when defined(nimArrIdx): shallowCopy(x, y) type - Slice*[T, U] = object ## builtin slice type + HSlice*[T, U] = object ## "heterogenous" slice type a*: T ## the lower bound (inclusive) b*: U ## the upper bound (inclusive) + Slice*[T] = HSlice[T, T] ## an alias for ``HSlice[T, T]`` -when defined(nimalias): - {.deprecated: [TSlice: Slice].} - -proc `..`*[T, U](a: T, b: U): Slice[T, U] {.noSideEffect, inline, magic: "DotDot".} = +proc `..`*[T, U](a: T, b: U): HSlice[T, U] {.noSideEffect, inline, magic: "DotDot".} = ## `slice`:idx: operator that constructs an interval ``[a, b]``, both `a` ## and `b` are inclusive. Slices can also be used in the set constructor ## and in ordinal case statements, but then they are special-cased by the @@ -323,7 +321,7 @@ proc `..`*[T, U](a: T, b: U): Slice[T, U] {.noSideEffect, inline, magic: "DotDot result.a = a result.b = b -proc `..`*[T](b: T): Slice[int, T] {.noSideEffect, inline, magic: "DotDot".} = +proc `..`*[T](b: T): HSlice[int, T] {.noSideEffect, inline, magic: "DotDot".} = ## `slice`:idx: operator that constructs an interval ``[default(T), b]`` result.b = b @@ -1169,7 +1167,7 @@ proc contains*[T](x: set[T], y: T): bool {.magic: "InSet", noSideEffect.} ## is achieved by reversing the parameters for ``contains``; ``in`` then ## passes its arguments in reverse order. -proc contains*[T](s: Slice[T, T], value: T): bool {.noSideEffect, inline.} = +proc contains*[T](s: HSlice[T, T], value: T): bool {.noSideEffect, inline.} = ## Checks if `value` is within the range of `s`; returns true iff ## `value >= s.a and value <= s.b` ## @@ -2088,7 +2086,7 @@ proc clamp*[T](x, a, b: T): T = if x > b: return b return x -proc len*[T: Ordinal](x: Slice[T, T]): int {.noSideEffect, inline.} = +proc len*[T: Ordinal](x: HSlice[T, T]): int {.noSideEffect, inline.} = ## length of ordinal slice, when x.b < x.a returns zero length ## ## .. code-block:: Nim @@ -2156,7 +2154,7 @@ iterator items*(E: typedesc[enum]): E = for v in low(E)..high(E): yield v -iterator items*[T](s: Slice[T, T]): T = +iterator items*[T](s: HSlice[T, T]): T = ## iterates over the slice `s`, yielding each value between `s.a` and `s.b` ## (inclusively). for x in s.a..s.b: @@ -3457,7 +3455,7 @@ template `^^`(s, i: untyped): untyped = (when i is BackwardsIndex: s.len - int(i) else: int(i)) when hasAlloc or defined(nimscript): - proc `[]`*[T, U](s: string, x: Slice[T, U]): string {.inline.} = + proc `[]`*[T, U](s: string, x: HSlice[T, U]): string {.inline.} = ## slice operation for strings. ## returns the inclusive range [s[x.a], s[x.b]]: ## @@ -3466,7 +3464,7 @@ when hasAlloc or defined(nimscript): ## assert s[1..3] == "bcd" result = s.substr(s ^^ x.a, s ^^ x.b) - proc `[]=`*[T, U](s: var string, x: Slice[T, U], b: string) = + proc `[]=`*[T, U](s: var string, x: HSlice[T, U], b: string) = ## slice assignment for strings. If ## ``b.len`` is not exactly the number of elements that are referred to ## by `x`, a `splice`:idx: is performed: @@ -3482,7 +3480,7 @@ when hasAlloc or defined(nimscript): else: spliceImpl(s, a, L, b) -proc `[]`*[Idx, T, U, V](a: array[Idx, T], x: Slice[U, V]): seq[T] = +proc `[]`*[Idx, T, U, V](a: array[Idx, T], x: HSlice[U, V]): seq[T] = ## slice operation for arrays. ## returns the inclusive range [a[x.a], a[x.b]]: ## @@ -3494,7 +3492,7 @@ proc `[]`*[Idx, T, U, V](a: array[Idx, T], x: Slice[U, V]): seq[T] = result = newSeq[T](L) for i in 0..