[libgee] Refactor benchmarks

[Maciej Marcin Piechotka <mpiechotka src gnome org>]

commit 798b069346adb3b7ec18f0ce5f2dfa5d55c031f4
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date:   Sun Feb 19 02:22:38 2012 +0000

    Refactor benchmarks

 benchmark/Makefile.am         |    1 -
 benchmark/benchmark.vala      |   31 ++++++++++++
 benchmark/benchmarksorts.vala |   95 ++++++++++++++++++++++++++++++++++-
 benchmark/mergesort.vala      |  110 -----------------------------------------
 4 files changed, 124 insertions(+), 113 deletions(-)
---
diff --git a/benchmark/Makefile.am b/benchmark/Makefile.am
index f43ebbb..22513f7 100644
--- a/benchmark/Makefile.am
+++ b/benchmark/Makefile.am
@@ -5,7 +5,6 @@ noinst_PROGRAMS = benchmarks
 benchmarks_SOURCES = \
 	benchmark.vala \
 	benchmarksorts.vala \
-	mergesort.vala \
 	$(NULL)
 
 benchmarks_VALAFLAGS = \
diff --git a/benchmark/benchmark.vala b/benchmark/benchmark.vala
index 0aae1a5..f973931 100644
--- a/benchmark/benchmark.vala
+++ b/benchmark/benchmark.vala
@@ -2,6 +2,7 @@
  *
  * Copyright (C) 2008  JÃrg Billeter
  * Copyright (C) 2009  Didier Villevalois
+
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -24,6 +25,36 @@
 using Gee;
 
 namespace Gee.Benchmark {
+	OptionEntry run_benchmark_option(string long_name, char short_name, string description, ref bool do_run) {
+		return OptionEntry() {
+			long_name = long_name,
+			short_name = short_name,
+			flags = 0,
+			arg = OptionArg.NONE,
+			arg_data = &do_run,
+			description = description,
+			arg_description = null
+		};
+	}
+
+	int main (string[] args) {
+		bool run_sort = false;
+		OptionEntry[] entries = {
+			run_benchmark_option("run-sort", 's', "Run sorting benchmark", ref run_sort)
+		};
+		var context = new OptionContext ("Run various benchmarks");
+		context.add_main_entries (entries, "gee-benchmark");
+		try {
+			context.parse (ref args);
+		} catch (OptionError e) {
+			stdout.printf ("option parsing failed: %s\n", e.message);
+			return 2;
+		}
+		if(run_sort) {
+			benchmark_sorts ();
+		}
+		return 0;
+	}
 
 	public interface Factory<G> : Object {
 
diff --git a/benchmark/benchmarksorts.vala b/benchmark/benchmarksorts.vala
index 28272ca..94f4f3e 100644
--- a/benchmark/benchmarksorts.vala
+++ b/benchmark/benchmarksorts.vala
@@ -19,6 +19,7 @@
  *
  * Author:
  * 	Didier 'Ptitjes Villevalois <ptitjes free fr>
+ * 	Will <tcosprojects gmail com>
  */
 
 using Gee;
@@ -44,7 +45,7 @@ namespace Gee.Benchmark {
 		}
 	}
 
-	void main (string[] args) {
+	public void benchmark_sorts () {
 		var algorithms = new ArrayList<Algorithm<int32>> ();
 		algorithms.add (new TimSort<int32> ());
 		algorithms.add (new MergeSort<int32> ());
@@ -57,7 +58,7 @@ namespace Gee.Benchmark {
 		generators.add (new SortedInt32 ());
 
 		Benchmark<int32> benchmark =
-			new Benchmark<int32> (new ArrayListFactory<int32> (),
+		    new Benchmark<int32> (new ArrayListFactory<int32> (),
 		                          algorithms,
 		                          generators,
 		                          new int[] { 10,
@@ -71,3 +72,93 @@ namespace Gee.Benchmark {
 		benchmark.run ();
 	}
 }
+
+internal class Gee.MergeSort<G> {
+
+	public static void sort<G> (List<G> list, CompareDataFunc compare) {
+		if (list is ArrayList) {
+			MergeSort.sort_arraylist<G> ((ArrayList<G>) list, compare);
+		} else {
+			MergeSort.sort_list<G> (list, compare);
+		}
+	}
+
+	public static void sort_list<G> (List<G> list, CompareDataFunc compare) {
+		MergeSort<G> helper = new MergeSort<G> ();
+
+		helper.list_collection = list;
+		helper.array = list.to_array ();
+		helper.list = helper.array;
+		helper.index = 0;
+		helper.size = list.size;
+		helper.compare = compare;
+
+		helper.do_sort ();
+
+		// TODO Use a list iterator and use iter.set(item)
+		list.clear ();
+		foreach (G item in helper.array) {
+			list.add (item);
+		}
+	}
+
+	public static void sort_arraylist<G> (ArrayList<G> list, CompareDataFunc compare) {
+		MergeSort<G> helper = new MergeSort<G> ();
+
+		helper.list_collection = list;
+		helper.list = list._items;
+		helper.index = 0;
+		helper.size = list._size;
+		helper.compare = compare;
+
+		helper.do_sort ();
+	}
+
+	private List<G> list_collection;
+	private G[] array;
+	private unowned G[] list;
+	private int index;
+	private int size;
+	private CompareDataFunc compare;
+
+	private void do_sort () {
+		if (this.size <= 1) {
+			return;
+		}
+
+		var work_area = new G[this.size];
+
+		merge_sort_aux (index, this.size, work_area);
+	}
+
+	private void merge_sort_aux (int left, int right, G[] work_area) {
+		if (right == left + 1) {
+			return;
+		} else {
+			int size = right - left;
+			int middle = size / 2;
+			int lbegin = left;
+			int rbegin = left + middle;
+
+			merge_sort_aux (left, left + middle, work_area);
+			merge_sort_aux (left + middle, right, work_area);
+
+			for (int i = 0; i < size; i++) {
+				if (lbegin < left + middle && (rbegin == right ||
+					compare (list[lbegin], list[rbegin]) <= 0)) {
+
+					work_area[i] = list[lbegin];
+					lbegin++;
+				} else {
+					work_area[i] = list[rbegin];
+					rbegin++;
+				}
+			}
+
+			for (int i = left; i < right; i++) {
+				list[i] = work_area[i - left];
+			}
+		}
+	}
+}
+