How to group only subsequent items with the same property using linq

Question

I have input that could look like this:

A   1   2   C,D
A   2   3   C,E
B   4   5   F
A   6   7
A   7   8   D
A   9   10  E

I store this in my model class:

public class Item {

public String Name {get;set;}
public int Start {get;set;}
public int End {get;set;}
public List<string> Orders {get;set;}

}

I tried to use Linq to merge all subsequent items if the items have the same name and generate a new item that has the start value of the first item in the group, the end value of the last item in the group and a union of all order lists. It should then look like this:

A   1   3   C,D,E
B   4   5   F
A   6   10  D, E

I tried the following Linq statement, however, it groups all As and Bs together, independent of whether there are any other items in between. What do I need to change? The union of the order list is also missing.

var groups = items.GroupBy(i => i.Name).ToList();

foreach (var group in groups)
{
   result.Add(new Item {
     Start = group.First().Start, 
     End = group.Last().End, 
     Name = group.First().Name });
}

Answer 1

A bit late, I know, but I think the following solution will still help someone. It includes the original Item class, enhanced with:

• A ToString method to simplify inspection.
• A CreateSamples method to generate the sample items.
• A bonus nested class ComparerByStartAndEnd to sort items based on Start and End properties.

The solution resides in the EXTENSIONS.GroupWhenChanging method and the Item.FromGroup method.

The TEST class provides code to verify everything works as expected.

The actual grouping logic (EXTENSIONS.GroupWhenChanging) simply implements an enumerator that does not invoke Linq methods and allocates only a List object for each group, thus saving both in performance and memory resources. The method is generic and accepts a comparison predicate, so it is not restricted to the sample Item class.

The creation of the result items, representing the groups with merged orders, is kept in the separate method Item.FromGroup. It uses some Linq to ease the task.

The TEST.Test method does the following:

• Creates the list of samples.
• Ensures the samples are ordered based on Start and End.
• Enumerates the groups (by means of GroupWhenChanging) and creates the corresponing items (through Item.FromGroup).

The Item class:

public static class MODEL
{
    public class Item
    {
        public String Name { get; set; }
        public int Start { get; set; }
        public int End { get; set; }
        public List<string> Orders { get; set; }

        /// <inheritdoc/>
        public override string ToString()
        {
            return string.Format("{0} {1} .. {2} {3}", this.Name, this.Start, this.End, string.Join(",", this.Orders));
        }

        public static Item? FromGroup(IEnumerable<Item> group)
        {
            var array = group as Item[] ?? group.ToArray();
            if (array.Length > 0)
            {
                var newName = array[0].Name;
                var newStart = array.Min(item => item.Start);
                var newEnd = array.Max(item => item.End);
                var newOrders = array.SelectMany(item => item.Orders).Distinct().OrderBy(orderID => orderID).ToList();

                var newItem = new Item()
                {
                    Name = newName,
                    Start = newStart,
                    End = newEnd,
                    Orders = newOrders
                };

                return newItem;
            }

            return null;
        }

        public static IEnumerable<Item> CreateSamples()
        {
            yield return new Item() { Name = "A", Start = 1, End = 2, Orders = new List<string>() { "C", "D" } };
            yield return new Item() { Name = "A", Start = 2, End = 3, Orders = new List<string>() { "C", "E" } };
            yield return new Item() { Name = "B", Start = 4, End = 5, Orders = new List<string>() { "F" } };
            yield return new Item() { Name = "A", Start = 6, End = 7, Orders = new List<string>() };
            yield return new Item() { Name = "A", Start = 7, End = 8, Orders = new List<string>() { "D" } };
            yield return new Item() { Name = "A", Start = 9, End = 10, Orders = new List<string>() { "E" } };
        }

        public sealed class ComparerByStartAndEnd : Comparer<Item>
        {
            /// <inheritdoc/>
            public override int Compare(Item x, Item y)
            {
                if (x == y)
                    return 0;

                return x.End.CompareTo(y.Start);
            }
        }
    }
}

The EXTENSIONS class:

public static class EXTENSIONS
{
    public static IEnumerable<IEnumerable<T>> GroupWhenChanging<T>(this IEnumerable<T> items, Func<T, T, bool> predicate)
    {
        List<T> group = null;
        foreach (var item in items)
        {
            if (group is null)
                group = new List<T>() { item };
            else if (predicate(group[group.Count - 1], item))
                group.Add(item);
            else
            {
                yield return group;
                group = new List<T>() { item };
            }
        }
        if (group is not null)
            yield return group;
    }
}

The TEST class:

public static class TEST
{
    public static void Test()
    {
        var items = MODEL.Item.CreateSamples().ToList();

        items.Sort(new MODEL.Item.ComparerByStartAndEnd());

        var groups = items
            .GroupWhenChanging((prev, next) => prev.Name == next.Name)
            .Select(MODEL.Item.FromGroup)
            .ToList();
    }
}

Answer 2

This is not done by Linq. I just played a bit using simpler methods. But it gives same result which you wanted.

using System;
using System.Collections.Generic;

public class Item
{
    public static List<Item> Database;

    static Item()
    {
        Database = new List<Item>();
    }

    public Item(string name, int start, int end, params string[] orders)
    {
        Name = name;
        Start = start;
        End = end;
        Orders = new List<string>();
        foreach (string s in orders)
            Orders.Add(s);
        //putting newly created Item to database
        Database.Add(this);
    }

    //overload for creating tmp Items in GroupThem(), could be done using optinional parameter
    public Item(bool AddToDatabase, string name, int start, int end, params string[] orders)
    {
        Name = name;
        Start = start;
        End = end;
        Orders = new List<string>();
        foreach (string s in orders)
            Orders.Add(s);
        if (AddToDatabase) Database.Add(this);
    }

    public string Name { get; set; }
    public int Start { get; set; }
    public int End { get; set; }
    public List<string> Orders { get; set; }

    public List<Item> GroupedItems()
    {
        List<Item> groupedItems = new List<Item>();
        Item previous = Database[0];
        Stack<Item> sameItems = new Stack<Item>();

        foreach (Item item in Database)
        {
            if (previous.Name == item.Name)
            {
                sameItems.Push(item);
            }
            else
            {
                groupedItems.Add(GroupThem(sameItems));
                previous = item;
                sameItems.Push(item);
            }
        }
        groupedItems.Add(GroupThem(sameItems));
        return groupedItems;
    }

    private Item GroupThem(Stack<Item> sameItems)
    {
        string newName = "";
        int newEnd = 0;
        int newStart = int.MaxValue;
        List<string> newOrders = new List<string>();
        Item tmp = null;
        while (sameItems.Count > 0)
        {
            tmp = sameItems.Pop();
            if (tmp.Start < newStart)
                newStart = tmp.Start;
            if (tmp.End > newEnd)
                newEnd = tmp.End;
            foreach (string s in tmp.Orders)
                if (!newOrders.Contains(s))
                    newOrders.Add(s);
            newName = tmp.Name;
        }
        return new Item(false, newName, newStart, newEnd, newOrders.ToArray());
    }

    public override string ToString()
    {
        string tmp = "";
        foreach (string s in Orders)
            tmp += " " + s;
        return "Name = " + Name + ", Start = " + Start + ", End = " + End +", Orders  = "+ tmp;
    }
}

class Program
{
    static void Main(string[] args)
    {

        Item item1 = new Item("A", 1, 2, "C", "D");
        Item item2 = new Item("A", 2, 3, "C", "E");
        Item item3 = new Item("B", 4, 5, "F");
        Item item4 = new Item("A", 6, 7);
        Item item5 = new Item("A", 7, 8, "D");
        Item item6 = new Item("A", 9, 10, "E");

        foreach (Item item in item1.GroupedItems())
        {
            Console.WriteLine(item);
        }
    }
}

Answer 3

Maybe not the best or fastest way but I got bored:

int groupID = -1;

var result = items.Select((item, index) =>
{
    if (index == 0 || items[index - 1].Name != item.Name)
        ++groupID;

    return new { group = groupID, item = item };
}).GroupBy(item => item.group).Select(group =>
{
    Item item = new Item();

    var first = group.First().item;
    var last = group.Last().item;

    item.Name = first.Name;
    item.Start = first.Start;
    item.End = last.End;
    item.Orders = group.SelectMany(g => g.item.Orders).Distinct().ToList();

    return item;
});

The variable items should be your input collection like a List<Item>. The result will be stored in result. This is an IEnumerable<Item> but you may add .ToList() or .ToArray() as you like to convert it to List<Item> or Item[].

The result will contain new created items. I did this on purpose to not mess up the input data.

The trick here is to use a local variable as a group id. It is increased if it is the first item or the last item had a different name. Then we group by the group id and the rest of the code will just create the item. The SelectMany method will join all Orders-values from the entire group and Distinct will then remove all duplicates.

Answer 4

Use a classic loop for this:

var List<List<Item>> groups = new List<List<Item>>()
var currentGroup = new List<Item> { items.First() };
int i = 0;
foreach(var item in items.Skip(1))
{
    if(currentGroup.First().Name != item.Name)
    {
        groups.Add(currentGroup);
        currentGroup = new List<Item> { item };
    }
    else
    {
        currentGroup.Add(item);
        if(i == items.Count - 2) 
            groups.Add(currentGroup);
    }
    i++;
}

Now you can continue with your code by iterating the groups-list.