using System;

using System.Collections.Generic;

using System.Linq;

using Newtonsoft.Json.Linq;

​

public class Program

{

    public static void Main()

    {

        string inputDocument = @"

            {

                ""Array3A"": [

                  { ""Item_1"": ""Desc_3A1"" },

                  { ""Item_2"": ""Desc_3A2"" },

                  { ""Item_3"": ""Desc_3A3"" }

                ],

                ""Array3B"": [

                  { ""Item_3B1"": ""Desc_3B1"" },

                  {

                    ""Array3B1"": [

                      { ""Item_1"": ""Desc_3B11"" },

                      { ""Item_2"": ""Desc_3B12"" },

                      { ""Item_3"": ""Desc_3B13"" }

                    ]

                  },

                  {

                    ""Array3B2"": [

                      { ""Item_1"": ""Desc_3B21"" },

                      { ""Item_2"": ""Desc_3B22"" },

                      { ""Item_3"": ""Desc_3B23"" }

                    ]

                  }

                ]

            }";

​

        string expectedFindItem_1 = @"

            {

                ""Array3A"": [

                  { ""Item_1"": ""Desc_3A1"" }

                ],

                ""Array3B"": [

                  {

                    ""Array3B1"": [

                      { ""Item_1"": ""Desc_3B11"" }

                    ]

                  },

                  {

                    ""Array3B2"": [

                      { ""Item_1"": ""Desc_3B21"" }

                    ]

                  }

                ]

            }";

​

        var root = (JContainer)JToken.Parse(inputDocument);

        var expected = (JContainer)JToken.Parse(expectedFindItem_1);

        var t1merged = MergeAncestry(root.SelectTokens("$.Array3A"));

        Console.WriteLine($"{t1merged.ToString()}");

        /* Outputs:

        {

            "Array3A": [

            {

                "Item_3A1": "Desc_3A1"

            },

            {

                "Item_3A2": "Desc_3A2"

            },

            {

                "Item_3A3": "Desc_3A3"

            }

            ]

        }

         */

        Console.WriteLine("------------------------");

        var t2merged = MergeAncestry(root.SelectTokens("$.Array3B.[*].*.[*].Item_1"));

        Console.WriteLine($"{t2merged.ToString()}");

        /* Outputs:

        {

            "Array3B": [

            {

                "Array3B1": [

                {

                    "Item_1": "Desc_3B11"

                }

                ]

            },

            {

                "Array3B2": [

                {

                    "Item_1": "Desc_3B21"

                }

                ]

            }

            ]

        }

         */

​

        Console.WriteLine("------------------------");

        var t3merged = MergeAncestry(root.SelectTokens("$.Array3B.[*].Array3B1.[*].*"));

        Console.WriteLine($"{t3merged.ToString()}");

        /* Outputs:

        {

          "Array3B": [

            {

              "Array3B1": [

                {

                  "Item_1": "Desc_3B11"

                },

                {

                  "Item_2": "Desc_3B12"

                },

                {

                  "Item_3": "Desc_3B13"

                }

              ]

            }

          ]

        }

         */

​

        Console.WriteLine("------------------------");

        var t4merged = MergeAncestry(root.SelectTokens("$.DoesntExist"));

        Console.WriteLine($"{t4merged.ToString()}"); 

        /* Outputs: 

        {}

        */

​

        Console.WriteLine("------------------------");

        var t5merged = MergeAncestry(root.SelectTokens("$..Item_1"));

        Console.WriteLine($"{t5merged.ToString()}");

        /* Outputs:

        {

          "Array3A": [

            {

              "Item_1": "Desc_3A1"

            }

          ],

          "Array3B": [

            {

              "Array3B1": [

                {

                  "Item_1": "Desc_3B11"

                }

              ]

            },

            {

              "Array3B2": [

                {

                  "Item_1": "Desc_3B21"

                }

              ]

            }

          ]

        }

        */

        Console.WriteLine(JToken.DeepEquals(expected, t5merged));

    }

​

    static JToken MergeAncestry(IEnumerable<JToken> tokens)

    {

        if (tokens == null || !tokens.Any())

        {

            return new JObject();

        }

​

        // Get a dictionary of tokens indexed by their depth

        var tokensByDepth = tokens

            .Distinct(ObjectReferenceEqualityComparer<JToken>.Default)

            .GroupBy(t => t.Ancestors().Count())

            .ToDictionary(

                g => g.Key, 

                g => g.Select(node => new CarbonCopyToken { Original = node, CarbonCopy = node.DeepClone() })

                        .ToList());

​

        // start at the deepest level working up

        int depth = tokensByDepth.Keys.Max();

        for (int i = depth; i > 0; i--)

        {

            // If there's nothing at the next level up, create a list to hold parents of children at this level

            if (!tokensByDepth.ContainsKey(i - 1))

            {

                tokensByDepth.Add(i - 1, new List<CarbonCopyToken>());

            }

​

            // Merge all tokens at this level into families by common parent

            foreach (var parent in MergeCommonParents(tokensByDepth[i]))

            {

                tokensByDepth[i - 1].Add(parent);

            }

        }

​

        // we should be left with a list containing a single CarbonCopyToken - contining the root of our copied document and the root of the source

        var cc = tokensByDepth[0].FirstOrDefault();

        return cc?.CarbonCopy ?? new JObject();

    }

​

    static IEnumerable<CarbonCopyToken> MergeCommonParents(IEnumerable<CarbonCopyToken> tokens)

    {

        var newParents = tokens.GroupBy(t => t.Original.Parent).Select(g => new CarbonCopyToken {

            Original = g.First().Original.Parent,

            CarbonCopy = CopyCommonParent(g.First().Original.Parent, g.AsEnumerable())

            });

        return newParents;

    }

​

    static JToken CopyCommonParent(JToken parent, IEnumerable<CarbonCopyToken> children)

    {

        switch (parent)

        {

            case JProperty _:

                return new JProperty(((JProperty)parent).Name, children.First().CarbonCopy);

            case JArray _:

                var newParentArray = new JArray();

                foreach (var child in children)

                {

                    newParentArray.Add(child.CarbonCopy);

                }

                return newParentArray;

            default: // JObject, or any other type we don't recognise

                var newParentObject = new JObject();

                foreach (var child in children)

                {

                    newParentObject.Add(child.CarbonCopy);

                }

                return newParentObject;

        }

​

    }

​

    class CarbonCopyToken

    {

        public JToken Original { get; set; }

        public JToken CarbonCopy { get; set; }

    }   

​

    /// <summary>

    /// A generic object comparerer that would only use object's reference, 

    /// ignoring any <see cref="IEquatable{T}"/> or <see cref="object.Equals(object)"/>  overrides.

    /// </summary>

    public class ObjectReferenceEqualityComparer<T> : IEqualityComparer<T> where T : class

    {

        // Adapted from this answer https://stackoverflow.com/a/1890230

        // to https://stackoverflow.com/questions/1890058/iequalitycomparert-that-uses-referenceequals

        // By https://stackoverflow.com/users/177275/yurik

        private static readonly IEqualityComparer<T> _defaultComparer;

​

        static ObjectReferenceEqualityComparer() { _defaultComparer = new ObjectReferenceEqualityComparer<T>(); }

​

        public static IEqualityComparer<T> Default { get { return _defaultComparer; } }

​

        #region IEqualityComparer<T> Members

​

        public bool Equals(T x, T y)

        {

            return ReferenceEquals(x, y);

        }

​

        public int GetHashCode(T obj)

        {

            return System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj);

        }

​

        #endregion

    }

}