From ea1809a931d401e97959f8fd3ddd44b5f65c77c0 Mon Sep 17 00:00:00 2001
From: apense <apense@users.noreply.github.com>
Date: Wed, 17 Jun 2015 19:56:32 -0400
Subject: Added `isSorted` proc

Linear-time verification that an openarray is sorted. Operates on the same parameters as `sort`. Seems much cheaper for large sorts.
---
 lib/pure/algorithm.nim | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

(limited to 'lib/pure/algorithm.nim')

diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index c9f779018..bfc2e0351 100644
--- a/lib/pure/algorithm.nim
+++ b/lib/pure/algorithm.nim
@@ -237,6 +237,19 @@ template sortedByIt*(seq1, op: expr): expr =
     result = cmp(a, b))
   result
 
+proc isSorted*[T](a: openarray[T],
+                 cmp: proc(x, y: T): int {.closure.},
+                 order = SortOrder.Ascending): bool =
+  ## Tests whether `a` is sorted
+  if len(a) <= 1: return true # empty or one-element lists are already sorted
+
+  result = true
+  for i in 0..<len(a)-1:
+    if cmp(a[i],a[i+1]) * order <= 0: # same test as `sort`
+      continue
+    else:
+      return false
+
 proc product*[T](x: openArray[seq[T]]): seq[seq[T]] =
   ## produces the Cartesian product of the array. Warning: complexity
   ## may explode.
@@ -340,4 +353,14 @@ when isMainModule:
   assert arr.lowerBound(4) == 1
   assert arr.lowerBound(5) == 1
   assert arr.lowerBound(6) == 2
+  # Tests for isSorted
+  var srt1 = [1,2,3,4,4,4,4,5]
+  var srt2 = ["iello","hello"]
+  var srt3 = [1.0,1.0,1.0]
+  var srt4 = []
+  assert srt1.isSorted(cmp) == true
+  assert srt2.isSorted(cmp) == false
+  assert srt3.isSorted(cmp) == true
+  var srtseq = newSeq[int]()
+  assert srtseq.isSorted(cmp) == true
 
-- 
cgit 1.4.1-2-gfad0


From 34910471419637bc616c08f369715ffbf4d881d1 Mon Sep 17 00:00:00 2001
From: apense <apense@users.noreply.github.com>
Date: Wed, 17 Jun 2015 20:14:53 -0400
Subject: Fixed silly continue

The old if/else was weird and unnecessary
---
 lib/pure/algorithm.nim | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

(limited to 'lib/pure/algorithm.nim')

diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index bfc2e0351..32bf9eb98 100644
--- a/lib/pure/algorithm.nim
+++ b/lib/pure/algorithm.nim
@@ -240,14 +240,11 @@ template sortedByIt*(seq1, op: expr): expr =
 proc isSorted*[T](a: openarray[T],
                  cmp: proc(x, y: T): int {.closure.},
                  order = SortOrder.Ascending): bool =
-  ## Tests whether `a` is sorted
-  if len(a) <= 1: return true # empty or one-element lists are already sorted
+  if len(a) <= 1: return true
 
   result = true
   for i in 0..<len(a)-1:
-    if cmp(a[i],a[i+1]) * order <= 0: # same test as `sort`
-      continue
-    else:
+    if cmp(a[i],a[i+1]) * order > 0:
       return false
 
 proc product*[T](x: openArray[seq[T]]): seq[seq[T]] =
-- 
cgit 1.4.1-2-gfad0


From 138cf777da38925a4f91239b8c858112d4464436 Mon Sep 17 00:00:00 2001
From: apense <apense@users.noreply.github.com>
Date: Thu, 18 Jun 2015 14:43:38 -0400
Subject: Removed redundant check

Loop takes care of it already
---
 lib/pure/algorithm.nim | 2 --
 1 file changed, 2 deletions(-)

(limited to 'lib/pure/algorithm.nim')

diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index 32bf9eb98..b6bcdab7e 100644
--- a/lib/pure/algorithm.nim
+++ b/lib/pure/algorithm.nim
@@ -240,8 +240,6 @@ template sortedByIt*(seq1, op: expr): expr =
 proc isSorted*[T](a: openarray[T],
                  cmp: proc(x, y: T): int {.closure.},
                  order = SortOrder.Ascending): bool =
-  if len(a) <= 1: return true
-
   result = true
   for i in 0..<len(a)-1:
     if cmp(a[i],a[i+1]) * order > 0:
-- 
cgit 1.4.1-2-gfad0


From dc41beed5a00db02b8d4accf40916b5684df3c3b Mon Sep 17 00:00:00 2001
From: apense <apense@users.noreply.github.com>
Date: Thu, 18 Jun 2015 18:53:42 -0400
Subject: Added documentation

Now `isSorted` is documented.
---
 lib/pure/algorithm.nim | 3 +++
 1 file changed, 3 insertions(+)

(limited to 'lib/pure/algorithm.nim')

diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index b6bcdab7e..ac18ae420 100644
--- a/lib/pure/algorithm.nim
+++ b/lib/pure/algorithm.nim
@@ -240,6 +240,9 @@ template sortedByIt*(seq1, op: expr): expr =
 proc isSorted*[T](a: openarray[T],
                  cmp: proc(x, y: T): int {.closure.},
                  order = SortOrder.Ascending): bool =
+  ## Checks to see whether `a` is already sorted in `order`
+  ## using `cmp` for the comparison. Parameters identical
+  ## to `sort`
   result = true
   for i in 0..<len(a)-1:
     if cmp(a[i],a[i+1]) * order > 0:
-- 
cgit 1.4.1-2-gfad0