1 files changed, 65 insertions, 2 deletions
diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index 8b44e69d9..37fbc948c 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:
@@ -55,6 +55,36 @@ 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
+  ## 
+  ## 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
+  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, 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) = 
@@ -79,7 +109,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
@@ -131,3 +161,36 @@ 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):
+    if len(x[i]) == 0: return
+    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