graphlang 0.1.3

use std::collections::HashSet;

use crate::primitives::{Edge, Node};
use crate::{Graph, GraphGrammar, Production};

/// Generates a simple string grammar.
/// It has two productions:
/// - 'extend'   extends the chain by 1 node.
/// - 'finalize' replaces the nonterminal node by a row of terminals and
///              therefore prohibits further expansion and makes the graph
///              valid w.r.t. the graph grammar.
///
/// ```text
///       g0:  a - A
///
///   extend:  a - A  <--  a  -->  a - a - A
///         
/// finalize:  a - A  <--  a  -->  a - a
///
/// GG = ( g0, {'extend', 'finalize'}, {'a'})
/// ```
///
/// # Examples
///              
/// ```
/// # fn test() -> Option<()> {
/// let string = graphlang::predefined::string_grammar();
/// let mut g = string.start_graph.clone();
/// string.productions["extend"].apply_inplace(&mut g)?;
/// string.productions["extend"].apply_inplace(&mut g)?;
/// string.productions["finalize"].apply_inplace(&mut g)?;
/// assert!(string.is_valid(&g));
/// # Some(())
/// # }
/// # test().unwrap();
/// ```
#[must_use]
pub fn string_grammar() -> GraphGrammar<u32, &'static str, ()> {
    let start_graph = Graph {
        nodes: vec![Node::new(0, "a"), Node::new(1, "A")],
        edges: vec![Edge::new_unlabeled(0, 1)],
    };

    let productions = vec![
        // Finalize string by replacing the nonterminal node
        (
            "finalize".to_string(),
            Production::new(
                Graph {
                    nodes: vec![Node::new(0, "a"), Node::new(1, "A")],
                    edges: vec![Edge::new_unlabeled(0, 1)],
                },
                Graph {
                    nodes: vec![Node::new(0, "a")],
                    edges: vec![],
                },
                Graph {
                    nodes: vec![Node::new(0, "a"), Node::new(1, "a")],
                    edges: vec![Edge::new_unlabeled(0, 1)],
                },
            ),
        ),
        // Extend the string into the direction of the nonterminal node
        (
            "extend".to_string(),
            Production::new(
                Graph {
                    nodes: vec![Node::new(0, "a"), Node::new(1, "A")],
                    edges: vec![Edge::new_unlabeled(0, 1)],
                },
                Graph {
                    nodes: vec![Node::new(0, "a")],
                    edges: vec![],
                },
                Graph {
                    nodes: vec![Node::new(0, "a"), Node::new(1, "a"), Node::new(2, "A")],
                    edges: vec![Edge::new_unlabeled(0, 1), Edge::new_unlabeled(1, 2)],
                },
            ),
        ),
    ]
    .into_iter()
    .collect();
    let terminal_nodes = ["a"].into_iter().collect::<HashSet<_>>();
    GraphGrammar {
        start_graph,
        productions,
        terminal_nodes,
    }
}

/// Generates a graph grammar for a string with width `width`, also called ladder.
/// If `width` = 1 it reduces to a string grammar.
/// It has two productions:
/// - 'extend'   extends the lattice by 1 row of nodes.
/// - 'finalize' replaces the nonterminal node by a row of terminals and
///              therefore prohibits further expansion and makes the graph
///              valid w.r.t. the graph grammar.
///
/// ```text
/// g0: a --- a\
///     |     | A
///     a --- a/
///     
/// extend:    a \        a        a --- a \
///            |  A  <--  |  -->   |     |  A
///            a /        a        a --- a /
///         
/// finalize:  a \        a        a --- a
///            |  A  <--  |  -->   |     |
///            a /        a        a --- a
///
/// GG = ( g0, {'extend', 'finalize'}, {'a'})
/// ```
///
/// # Examples
///
/// Start by cloning the starting graph of the graph grammar:
/// ```
/// # fn test() -> Option<()> {
/// let ladder = graphlang::predefined::ladder_grammar(2);
/// let mut g = ladder.start_graph.clone();
/// # ladder.productions["extend"].apply_inplace(&mut g)?;
/// # ladder.productions["extend"].apply_inplace(&mut g)?;
/// # ladder.productions["finalize"].apply_inplace(&mut g)?;
/// # assert!(ladder.is_valid(&g));
/// # Some(())
/// # }
/// # test().unwrap();
/// ```
/// Then the productions can be applied. Note that this specific
/// order of applications of productions is carefully choosen and
/// they can fail, returning `None`. If a random graph should be
/// generated refer to `generate_random`.
/// ```
/// # fn test() -> Option<()> {
/// # let ladder = graphlang::predefined::ladder_grammar(2);
/// # let mut g = ladder.start_graph.clone();
/// ladder.productions["extend"].apply_inplace(&mut g)?;
/// ladder.productions["extend"].apply_inplace(&mut g)?;
/// ladder.productions["finalize"].apply_inplace(&mut g)?;
/// assert!(ladder.is_valid(&g));
/// # Some(())
/// # }
/// # test().unwrap();
/// ```
#[must_use]
pub fn ladder_grammar(width: u32) -> GraphGrammar<u32, &'static str, ()> {
    let interface = {
        let mut nodes = Vec::with_capacity(width as usize + 1);
        for i in 0..width {
            nodes.push(Node::new(i, "a"));
        }

        let mut edges = Vec::with_capacity(width as usize + 1);
        for i in 1..width {
            edges.push(Edge::new_unlabeled(i - 1, i));
        }

        Graph { nodes, edges }
    };

    let mut start_graph = interface.clone();
    start_graph.nodes.push(Node::new(width, "A"));
    start_graph
        .edges
        .extend(start_graph.nodes.iter().filter_map(|n| {
            if n.id == width {
                None
            } else {
                Some(Edge::new_unlabeled(n.id, width))
            }
        }));

    let mut finalization_rhs = interface.clone();
    finalization_rhs.nodes.extend(
        interface
            .nodes
            .iter()
            .map(|n| Node::new(n.id + width, n.label)),
    );
    // Add horizontal connections
    finalization_rhs
        .edges
        .extend((0..width).map(|id| Edge::new_unlabeled(id, id + width)));
    // Add vertical connections
    finalization_rhs
        .edges
        .extend((1..width).map(|id| Edge::new_unlabeled(id + width - 1, id + width)));

    let mut extension_rhs = finalization_rhs.clone();
    extension_rhs.nodes.push(Node::new(2 * width, "A"));
    extension_rhs
        .edges
        .extend((width..(2 * width)).map(|id| Edge::new_unlabeled(id, 2 * width)));

    let productions = vec![
        // Finalize string by replacing the nonterminal node
        (
            "finalize".to_string(),
            Production::new(start_graph.clone(), interface.clone(), finalization_rhs),
        ),
        // Extend the string into the direction of the nonterminal node
        (
            "extend".to_string(),
            Production::new(start_graph.clone(), interface.clone(), extension_rhs),
        ),
    ]
    .into_iter()
    .collect();

    let terminal_nodes = ["a"].into_iter().collect::<HashSet<_>>();

    GraphGrammar {
        start_graph,
        productions,
        terminal_nodes,
    }
}

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

    #[test]
    fn test_predefined_string_grammer() {
        let gg = string_grammar();
        let mut g = gg.start_graph.clone();
        for _ in 0..5 {
            gg.productions["extend"].apply_inplace(&mut g).unwrap();
        }
        gg.productions["finalize"].apply_inplace(&mut g).unwrap();
        assert!(gg.is_valid(&g));
    }

    #[test]
    fn test_predefined_string_grammer_equals_ladder_with_width_1() {
        let string = string_grammar();
        let ladder = ladder_grammar(1);
        let mut gs = string.start_graph.clone();
        let mut gl = ladder.start_graph.clone();
        for _ in 0..5 {
            string.productions["extend"].apply_inplace(&mut gs).unwrap();
            ladder.productions["extend"].apply_inplace(&mut gl).unwrap();
        }
        string.productions["finalize"]
            .apply_inplace(&mut gs)
            .unwrap();
        ladder.productions["finalize"]
            .apply_inplace(&mut gl)
            .unwrap();
        assert!(string.is_valid(&gs));
        assert!(ladder.is_valid(&gl));
        assert_eq!(gs, gl);
    }

    #[test]
    fn test_predefined_ladder_grammer() {
        let ladder = ladder_grammar(2);
        let mut g = ladder.start_graph.clone();
        ladder.productions["extend"].apply_inplace(&mut g).unwrap();
        ladder.productions["extend"].apply_inplace(&mut g).unwrap();
        ladder.productions["finalize"]
            .apply_inplace(&mut g)
            .unwrap();

        let reference = Graph {
            nodes: vec![
                // Column 1
                Node::new(0u32, "a"),
                Node::new(1, "a"),
                // Column 2
                Node::new(2, "a"),
                Node::new(3, "a"),
                // Column 3
                Node::new(4, "a"),
                Node::new(5, "a"),
                // Column 4
                Node::new(6, "a"),
                Node::new(7, "a"),
            ],
            edges: vec![
                // Vertical connections
                Edge::new_unlabeled(0, 1),
                Edge::new_unlabeled(2, 3),
                Edge::new_unlabeled(4, 5),
                Edge::new_unlabeled(6, 7),
                // Horizontal connections
                Edge::new_unlabeled(0, 2),
                Edge::new_unlabeled(2, 4),
                Edge::new_unlabeled(1, 3),
                Edge::new_unlabeled(3, 5),
                Edge::new_unlabeled(4, 6),
                Edge::new_unlabeled(5, 7),
            ],
        };

        assert!(ladder.is_valid(&g));
        assert!(crate::are_graphs_isomorph(&g, &reference));
    }
}