dijkstra.rs

use crate::graph::*;
use crate::hash_map::HashMap;
use crate::q::PriorityQ;
use std::hash::Hash;

//Not sure if I spelled this right lol
pub fn dijkstra<T: Hash + Eq + PartialOrd + GraphNode<T>>(start: &T, goal: &T) {
    let mut pq = PriorityQ::<&T>::new();
    //HashMap<Elem, (prev nghbr with least dist, dist from prev nghbr)>
    //consider using struct to improve readability
    let mut node_meta = HashMap::<&T, (Option<&T>, usize)>::new();
    //visited means all of it's neighbors have been queued, not whether or not
    //it's distance values have been added
    //using a hashmap with unit type because I didn't feel like implementing hash set too lmao
    let mut visited = HashMap::<&T, ()>::new();
    pq.push(start, 0);
    node_meta.insert(start, (None, 0));

    while !pq.is_empty() {
        let (curr_elem, cum_dist) = pq.pop().unwrap();
        visited.insert(curr_elem, ());
        if curr_elem == goal {
            break;
        }

        for (neighbor, nghbr_dist) in curr_elem.get_neighbors() {
            //note: possible optimization would be caching hash or giving a hash hint
            //since we're hashing the same element twice
            //is_none_or is available with nightly rust, but I don't think it's worth the switch
            if node_meta.get(&neighbor).is_none()
                || cum_dist + nghbr_dist < node_meta.get(&neighbor).unwrap().1
            {
                node_meta.insert(neighbor, (Some(curr_elem), cum_dist + nghbr_dist));
            }

            if visited.get(&neighbor).is_none() {
                pq.push(&neighbor, cum_dist + nghbr_dist);
            }
        }
    }
}