Find hierarchy

Question

Consider a class in java

class Entity { Integer id; Integer parentId; public Integer getId() { return id; } public void setId(Integer id) { this.id = id; } public Integer getParentId() { return parentId; } public void setParentId(Integer parentId) { this.parentId = parentId; } } } 

Consider parentId as a foreign key (refers to id to another object).

Now I created 6 objects and put some values.

 Entity e1 = new Entity(); e1.setId(400); Entity e2 = new Entity(); e2.setId(300); e2.setParentId(400); Entity e3 = new Entity(); e3.setId(200); e3.setParentId(300); Entity e4 = new Entity(); e4.setId(100); e4.setParentId(200); Entity e5 = new Entity(); e5.setId(50); e5.setParentId(100); Entity e6 = new Entity(); e6.setParentId(50); 

Now I want to get a hierarchy of objects. This means that if I give id, I have to get the full parent hierarchy and child hierarchy.

for example: if I give 100 as id (entity: e4), I should get the parent hierarchy: - e4, e3, e2, e1 child hierarchy: - e4, e5, e6

Explanation: - for the parent hierarchy: - first you need to add the initial e4-object. then we will find an object whose iD is the same as e4 parentId. (here e3) the process continues until parentid is non-zero for the child hierarchy: - first you need to add the initial e4-object. then we will find an object whose parentId is similar to the e4 id object. (here e5) the process continues until parentid is null

Solution from me for parent hierarchy: -

  List<Entity> parent = new ArrayList<Entity>(); Entity ent = list.stream().filter(e -> e.getId() == 100).findFirst() .get(); // // 100 input id value parent.add(ent); Integer parentId = ent.getParentId(); while (parentId != null) { int search = parentId; Entity newEntity = list.stream().filter(e -> e.getId() == search) .findFirst().get(); parent.add(newEntity); parentId = newEntity.getParentId(); } 

for child hierarchy:

  Entity entnew = list.stream().filter(e -> e.getId() == 100).findFirst() .get(); // 100 input id value child.add(entnew); Integer idNew = entnew.getId(); while (idNew != null) { int searchNew = idNew; Entity newEnt = list.stream().filter(f -> f.getParentId()!= null && f.getParentId() == searchNew) .findFirst().get(); child.add(newEnt); idNew = newEnt.getId(); } 

I found this method to solve the scenario, but I want a more efficient solution in java 8, using its basic concepts to solve this problem.

Answer 1

I found a more Java8-ish solution with the smell of functional programming.

Given your six entities (note that I set Id for e6 , otherwise we get a NullPointerException ):

 Entity e1 = new Entity(); e1.setId(400); Entity e2 = new Entity(); e2.setId(300); e2.setParentId(400); Entity e3 = new Entity(); e3.setId(200); e3.setParentId(300); Entity e4 = new Entity(); e4.setId(100); e4.setParentId(200); Entity e5 = new Entity(); e5.setId(50); e5.setParentId(100); Entity e6 = new Entity(); e6.setId(25); // this Id must be set, or we'll get a NPE e6.setParentId(50); 

And a list containing them:

 List<Entity> list = new ArrayList<>(); list.add(e1); list.add(e2); list.add(e3); list.add(e4); list.add(e5); list.add(e6); 

Then for the parent hierarchy:

 Function<Integer, Entity> byId = id -> list.stream() .filter(e -> e.getId().equals(id)) .findFirst() .orElse(null); Entity parentsSeed = byId.apply(100); // e4 UnaryOperator<Entity> nextParent = e -> e == null ? e : byId.apply(e.getParentId()); List<Entity> parents = Stream.iterate(parentsSeed, nextParent) .limit(list.size()) .filter(Objects::nonNull) .collect(Collectors.toList()); // [e4, e3, e2, e1] 

And for the hierarchy of children:

 Entity childrenSeed = byId.apply(100); // e4 Function<Integer, Entity> byParentId = id -> list.stream() .filter(e -> id.equals(e.getParentId())) .findFirst() .orElse(null); UnaryOperator<Entity> nextChild = e -> e == null ? e : byParentId.apply(e.getId()); List<Entity> children = Stream.iterate(childrenSeed, nextChild) .limit(list.size()) .filter(Objects::nonNull) .collect(Collectors.toList()); // [e4, e5, e6] 

The idea is to use the Stream.iterate() method by creating a stream using "functional" iteration.

For parents, I created a UnaryOperator (function), which when set to Entity returns either its parent Entity or null ; for children, I created UnaryOperator , which, with the Entity UnaryOperator , returns either its child Entity or null .

To perform these two searches, I used another Function that just looks for list on id and parentId respectively.

Answer 2

I would create lookup tables for objects, parents and children:

 List<Integer> ancestors = new ArrayList<>(); List<Integer> descendants = new ArrayList<>(); Map<Integer, Entity> objectById = list.stream().collect(Collectors.toMap(e ->e.getId(), e->e)); Map<Integer, Integer> parentIdByChildId = list.stream().collect(Collectors.toMap(e->e.getId(), e ->e.getParentId()); Map<Integer, Integer> childIdByParentId = list.stream().collect(Collectors.toMap(e ->e.getParentId(), e->e.getId()); Integer parentId = 10; Integer current = parentId; while(current!=null) { current = childIdByParentId.get(current); if(current!=null){ descendants.add(objectById.get(current)); } } current = parentId; while(current!=null) { current = parentIdByChildId.get(current); if(current!=null){ ancestors.add(objectById.get(current)); } } 

This does not support objects with multiple children, you can check examples for java.util.stream.Collectors.groupBy

Answer 3

Do you need to use int id to refer to the parent? Depending on what you are trying to achieve, but can you just refer to this:

 class Entity { Integer id; Entity parent; } 

Then you do not have to search the entire list as soon as you have the first entity.