From: Jean Privat <jean@pryen.org>
Date: Fri, 4 Sep 2009 18:12:17 +0000 (-0400)
Subject: lib: add Array::sort !cmp
X-Git-Tag: v0.4~122
X-Git-Url: http://nitlanguage.org

lib: add Array::sort !cmp

Also add a test.

Signed-off-by: Jean Privat <jean@pryen.org>
---

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index 88d76c1..fa99224 100644
--- a/lib/standard/collection/array.nit
+++ b/lib/standard/collection/array.nit
@@ -335,6 +335,58 @@ special ArrayCapable[E]
 
 	# The size of `_items'.
 	var _capacity: Int = 0
+
+	# Sort the array using the !cmp function.
+	fun sort
+		!cmp(e1,e2: E): Int
+	do
+		sub_sort(0, length-1) !cmp(x,y) = cmp(x, y)
+	end
+
+	# Sort `array' between `from' and `to' indices
+	private fun sub_sort(from: Int, to: Int)
+		!cmp(e1,e2: E): Int
+	do
+		if from >= to then
+			return
+		else if from + 7 < to then
+			var pivot = self[from]
+			var i = from
+			var j = to
+			while j > i do
+				while i <= to and cmp(self[i], pivot) <= 0 do i += 1
+				while j > i and cmp(self[j], pivot) >= 0 do j -= 1
+				if j > i then
+					var t = self[i]
+					self[i] = self[j]
+					self[j] = t
+				end
+			end
+			self[from] = self[i-1]
+			self[i-1] = pivot
+			sub_sort(from, i-2) !cmp(x,y) = cmp(x, y)
+			sub_sort(i, to) !cmp(x,y) = cmp(x, y)
+		else
+			var i = from
+			while i < to do
+				var min = i
+				var min_v = self[i]
+				var j = i
+				while j <= to do
+					if cmp(min_v, self[j]) > 0 then
+						min = j
+						min_v = self[j]
+					end
+					j += 1
+				end
+				if min != i then
+					self[min] = self[i]
+					self[i] = min_v
+				end
+				i += 1
+			end
+		end
+	end
 end
 
 # An `Iterator' on `AbstractArray'
diff --git a/tests/example_array_sort.nit b/tests/example_array_sort.nit
new file mode 100644
index 0000000..028e584
--- /dev/null
+++ b/tests/example_array_sort.nit
@@ -0,0 +1,38 @@
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2005-2009 Jean Privat <jean@pryen.org>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+fun get_an_array(nb: Int): Array[Int]
+do
+	var res = new Array[Int].with_capacity(nb)
+	var j = 64
+	while res.length < nb do
+		j = (j * 3451 + 234) % 56557
+		var k = j % 90 + 10
+		res.add(k)
+	end
+	return res
+end
+
+var q = get_an_array(50)
+print(q.join(" "))
+q.sort !cmp(x,y) = x <=> y
+print(q.join(" "))
+q.sort !cmp(x,y) = (x%10) <=> (y%10)
+print(q.join(" "))
+q.sort !cmp(x,y) = y <=> x
+print(q.join(" "))
+q.sort !cmp(x,y) = (x%10) <=> (y%10)
+print(q.join(" "))
diff --git a/tests/sav/example_array_sort.sav b/tests/sav/example_array_sort.sav
new file mode 100644
index 0000000..2d41645
--- /dev/null
+++ b/tests/sav/example_array_sort.sav
@@ -0,0 +1,5 @@
+47 72 94 80 23 35 64 68 88 34 47 25 99 32 22 89 52 38 37 43 45 79 40 70 13 97 35 38 18 76 35 49 78 28 50 88 38 41 27 68 58 38 80 34 59 31 96 60 45 93
+13 18 22 23 25 27 28 31 32 34 34 35 35 35 37 38 38 38 38 40 41 43 45 45 47 47 49 50 52 58 59 60 64 68 68 70 72 76 78 79 80 80 88 88 89 93 94 96 97 99
+80 40 50 80 70 60 41 31 32 72 52 22 23 13 93 43 94 34 34 64 35 35 45 45 25 35 76 96 47 47 37 97 27 68 68 28 58 78 38 38 18 88 88 38 38 79 89 49 99 59
+99 97 96 94 93 89 88 88 80 80 79 78 76 72 70 68 68 64 60 59 58 52 50 49 47 47 45 45 43 41 40 38 38 38 38 37 35 35 35 34 34 32 31 28 27 25 23 22 18 13
+60 80 70 40 50 80 41 31 32 52 22 72 93 13 23 43 64 94 34 34 25 35 35 35 45 45 76 96 47 47 27 37 97 38 38 38 38 88 58 18 78 88 28 68 68 59 79 49 89 99