Question: Linq OrderBy dependencies on other entities

Question

Linq OrderBy dependencies on other entities

Answers 1
Added at 2017-01-01 23:01
Tags
Question

I have collections of entities that I need to sort depending on their dependencies to each other. Here's an example because it's fairly tough to explain:

public class A : I {
    private B objB;
    public B propB { get{ return objB; } }
    // Some other fields and properties.
}

public class B : I { /* Some fields and properties. */ }

public class C : I {
    private A objA;
    public A propA { get{ return objA; } }
    // Some other fields and properties.
}

public interface I {}

The thing is that I need to import data into collections of those types but I need to import in a certain order because if I import A objects first, I will not be able to link the corresponding B since it won't exist yet.

So what I'd like is to sort my collections in a way that all dependencies are imported in the right order (There are no circular dependencies). I can't figure out a linq statement that will do that though.

lists.OrderBy(l => l. ??? );

I was thinking maybe get a list typesList of all the types T of the List<T> in lists and somehow use reflection to count how many fields in T are in typesList but that seems... inefficient ?


EDIT: Realized the wording of my structure is a bit vague.
Basically lists is a List<List<I>>. Here's a results example:

List<List<I>> collections before:
    -List<A>
    -List<C>
    -List<B>

List<List<I>> collections after:
    -List<B>  // B has 0 dependency to B or C.
    -List<A>  // A has 1 dependency to B.
    -List<C>  // C has 1 dependency to A.
Answers to

Linq OrderBy dependencies on other entities

nr: #1 dodano: 2017-01-02 00:01

The easiest way I know to do it is build up a new collection, as you build it up see if you see any known types in the class. If you do see a known type put it it just before the first sighting or put it at the end if no known types were found. Once you have that collection just enumerate the collection in reverse order and it will the items in reverse dependency order.

The below example is used like

var sortedLists = lists.OrderByTypeDependency();

How to implement the LINQ style extension method:

static class ExtensionMethods
{
    public static IEnumerable<T> OrderByTypeDependency<T>(this IEnumerable<T> items)
    {
        LinkedList<T> knownItems = new LinkedList<T>();

        foreach (var item in items)
        {
            var itemType = item.GetType();
            var itemPropertyTypes =
                itemType.GetProperties(BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance)
                    .Select(x => x.PropertyType);
            var itemFieldTypes =
                itemType.GetFields(BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance)
                    .Select(x => x.FieldType);

            //Create a set of all types internal to type we are checking on.
            HashSet<Type> itemChildTypes = new HashSet<Type>(itemPropertyTypes.Concat(itemFieldTypes));

            bool found = false;
            for (var knownItemNode = knownItems.First; knownItemNode != null; knownItemNode = knownItemNode.Next)
            {
                var knownItemType = knownItemNode.Value.GetType();
                if (itemType == knownItemType || itemChildTypes.Contains(knownItemType))
                {
                    knownItems.AddBefore(knownItemNode, item);
                    found = true;
                    break;
                }
            }
            if (!found)
            {
                knownItems.AddLast(item);
            }
        }

        //output the result in reverse order.
        for (var knownItemNode = knownItems.Last; knownItemNode != null; knownItemNode = knownItemNode.Previous)
        {
            yield return knownItemNode.Value;
        }
    }
}

EDIT: it was not clear if you where passing in a list of types or a list of objects. If you are passing in a list of types it is only a few small tweaks to the code, just drop the two .GetType() calls and switch from generics to only accepting IEnumerable<Type>

static class ExtensionMethods
{
    public static IEnumerable<Type> OrderByTypeDependency(this IEnumerable<Type> items)
    {
        LinkedList<Type> knownItems = new LinkedList<Type>();

        foreach (var item in items)
        {
            var itemType = item;
            var itemPropertyTypes =
                itemType.GetProperties(BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance)
                    .Select(x => x.PropertyType);
            var itemFieldTypes =
                itemType.GetFields(BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance)
                    .Select(x => x.FieldType);

            //Create a set of all types internal to type we are checking on.
            HashSet<Type> itemChildTypes = new HashSet<Type>(itemPropertyTypes.Concat(itemFieldTypes));

            bool found = false;
            for (var knownItemNode = knownItems.First; knownItemNode != null; knownItemNode = knownItemNode.Next)
            {
                var knownItemType = knownItemNode.Value;
                if (itemType == knownItemType || itemChildTypes.Contains(knownItemType))
                {
                    knownItems.AddBefore(knownItemNode, item);
                    found = true;
                    break;
                }
            }
            if (!found)
            {
                knownItems.AddLast(item);
            }
        }
        for (var knownItemNode = knownItems.Last; knownItemNode != null; knownItemNode = knownItemNode.Previous)
        {
            yield return knownItemNode.Value;
        }
    }
}

UPDATE:

Per your update to the question, as long as the inner lists hold the same type of object in the list so we can just check the first item in the list to find it's type this modification of the original code will do the sorting you need.

static class ExtensionMethods
{
    public static IEnumerable<T> OrderByTypeDependency<T>(this IEnumerable<T> outerList)
        where T: IList
    {
        LinkedList<T> knownItems = new LinkedList<T>();

        foreach (var innerList in outerList)
        {
            if(innerList.Count == 0)
                continue;
            var itemType = innerList[0].GetType();
            var itemPropertyTypes = itemType.GetProperties(BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance)
                    .Select(x => x.PropertyType);
            var itemFieldTypes = itemType.GetFields(BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance)
                    .Select(x => x.FieldType);

            //Create a set of all types internal to type we are checking on.
            HashSet<Type> itemChildTypes = new HashSet<Type>(itemPropertyTypes.Concat(itemFieldTypes));

            bool found = false;
            for (var knownItemNode = knownItems.First; knownItemNode != null; knownItemNode = knownItemNode.Next)
            {
                var knownItemType = knownItemNode.Value[0].GetType();
                if (itemType == knownItemType || itemChildTypes.Contains(knownItemType))
                {
                    knownItems.AddBefore(knownItemNode, innerList);
                    found = true;
                    break;
                }
            }
            if (!found)
            {
                knownItems.AddLast(innerList);
            }
        }
        for (var knownItemNode = knownItems.Last; knownItemNode != null; knownItemNode = knownItemNode.Previous)
        {
            yield return knownItemNode.Value;
        }
    }
}
Source Show
◀ Wstecz