3 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
\r
4 Permission is hereby granted, free of charge, to any person obtaining a copy
\r
5 of this software and associated documentation files (the "Software"), to deal
\r
6 in the Software without restriction, including without limitation the rights
\r
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
\r
8 copies of the Software, and to permit persons to whom the Software is
\r
9 furnished to do so, subject to the following conditions:
\r
11 The above copyright notice and this permission notice shall be included in
\r
12 all copies or substantial portions of the Software.
\r
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
\r
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
\r
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
\r
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
\r
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
\r
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
\r
25 using System.Reflection;
\r
26 using System.Reflection.Emit;
\r
27 using System.Diagnostics;
\r
28 using SCG = System.Collections.Generic;
\r
33 /// Utility class for building default generic equalityComparers.
\r
35 /// <typeparam name="T"></typeparam>
\r
36 public static class EqualityComparer<T>
\r
38 readonly static Type isequenced = typeof(ISequenced<>);
\r
40 readonly static Type icollection = typeof(ICollection<>);
\r
42 readonly static Type orderedcollectionequalityComparer = typeof(SequencedCollectionEqualityComparer<,>);
\r
44 readonly static Type unorderedcollectionequalityComparer = typeof(UnsequencedCollectionEqualityComparer<,>);
\r
46 readonly static Type equalityequalityComparer = typeof(EquatableEqualityComparer<>);
\r
48 readonly static Type iequalitytype = typeof(IEquatable<T>);
\r
50 static SCG.IEqualityComparer<T> cachedDefault = null;
\r
52 //TODO: find the right word for initialized+invocation
\r
54 /// A default generic equalityComparer for type T. The procedure is as follows:
\r
56 /// <item>If T is int, double, byte or char,
\r
57 /// the equalityComparer will be a standard equalityComparer for that type</item>
\r
58 /// <item>If the actual generic argument T implements the generic interface
\r
59 /// <see cref="T:C5.ISequenced`1"/> for some value W of its generic parameter T,
\r
60 /// the equalityComparer will be <see cref="T:C5.SequencedCollectionEqualityComparer`2"/></item>
\r
61 /// <item>If the actual generic argument T implements
\r
62 /// <see cref="T:C5.ICollectionValue`1"/> for some value W of its generic parameter T,
\r
63 /// the equalityComparer will be <see cref="T:C5.UnsequencedCollectionEqualityComparer`2"/></item>
\r
64 /// <item>If T is a type implementing <see cref="T:C5.IEquatable`1"/>, the equalityComparer
\r
65 /// will be <see cref="T:C5.EquatableEqualityComparer`1"/></item>
\r
66 /// <item>If T is a type not implementing <see cref="T:C5.IEquatable`1"/>, the equalityComparer
\r
67 /// will be <see cref="T:C5.NaturalEqualityComparer`1"/> </item>
\r
69 /// The <see cref="T:C5.IEqualityComparer`1"/> object is constructed when this class is initialised, i.e.
\r
70 /// its static constructors called. Thus, the property will be the same object
\r
71 /// for the duration of an invocation of the runtime, but a value serialized in
\r
72 /// another invocation and deserialized here will not be the same object.
\r
75 public static SCG.IEqualityComparer<T> Default
\r
79 if (cachedDefault != null)
\r
80 return cachedDefault;
\r
86 if (t.Equals(typeof(int)))
\r
87 return cachedDefault = (SCG.IEqualityComparer<T>)(IntEqualityComparer.Default);
\r
88 else if (t.Equals(typeof(double)))
\r
89 return cachedDefault = (SCG.IEqualityComparer<T>)(DoubleEqualityComparer.Default);
\r
90 else if (t.Equals(typeof(byte)))
\r
91 return cachedDefault = (SCG.IEqualityComparer<T>)(ByteEqualityComparer.Default);
\r
92 else if (t.Equals(typeof(char)))
\r
93 return cachedDefault = (SCG.IEqualityComparer<T>)(CharEqualityComparer.Default);
\r
95 Type[] interfaces = t.GetInterfaces();
\r
96 if (t.IsGenericType && t.GetGenericTypeDefinition().Equals(isequenced))
\r
97 return createAndCache(orderedcollectionequalityComparer.MakeGenericType(new Type[] { t, t.GetGenericArguments()[0] }));
\r
98 foreach (Type ty in interfaces)
\r
100 if (ty.IsGenericType && ty.GetGenericTypeDefinition().Equals(isequenced))
\r
101 return createAndCache(orderedcollectionequalityComparer.MakeGenericType(new Type[] { t, ty.GetGenericArguments()[0] }));
\r
103 if (t.IsGenericType && t.GetGenericTypeDefinition().Equals(icollection))
\r
104 return createAndCache(unorderedcollectionequalityComparer.MakeGenericType(new Type[] { t, t.GetGenericArguments()[0] }));
\r
105 foreach (Type ty in interfaces)
\r
107 if (ty.IsGenericType && ty.GetGenericTypeDefinition().Equals(icollection))
\r
108 return createAndCache(unorderedcollectionequalityComparer.MakeGenericType(new Type[] { t, ty.GetGenericArguments()[0] }));
\r
110 if (iequalitytype.IsAssignableFrom(t))
\r
111 return createAndCache(equalityequalityComparer.MakeGenericType(new Type[] { t }));
\r
113 return cachedDefault = NaturalEqualityComparer<T>.Default;
\r
116 static SCG.IEqualityComparer<T> createAndCache(Type equalityComparertype)
\r
118 return cachedDefault = (SCG.IEqualityComparer<T>)(equalityComparertype.GetProperty("Default", BindingFlags.Static | BindingFlags.Public).GetValue(null, null));
\r
123 /// A default item equalityComparer calling through to
\r
124 /// the GetHashCode and Equals methods inherited from System.Object.
\r
126 public sealed class NaturalEqualityComparer<T> : SCG.IEqualityComparer<T>
\r
128 static NaturalEqualityComparer<T> cached;
\r
129 NaturalEqualityComparer() { }
\r
133 /// <value></value>
\r
134 public static NaturalEqualityComparer<T> Default { get { return cached ?? (cached = new NaturalEqualityComparer<T>()); } }
\r
135 //TODO: check if null check is reasonable
\r
136 //Answer: if we have struct C<T> { T t; int i;} and implement GetHashCode as
\r
137 //the sum of hashcodes, and T may be any type, we cannot make the null check
\r
138 //inside the definition of C<T> in a reasonable way.
\r
140 /// Get the hash code with respect to this item equalityComparer
\r
142 /// <param name="item">The item</param>
\r
143 /// <returns>The hash code</returns>
\r
145 public int GetHashCode(T item) { return item == null ? 0 : item.GetHashCode(); }
\r
149 /// Check if two items are equal with respect to this item equalityComparer
\r
151 /// <param name="item1">first item</param>
\r
152 /// <param name="item2">second item</param>
\r
153 /// <returns>True if equal</returns>
\r
155 public bool Equals(T item1, T item2)
\r
157 return item1 == null ? item2 == null : item1.Equals(item2);
\r
162 /// A default equalityComparer for a type, T, implementing <see cref="T:C5.IEquatable`1"/>.
\r
164 /// The equalityComparer forwards calls to GetHashCode and Equals to the methods
\r
165 /// on T. The point is that it is Equals(T) and not Equals(object)
\r
166 /// that is called. This will save a boxing/unboxing pair if T is a value type
\r
167 /// and in general a runtime type check.
\r
169 /// <typeparam name="T"></typeparam>
\r
170 public class EquatableEqualityComparer<T> : SCG.IEqualityComparer<T> where T : IEquatable<T>
\r
172 static EquatableEqualityComparer<T> cached = new EquatableEqualityComparer<T>();
\r
173 EquatableEqualityComparer() { }
\r
177 /// <value></value>
\r
178 public static EquatableEqualityComparer<T> Default { get { return cached ?? (cached = new EquatableEqualityComparer<T>()); } }
\r
182 /// <param name="item"></param>
\r
183 /// <returns></returns>
\r
184 public int GetHashCode(T item) { return item == null ? 0 : item.GetHashCode(); }
\r
189 /// <param name="item1"></param>
\r
190 /// <param name="item2"></param>
\r
191 /// <returns></returns>
\r
192 public bool Equals(T item1, T item2) { return item1 == null ? item2 == null : item1.Equals(item2); }
\r
196 /// A equalityComparer for a reference type that uses reference equality for equality and the hash code from object as hash code.
\r
198 /// <typeparam name="T">The item type. Must be a reference type.</typeparam>
\r
199 public class ReferenceEqualityComparer<T> : SCG.IEqualityComparer<T> where T : class
\r
201 static ReferenceEqualityComparer<T> cached;
\r
202 ReferenceEqualityComparer() { }
\r
206 /// <value></value>
\r
207 public static ReferenceEqualityComparer<T> Default { get { return cached ?? (cached = new ReferenceEqualityComparer<T>()); } }
\r
211 /// <param name="item"></param>
\r
212 /// <returns></returns>
\r
213 public int GetHashCode(T item)
\r
215 return System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(item);
\r
221 /// <param name="i1"></param>
\r
222 /// <param name="i2"></param>
\r
223 /// <returns></returns>
\r
224 public bool Equals(T i1, T i2)
\r
226 return object.ReferenceEquals(i1, i2);
\r
231 /// An equalityComparer compatible with a given comparer. All hash codes are 0,
\r
232 /// meaning that anything based on hash codes will be quite inefficient.
\r
233 /// <para><b>Note: this will give a new EqualityComparer each time created!</b></para>
\r
235 /// <typeparam name="T"></typeparam>
\r
236 public class ComparerZeroHashCodeEqualityComparer<T> : SCG.IEqualityComparer<T>
\r
238 SCG.IComparer<T> comparer;
\r
240 /// Create a trivial <see cref="T:C5.IEqualityComparer`1"/> compatible with the
\r
241 /// <see cref="T:C5.IComparer`1"/> <code>comparer</code>
\r
243 /// <param name="comparer"></param>
\r
244 public ComparerZeroHashCodeEqualityComparer(SCG.IComparer<T> comparer)
\r
246 if (comparer == null)
\r
247 throw new NullReferenceException("Compaer cannot be null");
\r
248 this.comparer = comparer;
\r
251 /// A trivial, inefficient hash fuction. Compatible with any equality relation.
\r
253 /// <param name="item"></param>
\r
254 /// <returns>0</returns>
\r
255 public int GetHashCode(T item) { return 0; }
\r
257 /// Equality of two items as defined by the comparer.
\r
259 /// <param name="item1"></param>
\r
260 /// <param name="item2"></param>
\r
261 /// <returns></returns>
\r
262 public bool Equals(T item1, T item2) { return comparer.Compare(item1, item2) == 0; }
\r
266 /// Prototype for an sequenced equalityComparer for something (T) that implements ISequenced[W]
\r
267 /// This will use ISequenced[W] specific implementations of the equalityComparer operations
\r
269 /// <typeparam name="T"></typeparam>
\r
270 /// <typeparam name="W"></typeparam>
\r
271 public class SequencedCollectionEqualityComparer<T, W> : SCG.IEqualityComparer<T>
\r
272 where T : ISequenced<W>
\r
274 static SequencedCollectionEqualityComparer<T, W> cached;
\r
275 SequencedCollectionEqualityComparer() { }
\r
279 /// <value></value>
\r
280 public static SequencedCollectionEqualityComparer<T, W> Default { get { return cached ?? (cached = new SequencedCollectionEqualityComparer<T, W>()); } }
\r
282 /// Get the hash code with respect to this sequenced equalityComparer
\r
284 /// <param name="collection">The collection</param>
\r
285 /// <returns>The hash code</returns>
\r
287 public int GetHashCode(T collection) { return collection.GetSequencedHashCode(); }
\r
291 /// Check if two items are equal with respect to this sequenced equalityComparer
\r
293 /// <param name="collection1">first collection</param>
\r
294 /// <param name="collection2">second collection</param>
\r
295 /// <returns>True if equal</returns>
\r
297 public bool Equals(T collection1, T collection2) { return collection1 == null ? collection2 == null : collection1.SequencedEquals(collection2); }
\r
301 /// Prototype for an unsequenced equalityComparer for something (T) that implements ICollection[W]
\r
302 /// This will use ICollection[W] specific implementations of the equalityComparer operations
\r
304 /// <typeparam name="T"></typeparam>
\r
305 /// <typeparam name="W"></typeparam>
\r
306 public class UnsequencedCollectionEqualityComparer<T, W> : SCG.IEqualityComparer<T>
\r
307 where T : ICollection<W>
\r
309 static UnsequencedCollectionEqualityComparer<T, W> cached;
\r
310 UnsequencedCollectionEqualityComparer() { }
\r
314 /// <value></value>
\r
315 public static UnsequencedCollectionEqualityComparer<T, W> Default { get { return cached ?? (cached = new UnsequencedCollectionEqualityComparer<T, W>()); } }
\r
317 /// Get the hash code with respect to this unsequenced equalityComparer
\r
319 /// <param name="collection">The collection</param>
\r
320 /// <returns>The hash code</returns>
\r
322 public int GetHashCode(T collection) { return collection.GetUnsequencedHashCode(); }
\r
326 /// Check if two collections are equal with respect to this unsequenced equalityComparer
\r
328 /// <param name="collection1">first collection</param>
\r
329 /// <param name="collection2">second collection</param>
\r
330 /// <returns>True if equal</returns>
\r
332 public bool Equals(T collection1, T collection2) { return collection1 == null ? collection2 == null : collection1.UnsequencedEquals(collection2); }
\r
342 namespace C5.EqualityComparerBuilder
\r
346 /// IEqualityComparer factory class: examines at instatiation time if T is an
\r
347 /// interface implementing "int GetHashCode()" and "bool Equals(T)".
\r
348 /// If those are not present, MakeEqualityComparer will return a default equalityComparer,
\r
349 /// else this class will implement IequalityComparer[T] via Invoke() on the
\r
350 /// reflected method infos.
\r
352 public class ByInvoke<T> : SCG.IEqualityComparer<T>
\r
354 internal static readonly System.Reflection.MethodInfo hinfo, einfo;
\r
359 Type t = typeof(T);
\r
361 if (!t.IsInterface) return;
\r
363 BindingFlags f = BindingFlags.Public | BindingFlags.Instance;
\r
365 hinfo = t.GetMethod("GetHashCode", f, null, new Type[0], null);
\r
366 einfo = t.GetMethod("Equals", f, null, new Type[1] { t }, null);
\r
370 private ByInvoke() { }
\r
375 /// <returns></returns>
\r
376 public static SCG.IEqualityComparer<T> MakeEqualityComparer()
\r
378 if (hinfo != null && einfo != null)
\r
379 return new ByInvoke<T>();
\r
381 return NaturalEqualityComparer<T>.Default;
\r
387 /// <param name="item"></param>
\r
388 /// <returns></returns>
\r
389 public int GetHashCode(T item)
\r
391 return (int)(hinfo.Invoke(item, null));
\r
397 /// <param name="i1"></param>
\r
398 /// <param name="i2"></param>
\r
399 /// <returns></returns>
\r
400 public bool Equals(T i1, T i2)
\r
402 return (bool)(einfo.Invoke(i1, new object[1] { i2 }));
\r
409 /// Like ByInvoke, but tries to build a equalityComparer by RTCG to
\r
410 /// avoid the Invoke() overhead.
\r
412 public class ByRTCG
\r
414 private static ModuleBuilder moduleBuilder;
\r
416 private static AssemblyBuilder assemblyBuilder;
\r
421 /// <param name="hinfo"></param>
\r
422 /// <param name="einfo"></param>
\r
423 /// <returns></returns>
\r
424 public static SCG.IEqualityComparer<T> CreateEqualityComparer<T>(MethodInfo hinfo, MethodInfo einfo)
\r
426 if (moduleBuilder == null)
\r
428 string assmname = "LeFake";
\r
429 string filename = assmname + ".dll";
\r
430 AssemblyName assemblyName = new AssemblyName("LeFake");
\r
431 AppDomain appdomain = AppDomain.CurrentDomain;
\r
432 AssemblyBuilderAccess acc = AssemblyBuilderAccess.RunAndSave;
\r
434 assemblyBuilder = appdomain.DefineDynamicAssembly(assemblyName, acc);
\r
435 moduleBuilder = assemblyBuilder.DefineDynamicModule(assmname, filename);
\r
438 Type t = typeof(T);
\r
439 Type o_t = typeof(object);
\r
440 Type h_t = typeof(SCG.IEqualityComparer<T>);
\r
441 Type i_t = typeof(int);
\r
442 //TODO: protect uid for thread safety!
\r
443 string name = "C5.Dynamic.EqualityComparer_" + Guid.NewGuid().ToString();
\r
444 TypeAttributes tatt = TypeAttributes.Class | TypeAttributes.Public | TypeAttributes.Sealed;
\r
445 TypeBuilder tb = moduleBuilder.DefineType(name, tatt, o_t, new Type[1] { h_t });
\r
446 MethodAttributes matt = MethodAttributes.Public | MethodAttributes.Virtual;
\r
447 MethodBuilder mb = tb.DefineMethod("GetHashCode", matt, i_t, new Type[1] { t });
\r
448 ILGenerator ilg = mb.GetILGenerator();
\r
450 ilg.Emit(OpCodes.Ldarg_1);
\r
451 ilg.Emit(OpCodes.Callvirt, hinfo);
\r
452 ilg.Emit(OpCodes.Ret);
\r
453 mb = tb.DefineMethod("Equals", matt, typeof(bool), new Type[2] { t, t });
\r
454 ilg = mb.GetILGenerator();
\r
455 ilg.Emit(OpCodes.Ldarg_1);
\r
456 ilg.Emit(OpCodes.Ldarg_2);
\r
457 ilg.Emit(OpCodes.Callvirt, einfo);
\r
458 ilg.Emit(OpCodes.Ret);
\r
460 Type equalityComparer_t = tb.CreateType();
\r
461 object equalityComparer = equalityComparer_t.GetConstructor(new Type[0]).Invoke(null);
\r
463 return (SCG.IEqualityComparer<T>)equalityComparer;
\r
469 /// <typeparam name="T"></typeparam>
\r
470 /// <returns></returns>
\r
471 public static SCG.IEqualityComparer<T> build<T>()
\r
473 MethodInfo hinfo = ByInvoke<T>.hinfo, einfo = ByInvoke<T>.einfo;
\r
475 if (hinfo != null && einfo != null)
\r
476 return CreateEqualityComparer<T>(hinfo, einfo);
\r
478 return EqualityComparer<T>.Default;
\r
486 assemblyBuilder.Save("LeFake.dll");
\r