Merge pull request #1032 from barcharcraz/lowerBound

Added lowerBound function to the stdlib

1 files changed, 29 insertions, 0 deletions

diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index 921c659de..49d1ac972 100644
--- a/lib/pure/algorithm.nim
+++ b/lib/pure/algorithm.nim
@@ -55,6 +55,35 @@ 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) =