CODEWITHSUNDEEP
c#.netlinqforeach
Suraj Nair
Suraj Nair

Reputation: 561

Filter hierarchical list retaining parent using LINQ

I have a model class which looks something like this:

public class Employee
{ 
    public int Id {get;set;}
    public int ParentId {get;set;}
    public string Name{get;set;}
    public string Designation {get;set;}
}

using which I simulated a list:

new List<Employee> employees
{
    new Employee{Id = 1, ParentId = 0, Name = "A", Designation = "CEO" },
    new Employee{Id = 2, ParentId = 1, Name = "B", Designation = "Manager" },
    new Employee{Id = 3, ParentId = 1, Name = "C", Designation = "Manager" },
    new Employee{Id = 4, ParentId = 2, Name = "D", Designation = "Lead" },
    new Employee{Id = 5, ParentId = 3, Name = "E", Designation = "Lead" },
    new Employee{Id = 6, ParentId = 4, Name = "F", Designation = "Developer" },
    new Employee{Id = 7, ParentId = 4, Name = "G", Designation = "Developer" },
    new Employee{Id = 8, ParentId = 5, Name = "H", Designation = "Developer" }
};

Well I need to write a LINQ query to filter the above list so that even the parent objects(if present) are retained during the filtering. I could not quiet wrap my head around the retainment of the parent part where I always end up getting it wrong.

To make it more clear this is what is the expected filtered list in case the filter search criteria are the Ids 6 and 7:

{
    new Employee{Id = 1, ParentId = 0, Name = "A", Designation = "CEO" },
    new Employee{Id = 2, ParentId = 1, Name = "B", Designation = "Manager" },
    new Employee{Id = 4, ParentId = 2, Name = "D", Designation = "Lead" }
    new Employee{Id = 6, ParentId = 4, Name = "F", Designation = "Developer" },
    new Employee{Id = 7, ParentId = 4, Name = "G", Designation = "Developer" }
}

and if the Id to filter is 8:

{
    new Employee{Id = 1, ParentId = 0, Name = "A", Designation = "CEO" },
    new Employee{Id = 3, ParentId = 1, Name = "C", Designation = "Manager" },
    new Employee{Id = 5, ParentId = 3, Name = "E", Designation = "Lead" },
    new Employee{Id = 8, ParentId = 5, Name = "H", Designation = "Developer" }
}

and if the Id to filter is 2:

{
    new Employee{Id = 1, ParentId = 0, Name = "A", Designation = "CEO" },
    new Employee{Id = 2, ParentId = 1, Name = "B", Designation = "Manager" }
}

Upvotes: 0

Views: 319

Answers (2)

Classe
Classe

Reputation: 256

As some comments seem to be quite... Subjective... Here is a simple (but somewhat inefficient) extension that handles your requirements like a charm: (assuming you'll never hire an employee as a boss to another employee that in turn is their boss, but such madness would probably break the company quicker than it breaks the query)

    public static IEnumerable<Employee> FindByIdsAndIncludeParents(this IEnumerable<Employee> employees, params int[] targetIds)
        => employees
            .Where(r => targetIds.Contains(r.Id))
            .SelectMany(r => employees.FindByIdsAndIncludeParents(r.ParentId).Append(r))
        .Distinct();

As some are not quite as keen of exchanging this quite expensive operation for the mere beauty of it, we could trade in some beauty for speed using a dictionary as entry point for instant access to the appended boss-search:

    public static IEnumerable<Employee> FindFriendsFaster(this IEnumerable<Employee> employees, params int[] targetIds) 
        => employees
            .ToDictionary(e => e.Id, e => e)
            .FindWithBossFriend(targetIds)
        .Distinct();

    public static IEnumerable<Employee> FindWithBossFriend(this IDictionary<int, Employee> hierarchy, params int[] targetIds)
            => targetIds
                .Where(eId => hierarchy.ContainsKey(eId))
                .Select(eId => hierarchy[eId])
                .SelectMany(e => hierarchy.FindWithBossFriend(e.ParentId).Append(e));

As you might be able to spot, I personally can't seem to be able to trade in any more of my dignity for the possible removal of that last .Distinct(), but there are rumors going around some would be.

Upvotes: 0

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186843

You can implement a help method, EmployeeAndBosses which returns given employee and all the parents:

private static IEnumerable<Employee> EmployeeAndBosses(Employee value, 
                                                       IEnumerable<Employee> collection) {
  for (Employee item = value; 
       item != null; 
       item = collection.FirstOrDefault(x => x.ParentId == item.Id))
    yield return item; 
}

then you can filter topmost employee in the hierarchy, and add their bosses then:

HashSet<int> ids = new HashSet<int>() {
  6, 7
}; 

var result = employees
  .Where(item => ids.Contains(item.Id))                   // topmost
  .SelectMany(item => EmployeeAndBosses(item, employees)) // topmost and parents
  .GroupBy(item => item.Id)          // Duplicates (e.g. CEO) removing
  .Select(group => group.First());   //

Edit: If you have a huge collection(s) and that's why FirstOrDefault and GroupBy are bad choice, you can implement Bread First Search:

private static IEnumerable<Employee> MyFilter(IEnumerable<Employee> list, 
                                              IEnumerable<int> idsToFind) {
  Dictionary<int, Employee> stuff = list
    .ToDictionary(item => item.Id, item => item);

  HashSet<int> ids = new HashSet<int>(idsToFind);

  HashSet<int> completed = new HashSet<int>(); 
  Queue<Employee> agenda = new Queue<Employee>(list.Where(item => ids.Contains(item.Id)));

  while (agenda.Count > 0) {
    Employee current = agenda.Dequeue();

    if (null != current && completed.Add(current.Id)) {
      yield return current;

      if (stuff.TryGetValue(current.ParentId, out current))
        agenda.Enqueue(current);
    }
  }   
}

Upvotes: 1

Related Questions