//! This file implements a labelled graph that can index vertices by
//! labels.
//!
//! Since we do not have to index edges by labels, the labels can be
//! stored simply by adjacency maps.  This may save memory usage and
//! improve performance, potentially.

use super::*;

use std::collections::{hash_map::Keys, HashMap as Map};

use crate::builder::BuilderMut;

/// The type of a node.
#[derive(Debug, Clone, Default)]
struct SLNode<T: GraphLabel> {
    /// The edges are stored as an association from the target node
    /// index to the label of the corresponding edge.
    ///
    /// An implication is that an edge can only have one label.
    children: Map<usize, T>,
    /// The label of this node.
    label: T,
}

impl<T: GraphLabel> SLNode<T> {
    fn new(children: Map<usize, T>, label: T) -> Self {
        Self { children, label }
    }

    /// This function just adds an edge, blindly.
    ///
    /// # Safety
    ///
    /// Only use this after making sure that `target` refers to a
    /// valid node, and there was no edge from this node to the node
    /// pointed to by `target` previously.
    unsafe fn add_edge(&mut self, target: usize, label: T) {
        self.children.insert(target, label);
    }
}

/// The type of labelled graphs implemented using adjacency maps.
#[derive(Debug, Clone)]
pub struct SLGraph<T: GraphLabel> {
    nodes: Vec<SLNode<T>>,
    label_index_map: Map<T, usize>,
}

impl<T: GraphLabel> Default for SLGraph<T> {
    fn default() -> Self {
        let nodes = Vec::new();
        let label_index_map = Default::default();
        Self {
            nodes,
            label_index_map,
        }
    }
}

impl<T: GraphLabel> Graph for SLGraph<T> {
    type Iter<'a> = std::iter::Copied<Keys<'a, usize, T>>
    where
        Self: 'a;

    #[inline]
    fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    #[inline]
    fn nodes_len(&self) -> usize {
        self.nodes.len()
    }

    #[inline]
    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> {
        if let Some(node) = self.nodes.get(node_id) {
            Ok(node.children.keys().copied())
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
        }
    }

    #[inline]
    fn degree(&self, node_id: usize) -> Result<usize, Error> {
        if let Some(node) = self.nodes.get(node_id) {
            Ok(node.children.len())
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
        }
    }

    #[inline]
    fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> {
        if let Some(node) = self.nodes.get(node_id) {
            Ok(node.children.is_empty())
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
        }
    }

    #[inline]
    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
        let nodes_len = self.nodes.len();

        let node = if let Some(node) = self.nodes.get(source) {
            node
        } else {
            return Err(Error::IndexOutOfBounds(source, nodes_len));
        };

        if !self.has_node(target) {
            return Err(Error::IndexOutOfBounds(target, nodes_len));
        }

        Ok(node.children.contains_key(&target))
    }

    fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
        // In case this is not clear enough, I deliberately avoid
        // implementing this.
        unimplemented!()
    }
}

/// An iterator of edge labels.
///
/// This is used to avoid a box allocation.
#[derive(Copy, Clone, Debug)]
pub struct EdgeLabelIter<T: GraphLabel>(Option<T>);

impl<T: GraphLabel> Iterator for EdgeLabelIter<T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.0.is_some() as usize;

        (len, Some(len))
    }
}

impl<T: GraphLabel> DoubleEndedIterator for EdgeLabelIter<T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.take()
    }
}

impl<T: GraphLabel> ExactSizeIterator for EdgeLabelIter<T> {
    #[inline]
    fn len(&self) -> usize {
        // Thanks to Clippy for teaching me about coercing a boolean
        // value to an integer.
        self.0.is_some() as usize
    }
}

impl<T: GraphLabel> LabelGraph<T> for SLGraph<T> {
    // The following two types are not used, as we do not need to
    // index edges by labels.
    type Iter<'a> = std::iter::Empty<usize>
    where
        Self: 'a;

    type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)>
    where
        Self: 'a,
        T: 'a;

    type EdgeLabelIter<'a> = EdgeLabelIter<T>
    where
        Self: 'a,
        T: 'a;

    #[inline]
    fn query_label(&self, label: T) -> Option<usize> {
        self.label_index_map.get(&label).copied()
    }

    #[inline]
    fn vertex_label(&self, node_id: usize) -> Result<Option<T>, Error> {
        if let Some(node) = self.nodes.get(node_id) {
            Ok(Some(node.label))
        } else {
            Err(Error::IndexOutOfBounds(node_id, self.nodes_len()))
        }
    }

    #[inline]
    fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
        let nodes_len = self.nodes.len();

        let node = if let Some(node) = self.nodes.get(source) {
            node
        } else {
            return Err(Error::IndexOutOfBounds(source, nodes_len));
        };

        if !self.has_node(target) {
            return Err(Error::IndexOutOfBounds(target, nodes_len));
        }

        Ok(EdgeLabelIter(node.children.get(&target).copied()))
    }

    fn find_children_with_label(
        &self,
        _node_id: usize,
        _label: &T,
    ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, Error> {
        unimplemented!()
    }

    fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, Error> {
        unimplemented!()
    }

    #[inline]
    fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error> {
        let nodes_len = self.nodes.len();

        let node = if let Some(node) = self.nodes.get(node_id) {
            node
        } else {
            return Err(Error::IndexOutOfBounds(node_id, nodes_len));
        };

        if !self.has_node(target) {
            return Err(Error::IndexOutOfBounds(target, nodes_len));
        }

        Ok(node.children.get(&target) == Some(label))
    }
}

/// The type of `builder_mut` builders for this type of graphs.
#[derive(Debug)]
pub struct SLGBuilderMut<'a, T: GraphLabel> {
    graph: &'a mut SLGraph<T>,
}

impl<'a, T: GraphLabel> BuilderMut for SLGBuilderMut<'a, T> {
    type Label = T;

    type Graph = SLGraph<T>;

    type ResultBuilder<'b> = SLGBuilderMut<'b, T>
    where
        T:'b;

    fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_> {
        SLGBuilderMut { graph }
    }

    fn add_vertex(&mut self, label: T) -> Result<usize, Error> {
        if let Some(old_node) = self.graph.label_index_map.get(&label) {
            dbg!(label);
            return Err(Error::DuplicatedNode(*old_node));
        }

        self.graph
            .nodes
            .push(SLNode::new(Default::default(), label));

        let new = self.graph.nodes_len() - 1;

        self.graph.label_index_map.insert(label, new);

        Ok(new)
    }

    fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error> {
        let graph = &mut self.graph;

        let nodes_len = graph.nodes.len();

        // NOTE: We check the validity of `target` first because we
        // need to borrow graph mutably later, which would prevent us
        // from borrowing graph immutably to check the validity of
        // `target` then.
        if !graph.has_node(target) {
            return Err(Error::IndexOutOfBounds(target, nodes_len));
        }

        let node = if let Some(node) = graph.nodes.get_mut(source) {
            node
        } else {
            return Err(Error::IndexOutOfBounds(source, nodes_len));
        };

        if node.children.get(&target).is_some() {
            return Err(Error::DuplicatedEdge(source, target));
        }

        // We checked what we need to check, so this is safe.
        unsafe {
            node.add_edge(target, label);
        }

        Ok(())
    }

    fn remove_edge<F>(&mut self, source: usize, target: usize, predicate: F) -> Result<(), Error>
    where
        F: Fn(Self::Label) -> bool,
    {
        let graph = &mut self.graph;

        let nodes_len = graph.nodes.len();

        // NOTE: We check the validity of `target` first because we
        // need to borrow graph mutably later, which would prevent us
        // from borrowing graph immutably to check the validity of
        // `target` then.
        if !graph.has_node(target) {
            return Err(Error::IndexOutOfBounds(target, nodes_len));
        }

        let node = if let Some(node) = graph.nodes.get_mut(source) {
            node
        } else {
            return Err(Error::IndexOutOfBounds(source, nodes_len));
        };

        if let Some(child_label) = node.children.get(&target) {
            // There is only one label, so we just check this label.
            if predicate(*child_label) {
                node.children.remove(&target);
            }

            Ok(())
        } else {
            Err(Error::DuplicatedEdge(source, target))
        }
    }
}