using System; using System.Collections.Generic; using System.Linq; public class Graph : IEquatable> { public Graph(T value, IEnumerable> children) { Value = value; Children = children; } public T Value { get; } public IEnumerable> Children { get; } public bool Equals(Graph other) => Value.Equals(other.Value) && Children.SequenceEqual(other.Children); } public class GraphCrumb { public GraphCrumb(T value, IEnumerable> left, IEnumerable> right) { Value = value; Left = left; Right = right; } public T Value { get; } public IEnumerable> Left { get; } public IEnumerable> Right { get; } } public class GraphZipper { public GraphZipper(Graph focus, IEnumerable> crumbs) { Focus = focus; Crumbs = crumbs; } public Graph Focus { get; } public IEnumerable> Crumbs { get; } } public static class Pov { public static Graph CreateGraph(T value, IEnumerable> children) => new Graph(value, children); public static Graph FromPOV(T value, Graph graph) where T : IComparable => ChangeParent(FindNode(value, GraphToZipper(graph))); public static IEnumerable TracePathBetween(T value1, T value2, Graph graph) where T : IComparable => ZipperToPath(FindNode(value2, GraphToZipper(FromPOV(value1, graph)))); private static GraphZipper GraphToZipper(Graph graph) { if (graph == null) return null; return new GraphZipper(graph, Enumerable.Empty>()); } private static IEnumerable ZipperToPath(GraphZipper zipper) { if (zipper == null) return null; return zipper.Crumbs.Select(c => c.Value).Reverse().Concat(new[] { zipper.Focus.Value }); } private static GraphZipper GoDown(GraphZipper zipper) { if (zipper == null || !zipper.Focus.Children.Any()) return null; var focus = zipper.Focus; var children = focus.Children; var newCrumb = new GraphCrumb(focus.Value, Enumerable.Empty>(), children.Skip(1)); return new GraphZipper(children.First(), new[] { newCrumb }.Concat(zipper.Crumbs)); } private static GraphZipper GoRight(GraphZipper zipper) { if (zipper == null || !zipper.Crumbs.Any() || !zipper.Crumbs.First().Right.Any()) return null; var crumbs = zipper.Crumbs; var firstCrumb = crumbs.First(); var newCrumb = new GraphCrumb(firstCrumb.Value, firstCrumb.Left.Concat(new[] { zipper.Focus }), firstCrumb.Right.Skip(1)); return new GraphZipper(firstCrumb.Right.First(), new[] { newCrumb }.Concat(crumbs.Skip(1))); } private static GraphZipper FindNode(T value, GraphZipper zipper) where T : IComparable { if (zipper == null || zipper.Focus.Value.CompareTo(value) == 0) return zipper; return FindNode(value, GoDown(zipper)) ?? FindNode(value, GoRight(zipper)); } private static Graph ChangeParent(GraphZipper zipper) { if (zipper == null) return null; if (!zipper.Crumbs.Any()) return zipper.Focus; var firstCrumb = zipper.Crumbs.First(); var focus = zipper.Focus; var newZipper = new GraphZipper(CreateGraph(firstCrumb.Value, firstCrumb.Left.Concat(firstCrumb.Right)), zipper.Crumbs.Skip(1)); var parentGraph = ChangeParent(newZipper); var ys = focus.Children.Concat(new[] { parentGraph }); return CreateGraph(focus.Value, ys); } }