3
\$\begingroup\$

I have to list the number of documents related to items in a hierarchical tree.

The specification states: The tree will only ever be 2 levels deep. The higher level items will list not only the number of documents in it's folder, but also the total count of documents in the child folders. They want this total to include the documents in the current folder.

I've developed the solution below, it works, however it just seems complicated, hard to maintain and probably not the most efficient way to do this. Also, if the tree is ever more than 2 levels deep, this will fail.

class Item
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public int DocumentCount { get; set; }
    public int ChildItemCount { get; set; }
    public int ChildCount { get; set; }
}

static class Program
{
    static void Main()
    {
        var items = new List<Item>
        {
            new Item {Id = 1, ParentId = 0},
            new Item {Id = 2, ParentId = 1},
            new Item {Id = 3, ParentId = 1},
            new Item {Id = 4, ParentId = 2},
            new Item {Id = 5, ParentId = 2},
            new Item {Id = 6, ParentId = 3},
            new Item {Id = 7, ParentId = 3},
            new Item {Id = 8, ParentId = 3}
        };
        // setup
        var rnd = new Random();
        items.ForEach(c => c.DocumentCount = rnd.Next(1, 10));

        // act
        items.ForEach(z => z.ChildCount = items.Count(x => x.ParentId == z.Id));
        items.ForEach(z => z.ChildItemCount = items.Where(x => x.ParentId == z.Id).Sum(y => y.DocumentCount) + z.DocumentCount);
        items.Where(k => k.ParentId == 0).ToList().ForEach(z => z.ChildItemCount = items.Where(x => x.ParentId == z.Id).Sum(y => y.ChildItemCount) + z.DocumentCount);

        // output
        items.ForEach(i => Console.WriteLine("Id: {0}, ParentId: {1}, DocumentCount: {2}, ChildCount: {3}, ChildItemCount: {4}", i.Id, i.ParentId, i.DocumentCount,i.ChildCount, i.ChildItemCount));
        Console.ReadKey();
    }
}

This gives the output below which is technically correct and meets the spec, but I just feel the solution is not the best solution. Can anyone think of a better way to do this?

Id: 1, ParentId: 0, DocumentCount: 8, ChildCount: 2, ChildItemCount: 46
Id: 2, ParentId: 1, DocumentCount: 7, ChildCount: 2, ChildItemCount: 16
Id: 3, ParentId: 1, DocumentCount: 8, ChildCount: 3, ChildItemCount: 22
Id: 4, ParentId: 2, DocumentCount: 2, ChildCount: 0, ChildItemCount: 2
Id: 5, ParentId: 2, DocumentCount: 7, ChildCount: 0, ChildItemCount: 7
Id: 6, ParentId: 3, DocumentCount: 9, ChildCount: 0, ChildItemCount: 9
Id: 7, ParentId: 3, DocumentCount: 1, ChildCount: 0, ChildItemCount: 1
Id: 8, ParentId: 3, DocumentCount: 4, ChildCount: 0, ChildItemCount: 4
\$\endgroup\$
4
\$\begingroup\$

You can create lookup for children. That will involve single enumeration over items collection instead of enumerating all items for each calculation of each item.

I.e. you currently have 2 * N * N iterations for calculating child count and child item count. With lookup you will have N + N + N iterations

var children = items.ToLookup(i => i.ParentId);

foreach(var item in items) 
{
    var subitems = children[item.Id];
    item.ChildCount = subitems.Count();
    item.ChildItemCount = subitems.Sum(i => i.DocumentCount) + item.DocumentCount;
}

Explanation: Let's look on this line

items.ForEach(z => z.ChildItemCount = 
    items.Where(x => x.ParentId == z.Id).Sum(y => y.DocumentCount) + z.DocumentCount);

Here for each item in items collection you enumerate every item in items collection to get only items which are children of current. That gives you N * N iterations totally. Count is calculated same way.

Now lets look on my code.

var children = items.ToLookup(i => i.ParentId);

Here lookup is created. Internally it looks like enumerating over items and adding them to appropriate groupings of lookup. You can think of lookup as a Dictionary<TKey, List<TValue>>.

Next we do enumerating of all items (that's another N). In body of this loop we get children of item (getting appropriate group by key is pretty fast O(1) operation, comparing to enumerating all items and filtering them). Good news here is behavior of lookup when key not found - it simply returns EmptyEnumerable (i.e. empty array of TValue), so we don't need to check anything - further calculations will work without problems:

foreach(var item in items)
{
    var subitems = children[item.Id];
    // ...
}

Next we do two operations. First is getting count of items in group. Grouping implements ICollection with Count property, and it simply returns count of items in group, without enumerating them:

item.ChildCount = subitems.Count();

Second operation is calculating sum of documents in group. Thus total number of items in all groups will be N then enumerating all groups will take N iterations:

item.ChildItemCount = subitems.Sum(i => i.DocumentCount) + item.DocumentCount;

UPDATE: Thus you want ChildItemCount to contain sum

\$\endgroup\$
  • \$\begingroup\$ Hi Sergey, while I like how your solution is cleaner and an improvement, it fails to give the correct solution for the highest level. (item id 1) a second foreach would be needed to calculate this value, which gives the same number of iterations as my solution. Your solution is definitely easier to understand. \$\endgroup\$ – Nigel Joyce May 20 '14 at 23:42
  • \$\begingroup\$ @NigelJoyce just verified - it returns correct value for top-level item - 2 children and correct total documents value \$\endgroup\$ – Sergey Berezovskiy May 20 '14 at 23:54
  • \$\begingroup\$ using your solution, Id: 1, PId: 0, DC: 1, CC: 2, CIC: 9 Id: 2, PId: 1, DC: 5, CC: 2, CIC: 19 Id: 3, PId: 1, DC: 3, CC: 3, CIC: 7 Id: 4, PId: 2, DC: 5, CC: 0, CIC: 5 Id: 5, PId: 2, DC: 9, CC: 0, CIC: 9 Id: 6, PId: 3, DC: 1, CC: 0, CIC: 1 Id: 7, PId: 3, DC: 2, CC: 0, CIC: 2 Id: 8, PId: 3, DC: 1, CC: 0, CIC: 1 Item Id: 1 should actually be 27 (19 + 7 + 1) I think it's close, but not quite there. \$\endgroup\$ – Nigel Joyce May 21 '14 at 0:07
  • \$\begingroup\$ @NigelJoyce can you explain in words what should be value of CIC? If it should be sum of subitems CIC + DC, then you should do two things - enumerate items in their parent ids descending order, and use CIC when calculating sum. I.e. foreach (var item in items.OrderByDescending(i => i.ParentId)) and item.ChildItemCount = subitems.Sum(i => i.ChildItemCount) + item.DocumentCount; Sorry, its too late here, will be back in 7 hours \$\endgroup\$ – Sergey Berezovskiy May 21 '14 at 0:27
  • \$\begingroup\$ The OrderByDecending is part of the solution. item.ChildItemCount = subitems.Sum(i => i.DocumentCount) + item.DocumentCount; needs to be changed to item.ChildItemCount = subitems.Sum(i => i.ChildItemCount) + item.DocumentCount; \$\endgroup\$ – Nigel Joyce May 21 '14 at 0:31
2
\$\begingroup\$

@Sergey's answer does a beautiful job at flattening your solution's complexity; this is more of a style review.

Your lambda parameters are arbitrarily named:

items.ForEach(z => z.ChildCount = items.Count(x => x.ParentId == z.Id));

Consider giving a somewhat meaningful name to these identifiers:

items.ForEach(item => item.ChildCount = items.Count(child => child.ParentId == item.Id));

Better naming and proper whitespace make it easier to read your code; you didn't need to come up with y, it's in a scope that's a sibling of that of x, but it's harder to tell when everything is on one line:

items.ForEach(z => z.ChildItemCount = items.Where(x => x.ParentId == z.Id).Sum(y => y.DocumentCount) + z.DocumentCount);

Breaking the line and lining up the dots makes it easier to see the scopes created (and iterations), at a glance:

items.ForEach(item => item.ChildItemCount = items.Where(child => child.ParentId == item.Id)
                                                 .Sum(child => child.DocumentCount) + item.DocumentCount);
\$\endgroup\$
  • \$\begingroup\$ Ah, yes you are right about y being a sibling of x. I missed that. The production code has meaningful names, I just used single letter parameters for the example code. Maybe that's why I missed the scope issue :) \$\endgroup\$ – Nigel Joyce May 21 '14 at 3:29
  • \$\begingroup\$ Another good reason to post your real code on this site ;) \$\endgroup\$ – Mathieu Guindon May 21 '14 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.