graphlang 0.1.3

use serde::{Deserialize, Serialize};
use std::{collections::HashMap, mem::swap};

use crate::Graph;

/// Trait alias `Index` without language support for trait aliases
pub trait Index:
    std::fmt::Debug + std::cmp::Eq + std::hash::Hash + Serialize + Clone + Default
{
}
impl<
        T: std::fmt::Debug + std::cmp::Eq + std::hash::Hash + Serialize + Clone + Default + ?Sized,
    > Index for T
{
}

/// Trait alias `Label` without language support for trait aliases
pub trait Label: std::cmp::Eq + std::fmt::Debug + std::hash::Hash + Serialize + Clone {}
impl<T: std::cmp::Eq + std::fmt::Debug + std::hash::Hash + Serialize + Clone + ?Sized> Label for T {}

/// Represents a single `Node`. It has an `id`entifier  and an optional `label`,
/// which can be removed by using the zero-sized type `()`
#[derive(Serialize, Deserialize, PartialEq, Clone, Debug)]
pub struct Node<I: Index, NL: Label> {
    pub id: I,
    pub label: NL,
}

impl<I: Index, NL: Label> Node<I, NL> {
    /// Create a new `Node` with an `id`, that is used to differentiate/identify the
    /// node which has therefore to be unique and a `label`, which determines the
    /// 'type'.
    pub fn new(id: I, label: NL) -> Self {
        Self { id, label }
    }

    /// Checks if the node has the same label as the other node `n`.
    pub fn is_isomorph_to(&self, n: &Self) -> bool {
        self.label == n.label
    }
}

/// Represents a single directed `Edge` and an optional `label`,
/// which can be removed by using the zero-sized type `()`.
/// It is recommended to use the corresponding `::new_*` methods.
#[derive(Serialize, Deserialize, PartialEq, Clone, Debug)]
pub struct Edge<I: Index, EL: Label> {
    pub from: I,
    pub to: I,
    pub label: EL,
}

impl<I: Index, EL: Label> Edge<I, EL> {
    /// Create a labeled `Edge`. Note that the current implementation
    /// does not handle/respect edge labels.
    pub fn new_label(from: I, to: I, label: EL) -> Self {
        Self { from, to, label }
    }
}

impl<I: Index> Edge<I, ()> {
    /// Create an unlabeled `Edge`.
    pub fn new_unlabeled(from: I, to: I) -> Self {
        Self {
            from,
            to,
            label: (),
        }
    }
}

// TODO: Make inner private
/// An `Isomorphism` is a map from the matching graph to the matched subgraph. You most likely
/// don't want to construct it, but use the `match_subgraph`-method.
#[derive(Serialize, Deserialize, Default, PartialEq, Clone, Debug)]
pub struct Isomorphism<I: Index>(pub HashMap<I, I>);

impl<I: Index> Isomorphism<I> {
    /// Translates a single node, if possible or else returns `None`.
    #[must_use]
    pub fn translate_node<NL: Label>(&self, node: &Node<I, NL>) -> Option<Node<I, NL>> {
        Some(Node::new(
            self.0.get(&node.id)?.to_owned(),
            node.label.clone(),
        ))
    }

    /// Checks if the preimage contains all nodes given by `nodes`.
    #[must_use]
    pub fn contains_nodes<NL: Label>(&self, nodes: &[Node<I, NL>]) -> bool {
        nodes.iter().all(|n| self.0.get(&n.id).is_some())
    }

    /// Checks if there exists a mappings for every node id in `nodes`,
    /// where each entry constitutes the lhs of one.
    #[must_use]
    pub fn contains_nodeids_on_lhs(&self, nodes: &[&I]) -> bool {
        nodes.iter().all(|n| self.0.get(n).is_some())
    }

    /// Checks if there exists a mappings for every node in `nodes`,
    /// where each entry constitutes the rhs of one.
    #[must_use]
    pub fn contains_nodeids_on_rhs(&self, nodes: &[&I]) -> bool {
        nodes.iter().all(|n| {
            for v in self.0.values() {
                if &v == n {
                    return true;
                }
            }
            false
        })
    }

    /// Checks if there exists a mapping, where `node` constitutes
    /// the lhs.
    #[must_use]
    pub fn contains_nodeid_on_lhs(&self, node: &I) -> bool {
        self.contains_nodeids_on_lhs(&[node])
    }

    /// Checks if there exists a mapping, where `node` constitutes
    /// the rhs.
    #[must_use]
    pub fn contains_nodeid_on_rhs(&self, node: &I) -> bool {
        self.contains_nodeids_on_rhs(&[node])
    }

    // Check if there is no overlap between self & other. This definition is up to debate
    // (and tests).
    #[must_use]
    pub fn can_be_safely_merged(&self, other: &Self) -> bool {
        for (k, v) in &self.0 {
            if other.contains_nodeids_on_lhs(&[k]) || other.contains_nodeids_on_rhs(&[v]) {
                return false;
            }
        }
        true
    }
}

impl<I: Index, T: AsRef<[(I, I)]>> From<T> for Isomorphism<I> {
    fn from(list: T) -> Self {
        let mut iso = Self::default();
        for (from, to) in list.as_ref() {
            iso.0.insert(from.clone(), to.clone());
        }
        iso
    }
}
/*
impl<'a, I: Index + 'a> From<&'a [(I,I)]> for Isomorphism<I>
{
    fn from(list: &[(I,I)]) -> Self {
        let mut iso = Isomorphism::default();
        for (from, to) in list {
            iso.0.insert(from.clone(), to.clone());
        }
        iso
    }
}
*/

/// A double-pushout production (DPO). For a description of the theory behind
/// it please refer to the crates `README.md`.
///
/// It is a rule how to transform a specific part of an `Graph` into another and
/// the core of a `GraphGrammar`.
#[derive(Serialize, Deserialize, PartialEq, Clone, Debug)]
pub struct Production<I: Index, NL: Label, EL: Label> {
    lhs: Graph<I, NL, EL>,
    #[serde(alias = "interface")]
    int: Graph<I, NL, EL>,
    rhs: Graph<I, NL, EL>,
}

impl<I: Index, NL: Label, EL: Label> Production<I, NL, EL> {
    #[must_use]
    pub fn new(lhs: Graph<I, NL, EL>, interface: Graph<I, NL, EL>, rhs: Graph<I, NL, EL>) -> Self {
        Self {
            lhs,
            int: interface,
            rhs,
        }
    }

    #[must_use]
    pub fn statisfies_gluing_condition(&self) -> bool {
        let _ = &self;
        unimplemented!()
    }

    // TODO: Classification methods
}

impl<I: Index> From<Production<I, &str, ()>> for Production<I, String, ()> {
    fn from(g: Production<I, &str, ()>) -> Self {
        Self {
            lhs: g.lhs.into(),
            int: g.int.into(),
            rhs: g.rhs.into(),
        }
    }
}

// TODO: Generalize s.t. Index can be used instead of u32
fn find_additional_ids<NL: Label, EL: Label>(
    graph_to_insert: &Graph<u32, NL, EL>,
    count: u32,
) -> Vec<u32> {
    let max = 1 + graph_to_insert.nodes.iter().map(|n| n.id).max().unwrap();
    (max..(max + count)).collect()
}

/// Finds all ids in `graph_to_translate` that are not covered by `isomorphism` and creates new mappings
/// using `ids`.  
fn fill_unmapped_indices<NL: Label, EL: Label>(
    graph_to_translate: &Graph<u32, NL, EL>,
    isomorphism: &mut Isomorphism<u32>,
    ids: &[u32],
) {
    //isomorphism.0.extend_reserve(ids.len());
    #[allow(clippy::clone_on_copy)]
    let new_mappings = graph_to_translate
        .nodes
        .iter()
        .map(|n| n.id)
        .filter(|id| isomorphism.0.get(id).is_none())
        .zip(ids)
        .map(|(l, r)| (l.clone(), r.clone()))
        .collect::<Vec<_>>();
    isomorphism.0.extend(new_mappings);
}

fn extend_isomorphism_for_unmapped_ids<NL: Label, EL: Label>(
    production: &Production<u32, NL, EL>,
    graph: &Graph<u32, NL, EL>,
    iso: &mut Isomorphism<u32>,
) {
    let n_new_ids_needed = production.rhs.nodes.len() - production.int.nodes.len();
    #[allow(clippy::cast_possible_truncation)]
    let additional_ids = find_additional_ids(graph, n_new_ids_needed as u32);
    fill_unmapped_indices(graph, iso, &additional_ids);
}

impl<NL: Label, EL: Label> Production<u32, NL, EL> {
    // TODO: Should be Result
    pub fn apply_inplace(&self, g: &mut Graph<u32, NL, EL>) -> Option<()> {
        let mut isomorphism = crate::graphoperations::match_subgraph(g, &self.lhs)?;
        log::warn!("      Apply to graph : {:?}", &g);
        log::warn!("      Find match for : {:?}", &self.lhs);
        log::warn!("Found p. isomorphism : {:?}", &isomorphism);
        log::warn!("     Removing from g : {:?}", &(&self.lhs - &self.int));
        log::warn!("    Inserting into g : {:?}", &(&self.rhs - &self.int));

        extend_isomorphism_for_unmapped_ids(self, g, &mut isomorphism);
        log::warn!("    Extended p. iso. : {:?}", &isomorphism);

        // TODO: New ids that cant be translated must get a new (unique) id
        let mut saved_edges = Vec::new();
        swap(&mut saved_edges, &mut g.edges);
        g.remove(&(&self.lhs - &self.int).translate_copy(&isomorphism));
        swap(&mut saved_edges, &mut g.edges);
        g.insert(&(&self.rhs - &self.int).translate_copy(&isomorphism));
        g.cleanup_edges();
        Some(())
    }

    // TODO: Should be Result
    #[must_use]
    pub fn apply(&self, g: &Graph<u32, NL, EL>) -> Option<Graph<u32, NL, EL>> {
        let mut g = g.clone();
        self.apply_inplace(&mut g)?;
        Some(g)
    }
}

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

    #[test]
    fn deserialize_reference_graph() {
        type N = Node<usize, &'static str>;
        type E = Edge<usize, ()>;
        let g = Graph {
            nodes: vec![N { id: 0, label: "a" }, N { id: 1, label: "a" }],
            edges: vec![E {
                from: 0,
                to: 1,
                label: (),
            }],
        };
        let s = std::fs::read_to_string("./tests/minimal.graph.json").unwrap();
        let d = serde_json::from_str::<Graph<_, _, _>>(&s).unwrap();
        assert_eq!(&g, &d);
    }

    #[test]
    fn serialize_and_deserialize_graph() {
        let g = Graph {
            nodes: vec![Node::new(0, "a"), Node::new(1, "a")],
            edges: vec![Edge::new_unlabeled(0, 1)],
        };
        let s = serde_json::to_string_pretty(&g).unwrap();
        let d = serde_json::from_str::<Graph<_, _, _>>(&s).unwrap();
        assert_eq!(&g, &d);
    }
}