+
+ # Insertion-sort `array` between `from` and `to` indices
+ # Worst case: O(n^2), average case: O(n^2)
+ #
+ # var a = [5, 2, 3, 1, 4]
+ # default_comparator.insertion_sort(a, 0, a.length - 1)
+ # assert a == [1, 2, 3, 4, 5]
+ fun insertion_sort(array: Array[COMPARED], from: Int, to: Int) do
+ for i in [from..to] do
+ var j = i
+ while j > 0 and compare(array[j], array[j - 1]) < 0 do
+ array.swap_at(j, j - 1)
+ j -= 1
+ end
+ end
+ end
+
+ # Merge-sort `array` between `from` and `to` indices
+ # Worst case: O(n lg n), average: O(n lg n)
+ #
+ # var a = [5, 2, 3, 1, 4]
+ # default_comparator.merge_sort(a, 0, a.length - 1)
+ # assert a == [1, 2, 3, 4, 5]
+ fun merge_sort(array: Array[COMPARED], from, to: Int) do
+ if from >= to then return
+ var mid = (to + from) / 2
+ merge_sort(array, from, mid)
+ merge_sort(array, mid + 1, to)
+ merge(array, from, mid, to)
+ end
+
+ private fun merge(array: Array[COMPARED], from, mid, to: Int) do
+ var l = new Array[COMPARED]
+ for i in [from..mid] do l.add array[i]
+ var r = new Array[COMPARED]
+ for i in [mid + 1..to] do r.add array[i]
+ var i = 0
+ var j = 0
+ for k in [from..to] do
+ if i >= l.length then
+ array[k] = r[j]
+ j += 1
+ else if j >= r.length then
+ array[k] = l[i]
+ i += 1
+ else if compare(l[i], r[j]) <= 0 then
+ array[k] = l[i]
+ i += 1
+ else
+ array[k] = r[j]
+ j += 1
+ end
+ end
+ end
+
+ # Heap-sort `array` between `from` and `to` indices
+ # Worst case: O(n lg n), average: O(n lg n)
+ #
+ # var a = [5, 2, 3, 1, 4]
+ # default_comparator.heap_sort(a, 0, a.length - 1)
+ # assert a == [1, 2, 3, 4, 5]
+ fun heap_sort(array: Array[COMPARED], from, to: Int) do
+ var size = build_heap(array)
+ for j in [from..to[ do
+ array.swap_at(0, size)
+ size -= 1
+ heapify(array, 0, size)
+ end
+ end
+
+ private fun build_heap(array: Array[COMPARED]): Int do
+ var size = array.length - 1
+ var i = size / 2
+ while i >= 0 do
+ heapify(array, i, size)
+ i -= 1
+ end
+ return size
+ end
+
+ private fun heapify(array: Array[COMPARED], from, to: Int) do
+ var l = from * 2
+ var r = l + 1
+ var largest: Int
+ if l < to and compare(array[l], array[from]) > 0 then
+ largest = l
+ else
+ largest = from
+ end
+ if r < to and compare(array[r], array[largest]) > 0 then
+ largest = r
+ end
+ if largest != from then
+ array.swap_at(from, largest)
+ heapify(array, largest, to)
+ end
+ end
+
+end
+
+redef class MapRead[K,V]
+ # Return an array of all values sorted with their keys using `comparator`.
+ #
+ # ~~~
+ # var map = new HashMap[Int, String]
+ # map[10] = "ten"
+ # map[2] = "two"
+ # map[1] = "one"
+ # assert map.values_sorted_by_key(default_comparator) == ["one", "two", "ten"]
+ # assert map.values_sorted_by_key(alpha_comparator) == ["one", "ten", "two"]
+ # ~~~
+ fun values_sorted_by_key(comparator: Comparator): Array[V]
+ do
+ var keys = self.keys.to_a
+ comparator.sort(keys)
+ return [for k in keys do self[k]]
+ end
+
+ # Return an array of all keys sorted with their values using `comparator`.
+ #
+ # ~~~
+ # var map = new HashMap[String, Int]
+ # map["ten"] = 10
+ # map["two"] = 2
+ # map["one"] = 1
+ # assert map.keys_sorted_by_values(default_comparator) == ["one", "two", "ten"]
+ # assert map.keys_sorted_by_values(alpha_comparator) == ["one", "ten", "two"]
+ # ~~~
+ #
+ # See: `to_map_comparator` to get the comparator used internally.
+ fun keys_sorted_by_values(comparator: Comparator): Array[K]
+ do
+ var keys = self.keys.to_a
+ var map_cmp = to_map_comparator(comparator)
+ map_cmp.sort(keys)
+ return keys
+ end
+
+ # A comparator that compares things with their values in self.
+ #
+ # See `MapComparator` for details.
+ fun to_map_comparator(comparator: Comparator): MapComparator[K, V] do return new MapComparator[K,V](self, comparator)