Nested grouping strategy/algorithm c#

Question

Not sure if I have to correct label for this type of problem, but do you have any thoughts on a generic solution for the following?

Given a collection of Invoices:

var invoices = new List<Invoice>()
{
new Invoice() { Id = 1, Customer = "a", Date = DateTime.Parse("1/1/2009") },
new Invoice() { Id = 2, Customer = "a", Date = DateTime.Parse("1/2/2009") },
new Invoice() { Id = 3, Customer = "a", Date = DateTime.Parse("1/2/2009") },
new Invoice() { Id = 4, Customer = "b", Date = DateTime.Parse("1/1/2009") },
new Invoice() { Id = 5, Customer = "b", Date = DateTime.Parse("1/1/2009") },
new Invoice() { Id = 6, Customer = "b", Date = DateTime.Parse("1/2/2009") }
}

What technique can I use where specifying something like:

var tree = invoices.ToHeirarchy(t => {
    t.GroupBy(x => x.Date);
    t.GroupBy(x => x.Customer);
})

Results in a graph like:

Date "1/1/2009"
  Customer a
    Invoice 1
  Customer b
    Invoice 4
    Invoice 5
Date "1/2/2009"
  Customer a
    Invoice 2
    Invoice 3
  Customer b
    Invoice 6

And also allows the following to pass (allowing for calculations on the invoices from any level)?

Assert.AreEqual(3, tree.Node[0].Items.Count)
Assert.AreEqual(DateTime.Parse("1/1/2009"), tree.Node[0].Key)

Assert.AreEqual(3, tree.Node[1].Items.Count)
Assert.AreEqual(DateTime.Parse("1/2/2009"), tree.Node[1].Key)

Assert.AreEqual("a", tree.Node[0].Node[0].Key)
Assert.AreEqual(1, tree.Node[0].Node[0].Items.Count)

Assert.AreEqual("b", tree.Node[0].Node[1].Key)
Assert.AreEqual(2, tree.Node[0].Node[1].Items.Count)

Answer 1

Instead of a tree, you could sort the results by Date & then by Customer.

Answer 2

Far from being reusable but this should do it:

       var tree = invoices.GroupBy(x => x.Date).Select(x => new
            {
                Key = x.Key,
                Items = x.GroupBy(y => y.Customer).Select(y => new
                    {
                        Key = y.Key,
                        Items = y.Select(z => z.Id).ToList()
                    })
            }).ToList();

Answer 3

The term you're looking for is a "nested groupby".

http://msdn.microsoft.com/en-us/vcsharp/aa336754.aspx#nested

Answer 4

You need a type that is capable of representing the tree structure. There are some types in the framework that could be used - for example KeyValuePair<TKey, TValue>, the tree view node TreeNode, XML elements XmlElement and XElement, and probably some more. The following example contains two solutions using XElement to represent the tree. One uses lambdas to access the members, the other uses strings and both have pros and cons. I assume it is possible to get the best from solutions with complexer code.

static void Main()
{
    IEnumerable<Invoice> invoices = new List<Invoice>()
    { 
        new Invoice() { Id = 1, Customer = "a", Date = DateTime.Parse("1/1/2009") },
        new Invoice() { Id = 2, Customer = "a", Date = DateTime.Parse("1/2/2009") }, 
        new Invoice() { Id = 3, Customer = "a", Date = DateTime.Parse("1/2/2009") }, 
        new Invoice() { Id = 4, Customer = "b", Date = DateTime.Parse("1/1/2009") }, 
        new Invoice() { Id = 5, Customer = "b", Date = DateTime.Parse("1/1/2009") }, 
        new Invoice() { Id = 6, Customer = "b", Date = DateTime.Parse("1/2/2009") } 
    };


    StringBuilder sb = new StringBuilder();
    TextWriter tw = new StringWriter(sb);

    using (XmlWriter xmlWriter = new XmlTextWriter(tw) { Formatting = Formatting.Indented })
    {

        XElement t1 = new XElement("Root", BuildTree(invoices, i => i.Customer, i => i.Date, i => i.Id));
        XElement t2 = new XElement("Root", BuildTree(invoices, "Customer", "Date", "Id"));

        var xyz = t2.Elements("Customer").ElementAt(1).Descendants("Item").Count();

        t1.WriteTo(xmlWriter);
        t2.WriteTo(xmlWriter);
    }

    Console.WriteLine(sb.ToString());

    Console.ReadLine();
}

public static IEnumerable<XElement> BuildTree<T>(IEnumerable<T> collection, params Func<T, Object>[] groups)
{
    if ((groups != null) && (groups.Length > 0))
    {
        return collection
            .GroupBy(groups[0])
            .Select(grp => new XElement(
                "Group",
                new XAttribute("Value", grp.Key),
                BuildTree(grp, groups.Skip(1).ToArray())));
    }
    else
    {
        return collection.Select(i => new XElement("Item"));
    }
}

public static IEnumerable<XElement> BuildTree<T>(IEnumerable<T> collection, params String[] groups)
{
    if ((groups != null) && (groups.Length > 0))
    {
        return collection
            .GroupBy(i => typeof(T).GetProperty(groups[0]).GetValue(i, null))
            .Select(grp => new XElement(
                groups[0],
                new XAttribute("Value", grp.Key),
                BuildTree(grp, groups.Skip(1).ToArray())));
    }
    else
    {
        return collection.Select(i => new XElement("Item"));
    }
}

The ouput for the first solution is the following.

<Root>
  <Group Value="a">
    <Group Value="2009-01-01T00:00:00">
      <Group Value="1">
        <Item />
      </Group>
    </Group>
    <Group Value="2009-02-01T00:00:00">
      <Group Value="2">
        <Item />
      </Group>
      <Group Value="3">
        <Item />
      </Group>
    </Group>
  </Group>
  <Group Value="b">
    <Group Value="2009-01-01T00:00:00">
      <Group Value="4">
        <Item />
      </Group>
      <Group Value="5">
        <Item />
      </Group>
    </Group>
    <Group Value="2009-02-01T00:00:00">
      <Group Value="6">
        <Item />
      </Group>
    </Group>
  </Group>
</Root>

The second solution yields the following.

<Root>
  <Customer Value="a">
    <Date Value="2009-01-01T00:00:00">
      <Id Value="1">
        <Item />
      </Id>
    </Date>
    <Date Value="2009-02-01T00:00:00">
      <Id Value="2">
        <Item />
      </Id>
      <Id Value="3">
        <Item />
      </Id>
    </Date>
  </Customer>
  <Customer Value="b">
    <Date Value="2009-01-01T00:00:00">
      <Id Value="4">
        <Item />
      </Id>
      <Id Value="5">
        <Item />
      </Id>
    </Date>
    <Date Value="2009-02-01T00:00:00">
      <Id Value="6">
        <Item />
      </Id>
    </Date>
  </Customer>
</Root>

This solutions are far from perfect but might offer something to start with and they give the full power of LINQ to XML for querying the tree. If you are going to use this trees heavily, I suggest to build a custome node type for the tree that better fits the needs. But it will probably be quite hard to design this - esspecially if you want strong typing.

Finally I want to mention that I can not really see the use of such an structure - wouldn't it be much easyer to use LINQ to object to obtain the results directly from the list?

Answer 5

I haven't tested it but I think eulerfx's proposed answer is in the right direction. Below I've written my own solution for this type of thing in LINQ comprehension syntax.

var tree =
    (from i in invoices
    group i by i.Date into g1
    select new
    {
     Key = g1.Key,
     Items =
      (from d in g1
      group d by d.Customer into g2
      select new
      {
       Key = g2.Key,
       Items =
        from d in g2
        select new
        {
         Key = d.Id,
        }
      }).ToList()
    }).ToList();

The ToList() calls are really optional depending on what your trying to achieve in your projection.

Recently I've asked a similar question and it appears that I may be answering it myself. Please take it look if you think it may help understand other options with regard to grouping with linq to create hierarchies.