export type Task = {
  id: ID;   // ID — alias for string
  title: string;
  start: Date;
  end: Date;
  duration: number;
  position: number;  // Приоритет
  progress: number;
  resourceId: ID;
  dependencies?: ID[];
};

/**
* Graph respects explicit dependencies
* and implicit by resources (via positions)
*/
export const makeGraphFromTasks = (tasks: Task[]): Graph => {
  const graph: Graph = new Map();
  const resources = new Map<ID, Task[]>();
  // add edges for deps by resourceId and explicit dependencies
  for (const t of tasks) {
    const tasksForResource = resources.get(t.resourceId) ?? [];
    tasksForResource.push(t);
    resources.set(t.resourceId, tasksForResource);
    graph.set(t.id, new Set(t.dependencies ?? []));
  }
  for (const tasksForResource of resources.values()) {
    // sort by position
    tasksForResource.sort((a, b) => a.position - b.position);
    // add to graph such edges so first node has second as dependency
    let prevTask: Task | undefined;
    for (const task of tasksForResource) {
      if (prevTask) {
        graph.get(prevTask.id)?.add(task.id);
      }
      prevTask = task;
    }
  }
  return graph;
};

export const makeReverseGraph = (graph: Graph): Graph => {
  const reverseGraph: Graph = new Map();
  for (const [id, parentId] of dfs(graph, { withParentId: true })) {
    const prerequesitions = reverseGraph.get(id) ?? new Set();
    if (parentId) {
      prerequesitions.add(parentId);
    }
    reverseGraph.set(id, prerequesitions);
  }
  return reverseGraph;
};
/**
* Iterate over every node.
* If withParentId = true, than it is possible to visit same not more then once
* @yields {[string, string?]} [nodeId, parentNodeId?]
*/
export function* dfs(
  graph: Graph,
  options: { withParentId: boolean } = { withParentId: false }
): Generator<readonly [string, string?], void, void> {
  const visited = new Set<ID>();
  // DFS interative
  // iterate over all nodes in case of disconnected graph
  for (const node of graph.keys()) {
    if (visited.has(node)) {
      continue;
    }
    const stack: ID[] = [node];
    while (stack.length > 0) {
      const currentNode = stack.pop();
      assertIsDefined(currentNode);
      yield [currentNode];
      visited.add(currentNode);
      const dependencies = graph.get(currentNode);
      if (!dependencies) {
        continue;
      }
      for (const dependencyId of dependencies) {
        if (options.withParentId) {
          // possible to yield same nodeId multiple times (needed for making reverse graph)
          yield [dependencyId, currentNode];
        }
        if (visited.has(dependencyId)) {
          continue;
        }
        stack.push(dependencyId);
      }
    }
  }
}
export const makeReverseGraph = (graph: Graph): Graph => {
  const reverseGraph: Graph = new Map();
  for (const [id, parentId] of dfs(graph, { withParentId: true })) {
    const prerequisites = reverseGraph.get(id) ?? new Set();
    if (parentId) {
      prerequisites.add(parentId);
    }
    reverseGraph.set(id, prerequisites);
  }
  return reverseGraph;
};
/**
* Iterate over every node.
* If withParentId = true, than it is possible to visit same not more then once
* @yields {[string, string?]} [nodeId, parentNodeId?]
*/
export function* dfs(
  graph: Graph,
  options: { withParentId: boolean } = { withParentId: false }
): Generator<readonly [string, string?], void, void> {
  const visited = new Set<ID>();
  // DFS interative
  // iterate over all nodes in case of disconnected graph
  for (const node of graph.keys()) {
    if (visited.has(node)) {
      continue;
    }
    const stack: ID[] = [node];
    while (stack.length > 0) {
      const currentNode = stack.pop();
      assertIsDefined(currentNode);
      yield [currentNode];
      visited.add(currentNode);
      const dependencies = graph.get(currentNode);
      if (!dependencies) {
        continue;
      }
      for (const dependencyId of dependencies) {
        if (options.withParentId) {
          // possible to yield same nodeId multiple times (needed for making reverse graph)
          yield [dependencyId, currentNode];
        }
        if (visited.has(dependencyId)) {
          continue;
        }
        stack.push(dependencyId);
      }
    }
  }
}

export const scheduleTasks = (tasks: Task[], today?: Date) => {
  const graph = makeGraphFromTasks(tasks);
  const tasksById = tasks.reduce((map, task) => {
    map[task.id] = task;
    return map;
  }, {} as { [id: string]: Task });
  // @TODO: 0. Detect cycles, if present throw error
  // 1. Make reverse graph, to detect sinks and sources
  const reverseGraph = makeReverseGraph(graph);
  // 2. If node is source, t.start = max(today, t.start)
  // Repeat until dates remains unchanged, max graph.size times.
  // Similar to optimization in Bellman-Ford algorithm
  // @see https://en.wikipedia.org/wiki/Bellman–Ford_algorithm#Improvements
  for (let i = 0; i <= graph.size; i++) {
    let datesChanged = false;
    for (const [id] of dfs(graph)) {
      const t = tasksById[id];
      const isSource = reverseGraph.get(id)?.size === 0;
      const isSink = graph.get(id)?.size === 0;
      const isDisconnected = isSource && isSink;
      if (isSource || isDisconnected) {
        datesChanged = updateStartDate(t, today ?? new Date());
      } else {
        const prerequesionsEndDates = Array.from(
          reverseGraph.get(id) ?? []
        ).map((id) => tasksById[id].end);
        datesChanged = updateStartDate(
          t,
          addBusinessDays(max(prerequesionsEndDates), 1)
        );
      }
    }
    if (datesChanged === false) {
      break;
    }
  }
  return tasks;
};
/**
* Update task dates, according to startDate change
* @returns false if date didn't change, true if it changed
*/
export const updateStartDate = (task: Task, startDate: Date) => {
  const correctedStartDate = shiftToFirstNextBusinessDay(startDate);
  const daysSpent = Math.floor(task.duration * task.progress);
  const newStartDate = subBusinessDays(correctedStartDate, daysSpent);
  if (isEqual(task.start, newStartDate)) {
    return false;
  }
  task.start = subBusinessDays(correctedStartDate, daysSpent);
  // -1 because every task is minimum 1 day long,
  // say it starts and ends on same date, so it has 1 day duration
  task.end = addBusinessDays(task.start, task.duration - 1);
  return true;
};