我有一些实体集合,需要根据它们之间的依赖关系进行排序。这是一个例子,因为它很难解释:
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 {}
问题是我需要将数据导入到这些类型的集合中,但我需要按一定的顺序导入,因为如果我先导入
A
对象,我将无法链接相应的 B
,因为它不会'还不存在。
所以我想要的是以正确的顺序导入所有依赖项的方式对我的集合进行排序(没有循环依赖项)。但我无法找出可以做到这一点的 linq 语句。
lists.OrderBy(l => l. ??? );
我在想也许可以得到
typesList
中 T
的所有类型 List<T>
的列表 lists
并以某种方式使用反射来计算 T
中有多少个字段在 typesList
中,但这似乎..效率低下?
编辑:意识到我的结构的措辞有点模糊。
基本上
lists
是 List<List<I>>
。这是结果示例:
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.
我知道的最简单的方法是建立一个新的集合,当你建立它时,看看你是否在类中看到任何已知的类型。如果您确实看到已知类型,请将其放在第一次看到之前;如果未找到已知类型,则将其放在最后。一旦你有了这个集合,只需以相反的顺序枚举该集合,它就会以相反的依赖顺序排列项目。
下面的示例使用方式如下
var sortedLists = lists.OrderByTypeDependency();
如何实现LINQ风格的扩展方法:
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;
}
}
}
编辑:不清楚您是否传入类型列表或对象列表。如果您传递类型列表,则只需对代码进行一些小调整,只需删除两个
.GetType()
调用并从泛型切换为仅接受 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;
}
}
}
更新:
根据您对问题的更新,只要内部列表在列表中保存相同类型的对象,我们就可以检查列表中的第一项以查找它的类型,对原始代码的修改将完成您需要的排序.
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;
}
}
}
斯科特的回答很棒并且很有帮助。我刚刚制作了一个更通用的解决方案,它可以(希望)用于应按依赖关系排序的任何类型的项目。这是扩展方法的代码:
public static class EnumerableDependencyExtensions
{
public static IEnumerable<T> OrderByDependency<T, TDependency>(
this IEnumerable<T> source,
Func<T, TDependency> dependentSelector,
Func<T, IReadOnlyList<TDependency>> dependenciesSelector)
{
return source.OrderByDependency(
dependentSelector,
dependenciesSelector,
EqualityComparer<TDependency>.Default,
false);
}
public static IEnumerable<T> OrderByDependency<T, TDependency>(
this IEnumerable<T> source,
Func<T, TDependency> dependentSelector,
Func<T, IReadOnlyList<TDependency>> dependenciesSelector,
bool verifyCircularDependency)
{
return source.OrderByDependency(
dependentSelector,
dependenciesSelector,
EqualityComparer<TDependency>.Default,
verifyCircularDependency);
}
public static IEnumerable<T> OrderByDependency<T, TDependency>(
this IEnumerable<T> source,
Func<T, TDependency> dependentSelector,
Func<T, IReadOnlyList<TDependency>> dependenciesSelector,
IEqualityComparer<TDependency> dependencyComparer)
{
return source.OrderByDependency(
dependentSelector,
dependenciesSelector,
dependencyComparer,
false);
}
public static IEnumerable<T> OrderByDependency<T, TDependency>(
this IEnumerable<T> source,
Func<T, TDependency> dependentSelector,
Func<T, IReadOnlyList<TDependency>> dependenciesSelector,
bool verifyCircularDependency,
IEqualityComparer<TDependency> dependencyComparer)
{
return source.OrderByDependency(
dependentSelector,
dependenciesSelector,
dependencyComparer,
verifyCircularDependency);
}
public static IEnumerable<T> OrderByDependency<T, TDependency>(
this IEnumerable<T> source,
Func<T, TDependency> dependentSelector,
Func<T, IReadOnlyList<TDependency>> dependenciesSelector,
IEqualityComparer<TDependency> dependencyComparer,
bool verifyCircularDependency)
{
var ordering = new LinkedList<(T item, TDependency dependent)>();
foreach (var item in source)
{
var dependent = dependentSelector(item);
var dependencies = dependenciesSelector(item);
var found = false;
for (var node = ordering.First; node != null; node = node.Next)
{
var foundDependency = dependencies
.FirstOrDefault(dep => dependencyComparer.Equals(dep, node.Value.dependent));
if (foundDependency is not null)
{
if (verifyCircularDependency)
{
var circleFound = ordering.FirstOrDefault(node
=> dependenciesSelector(node.item).Any(dep
=> dependencyComparer.Equals(dependent, dep)));
if (circleFound.item is not null)
throw new InvalidOperationException(
$"Circular dependency detected between {item} and {circleFound.item}");
}
ordering.AddBefore(node, (item, dependent));
found = true;
break;
}
}
if (!found)
{
ordering.AddLast((item, dependent));
}
}
for (var node = ordering.Last; node != null; node = node.Previous)
{
yield return node.Value.item;
}
}
}
这是一个使用示例:
public class DependencyOrderingTests
{
[Fact]
public void OrdersElementsByDependency()
{
var items = new[]
{
new SomethingWithDependencies { Name = "A", Dependencies = new[] { "B", "C" } },
new SomethingWithDependencies { Name = "B", Dependencies = new[] { "C" } },
new SomethingWithDependencies { Name = "C", Dependencies = Array.Empty<string>() },
};
var ordered = items
.OrderByDependency(
x => x.Name,
x => x.Dependencies,
false)
.ToList();
ordered[0].Name.ShouldBe("C");
ordered[1].Name.ShouldBe("B");
ordered[2].Name.ShouldBe("A");
}
[Fact]
public void DetectsCircularDependencies()
{
var items = new[]
{
new SomethingWithDependencies { Name = "A", Dependencies = new[] { "B" } },
new SomethingWithDependencies { Name = "B", Dependencies = new[] { "C" } },
new SomethingWithDependencies { Name = "C", Dependencies = new[] { "A" } },
};
Should.Throw<InvalidOperationException>(() => items
.OrderByDependency(
x => x.Name,
x => x.Dependencies,
true)
.ToList());
}
internal class SomethingWithDependencies
{
public required string Name { get; set; }
public required IReadOnlyList<string> Dependencies { get; set; }
public override string ToString()
{
return $"{Name} -> {string.Join(", ", Dependencies)}";
}
}
}