inf304-graphviz.rs

// GPL-3.0 Edgar Onghena
// Last mod: Sun 06 Dec 2020 08∶49∶15 PM CET

trait AllValues: Sized {
    fn get_all_values() -> Vec<Self>;
}

#[derive(Copy, Clone, Debug, Eq, PartialEq)]
enum Direction {
    Devant = 0b0001isize,
    Droite = 0b0010isize,
    Derriere = 0b0100isize,
    Gauche = 0b1000isize,
}

type DirNum = std::num::NonZeroI8;
#[derive(Copy, Clone, Eq, Hash, PartialEq)]
struct Directions(DirNum);

impl Directions {
    #[inline]
    fn contains(self, d: Direction) -> bool {
        i8::from(self.0) & (d as i8) != 0
    }

    fn rotate_g(self) -> Self {
        use Direction::*;

        let mut d = Directions::default();
        if (self.contains(Devant)) { d += Droite };
        if (self.contains(Droite)) { d += Derriere };
        if (self.contains(Derriere)) { d += Gauche };
        if (self.contains(Gauche)) { d += Devant };
        d
    }

    fn rotate_d(self) -> Self {
        use Direction::*;

        let mut d = Directions::default();
        if (self.contains(Devant)) { d += Gauche };
        if (self.contains(Gauche)) { d += Derriere };
        if (self.contains(Derriere)) { d += Droite };
        if (self.contains(Droite)) { d += Devant };
        d
    }
}

impl Default for Directions {
    fn default() -> Self {
        unsafe { Directions(DirNum::new_unchecked(-128)) }
    }
}

impl std::fmt::Debug for Directions {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut l = f.debug_struct("Directions");
        l.field("devant", &self.contains(Direction::Devant));
        l.field("droite", &(i8::from(self.0) & 0b0010 == 0b0010));
        l.field("derriere", &(i8::from(self.0) & 0b0100 == 0b0100));
        l.field("gauche", &(i8::from(self.0) & 0b1000 == 0b1000));
        l.finish()
    }
}

impl From<Direction> for Directions {
    fn from(d: Direction) -> Self {
        let mut new = Directions::default();
        new += d;
        new
    }
}

impl std::ops::AddAssign<Direction> for Directions {
    fn add_assign(&mut self, d: Direction) {
        unsafe {
            self.0 = DirNum::new_unchecked(i8::from(self.0) | d as isize as i8);
        }
    }
}

/// Alphabet de l'automate
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
enum Alphabet {
    /// Mesure
    M(Direction),

    A,
    D,
    G,
}

impl std::fmt::Display for Alphabet {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        use Alphabet::*;
        use Direction::*;

        f.write_str(match self {
            M(Devant) => "Mdevant",
            M(Droite) => "Mdroite",
            M(Derriere) => "Mderriere",
            M(Gauche) => "Mgauche",
            A => "A",
            D => "D",
            G => "G",
        })
    }
}

impl AllValues for Alphabet {
    fn get_all_values() -> Vec<Self> {
        // Pour écrire plus vite, j'importe les variantes de ces deux enums
        use Alphabet::*;
        use Direction::*;

        // `vec!` est une macro pour créer rapidement une liste (un `Vec`)
        vec![M(Devant), M(Droite), M(Derriere), M(Gauche), A, D, G]
    }
}

/// Etat de l'automate
#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
enum State {
    Error,
    Normal(Directions),
}

impl std::fmt::Display for State {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        use Alphabet::*;
        use Direction::*;

        match self {
            State::Error => f.write_str("Erreur"),
            State::Normal(dir) => {
                let mut l = String::with_capacity(9);
                l.push('N');
                if (dir.contains(Devant)) { l.push_str("↑") };
                if (dir.contains(Gauche)) { l.push_str("←") };
                if (dir.contains(Derriere)) { l.push_str("↓") };
                if (dir.contains(Droite)) { l.push_str("→") };
                f.write_str(&l)
            },
        }
    }
}

impl State {
    /// Etat atteignable en transitionnant d'ici avec le symbole `symbole`
    /// C'est un copier coller traduit de notre code C
    fn transition(&self, symbole: Alphabet) -> State {
        // Pour écrire plus vite, j'importe les variantes de ces deux enums
        use Alphabet::*;
        use Direction::*;

        let mut directions: Directions = match *self {
            State::Error => return State::Error,
            State::Normal(dir) => dir,
        };

        match symbole {
            A => {
                if directions.contains(Devant) {
                    State::Normal(Direction::Derriere.into())
                } else {
                    State::Error
                }
            }
            D => {
                State::Normal(directions.rotate_d())
            }
            G => {
                State::Normal(directions.rotate_g())
            }
            M(dir) => {
                // Grâce au `impl AddAssign` plus haut, je peux additionner
                // des directions.
                directions += dir;
                State::Normal(directions)
            }
        }
    }
}

impl AllValues for State {
    fn get_all_values() -> Vec<Self> {
        let mut values = Vec::with_capacity(17); // DANIEL BALAVOINE OUIIIIIIIII CASSER LA VOIX aller la voix lol ahahahahaahahahahahahahahah
        values.push(State::Error);
        for i in 0..16 {
            let dirs = DirNum::new(i + (-128)).expect("si je sais bien coder c'est bon");
            values.push(State::Normal(Directions(dirs)))
        }
        values
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn rotate_g() {
        let dirs: Directions = Direction::Gauche.into();
        let dirs = dirs.rotate_g();
        assert_eq!(dirs, Direction::Devant.into());
    }

    #[test]
    fn rotate() {
        let mut dirs = Directions::default();
        dirs += Direction::Devant;
        dirs += Direction::Gauche;
        dirs += Direction::Derriere;

        assert_eq!(dirs.rotate_g(), dirs.rotate_d().rotate_d().rotate_d());
    }

    #[test]
    fn contains() {
        let dirs: Directions = Direction::Gauche.into();

        assert!(dirs.contains(Direction::Gauche));
        assert!(!dirs.contains(Direction::Droite));
    }
}

struct Transition(Vec<Alphabet>);

fn main() {
    let tous_les_etats = State::get_all_values();
    let tous_les_symboles = Alphabet::get_all_values();

    // Liste vide mutable pour les transitions
    let mut transitions = Vec::new();

    // On doit maintenant calculer toutes les transitions possibles
    // c.f. algorithme de parcours @ inf302 paul youssef rpz yeaaaah

    for etat in tous_les_etats.iter().copied() {
        for symbole in tous_les_symboles.iter().copied() {
            transitions.push((etat, symbole, etat.transition(symbole)));
        }
    }

    // === Là on est bon, création du graphe ===

    use petgraph::graph::DiGraph;
    let mut graph = DiGraph::<State, Alphabet>::new();

    let mut states_map = std::collections::HashMap::new();

    for node in tous_les_etats {
        states_map.insert(node, graph.add_node(node));
    }

    // On recrée une liste de transitions où les transitions reliant les mêmes
    // points sont fusionnées en une seule.
    let transitions = {
        let mut transition_groups = Vec::default();

        transitions
            .map(|(from, s, to)| (*states_map.get(&from).unwrap(), s, *states_map.get(&to).unwrap()))
            .group_by(|(from, s, to)| (from, to))
            .collect();

        groups.map()
    }

    for (from, s, to) in transitions {
        graph.add_edge(*states_map.get(&from).unwrap(), *states_map.get(&to).unwrap(), s);
    }

    std::fs::write("out.dot", format!("{}", petgraph::dot::Dot::new(&graph))).unwrap();
}