Работа с иерархиями на .NET. Домашняя страничка Андрея Скляревского.

Работа с иерархиями на .NET

Для решения некоторых задач иногда возникает необходимость в работе с иерархиями, т.е. с объектами, каждый из которых содержит список дочерних объектов такого же типа. Операции с такими структурами затруднены тем, что они не являются плоскими коллекциями, что делает невозможным поиск по иерархиям, фильтрацию и сортировку стандартными средствами .NET (могу ошибаться, но сколько не искал, не нашёл). Одна из возможных реализаций инструментов для работы с иерархиями приведена далее.

Определим иерархию следующим образом:

public interface IHierarchy<T> where T : IHierarchy<T> {
	List<T> Children { get; }
}

Приведённый ниже код упрощает работу с иерархиями, предлагая решение следующих задач:

  1. Выстраивание всей иерархии в ряд, что может быть нужно для:
    • поиска элемента по критерию среди всей иерархии;
    • подсчёта количества всех элементов;
    • выполнения действий на всех элементах;
  2. Перебор иерархии с вызовом для каждого элемента установленного делегата, принимающего два параметра -- parent и child, что позволяет с лёгкостью фильтровать иерархию;

public static class HierarchyExtensions {
 
	public static IEnumerable<T> FlattenHierarchy<T>(this T hierarchy) where T : IHierarchy<T> {
		return Enumerable.Repeat(hierarchy, 1).Concat(hierarchy.Children != null ?
			hierarchy.Children.SelectMany(child => child.FlattenHierarchy()) : Enumerable.Empty<T>());
	}
 
	public static IEnumerable<T> FlattenHierarchy<T>(this IEnumerable<T> hierarchies) where T : IHierarchy<T> {
		return hierarchies.SelectMany(h => h.FlattenHierarchy());
	}
 
	public static void RunThroughHierarchy<T>(this IEnumerable<T> hierarchies, Action<T, T> action) where T : IHierarchy<T> {
		foreach (var o in new List<T>(hierarchies)) {
			o.RunThroughHierarchy(action);
		}
	}
 
	public static void RunThroughHierarchy<T>(this T hierarchy, Action<T, T> action) where T : IHierarchy<T> {
		hierarchy.runThroughHierarchy(action, default(T));
	}
 
	private static void runThroughHierarchy<T>(this T hierarchy, Action<T, T> action, T parent) where T : IHierarchy<T> {
		if (hierarchy.Children != null) {
			foreach (var child in new List<T>(hierarchy.Children)) {
				runThroughHierarchy(child, action, hierarchy);
			}
		}
		action(parent, hierarchy);
	}
}

Реализация заключается в интерфейсе IHierarchy и наборе дополняющих методов для него. Можно так же реализовать это и через класс Hierarchy, но у интерфейса есть большой плюс в том, что наследуемый класс может так же наследоваться и от другого класса. В итоге появляется возможность работы с иерархией как с плоской коллекцией. В качестве примера, ниже приведён unit test для этого кода (NUnit).

[TestFixture]
public class HierarchyTests {
	public class Question {
		public string Label { get; set; }
		public string Answer { get; set; }
	}
 
	public class HierarchicalQuestion : Question, IHierarchy<HierarchicalQuestion> {
		public List<HierarchicalQuestion> Children {
			get;
			set;
		}
	}
 
	[Test]
	public static void IHierarchyTest() {
		var hierarchicalQuestions = new List<HierarchicalQuestion> {
			new HierarchicalQuestion {
				Label = "How many apples do you have?",
				Answer = "5",
				Children = new List<HierarchicalQuestion> {
					new HierarchicalQuestion {
						Label = "Yellow?",
						Answer = "1"
					},
					new HierarchicalQuestion {
						Label = "Green?",
						Answer = "3"
					},
					new HierarchicalQuestion {
						Label = "Red?",
						Answer = "1",
						Children = new List<HierarchicalQuestion> {
							new HierarchicalQuestion {
								Label = "From Mars?",
								Answer = "1"
							},
							new HierarchicalQuestion {
								Label = "From Jupiter?",
								Answer = "0"
							}
						}
					}
				}
			},
			new HierarchicalQuestion {
				Label = "Do you like apples?",
				Answer = "Yes"
			},
			new HierarchicalQuestion {
				Label = "Do you like C#?",
				Answer = "Certainly"
			}
		};
		Assert.AreEqual(8, hierarchicalQuestions.FlattenHierarchy<HierarchicalQuestion>().Count(), "Objects count mismatch.");
		Assert.AreEqual("From Jupiter?", hierarchicalQuestions.FlattenHierarchy<HierarchicalQuestion>().First(h => h.Answer == "0").Label);
		hierarchicalQuestions.RunThroughHierarchy((parent, child) => {
			if (child.Answer == "0") {
				(parent == null ? hierarchicalQuestions : parent.Children).Remove(child);
			}
		});
		Assert.AreEqual(7, hierarchicalQuestions.FlattenHierarchy<HierarchicalQuestion>().Count(), "Objects count mismatch after filtering.");
		Assert.IsFalse(hierarchicalQuestions.FlattenHierarchy<HierarchicalQuestion>().Any(h => h.Answer == "0"), "Deleted element found.");
	}
}

Статья была впервые опубликована 3-го апреля 2010 года в блоге.