Complex Linq Grouping

Question

I'm new to Stack Overflow, but tried to put as much information

I have following class structure

public class ItemEntity
{
    public int ItemId { get; set; }
    public int GroupId { get; set; }
    public string GroupName { get; set; }
    public DateTime ItemDate { get; set; }
    public string Field1 { get; set; }
    public string Filed2 { get; set; }
    public string Field3 { get; set; }
    public string Field4 { get; set; }
    public int Duration { get; set; }        
}

public class MasterEntity
{
    public ItemEntity Item { get; set; }
    public List<int> ItemList { get; set; }
    public List<int> GroupList { get; set; }
}

I am trying to group list of ItemEntity into MasterEntity. Grouping fileds are Field1,Field2 and Field3.

I have done the grouping so far like below

var items = new List<ItemEntity>
            {
                new ItemEntity
                {
                    ItemId = 100,
                    GroupId = 1,
                    GroupName= "Group 1",
                    ItemDate = new DateTime(2018,10,17),
                    Duration = 7,
                    Field1 = "Item Name 1",
                    Filed2 = "aaa",
                    Field3= "bbb",
                    Field4= "abc"
                },
                new ItemEntity
                {
                    ItemId = 150,
                    GroupId = 2,
                    GroupName= "Group 2",
                    ItemDate = new DateTime(2018,10,17),
                    Duration = 5,
                    Field1 = "Item Name 1",
                    Filed2 = "aaa",
                    Field3= "bbb",
                    Field4= "efg"
                },
                new ItemEntity
                {
                    ItemId = 250,
                    GroupId = 3,
                    GroupName= "Group 3",
                    ItemDate = new DateTime(2018,10,15),
                    Duration = 7,
                    Field1 = "Item Name 1",
                    Filed2 = "aaa",
                    Field3= "bbb",
                    Field4= "xyz"
                }
            };


            var group = items.GroupBy(g => new
            {
                g.Field1,
                g.Filed2,
                g.Field3
            }).Select(s => new MasterEntity
            {
                Item = new ItemEntity
                {
                    Field1 = s.Key.Field1,
                    Filed2 = s.Key.Filed2,
                    Field3 = s.Key.Field3
                },
                ItemList = s.Select(g => g.ItemId).ToList(),
                GroupList = s.Select(g => g.GroupId).ToList()
            }).ToList();

With in this group, I want to further split this by actual ItemDate and Duration so it looks like below

Basically, I want to split this group in to three in this case.

As only Group3 is having Date 15th to 17, it will be one group. From 17th to 22nd Group1, Group2 and Group3 are same. so that will become another group. And last only Group1 have 22nd to 24 so it become another group

Final grouped data to be like

G1
{
 ItemEntity :{
 ItemDate : 15/10/2018,
 Duration : 2,
 Field1 : "Item Name 1",
 Filed2 : "aaa",
 Field3 : "bbb",
    },
ItemList: {250},
GroupList:{3}
}

,
G2
{
 ItemEntity :{
 ItemDate : 17/10/2018,
 Duration : 5,
 Field1 : "Item Name 1",
 Filed2 : "aaa",
 Field3 : "bbb",
},
ItemList: {100,150,250},
GroupList:{1,2,3}
}
,
G3
{
 ItemEntity :{
 ItemDate : 22/10/2018,
 Duration : 2,
 Field1 : "Item Name 1",
 Filed2 : "aaa",
 Field3 : "bbb",
},
ItemList: {100},
GroupList:{1}
}

Answer 1

This was pretty challenging. I used some convenient extension methods I already had to make it easier, and created a HashSet subclass that defaults to using SetEqual (.Net really needs some member equal collection classes built-in).

First, the class HashSetEq that implements equality when its members match:

public class HashSetEq<T> : HashSet<T>, IEquatable<HashSetEq<T>> {
    private static readonly IEqualityComparer<HashSet<T>> SetEq = HashSet<T>.CreateSetComparer();

    public override int GetHashCode() => SetEq.GetHashCode(this);
    public override bool Equals(object obj) => obj != null && (obj is HashSetEq<T> hs) && this.Equals(hs);
    public bool Equals(HashSetEq<T> other) => SetEq.Equals(this, other);

    public HashSetEq(IEnumerable<T> src) : base(src) {
    }
}

Now, some extensions to IEnumerable. One extension converts an IEnumerable to a HashSetEq for ease of creating a collection of keys. The other extension is a variation on GroupBy that groups while a predicate is true, based on an extension ScanPair that implements a pair-wise version of the APL Scan operator.

public static class IEnumerableExt {
    public static HashSetEq<T> ToHashSetEq<T>(this IEnumerable<T> src) => new HashSetEq<T>(src);


    // TKey combineFn((TKey Key, T Value) PrevKeyItem, T curItem):
    // PrevKeyItem.Key = Previous Key
    // PrevKeyItem.Value = Previous Item
    // curItem = Current Item
    // returns new Key
    public static IEnumerable<(TKey Key, T Value)> ScanPair<T, TKey>(this IEnumerable<T> src, TKey seedKey, Func<(TKey Key, T Value), T, TKey> combineFn) {
        using (var srce = src.GetEnumerator()) {
            if (srce.MoveNext()) {
                var prevkv = (seedKey, srce.Current);

                while (srce.MoveNext()) {
                    yield return prevkv;
                    prevkv = (combineFn(prevkv, srce.Current), srce.Current);
                }
                yield return prevkv;
            }
        }
    }

    public static IEnumerable<IGrouping<int, T>> GroupByWhile<T>(this IEnumerable<T> src, Func<T, T, bool> testFn) =>
        src.ScanPair(1, (kvp, cur) => testFn(kvp.Value, cur) ? kvp.Key : kvp.Key + 1)
           .GroupBy(kvp => kvp.Key, kvp => kvp.Value);
}

In order to group the spans of dates, I expanded my GroupBySequential based on GroupByWhile inline so I could group by sequential date runs and matching sets of GroupIds. GroupBySequential depends on an integer sequence, so I need a base Date to compute a day sequence number so I use the earliest date in all the items:

var baseDate = items.Min(i => i.ItemDate);

Now I can compute the answer.

For each group of items, I expand each item out across all the dates it covers, based on Duration, and associated each date with the original item:

var group = items.GroupBy(g => new {
    g.Field1,
    g.Filed2,
    g.Field3
})
.Select(g => g.SelectMany(i => Enumerable.Range(0, i.Duration).Select(d => new { ItemDate = i.ItemDate.AddDays(d), i }))

Now that I have all the individual date+item, I can group them for each date.

              .GroupBy(di => di.ItemDate)

And then group each date+items on the date and set of groups for that date and order by the date.

              .GroupBy(dig => new { ItemDate = dig.Key, Groups = dig.Select(di => di.i.GroupId).ToHashSetEq() })
              .OrderBy(ig => ig.Key.ItemDate)

With them ordered by date, I can group the sequential dates together (using the number of days from the baseDate) that have the same Groups.

              .GroupByWhile((prevg, curg) => (int)(prevg.Key.ItemDate - baseDate).TotalDays + 1 == (int)(curg.Key.ItemDate - baseDate).TotalDays && prevg.Key.Groups.Equals(curg.Key.Groups))

Finally, I can extract the information from each sequential date group into a MasterEntity and make it the whole answer a List.

              .Select(igg => new MasterEntity {
                  Item = new ItemEntity {
                      ItemDate = igg.First().Key.ItemDate,
                      Duration = igg.Count(),
                      Field1 = g.Key.Field1,
                      Filed2 = g.Key.Filed2,
                      Field3 = g.Key.Field3
                  },
                  ItemList = igg.First().First().Select(di => di.i.ItemId).ToList(),
                  GroupList = igg.First().Key.Groups.ToList()
              })
)
.ToList();

Answer 2

https://dotnetfiddle.net/fFtqgy

Okay so the example contains 3 parties going to a "hotel" as given in your explanation. The groups are layed out below with the times the groups will arrive and depart from the hotel

Scenario

Group 1) 15th - 20th

Group 2) 17th - 19th

Group 3) 17th - 22nd

Result Groupings

15th - 17th: Group 1

17th - 19th: Groups 1, 2 , 3

19th - 20th: Groups 1, 3

20th - 22nd: Groups 3

Explanation

This depicts the groups that will be present in the hotel for each date, a new group is created each time a group joins or leaves the hotel, which is why the code joins all of the start and end dates for all of the groups and iterates through them.

I wasn't certain what to put for the GroupId and ItemID on the resulting MasterEntity since it contains a list of items and groups, so I've set it to negative 1 in the example

Code for fiddle

public static class Utilities
{

    public static bool DatesOverlap(DateTime aStart, DateTime aEnd, DateTime bStart, DateTime bEnd)
    {
        return aStart < bEnd && bStart < aEnd;
    }

    public static IList<MasterEntity> GroupFunky(IList<ItemEntity> list)
    {

        var result = new List<MasterEntity>();
        var ordered = list.OrderBy(x => x.ItemDate).ToArray();

        var startDates = list.Select(x => x.ItemDate);
        var endDates = list.Select(x => x.ItemDate.AddDays(x.Duration));

        var allDates = startDates.Concat(endDates).OrderBy(x => x).ToArray();

        for (var index = 0; index < allDates.Length - 1; index++)
        {
            var group = ordered.Where(x => DatesOverlap(allDates[index], allDates[index + 1], x.ItemDate,
                                                        x.ItemDate.AddDays(x.Duration)));


            var item = new ItemEntity
            {
                Duration = (allDates[index + 1] - allDates[index]).Days,
                ItemDate = allDates[index],
                Field1 = group.First().Field1,
                Field2 = group.First().Field2,
                Field3 = group.First().Field3,
                Field4 = group.First().Field4,
                GroupName = group.First().GroupName,
                ItemId = -1,
                GroupId = -1
            };
            item.ItemDate = allDates[index];
            item.Duration = (allDates[index + 1] - allDates[index]).Days;
            result.Add(new MasterEntity
            {
                Item = item,
                GroupList = group.Select(x => x.GroupId).ToList(),
                ItemList = group.Select(x => x.ItemId).ToList()
            });
        }

        return result.Where(x => x.Item.Duration > 0).ToList();
    }
}

public class ItemEntity
{
    public int ItemId { get; set; }
    public int GroupId { get; set; }
    public string GroupName { get; set; }
    public DateTime ItemDate { get; set; }
    public string Field1 { get; set; }
    public string Field2 { get; set; }
    public string Field3 { get; set; }
    public string Field4 { get; set; }
    public int Duration { get; set; }
}

public class MasterEntity
{
    public ItemEntity Item { get; set; }
    public List<int> ItemList { get; set; }
    public List<int> GroupList { get; set; }
}

public class TestClass
{

    public static void Main()
    {
        var items = new List<ItemEntity>
        {
            new ItemEntity
            {
                ItemId = 100,
                GroupId = 1,
                GroupName = "Group 1",
                ItemDate = new DateTime(2018, 10, 15),
                Duration = 5,
                Field1 = "Item Name 1",
                Field2 = "aaa",
                Field3 = "bbb",
                Field4 = "abc"
            },
            new ItemEntity
            {
                ItemId = 150,
                GroupId = 2,
                GroupName = "Group 2",
                ItemDate = new DateTime(2018, 10, 17),
                Duration = 2,
                Field1 = "Item Name 1",
                Field2 = "aaa",
                Field3 = "bbb",
                Field4 = "efg"
            },
            new ItemEntity
            {
                ItemId = 250,
                GroupId = 3,
                GroupName = "Group 3",
                ItemDate = new DateTime(2018, 10, 17),
                Duration = 5,
                Field1 = "Item Name 1",
                Field2 = "aaa",
                Field3 = "bbb",
                Field4 = "xyz"
            }
        };


        var group = items.GroupBy(g => new
        {
            g.Field1,
            g.Field2,
            g.Field3
        })
            .Select(x => x.AsQueryable().ToList())
            .ToList();

        var result = group.Select(x => Utilities.GroupFunky(x));

        foreach (var item in result)
        {
            Console.WriteLine(JsonConvert.SerializeObject(item, Formatting.Indented));
        }

    }
}