Alien dictionary

use std::collections::{HashMap, VecDeque};

struct Solution;

struct Graph {
    edges: HashMap<char, Vec<char>>,
    indegree: HashMap<char, usize>,
}


impl Graph {
    fn new() -> Self {
        Graph { edges: HashMap::default(), indegree: HashMap::default() }
    }

    fn add_vertex(&mut self, vertex: char) {
        self.edges.entry(vertex).or_insert(vec![]);
        self.indegree.entry(vertex).or_insert(0);
    }

    fn add_edge(&mut self, from: char, to: char) {
        self.edges.entry(from).or_insert(vec![]).push(to);
        *self.indegree.entry(to).or_insert(0) += 1;
    }

    fn find_dangling(&self) -> Vec<char> {
        self.indegree.iter()
            .filter(|(_, &count)| count == 0)
            .map(|(&vertex, _)| vertex)
            .collect::<Vec<char>>()
    }

    fn get_adjacent(&self, vertex: char) -> &Vec<char> {
        self.edges.get(&vertex).unwrap()
    }

    fn decrease_incoming(&mut self, vertex: &char) -> Option<usize> {
        match self.indegree.get_mut(vertex) {
            None => None,
            Some(count) => {
                *count = count.saturating_sub(1);
                Some(*count)
            }
        }
    }

    fn len(&self) -> usize {
        self.edges.len()
    }
}

impl Solution {
    pub fn alien_order(words: Vec<String>) -> String {
        let mut result = String::new();

        let mut graph = match Self::build_graph(&words) {
            None => return result,
            Some(graph) => graph
        };

        let mut queue = VecDeque::from(graph.find_dangling());

        while let Some(vertex) = queue.pop_front() {
            result.push(vertex);

            for adjacent in graph.get_adjacent(vertex).clone() {
                match graph.decrease_incoming(&adjacent) {
                    Some(count) if count == 0 => queue.push_back(adjacent),
                    _ => {}
                }
            }
        }

        if result.len() < graph.len() {
            return "".to_string();
        }

        result
    }

    fn build_graph(words: &[String]) -> Option<Graph> {
        let mut graph = Graph::new();
        words.iter()
            .flat_map(|work| work.chars())
            .for_each(|char| graph.add_vertex(char));

        let pair_iter = words.iter().zip(words.iter().skip(1));
        for (w_curr, w_next) in pair_iter {
            // broken ordering
            if w_curr.len() > w_next.len() && w_curr.starts_with(w_next) {
                return None;
            }

            let first_difference = w_curr.chars()
                .zip(w_next.chars())
                .find(|(ch_curr, ch_next)| ch_curr != ch_next);

            if let Some((ch_curr, ch_next)) = first_difference {
                graph.add_edge(ch_curr, ch_next);
            }
        }

        Some(graph)
    }
}


#[cfg(test)]
mod tests {
    use arrays::create::LeetCodeArrayTestHelper;

    use crate::alien_dictionary::bfs::Solution;

    #[test]
    fn test() {
        println!("{:?}", Solution::alien_order(
            ["wrt", "wrf", "er", "ett", "rftt"].to_string_vec()
        ));
    }
}