import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class GetPath {

    private static int threshold;
    private static String curNode;
    private static GroumNode groumNode;
    private static Groum targetGraph;
    private static List forPathList;
    private static List backPathList;
    private static List fuzzyPathList;
    private static List forAndbackPathList;
    private static List pathResult;


    private static void getForPath(List successors) {
        if (successors.size() + 1 > threshold)
            return;
        curNode = successors.get(successors.size() - 1);
        groumNode = targetGraph.getNodeMap().get(curNode);
        for (GroumNode predecessor : groumNode.getParents()) {
            List successorsFor = new ArrayList();
            Collections.addAll(successorsFor, new String[successors.size()]);
            Collections.copy(successorsFor, successors);
            successorsFor.add(predecessor.getId());
            List successorsCopy = new ArrayList();
            Collections.addAll(successorsCopy, new String[successorsFor.size()]);
            Collections.copy(successorsCopy, successorsFor);
            Collections.reverse(successorsFor);
            forPathList.add(successorsFor);
            getForPath(successorsCopy);
        }
    }

    private static void getBackPath(List predecessors) {
        if (predecessors.size() + 1 > threshold)
            return;
        curNode = predecessors.get(predecessors.size() - 1);
        groumNode = targetGraph.getNodeMap().get(curNode);
        for (GroumNode successor : groumNode.getChildren()) {
            List predecessorsFor = new ArrayList();
            Collections.addAll(predecessorsFor, new String[predecessors.size()]);
            Collections.copy(predecessorsFor, predecessors);
            predecessorsFor.add(successor.getId());
            backPathList.add(predecessorsFor);
            getBackPath(predecessorsFor);
        }
    }

    /**
     * List
     * @param starter 
     * @param ender   
     * @return        List
     */
    private static List getRangeNums(int starter, int ender) {
        List result = new ArrayList();
        for (int i = starter; i < ender; ++i) {
            result.add(i);
        }
        return result;
    }

    /**
     * fuzzy path
     * @param target path
     * @param start fuzzyindex
     * @param end   fuzzyindex + 1
     */
    private static void makeOneFuzzyPath(List target, int start, int end) {
        for (int i = start; i < end; ++i) {
            target.set(i, "*");
        }
    }

    private static void getFuzzyPath(){
        forAndbackPathList = new ArrayList();
        forAndbackPathList.addAll(forPathList);
        forAndbackPathList.addAll(backPathList);
        for (List path : forAndbackPathList) {
            for (int starLen : getRangeNums(1, path.size() - 1)) {
                List pathCopyFor = new ArrayList();
                Collections.addAll(pathCopyFor, new String[path.size()]);
                Collections.copy(pathCopyFor, path);
                makeOneFuzzyPath(pathCopyFor, 1, starLen + 1);
                fuzzyPathList.add(pathCopyFor);
                List pathCopyBack = new ArrayList();
                Collections.addAll(pathCopyBack, new String[path.size()]);
                Collections.copy(pathCopyBack, path);
                makeOneFuzzyPath(pathCopyBack, path.size() - 1 - starLen, path.size() - 1);
                fuzzyPathList.add(pathCopyBack);
            }
        }
    }

    /**
     * List 
     * @param target
     */
    private static void removeDuplicate(List target) {
        LinkedHashSet set = new LinkedHashSet(target.size());
        set.addAll(target);
        target.clear();
        target.addAll(set);
    }

    /**
     * idMapid
     * @param pathResult
     * @param source
     */
    public static void convert(List pathResult, List source) {
        Map nodeMap = targetGraph.getNodeMap();
        for (List sourcePath : source) {
            List apiPath = new ArrayList();
            boolean canAdd = true;
            for (String id : sourcePath) {
                if (id.equals("*")) {
                    apiPath.add("*");
                }
                else {
                    String temp = nodeMap.get(id).getApi();
                    if (!temp.equals("-1")) apiPath.add(temp);
                    else {
                        canAdd = false;
                        break;
                    }
                }
            }
            if (canAdd) pathResult.add(apiPath);
        }
    }
    public static List getAllPath(Groum groum, List startList, int d) {
        threshold = d;
        targetGraph = groum;
        // get forward paths
        forPathList = new ArrayList();
        getForPath(startList);
        // get backward paths
        backPathList = new ArrayList();
        getBackPath(startList);
        // get fuzzy paths
        fuzzyPathList = new ArrayList();
        getFuzzyPath();
        removeDuplicate(fuzzyPathList);
        // path list
        pathResult = new ArrayList();
        convert(pathResult, forPathList);
        convert(pathResult, backPathList);
        convert(pathResult, fuzzyPathList);
        return pathResult;
    }
}