use std::collections::hash_map::Entry::{Occupied, Vacant};
use std::collections::{BinaryHeap, HashMap};
use std::hash::Hash;
use crate::algo::Measure;
use crate::scored::MinScored;
use crate::visit::{EdgeRef, IntoEdges, VisitMap, Visitable};
pub fn dijkstra<G, F, K>(
graph: G,
start: G::NodeId,
goal: Option<G::NodeId>,
mut edge_cost: F,
) -> HashMap<G::NodeId, K>
where
G: IntoEdges + Visitable,
G::NodeId: Eq + Hash,
F: FnMut(G::EdgeRef) -> K,
K: Measure + Copy,
{
let mut visited = graph.visit_map();
let mut scores = HashMap::new();
let mut visit_next = BinaryHeap::new();
let zero_score = K::default();
scores.insert(start, zero_score);
visit_next.push(MinScored(zero_score, start));
while let Some(MinScored(node_score, node)) = visit_next.pop() {
if visited.is_visited(&node) {
continue;
}
if goal.as_ref() == Some(&node) {
break;
}
for edge in graph.edges(node) {
let next = edge.target();
if visited.is_visited(&next) {
continue;
}
let next_score = node_score + edge_cost(edge);
match scores.entry(next) {
Occupied(ent) => {
if next_score < *ent.get() {
*ent.into_mut() = next_score;
visit_next.push(MinScored(next_score, next));
}
}
Vacant(ent) => {
ent.insert(next_score);
visit_next.push(MinScored(next_score, next));
}
}
}
visited.visit(node);
}
scores
}