Find an object from a tree or hierarchy of lists
I have a class like
public class Employee
{
public Employee[] ChildOrg{get; set;}
public string name {get; set;};
public string id{get; set;};
}
How can I find a specific employee from their ID?
I have tried several following function.
private static Employee GetNode(Employee objEmployeeList, string id)
{
if (objEmployeeList.ChildOrg==null)
{
return null;
}
foreach (var item in objEmployeeList.ChildOrg)
{
if (item.ID.Equals(id))
{
return (objEmployeeList)item;
}
}
foreach (var item in objEmployeeList.ChildOrg)
{
return GetNode((objEmployeeList)item, id);
}
return null;
}
As you can see, I am trying to write some recursive function to get the employee.
If you look closely, it just goes down to just the first node.
Then it returns null and doesn't go to any other node.
Please tell me how to fix my function and other ways to accomplish the samething using linq?
EDIT: -
I want to access a specific node and its siblings.
+3
source to share
6 answers
Some changes in the class and some changes in the subroutine.
public class Employee
{
public List<Employee> ChildOrg { get; set; }
public string Name { get; set; }
public string Id { get; set; }
public Employee(string id, string name)
{
Id = id;
Name = name;
ChildOrg = new List<Employee>();
}
public Employee AddChildOrg(string id, string name)
{
var newEmployee = new Employee(id, name);
ChildOrg.Add(newEmployee);
return newEmployee;
}
public static Employee GetNode(Employee father, string id)
{
if (father != null)
{
if (father.Id.Equals(id))
return father;
if (father.ChildOrg != null)
foreach (var child in father.ChildOrg)
{
if (child.Id.Equals(id))
return child;
var employee = Employee.GetNode(child, id);
if (employee != null)
return employee;
}
}
return null;
}
}
And a little test program:
class Program
{
static void Main(string[] args)
{
Employee root = new Employee(1.ToString(), "root");
var e2 = root.AddChildOrg(2.ToString(), "2 second level");
var e3 = e2.AddChildOrg(3.ToString(), "3 third level");
var e1 = root.AddChildOrg(4.ToString(), "4 second level");
var e5 = e1.AddChildOrg(5.ToString(), "5 third level");
Console.WriteLine("Id 3 -> {0}", Employee.GetNode(root, "3").Name);
Console.WriteLine("Id 1 -> {0}", Employee.GetNode(root, "1").Name);
Console.WriteLine("Id 5 -> {0}", Employee.GetNode(root, "5").Name);
Console.ReadKey();
}
}
+3
source to share
I think the best approach here is to write a recursive method that returns IEnumerable<Employee>
that iterates over all the nodes in the tree.
Given a class Employee
that looks like this:
public class Employee
{
public Employee[] ChildOrg { get; set; }
public string name { get; set; }
public string id { get; set; }
}
You can write a recursive counter like this:
public static IEnumerable<Employee> AllEmployees(Employee root)
{
if (root == null)
yield break;
yield return root;
if (root.ChildOrg == null)
yield break;
foreach (var child in root.ChildOrg.SelectMany(AllEmployees))
yield return child;
}
Please note that this returns ALL employees. If you want to filter it by id, you just need to filter the enum like:
var allNodesWithIdEndingIn0 = AllEmployees(root).Where(node => node.id.EndsWith("0"));
It is much more flexible to return an enumeration of all employees because you can use Linq to process or filter as needed.
Here's a complete compiled console application that demonstrates this approach:
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication4
{
public class Employee
{
public Employee[] ChildOrg { get; set; }
public string name { get; set; }
public string id { get; set; }
}
public static class Program
{
public static IEnumerable<Employee> AllEmployees(Employee root)
{
if (root == null)
yield break;
yield return root;
if (root.ChildOrg == null)
yield break;
foreach (var child in root.ChildOrg.SelectMany(AllEmployees))
yield return child;
}
private static void Main()
{
Employee root = new Employee { name = "root", id = "root" };
createChildren(root, 4, 4, 0);
Console.WriteLine("All employees:");
Console.WriteLine(string.Join("\n", AllEmployees(root).Select(node => node.id)));
Console.WriteLine("\nAll nodes with an id that ends in 0:");
var allNodesWithIdEndingIn0 = AllEmployees(root).Where(node => node.id.EndsWith("0"));
Console.WriteLine(string.Join("\n", allNodesWithIdEndingIn0.Select(node => node.id)));
}
private static int createChildren(Employee root, int depth, int width, int count)
{
if (depth == 0)
return count;
root.ChildOrg = new Employee[width];
for (int i = 0; i < width; ++i)
{
var node = new Employee { id = count.ToString() };
root.ChildOrg[i] = node;
count = createChildren(node, depth-1, width, count+1);
}
return count;
}
}
}
Accessing child nodes of nodes
If you need the siblings of the nodes, you can return a list of the parents of the ChildOrg
nodes.
To do this, I will write a wrapper class called `EmployeeAndParent to contain both the node and its parent.
Here's the modified code. It also demonstrates how to access sibs from node with id == "100":
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication4
{
public class Employee
{
public Employee[] ChildOrg
{
get;
set;
}
public string name
{
get;
set;
}
public string id
{
get;
set;
}
}
public class EmployeeAndParent
{
public EmployeeAndParent(Employee employee, Employee parent)
{
Employee = employee;
Parent = parent;
}
public readonly Employee Employee;
public readonly Employee Parent;
}
public static class Program
{
public static IEnumerable<EmployeeAndParent> AllEmployees(Employee root, Employee parent)
{
if (root == null)
yield break;
yield return new EmployeeAndParent(root, parent);
if (root.ChildOrg == null)
yield break;
foreach (var child in root.ChildOrg.SelectMany(child => AllEmployees(child, root)))
yield return child;
}
private static void Main()
{
Employee root = new Employee
{
name = "root",
id = "root"
};
createChildren(root, 4, 4, 0);
Console.WriteLine("All employees:");
Console.WriteLine(string.Join("\n", AllEmployees(root, null).Select(node => node.Employee.id)));
Console.WriteLine("\nAll nodes with an id that ends in 0:");
var allNodesWithIdEndingIn0 = AllEmployees(root, null).Where(node => node.Employee.id.EndsWith("0"));
Console.WriteLine(string.Join("\n", allNodesWithIdEndingIn0.Select(node => node.Employee.id)));
Console.WriteLine("\nAll siblings of the node with id == 100, along with that node itself:");
var foundNode = AllEmployees(root, null).Single(node => node.Employee.id == "100");
Console.WriteLine(string.Join("\n", foundNode.Parent.ChildOrg.Select(node => node.id)));
}
private static int createChildren(Employee root, int depth, int width, int count)
{
if (depth == 0)
return count;
root.ChildOrg = new Employee[width];
for (int i = 0; i < width; ++i)
{
var node = new Employee
{
id = count.ToString()
};
root.ChildOrg[i] = node;
count = createChildren(node, depth-1, width, count+1);
}
return count;
}
}
}
+1
source to share
public class Employee
{
public Employee()
{
ChildOrg = new List<Employee>();
}
public Employee(string toString, string root)
{
ChildOrg = new List<Employee>();
Id = toString;
Name = root;
}
public IList<Employee> ChildOrg { get; set; }
public string Name { get; set; }
public string Id { get; set; }
public static Employee GetNode(Employee e, string theId)
{
if (e.Id.Equals(theId))
{
return e;
}
var employeeInList = (e.ChildOrg == null) ? null : e.ChildOrg.FirstOrDefault(item => item.Id.Equals(theId));
return employeeInList ??
e.ChildOrg.Select(item => GetNode(item, theId)).FirstOrDefault(employee => employee != null);
}
}
Test
static void Main(string[] args)
{
var root = new Employee(1.ToString(), "root");
var e1 = new Employee(2.ToString(), "1 second level");
var e2 = new Employee(3.ToString(), "2 third level");
var e3 = new Employee(4.ToString(), "3 second level");
var e4 = new Employee(5.ToString(), "4 third level");
e3.ChildOrg.Add(e4);
e2.ChildOrg.Add(e3);
e1.ChildOrg.Add(e2);
root.ChildOrg.Add(e1);
Console.WriteLine("Id 3 -> {0}", Employee.GetNode(root, "3").Name);
Console.WriteLine("Id 1 -> {0}", Employee.GetNode(root, "1").Name);
Console.WriteLine("Id 5 -> {0}", Employee.GetNode(root, "5").Name);
Console.ReadKey();
}
0
source to share
Define a bypass function:
public static IEnumerable<Employee> Traverse(Employee employee)
{
yield return employee;
if (employee.ChildOrg == null) yield break;
var subordinates = employee
.ChildOrg
.SelectMany(Traverse);
foreach(var s in subordinates)
yield return s;
}
and then find the corresponding element:
var root = new Employee(...);
...
var searchId = "42";
var employee42 = Traverse(root)
.Single(e => e.id == searchId);
0
source to share
try it
private static Employee GetNode(Employee employee, string id){
if (employee.id == id)
return employee;
if (employee.ChildOrg != null)
{
foreach (var item in employee.ChildOrg)
{
if(item.id == id)
return item;
var child = GetNode(item, id);
if(child != null)
return child;
}
}
return null;
}
0
source to share