import './utility.js';
import {BasicStack} from './stack.js';
import {BasicQueue} from './queue.js';
import {BasicPriorityQueue} from './priority_queue.js';
import {firstExample, secondExample} from './inputs.js';

function print(value) {
  $('#output').append($('<span></span>').text(value)).append('<br>');
}

export function dfs(graph, source, destination) {
  const backpointers = new Map();
  const worklist = new BasicStack();
  worklist.insert([undefined, source]);
  while (worklist.size > 0) {
    const [from, to] = worklist.remove();
    if (backpointers.has(to)) {
      continue;
    }
    backpointers.set(to, from);
    if (to === destination) {
      break;
    }
    for (const incidence of graph.getIncidences(to)) {
      worklist.insert([to, incidence.destination]);
    }
  }
  const path = [];
  for (let current = destination; current !== undefined; current = backpointers.get(current)) {
    path.push(current);
  }
  return path.reverse();
}

export function bfs(graph, source, destination) {
  const backpointers = new Map();
  const worklist = new BasicQueue();
  worklist.insert([undefined, source]);
  while (worklist.size > 0) {
    const [from, to] = worklist.remove();
    if (backpointers.has(to)) {
      continue;
    }
    backpointers.set(to, from);
    if (to === destination) {
      break;
    }
    for (const incidence of graph.getIncidences(to)) {
      worklist.insert([to, incidence.destination]);
    }
  }
  const path = [];
  for (let current = destination; current !== undefined; current = backpointers.get(current)) {
    path.push(current);
  }
  return path.reverse();
}

export function dijkstras(graph, source, destination) {
  const backpointers = new Map();
  const worklist = new BasicPriorityQueue();
  worklist.insert([undefined, source], 0);
  while (worklist.size > 0) {
    const [[from, to], distance] = worklist.remove();
    if (backpointers.has(to)) {
      continue;
    }
    backpointers.set(to, from);
    if (to === destination) {
      break;
    }
    for (const incidence of graph.getIncidences(to)) {
      worklist.insert([to, incidence.destination], distance + incidence.weight);
    }
  }
  const path = [];
  for (let current = destination; current !== undefined; current = backpointers.get(current)) {
    path.push(current);
  }
  return path.reverse();
}

const search = dijkstras;
print(search(firstExample, 'a', 'd'));
print(search(secondExample, '123', '321'));