From 92b8fac94a7243cde785d985db3fd86b6025b079 Mon Sep 17 00:00:00 2001 From: Araq Date: Fri, 27 Dec 2013 23:10:36 +0100 Subject: case consistency part 4 --- 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 8b44e69d9..df7ae6d17 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -34,7 +34,7 @@ proc reverse*[T](a: var openArray[T]) = ## reverses the array `a`. reverse(a, 0, a.high) -proc binarySearch*[T](a: openarray[T], key: T): int = +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: @@ -79,7 +79,7 @@ proc merge[T](a, b: var openArray[T], lo, m, hi: int, inc(bb) inc(j) else: - CopyMem(addr(b[0]), addr(a[j]), sizeof(T)*(m-j+1)) + copyMem(addr(b[0]), addr(a[j]), sizeof(T)*(m-j+1)) j = m+1 var i = 0 var k = lo -- cgit 1.4.1-2-gfad0 From ac0f15379cb0409e47512bcd40af28d1e7816337 Mon Sep 17 00:00:00 2001 From: Simon Hafner Date: Thu, 30 Jan 2014 02:07:21 -0600 Subject: added Cartesian product --- lib/pure/algorithm.nim | 32 ++++++++++++++++++++++++++++++++ tests/stdlib/talgorithm.nim | 9 +++++++++ 2 files changed, 41 insertions(+) create mode 100644 tests/stdlib/talgorithm.nim (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index df7ae6d17..2620f7c90 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -131,3 +131,35 @@ proc sort*[T](a: var openArray[T], dec(m, s*2) s = s*2 +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: + return + if x.len == 1: + result = @x + return + var + indexes = newSeq[int](x.len) + initial = newSeq[int](x.len) + 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): + initial[i] = len(x[i])-1 + indexes = initial + while true: + while indexes[index] == -1: + indexes[index] = initial[index] + index +=1 + if index == x.len: return + indexes[index] -=1 + for ni, i in indexes: + next[ni] = x[ni][i] + var res: seq[T] + shallowCopy(res, next) + result.add(res) + index = 0 + indexes[index] -=1 diff --git a/tests/stdlib/talgorithm.nim b/tests/stdlib/talgorithm.nim new file mode 100644 index 000000000..ea57883b0 --- /dev/null +++ b/tests/stdlib/talgorithm.nim @@ -0,0 +1,9 @@ +import unittest + +suite "product": + test "a simple case of one element": + check product(@[@[1,2]]) == @[@[1,2]] + test "two elements": + check product(@[@[1,2], @[3,4]]) == @[@[2,4],@[1,4],@[2,3],@[1,3]] + test "three elements": + check product(@[@[1,2], @[3,4], @[5,6]]) == @[@[2,4,6],@[1,4,6],@[2,3,6],@[1,3,6], @[2,4,5],@[1,4,5],@[2,3,5],@[1,3,5]] -- cgit 1.4.1-2-gfad0 From f070edb8b91d07bd4ac8fea82317b906cc5ec1c9 Mon Sep 17 00:00:00 2001 From: Simon Hafner Date: Thu, 30 Jan 2014 02:09:37 -0600 Subject: forgot to export product --- 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 2620f7c90..b71b2c0fc 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -131,7 +131,7 @@ proc sort*[T](a: var openArray[T], dec(m, s*2) s = s*2 -proc product[T](x: openarray[seq[T]]): seq[seq[T]] = +proc product*[T](x: openarray[seq[T]]): seq[seq[T]] = ## produces the Cartesian product of the array. Warning: complexity ## may explode. result = @[] -- cgit 1.4.1-2-gfad0 From e01fb17d023b046b3403a4413a637d24a9dc492f Mon Sep 17 00:00:00 2001 From: Simon Hafner Date: Thu, 30 Jan 2014 23:55:43 -0600 Subject: product more robust against empty input --- lib/pure/algorithm.nim | 1 + tests/stdlib/talgorithm.nim | 5 +++++ 2 files changed, 6 insertions(+) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index b71b2c0fc..921c659de 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -148,6 +148,7 @@ proc product*[T](x: openarray[seq[T]]): seq[seq[T]] = var next: seq[T] = @[] next.setLen(x.len) for i in 0..(x.len-1): + if len(x[i]) == 0: return initial[i] = len(x[i])-1 indexes = initial while true: diff --git a/tests/stdlib/talgorithm.nim b/tests/stdlib/talgorithm.nim index ea57883b0..37de1262f 100644 --- a/tests/stdlib/talgorithm.nim +++ b/tests/stdlib/talgorithm.nim @@ -1,6 +1,11 @@ import unittest +import algorithm suite "product": + test "empty input": + check product[int](newSeq[seq[int]]()) == newSeq[seq[int]]() + test "bit more empty input": + check product[int](@[newSeq[int](), @[], @[]]) == newSeq[seq[int]]() test "a simple case of one element": check product(@[@[1,2]]) == @[@[1,2]] test "two elements": -- cgit 1.4.1-2-gfad0 From baa304f37013b6be642aa6c9ae20990b6c489573 Mon Sep 17 00:00:00 2001 From: Charlie Barto Date: Sun, 23 Mar 2014 18:28:05 -0400 Subject: added lowerBound function to algorithm library --- lib/pure/algorithm.nim | 24 ++++++++++++++++++++++++ tests/stdlib/talgorithm.nim | 3 +++ 2 files changed, 27 insertions(+) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 921c659de..b6a97b5da 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -55,6 +55,30 @@ proc smartBinarySearch*[T](a: openArray[T], key: T): int = 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)) + ## the sequence will still be sorted + ## + ## `cmp` is the comparator function to use, the expected return values are the same as + ## that of system.cmp + result = a.low + var pos = result + var count, step: int + count = a.high - a.low + 1 + while count != 0: + pos = result + step = count div 2 + pos += step + if cmp(a[pos], key) < 0: + pos.inc + result = pos + count -= step + 1 + else: + count = step + +proc lowerBound*[T](a: openarray[T], key: T): int = lowerBound(a, key, system.cmp[T]) proc merge[T](a, b: var openArray[T], lo, m, hi: int, cmp: proc (x, y: T): int {.closure.}, order: TSortOrder) = template `<-` (a, b: expr) = diff --git a/tests/stdlib/talgorithm.nim b/tests/stdlib/talgorithm.nim index 7ab652c82..3ca425fbc 100644 --- a/tests/stdlib/talgorithm.nim +++ b/tests/stdlib/talgorithm.nim @@ -6,3 +6,6 @@ doAssert product(@[@[1,2]]) == @[@[1,2]], "a simple case of one element" doAssert product(@[@[1,2], @[3,4]]) == @[@[2,4],@[1,4],@[2,3],@[1,3]], "two elements" doAssert product(@[@[1,2], @[3,4], @[5,6]]) == @[@[2,4,6],@[1,4,6],@[2,3,6],@[1,3,6], @[2,4,5],@[1,4,5],@[2,3,5],@[1,3,5]], "three elements" doAssert product(@[@[1,2], @[]]) == newSeq[seq[int]](), "two elements, but one empty" +doAssert lowerBound([1,2,4], 3, system.cmp[int]) == 2 +doAssert lowerBound([1,2,2,3], 4, system.cmp[int]) == 4 +doAssert lowerBound([1,2,3,10], 11) == 4 \ No newline at end of file -- cgit 1.4.1-2-gfad0 From 976fb18a8f99adb9ccec5a248fcf36be7d07388f Mon Sep 17 00:00:00 2001 From: Charlie Barto Date: Sun, 23 Mar 2014 18:30:54 -0400 Subject: made the default comparator for lowerBound unqualified, so the user can customize via two phase lookup --- 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 b6a97b5da..fb0ba5355 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -78,7 +78,7 @@ proc lowerBound*[T](a: openarray[T], key: T, cmp: proc(x,y: T): int {.closure.}) else: count = step -proc lowerBound*[T](a: openarray[T], key: T): int = lowerBound(a, key, system.cmp[T]) +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: TSortOrder) = template `<-` (a, b: expr) = -- cgit 1.4.1-2-gfad0 From 491291ae24fe5901f4be918cbce2d6c21a0ae0e9 Mon Sep 17 00:00:00 2001 From: Charlie Barto Date: Thu, 27 Mar 2014 00:21:19 -0400 Subject: added usage example for lower bound --- lib/pure/algorithm.nim | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index fb0ba5355..49d1ac972 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -63,6 +63,11 @@ proc lowerBound*[T](a: openarray[T], key: T, cmp: proc(x,y: T): int {.closure.}) ## ## `cmp` is the comparator function to use, the expected return values are the same as ## that of system.cmp + ## + ## example: + ## `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]` result = a.low var pos = result var count, step: int -- cgit 1.4.1-2-gfad0 From 76dfa611ed480f81b33bf3966c2dddc7cc09159f Mon Sep 17 00:00:00 2001 From: Charlie Barto Date: Thu, 27 Mar 2014 15:13:10 -0400 Subject: fixed doc comment --- lib/pure/algorithm.nim | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'lib/pure/algorithm.nim') diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 49d1ac972..37fbc948c 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -64,10 +64,11 @@ proc lowerBound*[T](a: openarray[T], key: T, cmp: proc(x,y: T): int {.closure.}) ## `cmp` is the comparator function to use, the expected return values are the same as ## that of system.cmp ## - ## example: - ## `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]` + ## example:: + ## + ## 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]` result = a.low var pos = result var count, step: int -- cgit 1.4.1-2-gfad0