How can I use "Linq to Objects" to put a set of contiguous dates in one group?

Question

I have a troublesome query to write. I'm currently writing some nasty for loops to solve it, but I'm curious to know if Linq can do it for me.

I have:

struct TheStruct
{
 public DateTime date {get; set;} //(time portion will always be 12 am)
 public decimal A {get; set;}
 public decimal B {get; set;}
}

and a list that contains these structs. Let's say it's ordered this way:

List<TheStruct> orderedList = unorderedList.OrderBy(x => x.date).ToList();

If you put the orderedList struct dates in a set they will always be contiguous with respect to the day.. that is if the latest date in the list was 2011/01/31, and the earliest date in the list was 2011/01/01, then you'd find that the list would contain 31 items, one for each date in January.

Ok, so what I want to do is group the list items such that:

1. Each item in a group must contain the same Decimal A value and the same Decimal B value
2. The date values in a group must form a set of contiguous dates, if the date values were in order
3. If you summed up the sums of items in each group, the total would equal the number of items in the original list (or you could say a struct with a particular date can't belong to more than one group)

Any Linq masters know how to do this one?

Thanks!

Answer 1

You can group adjacent items in a sequence using the GroupAdjacent Extension Method (see below):

var result = unorderedList
    .OrderBy(x => x.date)
    .GroupAdjacent((g, x) => x.A == g.Last().A && 
                             x.B == g.Last().B && 
                             x.date == g.Last().date.AddDays(1))
    .ToList();

Example:

(1,1) 2011-01-01   \
(1,1) 2011-01-02    >  Group 1
(1,1) 2011-01-03 __/
(2,1) 2011-01-04   \
(2,1) 2011-01-05    >  Group 2
(2,1) 2011-01-06 __/
(1,1) 2011-01-07   \
(1,1) 2011-01-08    >  Group 3
(1,1) 2011-01-09 __/
(1,1) 2011-02-01   \
(1,1) 2011-02-02    >  Group 4
(1,1) 2011-02-03 __/

Extension Method:

static IEnumerable<IEnumerable<T>> GroupAdjacent<T>(
    this IEnumerable<T> source, Func<IEnumerable<T>, T, bool> adjacent)
{
    var g = new List<T>();
    foreach (var x in source)
    {
        if (g.Count != 0 && !adjacent(g, x))
        {
            yield return g;
            g = new List<T>();
        }
        g.Add(x);
    }
    yield return g;
}

Answer 2

Here is an entry for "Most Convoluted way to do this":

public static class StructOrganizer
{
    public static IEnumerable<Tuple<Decimal, Decimal, IEnumerable<MyStruct>>> OrganizeWithoutGaps(this IEnumerable<MyStruct> someStructs)
    {
        var someStructsAsList = someStructs.ToList();
        var lastValuesSeen = new Tuple<Decimal, Decimal>(someStructsAsList[0].A, someStructsAsList[0].B);
        var currentList = new List<MyStruct>();
        return Enumerable
            .Range(0, someStructsAsList.Count)
            .ToList()
            .Select(i =>
                        {
                            var current = someStructsAsList[i];
                            if (lastValuesSeen.Equals(new Tuple<Decimal, Decimal>(current.A, current.B)))
                                currentList.Add(current);
                            else
                            {
                                lastValuesSeen = new Tuple<decimal, decimal>(current.A, current.B);
                                var oldList = currentList;
                                currentList = new List<MyStruct>(new [] { current });
                                return new Tuple<decimal, decimal, IEnumerable<MyStruct>>(lastValuesSeen.Item1, lastValuesSeen.Item2, oldList);
                            }
                            return null;
                        })
            .Where(i => i != null);
    }

    // To Test:
    public static void Test()
    {
        var r = new Random();

        var sampleData = Enumerable.Range(1, 31).Select(i => new MyStruct {A = r.Next(0, 2), B = r.Next(0, 2), date = new DateTime(2011, 12, i)}).OrderBy(s => s.date).ToList();
        var sortedData = sampleData.OrganizeWithoutGaps();

        Console.Out.WriteLine("Sample Data:");
        sampleData.ForEach(s => Console.Out.WriteLine("{0} = ({1}, {2})", s.date, s.A, s.B));
        Console.Out.WriteLine("Output:");
        sortedData.ToList().ForEach(s => Console.Out.WriteLine("({0}, {1}) = {2}", s.Item1, s.Item2, String.Join(", ", s.Item3.Select(st => st.date))));
    }
}

Answer 3

If I understood you well, a simple Group By would do the trick:

var orderedList = unorderedList.OrderBy(o => o.date).GroupBy(s => new {s.A, s.B});

Just that. To print the results:

      foreach (var o in orderedList) {                 
            Console.WriteLine("Dates of group {0},{1}:", o.Key.A, o.Key.B);
            foreach(var s in o){
                Console.WriteLine("\t{0}", s.date);
            }
        }

The output would be like:

Dates of group 2,3:
    02/12/2011
    03/12/2011
Dates of group 4,3:
    03/12/2011
Dates of group 1,2:
    04/12/2011
    05/12/2011
    06/12/2011

Hope this helps. Cheers