package uk.ac.aber.cs31920.assignment.implementation.solvers;

import uk.ac.aber.cs31920.assignment.implementation.datastructures.GraphNode;

import java.util.*;
import java.util.function.Function;

public class BreadthFirstSearchRunner {
    /**
     * Calculates a path to a given node from root using a breadth first search. Since nodes have
     * multiple sets of children, this method takes a getChildrenFunc to define which group of children we
     * request as we do our traversal.
     *
     * https://stackoverflow.com/questions/15228819/how-to-pass-a-member-function-as-a-parameter-in-java
     *
     * @param root starting node
     * @param target node we're looking for
     * @param getChildrenFunc method for requesting a nodes children e.g. GraphNode::getResidualNetworkChildren
     * @return
     */
    public static List<GraphNode> run(GraphNode root, GraphNode target, Function<GraphNode, List<GraphNode>> getChildrenFunc){
        Queue<GraphNode> toCheck = new LinkedList<>(List.of(root));

        List<GraphNode> visited = new ArrayList<>();

        Map<GraphNode, GraphNode> parents = new HashMap<>();

        GraphNode current = root;
        while (!toCheck.isEmpty()){
            current = toCheck.remove();
            if (visited.contains(current)){
                continue;
            }

            if (current == target){
                // found it!
                List<GraphNode> result = new LinkedList<>();
                while(true) {
                    result.add(0, current);

                    if (current.isSource()) // no parent, at root
                        return result;

                    current = parents.get(current);
                }

            }

            visited.add(current);
            for (GraphNode child : getChildrenFunc.apply(current)) {
                toCheck.add(child);
                parents.putIfAbsent(child, current);
            }
        }
        return null;
    }
}