[Mono-devel-list] Mono .net 2.0 preview and generics
prw at ceiriog1.demon.co.uk
prw at ceiriog1.demon.co.uk
Thu May 13 11:12:45 EDT 2004
Hi,
I've just got started with Mono and .NET. I need to know whether it is a
viable platform for a project for which I have previously used C++ with
its templates, so I'm testing on some substantial examples found on
the WWW.
On the example attached, I get the following errors from gmcs (The 0.91
RPM for mono-preview).
[prw at desdemona generics]$ gmcs Gsort.cs
Mono C# Compiler 0.91.0.0 for Generics
Gsort.cs(70) error CS1502: The best overloaded match for method 'void Polysort.swap (T, T)' has some invalid arguments
Gsort.cs(70) error CS1503: Argument 0: Cannot convert from 'ref T' to 'T'
Gsort.cs(103) error CS1502: The best overloaded match for method 'void Polysort.swap (T, T)' has some invalid arguments
Gsort.cs(103) error CS1503: Argument 0: Cannot convert from 'ref T' to 'T'
Compilation failed: 4 error(s), 0 warnings
Should not the template (sorry, generic) Polysort.swap<U> be instantiated
automatically to resolve the calls on line 70 and 103? Is this yet
to be fixed in gmcs, or am I doing something wrong (quite possible
as I am such a noobie here :)
Peter Wainwright
********
// Sorting with Generic C#, and comparisons with dynamically typed sorting
// Revised to use three-way comparisons (IComparable and IGComparable)
// Sorting integers or strings
// This program requires .NET version 2.0.
// Peter Sestoft (sestoft at dina.kvl.dk) * 2001-11-01, 2001-11-22, 2003-08-11
using System;
// Generic sorting routines
public class Polysort {
// Cannot use this in
// void qsort<T>(IGComparable<T>[] arr, int a, int b)
// because ref arguments that are array elements of reference
// type must have the exact element type of the formal parameter
private static void swap<U>(ref U s, ref U t) {
U tmp = s; s = t; t = tmp;
}
private static void swap<U>(U[] arr, int s, int t) {
U tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
}
private static void swap(object[] arr, int s, int t) {
object tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
}
// Polymorphic OO-style quicksort: general, not typesafe
private static void qsort<T>(IGComparable<T>[] arr, int a, int b) {
// sort arr[a..b]
if (a < b) {
int i = a, j = b;
IGComparable<T> x = arr[(i+j) / 2];
do {
while (arr[i].CompareTo(x) < 0) i++;
while (x.CompareTo(arr[j]) < 0) j--;
if (i <= j) {
swap< IGComparable<T> >(arr, i, j);
i++; j--;
}
} while (i <= j);
qsort<T>(arr, a, j);
qsort<T>(arr, i, b);
}
}
public static void Quicksort<T>(IGComparable<T>[] arr) {
qsort<T>(arr, 0, arr.Length-1);
}
public static void CheckSorted<T>(IGComparable<T>[] arr) {
for (int i=1; i<arr.Length; i++)
if (arr[i].CompareTo(arr[i-1]) < 0)
throw new Exception("Polysort.CheckSorted");
}
// Polymorphic functional-style quicksort: general, typesafe
private static void qsort<T>(T[] arr, IGComparer<T> cmp, int a, int b) {
// sort arr[a..b]
if (a < b) {
int i = a, j = b;
T x = arr[(i+j) / 2];
do {
while (cmp.Compare(arr[i], x) < 0) i++;
while (cmp.Compare(x, arr[j]) < 0) j--;
if (i <= j) {
swap<T>(ref arr[i], ref arr[j]); // ***** LINE 70 *****
// swap<T>(arr, i, j);
i++; j--;
}
} while (i <= j);
qsort<T>(arr, cmp, a, j);
qsort<T>(arr, cmp, i, b);
}
}
public static void Quicksort<T>(T[] arr, IGComparer<T> cmp) {
qsort<T>(arr, cmp, 0, arr.Length-1);
}
public static void CheckSorted<T>(T[] arr, IGComparer<T> cmp) {
for (int i=1; i<arr.Length; i++)
if (cmp.Compare(arr[i], arr[i-1]) < 0)
throw new Exception("Polysort.CheckSorted");
}
// Polymorphic functional-style quicksort using delegates: general, typesafe
public delegate int DGComparer<T>(T v1, T v2);
private static void qsort<T>(T[] arr, DGComparer<T> cmp, int a, int b) {
// sort arr[a..b]
if (a < b) {
int i = a, j = b;
T x = arr[(i+j) / 2];
do {
while (cmp(arr[i], x) < 0) i++;
while (cmp(x, arr[j]) < 0) j--;
if (i <= j) {
swap<T>(ref arr[i], ref arr[j]); // ***** LINE 103 *****
// swap<T>(arr, i, j);
i++; j--;
}
} while (i <= j);
qsort<T>(arr, cmp, a, j);
qsort<T>(arr, cmp, i, b);
}
}
public static void Quicksort<T>(T[] arr, DGComparer<T> cmp) {
qsort<T>(arr, cmp, 0, arr.Length-1);
}
}
public class Polyselfsort {
private static void swap<T>(T[] arr, int s, int t) {
T tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
}
// Polymorphic OO-style quicksort: general, typesafe
// Note the type parameter bound in the generic method
public static void qsort<T>(T[] arr, int a, int b)
where T : IGSelfComparable<T> {
// sort arr[a..b]
if (a < b) {
int i = a, j = b;
T x = arr[(i+j) / 2];
do {
while (arr[i].CompareTo(x) < 0) i++;
while (x.CompareTo(arr[j]) < 0) j--;
if (i <= j) {
swap<T>(arr, i, j);
i++; j--;
}
} while (i <= j);
qsort<T>(arr, a, j);
qsort<T>(arr, i, b);
}
}
public static void Quicksort<T>(T[] arr) where T : IGSelfComparable<T> {
qsort<T>(arr, 0, arr.Length-1);
}
}
public class Objsort {
private static void swap(object[] arr, int s, int t) {
object tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
}
// OO-style IComparable quicksort: general, not typesafe
private static void qsort(IComparable[] arr, int a, int b) {
// sort arr[a..b]
if (a < b) {
int i = a, j = b;
IComparable x = arr[(i+j) / 2];
do {
while (arr[i].CompareTo(x) < 0) i++;
while (x.CompareTo(arr[j]) < 0) j--;
if (i <= j) {
swap(arr, i, j);
i++; j--;
}
} while (i <= j);
qsort(arr, a, j);
qsort(arr, i, b);
}
}
public static void Quicksort(IComparable[] arr) {
qsort(arr, 0, arr.Length-1);
}
public static void CheckSorted(IComparable[] arr) {
for (int i=1; i<arr.Length; i++)
if (arr[i].CompareTo(arr[i-1]) < 0)
throw new Exception("Objsort.CheckSorted");
}
}
public class Intsort {
private static void swap(int[] arr, int s, int t) {
int tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
}
// Plain monomorphic quicksort: not general, but typesafe
private static void qsort(int[] arr, int a, int b) {
// sort arr[a..b]
if (a < b) {
int i = a, j = b;
int x = arr[(i+j) / 2];
do {
while (arr[i] < x) i++;
while (x < arr[j]) j--;
if (i <= j) {
swap(arr, i, j);
i++; j--;
}
} while (i <= j);
qsort(arr, a, j);
qsort(arr, i, b);
}
}
public static void Quicksort(int[] arr) {
qsort(arr, 0, arr.Length-1);
}
public static void CheckSorted(int[] arr) {
for (int i=1; i<arr.Length; i++)
if (arr[i] < arr[i-1])
throw new Exception("Intsort.CheckSorted");
}
}
public class Stringsort {
private static void swap(string[] arr, int s, int t) {
string tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
}
// Plain monomorphic quicksort: not general, but typesafe
private static void qsort(string[] arr, int a, int b) {
// sort arr[a..b]
if (a < b) {
int i = a, j = b;
string x = arr[(i+j) / 2];
do {
while (string.Compare(arr[i],x) < 0) i++;
while (string.Compare(x,arr[j]) < 0) j--;
if (i <= j) {
swap(arr, i, j);
i++; j--;
}
} while (i <= j);
qsort(arr, a, j);
qsort(arr, i, b);
}
}
public static void Quicksort(string[] arr) {
qsort(arr, 0, arr.Length-1);
}
public static void CheckSorted(string[] arr) {
for (int i=1; i<arr.Length; i++)
if (string.Compare(arr[i], arr[i-1]) < 0)
throw new Exception("Stringsort.CheckSorted");
}
}
public class FunIntsort {
private static void swap(int[] arr, int s, int t) {
int tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
}
// Monomorphic quicksort with comparer: not general, but typesafe
private static void qsort(int[] arr, IIntComparer cmp, int a, int b) {
// sort arr[a..b]
if (a < b) {
int i = a, j = b;
int x = arr[(i+j) / 2];
do {
while (cmp.Compare(arr[i], x) < 0) i++;
while (cmp.Compare(x, arr[j]) < 0) j--;
if (i <= j) {
swap(arr, i, j);
i++; j--;
}
} while (i <= j);
qsort(arr, cmp, a, j);
qsort(arr, cmp, i, b);
}
}
public static void Quicksort(int[] arr, IIntComparer cmp) {
qsort(arr, cmp, 0, arr.Length-1);
}
}
public class FunStringsort {
private static void swap(string[] arr, int s, int t) {
string tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp;
}
// Monomorphic quicksort with comparer: not general, but typesafe
private static void qsort(string[] arr, IStringComparer cmp, int a, int b) {
// sort arr[a..b]
if (a < b) {
int i = a, j = b;
string x = arr[(i+j) / 2];
do {
while (cmp.Compare(arr[i], x) < 0) i++;
while (cmp.Compare(x, arr[j]) < 0) j--;
if (i <= j) {
swap(arr, i, j);
i++; j--;
}
} while (i <= j);
qsort(arr, cmp, a, j);
qsort(arr, cmp, i, b);
}
}
public static void Quicksort(string[] arr, IStringComparer cmp) {
qsort(arr, cmp, 0, arr.Length-1);
}
}
// Two generic versions of IComparable
public interface IGComparable<T> {
int CompareTo(IGComparable<T> that);
}
public interface IGSelfComparable<T> {
// Actually we could assert a bound on the parameter:
// public interface IGSelfComparable< T : IGSelfComparable<T> >
// but there seems to be no need for that.
// Note that the argument type is T itself, not a superclass:
int CompareTo(T that);
}
// An int wrapper that implements all Comparable interfaces
public class OrderedInt : IComparable,
IGComparable<OrderedInt>,
IGSelfComparable<OrderedInt> {
int i;
public OrderedInt(int i) {
this.i = i;
}
public int Value {
get { return i; }
}
// Implements IComparable.CompareTo(object)
public int CompareTo(object that) {
int thati = ((OrderedInt)that).i;
return i < thati ? -1 : i > thati ? +1 : 0;
}
// Implements IGComparable<OrderedInt>.CompareTo(IGComparable<OrderedInt>)
public int CompareTo(IGComparable<OrderedInt> that) {
int thati = ((OrderedInt)that).i;
return i < thati ? -1 : i > thati ? +1 : 0;
}
// Implements IGSelfComparable<OrderedInt>.CompareTo(T)
// because with T = OrderedInt we have T : IGSelfComparable<T>
public int CompareTo(OrderedInt that) {
// Simple subtraction i-that.i won't do because of possible overflow.
return i < that.i ? -1 : i > that.i ? +1 : 0;
// This following is eight times slower, although the compiler
// and runtime knows that i and that.i are ints:
// return i.CompareTo(that.i);
}
}
// A string wrapper that implements all Comparable interfaces
public class OrderedString : IComparable,
IGComparable<OrderedString>,
IGSelfComparable<OrderedString> {
string s;
public OrderedString(string s) {
this.s = s;
}
public string Value {
get { return s; }
}
// Implements IComparable.CompareTo(object)
public int CompareTo(object that) {
return string.Compare(this.s, ((OrderedString)that).s);
}
// Implements IGComparable<OrderedString>.CompareTo(IGComparable<OrderedString>)
public int CompareTo(IGComparable<OrderedString> that) {
return string.Compare(this.s, ((OrderedString)that).s);
}
// Implements IGSelfComparable<OrderedString>.CompareTo(T)
// because with T = OrderedString we have T : IGSelfComparable<T>
public int CompareTo(OrderedString that) {
return string.Compare(this.s, that.s);
}
}
// A generic version of IComparer
public interface IGComparer<T> {
int Compare(T v1, T v2);
}
public interface IIntComparer {
int Compare(int v1, int v2);
}
public class IntComparer : IGComparer<int>, IIntComparer {
public int Compare(int v1, int v2) {
return v1 < v2 ? -1 : v1 > v2 ? +1 : 0;
}
}
public interface IStringComparer {
int Compare(string v1, string v2);
}
public class StringComparer : IGComparer<string>, IStringComparer {
public int Compare(string v1, string v2) {
return string.Compare(v1, v2);
}
}
// Try it on integers
public class Gsort {
static readonly Random rnd = new Random();
static void Main(string[] args) {
if (args.Length < 1)
Console.Out.WriteLine("Usage: Gsort <arraysize> [string]\n");
else {
int N = int.Parse(args[0]);
const string fmt = "{0,9:0.00}";
if (args.Length < 2 || args[1] != "string") {
Console.Out.WriteLine(" Sorting {0} ints", N);
headers(fmt);
for (int i=0; i<20; i++) {
int[] arr = mkRandomInts(N);
Console.Out.Write(fmt, ObjComparable(arr));
Console.Out.Write(fmt, ObjOrderedInt(arr));
Console.Out.Write(fmt, MonoIntPrimitive(arr));
Console.Out.Write(fmt, MonoIntComparer(arr));
Console.Out.Write(fmt, PolyIGComparable(arr));
Console.Out.Write(fmt, PolyIGSelfComparable(arr));
Console.Out.Write(fmt, PolyIGComparer(arr));
Console.Out.Write(fmt, PolyDGComparer(arr));
Console.Out.WriteLine();
}
} else {
Console.Out.WriteLine(" Sorting {0} strings", N);
headers(fmt);
for (int i=0; i<20; i++) {
string[] arr = mkRandomStrings(N);
Console.Out.Write(fmt, ObjComparable(arr));
Console.Out.Write(fmt, ObjOrderedString(arr));
Console.Out.Write(fmt, MonoStringPrimitive(arr));
Console.Out.Write(fmt, MonoStringComparer(arr));
Console.Out.Write(fmt, PolyIGComparable(arr));
Console.Out.Write(fmt, PolyIGSelfComparable(arr));
Console.Out.Write(fmt, PolyIGComparer(arr));
Console.Out.Write(fmt, PolyDGComparer(arr));
Console.Out.WriteLine();
}
}
}
}
static void headers(string fmt) {
Console.Out.Write(fmt, "general");
Console.Out.Write(fmt, "general");
Console.Out.Write(fmt, "not genl");
Console.Out.Write(fmt, "not genl");
Console.Out.Write(fmt, "general");
Console.Out.Write(fmt, "general");
Console.Out.Write(fmt, "general");
Console.Out.Write(fmt, "general");
Console.Out.WriteLine();
Console.Out.Write(fmt, "not safe");
Console.Out.Write(fmt, "not safe");
Console.Out.Write(fmt, "typesafe");
Console.Out.Write(fmt, "typesafe");
Console.Out.Write(fmt, "not safe");
Console.Out.Write(fmt, "typesafe");
Console.Out.Write(fmt, "typesafe");
Console.Out.Write(fmt, "typesafe");
Console.Out.WriteLine();
Console.Out.Write(fmt, "Comparab");
Console.Out.Write(fmt, "OrderedI");
Console.Out.Write(fmt, "Primitiv");
Console.Out.Write(fmt, "Comparer");
Console.Out.Write(fmt, "GCompara");
Console.Out.Write(fmt, "GSelfCom");
Console.Out.Write(fmt, "IGCompar");
Console.Out.Write(fmt, "DGCompar");
Console.Out.WriteLine();
}
// The standard OO thing to do, given that int : IComparable
static double ObjComparable(int[] arr) {
int n = arr.Length;
// Objsort.Quicksort(arr) would be illegal since int[] cannot be
// converted to IComparable[], even though int : IComparable.
IComparable[] oarr = new IComparable[n];
for (int i=0; i<n; i++)
oarr[i] = arr[i]; // using that int : IComparable
Timer t = new Timer();
Objsort.Quicksort(oarr);
// print(oarr);
return t.Check();
}
// Here we're using our own int wrapper, instead of IComparable (faster)
static double ObjOrderedInt(int[] arr) {
int n = arr.Length;
OrderedInt[] oarr = new OrderedInt[n];
for (int i=0; i<n; i++)
oarr[i] = new OrderedInt(arr[i]);
Timer t = new Timer();
Objsort.Quicksort(oarr);
// print(oarr);
return t.Check();
}
static double MonoIntPrimitive(int[] arr) {
int n = arr.Length;
int[] narr = new int[n];
for (int i=0; i<n; i++)
narr[i] = arr[i];
Timer t = new Timer();
Intsort.Quicksort(narr);
// print(narr);
return t.Check();
}
static double MonoIntComparer(int[] arr) {
int n = arr.Length;
int[] narr = new int[n];
for (int i=0; i<n; i++)
narr[i] = arr[i];
Timer t = new Timer();
FunIntsort.Quicksort(narr, new IntComparer());
// print(narr);
return t.Check();
}
static double PolyIGComparable(int[] arr) {
int n = arr.Length;
OrderedInt[] oarr = new OrderedInt[n];
for (int i=0; i<n; i++)
oarr[i] = new OrderedInt(arr[i]);
Timer t = new Timer();
Polysort.Quicksort<OrderedInt>(oarr);
// print(oarr);
return t.Check();
}
static double PolyIGSelfComparable(int[] arr) {
int n = arr.Length;
OrderedInt[] oarr = new OrderedInt[n];
for (int i=0; i<n; i++)
oarr[i] = new OrderedInt(arr[i]);
Timer t = new Timer();
Polyselfsort.Quicksort<OrderedInt>(oarr);
// print(oarr);
return t.Check();
}
static double PolyIGComparer(int[] arr) {
int n = arr.Length;
int[] narr = new int[n];
for (int i=0; i<n; i++)
narr[i] = arr[i];
Timer t = new Timer();
Polysort.Quicksort<int>(narr, new IntComparer());
// print(narr);
return t.Check();
}
static int intCompare(int v1, int v2) {
return v1 < v2 ? -1 : v1 > v2 ? +1 : 0;
}
static double PolyDGComparer(int[] arr) {
int n = arr.Length;
int[] narr = new int[n];
for (int i=0; i<n; i++)
narr[i] = arr[i];
Timer t = new Timer();
Polysort.Quicksort<int>(narr, new Polysort.DGComparer<int>(intCompare));
// print(narr);
return t.Check();
}
// Eight ways to sort strings
// The standard OO thing to do, given that string : IComparable
static double ObjComparable(string[] arr) {
int n = arr.Length;
// Objsort.Quicksort(arr) would be illegal since string[] cannot be
// converted to IComparable[], even though string : IComparable.
IComparable[] oarr = new IComparable[n];
for (int i=0; i<n; i++)
oarr[i] = arr[i]; // using that string : IComparable
Timer t = new Timer();
Objsort.Quicksort(oarr);
// print(oarr);
return t.Check();
}
// Here we're using our own string wrapper, instead of IComparable (faster)
static double ObjOrderedString(string[] arr) {
int n = arr.Length;
OrderedString[] oarr = new OrderedString[n];
for (int i=0; i<n; i++)
oarr[i] = new OrderedString(arr[i]);
Timer t = new Timer();
Objsort.Quicksort(oarr);
// print(oarr);
return t.Check();
}
static double MonoStringPrimitive(string[] arr) {
int n = arr.Length;
string[] narr = new string[n];
for (int i=0; i<n; i++)
narr[i] = arr[i];
Timer t = new Timer();
Stringsort.Quicksort(narr);
// print(narr);
return t.Check();
}
static double MonoStringComparer(string[] arr) {
int n = arr.Length;
string[] narr = new string[n];
for (int i=0; i<n; i++)
narr[i] = arr[i];
Timer t = new Timer();
FunStringsort.Quicksort(narr, new StringComparer());
// print(narr);
return t.Check();
}
static double PolyIGComparable(string[] arr) {
int n = arr.Length;
OrderedString[] oarr = new OrderedString[n];
for (int i=0; i<n; i++)
oarr[i] = new OrderedString(arr[i]);
Timer t = new Timer();
Polysort.Quicksort<OrderedString>(oarr);
// print(oarr);
return t.Check();
}
static double PolyIGSelfComparable(string[] arr) {
int n = arr.Length;
OrderedString[] oarr = new OrderedString[n];
for (int i=0; i<n; i++)
oarr[i] = new OrderedString(arr[i]);
Timer t = new Timer();
Polyselfsort.Quicksort<OrderedString>(oarr);
// print(oarr);
return t.Check();
}
static double PolyIGComparer(string[] arr) {
int n = arr.Length;
string[] narr = new string[n];
for (int i=0; i<n; i++)
narr[i] = arr[i];
Timer t = new Timer();
Polysort.Quicksort<string>(narr, new StringComparer());
// print(narr);
return t.Check();
}
static double PolyDGComparer(string[] arr) {
int n = arr.Length;
string[] narr = new string[n];
for (int i=0; i<n; i++)
narr[i] = arr[i];
Timer t = new Timer();
// Note that string.Compare plugs right into the delegate:
Polysort.Quicksort<string>(narr, new Polysort.DGComparer<string>(string.Compare));
// print(narr);
return t.Check();
}
// Create arrays of random ints
static int[] mkRandomInts(int n) {
int[] arr = new int[n];
for (int i=0; i<n; i++)
arr[i] = rnd.Next(100000000);
return arr;
}
// Create arrays of random strings
static string[] mkRandomStrings(int n) {
string[] arr = new string[n];
for (int i=0; i<n; i++)
arr[i] = mkRandomString(5 + rnd.Next(15));
return arr;
}
static string mkRandomString(int n) {
System.Text.StringBuilder sb = new System.Text.StringBuilder();
for (int i=0; i<n; i++)
sb.Append((char)(65 + rnd.Next(26) + 32 * rnd.Next(2)));
return sb.ToString();
}
static void print(int[] arr) {
for (int i=0; i<arr.Length; i++)
Console.Write("{0} ", arr[i]);
Console.WriteLine();
}
static void print(IComparable[] arr) {
for (int i=0; i<arr.Length; i++)
Console.Write("{0} ", (int)arr[i]);
Console.WriteLine();
}
static void print(OrderedInt[] arr) {
for (int i=0; i<arr.Length; i++)
Console.Write("{0} ", arr[i].Value);
Console.WriteLine();
}
}
public class Timer {
private DateTime start;
public Timer() {
start = DateTime.Now;
}
public double Check() {
TimeSpan dur = DateTime.Now - start;
return dur.TotalSeconds;
}
}
More information about the Mono-devel-list
mailing list