[prev in list] [next in list] [prev in thread] [next in thread] 

List:       mono-devel-list
Subject:    [Mono-devel-list] [Patch] Array.Sort
From:       Carlos Alberto Cortez <calberto.cortez () gmail ! com>
Date:       2005-03-02 22:06:44
Message-ID: 1109801205.2608.9.camel () localhost ! localdomain
[Download RAW message or body]

Attached is a patch for implementing Array.Sort generic methods. Could
somebody review it?

Carlos.

["sort.diff" (sort.diff)]

Index: Array.cs
===================================================================
--- Array.cs	(revisión: 41210)
+++ Array.cs	(copia de trabajo)
@@ -37,6 +37,7 @@
 using System.Runtime.CompilerServices;
 using System.Runtime.InteropServices;
 #if NET_2_0
+using System.Reflection;
 using System.Collections.Generic;
 using System.Runtime.ConstrainedExecution;
 #endif
@@ -1122,6 +1123,128 @@
 			}
 		}
 
+#if NET_2_0
+		[CLSCompliant (false)]
+		public static void Sort<T> (T [] array)
+		{
+			if (array == null)
+				throw new ArgumentNullException ("array");
+
+			Sort<T, T> (array, null, 0, array.Length, Comparer<T>.Default);
+		}
+
+		[CLSCompliant (false)]
+		public static void Sort<K, V> (K [] keys, V [] items)
+		{
+			Sort<K, V> (keys, items, 0, keys.Length, Comparer<K>.Default);
+		}
+
+		[CLSCompliant (false)]
+		public static void Sort<T> (T [] array, Comparison<T> comparison)
+		{
+			if (array == null)
+				throw new ArgumentNullException ("array");
+
+			Sort<T, T> (array, null, 0, array.Length, comparison);
+		}
+
+		[CLSCompliant (false)]
+		public static void Sort<T> (T [] array, IComparer<T> comparer)
+		{
+			if (array == null)
+				throw new ArgumentNullException ("array");
+
+			Sort<T, T> (array, null, 0, array.Length, comparer);
+		}
+
+		[CLSCompliant (false)]
+		public static void Sort<K, V> (K [] keys, V [] items, IComparer<K> comparer)
+		{
+			Sort<K, V> (keys, items, 0, keys.Length, comparer);
+		}
+
+		[CLSCompliant (false)]
+		public static void Sort<T> (T [] array, int index, int length)
+		{
+			if (array == null)
+				throw new ArgumentNullException ("array");
+			
+			Sort<T, T> (array, null, index, length, Comparer<T>.Default);
+		}
+
+		[CLSCompliant (false)]
+		public static void Sort<K, V> (K [] keys, V [] items, int index, int length)
+		{
+			Sort<K, V> (keys, items, index, length, Comparer<K>.Default);
+		}
+
+		[CLSCompliant (false)]
+		public static void Sort<T> (T [] array, int index, int length, IComparer<T> \
comparer) +		{
+			if (array == null)
+				throw new ArgumentNullException ("array");
+
+			Sort<T, T> (array, null, index, length, comparer);
+		}
+
+		[CLSCompliant (false)]
+		public static void Sort<K, V> (K [] keys, V [] items, int index, int length, \
IComparer<K> comparer) +		{
+			IComparer<K> comp = comparer != null ? comparer : Comparer<K>.Default;
+			Comparison<K> comparison = (Comparison<K>) Delegate.CreateDelegate (typeof \
(Comparison<K>), comp, "Compare"); +
+			Sort<K, V> (keys, items, index, length, comparison);
+		}
+
+		private static void Sort <K, V> (K [] keys, V [] items, int index, int length, \
Comparison<K> comparison) +		{
+			if (keys == null)
+				throw new ArgumentNullException ("keys");
+
+			if (index < 0)
+				throw new ArgumentOutOfRangeException ("index");
+
+			if (length < 0)
+				throw new ArgumentOutOfRangeException ("length", Locale.GetText (
+					"Value has to be >= 0."));
+
+			if (keys.Length - index < length
+				|| (items != null && index > items.Length - length))
+				throw new ArgumentException ();
+			
+			//
+			// Check for value types which can be sorted without Compare () method
+			//
+			if (default (K) != null) {
+				Swapper iswapper;
+				if (items == null)
+					iswapper = null;
+				else 
+					iswapper = get_swapper (items);
+				if (keys is double[]) {
+					combsort (keys as double[], index, length, iswapper);
+					return;
+				}
+				if (keys is int[]) {
+					combsort (keys as int[], index, length, iswapper);
+					return;
+				}
+				if (keys is char[]) {
+					combsort (keys as char[], index, length, iswapper);
+					return;
+				}
+			}
+			try {
+				int low0 = index;
+				int high0 = index + length - 1;
+				qsort<K, V> (keys, items, low0, high0, comparison);
+			}
+			catch (Exception e) {
+				throw new InvalidOperationException (Locale.GetText ("The comparer threw an \
exception."), e); +			}
+		}
+#endif
+
 		/* note, these are instance methods */
 		void int_swapper (int i, int j) {
 			int[] array = this as int[];
@@ -1262,6 +1385,38 @@
 				qsort (keys, items, low, high0, comparer);
 		}
 
+#if NET_2_0
+		private static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, \
Comparison<K> comparison) +		{
+			if (low0 >= high0)
+				return;
+
+			int low = low0;
+			int high = high0;
+
+			K keyPivot = keys [(low + high) / 2];
+
+			while (low <= high) {
+				// Move the walls in
+				while (low < high0 && comparison (keys [low], keyPivot) < 0)
+					++low;
+				while (high > low0 && comparison (keyPivot, keys [high]) < 0)
+					--high;
+
+				if (low <= high) {
+					swap<K, V> (keys, items, low, high);
+					++low;
+					--high;
+				}
+			}
+
+			if (low0 < high)
+				qsort<K, V> (keys, items, low0, high, comparison);
+			if (low < high0)
+				qsort<K, V> (keys, items, low, high0, comparison);
+		}
+#endif
+
 		private static void swap (Array keys, Array items, int i, int j)
 		{
 			object tmp;
@@ -1277,6 +1432,24 @@
 			}
 		}
 
+#if NET_2_0
+		private static void swap<K, V> (K [] keys, V [] items, int i, int j)
+		{
+			K tmp;
+
+			tmp = keys [i];
+			keys [i] = keys [j];
+			keys [j] = tmp;
+
+			if (items != null) {
+				V itmp;
+				itmp = items [i];
+				items [i] = items [j];
+				items [j] = itmp;
+			}
+		}
+#endif
+
 		private static int compare (object value1, object value2, IComparer comparer)
 		{
 			if (value1 == null)



[prev in list] [next in list] [prev in thread] [next in thread]