Tree.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace _
{
    public sealed class Tree<TKey, TValue> : IEnumerable<KeyValuePair<TKey, Tree<TKey, TValue>.Node>>
        where TKey : IEquatable<TKey>
    {
        private readonly Dictionary<TKey, Node> nodesIndex;

        private Tree(IReadOnlyCollection<Node> root, Dictionary<TKey, Node> nodes)
        {
            nodesIndex = nodes;
            Root = root;
        }

        public IReadOnlyCollection<Node> Root { get; }
        public IEnumerable<TKey> Keys => nodesIndex.Keys;
        public IEnumerable<Node> Values => nodesIndex.Values;
        public Node this[TKey key] => nodesIndex[key];


        public abstract class Node
        {
            [CanBeNull]
            public Node Parent { get; }

            public TValue Value { get; }
            public IReadOnlyCollection<Node> Children { get; protected set; }

            protected Node(TValue value, Node parent = null)
            {
                Value = value;
                Parent = parent;
            }
        }

        public sealed class MyNode : Node
        {
            public new IReadOnlyCollection<Node> Children
            {
                get => base.Children;
                set => base.Children = value;
            }

            public MyNode(TValue value, Node parent = null) : base(value, parent)
            {
            }
        }

        public static Tree<TKey, TValue> BuildTree<TParentKey>(IEnumerable<TValue> values,
            Func<TValue, TKey> keySelector,
            Func<TValue, TParentKey> parentKeySelector,
            TParentKey rootKey)
            where TParentKey : IEquatable<TKey>, IEquatable<TParentKey>, TKey
            => BuildTree(values, keySelector, parentKeySelector, x => x, rootKey);

        public static Tree<TKey, TValue> BuildTree<TElement, TParentKey>(IEnumerable<TElement> values,
            Func<TValue, TKey> keySelector,
            Func<TElement, TParentKey> parentKeySelector,
            Func<TElement, TValue> valueSelector,
            TParentKey rootKey = default)
            where TParentKey : IEquatable<TKey>, IEquatable<TParentKey>, TKey
        {
            var nodes = new Dictionary<TKey, Node>();
            var enumerable = values as IReadOnlyCollection<TElement> ?? values.ToArray();
            if(enumerable.Count == 0)
            {
                return new Tree<TKey, TValue>(new List<Node>(), new Dictionary<TKey, Node>());
            }

            var index = enumerable.GroupBy(parentKeySelector).ToDictionary(x => x.Key);
            if(!index.ContainsKey(rootKey))
            {
                throw new InvalidOperationException("Invalid tree");
            }

            var root = new List<MyNode>();
            foreach(var element in index[rootKey])
            {
                var value = valueSelector(element);
                var node = new MyNode(value);
                root.Add(node);
                nodes.Add(keySelector(value), node);
                FillBranch(node, keySelector, index, valueSelector, nodes);
            }

            index.Remove(rootKey);

            return new Tree<TKey, TValue>(root, nodes);
        }

        private static void FillBranch<TParentKey, TElement, TElements>(MyNode branch,
            Func<TValue, TKey> keySelector,
            IDictionary<TParentKey, TElements> index,
            Func<TElement, TValue> valueSelector,
            IDictionary<TKey, Node> nodes)
            where TParentKey : IEquatable<TKey>, IEquatable<TParentKey>, TKey
            where TElements : class, IEnumerable<TElement>
        {
            var key = (TParentKey) keySelector(branch.Value);
            if(index.ContainsKey(key))
            {
                branch.Children = index[key].Select(x =>
                {
                    var value = valueSelector(x);
                    var node = new MyNode(value, branch);
                    nodes.Add(keySelector(value), node);
                    return node;
                }).ToArray();
                index.Remove(key);
                foreach(var child in branch.Children)
                {
                    FillBranch((MyNode) child, keySelector, index, valueSelector, nodes);
                }
            }
            else
            {
                branch.Children = new Node[0];
            }
        }

        public Comparsion Diff(Tree<TKey, TValue> other, Func<TValue, TValue, bool> valueComparer)
        {
            var lhs = this;
            var rhs = other;
            var changeList = new List<Comparsion.Change>();
            foreach(var (key, lNode) in lhs)
            {
                if(rhs.Keys.Contains(key))
                {
                    var rNode = rhs[key];
                    var isModified = IsModified(valueComparer, lNode, rNode);
                    if(isModified)
                        changeList.Add(new Comparsion.Change(ChangeType.Modification, key, rNode));
                }
                else
                    changeList.Add(new Comparsion.Change(ChangeType.Deletion, key));
            }

            foreach(var (key, rNode) in rhs)
            {
                if(lhs.Keys.Contains(key))
                    continue;
                changeList.Add(new Comparsion.Change(ChangeType.Addition, key, rNode));
            }

            changeList.Sort();
            return new Comparsion(changeList);
        }

        private static bool IsModified(Func<TValue, TValue, bool> valueComparer, Node lNode, Node rNode)
        {
            if(valueComparer(lNode.Value, rNode.Value))
            {
                var lParentValue = lNode.Parent == null ? default : lNode.Parent.Value;
                var rParentValue = rNode.Parent == null ? default : rNode.Parent.Value;
                if(valueComparer(lParentValue, rParentValue))
                    return true;
            }
            else
                return true;

            return false;
        }

        public class Comparsion
        {
            public Comparsion(IEnumerable<Change> changes)
            {
                Changes = changes;
            }

            public IEnumerable<Change> Changes { get; }

            public class Change : IComparable<Change>
            {
                public Change(ChangeType type, TKey key, Node value = default, Node parent = default)
                {
                    Type = type;
                    Key = key;
                    Value = value;
                }

                public ChangeType Type { get; }
                public TKey Key { get; }
                public Node Value { get; }

                public int CompareTo(Change other)
                {
                    if(ReferenceEquals(this, other)) return 0;
                    if(ReferenceEquals(null, other)) return 1;
                    return ((byte) Type).CompareTo((byte) other.Type);
                }
            }
        }


        public enum ChangeType : byte
        {
            Addition,
            Modification,
            Deletion,
        }

        public Enumerator GetEnumerator() => new Enumerator(nodesIndex.GetEnumerator());
        IEnumerator<KeyValuePair<TKey, Node>> IEnumerable<KeyValuePair<TKey, Node>>.GetEnumerator() => GetEnumerator();

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

        public struct Enumerator : IEnumerator<KeyValuePair<TKey, Node>>
        {
            private Dictionary<TKey, Node>.Enumerator internalEnumerator;

            public Enumerator(Dictionary<TKey, Node>.Enumerator internalEnumerator)
            {
                this.internalEnumerator = internalEnumerator;
            }

            public bool MoveNext() => internalEnumerator.MoveNext();

            void IEnumerator.Reset() => ((IEnumerator) internalEnumerator).Reset();

            public KeyValuePair<TKey, Node> Current => internalEnumerator.Current;

            object IEnumerator.Current => Current;

            public void Dispose() => internalEnumerator.Dispose();
        }
    }
}