Improve nodes support

eduherminio · eduherminio · May 2, 2020 · Apr 25, 2020 · Apr 27, 2020 · Apr 27, 2020
commit d1f70aeafa8b281b07e5c1920f666cf99ebad088
diff --git a/src/SheepTools/Model/Node.cs b/src/SheepTools/Model/Node.cs
@@ -1,4 +1,6 @@
-namespace SheepTools.Model
+using System.Collections.Generic;
+
+namespace SheepTools.Model
 {
     /// <summary>
     /// Node class, with equality operators overriden
@@ -15,5 +17,15 @@ public Node(string id) : base(id)
         public Node(string id, Node child) : base(id, child)
         {
         }
+
+        /// <inheritdoc/>
+        public Node(string id, IEnumerable<Node> children) : base(id, children)
+        {
+        }
+
+        /// <inheritdoc/>
+        public Node(Node parent, string id) : base(parent, id)
+        {
+        }
     }
 }
diff --git a/src/SheepTools/Model/Point.cs b/src/SheepTools/Model/Point.cs
@@ -74,7 +74,7 @@ public Point CalculateClosestManhattanPointNotTied(ICollection<Point> candidateP
                 : null;
         }
 
-        static public IEnumerable<Point> GeneratePointRangeIteratingOverYFirst(IEnumerable<double> xRange, IEnumerable<double> yRange)
+        public static IEnumerable<Point> GeneratePointRangeIteratingOverYFirst(IEnumerable<double> xRange, IEnumerable<double> yRange)
         {
             foreach (double x in xRange)
             {
@@ -85,12 +85,12 @@ static public IEnumerable<Point> GeneratePointRangeIteratingOverYFirst(IEnumerab
             }
         }
 
-        static public IEnumerable<Point> GeneratePointRangeIteratingOverYFirst(IEnumerable<int> xRange, IEnumerable<int> yRange)
+        public static IEnumerable<Point> GeneratePointRangeIteratingOverYFirst(IEnumerable<int> xRange, IEnumerable<int> yRange)
         {
             return GeneratePointRangeIteratingOverYFirst(xRange.Select(x => (double)x), yRange.Select(y => (double)y));
         }
 
-        static public IEnumerable<Point> GeneratePointRangeIteratingOverXFirst(IEnumerable<double> xRange, IEnumerable<double> yRange)
+        public static IEnumerable<Point> GeneratePointRangeIteratingOverXFirst(IEnumerable<double> xRange, IEnumerable<double> yRange)
         {
             foreach (double y in yRange)
             {
@@ -101,7 +101,7 @@ static public IEnumerable<Point> GeneratePointRangeIteratingOverXFirst(IEnumerab
             }
         }
 
-        static public IEnumerable<Point> GeneratePointRangeIteratingOverXFirst(IEnumerable<int> xRange, IEnumerable<int> yRange)
+        public static IEnumerable<Point> GeneratePointRangeIteratingOverXFirst(IEnumerable<int> xRange, IEnumerable<int> yRange)
         {
             return GeneratePointRangeIteratingOverXFirst(xRange.Select(x => (double)x), yRange.Select(y => (double)y));
         }

diff --git a/src/SheepTools/Model/TreeNode.cs b/src/SheepTools/Model/TreeNode.cs
@@ -22,30 +22,67 @@ public class TreeNode<TKey> : GenericNode<TKey>
         /// <summary>
         /// Direct descendants
         /// </summary>
-        public ICollection<TreeNode<TKey>> Children { get; set; } = new HashSet<TreeNode<TKey>>();
+        public ICollection<TreeNode<TKey>> Children { get; set; }
 
         /// <inheritdoc/>
         public TreeNode(TKey id) : base(id)
         {
+            Children = new HashSet<TreeNode<TKey>>();
         }
 
         /// <summary>
         /// Initialize with one of its children
         /// </summary>
         /// <param name="id"></param>
         /// <param name="child">One of their descendants</param>
+        /// <exception cref="ArgumentException">When provided child's key is the same as TreeNode key</exception>
         public TreeNode(TKey id, TreeNode<TKey> child) : base(id)
         {
             if (Equals(child))
             {
                 throw new ArgumentException("A node cannot be its own child");
             }
 
-            Children.Add(child);
+            Children = new HashSet<TreeNode<TKey>> { child };
         }
 
         /// <summary>
-        /// Number of descendants
+        /// Initialize with a number of its descendants
+        /// </summary>
+        /// <param name="id"></param>
+        /// <param name="children">Multiple descendants</param>
+        /// <exception cref="ArgumentException">When provided child's key is the same as TreeNode key</exception>
+        public TreeNode(TKey id, IEnumerable<TreeNode<TKey>> children) : base(id)
+        {
+            if (children.Select(c => c.Id).Contains(id))
+            {
+                throw new ArgumentException("A node cannot be its own child");
+            }
+
+            Children = new HashSet<TreeNode<TKey>>(children);
+        }
+
+        /// <summary>
+        /// Initialize with its parent
+        /// </summary>
+        /// <param name="parent">Node parent</param>
+        /// <param name="id"></param>
+        /// <exception cref="ArgumentException">When provided child's key is the same as TreeNode key</exception>
+        public TreeNode(TreeNode<TKey> parent, TKey id) : base(id)
+        {
+            if (parent.Id.Equals(id))
+            {
+                throw new ArgumentException("A node cannot be its own parent");
+            }
+
+            Parent = parent;
+            ParentId = parent.Id;
+            Children = new HashSet<TreeNode<TKey>>();
+        }
+
+        /// <summary>
+        /// Number of descendants.
+        /// Requires nodes children to be populated
         /// </summary>
         /// <returns></returns>
         public int DescendantsCount()
@@ -55,7 +92,8 @@ public int DescendantsCount()
         }
 
         /// <summary>
-        /// Number of children of the children of (the children of) my children
+        /// Number of children of the children of (the children of) my children.
+        /// Requires nodes children to be populated
         /// Equals to <see cref="DescendantsCount()"/>
         /// </summary>
         /// <returns></returns>
@@ -74,6 +112,7 @@ public int RelationshipsCount()
 
         /// <summary>
         /// Distance to childNode.
+        /// Requires nodes children to be populated.
         /// int.MaxValue if childNode is not among this node descendants
         /// </summary>
         /// <param name="childNode"></param>
@@ -97,5 +136,44 @@ public int DistanceTo(TreeNode<TKey> childNode, int initialDistance)
                     : ++existingDistance;
             }
         }
+
+        /// <summary>
+        /// Common ancestor of two nodes.
+        /// Requires node parents to be populated
+        /// </summary>
+        /// <param name="nodes"></param>
+        /// <param name="otherNode"></param>
+        /// <exception cref="NotFoundException"></exception>
+        /// <returns></returns>
+        public TreeNode<TKey> GetCommonAncestor(IEnumerable<TreeNode<TKey>> nodes, TreeNode<TKey> otherNode)
+        {
+            var identifiers = new HashSet<TKey>();
+
+            TreeNode<TKey> commonAncestor = null;
+
+            void transverseBackwards(IEnumerable<TreeNode<TKey>> nodes, ref HashSet<TKey> identifiers, TreeNode<TKey> currentNode)
+            {
+                while (currentNode.ParentId != null && !currentNode.ParentId.Equals(default(TKey)))
+                {
+                    if (!identifiers.Add(currentNode.Id))
+                    {
+                        commonAncestor = currentNode;
+                        break;
+                    }
+
+                    currentNode = nodes.Single(node => node.Id.Equals(currentNode.ParentId));
+                }
+            }
+
+            transverseBackwards(nodes, ref identifiers, this);
+            transverseBackwards(nodes, ref identifiers, otherNode);
+
+            if (commonAncestor == null)
+            {
+                throw new NotFoundException($"We couldn't find any common ancestors between nodes {Id} and {otherNode.Id}");
+            }
+
+            return commonAncestor;
+        }
     }
 }
diff --git a/src/SheepTools/SheepToolsExceptions.cs b/src/SheepTools/SheepToolsExceptions.cs
@@ -22,4 +22,24 @@ protected ValidationException(SerializationInfo info, StreamingContext context)
         {
         }
     }
+
+    [Serializable]
+    public class NotFoundException : Exception
+    {
+        public NotFoundException()
+        {
+        }
+
+        public NotFoundException(string message) : base(message)
+        {
+        }
+
+        public NotFoundException(string message, Exception innerException) : base(message, innerException)
+        {
+        }
+
+        protected NotFoundException(SerializationInfo info, StreamingContext context) : base(info, context)
+        {
+        }
+    }
 }
diff --git a/tests/SheepTools.Test/Extensions/IntExtensionsTest.cs b/tests/SheepTools.Test/Extensions/IntExtensionsTest.cs
@@ -50,7 +50,7 @@ public void Clamp()
 
             foreach (var pair in testCases)
             {
-                Assert.Equal(pair.Value, pair.Key.Factorial());
+                Assert.Equal(pair.Value, pair.Key.Clamp(minValue, maxValue));
             }
         }
     }

diff --git a/tests/SheepTools.Test/Model/NodeTest.cs b/tests/SheepTools.Test/Model/NodeTest.cs
@@ -1,5 +1,6 @@
 using SheepTools.Model;
 using System;
+using System.Linq;
 using System.Collections.Generic;
 using Xunit;
 
@@ -103,22 +104,9 @@ public void DescendantsCount()
         [Fact]
         public void RelationshipsCount()
         {
-            var l = new Node("L");
-            var i = new Node("I");
-            var h = new Node("H");
-            var f = new Node("F");
-            var k = new Node("K", l);
-            var j = new Node("J", k);
-            var g = new Node("G", h);
-            var e = new Node("E", f);
-            var d = new Node("D", e);
-            var c = new Node("C", d);
-            var b = new Node("B", c);
-            var com = new Node("COM", b);
-            b.Children.Add(g);
-            e.Children.Add(j);
-            d.Children.Add(i);
+            var nodes = GenerateTestGraphWithChildren();
 
+            var com = nodes.Single(n => n.Id == "COM");
             var result = com.RelationshipsCount();
 
             Assert.Equal(42, result);
@@ -130,15 +118,11 @@ public void RelationshipsCount()
         [Fact]
         public void DistanceTo()
         {
-            var f = new Node("F");
-            var i = new Node("I");
-            var l = new Node("L");
-            var e = new Node("E", f);
-            var d = new Node("D", e);
-            var k = new Node("K", l);
-            var j = new Node("J", k);
-            e.Children.Add(j);
-            d.Children.Add(i);
+            var nodes = GenerateTestGraphWithChildren();
+
+            var k = nodes.Single(n => n.Id == "K");
+            var d = nodes.Single(n => n.Id == "D");
+            var i = nodes.Single(n => n.Id == "I");
 
             var result = d.DistanceTo(k, 0) + d.DistanceTo(i, 0);
 
@@ -150,5 +134,77 @@ public void DistanceTo()
             Assert.Equal(int.MaxValue, k.DistanceTo(i, 0));
             Assert.Equal(int.MaxValue, i.DistanceTo(k, 0));
         }
+
+        [Fact]
+        public void GetCommonAncestor()
+        {
+            var nodes = GenerateTestGraphWithParent();
+
+            var d = nodes.Single(n => n.Id == "D");
+            var e = nodes.Single(n => n.Id == "E");
+            var f = nodes.Single(n => n.Id == "F");
+            var l = nodes.Single(n => n.Id == "L");
+
+            Assert.Equal(d.Id, d.GetCommonAncestor(nodes, d).Id);
+            Assert.Equal(d.Id, d.GetCommonAncestor(nodes, e).Id);
+            Assert.Equal(d.Id, d.GetCommonAncestor(nodes, f).Id);
+            Assert.Equal(e.Id, f.GetCommonAncestor(nodes, l).Id);
+            Assert.Equal(e.Id, l.GetCommonAncestor(nodes, f).Id);
+        }
+
+        /// <summary>
+        /// https://adventofcode.com/2019/day/6
+        /// </summary>
+        /// <returns></returns>
+        private static ICollection<Node> GenerateTestGraphWithChildren()
+        {
+            var nodeList = new List<Node>();
+
+            var l = new Node("L");
+            var i = new Node("I");
+            var h = new Node("H");
+            var f = new Node("F");
+            var k = new Node("K", l);
+            var j = new Node("J", k);
+            var g = new Node("G", h);
+            var e = new Node("E", new[] { f, j });
+            var d = new Node("D", new[] { e, i });
+            var c = new Node("C", d);
+            var b = new Node("B", new[] { c, g });
+            var com = new Node("COM", b);
+            b.Children.Add(g);
+            e.Children.Add(j);
+            d.Children.Add(i);
+
+            nodeList.AddRange(new[] { com, b, c, d, e, f, g, h, i, j, k, l });
+
+            return nodeList;
+        }
+
+        /// <summary>
+        /// https://adventofcode.com/2019/day/6
+        /// </summary>
+        /// <returns></returns>
+        private static ICollection<Node> GenerateTestGraphWithParent()
+        {
+            var nodeList = new List<Node>();
+
+            var com = new Node("COM");
+            var b = new Node(com, "B");
+            var c = new Node(b, "C");
+            var d = new Node(c, "D");
+            var e = new Node(d, "E");
+            var f = new Node(e, "F");
+            var g = new Node(b, "G");
+            var h = new Node(g, "H");
+            var i = new Node(d, "I");
+            var j = new Node(e, "J");
+            var k = new Node(j, "K");
+            var l = new Node(k, "L");
+
+            nodeList.AddRange(new[] { com, b, c, d, e, f, g, h, i, j, k, l });
+
+            return nodeList;
+        }
     }
 }
-Original file line number
+Diff line change
@@ Expand Up / @@ -50,7 +50,7 @@ public void Clamp() @@
                 foreach (var pair in testCases)
                 {
-                    Assert.Equal(pair.Value, pair.Key.Factorial());
+                    Assert.Equal(pair.Value, pair.Key.Clamp(minValue, maxValue));
                 }
             }
         }
@@ Expand Down @@