import { PriorityQueue } from './collections.js';

export class Incidence {
  constructor(action, weight, outcome) {
    this.action = action;
    this.weight = weight;
    this.outcome = outcome;
  }
}

class Edge {
  constructor(from, action, to, distance) {
    this.from = from;
    this.action = action;
    this.to = to;
    this.distance = distance;
  }

  get weight() {
    return this.action.length;
  }
}

export function dijkstras(source, getIncidences, isDestination) {
  const backpointers = new Map();
  const worklist = new PriorityQueue();
  worklist.insert(new Edge(undefined, undefined, source, 0), 0);
  while (worklist.size > 0) {
    const workitem = worklist.remove();
    const key = workitem.to.toKey();
    if (backpointers.has(key)) {
      continue;
    }
    backpointers.set(key, workitem);
    if (isDestination(workitem.to)) {
      const reversedPath = [];
      for (let current = workitem; current.from !== undefined; current = backpointers.get(current.from.toKey())) {
        reversedPath.push(current.action);
      }
      return reversedPath.reverse();
    }
    for (const incidence of getIncidences(workitem.to)) {
      const newDistance = workitem.distance + incidence.weight;
      worklist.insert(new Edge(workitem.to, incidence.action, incidence.outcome, newDistance));
    }
  }
  return undefined;
}