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 (file)
--- 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 (file)
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 (file)
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