CODEWITHSUNDEEP
c#recursioncollectionsmerge
Unapedra
Unapedra

Reputation: 2403

Merge two collections recursivelly combining duplicates by property

Given two collections of objects with recursive structure:

Collection1 = [
    {
        Header: "H1",
        Items: [{
            Header: "H1.1"
        },{
            Header: "H1.2"
        }]
    },
    {
        Header: "H2",
        Items: [{
            Header: "H2.1"
        }]
    }
]

Collection2 = [
    {
        Header: "H1",
        Items: [{
            Header: "H1.1",
            Items: [{
                Header: "H1.1.1"
            }]
        }]
    }
]

I'd like to make some kind of function to combine those two collection having as the comparison property the one I indicate, in this case Header, and that combines their properties so that the result is somewhat as follows:

Result = [
    {
        Header: "H1",
        Items: [{
            Header: "H1.1",
            Items: [{
                Header: "H1.1.1"
            }]
        },{
            Header: "H1.2"
        }]
    },
    {
        Header: "H2",
        Items: [{
            Header: "H2.1"
        }]
    }
]

As you can see, it checks recursively the object properties and, if a similar item exists (in this case, comparing the Header property), it just combines both objects.

I've tried Union(), Distinct() and so on, but I cannot seem to find the way to achieve this.

EDIT: The merge should be done on a "same-level" basis, so only items that have the same header at the same deepness level should be considered equal.

Upvotes: 2

Views: 410

Answers (2)

Renato Lucas Chitolina
Renato Lucas Chitolina

Reputation: 146

You can do the following...

Supposing that you have a class similar to this:

public class Node {
    public string Header { get; set; }
    public IEnumerable<Node> Items { get; set; }

    public Node() {
        /* Note that I like to start the collections within the object's construction, 
         * to avoid issues inside operations that manipulate these collections. */
        Items = new Collection<Node>();
    }
}

You can use the virtues of the Linq Union, using a recursive implementation of IEqualityComparer. Something like that:

public class NodeComparer : IEqualityComparer<Node>
{
    public bool Equals(Node me, Node another) 
    {
        if (me.Header == another.Header) 
        {
            me.Items = me.Items.Union(another.Items, new NodeComparer()).ToList();

            return true;
        }

        return false;
    }

    public int GetHashCode(Node node) 
    {
        return node.Header.GetHashCode();
    }
}

The main calling of this is:

var result = collection1.Union(collection2, new NodeComparer()).ToList();

Basically what this does is use the comparison of the Union method, considering the headers of nodes (through method GetHashCode), and for each node that has the same header value, the same process is done for your child (through the method Equals), and this occurs successively to all levels.

I've tested this solution with a few scenarios, and it seemed to work out fine, but if there is still some situation that does not solve, maybe it's a good way to start.

Upvotes: 2

Martin Liversage
Martin Liversage

Reputation: 106926

Here is a class that models your items:

class Item
{
    public string Header { get; set; }
    public IEnumerable<Item> Items { get; set; }
}

This recursive function merges the items in the way you describe:

IEnumerable<Item> Merge(IEnumerable<Item> items)
{
    var lookup = items.ToLookup(item => item.Header);
    foreach (var grouping in lookup)
    {
        var childItems = grouping.Aggregate(
            new List<Item>(),
            (list, item) =>
            {
                if (item.Items != null)
                    list.AddRange(item.Items);
                return list;
            });
        yield return new Item
        {
            Header = grouping.Key,
            Items = Merge(childItems)
        };
    }
}

Let me explain a bit:

  • The lookup is like a dictionary except the value for each key is not a single Item but instead a collection of Item instances that all share the same key (Header).

  • Each item in the lookup is not a KeyValuePair but instead an IGrouping and by iterating all the groupings you get all the headers on that level.

  • Aggregate is used to create a list that has all the child items of all the items in the grouping. This list can contain multiple items with the same header but this is the kind of data Merge is designed to work on.

  • To merge the child items recursion is used.

To merge two collections you need to call the function like this:

var mergedCollection = Merge(collection1.Concat(collection2));

Upvotes: 1

Related Questions