How to convert a List<Entity> where each element points to other Entities into Map<String,-CodePudding

I am having a class as

public class Entity {
    private String id;
    private List<Entity> children;
    
    // getters, constructor, etc.
}

Now I need to convert this Entity class data into Map<String, Entity>

My Method accepts (List entity) as Input and that need to be converted to Map

I tried like:

public static Map<String, Entity> group(List<Entity> entities) {
    
    Map<String, Entity> map = new HashMap<>();
    for (Entity e : entities) {
        if (!map.containsKey(e.getId())) {
            map.put(e.getId(), ??? e.getChildren() ???); // my point of confusion
        }
    }
    return map;
}

My problem is that I don't know how to proceed at the point when I need to access children-entities via getChildren(). How it can be implemented to get the proper data?

Sample data format is as follows.

[
 {
    id: bos
    childs:[
        {
            id: manager1
            childs: [{id: worker11}, {id: worker12}]
        },
        {
            id: manager2
            childs: [{id: worker21}, {id: worker22}]
        }
    ]
 }
]

CodePudding user response：

Basically, you have a disjointed Graph of Entities.

Therefore, you need to implement a graph traversal algorithm in order to the data of the Entities into the resulting Map.

One of the simplest algorithms commonly used for such purposes is the Depth first search.

The core idea behind this algorithm:

Maintain a Stack, containing the element that are being examined.
Search starts from the root element being pushed on the top of the stack.
Elements are being repeatedly removed from the top of the stack. And if the next element has children that haven't been yet seen, they are being pushed on the top of the stack.

Here's how the iterative implementation might look like:

public static Map<String, Entity> group(List<Entity> entities) {
    
    Map<String, Entity> result = new HashMap<>();
    Set<String> seen = new HashSet<>();
    
    for (Entity e : entities) {
        if (seen.add(e.getId())) { // entity was not previously encountered
            addAllChildren(result, seen, e);
        }
    }
    return result;
}

/**
 * Depth first search algorithm implementation
 */
public static void addAllChildren(Map<String, Entity> result,
                                  Set<String> seen,
                                  Entity root) {
    
    Deque<Entity> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        Entity current = stack.pop();
        result.put(current.getId(), current);
        
        for (Entity child: current.getChildren()) {
            if (seen.add(child.getId())) {
                stack.push(child);
            }
        }
    }
}