Measuring relational inheritance distance between types
Does anyone know how I could (or if there is an existing algorithm) measure the relational distance between two .NET types?
By this I mean the number of "steps" in the hierarchical tree it takes to go from object A to object B.
For example, if object A is a Button and object B is a LinkButton, there will be two steps, Button -> WebControl -> LinkButton. Should I create my own static inheritance tree and use a pathfinding algorithm, or is there a way I can dynamically look at the .NET inheritance framework to calculate the distance between two objects?
source to share
Not a generic path (also you don't need to explicitly specify the parent / child language):
private static int CalulateDistanceOneWay(Type firstType, Type secondType)
{
var chain = new List<Type>();
while (firstType != typeof(object))
{
chain.Add(firstType);
firstType = firstType.BaseType;
}
return chain.IndexOf(secondType);
}
// returns -1 for invalid input, distance between types otherwise
public static int CalculateDistance(Type firstType, Type secondType)
{
int result = CalulateDistanceOneWay(firstType, secondType);
if (result >= 0)
{
return result;
}
return CalulateDistanceOneWay(secondType, firstType);
}
EDIT: Update for calculating cousins:
public class DistanceResult
{
public Type SharedAncestor { get; private set; }
public int FirstTypeDistance { get; private set; }
public int SecondTypeDistance { get; private set; }
public DistanceResult(Type sharedAncestor, int firstTypeDistance, int secondTypeDistance)
{
SharedAncestor = sharedAncestor;
FirstTypeDistance = firstTypeDistance;
SecondTypeDistance = secondTypeDistance;
}
}
static DistanceResult CalculateDistance(Type firstType, Type secondType)
{
var firstChain = new List<Type>();
while (firstType != typeof(object))
{
firstChain.Add(firstType);
firstType = firstType.BaseType;
}
firstChain.Add(typeof(object));
var secondChain = new List<Type>();
while(secondType != typeof(object))
{
secondChain.Add(secondType);
secondType = secondType.BaseType;
}
secondChain.Add(typeof(object));
for(var i = 0; i < secondChain.Count; i++)
{
var type = secondChain[i];
int index = firstChain.IndexOf(type);
if (index >= 0)
{
return new DistanceResult(firstChain[index], index, i);
}
}
return null;
}
source to share
You can walk through the inheritance path with Type.BaseType
. For example:
public static int GetTypeDistance<T, B>(T t, B baseType)
{
if (t is B) // checking if t inherits baseType
{
int distance = 0;
Type curType = t.GetType();
while (curType != typeof(B) && curType != null)
{
distance++;
curType = curType.BaseType;
}
return distance;
}
else { throw new Exception("..."); }
}
source to share
Based on the answers from Ondrej and Bényi, there are two extension methods for calculating the distance from a particular type to its (indirect) base class type, or one of its implemented interfaces, or one of its base classes.
Examples of using:
Assert.AreEqual( 4, typeof( MultiDictionary<int, int> ).DistanceTo<IEnumerable>() );
Assert.AreEqual( 4, typeof( MultiDictionary<int, int> ).DistanceTo( typeof( IEnumerable ) );
Assert.AreEqual( 2, typeof( StringReader ).DistanceTo( typeof( IDisposable ) ) );
Extension methods:
public static class ExtensionsForType
{
public static int DistanceTo( [CanBeNull] this Type current, [NotNull] Type target )
{
Contract.Requires<ArgumentNullException>( target != null );
// `root` will point to the topmost type which is implementing
// our `target` interface
Type root = current;
// search for topmost base type implementing `target` interface type
// or for the `target` base class type itself
int distance = 0;
while ( current != null && ( target.IsInterface
? current.GetInterfaces().Contains( target )
: current != target ) )
{
root = current;
current = current.BaseType;
distance++;
}
// probably the `current` type does not even derive from / implement
// the target type at all
if ( current == null ) return -1;
// if it not an interface then we've found it in one of the base classes
if ( !target.IsInterface ) return distance;
// go one step back, because 'current' does not implement
// our target interface anymore
distance--;
// iterate interface "derivations" while the target interface is still
// in the list of implemented interfaces
Type[] interfaces = root.GetInterfaces();
while ( interfaces.Contains( target ) )
{
interfaces = interfaces.SelectMany( i => i.GetInterfaces() ).ToArray();
distance++;
}
return distance;
}
public static int DistanceTo<T>( [CanBeNull] this Type current )
{
return current.DistanceTo( typeof( T ) );
}
}
source to share