/**
* The Problem:
*
* We have a list of tasks. Each task can depend on other tasks. 
* For example if task A depends on task B then B should run before A.
* 
* Implement the "getTaskWithDependencies" method such that it returns a list of task names in the correct order.
* 
* For example if I want to execute task "application A", the method should return a list with "storage,mongo,application A".
*
* List of Tasks:
*
*   - name: application A
*     dependsOn:
*       - mongo
*
*   - name: storage
*
*   - name: mongo
*     dependsOn:
*       - storage
*
*   - name: memcache
*
*   - name: application B
*     dependsOn:
*       - memcache
*
* The Java program is expected to be executed succesfully.
*/

import java.io.*;
import java.util.*;
import org.junit.*;
import org.junit.runner.*;

public class Solution { 
 private static List<String> getTaskWithDependencies(List<Task> tasks, String dependsOn) {
   // TODO: please implement logic here
   //定义 
        int numCourses = tasks.size();
        boolean[] visited = new boolean[numCourses];
        Stack<String> stack = new Stack<>();
        //判断
        //v是课程的数量 0-4
        for (int i = 0; i < numCourses; i++) {
            //有环就是空
            if (!topologicalSort(tasks, i, tasks.get(i).getName(),
                stack, visited, new boolean[numCourses])) return new ArrayList<>();
        }
        
        //定义结果
        //int[] result = new int[numCourses];
        List<String> result = new ArrayList<>();
        //往里面加
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
 }
  
private static boolean topologicalSort(List<Task> adj, int taskIndex, String taskName,
        Stack<String> stack, boolean[] visited, boolean[] isLoop) {
        //提前判断一下
        if (visited[taskIndex]) return true;
        if (isLoop[taskIndex]) return false;

        //设定v是有循环的，因为v是大的[]，就分析这么一次。类比，task是大的，就分析一次。所以signature要改。
        isLoop[taskIndex] = true;
        //u需要具体问题具体分析。有回路就是false。类比，name需要具体问题具体分析。
        //所以怎么迁移到这道题呢？adj.get(v)是Task。那都换成Task不就行了？
        //两个不一样类型。。。注释掉会不会有影响？会，主要是中途false了就不能加了。一直是true才能加
        //别用for each循环不就行了
        if (!adj.get(taskIndex).getDependsOn().isEmpty()) {
          if (!topologicalSort(adj, taskIndex, adj.get(taskIndex).getDependsOn().toString(),
                stack, visited, isLoop)) 
        {System.out.println("false here");
                return false;}
        } else {
          if (!topologicalSort(adj, taskIndex, "",
                stack, visited, isLoop)) 
        {System.out.println("false here1");
                return false;}
        }
        //访问完v了
        visited[taskIndex] = true;

        //把课程加到stack里，后续要拿来排序。所以应该是string对吧。处理下就行了。
        System.out.println("adj.get(taskIndex).getName() = " + adj.get(taskIndex).getName());
        stack.push(adj.get(taskIndex).getName());
        return true;
    }

 public static void main(String[] args) {
   JUnitCore.main("Solution");        
 }

 @Test
 public void testGetTaskDependenciesForApplicationA() {
   Assert.assertEquals(
     Arrays.asList(
       "storage",
       "mongo",
       "application A"
     ),
     getTaskWithDependencies(TaskList.getTasks(), "application A")
   );
 }
}

/**
* Definition of a Task
*/
class Task {
 private final String name;
 private final List<String> dependsOn;

 Task(String name) {
   this(name, new ArrayList<>());
 }

 Task(String name, List<String> dependsOn) {
   this.name = name;
   this.dependsOn = dependsOn;
 }

 public String getName() { return this.name; }
 public List<String> getDependsOn() { return this.dependsOn; }
}

class TaskList {
 public static List<Task> getTasks() {
   List<Task> tasks = new ArrayList<>();

   tasks.add(new Task("application A", Arrays.asList("mongo")));
   tasks.add(new Task("storage"));
   tasks.add(new Task("mongo", Arrays.asList("storage")));
   tasks.add(new Task("memcache"));
   tasks.add(new Task("application B", Arrays.asList("memcache")));

   return tasks;
 }
}