//! This file implements a labelled graph that can index vertices by
//! labels and each node knows about its parents.

use super::*;
use crate::ParentsGraph;

use std::collections::{HashMap as Map, HashSet as Set};

use crate::builder::BuilderMut;

/// A node has some children, some parents, and a label.
#[derive(Debug, Clone)]
struct PLNode<T: GraphLabel> {
    children: Set<usize>,
    // REVIEW: If performance for removing edges is a bottleneck, use
    // a hash set here.
    parents: Vec<usize>,
    label: T,
}

impl<T: GraphLabel> PLNode<T> {
    fn new(children: Set<usize>, parents: Vec<usize>, label: T) -> Self {
        Self {
            children,
            parents,
            label,
        }
    }
}

impl<T: GraphLabel + Default> Default for PLNode<T> {
    #[inline]
    fn default() -> Self {
        let children = Default::default();
        let parents = Default::default();
        let label = Default::default();
        Self {
            children,
            label,
            parents,
        }
    }
}

/// A Parents-knowing, vertex-Labelled Graph.
#[derive(Debug, Clone)]
pub struct PLGraph<T: GraphLabel> {
    nodes: Vec<PLNode<T>>,
    label_index_map: Map<T, usize>,
}

impl<T: GraphLabel> Default for PLGraph<T> {
    #[inline]
    fn default() -> Self {
        let nodes = Default::default();
        let label_index_map = Default::default();
        Self {
            nodes,
            label_index_map,
        }
    }
}

impl<T: GraphLabel> Graph for PLGraph<T> {
    type Iter<'a> = std::iter::Copied<std::collections::hash_set::Iter<'a, usize>>
    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.iter().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()))
        }
    }

    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
        if let Some(node) = self.nodes.get(source) {
            if !self.has_node(target) {
                return Err(Error::IndexOutOfBounds(target, self.nodes.len()));
            }

            Ok(node.children.contains(&target))
        } else {
            Err(Error::IndexOutOfBounds(source, self.nodes.len()))
        }
    }

    fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
        unimplemented!("for later")
    }

    fn print_viz(&self, _filename: &str) -> Result<(), std::io::Error> {
        todo!()
    }
}

impl<T: GraphLabel> ParentsGraph for PLGraph<T> {
    type Iter<'a> = std::iter::Copied<std::slice::Iter<'a, usize>>
        where Self: 'a;

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

impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> {
    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> = std::iter::Empty<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()))
        }
    }

    fn edge_label(&self, _source: usize, _target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
        unimplemented!("Edges have no labels")
    }

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

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

    fn has_edge_label(&self, _node_id: usize, _label: &T, _target: usize) -> Result<bool, Error> {
        unimplemented!("Edges have no labels")
    }
}

/// A builder that modifies PLGraph in place.
#[derive(Debug)]
pub struct PLGBuilderMut<'a, T: GraphLabel> {
    graph: &'a mut PLGraph<T>,
}

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

    type Graph = PLGraph<T>;

    type ResultBuilder<'b> = PLGBuilderMut<'b, T>
    where
        Self::Label: 'b;

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

    fn add_vertex(&mut self, label: Self::Label) -> usize {
        if let Some(old) = self.graph.label_index_map.get(&label) {
            *old
        } else {
            let new_node = PLNode::new(Default::default(), Default::default(), label);
            self.graph.nodes.push(new_node);

            let new_index = self.graph.nodes.len() - 1;

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

            new_index
        }
    }

    fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
        if self.graph.has_edge(source, target)? {
            return Err(Error::DuplicatedEdge(source, target));
        }

        self.graph
            .nodes
            .get_mut(source)
            .unwrap()
            .children
            .insert(target);

        self.graph
            .nodes
            .get_mut(target)
            .unwrap()
            .parents
            .push(source);

        Ok(())
    }

    fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
    where
        F: Fn(Self::Label) -> bool,
    {
        if !self.graph.has_edge(source, target)? {
            return Ok(());
        }

        self.graph
            .nodes
            .get_mut(source)
            .unwrap()
            .children
            .remove(&target);

        self.graph
            .nodes
            .get_mut(target)
            .unwrap()
            .parents
            .retain(|parent| *parent != source);

        Ok(())
    }
}

// TODO: tests