Collect members from custom tree nodes

Question

In my program, I have a tree of Group nodes, each identified by their ImportId.

Each group has zero or more members, that I want to collect.

Each group has zero or more child groups, referenced by their importId, whose members should be added to the collection.

Each group has zero or more RuleParts.

Each rulePart is a collection of zero or more groups, referenced by their importId, whose members should be added or removed to the collection, depending on a boolean value Negated on each rulePart.

I got the following code working:

internal class RulePartTraverser
{
 public List<string> GetRulePartMembers(IReadOnlyList<RulePart> ruleParts, IReadOnlyList<Group> allGroups)
 {
 if (ruleParts is null || !ruleParts.Any() || allGroups is null || !allGroups.Any())
 {
 return new List<string>();
 }
 var positiveRuleParts = collectRulePartMembers(ruleParts.Where(rp => !rp.Negated), allGroups);
 var negativeRuleParts = collectRulePartMembers(ruleParts.Where(rp => rp.Negated), allGroups);
 return positiveRuleParts.Except(negativeRuleParts).ToList();
 }
 private IEnumerable<string> collectRulePartMembers(IEnumerable<RulePart> ruleParts, IReadOnlyList<Group> allGroups)
 {
 var members = ruleParts.Aggregate(
 seed: new List<string>().AsEnumerable(),
 (current, rp) => current.Union(collectIndirectMembers(rp.RulePartMemberImportIds, allGroups)));
 return members;
 }
 private IEnumerable<string> collectIndirectMembers(List<string> indirectGroupImportIds, IReadOnlyList<Group> allGroups)
 {
 var returnList = indirectGroupImportIds.Aggregate(
 seed: new List<string>().AsEnumerable(),
 (current, importId) =>
 {
 var correspondingGroup = allGroups.Single(ag => ag.ImportId == importId);
 return current.Union(GetRulePartMembers(correspondingGroup.RuleParts, allGroups))
 .Union(collectIndirectMembers(correspondingGroup.Children, allGroups))
 .Union(correspondingGroup.Members);
 });
 return returnList;
 }
}
public class RulePart
{
 public bool Negated { get; set; }
 public List<string> RulePartMemberImportIds { get; set; }
}
public class Group
{
 public string ImportId { get; set; }
 public string Name { get; set; }
 public List<string> Children { get; set; }
 public List<string> Members { get; set; }
 public List<RulePart> RuleParts { get; set; }
}

The above method accepts a list of ruleParts for a given group and a list of all groups.

Some sanity checks are performed and if they fail, an empty list is returned.

It then collects all members of all ruleParts that are not negated, then collects all members of all ruleParts that are negated and substracts the latter from the former. The resulting collection is returned.

In order to collect all members of a single rulePart, all rulePartMembers are inspected and all the members of the corresponding groups are collected.

To collect all members of a given single group, I recursively collect all members of the corresponding ruleParts; then I recursively add the members of all child groups, potentially collecting the members of this child group's ruleParts and this child group's children. Finally I add all direct members of the group and step up.

Due to the nature of my data structure, I fear that this is the best I can do. However, is it possible (or sensible) to replace the recursion by an iteration? Are there other things I could or should improve?

---

The following example is not too far away from a real case scenario, I hope it helps in explaining the data structure:

 var rootGroup = new Group
 {
 ImportId = "Root",
 Members = new List<string>(),
 Children = new List<string>(),
 RuleParts = new List<RulePart>
 {
 new RulePart{Negated = false, RulePartMemberImportIds = new List<string>{ "group01", "group02" } }, //add all members of groups group01 and group02 to the collection
 new RulePart{Negated = true, RulePartMemberImportIds = new List<string>{"group03", "group04"}} //but remove all members of groups group03 and group04
 }
 };
 var group01 = new Group
 {
 ImportId = "group01",
 Members = new List<string>(),
 Children = new List<string>(),
 RuleParts = new List<RulePart>
 {
 new RulePart{Negated = false, RulePartMemberImportIds = new List<string>{"group05"}}, //add all members of group05
 new RulePart{Negated = true, RulePartMemberImportIds = new List<string>{"group06"}} //remove all members of group06
 }
 };
 var group02 = new Group
 {
 ImportId = "group02",
 Members = new List<string> { "member01", "member04", "member05" },
 Children = new List<string>(),
 RuleParts = new List<RulePart>()
 };
 var group03 = new Group
 {
 ImportId = "group03",
 Members = new List<string> { "member06", "member07", "member09" },
 Children = new List<string>(),
 RuleParts = new List<RulePart>()
 };
 var group04 = new Group
 {
 ImportId = "group04",
 Members = new List<string> { "member09", "member10", "member11" },
 Children = new List<string>(),
 RuleParts = new List<RulePart>()
 };
 var group05 = new Group
 {
 ImportId = "group05",
 Members = new List<string>(),
 Children = new List<string> { "group07", "group08" }, //add all members of groups group07 and group08
 RuleParts = new List<RulePart>()
 };
 var group06 = new Group
 {
 ImportId = "group06",
 Members = new List<string> { "member02" },
 Children = new List<string>(),
 RuleParts = new List<RulePart>()
 };
 var group07 = new Group
 {
 ImportId = "group07",
 Members = new List<string> { "member12" },
 Children = new List<string>(),
 RuleParts = new List<RulePart>()
 };
 var group08 = new Group
 {
 ImportId = "group08",
 Members = new List<string>(),
 Children = new List<string> { "group04" }, //add all members of group04
 RuleParts = new List<RulePart>()
 };
 var expectedMembers = new List<string> { "member01", "member04", "member05", "member12" };

The rule parts of the RootGroup would serve as input to GetRulePartMembers.

In order to collect the members of the different rule parts, first the members of groups group01 - group04 have to be determined.

For group01, this means determining the members of the ruleparts of group01, ie determining the members of groups group05 and group06, as these are ruleparts of group01.

As group05 has child groups, the members of group05 is the union of the members of groups group07 and group08, group08 has a single child group group04, so the members of group08 are the members of group04, yielding member09, member10, member11 for group08, resulting in member09, member10, member11, member12 for group05.

The single member of group06 is member02, removing it from the result collection of group05 results in the collection member09, member10, member11, member12 for group01.

For group02, the members are directly member01, member04, member05, which results in the member collection member01, member04, member05, member09, member10, member11, member12 for the non-negated rulepart of the RootGroup.

For the negated rulepart of the RootGroup, the members of group03 and group04 can directly be added to the result collection, as neither of the groups have children or ruleparts. This results in member06, member07, member09, member10, member11 for the negated rulepart.

These members are then removed from the collection of members for the non-negated rulepart, yielding the final result of member01, member04, member05, member12 for the RootGroup.

Answer 1

Just a couple of tipps...

---

if (ruleParts is null || !ruleParts.Any() || allGroups is null || !allGroups.Any())

This sanity checks would be a big surprise for me because null is virtually never a valid value so this method should throw if any parameter is null.

Having checked for nulls it's not necessary to also check them for Any. The queries wouldn't return anything anyway in this case so just let them do the job.

---

 var positiveRuleParts = collectRulePartMembers(ruleParts.Where(rp => !rp.Negated), allGroups);
 var negativeRuleParts = collectRulePartMembers(ruleParts.Where(rp => rp.Negated), allGroups);

You don't have to iterate ruleParts twice. Instead use ToLookup

var rulePartsLookup = ruleParts.ToLookup(x => x.Negated);

and get the values with

collectRulePartMembers(rulePartsLookup[false], allGroups);
collectRulePartMembers(rulePartsLookup[true], allGroups);

---

new List<string>().AsEnumerable()

It's more natural to use Enumerable.Empty<string>() than creating an empty list and turn it into an enumerable anyway.

---

I cannot comment on the recursion because I am not able to visualize it without an example.

• Thaoden: Thanks, I have incorporated your tips. What is the practice on CodeReview regarding code changes in the original question? I have also added an example of some groups and ruleparts and the expected outcome of the recursion, along with an explanation how to determine the result.
• t3chb0t: @Thaoden You did the right thing by not chaniging the original code ;-) it's not allowed after reviews have been posted. Adding an additional example is a great help too. If you want to share your new code you can post a self-answer or a follow-up if you'd like to have more feedback. There is, however, a catch when posting a self-answer - this needs to be described too - code-only answers are off-topic.

Answer 2

If a Member can be owned by more groups that can correspond to RuleParts that can be either Negated or not, and that the Negated ownership take precedence over !Negated, I understand your code:

public IEnumerable<string> GetRulePartMembers2(IEnumerable<RulePart> ruleParts, IEnumerable<Group> allGroups)
{
 IEnumerable<string> ExtractMembers(IEnumerable<RulePart> partialRuleParts, bool negated)
 {
 return partialRuleParts
 .Where(rp => rp.Negated == negated)
 .SelectMany(rp => rp.RulePartMemberImportIds)
 .SelectMany(importId =>
 {
 Group group = allGroups.Single(g => g.ImportId == importId);
 var children = allGroups.Where(g => group.Children.Contains(g.ImportId));
 return group
 .Members
 .Union(ExtractMembers(group.RuleParts, negated)
 .Union(ExtractMembers(children.SelectMany(sg => sg.RuleParts), negated)))
 .Union(children.SelectMany(sg => sg.Members));
 });
 }
 return ExtractMembers(ruleParts, false).Except(ExtractMembers(ruleParts, true)); 
}

If I test against your solution in the following way, I get the same result. I assume that the initial list of RuleParts is the gross list of all:

 var groups = new[]
 {
 rootGroup,
 group01,
 group02,
 group03,
 group04,
 group05,
 group06,
 group07,
 group08,
 };
 var ruleParts = rootGroup.RuleParts; //groups.SelectMany(g => g.RuleParts).ToList();
 var expectedMembers = new List<string> { "member01", "member04", "member05", "member12" };
 RulePartTraverser traverser = new RulePartTraverser();
 Console.WriteLine(string.Join(", ", traverser.GetRulePartMembers(ruleParts, groups).OrderBy(m => m)));
 Console.WriteLine(string.Join(", ", traverser.GetRulePartMembers2(ruleParts, groups).OrderBy(m => m)));

I'm not convinced that my solution is more readable and clear than the yours - any more.

---

Update:

In order to only iterate the rule parts once for both Negated and !Negated the following could be a solution:

public IEnumerable<string> GetRulePartMembers2(Group rootGroup, IEnumerable<Group> allGroups)
{
 List<string> positiveMembers = new List<string>();
 List<string> negativeMembers = new List<string>();
 void AddMembers(RulePart rulePart, Group group)
 {
 if (rulePart.Negated)
 negativeMembers.AddRange(group.Members);
 else
 positiveMembers.AddRange(group.Members);
 }
 void ExtractMembers(IEnumerable<RulePart> partialRuleParts)
 {
 foreach (RulePart rulePart in partialRuleParts)
 {
 foreach (Group group in allGroups.Where(g => rulePart.RulePartMemberImportIds.Contains(g.ImportId)))
 {
 AddMembers(rulePart, group);
 ExtractMembers(group.RuleParts);
 foreach (Group childGroup in allGroups.Where(cg => group.Children.Contains(cg.ImportId)))
 {
 // This is the only thing that is not obvious: 
 // The members of a child group are added according to the rulePart of its parent?
 AddMembers(rulePart, childGroup);
 ExtractMembers(childGroup.RuleParts);
 }
 }
 }
 }
 ExtractMembers(rootGroup.RuleParts);
 return positiveMembers.Except(negativeMembers);
}

• Thaoden: Exactly, a member can be part of multiple groups, that can in turn each be part of multiple ruleparts, that in turn can be negated or not. Additionally, each group can be part of another groups children. I'm not sure I understand what is happening in your ExtractMembers method though, how would I incorporate the childgroups there?
• user73941: @Thaoden: see my update...
• Thaoden: Not exactly, the initial list of ruleParts to start is only the ruleParts of the RootGroup - at least that was my initial intention. So basically you go through the list of all ruleparts twice, collecting all non-negated and all negated members and removing the negated from the non-negated - I'm not sure this would yield the same result for all cases, I would have to think of a counter-example though...
• user73941: @Thaoden: OK, it seems to work with just rootGroup.RuleParts as initial list of RuleParts, and you can optimize it, as my edit show. But don't waste time on my suggestion, I was just trying to understand your problem and it doesn't seem to make anything clearer :-)
• Thaoden: The members of a child group are added unconditionally. Thanks for your input, I especially like the fact that these are local functions, so I don't have to pass all the references around.