grapes 0.3.0

//! Persistent [MapGraph] & related items
//!
//! This is the same as a [Graph](crate::graph) – a collection of nodes and edges connecting them. However, it also maintains an arbitrary mapping of `NodeKey` to nodes and `EdgeKey` to edges. So instead of using the `NodeId`s you're given, you can use almost any type to identify your nodes – for example, a [String]. (If you don't need this, it might be easier to use a regular [Graph](crate::graph).)

mod edge_iter;
mod edge_mut;
mod edge_ref;
mod node_iter;
mod node_mut;
mod node_ref;

pub use edge_iter::*;
pub use edge_mut::*;
pub use edge_ref::*;
pub use node_mut::*;
pub use node_ref::*;

use crate::graph::{EdgeId, Graph, NodeId};
use crate::map_graph::node_iter::GraphNodes;
use imbl::HashMap;
use std::hash::Hash;

/// Error: the specified node key is already present in the graph
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct KeyAlreadyExists<NodeKey>(pub NodeKey);

/// Error when inserting an edge
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum InsertEdgeError<NodeKey, EdgeKey> {
    /// No node found with the specified `NodeKey`
    NoSuchNode(NodeKey),
    /// The specified edge key is already present in the graph
    KeyAlreadyExists(EdgeKey),
}

/// A node in a [MapGraph] with its associated key
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct NodeEntry<NodeKey: Hash + Eq + Clone, NodeData: Clone> {
    /// The key associated with this node
    pub key: NodeKey,
    /// The data (weight) associated with this node
    pub data: NodeData,
}

/// An edge in a [MapGraph] with its associated key
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct EdgeEntry<EdgeKey: Hash + Eq + Clone, EdgeData: Clone> {
    /// The key associated with this edge
    pub key: EdgeKey,
    /// The data (weight) associated with this edge
    pub data: EdgeData,
}

/// A directed graph that also maintains an arbitrary key-node and key-edge mapping
///
/// See [module docs](crate::map_graph) for more information
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct MapGraph<
    NodeKey: Hash + Eq + Clone,
    NodeData: Clone,
    EdgeKey: Hash + Eq + Clone,
    EdgeData: Clone,
> {
    inner: Graph<NodeEntry<NodeKey, NodeData>, EdgeEntry<EdgeKey, EdgeData>>,
    node_map: HashMap<NodeKey, NodeId>,
    edge_map: HashMap<EdgeKey, EdgeId>,
}

impl<NodeKey: Hash + Eq + Clone, NodeData: Clone, EdgeKey: Hash + Eq + Clone, EdgeData: Clone>
    Default for MapGraph<NodeKey, NodeData, EdgeKey, EdgeData>
{
    /// The default: an empty graph
    fn default() -> Self {
        Self::new()
    }
}

impl<NodeKey: Hash + Eq + Clone, NodeData: Clone, EdgeKey: Hash + Eq + Clone, EdgeData: Clone>
    MapGraph<NodeKey, NodeData, EdgeKey, EdgeData>
{
    /// Create a new, empty, graph
    #[must_use]
    pub fn new() -> Self {
        Self {
            inner: Graph::new(),
            node_map: HashMap::new(),
            edge_map: HashMap::new(),
        }
    }

    /// Insert a node with the specified key and data
    ///
    /// Returns a mutable reference to the new node
    pub fn insert_node(
        &mut self,
        key: NodeKey,
        data: NodeData,
    ) -> Result<NodeMut<NodeKey, NodeData, EdgeKey, EdgeData>, KeyAlreadyExists<NodeKey>> {
        if self.node_map.get(&key).is_some() {
            return Err(KeyAlreadyExists(key));
        }

        let inner = self.inner.insert_node(NodeEntry {
            key: key.clone(),
            data,
        });
        self.node_map.insert(key, inner.index);

        Ok(NodeMut::new(inner, &mut self.node_map, &mut self.edge_map))
    }

    /// Get a reference to the node with the specified key.
    ///
    /// Returns [None] if there is no such node
    #[must_use]
    pub fn get_node(&self, key: &NodeKey) -> Option<NodeRef<NodeKey, NodeData, EdgeKey, EdgeData>> {
        let id = self.node_map.get(key)?;
        let inner = self.inner.get_node(*id).expect("no node for known key");

        Some(NodeRef::new(inner))
    }

    /// Get a mutable reference to a node with the specified key
    ///
    /// Returns [None] if there is no such node
    #[must_use]
    pub fn get_node_mut(
        &mut self,
        key: &NodeKey,
    ) -> Option<NodeMut<NodeKey, NodeData, EdgeKey, EdgeData>> {
        let id = self.node_map.get(key)?;
        let inner = self.inner.get_node_mut(*id).expect("no node for known key");

        Some(NodeMut::new(inner, &mut self.node_map, &mut self.edge_map))
    }

    /// Iterate over all nodes in the graph
    ///
    /// Order is unspecified
    pub fn iter_nodes(&self) -> GraphNodes<NodeKey, NodeData, EdgeKey, EdgeData> {
        GraphNodes::new(self.inner.iter_nodes())
    }

    /// Insert a new edge between the specified nodes, with the specified key and data
    pub fn insert_edge(
        &mut self,
        from: NodeKey,
        to: NodeKey,
        key: EdgeKey,
        data: EdgeData,
    ) -> Result<EdgeMut<NodeKey, NodeData, EdgeKey, EdgeData>, InsertEdgeError<NodeKey, EdgeKey>>
    {
        if self.edge_map.get(&key).is_some() {
            return Err(InsertEdgeError::KeyAlreadyExists(key));
        }

        let from_id = self
            .node_map
            .get(&from)
            .ok_or(InsertEdgeError::NoSuchNode(from))?;
        let to_id = self
            .node_map
            .get(&to)
            .ok_or(InsertEdgeError::NoSuchNode(to))?;

        let inner = self
            .inner
            .insert_edge(
                *from_id,
                *to_id,
                EdgeEntry {
                    key: key.clone(),
                    data,
                },
            )
            .expect("could not insert edge between known nodes");
        self.edge_map.insert(key, inner.id());

        Ok(EdgeMut::new(inner, &mut self.node_map, &mut self.edge_map))
    }

    /// Get a reference to the edge with the specified key
    ///
    /// Returns [None] if there is no such edge
    #[must_use]
    pub fn get_edge(&self, key: &EdgeKey) -> Option<EdgeRef<NodeKey, NodeData, EdgeKey, EdgeData>> {
        let id = self.edge_map.get(key)?;
        let inner = self.inner.get_edge(*id).expect("could not find known edge");
        Some(EdgeRef::new(inner))
    }

    /// Get a mutable reference to the edge with the specified key
    ///
    /// Returns [None] if there is no such edge
    #[must_use]
    pub fn get_edge_mut(
        &mut self,
        key: &EdgeKey,
    ) -> Option<EdgeMut<NodeKey, NodeData, EdgeKey, EdgeData>> {
        let id = self.edge_map.get(key)?;
        let inner = self
            .inner
            .get_edge_mut(*id)
            .expect("could not find known edge");
        Some(EdgeMut::new(inner, &mut self.node_map, &mut self.edge_map))
    }

    /// Iterate over all edges in the graph
    ///
    /// Order is unspecified
    pub fn iter_edges(&self) -> GraphEdges<NodeKey, NodeData, EdgeKey, EdgeData> {
        GraphEdges::new(self.inner.iter_edges())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use impls::impls;
    use std::collections::HashSet;
    use velcro::hash_set;

    impl<
            NodeKey: Hash + Eq + Clone,
            NodeData: Clone + Eq + Hash,
            EdgeKey: Hash + Eq + Clone,
            EdgeData: Clone + Eq + Hash,
        > MapGraph<NodeKey, NodeData, EdgeKey, EdgeData>
    {
        pub(crate) fn to_description(
            &self,
        ) -> (
            HashSet<(NodeKey, NodeData)>,
            HashSet<(NodeKey, NodeKey, EdgeData)>,
        ) {
            let nodes = self
                .iter_nodes()
                .map(|node| (node.key().clone(), node.data().clone()))
                .collect();

            let edges = self
                .iter_edges()
                .map(|edge| {
                    (
                        edge.get_from_node().key().clone(),
                        edge.get_to_node().key().clone(),
                        edge.data().clone(),
                    )
                })
                .collect();

            (nodes, edges)
        }
    }

    type SimpleGraph = MapGraph<i32, i32, i32, i32>;

    #[test]
    fn new() {
        let graph = SimpleGraph::new();

        assert_eq!(graph.to_description(), (hash_set!(), hash_set!()))
    }

    #[test]
    fn insert_node() {
        let mut graph = SimpleGraph::new();

        graph.insert_node(1, 2).unwrap();

        assert_eq!(graph.to_description(), (hash_set!((1, 2)), hash_set!()))
    }

    #[test]
    fn get_node() {
        let mut graph = SimpleGraph::new();

        let a = *graph.insert_node(1, 2).unwrap().key();
        let b = *graph.insert_node(3, 4).unwrap().key();

        assert_eq!(graph.get_node(&a).unwrap().data(), &2);
        assert_eq!(graph.get_node_mut(&b).unwrap().data(), &4);
    }

    #[test]
    fn remove_node() {
        let mut graph = SimpleGraph::new();

        let a = graph.insert_node(1, 2).unwrap();

        a.remove();
        assert_eq!(graph.to_description(), (hash_set!(), hash_set!()))
    }

    #[test]
    fn insert_duplicate_node() {
        let mut graph = SimpleGraph::new();

        graph.insert_node(1, 2).unwrap();
        let a = graph.insert_node(1, 2);

        assert!(matches!(a, Err(KeyAlreadyExists(1))));
    }

    #[test]
    fn removing_node_removes_edges() {
        let mut graph = SimpleGraph::new();

        let a = *graph.insert_node(1, 10).unwrap().key();
        let b = *graph.insert_node(2, 20).unwrap().key();
        let c = *graph.insert_node(3, 30).unwrap().key();

        graph.insert_edge(a, a, 11, 110).unwrap();
        graph.insert_edge(a, b, 12, 120).unwrap();

        graph.insert_edge(b, b, 22, 220).unwrap();
        graph.insert_edge(b, c, 23, 230).unwrap();

        graph.insert_edge(c, c, 33, 330).unwrap();
        graph.insert_edge(c, a, 31, 310).unwrap();

        assert_eq!(
            graph.to_description(),
            (
                hash_set!((1, 10), (2, 20), (3, 30)),
                hash_set!(
                    (1, 1, 110),
                    (1, 2, 120),
                    (2, 2, 220),
                    (2, 3, 230),
                    (3, 3, 330),
                    (3, 1, 310)
                )
            )
        );

        graph.get_node_mut(&a).unwrap().remove();

        assert_eq!(
            graph.to_description(),
            (
                hash_set!((2, 20), (3, 30)),
                hash_set!((2, 2, 220), (2, 3, 230), (3, 3, 330),)
            )
        );
    }

    #[test]
    fn persistence() {
        let empty = SimpleGraph::new();

        let mut version_a = empty.clone();
        version_a.insert_node(1, 2).unwrap();

        let mut version_b = empty.clone();
        version_b.insert_node(3, 4).unwrap();

        assert_eq!(empty.to_description(), (hash_set!(), hash_set!()));
        assert_eq!(version_a.to_description(), (hash_set!((1, 2)), hash_set!()));
        assert_eq!(version_b.to_description(), (hash_set!((3, 4)), hash_set!()));
    }

    #[test]
    fn traits() {
        assert!(impls!(
            SimpleGraph: Clone & !Copy & Send & Sync & Eq & PartialEq & Hash & std::fmt::Debug
        ));

        #[cfg(feature = "serde")]
        assert!(impls!(SimpleGraph: serde::Serialize));
    }
}