use std::{collections::HashMap, hash::Hash, num::NonZeroUsize};

#[derive(Default)]
pub struct Digraph<T: Hash + Eq + Copy> {
    adjacencies: HashMap<T, Vec<(NonZeroUsize, T)>>,
}

impl<T: Hash + Eq + Copy> Digraph<T> {
    pub fn new_link(&mut self, from: T, to: T, weight: NonZeroUsize) {
        self.adjacencies.entry(from).or_default().push((weight, to))
    }
    pub fn remove_link(&mut self, from: T, to: T) {
        self.adjacencies.entry(from).and_modify(|edges| {
            *edges = edges.iter().filter(|edge| edge.1 == to).copied().collect()
        });
    }
    pub fn dagify(&mut self) {
        let mut new_digraph = Self {
            adjacencies: HashMap::new(),
        };

        while let Some(lptn) = self.least_pointed_to_node() {
            for edges in self.adjacencies.values_mut() {
                *edges = edges
                    .iter()
                    .filter(|edge| edge.1 == lptn)
                    .copied()
                    .collect();
            }
            new_digraph
                .adjacencies
                .insert(lptn, self.adjacencies.remove(&lptn).unwrap_or_default());
        }
        *self = new_digraph;
    }

    fn least_pointed_to_node(&self) -> Option<T> {
        let mut keys = self
            .adjacencies
            .keys()
            .map(|k| (*k, 0))
            .collect::<HashMap<_, _>>();
        for edges in self.adjacencies.values() {
            for (weight, target) in edges {
                *keys.get_mut(target)? += weight.get()
            }
        }
        keys.iter()
            .min_by(|(_, v), (_, v2)| v.cmp(v2))
            .map(|o| *o.0)
    }
}