[libgee] Add ArrayList.sort_with_data

[Maciej Marcin Piechotka <mpiechotka src gnome org>]

commit 5af45076013d07862246bf3f55195a3e72a68f24
Author: Zeeshan Ali (Khattak) <zeeshanak gnome org>
Date:   Sat Jul 24 04:40:11 2010 +0300

    Add ArrayList.sort_with_data
    
    Add a variant of List.sort that takes CompareDataFunc rather than
    CompareFunc so compare func could be a method or closure. We are
    adding this to ArrayList rather than List to not break the API/ABI.
    In 0.7.x, this method will be removed as List.sort will then do
    exactly the same.

 gee/arraylist.vala |   12 ++++++++++++
 gee/timsort.vala   |   31 +++++++++++++++++++++++++++----
 2 files changed, 39 insertions(+), 4 deletions(-)
---
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
index 3654fb1..01f48d8 100644
--- a/gee/arraylist.vala
+++ b/gee/arraylist.vala
@@ -223,6 +223,18 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 		return true;
 	}
 
+	/**
+	 * Sorts items by comparing with the specified compare function.
+	 *
+	 * WARNING: This method has only been added as hack and will not
+	 *          exist after the next odd minor version bump (>= 0.7.x).
+	 *
+	 * @param compare_func compare function to use to compare items
+	 */
+	public void sort_with_data (CompareDataFunc compare) {
+		TimSort.sort_with_data<G> (this, compare);
+	}
+
 	private void shift (int start, int delta) {
 		assert (start >= 0);
 		assert (start <= _size);
diff --git a/gee/timsort.vala b/gee/timsort.vala
index 1fbc10b..cb79ced 100644
--- a/gee/timsort.vala
+++ b/gee/timsort.vala
@@ -54,7 +54,17 @@ internal class Gee.TimSort<G> : Object {
 		}
 	}
 
-	private static void sort_list<G> (List<G> list, CompareFunc compare) {
+	public static void sort_with_data<G> (List<G> list, CompareDataFunc compare_data) {
+		if (list is ArrayList) {
+			TimSort.sort_arraylist<G> ((ArrayList<G>) list, null, compare_data);
+		} else {
+			TimSort.sort_list<G> (list, null, compare_data);
+		}
+	}
+
+	private static void sort_list<G> (List<G> list, CompareFunc? compare, CompareDataFunc? compare_data = null) {
+        assert (compare != null || compare_data != null);
+
 		TimSort<G> helper = new TimSort<G> ();
 
 		helper.list_collection = list;
@@ -63,6 +73,7 @@ internal class Gee.TimSort<G> : Object {
 		helper.index = 0;
 		helper.size = list.size;
 		helper.compare = compare;
+		helper.compare_data = compare_data;
 
 		helper.do_sort ();
 
@@ -73,7 +84,9 @@ internal class Gee.TimSort<G> : Object {
 		}
 	}
 
-	private static void sort_arraylist<G> (ArrayList<G> list, CompareFunc compare) {
+	private static void sort_arraylist<G> (ArrayList<G> list, CompareFunc? compare, CompareDataFunc? compare_data = null) {
+        assert (compare != null || compare_data != null);
+
 		TimSort<G> helper = new TimSort<G> ();
 
 		helper.list_collection = list;
@@ -81,6 +94,7 @@ internal class Gee.TimSort<G> : Object {
 		helper.index = 0;
 		helper.size = list._size;
 		helper.compare = compare;
+		helper.compare_data = compare_data;
 
 		helper.do_sort ();
 	}
@@ -95,6 +109,7 @@ internal class Gee.TimSort<G> : Object {
 	private Slice<G>*[] pending;
 	private int minimum_gallop;
 	private CompareFunc compare;
+	private CompareDataFunc compare_data;
 
 	private void do_sort () {
 		if (size < 2) {
@@ -153,11 +168,19 @@ internal class Gee.TimSort<G> : Object {
 	private delegate bool LowerFunc (G left, G right);
 
 	private inline bool lower_than (G left, G right) {
-		return compare (left, right) < 0;
+        if (compare != null) {
+            return compare (left, right) < 0;
+        } else {
+            return compare_data (left, right) < 0;
+        }
 	}
 
 	private inline bool lower_than_or_equal_to (G left, G right) {
-		return compare (left, right) <= 0;
+        if (compare != null) {
+            return compare (left, right) <= 0;
+        } else {
+            return compare_data (left, right) <= 0;
+        }
 	}
 
 	private int compute_minimum_run_length (int length) {